一种应用FPGA定点化技术实现指数CORDIC算法收敛域扩张的方法

摘要

本发明公开了一种应用FPGA定点化技术实现指数函数CORDIC算法收敛域扩张的方法，该方法包括：由双曲系统CORDIC算法推导收敛域内指数函数CORDIC算法；应用区间压缩方法实现指数函数CORDIC算法的收敛域扩张；应用定点化技术在FPGA实现指数函数CORDIC算法收敛域扩张。本发明只用两条数据链，即对角度zi与坐标xi进行迭代，能有效节省1/3硬件资源，提高算法实时性；应用定点化技术在FPGA实现收敛域扩张方法，其求解方法巧妙，只需使用两个乘法器，避免除法器的使用；采用15级流水线结构，用FPGA实现双曲系统CORDIC算法来求解指数函数，运算结果相对误差达到了10-4，满足实际工程精度要求。

说明书

技术领域

本发明涉及一种应用FPGA定点化技术实现指数CORDIC算法收敛域 扩张的方法。

背景技术

指数函数和对数函数在超声检测、无线通信、图像信号处理等领域应用 非常广泛，用较低的硬件代价实现快速高精度的指、对数函数运算电路变得 非常重要。目前在硬件实现指数/对数函数求值的方法主要有查表法、泰勒展 开式法、查表相加法、基于查找表的多项式逼近和坐标旋转数字计算 (Coordinate Rotation Digital Computer,CORDIC)算法等。CORDIC算法由于 硬件实现简单而备受关注，它是1959年由Volder J提出，通过一系列固定 与运算基数有关角度不断偏摆迭代以逼近所需旋转角度，由简单加法、移位 操作即可完成三角函数、指数函数、对数函数等超越函数的计算。1971年 Walther J D把旋转模式、向量模式和线性模式统一成标准CORDIC迭代方 程，并根据旋转角度分为圆周系统和双曲系统。指数函数就是在双曲系统下 采用旋转模式实现的。

为实现指数函数的CORDIC算法，国内外开展很多有益研究，主要从 指数CORDIC算法实现机理、算法改进思路、算法收敛域扩张等进行研究， 但大多文献只给出了指数CORDIC算法的仿真实现及理论探索，对硬件实 现很少作详细讨论，更没有涉及FPGA实现技巧的研究。为此，本发明针对 指数函数CORDIC算法在FPGA实现的技巧问题，研究FPGA定点化技术 实现收敛域扩张的方法，在FPGA实现指数函数CORDIC算法。

发明内容

为解决上述技术问题，本发明的目的是提供一种应用FPGA定点化技术 实现指数函数CORDIC算法收敛域扩张的方法，该方法降低结构复杂度、 节省系统资源、收敛域范围宽和计算精度高。

本发明目的通过以下技术方案来实现：

1、一种应用FPGA定点化技术实现指数CORDIC算法收敛域扩张的方 法，包括：

A由双曲系统CORDIC算法推导收敛域内指数函数CORDIC算法；

B采用区间压缩方法实现指数函数CORDIC算法的收敛域扩张；

C应用定点化技术在FPGA实现指数函数CORDIC算法收敛域扩张。

与现有技术相比，本发明的一个或多个实施例可以具有如下优点：算法 只用两条数据链，即对角度z_i与坐标x_i进行迭代，能有效节省1/3硬件资源， 提高算法实时性；应用定点化技术在FPGA实现收敛域扩张方法，其求解方 法巧妙，只需使用两个乘法器，避免除法器的使用；采用15级流水线结构， 用FPGA实现双曲系统CORDIC算法来求解指数函数，运算结果相对误差 达到了10^-4，满足实际工程精度要求。本指数CORDIC算法在超声相控TCG (Time Complement Gain)应用具有有重要的实际意义。

附图说明

附图用来提供对本发明的进一步理解，并且构成说明书的一部分，与本 发明的实施例共同用于解释本发明，并不构成对本发明的限制。在附图中：

图1是应用FPGA定点化技术实现指数CORDIC算法收敛域扩张的方 法流程图；

图2是双曲函数坐标旋转模型；

图3是整数Q和小数θ定点化值求解原理框架图；

图4是双曲系统CORDIC算法求解指数函数流水线结构图；

图5是FPGA实现双曲系统CORDIC算法指数函数部分流水线电路图；

图6是CORDIC算法指数函数在Modelsim的仿真图。

具体实施方式

容易理解，根据本发明的技术方案，在不变更本发明的实质精神下，本 领域的一般技术人员可以提出本发明的多个结构方式和制作方法。因此以下 具体实施方式以及附图仅是本发明的技术方案的具体说明，而不应当视为本 发明的全部或者视为本发明技术方案的限定或限制。

下面结合实施例及附图对本发明作进一步详细的描述。

图1是应用FPGA定点化技术实现指数CORDIC算法收敛域扩张的方 法流程图，该方法包括：

步骤10由双曲系统CORDIC算法推导指数函数CORDIC算法,实现步 骤如下：

