DocumentCode :
2761835
Title :
Efficient FPGA implementation of FFT based multipliers
Author :
Cheng, Lo Sing ; Miri, Ali ; Yeap, Tet Hin
Author_Institution :
Sch. of Inf. Technol. & Eng., Ottawa Univ., Ont.
fYear :
2005
fDate :
1-4 May 2005
Firstpage :
1300
Lastpage :
1303
Abstract :
Finite field multiplication is one of the most useful arithmetic operations and has applications in many areas such as signal processing, coding theory and cryptography. However, it is also one of the most time consuming operations in both software and hardware, which makes it pertinent to develop a fast and efficient implementation. In this paper, we propose a novel FFT based finite field multiplier to address this problem. The fast Fourier transform (FFT) is the collection of computationally efficient algorithms that perform the discrete Fourier transform (DFT). For our purposes, we will use its efficient computation for polynomial multiplication. The FFT performs polynomial multiplication in O(nlog(n)) time compared to the classical method time of O(n2). The idea of using the FFT for finite field multiplication has been researched extensively, but to our knowledge, this is the first implementation in hardware
Keywords :
fast Fourier transforms; field programmable gate arrays; multiplying circuits; polynomials; FFT; FPGA; classical method time; discrete Fourier transform; fast Fourier transform; finite field multiplier; polynomial multiplication; Application software; Arithmetic; Codes; Cryptography; Discrete Fourier transforms; Field programmable gate arrays; Galois fields; Hardware; Polynomials; Signal processing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Electrical and Computer Engineering, 2005. Canadian Conference on
Conference_Location :
Saskatoon, Sask.
ISSN :
0840-7789
Print_ISBN :
0-7803-8885-2
Type :
conf
DOI :
10.1109/CCECE.2005.1557215
Filename :
1557215
Link To Document :
بازگشت