ЗАМЕЧАНИЯ 397

11.2. Построить алгоритм быстрой свертки для кодирования (15, 11)-кода

PJJдa Соломона с порождающим многочленом g (х) = + ах? -j- ах +

+ а=* л: + а".

II.3.а. Построить алгоритм Винограда трехточечного БПФ в поле GF (16). б. Используя гнездовой метод Винограда, построить 15-точечный БПФ-алгоритм Винограда над GF (16) на основе трехточечного и пятиточечного БПФ-алгоритмов Винограда.

11.4. Выписать уравнения переиндексации для 35-точечного БПФ-алгоритма Кули-Тьюки

11.5. Алгоритм Форни, согласно которому Cj = -oij/Xi), аналогичен равенству Е (х) А (х) = Q (х). Однако последнее выражение не является периодическим, и, следовательно, метод преобразования Фурье нельзя непосредственно использовать для вывода из него алгоритма Форни. Для вывода алгоритма Форни на основе преобразования Фурье надо рассуждать следующим образом. Выбрать такое п, чтобы в некотором расширении поля содержался элемент порядка nn. Показать, что выражение/; (х) Л (х) = - (х" - l) (х) можно рассматривать как периодическое с периодом пп. Использовать преобразование Фурье длины пп для завершения доказательства.

11.6. Для полей характеристики 2 описать процедуру построения 8-точечной циклической свертки, содержащей не более 28 умножений. Описание должно быть полным, но не содержать непосредственных вычислений.

11.7. Пусть требуется написать программу вычисления 31-точечной циклической свертки в поле GF (32) или в некотором его расширении.

а. Оценить сложность программы, использующей 31-точечное ДПФ и теорему о свертке.

б. Написать программу, использующую 75-точечное быстрое преобразование Фурье в поле GF (2™). Построить БПФ из трехточечного и пятиточечного алгоритмов Винограда быстрого преобразования Фурье. Оценить сложность подпрограммы, вычисляющей свертку.

11.8. Для систематического кодирования 8-битовых байтов используется (256, 256-20-код Рида-Соломона над GF (2+ 1). Когда проверочный символ принимает значение 2", он не может быть представлен восемью битами и заменяется на нуль, так что в момент кодирования кодовое слово уже содержит ошибку, которая может быть данным кодом исправлена. Чему равна скорость кода в двоичном представлении? Описать ухудшение кодовых характеристик при использовании в проверочных символах только восьми битов.

ЗАМЕЧАНИЯ

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

Алгоритмы быстрого преобразования Фурье широко используются в обработке дискретных сигналов, начиная с известной работы Кули и Тьюки [1965]. Однако другой подход к БПФ был предложен в более ранних статьях Гуда [I960] и Томаса [1963]. Взаимосвязь между БПФ и сложностью декодирования обсуждалась Юстесеном [1976] и Сервейтом [1977] ).

) Аналогичную задачу рассматривал В. Б. Афанасьев; см. Афанасьев В. Б. Быстрое кодирование и обнаружение ошибок кодом Рида-Соломона. - В кн.: Третий международный симпозиум по теории информации. Тезисы докладов. Часть П. - М. Таллин: URS1 АН СССР и АН ЭССР, 1973, с. 13-17.- Прим. перев.

Основанные на прямых и грубых методах быстрые алгоритмы свертки впервые были построены Агарвалом и Кули [1977]. Виноград [1978] предложил описанный в данной главе общий метод нестроения, а также доказал, что в полях вещественных и комплексных чисел не существует лучших алгоритмов свертки. Он почти не обращался к полям Галуа, так как в этих полях умножения легко маскируются под сложения. Использование китайской теоремы об остатках для целых чисел для разбиения длинных сверток на короткие предложили Агарвал и Кули [1977]. Алгоритм Винограда БПФ был опубликован в 1978 г. Наше описание не следует оригиналу и связывает его с другими методами обработки сигналов. Алгоритм БПФ Винограда и другие эффективные алгоритмы обсуждал также Нуссбаумер [1981].

Применение БПФ-алгоритма Винограда для декодирования кодов Рида- Соломона рассматривали Миллер, Труонг и Рид [1980].

Ускоренный и рекуррентный алгоритмы Берлекэмпа-Месси публикуются впервые; они были анонсированы в работе Блейхута [1981 . Использование в алгоритмах свертки суррогатных полей предложили Препарата и Сервейт [1977 ].

ГЛАВА 12

СВЕРТОЧНЫЕ КОДЫ

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

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

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

12.1. ДРЕВОВИДНЫЕ И РЕШЕТЧАТЫЕ КОДЫ

Изучение древовидных кодов начнем с рассмотрения кодера, представленного на рис. 12.1 в виде регистра сдвига. Многие основные определения могут быть введены с использованием этой