多進(jìn)制ldpc碼的編碼算法研究

多進(jìn)制ldpc碼的編碼算法研究

0多進(jìn)制ldpc碼編碼算法196年，garago首次提出了ldpc（低密度奇偶校驗(yàn)）代碼。目前針對(duì)多進(jìn)制LDPC編碼的算法主要有直接編碼算法、近似下三角編碼算法和準(zhǔn)循環(huán)RA結(jié)構(gòu)編碼算法。直接編碼算法原理簡(jiǎn)單,計(jì)算復(fù)雜度較高,但對(duì)校驗(yàn)矩陣無(wú)要求;近似下三角編碼算法,也叫做RU編碼算法,該算法要求校驗(yàn)矩陣具有下三角或可化簡(jiǎn)為下三角構(gòu)造,算法復(fù)雜度有所減小,但該種結(jié)構(gòu)的碼在性能上會(huì)有損失多進(jìn)制LDPC譯碼算法復(fù)雜度高,大量計(jì)算集中在校驗(yàn)節(jié)點(diǎn)的更新,因此目前針對(duì)多進(jìn)制LDPC譯碼算法的改進(jìn)主要在校驗(yàn)節(jié)點(diǎn)更新算法的簡(jiǎn)化上。最初Davey和MacKay提出概率域和積譯碼算法(QSPA),該算法運(yùn)算量太大,硬件無(wú)法實(shí)現(xiàn);HenkWymccrsch等人提出對(duì)數(shù)域和積譯碼算法(log-SPA)本文所述多進(jìn)制LDPC碼應(yīng)用背景校驗(yàn)矩陣為64進(jìn)制、維度為44×88的普通稀疏矩陣,并不具有下三角或準(zhǔn)循環(huán)結(jié)構(gòu),因此編碼算法采用直接編碼算法,提出一種利用查表法計(jì)算伽羅華域乘法運(yùn)算的方法,有效降低了直接編碼算法的計(jì)算復(fù)雜度,提高了編碼效率。譯碼算法在TMM的基礎(chǔ)上,對(duì)其進(jìn)行了Matlab仿真驗(yàn)證,并對(duì)硬件實(shí)現(xiàn)方法進(jìn)行了進(jìn)一步優(yōu)化,提出了多個(gè)關(guān)鍵模塊的優(yōu)化設(shè)計(jì)方案,如整體架構(gòu)設(shè)計(jì)、交換網(wǎng)絡(luò)設(shè)計(jì)、存儲(chǔ)單元設(shè)計(jì)、比較最小次小值單元設(shè)計(jì)等。最后以64進(jìn)制44×88的校驗(yàn)矩陣為例進(jìn)行編譯碼的FPGA實(shí)現(xiàn)。本文提出的設(shè)計(jì)方案有效解決了多進(jìn)制LDPC譯碼工程實(shí)現(xiàn)中資源消耗過(guò)大的問(wèn)題,并在工程實(shí)踐中得到驗(yàn)證。150.ldtc碼的多輸入1.1編碼算法流程假設(shè)校驗(yàn)矩陣為:待編碼信息向量為:式中,x編碼后的信息向量為c=[x由校驗(yàn)矩陣性質(zhì)c·H直接編碼算法即根據(jù)式(1),由待編碼信息和校驗(yàn)矩陣直接計(jì)算得出冗余位。流程圖如圖1所示。具體步驟如下:(1)接收并存儲(chǔ)待編碼的信息;(2)將待編碼信息與變換后的校驗(yàn)矩陣在伽羅華域相乘;(3)乘法運(yùn)算的結(jié)果在伽羅華域相加;(4)與待編碼信息組合輸出編碼后的信息比特。1.2多進(jìn)制ldpc的譯碼過(guò)程多進(jìn)制LDPC譯碼算法主體步驟類(lèi)似于二進(jìn)制LDPC譯碼算法,主要包括初始化、迭代更新和輸出判決。主要區(qū)別在于多進(jìn)制LDPC譯碼過(guò)程中所涉及到的除概率外的計(jì)算均在伽羅華域GF(q)中進(jìn)行,另外,在迭代更新過(guò)程中由于多進(jìn)制LDPC每個(gè)節(jié)點(diǎn)有q個(gè)取值的可能,計(jì)算復(fù)雜度明顯增加。對(duì)于校驗(yàn)矩陣H1.2.1數(shù)值積分法處理初始化的目的是根據(jù)接收到的信息完成每個(gè)信息對(duì)應(yīng)q個(gè)取值的概率。對(duì)數(shù)操作可將乘除法運(yùn)算變?yōu)榧訙p法運(yùn)算,顯著降低計(jì)算量。歸一化的目的是使所有的概率取值為非負(fù),為方便后續(xù)計(jì)算,此時(shí)概率越小表示置信度越高。具體計(jì)算公式如下:式中,L1.2.2計(jì)算變量節(jié)點(diǎn)更新值q迭代更新包括變量節(jié)點(diǎn)更新和校驗(yàn)節(jié)點(diǎn)更新,根據(jù)初始化信息,通過(guò)一定次數(shù)的反復(fù)迭代計(jì)算,最終使變量節(jié)點(diǎn)真值位置概率最小,具體計(jì)算公式如下:式中,Q計(jì)算變量節(jié)點(diǎn)更新值Q按照m=1,2…M的順序進(jìn)行更新,在完成M行計(jì)算后表示一次迭代更新結(jié)束,重新開(kāi)始下一次迭代更新,在完成設(shè)置次數(shù)的迭代更新后,迭代更新步驟完成。1.2.3校驗(yàn)節(jié)點(diǎn)的更新根據(jù)迭代更新步驟計(jì)算的變量節(jié)點(diǎn)信息,比較計(jì)算最小值所在位置即為譯碼結(jié)果,具體計(jì)算公式如下:式中,TMM譯碼算法在計(jì)算校驗(yàn)節(jié)點(diǎn)更新時(shí)通過(guò)額外引入一列中間變量,使得校驗(yàn)節(jié)點(diǎn)的更新值在每行最小值、次小值和額外引入的值之間選取,整個(gè)計(jì)算過(guò)程只涉及比較和賦值運(yùn)算,不涉及數(shù)據(jù)位的擴(kuò)展,大大簡(jiǎn)化了計(jì)算量,易于硬件實(shí)現(xiàn)。TMM的具體計(jì)算步驟如下,假設(shè)輸入為Q式中,z1.3古希臘域元素表示法編譯碼算法中涉及到的關(guān)于位置的運(yùn)算均在伽羅華域GF(q)中進(jìn)行,伽羅華域元素可以由本原表示和矢量表示,表1為GF(8)域元素表示法對(duì)照表。伽羅華域中的運(yùn)算與普通域中運(yùn)算有所不同,加法運(yùn)算為矢量表示按位異或;乘法運(yùn)算中本原表示為0的元素與任何元素相乘仍為0,本原表示非0的元素乘法運(yùn)算為本原元素的冪次模(22仿真結(jié)果分析采用Matlab對(duì)多進(jìn)制LDPC直接編碼算法及TMM譯碼算法進(jìn)行仿真驗(yàn)證。以GF(64)域校驗(yàn)矩陣為H仿真結(jié)果如圖2所示,為便于比較引入同樣為528bit碼長(zhǎng)的二進(jìn)制LDPC由仿真結(jié)果可以看出,多進(jìn)制LDPCTMM譯碼算法原理正確,比同樣碼長(zhǎng)的二進(jìn)制LDPC性能要好,GF(64)LDPC譯碼性能優(yōu)于GF(2)LDPC約0.3dB。3硬件安裝3.1校驗(yàn)矩陣模塊直接編碼算法具體硬件實(shí)現(xiàn)整體框圖如圖3所示,包括存儲(chǔ)模塊、校驗(yàn)矩陣模塊、伽羅華域乘法器、伽羅華域加法器、組合模塊和控制模塊。存儲(chǔ)模塊用于接收待編碼信息,并在控制模塊的作用下以p比特為單位存儲(chǔ)待編碼信息,將待編碼信息分別發(fā)送至伽羅華域乘法器和組合模塊。校驗(yàn)矩陣模塊用于存儲(chǔ)對(duì)校驗(yàn)矩陣進(jìn)行變換后得到的矩陣:將變換后的校驗(yàn)矩陣每一行的值存入一個(gè)存儲(chǔ)單元,并在控制模塊的作用下將各個(gè)存儲(chǔ)單元中的值發(fā)送至伽羅華域乘法器,所述的校驗(yàn)矩陣模塊包括M個(gè)存儲(chǔ)單元。伽羅華域乘法器用于每次提取各個(gè)存儲(chǔ)單元中相同列數(shù)的一個(gè)值,將提取值與待編碼信息在伽羅華域相乘,得到乘法運(yùn)算的結(jié)果輸出至伽羅華域加法器。伽羅華域加法器用于將乘法運(yùn)算的結(jié)果在伽羅華域采用按位異或的方法相加,將相加的結(jié)果輸出至組合模塊。組合模塊用于在控制模塊的作用下將相加的結(jié)果與待編碼信息組合,輸出編碼后的信息?？刂颇K用于控制存儲(chǔ)模塊中輸入數(shù)據(jù)的存儲(chǔ)、校驗(yàn)矩陣模塊輸入伽羅華域乘法器的數(shù)據(jù)以及編碼信息的輸出。伽羅華域乘法器采用查表法實(shí)現(xiàn),實(shí)現(xiàn)框圖如圖4所示,包括第一查找表、第二查找表、模23.2迭代控制模塊TMM譯碼算法整體實(shí)現(xiàn)框圖如圖5所示,主要包括初始化模塊、迭代更新模塊、存儲(chǔ)模塊、輸出判決模塊和迭代控制模塊。初始化模塊用于在迭代控制模塊的作用下接收待譯碼信息,計(jì)算所有輸入的待譯碼信息的后驗(yàn)概率,從所有后驗(yàn)概率中找到最大的后驗(yàn)概率,并根據(jù)最大后驗(yàn)概率初始化待譯碼信息,將初始化后的待譯碼信息輸出至存儲(chǔ)模塊,并將本模塊運(yùn)行狀態(tài)報(bào)告給迭代控制模塊。迭代更新模塊用于在迭代控制模塊的作用下從存儲(chǔ)模塊中讀取初始化后的待譯碼信息、前一次校驗(yàn)節(jié)點(diǎn)的迭代更新值和變量節(jié)點(diǎn)的迭代更新值,計(jì)算本次校驗(yàn)節(jié)點(diǎn)及變量節(jié)點(diǎn)的迭代更新值,將更新值存入存儲(chǔ)模塊,并將本模塊運(yùn)行狀態(tài)報(bào)告給迭代控制模塊。輸出判決模塊用于在迭代控制模塊的作用下從存儲(chǔ)模塊中讀取最后一次變量節(jié)點(diǎn)的迭代更新值,根據(jù)最后一次變量節(jié)點(diǎn)的迭代更新值進(jìn)行譯碼輸出計(jì)算,輸出譯碼后的信息,并將本模塊運(yùn)行狀態(tài)報(bào)告迭代控制模塊。存儲(chǔ)模塊用于存儲(chǔ)初始化信息、2組變量節(jié)點(diǎn)信息、校驗(yàn)節(jié)點(diǎn)信息、校驗(yàn)矩陣信息,接收初始化模塊送入的初始化信息,與迭代更新模塊進(jìn)行初始化、變量節(jié)點(diǎn)、校驗(yàn)節(jié)點(diǎn)、校驗(yàn)矩陣的信息交互,并將最后一次更新的變量節(jié)點(diǎn)信息送入輸出判決模塊。迭代控制模塊用于接收初始化模塊、迭代更新模塊和輸出判決模塊的運(yùn)行狀態(tài),并控制初始化模塊、迭代更新模塊和輸出判決模塊的工作狀態(tài)。迭代更新模塊是整個(gè)譯碼算法中最關(guān)鍵的一部分,算法的核心部分都集中在該模塊,具體實(shí)現(xiàn)框圖如圖6所示。整個(gè)模塊的輸入包括初始化信息L本次變量節(jié)點(diǎn)信息Q該模塊中與概率有關(guān)的運(yùn)算均在普通域中進(jìn)行,與位置有關(guān)的運(yùn)算均在伽羅華域中進(jìn)行。置換模塊(P和P最小值次小值及最小值對(duì)應(yīng)列查找模塊(2minfinder)設(shè)計(jì)2個(gè)基本的比較單元,一個(gè)比較單元輸入為2個(gè)被比較值及其所對(duì)應(yīng)列,輸出為最小值、次小值及最小值對(duì)應(yīng)的列;另一個(gè)比較單元輸入為2組最小值、次小值及最小值對(duì)應(yīng)的列,輸出為最小值、次小值及最小值對(duì)應(yīng)的列。通過(guò)這2種比較器的組合可實(shí)現(xiàn)任意多個(gè)輸入的最小值次小值及最小值對(duì)應(yīng)列信息查找。具體實(shí)現(xiàn)框圖如圖7所示。額外列提取模塊(ExtraColumn)根據(jù)最小值及最小值所在的列信息在配置集conf整個(gè)提取過(guò)程通過(guò)二級(jí)比較運(yùn)算和一級(jí)選擇運(yùn)算實(shí)現(xiàn)。第一級(jí)比較運(yùn)算通過(guò)3個(gè)兩輸入一輸出的最大值比較器實(shí)現(xiàn),隨后輸出至二選一選擇器的一個(gè)輸入口,選擇器另一個(gè)輸入口輸入固定最大值,以確保在列信息相等時(shí)不會(huì)被下一級(jí)最小值查找單元選中。選擇器通過(guò)對(duì)應(yīng)的列信息進(jìn)行選擇,若對(duì)應(yīng)的列信息相等則輸出最大值,否則輸出2個(gè)參與比較的較大的一個(gè),選擇器的輸出送入最小值查找單元。在計(jì)算ΔQ4生成編碼運(yùn)算由于多進(jìn)制LDPC譯碼算法較為復(fù)雜,即使采用計(jì)算復(fù)雜度最小的TMM算法仍要在資源占用和計(jì)算延遲方面權(quán)衡考慮,本文在硬件實(shí)現(xiàn)時(shí)大部分計(jì)算以一個(gè)節(jié)點(diǎn)為最小單位進(jìn)行串行運(yùn)算,這樣可以最大化地減小資源消耗。在進(jìn)行m本文以GF(64)域校驗(yàn)矩陣為H編譯碼器實(shí)現(xiàn)后Modelsim仿真結(jié)果分別如圖9和圖10所示。編碼器只需要7個(gè)時(shí)鐘周期即可得出第一個(gè)校驗(yàn)位計(jì)算結(jié)果,再經(jīng)過(guò)43個(gè)系統(tǒng)時(shí)鐘周期就可以完成整個(gè)編碼運(yùn)算。譯碼器在10次迭代時(shí)只需約2500個(gè)時(shí)鐘周期即可完成從數(shù)據(jù)輸入到譯碼輸出的計(jì)算。最終實(shí)現(xiàn)的編譯碼器在相同激勵(lì)作用下運(yùn)算結(jié)果與Matlab仿真計(jì)算結(jié)果一致,該編譯碼器設(shè)計(jì)正確可行。5基于資源消耗和折中的實(shí)現(xiàn)方案多進(jìn)制LDPC編碼器采用直接編碼算法,利用查表法實(shí)現(xiàn)伽羅華域乘法運(yùn)算,原理簡(jiǎn)單易于實(shí)現(xiàn)。譯碼器雖然采用目前計(jì)算復(fù)雜度最小的TMM算法,但在硬件實(shí)現(xiàn)過(guò)程中資源消耗仍較大,尤其是隨著進(jìn)制的增加,每個(gè)節(jié)點(diǎn)對(duì)應(yīng)