劉 倩，張 昊，宋瑩炯，王 剛

（1.信息工程大學信息系統(tǒng)工程學院,河南鄭州 450001；2.信息工程大學密碼工程學院,河南鄭州 450001）

1 引言

信道編碼類型眾多，其中的LDPC（Low-Density Parity-Check）碼［1，2］由于其逼近香農(nóng)限的傳輸性能和強糾錯能力，以及適用于硬件并行運算的置信度傳播解碼算法被廣泛應用于各種通信標準中.LDPC 碼不同于其他線性碼，（如Hamming 碼、循環(huán)碼、卷積碼和Turbo 碼等），這類編碼由其稀疏校驗矩陣來確定，一般具有較長的碼長.由于計算復雜度或空間復雜度的原因，原本適用于短碼的編碼參數(shù)識別算法［3］很難再對LDPC碼起作用.因此，對LDPC 碼的識別分析方法自成一派.

目前對LDPC 碼的參數(shù)識別算法主要集中于閉集識別［4～8］，即信號接收方手里已有若干種LDPC 編碼方式構(gòu)成的集合，且發(fā)送方選取的編碼方式為集合中的一種，只需要利用接收碼字序列將編碼方式挑出即可.開集識別時，由于信號截獲方?jīng)]有任何先驗知識，識別難度更大導致研究成果較少［9～16］.已有工作中有基于對偶碼的方法，通過尋找具有一定的漢明重量（或小漢明重量）的對偶碼獲得校驗向量，與此同時恢復碼長、碼率和起點［9］.也有假設編碼長度、碼率及起點均已知，在此基礎(chǔ)上恢復稀疏校驗矩陣［10～13］.或者假設截獲信號序列長度足夠長，在此基礎(chǔ)上利用秩分析法（分析構(gòu)造碼字矩陣的秩率［14］或近似秩率［15，16］）估計碼長和起點，這兩種方法均是基于高斯列消元方法.近兩年還出現(xiàn)了利用秩的概率分布獲取正確的編碼長度和起點的算法［17，18］.算法中需要多次從編碼矩陣中隨機獲取方陣，計算它們的秩并得到其經(jīng)驗分布規(guī)律.如果其與已有的同階隨機方陣的秩的分布規(guī)律相同，則被認為是隨機方陣，此時碼長和起點不正確.否則便被認為具有某種代數(shù)結(jié)構(gòu)，此時碼長和起點正確.關(guān)于已有工作［14～18］的詳細介紹和對其原理及缺點的具體分析將在節(jié)2.4節(jié)中給出.

以上方法均要求截獲比特流的長度是足夠供信息截獲者進行分析的，但是，在信息對抗過程中，信息對抗方是被動接收信息，并不能保證截獲所得數(shù)據(jù)量充足，此時已有的方法全部失效.本文在截獲比特數(shù)量遠少于現(xiàn)有方法所需的比特數(shù)量的情況下（不含或含少量錯誤比特），基于碼字空間與其對偶空間的正交性、完整碼字比特間的線性相關(guān)性、矩陣乘積的秩不大于每個因子矩陣的秩等性質(zhì)，提出了一種估計LDPC 碼的碼長、起點等參數(shù)的矩乘秩減算法，并對算法的計算復雜度和正確識別概率進行了分析.

2 數(shù)學模型和理論基礎(chǔ)

2.1 符號說明

接下來在二元域F2上展開問題的研究.用C表示所采用的糾錯碼，n，k分別表示糾錯碼的碼長和維數(shù).信息向量和碼字向量等矢量分別用粗體u和c表示，變量用小寫斜體字母表示.大寫斜粗體字母A和AT分別表示碼字矩陣及其轉(zhuǎn)置，矩陣A的零空間記為Kel(A)，A(i，：)和A(：，i)分別表示矩陣A的第i行和第i列.W和W⊥分別代表糾錯碼碼字空間和其對偶空間.d表示正確的起點位置，l0和t0分別表示利用我們提出的算法得出的碼字長度和起點位置，l和t是在一定區(qū)間內(nèi)變化的變量，將截獲比特流在不同的起點t下按列數(shù)l排列成的碼字矩陣記為Dl，t.

