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

劉建成 楊曉靜

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

1 引言

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

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

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

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

2.1 (n,1,m)卷積碼

設I和C分別為(n,1,m)卷積碼的信息序列和碼字序列，在環(huán)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表示矩陣轉(zhuǎn)置)。

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

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

2.2 識別問題的描述

現(xiàn)將卷積碼的編碼過程由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…h(huán)0)的移位，可以表示為

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

由于校驗矩陣H的不唯一性，故對其求解較為困難?，F(xiàn)引入校驗序列H'，能容易地由后續(xù)內(nèi)容中建立的矩陣模型求解得出，進而由多個H'構(gòu)造出校驗多項式矩陣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根據(jù)式(16)構(gòu)造求解校驗序列H'的方程系數(shù)，如式(17)所示，N為[n(M+ 1 ) + 1 ]×n(M+ 1 )維的矩陣，系數(shù)矩陣的列數(shù)n(M+ 1 )要大于(n,1,m)卷積碼的約束長度。由于譯碼復雜度的限制，卷積碼約束長度通常情況下不大于48[10]，構(gòu)建矩陣N時n(M+ 1 )取值為48即可。

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

3 識別方法

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

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

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

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

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

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

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

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

3.2 生成多項式的求解

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

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

3.3 計算復雜度分析

4 仿真實驗與容錯性分析

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

4.1 實例仿真

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

下面是該卷積碼非碼字同步的 500 bit編碼數(shù)據(jù)：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節(jié)和2.2節(jié)的方法建立校驗序列識別模型N，估計參數(shù)n= 6 時，矩陣模型化簡后的N'形式如圖1所示。

圖1 矩陣模型化簡結(jié)果

由3.1節(jié)推導生成多項式矩陣方法的步驟(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]?？梢奊2只是G1的移位，所以識別出該碼字序列為(3,1,5)卷積碼編碼序列，生成多項式矩陣為： [1 +x3+x4+x51+x2+x4+x51 +x+x2+x3+x5]，與式(20)相同，識別準確有效。

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

4.2 容錯性能分析

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

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

5 結(jié)論

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

[1]聞年成, 楊曉靜, 白或. 一種新的 RS碼識別方法[J]. 電子信息對抗技術(shù), 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]聞年成, 楊曉靜. 采用秩統(tǒng)計和碼根特征的二進制循環(huán)碼盲識別方法[J]. 電子信息對抗技術(shù), 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]薛國慶, 常逢佳, 柳衛(wèi)平, 等. 1/n卷積碼盲識別[J]. 無線通信技術(shù), 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]薛國慶, 李易, 柳衛(wèi)平. 系統(tǒng)卷積碼盲識別[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]趙曉群. 現(xiàn)代編碼理論[M]. 武漢: 華中科技大學出版社, 2008:154-189.

[10]陳占計. (2,1,4)卷積碼的邏輯代數(shù)譯碼方法研究[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.