基于2n-1長m序列的FHT運(yùn)算及FPGA實(shí)現(xiàn)

作者簡介：張慶業(yè)（1985—），男，高級(jí)工程師，碩士；研究方向：衛(wèi)星移動(dòng)通信傳輸技術(shù)設(shè)計(jì)及仿真。

*通信作者：王力男（1968—），男，研究員，碩士；研究方向：衛(wèi)星移動(dòng)通信系統(tǒng)設(shè)計(jì)。

摘要：在地面4G/5G移動(dòng)通信中輔同步信號(hào)（SecondarySynchronizationSignal，SSS）都由長為31和127的小m序列組成，在求最大相關(guān)值運(yùn)算中通常都采用快速哈達(dá)碼變換（FastHadamardTransform，F(xiàn)HT）來減少計(jì)算量、降低運(yùn)算資源的使用，但是對于任意長序列的FHT推導(dǎo)沒有擴(kuò)展描述。文章針對基于2n-1任意長度的小m序列到FHT運(yùn)算的行列變換過程給出了完整的矩陣推導(dǎo)，并利用長為3的小m序列進(jìn)行仿真驗(yàn)證結(jié)論的正確性，最后以5G標(biāo)準(zhǔn)中長度為127的SSS序列完成FHT的FPGA實(shí)現(xiàn)。

關(guān)鍵詞：輔同步信號(hào)；快速哈達(dá)碼變換；m序列；FPGA

中圖分類號(hào)：TN9295文獻(xiàn)標(biāo)志碼：A

0引言

快速哈達(dá)碼變換（FastHadamardTransform，F(xiàn)HT）是當(dāng)前數(shù)字信號(hào)處理中最基本的變換之一，在現(xiàn)有的地面移動(dòng)通信、衛(wèi)星通信、多媒體編解碼中得到廣泛應(yīng)用［1-2］。在地面4G/5G移動(dòng)通信中輔同步信號(hào)（SecondarySynchronizationSignal，SSS）都是由長度為2n-1的小m序列組成，而且在4G移動(dòng)通信中SSS序列的計(jì)算需要與本地168種m序列進(jìn)行相關(guān)運(yùn)算，在5G移動(dòng)通信中需要與本地336種m序列進(jìn)行相關(guān)運(yùn)算，因此在求最大相關(guān)值運(yùn)算的過程中通常采用FHT來減少計(jì)算量、降低運(yùn)算資源的使用。然而當(dāng)前4G/5G移動(dòng)通信中的相關(guān)文獻(xiàn)對于長度分別為31（25-1）和127（27-1）的小m序列到FHT只給出了最終的前后變換系數(shù)，而對于中間的過程推導(dǎo)以及任意2n-1長度的小m序列到FHT的過程沒有擴(kuò)展描述［3-4］，因此在本文中將會(huì)對基于2n-1長度的小m序列到FHT的變換過程推導(dǎo)以及其FPGA開發(fā)實(shí)現(xiàn)進(jìn)行詳細(xì)的介紹和應(yīng)用舉例說明。

1基于2n-1長M序列FHT

由5G移動(dòng)通信中SSS序列的第二部分表達(dá)式d（n）=1-2×（（n+m1）%127）中可以看到，隨著m1從0～126的變化，總計(jì)可以有127種本地m序列形成維度為127×127的矩陣M0。對于接收序列r=［r0，r1，…，r126］，為了找到其最大峰值相關(guān)序列，需要和上述127種本地序列進(jìn)行求相關(guān)運(yùn)算，即，

y=r0×M0（1）

其中，y=［y0，y1，…，y126］，進(jìn)而從y中找到最大值。上述求相關(guān)運(yùn)算總計(jì)需要16002次加法運(yùn)算。

另一方面，F(xiàn)HT可以看作是實(shí)數(shù)域的快速傅里葉變換（FastFourierTransform，F(xiàn)FT），可以利用蝶形運(yùn)算快速完成相關(guān)計(jì)算過程。以23哈達(dá)碼為例，整個(gè)計(jì)算過程可以表示為：

s=z·H8（2）

其中，s=［s0，s1，…，s7］是FHT的輸出，z=［z0，z1，…，z7］是FHT需要的輸入，H8是基于23的哈達(dá)碼矩陣，整個(gè)FHT蝶形運(yùn)算分為3個(gè)階段完成。

為了利用蝶形運(yùn)算達(dá)到FHT的快速計(jì)算，需要對矩陣M0進(jìn)行預(yù)處理，即在最左邊一列和最上面一行添加全1的元素，將矩陣M0變?yōu)橐粋€(gè)維度為2n×2n的矩陣M1，由于M1是小m序列循環(huán)移位生成的，整個(gè)矩陣是滿秩矩陣，利用矩陣變換公式：

M1=PL·H·PS（3）

其中，PL和PS表示置換矩陣，H是基于2n的哈達(dá)碼矩陣，上式表示對哈達(dá)碼矩陣H的行列進(jìn)行線性變換即可生成矩陣M1。因此，公式（1）可以統(tǒng)一表示為：

y=［0，r］·M1

=（［0，r］·PL）·H·PS

=z·H·PS

=s·PS（4）

其中，y=［y0，y1，…，y2n-1］，r=［r0，r1，…，r2n-2］，s=z·H=［s0，s1，…，s2n-1］，可以看到，公式（5）即為FHT標(biāo)準(zhǔn)的輸入輸出過程，而z=［0，r］·PL=［z0，z1，…，z2n-1］是FHT的行置換過程，y=s·Ps是FHT的列置換過程。

接下來，對置換矩陣PL和PS的求解進(jìn)行分析，由于對M1矩陣到H矩陣行列變換PL和PS的組合有很多種，可以采用固定PS再求解PL的思路。PS在H矩陣右側(cè)可以理解為對H矩陣進(jìn)行列變換生成，具體的列變換過程可以表示為：（1）利用M0矩陣每個(gè)元素的符號(hào)位生成元素為0和1的矩陣K0，整個(gè)K0矩陣大小為（2n-1）×（2n-1）；（2）取M0矩陣的前n列和全部（2n-1）行組成新的矩陣K1，矩陣大小為（2n-1）×n，將第0列定義為MSB比特，最后一列定義為LSB比特，生成大小為（2n-1）×1的矩陣L0，同時(shí)將第一個(gè)元素置0生成大小為2n×1的矩陣HC，利用HC矩陣中每個(gè)元素對應(yīng)為H矩陣列序號(hào)的索引生成大小為的2n×2n矩陣PS，HC即為H矩陣的列變換索引，再利用PL=M1·P-1S·H-1，即可求得PL矩陣；（3）將PL中的每一行與M0矩陣中的每一行進(jìn)行對比即可得到H矩陣行的索引值矩陣HR，即為H矩陣的行變換索引。

具體來說，在4G/5G移動(dòng)通信的FHT應(yīng)用中，假設(shè)接收端序列為rx0=［r0，r1，…，r2n-2］，首先將第一個(gè)元素補(bǔ)0，得到rx1=［0，r0，r1，…，r2n-2］；然后再利用HR矩陣中的序號(hào)索引完成對rx1的重新排列得到序列z，再將序列z輸入FHT運(yùn)算模塊完成2n個(gè)相關(guān)值運(yùn)算，得到序列s；最后利用HC矩陣中的序號(hào)索引完成對序列s的重新排列得到y(tǒng)，即為最終rx1和M1的相關(guān)運(yùn)算結(jié)果。

2基于22-1長序列FHT應(yīng)用

設(shè)置小m序列生成多項(xiàng)式為x2+x+1，寄存器初始狀態(tài)為［0，1］，輸出表達(dá)式為d（n）=1-2×（（n+m1）%3），x0=0，x1=1，x2+i=（x0+i+x1+i）mod2，設(shè)置m1=1，可得本地接收序列r0=［-1，-1，1］。整個(gè)m1的取值范圍為0～2，最后得到矩陣M0：

M0=+1-1-1

-1-1+1

-1+1-1（5）

當(dāng)本地序列r0與矩陣相乘，即r0=［r0，r1，r2］·M0=［-1，3，-1］，其中最大值3所對應(yīng)的序號(hào)1即為m1。

對矩陣M0進(jìn)行哈達(dá)碼變換，在最左邊和最上邊添加全1，變成大小為4×4的矩陣M1；利用公式（3）M1=PL·H4·PS，對矩陣M1進(jìn)行變換，其中哈達(dá)碼矩陣H4可以表示為：

H4=+1+1+1+1

+1-1+1-1

+1+1-1-1

+1-1-1+1（6）

進(jìn)一步利用c（n）=x（（n+m1）%3），生成元素為0和1的矩陣K0：

K0=011

110

101（7）

取K0矩陣的前2列組成矩陣K1，將第0列定義為MSB比特，第1列定義為LSB比特，生成矩陣L0=［1，3，2］T，同時(shí)將第一個(gè)元素補(bǔ)0得到矩陣HC，利用HC每個(gè)元素對應(yīng)為哈達(dá)碼矩陣H4的列序號(hào)索引重新生成矩陣PS：

