はみんぐふごう
1ビットの誤りを訂正できる誤り訂正符号の代表。r個の検査ビットを使い、長さ 2^r − 1 ビットの符号語のうち 2^r − 1 − r ビットをデータに使う。r = 3 のハミング符号(7, 4)では、4ビットのデータに3ビットの検査ビットを付ける。各検査ビットは、重なり合うビットの組のパリティで、受信側で検査をやり直した結果(シンドローム)が、誤ったビットの位置を2進数で示す。最小ハミング距離は3で、全体のパリティを1ビット加えたSECDEDでは、2ビットの誤りの検出もできる。サーバー用のメモリのECCなどに使われる。
「ハミング符号」は、2分野の5問の練習問題に出てきます(情報理論と符号の基礎, 論理回路など)。
この用語の分野: 情報理論と符号の基礎
ビットの位置を1〜7とし、2のべき乗の位置1、2、4を検査ビットにします。検査1は位置の番号を2進数で表したときに1の位が1になる位置(1、3、5、7)、検査2は2の位が1になる位置(2、3、6、7)、検査4は4の位が1になる位置(4、5、6、7)の1の個数を偶数にします。誤った位置の番号の、2進数で1になる桁に当たる検査だけが合わなくなるので、合わない検査の重みを足すと、誤った位置が分かります。
検査ビットがr個なら符号語は 2^r − 1 ビットで、(7, 4)、(15, 11)、(31, 26) のように長くするほど、符号化率は 4/7 ≈ 0.57、11/15 ≈ 0.73、26/31 ≈ 0.84 と高くなります。その代わり、1つの符号語で訂正できるのは1ビットだけなので、長い符号語ほど、2ビット以上の誤りが入る確率が高くなります。
ハミング符号に全体のパリティを1ビット加えると最小ハミング距離が4になり、1ビットの誤りの訂正(SEC)と2ビットの誤りの検出(DED)ができます。64ビットのデータには8ビットの検査ビットが必要で、サーバー用のメモリが72ビット幅になっているのはこのためです。より多くの誤りを扱うフラッシュメモリなどでは、BCH符号やLDPC符号が使われます。
正解：B. 約0.57
符号化率は、符号語の長さnのうち、データのビット数kが占める割合 k/n です。ハミング符号(7, 4)では 4/7 ≈ 0.57 で、送るビットの約57%がデータです。符号化率が低いほど、検査ビットが多く誤りに強くしやすい一方、データを送る効率は下がります。
正解：C. 6ビット目
受信した 0110001 で、1、3、5、7ビット目は0、1、0、1で1の個数は偶数(検査1の結果は0)、2、3、6、7ビット目は1、1、0、1で奇数(検査2の結果は1)、4、5、6、7ビット目は0、0、0、1で奇数(検査4の結果は1)です。検査4、検査2、検査1の結果を並べた 110 を2進数として読むと6なので、6ビット目が誤っています。6ビット目を反転した 0110011 は、3つの検査をすべて満たします。
全体のパリティのないハミング符号では、2ビットの誤りでもシンドロームが0以外のどれかの位置を示すので、正しいビットを反転してしまい、誤りが3ビットに増えます。これを防ぐために、メモリなどでは全体のパリティを加えたSECDEDを使い、2ビットの誤りは訂正せずにエラーとして報告します。
使われています。計算が簡単で速いので、メモリのECCやキャッシュ、レジスタの保護など、遅延を小さくしたい場面で広く使われています。通信のように、多くの誤りを効率よく訂正したい場面では、LDPC符号などのより強力な符号が使われます。
ハミング符号(7, 4)では 4/7 ≈ 0.57 で、送るビットの約57%がデータです。
4ビットのデータに3ビットの検査ビットを付けて7ビットの符号語にする、ハミング符号(7, 4)の符号化率に最も近いもの…r = 5 では 2⁵ = 32 < 32 + 5 + 1 = 38 で足りず、r = 6 では 2⁶ = 64 ≥ 32 + 6 + 1 = 39 なので、ハミング符号の検査ビットは6ビットです。
32ビットのデータに、1ビットの誤りを訂正し、2ビットの誤りを検出できるSECDED符号を付ける。ハミング符号の検査ビ…そのため、連続した5ビット以下のバースト誤りは、並べ戻すと5つの符号語に1ビットずつ以下に分かれ、どれもハミング符号で訂正できます。
ハミング符号(7, 4)の符号語を5つ並べ、各符号語の1ビット目を5つ、次に2ビット目を5つ、という順に送る(深さ5の…訂正まで必要なメモリでは、複数のパリティを組み合わせたECC(ハミング符号など)が使われます。
7ビットのデータ 1011001 に偶数パリティのビットを付けるとき、パリティビットの値はどれか。Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。
パリティビット ECC(誤り訂正符号) 可逆圧縮 クラフトの不等式 情報エントロピー 情報量 接頭符号 前方誤り訂正(FEC) 相互情報量 二元対称通信路