с учетом равенств

WnI2, WlW (12.78)

правые части выражений (12.76), (12.77) можно привести к виду

2 Si(ft)n"2 = Si(n), IFjx

i I I I I I I

10 12. /4. -Ы/1-м

, I I М i I ,

I I I I j I I 1 I

* = o

0 2 В 8 10 1Z 1 18

/5 12 14 16

Рис. 12.37. Спектры ДПФ последовательностей четных отсчетов (а), нечетных отсчетов (б) и исходной последовательности (в)

X 2 su(fe) n% = nsii(«)- й>

в этих выражениях Si (п) и Sn (л) представляют собой ДПФ соответственно четной и нечетной подпоследовательностей.

Заменой Wn" на Гма учитывается, что шаг дискретизации в {s\ (k)} и {sii (Щ вдвое больше, чем в исходной последовательности {s (fe)}.

( 2£L

Фазовый множитель W% = е перед второй суммой учитывает за-

держку последовательности {зц (k)} на один интервал относительно последовательности {si (k)} (см. рис. 12-36).

На рис. 12.37, ан б представлен примерный вид спектров Si (п) и Sn (п). В соответствии с числом временных отсчетов N/2 число спектральных коэффициентов также равно N/2 (п - 0,1.....N/2 - 1). Штриховыми линиями на

рисунках показано периодическое продолжение спектра на участок N/2 < п< - 1.

Результирующее ДПФ S (п) исходной последовательности {s (k)} можно выразить через Si (п) и Sn (л).

В диапазоне п =0,1, N/2- 1 имеет место очевидное соотношение

S(rt)S, in)+W%Su(n).

В диапазоне п = N/2, N12 + 1,..., Л - 1 можно, основываясь на периодичности Si (л) и Sii (п) (с периодом N12), исходить из равенств

Si(n) = S,(n-A?/2), S„(n) = Sii(rt-iV/2). (12.79)

Кроме того, необходимо учитывать перемену знака перед фазовым множителем при п N12:

поскольку W/2=re

JV 2

В результате приходим к следующему выражению для ДПФ всей последовательности:

S(a) =

Si (л)+ 117 Sii (л), 0<«<yV/2-I,

Si (n - N/2) - Wy Sii (n-N/2), /V/2 < n < iV- 1.

(12.80)

Спектр S (ri) содержит Л спектральных отсчетов на интервале одного периода (на оси п), как это представлено на рис. 12.37, в.

Заметим, что Si (п - Л/2) и Sn (п - N/2) совпадают с соответствующими значениями Si (п) и Sn (п).

Выяснив структуру спектров Si (п) и Sn (п), подсчитаем число операций умножения, требующихся для получения спектральных коэффициентов при использовании алгоритма (12.80). Для вычисления функций Si (п) и Sn (п) требуется (Л/2) умножений отсчетов s (k) на комплексные коэффициенты Wn- Кроме того, требуется Л умножений Sn (п) на коэффициент Wn- Всего требуется 2 (iV/2) -f N умножений, т. е. почти вдвое меньше, чем при использовании алгоритма (12.73).

Разбиением каждой подпоследовательности можно осуществить дальнейшее уменьшение объема вычислений. Разбиение следует продолжать вплоть до получения простейших, двухэлементных последовательностей. Определив ДПФ указанных простейших пар отсчетов, можно найти ДПФ етырехэлементных, восьмиэлементных и т. д. последовательностей. При объединении ДПФ двух подпоследовательностей можно руководствоваться алгоритмом (12.80), подставляя в него соответствующие значения N н п.

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

При обозначениях (12.80) базовая операция принимает вид, показанный на рис. 12.38, б. Основанный на этой базовой операции сигнальный граф объединения двух ДПФ представлен на рис. 12.38, в.

Проиллюстрируем описанный способ построения полного графа БПФ от двухточечных до -точечных ДПФ на примере N = 8.

После первого разбиения последовательности {s (k)} получаются две четырехэлементные последовательности {si} и (sn), показанные в левой части рис. 12.39. В первой из них четными считаются Si (0) = s (0) и Sj (2) = = s (4), а нечетными Sj (1) = s (2) и Si (3) = si (6). Поэтому последовательность {si} распадается на две пары: а (0), а {\) и b (0), b (1) [т. е. s (0), s (4) и S (2), S (6)].

Аналогично последовательность {sn} распадается на две пары: с (0), с (1) и d (0), d (1).

S (/V-f)

Рис. 12.38. Базовые операции, используемые в алгоритме БПФ

s(S)-s(f)»-Ч/cCfJ-sff)

b(1)- s ® « SIH.

Рис. 12.39. Сигнальный граф БПФ при Л? = 8

Определим ДПФ двухэлементных последовательностей. Для пары а (0),

а(1) откуда

Л(0)=а(0) + а(1)Г?,/4 = а(0) + а(1), Л(1) = а(0) + а(1)Г/4 = = а(0) + а(1)1П-«(0)-а(1).

Как видим, для вычисления Л (0) и Л (1) не требуется умножений. Нужно лишь образовать сумму с (0) + а (1) и разность а (0) - а (1), т. е. S (0) + S (4) и S (0) - S (4).

На рис. 12.39 для операции сложение-вычитание использована символика, совпадающая с операцией «бабочка» при = 1: верхний вывод соответствует сумме, а нижний - разности.

Аналогичным образом на рис. 12.39 обозначены ДПФ остальных пар: 6(0), 6(1)-(0).с(1), Hd(0),d(l).

Следующий шаг объединение ДПФ А (п) и В (п). Число спектральных коэффициентов в суммарном ДПФ равно 4: л = О, 1, 2 и 3.

По аналогии с (12.80) можем написать

S, (л) =

A(n) + WlB(n),n=0, 1, ,Л(л-2j-1Г<«-2)В(л-2), п = 2, 3.

Учитывая, что W» = Wl, переписываем последнее выражение в форме

S,(„)= iA{n) + Wl-Bin),n = 0, 1,

U(rt-2)-ir2(«-2) В(а 2), л = 2, 3.

Итак,

5,(0) = Л(0)-Ь W»5(0), S,(l) = (l)-f W,B(1), Si (2) A {0)~WI В (0), S, (3)-Л (0)- В (1).

Аналогичные выражения нетрудно составить для ДПФ Sn (л), объединяющего ДПФ С (п) и D (л).

см. Базовые операции для Si (л) и Sn (л) одинаковы (см. рис. 12.39).

Для определения ДПФ всей последовательности из восьми отсчетов нужно воспользоваться выражением (12.80) и графом, представленным на рис. 12.38, в при Л = 8.