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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к технике связи с использованием помехоустойчивого кодирования и предназначено для исправления ошибок, возникших в канале связи. Цель изобретения - повышение помехоустойчивости устройства. Устройство содержит генератор 1 адреса, первый и второй коммутаторы 5 и 6, декодер 7 Хемминга, накапливающие сумматоры 8 и 9, регистры 10,11 и 12, элемент ИЛИ 14, инвертор 13 и элемент И 15, программно-временный блок 2, блок 3 памяти, элемент 4 НЕРАВНОЗНАЧНОСТЬ, ключ 16. Устройство позволяет, помимо проверки на четность по строке и по столбцу, осуществить декодирование кода Хемминга по столбцу и вычислить логические функции I и Р, используемые для коррекции ошибок. 4 ил.

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

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

РЕСПУБЛИК (51)5 Н 03 Н 13/00

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

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4446007/24-24 (22) 24.06.88 (46) 28.02.90. Бюл. М 8 (71) Всесоюзный научно-исследовательский институт радиовещательного приема и акустики им. А.СвПопова (72) О.А.Климова и А.И.Синильников (53) 681.325 (088.8) (56} Как-Вильямс Ф.Дж.; Слоэн Н.Дж.

Теория кодов, исправляющих ошибки, И.: Связь, 1979, с. 548-549, борисов В.С., Горемыкин В.В., Никулин В.С. Микросхема обнаружения и исправления ошибок в ЗУ. - Электронная промышленность, 1983, вып.4 (121), с. 21-23.

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

М 364032, кл. С 11 С 29/00, 1970. (54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ

ИТЕРАТИВНОГО КОДА

„„Я0„„1547080 А 1

2 (57) Изобретение относится к технике связи с использованием помехоустойчивого кодирования и предназначено для исправления ошибок, возникших в канале связи. Цель изобретения - повышение помехоустойчивости устройства. Устройство содержит генератор 1 адреса, первый и второй коммутаторы 5 и 6, декодер 7 Хемминга, накапливающие сумматоры 8 и 9, регистры 10, 11 и 12, элемент ИЛИ 14, инвертор 13 и элемент И 15, программно-временной блок 2, блок 3 памяти, элемент 4 НЕРАВНОЗНАЧНОСТЬ, ключ 16.

Устройство позволяет, момимо проверки на четность по строке и по столбцу, осуществить декодирование кода Хемииигв по стопову и вычислить логи- я ческие Функции I и,Р, используемые для коррекции ошибок. 4 ил.

1547080

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

Цель изобретения - повышение помехоустойчивости устройства.

На фиг.1 представлена схема предлагаемого устройства; на фиг.2структурная схема декодера Хеммин. га; на фиг.3 - структурная схема программно-временного блока; на фиг.4 - временные диаграммы сигналов, поясняющие работу устройства. !

Устройство для декодирования итеративного кода содержит генератор 1 адреса, программно-временной блок

2, блок 3 памяти, элемент 4 НЕРАВНОЗНАЧНОСТЬ, коммутаторы 5 и 6, декодер 7 Хемминга, накапливающие сумматоры 8 и 9, регистры 10, 11 и 12, инвертор 13, элемент ИЛИ 14, weмент И 15 и ключ 16.

Декодер 7 Хемминга содержит регистры 17 и l8, блок 19 коррекции ошибок и элемент ИЛИ 20.

Программно-временной блок 2 содержит генератор 21 тактовых импульсов, счетчик 22 импульсов и элемент 23 памяти.

На фиг.4 приняты следующие обозначения: ! 1 - синхроимпульсы на входе синхронизации генератора 1 адреса и блока 3 памяти;

2 — сигнал на управляющем входе записи (считывания) блока 3 памяти;

3 - символы на выходе блока 3 памяти;

4 - сигнал обнуления накапливающего сумматора 8;

5 - сигнал на первом управляющем входе декодера 7 Хемминга;

6 - сигнал на втором управляющем входе декодера 7 Хемминга;

7 - сигнал на первом входе синхронизации декодера 7 Хемминга;

8 - сигнал на третьем управляющем входе декодера 7 Хемминга (на первом управляющем входе блока 19 коррекции ошибок);

9 - сигнал на четвертом управляю ем входе декодера 7 Хемминга (на втором управляющем входе блока 19 коррекции ошибок);

10 - сигнал на втором синхровходе декодера 7 Хемминга (на входе синхронизации регистра 18);

11 - сигнал на пятом управляющем входе декодера 7 Хемминга (на первом управляющем входе регистра 18);

12 - сигнал на шестом управляющем входе декодера 7 Хемминга (на втором управляющем входе регистра 18);

13 - символы на первом выходе декодера 7 Хемминга, поступающие на вход записи информации блока 3 памяти;

14 - сигнал индикатора синдрома на втором выходе декодера 7 Хемминга;

15 - сигнал на управляющем входе коммутатора 5;

16 - сигнал на входе синхронизации накапливающего сумматора 8;

17 - значение q на выходе накапливающего сумматора 8;

18 - значение функции I на входе .1 регистра 11;

19 - значение функции Р на вход, регистра 12;

20 - с иг HBfl HB входе синхрони за ци . регистра 11, регистра 12;

21 - управляющий сигнал на входе коммутатора 6;

22 - сигнал на входах обнуления генератора 1 адреса, регистров 11 и

12 признаков;

23 - сигнал, поступающий на вход обнуления накапливающего сумматора 9;

24 - сигнал, поступающий на вход синхронизации этого же сумматора 9;

25 - сигнал, поступающий на вход синхронизации регистра 10;

26 - значения q; с выхода накапливающего сумматора 9;

27 - значения функции I с выхода . регистра 11;

40 28 - значение функции Р с выхода регистра 12;

29 - значение символов с выхода регистра 10;

30 - значения символов с выхода элемента 4 "Неравнозначность", т.е. с выхода декодера итеративного кода.

Временные диаграммы на фиг.4 иллюстрируют случай исправления трехкратной ошибки;

50 а<, а а@ ... а к ай! . аы а2ъ ° ° а2к а j1 а 32. ау) ° ° ° a 3K

