ЗАДАЧИ 283

Перебирая все корни этих уравнений, получаем, что А С а, а", а, a а*, а**}.

Но в этом множестве не содержится ни одного куба. Таким образом, (Л, 0) и (О, Е) не могут одновременно удовлетворять нашим ограничениям. Это завершает доказательство теоремы. □

ЗАДАЧИ

8.1. Исходя из определения пары преобразования Фурье {Ci}-<-*{Cj,), доказать следующие стандартные свойства дискретного преобразования Фурье.

а. Линейность:

\aCi-\- Ьс\\\аС.-\-ЬС.\.

б. Свойство циклического сдвига:

- {с/С.}. :. . -

в. Модульность: •

8.2. Доказать, что преобразование Фурье сигнального вектора ci = a содержит единственную ненулевую спектральную компоненту. Что происходит, если / = О? Доказать, что спектр вектора с единственной ненулевой компонентой всюду отличен от нуля.

8.3. Доказать, что iJj = Ffij тогда и только тогда, когда

ft=0

8.4. Сколько идемпотент.ов содержится в кольце многочленов по модулю многочлена х - 1? Перечислить их.

8.5. Основная теорема алгебры гласит, что многочлен степени d имеет не более d корней. Используя эту теорему, доказать границу БЧХ для кода Рида-Соломона, спектр {Cj} кодовых слов которого удовлетворяет условию

= О для всех / > п - k. 8.6.а. Найти порождающий многочлен для двоичного расширенного (42, 25, 7)-кода БЧХ. Построить кодер.

б. Найти порождающий многочлен расширенного (17, 9, 7)-кода БЧХ над GF (4). Построить кодер.

8.7. Пусть G (л:) = л:-f х-\- 1 - многочлен Гоппы для (32, 22, 5)-кода Гоппы. Разработать правило кодирования и процедуру декодирования.

8.8. Пусть G {х) = + х-\- а-многочлен Гоппы для (16, 8, 5)-кода Гоппы, где а - примитивный элемент поля GF (16). Найти проверочную матрицу кода.

8.9. Модифицируя несистематический кодер для (15, 7)-кода БЧХ, построить кодер для (15, 8)-кода Препараты.

8.10. Код Препараты можно декодировать с помощью алгоритма Берлекэмпа-Месси для двоичных кодов, используя три итерации (г= 1, 3, 5) и выбирая А к В так, чтобы Дв = 0. Выписать уравнения, для А -а. В, которые должны быть разрешены при таком алгоритме декодирования.

8.11. Двоичный (63, 52)-код Препараты может быть определен при помощи своего спектра следующим образом: С = О, Сз = Л, С-~ В, где либо

V) А {1, а», а", оР-, а»*, а«, ««, of\ и В = О, либо

2) В {1, ofi, «18 т, «38. «« а} и Л =

а остальные спектральные компоненты удовлетворяют только условиям сопряженности.

а. Доказать, что этим кодом можно закодировать 52 информационных

бита.

б. Исследуя уравнение

Л* + + S\A + [SfSg + 4 + S\SI + S%] + S?fi = О

и изучая его корни, доказать, что минимальное расстояние рассматриваемого кода не меньше 5.

ЗАМЕЧАНИЯ

Спектральное описание кодов, контролирующих ошибки, можно найти в очень ранних работах, хотя связь с преобразованием Фурье не была сразу осознана. Спектральный декодер использовался в основополагающей работе Рида и Сс-лэмона [1960] для нахождения минимального расстояния предлагаемых кодов, но, так как описанный в этой работе декодер не имел практического значения, спектральные методы не изучались еще долгие годы. Мэттсон и Соломон [1961] ввели спектральный многочлен, сыгравший большую роль в теоретических исследованиях, но смысл спектрального многочлена как преобразования Фурье вновь не был осознан, и тесная связь теории корректирующих кодов с обработкой сигналов опять оЬталась скрытой. Близкие идеи разрабатывал Мандельбаум [1979], но на языке интерполяции.

Преобразование Фурье над конечными полями рассматривал Поллард [1971 ], а использовать его в теории кодов, контролирующих ошибки, предло.жил Гор [1973], работа которого получила дальнейшее развитие в работах Ченя и Чоя [1975] и Лемпеля и Винограда [1977]. Приведенное в данной главе доказательство границы БЧХ частично использует перенесенное в частотную область доказательство Ченя [1972].

Идея расширения кода широко известна. Расширенные коды Рида-Соломона рассматривал Вулф [1969]. Конструкции расширения кодов БЧХ были предложены Андриановым и Сасковцом [1966], Слоэном, Редди и Чинем [1972]; Касахарой, Сугиямой, Хирасавой и Намекавой [1975]. Описание конструкций в виде преобразований дал Блейхут [1980 .

Альтернантные коды были введены Хельгертом 1974], который дал пм такое название потому, что проверочная матрица этих кодов может быть записана в виде так называемой (в математической литературе) альтернантной матрицы. К альтернантным кодам относятся открытые ранее коды Гоппы [1970]. Дельсарт [1975] предложил определять альтернантные коды как ограничения на подполе модифицированных кодов Рида-Соломона, так что его определение значительно отличается от исходаюго.

Коды Препараты имеют интересную историю. Препарата [1968] открыл этот класс кодов в процессе исследования свойств наименьшего кода в классе, а именно (15, 8, 5)-кода, известного под названием кода Нордстрома-Робинсона [1967]. Два последних автора построили этот нелинейный (15, 8, 5)-код с помощью ЭВМ как расширение ранее построенного Нейдлером нелинейного (12, 5, 5)-кода [1962] или нелинейного (13, 6, 5)-кода Грина [1966]. В свою очередь коды Препараты стимулировали открытие еще более сложных нелинейных кодов, а именно низкоскоростпых кодов Кердока 11972] и исправляющих три ошибки кодов Геталса 11976],

ГЛАВА 9

АЛГОРИТМЫ, ОСНОВАННЫЕ НА СПЕКТРАЛЬНЫХ МЕТОДАХ

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

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

9.1. СПЕКТРАЛЬНЫЕ МЕТОДЫ ДЕКОДИРОВАНИЯ

Вернемся к задаче декодирования кодов БЧХ и будем интерпретировать с частотной точки зрения уже рассмотренные вопросы. Используя преобразование Фурье, разработаем новые процедуры декодирования.

Принятое слово v с компонентами Vt = с,- 4-ег, i = О, п - 1, представляет собой сумму кодового слова с и вектора ошибок е. Декодер должен так обработать слово v, чтобы удалить из него вектор ошибок е; после этого из с выделяется ннформа-

*) Имеется в ввду исправление векторов ошибок, вес которых превышает половину конструктивного расстояния кода. - Прим. юерее.