# Вторая пачка часть 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

Индекс
Элементарные функции Линейные уравнения Нелинейные уравнения Случайные числа