Accession Number:

ADA018053

Title:

Fast Complex Convolution Using Number Theoretic Transforms,

Descriptive Note:

Corporate Author:

NAVAL RESEARCH LAB WASHINGTON D C

Personal Author(s):

Report Date:

1975-11-17

Pagination or Media Count:

17.0

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.

Subject Categories:

  • Cybernetics
  • Non-Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE