Fast Complex Convolution Using Number Theoretic Transforms,

Abstract

It is shown that discrete circular convolution of complex number sequences may be carried out without arithmetic roundoff error using a family of number theoretic transforms defined in a finite ring. In certain cases the arithmetic of this transform may involve only additions, subtractions, and circular bit shifts and may be implemented with an FFT type procedure. As an application it is shown that the discrete Fourier transform may be computed with these transforms.

Document Details

Document Type
Technical Report
Publication Date
Nov 17, 1975
Accession Number
ADA018053

Entities

People

  • Emanuel Vegh
  • Lawrence M. Leibowitz

Organizations

  • United States Naval Research Laboratory

Tags

DTIC Thesaurus Topics

  • Arithmetic
  • Complex Numbers
  • Convolution
  • Discrete Fourier Transforms
  • Mathematics
  • Numbers
  • Sequences

Fields of Study

  • Engineering

Readers

  • Computer Programming and Software Development.
  • Image Processing and Computer Vision.