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

Текст подпрограммы и версий ( Фортран ) ftf1c.zip , ftf2c.zip	Тексты тестовых примеров ( Фортран ) tftf1c.zip , tftf2c.zip
Текст подпрограммы и версий ( Си ) ftf1c_c.zip , ftf2c_c.zip	Тексты тестовых примеров ( Си ) tftf1c_c.zip , tftf2c_c.zip
Текст подпрограммы и версий ( Паскаль ) ftf1c_p.zip , ftf2c_p.zip	Тексты тестовых примеров ( Паскаль ) tftf1c_p.zip , tftf2c_p.zip

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

Назначение

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

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

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

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

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

                   _L-1             
        Y_r  =   ∑   X_m*W^{m r}  ,      r = 0, 1, ..., L-1  ,
                  ^m=0

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

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

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

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

    SUBROUTINE  FTF1C (ARE, AIM, N, IN, K, P)

   Параметры

ARE - AIM	вещественные одномерные массивы длины N, компоненты которых перед началом работы подпрограммы содержат сооответственно действительные и мнимые части элементов преобразуемого комплексного ряда X. По окончании работы подпрограммы содержат сооответственно действительные и мнимые части элементов преобразованного ряда Y на тех же местах, что и преобразуемый ряд X;
N -	заданная длина массива A (тип: целый);
IN -	заданный номеp первого элемента преобразуемого ряда в массиве A (тип: целый);
K -	заданный шаг выбора элементов преобразуемого ряда (тип: целый);
P -	заданная вещественная переменная, признак преобразования Фурье. При P > 0. выполняется дискретное преобразование Фурье, при P < 0. выполняется обратное дискретное преобразование Фурье.

   Версии

FTF2C -

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

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

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

	1.	Длина преобразуемого ряда L = N / K должна быть целой степенью двух: N / K = 2^M ≥ 4 ; 1 ≤ IN ≤ K .
	2.	Если преобразуемый ряд целиком заполняет массив A, то IN = K = 1.
	3.	Если вычислялось ДПФ, то на выходе P = π (= 3.1415...), а если OДПФ, то P = - π.
	4.	Если на выходе P = 0., то элементы ряда X располагаются в двоично - инверсном порядке, а преобразование Фурье не выполняется.
	5.	Значения элементов массива A, не используемых при вычислении коэффициентов Фурье, при работе подпрограммы сохраняются.
	6.	Подпрограмма FTF1C позволяет выполнить преобразование ряда, заданного одним комплексным массивом A. B этом случае, например, для ряда длины 128 подпрограмма используется следующим образом: COMPLEX A(128) REAL B(256) EQUIVALENCE (A(1), B(1)) CALL FTF1C (B(1), B(2), 256, 1, 2, P)
	7.	Заголовок подпрограммы FTF2C имеет следующий вид: SUBROUTINE FTF2C (A, N, IN, K, P), где A - комплексный одномерный массив длины N. Перед началом работы подпрограммы содержит элементы преобразуемого ряда X. По окончании работы подпрограммы содержит элементы преобразованного ряда Y на тех же местах, что и элементы преобразуемого ряда. Остальные формальные параметры подпрограммы FTF2C имеют тот же смысл, что и соответствующие параметры подпрограммы FTF1C.

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

1. 
      REAL  ARE(12), AIM(12)
      DO 1  I = 1, 12
      ARE(I) = I - 1
   1 AIM(I) = 0.
      N = 12
      IN = 2
      K = 3
      P = 1.
      CALL  FTF1C (ARE, AIM, N, IN, K, P)

Результаты:

      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.
      COMPLEX  A(12)
      DO 1  I = 1, 12
   1 A(I) = I - 1
      N = 12
      IN = 2
      K = 3
      P = 1.
      CALL  FTF2C (A, N, IN, K, P)

Результаты:

      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  )