基于超前迭代的迭代结构QR分解装置及分解方法

摘要

一种基于超前迭代的迭代结构QR分解装置及分解方法，分解装置用来对n×n的矩阵A进行QR分解，它包括三角处理模块、1个对角处理模块、(n‑1)个迭代处理模块；第一多路选择器从外部接收到矩阵A的第一个列向量a

说明书

技术领域

本发明主要涉及到无线通信系统基带信号处理领域，特指一种基于超前迭代的迭代结构QR分解装置及分解方法。

背景技术

正交频分复用(OFDM，orthogonal frequency division multiplexing)技术和多输入多输出技术(MIMO，multiple input multiple output)技术因其具有高频谱利用率和高传输速率得到广泛的关注，近年来关于预编码技术的一系列研究进展使得基于MIMO-OFDM技术的多用户无线通信系统可以实现同时为多个用户服务。然而基于MIMO-OFDM技术的多用户无线通信系统基带信号处理算法计算复杂度大大增加，对基带信号处理器的设计提出了前所未有的挑战。

在基于MIMO-OFDM无线通信系统的基带信号处理链路中，预编码算法和MIMO检测算法是较为复杂的两个基带信号处理算法，近年来得到研究者的广泛关注。1983年，Costa在其经典论文“Writing on dirty paper”(“脏纸编码”)中提出的脏纸编码算法被认为是性能最好的非线性预编码算法，但是其计算复杂度特别高，几乎不可能在硬件电路上实时地执行，2005年Wei Yu等人在其论文“Trellis and Convolutional Precoding for Transmitter-BasedInterference Presubtraction”(“基于网格和卷积预编码的发射机干扰预消除”)中将THP(Tomlinson-Harashima Precoding)算法用于非线性预编码并取得了较好的干扰消除效果，虽然其性能较脏纸编码算法有所降低，但是其计算复杂度大大降低，使得硬件实现非线性预编码算法成为可能，在THP算法中计算复杂度最高的部分是对信道矩阵H执行QR分解的部分，高效快速的QR分解部件有助于提高THP预编码算法整体性能。最大似然估计算法是MIMO检测所有算法中检测精度最高的算法，然而其计算复杂度相当高，因此，M.Shabany等人在“A 0.13μm CMOS 655Mb/s 4×4 64-QAM k-best MIMO detector”(“在0.13μm CMOS工艺下使用64-QAM调制方式时655Mb/s的4×4MIMO检测器设计”)中使用最大似然估计算法的近似算法球形检测(SD)算法进行MIMO检测，取得了很好的检测效果，QR分解作为SD算法的瓶颈之一，制约着其执行速度。

由于QR分解在基于MIMO-OFDM技术的多用户基带信号处理器中得到广泛的应用，且很多情况下是制约处理速度的瓶颈，因此，在很多基带信号处理器的设计中将QR分解作为一个重要的运算部件进行优化。所谓QR分解，就是将n×n的矩阵A分解为n×n的酉矩阵Q和n×n的上三角矩阵R，当前的QR分解算法主要分为三类，分别基于Householder变换、Given旋转以及MGS(modified Gram-Schmidt)算法，由于基于Householder变换的QR分解很难用硬件实现，所 以使用较少，基于Given旋转的QR分解算法虽然大大降低了所使用的硬件资源，但是其所需的执行时间较长，不符合通信系统实时性的要求，基于MGS算法的QR分解因占用硬件资源较少且执行时间较短符合通信系统的实际需求。

