王偉年 彭 華 董 政

(解放軍信息工程大學，河南鄭州 450002)

1 引言

在現(xiàn)代數(shù)字通信系統(tǒng)中，糾錯編碼技術常用來糾正隨機獨立錯誤，但是對于由多徑衰落、同頻干擾、脈沖干擾等造成的突發(fā)錯誤[1]，糾錯編碼技術無法進行糾正。為抵抗突發(fā)錯誤，實際通信過程中往往會將糾錯編碼與數(shù)據(jù)交織技術進行級聯(lián)。交織技術利用時間分集的思想，能夠將連續(xù)突發(fā)錯誤離散成單個隨機錯誤，使得糾錯編碼技術能夠有效發(fā)揮作用，保證通信的可靠進行[2]。

在非合作通信領域，第三方截獲到信號之后，首先就要進行解調得到比特流數(shù)據(jù)。然而，要想從信號層進入信息層，進一步獲取有價值的信息，就必須進行信道編碼分析[3]，得到比特流數(shù)據(jù)的編碼方式及參數(shù)，而其中交織參數(shù)識別分析是難點之一。

最常見的交織方式有矩陣交織[4]、卷積交織[5]和隨機交織。矩陣交織和卷積交織均可以通過遍歷交織參數(shù)進行識別，這里不再贅述。而隨機交織識別比較困難，無法通過參數(shù)遍歷方法解決，且目前已有的文獻都是針對Turbo碼中偽隨機交織的識別，鮮有文獻涉及包含Turbo碼在內的非特定類型編碼數(shù)據(jù)的隨機交織參數(shù)識別。Turbo碼中偽隨機交織參數(shù)識別的方法主要有文獻[6-9]：文獻[6]提出了一種利用多樣本數(shù)據(jù)逐位恢復交織的識別算法，首先對每個交織位置列出多個候選，計算由每個候選帶給編碼器的平均信息熵，然后設定合理門限對候選進行排除，最終得到整個交織關系；文獻[7]提出了一種基于BCJR譯碼狀態(tài)概率分布的方法，該方法假設前面i-1個交織關系已知，遍歷求得各候選位置的狀態(tài)概率，最大狀態(tài)概率對應的位置即第i個交織位置；文獻[8]利用SISO譯碼器軟輸出之間的互相關矩陣與交織矩陣的關系，并結合譯碼進行迭代，完成交織關系的識別。該方法抗誤碼能力較強，并且適用于任意交織方式；文獻[9]提出一種基于校驗方程平均符合度的識別算法。首先給出了校驗方程平均符合度的定義，然后以校驗方程平均符合度取到最大值為目標，逐步識別交織關系，最終得到整個交織關系。該算法不僅有較強的抗誤碼能力，且計算復雜度較低。

但上述算法要求編碼結構已知，且信息序列和校驗序列能夠分開處理，而其他類型編碼數(shù)據(jù)的隨機交織通常是信息與校驗全部進行交織，且編碼結構完全未知，此情況下上述算法會完全失效。即上述算法僅適用于Turbo碼的偽隨機交織，對于其他類型編碼數(shù)據(jù)的隨機交織關系求解無法適用。針對此問題，本文提出一種基于搜索小重量向量的交織及編碼類型識別算法：利用Canteaut-Chabaud算法[10]與LDPC譯碼進行迭代求得全部小重量校驗向量，再通過所提出的兩種統(tǒng)計量判斷交織存在性及編碼類型，即利用搜索得到的校驗向量判斷交織存在性及編碼類型。交織后碼字雖然信息與校驗序列完全打亂，但校驗關系依然存在，只是對應的位置發(fā)生了改變，所以可以將每個碼字看成是定碼長的分組碼且校驗向量可以搜索得到，再利用LDPC譯碼能夠進一步降低碼字誤碼率。由于使用軟信息時LDPC譯碼效果更佳，所以本文后面進行譯碼時利用軟解調序列。本文接下來的內容安排如下：第2節(jié)對誤碼條件下交織及編碼類型識別問題進行描述；第3節(jié)介紹低重量校驗向量搜索過程：Canteaut-Chabaud算法與LDPC譯碼進行迭代處理；第4節(jié)提出校驗向量的兩種度量，判斷交織存在性以及編碼類型；仿真實驗結果在第5節(jié)中展示；末節(jié)將進行一些總結和討論。

2 問題描述

本節(jié)描述基于軟解調序列的交織及編碼類型識別問題，發(fā)射端糾錯交織結構如圖1所示。

用ci表示交織前的碼字，大小為1×n，hk表示交織前校驗向量，大小為1×n，則有

(1)

(2)

(3)

由式(3)可知，碼字交織后的校驗向量僅僅是1元素的位置發(fā)生了變化，校驗向量數(shù)目完全沒有改變，交織碼字的約束關系依然穩(wěn)定存在，因此仍可以從識別校驗向量的角度出發(fā)對交織后的碼字進行識別。本文的編碼類型識別問題便是根據(jù)搜索得到的校驗向量判斷交織的存在性以及編碼類型，為進一步識別交織關系提供依據(jù)。

為不失一般性，這里假設映射為簡單的BPSK映射(0?+1,1?-1), 信道為加性高斯白噪聲信道，則接收序列ri=zi+ei, 由于圖1中省去了信號層面上的調制過程，因此軟解調序列認為是接收序列ri，下面的所有過程均是基于軟解調序列ri。

圖1 發(fā)射端糾錯交織結構

3 校驗向量搜索

3.1 碼字矩陣變換

假設接收到M幀碼字序列r=(r1,r2,...,rM)，其中ri=(ri,1,ri,2,...,ri,n)i=1,2,...,M,n代表每幀碼字長度，相應的硬判決序列v=(v1,v2,…,vM)，vi=(vi,1,vi,2,…,vi,n)。隨機選取其中的N幀碼字，組成矩陣G如下：

(4)

用R(X)表示由矩陣X的行向量張成的線性空間，用C表示由此N幀碼字線性組合而成的碼空間，則有R(G)=C；用H表示矩陣G的對偶矩陣(校驗矩陣)，則有

R(H)=C⊥=R(G)⊥

(5)

其中C⊥表示C在GF(2)n中的正交補空間，或稱對偶空間(Dual Space)。

對G進行高斯約旦行消元以及列調換操作，可將其化簡至系統(tǒng)形式的矩陣：

(6)

其中，k表示所選N幀碼字中線性無關的碼字數(shù)目。

利用式(6)可進一步可得到G的對偶矩陣的系統(tǒng)形式：

(7)

碼字無誤碼時，H的行空間總是包含所有的校驗向量，理論上能夠從此空間中搜索出全部所需的校驗向量，具體如下：

k

k=k0時，R(G)=R(Gsys)=C=C0=R(G0)

3.2 校驗向量粗搜索

3.2.1小重量向量搜索

從3.1節(jié)可知，校驗向量可從H的行空間搜索得到，但當行空間的維數(shù)過高，空間中向量數(shù)目呈指數(shù)級增長，如何進行有效搜索就顯得尤為重要。

(8)

(9)

下面介紹比較經典的小重量向量搜索算法：Canteaut-Chabaud算法[10]，該算法能夠以迭代的方式快速找出輸入系統(tǒng)矩陣行空間的小重量向量，具體如下：

信息列標號集合I，包含k+1,k+2,…,n共n-k個元素。

所有列標號集合S，重量閾值t，小重量向量集合Φ=?，迭代次數(shù)Nc,1。

(3)從H1中隨機選取p行，計算和向量s1，將取值s1|L添加至集合C1；從H2中隨機選取p行，計算和向量s2，將取值s2|L添加至集合C2；

(4) 考察集合C1、C2中所有滿足s1|L=s2|L的(s1,s2)組合，若wt(s1|JL+s2|JL)≤t-2p，且h=s1+s2?Φ，則令Φ=Φ∪{h}；

上述算法參數(shù)包括σ、p、t和Nc,1，σ、p選取方法已由文獻[10]給出，這里不再贅述。由于實際編碼數(shù)據(jù)中校驗向量的重量都比較小，t可以取值小一些，這里取t≤10，Nc,1的選取可以根據(jù)計算量的限制進行進一步的設置。

3.2.2校驗向量剔除

(10)

(11)

3.3 校驗向量精確搜索

3.2節(jié)已經得到部分有效校驗向量，但數(shù)目較少且不同校驗向量之間很可能存在線性關系，這樣會對后面的識別產生不利影響，因此需要對校驗向量進行精確搜索。

數(shù)目較少是碼字存在誤碼所導致，因此必須首先降低碼字的誤碼率。雖然碼字存在交織，編碼結構被完全打亂，但碼字比特之間的約束關系仍然存在，已經搜索出的校驗向量正是反映了這一點。而LDPC譯碼方法不要求編碼方式必須是LDPC編碼，只需校驗向量已知，便可以根據(jù)校驗關系進行有效譯碼，因此可以根據(jù)其原理對交織后碼字進行譯碼。

傳統(tǒng)的LDPC譯碼算法是基于Tanner圖進行交叉處理，在每次迭代中都會多次涉及同一校驗向量，計算復雜度較高；而專利[11]中的LDPC譯碼算法，由于對校驗方程分開進行處理，每次迭代中僅涉及一次校驗方程，因此計算復雜度較低。但兩種方法譯碼性能基本相當，因此，本文采用專利[11]中的譯碼算法，在保證譯碼性能的同時有效降低了計算量。

校驗向量之間存在線性關系會對第4節(jié)中的統(tǒng)計量產生不利影響，導致識別率降低，因此必須降低存在線性關系的可能性。3.2節(jié)已經搜索得到的校驗向量碼重都較低，但肯定存在最低碼重，其他高碼重校驗向量很可能是由此低碼重校驗向量線性組合而來，因此在接下來的搜索中可以通過僅搜索最低碼重的校驗向量來降低存在線性關系的可能性。

由以上分析，校驗向量精確搜索過程如下：

(1)利用粗搜索得到的校驗向量對碼字進行LDPC譯碼；

