基于密度演化理論的IRA碼度分布設(shè)計(jì)

1、基于密度演化理論的IRA碼度分布設(shè)計(jì)0 引言1998年，D.Divsalar等人提的重復(fù)累積碼（Repeat-Accumulate Codes，RA碼）是一種簡(jiǎn)單的類Turbo碼1。它的兩個(gè)成員碼一個(gè)是碼率為1/q的重復(fù)碼，一個(gè)是碼率為1，傳遞函數(shù)為1/(l+D)的卷積碼(稱為累加器)，這也是重復(fù)累積碼名字的由來(lái)。這類碼不僅編碼復(fù)雜度低且結(jié)構(gòu)簡(jiǎn)單。Divsalar等人證明了對(duì)于RA碼，采用最大似然譯碼算法，在足夠大的信噪比下，當(dāng)碼長(zhǎng)趨于無(wú)窮時(shí)幀錯(cuò)誤概率趨于零,是一類性能良好的碼。2000年，受到不規(guī)則LDPC碼的啟發(fā)，提出了不規(guī)則重復(fù)累積碼（IRA碼）5，與規(guī)則RA碼相比，IRA碼具有更接近香

2、農(nóng)限的性能。本文首先介紹了IRA碼的結(jié)構(gòu)，推導(dǎo)了在AWGN信道下采用高斯近似優(yōu)化IRA碼的度分布，并對(duì)設(shè)計(jì)結(jié)果進(jìn)行計(jì)算機(jī)仿真，最后是結(jié)束語(yǔ)。1 IRA碼的結(jié)構(gòu)圖1是參數(shù)為的IRA碼的Tanner圖，其中，一般情況，表示度數(shù)為i的信息節(jié)點(diǎn)與所有信息節(jié)點(diǎn)的比例，j為信息節(jié)點(diǎn)的最大度數(shù)，a為校驗(yàn)節(jié)點(diǎn)連接信息節(jié)點(diǎn)的邊數(shù)，一般情況下為正整數(shù)。IRA碼的Tanner圖包含變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)，其中變量節(jié)點(diǎn)包括信息節(jié)點(diǎn)和奇偶節(jié)點(diǎn)，如圖2.7，上方為N個(gè)變量節(jié)點(diǎn)，中間為r個(gè)校驗(yàn)節(jié)點(diǎn)，下方為r個(gè)奇偶節(jié)點(diǎn)。第i個(gè)信息節(jié)點(diǎn)與個(gè)校驗(yàn)節(jié)點(diǎn)相連，每個(gè)校驗(yàn)節(jié)點(diǎn)連接a個(gè)信息節(jié)點(diǎn)，條邊通過(guò)交織器將信息節(jié)點(diǎn)和檢驗(yàn)節(jié)點(diǎn)連接起來(lái)，每個(gè)

3、校驗(yàn)節(jié)點(diǎn)通過(guò)Z字型的方式連接兩個(gè)奇偶節(jié)點(diǎn)(第一個(gè)節(jié)點(diǎn)除外)。圖1IRA碼的Tanner圖從矩陣的角度來(lái)看，IRA碼的校驗(yàn)矩陣類似于規(guī)則RA碼的校驗(yàn)矩陣，也包含兩部分，為一個(gè)維矩陣。其中是一個(gè)稀疏的維矩陣，對(duì)應(yīng)于Tanner圖中的隨機(jī)交織。是一個(gè)滿秩的維矩陣，對(duì)應(yīng)著Tanner圖中奇偶節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)之間固定的Z形連接，具有式（2.4）的形式。在H矩陣中，第一行所含“1”的個(gè)數(shù)為a+1，其余行“1”的個(gè)數(shù)為a+2。所以，IRA碼的校驗(yàn)矩陣也是低密度校驗(yàn)矩陣。IRA碼的碼率為： (2.16)碼率也可以用度數(shù)分布表示為 (2.17)2、高斯近似優(yōu)化IRA碼的度分布本章介紹了IRA碼的密度進(jìn)化設(shè)計(jì)方法，

