欧美精品久久久亚洲,欧美国产第一页,亚欧成人一区二区,久久精品一区二区影院,国产成人精品综合久久久,亚洲国产精品一区

https://blog.csdn.net/sinat_38151275/article/details/98102699

LDPC碼簡介

低密度校驗碼（LDPC碼）是一種前向糾錯碼，LDPC碼最早在20世紀60年代由Gallager在他的博士論文中提出，但限于當時的技術條件，缺乏可行的譯碼算法，此后的35年間基本上被人們忽略，其間由Tanner在1981年推廣了LDPC碼并給出了LDPC碼的圖表示，即后來所稱的Tanner圖。1993年Berrou等人發現了Turbo碼，在此基礎上，1995年前后MacKay和Neal等人對LDPC碼重新進行了研究，提出了可行的譯碼算法，從而進一步發現了LDPC碼所具有的良好性能，迅速引起強烈反響和極大關注。經過十幾年來的研究和發展，研究人員在各方面都取得了突破性的進展，LDPC碼的相關技術也日趨成熟，甚至已經開始有了商業化的應用成果，并進入了無線通信等相關領域的標準。

• LDPC碼的特點

LDPC碼是一種分組碼，其校驗矩陣只含有很少量非零元素。正是校驗矩陣的這種稀疏性，保證了譯碼復雜度和最小碼距都只隨碼長呈現線性增加。除了校驗矩陣是稀疏矩陣外，碼本身與任何其它的分組碼并無二致。其實如果現有的分組碼可以被稀疏矩陣所表達，那么用于碼的迭代譯碼算法也可以成功的移植到它身上。然而，一般來說，為現有的分組碼找到一個稀疏矩陣并不實際。不同的是，碼的設計是以構造一個校驗矩陣開始的，然后才通過它確定一個生成矩陣進行后續編碼。而LDPC的編碼就是本文所要討論的主體內容。對于LDPC碼而言，校驗矩陣的選取十分關鍵，不僅影響LDPC碼的糾錯性能力，也影響LDPC編譯碼的復雜度及硬件實現的復雜度。準循環 LDPC 碼(Quasi-Cycle,QC-LDPC)是 LDPC 碼中重要的一類,是指一個碼字以右移或左移固定位數的符號位得到的仍是一個碼字。QC-LDPC 碼的校驗矩陣是由循環子矩陣的陣列組成，相對于其他類型的 LDPC 碼，在編碼和解碼的硬件實現上具有許多優點。編碼可以通過反饋移位寄存器有效實現，采用串行算法，編碼的復雜度與校驗比特位數成正比，而采用并行算法，編碼復雜度與碼字長度成正比。對硬件解碼實現，準循環的結構簡化了消息傳遞的路徑，可以部分并行解碼，實現了解碼復雜度和速率的折中。這些優點，使得 QC-LDPC 碼作為未來通信和存儲系統應用的主要 LDPC 碼。

• 譯碼算法的選擇

譯碼方法是LDPC碼與經典的分組碼之間的最大區別。經典的分組碼一般是用ML類的譯碼算法進行譯碼的，所以它們一般碼長較小，并通過代數設計以減低譯碼工作的復雜度。但是LDPC碼碼長較長，并通過其校驗矩陣H的圖像表達而進行迭代譯碼，所以它的設計以校驗矩陣的特性為核心考慮之一。由于 LDPC 碼校驗矩陣的稀疏性,其譯碼復雜度與碼長不是指數關系,而是線性關系,因而 LDPC 碼的碼長可以很長，可以達到幾千到幾萬甚至更高，這樣帶來的一個好處是：一個碼字內各比特之間的關聯長度比較長，一般通過迭代譯碼方法進行譯碼，充分利用碼字內各比特的關聯性以提高譯碼準確度,并且還充分利用了信道的特征。本課題采用的譯碼算法為置信傳播（BP）譯碼算法，置信傳播算法是基于 Tanner 圖的迭代譯碼算法。在迭代過程中，可靠性信息，即“消息”通過 Tanner圖上的邊在變量節點和校驗節點中來回傳遞，經多次迭代后趨于穩定值，然后據此進行最佳判決，BP譯碼算法有著非常好譯碼性能。

• Tanner圖

LDPC碼常常通過圖來表示，而Tanner圖所表示的其實是LDPC碼的校驗矩陣。Tanner圖包含兩類頂點:n個碼字比特頂點(稱為比特節點)，分別與校驗矩陣的各列相對應和m個校驗方程頂點(稱為校驗節點)，分別與校驗矩陣的各行對應。校驗矩陣的每行代表一個校驗方程，每列代表一個碼字比特。所以，如果一個碼字比特包含在相應的校驗方程中，那么就用一條連線將所涉及的比特節點和校驗節點連起來，所以Tanner圖中的連線數與校驗矩陣中的1的個數相同。以下圖是矩陣的Tanner圖，其中比特節點用圓形節點表示，校驗節點用方形節點表示，加黑線顯示的是一個6循環：