2.2 碼字空間的封閉性及與其對偶空間的正交性

一般的線性分組碼的編碼方式是由生成矩陣定義：給定生成矩陣Gk×n，輸入由k個比特組成的信息塊u=(u1，u2，…，uk)，得到一個完整的碼字c=(c1，c2，…，cn)=u·Gk×n.已知Gk×n的行向量線性無關(guān)，分別記之為g1，g2，…，gk，則

可知所有碼字c均表示為生成矩陣行向量的線性組合，因此生成矩陣行向量張成一個k維線性空間，稱為碼字空間，記為W.當Gk×n為系統(tǒng)形式(Ik×k，Pk×(n-k))時，則生成系統(tǒng)碼.

若有兩個碼字ci=(ci1，ci2，…，cin)=ui·Gk×n和cj=(cj1，cj2，…，cjn)=uj·Gk×n，則

ci⊕cj=(ci1⊕cj1，ci2⊕cj2，…，cin⊕cjn)=(ui⊕uj) ·Gk×n仍然是一個合法碼字，因此碼字空間關(guān)于F2上的加法運算⊕封閉.

LDPC 碼是一種特殊的線性分組碼，僅由一個包含很少個1 的校驗矩陣H(n-k)×n的零空間所定義.因此當給定k個信息比特(u1，u2，…，uk)時，需要利用校驗矩陣求解n-k個校驗比特(uk+1，uk+2，…，un)，即系統(tǒng)碼字c=(c1，c2，…，cn)=(u1，u2，…，uk，uk+1，uk+2，…，un) 滿足c·HT=0，因此LDPC碼的碼字空間不僅關(guān)于⊕封閉，并且與其對偶空間具有正交性.而LDPC 碼的識別過程也正是基于這種關(guān)系.

2.3 高斯若當列消元法

高斯若當列消元法GJETP（Gauss-Jordan Elimination Through Pivoting），通過行置換和列變換將一個矩陣變換為下三角矩陣，文獻［14～16］均是在此基礎(chǔ)上給出各自的算法.先給出F2上GJETP 法實施的具體過程.

對于一個s×l階的矩陣A，i的變化范圍是從1 到min｛s，l｝.

（1）如果A的第i列的第i個元素為0，并且存在最小的j(j＞i)使得第j列的第i個元素為1，則交換A的第i列和第j列；

（2）如果A的第i列的第i個元素為0，并且不存在第j(j＞i)列其第i個元素為1，但有最小的j(j＞i)使得A的第j行中第i個元素為1，則交換A的第i行和第j行；

（3）如果A的第i列的第i個元素為1，則將其加到第i行中所有列數(shù)大于i的位置上為1 的列上.

2.4 已有工作和數(shù)學模型

在一個完整碼字中，校驗比特是某些信息比特的線性組合.如果接收比特足夠多，且由無誤碼比特序列構(gòu)建的矩陣A的每一行恰好為一個完整的碼字，則其列與列之間的比特服從相同的線性約束關(guān)系，因此至多只有k列線性無關(guān)，A的秩至多為k.在通過GJETP 將A變換為有n-k列全零列的矩陣的過程中，設列變換矩陣為Q.若編碼是系統(tǒng)碼，則存在Q=(Q1Q2)使得AQ1=VM×k，AQ2=0M×(n-k)，記作

圖1 當l ≠βn和l=βn時，矩陣A在形式上的差別

