Алгоритм БПФ с разделенным основанием

БПФ с разделенным основанием - это алгоритм быстрого преобразования Фурье (БПФ) для вычисления дискретного преобразования Фурье (ДПФ), который был впервые описан в первоначально мало оцененной статье Р. Явне (1968) [1] и впоследствии одновременно заново открыт различные авторы в 1984 году. (Название «разделенное основание системы счисления» было придумано двумя из этих изобретателей, П. Дюамелем и Х. Холлманном .) В частности, расщепленное основание системы счисления - это вариант алгоритма БПФ Кули – Тьюки , который использует смесь оснований. 2 и 4: он рекурсивно выражает ДПФ длины N через одно меньшее ДПФ длины N /2 и два меньших ДПФ длины N /4.

БПФ с разделением системы счисления, наряду с его вариациями, долгое время отличалось достижением наименьшего опубликованного количества арифметических операций (общее точное количество необходимых действительных сложений и умножений) для вычисления ДПФ размеров двойки степени N . Арифметический подсчет исходного алгоритма разделения системы счисления был улучшен в 2004 году (первоначальные успехи были достигнуты в неопубликованной работе Дж. Ван Баскирка посредством ручной оптимизации для N = 64 [2] [3] ), но оказывается, что один все еще можно достичь нового наименьшего значения путем модификации разделения системы счисления (Johnson and Frigo, 2007). Хотя количество арифметических операций не является единственным фактором (и даже не обязательно доминирующим) при определении времени, необходимого для вычисления ДПФ на компьютере , вопрос о минимально возможном количестве представляет давний теоретический интерес. (В настоящее время не установлено жесткой нижней границы количества операций.)

Алгоритм разделения системы счисления может применяться только в том случае, если N кратно 4, но поскольку он разбивает ДПФ на более мелкие ДПФ, его можно по желанию комбинировать с любым другим алгоритмом БПФ.

Разложение по основанию расщепления

Напомним, что ДПФ определяется по формуле:

$X_{k}=\sum _{n=0}^{N-1}x_{n}\omega _{N}^{nk}$

где $k$ целое число в диапазоне от $0$ к $N-1$ и $\omega _{N}$ обозначает примитивный корень из единицы :

$\omega _{N}=e^{-{\frac {2\pi i}{N}}},$

и таким образом: $\omega _{N}^{N}=1$.

Алгоритм разделения системы счисления работает, выражая это суммирование через три меньших суммирования. (Здесь мы даем версию БПФ с расщепленным основанием системы счисления с «прореживанием по времени»; версия с двойным прореживанием по частоте, по сути, является противоположностью этих шагов.)

Сначала суммируем по четным индексам $x_{2n_{2}}$. Во-вторых, суммирование по нечетным индексам, разбитое на две части: $x_{4n_{4}+1}$ и $x_{4n_{4}+3}$, в зависимости от того, равен ли индекс 1 или 3 по модулю 4. Здесь $n_{m}$ обозначает индекс, который работает от 0 до $N/m-1$. Итоговые суммирования выглядят так:

$X_{k}=\sum _{n_{2}=0}^{N/2-1}x_{2n_{2}}\omega _{N/2}^{n_{2}k}+\omega _{N}^{k}\sum _{n_{4}=0}^{N/4-1}x_{4n_{4}+1}\omega _{N/4}^{n_{4}k}+\omega _{N}^{3k}\sum _{n_{4}=0}^{N/4-1}x_{4n_{4}+3}\omega _{N/4}^{n_{4}k}$

где мы использовали тот факт, что $\omega _{N}^{mnk}=\omega _{N/m}^{nk}$. Эти три суммы соответствуют частям основанию 2 (размер N /2) и 4 (размер N ступеней Кули – Тьюки по /4) соответственно. (Основная идея заключается в том, что субпреобразование с четным индексом системы счисления-2 не имеет перед собой мультипликативного множителя, поэтому его следует оставить как есть, в то время как субпреобразование с нечетным индексом системы счисления-2 выигрывает от объединения второго рекурсивного подразделения .)

Эти меньшие суммирования теперь представляют собой в точности ДПФ длины N /2 и N /4, которые можно выполнять рекурсивно, а затем рекомбинировать.

Точнее, пусть $U_{k}$ обозначаем результат ДПФ длины N /2 (для $k=0,\ldots ,N/2-1$), и пусть $Z_{k}$ и $Z'_{k}$ обозначаем результаты ДПФ длины N /4 (для $k=0,\ldots ,N/4-1$). Затем вывод $X_{k}$ это просто:

