Алгоритм векторного БПФ

Алгоритм векторного БПФ — это многомерный алгоритм быстрого преобразования Фурье (БПФ), который является обобщением обычного алгоритма БПФ Кули-Тьюки , который делит измерения преобразования на произвольные основания. Он разбивает многомерное (MD) дискретное преобразование Фурье (DFT) на последовательно меньшие MD DFT до тех пор, пока, в конечном итоге, не потребуется оценивать только тривиальные MD DFT. ^[1]

Наиболее распространенным многомерным алгоритмом БПФ является алгоритм строки-столбца, который означает преобразование массива сначала в один индекс, а затем в другой, подробнее см. в БПФ . Затем было разработано прямое двумерное БПФ по основанию 2, ^[2] и он может исключить 25% умножений по сравнению с традиционным подходом строк и столбцов. И этот алгоритм был распространен на прямоугольные массивы и произвольные системы счисления. ^[3] который является общим векторно-основанным алгоритмом.

Алгоритм векторно-основанного БПФ может значительно сократить количество комплексных умножений по сравнению с алгоритмом вектор-строки. Например, для $N^{M}$ матрица элементов (размеры M и размер N в каждом измерении), количество комплексных кратных векторного алгоритма БПФ для системы счисления-2 равно ${\frac {2^{M}-1}{2^{M}}}N^{M}\log _{2}N$ , в то время как для алгоритма строка-столбец это ${\frac {MN^{M}}{2}}\log _{2}N$ . И, как правило, еще большая экономия в умножениях достигается, когда этот алгоритм работает с более крупными системами счисления и массивами более высокой размерности. ^[3]

В целом, векторно-основанный алгоритм значительно снижает структурную сложность традиционного ДПФ, имеющего лучшую схему индексации, за счет небольшого увеличения арифметических операций. Таким образом, этот алгоритм широко используется для многих приложений в технике, науке и математике, например, при обработке изображений. ^[4] и проектирование высокоскоростного процессора БПФ. ^[5]

2-D DIT-окно

Как и в случае с алгоритмом БПФ Кули-Тьюки , двумерное БПФ с векторным основанием получается путем разложения обычного двумерного ДПФ на суммы меньших ДПФ, умноженных на коэффициенты «вертельности».

Алгоритм прореживания во времени ( DIT ) означает, что разложение основано на временной области. $x$ подробнее см. в разделе «Алгоритм БПФ Кули – Тьюки» .

Мы предполагаем, что двумерное ДПФ определено

X(k_{1},k_{2})=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}x[n_{1},n_{2}]\cdot W_{N_{1}}^{k_{1}n_{1}}W_{N_{2}}^{k_{2}n_{2}},

где $k_{1}=0,\dots ,N_{1}-1$ ,и $k_{2}=0,\dots ,N_{2}-1$ , и $x[n_{1},n_{2}]$ это $N_{1}\times N_{2}$ матрица и $W_{N}=\exp(-j2\pi /N)$ .

Для простоты предположим, что $N_{1}=N_{2}=N$ , а основание- $(r\times r)$ таков, что $N/r$ является целым числом.

Используя замену переменных:

$n_{i}=rp_{i}+q_{i}$ , где $p_{i}=0,\ldots ,(N/r)-1;q_{i}=0,\ldots ,r-1;$
$k_{i}=u_{i}+v_{i}N/r$ , где $u_{i}=0,\ldots ,(N/r)-1;v_{i}=0,\ldots ,r-1;$

где $i=1$ или $2$ , то двумерное ДПФ можно записать как: ^[6]

X(u_{1}+v_{1}N/r,u_{2}+v_{2}N/r)=\sum _{q_{1}=0}^{r-1}\sum _{q_{2}=0}^{r-1}\left[\sum _{p_{1}=0}^{N/r-1}\sum _{p_{2}=0}^{N/r-1}x[rp_{1}+q_{1},rp_{2}+q_{2}]W_{N/r}^{p_{1}u_{1}}W_{N/r}^{p_{2}u_{2}}\right]\cdot W_{N}^{q_{1}u_{1}+q_{2}u_{2}}W_{r}^{q_{1}v_{1}}W_{r}^{q_{2}v_{2}},

