Устройство для декодирования с коррекцией ошибок

 

Изобретение относится к обработке дискретной информации с исправлением ошибок данных путем контроля избыточности. Устройство применяется для обнаружения и исправления ошибок при сборе, хранении и передаче цифровой информации недвоичным кодом с применением многопозиционных сигналов. Каждый элемент кодовой комбинации, проверочной матрицы и синдрома формируют, хранят и пересылают между блоками в виде набора двоичных цифровых сигналов (многопозиционного сигнала). Целью изобретения является упрощение устройства. Устройство содержит регистры 1, 4, 12 и 13, блок 2 сумматоров, блок элементов И 3, счетчики 5 и 7 импульсов, умножители 9 и 10, элемент И 8, блок 6 деления, сумматоры 11 и 14, тактовый, информационные входы и выходы 15, 16 и 17 устройства соответственно. 2 ил.

А1

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

СОЩИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

»»> SU»»

Р1} Н 03 М 13/00

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

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

Фиг. 1

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

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

ПРИ П<НТ СССР! (21) 4360286/24-24 (22) 11.01 ° 88 (46) 07.08.90. Бюл. У 29 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) В,П. Полторак, Ю.П. Жураковский и В.Н. Кузнецов (53) 681.325(088.8) (56) Авторское свидетельство СССР

1!> 794728, кл. Н 03 М 13/00, 1981.

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

