УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ КОДА ХЭММИНГА Советский патент 1973 года по МПК G06F11/10 

1

Изобретение относится к области иьмислительнои техники и может быть использовано в цифровых вычислительных машинах, обрабатывающих информацию, поступающую по линиям связи.

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

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

Для этого предлагаемое устройство декодирует со скоростью несколько разрядов (одна группа) за один такт двухфазного тактирования, при этом экономно используется оборудование по сравнению с устройством параллельного комбинационного декодирования.

Предлагаемое устройство использует принцип совмещения этапов обработки информации при котором одновременно обрабатывается несколько последовательных групп разрядов. Чтобы реализовать алгоритм декодирования в виде поэтапной сов.мещепной обработки, правило декодировапия кода Хэммипга сфор.мулировапо следующи.м образом; результатом декодирования (набором контрольных разрядов) сообщения произвольной длины является сумма по mod 2 (свертка) номеров тех разрядов сообщения, которые равны единице.

Следствием такой формулировки является следующее: для декодирования группы Из нескольких разрядов необходимо свернуть (суммировать по mod 2) соответствующие номера разрядов в группе. При этом каждая группа разрядов начинается с разряда, номер которого в двоичном виде записывается как уп

... 00, где число нулей определяется как , где число разрядов в группе, а г/г - произвольные значения: либо О, либо 1, тогда номера разрядов в группе будут записываться следующим образом:

у„у„ 1r/j 00О,

001,

г/„У«-1г/, 11 ,... 1,

или другими словами, старшие части номеров разрядов одни и те же для всех разрядов группы.

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

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

У„У,г-1i/,

Если число единиц в группе четное, то результат свертки старших частей

00.... 00

Для получения свертки младших частей номеров разрядов обозначим значение разрядов в группе, как

, а2«-2, . . . «и «01 перепишем номера разрядов в двоичном виде

;«П. . .. П , 1110 , . . .«00.. ..01 , «00. .. .00.

Обозначим результат свертки младшей части номеров разрядов Vj, где / номер разряда результата.

Тогда

00 ... 00 - / (.00 . . . 00, СОО . . . 01, «00 ... И,

-ОО ... 101 .. ) СО . . . 01 / ( ... 01, «00 ... 10, У-йО ... и,

«00... но...),

00 ... 10 / (XQQ ... 10. «00. . . 100, ЯОО. . . 101,

«00 ... по),

где I - функция свертки, Xi есть разряд результата свертки младшей части для предыдупдих групп.

па ф-иг. 1 приведена блок-схема устройства для декодирования кода Хэмминга; на фиг. 2 представлена временная диаграмма работы устройства.

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

, 00.... 00, 00. ...01, 00... .10 и т. д.,

..где к первому коитрольному разряду отно сится разряд с номером 00 ... 01; устройство содержит также счетчик 3, содержащий старшую часть разрядов номера разряда в сообщеник, т. е. представляющий номер группы, выбираемый из сообщения через дешифратор 4 на регистр,5; первую схе.му светрки 6, реализующую свертку старшей части номеров разряда, с первым входом которой через регистр 7, являющийся промежуточным буфером для счетчика, соединен счетчик 3. Со вторым входом схемы соединен выход второй схемы свертки 8. Последняя указывает четное или нечетное число единиц в выбраной на ре-гистр -5 группе -разрядов, с третьим входом которой через регистр Я являющийся проме4

жуточным буфер.о.м для результата свергни старшей части номера разряда сообщения, соединен выход первой схе.мы свертки; значение разрядов на выходе первой схемы свертки 6 либо представляет старое з ачение регистра Я если выход второй схе.мы сзертки 8 говорит о том, что в выбранной группе разрядов четное число единиц, либо свертку (сумму по mod 2) нового значения счетчика и

старого значения регистра Я представляющего предыдущий результат свертки; третью схему свертки 10, реализующую свертку младщих частей номеров разрядов, с первым входом которой, соединен выход регистра 5,

на последнем находится выбранная дешифратором группа разрядов, со вторым входом которой соединен регистр 11,- являющийся промежуточным буфером для результата свертки младшей части номера разряда; значение

разрядов выхода третьей схемы свертки представляет описанную функцию Uj выход третьей схемы свертки 10 и первой схемы свертки 6 соединен с выходом 12 устройства декодирования.

Динамика работы схемы показана на вре.менной диаграмме работы устройства декодирования кода Хэмминга (см. фиг. 2), где номера графиков соответствуют но.мерам блоков на ф:иг. 1, приведены двухфазные тактирующие сигналы и отмечены моменты времени ti, tz-.-tis- Для конкретности применены следующие параметры устройства: длина сообщения не более 100 разрядов, число контрольных разрядов не.более 7, скорость декодирования составляет 4 разряда за один такт. В таком случае сче/чик 3, регистры 7, 9 имеют длину по пять разрядов. Регистр 5 имеет соответственно длину четыре разряда. Регистр 11 имеет длину два разряда. В начальный момент / счетчик 3 выберет на регистр 5 первые 4 разряда, соответственно содержимое счетчика 00000, в момент ta содержимое счетчика 3 передается на регистр 7 и в то же время становится равным 00001. В момент /з выход схемы свертки 8 равен единице, если свертка (сумма по mod 2) разрядов регистра 5 равна единице, в этот же момент на выходе схемы свертки JO установится результат по следующему правилу:

U, f(x,,j.,,a,},

и 3 -- I 2 -з)

где L/i, f/2 - разряды выхода схемы 10;

Ко, ссь az, аз-разряды регистра 5;

f - функция свертки.

В момент 4 на регистре 5 установится вторая четверка разрядов из сообщения, т. е. с 5 по 8-й разряды, и выход схемы свертки 6

есть свертка (сумма по mod 2) 7 и 5 регистров, если состояние выхода схемы свертки 8 есть «1, если же состояние выхода схемы 8 есть «О, то выход схе.л1Ы свертки 6 равен содержимому регистра 9. В момент /4 состояние счетчика 3 равно 00010, состояние регистpa 7 равно 00001, a состояние регистра 9 равно состоянию выхода схемы свертки 6 в предыдущий момент. Таким образом в момент 5 на регистрах 9 10 хранится результат обработки первой четверки разрядов и на выходе схемы свертки 8 устанавливается свертка (сумма по niod 2) .второй четверки и на регистре 7 номер этой четверки. Далее все повторяется аналогично до тех пор, пока последняя четверка разрядов сообщения не пройдет через схему сварки 6 и результат декадирования сообщения в этот момент оказывается, на регистрах 9 и //.

Предмет изобретения

Устройство для декодирования кода Хэмминга, содержащее приемный регистр, схемы

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

B/off

( Г -J

/

iL

у

М

Фиг /

7-

58

(5

9

W

П --

t1 t2 tJ tfy tS t6 t7 t8 t9 tlO tn tJ2 tIJ

Фи,.2