• Прибор дистанционного контроля и управления
• Прибор контроля изоляции
• Цифровой прибор контроля изоляции
• Тиристорные выключатели - коммутаторы
• Слаботочные кабельные жгуты
• Сильноточные кабельные жгуты
• Цены на продукцию
• Сертификаты
• Буклет о продукции
• Награды
• Отзывы о продукции
• Клиенты
• Карта сайта

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

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

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

МОСКВА

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

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)
Задачи
Список литературы
Список литературы, переведенной на русский язык
Дополнительный список литературы

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

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

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

Актуальность гармонического анализа признавалась всегда, но в силу оценки 0(N2) считалось, что для его проведения требуются громоздкие и длительные вычисления. Даже появление алгоритма быстрого преобразования Фурье (БПФ) Кули — Тьюки с оценкой 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