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

0

= - = - = -

Õ=

k m

r

l r j N k

q

q

k

и легко реализуется.

Очевидно, алгоритм (2.32) – (2.34) реализует БПФ и при одинаковых

основаниях.

– 45 –

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

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

по времени помимо того, что в базовых операциях умножение  на фазовые

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

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

с прореживанием по частоте). Трудоемкость алгоритмов БПФ с прорежи-

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

ем по времени.

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

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

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

[ ] [ ]

[ ] [ ] ï

ï

þ

ï ï

ý

ü

= ×

Õ

= ×

å -

=

×

-

÷ ÷

ø

ö

ç ç

è

æ

=

× ×

- -

1

0

1

/

0

1 1

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

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

k

k

k

k

q

r

n

k

n l

k k r

k

r

q

l j r

k k N

X i l j X i n j W l r

X i l j X i l j W l r (2.41)

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

= - -

Õ

Õ

=

=

,

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

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

нованиям с прореживанием  по времени можно представить  как (2.43),

(2.44)

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

[] [ ]

[ ] [ ] ï

ï

þ

ï ï

ý

ü

= ×

Õ

= ×

å -

=

×

÷ ÷

ø

ö

ç ç

è

æ

=

× ×

1

0

/

0

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

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

k

k

k

k

q

r

n

k

n l

r

k

r

q

l j r

N

X i l j X i n j W l r

B l X i l j W l r (2.44)

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.43) определяет запись

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

лителя. Отсчеты должны записываться в R-ично-инверсном порядке (см.

– 46 –

алгоритм R-ичной инверсии индекса). Непосредственно сам алгоритм

(реализация базовой операции) представлен в выражениях (2.44). В  первом

выражении (2.44) входные отсчеты, умноженные на фазовые множители,

соответствующей базовой  операции записываются в рабочий  массив B.

Второе выражение (2.44) реализует rk-точечные ДПФ с записью результата

в массив комплексных чисел X.

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

методик реализации и исследования алгоритмов БПФ по смешанным осно-

ваниям.

2.7.1. Пример реализации  и исследования алгоритма БПФ  для

N = 24 = 4 ´ 3 ´ 2 с прореживанием по частоте

Исходные данные: N = 24, m = 3, R = (4, 3, 2); (r0 = 4, r1 = 3, r2 = 2).

Требуется построить графическую  схему алгоритма БПФ и оценить  его

трудоемкость в комплексных  умножениях и комплексных сложениях.

На рис. 2.7 представлено обозначение rk-точечной базовой операции

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

Базовая операция БПФ записана в выражениях (2.31) – (2.34) для ал-

горитма без замещения  и в (2.24), (2.25) для алгоритма с  замещением. Ба-

зовая операция заключается  в rk-точечном ДПФ и умножении его резуль-

татов на фазовые множители. На рис. 2.7 через x[lj], j=0, ..., rk - 1 обозначе-

на входная последовательность rk-точечного ДПФ, через X[lj],

j = 0, ..., rk - 1 выходная последовательность базовой операции (БО) стрел-

кой ( ® ) умножение на фазовые множители, а через aj, j = 1, ..., rk - 1 пока-

затель степени WN фазовых множителей. Следует помнить, что a0 всегда

равно нулю, что соответствует  тривиальному умножению на 1. Поэтому  на

соответствующем выходе базовой  операции не показано стрелкой умно-

жение на фазовый множитель.

– 47 –

a -1

rk

.

.

.

.

.

.

X[lrk -2 ]

a -2

rk

a0

X[l0 ]

x[lrk -2 ]

x[l0 ]

x[l1]

a1 X[l1]

x[lrk -1] X[lrk -1]

[ ] ( [ ] ) , 0,..., 1; 0,..., 1;

1

0

= × × = - = - × a

-

= å

X l x l W WN j rk k m

i j

r

r

i

j i

j

k

k

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

0

a = × × 0 = - = - = -

Õ

Õ

=

