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

• Автор: Просеков, Олег Валерьевич
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Санкт-Петербург
• Количество страниц: 118 с. : ил.

§ 1. Перестановки и кронекерово произведение матриц
§2. Факторизация матриц реверсных перестановок
§3. Факторизация Кули-Тьюки матрицы Фурье
§ 4. Общий подход к вычислению дискретного преобразования Фурье
§5. Параметрический вариант метода простых множителей
§6. Параметрический вариант быстрого преобразования Фурье
§ 7. Параметрический вариант метода простых множителей с последовательными перестановками
§ 8. Параметрический вариант многомерного быстрого преобразования Фурье
§ 9. Быстрое преобразование Фурье малых порядков
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ. Быстрое преобразование Фурье порядков 2-10, 12, 16

Быстрые алгоритмы играют важную роль при обработке дискретных периодических сигналов, особенно в многомерном случае. Наиболее популярным и по-прежнему востребованным является быстрое преобразование Фурье (БПФ). Отметим, что теория БПФ далеко ие проста [2, 3, 6, 9, 24]. Хороший обзор её развития дан в [40].
Ключевой работой в теории БПФ явилась работа Кули и Тыоки 1965 года [38]. Немаловажную роль в то время сыграло развитие вычислительных средств. В [38] приводится время работы реализации трёхмерного БПФ на «новых» тогда ЭВМ 1ВМ 7094. С тех пор интерес к БПФ не угасает. В известном обзорном отчёте Барраса 1997 года [36] упоминается более 3400 работ по БПФ. Большая часть из них — это работы, связанные с вычислительными аспектами БПФ и вопросами реализации БПФ на различных архитектурах ЭВМ. Вопрос о быстродействии стоит очень остро в связи с обработкой сигналов в реальном времени, а дискретное преобразование Фурье (ДПФ) является базовой операцией для других алгоритмов, и быстродействие системы в целом сильно зависит от эффективной реализации БПФ. Типичные приложения — это цифровые устройства связи, аудио- и видеоустройства.
С развитием микроэлектроники появилось множество микропроцессоров с сильно различающейся архитектурой. В связи с этим встал вопрос об универсальном подходе к реализации БПФ. Самой известной работой в этой области является система РБТ¥, разработанная Фриго и Джонсоном [42]. Система анализирует вычислительные графы БПФ и адаптирует их для конкретной
вычислительной архитектуры ЭВМ. Для большинства длин периодов и большинства ЭВМ — это самая быстрая реализация БПФ на сегодня. Другой не менее известной работой является проект SPIRAL [48], в котором реализуется новый подход к дискретным преобразованиям, основанный на теории представлений.
Несмотря на то, что эффективные алгоритмы БПФ существуют для практически любых длин периодов, длина, равная степени двойки, остаётся самой популярной. В этом случае БПФ достаточно легко реализуется, и основной вычислительный модуль «бабочка» задаётся всего несколькими инструкциями. Более сложный по реализации, но более эффективный алгоритм БПФ «split-radix» [39, 51] позволяет сократить число вещественных арифметических операций на 20%, а алгоритм, описанный в новой работе [41], — ещё примерно на 6%.
Различные алгоритмы БПФ зависят от арифметических свойств длины периода сигнала. Если эта длина — число составное, то применим алгоритм Кули-Тьюки. Описание различных вариантов алгоритма Кули-Тьюки можно найти в [37]. В случае, когда длина сигнала может быть представлена в виде произведения попарно взаимно простых чисел, применим алгоритм простых множителей, разработанный Гудом в 1958 году [8]. В вычислительном отношении алгоритм простых множителей проще алгоритма Кули-Тьюки.
Если длина сигнала является простым числом, то можно воспользоваться алгоритмом Рейдера [31]. В этом случае задача вычисления ДПФ сводится к задаче вычисления циклической свёртки. Эффектное применение этой идеи нашёл Виноград для вычисления ДПФ небольшой длины [4]. Задача быстрого вычисления циклической свёртки решается с помощью полиномиальной техники. По сути, метод Винограда даёт разложение матрицы Фурье малого порядка в произведение трёх матриц — матрицы предсложений, диагональной матрицы и матрицы постсложений. Такое разложение имеет целью ми-

§ 6. Параметрический вариант быстрого преобразования Фурье
6.1. Пусть N — піП2---п3 и р„ при и Є 1 : в — фиксированные натуральные числа, взаимно простые с п„. Вектор р = (рі,р2, ■ ■ ■ ,Рв) называется вектором параметров.
Введём перестановки и теУщ’п^п^, сопоставляющие числу
,7 Є 0 : ЛГ — 1 с разложением

числа
Эти перестановки содержательны и при 5 = 1:
При 5 = 2 имеем
тіх1ьп'2,(л + к Пі) = (І1 Рі + кР2П)щп2 , ^пищік + І2 Пі) = (к РіП2 + ПР2)щп2 •
(6.1)
(6.2)