おしょうしな日記 Thanks 101

科学・技術をわかりやすい言葉で解説。「おしょうしな」とは、山形おきたま弁で「ありがとう」の意味。

広告

※このエリアは、60日間投稿が無い場合に表示されます。記事を投稿すると、表示されなくなります。

ハミング符号の原理(1)

2008-12-20 11:59:56 | 科学・技術
 コンピュータの主記憶装置として、DRAMなどの半導体メモリが使用されており、記憶されたデータのエラーを訂正する誤り訂正符号として、ハミング符号(ハミングコード)が用いられています。
 このハミング符号の原理を難しい数式を使わず、小中学生でも理解できるように簡単に説明します。

【表1:検査ビット生成表(パリティ生成テーブル)】

    (1**) (*1*) (**1)
a 011     a   a
b 101 b       b
c 110 c   c
d 111 d   d   d
--------------------------
    p1   p2   p3

上記の表は、半導体メモリなどの記憶装置に情報ビット(a,b,c,d)からなるデータを書き込むときに、
情報ビット a をアドレス011番地に書き込み、情報ビット b をアドレス101番地に書き込み、
情報ビット c をアドレス110番地に書き込み、情報ビット d をアドレス111番地に書き込む際の、ハミング符号(ハミングコード)の作成方法を示します。

(1**) は、最上位ビット(一番左の桁)が 1 であるアドレスを意味します。
(*1*)は、中間のビット(真ん中の桁)が 1 であるアドレスです。
(**1)は、最下位ビット(一番右の桁)が 1 であるアドレスです。
なお、* は任意の数字です。2進数なので 0、1 の両方を示します。

(1**) に該当するアドレス 101、110、110番地に記憶される情報ビットは b,c,d なので、この b,c,d に基づいて検査ビット(チェックビット) p1 を作ります。

(*1*) に該当するアドレス 011、110、111番地に記憶される情報ビット a,c,d に基づいて検査ビット p2 をつくります。

(**1) に該当するアドレス 011、101、111番地に記憶される情報ビット a,b,d に基づいて検査ビット p3 をつくります。

◆具体的なデータの符号化方法(書き込み時の動作)

例えば、情報ビット(a,b,c,d)=(1101)からなるデータを記憶するときは、次のように検査ビットをつけることとします。

まず(1**) の列に注目し、情報ビット b,c,d に含まれる 1 の数を数えます。
b,c,d を足して奇数なら p1 を 1 とし、偶数なら p1 を 0 とします。
言い換えると、b,c,d,p1 中の 1 の数の合計が偶数となるようにします。これを偶数パリティと言います。

(a,b,c,d)=(1101)では、b,c,d のうちで 1 は b,d の 2 個なので、p1 は 0 です。

(*1*)の列では、データ a,c,d のうちで、1 は a,d の 2 個なので、p2 は 0 です。
(**1)の列では、データ a,b,d の 3 つが 1 なので、p3 を 1 とします。

以上の説明を、数式で書くと、次のようになります。

a=1 b=1 c=0 d=1

p1 = b+c+d = 1+0+1 = 0
p2 = a+c+d = 1+0+1 = 0
p3 = a+b+d = 1+1+1 = 1

p1,p2,p3 は、1 の数が奇数か偶数かを検査しているので、奇偶検査ビット(パリティビット)と言います。

この計算で求めた検査ビット p1,p2,p3 をそれぞれメモリのアドレス 100、010、001番地に記憶します。

p1 100
p2 010
p3 001

情報ビット(a,b,c,d)=(1101)には、検査ビットがつけられ、
記憶されるデータは(a,b,c,d, p1,p2,p3)=(1101 001) となって、メモリに格納されます。

このようにして格納したデータの誤り訂正(エラー訂正)の方法は、以下のとおりです。

◆復号化方法(読み出し時の動作)
何らかのノイズの影響で、1ビットだけデータが反転し、誤って読み出されたとします。

