定点FFT量化误差模型及性能分析

开篇：润墨网以专业的文秘视角，为您筛选了一篇定点FFT量化误差模型及性能分析范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：介绍了快速傅里叶变换(FFT)的基本原理，针对硬件实现中的定点运算，分析推导出了不同fft长度和不同量化位数带来的误差模型，并进行了实验验证。结果表明，相同量化位数条件下，FFT长度越长误差越大;相同FFT长度条件下，量化位数越多，误差越小。实验结果为FFT设计提供了参考。

关键词：FFT; 定点运算; 误差模型; FFT长度; 量化位数

中图分类号：TN911.72-34文献标识码：A 文章编号：1004-373X(2011)21-0083-03

Quantification Error Model of Fixed-point FFT and Its Performance Analysis

ZHAO Min, ZHANG Quan

(National University of Defense Technology, Changsha 410073, China)

Abstract： The basic theory of fast Fourier transform (FFT) is introduced. An error model with different FFT length and different quantification bit width is analyzed according to the fixed-point calculation of hardware realization. The experimental results indicate that the longer FFT length is, the bigger error will be in the condition of the same quantification bit width, and the wider quantification bit width is, the smaller error will be in the condition of the same FFT length. The results provide a reference for FFT design.

Keywords： FFT; fixed-point calculation; error model; FFT length; quantification bit width

数字信号处理是信号与信息处理的一个分支学科，在现今的信息时代一直起着中流砥柱的作用，它的核心算法是离散傅里叶变换(DFT)。DFT使信号在数字域、频域都实现了离散化，从而可以用通用计算机处理离散信号。使数字信号处理从理论走向实用的是快速傅里叶变换(FFT)，FFT的出现大大减少了DFT的运算量，使实时的数字信号处理成为可能。FFT硬件在实现上一般采用蝶形流水过程实现\[1\]。为了节省硬件实现资源，经常采用有限字长定点实现方法［2］，但是定点实现方法往往带来精度的损失，设计者需要根据需求设计不同长度、不同位长的FFT。本文从理论上推导出量化位数以及FFT长度对FFT结果的影响模型，并对模型进行了实验验证。

1 FFT蝶形算法

FFT算法是基于将一个长度为N的序列离散傅里叶变换逐次分解为较短的离散傅里叶变换来计算这一基本原理。它的出现大大减少了DFT的运算量，避免了大量重复运算，其算法按照抽取方式的不同可分为按时间抽取(DIT-FFT)算法和按频率抽取(DIF-FFT)算法。按照蝶形运算的构成不同可分为基2、4、基8以及任意因子(2n,n为大于1的整数)，其中基2、基4算法较为常用。

И

按时间抽取(DIT)算法与按频率抽取(DIF)算法没有本质上的区别，只是复数加减法与旋转因子乘法的次序有区别。两种方法的运算量是一样的，都小于直接计算DFT的运算量。同理，通过推导可得随着蝶形运算基的增加，其运算量会不断减少，而运算复杂度不断增加，在实际应用中要根据自己需求来选择合适的蝶基或多个蝶基混合的分裂基。

图1 按时间抽取的蝶形计算

2 定点FFT分析

在FFT硬件实现中存储数据的存储器字长是有限的，在误差允许情况下一般采用固定字长的定点量化方法来实现FFT。

2.1 定点量化方法

定点数量化在硬件实现上常用二进制补码形式表示。一个实数用无限精度的补码可以表示如下：

И

式中:b0为符号位;bi是数据位;B是数据位宽度;Xm是任意幅度加权因子(通常这个加权因子是隐含在实现的程序或硬件结构中)。由上式可看出，有限位数据量化及量化数据运算过程中数据的表示都会出现溢出与截断误差两种现象。

为了更方便地分析FFT在运算过程中的误差问题，这里不考虑数据的量化误差，而主要讨论数据运算过程中的误差。

(1) 溢出误差。

当运算结果超出了数据表示范围，则可能会产生很大的误差，例如，考虑5位的补码数01110，若将该数加上00010，那么结果为10000，导致最终结果的错误。所以FFT计算过程中会控制数据输入的大小范围或增加量化位数，从而使计算过程中不出现溢出。

(2) 截断误差。

FFT计算过程主要包括加法、乘法两种操作运算。进行加法运算时不存在截断误差，而在进行乘法运算时，两个┆B+1位有符号补码数相乘会得到2(B+1)位的结果，将结果存入与输入数据相同字长的存储器时会将高位保留,低位作舍入或去尾处理，从而引入误差，这是无法避免的。

因此乘法运算的截断误差对FFT的计算精度起决定性作用，下面将重点分析。

2.2 截断误差对FFT的影响

采用线性噪声模型分析可知，在不同类的 FFT计算中截断误差对计算结果的影响是相类似的，所以这里考虑基2按时间抽取算法，数据处理采用定点方式，小数点定在第一位符号位之后。

2.2.1 蝶形单元误差模型

基2DIT-FFT蝶形单元的误差模型如图3所示。

图2 蝶形算法中的线性噪声模型

