Декодер укороченного кода Хэмминга Советский патент 1984 года по МПК H03M13/51 G06F11/08 H04L17/30 

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

Известно устройство для декодирования кода с коррекцией одиночных ошибок, содержащее регистр с фиксирован-,Q ными цепями сложения по модулю два порождающего полинома l3 Недостатком устройства является низкое быстродействие. Наиболее близким к изобретению по технической сущности является дек дер кода Хэмминга, содержащий опера-ционный регистр, регистр остатка и д шифратор, а также блоки элементов И и элементов ИЛИ, блок управления, блоки ввода и вьгаода информации. Известньй декодер предназначен для коррекции одиночных ошибок в информации с высокой скоростью вычисления полинома остатка, что Достигается совмещенией во времени операций сложения определенных групп разрядов в операционном регистре 2. Недостатком известного устройства является его сложность из-за использования m -разрядного приемного регистра (где tn - число информационных разрядов), блоков элементов И и ИЛИ, блоков ввода и вьшода информации. Цель изобретения - упрощение деко дера путем исключения блоков элементов И и элементов ИЛИ, блока управления, блока ввода и вывода информации. Для достижения поставленной цели в декодер укороченного кода Хэмминга содержащий операционный регистр, регистр остатка и дешифратор, введены последовательно соединенные преобразователь кода, регистр циклического сдвига и первый блок сумматоров по модулю два, а также второй блок сумматоров по модулю два, выход которого является выходом декодера, при этом к первому входу второго блока сумматоров по модулю два подключен выход дешифратора, к входу которого и второму входу первого блока сумматоров по модулю два подключен выход регистра остатка, первый вход которого объединен с входом операционного регистра и является входом декоде ра, а к второму входу регистра остатка подключен выход первого блока

