中國數字電視地面廣播標準ldpc碼畢業論文(編輯修改稿)

　

【文章內容簡介】 的稀疏性，它具有Tanner圖這樣的數學模型，因此理論分析相對簡單。20世紀90年代，人們利用定義在Tanner圖對LDPC碼的譯碼性能進行分析，目前己經有了一些較為完善的理論，人們還發現基于稀疏圖的LDPC碼具有非常接近Shannon限的性能。這一章首先介紹線性分組碼的原理，然后簡介LDPC碼的圖論基礎知識，最后給出LDPC碼的分類。線性分組碼在糾錯碼中有很重要的地位，它的數學模型簡單，較易對其進行性能分析。而LDPC碼本質上就是一種線性分組碼，它通過一個生成矩陣G將信息序列映射成碼字序列。每一個生成矩陣G，都存在一個奇偶校驗矩陣H，所有的碼字序列C構成了H的零空間。線性分組碼的信息位和監督位之間的關系滿足一組線形代數方程。一個(N，K)線性分組碼的編碼就是根據己知的K個信息比特求出NK個校驗比特，因此必須有NK個線形獨立的方程。如果線性分組碼的前K位就是原來的信息比特，后NK位是監督位，則稱之為線形系統碼。設二進制線性分組碼(N，K)的校驗矩陣為，碼字為z，則H的每一行與它的碼字的內積均為零，即式(21)成立。 （21）線性分組碼的最小距離就是碼的最小重量(除全“0”碼字外)。線性分組碼有兩個重要的參數，一個是最小碼距，它反映了碼的檢糾錯能力，值越大檢糾錯能力越強。另一個是碼率R=K/N ，它表示信息位在碼組中所占的比重，體現了編碼效率。 LDPC碼的圖結構在圖論中一個圖是由頂點和邊組成的，其中的樹(tree)和二分圖(bipartite graph)都可被用來描述和分析LDPC碼。二分圖中所有的頂點分為兩個子集，任何一個子集內部各個頂點之間沒有邊相連，任意一個頂點都和一個不在同一個子集里的頂點相連。 樹Gallager 用校驗樹來表示H矩陣[2]，用以說明消息在置信傳播譯碼中傳播的過程。在這之后，表示LDPC矩陣的樹圖有了改進，如圖21所示。一條斜線和與其上端相連的一條橫線代表一個校驗方程，線上的節點即為構成此校驗方程的節點：圖21中，黑點代表校驗節點，白點代表變量節點。圖中有兩層結構，由上至下，第一層表示為校驗方程c，第二層表示參與c的信息節點v，第三層表示v參與的其余校驗方程，第四層代表參與上一層校驗方程的其它信息節點。如果繼續衍生下去，將會出現相同節點。圖21變量節點v的校驗樹 Tanner圖1981年Tanner建立了編碼的圖模型概念，并證明了和積算法在無環圖中譯碼的最佳性，后來人們將應用于編碼領域的二分圖稱為Tanner 圖。LDPC碼可以用一個Tanner圖來表征，Tanner圖和校驗矩陣一一對應。圖中包含三種元素，變量節點(Variable node) 、校驗節點(Check node)和連接它們的邊，其中變量節點內部和校驗節點內部沒有任何邊連接，只有在變量節點和校驗節點之間才有邊相連接，任意一對變量節點和校驗節點最多只有一條邊相連。Tanner圖中的每一條連線對應于校驗矩陣中的‘1’。而且對于一個碼長為N，碼率R=K/N的線性碼，它的校驗數目是M=NK。任意一個線性碼都可以用一個Tanner圖來表示，而LDPC的Tanner圖是稀疏的，每一個變量節點只和少數幾個校驗節點相連，每一個校驗節點也只和少數幾個變量節點相連。使得圖中邊的數目幾乎正比于碼長N，而不是N的二次方。下面以一個(6，3) 線性分組碼說明二分圖。以(6，3)線性分組碼的校驗矩陣和其二分圖，圖中上面的節點是變量節點，下面的節點是校驗節點。校驗矩陣: (22)相應的二分圖:圖 22 (6，3)線性分組碼的校驗方程和對應的二分圖圖22的第一行節點表示發送的比特(稱為變量節點)，第二行是它們滿足的校驗(稱為校驗節點)。圖中變量節點集合V=()和校驗節點集C=()內部不存在相連的邊，但兩類節點之間存在著連線。變量節點和校驗節點之間存在連線意味著該變量比特參加了此校驗式，也就是校驗矩陣某一行中‘1’的位置。每個節點上的連線數目稱為該節點的次數(degree)，圖22，變量節點的次數都是=2，校驗節點的次數都是=3。可以把Tanner圖拆成一個一個的子碼(subcode) ，例如圖2－3所示：圖23(6，3)線性分組碼的一個子碼LDPC碼是線性分組碼的一種，它的最小漢明距離決定了性能優劣，然而一般情況下，LDPC碼的碼長較長，無法直接求出一個碼的最小距離。而Tanner圖中的“環”在一定程度上反映了譯碼性能。Tanner圖中由變量節點、校驗節點和邊首尾相連組成的閉合環路稱為“環”。環的長度就是其中邊的數目。從LDPC碼的Tanner圖中可以看出，每個節點都會存在許多這樣的閉合環路，且每個環的周長一定是2的整數倍。在圖22變量節點就參與了一個長度為6的環，如圖中粗線所示，由起，經過，最后返回。環在LDFC碼的迭代解碼過程中會造成不良影響，形成無效信息的正反饋，使迭代解碼無法達到最佳性能，環是如何影響譯碼性能將在譯碼章節中詳細說明。理論和實踐均己證明，Tanner圖中的環，特別是短環對迭代解碼的性能影響很大。Tanner圖中最短環的周長稱為最小圈長girth，例如圖22girth是6。girth的越大，最小距離的下界越大，碼的糾錯能力越強，Tanner給出了最小距離的下界和girth的關系式： （23）其中，D為LDPC碼的最小碼距，g為LDPC碼的girth，y為變量節點的次數，d為二分圖中子碼(subcode) 的最小碼距。如果二分圖的girth等于4，將會影響LDPC碼的誤碼率性能，所以在構造LDPC碼的校驗矩陣時，要盡量避免二分圖中出現girth為4的情況。 LDPC碼的分類LDPC碼有多種分類方法，例如按行重、列重是否是定值劃分，可以分為規則碼和非規則碼；按所在的域劃分，分為二元域和多元域的碼。下面將分別介紹這兩種分類。 規則碼和非規則碼1. 規則(regular)LDPC碼如果LDPC碼的校驗矩陣行列重量固定為，即每個校驗方程有比特參與校驗，每個變量參與個校驗方程，我們稱之為規則LDPC碼。這也是Gallager最初提出的Gallager碼的特點。我們用Gallager對LDPC碼的表示方法：將碼長為N，行重、列重分別為和的LDPC碼稱為(N，)LDPC碼。從Tanner圖的角度來看，這種LDPC碼的變量節點次數全部為，而校驗節點的次數都為。上例就是一個規則的(6，2，3)LDPC碼，相應的圖22，第一行每個變量節點與3條線相連，第二行校驗節點與2條線相連。可以適當放寬上述規則LDPC碼的條件，行或列的重量可以不是固定的整數，但行列重量盡量服從均勻分布。另外為了保證LDPC碼的Tanner圖上不存在長度為4的圈，通常要求行與行以及列與列之間的交疊部分重量不超過1。當校驗矩陣H滿秩時，規則碼的碼率R=(NM)/N=K/M=1，當校驗矩陣H不滿秩時，R=(N一rank(H)/N=K/M。Mackay在文獻[13]中證明了在任意信道中，1)規則LDPC碼滿足了好碼(Good codes)定理的要求，即在固定列重，碼長N足夠長的情況下，存在一個0到信道傳輸容量之間的值r，在此速率下可以實現無差錯傳輸。2)規則LDPC碼滿足了更好碼(very Good Codes)定理的要求，即如果不固定列重，當/M很小時，此LDPC碼可以很接近信道容量。 2. 非規則(irregular)LDPC碼在Tanner圖中，信息節點希望能參與盡可能多的校驗方程，以便更準確的判斷自己。而校驗節點希望向盡可能少的信息節點傳遞消息，以確保更準確的判斷信息節點。非規則LDPC在此要求下受到人們的重視。Luby[12]分析了非規則的性能和構造好的非規則碼的方法。非規則碼的行列重已不再是固定值，即每個變量節點參與的校驗式數目或每個校驗式中含有的變量節點數目不再保持均勻，而是有意設置部分突出的變量節點和校驗節點。在譯碼過程中，那些參與較多校驗式的變量節點迅速得到正確譯碼信息，然后它們給相鄰的校驗節點更加有效的概率信息，而這些校驗節點又可以給與它們相鄰的次數少的變量節點更多的信息。整個譯碼的過程呈現出一種波狀效應，次數越高的變量節點首先獲得正確信息，然后是次數較低的節點，然后依次往下，直到次數最低的變量節點。正是這種波浪效應，使得非規則碼獲得比規則更好的譯碼性能。 二元域和多元域的碼Matthew ，將其放到了多元域GF(q)上。假設在域GF(2)和域GF(q)()上構造的LDPC碼所對應的校驗矩陣分別是和中的元素是0或1，而是由元素0，1，q1構成，中的每個元素都是中p個元素的組合。從矩陣看將相應GF(2)域中相應的1q向量代入GF(q)域的，得到的二進制形式，調節檢驗矩陣可以增加與之對應的二進制校驗矩陣中列的平均重量，從的Tanner圖看，結構并沒有改變，不會造成節點之間短圈數目的增加。對于二進制LDPC碼來說，如果它的校驗矩陣H的列重量增大，那么它的性能也增加，但是如果增加列重量會使得Tanner圖中各節點之間的短環數目急劇增加，從而使BP算法的性能下降。而在GF(q)域上構造的LDPC正好可以解決這個矛盾。例如在GF(16)上構造的規則碼性能已經和Turbo碼相差無幾。第三章 LDPC碼的編碼與譯碼 LDPC碼的構造LDPC碼是線性分組碼，可以由校驗矩陣H等效描述，所以我們只要構造了該碼的校驗矩陣就完成了LDPC碼的構造。 Gallager的構造方法Gallager 1962年最初的工作中，給出了正則碼的構造方法：對碼長為N的正則碼，他將校驗矩陣按行水平