TELKOMNIKA Telecommunication Computing Electronics and Control
Unified algorithms for generalized new Mersenne number transforms

TELKOMNIKA Telecommunication Computing Electronics and Control
Unified algorithms for generalized new Mersenne number transforms

Decimation-in-frequency
Fast transform algorithms
New Mersenne number
transforms
Number theoretic transforms

The generalized new Mersenne number transforms (GNMNTs) have proved to be significant number theoretic transforms (NTTs) used to calculate convolutions and correlations accurately. In this paper, by applying the principles of the decimation-in-frequency (DIF) approach with appropriate relations in finite field modulo Mersenne primes, two new fast algorithms for computing odd NMNT (ONMNT) and odd-squared NMNT (O2NMNT) are introduced. Moreover, by formulating a unified index mapping scheme for data sequence, a close relationship between the structures of the developed algorithms has been established. As a result, it has been shown that only a single universal butterfly structure is adequate to execute both algorithms. Consequently, a unified implementation platform can be used to compute the ONMNT as well as the O2NMNT. The validity of the development has been checked via an example for fast calculations of different types of
convolutions, using both the GNMNTs and the proposed algorithms.

Lujain S. Abdulla, Abdulmutalib A-Wahab Hussein, Mounir Taha Hamood

http://telkomnika.uad.ac.id

Aug 15, 2023

peri irawan

pdf

english

text