Алгоритм БПФ Брууна

Алгоритм Брюуна представляет собой алгоритм быстрого преобразования Фурье (БПФ), основанный на необычном подходе рекурсивной полиномиальной -факторизации, предложенном для степеней двойки Г. Брюуном в 1978 году и обобщенном на произвольные даже составные размеры Х. Мураками в 1996 году. Поскольку его операции включают в себя только действительные коэффициенты до последнего этапа вычислений, изначально это было предложено как способ эффективного вычисления дискретного преобразования Фурье (ДПФ) реальных данных. Однако алгоритм Брууна не получил широкого распространения, поскольку подходы, основанные на обычном алгоритме БПФ Кули – Тьюки, были успешно адаптированы к реальным данным с, по крайней мере, такой же эффективностью. Более того, есть свидетельства того, что алгоритм Брууна может быть по сути менее точным, чем алгоритм Кули-Тьюки, ввиду конечной числовой точности ( Storn 1993 ).

Тем не менее, алгоритм Брууна иллюстрирует альтернативную алгоритмическую структуру, которая может выражать как себя, так и алгоритм Кули-Тьюки, и, таким образом, дает интересный взгляд на БПФ, который допускает сочетание двух алгоритмов и другие обобщения.

Полиномиальный подход к ДПФ

Напомним, что ДПФ определяется по формуле: $X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.$

Для удобства обозначим N корней из единицы через ω _N^н ( n = 0, ..., N − 1): $\omega _{N}^{n}=e^{-{\frac {2\pi i}{N}}n}$ и определим многочлен x ( z ), коэффициенты которого равны x _n : $x(z)=\sum _{n=0}^{N-1}x_{n}z^{n}.$

Тогда ДПФ можно понимать как сокращение этого полинома; то есть X _k определяется выражением: $X_{k}=x(\omega _{N}^{k})=x(z)\mod (z-\omega _{N}^{k})$ где mod обозначает операцию полиномиального остатка . Ключом к быстрым алгоритмам, таким как алгоритмы Брууна или Кули-Тьюки, является тот факт, что можно выполнить этот набор операций с остатком из N на рекурсивных этапах.

Рекурсивные факторизации и БПФ

Чтобы вычислить ДПФ, нам нужно оценить остаток $x(z)$ по модулю N полиномов степени 1, как описано выше. Вычисление этих остатков одно за другим эквивалентно непосредственному вычислению обычной формулы ДПФ и требует O( N ²) операции. Однако можно рекурсивно объединить эти остатки, чтобы уменьшить стоимость, используя следующий прием: если мы хотим вычислить $x(z)$ по модулю двух многочленов $U(z)$ и $V(z)$ , мы можем сначала взять остаток по модулю их произведения $U(z)$ $V(z)$ , что снижает степень многочлена $x(z)$ и делает последующие операции по модулю менее затратными в вычислительном отношении.

Произведение всех мономов $(z-\omega _{N}^{k})$ для k =0.. N -1 просто $z^{N}-1$ (корни которого явно являются N корнями из единицы). Затем возникает желание найти рекурсивную факторизацию $z^{N}-1$ на полиномы из нескольких членов все меньшей и меньшей степени. Чтобы вычислить ДПФ, нужно $x(z)$ по модулю каждого уровня этой факторизации по очереди, рекурсивно, пока не получим мономы и окончательный результат. Если каждый уровень факторизации разбивает каждый полином на O(1) (ограниченное константой) количество меньших многочленов, каждый из которых имеет O(1) число ненулевых коэффициентов, то операции по модулю для этого уровня занимают O( N время ). ; поскольку количество уровней будет логарифмическое, общая сложность составит O ( N log N ).

Более явно предположим, например, что $z^{N}-1=F_{1}(z)F_{2}(z)F_{3}(z)$ , и это $F_{k}(z)=F_{k,1}(z)F_{k,2}(z)$ , и так далее. Соответствующий алгоритм БПФ будет состоять из первого вычисления x _k ( z ) = x ( z ) mod F _k ( z ), затем вычисляем x _{k , j} ( z ) = x _k ( z ) mod F _{k , j} ( z ) и т. д., рекурсивно создавая все больше и больше полиномов-остатков все меньшей и меньшей степени, пока не будет достигнут окончательный результат степени 0.

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

