非規則LDPC碼解碼改進算法及其DSP實現

2020-12-05 電子產品世界

為了降低非規則低密度奇偶校驗(low-densityparity-check,LDPC)碼解碼算法的複雜度，提出一種適合數位訊號處理囂(digital signal processor，DSP)實現的低運算複雜度、低誤碼平臺解碼的改進算法。

本文引用地址：http://www.eepw.com.cn/article/148209.htm

該算法校驗節點的運算採用修正最小和算法，外信息的更新採用串行方式，既保持了串行和積算法在有限迭代次數下解碼門限低的優點，又降低了節點運算複雜度和誤碼平臺。用定點DSP晶片實現的非規則LDPC碼解碼器的實測結果表明，該算法能以較低的實現複雜度獲得低的誤碼平臺和解碼門限。

低密度奇偶校驗(low-density paruty-check，LDPC)碼是一種非常有效的信道編碼方案，已經成為新一代數字衛星廣播(DVB-S2)等標準的信道編碼方案，具有重要的應用價值。

LDPC碼解碼器設計的實現成為近年來研究的熱點。LDPC碼解碼器的實現方法主要有2種：一種是基於超大規模集成電路(VLSI)的設計;另外一種是基於數位訊號處理器(digital signalprocessor，DSP)等指令串行執行系統的實現。

LDPC碼解碼多採用和積(sum-product，SP)解碼算法，影響其複雜度的因素有迭代次數和每次迭代的運算複雜度。由於DSP晶片指令串行執行的特點，要實現較高速率的LDPC碼解碼器，必須同時減少迭代解碼次數和每次迭代的運算量。文提出一種逐個校驗節點串行更新的迭代解碼算法(S-SP)，並說明在二進位對稱信道(BSC)下可以有效降低迭代解碼的次數;為降低每次迭代的運算複雜度，校驗節點的運算存在一些簡化的解碼算法，如修正最小和算法(modified mim-sum，MMS)等，但這些算法的解碼門限有一定的損失。

本文研究非規則LDPC碼的S-SP算法在加性高斯白噪聲(AWGN)信道下的性能，說明該算法雖能降低迭代次數，但是存在誤碼平臺較高的問題。考慮到簡化的解碼算法(例如MMS算法)有複雜度和誤碼平臺低的特點，本文綜合這2類算法的特點，提出了串行MMS(S-MMS)算法，該算法在有限迭代次數下具有低的誤碼平臺和較低的解碼門限，實現了複雜度和性能的較好折衷，適合於用DSP實現。

1 LDPC碼簡介和迭代解碼算法

1.1 LDPC碼簡介

LDPC碼是一種分組碼。其校驗矩陣為超稀疏隨機矩陣，設為H。對於任何一個合法的碼字v，都有校驗方程。由該方程可知，校驗矩陣中每行的非零元素，將所對應的LDPC碼元映射成一個相當於校驗碼的約束，定義這種約束關係為一個校驗節點。校驗矩陣中每列的非零元素對應LDPC碼的同一個碼元，形成了一個相當於重複碼的約束，定義這種約束關係為一個變量節點，而矩陣中的非零元素，既參與了變量節點的重複碼的約束關係，又參與了校驗節點的校驗碼的約束關係;因此定義矩陣中非零元素所對應的關係為連結這2種節點的「連結線」。因此，LDPC碼的結構也可以用圖1的因子圖表示。

LDPC碼的編碼，先利用校驗矩陣得到對應的生成矩陣，然後直接用信息序列和生成矩陣相乘即可得到編碼碼字，而LDPC碼的解碼則利用校驗節點和變量節點的約束關係，在2類節點間通過「連結線」進行外信息的傳遞，從而實現迭代解碼。

1.2 LDPC碼迭代解碼算法

定義為變量節點n的先驗信息，即對數似然比;表示第k次迭代中，從校驗節點m到變量節點n的外信息;表示第k次迭代中，從變量節點n到校驗節點m的外信息;為第k次迭代後變量節點n的後驗信息;M(n)表示和變量節點n相連的校驗節點的集合;N(m)表示和校驗節點m相連的變量節點的集合。

