一种变步长插值反正切算法的设计与实现

陈文艺, 王子越, 杨 辉

(1.西安邮电大学 物联网与两化融合研究院， 陕西 西安 710061； 2. 西安邮电大学 通信与信息工程学院, 陕西 西安 710121)

查找表(look-up-table, LUT)算法在图像处理和三维测量方面有重要应用[1]，其中相位测量轮廓术(phase measuring profilometry，PMP)是应用较为广泛的一种结构光三维测量技术[2]，其基本思想是通过计算有一定相位差的多副光栅条纹图像来得到每个像素的相位值，再根据相位值计算物体的深度信息。其中相对相位的解算涉及到反正切函数的求解，而目前应用较为广泛的数字映射技术包含数字循环技术、乘法技术和查找表技术[3-4]等。其中cordic算法就是典型的数字循环技术，只需进行移位和加法运算就能实现三角函数的运算[5]。为了提高算法精度，cordic算法需要进行反复迭代计算或者增加流水线长度，反复迭代节省硬件资源但是运算速度慢，增加流水线则会增加运算资源[6]。多项式近似及泰勒展开算法主要是利用逻辑资源和乘法器资源逼近目标函数,优点是收敛速度较快，但是会消耗较多的乘法器资源，同时等待时间较长[7]。在高精度计算情况下，查找表尺寸会呈指数式增长，因此，查找表技术通常只应用于单精度范围内的计算[8-9]。

为了改善基于查找表技术下高精度要求时资源消耗较多的问题，本文拟在插值查找表基础上利用matlab工具量化误差范围，并划分插值点个数，改变步长，从而在保证一定误差限度下减少资源消耗。

1 插值查找表反正切算法

查找表实质是一个存储元件，能够根据任何给定的输入状态组合，查找得到相应的函数值，但使用查找表需要在精度和表的大小之间作出权衡。对于8-10位的短输入来说，直接用查找表是最有效的。而对于12-20位的输入，使用插值查找表是最有效的。插值查找表在实现数字信号处理功能时，不仅具有查找表所具有的优势，而且无需太多的存储资源，可以使用较小容量的LUT对其存储值线性内插，以模拟更大容量的LUT，从而达到更高数值分辨率。插值查找表用计算资源和等待时间的增加换取表尺寸的减小。此外，通过插值查找表只需再增加一小部分逻辑资源和一个乘法器。

线性插值中点的纵坐标

其中，(x0,y0)与(x1,y1)都为已知点坐标，xa为区间(x0,x1)内某一位置点坐标。

如用16位无符号定点数U16.8作为输入，用高有效位8 bit作为地址线，低有效位8 bit作为插值位，则自变量x的取值范围为0≤x≤256，用于插值的步长为2-8，便可以模拟地址线为16位的LUT。双端口随机存取存储线性插值计算结构，如图1所示。

图1 双端口随机存取存储线性内插计算结构

反正切函数f(x)=arctanx曲线如图2所示。对其进行等间距插值误差，结果如图3所示。由图3可知，在自变量在(0,2)的区域误差极大。

图2 反正切函数

图3 等间距插值误差

对于反正切函数，当自变量值较小时，其非线性特性明显(曲率值较大)，反正切函数的曲率，如图4所示。

图4 反正切函数的曲率

在中低精度要求下，插值查找表很有效，但是，随着输入宽度的增加，表的尺寸仍会呈指数增长。在保证一定误差前提下，使用插值查找表就要增加用于查找的高有效位位宽，导致资源开销的增加。针对这一问题，结合反正切函数的曲率特征，提出一种变步长插值查找表算法。

2 变步长插值反正切算法

2.1 自变量范围内变步长取点

分析图4反正切函数的曲率曲线，可以发现，其曲率逐渐增加并在x=0.83附近达到最大值，随后曲率逐渐减小并趋近于0。利用反正切函数曲率特性，考虑到易于硬件实现和最大化利用存储资源等划分原则，划分自变量x的坐标应满足以下要求[10]。

(1) 函数曲率高的范围内尽量多划分点。

(2) 从自变量值到查找表地址的映射以及后续插值易硬件实现。

(3) 采用划分方法得到对应点的个数m≤2n，并且点的个数尽量大。

拟用16位无符号定点数U16.8输入映射为8位地址线即最大256个点；输出结果为16位无符号定点数U16.15，按上述要求的自变量范围、缩放比例、规划点的个数如表1所示。

表1 自变量范围、其缩放比、规划点个数

2.2 量化误差范围

借助Matlab LUT函数量化误差需要指定函数类型为反正切函数；需要指定分段范围内各自自变量上限、自变量下限、自变量数据类型、自变量数据步长、因变量数据类型、因变量数据步长、舍入类型等，确定自变量取点策略；最后将分段量化自变量[0,256)范围内插得到函数值与32位浮点数函数值作比较，其最大绝对误差1.4×10-4，满足系统要求。自变量范围为[0,2)的反正切函数与线性插值函数，如图5所示。采用以2的幂为间隔的自变量取点策略，共得到128个自变量点，对自变量在[0，2)范围内的反正切函数的插值误差量化，如图6所示。

图5 自变量[0,2)内128个插值点插值

图6 插值误差示意图

从图6可以看出，采用以2的幂为间隔的自变量取点策略，得到的128个自变量点，对自变量在[0，2)范围内的反正切函数的误差量化，自变量范围内最大误差为5.076 7×10-5。

3 变步长插值反正切算法设计与实现

3.1 模块功能设计

将系统划分为地址映射模块和插值查找表模块2个模块。其中地址映射模块是重点，其功能是将自变量16位无符号定点数U16.8按照自变量分段划分方式映射至8位地址位。系统结构如图7所示。

图7 系统结构示意图

3.1.1 地址映射模块

地址映射模块将数据预处理模块中16位无符号定点数U16.8数据映射成为插值查找表8位地址[11]。采用判定最高有效位及位拼接的方法，自变量范围为[0,256)的16位数据映射规则由表2给出具体划分，分别包含数据格式、对应的8位地址、其映射规则、插值低有效位及点的个数。

表2 地址映射细则

3.1.2 线性插值模块

插值查找表模块采用双口随机存取存储查找表，读取输入的当前地址和下一个地址的数据用于插值，线性插值硬件结构，如图8所示。

图8 线性插值硬件结构

在图8中，Y0是8位映射地址(U8.0)，Y1是Y0地址的下一位(U8.0)，用Y1地址读取到的为B值(U16.15)、Y0地址读取的为A值(U16.15)，Dx为插值有效位，其位宽随输入变化。用B-A的值与插值低有效位Dx相乘即为B1，则A+B1即为得到线性插值后的相位值16位(U16.15)。

3.2 算法实现

采用标准四步相移的正弦光栅数据输入并对其进行相位解算。数据流处理及显示过程，如图9所示。

图9 数据流处理及显示过程

使用内嵌逻辑分析仪对相位解算进行在线调试，如图10所示。软件、硬件及实时硬件计算结果VGA显示，如图11所示。

图10 相位解算数据采集调试

图11 软件、硬件计算结果及实时硬件计算结果VGA显示

4 实验结果及分析

选用Modelsim10.0进行系统仿真。采用流水线结构工作，第一个数据输入后顺延10个时钟得到相位结果。例如，当输入为2 913(U16.8)时，10个时钟周期后输出的相位值为48 598(U16.15)，对应Matlab中32位精度反正切函数值为1.483 139 …。

反正切值相位的16位无符号定点数U16.15为48 598，与32位精度的反正切函数误差为4.635 8×10-5。系统仿真结果如图12所示。

图12 系统仿真结果

选用Altera cycloneIV系列的EP4CE30F23C6芯片，在quartus15.1的开发环境对代码进行编译综合，其最高时钟频率为219.06 MHz共使用311个逻辑单元(Les)，4211个存储位(Bits)，一个9位乘法器，一个9位除法器。

仿真实验使用quartus15.1软件且在同一芯片选用Altera自带的16次迭代cordic IP核作反正切运算。设置IP核性能最高频率目标为219 MHz，综合后达到206.1 MHz。其最大绝对误差随输出位宽变化，最大值为1.431 2×10-4，如图13所示。其消耗资源情况，如表3所示。

图13 不同输出位宽的最大绝对误差

算法16位BitsLes17位BitsLes18位BitsLes19位BitsLes20位BitsLes21位BitsLes22位BitsLes23位BitsLescordic算法02 43502 73302 99403 41403 70804 23204 48504 722变步长插值8位地址线4 2113114 3823114 7233114 9793115 2353115 4913115 7473116 003311变步长插值9位地址线8 1923118 7043119 216 3119 72831110 24031110 75231111 26431111 776311

cordic算法的精度由迭代次数与输出位宽共同决定[12]，由图13及表3可以得到结论如下。

(1) 16次迭代cordic算法的误差在16位输出位宽至19位之间变化较为明显，后续变化趋于平缓。变步长插值算法的误差随输出位宽变化一直趋于平缓。8位地址线的变步长插值算法在16位位宽时其误差明显小于16次迭代cordic算法，其消耗资源也比较接近。

(2) 与cordic算法相比，变步长插值算法适合存储资源丰富、逻辑资源较少的系统。

变步长插值算法的系统最高频率基本不会随位宽的增加而降低，16次迭代cordic算法的系统最高频率会随输出位宽而降低，23位宽时最高频率192.08 MHz。

5 结语

结合插值查找表算法的特点和反正切函数的曲率特性，使用变步长插值查找表的方法对反正切函数进行计算，通过Matlab量化误差确定误差范围，再经地址映射将数据转化为插值地址，通过线性插值完成查找。经Modelsim10.0仿真和QuartusII 15.1在EP4CE30F23C6芯片下综合验证，结果表明，该方法与传统插值查找表和ATLERA CORDIC IP核比较，在同样的16位位宽输出下，最大误差1.431 2 ×10-4，误差较小；最高工作频率为219.06 MHz，工作频率较高；同时，占用资源适中，相较于传统插值查找表算法可以节省存储资源。