= 2"«(Р) (/7 -L 1 -/7)",

что доказывает лемму. □

Лемма 7.9.3. Для любого множества М различных ненулевых двоичных слов длины 2т сумма W весов слов удовлетворяет неравенству

W2mk{M--2">"0)),

где - любое число в интервале (О, 1/2).

Доказательство. В силу леммы 7.9.2 в рассматриваемом множестве для любого % из интервала (О, 1/2) число последовательностей длины 2т, имеющих вес не более 2тк, удовлетворяет неравенству

1=1

Таким образом, для каждого "к существует не менее М -• 2" () слов веса более 2тк. Следовательно, сумма весов М слов множества удовлетворяет неравенству

W2mk{M -2"0>).

Лемма доказана. □

Теорема 7.9.4. Пусть для каждого фиксированного R (О < < R < 1/2) К = [2NR]. Тогда при каждом целом т (п, к)-код Юстесена (п = 2mN, k = 2тК) имеет скорость не менее R и минимальное расстояние, удовлетворяющее неравенству

d*ln 5s (1 - 2R) (1/2) - о (1)),

где о (1) - функция от п, стремящаяся к нулю при / -> со.

Доказательство. Поскольку К = [2NR], то К 2NR и, следовательно, скорость кода /C/(2iV) превышает R. Кодовое слово с содержит не менее N - К + I различных ненулевых столбцов, т. е. не менее N - /С + 1 различных ненулевых двоичных последовательностей длины 2т. Далее,

К + lN {I- 2R).

Выберем теперь X = loga [(1 - р)/рУ, тогда

Й36 7. кОДЬ! БОУЗА-ЧОУДХУРИ-ХОКВИНГЁМА

Выберем N (1 - 2R) этих последовательностей длины 2т. Тогда условия леммы 7.9.3 удовлетворяются, и из этой леммы следует оценка

d*W2mk[N(\-2R)-22",

Полагая

приходим к утверждению теоремы. □

Из теоремы 7.9.4 следует важность кодов Юстесена. Эта теорема гласит, что для достаточно больших п выполняется неравенство

d*lnQ,\\ {\ -2R).

При фиксированном R < 1/2 отношение d*/n отделено от нуля при п оо. Коды Юстесена являются единственным известным классом кодов с заданной в явном виде конструкцией, для которых установлено это свойство ).

Коды Юстесена имеют скорость, меньшую 1/2. Коды с большей скоростью можно получить, выкалывая компоненты исходного кода. Получаемые таким образом коды также представляют только теоретический интерес как пример кодов, имеющих хорошие характеристики при очень больших длинах.

ЗАДАЧИ

7.1. Найти порождающий многочлен g {х) для исправляющего двойные ошибки двоичного кода длины и=31. Использовать примитивный элемент к и примитивный многочлен р {х) = х -\- х -\- I.

7.2. Найти кодовое слово, соответствующее информационному многочлену ах -f для кода Рида-Соломона длины 15, исправляющего одиночные ошибки и построенного по примитивному элементу а поля GF (2).

7.3.а. Найти порождающий многочлен g (х) для исправляющего двойные ошибки кода Рида-Соломона, основываясь на примитивном элементе к поля GF (2*) и полагая /о = I.

Коды Юстесена отнюдь не являются единственным подклассом обширного класса каскадных кодов, обладающих тем свойством, что при увеличении п оба параметра кода - и скорость, и отношение расстояние/длина - отделены от нуля. Подчеркиваемая автором «явность» конструкции Юстесена в равной мере может быть отнесена и к конструкции Зябл она линейных каскадных кодов, если допустить несущественный перебор внутренних кодов, ле}кащих на границе Варшамова-Гилберта (см. Зяблов В. В. Оценка сложности построения двоичных линейных каскадных кодов. - Проблемы передачи информации, 1971, Вып. I, с. 5-\3). - Прим. ред.

б. Используя метод декодирования Питерсоиа-Горенстейна-Цирлера (ПГЦ), найти многочлены локаторов ошибок, локаторы и значения ошибок, если Si = V?, S2 =0, S3 = «8 и S4 = «2.

в. Решить задачу п. б, используя алгоритм Берлекэмпа-Месси.

7.4. В § 7.1 был получен порождающий многочлен (15, 6, 7)-кода БЧХ над полем GF (4). Найти порождающий многочлен (15, 7, 7)-кода БЧХ над тем же полем.

7.5. Исправляющий двойные ошибки (15, 7)-код БЧХ имеет порождающий многочлен g (л;) = л; + л;+ л; + л;* + 1. Комбинируя идеи декодера Меггитта и алгоритма ПГЦ, построить декодер, работающий по принципу декодера Меггитта, но использующий последовательность компонент синдрома Sj, Sg, S3, S4 в расширении поля, а не сам синдромный многочлен s (л;).

7.6. Найти порождающий многочлен (63, 55, 5)-кода над GF (8).

7.7. Предположим, что задан код Рида-Соломона с минимальным расстоянием 2 -Ь I и что V - целое число, меньшее /. При декодировании требуется исправлять все ошибки кратности до v включительно и обнаруживать ошибки с кратностями в пределах от v -f- 1 до 2/ - v. Как это сделать, используя алгоритм Берлекэмпа-Месси? Решить ту же задачу в случае кода БЧХ.

7.8. Показать, что каждый код БЧХ является подкодом над подполем некоторого кода Рида-Соломона с тем же конструктивным расстоянием. В каком случае скорость подкода над подполем будет такой же, как и у исходного кода Рида-Соломона? Найти в несистематическом (7, 5)-коде Рида-Соломона 16 информационных последовательностей, которые порождают кодовые слова (7, 4)-кода Хэмминга.

7.9. Найти порождающий многочлен для исправляющего двойные ошибки (23, 12)-кода БЧХ над GF (2). (Заметим, что найденный код представляет собой код Голея; он является примером кода БЧХ, у которого минимальное расстояние больше конструктивного.)

7.10. По троичному каналу в каждый момент времени передается один из трех символов: синусоидальный импульс с нулевой фазой, синусоидальный импульс с фазой 120° и синусоидальный импульс с фазой 240°. Обозначим множество передаваемых символов через {О, 1, 2} и будем считать, что ошибки в канале происходят случайно и с равными вероятностями.

Построи~ь исправляющий тройные ошибки код длины 80 для передачи по такому каналу, учитывая, что примитивный многочлен степени 4 над GF (3) записывается в виде

j,()=4++2.

Какова скорость полученного кода? Как использовать этот код для передачи блоков двоичных данных?

7.11. Память на магнитной ленте хранит байты из восьми битов как один 256-ичный символ. Построить в этом алфавите исправлякщий одиночные ошибки (15, 13)-код над GF (25бк а также схему декодера.

7.12. Многочлен -\-]?-\- является примитивным многочленом надО/(2). Примитивный элемент а = у с минимальным многочленом у" + / + 1 используется для построения исправляющего двойные ошибки кода БЧХ длины 22» = 1 048 576.

а. По принятому слову вычислены компоненты синдрома

Si=y, у-]-у-{-у.

Найти остальные компоненты синдрома.

б. Найти многочлен локаторов ошибок.

в. Найти позиции ошибок или ошибки.

7.13.а. Найти пороадающий многочлен g (х) двоичного кода БЧХ длины и= 15 с d = 7. При построении использовать примитивный элемент к, /о = 1 и неприводимый многочлен р (х) = } -\- х-\- 1.