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.
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;
Conference_Titel :
Electrical and Computer Engineering, 2005. Canadian Conference on
Conference_Location :
Saskatoon, Sask.
Print_ISBN :
0-7803-8885-2
DOI :
10.1109/CCECE.2005.1557215