Ирина Эланс

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

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

Сколько операций требуется на проведение дискретного преобразования Фурье? Посчитав по определению (N раз суммировать N слагаемых), получаем величину порядка N ². Тем не менее, можно обойтись существенно меньшим числом операций.

Наиболее популярным из алгоритмов ускоренного вычисления ДПФ является т.н. метод Cooley-Tukey, позволяющий вычислить ДПФ для числа отсчетов N = 2 ^kза время порядкаNlog₂N (отсюда и название - быстрое преобразование Фурье, БПФ). Этот способ чем-то неуловимо напоминает быструю сортировку. В ходе работы алгоритма также проводится рекурсивное разбиение массива чисел на два подмассива и сведение вычисления ДПФ от целого массива к вычислению ДПФ от подмассивов в отдельности.

Изобретение БПФ привело к потрясающему всплеску популярности преобразования Фурье. Целый ряд важных задач раньше решался за время порядка N ², но после проведения преобразования Фурье над исходными данными (за время порядка Nlog₂N) решается практически мгновенно. Преобразование Фурье лежит в основе цифровых корелляторов и методов свертки, активно используется при спектральном анализе (практически в чистом виде), применяется при работе с длинными числами.

Широко распространено ошибочное мнение о том, что метод Cooley-Tukey - единственный существующий метод выполнения БПФ, а само БПФ существует только для случая N = 2 ^k. На самом деле это не так - существуют алгоритмы БПФ для любого числа отсчетов. В одномерном случае, рассмотренном в этой статье, метод Винограда позволяет решить задачу для простого числа отсчетов N. Этот же алгоритм может быть легко обобщен на случай, когда N является степенью произвольного простого числа (а не только двойки), а также на случай, когда число N является произведением степеней простых чисел - т.е. N является произвольным числом, чье разложение на простые множители нам известно.

В двумерном случае можно использовать метод Нуссбаумера. Существуют и другие алгоритмы, как для одномерного, так и для двумерного случаев, но рассмотрение этих вопросов выходит за рамки статьи (мне рекомендовали следующий источник - Блейхут, "Быстрые алгоритмы цифровой обработки сигналов").

Как уже говорилось выше, существуют алгоритмы БПФ для произвольного числа отсчетов, но наиболее широкое распространение получил только алгоритм для случая N = 2 ^k, что является существенным ограничением. Почему же это произошло?

Причина этого в том, что алгоритм, построенный по методу Cooley-Tukey, обладает рядом очень хороших технологических свойств. Структура алгоритма и его базовые операции не зависят от числа отсчетов (меняется только число прогонов базовой операции "бабочка"). Алгоритм легко распараллеливается с использованием базовой операции и конвееризуется, а также легко каскадируется (коэфициенты БПФ для 2N отсчетов могут быть легко получены преобразованием коэфициентов двух БПФ по N отсчетов, полученных "прореживанием" через один исходных 2N отсчетов). Алгоритм прост и компактен, не требует дополнительной оперативной памяти и допускает обработку данных "на месте". Существует целый ряд оптимизированных именно для этого алгоритма DSP-процессоров (это одновременно и причина, и следствие).

Всё это и обусловило популярность в инженерно/программистской среде именно этого алгоритма, и, соответственно, выбора именно 2 ^kотсчетов при использовании БПФ. Правда, попутно это привело к незаслуженному забвению широкими массами альтернативных алгоритмов, некоторые из которых (что следует отметить) требуют меньше вещественных операций на один отсчет, чем алгоритм Cooley-Tukey.

Современноеa состояние вычислительной техники характеризуется

большим расширением сферы цифровой обработки сигналов. Широкое

распространение получают исследования в области цифровых звукозапи-

сывающих и звуковоспроизводящих устройств, цифрового телевидения,

цифровых фильтров различного рода сигналов вплоть до радиосигналов.

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

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

Одним из путей удовлетворения этих потребностей является выбор

разумно построенных алгоритмов. Вместо того чтобы повышать быстро-

действие процессора от одного миллиона умножений в секунду до пяти

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

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

