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



z = (zo,...,z,4) = (4, 2, 10; 3, 9, 10; 12, 8, 14; 6, 10, 9) As=diag (1, 1, 1; 1, 2, 3; 1, 3, 5; 1, 4. 7)

Dh = (4, 2, 10; 3, 10,12; 12, 10, 3; 6, 13,15) =

- (УоУи У2 ; Уз. У4 У5\ Уб> Уп> Уь\ У9> У.Уп)

Наконец, найдем синдром как скалярное произведение матрицы (6-41) на векторjv:

5 =54/= (4 + 2+10 = 0; 3 + 10+12 = 0; 12+10 + 3=0; 6+13 + 15=0) = (0,0,О,0), GF(2).

Нулевой синдром подтверждает, что исходный вектор v является кодовым словом.

Укрупненный алгоритм гибридного декодирования РОкода. Согласно рис. 6.4, в процесс гибридного декодирования состоит из следующих этапов:

1) вычисление т-точечного ФМС-преобразования;

2) нахождение полинома локаторов;

3) рекуррентное продолжение синдрома;

4) обратное ФМС-преобразование;

5) коррекция;

6) извлечение сообщения.

Первый этап фактически сводится к вычислению синдрома и аналогичен первому этапу временного декодирования. Специфика ФМС-преобразования проявляется лишь при реализации быстрых алгоритмов, подобных рассматривавшимся вьппе.

Второй и третий этапы идентичны соответствующим этапам частотного декодирования. Продолжение вектора синдрома S совпадает с особым продолжением ганкелевой матрицы (6.23). Как было показано в гл.2, подобные продолжения матриц над бесконечным полем могут

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

Обратное ФМС-преобразование На четвертом этапе выполняется по быстрым алгоритмам и по существу не отличается от последнего этапа кодирования в частотной области. Отличие состоит лишь в том, что в процессе декодирования находится вектор е, большинство (от п ЛОп~ От) составляющих которого равны нулю.

* Использование ТБЛметода и алгоритма Гаусса иллюст и 6.3. Далее будет приведен пример декодирования иа основе вычисления полу-НОД.



Завершают декодирование - коррекция, сводящаяся к суммированию принятого слова v с вектором ошибки е и вьщеление сообщения (при систематическом кодировании - отбрасывание проверочных символов) .

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

что вероятность перехода одного сообщения в другое под воздействием помех и сбоев аппаратуры пренебрежимо мало.

Итак, можно констатировать следующее: гибридный метод декодирования проще временного, но сложнее частотного. Зато в гибридном

случае, в отличие от частотного, вероятность ложного декодирования значительно ниже, чем при частотном методе, при котором правильность ФМС-преобразования не контролируема (точнее: требует существенных дополнительных затрат).

Пример гибридного декодирования (с помощью алгоритма Евклида и безрекуррентного вычисления особых продолжений ганкелевой матрицы). Рассматривая произведение S (z)o(z), можно, как ив § 2.3, установить, что оно состоит из трех частей - "избытка" Р (z), средней части2(2)= О и "остатка" R{z). Избыток P(z) является полу-НОД

полиномов z" и 5(z), а остаток R{z) - полу-НОД полиномов z"

и 5 (z). Векторы а и могут быть вычислены на основании выражений, аналогичных (2.43) и (2.42):

a=Pz":5;

(6.42 а) (6.426)

Продолжения вниз si и вверх ДО вектора синдромов S, можно найти иэ соотношений, подобных (2.46) и (2.47):

5 =~R: а=-Л: (Р:А); 5 (RiA),

(6.43) (6.44)

При декодировании можно воспользоваться также рекуррентным соотношением типа (2.27).

Если кодовый вектор искажен не более чем в 0,5 т символах, то степень полинома a(z) не превысит величины 0,5т, а его корни будут только простыми- В этом случае период продолжений и вверх и вниз

строго равен q ~ {/ и s\ = 5 . С другой стороны, равенство периода



величине q может использоваться для косвенной проверки результатов вычислений продолжений S в процессе декодирования РС-кода.

Пример 6.8. Для вектора (6.13) компоненты синдрома определяются зависимостями (6.14а). Здесь m = 6.

Найдем полу-НОД i?/для 2и5 = (8,13,7,13,15,15):

U о, о, 0. 0. о, о : 8.13,7,13,15,15 = 9,14(fl,) 1, 6, 15, 6, 8, 8

6, 15,- 6, 8, 8, О 6, И, 5, 1Ь 13, 13

12, 9. 7, 3, 13 (г,);

8,13, 7,13,15,15 : 12,9,7,3,13 = 12,11(2)/ 8, 5, 3, 14, 9

7, 4, 2, 7. 15 7, 4, 2, 13, 8

5, 2 Rj{r2)j.

Воспользовавшись соотношением (6.426), вычислим

2, 5, О, О, О, О, О, О

2, 2, 15, 9, 15, 10,

1, 15, 9, 15, 10, О

1, 1, 14, 8, 14, 9

4, 4, 2, И, 9, О

4, 4, 2, И, 2, 12

15,15,13,7,13,8 = 3,2,5

И, 12 =

Откуда Ojiz) = 5z + 2z + 3.

На основании формулы (6.43) находим продолжение вниз

5, 2, 0. О, 5, 2, 3

R"

О, О, 0. О, О, О, О : 5, 2, 3

9, 6. 7

О, 3, О, О,

3,15, 1

15, 1, О

15, 12, 13

13, 13, о

13. 10, 11

9, 11,

9, 6,

1, 0. 14, И, 9, 5, 12, 1, 9 5*7. 5*8,5*9,5*10,5"II ,5*12 <5i3,5*14 ,5*15

1, 7, о, 1, 13, 14

5, 14, о 5. 2. 3

13, 3, о 13, 10, 11

12, И - Л



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