標準的和積(SP)解碼算法如下。

步驟l 初始化。

其中：xn為發送比特;yn為接收符號。採用二進位相移鍵控(BPSK)調製，信道為AWGN信道。

步驟2迭代解碼。

迭代解碼包括2個步驟，變量節點的計算和校驗節點的計算。本文中設定固定的迭代次數K，然後判決輸出。

1)變量節點的運算(對所有的變量節點n)。

2)校驗節點的運算(對所有的校驗節點m)。

其中k≥1.

步驟3後驗信息計算和判決輸出。

串行和積解碼算法(S-SP)，在計算校驗節點m時，需要將上面和積(SP)算法中的步驟2變量節點的運算修改為

其k≥1，假設校驗節點的計算從1開始，也即m依次取1，2，3，…，M，這裡M為校驗節點的個數，如圖1所示。

S-SP算法和SP算法的不同點在於：在SP算法中，所有與校驗節點m相鄰的變量節點更新時所使用的校驗節點外信息都來自上一次的迭代輸出，然後進行校驗節點m的運算。而在S-SP算法中，計算校驗節點m時，和其相連變量節點的更新可以使用本次迭代中已經更新過的外信息。從上面的分析也可看出，S-SP算法的複雜度和SP算法相同，另外，可通過合理設計，使得該算法需要的存儲資源可降低為原來的1/2。

2 改進的迭代解碼算法和優化設計

文指出，在BSC信道下，S-SP算法可以有效降低迭代解碼次數。本文研究了該算法在AWGN信道下的特點，發現該算法雖可以降低迭代解碼次數，但是存在誤碼平臺較高的缺點。後面將利用仿真結果說明這一特點。

本文將S-SP算法與修正最小和算法(MMS)結合，提出了改進算法，將外信息的更新採用串行更新策略，校驗節點的計算採用修正最小和算法，稱為串行修正最小和算法(S-MMS)。該算法解決了S-SP算法的誤碼平臺較高的問題，解碼門限和標準的SP算法相比，性能損失很小。

提出的串行修正最小和算法(S-MMS)，其迭代解碼步驟2修改如下。

設定固定的迭代次數K，對校驗節點m，依次取1，2，3，…，M，進行下面的2個步驟。

1)變量節點的運算(只計算和校驗節點m相連的變量節點)。

其中：r=│N(m)│表示集合N(m)中的元素個數，即非規則碼的校驗節點m的階數;βr為非規則碼不同階校驗節點的偏移因子;sgn()為符號函數。

最優的偏移因子βr值，可以採用密度演化或者計算機仿真的方法得到。

本算法變量節點的運算只包括求和運算，校驗節點只包括最大、最小和減法操作，與SP算法的校驗節點運算的非線性函數ln(tanh())相比，量化噪聲對其影響小。本文針對定點DSP晶片特點，信道觀測值和迭代解碼中的外信息，都採用16 b的量化精度，有利於優化指令並行度，並可以降低存儲器讀取、存儲延時。

