Текст подпрограммы и версий
ftfgc_c.zip 		Тексты тестовых примеров
tftfgc_c.zip

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

Назначение

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

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

    int ftfgc_c (real *are, real *aim, integer *n, integer *l,
            integer *m, real *p, real *xre, real *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_c - вычисление дискретного или обратного дискретного преобразования Фурье комплексного ряда длины равной целой степени двух, методом быстрого преобразования Фурье. 
   Замечания по использованию
  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, сохраняется.

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

int main(void)
{
    /* Local variables */
    static int i__, l, m, n;
    static float p;
    extern int ftfgc_c(float *, float *, int *, int *,
                       int *, float *, float *, float *);
    static float aim[4], are[4], xim[12], xre[12];

    for (i__ = 1; i__ <= 4; ++i__) {
        are[i__ - 1] = i__ - 1.f;
/* l1: */
        aim[i__ - 1] = 0.f;
    }
    n = 12;
    l = 4;
    m = 0;
    p = 1.f;
    ftfgc_c(are, aim, &n, &l, &m, &p, xre, xim);

    for (i__ = 1; i__ <= 4; ++i__) {
    printf("\n %16.7e %16.7e \n",are[i__-1], aim[i__-1]);
    }
    for (i__ = 1; i__ <= 12; ++i__) {
    printf("\n %16.7e %16.7e \n",xre[i__-1], xim[i__-1]);
    }
    return 0;
} /* main */


Результаты:

      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