Tanner圖中的循環是由圖中的一群相互連接在一起的頂點所組成的，循環以這群頂點中的一個同時作為起點和終點，且只經過每個頂點一次。循環的長度定義為它所包含的連線的數量，而圖形的圍長，也可叫做圖形的尺寸，定義為圖中最小的循環長度。如上圖中，圖形的尺寸，即圍長為6，如加黑線所示。

LDPC編碼

基于校驗矩陣H直接編碼方案

首先推導出根據校驗矩陣直接編碼的等式。將尺寸為（m,n）校驗矩陣寫成如下形式：

 其中H₁的大小為m ? k ，H₂  的大小為m ? m  。設編碼后的碼字行向量為c，它的長度為n，把它寫成如下形式

其中s是信息碼的行向量，長度為k，p為檢驗行向量，長度為m，根據校驗公式

上式展開得

展開該矩陣方程，并考慮到運算是在GF（2）中進行的，得到

如果校驗矩陣H是非奇異的，則滿秩，所以有

這樣就把碼字的校驗位計算出來了，這種方法需要保證H₂  是可逆的，而準循環LDPC碼因其結構化的特點可以保證這一條件。

• 基于生成矩陣G的編碼方案

令LDPC碼的校驗矩陣H分為兩部分:

其中子矩陣P的大小為c×c，Q的大小為c×m。計算

其中的矩陣運算為模二運算。求得的m×c矩陣W必定是一個稠密的準循環結構矩陣。由稠密的準循環結構矩陣W可以求得生成矩陣：

其中I是m×m的單位矩陣。可以看出生成矩陣具有準循環結構特性。得到生成矩陣G后將碼字X與其相乘C=X*G，獲得編碼后的碼字C。這里的乘法要滿足有限域的乘法法則。

LDPC譯碼

Gallager 在描述 LDPC 碼的時候，分別提出了硬判決譯碼算法和軟判決譯碼算法兩種。經過不斷發展，如今的硬判決算法已在 Gallager 算法基礎上進展很多，包含許多種加權比特翻轉譯碼算法及其改進形式。硬判決和軟判決各有優劣，可以適用于不同的應用場合。

• 比特翻轉算法（BF）

硬判決譯碼算法最早是 Gallager 在提出 LDPC 碼軟判決算法時的一種補充。硬判決譯碼的基本假設是當校驗方程不成立時，說明此時必定有比特位發生了錯誤，而所有可能發生錯誤的比特中不滿足校驗方程個數最多的比特發生錯誤的概率最大。在每次迭代時均翻轉發生錯誤概率最大的比特并用更新之后的碼字重新進行譯碼。具體步驟如下：

設置初始迭代次數 k1及其上限kmax 。對獲得的碼字y=（y1，y2…yn）按照下式展開二元硬判決得到接收碼字的硬判決序列Zn 。

若k₁=k_max ，則譯碼結束。不然，計算伴隨式s=(s0,s1,…sm-1)，sm表示第m個校驗方程的值。若伴隨式的值均為 0，說明碼字正確，譯碼成功。否則說明有比特位錯誤。繼續進行步驟3。

對每個比特，統計其不符合校驗方程的數量fn （1<=n<=N）

4. 將最大f_n 所對應的比特進行翻轉，然后k=k+1，返回步驟2。

      BF 算法的理論假設是若某個比特不滿足校驗方程的個數最多，則此比特是最有可能出錯的比特，因此，選擇這個比特進行翻轉。BF 算法舍棄了每個比特位的可靠度信息，單純的對碼字進行硬判決，理論最為簡單，實現起來最容易，但是性能也最差。當連續兩次迭代翻轉函數判斷同一個比特位為最易出錯的比特時，BF 算法會陷入死循環，大大降低了譯碼性能。

• 置信傳播算法（BP）

