Главная Помехоустойчивое кодирование 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.0206 |