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

劉建成 楊曉靜

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

1 引言

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

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

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

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

2.1 (n,1,m)卷積碼

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

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

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

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

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

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

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

2.2 識(shí)別問題的描述

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

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

定義4[9]校驗(yàn)矩陣H定義為

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

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

碼字序列C和校驗(yàn)矩陣H滿足關(guān)系式[9]

由于校驗(yàn)矩陣H的不唯一性，故對(duì)其求解較為困難?，F(xiàn)引入校驗(yàn)序列H'，能容易地由后續(xù)內(nèi)容中建立的矩陣模型求解得出，進(jìn)而由多個(gè)H'構(gòu)造出校驗(yàn)多項(xiàng)式矩陣H(x)，并由式(5)推導(dǎo)出生成多項(xiàng)式矩陣G(x)。

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

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

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

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

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

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

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

3 識(shí)別方法

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

3.1 校驗(yàn)序列H'的識(shí)別方法

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

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

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

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

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

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

3.2 生成多項(xiàng)式的求解

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

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

3.3 計(jì)算復(fù)雜度分析

4 仿真實(shí)驗(yàn)與容錯(cuò)性分析

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

4.1 實(shí)例仿真

例1(3,1,5)卷積碼的生成多項(xiàng)式矩陣用八進(jìn)制數(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é)的方法建立校驗(yàn)序列識(shí)別模型N，估計(jì)參數(shù)n= 6 時(shí)，矩陣模型化簡后的N'形式如圖1所示。

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

由3.1節(jié)推導(dǎo)生成多項(xiàng)式矩陣方法的步驟(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的移位，所以識(shí)別出該碼字序列為(3,1,5)卷積碼編碼序列，生成多項(xiàng)式矩陣為： [1 +x3+x4+x51+x2+x4+x51 +x+x2+x3+x5]，與式(20)相同，識(shí)別準(zhǔn)確有效。

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

4.2 容錯(cuò)性能分析

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

圖2 兩種卷積碼的識(shí)別概率

5 結(jié)論

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

[1]聞年成, 楊曉靜, 白或. 一種新的 RS碼識(shí)別方法[J]. 電子信息對(duì)抗技術(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)計(jì)和碼根特征的二進(jìn)制循環(huán)碼盲識(shí)別方法[J]. 電子信息對(duì)抗技術(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]鄒艷, 陸佩忠. 關(guān)鍵方程的新推廣[J]. 計(jì)算機(jī)學(xué)報(bào), 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卷積碼盲識(shí)別[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)卷積碼盲識(shí)別[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變換的卷積碼盲識(shí)別[J]. 電子與信息學(xué)報(bào), 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]. 武漢: 華中科技大學(xué)出版社, 2008:154-189.

[10]陳占計(jì). (2,1,4)卷積碼的邏輯代數(shù)譯碼方法研究[D]. [碩士論文], 四川大學(xué), 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.