Transform-Domain Digital Filtering with Number Theoretic Transforms and Limited Word Lengths

Abstract

While the discrete Fourier transform (DFT) is defined in the field of complex numbers, number theoretic transforms (NTT’s) operate in finite rings and fields. Some of these NIT's have a fast-transform structure similar to that of the fast Fourier transform (FFT) and can be used for fast digital signal processing. Both the computational effort and the signal-to-noise ratio (SNR) performance of transform-domain signal processing with NTT's are investigated in this paper. In particular, the effect of limited word lengths, i.e., b ≤ 16, and long transform lengths on the SNR of NIT filtering is analyzed. For small word lengths and/or moderate to large transform lengths, NTT filtering is shown to achieve a better SNR than FFT filtering with fixed-point arithmetic. Finally, new NTT's with a single- or mixed-radix fast-transform structure are presented. While these NTT's require efficient implementations of modulo arithmetic operations, their transform length is optimum for any given work length b in the range 8 ≤ b ≤16. © 1978 IEEE