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

(51) 4 Н 03 М 13/02 ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ПА 1 Е 1 П 1 д,. 1 Е;,ЛЕ" г.ЛЛ Б 1 БЛ 4 О1.44 ь ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГННТ СССР(71) Новосибирский электротехнический институт(56) Авторское свидетельство СССР Р 1150771, кл. Н 03 М 7/04, 1984.Авторское свидетельство СССР 6 1307593, кл. Н 03 М 7/04, 1985. (54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ ДВОИЧНЫХ КОДОВ ХЭММИНГА(57) Изобретение относится к автоматике и вычислительной технике. Его 801481903 А 1 использование в аппаратуре передачиданных по каналу с помехами позволяет повысить информативности декодирования. Устройство .содержит решающий блок 1, регистры 2, 3 сдвига,счетчики 6, 7, триггеры 8, 9, группутриггеров 10, сумматор 11, элементы13-16 И, группу элементов 17 И и элемент 6 ИЛИ. Благодаря введению регистров 4, 5 сдвига и сумматора 12 вустройстве реализуется конвейернаяобработка информации, позволяющаявтрое повысить количество декодируемой в единицу времени информациибез снижения помехозащищенности устройства. 2 ил.510 Изобретение относится к автоматике и вычислительной технике и может использоваться в аппаратуре передачиданных по каналу с помехами,Цель изобретения - повышение информативности декодирования.На фиг, изображена функциональная схема устройства; на фиг.2, - решающий блокУстройство для декодирования двоичных кодов Хэмминга содержит фиг,решающий блок 1, первый - четвертыйрегистры 2-5 сдвига, первый 6 и второй 7 счетчики, первый 8 и второй 9триггеры, группу триггеров 10, первый 11 и второй 12 сумматоры, первыйчетвертыи элементы И 13-16, группуэлементов И 17, элемент ИЛИ 18, информационный 19 и тактовый 20 входы,Решающий блок 1 аналогичен известному решающему блоку и содержит(фиг,2) первый 21 и второй 22 компараторы, триггер 23, элемент НЕ 24 иэлемент И 25, информационный 26 иуправляющий 27 входы, информационный (первый) выход 28 и выход 29 стираний (второй выход),Устройство для декодирования двоичных кодов Хэмминга работает следующим образом.В исходном состоянии счетчики 6и 7, регистры 2-5 сдвига и триггеры8-10 устройства находятся в н"евомсостоянии (установка триггеров в "0не указана и может производиться полюбому фронту синхросигнала, приходящего из линии связи).Посылка двоичных символов, закодированная в коде Хэмминга, поступа"ет на вход 26 решающего блока 1. Припомощи решающего блока 1 осуществляется разделение приходящей из линии связи комбинации на две: комбинацию ошибок типа стирание (выход 29)и принятую комбинацию, у которойстертые позиции заменены нулями выход 28 . Тактовые импульсы с входа20 поступают на тактовые входы первого 2 и второго 3 регистров сдвига,тем самым производится запись в нихинформации, поступающей с выходоврешающего блока 1, причем в регистре2 сдвига записывается принятая последовательность, у которой стертые разряды заменены нулями, а в регистр 3сдвига записывается последовательность, у которой единица стоит напервой стертой позиции, а на остальных Гоз ициях стоят нули)то и ровсходит следующим образом. Как толькона выходе первого разряда второго ре гистра 3 появляется уровень логической 1 , означающий, что в принимаемой последовательности есть ошибкатипа стирание, дальнейшая запись вовторой регистр 3 сдвига ошибок типастирание прекращается, так как сигнал, поступающий с первого разрядарегистра 3 на управляющий вход 27 решающего блока 1, устанавливает триггер 23 в "1", элемент И 25 закрывается и на втором выходерешающего блока 1 устанавливается уровень логического 10" независимо от входной информации.Одновременно информация, подлежащая записи в первый регистр 2 сдвига,поступает на один иэ входов пе-.вагоэлемента И 13, на другой вход которого поступают тактовые импульсы свхода 20, подсчет последних осуществляется счетчиком Ь, При помощи элемента И 13 происходит формированиепаузы между информационными символами. Далее информационная последовательность поступает на счетный входтриггера 8, Необхоцимость в формировании пауз вызвана тем, что в протинном случае при наличии в информационной последовательности двух и более единиц, стоящих подряд, триггер 8 воспринимает их как один импульс, так как триггеры со счетным входом работают по фронту входных сигналов, Сумматор 11 производит под счет по модулю два числа единиц,записанных в регистр 2 сдвига. Конеццикла приема определяется при помощиэлемента И, когда на всех выходахсчетчика 6 появляются уровни логической "1", Элемент И 14 срабатывает ив триггер 9 записывается состояниетриггера 8. Если число единиц, запи-.санных в первый регистр 2 сдвиганечетное то триггер 9 устанавливается в единичное состояние, а если четное - то в нулевое. Состояние триггера 9 определяет режим работы элемента И 16, разрешает прохождение информации, записанной в регистре 3 сдвига на суммирование сумматором с информацией, поступающей с вЫхода регистра 2 сдвига.Регистры 2 и 3 сдвига содержат и+1 ячейку памяти, где и - длина принятой последовательности. На следую481903 Разделенные символы поступают на счетные входы триггеров, которые позволяют осуществить операцию сложения по модулю два и запомнить результат сложения, Каждому сочетанию состояний триггеров соответствует синдром ошибки, который указывает номер поврежденного разряда, После вычисления синдрома ошибки импульсом, снимаемым с выхода логического элемента И 14, состояния триггеров 10 переписываются в инверсном коде в счетчик 7, который начинает подсчет тактовых импульсов. Если синдром отличен от нуля, т.е. в канале связи произошла ошибка типа трансформация на -й позиции, та черезтактов, считая .такт записи в счетчик 7, на выходе логического элемента И 15 появляется уровень логической "1". Полученный вектор ошибки суммируется по модулю два при помощи сумматора 12 с поступающей с выхода регистра 4 сдвига информационной последовательностью и запись ее в регистр 5 сдвига.Рассмотрим процесс декодирования на примере, когда устройство рассчитано на прием информационных последовательностей, имеющих следующий вид:0111100101101011001101101001101010101100110001111 351010101Аналогично происходит коррекцияодиночной ошибки типа стирание.Рассмотрим, как осуществляется 40коррекция двойной ошибки: одной ошибки типа трансформация и одной ошибки типа стирание. Допустим, принятаяпоследовательность имеет входООХ 0101 (трансформирована "1" перваго разряда и стерта 1 третьеговс гфразряда) . Тогда в регистр 2 з аписыв ает ся комбинация 0000 1 О 1 , а в регист р 3 - комбинация 00 1 0 00 О . Таккак в комбинации , записанной в регистр 2, находится четное количествоединиц, та триггер 8 к концу циклаприема находится в нулевом состоянии, а триггер 9 - в единичном. Эле мент И 16 открывается последовательность, записанная в регистре 3,суммируется с последовательностью,записанной в регистре 1, при помощисумматора 11; щем такте счетчик 6 устанавливается в нулевом состояние, элемент ИЛИ 1 Ь срабатывает и устанавливает триггеры О в исходное состояние. Последуюшими тактовыми импульсами производится выталкивание кодовой по следавательнасти из регистров 2 и 3 через сумматор 11 на объединенные между собой входы элементов И 17 и запись ее в регистр 4 сдвига. В зависимости от состояния счетчика 6 изменяются режимы работы элементов И 17 группы, которые осуществляют разделение символов двоичного кода Хэмминга. Рассмотрим все возможные варианты ошибок в принятой информационной последовательности и работу устройства при коррекции этих ошибок. Пусть в паследавател .насти вида1010101 происходит одиночная ошибка типа трансформация. Предположим, что трансформивался первый разряд, Тогда в первый 2 и второй 3 регистры сдвига записываются комбинации 0010101 и 0000000 соответственно. Состояние триггера 8 в данном варианте 10 безразлично, так как в регис-.ре 3 записана нулевая комбинация. Затем начинается цикл вычисления синдрома одиночной ошибки,Б этом цикле информация, записан ная в первом регистре 2 сдвига, последовательно выталкивается из него через сумматор 11 при помощи тактовых импульсов, и записывается в регистр 4 сдвига, Одновременна происха дит разделение символов инфармацион -ной последовательна ти элементами И 17 согласно уравнениям проверок и вычисление синдрома ошибки (100) триггерами 10, Далее вычисленный синдром 25 в инверсном виде (011) записываетсяво второй счетчик 7 пс сигналу с выхода элемента И 14. Затем при помощи второго счетчика 7 и элемента И 15 определяется вектор ошибки 1000000 30 и производится коррекция принятой ко.давай посылки при помощи сумматора 12:0010101100000000001000100000010101Допустим, принятая последователь-. ность имеет вид 001 10 трансформирована 1 первого разряда и происходит стирание 0 четвертого разряда) . Тогда в регистр 2 записывается последовательность 0010101, а в регистр 3 - последовательность 0001000. Триггер 8 находится в единичном состоянии, а триггер 9в нулевом, так как в регистре 2 записана последовательность, содержащая нечетное количество 11 иТак как триггер 9 находится в нулевом состоянии, то элемент 15 закрыт и суммирования инфорации, записанной в регистрах 2 и 3 сдвига, не производится, Коррекция ошибки типа стирание происходит при помощи решающего блока 1,Допустим, принятая последователь ность имеет вид ХОХ 0101, Тогда в регистр 2 записывается комбинация 0000101, а в регистр 3 - комбинация 1000000, Триггер 8 остается в нулевом состоянии, а триггер 9 устанавли вается в единичное, тем самым разре" шая последовательное суммирование кодовых последовательностей, записанных в первом 2 и втором 3 регистрах сдвига сумматором 11:35000010110000001000101В данной информационной последовательности имеется только одиночная ошибка, которая корректируется в дальнейшем аналогично рассмотренному примеру.Пусть информация имеет вид" 101 (происходит стирание двух нулевых сигналов). Тогда в регистр 2 записывается последовательность вида 1010101, а в регистр 3 - последовательность 0100000. Триггер 9 устанавливается в единичное состояние, разрешая суммирование кодовых последовательностей регистров 2 и 3 сдвига сумматором 1:101010101000001110101 В данной информационной последовательности имеется только одиночнаяошибка, которая корректируется вдальнейшем аналогично рассмотренномупримеру.Таким образом, из анализа корректирующей способности устройства видно, что предлагаемое устройство способно исправлять точно такое же количество ошибок, как и известное устройство, при этом информативностьустройства при декодировании увеличивается. Под информативностью декодирования понимается количество декодируемой информации, отнесенной повремени декодирования. Анализ известного устройства показывает, что устройство может декодировать только одно информационное слово за три .цикладекодирования в силу того, что в информационный регистр. и регистр стираний в циклах вычисления синдромаошибки информацию записывать нельзя,В предлагаемом устройстве декодирование производится также в три цикла,Но использование конвейерного декодирования позволяет производить запись информации в регистр 3 и информационный регистр 2 в каждом цикледекодирования беэ нарушения работоспособности устройства,Следовательно, количество информации, подлежащей декодированию, зато же время может быть увеличено втри раза.Формула изобретенияУстройство для декодирования двоичных кодов Хэмминга, содержащее решающий блок информационный вход которого является информационным входом устройства, первый и второй регистры сдвига, тактовые входы которых объединены, последовательный вы" ход первого регистра сдвига соединен с первым входом первого сумматора, первый и второй счетчики, счетные входы которых объединены с первым входом первого элемента И и являютсяттактовым входом устройства, выходы первого счетчика подключены, к соответствующим входам второго элемента И и первым .входам соответствующих элементов И группы, выходы которых соединены со счетными входами одноименных триггеров группы, инверсные1 ч 8903 версный выход первого триггера соединен с информационным входом второго триггера, выход второго элементаИ подключен к управляющему входу второго счетчика и входу синхронизациивторого триггера, прямой выход которого и последовательный выход второ -го регистра сдвига соединены с первым и вторым входами четвертого элемента И, выход которого подключен квторому входу первого сумматора, выход которого соединен с информацион 20 25 Составитель О,Ревинседактор М.Вланар Техред М.Дидык рректор Т.Ма 02/57Государств1 Заказ В НИИП Тираж 885ного комитета по изо035, Москва, Ж, Р Подписное етениям и открытиям при ГКНТ СССушская наб., д. 4/5 Производственно в издательск комбинат "Патент", г.ужгород, ул. Гагарина,101 выходы которых подключены к одноименным установочным входам второго счетчика, выходы которого соединены ссоответствующими входами третьегоэлемента И, четвертый элемент И, первый и второй триггеры и элемент ИПИ,информационный вход первого регистрасдвига объединен с вторым входом первого элемента И, выход котого соединен со счетным входом первого триггера, выход первого разряда второго регистра сдвига подключен к управляющему входу решающего блока, выходстираний которого соединен с информационным входом второго регистра сдвига, о т л и ч а ю щ е е с я тем,что, с целью повышения информативности декодирования, в устройствовведены второй сумматор и третий ичетвертый регистры сдвига, тактовыевходы которых объединены с тактовымвходом первого регистра сдвига иподключены к тактовому входу устройства, информационный вход первогорегистра сдвига подключен к информационному выходу решающего блока, инным входом третьего регистра сдвигаи вторыми входами всех элементов Игруппы, входы и выход элемента ИЛИподключены соответственно к соответствующим выходам первого счетчика ик входам обнуления всех триггеровгруппы, выход третьего элемента П ипоследовательный выход третьего регистра сдвига соединены с первым ивторым входами второго сумматора, выход которого подключен к информационному входу четвертого регистра сдвига, выходы которого являются выходами устройства.