分層最小和ldpc解碼校驗節點處理的實現方法
2023-06-26 03:28:11 1
專利名稱：分層最小和ldpc解碼校驗節點處理的實現方法
技術領域：
本發明涉及一種LDPC解碼處理技術，尤其涉及一種分層最小和LDPC解碼校驗節點處 理的實現方法。
技術背景LDPC碼具有容易實現和複雜度低的特點，具有高編碼增益並提供了接近香農限的特性， 隨著VLSI技術的發展LDPC編碼被大量到商業通信系統所採用，其典型應用主要有衛星 DVB-S2、 WLAN802.11n、 WiMAX 802.16e、移動寬帶無線802.20、 IPTV、先進磁媒介存儲、 長距離光通信、無線個人區域網(WPAN) 802.12。LDPC屬於線性分組碼，可通過含有很少數目的非零元素的稀疏校驗矩陣來描述。某一 稀疏校驗矩陣H是由M行N列組成，列的數目N和信息比特經過編碼後得到的N比特碼字 相對應。碼字是由K- (N-M)個信息比特和M個校驗比特組成。通過二分圖(Tanner圖)可以以圖的方式來表示LDPC碼，如圖1所示。和校驗矩陣列 對應的碼字比特稱為變量節點或者比特節點v，和校驗矩陣行對應校驗比特稱為校驗節點c, 每個稀疏校驗矩陣H對應一個具有變量節點和校驗節點的二分圖，參見圖2。圖1所示的稀疏校驗矩陣H， LDPC碼對應的Tanner圖具有6個變量節點(圖1中所示 V,，V^,V3，^,^，^)和3個校驗節點(圖1中所示^^2,3)，碼字的長度N=6，校驗比特數 M=3，信息比特&= (N-M) =3，碼率R二K/N4/2。校驗矩陣中的元素為/^為1時表明第/校驗節點和第j'變量節點相關聯。稀疏校驗矩陣H屮的行數與碼字屮的M比特的校驗位相對應，在相應的Tanner圖(圖2)中有M:N-K個校 驗節點" 一個校驗節點對應一個校驗方程，N個變量節點中每個變量節點對應碼字信息中 的一個比特。用向量X表示的N比特LDPC編碼碼字，調製後經過高斯白噪聲信道信道傳輸，接收解 調後的碼字向量y可以表示為其中N代表向量I經過信道傳輸引入的高斯白噪聲。碼字y被接收解調後，首先計算接收碼字的對數似然比(LLR)。對數似然比是接收碼字 比特的先驗估計，作為LDPC解碼的軟判決輸入，相對硬判決輸入有利於提高LDPC解碼性能。針對此一稀疏校驗矩陣H，現有技術的處理方式使得運算的複雜度很卨，由於運算的復 雜性，需要大量的比較器，而且需要的比較器數量以變量節點數的平方的關係遞增，使得硬體開銷巨大。 發明內容本發明提出了一種分層最小和LDPC解碼校驗節點處理的實現方法，將LDPC的校驗矩 陣按校驗節點數分為多層，每層或每個校驗節點的解碼迭代稱為子迭代，每完成一次所有層 或所有校驗節點的子迭代則認為完成了一次校驗矩陣迭代前一層子迭代的輸出信息作為後 一層子迭代的輸入信息；前一次校驗矩陣迭代的輸出信息作為後一次校驗矩陣迭代的輸入信 息；連續的校驗矩陣迭代之間的子迭代次數連續計數；其創新點在於某一校驗節點，將與之相連的所有變量節點對應的a"和A」—'分別相減，採用冒泡法從所有相減結果中査找絕對值最小值和次最小值，根據査找結果對後一校驗節點的a'和更新，直到預先設定的子迭代次數或者迭代收斂為止；各層子迭代處理時，絕對值最小值和次最小值的查找採用同一硬體串行共享處理； 其中，上標/和/-1表示第/和/-1次子迭代；0/—'表示第糹-l次子迭代處理後各個變量 節點到校驗節點的輸入信息；1表示第/-1次子迭代處理後校驗節點到各個變量節點的輸 入信息g/和^/表示第/次子迭代處理需要更新的信息，g/表示第/次子迭代處理後各個 變量節點到校驗節點的輸入信息；及」表示第/次子迭代處理後校驗節點到各個變量節點的輸 入信息；該方法步驟為設某一校驗矩陣有/個校驗節點，每個校驗節點有《個變量節點與之相連，1 )第一次校驗矩陣迭代時，解碼器根據接收的碼字F計算其對數似然比A ，用A將各個變量節點到第一個校驗節點的信息a;,a^,a/,…a/初始化，第一個校驗節點到各個變量節點的信息《二《二^/，…iUG全部初始化為0;將a,。，e二a二…a/和id。,i^。,…iu。分別柳或，採用冒泡法從所有相減結果 中査找絕對值最小值和次最小值，根據査找結果對第二個校驗節點的aZ,e二Gj,…e,J和&J, w"'2',，…更新；2) 將仏'必2',化3',…aJ和W丄LU丄…^ 分別相減，採用冒泡法從所有相減結果中査找絕對值最小值和次最小值，根據査找結果對第三個校驗節點的a ，a/，G.32,…0^2禾口凡 ，及 22 ， Av32,...及"'&2更親f;3) 重複步驟2)，在第一次校驗矩陣迭代的子迭代次數內，若達到預先設定的迭代次數或者迭代收斂，則停止迭代；4) 若第一次校驗矩陣迭代完成，即/個校驗節點都更新完畢，還未達到預先設定的迭代 次數或者迭代未收斂，則將第 一 次校驗矩陣迭代的最後 一 次子迭代更新的2/',2;—'必"，…C和L"，l"^」—、作為第二次校驗矩陣迭代的第一 次子迭代的初始值，[1]將aZ-',a",a3'-',…eJ-'和ir,i2'—',l'—',…及d別相減，求得《個a信和各個A的符號Wgn(A)， 其中，A = {A"A2,A3, ...△」，l",…,A^ =0^-1*"; W^(A) = 0時為正，s/g"(A) = 1時為負；[2]採用冒泡法，從《個A中査找出lAl的最小值minO和次最小值minl ，記錄minO所對 應的變量節點序號"ww(minO);其中，lAl為各個A值的絕對值的集合；[3]設步驟[2]中查找到的min0所對應的m/附(min0hw， me[1，《]，若需要更新的g/和 尺/所對應的變量節點序號與minO所對應的變量節點序號相同，則i ，'的絕對值取minl ， 否則取minO; i ，'的符號為除當前節點序號對應的Wg"(AJ外其餘的Wg"(A)的乘積；5)重複步驟4)，在/個校驗節點的子迭代次數內，若達到預先設定的迭代次數或者迭代 收斂，則停止迭代，否則，將第二次校驗矩陣迭代的最後一次子迭代更新的a"必,',a,—1，...^2'-1和4/_1,^,1,凡/_1,..《^—1，作為第三次校驗矩陣迭代的第 一次子迭代的初始值，繼續進行迭代處理，直至達到預先設定的迭代次數或者迭代收斂為止。其中，變量節點到校驗節點的輸入信息用8bit 二進位補碼表示，校驗節點到變量節點的 輸入信息用6bit 二進位補碼表示。為了保證二進位補碼數據對稱性，在每個a計算後，對a的計算結果都進行飽和運算。本發明的有益技術效果是大大降低LDPC校驗矩陣的解碼迭代處理的複雜度，大大降 低解碼迭代處理的硬體開銷。
圖1、稀疏校驗矩陣；圖2、與圖l對應的二分圖；圖3、採用本發明方法的輸入信號處理流程框圖；圖4、採用本發明方法的輸出信號處理流程框圖；圖5、飽和處理環節；圖6、串行計算環節；具體實施方式
針對背景技術中描述的現有技術的不足，發明人經過潛心研究提出了一種分層最小和LDPC解碼校驗節點處理的實現方法，該方法與現有技術最大的不同之處在於將冒泡二值 査找算法引入LDPC的校驗矩陣解碼迭代處理中，使解碼迭代處理的複雜度從0(《)簡化為 <9(《)，並且對冒泡二值査找算法採用同一硬體串行共享處理，大大的降低了硬體開銷。 本發明方法的具體處理過程為設某一校驗矩陣有/個校驗節點(例如，Cl， cv…，。)，每個校驗節點有《個變量節點 與之相連，1) 第一次校驗矩陣迭代時，解碼器根據接收的碼字;r計算其對數似然比A，用A將各個 變量節點到第一個校驗節點的信息o^必/必/，…a/初始化，第一個校驗節點到各個變量節點的信息i^、A^，i^/,…i^/全部初始化為0;將a:,a2Q,a/,…a/和4二及,及，…^/分別相減，採用冒泡法從所有相減結果 中査找絕對值最小值和次最小值，根據查找結果對第二個校驗節點的az,a ,e丄…ej和L', "J ， "J,…、」更新；2) 將a入a"G丄…0j和&丄^UJ,…凡J分別相減，採用冒泡法從所有相減結果中查找絕對值最小值和次最小值，根據査找結果對第三個校驗節點的e二e^,a二…Ofc2 和/ d22,i^2,…/u2更新；3) 重複步驟2)，在第一次校驗矩陣迭代的子迭代次數內，若達到預先設定的迭代次數 或者迭代收斂，則停止迭代；4) 若第一次校驗矩陣迭代完成，即/個校驗節點都更新完畢，還未達到預先設定的迭代 次數或者迭代未收斂，則將第 一 次校驗矩陣迭代的最後 一 次子迭代更新的仏"必"必:"，…l"和L"人2"人3",…凡」—、作為第二次校驗矩陣迭代的第一次子迭代的初始值，[1]將仏"必2"必3"，...1'—'和l'—U:UJ—分別相減，求得《個A值和各個A的符號Wgw(A)，其中，"K，A2,A3,…A丄A^a"—L"，…,^二0^1— Wg"(A) = 0時為正，= 1時為負；[2]採用冒泡法，從《個A中査找出lAl的最小值minO和次最小值minl，記錄min0所對 應的變量節點序號"ww(min0);其中，lAl為各個A值的絕對值的集合；[3]設步驟[2]中査找到的min0所對應的",(min0^m，附e[1,《]，若需要更新的g/和 及」所對應的變量節點序號與minO所對應的變量節點序號相同，則的絕對值取minl ， 否則取minO; i ^/的符號為除當前節點序號對應的s/gw(AJ外其餘的Wgw(A)的乘積；gVffl'取e柳'二A"/ 二5)重複步驟4)，在/個校驗節點的子迭代次數內，若達到預先設定的迭代次數或者迭代 收斂，則停止迭代，否則，將第二次校驗矩陣迭代的最後一次子迭代更新的e/—',a/",a,1,…0/—'和^/—'兀,'a/—',…凡J"，作為第三次校驗矩陣迭代的第 一次子迭代的初始值，繼續進行迭代處理，直至達到預先設定的迭代次數或者迭代收斂為止。其中，變量節點到校驗節點的輸入信息用8bit二進位補碼表示，校驗節點到變量節點的輸入信息用6bit 二進位補碼表示。下面分別闡述本發明方法在兩種信號處理情況下的應用。 1、輸入信號處理輸入信號處理包括以下幾個環節1)依次計算4 =0^_1-及_"， (附e卩,《p並進行飽和處理；2)將A^寫入RAM; 3)串行計算Wg"(f[Am);4)根據lA,"l進行minO和min查找，同時記錄minO對應的序號；步驟l)中引入一個時鐘周 期的處理時延，2)、 3)和4)並行處理也引入一個時鐘周期的處理時延，輸入信號處理共引 入二個時鐘周期的處理時延。整個處理過程如圖3所示。和校驗節點的度《對應("度"表示有《個變量節點與校驗節點相連)，輸入信號處理的 每個環節都需要執行《次。步驟l)中的飽和處理(即飽和運算)環節在處理流程中的位置如圖5所示。0」_1用8 比特二進位補碼表示，i ，'—'用6比特二進位補碼表示，首先進行位擴展，即^"和i ，"都 擴展到9比特二進位補碼然後進行相減。進行飽和處理的原因是為了保證二進位補碼數據對 稱性，即飽和處理的數據取值範圍是-127到127。飽和處理首先判斷Oj—"-及，"的絕對值 是否大於127，如果小於127那麼^^G」—1-i CT)BM;否則根據a/'-及，w的符號產生飽 和處理結果，如果差是正數那麼^ =127，否則~=-127。步驟2)中，把依次產生的厶 寫入RAM。當輸入操作結束後從RAM讀出，進行a/必2',2丄…a;和i 丄iC2U丄…/u'的更新。步驟3)串行計算Wg"(]"[^)，如圖6所示，計算Wgw(]"]乂)通過異或(模2)操作實 現，Wgw(flAJ置初值0，然後對Wg"(AJ和Wgw(;QAJ進行異或(模2)操作產生新的俯"(Haj 。步驟4)如圖3所示，通過冒泡算法進行絕對值最小值和次最小值査找，這是本發明對 校驗節點處理的關鍵，利用冒泡算法可以大大降低硬體的複雜度，同時處理時延也得到保證。 數據輸入前首先對minO和minl賦初值127， www(min0)賦初值每產生新的|~|就進行一 次冒泡計算，冒泡過程如下如果lA」〈min01，把lA」賦值給minO，當前minO賦值給minl,當前處理的節點號m賦 值給"ww(min 0);如果min 0 < |Am | < min 1 ，把|AM|賦值給min 1 。2、輸出信號處理輸出信號處理包括以下幾個環節1)依次更新及_(， me[l，《];2)依次更新 0/，附e[l，《]。更新0j需要利用iC」的更新信息，因此輸出信號處理引入一個時鐘周期 的處理時延。整個處理過程如圖4所示。和校驗節點的度《對應，輸出信號處理的每個環節都需要執行《次。 步驟1)如圖4所示，更新及,」包括符號確定，minO和minl選擇，飽和處理三部分。 Wgw(AJ和Wg"(r7AJ進行異或(模2)計算，如果異或(模2)結果等於O那麼尺J 是正數，否則是負數。如果M腦(miiiO—;n，那麼i^」飽和處理前的數值等於minl，否則 飽和處理前的數值等於minO。因為minO和minl是8比特無符號數，i ，,'是6比特二進位補 碼，通過飽和處理把8比特二進位補碼數據轉換成6比特二進位補碼進行輸出，輸出數據範 圍-32~31，小於-32的數據用-32表示，大於31的數據用31表示。步驟2)如圖4所示，從RAM讀取數據z^，和相同序號m的i ，'相加，相加的結果進 行飽和處理產生OJ。 0J用8比特二進位補碼表示，《」和A^以9比特二進位補碼進行相 力口，如果飽和處理前數據大於127 ,更新的數據0J取127;如果飽和處理前數據小於-128 ，更新的數據a」取-i28。
權利要求
1、一種分層最小和LDPC解碼校驗節點處理的實現方法，將LDPC的校驗矩陣按校驗節點數分為多層，每層或每個校驗節點的解碼迭代稱為子迭代，每完成一次所有層或所有校驗節點的子迭代則認為完成了一次校驗矩陣迭代；前一層子迭代的輸出信息作為後一層子迭代的輸入信息；前一次校驗矩陣迭代的輸出信息作為後一次校驗矩陣迭代的輸入信息；連續的校驗矩陣迭代之間的子迭代次數連續計數；其特徵在於某一校驗節點，將與之相連的所有變量節點對應的Qvl-1和Rcvl-1分別相減，採用冒泡法從所有相減結果中查找絕對值最小值和次最小值，根據查找結果對後一校驗節點的Qvl和Rcvl更新，直到預先設定的子迭代次數或者迭代收斂為止；各層子迭代處理時，絕對值最小值和次最小值的查找採用同一硬體串行共享處理；其中，上標l和l-1表示第l和l-1次子迭代；Qvl-1表示第l-1次子迭代處理後各個變量節點到校驗節點的輸入信息；Rcvl-1表示第l-1次子迭代處理後校驗節點到各個變量節點的輸入信息；Qvl和Rcvl表示第l次子迭代處理需要更新的信息，Qvl表示第l次子迭代處理後各個變量節點到校驗節點的輸入信息；Rcvl表示第l次子迭代處理後校驗節點到各個變量節點的輸入信息
2、根據權利要求1所述的分層最小和LDPC解碼校驗節點處理的實現方法，其特徵在於 該方法歩驟為設某一校驗矩陣有/個校驗節點，每個校驗節點有《個變量節點與之相連，1) 第一次校驗矩陣迭代時，解碼器根據接收的碼字r計算其對數似然比x，用人將各個變量節點到第一個校驗節點的信息2/,0」,G了,…a/初始化，第一個校驗節點到各個變量 節點的信息/dA及J，…iUQ全部初始化為0;將2二a/，a/，…a^和^Q，及,^。,…^/分別相減，採用冒泡法從所有相減結果 中查找絕對值最小值和次最小值，根據查找結果對第二個校驗節點的g丄0j，2丄…込j和2) 將G丄e二d1和Cd',…u1分別相減，採用冒泡法從所有相減結 果中査找絕對值最小值和次最小值，根據查找結果對第三個校驗節點的e,a/，e^,…&J和尺？，A二&32，…^fc2更新；3) 重複歩驟2)，在第一次校驗矩陣迭代的子迭代次數內，若達到預先設定的迭代次數或者迭代收斂，則停止迭代；4) 若第一次校驗矩陣迭代完成，即/個校驗節點都更新完畢，還未達到預先設定的迭代 次數或者迭代未收斂，則將第 一 次校驗矩陣迭代的最後 一 次子迭代更新的a,'—'必2'—'，a/—',…aV和wdd'-'，…L"，作為第二次校驗矩陣迭代的第一 次子迭代的初始值，[1]將","必2"必3'—',…2j—'和Ld'-UC…及C'分別相減'求得《個A值 和各個A的符號Wgw(A;)，其中，A-",，A2,A3,…A丄A，=aZ—'—d'—'，...,△& =Gj_1—l*M;= 0時為正，= 1時為負； [2〗採用冒泡法，從《個A中查找出|A|的最小值minO和次最小值minl ，記錄min0所對 應的變量節點序號"wm(minO);其中，lAl為各個A值的絕對值的集合；[3]設步驟[2]中査找到的min0所對應的",(min0):w ， we[1，《]，若需要更新的0/和 尺,/所對應的變量節點序號與minO所對應的變量節點序號相同，則i ，,'的絕對值取minl ， 否則取minO;及 /的符號為除當前節點序號對應的Wg"(AJ外其餘的WgW(A)的乘積；g」5)重複步驟4)，在/個校驗節點的子迭代次數內，若達到預先設定的迭代次數或者迭代收斂，則停止迭代，否則，將第二次校驗矩陣迭代的最後一次子迭代更新的 a,',a,'必,V'.a,'和尺/—UJ'-'人,1,.《/—'，作為第三次校驗矩陣迭代的第一次子迭代的初始值，繼續進行迭代處理，直至達到預先設定的迭代次數或者迭代收斂為止； 其中，變量節點到校驗節點的輸入信息用8bit二進位補碼表示，校驗節點到變量節點的輸入信息用6bit 二進位補碼表示。
3、根據權利要求2所述的分層最小和LDPC解碼校驗節點處理的實現方法，其特徵在於在每個A計算後，對A的計算結果進行飽和運算。
全文摘要
本發明公開了一種分層最小和LDPC解碼校驗節點處理的實現方法某一校驗節點，將與之相連的所有變量節點對應的Qvl-1和Rcvl-1分別相減，採用冒泡法從所有相減結果中查找絕對值最小值和次最小值，根據查找結果對後一校驗節點的Qvl和Rcvl更新，直到預先設定的子迭代次數或者迭代收斂為止；各層子迭代處理時，絕對值最小值和次最小值的查找採用同一硬體串行共享處理；本發明的有益技術效果是大大降低LDPC校驗矩陣的解碼迭代處理的複雜度，大大降低解碼迭代處理的硬體開銷。
文檔編號H03M13/00GK101615914SQ20091010416
公開日2009年12月30日 申請日期2009年6月24日 優先權日2009年6月24日
發明者佳 劉, 李建國, 波 楊, 陶小魚 申請人:重慶金美通信有限責任公司