Приведенное выше уравнение определяет базовую структуру 2-D системы счисления DIT. $(r\times r)$ «бабочка». (См. одномерную «бабочку» в алгоритме БПФ Кули – Тьюки )

Когда $r=2$ , уравнение можно разбить на четыре суммирования, что приводит к: ^[1]

X(k_{1},k_{2})=S_{00}(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}

для

0\leq k_{1},k_{2}<{\frac {N}{2}}

,

где $S_{ij}(k_{1},k_{2})=\sum _{n_{1}=0}^{N/2-1}\sum _{n_{2}=0}^{N/2-1}x[2n_{1}+i,2n_{2}+j]\cdot W_{N/2}^{n_{1}k_{1}}W_{N/2}^{n_{2}k_{2}}$ .

The $S_{ij}$ можно рассматривать как $N/2$ -мерное ДПФ, каждое по подмножеству исходного образца:

$S_{00}$ это ДПФ по этим образцам $x$ для чего оба $n_{1}$ и $n_{2}$ четные;
$S_{01}$ - это ДПФ по образцам, для которых $n_{1}$ четный и $n_{2}$ является странным;
$S_{10}$ - это ДПФ по образцам, для которых $n_{1}$ это странно и $n_{2}$ четный;
$S_{11}$ — это ДПФ по образцам, для которых оба $n_{1}$ и $n_{2}$ странные.

Благодаря периодичности комплексной экспоненты мы можем получить следующие дополнительные тождества, справедливые для $0\leq k_{1},k_{2}<{\frac {N}{2}}$ :

$X{\biggl (}k_{1}+{\frac {N}{2}},k_{2}{\biggr )}=S_{00}(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}-S_{10}(k_{1},k_{2})W_{N}^{k_{1}}-S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}$ ;
$X{\biggl (}k_{1},k_{2}+{\frac {N}{2}}{\biggr )}=S_{00}(k_{1},k_{2})-S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1}}-S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}$ ;
$X{\biggl (}k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}{\biggr )}=S_{00}(k_{1},k_{2})-S_{01}(k_{1},k_{2})W_{N}^{k_{2}}-S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}$ .

Случай 2-D DIF

Аналогичным образом, алгоритм прореживания по частоте ( DIF , также называемый алгоритмом Сэнда – Тьюки) означает, что разложение основано на частотной области. $X$ подробнее см. в разделе «Алгоритм БПФ Кули – Тьюки» .

Используя замену переменных:

$n_{i}=p_{i}+q_{i}N/r$ , где $p_{i}=0,\ldots ,(N/r)-1;q_{i}=0,\ldots ,r-1;$
$k_{i}=ru_{i}+v_{i}$ , где $u_{i}=0,\ldots ,(N/r)-1;v_{i}=0,\ldots ,r-1;$

где $i=1$ или $2$ , а уравнение ДПФ можно записать как: ^[6]

X(ru_{1}+v_{1},ru_{2}+v_{2})=\sum _{p_{1}=0}^{N/r-1}\sum _{p_{2}=0}^{N/r-1}\left[\sum _{q_{1}=0}^{r-1}\sum _{q_{2}=0}^{r-1}x[p_{1}+q_{1}N/r,p_{2}+q_{2}N/r]W_{r}^{q_{1}v_{1}}W_{r}^{q_{2}v_{2}}\right]\cdot W_{N}^{p_{1}v_{1}+p_{2}v_{2}}W_{N/r}^{p_{1}u_{1}}W_{N/r}^{p_{2}u_{2}},

Другие подходы

Алгоритм БПФ с разделенным основанием оказался полезным методом для одномерного ДПФ. И этот метод был применен к БПФ векторного счисления для получения разделенного БПФ векторного счисления. ^[6]^[7]

