一种基于稀疏矩阵的多核并行扰码方法

摘要：针对多核环境中高速无线信号的加扰、解扰，提出了一种基于稀疏矩阵的多核并行扰码方法。首先对输入信号进行串／并转换，并将各路信号分别送入对应的处理器核；考虑基于稀疏矩阵的并行扰码生成器，在单个处理器核内，将其生成的伪随机码与输入信号进行模二加运算，得到单路信号的扰码输出；最后将多路并行的扰码输出变换为串行输出。运算量分析结果表明，采用IEEE 802．11n中的扰码生成多项式，与普通矩阵乘法实现的多核并行扰码方法相比，基于稀疏矩阵的多核并行扰码方法，其运算量降低了一个数量级。
关键词：稀疏矩阵；多核；并行扰码；运算量

0 引言
    无线通信速率的不断提高，要求无线通信设备的处理速度不断提高。未来无线通信设备处理速度的提高不仅依赖于单处理器处理速度的提高，更主要是依赖于片上处理器核数量的增加。因而，多核处理器被广泛应用在无线通信信号处理中。
    加扰、解扰是无线通信信号处理中的重要环节。随着无线通信速率的提高，串行扰码对硬件处理速度的要求越来越高。针对高速信号的加扰、解扰，串行扰码不再适用。因此，文献提出了矩阵法实现的并行扰码方法，首先将串行的高速信号转换为并行的低速信号，再利用扰码生成器产生的多个并行相位，同时对输入并行信号进行扰码处理。其中，扰码生成器是基于线性反馈移位寄存器的状态转移矩阵实现的。文献提出了用查表法实现的并行扰码方法，并行扰码的步骤与文献一致，但其扰码生成器是基于伪随机序列存储表实现的。与用矩阵法实现的并行扰码方法相比，该方法的运算量小，存储量大。文献改进了并行扰码方法的FPGA结构，在该结构中，各路并行扰码输出的路径时延均仅由一个D触发器和一个异或门构成，该结构对高速信号处理具有很强的适应性。在文献的基础上，文献进一步改进了并行扰码的FPGA结构，
与文献的结构相比，在保证输出路径时延不变的条件下，该结构减少了寄存器的使用数量。
    针对多核环境中的高速无线信号，本文提出一种基于稀疏矩阵的多核并行扰码方法。该方法应用稀疏矩阵的存储及运算，产生了并行输出的伪随机码，并实现了多核的并行加扰、解扰。

1 系统模型
    基于稀疏矩阵的多核并行扰码无线收发机通信链路如图1所示。发射机对比特流b(i)进行基于稀疏矩阵的多核并行加扰，具体步骤为：首先对输入信号进行串／并转换，将N路信号分别送入对应序号的处理器核，在单个处理器核内，对输入信号进行加扰处理；然后将N路并行扰码输出经过并／串转换得到d(i)。d(i)经过调制，产生发射信号s(t)。发射信号经过无线信道到达接收机。接收机对接收信号r(t)进行信道均衡，得到发射信号s(t)的估计值；然后解调得到比特流d(i)的估计值；最后经过基于稀疏矩阵的多核并行解扰恢复出比特流b(i)的估计值。多核的并行解扰步骤与加扰步骤类似，这里不再赘述。

