Fast Fourier Transformation Based on Number Theoretic Transforms

✍ Scribed by Reza Adhami; Robert J. Polge

• Publisher: Elsevier Science
• Year: 1988
• Tongue: English
• Weight: 643 KB
• Volume: 325
• Category: Article
• ISSN: 0016-0032
• DOI: 10.1016/0016-0032(88)90031-2

✦ Synopsis

Many fast algorithms have been proposed for computing the discrete Fourier transformation. Most of them are based on factorization with the goal of reducing the number of multiplications. They usejoating point arithmetic to avoid repetitious scaling and a sizeable wordlength to minimize quantization errors. This paper shows that the DFT of a sequence with prime length, P, can be computed eficiently, for selected P's, using number theoretic transforms. The proposed technique, denoted as FFT/NTT, is illustrated for p = 2M + 1. Advantages include availability offast algorithms for a set ofprime lengths, residue arithmetic with bene$t in speed and hardware costs, parallel implementation with short wordlengths through the use of the Chinese remainder theorem, and exact computation except for scaling and round offfor the input array and the trigonometric sequences.