In the paper it is shown that discrete Fourier transform can be computed using only 0(NlogN) operations even if N is prime, N is the transform size. A fast algorithm working for any prime N is presented, which worst case computational complexity is below 32N log/sub 2/(N) arithmetical operations, which can be compared to less than 4Nlog/sub 2/(N) operations for the best existing FFT for N being power of number 2. It is shown, however that by introducing few modifications the worst case computational complexity of the algorithm can be reduced to circa 16Nlog/sub 2/(N) arithmetical operations. In this way an interesting theoretical result is obtained that computational complexities of the DFT for 'most' and 'least' convenient N values do not differ by more than factor 4.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Universal fast Fourier transform algorithm for prime data vector sizes


    Contributors:


    Publication date :

    2003-01-01


    Size :

    290269 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Universal Fast Fourier Transform Algorithm for Prime Data Vector Sizes

    Stasinski, R. / IEEE / EURASIP | British Library Conference Proceedings | 2003


    The Fast Fourier Transform

    Sakai, H. | British Library Online Contents | 1994



    The Fast Fourier Transform (FFT)

    Springer Verlag | 2008


    Fast Fourier Transform for Hexagonal Aggregates

    Zapata, J. L. / Ritter, G. X. | British Library Online Contents | 2000