丁　嶠，徐　衛(wèi)

（1.解放軍理工大學(xué)，南京 210007；2.空軍通信網(wǎng)絡(luò)技術(shù)管理中心，北京 100843）

?

卷積碼識(shí)別算法淺述

丁嶠1，徐衛(wèi)2

（1.解放軍理工大學(xué)，南京 210007；2.空軍通信網(wǎng)絡(luò)技術(shù)管理中心，北京 100843）

摘要：本文介紹了信道編碼識(shí)別技術(shù)的發(fā)展概況，給出了常規(guī)識(shí)別算法、基于校驗(yàn)矩陣識(shí)別算法和基于歐幾里德識(shí)別算法三種卷積碼識(shí)別算法的工作原理，對(duì)比分析了三種算法的性能。

關(guān)鍵詞：卷積碼；編碼識(shí)別；校驗(yàn)矩陣；歐幾里德算法；算法性能

徐 衛(wèi)，空軍通信網(wǎng)絡(luò)技術(shù)管理中心高級(jí)工程師，主要從事通信網(wǎng)絡(luò)管理方面的技術(shù)工作。

1 引言

通信偵察使用專門的偵察設(shè)備搜索、截獲無(wú)線電通信信號(hào)，通過(guò)對(duì)信號(hào)進(jìn)行處理、分析和識(shí)別，從而獲取大量通信對(duì)抗情報(bào)，乃至重要的軍事情報(bào)。由于不同通信系統(tǒng)的業(yè)務(wù)要求和信道條件差異較大，因此，不同的通信系統(tǒng)通常采用不同的信道編碼方案，這對(duì)于諸如通信偵察這樣的非合作通信來(lái)說(shuō)，要獲取無(wú)線電信號(hào)中所攜帶的信息，知道該信號(hào)所采用的信道編碼方案是其中的必要條件之一，編碼分析識(shí)別技術(shù)在通信偵察領(lǐng)域應(yīng)運(yùn)而生。此外，編碼分析識(shí)別技術(shù)還可以應(yīng)用于未來(lái)智能通信領(lǐng)域、無(wú)線電監(jiān)測(cè)與管理等領(lǐng)域［1］。

2 信道編碼識(shí)別技術(shù)發(fā)展概況

當(dāng)前信道編碼分析識(shí)別技術(shù)研究主要集中在對(duì)線性分組碼和卷積碼的盲識(shí)別上。

二進(jìn)制線性分組碼的盲識(shí)別方法又可分為通過(guò)解線性方程來(lái)計(jì)算校驗(yàn)多項(xiàng)式的識(shí)別方法和基于碼組正交空間的盲識(shí)別方法。利用低碼率二進(jìn)制線性分組碼的碼重分布特征來(lái)估計(jì)編碼參數(shù)［2］，數(shù)據(jù)矩陣求秩的方法在無(wú)誤碼情況下能夠準(zhǔn)確地估計(jì)出線性分組碼碼長(zhǎng)、碼組偏差，但是當(dāng)誤碼率較高時(shí)，由于矩陣求秩的限制，不能有效估計(jì)出編碼參數(shù)，并且，當(dāng)碼長(zhǎng)較長(zhǎng)時(shí)，也不能有效估計(jì)出編碼參數(shù)。

RS碼的盲識(shí)別方法是基于伽羅華域傅立葉變換來(lái)實(shí)現(xiàn)的，它是利用RS碼在伽羅華域中的零譜連續(xù)特征求出碼根，得到編碼參數(shù)。卷積碼的盲識(shí)別方法可進(jìn)一步分為一般卷積碼的盲識(shí)別和刪除卷積碼的盲識(shí)別方法。當(dāng)前編碼盲識(shí)別技術(shù)尚處于發(fā)展中，仍存在許多局限和不足。本文主要介紹卷積碼的盲識(shí)別算法。

3 常見(jiàn)卷積碼識(shí)別算法

3.1 常規(guī)識(shí)別算法

進(jìn)行卷積碼識(shí)別最直接的算法是求解線性方程組。為敘述簡(jiǎn)單，我們以碼率為 的卷積碼為例。設(shè)卷積碼是［4］

式中，y（X）=y0+y1X+y2X2+…，是信息源數(shù)據(jù)序列；f1（X）,f2（X）是生成多項(xiàng)式。p（X）=（p1（X）,p2（X））∈p，其中，pi（X）= pi , 0+ pi , 1X+ pi , 2X2+…，i = 1 , 2。該方法需要先估計(jì)約束長(zhǎng)度L=max（degf1（X）,degf2（X））。如果能保證采集到的不含誤碼的卷積碼的片段序列足夠長(zhǎng)N≥3（L+1），即要獲取的卷積碼碼流比特?cái)?shù)大于2N=6（L+1），則可以求解如下的線性方程組：

常規(guī)做法是高斯消元法，但是會(huì)存以下弊端：

