基于改進(jìn)歐幾里德算法的（n，1，m）卷積碼識別

劉建成，楊曉靜，張 玉

（解放軍電子工程學(xué)院，安徽 合肥 230037）

0 引言

在數(shù)字通信中，信道編碼包括線性分組碼、卷積碼、LDPC碼和Turbo碼等。卷積碼因糾錯能力強(qiáng)、編譯簡單，廣泛應(yīng)用于衛(wèi)星系統(tǒng)測控鏈路、深空探測系統(tǒng)和第三代移動通信中，這使得卷積碼的識別成為信息截獲領(lǐng)域中急需解決的問題。目前，針對卷積碼的識別主要有高斯消元法、基于快速雙合沖算法、構(gòu)建分析矩陣法和歐幾里德算法。在低碼率卷積碼識別中，高斯消元法運(yùn)算量大，復(fù)雜度為O（N3），其中N為方程組未知數(shù)的個數(shù)一般大于22；傳統(tǒng)歐幾里德算法［1］和基于快速雙合沖算法［2］均只適用于（2，1，m）卷積碼，計算復(fù)雜度分別為O（L2／4）、O（L2），L為所需碼字序列長度一般不小于25；構(gòu)建分析矩陣法［3］需要幾千比特的數(shù)據(jù)量，對矩陣化簡的運(yùn)算量大于高斯消元法?？梢?，對（n，1，m）卷積碼識別的現(xiàn)有方法主要有兩點不足：1）應(yīng)用范圍受限，不能對所有（n，1，m）進(jìn)行識別；2）所需數(shù)據(jù)量大，運(yùn)算較復(fù)雜。本文提出的改進(jìn)歐幾里德算法可有效彌補(bǔ)這兩點不足。

1 （n，1，m）卷積碼識別問題數(shù)學(xué)描述

本文討論卷積碼是建立在二元域F2上，一般表示為（n，k，m），其中n為碼長，k為信息位，m 為記憶長度。（n，k，m）卷積碼的編碼過程可用F2上的多項式矩陣表示為［4］：

式（1）中，C（x）為（1×n）的碼字多項式矩陣、I（x）為（1×k）的信息多項式矩陣、G（x）為（k×n）的生成多項式矩陣。（n，1，m）卷積碼編碼可表示為：

ci（x）和gi（x）分別為子碼多項式和子生成多項式，i＝1，2，…，n。

對（n，1，m）卷積碼的識別問題就是在僅知C（x）＝ ｛c1（x），c2（x），…，cn（x）｝的情況下如何求出 G（x）＝ ｛g1（x），g2（x），…，gn（x）｝，進(jìn) 而 得 出I（x）實現(xiàn)對信息的恢復(fù)。對式（2）展開得：

即，

可 見，I（x）為c1（x），c2（x），…，cn（x）的 公 因式。由文獻(xiàn)［4］可知，為了避免惡性碼的產(chǎn)生，其生成多項式需滿足：g1（x），g2（x），…，gn（x）的最高公因式為xL，0≤L＜m，m為記憶長度（即gi（x）的最高冪次）。又因I（x）為輸入信息序列的多項式，實際中冪次大于m，所以I（x）即為c1（x），c2（x），…，cn（x）的最高公因式，在文獻(xiàn)［5］中表示為：

式（5）中，gcd（·）表示求解最大公約數(shù)和最高公因式。在僅知c1（x），c2（x），…，cn（x）的情況下求出I（x），即可得g1（x），g2（x），…，gn（x）。這樣，（n，1，m）卷積碼的識別問題就轉(zhuǎn)化為求已知碼字多項式c1（x），c2（x），…，cn（x）的最高公因式。

歐幾里德算法是計算兩個數(shù)最大公約數(shù)的算法，又名輾轉(zhuǎn)相除法，可用于求解Fq（x）上兩個多項式a（x）和b（x）的最高公因式。輾轉(zhuǎn)相除過程如下：

式（6）中，deg（·）表示最高冪次，當(dāng)余數(shù)多項式ri（x）等于0時，余數(shù)多項式ri－1（x）＝gcd｛a（x），b（x）｝。歐幾里德算法只適用于求解兩個多項式最高公因式，下文將對其進(jìn)行改進(jìn)，求解n個多項式最高公因式。

2 歐幾里德算法的改進(jìn)及應(yīng)用

2.1 歐幾里德算法的改進(jìn)

定理［5］1：設(shè)a和b是兩個整數(shù)，而b≠0。那么存在唯一的一對整數(shù)q和r，使得

式（7）中，｜b｜表示b的絕對值。

定理［5］2（算術(shù)基本定理）：任何大于1的整數(shù)都可以表示成一些素數(shù)的乘積，如果不計這些素數(shù)在乘積中排列的先后順序，那么這種表示法是唯一的。

利用上述定理，經(jīng)典的歐幾里德算法只用于求兩個正整數(shù)的最大公約數(shù)，本文對該算法進(jìn)行推廣，使其可求n個正整數(shù)的最大公約數(shù)。

設(shè)｛a1，a2，…，an｝為n個正整數(shù)，利用改進(jìn)的歐幾里德算法求解最大公約數(shù)，具體步驟如下：

