Базовые операции, соответствующие приведенным соотношениям, показаны в правой части графа на рис. 12.39.

Выяснив структуру сигнального графа БПФ, подсчитаем суммарное число операций умножения. При достаточно больших значениях на каждом этапе вычислений (при каждом разбиении последовательности на две более короткие) требуется порядка умножений. При числе разбиений logj/V общее число операций равно примерно N log N (приближенность связана с тем, что умножение на Wn, Wv Wn* и Wf/* сводится просто к сложениям и вычитаниям комплексных чисел).

Итак, при использовании алгоритма БПФ для вычисления ДПФ N-to-чечной последовательности требуется примерно N logN операций умноже-

гев1

ггвб

(309

«ей

teit ге\ъ

«017

eeie га 19

»в2в вв21

вс23

«025

гв2б

«027 19028 «0 2 9

гегъ

«051

»в>з

в0>5

гвзб

8037 «038

гоз9

8041 в0<)2

8044 «045 «046

SUBROUTiNE FFT(NNiX,IN)

ПРОГРАММА ВЫПОЛНЕНИЯ ВП»

Х-КОМПЛЕКСНЫЙ МАССИВ ПРЕОБРАЗУЕМЫХ ОТСЧЕТОВ ММ-тЧИСЛО ПРЕОБРАЗУЕМЫХ ОТСЧЕТОВ. РАВНОЕ ЦЕЛОЙ СТЕПЕНИ ДВОЙКИ! НЕ ПРЕВЫЙАМЫЕЕ 512 1Н=Я ЛЛЯ ПРЯМОГО ПРЕОБРАЗОВАНИЯ IN=l аля ОБРАТНОГО ПРЕОБРАЗОВАНИЯ

COMPLEX X(512)(W,Т

IRsNN 10 lRsIR/2

IF(IR,Ea.01 50 ТО 20 IT=tT*l GO To 10 20 CONTINUE-Sls-l.

IF(tN,E9,n Sisl,. NX2=NN

00 50 tTT=J(tT >X=NX2 • NX2=NX/2

>iP = 3.14l592/FU0AtlNx2i

DO 4if M = l NX2

ARC=fLOAT(Mrl)»Wp

VI = CMPLX(COS(ARC) 3I»SIN!ARC)

DO 40 «X=NX,NNiHX

Jl=HX-NX*M

02=Jl*MX2

T=X(J1IX(J2)

X(JU=X(01)+X(g2) 42 X(02)=T«W 50 CONTINUE

N2=NN/2

DO 65 1=1(H1 IFir.Ce.J) CP TO 55 T=X(J) X(JI=X(I) . XdJeT 55 K=MM/2

6J3 IFIK.GE.O) G"p TO 65

0=J-K

K=K/2 . , CO TO

J=J*K

IF (IN.EO.l.i CO TO 75

00 70 JsliNN Iji XdJsXdI/fLOATNN) -75 CONTINUE

RETURN

ния. Ранее было показано, что при прямом вычислении ДПФ по выражению (12.73) требуется Л умножений. Следовательно, алгоритм БПФ уменьшает число операций в NIN hgN. При = 1024 (г - 10) loga = 10 и A/loga л; 100. Столь большое сокращение числа операций резко уменьшает объем аппаратуры и повышает быстродействие цифровых устройств. Из рассмотрения графа следует, что экономия достигается благодаря объединению всех слагаемых, подлежащих умножению на однаковые множители.

К обоснованию алгоритма БПФ можно также прийти, используя метод факторизации матрицы, описывающей дискретное преобразование (12.73) [21].

Для большей наглядности все предыдущее рассмотрение проводилось в предположении действительного (вещественного) сигнала. Однако результаты можно распространить и на комплексный сигнал.

На с. 390 приведена программа вычисления прямого и обратного преобразований Фурье как для действительного, так и крмплексного сигнала с базой до 512.

Существует большое разнообразие вариантов построения схем БПФ.

12.15. СПЕКТРАЛЬНЫЙ АНАЛИЗ НА БАЗЕ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

Обратимся к выражению (12.13) для ДПФ

N-1 --jr""

S(n) = -s(k)e , n=0, ± 1, ±2,..., ±/V/2,

и к рис. 12.40, иллюстрирующему преобразование исходного сигнала s (t), начиная с его дискретизации с шагом Т до выделения спектральных коэффициентов S (п) на выходе устройства, осуществляющего ДПФ. Это устройство обозначено на рис. 12.40 в виде «черного ящика» ДПФ (БПФ) без раскрытия его внутренней структуры.

Если шаг Т выбран достаточно малым для сохранения содержащейся в сигнале s (t) информации, то и совокупность спектральных коэффициентов S (п) дает полную информацию о всем спектре S((o) континуального сигнала S (t). На рис. 12.40 функция 5 (со) обозначена штриховой линией в виде огибающей дискретного спектра 5 (п) в пределах центрального участка диапазона частот от О) == - я/Т до со = я/Т или, что то же, от соТ - О до соТ = = 2я (соответственно от n = О до n = - 1, см. нижнюю часть рис. 12.40).

С этой точки зрения устройство, осуществляющее ДПФ, можно трактовать как анализатор спектра, представляющий собой набор из узкополосных фильтров, каждый из которых пропускает одну дискретную частоту пАо).

Поскольку в образовании любого из спектральных коэффициентов S (п) участвуют все временные отсчеты s (k), то информацию о спектре сигнала S (i) можно получить не ранее чем после ввода в устройство БПФ всех отсчетов S (k). В этом смысле ДПФ не отличается от обычного преобразования Фурье, определяемого выражением

S(o)) = J sit) e-"dt, tT.

Нетрудно выявить АЧХ любого из упомянутых выше фильтров, образующих анализатор спектра. С этой целью зададим испытательный сиг-

5(0)

-(sr.)}

A=<7,/...., -/ - -

5 (N4)

Рис. 12.40. К определению ДПФ сигнала s (t)

01 Z N/l Ы-1 n

нал на входе анализатора в виде гармонического колебания с частотой со, не превышающей я/Г, что вытекает из теоремы отсчетов (см. § 2.16).

Для упрощения выкладок удобно исходить из комплексного испытательного сигнала, заданного в одной из двух форм (при - оо < < оо):

S (t) = cos at + i sin Ш = е

(12.81)

s (t) cos oit - i sin at e-<- (12.82)

Поддерживая неизменной амплитуду (1 В) входного сигнала, проследим за изменением спектрального коэффициента S (п) в зависимости от со. После дискретизации s (t) с шагом Т получим временные отсчеты вида

s(fe)=e"*?", k0,\,..., N - l,

s(fe) = e-* k = 0,l.....N-l,

где N = TJT.

Рассмотрим сначала случай s (t) = e<*, когда выражение (12.13) принимает форму

S (п, аТ) = У е»* i

ft=0

{wT -

«=.= 0, 1,..., N12, 0<сйГ<я.

(12.83)

При отрицательных значениях п коэффициенты S (п, аТ) равны нулю, поскольку спектральная плотность аналитического сигнала е"» отлична от нуля только в области частот со > О [см. § 3.10 и формулу (3.87)].

Новое обозначение S {п, аТ) имеет тот же смысл, что и S (п), т. е. это спектральный коэффициент на фиксированной частоте п ка, однако модуль и аргумент этого комплексного коэффициента зависят от частоты со исходного сигнала s (t), из которого взяты временных отсчетов.

Введем обозначение х = аТ - п и запишем (12.83) в форме

N-1 N-1 W-1

S (п, аТ) = 2 е* = 2 kx + i sin kx.