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

383050

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Соастскин

Социалистикесних

Республик

Зависимое от авт. свидетельства _#_Заявлено 27.Х.1970 (№ 1486619/18-24) с присоединением заявки №

Приоритет

Опубликовано 23.V.1973. Бюллетень . е 23

Дата опубликования описания 27Х111.1973

М. Кл. G 06f 11/10

Комитет по делам изобретений и открытий ври Ссвете Министров

СССР

УДК 681.326.75(088.8) Авторы изобретения

В. Ф. Жиров, В. И. Смирнов и А. Л. Соколов

Заявитель

УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ КОДА

ХЭММИ НГА

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

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

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

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

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

Следствием |акой формулировки является следуюшее: для декодирования группы из не10 скольких разрядов необходимо свернуть (суммировать по mod 2) соответствующие номера разрядов в группе. При этом каждая группа разрядов начинается с разряда, номер которого в двоичном виде записывается как у... уаут00 ... 00, где число нулей определяется как 1очс2 ", где 2" число разрядов в группе, а у; — произвольные значения: либо О, либо 1, тогда номера разрядов в группе будут записываться следующим образом:

20 у,у i .... у, 00, ... О, у,у„,....g,00....1, уу т у 11 1

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

Будем рассматривать вместо общей свертки номеров разрядов свертку старшей части но30 меров разрядов и свертку младшей части но383050

УпУл-1 У1

Гогда

00.... 00, 00....0l, 00.... 10 и т. д., 1я — f (ха 1а 3)з

55 .60

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

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

00....00

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

2$i17 1 02т Р ... Я Rp перепишем номера разрядов в двоичном виде

P 11.... И, -И.... 10 ) . 00 ..; 01) >00.... 00

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

Uoo... оо = / (хоо... оо, <00... ои ооо ... и, 7.00... 101 ° ° ) э

U0o... o1 — / (хоо... о1, oo... 1о, oo... и>

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

3i3 жуточным буфером для результата свер ки старшей части номера разряда сообщения, соединен выход первои схемы свертки; значение разрядов на выходе цсриой схемы свертки 6 либо представляет старое значение регистра 9, если выход второй схемы свертки 8 говорит о том, что в выоранной группе разрядов четное число единиц, либо свертку (сумму по mod 2) нового значения счегчика и старого значения регистра 9, представляющего предыдущий результат свертки; третью схему свертки 10, реализующую свертку младших частей номеров разрядов, с первым входом которой. соединен выход регистра 5, на последнем находится выбранная дешифратором группа разрядов, со вторым входом которой соединен регистр 11,— являющийся промежуточным буфером для результата свертки младшей части номера разряда; значение разрядов выхода третьей схемы свертки представляет описанную функцию U; выход третьей схемы свертки 10 и первой схемы свертки б соединен с выходом 12 устройства декодирования.

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

t1, 4...11з. Для конкретности применены следующие параметры устройства: длина сообщения не более 100 разрядов, число контрольных разрядов не более 7, скорость декодирования составляет 4 разряда за одич такт.

В таком случае счегчик 8, регистры 7, 9 имеют длину по пять разрядов. Регистр 5 имеет соответственно длину четыре разряда. Регистр 11 имеет длину два разряда. В начальный момент t счетчик 8 выберет на регистр 5 первые 4 разряда, соответственно содержимое счетчика 00000, в момент 1З содержимое счетчика 8 передается на регистр 7 и в то же время становится равным 00001. В момент 4 выход схемы свертки 8 равен единице, если свертка (сумма по mod 2) разрядов регистра

5 равна единице, в этот же момент на выходе схемы свертки 10 установится результат по следующему правилу;

U, = f (х„ .„" ), где U1, Uz — разряды выхода схемы 10; ао, а1, а, аз — разряды регистра 5;

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

В момент 14 на регистре 5 установится вторая четверка разрядов из сообщения, т. е. с

5 по 8-й разряды, и выход схемы свертки б есть свертка (сумма по mod 2) 7 и 9 регистров, если состояние выхода схемы свертки 8 есть «1», если же состояние выхода схемы

8 есть «О», то выход схемы свертки 6 равен содержимому регистра 9. В момент 1„состояние счетчика 8 равно 00010, состояние регист5 ра 7 равно 00001, а состояние регистра 9 равно состоянию выхода схемы свертки 6 в предыдущий момент. Таким образом в момент

t5 на регистрах 9 и 10 хранится результат обработки первой четверки разрядов и на выходе схемы свертки 8 устанавливается свертка (сумма по mod 2) .второй четверки и на регистре 7 номер этой четверки. Далее все повторяется аналогично до тех пор, пока последняя четверка разрядов сообщения не пройдет через схему сварки 6 и результат декадирования сообщения в этот момент оказывается. на регистрах 9 и 11.

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

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

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

383050

t 7 tZ td tФ Ы iá 6 7 tä t9 fig t77 С72 t.7 3

Фив. 2

Составитель В. Крылова

Техред Е. Борисова 1(орректор E. Сапунова

Редактор E. Гончар

Типография, пр. Сапунова, 2

Заказ 2338/3 Изд. М 617 Тираж 647 Подписное

ЦНИИПИ 1(омитета по делам изобр тспий и открытий при Совете Министров СССР

Моски 1, Я(-35, Рауьпская наб., д. 415