基于求解校驗序列的(n,1,m)卷積碼盲識別

劉建成 楊曉靜

(解放軍電子工程學院 合肥 230037)

1 引言

在數字通信中，信道編碼可以提高信息傳輸的可靠性，保證通信質量。目前信道編碼主要包括線性分組碼、卷積碼、LDPC碼和Turbo碼等。卷積碼具有糾錯能力強和編譯簡單等優點已廣泛應用于衛星系統測控鏈路、深空探測系統和第3代移動通信系統等，這也使得卷積碼識別成為了信息對抗和智能移動通信 AMC(自適應調制編碼)技術中實現信息恢復所亟需解決的問題。目前，國外針對信道編碼識別研究的公開文獻資料相對較少，國內對線性分組碼的研究方法主要有文獻[1,2]中的秩函數求解、碼根統計等；對卷積碼識別主要有文獻[3]中的基于快速雙合沖算法、文獻[4]中的歐幾里德算法、文獻[5,6]中的構建分析矩陣法和文獻[7]中的Walsh-Hadamard變換法。歐幾里德算法和基于快速合沖算法計算復雜度低、所需數據量小，但只適于無記憶的(2,1,m)卷積碼碼字序列識別；構建分析矩陣法只對(n,1,m)卷積碼和系統卷積碼進行了相關的識別分析，且所需數據量非常巨大，在不知子碼長度n的情況下一般需要幾萬比特；Walsh-Hadamard變換法具有較好的容錯性能，同時需要參數n、碼字起始位置等先驗條件和巨大的數據存儲空間?？梢?，現有的卷積碼識別方法一般具有應用范圍受限、數據利用率低和所需先驗條件較多等不足。

(n,1,m)卷積碼具有良好的糾錯性能，是衛星通信、深空探測等常用的低碼率信道編碼方式[8]。本文針對該類卷積碼提出了一種新的盲識別方法，該方法計算復雜度較低，能夠在參數n和碼字起始位置均未知的情況下有效完成識別。

2 (n,1,m)卷積碼識別問題的描述

本文討論卷積碼是建立在二元域F2上，卷積碼是把信源輸出的信息序列，以k個碼元分為一組，通過編碼器輸出長為n(n＞k)的一組碼字，該碼組的n-k個校驗元不僅與本組的信息元相關，而且還與先前的m組信息元有關。因此，卷積碼一般表示為：(n,k,m)，稱k為信息子組長度，n為子碼長度，m為編碼記憶長度，n(m+ 1 )為卷積碼的約束長度[9]。現只討論k=1的卷積碼。

2.1 (n,1,m)卷積碼

設I和C分別為(n,1,m)卷積碼的信息序列和碼字序列，在環F2[x]上二者可以表示為

定義1[9](n,1,m)卷積碼的生成多項式矩陣G(x)定義為

則I(x)和C(x)之間滿足如下關系：

定義2[9]與線性分組碼相似，對于卷積碼定義校驗多項式矩陣，設G(x)是(n,1,m)卷積碼的生成多項式矩陣，H(x)為(n-1)×n的多項式矩陣，若滿足

稱H(x)為(n,1,m)卷積碼的校驗多項式矩陣(滿足式(5)的H(x)不唯一，T表示矩陣轉置)。

由式(3)和式(5)可知

現(n,1,m)卷積碼的盲識別問題可轉化為求解式(5)和式(6)，本文將通過構建數據利用率高的矩陣識別模型，引入校驗序列解決該識別問題。

2.2 識別問題的描述

現將卷積碼的編碼過程由F2[x]引申至F2上，即由標量矩陣表示，以便由截獲或接收到的0, 1序列建立識別模型。

定義3[9](n,1,m)卷積碼碼字序列C定義為

定義4[9]校驗矩陣H定義為

其中ht為(n-1)×n的矩陣(0≤t≤M,M等于H(x)中元素的最高冪次的值)，可表示為

所以，校驗矩陣H可看作是(n- 1 )×n(M+ 1 )維矩陣(hMhM-1…h0)的移位，可以表示為

碼字序列C和校驗矩陣H滿足關系式[9]

由于校驗矩陣H的不唯一性，故對其求解較為困難?，F引入校驗序列H'，能容易地由后續內容中建立的矩陣模型求解得出，進而由多個H'構造出校驗多項式矩陣H(x)，并由式(5)推導出生成多項式矩陣G(x)。

定義5(n,1,m)卷積碼校驗序列H'定義為：H'為F2上半無限長行向量

對于(n,1,m)卷積碼任意輸出的編碼序列C，若滿足