ножений в секунду оказалось достаточно. К настоящему моменту имеется

хорошо разработанная теория, позволяющая подойти к решению задач с

этих позиций. Она хорошо известна теоретикам, специалистам в данной

области, но на практике инженеры-конструкторы часто пренебрегают ею,

поскольку она пока недоступна в виде единого научного подхода. Инже-

нер-конструктор должен хорошо знать предмет, чтобы выбрать алгоритм,

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

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

ния Фурье.

2.1. Свойства дискретного преобразования Фурье

Некоторые свойства ДПФ играют важную роль в практических во-

просах обработки сигналов. Ниже они будут в основном перечислены, де-

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

Линейность

Если хр(n) и yp(n) - периодические последовательности (с периодом в

N отсчетов каждая), a Xр(k), Yp(k) - их ДПФ, то дискретное преобразование

Фурье последовательности хр(n) + yp(n) равно Xр(k) + Yp(k). Это положение

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

Свойства симметрии

Если периодическая последовательность хр(n) с периодом в N отсчё-

тов является действительной, то ее ДПФ Xр(k) удовлетворяет следующим

условиям симметрии:

Re[Xp(k)] = Re[Xp(N - k)];

Im[Xp(k)] = -Im[Xp(N - k)];

½Xp(k)½ = ½Xp(N - k)½;

arg[Xp(k)] = - arg[Xp(N - k)].

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

ной последовательности x(n), имеющей N-точечное ДПФ X(k). Если ввести

дополнительное условие симметрии последовательности xp(n), т.е. считать,

что xp(n) = xp(N - n), тo окажется, что Xр(k) может быть только действитель-

ной.

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

последовательностями, то, вычислив одно ДПФ, можно получить ДПФ

двух последовательностей, используя свойства симметрии. Рассмотрим

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

дом в N отсчётов и N -точечными ДПФ Xр(k) и Yр(k) соответственно. Вве-

дем комплексную последовательность zp(n) вида zp(n)= xp(n)+j×yp(n).

Ee ДПФ

( ) j N nk

Z p k xp n j yp n e (2 / )

[ ( ) ( )] - p

= å + × × ;

Zp(k) = Xp(k) + j×Yp(k).

Выделяя действительную и мнимую части равенства, получим

Re[Zp(k)] = Re[Xp(k)] - Im[Yp(k)];

Im[Zp(k)] = Im[Xp(k)] + Re[Yp(k)].

Действительные части Xp(k) и Yp(k) cиммeтpичны, а мнимые анти-

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

и вычитания:

[ ( )]

Re[ ( )] Re[ ( )]

Z k Z N k

X k p p

+ -

= ;

[ ( )]

Re[ ( )] Re[ ( )]

Z N k Z k

Y k p p

- -

= ;

[ ( )]

Im[ ( )] Im[ ( )]

Z k Z N k

Y k p p

+ -

= ;

[ ( )]

Im[ ( )] Im[ ( )]

Z k Z N k

X k p p

- -

= .

– 28 –

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

две действительные последовательности длиной по N/2 отсчетов. Если эти

последовательности являются еще и симметричными, то число операций,

необходимых для получения их ДПФ, можно сократить еще больше.

2.2. Алгоритмы быстрого преобразования Фурье

Из выражения (2.2) видно, что ДПФ является трудоемкой

пpoцeдуpoй, включaющeй (N - 1)2 комплексных умножений и N×(N - 1)

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

нение прямого ДПФ при цифровой обработке сигналов.

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

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

прямого вычисления ДНФ значительно меньшей трудоемкостью. Особен-

но следует отметить алгоритм быстрого преобразований Фурье (БПФ)[1, 3,

20, 23, 25] , алгоритм Винограда преобразования Фурье (АВПФ) [1, 20] и

метод двойного преобразования [22].

Основная идея быстрого преобразования Фурье (БПФ) состоит в

том, чтобы разбить исходную N -точечную последовательность на две бо-

лее короткие последовательности, ДПФ которых могут быть скомбиниро-

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

довательности. Далее полученные короткие последовательности аналогич-

