Главная Помехоустойчивое кодирование



Итак, при d = 3 и задании проверочной матрицы Н в систематической форме (1.13) имеем следующий алгоритм декодирования принятого кодового слова V = (Q, Qjt-l--62>6lP2»Pl)-

1. Вычислить синдроме" = vHу т. е.

где / =1,2; Ci = ai при j = I ис = bi при/ = 2.

2. Если 5"! = О или 5*2 - О, то информационные символы считать верными (при Sj ФО, где / =1 либо / =2, ошибочен проверочный символ р-, а при Si ФО и S2 ФО - по крайней мере один из информационных символов).

3. Если 5"; 0,/ = 1, 2, то рассчитать отношение S2/S

4. Если S2/S1 - ui/bj, то искажен символ Qi, а величина ошибки е =

-52 -

5. Скорректировать /-й принятый информационный символ, вычитая из него величину е.

6. Если S2/S1 Фа/Ь ни при каком г € 1, 2, то ошибок в принятом кодовом слове более одной (имеется неисправимая данным кодом конфигурация ошибок).

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

Далее мы будем рассматривать также матрицы Н, отличающиеся от формы (1.13). Б этом случае алгоритм декодирования несколько изменяется. Проиллюстрируем процессы кодирования и декодирования на примере.

Пример 1.1. Кодирование и декодирование (с помощыб проверочной матрицы в систематической форме) для кода над полем рациональных чисел. Примем для простоты и определенности 2 ~ ~ 2 ~ Ь ~ 2. Тогда А = аЬу - 0 и столбцы (строки) матриц Н линейно

независимы. Пусть задано сообщение Q - [Q2 - 4, 0\~б\. Закодируем его:

V = (Q2QiP2Pi)=QG= (6261)

10 11 0 1 12

где Р2 - Q2 + Ql - 10; Pi = Q2 + 2(2i - 16.

Таким образом, кодовое слово имеет вид v ~ (4, 6, 10, 16).

Предположим, что символ Qi искажен аддитивной помехой е = -5, т. е. что принято кодовое слово v = (4, 1, 10, 16). Воспользуемся приведенным алгоритмом декодирования.

1. Вычисляем си11др1)м

S = (S2S,) =vH (4, 1, iO, 16)

1 -1 1 О

1-2 О 1J



т.е. 2 = -4-1 + 10 = 5; Sy - -4-2+ 16= Ю.

2. Так как S2 ФО, Si Ф О, то какой-то информационный символ ошибочен.

3. Найдем отношение iS2/»Si - 5/10 ~ 1/2.

4. Так как отношение 1/2 выполняется для второго слева столбца в матрице Я, т.е. S2/S1 -fli/bi, то ошибочен символ Qi. Величина ошибки е =82/01 - -5.

5. Скорректированное сообщение [4, 1 - (-5)] = (4,6) совпадает с исходным Q - {Q2 Qi).

Блоковые коды над полем рационалысых чисел, исправляющие произвольное число независимых ошибок. Так как процесс декодирования существенно сложнее процесса кодирования, то целесообразно проверочной матрице Я задать специальную форму, при которой последующее декодирование упрощается. Прежде всего необходимо обеспечить линейную независимость ?п столбцов (строк) матрицы Я. Известно [31, 33], что определитель А Вандермонда, построенный на наборе чисел fli, ai, . . . , а», равен произведению всевозможных разностей д- - Ду, где 1 < / < г < п. Таким образом, А О при Фа!, а а1едовательно, столбцы (строки) в соответствующей матрице линейно независимы.

Итак, примем проверочную матрицу в виде усеченной матрицы Вандермонда;

, т < п. (1-14)

"« J

В матрице (1.14) т столбцов линейно независимы. Для простоты и определенности положим: = 1, Дг - 2, . . ., д„ = п. Тогда получим

1 2

. 1

(1.15)

0 т - I

где строки и столбцы обозначены переменными / и / и пронумерованы.

Кодировать сообщения Q = (g, G: - 1 • Gi) систематической форме можно не только с помощью порождающей, но и произвольной проверочной матрицы. Для этого к сообщению Q приписывают, напри-



мер, справа т искомых переменных - проверочных символов р = (р,

Рт - 1» • • • > Р1) получают вектор v = (Qp)» в котором б и р - наборы известных и неизвестных величин. Вектор v умножают на матрицу Я, а все компоненты полученного синдрома S = vH приравнивают нулю. В результате получают линейную систему из т уравнений с т неизвестными Pi, р2, .. ,, pj. Благодаря строению матрицы Я эта система всегда имеет решение, причем единственное.

Однако проще сообщения кодировать с помощью порождающей матрицы G в форме (1.7), которая может быть составлена по матрице Я (1Л5), если последнюю, в свою очередь, привести к виду (1.13).

Это достигается следующим образом. Вначале матрица (1.15) приводится к трапецеидальной форме:

" 1

- 3

.. . -

• •

fm -

• /7 -

1 - >

(1.16)

к - \ нулей

т + 1 элементов

1 элементов по / - 1 эле-

где п = к т; Cj 1 - число сочетаний из / -

менту, причем Са = = 1, = О при а < Ь.

Заметим, что помехоустойчивый код, задаваемый матрицей Я (1.16) в ряде случаев используется при защите вычислительных систем от ошибок оператора [19, 28]. На втором этапе матрица (1.16) приводится к виду (1.13), где

Л = [/(Л/)],/(/,/) = ("О

J -1

Ci - Ci

(1.17)

Например, при к ~3, m = 4 получим:

1 0 0

0 1 0

3 8 6

6 15

10 24 15

(1.18)

3 8 15 24

-6 I 10 I 15

1 0 0

1 0 0 1 0 0

0 0 0

(1.19)



0 1 2 [3] 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94


0.0116