способами. Согласно лемме 14.5.2, каждый начальный сегмент кодового слова, имеющий ненулевой символ в первом кадре, может войти не более чем в («о-*») (*o-i) различных система-

тических сЕ?ерточных (щ, о)-кодов. Следовательно, если

(m+I) (п„-/г„) (/e„-I)(m+l) (По-о) /ее

то должен существовать хотя бы один код с минимальным расстоянием, большим р. Теорема доказана. □

Следствие 14.5.4 (граница Гилберта). Для двоичных сверточных кодов

Доказательство. При <? = 2 теорема утверждает, что

d (п, R)

2 (")2"-.

Следовательно,

d (п. R)

(l/«)log Jj (1)1 - R.

Отсюда, используя теорему 14.4.1 и переходя к пределу, получаем утверждение следствия. □

ЗАДАЧИ

14.1. Рассмотрегь (31, 27)-код Рида-Соломона.

а. Сколько кодовых слов имеет вес 5?

б. Сколько конфигураций ошибок имеют вес 3?

в. Какая часть конфигураций ошибок веса 3 не обнаруживается?

всех сверточных кодов с длиной блока п можно сосчитать общее число начальных кодовых слов, вес которых не больше р и которые имеют ненулевой символ в первом кадре. Если их число меньше числа систематических сверточных кодов, то существует хотя бы один код, у которого минимальное расстояние больше р.

Так как систематический сверточный {щ, о)-код описывается («о - Ю К порождающими многочленами степени не выше т и каждый такой многочлен может быть выбран q+ различными способами, то число таких кодов равно q"+> ("о-Ло) Ло.

Ненулевые -последовательности веса, не превышающего р, можно выбрать

ЗАМЕЧАНИЯ 521

г. Пусть слово выбрано случайно (с одинаковыми вероятностями для всех его значений). Какова вероятность того, что оно будет декодировано?

14.2. Используя тождество Мак-Вильямс и табл. 5.3, найти распределение весов кода, дуального расширенному (24, 12)-коду Голея. (В действительности расширенный (24, 12)-код Голея является дуальным самому себе; такие коды называются самодуальньши.)

14.3. Доказать, что в линейном блоковом коде над GF (2) либо не существует слов с нечетным весом, либо половина слов имеет нечетный вес.

14.4. Простейшим двумерным двоичным кодом с N строками и М столбцами является код, исправляющий одну ошибку. В каждой строке и в каждом столбце он имеет по одному проверочном символу. Минимальное расстояние кода равно 4. Предположим, что этот код используется для обнаружения ошибок в двоичном симметричном канале с переходной вероятностью q. Какова вероятность необнаруженной ошибки? При вычислениях необходимо учитывать лишь член с минимальной степенью q.

14.5. Исправляющий t ошибок (к, й)-код Рида-Соломона имеет минимальное расстояние d*=n-k -f 1 = 2 -f 1 и число слов веса d* равно Л, =

=a)(7-»-

а. Сколько существует конфигураций ошибок веса / -f 1?

б. Непосредственным подсчетом найти число конфигураций ошибок веса t-\- \, которые декодер, декодирующий в пределах радиуса упаковки, декодирует неправильно.

в. Какая доля конфигураций ошибок веса t -Ь I декодируется неправильно?

г. Дать численный ответ на вопрос п. в в случаях q - Ъ2, t = 5 и (? = 64, ; = 6.

14.6. Оценить сумму компонент распределения весов 1]"=оГ

14.7. Исправляющий t ошибок (к, /г)-код Рида-Соломона имеет минимальное расстояние d* = n-k+l=2t -f I и число слов веса d* равно Л, = (,) X X (<? - 1).

а. Сколько существует конфигураций пакетов ошибок веса t -f- 1 и длины f -f 1?

б. Найти число конфигураций пакетов ошибок веса t + \ и длины t-{- \, которые декодер, декодирующий в пределах радиуса упаковки, декодирует неправильрго.

в. Какая доля конфигураций пакетов ошибок веса t + I и длины t-Ь 1 декодируется неправильно?

г. Дать численный ответ на вопрос и. в в случаях <? = 32, = 5 и (? = 64, t=6.

14.8. Пусть код Рида-Соломона над GF (2") используется как код, исправляющий многократные пакеты ошибок над GF (2). Рассмотреть декодирование принятых слов, которые находятся вне радиуса упаковки кода.

14.9. Порождающие многочлены двоичного сверточного (8, 4)-кода равны

Найти его свободное расстояние, свободную длину и число единиц во входной последовательности, соответствующей пути с длиной, равной свободной.

ЗАМЕЧАНИЯ

Распределение весов кода с максимальным расстоянием было найдено независимо Ассмусом, Мэттсоном и Турином [1965], Форни [1966], Касами, Лином иПитерсоном [1966]. Тождество Мак-Вильямс было выведено ею в 1963 г. В этой же статье она дала свою трактовку связи между распределением весов и вероят-

) См. работу: Tsfasman М. А., Vladuts S. С, Zink Th. Modularcurves, Shimura curves and Goppa codes, better than Varshamov-Gilbert bound. - Math. Nachr., 1982, Bd 104, S. 13-28. Она существенно опирается на работу: Гоппа В. Д. Коды на алгебраических кривых.-ДАН СССР, 1981, т. 259, № 6, с. 1289-lf90. - Прим. ред.

ностыо ошибки декодирования. Иная трактовка принадлежит Форни [1966] и Хунтуну и Михельсону [1977]. Использование диаграммы состояний для нахождения распределения весов сверточного кода предложил Витерби [1971].

Нижняя граница минимального расстояния блоковых кодов опубликована Гилбертом [1952]. Элайс никогда не публиковал свою верхнюю границу; впервые она появилась в его лекциях в 1960 г. Известны и лучшие верхние границы, но они доказываются гораздо сложнее. Наилучшая известная верхняя граница найдена Мак-Элисом, Родемичем, Рамсеем и Велчем [1977]. В недавно выполненной в СССР.работе ) показано, что в GF (49) граница Гилберта может быть улучшена. .