為了更好的做出對比，將矩陣的秩除以l得到歸一化秩率［14，15］，便可利用這兩種情況下歸一化秩率的不同表現(xiàn)來區(qū)分預設的編碼長度和起點是否正確.為了進一步提高算法的容錯能力，降低錯誤比特對碼字矩陣秩的影響，文獻［16］改為尋找矩陣的“近似秩”.其做法是利用GJETP 將碼字矩陣化成下三角階梯型矩陣后，尋找矩陣中列重大于某一閾值的列，其數(shù)目便為矩陣的近似秩.同樣地，近似秩歸一化后得到近似秩的歸一化秩率，將使得其取得最小值的矩陣的列數(shù)和起點視為正確的參數(shù).這里把文獻［14，15］中的方法叫做秩準則，把文獻［16］中的方法叫做近似秩準則，這兩種方法都為基于GJETP的秩分析法.

但在利用上述秩分析法獲取碼字長度和起點等參數(shù)的過程中，一般要求矩陣A的行數(shù)s大于其列數(shù)l.如果截獲碼字個數(shù)較少使得構(gòu)建的碼字矩陣的行數(shù)遠遠小于列數(shù)，則秩分析法失效.以秩準則為例，設碼字為(n，k)線性分組碼，截獲的碼字序列為Z，其中含有M個比特.假定碼字長度和起點分別為l和t，構(gòu)造碼字矩陣Dl，t，其中Dl，t的第i個行向量為在≤k的情況下分析問題.此時，如果l≠βn，相應的矩陣Dl，t為隨機矩陣，由于其行數(shù)遠小于列數(shù)，因此有rank(Dl，t)≤k.而當l=βn時，矩陣Dl，t是結(jié)構(gòu)矩陣，其行向量是至多k個線性無關(guān)的行向量（生成矩陣G的行向量）的線性組合，因此也有rank(Dl，t)≤k.此時無法由秩準則區(qū)分假定的碼字長度和起點是否正確.

近似秩準則［16］在估計編碼參數(shù)問題上表現(xiàn)突出.但是近似秩準則有一個要求，那就是截獲比特數(shù)量必須非常大，使得構(gòu)造的碼字矩陣為“高瘦型”.矩陣越高，近似秩才越準確，從而得出正確參數(shù)的概率也越大，并可以利用近似秩進一步確定校驗關(guān)系.而當碼字矩陣為方陣或者“矮胖型”矩陣時，則無法計算近似秩.因此近似秩準則在截獲比特數(shù)量較少時完全失效（高瘦型矩陣指的是其行數(shù)遠遠大于列數(shù)，矮胖型矩陣指的是其行數(shù)遠遠小于其列數(shù)）.

在利用隨機方陣秩的分布獲得編碼參數(shù)的做法［17，18］中，需要在構(gòu)造的碼字矩陣Dl，t中隨機選取行向量構(gòu)造出許多個方陣.計算方陣的秩得出其經(jīng)驗分布函數(shù)，然后將其與同階隨機方陣的秩的分布規(guī)律進行比較.如果分布規(guī)律相同，則判定預設碼字長度和起點不正確，如果不同則認為碼字長度和起點正確.但在構(gòu)造碼字矩陣為“矮胖型”的情況下，其行向量不可能構(gòu)造出方陣，因此算法［17，18］也失效.另一方面，算法需要做大量實驗統(tǒng)計不同設定碼長和起點下方陣的秩的分布規(guī)律，因此其計算量也是一個天文數(shù)字，在碼長較大時并不實用.

3 本文算法、原理及復雜度分析

在給出本文具體算法之前，先以定理的形式給出一個乘積矩陣的秩的性質(zhì)［19］.

定理1設矩陣A和B都是l階方陣，則有rank(AB)≤min{rank(A)，rank(B)}成立.容易將此結(jié)論推廣到n個方陣相乘的情形.即對n個方陣A1，A2，…，An，有

3.1 本文算法

為了解決在截獲比特數(shù)量較少的情況下編碼參數(shù)的識別問題，本文改變研究矩陣的秩的方式.注意到不管碼字個數(shù)有多么少，一個完整碼字中的比特間的線性約束關(guān)系總是存在的.因此，我們不去關(guān)心全部的校驗關(guān)系，而將注意力放在尋找滿足同一個校驗關(guān)系的比特上.在l=βn的情形下，設h=(h1，h2，…，hn) ∈W⊥，令集合

