Skip to main content
SpringerLink
Log in

A methodology for designing, modifying, and implementing Fourier transform algorithms on various architectures

  • Published:
Circuits, Systems and Signal Processing Aims and scope Submit manuscript

Abstract

Fourier transform algorithms are described using tensor (Kronecker) products and an associated class of permutations. Algebraic properties of tensor products and the related permutations are used to derive variants of the Cooley-Tukey fast Fourier transform algorithm. These algorithms can be implemented by translating tensor products and permutations to programming constructs. An implementation can be matched to a specific computer architecture by selecting the appropriate variant. This methodology is carried out for the Cray X-MP and the AT&T DSP32.

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

Access this article

Log in via an institution

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

References

  1. CAL Assembler Version 1 Reference Manual. Cray Research, Inc., Mendota Heights, Minnesota, March 1985. SR-0000.

  2. CRAY X-MP Series Mainframe Reference Manual. Cray Research, Inc., Mendota Heights, Minnesota, November 1982. HR-0032.

  3. WE DSP32 Digital Signal Processor—Information Manual. AT&T Technologies, Inc., 1986.

  4. R. C. Agarwal and J. W. Cooley. Vectorized mixed radix discrete Fourier transform algorithms. January 1987. Preprint.

  5. W. T. Cochran, J. W. Cooley, D. L. Favin, H. D. Helms, R. A. Kaenal, W. W. Lang, G. C. Mailing Jr., D. E. Nelson, C. M. Rader, and P. D. Welch. What is the fast Fourier transform?IEEE Trans. Audio Electroacoust.,15(2): 45–55, June 1967.

    Google Scholar 

  6. J. W. Cooley and J. W. Tukey. An algorithm for the machine calculation of complex Fourier series.Maths. Comp.,19(90): 297–301, April 1965.

    Google Scholar 

  7. J. Granata and M. Rofheart. The tensor product as a tool for designing efficient Fourier transform algorithms for digital signal processing. 1988. Unpublished notes.

  8. J. R. Johnson. Some Issues in Designing Algebraic Algorithms for the CRAY X-MP. Technical Report 88-02, Center for Mathematical Computation, University of Delaware, January 1988. Master's Thesis.

  9. J. R. Johnson. Some issues in designing algebraic algorithms for the CRAY X-MP. InComputer Algebra and Parallelism (J. Della Dora and J. Fitch, eds.), pp. 179–195, Academic Press, New York, 1989.

    Google Scholar 

  10. R. W. Johnson, C. Lu, and R. Tolimieri. Fast Fourier transform algorithms for the sizeN, a product of distinct primes and their implementation on VAX architecture. 1989. Unpublished notes.

  11. D. G. Korn and J. J. Lambiotte, Jr. Computing the fast Fourier transform on a vector computer.Math. comp.,33(147): 977–992, July 1979.

    Google Scholar 

  12. D. H. Lawrie. Access and alignment of data in an array processor.IEEE Trans. Comput.,24(2); 1145–1155, December 1975.

    Google Scholar 

  13. M. C. Pease. An adaptation of the fast Fourier transform for parallel processing.J. Assoc. Compt. Mach. 15(2): 252–264, April 1968.

    Google Scholar 

  14. D. Rodriguez. On Tensor Product Formulations of Additive Fast Fourier Transform Algorithms and Their Implementations. Ph.D. thesis, E.E. Department, City College of New York, City University of New York, 1987.

  15. H. S. Stone. Parallel processing with the perfect shuffle.IEEE Trans. Comput.,20(2): 153–161, February 1971.

    Google Scholar 

  16. P. N. Swartztrauber. FFT algorithms for vector computers.Parallel Comput.,1: 45–63, 1984.

    Google Scholar 

  17. P. N. Swartztrauber. Multiprocessor FFTs.Parallel Comput.,5(1 & 2): 197–210, July 1987.

    Google Scholar 

  18. C. Temperton. A note on prime factor FFT algorithms.J. Comput. Phys.,52(1): 198–204, October 1983.

    Google Scholar 

  19. C. Temperton. Self-sorting mixed-radix fast Fourier transforms.J. Comput. Phys.,52(1): 1–23, October 1983.

    Google Scholar 

  20. C. Temperton. Implementation of a self-sorting in-place prime factor FFT algorithm.J. Comput. Phys.,58(3): 283–299, May 1985.

    Google Scholar 

  21. C. Temperton. Implementation of a prime factor FFT algorithm on the CRAY-1.Parallel Comput., 99–108, 1988.

Download references

Author information

Authors and Affiliations

  1. Department of Computer and Information Science, The Ohio State University, 43210, Columbus, Ohio, USA

    J. R. Johnson

  2. Department of Computer Science, The Graduate School and University Center of the City, University of New York, 10036, New York, New York, USA

    R. W. Johnson

  3. Department of Electrical Engineering, The City College of New York, 10031, New York, New York, USA

    D. Rodriguez & R. Tolimieri

Authors
  1. J. R. Johnson
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R. W. Johnson
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. D. Rodriguez
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. R. Tolimieri
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was performed at the Center for Large Scale Computation, Suite 400, 25 West 43rd Street, New York, New York 10036, USA, and was supported by a grant from DARPA/ACMP.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Johnson, J.R., Johnson, R.W., Rodriguez, D. et al. A methodology for designing, modifying, and implementing Fourier transform algorithms on various architectures. Circuits Systems and Signal Process 9, 449–500 (1990). https://doi.org/10.1007/BF01189337

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01189337

Keywords

Search

Navigation