情報科学概論9 通信と符号化の話 2014.6.27 田中美栄子ディジタル通信と情報の符号化 • ディジタル方式による情報の記録は,「すべての情報を数字に置き換えて記録する」という考え方によるもの. 例えば音楽 CD の場合, 記録すべき音の強さを 65536(＝216) 段階に分けている. • 文字で文章を送る場合. 英語のアルファベットは, 大文字, 小文字を区別すると 52 文字あるが, これは「52 個の異なる記号があって, その組み合わせで文章を作っている」と考えられる. 文章を記録, 伝達するには, 使う文字の数 (この場合 52 個) だけの 2 進数を用意し, それらの組み合わせで文章を 0, 1 の列に置き換えるディジタル情報とは何か • 1 桁の 2 進数は「0, 1」の 2 つ, つまり 2 つの異なるものが区別でき, 2 桁の 2 進数は「00, 01, 10, 11」の 4 つなので 4 つの異なるもの (文字) が区別できる. • 3 桁だと, 000, 001, 010, 011, 100, 101, 110, 111 となり, これら 8 つにそれぞれ異なる文字を対応させ、 8 文字まで使って文が作れる, というわけ 4 桁の 2 進数. • 一般に k 桁の 2 進数は 2のk乗個ある符号文字２進 NL（改行） 0001010 １０進 10 a 1100001 97 b 1100010 98 c 1100011 99 d 1100100 100 e 1100101 101 誤り率1万分の１は小さいか？誤りの正体と符号化 • ディジタル信号にもエラーが起こる • 0と1という数字を送ると言っても、実際には電気信号なので雑音が入ったり、クロックがずれたりするだけで 0が1に、1が0に変わってしまう • 英数半角文字は8ビットで一文字を表すので、実際には8個の２進数列のうち１個が変化しただけで違った文字に化けてしまう • 誤りの正体は、信号の中で0 と 1 が入れ替わること誤り訂正の考え方（１） • バースト欠損ランダム欠損誤り検出訂正（また誤り検出はエラー検出訂正）はエラー検出訂正）とは、データに符号とは、デに符号誤りが発生誤た場合場合にそれをいはある。が発生にそれことで正（また検出・あるは訂正すある。こでバースト欠損をランダム欠損にする方法～アミダくじのアイデア～０１２３４５６７８９３５１２６０８９４７３倍にして送ると安全 • 0→000 • 1→111 と3倍にして送ると、無駄な情報を送らなければならない代わりに、間違いを修正できる 000の一つの0が1に化けても、多数決で元に戻せる．二つ以上同時に間違うとどうしようもないが、そのような確率は非常に低い．誤り確率が１億分の１だと • ３つのゼロのうち一つ間違っても元に戻せる • ２つ以上同時に間違う確率は１億分の１、つまり１憶の文字中１個しか間違わない．１頁に 1000文字、200頁分ある本が持つ情報量は 20万文字である．2バイト文字が20万で320 万ビットである．このような本が３冊で1000万ビット．30冊で１億ビット．つまり誤り率１億分の１とは、本30冊のうち１文字以下しか間違わない、非常に正確な情報伝達ができること誤り検出だけならもっと簡単 • いくら正確でも情報量を3倍使うのでは無駄 • 間違っていることを知るだけなら、パリティ・ビットを付け加えるだけで済む • 送ろうとする情報単位ごとに１の個数を奇数と決めておく．つまりもともと1が奇数個の情報には0を、１が偶数個含まれる情報には、1 をパリティ・ビットに書き込んでおく • 送られてきた情報の1の数が偶数ならどこかに間違いがあるので送りなおして貰えば良い parity check code 「パリティ検査符号」 • つまり, もともと 2 桁だったものの右に, 余分に 1 桁増やして 3 桁にしているのですが, その規則はもとの情報に 1 が偶数個なら 0 を付け加え, もとの情報に 1 が奇数個なら 1 を付け加えるというものです. このように, 誤りの検出や訂正のために余分な情報を付け加えることを符号化といいます. この符号化によると「たけやぶやけた」は 011 000 110 101 110 000 011」となります. 送り手はこれを送るわけです. • なお, 上のような規則で符号化を行う符号を「パリティ検査符号」(parity check code) といいます符号化の話いろいろな符号化 • アルファベットが (ほんとうは２６文字あるが）Ａ，Ｂ, Ｃ, Ｄの４文字だと仮定しよう • これを０と１で符号化（２元符号化）するとき下の表のようにいろいろ考えられるＣ１Ｃ２Ｃ３Ｃ４Ｃ５Ｃ６出現比Ａ 00 0 0 0 0 0 0.6 Ｂ 01 10 10 01 10 10 0.25 Ｃ 10 110 110 011 11 11 0.1 Ｄ 11 1110 111 111 01 0 0.05 特異符号 • Ｃ６は、ＡとＤの両方に0が対応しており、0をＡと読むのかＤなのか不明．このような符号を特異符号という．（文脈次第で、これでも読めることもある）Ｃ１Ｃ２Ｃ３Ｃ４Ｃ５Ｃ６出現比Ａ 00 0 0 0 0 0 0.6 Ｂ 01 10 10 01 10 10 0.25 Ｃ 10 110 110 011 11 11 0.1 Ｄ 11 1110 111 111 01 0 0.05 一意復号可能かどうか • Ｃ5は、特異符号ではないものの、一意復号できない． • 0110という信号はＤＢとも読めるし、ACAとも読めるので紛らわしいＣ１Ｃ２Ｃ３Ｃ４Ｃ５Ｃ６出現比Ａ 00 0 0 0 0 0 0.6 Ｂ 01 10 10 01 10 10 0.25 Ｃ 10 110 110 011 11 11 0.1 Ｄ 11 1110 111 111 01 0 0.05 瞬時復号可能かどうか • C1～Ｃ4は、すべて、一意復号できるが、C4 は瞬時複合できない．C４で0110を送ると、 • 0110という信号を復号するときAやBから始めると途中で困って引き返し、CAと読むまでに時間がかかる．瞬時性がない．Ｃ１Ｃ２Ｃ３Ｃ４Ｃ５Ｃ６出現比Ａ 00 0 0 0 0 0 0.6 Ｂ 01 10 10 01 10 10 0.25 Ｃ 10 110 110 011 11 11 0.1 Ｄ 11 1110 111 111 01 0 0.05 コンパクトかどうか • C1～Ｃ3は、瞬時符号だが、C2はコンパクトでない．無駄がある． • 平均符号長を計算するとC1は２,C2は1.6で C3は1.55．C2はC3より長くコンパクトでないＣ１Ｃ２Ｃ３Ｃ４Ｃ５Ｃ６出現比Ａ 00 0 0 0 0 0 0.6 Ｂ 01 10 10 01 10 10 0.25 Ｃ 10 110 110 011 11 11 0.1 Ｄ 11 1110 111 111 01 0 0.05 コンパクト符号の作り方 • ハフマン符号はコンパクト • 文字の出現比の順にソートし、出現比の一番小さい文字と2番目に小さい文字を合流させる．この二つの枝に0と１を割りつける • 合流したものを含めて、出現比の小さい二つを合流させてこの二つの枝に0と１を割りつける • これを繰り返して確率が1になったらやめる