图2为双曲函数坐标旋转模型图，图中θ为射线OV_n、双曲线和x轴围 成面积的2倍，为射线OV₁、双曲线和x轴围成面积的2倍，分别对应阴影 部分面积的2倍，双曲线x²-y²＝C上点V₁(x₁,y₁)沿着上半轴曲线移动到点 V_n(x_n,y_n)，可表示为：

矩阵形式表示为

$\left(\begin{array}{c}{x}_n\\ y_n\end{array}\right)=\left(\begin{array}{cc}\cosh \theta & \sinh \theta \\ \sinh \theta & \cosh \theta \end{array}\right)\left(\begin{array}{c}{x}_1\\ y_1\end{array}\right)=\cosh \theta \left(\begin{array}{cc}1& \tanh \theta \\ \tanh \theta & 1\end{array}\right)\left(\begin{array}{c}{x}_1\\ y_1\end{array}\right)---\left(2\right)$

将θ分解成一系列基本角度(实际上是面积)之和，为简化计 算，令微旋转角度满足条件θ_i＝d_i·tanh^-12^-i，d_i为旋转方向，由每次迭代之后 剩下角度的极性决定，则式(2)可转化为式(3)。

$\left(\begin{array}{c}{x}_n\\ y_n\end{array}\right)=\underset{i=1}{\overset{n}{\Pi }}\left(\begin{array}{cc}1& d_i·2^{-i}\\ d_i·2^{-i}& 1\end{array}\right)\left(\begin{array}{c}{x}_1\\ y_1\end{array}\right)K---\left(3\right)$

其中，K为校模因子

$\left(\begin{array}{c}K=\underset{i=1}{\overset{n}{\Pi }}\cosh {\theta }_i=\underset{i=1}{\overset{n}{\Pi }}\sqrt{\frac{\cos h^2{\theta }_i}{\cos h^2{\theta }_i-\sin h^2{\theta }_i}}=\underset{i=1}{\overset{n}{\Pi }}\sqrt{\frac{1}{1-\tan h^2{\theta }_i}}=\underset{i=1}{\overset{n}{\Pi }}\sqrt{\frac{1}{1-2^{-2i}}}\\ \underset{i\to \infty }{\lim }K=\underset{i\to \infty }{\lim }\underset{i=1}{\overset{n}{\Pi }}\sqrt{\frac{1}{1-2^{-2i}}}\approx 1.2075\end{array}\right)---\left(4\right)$

当C＝0时，双曲线x²-y²＝C最终退化为直线x＝±y，若暂不考虑K，则 迭代递推关系为：

$\left(\begin{array}{c}{x}_{i+1}=x_i+d_i{y}_i{2}^{-i}\\ y_{i+1}=y_i+d_i{x}_i{2}^{-i}\\ z_{i+1}=z_i-d_i\tan h^{-1}{2}^{-i}\\ d_i=\mathrm{sign}\left(z_i\right)\end{array}\right),i=\mathrm{1,2,3},...,n---\left(5\right)$

由于式(5)只用到加法、乘法非常适合FPGA实现。

为满足迭代序列收敛，迭代序列i的取值从第4项开始，每个3k+1(k∈ Z⁺)项必须重复一次，即i＝1，2，3，4，4，5，…，13,13，…

经过n次旋转后，有

$\left(\begin{array}{c}{x}_{n+1}=K[x_1\cosh \left(z_{\mathrm{in}}\right)+y_1\sinh \left(z_{\mathrm{in}}\right)]\\ y_{n+1}=K[x_1\sinh \left(z_{\mathrm{in}}\right)+y_1\cosh \left(z_{\mathrm{in}}\right)]\\ z_{n+1}=0\end{array}\right)---\left(6\right)$

若取初值x₁＝y₁＝1/K，z_in＝θ，则有：

x_n+1＝y_n+1＝coshz_in+sinhz_in＝e^θ    (7)

步骤20采用区间压缩方法实现指数函数CORDIC算法的收敛域扩张， 实现方法如下：

为了保证迭代序列收敛，双曲系统的CORDIC算法的收敛范围为

$\left|z_{\mathrm{in}}\right|\le {\theta }_{\max }=\underset{i=1}{\overset{N}{\Sigma }}\tan h^{-1}\left(2^{-i}\right){|}_{N=\infty }\approx 1.1182---\left(8\right)$

由于z_in的范围较小，实际应用意义不大。为扩大指数函数收敛域(输入 值范围)，必须对输入值z_in作预处理。

令z_in＝Qln2+θ，其中Q∈Z，|θ|<ln2＝0.6931，使θ处于算法收敛域内， 由此可得：

$e^{z_{\mathrm{in}}}=e^{Q\ln 2+\theta }=2^Q·e^{\theta }---\left(9\right)$

若整数Q能确定，则2^Q可通过左移或右移|Q|位实现，可把的计 算等效转化为e^θ的计算，通过区间压缩方法实现指数函数CORDIC算法的收 敛域扩张。

