Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
В задачу декодирования входит исправление и обнаружение ошибок, и эта процедура много более сложная, чем кодирование. Но устройства, подобные рассмотренным «мини-ЭВМ», позволяют решить и эту задачу. В отличие от кодеров, которые выглядят более или менее стандартно для всех циклических кодов, декодирующие устройства (или декодеры) отличаются большим разнообразием, и то как они устроены, зависит и от типа кода, и в особенности, от способа декодирования.
Кроме синдромного декодирования, о котором мы рассказывали в § 12, существуют еще ряд других методов, так или иначе связанных с вычислением синдрома. Для любого из них принципиальная схема декодера выглядит так, как показано на рис. 20,
Наиболее сложной частью такого декодера является комбинационная логическая схема, которая по вычисленному синдрому находит положение ошибочных символов,
Помученное
O
Устройство для вычисления синдрома
Комёитционная логическая
Запокцкаюшее устройство на п символов
ф
Исправленное слово
Рис. 20.
Устройство этой логической схемы целиком определяется алгоритмом декодирования, а многообразием логических схем в свою очередь определяется большое разнообразие декодеров. Сложность практической реализации декодера всецело зависит от характера логической схемы. Комбинационная схема исключительно проста, как мы увидим, в случае декодеров, только обнаруживающих ошибки или исправляющих лишь одиночные ошибки, но существенно
,88сложнее для декодеров, исправляющих кратные ошибки. В следующих двух параграфах мы познакомимся с методами так называемого мажоритарного декодирования, которые позволяют значительно упростить комбинационную логическую схему.
Что же касается устройств для вычисления синдрома, то здесь особой проблемы нет: они реализуются по тому же принципу, что и кодеры циклических кодов. Для этой цели, оказывается, могут быть использованы схемы деления многочленов.
Чтобы убедиться в этом, рассмотрим матрицу Н, по столбцам которой стоят коэффициенты остатков г-(х) отделения многочленов Xі (i=0, 1, . . ., п—1) на порождающий многочлен g(x). Запишем ее условно в виде:
H = (/•„ (х), тх {X), ґ2 (*)...../¦„_( (X)).
Можно показать, что матрица H является проверочной для рассматриваемого кода (см. дополнение 2 к этому параграфу).
Если и=(н0, Uu • . и„-г) — принятый вектор, то его синдром иНт будет равен
"«/о (*) + uS1 (*)+••• + мя_іг„_і (X)• (3)
Выражение (3) совпадает с остатком от деления многочлена
U(x) = Ug + U1X + ... +U^1X"-1 на порождающий многочлен g(x). Таким образом, любая схема деления, вычисляющая остаток,— например, схема, представленная на рис. 19,— может быть использована как составная часть декодера для получения синдрома.
Рис, 21.
На рис. 21 приведена схема декодера, предназначенного только для обнаружения ошибок.
Полученное слово одновременно вводится в запоминающее устройство и в схему деления. К моменту заполнения
,89запоминающего устройства в ячейках схемы деления будет получен остаток от деления на g(x), который равен синдрому. Если синдром равен нулю, то слово передается адресату, в противном случае прием прекращается и передающей стороне посылается запрос на повторную передачу.
Не намного сложнее схема декодера для кодов Хемминга, исправляющих одиночные ошибки. В качестве примера рассмотрим декодер для (7,4)-кода с порождающим многочленом I+*2+*3. Его схема представлена на рис. 22. Она
включает в себя наряду со схемой деления и запоминающим устройством также и логическую схему. Последняя устроена так, что на ее выходе появляется 1, только если на вход из ячеек памяти подается комбинация 011, равная последнему столбцу проверочной матрицы
(которая построена указанным выше способом из остатков от деления многочленов Xі на пооождающий многочлен
1 +X24- Xs).
Предположим теперь для примера, что ошибка в слове и0 Ui U2 U3 Ui W5 Ue произошла в символе U3 — четвертом по порядку. Как мы знаем, синдром в этом случае будет совпадать с четвертым столбцом матрицы Н, т. е. будет равен вектору (1 0 1). Следовательно, после семи тактов работы в запоминающем устройстве окажется слово U0 U1U2 U3 Ui иъ ws, а в трех последовательных ячейках схемы деления —г- комбинация 10 1. На восьмом такте из запоминающего устройства на исправляющий сумматор поступит символ и„, на вход логической схемы сдвинется комбинация'
Исправляющий сумматор
Подушное мово
Рис. 22,
/10 0 1110 //=01001 1 1 40 0 111O1
,901 О 1, на ее выходе окажется 0, и символ и„ без изменений поступит на выход всей схемы. При этом, как нетрудно проверить, в ячейках схемы деления окажется комбинация 1 1 1 (на вход всей схемы, начиная с восьмого такта поступают нули). В следующих трех тактах из запоминающего устройства будут последовательно поступать символы иь, Ui, us, на вход логической схемы — комбинации 111, 110, 011, а на ее выходе получатся поочередно 0, 0 и 1. Поэтому символы us и Ui поступят на выход неисправленными, а ошибочный символ U3 исправится. Проследив дальнейшие три такта, можно убедиться, что символы и2, Ui и U0 исправляться не будут. В результате на выходе схемы окажется слово, в котором будет исправлен только ошибочный символ U3.