В обычном двумерном векторно-радиксном алгоритме мы разлагаем индексы $k_{1},k_{2}$ на 4 группы:

{\begin{array}{lcl}X(2k_{1},2k_{2})&:&{\text{even-even}}\\X(2k_{1},2k_{2}+1)&:&{\text{even-odd}}\\X(2k_{1}+1,2k_{2})&:&{\text{odd-even}}\\X(2k_{1}+1,2k_{2}+1)&:&{\text{odd-odd}}\end{array}}

С помощью алгоритма разделения вектора-основания первые три группы остаются неизменными, четвертая нечетно-нечетная группа далее разбивается на еще четыре подгруппы, а всего семь групп:

{\begin{array}{lcl}X(2k_{1},2k_{2})&:&{\text{even-even}}\\X(2k_{1},2k_{2}+1)&:&{\text{even-odd}}\\X(2k_{1}+1,2k_{2})&:&{\text{odd-even}}\\X(4k_{1}+1,4k_{2}+1)&:&{\text{odd-odd}}\\X(4k_{1}+1,4k_{2}+3)&:&{\text{odd-odd}}\\X(4k_{1}+3,4k_{2}+1)&:&{\text{odd-odd}}\\X(4k_{1}+3,4k_{2}+3)&:&{\text{odd-odd}}\end{array}}

Это означает, что четвертый член в системе счисления 2-D DIT $(2\times 2)$ уравнение, $S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}$ становится: ^[8]

A_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}+A_{13}(k_{1},k_{2})W_{N}^{k_{1}+3k_{2}}+A_{31}(k_{1},k_{2})W_{N}^{3k_{1}+k_{2}}+A_{33}(k_{1},k_{2})W_{N}^{3(k_{1}+k_{2})},

где $A_{ij}(k_{1},k_{2})=\sum _{n_{1}=0}^{N/4-1}\sum _{n_{2}=0}^{N/4-1}x[4n_{1}+i,4n_{2}+j]\cdot W_{N/4}^{n_{1}k_{1}}W_{N/4}^{n_{2}k_{2}}$

Затем путем последовательного использования описанного выше разложения получается 2-DN по N DFT вплоть до последней стадии.

Было показано, что алгоритм разделения векторного счисления позволяет сэкономить около 30% комплексных умножений и примерно столько же комплексных сложений для типичных задач. $1024\times 1024$ массив по сравнению с векторно-основанным алгоритмом. ^[7]

Ссылки

^ Jump up to: ^а ^б Даджен, Дэн; Рассел, Мерсеро (сентябрь 1983 г.). Многомерная цифровая обработка сигналов . Прентис Холл. п. 76. ИСБН 0136049591 .
^ Ривард, Г. (1977). «Прямое быстрое преобразование Фурье двумерных функций». Транзакции IEEE по акустике, речи и обработке сигналов . 25 (3): 250–252. дои : 10.1109/ТАССП.1977.1162951 .
^ Jump up to: ^а ^б Харрис, Д.; Макклеллан, Дж.; Чан, Д.; Шюсслер, Х. (1977). «Векторное быстрое преобразование Фурье». ИКАССП '77. Международная конференция IEEE по акустике, речи и обработке сигналов . Том. 2. С. 548–551. дои : 10.1109/ICASSP.1977.1170349 .
^ Буйс, Х.; Померло, А.; Фурнье, М.; Тэм, В. (декабрь 1974 г.). «Реализация быстрого преобразования Фурье (БПФ) для приложений обработки изображений». Транзакции IEEE по акустике, речи и обработке сигналов . 22 (6): 420–424. дои : 10.1109/ТАССП.1974.1162620 .
^ Бадар, С.; Дандекар, Д. (2015). «Проектирование высокоскоростного процессора БПФ с использованием системы счисления — ⁴ конвейерная архитектура». Международная конференция по промышленному приборостроению и управлению (ICIC) , 2015 г., стр. 1050–1055. doi : 10.1109/IIC.2015.7150901 . ISBN 978-1-4799-7165-7 . S2CID 11093545 .
^ Jump up to: ^а ^б ^с Чан, Южная Каролина; Хо, КЛ (1992). «Разделенное векторно-радиксное быстрое преобразование Фурье». Транзакции IEEE по обработке сигналов . 40 (8): 2029–2039. Бибкод : 1992ITSP...40.2029C . дои : 10.1109/78.150004 .
^ Jump up to: ^а ^б Пей, Су-Чанг; Ву, Джа-Лин (апрель 1987 г.). «Двумерное быстрое преобразование Фурье с разделением векторного основания». ИКАССП '87. Международная конференция IEEE по акустике, речи и обработке сигналов . Том. 12. стр. 1987–1990. дои : 10.1109/ICASSP.1987.1169345 . S2CID 118173900 .
^ Ву, Х.; Паолони, Ф. (август 1989 г.). «О двумерном векторном алгоритме БПФ с расщепленным основанием». Транзакции IEEE по акустике, речи и обработке сигналов . 37 (8): 1302–1304. дои : 10.1109/29.31283 .

