Exact Convolutions by Number-Theoretic Transforms

Abstract

Because of their importance in every engineering discipline, the calculation of convolutions deserves close study. With the advent of the Fast Fourier Transform it was possible to speed up this calculation substantially -- this despite the fact that the FFT itself involves a large number of trigonometric table look-ups and multiplications. This raised the question as to whether some other transform might be more efficient. In this report the Mersenne and Fermat Transforms are studied in some detail. Both results available in the literature and new results are presented. In addition to Part II, Practical Considerations, and Part III, Theoretical Considerations, a number of Appendices are collected as Part IV and are intended to summarize some basic material needed in the body of the report.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 02, 1975
Accession Number
ADA013395

Entities

People

  • Philip J. Erdelsky

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • Complex Numbers
  • Composite Materials
  • Convolution
  • Discrete Fourier Transforms
  • Engineering
  • Equations
  • Fast Fourier Transforms
  • Information Theory
  • Notation
  • Numbers
  • Prime Numbers
  • Rational Numbers
  • Real Numbers
  • Signal Processing
  • Two Dimensional

Readers

  • Approximation Theory.
  • Computer Programming and Software Development.
  • Systems Analysis and Design