https://en.wikipedia.org/wiki/Discrete_ ... _transform
Here is a BASIC:
http://www.analog.com/media/en/technica ... ok_Ch8.pdf
http://rsdn.ru/forum/mfc/452905.1
Code: Select all
Это тип данных, в котором хранятся отсчеты кривой:
Type complex
Re As Double
Im As Double
End Type
Перед вызовом функции нужно заполнить массив А() числами. Причем A.Re()=величина сигнала, а A.Im=0
Потом вызываем FFT(). Она возвращает результат в том же массиве A()
Пользоваться так:
int A(255),i;
A(i).Re=sin(2*PI*i/255); // какая-то кривая
A(i).Im=0; // все это для всех 256 точек
FFT(256,&A); /* именно 256, а не 255 */
Ниже идет текст подпрограммы быстрого преобр. Фурье на бейсике.
Sub FFT(n As Integer, A() As complex) 'кол-во точек, действит., мнимые
Dim j, i, N2, N1, D1, D2, K, M, l, l1, l2, U1, U2, W1, W2, I1, t1, t2, U3
N2 = n / 2: N1 = n - 1: j = 1
M = Fix(Log(n) / Log(2) + 0.1)
For i = 1 To N1 'перестановка
If i < j Then
D1 = A(j).Re: A(j).Re = A(i).Re: A(i).Re = D1
D2 = A(j).Im: A(j).Im = A(i).Im: A(i).Im = D2
End If
K = N2
While (K < j)
j = j - K: K = K / 2
Wend
j = j + K
Next i
'FFT
For l = 1 To M
l1 = 2 ^ l
l2 = l1 / 2
U1 = 1: U2 = 0
W1 = Cos(PI / l2): W2 = -Sin(PI / l2)
For j = 1 To l2
For i = j To n Step l1
I1 = i + l2
t1 = A(I1).Re * U1 - A(I1).Im * U2: t2 = A(I1).Im * U1 + A(I1).Re * U2
A(I1).Re = A(i).Re - t1: A(I1).Im = A(i).Im - t2
A(i).Re = A(i).Re + t1: A(i).Im = A(i).Im + t2
Next i
U3 = U1: U1 = U1 * W1 - U2 * W2: U2 = U2 * W1 + U3 * W2
Next j
Next l
End Sub
