Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Последнее предполагает использование схемы рис. 6.7.5 для реализации критерия (6.7.63) сначала для n — N—1, затем для n = N — —2 и т. д.
Как уже было указано, в случае двоичных БЧХ-кодов этап 4 в процедуре декодирования не является необходимым. Поэтому принятые символы могут выходить из декодера синхронно с операциями, производимыми устройством на рис. 6.7.5, если на выходе устройства просто производится сложение уп и zn по модулю 2 при изменении п от N — 1 до 0, что позволяет получить переданное кодовое слово, если произошло не более |___(d — 1)/2___[ ошибок.
Если при использовании двоичного кода произошло более чем l_(d—1)/2 J ошибок, то может произойти одно из следующих трех событий. Во-первых, длина [a (D), Н-регистра, который был на
этапе 2, могла быть больше чем |_____(d— 1)/2__|. Если в устройстве на
рис. 6.7.4 / = [_ (d— 1)/2_1, то в этом случае нельзя найти а (D), но
довольно просто обнаружить это событие. Во-вторых, вполне возможно
также, что I, найденное на этапе 2, не превышает |_______(d—1)/2___I, но
а (D) не имеет I корней в GF (2т). В этом случае на этапе 3 будет
273
сделано меньше, чем I исправлений, но декодированная последовательность не будет представлять собой кодовое слово. Это вновь может быть легко обнаружено или путем подсчета числа исправлений, или путем проверки, является ли декодированная последовательность кодовым словом. Наконец, вполне возможно, что [a (D), Л-регистр
имеет длину _______(d— 1)/2__| и что при декодировании будет найдено
I ошибок. В этом случае декодированная последовательность будет кодовым словом, которое отличается от принятой последовательности
более чем в |_(d— 1)/2____J позициях. При этом нельзя обнаружить
ошибку декодирования, но мы по крайней мере знаем, что декодер принял в двоичном симметричном канале решение по максимуму правдоподобия.
Обратимся теперь к отысканию значений ошибок (этап 4) в процессе декодирования недвоичных БЧХ-кодов. Определим многочлен А (D) в (6.7.22) как
Л(Я)= %VJUl П (I —t/,D). (6.7.67)
/= 1 / ф j
Тогда согласно (6.7.25) А (D) определяется следующим образом через o(D):
4(D) = [a(?)S(D)]g-2. (6.7.68)
Многочлен А (D) можно найти непосредственно из (6.7.68) или, что более красиво, его вычисление можно включить в виде составной части в итеративный алгоритм нахождения с (D). В частности, из начальных условий А-\ (D) = —D-1 и A0(D) = 0 вычислим при п^О многочлен Лп + 1(?>) согласно формуле
Лл+1 (D) = An(D)~-^Dn~kn Ahn (D), (6.7.69)
dkn
где dn и kn определяются (6.7.34) и (6.7.35). Для этого в блок-схему на рис. 6.7.4 необходимо включить два дополнительных регистра; никаких дополнительных логических элементов управления, по существу, не требуется, поскольку операции, производимые регистрами при вычислении Ап (D) и Dn~kn Ahn (D), аналогичны операциям,
производимым регистрами при вычислении Сп (D) и Dn~kn Chn (D). Доказательство того, что [Сп (D)S (D)]?-1 == Ап (D) при любом почти аналогично доказательству теоремы 6.7.3 и это приведено в виде задачи 6.35.
После нахождения А (D) нетрудно убедиться, что согласно (6.7.67)
A (U]~l) = VjUrf П (1 -VlVfX). (6.7.70)
1ф }
Можно упростить правую часть (6.7.70), если ввести производную a (D) = о0 + ajD + ... + aeDe:
a' (D) = CT1 + 2a2D + ... + eaeDe_1. (6.7.71)
274
Легко реализовать вычисление ст' (D) по о (D); если q является степенью 2, то о' (D) равна сумме членов ст (D) в нечетных степенях, деленной на D, так как
о (D) = П (1 — t/j D),
то получим (см. задачу 6.36)
е
a'(D) = - 21 Uj п [1 ~utD]
о’(иг1)= -Uj п (I-и
(6.7.72)
Подставляя (6.7.72) в (6.7.70), получаем
(6.7.73)
Используя определения Uj и Vj, данные в (6.7.16), получаем следующую формулу для нахождения каждого из ненулевых шумовых символов zn:
Каждая из трех функций, входящих в правую часть (6.7.74), может быть последовательно вычислена для всех п при изменении п от N — 1 до 0 при помощи устройства того же типа, что и на рис. 6.7.5.
На этом заканчивается обсуждение декодирования БЧХ-кодов. Главный вывод состоит в том, что хотя по замыслу это декодирование является сложным, оно очень просто в смысле времени декодирования и требуемой сложности оборудования. Если не считать ячеек памяти, необходимых для запоминания принятого слова, и устройства вычисления обратных элементов в GF (qm), то количество требуемого оборудования пропорционально md. Время декодирования на этапе 2 пропорционально md, а на этапах 3 и 4 пропорционально tnN.
