Fast Fourier Transforms (6x9 Version) by C. Sidney Burrus - HTML preview

[204] Steven G. Johnson and J. D. Joannopoulos. Block-iterative

frequency-domain methods for maxwell’s equations in a

planewave basis. Optics Express, 8(3):1738211;190, 2001.

[205] Douglas L. Jones.

The DFT, FFT, and Practi-

cal Spectral Analysis.

Connexions, February 2007.

http://cnx.org/content/col10281/1.2/.

[206] Douglas L. Jones.

The DFT, FFT, and Practi-

cal Spectral Analysis.

Connexions, February 2007.

http://cnx.org/content/col10281/1.2/.

[207] Alan H. Karp. Bit reversal on uniprocessors. SIAM Rev.,

38(1):18211;26, 1996.

[208] Donald E. Knuth. The Art of Computer Programming, Vol.

2, Seminumerical Algorithms. Addison-Wesley, Reading,

MA, third edition, 1997.

[209] Donald E. Knuth. The Art of Computer Programming, Vol.

2, Seminumerical Algorithms. Addison-Wesley, Reading,

MA, third edition, 1997.

[210] Donald E. Knuth. Fundamental Algorithms, volume 1 of

The Art of Computer Programming. Addison-Wesley, 3nd

edition, 1997.

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

BIBLIOGRAPHY

325

[211] John F. Kohne. A quick fourier transform algorithm. Tech-

nical report TR-1723, Naval Electronics Laboratory Center,

July 1980.

[212] D. P. Kolba and T. W. Parks.

A prime factor fft algo-

rithm using high speed convolution. IEEE Trans. on ASSP,

25:2818211;294, August 1977. also in.

[213] D. P. Kolba and T. W. Parks.

A prime factor fft algo-

rithm using high speed convolution. IEEE Trans. on ASSP,

25:2818211;294, August 1977. also in.

[214] D. P. Kolba and T. W. Parks.

A prime factor fft algo-

rithm using high speed convolution. IEEE Trans. on ASSP,

25:2818211;294, August 1977. also in.

[215] H. Krishna, B. Krishna, K.-Y. Lin, and J.-D. Sun. Computa-

tional Number Theory and Digital Signal Processing. CRC

Press, Boca Raton, FL, 1994.

[216] Z. Li, H. V. Sorensen, and C. S. Burrus. Fft and convolution

algorithms for dsp microprocessors. In Proceedings of the

IEEE International Conference on Acoustics, Speech, and

Signal Processing, page 2848211;292, Tokyo, Japan, April

1986.

[217] J. S. Lim and A. V. Oppenheim. Advanced Topics in Signal

Processing. Prentice-Hall, Englewood Cliffs, NJ, 1988.

[218] J. S. Lim and A. V. Oppenheim. Advanced Topics in Signal

Processing. Prentice-Hall, Englewood Cliffs, NJ, 1988.

[219] Jae S. Lim and A. V. Oppenheim. Advanced Topics in Signal

Processing, chapter 4. Prentice-Hall, 1988.

[220] C. M. Loeffler and C. S. Burrus. Equivalence of block filter

representations. In Proceedings of the 1981 IEEE Interna-

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

326

BIBLIOGRAPHY

tional Symposium on Circuits and Systems, pages 546–550,

Chicago, IL, April 1981.

[221] C. M. Loeffler and C. S. Burrus.

Periodically

time8211;varying bandwidth compressor. In Proceedings of

the IEEE International Symposium on Circuits and Systems,

page 6638211;665, Rome, Italy, May 1982.

[222] C. M. Loeffler and C. S. Burrus. Optimal design of pe-

riodically time varying and multirate digital filters. IEEE

Transactions on Acoustics, Speech, and Signal Processing,

ASSP-32(5):991–924, October 1984.

[223] Chao Lu, James W. Cooley, and Richard Tolimieri. Fft algo-

rithms for prime transform sizes and their implementations

on vax, ibm3090vf, and ibm rs/6000. IEEE Transactions on

Signal Processing, 41(2):6388211;648, February 1993.

