Устройство для декодирования двоичных кодов хемминга

 

УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ ДВОИЧНЫХ КОДОВ ХЕММИНГА, содержащее триг геры, входные элементы И, су матор, элемент ИЛИ, выходной элемент И, первый элемент И, вторые элементы И, дополнительный триггер,сдвиговый регистр и счетчик импульсов, прямые входы которого соединены с первыми входами соответствующих входных элементов И, которых соединены со счетными входами соответствующих триггеров, выход выходного элемента И подключен к входу сумматора , другой вход которого соединен с выходом последнего разряда сдвигового регистра, а выход подключен к входу элемента ИЛИ, другой вход которого подключен к входной шине, а выход - к информационному входу сдвигового регистра, тактовый вход которого соединен с входом счетчика,вторые входы входных элементов И объе-. i динены и подключены к входной шине, счетный вход дополнительного триггера подключен к выходу первого элемента И, а прямой выход - к первому входу выходного элемента И второй вход которого соединен с инверсным выходом счетчика импульсов, а третий и четвертый - с соответствующими прямыми выходами счетчика импульсов, инверсные выходы триггеров подключены к первым входам соответствующих вторых элементов И, вторые входы которых объединены и подключены к выходу первого элемента И, входы которого соединены с соответствующими прямыми выходами счетчика импульсов, а его установочные входы подключены ео с к соответствующим выходам вторых элементов И, о т л и ч а ю щ е е с я тем, что, с целью повьшения быстродействия , в него введены генератор импульсов, третий и четвертый элементы И и дополнительный элемент ИШ, выход которого подключен к тактовому . э У1 входусдвигового регистра, а его входы соединены с выходами третьего и четвертого элементов И, причем вый вход третьего элемента И соедиэ нён с прямым выходом дополнительного UD триггера, а второй - с выходом генератора импульсов, тактовая тина соединена с первым входом четвертого элемента И, второй вход которого подключен к инверсному выходу дополнительного триггера.

СОЮЗ СОВЕТСКИХ.

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

09) (И) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬПЪЮ (21) 3456086/18-21 (22) 23.06.82 (46) 30.10. 83. Бюл. Ф 40 (72) В.С. Давыдов, А.Б. Жуков и С.В. Обухов (71) Новосибирский электротехнический институт (53) 621.374(088.8) (56) 1. Авторское свидетельство СССР

У 892714, кл. Н 03 К 13/24, 13.11.80.

2.. Авторское свидетельство по заявке Ф 3220084/18-21, кл.Н 03 К 13/24, l6.12.80. (54)(57) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ ДВОИЧНЫХ КОДОВ XEMNHHI A, содержащее триггеры, входные элементы И, сумматор, элемент ИЛИ, выходной элемент И, первый элемент И; вторые элементы И, дополнительный триггер,сдвиговый регистр и счетчик импульсов, прямые входы которого соединены с первыми входами соответствующих входных элементов И, выходы которых соединены со счетными входами соответствующих триггеров, выход выходного элемента И подключен к входу суммлтора, другой вход которого соединен с выходом последнего раэряда сдвигового регистра, а выход подключен к входу элемента ИЛИ, другой вход которого подключен к входной шине, а выход — к информационному входу сдвигового регистра, тактовый вход которого соединен с входом счетчика,вторые входы входных элементов И объе- 1 динены и подключены к входной шине, счетный вход дополнительного триггера подключен к выходу первого элемента И, а прямой выход — к первому входу выходного элемента И, второй вход которого соединен с инверсным выходом счетчика импульсов, а третий и четвертый — с соответствующими прямыми выходами счетчика импульсов, инверсные выходы триггеров подключены к первым входам соответствующих вторых элементов И, вторые входы которых объединены и подключены к выходу первого элемента И, входы которого соединены с соответствующими прямыми выходами счетчика импульсов, а

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

1051709 2

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

Известно устройство для декодирования двоичных кодов Хемминга, содержащее счетчики, триггеры„ входные элементы И, сумматор, элемент ИЛИ, выходной элемент И и сдвиговый регистр $1) .

Однако устройство характеризуется низким быстродействием, .которое обусловлено .тем, что процесс декодирования осуществляется в два равных по времени цикла. В первом цикле проис-. ходит вычисление синдрома, во второмкоррекция принятой комбинации.

1О

