Г. Нуссбаумер. Быстрое преобразование Фурье и алгоритмы вычисления сверток

Г. Нуссбаумер

Быстрое преобразование Фурье и алгоритмы вычисления сверток

Перевод с английского Ю. Ф. Касимова и И. П. Пчелинцева

под редакцией чл.-кор. АН КазССР В. М. Амербаева и Т. Э. Кренкеля

МОСКВА

РАДИО И СВЯЗЬ-1985

ББК 32.81 Н90 УДК 621.391

Henri J. Nussbaumer

Fast Fourier Transform and Convolution

Algorithms Second Corrected and Updated Edition

Springer Series in Information Sciences

Edidors: King Sun Fu Thomas S. Huang Manfred

R. Schroeder

Редакция переводной литературы

© Перевод на русский язык, предисловие ре­дакторов перевода, примечания, дополни­тельный список литературы. Издательство «Радио и связь», 1985

Содержание книги Быстрое преобразование Фурье и алгоритмы вычисления сверток

Предисловие редакторов перевода
Предисловие

ГЛАВА 1. ВВЕДЕНИЕ
1.1. Вводные замечания
1.2. Обозначения
1.3. Структура книги

ГЛАВА 2. ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ И ПОЛИНОМИАЛЬНОЙ АЛГЕБРЫ
2.1. Элементарная теория чисел
2.2. Полиномиальная алгебра

ГЛАВА 3. АЛГОРИТМЫ БЫСТРОЙ СВЕРТКИ
3.1. Цифровая фильтрация, использующая циклическую свертку
3.2. Вычисление коротких сверток и произведений полиномов
3.3. Вычисление больших сверток с помощью вложения коротких сверток
3.4. Цифровая фильтрация, использующая многомерное преобразование
3.5. Вычисление сверток рекурсивным вложением полиномов
3.6. Распределенная арифметика
3.7. Алгоритмы вычисления коротких сверток и произведений полиномов

ГЛАВА 4. БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ
4.1. Дискретное преобразование Фурье
4.2. Алгоритм быстрого преобразования Фурье
4.3. БПФ Рейдера — Бреннера
4.4. Многомерные БПФ
4.5. Алгоритм Бруна
4.6. Вычисление сверток с помощью БПФ

ГЛАВА 5. ВЫЧИСЛЕНИЕ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ НА ОСНОВЕ ЛИНЕЙНОЙ ФИЛЬТРАЦИИ
5.1. Алгоритм ЛЧМ z-преобразования
5.2. Алгоритм Рейдера
5.3. БПФ с простыми множителями
5.4. Алгоритм Винограда преобразования Фурье
5.5. Алгоритмы малоточечных ДПФ

ГЛАВА 6. ПОЛИНОМИАЛЬНЫЕ ПРЕОБРАЗОВАНИЯ
6.1. Введение в полиномиальные преобразования
6.2. Общее определение полиномиальных преобразований
6.3. Вычисление полиномиальных преобразований и операций приведения
6.4. Двумерная фильтрация с использованием полиномиальных преобразований
6.5. Полиномиальные преобразования, определенные в модифицированных кольцах
6.6. Комплексные свертки
6.7. Многомерные полиномиальные преобразования

ГЛАВА 7. ВЫЧИСЛЕНИЕ ДИСКРЕТНЫХ ПРЕОБРАЗОВАНИИ ФУРЬЕ С ПОМОЩЬЮ ПОЛИНОМИАЛЬНЫХ ПРЕОБРАЗОВАНИИ
7.1. Вычисление многомерных ДПФ с помощью полиномиальных преобразований
7.2. Вычисление ДПФ с помощью многомерных корреляций и полиномиальных преобразований
7.3. Сравнение с БПФ-алгоритмом
7.4. Алгоритмы нечетных ДПФ

ГЛАВА 8. ТЕОРЕТИКО-ЧИСЛОВЫЕ ПРЕОБРАЗОВАНИЯ
8.1. Определение теоретико-числовых преобразований
8.2. Преобразования Мерсенна
8.3. Преобразования Ферма
8.4. Ограничения, связанные с длиной машинного слова и длиной преобразования
8.5. Псевдопреобразования
8.6. Комплексные ТЧП
8.7. Сравнение с БПФ

