ハミング符号とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > デジタル大辞泉 > ハミング符号の意味・解説 

ハミング‐ふごう〔‐フガウ〕【ハミング符号】


ハミングコード

別名:ハミング符号
【英】Hamming code

ハミングコードとは、誤り訂正符号一つで、本来のデータ冗長な検査ビットとして付加したのである1950年発表された。

ハミングコードにより、1ビット誤りであれば検出訂正ができ、2ビット誤りであれば検出ができる。ハミングコードは、検査ビット数をnとすると、2n - 1のビット数を持つ。すなわち、本来のデータビット数は2n - 1 - nである。

4ビットデータd0d3)に対する3ビットのハミングコード(p0、p1p2)の求め方次の通りである。p0 = d0 xor d1 xor d3p1 = d0 xor d2 xor d3p2 = d1 xor d2 xor d3

ハミングコードは、高速で高い信頼性求められる用途にはあまり向かず、ECCメモリのような処理速度要求される比較エラー起きにくい場面で使われる

ちなみにハミングコードの名称は、情報工学者リチャード・ハミングRichard Hamming)の名にちなんでいる。

ネットワーク接続のほかの用語一覧
接続方式:  ハートビート  ハーフデュプレックス  半二重  ハミングコード  バーストモード  ペイロード  非同期

ハミング符号

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/03/25 08:13 UTC 版)

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

概要

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となり、元の符号語に訂正されたことがわかる。

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

拡張ハミング符号

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

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

となる。この時 eiej であるため、上記の式は検査行列の任意の2つの列の値排他的論理和が出力される。検査行列の定義より列の値は全て相違となるので 2ビット誤りの時も検査行列との積が零ベクトルになることはない。ただし、別の検査行列の値と一致するため誤訂正を起こすことになる。

すなわち単純なハミング符号で誤り検出のみを行うと 2ビットの誤りまで検出できる。しかし、1ビット誤り(訂正可能)か 2ビット誤り(訂正不可能)であるかを判断する術がないため、この二つの機能を同時に実装することができない。そこでハミング符号に符号語全体のパリティビットを付加することで 1ビットの誤り訂正と同時に、2ビットまでの誤りの検出を行うことが可能になる(SECDED("single error correction, double error detection"))。これを拡張ハミング符号という。

符号の生成は単純なハミング符号で生成された符号語の全ビットの排他的論理和を符号語の末尾に追加する。符号化、復号の例で使用した 1 0 1 1 1 0 0 の場合、パリティビットは 0 なので末尾に 0 を加えた 1 0 1 1 1 0 0 0 になる。復号には、以下のような検査行列を用いる。

この行列は、先ほどまで使用した検査行列に、新たに全て 0の列を一番右側に加え、全て 1 の行を一番下に加えたものである。

誤り訂正の方法は、通常のハミング符号と同様である。この時 1ビット誤りなら検査行列のいずれかの列と同じ値になるが、2ビット誤りの場合は検査行列の列の値に含まれない値を出力する。これにより 1ビットの誤り訂正と2ビットの誤りの検出が同時に行える。

参考文献

  • Hamming, R. W. (1950). "Error detecting and error correcting codes". Bell System Tech. J. 29: pp. 147-160.PDF.
  • J.ユステセン、T.ホーホルト、『誤り訂正符号入門』、阪田省二郎、栗原正純、松井 一、藤沢 匡哉 訳、森北出版、2005年、ISBN 4-627-81711-8
  • 今井秀樹、『符号理論』、コロナ社、1990年、ISBN 4-88552-090-8
  • 情報理論とその応用学会編、『符号理論とその応用』、培風館、2003年、ISBN 4-563-01453-2

関連項目


ハミング符号

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/12/21 09:57 UTC 版)

巡回符号」の記事における「ハミング符号」の解説

ハミング符号は必ずしも巡回符号ではないが、ある種のハミング符号は巡回符号の定義を満たすことが知られている。この符号のことを特に 巡回ハミング符号 と呼ぶ。巡回ハミング符号の生成行列生成多項式表した場合、 G(x) は m次の原始多項式であることが知られている。

※この「ハミング符号」の解説は、「巡回符号」の解説の一部です。
「ハミング符号」を含む「巡回符号」の記事については、「巡回符号」の概要を参照ください。

ウィキペディア小見出し辞書の「ハミング符号」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「ハミング符号」の関連用語

ハミング符号のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



ハミング符号のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
デジタル大辞泉デジタル大辞泉
(C)Shogakukan Inc.
株式会社 小学館
IT用語辞典バイナリIT用語辞典バイナリ
Copyright © 2005-2025 Weblio 辞書 IT用語辞典バイナリさくいん。 この記事は、IT用語辞典バイナリの【ハミングコード】の記事を利用しております。
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのハミング符号 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの巡回符号 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS