Bit-serial, VLSI architecture for the implementation of maximum-length number-theoretic transforms using mixed basis representation

Fermat and Mersenne number-theoretic transforms (NTTs) are relatively easy to implement, but they are unsuitable for many DSP applications, due to small block length over wordlength. The authors present VLSI design techniques appropriate for a wider range of NTTs, including maximum-length NTTs, and outline a systolic architecture exploiting block-length factorization to decompose the architecture into submodules, themselves systolic NTTs. The design avoids the explicit implementation of modular addition, accumulation, and multiplication by using systolic basis converters, which inherently perform the tasks described. The implementation of a maximum-length 60pt NTT is described as an example. It uses binary to ternary basis conversion to perform all addition and multiplication, and ternary basis compression to perform accumulation.<>