° ° ° ° ° ° 4 ° ° ° ° ° 4 ° ° ° ° ° ° ° ° ° ° ° °

° е ° ° ° ° ° ° ° е ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° е К2. а Е3 ° ° ° а7

Правильные значения символов для наглядности полагаем "0" (не закраа,„ а якшу<

10 гк <

° ° ° а ГК а Г

al

А= е ° ° ° ° ° аГл<К+<

° ° аФ+л«

Г+а

a„<.«

° ° ° ° ° ° ° ° ° Э °

20 а mk+<

30

40

50

5 1547080 шены на фиг.4), ошибочные - "1" (закрашенные).

Устройство работает следующим образом.

В блоке 3 памяти записано кодо5 вое слово итеративного кода в виде матрицы А ан а<2 а<к а1< а22 ° . ° а „

° ° ° в ° ° ° ° ° ° ° ° ° ° е ° ° ° ° ° ° ° ° е ° ° ° ° ° ° ° ° ° °

° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° °

° ° ° ° ° ° е ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° °

° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° °

° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ап» аmz аек

° ° ° ° ° ° ° ° ° ° ° ° ° ° ° Ф ° ° ° ° ° ° Э ° ° ° ° ° ° Ф Ф ° ° °

a<<<+<< a«<<- « a«<<-<к am<-< k+<

В матрице А каждый столбец состоит из символов расширенного кода

Хемминга Vf (m+1, r, 4), т.е. кода

Хемминга (ш, r, 3), дополненного общей проверкой на четность по столбцу (символ и<+1-й строки), а каждая из

r первых строк дополнена символом четности по строке (символ k+1-го столбца) и представляет собой ко)1

V с общей проверкой на четность.

Таким образом, матрица А является кодовым словом итеративного кода

V образованного из кодов Vf (по столбцам) и V< (по строкам), Данный код V позволяет исправлять любую комбинацию оши<1ок кратности не выше трех.

Введем обозначения: V, — кодовое

V q, — индикатор синдрома: S =0, если синдром кодового слова V<> ра" вен нулю, и S =1 в противном случае.

Алгоритм декодирования .кода V реализуется за следующие 5 шагов: декодирование кодов V<>, вычисление 8 {j=1, ..., k+1); вычисление общей проверки на чет ность q в кодах Ч<, вычисление значений функции I =

Б1Ч <1 <3 и P j =S) h q <5 э вычисление проверки на четност.ь

q ; в кодах Че,, инвертирование символов а, находящихся на пересечении столбцов, для которых значение I =1, и строк, для которых q1 1 в случае если Для

2 всех j=1, ..., k+1 P =О, в противном случае (если хо я Ьы для одного значения Р =1) - инвертирование

1 символов а;, находящихся на пересечении столЬцов, для которых Р =1, и строк для Kotopblx q 2 )

При всех возможных комбинациях однократных, двукратных и трехкратных ошиЬок при данном построении кода Ч приведенный выше алгоритм декодирования исправляет все эти ошибки.

В работе устройства можно выделить два этапа.

На первом этапе работы производится считывание матрицы А из Ьлока

3 памяти по столбцам, начиная с первого (по адресам, вырабатываемым генератором 1 адреса), при этом на управляющий вход первого коммутатора

5 подается сигнал, переводящий коммутатор 5 в состояние, когда информа" ция с его информационного входа поступает на информационные входы декодера 7 Хемминга и накапливающего сумматора 8. B этом сумматоре производится вычисление q, для данного столбца, а в декодере 7 Хемминга его декодирование, при котором исправляются однократные ошибки. Значения декодированных символов столбца с первого выхода декодера 7 Хемминга перезаписываются в блок 3 памяти на свои старые места, а значение индикатора синдрома декодирования этого столбца S с второго выхо) да декодера 7 Хемминга поступает на первые входы элемента ИЛИ 14 u weмента И 15, на второй вход элемента