步骤30应用定点化技术在FPGA实现指数函数CORDIC算法收敛域 扩张，实现步骤如下：

(1)整数Q值和小数θ值定点化值的求解

令

Q＝[z_in/ln2]

R＝z_in％ln2

θ＝R/ln2

其中Q表示z_in与ln2相除得到商的整数部分，R表示z_in与ln2相除得到 的余数部分，θ表示R与ln2相除得到的商。

则有

通常FPGA实现定点数运算，故在FPGA求解Q、θ过程中，必须对式 (10)进行定点化，即乘以2ⁿ放大，再对结果右移n位实现除法恢复到原始值。

本算法扩大65536(2¹⁶)倍实现定点化，把除法运算转换成乘法运算，实 现定点化运算，有利于硬件实现，这时有：

$\frac{z_{\mathrm{in}}}{\ln 2}·2^{16}=z_{\mathrm{in}}·\frac{2^{16}}{\ln 2}\approx z_{\mathrm{in}}·94548$(其中ln2＝0.6931)    (11)

由于可以分解为整数Q和小数θ两部分，故式(11)可转化为：

$\frac{z_{\mathrm{in}}}{\ln 2}·2^{16}=2^{16}·(Q+\frac{\theta }{\ln 2})=2^{16}·Q+2^{16}·\frac{\theta }{\ln 2},Q\in Z---\left(12\right)$

图3为整数Q和小数θ定点化值求解原理框架图。

①定点化求解整数Q值

假设输入值z_in∈[-2⁷,2⁷)，对z_in定点化后(扩大2¹⁶倍)取整，用[z_in·2¹⁶]表 示，其位宽为24bit；对定点化后(扩大2¹⁶倍)取整，用[z_in·2¹⁶·2¹⁶/ln2]表 示，其位宽为42bit。表1为对应的二进制数位宽表，用H10表示bit[41:32] 共10bit，为整数部分，用L32表示bit[31:0]共32bit，为小数部分，则H10即 为Q整数部分。

表1

[z_in·2¹⁶·2¹⁶/ln2]对应二进制数位宽表

②求解小数θ定点化值

根据式(12)与表1可以得出定点化小数部分为其中L16表 示L32的高16位bit[31:16]，则2¹⁶·θ＝ln2·L16。由于ln2为浮点数，必须进行 定点化(扩大2¹⁶倍)，得2¹⁶·2¹⁶·θ＝ln2·2¹⁶·L16≈45426·L16，[45426·L16]位宽为 32bit。表2为对应的二进制数位宽表，用H17表示bit[32:16]共17bit，右移 16位可得2¹⁶·θ＝H17，即H17为θ小数部分的定点化值。

表2

[45426·L16]对应二进制数位宽表

在FPGA实现上只需两个乘法器，即可实现整数Q和小数θ定点化值求 解，实现定点化区间压缩，达到收敛域扩张的效果。

(2)采用流水线结构在FPGA定点化实现

图4为双曲系统CORDIC算法求解指数函数流水线结构图，图5为FPGA 实现双曲系统CORDIC算法指数函数部分流水线电路图。由于坐标x_n、y_n的初值与迭代模式相同，可以合成一个迭代通道，省掉坐标y_n的迭代过程， 这时式(5)可以转化为式(13)，只需用到两条数据链，即对角度z_i与坐标x_i进 行迭代，这种方式在硬件实现上可以节省约1/3硬件资源，大大提高了FPGA 处理算法的实时性。

$\left(\begin{array}{c}{x}_{i+1}=x_i+d_i{x}_i{2}^{-i}\\ z_{i+1}=z_i-d_i\tan h^{-1}{2}^{-i}\\ d_i=\mathrm{sign}\left(z_i\right)\end{array}\right),i=\mathrm{1,2,3},...,n---\left(13\right)$

图6为CORDIC算法指数函数在Modelsim的仿真图。采用15级流水 线CORDIC算法结构，输入定点化参数[z_in·2¹⁶]，其中z_in∈[-8,8]。图中斜线 为输入z_in值，曲线为对应的指数函数值输出，垂直的线为光标线，此时光标 位置对应的输入值1，输出值为e¹≈2.71823，与理论值2.71828相比，相对 误差为

表3列出了收敛域z_in∈[-8,8]部分输入值的运算结果，可以看出，当输 入值z_in<0时，其绝对误差很小，达到10^-4，当输入值z_in>0时，其相对误差 很小，达到10^-4。

表3

收敛域z_in∈[-8,8]部分输入值的FPGA运算结果

虽然本发明所揭露的实施方式如上，但所述的内容只是为了便于理解本 发明而采用的实施方式，并非用以限定本发明。任何本发明所属技术领域内 的技术人员，在不脱离本发明所揭露的精神和范围的前提下，可以在实施的 形式上及细节上作任何的修改与变化，但本发明的专利保护范围，仍须以所 附的权利要求书所界定的范围为准。