[Dudgeon83-1] Jump up to: ^а ^б Даджен, Дэн; Рассел, Мерсеро (сентябрь 1983 г.). Многомерная цифровая обработка сигналов . Прентис Холл. п. 76. ИСБН 0136049591 .

[Rivard77-2] Ривард, Г. (1977). «Прямое быстрое преобразование Фурье двумерных функций». Транзакции IEEE по акустике, речи и обработке сигналов . 25 (3): 250–252. дои : 10.1109/ТАССП.1977.1162951 .

[Harris77-3] Jump up to: ^а ^б Харрис, Д.; Макклеллан, Дж.; Чан, Д.; Шюсслер, Х. (1977). «Векторное быстрое преобразование Фурье». ИКАССП '77. Международная конференция IEEE по акустике, речи и обработке сигналов . Том. 2. С. 548–551. дои : 10.1109/ICASSP.1977.1170349 .

[Buijs74-4] Буйс, Х.; Померло, А.; Фурнье, М.; Тэм, В. (декабрь 1974 г.). «Реализация быстрого преобразования Фурье (БПФ) для приложений обработки изображений». Транзакции IEEE по акустике, речи и обработке сигналов . 22 (6): 420–424. дои : 10.1109/ТАССП.1974.1162620 .

[Badar15-5] Бадар, С.; Дандекар, Д. (2015). «Проектирование высокоскоростного процессора БПФ с использованием системы счисления — ⁴ конвейерная архитектура». Международная конференция по промышленному приборостроению и управлению (ICIC) , 2015 г., стр. 1050–1055. doi : 10.1109/IIC.2015.7150901 . ISBN 978-1-4799-7165-7 . S2CID 11093545 .

[Chan92-6] Jump up to: ^а ^б ^с Чан, Южная Каролина; Хо, КЛ (1992). «Разделенное векторно-радиксное быстрое преобразование Фурье». Транзакции IEEE по обработке сигналов . 40 (8): 2029–2039. Бибкод : 1992ITSP...40.2029C . дои : 10.1109/78.150004 .

[Pei87-7] Jump up to: ^а ^б Пей, Су-Чанг; Ву, Джа-Лин (апрель 1987 г.). «Двумерное быстрое преобразование Фурье с разделением векторного основания». ИКАССП '87. Международная конференция IEEE по акустике, речи и обработке сигналов . Том. 12. стр. 1987–1990. дои : 10.1109/ICASSP.1987.1169345 . S2CID 118173900 .

[Wu89-8] Ву, Х.; Паолони, Ф. (август 1989 г.). «О двумерном векторном алгоритме БПФ с расщепленным основанием». Транзакции IEEE по акустике, речи и обработке сигналов . 37 (8): 1302–1304. дои : 10.1109/29.31283 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]