一種解碼方法中校驗節點的更新方法及解碼器與流程
2023-07-28 20:15:26 1
本發明涉及通信技術領域，具體涉及一種解碼方法中校驗節點的更新方法及解碼器。
背景技術：
信道編碼是保證通信系統和存儲系統可靠工作的關鍵技術。二進位低密度奇偶校驗(LDPC)碼是一類性能可逼近香農極限的線性糾錯碼。在過去的十餘年裡，二進位LDPC碼得到快速的發展並廣泛應用於通信和數據傳輸系統中。多進位LDPC碼可以表現出比二進位LDPC碼更好的糾錯能力，更低的錯誤平層並高度適用於高階調製。在無線通信、深空通信和數字存儲系統中，多進位LDPC碼都表現出了取代二進位LDPC碼的巨大潛力。然而，多進位LDPC碼的基於置信度傳播(BP)解碼算法的巨大複雜度一直阻礙其實際的應用。
多進位和積解碼算法(QSPA)是最優的BP解碼算法，但是其解碼複雜度也最大。對於有限域GF(q)(q＝2r)下的多進位LDPC碼，QSPA算法在解碼過程中，對每個碼字符號需要存儲和計算該符號全部q個域元素的置信度。校驗節點的更新運算是基於dc個長度為q的置信度向量之間的卷積運算。每個校驗節點運算需要dcq2數量級的計算量和計算複雜度。
因此，設計高效且解碼複雜度低，設計結構簡單的解碼算法來推動多進位LDPC碼在通信和存儲系統中的廣泛應用是亟待解決的問題。
技術實現要素：
為解決上述技術問題，本發明提供一種解碼方法中校驗節點的更新方法及解碼器，實現有效地匹配計算效率，提高解碼效率，降低在校驗節點的計算複雜度。
為實現上述目的，本發明提供以下技術方案：
一方面，本發明提供了一種解碼方法中校驗節點的更新方法，包括：
用網格圖表示輸入校驗節點的置信度向量；
將網格圖中的節點劃分為集合；
集合中的節點連接組成固定路徑；
通過固定路徑輸出置信度向量。
進一步的，所述將網格圖中的節點劃分為集合的步驟，之前還包括：
按照網格圖中每列第x個節點置信度值遞增或遞減的順序對網格圖中的每列進行排序。
進一步的，按照網格圖中每列第二個節點置信度值遞增或遞減的順序對網格圖中的每列進行排序。
進一步的，所述將網格圖中的節點劃分為集合的步驟，具體包括：
在網格圖中選取t行以及t行之前的所有節點組成集合1；
集合2的範圍為：在網格圖中t行之後，d行以及d行之前的，所述網格圖中第r行置信度值的最小值和次小值所在列的節點，其中r>t；
集合3的範圍為：在網格圖中d行之後，e行以及e行之前的，所述網格圖中第s行置信度值的最小值和次小值所在列的節點，其中s>d；
集合N的範圍為：在網格圖中f行之後，所述網格圖中第v行置信度值的最小值和次小值所在列的節點，其中v>f。
進一步的，所述通過固定路徑輸出置信度向量的步驟，之前還包括：
將固定路徑存儲至所述網格圖中的額外列中，通過額外列中的固定路徑輸出置信度向量。
進一步的，其特徵在於，將網格圖中第一行節點組成的固定路徑、含有一個偏離網格圖中第一行節點組成的固定路徑的節點所組成的固定路徑以及含有兩個偏離網格圖中第一行節點組成的固定路徑的節點所組成的固定路徑存儲至網格圖中的額外列中。
進一步的，所述通過額外列中的固定路徑輸出置信度向量的步驟，之後還包括：
將輸出置信度向量的順序調整為輸入校驗節點時的置信度向量的順序。
另一方面，本發明提供了一種解碼器，包括：
接收單元、初始化單元、變量節點更新單元、埠預調單元以及校驗節點更新單元；
所述接收單元，用於向初始化單元輸出符號信息向量；
所述初始化單元，用於將符號信息向量初始化並至二分圖中，並將符號信息向量傳遞給校驗節點更新單元；
所述校驗節點更新單元，用於對輸入校驗節點的符號信息向量進行更新運算並傳遞給變量節點更新單元；
所述變量節點更新單元，用於接收校驗節點更新單元輸出的符號信息向量並進行變量節點更新計算，將計算結果傳遞給校驗節點更新單元；
所述埠預調單元，用於根據輸入校驗節點更新單元的符號信息向量的順序調整校驗節點更新單元輸出的符號信息向量的順序。
進一步的，所述校驗節點更新單元包括：
校驗寄存器，用於存儲輸入的符號信息向量；
校驗比較器，用於讀取校驗寄存器中輸入的預設符號信息向量，選擇符號信息向量中最可信和次可信的元素；
校驗選擇器，用於選擇集合中的元素參與更新運算；
存儲器，用於存儲額外列中的校驗值。
進一步的，所述埠預調單元包括：
埠預調緩存器，用於存儲輸入校驗節點更新單元的符號信息向量；
埠預調比較器，用於讀取校驗寄存器中輸入的預設符號信息向量，選擇符號信息向量中最可信和次可信的元素；
埠預調選擇器，用於對緩存器中存儲的符號信息向量進行排序並輸出至校驗節點更新單元。
由上述技術方案可知，本發明所述的一種解碼方法中校驗節點的更新方法及解碼器，實現了降低了解碼算法的複雜度，降低了在校驗節點的計算複雜度。同時選取固定的偏差路徑、採用判決置信度可以在很小的解碼性能損失下，提高解碼吞吐量，減少硬體資源的消耗。
附圖說明
為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其他的附圖。
圖1是本發明實施例一提供的一種解碼方法中校驗節點的更新方法的流程示意圖；
圖2是本發明實施例提供的劃分集合數為4的網格圖；
圖3是本發明實施例二提供的一種解碼方法中校驗節點的更新方法的流程示意圖；
圖4是本發明實施例提供的校驗矩陣示意圖；
圖5是本發明實施例提供的Tanner圖；
圖6是本發明實施例提供的劃分集合數為2的網格圖；
圖7是本發明實施例三提供的一種解碼器的結構示意圖；
圖8是本發明實施例提供的校驗節點更新單元的結構示意圖；
圖9是本發明實施例提供的埠預調單元的結構示意圖；
圖10是本發明實施例提供的一種固定路徑解碼器中寄存器與比較器的連接電路示意圖。
具體實施方式
為使本發明實施例的目的、技術方案和優點更加清楚，下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整的描述，顯然，所描述的實施例是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員在沒有作出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。
信道編碼是保證通信系統和存儲系統可靠工作的關鍵技術。二進位LDPC碼得到快速的發展並廣泛應用於通信和數據傳輸系統中。多進位LDPC碼可以表現出比二進位LDPC碼更好的糾錯能力，更低的錯誤平層並高度適用於高階調製。然而，多進位LDPC碼的基於置信度傳播(BP)解碼算法的巨大複雜度一直阻礙其實際的應用。因此，設計高效且解碼複雜度低，設計結構簡單的解碼算法來推動多進位LDPC碼在通信和存儲系統中的廣泛應用是亟待解決的問題。為解決上述技術問題，本發明實施例提供一種解碼方法中校驗節點的更新方法及解碼器。
本發明實施例一提供一種解碼方法中校驗節點的更新方法，參見圖1，本發明的更新方法具體包括：
S101：用網格圖表示輸入校驗節點的置信度向量；
在本步驟中，首先根據信道接收來的比特信息序列計算出每個碼字符號的比特或者符號置信度向量，並用每個碼字符號的置信度向量初始化變量節點傳遞給校驗節點的邊信息。然後進行碼字判決，若是合法的碼字或者達到最大迭代次數，則終止解碼，輸出解碼結果，否則將置信度向量輸入校驗節點進行更新運算。
採用Rι,c和Rc,ι(0≤ι＜ρ)分別表示一個校驗節點的長度為nm輸入置信度向量和輸出置信度向量。Rsι,c和Rsc,ι分別存儲Rι,c和Rc,ι中每個置信度對應的域元素。用一個網格圖表示校驗節點的每個輸入向量，網格圖中的每一列對應於一個輸入置信度向量Rι,c和其對應的域元素向量Rsι,c。
S102：將網格圖中的節點劃分為集合；
在本步驟中，將網格圖中的所有列劃分為N個集合。集合1(S0)包含前t行的所有節點，t<<nm。很明顯，集合1包含了網格圖中絕大多數的最可靠的節點。集合2(S1)包含第e1行中最小值和次小值所對應列的第t+1～d1個節點(t<e1<d1),集合3(S2)包含第e2行中最小值和次小值所對應列的第d1+1～d2個節點(d1<e2<d2),依次類推，集合N(SN-1)包含第eN-1行中最小值和次小值所對應列的第dN-2+1～nm個節點(dN-2<eN-1<nm)。參見圖2，是一個行重為4的網格圖，t的取值為3，N＝4。
S103：集合中的節點連接組成固定路徑；
在本步驟中，網格圖中第一行節點的組合即為最可靠路徑，即ML路徑。在網格圖中引進一個額外列ΔRs存儲與最可靠路徑相比最多只有兩個位置偏差(偏差節點)的固定路徑的校驗值，這些偏差位置只能是N個集合中的元素，ΔR存儲ΔRs中每個校驗值的置信度。以t的取值為3，N＝4為例：ΔRs和ΔR的更新如下：
其中e1'和e1」分別表示網格圖中第e1行中最小值和次小值所對應的輸入向量的序號,e2'和e2」分別表示網格圖中第e2行中最小值和次小值所對應的輸入向量的序號,e3'和e3」分別表示網格圖中第e3行中最小值和次小值所對應的輸入向量的序號。
S104：通過固定路徑輸出置信度向量。
在本步驟中，將固定路徑存儲至所述網格圖中的額外列中，通過額外列中的固定路徑輸出置信度向量。將網格圖中第一行節點組成的固定路徑、含有一個偏離網格圖中第一行節點組成的固定路徑的節點所組成的固定路徑以及含有兩個偏離網格圖中第一行節點組成的固定路徑的節點所組成的固定路徑存儲至網格圖中的額外列中。
所述校驗節點輸出置信度向量的固定路徑為：
1、固定路徑存儲的置信度值小於集合N中第k行置信度值的最小值或次小值；其中，所述固定路徑存儲的置信度值為該固定路徑中所有節點的置信度值的和；即：
設置標記向量以判斷固定路徑的可靠性。以t的取值為3，N＝4為例：對於0≤k＜4ρ+2d3-8，兩個標記向量T和分別標誌ΔR中每個置信度是否小於和
2、排除含有該輸出的置信度向量中的偏差節點組成的固定路徑；即：
通過在ΔRs和ΔR中去掉自己所在列中的節點，若某固定路徑的偏差節點包含該輸出向量對應的輸入列中的節點，則捨棄該固定路徑。對於偏差節點不位於集合N中次小值所在列固定路徑，若T向量中對應的值為1，則捨棄該路徑；對於偏差節點位於集合N中次小值所在列固定路徑，若向量中對應的值為1，則捨棄該路徑。
從上述描述可知，本發明所提供的一種解碼方法中校驗節點的更新方法，減少了排序運算，並降低了在校驗節點的計算複雜度。同時可以並行地更新置信度信息，有效地匹配計算效率，提高解碼效率。
本發明實施例二提供一種解碼方法中校驗節點的更新方法，參見圖3，上述步驟S101之前，還包括如下步驟：
S100：按照網格圖中每列第x個節點置信度值遞增或遞減的順序對網格圖中的每列進行排序。
上述步驟S104之後，還包括如下步驟：
S105：將輸出置信度向量的順序調整為輸入校驗節點時的置信度向量的順序。
在本步驟中，將校驗節點輸出的置信度向量輸入值變量節點，變量節點接收進行更新運算的置信度向量後，將置信度向量傳遞給校驗節點；解碼器對變量節點輸出的碼字進行判決；直至解碼器譯出合法的碼字或者達到最大迭代次數，終止解碼，輸出解碼結果。
本發明提出的校驗節點更新方法是基於多進位LDPC碼的校驗矩陣Tanner圖的信息傳輸迭代解碼算法。Tanner圖結構由多進位LDPC碼的校驗矩陣H決定，參見圖4和圖5，為一個LDPC碼的校驗矩陣和它對應的Tanner圖。Tanner圖由變量節點和校驗節點以及連接這兩種節點的邊構成。變量節點(VN)和校驗節點(CN)分別代表校驗矩陣的每一列和每一行，如果在校驗矩陣H中元素第i行第j列的元素是非零元素，那麼就表示Tanner圖中第i個CN與第j個VN相連。多進位LDPC碼的基於Tanner圖的信息傳輸迭代解碼算法分為解碼初始化和解碼迭代兩部分，迭代過程包括如下步驟：解碼結果硬判決、校驗節點更新、變量節點更新，直到解碼成功或達到最大迭代次數時結束解碼。
本發明的校驗節點更新方法可以適用於任意概率解碼器，本發明以多進位LDPC碼為例對本發明的實施方式展開詳細描述。本發明的解碼過程中所有可靠性信息更新是在符號置信度形式下進行的，以下結合具體實例分別進行描述。
假設多進位LDPC碼由在有限域GF(q)(q＝2r)下大小為m×n，列重和行重分別為γ，ρ的奇偶校驗矩陣H的零空間定義。用h0,h1,...,hm-1表示矩陣H的每一行，其中hi＝(hi,0,hi,1,...,hi,n-1),0≤i＜m。令c＝(c0,c1,…,cn-1)是碼字空間中的一個碼，則c＝(c0,c1,…,cn-1)是一個長度為n的GF(2r)下的向量，該碼字向量可以用一個長度為nr的二進位向量等效表示。用cj(0≤j≤n-1)表示碼字的第j個符號，用cj＝(cj,0,cj,1,…,cj,r-1)表示第j個符號的二進位表示，cj,t表示第j個符號的第t位二進位位，值為0或1。當通信系統使用BPSK調製方式進行傳輸時，對碼字二進位表示的每一比特做如下映射：0→+1V，1→-1V。經過二進位輸入加性高斯白噪聲(BI-AWGN)信道後，系統接收到的碼字信息為y＝(y0,y1,...,yn-1)，其中yj＝(yj,0,yj,1,...,yj,r-1)為第j個碼字符號r個比特的對數似然比，0≤j≤n-1，0≤t≤r-1。z＝(z0,z1,…,zn-1)為硬判決接收向量，其中zj＝(zj,0,zj,1,...,zj,r-1)為第j個碼字符號r個硬判決比特。
第j個碼字符號的符號置信度向量可以通過一個長度q的對數似然比向量來計算：
其中，Pr(cj＝al|yj)是第j個碼字符號cj取域元素al∈GF(q)的後驗概率，因此，Lj[0]＝0,且Lj[l]越小，cj＝al越可靠。
對每個碼字的q-符號置信度向量只截取LLR最小的前nm個域元素及其對應的LLR值，即得到截取的信道輸出的碼字符號置信度向量：
Y＝[Y0,Y1,...,Yn-1]
其中對應的域元素向量為Yj,t＝Lj(SYj,t)，0≤j＜n，0≤t＜nm。定義變量節點節點j傳遞給CN節點i的邊信息為：及對應的域元素向量：使用信道輸出的碼字符號信息分別初始化Uj→i和SUj→i：
Uj→i,l＝Yj,l
SUj→i,l＝SYj→i,l
其中0≤j＜n，0≤j＜m，0≤l＜nm。
以一個校驗節點的更新為例，校驗節點更新運算規則如下：
Step1：Rι,c和Rc,ι(0≤ι＜ρ)分別表示一個CN的長度為nm輸入置信度向量和輸出置信度向量。Rsι,c和Rsc,ι分別存儲Rι,c和Rc,ι中每個置信度對應的域元素。用一個網格圖表示CN的每個輸入向量，網格圖中的每一列對應於一個輸入置信度向量Rι,c和其對應的域元素向量Rsι,c。將網格圖中的每一列按照其第二個元素置信度值的從小到大往右排序。排序後網格圖中第二行元素的大小關係如下：R0,c[1]≤R1,c[1]≤…≤Rρ-1,c[1]。將網格圖中的所有列劃分為兩個集合。集合1(S0)包含前t行的所有節點，t<<nm。很明顯，集合1包含了網格圖中絕大多數的最可靠的節點。集合2(S1)只包含第nm/2行中最小值和次小值所對應列的節點(這兩列各自的前t個節點除外)。參見圖6所示，是一個行重為4的網格圖，t的取值為3。
Step2：計算固定偏差路徑。網格圖中第一行元素的組合即為最可靠路徑，即ML路徑。在網格圖中引進一個額外列ΔRs存儲最可靠路徑最多只有兩個位置偏差的固定路徑的校驗值，這些偏差位置只能是集合1或者集合2中的元素，如圖6所示。ΔR存儲ΔRs中每個校驗值的置信度。ΔRs和ΔR的更新如下：
其中i'和i'『』分別表示網格圖中第行中最小值和次小值所對應的輸入向量的序號。
Step3：設置標記向量以判斷固定路徑的可靠性。對於0≤k＜4ρ+2nm-8，兩個標記向量T和分別標誌ΔR中每個置信度是否小於和
和
Step4：並行地更新CN的輸出向量。通過在ΔRs和ΔR中去掉自己所在列中的元素，CN的ρ個輸出向量Rsc,ι和Rc,ι的更新如下：
和
Rc,ι[d]＝ΔR[k]，
其中0≤ι＜ρ，0≤d＜nm，k的取值範圍由不同的情況決定。對於ι＝0，如果i′≠0，k的取值範圍是
{k:T[k]＝1}∩{k＝0or1＜k≤ρor2ρ≤k＜3ρ-2ork＞3ρ-2}，
否則，
對於1≤ι＜ρ，如果ι≠i′，k的取值範圍是
{k:T[k]＝1}∩{0≤k≤2ρ-1ork≥3ρ-2}∩{k≠ι+1andk≠ρ+ιandk≠3ρ+ι-2},
否則，
CN更新計算完成後再將對應輸出向量的順序調整回原順序，並將置信度向量傳遞給相鄰的VN，進行VN更新計算。
從上述描述可知，本發明提供一種解碼方法中校驗節點的更新方法，根據網格圖上不同偏差路徑的置信度差異的不同，將所述網格圖節點劃分成兩個集合，以集合為單位選取固定偏差路徑進行解碼過程中的計算。
本發明實施例三提供一種解碼器，參見圖7，本發明的解碼器具體包括：
接收單元、初始化單元、變量節點更新單元、埠預調單元以及校驗節點更新單元；
所述接收單元，用於向初始化單元輸出符號信息向量；
所述初始化單元，用於將符號信息向量初始化並至二分圖中，並將符號信息向量傳遞給校驗節點更新單元；
所述校驗節點更新單元，用於對輸入校驗節點的符號信息向量進行更新運算並傳遞給變量節點更新單元；
所述變量節點更新單元，用於接收校驗節點更新單元輸出的符號信息向量並進行變量節點更新計算，將計算結果傳遞給校驗節點更新單元；
所述埠預調單元，用於根據輸入校驗節點更新單元的符號信息向量的順序調整校驗節點更新單元輸出的符號信息向量的順序。
在具體實施時，校驗節點更新單元首先對所有輸入信息向量選取固定路徑構造出一個輔助信息向量，輔助信息向量中每個元素對應一條路徑，輸出信息向量中元素的計算為輔助信息向量中的元素減去各埠對應路徑上的輸入元素。變量節點更新單元將計算結果傳遞給校驗節點再次進行碼字判決，如此反覆迭代直到譯出正確碼字或直到達到最大迭代次數為止。
所述校驗節點更新單元包括：
校驗寄存器，用於存儲輸入的符號信息向量；
校驗比較器，用於讀取校驗寄存器中輸入的預設符號信息向量，選擇符號信息向量中最可信和次可信的元素；
校驗選擇器，用於選擇集合中的元素參與更新運算；
存儲器，用於存儲額外列中的校驗值。
在具體實施時，參見圖8，校驗節點更新單元(CNU)的硬體電路結構圖，四個埠的輸入信息向量首先分別緩存至四組寄存器中，並按順序計算額外信息向量中各元素。當預設偏差元素輸入時，比較器讀入這四個數據，找到最可信及次可信的元素和它們對應的埠，控制各埠的二選一數據選擇器選擇集合1中的元素或集合2中的元素參與運算。同時最可信及次可信元素還控制輸出緩存的寫使能，根據與最可信及次可信元素比較結果判斷輸出路徑是否保留，若輸出路徑的置信度小於最可信及次可信元素，則保留，否則捨棄。
所述埠預調單元包括：
埠預調緩存器，用於存儲輸入校驗節點更新單元的符號信息向量；
埠預調比較器，用於讀取校驗寄存器中輸入的預設符號信息向量，選擇符號信息向量中最可信和次可信的元素；
埠預調選擇器，用於對緩存器中存儲的符號信息向量進行排序並輸出至校驗節點更新單元。
在具體實施時，在信息向量輸入至校驗節點更新單元(CNU)進行計算前，需要根據每個信息向量第二個元素的大小將埠順序進行調整，CNU計算完成後再將埠調整回原順序。因此本發明設計了埠預調單元，參見圖9，首先對輸入信息向量進行緩存，比較器根據偏差為1的元素找到擁有最可信元素和次可信元素的兩個埠，左側兩個數據選擇器為dc選一多路選擇器，與所有緩存器的輸出相連，分別選通擁有最可信元素的信息向量和擁有次可信元素的信息向量，其餘數據選擇器為三選一多路選擇器，與原埠0、原埠1及原對應埠相連，原埠擁有最可信元素的選擇器選通原埠0的信息向量，原埠擁有次可信元素的選擇器選通原埠1的信息向量，其餘選擇器選通原埠數據。隨著行重的增加，只需增加若干緩存器和佔用資源較少的三選一多路選擇器，不會造成硬體資源佔用的大幅增加。
在CNU中，比較結果只在選擇網格圖集合2中的元素及輸出時對計算過程進行了控制，距預設偏差元素輸入有一定的時間間隔；而對於埠預調單元，由於當一個校驗節點的輸入數據全部輸入CNU模塊後，埠預調電路可以立即讀入下一個校驗節點的輸入數據並對埠順序進行調整，比較器的時延只對每次迭代第一個校驗節點的計算時延有影響。採用了圖10所示的並行輸入串行比較的方式，比較器接收到開始信號後對所有輸入數據進行緩存，首先比較前兩個埠的數據大小，存為最小值和次小值，接下來將第三個埠的數據與當前最小值和次小值進行比較，並根據結果更新最小值和次小值，同時將第三埠之後其他埠的數據全部移至前一埠數據寄存器，繼續將第三埠寄存器的數據與當前最小值和次小值進行比較，直至比較完所有埠數據。從輸入到輸出比較結果一共需要ρ個時鐘周期，當行重增加時，只需相應增加埠緩存寄存器，而比較邏輯電路不需要增加，可以在滿足時序要求的情況下減少硬體資源的佔用。
通過上述描述可知，通過本發明提供的固定路徑解碼器降低了解碼複雜度，尤其降低了在校驗節點的計算複雜度。同時本發明選取固定的偏差路徑、採用合適的判決置信度可以在很小的解碼性能損失，提高解碼吞吐量，減少硬體資源的消耗。
以上實施例僅用於說明本發明的技術方案，而非對其限制；儘管參照前述實施例對本發明進行了詳細的說明，本領域的普通技術人員應當理解：其依然可以對前述各實施例所記載的技術方案進行修改，或者對其中部分技術特徵進行等同替換；而這些修改或替換，並不使相應技術方案的本質脫離本發明各實施例技術方案的精神和範圍。