У. Питерсон - Коды, исправляющие ошибки (1267328), страница 29
Текст из файла (страница 29)
Таким образом, сравнивая синдром с матрицей Нт, можно найти положение ошибки н затем исправить ее, просто заменив соответствующий символ на правильный. Особенноудобно это делать, если использовать в качестве 1-го столбца матрицы Н двоичное представление числа й Тогда для каждой отдельной одиночной огпибки синдром является двоичным представлением номера разряда, в котором произошла ошибка. Это расположение первоначально использовано Хэммингом !138~. Пример.
Для т'= 3, и = 2' — 1 = 7 в качестве проверочной может быть выбрана следующая матрица: 00 01111 Н = 0110011 1010101 Кодирование легко проводится, если в качестве проверочных выбраны первый, второй и четвертый символы, так как каждый из этих символов*входит только в одно из проверочных соотношений, задаваемых матрицей Н. Чтобы закодировать информационные символы 1100, нужно определить проверочные символы в слове р~ пз 1 рз! 00. Символ р~ должен быть выбран так, чтобы удовлетворялось проверочное соотношение, задаваемое последней строкой матрицы Н, т.
е. чтобы Р~+ 1+ 1+ 0= 0. Следовательно, р~ = О. Аналогично рз = 1 и рз — — 1, и кодовый вектор равен 01! 1100, Предположим, что пятый символ принят ошибочно, тогда будет получен вектор 0 1 1 100 0. Легко вычислить синдром, который оказывается равным 101 — величине, соответствующей пятому столбцу матрицы Н н указывающей на то, что ошибка произошла в пятом символе полученного вектора. Синдром является двоичным кодом числа 5, поскольку каждый столбец матрицы Н выбирался как двоичное представление номера столбца. Двоичный код с минимальным весом, равным 4, может быть получен прибавлением к двоичному коду Хэмминга одного проверочного соотношения, проверяющего на четность совокупность всех символов кода.
Действительно, добавление одного проверочного символа, который является суммой всех символов некоторого двоичного кода, эквивалентно присоединению символа 0 ко всем словам четного веса н присоединению символа 1 ко всем словам нечетного веса. Поэтому если минимальный вес кода нечетный, то добавление еще одного проверочного соотношения увеличивает минимальный вес на 1. Получается т+ 1 проверочных символов, 2 — пг' — 1 информационных символов (столько же, сколько у кода, исправляющего все одиночные ошибки) и, следовательно, всего и = 2~ символов.
Пример. Проверочная матрица для (8,4)-кода Хэмминга, исправляющего все одиночные ошибки и обнаруживающего все двоичные ошибки, имеет вид 00001111 00110011 01010101 11111111 Декодирование для такого кода проводится следующим образом: 1. Если синдром равен О, то предполагается, что ошибок не было. 2. Если проверка по всем символам (соответствующая последней строке матрицы Н в приведенном выше примере) дает 1, то предполагается, что произошла одна ошибка. Синдром будет совпадать с вектор-столбцом матрицы Н, соответствующим ошибке. 3. Если проверочный символ, полученный как результат проверки по всем символам, равен О, а хотя бы один из остальных проверочных символов равен 1, то обнаружена неисправимая ошибка. Можно доказать, что код Хэмминга с расстоянием, равным 4, является квазисовершенным.
(См. задачу 5.2.) И в этом случае можно отбросить некоторые столбцы проверочной матрицы, чтобы получился код с минимальным расстоянием, равным 4, для любой длины п ~ 2, На первый взгляд может показаться, что, для того чтобы обобщить код Хэммннга на случай, когда символы кода принадлежат некоторому полю с и ) 2 элементами, необходимо только выбрать в качестве проверочной матрицы Н матрицу размерности гп Х(д — 1), столбцами которой являются все возможные различные наборы длины т.
Однако это не так, поскольку теперь не- которые нетривиальные линейные комбинации двух столбцов равны О. НапРимеР, над полем из тРех элементов сУмма вектоРов (2 1) и (1,2) равна (0,0). Затруднение возникает потому, что вектор (1, 2) получается умножением вектора (2, 1) на скаляр. В случае двоичного кода единственный ненулевои скаляр тривиален. Эту трудность можно преодолеть, если нз каждого класса векгоров, отличающихся друг от друга на скалярный множитель, выбирать только один вектор, например содержащий ! в качестве первой ненулевой компоненты, Тогда среди столбцов матрицы Н никакие два не являются линейно зависимыми, и нулевое пространство матрипы Н вЂ” это код с минимальным расстоянием, равным 3, исправляющий любую ошибку в отдельной компоненте.
Всего имеется д™ вЂ” ! ненулевых наборов длины т, причем у 1/(д — 1)-й доли их первый ненулевой символ равен 1. Максимальное число столбцов матрицы Н равно поэтому (д'" — 1)/(и — 1). Пример. В поле из трех элементов код с тремя проверочными символами является нулевым пространством матрицы 0000111111111 Н = 0111000111222 !012012012012 Этот код длины (Зз — 1)/(3 — 1) = 13 с 10 информационными символами может исправить любую ошибку в любом отдельном символе. Кодирование легко проводится, если в качестве проверочных символов выбраны первый, второй и пятый символы, т.
е. символы, соответствующие столбцам с единственным ненулевым элементом. Если передавалось кодовое слово ц и произошла ошибка, в результате которой !-й символ увеличился на Ь, то полученный вектор равен и+ е, где е — вектор, содержащий Ь в качестве /-й компоненты и нули в качестве всех остальных компонент. Тогда синдром равен (и+в) Нг=пНг+еНг=еНг (5.1) Этот вектор представляет собой просто транспонированный !-й столбец матрицы Н, умноженный на Ь. Поэтому первый ненулевой символ синдрома равен Ь. Следовательно, для проведения декодирования нужно разделить синдром на его первый ненулевой символ Ь.
Вектор, найденный в результате деления, будет указывать столбец матрицы Н, соответствующий положению ошибки, и для гого, чтобы исправить ошибку, нужно вычесть Ь из соответствующего символа в полученном векторе. Обобщенный код Хэмминга с максимальным числом символов и = (9™ — 1)/(д — 1) является совершенным, поскольку все п(д — 1) = д — 1 векторов„соответствующих одиночным ошибкам, и нулевой вектор должны быть образующими смежных классов; таким образом, этим исчерпываются все возможные д смежных классов. (См.
задачу 5.3.) Нетрудно найти распределение весов для нулевого пространства кода Хэмминга (см. равд. 8.4), и, следователыю, распределе. ние весов самого кода Хэмминга может быть найдено с помощью формул Мак-Уильямс. (См. задачи 5.7, 5.8 и 5.9.) 5.2. (23, 12)-код Голея Занимаясь поиском совершенных кодов, Голей заметил, что Сом+ С~м. + См~+ Саек 2 и, таким образом, может существовать совершенный двоичный (23,12)-код, исправляющий все комбинации из трех или меньшего числа ошибок.
Ои нашел, что такой код действительно существует. Мы не будем описывать здесь этот код, поскольку он ниже будет рассматриваться как циклический. ь1исло кодовых векторов, входящих в (23, 12)-код и в (24,12)- код, получаемый из первого кода дополнительной проверкой на четность по всем символам, указано в табл. 5.1. Таблица 5.1. Вес кодовых векторов в кодах Голеи Число кодовых слов укаааккого асса <м,иркол 1ав,32ркод Всего Коды, содержащие один информационный символ, повторенный 2пг+1 раз, исправляют все комбинации из пт или меньшего числа ошибок и не исправляют комбинаций из более чем и оши- 0 7 8 11 12 15 16 28 24 1 258 506 1288 1288 866 258 1 0 1 О 759 о 2576 о 759 О 1 бок Кроме этих тривиальных кодов, кода Хэмминга и (23,12)- кода Голея, неизвестно никаких других совершенных двоичных кодов.
Единственным известным нетривиальным совершенным не- двоичным кодом является троичный (11,5)-код с 1= 3 (см. задачу 5,19). Имеются некоторые результаты, показывающие, что совершенных кодов мало„и кажется вполне правдоподобным, что не существует других совершенных кодов, кроме перечисленных выше 18, 54, 188, 274).
5.3. Оптимальные коды для двоичного симметричного канала Поиски оптимальных кодов для двоичного симметричного канала до сих пор ведутся с весьма ограниченным успехом. Коды с одним информационным символом, повторенным нечетное число раз, очевидно, оптимальны", коды Хэмминга образуют другой бесконечный класс оптимальных кодов. Некоторые коды, получаемые из кодов Хэмминга отбрасыванием столбцов, как можно показать, являются квазисовершенными и, следовательно, оптимальными. (См. задачу 5.3.) Коды Боуза — Чоудхури — Хоквингема (БЧХ-коды), исправляющие две ошибки, квазисовершенны и, следовательно, оптимальны 1125).
Значения и и й для остальных известных оптимальных кодов приведены в табл. 5.2. Известные оптимальные коды распадаются на два класса: 1) коды, про которые было доказано, что они являются квазисовершеннымн и, следовательно, оптимальными, и 2) коды, относительно которых было доказано, что они не хуже, чем любой другой код с таким же общим числом символов и с тем же самым числом информационных символов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
