CORDIC算法原理及实现.ppt

1、第4章 CORDIC算法原理及实现,何宾 2009.09,本章概述,本章介绍了CORDIC算法的原理，着重介绍了的三个 坐标系及其两种模式下的CORDIC的实现原理，以及迭 代的算法的实现方法。 在此基础上，详细介绍了CORDIC算法在FPGA上的 实现方法及实现过程，并对其性能进行了详细的讨论。,CORDIC简介,坐标旋转数字计算机(Coordinate Rotation Digital Computer，CORDIC)算法可以追溯到1957年由J.Volder发 表的一篇文章。 在上个世纪五十年代，在大型实际的计算机中的实 行移位相加受到了当时技术上的限制，所以使用CORDIC 变得非常必

2、要。到了七十年代，惠普公司和其他公司生产 了手持计算器，许多计算器使用一个内部CORDIC单元来 计算所有的三角函数(那时求一个角度的正切值需要延迟 大约1秒中)。,CORDIC简介,二十世纪八十年代，随着高速度乘法器与带有大存 储量的通用处理器的出现，CORDIC算法变得无关紧要了。 然而在二十一世纪的今天，对于FPGA来说， CORDIC一定是在数字信号处理应用中(比如：多输入多输 出（MIMO），波束形成以及其他自适应系统)计算三角函 数的备选技术。,如图4.1，在xy坐标平面内将点(x1,y1)旋转角度到点 (x2,y2)。其关系用下式表示： （4.1） 这被称为是平面旋转、向量旋转或

3、者线性(矩阵)代数 中的Givens旋转。上面的方程组同样可写成矩阵向量形式：,图4.1 圆坐标系旋转,CORDIC算法原理-圆坐标系旋转原理,CORDIC算法原理-圆坐标系旋转原理,上面的方程组同样可写成矩阵向量形式：,例如一个90o相移为:,通过提出因数cos，式4.1可写成下面的形式：,如果去除项cos，得到伪旋转方程式: （4.5） 如图4.2所示，即旋转的角度是正确的，但是x 与y 的 值增加倍cos(由于cos1，所以模值变大)。,CORDIC算法原理-圆坐标系旋转原理,CORDIC算法原理-圆坐标系旋转原理,图4.2 伪旋转描述,并不能通过适当的数学方法去除cos项 ,然而随后

4、发现去除cos项可以简化坐标平面旋转的计算操作。 CORDIC方法的核心是伪旋转角度，其中tan=2-i。 故方程可表示为： （4.6） 表4.1给出用CORDIC算法中每个迭代(i)的旋转角度 (精确到9位小数),CORDIC算法原理-圆坐标系旋转原理,CORDIC算法原理-圆坐标系旋转原理,表4.1用CORDIC算法中每个迭代(i)的旋转角度,在这里，把变换改成了迭代算法。将各种可能的旋转 角度加以限制，使得对任意角度的旋转能够通过一系列连 续小角度的旋转迭代i来完成。旋转角度遵循法 则： ，遵循这样的法则，乘以正切项变成了移位 操作。 前几次迭代的形式为：第1次迭代旋转45o，第2次迭代

5、 旋转26.6o，第3次迭代旋转14o等。,CORDIC算法原理-圆坐标系旋转原理,CORDIC算法原理-圆坐标系旋转原理,很显然，每次旋转的方向都影响到最终要旋转的累积 角度。在99.799.7的范围内的任意角度都可以旋 转。满足法则的所有角度的总和为99.7。对于该范围之外 的角度，可使用三角恒等式转化成该范围内的角度。当 然，角分辨率的数据位数与最终的精度有关。 cos45xcos26.5xcos14.03xcos7.125xcos0.0139 =0.60725941 10.607252941=1.6467602。因此，在13次旋转以 后，为了标定伪旋转的幅度，要求乘以一个系数 1.64

