基于FPGA的FFT处理器的设计
|
摘要
数字信号处理是信息科学中近几十年来发展最为迅速的学科之一。目前,数字信号处理已经广泛应用于通信、雷达、声纳、语音与图像处理等领域。而离散傅立叶变换(DFT)作为数字信号处理中的基本变换,发挥着重要作用。但是由于离散傅立叶变换(DFT)的运算量太大,在提出之后的一段时间内并没有在实际工程中得到应用,直到快速傅立叶变换(FFT)算法的提出,减少了当N很大时的DFT运算量,才使得DFT在实际工程中得到具体的应用,这也进一步推动了数字信号处理技术的发展。FFT算法从出现到现在已经有四十多年的历史,算法理论已经趋于成熟,具体实现方法也不断的更新。在面向高速、大容量数据流的FFT实时处理时,可以通过数据并行处理或者采用多级流水线结构来实现。
本文分析了离散傅立叶变换及其快速计算方法FFT。对实际中常用的四种用来实现FFT处理器的硬件电路结构进行了介绍,分析了各自的特点。根据算法的特点和硬件结构实现的难易,选择了按时间抽取法中的基-2 FFT算法和流水线工作方式的硬件结构来设计FFT处理器,这样结构在一定程度上提高了FFT处理器的处理速度,而且设计中采用IEEE单精度规格化浮点数的数据形式进行计算提高了计算的精度。选用XILINX公司的Virtex II系列FPGA芯片中的XC2V8000,在ISE 7.1设计平台中使用Verilog HDL硬件描述语言设计流水线工作方式的FFT处理器,计算数据长度为1024点。最后使用MATLAB计算软件对设计的FFT处理器进行了测试仿真,并对FFT处理器运算结果和MATLAB中FFT计算的理论值进行了对比,计算误差。仿真结果表明其计算结果达到了单精度浮点数的要求,运算速度可以满足实时信号处理的要求。
Digital Signal Processing is one of the subjects expanding rapidly in the field of information science during the past several decades. At present, it has applied extensively in many subjects such as communications, radar, sonar, speech and image processing etc. Discrete Fourier Transform (DFT) plays a very important role in Digital Signal Processing as the basic calculation. But it was not widely used in actual project because of its tremendous amount of computing. Until the arithmetic of Fast Fourier Transform was presented which reduces the calculation quantity when N is a little great, the DFT arithmetic is widely used in actual project. It also further promotes the Digital Signal Processing technology development. It has been more than forty years since FFT arithmetic firstly presented, the theory of FFT arithmetic is much mature today, and the method of how to implement has been updated too. The real-time computation of FFT with high-speed and large capacity of data flow can be implemented by parallel data processing or multi level pipeline processing.
This article has a detailed analysis of Discrete Fourier Transform and its rapid calculation method Fast Fourier Transform -- FFT. I introduce four hardware structures and analyze the characteristic of each hardware structure which were common used to implement FFT processor. According to the algorithm and the difficulty to implement it in hardware, I choose Decimation-In-Timer radix 2 FFT algorithm and pipeline hardware structure which can improve the processing speed to design the FFT processor on the FPGA chip XC2V8000 of Virtex II made by XILINX . And the data form in the calculation is IEEE single-precision floating-point standardized form which can increase the accuracy of the calculation. I use Verilog HDL hardware description language to design the FFT processor which works in pipeline form in design platform ISE 7.1, and the points in calculation is 1024.Finaly I simulate the design in MATLAB software and compare the results of the FFT processor with the academic results calculated in MATLAB and calculate the errors. The simulation indicates that the result of calculation can reach equivalent precision and the operation speed of FFT can satisfy the request of commonly real— time signal processing.
本文分析了离散傅立叶变换及其快速计算方法FFT。对实际中常用的四种用来实现FFT处理器的硬件电路结构进行了介绍,分析了各自的特点。根据算法的特点和硬件结构实现的难易,选择了按时间抽取法中的基-2 FFT算法和流水线工作方式的硬件结构来设计FFT处理器,这样结构在一定程度上提高了FFT处理器的处理速度,而且设计中采用IEEE单精度规格化浮点数的数据形式进行计算提高了计算的精度。选用XILINX公司的Virtex II系列FPGA芯片中的XC2V8000,在ISE 7.1设计平台中使用Verilog HDL硬件描述语言设计流水线工作方式的FFT处理器,计算数据长度为1024点。最后使用MATLAB计算软件对设计的FFT处理器进行了测试仿真,并对FFT处理器运算结果和MATLAB中FFT计算的理论值进行了对比,计算误差。仿真结果表明其计算结果达到了单精度浮点数的要求,运算速度可以满足实时信号处理的要求。
Digital Signal Processing is one of the subjects expanding rapidly in the field of information science during the past several decades. At present, it has applied extensively in many subjects such as communications, radar, sonar, speech and image processing etc. Discrete Fourier Transform (DFT) plays a very important role in Digital Signal Processing as the basic calculation. But it was not widely used in actual project because of its tremendous amount of computing. Until the arithmetic of Fast Fourier Transform was presented which reduces the calculation quantity when N is a little great, the DFT arithmetic is widely used in actual project. It also further promotes the Digital Signal Processing technology development. It has been more than forty years since FFT arithmetic firstly presented, the theory of FFT arithmetic is much mature today, and the method of how to implement has been updated too. The real-time computation of FFT with high-speed and large capacity of data flow can be implemented by parallel data processing or multi level pipeline processing.
This article has a detailed analysis of Discrete Fourier Transform and its rapid calculation method Fast Fourier Transform -- FFT. I introduce four hardware structures and analyze the characteristic of each hardware structure which were common used to implement FFT processor. According to the algorithm and the difficulty to implement it in hardware, I choose Decimation-In-Timer radix 2 FFT algorithm and pipeline hardware structure which can improve the processing speed to design the FFT processor on the FPGA chip XC2V8000 of Virtex II made by XILINX . And the data form in the calculation is IEEE single-precision floating-point standardized form which can increase the accuracy of the calculation. I use Verilog HDL hardware description language to design the FFT processor which works in pipeline form in design platform ISE 7.1, and the points in calculation is 1024.Finaly I simulate the design in MATLAB software and compare the results of the FFT processor with the academic results calculated in MATLAB and calculate the errors. The simulation indicates that the result of calculation can reach equivalent precision and the operation speed of FFT can satisfy the request of commonly real— time signal processing.
引文
1董绍平,陈世耕,王洋.数字信号处理基础(修订版).哈尔滨工业大学出版社,1996:225～243
2 (美)迈耶-贝斯(Meyer-Baese,U)著;刘凌译.数字信号处理的FPGA实现(第2版).清华大学出版社,2006:219～235
3王金明.数字系统设计与Verilog HDL.第2版.电子工业出版社,2005:33～36
4夏宇闻. Verilog数字系统设计教程.北京航空航天大学出版社,2003:1～9
5 (美)奥本海姆(Oppenheim,A.V.),谢弗(Schafer,R.W.),巴克(Buck,J.R.)著;刘树棠,黄建国译.离散时间信号处理(第2版).西安交通大学出版社,2001:436～539
6伍万棱,邵杰,冼楚华. FPGA实现的基4FFT处理器高效排序算法研究.南京航空航天大学学报. 2005,37(2):222～226
7胡德俊. FFT处理器的设计与实现.合肥工业大学硕士学位论文. 2006:15～17
8邓学禹.基于FPGA的高速高阶流水线工作FFT设计.电讯技术,2005,(2):188～191
9孙阳,余锋.基于FPGA的FFT/IFFT处理器的实现.电子工程师. 2002,(28):52～56
10王诚,薛小刚,钟信潮. XILINX ISE使用详解.人民邮电出版社, 2004:63～83
11王伟. Verilog HDL程序设计与应用.人民邮电出版社, 2005:66～91
12董敬富,李雪.浮点数的教学实践与研究.安阳工学院学报. 2006,(3):137～140
13张予器.超高精度浮点数运算的关键技术研究.国防科技大学硕士学位论文. 2005:35～50
14王伟,吴裕功.快速浮点加法器.电子测量技术. 2005,(5):71～72
15郭天天,张志勇,卢焕章.快速浮点加法器的FPGA实现.计算机工程. 2005,(31):202～204
16朱亚超.基于IEEE 754的浮点数存储格式分析研究.计算机与信息技术. 2006,(9):50～52
17王颖,林正浩.快速浮点加法器的优化设计.电子工程师. 2004,(11):24～26
18陈冬,李小珉,赵志宏.浮点运算的FPGA实现. DSP开发与应用. 2007,(23):208～210
19吕律,易清明,刘光昌.基于FPGA单精度浮点乘法器的设计实现与测试.暨南大学学报(自然科学版). 2004,(3):302～309
20李笑盈,孙富明,夏宏.浮点加法运算器前导1预判电路的实现.计算机工程与应用. 2002,(21):142～146
21 IEEE Standard for Binary Floating-Point Arithmetic, ANSI/IEEE Std 754-1985,1985:1～20
22 Chi Huang, Xinyu Wu, Jinmei Lai, Chengshou Sun, Gang Li. A Design of High Speed Double Precision Floating Point Adder Using Macro Modules, Design Automation Conference, 2005:18~21
23 R.V.K.Pillai, D.Al-Khalilit, A.J.Al-Khalili.A Low Power Floating Point Accumulator, VLSI Design, Eleventh International Conference,1998:330~333
24 C.S.WALLACE, A Suggestion for a Fast Multiplier, IEEE Transactions on Electronic Computers,1964:14~17
25 Saroja.V Siddamal, R.M Banakar , B.C. Jinaga . Design of High-Speed Floating Point Multiplier, 4th IEEE International Symposium on Electronic Design, Test & Applications,2008:285~289
26 Junhyung Um , Tacwhan Kim, Utilization of Carry-Save-Adders in Arithmetic Optimization, ASIC/SOC Conference,1999:173~177
27 Fayez Elguibaly. A Fast Parallel Multiplier-Accumulator Using the Modified Booth Algorithm, Analog and Digital Signal Processing, IEEE Transactions and Circuits and Systems,2000,(47):902～908
28 Yohei Horima, Takeshi Onomi, Masayuki Kobori, Itsuhei Shimizu, Koji Nakajima. Improved Design for Parallel Multiplier Based On Phase-Mode Logic, IEEE Transactions on Applied Superconductivity,2003,(13):527～530
29 Gensuke Goto, Atsuki Inoue, Ryoichi Ohe, Shoichiro Kashiwakura, Shin Mitarai, Takayuki Tsuru, Tetsuo Izawa. A 4.1-ns Compact 54×54-b Multiplier Utilizing Sign-Select Booth Encoders,Solid-State Circuits IEEE ,1997,(32):1676～1682
30 Soontorn Oraintara, Ying-Jui Chen, Truong Q.Nguyen. Integer Fast Fourier Transform, IEEE TR on Signal Processing,2002,(50):607～618
31 VirtexTM II Platform FPGAs Complete Data Sheet, www.xilinx.com
32 Herbert L.Groginsky, George A.Works. A Pipeline Fast Fourier Transform.IEEE TR on Computers 1970,(19):1015~1019
33夏宇闻.数字系统设计-Verilog实现,高等教育出版社, 2006:1～17
34林灶生,刘绍汉. Verilog FPGA芯片设计,北京航空航天大学出版社,2006:201～207
35 Ali Saidi. Decimation-In-Timer-Frequency FFT Algorithm, IEEE International Conference on Acoustics, Speech and Signal Processing 1994,(3):453～456
36 Chung-Ping Hung, Sau-Gee Chen, Kun-Lung Chen. Design of an Efficient Variable-length FFT Processor, IEEE Circuit and Systems 2004,(2):23～26
37 Kiran George, Chien-In IIenery Chen. Configurable and Expandable FFT Processor for Wideband Communication, IEEE Instrumentation And Measurement Technology Conference 2007:1～6
38蔡可红.基于FPGA的FFT设计与实现.南京理工大学硕士学位论文,2006:31～68
39杜慧敏,李宥谋,赵全良.基于Verilog的FPGA设计基础.西安电子科技大学出版社,2006:225～230
40简弘伦.精通Verilog HDL:IC设计核心技术实例详解.电子工业出版社, 2005:66～68
41赵红怡,张常年.数字信号处理及其MATLAB实现.化学工业出版社, 2002:126～129
42 Wen-Chang,Yeh, Chein-Wei,Jen. High-Speed Booth Encoded Parallel Multipiler Design,IEEE TR on Computers,2000,(49):692～701
43 Philip E.Madrid, Brian Millar, Earl E.Swartzlander. Modified Booth Algorithm for High Radix Fixed-Point Multiplication , IEEE TR On Very Large Scale Integration Systems,1993,(1):164～167
44 A.D.Booth. A Signed Binary Multiplication Technique, Quart. J. Mech. Appl. Math,1951,(4):236～241
45 Ediz Cetin, Richard C.S.Morling, Izzet Kale. An integrated 256-point Complex FFT Processor for Real-time Spectrum Analysis and Measurement. IEEE Instrumentation and Measurement Technology Conference,1997,(52):96～101
46 David C.Munson, Bede Liu. Floating Point Roundoff Error in the Prime Factor FFT.IEEE TR On Acoustics,Speech,And Signal Processing,1991,29(4):877～882
47 S Sukhsawas, K Benkrid. A High-level Implementation of a High Performance Pipeline FFT on Virtex-E FPGAs, VLSI ,Proceedings.IEEE Computer society Annual Symposium .2004,(56):229～232
48黄晓革. FPGA同步设计及实现.重庆邮电学院学报(自然科学版). 2006,(6):94～96
2 (美)迈耶-贝斯(Meyer-Baese,U)著;刘凌译.数字信号处理的FPGA实现(第2版).清华大学出版社,2006:219～235
3王金明.数字系统设计与Verilog HDL.第2版.电子工业出版社,2005:33～36
4夏宇闻. Verilog数字系统设计教程.北京航空航天大学出版社,2003:1～9
5 (美)奥本海姆(Oppenheim,A.V.),谢弗(Schafer,R.W.),巴克(Buck,J.R.)著;刘树棠,黄建国译.离散时间信号处理(第2版).西安交通大学出版社,2001:436～539
6伍万棱,邵杰,冼楚华. FPGA实现的基4FFT处理器高效排序算法研究.南京航空航天大学学报. 2005,37(2):222～226
7胡德俊. FFT处理器的设计与实现.合肥工业大学硕士学位论文. 2006:15～17
8邓学禹.基于FPGA的高速高阶流水线工作FFT设计.电讯技术,2005,(2):188～191
9孙阳,余锋.基于FPGA的FFT/IFFT处理器的实现.电子工程师. 2002,(28):52～56
10王诚,薛小刚,钟信潮. XILINX ISE使用详解.人民邮电出版社, 2004:63～83
11王伟. Verilog HDL程序设计与应用.人民邮电出版社, 2005:66～91
12董敬富,李雪.浮点数的教学实践与研究.安阳工学院学报. 2006,(3):137～140
13张予器.超高精度浮点数运算的关键技术研究.国防科技大学硕士学位论文. 2005:35～50
14王伟,吴裕功.快速浮点加法器.电子测量技术. 2005,(5):71～72
15郭天天,张志勇,卢焕章.快速浮点加法器的FPGA实现.计算机工程. 2005,(31):202～204
16朱亚超.基于IEEE 754的浮点数存储格式分析研究.计算机与信息技术. 2006,(9):50～52
17王颖,林正浩.快速浮点加法器的优化设计.电子工程师. 2004,(11):24～26
18陈冬,李小珉,赵志宏.浮点运算的FPGA实现. DSP开发与应用. 2007,(23):208～210
19吕律,易清明,刘光昌.基于FPGA单精度浮点乘法器的设计实现与测试.暨南大学学报(自然科学版). 2004,(3):302～309
20李笑盈,孙富明,夏宏.浮点加法运算器前导1预判电路的实现.计算机工程与应用. 2002,(21):142～146
21 IEEE Standard for Binary Floating-Point Arithmetic, ANSI/IEEE Std 754-1985,1985:1～20
22 Chi Huang, Xinyu Wu, Jinmei Lai, Chengshou Sun, Gang Li. A Design of High Speed Double Precision Floating Point Adder Using Macro Modules, Design Automation Conference, 2005:18~21
23 R.V.K.Pillai, D.Al-Khalilit, A.J.Al-Khalili.A Low Power Floating Point Accumulator, VLSI Design, Eleventh International Conference,1998:330~333
24 C.S.WALLACE, A Suggestion for a Fast Multiplier, IEEE Transactions on Electronic Computers,1964:14~17
25 Saroja.V Siddamal, R.M Banakar , B.C. Jinaga . Design of High-Speed Floating Point Multiplier, 4th IEEE International Symposium on Electronic Design, Test & Applications,2008:285~289
26 Junhyung Um , Tacwhan Kim, Utilization of Carry-Save-Adders in Arithmetic Optimization, ASIC/SOC Conference,1999:173~177
27 Fayez Elguibaly. A Fast Parallel Multiplier-Accumulator Using the Modified Booth Algorithm, Analog and Digital Signal Processing, IEEE Transactions and Circuits and Systems,2000,(47):902～908
28 Yohei Horima, Takeshi Onomi, Masayuki Kobori, Itsuhei Shimizu, Koji Nakajima. Improved Design for Parallel Multiplier Based On Phase-Mode Logic, IEEE Transactions on Applied Superconductivity,2003,(13):527～530
29 Gensuke Goto, Atsuki Inoue, Ryoichi Ohe, Shoichiro Kashiwakura, Shin Mitarai, Takayuki Tsuru, Tetsuo Izawa. A 4.1-ns Compact 54×54-b Multiplier Utilizing Sign-Select Booth Encoders,Solid-State Circuits IEEE ,1997,(32):1676～1682
30 Soontorn Oraintara, Ying-Jui Chen, Truong Q.Nguyen. Integer Fast Fourier Transform, IEEE TR on Signal Processing,2002,(50):607～618
31 VirtexTM II Platform FPGAs Complete Data Sheet, www.xilinx.com
32 Herbert L.Groginsky, George A.Works. A Pipeline Fast Fourier Transform.IEEE TR on Computers 1970,(19):1015~1019
33夏宇闻.数字系统设计-Verilog实现,高等教育出版社, 2006:1～17
34林灶生,刘绍汉. Verilog FPGA芯片设计,北京航空航天大学出版社,2006:201～207
35 Ali Saidi. Decimation-In-Timer-Frequency FFT Algorithm, IEEE International Conference on Acoustics, Speech and Signal Processing 1994,(3):453～456
36 Chung-Ping Hung, Sau-Gee Chen, Kun-Lung Chen. Design of an Efficient Variable-length FFT Processor, IEEE Circuit and Systems 2004,(2):23～26
37 Kiran George, Chien-In IIenery Chen. Configurable and Expandable FFT Processor for Wideband Communication, IEEE Instrumentation And Measurement Technology Conference 2007:1～6
38蔡可红.基于FPGA的FFT设计与实现.南京理工大学硕士学位论文,2006:31～68
39杜慧敏,李宥谋,赵全良.基于Verilog的FPGA设计基础.西安电子科技大学出版社,2006:225～230
40简弘伦.精通Verilog HDL:IC设计核心技术实例详解.电子工业出版社, 2005:66～68
41赵红怡,张常年.数字信号处理及其MATLAB实现.化学工业出版社, 2002:126～129
42 Wen-Chang,Yeh, Chein-Wei,Jen. High-Speed Booth Encoded Parallel Multipiler Design,IEEE TR on Computers,2000,(49):692～701
43 Philip E.Madrid, Brian Millar, Earl E.Swartzlander. Modified Booth Algorithm for High Radix Fixed-Point Multiplication , IEEE TR On Very Large Scale Integration Systems,1993,(1):164～167
44 A.D.Booth. A Signed Binary Multiplication Technique, Quart. J. Mech. Appl. Math,1951,(4):236～241
45 Ediz Cetin, Richard C.S.Morling, Izzet Kale. An integrated 256-point Complex FFT Processor for Real-time Spectrum Analysis and Measurement. IEEE Instrumentation and Measurement Technology Conference,1997,(52):96～101
46 David C.Munson, Bede Liu. Floating Point Roundoff Error in the Prime Factor FFT.IEEE TR On Acoustics,Speech,And Signal Processing,1991,29(4):877～882
47 S Sukhsawas, K Benkrid. A High-level Implementation of a High Performance Pipeline FFT on Virtex-E FPGAs, VLSI ,Proceedings.IEEE Computer society Annual Symposium .2004,(56):229～232
48黄晓革. FPGA同步设计及实现.重庆邮电学院学报(自然科学版). 2006,(6):94～96