從矩陣Dl，t中隨機選取列構(gòu)建一個階的方陣Sl，設選取列的列標集合為θ.若有τ(h) ?θ，則Sl不滿秩.由于LDPC 碼的校驗向量的稀疏性，可知滿足同一個校驗的比特數(shù)目較少，只要這幾個比特所在列被選入Sl，Sl就不滿秩.若是幾個校驗關(guān)系中的比特所在列均被選入Sl，則Sl秩虧的更多，因此使得Sl秩虧的條件較容易達到.當從Dl中隨機選取p個方陣，分別記為Sl1，Sl2，…，Slp，作乘積得Sl1Sl2…Slp，由式（3）可得

這使得乘積矩陣Sl1Sl2…Slp的秩較小的概率大大提升.若l≠βn，則Dl，t為隨機矩陣，其列之間并不存在線性結(jié)構(gòu).隨機從中選取列組成的方陣Sl仍然是隨機矩陣，因此乘積矩陣Sl1Sl2…Slp也是隨機矩陣，其秩在一般情況下不會較小.在此分析基礎(chǔ)上，為了更好地區(qū)分兩種情形，定義歸一化秩率函數(shù)

在具體實施過程中，先估計l0，再將t0確定，提出了下面的矩乘秩減算法，如算法1所示.

注1關(guān)于隨機選取方陣的個數(shù)p的選擇問題.由式（4）可知，隨著p的增大，乘積矩陣的秩是單調(diào)不增的.只要出現(xiàn)一個乘因子矩陣的秩比較小，那么乘積矩陣的秩就會很小.但若Sl1，Sl2，…，Slp都是隨機矩陣，它們的乘積也是隨機矩陣，出現(xiàn)秩較小的概率較低.因此，隨著p的增大，在預設碼長正確和不正確兩種情況下，乘積矩陣的秩的差距進一步拉大，碼長和起點的正確識別概率也會提升（在理論分析部分詳細介紹）.但如果p的取值過大，則會使得計算矩陣乘法的次數(shù)較多，計算量顯著增加.所以，需要在識別概率和計算復雜度之間做一個權(quán)衡，選擇合適的p值.

注2關(guān)于起點所在位置對算法的識別概率的影響問題.在估計碼字長度的過程中，若預先設定的碼字長度l0正確，t0未知，則碼字矩陣Dl0的每一行由上一個碼字的l0-t0個比特和下一個碼字的t0個比特構(gòu)成.當t0的值靠近0 或者l0時，由于大部分比特在同一個碼字中，隨機選取的方陣中出現(xiàn)具有線性相關(guān)關(guān)系的列的可能性較大，此時更容易得到秩較小的矩陣，識別概率較高.當t0的值靠近時，每一個行向量中約一半的比特分別位于在上一個碼字和下一個碼字中，而兩個碼字中的比特之間一般不具有線性相關(guān)關(guān)系，因此隨機選取的方陣秩較大的概率較高.此時，與非正確起點下乘積矩陣的秩區(qū)分度不大，識別概率較低.

3.2 算法理論分析

設LDPC 碼稀疏校驗矩陣為H，其行向量記為h1，h2，…，hr，記w(h)=，w(·)代 表向量的Hamming 重量.我們想要在下面兩個假設檢驗中做判決

下面來考慮正確識別概率，這需要二元域上隨機方陣的秩的分布規(guī)律.由于二元域上隨機方陣秩的具體分布規(guī)律目前還未知，已有的僅僅是當方陣階數(shù)趨于無窮大時隨機方陣秩的分布規(guī)律［20］.因此，利用多次蒙特-卡羅實驗將有限階隨機方陣的秩的經(jīng)驗分布函數(shù)得出.在10000 次實驗中，為了映照后面實驗部分選擇的編碼類型，圖2（a）中給出了280階隨機方陣的秩的經(jīng)驗分布函數(shù).圖2（b）為階數(shù)從200變化到280的隨機方陣的秩取不同值時的頻率.從圖中可知不管方陣階數(shù)如何變化，l階隨機方陣的秩極大概率都落在區(qū)間[l-2，l]上，其中以l-1比例最大.

