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

Союз Соаетскин Социалистикеских РеспубликЗависимое от авт. свидетельства1/10 М, Кл. б Заявлено 27.Х,1970 ( 6619/18-24 с присоединением заявкиПриоритетОпубликовано 23,7.1973. Бюллетень .4Дата опубликования описания 27 Х 111,19 Комитет по делам аобретений и открыти при Ссвете Министров СССРК 681,326,75(088,8) Авторызобретсни В. ф. Жиров, В. И. Смирнов и А. Л. Соколов 3 аявител УСТРОЯ СТ Я ДЕКОДИР ХЭММИ т 11 А ИЯ К ния в виде поэтапной совмещенной обработки, правило декодирования кода Хэмминга сформулировано следующим образом: результатом декодирования (набором контрольных разрядов) сообщения произвольнон длины является сумма по тном 2 свертка) номеров тех разрядов сообщения, которые равны единице.Следствием акой формулировки является следуюшее: для декодирования группы из нескольких разрядов необходимо свернуть (суммировать по тном 2) соответствующие номера разрядов в группе. При этом каждая группа разрядов начинается с разряда, номер которого в двоичном виде записывается как уп у 2 У 100ОО, где число нулей определяется как 1 оч.2", где 2" число разрядов в группе, а у; - произвольные значения: либо О, либо 1, тогда номера разрядов в группе будут записываться следующим образом:. У,00,0, ,У,001, .У,111,Улус-тили другими разрядов од группы.Будем рас номеров раз меров разря ловами, и те ж ршие части номеро для всех разрядо Изобретение относится к области вы ислительнои техники и может быть использовано в цифровых вычислительных машинах, обрабатывающих информацию, поступающую по линиям связи. 5Известное у стройство для декодирования кода Хэмминга, содержащее приемный регистр, схемы сьертки, схему коррекции ошибки и цепи связи, имеет ряд существенных ограничений. Например, для длинных сообще ний использование данного устройства приводит почти к непреодолимым трудностям изза больших нагрузок на элементы.Цель изобретения состоит в построении быстродеиствующего устройства для декодиро вания кода Хэмминга, выполняющего операцию декодирования для доков произвольной длины, при экономном использовании оборудования.Для этого предлагаемое устройство декоди рует со скоростью несколько разрядов (одна группа) за один такт двухфазного тактирования, при этом экономно используется оборудование по сравнению с устройством параллдльного комбинационного декодирования. 25Предлагаемое устройство использует принцип совмещения этапов обработки информации при котором одновременно обрабатывается несколько последовательных групп разрядов. Чтобы реализовать алгоритм декодирова матривать вместо общей свертки ядов свертку старшей части ноов и свертку младшей части ноуулу Гогда 00, 00,00,01,00,10 и т. д.,1 я - Р (а аа аз)55 .60 65 3меров разрядов, учитывая значения разрядов в группе. Если число единиц в группе нечетное, то результат свертки старших частей Если число единиц в группе четное, то результат свертки старших частей0000 Для получения свертки младших частей номеров разрядов обозначим значение разрядов в группе, как а 2 - 1 а 2 2.а,аО перепишем номера разрядов в двоичном виде ап иац юаоо,. одаоо ооОбозначим результат свертки младшей части номеров разрядов Ь;, где 1 номер разряда результата. Уоо оо = 1(гоо оо, аоо оь аоои,аооо )Ьооо= 1 (хооо, аооо, аооцаоо по. ),Соо го - ) (хоо о аоо оо аоо тоаоо по),где- функция свертки, Х; есть разряд результата свертки младшей части для предыдущих групп.па фиг. 1 приведена блок-схема устройствадля декодирования кода Хэмминга; на фиг. 2представлена временная диаграмма работыу строиства.о строиство декодирования состоит из приемного регистра 1, принимающего из О,эо через вход 2 слова, составляющие сооощение, ирасширенного на один нулевой разряд, значение которого равно нулю для того, чтобы впервой выбранной из сообщения группе полу"чить разряды с номерами где к первому контрольному разряду относится разряд с номером 0001; устройство содержит также счетчик 8, содержащий старшую часть разрядов номера разряда в сообщении, т. е. представляющий номер группы, выбираемый из сообщения через дешифратор 4 на регистр 5; первую схему светрки 6, реализующую свертку старшей части номеров разряда, с первым входом которой через регистр 7, являющийся промежуточным буфером для счетчика, соединен счетчик 8. Со вторым входом схемы соединен выход второй схемы свертки 8. Последняя указывает четное или нечетное число единиц в выбраной на ре.гистр 5 группе разрядов, с третьим входом которой через регистр 9, являющийся проме 5 10 15 20 25 30 35 40 45 д жуточным буфером для результата свероки старшей части номера разряда сообщения, соединен выход первои схемы свертки; значение разрядов на выходе цсриой схемы свертки 6 либо представляет старое значение регистра 9, если выход второй схемы свертки 8 говорит о том, что в выоранной группе разрядов четное число единиц, либо свертку (сумму по гпос 1 2) нового значения счегчика и старого значения регистра 9, представляющего предыдущий результат свертки; третью схему свертки 10, реализующую свертку младших частей номеров разрядов, с первым входом которой соединен выход регистра 5, на последнем находится выбранная дешифратором группа разрядов, со вторым входом которой соединен регистр 11, - являющийся промежуточным буфером для результата свертки младшей части номера разряда; значение разрядов выхода третьей схемы свертки представляет описанную функцию 11,; выход третьей схемы свертки 10 и первой схемы свертки б соединен с выходом 12 устройства декодирования.Динамика работы схемы показана на временной диаграмме работы устройства декодирования кода Хэмминга (см. фиг. 2), где номера графиков соответствуют номерам блоков на фиг. 1, приведены двухфазные тактирующие сигналы и отмечены момепть; времени 1 ь Ь 2 1 з. Для конкретности применены следующие параметры устройства: длина сообщения не более 100 разрядов, число контрольных разрядов не более 7, скорость декодирования составляет 4 разряда за одич такт.В таком случае счегчик 8, регистры 7, 9 имеют длину по пять разрядов. Регистр 5 имеет соответственно длину четыре разряда. Регистр 11 имеет длину два разряда, В начальный момент 1 счетчик 8 выберет на регистр 5 первые 4 разряда, соответственно содержимое счетчика 00000, в момент 12 содержимое счетчика 8 передается на регистр 7 и в то же время становится равным 00001. В момент 1 з выход схемы свертки 8 равен единице, если свертка (сумма по гпоо 2) разрядов регистра 5 равна единице, в этот же момент на выходе схемы свертки 10 установится результат по следующему правилу;1, = Р(х) где Ьи 02 - разряды выхода схемы 10; ао, а а 2, аз - разряды регистра 5;- функция свертки.В момент 14 на регистре 5 установится вторая четверка разрядов из сообщения, т, е. с 5 по 8-й разряды, и выход схемы свертки б есть свертка (сумма по гпой 2) 7 и 9 регистров, если состояние выхода схемы свертки 8 есть 1, если же состояние выхода схемы 8 есть О, то выход схемы свертки 6 равен содержимому регистра 9, В момент 1 состояние счетчика 8 равно 00010, состояние регист 5ра 7 равно 00001, а состояние регистра 9 равно состоянию выхода схемы свертки 6 в предыдущий момент. Таким образом в момент 15 на регистрах 9 и 10 хранится результат обработки первой четверки разрядов и на выходе схемы свертки 8 устанавливается свертка (сумма по гпод 2) второй четверки и на регистре 7 номер этой четверки. Далее все повторяется аналогично до тех пор, пока последняя четверка разрядов сообщения не пройдет через схему сварки 6 и результат декадирования сообщения в этот момент оказывается. на регистрах 9 и 11. Предмет изобретенияУстройство для декодирования кода Хэмминга, содержащее приемный регистр, схемы 3830506свертки, буферные регистры и дешифратор, отличающийся тем, что, с целью повышения быстродействия устройства, в него введен счетчик, выход которого соединен с первым5 входом дешифратора и через первый буферный регистр - с первым входом первой схемы свертки, со вторым входом которой соединен выход второй схемы свертки, а с третьим входом через второй буферный регистр - вы ход первой схемы свертки, выход приемногорегистра соединен со вторым входом дешифратора, выход которого через третий буферный регистр соединен с входом второй схемы свертки и с первым входом третьей схемы 15 свертки, второй вход которой через четвертыйбуферный регистр соединен с ее выходом, выходы первой и третьей схем сверток соединены с выходом устройства.383050Ф адиева О 7 ЕЯ М СФ Сб б 7 1 д С 9 Е 70 С 77 С 72 С 7 ДФив. 2Составитель В. Крыловаактор Е. Гончар Техред Е. Борисова Корректор Е. СапуноваЗаказ 2338/3 ИзтФ 617 Тираж 647 Подписное ЦНИИПИ Комитета по делам изобрзтспий и открытий при Совете Министров СССР МоскваК, Рауьпская наб., д. 45поирафия, пр. Сапунова, 2