1）取r0，k＝ min｛ak，1≤k≤n｝，其余n－1個｛ai｝按原順序編為｛r0，1，r0，2，…，r0，n－1｝，由定理1可知r0，i∈ ｛r0，1，r0，2，…，r0，n－1｝均可唯一表示為：

2）同步驟1），再由n－1個r得出r1，k＝min｛r1，i｜r1，i≠0，1≤i≤n－j｝，同時找出r1，i＝0，記個數(shù)為m1，對n－m1－2個r1，i∈ ｛r1，i｜r1，i≠r1，k，0｝重新編號為r1，1，r1，2，…，r1，n－m－2。此時r1，i可表示為：

3）對 ｛rj，i｝重復(fù)步驟2），直至n－m1－…－mj－j－1＝2，設(shè)此時j＝m，則定義rm，1和rm，2為｛a1，a2，…，an｝的剩余項。

4）利用經(jīng)典歐幾里德算法求步驟3）中剩余項｛rm，1，rm，2｝的最大公約數(shù)，gcd（rm，1，rm，2）＝dm，r。

5）j從m 到1，初始化dj，r＝dm，r。依次驗證dj，r是否能整除rj－1，k，即是否滿足rj－1，kmod（dj，r）＝0。若滿足則dj－1，r＝ dj，r，否則 dj－1，r＝ gcd（dj，r，rj－1，k）。

6）得｛a1，a2，…，an｝的最大公約數(shù)，gcd｛a1，a2，…，an｝＝d0，r。

2.2 算法的計算復(fù)雜度分析

對于求解n 個整數(shù)｛a1，a2，…，an｝最大公約數(shù)的問題，一般采用先求 gcd（a1，a2）＝d1，再求gcd（d1，a3）＝d2，依次類推至gcd（dn－2，an）＝dn－1，共需要進(jìn)行n－1次最大公約數(shù)求解。改進(jìn)的算法在最壞（即式n－m1－…－mj－j－1中的mk（1≤k≤j）均為0，步驟5）中rj－1，kmod（dj，r）＝0均不滿足）的情況下，才需進(jìn)行n－1次歐幾里德求最大公約數(shù)計算。所以本文提出的算法一般只需要N＝n－（Nm＋Nj＋1）次歐幾里德最大公約數(shù)計算，其中Nm＝ m1＋m2＋ … ＋mj，Nj為步驟5）中rj－1，kmod（dj，r）＝ 0 的 次 數(shù)， 算 法 復(fù) 雜 度 為O（L2／2n）。而在同等條件下，構(gòu)建分析矩陣法復(fù)雜度為O（L3），L為碼字序列長度（一般不小于12n）。可見，該算法在解決應(yīng)用范圍受限問題的同時與構(gòu)建分析矩陣法相比有效地降低了算法復(fù)雜度。

2.3 算法的應(yīng)用

由文獻(xiàn)［5］第十章可知，解決有限域上兩個多項式的最高公因式求解問題可采用與求兩個數(shù)的最大公因式一樣的歐幾里德算法（又稱輾轉(zhuǎn)相除法）。同樣，本文對歐幾里德算法的改進(jìn)也可用于對n個二元域F2上多項式｛f1（x），f2（x），…，fn（x）｝最高公因式的求解，即可用于解決對（n，1，m）卷積碼的識別。由于實際中所截獲的碼元序列不能構(gòu)成完整的碼字多項式，本文利用參考文獻(xiàn)［1］中的修飾算法可實現(xiàn)對式（4）和（5）的求解。設(shè)c1（x），c2（x），…，cn（x）分別為所獲取的n個（n，1，m）卷積碼的不完整碼字，對g1（x），g2（x），…，gn（x）識別的具體步驟如下：

1）假設(shè)記憶長度為L，選取c1（x），c2（x），…，cn（x）中次數(shù)最低的一個碼字記為：

將其余碼字記為：

2）對j≥0，定義多項式集合為｛qj，i（x）｝和｛rj，i（x）｝，它們滿足以下關(guān)系式：

對rj，i（x）進(jìn)行式（10）、（11）和（12）遞歸計算，結(jié)束條件為i＝1、2，記此時j＝m。定義rm，1（x）和rm，2（x）為 ｛c1（x），c2（x），…，cn（x）剩 余 項 多 項 式。其 中 qj，i（x）和 rj，i（x）分 別 為 rj－1，i（x）除 以rj－1，min（x）所得的商多項式和余數(shù)多項式。

3）對剩余項多項式rm，1（x）和rm，2（x）進(jìn)行輾轉(zhuǎn)相除，這里i≥1。即：

結(jié)束條件為deg（rm，i＋2（x））≤L，設(shè)此時N ＝i＋1并記錄rm，N（x）＝rm，i＋1（x）。

4）設(shè)gk，－1（x）＝0，gk，0（x）＝1，（x）＝1，（x）＝0，rr－1（x）＝ck（x），rr0（x）＝rm，N（x），（1≤k≤n，下標(biāo)r為標(biāo)記）。對i≥1，定義qqi（x）和rri（x），滿足：

