Основные алгоритмы компьютерной графики   БПФ   КГ   ДМ   ТПОИ   Теория сигналов  

Быстрое преобразование Фурье

Пояснения и оптимизация алгоритма БПФ

Настало время написать и оптимизировать алгоритм. Посмотрите на исходный алгоритм "fft" и на алгоритм для случая четного N "fft2".

Здесь мы рассмотрим листинг "fft2" сверху вниз, комментируя все детали.

Сверху вы видите фрагмент, совпадающий со старым листингом вплоть до #define M_2PI. Этот макрос определяет константу .

Функция complex_mul выполняет умножение комплексных чисел z1 и z2 и записывает результат в ячейку z.

Мы собираемся вызывать алгоритм "fft" M раз для одного и того же числа элементов L. Для оптимизации мы должны вынести за пределы алгоритма "fft" те действия, которые не зависят от выбора конкретных элементов в массиве.

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

Функция createWstore представляет собой ту часть основного цикла "fft", которая отвечала за рассчет поворачивающих множителей. Однако, она оптимизирована. Число итераций меньше, чем в исходном алгоритме, поскольку не на всех итерациях выполнялось вычисление нового множителя, иногда происходило только копирование. Поэтому шаг приращений индекса в массиве вдвое больше: Skew2 вместо Skew. Переменная k для определения четности/нечетности нам больше не нужна, так что внутренний цикл останавливается при достижении границы массива WstoreEnd.

Порядок вычисления множителей будет понятнее на примере. Если L = 32, то порядок изменения k такой (точкой с запятой разделены итерации внешнего цикла, а запятой - внутреннего):

k = 0; 16; 8, 24; 4, 12, 20, 28; 2, 6, 10, 14, 18, 22, 26; 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23...31

Далее, вместо старого алгоритма "fft" мы напишем новый - "fft_step" с учетом того, что поворачивающие множители считать не надо, и не надо делить результат на N.

Сам алгоритм практически не изменился за исключением того, что все расстояния между элементами массива увеличились в M раз, согласно формуле (38). Приставка "M" перед именами новых переменных означает умножение на M.

На вход этой функции будет передаваться массив со смещением. Тем самым происходит коррекция индекса на +h элементов, согласно формуле (38).

В основной функции сначала анализируется параметр N. Если он нечетный, то мы вынуждены отсечь один элемент (последний) и уменьшить N на единицу. Таким образом, на входе алгоритма требуется N ≥ 2.

Далее вычисляется L как максимальная степень двойки, кратная N, сама эта степень T и величина M.

Затем вычисляются поворачивающие множители для "fft_step" и вызывается сам "fft_step" нужное число раз. Если оказывается, что N является степенью двойки, то сработает обычный "fft".

Следующим шагом мы вычисляем поворачивающие коэффициенты уже для формулы (40). Этот фрагмент алгоритма очень похож на createWstore, поэтому в дополнительных комментариях не нуждается. Результат оказывается в массиве mult.

Далее вычисляется формула (40). Смысл переменных: pX - указатель на Xr+sL; rpsL = r + sL; mprM = m + rM; one - очередное слагаемое суммы (40).

Величина widx равна остатку от деления m(r + sL) на N. Таким способом мы избегаем выхода за границы массива mult. Это можно делать, благодаря Теореме 1 - ведь поворачивающие множители как раз имеют период N.

Еще можно заметить, что в сумме (40) в первом множителе поворачивающий коэффициент всегда равен 1, благодаря чему мы экономим несколько умножений.

И наконец, происходит корректировка результатов для обратного ДПФ делением на N.

Функция БПФ для четного N называется "fft2".

Основные алгоритмы компьютерной графики   БПФ   КГ   ДМ   ТПОИ   Теория сигналов  

Юрий Болдырев: Существуют ли в России тайные общества?

ВСЕ ВИДЕО
Знаете ли Вы, что диаграмма состояний, Statechart diagram - это методология объектно-ориентированного проектирования, предназначенная для представления жизненного цикла объектов в реальном или абстрактном мире.

НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
 20.04.2018 - 20:37: СОВЕСТЬ - Conscience -> РУССКИЙ МИР - Карим_Хайдаров.
28.03.2018 - 18:15: СОВЕСТЬ - Conscience -> Проблема государственного терроризма - Карим_Хайдаров.
22.03.2018 - 09:33: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от Ю.Ю. Болдырева - Карим_Хайдаров.
04.10.2017 - 15:26: ЭКОНОМИКА И ФИНАНСЫ - Economy and Finances -> ПРОБЛЕМА КРИМИНАЛИЗАЦИИ ЭКОНОМИКИ - Карим_Хайдаров.
04.10.2017 - 05:02: Беседка - Chatter -> "Зенит"ы с "Протон"ами будут падать - Карим_Хайдаров.
03.10.2017 - 18:16: ВОСПИТАНИЕ, ПРОСВЕЩЕНИЕ, ОБРАЗОВАНИЕ - Upbringing, Inlightening, Education -> Просвещение от О.Н. Четвериковой - Карим_Хайдаров.
03.10.2017 - 07:24: ЦИТАТЫ ЧУЖИХ ФОРУМОВ - Outside Quotings -> ЗА НАМИ БЛЮДЯТ - Карим_Хайдаров.
03.10.2017 - 05:48: Беседка - Chatter -> WHO IS WHO - КТО ЕСТЬ КТО - Карим_Хайдаров.
02.10.2017 - 19:04: АСТРОФИЗИКА - Astrophysics -> Апериодическая комета C/2014 Q2 Lovejoy - Карим_Хайдаров.
02.10.2017 - 14:57: СОВЕСТЬ - Conscience -> РАСЧЕЛОВЕЧИВАНИЕ ЧЕЛОВЕКА. КОМУ ЭТО НАДО? - Карим_Хайдаров.
01.10.2017 - 13:58: Беседка - Chatter -> ЭПИСТОЛЯРНАЯ ФИЗИКА - Карим_Хайдаров.
01.10.2017 - 07:23: СОВЕСТЬ - Conscience -> НАСАтые астропиндосы - Карим_Хайдаров.
Bourabai Research Institution home page

Боровское исследовательское учреждение - Bourabai Research Bourabai Research Institution