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



關(guān)鍵詞：稀疏矩陣； 多核； 并行擾碼； 運(yùn)算量

中圖分類(lèi)號(hào)：TN914-34

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(60832007，60901018，60902027，61001087，U1035002/L05)；國(guó)家重大科技專(zhuān)項(xiàng)(2009ZX03003-008-01，2010ZX03003-002-01)；中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金資助項(xiàng)目(ZYGX2009J008)

0 引 言

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

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

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

1 系統(tǒng)模型

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

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

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

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

圖2 基于稀疏矩陣的多核并行擾碼結(jié)構(gòu)

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

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

(1)

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

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

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

(2)

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

以式(2)作為生成多項(xiàng)式，圖3給出了相應(yīng)的r級(jí)線性反饋移位寄存器結(jié)構(gòu)。

圖3 r級(jí)線性反饋移位寄存器

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

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

(3)

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

Fi+1=TFi

(4)

式中：

T=C1

Ir-1Φr×r

(5)

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

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

(6)

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

Fi+N=TNFi

(7)

容易看出，式(7)所示的矩陣乘法運(yùn)算完全等價(jià)于圖3中線性反饋移位寄存器進(jìn)行N次狀態(tài)轉(zhuǎn)換的結(jié)果，即該運(yùn)算可實(shí)現(xiàn)一個(gè)N路并行擾碼生成器，每個(gè)并行周期產(chǎn)生偽隨機(jī)序列q的N路并行輸出，同時(shí)將狀態(tài)向量從Fi更新至Fi+N。考慮N≤r的情況，{f(r-N+1)i，f(r-N+2)i，…，fri}即為并行擾碼生成器的輸出向量[2]。

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

1.2 稀疏矩陣的存儲(chǔ)及運(yùn)算

1.2.1 三元組存儲(chǔ)

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

g(x)=x7+x4+1

(8)

其對(duì)應(yīng)的擾碼狀態(tài)轉(zhuǎn)移矩陣T為：

T=

0001001

1000000

0100000

0010000

0001000

0000100

0000010

(9)

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

A=T3=

0100100

0010010

0001001

1000000

0100000

0010000

0001000

(10)

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

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

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

1.2.2 稀疏矩陣相乘

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

2 運(yùn)算量分析

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

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

表1 普通矩陣乘法與稀疏矩陣乘法的運(yùn)算量比較

N234567

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

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



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

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

3 結(jié) 語(yǔ)

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

(上接第70頁(yè))

參 考 文 獻(xiàn)

［1］楊際祥，譚國(guó)真，王榮生.多核軟件的幾個(gè)關(guān)鍵問(wèn)題及其研究進(jìn)展［J］.電子學(xué)報(bào)，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］查光明，熊賢祚.擴(kuò)頻通信［M］.西安:西安電子科技大學(xué)出版社，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］蔣川群，杜奕.稀疏矩陣相乘的一個(gè)改進(jìn)算法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45(19)：55-57.

作者簡(jiǎn)介：

馬萬(wàn)治 男，1978年出生，四川都江堰人，博士研究生。主要研究方向?yàn)榭諘r(shí)編碼、MIMO非相干檢測(cè)技術(shù)、分布MIMO信道建模等。

王 俊 女，1988年出生，重慶永川人，碩士研究生。主要研究方向?yàn)閿U(kuò)頻通信、移動(dòng)通信、通信抗干擾技術(shù)等。

趙宏志 男，1978年出生，河北石家莊人，講師。主要研究方向?yàn)橐苿?dòng)通信、MIMO、OFDM技術(shù)等。

唐友喜 男，1964年出生，河南潢川人，教授，博士生導(dǎo)師。主要研究方向?yàn)镺FDM、UWB、分布MIMO、傳感器網(wǎng)絡(luò)等。

