低密度奇偶檢查碼 （Low-density parity-check code，LDPC code），是線性分組碼 （linear block code）的一種，用於更正傳輸過程中發生錯誤的編碼方式。
编辑
在1962年，低密度奇偶檢查碼(LDPC code)即被羅伯特·加拉格 提出[ 1] 香農極限 。但受限於當時技術，低密度奇偶檢查碼並無法實作。近年，低密度奇偶檢查碼被重新發現[ 2] 積體電路 的技術演進，低密度奇偶檢查碼的實作逐漸可行，而成為各種先進通訊系統 的信道編碼 標準。
编辑
低密度奇偶檢查碼是基於具有稀疏矩陣 性質的奇偶檢驗矩陣 建構而成。對(n, k )的低密度奇偶檢查碼而言，每k 位元資料會使用n 位元的碼字 (codeword)編碼。以下是一個被(16, 8 )的低密度奇偶檢查碼使用的奇偶檢驗矩陣 H 。當中可以見得矩陣 內的元素1數量遠少於元素0數量，所以具有稀疏矩陣 性質，也就是低密度的由來。
H
=
[
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
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
]
{\displaystyle 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)；整個解碼流程如下方所示：
當接收資料R從通訊頻道(channel)進入低密度奇偶檢查碼的解碼器，解碼器會對訊息作初始化(initialization)。
check node根據互相連接的多個bit node內的資料做更新運算(update)。
bit node對相連接的多個check node內的資料做更新運算。
觀察終止(termination)條件，來決定是否繼續疊代計算。 詳細的解碼演算法，常見有兩種：總和-乘積演算法(Sum-Product Algorithm)[ 3] [ 4] [ 5] [ 6]
编辑
假設在一通訊系統的頻道有AWGN 屬性，而傳送訊號為
U
(
u
1
,
u
2
,
…
,
u
n
)
{\displaystyle \mathbf {U} \left(u_{1},u_{2},\dots ,u_{n}\right)}
Y
(
y
1
,
y
2
,
…
,
y
n
)
{\displaystyle \mathbf {Y} \left(y_{1},y_{2},\dots ,y_{n}\right)}
bit node 有n 個，check node 有m 個。而總和-乘積演算法在解碼流程如下：
初始化：假設AWGN的方差(variance)是
σ
2
{\displaystyle \sigma ^{2}}
λ
n
→
m
(
u
n
)
=
log
P
(
u
n
=
0
/
y
n
)
P
(
u
n
=
1
/
y
n
)
=
2
y
n
σ
2
{\displaystyle \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}}}}
Λ
m
→
n
(
u
n
)
=
0
{\displaystyle \Lambda _{m\to n}\left(u_{n}\right)=0}
Λ
m
→
n
(
u
n
)
=
2
tanh
−
1
{
∏
n
′
∈
N
(
m
)
∖
n
tanh
[
λ
n
′
→
m
(
u
n
′
)
2
]
}
{\displaystyle \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
′
∈
N
(
m
)
∖
n
{\displaystyle n'\in N\left(m\right)\backslash n}
λ
n
→
m
(
u
n
)
=
2
y
n
σ
2
+
∑
m
′
∈
M
(
n
)
∖
m
Λ
m
′
→
n
(
u
n
)
{\displaystyle \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
′
∈
M
(
n
)
∖
m
{\displaystyle m'\in M\left(n\right)\backslash m}
終止：
解碼位元計算：假設解碼後訊號為
U
^
(
u
^
1
,
u
^
2
,
…
,
u
^
n
)
{\displaystyle {\hat {\mathbf {U} }}\left({\hat {u}}_{1},{\hat {u}}_{2},\dots ,{\hat {u}}_{n}\right)}
λ
n
(
u
n
)
=
2
y
n
σ
2
+
∑
m
∈
M
(
n
)
Λ
m
→
n
(
u
n
)
{\displaystyle \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)}
u
^
i
=
{
0
,
if
λ
i
(
u
i
)
≥
0
∀
i
∈
{
1
,
2
,
…
,
n
}
1
,
if
λ
i
(
u
i
)
≤
0
∀
i
∈
{
1
,
2
,
…
,
n
}
{\displaystyle {\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}}}
只要解碼後的碼字
v
{\displaystyle \mathbf {v} }
H
v
T
=
0
{\displaystyle \mathbf {H} \mathbf {v} ^{T}=0}
编辑
最小值-總和演算，大至和總和-乘積演算法類似，除了於「check node更新」做不一樣的計算方式。而改變的計算式如下：
σ
m
=
X
O
R
{
sgn
(
λ
n
′
→
m
)
|
n
′
∈
N
(
m
)
∖
n
}
{\displaystyle \sigma _{m}=\mathrm {XOR} \left\{\operatorname {sgn} \left(\lambda _{n'\to m}\right)|n'\in N\left(m\right)\backslash n\right\}}
μ
m
,
min
=
min
{
|
λ
n
′
→
m
|
|
n
′
∈
N
(
m
)
∖
n
}
{\displaystyle \mu _{m,\min }=\min \left\{|\lambda _{n'\to m}||n'\in N\left(m\right)\backslash n\right\}}
Λ
m
→
n
(
u
n
)
=
σ
m
⋅
μ
m
,
min
{\displaystyle \Lambda _{m\to n}\left(u_{n}\right)=\sigma _{m}\cdot \mu _{m,\min }}
编辑
^ R. Gallager, “Low-Density Parity-Check Codes,” IRE Trans. Inf. Theory, vol. 7, pp. 21–28, Jan. 1962.
^ David J.C. MacKay and Radford M. Neal, "Near Shannon Limit Performance of Low Density Parity Check Codes," Electronics Letters, July 1996
^ R. M. Tanner, “A Recursive Approach to Low Complexity Codes,” IEEE Trans. Inform. Theory, Vol. IT-27, no. 5, pp. 399–431, Sep. 1981.
^ F. R. Kschischang, B. J. Frey and H. A. Loeliger, “Factor Graphs and the Sum-Product Algorithm,” IEEE Trans. Info. Theory, Vol. 47, pp. 498–519, Feb. 2001.
^ M. P. C. Fossorier, M. Mihaljevic, and H. Imai, “Reduced Complexity Iterative Decoding of Low-density Parity Check Codes Based on Belief Propagation,” IEEE Trans. Commun., vol. 47, no. 5, pp. 673–680, May, 1999.
^ J. Chen, A. Dholakia, E. Eleftheriou, M. P. C. Fossorier, and X. Y. Hu, “Reduced-complexity Decoding of LDPC Codes,” IEEE Trans. Commun., vol. 53, no. 8, pp. 1288–1299, Aug. 2005.
![{\displaystyle 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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88da6407a65fc64efc2cc4ee5edebc253be7b61a)
![{\displaystyle \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\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa1e896866cdfa2543dbe341e15fa724e50e6896)
