一种类正交矩阵产生方法

单侠芹，潘 洋，殷奎喜，赵 华

（南京师范大学 物理科学与技术学院，江苏 南京 210046）

0 引言

CDMA在CDMA通信系统中，它的用户编码采用的是一个PN伪随机序列，常用的伪随机码有m序列码、gold码、截断码等。但一般伪随机（PN）序列采用的本原多项式通常最高次数为42，本原多项式有限，限制了用户数量[1]。

CDMA系统采用walsh矩阵作为它的信道编码。walsh矩阵的每一行（或列）都是正交码组[2]。

m序列、gold序列和walsh序列是目前CDMA系统中广泛采用的扩频序列[3]。m序列和gold序列具有正交性差、可用码组少的特点；walsh序列是由哈达码矩阵（H矩阵）扩展而来，所以walsh矩阵大小只能是2的指数次方，不可能是任意值，且由于H矩阵的大小有限（n≤200内除去n=188），所以以上三种扩频序列都限制了 CDMA系统的用户数目。所以可以用类正交矩阵代替他们应用到CDMA、多载波码分多址（MC-CDMA）和测距等系统中。

1 穷举法

穷举法也叫枚举法或列举法[2]。在研究对象是由有限个元素构成的集合时，把所有对象一一列举出来，再对其一一进行试验，找出符合条件的解的方法。这里所研究的对象（元素）可以是各个个体事物，也可以是构成研究对象的各类事物，在这里所研究的对象是类正交矩阵。

对于许多毫无规律的问题而言，穷举法用时间上的牺牲换来了解的全面性保证，尤其是随着计算机运算速度的飞速发展，穷举法的形象已经不再是最低等和原始的无奈之举，比如经常有黑客在几乎没有任何已知信息的情况下利用穷举法来破译密码，足见这种方法还是有其适用的领域的。

2 类正交矩阵

在一个矩阵中，设各个码组长度为n，每个码元只取+1和-1，x和y是该矩阵中的两个码组：

其中，xi,yi∈(+1,−1),i=1,2,…,n，则x和y间的互相关系数[4]定义为：

若码组x和y完全正交，则必有ρ(x, y)=0，说明码组间不相关；若x和y不完全正交，则ρ(x, y)≠ 0，说明x和y之间具有一定的相关性，称x和y为类正交；若码组x和y完全相同，则ρ(x, y)=1，说明码组具有很好的自相关特性[5]。由此可见，若码组x和y的相关系数ρ(x, y)越小，说明它们的互相关性越弱；若码组x和y的相关系数ρ(x, y)越大，说明它们的相关性越强[6]。

由r个“0”和“1”组成的码组共有2r种可能，因为全“0”和只有一个“1”的码组所含的信息量太少，除去全“0”行和只包含一个“1”的可能，剩下2r−r−1种可能，由这2r−r−1种可能组成一个矩阵，即原始矩阵w，但是该矩阵的每行之间并不一定正交或是满足相关值ρ∈ (−1，1)，部分序列的相关性如图1所示。

图1 部分筛选后的类正交矩阵的相关系数

由图1可以看出，有一部分行向量之间的互相关系数值比较大，这说明在矩阵中存在一部分互相关性较差的行向量。在实际使用中，利用类正交矩阵的类正交特性，可以将矩阵中的行向量作为用户编码或信道编码应用于 CDMA等通信系统[7]，如果作为编码的行向量之间的互相关性较强，则会严重影响解码后恢复出的各路用户信号的效果。所以需要将原始矩阵w经过根据穷举法设计的算法进行筛选，从而筛选出互相关系数较小，即正交性较好的行向量作为多址通信中的用户编码。但是，经过筛选之后，虽然得到了具有更好正交性的矩阵，但是由于剔除了一些互相关系数大的行向量，所以由筛选后的向量组成的矩阵的大小将会变小，也就是可用于编码的序列的数量变少了，这也限制了可接入系统的用户的数量。

3 类正交矩阵的产生

这里介绍一种运用穷举法得到满足条件的正交或类正交矩阵的算法。首先，根据第2部分的描述产生原始矩阵，具体步骤如下：

①产生2r所有可能的码组，将其保存到矩阵w中，即得到r×r的矩阵；

②筛选：删除全“0”和只有一个“1”的码组；

③数值转换：用 “-1”代替原码组中二进制数字“0”，用“+1”代替原码组中的二进制数字“1”，这样得到原始矩阵w。

