Decomposition on a group and parallel convolution and fast Fourier transform algorithms | SpringerLink
Skip to main content
Springer Nature Link
Log in

Decomposition on a group and parallel convolution and fast Fourier transform algorithms

  • Applications
  • Conference paper
  • First Online:
Parallel Computing Technologies (PaCT 1997)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1277))

Included in the following conference series:

  • 240 Accesses

Abstract

The group-theoretic approach to the decomposition of the basic operations of the digital signal processing (DSP) such as discrete Fourier transform (DFT) and convolution is proposed. The distinctive feature of the approach is its primordial orientation to parallel processing. The recurrent description of the decomposition process producing fast parallel algorithms are effective both for parallel and sequential processing. The main properties of these algorithms are formulated and the description of a vector DFT algorithm is adduced.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Kung H.T., Computing on VLSI, in Evans D.J., ed.: Parallel processing systems, Cambridge University Press, 1982.

    Google Scholar 

  2. Rabiner L.R., Gold B.: Theory and Application of Digital Signal Processing, Prentice-Hall, Englewood C1iffs,N.J.,1975.

    Google Scholar 

  3. McClellan J.H., Rader C.M.: Number Theory in Digital Signal Processing, Prentice-Hall, Englewood Cliffs,N.J.,1979.

    Google Scholar 

  4. Nussbaumer H.J.: Fast Fourier Transform and Convolution Algorithms, Springer-Verlag, Berlin Heidelberg, 1982.

    Google Scholar 

  5. Pease M.C.: An Adaptation of the Fast Fourier Transform for Parallel Processing. J.Assoc. Comput.Mach.15 (1968) 253–264.

    Google Scholar 

  6. Korn D.G., J. Lambiotte,Jr.: Computing the Fast Fourier-Transform on a Vector Computer. Math. Comput. 33 (1979) 977–992.

    Google Scholar 

  7. Petersen W.P.: Vector Fortran for Numerical Problems on CRAY-1. Commun. Assoc. Comput.Mach. 26 (1983) 1008–1021.

    Google Scholar 

  8. Agarwal R.C., Cooley J.W.:Vectorized Mixed Radix Discrete Fourier Transform Algorithms. Proc. of the IEEE. 75 (1987) 1283–1292.

    Google Scholar 

  9. Kung S.Y., Whitehouse H.J. and Kailath T.,eds.: VLSI and Modern Signal Processing, Prentice-Hall, Englewood Cliffs, N.J., 1985.

    Google Scholar 

  10. Klimova O.V.: Developing and Studying Architectural Methods for Parallel Multiprocessor Systems Designed to Compute Convolutions. Ph.D. diss., Inst. of Eng. Sci., Russian Ac. of Sci. (Ural Branch), Sverdlovsk (Ekaterinburg), 1988.

    Google Scholar 

  11. Klimova O.V.: Parallel Architecture of the Arbitrary-Length Convolution Processor with the Use of Rader Number Transforms. Izv. AN Tekhn. Kibernet. (Russia). 2 (1994) 183–191.

    Google Scholar 

  12. Klimova O.V.: The Separating Decomposition of Discrete Fourier Transform and Vectorization of its Calculation. In Malyshkin V. ed., Pact-95, Third Int'l Conference on Parallel Computing Technologies. Proceedings, pages 241–245. Springer-Verlag, Berlin, LNCS 964.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Engineering Science, Ural Branch of the Russian Academy of Science, 91 Pervomayskaya str., 620219, Ekaterinburg, Russia

    Olga V. Klimova

Authors
  1. Olga V. Klimova
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Victor Malyshkin

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Klimova, O.V. (1997). Decomposition on a group and parallel convolution and fast Fourier transform algorithms. In: Malyshkin, V. (eds) Parallel Computing Technologies. PaCT 1997. Lecture Notes in Computer Science, vol 1277. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63371-5_37

Download citation

  • DOI: https://doi.org/10.1007/3-540-63371-5_37

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-63371-6

  • Online ISBN: 978-3-540-69525-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation