Title :
Rader–Brenner Algorithm for Computing New Mersenne Number Transform
Author :
Boussakta, Said ; Hamood, Monir T.
Author_Institution :
Sch. of Electr., Electron. & Comput. Eng., Newcastle Univ., Newcastle upon Tyne, UK
Abstract :
Error-free convolutions and correlations can be efficiently computed using number theoretic transforms. One particular transform, which is known as the new Mersenne number transform (NMNT), can be used for the calculation of long-length convolutions/correlations. In this brief, a new decimation-in-time algorithm for the fast calculation of the NMNT based on the Rader-Brenner approach is proposed. The structure of the NMNT can be further improved by means of the developed algorithm, which involves multiplication by constants that are simpler than vector rotation. In terms of arithmetic operation, the proposed algorithm achieves the lowest number of multiplication among all known butterfly-style algorithms. An example of large integer multiplication is given to prove the validity of the developed algorithm.
Keywords :
number theory; transforms; Mersenne number transform; Rader-Brenner algorithm; butterfly style algorithms; error free convolutions; integer multiplication; number theoretic transforms; vector rotation; Complexity theory; Convolution; Mathematical model; Polynomials; Signal processing algorithms; Transforms; New Mersenne number transform (NMNT); Rader–Brenner algorithm (RBA); number theoretic transforms (NTTs);
Journal_Title :
Circuits and Systems II: Express Briefs, IEEE Transactions on
DOI :
10.1109/TCSII.2011.2158714