對gk，i（x）和（x）遞歸計算：

結(jié)束條件為deg（rri（x））≤L，設(shè)此時i＝I，則gk（x）＝gk，I（x）即為第k個碼字對應(yīng)的生成多項式，重復(fù)此步驟即可求出（n，1，m）卷積碼的n個碼字生成多項式：

需要說明的是，以上運(yùn)算均是建立在F2（x）上。

3 實例仿真

以（3，1，6）和（5，1，9）卷積碼為例驗證該算法的可行性。

例1：（3，1，6）卷積碼的生成多項式用八進(jìn)制數(shù)表示為G （171，133，115），即

下面是接收到該卷積碼的一段碼字同步的編碼序列：1 1 1 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 0 1 1 0 0 1 1。

按照2.3節(jié)所述的步驟對該序列進(jìn)行識別，由該段編碼序列得：

取r0，min（x）＝c2（x），由步驟2）得表1。

表1 剩余項多項式的求解過程Tab.1 Process of solving the residual polynomial

對r1，1（x）和r1，2（x）進(jìn)行步 驟 3）計 算，得r1，N（x）＝r1，5（x）：

對r1，5（x）和c1（x），c2（x），c3（x）進(jìn)行步驟4）計算，過程如表2所示，識別結(jié)果為：g1（x）＝x6＋x5＋x4＋x3＋1；g2（x）＝x6＋x4＋x3＋x＋1；g3（x）＝x6＋x3＋x2＋1，可見與式（18）相同，結(jié)果正確，驗證了算法的可行性。

表2 gk（x）的識別過程Tab.2 Process of recognizing gk（x）

例2：同理（5，1，9）卷積碼生成多項式為G （1635，1327，1517，1167，1333），即

接收到該卷積碼的一段碼字同步的編碼序列為：1 1 1 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 0 1 0 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 1 0 1 1 1 0 1 1。由該序列得碼字多項式：

取r0，min（x）＝c3（x），經(jīng)計算剩余項多項式為r3，1（x）＝x23＋x20＋…＋x5＋x3＋x2和r3，2（x）＝x24＋x22＋…＋x2＋x＋1。對r3，1（x）和r3，2（x）進(jìn)行步驟3）計算，得N即：

由步驟4）對生成多項式進(jìn)行識別，結(jié)果為：g1（x）＝x9＋x8＋x7＋x4＋x3＋x2＋1，（x）＝x9＋x8＋x3＋x2＋1；g2（x）＝x9＋x7＋x6＋x4＋x2＋x＋1，r（x）＝x9＋x5＋x4＋x3＋x2＋x＋1；g3（x）＝x9＋x8＋x6＋x3＋x2＋x＋1，r（x）＝x9＋x8＋x7＋x6＋x5＋x4＋1；g4（x）＝x9＋x6＋x5＋x4＋x2＋x＋1，（x）＝x9＋x7＋x5＋x＋1；g5（x）＝x9＋x7＋x6＋x4＋x3＋x＋1，（x）＝x9＋x5＋x4＋1。

可見gk（x）與式（21）相同，結(jié)果正確，驗證了算法的可行性。

4 結(jié)論

本文提出了基于改進(jìn)歐幾里德算法的（n，1，m）卷積碼識別方法。該方法利用求解n個多項式最高公因式的改進(jìn)歐幾里德算法解決（n，1，m）卷積碼識別問題，只要求碼字多項式最高冪次大于記憶長度m，即截獲的碼字序列長度大于其約束度，通常（n，1，m）卷積碼的約束度n·（m＋1）不大于96，所以能夠利用較少數(shù)據(jù)（小于100bit）實現(xiàn)對所有（n，1，m）卷積碼的準(zhǔn)確識別，克服了文獻(xiàn)［1］只能針對（2，1，m）卷積碼識別的局限性，彌補(bǔ)了文獻(xiàn)［3］所需數(shù)據(jù)量大和運(yùn)算復(fù)雜的不足。

［1］WANG Fenghua，HUANG Zhitao.A method for blind recognition of convolution code based on euclidean algorithm［C］／／IEEE Inter Conference on Wireless Com Networking and Mobile Computing.US：IEEE，2007：1 414－1 417.

［2］鄒艷，陸佩忠.關(guān)鍵方程的新推廣［J］.計算機(jī)學(xué)報，2006，29（5）：171－178.ZOU Yan，LU Peizhong.A new generalization of key equation［J］.Chinese Journal of Computers，2006（5）：171－178.

［3］薛國慶，常逢佳，柳衛(wèi)平，等.1／n卷積碼盲識別［J］.無線通信技術(shù)，2009（3）：38－42.XUE Guoqing，CHANG Fengjia，LIU Weiping，et al.Blind identification of 1／n convolutional codes［J］.wireless communication Technology，2009（3）：38－42.

［4］Andre Neubauer，Jurgen Freudenberger，Volker Kuhn.Coding theory algorithms，architectures and applications［M］.北京：人民郵電出版社，2009.

［5］萬哲先.代數(shù)導(dǎo)引［M］.北京：科學(xué)出版社，2010.