Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
,96 Теперь уже голосование осуществляется по значениям аи аг+а4, as-fao, a5+ag, и в результате получается значение а[ следующего символа сообщения. Дальнейшие такты работы схемы совершенно аналогичны. Если произошло не более одной ошибки, то последовательность (а'0, а[,. . . . . ., а«) и есть верное кодовое слово.
Как мы видим, в схеме используется только информация о принятом слове; никакой дополнительной информации не требуется. А это очень важно, потому что именно необходимость хранения большого объема данных служит основным препятствием для применения некоторых методов декодирования (например, синдромного декодирования).
Еще одно немаловажное достоинство голосования по сравнению с другими методами декодирования заключается в том, что этот метод зачастую позволяет исправлять или обнаруживать многие ошибки, кратность которых превышает (d— 1 )/2.
Задачи и дополнения
1. Доказать, что код из примера § 8 с проверками на четность по строкам и по столбцам является полностью ортогонализуемым, составив для каждого из символов систему из трех ортогональных проверок (например, проверки
al=a2+as+?i>
оц=а«+а»+р4.
аі=«5+аб-Ьав+ай+Рз+Р5+Рв+Р7
образуют требуемую систему для символа 0?),
2. Проверить, что (7,4)-код Хемминга не является полностью ортогонализуемым, показав, что для символа а* не существует пары ортогональных проверок.
Будет ли полностью ортогонализуемым расширенный (8,4)-код Хемминга?
3. Решить те же вопросы, что и в задаче 2, для произвольного двоичного кода Хемминга и его расширенного варианта.
4. Построить систему ортогональных проверок и мажоритарный декодер для троичного циклического (13,6)-кода с порождающим многочленом
g(*)=(*+2) (**+2*Ч-2*+2) (*»+*?+2).
18. МНОГОСТУПЕНЧАТОЕ ГОЛОСОВАНИЕ И КОДЫ РИДА — M АЛ Л EPA
Мы расскажем здесь о кодах, для которых найден замечательный алгоритм исправления ошибок, сыгравший важнейшую роль в развитии методов мажоритарного декодирования.
4 М. Н. Аршянов, Л. В. СадовскиЯ 97 Проще всего начать с расширенного (8,4)-кода Хемминга. Нетрудно убедиться, что этот код дуален самому себе, т. е. что его проверочная матрица служит для него и порождающей:
/MlIlllb с /о О О 0 1 1 1 1 ° і 0 0 1 10 0 1 1 \0 1 О 1 О 1 О 1
Этот код не является полностью ортогонализуемым (см. § 17, задача 2). Значит ли это, что голосование для этого кода невозможно? Оказывается, нет.
Идея, которую мы проиллюстрируем на данном примере, состоит в следующем. Если нельзя составить нужной системы ортогональных проверок для каждого символа в отдельности, то, может быть, это удастся сделать для определенных линейных комбинаций этих символов.
Пусть ®=(а„, Gti, а2, а3, а4, а6, а„, а,) — произвольное кодовое слово. Оно, как обычно, может быть записано в виде:
^==0.)^.)+^^1+0^2+03^3- (1)
Выясним, как связаны координаты а, вектора v с коэффициентами равенства (1). Заметим, что сумма первых двух координат каждого из векторов g0, и равна О, тогда как для вектора^ она равна 1. Поэтому сумма соответствующих координат вектора v равна а3, т. е.
Оз=ао+аі- (2)
Совершенно так же убеждаемся, что верны равенства:
аз=а2+аз.
o3=a4+a6. (3)
os=ae+a7.
Нетрудно понять, что соотношения (2) и (3) представляют систему ортогональных проверок для коэффициента а3. Для коэффициентов а2 и аі дело обстоит аналогично и ортогональные проверки для них таковы:
о2=а0+а2, «і=ао+а4.
O2=Ot1+^ Oi=otI+а5» (4)
O2=а4+а6, O1=CC2+^
ва = «5+«7. Ai1 = Cl4 + **,.
,98 Применяя к полученным проверкам принцип большинства, мы найдем верные значения коэффициентов сч, ai, а3, если произошло не более одной ошибки. В случае двойной ошибки при определении хотя бы одного из коэффициентов голоса распределятся поровну и ошибка будет только обнаружена.
Предположим, что верные значения коэффициентов Q1-, а2, а3 найдены. Тогда еще один этап голосования позволяет определить также и верное значение коэффициента а„. Сделать это совсем несложно. В самом деле, рассмотрим разность
V1 = V CligtI аг?ъ—a3g3.
В случае безошибочной передачи, в силу равенства (1), V1=Ctfjg0, т. е. все координаты вектора V1 равны а0. Значит, либо все они равны нулю, либо все равны единице. Поэтому в качестве верного значения q0 выбираем то, которое преобладает среди координат вектора Vі.
Определив значения коэффициентов а„, CL1, а2, а3% мы без труда восстанавливаем кодовое слово согласно равенству (1).
Пример. Пусть принято слово 011IOl 10, содержащее одиночную ошибку. Для декодирования обращаемся к равенствам (2), (3) и (4), которые в данном случае дают следующие результаты:
Q1=O, Q2=I, Q8-I, !
Q1=O, Q2 = O, Qj=O, q1 = O, qa=i, Qs=i, O1=I, й2=1, а„=1.
По большинству значений находим: Q1=O; a2=as = I . Тогда
W1=COl 110110)—(00110011)-(01010101) = (00010000), откуда Q0=O. Следовательно,
*>=g-2+g-3=(01100110).
' Этот изящный метод декодирования может быть применен к так называемым кодам Рида — Маллера (сокращенно :—РМ-коды), которые мы и хотим сейчас рассмотреть.
РМ-код первого порядка определяется как код, дуальный к расширенному коду Хемминга, т. е. как код, порождающая матрица которого совпадает с проверочной матрицей расширенного кода Хемминга. Таким образом, расширенному («, ?)-коду Хемминга (п=2т, k=2m—m—\) отвечает (п, п—^)-код Рида — Маллера. При т=3 оба кода сов-
