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



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

по формуле (6.30).

В данном случае имеем: и = 15; и = 2; 1; Ф1 4; фо = 15;

14 - 5з - 13; £13 =2 = 7; Ег2 = = 3; Е,, = = 0.

Прежде всего убедимся, что при/ = О и/ = 1 соотношение (6.30) справедливо (это явится косвенной проверкой правильности вычисления синдрома и полинома локаторов):

при / = О £"12 Еуз , 1 + £"14 1 0 = 7 4 + 13 • 15 = 3; при/ = 1 £"11 = £i2/i + £i3Vo= 3-4 + 7 • 15 = 0, ]

Далее при / = 2 находим

£"10 £"111 ! + 12 V/o = О • 4 + 3 • 15 = 2, GF(2).

Аналогично получим: £"9 = 5; £"8 = 10; £"7 = £•4 = 1; £3 = 8; £"2 = 12; Е = 9;£о = 15.

ошибки е = (0) i)

= (14, 3), то мы можем выполнить проверку, умножив *is, усеченную до двух строк:

-(14, 3) •

111111111111111 .1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

= (15, 9, 12, 8, 1, 6, 4, И, 10, 5, 2, О, 3, 7, 13) = - {Eof El, Е2, Ез, Е, Е$, Esf Е, Е, Е9, Ею, Ец, Ei2, Е13, £14).

Можно заметить, что умножая вектор (о, i) на указанную матрицу, мы получаем последовательные значения на рис. 3.5 (* = 4), начиная со строки = 3 в циклически продолженном столбце = 14.

Коррекция (F = С + £) дает вектор (6.27), отбрасьюая в котором четыре правые нулевые разряда, извлекаем верное сообщение Q (6.26).

Частотный метод декодирования значительно проще декодирования во временной области. Однако, как отмечалось выше, он имеет следующий недостаток: сбои в блоке ФМС-преобразования (см. рис. 6.4, б), искажающие любые "несиндромные* символы Q с номерами / = О, 1, ..., к - 1, не могут быть выявлены. Действительно, пусть для простоты принято искаженное кодовое слово v = v с нулевыми т правыми разрядами. Но если в процессе ФМСП будут искажены символы Q с номерами / = О, 1, ..., fc- 1, то аналогично будет искажено сообщение Q на выходе декодера, хотя т проверочных компонент вектора С, т. е. синдром, и равны нулю.



Различные аспекты частотного кодирования - декодирования изложены также в работах [10,11, 20, 29, 59].

64. СМЕШАННОЕ КОДИРОВАНИЕ И ДЕКОДИЮВАНИЕ КОДОВ РИДА - СОЛОМОНА: ВРЕМЕННОЙ КОДЕР - ГИБРИДНЫЙ

(ЧАСТОТНО-ВРЕМЕННОЙ) ДЕКОДЕР

Систематическое кодирование РС-кодом во временной обпасш с помоию симметричного порождающего полинома. До сих пор кодирование осуществлялось с помощью полинома (6.1) при = О или V = I, Можно упростить процесс кодирования (снизить число умножений на разные константы), если, принимая = 2" ~* - 0,5w, составить порождающий полином в симметричной форме:

g(2)=2"+ . z«-l+...+gi2+go, (6.33)

где ,. =,., / =0,1,... ,0,5w-l; gQ = g = l,

В остальном процедура систематического кодирования не изменяется: находится остаток R = rest [z"6(z) :g(z)] и составляется кодовое слово вида (6.3):

v(z)-z«e(z)+i?(2).

Пример 6,6, Зададимся полем GF(2 = 2*), а = 2, и примем п = 15, W = 4, тогда при <i = 5 и 1 = 6 получим

giz) = S (2+20 =2*+4z+2z +42 + 1. (6.34)

/ = 6

Задавшись сообщением Q (6.26), найдем /?=rest(z*Q/g)-(7,4,8,6).

Таким образом, получаем кодовое слово V = (Q; Я){13, 7, 15, 5, 9, 1, О, О, О, О, О, 7, 4, 8, 6) =

= (14. 1ЭзУ12уП,ЮуУ9*Н,т,У,У5,У4, Рз ,з , 1 , Pq ) *

(6.35)

Вычисление синдрома как быстрое ФМС-преобразоваиие. Порождающий полином g(z) является симметричным, если переменная i в формуле (6.1) изменяется в пределах /ш = = (2* ~ * - От), /щах -= (i + w - 1).В этих же пределах должна изменяться переменная i в соотношении (6.2) при формировании проверочной матрицы Н. Так, полиному (6.34) соответствует матрица



1 7 13 4 10 1 7 13 4 10 1 7 13 4 10

1 8 15 7 14 6 13 5 12 4 11 3 10 2 9

1 9 2 10 3 11 4 12 5 13 6 14 7 15 8

1 10 4 13 7 1 10 4 13 7 1 10 4 13 7

. (6.36)

Заметим, что вследствие симметричности полинома g{z) столбцы в матрице Н могут бьпь расположены в прямом порядке [столбец

из единиц находится справа, как, например, в формуле (6.2)] либо в обратном порядке, как в матрице (6.36). Другими словами, неискаженное кодовое слово v представимо как в виде v = (vo, vi, ., vj j),

так и в виде Г= (Упхп-г • - уо)-

Читатель может убедиться, что умножение v и v на - транспонированную матрицу (6.36) дает в обоих вариантах нулевой синдром. Конечно, в процессе декодирования расположение компонент принятого вектора v должно быть заранее фиксировано, для того чтобы позиции ошибок определялись однозначно.

Синдром .S" вычисляется либо по методу Горнера (6.9), либо методами, аналогичными быстрым алгоритмам усеченного ФМС-преобразования, например, основанными на факторизации матрицы Я. Во втором случае матрицу Я типа (6.36), соответствующую симметричному полиному g {z), вначале представляют в виде Н Я, где Я - стандартная матрица (6.5) с единичной верхней строкой; D - диагональная матрица с компонентами, совпадающими с первой строкой исходной матрицы Я. Затем w-строчная стандартная матрица Я, соответствующая т верхним строкам в матрице (6.5), рассматривается как усеченное и-точечное ФМС-преобразование, В данном примере

As = diag (1, 7, 13, 4, 10; 1. 7, 13, 4, 10; 1, 7, 13, 4, 10); (6.37)

п = Wi Из = 5 • 3 = 15 и можно воспользоваться, например, факторизацией (4.26) - см. рис. 4.12 ... 4.15. Прн этом матрица перестановок исключается, а в матрице А = (£"3 ® Фв) достаточно оставить w = 4 строк с номерами

/ = Wi f (mod и - 1) = 5 / (mod 14),

где / =0, l,...,w - 1 = 3и принята последовательная нумерация 0,1, 2,..., и- 1 = 14 сверху вниз для строк матрицы Л. Так что

S=Hv ADlpBDisV.

(6.38)

где Dis - матрица (6.37); DP и 5 - матрицы, вычисленные соответственно на рис. 4,12 и 4.14; а матрица имеет вид



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