Computer Science – Information Theory
Scientific paper
2011-08-21
Computer Science
Information Theory
6 pages, 4 figures
Scientific paper
Cyclotomic fast Fourier transforms (CFFTs) are efficient implementations of discrete Fourier transforms over finite fields, which have widespread applications in cryptography and error control codes. They are of great interest because of their low multiplicative and overall complexities. However, their advantages are shown by inspection in the literature, and there is no asymptotic computational complexity analysis for CFFTs. Their high additive complexity also incurs difficulties in hardware implementations. In this paper, we derive the bounds for the multiplicative and additive complexities of CFFTs, respectively. Our results confirm that CFFTs have the smallest multiplicative complexities among all known algorithms while their additive complexities render them asymptotically suboptimal. However, CFFTs remain valuable as they have the smallest overall complexities for most practical lengths. Our additive complexity analysis also leads to a structured addition network, which not only has low complexity but also is suitable for hardware implementations.
Wu Xuebin
Yan Zhiyuan
No associations
LandOfFree
Computational Complexity of Cyclotomic Fast Fourier Transforms over Characteristic-2 Fields does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computational Complexity of Cyclotomic Fast Fourier Transforms over Characteristic-2 Fields, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computational Complexity of Cyclotomic Fast Fourier Transforms over Characteristic-2 Fields will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-537658