1．1 基于稀疏矩阵的多核并行扰码
    基于稀疏矩阵的多核并行扰码结构如图2所示。基于稀疏矩阵的并行扰码生成器产生了伪随机序列q，且同时输出序列q中N个相邻的伪随机码。此外，输入信号b(i)经过串／并转换后得到N路并行信号，然后分别送入对应序号的处理器核，在单个处理器核内，生成的伪随机码与输入信号进行模二加运算，得到输入信号的扰码输出；最后，并行扰码输出经过并／串转换得到串行扰码输出d(i)。

    图2中q(i)表示伪随机序列的第i个元素；k为非负整数；加法器表示模二加运算，则第i时刻扰码输出d(i)的数学表达式为：
    d(i)=b(i)⊕q(i)       (1)
    从图2及式(1)可以看出，基于稀疏矩阵的并行扰码生成器是加扰，解扰过程中的重要组成部分。接下来详细介绍如何实现基于稀疏矩阵的并行扰码生成器。
    假设并行扰码生成器输出的伪随机序列q为m序列，则q可由r级线性反馈移位寄存器产生，且其循环周期L=2r-1。r级线性反馈移位寄存器的生成多项式可写为：
   
    式中c(n)取值为0或1。
    以式(2)作为生成多项式，图3给出了相应的r级线性反馈移位寄存器结构。

    图中，q(i)表示第i时刻生成的伪随机码；fn代表寄存器；cn代表乘法器，加法器表示模二加运算，则i时刻的线性反馈移位寄存器状态为：
    Fi=[f1i，f2i，…，fri]T     (3)
    下一时刻，线性反馈移位寄存器的状态为：
   
    式中：r阶方阵T为r级线性反馈移位寄存器的状态转移矩阵；Ir-1表示r-1阶单位矩阵；C表示生成多项式的系数向量，如式(6)所示；φ表示r-1维全零列向量。
    C=[c1，c2，…，cr-1]        (6)
    如图2所示，为了利用伪随机码q(i)对输入信号进行N路并行扰码，要求扰码生成器同时给出N路并行输出。在一个并行周期后，线性反馈移位寄存器的状态由Fi转换至Fi+N。
    Fi+N=TNFi       (7)
    容易看出，式(7)所示的矩阵乘法运算完全等价于图3中线性反馈移位寄存器进行N次状态转换的结果，即该运算可实现一个N路并行扰码生成器，每个并行周期产生伪随机序列q的N路并行输出，同时将状态向量从Fi更新至Fi+N。考虑N≤r的情况，{f(r-N+1)i，f(r-N+2)i，…，fri}即为并行扰码生成器的输出向量。
    如式(5)所示，由于状态转移矩阵T包含了r-1阶的单位矩阵以及r-1维全零列向量，不失一般性，且假设TN为稀疏矩阵。本文采用稀疏矩阵的存储及实现运算式(7)中的矩阵乘法，进而实现N路的并行扰码生成器，并将其定义为基于稀疏矩阵的并行扰码生成器。
1．2 稀疏矩阵的存储及运算
1．2．1 三元组存储
    如式(8)，以IEEE 802．11n使用的扰码生成多项式为例，说明如何利用稀疏矩阵的存储及运算实现并行的扰码生成器。

    根据稀疏矩阵的三元组存储结构，将状态转移矩阵A存储为(i，j，aij)的形式，如图4所示。图中i表示行数，j表示列数，aij表示A中位于第i行第j列的元素。矩阵相乘时，矩阵A左乘列向量Fi，为方便对A进行遍历，在进行A的三元组存储时，先以行序号由小到大排列，同一行中再以列序号由小到大排列。

    同理，并行扰码生成器在i时刻的状态向量Fi也可以写为三元组的形式。值得注意的是，由于Fi是列向量，其三元组形式中的列序号均为1。
1．2．2 稀疏矩阵相乘
    对状态转移矩阵A、状态向量Fi进行三元组存储后，利用其三元组结构完成两者的矩阵乘法。具体步骤为：首先遍历A的三元组中第一行对应的列序号，若在列向量Fi的三元组中有相同的行序号，则将两个三元组中的对应元素相乘并累加，直至A的三元组中第一行元素遍历完毕，然后将其乘累加结果进行模二运算，再作为Fi+N的第一个数据。以此类推，可以得到一个并行周期后的寄存器状态向量Fi+N，将得到的Fi+N再次进行三元组存储，重复上述步骤，即可实现N路的并行扰码生成器。

2 运算量分析
    由于产生m序列的r级线性反馈移位寄存器能够遍历除全0外的2r-1个状态，不失一般性，且假设寄存器状态向量Fi中每个元素取值1，0的概率都为0．5。在实现并行扰码生成器时，状态转移矩阵A与状态向量Fi进行一次乘法运算后，采用普通矩阵相乘的乘法次数为r2，而采用稀疏矩阵相乘的平均乘法次数为0．5×an，式中an为稀疏矩阵A的非零元素个数。
    由于加扰、解扰的运算量主要来自于并行扰码生成器，如式(8)所示，采用文献中IEEE 802．11n的扰码生成多项式，给出了实现并行扰码生成器时，分别采用普通矩阵乘法与稀疏矩阵乘法的运算量见表1。

    表中，N表示并行支路数，采用文献中IEEE 802．11n的扰码生成多项式，Fi的一次状态转移矩阵T如式(9)所示，则A=TN，r=7。
    从表1可以看出，采用IEEE 802．11n的生成多项式，与普通矩阵乘法实现的多核并行扰码方法相比，基于稀疏矩阵的多核并行扰码方法，其乘法运算量降低了一个数量级。

3 结语
    针对多核环境中的无线通信信号处理，本文提出了一种基于稀疏矩阵的多核并行扰码方法，该方法考虑扰码生成器中状态转移矩阵的稀疏特性，应用稀疏矩阵的运算产生了并行输出的伪随机码，并且利用多个处理器核对输入信号进行并行加扰、解扰。该方法与普通矩阵乘法实现的多核并行扰码相比，其乘法运算量降低了，同时还充分利用多核资源，为在多核环境中实现高速信号的加扰、解扰提供了参考。