4、研究了在AWGN信道下，利用高斯估計(jì)密度進(jìn)化理論設(shè)計(jì)IRA碼的最優(yōu)度分布，對(duì)IRA碼在不同度分布進(jìn)行了仿真分析，并對(duì)比分析了規(guī)則RA碼和IRA碼的性能，最后分析了IRA碼的編譯碼復(fù)雜度。3.1 IRA碼的度分布設(shè)計(jì)在迭代的BP譯碼算法中，所有的消息都假定為對(duì)數(shù)似然比，即的形式。從節(jié)點(diǎn)u送出到節(jié)點(diǎn)v的消息取決于從u的所有鄰居節(jié)點(diǎn)w(除v之外)來(lái)的消息。如果u是一個(gè)變量節(jié)點(diǎn)，發(fā)出的消息為： （3.1）此處是u的對(duì)數(shù)似然比。若u是校驗(yàn)節(jié)點(diǎn)，發(fā)出的消息是22 （3.2）IRA碼在二元?jiǎng)h除信道中的度分布設(shè)計(jì)用式(3.1)和(3.2)表示的IRA碼的和積譯碼算法在二元?jiǎng)h除信道(BEC)中可以大大簡(jiǎn)化。BE

5、C的信道輸入為二進(jìn)制符號(hào)，輸出符號(hào)為“”，“”和“刪除位”。輸入的符號(hào)以概率p被刪除，以概率1-p正確接收。在BEC下，信息只會(huì)被刪除，不會(huì)有錯(cuò)誤出現(xiàn)。不難看出由式(3.1)和(3.2)定義的消息在BEC中可以假定為只有三個(gè)值，即、和0，對(duì)應(yīng)變量值0、1和“未知量”。在這種情況下在Tanner圖中按方程(3.1) 和(3.2)給定的節(jié)點(diǎn)操作會(huì)變得更為簡(jiǎn)單和直觀。對(duì)于變量節(jié)點(diǎn)，送出的消息等于送來(lái)的非刪除位的消息，或者等于刪除消息（如果所有的進(jìn)入消息都是刪除消息）。對(duì)于校驗(yàn)節(jié)點(diǎn)，如果送入的消息有刪除消息則送出的消息是刪除消息，否則送出的是所有進(jìn)入消息的二進(jìn)制和。1. 迭代譯碼的固定點(diǎn)分析密度進(jìn)化中

6、，進(jìn)化的是消息的概率密度。在刪除信道中，只有三種消息類型，因此得到一個(gè)離散的密度函數(shù)，而且錯(cuò)誤概率也僅僅是刪除概率。只要迭代次數(shù)足夠大、碼長(zhǎng)足夠長(zhǎng)，就可以達(dá)到任意小的比特錯(cuò)誤率19，這就是刪除概率的進(jìn)化。令p為消息比特的初始刪除概率，在譯碼算法實(shí)現(xiàn)過(guò)程中，將沿Tanner圖的邊迭代刪除概率。令為信息節(jié)點(diǎn)到校驗(yàn)節(jié)點(diǎn)的刪除概率，為校驗(yàn)節(jié)點(diǎn)到奇偶節(jié)點(diǎn)的刪除概率，為奇偶節(jié)點(diǎn)到校驗(yàn)節(jié)點(diǎn)的刪除概率，為校驗(yàn)節(jié)點(diǎn)到信息節(jié)點(diǎn)的刪除概率。定義多項(xiàng)式R( x)，有： （3.3）其中的系數(shù)表示與i個(gè)信息節(jié)點(diǎn)相連的校驗(yàn)節(jié)點(diǎn)的比例。由式（3.3）和式（2.14）有： （3.4）假定要在譯碼算法的一個(gè)固定的節(jié)點(diǎn)求解，有 （

7、3.5） （3.6） （3.7） （3.8）由（3.5）、（3.6）、（3.7）、（3.8）消除、得到關(guān)于的函數(shù)，記為，則有： （3.9）若式（3.9）在區(qū)間上無(wú)解，那么RA碼譯碼器的誤碼率收斂于0。所以，如果有： （3.10）以文獻(xiàn)19的思想，則迭代譯碼成功實(shí)現(xiàn)。2. 接近信道容量的參數(shù)設(shè)計(jì)下面我們將推導(dǎo)接近信道容量的度分布。首先，設(shè)定，即轉(zhuǎn)換為在此條件下達(dá)到信道容量。且有，則在BER信道下將誤碼率收斂于0轉(zhuǎn)變?yōu)椋?（3.11）定義 （3.12） （3.13） （3.14）、與在0,1區(qū)間內(nèi)都是單調(diào)函數(shù)，當(dāng)x取值為0時(shí)函數(shù)的值為0；當(dāng)x取值為時(shí)，函數(shù)的值為1。此外，可以通過(guò)令求逆得到。可以在

