講義「情報理論」
第１２回 通信路符号化法(1)
情報理工学部門 情報知識ネットワーク研究室 喜田拓也
2019/7/24
講義資料通信路符号化定理 （おさらい）
2
定理 7.4 ［通信路符号化定理］
通信路容量 𝐶𝐶 である通信路に対し， 𝑅𝑅 < 𝐶𝐶 であれば，
情報速度 𝑅𝑅 の符号で復号誤り率がいくらでも小さいも のが存在する．しかし， 𝑅𝑅 > 𝐶𝐶 であれば，そのような 符号は存在しない．
通信路容量を超えない情報速度でなら，
いくらでも精度よく通信できる
ような符号法がある！！
※ Shannon の第 2 符号化定理とも呼ばれる
※でも具体的な符号の構成方法は分かっていない・・・
通信システム全体としての情報伝達の限界 （おさらい）
3
定理 7.6
情報速度 𝓡𝓡 （ビット／秒）で発生する情報を通信路容量 𝐂𝐂 （ビット
／秒）の通信路を介して送るとき，
𝓡𝓡 < 𝐂𝐂
であれば，任意に小さい誤り率で情報を伝送できる．また，
𝓡𝓡 > 𝐂𝐂
であれば，情報源の速度・ひずみ関数が
𝓡𝓡 𝐷𝐷 ∗ = 𝐂𝐂 （ビット／秒）
を満たす 𝐷𝐷 ∗ に対し， 𝐷𝐷 ∗ に任意に近いひずみで情報を伝送できる
が， 𝐷𝐷 ∗ より小さい平均ひずみでは伝送できない．
今日の内容
8.1 線形符号の基礎 8.2.1 (7,4) ハミング符号
4
クイズ・ザ・パリティ！
5
セーフ アウト！
0 1
11 10
110 111
1000001 1001001
01010101 01101101
1111111111 11111111111
単一パリティ検査符号
長さ 𝑘𝑘 の系列 𝑥𝑥 1 𝑥𝑥 2 ・・・ 𝑥𝑥 𝑘𝑘 を記憶のない 2 元通信路で伝送する
そのうちの 1 個に誤りが生じた場合に，それを受信側で検出するには どうすればよいだろうか？
単一パリティ検査符号の符号化方法
全体で「 1 」の個数が偶数になるように，末尾に記号を追加する 𝑐𝑐 = 𝑥𝑥 1 ⊕ 𝑥𝑥 2 ⊕ ・・・ ⊕ 𝑥𝑥 𝑘𝑘
𝒘𝒘 = 𝑥𝑥 1 𝑥𝑥 2 ・・・ 𝑥𝑥 𝑘𝑘 𝑐𝑐
元の情報を表す記号 𝑥𝑥 1 , 𝑥𝑥 2 , ・・・ , 𝑥𝑥 𝑘𝑘 を情報記号という
（ 2 元記号の場合は情報ビットと呼ばれる）
付加された記号 𝑐𝑐 を検査記号（または，検査ビット）という 2 番目の式はしばしば 𝒘𝒘 = (𝑥𝑥 1 , 𝑥𝑥 2 , ・・・ , 𝑥𝑥 𝑘𝑘 , 𝑐𝑐) と表される
6
含まれる 1 の個数が 偶数の場合は 𝑐𝑐 = 0 奇数の場合は 𝑐𝑐 = 1
Try 問 8.1
単一パリティ検査符号の誤り検出
長さ 𝑘𝑘 = 2 の単一パリティ検査符号は， 𝒘𝒘 = (𝑥𝑥
1, 𝑥𝑥
2, 𝑐𝑐) が 0,0,0 , 0,1,1 , 1,0,1 , (1,1,0)
となるので，長さ 3 ，符号語数 4 の符号 𝐶𝐶 = {000, 011, 101, 110}
を用いているとみなせる．
一般には，長さ 𝑘𝑘 の系列に対して，
長さが 𝑘𝑘 + 1 で 1 の個数が偶数となる 2 元系列すべてを符号語として用いる．
（よって符号語数は 𝑀𝑀 = 2 𝑘𝑘 個）
単一パリティ検査符号は，一つの誤り を検出できる！このように誤りの検出 が行える符号を誤り検出符号と呼ぶ
7
100 110
101
001
000 010
011 111
𝑐𝑐
𝑥𝑥1
𝑥𝑥2
単一パリティ符号
(𝑘𝑘 = 2)
の 幾何的表現含まれる１の
個数が偶数個
符号語に隣接する点は
符号語になっていない
組織符号
𝑘𝑘 個の情報記号に対して，何らかの 方法で検査記号を求め，それを付加 することで信頼性を高める符号長 𝑛𝑛 の等長符号を組織符号と呼ぶ
符号長 𝑛𝑛 で情報記号の数が 𝑘𝑘 の組織符号を (𝑛𝑛, 𝑘𝑘) 符号と書く (𝑛𝑛, 𝑘𝑘) 符号の効率 𝜂𝜂 は，定義より
𝜂𝜂 = 𝑅𝑅
𝑅𝑅 𝑚𝑚𝑚𝑚𝑚𝑚 = log 2 𝑀𝑀 � 𝑛𝑛
log 2 2 𝑛𝑛
𝑛𝑛 = 𝑘𝑘
𝑛𝑛 . 単一パリティ検査符号は (𝑘𝑘 + 1, 𝑘𝑘) 符号であり，
効率は 𝜂𝜂 = 𝑘𝑘/(𝑘𝑘 + 1) である
8
長さ 𝑛𝑛 の系列で 𝑘𝑘 個の情報記号を
送るとみれる 𝑘𝑘 を大きくとれば効率は上がるが，
冗長度が低くなり信頼性は小さくなる
𝒘𝒘 = 𝑥𝑥
1𝑥𝑥
2・・・ 𝑥𝑥
𝑘𝑘𝑐𝑐
1𝑐𝑐
2・・・ 𝑐𝑐
𝑛𝑛−𝑘𝑘𝑛𝑛
先の例は，
(3,2) パリティ
検査符号
(9,4) 水平垂直パリティ検査符号
右図のように 4 個の情報ビットを 2 × 2 の配列 に並べ，各行と各列に一つずつ検査ビットを 付け加える．
𝑐𝑐 1 = 𝑥𝑥 11 + 𝑥𝑥 12 𝑐𝑐
2= 𝑥𝑥 21 + 𝑥𝑥 22 𝑐𝑐 3 = 𝑥𝑥 11 + 𝑥𝑥 21 𝑐𝑐 4 = 𝑥𝑥 12 + 𝑥𝑥 22
検査ビットの行の 1 の数が偶数になるよう に，検査ビットの検査ビットを右隅におく．
𝑐𝑐 5 = 𝑐𝑐 1 + 𝑐𝑐 2 = 𝑥𝑥 11 + 𝑥𝑥 12 + 𝑥𝑥 21 + 𝑥𝑥 22
= 𝑐𝑐 3 + 𝑐𝑐 4
この符号により 1 個の誤りが訂正できる．
また， 2 個の誤りを検出することができる．
このような符号を，誤り検出訂正符号，
あるいは単に誤り訂正符号と呼ぶ．
9
𝑥𝑥
11𝑥𝑥
12𝑥𝑥
21𝑥𝑥
22𝑐𝑐
3𝑐𝑐
4𝑐𝑐
1𝑐𝑐
2𝑐𝑐
5水平垂直パリティ検査符号
単一誤りの訂正と
2
重誤りの検出(a) (b)
(c) (d)
Try 問 8.3
線形符号
式 𝑐𝑐 = 𝑥𝑥 1 + 𝑥𝑥 2 + ・・・ + 𝑥𝑥 𝑘𝑘 のように
※，検査記号が情報記号の線 形な式で与えられる符号を線形符号と呼ぶ
線形符号では，任意の二つの符号語について，成分ごとの和（排 他的論理和）をとると，それもまた符号語になる．この性質は線形 符号となるための必要十分条件である
単一パリティ検査符号 𝐶𝐶 = {000, 011, 101, 110} は線形符号 この二つの符号語 011 と 101 の和をとってみよう
(0, 1, 1) + (1, 0, 1) = (0 + 1, 1 + 0, 1 + 1) = (1, 1, 0)
※
元は⊕
（排他的論理和）．この演算は，mod 2
の演算，つまり2
で割って余りをとる演算 を考えれば簡単に+
演算子で表すことができる．以降は基本的に+
は⊕
を表す．mod 2
の世界では，加算も減算も同じ意味となる．たとえば，1 − 1 = 1 + 1 = 0
だし，0 − 1 = 0 + 1 = 1
である．すなわち，−
演算子もそのまま+
演算子に置き換えられる．10
パリティ検査方程式
(𝑛𝑛, 𝑘𝑘) 線形符号において，各検査ビット (𝑤𝑤 𝑘𝑘+1 , 𝑤𝑤 𝑘𝑘+2 , … , 𝑤𝑤 𝑛𝑛 ) は
𝑤𝑤
𝑘𝑘+1= 𝑎𝑎
11𝑤𝑤
1+ 𝑎𝑎
12𝑤𝑤
2+ ⋯ + 𝑎𝑎
1𝑘𝑘𝑤𝑤
𝑘𝑘, 𝑤𝑤
𝑘𝑘+2= 𝑎𝑎
21𝑤𝑤
1+ 𝑎𝑎
22𝑤𝑤
2+ ⋯ + 𝑎𝑎
2𝑘𝑘𝑤𝑤
𝑘𝑘,
𝑤𝑤
𝑛𝑛= ⋮ 𝑎𝑎
(𝑛𝑛−𝑘𝑘)1𝑤𝑤
1+ 𝑎𝑎
(𝑛𝑛−𝑘𝑘)2𝑤𝑤
2+ ⋯ + 𝑎𝑎
𝑛𝑛−𝑘𝑘 𝑘𝑘𝑤𝑤
𝑘𝑘.
これを移行して得られる次の式をパリティ検査方程式と呼ぶ．
𝑎𝑎
11𝑤𝑤
1+ 𝑎𝑎
12𝑤𝑤
2+ ⋯ + 𝑎𝑎
1𝑘𝑘𝑤𝑤
𝑘𝑘+ 𝑤𝑤
𝑘𝑘+1= 0, 𝑎𝑎
21𝑤𝑤
1+ 𝑎𝑎
22𝑤𝑤
2+ ⋯ + 𝑎𝑎
2𝑘𝑘𝑤𝑤
𝑘𝑘+ 𝑤𝑤
𝑘𝑘+2= 0,
𝑎𝑎
(𝑛𝑛−𝑘𝑘)1𝑤𝑤
1+ 𝑎𝑎
(𝑛𝑛−𝑘𝑘)2⋮ 𝑤𝑤
2+ ⋯ + 𝑎𝑎
𝑛𝑛−𝑘𝑘 𝑘𝑘𝑤𝑤
𝑘𝑘+ 𝑤𝑤
𝑛𝑛= 0.
単一パリティ検査符号の符号語を 𝒘𝒘 = 𝑤𝑤 1 , 𝑤𝑤 2 , … , 𝑤𝑤 𝑛𝑛 とすると，
そのパリティ検査方程式は 𝑤𝑤 1 + 𝑤𝑤 2 + ・・・ + 𝑤𝑤 𝑛𝑛−1 + 𝑤𝑤 𝑛𝑛 = 0 .
𝒘𝒘 に含まれる 1 の数が偶数
11誤りパターンとシンドローム
ある線形符号 𝐶𝐶 の符号語 𝒘𝒘 を送って 𝒚𝒚 が 受信されたとする．これは， 𝒘𝒘 に誤り 𝒆𝒆 が 加わったものと見ることができる．
𝒚𝒚 = 𝒘𝒘 + 𝒆𝒆
この 𝒆𝒆 を誤りパターンと呼ぶ．
パリティ検査方程式の左辺に受信語 𝒚𝒚 = (𝑦𝑦 1 , 𝑦𝑦 2 , … , 𝑦𝑦 𝑛𝑛 ) を（ 𝑦𝑦 𝑖𝑖 を 𝑥𝑥 𝑖𝑖 として）代入して得られる値（の組）をシンドロームと呼ぶ．
単一パリティ検査符号の場合， 𝒘𝒘 = (𝑤𝑤 1 , 𝑤𝑤 2 , … , 𝑤𝑤 𝑛𝑛 ) はパリティ 検査方程式 𝑥𝑥 1 + 𝑥𝑥 2 + ⋯ + 𝑥𝑥 𝑛𝑛 = 0 を満たすので，
𝑠𝑠 = 𝑤𝑤 1 + 𝑒𝑒 1 + ・・・ + 𝑤𝑤 𝑛𝑛 + 𝑒𝑒 𝑛𝑛 = 𝑒𝑒 1 + 𝑒𝑒 2 + ・・・ + 𝑒𝑒 𝑛𝑛 .
よって，奇数個の誤りが生じた場合には 𝑠𝑠 = 1 となる．このように，
シンドロームは誤りが発生した場合の有力な手がかりとなる．
12
誤りパターン 𝒆𝒆 を 用いた通信路のモデル
⊕ 𝒆𝒆 𝒚𝒚 = 𝒘𝒘 + 𝒆𝒆
誤り源
𝒘𝒘
(7,4) ハミング符号 (Hamming codes)
水平垂直パリティ検査符号は情報ビットよりも 検査ビットが多く，あまり効率がよくない
行と列の検査による誤り位置推定という考えを 一般化し，効率のよい符号を構成したい！
4 個の情報ビット 𝑥𝑥 1 , 𝑥𝑥 2 , 𝑥𝑥 3 , 𝑥𝑥 4 に対して，
𝑐𝑐
1= 𝑥𝑥 1 + 𝑥𝑥 3 + 𝑥𝑥 4
𝑐𝑐
2= 𝑥𝑥 1 + 𝑥𝑥 2 + 𝑥𝑥 3
𝑐𝑐
3= +𝑥𝑥 2 + 𝑥𝑥 3 + 𝑥𝑥 4
として検査ビット 𝑐𝑐
1, 𝑐𝑐
2, 𝑐𝑐
3を作り，組織符号化
（ 𝒘𝒘 = (𝑥𝑥 1 , 𝑥𝑥 2 , 𝑥𝑥 3 , 𝑥𝑥 4 , 𝑐𝑐 1 , 𝑐𝑐 2 , 𝑐𝑐 3 ) ）する．
この符号は (7,4) ハミング符号と呼ばれる．
この符号は情報ビットが 4 であるから，符号語は 2 4 = 16 個ある．
14
𝑥𝑥
1𝑥𝑥
2𝑥𝑥
3𝑥𝑥
4𝑐𝑐
1𝑐𝑐
2𝑐𝑐
30 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 0 1 1 1 1 0 1 0 0 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1 1 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1
(7,4) ハミング符号
(7,4) ハミング符号のシンドローム
符号語を 𝒘𝒘 = (𝑤𝑤
1, 𝑤𝑤
2, ・・・ , 𝑤𝑤
7) とすると，パリティ検査方程式は，
𝑤𝑤 1 + 𝑤𝑤 3 + 𝑤𝑤 4 + 𝑤𝑤 5 = 0,
𝑤𝑤 1 + 𝑤𝑤 2 + 𝑤𝑤 3 + 𝑤𝑤 6 = 0,
𝑤𝑤 2 + 𝑤𝑤 3 + 𝑤𝑤 4 + 𝑤𝑤 7 = 0.
受信語 𝒚𝒚 = 𝑦𝑦 1 , 𝑦𝑦 2 , ・・・ , 𝑦𝑦 7 に対するシンドロームは 𝑠𝑠
1= 𝑦𝑦 1 + 𝑦𝑦 3 + 𝑦𝑦 4 + 𝑦𝑦 5 ,
𝑠𝑠
2= 𝑦𝑦 1 + 𝑦𝑦 2 + 𝑦𝑦 3 + 𝑦𝑦 6 ,
𝑠𝑠
3= 𝑦𝑦 2 + 𝑦𝑦 3 + 𝑦𝑦 4 + 𝑦𝑦 7 . これは結局，誤りパターン 𝒆𝒆 = (𝑒𝑒
1, 𝑒𝑒
2, ・・・ , 𝑒𝑒
7) のみから次のようになる．
𝑠𝑠
1= 𝑒𝑒 1 + 𝑒𝑒 3 + 𝑒𝑒 4 + 𝑒𝑒 5 ,
𝑠𝑠
2= 𝑒𝑒 1 + 𝑒𝑒 2 + 𝑒𝑒 3 + 𝑒𝑒 6 ,
𝑠𝑠
3= 𝑒𝑒 2 + 𝑒𝑒 3 + 𝑒𝑒 4 + 𝑒𝑒 7 .
15誤りパターン
ロームシンド𝑒𝑒1 𝑒𝑒2 𝑒𝑒3 𝑒𝑒4 𝑒𝑒5 𝑒𝑒6 𝑒𝑒7 𝑠𝑠1 𝑠𝑠2 𝑠𝑠3 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 1 0 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
同じパターン
がない！
(7,4) ハミング符号の復号 （例題 8.1 ）
先のハミング符号で符号化された系列 1101111 を受け取った．
この系列を復号しよう．ただし，誤りは高々 1 か所だけとする．
まず，受信語 𝒚𝒚 = 1,1,0,1,1,1,1 のシンドロームを計算する．
𝑠𝑠
1= 𝑦𝑦 1 + 𝑦𝑦 3 + 𝑦𝑦 4 + 𝑦𝑦 5 = 1 + 0 + 1 + 1 = 1, 𝑠𝑠
2= 𝑦𝑦 1 + 𝑦𝑦 2 + 𝑦𝑦 3 + 𝑦𝑦 6 = 1 + 1 + 0 + 1 = 1, 𝑠𝑠
3= 𝑦𝑦 2 + 𝑦𝑦 3 + 𝑦𝑦 4 + 𝑦𝑦 7 = 1 + 0 + 1 + 1 = 1.
これより，シンドロームは (1,1,1) なので，
誤りパターンは (0,0,1,0,0,0,0) と分かる．
3 ビット目を修正して， 𝒚𝒚 = (1,1,1,1,1,1,1) . したがって，元の情報は (1,1,1,1) となる．
Try 練習問題 8.1
16誤りパターン
ロームシンド𝑒𝑒1 𝑒𝑒2 𝑒𝑒3 𝑒𝑒4 𝑒𝑒5 𝑒𝑒6 𝑒𝑒7 𝑠𝑠1 𝑠𝑠2 𝑠𝑠3 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 1 0 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
今日のまとめ
8.1 線形符号の基礎
8.1.1 単一パリティ検査符号
8.1.2 組織符号と線形符号
8.1.3 水平垂直パリティ検査符号
8.2 ハミング符号
8.2.1 (7,4) ハミング符号 次回
一般のハミング符号とハミング符号の誤り訂正能力
17