[224] D. P-K. Lun and W-C. Siu. An analysis for the realization

of an in-place and in-order prime factor algorithm. IEEE

Transactions on Signal Processing, 41(7):23628211;2370,

July 1993.

[225] T. Lundy and J. Van Buskirk.

A new matrix approach

to real ffts and convolutions of length.

Computing,

80(1):238211;45, 2007.

[226] J. D. Markel. Fft pruning. IEEE Trans on Audio and Elec-

troacoustics, 19(4):3058211;311, June 1971.

[227] J. B. Martens. Recursive cyclotomic factorization 8211; a

new algorithm for calculating the discrete fourier transform.

IEEE Trans. on ASSP, 32(4):7508211;762, August 1984.

[228] J. B. Martens. Recursive cyclotomic factorization 8211; a

new algorithm for calculating the discrete fourier transform.

IEEE Trans. on ASSP, 32(4):7508211;762, August 1984.

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

BIBLIOGRAPHY

327

[229] J. B. Martens. Recursive cyclotomic factorization 8211; a

new algorithm for calculating the discrete fourier transform.

IEEE Trans. on ASSP, 32(4):7508211;762, August 1984.

[230] J. B. Martens.

Recursive cyclotomic factorization8212;a

new algorithm for calculating the discrete fourier transform.

IEEE Trans. Acoust., Speech, Signal Processing, 32(4):750–

761, 1984.

[231] D. Maslen and D. Rockmore.

Generalized ffts 8211; a

survey of some recent results. In Proceedings of IMACS

Workshop in Groups and Computation, volume 28, page

1828211;238, 1995.

[232] J. H. McClellan and C. M. Rader. Number Theory in Digi-

tal Signal Processing. Prentice-Hall, Englewood Cliffs, NJ,

1979.

[233] J. H. McClellan and C. M. Rader. Number Theory in Digi-

tal Signal Processing. Prentice-Hall, Englewood Cliffs, NJ,

1979.

[234] J. H. McClellan and C. M. Rader. Number Theory in Digi-

tal Signal Processing. Prentice-Hall, Englewood Cliffs, NJ,

1979.

[235] J. H. McClellan and C. M. Rader. Number Theory in Digi-

tal Signal Processing. Prentice-Hall, Englewood Cliffs, NJ,

1979.

[236] J. H. McClellan and C. M. Rader. Number Theory in Digi-

tal Signal Processing. Prentice-Hall, Englewood Cliffs, NJ,

1979.

[237] J. H. McClellan and C. M. Rader. Number Theory in Digi-

tal Signal Processing. Prentice-Hall, Englewood Cliffs, NJ,

1979.

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

328

BIBLIOGRAPHY

[238] J. H. McClellan and C. M. Rader. Number Theory in Digital

Signal Processing. Prentice-Hall, Inc., Englewood Cliffs,

NJ, 1979.

[239] J. H. McClellan and C. M. Rader. Number Theory in Digi-

tal Signal Processing. Prentice-Hall, Englewood Cliffs, NJ,

1979.

[240] J. W. Meek and A. S. Veletsos. Fast convolution for recur-

sive digital filters. IEEE Transactions on Audio and Elec-

troacoustics, AU-20:938211;94, March 1972.

[241] R. Meyer, R. Reng, and K. Schwarz. Convolution algo-

rithms on dsp processors. In Proceedings of the ICASSP-91,

page 21938211;2196, Toronto, Canada, May 1991.

[242] R. Meyer and K. Schwarz. Fft implementation on dsp-chips,

Sept. 18 1990. preprint.

[243] R. Meyer, K. Schwarz, and H. W. Schuessler. Fft implemen-

tation on dsp-chips 8212; theory and practice. In Proceed-

ings of the ICASSP-90, page 15038211;1506, Albuquerque,

NM, April 1990.

[244] R. A. Meyer and C. S. Burrus.

A unified analy-

sis of multirate and periodically time varying digital fil-

ters.

IEEE Transactions on Circuits and Systems, CAS-

22(3):1628211;168, March 1975.

[245] R. A. Meyer and C. S. Burrus. Design and implementation

