Устройство для декодирования двоичных кодов Хэмминга Советский патент 1987 года по МПК H03M7/04 

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

Цель изобретения - повышение надежности устройства путем его упрощения, а также повьпнение его быстродействия.

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

Устройство содержит вход 1, решающий блок 2, элемент ИЛИ 3, первый- шестой элементы И 4-9, первый 10 и второй 11 регистры сдвига, ключи 12,

группу 13 элементов И, группу 14триг-15 ной иг1формации, т.е. во второй ре- геров, первый 14 и второй 16 счетчики импульсов, первьй 17 и второй 18 триггеры, сумматор 19, тактовую шину 20 -и выходы 21 устройства.

гистр 11 сдвига записывается только одна единица. Одновременно информация, подлежащая записи в первый регистр 10 сдвига, поступает на один

На фиг.2 представлена схема решаю-20 из входов элемента И 8. На другой

щего блока.

Блок 2 состоит из компараторов 22 и 23, элемента НЕ 24, элемента И 25 и RS-триггера 26.

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

В исходном состоянии триггеры 17 и 18 устройства находятся в нулевом состоянии.

Посылка двоичных символов закоди- рования в коде Хэмминга поступает с входа 1 устройства на вход решающего блока 2. При помощи решающего блока 2 осуществляется разделение приходящей из линии связи комбинации на две: комбинацию ошибок типа стирание и принятую комбинацию, у которой стертые позиции заменены нулями.

Декодирование последовательности состоит из трех циклов: цикла приема информации, обнаружения двойной ошибки и исправления стертого разряда, цикла вычисления синдрома одиночной ошибки и цикла исправления одиночных ошибок типа трансформация.

Так как триггер 17 находится в нулевом состоянии, то элемент И 4 открыт и тактовые импульсы поступают с шины 20 на тактовые входы первого 10 и второго 11 регистров сдвига, при П.ОМОЩИ которых осуществляется запись информации, поступающей с выходов решающего блока 2, причем в регистр 10 сдвига записывается последовательность, у которой стертые разряды заменены нулями, а в регистр 11 сдвига записывается последовательность, у которой единица стоит на первой стер

тон позиции, а на -остальных позициях стоят нули. Это происходит следующим образом. Как только на выходе первого разряда второго регистра 11 сдвига появляется уровень 1, означающий, что в принимаемой последовательности есть ошибка типа стирание, дальнейшая запись во второй регистр 11 сдвига ошибок типа стирание прекращается, так как сигнал, поступающий с первого разряда регистра 11 на управляющий вход решающего блока 2, устанавливает на втором выходе решающего блока уровень О независимо от входной иг1формации, т.е. во второй ре-

гистр 11 сдвига записывается только одна единица. Одновременно информация, подлежащая записи в первый регистр 10 сдвига, поступает на один

вход этого элемента поступают тактовые импульсы, подсчет которых осуществляется при помощи счетчика 16 им- тульсов. При помощи элемента И 8 исходит, формирование паузы между информационными символами. Далее информационная последовательность поступает на счетный вход триггера 18. Необходимость в формировании пауз вы30 звана тем, что противном случае при наличии в информационной последовательности двух и более единиц, стоящих подряд, триггер 18 воспринимает их как один импульс, так как он ра35 ботает по фронту входных сигналов. Триггер 18 производит подсчет числа единиц, записанных в регистр 10 сдвига. Конец первого цикла определяется при помощи элемента И 5. Как только

40 на всех прямых выходах счетчика 16 импульсов появляются уровни 1, элемент И 5 открывается, триггер 17 устанавливается в единичное состояние, а элемент И 4 закрывается. В резуль45 тате прекращается поступление тактовых импульсов на тактовые входы регистров 10 и 11 сдвига и, соответ- ствен но,сдвиг информации в них. Если число единиц, записанных в первый ре50 гистр 10 сдвига к концу первого цикла,, нечетное, то на инверсном выходе триггера 18 появляется уровень О, элемент И 9 закрывается и на следующем такте не происходит перезаписи