Наиболее близким техническим решением является устройство для деко- щ дирования двоичных кодов Хемминга, содержащее триггеры, входные элементы И, сумматор, элемент ИЛИ, выходной элемент И, первый элемент И, вторые элементы И, дополнительный триг- р5 гер, сдвиговый регистр и счетчик, прямые выходы которого соединены с первыми входами соответствующих входных элементов И, выходы которых соединены со счетными входами соответствующих триггеров, выход выходного элемента И подключен к входу сумматора, другой вход которого соединен с вьгходом последнего разряда сдвигового регистра, а выход подключен к входу элемента ИЛИ, другой вход кото- . рого подключен к входной шине, а выход — к информационному входу сдвигового регистра, тактовый вход которого соединен с входом счетчика, вто-4О рые входы входных элементов И объединены и подключены к входной шине, счетный вход дополнительного триггера подключен к выходу первого элемента И, а прямой выход к первому 45 входу выходного элемента И, второй ,вход которого соединен с инверсным выходом счетчика, а третий и четвер» . тый — с соответствующими прямыми выходами счетчика, инверсные выходы 50 триггеров подключены к первым входам соответствующих вторых элементов И, вторые входы которых объединены и подключены к выходу первого элемента И, входы которого соединены с соответствующими прямыми выходами счет- 55 ,.чика, а его установочные входы подключены к соответствующим выходам вторых элементов И (2J .

Недостатком этого устройства так же является низкое быстродействие, обусловленное тем, что процесс декодирования осуществляется в два равных по времени цикла. В первом цикле происходит вычисление синдрома, во втором — коррекция принятой комбинации.

Цель изобретения — повышение быстродействия.

Поставленная цель достигается тем, что .в устройство для декодирования двоичных кодов Хемминга, содержащее триггеры, входные элементы И, сумматор, элемент ИЛИ, выходной элемент И. первый элемент И, вторые элементы И, дополнительный триггер, сдвиговый регистр и счетчик импульсов, прямые выходы которого соединены с первыми входами соответствующих входных элементов И, выходы которых соединены со счетными входами соответствующих триггеров, выход выходного элемента И подключен к входу сумматора, другой вход которого соединен с выходом последнего разряда сдвигового регистра, а выход подключен к входу элемента ИЛИ, другой вход которого подключен к входной шине, а выход— к информационному входу сдвигового регистра, тактовый вход которого соединен с входом счетчика, вторые входы входных элементов И объединенй и подключены к входной.шине, счетный вход дополнительного .триггера подключен к выходу первого. элемента И, а прямой выход — к первому входу выходного элемента И, второй вход которого соединен с инверсным выходом счетчика импульсов, а третий и четвертый — с соответствующими прямыми выходами счетчика импульсов, инверсные выходы триггеров подключены к первым входам соответствующих вторых элементов И, вторые входы которых объединены и подключены к выходу йервого элемента И, входы которого соединены с соответствующими прямыми выходами счетчика импульсов, а его установочные входы подключены к соответствующим выходам вторых элементов И, введены генератор импульсов, третий и четвертый элементы И и дополнительный элемент ИЛИ, выход которого подключен к тактовому входу сдвигового регистра, à его входы соединены с выходами третьего и чет-, вертого элементов И, причем первый вход третьего элемента И соединен с

) г j з

Таблица 1

ЗО

0

3. .10 прямым выходом дополнительного триггера, а второй — с выходом генератора импульсов, тактовая шина соединена с первым входом четвертого элемента И, второй вход .которого подключен к инверсному выходу дополнительного триггера.

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

Устройство для декодирования двоичных кодов Хемминга содержит генератор 1 импульсов, элементы И 2 и 3, дополнительный элемент ИЛИ 4, первый элемент И 5, вторые элементы И 6, тактовую шину 7, входную шину 8, входные элементы И 9, триггеры 10, дополнительный триггер ll, выходной элемент И 12, элемент ИЛИ 13 сдвиговый регистр 14, сумматор 15 и счет чик 16 импульсов, причем выход гене-. ратора 1 импульсов, соединен с входом элемента И 2, второй вход которого соединен с прямым выходом триггера 11, а инверсный выход триггера

1l соединен с входом элемента И 3, второй вход которого подключен к тактовой шине 7, Выходы элементов И

2 и 3. подключены к входам элемента

