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

1 Изобретение относится к автоматике и вычислительной технике и может использоваться в аппаратуре передачи данных по каналу с помехами, Известно устройство для декодирования двоичных кодов Хемминга, содержащее счетчики, триггеры, входные элементы И, сумматор, элемент ИЖ, выходной элемент И и сдвиговый регистр l . Однако устройство характеризуется низким быстродействием, которое обус ловлено тем, что процесс декодирования осуществляется в два равных по времени цикла. В первом цикле происходит вычисление синдрома, во втором коррекция принятой комбинации. Наиболее близким техническим решением является устройство для декодарования двоичных кодов Хемминга, содержащее триггеры, входные элементы И, сумматор, элемент ИЛИ, выходной элемент И, первый элемент И, вто рые элементы И, дополнительный тригтер, сдвиговый регистр и счетчик, прямые выходы которого соединены с первыми входами соответствующих вход ных элементов И, выходы которых соединены со счетными входами соответст вующих триггеров, выход выходного элемента И подключен к входу сумматора, другой вход которого соединен с выходом последнего разряда сдвигового регистра, а выход подключен к входу элемента ИЛИ, другой вход кото рого подключен к входной шине, а выход - к информационному входу сдвигового регистра, тактовый вход которого соединен с входом счетчика, вто рые входы входных элементов И объеди нены и подключены к входной шине, счетный вход дополнительного триггера подключен к выходу первого элемента И, а прямой выход - к первому входу выходного элемента И, второй |вход которого соединен с инверсным выходом счетчика, а третий и четвертый - с соответствующими прямыми выходами счетчика, инверсные выходы Триггеров подключены к первым входам соответствующих вторых элементов И, вторые входы которых объединены и подключены к выходу первого элемента И,входы которого соединены с соответствующими прямыми выходами счет гЧика, а его установочные входы подключены к соответствутощим выходам элементов И 2 . 092 Недостатком этого устройства является низкое быстродействие, обусловленное тем, что процесс декодирования осуществляется в два равных по времени цикла. В первом цикле происходит вычисление синдрома, во втором - коррекция принятой комбинации. Цель изобретения - повьпвание быстродействия. Поставленная цель достигается тем, что в устройство для декодирования двоичных кодов Хеь1минга, содержащее триггеры, входные элементы И, сумматор, элемент ИЛИ, выходной элемент И. первый элемент И, вторые элементы И, дополнительный триггер, сдвиговый регистр и счетчик импуль;сов, прямые выходы которого соединены с первыми входами соответствующих входных элементов И, выходы к торьгх соединены со счетными входами соответствующих триггеров, выход выходного элемента И подключен к входу сумматора, другой вход которого соединен с выходом последнего разряда сдвигового регистра, а выход подключен к входу элемента; ИЛИ, другой вход которого подключен к входной шине, а выход к информационному входу сдвигового регистра, тактовый вход которого соединен с входом счётчика, вторые входы входных элементов И объединены и подключены к входной шине, счетный вход дополнительного триггера подключен, к выходу первого элемента И, а прямой выход - к первому входу выходного элемента И, второй вход которого соединен с инверсным выходом счетчика импульсов, а третий и четвертый - с соответствующими прямыми выходами счетчика импyльJCOв, инверсные выходы триггеров подключены к первым .выходам соответствующих вторых элементов И, вторые входы которьпс объединены И подключены к выходу йервого элемента И, входы которого сое(инены с соответствующими прямыми выходами счетчика импульсов, а его установочные входы подключены к со- : ответствующиМ выходам вторых элемен тов И, введены генератор импульсов, третий и четвертый элементы И и дополнительный элемент ИЛИ, выход которого подключен к тактовому входу двигового регистра, а его входы оединены с выходами третьего и четертого элементов И, причем первый ход третьего элемента И соединен с

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

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

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

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

В исходном состоянии все триггеры 10 и 11 устройства находятся в нулевом состоянии. Посылка двоичных сим- волов, закодированная в коде Хемминга, поступает одновременно на все входные элементы И 9, в то. же время

через элемент ИЛИ 13, .спустя ц -тактов, число которых определяется длиной декодируемой посылки, она записывается в сдвиговый регистр 14.Счетчик 16 осуществляет подсчет тактовых

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

Рассмотрим случай, когда из линии связи поступают символы кода ОТ а О а 4 а 5 о 6 а г , где а, а q; 04 - проверочные ;c3lj 015 6 г информационные разряды кода..

Состояние прямых выходов счетчика 16 приведено в табл. 1.

I

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

Состояние элементов памяти после вычисления синдрома приведены в табл. 2. $ Таблица 2 1 а,® а.() 05007 2 0-2 ФОс;® 3 ал ® Ос ® а. © 07 Процесс декодирования происходит в два цикла. В первом цикле происходит вычисление синдрома, во втором коррекция принятой комбинации. Конец цикла определяется при помощи элемен та И 5. Как только на всех прямых выходах счетчика 16 появятся единичные значения, элемент И 5 откроется и на следующем такте синдром ошибки, вычисленный при помощи триггеров 10 через вторые элементы И 6, запишется в инверсном коде в счетчик 16. Одновременно триггер 11 устанавливается в единичное состояние, тем самым эле мент И 2 открывается, а элемент И 3 запирается, и на счетный вход счетчи ка 16 поступают импульсы от генератора 1 импульсов. Во втором цикле счетчик 16 осуществляет подсчет им09«пульсов, поступающих CJT генератора 1 импульсов. Частота генератора 1 импульсов выбирается много больще, чем частота тактовых импульсов. Тем самым значительно сокращается время второго цикла и значительно повьтается быстродействие устройства для декодирования двоичных кодов Хемминга в целом. Если синдром ошибки отличен от О, т.е. в канале связи произошло искажение символа на Ц -ой позиции, то через И -тактов, считая такт записи в счетчик 16, на выходе выходного элемента И 12 появится логическая 1. Полученный вектор ошибки суммируется по модулю 2 при помощи сумматора 15 с принятой кодовой посылкой. Далее исправленная кодовая посылка через элемент ИЛИ 13 записывается в информационный сдвиговый регистр 14. Таким образом, осуществляется коррекция одиночной ошибки. Введение в устройство для декодирования двоичных кодов Хемминга генератора импульсов, дополнительньш элементов И и элемента ИЛИ позволяет значительно увеличить его быстродействие без нарушения работоспособности в целом.

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