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

323778 Союз Созетскиз Сецизлистическиз РеспубликЗависимое от авт. свидетельстваЗаявлено 29.Х.1969 (Лт. 1383025/18-24) М, Кл. С 06111/О заявки М с присоединеПриоритетОпубликован комитет по деламизобретений и открыт ДК 68.326.77(088.8 ри Совете Министров СССРО.Х.1971, Бюллетень1за 1972 ания описания 13.1 Ъ,1972 ата опублик Авторы изобретениН. В, Волков и ф. 3. Келлер Заявцтел ЕШИФРА ИКЛИЧЕСКОГО КОДА С ИСПРАВЛЕНИЕМОШИБОК И СТИРАНИИ Изобретение относится к области вычислительной техники и может быть использовано в устройствах передачи информации через канал с помехами.Известны дешифраторы циклического кода с исправлением ошибок типа переходов 1 в О или О в 1 в отдельных разрядах передаваемого слова. Однако нередко в каналах связи наблюдаются переходы типа 1 в Х или О в Х (Х - стертый, неопо знанный символ).Целью изобретения является:повышение помехоустойчивости систем передачи информации путем учета искажений типа 1 в Х или О в Х. 15Сущность изобретения заключается в том, что определение кодового расстояния между принятой комбинацией (ее циклическими сдвигами) и опорной кодовой комбинацией производится только в нестертых позициях. 20Как известно, циклический код характеризуегся тем, что если Е 1, Е в,Е,Ео - комбинация циклического кода, то комбинация ЕвЕ, ь Е, з,ЕзЕь получаемая циклическим сдвигом символов первой комбинации, также 25 принадлежит циклическому коду (всего имеется а допустимых комбинаций) . Дешифрирование состоит в отождествлении принятого сообщения с той допустимой кодовой комбинацией, с которой оно различается не более, чем 30 в / символах, исключая з стертых символов.Алгоритм отождествления (для 1 ошибок и з стираний) можно записать в виде следующеи последовательности этапов:1) образуется комбинация Ь,ш путем подстановки в принятой комбинации Ь (передавалась Ь) нулей вместо стертых символов; в комбинации Ь,ш имеют место ошибки, полученные как при передаче по линии связи, так и в результате замены стираний иа нули;2) образуется комбинация Ьпутем подстановки единиц на всех нестертых позициях и нулей на всех стертых; комбинация Ьст характеризует расположение стирании в принятой комбинации;3) образуются по и комбинаций вида Ь 0 и Ь (0 п - 1) за счет циклических сдви- ГОВ СИМВОЛОВ В КОМОИНацняХ "ош И Ьст4) после каждого у-го циклического сдвига определяется комбинация Ь,Д+ с (сложение по модулю 2), в которой число единиц равно кодовому расстоянию ду (числу несовпадающих символов между Ь,ш и опорной комбинацией) с;5) чтобы исключить в (ЬпД+ с) единицы,65 гического умножения элементов (Ь,ш Д+ с) на1соответствующие элементы Ь; в комбинации(ЬошО+с) ЛЬчисло единиц равно искомому кодовому расстоянию ф между Ь 1 и с, исключая символы стирания;б) полученное значение д сравнивается с пороговой величиной Опор -- 1+1, причем, если)13 пор, то считается, что Й не похожа на с, если же д Опор, то считается, что Ь 1 похожа на с и, значит 1=Й;7) в соответствии с числом сдвигов выбирается выходная шина дешифратора.На чертеже изображен дешифратор циклического кода с исправлением ошибок и стираний для циклического кода с минимальным кодовым расстоянием (1 тп(п -- 4, порождаемого полиномом вида (х) =х+х+хг+1, В качестве опорной выбрана комбинация с=1011100.Дешифратор имеет два информационных входа. На вход 1 подается импульс при приеме единицы, благодаря чему в первом регистре 1 (элементы 2 - 8) окажется записанной комбинация Ь,ш, отличающаяся от полученной комбинации Ь наличием нулей в стертых позициях.На вход 9 подается импульс при приеме единицы или нуля, благодаря чему во втором регистре П (элементы 10 - 1 б) окажется записанной комбинация Ь, содержащая единицы на нестертых позициях и нули на стертых позициях. На вход 17 на все время ввода информации подается запрещающий ситнал, разрывающий цепи обратной связи регистров, благодаря чему они очищаются от старой информации. Комбинации Ьо образуются путем цикли 1ческих сдвигов в регистре 1, а комбинации 1Ьпутем циклических сдвигов в регистре 11.Комбинации ЬошЯ с образуется с помощьюlсхем НЕ 18 - 21, расположение которых соответствует расположению единиц в опорной комбинации, благодаря чему на первые входы первых схем И 22 - 28 подаются символы комбинации (Ьошс), а на вторые входы первых схем И подаются символы Ь так1 что на выходах схем И образуется комбинация (Ь рщ Я с ( Д Ьсу, число единиц В кОтОрой равно искомому кодовому расстоянию(1( между Ь 1 и с, исключая символы стирания.С помощью порогового элемента 29, имеющего порог срабатывания П=йпор=1+1=2, производится сравнение д с пороговой величиной Йпор -- +1=2. Поэтому выходы первых схем И соединены с входами 29. Так как нам удобнее иметь на выходе сигнал при (11(Опор и отсУтствие сигнала пРи д;).О,р то, на выходе 29 ставится схема НЕ 30. Выбор выходной шины в соответствии с числом сдвигов Й после которого д;=А(Опор осуществляется с помощью вторых схем И 31 - 37, на первые входы которых, поступают сигналы 5 10 15 го 25 30 35 40 45 50 55 60 с выхода схемы НЕ 30, а на вторые входы -импульсы разрежения исполнения (38 - 44),Предложенный дешифратор работает следующим образом.Рассмотрим процесс дешифрования на примере комбинации Ь=11110 ХО, которая получилась из комбинации Ь=1110010 в результатеодной ошибки и одного стирания. После вво.да всей информации в регистре 1 будет запи-осана комбинация Ь,ш=1111000, а в регистре 11 - Ьс =1111101. Подается сигнал 38,- оПри этом на первые входы первых схем И(22 - 28) поступает комбинация Ьо (+) с ==0100100, а на вторые входы - Ь = 1111101,на выходах первых схем И (22 - 28) обра.зуется комбинация (Ьо (+) с) Ь о, =0100100, вФкоторой число единиц, равно (1 о =2. В результате тото, что А =П=Опор пороговый элемент 29 срабатывает, но на выходе схемыНЕ 30 сигнала не будет.Затем осуществляется первый сдвиг и подается сигнал 39. При этом в первом регистре окажется комбинация Ь,ш=0111100, а вовтором регистре Ь=1111110. На первые входы первых схем И поступает комбинацияЬош(+)с =1100000, а на вторые входы - Ь ==1111110, поэтому на выходах первых схем1И образуется комбинация Ь,ш (с) /Ь 1 = 1100000, в которой число единиц равно д; =2, В результате того, чтоФ4 =П=1 пор пороговый элемент 29 сработа.ет, но на выходе схемы НЕ 30 сигнала небудет.Далее осуществляется третий сдвиг и подается сигнал 40. При этом в первом регистреокажется комбинация Ь,Ш=0011110, а во вто-г- 2ром регистре Ь=0111111. На первые входыпервых схем И поступает комбинацияЬ,ш(+)с=1000010, а на вторые входы Ьст ==0111111, поэтому на выходах первых схем- 2 - 2И образуется комбинация (Ьш+ с)/Ь=Ф=0000010, в которой дг =1. В результате того, что А СП=Йр пороговый элемент 29не сработает и на выходе схемы НЕ 30 будет сигнал, который поступает на первые входы вторых схем И 31 - 37. При этом сработает схема И 33, на второй,вход которой поступает сигнал 40, С,выхода схемы И 33сигнал поступает на соответствующую выходную шину,Если код представлен несколькими,кодовы.ми кольцами, то в каждом кольце выбираетсясвоя опорная комбинация. Построение дешифратора аналогично, но кодовое расстояние определяется между Ь и всеми опорными комбинациями. Предмет изобретенияДешифратор циклического кода с исправлением ошибок и стираний содержащий два323778 Составитель В. Шумскийедактор Л. Утехина Техред А. Камышникова Корректор Н. Шевченко Заказ 8626 ЦНИИПИ Коми Изд.367 Тираж 448 Подписноепо делам изобретений и открытий прн Совете Министров СССР Москва, Ж, Раушская наб., д. 4/6 пография, пр. Сапунова, 2 кольцевых регистра сдвига, схемы НЕ, пороговые элементы, схемы И, отличающийся тем, что, с целью повьппения,помехоустойчивости системы передачи информации, выходы ячеек первого кольцевого регистра сдвига, соответствующие нулевым позициям опорных комбинаций кодовых колец, соединены с первыми входами первых схем И, а выходы ячеек первого кольцевого регистра сдвига, соответствующих единичным позициям опорных комбинаций, соединены с первыми входами первых схем И через схемы НЕ, выходы 5 ячеек второго кольцевого регистра сдвига соединены,со вторыми входами, первых схем И, выходы первых схем И соединены со входами пороговых элементов.