Efficient number theoretic transforms for convolutions using ROM arrays

Hardware realisations are proposed of number theoretic transforms (NTTs) that are based on the transformation of their fundamental relationships into recursive filter forms with single integer poles. Furthermore, use is made of read-only memory (ROM) to effect the multiplications by the root of unity, α. Suitable NTTs are then suggested for the fast computation of cyclic convolutions using multi-dimensional and multi-modular techniques. The required ROM size in the proposed realisations is small and the control of data flow is simple and straightforward. This new class of number theoretic transforms can relax considerably the normal sequence length and wordlength constraints for the NTT.Department of Electronic and Information Engineerin