基於網格複雜度的LDPC碼兩階段解碼方法與流程
2023-08-04 00:04:16 1
本發明屬於通信技術領域，涉及通信數據傳輸中所用的ldpc碼信道編碼方案的一種新的高效解碼算法，具體是一種基於網格複雜度的ldpc碼兩階段解碼方法。
技術背景
近年來，對高效可靠的數字傳輸和存儲系統的需求日益增長。這種需求隨著在商業、政府和軍事領域面向數字信息的交換、處理和存儲的大規模高速數據網的出現而變得更加迫切。如何保證這些數據準確快速的交換、處理是我們需要解決的問題。這其中的一種重要的方法就是在數據進入新到傳輸時先對所要傳輸的數據進行適當的編碼，通過對索要傳輸的增加數據增加冗餘信息，使得我們可以對數據傳輸中所產生的錯誤進行檢測和糾正，這種技術被稱為信道編碼技術，隨著越來越多的人研究信道編碼技術，現在已經出現了許多高效的信道編碼方案。
ldpc碼就是眾多性能優異的信道編碼方案中的一種。隨著3gpp最終選定ldpc碼為5g中長碼編碼方案，ldpc碼的高效性越來越受到研究者的重視，對於一套信道編碼方案而言，能否找到一種有效的解碼算法，即低時間複雜度和低解碼錯誤概率，是該信道編碼最終應用於實際的重要因素。
對於ldpc碼而言，目前主流的解碼算法有比特翻轉解碼算法、和積解碼算法、最小和解碼算法，其中和積解碼算法是一類在碼因子圖上的解碼算法，當因子圖中不存在環的時候，它的解碼錯誤概率是所有已知解碼算法中最小的，但是當因子圖中存在4元或者6元環時，會嚴重影響和積解碼算法的解碼錯誤概率，而到目前為止，還沒有找到一種行之有效的方法來解決這個問題。
因此當ldpc碼的因子圖中存在4元或6元短環時，設計一種不受短環影響的高效解碼算法具有極其重要的實際意義。
目前沒有發現同本發明類似技術的說明或報導，也尚未收集到國內外類似的資料。
技術實現要素：
為了降低在4元環和6元環存在時，ldpc碼的解碼錯誤概率，本發明提出了一種基於網格複雜度的ldpc碼兩階段解碼方法，該解碼方法，適用於ldpc碼的可靠高效的解碼體系。該解碼方法解決了傳統和積解碼算法的ldpc碼因子圖存在4元6元短環時，解碼性能變壞的問題。同時針對不同的線性碼，對該解碼方法兩階段各自使用的解碼算法進行針對性的變換後可以被應到相應線性碼的解碼中，即該解碼方法具有極強的普遍適用性。
本發明是通過以下技術方案實現的。
本發明所提出的基於網格複雜度的ldpc碼兩階段解碼方法，包括如下步驟：
-第一階段解碼，所述第一階段解碼在超ldpc碼中採用第一階段解碼算法，得到超碼碼字，當超碼碼字滿足校驗結果時，則作為最終的解碼輸出碼字；當超碼碼字不滿足校驗結果時，進行第二階段解碼；
-第二階段解碼，在原ldpc碼中採用第二階段解碼算法，得到最終的解碼輸出碼字。
優選地，所述第一階段解碼算法採用和積解碼算法，包括如下步驟：
將編碼完成後的原ldpc碼的校驗矩陣中出現4元和6元短環的行全部刪除，利用刪除後的校驗矩陣構造得到原ldpc碼的超ldpc碼，並用該超ldpc碼的校驗矩陣構造超因子圖，對接收到的數據向量在超因子圖上運用和積解碼算法，在和積解碼算法結束時，得到超碼碼字。
優選地，在進行和積解碼算法時，每次迭代過程更新校驗節點的狀態信息和變量節點的狀態信息，直到得到正確的超碼碼字或達到最大迭代次數時停止和積解碼算法。
優選地，校驗結果為：
設校驗式s＝c′ht，其中，c′為超碼碼字，h為原ldpc碼的校驗矩陣，t為矩陣轉置；當s＝0，則超碼碼字為最終的解碼輸出碼字；當s≠0時，則執行第二階段解碼。
優選地，所述第二階段解碼算法採用優先級算法，，包括如下步驟：
利用原ldpc碼的校驗矩陣構造一個碼網格，並利用第一階段解碼中得到的超碼碼字，對接收到的數據向量在碼網格上使用優先級算法。
優選地，運用優先級算法時，先構造一個代價函數，該代價函數包括兩部分，一部分為優先級算法找到的從初始結點到當前節點最小路徑，另一部分為從當前節點到目標節點最小路徑的預測；對於每一個訪問節點，計算該訪問節點的代價函數，並從該訪問節點的代價函數中選擇具有最小代價函數值的節點，直到搜尋到目標節點時結束優先級算法；在完成第二階段解碼算法之後，將得到最終的解碼輸出碼字。
優選地，第二階段解碼中得到的最終的解碼輸出碼字為最大似然碼字。
與現有技術相比，本發明具有如下有益效果：
1、本發明提供的基於網格複雜度的ldpc碼兩階段解碼方法，是一種適用於ldpc碼的可靠高效的解碼體系，採用兩階段混合設計，以此保證解碼算法的最優性；
2、本發明可以靈活的變換兩個階段中各自使用的解碼算法，並將兩階段解碼算法運用於其他線性碼的解碼中；
3、本發明降低了在4元環和6元環存在時，ldpc碼的解碼錯誤概率；
4、本發明具有極強的普遍適用性。
附圖說明
圖1為原ldpc碼校驗矩陣與超ldpc碼校驗矩陣，其中，(a)為原ldpc碼，該原ldpc碼為(3，3)規則ldpc碼，(b)為超ldpc碼，該超ldpc碼為非規則ldpc碼；
圖2為超ldpc碼的超因子圖；
圖3為第一階段和積解碼算法校驗節點與變量節點消息更新(傳遞)說明圖；
圖4為第二階段優先級解碼算法流程圖。
具體實施方式
下面對本發明的實施例作詳細說明：本實施例在以本發明技術方案為前提下進行實施，給出了詳細的實施方式和具體的操作過程。應當指出的是，對本領域的普通技術人員來說，在不脫離本發明構思的前提下，還可以做出若干變形和改進，這些都屬於本發明的保護範圍。
本實施例提供的基於網格複雜度的ldpc碼兩階段解碼方法，包括如下步驟：
-第一階段解碼，所述第一階段解碼在超ldpc碼中採用第一階段解碼算法，得到超碼碼字，當超碼碼字滿足校驗結果時，則作為最終的解碼輸出碼字；當超碼碼字不滿足校驗結果時，進行第二階段解碼；
-第二階段解碼，在原ldpc碼中採用第二階段解碼算法，得到最終的解碼輸出碼字。
進一步地，第一階段解碼，採用和積解碼算法。對於編碼完成後的原ldpc碼c和接收到的數據向量r，首先將原ldpc碼c的校驗矩陣中出現4元和6元短環的行全部刪除，利用刪除後的校驗矩陣構造可以得到原ldpc碼的一個超ldpc碼，並用該超ldpc碼的校驗矩陣構造超因子圖，對接收到的數據向量r在超因子圖上運用和積解碼算法；在進行和積解碼算法時，每次迭代過程更新校驗節點的狀態信息和變量節點的狀態信息，直到得到正確的超碼字或達到最大迭代次數時停止和積解碼算法，在該階段結束時，可以得到一個超碼字c′屬於超碼，判斷這個超碼碼字是否滿足校驗結果；當不滿足校驗結果時，利用這個超碼碼字進行第二階段解碼。
進一步地，第二階段解碼，採用優先級算法。將原ldpc解碼看成圖上最短路徑搜尋問題，用原ldpc碼的校驗矩陣構造一個碼網格，在碼網格上使用優先級算法，運用優先級算法時先構造一個代價函數，該代價函數包括兩部分，一部分為優先級算法找到的從初始結點到當前節點最小路徑，另一部分為從當前節點到目標節點最小路徑的預測；對於每一個訪問節點，計算它們的代價函數，並從中選擇具有最小代價函數值的節點，直到算法搜尋到目標節點時結束解碼算法；在完成第二階段解碼算法之後，得到一個最終的解碼輸出碼字c。
由於本實施例提供的基於網格複雜度的ldpc碼兩階段解碼方法分為兩個階段解碼，第一階段在超ldpc碼的因子圖上優選使用和積解碼算法，第二階段是在原ldpc碼的碼網格圖上優選使用優先級解碼算法，對於第一階段解碼算法複雜度，可以利用已知的結論得到，對於第二階段解碼算法的時間複雜度，因為對於網格圖上的解碼算法，其解碼算法的時間複雜度與網格的結構複雜度有直接的關係，而對於同一個ldpc碼而言，經過不同的列置換所得到的碼網格圖的結構有很大的差異，此處利用子碼與超碼網格複雜度之間的關係來得到第二階段解碼算法的時間複雜度。
下面結合流程圖對本發明的實施步驟做簡要說明：
如圖1所示：
第一階段解碼：
步驟s1：刪除原ldpc碼因子圖中出現4元環(或6元環)的相應校驗矩陣h的行，用剩餘的校驗矩陣h′構造超因子圖t。
步驟s2：在超因子圖t上使用和積解碼算法：
用n(j)表示與校驗式cj相連的所有比特分量集合，m(i)表示所有與變量比特vi相連的校驗方程集合。m(i)/j表示集合m(i)中除去校驗方程j後，剩餘校驗方程組成的集合，n(i)/j表示集合n(i)中除去變量比特vi後，剩餘變量比特組成的集合。令表示在集合m(i)/j中所有校驗節點狀態已知的情況下，變量比特vi＝a成立的概率，表示在集合n(i)/j中所有變量節點狀態已知，且vi＝a的情況下，校驗和式cj成立的概率。接下來引入對數度量：
同時定義對數域中的消息更新方程為：
s2.1.對校驗節點計算更新方程：
對於每一個校驗節點j以及與它相連的變量節點i∈n(j)，
s2.2.對變量節點計算更新方程：
對於每一個變量節點i以及與它相連的校驗節點j∈m(i)，
λi→j(qij)＝λ(xi)+{∑j′∈m(i)\jλj′→i(rji)}
s2.3.嘗試解碼，
計算變量節點判別式
λ(xi)＝l(xi)+{∑j′∈m(i)λj→i(rji)}
將對應的數據比特xi進行解碼，
步驟s3：解碼輸出第一階段碼字c′。
步驟s4：計算校驗式s＝c′ht，若s＝0則輸出碼字c′為最終解碼結果。若s≠0則執行步驟s1。
第二階段解碼：
如圖2所示：
步驟s1：利用原ldpc碼的校驗矩陣構造碼字網格圖g。
步驟s2：在原ldpc碼網格g上使用優先級算法：
將接收到的向量r＝(r1，r2，...，rn)，將其變為φ＝(φ1，φ2，...，φn)，其中，
同時將φ＝(φ1，φ2，...，φn)中各個元素按照絕對值從大到小排列得到置換後的向量為φ′＝(φ1′，φ2′，...，φn′)。為了使用優先級算法，需要建立代價函數f，對於算法進行中的任意一個訪問節點m，其代價函數有兩部分組成，即f(m)＝g(m)+h(m)，其中g(m)表示從初始節點到節點m的最小代價，h(m)從節點m到目標節點的最小代價。
對於在網格圖第1層的任意訪問節點m，定義g(m)為：
其中表示算法所找到的到節點m的最短路徑pm′的標籤。
對於h(m)利用ldpc碼的性質來構造：
令m表示在第1層的節點，且表示由算法找到的從初始節點到m的最短路徑pm′的標籤，建立一個集合，
其中，dh(v，c′)表示向量v與第一階段解碼輸出碼字c′之間的漢明距離，集合表示碼字集合中所有碼字所具有的不同的漢明重量，表示所有屬於超ldpc碼而不屬於原ldpc碼c的碼字集合，hw(v)表示向量v的漢明重量。
則構造h(m)為，
s2.1.建立一個open表格，將網格g的起始節點s-1加入到open中。
s2.2.創建一個closed表格，且初始化為空。
s2.3.將open中具有最小代價函數值f，且沒有在closed中出現過的節點m加入到closed中，並將該節點從open中刪除。
s2.4.將節點m的所有之前未出現在open中的子節點加入到open中，並計算這些子節點的代價函數f的值。
s2.5.如果節點m是目標節點，則解碼成功。
步驟s3：輸出第二階段解碼碼字並將其作為解碼算法的最終解碼結果c。
在本實施例中，
第一階段解碼：在超ldpc碼中優先使用和積解碼算法。
第二階段解碼，在原ldpc碼上優先使用優先級算法。
採用兩階段混合設計，以此保證解碼算法的最優性。
可以靈活的變換兩個階段中各自使用的解碼算法，並將該算法運用於其他線性碼的解碼中。
在第一階段解碼中，刪除原ldpc碼校驗矩陣中使得因子圖出現4元或6元短環的行，用刪除後的校驗矩陣構造超因子圖，並在超因子圖上使用和積解碼算法。
在第二階段解碼中，對原ldpc碼的網格圖上使用優先級算法。
第二階段解碼中得到的最終的解碼輸出碼字是最大似然碼字。
對於ldpc碼進行解碼時，可以將第一階段的和積解碼算法變換為其他適合於ldpc碼的高效解碼算法，例如線性規劃解碼算法(linearprogrammingdecodingalgorithm)、最小和解碼算法(min-sumalgorithm)。同時可以將第二階段的優先級解碼算法變換為其他複雜度低易於實現的解碼算法，例如列表解碼算法(listdecodingalgorithm)。
可以利用變換前或變換後的兩階段解碼算法對其他已有的線性信道編碼方案進行解碼。
本實施例提供的基於網格複雜度的ldpc碼兩階段解碼方法，是針對5g長碼編碼方案的ldpc碼的一種高效的解碼算法，有效的降低了ldpc碼的解碼錯誤概率。首先刪除原ldpc碼校驗矩陣中產生4元和6元短環的行，得到一套超ldpc碼，對接收到的信息比特在超ldpc碼的因子圖中使用和積解碼算法進行解碼。之後對於不滿足校驗方程的碼字進行第二階段解碼，利用ldpc碼的校驗矩陣構造碼網格圖，並在該碼網格圖上使用優先級算法。本實施例有效的降低了在ldpc碼存在短環情況下的解碼錯誤概率，由於對於兩階段中各自使用的解碼算法進行更改可以使用到其他線性碼的解碼中，所以本實施例對線性碼具有普適性。
以上對本發明的具體實施例進行了描述。需要理解的是，本發明並不局限於上述特定實施方式，本領域技術人員可以在權利要求的範圍內做出各種變形或修改，這並不影響本發明的實質內容。