圖2 隨機方陣的秩的分布規(guī)律

考察正確檢測概率

假定隨機選取的方陣之間的相關(guān)性不大，則可認為其是相互獨立的，那么正確檢測概率可表示為

由于只要有某兩個τ(hi) ?θ(i=1，2，…，r)，便有

式（10）中w(h)為稀疏校驗向量中重量的最大值.可知隨著w(h)變小，Pcd變大，隨著M變小，Pcd變小.LDPC 碼的校驗矩陣為稀疏的且沒有4 環(huán)，校驗矩陣的行重一般來說遠遠小于碼長，因此提出的算法特別適用于LDPC碼的參數(shù)識別.

3.3 算法計算復雜度分析

當l在[lmin，lmax]中變化時，對于給定的l，計算p個階方陣的乘積需要的乘法數(shù)量為

加法數(shù)量為

因此，要估計出編碼長度l0，一共需要的乘法數(shù)量為

加法數(shù)量為

比較運算的數(shù)量為(lmax-lmin)次.固定編碼長度，讓起點t在[1，l0]中變化.要得出起點t0，類似的操作下至多需要的乘法數(shù)量為

加法數(shù)量為

比較運算的數(shù)量為l0-1次.

4 模擬仿真實驗

4.1 實驗設置

在模擬仿真實驗中，均以IEEE802.16e 標準中的（576，288）LDPC 碼為例.在截獲比特流長度M固定的情況下，在截獲數(shù)據(jù)含少量誤碼和無誤碼兩種情形下，我們分別考察了選取乘積矩陣的個數(shù)p對識別成功概率的影響.令M=132480，分別在誤比特率Pe為0 和0.0001時令乘積矩陣的個數(shù)從1連續(xù)變化到10.

由于有這樣的結(jié)論：若長向量線性相關(guān)，則從中截取的短向量一定線性相關(guān).而短向量線性相關(guān)時，其延長得到的長向量未必線性相關(guān)，因此，M對識別概率也是有影響的.一般情況下，由上面結(jié)論可知當比特流長度越長時，碼字長度和起點的正確識別概率也會越高.因此在p固定時，我們考察在有誤碼和無誤碼情況下M的變化對識別成功率的影響.在比特流長度M=q·n時，令q在180和320之間變化，將本文方法與文獻［14～17］在無誤碼和Pe=0.0001兩種情況下進行對比.

為了考察本文算法在不同的誤比特率下的表現(xiàn)，我們在截獲比特數(shù)量M=132480，p=10的情況下，令誤比特率Pe從0.0001按間隔為10-4變化到0.0008，考察Pe的變化對識別成功率的影響.還研究了在碼字長度確定的情況下，起點t0的位置對歸一化秩率的影響，印證了我們在第3節(jié)中的分析.

4.2 實驗結(jié)果分析

從圖3中可以看出，碼字長度和起點的正確識別概率確實隨著p的增大而增大.原因是列向量的選取具有隨機性，如果滿足幾個校驗關(guān)系的列都被選中，則方陣的秩較小.但若都未被選中，則方陣的秩可能比隨機矩陣的秩大，也可能比隨機矩陣的秩小.因此，當p較小時不確定性較大，隨著p的增大這種不確定性的影響漸漸被減弱.在圖3中還可以看出當p=1時，有誤碼情況下的識別概率稍大于無誤碼情況下的識別概率，正是這種原因的直觀體現(xiàn).

圖3 選擇作乘積的矩陣個數(shù)p對識別概率的影響

