CORDIC算法在QR分解中应用讲义.pptVIP

Copyright ?天津大学电子信息工程学院 侯永宏 All Right Reserved Copyright ?天津大学电子信息工程学院 侯永宏 All Right Reserved 可以分解为两步实现 也可以从求角度的观点看这个问题。 * CORDIC算法在QR分解中应用 1.介绍QR分解算法之一——Givens分解法 2.cordic算法实现Givens分解 GIVENS分解 GIVENS矩阵旋转表示为如下形式的矩阵 ii i,k分别表示矩阵 其中i、k代表某次迭代矩阵的元素下标 其中s和c形式分别如下： 令A= GIVENS算法求上三角形矩阵的思想是：GIVENS矩阵G(1,1, )与A矩阵相乘得矩阵B1，再将B1矩阵乘以对应的GIVENS矩阵，直到第一列除最上面元素外全为零为止。此时对得到的矩阵除第一行和第一列外进行相同的运算，然后开始第二次迭代。 第K次迭代后矩阵形式为： 举例：对矩阵A=[-12 3 3;3 1 -2;3 -2 7] 第一次迭代：吉文斯矩阵G1= B1=G1*A= 再对B1进行吉文斯变换:G2= B2=G2*B1= 第二次迭代：对B2的部分 进行GIVENS变换 所以G= ， G* = 综上两次迭代：上三角形矩阵为 R= (-2.7192e-016和-3.5111e-016约为零) 在吉文斯矩阵G与矩阵相乘中反复出现 * = * = 其中 表示迭代过程中的吉文斯矩阵，i、 j表示行数，1 i j n； 分别表示矩阵的第i，j两行，i k n； 设 分别是 两行的元素，展开上式： ? 其中：k n 由?知，吉文斯方法产生上三角形矩阵的过程涉及到大量的乘法、除法、开根方等运算，在计算硬件中运算效率较低。CORDIC算法能用于角度计算旋转操作，可以方便地计算出?的结果,从而使得QR分解变得更有效率。 CORDIC算法原理： 将需要旋转的角度分解成一系列预先设定的基本旋转角度的加权和,使得角度旋转可以通过一系列的移位和加法来实现,避免了复杂的乘法器,从而降低了硬件实现成本。 CORDIC 基本算法 x1 = cos a ? ( x - y tan a ) y1 = cos a ? ( y + x tan a ) x1 = x cos a - y sin a y1 = x sina + y cos a 分解 a=a1+a2+ …+ am 选择am ,使得am = tan-1 2-m 或 tan am = 2-m 方程中乘以 tan am 变成简单的移位操作 将角度旋转关系式 作如下变换 xi+1 = Ki ( xi - yi di 2-i ) yi+1 = Ki ( yi + xi di 2-i ) 第 ith 步,从 (xi, yi)计算 (xi+1, yi+1) 可改写为： 式中 di=sign(zi) 乘积, 为常数取决于迭代的次数和角度 残余的角度为：zi+1 = zi - di tan-1(2-i ) ai = arctan 2-i i ai(弧度） ai(度） 0 ?/4 45 1 0.4637 26.6 2 0.2450 14 3 0.1244 7.1 4 0.0624 3.6 5 0.0312 1.8 6 0.0156 0.9 7 0.0078 0.4 8 0.0039 0.2 9 0.0019 0.1 cordic可以分解为2步 （1）伪旋转 R(i+1)= R(i) (1+tan2 ?(i))1/2 x(i+1)= R(i+1) cos(?+?(i)) = x(i)– y(i) tan?(i) y(i+1)= R(i+1)sin(?+?(i)) = y(i) + x(i) tan?(i) 只考虑角度旋转，不考虑幅度变化 例：将某矢量进行30度的伪旋转 （2）Scaling Operation Scaling operation is used to maintain the “norm” of the original vector P常数，可以优化 Copyright ?天津大学电子信息工程学