В 1446695, кл. Н 03 М 13/00, 29.11.(5. (54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ

С КОРРЕКЦИЕЙ ОШИБОК (57) Изобретение относится к .обработке дискретной информации с исправлением ошибок данных путем контроля

2 избыточности. Устройство может приме-няться для обнаружения и исправления, ошибок при сборе, хранении и передаче, цифровой информации недвоичным кодом . с применением многопозиционных сигналов. Каждый элемент кодовой комбинации, проверочной матрицы и синдрома формируют, хранят и пересылают мея(цу блоками в виде набора двоичных цифровых сигналов (многопозиционного сигнала). Целью изобретения является упрощение устройства. Устройство содержит регистры 1, 4, 12 и 13, блок 2 сумматоров, блок 3 элементов И, счетчики 5 и 7 импульсов, умножители 9 и .

10, элемент И 8, блок 6 деления, сум-. маторы 11 и 14, тактовый, информационные входы и выходы устройства соответственно 15, 16 и 17. 2 ил., 2 табл.

1584!08

Таблица 2

1 1 1

О О О

1 1 1

2 2 2

3 3 3

4 4 4

5 5 5

6 6 6

7 7 7

1 О 1 1 1 1

О. О О О О О

1 ° О 1 1 1 1.

2 О 2 2 2 2

3 О 3 3 3 3

4 О 4 4 4 4

5 О. 5 5 5 5

6 О 6, 6 6 6

7 О 7 7 7 7 (.)

О

2

4

6

82 где +);>

h.

1) У; (.) О

3 4

4 5 6 7

0 О 0,0

4 5 6 7

3 1 7 5

7 4 1 2

5 2 5,1

2 7 3 6

5 3 2 4

6 4 3

О 1 1 2 3

0 О О О О

О i 1 2 3

О 2 2 4 6

0 3 3 6 5

О 4 4 3 7

0 5 5 1 4

О 6 6 7 1

О 7 7 5 2

55

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

5 при сборе, хранении и передаче цифровой информации.

Целью изобретения является упрощение устройства.

На фиг. 1 представлена структурная схема предлагаемого устройства; на

:фиг. 2 — пространственно-временная

:диаграмма работы устройства..

Устройство содержит регистр 1, "блок 2 су жаторов, блок 3 элементов .И, регистр 4, счетчик 5 импульсов, блок 6 деления, счетчик 7 импульсов, элемент И 8, умножители 9 и 10, сумматор 11, регистры 12 и 13, сумматор

14, тактовый, информационные входы и выходы устройства соответственно

15, 16 и 17. Регистр 1 представляет собой регистр длиной в и ячеек no m параллельных двоичных разрядов, каждая25 из которых принимает одно m-разрядное двоичное слово. Блок 2 сумматоров представляет собой ш элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и выполняет логическую .функцию поразрядного суммирования

30 по mod 2 двух m-разрядных двоичных чисел, где m-разрядность кодового символа в декодируемом коде. Блок 3 элементов И представляет собой m параллельно работающих элементов И с (m+1) входами, причем (m+1)-й вход каждого

35 элемента подключен к своему разряду выхода регистра 4, а остальные ш входов каждого элемента И подключены к соответствующим разрядам выхода счет40 чика 5. Умножитель 10 может быть организован на основе ПЗУ на (2m+1) адресных входах и m выходах, хранящего таблицу умножения, представленную в табл. 1.

Таблица 145.Элементы Элементы второй строки прокода. d верочной матрицы кода Н

Умножитель 9 может быть организован на основе ПЗУ; хранящего таблицу умножения в конечном поле GF(8) сок ласно табл. 2.

Элементы Элементы первой строки прохода d верочной матрицы кода H

Особенностью. умножителей 10 и 9 является то,.что с их помощью выполняют умножение в конечном поле, например СГ(8), элементов кода на элементы одной строки проверочной матрицы систематического кода Н (для умножителя 9) и на элементы другой строки матрицы Н (для умножителя 10).

Работа предлагаемого устройства основана на выполнении следующего алгоритма декодирования с коррекцией ошибки.

Формируют две группы разрядов синдрома S и S из элементов кодовой комбинации, поступающей на входы первого и второго умножителей

Il

97у, h, (., h ()

1с1 сумма в GF(q); элементы проверочной матрицы Н; элементы принятой кодовой комбинации вида

У9 У3 будд узу2У1)

i-N oTo 6, j-N строки матрицы Н, а у и y>— проверочные элементы кодового блока и у — у — информационные элементы кодового блока.

Так, например, для систематического кода с основанием q = 2 = 8 матрица Н выглядит следующим образом:

5 15841

0 1 1 2 3 4 5 6.7

При этом, если в одном из п элементов кодовой комбинации произошла любая 5 ошибка, то первая группа разрядов S синдрома представляет собой величину ошибки Р, а вторая S — произведение величины ошибки 6 на йомер L искаженной информационной позиции в кодовой комбинации.

S е °

1 1

S = е1. (4) г

Затем "делят" величину $, представленную второй группой разрядов синдрома, на величину ошибки S = е и определяет номер L искаженной информационной позиции.

15 (5) 1 = S1/S1 °

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

35 разрядов, и ставят в соответствие одному элементу конечного поля порядкац=2 .

Исходное состояние устройства характеризуется следующими признаками 40 (фиг. 2): состояния регистра 1 (позиции 18-26), регистра 4 (позиция 29) и счетчика 5 (позиция 30) произвольны; состояния второго счетчика 7, пер-. вого 12 и второго 13 регистров нулевые.

Пусть для примера m = 3, когда п = 9. На вход 16 устройства (фиг.1) потактно подают и = 9 групп по ш = 3 двоичных разрядов. Под действием тактовых импульсов, например, по заднему их фронту в регистре 1 эти группы сдвигают и = 9 раз в течение и = 9 тактов, до заполнения регистра 1 ко- 55 довой комбинацией. Процесс продвижения кодового вектора в ячейках регистра 1 данных иллюстрирован на фиг..2 позициями 18-26.

Корректируют искаженную группу информационных разрядов у „ отыскивая ее по найденному номеру L и прибавляя ?5 к ней величину ошибки 8 . При этом получают истинное значение L-й группы данных у„, которая была искажена.

,ист

08

Одновременно с продвижением групп данных в регистре 1 элементы кодовой комбинации с входа декодера поэлементно подают на первый умножитель 10, в котором происходит умножение на элементы второй строки матрицы Н, и на второй умножитель 9, посредством которого элементы принятого кодового вектора умножаются на элементы первой строки матрицы Н. Произведения этих элементов подают на первый 11 и второй 14 сумматоры, суммируя их с содержимым, хранящимся в регистрах 12 и

13 соответственно., и вновь помещаются для промежуточного хранения в регистры 12 и 13. Так реализуют выполнение в соответствии с выражениями (1) обработки сигналов кода. При этом в регистрах 12 и 13 запоминают сигналы данных по переднему фронту тактового импульса.. Две группы разрядов проверочного синдрома S и S, сформированные по указанному правилу, подают на блок 6 деления, где определяют номер позиции 1 искаженного элемента посредством деления второй группы разрядов проверочного синдрома, хранящегося в регистре 12 >Я z = eL на первую группу Б = е, хранящуюся в регистре 13.

Задним фронтом п=9-ro тактового импульса счетчик 7 устанавливают в нулевое состояние. Его выходные сигналы при этом через элемент И 8 разрешают очередному тактовому импульсу. (фиг. 2, позиции 28 и 31) по переднему его фронту осуществить установку разрядов счетчика 5 и регистра 4 в соответствии с поступившими на их информационные входы сигналами, а именно — записывают в регистр 4 значение ошибкн Р,. а в счетчик 5 — сигналы, представляющие собой номер позиции искаженной группы данных в кодовой комбинации, после чего происходит обнуление первого 12 и второго 13 регистров по заднему фронту тактового .импульса. Момент обнуления регистров 12 и 13 выходным сигналом переноса (переполнения) с выхода счетчика 7 показан на фиг. 2, диаграмма 27.

Пусть ошибка произошла на 7-й позиции в первой кодовой комбинации. На. фиг. 2 позициями 18-26 показано продвижение искаженного элемента 7. 1 в составе новой кодовой комбинации. По окончании 9-ro такта счетчик 7 уста-. навливается в состояние "0", и очеред, 1584 108 ным тактовым импульсом записывают врегистр 4 величину ощибки е = е, а в счетчик 5 — номер L (фиг. 2, позиции 29 и 30). Выходными сигналами счетчика 5 в состоянии К = 7 отпирают блок 3 элементов И и разрешают величине ошибки суммироваться в блоке 2 сумматоров с искаженным элементом

7.1 с выхода регистра 1. Скорректированные данные в виде (m = 3)-разрядного числа снимают с выхода блока 2 сумматоров в интервале от заднего фронта предыдущего тактового импульса и до переднего фронта следующего тактового импульса. Очередность появления данных на выходе устройства проиллюстрирована на фиг. 2, позиция 31, где скорректированный, элемент 7.1 изображен в незаштрихованной области.

Коррекцию ошибки на другой позиции регистра 1 данных осуществляют аналогично. Пусть, например, искажен элемент кода на третьей позиции второй кодовой комбинации, обозначенный сим- 25 волом 3.2 (фиг. 2, позиции 18-26).

После записи кодовой комбинации в регистр i на выходе регистра 13 присутствует величина ошибки e = e„ а на выходе блока 6 деления — значение ло30 катора L ошибки. По переднему фронту тактового импульса эту информацию записывают импульсом с выхода элемента в регистр 4 и в счетчик 5 (фиг. 2, позиции 29 и 30) соответственно. Съем информации с выхода устройства получателем происходит в середине тактового интервала. При этом посредством счетчика 5, установленного в состояние L = 3 = 011 подсчитывают чист

40 ло сдвигов групп данных в регистре 1 до состояния К = 7, когда на вход блока 2 сумматоров с выхода последней ячейки регистра 1 поступает искаженный элемент второй кодовой комбинации, 45 обозначенный символом 3.2 (фиг. 2) .

После перевода счетчика 5 в состояние К = 7, его выходными сигналами отпирают блок 3 элементов И и разрешают величине ошибки 9 суммироваться с искаженной группой данных 3.2 второй кодовой комбинации в блоке .2 сумматоров. Скорректированный элемент присутствует на выходе блока 2 в интервале от заднего фронта текущего до переднего фронта следующего тактового им- 55 пульса. Скорректированная вторая кодовая комбинация показана на фиг. 2, позиция 31, где скорректированный элемент 3.2 изображен в незаштрихованной области. ЛРугие группы разрядов по мере их поступления в блок 2 суммируются с "0", что никак их не из;:— няет.

Если ошибка не происходит вовсе, то в регистр 4 величины ошибки записывается "0", и во время коррекции независимо от состояния счетчика 5 все группы разрядов данных, поступающие на вход блока 2, суммируются с нулем, что никак их не изменяет. Сигналы проверочных (избыточных) элементов кода устройство не корректирует, так как в их коррекции нет необходимости и получатель сигналов данных обычно их игнорирует, При этом, если ошибка искажает сигналы проверочного элемента у (выражение 2), которому

0 соответствует столбец матрицы Н (выражение 3), в регистр 4 запишутся сигналы "О, с которыми в дальнейшем суммируются сигналы данных у„ — у никак не изменяясь. Если ошибка искажает сигналы проверочного элемента у9 (выражение 2), которому соответствует

1 столбец -- матрицы Н (выражение 3); то сигналы величины ошибки e g О, записанные в регистр 4, впоследствии суммируют с сигналами проверочного элемента у, искажая его истинное значение. Однако в предлагаемом устройстве для указанного применения так же, как и в известном устройстве, это не является недостатком, так как сигналы данных устройство корректирует надежно (если произошла однократная ошибка), а проверочные сигналы получатель игнорирует.

Формула изобретения

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

)О

