一種基于稀疏矩陣的多核并行擾碼方法

摘要：針對多核環(huán)境中高速無線信號的加擾、解擾，提出了一種基于稀疏矩陣的多核并行擾碼方法。首先對輸入信號進(jìn)行串／并轉(zhuǎn)換，并將各路信號分別送入對應(yīng)的處理器核；考慮基于稀疏矩陣的并行擾碼生成器，在單個處理器核內(nèi)，將其生成的偽隨機碼與輸入信號進(jìn)行模二加運算，得到單路信號的擾碼輸出；最后將多路并行的擾碼輸出變換為串行輸出。運算量分析結(jié)果表明，采用IEEE 802．11n中的擾碼生成多項式，與普通矩陣乘法實現(xiàn)的多核并行擾碼方法相比，基于稀疏矩陣的多核并行擾碼方法，其運算量降低了一個數(shù)量級。
關(guān)鍵詞：稀疏矩陣；多核；并行擾碼；運算量

0 引言
    無線通信速率的不斷提高，要求無線通信設(shè)備的處理速度不斷提高。未來無線通信設(shè)備處理速度的提高不僅依賴于單處理器處理速度的提高，更主要是依賴于片上處理器核數(shù)量的增加。因而，多核處理器被廣泛應(yīng)用在無線通信信號處理中。
    加擾、解擾是無線通信信號處理中的重要環(huán)節(jié)。隨著無線通信速率的提高，串行擾碼對硬件處理速度的要求越來越高。針對高速信號的加擾、解擾，串行擾碼不再適用。因此，文獻(xiàn)提出了矩陣法實現(xiàn)的并行擾碼方法，首先將串行的高速信號轉(zhuǎn)換為并行的低速信號，再利用擾碼生成器產(chǎn)生的多個并行相位，同時對輸入并行信號進(jìn)行擾碼處理。其中，擾碼生成器是基于線性反饋移位寄存器的狀態(tài)轉(zhuǎn)移矩陣實現(xiàn)的。文獻(xiàn)提出了用查表法實現(xiàn)的并行擾碼方法，并行擾碼的步驟與文獻(xiàn)一致，但其擾碼生成器是基于偽隨機序列存儲表實現(xiàn)的。與用矩陣法實現(xiàn)的并行擾碼方法相比，該方法的運算量小，存儲量大。文獻(xiàn)改進(jìn)了并行擾碼方法的FPGA結(jié)構(gòu)，在該結(jié)構(gòu)中，各路并行擾碼輸出的路徑時延均僅由一個D觸發(fā)器和一個異或門構(gòu)成，該結(jié)構(gòu)對高速信號處理具有很強的適應(yīng)性。在文獻(xiàn)的基礎(chǔ)上，文獻(xiàn)進(jìn)一步改進(jìn)了并行擾碼的FPGA結(jié)構(gòu)，
與文獻(xiàn)的結(jié)構(gòu)相比，在保證輸出路徑時延不變的條件下，該結(jié)構(gòu)減少了寄存器的使用數(shù)量。
    針對多核環(huán)境中的高速無線信號，本文提出一種基于稀疏矩陣的多核并行擾碼方法。該方法應(yīng)用稀疏矩陣的存儲及運算，產(chǎn)生了并行輸出的偽隨機碼，并實現(xiàn)了多核的并行加擾、解擾。

1 系統(tǒng)模型
    基于稀疏矩陣的多核并行擾碼無線收發(fā)機通信鏈路如圖1所示。發(fā)射機對比特流b(i)進(jìn)行基于稀疏矩陣的多核并行加擾，具體步驟為：首先對輸入信號進(jìn)行串／并轉(zhuǎn)換，將N路信號分別送入對應(yīng)序號的處理器核，在單個處理器核內(nèi)，對輸入信號進(jìn)行加擾處理；然后將N路并行擾碼輸出經(jīng)過并／串轉(zhuǎn)換得到d(i)。d(i)經(jīng)過調(diào)制，產(chǎn)生發(fā)射信號s(t)。發(fā)射信號經(jīng)過無線信道到達(dá)接收機。接收機對接收信號r(t)進(jìn)行信道均衡，得到發(fā)射信號s(t)的估計值；然后解調(diào)得到比特流d(i)的估計值；最后經(jīng)過基于稀疏矩陣的多核并行解擾恢復(fù)出比特流b(i)的估計值。多核的并行解擾步驟與加擾步驟類似，這里不再贅述。

