「ハミング符号」の版間の差分
m →復号化 |
m ロボットによる 追加: zh:汉明码 |
||
128行目: | 128行目: | ||
[[tr:Hamming kodu]] |
[[tr:Hamming kodu]] |
||
[[vi:Mã Hamming]] |
[[vi:Mã Hamming]] |
||
[[zh:汉明码]] |
2008年10月14日 (火) 06:30時点における版
ハミング符号(- ふごう)とはデータの誤りを検出・訂正できる線型誤り訂正符号のひとつ。
概要
1950年にベル研究所のリチャード・ハミングによって考案された。知られている誤り訂正符号の中では最も古く、ブロックあたり1ビットの誤りを訂正できる。リード・ソロモン符号などに比べると、ある程度高速で処理できるが、訂正力は高くない。このためエラー発生率が低く、速度が要求される用途に使う。ECCメモリやRAID 2などに使用される。身近なところではWinRARのリカバリレコードに使用されている。
基本概念
一般にハミング符号は、ある整数 m に対し、
- 符号長 :
- 情報数 :
で構成される。ここで情報数とは元のデータのビット数、符号長とは生成される符号のビット数である。 m = 3 の場合は n = 7、k = 4 となり、4ビットのビット列を7ビットの符号語に置き換えるハミング符号が形成される、この場合を(7,4)ハミング符号という。
ハミング符号は検査行列と生成行列と呼ばれる二つの行列を用いて処理が行われる。まず検査行列について述べる。この行列は m行 n列の行列で、全ての列要素がゼロではなく、かつ相違であるという条件がある。 (7,4)ハミング符号の検査行列 H の一例を以下に示す。
検査行列 H の条件は上記に記したように全ての列が相違であり、なおかつ 0 しかない列が存在しないことである。H の列の数は nであるので、Hの各列には 0 以外の全てのビットパターンが存在することになる。列の順番は任意であるが特に
- H = [ A Im ]
の形で表される行列の場合を組織符号という、ここで A は任意の行列、 Imは m × m の単位行列である。ハミング符号に於いては組織符号の理論上の重要性は持たないが後述する生成行列の計算が容易になるのと、符号の装置化が簡略になるので良く用いられる。なお上記の例での H も組織符号である。
次に生成行列について述べる。生成行列 G とは以下の条件を満たす非零の行列である。
- HGT = GHT = 0
ここで、GTは G の転置行列を表す。組織符号の場合、G は以下の形で表される。
- G = [ Ik AT ]
上記の例で示した H に対する G は以下のようになる。
符号化
符号化では生成行列 G と送信したいデータ m1 ... mk との乗算を行う。 なお各行列計算で用いられる加算は全て排他的論理和であることに注意する。 先ほどの例で取り上げた G を生成行列として、ビット列 1 0 1 1 を符号化する場合を考える。このとき生成される符号は
となり、1 0 1 1 1 0 0 が生成された符号である。
復号化
復号化は検査行列 H と受信したデータの積を求めることで行われる。今、受信データ Y を受け取ったとする。このとき Y に誤りが存在しない場合は
であるといえる。ここで x とは符号化される前のビット列である。この Y と H の転置行列との積を求めると H と G の関係式より
と求められる。すなわち受信語と検査行列の積が零ベクトルであるなら誤りが無いことになり、非零であるなら誤りを含むことになる。次に Y が 1 ビットの誤りを含むとする、ここで Y を以下のように仮定する。
ここで ei とは i番目のビットが 1、それ以外のビットが 0 のビット列である。このような eiのことを誤りベクトルという。先ほどと同様に Y と H の転置行列との積を求めると以下のようになる。
ここでei は i番目のビットのみ 1 であるので、すなわち H の i番目の列が出力されることになる。よってこの出力が Hの何列目と一致するかを比べることにより誤りの位置が検出され、その部分のビットを反転することで誤りを訂正できる。
例として上記の符号語が送信され、1 1 1 1 1 0 0 が受信されたとする。この受信データは 1 1 1 1 1 0 0 に誤りを含む、このデータを復号化する。受信データと H の転置行列の積を求めると以下のようになる。
この出力を転置すると、Hの2列目と同じ値であることがわかる。よって誤りは 2列目であり、2 列目のビットを反転させると 1 0 1 1 1 0 0となり、元の符号語に訂正されたことがわかる。
拡張ハミング符号
ハミング符号に符号語全体のパリティビットを付加したものを拡張ハミング符号という。 これにより通常のハミング符号の 1ビットの誤り訂正と同時に、2ビットまでの誤りの検出ができる。 上記の例のハミング符号で生成される符号語の末尾にパリティビットを付加した場合は検査行列は次のようになる。
関連項目
参考文献
- J.ユステセン、T.ホーホルト、『誤り訂正符号入門』、阪田省二郎、栗原正純、松井 一、藤沢 匡哉 訳、森北出版、2005年、ISBN 4-627-81711-8
- 今井秀樹、『符号理論』、コロナ社、1990年、ISBN 4-88552-090-8
- 情報理論とその応用学会編、『符号理論とその応用』、倍風館、2003年、ISBN 4-563-01453-2