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

 

Изобретение относится к технике связи с использованием помехоустойчивого кодирования и предназначено для исправления ошибок, возникших в канале связи. Цель изобретения - повышение помехоустойчивости устройства. Устройство содержит генератор 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

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

 

Похожие патенты:

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

Изобретение относится к вычислительной технике и технике связи,, Его применение в системах передачи и обработки информации позволяет повысить точность декодера, который содержит буферные регистры 1,2, вычислители 3,4 синдрома, генератор 5 синдрома , дешифратор 6 состояний, элемент И 7 и с т-1матор 8 по модулю два

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

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

Изобретение относится к системам мобильной связи, в частности к устройству и способу кодирования-декодирования блоковых кодов низкой плотности с проверкой на четность (НППЧ)

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

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

Изобретение относится к системам радиосвязи, а более конкретно к механизмам и способам для отображения кодового слова в связанный с ним слой

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

Изобретение относится к вычислительной технике

Изобретение относится к средствам для генерирования матрицы проверки четности в системе связи с использованием линейных блочных кодов. Технический результат заключается в повышении эффективности восстановления искаженной информации. Определяют базовый параметр второй матрицы проверки четности, удовлетворяющей правилу, предварительно определенному по отношению к заданной первой матрице проверки четности. Генерируют подматрицы, соответствующие части четности второй матрицы проверки четности, с использованием базового параметра. Генерируют подматрицы, соответствующие части информационного слова второй матрицы проверки четности, с использованием первой матрицы проверки четности и базового параметра. 4 н. и 8 з.п. ф-лы, 14 ил., 41 табл.

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

Наверх