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



Еще раз подчеркнем, что полиномам (6.4) соответствуют разные проверочные матрицы. Составим вспомогательную матрицу

1 1

2 1

3 1

4 1

. (6.5)

5 1

6 1

7 и

Тогда проверочные матрицы Я, сопоставляемые с полиномами g{z) (6.4а) и (6.46), образуются шестью строками матрицы (6.5) -соответственно последними и первыми*.

Предположим теперь, что задан информационный вектор Q = 13, 9, 6, 7, 15, 14, 12, 10). Умножая его на вектор, соответствующий полиному (6-4а), получим после преобразований несистематическое кодовое слово

(11>

G- (11,15,3,9,6,14,7,5,12,15,14,3,3,7,1).

(6.6)

Для того чтобы закодировать полином Q(z) систематически, следует представить его в форме Q(z) =q(z)g(z) + Л (z), где deg R(z) <

< m, и приписать R к Q. Выполнив деление Q{z)z Hag(z), можно показать, что

(И, 13,9,6,7,15,14,12,10,0,0,0,0,0,0) =

= (1,11,15, 5, 7,10,7)-(И, 15, 9,10,12,10,10,10,3) + + (1,2,3,7,13,9), GF(2*),

T.e./?=rest (Q/g) = (1,2,3,7,13,9).

Дописывая вектор R справа от Q, получим кодовое слово U в систематической форме:

f/= (11,13,9,6,7,15,14,12,10; 1,2,3,7,13,9),

(6.7)

где младшие разряды расположены справа и нумеруются О, 1, .. . , 14.

Первые девять компонент в слове (6.7) совпадают с информационными, а остальные шесть - являются проверочными.

Синдром РСкода. Любое неискаженное кодовое слово U удовлетворяет соотношению (1.53а) UH = 0. Произведение UH =S определяет синдром, причем вектор f/, возможно, содержит ошибки. При использовании матрицы Я в форме (6.2), т. е. для РС-кода, синдром S

* в § 6.4 будет использована еще одна - симметричная форма порождающего полинома (2). 94



является вектором-изображением усеченного ФМС-преобразования для

рАк-тппя-ппигиняпя и (г.м, 8 Компонентьт гинппомя задаются

вектора-оригинала U (см. § 6.4). Компоненты выражением

5. = 2 w.a/, и = 1.

(6.8)

I = О

Часто практически удобнее компоненты .Sy вычислять по следующей рекурсивной формуле, называемой схемой Горнера:

S. -щ + («i + («2 + ... + Ч"„ 2 "и- i) *••)) С)

где / = 1,2,..., /«.

Используя соотношения (6.8) или (6.9), читатель может убедиться,

что для вектора U (6.7), не искаженного помехами, все компоненты синдрома S равны нулю.

Если кодовое слово U под воздействием вектора помех трансформировалось в вектор ф

S = иН = {U + £)Я = Ш + ЕН = ЕН = 0. (6.10)

Пример 62. Для поля GF (2*):

и= (11,13,9,6, 7,15,14,12,10, 1, 2, 3, 7, 13, 9) (6.11)

Е= ( О, 0,0,0,12, О, О, О, О, О, О, 8, О, О, 0) (6.12)

4= (11,13,9,6, 2,15,14,12,10, 1,2,13, 7, 13, 9), (6.13)

т. е. на позициях /3 = 3 и /ю = Ю (нумерация справа, начиная с нуля) действуют помехи, имеющие величину е/ = 8 и б/ =12.

Компоненты Sj синдрома в процессе декодирования вычисляются по формулам (6.8) или (6.9) с учетом замены, естественно, U на U. Мы же для простоты воспользуемся соотношением (6.10), из которого следует:

S=EH\

5. = "s ~ \.а =8(а)/" +12(а**) =8 - 4" + 12 • иЛ (6.14а) / = о

Откуда находим:

Sx = 8, 2 = 13, 5з = 7,, .S4 = 13, 5 - 15, = 15. (6.146)

Укрупненный алгоритм декодирования РС-кода во временной области. Для простоты предположим пока, что стирания (искажения, местоположение которых известно) в кодовом слове отсутствуют, а оно испорчено только 01пибками, т.е. искажениями, для которых неизвестны ни местоположение, ни величина. Более того, заранее не известно и их число.



Классический синдромный метод декодирования во временной области для (и, А:)-кода PC с кодовым расстоянием d состоит из следующих укрупненных этапов:

1) вычисление синдромаS;

2) вычисление вектора ошибок; в классическом варианте декодирования данный этап разбивается на два:

2а) определение местоположений ошибок /; 26) нахождение величин ошибок е/;

3) коррекция кодового вектора и извлечение сообщения. Охарактеризуем каждый из этапов,

1. Компоненты синдрома S = (5,5, • • • > т + у - i) е 0,1 ] J находятся по формулам (6.8) или (6.9). Если все Sj = О, / = = 1, i+l,,..,m + i/ - 1,то считаем, что ошибок нет. В противном случае, если Sj Ф О хоть для одного /, то устанавливаем факт искажения кодового вектора; для его коррекции необходимо найти вектор оши-бок,т. е. их местоположение и величину.

2а. Задача определения местоположений ошибок является наиболее трудной, и, как будет видно из дальнейшего, она может быть сведена к решению системы ганкелевых (теплицевых) уравнений, а затем - к одному, так называемому уравнению локаторов. Если степень этого уравнения не превышает 0,5т, а его решение над полем Галуа существует, причем все корни различны, то позиции ошибок равны обратным значениям корней. При небольшом числе ошибок и, следовательно, невысоком порядке уравнения над полем Галуа его решение может бьпь найдено, например, табличным методом (гл.5). В общем случае прибегают к упорядоченному перебору всех возможных значений для его корней; подобный перебор именуется процедурой Ченя [22, 40], Далее в § 63 будет рассмотрен метод декодирования, основанный на вычислении особых продолжений ганкелевых (теплицевых) матриц и вообще не требуюший решения указанного уравнения локаторов.

26.После того как расположение ошибок установлено, т.е. они перешли в разряд стираний, возникает задача вычисления их величин е,-. Данная задача сводится по существу к решению системы линейных уравнений над полем Галуа относительно е/. Такая система может быть решена любым стандартным методом, например методами Крамера, Гаусса, обращения матриц. Однако в процедуре декодирования кодов над полями Галуа для вычисления величин ошибок удобнее использовать особые продолжения ганкелевых матриц (см. § 63) либо применить формулу Форни

г 9 ..-1

(6.15)

где / - позиция ошибки; oz {z) - формальная производная полинома o(z) по z; 02 (а~) и со(а~) - значения полиномов a(z) и co(z) в точке



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