Signal processing with number theoretic transforms and limited word lengths

Number Theoretic Transforms (NTT\´s), unlike the Discrete Fourier Transform (DFT), are defined in finite rings and fields rather than in the field of complex numbers. Some NTT\´s have a transform structure like the Fast Fourier Transform (FFT) and can be used for fast digital signal processing. The computational effort and the signal-to-noise ratio (SNR) performance of linear filtering in finite rings and fields are investigated. In particular, the effect of limited word lengths, i.e., , and long transform lengths on the SNR is analyzed. It is shown that for small word lengths and/or moderate to large transform lengths NTT filtering achieves a better SNR than FFT filtering with fixed-point arithmetic. Some new NTT\´s with a single- or mixed-radix fast transform structure are presented. While these NTT\´s may require special modulo arithmetic they achieve optimum transform length for any given word length b in the range .