1．1 基于稀疏矩陣的多核并行擾碼
    基于稀疏矩陣的多核并行擾碼結(jié)構(gòu)如圖2所示?；谙∈杈仃嚨牟⑿袛_碼生成器產(chǎn)生了偽隨機序列q，且同時輸出序列q中N個相鄰的偽隨機碼。此外，輸入信號b(i)經(jīng)過串／并轉(zhuǎn)換后得到N路并行信號，然后分別送入對應(yīng)序號的處理器核，在單個處理器核內(nèi)，生成的偽隨機碼與輸入信號進(jìn)行模二加運算，得到輸入信號的擾碼輸出；最后，并行擾碼輸出經(jīng)過并／串轉(zhuǎn)換得到串行擾碼輸出d(i)。

    圖2中q(i)表示偽隨機序列的第i個元素；k為非負(fù)整數(shù)；加法器表示模二加運算，則第i時刻擾碼輸出d(i)的數(shù)學(xué)表達(dá)式為：
    d(i)=b(i)⊕q(i)       (1)
    從圖2及式(1)可以看出，基于稀疏矩陣的并行擾碼生成器是加擾，解擾過程中的重要組成部分。接下來詳細(xì)介紹如何實現(xiàn)基于稀疏矩陣的并行擾碼生成器。
    假設(shè)并行擾碼生成器輸出的偽隨機序列q為m序列，則q可由r級線性反饋移位寄存器產(chǎn)生，且其循環(huán)周期L=2r-1。r級線性反饋移位寄存器的生成多項式可寫為：
   
    式中c(n)取值為0或1。
    以式(2)作為生成多項式，圖3給出了相應(yīng)的r級線性反饋移位寄存器結(jié)構(gòu)。

    圖中，q(i)表示第i時刻生成的偽隨機碼；fn代表寄存器；cn代表乘法器，加法器表示模二加運算，則i時刻的線性反饋移位寄存器狀態(tài)為：
    Fi=[f1i，f2i，…，fri]T     (3)
    下一時刻，線性反饋移位寄存器的狀態(tài)為：
   
    式中：r階方陣T為r級線性反饋移位寄存器的狀態(tài)轉(zhuǎn)移矩陣；Ir-1表示r-1階單位矩陣；C表示生成多項式的系數(shù)向量，如式(6)所示；φ表示r-1維全零列向量。
    C=[c1，c2，…，cr-1]        (6)
    如圖2所示，為了利用偽隨機碼q(i)對輸入信號進(jìn)行N路并行擾碼，要求擾碼生成器同時給出N路并行輸出。在一個并行周期后，線性反饋移位寄存器的狀態(tài)由Fi轉(zhuǎn)換至Fi+N。
    Fi+N=TNFi       (7)
    容易看出，式(7)所示的矩陣乘法運算完全等價于圖3中線性反饋移位寄存器進(jìn)行N次狀態(tài)轉(zhuǎn)換的結(jié)果，即該運算可實現(xiàn)一個N路并行擾碼生成器，每個并行周期產(chǎn)生偽隨機序列q的N路并行輸出，同時將狀態(tài)向量從Fi更新至Fi+N?？紤]N≤r的情況，{f(r-N+1)i，f(r-N+2)i，…，fri}即為并行擾碼生成器的輸出向量。
    如式(5)所示，由于狀態(tài)轉(zhuǎn)移矩陣T包含了r-1階的單位矩陣以及r-1維全零列向量，不失一般性，且假設(shè)TN為稀疏矩陣。本文采用稀疏矩陣的存儲及實現(xiàn)運算式(7)中的矩陣乘法，進(jìn)而實現(xiàn)N路的并行擾碼生成器，并將其定義為基于稀疏矩陣的并行擾碼生成器。
