国产精品免费看久久久_日韩在线不卡精品视频_免费鲁丝片中文字幕在线_欧美激情性爱小说视频_日韩欧美亚洲范冰冰与中字_亚洲精品国产网红在线观看91_麻豆精品一区二区色播_日本护士野外奶水hd_免费A级网站视频_網友分享草的爽免费视频心得

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

LDPC碼簡介

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

• LDPC碼的特點

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

• 譯碼算法的選擇

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

• Tanner圖

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

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

LDPC編碼

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

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

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

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

上式展開得

展開該矩陣方程，并考慮到運(yùn)算是在GF（2）中進(jìn)行的，得到

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

這樣就把碼字的校驗位計算出來了，這種方法需要保證H₂  是可逆的，而準(zhǔn)循環(huán)LDPC碼因其結(jié)構(gòu)化的特點可以保證這一條件。

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

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

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

其中的矩陣運(yùn)算為模二運(yùn)算。求得的m×c矩陣W必定是一個稠密的準(zhǔn)循環(huán)結(jié)構(gòu)矩陣。由稠密的準(zhǔn)循環(huán)結(jié)構(gòu)矩陣W可以求得生成矩陣：

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

LDPC譯碼

Gallager 在描述 LDPC 碼的時候，分別提出了硬判決譯碼算法和軟判決譯碼算法兩種。經(jīng)過不斷發(fā)展，如今的硬判決算法已在 Gallager 算法基礎(chǔ)上進(jìn)展很多，包含許多種加權(quán)比特翻轉(zhuǎn)譯碼算法及其改進(jìn)形式。硬判決和軟判決各有優(yōu)劣，可以適用于不同的應(yīng)用場合。

• 比特翻轉(zhuǎn)算法（BF）

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

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

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

對每個比特，統(tǒng)計其不符合校驗方程的數(shù)量fn （1<=n<=N）

4. 將最大f_n 所對應(yīng)的比特進(jìn)行翻轉(zhuǎn)，然后k=k+1，返回步驟2。

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

• 置信傳播算法（BP）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為后面章節(jié)的推導(dǎo)方便，先介紹一引理。

    引理：

          一個獨立的比特序列，其長度為m，假設(shè)第i個比特為 1 的概率為p_i ，則整個序列中出現(xiàn)偶數(shù)個1的概率為

出現(xiàn)奇數(shù)個 1 的概率為

這是信道編碼領(lǐng)域中經(jīng)常使用的一個定理，故直接使用。

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

其中:

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

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

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

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

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

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

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

再定義

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

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

將上式代入

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

（1） 初始化

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

其中的上標(biāo)(0)表示迭代次數(shù)。

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

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

其中的上標(biāo)(l)和(l?1)均表示迭代次數(shù)。

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

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

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

（4）譯碼判決

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

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

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

仿真驗證

仿真說明如下：

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

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

• 結(jié)束語

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

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

（2）LDPC編碼系統(tǒng)的聯(lián)合優(yōu)化設(shè)計，將編碼技術(shù)與調(diào)制技術(shù)、均衡技術(shù)、時空編碼技術(shù)、OFDM技術(shù)結(jié)合進(jìn)行性能優(yōu)化是當(dāng)前及將來的發(fā)展方向之一。

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

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