PS=+1+1+1+1

+1-1-1+1

+1+1-1-1

+1-1+1-1（8）

同時(shí)，利用PL=M1·P-1S·H-14，得到矩陣PL;將矩陣PL中的每一行與哈達(dá)碼矩陣H4的每一行進(jìn)行對比，即可得到H4矩陣行的索引變換矩陣HR=［0，2，1，3，2］T。

最后，利用FHT完成相關(guān)運(yùn)算。先將本地序列r0的第一個(gè)元素補(bǔ)0，即r1=［0，-1，-1，1］，再利用HR矩陣中的序號(hào)索引對r進(jìn)行重新排列得到z=［0，-1，-1，1］，再將r1輸入FHT模塊完成相關(guān)值計(jì)算得到s=z·H=［-1，-1，-1，3］，再利用矩陣HC中的序號(hào)索引對s進(jìn)行重新排列得到y(tǒng)=［-1，-1，3，-1］，最后去掉第1個(gè)元素得到y(tǒng)0=［-1，3，-1］，可以看到y(tǒng)0中最大值3所對應(yīng)的序號(hào)為1，即為m1的值。

3基于27-1長序列FHT變換FPGA實(shí)現(xiàn)

針對5G移動(dòng)通信中SSS信道序列第二部分d（n）=1-2×（（n+m1）%127），進(jìn)行FHT變換實(shí)現(xiàn)。首先將接收序列的第一個(gè)元素補(bǔ)0生成新的接收序列r1=［0，r0，r1，…，r126］，然后輸入FHT運(yùn)算模塊，如圖1所示，整個(gè)FHT運(yùn)算模塊由5部分組成：輸入位置變換模塊、地址控制模塊、單口RAM模塊、蝶形運(yùn)算模塊、輸出位置變換模塊。其中：（1）1st_permute完成輸入數(shù)據(jù)的位置變換后存入深度為128的單口SPRAM；（2）蝶形運(yùn)算模塊分為Stage0到Stage6總計(jì)7個(gè)階段，每個(gè)階段將由64組蝶形運(yùn)算完成，每次蝶形運(yùn)算需要4個(gè)時(shí)鐘，前2個(gè)時(shí)鐘為讀SPRAM數(shù)據(jù)使能，后2個(gè)時(shí)鐘完成加運(yùn)算（A+B）和減運(yùn)算（A-B），并寫入SPRAM；（3）AddressCtrl是地址控制單元完成SPRAM所有數(shù)據(jù)的數(shù)和寫地址管理；（4）2nd_permute完成FHT蝶形運(yùn)算后輸出數(shù)據(jù)的位置變換，通過地址控制依次從SPRAM中讀出輸出數(shù)據(jù)；（5）FHT計(jì)算過程需要2490個(gè)時(shí)鐘，如圖2所示為FHT模塊仿真時(shí)序。

4結(jié)語

本文針對基于2n-1任意長度小m序列到FHT的變換給出了詳細(xì)的矩陣推導(dǎo)過程，主要集中于置換矩陣PL和PS的推導(dǎo)，同時(shí)利用22-1長度的小m序列進(jìn)行了整體推導(dǎo)算法正確性的驗(yàn)證，最后以5G移動(dòng)通信標(biāo)準(zhǔn)中SSS序列對127長度的小m序列到FHT的變換進(jìn)行了仿真驗(yàn)證，利用單個(gè)深度為128的單口SPRAM完成了輸入數(shù)據(jù)置換、蝶形運(yùn)算以及輸出數(shù)據(jù)置換的FPGA開發(fā)實(shí)現(xiàn)。

參考文獻(xiàn)

［1］郭吳晨.基于FPGA的二維快速哈達(dá)巧變換［D］.西安：西安電子科技大學(xué)，2014.

［2］李娜，朱剛.基于哈達(dá)瑪變換的LTE輔同步信號(hào)檢測方法實(shí)現(xiàn)研究［J］.重慶郵電大學(xué)學(xué)報(bào)，2011（3）：294-298.

［3］喬志偉，魏學(xué)業(yè)，韓焱.用快速哈達(dá)瑪變換（FHT）實(shí)現(xiàn)高速線性卷積［J］.電子測量與儀器學(xué)報(bào)，2010（3）：263-267.

［4］程云鵬，葛利嘉.快速哈達(dá)馬變換在擴(kuò)頻序列并行捕捉中的應(yīng)用［J］.解放軍理工大學(xué)學(xué)報(bào)，2000（2）：5-10.

（編輯沈強(qiáng)）