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

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

Иллюстрации

Показать все

Реферат

 

2ОО894

Сова Советских

Социалистических

Республик

Зависимое от авт. свидетельства №

Кл 43m, 14

Заявлено 05Х111.1966 (№ 1095840 26-24) с присоединением заявки №

МПК т.т 061

Приоритет

Комитет по делам изобретений и открытий при Совете Министров

СССР

УДК 681.142.07 (088.8) Опубликовано 15Л 111.1967, Бюллетень ¹ 17

Дата опубликования описания 3.Х1.1967 т

Автор изобретения

Р. П. Мегрелишвили

Институт алектроники, аитоматнки и телемеханикл АН Грузинткой-66Р-

Заявитель

УС1РОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ ЦИКЛИЧЕСКИХ

КОДОВ, ИСПРАВЛЯЮЩИХ МНОГОКРАТНЫЕ ПАЧКИ ОШИБОК

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

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

Это позволяет упростить устройство.

На чертеже изобра>кена схема предлагаемого устройства.

Оно содержит входной регистр 1 сдвига, замкнутый при помощи обратной связи в кольцо (этот регистр представляет собой линию задер>кки из и элементов, где последний элемент связан с первым); регистр 2 сдвига с линейшлми обратными связями, так называемый кодирующий (и, ит) регистр; выходной регистр 8, собранный по аналогичной с входным регистром схеме; пороговое устройство

4; устройство 5 управления клапанами.

Входной регистр 1 сдвига может быть сооран из полупроводниковых триггерных ячеек.

Его вход является входом декодирующего устройства, 5 Кодирующий регистр 2 также может быть собран из полупроводниковых триггерных ячеек.

Здесь g,. (i=0, ..., n — m) означает наличие или отсутствие цепей обратных связей в за10 висимости от значения коэффициентов порождающего код многочлена

