УСТРОЙСТВО для ДЕКОДИРОВАНИЯ ЦИКЛИЧЕСКИХ КОДОВ, ИСПРАВЛЯЮЩИХ МНОГОКРАТНЫЕ ПАЧКИ ОШИБОК Советский патент 1967 года по МПК H03M13/15 

Известны устройства для декодирования циклических кодов, иснравляющих многократные начки ошибок, содержащие регистры, охваченные цепями обратной связи, и логические схемы. Предлагаемое устройство отличается от известных тем, что оно содержит пороговое устройство на двух счетчиках, первый вход которого через клапан подсоединен к выходу входного регистра сдвига, второй вход через второй клапап соединен с выходом кодирующего устройства, выходы порогового устройства нодключеиы соответственно к устройству управления и выходному регистру, вход кодирующего регистра подсоединен к выходу входного регистра через два клапана, подключенных к устройству унравления, и к своему выходу через диод и клапан. Это позволяет упростить устройство. На чертеже изображена схема нредлагаемого устройства. Оно содержит входной регистр 1 сдвига, замкнутый при помощи обратной связи в кольцо (этот регистр представляет собой лннию задержки из п элементов, где последний элемент связан с первым); регистр 2 сдвига с линейными обратными связямн, так называемый кодирующий (п, т) регистр; выходной регистр 3, собранный по аналогичной с входным регистром схеме; пороговое устройство 4; устройство 5 унравлення клапанами. Входной регистр 1 сдвига может быть собран из нолупроводниковых триггерных ячеек. Его вход является входом декодирующего устройства. Кодирующий регистр 2 также может быть собран из полупроводниковых триггерных ячеек. Здесь gi (t 0,..., п-/п) означает наличие нли отсутствие цепей обратных связей в зависимости от значения коэффициентов порождающего код многочлена g(-X) gtt- -glX++Яя-,«Л;л-т При этом gf - I соответствует налнчию связи, а gj 0 - ее отсутствию. Выход входного регистра / через клапан 6 соединен со входом норогового устройства 4, а также через клананы 6 и 7 подключен ко входу кодирующего регистра 2 и через клананы 5 и 7 и диод 8 - к выходу кодирующего регистра 2. Выход последнего осуществлен через клапан 9 (клапаны могут быть выполнены на полупроводниковых триггерах). Вход выходного регистра 3 подключен к выходу кодирующего регистра 2, а выход через клапан W является выходом устройства. Пороговое устройство 4 имеет два входа и два выхода. Один вход порогового устройства через клапан 6 подключен к выходу входного регистра 1, а другой - через клапан 9 к выходу коднрующего регистра 2. Пороговое ycTpoikTBo 4 выходом // подключено к разрядам выходного регистра 3. Устройство 5 управления клапанами представляет собой обычное программное устройство, основанное на распределении импульсов. Оно может быть осуществлено, например, на транзисторных или феррит-диодных распределителях импульсов (в нашем случае необходимо два распределителя из я+1 ячеек). Выходы устройства управления подключены к управляющим входам клапанов, а вход соединен с выходом порогового устройства 4. Пусть в результате передачи по каналу сигналаа К, ..., ), в приемник поступил искаженный сигнал а(ао, ..., ). Сигнал записывается во входной регистр. Запись происходит последовательно, начиная с символа «о, т. е. символ ао помещается в последиий (на чертеже первый справа) разряд входного регистра йь в предпоследний разряд и т. д. После этого во входном регистре происходит сдвиг сигнала а, в результате которого символ un-i из первого разряда переходит во второй, символ из второго разряда - в третий и т. д.; символ ао по обратной связи переходит в первый разряд и одновременно поступает на выход входного регистра. Такой сдвиг в дальнейщем будем называть тактом работы регистра; при этом начало тактов определяется тактовыми импульсами, поступающими из блока питания. Во второй такт осуществляется переход--символа йо из первого .разряда во второй, символ а , из второго в .третий и т. д., символа ai из последнего в первый; при этом символ ui параллельно поступает на выход входного регистра. За вторым тактом последует третий и т. д. Ра-бота входного регистра в целом заключается в последовательном (циклическом) сдвиге сигнала а с одновременной генерацией символов его на выходе. Первые n-f 1 тактов работы входною регистра составляют первый цикл, в течение которого из входного регистра в остальные узлы устройства декодирования символы поступают следующим образом. В первом такте символ «о через клапаны 6 и 7 вводится в кодирующий регистр и но линейным обратным связям записывается в его разряды. Одновременно символ «о через вход 12 вводится в пороговое устройство, а также через клапан 9 - в первый разряд выходного регистра 3. Во втором такте ai символ записывается в кодирующий регистр, пороговое устройство и выходной регистр сдвига и т. д. Работа выходного регистра аналогична работе входного регистра. Поэтому в момент поступления символа на его вход символы, находящиеся в регистре, сдвигаются на один разряд. Например, во втором цикле при посимвол ао, находящийся в выходном регистре, переходит во второй разряд, а в первый разряд записывается символ а. Для кланаиов установлен следующий режим работы, заложенный в устройстве управления. Кланан 6 открыт в течение п тактов и закрыт на (п+1)-н такт. Клапаны 7 и 13 открыты в течение первых тактов и закрыты в последующий период. Для клапа,на 9 выбран режим работы, обратный клапанам 7 и 13. Поэтому в течение тактов первого цикла первые m компонентов сигнала а, т. е. символы а„, ..., записываются в кодирующий и выходной регистры. За последующие п-т тактов из кодирующего регистра в выходной регистр записываются еще п-т символов. Обозначим через ф(а) последовательность, записанную в выходном регистре; ф(й) есть сигнал, первые т компонентов которого совпадают с соответствующими компопентами сигнала а, а последующие л-/п компонентов определены из первых согласно рекуррентному соотношению кода. Иначе говоря, ф(а) есть сигнал, закодированный по а, ..., информационным символам. Очевидно, что есл;-) среди первых символов нет искаженных, то сигнал ф(а) есть истинный кодовый сигнал, соответствующий переданному. В течение нервого цикла на вход 14 порогового устройства поступает сигнал ф(а), а на вход 12 - сигнал а. Сигналы, поступившие на входы порогового устройства суммируются в сумматоре но модулю два и их сумма + fp(a) (XQ, ..., Xn-i ) вводится в пороговое устройство. Работа порогового устройства математически может быть представлена следующим образом: либо (х) t г (на выходе 11 выдается сигнал воздействия), либо (x).r (на выходе }1 нет сигнала, есть сигнал на выходе 14). При этом (x),(, t) есть кратность пачек ошибок длиной tb последовательности х; й(р, /) определяется из соотиошения d (,0 1 м 2 2 -ъ-(1) 1 где ,,,2, . . 4C,f) Допустим теперь, что в сигнале а (ао, ..., un-i) количество пачек ошибок длиной - t не превосходит заданную кратность г (г - максимальное число исправляемых кодом ошибок). Тогда для любого принятого сигнала может иметь место одно из двух соотношений: либо ((2)

