Устройство для декодирования двоичных кодов Хемминга Советский патент 1982 года по МПК H03M13/51 

1

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

Известное устройство для декодирования двоичных кодов Хемминга, содержащее регистр сдвига, сумматоры по модулю 2, входы которых связаны с ячейками регистра сдвига в соответствии с уравнениями проверок, и дешифратор про- Q верок, входные шины которого соединены с выходами соответствующих сумматоров по модулю 2, а выходные нганы - со счетными входами соответствующих ячеек регистра сдвига .-is

Однако данное устройство имеет повышенную сложность реализации при декодировании информационных посыпок большой длины. Сложность такого уст- 20 ройства обуславливается наличием в схеме параллельных сумматоров по модулю 2, количество входов у которых зависит от длины декодируемого слова. Pea- .

лизация сумматоров по модулю 2 с 6ол1 шим числом входов представляет значн тельную сложность из-за использования большого количества логических cxei при построении многовходовых сумматоров по модулю 2. Использование дешифратора проверок, формирующего вектор для исправления ошибок, значительно усложняет устройство, так как с увеличением длины декодируемой посылки увеличивается число схем совпадений, на которых построен дешифратор проверок, а кроме того, возникает необходимость в использовании многовходовых схем совпадений С Я J.

Наиболее близким по технической сущности к предлагаемому является уст ройство для. декодирования двоичных кодов Хемминга, содержащее счетчики, триггеры, входные элементы И, гумматор, элемент ИЛИ, выходной элемент И, к сдвиговой регистр, тактовый вход которого соединен с.шиной Тактирования, кроме того, счетный вход первого счетчика соединен с шиной тактирования и со счетным входом второго счетчика, а каждый из выходов подключен к одному из входов соответствующего входного элемента И, выход которого соединен со счетным входом одноименного триггера, нулевой выход которого подключен к одному из разрядных входов второго счетчи ка, нулевой выход первого разряда и единичные выходы последующих разрядов которого соединены с входами вьпсодного элемента И, выход которого подключен к одному из выходов сумматора, другой Вход которого соединен с выходом послед него разряда сдвигового регистра, а выход подключен к одному из входов элемента ИЛИ, другой Е5ход которого подклю чен ко вхоцной шине а выход - к информационному входу сдвигового регистра, при этом другие входы входных элементов И объединены и подключены к информационной входной шине. Однако известное устройство имеет достаточную сложность реализации, о словленную тем, что в устройстве используется два счетчика, а это щшводит к дополнительным усложнениям при построении устройств для декодирования двоичн кодов Хемминга. Цель изобретения - упрощение устройства для декодирования двоичных: кодов Хеммикга. Поставленная цель достигается тем, 4i;o в устройство для декодирования двоич ных кодов Хемминга, содержащее счетчики, триггеры, входные элементы И, сумматор, элемент ИЛИ, выходной элемент И и сдвиговый регистр, тактовый вход которого соединен с щиной тактирования, и к этой же шине тактирования подключен вход счетчика, каждый из выходов которого соединен с одним из входов соответ ствуюнгего вхрцного элемента И, выходкого- роге соединен со счетным входом одноименн го триггера, а выход выходного элемента И подключен к одному из входов сумматора, другой Вход которого соединен с выходом последнего разряда сдвигового регистра, а выход подключен к одному из входов элемента ИЛИ, другой вход которого подключен к входной шине, а выход к информационному входу сдвигового регистра, при этом другие входы входных элементов И объединены и подключены к информационной шине, введены четыре дополнительных элемента И и дополнительный триггер, счетный вход которого подключен к выходу первого дополнительного элемента И, а выход - к одному из входов выходного элемента И, первый вход которого соединен с инверснъ1м вы ходом счетчика, а другие - с Прямыми, кроме того, нулевые выходы триггеров подключены к входам одноименных дополнительных элементов И, другие входы которых объединены и подключенъ к выходу первого дополнительного элемента И, входы которого соединены с единичными выходами счетчика, причем установочные входы счетчика подключены к Выходам соответствукщих дополнительных элементов И, . На чертеже приведена блок-схема предлагаемого устройства для декодирования двоичных кодов, например, с длиной слова, равной 7. Устройство для декодирования двоичных кодов Хемминга содержит тактовую шину 1, первый счетчик 2, первый дополнительный элемент И 3, другие дополнительные элементы И 4, информационную вкоцнуюшину 5, входные элементы И 6, триггеры 7, Тюполнигельный триггер 8, выхоаной элемент И 9, элемент ИЛИ 10, с цвиговый регистр 11, сумматор 1 2, причем тактовые выходы счетчика 2 и сдвигового регистра 11 подключены к тактовой шине 1, а информационная шина 5 подключена к одному из входов элемента ИЛИ 10 и к соединенным между собой первыми входами Входных элементов И 5, вторые входы которых подключены к одноименным единичным выходам счетчика 2, Выходы входных элементов И 5 соединены со c4eTHbnvoi входами одноименных триггеров 7, нулевые выходы которых соединены соответственно с одними входами дополнительных элементов И 4, другие выходы которых объединены и подключены к выходу первого дополнительного элемента И 3. Этот выход также подключен к счетному входу триггера 8, выход которого соединен с одним из входов выходного элемента И 9, первый вход которого соединен с нулевым выходом счетчика 2, а другие - с единичными. Кроме того, единичные выходы счетчика 2 подключены к входам первого дополнительного элемента И 3. Один вход сумматора 12 соединен с выходом выходного элемента И 9, а другой подключен к выходу последнего разряда сдвигового регистра 11, первый разряд которого через элемент ИЛИ 10 соединен с выходом сумматора. Устройство для декодирования двоичн кодов Хемминга работает следующим об разом. В исходном состоянии все триггеры устройства находятся в нулевом состояНИИ (установка триггеров в О на схеме не указана). Посыпка двоичных символов, закодированная в коде Хемминга, поступает одновременно на все входные элементы И 6, в то же время через элемент ИЛИ 10,спустя И тактов, число которых определяется длиной декодируемой посылки она записывается в сцвиговый регистр 11.Счетчик 2 осуществляет подсчет тактовых импульсов. В зависимости от состояния триггеров счетчика 2 изменяются режимы работы входных элементов И 6. Рассмотрим случай, когда из линии сЬязи поступают символы кода а «,, а а а а, где а. - проверочные, а а Ч информационною разряды кода. Состояние триггеров счетчика можно выразить в виде табл. 1 Таблица Исходя из даннъЬс табл. 1, элементы И 6 пропускают соответственно символы а а, а а.,; а а а а а, ag а, . Полученные символы полностью соответствуют .символам, находящимся в ура нениях проверок кода Хемминга. Дапее разделенные символы поступают на счет ные входы одноименных триггеров 7, которые позволяют осуществить операцию сложения по модулю 2 и запомнить результат сложения. Каждому сочетанию состояний триггеров соответствует двои ное число, называемое синдромом ошибки, которое указывает номер поврежденного разряда. 0 (5 Состояния элементов памяти после вычисления синдрома приведены в табл.. 2. ;jr а б л и ц а 2 1 а, /+/ а, /+/ а., /+/ а -155t 2 а. /+/ а. /+/. а /+/ а.. уЬ 3 а. /+/ а.. /+/ а. /+/ а, ь6 Процесс декодирования происходит в два цикла, В первом цикле происходит вычисление синдрома, а во втором - коррекция принятой комбинации. Конец цикла определяется при помощи первого дополнительного элемента И 3. Как только на всех единичных выходах счетчика 2 появляются все единицы, элемент И 3 открьшается и на следующем такте синдром ошибки, вычисленной при помощи триггеров 7, через элементы И 4 запишется в инверсном коде в счетчик 2. Сигнал, поступающий с выхода элемента И 3, устанавливает триггер 8 в единичное состояние, тем самым осуществляется подготовка к работе выходного элемента И 9. Во втором цикле счетчик 2 также осуществляет подсчет тактовых импульсов. Если синдром ошибки отличен от О, т,е. в канале связи произошло искажение . символа на И-ой позиции, то через И тактов, считая такт записи в счетчик 2, на выходе выходного элемента И 9 появится логическая 1, Полученный вектор ошибки суммируется по модулю 2 при помощи сумматора 12с принятой кодовой посылкой. Далее исправленная кодовая посылка через элемент ИЛИ 10 записывается в сдвиговый регистр 11. Таким образом, осуществляется кор рекция одиночной сшибки. Рассмотрим процесс декодирования на конкретном примерю. Допустим передается посылка 10 1О 101, закодированная в коде Хемминга. В результате действия помех и линии связи происходит ее искажение и на вход устройства приходит посылка 10 00 101. Наиболее удобно процесс декодирования предстаьать в виде табл. 3, из которой видно, как происходит вычисление синдрома ошибки (НО), запись его в инверсном виде (001) на восьмом такте во вторюй счетчик, определеше вектора ошибки и коррюкция принятой кодовой посылки, .

S40299

8 . ТаблицаЗ

Вх.1000101

1О10101О1 О

б

OllOOllOO 1

ОО0111111

и

Вых, 1 о о о 1 о 1

Вых. 0000001

Вых. 00 О О 1 О 1 С. Р.

11001

о 00 о 90 о 1

О о 00110

Т.

Вых. С. Р.

Вых. И

Вых. С. М.

Включение в схему устройства для декодирования двоичных кодов Хемминга дополнительных элементов И и триггера позволяет упростить его без нарушения рабсгтоспособности в целом и без изменения технических характеристик.

Упрощение достигается исключением из схемы устройства для декодирования двоичных кодов Хемминга, взятого за / прототип, одного счетчика.

Счетчт1К по своей структуре гораздо сложле з эл }мептов И, которые являкзггся

