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

 

Изобретение относится к автоматике и вычислительной технике. Его использование в аппаратуре передачи данных по каналу с помехами позволяет повысить информативность декодирования. Устройство содержит решающий блок 1, регистры 2, 3 сдвига, счетчики 6, 7, триггеры 8, 9, группу триггеров 10, сумматор 11, элементы 13-16 И, группу элементов 17 И и элемент 18 ИЛИ. Благодаря введению регистров 4, 5 сдвига и сумматора 12 в устройстве реализуется конвейерная обработка информации, позволяющая втрое повысить количество декодируемой в единицу времени информации без снижения помехозащищенности уа. 2 ил.

(1) 4 H 03 М 13/02

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

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ 1 " @".,1;г..g

ПА1Е1П113 - 1Е .";.ЛЕ "= г.ЛЛ

E : ÁË 1G Ег А

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

Г1РИ ГННТ СССР (21) 4319839/24-24 (?2) ?2.10.87 (46) 23.05.89. Бюл. М 19 (71) Новосибирский электротехнический институт (72) В.С.Давыдов, A.Á.Æóêîâ и С.В.Обухон (53) 681,325(088.8) (56) Авторское свидетельство СССР

Р 1150771, кл. Н 03 М 7/04, 1984.

Авторское свидетельство СССР

YP 1307593, кл. Н 03 М 7/04, 1985. (54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ

ДВОИЧНЫХ КОДОВ ХЭММИНГА (57) Изобретение относится к автоматике и вычислительной технике. его

„„SU„„1481903 А 1 использование в аппаратуре передачи данных по каналу с помехами позволяет повысить информативности декодирования. Устройство .содержит решающий блок l регистры 2, 3 сдвига, счетчики 6, 7, триггеры 8, 9, группу триггеров 10, сумматор 11, элементы

13-16 И, группу элементов 17 И и элемент !6 ИЛИ. Благодаря введению регистров 4, 5 сдвига и сумматора 12 в устройстве реализуется коннейерная обработка информации, позволяющая втрое повысить количество декодируемой в единицу времени информации без снижения помехоэащищенности устройства. 2 ил. з 1481903 4

1О

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

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

На фиг.! изображена функциональная схема устройства; на фиг.2, — решающий блок..

Устройство для декодирования двоичных кодов Хэмминга содержит фиг,1 решающий блок 1, первый — четвертый регистры 2-5 сдвига, первый 6 и второй 7 счетчики, первый 8 и второй 9 триггеры, группу триггеров 10, первый 11 и второй 12 сумматоры, первыйчетвертыи элементы И 13-16, группу элементов И 17, элемент ИЛИ 18, информационный 19 и тактовый 20 входы.

Решающий блок 1 аналогичен известiioìó решающему блоку и содержит (фиг ° 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 сдвига записывается последовательность, у которой единица стоит на первой стертой позиции, а на остальных позициях стоят нули, )то пpnnc ходит следующим образом. КаК тс лько на выходе первого разряда второго ре-1 гистра 3 появляется уровень логической 1, означающий, что в принимаемой последовательности есть ошибка типа стирание, дальнейшая запись во второй регистр 3 сдвига ошибок типа стирание прекращается, так как сигнал, поступающий с первого разряда регистра 3 на управляющий вход 27 решающего блока 1, устанавливает триггер 23 в "1", элемент И 25 закрывается и на втором выходе-29 решающего блока 1 устанавливается уровень логического "0" независимо от входной информации.

Одновременно информация, подлежа-. щая записи в первый регистр 2 сдвига, поступает на один иэ входов пе-.ваго элемента И !3, на другой вход которого поступают тактовые импульсы с входа 20, подсчет последних осуществляется счетчиком Ь, При помощи элемента И !3 происходит формирование паузы между информационными символами. Далее информационная последовательность поступает на счетньй вход триггера 8, Необхоцимость в формировании пауз вызвана тем, что в протинном случае при наличии в информационной последовательности двух и более единиц, стоящих подряд, триггер 8 воспринимает их как один импульс, так как триггеры со счетным входом работают по фронту входных сигналов, Сумматор 11 производит под счет по модулю два числа единиц,записанных в регистр 2 сдвига. Конец цикла приема определяется при помощи элемента И, когда на всех выходах счетчика 6 появляются уровни логической "1". Элемент И 1А срабатывает и в триггер 9 записывается состояние триггера 8. Если число единиц, запи-. санных в первый регистр 2 сдвига, нечетное,, то триггер 9 устанавливается в единичнсс состояние, а если четное — то в нулевое. Состояние триг— гера 9 определяет режим работы элемента И !6, ",.àçðåøàåò прохождение информации, записанной в регистре 3 сдвига на суммирование сумматором с информацией, поступающей с вЫходa регистра ? сдвига.

Регистры 2 и 3 сдвига содержат п+! ячейку памяти, где и — длина принятой последовательности. На следую1481903

Разделенные символы поступают на счетные входы триггеров, которые позволяют осуществить операцию сложения по модулю два и запомнить результат сложения. Каждому сочетанию состояний триггеров соответствует синдром ошибки, который указывает номер поврежденного разряда. После вычисления синдрома ошибки импульсом, снимаемым с выхода логического элемента И 14, состояния триггеров 10 переписываются в инверсном коде в счетчик 7, который начинает подсчет тактовых импульсов. Если синдром отличен от нуля, т.е. в канале связи произошла ошибка типа трансформация на i-й позиции, та через i тактов, считая такт записи в счетчик 7, на выходе логического элемента И 15 появляется уровень логической "1". Полученный вектор ошибки суммируется по мадулю два при помощи сумматора

12 с поступающей с выхода регистра 4 сдвига информационной последовательностью и запись ее в регистр 5 сдвига.

Рассмотрим процесс декодирования на примере, когда устройство рассчитано на прием информационных последовательностей, имеющих следующий вид.

110100)

