ハミング符号

垂直水平パリティ符号より効率的に冗長ビットを作り出す方法

ブロックの長さと追加する符号の長さによって誤り検出能力は異なる。

情報ビット=4ビット，符号ビット=3ビットの場合1ビットの誤り検知、1ビットの誤り訂正ができる

$ (7,4) ハミング符号という

$ (n,k) 符号、$ n : 符号総長、$ k : 情報ビット長、情報記号数

一般のハミング符号

符号長$ n の組織符号(systematic code)$ \bm{w}

$ \bm{w} = x_1x_2...x_k c_1 c_2 ... c_{n-k}

これを$ (n,k) 符号と呼ぶ。

符号長$ n

情報記号数$ 𝑘

$ x_1x_2...x_k は情報ビット

$ c_1 c_2 ... c_{n-k} は検査ビット

符号長$ n : $ n = 2^m -1

情報記号数$ k : $ n = n - m = 2^m -1 -m

冗長ビット長$ n-k : $ n - k = m

シンドローム長$ m

$ y_i = w_i + e_i

受信語$ y をパリティ検査方程式の左辺に代入した結果$ s＝ y_1 ＋ y_2 ＋・・・＋ y_n

問題

https://gyazo.com/79a3b013bbe50222856d1b7f40b021aa

ハミング符号は$ X_1X_2X_3P_3X_4P_2P_1

問題文にあるのは多分パリティ検査方程式。

$ X_1 \oplus \quad \quad X_3 \oplus X_4 \oplus P_1 = 0

$ X_1 \oplus X_2 \oplus \quad \quad X_4 \oplus P_2 = 0

$ X_1 \oplus X_2 \oplus X_3 \quad \quad \oplus P_3 = 0

パリティ検査方程式から係数行列(パリティ検査行列)$ \bm{H} を取る。

$ \bm{H} = \begin{pmatrix} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1\end{pmatrix}

$ \bm{H} : パリティ検査行列

$ \bm{H}^T = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\\ 0 & 1 & 0 \\ 1 & 0 & 0\end{pmatrix}

$ \bm{H}^T : $ \bm{H} の転置行列

問題文の受信語1110011をパリティ検査方程式に入れると、シンドローム$ \bm{s} が出てくる。

$ \bm{s} =(s_1, s_2, s_3) = (1, 1, 1)

確認用

Q. 垂直水平パリティ符号