1584108

4 2 5 4.1 .. 2.111 11 52 .2 2212 1 22 7. 3 .3 4. Х 2

1 1 Z111 1 tl .2 242 2.212 12К2273 353 43

1 I 1

G . И Л! 1 11 К11 12 72 6ZSZ 42 .Z 22 12 К12К2 73 63 53 43

l I t

61 1 1 Х1 211 К1 1272 62 524.2 . 22 12 fff К2 73 ЕЗ 5.3

1 t

1 Ф. 12111 fl f. 72 6.25. 42 .2 2.212 К1 к2 73 63

1 I

61 .1 t 31 Zf 11 fuff 1 lZ 6Z 2 .2 3Z 2.Z 1,2К12К2 73

I I t.1 1И . 2111 3 1272 Z 24.2 2212К1.2кг

151 Zf 11 11 f 72 62 524.232 2.212 К1

f 5.141 31 2.1 11 11 f. 72 62 52 2 3Z 2.2 12 32 ЗЗ

29 е, 0123701234567345870 f 2

1 1 t

ЯРНУСНЕОПДЕдСЯСНУ 61 5 i v f 3 21 к" !272 62 5.2 2Z 12

ФУ2. 2

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

Техред Л.Олийнык Корректор M. Самборская

Редактор И. Горная

Заказ 2264 Тираж 661 Подписное

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

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

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101 вертого регистра, выходы которых подключены соответственно к первым и вторым входам блока элементов И, выходы которого подключены к вторым . входам блока сумматоров, выходы кото5 рого являются выходами устройства, выходы второго и третьего регистров подключены к первым входам первого и второго сумматоров, выходы блока деления подключены к информационным входам второго счетчика импульсоВ, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, в него введены первый и второй умножители, первые входы которых объединены с информационными входами первого регистра и являются информационными входами устройства, вторые входы умножителей объединены и подключены к информационйым выходам первого счетчика импульсов, выход переполнения которого подключен к управляющим входам второго и третьего регистров, выходы первого и второго умножителей подключены соответственно к вторым входам одноименных сумматоров, выходы которых подключены к информационным входам соответственно второго и третьего регистров, первые входы блока деления подключены к выходам второго регистра, вторые выходы блока деления объединены с информационными входами четвертого регистра и подключены к выходам третьего регистра.