10．通信路符号化手法2 （誤り検出と誤り訂正符号） 1 • 誤り検出符号 – パリティ検査符号 • 誤り訂正符号 – 垂直水平パリティ符号 – ハミング符号 2 誤り検出符号（パリティ検査符号） 3 通信路符号と冗長性ここからは、通信路符号化において、主に２元符号を考察していく。通信路アルファベットを B  {0,1} とする。（定義）情報ビットと検査ビット通信路符号語は、情報源符号語に加えて意識的に冗長部分を付加して構成される。情報を表す記号列を情報部分といい、冗長性を表す記号列を冗長部分という。特に、２元符号の場合、情報部分を情報ビット、冗長部分を検査ビットという。 4 通信路符号の数学的表現情報ビット冗長ビット w  (w1, w2 , , wn )  ( x1, , xk , p1, , pnk ) nビット kビット nkビット  ( x, p) （通信路）符号語＝情報部分＋冗長部分ただし、 x  ( x1, x2 , , xk ) p  ( p1, p2 , , pnk )  1  i  k , wi  xi  B  {0,1}  k  1  i  n, wi  pi k  B  {0,1} 5 パリティ（遇奇性）（定義）パリティ n 符号語 w  w1 , , wn  B に対して、次式が成り立つとき、偶数パリティを持つという。  w1  w2    wn  0  n    wi (mod 2)  0   i 1  また、次式が成り立つとき、奇数パリティを持つという。 w1  w2   wn  1  n    wi (mod 2)  1  i 1  6 例次の符号が偶数パリティを持つか、奇数パリティを持つかを判定せよ。 w  (w1 , , wn )  (0,0,1,1,0,1,0,1)  00110101 w mod2  4 i (mod2)  0 よって、偶数パリティを持つ。これ以降では、  mod2 略記法符号に現れる１の個数が偶数を省略することもある。 7 練習次の式を計算せよ。（１） 1 0 11 0 11 （２） 11 0  0  0 11 （３） 1 0 1 0  0 1 0 （４） 3  4  7  5  8  9 1(mod2) （５） 9  3  6  4  8  7  5 (mod2) （６） 5  4  3  8  6  9  2 (mod2) 8 練習次の符号が偶数パリティを持つか、奇数パリティを持つかを判定せよ。（１） (1,1,1,0,1,1,0,1) （２） (0,1,0,1,1,0,1,1) （３） (0,0,0,1,1,0,1,1) （４） 10111000 11001100 （６） 01001100 （５） 9 パリティ検査（符号）まず、１番単純な通信路符号としてパリティ検査について考える。パリティ検査は１誤り検出符号になっている。パリティ検査符号は以下の符号語の形式になる。 w  ( x1, x2 , , xn1 , p ) n1ビット情報ビット１ビット冗長ピットこれらに関係する概念を順にみていく。 10 パリティ検査（符号）の定義（定義）パリティ検査（符号）１ビットの検査ビット（パリティビット） p  B を持ち、偶数パリティだけを符号語とするような符号を（偶数）パリティ検査符号と n1 いう。情報ビットを x  ( x1 , , xn1 )  B とすると次式が成り立つ。 w  ( x1 , , xn1 , p)  B x1   xn1  p  0  p  x1   xn1 n 偶数パリティ検査では、情報ビットが偶数パリティを持てばパリティビットは０で、奇数パリティを持てばパリティビットは１。 11 例次の情報源符号語から、偶数パリティ検査符号を構成せよ。（１） x1  ( x , , x )  (1,0,1,1,1,0,0)  1011100 p1   x11  mod2  4 (mod2)  0 1 1 1 7 よって、以下のように通信路符号語が得られる。 w1  ( x , , x , p )  (1,0,1,1,1,0,0,0)  (1011100,0)  10111000 略記法 1 1 （２） 1 7 1 x2  ( x12 , , x72 )  (0,1,1,1,1,0,1)  0111101 p   x  mod2  5 (mod2)  1 2 2 1 よって、以下のように通信路符号語が得られる。 w2  ( x12 , , x72 , p2 )  (0,1,1,1,1,0,1,1)  (0111101,1) 12  01111011 練習以下のような情報源記号が与えられているとき、偶数パリティ検査符号を求めよ。（１）（２）（３）（４）（５）（６） x1  (1,1,1,0,1,1,0) x2  (0,1,0,1,1,0,1) x3  (0,0,0,1,1,0,1) x4  1011100 x5  1100110 x6  0100110 13 偶数パリティ符号における符号語 HC(1) 0 HC(2) 00 01 HC(3) 001 000 011 010 1 ：符号語 10 11 101 100 111 110 14 HC(4) 0010 0000 1010 0110 1000 1100 0100 0011 0111 1110 1011 1111 0001 0101 1001 1101 ：符号語 15 練習情報ビットが４ビット x  B で、パリティビットが１ビット p  B 5 の偶数パリティ符号 w  B を考える。この符号語になりえるハイパーキューブ HC(5) 上頂点を図示せよ。 4 16 パリティ検査符号の誤り検出原理性質：パリティ検査符号語間のハミング距離偶数パリティ検査符号において、各符号語 i, j, i  j, wi , wj W のハミング距離で以下が成り立つ。 W dh (wi , w j )  2( s 1) s  1 証明各符号語 wi , w j W は全て偶数パリティを持つので、ハミング距離が dh (wi , w j )  1 となることは無い。また、異なる符号語では、 dh (wi , w j )  0 となることも無い。 QED 17 パリティ検査符号の情報伝送速度 n 1 情報ビットがで、検査ビットが１ビットのビットのパリティ検査符号 n w  ( x1, x2 , , xn1 , p ) n1ビットの情報速度 RP １ビットは次式で表わされる。 n 1 RP  [bit / 記号] n 情報速度＝情報ビット長符号長 18 誤り訂正符号 19 代表的誤り訂正符号垂直水平パリティ符号パリティ検査符号の拡張による誤り訂正符号ハミング符号誤りベクトルの考察による誤り訂正符号 20 垂直水平パリティ符号 21 垂直水平パリティ符号 1ビット誤り検出可能な符号であるパリティ検査符号の考え方を拡張し、１ビット誤り訂正可能な符号を構成できる。まず、情報ビット４ビット、冗長ビット５ビットからの９ビットの垂直水平パリティ符号の構成法を示す。 w  (w1, w2 , , w9 )  ( x1, x2 , x3 , x4 , p1, p2 , p3 , p4 , p5 )  ( x, p) 22 情報ビット列に関する冗長ビット x11 x12 r1 x21 x22 r2 c1 c2 p 行に関する冗長ビット全体の冗長ビット w  ( x11, x12 , x21, x22 , r1, r2 , c1, c2 , p) ただし、冗長ビットは次式で定める。 r1  x11  x12 r2  x21  x22 c1  x11  x21 c2  x12  x22 p  r1  r2  c1  c2  x11  x12  x21  x22 23 垂直水平パリティ符号における誤り訂正の原理 i j 列の誤り検出行の誤り検出誤っている (i, j ) 要素を特定→１ビット誤り訂正 24 垂直水平パリティ符号における誤り訂正能力２ビット誤りを検出可能であるが、丸と四角のどちらの組が誤りかはを判定できない。２ビット誤りを検出可能である。行は特定できるが、どの列がは特定不能。２ビット誤りを検出可能である。列は特定できるが、どの行かは特定不能。 25 一般的な垂直水平パリティ符号 c r r c r 1 c 1 一般に、情報ビットが r  c であるとき、符号ビットを (r  1)  (c 1) として構成できる。したがって冗長ビットは r  c 1 である。 26 例 w  ( x11, x12 , x21, x22 , r1, r2 , c1, c2 , p) の垂直水平パリティ符号を考える。このとき、次の情報ビットから垂直水平符号を求めよ。 x  0101  x11x12 x21x22  r1  x11  x12  0 1  1, r2  x21  x22  0 1  1, c1  x11  x21  0  0  0, r2  x12  x22  11  0, s  x11  x12  x21  x22  0 w  (0,1,0,1,1,1,0,0,0) 27 練習 w  ( x11, x12 , x21, x22 , r1, r2 , c1, c2 , p) の垂直水平パリティ符号を考える。このとき、次の情報ビットから垂直水平パリティ符号を求めよ。（１）（２）（３） x１  0001 x2  1001 x3  1101 （４） x4  1110 28 誤り訂正例 w  ( x11, x12 , x21, x22 , r1, r2 , c1, c2 , p) の垂直水平パリティ符号を考える。このとき、次の符号から誤りを訂正せよ。 y  w  e  000111000 0 0 1 0 1 1 0 0 0 パリティの検査から、 x21 が誤っていることが判明する。行ベクトル毎、列ベクトル毎にパリティ検査を行い、誤りっている行と列の交差している箇所が誤りである。誤りベクトルと、正しい符号は以下である。 e  010000000 w  y  e  010111000 29 練習 w  ( x11, x12 , x21, x22 , r1, r2 , c1, c2 , p) の垂直水平パリティ符号を考える。このとき、このとき、次の符号から誤りを訂正せよ。（１）（２）（３）（４） y1  100101011 y2  111101101 y3  100110110 y4  111001010 30 垂直水平パリティ符号の符号語間距離 w  ( x11, x12 , x21, x22 , r1, r2 , c1, c2 , p) で定義される垂直水平パリティ符号のの各符号語間の距離において、次式がなりたつ。 i, j, i  j dh (wi , w j )  3 wi   xi , pi  w j   x j , p j  dh ( xi , x j )  1 dh ( xi , x j )  2 において、のとき、行と列の検査１ビットづつ異なる。のとき、少なくとも行と列のどちらかが、 31 検査ビットが２か所異なる。垂直水平パリティ符号の情報速度 w  ( x11, x12 , x21, x22 , r1, r2 , c1, c2 , p) で定義される２×２の情報ビットを持つ垂直水平パリティ符号の情報速度 RVHP (2  2) は、次式で表わされる。 4 RVHP (2  2)  [bit / 記号] 9 より一般に、 r  c の情報ビットを持つ垂直水平パリティ符号の情報速度 RVHP (r  c) は、次式で表らわされる。 rc RVHP (r  c)  [bit / 記号] (r 1)(c 1) 32 ハミング符号 33 ハミング符号垂直水平パリティ符号より効率的に冗長ビットを作り出す方法が知られている。まず、情報ビット４ビット、冗長ビット３ビットからの７ビットのハミング符号の構成法を示す。（これを（７，４）ハミング符号という。） w  (w1, w2 , , w7 )  ( x1, x2 , x3 , x4 , p1, p2 , p3 )  ( x, p) (7,4) ハミング符号という。 (n, k ) 符号 n : 符号総長 k : 情報ビット長 34 （７，４）ハミング符号 w  (w1, w2 , , w7 )  ( x1, x2 , x3 , x4 , p1, p2 , p3 )  ( x, p) 冗長ビットを次の規則で定める。 p1  x1  x2  x3 (mod 2) での演算。 (mod 2) は省略する。 p2  x2  x3  x4 p3  x1  x2  x4 35 検査方程式 w  (w1, w2 , , w7 )  ( x1, x2 , x3 , x4 , p1, p2 , p3 ) に対して、冗長ビットの決め方から次の関係式が成り立つ。  w1  w2  w3  w5  0 ( x1  x2  x3  p1  0)  w2  w3  w4  w6  0 ( x2  x3  x4  p2  0)  w  w  w  w  0 ( x  x  x  p  0) 4 7 1 2 4 3  1 2 この関係式を検査方程式という。誤りが混入しなければ、検査方程式を満足するはずである。 36 シンドローム検査方程式から、誤りの位置を特定するための情報を抽出することができる。受信語が y  ( y1, y2 , , y7 ) であるとき、受信語から次式で定義される３ビット s1s2 s3 をシンドロームという。  s1  y1  y2  y3  y5  s2  y2  y3  y4  y6 s  y  y  y  y  3 1 2 4 7 受信語の誤り位置を診断するための情報検査方程式の右辺で、送信記号 wi を受信記号 yi に置き換える。 37 誤りベクトルとシンドローム  s1  y1  y2  y3  y5 通信路により誤りの混入  s2  y2  y3  y4  y6 s  y  y  y  y  3 1 2 4 7  s1   w1  e1    w2  e2    w3  e3    w5  e5    s2   w2  e2    w3  e3    w4  e4    w6  e6   s  w  e   w  e   w  e   w  e  1 1 2 2 4 4 7 7  1  s1  e1  e2  e3  e5   s2  e2  e3  e4  e6 s  e  e  e  e  3 1 2 4 7 検査方程式より 38 ハミング符号の誤り訂正原理７ビットからなる符号には、１ビット誤りベクトルは７個しかない。正しい場合を含めて８通りを区別できれば良い。 e1 e2 e3 e4 e5 e6 e7 s1 s2 s3 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 各列がシンドロームの定義式に対応する。 s3  e1  e2  e4  e7  p3  x1  x2  x4 各行の誤りベクトルに２進数を割り当てる。 39 例 w  ( x1, x2 , x3 , x4 , p1, p2 , p、3 ) 次のように冗長ビットを定める（７，４）ハミング符号を考える。 p1  x1  x2  x3 p2  x2  x3  x4 p3  x1  x2  x4 このとき、次の情報ビットに対して符号語を求めよ。 x  0101 p1  x1  x2  x3  0  1 0  1 p2  x2  x3  x4  1 0  1  0 p3  x1  x2  x4  0 11  0 w  ( x, p)  0101100 40 練習 w  ( x1, x2 , x3 , x4 , p1, p、2 , p3 ) に対して、次のように冗長ビットを定める（７，４）ハミング符号を考える。 p1  x1  x2  x3 p2  x2  x3  x4 p3  x1  x2  x4 このとき、次の情報ビットに対して符号語を求めよ。（１）（３） x１  0001 x3  1101 （２）（４） x2  1001 x4  1110 41 例 w  ( x1, x2 , x3 , x4 , p1, 、p2 , p3 ) に対して、次のように冗長ビットを定める（７，４）ハミング符号を考える。 p1  x1  x2  x3 p2  x2  x3  x4 p3  x1  x2  x4 このとき、次の受信語に対して誤り訂正を行え。 y   y1, y2 , , y7   0111100 まず、シンドロームを求める。 s1  y1  y2  y3  y5  0 111  1 s2  y2  y3  y4  y6  1 1 1 0  1 s3  y1  y2  y4  y7  0 11 0  0 42 よって、シンドローム s  s1s2 s3  110 より、誤りベクトルが一意に e  (e1 , e2 , , e7 )  0010000 と特定できる。したがって、次のように誤り訂正できる。 y   y1, y2 , , y7   0111100 w  y  e  0111100  0010000  0101100 43 練習 w  ( x1, x2 , x3 , x4 , p1, 、p2 , p3 ) に対して、次のように冗長ビットを定める（７，４）ハミング符号を考える。 p1  x1  x2  x3 p2  x2  x3  x4 p3  x1  x2  x4 このとき、次の受信語に対して誤り訂正を行え。（１） y1  1001011 （３） y3  1101011 （２） y2  1001001 （４） y4  0110001 44 一般のハミング符号 (n, k ) ハミング符号 n  2 1 m 情報ビット長： k  n  m  2 1  m 冗長ビット長： n  k  m シンドローム長： m 符号長： m W  000,111 は、 n  3, m  2, k  1 となり、ちなみに、符号（３、１）ハミング符号。 45 練習 2ビットのシンドロームを持つ、義せよ。 (3,1) ハミング符号を定 46 ハミング符号の符号語間距離 w  ( x1, x2 , x3 , x4 , p1, p、2 , p3 ) に対して、次のように冗長ビットを定める（７，４）ハミング符号を考える。 p1  x1  x2  x3 p2  x2  x3  x4 p3  x1  x2  x4 このとき、次式が成り立つ。 i, j, i  j dh (wi , w j )  3 wi   xi , pi  w j   x j , p j  において、 dh ( xi , x j )  1 のとき、定義より少なくとも冗長ビットが２ビットは異なる。（例えば、 x1 が異なれば、 p1 と p3 も異なる。） dh ( xi , x j )  2 のとき、定義より少なくとも冗長ビットが 1ビット異なる。（例えば、x1 とx2 が異なれば、p2 も異なる。） 47 ハミング符号の情報速度 w  ( x1, x2 , x3 , x4 , p1, p2 , p3 ) で定義される（７，４）ハミング符号の情報速度は、次式で表わされる。 RH (7,4) 4 RH (7,4)  [bit / 記号] 7 より一般に、シンドローム長が m のハミング符号は、情報ビットが、 n  2 1 m 冗長ビットが km  n m m  2  m 1 m の (2 1,2  m 1) ハミング符号になり、情報速度は次式表わされる。 m 2  m 1 m m RH (2 1,2  m 1)  m [bit / 記号] 2 1 48