ИЛИ 14 подается значение q на второй вход элемента И 15 это же значение q подается инвертированным при помощи инвертора 13. На выходе элемента ИЛИ 14 формируется значение If =Sf q а на выходе элемента

И 15 - Р; =S Aq . Значения I и Р„ .< f записываются в соответствующйе ячейки регистра 11 (там записываются значения I ) и регистра 12 (там записы) ваются значения Р ). Такой процесс осуществляется для всех столбцов матрицы А, считываемых последовательно из блока 3. В результате в блок

3 будут записаны символы матрицы А

1547080 с исправленными однократными ошибками в столбцах (т.е. матрица А ), а в

I регистрах 11 и 12 - значения I и Р

J„ для всех столбцов, причем второй коммутатор 6 будет находиться в положении, когда на его выход будет пода.ва ться сигнал с выхода регистра 11, е ли все значения Р =О, в противном ! У с учае, как только для какого-либо з аченйя j (j=1, 2, ..., !с+!) Р =1 с гнал с выхода элемента И 15, подав емый на управляющий вход второго к ммутатора 6, переключит его в полож ние,. когда на его выход будет проходить сигнал с выхода регистра 12.

Т перь наступает второй этап работы, п и котором производится считывание последовательно по строкам символов .матрицы А, кдторые поступают на инффрмационный вход первого коммутатор 5, на управляющий вход которого поступает сигнал, переключающий его а положение, когда информация а его и формационного входа поступает на а од регистра 10 и накапливающего сумматора 9, который вычисляет значение q - для данной строки. Значе2i ння символов этой строки записываются и хранятся в регистре 10 lloKa 30 ж закончится вычисление и . Значение 1; с выхода накапливающего сумматора 9 подается на второй вход юча 16 переписи информации, на ервый вход которого в это время ерез второй коммутатор 6 поступает

Значение Е q (если все Р =О), лиоо

Р, (в противном случае), сигнал с айхода ключа. 16 переписи информаЦии равен единице лишь в том случае, Когда !2, =1 и I,=1 (если все Р =О), либо Р< =1 (в противном случае), т.е.

Если считываемый в это время из регистра 10 символ (в данном случае а, ) находится на пересечении "ошибочных" столбца и строки. В таком случае на первый вход элемента 4 "Неравнозначность" с выхода ключа 16

Подается "1" и символ а;,, поступающий с выхода регистра 10 на второй вход элемента И, проходит на ее выход 5

50 инвертированным, т.е. исправленным.

Если же символ правильный, он проходит на выход без изменения. Аналогичным образом исправляются ошибки во всех символах строки, считывае- 55 мых последовательно из регистра 10.

Затем производится считывание из блока 3 следующей строки и т.д.

Таким образом, предлагаемый декодер итеративного кода позволяет полнее использовать корректирующие свойства итеративного кода за счет применения в процессе коррекции наряду с проверкой на четность символов строк и столбцов декодирования по Хеммингу символов столбцов, а также использования в процессе декодирования результатов вычисления некоторых логических функций I и Р, благодаря чему корректирующая спо=.абность декодера возросла в 3 раза. ф о р м у л а и з о б р е т е н и я

Устройство для декодирования итеративного кода, содержащее первый регистр, информационные входы которого объединены с информационными входами первого накапливающего сумматора, выход которого соединен с первым входом ключа, выход которсго подключен к первому входу элемента НЕРАВНОЗНАЧНОСТЬ, выход которого является выходом устройства, второй регистр и блок памяти, о т л и ч а ю щ е е с я тем, что, с целью повышения помехоустойчивости устройства, в него введены третий регистр, второй накапливающий сумматор, инвертор, элемент ИЛИ, элемент И, коммутаторы, декодер Хемминга, программно-временной блок и генератор адреса, выходы которого подключены к адресным входам блока памяти,. выход которого подключен к информационному входу первого коммутатора, первый выход которого соединен с информационным входом первого регистра, выход которого подключен к второму входу элемента НЕРАВНОЗНАЧНОСТЬ, первый выход программно-временного блока подключен к входам синхронизации генератора адреса и блока памяти, второй и третий выходы программно-временного блока подключены соответственно к входу управления режимами блока памяти и управляющему входу первого коммута-. тора, второй выход которого подключен к информационным входам второго накапливающего сумматора и декодера Хемминга, первый выход которого подключен к входу записи блока памяти„ четвертый и пятых выходы программно-временного блока подключены соответственно к входам синхронизации и обнуления второго накапливающего сумматора, выход которого подключен непосредственно к первому

1547080

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

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

Составитель О.Тюрина

Редактор A.Лежнина Техред И,Дяцык Корректор A,0Ьручар Заказ 86 Тираж 657 .«Подписное

ВКИИПИ Государственного комитета по иэооретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород,. ул. Гагарина,101