сумматоров по модулю два, при этом операционный регистр содержит V регистров , выход каждого -го из которых (1 2,3,.,., V) подключен к входу (i-l)-ro регистра и к соответствующему входу второго блока сумматоров по модулю два, а выход первого регистра операционного регистра подключен к входам V -го регистра. преобразователя кодов и второго блока сумматоров по модулю два. На черт.ежр приведена структурная электрическая схема предлагаемого декодера. Декодер содержит операционный регистр 1, состоящий из V регистров 1.1-1.V, регистр 2 остатка, преобразователь 3 кода, регистр 4 циклического сдвига, первый и второй блоки 5 и 6 сумматоров по модулю два, дешифратор 7. Предложенный декодер предназначен для декодирования кодов Хэмминга, укороченных за счет сокращения числа информационных символов таким образом, чтобы число К информационных символов после укорочения было кратно числу ,1Т1 избыточных символов исходного кода Хэмминга (2 - 1 , 2 - 1 - m ) . В этом случае коды Хэмминга (31, 26) и (127, 120) укорачиваются до вида (30,25) и (126,119), например до вида (30, 25): При этом проверочная матрица укороченного кода Хемминга представляется в виде Н la 1 h h, .; .... h у;, где - единичная матрица, а подматрицы hj, ..., hy составлены путем циклического сдвига строк матрицы h. Декодер укороченного кода Хэмминга функционирует на основе следующих предпосылок. Согласно теории кодирования основной задачей при декодировании кода Хэмминга является вычисление полинома остатка (кода номера искаженного разряда) посредством вьфажения S (С... а)- Н, (1) где S - полином остатка; |С... контрольные разряды кодового блока; аЛ - информационные разряды - знак транспонирования матрицы; Н - проверочная матрица код Выбрав Н З : h ; h,... hy такам образом, чтобы h, ... hy образовывались от h посредством.циклических сдвигов строк в h , получаем вьфажение v-t 5--(с,...с,ЛХ{о| ли-.,{2) где А К/т. Откуда, используя циклическую за;висимость подматриц h , формирование S в устройстве производится в V тактов. Причем в каждом такте сна чала производится вычисление значения ( (41) затем - I циклических сдвигов вправ результата произведения (а,ц ... л(1t 1 и подстановка полученного значения в выражение (2). Например, для случая К 25, m 5, А 5, если требуется вычислить зна чение ( а а,4 h - .(lOni)f-hj (00011), достаточно вычислить: (а а а ) h (10111) h, (01100) и произвести t 2 циклических сдвига вправо. Вычисление S и его дешифрация в устройстве производится следующим образом. Предполагается, что функция синхронизации и управления устройством возложены на блок управления (не показан) . В первом такте с входа 8 декодера контрольный код (С ... С) записывается в регистр 2 остатка, а информационный код I а ... а 1 1 - в операционный регистр 1, причем в каждый из регистров 1.1 - 1 записывается А-разрядный код в следующей последовательности: в регистр 1.1 код (а, ... а), в регистр 1.2 код (,... a,jfl) и т.д. С выходов регистра 1.1 информация в параллельном ввде поступает на входы преобра- зователя 3 кода, которьй вырабатывает ---I. - 7 --- код согласно ( а, ... и выдает его на входы регистра 4 циклического сдвига. Первый такт заканчивается приемом информации с выходов преобразователя 3 кода в регистр 4, суммированием информации в параллельном коде с выходов регистра 4 циклического сдвига и регистра 2 остатка в блоке 5 сумматоров по модулю два и записью результата сзпчмирования через другие входы в регистр 2 остатка. В результате по окончании первого такта в регистре 2 остатка зафиксировано значение (С ... С,) + + (а ... ад). Во втором такте производится параллельная циклическая перезапись информации регистров 1.1-1.V через их другие входы, т.е. информация регистра 1.1 записывается в регистр 1.V, информация регистра 1.2в регистр 1.1 и т.д. Далее посредством регистра 1.1 и преобразователя 3 кода производится аналогично предыдущему такту формирование значения 1 и прием его в регистр 4 циклического сдвига, после чего производится 1 циклических сдвигов информации в регистре 4 циклического сдвига и аналогично предыдущему такту запись результата суммы в регистр 2 остатка. В результате в регистре 2 остатка фиксируется знаС„)Ч (а, ... ад ) чение (С + (... aift)T. Последующие такты до V-ro включительно производятся анйлогично второму лишь с той разницей, что количество циклических сдвигов регистра 4 пропорционально возрастает согласно вы,ражению (2). Таким образом, в V-OM такте в регистре 2 остатка зафиксировано значение S по выражению (2), а в операционном регистре 1 - информация (а ... а ), которая с выходов регистров 1.1-1.V поступает на входы блока 6 сумматоров по модулю два, на другие входы которого с выходов дешифратора 7 поступает дешифрированное значение S, указьгоающее номер неисправного разряда в информации (яц ... а). В результате на выход 9 декодера выдается скорректированная блоком 6 сумматоров по модулю два информация Например, для случая К 25, m 5, если в операционньй регистр вместо исправной информации, т.е. когда согласно (1), (С ... ), где С - GI 1, в под- 1i го 25 матрицах проверочной матрицы укорочен ного (30,25) кода Хэмминга отмечены зн ком записана та же информация,но с оши бочным значением в 1 (отмечена знаком 1 ) , то в первом такте в регистре 2 остатка зафиксировано значение (11100) + (OOOIO), (IllOof + (10110) - (01010) ; во втором - значение (01010)+ (00010) X h с одним циклическим сдвигом впр во второго слагаемого, т.е. (01010) + (00010) (01010) + (01011) (00001); в третьем - значение (00001) + (00100)-h;, с 1 2 циклическим сдвигом вправо второго слага(00001) + (00100)h емого, т.е Т + (00111) (00110). (00001) Аналогично в последующих тактах: в четвертом - значение (00110) н + (00001 )-h4 (00110) + (11011) (11101) , в пятом - значение (11101) + (10001)-h5 (11101) + + (01100) (ЮОО) . В результате в последнем, пятом, такте в регистре 2 остатка хранится полином остатка, соответствующий ошибке в разряде а , а на выходах дешифратора 7 вьфаботан корректирующий сигнал в позиции, соответствующей разряду ау. Преимуществом предлагаемого декодера является его упрощение. Сложность введенных блоков пропорциональна числу контрольных разрядов т. В известном устройстве использованы элементы И и ИЛИ, а также приемный регистр, у которых сложность пропорциональна числу информационных разрядов К. Учитывая, что величина К для кодов Хэмминга растет быстрее, чем величина т, сокращение сложности аппаратуры в предлагаемом декодере тем знаЧительнее, чем больше значение К. Для К 119 при использовании, например, микросхем серии 155, достигается сокращение примерно 25% оборудования, что составляет порядка 45-50 микросхем.

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