Быстрое преобразование Фурье

плексных сложений Nl(N, r) в зависимости от размерности преобразуемой

выборки сигнала и основания  алгоритма БПФ:

( ) ( ) ( )

( ) ( ) ( ) ( ) ï

ï

î

ï ï

í

ì

- - × Ü ¹

× -

× × + - -

- Ü

× -

× × + - -

=

=

å

å

-

=

-

=

1 1 1 , mod 4 0;

1 1 , mod 4 = 0;

( , )

2

0

1

1

r r N

r

m M r N r

r

N

r N

r

m M r N r

r

N

M N r

m

k

k

yr

m

k

k

yr

y

(2.22)

( , ) ,

r

N N r N m N l = lr × ×

(2.23)

где Myr – количество нетривиальных комплексных умножений в

r-точечном ДПФ базовой операции; Nlr – количество нетривиальных ком-

плексных сложений в r-точечном ДПФ базовой операции.

При расчете My(N, r) не учитываются умножения на действительную

и мнимую единицы.

Приведем вывод выражения (2.22). Сначала рассмотрим случай, ко-

гда N некратно 4 (N (mod 4) ¹ 0). При этом в алгоритме (2.14) – (2.16) от-

сутствуют умножения на фазовые  множители равные ± j = ± -1 (см.

(2.18)). Количество базовых  операций в алгоритме (2.14) –  (2.16) определя-

– 39 –

ется как m×N /r. Умножения на фазовые множители в выражениях (2.15)

выполняются в цикле по l = 0, ... , r - 1. Значит, при выполнении любой ба-

зовой операции есть хотя бы одно тривиальное комплексное умножение

(при l = 0 см. (2.18)). Исходя из этого максимально возможное количество

комплексных умножений в  алгоритме (2.14) – (2.16) определяется как

(N /r)×m×(Myr + r - 1). Однако на последнем (m - 1)-м этапе алгоритма отсут-

ствуют нетривиальные  умножения на фазовые множители, так как для всех

базовых операций j = 0 (см. (2.18)). Поэтому из максимально возможного

количества комплексных  умножений следует вычесть N×(r - 1)/r. Кроме

этого, на этапах, отличных от последнего, есть базовые операции, для ко-

торых j = 0, т.е. умножения на фазовые множители сводятся к тривиаль-

ным умножениям на единицу. Из (2.15) следует что на нулевом  этапе таких

базовых операций будет r 0 = 1, на первом – r1, ... и на m - 2-м – rm-2. Исходя

из этого, из максимально  возможного количества комплексных  умножений

следует вычесть также  и ( 1) .

2

0

å-

=

- ×

m

k

r rk

Если N кратно четырем (N (mod 4) = 0), помимо тривиальных умно-

жений на фазовые множители, равные 1, в алгоритме (2.14) – (2.16) при-

сутствуют также и тривиальные  умножения на j = -1 (когда ljrk = N /4; l

= 0, ..., r - 1; j = 0, ..., N /r k - 1; i = 0, ..., r k - 1; k = 0, ..., log rN - 1). Из выра-

жений в скобках видно, что на нулевом этапе таких  умножений – r 0 = 1, на

первом – r1,... и на m - 2-м r m - 2. Суммарное количество всех комплексных

тривиальных умножений на первых m - 1 этапах можно представить (2.24)

( ) å å å å

-

=

-

=

-

=

-

=

- × + = × =

1

1

2

0

2

0

2

0

1

m

k

k

m

k

k

m

k

k

m

k

r r k r r r r . (2.24)

С учетом вышеописанного и (2.24) получается выражение (2.22).

Приведем известные формулы  для вычисления геометрических про-

грессий [19], с помощью  которых наиболее просто реализовать  выражение

(2.22) на некоторых калькуляторах

r

r r r

m m

k

k

-

-

= å-

= 1

1

1

,

.

1

2 1 1

0 r

r r

m m

k

k

-

-

=

- -

= å

С учетом выражений для  вычисления геометрических прогрессий

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

нованию можно представить (2.25)

– 40 –

( ) ( ) ( )

( ) ( ) ( ) ï

ïî

ï ïí

ì

+ - Ü ¹

× -

× × + - -

Ü

-

-

-

× -

× × + - -

=

=

1 1 1 - , mod 4 0.

r

N

, mod 4 = 0;

1

