Алгоритм БПФ Бруунса - Википедия - Bruuns FFT algorithm
Алгоритм Брууна это быстрое преобразование Фурье (БПФ) алгоритм, основанный на необычной рекурсивной многочлен -факторизационный подход, предложенный для степеней двойки Г. Брууном в 1978 г. и обобщенный для произвольных четных составных размеров Х. Мураками в 1996 г. Поскольку его операции включают только действительные коэффициенты до последнего этапа вычислений, он первоначально был предложен как способ эффективно вычислить дискретное преобразование Фурье (ДПФ) реальных данных. Однако алгоритм Брууна не получил широкого распространения, поскольку подходы, основанные на обычных Алгоритм Кули – Тьюки БПФ были успешно адаптированы к реальным данным, по крайней мере, с такой же эффективностью. Более того, есть свидетельства того, что алгоритм Брууна может быть по своей сути менее точным, чем алгоритм Кули-Тьюки, несмотря на конечную числовую точность (Storn, 1993).
Тем не менее, алгоритм Брууна иллюстрирует альтернативную алгоритмическую структуру, которая может выражать как себя, так и алгоритм Кули-Тьюки, и, таким образом, дает интересный взгляд на БПФ, позволяющий сочетать два алгоритма и другие обобщения.
Полиномиальный подход к ДПФ
Напомним, что ДПФ определяется формулой:
Для удобства обозначим N корни единства автор: ωNп (п = 0, ..., N − 1):
и определим полином Икс(z) с коэффициентами Иксп:
Тогда ДПФ можно понимать как снижение этого многочлена; то есть, Иксk дан кем-то:
куда мод обозначает полиномиальный остаток операция. Ключ к быстрым алгоритмам, подобным алгоритму Брууна или Кули-Тьюки, заключается в том, что можно выполнить этот набор N операции с остатком на рекурсивных этапах.
Рекурсивные факторизации и БПФ
Чтобы вычислить ДПФ, нам нужно оценить оставшуюся часть по модулю N полиномы 1 степени, как описано выше. Вычисление этих остатков один за другим эквивалентно вычислению обычной формулы ДПФ напрямую и требует O (N2) операции. Однако можно комбинировать эти остатки рекурсивно уменьшают стоимость, используя следующий трюк: если мы хотим оценить по модулю двух многочленов и , мы можем сначала взять остаток от их произведения , что снижает степень полинома и делает последующие операции по модулю менее затратными в вычислительном отношении.
Произведение всех одночленов за k=0..N-1 просто (чьи корни явно N корни единства). Затем нужно найти рекурсивную факторизацию на полиномы из нескольких членов все меньшей и меньшей степени. Чтобы вычислить ДПФ, нужно модулируйте каждый уровень этой факторизации по очереди, рекурсивно, пока не придете к одночленам и окончательному результату. Если каждый уровень факторизации разбивает каждый многочлен на O (1) (ограниченное константой) число меньших многочленов, каждый с числом ненулевых коэффициентов O (1), то операции по модулю для этого уровня принимают O (N) время; так как будет логарифмическое количество уровней, общая сложность составит O (N бревно N).
Более явно, предположим, например, что , и это , и так далее. Соответствующий алгоритм БПФ будет состоять из первых вычислений Иксk(z) = Икс(z) модFk(z), затем вычисляя Иксk,j(z) = Иксk(z) модFk,j(z) и т. д., рекурсивно создавая все больше и больше остаточных многочленов все меньшей и меньшей степени, пока не будет получен окончательный результат степени 0.
Более того, пока полиномиальные множители на каждом этапе равны относительно простой (что для многочленов означает, что они не имеют общих корней), можно построить двойственный алгоритм, обращая процесс с помощью Китайская теорема об остатках.
Кули – Тьюки как полиномиальная факторизация
Стандартная система счисления децимации по частоте (DIF) -р Алгоритм Кули – Тьюки близко соответствует рекурсивной факторизации. Например, radix-2 DIF факторы Кули – Тьюки в и . Эти операции по модулю уменьшают степень на 2, что соответствует делению размера проблемы на 2. Вместо рекурсивного факторизации однако вместо этого Кули – Тьюки сначала вычисляет Икс2(z ωN), сдвинув все корни (на фактор вращения), чтобы можно было применить рекурсивную факторизацию к обеим подзадачам. То есть Кули – Тьюки гарантирует, что все подзадачи также являются ДПФ, в то время как это обычно неверно для произвольной рекурсивной факторизации (такой как Бруун, ниже).
Факторизация Брууна
Базовый алгоритм Брууна для силы двух N=2п факторизует z2п-1 рекурсивно по правилам:
куда а действительная константа с |а| ≤ 2. Если , , тогда и .
На этапе s, s=0,1,2,п-1, промежуточное состояние состоит из 2s многочлены степени 2п-s - 1 или меньше, где
Путем построения факторизации z2п-1, многочлены пs,м(z) каждый кодирует 2п-s значения
преобразования Фурье для м= 0, покрытые индексы равны k=0, 2k, 2∙2s, 3∙2s,…, (2п-s-1)∙2s, за м>0 покрытые индексы k=м, 2s+1-м, 2s+1+м, 2∙2s+1-м, 2∙2s+1+м, …, 2п-м.
При переходе к следующему этапу полином сводится к полиномам и с помощью полиномиального деления. Если кто-то хочет сохранить полиномы в порядке возрастания индекса, этот шаблон требует реализации с двумя массивами. Реализация на месте создает предсказуемую, но сильно неупорядоченную последовательность индексов, например для N=16 окончательный приказ 8 линейный остаток (0, 4, 2, 6, 1, 7, 3, 5).
В конце рекурсии для s=п-1, осталось 2п-1 линейные полиномы, кодирующие два коэффициента Фурье Икс0 и Икс2п-1 для первого и для любого другого k-го многочлена коэффициенты Иксk и Икс2п-k.
На каждом рекурсивном этапе все многочлены общей степени 4 млн-1 сводятся к двум частям половинной степени 2 млн-1. Дивизор этого полиномиального вычисления остатка является квадратичным полиномом zм, так что все редукции можно свести к полиномиальному делению кубики на квадратичные полиномы. Есть N/2=2п-1 этих небольших подразделений на каждом этапе, что приводит к O (N бревно N) алгоритм БПФ.
Более того, поскольку все эти многочлены имеют чисто вещественные коэффициенты (до самого последнего этапа), они автоматически используют особый случай, когда входные данные Иксп являются чисто реальными, чтобы сэкономить примерно два раза на вычислениях и хранении. Можно также использовать прямое преимущество случая реально-симметричных данных для вычисления дискретное косинусное преобразование (Чен и Соренсен, 1992).
Обобщение на произвольные корни
Факторизация Брууна и, следовательно, алгоритм БПФ Брууна были обобщены для обработки произвольных четное составные длины, т. е. деление степени полинома на произвольное основание (коэффициент) следующим образом. Сначала определим набор многочленов φN, α(z) для натуральных чисел N и для α в [0,1):
Обратите внимание, что все многочлены, которые появляются в приведенной выше факторизации Брууна, могут быть записаны в этой форме. Нули этих многочленов равны за в случай, и за в дело. Следовательно, эти многочлены могут быть рекурсивно разложены на множитель (основание) р через:
Рекомендации
- Георг Бруун "z-Преобразование фильтров DFT и FFT, " IEEE Пер. по акустике, речи и обработке сигналов (ASSP) 26 (1), 56-63 (1978).
- Х. Дж. Нуссбаумер, Алгоритмы быстрого преобразования Фурье и свертки (Springer-Verlag: Берлин, 1990).
- Юхан Ву, «Новые структуры БПФ на основе алгоритма Брууна», IEEE Trans. ASSP 38 (1), 188-191 (1990)
- Цзяньпин Чен и Хенрик Соренсен, «Эффективный алгоритм БПФ для вещественно-симметричных данных», Proc. ICASSP 5, 17-20 (1992).
- Райнер Сторн, "Некоторые результаты анализа ошибок с фиксированной запятой в Bruun-FTT [sic ] алгоритм " IEEE Trans. Сигнальный процесс. 41 (7), 2371-2375 (1993).
- Хидео Мураками, "Реальные алгоритмы децимации во времени и децимации по частоте", IEEE Trans. Circuits Syst. II: Аналоговые и цифровые сигн. Proc. 41 (12), 808-816 (1994).
- Хидео Мураками, «Действительное быстрое дискретное преобразование Фурье и алгоритмы циклической свертки очень сложной четной длины», Proc. ICASSP 3, 1311-1314 (1996).
- Шашанк Миттал, доктор Зафар Али Хан, М. Б. Шринивас, «Сравнительное исследование различных архитектур БПФ для программно-определяемого радио», Конспект лекций по информатике 4599 (Встроенные компьютерные системы: архитектуры, моделирование и имитация), 375-384 (2007). Proc. 7-й международный Семинар, САМОС 2007 (Самос, Греция, 16–19 июля 2007 г.).