6、676024187。角分辨率的数据位数对最终的旋转精度 非常关键。,前面所示的伪旋转现在可以表示为（对每次迭代）: (4.7) 在这里引入第三个方程，被称为角度累加器，用来在 每次迭代过程中追踪累加的旋转角度: （4.8） 这里：di=1。符号di是一个判决算子，用于确定旋转的方向。 上述三个方程式为圆周坐标系中用于角度旋转的CORDIC算法的 表达式。在本章的后续部分中我们还将看到CORDIC算法被用于其 它的坐标系，通过使用这些坐标系可以执行更大范围的函数计算。,CORDIC算法原理-圆坐标系旋转原理,伸缩因子是伪旋转的副产物。当简化算法以允许伪 旋转时，cos项被忽略。这样，输出x(n)

7、,y(n)被伸缩Kn 倍，其中: （4.9） 如果迭代次数n可知，则可以预先计算伸缩因子Kn 。 同样,1/ Kn也可被预先计算以得到x(n )和y(n)的真值。 （4.10） 为了简化Givens旋转，我们去除了cos项以执行伪 旋转。然而，该简化引发了负面效应。输出值x(n)和y(n) 被乘以一个因子Kn ，该因子被称为伸缩因子。,CORDIC算法原理-伸缩因子,CORDIC方法有两种操作模式:旋转模式和向量模 式。工作模式决定了控制算子di的条件。在旋转模式中 选择:di=sign(z(i)=z(i)0。n 次迭代后得到: （4.11） 通过设置x(0)=1/Kn和y(0)=0可以计算c

8、osz(0)和 sinz(0)。 旋转模式中，判决算子di满足下面条件: （4.12） 因此，输入x(0)和z(0)(y(0)=0)，然后通过迭代使z(0) 取值趋近于0。,CORDIC算法原理-旋转模式,在向量模式中选择:di =-sign(x(i)y(i)=y(i)0。经过 n 次迭代后，用下式表示： 通过设定x(0)=1和z(0)=0来计算tan-1y(0)。向量模式 中，判决算子di 满足下面条件: 因此 我们输入x(0)和y(0)(z(0)=0)，并通过迭代使y(0) 取值趋近于0。,CORDIC算法原理-向量模式,CORDIC算法原理-向量模式,CORDIC算法的向量模式可以得到输

9、入向量的幅度。 当使用向量模式旋转后向量就与x轴对齐（重合）。因 此，向量的幅度就是旋转向量的x值。幅度结果由Kn增 益标定。,如图4.3，在线性坐标系下迭代的过程可以用下式 表示：,线性坐标系旋转-旋转模式,线性坐标系旋转-旋转模式,在旋转模式中选择:di=sign(z(i)=z(i)0。n 次迭代 后得到: (4.16) 该等式类似于实现一个移位相加的乘法器。,在向量模式中选择:di =-sign(x(i)y(i)=y(i)0。经 过n 次迭代后，用下式表示： （4.17） 这个迭代式可以用于比例运算。在线性坐标系中， 增益是固定值，所以不需要进行标定。,线性坐标系旋转-向量模式,双曲线坐

10、标系旋转- 旋转模式,如图4.4，双曲坐标系下的迭代过程可以用下式表示：,图4.4 双曲线坐标系旋转,在旋转模式中选择:di=sign(z(i)=z(i)0。n 次 迭代后得到: （4.19） 在双曲坐标系下旋转时，伸缩因子K与圆周旋转 的因子有所不同。双曲伸缩因子K*可用下式表示： （4.20） 且：,双曲线坐标系旋转- 旋转模式,在旋转模式中选择:di=-sign(x(i)y(i)=y(i)0。经过n 次迭代后，用下式表示： （4.21） 在双曲坐标系下的坐标变换不一定收敛。当迭代系 数为4，13，40，k，3k+1，时，该系统是收敛的。 根据三角函数之间的关系，下面的函数可以通过 COR

11、DIC算法的计算得到。,双曲线坐标系旋转- 向量模式,双曲线坐标系旋转- 向量模式,根据三角函数之间的关系，下面的函数可以通 过CORDIC算法的计算得到。,从上面可以看出，CORDIC在圆周坐标系、线性坐 标系和双曲线坐标系中，其表达式是非常相似的。可 以给出一个通用的表达式，然后通过选择模式变量就 可以得到CORDIC算法的一般描述。其通用描述式如下 所示： 式中：e(i)是用于给定旋转坐标系内，迭代i次所给出 的旋转的初角。,CORDIC算法一般描述,CORDIC算法一般描述,对于圆坐标系： ； 对于线性坐标系： ； 对于双曲线坐标系： 。 通过该式，就可以用通用的方法来实现CORDIC

12、算 法了。 在三角函数中，k 位的精度要求k 次迭代。使用- 99.7z99.7范围内角度，圆周和线性CORDIC一定收 敛。,理想CORDIC架构取决于具体应用中速率与面积的权 衡。可以将CORDIC方程直接翻译成迭代型的位并行设 计，然而位并行变量移位器不能很好地映射到FPGA中;需 要若干个FPGA单元，导致设计规模变大而设计时间变长。 一次单独的CORDIC迭代所需要的硬件是足够简单的。 然而，为了获得所希望的精确度，需要确定以下两个问题： 需要迭代的次数和需要数据路径的宽度。 Yu Hen Hu设计了一种算法，该算法可以解决 CORDIC迭代中基于总量化误差(Output Quant

13、ization Eroor，OQE)的问题。一旦确定了OQE，即可计算有效小 数位的数目。,CORDIC算法性能分析,Yu Hen Hu提出OQE由两种误差组成： 1近似误差，即CORDIC旋转角度存在有限个基本 角度量化所带来的量化误差。 2舍入误差，即取决于实际实现中使用的有限精确 度的代数运算。 可根据下面的参数来定义上述两种误差：迭代次数 (n)；数据路径中的小数位的位数(b)；最大向量的模值 (|v(0)|)。OQE是上述误差的总和。 使用向量模式时，目标就是通过迭代使向量趋近x轴。 如图4.5，有限次的旋转通常导致余下一个小角度，从 而引起近似误差。,输出量化误差的确定,输出量化误

14、差的确定,图4.6 一次迭代的误差,输出量化误差的确定,输出量化误差的确定,图4.6，说明了只执行1次迭代的例子。模值为1的 向量在开始时的初始角度60。第一次迭代将向量旋转 45，从而导致了=15o的角度量化误差。 对于一次迭 代，其伸缩因子K等于： （4.24） 因此，旋转向量的幅度现为 。x方程给出的值为 。用这个值除以伸缩因子K，得到了真正的量化幅度cos15o。,输出量化误差的确定,上图对应的x方程的输出如下所示。,为了计算近似误差的上界，必须现找出的上界。 Yu Hen Hu 提出的上界为： （4.26） 其中a( 1)为最终的旋转角度。观察图4.7，显然近 似误差为： （4.27

15、）,近似误差的分析,近似误差的分析,图4.7 近似误差的表示,Yu Hen Hu 推导出的舍入误差为： （4.28） 其中： （4.29） （4.30） 式中，b=数据路径中的小数位个数，n =迭代次数。,舍入误差的分析,为了计算有效位的个数deff,必须首先计算OQE。前 面已经提到了OQE的计算方法： OQE =近似误差+舍入误差 因此有效位的个数为： deff =(log2OQE) （4.31） 这种方法求得的deff值依赖于所选择的b和n的值。然而， 希望先指定deff ，然后求出b和n的值。 因此,Yu Hen Hu采用的方法是通过取不同组的b和 n，将计算出的deff值编制成表。通

16、过查表找到所需的 deff ，其对应的b和n即为可知。 使用下面的等式可求得有效小数位的个数: deff = (log2OQE)。,有效位deff的估算,有效位deff的估算,并不是所有计算器都允许计算以2为底的对数运算。 因此,可使用下面的运算来代替：,使用OQE方程，可以计算出一个表，从而对一组n 和b，可以预测出deff。假如输入被限制在0.5的范围 内，那么|v(0)| = 0.5。使用|v(0)|的值，对3n 9和8b 10，给定一个deff , deff 表可被用来找出n和b的值。比如 说希望计算带有6个小数位精度的向量幅度。通过查表 4.6（参考书上），能够提供该精确度的最有效的

17、结构是 n=4，b=8。当我们使用这组值设计CORDIC系统时，相 对于浮点设计，最坏情况下的所产生的误差小于2-6。,预测与仿真,下面介绍使用FPGA芯片和Xilinx的System Generator 工具实现CORDIC算法的过程。理想的CORDIC结构取决 于在应用中速度和面积均衡。在FPGA中可以实现的方式 有：循环结构，非循环结构和非循环流水线结构。 循环的方式，即所有的迭代均在一个单元内完成。 图4.8给出了这种实现方式的结构。这种结构内部带有反 馈。在这个结构中，移位寄存器的实现是一个难点。在非 循环的结构中使用的是固定结构的移位寄存器，能适用布 线资源来建立。而循环方式的结构

18、要求的是一个可变位数 的移位寄存器，每个单元乘2-i，表示移位i比特。单个的 cell单元必须能提供所有的i值。这种可变移位寄存器可以 使用桶型移位寄存器（barrel shifter）来实现。,基于System Generator实现CORDIC算法-循环结构的原理,图4.8 循环方式实现迭代,基于System Generator实现CORDIC算法-循环结构的原理,桶型移位寄存器可通过多路复用器来构成。图4.9给 出一个4位桶型移位寄存器的例子。 S0控制桶型移位器的第一列，当S0=0时，输入直接 到输出；S0=1时，移动一位，输入D0D1D2D3，输出 D3D0D1D2。 S1控制桶型移

19、位器的第二列，当S1=0时，输入直接 到输出；S0=1时，移动二位，输入D3D0D1D2，输出 D1D2D3D0。 这个结构非常灵活，可扩展。如果要求8位的桶型移 位寄存器，需要额外的列。阵列向下扩展。,基于System Generator实现CORDIC算法-移位寄存器的设计,基于System Generator实现CORDIC算法-移位寄存器的设计,图4.9 4位桶型移位器的结构,如图4.10，该设计包括3个位串行加法器/减法器、3 个移位寄存器以及一个串行ROM(存放旋转角度)。同 时需要2个复用器以实现可变位移器。本设计中每个移 位寄存器必须具有与字宽相等的长度。因此每次迭代 都需要将

20、该逻辑电路运行w次(其中w =字宽度)。,基于System Generator实现CORDIC算法-迭代位-串行移位寄存器,基于System Generator实现CORDIC算法-迭代位-串行移位寄存器,图4.10 迭代位-串行设计的实现结构,首先通过将初值x(0),y(0)和z(0)装入相关的移位寄存器 中来运行。因此,数据通过加法器/减法器右移并被返回到 移位寄存器的左端。变量移位器通过2个复用器来实现。 在每个迭代的初始阶段，两个复用器均被设置为从移位寄 存器中读取合适的抽头数据。来自每个复用器的数据被传 送到了合适的加法器/减法器。在每次迭代的开始，x ,y和 z寄存器的符号被读出以便将加法器加法器设置到正确 的操作模式。在最后一次迭代过程中，结果可直接从加法 器/减法器中读取。,基于System Generator实现CORDIC算法-迭代位-串行移位寄存器,基于System Generator实现CORDIC算法-迭代位-串行移位寄存器,图4.11给出了使用移位寄存器和复用器实现可变移 位器的过程。图中所示对储存在移位寄存器中的数据执 行2-3的移位操作。 显然需要在每个迭代的初始就设定 好多路复用器的选择线，这将能够