13.2. СХЕМЫ МАЖОРИТАРНОГО ДЕКОДИРОВАНИЯ

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

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

Над эта матрица принимает вид

В тех проверочных равенствах, которые включают правая компонента равна единице. Существует восемь таких равенств, коэффициенты которых определяются следующим образом:

Выбрав третью, четвертую и седьмую строки, получим равенства

образующие искомое множество трех равенств, которые согласуются в первой координате, содержащей Основываясь на них, получим декодер, изображенный на рис. 13.1. Если первоначально регистр сдвига содержит принятый вектор, то в случае, когда произошла одна ошибка, после семи сдвигов он будет содержать исправленное кодовое слово.

Рис. 13.1. Мажоритарный декодер для симплексного -кода.

Конечно, для исправления одной ошибки необходимо использовать лишь два из приведенных выше проверочных равенств. Добавление третьего равенства приводит к декодеру, основанному на правиле решения «два из трех», а не на правиле «два из двух». До тех пор пока происходят одиночные ошибки, оба декодера ведут себя одинаково, но, если произошло две ошибки, поведение декодеров становится различным. Декодер «два из трех» исправляет несколько большую долю конфигураций из двух ошибок, хотя оба декодера не исправляют или неправильно исправляют большинство конфигураций из двух ошибок. При желании можно потребовать, чтобы удовлетворялись все три проверочных равенства. Тогда декодер будет исправлять все одиночные и обнаруживать все двойные ошибки.

Можно превратить мажоритарный декодер в декодер Меггитта. Напомним, что синдромный многочлен определялся или как

или как

Через проверочную матрицу синдромный многочлен линейно связан с принятым многочленом Запишем каждый коэффициент в виде

Любое другое проверочное равенство получается как некоторая линейная комбинация строк т. е. как линейная комбинация компонент синдрома. Поэтому все проверочные соотношения.

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

Симплексный -код является циклическим, и его порождающий многочлен равен Пусть

Это соотношение можно переписать в виде

Для мажоритарного декодирования будем использовать следующие проверочные равенства:

Выражение в левой части первого из них совпадает с второе — с , а третье — с На рис. 13.2 показан мажоритарный декодер, реализованный как декодер Меггитта.

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

Для того чтобы мажоритарный декодер, реализованный как декодер Меггитта, исправлял большое число конфигураций ошибок вне радиуса упаковки, необходимо добавить цепь обратной

Рис. 13.2. Декодер Меггитта для симплексного -кода.

связи; такая цепь показана на рис. 13.2. Если декодирование вне радиуса, упаковки не играет особой роли, то цепь обратной связи можно опустить.