Кули – Тьюки как полиномиальная факторизация

Стандартный алгоритм счисления по частоте (DIF) Кули -Тьюки близко соответствует рекурсивной факторизации. Например, факторы по основанию 2 DIF Кули – Тьюки. $z^{N}-1$ в $F_{1}=(z^{N/2}-1)$ и $F_{2}=(z^{N/2}+1)$ . Эти операции по модулю уменьшают степень $x(z)$ на 2, что соответствует делению размера задачи на 2. Вместо рекурсивной факторизации $F_{2}$ Однако непосредственно Кули-Тьюки вместо этого сначала вычисляет x ₂ ( z ω _N ), сдвигая все корни (на коэффициент поворота ), чтобы можно было применить рекурсивную факторизацию $F_{1}$ к обеим подзадачам. То есть Кули-Тьюки гарантирует, что все подзадачи также являются ДПФ, тогда как это обычно не верно для произвольной рекурсивной факторизации (такой как у Брууна ниже).

Факторизация Брюуна

Базовый алгоритм Брюна для степеней двойки N = 2 ^н факторизует z ^{2 ^н}- 1 рекурсивно по правилам:

$z^{2M}-1=(z^{M}-1)(z^{M}+1)\,$ $z^{4M}+az^{2M}+1=(z^{2M}+{\sqrt {2-a}}z^{M}+1)(z^{2M}-{\sqrt {2-a}}z^{M}+1)$

где a — действительная константа с | а | ≤ 2. Если $a=2\cos(\phi )$ , $\phi \in (0,\pi )$ , затем ${\sqrt {2+a}}=2\cos {\tfrac {\phi }{2}}$ и ${\sqrt {2-a}}=2\cos({\tfrac {\pi }{2}}-{\tfrac {\phi }{2}})$ .

На этапе s , s =0,1,2, n -1 промежуточное состояние состоит из 2 ^с полиномы $p_{s,0},\dots ,p_{s,2^{s}-1}$ степени 2 ^{н - с} - 1 или меньше, где ${\begin{aligned}p_{s,0}(z)&=p(z)\mod \left(z^{2^{n-s}}-1\right)&\quad &{\text{and}}\\p_{s,m}(z)&=p(z)\mod \left(z^{2^{n-s}}-2\cos \left({\tfrac {m}{2^{s}}}\pi \right)z^{2^{n-1-s}}+1\right)&m&=1,2,\dots ,2^{s}-1\end{aligned}}$

По построению факторизации z ^{2 ^н}- 1 , полиномы p _{s , m} ( z ) каждый кодируют 2 ^{н - с} ценности $X_{k}=p(e^{2\pi i{\tfrac {k}{2^{n}}}})$ преобразования Фурье для m =0 охватываемые индексы равны k = 0 , 2 ^к, 2∙2 ^с, 3∙2 ^с,…, (2 ^{н - с}-1)∙2 ^с, для m > 0 покрываемые индексы: k = m , 2 ^{с +1}- м , 2 ^{с +1}+ м , 2∙2 ^{с +1}- м , 2∙2 ^{с +1}+ м , …, 2 ^н- м .

При переходе на следующий этап полином $p_{s,\ell }(z)$ сводится к полиномам $p_{s+1,\ell }(z)$ и $p_{s+1,2^{s}-\ell }(z)$ полиномиальным делением. Если кто-то хочет сохранить полиномы в порядке возрастания индексов, этот шаблон требует реализации с двумя массивами. Реализация на месте создает предсказуемую, но сильно неупорядоченную последовательность индексов, например, для N = 16 окончательный порядок 8 линейных остатков равен (0, 4, 2, 6, 1, 7, 3, 5).

В конце рекурсии для $s = n -1$ остается $2 п -1$ линейные полиномы, кодирующие два коэффициента Фурье $X 0$ и $X 2 п -1$ для первого и для любого другого $k$ -го полинома коэффициенты $X k$ и $X 2 н - к$ .

