低密度奇偶檢查碼

**低密度奇偶檢查碼**（Low-density parity-check code，LDPC code），是線性分組碼（linear block code）的一種，用於更正傳輸過程中發生錯誤的編碼方式。

## 歷史

在 1962 年，低密度奇偶檢查碼 (LDPC code) 即被羅伯特・加拉格提出，並被證明其錯誤校正能力非常接近理論最大值，香農極限（Shannon Limit）；不過受限於當時技術，低密度奇偶檢查碼並無法實作。最近幾年，低密度奇偶檢查碼被重新發現，並隨著積體電路的技術演進，低密度奇偶檢查碼的實作逐漸可行，而成為各種先進通訊系統的信道編碼標準。

## 運作

低密度奇偶檢查碼是基於具有稀疏矩陣性質的奇偶檢驗矩陣建構而成。對 (_n, k_) 的低密度奇偶檢查碼而言，每 _k_ 位元資料會使用 _n_ 位元的碼字 (codeword) 編碼。以下是一個被 (_16, 8_) 的低密度奇偶檢查碼使用的奇偶檢驗矩陣 _H_。當中可以見得矩陣內的元素 1 數量遠少於元素 0 數量，所以具有稀疏矩陣性質，也就是低密度的由來。

$$
H=\left[{\begin{matrix}1&1&1&1&0&0&0&0&0&0\\0&0&0&0&1&1&1&1&0&0\\0&0&0&0&0&0&0&0&1&1\\0&0&0&0&0&0&0&0&0&0\\1&0&0&0&0&0&0&1&0&0\\0&1&0&0&1&0&0&0&0&0\\0&0&1&0&0&1&0&0&1&0\\0&0&0&1&0&0&1&0&0&1\end{matrix}}\quad \!{\begin{matrix}0&0&0&0&0&0\\0&0&0&0&0&0\\1&1&0&0&0&0\\0&0&1&1&1&1\\1&0&0&1&0&0\\0&1&0&0&1&0\\0&0&0&0&0&1\\0&0&1&0&0&0\end{matrix}}\right]
$$

### 解碼

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

 

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

1. 當接收資料 **R** 從通訊頻道 (channel) 進入低密度奇偶檢查碼的解碼器，解碼器會對訊息作初始化 (initialization)。
2. **check node** 根據互相連接的多個 **bit node** 內的資料做更新運算 (update)。
3. **bit node** 對相連接的多個 **check node** 內的資料做更新運算。
4. 觀察終止 (termination) 條件，來決定是否繼續疊代計算。

詳細的解碼演算法，常見有兩種：**總和 - 乘積演算法 (Sum-Product Algorithm)** 和**最小值 - 總和演算法 (Min-Sum Algorithm)**。**總和 - 乘積演算法**具有較佳的錯誤更正能力，卻具較高的計算複雜度；反之，**最小值 - 總和演算法**在稍微減低的錯誤更正能力下，換取較低的計算複雜度。

#### 總和 - 乘積演算法

假設在一通訊系統的頻道有 AWGN 屬性，而傳送訊號為 $\mathbf {U} \left(u_{1},u_{2},\dots ,u_{n}\right)$ ，接收訊號是 $\mathbf {Y} \left(y_{1},y_{2},\dots ,y_{n}\right)$ ，**bit node** 有 _n_ 個，**check node** 有 _m_ 個。而**總和 - 乘積演算法**在解碼流程如下：

* 初始化：假設 AWGN 的方差 (variance) 是 $\sigma ^{2}$ 。
  * **bit node** _n_ 會被初始化成：

 $\lambda _{n\to m}\left(u_{n}\right)=\log {\frac {P(u_{n}=0/y_{n})}{P(u_{n}=1/y_{n})}}={\frac {2y_{n}}{\sigma ^{2}}}$ 。

* * **check node** _m_ 會被初始化成：

 $\Lambda _{m\to n}\left(u_{n}\right)=0$ 。

* **check node** 更新：
  * **check node** _m_ 更新為：

 $\Lambda _{m\to n}\left(u_{n}\right)=2\tanh ^{-1}\left\{\prod _{n'\in N\left(m\right)\backslash n}\tanh \left[{\frac {\lambda _{n'\to m}\left(u_{n'}\right)}{2}}\right]\right\}$ ；
其中 $n'\in N\left(m\right)\backslash n$ 是連接到 **check node** _m_ 的 **bit node** 組合，但不包含第 _n_ 個 **bit node**。

* **bit node** 更新：
  * **bit node** _n_ 更新為：

 $\lambda _{n\to m}\left(u_{n}\right)={\frac {2y_{n}}{\sigma ^{2}}}+\sum _{m'\in M\left(n\right)\backslash m}\Lambda _{m'\to n}\left(u_{n}\right)$ ；其中 $m'\in M\left(n\right)\backslash m$ 是連接到 **bit node** _n_ 的 **check node** 組合，但不包含第 _m_ 個 **check node**。

* 終止：
  * 解碼位元計算：假設解碼後訊號為 ${\hat {\mathbf {U} }}\left({\hat {u}}_{1},{\hat {u}}_{2},\dots ,{\hat {u}}_{n}\right)$ 。**Hard-decision** 解碼位元可由下列兩式求出：

 $\lambda _{n}\left(u_{n}\right)={\frac {2y_{n}}{\sigma ^{2}}}+\sum _{m\in M\left(n\right)}\Lambda _{m\to n}\left(u_{n}\right)$
 ${\hat {u}}_{i}={\begin{cases}0,&{\mbox{if }}\lambda _{i}\left(u_{i}\right)\geq 0~\forall i\in \left\{1,2,\dots ,n\right\}\\1,&{\mbox{if }}\lambda _{i}\left(u_{i}\right)\leq 0~\forall i\in \left\{1,2,\dots ,n\right\}\end{cases}}$

* * 只要解碼後的碼字 $\mathbf {v} $ 在恆等式 $\mathbf {H} \mathbf {v} ^{T}=0$ 成立，即終止疊代計算。

#### 最小值 - 總和演算法

**最小值 - 總和演算**，大抵上和**總和 - 乘積演算法**類似，除了於「**check node** 更新」做不一樣的計算方式。而改變的計算式如下：

 $\sigma _{m}=\mathrm {XOR} \left\{\operatorname {sgn} \left(\lambda _{n'\to m}\right)|n'\in N\left(m\right)\backslash n\right\}$ ，
 $\mu _{m,\min }=\min \left\{|\lambda _{n'\to m}||n'\in N\left(m\right)\backslash n\right\}$ ，
 $\Lambda _{m\to n}\left(u_{n}\right)=\sigma _{m}\cdot \mu _{m,\min }$ 。

## 參考文獻