УТБПФ, раздел 2.
УТБПФ с прореживанием по времени
Рис 2.1 - граф "бабочка" для УТБПФ с прореживанием по времени
Прямые вычисления выражения УТДПФ требуют O(N2) операций. Для N=3q (q∈ℕ) выведем один из алгоритмов, имеющий время выполнения O(NlogN).
Для удобства введем обозначение
Можно видеть, что при этом будут выполняться следующие тождества:
, которые пригодятся нам в дальнейшем.
Очевидно, что при q=0 (N=1) преобразование Фурье вырождается в тождественное преобразование, F[0]=x[0].
Рассмотрим теперь q>0. Разобьем последовательность x[n] (-T≤n≤T, T=(3q-1)/2) на три:
x0[k]=x[3k],
x-[k]=x[3k-1],
x+[k]=x[3k+1], -t≤k≤t,
Выразим УТДПФ исходной последовательности через указанные последовательности:
Вынесем за знак суммы не зависящие от k множители и получим:
Входящие в выражение суммы - не что иное, как преобразование Фурье от последовательностей x0[n], x+[n] и x-[n], обозначим их F0[n], F+[n] и F-[n].
Они имеют период N/3, то есть F0[n+N/3]=F0[n-N/3]=F0[n] и аналогично для F+ и F-.
Поэтому при вычислении F[n] (-t≤n≤t), F[n+N/3] и F[n-N/3] мы будем использовать одни и те же вычисленные значения F0[n],F+[n] и F-[n]. Запишем это в явном виде:
для -t≤n≤t.
(2.1)
Это и есть формула для одной итерации УТ БПФ, сводяшая преобразование для N=3q элементов к трем преобразованием для 3q-1 элементов. Число арифметических операций на каждой итерации пропорционально N, а всего итераций q=log3N, следовательно, данный алгоритм требует O(NlogN) операций, то есть является «быстрым».
Граф «бабочка».
Выражение (2.1) для конкретного n является атомарной операцией УТ БПФ, которая из трех значений - F0[n], F+[n] и F-[n] получает F[n], F[n+N/3], F[n-N/3]. С точки зрения практической реализации удобно, если входные и выходные значения располагаются в одних и тех же ячейках памяти, то есть преобразование выполняется «на месте». На рис. 2.1 изображено, как это можно реализовать (см в начале записи).
Справа представлен результат, F[n]. Для того, чтобы получить значения F[0], F[-3] и F[3], нужны значения F0[0],F+[0] и F-[0]. Их мы расположили в тех же ячейках, 0, -3 и 3. Центральная колонка графа показывает, как расположены в памяти F0,F+ и F-. Для вычисления F0 необходимы отсчеты x[-3],x[0] и x[3], поэтому, чтобы на протяжении всех итераций вычисления производились на месте, мы должны их поместить в ячейки -1,0,+1. Аналогично отсчеты x[-4],x[-1],x[2] заносятся в ячейки -4,-3,-2 и т.д.
Чтобы лучше понять, каким образом входные данные должны быть «перемешаны», запишем номера отсчетов в уравновешенной троичной системе счисления:
n=dq-13q-1+dq-23q-2+⋯+d13+d0≡(dq-1dq-2…d1d0)ут,
dq-1,dq-2,…,d0∈{-1,0,1}
Для удобства будем записывать цифру -1 как 1 (см Д. Кнут, Искусство программирования, т.2, гл. 4.1). Представления отсчетов в уравновешенной троичной системе также приведены на рисунке.
На заключительной итерации мы по формулам (2.1) находим значения F[n+N/3],F[n] и F[n-N/3], иными словами,
F[1dq-2…d0 ],F[0dq-2…d0],F[1dq-2…d0 ].
На их месте должны находиться значения F+[n], F0[n],F-[n]. Заметим, что F+ является преобразованием Фурье от последовательности x+[n]=x[3n+1]. Число 3n+1 заведомо содержит единицу в младшем разряде в уравновешенной троичной записи. Аналогично 3n заведомо содержит 0, а 3n-1 - минус единицу.
Итак, на последней итерации в позициях, начинающихся с 1 в троичной записи могут располагаться только элементы, номера которых заканчиваются на 1 и то же самое верно для 0 и 1.
Рассматривая теперь предыдущую итерацию, мы должны отбросить младший разряд у входных данных и старший разряд у выходных, после чего верны те же рассуждения. Разряд 1 поменяется местами с разрядом q-1, и т.д.
Такую перестановку, в ходе которой отсчет с номером dq-1dq-2…d1d0 встает на место d0d1…dq-2dq-1, назовем троичной инверсией.
Итак, мы видим, что быстрое вычисление преобразования Фурье с симметричными относительно нуля индексами тесно связано с уравновешенной троичной системой счисления, что и послужило причиной назвать алгоритм УТ БПФ.
Рис 2.1 - граф "бабочка" для УТБПФ с прореживанием по времени
Прямые вычисления выражения УТДПФ требуют O(N2) операций. Для N=3q (q∈ℕ) выведем один из алгоритмов, имеющий время выполнения O(NlogN).
Для удобства введем обозначение
Можно видеть, что при этом будут выполняться следующие тождества:
, которые пригодятся нам в дальнейшем.
Очевидно, что при q=0 (N=1) преобразование Фурье вырождается в тождественное преобразование, F[0]=x[0].
Рассмотрим теперь q>0. Разобьем последовательность x[n] (-T≤n≤T, T=(3q-1)/2) на три:
x0[k]=x[3k],
x-[k]=x[3k-1],
x+[k]=x[3k+1], -t≤k≤t,
Выразим УТДПФ исходной последовательности через указанные последовательности:
Вынесем за знак суммы не зависящие от k множители и получим:
Входящие в выражение суммы - не что иное, как преобразование Фурье от последовательностей x0[n], x+[n] и x-[n], обозначим их F0[n], F+[n] и F-[n].
Они имеют период N/3, то есть F0[n+N/3]=F0[n-N/3]=F0[n] и аналогично для F+ и F-.
Поэтому при вычислении F[n] (-t≤n≤t), F[n+N/3] и F[n-N/3] мы будем использовать одни и те же вычисленные значения F0[n],F+[n] и F-[n]. Запишем это в явном виде:
для -t≤n≤t.
(2.1)
Это и есть формула для одной итерации УТ БПФ, сводяшая преобразование для N=3q элементов к трем преобразованием для 3q-1 элементов. Число арифметических операций на каждой итерации пропорционально N, а всего итераций q=log3N, следовательно, данный алгоритм требует O(NlogN) операций, то есть является «быстрым».
Граф «бабочка».
Выражение (2.1) для конкретного n является атомарной операцией УТ БПФ, которая из трех значений - F0[n], F+[n] и F-[n] получает F[n], F[n+N/3], F[n-N/3]. С точки зрения практической реализации удобно, если входные и выходные значения располагаются в одних и тех же ячейках памяти, то есть преобразование выполняется «на месте». На рис. 2.1 изображено, как это можно реализовать (см в начале записи).
Справа представлен результат, F[n]. Для того, чтобы получить значения F[0], F[-3] и F[3], нужны значения F0[0],F+[0] и F-[0]. Их мы расположили в тех же ячейках, 0, -3 и 3. Центральная колонка графа показывает, как расположены в памяти F0,F+ и F-. Для вычисления F0 необходимы отсчеты x[-3],x[0] и x[3], поэтому, чтобы на протяжении всех итераций вычисления производились на месте, мы должны их поместить в ячейки -1,0,+1. Аналогично отсчеты x[-4],x[-1],x[2] заносятся в ячейки -4,-3,-2 и т.д.
Чтобы лучше понять, каким образом входные данные должны быть «перемешаны», запишем номера отсчетов в уравновешенной троичной системе счисления:
n=dq-13q-1+dq-23q-2+⋯+d13+d0≡(dq-1dq-2…d1d0)ут,
dq-1,dq-2,…,d0∈{-1,0,1}
Для удобства будем записывать цифру -1 как 1 (см Д. Кнут, Искусство программирования, т.2, гл. 4.1). Представления отсчетов в уравновешенной троичной системе также приведены на рисунке.
На заключительной итерации мы по формулам (2.1) находим значения F[n+N/3],F[n] и F[n-N/3], иными словами,
F[1dq-2…d0 ],F[0dq-2…d0],F[1dq-2…d0 ].
На их месте должны находиться значения F+[n], F0[n],F-[n]. Заметим, что F+ является преобразованием Фурье от последовательности x+[n]=x[3n+1]. Число 3n+1 заведомо содержит единицу в младшем разряде в уравновешенной троичной записи. Аналогично 3n заведомо содержит 0, а 3n-1 - минус единицу.
Итак, на последней итерации в позициях, начинающихся с 1 в троичной записи могут располагаться только элементы, номера которых заканчиваются на 1 и то же самое верно для 0 и 1.
Рассматривая теперь предыдущую итерацию, мы должны отбросить младший разряд у входных данных и старший разряд у выходных, после чего верны те же рассуждения. Разряд 1 поменяется местами с разрядом q-1, и т.д.
Такую перестановку, в ходе которой отсчет с номером dq-1dq-2…d1d0 встает на место d0d1…dq-2dq-1, назовем троичной инверсией.
Итак, мы видим, что быстрое вычисление преобразования Фурье с симметричными относительно нуля индексами тесно связано с уравновешенной троичной системой счисления, что и послужило причиной назвать алгоритм УТ БПФ.