基于2n-1長m序列的FHT運算及FPGA實現

作者簡介：張慶業（1985—），男，高級工程師，碩士；研究方向：衛星移動通信傳輸技術設計及仿真。

*通信作者：王力男（1968—），男，研究員，碩士；研究方向：衛星移動通信系統設計。

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

關鍵詞：輔同步信號；快速哈達碼變換；m序列；FPGA

中圖分類號：TN9295文獻標志碼：A

0引言

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

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

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

y=r0×M0（1）

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

另一方面，FHT可以看作是實數域的快速傅里葉變換（FastFourierTransform，FFT），可以利用蝶形運算快速完成相關計算過程。以23哈達碼為例，整個計算過程可以表示為：

s=z·H8（2）

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

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

M1=PL·H·PS（3）

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

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標準的輸入輸出過程，而z=［0，r］·PL=［z0，z1，…，z2n-1］是FHT的行置換過程，y=s·Ps是FHT的列置換過程。

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

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

2基于22-1長序列FHT應用

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

M0=+1-1-1

-1-1+1

-1+1-1（5）

當本地序列r0與矩陣相乘，即r0=［r0，r1，r2］·M0=［-1，3，-1］，其中最大值3所對應的序號1即為m1。

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

H4=+1+1+1+1

+1-1+1-1

+1+1-1-1

+1-1-1+1（6）

進一步利用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，同時將第一個元素補0得到矩陣HC，利用HC每個元素對應為哈達碼矩陣H4的列序號索引重新生成矩陣PS：

PS=+1+1+1+1

+1-1-1+1

+1+1-1-1

+1-1+1-1（8）

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

最后，利用FHT完成相關運算。先將本地序列r0的第一個元素補0，即r1=［0，-1，-1，1］，再利用HR矩陣中的序號索引對r進行重新排列得到z=［0，-1，-1，1］，再將r1輸入FHT模塊完成相關值計算得到s=z·H=［-1，-1，-1，3］，再利用矩陣HC中的序號索引對s進行重新排列得到y=［-1，-1，3，-1］，最后去掉第1個元素得到y0=［-1，3，-1］，可以看到y0中最大值3所對應的序號為1，即為m1的值。

3基于27-1長序列FHT變換FPGA實現

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

4結語

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

參考文獻

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

［2］李娜，朱剛.基于哈達瑪變換的LTE輔同步信號檢測方法實現研究［J］.重慶郵電大學學報，2011（3）：294-298.

［3］喬志偉，魏學業，韓焱.用快速哈達瑪變換（FHT）實現高速線性卷積［J］.電子測量與儀器學報，2010（3）：263-267.

［4］程云鵬，葛利嘉.快速哈達馬變換在擴頻序列并行捕捉中的應用［J］.解放軍理工大學學報，2000（2）：5-10.

（編輯沈強）