разрядов). Здесь х (Х;, лмл. . ., Хп-г,

Хд . . . , л (-:).

Таким образом, в течение первого цикла работы устройства могут иметь место два случая.

1.Первые т символов сигнала а не искажены. В этом случае/а ® ф(а)/(; г. Поэтому в конце первого цикла от порогового устройства на устройство управления клапанами поступит сигнал воздействия. Устройство управления откроет клапан 10 и выходной регист, в котором записан истинный сигнал а ф(а), выдает его на выходе через последующие /. тактов.

2.Среди первых символов сигнала а имеются искаженные. В этом случае /аШф(а), поэтому пороговое устройство выдает сигналы на стирание информации в выходном регистре, клапан 6 остается закрытым, и начинается второй цикл декодирования.

В течение первых т тактов второго цикла через клапаны 6 и 7 в кодирующий и выходиой регистры поступают символы «i, ..., а.

За последующие п-т тактов из кодирующего регистра в выходной записываются еще п-m символов, и в выходном регистре получается последовательность (р(а). В течение второго цикла на входы порогового устройства поступают: на вход 12 сигнал ai(ai, ..., , йо), а на вход 14 сигнал ф(а1).

Как и в первом цикле, в зависимости от того, какое из условий удовлетворяется - (2) или (3), либо на выходе выходного устройства получается истинный рабочий сигнал, либо процесс декодирования, аналогичный первым двум циклам, продолжается до тех пор, пока, начииая с некоторого символа ау среди т символов, записываемых в кодирующий регистр, не будет ни одного искаженного (О ).

Таким образом, задача декодирующего устройсгва заключается в отыскании в принятом на приемной стороне сигнале таких т подряд идущих а, , ..., a(.i.,n-i символов, которые не содержат ошибочных компонент (так как при этом а ф(а ), и истинный сигнал а получается сдвигом a на п - г + 1 тактов.

Это достигается тем, что устройство управлеиия задерживает открытие клапана 10 на п-i+l тактов, где i количество циклов.

Указанная задача разрешима для любого принятого рабочего сигнала, не нретерпевшего более чем г пачек искажений, если код удовлетворяет условию - ... (4). Здесь нег

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

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

Пример. Рассмотрим двоичный циклический (15,9) код, исправляющий все одиночные пакеты ошибок длиной - 3.

Порождающий многочлен данного кода

имеет вид §(х + к+х- + .

Допустим, что в результате передачи по каналу связи сигнала « 100000000100111 был искажен помехой е 111 00000 000000, тогда декодированию подлежит сигнал а а@е

100000000100111 е пюооооооооооо : 011000 000101 по.

Декодирующее устройство работает следующим образом. В течение т тактов первого цикла первые т 9 символов сигнала а, т. е. 011000000, записываются в кодирующий и выходной регистры. Эта же последовательность поступает и на вход 14 порогового устройства. За последующие п-иг 6 тактов из кодирующего регистра на вход 14 и в выходной регистр поступают еще 6 символов, а именно 101110. В течение первого цикла ( тактов) на вход 14 порогового устройства подается последовательность.

Ф(а) 011000000100111. Эта же последовательность записывается в выходной регистр.

С другой стороны на вход 12 порогового устройства поступает сигнал а 011000000101 ПО.

Таким образом, в течение первого цикла в пороговое устройство вводится последовательность:

аЭ с (а) : 011 000000 100 111 е © 011 000 000 101 110 000 000 000 011 001,

в которой кратность пачек длиной 3 больше г, т. е. (000 000 000 110 001)„з .

Значит первые 7П 9 символов сигнала а с искажеииями. Поэтому в конце тактов пороговое устройство выдает импульс на стирание сигнала в выходном регистре, и устройство своим вторым циклом ПрОДОЛЛчПТ

поиск безошибочного т-разрядного иитервала.

В течение первых т тактов второго цикла в кодирующий и выходной регистры запишутся нервые т символов сигнала ai -(110000001001110), п процесс, аналогичный первому цнклу, продлится до тех пор, пока /п-разрядный безошибочный интервал не Судет обнаружен и в выходной регистр не запишется неи:ка;кеиный сигнал. В данном случае это произойдет в четвертом цикле декодирования, так как

/а @ -i ()/,.-з (000 000 100 111 011 © ©000000 100111

(000 000 000 000 11 l) 1 г

Тогда в выходной регистр запишется истинный сигнал ф(а)аз 000000100111100, сдвинутый на три позиции. После соответствуюпдего сдвига fls на 12 нозицнй истинный сигнал 0 100000000100111 постуннт и а выход декодируюш,его устройства.

Предмет изобретения

Устройство для декодирования циклических кодов, исправляющих многократные пачки

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