1010)01

0110011

0001111

1010101

Аналогично происходит коррекция одиночной ошибки типа стирание.

Рассмотрим, как осуществляется

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

00X0)0) (трансформирована "1" пер45 ваго разряда и стерта 1 третьего ес гф разряда). Тогда в регистр 2 записывается комбинация 0000101, а в регистр 3 — комбинация 0010000. Так как в комбинации, записанной в ре50 гистр 2, находится четное количество единиц, та триггер 8 к концу цикла приема находится в нулевом состоянии, а триггер 9 — в единичном. Эле55 мент И 16 открь!вается последовательность, записанная в регистре 3, суммируется с последовательностью, записанной в регистре 1, при помощи сумматора 11: щем такте счетчик 6 устанавливается в нулевом состояние, элемент ИЛИ 18 срабатывает и устанавливает триггеры 10 в исходное состояние. Последующими тактовыми импульсами производится выталкивание кодовой поA следавательнасти из регистров 2 и 3 через сумматор ll на объединенные между собой входы элементов И 17 и запись ее в регистр 4 сдвига. В зависимости от состояния счетчика 6 изменяются режимы работы элементов

И 17 группы, которые осуществляют разделение символов двоичного кода

Хэмминга.

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

Пусть в последовательности вида

1010101 происходит одиночная ошибка типа трансформация. Предположим, что трансформивался первый разряд. Тогда в первый 2 и второй 3 регистры сдвига записываются комбинации

0010101 и 0000000 соответственно. Состояние триггера 8 в данном варианте безразлично, так как в регис-.ре 3 записана нулевая комбинация. Затем начинается цикл вычисления синдрома одиночной ошибки, Б этом цикле информация, записан15 ная в первом регистре 2 сдвига, последовательно выталкивается из него через сумматор )1 при помощи тактовых импульсов, и записывается в регистр 4 сдвига. Од повременна происха20 дит разделение символов информационной последовательна< ти элементами И

