Статья:

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

Конференция: XLI Студенческая международная заочная научно-практическая конференция «Молодежный научный форум: технические и математические науки»

Секция: Физико-математические науки

Выходные данные
Андросова Т.Е., Курочкин В.М., Болдырев А.С. [и др.] Быстрые алгоритмы дискретного преобразования Фурье // Молодежный научный форум: Технические и математические науки: электр. сб. ст. по мат. XLI междунар. студ. науч.-практ. конф. № 1(41). URL: https://nauchforum.ru/archive/MNF_tech/1(41).pdf (дата обращения: 21.10.2018)
Лауреаты определены. Конференция завершена
Эта статья набрала 0 голосов
Мне нравится
Дипломы
лауреатов
Сертификаты
участников
Дипломы
лауреатов
Сертификаты
участников
на печатьскачать .pdfподелиться

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

Андросова Татьяна Евгеньевна
студент 4 курса, кафедра геоинформатики и информационной безопасности, Самарский университет, РФ, г. Самара
Курочкин Владислав Михайлович
студент 4 курса, кафедра геоинформатики и информационной безопасности, Самарский университет, РФ, г. Самара
Болдырев Артем Сергеевич
студент 4 курса, кафедра геоинформатики и информационной безопасности, Самарский университет, РФ, г. Самара
Чернов Роман Вячеславович
студент 4 курса, кафедра геоинформатики и информационной безопасности, Самарский университет, РФ, г. Самара

 

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

Введение

Пусть v = {vii = 0,..,n-1} обозначает вектор с вещественными или комплексными компонентами.

Определение. Преобразованием Фурье вектора v называется вектор V длины n с комплексными компонентами, задаваемыми равенствами

где: 

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

Алгоритм Кули-Тьюки в общем виде

Для построения алгоритма предполагается, что n = n1n2. В выражении для преобразования Фурье произведем следующую замену записи индексов:

i = i1 + n1i2                      i1 = 0,..,n1-1                   i2 = 0,..,n2-1

k = n2k1 + k2           k1 = 0,..,n1-1                  k2 = 0,..,n2-1

Подставим новые обозначения в исходную формулу преобразования:

Определим двумерные переменные для удобства записи формул:

Раскроем скобки в показателе степени и положим  и  Также примем во внимание, что 

В терминах двумерных переменных формула преобразуется к виду

Дискретное преобразование Фурье по алгоритму Кули-Тьюки требует не более n*(n1 + n2 + 1) комплексных умножений и n*(n1 + n2 – 2) комплексных сложений. В общем случае количество умножений и сложений можно записать следующим образом:

MC(n) = n1MC(n2) + n2MC(n1) + n

AC(n) = n1AC(n2) + n2AC(n1)

Так, например, для n = 1000 (учитывая, что MC(2) = 0, MC(5) = 10):

MC(1000) = 2MC(500) + 500MC(2) + 1000 = 2MC(500) + 1000 = 11000

Таким образом, алгоритм Кули-Тьюки дает выигрыш по количеству умножений в 1000000/11000 ≈ 91 раз.

Визуально алгоритм выглядит следующим образом: значения вектора v заносятся по порядку в таблицу n1 на n2 слева направо, сверху вниз. Вычисления состоят из n2-точечного ДПФ каждого столбца, поэлементного умножения всех элементов таблицы соответственно на  и n1-точечного ДПФ для каждой строки.

Алгоритм Кули-Тьюки в случае, когда n = 2m

Если n1 = 2, а n2 = 2m-1, то алгоритм называют алгоритмом Кули-Тьюки по основанию два с прореживанием по времени. Используя тот факт, что  уравнения, задающие БПФ, можно записать в следующем виде:

k = 0,..,n/2 – 1

Если n1 = 2m-1, а n2 = 2, то алгоритм называют алгоритмом Кули-Тьюки по основанию два с прореживанием по частоте. Уравнения БПФ в этом случае преобразуются к виду:

Число MC(n) комплексных умножений n-точечного БПФ удовлетворяет уравнению MC(n) = 2MC(n/2) + n/2, а число AC(n) комплексных сложений удовлетворяет уравнению AC(n) = 2AC(n/2) + n. Решения этих уравнений даются равенствами

MC(n) = (n/2) log2n,

AC(n) = n log2n

Алгоритм Гуда-Томаса

Для применения алгоритма Гуда-Томаса числа n1 и n2 должны быть взаимно простыми. В двумерную таблицу входные данные выписываются, начиная с верхнего левого угла, вдоль расширенной диагонали. Входные индексы задаются по правилу

i1 = i (mod n1),                i2 = i (mod n2)

Это правило представляет собой отображение индекса i на расширенную диагональ двумерной таблицы, элементы которой занумерованы парами индексов (i1i2). Из теории чисел известно, что для чисел n1 и n2 существуют такие целые числа N1 и N2, что N1n1 + N2n2 = НОД(n1n2). Если n1 и n2 взаимно просты, то, согласно китайской теореме об остатках

i = i1N2n2 + i2N1n1 (mod n).

Пусть k1 = N2k (mod n1), k2 = N1k (mod n2). Тогда выходные индексы вычисляются по правилу

k = n2k1 + n1k2 (mod n).

В этих новых индексных обозначениях формула преобразуется к виду

Раскроем скобки в показателе степени

где: 

Если длина n преобразования раскладывается в произведение простых множителей nl, то описанная форма БПФ-алгоритма требует примерно  умножений и столько же сложений. Например, для n = 1000 = 2*2*2*5*5*5 число умножений MC(1000) = 1000*(2+2+2+5+5+5) = 21000, что дает выигрыш по количеству операций умножения в 1000000/21000 ≈ 48 раз.

Заключение

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

 

Список литературы:
1. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов: Пер. с англ. – М.: Мир, 1989. – 448 с.
2. Оппенгейм А., Шафер Р. Цифровая обработка сигналов: – М.: Техносфера, 2006. – 856 с.