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



приведем числовой пример кодирования сообщения с помощью матрицы (1.18) и примеры исправления одной и двух ошибок при декодировании с помощью матрицы (1.19). Примем Q = (бз Qi) -

- (5, 1, 2). Тогда V = QG; Vn - Q,v Qi.Vs Qi,v = Qa - 32 +

+ 3Gb V3 - 3G3 - 8G2 + 6Q1, V2 - 6Q3 - 15Q2 + lOGiii = 10Q3 -

- 24G2 + 15Gb т.е. V = (v, v, .... vy) = (5, 1, 2, 8, 19, 35, 56). Умножая полученное кодовое слово v на Н, можно убедиться, что все четыре компоненты синдрома 5" равны нулю.

Внесем ошибку, например на символ v- наложим помеху е = -5, т. е. примем v = (О, 1, 2, 8, 19, 35, 56). Найдем синдром: 5 = (Sy, SyS). Имеем

SvH\ 5i - 5; 52"=15; 5з=30; 4 50. (1.20)

Компоненты синдрома имеют наибольший общий делитель, равный НОД (5"!, 5*2, 5*3, 5*4) = 5. Разделив их на этот НОД, получим набор (1, 3, 6, 10), отличающийся от левого столбца в матрице Я (1.19) лишь знаком. Это позволяет заключить, что ошибочен левый кодовый символ, а величина ошибки е = -НОД= - 5. Коррекция: V7 ~ V7 - е = 5.

Обратим внимание на следуюшлй важный факт: вектор синдрома 5" пропорционален тому столбцу в матрице Я, номер которого соответствует позиции одиночной ошибки. При этом величина ошибки равна коэффициенту пропорциональности. Мы не будем формулировать алгоритм исправления одной ошибки при декодировании с помощью матрицы (1.19) и надеемся, что читатель при желании сделает это самостоятельно.

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

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

под воздействием ошибки стал равным 60, т. е. вектор ошибки равен (-5, О, О, О, О, О, 4). Умножая правый столбец на 4 и добавляя его

к вектору синдрома S (1.20), получим для S новые значения (5, 15, 30, 54). Естественно, в процессе декодирования синдром вычисляется как S = v; в данном случае можно убедиться, что S = (О, 1, 2, 8, 19, 35,60) = (5, 15,30,54).

Как теперь по синдрому найти позиции и величины ошибок? Можно утверждать следующее: а) так как S ф О, то кодовый вектор искажен; б) так как НОД {Sy, . . . , S) = 1, то ошибок более одной.

Для "двоичного" кода, т.е. если известно, что е £ (о, l}, можно заранее составить таблицу всевозможных сумм столбцов матрицы Я. Тогда в подобной таблице позиции ошибок находятся по синдрому S. Но ввиду произвольной величины ошибки е способ табличного декодирования нереален. Даже в конечном поле (при ограничении числа градаций и при исправлении небольшого числа ошибок, но в длинном кодовом слове) табличный способ декодирования труднореализуем.



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

Оказывается, для декодирования с исправлением любого числа ошибок удобнее не систематическая форма (1.13) матрицы Н, а усеченная форма (1,14), получаемая из матрицы Вандермонда. В этом случае процесс выявления позиций всех v ошибок сводится к решению некоторого алгебраического уравнения степени и, что и является сутью алгебраического метода декодирования.

Пусть позиции Ц искажены ошибками , / = 1, 2, . . . , и. Согласно матрице (1.14), для синдромов имеем

S 1 al , / = О, 1,.. . , ш - 1, i = 1 Ч

В данных соотношениях известны лишь составляющие Sj синдрома, а также то, что параметры ai. лежат среди чисел fli, 2. • • • > /7. Ни величина ошибок ei , ни их позиция ни даже количество v не известны.

Поэтому соотношения (1.21) задают систему нелинейных уравнений. Эта система, как будет показано в гл. 6, приводится к линейной системе уравнений со специальной матрицей. (В гл. 6 используется конечное поле, но сам принцип приведения и его результат справедлршы для любого поля.) Для этого относительно неизвестной переменной z - локатора (обратного позиции ошибки) вводится так называемоеурав-

(1.21)

нение локаторов o(z) + сто; ао = 1.

О, где o(z) = Qyz" +ay i2

и - 1

+ . . . + 0\Z +

В результате получается линейная относительно , ст i, • . . , Оу система уравнений, в матричной форме имеющая вид

(1.22)

где о = (ау, 1, . . . , ai); 5" = (S, • • • iv) ганкелева

матрица

Si S

m + I

m + 1

(1.23)

Решение о = -ST" может быть найдено каким-либо традиционным методом, не учитывающим специфику матрицы Г: определитель-



ным методом Крамера, методом исключения Гаусса и т.п. [31-33]. Разработаны и методы обращения ганкелевых и теплицевых матриц [7, 18, 27, 42].

Однако в теории помехоустойчивого кодирования обычно используются итеративные процедуры. Для этого вводится так называемое ключевое уравнение

S(z)o(z) =ы(2:).

(1.24)

где S (z) - известный полином синдрома; o(z) и co{z) - неизвестные полиномы локаторов и величин ошибок.

В гл. 2 будут изложены универсальные методы, позволяющие решить уравнение (1.24), т. е. найти полиномы o{z) и cj(z) по полиному 5(z).

Сейчас мы можем только перечислить эти методы: метод Тренча- Берлекэмпа-Месси (ТБМ) ; метод Сугиямы, основанный на алгоритме Евклида; беэрекуррентный метод, основанный на алгоритме Гаусса и вычислении особых продолжений ганкелевой матрицы.

Здесь же для простоты мы ограничимся частным приемом, удобным для исправления одной - двух ошибок.

Итак, предположим, что и < 2. Тогда ш = 4 и

5*0 = е. + е.; Si = е. а. + е. а.;

Исключая последовательно переменные , е, получим Si-S, (д. а.)8оа.а. =0;

8г - S, (af + а.а. + д) + а.а. (д. + д-) = 0.

(1.25)

Подставляя в последнее уравнение произведение 5оД/Ду-, взятое из уравнения (1.25), найдем после преобразований

(1.26)

2 (а. aj)S,a.a. =0.

Таким образом, получаем систему из двух уравнений (1.25), (1.26) относительно неизвестных i д,- + Ду и 2 - Д/Д/, которая в матричной форме записывается следующим образом:

{УхУг)

(1.27)

Решая матричное уравнение (1.27) по методу Крамера, получаем Уу = Ai/A,y2 = А2/Д, где



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