基于混沌理論的導(dǎo)航電文LDPC設(shè)計(jì)

北京航空航天大學(xué)電子信息工程學(xué)院 周 昀 黃智剛

一、引言

混沌是非線性系統(tǒng)普遍存在的現(xiàn)象，于上世紀(jì)60年代被Lorenz發(fā)現(xiàn)?；煦绗F(xiàn)象具有不可預(yù)測性、對初始條件的敏感依賴性和非周期性等特點(diǎn)。近年來，人們已經(jīng)將混沌理論應(yīng)用到通信領(lǐng)域，基于混沌系統(tǒng)固有的基本屬性設(shè)計(jì)相應(yīng)的擴(kuò)頻、保密通信等系統(tǒng)。如何將混沌理論應(yīng)用到衛(wèi)星導(dǎo)航信道編碼中，特別是LDPC的設(shè)計(jì)中，是本文主要探討的內(nèi)容。

LDPC碼由Gallager首先發(fā)明，之后MacKay等人重新研究發(fā)現(xiàn)在碼長較大時(shí)（大于104）其性能甚至超過了Turbo碼。Richardson等人基于置信傳播算法，應(yīng)用密度進(jìn)化理論研究了LDPC碼的性能，并將其用于校驗(yàn)矩陣的優(yōu)化設(shè)計(jì)。目前LDPC已經(jīng)應(yīng)用于移動(dòng)通信，無線局域網(wǎng)，以及衛(wèi)星導(dǎo)航系統(tǒng)等領(lǐng)域。

本文首先介紹混沌系統(tǒng)的基本特點(diǎn)以及典型的混沌模型，然后利用基本模型Logistic構(gòu)造一種基于混沌理論的LDPC碼（稱為Chaos code），將其與規(guī)則的MacKay碼以及隨機(jī)構(gòu)造的非規(guī)則LDPC碼比較，從而分析說明利用混沌理論設(shè)計(jì)的LDPC碼的優(yōu)缺點(diǎn)。

二、有關(guān)LDPC基本概念的說明

LDPC碼可用非常稀疏的校驗(yàn)矩陣H或Tanner圖來表示H的列中非零元素“1”（GF(2)域）的個(gè)數(shù)稱為列重（ds），對應(yīng)于Tanner圖中與變量節(jié)點(diǎn)（symbol node）相連的邊的個(gè)數(shù)；每行中“1”的個(gè)數(shù)稱為行重（dc），對應(yīng)于校驗(yàn)節(jié)點(diǎn)（check node）相連的邊的個(gè)數(shù)。若dc，ds為固定值，則稱為規(guī)則LDPC碼，否則稱為非規(guī)則碼。非規(guī)則碼變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的密度分布分別定義為：

式中，λi(ρi)是指連接到度為i的變量節(jié)點(diǎn)（校驗(yàn)節(jié)點(diǎn)）邊的個(gè)數(shù)占總邊數(shù)的比例。且滿足：

式中，dsmax，dcmax為相應(yīng)的最大度數(shù)。設(shè)碼長為n，校驗(yàn)位為m，則度為i的變量節(jié)點(diǎn)（校驗(yàn)節(jié)點(diǎn)）個(gè)數(shù)分別為

圖1(a)表示一個(gè)碼長為8，碼率為1/2的非規(guī)則LDPC碼的校驗(yàn)矩陣，圖1(b)為對應(yīng)的Tanner圖。其中，變量節(jié)點(diǎn)度分布序列：

校驗(yàn)節(jié)點(diǎn)度分布序列：

圖1(a)還描述了校驗(yàn)矩陣H中環(huán)長等于4(s7－c3－s8－c4－s7)和6(s1－c1－s7－c3－s5－c4－s1)的環(huán)。校驗(yàn)矩陣中短環(huán)的存在特別是長度為4的環(huán)，影響LDPC碼的譯碼性能。然而近期的研究表明，環(huán)長并非是影響LDPC碼性能的絕對因素，環(huán)長分布對碼性能也具有重要的影響。環(huán)長分布將在下文詳細(xì)分析。

圖1 校驗(yàn)矩陣及其對應(yīng)的Tanner圖

三、混沌系統(tǒng)的基本特性

混沌系統(tǒng)具有以下基本特性：

（1）有界性：混沌狀態(tài)是有界的，即它的運(yùn)動(dòng)軌跡始終局限于一個(gè)確定的區(qū)域，即混沌吸引域。假如初始狀態(tài)：0＜x＜L，則之后的所有迭代結(jié)果都落在此區(qū)間內(nèi)。

