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

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



關鍵詞：稀疏矩陣； 多核； 并行擾碼； 運算量

中圖分類號：TN914-34

文獻標識碼：A

文章編號：1004-373X(2012)01-0068-03

A parallel scrambling method based on sparse matrix in multicore processors



MA Wan-zhi， WANG Jun， ZHAO Hong-zhi， TANG You-xi

(National Key Lab. of Science and Technology on Communications， UESTC， Chengdu 611731， China)



Abstract：

Considering scrambling and descrambling of high-speed wireless signal in multicore processors， a parallel scrambling method based on sparse matrix in multicore processors is proposed. Firstly， the input signal was passed through deserializer， and fed into specific processor. Then， in the specific processor， the sum modulo two of the input signal and the PN(pseudo-random) code generated by the Parallel Scrambler based on sparse matrix， was acted as the scrambling output of each input signal. At last， all parallel scrambling outputs were passed through serializer， and converted into serial output. By analysis of the calculated amount， using generating polynomial of scrambler in IEEE 802.11n， comparing with parallel scrambling method based on common matrix multiplication in multicore processors， the calculated amount of the parallel scrambling method based on sparse matrix in multicore processors decreased one order of magnitude.



Keywords： sparse matrix; multicore processors; parallel scrambling; calculated amount





收稿日期：2011-08-15

基金項目：國家自然科學基金資助項目(60832007，60901018，60902027，61001087，U1035002/L05)；國家重大科技專項(2009ZX03003-008-01，2010ZX03003-002-01)；中央高校基本科研業(yè)務費專項資金資助項目(ZYGX2009J008)

0 引 言

無線通信速率的不斷提高，要求無線通信設備的處理速度不斷提高。未來無線通信設備處理速度的提高不僅依賴于單處理器處理速度的提高，更主要是依賴于片上處理器核數(shù)量的增加[1]。因而，多核處理器被廣泛應用在無線通信信號處理中。

加擾、解擾是無線通信信號處理中的重要環(huán)節(jié)。隨著無線通信速率的提高，串行擾碼對硬件處理速度的要求越來越高。針對高速信號的加擾、解擾，串行擾碼不再適用。因此，文獻［2］提出了矩陣法實現(xiàn)的并行擾碼方法，首先將串行的高速信號轉換為并行的低速信號，再利用擾碼生成器產(chǎn)生的多個并行相位，同時對輸入并行信號進行擾碼處理。其中，擾碼生成器是基于線性反饋移位寄存器的狀態(tài)轉移矩陣實現(xiàn)的。文獻［3］提出了用查表法實現(xiàn)的并行擾碼方法，并行擾碼的步驟與文獻［2]一致，但其擾碼生成器是基于偽隨機序列存儲表實現(xiàn)的。與用矩陣法實現(xiàn)的并行擾碼方法相比，該方法的運算量小，存儲量大。文獻［4］改進了并行擾碼方法的FPGA結構，在該結構中，各路并行擾碼輸出的路徑時延均僅由一個D觸發(fā)器和一個異或門構成，該結構對高速信號處理具有很強的適應性。在文獻［4］的基礎上，文獻［5］進一步改進了并行擾碼的FPGA結構，與文獻［4］的結構相比，在保證輸出路徑時延不變的條件下，該結構減少了寄存器的使用數(shù)量。

針對多核環(huán)境中的高速無線信號，本文提出一種基于稀疏矩陣的多核并行擾碼方法。該方法應用稀疏矩陣的存儲及運算，產(chǎn)生了并行輸出的偽隨機碼，并實現(xiàn)了多核的并行加擾、解擾。

1 系統(tǒng)模型

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

圖1 基于稀疏矩陣的多核并行擾碼無線收發(fā)機

1.1 基于稀疏矩陣的多核并行擾碼

基于稀疏矩陣的多核并行擾碼結構如圖2所示。基于稀疏矩陣的并行擾碼生成器產(chǎn)生了偽隨機序列q，且同時輸出序列q中N個相鄰的偽隨機碼。此外，輸入信號b(i)經(jīng)過串/并轉換后得到N路并行信號，然后分別送入對應序號的處理器核，在單個處理器核內(nèi)，生成的偽隨機碼與輸入信號進行模二加運算，得到輸入信號的擾碼輸出；最后，并行擾碼輸出經(jīng)過并/串轉換得到串行擾碼輸出d(i)。