首先，高斯消元法是不容錯(cuò)的，即要求方程組（2）中的系數(shù)矩陣中的每個(gè)系數(shù)不能有錯(cuò)誤。但在實(shí)際通信中，信道誤碼在所難免，采集到的數(shù)據(jù)很難保證沒(méi)有差錯(cuò)。

其次，為保證方程組（2）的可解性，要求卷積碼序列長(zhǎng)度N≥3（L+1）。由于L也是未知的，所以要設(shè)置一個(gè)較大的估計(jì)值，通常是實(shí)際約束長(zhǎng)度的數(shù)倍，而且未知參數(shù)L與N是相同數(shù)量級(jí)，所以必須采集足夠長(zhǎng)的數(shù)據(jù)。同時(shí)方程組（2）的可解性還與信源有關(guān)，方程組（2）有惟一解的概率只有50％［4］。

第三，當(dāng)卷積碼的總約束長(zhǎng)度較大時(shí)，識(shí)別過(guò)程非常耗時(shí)，因此無(wú)法在實(shí)際中應(yīng)用。

因此，采用常規(guī)識(shí)別算，如何提高識(shí)別效率是重中之重。

3.2 基于校驗(yàn)矩陣的識(shí)別算法

卷積碼序列G與校驗(yàn)矩陣H存在如下校驗(yàn)關(guān)系［5］

校驗(yàn)矩陣多項(xiàng)式的最高階數(shù)根據(jù)實(shí)際應(yīng)用設(shè)定為k，卷積碼輸出路數(shù)n，容易得到校驗(yàn)矩陣多項(xiàng)式系數(shù)的齊次線性方程組

式中，gi為接收序列中第i位；L=n（k+1）。文獻(xiàn)［6］針對(duì)式中的模型給出了相應(yīng)的求解算法，將1/2碼率卷積碼校驗(yàn)矩陣的求解模型轉(zhuǎn)化為關(guān)鍵模方程表示［7］，求解該算法即轉(zhuǎn)化為在集合φ（n）中尋找元素（h1（x）,h2（x）,k），使得k達(dá)到最小且（h1（0）,h2（0））≠（0,0），φ（n）的定義如下

其中，F(xiàn)（x）為二元域上的多項(xiàng)式環(huán)。

3.3 基于歐幾里德算法的識(shí)別算法

歐幾里德算法又稱輾轉(zhuǎn)相除法［5］，是一個(gè)迭代算法，可以用于計(jì)算兩個(gè)多項(xiàng)式a（x）和b（x）的最大公約數(shù)d（x），然后找到一個(gè)表示a（x）和b（x）之間的線性聯(lián)系，使其等于d（x），即找到方程

本方法即是應(yīng)用歐幾里得算法在有限域上的算法來(lái)求解卷積碼生成多項(xiàng)式的。對(duì)于一個(gè)1/2碼率的卷積碼的識(shí)別，接收到的碼字多項(xiàng)式是已知的c1（x）和c2（x），目標(biāo)是尋找多項(xiàng)式g1（x）和g2（x），使得

由于接收到的數(shù)據(jù)只是卷積碼編碼數(shù)據(jù)的一部分，并且，編碼序列在傳輸過(guò)程中，也會(huì)遭受噪聲的影響，使得c1（x）和c2（x）不一定滿足式（7），所以需要對(duì)歐幾里德算法進(jìn)行修正，修正后的歐幾里德算法過(guò)程如下：

第一步：參數(shù)初始化

第二步：對(duì)于i≥1，定義qi（x），ri（x）滿足ri-2（x）= qi（x）ri-1（x）+ri（x），其中qi（x），ri（x）分別是ri-2（x）除以ri-1（x）所得到的商多項(xiàng)式和余數(shù)多項(xiàng)式。

第三步：迭代運(yùn)算

第四步：終止條件

設(shè)此時(shí)i=n，可以得到g1（x）=g1,n（x）,g2（x）= g2,n（x）。

4 算法性能比較

4.1 正確識(shí)別率比較

根據(jù)相關(guān)文獻(xiàn)資料［8］可以得到前述三種算法在識(shí)別完全無(wú)誤卷積碼時(shí)的正確識(shí)別率，如表1所示。由表1可以看出，除了常規(guī)算法以外，另二種識(shí)別算法都能正確識(shí)別接收到的完全無(wú)誤卷積碼，正確識(shí)別率可以達(dá)到 。

表1　正確識(shí)別率比較結(jié)果

4.2 抗誤碼性比較

表2列出了3種算法的抗誤碼性能［4］，從表中可以看出，除了常規(guī)算法以外，另外兩種識(shí)別算法都具有一定的抗誤碼能力，基于校驗(yàn)矩陣的匹配識(shí)別算法抗誤碼能力與誤碼發(fā)生在截取碼流中的位置有關(guān)；基于歐幾里德算法的識(shí)別算法只能抗少量誤碼。

表2　抗誤碼性能比較結(jié)果

