High speed parallel architecture for cyclic convolution based on FNT

摘要

This paper presents a high speed parallel architecture for cyclic convolution based on Fermat Number Transform (FNT) in the diminished-1 number system. A code conversion method without addition (CCWA) and a butterfly operation method without addition (BOWA) are proposed to perform the FNT and its inverse (IFNT) except their final stages in the convolution. The pointwise multiplication in the convolution is accomplished by modulo 2~n+1 partial product multipliers (MPPM) and output partial products which are inputs to the IFNT. Thus modulo 2~n+1 carry propagation additions are avoided in the FNT and the IFNT except their final stages and the modulo 2~n+1 multiplier. The execution delay of the parallel architecture is reduced evidently due to the decrease of modulo 2~n+1 carry-propagation addition. Compared with the existing cyclic convolution architecture, the proposed one has better throughput performance and involves less hardware complexity. Synthesis results using 130nm CMOS technology demonstrate the superiority of the proposed architecture over the reported solution.