圖2 基于稀疏矩陣的多核并行擾碼結構

圖2中q(i)表示偽隨機序列的第i個元素；k為非負整數(shù)；加法器表示模二加運算，則第i時刻擾碼輸出d(i)的數(shù)學表達式為：

d(i)=b(i)q(i)

(1)

從圖2及式(1)可以看出，基于稀疏矩陣的并行擾碼生成器是加擾、解擾過程中的重要組成部分。接下來詳細介紹如何實現(xiàn)基于稀疏矩陣的并行擾碼生成器。

假設并行擾碼生成器輸出的偽隨機序列q為m序列，則q可由r級線性反饋移位寄存器產(chǎn)生，且其循環(huán)周期[6]L=2r-1。r級線性反饋移位寄存器的生成多項式可寫為[6]：

g(x)=1+xr+∑r-1n=1c(n)xn

(2)

式中c(n)取值為0或1。

以式(2)作為生成多項式，圖3給出了相應的r級線性反饋移位寄存器結構。

圖3 r級線性反饋移位寄存器

圖中，q(i)表示第i時刻生成的偽隨機碼；fn代表寄存器；cn代表乘法器，加法器表示模二加運算，則i時刻的線性反饋移位寄存器狀態(tài)為：

Fi=[f1i，f2i，…，fri]T

(3)

下一時刻，線性反饋移位寄存器的狀態(tài)為：

Fi+1=TFi

(4)

式中：

T=C1

Ir-1Φr×r

(5)

式中：r階方陣T為r級線性反饋移位寄存器的狀態(tài)轉移矩陣；Ir-1表示r-1階單位矩陣；C表示生成多項式的系數(shù)向量，如式(6)所示；Φ表示r-1維全零列向量。

C=[c1，c2，…，cr-1]

(6)

如圖2所示，為了利用偽隨機碼q(i)對輸入信號進行N路并行擾碼，要求擾碼生成器同時給出N路并行輸出。在一個并行周期后，線性反饋移位寄存器的狀態(tài)由Fi轉換至Fi+N。

Fi+N=TNFi

(7)

容易看出，式(7)所示的矩陣乘法運算完全等價于圖3中線性反饋移位寄存器進行N次狀態(tài)轉換的結果，即該運算可實現(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}即為并行擾碼生成器的輸出向量[2]。

如式(5)所示，由于狀態(tài)轉移矩陣T包含了r-1階的單位矩陣以及r-1維全零列向量，不失一般性，且假設TN為稀疏矩陣。本文采用稀疏矩陣的存儲及實現(xiàn)運算式(7)中的矩陣乘法，進而實現(xiàn)N路的并行擾碼生成器，并將其定義為基于稀疏矩陣的并行擾碼生成器。

1.2 稀疏矩陣的存儲及運算

1.2.1 三元組存儲

如式(8)，以IEEE 802.11n使用的擾碼生成多項式[7]為例，說明如何利用稀疏矩陣的存儲及運算實現(xiàn)并行的擾碼生成器。

g(x)=x7+x4+1

(8)

其對應的擾碼狀態(tài)轉移矩陣T為：

T=

0001001

1000000

0100000

0010000

0001000

0000100

0000010

(9)

令A=TN，并作為N路并行擾碼生成器的狀態(tài)轉移矩陣，考慮并行支路數(shù)N=3，則A為：

A=T3=

0100100

0010010

0001001

1000000

0100000

0010000

0001000

(10)

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

圖4 狀態(tài)轉移矩陣A的三元組存儲

同理，并行擾碼生成器在i時刻的狀態(tài)向量Fi也可以寫為三元組的形式。值得注意的是，由于Fi是列向量，其三元組形式中的列序號均為1。

1.2.2 稀疏矩陣相乘