（2）非周期和不可預(yù)測：如果在無限精確的數(shù)學(xué)層次上跟蹤一條混沌軌道，經(jīng)歷的狀態(tài)永遠(yuǎn)沒有重復(fù)的，當(dāng)要確定某個(gè)混沌軌道上的相點(diǎn)時(shí)，只能跟蹤軌道的全過程，而不可能利用任何具周期意義的、有可壓縮性質(zhì)的所謂規(guī)律來準(zhǔn)確預(yù)測。

（3）初值敏感性：實(shí)際中只可能以有限的精度來設(shè)置初始值，若誤差以指數(shù)速度迅速增加，則計(jì)算結(jié)果將越來越依賴于表示初始條件的無理數(shù)的小數(shù)部分的位數(shù)。隨著時(shí)間推移系統(tǒng)將變?yōu)榛煦鐟B(tài)。也就是說：初始條件的極小偏差，經(jīng)過一定次數(shù)的迭代后，將會(huì)引起混沌軌跡的極大差異。Lorenz形象地把這種對初始條件的敏感依賴性稱為“蝶形效應(yīng)”。如果我們將不同的初始狀態(tài)映射為不同的碼字，那么簡單來說，經(jīng)過適當(dāng)?shù)牡螖?shù)后，相應(yīng)的軌跡具有宏觀的距離。

下文將詳細(xì)討論如何利用混沌系統(tǒng)的有界性、不可預(yù)測性、初值敏感等特性設(shè)計(jì)LDPC碼。

四、利用Logistic混沌模型設(shè)計(jì)LDPC碼原理

一維離散時(shí)間混沌系統(tǒng)可以用差分方程簡單描述為xn+1=f(xn)。一維離散映射通常是分段單調(diào)的，常見的有Tent映射和Logistic映射等。Logistic映射是在實(shí)際系統(tǒng)中存在的較簡單的非線性差分方程，是一個(gè)被廣泛研究的動(dòng)態(tài)系統(tǒng)，本文后面的研究都是基于該模型的，具體表達(dá)式為

式中，λ為分叉參數(shù)，3.5699…＜λ≤4時(shí)，Logistic映射表現(xiàn)出混沌行為。當(dāng)初值0＜x0＜1，根據(jù)有界性，迭代序列的取值范圍也一定在該區(qū)間內(nèi)。設(shè)λ=4，x0=1/3（取無理數(shù)），圖2中（◇）給出了迭代60次序列值，由圖可以看出，混沌序列在(0,1)內(nèi)無規(guī)則、雜亂無章地分布。同理為了說明初值敏感性，設(shè)λ=4，x0=1/3+10－5，畫出迭代60次序列值（Δ），由圖2，迭代10次以后兩條初值相差1×10－5的軌跡變得完全不同，說明了該混沌系統(tǒng)對初值的敏感特性。

圖2 Logistic映射初值敏感性

我們以序列值xn為橫坐標(biāo)，以其落在區(qū)間（0，1）內(nèi)的個(gè)數(shù)為縱坐標(biāo)，迭代1000次畫出其分布情況如圖3。由圖3可知在區(qū)間（0，1）內(nèi)序列關(guān)于0.5對稱分布。

在討論混沌行為的狀態(tài)特征時(shí)，要研究時(shí)間趨于無窮后（即迭代次數(shù)趨于無窮大）對整個(gè)時(shí)間過程進(jìn)行平均的極限過程，即混沌狀態(tài)的概率分布密度（也稱不變測度），也就是研究圖3中包絡(luò)情況。對于一般的混沌映射，我們用分析離散映射的有用的工具：Perron-Frobenius方程。若一維離散映射為xn+1= f(xn)，則P-F方程可表示為：

圖3 Logistic映射分布直方圖

我們根據(jù)P-F方程可求得Logistic映射的概率密度分布函數(shù)：

式（11）用圖4表示如下。觀察知：密度函數(shù)也是關(guān)于0.5對稱的，而且在0.5處取得極小值。

圖4 Logistic映射的概率密度分布函數(shù)

綜合以上研究結(jié)果，利用Logistic混沌模型設(shè)計(jì)LDPC碼的校驗(yàn)矩陣規(guī)則如下：

（1）稀疏：根據(jù)Logistic混沌模型分布特性（圖3、圖4），知其在中間值密度最低，而LDPC碼中非零元素稀疏分布（即“1”的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于校驗(yàn)矩陣的大小），我們可以將中間值在混沌軌跡中的位置，即作為元素“1”在校驗(yàn)矩陣中的位置。

（2）距離：在無限精確的數(shù)學(xué)層次上考慮，混沌序列具有周期無限的特性，即同一個(gè)值不可能出現(xiàn)第二次，反應(yīng)在軌跡上即兩條軌跡不可能相交?；煦缦到y(tǒng)又具有初值敏感特性（圖2），初始值的極小差異，經(jīng)一定次數(shù)的迭代后，導(dǎo)致混沌序列的值完全不同，反應(yīng)在校驗(yàn)矩陣H中，即任意兩行中“1”的位置具有距離特性。

