Дешифратор циклического кода

267184 Союз Советских Социалистических РеспубликК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Зависимое от авт. свидетельстваЗаявлено 23.Х 1,1968 (М 1285050/18-24) Кл. 42 птз, 7/00 с присоединением заявкиМПК б 06УДК 681,325.63(088,8) ПриоритетОпубликовано 01,11/,1970, Бюллетень12Дата опубликования описания ЗЛ 111.1970 Комитет по делам изобретений и открытий при Совете Министров СССРАвторыизобретения Н, В. Волков и Ф, Э, Келлер Заявитель ДЕШИФРАТОР ЦИКЛИЧЕСКОГО КОДА,Предложенный дешифратор может найтиприменение в системах телеуправления, связи.Известны дешифраторы корректирующихкодов, содержащие кольцевые регистры сдвига и логические элементы.Предложенное устройство отличается от известных тем, что выходы ячеек кольцевого регистра сдвига, соответствующих нулевым по.зициям опорной комбинации кодового кольца,соединены непосредственно со входами порогового элемента, а выходы ячеек, соответствующих единичным позициям опорной комбинации кодового кольца, соединены со входами,порогового элемента через инверторы, выходпорогового элемента через инвертор подключен ко входам схем совпадения, другие входыкоторых соединены с шинами импульсов разрешения исполнения,Применение пороговых элементов в дешифраторах не является новым, но известныедешифраторы с использованием пороговыхэлементов имеют сложную конструкцию, чтовыражается в большом количестве пороговыхэлементов, имеют низкое отношение сигнали/помеха для кодов с д,( - , где и - длинакода, Ы,) 21+1 - минимальное кодовоерасстояние, а 1 - число исправляемых ошибок.Предлагаемый дешифратор циклического кода позволяет достигнуть многократного сокращения числа пороговых элементов, Этот результат является полезным потому, что пороговые элементы являются весьма сложными 5 и предъявляют высокие требования к разбросу параметров конструктивных элементов.Далее, что наиболее важно, предлагаемыедешифраторы позволяют увеличить различие между сигналом и помехой для кодов с 10 йд( - что открывает возможность применения этих устройств для исправления ошибок в системах телеуправления, связи и т. п.В целом предлагаемые устройства обеспечи вают более высокую надежность в работе засчет большего различия между сигналом и помехой,Как известно, циклический код характери зуется тем, что если ел - 1, еп е, е 0 - комбинация циклического кода, то комбинация е 0 еп - 1 зп - 2 .езв 1, получаем ая циклическим сдвигом символов первой комбинации, также принадлежит циклическому коду,Выберем в кольце в качестве опорной произвольную кодовую комбинацию, например ту, члены которой совпадают с элементами записи кодового кольца, и обозначим ее через С, Тогда комбинацию С можно получить 30 .из произвольной комбинации Ь тога же каль 3ца в результате Й циклических сдвигов(о(Й:и - 1), что можно записать какС=Ь, где 1=0,1,2 .и - 1.Отсюда следует, что каждая кодовая комбинация Ь данного кольца однозначно характеризуется числом сдвигов й, необходимых дляполучения опорной комбинации С,Допустим, что для передачи информациииспользуется циклический код с 4, )21+,1,который гарантированно исправляет до 1 ошибок включительно.Если в переданной комбинации Ь не произошло ошибок, то принятая комбинацияЬ=Ь. Осуществив й циклических сдвигов, мы,получим комбинацию Ь"=Р, которая во всехчленах совпадает с опорной комбинацией С,т. е, Р=Ьф=С. Ни один другой циклическийсдвиг Ь 1 =Ь 1 7= Й) не совпадает с комбинацией С. Так как число Й однозначно характеризует дешифрируемую комбинацию Ь, то всоответствии с числом Й можно выбрать выходную шину дешифратора.Если же при передаче той же комбинацииЬ произошло не более 1 ошибок, то получен,ная искаженная комбинация Ь все же большепохожа (совпадает в большем числе членов) на комбинацию Ь, чем на другие комбинации циклического кода. Поэтому и Й-й ци,клический сдвиг комбинации Ь, т, е. Р больше похож на опорную комбинацию С, чемдругие циклические сдвиги Ь 1 (11), Следовательно, несмотря наошибки в кодовой комбинации, возможно правильное дешифрирование: для этого достаточно определить номерсдвига (т. е. число Й), после которого отмечается наибольшее сходство с опорной комбинацией С, и выбрать в соответствии с числомА выходную шину дешифратора, Очевидно,мерой сходства комбинаций Ь 1 (0(1(а - 1)и опорной комбинации С может служить величина кодового расстояния д 1 между ними.Рассмотрим этот вопрос теперь более детально. Если ошибок не произошло, тоЬ = Ь = С, т. е, кодовое расстояние междуЬ =Ь и С будет д - О, Кодовые расстояниямежду Ь 1 =Ь и С будут равны Ы 1)й.ОФ).Если же произошло ровно 1 ошибок (наихудший вариант), то расстояние между Ь и.Ь равно й=1. Поэтому и расстояние междуЬ и С определится как д =. В то же времякодовые расстояния между Ь 1 (1 ФЙ) и С будут равныд 1) д; - 121+,1 - 1=1+(1 Ф 1)Минимальное пороговое значение д 1 (при1 Ф=Й) обозначим через Рпор =1+1.Так как всегда д Р,р, а Й 1 Цюр у(1 Фф)то это обстоятельство может быть использова 267184 но для правильного дешифрирования при наличии не более 1 ошибок.Окончательно алгоритм дешифрированиякомбинаций, входящих в одно кодовое коль 5 цо, можно описать следующим образом,1, Принятая комбинация Ь циклически сдвигается, при этом образуются п комбинацийвида Ь 1 (0)1) и - 1),2, После каждого 1-го сдвига производитсяопределение кодового расстояния д междукомбинацией Ь 1 и опорной комбинацией С,3. Полученное значение д сравнивается с,пороговой величиной Р,р в в ; причем, ес 15 ли д 1 )Р,р, то считается, что Ь не похожа на С, если же д 1(Р,р, то считается,что М похожа на С и, значит, 1=1.4. В соответствии с числом й выбираетсявыходная шина дешифратора.Техническая реализация этого алгоритма,дешифрированная для циклического кода(7, 3), приведена на чертеже,где Вх 1, Вх 2 - входные шины; Я 1 - Я 7 -25ячейки кольцевого регистра сдвига; 3 - ячейка запрета, НЕ - инверторы; ПЭ - пороговый элемент; И - схемы совпадения; РИ, -РИ, - шины разрешения исполнения; Вых 1 -Вых 7 - выходные шины дешифратора.Поэтапно работа дешифратора может бытьописана следующим образом,1. Операция циклического сдвига дешифри,руемой комбинации производится в приемномкольцевом регистре сдвига. В цепи обратнойсвязи регистра помец 1 ается ячейка запрета,которая обрывает обратную связь на время,приема, дешифрируемой комбинации (приэтом старая комбинация покидает регистр),2, Определение кодового расстояния д 140 между комбинацией Ь 1 в регистре и опорнойкомбинации С осуществляется с помощьюсхем инверсии НЕ, расположенных на выходах тех разрядов регистра, которые соответствуют 1 в опорной комбинации С. Благо 45 даря этому осуществляется сравнение комбинаций в регистре и комбинации С, причем результатом сравнения являются импульсы(сигналы) на выходах схем НЕ и непосредственно на выходах тех разрядов регистра,50 где схемы НЕ отсутствуют. Эти сигналыпоявляются лишь при несовпадении соответствующих членов комбинации в регистре иопорной комбинации С. Таким образом, числоимпульсов (сигнала) на выходах будет равно55 кодовому расстоянию д;.3. Сравнение д 1 с величиной Р,р -- 1+1осуществляется на и-входовом пороговом элементе ПЭ, имеющем порог срабатывания, .равный Р,р -- 1+1, На эти и входов ПЭ и по 60 даются сигналы с выходов схем НЕ и выходов ячеек регистра, где схемы НЕ отсутствуют, Если число входных импульсов (сигналов) Й 1)Р,р, то пороговый элемент сработает и выдаст выходной сигнал, если же65 д (Р,р, то пороговый элемент не сработает,Однако нам необходимо получить на выходе сигнал при а (Оор и отсутствие сиг-. нала при д 1 0 щ, поэтому на выходе ПЭ ставится схема НЕ.4. Выбор выходной шины в соответствии с числом сдвигов Й, после которого оказывалось 1 = д(й,р, осуществляется с помощью схем двух совпадений И, на один вход которых поступают сигналы с выхода схемы НЕ 1 после порогового элемента), а на другой - импульсы разрешения исполнения РО.Процесс дешифрирования в такой схеме представляет собой следующую последовательность действия: на Вх 1 поступает в последовательном коде дешифрируемая комбинация. На,время ввода новой комбинации на Вх 2 подается сигнал запрета, благодаря чему обрывается цепь обратной связи, и старая комбинация выталкивается из регистра. После ввода членов дешифрируемой комбинации сигнал запрета на Вх 2 снимается и подается сигнал РИО, затем осуществляется первый сдвиг в регистре и одновременно подается РО и т. д., наконец, после Й-го сдвига на выходе схемы НЕ после порогового элемента появится импульс, а так как одновременно подается сигнал РИ, то одна из схем И ."работает и на соответствующую выходную шину поступит выходной импульс.В качестве опорной комбинации выбрана кодовая комбинация 1011100, чем и объясняется расположение схем НЕ, Так как в этом коде д,=4, то величина В,р -- 1+1=2, Дешифратор позволяет исправить одну ошибку, так как в этом случае й=1( (1 пор =2. Если произойдет две ошибки, то И=2 и схема ПЭ сработает, но на выходесхемы НЕ сигнала не будет, Итак, схемареализует возможности кода, исправляя однуошибку и обнаруживая две ошибки,Если код представляется системой кодовыхколец, то в каждом кольце выбирается свояопорная комбинация С. Построение дешифратора будет аналогичным за тем исключением,что комбинации в регистре сравниваются пе1 О с одной, а со всеми опорными комбинациями.При этом для дешифрирования комбинацийкаждого кодового кольца потребуется одинпороговый элемент ПЭ, одна схема НЕ, стоящая после ПЭ, и п схем И. Число схемНЕ для сравнения со всеми опорными комбинациями не превысит числа и. Предмет изобретениягоДешифратор циклического кода, содержащий кольцевой регистр сдвига и логические элементы, отличающийся тем, что, с целью повышения надежности работы устройства, выходы ячеек кольцевого регистра сдвига, соответствующих нулевым позициям опорной комбинации кодового кольца, соединены непосредственно со входами порогового элемента, а выходы ячеек, соответствующих единичным позициям опорной комбинации кодового кольца, соединены со входами порогового элемента через инверторы, выход порогового элемента через инвертор подключен ко входам схем совпадения, другие входы которыхсоединены с шинами импульсов разрешенияисполнения.267184 Р РИ орска ставцтел ненко Корректор Л. С. Ведене ред 3,. П, Белявска едакт Гцпографня, пр, Сапунова Заказ 19153 Тираж 480.1 НИИПИ Комитета по делам изобретений и открь Москва, Ж, Раушская нПодписноий при Совете Министров ССС6., д. 4/5