но разбивают на еще более короткие и т.д. В результате прямое ДПФ не-

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

r - основание алгоритма БПФ. Следует отметить, что прямое ДПФ для r = 2

и r = 4 не содержит нетривиальных умножений. Однако, БПФ для N > 4

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

ДПФ (для алгоритма с прореживанием по времени), либо после него (для

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

на фазовые множители [23]. Таким образом, N-точечное БПФ будет вы-

полняться за m = logr N этапов (на каждом этапе необходимо выполнить

N/r прямых ДПФ и умножить входные или выходные отсчеты на фазовые

множители).

АВПФ основан на применении теоретико-числовых методов

(полиномиальной алгебры, китайской теоремы об остатках) при

вычислении ДПФ.

Метод двойного преобразования заключается в том, что сначала ис-

ходный сигнал подвергается преобразованию Уолша, Хаара или Адамара

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

тривиальных умножений), а затем осуществляется переход в базис Фурье

умножением на определенную матрицу перехода. Этот метод эффективен

только для последовательностей небольшой размерности.

Несмотря на обилие методов преобразования Фурье [1, 23], в на-

– 29 –

стоящее время не существует универсального алгоритма ДПФ, отличаю-

щегося во всех случаях минимальной трудоемкостью. Далее будет рас-

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

синтезированному в работе [18]. Этот метод позволяет решать задачу ДПФ

с приемлемым быстродействием.

2.3. Алгоритм быстрого преобразования Фурье с основанием 2

и прореживанием по времени

Если N - четное число, а исходная N-точечная последовательность

разбита на две (N/2) -точечные последовательности, то для вычисления ис-

комого N-точечного ДПФ потребуется около (N×/2)2×2 = N 2 /2 комплексных

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

здесь множитель (N/2)2 дает число умножений, необходимое для прямого

вычисления (N/2)-точечного ДПФ, а множитель 2 соответствует двум

ДПФ, которые должны быть вычислены. Эту операцию можно повторить,

определяя вместо (N/2)-точечного ДПФ два (N/4)-точечных ДПФ (предпо-

лагая, что ((N/2) - четное) и сокращая тем самым объем вычислений еще в

два раза. Выигрыш в два раза является приближенным, поскольку не учи-

тывается, каким образом из ДПФ меньшего размера образуется искомое

N-точечное ДПФ.

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

тельности {x(n)} считая, что N равно степени 2. Введем две (N/2)-точечные

последовательности {x1(n)} и {x2(n)} из четных и нечетных членов x(n) со-

ответственно, т.е. x1(n) = x(2n), n = 0, 1, …, (N /2) – 1; x2(n) = x(2n + 1),

n = 0, 1, …, (N /2) – 1.

При этом N-точечное ДПФ последовательности {x(n)} можно запи-

сать как

( ) å å å å

= + = + +

/ 2 1

(2 1)

/ 2 1

1( ) ( ) (2 ) (2 1)

n k

X k х n WN х n W х n W х n W

С учетом того, что [ ( ) ] ( ( )) / 2 ,

2 2 / 2 2 / / 2

j N j N

WN = e = e =W - p - p

получим

() ( ) ( )

() ( ) ( ) ïþ

ïý

= + ×

= å × + å ×

;

1 2

/ 2 1

2 / 2

/ 2 1

1 / 2

X k X k W X k

X k x n W W x n W

n k

N , (2.6)

где X1(k) и X2(k) равны (N /2) -точечным ДПФ последовательностей x1(n) и

x2(n).

Из формул (2.6) следует, что N-точечное ДПФ X(k) может быть раз-

ложено на два (N/2)-точечных ДПФ, результаты которых объединяются.

Если бы (N/2)-точечные ДПФ вычислялись обычным способом, то для вы-

числения N-точечного ДПФ потребовалось бы, очевидно, (N 2/2 + N) ком-

плексных умножений. При больших N (когда N 2/2 >> N) это позволяет со-

– 30 –

кратить время вычисления на 50 %.

Поскольку X(k) рассчитано при 0 £ k < N, a X1(k) и X2(k) рассчитаны

при 0 £ k £ N /2 - 1 , то необходимо доопределить формулу (2.6) для

k ³ N/2. Это определение очевидно и может быть записано следующим

образом:

( )

( ) ( )

ï ïî

ï ïí

- £ £ ÷ø

çè

+ × æ - ÷ø

çè

æ -

+ × £ £ -

k N 1.

, N

2 2

, 0 k N

1 2

X k N W X k N

X k W X k

X k

(2.7)

На рис. 2.1 с помощью направленного графа представлена последо-

вательность операций при выполнении восьмиточечного ДПФ с использо-

ванием двух четырехточечных преобразований. Входную последователь-

ность х(n) сначала разбивают на две последовательности х1(n) и x2(n) из

четных и нечетных членов x(n), после чего paccчитывaют их преобразова-

ния X1(k) и X2(k). Затем в соответствии с формулой (2.7) получают X(k).

x1(0) = x(0)

x1(1) = x(2)

x1(2) = x(4)

x1(3) = x(6)

x2(0) = x(1)

x2(1) = x(3)

x2(2) = x(5)

x2(3) = x(7)

Четырех-

точечное

ДПФ

Четырех-

точечное

ДПФ

X1(0)

X1(1)

X1(2)

X1(3)

X2(0)

X2(1)

X2(2)

X2(3)

X(0)

X(1)

X(2)

X(3)

X(4)

X(5)

X(6)

X(7)

a Wk 8 ×

a + b

a - b

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

через два четырехточечных дискретных преобразования Фурье

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

чета N/2 -точечных ДПФ в соответствии с формулами (2.6) и (2.7). Каждая

из последовательностей х1(n) и х2(n) разбивается на две поcледовательно-

сти, состоящие из четных и нечетных членов. Аналогично 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 ;

F f W f

, (2.10)

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

Поскольку 0 1

W8 = и 1 4

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

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

– 32 –

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)

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