(2)利用粗搜索得到的校驗向量確定最低碼重tmin，令t=tmin，將Canteaut-Chabaud算法中第(4)步的判斷條件wt(s1|JL+s2|JL≤t-2p修改為wt(s1|JL+s2|JL=t-2p；

(3)粗搜索過程與LDPC譯碼進行迭代。

3.4 算法總結

綜合以上3小節(jié)的內容，可將校驗向量搜索算法總結如下：

初始化： 接收碼字總數(shù)目M，碼長n，每次搜索選取碼字數(shù)目N，Canteaut-Chabaud算法中迭代次數(shù)Nc,1，行數(shù)p=1，列數(shù)σ=10，重量閾值t，小重量向量集合Φ=?。粗搜索過程中碼字選取迭代次數(shù)Nc,2,LDPC譯碼與粗搜索過程迭代次數(shù)Nc,3。

(1)從M個碼字中隨機選取N個組成矩陣，變換至對偶矩陣Hsys；

(2)利用Canteaut-Chabaud算法對Hsys行空間進行搜索，篩選剔除后得到部分有效校驗向量，(1)(2)過程迭代進行Nc,2次，得到元素盡可能多的校驗向量集合Φ；

(3)利用集合Φ中元素對M個碼字進行LDPC譯碼，并更新重量閾值t=tmin，去掉集合Φ中重量大于tmin的元素；

(4)將Canteaut-Chabaud算法中wt(s1|JL+s2|JL)≤t-2p改為wt(s1|JL+s2|JL)=t-2p，重復前三個過程Nc,3-1次，得到最終的小重量校驗向量集合Φ。

4 交織及編碼類型識別

第3節(jié)已經搜索得到了大部分的校驗向量，本節(jié)將對校驗向量進行統(tǒng)計分析，根據(jù)統(tǒng)計量的結果判卷交織存在性以及編碼類型。

實際通信中交織后的碼字往往是由多個短碼字合并到一起經過交織而成，因此交織后碼字的校驗向量始終能反映出原碼的特點，通過找出并分析這些特點，能夠確定編碼類型，為交織關系分析提供依據(jù)。

4.1 交織存在性識別

這里提出校驗向量的一種統(tǒng)計量：跨度S，代表校驗向量中元素1位置的分布情況。設交織前碼字校驗向量hk中元素1的位置集合為{c1,c2,…,cwk}，則hk的跨度Sk定義為

Sk=span(hk)=max{c1,c2,…,cwk}-

min{c1,c2,…,cwk}+1

(12)

(13)

若原碼為分組碼，則最低碼重校驗向量數(shù)目y滿足

(14)

(15)

對于原碼為分組碼，另有

(16)

從1,2,…,n中任取wmin個元素組成向量，其跨度為i，記Qi為跨度為i的選取方法總數(shù)目，則Qi滿足

(17)

(18)

從而可得到交織后校驗向量的歸一化平均跨度。

4.2 編碼類型識別

(1)更新Φ=ΦΦi，即從Φ中除去包含在Φi中的元素，執(zhí)行步驟(2)；

(2)統(tǒng)計Φ中元素與Φi中元素是否有相同位置的1。若存在，則從Φ中剔除，添加至Φi，重復執(zhí)行步驟(2)；若元素不存在且Φ≠?，則執(zhí)行步驟(3)；若Φ=?，結束；

(3)更新i=i+1，將Φ中第一個元素添加至Φi，執(zhí)行步驟(1)。

經過以上步驟，可將校驗向量集合Φ分為i個集合，各個集合之間的元素沒有相同位置的1，可以認為各個集合之間相互獨立。

這里將i的大小作為校驗向量集合的一種統(tǒng)計量：離散度D，用來描述集合中向量之間的離散程度。當搜索得到的校驗向量比較完備時，對于原碼為卷積碼，由于校驗向量可以通過移位原碼碼長依次得到，因此相鄰校驗向量之間肯定有相同位置的1元素，從任一個校驗向量出發(fā)向外擴展(即前面的分類過程)，最后總能包含所有校驗向量，即離散度D=1；對于原碼為分組碼，由于不同碼字間完全獨立，校驗向量只有屬于同一個碼字時才會有相同位置的1，因此經過分類之后，離散度等于原碼字個數(shù)，即D=n/n′。

因此可以通過離散度D的大小來判斷編碼類型，若D=1，則可認為編碼方式為卷積碼，否則編碼方式為分組碼。

4.3 復雜度分析

本文整體算法包括校驗向量搜索、交織存在性識別和編碼類型識別，其中校驗向量搜索過程計算復雜度較另外兩個過程要高得多，因此下面主要針對校驗向量搜索過程進行詳細分析，設原碼字最低碼重校驗向量數(shù)目為y，其他參數(shù)具體意義見3.4節(jié)。

其次是校驗向量精確搜索過程：該過程采用專利[11]中的LDPC譯碼算法，迭代一次每個校驗向量涉及Mtmin次實數(shù)域乘法和加法運算，同時調用雙曲正切函數(shù)tan(·)和反雙曲正切函數(shù)atan(·)各Mtmin次，由于每次譯碼前識別得到的校驗向量并不完整，所以每次譯碼運算量小于y個校驗向量全部參與譯碼時的運算量。

通過以上分析，考慮到各種迭代次數(shù)，整體算法運算量如下：二進制運算次數(shù)為Nc,3·Nc,2·Nc,1·W1+W2次，實數(shù)域乘法和加法運算次數(shù)少于Nc,3·y·Mtmin次，雙曲正切函數(shù)tan(·)和反雙曲正切函數(shù)atan(·)調用次數(shù)少于Nc,3·y·Mtmin次。

5 仿真實驗及分析

本節(jié)仿真實驗以1/2碼率卷積碼和(15,11)漢明碼為例展開測試。其中卷積碼生成多項式為g1(x)=1+x+x2+x5，g2(x)=1+x+x3+x4+x6，漢明碼生成多項式為G=[1 1 0 0;1 0 1 0;0 1 1 0;1 1 1 0;1 0 0 1;0 1 0 1;1 1 0 1;0 0 1 1;1 0 1 1;0 1 1 1; 1 1 1 1]。利用MATLAB產生5000幀長度為500的卷積碼，5100幀長度為510的分組碼(漢明碼)，通過產生1,2,…,500與1,2,…,510的隨機排列，分別對卷積碼和分組碼進行隨機交織，后面實驗均基于此數(shù)據(jù)進行。

表1給出了Nc,1=16384，Nc,2=5，p=0.003，t=10時，不同碼字選取數(shù)目N條件下，卷積碼數(shù)據(jù)粗搜索過程得到的校驗向量數(shù)目變化情況；表2給出了Nc,1=16384，Nc,2=5，p=0.005，t=10時，不同碼字選取數(shù)目N條件下，粗搜索過程得到的校驗向量數(shù)目變化情況。由表1和表2可以看出，碼字選取數(shù)目N越小，(pwk)N越大，由式(9)可知有更多的校驗向量包含于Hsys的行空間，但相同條件下能夠搜索出的校驗向量數(shù)目卻不是越來越多，這是因為雖然Hsys的行空間包含有更多有效校驗向量，但Hsys的行空間向量數(shù)目卻越來越多，校驗向量的比例在不斷變小，要想搜索出更多必須增加迭代次數(shù)Nc,1及Nc,2，計算復雜度會越來越高。此外，表1和表2均表明(pwk)N在0.01附近時，能夠搜索出更多的校驗向量，(pwk)N過小或者過大，在相同計算復雜度情況下，搜索出的校驗向量數(shù)目均較少，不能對數(shù)據(jù)進行充分利用，因此需根據(jù)(pwk)N的大小進一步確定N的取值。

圖2給出了Nc,1=16384，Nc,2=10，t=10，(pwk)N∈[0.005,0.03]，誤碼率p分別為0.003，0.004，0.005條件下，卷積碼數(shù)據(jù)粗搜索過程得到的校驗向量數(shù)目變化曲線。從圖中可以看出，不同誤碼率下，(pwk)N的最優(yōu)值一直在變化，隨著誤碼率的降低，(pwk)N的最優(yōu)值一直在變大；且不同誤碼率下，(pwk)N即使取最優(yōu)值，相同迭代次數(shù)下搜索出的校驗向量數(shù)目差異也比較明顯，誤碼率越低，搜索得到的校驗向量數(shù)目越多，這與前面的分析一致。三種誤碼率下對應的(pwk)N最優(yōu)值分別為0.015，0.01，0.005，選取碼字數(shù)目分別為140，119，109。實際中可以通過計算接收碼字的噪聲方差σ2，并進一步計算誤碼率p，通過實驗找出該誤碼率對應的碼字選取數(shù)目N的最佳值。

圖2 校驗向量數(shù)目變化曲線

表1 p=0.003時不同N的實驗結果

表2 p=0.005時不同N的實驗結果

圖3 歸一化平均跨度變化曲線

在搜索得到的最低碼重校驗向量比例不同條件下，針對卷積碼和分組碼，β設置為0.4，各進行300次蒙特卡洛仿真實驗，得到交織識別正確率的變化曲線如圖4。從圖中可以看出，分組碼和卷積碼交織后的歸一化平均跨度比較穩(wěn)定，基本不隨校驗向量比例的變化而變化；歸一化平均跨度的取值始終高于檢測門限β且接近理論值0.78，交織存在性的識別率為100%。交織存在性識別效果較理想，主要是因為原始的所有校驗向量進行了隨機交織，得到的新校驗向量無論識別出多大比例，其隨機性一直存在，歸一化平均跨度值始終跟圖3比較接近，而原始校驗向量歸一化平均跨度值一般較小。由以上可知，對于交織存在性識別，本文提出的校驗向量歸一化平均跨度效果良好，能夠滿足實際需求。

圖4 交織存在性識別結果

圖5 編碼類型識別結果

實際中如果能夠識別出50%的校驗向量，經過LDPC譯碼之后，碼字誤碼率通常會降低很多，進一步利用前面的算法能夠識別出大部分校驗向量，則編碼類型識別結果不會出現(xiàn)錯誤。因此無法判斷編碼類型通常是由于碼字誤碼率過高，識別出校驗向量比例過低，即使利用LDPC譯碼進行迭代也無法進一步降低碼字誤碼率。

6 結論

本文針對誤碼情況下采用隨機交織碼字識別問題，提出了一種容錯能力較強的交織及編碼類型識別算法。該算法通過碼字矩陣變換，小重量向量搜索算法以及LDPC譯碼進行迭代，能夠識別出絕大部分的最低碼重校驗向量；并進一步提出校驗向量的兩種統(tǒng)計量，能夠對交織的存在性以及編碼類型進行有效判斷。仿真結果表明，本文算法容錯能力較高，能夠在誤比特率為0.006的條件下，實現(xiàn)交織及編碼類型的有效識別，克服了已有方法無法適用于隨機交織碼字識別的局限性，且本文算法復雜度在可以承受的范圍內，能夠適用于實際環(huán)境。另外，本文算法降低了碼字誤碼率且初步識別出編碼結構，能夠為進一步交織關系的識別提供明確方向與可靠依據(jù)。

[1] 解輝, 王豐華, 黃知濤. 卷積交織器盲識別方法[J]. 電子與信息學報, 2013, 35(8): 1952-1957.

Xie Hui, Wang Fenghua, Huang Zhitao. A method for blind recognition of convolutional interleaver[J]. Journal of Electronics & Information Technology, 2013, 35(8): 1952-1957.(in Chinese)

[2] Cao S, Chen J, Damask J N, et al. Interleaver technology: comparisons and applications requirements[C]∥Optical Fiber Communication Conference, Atlanta, USA, 2003: 1-9.

[3] 解輝, 黃知濤, 王豐華. 信道編碼盲識別技術研究發(fā)展[J]. 電子學報, 2013, 41(6): 1166-1176.

Xie Hui, Huang Zhitao, Wang Fenghua. Research progress of blind recognition of channel coding[J]. Acta Electronica Sinica, 2013, 41(6): 1166-1176. (in Chinese)

[4] Sicot G, Houcke S, Barbier J. Blind detection of interleaver parameters[J]. Signal Processing, 2009, 89(4): 450- 462.

[5] 甘露,劉宗輝,廖紅舒,等. 卷積交織參數(shù)的盲估計[J]. 電子學報,2011,39(9): 2173-2177.

Gan Lu, Liu Zonghui, Liao Hongshu, et al. Blind estimation of the parameters of convolutional interleaver[J]. Acta Electronica Sinica, 2011, 39(9): 2173-2177. (in Chinese)

[6] Cluzeau M, Finiasz M, Tillich J-P. Methods for the Reconstruction of Parallel Turbo Codes[C]∥Proc. IEEE Int. Symposium on Information Theory, Austin, Texas, USA, June 2010: 2008-2012.

[7] Jean-Pierre Tillich, Audrey Tixier, Nicolas Sendrier. Recovering the interleaver of an unknown[C]∥Proc. IEEE Int. Symposium on Information Theory, 2014.

[8] 劉駿,李靜,于沛東. 一種Turbo碼隨機交織器的迭代估計方法[J]. 通信學報,2015, 36(6): 205-210.

Liu Jun, Li Jing, Yu Peidong. Iterative estimation method for random interleaver of Turbo codes[J]. Journal on Communications, 2015, 36(6): 205-210. (in Chinese)

[9] 劉駿, 李靜, 彭華. 基于校驗方程平均符合度Turbo碼交織器估計[J]. 電子學報, 2016, 44(5):1213-1218.

Liu Jun, Li Jing, Peng Hua. Estimation of Turbo-code interleaver based on average conformity of parity-check Equation[J]. Acta Electronica Sinica, 2016,44(5):1213-1218. (in Chinese)

[10] Canteaut A, Chabaud F. A new algorithm for finding minimum weight words in a linear codes: application to primitive narrow-sense BCH codes of length 511[J]. IEEE Transactions on Information Theory, 1998, 44(1): 367-378.

[11] Patrick A.Owsley. LDPC Architecture[P]. United States Patent: US7353444, 2005- 05- 06.