16. КОДИРУЕТ И ДЕКОДИРУЕТ ЭВМ
Заголовок этого параграфа не следует понимать буквально. Вряд ли было бы целесообразно привлекать универсальные ЭВМ для кодирования и декодирования с помощью линейных и циклических кодов. Однако устройства или схемы, предназначенные для этих целей, состоят из тех же элементов, что и любая ЭВМ, так что такие схемы, если угодно, можно рассматривать как специализированные мини-ЭВМ. В случае двоичных кодов применяются элементы двух основных типов:
Ячейка памяти (или триггер), которая может находиться в двух состояниях: одно из них соответствует символу 0, другое — символу 1. Ячейка памяти имеет один вход и один выход.
Двоичный сумматор, осуществляющий сложение по модулю 2. Сумматор имеет два входа и один выход.
и оценки (1)
Отсюда получаем:
Устройства, составленные из этих элементов, позволяют легко перемножать и делить двоичные многочлены, а это как раз те операции, которые приходится выполнять при использовании циклических кодов.
В качестве первого примера рассмотрим схему» осуществляющую умножение произвольного двоичного многочлена [(X) на многочлен 1 + Х24-Эта схема представлена на рис. 14 и состоит всего из трех ячеек памяти и двух сумматоров. Поясним принцип ее работы.
Первоначально все ячейки памяти содержат нули, а на вход поступают коэффициенты многочлена начиная с коэффициентов при старших степенях. Коэффициент ап без изменений передается на выход и запоминается в первой ячейке памяти (рис. 15, а) В следующем такте работы (рис. 15, б) в первую ячейку памяти попадет коэффициент а коэффициент апдвигается в следующую ячейку памяти. При этом на ?,ходах первого сумматора окажутся значения а„ н ап_и а на выходе — их сумма по модулю 2.
В третьем такте (рис. 15, в) произойдет дальнейший сдвиг коэффициентов в ячейках памяти, а на выходе первого сумматора и всей схемы появится сумма ап_2-\ ап_1.
На рис. 15, г показано состояние схемы на г'-м такте, когда на вход подан коэффициент
Эта последовательность соответствует многочлену
Непосредственно проверяется, что этот многочлен как и есть нужное нам произведение
Аналогично устроена схема умножения на произвольный многочлен
Последние три такта отражены на рис. 15, д—ж. Итак, на выходе схемы появится следующая последовательность из п- 3 коэффициентов:
«запоминают», но и «сдвигают» поступающие в них коэффициенты (играют роль сдвигающего регистра). Сумматоры осуществляют сложение по правилам сложения в поле Р,Кроме того, в схему сведены добавочные устройства, производящие умножение на элемент € Р (на рис. 16 эти устройства показаны кружками, помеченными соответствующими множителями). В двоичном случае особых устройств для этого не требуется: если ^> — 1, то в соответствующем месте схемы имеется «вертикальное» соединение и двоичный сумматор, в противном случае они отсутствуют.
Столь же просты схемы деления многочлена на многочлен с остатком. Вот, например, как устроена схема деления на многочлен 1-\-Х2+Ха (рис. 17).
На вход поступают коэффициенты делимого, начиная со старших степеней, на выходе последовательно появляются коэффициенты частного. После окончания деления в ячейках памяти слева направо оказываются записанными коэффициенты остатка, начиная с младших степеней. Проследим последовательность работы схемы при делении на Х3+ + Х5+1 многочлена Х6+Х4+Х3+А:+1. Деление углом
(рамочками выделены последовательные частичные остатки).
В первые три такта работы схемы старшие коэффициенты делимого сдвигаются по ячейкам памяти. При этом старший коэффициент (при X6) окажется в крайней правой ячейке (рис. 18, а). Все это Бремя на «нижних» входах
сумматоров сохраняются нулевые элементы, не влияющие на работу схемы. В следующем такте (рис. 18, б) старший коэффициент сдвигается на выход схемы, одновременно попадая на нижние входы сумматоров. На вход схемы поступает нулевой коэффициент при X2. В первую ячейку записывается выход первого сумматора, равный 1+0=1, вс
вторую — содержимое первой ячеики в предыдущем такте (т. е. I), а в третью — выход второго сумматора, равный 1 + 1=0. В итоге в ячейках памяти сдвигающего регистра оказываются записанными коэффициенты первого из обведенных рамочкой остатков.
На рис. 18, е показано состояние схемы после еще одного такта ее работы. Теперь уже содержимое ячеек — коэффициенты второго из заключенных в рамочку остатков.
Еще один такт работы схемы переводит ее в конечное состояние (рис. 18, г). В ячейках памяти получены коэффициенты остатка, а последовательность символов 1, 0, 1 на выходе — это коэффициенты частного.
Приведем без комментариев схему, осуществляющую деление с остатком на произвольный многочлен д(Х) (рис. 19), предоставляя читателю самому разобраться в принципе ее действия.
где С — порождающая матрица линейного кода.
Схемы умножения и деления многочленов, рассмотренные нами,— это, по существу, уже готовые кодирующие устройства (или, как их называют, кодеры) для циклических кодов. В самом деле, вспомним правило кодирования линейным (п, й)-кодом. Если Л=ас. . — произвольное сообщение длины к. то ему сопоставляется кодовый вектор
Разумеется, правило остается в силе и для любого циклического кода, но на языке многочленов ему можно придать теперь иную, гораздо более удобную форму.
— многочлен, соответствующий сообщению А, то равенство (1) перейдет в равенство многочленов
где д(х) — порождающим многочлен циклического кода.
Если а(х) — многочлен, соответствующий вектору а, и
Для того чтобы убедиться в этом, достаточно подставить в (I) матрицу С из формулы (9) § II и проверить, что координаты получающегося вектора служат коэффициентами многочлена А (х)д(х).
Итак, операция кодирования сводится к умножению многочленов. При этом можно считать, что речь идет об обычном умножении многочленов, поскольку степень равна т, а степень А(х) меньше п—т, так что сумма степеней этих многочленов меньше п. Но схемы, которые мы здесь рассмотрели (рис. 14 и 16), как раз и вычисляют обычное произведение многочленов. Первая из них может служить кодером для циклического (7,4)-кода с порождающим многочленом х3+х?+1, а вторая — для произвольного циклического кода с порождающим многочленом Если на вход последней поступают информационные символы а0, «1,. . ., а„_! (коэффициенты многочлена А(х)), то на выходе согласно (2) будем иметь коэффициенты кодового многочлена а(х).
На основе схем деления чрезвычайно удобно строить кодеры для систематических циклических кодов, в которых информационные символы отделены от проверочных (см. дополнение 4 к этому параграфу).
Даже наше беглое знакомство с устройствами кодирования показывает, что все они имеют унифицированную струк-туру. Как видно из рис. 16, путем определенных видоизменений схемы, предназначенной для одного кода, можно получить схему кодирования для другого кода. Поэтому в ряде случаев целесообразно использовать не конкретные схемы для каждого кода, а достаточно разветвленное устройство з большим набором стандартных элементов, работу которого можно было бы перестраивать, вводя в него ту или иную программу. Такое устройство, в сущности, и есть специализированная мини-ЭВМ с программным управлением.
В задачу декодирования входит исправление и обнаружение ошибок, и эта процедура много более сложная, чем кодирование. Но устройства, подобные рассмотренным «мини-ЭВМ», позволяют решить и эту задачу. В отличие от кодеров, которые выглядят более или менее стандартно для всех циклических кодов, декодирующие устройства (или декодеры) отличаются большим разнообразием, и то как они устроены, зависит и от типа кода, и в особенности, от способа декодирования.
Кроме синдромного декодирования, о котором мы рассказывали в § 12, существуют еще ряд других методов, так или иначе связанных с вычислением синдрома. Для любого из них принципиальная схема декодера выглядит так, как показано на рис. 20.
Наиболее сложной частью такого декодера является комбинационная логическая схема, которая по вычисленному синдрому находит положение ошибочных символов,
Устройство этой логической схемы целиком определяется алгоритмом декодирования, а многообразием логических схем в свою очередь определяется большое разнообразие декодеров. Сложность практической реализации декодера всецело зависит от характера логической схемы. Комбинационная схема исключительно проста, как мы увидим, в случае декодеров, только обнаруживающих ошибки или исправляющих лишь одиночные ошибки, но существенно сложнее для декодеров, исправляющих кратные ошибки. В следующих двух параграфах мы познакомимся с методами так называемого мажоритарного декодирования, которые позволяют значительно упростить комбинационную логическую схему.
Что же касается устройств для вычисления синдрома, то здесь особой проблемы нет: они реализуются по тому же принципу, что и кодеры циклических кодов. Для этой цели, оказывается, могут быть использованы схемы деления многочленов.
Чтобы убедиться в этом, рассмотрим матрицу Н, по столбцам которой стоят коэффициенты остатков отделения многочленов х' (1=0, 1 п—1) на порождающий многочлен р(х). Запишем ее условно в виле:
Можно показать, что матрица И является проверочной для рассматриваемого кода (см. дополнение 2 к этому параграфу).
Выражение (3) совпадает с остатком от деления многочлена
Если и=(ив, «1, . . ., ип_г) — принятый вектор, то его синдром иНт будет равен
на порождающий многочлен ^(х). Таким образом, любая схема деления, вычисляющая остаток,— например, схема, представленная на рис. 19,— может быть использована как составная часть декодера для получения синдрома.
На рис. 21 приведена схема декодера, предназначенного только для обнаружения ошибок.
Полученное слово одновременно вводится в запоминающее устройство и в схему деления. К моменту заполнениязапоминающего устройства в ячейках схемы деления оудет получен остаток от деления на д(х), который равен синдрому. Если синдром равен нулю, то слово передается адресату, в противном случае прием прекращается и передающей стороне посылается запрос на повторную передачу.
Не намного сложнее схема декодера для кодов Хемминга, исправляющих одиночные ошибки. В качестве примера рассмотрим декодер для (7,4)-кода с порождающим многочленом 1+л:2+л:3. Его схема представлена на рис. 22. Она включает в себя наряду со схемой деления и запоминающим устройством также и логическую схему. Последняя устроена так, что на ее выходе появляется 1, только если на вход из ячеек памяти подается комбинация ОН, равная последнему столбцу провепочной матоины (которая построена указанным выше способом из остатков от деления многочленов х1 на порождающий многочлен 1+^+х8).
Предположим теперь для примера, что ошибка в слове «о «1 и2 иа «4 щ ив произошла в символе и3 — четвертом по порядку. Как мы знаем, синдром в этом случае будет совпадать с четвертым столбцом матрицы Н, т. е. будет равен вектору (I 0 1). Следовательно, после семи тактов работы в запоминающем устройстве окажется слово иа иг и2 ия и4 иъ ив, а в трех последовательных ячейках схемы деления — комбинация 1 0 1. На восьмом такте из запоминающего устройства на исправляющий сумматор поступит символ ив, на вход логической схемы сдвинется комбинация 1 О 1, на ее выходе окажется 0, и символ и(. без изменений поступит на выход всей схемы. При этом, как нетрудно проверить, в ячейках схемы деления окажется комбина ция 1 1 1 (на вход всей схемы, начиная с восьмого такта поступают нули). В следующих трех тактах из запоминающего устройства будут последовательно поступать символы иь, и3, на вход логической схемы — комбинации 111, 110, 011, а на ее выходе получатся поочередно 0, 0 и 1. Поэтому символы иь и щ поступят на выход неисправленными, а ошибочный символ и3 исправится. Проследив дальнейшие три такта, можно убедиться, что символы и^ и и0 исправляться не будут. В результате на выходе схемы окажется слово, в котором будет исправлен только ошибочный символ и3.
Совершенно аналогично происходит исправление ошибки в любой другой позиции.
Задачи и дополнения
1. Построить кодеры для двоичных циклических кодов плины 15 г попожпяюшими многочленами
2. Всякий циклический (п, к)-код с порождающим многочленом д(х) можно представить в систематической форме следующим образом. Пусть л,- (л.) — остаток от деления х' на порождающий многочлен д (л), т.е
Рассмотрим многочлены
при 1—т, /71+1, . . ., п—1, где т=п—к — степень порождающего многочлена %(х). Все эти многочлены кодовые, так как они кратны Кодовый вектор, соответствующий многочлену х'—г,- (х), имеет вид:
где г;0, гг-и ш—\— коэффициенты остатка г,-(х), а символ 1 стоит в позиции с номером I.
Мы получили п—т—к векторов, которые, как нетрудно видеть, линейно независимы. Если составить матрицу О, строками которой являются указанные векторы, то она и будет порождающей (ее строки образуют базис кодового подпространства). Если через Я обозначить матрицу, строками которой являются коэффициенты многочленов г;(х), то матрица О получается приписыванием к матрице — К справа единичной матрицы Ек порядка к и ее можно условно записать в виде:
Отсюда легко следует (ср. § 11, задача 10), что в качестве проверочной можно взять матрицу
По столбцам матрицы Н стоят коэффициенты остатков от деления мно
гой лено!
на ё(х).
рассмотрим снова (7,4)-код с порождающим многочленом Имеем:
3. Чтобы ппоиллюстпиоовать метод, изложенный в дополнении 2,
Строками порождающей матрицы являются, следовательно, коэфф»' ш- енты многочленов:
Таким образом,
4. Метод, рассмотренный в дополнении 2, можно использовать для построения кодера систематического циклического кода.
При кодировании с помощью матрицы (4) кодовое слово получается умножением информационного слова на эту матрицу (см. (6), § 11). В этом случае последние к символов ат, ат + 1, . . ., ап-1 кодового слова совпадают с информационными символами, а все кодовое слово является линейной комбинацией строк порождающей матрицы (4) с коэффициентами а,„, сга + {, . . ., ап_,. Учитывая, что построкам матрицы стоят коэффициенты остатков от деления многочленов х1 на порождающий многочлен мы убеждаемся, что величины о0, аг ат-х
являются коэффициентами остатка от деления многочлена на многочлен §(х) (в случае двоичных многочленов знак минус перед скобкой можно опустить).
Следовательно, схемы деления могут быть использованы для нахождения проверочных символов кодовых слов циклического кода в систематической форме и, в конечном итоге, для построения его кодера, на рис. А6 приведена схема кодера двоичного (7, 4)-кода с порождающим многочленом !+*■+*», основанная на указанном принципе,Проследим вкратце работу этой схегы в течение семи тактов. Пс вые четыре такта переключатели схемы находятся в положении следующие три — в положении В. В первые четыре такта информацио, ные символы поступают (без изменений) на выход всей схемы и на выхе ( схемы деления. В течение этих четырех тактов в последовательных ячейках схемы деления получаются к эффициенты остатка а0, аг, о2 от деления многочлена аедсе+с5л:6+с4л:4+а3л-3 на порождающий многс мен 1+;г+л:3, т. е. проверочные символы (в схеме на рис. 18 на это ушло бы семь тактов, но в данной схеме три такта «экономятся», так как последовательность коэффициентов сц, аъ, с,, а3 подается не на вход, а сразу на выход схемы деления). В последующие три такта проверочные символы — сначала а2, затем щ, затем а0— поступают из схемы деления на выход всей схемы. Таким образом, по истечении семи тактов на выходе всей схемы получаем целиком кодовое слово.
Рекомендуем читателю проследить по тактам работу рассматриваемой схемы для случая о3= 0, с4=йв=о6= 1.