of multirate digital filters. IEEE Transactions on Acoustics,

Speech, and Signal Processing, ASSP-24(1):538211;58,

February 1976.

[246] S. K. Mitra and R. Gransekaran. A note on block implemen-

tation of iir digital filters. IEEE Transactions on Circuit and

Systems, CAS-24(7), July 1977.

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

BIBLIOGRAPHY

329

[247] S. K. Mitra and R. Gransekaran.

Block implementation

of recursive digital filters 8211; new structures and prop-

erties. IEEE Transactions on Circuit and Systems, CAS-

25(4):2008211;207, April 1978.

[248] Jacques Morgenstern. Note on a lower bound of the linear

complexity of the fast fourier transform. 20(2):305–306,

1973.

[249] L. R. Morris. Digital Signal Processing Software. DSPSW,

Inc., Toronto, Canada, 1982, 1983.

[250] L. R. Morris. Digital Signal Processing Software. DSPSW,

Inc., Toronto, Canada, 1982, 1983.

[251] L. R. Morris. Digital Signal Processing Software. DSPSW,

Inc., Toronto, Canada, 1982, 1983.

[252] Douglas G. Myers. Digital Signal Processing, Efficient Con-

volution and Fourier Transform Techniques. Prentice-Hall,

Sydney, Australia, 1990.

[253] Douglas G. Myers. Digital Signal Processing, Efficient Con-

volution and Fourier Transform Techniques. Prentice-Hall,

Sydney, Australia, 1990.

[254] Douglas G. Myers. Digital Signal Processing, Efficient Con-

volution and Fourier Transform Techniques. Prentice-Hall,

Sydney, Australia, 1990.

[255] Kenji Nakayama.

An improved fast fourier trans-

form algorithm using mixed frequency and time decima-

tions.

IEEE Trans. Acoust., Speech, Signal Processing,

36(2):2908211;292, 1988.

[256] P. J. Nicholson.

Algebraic theory of finite fourier

transforms.

Journal of Computer and System Sciences,

5:5248211;547, 1971.

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

330

BIBLIOGRAPHY

[257] P. J. Nicholson.

Algebraic theory of finite fourier

transforms.

Journal of Computer and System Sciences,

5(2):5248211;547, February 1971.

[258] Ivan Niven and H. S. Zuckerman. An Introduction to the

Theory of Numbers. John Wiley & Sons, New York, fourth

edition, 1980.

[259] Ivan Niven and H. S. Zuckerman. An Introduction to the

Theory of Numbers. John Wiley & Sons, New York, fourth

edition, 1980.

[260] Ivan Niven and H. S. Zuckerman. An Introduction to the

Theory of Numbers. John Wiley & Sons, New York, fourth

edition, 1980.

[261] H. J. Nussbaumer. Fast Fourier Transform and Convolution

Algorithms. Springer-Verlag, Heidelberg, Germany, second

edition, 1981, 1982.

[262] H. J. Nussbaumer. Fast Fourier Transform and Convolution

Algorithms. Springer-Verlag, Heidelberg, Germany, second

edition, 1981, 1982.

[263] H. J. Nussbaumer. Fast Fourier Transform and Convolution

Algorithms. Springer-Verlag, Heidelberg, Germany, second

edition, 1981, 1982.

[264] H. J. Nussbaumer. Fast Fourier Transform and Convolution

Algorithms. Springer-Verlag, Heidelberg, Germany, second

edition, 1981, 1982.

[265] H. J. Nussbaumer. Fast Fourier Transform and Convolution

Algorithms. Springer-Verlag, Heidelberg, Germany, second

edition, 1981, 1982.

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

BIBLIOGRAPHY

331

[266] H. J. Nussbaumer. Fast Fourier Transform and Convolution

Algorithms. Springer-Verlag, Heidelberg, Germany, second

edition, 1981, 1982.

[267] H. J. Nussbaumer. Fast Fourier Transform and Convolution

Algorithms. Springer-Verlag, Heidelberg, Germany, second

edition, 1981, 1982.

[268] H. J. Nussbaumer. Fast Fourier Transformation and Convo-