ИЛ! 4, выход которого соединен с входом счетчика 16 и с тактовым входом сдвигового регистра 14. Входная шина 8 подключена к .входу элемента

ИЛИ .!3 и к входам входных элементов

И 9, другие входы которых подключены к выходам .счетчика 16. Выходы входных элементов И 9 соединены со счетными входами триггеров 10, выходы . которых соединены соответственно с входами вторых элементов И 6, другие входы которых обьединены и подключены к выходу элемента И 5 и к счетному входу триггера ll, выход которого соединен с входом выходного элемента И 12, другие входы которого соединены с соответствующими выходами счетчика !6.. Кроме того, прямые выходы счетчика 16 подключены к входам элемента И 5. Вход сумматора 15 соединен с выходом выходного элемента И

12, другой вход которого подключен к выходу последнего разряда регистра 14, первый разряд-которого через элемент ИЛИ 13 соединен с выходом сумматора !5.

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

В исходном состоянии все триггеры

10 и 11 устройства находятся в нуле51709 4 вом состоянии. Посылка двоичных сим= волов, закодированная в коде Хемминга, поступает одновременно на все входные элементы И 9, в то.же время через элемент HJIH 13,.спустя 11 -тактов, число которых определяется длиной декодируемой посылки, она записывается в сдвиговый регистр 14.Счетчик 16 осуществляет подсчет тактовых !

0 импульсов, поступающих íà его счетный вход через открытый элемент И 2 (триггер 11 в нулевом состоянии) и элемент ИЛИ 4. В зависимости от состояния счетчика 16 изменяются режимы работы входных элементов И 9.

Рассмотрим случай, когда иэ линии связи поступают символы кода Of Q q ь а z где О, а е 04 - npo

Верочные а q Q g Q g o у информацион ные разряды кода.

Состояние прямых выходов счетчика

16 приведено в табл. 1.

Исходя из вышеуказанной табл. первый элемент И 9 пропустит симво- лыа, а а а7,второй -а а аба третий — а4.сМ а ь а г. Полученные символы полностью соответствуют симво- . лам, находящимся в уравнениях проверок кода Хемминга. Далее разделенные символы поступают на счетные входы соответствующих триггеров 10, которые позволяют осуществить операцию

50 сложения по модулю 2 и запомнить результат сложения. Каждому сочетанию состояний триггеров 10 соответствует двоичное число, называемое синдромом ошибки, которое указывает номер по55 врежденного разряда.

Состояние элементов памяти после вычисления синдрома приведены я табл. 2.! 05 l 709

Таблица 2

l а, О+ а ® а О а

2 а, 9 ci„O а 6 з

3 Q4® о> 9

Процесс декодирования происходит .в два цикла. В первом цикле происходит вычисление синдрома, во втором — 15 коррекция принятой комбинации. Конец цикла определяется при помощи элемента И 5, Как только на всех прямых выходах счетчика 16 появятся единичные значения, элемент И 5 откроется 20 и на следующем такте синдром ошибки, вычисленный при помощи триггеров 10 через вторые элементы И 6, запишется в инверсном коде в счетчик 16. Одновременно триггер 11 устанавливается 25

s единичное состояние, тем самым элемент И 2 открывается, а элемент И 3 запирается, и на счетный вход счетчика 16 поступают импульсы от генератора 1 импульсов. Во втором цикле Зп счетчик 16 осуществляет подсчет импульсов, поступающих от генератора импульсов. Частота генератора им пульсов выбирается много больше, чем частота тактовых импульсов. Тем самым значительно сокращается время второго цикла и значительно.повышается быстродействие устройства для декодирования двоичных кодов Хемминга в целом.

Если синдром ошибки отличен от О, т.е. в канале связи произошло искажение символа на !! -ой позиции, то через !! -тактов, считая такт записи в счетчик 16, на выходе выходного элемента И 12 появится .логическая "1".

Полученный вектор ошибки суммируется по модулю 2 при помощи сумматора 15 с принятой кодовой посылкой. Далее исправленная кодовая посылка через элемент ИЛИ 13 записывается в информационный сдвиговый регистр 14. Таким образом, осуществляется коррекция одиночной ошибки.

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

105 I 709

Составитель С.. Кривуценко

- Редактор О, Сопко Техред И. Гергель Корректор И. Эрдейи

Заказ 8674j57 Тиран 93б Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал IlllTl "Патент", г. Ужгород, ул. Проектная, 4