[發明專利]一種改進的LDPC碼的線性規劃譯碼方法

有效

• 申請號: 201110086722.X
• 申請日: 2011-04-07
• 公開（公告）號: CN102130745A
• 公開（公告）日: 2011-07-20
• 發明（設計）人: 馬丕明;張嫻
• 申請（專利權）人: 山東大學
• 主分類號: H04L1/00
• 分類號: H04L1/00;H03M13/11
• 代理公司: 濟南金迪知識產權代理有限公司 37219
• 代理人: 許德山

1.一種改進的LDPC碼的線性規劃譯碼方法，用于通信系統信號接收端的譯碼模塊，以實現從含有噪聲及干擾的接收序列中最大化無失真地恢復出信道發端信息的功能；預先設C是一個具有m×n維校驗矩陣H＝{h_j，i}的n長二進制LDPC碼，I和J分別表示其變量節點的集合和校驗節點的集合，其中，I＝{1，2，......，n}，J＝{1，2，......，m}；N(j)表示同校驗節點j相連的變量節點的集合，即N(j)＝{i：i∈I，h_i，j＝1}；V表示N(j)的具有奇數個元素的子集；C_j表示第j個校驗節點的本地碼，即所有滿足第j個校驗方程的二進制序列的集合，P_i表示C_j的凸包；假設碼C中的碼字y經過一個二進制離散無記憶對稱信道后，信道收端接收到一個受過噪聲和干擾影響的序列y*；該方法步驟如下：

A.初始化

將信道收端收到的第i(i＝1，2，......，n)個變量節點的消息初始化為該節點的對數最大似然消息γ_i；在高斯白噪聲信道下，采用二進制相移鍵控調制時，

γi=ln(Pr[yi*|yi=0]Pr[yi*|yi=1])=2yi*2σ2---(1)]]>

其中y_i表示信道發送端的符號，σ²為該信道的噪聲方差，Pr[·]表示對括號里所表示的事件求概率；

B.建立原始線性規劃譯碼模型，求解線性規劃問題

將本地碼字凸包的交集P作為原始線性規劃的可行域多面體，即可行域多面體其中P_i表示滿足第j個校驗方程的本地碼字的凸包，將作為目標函數，表示將接收序列中第i(i＝1，2，......，n)個變量節點的消息比特譯為“1”的總代價，其中f_i表示原始線性規劃可行域中可行點的第i個元素的取值，建立如下原始線性規劃譯碼模型：

最小化：γ^Tf??使得：f∈P，????????(2)

其中，γ＝[γ₁，γ₂，......γ_n]^T表示由所有變量節點的初始消息組成的列向量，γ^T表示γ的轉置向量，f＝[f₁，f₂，......，f_n]^T表示可行域中的可行點，根據奇偶校驗方程得可行域多面體P的表達式為：

0≤f_i≤1，i＝1，2，......，n，?????(3)

Σi∈Vfi-Σi∈N(j)/Vfi≤|V|-1,]]>∀V⊆N(j),]]>j＝1，2，......，m，(4)

其中，f_i表示變量節點i在可行點f中的取值，N(j)表示同校驗節點j相連的變量節點的集合，V表示N(j)的具有奇數個元素的子集，符號“|·|”表示取集合中元素的個數，表示集合與集合之間的從屬關系，即“屬于或者等于”，符號“·/·”表示左右兩個集合的差集，符號表示對集合中的任何一個取值；不等式(3)將變量節點的集合I中每個變量節點的取值都限制在區間[0，1]上，不等式(4)將不滿足任何校驗方程的具有壞結構的二進制序列排除出可行域；求解上述原始線性規劃問題，其最優解即為可行域多面體P中使目標函數取最小值的點；

C.判決

如果原始線性規劃的最優解f^Δ全由整數元素組成，即對任意變量節點i(i＝1，2，......，n)，其在點f^Δ中的取值都滿足其中f^Δ表示原始線性規劃可行域中具有最小目標函數值的點，譯碼終止，譯碼器將原始最優解作為最大似然碼字輸出，否則，此解為錯誤解，進入下一步；

D.添加冗余重新譯碼

記當前錯誤解為f^err，從當前錯誤解中將取值為分數的變量節點提取出來，假設共有L個這樣的變量節點，令對原始校驗矩陣H進行自適應初等行變換得到其等價校驗矩陣對校驗節點j(j＝1，2，......，min{m，L})，記k_j＝|K_j|，其中表示矩陣中同第j個校驗節點相連的變量節點的集合，U表示在當前錯誤解f^err中取值為分數的變量節點的集合，u表示集合U中的變量節點，表示變量節點u在錯誤解f^err中的取值，A_j表示矩陣中既與校驗節點j相連又在錯誤解f^err中取值為分數的變量節點的集合，s表示集合A_j中的變量節點，K_j表示矩陣中既與校驗節點j相連又在錯誤f^err中取值為1的變量節點的集合，k_j表示集合K_j中元素的個數，K′_j表示矩陣中既與校驗節點j相連又在錯誤f^err中取值為0的變量節點的集合，h表示集合K_j中的變量節點，表示變量節點h在錯誤解f^err中的取值，h′表示集合K′_j中的變量節點，表示變量節點h′在錯誤解f^err中的取值，當|A_j|＝1時，即矩陣中與校驗節點j相連的變量節點中有且只有一個在錯誤解f^err中取值為分數，如果k_j是奇數，那么關于校驗節點j的有效冗余校驗為

Σh∈Kjfh-fs-Σh′∈Kj′fh′≤kj-1,---(5)]]>

其中f_h、f_s、f_h′分別表示變量節點h、s、h′在可行點f中的取值，如果k_j是偶數，那么關于校驗節點j的有效冗余校驗為

Σh∈Kjfh+fs-Σh′∈Kj′fh′≤kj,---(6)]]>

當|A_j|≥2時，如果k_j是奇數并且其中表示變量節點s在錯誤解f^err中的取值，那么關于校驗節點j的有效冗余校驗為

Σh∈Kjfh-Σs∈Ajfs-Σh′∈Kj′fh′≤kj-1,---(7)]]>

如果k_j是偶數，記s^max為集合A_j中在錯誤解f^err中取值最大的那個變量節點，記該變量節點在錯誤解f^err中的取值為那么有如果那么關于校驗節點j的有效冗余校驗為

Σh∈Kjfh+fsmax-Σs∈Aj/smaxfs-Σh′∈Kj′fh′≤kj;---(8)]]>

其中表示變量節點s^max在可行點f中的取值；將得到的所有冗余校驗不等式添加至原始線性規劃問題中，重新譯碼；

E.判斷結果輸出

如果此時的解全由整數元素組成，譯碼模塊輸出最大似然碼字，否則，譯碼模塊輸出錯誤或者返回步驟D，繼續添加冗余，重新譯碼，直到獲得最大似然碼字或者達到預期要求；

F.算法結束，譯碼終止。