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

сти, состоящие из четных и нечетных членов. Аналогично N /2-точечные

ДПФ могут быть записаны как комбинации двух N /4-точечных ДПФ, т.е.

X (k ) A(k ) Wk B(k )

1 = + N / 2 × (2.8)

или

– 31 –

X (k ) A(k ) W k B(k )

= + N × 2

1 , (2.9)

где 0 £ k £ N /2 - 1, A(k) и В(k) – N /4-точечные ДПФ соответственно четных

и нечетных членов х1(n).

На рис. 2.2 показан результирующий направленный граф, в котором

четырехточечные БПФ, как  и на рис.2.1, рассчитываются согласно форму-

ле (2.9).

D(1)

D(0)

C(1)

C(0)

B(1)

B(0)

A(1)

A(0)

X(1)

X(0)

X(3)

X(2)

X1(3)

X1(2)

X1(1)

X1(0)

X2(3)

X2(2)

X2(1)

X2(0)

a(0) = x1(0) = x(0)

a(1) = x1(2) = x(4)

b(0) = x1(1) = x(2)

b(1) = x1(3) = x(6)

c(0) = x2(0) = x(1)

c(1) = x2(2) = x(5)

d(0) = x2(1) = x(3)

d(1) = x2(3) = x(7)

Двухточеч-

ное ДПФ

Двухточеч-

ное ДПФ

Двухточеч-

ное ДПФ

Двухточеч-

ное ДПФ X(7)

X(6)

X(5)

X(4)

Рис. 2.2. Вычисление восьмиточечного  дискретного преобразования Фурье

через два четырехточечных  ДПФ, которые выполнены через  двухточечные

ДПФ

Процесс уменьшения размера  ДПФ от L до L /2, где L равно степени

2, может быть продолжен  до тех пор, пока не останутся  только двухточеч-

ные ДПФ. Двухточечное ДПФ F(k), k = 0, 1, может быть рассчитано без

использования умножений  по формулам

( ) ( ) ( )

() () ( ) ïþ

ïý ü

= + ×

= + ×

1 0 1 ,

0 0 1 ;

4

8

0

8

F f W f

F f W f

, (2.10)

где f(n), n = 0, 1 – преобразуемая двухточечная последовательность.

Поскольку 0 1

W8 = и 1 4

W8 = - , то для вычислений

