-*®-*®-*с(х)

Рис. 6.13. Несистематический кодер для (15, 11)-кода Хэмминга.

4-битовйя И-битобое прокяайка информационное / / слово

15-битовое кобобое слово

Рис 6.14. Кодирование длинного потока битов.

Открыто на гослеЭних А тактах

, Вверх на послейних I А тактах

Т Вниз на первых Н тактах (всего 19 тактов)

Рис. 6

.15. Систематический кодер для (15, 11)-кода Хэмминга.

Численный остаток готов для подачи в канал в качестве проверочных символов. В течение этих последних четырех тактов работы цепь обратной связи в устройстве деления разомкнута. В общей сложности полное кодирование занимает 19 тактов.

Можно несколько ускорить кодирование,удалив первые четыре такта. Такой кодер изображен на рис. 6.16. Чтобы понять эту схему, нужно заметить, что поступающие информационные Символы не вводятся немедленно" для выполнения деления на g (х), а поступают тогда, когда необходимо сформировать сигнал обратной связи. Таким образом, обратная связьв устройстве на рис. 6.16 такова же, как и в устройстве на рис. 6.15. Далее,так как последние биты многочлена хЧ (х) всегда равны нулю, то*ни-чего не случится, если мы прибавим их к остатку от деления. Таким образом, остаток, вычисляемый устройством на рис. 6.16, равен остатку, вычисляемому устройством на рис. 6.15, но вычисление происходит только за 15 тактов, что, конечно, удобнее. 6*

Открыто на послевних I тактах

Ч1Н±>*

i(x)

Вверх на послебних I* тактах -С(Х)

Вниз на. первых \\ тактазг (всего 15 тактов)

Рис. 6.16. Другой систематический кодер для (15, 11)-кода Хэмминга.

Теперь обратимся к декодеру. В канал поступают коэффициенты многочлена с (х). К ним прибавляется многочлен ошибок е (х). На выходе канала принимается многочлен

V (х) = с (х) + е (х).

В § 5.2 была описана очень простая по идее процедура декодирования, основанная на просмотре таблицы. Принятая последовательность делится на g (х), и остаток от деления полагается равным синдромному многочлену. Синдромный многочлен используется для выбоза из таблицы оценки для многочлена ошибки. В двоичном случае синдром можно использовать непосредственно как адрес хранящейся в таблице оценки вектора ошибок е (х).

На рис. 6.17 изображен декодер для несистематического (15, 11)-кода Хэмминга. Для этого кода синдром задается 4 битами, и, следовательно, необходимо постоянное запоминающее устройство (ПЗУ), в котором записаны 15-битовые слова, четыре из которых заняты адресом. Такой подход представляется практичным для длин п -k синдромов вплоть до 12 или 14 битов, но, как

ПЗУ: 16 слов по 15 ffumoe к,аж()ое

15-gumo6biu регистр cfleuta -

-jl5-6omo6biu регистр сЭвига [.(+)н1.0-*Д. i{ce)

Рис. 6.17. Синдромный декодер для несистематического (15, 11)-кода Хэм: минга.

МЫ увидим в следующем параграфе, возможны и другие технические решения. После исправления принятого слова получаем многочлен с (х), по которому устройство деления на g (х) вычисляет информационные символы согласно правилу

i (Х) = /?gM [с (х)], и на этом работа декодера заканчивается.

6.4. ДЕКОДЕР МЕГГИТТА

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

Простейший декодер такого типа, так называемый декодер Меггитта, проверяет синдромы только для тех конфигураций ошибок, которые расположены в старших позициях. Декодирование ошибок в остальных позициях основано на циклической структуре кода и осуществляется позже. Соответственно таблица синдромов содержит только те синдромы, которые соответствуют многочленам ошибок с ненулевым коэффициентом e„ i. Если вычисленный синдром находится в этой таблице, то „ j исправляется. Затем принятое слово циклически сдвигается и повторяется процесс нахождения возможной ошибки в предшествующей по старшинству позиции (е„ 2 ф 0). Этот процесс повторяется последовательно для каждой компоненты; каждая компонента проверяется на наличие ошибки, и если ошибка найдена, то она исправляется.

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

Теорема 6.4.1 (Меггитт), Предположим, что g (х) h (х) =

х« - I и

Тогда

Rg м [xv (х) (mod X" - 1)] = Rg м [xs (х)].