則稱H'為(n,1,m)卷積碼的校驗序列。

可見，校驗矩陣H的各行Hf,i均為校驗序列，式(12)可表示為

表示成二元齊次線性方程組的形式為

由已知的碼字序列C根據式(16)構造求解校驗序列H'的方程系數，如式(17)所示，N為[n(M+ 1 ) + 1 ]×n(M+ 1 )維的矩陣，系數矩陣的列數n(M+ 1 )要大于(n,1,m)卷積碼的約束長度。由于譯碼復雜度的限制，卷積碼約束長度通常情況下不大于48[10]，構建矩陣N時n(M+ 1 )取值為48即可。

該系數矩陣N即為識別所需的矩陣模型，由其可估計出某一校驗序列H'，進而推導出生成多項式矩陣。為方便表示，令L=n(M+ 1 ),L+ 1 =n(M+ 1 ) + 1。

3 識別方法

根據以上建立的識別模型，本節提出了校驗序列H'的識別算法和基于H'的生成多項式矩陣G(x)求解方法。針對(n,1,m)卷積碼的該識別方法同文獻[5]中的方法相比，有效地降低了所需數據量和計算復雜度。

3.1 校驗序列H'的識別方法

識別模型的建立和求解中要解決兩個問題，如何預知參數(子碼長度)n和確定碼字起始位置即ci,j中j的數值。通過系數矩陣N的秩可判斷估計的n是否正確，進而可以通過化簡后的矩陣N'確定碼字起始位置，具體算法步驟如下：

(1)設系數矩陣維數(L+1)×L,L=48。

(2)假設參數n依次取5,6,7和 8(實際應用中n不會超過8[5])。因為6是3的倍數，8是2和4的倍數，當估值不準確時只是碼字序列多移位整數個子碼長，故構建的矩陣N每一行仍滿足式(16)。

(3)根據步驟(2)中n的值由已知碼字序列C構造系數矩陣N，所需數據量為：(n·49 + 4 8) bit，當n=8時所需數據量最多，為440 bit小于500 bit。

(4)把N化成行最簡形N'，計算出N的秩K，判斷K是否等于列數L，若等于則表明式(16)只有全0解，N'除最后一行外為單位陣，此時返回步驟(2)改變n的取值；若小于L則表明具有非0解，化簡后的矩陣即為要分析的結果，執行步驟(5)。

(5)秩K不等于列數L時，矩陣化簡結果如下[5,6]：

3.2 生成多項式的求解

由上一節可識別出卷積碼的參數n和若干個(記為r個)校驗序列H'的部分序列，現介紹由識別出的r個部分序列推導出生成多項式矩陣方法的具體步驟：

(3)將方程組式(19)轉化為F2上的方程組，利用高斯消元法求解。方程組求解過程中可能存在q(q≥1)組解，由q組解中冪次最小的一組構成生成多項式矩陣G(x)，完成識別。

3.3 計算復雜度分析

4 仿真實驗與容錯性分析

本節以常用的(3,1,5)卷積碼和(4,1,5)卷積碼為例，對該識別方法的有效性進行了驗證，同時在蒙特卡洛仿真實驗的基礎上分析了該識別方法的容錯性能，即在碼字序列含有誤碼情況下能夠正確識別的能力。

4.1 實例仿真

例1(3,1,5)卷積碼的生成多項式矩陣用八進制數分別表示為[11]：G(47 53 75)，即

下面是該卷積碼非碼字同步的 500 bit編碼數據：1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 … 0 0 1 1 0 1 0 1 1 1 1 0 0 1 0 1 1 1 0 1。按照2.1節和2.2節的方法建立校驗序列識別模型N，估計參數n= 6 時，矩陣模型化簡后的N'形式如圖1所示。

圖1 矩陣模型化簡結果

由3.1節推導生成多項式矩陣方法的步驟(2)建立F2上的齊次線性方程組A·GT=0，其中G=[g1,0g1,1…g1,6g2,0g2,1…g2,6g3,0g3,1…g3,6],A為F2上22×21維矩陣，方程組如式(22)所示。

利用消元法求解方程組A·GT=0得解為：G1=[1 0 0 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 0],G2=[0 1 0 0 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1]。可見G2只是G1的移位，所以識別出該碼字序列為(3,1,5)卷積碼編碼序列，生成多項式矩陣為： [1 +x3+x4+x51+x2+x4+x51 +x+x2+x3+x5]，與式(20)相同，識別準確有效。

例2(4,1,5)卷積碼的生成多項式矩陣用八進制數分別表示為[11]：G(53 67 71 75)，即

