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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) 1. Авторское свидетеФ 318939, кл. С 06 Р 5/022. Авторское свидетель669357, кл, С 06 Р 11/1 хоян ьство СС 1969. тво СССР 1975.(54)(57) ДЕКОДЕХЭММИНГА, содеррегистр, регисттор, о т л и ччто, с целью уптем исключенияи элементов ИЛИблоков ввода ив него введены Р УКОРОЧЕНжащий оперр остаткаа ю щ и й ОГО КОДАционныйдешифратем рощения декодера и блоков элементов И,блока упр вывода инф последоват азователь влен рмации,льно соеода, реи первый ые пре дине гист блок циклического сд умматоро второй б а, а по м такж ок суммат ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР00 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ,ЯО 1109924 А зш Н 04 Е 1/10//С 06 Р 11/12 два, выход которого является в ходом декодера, при этом к первому входу второго блока сумматоров по модулю два подключен выход дешифратора, к входу которого и второму входу первого блока сумматоров по модулю два подключен выход регистра остатка, первый вход которого объединен с входом операционного регистра и является входом декодера, а к второму входу регистра остатка подключен выход первого блока сумматоров по модулю два, при этом операционный регистр содержит у регистров, выход каждого 1 -го из которых ( 1 = 2, 3, , М ) подключен к входу -1)- Я го регистра и к соответствующему вхо - ду второго блока сумматоров по модулю два, а выход первого регистра опе- Сфф рационного регистра подключен к входам Ч -го регистра, преобразователя р кодов и второго блока сумматоров пойети модулю два.1109Изобретение относится к вычислительной технике и может быть применено в устройствах обмена цифровых вычислительных машин, в периферийныхустройствах цифровых систем, а также5между устройствами внутри вычислительной машины.Известно устройство для декодирования кода с коррекцией одиночных ошибок, содержащее регистр с фиксированными цепями сложения по модулю двапорождающего полинома 11,Недостатком устройства являетсянизкое быстродействие,Наиболее близким к изобретениюпо технической сущности является декодер кода Хзмминга, содержащий операционный регистр, регистр остатка и дешифратор, а также блоки элементов Ии элементов ИЛИ, блок управления,блоки ввода и вывода информации,Известный декодер предназначендля коррекции одиночных ошибокв информации с высокой скоростью вычисления полинома остатка, что достига 25ется совмещением во времени операцийсложения определенных групп разрядовв операционном регистре 1.21.Недостатком известного устройстваявляется его сложность из-за исполь- ..зования Е -разрядного приемного ре 30гистра (где Ф - число информационныхразрядов), блоков элементов И и ИЛИ,блоков ввода и вывода информации.Цель изобретения - упрощение декодера путем исключения блоков элемен- З 5 тов И и элементов ИЛИ, блока управления, блока ввода и вывода информа- ЦИИДля достижения поставленной цели в декодер укороченного кода Хэмминга,ф содержащий операционный регистр, регистр остатка и дешифратор, введены последовательно соединенные преобразователь кода, регистр циклического сдвига и первый блок сумматоров по модулю два, а также второй блок сумматоров по модулю два, выход которого является выходом декодера, при этом к первому входу второго блока сумматоров по модулю два подключен 50 выход дешифратора, к входу которого и второму входу первого блока сумматоров по модулю два подключен выход регистра остатка, первый вход которого объединен с входом операционно го регистра и является входом декодера, а к второму входу регистра остатка подключен выход первого блока924 2сумматоров по модулю два, при этомоперационный регистр содержит У регистров, выход каждого 1 -го из которых ( 1 = 2,3 У ) подключенк входу (1 -1)-го регистра и к соответствующему входу второго блока сумматоров по модулю два, а выход первого регистра операционного регистраподключен к входам Ч -го регистра, преобразователя кодов и второго блока сумматоров по модулю два.На чертеже. приведена структурная электрическая схема предлагаемого декодера.Декодер содержит операционный регистр 1, состоящий из У регистров 1.1-1. У, регистр 2 остатка, преобразователь 3 кода, регистр 4 циклического сдвига, первый и второйблоки 5 и 6 сумматоров по модулю два,дешифратор 7.Предложенный декодер предназначен для декодирования кодов Хэмминга, укороченных за счет сокращения числа ин-. формационных символов таким образом, чтобы число К информационных символов после укорочения было кратно числу ,Ф избыточных символов исходного кода Хэмминга (2 - 1, 2 - 1 - Ф ).В этом случае коды Хэмминга (31, 26) и (127, 120) укорачиваются до вида (30,25) и (126,119), например до вида (30, 25):к 1 0000 01000 00100 00010 0000.1 С 4 СФСЗС 4 С 00011 00000 11111 1010 01111 ааааа ю 1 Ю 1 м 1501.11100011000001111110101ьацаф а ю41010101111000110000011111ВГ 2 ая 111 0101 1111 0011 0000 а а а,а00001110101110 0ьауава 9 уколяетчодри этом проверочная матрица нного кода Хемминга представиде Н =ЭЬ 1. Ь Э - единичная матрица, а ся где3 11099 матрицы Ь , , Ь, составлены путем циклического сдвига строк матрицы Ьл.Декодер укороченного кода Хэмминга функционирует на основе следующих предпосылок.Согласно теории кодирования основной задачей при декодировании кода Хэмминга является вычисление поли- нома остатка (кода номера искаженного разряда) посредством выражения 10Б = (Сл С аар) Н, (1) где Б полином остатка,СлС - контрольные разряды кодового блока;азаз 1 - информационные разрядЫ, ЗаТ - знак транспонированияматрицы;Н - проверочная матрица кода.Выбрав Н = ЭЬ . ЬЬ 1 такам образом, чтобы ЬЬ образо вывались от Ь посредством циклических сдвигов строк в Ь 1 , получаем выражениеЧ, 25Злос 1 цаОгде А = К/ш.Откуда, используя циклическую за,висимость подматриц Ь , формирование Б в устройстве производится вЧ, тактов. Причем в каждом такте сначала производится вычисление значе 1ол 1р(л 1)л затем -циклических сдвигов вправорезультата произведения (артаА(1 лЬ и подстановка полученного значения в выражение (2). Например, для случая К = 25, ш = 540А = 5, если требуется вычислить эначение ( алл алр ал ал ал ) Ьз= .(10111)т Ь = (00011) , достаточновычислить: (алл ал алз ам ал )Тт=(10111) Ь = (01100) и произвес 45ти= 2 циклических сдвига вправо.Вычисление Б и его дешифрация в устройстве производится следующим образом.Предполагается, что функция синхронизации и управления устройством50возложены на блок управления (не показан).В первом такте с входа 8 декодераконтрольный код (С лС,1 записывается в регистр 2 остатка, а информационный кодаа 1 - в операционный регистр 1, причем в каждыйиз регистров 1.1 - 1 записывает 24 4ся А-разрядный код в следующей последовательности: в регистр 1.1 код (а,а), в регистр 1.2 код (ад л а) и т.д. С выходов регистра 1.1 информация в параллельном виде поступает на входы преобра зователя 3 кода, который вырабатывает код согласноаа Ь и выдает его на входы регистра 4 циклического сдвига. Первый такт заканчивается приемом информации с выходов преобразователя 3 кода в регистр 4, суммированием информаций в параллельном коде с выходов регистра 4 циклического сдвига и регистра 2 остатка в блоке 5 сумматоров по модулю два и записью результата суммирования через другие входы в регистр 2 остатка. В результате по окончании первого такта в регистре 2 остатка зафиксировано значение (СлС) + + (аад)Во втором такте производится параллельная циклическая перезапись информаций регистров 1.1-1.Ч через их другие входы, т.е. информация регистра 1.1 записывается в регистр 1 Ч, информация регистра 1.2- в регистр 1.1 и т.д. Далее посредством регистра 1.1 и преобразователя 3 кода производится аналогично предыдущему такту формирование значения (аЛл 1 а ) . Ь и прием его в регистр 4 циклического сдвига, после чего производится= 1 циклических сдвигов информации в регистре 4 циклического сдвига и аналогично предыдущему такту запись результата суммы в регистр 2 остатка. В результате в регистре 2 остатка фиксируется значение (СлСш) л (аа ) + + (а я+лаая )тПоследующие такты до Ч-го включительно производятся аналогично второму лишь с той разницей, что количество циклических сдвигов регистра 4 пропорционально возрастает согласно выражению (2),Таким образом, в Ч-ом такте в регистре 2 остатка зафиксировано значение Б по выражению (2), а в операционном регистре 1 - информация (аа, ), которая с выходов регистров 1.1-1.Ч поступает на входы блока 6 сумматоров по модулю два, на другие входы которого с выходов дешифратора 7 поступает дешифрированное значение Б, указывающее номер(аак).В результате на выход 9 декодеравыдается скорректированная блоком 6сумматоров по модулю два информация.Например, для случая К = 25,ш = 5, если в операционный регистр 1вместо исправной информации, т.е.когда Б = 0 согласно (1), (СС аа 5), где С= С = СЗ=а=ап =а=а=а =1,вподматрицах проверочной матрицы укороченного (30,25) кода Хэмминга отмечены зна-,комоорзаписана та же информация,но с ошибочным значением й т = 1 (отмечена 15Мзнаком р ), то в первом такте в регистре 2 остатка зафиксировано значение (11100) + (00010)- (11100) + (10110)(01010) ; вот Твтором - значение (01010) + (00010) х 20х Ь с одним циклическим сдвигом вправо второго слагаемого, т.е(01010) +(00001) + (00100) Ь с= 2 циклическим сдвигом вправо второго слагаемого, т,е. (00001) + (00100)Ь 5 =+ (01100) = (10001)В результате в последнем, пятом,такте в регистре 2 остатка хранитсяполином остатка, соответствующийошибке в разряде а , а на выходахдешифратора 7 выработан корректирую щий сигнал в позиции, соответствующейразряду ан,Преимуществом предлагаемого декодера является его упрощение, Слож" ность введенных блоков пропорциональна числу контрольных разрядов ш. В известном устройстве использованыэлементы И и ИЛИ, а также приемный регистр, у которых сложность пропорциональна числу информационных разрядов К, Учитывая, что величина К для кодов Хэмминга растет быстрее,чем величина шр сокращение сложности аппаратуры в предлагаемом декодере тем значительнее, чем больше значение К. Для К = 119 при использовании, например, микросхем серии 155, достигается сокращение примерно 253 оборудования, что составляет порядка 45-50 микросхем.