lution Algorithms. Springer, 2nd edition, 1982.

[269] A. V. Oppenheim and R. W. Schafer. Discrete-Time Signal

Processing. Prentice-Hall, Englewood Cliffs, NJ, 1989.

[270] A. V. Oppenheim and R. W. Schafer. Discrete-Time Signal

Processing. Prentice-Hall, Englewood Cliffs, NJ, 1989.

[271] A. V. Oppenheim and R. W. Schafer. Discrete-Time Signal

Processing. Prentice-Hall, Englewood Cliffs, NJ, second

edition, 1999. Earlier editions in 1975 and 1989.

[272] A. V. Oppenheim and R. W. Schafer. Discrete-Time Signal

Processing. Prentice-Hall, Englewood Cliffs, NJ, second

edition, 1999. Earlier editions in 1975 and 1989.

[273] A. V. Oppenheim and R. W. Schafer. Discrete-Time Signal

Processing. Prentice-Hall, Englewood Cliffs, NJ, second

edition, 1999. Earlier editions in 1975 and 1989.

[274] A. V. Oppenheim and R. W. Schafer. Discrete-Time Signal

Processing. Prentice-Hall, Englewood Cliffs, NJ, second

edition, 1999. Earlier editions in 1975 and 1989.

[275] A. V. Oppenheim and R. W. Schafer. Discrete-Time Signal

Processing. Prentice-Hall, Englewood Cliffs, NJ, second

edition, 1999. Earlier editions in 1975 and 1989.

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

332

BIBLIOGRAPHY

[276] A. V. Oppenheim and R. W. Schafer. Discrete-Time Signal

Processing. Prentice-Hall, Englewood Cliffs, NJ, second

edition, 1999. Earlier editions in 1975 and 1989.

[277] A. V. Oppenheim, R. W. Schafer, and J. R. Buck. Discrete-

Time Signal Processing. Prentice Hall, 2nd edition, 1999.

[278] A. V. Oppenheim, R. W. Schafer, and J. R. Buck. Discrete-

Time Signal Processing. Prentice-Hall, Upper Saddle River,

NJ, 2nd edition, 1999.

[279] Oystein Ore. Number Theory and Its History. McGraw-Hill,

New York, 1948.

[280] Victor Ya. Pan. The trade-off between the additive complex-

ity and the asyncronicity of linear and bilinear algorithms.

Information Proc. Lett., 22:118211;14, 1986.

[281] Christos H. Papadimitriou. Optimality of the fast fourier

transform. 26(1):95–102, 1979.

[282] T. W. Parks and C. S. Burrus. Digital Filter Design. John

Wiley & Sons, New York, 1987.

[283] T. W. Parks and C. S. Burrus. Digital Filter Design. John

Wiley & Sons, New York, 1987.

[284] T. W. Parsons. A winograd-fourier transform algorithm for

real-valued data. IEEE Trans. on ASSP, 27:398–402, August

1979.

[285] F. Perez and T. Takaoka. A prime factor fft algorithm im-

plementation using a program generation technique. IEEE

Transactions on Acoustics, Speech and Signal Processing,

35:12218211;1223, August 1987.

[286] I. Pitas and C. S. Burrus. Time and error analysis of digital

convolution by rectangular transforms. Signal Processing,

5(2):1538211;162, March 1983.

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

BIBLIOGRAPHY

333

[287] I. Pitas and C. S. Burrus. Time and error analysis of digital

convolution by rectangular transforms. Signal Processing,

5(2):1538211;162, March 1983.

[288] J. M. Pollard. The fast fourier transform in a finite field.

Mathematics of Computation, 25(114):3658211;374, April

1971.

[289] Miodrag Popovi263; and Dragutin 352;evi263;.

A new

look at the comparison of the fast hartley and fourier

transforms.

IEEE Transactions on Signal Processing,

42(8):21788211;2182, August 1994.

[290] W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vet-

terling. Numerical Recipes in C: The Art of Scientific Com-

puting. Cambridge Univ. Press, New York, NY, 2nd edition,

1992.