8、零點(diǎn)展為非負(fù)系數(shù)的冪級(jí)數(shù)，令?，F(xiàn)在，條件式(3.11)可以重新寫為： （3.15）即 （3.16）在（3.17）式中選擇， （3.17）式中，且。N和存在且是唯一的，因?yàn)槭欠秦?fù)的，且。對(duì)于這樣選擇的，有： （3.18）后一個(gè)不等式成立是因?yàn)椤Ｒ驗(yàn)槭剑?.17）滿足條件（3.16），所以誤碼率BER收斂到0。由這樣度數(shù)分布函數(shù)得到的IRA碼門限值大于等于p?，F(xiàn)在我們將計(jì)算在的情況下的碼率?？梢钥吹竭@時(shí)碼率接近信道容量。IRA碼的碼率由式（2.17）給出，簡(jiǎn)化為,有： （3.19） （3.20）（3.20）式中右邊的不等式是由的性質(zhì)決定的。由容易看出： （3.21）在式（3.21）中，當(dāng)a很大時(shí)，

9、其值趨于(1-p)/p。把這個(gè)結(jié)果代入計(jì)算碼率的公式，最后得到當(dāng)a很大時(shí)碼率趨于1-p，這實(shí)際上就是BEC的信道容量。因此方程(3.17)給出的度數(shù)分布序列達(dá)到了信道容量。文獻(xiàn)10給出了在BEC下設(shè)計(jì)IRA碼的結(jié)論：在碼率相同的情況下，隨著a與的項(xiàng)數(shù)的增加，閾值逐漸接近信道容量。所以，在設(shè)計(jì)IRA碼時(shí)，選擇參數(shù)a與的項(xiàng)數(shù)的值時(shí)，在可能情況下，應(yīng)盡量選擇大一點(diǎn)的值。 IRA碼在AWGN信道中的度分布設(shè)計(jì)在本節(jié)中，考慮在AWGN信道下的度分布設(shè)計(jì)。AWGN信道中，只有“0”和“1”兩種輸入，輸出為，其中z為均值為0，方差為的高斯白噪聲。給定噪聲方差，找到最優(yōu)度序列使其在高碼率的情況下誤碼率接近0。

10、在BEC信道中僅需考慮概率，而在AWGN信道中，還需考慮概率密度，這使得分析變得復(fù)雜化，于是采用近似方法去設(shè)計(jì)。1 高斯近似Wiberg18指出在AWGN信道中，迭代譯碼傳遞的對(duì)數(shù)似然比信息可以用高斯隨機(jī)變量來(lái)近似。在文獻(xiàn)20中，提出將概率密度函數(shù)進(jìn)行高斯近似（Gaussian approximation）的方法運(yùn)用于AWGN信道中的LDPC碼的度分布設(shè)計(jì)。 作為一類特殊的LDPC碼，運(yùn)用高斯近似（GA）同樣可以設(shè)計(jì)在AWGN信道下IRA碼的度分布，在每次迭代時(shí)，用高斯變量近似校驗(yàn)節(jié)點(diǎn)到變量節(jié)點(diǎn)（信息節(jié)點(diǎn)和奇偶節(jié)點(diǎn)）的消息。對(duì)于一個(gè)變量節(jié)點(diǎn)，若所有輸入為高斯信息，通過(guò)式（3.1）可以知道，此變

11、量節(jié)點(diǎn)的輸出也為高斯信息。若高斯分布滿足，則稱此高斯分布具有一致性。具有一致性條件的高斯分布的方差和均值滿足。文獻(xiàn)19證明了在和積算法中，消息在變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的更新中保持了一致性。這樣，對(duì)于輸入信息為一致高斯信息的點(diǎn)，只需要跟蹤均值就可以得到信息密度的分布。定義具有均值為的一致高斯分布為： （3.22）對(duì)均值為符合一致高斯分布的隨機(jī)變量z，的期望值為 （3.23）容易看出，是的連續(xù)單調(diào)遞減函數(shù)。標(biāo)記其反函數(shù)為。在第次迭代時(shí)，用和分別表示從檢驗(yàn)節(jié)點(diǎn)到變量節(jié)點(diǎn)和檢驗(yàn)節(jié)點(diǎn)到奇偶節(jié)點(diǎn)的消息，希望得到用和表示的和。度為i的信息節(jié)點(diǎn)向校驗(yàn)節(jié)點(diǎn)傳送的信息為方差是的高斯信息，為式（3.1）中信息的方差。用