其次，运用穷举法设计算法，从原始矩阵中找到满足要求的正交或类正交矩阵，框图如图2所示。

图2 正交或类正交矩阵的产生框

其中应用穷举法进行筛选的算法描述如下：采用最大似然准则判决法，将阈值（即相关值）设置为 0，即σ=0，则得到的矩阵即为完全正交阵，若将阈值设置为某个非常接近0的值（−1＜σ ＜1），则可得到相应的类正交阵。这里假设σ=0，得到的矩阵都为完全正交的矩阵，若想得到类正交阵，只需改变阈值即可。

具体步骤如下所述：

①以原矩阵w的第一行为例，按照式（1）计算第2～n行与该行的互相关系数ρ，记录下ρ=0的行，并将其行号保存到矩阵w1中；

②以w1矩阵的第一个元素所记录的行号为原矩阵的第一行，重复步骤①搜索与该行相关系数不满足给定值的行，并从w1矩阵中删除该行，此时i的范围为[1,m−1]；

③根据步骤②得到的新矩阵 w1，重复步骤②，直到m＜2；

④以w1矩阵中的第i个元素值为原矩阵的第一行，重复步骤②～③可以得到新的一组正交矩阵M；

⑤重复步骤①～④，得到不包含第 i（i∈[1,n-1]）行之前所有行的正交矩阵。

其中n=2r-r-1，m为计算所得的w1矩阵大小。

根据上面算法得到的矩阵中任意码组之间的相关系数都为0，即码组之间是两两正交。现把这种两两正交的码组所组成的矩阵称为正交矩阵。若改变阈值σ的大小，使相关系数在(0,1)之间，则得到的矩阵为类正交矩阵。下面分别为不同阈值和r大小不同时得到的部分正交阵M和类正较阵M。

设r=7，阈值为1/r时，通过穷举法得到的部分类正交矩阵如表1所示，表中的数据都是十六进制，每一行都是一个类正交矩阵M。

表1 r=7时的部分类正交矩阵

其中第一行所表示的二进制类正交矩阵如表2所示。

表2 表1中第一行所表示类正交矩阵M

设r=7，阈值为0时，通过穷举法得到的部分完全正交矩阵如表2所示，同表1、表3中的数据也都是十六进制，每一行都是一个正交矩阵M。

表3 r=8时阈值为0得到的部分正交阵

表1和表3只是筛选出的部分类正交矩阵和部分正交矩阵，拒不完全统计，当r=8，阈值为1/r时，能够得到的符合条件的类正交矩阵数量n≻100，矩阵大小最大为8×7。

对于传统的walsh矩阵而言，其行向量或者列向量的个数总是2的指数次方[8]，不可能出现非2的指数次方的矩阵。表1产生的类正交矩阵，与Walsh矩阵类似的正交性，具有良好的自相关和互相特性，但是它们的矩阵的大小和数量由互相关系数的大小和码长确定，不再受到2的指数次方的限制；同样码长的矩阵比WALSH矩阵有更多码组，具有相似相关性的矩阵数量随着码长和互相关系数的不同而不同，码长越长、互相关系数越大长符合条件的类正交矩阵越多，可以随机选择其中的任意一个作为 CDMA的用户编码，增加扩频序列的不确定性。

4 结语

提出一种用穷举法产生类正交矩阵的方法，并对该方法进行了阐述和分析。并比较了它和WALSH矩阵的区别，与WALSH矩阵相比有了很大的改进，所以很多应用 WALSH矩阵的地方都可以用类正交矩阵来代替。另外，如果要求筛选出的矩阵之间完全正交，即在下一步筛选之前从原矩阵中剔除已筛选出的矩阵，这样筛选出的矩阵可以应用到各个不同的小区或不同的“物体”上，保证了小区之间不受影响，如物联网、蜂窝网等。

[1] 王玉德，王金新.基于MATLAB的调频扩频通信系统的仿真研究[J].通信技术，2010，43（06）：21-23.

[2] 王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2005：86-113.

[3] 张治元，蒋清泉，宋燕辉.TD-SCDMA系统扰码规划算法及仿真[J].通信技术，2010，43（06）：176-178.

[4] 樊昌信，曹丽娜.通信原理[M].北京：国防工业出版社，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] 査艳芳.多维类正交伪随机矩阵及其扩展[D].南京：南京师范大学，2010.

[7] Roy Blake.现代通信系统[M].北京：电子工业出版社，2003.

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