Привет всем!

Может это не по MFC вопрос конечно, но так как я пишу в основном под ним, то и спрашиваю здесь.
В общем, нужен исходник, реализующий быстрое преобразование Фурье.
Встречал кто такое?
Можно в принципе и на других языках, не на С.

Буду оч. признателен.

val

V>Может это не по MFC вопрос конечно, но так как я пишу в основном под ним, то и спрашиваю здесь.
V>В общем, нужен исходник, реализующий быстрое преобразование Фурье.
V>Встречал кто такое?
V>Можно в принципе и на других языках, не на С.

Например так

// нерекурсивный алгоритм с прореживанием по частоте
void CYourCoolClass::Fft(complex a[], int m, int ind)
    {
    int n = pow2(m), i;

    ASSERT(n == BUFSIZE);
    complex v, w;
    int step = n;
    for(i = m; i > 0; i--)
        {
        step >>= 1;

        cexp(&v, ind*step);
        w = complex(1, 0);
        for(int j = 0; j < step; j++)
            {
            for(int k = j; k < n; k += step<<1)
                bfl(a[k], a[k+step], w);
            w *= v;
            }
        }

    for(int j = i = 0; i < n-1; i++)
        {
        if(i < j)
            {
            complex t;
            t = a[i];
            a[i] = a[j];
            a[j] = t;
            }
        int k = n/2;
        while(k <= j)
            {
            j -= k;
            k /=2;
            }
        j += k;
        }
    }

double cexp(complex* c, int n)
    {
    __asm
        {
        fldpi
        fild    n
        fdivp   st(1), st(0)
        fsincos
        mov     ebx, c
        fstp    qword ptr [ebx]
        fstp    qword ptr [ebx+8]
        }
    }


void CYourCoolClass::bfl(complex& a1, complex& a2, complex& w)
    {
    complex t = a1 - a2;
    a1 += a2;
    a2 = w * t;
    }

Или так (медленнее, но понятнее)

// рекурсивный вариант БПФ
void CYourCoolClass::fft(complex a[], int num, int ind)
    {
    if(num == 2)
        {
        complex tmp = a[0] - a[1];
        a[0] += a[1];
        a[1] = tmp;
        return;
        }

    int step = num>>1;
    complex    w, v;
    cexp(&v, ind*step);
    w = complex(1,0);
    for(int k = 0; k < step; k++)
        {
        int l = k+step;
        complex tmp = a[k] - a[l];
        a[k] += a[l];
        a[l] = w * tmp;
        w *= v;
        }

    fft(a, step, ind);
    fft(a+step, step, ind);
    }

Здравствуйте, valxb, Вы писали:

V>Привет всем!

V>Может это не по MFC вопрос конечно, но так как я пишу в основном под ним, то и спрашиваю здесь.
V>В общем, нужен исходник, реализующий быстрое преобразование Фурье.
V>Встречал кто такое?
V>Можно в принципе и на других языках, не на С.

V>Буду оч. признателен.

V>val

Тебе какое преобразование нужно: дискретно-косинусное или по "бабочке"?

Здравствуйте, valxb, Вы писали:

V>Может это не по MFC вопрос конечно, но так как я пишу в основном под ним, то и спрашиваю здесь.
V>В общем, нужен исходник, реализующий быстрое преобразование Фурье.
V>Встречал кто такое?
V>Можно в принципе и на других языках, не на С.

Есть исходник на VB ,надеюсь что на С переделать проблем не будет.
Также есть и C-шный,но долго искать.Если понадобиться,то скажи.

Это тип данных, в котором хранятся отсчеты кривой:
 
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

Удачи.

Здравствуйте, izi, Вы писали:


izi>Есть исходник на VB ,надеюсь что на С переделать проблем не будет.
izi>Также есть и C-шный,но долго искать.Если понадобиться,то скажи.

Надо.

izi>>Есть исходник на VB ,надеюсь что на С переделать проблем не будет.
izi>>Также есть и C-шный,но долго искать.Если понадобиться,то скажи.

А>Надо.

А этот

Автор: SWW
Дата: 22.11.03

чем не нравится?

Здравствуйте, valxb, Вы писали:


V>В общем, нужен исходник, реализующий быстрое преобразование Фурье.
V>Встречал кто такое?


посмотри http://prog2004.nm.ru/soft/fft.zip