12、表示隨機(jī)選擇一條從信息節(jié)點(diǎn)到校驗(yàn)節(jié)點(diǎn)的邊的信息，則其密度函數(shù)為： （3.24）由式（3.23）和式（3.24）得到： （3.25）同理，用表示隨機(jī)選擇一條從奇偶節(jié)點(diǎn)到校驗(yàn)節(jié)點(diǎn)的邊的信息，有： （3.26）由式（3.2）有： （3.27）分別用和表示從校驗(yàn)節(jié)點(diǎn)到信息節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)到奇偶節(jié)點(diǎn)的信息。將式（3.25）和式（3.26）分別代入（3.27）有：由式（3.23）定義的，得到： （3.28） （3.29）為了獲得任意小的誤碼率，當(dāng)趨于無(wú)窮大時(shí)，和的均值也應(yīng)該趨于無(wú)窮大。但是Richardson等人14在研究AWGN信道下基于置信傳遞算法的密度進(jìn)化時(shí)，發(fā)現(xiàn)迭代中存在幾個(gè)誤碼率下降緩慢的關(guān)鍵點(diǎn)，

13、稱之為“黏滯點(diǎn)（Fixed Point）”。在這些點(diǎn)上，相鄰兩次迭代譯碼消息變化很小。2黏滯點(diǎn)分析假設(shè)迭代譯碼達(dá)到式（3.28）和（3.29）中的黏滯點(diǎn)，這時(shí)，有 ，令由式（3.25）可以得到，且當(dāng)時(shí)，。很顯然，式（3.29）中是x的函數(shù)，表示為。則由式（3.28）和式（3.29）得到 （3.30）用替代（3.30）中的，并將其標(biāo)識(shí)為x，得到黏滯點(diǎn)x的方程 （3.31）若式（3.31）在區(qū)間內(nèi)無(wú)解，那么譯碼的誤碼率趨于0。令 （3.32）在任意中成立（為第一次迭代時(shí)x的值），則高斯估計(jì)迭代譯碼成功。由式（3.17）得到IRA碼的碼率為： （3.33）為了使碼率最大化，應(yīng)該使最大化。因此，用高斯

14、估計(jì)時(shí)，IRA碼的優(yōu)化設(shè)計(jì)問(wèn)題轉(zhuǎn)化為線性規(guī)劃問(wèn)題，即為在條件 （3.34）下，最大化 （3.35）10。表中，a,分別為IRA碼的校驗(yàn)節(jié)點(diǎn)與信息節(jié)點(diǎn)度數(shù)分布參數(shù)；為運(yùn)用密度進(jìn)化技術(shù)（GA）計(jì)算出的IRA碼的真實(shí)閾值；閾值對(duì)應(yīng)的信噪比（dB）為真實(shí)閾值對(duì)應(yīng)的信噪比；為高斯估計(jì)下得到的閾值，最后1行為相應(yīng)碼率下的Shannon限。在3.1中，當(dāng)時(shí)，調(diào)整高斯閾值至1.2315,得到了碼率為0.333223的IRA碼的一組參數(shù)。運(yùn)用精確的密度進(jìn)化技術(shù)，通過(guò)計(jì)算得到這組參數(shù)下的真實(shí)閾值，其對(duì)應(yīng)的信噪比為-0.250，與香農(nóng)限-0.4958很接近。當(dāng)增加a到4時(shí)，IRA碼在AWGN下的閾值為-0.371d

15、B，與香農(nóng)限僅差0.12dB。表3.1在AWGN信道下碼率為1/3的IRA碼優(yōu)化參數(shù) a23420.1390250.0781940.05448530.2221550.1280850.10431550.16081360.6388200.0361780.126755100.229816110.016484120.108828130.487902270.450302280.017842碼率0.3333640.3332230.333218GA1.18401.24251.2615*1.19811.26071.2780(Eb/N0)*(dB)0.190-0.250-0.371香農(nóng)限（dB）-0.4953-

16、0.4958-0.4958表3.2為，碼率約為1/2的IRA碼的兩組參數(shù)值。在第一組參數(shù)中不含項(xiàng)，第二組參數(shù)中含有項(xiàng)，由香農(nóng)限可以看出，含有項(xiàng)的參數(shù)性能更加優(yōu)越。這是因?yàn)?，從變量?jié)點(diǎn)的角度看，其度數(shù)越高越好，因?yàn)閷?duì)它進(jìn)行監(jiān)督的校驗(yàn)節(jié)點(diǎn)越多，提供的譯碼信息越準(zhǔn)確，使得它能更快更準(zhǔn)確地譯碼，所以度數(shù)為2的變量節(jié)點(diǎn)性能很差是顯而易見(jiàn)的。然而，如T. Richardson14所述，為了保證最優(yōu)的非規(guī)則性，度數(shù)為2的節(jié)點(diǎn)是必要的。直觀認(rèn)為，低度數(shù)的變量節(jié)點(diǎn)是“不好”的，但是為了平衡低度數(shù)的校驗(yàn)節(jié)點(diǎn)的存在，它又是“好的”。低度數(shù)校驗(yàn)節(jié)點(diǎn)的存在是有利的，度數(shù)越低，它對(duì)與之相鄰變量節(jié)點(diǎn)的校驗(yàn)約束更有效，變量節(jié)

