小樣本條件下基于矩陣乘法和秩分析的LDPC參數(shù)估計(jì)方法

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

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

1 引言

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

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

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

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

2.1 符號(hào)說明

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

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

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

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

若有兩個(gè)碼字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仍然是一個(gè)合法碼字，因此碼字空間關(guān)于F2上的加法運(yùn)算⊕封閉.

LDPC 碼是一種特殊的線性分組碼，僅由一個(gè)包含很少個(gè)1 的校驗(yàn)矩陣H(n-k)×n的零空間所定義.因此當(dāng)給定k個(gè)信息比特(u1，u2，…，uk)時(shí)，需要利用校驗(yàn)矩陣求解n-k個(gè)校驗(yàn)比特(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)于⊕封閉，并且與其對(duì)偶空間具有正交性.而LDPC 碼的識(shí)別過程也正是基于這種關(guān)系.

2.3 高斯若當(dāng)列消元法

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

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

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

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

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

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

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

圖1 當(dāng)l ≠βn和l=βn時(shí)，矩陣A在形式上的差別

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

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

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

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

3 本文算法、原理及復(fù)雜度分析

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

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

3.1 本文算法

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

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

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

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

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

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

3.2 算法理論分析

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

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

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

考察正確檢測(cè)概率

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

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

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

3.3 算法計(jì)算復(fù)雜度分析

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

加法數(shù)量為

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

加法數(shù)量為

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

加法數(shù)量為

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

4 模擬仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

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

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

為了考察本文算法在不同的誤比特率下的表現(xiàn)，我們?cè)诮孬@比特?cái)?shù)量M=132480，p=10的情況下，令誤比特率Pe從0.0001按間隔為10-4變化到0.0008，考察Pe的變化對(duì)識(shí)別成功率的影響.還研究了在碼字長(zhǎng)度確定的情況下，起點(diǎn)t0的位置對(duì)歸一化秩率的影響，印證了我們?cè)诘?節(jié)中的分析.

4.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

表1 十次實(shí)驗(yàn)中，p對(duì)乘積矩陣平均秩的影響

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

圖4 截獲比特流長(zhǎng)度M=q·n的變化對(duì)識(shí)別概率的影響

圖5 誤比特率較低時(shí)，誤比特率Pe對(duì)識(shí)別概率的影響

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

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

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

5 總結(jié)

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