На каждом рекурсивном этапе все многочлены общей степени $4 M -1$ приводятся к двум частям половинной степени $2 M -1$ . Делителем этого вычисления полиномиального остатка является квадратичный многочлен z ^м, так что все сокращения можно свести к полиномиальному делению кубики на квадратичные многочлены. Существует $N /2 = 2 п -1$ этих небольших делений на каждом этапе, что приводит к $алгоритму O (N log N)$ для БПФ.

Более того, поскольку все эти полиномы имеют чисто вещественные коэффициенты (до самого последнего этапа), они автоматически используют особый случай, когда входные данные x _n являются чисто вещественными, чтобы примерно в два раза сэкономить на вычислениях и хранении. Можно также напрямую воспользоваться случаем вещественно-симметричных данных для вычисления дискретного косинусного преобразования ( Chen & Sorensen 1992 ).

Обобщение на произвольные корни

Факторизация Брюна и, следовательно, алгоритм БПФ Брюуна были обобщены для обработки произвольных четных составных длин, т.е. деления степени полинома на произвольное основание (множитель) следующим образом. Сначала мы определяем набор полиномов $φ N, α (z)$ для натуральных чисел $N$ и для $α$ в $[0, 1)$ следующим образом: $\phi _{N,\alpha }(z)={\begin{cases}z^{2N}-2\cos(2\pi \alpha )z^{N}+1&{\text{if }}0<\alpha <1\\\\z^{2N}-1&{\text{if }}\alpha =0\end{cases}}$

Обратите внимание, что все полиномы, которые появляются в приведенной выше факторизации Брюна, могут быть записаны в этой форме. Нули этих полиномов равны $e^{2\pi i(\pm \alpha +k)/N}$ для $k=0,1,\dots ,N-1$ в $\alpha \neq 0$ случай, и $e^{2\pi ik/2N}$ для $k=0,1,\dots ,2N-1$ в $\alpha =0$ случай. Следовательно, эти полиномы могут быть рекурсивно факторизованы по фактору (основанию) $r$ посредством:

$\phi _{rM,\alpha }(z)={\begin{cases}\prod _{\ell =0}^{r-1}\phi _{M,(\alpha +\ell )/r}&{\text{if }}0<\alpha \leq 0.5\\\\\prod _{\ell =0}^{r-1}\phi _{M,(1-\alpha +\ell )/r}&{\text{if }}0.5<\alpha <1\\\\\prod _{\ell =0}^{r-1}\phi _{M,\ell /(2r)}&{\text{if }}\alpha =0\end{cases}}$

Ссылки

Брюун, Георг (1978). « z - Преобразование фильтров ДПФ и БПФ». IEEE Транс. по акустике, речи и обработке сигналов (ASSP) . 26 (1): 56–63.
Нуссбаумер, HJ (1990). Алгоритмы быстрого преобразования Фурье и свертки . Берлин: Springer Verlag.
Ву, Юхан (1990). «Новые структуры БПФ на основе алгоритма Брюуна». IEEE Транс. АССП . 38 (1): 188–191.
Чен, Цзяньпин; Соренсен, Хенрик (1992). «Эффективный алгоритм БПФ для вещественно-симметричных данных». Учеб. ИКАССП . 5 : 17–20.
Сторн, Райнер (1993). «Некоторые результаты анализа ошибок с фиксированной запятой алгоритма Брюуна-FTT [ sic ]». IEEE Транс. Сигнальный процесс . 41 (7): 2371–2375.
Мураками, Хидео (1994). «Алгоритмы действительного прореживания по времени и прореживания по частоте». IEEE Транс. Сист. цепей. II: Аналоговая и цифровая сигнализация. Проц . 41 (12): 808–816.
Мураками, Хидео (1996). «Вещественное быстрое дискретное преобразование Фурье и алгоритмы циклической свертки очень сложной четной длины». Учеб. ИКАССП . 3 : 1311–1314.
Шашанк Миттал, доктор медицинских наук Зафар Али Хан, М.Б. Шринивас, «Сравнительное исследование различных архитектур БПФ для программно-конфигурируемой радиосвязи», Конспект лекций по информатике 4599 ( Встроенные компьютерные системы: архитектуры, моделирование и моделирование ), 375-384 (2007 г.) ). Учеб. 7-й международный Семинар SAMOS 2007 (Самос, Греция, 16–19 июля 2007 г.).