包 昕,游 凌

(盲信號(hào)處理重點(diǎn)實(shí)驗(yàn)室，成都　610041)

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

包 昕**,游 凌

(盲信號(hào)處理重點(diǎn)實(shí)驗(yàn)室，成都610041)

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

盲識(shí)別;刪除卷積碼;母碼;擴(kuò)展卷積碼;生成矩陣

引用格式:包昕，游凌.擴(kuò)展卷積碼生成矩陣的統(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)想。半個(gè)世紀(jì)以來(lái)，隨著其編碼、譯碼技術(shù)的深入研究，卷積碼已被廣泛應(yīng)用于衛(wèi)星、深空等多種通信系統(tǒng)中，成為CCSDS、IESS、DVB-S等協(xié)議/標(biāo)準(zhǔn)中的信道編碼解決方案。

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

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

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

2　問(wèn)題描述及符號(hào)定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

以此類(lèi)推，有

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

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

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

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

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

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

而對(duì)于C[M]，輸出序列

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

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

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

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

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

式中：α=(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)的第β個(gè)系數(shù)處開(kāi)始的M次采樣，且當(dāng)β+ln＜0或β+ln＞m時(shí)，gα，β+ln=0。

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

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

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

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

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

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

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

圖7　(Mn，Mk，m)卷積碼的第1類(lèi)輸出情況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)輸入序列為足夠長(zhǎng)序列[010…0]，對(duì)于C，輸出序列

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

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

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

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

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

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

式中：α=(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)的第γ個(gè)系數(shù)處開(kāi)始的M次采樣，且當(dāng)γ+ln＜0或γ +ln＞m時(shí)，gα，βγ+ln=0。

顯然，定理2是定理1的加強(qiáng)。

5　驗(yàn)證

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

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

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

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

6　結(jié)束語(yǔ)

本文研究了刪除卷積碼識(shí)別問(wèn)題中的重要子課題，即卷積碼母碼與擴(kuò)展卷積碼生成矩陣的統(tǒng)一表述問(wèn)題。從編碼器輸入輸出的基本物理意義出發(fā)，先后分析和建立了(n，1，m)?(Mn，M，m)和(n，k，m)?(Mn，Mk，m)的編碼序列輸出模型，歸納和證明了其生成矩陣的統(tǒng)一表述定理，并進(jìn)行了相應(yīng)驗(yàn)證計(jì)算。本文所給出的計(jì)算方法可用于加速刪除卷積碼識(shí)別刪除圖樣的遍歷過(guò)程，也可應(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].計(jì)算機(jī)學(xué)報(bào)，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] 劉建成，楊曉靜.基于求解校驗(yàn)序列的(n，1，m)卷積碼盲識(shí)別[J].電子與信息學(xué)報(bào)，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] 楊曉靜，劉建成，張玉.基于求解校驗(yàn)序列的(n，k，m)卷積碼盲識(shí)別[J].宇航學(xué)報(bào)，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)卷積碼的盲識(shí)別[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] 陸佩忠，沈麗，鄒艷.刪除卷積碼的盲識(shí)別[J].中國(guó)科學(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].無(wú)線電通信技術(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年于盲信號(hào)處理重點(diǎn)實(shí)驗(yàn)室獲碩士學(xué)位，現(xiàn)為博士研究生，主要研究方向?yàn)樾诺谰幋a和衛(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年于盲信號(hào)處理重點(diǎn)實(shí)驗(yàn)室獲工學(xué)博士學(xué)位，主要研究方向?yàn)槊ば畔⑻幚怼?/p>

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