RTL fast convolution using the mersenne number transform

Abstract

VHDL is a versatile high level language for the specification and simulation of hardware components. Here a functional VHDL model is presented for performing fast convolution based on Mersenne's number theoretic transform. For filtering a rather long input sequence xn() we can decomposed it into a number of short segments, each of which can be processed individually. The output yn()then becomes a combination of partial convolutions. The superposition principle for linear operators is used here. Each partial convolution can be solved using the Discrete Fourier Transform (DFT) implementing a fast FFT (Fast Fourier Transform) algorithm. This DFT approach is the most popular. In this paper we use the Mersenne Number Transform (MNT) as an alternative for the DFT in the framework of a register transfer level (RTL) implementation of the filter operation. Even when the MNT does not have a fast algorithm it can be see that RTL in the natural level of abstraction for the implementation of the MNT. This work is conceived as part of an academic exercise in the use of VHDL for modeling a DSP algorithm all the way from the mathematical specification to the circuit implementation.