Файл: Основы технической эксплуатации ЭЦВМ..pdf

ся без остатка двучлен Д + і при минимальном 'положи­ тельном І ^ п г + г.

Для доказательства того, что такой циклический код действительно обнаруживает все одиночные и двойные ошибки, рассмотрим многочлен ошибок Е ( х ) . Пусть при передаче кодовой комбинации возникли ошибки в і-м и j-н разрядах. Тогда Е ( х ) = х 1+ хк

Обязательным условием обнаружения ошибок явля­ ется невозможность деления полученного многочлена

ше одного члена, то все одиночные ошибки также будут обнаружены.

Для обнаружения всех одиночных, двойных и трой­ ных ошибок используют циклический код с многочленом

При применении циклического кода в качестве кор­ ректирующего для определения номера разряда, в кото­ ром знак принят е ошибкой, проводится анализ остатка, получившегося после деления принятой кодовой комби­ нации на многочлен Р(х).

Из (3-8) следует, что для формирования циклическо­ го кода необходимо многочлен G(x), соответствующий информационной кодовой комбинации, умножить на хт,

119

затем 'Полученное произведение разделить на Р(х) И остаток от деления G(x)xr на Р(х) сложить по модулю 2 с произведением G(x)xr.

Умножение G(x) на хг соответствует сдвигу информа­ ционной кодовой комбинации на г разрядов (в сторону старших разрядов). Операцию деления на основании рас­ смотренного выше примера деления многочленов, коэф­ фициенты которых являются нулем или единицей, молено свести к последовательному суммированию по модулю 2

Рис. 3-9. Структурная схема кодирующего устройства (в цикли­ ческом коде) для многочлена Р(х) = х ' + х + 1.

делителя со старшими разрядами делимого, а затем с оче­ редными суммами. Суммирование производится до тех пор, пока очередная сумма не будет иметь порядок ни­ же порядка делителя.

Описанная схема формирования циклического кода может быть реализована с помощью регистра с обрат­ ными связями, представляющего собой сдвигающий ре­ гистр и ряд сумматоров по модулю 2. Количество раз­ рядов сдвигающего регистра выбирается равным степени многочлена Р(х). Сумматоры в количестве, на единицу меньшем числа ненулевых членов многочлена Р{х), вклю­ чаются на входы тех разрядов регистра (начиная с ■младшего), которым соответствуют ненулевые члены многочлена Р(х).

На рис. 3-9 показана структурная схема устройства кодирования в циклическом коде для многочлена Р(х) = = х і +х+-1. Для простоты пояснения клапаны Кі и /<2 по­ казаны в виде обыкновенных выключателя и переключа­ теля. Схема работает следующим образом. К моменту начала кодирования ключ Кг находится в положении 1, а ключ Кі—в положении включено. Последовательность импульсов обыкновенного кода G(x) поступает, начинал со старшего разряда, одновременно в канал передачи и

120

на вход сумматора 1. Первые г сдвигов соответствуют умножению многочлена G(x) на' хт. За m + r тактов в схеме сдвигающего регистра с обратными связями на­ капливается г контрольных разрядов, являющихся остат­

выключено, а ключ Кг на (т + г+ 1 )-м такте устанавли­ вается'в положение 2. За последующие г тактов с выхода старшего разряда регистра в канал передачи последова­ тельно поступят г контрольных разрядов. В результате описанной процедуры будет сформирован циклический код, соответствующий многочлену F(x).

Проиллюстрируем работу схемы на примере кодиро­ вания двоичного числа 101011001. В табл. 3-5 во втором вертикальном столбце показано потактовое поступление информации на вход сдвигающего регистра с обратными связями, а в третьем, четвертом, пятом и шестом — опе­ рации вычитания (сложения по модулю 2), происходя­ щие в регистре в процессе проведения деления.

Сравнивая циклический код, полученный для числа 101011001 в кодирующем устройстве, с многочленом 3-9, образованным путем последовательного деления много­ члена G(x)xr— xiZ+ x i0+x8+x1+x!i на Р(х) — хі + х + 1, можно сказать, что в обоих случаях получены идентич­ ные результаты.

Структурная схема (рис. 3-10), предназначенная для декодирования циклического кода с целью обнаружения и .исправления ошибок, состоит из приемного, информа­ ционного и декодирующего регистров и дешифратора коррекции одиночной ошибки. Декодирующий регистр представляет собой точно такой же сдвиговый регистр с обратными связями, который применяется в кодиру­ ющем устройстве. Это объясняется тем, что при кодиро­ вании и декодировании выполняются аналогичные опе­ рации деления многочлена G(x)xr на Р(х) в первом случае и Н(х) или Р(х) на Р(х) во втором.

На структурной схеме изображен сдвиговый регистр для многочлена Р ( х ) — х'1+ х + 1.

Работа схемы происходит следующим образом. Цик­ лический код поступает, начиная со старшего разряда, одновременно на входы приемного и декодирующего ре­ гистров. Спустя m+ r тактов приемный регистр оказыва­ ется полностью заполненным принятой кодовой комбина­ цией, За эти же m + r тактов в схеме декодирующего

. 1?!

123

X О X О

C°L ЯI

*8

вінві douoH

123