ハミング符号とは、線型誤り訂正符号のひとつで、1bitのデータ誤りの検出・修正ができます。 ハミング符号は誤り訂正符号だけではなく、McEliece暗号などのショアのアルゴリズムを用いた攻撃で破ることができない耐量子暗号にも少し関係するので、おさらいもかねて勉強したのでここに備忘録とします。
線形符号
$(n,k)$ 線形符号とは、2進数の $n$ 次のベクトル空間 $(\mathbb{Z}_2)^n$ での部分空間のことです。 線形符号には以下の性質があります。
- 符号語同士を足すと、別の符号語になる： $\vec{w}_1 + \vec{w}_2 = \vec{w}_3$
- 全ての要素が $0$ の符号語が存在する： $\vec{0} = (0,0,…,0,0)$
なお、$(n,k)$ 符号に対する生成行列は $k \times n$ の2進数行列です。
ハミング符号
ハミング符号では、情報列にパリティ列を付加したものが符号語になります。 そして、情報列 $\vec{i}$ から符号語 $\vec{w}$ に変換するための行列を「生成行列」と呼びます。 $(7,4)$ ハミング符号の生成行列 $G$ は例えば次のようなものがあります。
\[G = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{pmatrix}\]情報列から符号語に変換する処理は、行列の掛け算で求まります。 なお、情報列は長さが $k=4$ のベクトルで、例えば $\vec{i} = (1,0,1,1)$ が情報列となります。
\[\vec{i} G = \vec{w}\]次に、受信した符号語に誤りが含まれているかを検出して訂正する方法についてです。 ただし、ここで扱うものは単一誤り検出・修正しかできませんのでご承知おきください。 まず、受信した符号語が $\vec{w}^\prime$ だとします。 ここに誤りがあるか調べるには「パリティ検査行列」と行列の掛け算をします。 パリティ検査行列 $H$ は、$HG^\mathsf{T} = GH^\mathsf{T} = O$ (ゼロ行列) を満たす行列で、今回の例だと次のような行列になります。
\[H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{pmatrix}\]受信した符号語 $\vec{w}^\prime$ とパリティ検査行列 $H$ の掛け算をし、その結果がゼロベクトルになる場合は、受信した符号語に誤りはないことがわかります。なお、$H{\vec{w}^\prime}^\mathsf{T}$ の値をシンドロームといいます。
\[H{\vec{w}^\prime}^\mathsf{T} = \vec{0}\]もし、パリティ検査行列との掛け算の結果がゼロベクトルではない場合、誤りが含まれていることがわかります。 例えば、計算した結果が以下のようになったとすると、このベクトルはパリティ検査行列 $H$ の3列目と一致するので、誤りが3bit目にあることがわかります。
\[H{\vec{w}^\prime}^\mathsf{T} = \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}\]誤りの訂正は、2進数なので対象ビットを 0 から 1 または 1 から 0 に変えるだけで修正できます。
$(7,4)$ ハミング符号をプログラム (SageMath) で計算する例を以下に示します。
G = matrix(GF(2), [
[1,0,0,0,0,1,1],
[0,1,0,0,1,0,1],
[0,0,1,0,1,1,0],
[0,0,0,1,1,1,1]
])
H = matrix(GF(2), [
[0,0,0,1,1,1,1],
[0,1,1,0,0,1,1],
[1,0,1,0,1,0,1]
])
info = vector(GF(2), [1,0,1,1])
word = info * G
# 受信した符号語にノイズなし
recv1 = word
syndrome1 = H * recv1
print(syndrome1)
# => (0, 0, 0)
# 受信した符号語にノイズあり (3bit目)
recv2 = word + vector(GF(2), [0,0,1,0,0,0,0])
syndrome2 = H * recv2
print(syndrome2)
# => (0, 1, 1)
補足：
符号語が $(i_1, i_2, i_3, i_4, p_1, p_2, p_3)$ のように情報ビット $i_k$ と検査ビット $p_k$ の位置が明確に区別されている符号を「組織符号」といいます。 組織符号にすることで生成行列の計算を容易にすることができるメリットがあります。
以上です。
参考文献
- ハミング符号 - Wikipedia
- 『誤り訂正符号入門』森北出版, 第2版, 2019