ДЕШИФРАТОР ЦИКЛИЧЕСКОГО КОДА С ИСПРАВЛЕНИЕМ ОШИБОК И СТИРАИИИ Советский патент 1972 года по МПК G06F11/08 

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

Известны дешифраторы циклического кода с исправлением ошибок типа переходов «1 в «О или «О в «1 в отдельных (разрядах передаваемого слова. Однако нередко в каналах связи наблюдаются переходы типа «1 в «X или «О в «X («X - «стертый, «еонознанный символ).

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

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

Как известно, циклический код характеризуется тем, что если En-i, Еп-2, - EiEo - комбинация циклического кода, то комбинация ЕйЕп-1, En-z,... EzEi, получаемая циклическим сдвигом символов лервой комбинации, также принадлежит циклическому коду (всего имеется п допустимых комбинаций). Дешифрирование состоит в отождествлении принятого сообщения с той допустимой кодовой комбинацией, с которой оно различается не более, чем

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

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

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

3)образуются по п комбинаций вида Ьош и bct () за счет циклических сдвигов символов в комбинациях &ош и &ст;

4)после каждого /-го циклического сдвига определяется комбинация с (сложение по модулю 2), В которой число единиц равно кодовому расстоянию J// (числу несовпадающих символов между Ьош и опорной комбинацией) с;

гического умножения элементов (&ош © с) на соответствующие элементы &ст комбинации (&ош®) Л&ст число единиц равно искомому кодовому расстоянию dj между Ь и с, исключая символы стирания;

6)полученное значение d сравнивается с Пороговой величиной jDnop +l, причем, если dj , то считается, что Ь не «похожа

на с, если же d/ пор, то считается, что Ь «похожа на с и, значит j-k;

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

На чертеже изображен дешифратор циклического кода с исправлением ошибож и стираНИИ для циклического кода с минимальным кодовым .расстоянием dmin-, порождаемого полиномом вида (л:) - л;2+1. В качестве опорной выбрана комбинация с 1011100.

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

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

Комбинации Ь{т образуются путем циклических сдвиго)В IB регистре 1, а комбинации бет путем циклических сдвигов Б регистре //.

Комбинации Ьошф с образуется с помощью схем «НЕ 18-21, расположение которых соответствует расположению единиц в опорной комбинации, благодаря чему на первые входы первых схем «И 22-28 подаются символы комбинации (&ош@с), а на вторые входы первых схем «И подаются символы b{f, так что на вь1ходах схем «И образуется комбинация (б{щ @ с (Д бет, число единиц в которой равно искомому кодовому расстоянию dj между Ь и с, исключая символы стирания.

С помощью порогового элемента 29, имеющего порог срабатывания , производится сравнение dJ с пороговой величиной . Поэтому выходы первых схем «И соединены с входами 29. Так как нам удобнее иметь на выходе сигнал при и отсутствие сигнала при то, на выходе 29 ставится схема «НЕ 30. Выбор выходной щины в соответствии с числом сдвигов k после которого dj осуществляется с помощью вторых схем «И 5/-37, на первые входы которых поступают сигналы

с выхода схемы «НЕ 30, а на вторые входыимпульсы разрешения исполнения (38-44).

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

Рассмотрим процесс дешифрования на примере комбинации Ь 11110ХО, которая получилась из комбинации 6 1110010 в результате одной ошибки и одного стирания. После ввода всей информации в регистре I будет записана комбинация Ьош 1111000, а в регистре II -&СТ 1111101. Подается сигнал 38. При этом на первые входы первых хем «И (22-28) поступает комбинация (+)с - 0100100, а на вторые входы - бет 1Ш101, на выходах первых схем «И (22-28) образуется комбинация (бош (+) с) 0100100, в которой число единиц равно do 2. В результате того, что dl П -Dnop пороговый элемент 29 срабатывает, но на выходе схемы «НЕ 30 сигнала не будет.

Затем осуществляется первый сдвиг и подается сигнал 39. При этом в первом регистре окажется комбинация 6ош 0111100, а во втором регистре bl, 1111110. На первые входы первых схем «И поступает комбинация 1100000, а на вторые входы -&« - 1111110, поэтому на выходах первых схем «И образуется комбинация бош 0 с) Д 6„ 1100000, в которой число единиц равно d 2. В результате того, что

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

Далее осуществляется третий сдвиг и подается сигнал 40. При этом в первом регистре окажется комбинация Ьош 0011110, а во втором регистре 6ош 0111111. На первые входы первых схем «И поступает комбинация

ош©С1 1000010, а на вторые входы ист- 0111111, поэтому на выхода х первых схем «И образуется комбинация (omliс) Д бет 0000010, в которой iia 1. В результате того, что dz )пор пороговый элемент 29 пе сработает и на выходе схемы «НЕ 30 будет сигнал, который поступает на первые входы вторых схем «И 31-57. При этом сработает схема «И 33, на второй вход которой поступает сигнал 40. С выхода схемы «И 33 сигнал поступает на соответствующую выходную шину.

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

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

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

о о о о О о

39 39 0 f fi2 it3