包 昕,游 凌

(盲信號處理重點實驗室，成都　610041)

擴展卷積碼生成矩陣的統(tǒng)一表述*

包 昕**,游 凌

(盲信號處理重點實驗室，成都610041)

針對在刪除卷積碼識別過程中缺乏對擴展卷積碼先驗認知的問題,提出了一種求解母碼與擴展卷積碼生成矩陣的統(tǒng)一表述方法。通過分析編碼器輸入輸出關(guān)系的基本物理意義,先后以(n, 1,m)、(n,k,m)作為母碼,構(gòu)建了其與擴展后編碼器多項式系數(shù)的對應(yīng)關(guān)系模型,歸納和證明了擴展卷積碼生成矩陣的統(tǒng)一表述定理。驗證結(jié)果表明:該定理能夠?qū)U展卷積碼生成矩陣實現(xiàn)快速計算,為遍歷和重建刪除卷積碼的刪除圖樣和母碼生成矩陣提供方便。

盲識別;刪除卷積碼;母碼;擴展卷積碼;生成矩陣

引用格式:包昕，游凌.擴展卷積碼生成矩陣的統(tǒng)一表述[J].電訊技術(shù)，2016，56(3)：267-272.[BAO Xin，YOU Ling.A unified descriPtion of generator matrix of exPansion convo1utiona1 codes[J].Te1ecommunication Engineering，2016，56(3)：267-272.]

1　引 言

E1ias于1955年最早提出卷積碼，Cain于1979年給出了刪除卷積碼的構(gòu)想。半個世紀以來，隨著其編碼、譯碼技術(shù)的深入研究，卷積碼已被廣泛應(yīng)用于衛(wèi)星、深空等多種通信系統(tǒng)中，成為CCSDS、IESS、DVB-S等協(xié)議/標(biāo)準(zhǔn)中的信道編碼解決方案。

與此同時，人們針對卷積碼識別問題也抱有濃厚的興趣。Rice[1]證明(n，1，m)卷積碼的識別可等價于LRS問題中關(guān)鍵方程(Key Equation，KE)的求解；Fi1io1[2]將BM算法引入前述問題中；鄒艷[3]則進一步推廣KE，給出了基于Gr?bner基快速合沖的識別算法。利用卷積碼的代數(shù)結(jié)構(gòu)，劉建成[4]和楊曉靜[5]分別研究了矩陣分析方法；Wang[6]和Xie[7]建立了基于歐幾里德算法的識別模型；Marazin[8]使用迭代策略，給出了基于對偶碼組的識別思想。在誤碼條件下，Dinge1[9]和Barbier[10]提出了能夠規(guī)避誤碼碼組的隨機高斯消元法；張立民[11]引入Wa1sh -Hadamard變換，可在變元數(shù)不大的條件下實現(xiàn)卷積碼校驗向量的有限窮舉。

刪除卷積碼的識別問題更為復(fù)雜。文獻[12-14]將其分為三步：第1步，獲得碼流的等效校驗矩陣HP；第2步，求解HP在某準(zhǔn)則下的正交矩陣，即等效生成矩陣GP；第3步，由GP重建擴展生成矩陣G[M]、母碼生成矩陣G和刪除圖樣P。對于第1步，即等效校驗矩陣HP的估計問題，可依賴前述一般卷積碼識別方法。因此，第2步和第3步才是刪除卷積碼識別問題的核心和難點。陸佩忠[12]研究了(2，1，) m卷積碼作為母碼的盲識別問題，通過搜索可能的刪除圖樣，建立并求解了HP和GP的方程組。C1uzeau[13]重點討論了如何獲得一個適合譯碼的最佳等效生成矩陣G。Marazin[14]系統(tǒng)研究了母碼為(n，k，) m卷積碼時的刪除卷積碼的代數(shù)求解方法。

顯然，正確描述擴展卷積碼生成矩陣G[M]的基本構(gòu)造形態(tài)及其與母碼G的對應(yīng)關(guān)系，有助于上述識別問題第3步的快速解決。本文嘗試從簡單的物理意義出發(fā)，建立兩者的對應(yīng)關(guān)系模型，推導(dǎo)其數(shù)學(xué)表示形式，以作為刪除卷積碼識別問題的補充。

2　問題描述及符號定義