（3）不規(guī)則：由混沌模型構(gòu)造校驗(yàn)矩陣H，由于其值的不可預(yù)測性，體現(xiàn)在H中，即行、列中“1”的個(gè)數(shù)分布不均勻，也就是說利用混沌模型取值的不規(guī)則，可以構(gòu)造出滿足一定密度分布的非規(guī)則LDPC碼。Luby，Richardson等人的研究結(jié)果已經(jīng)證明，優(yōu)化設(shè)計(jì)的非規(guī)則LDPC的性能好于規(guī)則的LDPC碼。

根據(jù)以上規(guī)則，設(shè)計(jì)LDPC碼校驗(yàn)矩陣具體步驟為：

第一步：產(chǎn)生混沌序列：設(shè)校驗(yàn)矩陣為hm×n，混沌序列初始值x0i，分叉系數(shù)λ=4，根據(jù)Logistic映射方程（9），迭代生成m維混沌序列xi（即迭代次數(shù)為m）。

第二步：確定h中每列1的個(gè)數(shù)和位置：統(tǒng)計(jì)序列xi落在區(qū)間A（0.5附近的一個(gè)區(qū)間）內(nèi)的個(gè)數(shù)numi，（即為h的列重），并記錄相應(yīng)的位置索引indexi（即h的每列中1的位置）。

第三步：由密度演化理論構(gòu)造h：根據(jù)有關(guān)文獻(xiàn)，選取密度分布對（λ，ρ），由式（5），式（6）度為的變量節(jié)點(diǎn)的個(gè)數(shù)設(shè)為si。若第二步中的numi與i相等，則將位置索引indexi位置處填1，其余位置填0后構(gòu)造的m×1維矢量作為h中度為i的列。

第四步：構(gòu)造h下一列需滿足的條件：檢驗(yàn)該列和已構(gòu)造的h中所有列，保證沒有長度為4的環(huán)，即要求該列與校驗(yàn)矩陣中任意一列相同位置處1的個(gè)數(shù)最多是一個(gè)，公式表示就是hi和hj內(nèi)積的漢明重量小于等于1。這樣保證環(huán)長將大于4。

五、性能仿真與分析

考慮到LDPC碼的塊結(jié)構(gòu)、逼近Shannon限和知識(shí)產(chǎn)權(quán)等因素，GPS新民用信號L1C（頻點(diǎn)1575.42MHz），播發(fā)的導(dǎo)航電文CNAV-2中第2幀和第3幀分別采用碼長1200，548，碼率為1/2的LDPC碼作為前向糾錯(cuò)碼。在同樣的碼長和碼率條件下，我們分別構(gòu)造了三類（n，k）=（1200,600）和（548, 274）的LDPC碼。利用上述混沌法構(gòu)造時(shí)，盡量保證混沌序列初始值x0i為一個(gè)無理數(shù)，這樣在迭代一定次數(shù)后，無理數(shù)的小數(shù)部分的微小差異會(huì)被宏觀地體現(xiàn)出來，具體反映在序列xi落在設(shè)定區(qū)間A內(nèi)的個(gè)數(shù)能更好地滿足條件。對于區(qū)間A={0.48－2－8, 0.5+2－8}，仿真實(shí)驗(yàn)表明，當(dāng)A={0.48－2－8, 0.5+2－8}時(shí)最理想。至于隨機(jī)構(gòu)造的非規(guī)則LDPC碼，在保證變量節(jié)點(diǎn)密度的條件下，隨機(jī)搜索每列中1的位置，而且盡可能使每行中1的個(gè)數(shù)一致，同樣要求不能有長為4的環(huán)。

其中混沌構(gòu)造法與隨機(jī)碼選取一致的密度分布對。碼長為1200時(shí)變量節(jié)點(diǎn)最大度選為15，密度分布如下：

碼長為548時(shí)，變量節(jié)點(diǎn)最大度數(shù)設(shè)為11，密度分布如下：

對于不同碼長選取的不同密度參數(shù)具體見表1。

MacKay規(guī)則碼，保證每列1的個(gè)數(shù)為3，每行1的個(gè)數(shù)為6，即ds=3，dc=6。在構(gòu)造時(shí)同樣要求消去長為4的環(huán)。

最后在二進(jìn)制高斯白噪聲信道（BIAWGN）下，仿真驗(yàn)證上述三種LDPC碼的性能，仿真實(shí)驗(yàn)系統(tǒng)參數(shù)見表2。文中選取對數(shù)似然比置信傳播算法（LLR-BP），最大迭代次數(shù)設(shè)為80次，而且對于每一個(gè)Eb/N0值，錯(cuò)誤的幀個(gè)數(shù)達(dá)到100個(gè)則仿真結(jié)束。