17 согласно уравнениям проверок и вычисление синдрома ошибки (100) триггерами 10. Далее вычисленный синдром

25 в инверсном виде (n» ) записывается

Во второй счетчик 7 пс сигналу с выхода элемента И 14. Затем при помощи второго счетчика 7 и элемента И 15 определяется вектор ошибки 1000000

30 и производится коррекция принятой кодовой посылки при помощи сумматора

12:

0010101

1000000!

481903

0000101

0010101

Допустим, принятая последователь-. ность имеет вид 001 «101 (трансформирована l первого разряда и происходит стирание 0" четвертого разряда) . Тогда в регистр 2 записывается последовательность 0010101, а в регистр 3 — последовательность

0001000. Триггер 8 находится в единичном состоянии, а триггер 9 в нулевом, так как в регистре 2 записана последовательность, содержащая нечетное количество 1

t I I I

Так как триггер 9 находится в нулевом состоянии, то элемент 15 закрыт и суммирования инфорации, записанной в регистрах 2 и 3 сдвига, не производится, Коррекция ошибки типа стирание происходит при помощи решающего блока l.

Допустим, принятая последователь- 25 ность имеет вид ХОХ0101. Тогда в регистр 2 записывается комбинация

0000101, а в регистр 3 — комбинация

1000000, Триггер 8 остается в нулевом состоянии, а триггер 9 устанавли- 30 вается в единичное, тем самым разре" шая последовательное суммирование кодовых последовательностей, записанных в первом 2 и втором 3 регистрах сдвига сумматором 11:

0000101

1000101

В данной информационной последовательности имеется только одиночная ошибка, которая корректируется в дальнейшем аналогично рассмотренному примеру.

Пусть информация имеет вид 1 «1 "

»101 (происходит стирание двух нулевых сигналов). Тогда в регистр 2 записывается последовательность вида

1010101, а в регистр 3 — последовательность 0100000. Триггер 9 устанавливается в единичное состояние, разрешая суммирование KopoBblx последовательностей регистров 2 и 3 сдвига сумматором ll:

1010101

1110101

В данной информационной последовательности имеется только одиночная ошибка, которая корректируется в дальнейшем аналогично рассмотренному примеру.

Таким образом, из анализа корректирующей способности устройства видно, что предлагаемое устройство способно исправлять точно такое же количество ошибок, как и известное устройство, при этом информативность устройства при декодировании увеличивается. Под информативностью декодирования понимается количество декодируемой информации, отнесенной по времени декодирования. Анализ известного устройства показывает, что устройство может декодировать только одно информационное слово за три .цикла декодирования в силу того, что в информационный регистр. и регистр стираний в циклах вычисления синдрома ошибки информацию записывать нельзя.

В предлагаемом устройстве декодирование производится также в три цикла.

Но использование конвейерного декодирования позволяет производить запись информации в регистр 3 и информационный регистр 2 в каждом цикле декодирования беэ нарушения работоспособности устройства.

Следовательно, количество информации, подлежащей декодиров" íèþ,,за то же время может быть увеличено в три раза.

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

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

r тактовым входом устройства, выходы первого счетчика подключены, к соответствующим входам второго элемента

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

148!903 версный выход первого триггера соединен с информационным входом второго триггера, выход второго элемента

И подключен к управляющему входу Вто рого счетчика и входу синхронизации второго триггера, прямой выход которого и последовательный выход второ— го регистра сдвига соединены с первым и вторым входами четвертого элемента И, выход которого подключен к второму входу первого сумматора, выход которого соединен с информацион2О

Со с т ав и т ель 0. Р ев инский

Редактор M.Нланар expep M,ÄÈät Корректор Т.Малец

Заказ 2702/57 Тираж 885 Подписное

BHHHHH Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

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