有从业者R.-H.Chang等人发表文章“Iterative QR decomposition architecture usingthe modified Gram-Schmidt algorithm for MIMO systems”(“MIMO系统中基于MGS算法的迭代QR分解结构”)，在文章中提出了一种基于MGS算法的迭代结构QR分解硬件电路，完成一个n(n为大于等于2的正整数)阶方阵的QR分解，所提出的迭代结构QR分解电路只需2n-1个时间单元。在具体应用时，使用R.-H.Chang等人提出的迭代结构QR分解电路对一个4×4的矩阵A进行QR分解，对于一个4×4的矩阵，使用基于MGS算法的迭代结构进行QR分解需要七步即可完成，每一步需要一个时间单元，共需要七个时间单元。由此可见，虽然R.-H.Chang等人提出的迭代结构的QR分解方法大大降低了计算时间，但是实际通信系统的基带信号处理中希望得到速度更快的QR分解结构。

发明内容

本发明要解决的技术问题就在于：针对现有技术存在的技术问题，本发明提供一种原理简单、易实现、分解速度快、效率高的基于超前迭代的迭代结构QR分解装置及分解方法。

为解决上述技术问题，本发明采用以下技术方案：

一种基于超前迭代的迭代结构QR分解装置，用来对n×n的矩阵A进行QR分解，它包括三角处理模块、1个对角处理模块、(n-1)个迭代处理模块；第一多路选择器从外部接收到矩阵A的第一个列向量a₁，从第一个迭代处理模块的a_j3^p+1端口接收到信号作为输入，第一多路选择器的输出端口与对角处理模块相连；第二多路选择器从外部接收到矩阵A的第二个列向量a₂，从第二个迭代处理模块的a_j3^p+1端口接收到信号作为输入，第二多路选择器的输出端与第一个迭代处理模块相连；第e1多路选择器从外部接收到矩阵A的第e1个列向量a_e1，其中3≦e1≦n-1，从第e1个迭代处理模块的a_j3^p+1端口接收到信号作为输入，第e1多路选择器的输出端口与第e1-1个迭代处理模块相连；所述对角处理模块的a_j端口以及所有迭代处理模块的a_j^p端口均与第一多路选择器相连，第e1-1个迭代处理模块的a_j3^p端口与第e1多路选择器的输出相连，所有迭代处理模块的r_jj²端口与对角处理模块的r_jj²端口相连，第e4寄存器与第e4+1多路选择器相连，其中1≦e4≦n-2，所有三角处理模块的q_j2端口与对角处理模块的q_j2端口相连，第e5三角处理模块的a_j3端口与第2*e5-1寄存器相连，第e5三角处理模块的a_j3+1端口与第2*e5寄存器相连。

作为本发明分解装置的进一步改进：当n为偶数时，采用n/2个三角处理模块；当n为奇数时，需要(n-1)/2个三角处理模块。

作为本发明分解装置的进一步改进：所述对角处理模块包括一个以上的乘法器、第一加法器、根号运算器以及一个以上的除法器，第e乘法器的两个输入端口均从外部接收a_j向量的第e个元素，其中1≦e≦n，第e乘法器的输出端口与第一加法器相连，第一加法器的输出端口与根号运算器相连，根号运算器的输出端口与第e1除法器相连，其中1≦e1≦n，除法器e1的另一个端口从外部接收a_j向量的第e1个元素。

作为本发明分解装置的进一步改进：所述迭代处理模块包括多路选择器、乘法器、第二加法器、除法器以及减法器，第n+1多路选择器的两个输入分别于外部a_j3^p和第n+1除法器相连，第n+1乘法器到第2*n乘法器与第n+1多路选择器以及外部a_j^p相连，当使能信号为‘0’时，乘法器的输出与第二加法器相连，第二加法器的输出与第n+1除法器相连，当使能信号为‘1’时，乘法器的输出与减法器相连，减法器输出为整个模块的输出信号a_j3^p+1。

作为本发明分解装置的进一步改进：所述三角处理模块包括第n+2多路选择器、第2*n+1乘法器到第3*n乘法器、以及第三加法器，多路选择器的输入为a_j3和a_j3+1，多路选择器的输出与第2*n+1乘法器到第3*n乘法器相连，乘法器的另一个输入为q_j2，乘法器的输出与第三加法器相连，第三加法器的输出为整个模块的输出。