Приложение А. Связь между алгоритмами вычисления ДПФ и свертки, основанными на полиномиальных преобразованиях
A.I. Вычисление многомерных ДПФ с помощью алгоритмов, использующих обратное полиномиальное преобразование
А.2. Вычисление многомерной свертки с помощью комбинации методов прямого и обратного полиномиального преобразования
А.З. Вычисление многомерных дискретных косинусных преобразований с помощью полиномиальных преобразований

Приложение Б. Алгоритмы вычисления произведений коротких полиномов
Б.1. Произведение полиномов по модулю z+l
Б.2. Произведение полиномов по модулю (z5—l)/(z—1)
Б.З. Произведение полиномов по модулю (z2i+Zi + I)(z5s— I)/(z2— 1)
Б.4. Произзедение полиномов по модулю (z4i-i-I)(z22+zs+l)
Б.5. Произведение полиномов по модулю (z2, + I)(z52— 1)/(Z2— I)
Задачи
Список литературы
Список литературы, переведенной на русский язык
Дополнительный список литературы

ПРЕДИСЛОВИЕ РЕДАКТОРОВ ПЕРЕВОДА

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

Гармонический анализ является одним из старейших разделов прикладной математики, но только в последние два десятилетия он получил признание в практических разработках. Это связано как с развитием интегральной технологии, так и с появлением эф­фективных алгоритмов гармонического анализа, позволяющих вы­числять дискретное преобразование Фурье (ДПФ) с числом опе­раций, пропорциональным не ./V² [в математике принято обозначе­ние 0(N²)], a O(NlogN) и даже 0(N).

Актуальность гармонического анализа признавалась всегда, но в силу оценки 0(N²) считалось, что для его проведения требуются громоздкие и длительные вычисления. Даже появление алгоритма быстрого преобразования Фурье (БПФ) Кули — Тьюки с оценкой O(NlogN) не изменило этой точки зрения. По-прежнему счита­лось, что разложение в ряд по дискретным комплексным экспонен­там представляет собой некоторое «упражнение для программис­тов».

Новый этап в развитии прикладного гармонического анализа возникал очень медленно, постепенно накапливались факты, необ­ходимые для получения новых по сравнению с БПФ алгоритмов гармонического анализа. Это развитие шло по такому пути: алго­ритм простых множителей Томаса — Гуда, алгоритм Рейдера (све­дение ДПФ при простом N к циклической свертке), алгоритм Тоома — Кука (интерполяционный алгоритм линейной свертки) и, на­конец, алгоритм Винограда преобразования Фурье (АВПФ) и ал­горитм простых множителей (1АПМ).

Все алгоритмы в соответствии с китайской теоремой об остат­ках (для целых чисел и полиномов) касались кодирования обла­сти определения дискретных сигналов (отсчетов времени и про­странства). На этом пути было достигнуто эффективное вычисле­ние ДПФ в виде системы коротких сверток с минимальным чис­лом умножений.

В свою очередь, кодирование области значений сигналов в не­котором коммутативном кольце с единицей привело к появлению теоретико-числовых преобразований (ТЧП), обеспечивающих цик­лическую свертку и ДПФ, которые по своей сути (выполнение модулярных операций) адекватны ЭВМ с модулярной арифмети­кой.

Естественным развитием указанных классов алгоритмов явля­ются: полиномиальное преобразование Нуссбаумера, в котором первообразные корни из единицы ищутся в кольце круговых целых чисел над полем рациональных чисел, и гибридный алгоритм Ри­да— Труонга, в котором алгоритм Винограда реализуется над квадратичным расширением простого поля по модулю числа Мерсенна. Работй в этой области еще только начинается, и очевидно, основное внимание должно быть обращено на каскадные (состав­ные) полиномиально-числовые преобразования, которые основы­ваются на совместном кодировании ансамбля адресов сигналов (временных, пространственных и в области значений) при вычис­лении ДПФ и свертки с целью достижения минимума вычисли­тельной сложности.

Термин «упорядочение полиномов» (ordering of polynomials), введенный Г. Нуссбаумером в связи с полиномиальными преобра­зованиями, следует понимать как образование полиномов по г, ко­эффициентами которых являются столбцы двумерных массивов. Такое представление двумерных массивов дает возможность запи­сывать двумерную циклическую свертку в виде одномерной цикли­ческой свертки полиномов по г.

Упорядочение полиномов применимо и к массивам большей размерности, например, трехмерной.

