-
低密度奇偶檢查碼
鎖定
低密度奇偶檢查碼（Low-density parity-check code，LDPC code），是線性分組碼（linear block code）的一種，用於更正傳輸過程中發生錯誤的編碼方式。
- 中文名
- 低密度奇偶檢查碼
- 外文名
- Low-density parity-check code
- 縮 寫
- LDPC code
低密度奇偶檢查碼歷史
在1962年，低密度奇偶檢查碼(LDPC code)即被Gallager提出，並被證明其錯誤校正能力非常接近理論最大值，香農極限(Shannon Limit)；不過受限於當時技術，低密度奇偶檢查碼並無法實現。低密度奇偶檢查碼被重新發現，並隨着集成電路的技術演進，低密度奇偶檢查碼的實現逐漸可行，而成為各種先進通信系統的頻道編碼標準。
[1]
低密度奇偶檢查碼運作
低密度奇偶檢查碼是基於具有稀疏矩陣性質的奇偶檢驗矩陣建構而成。對(n, k)的低密度奇偶檢查碼而言，每k比特數據會使用n比特的碼字(codeword)編碼。以下是一個被(16, 8)的低密度奇偶檢查碼使用的奇偶檢驗矩陣H。當中可以見得矩陣內的元素1數量遠少於元素0數量，所以具有稀疏矩陣性質，也就是低密度的由來。
低密度奇偶檢查碼解碼
低密度奇偶檢查碼的解碼，可對應成二分圖(bipartite graph)作表示。下方的二分圖是依照上述奇偶檢驗矩陣H建置，其中H的行(column)對應至check node，而H的列(row)對應至bit node。check node和bit node之間的連接，由H內的元素1決定；好比H中第一行(column)和第一列(row)的元素1，使check node和bit node兩者各自最左手邊的第一個彼此連接。
低密度奇偶檢查碼的解碼算法，主要基於有迭代性(iterative)的置信傳播(belief propagation)；整個解碼流程如下方所示：
- 當接收數據R從通信頻道(channel)進入低密度奇偶檢查碼的解碼器，解碼器會對消息作初始化(initialization)。
- check node根據互相連接的多個bit node內的數據做更新運算(update)。
- bit node對相連接的多個check node內的數據做更新運算。
- 觀察終止(termination)條件，來決定是否繼續迭代計算。
詳細的解碼算法，常見有兩種：總和-乘積算法(Sum-Product Algorithm)和最小值-總和算法(Min-Sum Algorithm)。總和-乘積算法具有較佳的錯誤更正能力，卻具較高的計算複雜度；反之，最小值-總和算法在稍微減低的錯誤更正能力下，換取較低的計算複雜度。
低密度奇偶檢查碼總和-乘積算法
bit noden會被初始化成：
check nodem會被初始化成：
check node更新：
check nodem更新為：
bit node更新：
bit noden更新為：
終止：
解碼比特計算：假設解碼後信號為
。Hard-decision解碼比特可由下列兩式求出：
只要解碼後的碼字
在恆等式
成立，即終止迭代計算。
最小值-總和算法[編輯]
最小值-總和演算，大抵上和總和-乘積算法類似，除了於“check node更新”做不一樣的計算方式。而改變的計算式如下：