55 информации, записанной во втором регистре 11 сдвига, в первый регистр 10 сдвига. Если число единиц четное, то на инверсном выходе триггера 18 к концу первого цикла сохраняет313

ся уровень 1, который поступает на один 43 входов элемента И 9

I

На следующем такте второй счетчик 16 импульсов устанавливается в нулевое состояние, на выходе элемента И 6 появляется уровень 1, который приводит к тому, что на выходе элемента И 9 также устанавливается уровень 1. Вследствие этого открываются ключи 12 и 1, записанная в регистре 11 сдвига, переписывается в соответствующий разряд первого регистра 10 сдвига. Таким образом происходит коррекция ошибки типа стирание.

Далее по заднему фронту сигнала, поступающего с выхода элемента И 6, триггер 17 устанавливается в нулевое состояние. Элемент И 4 открывается, и тактовые импульсы вновь начинают поступать на тактовые входы первого 10 и второго 11 регистров сдвига, в результате чего осуществляется сдвиг информации в них вправо. Информационная последовательность, записанная в регистре 10 сдвига, выталкивается из него и поступает на один из входо сумматора 19 и на объединенные между собой входы группы 13 элементов И Так как на выходе элемента И 7 нахо- дится сигнал, равньй О, то информационная последовательность с поступлением тактовых импульсов без изменения перезаписывается через элемент ИЛИ 3 в первый регистр 10 сдвига. Одновременно в зависимости от состояния счетчика 16 импульсов изменяются режимы работы группы 13 элементов И, которые осуществляют разделение символов двоичного кода Хэм- минга. Разделенные символы поступают на счетные входы группы 14 триггеров которые позволяют осуществить операцию сложения по модулю два и запомнить результат сложения. Каждому со- четанию состояний триггеров группы 1 соответствует синдром ошибки, которы указывает номер повреждения разряда. После вычисления синдрома ошибки импульсом, снимаемым с выхода элемента И 6, состояния триггеров группы 14 переписываются в инверсном коде в счетчик 15 импульсов, который начинает подсчет тактовых импульсов третьего цикла Если синдром отличен от нуля, т.е. в канале связи произошла ошибка типа трансформация на п-й позиции, то через п тактов, считая такт записи в счетчик 15 импульсов, на

,

5 „ ,, Q

5

934

выходе элемента И 7 появляется уровень 1. Полученный вектор ошибки суммируется по модулю два при помощи сумматора 19 с поступающей с выхода первого регистра 10 сдвига информационной последовательности. Затем исправленная кодовая посылка через элемент ИЛИ 3 вновь записывается в регистр 10 сдвига.

Формула изобретения

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

ходы первого регистра сдвига являются выходами устпойства.

2, Устройство по п,1, отличающееся тем, что решающий блок выполнен на двух компараторах, RS- триггере и элементах И и НЕ, первые входы компараторов объединены и подключены к входу решающего блока,, а вторые входы соединены с шинами соответствующих источников порогового напряжетшя, выход первого компаратора соединен с первым выходом решающего блока и через элемент НЕ - с первым входом элемента И, второй вход которого подключен к выходу второго компаратора, третий вход - к инверсному выходу RS-триггера, а выход - к второму выходу решающего блока, уп- равляюищй вход которого соединен с S-входом RS-триггера,,

г

Изобретение относится к автоматике и вычислительной технике. Его использование в аппаратуре передачи данных по каналу с помехами позволяет повысить ее быстродействие и надежность за счет упрощения устройства. Устройство для декодирования двоичных кодов Хэмминга содержит решающий блок, регистры сдвига, группу триггеров, сумматор, счетчики импульсов, ключи, элементы И, группу элементов И и элемент ИЛИ, Благодаря соответствующим соединениям этих блоков устройство упрощается, а вычисление синдромов ошибок и коррекция последних ускоряются. 1 з.п. ф-лы, 2 ил. оо о vl сл Х оо

фи.2

Редактор Л.Огар

Составитель Л.Захарова Техред А.Кравчук

Заказ 1642/56Тираж 902Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое, предприятие, г. Ужгород, ул. Проектная, 4

Корректор Т.Колб