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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Universal fast Fourier transform algorithm for prime data vector sizes


    Beteiligte:
    Stasinski, R. (Autor:in)


    Erscheinungsdatum :

    01.01.2003


    Format / Umfang :

    290269 byte




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    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