前のページ 1/2 次のページ

ハミング符号(- ふごう)とはデータの誤りを検出・訂正できる線型誤り訂正符号のひとつ。

◆ 概要

1950年にベル研究所のリチャード・ハミングによって考案された。知られている誤り訂正符号の中では最も古く、ブロックあたり1ビットの誤りを訂正できる。リード・ソロモン符号などに比べると、ある程度高速で処理できるが、訂正力は高くない。このためエラー発生率が低く、速度が要求される用途に使う。ECCメモリやRAID 2などに使用される。また、WinRARのリカバリレコードにも使用されている。

◆ 基本概念

一般にハミング符号は、ある整数 m に対し、

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

: 情報数 :$k\; =\; n\; -\; m$

で構成される。ここで情報数とは元のデータのビット数、符号長とは生成される符号のビット数である。

m = 3 の場合は n = 7、k = 4 となり、4ビットのビット列を7ビットの符号語に置き換えるハミング符号が形成される、この場合を(7,4)ハミング符号という。

ハミング符号は検査行列と生成行列と呼ばれる二つの行列を用いて処理が行われる。なお各行列計算で用いられる加算は全て排他的論理和であることに注意する。まず検査行列について述べる。この行列は m行 n列の行列で、全ての列要素がゼロではなく、かつ相違であるという条件がある。

(7,4)ハミング符号の検査行列 H の一例を以下に示す。

: $H\; =$

\begin

1 & 0 & 1 & 1 & 1 & 0 & 0 \\

1 & 1 & 0 & 1 & 0 & 1 & 0 \\

0 & 1 & 1 & 1 & 0 & 0 & 1 \\

\end

検査行列 H の条件は上記に記したように全ての列が相違であり、なおかつ 0 しかない列が存在しないことである。H の列の数は nであるので、Hの各列には 0 以外の全てのビットパターンが存在することになる。列の順番は任意であるが特に

: H = [外部リンク] I_m

の形で表される行列の場合を組織符号という、ここで A は任意の行列、 I_mは m × m の単位行列である。ハミング符号に於いては組織符号の理論上の重要性は持たないが後述する生成行列の計算が容易になるのと、符号の装置化が簡略になるので良く用いられる。なお上記の例での H も組織符号である。

次に生成行列について述べる。生成行列 G とは以下の条件を満たす非零の行列である。

: HG^T = GH^T = 0

ここで、G^Tは G の転置行列を表す。組織符号の場合、G は以下の形で表される。

: G = [外部リンク] A^T

上記の例で示した H に対する G は以下のようになる。

: $G\; =$

\begin

1 & 0 & 0 & 0 & 1 & 1 & 0 \\

0 & 1 & 0 & 0 & 0 & 1 & 1 \\

0 & 0 & 1 & 0 & 1 & 0 & 1 \\

0 & 0 & 0 & 1 & 1 & 1 & 1 \\

\end

◇ 符号化

符号化では生成行列 G と送信したいデータ m₁ ... m_k との乗算を行う。

先ほどの例で取り上げた G を生成行列として、ビット列 1 0 1 1 を符号化する場合を考える。このとき生成される符号は

: $$

\begin

1 & 0 & 1 & 1 \\

\end

\cdot

\begin

1 & 0 & 0 & 0 & 1 & 1 & 0 \\

0 & 1 & 0 & 0 & 0 & 1 & 1 \\

0 & 0 & 1 & 0 & 1 & 0 & 1 \\

0 & 0 & 0 & 1 & 1 & 1 & 1 \\

\end

= \begin

1 & 0 & 1 & 1 & 1 & 0 & 0 \\

\end

となり、1 0 1 1 1 0 0 が生成された符号である。

◇ 誤り訂正と復号

復号は検査行列 H と受信したデータの積を求めることで行われる。今、受信データ Y を受け取ったとする。このとき Y に誤りが存在しない場合は

:$Y\; =\; x\; \backslash cdot\; G$

であるといえる。ここで x とは符号化される前のビット列である。この Y と H の転置行列との積を求めると H と G の関係式より

:$Y\; \backslash cdot\; H^T\; =\; x\; \backslash cdot\; (G\; \backslash cdot\; H^T)\; =\; 0$

と求められる。すなわち受信語と検査行列の積が零ベクトルであるなら誤りが無いことになり、非零であるなら誤りを含むことになる。次に Y が 1 ビットの誤りを含むとする、ここで Y を以下のように仮定する。

:$Y\; =\; x\; \backslash cdot\; G\; \backslash oplus\; e\_i$

ここで e_i とは i番目のビットが 1、それ以外のビットが 0 のビット列である。このような e_iのことを誤りベクトルという。先ほどと同様に Y と H の転置行列との積を求めると以下のようになる。

:$Y\; \backslash cdot\; H^T\; =\; (x\; \backslash cdot\; G\; \backslash oplus\; e\_i)\; \backslash cdot\; H^T\; =\; x\; \backslash cdot\; (G\; \backslash cdot\; H^T)\; \backslash oplus\; e\_i\; \backslash cdot\; H^T\; =\; e\_i\; \backslash cdot\; H^T$

ここでe_i は i番目のビットのみ 1 であるので、すなわち H の i番目の列が出力されることになる。よってこの出力が Hの何列目と一致するかを比べることにより誤りの位置が検出され、その部分のビットを反転することで誤りを訂正できる。

例として上記の符号語が送信され、1 1 1 1 1 0 0 が受信されたとする。この受信データは 1 1 1 1 1 0 0 に誤りを含む、このデータを復号する。受信データと H の転置行列の積を求めると以下のようになる。

: $\backslash begin$

1 & 1 & 1 & 1 & 1 & 0 & 0 \\

\end

\cdot

\begin

1 & 0 & 1 & 1 & 1 & 0 & 0 \\

1 & 1 & 0 & 1 & 0 & 1 & 0 \\

0 & 1 & 1 & 1 & 0 & 0 & 1 \\

\end^ =

\begin

0 & 1 & 1 \\

\end

この出力を転置すると、Hの2列目と同じ値であることがわかる。よって誤りは 2列目であり、2 列目のビットを反転させると 1 0 1 1 1 0 0となり、元の符号語に訂正されたことがわかる。

訂正後、符号語からもとの情報を取り出す。これは生成行列内に単位行列の列成分となる部分がある場合、その箇所と同位置の符号語のビットは元の情報のビットがそのまま出力されているので、これを取り出すことで元の情報が得られる。組織符号の場合は生成行列の前部分が単位行列と一致するので、単に符号語の前 k ビットを取り出すだけである。

◇ 拡張ハミング符号

(7,3)ハミング符号の場合に符号語に2ビットの誤りが含まれている場合を考えてみる。この時位置 i と jに誤りが含まれているとすると

:$Y\; =\; x\; \backslash cdot\; G\; \backslash oplus\; e\_i\; \backslash oplus\; e\_j$

となり、検査行列との積を取ると

前のページ 1/2 次のページ

・ハミング符号 page1

・ハミング符号 page2