由于識別概率直接受到乘積矩陣的秩的影響，為了更加深入考察p的取值對乘積矩陣的秩的影響，在l=n和l≠n兩種情況下按照p取值從1到10的順序分別做了十次實驗.將實驗所得的秩求平均值，稱其為平均秩.表1給出了兩種情況下平均秩在不同的p值下的取值.可以看出，不管預設碼長正確不正確，平均秩都隨著p的增大而減小，并且碼長正確時的平均秩整體上要比碼長不正確時的平均秩小，這與我們提出算法的思想相符.

表1 十次實驗中，p對乘積矩陣平均秩的影響

從圖4（a）中可以看出，在無誤碼且q≤300時，秩準則方法［14，15］失效，而本文算法在p=10且q=250時正確識別率達到100%.在誤比特率Pe=0.0001且q≤309時，秩準則失效，而本文算法在p=10且q=260時正確識別率達到100%.4（b）中展示了利用近似秩準則［16］以及秩分布方法［18］在Pe=0.0008 時的結(jié)果，4（b）可作為4（a）的延展.可以看出雖然它們的容錯能力強于本文方法，但它們需要碼字最少個數(shù)時的q也要遠大于本文方法.圖5 中顯示，在這個變化過程中碼長和起點的正確識別概率從89%下降到20%.雖然本文算法容錯能力僅在10-4量級，但是在截獲比特數(shù)量較少而其他現(xiàn)有算法均失效的情況下，這樣的性能也是難能可貴的.圖6 給出了在Pe=0.0001 且預先設定碼長l變化時，從相應的分析矩陣中隨機選取p=10個方陣，其乘積矩陣的歸一化秩率的值.為了更清楚的顯示歸一化秩率隨l變化的取值情況，我們截取了正確碼長l0=576 所在的一段區(qū)間［558，594］.可以看出當l=576 時歸一化秩率的值最小.

圖4 截獲比特流長度M=q·n的變化對識別概率的影響

圖5 誤比特率較低時，誤比特率Pe對識別概率的影響

圖6 乘積矩陣的歸一化秩率隨著l的變化的取值情況

在確定碼字長度之后，分析矩陣中的列都已經(jīng)固定，差別僅僅是列的位置的不同.此時，正確起點與不正確起點所對應的平均歸一化秩率之間的差距進一步縮小，正確起點t0的尋找也不是一件容易的事.為了進一步增加確定性，確保正確起點被選出，可以讓起點在[t+1，t+l0+1]中變化.如果某兩個位置相差l0，且對應的平均歸一化秩率相較于其他值均較小，則可認定此位置為正確起點.表2 給出了（576，288）LDPC 碼在第1位即為正確起始位，無誤碼且M=132480，p=10的情況下，t變化時的平均歸一化秩率的部分取值.可以看到，標黑的第1 位和第577 位的值相對其他值較小，同時也可以看出當假定起始位置接近時的平均歸一化秩率明顯要大.這也印證了在第3節(jié)中關(guān)于t0位置對平均歸一化秩率的影響的分析.

表2 l0已確定，t變化時，歸一化秩率的取值情況

5 總結(jié)

本文在截獲少量比特的背景下，此時其他算法由于所需比特數(shù)量眾多而全部失效的情況下，對LDPC 碼的起點和碼長進行了識別.利用完整碼字中比特間具有線性相關(guān)性和矩陣乘積的秩不大于因子矩陣的秩等性質(zhì)，從構(gòu)造的碼字矩陣中隨機選取列，得到一系列方陣并作乘積，再選出使得乘積矩陣的歸一化秩率最小時的分析矩陣列數(shù)作為碼長.而后，利用類似的方法對列數(shù)固定、起點發(fā)生變化時構(gòu)造的分析矩陣進行處理，并且改變分析矩陣的行數(shù)多次實驗.將使得平均歸一化秩率最小時的位置確定為碼字起點.我們稱之為矩乘秩減算法.與傳統(tǒng)算法相比，達到相同的正確識別率時本文算法所需數(shù)據(jù)量至少減少25%，但計算量沒有明顯增加.