Текст подпрограммы и версий ( Фортран )
ftfgc.zip 		Тексты тестовых примеров ( Фортран )
tftfgc.zip
Текст подпрограммы и версий ( Си )
ftfgc_c.zip 		Тексты тестовых примеров ( Си )
tftfgc_c.zip
Текст подпрограммы и версий ( Паскаль )
ftfgc_p.zip 		Тексты тестовых примеров ( Паскаль )
tftfgc_p.zip

Подпрограмма:  FTFGC

Назначение

Вычисление всех значений прямого или обратного дискретного преобразования Фурье комплексного ряда длины  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.

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

    SUBROUTINE  FTFGC (ARE, AIM, N, L, M, P, XRE, XIM) 
   Параметры
         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, сохраняется.

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

      DIMENSION ARE(4), AIM(4), XRE(12), XIM(12)
      DO 1  I = 1, 4
      ARE(I) = I - 1
   1 AIM(I) = 0.0
      N = 12
      L = 4
      M = 0
      P = 1
      CALL  FTFGC (ARE, AIM, N, L, M, P, XRE, XIM)

Результаты:

      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