(2.10),.действительноu1073 {, не  нужны операции умножения.

– 32 –

W0

W0

W0

W0

W1

W0

W3

W2

W2

W0

W2

W0

X(0)

X(1)

X(2)

X(3)

X(4)

X(5)

X(6)

X(7)

x(0)

x(4)

x(2)

x(6)

x(1)

x(5)

x(3)

x(7)

Рис. 2.3. Восьмиточечное дискретное преобразование Фурье, полученное

последовательным прореживанием  в 2 раза

Таким образом, восьмиточечное ДПФ (см. рис.2.1 и 2.2) в итоге сво-

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

на рис.2.3.

2.4. Перестановка данных и двоичная инверсия

Еще одной особенностью алгоритма  с прореживанием по времени

(как, впрочем, и большинства  других алгоритмов БПФ) является  необхо-

димость такой перестановки элементов входной последовательности, что-

бы выходная последовательность X(k) имела естественный (прямой) поря-

док расположения, т.e. k = 0, 1, …, N - 1.

В примере, показанном на рис. 2.3, для этого требовался следующий

порядок размещения входной  последовательности: x(0), x(4), x(2), x(6),

x(1), x(5), x(3) и x(7). Характер перестановки элементов входной последо-

вательности может быть описан сравнительно просто. Ниже будет показа-

но, что в случае, когда N является степенью 2, входная последовательность

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

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

Двоично-инверсный порядок  определяется следующим образом. Ес-

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

двоичном коде, используя L двоичных разрядов, причем N = 2L, а затем ин-

вертировать порядок следования разрядов, то получаемые при этом числа

и будут номерами элементов  входной последовательности после  их пере-

становки. Так, для случая N = 8 = 23 прямой порядок номеров приведен в

табл. 2.1 слева, а двоично-инверсный  порядок – справа.

– 33 –

Таблица 2.1

Двоично-инверсные коды

Номер Двоичное

представление

Двоичная

инверсия

Двоично-

инверсионный

номер

0 000 000 0

1 001 100 4

2 010 010 2

3 01l 110 6

4 100 001 1

5 101 101 5

6 110 011 3

7 111 111 7

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

необходим соответствующий  алгоритм, обобщение которого на любые  и

смешанные основания рассмотрено  ниже.

2.5. Алгоритм БПФ по основанию 2 с прореживанием

по частоте

Другая распространенная форма алгоритма БПФ (при условии, что N

равно степени 2) – так  называемый алгоритм БПФ с прореживанием  по

частоте. В этом варианте алгоритма БПФ входная последовательность

{x(n)} разбивается на две последовательности, содержащие по N/2 отсче5 €–-

тов каждая, следующим образом: первая последовательность {x1(n)} со-

стоит из первых (N/2) отсчетов {x(n)} , вторая {x(n)} – из остальных (N/2)

отсчетов {x(n)}, т.е.

x1(n) = x(n), n = 0, 1, …, (N/2 - 1);

x2(n) = x(n + N/2), n = 0,1,…,(N/2 - 1).

При таком разбиении N-точечное ДПФ последовательности х(n)

можно записать в виде

( ) å å

-

=

×

-

=

= × + =

1

/ 2

/ 2 1

0

( ) ( )

N

n N

n k

N

N

n

n k

X k x n WN x n W

( ) ( ) ( ).

/ 2 1

0

/ 2

2

/ 2 1

0

å 1 å

-

=

+ ×

-

=

= × × + ×

N

n

n N k

N

N

n

n k

x n WN x n W

Учитывая, что N k j k

WN e × / 2 = - ×p× , получим

( ) [ ( ) ( )] .

/ 2 1

0

å 1 2

-

=

= + - ×p× × × ×

N

n

n k

N

X k x n e j k x n W

Запишем выражения отдельно для четных и нечетных отсчетов

ДПФ:

– 34 –

(2 ) [ ( ) ( )] ( ) [ ( ) ( )] ;

/ 2 1

0

1 2 / 2

/ 2 1

0

2

å 1 2 å

-

=

×

-

=

= + × × = + ×

N

n

n k

N

N

n

n k

X k x n x n WN x n x n W (2.11)

( + ) = å[ - ] =

-

=

× +

/ 2 1

0

(2 1)

2 1 1( ) 2 ( )

N

n

n k

X k x n x n WN

[ ( ) ( ) ] .

/ 2 1

0

å 1 2 / 2

-

=

= - × ×

N

n

n k

N

n

x n x n WN W (2.12)

Из выражений (2.11) и (2.12) видно, что четные и нечетные отсчеты

ДПФ можно получить из (N /2)-точечных ДПФ последовательностей f (n) и

q (n) :

( ) ( ) ( )

( ) [ ( ) ( )] 1.

2

, 0,...,

1;

2

, 0,...,

1 2

1 2

= - × = -

= + = -

q n x n x n W n N

f n x n x n n N

n

N

Таким образом, вычисление N-точечного ДПФ снова удалось свести

к вычислению двух (N /2)-точечных ДПФ.

На рис. 2.4 эта методика иллюстрируется для случая N = 8.

3

W8

1

W8

x1(0) = x(0)

x1(1) = x(1)

x1(2) = x(2)

x1(3) = x(3)

x2(0) = x(4)

x2(1) = x(5)

x2(2) = x(6)

x2(3) = x(7)

Четырех-

точечное

ДПФ

f (0)

f (1)

f (2)

f (3)

g(0)

g(1)

g(2)

g(3)

X(0)

X(4

X(2)

X(6

X(1)

X(5)

X(3

X(7)

2

W8

0

W8

Четырех-

точечное

ДПФ

Рис. 2.4. Переход от. восьмиточечного  дискретного преобразования Фурье

к двум четырехточечным ДПФ  при прореживании по частоте

Описанную методику можно  применить повторно и представить  ка-

ждое из (N/2)-точечных ДПФ в виде комбинации двух (N/4)-тoчечных

ДПФ.

На рис.2.5 и 2.6 показан переход  от четырехточечных ДПФ

(см. рис. 2.4) к двухточечным  ДПФ с последующим прямым вычислением

двухточечных ДПФ.

– 35 –

W2

W0

W2

W0

W3

W2

W1

W0

x(0)

x(1)

x(2)

x(3)

x(4)

x(5)

x(6)

x(7)

Двухточеч-

ное ДПФ

Двухточеч-

ное ДПФ

Двухточеч-

ное ДПФ

Двухточеч-

ное ДПФ

X(0)

X(4)

X(2)

X(6)

X(1)

X(5)

X(3)

X(7)

Рис. 2.5. Переход от четырехточечных  дискретных преобразований Фурье,

показанных на рис.2.4, к  двухточечным дискретным

преобразованиям Фурье

Сравнение алгоритмов, приведенных  на рис.2.3 и 2.6, позволяет вы-

явить - два очевидных  различия между ними. Во-первых, при  прорежива-

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

инверсный, а выходных - прямой, при прореживании по частоте наоборот

(рис.2.6).

W 0

W 0

W 0

W 0

W 0

W 2

W 0

W 2

W3

W0

W2

W1

x(0)

x(1)

x(2)

x(3)

x(4)

x(5)

x(6)

x(7)

X(0)

X(4)

X(2)

X(6)

X(1)

X(5)

X(3)

X(7)

Рис. 2.6. Полный направленный граф восьмиточечного дискретного

преобразования Фурье  с замещением и прореживанием  по частоте

Однако это отличие  кажущееся, поскольку в обоих  алгоритмах поря-

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

ично-инверсным, и наоборот. Второе отличие заключается в  несколько

ином выполнении базовой  операции: при прореживании по частоте  ком-

плексное умножение выполняется  после двухточечного ДПФ.

– 36 –

Легко заметить и сходство между алгоритмами с прореживанием  по

времени и по частоте. В  обоих случаях при вычислении ДПФ требуется

около Nlog2N операций, вычисления могут быть проведены с замещением,

должно предусматриваться  выполнение двоичной инверсии.

2.6. Обобщенный алгоритм быстрого преобразования Фурье

по любому основанию

Если объем блока данных БПФ N является степенью целого числа r

больше 1 (N = r m, где r – основание алгоритма БПФ, m – количество этапов

алгоритма БПФ), то можно  организовать N-точечный алгоритм БПФ Кули

– Тьюки по основанию r. В настоящее время широко используются алго-

ритмы БПФ по основанию 2 (r = 2). Однако в ряде случаев можно полу-

чить более эффективные  в смысле трудоемкости алгоритмы  БПФ для ос-

нований отличных от 2 (r = 4, 8, 16) [1, 20, 23 и др.].

Известны формальные описания алгоритмов БПФ Кули – Тьюки по

основаниям отличным от 2 [23 и др.], основанные на представлении  одно-

мерного массива данных БПФ  двумерным. Однако эти описания неудобны

для программирования и (или) микропрограммирования в связи  с тем, что

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

(2.13) – (2.30) приведены обобщенные  алгоритмы БПФ Кули – Тьюки  по

любому основанию инвариантные к N и r как без режима замещения, так и

в режиме замещения.

Синтез обобщенного алгоритма  БПФ по любому основанию [17, 18]

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

(входных, промежуточных,  выходных данных) БПФ трехмерным:

j X[i l j]

r

l N

r

X i N k k , , 1 º úû

ù

êë

é +

×

+

×

+ ; (2.13)

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

r

j N k

k = - - ,

где k – номер этапа БПФ.

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

массива одномерному. Учитывая вышеописанное, N точечный алгоритм

БПФ по основанию r с прореживанием по частоте можно записать в виде:

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

[ ] [ ]

[ ] [ ] ïþ

ïý

ü

= ×

= ×

× ×

-

=

×

å -

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

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

1

0

1

X i l j X i l j W l r

X i l j X i n j W l r

k r j lN

k k

r

n

n l

k k r (2.15)

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.16)

– 37 –

где x[n] и X[n], n = 0, ..., N - 1 – соответственно входная и выходная после-

довательности комплексных  отсчетов БПФ;

cos 2 sin 2 ; j = -1.

2

÷ø

ö

çè

æ

úû

ù

êë

é ×

× p

× - úû

ù

êë

é ×

× p

= º

×

p

- ×

l

N

l j

N

W e

l

N

j lN

(2.17)

В выражении (2.14) исходные данные x[n], n = 0, ..., N - 1 присваива-

ются массиву X с индексом -1 (начальное присваивание), который далее

будет обрабатываться как  трехмерный.

Непосредственно алгоритм записывается двумя выражениями (2.15):

первое выражение представляет r-точечное ДПФ, которое важно реализо-

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

ные ДПФ реализуют без  нетривиальных умножений. Для других длин бло-

ков данных тоже существуют эффективные в смысле вычислительной

сложности алгоритмы ДПФ); второе реализует умножение на фазовые (по-

ворачивающие) множители. В  ряде случаев умножения на фазовые  множи-

тели могут быть тривиальными

ï ï ï ï

î

ï ï ï ï

í

ì

×

- Ü × ×

Ü × ×

Ü × ×

Ü × ×

× × =

.

4

-1, (mod ) = 3

;

4

-1, (mod ) =

;

2

-1, (mod ) =

1, (mod ) = 0;

l j r N N

l j r N N

l j r N N

l j r N

W

k

k

k

k

r j lN

k (2.18)

Выражения (2.15) вычисляются  в трех вложенных циклах (по j, i и k).

Самым внешним должен быть обязательно цикл по k (по номеру этапа ал-

горитма БПФ). Вложенность  циклов по j и i не имеет значения.

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

может выполняться и в  режиме замещения. Тогда для его  реализации не-

обходим всего один массив данных в N комплексных отсчетов. В этом слу-

чае обобщенный алгоритм БПФ  по любому основанию можно записать

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

[] [ ]

[ ] [ ] ïþ

ïý

ü

= ×

= ×

× ×

-

=

å ×

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

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

1

0

X i l j R l W l r

R l X i n j W l r

k r j lN r

n

n l

r (2.20)

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

r

j N k

k = - -

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

мещения (2.19), (2.20) отсутствует  нижний индекс в комплексном массиве

данных X. Для его реализации помимо массива X в N комплексных отсче-

тов требуется еще рабочий  массив R в r комплексных отсчетов.

– 38 –

Следует помнить, что при  реализации алгоритмов (2.14) – (2.16) и

(2.19), (2.20) коэффициенты Фурье  будут находиться в массиве X в r-ично

инверсном порядке. Ниже (2.21) приведен алгоритм r-ичной инверсии ин-

декса i, который легко программируется и микропрограммируется.

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

r r a

r r

r

a

(2.21)

Все переменные и операции в алгоритме r-ичной инверсии индекса

(2.21) целого типа. Результирующий r -ично инверсный индекс формиру-

ется в переменной ir для каждого индекса i. Если основание алгоритма

БПФ r является степенью двойки, то операции умножения на r и деления

на r целесообразно заменить операциями арифметического сдвига на log2 r

разрядов влево и вправо соответственно, а выражение ia (mod r) заменить

на ia & (r - 1), где & – операция поразрядной конъюнкции. В этом случае

вычислительная сложность  алгоритма (2.21) значительно снизится.

Используя синтезированный  алгоритм (2.14) – (2.16), легко оценить

трудоемкость БПФ в  количествах комплексных умножений My(N, r) и ком-