О

Оп.

10 1 о

о1 и

о о

о

о 1

1 О О О

о о о

О О 1

О

о 1

101 о

одним из простейших элементов электронной техники, стоимость которых значительно уступает стоимости счетчика. Введение же триггера соответствует исключению из счетчика одного триггера.

Таким образом, изобретение значительно проще по сравнению с известными устройствами, кроме того, оно по стоимости гораздо дешевле, чем сушествующие устройства для декодирования двоичных кодов Хемминга, Особенно значительным этот фактор будет при декодироваНИИ информационных посылок большой длины. Формула изобретения Устройство для декодирования двоичных кодов Хемминга, содержащее счетчи ки, триггеры, входные элементы И, сумматор, элемент ИЛИ, выходной элемент И и сдвиговый регистр, тактовый вход которого соединен с шиной тактирования, и к этой же шине тактирования подключен вход счетчика, каждый из выходов которого соединен с одним из входов соответствующего входного элемента И, выход которого соединен со счетным входом одноименного триггера, а выход выходного элемента И подключен к одному из входов сумматора, другой вход которого соединен -с выходом последнего разряда сдвигового,регистра, а выход подключен к одному из входов элемента ИЛИ, другой вход которог подключен к входной шине, а выход - к информационному входу сдвигового регистра, при этом другие входы входных эле ентов И объединены и подключе 9 9 ны к информационной шине, отличающееся тем, что, с целью упрощения устройства, в него введены четыре дополнительных элемента И и дополни- тельный триггер, счетный вход которого подюгючен к выходу первого дополнительного элемента И, а выход - к одному из входов выходного элемента И, первый вход которого соединен с инверсным выходом счетчика, а другие - с прямыми, кроме того, нулевые выходы триггеров подключены к входам одноименных дополнительных элементов И, другие которых объединены и подключены к выходу первого дополнительного элемента И, входы которого соединены с единичными выходами счетчика, причем установочные входы счетчика подключены к выходам соответствующих дополнительных элементов И. Источники информации, принятые во внимание при экспертизе 1. Четвериков В. Н. Преобразование и передача информации, в АСУ. М., Высшая школа, 1974, с. 73. 2. Авторское свидетельство СССР по заявке № 2914442/18-24,