( ) å å

= × + =

/ 2

/ 2 1

( ) ( )

n N

n k

X k x n WN x n W

( ) ( ) ( ).

/ 2 1

/ 2

/ 2 1

å 1 å

+ ×

= × × + ×

n N k

n k

x n WN x n W

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

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

( ) [ ( ) ( )] .

/ 2 1

å 1 2

= + - ×p× × × ×

n k

X k x n e j k x n W

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

ДПФ:

– 34 –

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

/ 2 1

1 2 / 2

/ 2 1

å 1 2 å

= + × × = + ×

n k

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

( + ) = å[ - ] =

× +

/ 2 1

(2 1)

2 1 1( ) 2 ( )

n k

X k x n x n WN

[ ( ) ( ) ] .

/ 2 1

å 1 2 / 2

= - × ×

n k

x n x n WN W (2.12)

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

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

q (n) :

( ) ( ) ( )

( ) [ ( ) ( )] 1.

, 0,...,

1 2

= - × = -

= + = -

q n x n x n W n N

f n x n x n n N

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

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

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

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.4. Переход от. восьмиточечного дискретного преобразования Фурье

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

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

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

ДПФ.

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

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

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

– 35 –

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 2

W 0

W 2

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]

l N

X i N k k , , 1 º úû

êë

é +

+ ; (2.13)

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

j N k

k = - - ,

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

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

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

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

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

[ ] [ ]

[ ] [ ] ïþ

ïý

= ×

× ×

å -

, , : , , , = 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

n l

k k r (2.15)

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

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.

÷ø

çè

úû

êë

é ×

× p

× - úû

êë

é ×

× p

= º

- ×

l j

W e

j lN

(2.17)

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

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

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

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

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

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

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

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

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

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

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

ï ï ï ï

- Ü × ×

Ü × ×

× × =

-1, (mod ) = 3

;

-1, (mod ) =

;

-1, (mod ) =

1, (mod ) = 0;

l j r N N

l j r N

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;

X i l j R l W l r

R l X i n j W l r

k r j lN r

n l

r (2.20)

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

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

a a

r r a

r r

(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) и ком-

Быстрое преобразование Фурье 📙 Курсовая → 🆔 43723