A fast realization of new Mersenne number transformation and its applications

摘要

The new Mersenne number transform (NMNT) can be realized by the fast Fourier transform (FFT) with power-of-two length, which results in great flexibility in real-world fixed-point computations, such as the convolution-based signal processing in the embedded device. Yet the FFT realization exists the truncation errors and in order to further reduce the computations, this paper puts forward a novel realization structure for the NMNT, where the Walsh-Hadamard transform (WHT) is employed to accelerate the NMNT computation. Moreover, we also propose the refined computing structure using the matrix decomposition and multiple constant multiplication (MCM), and then all multiplications can be replaced by the shift-addition operations without precision loss. Besides, the use of lookup table (LUT) to reduce the complexity is also discussed in our study. A typical convolution application is tested by computer simulations, while the result demonstrates that the proposed scheme produces precise computing results with reduced complexity.