基于密度演化理論的IRA碼度分布設計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、B，與香農限僅差0.12dB。表3.1在AWGN信道下碼率為1/3的IRA碼優(yōu)化參數 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香農限（dB）-0.4953-

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

17、點所獲得的校驗信息就更準確。所以，文獻10指出，要達到接近0的誤碼率，項是必不可少的。表3.2在AWGN信道下碼率為1/2的IRA碼優(yōu)化參數序列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香農限（dB）0.1970.1783.2 仿真與分析1、 IRA碼在不同度分布下的性能

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

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

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