= k m

r

l r j N

r

r

l j k

q

q

k

k

k

q

q

l

Рис. 2.7. Графическое обозначение  базовой операции

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

На рис. 2.8 представлена графическая  схема алгоритма БПФ, постро-

енная по табл 2.1.

– 48 –

Таблица 2.1

Данные для схемы алгоритма  БПФ

k i j Номера отсчетов БО al, l = 0, ..., rk - 1

1 2 3 4 5

0 0 0 0, 6, 12, 18 0, 0, 0, 0

0 0 1 1, 7, 13, 19 0, 1, 2, 3

0 0 2 2, 8, 14, 20 0, 2, 4, 6

0 0 3 3, 9, 15, 21 0, 4, 8, 12

0 0 4 4, 10, 16, 22 0, 4, 8, 12

0 0 5 5, 11, 17, 23 0, 5, 10, 15

1 0 0 0, 2, 4 0, 0, 0

1 0 1 1, 3, 5 0, 4, 8

1 1 0 6, 8, 10 0, 0, 0

1 1 1 7, 9, 11 0, 4, 8

1 2 0 12, 14, 16 0, 0, 0

1 2 1 13, 15, 17 0, 4, 8

1 3 0 18, 20, 22 0, 0, 0

1 3 1 19, 21, 23 0, 4, 8

2 0 0 0, 1 0, 0

2 1 0 2, 3 0, 0

2 2 0 4, 5 0, 0

2 3 0 6, 7 0, 0

2 4 0 8, 9 0, 0

2 5 0 10, 11 0, 0

2 6 0 12, 13 0, 0

2 7 0 14, 15 0, 0

2 8 0 16, 17 0, 0

2 9 0 18, 19 0, 0

2 10 0 20, 21 0, 0

2 11 0 22, 23 0, 0

– 49 –

i=0 X[0] j=0

0 X[12]

X[4]

0 X[16]

i=1 j=0

X[8]

0 X[20]

i=2 j=0

0

4

0

8

i=0

j=0

j=1

x[0]

X[1]

0 X[13]

i=3

j=0

i=4 j=0 X[5]

0 X[17]

X[9]

0 X[21]

X[2]

0 X[14]

j=0

i=6

i=1

j=0

j=1

X[6]

0 X[18]

X[10]

0 X[22]

j=0

i=7

j=0

i=8

i=2

j=0

j=1

0 X[23]

X[11]

0 X[19]

X[7]

0 X[15]

0

4

0

8

0

4

0

8

0

4

0

8

i=9 j=0

i=10

i=11

j=0

j=0

j=1

j=0

i=3

X[3]

0

1

2

3

j=0

4

5

0

2

4

6

8

10

0

3

6

9

15

12

i=0

j=0

j=1

j=2

j=3

j=4

j=5

x[1]

x[2]

x[3]

x[4]

x[5]

x[6]

x[7]

x[8]

i=5

x[9]

x[10]

x[11]

x[12]

x[13]

x[14]

x[15]

x[16]

x[17]

x[18]

x[19]

k = 0 k = 1 k = 2

x[20]

x[21]

x[22]

x[23]

Рис. 2.8. Схема алгоритма  быстрого

преобразования Фурье  для N = 24 = 4 ´ 3 ´ 2

В колонке 1 табл. 2.1 записан  номер этапа алгоритма БПФ k. В ко-

лонках 2 и 3 индексы циклов базовых операций i и j (см. (2.20) – (2.22) и

– 50 –

(2.24) – (2.25)) соответственно. На каждом этапе каждая БО  однозначно

определяется индексами i и j.

Колонка 4 определяет номера индексов одномерного массива дан-

ных, элементы которого принадлежат  каждой БО. Номера одномерных ин-

дексов определяются по выражению (2.31) при подстановке в него соот-

ветствующих индексов k, i, j (колонки 1, 2, 3) и l (l = 0, ..., rk - 1 определяет

номер входа и выхода соответствующей  БО).

