invers discreet fourier transform

Hej,

fft er en algoritme til hurtig beregning af den diskrete fourier transformation.

En fourier transformation er næsten sin egen inverse - mener at huske at
fouriertransformations i 4. potens er lig identitet-operatoren, dvs.

f*f*f*f = I, hvoraf den inverse fourier transformation = f*f*f

Så har du et program der beregner fft, skal du bare bruge det 3 gange. Mener dog også at den inverse fft har en beskrevet direkte algortime.

Mvh Torben.

PS: Dette er ud fra hukommelsen, bør nok lige checkes op med en lærebog i fouriertransformation og fft.

Har du en formel for IDFT?

Hej,

for en række af tal g(k) hvor k=0,1,2,3,...,N-1 er den diskrete Fourier transformation DFT af g(k) en ny række af tal G(k) hvor

G(k) = g(0) + g(1)*w^k + g(2)*w^(2k) + ... + g(N-1)*w^((N-1)*k)

w = exp(2*pi*i/N)
pi = 3.15159265...
i = det komplekse tal hvor i*i = -1
w^p = w*w*...*w ialt p gange.

Så bemærk at både g(k) og G(k) er komplekse tal.

Den inverse transformation IDFT på tallene G(k) er den række af tal g(k) man får ved

g(k) = 1/N* (G(0) + G(1)/w^k + G(2)/w^(2k) + ... + G(N-1)/w^((N-1)*k))

Så må du se om du kan få noget ud af det :-).

Hvordan formlerne/algoritmerne ser ud for Fast Fourier Transform (FFT) er jeg ikke ekspert i (FFT er en hurtig måde for vise tal N at beregne DFT på en computer).

Skal man finde den inverse til FFT mener jeg stadig det nemmeste er at sige IFFT = "FFT anvendt 3 gange".

Mvh Torben.

Jeg beklager at jeg ikke har reageret på jeres kommentarer tidligere - jeg har haft meget travlt, og i mellemtiden har jeg selv fundet svaret, hvorfor jeg helt har glemt at jeg havde oprettet et spørgsmål her.
I skal have tak for jeres hjælp, omend svaret ligger et stykke fra det jeg skulle bruge.
Såfremt nogen skulle have interesse i at vide hvordan idft fungerer kan jeg lige kort vise det her:
idet dft (fft) anvendes til at finde frekvensspektret i et samplet signal (eks. lyd) går man fra en række samples der beskriver signalets amplituder til en række complekse tal der beskriver frekvensindholdet af signalet.
Idet en dft bruger samples værdier og spytter complekse tal ud kan jeg ikke lige se hvorvidt det skulle være muligt at sætte complekse tal ind og få samplesværdier ud (jævnfør Torbens kommentar) - selvom den inverse dft ligner dft'en. Men koden for idft er her, hvis andre nu skulle stå og få brug for den

void iDFT::invDFT ()
{   
    for (long f = 0; f < buffersize; f++)
    {
        sigreal[f]=0;
        for (long k = 0; k < buffersize; k++)
            {
                double arg = (2.0 * pi * k * f )/ buffersize;
                if (f == 0 || k == 0)
                {
                    sigreal[f] +=realarray[k]*cos(arg);
                }
                else
                {
                    sigreal[f] +=realarray[k]*cos(arg) - imagarray[k]*sin(arg);
                }
            }
    }

}

buffersize er lig med antallet af data i dine arrays (det skal måske her nævnes at det føromtalte komplekse tal ligger i to arrays - et indholdene de reelle værdier, og et indholdende de imaginære værdier)

Spørgsmålet lukkes...

Hej,

selvom dine samples er reele (ikke komplekse) eller komplekse tal kan en DFT hhv. en IDFT begge godt ende op i reele værdier. Det er der ikke noget specielt i.

Ovenstående C++ metode invDFT er faktisk en implementation af den formel jeg tidligere angav for IDFT under forudsætning af at dine tids-samples oprindeligt var reele og at realarray[k],imagarray[k] er de tilsvarende komplekse koefficienter for de Fourier transformerede tids-samples.
sigreal er så de oprindelige reele tids-samples.

Men jeg har to kommentarer til iDFT::invDFT,
1) Den algortime du anvender er ikke FFT (invers) men DFT (invers), som du også navngiver metoden. FFT og invers FFT er algoritmer, som giver samme result, men er optimalt hurtige at beregne for visse værdier af buffersize.
2) Din if-statement med f==0 || k==0 er unødvendig da sin(0)=0, og ønsker du en hastighedsoptimering bør du gemme cos(arg) og sin(arg) i nogle arrays.