Lec2-3 Computer Arithmetic( CORDIC) (2).ppt

实时信号处理系统设计与实现 王明全wmingquan 4 2012 第2章数字系统与代数运算实现 讲授内容安排 1 数字表示定点数 非传统定点数 浮点数2 二进制加法器流水线加法器 模加法器3 二进制乘法器4 二进制除法器线性收敛除法 快速除法器设计5 浮点运算实现定点 浮点格式转换 浮点加 乘 除运算 浮点倒数运算6 MAC和SOP分布式算法7 CORDIC算法 VI MAC和SOP 传统可编程DSP处理方式 1 DSP算法中的乘 累加 Multiply Accumulate MAC 计算非常密集 考虑线性卷积和对于每个采样y n 都需要进行包含L次乘法和L 1次加法的积之和 SumofProducts SOP 计算 在电路结构上对应1个N N位乘法器和1个与之相连接的累加器 采用MAC单元计算内积MAC内部采用N N位乘法器 乘积为2N位字长 若操作数俱为有符号数 乘积有效位为2N 1位 累加器需要增加额外K位来保证足够的动态范围 传统可编程DSP处理方式 2 传统可编程DSP处理方式 3 举例 ADSP21xx内部有1个16 16位阵列乘法器和1个40位 具有额外8位 累加器 可以至少实现28次累加而影响输出精度 如果操作数都是有符号数 就可以进行29次累加 其内部还有1个桶状移位寄存器 用于在一个时钟周期内实现预定格式输出 问题 在定点PDSP中要考虑溢出 并且在实时计算中不希望出现中断 检测和响应累加器溢出会中断数据流 并且会带来显著的时序负担 正确选择保护位的长度可以消除这一负担 分布式运算 DistributedArithmetic DA 分布式运算 DistributedArithmetic DA 是一种重要的FPGA技术 由Croisier于1973年首先提出 广泛用于计算SOP卷积 相关 DFT和RNS逆映射都可以归纳为SOP计算 采用通用乘法器构造MAC计算效率很低 例如 采用传统的运算单元 完成1个滤波器周期 需要N个MAC周期 即使采用流水线收效也不大 DA设计的前提条件若系数c n 已知 则部分乘积项c n x n 由通用乘法变成常系数乘法 缩放 无符号DA系统设计 1 考虑内积假设系数c n 为已知常数 x n 为变量 无符号DA系统假设变量x n 可以表示为 其中xb n 表示x n 的第b位 x n 是x的第n次采样 则内积y可以表示为 无符号DA系统设计 2 重新分布求和次序 有 无符号DA系统设计 3 内积运算的实现用1个LUT实现映射f c n xb n 预先对1个2N字的LUT进行设定 输入为N位向量xb xb 0 xb 1 xb n 1 输出为f c n xb n 对每个LUT输出值f c n xb n 乘以权重2b 用移位 加法器实现累加运算 运算时间为N个LUT周期 无符号DA系统设计 4 移位 加法器DA结构 无符号DA内积举例 1 定义3阶内积 设系数位宽为3 值为c 0 2 c 1 3 c 2 1 实现f c n xb n 的LUT为 无符号DA内积举例 2 对于输入内积值为 验算 无符号DA内积举例 3 在电路设计中 为避免使用筒状移位器 可以采用在每次迭代对累加器的值右移1位来代替对每个中间值移b位的操作 计算迟滞假设LUT和通用乘法器的延迟同为 LUT MUL 则DA系统的计算迟滞为B LUT PDSP的计算迟滞为N MUL 对于较小位宽值B DA设计的速度明显快于基于MAC的设计 有符号DA系统 DA系统如何处理有符号2的补码数有符号2的补码数最高位 MSB 为符号位例如 310 410 010 110 11002c 00002c 00012c 11012c有符号数x n 的 B 1 位表达式为 改造无符号DA结构以适应有符号运算累加器增加加 减控制 LUTROM增加一位输入 有符号DA内积举例 1 对于3阶内积 设输入4位2的补码数系数为c 0 2 c 1 3 c 2 1 实现f c n xb n 的LUT为 有符号DA内积举例 2 x k 的值为 x 0 110 00012C x 1 310 11012C x 2 710 01112C输出为 验算 改进的DA系统结构 1 进行改进的目的降低电路规模当系数的数量N太大而难以用单个LUT实现全字时 LUT的位宽值 系数的个数 可以将LUT划分成几个小LUT进行计算 最后将结果相加 适当引入流水线 不会降低运算速度 但可显著缩小设计的规模 注意 LUT的规模随地址空间 输入数量N 的增加而呈指数放大 假设长度为LN的内积可以由L个独立的N阶并行DALUT实现 规模优化DA系统结构 4NDA系统实现 需要另外增加3个加法器 LUT的规模从24N B降为2N B 改进的DA系统结构 2 提高运算速度以增加LUT 寄存器和加法器为代价 原理 一个执行N阶SOP计算的常规DA结构每一次输入N个字中每一个字的一位 如果一次能输入每个字中两位 则运行速度翻番 如果N的值限制为4或8 DA系统的速度优于所有PDSP VII CORDIC算法 CORDIC算法 1 如何在FPGA设计中实现超越函数 例如 方法1 采用Taylor级数估算方法2 采用CORDIC算法 CORDIC算法 2 CORDIC CoordinateRotationDigitalComputer 算法 亦称逐位法 digit by digitmethod 或Volder算法 是一种计算超越函数的简单高效算法 采用加 减 移位和LUT实现 通常在无硬件乘法器 如微控制器 和可用门资源有限 如FPGA 的情况下使用 CORDIC算法最早由JackE Volder于1956年提出 用于开发B 58战略轰炸机的导航计算机 Convair航空公司 英国数学家HenryBriggs1624年也曾提出过类似算法 HP公司的JohnS Walther进一步扩展了CORDIC算法 使之能够计算双曲函数 指数函数 对数 乘除法和平方根 CORDIC算法在FPGA上的实现最早由UMeyerB se完成 1995年 笛卡尔坐标平面旋转 在xy坐标平面上将点 x1 y1 旋转角度 到点 x2 y2 的标准方法如下所示 这种旋转被称为平面旋转 向量旋转或者是线性 矩阵 代数中的Givens旋转 笛卡尔坐标平面旋转 上面的方程组同样可写成矩阵向量形式 90o相移为 伪旋转 通过提出因数cos 方程可写成下面的形式 如果去掉cos 项 得到伪旋转方程式 即旋转的角度是正确的 但是x和y的值增加cos 1 倍 由于cos 1 1 所以模值变大 注意 并不能通过适当的数学方法去除cos 1 项 然而去除cos 项可以简化坐标平面旋转的计算操作 伪旋转 CORDIC算法 CORDIC算法的核心是 伪 旋转角度 其中tan i 2 i 故方程为 CORDIC算法中每次迭代 i 的旋转角度表 精确到9位小数 CORDIC算法 在CORDIC算法中 把变换改成了迭代算法 将各种可能的旋转角度加以限制 使得对任意角度 的旋转能够通过一系列连续小角度的旋转迭代i来完成 旋转角度遵循法则 tan i 2 i 遵循该法则 乘以正切项转变成了移位操作 前几次迭代的形式为 第1次迭代 旋转45o第2次迭代 旋转26 6o第3次迭代 旋转14o 注意 每次旋转的方向都影响到最终要旋转的累积角度 在 99 7o 99 7o的范围内的任意角度都可以旋转 满足法则的所有角度的总和tan i 2 i为99 7 对于该范围之外的角度 可使用三角恒等式转化成该范围内的角度 角分辨率的数据位数与最终的精度有关 1 0607252941 1 6467602 因此 在13次旋转后 为了标定伪旋转的幅度 要求乘以一个系数1 64676024187 角分辨率的数据位数对最终的旋转精度非常关键 角度累加器 对于每一次迭代 伪旋转可表示为 其中di 1 为判决算子 用于确定旋转的方向是顺时针还是逆时针 di的值取决于操作模式 引入第三个方程 角度累加器方程 用于在每次迭代过程中追踪累加的旋转角度 上述三个方程式为圆周坐标系中用于角度旋转的CORDIC算法的表达式 移位 加法算法 原始的算法现在已经被减化为使用向量的伪旋转来表示的迭代移位 相加算法 每次迭代需要进行 2次移位1次查找表 查询 i 值 3次加法进行迭代移位 相加的前提是去掉cos 项 移位 加法算法 伸缩因子 伸缩因子 也称增益因子 是伪旋转的副产物 当简化算法允许伪旋转时 cos 项被忽略 这样输出的x n y n 被伸缩Kn倍 如果迭代次数可知 则可以预先计算伸缩因子Kn和1 Kn 并将1 Kn与x n 和y n 相乘 来校正x n 和y n 的最终真值 旋转模式 CORDIC方法有两种操作模式 操作模式决定了控制算子di的条件 旋转模式 向量 x 0 y 0 0 0 通过旋转使得角度寄存器值z n 迭代收敛为0 旋转角z 0 已知 计算向量旋转后的最终的坐标 X n Y n t选择di sign z i z i 0 n次迭代后得到 通过设置x 0 1 Kn和y 0 0可以计算cosz 0 和sinz 0 旋转模式 举例 当z 0 30o时 计算sinz 0 和cosz 0 向量模式 向量模式 向量 x 0 y 0 0 0 通过旋转使得y n 迭代收敛为0旋转角 未知 z 0 0 选择di sign x i y i y i 0 n次迭代后得到 通过设定x 0 1和z 0 0来计算tan 1z 0 向量模式 举例 当y 0 2并且x 0 1时 计算tan 1 y 0 x 0 圆坐标系 在圆坐标系中 可以利用CORDIC算法计算下列函数 若采用其它的坐标系 可以利用CORDIC算法计算更多的函数 如乘 除法 线性坐标系和双曲坐标系 线性坐标系 双曲坐标系 线性坐标系和双曲坐标系 采用其它坐标系的CORDIC算法的优点是可以计算更多的函数 而缺点则是系统将变得更加复杂 当把CORDIC算法用于线性或双曲坐标系时 在圆周坐标系中的旋转角度集将不再有效 而采用其它的两种旋转角度集 可以推导出可在3个坐标系中表示CORDIC方程的通用公式 在该方程式中引入两个新变量 变量 表示选用何种坐标系 变量e i 表示在相应的坐标系中旋转的角度集 通用的CORDIC方程 CORDIC方程可被归纳到包括圆 线性和双曲等三个坐标系中 圆周旋转线性旋转双曲旋转 CORDIC函数计算 CORDIC函数计算 当把CORDIC算法用于线性旋转时 伸缩因子K0与圆周旋转的伸缩因子K不同 K0 1 当把CORDIC算法用于双曲旋转时 伸缩因子K 与圆周旋转的伸缩因子K不同 双曲伸缩因子K 使用下列方程计算 CORDIC计算超越函数 CORDIC算法几乎可以计算所有的超越函数 正确选择初始值 能直接计算函数X Y Y X sin Z cos Z tan 1 Z sinh Z cosh Z tanh Z 其它的函数计算 尽管CORDIC算法仅能够直接计算少量的函数 但更多的函数可以通过间接的方法来获得 举例 计算tanz首先 在圆旋转模式中采用CORDIC算法直接计算cosz和sinz 然后 将cosz和sinz的值回馈到系统中 使用线性矢量模式 并用前者除以后者 得到tanz 其它的函数计算 其它的函数可以通过选择适当的初始化 将多种操作模式组合计算而得 其它的函数计算 精度和收敛性 在三角函数中 k位的精度要求k次迭代 使用 99 7o z 99 7o范围内的角度 圆周和线性CORDIC一定收敛 对于该范围之外的角度 需要使用标准三角恒等式 使用双曲CORDIC时 旋转不一定收敛 如果重复某些迭代 CORDIC将收敛 i 4 13 40 k 3k 1 FPGA实现 理想的CORDIC架构取决于具体应用中速率与面积的权衡 可以将CORDIC方程直接综合为迭代型的位并行结构 但是 位并行变量移位器不能很好地被综合到FPGA中 需要多个FPGA逻辑单元 导致设计规模变大 位串行结构最小面积的架构变量移位寄存器的实现 迭代型位串行结构设计 迭代型位串行结构设计 迭代型位串行结构构成 包括3个位串行加 减法器 3个移位寄存器以及一个串行ROM 存放旋转角度 同时需要2个MUX实现可变位移器 每个移位寄存器必须具有与字宽相等的长度 因此每次迭代都需要将该逻辑电路运行w次 w 字宽度 操作首先通过将初值x 0 y 0 和z 0 载入相应的移位寄存器中 数据通过串行加 减法器右移并被返回到移位寄存器的左端 变量移位器通过2个复用器来实现 在每次迭代的初始阶段 两个MUX均被设置为从移位寄存器中读取合适的抽头数据 来自每个MUX的数据被传送到了相应的加 减法器 在每次迭代的开始 x y和z寄存器的符号被读出以便将加 减法器设置到正确的操作模式 在最后一次迭代过程中 结果可直接从加法器 减法器中读取 迭代型位串行结构设计 使用移位寄存器和MUX实现可变移位器 例如 对储存在移位寄存器中的数据执行2 3的移位操作 需要在每次迭代的初始就设定好MUX的选择线 以此来控制需要移位的次数 CORDIC全流水线结构 圆周系统向量化全流水线CORDIC结构实现举例 圆周系统向量化CORDIC结构第一次迭代 向量从II象限旋转到I象限 或者从III象限旋转到IV象限 移位序列为 0 0 1 2 前4个步骤的旋转角度为arctan 90 arctan 2 0 45 arctan 2 1 26 5 arctan 2 2 14 输入和输出为8bit 向量化全流水线CORDIC结构Verilog设计 1 modulecordic clk x in y in r phi eps parameterW 7 Bitwidth 1inputclk input W 0 x in y in output W 0 r phi eps reg W 0 r phi eps Thereisnobitaccessin2Darraytypes inVerilog thereforeusesinglevectorsreg W 0 x0 y0 z0 reg W 0 x1 y1 z1 reg W 0 x2 y2 z2 reg W 0 x3 y3 z3 always posedgeclk begin Inferregisterif x in 0 Testforx in 0rotatebegin 0 90