Колонка 5 определяет показатель степени al, l = 0, ..., rk - 1 (l номер

выхода каждой БО) у WN для всех фазовых множителей каждой БО

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

0

a = × × 0 = - = - = -

Õ

Õ

=

= k m

r

l r j N

r

r

l j k

q

q

k

k

k

q

q

l

Таким образом, колонка 4 определяет, какие элементы массива дан-

ных X являются входами и выходами каждой БО на каждом этапе алгорит-

ма БПФ, а колонка 5 определяет фазовые множители каждой БО. Кроме

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

ма коэффициенты Фурье  будут расположены в R-ично-инверсном порядке,

который показан на рис. 2.2. Алгоритм R-ичной инверсии индекса рас-

смотрен выше.

На рис. 2.9 иллюстрировано представление одномерного массива

трехмерным вместе с границами  изменения индексов l, j и i для каждого

этапа алгоритма БПФ. Это  представляет интерес при проектировании спе-

циализированных процессоров  БПФ, реализующих многословные обраще-

ния к ОЗУ данных (до rk комплексных слов) и более подробно будет рас-

смотрено ниже.

Теперь оценим трудоемкость алгоритма БПФ в комплексных  умно-

жениях и комплексных  сложениях. Сначала выберем эффективные  в

смысле трудоемкости способы  реализации rk-точечных ДПФ. Четырехто-

чечное ДПФ целесообразно  выполнить как БПФ по основанию 2 по алго-

ритму (2.20) – (2.22) или (2.24), (2.25). Будем учитывать только нетриви-

альные умножения (отличные от умножений на ±1 и ± -1 ). Тогда My4 = 0

и Nl4 = 8. Трехточечные ДПФ можно выполнять по алгоритму Винограда

(My3 = 2 и Nl3 = 6). Двухточечные ДПФ тривиальны по сути

(My2 = 0 и Nl2 = 2). Для того, чтобы воспользоваться выражением (2.38) для

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

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

тривиальных умножений (S0 = 3, S1 = 0). Подставляя приведенные данные в

(2.38) получаем

My(24; 4,3,2) = [24 ´ 3/4 + 24 ´ (2+3-1)/3] + 24 ´ 0/2 -

- (1 ´ 3+4 ´ 2) - (1 ´ 3+4 ´  0) = 36.

– 51 –

l = 0,...,3;

j = 0,...,5;

i = 0;

k = 0.

l = 0,...,2;

j=0,...,1;

i = 0,...,3;

k=1.

1 3 5

0 2 4 11

1

0

j

6 8 10 17

12 14 16 23

18 20 22

1

2

3

4

5

0

1

2

3

4

5

7

8

9

10

11

13

14

15

16

17

0 6 12 18

19

20

21

22

23

0 1 2 3

0

1

2

3

i

0 1 2 l

j

l

Рис. 2.9. Представление одномерного массива трехмерным для алгоритма

БПФ (N = 24 = 4 ´ 3 ´ 2)

– 52 –

l = 0, 1;

j = 0;

i = 0,...,11;

k = 2.

0 1

2 3

4 5

6 7

8 9

10 11

12 13

14 15

16 17

18 19

20 21

22 23

l

i

0

1

2

3

4

5

6

7

8

9

10

11

Рис. 2.9. Окончание.

Для оценки количества комплексных  сложений воспользуемся вы-

ражением (2.39)

Nl(24; 4,3,2) = 24 ´ 8/4 + 24 ´ 6/3 + 24 ´ 2/2 = 120.

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

быть легко запрограммированы (микропрограммированы) как для одно-

процессорных, так и для  мультипроцессорных систем. Реализация обоб-

щенного алгоритма БПФ  для любого основания рассмотрена  в работе [17].

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

ным основаниям совпадают  с соответствующим алгоритмом для  любого

основания. Возрастают только требования к процессору БПФ, который

должен одинаково эффективно реализовывать базовые операции для раз-

