基于游程特征的線性分組碼與卷積碼類型識別*

李歆昊 張 旻 史英春 袁 泉

(1.電子工程學(xué)院705教研室，合肥,230037; 2.電子工程學(xué)院電子制約技術(shù)重點實驗室，合肥,230037)

?

基于游程特征的線性分組碼與卷積碼類型識別*

李歆昊1,2張 旻1,2史英春1,2袁 泉1,2

(1.電子工程學(xué)院705教研室，合肥,230037; 2.電子工程學(xué)院電子制約技術(shù)重點實驗室，合肥,230037)

針對線性分組碼與卷積碼的類型識別問題，本文提出了一種基于游程特征的信道編碼類型識別方法。論文從理論上分析了兩種編碼游程特性存在的差異，即卷積碼的游程具有較好的隨機性而線性碼游程的隨機性較差，并且線性碼在信息位長度附近的游程數(shù)會發(fā)生一定的畸變。通過提取編碼的游程特征，算法實現(xiàn)了對這兩種編碼類型的識別。仿真結(jié)果驗證了所提識別方法的有效性和魯棒性，表明算法具有一定的工程應(yīng)用前景。

編碼識別；線性分組碼；卷積碼；隨機性；游程分布

引 言

為了實現(xiàn)通信的可靠性并提高通信的效率，信道編碼在數(shù)字通信中得到了普遍的應(yīng)用。信道編碼及其識別技術(shù)不僅在智能通信、衛(wèi)星通信和認(rèn)知通信領(lǐng)域有廣闊的應(yīng)用前景，而且在通信對抗和網(wǎng)絡(luò)對抗領(lǐng)域也有迫切的軍事需求，因此越來越引起人們的重視[1-5]。

信道編碼識別的算法主要分為線性分組碼識別和卷積碼識別。線性分組碼的識別算法主要包括基于碼根信息差熵函數(shù)的算法[6]、基于有限域同構(gòu)原理的算法[7]、基于Walsh-Hadamard變換的算法[8]和基于碼重分析法的算法[5]等。卷積碼的識別算法主要包括基于改進歐幾里德算法[9]、基于容錯矩陣分解的算法[5]、基于Walsh-Hadamard變換的算法[10]和基于高斯法解方程的算法[5]等。它們都是通過一定的手段，在已知編碼類型的基礎(chǔ)上實現(xiàn)對編碼參數(shù)、生成多項式和校驗矩陣的識別。然而在實際的非合作通信領(lǐng)域，接收序列的編碼類型往往是未知的，這就為選擇合適的算法造成了困難。此外在通信對抗領(lǐng)域，若能確認(rèn)對方通信系統(tǒng)使用的信道編碼類型，就可以選擇相應(yīng)的干擾方法，如對使用卷積碼的通信系統(tǒng)，可采用產(chǎn)生突發(fā)錯誤為主的干擾方法，實現(xiàn)高效干擾[5,11]。由此可見，實現(xiàn)對編碼類型的識別具有重要的意義，但目前在此方面的研究成果還不多。本文從理論上分析了線性分組碼與卷積碼的游程特征差異，通過提取游程特征實現(xiàn)了線性分組碼與卷積碼編碼類型的盲識別。仿真實驗表明，在高誤碼率的情況下，算法仍然具有較好的識別效果。

1 線性分組碼與卷積碼的基本概念

1.1 線性分組碼的基本概念

將信息碼元分組，為每組信息碼附加若干監(jiān)督碼的編碼稱為分組碼。若每個監(jiān)督碼元都是由碼組中某些信息碼元線性相加得到的，則稱這樣的分組碼為線性分組碼，它的編碼器模型如圖1所示[12]。M為編碼器的輸入，稱為信息位，它由k位碼元組成。C為編碼器的輸出，稱為碼字矢量，它由n位碼元組成，其中有k位信息元，r=n-k位校驗元，并且每組碼字的校驗元僅與本組的信息元有關(guān)，與其他組無關(guān)[12]。

圖1 線性分組碼編碼器結(jié)構(gòu)Fig.1 Linear block code encoder structure

1.2 卷積碼的基本概念