Теперь уже можно сказать, что использование теории чисел и алгебраических структур в прикладном гармоническом анализе и при вычислении сверток является разделом цифровой обработки сигналов, требующим самого пристального внимания. Изменилось само определение свертки — теперь вычисление свертки понимает­ся как задача вычисления системы билинейных форм над задан­ным коммутативным кольцом с единицей при помощи билинейной неветвящейся программы, а ее вычислительная сложность (число существенных умножений) по теореме Винограда — Штрассена определяется как ранг системы билинейных форм. Следует разли­чать верхние границы вычислительной сложности гармонического анализа и вычисления сверток, которые появляются при «изобре­тении» новых алгоритмов, и определение нижних границ (потен­циальных возможностей метода), что представляет собой основную задачу алгебраической теории сложности вычисления сверток и ДПФ. Например, в настоящий момент неизвестно,, достигает ли алгоритм Винограда преобразования Фурье нижней границы муль­типликативной сложности в случае произвольного N.

Таким образом, речь идет о создании новой идейной концепции конечных вычислительных структур на алгебраическо-числовой основе и поэтому следует ожидать применения все новых разделов.

Часть материала книги основана на курсе, прочитанном аспи­рантам в университете г. Ниццы (Франция). Хотелось бы выра­зить свою признательность д-ру Т. А. Крицу (IBM FSD) за добро­желательное рецензирование рукописи и многочисленные полезные пожелания. Я благодарен м-ру П. Беллоту (IBM С. Е. R., France) за советы, касающиеся вводных глав по теории чисел и полиноми­альной алгебре, и д-ру Кули (IBM Research, Yorktown Heights) за комментарии к работам, способствовавшим созданию этой книги. Я признателен также д-ру П. Куандэлу, с которым мы работали над полиномиальными преобразованиями во время подготовки его диссертации и с кем провели много плодотворных обсуждений. Я обязан м-сс С. де Бэкер за помощь по улучшению языка книги и м-сс К. Шевалье за подготовку рукописи.

ПРЕДИСЛОВИЕ

В книге с единой точки зрения представлены различные быстрые алгоритмы, используемые при реализации цифровых фильтров и вычислении дискретных преобразований Фурье (ДПФ).

Книга содержит восемь глав. Первые две главы посвящены об­щему рассмотрению проблемы и вводному материалу по теории чисел и полиномиальной алгебре. Обсуждаются лишь основные понятия, применяемые в книге. Из теории чисел приводятся срав­нения, первообразные корни, квадратичные вычеты и свойства чи­сел Мерсенна и Ферма, из полиномиальной алгебры — делимость и сравнения многочленов, а также некоторые вопросы алгебраиче­ской сложности вычислений.

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

Глава 3 содержит обзор быстрых алгоритмов цифровой фильт­рации, основанных на алгебраических методах, и вычислений од­номерных круговых сверток. В гл. 4 и 5 рассмотрены быстрое преобразование Фурье (БПФ) и алгоритм Винограда преобразования Фурье (АВПФ). В гл. 6 и 7 вводится понятие полиномиальных преобразований и показано, что они являются важным инструмен­том для уяснения структуры многомерных сверток, 'преобразова­ний Фурье и разработки эффективных алгоритмов.

В гл. 8 эти понятия применены к вычислению одномерных свер­ток с заменой полиномиальных конечных полей на конечные чис­ловые поля, что облегчило введение теоретико-числовых преобра­зований, полезных для быстрых вычислений сверток с помощью модулярной арифметики.

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

В заключение сформулируем алгоритмическую задачу ДПФ: существует ли массовый детерминированный алгоритм вычисления ДПФ (универсальный гармонический анализатор) с минимальной сложностью? Пока исчерпывающего ответа на этот вопрос мы не имеем.

Предлагаемая читателю книга Г. Нуссбаумера представляет собой «моментальный снимок» области вычисления ДПФ и сверт­ки в начале 80-х годов. Можно ожидать, что она станет настоль­ной книгой для специалистов по цифровой обработке сигналов, а также ценным пособием для аспирантов и студентов старших кур­сов, изучающих цифровую обработку.

Перевод книги выполнен Ю. Ф. Касимовым (предисловие, гл. 1—4, приложения, задачи) и И. П. Пчелинцевым (гл. 5—8).

В. М. Амербаев Т. Э. Кренкель

Скачать книгу Г. Нуссбаумер. Быстрое преобразование Фурье и алгоритмы вычисления сверток. Москва, Издательство Радио и связь, 1985