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



- S2S0

- S2SI

S2 - Si S3

(1.28)

0, / =0, 1,

m - 1, считается, что оши-

Напомним: при Sj = бок нет.

Вообще говоря, можно искусственно подобрать такие значения ошибок при и > ш, т. е. за пределом способности данного кода исправлять ошибки, что синдром 5" примет любое наперед заданное значение, в том числе и 5 = 0. Однако вероятность события v> т пренебрежимо

мала; в противном случае число проверочных символов должно быть увеличено.

Можно показать, что если Д = О, А/ = О, / G { 1, 2} , то кодовое слово искажено одной ошибкой в позиции, соответствующей Si/Sq ~ ai, а величина ошибки суть е = Sq. Если Д = О, Д/ О, / = 1 ипи i = 2, то ошибок более двух. Наконец, при Д Ф О, Aj Ф О, i G { 1, 2} , имеем вариант с двумя ошибками. Как показано выше, + Ду = Ai/A, Д/ду = = Д2/Д, т.е. мы знаем сумму и произведение позиций а,, Ду ошибок.

Наша задача - составить относительно неизвестных позиций д,-, д уравнение

+ ai л: + 02 - О,

(1.29)

где по теореме Виета [33] 02 - dfaj-, Oi ~ д,- + .

Пример 1.2. Пусть самый левый символ в кодовом слове искажен ошибкой ei - -5. Используя матрицу (1.14), находим; 5*0 - -5; =

- -5Д1; 2 = -5д?; S - ~5af.

Таким образом, Д = Д1 = Д2 = О, а следовательно, имеется только одна ошибка величины ei - Sq = -5 и на позиции, соответствующей Si/Sq = Д1.

Пусть, кроме того, ошибочен и второй слева символ, причем 62 - 2. Воспользовавшись матрицей (1.15), найдем: 5*0 = -5 + 2 = -3; -

- -5 + 2.2= -1; 2 = -5 + 2-4 = 3; 5з - -5 + 2-8 = 11. Поэтому, Д = -10, Ai = 30, Д2 = 20 и ai = Д1 + Д2 = -3, 02 - Д1Д2 - 2. Составим

Зх+2 =0, решая которое найдем пози-

уравнение типа (1.29), т. е. х -ции ошибок: Xi = 1,2 - 2.

Если ошибок много, то уравнение локаторов (позиций) имеет высокую степень. Решать такое уравнение целесообразно методом проб и ошибок - последовательно подставляя в это уравнение возможные значения локаторов (или позиций) - 1,2,... Подобный метод упорядоченного перебора называется процедурой Ченя.



Далее будет видно, что в конечном поле для вычисления величин ошибок еу разработана процедура Форни, требующая вычисления полинома cj(2:), входящего в уравнение (1.24), и взятия формальной производной Z от полинома a(z). В данном пункте поступим по-другому - составим систему из двух уравнений:

е. + е.

Решая эту систему, находим = {S i - So ) I (а - ) ; соотношение для Cj аналогично (при взаимной замене / и / ). В нашем примере соответственно имеем:

€i = {Si - Soa2)l(ai - Дз)

5; (Si - Soai)lia2- ai) = 2.

Подытожим изложенный алгебраический метод декодирования (во временной области) на основе матрицы Я (1.14) в виде следующего укрупненного алгоритма.

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

2. Если вектор синдрома равен нулю, то считать, что ошибок нет. Иначе, при S Ф О, решить уравнение локаторов (методом Гаусса, с помощью алгоритма Евклида или ТБМ-методом), составив полиномы локаторов a(z) и величин co(z) ошибок.

3. Решить уравнение a(z) =0 (например, путем упорядоченного перебора - способом Ченя), т.е. найти локаторы, а следовательно, позиции ошибок.

4. Вычислить величины ошибок, например, методом Форни.

5. Скорректировать*символы на позициях вычитая из них величину €,i = 1, 2,. . ., V.

Циклические коды над полем рациональных чисел. До сих пор на величины ai в проверочной матрице (1.14) не налагалось никаких ограничений. Однако можно принять fii), например: ау - = 1; а2 а\ Дз = д; . . , ; д,- = д ~ , . . . , д„ = д"~ . Тогда матрица (1.14) примет вид:

1

1){п

(1.30)

где для удобства столбцы матрицы помечены соответствующими кодо выми символами v, i = I, 2,., . , п.

Код, задаваемый матрицей Я (1.30), называется кодом Рида -Соло мона; его кодовое расстояние d связано с числом проверочных сим



волов т =п - k следующей простой зависимостью: d - т + \. Форма (1.30) имеет три достоинства. Во-первых, появляется возможность при вычислении компонент синдрома 5у, / О, I, . . , , ш - 1, производить умножения только на одну константу , используя метод Горнера:

S. =v-aUvn~i +a4 2 + ---+a(v2 + ah,) ,..)). (1.31)

Во-вторых, проверочная и ортогональная ей порождающая матрицы этого кода содержат соответственно по tn и к независимых столбцов.

В-третьих, код становится циклическим (усеченным) и может быть задан не только матрицами, но и полиномами - проверочным h{z) и порождающим (z) = (z - 1) (z - д) (z - д) ... {z - ~ ). При этом оказывается, что кодировать удобнее с помощью полинома (z), а декодировать - с помощью матрицы Н.

Примем, к примеру, д = 2, = 2, ??г - 4; тогда g(z) ~ (z - 1) X X (z - 2) (z - 4)(z - 8) =z - 15z + TOz - 12O2 +64;

"1

1 "

(1.32)

Приемы систематического кодирования с помощью полинома (z) будут изложены в гл. 6.

Несистематическое кодирование осуществляется по форму)е v =0g, где Q - {Q, . . . , Ql) = (62, Gl) - информационный вектор; (I, - 15, 70, -120, 64). Например, для Q - (-1, 2) имеем v = {v. - . . , Vi) - = (-1, 17,-100,260,-304, 128).

Напомним, что синдром находится как произведение: S -vH. Умножая вектор v на транспонированную матрицу (1.32), убеждаемся, что все компоненты синдрома равны нулю: So = 405 - 405 = 0; 5"! = = 1440- 1440- 0; 2 = 8640- 8640= 0; S = 86400- 86400= 0.

Приведенные методы кодирования и декодирования принято относить к временной области. В последние годы интенсивно разрабатываются и частотные методы.

Понятие о кодировании и декодировании в частотной области. Величина д в матрице (1.30) никак не регламентирована. Читатель, знакомый с дискретными ортогональными преобразованиями, безусловно, обратил внимание, что матрица (1.30) будет задавать дискретное преобразование Фурье (ДПФ), если принять т=п н в качестве параметра а выбрать первообразный корень степени п из единицы, т. е.

а = ехр(±/ 2я/п) = cos {l-njn) ± / sin (l-n/n),

где знак плюс соответствует прямому, а минус - обратному преобразованию.



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.0097