多项式拟合在log-add算法单元中的应用及其FPGA实现

摘 要： 综合考虑面积和速度等因素，采用一次多项式拟合实现了简单快速的log-add算法单元。实验结果表明，在相同的精度要求下，其FPGA实现资源占用合理，硬件开销好于其他次数的多项式拟合实现方案。
关键词： 多项式拟合；log-add算法单元；FPGA实现

在多路实时语音处理系统中，基于高斯混合概率模型[1，2]的系统后端运算量非常大，采用log-add算法单元可以简化运算，提高运算效率。其函数形式为[3]：

查表法可以认为是多项式次数为0的情况，随着精度要求的增加，查找表会变得很大[5]。函数逼近可以采用多项式拟合，首先根据所需要的精度确定多项式次数和分段的大小，然后计算每一段的多项式系数。
设分段的大小为d(d=2-k，k=0，1，2…)，计算各段系数时，各段函数平移到区间[0，d），如图2所示。用Matlab进行多项式拟合依次得到各段系数。由此可以得出各段的拟合多项式为：

这样实现时可以把二进制的定点数x分为MSBs和LSBs两段。MSBs对应段标号i，由段标号取出系数ci0，ci1，ci2…；LSBs对应浮点数xl，代表段内偏移值。由图3可以计算出f(x)。

MSBs和LSBs应该这样选取，例如定标为Q32.f，选择d=1/2，则MSBs为高32-（f-1）位，LSBs为低f-1位；选择d=1/4, 则MSBs为高32-(f-2)位，LSBs为低f-2位……；如果MSBs为32或31，则变成了查表法。
2 多项式拟合的实现方案
2.1 多项式次数与分段大小、精度的关系
用Matlab进行仿真，表1列出了各种精度要求下各次多项式所需的分段大小(d)，其中?啄为精度要求，?茁为多项式的次数。
由表1可以看出，相同次数的情况下，精度要求越高，分段大小d越小；而相同精度的情况下，次数越高，分段大小d越大。另外，次数越低，精度越高，分段大小d下降的数量级越快。

表2列出各次多项式在不同精度要求下，所需要系数个数(n)的分布情况。

由表2可以看出，其结果与表1趋于一致。相同次数下，精度要求越高，所需要的系数个数n越多；而相同精度下，次数越高，所需要系数个数n越少。n随着次数的降低和精度的提高迅速增大。
与n相反，多项式的计算量随着多项式次数的增加而增加。根据horner算法[3]多项式的表达式如下：

式(6)表明，多项式次数增加1次，计算多项式的函数值增加1次乘法和1次加法。多项式系数存储量与多项式的计算量是其FPGA实现时互相制约的两个因素。
3 仿真结果
为了取得面积与速度的平衡，根据测试结果及实际系统的要求，选择δ=10-4、β=1来实现。本文采用Xilinx ISE Design Suite 10.1进行仿真测试。定标取Q32.23，其硬件实现计算流程如图4，输入为定点数x，由MSBs和LBSs取得系数和xl，经过reg系数寄存器及1次乘法和1次加法，输出y。

时序仿真结果结果如图5。输入x是32 bit的无符号定点数，输出为y；clk是时钟；reset为复位信号；MSBs是x的高位，用于得到多项式系数；LSBs是x的低位即自变量；temp是用于缓存中间结果，coef[...]是多项式系数。输出延迟3个时钟周期，流水线填满后，每个时钟周期输出一个结果。

例如输入32’h00333333（浮点数0.4），从图中可以看出其输出y为24’h41aba5，与实际函数值24’h41aa7c存在误差。其实现结果与浮点结果比较误差如图6。可以看出定点数误差在800以内，也就是浮点数约10-4以内，误差范围与表1相一致。

使用ISE软件的XST工具综合，选择设备为Xilinx公司Virtex5系列的XC5VFX100T(speed-2)。其资源占用情况如表3，其中Xilinx公司的乘加硬件设备DSP48E用于算法中的乘法运算及加法运算[6]。

可以对比δ=10-4，β=0，1，2，3四种实现方式的硬件开销，如表4。

由表4可以看出，虽然多项式次数为0时使用寄存器（Registers）和查找表（LUTs）最少，且乘法和加法次数（DSP48Es）为0，但由于其使用了24×40 960 ROM，占用存储面积较大；而一次多项式拟合虽然所占用查找表(LUTs)一项相对较多，但综合考虑，其他资源占用都比较均衡。其整体的资源开销要好于其他方案。
log-add算法单元作为高斯混合概率模型FPGA实现的基本算法单元，能够简化运算、提高运算效率。在系统精度要求10-4的情况下，采用一次多项式拟合能够有效地节省硬件开销，实现简单快速log-add算法单元，为大规模实时处理多路语音数据提供了重要保证。
参考文献
[1] Douglas A.Reynolds，THOMAS E.Quatieri，Robert B.Dunn. Speaker verification using adapted gaussian mixture models[J].Digital Signal Processing，2000(10).
[2] Kazuo Miura，Hiroki Noguchi，Hiroshi Kawaguchi，et al.A low memory bandwidth gaussian mixture model(GMM) processor for 20，000-word real-time speech recognition FPGA system[J].ICECE Technology，2008.FPT.2008.
[3] MELNIKOFF S J，FQUIGLEY S.Implementing the Log-add Algorithm in Hardware[J].Electronics Letters，2003.
[4] LEE B R，BURGESS N.A pallrallel Look-up logarithmic number system addition subtraction scheme for FPGA[J]. Proc.FPT，2003.
[5] 李炜，沈绪榜.对数数值系统的研究[J].微电子学与计算机，2004.
[6] 胡彬.Xilinx ISE Design Suite 10.x FPGA开发指南—逻辑设计篇[M].北京：人民邮电出版社，2008.