• DocumentCode
    2993867
  • Title

    Multiply/Add tradeoffs in length-2nFFT algorithms

  • Author

    Heideman, M. ; Burrus, C. Sidney

  • Author_Institution
    Rice University, Houston, Texas
  • Volume
    10
  • fYear
    1985
  • fDate
    31138
  • Firstpage
    780
  • Lastpage
    783
  • Abstract
    The multiplicative complexity of the length-2ndiscrete Fourier Transform is derived. A constructive approach is followed which describes the set of algorithms that realize the minimum number of multiplications. The operation counts of minimum multiply algorithms are compared to other FFT algorithms. The basic method is extended to derive the multiplicative complexity of length-pnDFFs where p is an odd prime number.
  • Keywords
    Algorithm design and analysis; Arithmetic; Computational complexity; Discrete Fourier transforms; NASA; Polynomials; Signal processing algorithms; Upper bound;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Acoustics, Speech, and Signal Processing, IEEE International Conference on ICASSP '85.
  • Type

    conf

  • DOI
    10.1109/ICASSP.1985.1168331
  • Filename
    1168331
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2993867