Декодер укороченного кода хэмминга

Декодер укороченного кода хэмминга

Иллюстрации

Показать все

Реферат

 

ДЕКОДЕР УКОРОЧЕННОГО КОДА ХЭММИНГА, содержащий операционный регистр, регистр остатка и дешифратор , отличающийся тем, что, с целью упрощения декодера путем исключения блоков элементов И и элементов ИЛИ,блока управления, блоков ввода и вьтода информации, в него введены последовательно соединенные преобразователь кода, регистр циклического сдвига и первый блок сумматоров по модулю два, а также второй блок сумматоров по модулю два, выход которого является выходом декодера, при этом к первому входу второго блока сумматоров по модулю два подключен выход дешифратора , к входу которого и второму входу первого блока сумматоров по модулю два подключен выход регистра остатка , первый вход которого объединен с входом операционного регистра и является входом декодера, а к второму входу регистра остатка подключен выход первого блока сумматоров по моду;по два, при этом операционный регистр содержит V регистров, выход каждого 1 -го из которых (, i 3, ..., V ) подключен к входу (-1)го регистра и к соответствующему вхосл ду второго блока сумматоров по модулю два, а выход первого регистра операционного регистра подключен к входам V -го регистра, преобразователя кодов и второго блока сумматоров по модулю два. со со к 4

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСГ1УБЛИК

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

IlO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3534969/18-09 (22) 06.01.83 (46) 23.08.84. Бюл. 11 31 (72) А.В.Маркарян и Л.M.×àõoÿí (53) 621.394.14(088.8) (56) 1. Авторское свидетельство СССР

Ф 318939, кл. G 06 F 5/02, 1969.

2. Авторское свидетельство СССР

Ф 669357, кл. С 06 F 11/10, 1975. (прототип). (54)(57) ДЕКОДЕР УКОРОЧЕННОГО КОДА

ХЭММИНГА, содержащий операционный регистр, регистр остатка и дешифратор, отличающийся тем, что, с целью упрощения декодера путем исключения блоков элементов И и элементов ИЛИ,блока управления, блоков ввода и вывода информации, в него введены последовательно соединенные преобразователь кода, регистр циклического сдвига и первый блок сумматоров по модулю два, а также второй блок сумматоров по моду„,Я0„„1109924 A

З 51) Н 04 Е 1/10//G 06 F 11/12 лю два, выход которого является выходом декодера, при этом к первому входу второго блока сумматоров по модулю два подключен выход дешифратора, к входу которого и второму входу первого блока сумматоров по модулю два подключен выход регистра остатка, первый вход которого объединен с входом операционного регистра и является входом декодера, а к второму входу регистра остатка подключен выход первого блока сумматоров по модулю два, при этом операционный регистр содержит Ч регистров, выход каждого 1 -ro из которых (1 = 2, 3, ..., L/ ) подключен к входу ((-1)- Я

