Текст подпрограммы и версий
ftf1c_c.zip , ftf2c_c.zip 		Тексты тестовых примеров
tftf1c_c.zip , tftf2c_c.zip

Подпрограмма:  ftf1c_c (версия ftf2c_c)

Назначение

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

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

Элементы  Xr ,  r = 0, 1, ..., L - 1 преобразуемого комплексного ряда  X связаны с элементами  A (S) ,  S = 1, 2, ..., N задаваемого комплексного массива A соотношениями 

      Xr = A (IN + r * K) ,     r = 0, 1, ..., L - 1

Здесь натуральное  K задает шаг выбора,  IN определяет номер первого выбираемого элемента. При этом  N = K*L,  1 ≤ IN ≤ K, а  L должно быть степенью двух  L = 2M,  M - натуральное. Заметим, что если  IN = 1,  K = 1, то ряд  X целиком заполняет задаваемый массив  A. Ряд  X преобразуется в комплексный ряд  Y по формуле 

                   L-1             
        Yr  =   ∑   Xm*W m r  ,      r = 0, 1, ..., L-1  ,
                  m=0

где  W = e- 2π i / L для дискретного преобразования Фурье (ДПФ) и  W = e2π i / L для обратного дискретного преобразования Фурье (OДПФ).

Для вычислений используется метод быстрого преобразования Фурье. Подпрограмма реализует алгоритм Кули - Тьюки с двойной инверсией входных данных. При больших  L число операций пропорционально  L*log2 L. Данная подпрограмма подробно описана в [1, стp.34] под именем  FFT.

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

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

    int ftf1c_c (real *are, real *aim, integer *n, integer *in,
            integer *k, real *p)

   Параметры
         are -
         aim   		вещественные одномерные массивы длины  n, компоненты которых перед началом работы подпрограммы содержат сооответственно действительные и мнимые части элементов преобразуемого комплексного ряда  x. По окончании работы подпрограммы содержат сооответственно действительные и мнимые части элементов преобразованного ряда  y на тех же местах, что и преобразуемый ряд  x;
n - заданная длина массива a (тип: целый);
in - заданный номеp первого элемента преобразуемого ряда в массиве  a (тип: целый);
k - заданный шаг выбора элементов преобразуемого ряда (тип: целый);
p - заданная вещественная переменная, признак преобразования Фурье. При  p > 0. выполняется дискретное преобразование Фурье, при  p < 0. выполняется обратное дискретное преобразование Фурье. 
   Версии
ftf2c_c - вычисление дискретного или обратного дискретного преобразования Фурье комплексного ряда длины, равной степени двух методом быстрого преобразования Фурье (в подпрограмме ftf2c_c преобразуемый ряд задается одним комплексным массивом). 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
  1. 

Длина преобразуемого ряда  l = n / k должна быть целой степенью двух: 

      n / k = 2m ≥ 4 ;     1 ≤ in ≤ k .
  2. 

Если преобразуемый ряд целиком заполняет массив  a, то  in = k = 1.

  3. 

Если вычислялось ДПФ, то на выходе  p = π (= 3.1415...), а если OДПФ, то  p = - π.

  4. 

Если на выходе  p = 0., то элементы ряда  x располагаются в двоично - инверсном порядке, а преобразование Фурье не выполняется.

  5. 

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

  6. 

Заголовок подпрограммы ftf2c_c имеет следующий вид: 

int ftf2c_c(complex *a, integer *n, integer *in, integer *k,
        real *p)
где  a - комплексный одномерный массив длины  n. Перед началом работы подпрограммы содержит элементы преобразуемого ряда  x. По окончании работы подпрограммы содержит элементы преобразованного ряда  y на тех же местах, что и элементы преобразуемого ряда.

Остальные формальные параметры подпрограммы ftf2c_c имеют тот же смысл, что и соответствующие параметры подпрограммы ftf1c_c.

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

1.
int main(void)
{
    /* Local variables */
    extern int ftf1c_c(float *, float *, int *, int *, int *, float *);
    static int i__, k, n;
    static float p;
    static int in;
    static float aim[12], are[12];

    for (i__ = 1; i__ <= 12; ++i__) {
        are[i__ - 1] = (float) (i__ - 1);
/* l1: */
        aim[i__ - 1] = 0.f;
    }
    n = 12;
    in = 2;
    k = 3;
    p = 1.f;

    ftf1c_c(are, aim, &n, &in, &k, &p);

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


Результаты:

      p    =  3.1415

      are  =  (0., 22., 2., 3., - 6., 5., 6., - 6., 8., 9., - 6., 11.)
      aim  =  (0., 0., 0., 0., 6., 0., 0., 0., 0., 0., - 6., 0.), 

то есть преобразование Фурье ряда
     1 + 0*i ,  4 + 0*i ,  7 + 0*i ,  10 + 0*i , 

 расположенного в массивах  are и aim на местах с номерами 2,
   5, 8 и 11 дает ряд 22 + 0*i ,   - 6 + 6*i ,
   - 6 + 0*i , - 6 - 6*i ,  расположенный
   в  массивах  are, aim  на тех же местах. 


2.
int main(void)
{
    /* System generated locals */
    int i__1, i__2;

    /* Local variables */
    extern int ftf2c_c(complex *, int *, int *, int *, float *);
    static complex a[12];
    static int i, k, n;
    static float p;
    static int in;

    for (i = 1; i <= 12; ++i) {
/* L1: */
        i__1 = i - 1;
        i__2 = i - 1;
        a[i__1].r = (float) i__2, a[i__1].i = 0.f;
    }
    n = 12;
    in = 2;
    k = 3;
    p = 1.f;

    ftf2c_c(a, &n, &in, &k, &p);

    for (i = 1; i <= 12; ++i) {
        printf("\n %16.7e %16.7e \n",a[i-1].r, a[i-1].i);
    }
    return 0;
} /* main */


Результаты:

      p  =  3.1415

      a  =  (  0. + 0.*i, 22. + 0.*i,   2. + 0.*i,     3. + 0.*i, 
                - 6. + 6.*i,   5. + 0.*i,   6. + 0.*i,  - 6. + 0.*i, 
                  8. + 0.*i,   9. + 0.*i, - 6. - 6.*i,   11. + 0.*i  )