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

 

Союз Советскнк

Соцналистнчесник республик

О П И С А Н И E (940299

ИЗОВРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЮЛЬСТ8У (61} Дополнительное к авт. сеид-ву (22) Заявлено 16.12.80 (2 l ) 3220084/18-21 (5t)M. Кл.

Н 03 К 13/24 с присоединением заявки М

Рвудерстеенны1 комнтет

СССР нв денем неебретенне н открытей (23) Приоритет (53) УДК621. .374(088.8) Опубликовано 30.06.82. Бюллетень № 24

Дата опубликования описания 30.06.82 (72) Авторы изобретения

В. С. Давыдов и А. Б. Жуков

Новосибирский электротехнический инстй Ч, (7I ) Заявитель (54) УСТРОЙСТВО LUIH ДЕКОДИРОВАНИЯ

ДВ ОИЧН ЫХ К ОДОВ XE М МИН ГА

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

Известное устройство для декодирова5 ния двоичных кодов Хемминга, содержашее регистр сдвига, сумматоры по модулю 2, входы которых связаны с ячейками регистра сдвига в соответствии е уравнениями проверок, и дешифратор про- >и верок, входные шины которого соединены с выходами соответствуюших сумматоров по модулю 2, а выходные шины — со счетными входами соответствукецих ячеек регистра сдвига (1 1 . !

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

2, количество входов у которых эави« сит от длины декодируемого слова. Ðåà2 лизация сумматоров по модулю 2 с болт шим числом входов представляет значи» тельную сложность из-за использования большого количества логических схем при построении многовходовых сумматоров по модулю 2. Использование дешиф ратора проверок, формируюшего вектор для исправления ошибок, значительно усложняет устройство, так как с увеличением длины декодируемой посылки увеличивается число схем совпадений, на которых построен дешифратор проверок, а кроме того, возникает необходимость в использовании многовходовых схем совпадений (23.

Наиболее близким по техн ч сущности к предлагаемому является уст рэйство для. декодирования двоичных ко дов. Хемминга, содержащее счетчики, триггеры, входные элементы И, гуммвтор, элемент ИЛИ, выходной элемент И, и сдвиговой регистр, тактовый вход которого соединен с шиной тактирования, 940299 кроме того, счетный вход первого счетчика соединен с шиной тактирования и со счетным входом второго счетчика, а каждый из выходов подключен к одному из входов соответствующего входного 5 элемента И, выход которого соединен со счетным входом одноименного триггера, нулевой выход которого подключен к одному из разрядных входов второго счетчика, нулевой выход первого разряда и 10 единичные выходы последующих разрядов которого соединены с входами выходного элемента И, выход которого подключен к одному из выходов сумматора, другой вход которого соединен с выходом послед-1

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

Однако известное устройство имеет достаточную сложность реализации, обус- ловленную тем, что в устройстве используется два счетчика, а это приводит к дополнительным усложнениям при построении устройств для декодирования двоичных кодов Хемминга.

Цель изобретения — упрощение устроьства для декодирования двоичных кодов Хемминга.

Поставленная цель достигается тем, 35 что в устройство для декодирования двоичных кодов Хемминга, содержащее счетчики, триггеры, входные элементы И, сумматор, элемент ИЛИ, выходной элемент

И и сдвиговый регистр, тактовый вход

40 которого соединен с шиной тактирования, и к этой же шине тактирования подключен вход счетчика, каждый из выходов которого соединен с одним из входов соответствую пего входного элемента И, выход кото 5 рого соединен со счетным входом одноименного триггера, а выход выходного элемента И подключен к одному из входов сумматора, другой вход которого соединен с выходом последнего разряда сдвигового регистра, а выход подключен к одному из

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

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

На чертеже приведена блок-схема предлагаемого устройства для декодирования двоичных кодов, например, с длиной слова, равной 7.

Устройство для декодирования двоичных кодов Хемминга содержит тактовую шину 1, первый счетчик 2, первый дополнительный элемент И 3, другие дополнительные элементы И 4, информационную входную шину 5, вхопные элементы И 6, триггеры 7, дополнительный триггер 8, выходной элемент И 9, элемент ИЛИ 10, с цвиговый регистр 1 1, сумматор 1 2, причем тактовые выходы счетчика 2 и сдвигового регистра

l1 подключены к тактовой шине 1, а информационная шина 5 подключена к одному из входов элемента ИЛИ 10 и к соединенным между собой первыми входами входных элементов И 5, вторые входы которых подключены к одноименным единичным выходам счетчика 2, Выходы входных элементов И 5 соединены со счетными входами одноименных триггеров

7, нулевые выходы которых соединены соответственно с одними входами дополнительных элементов И 4, другие выходы которых обьединены и подключены к выходу первого дополнительного элемента И 3. Этот выход также подключен к счетному входу триггера 8, выход которого соединен с одним из входов выходного элемента И 9, первый вход которого соединен с нулевым выходом счетчика

2, а другие — с единичными. Кроме того, единичные выходы счетчика 2 подключены к входам первого дополнительного элемента И 3. Один вход сумматора 12 соединен с выходом выходного элемента

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

ИЛИ 10 соединен с выходом сумматора.

5 9- 02

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

В исходном состоянии все триггеры устройства находятся в нулевом состоянии (установка триггеров в "О на схе— ме не указана).

Посылка двоичных символов, закодированная в коде Хемминга, поступает одновременно на все входные элементы 10

И 6, в то же время через элемент ИЛИ

10, спустя И тактов, число которых определяется длиной декодируемой посылки, она записывается в сдвиговый регистр

1l. Счетчик 2 осуществляет подсчет 15 тактовых импульсов. В зависимости от состояния триггеров счетчика 2 изменяются режимы работы входных элементов И 6. Рассмотрим случай, когда из линии связи поступают символы кода 20

a4 a< а6 a, rge а а

7 х

a4 — проверочные информационйЫе разряды кода.

Состояние триггеров счетчика можно выразить в виде табл. 1

Таблицаl.

О

О

О

О

О

О

О

О

О

О

Исходя из данных табл. 1, элементы

И б пропускают соответственно симво45 лы а4 а> а а; à à аба; а+

Z Ъ а а0 а>

Полученные символы полностью соответствуют символам, находящимся в уравнениях проверок кода Хемминга. Далее

50 разделенные символы поступают на счетные входы одноименных триггеров 7, которые позволяют осуществить операцию сложения по модулю 2 и запомнить результат сложения. Каждому сочетанию состояний триггеров соответствует двои

i5 ное число, называемое синдромом ошибки, которое указывает номер поврежденного разряда. г < 6

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

:Т а блица 2 а /+/ а /+/ a /+/ а

4 3 5 7

2 а /+/ а /+/ a /+/ а

3 6 7

3 а4 /+/ а /+/ а /+/ а

Процесс декодирования происходит в два цикла. В первом цикле происходит вычисление синдрома, а во втором — коррекция принятой комбинации. Конец цикла определяется при помощи первого дополнительного элемента И 3. Как только на всех единичных выходах счетчика 2 появляются все единицы, элемент И 3 открывается и на следующем такте синдром ошибки, вычисленной при помощи триггеров 7, через элементы И 4 запишется в инверсном коде в счетчик 2.

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

И 3, устанавливает триггер 8 в единичное состояние, тем самым осуществляется подготовка к работе выходного элемента

И 9. Во втором цикле счетчик 2 также осуществляет подсчет тактовых импульсов.

Если синдром ошибки отличен от О, т,е. в канале связи произошло искажение . символа на pt-ой позиции, то через Yl тактов, считая такт записи в счетчик 2, на выходе выходного элемента И 9 появится логическая "1". Полученный вектор ошибки суммируется по модулю 2 при помощи сумматора 12 с принятой кодовой посылкой. Далее исправленная кодовая посылка через элемент ИЛИ 10 записывается в сдвиговый регистр 11.

Таким образом, осуществляется кор- рекция одиночной ошибки.

Рассмотрим процесс декодирования на конкретном примере.

Допустим передается посылка 10 10

101, закодированная в коде Хемминга, B результате действия помех и линии связи происходит ее искажение и на вход устройства приходит посылка 10

00 101.

Наиболее удобно процесс декодирования предстаь, ть в виде табл. 3, из которой видно, как происходит вычисление синдрома ошибки (110), запись его в инверсном виде (001} на восьмом такте во второй счетчик, определение вектора ошибки и коррекция принятой кодовой посылки.

940299

Т а блица 3

3 4

11 12

Вх, 1 0 0 0 1 0 1

1 0 1 0 1 0 1 0 1 0 1 0 1 On.

1 0 1 0 1 0 1 и

2 0 1 1 0 0 1 1< 0 0 1 1 0 0 1

3 0 0 0 1 1 1 1 1 1 1 1 0 1 1

Т

1 1 1 1 0 0 1

0 0 0 О 5 0

Т а

0 0 0 0 1 1 0

1 0 0 0 1 0 1

Вых.

С. Р.

0 0 1 0 0 0 0

Вых.

1 0 1 0 1 0 1

Вых.

С. М.

U„

Вых, 1 0 0 0 1 0 1

Вых 0 0 0 0 0 0 1

Вых. 0 0 0 0 1 0 1

С. Р.

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

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

Ъ двоичных кодов Хемминга, взятого за прототип, одного счетчика.

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

Введение же триггера соответствует исключению из счетчика одного триггера. г

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

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

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

15 выходу первого дополнительного элеменвыходов которого соединен с одним из та И входы которого соединены с едивходов соответствующего входного элеt ничными выходами счетчика, причем мента И, выход которого соединен со становочные входы счетчика подключены счетным входом одноименного триггера, У к выходам соответствукзцих дополниа выход выходного элемента И подключен к одному из входов сумматора, дру- 20 тель

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

1. Четвериков В. H. Преобразование подключен к входной шине, а выход — к 25 ча инфо мации в АСУ. М., "Высшая школа, 1974, с. 73. информационному входу сдвигового регистра, при этом другие о д угие входы вход- 2. Авторское свидетельство СССР по ных элементов И объединены и подключе- заявке % 2914442/18-24, 1Ч1И!!ПИ Заказ 4686/77 Тираж 959 Подписное

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