[科普中國]-低密度同位元檢查累積碼

低密度同位元檢查累積碼由低密度奇偶檢查碼（low-density parity-check，LDPC)和一個累加器組成。其運作方式為Bit Node以二位元模組的方式相加到Check Nodes，根據(jù)tanner graph。 然后，Check nodes的值以modulo-two被累加。 利用這種方式，通道解碼端的解碼器可以避免有一個check node沒有被連結(jié)到任何bit node的狀況。 經(jīng)過累加后，累加的位元會被存在一個緩沖器中，再逐漸傳送到解碼器。

簡介低密度同位元檢查累積碼是一種信道編碼方法，低密度同位元檢查累積碼有三個階段。第一個階段是一個可逆線性轉(zhuǎn)換矩陣，其中有資料來源序列。 第二個階段是一個一個rate的累加器，可以轉(zhuǎn)換長度為L的序列。第三個階段是變更或置換這個序列。 這個序列接下來會傳送到解碼器，總共需要傳送的碼數(shù)量由解碼器的回饋決定。低密度同位元檢查累積碼可以應用在許多編解碼應用的系統(tǒng)當中。

低密度奇偶檢查碼低密度奇偶檢查碼（Low-density parity-check code，LDPC code），是線性分組碼（linear block code）的一種，用于更正傳輸過程中發(fā)生錯誤的編碼方式。在1962年，低密度奇偶檢查碼(LDPC code)即被Gallager提出，并被證明其錯誤校正能力非常接近理論最大值，香農(nóng)極限(Shannon Limit)；不過受限于當時技術(shù)，低密度奇偶檢查碼并無法實現(xiàn)。低密度奇偶檢查碼被重新發(fā)現(xiàn)，并隨著集成電路的技術(shù)演進，低密度奇偶檢查碼的實現(xiàn)逐漸可行，而成為各種先進通信系統(tǒng)的頻道編碼標準。

低密度奇偶檢查碼是基于具有稀疏矩陣性質(zhì)的奇偶檢驗矩陣建構(gòu)而成。對(n, k)的低密度奇偶檢查碼而言，每k比特數(shù)據(jù)會使用n比特的碼字(codeword)編碼。以下是一個被(16, 8)的低密度奇偶檢查碼使用的奇偶檢驗矩陣H。當中可以見得矩陣內(nèi)的元素1數(shù)量遠少于元素0數(shù)量，所以具有稀疏矩陣性質(zhì)，也就是低密度的由來。

低密度奇偶檢查碼的解碼，可對應成二分圖(bipartite graph)作表示。下方的二分圖是依照上述奇偶檢驗矩陣H建置，其中H的行(column)對應至check node，而H的列(row)對應至bit node。check node和bit node之間的連接，由H內(nèi)的元素1決定；好比H中第一行(column)和第一列(row)的元素1，使check node和bitnode兩者各自最左手邊的第一個彼此連接。

低密度奇偶檢查碼的解碼算法，主要基于有迭代性(iterative)的置信傳播(belief propagation)；整個解碼流程如下方所示：

當接收數(shù)據(jù)R從通信頻道(channel)進入低密度奇偶檢查碼的解碼器，解碼器會對消息作初始化(initialization)。

check node根據(jù)互相連接的多個bit node內(nèi)的數(shù)據(jù)做更新運算(update)。

bit node對相連接的多個check node內(nèi)的數(shù)據(jù)做更新運算。

觀察終止(termination)條件，來決定是否繼續(xù)迭代計算。

累加器在中央處理器中，累加器 (accumulator) 是一種寄存器，用來儲存計算產(chǎn)生的中間結(jié)果（在運算器中，形成和存放運算 結(jié)果的寄存器）1；或指可以存儲一數(shù)并接受另一數(shù)，將兩者相 加后存儲其總和的設(shè)備稱累加器。累加器還 具有移位、讀出信號、清除、求補等功能。

如果沒有像累加器這樣的寄存器，那么在每次計算 (加法，乘法，移位等等) 后就必須要把結(jié)果寫回到 內(nèi)存，也許馬上就得讀回來。然而存取主存的速度是比從算術(shù)邏輯單元到有直接路徑的累加器存取更慢。標準的例子就是把一列的數(shù)字加起來。一開始累加器設(shè)定為零，每個數(shù)字依序地被加到累加器中，當所有的數(shù)字都被加入后，結(jié)果才寫回到主存中。

信道編碼一種為了提高通信系統(tǒng)可靠性而對傳輸信號進行的編碼。即使所傳輸信號內(nèi)部具有更強的規(guī)律性和相關(guān)性，以使信號受干擾而損傷時仍能正確恢復原有信息的處理過程。即為了適應信道條件(如頻帶寬度限制、波段、功率、通信時間等)和滿足通信的要求(如可靠性、有效性等)，需要對所傳輸?shù)男盘栠M行的某種變換。信道編碼的理論基礎(chǔ)是信息論中的信道編碼定理，它從理論上解決理想編碼器的存在性問題。信道編碼的具體方法屬于差錯控制技術(shù)。

能檢出和糾正傳輸中產(chǎn)生錯誤的編碼。用于檢錯的碼叫檢錯碼；用于檢錯與糾錯相結(jié)合的碼稱為“糾錯碼”。按糾錯類型可分糾隨機錯誤碼、糾突發(fā)錯誤碼，糾字節(jié)(byte)錯誤碼和糾運算錯誤的算術(shù)運算碼等。按構(gòu)造可分分組碼和樹碼。分組碼是將M個符號序列分別映射成長度為n的碼字。如該映射規(guī)律滿足線性關(guān)系，則稱為“線性碼”，否則稱為“非線性碼”。樹碼具有樹形結(jié)構(gòu)，可用樹形圖描述。狀態(tài)有限的樹圖可簡并成格狀圖，稱為格狀碼。由分組碼和樹碼級連的碼稱為“級連碼”，它具有更強的糾錯性能并更易于實現(xiàn)。糾錯碼的糾錯能力和有效的譯碼算法是研究信道編碼的焦點。Turbo碼和低密度奇偶校驗(LDPC)碼是兩種性能逼近仙農(nóng)限的最令人矚目的糾錯碼。信道編碼已在各類數(shù)字通信系統(tǒng)中得到廣泛應用。其發(fā)展趨勢是調(diào)制與糾錯相結(jié)合，信道編碼與信源編碼相結(jié)合等。

本詞條內(nèi)容貢獻者為:

王慧維 - 副研究員 - 西南大學