iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s00607-007-0222-6
A new matrix approach to real FFTs and convolutions of length 2 k | Computing Skip to main content
Springer Nature Link
Log in

A new matrix approach to real FFTs and convolutions of length 2k

  • Published:
Computing Aims and scope Submit manuscript

Abstract

A new matrix, scaled odd tail, SOT, is introduced. This new matrix is used to derive real and complex FFT algorithms for lengths n = 2k. A compromise is reached between Fourier transform and polynomial transform methods for computing the action of cyclic convolutions. Both of these methods lead to arithmetic operation counts that are better than previously published results. A minor improvement is also demonstrated that enables us to compute the actions of Fermat prime order FFTs in fewer additions than previously available algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Bergland, G. D., Dolan, M. T.: In: IEEE Acoust., Speech, Signal Processing Society, Programs for Digital Signal Processing. New York: IEEE Press 1979.

  • G. Bi Y. Zeng (2004) Transforms and fast algorithms for signal analysis and representations Birkhäuser Boston Occurrence Handle1095.94004

    MATH  Google Scholar 

  • L. Davis (1979) Circulant matrices Wiley New York Occurrence Handle0418.15017

    MATH  Google Scholar 

  • P. Duhamel H. Holliman (1984) ArticleTitleSplit-radix FFT algorithm Electr. Lett. 20 14–16 Occurrence Handle10.1049/el:19840012

    Article  Google Scholar 

  • P. Duhamel M. Vetterli (1990) ArticleTitleFast Fourier transforms: a tutorial review and a state of the art Signal Process. 19 259–299 Occurrence Handle0704.65106 Occurrence Handle10.1016/0165-1684(90)90158-U Occurrence Handle1048328

    Article  MATH  MathSciNet  Google Scholar 

  • M. Frigo S. G. Johnson (2005) ArticleTitleThe design and implementation of FFTW3 Proc. IEEE 93 IssueID2 216–231 Occurrence Handle10.1109/JPROC.2004.840301

    Article  Google Scholar 

  • N. C. Hu O. K. Ersoy (1991) ArticleTitleFast computation of real discrete Fourier transform for any number of data points IEEE Trans. Circuits Sys. 38 IssueID11 1280–1292 Occurrence Handle0751.65073 Occurrence Handle10.1109/31.99157

    Article  MATH  Google Scholar 

  • Johnson, H. W., Burrus, C. S.: The design of optimal DFT algorithms using dynamic programming. IEEE Trans. Acoust. Speech Signal Process. ASSP-31, 378–387 (1983).

    Google Scholar 

  • Johnson, S. G.: private communication.

  • C. Lu J. Cooley R. Tolimieri (1993) ArticleTitleFFT algorithms for prime transform sizes and their implementation on VAX, IBM3090VF, and IBM RS/6000 IEEE Trans. Acoust. Speech Signal Process. 41 638–648 Occurrence Handle0773.65095

    MATH  Google Scholar 

  • H. Murakami (1994) ArticleTitleReal-valued decimation-in-time and decimation-in-frequency algorithms IEEE Trans. Circuits Sys. 41 IssueID12 808–816 Occurrence Handle0840.65144 Occurrence Handle10.1109/82.338622

    Article  MATH  Google Scholar 

  • H. J. Nussbaumer (1982) Fast Fourier transform and convolution algorithms, 2nd corrected and updated edition Springer Berlin Heidelberg

    Google Scholar 

  • C. M. Rader (1968) ArticleTitleDiscrete Fourier transforms when the number of data samples is prime Proc. IEEE 56 1107–1108 Occurrence Handle10.1109/PROC.1968.6477

    Article  Google Scholar 

  • F. Scheid (1989) Schaum's outline series of theory and problems of numerical analysis EditionNumber2 McGraw-Hill New York 184–197

    Google Scholar 

  • I. Selesnick C. Burrus (1996) ArticleTitleAutomatic generation of prime length FFT programs IEEE Trans. Acoust. Speech Signal Process. 44 14–24

    Google Scholar 

  • Sorenson, H., Jones, D., Heideman, M., Burrus, C.: Real-valued fast Fourier transform algorithms. IEEE Trans. Acoust. Speech Signal Process. ASSP-35, 849–863 (1987).

    Google Scholar 

  • Swarztrauber, P.: FFTPACK, version 4, April 1985. http://gams.nist.gov/serve.cgi/package/FFTPACK/, 2006.

  • C. Temperton (1983) ArticleTitleFast mixed-radix real Fourier transforms J. Comput. Phys. 52 340–350 Occurrence Handle0513.65094 Occurrence Handle10.1016/0021-9991(83)90034-7 Occurrence Handle725599

    Article  MATH  MathSciNet  Google Scholar 

  • C. Temperton (1988) ArticleTitleA new set of minimum-add small-n rotated DFT modules J. Comput. Phys. 75 190–198 Occurrence Handle0637.65146 Occurrence Handle10.1016/0021-9991(88)90106-4 Occurrence Handle940812

    Article  MATH  MathSciNet  Google Scholar 

  • R. Tolimieri M. An C. Lu (1997) Algorithms for discrete Fourier transform and convolution EditionNumber2 Springer New York Occurrence Handle0894.65076

    MATH  Google Scholar 

  • Van Buskirk, J., Lundy, T.: The new FFT web page: http://www.cuttlefisharts.com/newfft/, 2004.

  • I. Verbauwhede (2002) What makes a programmable DSP processor special? V. Oklobdzija (Eds) The Computer Engineering Handbook CRC Press Boca Raton, FL

    Google Scholar 

  • M. Vetterli P. Duhamel (1989) ArticleTitleSplit-radix algorithms for length-pm DFT's IEEE Trans. Acoust. Speech Signal Process. 37 57–64 Occurrence Handle0669.65096 Occurrence Handle10.1109/29.17500 Occurrence Handle973039

    Article  MATH  MathSciNet  Google Scholar 

  • M. Vetterli H. J. Nussbaumer (1984) ArticleTitleSimple FFT and DCT algorithms with reduced number of operations Signal Process. 6 267–278 Occurrence Handle10.1016/0165-1684(84)90059-8 Occurrence Handle760430

    Article  MathSciNet  Google Scholar 

  • J. S. Walker (1988) Fourier analysis Oxford University Press New York Occurrence Handle0669.42001

    MATH  Google Scholar 

  • R. Yavne (1968) ArticleTitleAn economical method for calculating the discrete Fourier transform AFIPS Proc. 33 115–125

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Virtuallaboratory.net, 3500 Allison Street, Wheat Ridge, CO, 80033, USA

    T. Lundy

  2. One Room Schoolhouse of Physics, Wheat Ridge, CO, 80033, USA

    J. Van Buskirk

Authors
  1. T. Lundy
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. Van Buskirk
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to T. Lundy.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lundy, T., Van Buskirk, J. A new matrix approach to real FFTs and convolutions of length 2k . Computing 80, 23–45 (2007). https://doi.org/10.1007/s00607-007-0222-6

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00607-007-0222-6

AMS Subject Classifications

Keywords

Search

Navigation