High Speed Parallel Butterfly Architecture for Computing Circular Convolution Based on FNT Using Modulo 2n+1partial Product Multiplier

Abstract

This paper presents high speed butterfly architecture for circular convolution based on FNT using partial product multipliers. FNT is ideally suited to digital computation requiring the order of N log N additions, subtractions and bit shifts, but no multiplications. In addition to being efficient, the FNT implementation is exact with no round off errors. Binary arithmetic permits the exact computation of FNT. This technique involves arithmetic in a binary code corresponding to the simplest one of a set of code translations from the normal binary representation of each integer in the ring of integer. In the first stage normal binary numbers are converted into their diminished-1 representation using code conversion (CC). Then butterfly operation (BO) is carried out to perform FNT and IFNT where the point wise multiplication is performed using modulo 2n+1 partial product multipliers. Thus modulo 2n+1 additions are avoided in the final stages of FNT and IFNT and hence execution delay is reduced compared to circular convolution done with FFT and DFT. This architecture has better throughput and involves less hardware complexity.