對狀態(tài)轉移矩陣A、狀態(tài)向量Fi進行三元組存儲后，利用其三元組結構完成兩者的矩陣乘法。具體步驟為：首先遍歷A的三元組中第一行對應的列序號，若在列向量Fi的三元組中有相同的行序號，則將兩個三元組中的對應元素相乘并累加，直至A的三元組中第一行元素遍歷完畢，然后將其乘累加結果進行模二運算，再作為Fi+N的第一個數(shù)據(jù)。以此類推，可以得到一個并行周期后的寄存器狀態(tài)向量[8]Fi+N，將得到的Fi+N再次進行三元組存儲，重復上述步驟，即可實現(xiàn)N路的并行擾碼生成器。

2 運算量分析

由于產(chǎn)生m序列的r級線性反饋移位寄存器能夠遍歷除全0外的2r-1個狀態(tài)[6]，不失一般性，且假設寄存器狀態(tài)向量Fi中每個元素取值1，0的概率都為0.5。在實現(xiàn)并行擾碼生成器時，狀態(tài)轉移矩陣A與狀態(tài)向量Fi進行一次乘法運算后，采用普通矩陣相乘的乘法次數(shù)為r2，而采用稀疏矩陣相乘的平均乘法次數(shù)為0.5×an，式中an為稀疏矩陣A的非零元素個數(shù)。

由于加擾、解擾的運算量主要來自于并行擾碼生成器，如式(8)所示，采用文獻［7］中IEEE 802.11n的擾碼生成多項式，給出了實現(xiàn)并行擾碼生成器時，分別采用普通矩陣乘法與稀疏矩陣乘法的運算量見表1。

表1 普通矩陣乘法與稀疏矩陣乘法的運算量比較

N234567

稀疏矩陣相乘的乘法次數(shù) /次4.555.56.57.58.5

普通矩陣相乘的乘法次數(shù) /次494949494949



表中，N表示并行支路數(shù)，采用文獻［7］中IEEE 802.11n的擾碼生成多項式，F(xiàn)i的一次狀態(tài)轉移矩陣T如式(9)所示，則A=TN，r=7。

從表1可以看出，采用IEEE 802.11n的生成多項式，與普通矩陣乘法實現(xiàn)的多核并行擾碼方法相比，基于稀疏矩陣的多核并行擾碼方法，其乘法運算量降低了一個數(shù)量級。

3 結 語

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

(上接第70頁)

參 考 文 獻

［1］楊際祥，譚國真，王榮生.多核軟件的幾個關鍵問題及其研究進展［J］.電子學報，2010，38(9):2140-2146.



［2］CHOI D W. Parallel scrambling techniques for digital multiplexers [J]. ATT Technical Journal， 1986， 65: 123-136.



［3］LEE S H， LEE P J. Integrated parallel scrambler design for high-speed transmission systems [C]// IEEE International Symposium on Circuits and Systems. Espoo， Finland: IEEE， 1988: 361-364.



［4］LIN C H， CHEN C N， WANG Y J. et al. Parallel scrambler for high-speed applications [J]. IEEE Transactions on Circuits and Systems II: Express Briefs， 2006， 53:558-562.



［5］CHEN J W， LIN H C， TANG Y C. Efficient high-throughput architectures for high-speed parallel scramblers [C]// Proceedings of 2010 IEEE International Symposium on Circuits and Systems. Paris， France: IEEE， 2010: 441-444.



［6］查光明，熊賢祚.擴頻通信［M］.西安:西安電子科技大學出版社，1990.



［7］IEEE Std 802.11. Part 11: wireless LAN medium access control(MAC) and physical layer(PHY) specifications [S]. [S.l.]: IEEE， 2007.



［8］蔣川群，杜奕.稀疏矩陣相乘的一個改進算法［J］.計算機工程與應用，2009，45(19)：55-57.

作者簡介：

馬萬治 男，1978年出生，四川都江堰人，博士研究生。主要研究方向為空時編碼、MIMO非相干檢測技術、分布MIMO信道建模等。

王 俊 女，1988年出生，重慶永川人，碩士研究生。主要研究方向為擴頻通信、移動通信、通信抗干擾技術等。

趙宏志 男，1978年出生，河北石家莊人，講師。主要研究方向為移動通信、MIMO、OFDM技術等。

唐友喜 男，1964年出生，河南潢川人，教授，博士生導師。主要研究方向為OFDM、UWB、分布MIMO、傳感器網(wǎng)絡等。

