情報理論は、データを効率良く伝える・正しく届けるための数学的基礎。圧縮のハフマン符号と誤り訂正符号を学びます。
日野 こむぎ
ZIP圧縮とかってどうやって動いてるの?
藤森 さやか 先生
代表的な圧縮の基礎はハフマン符号という方式よ。
出現頻度が高い文字に短いビット列、稀な文字に長いビット列を割り当てるの。
青木 澪
補足すると、英文では「e」が頻出だから1〜3ビット、「z」は稀だから10ビットくらい、と差をつけて圧縮するのよ。
これが可変長符号の発想ね。
桃井 すみれ
へぇ〜!
よく出る文字を短くするんですねぇ♪
日野 こむぎ
誤り訂正って何?
青木 澪
通信路でビットが化けることがあるの。
それを検出・修正する技術が誤り訂正符号よ。
藤森 さやか 先生
代表はパリティビット。
送信データに1ビット余分に追加して、合計の1の数が偶数 (or 奇数) になるようにするの。
1ビットの誤りを検出できるわ。
青木 澪
より高度なハミング符号は誤りを「検出」するだけでなく「訂正」もできるの。
CDやメモリで使われている技術よ。
日野 こむぎ
通信中にビットが化けても直せるってすご〜い!
あたし、感動した!
桃井 すみれ
わぁ、CDが多少傷ついても再生できるのはこれのおかげなんですねぇ。
えへへ、感動ですぅ!
確認クイズ
1ビットの誤りを検出するだけでなく、訂正もできる符号はどれか。
- パリティビット
- ハミング符号
- CRC
- チェックサム
こたえを見る
正解: 2. ハミング符号
ハミング符号は冗長ビットを使って1ビット誤りを訂正、2ビット誤りを検出できます。パリティビット・CRC・チェックサムは検出のみで訂正はできません。