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

Союз СоветскнкСоцналистнческикРеспублик ОП ИСАНИЕИЗОВРЕТЕН ИЯК АВТОРСИОМУ СВИДЕТЕЛЬСТВУ и 940299(5М. Кл Н 03 К 13/24 с присоединением заявки М Рвудерстеенны 9 комнтет СССР нв делам наебретенне н вткрьпнй(72) Авторы изобретения В, С, Давыдов и А, Б, Жуков Новосибирский электротехнический инстйВЗ,(71) Заявитель(54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ ДВОИЧНЫХ КОДОВ ХЕММИНГА 1Изобретение относится к импульсной технике и может использоваться в аппаратуре передачи данных по каналу с помехами.Известное устройство для декодирова 5 ния двоичных кодов Хемминга, содержащее регистр сдвига, сумматоры по модулю 2, входы которых связаны с ячейками регистра сдвига в соответствии е уравнениями проверок, и дешифратор про- в верок, входные шины которого соединены с выходами соответствующих сумматоров по модулю 2, в выходные шины - со счетными входами соответствующих ячеек регистра сдвига1,5 Однако данное устройство имеет повышенную сложность реализации при декодировании информационных посылок большой длины. Сложность такого уст ройства обуславливается наличйем в схеме параллельных сумматоров по модулю 2, количество входов у которых эави сит от длины декодируемого слова. Реа 2лизация сумматоров по модулю 2 с болт шим числом входов представляет значи тельную сложность из-за использования большого количества логических схем при построении многовходовых сумматоров по модулю 2, Использование дешиф ратора проверок, формирующего вектор для исправления ошибок, значительно усложняет устройство, так как с увеличением длины декодируемой посылки увеличивается число схем совпадений, на которых построен дешифратор проверок, а кроме того, возникает необходимость в использовании многовходовых схем совпадений 23 Наиболее близким по технической сущности к предлагаемому является усъ рэйство для. декодирования двоичных ко дов. Хемминга, содержащее счетчики, триггеры, входные элементы И, гумматор, элемент ИЛИ, выходной элемент И, и сдвиговой регистр, тактовый вход кэторого соединен с шинойтактирования, 940299кроме того, счетный вход первого счетчика соединен с шиной тактирования и со счетным входом второго счетчика, а каждый из выходов подключен к одному из входов соответствующего входного 5 элемента И, выход которого соединен со счетным входом одноименного триггера, нулевой выход которого подключен к одному из разрядных входов второго счетчика, нулевой выход первого разряда и 1 О единичные выходы последующих разрядов которого соединены с входами выходного элемента И, выход которого подключен к одному из выходов сумматора, другой вход которого соединен с выходом послед Энего разряда сдвигового регистра, а выход подключен к одному из входов элемента ИЛИ, другой вход которого подключен ко входной шине, а выход - к информационному входу сдвигового регистра, при этом другие входы входных элементов И объединены и подключены к информационной входной шине.Однако известное устройство имеет достаточную сложность реализации, обус ловленную тем, что в устройстве используется два счетчика, а это приводит к дополнительным усложнениям при построении устройств для декодирования двоичных кодов Хемминга.30 Цель изобретения - упрощение устроьства для декодирования двоичных ко. дов Хемминга.Поставленная цель достигается тем,35 что в устройство для декодирования двоичных кодов Хемминга, содержащее счетчики, триггеры, входные элементы И, сумматор, элемент ИЛИ, выходной элемент И и сдвиговый регистр, тактовый вход40 которого соединен с шиной тактирования, и к этой же шине тактирования подключен вход счетчика, каждый из выходов которого соединен с одним из входов соответствую пего входного элемента И, выход кото 5 рого соединен со счетным входом одноименного триггера, а выход выходного элемента И подключен к одному из входов сумматора, другой вход которого соединен с выходом последнего разряда сдвигового регистра, а выход подключен к одному из50 входов элемента ИЛИ, другой вход которого подключен к входной шине, а выход - к информационному входу сдвигового регистра, при этом другие входы входных элементов И обьединены и подключены к информационной шине, введены четыре дополнительных элемента И и дополнительный триггер, счетный вход которого подключен к выходу первого дополнительного элемента И, а выход - к одному из входов выходного элемента И, первый вход которого соединен с инверсным вы ходом счетчика, а другие - с прямыми, кроме того, нулевые выходы триггеров подключены к вхопам одноименных доЦполнительных элементов И, другие входы которых обьединены и подключены к выходу первого дополнительного элемента И, входы которого соединены с единичными выходами счетчика, причем установочные входы счетчика подключены к выходам соответствующих дополнительных элементоь И, .На чертеже приведена блок-схема предлагаемого устройства для декодирования двоичных кодов, например, с длиной слова, равной 7.Устройство для декодирования двоичных кодов Хемминга содержит тактовую шину 1, первый счетчик 2, первый дополнительный элемент И 3, другие дополнительные элементы И 4, информационную вхопную шину 5, вхопные элементы И 6, триггеры 7, дополнительный триггер 8, выходной элемент И 9, элемент ИЛИ 10, с цвиговый регистр 1 1, сумматор 1 2, причем тактовые вы. ходы счетчика 2 и сдвигового регистра 11 подключены к тактовой шине 1, а информационная шина 5 подключена к одному из входов элемента ИЛИ 10 и к соединенным между собой первыми входами входных элементов И 5, вторые входы которых подключены к одноименным единичным выходам счетчика 2, Выходы входных элементов И 5 соединены со счетными входами одноименных триггеров 7, нулевые выходы которых соединены соответственно с одними входами дополнительных элементов И 4, другие выходы которых обьединены и подключены к выходу первого дополнительного элемента И 3, Этот выход также подключен к счетному входу триггера 8, выход которого соединен с одним из входов выходного элемента И 9, первый вход которого соединен с нулевым выходом счетчика 2, а другие - с единичными. Кроме того, единичные выходы счетчика 2 подключены к входам первого дополнительного элемента И 3, Один вход сумматора 12 соединен с выходом выходного элемента И 9, а другой подключен к выходу последнего разряда сдвигового регистра 1 1, первый разряд которого через элемент ИЛИ 10 соединен с выходом сумматора,5 9402Устройство для декодирования двоичных кодов Хемминга работает следующим образом.В исходном состоянии все триггеры устройства находятся в нулевом состоя нии (установка триггеров в "0" на схеме не указана).Посылка двоичных символов, закодированная в коде Хемминга, поступает одновременно на все входные элементы 10 И 6, в то же время через элемент ИЛИ 10, спустя И тактов, число которых определяется длиной декодируемой посылки, она записывается в сдвиговый регистр 11, Счетчик 2 осуществляет подсчет 5 тактовых импульсов, В зависимости от состояния триггеров счетчика 2 изменяются режимы работы входных элементов И 6, Рассмотрим случай, когда из линии связи поступают символы кода 20 а а а 5 а 4 а аЬ а, где7а - проверочные, а а 3 а аЬ аинформационййе разряды кода,Состояние триггеров счетчика можно выразить в виде табл. 1 Таблица 1.30 00 0 0 0350 00 0400О0Исходя из данных табл. 1, элементы И 6 пропускают соответственно симво 45 лы а 4 а а а; а а аьа; а+2 ЪПолученные символы полностью соответствуют символам, находящимся в уравнениях проверок кода Хемминга, Далее50 разделенные символы поступают на счетные входы одноименных триггеров 7, которые позволяют осуществить операцию сложения по модулю 2 и запомнить результат сложения, Каждому сочетанию состояний триггеров соответствует двоич5 ное число, называемое синдромом ошибки, которое указывает номер поврежденного разряда. г С 6 Состояния элементов памяти после вычисления синдрома приведены в табл. 2.:Т а блица 2 1 а /+/ а /+/ а /+/ а3 52 а /+/ а /+/ а /+/ а3 63 а 4 /+/ а /+/ аь /+/ аПроцесс декодирования происходит в два цикла, В первом цикле происходит вычисление синдрома, а во втором - коррекция принятой комбинации. Конец цикла определяется при помощи первого дополнительного элемента И 3, Как только на всех единичных выходах счетчика 2 появляются все единицы, элемент И 3 открывается и на следующем такте синдром ошибки, вычисленной при помощи триггеров 7, через элементы И 4 запишется в инверсном коде в счетчик 2,Сигнал, поступакхций с выхода элемента И 3, устанавливает триггер 8 в единичное состояние, тем самым осуществляется подготовка к работе выходного элемента И 9. Во втором цикле счетчик 2 также осуществляет подсчет тактовых импульсов.Если синдром ошибки отличен от О, т,е, в канале связи произошло искажение . символа на И-ой позиции, то через М тактов, считая такт записи в счетчик 2, на выходе выходного элемента И 9 появится логическая "1". Полученный вектор ошибки суммируется по модулю 2 при помощи сумматора 12 с принятой кодовой посылкой, Далее исправленная кодовая посылка через элемент ИЛИ 10 записывается в сдвиговый регистр 11.Таким образом, осуществляется кор- рекция одиночной ошибки.Рассмотрим процесс декодирования на конкретном примере.Допустим передается посылка 10 10 101, закодированная в коде Хемминга, В результате действия помех и линии связи происходит ее искажение и на вход устройства приходит посылка 10 00 101.Наиболее удобно процесс декодирования предстаь,ть в виде табл. 3, из которой видно, как происходит вычисление синдрома ошибки (110), запись его в инверсном виде (001) на восьмом такте во второй счетчик, определение вектора ошибки и коррекция принятой кодовой посылки.940299 8Т в блица 3 34 10 11 12 Вх, 1 О О О 1 О 1 1 О 1 О 1 О 1 О 1 О 1 О 1 Оп. 1 О 1 О 1 О 1 и 2 О 1 1 О О 1 1 О О 1 1 О О 1 3 О О О 1 1 1 1 1 1 1 1 О 1 1 Т 1 1 1 1 О О 1 О О О О Ю Т О О О О 1 1 О 1 О О О 1 О 1 Вых.С. Р. О О 1 О О О О Вых,И 1 О 1 О 1 О 1 Вых,С. М. Вых," 1 О О О 1 О 1 Вых.О О О О О О 1 Вых, О О О О 1 О 1С, Р. Включение в схему устройства для декодирования двоичных кодов Хемминга дополнительных элементов И и триггера позволяет упростить его без нарушения работоспособности в целом и без изменения технических характеристик. Упрощение достигается исключением из схемы устройства для декодирования двоичных кодов Хемминга, взятого за прототип, одного счетчика. Счетчик по своей структуре гораздо сложнее элементов И, которые являютсяодним из простейших элементов электронной техники, стоимость которых значительно уступает стоимости счетчика. Введение же триггера соответствует исключению из счетчика одного триггера,Ф Таким образом, изобретение значительно проще по сравнению с известными устройствами, кроме того, оно по стоимости будет гораздо дешевле, чем существующие устройства для декодирования двоичных кодов Хемминга. Особенно значительным этот фактор будет при декодирова9нии информационных посылок большойдлины. Устройство для декодирования двоичных кодов Хемминга, содержащее счетчики, триггеры, входные элементы И, сумматор, элемент ИЛИ, выходной эле 0 мент И и сдвнговый регистр тактовый вход которого соединен с шиной тактирования, и к этой же шине тактирования подключен вход счетчика, каждый из выходов которого соединен с одним из входов соответствующего входного элемента И, выход которого соединен со счетным входом одноименного триггера, а выход выходного элемента И подключен к одному из входов сумматора, дру гой вход которого соединен.с выходом последнего разряда сдвигового,регистра, а выход подключен к одному из входов элемента ИЛИ, другой вход которого подключен к входной шине, а выход - к информационному входу сдвигового регистра, при этом другие входы входных элементов И объединены и подключеИсточники информации,принятые во внимание при экспертизе1. Четвериков В, Н. Преобразованиеи передача информации, в АСУ. М.,"Высшая школа", 1974, с. 73.2. Авторское свидетельство СССР позаявке % 2914442/18-24,940299 1 Сны к информационной шине, о т л и ч аю ш е е с я тем, что, с целью упрощения устройства, в него введены четыредополнительных элемента И и дополниф о р м у л а и з о б р е т е н и я 5 тельный триггер, счетный вход которогоподключен к выходу первого дополнительного элемента И, а выход - к одному из входов выходного элемента И,первый вход которого соединен с инверсным выходом счетчика, а другие - с прямыми,.кроме того, нулевые выходы триггеров подключены к входам одноименныхдополнительных элементов И, другие входы которых объединены и подключены квыходу первого дополнительного элемента И, входы которого соединены с единичными выходами счетчика, причемустановочные входы счетчика подключенык выходам соответствующих дополнительных элементов И.