置信傳播(Belief Propagation)譯碼算法是消息傳遞(Message Passing)算法在 LDPC譯碼中的運用。消息傳遞算法是一個算法類，最初運用于人工智能領域，人們將其運用到 LDPC 碼的譯碼算法中，提出了LDPC 碼的置信傳播算法。置信傳播算法是基于 Tanner 圖的迭代譯碼算法。在迭代過程中，可靠性信息，即“消息”通過 Tanner圖上的邊在變量節點和校驗節點中來回傳遞，經多次迭代后趨于穩定值，然后據此進行最佳判決。

      在介紹BP譯碼算法之前需要先了解一下Tanner圖的概念。

      Tanner圖是一種表示LDPC碼的雙向圖，圖的下面每個節點表示碼字的一個比特位，稱比特節點（bit nodes）。上面每個節點稱為校驗節點（check nodes）。校驗矩陣中為1的元素，表示Tanner圖中比特節點和校驗節點之間存在連接邊，這條邊可稱為兩端節點的相鄰邊，相鄰邊兩端的節點稱為相鄰節點，每個節點相鄰邊數稱為該節點的度數。Tanner圖是用來描述LDPC碼結構的有效工具，同時也是迭代譯碼算法的參考工具。在Tanner圖中校驗節點和變量節點之間可以進行消息的可靠傳遞，首先變量節點接收初始化后驗概率進行計算，將得到的可靠信息傳遞給相鄰的校驗節點；經過校驗節點更新算法的計算，再將得到的運算結果傳回至與其相鄰的變量節點處，隨后變量節點再將由校驗節點得到的可靠信息以及初始化后驗概率信息進行處理；將最后得到的有效信息進行判決得到譯碼結果。

      LDPC碼的譯碼較為復雜，下面以置信傳播算法舉一個簡單的例子來說明一下。

      發送碼字C=(C9,C8,C7,C6,C5,C4,C3,C2,C1)，其監督矩陣H是

      則C必然滿足線性方程組HC^T = 0 ,即

      通過信道后接收到的碼字Y=(Y0,Y1,Y2,Y3,Y4,Y5,Y6,Y7,Y8,Y9)可能包含錯誤，因此伴隨式S= HY^T ≠ 0 。將此線性方程組用如圖所示的Tanner圖來表示。

圖中的X0,X1…X9稱為變量節點，代表10個比特C0,C1,C2…C9,它們是譯碼器待求解的未知變量。圖中的□成為校驗節點，代表線性方程組中的每一個校驗方程，連線就代表方程中此變量的系數為1。

      譯碼過程是在變量節點和校驗節點之間傳遞信息。每個變量節點告訴它所連接的校驗節點“我認為該變量是什么”，而校驗節點告訴它所連接的變量節點“我認為該變量應該是什么”。經過反復的消息傳遞后，變量節點和校驗節點不斷改變自己對各個變量是什么的看法，最終能形成一個滿足校驗方程的碼字，這就是譯碼的結果。如果經過充分的迭代后仍然不能形成一個滿足校驗方程的碼字，則譯碼器宣布它無法譯出這個碼字，即譯碼失敗。

• 置信傳播譯碼算法的基本流程如下：

      在迭代前，譯碼器接收到信道傳送過來的實值序列y=(y1,y2,….yn)，所有變量節點bi接收到對應的接收值yi。

      第一次迭代：每個變量節點給所有與之相鄰的校驗節點傳送一個可靠性消息，這個可靠性消息就是信道傳送過來的值；每個校驗節點接收到變量節點傳送過來的可靠性消息之后，進行處理，然后返回一個新的可靠性信息給與之相鄰的變量節點，這樣就完成了第一次迭代；此時可以進行判決，如果滿足校驗方程，則不需要再迭代，直接輸出判決結果，否則進行第二次迭代。

      第二次迭代：每個變量節點處理第一次迭代完成時校驗節點傳送過來的可靠性消息，處理完成后新的消息發送給校驗節點，同理，校驗節點處理完后返回給變量節點，這樣就完成了第二次迭代。完成后同樣進行判決，如果滿足校驗方程則結束譯碼，否則如此反復多次迭代，每次都進行判決，直到達到設定的最大迭代次數，譯碼失敗。在每次迭代過程中，無論是變量節點傳送給校驗節點的信息或者校驗節點傳送給變量節點的信息，都不應該包括前次迭代中接收方發送給發送方的信息，這樣是為了保證發送的信息與接收節點已得到的信息相互對立。

      假設在 AWGN 信道中，信道編碼后的碼字C=（c1,c2,…,cn）通過調制映射為調制序列X=（x1,x2…,xn）,然后經信道傳輸，接收的序列為y=(y1,y2…,yn)。

為后面章節的推導方便，先介紹一引理。

    引理：

          一個獨立的比特序列，其長度為m，假設第i個比特為 1 的概率為p_i ，則整個序列中出現偶數個1的概率為

出現奇數個 1 的概率為

這是信道編碼領域中經常使用的一個定理，故直接使用。

Gallager 定理：對于(n,j,k)規則 LDPC 碼，P_il 第i個校驗方程中第 l 校特為1的概率，則

