Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Давайте посмотрим, что можно сказать о поведении двоичных БЧХ-кодов в пределе при N-+- оо. На время допустим, что m (d— 1)/2 является хорошей оценкой для числа проверочных символов в коде, так что
где R — скорость передачи в двоичных символах. Так как т> ^ log2(jV+ 1),то при фиксированном R величина (d—1)/2 N должна стремиться к 0 при стремлении N к бесконечности. Поэтому число ошибок, которые можно исправить описанным алгоритмом декодирования, в конце концов становится меньше среднего числа ошибок в канале. Питерсон (1961) точно вычислил число проверочных символов в различных двоичных БЧХ-кодах; из его результатов следует, что при
-R,
2 N
275
фиксированном R величина (d — 1)/2 N стремится к нулю с возраста- • нием N. Вместе с тем это уменьшение наступает при таких больших значениях N, что этот предел мало значит для практики.
Коды Рида-Соломона (1960) представляют собой интересный частный класс БЧХ-кодов с параметром т, равным 1; иначе говоря, в этом случае расширенное поле, в котором определено а, совпадаете полем символов для кодовых букв. Тогда минимальный многочлен для а‘ равен D — а1, так что имеем
r + d-2
g(D)= П {D—а1').
i = г
Поэтому указанный код имеет d — 1 проверочных символов и минимальное расстояние d. Нетрудно убедиться, что ни один групповой код с такими же объемом алфавита, длиной блока и числом проверочных символов не может иметь большего минимального расстояния, поскольку если выбрать все информационные символы, кроме одного, равными 0, то соответствующее кодовое слово будет иметь не более d ненулевых символов.
Так как в коде Рида-Соломона длина блока N равна q — 1 или делителю числа (q — 1), то нетрудно заметить, что эти коды полезны лишь при больших объемах алфавита. Их можно эффективно использовать в непрерывных по времени каналах, где входной алфавит составляет огромное множество сигналов. Форни (1965) эффективно использовал их также в каскадной схеме, где символы кода Рида-Соломона являлись кодовыми словами в меньшем внутреннем коде. Форни показал, что такие коды можно использовать при скоростях передачи, как угодно близких к пропускной способности. Вероятность ошибки для них экспоненциально убывает с ростом длины блока, а сложность декодирования пропорциональна малой степени длины слова. Коды Рида-Соломона можно также непосредственно использовать в канале с малым входным алфавитом путем представления каждой буквы в кодовом слове в виде последовательности букв канала. Эта техника полезна для применения в каналах, где ошибки объединяются в группы, поскольку число операций декодирования зависит лишь от числа последовательностей выходных символов канала, содержащих ошибки.
6.8. СВЕРТОЧНЫЕ КОДЫ И ПОРОГОВОЕ ДЕКОДИРОВАНИЕ
Сверточные коды, которые будут определены в этом параграфе, отличаются от всех ранее рассмотренных кодов тем, что они являются неблоковыми кодами. Прежде чем определять эти коды, рассмотрим простой пример сверточного кода, иллюстрируемый рис. 6.8.1. В каждую единицу времени в кодер поступает новый двоичный символ источника ип, а каждый из ранее поступивших символов источника сдвигается в регистре сдвига на один разряд вправо. Новый символ источника поступает непосредственно в канал, так что xhX) ~ ип. За каждым таким информационным символом следует проверочный символ
— ип ф W,J_3 © ип — 4 © Wrj —5 = (6.8.1)
276
— xjj1* ® X^n — 3 *
Kn — 4 — 5 •
(6.8.2)
Предполагая, что в начальном положении регистр сдвига заполнен нулями и что передача начинается с иъ имеем ип — 0, хл1’ = 0 и xh2) — 0 при я<0. Опишем теперь очень простой метод декодирования этого кода для случая передачи по двоичному каналу — пороговое декодирование.
Пусть х = д;^) х^ х(а2)
-у[1) У[г) У[Х) у[2) -2(1) ,(2) 2(1) 2(2) *1 *1 2 2
— передаваемая последовательность,
— принятая последовательность,
— шумовая последовательность,
'О ft) (О
z3 ?2 xt
Рис. 6.8.1. Пример сверточного кода.
где z = У®х. Как и для кодов с проверкой на четность, определим синдром S = S j S 2 ... с помощью формулы
S П = Уп2) Уп— 3 © Уп- 4 ф Уп-5.
,0),
(6.8.3)
Следовательно, <S„ = 0, если выполнена п-я проверка на четность, вычисленная в приемнике, и Sn = 1, в противном случае. Из (6.8.2) также имеем
С -<2) , JD j__(l) . 1,П)
-\-Zn ~\-Zn—Z -t-Zn—4 ~Ггп — 5-
п^16, получаем:
(6.8.4)
(6.8.5)
Расписывая эти равенства при 1
S2=Z<2)®Z<1),
53 = z<2) © z'g1*,
54 = z<2> ®гП>(
S5=z<2»®44 6 S6 = z<2>®zn>g
Теперь остановимся на декодировании первого информационного символа и1; декодирование эквивалентно определению, является ли zi1’ единицей или нулем. Отметим, что величины Sb S4, S5 и Se не-
