§ 7.4. Коды Боуза — Чоудхури

Коды Хемминга можно рассматривать как частный случай более общего класса циклических кодов, известных под названием кодов Боуза — Чоудхури [2] (эти коды были независимо открыты Хоквингемом [22]). Хотя нам и не удалось доказать, что все коды этого класса допускают ортогонализацию в L шагов, все же мы проверим, что коды длины не более 15 допускают такую ортогонализацию. Имеется четыре таких кода. -коды являются кодами Хемминга и допускают ортогонализацию в 2 и 3 шага соответственно, согласно теореме 2.3. -код, как показано в § 6.3, может быть ортогонализован в один шаг. Как будет сейчас показано, оставшийся -код с кодовым расстоянием допускает ортогонализацию в 2 шага.

В проверочной матрице -кода Боуза — Чоудхури строки матрицы суть

Они соответствуют информационным шумовым символам, которые контролируются проверками от до соответственно. Для этого кода, как показано

в (191), можно построить проверок, ортогональных относительно Так как код циклический, то можно построить также проверки, ортогональные относительно что легко проверить и непосредственно.

Рис. 27. Комбинаторный элемент циклического декодера типа I для -кода Боуза — Чоудхури. Проверки на четность от до соответствуют уравнениям 1—10 системы (27). На выходе каждого мажоритарного элемента будет 1, если 1 поступили не менее чем на 4 входа.

Таким образом, считая эти суммы известными, мы можем исключить переменные из первоначальных проверочных уравнений. Из этих сумм можно образовать любые суммы четного числа переменных Это позволяет исключить из шести проверок формулы (191), контролирующих все остальные информационные символы. Этот процесс преобразует матрицу из которой можно построить шесть проверок,

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

Для иллюстрации средств, которыми проводится ортогонализация в L шагов, на рис. 27 показан комбинаторный элемент, пригодный к использованию в циклическом декодере типа I для -кода Боуза — Чоудхури. Остальная часть схемы декодирования такая же, как у описанного в § 6.3 декодера типа I для циклического кода, допускающего ортогонализацию в один шаг.

Три верхних мажоритарных элемента на рис. 27 используются для получения декодированных значений сумм Затем эти суммы трактуются как добавочные проверки и комбинируются с первоначальными проверками для построения системы проверок, ортогональных относительно Эти последние проверки затем обрабатываются четвертым мажоритарным элементом для получения декодированного значения символа Следует отметить, что в этом случае требуется два уровня мажоритарных элементов. Вообще для ортогонализации в L шагов требуется L уровней пороговых элементов. Однако, как было объяснено в § 7.2, для комбинаторного элемента всегда требуется не более чем мажоритарных элементов. Таким образом, вовсе не требуется, чтобы число мажоритарных элементов росло экспоненциально с ростом как было бы, если бы L уровней мажоритарных элементов имели структуру полного дерева.