§ 7.3. Коды Хемминга

Мы показали, что -код Хемминга с кодовым расстоянием может быть ортогонализован в 2 шага. Этот код принадлежит классу кодов с открытому Хеммингом [21]. Эти коды — циклические. Они являются также плотноупакованными; это означает, что любая из возможных принятых последовательностей длины отстоит от некоторого кодового слова на расстоянии или менее. Поэтому в случае двоичного симметричного канала любой алгоритм декодирования, исправляющий одиночную ошибку в блоке, будет алгоритмом декодирования по методу максимального правдоподобия (см. приложение Б). Таким образом, мажоритарное декодирование при ортогонализации в 2 шага для -кода

является одновременно алгоритмом декодирования по максимуму правдоподобия.

Покажем теперь, что все коды Хемминга допускают ортогонализацию в L шагов при некотором а потому в случае двоичного симметричного канала мажоритарное декодирование при ортогонализации в L шагов является декодированием по максимуму правдоподобия. Мы вовсе не предлагаем пороговое декодирование при ортогонализации в L шагов в качестве обязательного пути декодирования этих кодов, так как к ним можно применить очень простые способы декодирования, такие, как первоначально предложенный Хеммингом [21], или развитый Хаффменом [19]. Наша цель состоит только в том, чтобы показать, что метод обобщенного порогового декодирования приложим по крайней мере к одному классу кодов с высокой скоростью передачи.

Теорема 23. При -коды Хемминга порядка с кодовым расстоянием могут быть ортогонализованы в L шагов, где L не более чем

Доказательство. Проверочная матрица кода Хемминга порядка такова, что столбцы матрицы содержат все различные ненулевые последовательности длины веса не менее двух. Согласно теореме 21, при можно ортогонализовать -код в один шаг. При как уже показано, можно ортогонализовать -код в два шага. Покажем теперь по индукции, что код порядка можно ортогонализовать в шаг.

Предположим сначала, что символ встречается в нечетном числе первоначальных проверок, т. е. что первый столбец матрицы имеет нечетный вес. Тогда пусть будет строкой матрицы суммой остальных строк этой матрицы, при этом имеют единицы одновременно в тех и только тех позициях, которые соответствуют столбцам четного веса матрицы Я, причем в строке в этой позиции стоит единица. Таким образом, образуют систему проверок, ортогональных

относительно суммы информационных шумовых символов в этих разрядах. Можно построить таких пар ортогональных проверок. Предположив суммы известными, можно использовать их для исключения всех единиц из столбцов четного веса матрицы Первоначальное множество столбцов нечетного веса матрицы составляют только ненулевые столбцы. Тогда, отбрасывая последнюю строку и сплошь нулевые столбцы, преобразуем матрицу соответствующую проверочной матрице кода Хемминга порядка. Символ по-прежнему контролируется модифицированной проверочной матрицей, так как его разряд соответствовал столбцу нечетного веса матрицы

Предположим теперь, что символ встречается в четном числе первоначальных проверок, т. е. первый столбец матрицы четного веса. Рассмотрим множество сумм, известных по предположению и описанных в предыдущем абзаце. Эти суммы содержат в общей сложности различных шумовых символов, а именно те информационные шумовые символы, позиции (номера) которых соответствуют столбцам четного веса матрицы Эти суммы сами по себе соответствуют модифицированной проверочной матрице, составленной из всех столбцов четного веса матрицы Отбросим любую строку этой матрицы (если имеются только две модифицированные проверки, контролирующие то отбросим ту строку, которая не контролирует символа т. е. отбросим одну из сумм. Оставшиеся сумм определяют модифицированную проверочную матрицу, которая соответствует коду Хемминга порядка Модифицированные проверочные символы представляют собой информационных шумовых символов, которые контролировались, помимо отброшенной, еще только одной строкой.

После выполнения этого процесса раз мы получим проверочную матрицу кода Хемминга третьего пэрядка и символ будет контролироваться по-прежнему. Этот код допускает ортогонализацию в 2 шага. Таким образом, после шага

процесса ортогонализации можно образовать проверки, ортогональные относительно (мы не доказывали, что это наименьшее возможное число шагов). Ясно, что те же самые рассуждения применимы чем и завершается доказательство теоремы.