Scribd Logo
Upload

Welcome to Scribd!

  • 37 views

    Fast Fourier Transform

    Uploaded by

    Anonymous sDiOXHwPPj
    f(i) reverses the bit order of i. For example, the binary representation of 6 is 110. Reversing the bit order gives 011, which is 3 in decimal. So f(6) = 3. This bit-reversal ordering is used to map the input sequence to the outputs of the DFT in order to efficiently compute it using the FFT algorithm.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    Fast Fourier Transform

    Uploaded by

    Anonymous sDiOXHwPPj
    37 views10 pages
    f(i) reverses the bit order of i. For example, the binary representation of 6 is 110. Reversing the bit order gives 011, which is 3 in decimal. So f(6) = 3. This bit-reversal ordering is used to map the input sequence to the outputs of the DFT in order to efficiently compute it using the FFT algorithm.

    Original Description:

    fourier

    Original Title

    Fft

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    f(i) reverses the bit order of i. For example, the binary representation of 6 is 110. Reversing the bit order gives 011, which is 3 in decimal. So f(6) = 3. This bit-reversal ordering is used to map the input sequence to the outputs of the DFT in order to efficiently compute it using the FFT algorithm.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    37 views10 pages

    Fast Fourier Transform

    Uploaded by

    Anonymous sDiOXHwPPj
    f(i) reverses the bit order of i. For example, the binary representation of 6 is 110. Reversing the bit order gives 011, which is 3 in decimal. So f(6) = 3. This bit-reversal ordering is used to map the input sequence to the outputs of the DFT in order to efficiently compute it using the FFT algorithm.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 10

    Fast Fourier Transform

    Definition
    • All Periodic Waves Can be Generated
    by Combining Sin and Cos Waves of
    Different Frequencies
    • Number of Frequencies may not be
    finite
    • Fourier Transform Decomposes a
    Periodic Wave into its Component
    Frequencies
    DFT Definition
    • Sample consists of n points, wave
    amplitude at fixed intervals of time:
    (p0,p1,p2, ..., pn-1) (n is a power of 2)
    • Result is a set of complex numbers
    giving frequency amplitudes for sin and
    cos components
    • Points are computed by polynomial:
    P(x)=p0+p1x+p2x2+ ... +pn-1xn-1
    DFT Definition, continued
    • The complete DFT is given by
    P(1), P(w), P(w2), ... ,P(wn-1)

    • w Must be a Primitive nth Root of Unity

    • wn=1, if 0<i<n then wi  1


    Primitive Roots of Unity
    • wi is an nth root of unity (not primitive)
    • wn/2 = -1
    • if 0jn/2-1 then w(n/2)+j = -wj
    • if n is even and w is a primitive nth root
    of unity, then w2 is a primitive n/2 root of
    unity
    • Example: w = cos(2p/n) + isin(2p/n)
    n 1

    w
    i0
    i
    0
    Divide and Conquer
    • Compute an n-point DFT using one or
    more n/2-point DFTs
    • Need to find Terms involving w2 in following
    polynomial
    • P(w)=p0+p1w+p2w2+p3w3+p4w4+ ... +pn-1wn-
    1

    Here They Are


    Even/Odd Separation
    • P(w)= P1(w)+P2(w)
    • P1(w)=p0+p2w2+p4w4+ ... +pn-2wn-2
    • P1(w)=Pe (w2)=p0+p2w+p4w1+...+pn-2w(n-2)/2
    • P2(w)=p1w+p3w3+p5w5+ ... +pn-1wn-1
    • P2(w)= w P3(w)=p1+p3w2+... +pn-1wn-2
    • P3(w)=Po(w2)= p1+p3w+... +pn-1w(n-2)/2
    • P(w)= Pe(w2)+ wPo(w2)
    • Pe & Po come from n/2 point FFTs
    The Algorithm
    DFFT(P:Array;k,m:Integer):Array;
    begin
    If k=0 Then
    DFFT[0]=P[0];DFFT[1]=P[0];
    Else
    Evens = DFFT(EvenElemOf(P),k-1,2m);
    Odds = DFFT(OddElemOf(P),k-1,2m);
    For i := 0 to 2k-1-1 Do
    x := Odds[j]*wmj
    DFFT[j] := Evens[j] + x
    DFFT[2k-1+j] := Evens[j] - x
    End For
    End If
    end
    Iterative Algorithm
    For i := 0 To n-2 By 2 Do
    T[i] = p[f(i)] + p[f(t+1)];
    T[i+1] := p[f(i)] - p[f(t+1)];
    End For
    m := n/2; n := 2;
    For k := lg n - 2 To 0 By -1 Do
    m := m/2; n := 2*n;
    For i := 0 To (2k-1)*n By n Do
    For j := 0 To (n/2)-1 Do
    x := wmj * T[i+n/2+j];
    T[i+n/2+j] := T[i+j] - x;
    T[i+j] := T[i+j] + x;
    End For
    End For
    End For
    What is f(i)?
    i f(i)

    000 000 - 000 000 - 000 000


    001 010 - 010 100 - 100 100
    010 100 - 100 010 - 010 010
    011 110 - 110 110 - 110 110
    100 001 - 001 001 - 001 001
    101 011 - 011 101 - 101 101
    110 101 - 101 011 - 011 011
    111 111 - 111 111 - 111 111

    You might also like