|
Текст подпрограммы и версий ftf1c_p.zip , ftf2c_p.zip |
Тексты тестовых примеров tftf1c_p.zip , tftf2c_p.zip |
Вычисление дискретного или обратного дискретного преобразования Фурье комплексного ряда длины, равной степени двух, методом быстрого преобразования Фурье.
Элементы 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ДПФ).
Для вычислений используется метод быстрого преобразования Фурье. Подпрограмма реализует алгоритм Кули - Тьюки с расширенной (Extended) инверсией входных данных. При больших L число операций пропорционально L*log2 L. Данная подпрограмма подробно описана в [1, стp.34] под именем FFT.
| 1. | В.А.Морозов, Н.Н.Кирсанова, А.Ф.Сысоев, Комплекс алгоритмов быстрого преобразования Фурье дискретных рядов. Сб. "Численный анализ на ФОРТРАНе", вып. 15, Изд. МГУ, 1976. |
procedure FTF1C(var ARE :Array of Real; var AIM :Array of Real;
N :Integer; IN_ :Integer; K :Integer; var P :Real);
Параметры
|
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 = 2M ≥ 4 ; 1 ≤ IN ≤ K . | |
| 2. |
Если преобразуемый ряд целиком заполняет массив A, то IN_ := K := 1. | |
| 3. |
Если вычислялось ДПФ, то на выходе P = π (= 3.1415...), а если OДПФ, то P = - π. | |
| 4. |
Если на выходе P = 0., то элементы ряда X располагаются в двоично - инверсном порядке, а преобразование Фурье не выполняется. | |
| 5. |
Значения элементов массива A, не используемых при вычислении коэффициентов Фурье, при работе подпрограммы сохраняются. | |
| 6. |
Заголовок подпрограммы FTF2C имеет следующий вид: procedure FTF2C(var A :Array of Complex; N :Integer; IN_ :Integer;
K :Integer; var P :Real);
,где A - комплексный одномерный массив длины N. Перед началом работы подпрограммы содержит элементы преобразуемого ряда X. По окончании работы подпрограммы содержит элементы преобразованного ряда Y на тех же местах, что и элементы преобразуемого ряда. Остальные формальные параметры подпрограммы FTF2C имеют тот же смысл, что и соответствующие параметры подпрограммы FTF1C. |
1.Unit TFTF1C_p; interface uses SysUtils, Math, { Delphi } Lstruct, Lfunc, UtRes_p, FTF1C_p; function TFTF1C: String; implementation function TFTF1C: String; var I,N,IN_,K,_i :Integer; P :Real; ARE :Array [0..11] of Real; AIM :Array [0..11] of Real; label _1; beGIN Result := ''; { результат функции } for I:=1 to 12 do begin ARE[I-1] := I-1; _1: AIM[I-1] := 0.0; end; N := 12; IN_ := 2; K := 3; P := 1.0; FTF1C(ARE,AIM,N,IN_,K,P); Result := Result + #$0D#$0A; for _i:=0 to 11 do begin Result := Result + Format('%16.7f ',[ARE[_i]]); if ( ((_i+1) mod 4)=0 ) then Result := Result + #$0D#$0A; end; Result := Result + #$0D#$0A; Result := Result + #$0D#$0A; for _i:=0 to 11 do begin Result := Result + Format('%16.7f ',[AIM[_i]]); if ( ((_i+1) mod 4)=0 ) then Result := Result + #$0D#$0A; end; Result := Result + #$0D#$0A; Result := Result + Format(' %16.7f ',[P]) + #$0D#$0A; UtRes('TFTF1C',Result); { вывод результатов в файл TFTF1C.res } exit; end; end. Результаты: 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. Unit tftf2c_p; interface uses SysUtils, Math, { Delphi } Lstruct, Lfunc, UtRes_p, FTF2C_p; function tftf2c: String; implementation function tftf2c: String; var I,N,IN_,K,_i :Integer; P :Real; A :Array [0..11] of Complex; label _1; begin Result := ''; { результат функции } for I:=1 to 12 do begin _1: A[I-1] := Cmplx(I-1,0.0); end; N := 12; IN_ := 2; K := 3; P := 1.0; FTF2C(A,N,IN_,K,P); Result := Result + Format(' %16.7f ',[P]) + #$0D#$0A; Result := Result + #$0D#$0A; for _i:=0 to 11 do begin Result := Result + Format('%16.7f %16.7f ',[A[_i].re,A[_i].im]); if ( ((_i+1) mod 2)=0 ) then Result := Result + #$0D#$0A; end; Result := Result + #$0D#$0A; UtRes('tftf2c',Result); { вывод результатов в файл tftf2c.res } exit; end; end. Результаты: 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 )