Radix-4 decimation-in-frequency algorithm for the new Mersenne number transform

摘要

The development of efficient algorithms for fast calculation of discrete transforms has led to a wide spread use of these transforms in a large number of applications. Consequently, fast algorithms for the new Mersenne number transform (NMNT) need to be developed to make it suitable for efficient and fast implementation of error-free convolutions/correlations and related applications. In this paper the radix-4 decimation-in-frequency algorithm is developed for fast calculation of the 1-D NMNT. The mathematical development of this algorithm is presented, its arithmetic complexity is analyzed and the numbers of multiplications and additions are calculated. An example for the calculation of the auto-correlation using the 1-D NMNT and the developed algorithm is given.