Дешифратор циклического кода с исправлением ошибок и стираиии

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

323778

Союз Созетскиз

Сэцизлистическиз

Респеблив

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

Заявлено 29.XI.1969 (¹ 1383025/18-24) с присоединением заявки №

Приоритет

М. Кл. С 06f 11/08 комитет по делам изобретений и открытий ори Совете Министров

СССР

УДК 68! .326.77(088.8) Опубликовано 10.Х11.1971. Бюллетень № 1 за 1972

Дата опубликования описания 13.IV.1972

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

H. В. Волков и Ф. 3. Келлер

Заявитель

ДЕШИФРАТОР ЦИКЛИЧЕСКОГО КОДА С ИСПРАВЛЕНИЕМ

ОШИБОК И СТИРАНИИ

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

Известны дешифраторы циклического кода с исправлением ошибок типа переходов «1» в

«О» или «О» в «1» в отдельных разрядах передаваемого слова. Однако нередко в каналах связи наблюдаются переходы типа «1» в «Х» или «О» в «Х» («Х» — «стертый», неопознанный символ).

Целью изобретения является:повышение помехоустойчивости систем передачи информации путем учета искажений типа «1» в «Х» или «О» в «Х».

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

Как известно, циклический код характеризуегся тем, что если Е f> Е 2 ... ЕтЕо — комбинация циклического кода, то комбинация

ЕОЕп — ь Еп — 3, ... ЕзЕь получаемая циклическим сдвигом символов первой комбинации, также принадлежит циклическому коду (всего имеется и допустимых комбинаций) . Дешифрирование состоит в отождествлении принятого сообщения с той допустимой кодовой комбинацией, с которой оно различается не более, чем в / символах, исключая s «стертых» символов.

Алгоритм отождествления (для t ошибок и s стираний) можно записать в виде следующей последовательности этапов:

1) образуется комбинация b, путем подстановки в принятой комбинации b (передавалась b) нулей вместо стертых символов; в комбинации Ь,щ имеют место ошибки, полу1р ченные как при передаче по линии связи, так и в результате замены стираний иа нули;

2) образуется комбинация Ь„путем подстановки единиц на всех нестертых позициях и нулей на всех стертых; комбинация Б„ха15 рактеризует расположение стираний в принятой комбинации;

3) образуются по и комбинаций вида 6»„ и т (0(t(lI — 1) за счет циклических сдви20 ГОВ симВОЛОВ В комбинациях 00щ и 0ст, 4) после каждого у-го циклического сдвига определяется комбинация b U,Q+ с (сложение по модулю 2), в которой число единиц равно кодовому расстоянию ду (числу несовпадаю25 щих символов между b, и опорной комбинацией) с;

5) чтобы исключить в (b,Д+ c) единицы, » получившиеся на стертых позициях, образуЗр ется комбинация (b,,„Д+с)/,Ь, путем логи323778

65 гического умножения элементов (bÄ (+) с) на

1 соответствующие элементы bpT в o>+5" »UHH

/ (bp Q+ ) Лб„число единиц равно искомому кодовому расстоянию dl между b1 и с, исключая символы стирания;

b) полученное значение д сравнивается с пороговой величиной D ð — — 1+1, причем, если

) Drop> то считается, что & не «похожа» на с, если же di (Опор, то считается, что b1

«похожа» на с и, значит j=k;

7) в соответствии с числом сдвигов выбирается выходная шина дешифратора.

На чертеже изображен дешифратор циклического кода с исправлением ошибок и стираний для циклического кода с минимальным кодовым расстоянием d g — — 4, порождаемого полиномом вида (х) =х +х +х +1. В качестве опорной выбрана комбинация с=1011100.

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

На вход 9 подается импульс при приеме единицы или нуля, благодаря чему во втором регистре II (элементы 10 — 1б) окажется записанной комбинация b„, содержащая единицы на нестертых позициях и нули на стертых позициях. На вход 17 на все время ввода информации подается запрещающий сигнал, разрывающий цепи обратной связи регистров, благодаря чему они очищаются от старой информацииии.

Комбинации 6о образуются путем цикли1 ческих сдвигов в регистре 1, а комбинации

b„путем циклических сдвигов в регистре II.

Комбинации bpß с образуется с помощью

l схем «НЕ» 18 — 21, расположение которых соответствует расположению единиц в опорной комбинации, благодаря чему на первые входы первых схем «И» 22 — 28 подаются символы комбинации (b, Q+с), а на вторые входы

