Transform-domain digital filtering with number theoretic transforms and limited word lengths
Pierre Chevillat · IEEE Transactions on Acoustics Speech and Signal Processing · 1978
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 NTT'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 \leq 16, and long transform lengths on the SNR of NTT 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 range8 \leq b \leq 16.