Вторая пачка часть 97
Вы¬ход-ные: x (тип real) - двумерный массив, сфор¬ми¬ро-ван¬ный на месте одноименного вход¬но¬го (см. вы¬ше), содержащий действительные и мнимые час¬ти коэффициентов Фурье, расположенных в ес¬тес¬твенном порядке, - при выполнении прямого БПФ, или комплексный ряд X(m) - при вы¬пол¬не¬нии об¬ратного БПФ.
Примечание. Тип и длина массивов задается в вы¬¬зы¬вающей (головной) программе, например, сл嬬ду¬ю¬щим образом:
. . . . . . . . . . . . . .
TYPE
RT = ARRAY[0..5000] OF WORD;
RP = ^RT;
DRT = ARRAY[0..5000,0..1] OF REAL;
DRP = ^DRT;
VAR NS,T :RP; X :DRP;
. . . . . . . . . . . . . .
PROCEDURE FFT(X:DRP; T,NS:RP; N:WORD;
SIGN:INTEGER);
VAR Y,K,INDX2,I,NR,INDX,IDX,U,P :WORD;
A10,A11,A2,D10,D11,D20,D21,TT :REAL;
BEGIN
IF N=0 THEN
HALT(0); { ЕСЛИ N=0 - ВЫЙТИ ИЗ ПРОЦЕДУРЫ }
{ ПРОВЕРКА НА ТО, ЧТО N=2^N. ЕСЛИ N НЕ ЕСТЬ 2^N ,
ТО В КАЧЕСТВЕ N ВЫБИРАЕТСЯ НАИБОЛЬШЕЕ N'=2^N<N }
IDX:=0;
FOR INDX:=0 TO 12 DO
IF ROUND(POW(2,INDX))<=N THEN
IDX:=INDX;
N:=ROUND(POW(2,IDX));
NR:=ROUND(LN(N)/LN(2));
{ В ЗАВИСИМОСТИ ОТ ЗНАЧЕНИЯ КЛЮЧА SIGN ВЫЧИСЛЯЕТСЯ
БПФ (SIGN=-1) ИЛИ ОБПФ (SIGN=1)}
FOR INDX:=1 TO NR DO
BEGIN { ОСНОВНОЙ ЦИКЛ РАСЧЕТ A ДЛЯ INDX-Й ИТЕРАЦИИ }
A2:=(SIGN*2*PI)/( 1 SHL INDX);
FOR I:=1 TO INDX-1 DO
NS^[I]:=(1 SHL (INDX-I-1));
K:=0;
FOR I:=1 TO INDX-1 DO
BEGIN
FOR Y:=0 TO K DO
T^[K+Y+1]:=T^[Y]+NS^[I];
INC(K,Y+1);
END;
U:=0;
INDX2:=0;
P:=(N SHR (INDX-1));
Y:=P SHR 1;
REPEAT
{ ВЫПОЛНЕНИЕ INDX-Й ИТЕРАЦИИ СОГЛАСНО ГРАФУ БПФ }
A10:=COS(A2*T^[U]);
A11:=SIN(A2*T^[U]); INC(U);
FOR I:=INDX2 TO (INDX2-1+(P SHR 1)) DO
BEGIN
IDX:=I+(P SHR 1);
D10:=X^[I,0]+X^[IDX,0]* A10 -X^[IDX,1]* A11;
D11:=X^[I,1]+X^[IDX,0]* A11 +X^[IDX,1]* A10;
D20:=X^[I,0]+X^[I+Y,0]*(-A10)-
X^[I+Y,1]*(-A11);
D21:=X^[I,1]+X^[I+Y,0]*(-A11)+
X^[I+Y,1]*(-A10);
X^[I,0] :=D10;
X^[I,1] :=D11;
X^[I+Y,0]:=D20;
X^[I+Y,1]:=D21;
END;
INC(INDX2,P);
UNTIL (INDX2=N);
{ КОНЕЦ ЦИКЛА РАСЧЕТА INDX-Й ИТЕРАЦИИ }
FOR I:=0 TO N-1 DO
T^[I]:=0;
END; { КОНЕЦ ОСНОВНОГО ЦИКЛА }
{ ИНВЕРСИЯ ИНДЕКСОВ КОЭФФИЦИЕНТОВ ФУРЬЕ CX }
FOR I:=1 TO NR+1 DO
NS^[I]:=(1 SHL (NR-I));
K:=0;
FOR I:=1 TO NR DO
BEGIN
FOR Y:=0 TO K DO
T^[K+Y+1]:=T^[Y]+NS^[I];
INC(K,Y+1);
END;
{ ВЫЧИСЛЕНИЕ ЗНАЧЕНИЙ КОЭФФИЦИЕНТОВ ФУРЬЕ CX }
FOR I:=0 TO N-1 DO
BEGIN
NS^[I]:=0;
IF SIGN=(-1) THEN
BEGIN
X^[I,0]:=X^[I,0]/N;
X^[I,1]:=X^[I,1]/N;
END;
END;
FOR I:=0 TO N-1 DO
BEGIN
IF NS^[I]=0 THEN
BEGIN
TT:=X^[I,0];
X^[I,0]:=X^[T^[I],0];
X^[T^[I],0]:=TT;
TT:=X^[I,1];
X^[I,1]:=X^[T^[I],1];
X^[T^[I],1]:=TT;
NS^[T^[I]]:=1;
END
ELSE
END;
END {* КОНЕЦ ПРОЦЕДУРЫ БПФ *}
Процедура FFT тестировалась на IBM PC/AT-286 для последовательностей X(m), задававшихся как в ви¬де различного рода функций, так и виде про¬из¬воль¬ных ря¬дов действительных и комплексных чисел при раз-лич¬ных n
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