[291] M. Pschel and J. M. F. Moura. Algebraic signal processing

theory. available at http://arxiv.org/abs/cs.IT/0612077.

[292] M. Pschel and J. M. F. Moura. The algebraic approach to the

discrete cosine and sine transforms and their fast algorithms.

SIAM Journal of Computing, 32(5):12808211;1316, 2003.

[293] M. Pschel and J. M. F. Moura. Algebraic signal processing

theory: 1-d space. IEEE Transactions on Signal Processing,

56(8):3586–3599, 2008.

[294] M. Pschel and J. M. F. Moura.

Algebraic signal pro-

cessing theory:

Cooley-tukey type algorithms for dcts

and dsts.

IEEE Transactions on Signal Processing,

56(4):1502–1521, 2008.

a longer version is available at

http://arxiv.org/abs/cs.IT/0702025.

[295] M. Pschel and J. M. F. Moura. Algebraic signal processing

theory: Foundation and 1-d time. IEEE Transactions on

Signal Processing, 56(8):3572–3585, 2008.

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

334

BIBLIOGRAPHY

[296] Markus Pschel, Jos[U+FFFD] F. Moura, Jeremy R. John-

son, David Padua, Manuela M. Veloso, Bryan W. Singer,

Jianxin Xiong, Franz Franchetti, Aca Ga269;i263;, Yevgen

Voronenko, Kang Chen, Robert W. Johnson, and Nicholas

Rizzolo. Spiral: Code generation for dsp transforms. Proc.

IEEE, 93(2):232–275, 2005.

[297] Z. Qian, C. Lu, M. An, and R. Tolimieri.

Self-

sorting in-place fft algorithm with minimum working

space.

IEEE Trans. Acoust., Speech, Signal Processing,

42(10):28358211;2836, 1994.

[298] L. R. Rabiner and B. Gold. Theory and Application of Digi-

tal Signal Processing. Prentice-Hall, Englewood Cliffs, NJ,

1975.

[299] L. R. Rabiner and B. Gold. Theory and Application of Digi-

tal Signal Processing. Prentice-Hall, Englewood Cliffs, NJ,

1975.

[300] L. R. Rabiner and B. Gold. Theory and Application of Digi-

tal Signal Processing. Prentice-Hall, Englewood Cliffs, NJ,

1975.

[301] L. R. Rabiner and C. M. Rader, editors. Digital Signal Pro-

cessing, selected reprints. IEEE Press, New York, 1972.

[302] L. R. Rabiner and C. M. Rader, editors. Digital Signal Pro-

cessing, selected reprints. IEEE Press, New York, 1972.

[303] L. R. Rabiner and C. M. Rader, editors. Digital Signal Pro-

cessing, selected reprints. IEEE Press, New York, 1972.

[304] Lawrence Rabiner.

The chirp z-transform algorithm: a

lesson in serendipity. IEEE Signal Processing Magazine,

24:1188211;119, March 2004.

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

BIBLIOGRAPHY

335

[305] Lawrence R. Rabiner, Ronald W. Schafer, and Charles M.

Rader. The chirp -transform algorithm. IEEE Trans. Audio

Electroacoustics, 17(2):868211;92, 1969.

[306] L.R. Rabiner, R.W. Schafer, and C.M. Rader. The chirp

z-transform algorithm. IEEE Transactions on Audio Elec-

troacoustics, AU-17:868211;92, June 1969.

[307] L.R. Rabiner, R.W. Schafer, and C.M. Rader. The chirp

z-transform algorithm. IEEE Transactions on Audio Elec-

troacoustics, AU-17:868211;92, June 1969.

[308] C. M. Rader. Discrete fourier transforms when the num-

ber of data samples is prime. Proceedings of the IEEE,

56:11078211;1108, June 1968.

[309] C. M. Rader. Discrete fourier transforms when the number

of data samples is prime. Proc. IEEE, 56:11078211;1108,

June 1968.

[310] C. M. Rader and N. M. Brenner. A new principle for fast

fourier transformation.

IEEE Transactions on Acoustics,