1 1

( , )

r 1 N

r

m M r N r

N

r

r r

r

m M r N r

r

N

M N r

m

yr

m

yr

y

(2.25)

Выше представлен обобщенный алгоритм БПФ по любому основа-

нию с прореживанием по частоте. Известно [23 и др.], что в  алгоритмах

БПФ с прореживанием по времени помимо того, что в базовых  операциях

умножение на фазовые множители  предшествует r-точечным ДПФ, в схе-

мах алгоритмов этапы чередуются как бы в обратном порядке (по сравне-

нию с алгоритмами БПФ  с прореживанием по частоте).

С учетом этого, обобщенный алгоритм БПФ по любому основанию  с

прореживанием по времени  можно представить (2.26) – (2.28)

X 1[n] := x[n], n = 0, ..., N -1; - (2.26

[ ] [ ]

[ ] [ ] ïþ

ïý

ü

= ×

= ×

å-

=

×

-

× ×

- -

, , : , , , = 0, ..., -1;

, , : , , , = 0, ..., -1;

1

0

1

1 1

r

n

n l

k k r

r j lN

k k

X i l j X i n j W l r

X i l j X i l j W l r k

(2.27)

0, ..., 1; = 0, ..., 1; = 0, ..., -1; +1 i r k m

r

j N k

k = - -

X[n] := Xm-1[n], n = 0, ..., N -1. (2.28)

Достаточно просто записывается обобщенный алгоритм БПФ по лю-

бому основанию с прореживанием  по времени в режиме замещения (2.29),

(2.30)

X 1[n] := x[n], n = 0, ..., N -1; - (2.29)

[] [ ]

[ ] [ ] ïþ

ïý

ü

= ×

= ×

å-

=

×

× ×

, , : , = 0, ..., -1;

: , , , = 0, ..., -1;

1

0

r

n

n l

r

r j lN

X i l j R n W l r

R l X i l j W l r k

(2.30)

0, ..., 1; = 0, ..., 1; = 0, ..., -1 +1 i r k m

r

j N k

k = - - .

Следует помнить, что r-ично инверсная перестановка входных от-

счетов (см. (2.9)) должна предшествовать реализации алгоритмов (2.26) –

(2.28) и (2.29), (2.30).

Приведенные оригинальные алгоритмы  БПФ по любому основанию

(2.13) – (2.16); (2.19), (2.20); (2.26) –  (2.28) и (2.29), (2.30) как с прорежива-

нием по частоте, так и  с прореживанием по времени инвариантны  к объе-

мам выборок данных сигналов и основаниям алгоритмов БПФ. Кроме  это-

го они легко программируются  и (или) микропрограммируются, а также

– 41 –

могут быть заложены в архитектуру  специализированных процессоров

БПФ.

2.7. Обобщенный алгоритм БПФ Кули – Тьюки

по смешанным основаниям

В работе [17] рассмотрены  синтез и программная реализация обоб-

щенного алгоритма БПФ  по любому основанию. Синтез обобщенного  ал-

горитма БПФ по смешанным  основаниям, как и по любому основанию, ос-

нован на представлении одномерного  массива комплексных отсчетов

(входных, промежуточных,  выходных) БПФ трехмерным. Аналогично  по-

лучается обобщенный алгоритм БПФ по смешанным основаниям [5, 17 и

др.]. Предположим, что БПФ  выполняется за m этапов со смешанными ос-

нованиями ri, i = 0, ..., m - 1 (ri > 1 – целые). Тогда объем выборки данных

БПФ N должен определиться как

.

1

0 Õ-

=

=

m

q

N rq

В выражении (2.31) показано соответствие индексов трехмерного

массива одномерному для  алгоритма БПФ по смешанным основаниям:

[ , , ];

0 0

j X i l j

r

l N

r

X i N r k

q

q

k

q

q

k º

ú ú ú ú

û

ù

ê ê ê ê

ë

é

+

×

+

× ×

Õ Õ

= =

(2.31)

0, ..., 1; = 0, ..., -1; = 0, ..., 0 1; = 0, ..., -1.

0

k m

r

r

l r i

r

j N

k

k

q

q

k k

q

q

= - -

Õ

Õ

=

=

В обобщенном алгоритме БПФ  по смешанным основаниям с проре-

живанием по частоте (2.32) – (2.34) к массиву данных комплексного типа X

можно обращаться и как  к одномерному, и как к трехмерному.

X-1[n] := x[n], n = 0, ..., N -1; (2.32)

[ ] [ ]

[ ] [ ] ï

ï

þ

ï ï

ý

ü

Õ

= ×

= ×

÷ ÷

ø

ö

ç ç

è

æ

=

× ×

-

=

×

å -

, , : , , , = 0, ..., -1;

, , : , , , = 0, ..., -1;

/

0

1

0

1

k

r

q

l j r

k k N

r

n

k

n l

k k r

X i l j X i l j W l r

X i l j X i n j W l r

k

k

q

k

k

(2.33)

– 42 –

0, ..., N 1; = 0, ..., -1; = 0, ..., 0 1; = 0, ..., -1,

0

k m

r

r

l r i

r

j

k

k

q

q

k k

q

q

= - -

Õ

Õ

=

=

X[n] := Xm-1[n], n = 0, ..., N -1. (2.34)

Массив данных X в алгоритме имеет нижний индекс, соответствую-

щий номеру этапа БПФ. В  выражении (2.20) исходные данные x[n], n = 0,

..., N - 1 записываются в массив данных X с нижним индексом -1 (началь-

ное присваивание).

Непосредственно сам алгоритм записывается двумя строчками

(2.33). Первое выражение  определяет rk-точечное ДПФ, а второе – умно-

жение выходных отсчетов ДПФ  на фазовые множители. Следует отметить,

что двух- и четырехточечные  ДПФ реализуются без нетривиальных  умно-

жений, поэтому 2 и 4 часто  используются в качестве оснований  алгорит-

мов БПФ. С целью минимизации  трудоемкости алгоритма БПФ по сме-

шанным основаниям rk-точечное ДПФ целесообразно вычислять, пользу-

ясь ускоренными алгоритмами. При умножении на фазовые множители

выходных отчетов ДПФ  приходится каждый раз заново вычислять  фазо-

вый множитель. Если длительное время приходится реализовывать  БПФ

по одной и той же схеме алгоритма, целесообразно  фазовые множители

вычислить один раз и запомнить  в ОЗУ или ПЗУ вычислителя  в виде мас-

сива комплексных чисел. Тогда доступ к элементам массива  фазовых мно-

жителей удобно осуществлять по индексу

k

k

q

q

r

l j r

L

Õ=

× ×

= 0 . Комплексный

массив фазовых множителей Wm формируется по выражению

[ ]: cos 2 sin 2 l , l = 0, ..., N -1(, j = -1)

N

l j

N

W l Wm lN

÷ø

ö

çè

æ

úû

ù

êëé ×

× p

× - úû

ù

êë

é ×

× p

= º . По ин-

дексу L легко определяются тривиальные умножения на фазовые множи-

тели. При L = 0 умножать нужно на 1, при L = N/4 – на - -1 , при

L = 3×N/4 – на -1 . Выражение (2.33) выполняется во вложенных циклах

по j, i и k. Самым внешним циклом обязательно должен быть цикл по k.

Порядок вложения циклов по j и i можно выбирать произвольно.

Выражение (2.33) показывает, что  результатом БПФ (массив данных

комплексного типа X[n], n = 0, ..., N - 1) является результат последнего

(m - 1)-го этапа БПФ. Следует помнить, что результат БПФ в массиве X бу-

дет находиться в R-ично инверсном порядке (где массив R = (r0, ..., rm-1)).

Алгоритм R-ичной инверсии для любых целых rk > 1, k = 0, ..., m - 1

можно записать так:

– 43 –

0,..., 1.

1,...,0;

: / ;

[ ]: [ ] mod ;

[ ]: [ ] ;

[ ]: 0;

: ;

= -

ï ï ï ï

þ

ï ï ï ï

ý

ü

= -

ïþ

ïý

ü

=

= +

= ×

=

=

i N

k m

i i r

i i i i i r

i i i i r

i i

i i

a a k

r r a k

r r k

r

a

(2.35)

где i – R-ично-инверсный индекс; ir – прямой индекс; ia – рабочая перемен-

ная целого типа. Все переменные и операции над ними целого типа. Сле-

дует отметить, что если N является степенью двойки, то алгоритм R-ичной

инверсии по смешанным  основаниям выполняется без нетривиальных  опе-

раций умножения и деления. Операции умножения, деления и взятия по

модулю осуществляются при  этом сдвигом влево или вправо на log2 rk дво-

ичных разрядов и конъюнкцией  с rk - 1 соответственно.

Если при БПФ использовать различные основания, то возникает

трудность при выполнении R-ично-инверсной перестановки выходных от-

счетов в режиме замещения. Поэтому для формирования выходных отсче-

тов в естественном порядке  обычно приходится использовать дополни-

тельный массив размерностью в N комплексных отсчетов. Выполнять сам

алгоритм (2.32) – (2.34) можно  в режиме замещения данных в массиве X.

Ниже (2.36) – (2.37) приведен обобщенный алгоритм БПФ по смешанным

основаниям в режиме замещения:

X[n] := x[n], n = 0, ..., N -1; (2.36)

[] [ ]

[ ] [ ] ï

ï

þ

ï ï

ý

ü

Õ

= ×

= ×

÷ ÷

ø

ö

ç ç

è

æ

=

× ×

-

=

å ×

, , : , = 0, ..., -1;

: , , , = 0, ..., -1;

/

0

1

0

k

r

q

l j r

N

r

n

k

n l

r

X i l j B l W l r

B l X i n j W l r

k

k

q

k

k

(2.37)

0, ..., 1; = 0, ..., -1; = 0, ..., 0 1; = 0, ..., -1.

0

k m

r

r

l r i

r

j N

k

k

q

q

k k

q

q

= - -

Õ

Õ

=

=

В алгоритме введен рабочий  массив B комплексных чисел, размер-

ность которого определяется максимальным основанием

(sup ri, i = 0, ..., m - 1) алгоритма БПФ. Выражение (2.36) определяет запись

входных отсчетов в массив X, как правило, расположенный в ОЗУ вычис-

лителя. Непосредственно  сам алгоритм (реализация базовой  операции)

представлен двумя выражениями (2.37). В первом выражении результат rk-

точечного ДПФ записывается в рабочий массив B. Во втором выражении

(2.37) реализуется умножение  результата rk-точечного ДПФ на фазовые

– 44 –

множители с записью произведений в массив X. Выражение (2.31) показы-

вает соответствие индексов одномерного массива X трехмерному для ре-

зультатов последнего этапа  БПФ.

Хотя и алгоритм (2.32) – (2.34) справедлив для любых целых  основа-

ний больших единицы, обычно в качестве смешанных оснований  выбира-

ют степени двойки rk = (2, 4, 8, 16), k = 0, ..., m - 1, что позволяет в ряде

случаев сделать алгоритм эффективным в смысле трудоемкости. При этом

трудоемкость обобщенного  алгоритма БПФ по смешанным основаниям в

нетривиальных комплексных  умножениях My (2.38) и комплексных сложе-

ниях Nl (2.39) можно представить в виде выражений:

( ) -

×

+

+ -

= ×

-

-

-

= å

1

1

2

0

1

,

m

ym

m

k k

yk k

y r

N M

r

M r

M N R N

( )å

Õ

å

Õ -

=

=

-

=

- = × - - ×

2

0

0

2

0

0 1

m

k

k

k

k

q

m q

k

k

k

k

q

q

S

r

r

r

r

r

, (2.38)

( ) å

-

=

= ×

1

0

,

m

k

lk

k

l N

r

N N R N , (2.39)

где Myk – количество операций комплексных умножений в ДПФ базовой

операции БПФ k-го этапа; Nlk – количество операций комплексных сложе-

ний в ДПФ базовой операции БПФ k-го этапа; R = (r0, ..., rm-1) – вектор,

элементами которого являются основания k-го этапа БПФ; Sk – количество

тривиальных комплексных  умножений (на ± -1,±1) при умножениях на

фазовые множители в каждом цикле по i на k-м этапе алгоритма БПФ по

смешанным основаниям. Алгоритм для определения Sk записывается

Sk := 0;

Sk := Sk +1, если N(mod 4) = 0 и 0

4

mod 0 = ÷ø

ö

çè

æ

× × Õ=

N

r

l j r

k

k

q

q

или

N(mod 2) = 0 и 0

2

mod 0 = ÷ø

ö

çè

æ

× × Õ=

N

r

l j r

k

k

q

q

,

0,... 1; 0,..., 1; 0,..., 1