$X_{k}=U_{k}+\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}.$

Однако это приводит к ненужным вычислениям, поскольку $k\geq N/4$ оказывается, разделяют многие расчеты с $k<N/4$. В частности, если мы добавим N /4 к k , ДПФ размера N /4 не изменятся (поскольку они являются периодическими по N /4), в то время как ДПФ размера N /2 не изменится, если мы добавим N /2 к к . Итак, единственное, что меняется, это $\omega _{N}^{k}$ и $\omega _{N}^{3k}$ термины, известные как коэффициенты вращения . Здесь мы используем тождества:

$\omega _{N}^{k+N/4}=-i\omega _{N}^{k}$

$\omega _{N}^{3(k+N/4)}=i\omega _{N}^{3k}$

чтобы наконец прийти к:

$X_{k}=U_{k}+\left(\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}\right),$

$X_{k+N/2}=U_{k}-\left(\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}\right),$

$X_{k+N/4}=U_{k+N/4}-i\left(\omega _{N}^{k}Z_{k}-\omega _{N}^{3k}Z'_{k}\right),$

$X_{k+3N/4}=U_{k+N/4}+i\left(\omega _{N}^{k}Z_{k}-\omega _{N}^{3k}Z'_{k}\right),$

который дает все результаты $X_{k}$ если мы позволим $k$ диапазон от $0$ к $N/4-1$ в четырех приведенных выше выражениях.

Обратите внимание, что эти выражения устроены так, что нам нужно объединить различные выходные данные ДПФ с помощью пар сложений и вычитаний, которые известны как бабочки . Чтобы получить минимальное количество операций для этого алгоритма, необходимо учитывать особые случаи для $k=0$ (где коэффициенты вращения равны единице) и для $k=N/8$ (где коэффициенты вращения $(1\pm i)/{\sqrt {2}}$ и их можно умножать быстрее); см., например, Sorensen et al. (1986). Умножения на $\pm 1$ и $\pm i$ обычно считаются свободными (все отрицания могут быть поглощены путем преобразования сложений в вычитания или наоборот).

Это разложение выполняется рекурсивно, когда N является степенью двойки. Базовые случаи рекурсии — N = 1, где ДПФ — это просто копия. $X_{0}=x_{0}$, и N =2, где ДПФ представляет собой сложение $X_{0}=x_{0}+x_{1}$ и вычитание $X_{1}=x_{0}-x_{1}$.

Эти соображения приводят к подсчету: $4N\log _{2}N-6N+8$ действительные сложения и умножения, при N >1 степень двойки. Этот подсчет предполагает, что для нечетных степеней 2 оставшийся коэффициент 2 (после всех шагов разделения системы счисления, которые делят N на 4) обрабатывается непосредственно определением ДПФ (4 действительных сложения и умножения) или, что то же самое, с помощью определения Основание-2. Шаг БПФ Кули – Тьюки.

Ссылки

• Явне Р., « Экономичный метод вычисления дискретного преобразования Фурье », в сб. Осенняя совместная компьютерная конференция AFIPS. 33 , 115–125 (1968).
• П. Дюамель и Х. Холлманн, «Алгоритм БПФ с расщеплением системы счисления», Electron. Летт. 20 (1), 14–16 (1984).
• М. Веттерли и Х. Дж. Нуссбаумер, «Простые алгоритмы БПФ и ДКП с уменьшенным количеством операций», Signal Processing 6 (4), 267–278 (1984).
• Дж. Б. Мартенс, «Рекурсивная круговая факторизация — новый алгоритм расчета дискретного преобразования Фурье», IEEE Trans. Акуст., Речь, Обработка сигналов 32 (4), 750–761 (1984).
• П. Дюамель и М. Веттерли, «Быстрые преобразования Фурье: обзор учебного пособия и современное состояние», Signal Processing 19 , 259–299 (1990).
• С. Г. Джонсон и М. Фриго, « Модифицированное БПФ с расщеплением системы счисления с меньшим количеством арифметических операций », IEEE Trans. Сигнальный процесс. 55 (1), 111–119 (2007).
• Дуглас Л. Джонс, « Алгоритмы БПФ с расщепленным основанием », веб-сайт Connexions (2 ноября 2006 г.).
• Х. В. Соренсен, М. Т. Хайдеман и К. С. Буррус, «О вычислении БПФ с расщепленной системой счисления», IEEE Trans. Акуст., Речь, Обработка сигналов 34 (1), 152–156 (1986).