圖2 卷積碼編碼器結(jié)構(gòu)Fig.2 Convolutional code encoder structure

對于一個卷積碼的編碼器，輸入長度為k0的信息序列，經(jīng)過串并變換至離散線性系統(tǒng)的k0個輸入端。系統(tǒng)的輸出端有n0個，且延遲為m，輸出的n0個編碼數(shù)字通過并串變換后送入信道完成編碼。稱這種(n0,k0,m)的碼字為卷積碼[13],如圖2所示。由圖2可知，第i時刻輸入至編碼器的信息組mi及其相應(yīng)的碼段ci，不僅與前m個碼段中的碼元有關(guān)，而且也參與了后m個碼段中的校驗運算，因此用編碼約束長度N表示卷積碼編碼過程中相互約束的碼元個數(shù)，對于(n0,k0,m)卷積碼，其編碼約束長度N=n0(m+1)。

2 序列的游程特征分析

2.1 二進制隨機序列的游程特性

定義1 設(shè)a是GF(2)上周期為v的周期序列，將a的一個周期a=(a0,a1,a2,…,av-1)依次按循環(huán)排列，使av-1與a0相鄰，則把如100…001和011…110的一連串兩兩相鄰的項分別稱為a的一個周期中的一個0游程和1游程。0游程中的0的個數(shù)或1游程中1的個數(shù)稱為這個游程的長[5]。

定義2 隨機比特序列Xn特指長度為n的比特序列，序列元素取比特值0或者1。用符號表示為

(1)

定義3 隨機數(shù)R則是一個取自廣義隨機數(shù)序列Rn的數(shù)字。該廣義隨機數(shù)序列Rn的元素取值為實際應(yīng)用中要求的定義域內(nèi)任意值。用符號表示為

(2)

此外，隨機比特序列Xn與0，1個數(shù)和游程有如下兩條性質(zhì)[5]：

(1) 在周期為2n-1的0，1序列的一個周期中，若某一元素的個數(shù)為2n-1個，則另一個的個數(shù)就為2n-1-1個。

(2) 對周期為2n-1的序列，在其一個周期內(nèi)，游程總共有2n-1個，其中0游程個數(shù)和1游程個數(shù)各占一半。長度為k(0

由此可見，隨著游程長度的遞增，隨機序列的0，1游程數(shù)按照1/2規(guī)律遞減，而且相同游程長度下的0，1游程數(shù)基本相等。

2.2 線性分組碼與卷積碼的隨機性分析

2.2.1 線性分組碼的隨機性

對于(n,k)的二元編碼來說，k位信息碼元共有2k個不同組合，輸出的碼字矢量也應(yīng)當(dāng)有2k種，如圖3(a)所示。對于長度為n的二元隨機序列，共有2n個可能的碼字矢量，如圖3(b)所示?？梢?n,k)編碼有2n-2k個禁用碼字，破壞了線性分組碼的隨機特性，導(dǎo)致線性分組碼的隨機性能變差。因為信息元的k位是可以隨機產(chǎn)生的，所以游程長度小于k的游程可以在碼字中得到，而長度大于等于k的游程只有可能在兩個碼字的拼接處得到。因此，與隨機序列的游程相比，線性分組碼的游程長度在信息位附近會發(fā)生較大畸變，不再呈現(xiàn)1/2的遞減規(guī)律。

以(6,3)線性分組碼的1游程為例，它的許用碼字如圖4所示。當(dāng)游程長度t=4(信息位長度k=3)時，此種游程長度的序列只有碼字011011和碼字110110首尾相接時才能得到，其出現(xiàn)概率p'=(1/23)×(1/23)。此時，該游程長度下的游程出現(xiàn)概率僅為完全隨機序列的1/8，游程數(shù)與隨機序列相比差別很大。

2.2.2 卷積碼的隨機性

與線性分組碼相比，卷積碼最大的不同就是具有記憶性[14]。當(dāng)信息序列被切割成長度為k0的一個個分組后，編碼時本組的n0-k0個校驗位不僅與本組的k0個信息元有關(guān)，而且還與以前各時刻輸入至編碼器的信息元有關(guān)，如圖2所示[5]。因此，每組碼字中的校驗位不再由信息位唯一確定，并且卷積碼序列由移位寄存器產(chǎn)生得到，而移位寄存器生成的序列具有很好的隨機性[15]。因此，卷積碼的隨機性較好，表現(xiàn)在游程特征上就是隨著游程長度的增加，0，1游程的數(shù)量呈現(xiàn)出1/2的遞減規(guī)律。

圖3 碼字分布圖Fig.3 Codeword distribution

圖4 (6,3)線性分組碼碼字Fig.4 (6,3) linear block codeword

2.2.3 基于游程的識別方法

現(xiàn)有的序列隨機性檢測方法很多，如單比特頻率檢測、塊內(nèi)頻率檢測、非重疊模板匹配檢測、近似熵檢測和游程檢測等[5]，它們都只能從某一方面評估序列的隨機性。除游程特征以外，線性分組碼與卷積碼的其他隨機特征差別不大。通過2.2.1節(jié)與2.2.2節(jié)的分析可知，線性分組碼與卷積碼游程特征的差異體現(xiàn)在以下兩點：(1) 兩種編碼游程特征的隨機性存在差別，卷積碼的游程特征更接近于隨機序列。(2) 線性分組碼和卷積碼的游程都隨著游程長度的增加呈現(xiàn)遞減的特性，但線性分組碼的游程特征在信息位長度附近會發(fā)生較大的畸變。因此，通過提取游程特征的方式進行編碼類型的識別，識別流程如圖5所示(Dm如式(3)所示，ri如式(4)所示)。

具體識別步驟如下所示：

步驟1:提取信道編碼序列的游程特征xi(i=1,2,…,t)，i為游程長度，xi為相應(yīng)的游程數(shù)。

步驟2:利用式(3)計算編碼序列游程數(shù)與隨機序列游程數(shù)之間的偏差值

(3)

式中：t為最大游程長度；yi為游程長度為i時的隨機序列理論游程數(shù)；D0， D1分別為0游程和1游程的偏差值。

圖5 識別流程圖Fig.5 Identification flowchart

步驟3:計算后一游程與前一游程比值

(4)

步驟4:繪制編碼序列與隨機序列的游程分布圖。

步驟5:由游程分布圖和Dm， ri的值判斷編碼類型。若游程分布圖中隨機序列與編碼序列的分布相近、Dm值小于門限值0.1且ri值大于門限值0.3，判定編碼序列采用卷積編碼，反之采用線性編碼。

3 仿真實驗

3.1 線性分組碼的游程檢測

為了驗證算法的有效性，使用Matlab軟件進行仿真實驗。隨機產(chǎn)生序列長度為33 600比特的(6,3)線性碼、(7,4)線性碼、(8,4)線性碼和(15,5)線性碼等4組編碼序列，分別提取游程長度從1到10比特的游程數(shù)，其游程分布和相應(yīng)的隨機序列游程分布如圖6所示，具體的游程數(shù)值如表1所示。由圖6可以看出，隨機序列的游程數(shù)走勢比較平滑，呈規(guī)律性的遞減趨勢，但線性分組碼的游程走勢與隨機序列出現(xiàn)了較大的分叉。(6,3) 線性碼，(7,4)線性碼、(8,4)線性碼和(15,5)線性碼分別在游程長度為2，3，3，4的位置處出現(xiàn)了較大的畸變。從表1的游程數(shù)中也得到了與圖6相近的結(jié)論。線性分組碼與隨機序列的偏差值在0.41到1.63之間變化。由表1中的數(shù)值計算前后游程比值ri，結(jié)果如表2所示。

圖6 線性分組碼游程分布圖Fig.6 Run distribution of linear block code

游程長度(6，3)(7，4)(8，4)(15，5)01010101隨機理論值1414340564233418141574265425342094200230513106216921472129210820402209210033703691474149715861519112510041050487872142112071858588485255007483676271632626163186179141321231317175183708400912668126131718356561133偏差值Dm1．631．810．390．530．430．440．420．41

表2 線性碼游程比值統(tǒng)計

表2中(6,3)線性碼、(7, 4)線性碼、(8, 4)線性碼和(15,5)線性碼分別在r2， r3， r3和r4出現(xiàn)最小值0.12， 0.14， 0.12和0.07，與1/2有較大差異。

3.2 卷積碼的游程檢測

隨機產(chǎn)生序列長度為33 600比特的(2,1,6)卷積碼、(3,2,2)卷積碼、(3,2,[4 3])卷積碼和(3,2,[3 2])卷積碼等4組編碼序列，分別提取游程長度從1到10比特的游程數(shù)，其游程分布和相應(yīng)的隨機序列游程分布如圖7所示，具體的游程數(shù)值如表3所示。由圖7可以看出，隨著游程長度的增加，4組卷積碼與隨機序列的游程分布走勢基本重合，都呈現(xiàn)出規(guī)律性的遞減特征。

從表3的游程數(shù)中也得到了與圖表相近的結(jié)論。卷積碼與隨機序列的偏差值范圍在0.03到0.07之間。由表3中的數(shù)值計算前后游程比值ri，結(jié)果如表4所示。表4中(2,1,6)卷積碼、(3,2,2)卷積碼、(3,2,[4 3])卷積碼和(3,2,[3 2])卷積碼的游程比值ri基本穩(wěn)定在1/2的上下變化。

圖7 卷積碼游程分布圖Fig.7 Run distribution of convolutional code

游程長度(2，1，6)(3，2，2)(3，2，[4，3])(3，2，[3，2])01010101隨機理論值13710372137573792378537653768372437002184318031867182918501889190218651850395489895191195194790095292544654684594764394804554784625242243231255251220235239231610115712012312411812511816674566753554635363838382914513727332242偏差值Dm0．050．020．070．060．030．030．030．05

表4 卷積碼游程比值統(tǒng)計

3.3 線性分組碼與卷積碼的游程對比

隨機產(chǎn)生序列長度為33 600比特的(6,3)線性碼和(3,2,[3 2])卷積碼，分別提取游程長度從1到10比特的0游程的游程數(shù)，得到兩種碼字各自的游程分布如圖8所示。

圖8 線性碼與卷積碼游程比較圖Fig.8 Run comparison of linear block codes and convolutional codes

由圖8可以看出，隨著游程長度的增加，線性碼與卷積碼的游程分布雖然都呈現(xiàn)出遞減的特征，但兩者的走勢并不重合。卷積碼的游程個數(shù)隨著游程長度的增加呈現(xiàn)出接近1/2的規(guī)律性遞減，而線性碼的游程數(shù)遞減并無一定的規(guī)律性。從實驗結(jié)果可知：(1) 與隨機序列的游程分布相比，圖6中4組編碼的游程分布存在明顯差異，而圖7中4組編碼的游程分布與之相近。(2) 實驗1中，4組編碼的Dm取值在0.41～1.63之間，而實驗2中，4組編碼的Dm取值在0.03到0.07之間，選擇判決門限值D=0.1，實驗1的4組偏差值都高于門限、實驗2的4組偏差值都低于門限。(3) 實驗1中，4組編碼的ri取值存在畸變點，而實驗2中，4組編碼的ri取值都在1/2左右變化，選擇判決門限值r=0.3，實驗1的4組游程比值都存在低于門限的點、實驗2的4組游程比值大部分都高于門限。

因此，根據(jù)編碼類型的判決準(zhǔn)則，實驗1中的4組編碼為線性分組碼，實驗2中的4組編碼為卷積碼，與仿真結(jié)果相一致。

3.4 誤碼性能分析

隨機產(chǎn)生序列長度為33 600比特的(6,3)線性碼和(3,2,[3 2])卷積碼，在誤碼率為0.01, 0.05, 0.1和0.2的情況下，分別提取游程長度從1到10比特的0游程的游程數(shù)，得到兩種碼字各自的游程分布如圖9所示。

圖9 誤碼性能分析Fig.9 Error performance analysis

由圖9可以看出，在誤碼率不斷升高的情況下隨著游程長度的增加，兩種碼字的游程分布仍然保持了遞減的特征。在誤碼率為0.01,0.05和0.1時，線性碼與卷積碼的游程走勢有明顯的區(qū)別，可以較容易地識別出檢測序列的編碼類型；隨著誤碼率升高到0.2，線性碼與卷積碼的游程走勢呈現(xiàn)出逐漸重合的趨勢，但此時兩者的游程分布仍然存在差異，可以達到識別編碼類型的目的?？梢?，本文算法具有較好的抗誤碼性能。

4 結(jié)束語

本文利用游程檢測的方法，根據(jù)線性分組碼與卷積碼的產(chǎn)生方式不同所導(dǎo)致的編碼序列在隨機性上的差異，通過統(tǒng)計不同游程長度下，0，1游程數(shù)的變化情況，達到對線性分組碼和卷積碼類型識別的目的。因為游程測試統(tǒng)計的是游程數(shù)，在大量的實驗數(shù)據(jù)下，誤碼導(dǎo)致的有限游程數(shù)變化并不會對整體分布產(chǎn)生較大影響，理論分析和仿真實驗表明，在誤碼率一定的情況下，本文算法可以很好地識別出線性分組碼與卷積碼類型，具有一定的工程應(yīng)用價值。由于游程長度的選取和最佳判決門限的設(shè)置，都會對高效準(zhǔn)確的識別起到至關(guān)重要的作用，所以有關(guān)這方面的研究將會在后續(xù)的文章中討論。

[1] 胡春靜, 吳湛擊, 李宗艷, 等. 一種速率匹配的準(zhǔn)循環(huán)LDPC碼的編碼構(gòu)造方法[J].南京航空航天大學(xué)學(xué)報, 2012, 44(1): 93-99.

Hu Chunjing, Wu Zhanji, Li Zongyan, et al. Construction of rate-compatible quasi-cyclic LDPC code[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2012, 44(1): 93-99.

[2] 傅婷婷, 吳湛擊, 王文博. 基于PEG算法的準(zhǔn)循環(huán)LDPC碼的編碼構(gòu)造方法[J]. 數(shù)據(jù)采集與處理, 2009, 24(Z1): 182-186.

Fu Tingting, Wu Zhanji, Wang Wenbo. PEG-based construction method for Quasi-cyclic LDPC[J]. Journal of Data Acquisition and Processing, 2009, 24(Z1): 182-186.

[3] 王平, 朱宏鵬, 李廣俠. PEG-GLDPC碼設(shè)計與性能分析[J]. 數(shù)據(jù)采集與處理, 2013, 28(3): 358-362.

Wang Ping, Zhu Hongpeng, Li Guangxia. Design and performance analysis of PEG-GLDPC[J]. Journal of Data Acquisition and Processing, 2013, 28(3): 358-362.

[4] 張仲明, 許拔, 張爾揚. 準(zhǔn)循環(huán)低密度校驗碼的快速編碼[J].數(shù)據(jù)采集與處理, 2008, 23(Z1): 105-108.

Zhang Zhongming, Xu Ba, Zhang Eryang. Fast encoding of QC-LDPC codes[J]. Journal of Data Acquisition and Processing, 2008, 23(Z1):105-108.

[5] 張永光，樓才義. 信道編碼及其識別分析[M]. 北京：電子工業(yè)出版社，2010: 23-25.

Zhang Yongguang, Lou Caiyi. Channel coding and recognition analysis[M]. Beijing: Publishing House of Electronics Industry, 2010: 23-25.

[6] 楊曉靜，聞年成. 基于碼根信息差熵和碼根統(tǒng)計的BCH碼識別方法[J]. 探測與控制學(xué)報， 2010，32(3)：69-73.

Yang Xiaojing, Wen Niancheng. Recognition method of BCH codes based on roots information dispersion entropy and roots statistic[J]. Journal of Detection & Control, 2010, 32(3): 69-73.

[7] 呂喜在，黃芝平，蘇紹璟. BCH碼生成多項式快速識別方法[J]. 西安電子科技大學(xué)學(xué)報, 2011，38(6)：159-162.

Lü Xizai, Huang Zhiping, Su Shaojing. Fast recognition method for generator polynomial of BCH codes[J]. Journal of Xidian University, 2011, 38(6): 159-172.

[8] 楊曉煒，甘露. 基于Walsh-Hadamard變換的線性分組碼參數(shù)盲估計算法[J]. 電子與信息學(xué)報, 2012，34(7)：1642-1646.

Yang Xiaowei, Gan Lu. Blind estimation algorithm of the linear block codes parameters based on WHT[J]. Journal of Electronics & Information Technology, 2012, 34(7): 1642-1646.

[9] 解輝，王豐華，黃知濤. 基于改進歐幾里德算法的1/2碼率卷積碼盲識別方法[J]. 電子對抗, 2010(1): 32-36.

Xie Hui, Wang Fenghua, Huang Zhitao. A method for blind recognition of 1/2 rate convolution code based on improved euclidean algorithm[J]. Electronic Warfare, 2010(1): 32-36.

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

Liu Jian, Wang Xiaojun, Zhou Xiyuan. Blind recognition of convolutional coding based on Walsh-Hadamard transform[J]. Journal of Electronics & Information Technology, 2010, 32(4): 884-888.

[11]楊小牛. 通信電子戰(zhàn)——信息化戰(zhàn)爭的戰(zhàn)場網(wǎng)絡(luò)殺手[M]. 北京：電子工業(yè)出版社，2011: 59-61.

Yang Xiaoniu. Communication electronic warfare-killer of battlefield network in information warfare[M]. Beijing: Publishing House of Electronics Industry, 2011: 59-61.

[12]劉銘. 線性分組碼中的交疊編碼迭代譯碼技術(shù)研究[D].成都: 電子科技大學(xué), 2008.

Liu Ming. Iterative decoding technology research of linear block code of overlapping coding[D].Chengdu: University of Electronic Science and Technology, 2008.

[13]王育民， 李暉，梁傳甲. 信息論與編碼理論[M].北京:高等教育出版社,2005: 56-59.

Wang Yumin, Li Hui, Liang Chuanjia. Information and coding theory[M]. Beijing: Higher Education Press, 2005: 56-59.

[14]彭萬權(quán). 級聯(lián)碼基于線性疊加反饋的迭代譯碼研究[D]. 重慶：重慶大學(xué)，2005.

Peng Wanquan. Study on a iterative decoding of concatenated codes with linear combination feedback[D]. Chongqing: Chongqing University, 2005.

[15]朱和貴，張祥德，楊連平，等. 基于人體指紋特征的隨機序列發(fā)生器[J]. 計算機研究與發(fā)展, 2009, 46(11): 1862-1867.

Zhu Hegui, Zhang Xiangde, Yang Lianping, et al. Fingerprint-based random sequence generator[J]. Journal of Computer Research and Development, 2009, 46(11): 1862-1867.

Blind Identifying of Type of Linear Block Code and Convolutional Code Based on Run Feature

Li Xinhao1,2, Zhang Min1,2, Shi Yingchun1,2, Yuan Quan1,2

(1.705 Research Office, Electronic Engineering Institute, Hefei, 230037, China; 2.Key Laboratory of Electronic Restriction, Electronic Engineering Institute, Hefei, 230037, China)

Aiming at solving the problem of recognition for the type of linear block code and the convolutional code, a method of the channel coding type recognition based on the run feature is proposed. Namely, the difference of the run feature of the linear block code and convolutional code is analyzed in theory. It shows that the randomness of the convolutional code run feature is superior to that of the linear block code, and the linear block code run number around the information bit length has a certain amount of distortion. Therefore, the code type can be identified by abstracting the run feature of these two codes. Simulation results show that the proposed method has high robustness and accurate recognition, and the method has a certain value in future engineering application.

coding identification; linear block code; convolutional code; random; run’s distribution

國家自然科學(xué)基金(61171170)資助項目；安徽省自然科學(xué)基金青年項目(1408085QF115)資助項目。

2013-09-24;

2014-03-27

TN911.22

A

李歆昊(1989-)，男，博士研究生，研究方向：信道編碼識別，E-mail: lixinhao1989

616@126.com。

張旻(1966-)，男，教授，博士，研究方向：通信信號處理、計算智能。

史英春(1978-)，男，博士，研究方向：無線網(wǎng)絡(luò)。

袁泉(1977-)，男，博士，研究方向：無線網(wǎng)絡(luò)。