Документ взят из кэша поисковой машины. Адрес оригинального документа : http://num-anal.srcc.msu.su/lib_na/cat/ft_htm_p/ftfgc_p.htm
Дата изменения: Fri Nov 27 13:30:58 2015
Дата индексирования: Sun Apr 10 02:28:49 2016
Кодировка: Windows-1251
БЧА НИВЦ МГУ. FTFGC_P. Ускоренные дискретные преобразования Фурье
Текст подпрограммы и версий
ftfgc_p.zip 		Тексты тестовых примеров
tftfgc_p.zip

Подпрограмма:  FTFGC (модуль FTFGC_p)

Назначение

Вычисление всех значений прямого или обратного дискретного преобразования Фурье комплексного ряда длины  K * L,  L = 2 J, только  L последовательно задаваемых значений которого могут быть отличны от нуля, с использованием метода быстрого преобразования Фурье.

Математическое описание

Пусть комплексный ряд  An,  n = 0, 1, ..., N - 1, где  N = K * L,  L = 2 J,  J - натуральное, такое, что только  L его последовательных элементов  AML+S,  S = 0, 1, ..., L - 1, могут быть отличны от нуля (M - заданная константа, 0 ≤ M ≤ K - 1).

B качестве исходной информации задается комплексный ряд  А длины  L,  As = AML+s,  s = 0, 1, ..., L - 1, полностью определяющий преобразуемый ряд  A. Подпрограмма вычисляет значения 

                     L-1                              N-1            
        X r  =    ∑  An W r (ML+n)  =   ∑   A n W r n    ,
                    n=0                              n=0

                   r = 0, 1, ..., N - 1   ,

где  W = e-2π i / N для дискретного преобразования Фурье и  W = e2π i / N для обратного дискретного преобразования Фурье. B вычислениях используется метод быстрого преобразования Фурье.

При больших  N число операций пропорционально  N * (1 + log2L). Данная подпрограмма подробно описана в [1, стp. 42] под именем  FFTLN. Подпрограмма может быть использована для вычисления  N значений функции по L значениям коэффициентов Фурье.

1.  В.А.Морозов, Н.Н.Кирсанова, А.Ф.Сысоев, Комплекс алгоритмов быстрого преобразования Фурье дискретных рядов. Сб. "Численный анализ на ФОРТРАНе", вып. 15, Изд. МГУ, 1976.

Использование 

procedure FTFGC(var ARE :Array of Real; var AIM :Array of Real;
                var N :Integer; L :Integer; M :Integer; var P :Real;
                var XRE :Array of Real; var XIM :Array of Real);


   Параметры
         ARE -
         AIM   		одномерные вещественные массивы длины  L, компоненты которых являются соответственно действительными и мнимыми частями элементов отрезка длины  L, содержащего все отличные от нуля члены преобразуемого ряда  A;
N - заданная длина преобразуемого ряда  A (тип: целый);
L - заданная длина рассматриваемого отрезка отличных от нуля элементов преобразуемого ряда, целая степень двух, делитель  N (тип: целый);
M - заданный параметр, определяющий номеp первого элемента рассматриваемого отрезка преобразуемого ряда. Этот номеp будет pавен  M * L (тип: целый);
P - заданная вещественная переменная, признак преобразования Фурье. При  P > 0. выполняется дискретное преобразование Фурье, при  P < 0. выполняется обратное дискретное преобразование Фурье;
         XRE -
         XIM   		одномерные вещественные массивы длины  N, содержащие вычисленные соответственно действительные и мнимые части элементов преобразованного ряда. 
   Версии:  нет 
   Вызываемые подпрограммы
FTF1C - вычисление дискретного или обратного дискретного преобразования Фурье комплексного ряда длины равной целой степени двух, методом быстрого преобразования Фурье. 
   Замечания по использованию
  1. 

Количество  L элементов преобразуемого ряда, учитываемых при вычислении коэффициентов Фурье, должно быть целой степенью двух 

      L = 2 J ,    J - целое ,    L ≥ 4 .

Общая длина преобразуемого ряда должна быть кpатна  L 

      N = K * L ,     K ≥ 2 ,    0 ≤ M ≤ K - 1
  2. 

Если при обращении к подпрограмме задать  P = 0. , то pезультат ее работы не определен.

  3.  Исходная информация может быть расположена на месте первых  L компонент массива, в котоpом получается pезультат (вместо массивов ARE, AIM можно использовать первые  L компонент массивов XRE, XIM). Если в качестве ARE, AIM, XRE, XIM используются разные массивы, то исходная информация, расположенная в массивах ARE, AIM, сохраняется.

Пример использования 

Unit TFTFGC_p;
interface
uses
SysUtils, Math, { Delphi }
LStruct, Lfunc, UtRes_p, FTFGC_p;

function TFTFGC: String; 

implementation

function TFTFGC: String;
var
I,N,L,M,_i :Integer;
P :RЕal;
ARE :Array [0..3] of Real;
AIM :Array [0..3] of Real;
XRE :Array [0..11] of Real;
XIM :Array [0..11] of Real;
label
_1;
begin
Result := '';
for I:=1 to 4 do
 begin
  ARE[I-1] := I-1.0;
_1:
  AIM[I-1] := 0.0;
 end;
N := 12;
L := 4;
M := 0;
P := 1.0;
FTFGC(ARE,AIM,N,L,M,P,XRE,XIM);
Result := Result + #$0D#$0A;
for _i:=0 to 3 do
 begin
  Result := Result + Format('%20.16f ',[ARE[_i]]);
  if ( ((_i+1) mod 4)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
Result := Result + #$0D#$0A;
for _i:=0 to 3 do
 begin
  Result := Result + Format('%20.16f ',[AIM[_i]]);
  if ( ((_i+1) mod 4)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
Result := Result + #$0D#$0A;
for _i:=0 to 11 do
 begin
  Result := Result + Format('%20.16f ',[XRE[_i]]);
  if ( ((_i+1) mod 4)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
Result := Result + #$0D#$0A;
for _i:=0 to 11 do
 begin
  Result := Result + Format('%20.16f ',[XIM[_i]]);
  if ( ((_i+1) mod 4)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
UtRes('TFTFGC',Result);  { вывод результатов в файл TFTFGC.res }
exit;
end;

end.

Результаты:

      XRE  =  (6.,  1.866025,  -3.5,  -2.,  1.5,  0.1339746,  -2., 
                     0.1339746,  1.5,  -2.,  -3.5,  1.866025)

      XIM(1)    =   0.,    XIM(2)    =  -5.232051,    XIM(3)    =  -2.598076,
      XIM(4)    =   2.,    XIM(5)    =   0.866025,    XIM(6)    =  -1.767949, 
      XIM(7)    =   0.,    XIM(8)    =   1.767949,    XIM(9)    =  -0.866025, 
      XIM(10)  =  -2.,    XIM(11)  =   2.598076,    XIM(12)  =   5.232051