4.2 容錯性能分析

在假設子碼長度n估值準確情況下，分析該識別方法的容錯性能，即能夠正確識別不同誤碼率的碼字序列的概率。以4.1節中的(3,1,5)和(4,1,5)卷積碼為例，通過蒙特卡洛仿真實驗統計正確識別的次數。每次仿真實驗從10000 bit的碼字序列中隨機選取連續的500 bit進行識別，識別概率如圖2所示。由圖可見，隨著子碼長度n的增大識別概率有明顯的下降，這是因為n的增大增加了約束長度，使長度為n(m+ 1 )的序列含有錯誤碼元的可能性增加；但在誤碼率高達 1 0-2時，對以上兩種卷積碼的成功識別率仍可以達到90%以上，所以該方法具有較好的容錯性能和較高的實際應用價值。

圖2 兩種卷積碼的識別概率

5 結論

本文通過改進的分析矩陣構造方法，在僅需不到500 bit數據量的情況下能夠識別出所有(n,1,m)卷積碼的子碼長度n、碼字起始位置和校驗序列H'，在對記憶長度進行估計的基礎上由校驗序列H'的部分序列構造了生成多項式矩陣G(x)的識別方程組，進而利用高斯消元法求解該方程組，準確有效地完成了(n,1,m)卷積碼的識別。該識別方法不需任何先驗條件，數據利用率高，克服了卷積碼現有識別方法的不足，同時具有較好的容錯性能，在衛星通信、深空探測及航天控制的通信體制識別、智能通信及信息恢復等領域都有重要應用意義。

[1]聞年成, 楊曉靜, 白或. 一種新的 RS碼識別方法[J]. 電子信息對抗技術, 2011, 26(2): 36-40.

Wen Nian-cheng, Yang Xiao-jing, and Bai Yu. A new recognition method of RS codes[J].Electronic Information Warfare Technology, 2011, 26(2): 36-40.

[2]聞年成, 楊曉靜. 采用秩統計和碼根特征的二進制循環碼盲識別方法[J]. 電子信息對抗技術, 2010, 25(6): 26-29.

Wen Nian-cheng and Yang Xiao-jing. Blind recognition of cyclic codes based on rank statistic and codes roots characteristic [J].Electronic Information Warfare Technology,2010, 25(6): 26-29.

[3]鄒艷, 陸佩忠. 關鍵方程的新推廣[J]. 計算機學報, 2006,29(5): 711-718.

Zou Yan and Lu Pei-zhong. A new generalization of key equation[J].Journal of Computers, 2006, 29(5): 711-718.

[4]Wang Feng-hua and Huang Zhi-tao. A method for blind recognition of convolution code based on Euclidean algorithm[C]. IEEE International Conference on Wireless Communications, Shanghai: IEEE Press, 2007: 1414-1417.

[5]薛國慶, 常逢佳, 柳衛平, 等. 1/n卷積碼盲識別[J]. 無線通信技術, 2009, 38(3): 38-42.

Xue Guo-qing, Chang Feng-jia, Liu Wei-ping,et al.. Blind identification of 1/nconvolutional codes[J].Wireless Communication Technology, 2009, 38(3): 38-42.

[6]薛國慶, 李易, 柳衛平. 系統卷積碼盲識別[J]. 信息安全與通信保密, 2009, 54(2): 57-60.

Xue Guo-qing, Li Yi, and Liu Wei-ping. Blind identification of system convolutional codes[J].Information Security and Communications Privacy, 2009, 54(2): 57-60.

[7]劉健, 王曉君, 周希元. 基于Walsh-Hadamard變換的卷積碼盲識別[J]. 電子與信息學報, 2010, 32(4): 884-888.

Liu Jian, Wang Xiao-jun, and Zhou Xi-yuan. Blind recognition of convolutional coding based on Walsh-Hadamard transform[J].JournalofElectronics&Information Technology, 2010, 32(4): 884-888.

[8]CCSDS/131. 0-B-1-2003, CCSDS Recommendation for TM Synchronization and Channel Coding[S]. Washington:CCSDS Secretariat, 2003.

[9]趙曉群. 現代編碼理論[M]. 武漢: 華中科技大學出版社, 2008:154-189.

[10]陳占計. (2,1,4)卷積碼的邏輯代數譯碼方法研究[D]. [碩士論文], 四川大學, 2006.

[11]Katsiotis A, Rizomiliotis P, and Kalouptsidis N. New constructions of high-performance low-complexity convolutional codes[J].IEEETransactionson Communications, 2010, 58(7): 1950-1961.