本发明进一步提供一种基于上述分解装置的QR分解方法，其步骤为：

S1：用第一多路选择器选择将A的1个列向量a₁作为对角处理模块的输入，对角处理模块的输出为r₁₁，和q₁，用第k多路选择器选择a_k信号作为第k-1个迭代处理模块的输入，其中2≦k≦n-1；迭代处理模块用于计算下一次的迭代矩阵，其另一个输入为a₁，输出为下一次的迭代矩阵a_j¹，其中j大于等于2小于等于n，并将第k多路选择器输出的信号存放到第k寄存器；

S2～Sj：其中j大于等于2小于n；将第Sj-1步的存储到寄存器中的信号a_j^j-2，……，a_n^j-2以及第j-1步输出的信号q_j-1，a_j^j-1，……，a_n^j-1作为第j步的输入信号，其中a_j^j-1作为对角处理模块的输入，用于计算r_jj和q_j，第三角处理模块的输入信号为q_j-1，a_j3^j-2和a_j3+1^j-2，当n-j为奇数时，j3大于等于j小于等于n-1正整数，当n-j为偶数时，j3为大于等于j小于等于n的正整数，用于计算r_j-1，j3和r_j-1，j3+1，与第一步类似，迭代处理模块用于计算下一次的迭代矩阵，其输入为a_j^j-1，……，a_n^j-1，输出为a_j+1^j，……，a_n^j；

S2n步：将第n-1步寄存器中的a_n^n-2以及第n-1步的输出q_n-1和a_n^n-1作为输入，其中a_n^n-1作为对角处理模块的输入，对角处理模块的输出为r_n，n和q_n，q_n-1和a_n^n-2作为三角处理模块的输入，三角处理模块的输出为r_n-1，n。

与现有技术相比，本发明的优点在于：本发明的基于超前迭代的迭代结构QR分解装置及分解方法，原理简单、易实现，可以显著加快QR分解的速度；对于一个n×n的进行QR分解， 本发明所提结构仅需要n个时间单元即可完成，而使用传统的迭代结构需要2n-1个时间单元，如对于所述的4×4的矩阵A，采用本发明进行QR分解，只需要4个时间单元即可完成，相比7个，少了3个时间单元。

附图说明

图1是本发明分解装置的拓扑结构示意图。

图2是本发明在具体应用实例中对角处理模块的结构原理示意图。

图3是本发明在具体应用实例中迭代处理模块的结构原理示意图。

图4是本发明在具体应用实例中三角处理模块的结构原理示意图。

具体实施方式

以下将结合说明书附图和具体实施例对本发明做进一步详细说明。

如图1所示，本发明基于超前迭代的迭代结构QR分解装置，用来对n×n的矩阵A进行QR分解，它包括：1个对角处理模块，(n-1)个迭代处理模块，三角处理模块，当n为偶数时，需要n/2个三角处理模块；当n为奇数时，需要(n-1)/2个三角处理模块。

第一多路选择器从外部接收到矩阵A的第一个列向量a₁，从第一个迭代处理模块的a_j3^p+1端口接收到信号作为输入，第一多路选择器的输出端口与对角处理模块相连；第二多路选择器从外部接收到矩阵A的第二个列向量a₂，从第二个迭代处理模块的a_j3^p+1端口接收到信号作为输入，第二多路选择器的输出端与第一个迭代处理模块相连；第e1多路选择器(3≦e1≦n-1)从外部接收到矩阵A的第e1个列向量a_e1，从第e1个迭代处理模块的a_j3^p+1端口接收到信号作为输入，第e1多路选择器的输出端口与第e1-1个迭代处理模块相连；对角处理模块的a_j端口以及所有迭代处理模块的a_j^p端口均与第一多路选择器相连，第e1-1个迭代处理模块的a_j3^p端口与第e1多路选择器的输出相连，所有迭代处理模块的r_jj²端口与对角处理模块的r_jj²端口相连，第e4寄存器(1≦e4≦n-2)与第e4+1多路选择器相连，所有三角处理模块的q_j2端口与对角处理模块的q_j2端口相连，第e5三角处理模块的a_j3端口与第2*e5-1寄存器相连，第e5三角处理模块的a_j3+1端口与第2*e5寄存器相连。