личных оснований. При  реализации обобщенного алгоритма  БПФ по сме-

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

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

– 53 –

этапе БПФ. Предложенный алгоритм удобно использовать для проектиро-

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

фильтрации звуковых сигналов.

В прилож. 1 рассмотрен пример реализации алгоритма БПФ Кули –

Тьюки по смешанным основаниям с прореживанием по частоте для  длины

блока данных N = 6.

2.8. Обобщенный гнездовой алгоритм быстрого преобразования

Фурье на основе алгоритмов Винограда

для коротких выборок данных

В работах [1, 20, 25] показано, что  для большого множества объемов

выборок данных существуют более эффективные в смысле трудоемкости

алгоритмы БПФ, чем алгоритмы  Кули – Тьюки. В первую очередь  это ал-

горитмы ДПФ, основанные на теоретико-числовых представлениях. Ниже

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

Винограда. Незначительные изменения обобщенного гнездового алгорит-

ма позволяют реализовать  схему Джонсона – Барраса [1].

Основой рассматриваемого обобщенного  гнездового алгоритма ДПФ

являются базовые алгоритмы  Винограда [1] для малых размерностей бло-

ков входных данных ni = (2, 3, 4, 5, 7, 8, 9, 16). Базовые алгоритмы имеют

вид (2.45):

X = Ci × Bi ×Ai ×  x, (2.45)

где x – блок входных данных размерности (ni); Ai – матрица предсложений

размерности (n'i ´ ni), элементами матрицы являются целые числа 0, -1, 1,

2. Умножение матрицы на  вектор x реализуется без нетривиальных умно-

жений; Bi – диагональная матрица размерности (n'i ´ n'i), элементами мат-

рицы являются вещественные числа; Ci – матрица постсложений размер-

ности (ni ´ n'i). Элементами матрицы являются комплексные числа 0, ±1,

± -1 (либо 0, либо чисто мнимые ± -1 , либо вещественные). Умноже-

ние матрицы Ci на вектор размерности n'i вещественных или комплексных

чисел реализуется без  нетривиальных умножений; X – блок выходных дан-

ных (результат) размерности ni.

Матрицы базовых алгоритмов Винограда приведены в справочной

литературе, например [1, 25]. Из вышеописанного следует, что базовые  ал-

горитмы реализуются за n'i нетривиальных умножений. Однако, при анали-

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

этих матриц равны единице. Поэтому число нетривиальных  умножений в

базовых алгоритмах меньше n'i.

Если Õ-

=

=

1

0

m

k

N nk , где nk – взаимно простые числа из множества ni, а m

– число вложений гнездового алгоритма, то можно реализовать  гнездовой

– 54 –

алгоритм БПФ размерности N, используя базовые алгоритмы размерностей

nk, k = 0, ..., m - 1. В обобщенном виде известна запись гнездового алгорит-

ма БПФ с процедурой кронекеровского произведения матриц [1] (2.46)

X = (Cm-1 Ä Cm-2 Ä ... Ä C0) × (Bm-1 Ä Bm-2 Ä ... Ä B0) × (Am-1 Ä Am-2 Ä ...

... Ä A0) × x, (2.46)

где Ä – операция кронекеровского  произведения матриц. К недостаткам

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

большого объема оперативной  па0мяти для хранения результатов  кронеке-

ровского произведения матриц [1, 20].

Гнездовые алгоритмы предполагают преобразование одномерной

входной последовательности в m-мерную таблицу (переиндексация на

входе), обработку m-мерной таблицы с помощью матриц базовых алгорит-

мов Ak, Ck, k = 0, ..., m - 1 и m-мерной таблицы Bb, полученной из матриц

базовых алгоритмов Bk, k = 0, ..., m - 1, и преобразования результирующей

m-мерной таблицы в одномерную (переиндексация на выходе).

При обработке m-мерной таблицы матрицами Ak и Ck происходит

умножение Ak (Ck) на параллельно расположенные векторы мерной табли-