Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
k-п Кп'^'ПА ^пА ^ ПА ^А’
что противоречит (6.7.60). |
Теорема 6.7.4. При любом S(D) и всех 0 не существует регистра, который генерирует [S (D)]"-1 и имеет длину, меньшую, чем [Сп (D), /п]-регистр, построенный с помощью описанного выше алгоритма.
Доказательство. Проведем индукцию по п. Очевидно, что теорема справедлива при п = 0. Допустим, что она выполняется для любых заданных S (D) и некоторого данного п. Если 1п + 1 = /„, то ясно, что [Сп + j (D), 1п + 1]-регистр имеет минимальную длину среди регистров, генерирующих [S (D)]", поскольку он является самым коротким ре-ристром, генерирующим [S (D)]J-1, а любой регистр, генерирующий [5 (D)]", генерирует также и [5 (D)]^-1. Теперь предположим, что /п + 1 > 1п, так что
[Ca(D)S(D)]nin=daD*-, йпф0.
Рассмотрим какой-либо [В (D), /в]-регистр, генерирующий [S(D)]". Тогда имеем 1в > 1п и согласно лемме 2 из существования
Fz « « 9 Fj
Регистр сдвига. ПЗ
Замечания
при каждом гг, R1 содержит Cn(i), за исключением СПго -1
RZ содержит [?i'Pj]0 R3 содержит в(м)-Лп'><Г! С:. (заметим, что F0- О) элемент намята , содержащий d^
Функции управления
т
d
Поменять
сод ер ж и но
Улл-
Прада вить Я 3 к Я1 а сумму поместить в /?/ Сдвинуть ЯЗ вправо,^ поместив,,i" в краинии левь/й разряд
Сдвинуть R2 вправо и в не го подать Sn+i п+1 -*• п
у^Стоп
Рис. 6.7.4. Реализация PCJIOC-алгоритма для генерирования [5(D)]
271
Of-
[Cn(D), 1в\- и [В (D), /^-регистров следует существование при некотором /> 0 такого [F (D), 1В—/]-регистра, для которого
[F(D)S(D)]n~lj /^0.
Согласно лемме 3 (п—/) — (lB—j)^kn—lhn, Поэтому Ьв^п—
— (kn—lhn) = U+\. Тогда [B(D), /в]-регистр не короче, чем 1п + il-регистр, что завершает доказательство. |
Блок-схема, представленная на рис. 6.7.4, автором которой является Месси (1968), предлагает способ реализации алгоритма. Отметим, что соотношение (6.7.49) используется здесь в качестве критерия для указания изменения 1п и kn. Длина регистров /, представленных на рис. 6.7.4, должна быть достаточной для хранения многочлена связей самого длинного ожидаемого регистра. Выберем для декодирования БЧХ-кодов L = d — 2 и расположим а (D), кроме коэффициента сг0 = в R1 слева. Можно выбрать j — \_(d—l)/2_j и тем самым
гарантировать исправление всех комбинаций не более чем [_(d—1)/2___|
ошибок. В случае двоичных БЧХ-кодов элементы {S,} и {С,} являются элементами GF (2т) и каждый из регистров, представленных на рис. 6.7.4, может быть реализован при «помощи т двоичных регистров. Устройство, выполняющее умножение в GF (2т), можно сделать так, как показано на рис. 6.6.5. Легко видеть, что сложность оборудования, необходимого для регистров и умножителей, пропорциональна md. Также нетрудно убедиться, что время, необходимое для нахождения сг (D), пропорционально md [или чуть больше, что зависит от способа вычисления (d*)-1]. Безусловно, при построении такого устройства необходимо разрешить большое число технических вопросов; важно заметить, однако, что для такого устройства необходимо поразительно мало оборудования и поразительно мало вычислительного времени. Берлекэмп (1967) также доказав, что для двоичных кодов с г = 1 и при нечетных п величина dn всегда равна нулю. Использование этого обстоятельства, по существу, вдвое сокращает вычислительное время для нахождения а (D). На этом мы закончим обсуждение второго этапа процедуры декодирования БЧХ-кодов.
Теперь коротко рассмотрим реализации этапов 1, 3 и 4 для БЧХ-декодера. На этапе 1 можно вычислять элементы синдрома следующим способом:
5г= 2 ^а(г+г)'! = (”-(^-1аГ + г+^-2)аГ+г+г/л._з)аГ+г' + ...+г/о).
п~0
Таким образом, возможный путь вычисления S, состоит в сложении всех последовательно принятых символов в первоначально пустом регистре; сумма затем должна быть умножена на аг+1 и возвращена в регистр, ждущий следующего принятого символа.
Этап 3 легче всего реализовать при помощи процедуры Ченя (1964). Если число ошибок не превышает [_(d—1)/2______!, то a(D), вы-
численный на этапе 2, определяется соотношением (6.7.21), и ошибка 272
в n-й позиции (т. е. гпфО) произойдет тогда и только тогда, когда
о (а-п) = 0, или, что то же самое, тогда и только тогда, когда
Если обозначить
то
и при любом п
2 o,~ni = 0.
г — О
Oi.n^-Oi a~ni,
Oi,N-i =ага-(Л,-1)/ = агаг
&i, п — 1 — ®i, n
(6.7.63)
(6.7.64)
(6.7.65)
(6.7.66)
Рис. 6.7.5. Шаг 3 при декодировании БЧХ-кода: нахождение позиций ошибок.
Первоначально в регистре хранятся аь a, ____________ l)/2 _j - Затем производится
умножение и проверка гипотезы гм— 1 =^’ после этого производится умно-
жение и проверка гипотезы гм—2 = 0> и так Далее до г0 = 0.