在第一个时间单元，所有多路选择器选通外部矩阵A的输入向量，其他时间单元多路选择器选通迭代处理模块输入的信号；在第e2(2≦e2≦n)个时间单元，对角处理模块从第一多路选择器接收到信号，经过处理之后得到r_e2，e2²信号，并将其输出到迭代处理模块，对角模块对从第一多路选择器接收到的信号经过处理得到整个QR分解的输出信号r_e2，e2和q_e2，并将q_e2信号输出到三角处理模块，第e3(1≦e3≦n-1)个迭代处理模块从多路选择器e3+1接收到信号作为输入，从第一多路选择器接收到信号作为输入，并从对角处理模块接收到r_jj²信号作为输入，经过处理之后输出下一次的迭代矩阵的列向量到第e3多路选择器。第e4寄存器， 从第e4+1多路选择器接收到信号，缓存一个时间单元之后输出到三角处理模块，寄存器n从外部接收到矩阵A的第n个列向量a_n作为输入，缓存一个时间单元之后输出到第k个三角处理模块，第e5个三角处理模块从对角处理模块接收到输入信号q_j2，从第2×e5-1寄存器接收到输入信号，经过处理之后得到整个QR分解模块的输出信号r_j2，j3，r_j2，j3+1。

如图2所示，在具体应用实例中，对角处理模块包括一个以上的乘法器、第一加法器、根号运算器以及一个以上的除法器，其中第e乘法器(1≦e≦n)的两个输入端口均从外部接收a_j向量的第e个元素，第e乘法器的输出端口与第一加法器相连，第一加法器的输出端口与根号运算器相连，根号运算器的输出端口与第e1(1≦e1≦n)除法器相连，除法器e1的另一个端口从外部接收a_j向量的第e1个元素。

对角处理模块的工作过程为第e乘法器从外部接收到输入向量a_j的第e个元素，对其进行自乘处理后输出到第一加法器模块，第一加法器从第一乘法器到第n乘法器接收到信号，进行累加处理后输出到根号运算器模块的同时将其作为整个模块的输出信号r_jj²，根号运算器模块从第一加法器接收到信号之后，进行开平方处理后输出到第一除法器到第n除法器作为第一除法器到第n除法器的除数，同时作为整个模块的输出信号r_jj，第e1除法器从外部接收到输入向量a_j的第e1个元素作为被除数，并将从根号运算器接收到的信号作为除数，运算结果作为整个模块输出向量q_j2的第e1个元素。

如图3所示，在具体应用实例中，迭代处理模块包括多路选择器、乘法器、第二加法器、除法器以及减法器，第n+1多路选择器的两个输入分别于外部a_j3^p和第n+1除法器相连，第n+1乘法器到第2*n乘法器与第n+1多路选择器以及外部a_j^p相连，当使能信号为‘0’时，乘法器的输出与第二加法器相连，第二加法器的输出与第n+1除法器相连，当使能信号为‘1’时，乘法器的输出与减法器相连，减法器输出为整个模块的输出信号a_j3^p+1。