1．2 稀疏矩陣的存儲及運算
1．2．1 三元組存儲
    如式(8)，以IEEE 802．11n使用的擾碼生成多項式為例，說明如何利用稀疏矩陣的存儲及運算實現(xiàn)并行的擾碼生成器。

    根據(jù)稀疏矩陣的三元組存儲結(jié)構(gòu)，將狀態(tài)轉(zhuǎn)移矩陣A存儲為(i，j，aij)的形式，如圖4所示。圖中i表示行數(shù)，j表示列數(shù)，aij表示A中位于第i行第j列的元素。矩陣相乘時，矩陣A左乘列向量Fi，為方便對A進(jìn)行遍歷，在進(jìn)行A的三元組存儲時，先以行序號由小到大排列，同一行中再以列序號由小到大排列。

    同理，并行擾碼生成器在i時刻的狀態(tài)向量Fi也可以寫為三元組的形式。值得注意的是，由于Fi是列向量，其三元組形式中的列序號均為1。
1．2．2 稀疏矩陣相乘
    對狀態(tài)轉(zhuǎn)移矩陣A、狀態(tài)向量Fi進(jìn)行三元組存儲后，利用其三元組結(jié)構(gòu)完成兩者的矩陣乘法。具體步驟為：首先遍歷A的三元組中第一行對應(yīng)的列序號，若在列向量Fi的三元組中有相同的行序號，則將兩個三元組中的對應(yīng)元素相乘并累加，直至A的三元組中第一行元素遍歷完畢，然后將其乘累加結(jié)果進(jìn)行模二運算，再作為Fi+N的第一個數(shù)據(jù)。以此類推，可以得到一個并行周期后的寄存器狀態(tài)向量Fi+N，將得到的Fi+N再次進(jìn)行三元組存儲，重復(fù)上述步驟，即可實現(xiàn)N路的并行擾碼生成器。

2 運算量分析
    由于產(chǎn)生m序列的r級線性反饋移位寄存器能夠遍歷除全0外的2r-1個狀態(tài)，不失一般性，且假設(shè)寄存器狀態(tài)向量Fi中每個元素取值1，0的概率都為0．5。在實現(xiàn)并行擾碼生成器時，狀態(tài)轉(zhuǎn)移矩陣A與狀態(tài)向量Fi進(jìn)行一次乘法運算后，采用普通矩陣相乘的乘法次數(shù)為r2，而采用稀疏矩陣相乘的平均乘法次數(shù)為0．5×an，式中an為稀疏矩陣A的非零元素個數(shù)。
    由于加擾、解擾的運算量主要來自于并行擾碼生成器，如式(8)所示，采用文獻(xiàn)中IEEE 802．11n的擾碼生成多項式，給出了實現(xiàn)并行擾碼生成器時，分別采用普通矩陣乘法與稀疏矩陣乘法的運算量見表1。

    表中，N表示并行支路數(shù)，采用文獻(xiàn)中IEEE 802．11n的擾碼生成多項式，F(xiàn)i的一次狀態(tài)轉(zhuǎn)移矩陣T如式(9)所示，則A=TN，r=7。
    從表1可以看出，采用IEEE 802．11n的生成多項式，與普通矩陣乘法實現(xiàn)的多核并行擾碼方法相比，基于稀疏矩陣的多核并行擾碼方法，其乘法運算量降低了一個數(shù)量級。

3 結(jié)語
    針對多核環(huán)境中的無線通信信號處理，本文提出了一種基于稀疏矩陣的多核并行擾碼方法，該方法考慮擾碼生成器中狀態(tài)轉(zhuǎn)移矩陣的稀疏特性，應(yīng)用稀疏矩陣的運算產(chǎn)生了并行輸出的偽隨機碼，并且利用多個處理器核對輸入信號進(jìn)行并行加擾、解擾。該方法與普通矩陣乘法實現(xiàn)的多核并行擾碼相比，其乘法運算量降低了，同時還充分利用多核資源，為在多核環(huán)境中實現(xiàn)高速信號的加擾、解擾提供了參考。