Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
р(х, г)+р (г, у)^-р(х, г/)>2Ж.
Значит, для восстановления посланного слова (декодирования) необходимо найти кодовое слово х, «ближайшее» к принятому слову z в смысле расстояния Хемминга. Подчеркнем, что это правило декодирования приводит к правильному результату, если число ошибок в передаваемом слове действительно не превосходило t.
Если же условие d(V)>2t нарушается, то найдутся такие кодовые слова х и у, расстояние между которыми р (х, y)^2t. Тогда может найтись такая комбинация из t ошибок в одном из слов X, что принятое слово г будет находиться от другого слова у не дальше, чем от х. Поэтому нельзя будет определить, какое из слов — X или у — было на самом деле передано
Задачи и дополнения
1. Имеется 8 двоичных слов длины 3. Их можно изобразить в пространственной системе координат как вершины куба со стороной 1. Каков в этом случае «геометрический смысл» расстояния Хемминга между словами?^ 2. Доказать, что для обнаружения s (или меньшего числа) ошибок необходимо и достаточно, чтобы кодовое расстояние удовлетворяло неравенству d (V)^sjr 1.
3. Доказать, что для исправления t (и меньшего числа) ошибок и вместе с этим обнаружения s (и меньшего числа) ошибок (s^t) необходимо и достаточно, чтобы кодовое расстояние удовлетворяло неравенству d(V)^t+s-\-1.
4. Показать, что кодовое расстояние для кода с общей проверкой на четность равно двум, а для кода Хемминга — трем. Чему оно равно для кода с повторением, чему — для расширенного кода Хемминга?
II. ЛИНЕЙНЫЕ ИЛИ ГРУППОВЫЕ КОДЫ
Большинство рассмотренных выше кодов обладало следующим свойством: сумма (и разность) двух кодовых слов также являлась кодовым слово,м. Для кода с повторением это свойство очевидно. Ясно оно и для кода с общей проверкой на четность, потому что сумма двух слов с четным числом единиц есть также слово с четным числом единиц.
В § 9 был рассмотрен код Хемминга с системой проверочных соотношений (5). Обобщим теперь этот пример, выбрав в качестве кодового алфавита некоторое конечное поле F. Каждое слово XiX2. . .хп этого алфавита будем отождествлять с вектором (X1, х2, ... , хп) n-мерного пространства Ln (в котором координаты векторов являются элементами F). Вектор, соответствующий кодовому слову, будем называть кодовым. Систему проверочных соотношений запишем в виде системы уравнений:
611X1 + 612*2+. - . + 6і,Лг = 0,
621X1+62^2 + . . . + 62пх„=0, (1)
bmiX1-[-bm2X2 К • .jTbmnXn—О
с коэффициентами Ьи из F. Код, состоящий из всех слов X1X2. . .хп, для которых справедливы соотношения (1), называют кодом с проверками на четность.
Для такого кода выполняется следующее свойство: если векторы (?i, а2, ... , ап) и (Ьг, 62, ... , Ьп) являются кодовыми, а значит, решениями системы (1), то и их сумма (? + +61, U2+62, . . . , ап+Ъп) также является решением этой системы и потому кодовым вектором. Справедливо и другое свойство решений системы (1): если а — элемент поля F и (?i, а2, ... , ап) — решение системы (1), то и вектор (CLal, аа2, . . . , ссап) также является решением системы (1).
50 Оба отмеченных свойства проверяются непосредственной подстановкой в систему (1) векторов
(a-i+bi, a2+b2, . . . , an+bn) и (ааь аа2, . . . , аап).
Вместе эти свойства означают, что код с проверками на четность образует линейное подпространство в пространстве Ln всех я-буквенных слов. По этой причине коды с проверками на четность называют линейными кодами (двоичные линейные коды называют также групповыми). Если кодовое подпространство в пространстве Ln имеет размерность k, то употребляют для большей определенности термин линейный (п, &)-код.
Имеется очень много причин, по которым линейные коды являются важнейшими в теории кодирования. Одна из них связана с удобствами в обнаружении и исправлении ошибок, как это видно из примера, рассмотренного в § 9. Другая причина — это возможность компактного задания кода. Действительно, в случае линейного кода нет необходимости указывать полный список кодовых слов, ведь код вполне определен системой линейных уравнений (1) или матрицей этой системы (проверочной матрицей):
В дальнейшем мы будем предполагать, что строки этой матрицы линейно независимы.
К числу других достоинств линейных кодов, которые связаны с предыдущими, относятся простые алгоритмы кодирования и декодирования, легко реализуемые электронными переключательными схемами. Вообще, можно сказать, что бурное развитие теории кодирования, которое происходило в последние десятилетия, объясняется главным образом тем, что к линейным кодам приложим хорошо развитый аппарат линейной алгебры и теории конечных полей.
Возвращаясь к рассмотренным ранее кодам, легко найдем их проверочные матрицы. Так, для кода с общей проверкой на четность имеем одно проверочное соотношение ¦ .+.X71=O; соответственно этому проверочная матрица состоит из одной строки и имеет вид
//=(111.. .1).
51 Из проверочных соотношений для кода с повторением
X1—X2=O, X1-X3=O,
X1-Xn=O
,получаем следующую проверочную матрицу!
/1 -1 0 ... о\
н= \ .° -1/;;. .0I-
