ハミング符号とは？

ハミング符号の意味

データビットに複数の検査ビットを規則的に配置し、複数の検査式の成否の組合せから誤りビットの位置を特定する誤り訂正符号。一般に1ビット誤り訂正・2ビット誤り検出（SEC-DED）ができる。

ハミング符号の具体例

検査式c0・c1・c2がすべて不成立で、その結果が2進数の「011」＝3を指すなら、3ビット目が誤っていると判断して反転させる。ECCメモリで使われる。

ハミング符号は試験でどう引っ掛けられる？

「訂正」できるのは1ビット、「検出」できるのは2ビットまで、という非対称を取り違えやすい。

ハミング符号と関連する用語

• パリティチェック
• CRC

ハミング符号が出た過去問

• メモリの誤り制御方式で、2ビットの誤り検出機能と、1ビットの誤り訂正機能をもたせるのに用いられるものはどれか。

  正解：ハミング符号

  要点：ハミング符号は1ビット訂正・2ビット検出（SEC-DED）

  ハミング符号は、データビットに複数の検査ビット（冗長ビット）を付加し、誤りの位置を特定できるようにした誤り訂正符号である。一般にSEC-DED（拡張ハミング符号）として用いられ、1ビットの誤りは訂正でき、2ビットの誤りは訂正はできないが検出できる。このためメモリのECC（誤り訂正符号）として広く使われている。

  出典：平成30年度 秋期 高度共通_午前I試験 am1 問5（IPA）

• ハミング符号とは、データに冗長ビットを付加して、1ビットの誤りを訂正できるようにしたものである。ここでは、X1、X2、X3、X4の4ビットから成るデータに、3ビ…

  正解：0110011

  要点：不成立の検査式すべてに共通するビットが誤りビット

  符号1110011は左からX1=1, X2=1, X3=1, P3=0, X4=0, P2=1, P1=1である。三つの検査式を計算すると、X1⊕X3⊕X4⊕P1＝1、X1⊕X2⊕X4⊕P2＝1、X1⊕X2⊕X3⊕P3＝1となり、いずれも0にならない。三つすべての式に共通して現れるのはX1だけなので、誤っているのはX1である。X1を0に訂正すると0110011となり、三つの式がすべて0になることが確かめられる。

  出典：平成30年度 春期 高度共通_午前I試験 am1 問1（IPA）

• 符号長7ビット、情報ビット数4ビットのハミング符号による誤り訂正の方法を、次のとおりとする。 受信した7ビットの符号語 x1 x2 x3 x4 x5 x6 x7…

  正解：1010101

  要点：c0・c1・c2からi＝3を求め3ビット目を反転する

  受信語1000101をx1〜x7とすると、c0＝x1+x3+x5+x7＝1+0+1+1＝1、c1＝x2+x3+x6+x7＝0+0+0+1＝1、c2＝x4+x5+x6+x7＝0+1+0+1＝0（いずれもmod 2）。i＝1+1×2+0×4＝3となるので、左から3ビット目を反転する。1000101の3ビット目0を1にして1010101が得られる。

  出典：令和6年度 春期 高度共通_午前I試験 am1 問2（IPA）