4.3 計(jì)算復(fù)雜度比較

常規(guī)識(shí)別算法的計(jì)算復(fù)雜度是O（N3）（其中N是接收碼字長(zhǎng)度）、基于校驗(yàn)矩陣的匹配識(shí)別算法的計(jì)算復(fù)雜度隨著接收碼字長(zhǎng)度N的增加而增加，基于歐幾里德算法最多需要L×N/2次多項(xiàng)式乘法和加法運(yùn)算，其中L是生成多項(xiàng)式g1（x），g2（x）的最大階次，即L=max（degg1（x）,degg2（x））；N是用于求解的碼字序列長(zhǎng)度，N≥3（L+1）。在接收碼長(zhǎng)N一定時(shí)，常規(guī)識(shí)別算法的計(jì)算復(fù)雜度最高，基于歐幾里德算法的計(jì)算復(fù)雜度最低。

4.4 綜合比較

綜合上文對(duì)三種識(shí)別算法在識(shí)別1/2碼率卷積碼時(shí)的性能比較可以發(fā)現(xiàn)，常規(guī)識(shí)別算法無(wú)論在正確識(shí)別率、抗誤碼性能還是在計(jì)算復(fù)雜度上都不及其他算法；基于校驗(yàn)矩陣的匹配識(shí)別算法計(jì)算最簡(jiǎn)便，但抗誤碼性能不穩(wěn)定，而基于歐幾里德算法的識(shí)別算法正確識(shí)別率高、計(jì)算復(fù)雜度低，但是其抗誤碼性能有待改進(jìn)。

5 總結(jié)與展望

隨著通信對(duì)抗逐漸從信號(hào)對(duì)抗轉(zhuǎn)向信息對(duì)抗，信道編碼盲識(shí)別技術(shù)的地位越來(lái)越重要。本文簡(jiǎn)要介紹了現(xiàn)有三種卷積碼信道編碼的盲識(shí)別方法，分析了三種識(shí)別算法的算法性能。從分析中可以看到，現(xiàn)有信道編碼識(shí)別技術(shù)尚存在許多局限和不足，需要進(jìn)一步研究來(lái)補(bǔ)充和完善：在識(shí)別對(duì)象上，現(xiàn)有的研究主要集中在卷積碼的研究，其他信道編碼體制，如BCH碼、RS碼、Turbo碼以及LDPC等的相關(guān)研究資料非常少；目前的卷積碼識(shí)別方法也存在很多不足，普通卷積碼的識(shí)別方法僅對(duì)1/2碼率有效，不能適應(yīng)高碼率的情況，刪除卷積碼的識(shí)別方法不能快速穩(wěn)定地完成識(shí)別，等等?！?/p>

參考文獻(xiàn)

［1］ 杜宇峰.信道編碼分析識(shí)別技術(shù)研究［D］.西安：電子科技大學(xué)，2012

［2］ 劉健，謝锘，周希元.RS碼的盲識(shí)別方法［J］.電子科技大學(xué)學(xué)報(bào)，2009,38（3）：363-368

［3］ 解輝，王豐華，黃知濤.基于改進(jìn)歐幾里得算法的1/2碼率卷積碼盲識(shí)別方法［J］.電子對(duì)抗，2010,1：32-36

［4］ 宋鏡業(yè).信道編碼識(shí)別技術(shù)研究［D］.西安：西安電子科技大學(xué)，2009

［5］ J H van Lint. Introduction to Coding Theory［M］.Beijing：World Publishing Corporation,2003.

［6］ 周亞建，劉健.（n,n-1,m）卷積碼的盲識(shí)別［J］.北京郵電大學(xué)學(xué)報(bào)，2010,33（3）：135-138

［7］ 鄒艷，陸佩忠.關(guān)鍵方程的新推廣［J］.計(jì)算機(jī)學(xué)報(bào)，2006,29（5）：711-718

Analysis of the Recognition Algorithm of Convolutional Code

Ding Qiao1, Xu Wei2
（1.PLA University of Science and Technology, Nanjing, 210007； 2.Air Force Communication Network Management Center, Beijing, 100843）

Abstract:Overview of the development of the recognition of channel coding technology is presented in this paper, the working principle of three convolutional code recognition algorithms, i.e.conventional recognition algorithm, parity check matrix-based recognition algorithm and Euclidean-based recognition algorithm is given, comparative analysis of three algorithms’-performance is presented in this paper.

Keywords:Convolutional encoding； Coding Recognition； Parity check matrix； Euclidean algorithm；Algorithm performance

doi：10.3969/J.ISSN.1672-7274.2016.06.004

中圖分類號(hào)：TN97，TN92

文獻(xiàn)標(biāo)識(shí)碼：A 文章編碼：1672-7274（2016）06-0011-03

作者簡(jiǎn)介：丁 嶠，解放軍理工大學(xué)通信工程學(xué)院通信工程專業(yè)學(xué)生。