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.