Устройство для декодирования с коррекцией ошибок Советский патент 1990 года по МПК H03M13/03 

Фиг. 1

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

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

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

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

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

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

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

табл. 1.

Таблица 1

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

Таблица 2

Элементы кода d

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

(.) О 1 2 3 4 5 6 7

1111

10111

000000000

1-01111111

202222222

303333333

404444444

505555555

606666666

707777777

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

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

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

®ЈУ,-Ьм 5

)ЧI

©1угь12,

(1)

где ® $ сумма в GF(q);

Ч

У,

-элементы проверочной матрицы Н;

-элементы принятой кодовой комбинации вида

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

0

5

Y (у

3у8у,уьу5у4УзУ4у,)

(2)

t J (,J 3J i-N столбца, j-N строки матрицы Н, а у и у9 - проверочные элементы кодового блока и у 1 - у 7 - информационные элементы кодового блока.

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

1

4

1

.7

При этом, если в одном из п элементов кодовой комбинации произошла любая ошибка, то первая группа разрядов S синдрома представляет собой величину

ошибки g, а вторая

SZ произведение

величины ошибки е на номер L искаженной информационной позиции в кодовой комбинации.

е;

eL.

5г

делят величину S

(4)

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

L S4/S,.(5)

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

u , ИСТ

Ь.ист

L. иск4

(6)

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

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

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

4108

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

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

15 13 соответственно, и вновь помещаются для промежуточного хранения в регистры 12 и 13. Так реализуют выполнение в соответствии с выражениями (1) обработки сигналов кода. При этом в ре20 гистрах 12 и 13 запоминают сигналы данных по переднему фронту тактового импульса. Две группы разрядов проверочного синдрома S, и S

сформиро5

0

5

0

0

5

ванные по указанному правилу, подают на блок 6 деления, где определяют номер позиции L искаженного элемента посредством деления второй группы разрядов проверочного синдрома, хранящегося в регистре 12 ,S г eL на первую группу 5 6, хранящуюся в регистре 13.

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

Пусть ошибка произошла на 7-й позиции в первой кодовой комбинации. На фиг. 2 позициями 18-26 показано продвижение искаженного элемента 7.1 в составе новой кодовой комбинации. По окончании 9-го такта счетчик 7 устанавливается в состояние О, и очеред

ным тактовым импульсом записывают в- регистр 4 величину ощибки е е. , а в счетчик 5 - номер L (фиг. 2, позиции 29 и 30). Выходными сигналами счетчика 5 в состоянии К 7 отпирают блок 3 элементов И и разрешают величине ошибки суммироваться в блоке 2 сумматоров с искаженным элементом 7.1 с выхода регистра 1. Скорректированные данные в виде (т 3)-разрядного числа снимают с выхода блока 2 сумматоров в интервале от заднего фронта предыдущего тактового импульса и до переднего фронта следующего тактового импульса. Очередность появления данных на выходе устройства проиллюстрирована на фиг. 2, позиция 31, где скорректированный элемент 7.1 изображен в незаштрихованной области. Коррекцию ошибки на другой позиции регистра 1 данных осуществляют аналогично. Пусть, например, искажен элемент кода на третьей позиции второй

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

30

40

ствует величина ошибки е е1, а на выходе блока 6 деления - значение ло катера L ошибки. По переднему фронту тактового импульса эту информацию записывают импульсом с выхода элемента в регистр 4 и в счетчик 5 (фиг. 2, позиции 29 и 30) соответственно. Съем информации с выхода устройства получателем происходит в середине тактового интервала. При этом посредством счетчика 5, установленного в состояние L 3. 011 а, подсчитывают число сдвигов групп данных в регистре 1 до состояния К 7, когда на вход блока 2 сумматоров с выхода последней ячейки регистра 1 поступает искаженный элемент второй кодовой комбинации, обозначенный символом 3.2 (фиг. 2). После перевода счетчика 5 в состояние К 7, его выходными сигналами отпирают блок 3 элементов И и разрешают величине ошибки g суммироваться с искаженной группой данных 3.2 второй 50 кодовой комбинации в блоке 2 суммато-. ров. Скорректированный элемент присутствует на выходе блока 2 в интервале от заднего фронта текущего до передстолбец | матрицы Н (выражение 3),

то сигналы величины ошибки е 0, записанные в регистр 4, впоследствии суммируют с сигналами проверочного элемента yg, искажая его истинное значение. Однако в предлагаемом уст- 35 ройстве для указанного применения так же, как и в известном устройстве, это не является недостатком, так как сигналы данных устройство корректирует надежно (если произошла однократная ошибка), а проверочные сигналы получатель игнорирует.

45

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

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

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

торого подключен к установочным входам второго счетчика импульсов и чет-г

41088

элемент 3.2 изображен в незаштрихованной области. Другие группы разрядов по мере их поступления в блок 2 суммируются с О, что никак их не и т, - няет.

Если ошибка не происходит вовсе, то в регистр 4 величины ошибки запи

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

1 °

соответствует столбец

матрицы Н

(выражение 3), в регистр 4 запишутся сигналы О, с которыми в дальнейшем

суммируются сигналы данных у - у7,

никак не изменяясь. Если ошибка искажает сигналы проверочного элемента уд (выражение 2), которому соответствует

столбец | матрицы Н (выражение 3),

то сигналы величины ошибки е 0, записанные в регистр 4, впоследствии суммируют с сигналами проверочного элемента yg, искажая его истинное значение. Однако в предлагаемом уст- ройстве для указанного применения так же, как и в известном устройстве, это не является недостатком, так как сигналы данных устройство корректирует надежно (если произошла однократная ошибка), а проверочные сигналы получатель игнорирует.

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

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

первого счетчика импульсов подключены к вторым входам элемента И, выход ко-

торого подключен к установочным входам второго счетчика импульсов и чет-г

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

|8тб15Ш1Г2тщат7Гбт итг юяа msm um

imttimn2i tifrmtm5.2 42mi№ifa2 73№ $i 3 j 2T

t

t

.miUni1 t1V Wl 12 6Z $l uZ Ј 2t 1ZW2l/(.

тщеп5.1мштш1 к1№щг2 б2 52 й.гШ1г2 1г м2 щ731Бз 5з {13

t

m 61 ilWJWniWWffiU 6.2 52 ul fflZZ tZW№V3 S3 5j

my.iuwvwi iiv iiwi 7z 62 s2 i2 j2 22 i2 itimw3 63

..

t

ШЫ №№ 12П11 М1Ш1гуг 52 {12Ш г2(.Я

Щ5.(

Щбц51 ьщцгц11№Щ1 1г б2 5г ьгш 22 1г

i

,33

гг

Jf

пк

es

т ISTS т л or/ IZTJ r pr TZTJ т 5 |g 17 in 4 гдЕтпотгт.,

.SffHHbisнеопределены - i 5i r 2i i2 iz{52 52(

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

t

t

t

t

,33

пк

es