БЧА НИВЦ МГУ. FTA1C_P. Ускоренные дискретные преобразования Фурье

Документ взят из кэша поисковой машины. Адрес оригинального документа : http://num-anal.srcc.msu.ru/lib_na/cat/ft_htm_p/fta1c_p.htm
Дата изменения: Fri Nov 13 11:25:52 2015
Дата индексирования: Sun Apr 10 03:37:45 2016
Кодировка: Windows-1251

Текст подпрограммы и версий
fta1c_p.zip , fta1z_p.zip

Тексты тестовых примеров
tfta1c_p.zip , tfta1z_p.zip

Подпрограмма: FTA1C (модуль FTA1C_p)

Назначение

Выполнение прямого и обратного быстрых дискретных преобразований Фурье одномерного массива комплексных чисел длины N, равной целой степени двух.

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

Пусть известны значения h_k = h (t_k) комплексно - значной функции h (t) на равномерной сетке t_k = k Δt, k = 0, 1, 2, ..., N - 1 (где Δt - шаг сетки, а N равняется целой степени двух), заданные в виде одномерного массива комплексных чисел ARRAY длины N.

Подпрограмма FTA1C имеет два режима работы, задаваемых при обращении к ней значением параметра IREG. В первом режиме (IREG = 1) выполняется прямое быстрое дискретное преобразование Фурье заданного массива ARRAY, состоящее в получении N комплексных чисел H_n (n = 0, 1, 2, ..., N - 1) из N комплексных чисел h_k (k = 0, 1, 2, ..., N - 1), являющихся элементами этого массива, по формуле:

                                      _N-1
                           H_n  =   ∑    h_k e^{2π i k n / N} 
                                      ^{k =0}

Вычисленные значения H_n располагаются в том же массиве ARRAY. Во втором режиме (IREG = - 1) выполняется обратное быстрое дискретное преобразование Фурье, состоящее в восстановлении из значений H_n (n = 0, 1, 2, ..., N - 1), заданных в виде одномерного массива комплексных чисел ARRAY длины N, значений h_k (k = 0, 1, 2, ..., N - 1) по формуле:

                                              _N-1
                           h_k  =  1/N    ∑    H_n e ^{-2π i k n / N}
                                              ^{n =0}

Вычисленные значения h_k располагаются в том же массиве ARRAY.

Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков. Численные методы. Изд - во "Наука", 1987.

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

procedure FTA1C(var ARRAY_ :Array of Real; N :Integer; IREG :Integer);

   Параметры

ARRAY_ -	вещественный одномерный массив, имитирующий комплексный одномерный массив длины N, содержащий на входе значения h_k (IREG = 1) или H_n (IREG = - 1), а на выходе значения H_n (IREG = 1) или h_k (IREG = - 1);
N -	длина комплексного одномерного массива равная целой степени двух (тип: целый), где 2N - длина массива ARRAY_;
IREG -	задает режим работы подпрограммы (тип: целый); при этом:

IREG= 1 -	когда выполняется прямое преобразование;
IREG= -1 -	когда выполняется обратное преобразование.

   Версии

FTA1Z -

выполнение прямого и обратного быстрых преобразований Фурье одномерного массива, имитирующего массив комплексных чисел длины N, равной целой степени двух, в режиме расширенной (Extended) точности; при этом параметр ARRAY_ должен иметь тип Extended и иметь длину, равную 2N (см.также "Замечания по использованию").

   Вызываемые подпрограммы:  нет

   Замечания по использованию

	1.	В подпрограммах FTA1C и FTA1Z проверка того, что значение N должно быть целой степенью двух, не производится.
	2.	При обращении к подпрограмме FTA1C массив ARRAY_ всегда является вещественным. В этом случае его длина должна равняться 2N, а его элементы должны формироваться по следующему правилу: ARRAY_( I ) = Re (h_i) , если IREG= 1 ARRAY_( I ) = Re (H_i) , если IREG= - 1 ARRAY_(I+1) = Im (h_i) , если IREG= 1 ARRAY_(I+1) = Im (H_i) , если IREG= - 1 Здесь Re означает вещественную часть комплексного числа, Im - мнимую часть, I = 1, 2, ..., 2N - 1; i = 0, 1, ..., N - 1.
	3.	При обращении к подпрограмме FTA1Z массив ARRAY_ должен быть вещественным расширенной (Extended) точности длины 2N. Правила задания его содержимого такие же, как и в замечании 2. Если это допускает входной язык компилятора, массив ARRAY_ может быть описан как Complex длины N.
	4.	Для того чтобы избежать вычислений с использованием комплексной арифметики, подпрограммы FTA1C и FTA1Z рассматривают массив ARRAY_ всегда не как комплексный, а как вещественный длины 2N одинарной или расширенной (Extended) точности соответственно.

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

Unit tfta1c_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, FTA1C_p;

function tfta1c: String;

implementation

function tfta1c: String;
var
_i :Integer;
A :Array [0..3] of Complex;
_rar :Array of Real;   //рабочий динамический массив
begin
Result := '';  { результат функции }
A[0] := Cmplx(1.0,0.0);
A[1] := Cmplx(4.0,0.0);
A[2] := Cmplx(7.0,0.0);
A[3] := Cmplx(10.0,0.0);
SetLength(_rar,2*(High(A)+1));  //установка длины рабочего динамического массива
for _i:=0 to High(A) do
 begin
 _rar[2*_i] := A[_i].re;        //заполнение рабочего динамического массива
 _rar[2*_i + 1] := A[_i].im;    //по значениям действительной и мнимой частей массива A
 end;

FTA1C(_rar,4,1);

for _i:=0 to High(A) do
 begin
 A[_i].re := _rar[2*_i];        //заполнение действительной и мнимой частей исходного массива A
 A[_i].im := _rar[2*_i + 1];    //по значениям рабочего динамического массива
 end;
Result := Result + #$0D#$0A;
for _i:=0 to 3 do
 begin
  Result := Result + Format('%20.16f %20.16f ',[A[_i].re,A[_i].im]);
  if ( ((_i+1) mod 2)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
UtRes('tfta1c',Result);  { вывод результатов в файл tfta1c.res }
exit;
end;

end.

Результаты:

         A(1) = ( 22.0, 0.0),   A(2) = (- 6.0, - 6.0), 
         A(3) = (- 6.0, 0.0),    A(4) = (- 6.0,   6.0)