[發明專利]一種非碼本線性預編碼的快速算法

在審

• 申請號: 201811503887.0
• 申請日: 2018-12-10
• 公開（公告）號: CN109743090A
• 公開（公告）日: 2019-05-10
• 發明（設計）人: 李圣春;陳璇;張世龍;劉煉
• 申請（專利權）人: 深圳市海派通訊科技有限公司
• 主分類號: H04B7/0456
• 分類號: H04B7/0456;H04B7/0426;H04B7/06
• 代理公司: 深圳市科吉華烽知識產權事務所(普通合伙) 44248
• 代理人: 孫偉

1.一種非碼本線性預編碼的快速算法，其特征在于，包括以下步驟：

S1、帶位移的QR分解；

S2、SVD奇異值分解與功率注水技術相結合的預編碼方法。

2.根據權利要求1所述的非碼本線性預編碼的快速算法，其特征在于，步驟S1包括以下子步驟：

S11、基本QR分解方法；

S12、一般矩陣的簡化；

S13、擬上三角矩陣的QR算法；

S14、帶位移的QR分解方法。

3.根據權利要求2所述的非碼本線性預編碼的快速算法，其特征在于，步驟S11包括：

令A₀＝A，對k＝1,2,…分解A_k-1＝Q_k-1R_k-1；

令A_k＝R_k-1Q_k-1，其中，Q_k-1為正交矩陣，R_k-1為上三角矩陣；

得到的矩陣序列A_k都相似于A，從而于A有相同的特征值，這是因為A_k-1＝Q_k-1R_k-1，Q_k-1可逆，故從而

在一定條件下矩陣序列A_k基本收斂于分塊上三角矩陣R，

其中對角子塊R₁₁為1x1或2x2矩陣.當R_ii為一階方陣時，R_ii就是A的特征值；當R_ii為二階方陣時，其特征值是一對共軛復數，也是A的特征值。

4.根據權利要求3所述的非碼本線性預編碼的快速算法，其特征在于，步驟S12包括：

先將一般矩陣A簡化為擬上三角矩陣，又稱海森伯格矩陣，即次對角線下方元素全為0的特殊矩陣；

簡化Householder矩陣的過程如下：

H＝I-2uu^T

其中，u是的單位向量，易證它對稱、正定：

H^T＝(I-2uu^T)^T＝I-2uu^T＝H

H^TH＝(I-2uu^T)(I-2uu^T)

＝I-2uu^T-2uu^T+4u(u^Tu)u^T

＝I-4uu^T+4uu^T＝I

因此，向量x的線性變換y＝Hx必保持模不變：||y||₂＝||x||₂，

因此，要用Householder變換把已知向量a＝(a₁ a₂ … a_n)^T變為b＝(a₁ a₂ … a_r c 0… 0)^T，只需令

H＝I-2uu^T

此處c應滿足：

故，

a-b＝(0…0 a_r+1-c a_r+2…a_n)^T

取

則

所以，

對于任意向量，

按上述公式確定的Householder變換把x變為

其中，

把指向向量a的后n-r-1個分量變為0、前n個分量保持不變的Householder變換，施于任意向量x時，前r個分量也保持不變，后n-r個分量則按上述方法計算；

利用這種Householder變換，可將任意矩陣A化為相似的擬上三角矩陣，步驟如下：

作Householder矩陣H₁，使H₁A各列第一個元素不變，但使第一列第二個元素下方各元素變為0，此時，H₁A變成下列形狀：

作矩陣

則因H₁為正交陣，必然有

表明A₁～A且是H₁A用同一Householder矩陣H₁左乘所得矩陣，故第一行不變，A₁第一列不變，從而A的相似矩陣A₁仍具有形如上述H₁A的矩陣形式，再作Householder矩陣H₂，使得H₂A₁各列第一、二個元素不變，即A₁第一、二行不變，但使第二列第三個元素下面各元素變為0，此時第一列第三個元素下方各元素仍變為0，故H₂A₁變成下形：

表明A₂～A₁且是H₂A₁用同一Householder矩陣H₂左乘所得矩陣，因此第一、二行不變，A₂的第一、二列不變，從而A的相似矩陣A₂仍具有形如上述H₂A₁的矩陣形式，如此繼續下去，最多左、右乘n-2次，就將A化成相似的擬上三角矩陣A_n-2。