圖（5）和圖（6）比較了混沌碼（Chaos）、MacKay碼和隨機(jī)碼（Random）在碼長取1200，548時(shí)的誤碼率和誤幀率。表（3）、表（4）則列舉了誤碼率為1×10－5，誤幀率為1×10－2條件下三種碼的Eb/N0值。可以看出混沌碼大約好于隨機(jī)碼0.1dB，好于MacKay碼0.2dB。

表1 密度相關(guān)的變量節(jié)點(diǎn)數(shù)

表2 仿真實(shí)驗(yàn)系統(tǒng)參數(shù)

圖5 BIAWGNC下碼長1200誤碼率、誤幀率

圖6 BIAWGN下碼長548誤碼率、誤幀率

接下來從校驗(yàn)矩陣的環(huán)分布特性來分析比較三種碼，本文以碼長等于548的碼為例說明。由表5知，規(guī)則的MacKay碼中最小環(huán)長為8的變量節(jié)點(diǎn)數(shù)占總數(shù)的比例約41%，最小環(huán)長為6的變量節(jié)點(diǎn)數(shù)比例約為56%，且有16個(gè)變量節(jié)點(diǎn)數(shù)的最小環(huán)長大于等于8，而利用混沌構(gòu)造的非規(guī)則碼，其最小環(huán)長為8的變量節(jié)點(diǎn)數(shù)占總數(shù)的比例不到百分之一，幾乎所有的變量節(jié)點(diǎn)其最小環(huán)長都是6，隨機(jī)碼也具有同樣的現(xiàn)象。但是考慮整個(gè)校驗(yàn)矩陣，相比MacKay碼，混沌碼和隨機(jī)碼環(huán)的數(shù)量較多，且不同長度的環(huán)分布方差也較大。Thomas R研究結(jié)果表明：環(huán)不規(guī)則分布（即環(huán)分布方差）的影響大于環(huán)長的影響。

表3 碼長為548時(shí)三種碼性能比較

表4 碼長為1200時(shí)三種碼性能比較

表5 碼長為548時(shí)碼的環(huán)分布特性比較

表6計(jì)算了環(huán)長為6和8的環(huán)的均值和方差。從三種碼的環(huán)長分布特性可看出，混沌碼，其環(huán)分布的方差（σ）是最大的，cycle-8時(shí)是隨機(jī)碼的1.6倍，MacKay碼的300倍。這就從環(huán)的不規(guī)則分布特性解釋了混沌法構(gòu)造LDPC碼的優(yōu)點(diǎn)，即利用混沌系統(tǒng)的類隨機(jī)、不規(guī)則以及不可預(yù)測特性可構(gòu)造環(huán)分布方差較大的LDPC碼，從而相比MacKay碼、隨機(jī)碼具有更高的編碼增益。

表6 三種碼的環(huán)長分布特性比較

由圖5、圖6可以看出，盡管混沌碼和隨機(jī)碼隨著信噪比的增加會(huì)出現(xiàn)錯(cuò)誤平層，但是混沌碼相比隨機(jī)碼錯(cuò)誤平層性能略有改善，即出現(xiàn)平層時(shí)的Eb/N0值較高。我們知道錯(cuò)誤平層與最小碼距直接相關(guān)，所以相比隨機(jī)碼，混沌碼的最小碼距有所改善，相比規(guī)則的MacKay碼還是較小。

六、結(jié)束語

本文主要探討了如何利用混沌系統(tǒng)的基本特性以及特定的混沌模型的性質(zhì)來設(shè)計(jì)LDPC碼。綜合分析研究結(jié)果，我們得出以下結(jié)論。

（1）給出混沌模型，確定模型初值后，利用簡單的迭代就可產(chǎn)生一系列混沌軌跡，從而有效地確定校驗(yàn)矩陣中非零元素的位置，結(jié)合密度演化理論，可以構(gòu)造任意碼長和碼率的LDPC碼。

（2）碼長n=548/1200，信噪比區(qū)間(1～2.5dB/1～2dB)，混沌構(gòu)造法與隨機(jī)碼性能相當(dāng)，優(yōu)于MacKay碼大約0.3dB/0.4dB；在區(qū)間（2.5～3dB/2～2.5dB），相比隨機(jī)碼和MacKay規(guī)則碼，混沌碼的編碼增益改善約0.1dB，0.2dB。

（3）利用混沌理論構(gòu)造的LDPC碼環(huán)（cyecle-6和cycle-8）分布方差較大，相比隨機(jī)碼錯(cuò)誤平層略有改善。

見www.dcw.org.cn