Transform-domain digital filtering with number theoretic transforms and limited word lengths

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., , 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 range .