ro регистра и к соответствующему вхо— ду второго блока сумматоров по модулю два, а выход первого регистра опе- ( рационного регистра подключен к входам Ч -ro регистра, преобразователя р кодов и второго блока сумматоров по

@в модулю два.! 1109

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

5 между устройствами внутри вычислительной машины.

Известно устройство для декодирования кода с коррекцией одиночных ошибок, содержащее регистр с фиксированными цепями сложения по модулю два порождающего полинома (1j, Недостатком устройства является низкое быстродействие.

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

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

Недостатком известного устройства является его сложность из-за исполь- . .зования N -разрядного приемного ре30 гистра (где Ф вЂ” число информационных разрядов), блоков элементов И и ИЛИ, блоков ввода и вывода информации.

Цель изобретения — упрощение декодера путем исключения блоков элемен- 5 тов И и элементов ИЛИ, блока управления, блока ввода и вывода информации.

Для достижения поставленной цели в декодер укороченного кода Хэмминга,40 содержащий операционный регистр, регистр остатка и дешифратор, введены последовательно соединенные преобразователь кода, регистр циклического сдвига и первый блок сумматоров по модулю два, а также второй блок сумматоров по модулю два, выход которого является выходом декодера, при этом к первому входу второго блока сумматоров по модулю два подключен выход дешифратора, к входу которого и второму входу первого блока сумматоров по модулю два подключен выход регистра остатка, первый вход которого объединен с входом операционно- 55

ro регистра и является входом декодера, а к второму входу регистра остатка подключен выход первого блока

924 2 сумматоров по модулю два, при этом операционный регистр содержит V регистров, выход каждого 1 -го из которых (1 = 2,3,..., V ) подключен к входу (1 -1)-го регистра и к соответствующему входу второго блока сумматоров по модулю два, а выход первого регистра операционного регистра подключен к входам Ч -го регистра, преобразователя кодов и второго блока сумматоров по модулю два.

На чертеже. приведена структурная электрическая схема предлагаемого декодера.

Декодер содержит операционный регистр 1, состоящий из V регистров 1.1-1. V, регистр 2 остатка, преобразователь 3 кода, регистр 4 циклического сдвига, первый и второй блоки 5 и 6 сумматоров по модулю два, дешифратор 7.

Предложенный декодер предназначен для декодирования кодов Хэмминга, укороченных за счет сокращения числа ин-. формационных символов таким образом, чтобы число К информационных символов после укорочения было кратно числу ,tn избыточных символов исходного кода Хэмминга (2 — 1, 2 — 1 — н ).

В этом случае коды Хэмминга (31, 26) и (127, 120) укорачиваются до вида (30,25) и (126,119), например до вида (30, 25): .к

1 0000

0000.1

С4С С С4С

00011

11111

01111 а

„„а„а„а„„а, 01.1 11

00011

00000

1 1 1 1 1

10101 ьа а а а

0101

01111

00011

00000

11111

Г2 R3 24

111

0101

1111

001 1

„а а а,а

0000, 1111

01 01

1111

001 1 ьауаВа9а

5 г

При этом проверочная матрица укороченного кода Хемминга представляетсяв виде Н = )1, h„: Ь : .... h„, где 3 — единичная матрица, а под3 11099 матрицы Ьд Ь|(составлены путем циклического сдвига строк матрицы Ьл.

Декодер укороченного кода Хэмминга функционирует на основе следующих предпосылок.

Согласно теории кодирования основной задачей при декодировании кода Хэмминга является вычисление полинома остатка (кода номера искаженного разряда) посредством выражения 10 т

S = (Сл... С„„а .... Я(,) Н, (1) где S полином остатка, 1 Сл...С - контрольные разряды кодового блока; ак...аз{ в информационные разряды", Т вЂ” знак транспонирования матрицы, Н вЂ” проверочная матрица кода.

Выбрав Н = jD h . h ... h ) такам образом, чтобы h2 ... hv образо- 20 вывались от h„ посредством циклических сдвигов строк в h получаем выражение

V-(-, 25

Оа(О» ..Cêl g(a«+„...ца! „{.6 „(д( аО где А = К/m.

Откуда, используя циклическую за;висимость подматриц Ь „, формирование S в устройстве производится в

Ч. тактов. Причем в каждом такте сначала производится вычисление значе1

1 ()) 35 затем — 5 циклических сдвигов вправо результата произведения (а р „ ... т а „(„)) h1 и подстановка полученного значения в выражение (2) . Например, для случая К = 25, m = 5

А = 5, е сли требуется вычислить энат алл алр алр, +14 erts )

= .(10111)т Ь = (00011), достаточно вычислить: (алл ал ялз ало алз )

Т т л

=(10111) 11 = (01100) и произвесл 45 ти = 2 циклических сдвига вправо.

Вычисление S u его дешифрация в устройстве производится следующим образом.

Предполагается, что функция синхронизации и управления устройством

50 возложены на блок управления (не показан).

В первом такте с входа 8 декодера контрольный код (С A ... С,„) записывается в регистр 2 остатка, а информационный код ) а „... а «) — в операционный регистр 1, причем в каждый из регистров 1.1 — 1 записывает24 4 ся А-разрядный код в следующей последовательности: в регистр 1.1 код (а, ... Я„), в регистр 1.2— кОД (а(Л, cl 2A ) и т Д С ВыхОДОВ регистра 1.1 информация в параллельном виде поступает на входы преобра зователя 3 кода, который вырабатывает код согласно (а(... Яф{ h и выдает ф1 е го н а вх оды ре гис тра 4 ци кличе с ко го сдвига. Первый такт заканчивается приемом информации с выходов преобразователя 3 кода в регистр 4, суммированием информаций в параллельном коде с выходов регистра 4 циклического сдвига и регистра 2 остатка в блоке 5 сумматоров по модулю два и записью результата суммирования через другие входы в регистр 2 остатка. В результате по окончании первого такта в регистре 2 остатка зафиксировано значение (Сл ... С() +

Т т

+ (а„ ... Яд)

Во втором такте производится параллельная циклическая перезапись информаций регистров 1.1-1.V через их другие входы, т.е. информация регистра 1.1 записывается в регистр 1.V, информация регистра 1.2в регистр 1.1 и т.д. Далее посредством регистра 1.1 и преобразователя 3 кода производится аналогично предыдущему такту формирование значения (Я,1 ф л ° Я2A ) Ь, и прием еГО В Ре

Т гистр 4 циклического сдвига, после чего производится = 1 циклических сдвигов информации в регистре 4 циклического сдвига и аналогично предыдущему такту запись результата суммы в регистр 2 остатка. В результате в регистре 2 остатка фиксируется значение (Сл ... Сш) + (а „... aA ) +

+ (а аацз оаз i iЯ 2Д)

)т

Последующие такты до V-го включительно производятся аналогично второму лишь с той разницей, что количество циклических сдвигов регистра 4 пропорционально возрастает согласно выражению (2).

Таким образом, в V-ом такте в регистре 2 остатка зафиксировано значение S по выражению (2), а в операционном регистре 1 — информация (а„ ... а((), которая с выходов регистров 1.1-1.V поступает на входы блока 6 сумматоров по модулю два, на другие входы которого с выходов дешифратора 7 поступает дешифрированное значение S, указывающее номер

1109924 неисправного разряда в информации (а„ ... ак).

В результате на выход 9 декодера выдается скорректированная блоком 6 сумматоров по модулю два информация.

Например, для случая К = 25, m = 5, если в операционный регистр 1 вместо исправной информации, т.е. когда $ = 0 согласно (1), (С

С а .... а ), где С„= С = С вЂ” а = а = ам= а о= а 5= 1, в подматрицах проверочной матрицы укороченного (30,25) кода Хэмминга отмечены зна-, ком",записана та же информация,но с ошибочным значением и < = 1 (отмечена 15

М знаком р ), то в первом такте в регистре 2 остатка зафиксировано значение (11100) + (00010) . ? „ — (i 1100) + (101 10) -- (01010) ; во т Т втором — значение (01010) + (00010) х 20 х h с одним циклическим сдвигом вправо второго слагаемого, т.е ° (01010) +

+ (00010) h = (01010) + (01011) т (QQOQ1 ), в третьем значение (00001) + (00100) - h„ ) = 2 цикли- Zs ческим сдвигом вправо второго слагаемого, т.е. (00001) + (00100) h = (00001) + (00111) = (00110)

Аналогично в последующих тактах: в четвертом †. значение (00110) + зр

6 (00001) h4 (00110) + (11011) т (11101), в пятом — значение (11101) + (10001) . hz = (11101) +

+ (01100) = (10001)

В ре зультате в последнем, пятом, такте в регистре 2 остатка хранится полином остатка, соответствующий ошибке в разряде а „, а на выходах дешифратора 7 выработан корректирую щий сигнал в позиции, соответствующей разряду а>, Преимуществом предлагаемого декодера является его упрощение. Слож" ность введенных блоков пропорциональна числу контрольных разрядов m. В известном устройстве использованы элементы И и ИЛИ, а также приемный регистр, у которых сложность пропорциональна числу информационных разрядов К, Учитывая, что величина К для кодов Хэмминга растет быстрее,чем величина m, сокращение сложности аппаратуры в предлагаемом декодере тем знаI чительнее, чем больше значение К.

Для К = 119 при использовании, например, микросхем серии 155, достигается сокращение примерно 25Х оборудования, что составляет порядка 45-50 микросхем.

ВНИИПИ Заказ 6103/43 Тираж 635 Попаисное

Фхлхее ППП Потеет, г. Укгорох,рл.Проехтхех, 4