一種類正交矩陣產(chǎn)生方法

單俠芹，潘 洋，殷奎喜，趙 華

（南京師范大學(xué) 物理科學(xué)與技術(shù)學(xué)院，江蘇 南京 210046）

0 引言

CDMA在CDMA通信系統(tǒng)中，它的用戶編碼采用的是一個PN偽隨機(jī)序列，常用的偽隨機(jī)碼有m序列碼、gold碼、截?cái)啻a等。但一般偽隨機(jī)（PN）序列采用的本原多項(xiàng)式通常最高次數(shù)為42，本原多項(xiàng)式有限，限制了用戶數(shù)量[1]。

CDMA系統(tǒng)采用walsh矩陣作為它的信道編碼。walsh矩陣的每一行（或列）都是正交碼組[2]。

m序列、gold序列和walsh序列是目前CDMA系統(tǒng)中廣泛采用的擴(kuò)頻序列[3]。m序列和gold序列具有正交性差、可用碼組少的特點(diǎn)；walsh序列是由哈達(dá)碼矩陣（H矩陣）擴(kuò)展而來，所以walsh矩陣大小只能是2的指數(shù)次方，不可能是任意值，且由于H矩陣的大小有限（n≤200內(nèi)除去n=188），所以以上三種擴(kuò)頻序列都限制了 CDMA系統(tǒng)的用戶數(shù)目。所以可以用類正交矩陣代替他們應(yīng)用到CDMA、多載波碼分多址（MC-CDMA）和測距等系統(tǒng)中。

1 窮舉法

窮舉法也叫枚舉法或列舉法[2]。在研究對象是由有限個元素構(gòu)成的集合時，把所有對象一一列舉出來，再對其一一進(jìn)行試驗(yàn)，找出符合條件的解的方法。這里所研究的對象（元素）可以是各個個體事物，也可以是構(gòu)成研究對象的各類事物，在這里所研究的對象是類正交矩陣。

對于許多毫無規(guī)律的問題而言，窮舉法用時間上的犧牲換來了解的全面性保證，尤其是隨著計(jì)算機(jī)運(yùn)算速度的飛速發(fā)展，窮舉法的形象已經(jīng)不再是最低等和原始的無奈之舉，比如經(jīng)常有黑客在幾乎沒有任何已知信息的情況下利用窮舉法來破譯密碼，足見這種方法還是有其適用的領(lǐng)域的。

2 類正交矩陣

在一個矩陣中，設(shè)各個碼組長度為n，每個碼元只取+1和-1，x和y是該矩陣中的兩個碼組：

其中，xi,yi∈(+1,?1),i=1,2,…,n，則x和y間的互相關(guān)系數(shù)[4]定義為：

若碼組x和y完全正交，則必有ρ(x, y)=0，說明碼組間不相關(guān)；若x和y不完全正交，則ρ(x, y)≠ 0，說明x和y之間具有一定的相關(guān)性，稱x和y為類正交；若碼組x和y完全相同，則ρ(x, y)=1，說明碼組具有很好的自相關(guān)特性[5]。由此可見，若碼組x和y的相關(guān)系數(shù)ρ(x, y)越小，說明它們的互相關(guān)性越弱；若碼組x和y的相關(guān)系數(shù)ρ(x, y)越大，說明它們的相關(guān)性越強(qiáng)[6]。

由r個“0”和“1”組成的碼組共有2r種可能，因?yàn)槿?”和只有一個“1”的碼組所含的信息量太少，除去全“0”行和只包含一個“1”的可能，剩下2r?r?1種可能，由這2r?r?1種可能組成一個矩陣，即原始矩陣w，但是該矩陣的每行之間并不一定正交或是滿足相關(guān)值ρ∈ (?1，1)，部分序列的相關(guān)性如圖1所示。

圖1 部分篩選后的類正交矩陣的相關(guān)系數(shù)

由圖1可以看出，有一部分行向量之間的互相關(guān)系數(shù)值比較大，這說明在矩陣中存在一部分互相關(guān)性較差的行向量。在實(shí)際使用中，利用類正交矩陣的類正交特性，可以將矩陣中的行向量作為用戶編碼或信道編碼應(yīng)用于 CDMA等通信系統(tǒng)[7]，如果作為編碼的行向量之間的互相關(guān)性較強(qiáng)，則會嚴(yán)重影響解碼后恢復(fù)出的各路用戶信號的效果。所以需要將原始矩陣w經(jīng)過根據(jù)窮舉法設(shè)計(jì)的算法進(jìn)行篩選，從而篩選出互相關(guān)系數(shù)較小，即正交性較好的行向量作為多址通信中的用戶編碼。但是，經(jīng)過篩選之后，雖然得到了具有更好正交性的矩陣，但是由于剔除了一些互相關(guān)系數(shù)大的行向量，所以由篩選后的向量組成的矩陣的大小將會變小，也就是可用于編碼的序列的數(shù)量變少了，這也限制了可接入系統(tǒng)的用戶的數(shù)量。

3 類正交矩陣的產(chǎn)生

這里介紹一種運(yùn)用窮舉法得到滿足條件的正交或類正交矩陣的算法。首先，根據(jù)第2部分的描述產(chǎn)生原始矩陣，具體步驟如下：

①產(chǎn)生2r所有可能的碼組，將其保存到矩陣w中，即得到r×r的矩陣；

②篩選：刪除全“0”和只有一個“1”的碼組；

③數(shù)值轉(zhuǎn)換：用 “-1”代替原碼組中二進(jìn)制數(shù)字“0”，用“+1”代替原碼組中的二進(jìn)制數(shù)字“1”，這樣得到原始矩陣w。

其次，運(yùn)用窮舉法設(shè)計(jì)算法，從原始矩陣中找到滿足要求的正交或類正交矩陣，框圖如圖2所示。