g (с/ — Ь0 + Ото Г ° ° ° ° - ° i gn — rn n — от

i — о — i — . - - J o.

При этом g, =1 соответствует нали ппо свя15 зи, а g; =0 — ее отсутствию.

Выход входного регистра 1 через клапан б соединен со входом порогового устройства 4, а также через клапаны б и 7 подключен ко входу кодирующего регистра 2 и через кла20 паны б и 7 и диод 8 — к выходу кодирующего регистра 2. Выход последнего осуществлен через клапан 9 (клапаны могут быть выполнены на полупроводниковых триггерах).

Вход выходного регистра > подключен к вы2 ходу кодирующего регистра 2, а выход через клапан 10 является выходом устройства.

Пороговое устройство 4 имеет два входа и два выхода. Одни вход порогового устройства через клапан б подключен к выходу

ЗО входного регистра 1, а другой — через клапан 9 к выходу кодирующего регистра 2. По60

65 роговое устройство 4 выходом 11 подклю. опо к разрядам выходного регистра 8.

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

Оно может быть осуществлено, например, на транзисторных или феррит-диодных распределителях импульсов (в нашем случае необходимо два распределителя из а+1 ячеек).

Выходы устройства управления подключены к управляющим входам клапанов, а вход соединен с выходом порогового устройства 4.

Пусть в результате передачи по каналу сигнала а= (ар, ..., а, ), в приемник поступил искаженный сигнал а= (ар, ..., а, > ). Сигнал записывается во входной регистр. Запись происходит последовательно, начиная с символа а„т. е. символ ар помещается в последний (на чертеже первый справа) разряд входного регистра а, в предпоследний разряд и т. д.

После этого во входном регистре происходит сдвиг сигнала а, в результате которого символ a„ > из первого разряда переходит во второй, символ а„ z из второго разряда — в третий и т. д.; символ ар по обратной связи переходит в первый разряд и одновременно поступает на выход входного регистра. Такой сдвиг в дальнейшем будем называть тактом работы регистра; при этом начало тактов определяется тактовыми импульсами, поступающими из блока питания. Во второй такт осуществляется переход .символа ар из первого .разряда во второй, символа а >, из второго в третий и т. д., символа а из последнего в первый; при этом символ а, параллельно поступает на выход входного регистра. 3а вторым тактом последует третий и т. д. Работа входного регистра в целом заключается в последовательном (циклическом) сдвиге сигнала а с одновременной генерацией символов его на выходе.

Первые и+1 тактов работы входного регистра составляют первый цикл, в течение которого из входного регистра в осталь ые узлы устройства декодирования символы посгупают следующим образом. В первом такте символ ар через клапаны б и 7 вводится в кодирующий регистр и по линейным обратным связям записывается в его разряды. Одновременно символ ар через вход 12 вводится в пороговое устройство, а также через клапан

9 — в первый разряд выходного регистра 8.

Во втором такте а> символ записывается в кодирующий регистр, пороговое устройство и выходной регистр сдвига и т. д.

Работа выходного регистра аналогична раСоте входного регистра. Поэтому в момент поступления символа на его вход символы, находящиеся в регистре, сдвигаются на один разряд. Например, во втором цикле при поступлении символа а из входного регистра

4

cnìèoë ар, находящийся в выходном регистре, переходит во второй разряд, а в первый разряд записывается символ аь

Для клапанов установлен следующий режим работы, заложенный в устройстве управления. (лапан б открыт в течение г тактов и закрыт на (и+1)-й такт. Клапаны 7 и 18 открыты в течение первых тактов и закрыты в последующий период.

Для клапана 9 выбран режим работы, обратный клапанам 7 и 18.

Поэтому в течение тактов первого цикла первьм т, компонентов сигнала а, т. е. символы а,, ..., am > записываются в кодирующий и выходной регистры. 3а последующие и — т тактов из кодирующего регистра в выходной регистр записываются еще n — т символов.

Обозначим через ср(а) последовательность, записанную в выходном регистре; (а) есть сигнал, первые т компонентов которого совпадают с соответствующими компонентами сигнала а, а последующие n — т компонентов определены из первых согласно рекуррентному соотношению кода. Иначе говоря, ср(а) есть сигнал, закодированный по ар, ..., а„ информационным символам. Очевидно, что если среди первых символов пет искаженных, то сигнал ср(а) есть истинный кодовый сигнал, соответствующий переданному.

В течение первого цикла на вход 14 порогового устройства поступает сигнал cp (a), а на вход 12 — сигнал а.

Сигналы, поступившие на входы порогового устройства суммируются в сумматоре по модулю два и их сумма х=а+ср(а) = (хр, ..., х > ) вводится в пороговое устройство.

Работа порогового устройства математически может быть представлена следующим образом: либо (х), )r (на выходе 11 выдается сигнал воздействия), либо (х), ((на выходе 11 нет сигнала, есть сигнал на выходе 14).

Прн этом (х),=m;;in(d(P, t)) есть кратность пачек ошибок длпнои -(tb последовательности х; d(P, i) определяется из соотношения

Г

d(,",!) l

i.i= Q (>) =И где 1 -.;,.; с,." ; (8; + t (i = 1, 2,..., ..i (3, i))

Допустим теперь, что в сигнале а= (ар, ..., а, I) количество пачек ошибок длиной (t не превосходит заданную кратность r (r — максимальное число исправляемых кодом пачек ошибок). Тогда для любого принятого сигнала может иметь место одно из двух соотношений: либо

/a Г+ (а )/„. (r (2) (когда первые m разрядов не искажены), либо

/a 0 (a )/, ) r (3) (если искажение имеется среди а,,, af+m

200894

65 разрядов). Здесь х = (х,, х;,1..., х, 1, х г — 1).

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

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

2. Среди первых символов сигнала а имеются искаженные. В этом случае /а+ ср(а),) r, поэтому пороговое устройство выдает сигналы на стирание информации в выходном регистре, II IaizaH б Остается закрытым, и начинается второй цшсл декодирования.

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

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

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

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

Это достигается тем, что устройст o управления задерживает открытие клапана 10 на

n — i. + 1 тактов, где г количество циклов.

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

-0

ЗО

50 зусмого кода, которое, однако, в опредслсннг-.. . речслах нс является значительны" I.

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

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

Порождающий многочлен данного кода имеет вид g(x) =1+х+х- +хз+хб.

Допустим, что в результате передачи Ilo каналу связи сигнала а=100000000100111 был искажен помехой в=11100000000000, тогда декодированию подлежит сигнал а=аО1- в=

= 100 000 000 100 111 О 111 000 000 000 000 =

= 011000000 101 110.

Декодирующее устройство работает следующим образом. В течение In тактов первого цикла первые пг=9 символов сигнала а, т. е.

011000000, "àïèñûâàþòñÿ в кодирующий и выходной регистры. Эта же последовательность поступает и на вход 14 порогового устройства.

За последующие n — пг=б тактов из кодирующего регистра на вход 14 и в выходной регистр поступают еще 6 символов, а именно

101110. В течение первого цикла (и= — 15 такто") на вход 14 порогового устройства подается последовательность. ср(а) =011000000100111. Эта же последователь Ioсть записывается в выходной регистр.

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

Таким образом, в течение первого цикла в пороговое устройство вводится последовательность: а Q ср (u) 011 000 000 100 111 Q

С 011 000 000 101 110 = 000 000 000 011 001, в которой кратность пачек длиной (3 больше 7, т. е. (000 000 000 110 001)7=-з =2)r.

Значит первые m=9 символов сигнала а с иска 11<ениями. Поэтому В 1<онце и= 15 тактОв пороговое устройство выдаст импульс на ст1.рание сигнала в выходном регистре, н устройство своим вторым циклом продолжит поиск безîLIIèoo øoãо пг-разрядного интервала.

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

200894

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

à — г у ° (i ) ) 1

).и

) п

Составитель В. Субботин

Редактор Н. Джарагетти Текред А. А. Камышиикова Корректор М. П. Ромашова

Заказ 3077/1 Тираж 535 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва, Центр, пр. Серова, д. 4

Типографии, пр. Сапунова, 2

/a 0; (ч )/у 3 — (000000100 111011 З - 000 000 1 00 1 1 1 1 00) = 3 — (000 000 000 000 1 1 1)/=3 =- 1 — /

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

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

Ф у °,1 бз

// / //)

/7

// / ) )7/)

3 L 1 ошибок, содержащее регистры, охваченные цепямп обратной связи, и логические схемы, 07личаюш,ееся тем, что, с целью его упрощения, оно содержит пороговое устройство на двух счетчиках, первый вход которого через клапан подсоединен к выходу входного регистра сдвига, второй вход — через второй клаIIQh сосдинен с выходом кодирующего устройства, выходы порогового устройства подклю1О чены соответственно к устройству управления и выходному регистру, вход кодирующего регистра подсоединен к выходу входного регистра через два клапана, подключенных к устройству управления, и к своему выходу через

15 диод и клапан.