J первых схем «И» подаются символы 6„так

/ что на выходах схем «И» образуется комбинация (бoutQ+с(QЬс„число единиц в KOTOJ 1 рой равно искомому кодовому расстоянию d; между b1 и с, исключая символы стирания.

С помощью порогового элемента 29, имеющего порог срабатывания П=1)„р=1+1=2, п роизводится сравнение d с пороговой величиной D„ =t+1=2. Поэтому выходы первых схем «И» соединены с:входами 29. Так как нам удобнее иметь на выходе сигнал при

dj(Drrop и отсутствие сигнала при д;).Опор то, на выходе 29 ставится схема «НЕ» 80. Выбор выходной шины в соответствии с числом сдвигов k после которого d;=d<(Dppp осуществляется с помощью вторых схем «И» 31 — 87, на первые входы которых, поступают сигналы

15 г0

60 с выхода схемы «НЕ» 80, а на вторые входы— импульсы разрежения исполнения (38 — 44) .

Предложенный дешифратор работает следующим образом.

Рассмотрим процесс дешифрования на примере комбинации Ъ=11110ХО, которая получилась из комбинации b — — 1110010 в результате одной ошибки и одного стирания. После ввода всей информации в регистре 1 будет записана комбинация б, =1111000, а в регист-Π— О ре II — bp =1111101. Подается сигнал 38.

При этом на первые входы первых схем «И» (22 — 28) поступает:комбинация boo <+> с =

=0100100, а на вторые входы — b = 1111101, на выходах первых схем «И» (22 — 28) образуется комбинация (боц, (+) с) b„=0100100, в которой число единиц, равно do =2. В результате тото, что 1о =П=Dgpp пороговый элемент 29 срабатывает, но на выходе схемы

«НЕ» 80 сигнала не будет.

Затем осуществляется первый сдвиг и подается сигнал 89. При этом в первом регистре окажется комбинация b, =0111100, а во

1 втором регистре b. 1111110. На первые входы первых схем «И» поступает комбинация

bp(+)ñ =1100000, а на вторые входы — bp =

=1111110, поэтому на выходах первых схем

«И» образуется комбинация 4 < > с) l

1 1 = 1100000, в которой число единиц равно d; =2. В результате того, что

Ф

di =П=Ю р пороговый элемент 29 сработает, но на выходе схемы «НЕ» 80 сигнала не будет.

Далее осуществляется третий сдвиг и подается сигнал 40. При этом в первом регистре окажется комбинация b =0011110, а во вто-г

2 ром регистре b, =0111111. На первые входы первых схем «И» поступает комбинация

bp +>c= 1000010, а на вторые входы bgy ——

=0111111, поэтому на выходах первых схем

2 2

«И» образуется комбинация (bpm +> с)/ bc =

Ф

=0000010, в которой d2 =1. В результате того, что d2 (П=П„р поРоговый элемент 29 не сработает и на выходе схемы <НЕ» 30 будет сигнал, который поступает на первые входы вторых схем «И» 31 — 37. При этом сработает схема «И» 88, на второй,вход которой поступает сигнал 40. С,выхода схемы «И» 83 сигнал поступает на соответствующую выходную шину.

Если код представлен несколькими,кодовыми кольцами, то в каждом кольце выбирается своя опорная комбинация. Построение дешифратора аналогично, но кодовое расстояние определяется между b и всеми опорными комбинациямн.

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

Дешифратор циклического кода с исправлением ошибок и стираний содержащий два

323778

Составитель В. Шумский

Редактор Л. Утехина Техред А. Камышникова Корректор Н. Шевченко

Заказ 862/6 Изд. № 367 Тираж 448 Подписное

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

Москва, 5К-36, Раушская наб., д. 4/6

Типография, пр, Сапунова, 2 кольцевых регистра сдвига, схемы «НЕ», пороговые элементы, схемы «И», отличающийся тем, что, с целью повьппения,помехоустойчивости системы передачи информации, выходы ячеек первого кольцевого регистра сдвига, соответствующие нулевым позициям опорных комбинаций кодовых колец, соединены с первыми входами первых схем «И», а выходы ячеек первого кольцевого регистра сдвига, соответствующих единичным позициям опорных комбинаций, соединены с первыми входами первых схем «И» через схемы «НЕ», выходы

5 ячеек второго кольцевого регистра сдвига соединены,со вторыми входами, первых схем «И», выходы первых схем «И» соединены со входами пороговых элементов.