Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
ствует кодовому слову. Поскольку при каждом циклическом сдвиге кодового слова также получается кодовое слово, то можно, сдвигая полином г/(‘> (D) назад к у (D) и одновременно полином Bt (D) на
i позиций в том же направлении, убедиться, что многочлен у (D) —
— Rdn_i Ю‘ Bt (D)] также соответствует кодовому слову. Иначе говоря, многочлен Rdn_{ Юс Bt (D)] при заданном у (D) и при любом
i определяет возможную шумовую последовательность, которая могла бы наложиться на переданное слово, давая в итоге у (D). Из (6.10.10) следует, что каждый из полиномов Bt (D) имеет степень не больше N — L—1 и потому Rdn_i lD‘Bi(D)] соответствует последовательности, у которой все ненулевые символы циклически следуют друг за другом в ряду, состоящем не более чем из N — L символов.
z — (1, 0, 0......0,0, 1),
(6.10.8)
(6.10.10)
(6.Ю.9)
310
Теперь допустим, что передано х (D) и на него наложился пакет из b^N — L ошибок в промежутке от zt до (или до zi+b_!_w
при модифицированном определении пакета). Этот пакет можно представить с помощью многочлена Rdn_i №1 Р (D)], где степень |3 (D) равна b — 1; при этом получим у (D) = xD) + Rdn_x Ю‘ Р (?>)]. Тогда имеем yW (D) = (D) + |3 (D), где х<-1) (D) — циклический
сдвиг а: (D). В силу определения (6.10.10) это означает, что |3 (D) =
= Bt (D).
Из проведенных рассуждений вытекает следующая последовательность действий оптимального декодера: нахождение многочленов Bi (D) для всех i; выбор значения г, при котором Бг (D) соответствует
Рис. 6.10.3. Устройство для вычисления Bj(D) при каждом /.
самому короткому пакету, и затем сложение Rdn_1 Ш'В; (D)] при найденном значении i и у (D). Схема устройства, вычисляющего Bt (D) при любом i, представлена на рис 6.10.3. Можно заметить, что это — просто устройство, производящее деление у (D) на g (D), и что после поступления у0 в левый разряд регистра сдвига, в его разрядах будет храниться как раз полином В0 (D) (члены более высокого порядка находятся справа). Однако если после этого вновь сдвинуть регистр, не подавая при этом на его вход символы принятой последовательности, то в разрядах регистра будет храниться многочлен Rg(D) Юу (D)], который, как нетрудно убедиться, как раз совпадает с Bn-i Ф). Путем подобных последовательных сдвигов порождаются ¦Bn_2 (D), Bn-з (D), ..., Вг (D). Можно также убедиться, что самый простой способ нахождения Bt (D), соответствующего наименьшему пакету, состоит в нахождении самой длинной последовательности нулей в точке А после поступления слева в регистр сдвига у0. Наконец, для выполнения декодирования необходимо, чтобы регистр сдвига совершил цикл более чем N раз; после того как в А появится самый длинный отрезок нулей, в регистре будет содержаться пакет ошибок.
Иногда желательно несколько видоизменить такой декодер. Например, можно не рассматривать модифицированные пакеты, так как они обычно гораздо менее вероятны, чем обычные пакеты. Также любой пакет, имеющий длину больше заданной, можно относить к обнаруживаемым ошибкам. Наконец, при определении, какой из многочленов В t (D) следует использовать, декодер может принимать во внимание как число ошибок в пакете, так и длину пакета.
Теперь исследуем корректирующую пакеты способность b цик-
311
лических кодах, где 6 — наибольшее целое число, такое, что все пакеты длины 6 или меньше могут быть исправлены оптимальным декодером. Если корректирующая пакеты способность циклического кода равна 6, то существует некоторый пакет длины 6+1, который может быть декодирован как некоторый другой пакет длины 6 + 1 или меньше; следовательно, сумма этих пакетов является кодовым словом. Произведя циклический сдвиг этого кодового слова так, чтобы пакет неисправимых ошибок начинался с нулевой позиции, представим это сдвинутое кодовое слово в виде
х (D) — В (D) + Dm В' (D), (6.10.11)
где степень В (D) равна 6 и степень В'о не больше Ь.
Так как х (D) — кодовое слово, то его можно представить в виде А (D) g(D), где степень A (D), равная, например, а, представляется в виде разности степени члена самого высокого порядка в DmB' (D) и N— L. Поэтому, для того чтобы степень В’ (D) не превосходила 6 + 1, необходимо, чтобы коэффициенты при D1 в многочлене А (D) g (D) были бы равны нулю для
6+l<t<W —L + a —6—1. (6.10.12)
Другими словами, для того чтобы существовал неисправимый пакет длины 6+1, необходимо, чтобы существовали некоторое целое число a, 0^a=sCL, и некоторый ненулевой многочлен А (D) степени а, такой, что коэффициенты членов многочлена А (D) g (D) равны нулю при всех г, удовлетворяющих (6.10.12). Длиной исправимого пакета циклического кода называется такое наименьшее Ь, при котором такое решение существует. При любых заданных а и b нахождение такого решения эквивалентно нахождению совокупности (а — .1) коэффициентов Лъ Ла_х, которые удовлетворяли бы N — L + а—26—1 линейным уравнениям, указанным в (6.10.12). Легко видеть,