圖2 正交或類正交矩陣的產(chǎn)生框

其中應(yīng)用窮舉法進(jìn)行篩選的算法描述如下：采用最大似然準(zhǔn)則判決法，將閾值（即相關(guān)值）設(shè)置為 0，即σ=0，則得到的矩陣即為完全正交陣，若將閾值設(shè)置為某個非常接近0的值（?1＜σ ＜1），則可得到相應(yīng)的類正交陣。這里假設(shè)σ=0，得到的矩陣都為完全正交的矩陣，若想得到類正交陣，只需改變閾值即可。

具體步驟如下所述：

①以原矩陣w的第一行為例，按照式（1）計(jì)算第2～n行與該行的互相關(guān)系數(shù)ρ，記錄下ρ=0的行，并將其行號保存到矩陣w1中；

②以w1矩陣的第一個元素所記錄的行號為原矩陣的第一行，重復(fù)步驟①搜索與該行相關(guān)系數(shù)不滿足給定值的行，并從w1矩陣中刪除該行，此時i的范圍為[1,m?1]；

③根據(jù)步驟②得到的新矩陣 w1，重復(fù)步驟②，直到m＜2；

④以w1矩陣中的第i個元素值為原矩陣的第一行，重復(fù)步驟②～③可以得到新的一組正交矩陣M；

⑤重復(fù)步驟①～④，得到不包含第 i（i∈[1,n-1]）行之前所有行的正交矩陣。

其中n=2r-r-1，m為計(jì)算所得的w1矩陣大小。

根據(jù)上面算法得到的矩陣中任意碼組之間的相關(guān)系數(shù)都為0，即碼組之間是兩兩正交。現(xiàn)把這種兩兩正交的碼組所組成的矩陣稱為正交矩陣。若改變閾值σ的大小，使相關(guān)系數(shù)在(0,1)之間，則得到的矩陣為類正交矩陣。下面分別為不同閾值和r大小不同時得到的部分正交陣M和類正較陣M。

設(shè)r=7，閾值為1/r時，通過窮舉法得到的部分類正交矩陣如表1所示，表中的數(shù)據(jù)都是十六進(jìn)制，每一行都是一個類正交矩陣M。

表1 r=7時的部分類正交矩陣

其中第一行所表示的二進(jìn)制類正交矩陣如表2所示。

表2 表1中第一行所表示類正交矩陣M

設(shè)r=7，閾值為0時，通過窮舉法得到的部分完全正交矩陣如表2所示，同表1、表3中的數(shù)據(jù)也都是十六進(jìn)制，每一行都是一個正交矩陣M。

表3 r=8時閾值為0得到的部分正交陣

表1和表3只是篩選出的部分類正交矩陣和部分正交矩陣，拒不完全統(tǒng)計(jì)，當(dāng)r=8，閾值為1/r時，能夠得到的符合條件的類正交矩陣數(shù)量n?100，矩陣大小最大為8×7。

對于傳統(tǒng)的walsh矩陣而言，其行向量或者列向量的個數(shù)總是2的指數(shù)次方[8]，不可能出現(xiàn)非2的指數(shù)次方的矩陣。表1產(chǎn)生的類正交矩陣，與Walsh矩陣類似的正交性，具有良好的自相關(guān)和互相特性，但是它們的矩陣的大小和數(shù)量由互相關(guān)系數(shù)的大小和碼長確定，不再受到2的指數(shù)次方的限制；同樣碼長的矩陣比WALSH矩陣有更多碼組，具有相似相關(guān)性的矩陣數(shù)量隨著碼長和互相關(guān)系數(shù)的不同而不同，碼長越長、互相關(guān)系數(shù)越大長符合條件的類正交矩陣越多，可以隨機(jī)選擇其中的任意一個作為 CDMA的用戶編碼，增加擴(kuò)頻序列的不確定性。

4 結(jié)語

提出一種用窮舉法產(chǎn)生類正交矩陣的方法，并對該方法進(jìn)行了闡述和分析。并比較了它和WALSH矩陣的區(qū)別，與WALSH矩陣相比有了很大的改進(jìn)，所以很多應(yīng)用 WALSH矩陣的地方都可以用類正交矩陣來代替。另外，如果要求篩選出的矩陣之間完全正交，即在下一步篩選之前從原矩陣中剔除已篩選出的矩陣，這樣篩選出的矩陣可以應(yīng)用到各個不同的小區(qū)或不同的“物體”上，保證了小區(qū)之間不受影響，如物聯(lián)網(wǎng)、蜂窩網(wǎng)等。

[1] 王玉德，王金新.基于MATLAB的調(diào)頻擴(kuò)頻通信系統(tǒng)的仿真研究[J].通信技術(shù)，2010，43（06）：21-23.

[2] 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社，2005：86-113.

[3] 張治元，蔣清泉，宋燕輝.TD-SCDMA系統(tǒng)擾碼規(guī)劃算法及仿真[J].通信技術(shù)，2010，43（06）：176-178.

[4] 樊昌信，曹麗娜.通信原理[M].北京：國防工業(yè)出版社，2007.

[5] WELCH L R.Lower Bounds on the Maximum Cross Correlation of signals[J].IEEE Transactions on Inform, Theory, 1974, 20(05):397-399.

[6] 査艷芳.多維類正交偽隨機(jī)矩陣及其擴(kuò)展[D].南京：南京師范大學(xué)，2010.

[7] Roy Blake.現(xiàn)代通信系統(tǒng)[M].北京：電子工業(yè)出版社，2003.

[8] WILIANMSON J.Hadamard’s Determinant Theorem and the Sum of Four Squares[J].Duke Mathematical, 1944(11):65-81.