例えば、(a,b,c,d, p1,p2,p3)=(1001 001) が読み出されたとします。
この読み出しデータ中の情報ビット(a,b,c,d)=(1001)に基づいて、先ほどと同様にして、検査ビット p1,p2,p3 を計算します(再計算します。)。

 a=1 b=0 c=0 d=1

p1 = b+c+d = 0+0+1 = 1
p2 = a+c+d = 1+0+1 = 0
p3 = a+b+d = 1+0+1 = 0

この再計算された検査ビット(p1,p2,p3)=(100) は、読み出された検査ビット(p1,p2,p3)=(001) と異なるため、どこかのビットが誤っていることになります。

読み出した検査ビット(p1,p2,p3)=(001)
再計算した検査ビット(p1,p2,p3)=(100)

ここで、上記2つの検査ビットを各桁ごとに比較して、異なったら 1 、同じだったら 0 とします。
比較すると、真ん中のビットは同じなので 0 、最上位ビットと最下位ビットは異なるので 1 とします。
よって

 (p1,p2,p3)=(001)
+ (p1,p2,p3)=(100)
-------------------
  (s1,s2,s3)=(101)

となり、アドレス 101番地から読み出した情報ビット b が間違っていることがわかります。

よって、
(a,b,c,d, p1,p2,p3)=(1001 001)のうち、情報ビット b を反転させて、
(a,b,c,d, p1,p2,p3)=(1101 001)とデータを訂正することができます。

ここでは、データ中の情報ビットのエラー訂正を例に説明しましたが、検査ビットのエラーも同様の方法で訂正することができます。
検査ビット自体のエラー訂正が可能な点が、ハミング符号の特徴の一つです。

以上が簡単なハミング符号の原理です。
------------------------------
★おまけ:

情報ビットは、通信分野においては、通報ビットとも言います。
検査ビットは、チェックビット、パリティビット、奇偶検査ビット、冗長ビットなどとも言われます。

上記の記号 + は、排他的論理和(エクスクルッシブOR)です。記号は EXOR、EOR、XOR などとも書かれます。

(s1,s2,s3)=(101)は、読出しデータの誤っているアドレスを示しており、シンドロームと言います。

【表2:シンドローム生成テーブル(誤り位置の生成表)】

      (1**) (*1*) (**1)
a  011      a   a
b  101  b       b
c  110  c   c
d  111  d   d   d
p1 100  p1
p2 010     p2
p3 001         p3
--------------------------
      s1   s2   s3 (←書込み時は、0 0 0 になっている。)

最計算された検査ビットと、読み出された検査ビットとの比較によってシンドロームを求める方法を説明しましたが、
シンドロームの計算は、この表2の(a,b,c,d, p1,p2,p3)に読出しデータ(1001 001)を代入し、(s1,s2,s3)を直接求めることができます。

 a=1 b=0 c=0 d=1 p1=0 p2=0 p3=1

s1 = b+c+d+p1 = 0+0+1+0 = 1
s2 = a+c+d+p2 = 1+0+1+0 = 0
s3 = a+b+d+p3 = 1+0+1+1 = 1

シンドローム(s1,s2,s3)=(0,0,0)なら誤りなし(エラーなし)です。
それ以外の場合は、シンドロームは、エラーが生じたデータビット(情報ビット又は検査ビット)のアドレスを示します。

試しに、(a,b,c,d, p1,p2,p3)=(0000 000) を記憶させ、このデータの1ビット誤りのデータを上記のシンドローム生成テーブル(表2)に入力してみれば、シンドロームがエラーとなったデータ(情報ビット、検査ビット)の位置(アドレス)を示すことは一目瞭然です。

以上をまとめると、
ハミング符号の原理(2)

ハミング符号の原理(3)
ハミング符号の原理(4) -拡大ハミング符号-
ハミング符号の原理(5) -グレイ・ハミング符号-
ハミング符号の原理(6) -巡回ハミング符号-






コメント   この記事についてブログを書く
« そば、うどんは霞が関に限る... | トップ | あずきかぼちゃ »
最新の画像もっと見る

コメントを投稿

科学・技術」カテゴリの最新記事