Дешифратор циклического кода
Иллюстрации
Реферат
оесоюзна и е. т е и т н о .,-; . а, о Aihl5
О ПЙ САНИ Е
ИЗОБРЕТЕН ИЯ
267I84
Союз Советских
Социалистических
Республик
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Зависимое от авт. свидетельства №
Заявлено 23.XI.1968 (¹ 1285050/18-24) Кл. 42птз 7/00 с присоединением заявки №
МПК б 06f
УДК 681.325.63 (088.8) Приоритет
Опубликовано 01.IV.1970, Бюллетень № 12
Дата опубликования описания ЗЛ Ш.1970
Комитет по делам изобретений и открытий при Совете Министров
СССР
Авторы изобретения
Н. В. Волков и Ф. Э, Келлер
Заявитель
ДЕШИФРАТОР ЦИКЛИЧЕСКОГО КОДА,Предложенный дешифратор может найти применение в системах телеуправления, связи.
Известны дешифраторы корректирующих кодов, содержащие кольцевые регистры сдвига и логические элементы.
Предложенное устройство отличается от известных тем, что выходы ячеек кольцевого регистра сдвига, соответствующих нулевым по.зициям опорной комбинации кодового кольца, соединены непосредственно со входами порогового элемента, а выходы ячеек, соответствующих единичным позициям опорной комбинации кодового кольца, соединены со входами ,порогового элемента через инверторы, выход порогового элемента через инвертор подключен ко входам схем совпадения, другие входы .которых соединены с шинами импульсов разрешения исполнения.
Применение пороговых элементов в дешифраторах не является новым, но известные дешифраторы с использованием пороговых элементов имеют сложную конструкцию, что выражается в большом количестве пороговых элементов, имеют низкое отношение сигнал и
/помеха для кодов с dt„(—, где и — длина кода, d,„) 23+1 — минимальное кодовое расстояние, а t — число исправляемых ошибок.
Предлагаемый дешифратор циклического кода позволяет достигнуть многократного сокращения числа пороговых элементов. Этот результат является полезным потому, что пороговые элементы являются весьма сложными
5 и предъявляют высокие требования к разбросу параметров конструктивных элементов.
Далее, что наиболее важно, предлагаемые дешифраторы позволяют увеличить различие между сигналом и помехой для кодов с
10 11
d „(— что открывает возможность применения этих устройств для исправления ошибок в системах телеуправления, связи и т. п.
В целом предлагаемые устройства обеспечи15 вают более высокую надежность в работе за счет большего различия между сигналом и помехой, Как известно, циклический код характери2о ЗуЕтСя тЕМ, Чта ЕСЛИ Еп — 1, Еп-2 ... Е, ЕО бинация циклического кода, то комбинация
ЕОЕп — 1пп — 2 ... Езет, ПОЛуЧаЕМ ая ЦИКЛИЧЕСКИМ сдвигом символов первой комбинации, также принадлежит циклическому коду.
Выберем в кольце в качестве опорной произвольную кодовую комбинацию, например ту, члены которой совпадают с элементами записи кодового кольца, и обозначим ее че.рез С. Тогда комбинацию С можно получить
30 .из произвольной комбинации Ь тога же каль3 ца в результате k циклических сдвигов (o
C=b, где k=0, 1,2 ... n — 1. .Отсюда следует, что каждая кодовая комбинация b данного кольца однозначно характеризуется числом сдвигов k, необходимых для получения опорной комбинации С.
Допустим, что для передачи информации используется циклический код с dm<, )2t+1, который гарантированно исправляет до t оши.бок включительно.
Если в переданной комбинации b не:произошло ошибок, то принятая комбинация
b=b. Осуществив k циклических сдвигов, мы ,получим комбинацию b Ð, которая во всех членах совпадает с опорной комбинацией С, т. е. Ь" =Ь» =С. Ни один другой циклический сдвиг b» =Ь»() + k) не совпадает с комбинацией С. Так как число Й однозначно характеризует дешифрируемую комбинацию Ь, то в соответствии с числом k можно выбрать выходную шину дешифратора.
Если же при передаче той же комбинации
Ь произошло не более 1 ошибок, то получен,ная искаженная комбинация b все же больше .«похожа» (совпадает в большем числе членов) на комбинацию b, чем на другие комбинации циклического кода. Поэтому и Й-й ци,клический сдвиг комбинации b, т, е. Ь» боль.ше «похож» на опорную комбинацию С, чем другие циклические сдвиги b» (j k). Следовательно, несмотря на ошибки в кодовой комбинации, возможно правильное дешифрирование: для этого достаточно определить номер сдвига (т. е. число k), после которого отмечается наибольшее «сходство» с опорной комбинацией С, и выбрать в соответствии с числом
k выходную шину дешифратора. Очевидно, мерой сходства комбинаций Ь» (0
Рассмотрим этот вопрос теперь более детально. Если ошибок не произошло, то
b =b =С, т. е. кодовое расстояние между
b =Ь» и С будет d — О, Кодовые расстояния между Ь» =Ь» и С будут равны dl )dm,„
0= )Если же произошло ровно 1 ошибок (наихудший вариант), то расстояние между Ь и
b равно d=t. Поэтому и .расстояние между
b и С определится как d =t. В то же время
-кодовые расстояния между b» (j+k) и С будут равны
dy >d; — t>2t+,1 — t=t+1. (1Ф )
Минимальное пороговое значение dj (при
jAk) обозначим через D„> =1+1.
Так как всегда dp (Рпор а й/ Ощ,р у (jak) то это обстоятельство может быть использова267184 но для правильного дешифрирования при наличии не более t ошибок.
Окончательно алгоритм дешифрирования комбинаций, входящих в одно кодовое коль5 цо, можно описать следующим образом.
1. Принятая комбинация b циклически сдвигается, при этом образуются и комбинаций вида Ь»(0)1)п — 1).
2. После каждого 1-го сдвига производится определение кодового расстояния d между комбинацией Ь» и опорной комбинацией С.
3. Полученное значение dj сравнивается с
»пороговой величиной D„,ð — — 1+1; причем, ес15 ли d> ) D«p, то считается, что b - не «похожа» на С, если же dj (D„,ð, то считается, что Ь» «похожа» на С и, значит, j=k.
4. В соответствии с числом и выбирается выходная шина дешифратора.
Техническая реализация этого алгоритма, дешифрированная для циклического кода (7, 3), приведена на чертеже, где Вх1, Вх2 — входные шины; Яl — Я7—
25 ячейки кольцевого регистра сдвига; 3 — ячейка запрета, HL — инверторы; ПЭ вЂ” пороговый элемент; И вЂ”; РИО—
РИ6 — шины разрешения исполнения; Выхl—
Вых7 — выходные шины дешифратора.
Поэтапно работа дешифратора может быть описана следующим образом.
1. Операция циклического сдвига дешифри.руемой комбинации производится в приемном кольцевом регистре сдвига. В цепи обратной связи регистра помец1ается ячейка запрета, которая обрывает обратную связь на время ,приема, дешифрируемой комбинации (при этом старая комбинация покидает регистр).
2. Определение кодового расстояния d>
4О между комбинацией b» в регистре и опорной комбинации С осуществляется с помощью схем инверсии «НЕ», расположенных на выходах тех разрядов регистра, которые соответствуют «1» в опорной комбинации С. Благо45 даря этому осуществляется сравнение комбинаций в регистре и комбинации С, причем результатом сравнения являются импульсы (сигналы) на выходах схем «НЕ» и непосредственно на выходах тех разрядов регистра, 5р где схемы «НЕ» отсутствуют. Эти сигналы появляются лишь при несовпадении соответствующих членов комбинации в регистре и опорной комбинации С. Таким образом, число импульсов (сигнала) на выходах будет равно
55 кодовому расстоянию d;
3. Сравнение dl с величиной D,ð =t+1 осуществляется на п-входовом пороговом элементе ПЭ, имеющем порог срабатывания, . равный .О„р =t+1. На эти п входов ПЭ и по60 даются сигналы с выходов схем «НЕ» и выходов ячеек регистра, где схемы «НЕ» отсутствуют. Если число входных импульсов (сигналов) dj )В„,р, то пороговый элемент сработает и выдаст выходной сигнал, если же
65 г (Dapp, то поРоговый элемент не сРаботает, 267184
Однако нам необходимо получить на выходе сигнал при dj
4. Выбор выходной шины в соответствии с числом сдвигов Й, после которого оказывалось а = d»(Drop осуществляется с помощью схем двух совпадений «И», на один вход которых поступают сигналы с выхода схемы
«НЕ» (после порогового элемента), а на дру гой — импульсы разрешения исполнения РО.
Процесс дешифрирования в такой схеме представляет собой следующую последовательность действия: на Вх 1 поступает в последовательном коде дешифрируемая комбинация. На,время ввода новой комбинации на
Вх 2 подается сигнал запрета, благодаря чему обрывается цепь обратной связи, и старая комбинация выталкивается из регистра. После ввода членов дешифрируемой комбинации сигнал запрета на Вх 2 снимается и подается сигнал РИ,, затем осуществляется первый сдвиг в регистре и одновременно подается
РО и т. д., наконец, после k-го сдвига на выходе схемы «НЕ» после порогового элемента появится импульс, а так как одновременно подается сигнал РИ, то одна из схем «И» ."работает и на соответствующую выходную шину поступит выходной импульс.
В качестве опорной комбинации выбрана кодовая комбинация 1011100, чем и объясняется расположение схем «НЕ». Так как в этом коде dm,„=4, то величина В„,р — — 1+1=2, Дешифратор позволяет исправить одну ошибку, так как в этом случае d =1( (D„„,ð — — 2. Если произойдет две ошибки, то
d> — — 2 и схема ПЭ сработает, но на выходе схемы «НЕ» сигнала не будет, Итак, схема реализует возможности кода, исправляя одну ошибку и обнаруживая две ошибки.
Если код представляется системой кодовых колец, то в каждом кольце выбирается своя опорная комбинация С. Построение дешифратора будет аналогичным за тем исключением, что комбинации в регистре сравниваются е с одной, а со всеми опорными комбинациями.
При этом для дешифрирования комбинаций каждого кодового кольца потребуется один пороговый элемент ПЭ, одна схема «НЕ», стоящая после ПЭ, и п схем «И». Число схем
«НЕ» для сравнения со всеми опорными комбинациями не превысит числа и.
Пр едм ет изобретен и я го
Дешифратор циклического кода, содержащий кольцевой регистр сдвига и логические элементы, отличающийся тем, что, с целью повышения надежности работы устройства, выходы ячеек кольцевого регистра сдвига, соответствующих нулевым позициям опорной комбинации кодового кольца, соединены не.посредственно со входами порогового элемента, а выходы ячеек, соответствующих единичным позициям опорной комбинации кодового кольца, соединены со входами порогового элемента через инверторы, выход порогового элемента через инвертор подключен ко входам схем совпадения, другие входы которых соединены с шинами импульсов разрешения исполнения.
267184 ахи х!
РИо РИ, РИ РИу РИ Щ РИ
Составитель Л. Горская
Редактор Н. П. Белявская Техред 3. Н. Тараненко Корректор Л. С. Веденеева
Заказ 1915!3 Тираж 480 Подписное
11ИИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР
Москва, 5К-35, Раушская наб., д. 4/5
Тппография, пр. Сапунова, 2