17、點(diǎn)所獲得的校驗(yàn)信息就更準(zhǔn)確。所以，文獻(xiàn)10指出，要達(dá)到接近0的誤碼率，項(xiàng)是必不可少的。表3.2在AWGN信道下碼率為1/2的IRA碼優(yōu)化參數(shù)序列a8820.057712830.2527440.11705770.218992280.0333844110.081476120.327162180.2147221200.0752259460.184589480.154029550.0808676580.202038碼率0.502270.497946*0.95890.972(Eb/N0)* (dB)0.3440.266香農(nóng)限（dB）0.1970.1783.2 仿真與分析1、 IRA碼在不同度分布下的性能

18、比較為了研究度分布對(duì)IRA碼性能的影響，在AWGN信道下，對(duì)碼率為1/3和1/2的IRA碼在不同度分布的條件下分別進(jìn)行了仿真。表3.1為碼率為1/3的三組IRA碼的度分布，將表中所示a2，a=3，a=4的三組度分布分別設(shè)為第一組，第二組和第三組參數(shù)，仿真這三組參數(shù)下碼長(zhǎng)分別為1024和2048的IRA碼的性能曲線。其它參數(shù)相同，為：BPSK調(diào)制；隨機(jī)交織器；碼率R1/3；BP譯碼，且其迭代次數(shù)為100。圖3.1為碼長(zhǎng)1024，碼率1/3的IRA碼的性能曲線，圖3.2為碼長(zhǎng)為2048，碼率1/3的IRA碼的性能曲線。從圖3.1可以看到，在誤碼率BER=10-4時(shí)，IRA碼采用第一組度分布參數(shù)所需

19、的信噪比約為1.95dB，采用第二組度分布參數(shù)所需的信噪比約為1.8dB，采用第三組度分布參數(shù)所需的信噪比約為1.7dB，因此，碼率為1/3的IRA碼采用第三組度分布的性能優(yōu)于采用第一組和第二組度分布。為了不失一般性，圖3.2給出了碼長(zhǎng)為2048的性能曲線，從圖3.2可以得出同樣的結(jié)論。比較表3.1中碼率為1/3的IRA碼的三種度分布的閾值與香農(nóng)限的距離,得出在a=4時(shí)，IRA碼離其香農(nóng)限的距離最近，所以a=4時(shí)IRA碼的性能優(yōu)于a=2和a=3時(shí)的性能。于是，可以得到，在設(shè)計(jì)IRA碼的度分布參數(shù)時(shí)，參數(shù)a的適當(dāng)增大及的項(xiàng)數(shù)的適當(dāng)增多，可以使IRA碼的誤碼率下降，性能得到改善。圖3.1 碼長(zhǎng)10

20、24,碼率1/3的兩組度分布性能比較圖3.2 碼長(zhǎng)2048,碼率1/3的兩組度分布性能比較前面提到，在設(shè)計(jì)IRA碼的度分布時(shí)，為了達(dá)到接近0的誤碼率，在度分布設(shè)計(jì)時(shí)項(xiàng)是必不可少。為了研究項(xiàng)對(duì)IRA碼性能的影響，在AWGN信道下，對(duì)碼率為1/2的IRA碼的性能進(jìn)行了仿真。將表3.2所示的a為8，不包含2項(xiàng)設(shè)為第一組參數(shù)，包含2項(xiàng)設(shè)為第二組參數(shù)，仿真這二組度分布參數(shù)下碼長(zhǎng)分別為1024和2048的IRA碼的性能曲線。其它仿真參數(shù)相同，為：AWGN信道；BPSK調(diào)制；隨機(jī)交織器；碼率R1/2；BP譯碼，且其迭代次數(shù)為100。圖3.3為碼長(zhǎng)1024，碼率為1/2的IRA碼的性能曲線，圖3.4為碼長(zhǎng)為2048，碼率為1/2的IRA碼性能曲線。從圖3.3可以看到，在誤碼率BER=10-4時(shí)，IRA碼采用第一組度分布參數(shù)所需的信噪比約為2.95dB，采用第二組度分布參數(shù)所需的信噪比約為2.8dB，因此，包含2項(xiàng)的IRA碼的性能比不包含2項(xiàng)