令Е糯表复数乘法结果引起的误差，在这个蝶形结构中，有1个复数乘法和2个复数加法，其中只有乘法引入了截断误差，而一个复数乘法包含4个实数乘法。假设量化位数是B+1位，每个实数乘法会产生如下误差：两个B+1位数相乘会得到一个2(B+1)位的乘积，将结果舍入为B+1位，将产生在［－2－(B+1),2－(B+1)］上均匀分布的误差，每个实数乘法的误差之间不相关，且与输入/输出不相关，所以得到一个复数乘法产生误差的方差为：

这也就是1个蝶形单元所产生的噪声。

2.2.2 N点FFT误差分析

计算N点的FFT时，在每一级中新数列的N个数都是由先前数列的两个元素线性组合到一起来产生的，在FFT的算法流图中每个最终输出节点的产生都与┆N-1个蝶形相连接。假设各个蝶形中的噪声源不相关，则可以计算出最大输出噪声的均方值为：

И

И

然而对任一输出结点，所参与的第一级N/2个蝶形的旋转因子W0N=1，不会产生舍入误差。为了简化处理，假定除N/2个蝶形之外的蝶形都有舍入噪声引入，У玫礁精确的最大输出噪声均方值为：

И

出噪声均方值正比于变换点数N/2。

在实现定点FFT运算时，必须保证没有溢出。由式(1)可得：

由上可知，各级数列的最大幅度不是递减的。如果FFT的最后输出小于1，则各级数列的各个节点幅度必然小于1，从而保证不出现溢出。由DFT的定义式可得到：

И

为保证计算不溢出，根据X［k］

И

这表明信噪比随着N(N/2-1)的增大而减小。当N1时，N每增加1倍，为了维持同样的噪声信号比，就要把寄存器的长度增加1位。

3 实验结果

通过Xilinx ISE平台设计FFT模块，分别对不同点数及不同量化位数的FFT进行了实验。

3.1 长度对FFT的影响

数据格式采用16位有符号定点格式，对512点、1 024点、2 048点的FFT进行了处理，得到信噪比结果如图3所示。

从图3可以看出，保持量化位数不变，随着FFT点数N的增加，最终结果的信噪比会变小。

3.2 量化位数对FFT的影响

同时本文分别采用16位、24位、32位的有符号定点格式，对2 048点的FFT进行了处理，得到信噪比结果如图4所示。

お

从图4可以看出，保持FFT点数不变，随着量化位数的增加，最终结果的信噪比会变大。

对比图3,图4可以看出，实验结果满足理论分析，并且实验结果相对大于理论值。这是由于当旋转因子WkN=±1或±j时，所作的乘法并没有引入误差ε，Ф理论分析时仍然认为有部分旋转因子引入了误差。

4 结 语

本文论述了FFT的蝶形实现原理以及定点量化方法。通过线性噪声模型对定点FFT运算进行误差分析，得到量化误差公式。通过对不同FFT长度、不同量化位数的FFT运算进行实验测试，结果表明FFT计算的信噪比随序列长度以及量化位数的不同而改变。同时实际的信噪比要稍好于理论模型值。这主要因为FFT实现中存在以特殊常数作为乘数的乘法，不会引入误差。

参考文献

［1］杨静，郑恩让，张玲，等.基于FPGA的FFT处理器设计与实现［J］.化工自动化及仪表，2010,37(3):107-109.

［2］付博，李栋，谢应科.一种高速定点FFT处理器的设计与实现［J］.计算机工程，2005,31(11):52-55.

［3］王林泉，皮亦鸣，陈晓宁，等.基于FPGA的超高速FFT硬件实现［J］.电子科技大学学报，2005,34(2):152-155.

［4］愈卞章，李志钧，金明录.数字信号处理［M］.西安：西北工业大学出版社，2000.

［5］［美］A V 奥本海姆,R W 谢弗,J R 巴克.离散时间信号处理［M］.刘树棠，黄建国,译.2版.西安:西安交通大学出版社,2003.

［6］李眈,龙腾,李方慧.定点FFT的有限字长效应分析［J］.北京理工大学学报,1999,19(5):617-621.

［7］KNIGHT W R, KAISER R. A simple fixed-point error bound for the fast Fourier transform \[J\]. IEEE Transactions on Acoustics, Speech and Signal Process., 1979, 27(6): 615-20.

［8］AYAN Banerjee, DHAR Sundar, Anindya. FPGA realization of a CORDIC based FFT processor for biomedical signal processing \[J\]. Microprocessors and Microsystems, 2001, 25(3): 131-42.

［9］MOROZOV J A. Effects of quantization in FFT algorithms \[C\]// International Conference on Actual Problems of Electron Devices Engineering. \[S.l.\]: IEEE Press, 2006: 526-533.

［10］HUI C C, TIONG J D. Error analysis of FFT architecture for digital video applications \[C\]// 3th IEEE International Conference on Electronics, Circuits and Systems. Greece: IEEE CAS Society Press, 1996: 820-823.

作者简介：

赵 敏 男，1986年出生，江苏人，在读硕士研究生。主要研究方向为通信网信息安全与对抗。