迭代处理模块的工作过程为：共享硬件1共包含第n+1多路选择器和第n+1乘法器到第2*n乘法器，第n+1多路选择器为第n+1乘法器到第2*n乘法器选择不同的输入作为乘数，第n+1多路选择器从外部的a_j3^p向量和第n+1除法器的输出信号接收到输入进行选择后输出结果到第n+1乘法器到第2*n乘法器，当使能信号为‘0’时，第e2乘法器e2(n+1≦e2≦2*n)从第n+1多路选择器接收到的信号作为一个乘数，从外部接收的a_j^p向量的第e2个元素作为另一个乘数，进行相乘运算后将结果输出到第二加法器模块，第二加法器模块从第n+1乘法器到第2*n乘法器接收到输入信号，进行累加处理之后输出到第n+1除法器模块，第n+1除法器从第二加法器模块接收到的信号作为被除数，从外部接收到的信号r_jj²作为除数，进行相除运算后输出到第n+1多路选择器的输入，当使能信号为‘1’时，第e2乘法器将运算结果输出到第e3减法器(1≦e3≦n)，第e3减法器从第e2乘法器接收到信号作为减数，从外部 接收到a_j3^p信号的第e3个元素作为被减数，进行相减处理后结果作为整个模块输出信号a_j3^p+1向量的第e3个元素。

如图4所示，在具体应用实例中，三角处理模块包括第n+2多路选择器，第2*n+1乘法器到第3*n乘法器和第三加法器，多路选择器的输入为a_j3和a_j3+1，多路选择器的输出与第2*n+1乘法器到第3*n乘法器相连，乘法器的另一个输入为q_j2，乘法器的输出与第三加法器相连，第三加法器的输出为整个模块的输出。

三角处理模块的工作过程为：第n+2多路选择器的输入分别为a_j3向量的n个元素和a_j3+1向量的n个元素，当多路选择器使能信号为‘0’时，第n+2多路选择器选通a_j3向量的元素输出到第2*n+1乘法器到第3*n乘法器，多路选择器使能信号为‘1’时，第n+2多路选择器选通a_j3+1向量的元素输出到第2*n+1乘法器到第3*n乘法器，乘法器e4从多路选择器接收到的数据作为一个乘数，从外部接收到q_j2向量的第e4个元素作为另一个乘数，进行相乘运算后输出到加法器，第三加法器从第2*n+1乘法器到第3*n乘法器接收到信号之后进行累加运算，当多路选择器使能信号为‘0’时，第三加法器输出信号作为三角处理模块的输出信号r_j2，j3，当多路选择器使能信号为‘1’时，第三加法器输出信号作为三角处理模块的输出信号r_j2，j3+1。

本发明进一步提供一种基于上述分解装置的QR分解方法，其步骤为：

S1：用第一多路选择器选择将A的1个列向量a₁作为对角处理模块的输入，对角处理模块的输出为r₁₁，和q₁，用第k多路选择器(2≦k≦n-1)选择a_k信号作为第k-1个迭代处理模块的输入，迭代处理模块用于计算下一次的迭代矩阵，其另一个输入为a₁，输出为下一次的迭代矩阵a_j¹(j大于等于2小于等于n)，并将第k多路选择器输出的信号存放到第k寄存器。第一步中的各输出信号的值如式(1)所示；

$\begin{array}{c}{r}_{11}=\sqrt{{\left(a_{11}\right)}^2+{\left(a_{21}\right)}^2\mathrm{......}+{\left(a_{n1}\right)}^2}\\ q_{11}=\frac{a_{11}}{r_{11}},\mathrm{......},q_{n1}=\frac{q_{n1}}{r_{11}}\\ a_1^1=0\\ a_2^1=a_2-r_{12}{q}_1=a_2-q_1^T{a}_2{q}_1=a_2-\frac{a_1^T{a}_2{a}_1}{r_{11}^2}\\ \mathrm{......}\\ a_n^1=a_3-\frac{a_1^T{a}_n{a}_1}{r_{11}^2}\end{array}---\left(1\right)$