其中:

P_r (x_i =0∣{y},S)表示在程組為S ，接收序列為y的條件下判斷發送幀中的第i個比特為0的概率

P_r(x_i =1∣{y},S)表示在程組為S，接收序列為 y的條件下判斷發送幀中的第i個比特為0的概率

p_i 表示發送序列的第 i位為1的先驗概率；

M(i) 表示校驗節點的集合，集合中的節點均與變量節點i相鄰；

N(j) 表示變量節點的集合，集合中的節點均與校驗節點 j相鄰。

由上節介紹的 BP 算法的原理及 Gallager 定理中的描述可知，變量節點i傳遞給校驗節點j的可靠性信息q{ij}(1)就是Pr?(X_j=1|{y},S)，于是定義

表示變量節點i ii傳遞給校驗節點j 的外部概率信息，即在得到除校驗節點j以外的其他所有校驗比特和信道的外部信息后，判斷變量節點c_i =1的概率。

再定義

表示變量節點i傳遞給校驗節點 j 的外部概率信息，即在得到除j 以外的其他所有校驗比特和信道的外部信息后，判斷變量節點c_i =0的概率。

另一方面，校驗節點 j傳遞給變量節點i的可靠性信息應該為在給定信息位和其他信息位具有獨立概率分布條件下，校驗方程 j滿足的概率。將此可靠性信息記為r_ji ,則

將上式代入

根據以上的描述和符號定義,概率 BP 譯碼算法流程可以歸納為如下幾個步驟:

（1） 初始化

計算經信道傳輸后各變量節點的初始概率p_i(1)和p_i (0)。然后對每個變量節點求傳遞給與其相鄰的校驗節點的可靠性信息

其中的上標(0)表示迭代次數。

2） 校驗節點處理過程（r_ij 的計算)

求出第l ll次迭代過程中校驗節點i遞給與之相鄰的變量節點j可靠性信息

其中的上標(l)和(l?1)均表示迭代次數。

（3）變量節點處理過程（q_ij 的計算)

求出第l 次迭代過程中變量節點j傳遞給與之相鄰的校驗節點i ii的可靠性信息

其中的K_ij 是校正因子，使每次計算出的

（4）譯碼判決

在本次迭代過程處理最后，重新計算各變量節點的可靠性信息

其中的 K_j 也為校正因子，目的是使

如果，那么這一點的估計值時c_i=1，否則估計值為c_i= 0。如果估計值滿足奇偶校驗方程，那么終止算法，否則算法繼續運行，直到達到預先設置的最大迭代次數。

仿真驗證

仿真說明如下：

下圖是在高斯信道下，碼字經過LDPC編碼和未編碼的譯碼結果對比圖，為了保證對比的有效性，仿真中LDPC碼與未編碼的碼字等長，同為1440，LDPC碼通過BP譯碼算法譯碼，而未編碼的碼字通過解調硬判決譯碼。

仿真結果分析：從圖可以看出碼字經過LDPC編譯碼之后其抵抗噪聲的能力極大加強，與未編碼的碼字相比，在誤碼率都為1e-4時，其性能提高了9.5dB左右，從而驗證了LDPC碼是一種性能極佳的信道糾錯碼。

• 結束語

目前LDPC碼研究領域的主要工作集中在譯碼算法的性能分析、編碼方法、碼的優化算法等，經過研究人員的努力，LDPC碼的研究取得很大進展，但仍有許多問題需要進一步研究：

（1）LDPC碼校驗矩陣的構造，盡管在構造最優的LDPC碼方面取得了一些進步，但目前還沒有一套系統的辦法來構造所需要的好碼，特別是在碼字長度有限、碼率一定的條件下，構造性能優異的好碼是一個非常具有挑戰性的課題。

（2）LDPC編碼系統的聯合優化設計，將編碼技術與調制技術、均衡技術、時空編碼技術、OFDM技術結合進行性能優化是當前及將來的發展方向之一。

（3）無線衰落信道及MIMO技術下LDPC碼的性能分析方法及優化設計準則。目前LDPC碼字的優化設計主要在加性高斯白噪聲信道下得到的，而無線衰落信道下，特別是時變信道非線性環境下碼字的性能分析方法、優化設計準則和信道估計的影響也是非常關鍵的課題，需要進一步的研究探索。

     此外，基于LDPC碼的鏈路自適應技術，LDPC碼在集成通信網物理層、應用層聯合優化系統中的應用,LDPC碼在無線局域網和深空宇航中的應用，基于LDPC碼的圖像傳輸、圖像數字水印系統中的應用以及尋找更適合硬件實現的LDPC碼編譯碼方法等都是非常值得研究的課題。