相關焦點

  • LDPC 碼解碼算法及性能分析應用設計
    Mack-ay 和Neal利用隨機構造的Tanner 圖研究了LDPC 碼的性能，發現採用和積算法(SPA)的LDPC 碼具有優異的解碼性能，在長碼時甚至超過了Turbo 碼[2].本文採用Mackay 基於二分圖提出的改進方案構造LDPC 碼的校驗矩陣。基於置信傳播(BP)算法，給出了一種簡化的BP算法--對數域迭代APP LLR 算法，複雜度大大降低。
  • WIMAX LDPC碼解碼器的FPGA實現
    採用一種工作於增量模式的基於填充算法的桶形移位寄存器結構，實現了對該標準中576、768、1152、2304 4種碼長LDPC 碼解碼的支持。結果表明所設計的解碼器完全能滿足WIMAX標準對數據吞吐率的要求。
  • 基於FPGA的極化碼的SCL解碼算法研究
    極化碼被嚴格證明有以下兩個特性：一是基於信道極化現象存在；二是在碼長為無限長時，其信道容量可達香農極限。相比於經典的Turbo碼與LDPC碼，極化碼具有更低的誤碼率和複雜度以及更高的吞吐率［2-3］。 極化碼的解碼算法研究近年來發展迅速，其中成為研究熱點的連續刪除（Successive Cancellation，SC）解碼算法的基本思想是通過對信息位的比特似然概率值的判斷來進行解碼。
  • 使用準循環LDPC碼的OFDM系統性能分析
    特別是Mackay等重新發現最初由Gallager提出的低密度校驗碼(LDPC)，它在採用長的分塊長度的時候，與Turbo碼有極其相似的性能。但與Turbo碼相比，一方面，LDPC碼的解碼極其簡單；另一方面，良好設計的LDPC碼可以具有簡單的編碼器實現結構，在較低的誤碼率下不存在誤碼平臺。
  • 多碼率QC-LDPC解碼器設計與實現
    提出了一種通用的多碼率QC-LDPC 解碼器設計方法，並在FPGA 上完成了實現和測試。測試結果表明，該多碼率解碼器在資源佔用不超過2 種碼率解碼器資源之和的前提下能夠有效支持至少3 種碼率；且工作時鐘在110 MHZ 時，固定迭代次數為16 次，該解碼器的吞吐率能保持在110 Mb/s 以上。
  • 基於CMMB系統的LDPC解碼器的設計與實現
    摘要：根據CMMB中LDPC碼校驗矩陣的結構特點，提出了一種部分並行解碼結構的實現方法，並在XILINX的VirtexIV的XC4VLX80型FPGA上實現了這種結構。
  • LDPC(低密度奇偶校驗碼)
    （Low Density Parity Check Code，LDPC），它是由Robert G.Gallager博士於1963年提出的一類具有稀疏校驗矩陣的線性分組碼，不僅有逼近Shannon限的良好性能，而且解碼複雜度較低、結構靈活，是近年信道編碼領域的研究熱點，目前已廣泛應用於深空通信、光纖通信、衛星數字視頻和音頻廣播等領域。
  • 基於IEEE802.1 6e標準的LDPC編碼器設計與實現
    摘要 根據IEEE802．16e標準中對LDPC碼的定義，利用FPGA對編碼器進行了實現。所採用的算法使用了線性複雜度編碼，降低了邏輯資源佔用量，並提高了編碼速度。關鍵詞 IEEE 802．16e標準；低密度奇偶校驗碼；編碼器 1962年Gallager在對糾錯編碼的研究中提出了LDPC碼，但是由於當時的硬體條件不足，直到90年代末隨著超大規模集成電路的推廣才真正為人們所重視。
  • 詳談Turbo碼特點及應用分析
    MAP算法是1974年被用於卷積碼的解碼，但用作Turbo碼的解碼還是要做一些修改;Max-Log-MAP與Log-MAP是根據MAP算法在運算量上做了重大改進，雖然性能有些下降，但使得Turbo碼的解碼複雜度大大的降低了，更加適合於實際系統的運用;Viterbi算法並不適合Turbo碼的解碼，原因就是沒有每比特譯出的可靠性信息輸出，修改後的具有軟信息輸出的SOVA算法，就正好適合了Turbo碼的解碼
  • LDPC碼的設計以及在無線傳感器網絡中的應用
    討論了在無線傳感器網絡中LDPC碼的設計和實際應用，並提供了解決方案，以降低解碼複雜度，節省內存佔用量，提高了系統的誤碼率性能。結果表明，短碼長的LDPC碼可以在無線傳感器網絡節點上應用並能獲得較為理想的性能，具有很好的應用前景。
  • 基於DSP和FPGA的機器人聲控系統設計與實現
    2 系統硬體總體設計 系統的硬體功能是實現語音指令的採集和步進電機的驅動控制，為系統軟體提供開發和調試平臺。如圖1所示。 系統硬體分為語音信號的採集和播放，基於dsp的語音識別，fpga動作指令控制、步進電機及其驅動、dsp外接快閃記憶體晶片，jtag口仿真調試和鍵盤控制幾個部分。
  • 基於改進的CORDIC算法的FFT復乘及其FPGA實現
    在FFT運算中，核心操作是蝶形運算，而蝶形運算的主要操作是向量旋轉，實現向量旋轉可用複數乘法運算來實現，但複數乘耗費了FFT運算中大量的乘法器資源。CORDIC算法只需簡單的移位與加減運算就能實現向量旋轉，具有使用資源少、硬體規模小等優勢。因此在FFT蝶形運算中用其代替傳統FFT運算中的複數乘法器，可以獲得更好的性能。
  • 第六講 DSP在雷達信號處理中的應用
    dsp可以利用硬體算術單元、片內存儲器、哈佛總線結構、專用尋址單元、流水處理技術等特有的硬體結構，高速完成fft、fir、複數乘加、相關、三角函數以及矩陣運算等數位訊號處理。因此，dsp非常適合雷達數位訊號處理算法的實現。 fft是雷達信號處理的重要工具。
  • 基於DSP的數字掃描探針顯微鏡的硬體解決方案研究
    技術也已經廣泛地應用於通信、測量、多媒體、消費電子產品等領域，由於把dsp和spm結合在一起是spm儀器發展的必然方向，它能使spm性能更趨於完善，為此，本文介紹如何用tms320c5416來實現這一設想！
  • 基於DSP Builder的JPEG靜態圖像壓縮算法的實現
    因此，用FPGA實現數位訊號處理可以很好地解決並行性和速度問題，而且其靈活的可配置特性，使得以FPGA為核心器件的DSP系統易於修改、測試及硬體升級。採用這種方法實現了硬體級的仿真驗證。1 DSP Builder介紹 DSP Builder開發工具是Altera公司提供的數位訊號處理平臺,它是一個系統級(或算法級)設計工具,架構在多個軟體工具之上，並把系統級和RTL級兩個設計領域的設計工具連接起來，最大程度地發揮了兩種工具的優勢。
  • 增量調製編碼解碼實驗
    圖2.1   ΔM編解碼系統框圖（一）單片ΔM編解碼器1、MC3418簡介MC3418是MOTOLOLA公司生產的通信專用集成電路，它是數字檢測音節壓擴增量編解碼器。是由模擬輸入放大器、數字輸入運算放大器、電壓/電流轉換運算放大器、極性開關、工作選擇開關和數字檢測（移位寄存器和邏輯電路）等部分構成的。
  • 基於小波變換與DSP的實時音頻視頻處理系統
    本文介紹一種基於adv611，ct8021晶片同時結合ti公司的tms320c6201晶片實現音/視頻實時處理系統。在該實時系統中，dsp晶片作為控制核心、一方面要管理adv611，ct8021，存儲器和通信接口，另一方面要對adv611的圖像壓縮效果進行調解，對數據速率實時控制。系統實現方案原理圖如圖1所示。
  • QR碼印刷質量檢測系統
    運用圖像預處理及模板匹配算法對QR碼進行缺陷識別，實現對QR碼印刷品中出現的QR碼圖片漏印、誤印、印刷位置偏移、黑白拉線等印刷問題的自動識別，從而解決了人工檢測所帶來的問題。0 引言　　隨著物聯網與自動化識別技術的迅速發展，QR碼具有超高速識讀、數據隱蔽性、可很好地處理中國漢字和日文等優點。
  • 基於DSP的語音識別系統的實現及分析
    系統前端採用MFCC特徵參數、並用遺傳算法（GA）與矢量量化（VQ）混合算法對其進行聚類得到優化碼本，然後將所得碼本作為 SVM 模式訓練和識別算法的輸入，按照相應的準則最終得到識別的結果。語音識別系統流程圖如圖2所示。
  • 分組碼和卷積碼的區別 詳解分組碼和卷積碼
    本文主要是關於分組碼和卷積碼的相關介紹，並著重闡述了分組碼和卷積碼不同特性。 卷積碼 卷積碼是1955年由Elias等人提出的，是一種非常有前途的編碼方法。我們在一些資料上可以找到關於分組碼的一些介紹，分組碼的實現是將編碼信息分組單獨進行編碼，因此無論是在編碼還是解碼的過程中不同碼組之間的碼元無關。