从第一步可以发现本发明与传统的QR分解方法最大的不同在于，本发明通过当前矩阵的列向量和R矩阵对角元素的平方计算下一次迭代矩阵，而传统的QR分解需要等到R矩阵的行向量计算完成才可以计算下一次的迭代矩阵，因此，本发明超前一步计算出了下一次的迭代 矩阵，本发明通过对传统方法的改进使用第一步的输入计算下一次的迭代矩阵，具有大大提高了QR分解速度的潜力。

S2～S j：其中j大于等于2小于n；将第Sj-1步的存储到寄存器中的信号a_j^j-2，……，a_n^j-2以及第j-1步输出的信号q_j-1，a_j^j-1，……，a_n^j-1作为第j步的输入信号，其中a_j^j-1作为对角处理模块的输入，用于计算r_jj和q_j，第三角处理模块的输入信号为q_j-1，a_j3^j-2和a_j3+1^j-2(当n-j为奇数时，j3大于等于j小于等于n-1正整数，当n-j为偶数时，j3为大于等于j小于等于n的正整数)，用于计算r_j-1，j3和r_j-1，j3+1，与第一步类似，迭代处理模块用于计算下一次的迭代矩阵，其输入为a_j^j-1，……，a_n^j-1，输出为a_j+1^j，……，a_n^j，第j步中各输出如式(2)所示；

$\begin{array}{c}{r}_{j,j}=\sqrt{{\left(a_{1,j}^{j-1}\right)}^2+{\left(a_{2,j}^{j-1}\right)}^2+\mathrm{......}+{\left(a_{n,j}^{j-1}\right)}^2}\\ q_{1,j}=\frac{a_{1,j}^{j-1}}{r_{j,j}},\mathrm{......},q_{n,j}=\frac{a_{n,j}^{j-1}}{r_{j,j}}\\ r_{j-1,j3}=q_{j-1}^T{a_{j3}}^{j-2}\\ =q_{1,j-1}{q}_{1,j3}+\mathrm{......}+q_{n,j-1}{a}_{n,j3},\\ j\le j3\le n;j3\in N\\ \begin{array}{cc}{a}_{i4}^j=a_{i4}^{j-1}-\frac{{\left(a_j^{j-1}\right)}^T{a}_{i4}^{j-1}{a}_j^{i-1}}{r_{jj}^2}& j\le i4\le n;i4\in N\end{array}\end{array}---\left(2\right)$

S2n步：将第n-1步寄存器中的a_n^n-2以及第n-1步的输出q_n-1和a_n^n-1作为输入，其中a_n^n-1作为对角处理模块的输入，对角处理模块的输出为r_n，n和q_n，q_n-1和a_n^n-2作为三角处理模块的输入，三角处理模块的输出为r_n-1，n，第n步中各输出如式(3)所示；

$\begin{array}{c}{r}_{n,n}=\sqrt{{\left(a_{1,n}^{n-1}\right)}^2+{\left(a_{2,n}^{n-1}\right)}^2+\mathrm{......}+{\left(a_{n,n}^{n-1}\right)}^2}\\ q_{1,n}=\frac{a_{1,n}^{n-1}}{r_{n,n}},\mathrm{......},q_{n,n}=\frac{a_{n,n}^{n-1}}{r_{n,n}}\\ r_{n-1,n}=q_{n-1}^T{a}_n^{n-2}\\ =q_{1,n-1}{a}_{1,n}^{n-1}+\mathrm{......}+q_{n,n-1}{a}_{n,n}^{n-2}\end{array}---\left(3\right)$

由上可知，对于一个n×n的进行QR分解，本发明所提结构仅需要n个时间单元即可完成，而使用R.-H.Chang等人提出的迭代结构需要2n-1个时间单元，如对于前述的4×4的矩阵A，采用本发明进行QR分解，只需要4个时间单元即可完成，相比7个，少了3个时间单元。因此，本发明所提基于超前迭代的迭代结构QR分解可以显著加快QR分解的速度。

以上仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通技术 人员来说，在不脱离本发明原理前提下的若干改进和润饰，应视为本发明的保护范围。