刪除卷積碼是一種由己知卷積碼構(gòu)造而來的高碼率卷積碼，具有構(gòu)造簡單、碼率靈活和譯碼器可以通用等優(yōu)點。

給定(n，k，) m卷積碼的多項式生成矩陣

式中：gi，j(D)=gi，j0D0+gi，j1D1+…+gi，jmDm為生成多項式，i=1，2，…，k，j=1，2，…，n，D表示延遲運算。因此，編碼過程可記為

式中：m(D)為信息序列；c(D)為編碼序列。如果給定擴展因子M＞1，使得在一個節(jié)拍內(nèi)向編碼器輸入信息比特數(shù)由原來的k個擴展為Mk個，則輸出編碼比特數(shù)將由原來的n個擴展為Mn個。此時，(n，k，m)卷積碼將等效于(Mn，Mk，m')擴展卷積碼，其生成多項式矩陣可表示為

刪除卷積碼即是在C[M]基礎(chǔ)上，結(jié)合事先給定的刪除圖樣P，對輸出序列中特定比特予以刪除而得到的。P是一個規(guī)模為n×M的二元矩陣，其中1的個數(shù)為N，對應(yīng)予以保留的比特位置。最終，可以得到碼率為kp/np=N/kM的(np，kp，mp)刪除卷積碼CP。圖1給出了以上構(gòu)造流程及符號定義。

圖1　刪除卷積碼構(gòu)造流程Fig.1 The generating form of Punctured convo1utiona1 code

擴展卷積碼等效生成矩陣的表述問題是指：已知母碼C的生成矩陣G(D)k×n，在給定擴展因子M＞1后，如何獲得擴展卷積碼C[M]的擴展生成矩陣G[M](D)Mk×Mn。Shen[15]最早研究了該問題，給出了一種復(fù)雜的表述形式；陳發(fā)新[16]以示例的形式，演算了當(dāng)C為(n，1，m)時的計算過程。本文將從基本物理意義出發(fā)，系統(tǒng)建立(n，1，m)?(Mn，M，m)、(n，k，m)?(Mn，Mk，m)生成矩陣的統(tǒng)一表述模型。

3　(n,1,m)的擴展卷積碼生成矩陣

設(shè)母碼C記作(n，1，m)，其擴展卷積碼C[M]記作(Mn，M，m)。

(1)當(dāng)輸入序列為足夠長序列[100…0]時，由編碼公式(2)可知，序列c(D)可表示為

用圖2表示時可見，編碼器的n個支路分別依次輸出G(D)中n個支路抽頭多項式的系數(shù)。

圖2　(n，1，m)卷積碼的第1類輸出情況Fig.2 The 1st outPut situation of(n，1，m)convo1utiona1 code

同樣，將輸入序列串并轉(zhuǎn)換，則c[M]可表示為

用圖3表示可見，編碼器的Mn個支路分別依次輸出G[M](D)第一行Mn個支路抽頭多項式的系數(shù)。

圖3　(Mn，M，m')卷積碼的第1類輸出情況Fig.3 The 1st outPut situation of(Mn，M，m')convo1utiona1 code

比較圖2和圖3，可以直觀地確認G(D)各支路與G[M](D)第一行各支路的系數(shù)對應(yīng)關(guān)系。首先觀察圖3支路c1，可得如下關(guān)系式：

式中：g1，0，g1，M，…，g1，M分別表示G(D)中子生成多項式g1(D)內(nèi)第0，M，…，nM個系數(shù)；g1，10，g1，11，…，g1，1n分別表示G[M](D)中子生成多項式g(D)內(nèi)第0，1，…，n個系數(shù)。顯然，g1，10=g1，0，g1，11=g1，M，…，g1，1n=g1，nM，即g(D)的系數(shù)相當(dāng)于從中g(shù)1(D)第0個系數(shù)處開始的M次采樣。

以此類推，有

的系數(shù)相當(dāng)于分別從G (D )中g(shù)1(D )的第0，1，…，M-1個系數(shù)處開始的M次采樣。

繼續(xù)討論圖3支路c2，可得如下多項式：

即G[M](D)中g(shù)(D)系數(shù)相當(dāng)于從G(D)中g(shù)2(D)第0個系數(shù)處開始的M次采樣。以此類推，我們可最終歸納出G[M](D)中g(shù)(D)，j∈[1，nM]的統(tǒng)一表述：

(2)當(dāng)輸入序列為足夠長序列[010…0]時，對于C，輸出序列

可用圖4表示?？梢?，編碼器的n個支路分別依次輸出G(D)中n個支路抽頭多項式的系數(shù)，不過與圖2相比存在一個節(jié)拍的延遲。

圖4　(n，1，m)卷積碼的第2類輸出情況Fig.4 The 2nd outPut situation of(n，1，m)convo1utiona1 code

而對于C[M]，輸出序列

可用圖5表示?？梢?，編碼器的Mn個支路分別依次輸出G[M](D)第二行Mn個支路抽頭多項式的系數(shù)。

圖5　(Mn，M，m')卷積碼的第2類輸出情況Fig.5 The 2nd outPut situation of(Mn，M，m')convo1utiona1 code

使用與前述類似的歸納總結(jié)方法，我們直接給出G[M](D)中g(shù)(D)(j∈[1，nM])的統(tǒng)一表述：

(3)換用其他諸如[0010…0]、[00010…0]形式的輸入序列，我們可最終獲得如下定理。

定理1 (n，1，m)卷積碼及其擴展卷積碼(Mn，M，m')的生成多項式具有如下變換方式：

式中：α=(j-1) mod n+1；β=?[j-(i-1) n -1]/n」；m'=「(m+2)/M?-1。即G[M](D)中g(shù)[i，Mj](D)系數(shù)相當(dāng)于從G(D)中g(shù)α(D)的第β個系數(shù)處開始的M次采樣，且當(dāng)β+ln＜0或β+ln＞m時，gα，β+ln=0。

該定理可看作Shen[15]和陳發(fā)新[16]結(jié)論的另一種等效表述，并更具實用意義。

4　(n,k,m)的擴展卷積碼生成矩陣

運用同樣的分析方法，本節(jié)討論(n，k，m)卷積碼C的生成矩陣G(D)與(Mn，Mk，m)卷積碼C[M]的生成矩陣G[M](D)兩者間的統(tǒng)一表述問題。

(1)設(shè)一次性輸入足夠長序列[10…0]，對于C，輸出序列

用圖6表示時可見，編碼器的n個支路分別依次輸出G(D)第一行各個抽頭多項式的系數(shù)。

圖6　(n，k，m)卷積碼的第1類輸出情況Fig.6 The 1st outPut situation of(n，k，m)convo1utiona1 code

用圖7表示時可見，編碼器的Mn個支路分別依次輸出G[M](D)第一行各個抽頭多項式的系數(shù)，

圖7　(Mn，Mk，m)卷積碼的第1類輸出情況Fig.7 The 1st outPut situation of(Mn，Mk，m)convo1utiona1 code

比較圖6和圖7的輸出序列，可獲得G[M](D)中g(shù)(D)(j∈[1，nM])的統(tǒng)一表述：

(2)當(dāng)輸入序列為足夠長序列[010…0]，對于C，輸出序列

用圖8表示時可見，編碼器的n個支路分別依次輸出G(D)第二行各個抽頭多項式的系數(shù)。

圖8　(n，k，m)卷積碼的第2類輸出情況Fig.8 The 2nd outPut situation of(n，k，m)convo1utiona1 code

用圖9表示時可見，編碼器的Mn個支路分別依次輸出G[M](D)第二行各個抽頭多項式的系數(shù)。

圖9　(Mn，Mk，m)卷積碼的第2類輸出情況Fig.9 The 2nd outPut situation of(Mn，Mk，m)convo1utiona1 code

通過換用其他輸入序列，可最終獲得如下定理。

定理2 (n，k，m)卷積碼及其擴展卷積碼(Mn，Mk，m')生成多項式具有如下變換方式：

式中：α=(i-1) mod k+1；β=(j-1) modn+1；γ=[j-(i-1)/k」n -1]/n」；m'=(m+2)/M-1。即G[M](D)中g(shù)(D)系數(shù)相當(dāng)于從G(D)中g(shù)α，β(D)的第γ個系數(shù)處開始的M次采樣，且當(dāng)γ+ln＜0或γ +ln＞m時，gα，βγ+ln=0。

顯然，定理2是定理1的加強。

5　驗證

式中：n=2；k=1；m=6。設(shè)擴展因子M=3，分別使用定理1和定理2，均可得C[]3的生成矩陣

與熟知的(4，3，) 2刪除卷積碼生成矩陣完全相同。

例2 考慮(3，2，) 3卷積碼C及其生成矩陣

式中：n=3；k=2；m=3。設(shè)定擴展因子M=2，使用定理2，可得C[]2生成矩陣

6　結(jié)束語

本文研究了刪除卷積碼識別問題中的重要子課題，即卷積碼母碼與擴展卷積碼生成矩陣的統(tǒng)一表述問題。從編碼器輸入輸出的基本物理意義出發(fā)，先后分析和建立了(n，1，m)?(Mn，M，m)和(n，k，m)?(Mn，Mk，m)的編碼序列輸出模型，歸納和證明了其生成矩陣的統(tǒng)一表述定理，并進行了相應(yīng)驗證計算。本文所給出的計算方法可用于加速刪除卷積碼識別刪除圖樣的遍歷過程，也可應(yīng)用于母碼生成矩陣的快速恢復(fù)。

[1] RICE B.Determining the Parameter of a rate 1/n convo-1utiona1 encoder over GF(q)[C]//Proceedings of the 3rd Internationa1 Conference on Finite Fie1ds and APP1ications.G1asgow，USA：IEEE，1995：1-5.

[2] FILIOL E.Reconstruction of convo1utiona1 encoders over GF(q)[J].Lecture Notes in ComPuter Science，1997 (1355)：101-109.

[3] 鄒艷，陸佩忠.關(guān)鍵方程的新推廣[J].計算機學(xué)報，2006，29(5)：711-718.

ZOU Yan，LU Peizhong.A new genera1ization of key equation[J].Chinese Journa1 of ComPuters，2006，29(5)：711-718.(in Chinese)

[4] 劉建成，楊曉靜.基于求解校驗序列的(n，1，m)卷積碼盲識別[J].電子與信息學(xué)報，2012，34(10)：2363-2368.

LIU Jiancheng，YANG Xiaojing.B1ind recognition of(n，1，m)convo1utiona1 code based on so1ving check-sequence[J].Journa1 of E1ectronics&Information Techno1-ogy，2012，34(10)：2363-2368.(in Chinese)

[5] 楊曉靜，劉建成，張玉.基于求解校驗序列的(n，k，m)卷積碼盲識別[J].宇航學(xué)報，2013，2013(4)：568-573.

YANG Xiaojing，LIU Jiancheng，ZHANG Yu.B1ind recognition of(n，k，m)convo1utiona1 codes based on so1ving check-sequence[J].Journa1 of Astronautics，2013，2013 (4)：568-573.(in Chinese)

[6] WANG F H，HUANG Z T，ZHOU Y.A method for b1ind recognition of convo1ution code based on Euc1idean a1gorithm[C]//Proceedings of 2007 Internationa1 Conference on Wire1ess Communications Networking and Mobi1e ComPuting.Shanghai：IEEE，2007：1414-1417.

[7] XIE H，CHAI X M，WANG F H，et a1.A method for b1ind identification of rate 1/2 convo1utiona1 code based onImProved euc1idean a1gorithm[C]//Proceedings of 2012 Internationa1 Conference on Signa1 Processing Proceedings.Beijing：IEEE，2012：1307-1310.

[8] MARAZIN M，GAUTIER R，BUREL G.Dua1 code method

for b1ind identification of convo1utiona1 encoder for cognitive radio receiver design convo1utiona1 encoder for cognitive radio receiver design[C]//Proceedings of 2009 GLOBECOM.Hono1u1u，Hawaii，USA：IEEE，2009：1-6.

[9] DINGEL J，HAGENAUER J.Parameter estimation of a convo1utiona1 encoder from noisy observations[C]//Proceedings of 2007 IEEE Internationa1 SymPosium on Information Theory.Nice：IEEE，2007：1776-1780.

[10] BARBIER J，SICOT G，HOUCKE S.A1gebraic aPProach for the reconstruction of 1inear and convo1utiona1 error correcting codes[J].Internationa1 Journa1 of APP1ied Mathematics and ComPuter Sciences，2006，2(3)：113-118.

[11] 張立民，劉杰，鐘兆根.(n，1，m)遞歸系統(tǒng)卷積碼的盲識別[J].電訊技術(shù)，2014，54(9)：1220-1225.

ZHANG Limin，LIU Jie，ZHONG Zhaogen.B1ind recognition of(n，1，m)recursive system convo1utiona1 code [J].Te1ecommunication Engineering，2014，54(9)：1220-1225.(in Chinese)

[12] 陸佩忠，沈麗，鄒艷.刪除卷積碼的盲識別[J].中國科學(xué)，2005，35(2)：173-185.

LU Peizhong，SHEN Li，ZOU Yan.B1ind recognition of Punctured convo1utiona1 codes[J].Science in China Series E-Information Sciences，2005，35(2)：173-185. (in Chinese)

[13] CLUZEAU M，F(xiàn)INIASZ M.Reconstruction of Punctured convo1ution codes[C]//Proceedings of 2009 IEEE Information Theory WorkshoP.Seou1，Korea：IEEE，2009：546-550.

[14] MARAZIN M，GAUTIER R，BUREL G.A1gebraic method for b1ind recovery of P unctured convo1utiona1 encoders from an erroneous bitstream[J].Institution of Engineering and Techno1ogy，2012，6(2)：122-133.

[15] SHEN B Z，PATAPOUTIAN A，MCEWEN P A.Punctured recursive convo1utiona1 encoders and their aPP1ications in turbo codes[J].IEEE Transactions on Information Theory，2001，47(6)：2300-2320.

[16] 陳發(fā)新.刪除卷積碼生成矩陣及最佳信息恢復(fù)式的求法[J].無線電通信技術(shù)，2009(2)：5-10.

CHEN Faxin.A deducing method of generator matrix and the bPest information restoration matrix of Punctured convo1utiona1 codes[J].Radio Communications Techno1-ogy，2009(2)：5-10.(in Chinese)

包 昕(1986—)，男，四川成都人，2011年于盲信號處理重點實驗室獲碩士學(xué)位，現(xiàn)為博士研究生，主要研究方向為信道編碼和衛(wèi)星通信；

BAO Xin was born in Chengdu，Sichuan Province，in 1986.He received the M.S.degree from Nationa1 Key Laboratory on B1ind Signa1s Processing in 2011.He is current1y working toward the Ph.D. degree.His research concerns channe1 coding and sate11ite communication.

Emai1：funandaxian@foxmai1.com

游 凌(1971—)，男，成都人，2001年于盲信號處理重點實驗室獲工學(xué)博士學(xué)位，主要研究方向為盲信息處理。

YOU Ling was born in Chengdu，Sichuan Province，in 1971.He received the Ph.D.degree from Nationa1 Key Laboratory on B1ind Signa1s Processing in 2001.His research concerns b1ind signa1 Processing.

Emai1：YouLing2001@163.com

A Unified Description of Generator Matrix of Expansion Convolutional Codes

BAO Xin，YOU Ling
(Nationa1 Key Laboratory on B1ind Signa1s Processing，Chengdu 610041，China)

In order to get enough Priori know1edge about the exPansion convo1utiona1 codes in the Process of b1ind recognition of Punctured convo1utiona1 codes，a method for describing the unified generator matrix of the mother code and the exPansion convo1utiona1 codes is ProPosed.Through ana1yzing the basic Physic PrinciP1e of the re1ationshiP between the inPut and the outPut of encoding，the method first sets(n，1，m) and(n，k，m)convo1utiona1 codes as the mother code，then constructs a corresPondence coefficient mode1 of the Po1ymerization of the exPansion convo1utiona1 coding，and fina11y introduces and Proves a unified descriPtion theorem about the generator matrix of the exPansion convo1utiona1 codes.The verification shows that the theorem rea1izes the fast comPutation of the exPansion generator matrix and is ab1e to he1P to exhaustive1y search and reconstruct the mother generator matrices and the Puncturing Patterns.

b1ind recognition；Punctured convo1utiona1 codes；mother codes；exPansion convo1utiona1 code；generator matrix

TN911.22

A

1001-893X(2016)03-0267-06

10.3969/j.issn.1001-893x.2016.03.006

2015-08-26;

2015-12-04 Received date:2015-08-26;Revised date:2015-12-04

**通信作者:funandaxian@foxmai1.com Corresponding author:funandaxian@foxmai1.com