Speech, and Signal Processing, ASSP-24(3):264–266, June

1976.

[311] Charles M. Rader.

Discrete convolution via mersenne

transforms.

IEEE

Transactions

on

Computers,

21(12):12698211;1273, December 1972.

[312] Charles M. Rader. Number theoretic convolution. In IEEE

Signal Processing Workshop, Arden House, Harriman, NY,

January 1972.

[313] Charles M. Rader and N. M. Brenner. A new principle for

fast fourier transformation. IEEE Trans. Acoust., Speech,

Signal Processing, 24:264–265, 1976.

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

336

BIBLIOGRAPHY

[314] K. R. Rao and P. Yip.

Discrete Cosine Transform: Al-

gorithms, Advantages, Applications. Academic Press, San

Diego, CA, 1990.

[315] J. M. Rius and R. De Porrata-D[U+FFFD]. New fft bit-

reversal algorithm. IEEE Transactions on Signal Process-

ing, 43(4):9918211;994, April 1995.

[316] Christian Roche. A split8211;radix partial input/output fast

fourier transform algorithm. IEEE Transactions on Signal

Processing, 40(5):12738211;1276, May 1992.

[317] D. Rockmore. Some applications of generalized fft’s. In

Proceedings of DIMACS Workshop in Groups and Compu-

tation, volume 28, page 3298211;370, 1995.

[318] J. J. Rodr[U+FFFD]ez. An improved fft digit8211;reversal

algorithm. IEEE Transactions on Acoustics, Speech, and

Signal Processing, 37(8):12988211;1300, August 1989.

[319] J.H. Rothweiler. Implementation of the in-order prime fac-

tor fft algorithm.

IEEE TRANS. ON ASSP, 30:105–107,

February 1982.

[320] J.H. Rothweiler. Implementation of the in-order prime fac-

tor fft algorithm.

IEEE TRANS. ON ASSP, 30:105–107,

February 1982.

[321] Petr Rsel. Timing of some bit reversal algorithms. Signal

Processing, 18(4):4258211;433, December 1989.

[322] Ali Saidi. Decimation-in-time-frequency fft algorithm. In

Proc. IEEE Int’l Conf. Acoustics, Speech, and Signal Pro-

cessing, volume 3, page 4538211;456, 1994.

[323] Ali Saidi.

Decimation-in-time-frequency fft algorithm.

In Proceedings of the IEEE International Conference on

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

BIBLIOGRAPHY

337

Acoustics, Speech, and Signal Processing, volume 3, page

III:4538211;456, IEEE ICASSP-94, Adelaide, Australia,

April 198211;22 1994.

[324] Ali Saidi.

Decimation-in-time-frequency fft algorithm,

1996. manuscript.

[325] G. Sande. Fast fourier transform - a gobally complex algo-

rithm with locally real implementations. Proc. 4th Annual

Princeton Conference on Information Sciences and Systems,

pages 136–142, March 1970.

[326] James C. Schatzman. Accuracy of the discrete fourier trans-

form and the fast fourier transform. SIAM J. Scientific Com-

puting, 17(5):11508211;1166, 1996.

[327] James C. Schatzman. Index mapping for the fast fourier

transform.

IEEE Transactions on Signal Processing,

44(3):7178211;719, March 1996.

[328] Manfred R. Schroeder. Number Theory in Science and Com-

minication. Springer8211;Verlag, Berlin, second edition,

1984, 1986.

[329] I. W. Selesnick and C. S. Burrus. Automating the design of

prime length fft programs. In Proceedings of the IEEE In-

ternational Symposium on Circuits and Systems, volume 1,

page 1338211;136, ISCAS-92, San Diego, CA, May 1992.

[330] I. W. Selesnick and C. S. Burrus. Automating the design of

prime length fft programs. In Proceedings of the IEEE In-

ternational Symposium on Circuits and Systems, volume 1,

page 1338211;136, ISCAS-92, San Diego, CA, May 1992.

[331] I. W. Selesnick and C. S. Burrus. Multidimensional map-

ping techniques for convolution.

In Proceedings of the

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

338

BIBLIOGRAPHY