デジタル通信
- コンピュータネットワークを流れるデータ量を少なくするには、どのような工夫が必要かを考えてみましょう。
- 多くのスマートフォンやパソコンは、インターネットにつながっています。インターネットに接続できないと、電話、動画の視聴、検索ができなくなり、大変困ります。
- インターネットでは、文字、動画、音声はディジタル信号(0と1)に変換されます。コンピュータの中でもディジタル信号で計算されます。
- デジタル通信で我々は画像やテキストなどを送受信をしています。このデータの量をなるべく少なくしたい。それにはどのようにテキストや画像などを効率よく0と1の信号に置き換えるかを考えたいと思います。
図1 デジタル通信のデータは0と1
ディジタル信号に変換する
ディジタル信号に変換する(1)
例えば、「りんご」、「みかん」、「ぶどう」、そして「ばなな」、この4つの果物をデジタル信号にして相手に送ることを考えましょう。りんごを「00」、みかんを「01」、ぶどうを「10」、そしてばななを「11」とします。
図2 デジタル通信のデータは0と1(1)
ディジタル信号に変換する(2)
「00」や「01」というデータを受け取った時、これらがどの果物かわからないと困ります。どのように果物の名前を置き換えたか、このルールが分かっていれば置き換えは簡単です。
図3 デジタル通信のデータは0と1(2)
ディジタル信号に変換する(3)
「00」や「01」と変換されたデータを、受信側は「00はりんご」、「01はみかん」、「10はぶどう」、そして「11はばなな」だと理解することができます。
図4 デジタル通信のデータは0と1(3)
ディジタル信号に変換する(4)
今、「11101000」というデータが届きました。どの果物が届いたのでしょうか。
図5 デジタル通信のデータは0と1(4)
ディジタル信号に変換する(5)
11はばなな、10はぶどう、りんごは00ですから、「ばなな、ぶどう、ぶどう、りんご」になります。
図6 デジタル通信のデータは0と1(5)
データの量を減らそう!
- りんごを8個、みかんを4個、ぶどうを1個、ばななを2個を食べたい。これを相手に伝えるには、0または1が幾つ必要になるでしょうか?
図7 果物の種類を0と1で表す(符号1)
- 図7のように置き換えると、(1つの果物に0と1を2個使い→2ビット)×(8+4+1+2)個の果物=2ビット×15個=30ビット、となり0または1が30個(ビット)必要になります。
- 例えば、以下の果物を相手に伝えてみます。
- [送りたい果物] りんご,りんご,みかん,みかん,りんご,みかん,ぶどう,みかん,りんご,りんご,りんご,りんご,りんご,ばなな,ばなな,
- [0と1に置き換えてみる] 000001010001100100000000001111
データ量が少ない置き換え(1)
全ての信号を0と1の2つのデータで表していては全体のデータ量を少なくすることができません。このため果物の種類によって、「0」または「111」と違う数(長さ)の信号を使って置き換えを考えます。この置き換えを試してみましょう。
- まず、何個の果物を送りたいか、この順番によって果物をここに書いてあるような形に並べていきます。
- 個数の小さいものから、大きいものに、果物を並び替えてください。
図8 ハフマン木を作る(1)
データ量が少ない置き換え(2)
- この果物の中から個数が少ないものを2つ選びます。
- この2つの果物から新しい「ぶどう+ばなな」という果物の丸を作って下さい。
- そして、この新しい「ぶどう+ばなな」から元の「ぶどう」と「ばなな」に線を繋げます。
- 「ぶどう+ばなな」の中の数字は、元の「ぶどうが1個」と「ばななが2個」の中の数字を足した数の3になります。
図9 ハフマン木を作る(2)
データ量が少ない置き換え(3)
- この操作を繰り返します。
- 「ぶどうばなな」と「みかん」、これらがこの中から少ない数の果物になりますので、次は「ぶどう+ばなな」と「みかん」の2つから1つの果物「ぶどう+ばなな+みかん」にまとめます。「ぶどう+ばなな+みかん」の個数が3+4ですから合計で7になります。
図10 ハフマン木を作る(3)
データ量が少ない置き換え(4)
- 同じように「ぶどう+ばなな+みかん」と「りんご」をまとめて1つの果物「すべての果物」にします。
- ここでは4つしか果物ありませんから「すべての果物」とします。
- 「ぶどう+ばなな+みかん」の個数は7個、そして「りんご」が8個ですから、7+8で「すべての果物」の数字は15になります。
図11 ハフマン木を作る(4)
データ量が少ない置き換え(5)
数の少ない果物を2つずつまとめ上げることによって、木のような形の絵を描くことができます。
図12 ハフマン木を作る(5)
データ量が少ない置き換え(6)
- 求めた果物には2本ずつ線が引かれています。
- この2本の枝にそれぞれ「0」または「1」という数字を書いてください。
図13 ハフマン木を作る(6)
データ量が少ない置き換え(7)
- 「すべての果物」から「ぶどう」までの線に振られている0または1の数字を並べたものが「ぶどう」のデータになります。
- ここでは「すべての果物」から「ぶどう+ばなな+みかん」、「ぶどう+ばなな」、そして「ぶどう」、ここには1と1と1という数字が書かれています。
- この数字を並べ、「ぶどう」のデータは「111」になります。
図14 ハフマン木を作る(7)
データ量が少ない置き換え(8)
- 次は「ばなな」のデータを見つけてみましょう。
- 「全ての果物」、「ぶどう+ばなな+みかん」、「ぶどう+ばなな」、そして「ばなな」、この道順に沿って「110」というのが- 「ばなな」のデータになることがわかります。
図15 ハフマン木を作る(8)
データ量が少ない置き換え(9)
- 「みかん」のデータはどうでしょうか。もう手順が皆さん分かりましたよね。
- 「すべての果物」から「みかん」までの道のりを見ていきましょう。
- 「すべての果物」、「ぶどう+ばなな+みかん」、そして「みかん」に振られている数字は「10」、従って「みかん」のデータは「10」になります。
図16 ハフマン木を作る(9)
データ量が少ない置き換え(10)
- 最後に「りんご」です、
- 「りんご」は「すべての果物」から1つの線で「りんご」まで辿り着きます。
- このため「りんご」は、線に振られている数値が0ですから「0」と1つの数字だけでデータを作ることができました.
図17 ハフマン木を作る(10)
どれくらいデータ量が減るのか
- 相手に伝えたい果物(りんご:8個,みかん:4個,ぶどう:1個,ばなな:2個)
- 例えば、「りんご,りんご,みかん,りんご,りんご,りんご,みかん,みかん,みかん,りんご,りんご,ぶどう,ばなな,ばなな,りんご,」を0と1で置き換えてみる。
- [単純な置き換え(前の例)] 000001000000010101000010111100
- [工夫した置き換え] 0010000101010001111101100 (使用する0と1が、5個少なくなりました。)
- もちろん、工夫後の{0,1}データから果物を区別することができます! データから果物を見つけてみましょう。
図18 果物の種類を0と1で表す(符号2)
試してみよう
- 自分で果物の個数を変えて試してみよう!
- りんご:?個,みかん:?個,ぶどう:?個,ばなな:?個
- 各果物の個数により、一番良い置き換え方が代わります。
図19 自分で考えて果物の種類を0と1で表す(符号3)
- 工夫前:000001000000010101000010111100
- 工夫後:(どれくらい減るかを試してみよう)
- 手順を間違えると、データ数が増えてしまうことがあります。
まとめ
- どのように置き換えるかを工夫すると、データ量(0と1の数)を少なくすることができる。
- 置き換えは、どのデータをどれだけ送りたいか(確率)で考えるとよい。
- どのデータが送られるかは、予め分からないので、長い目で見てどのように置き換えるかを考えます。(ある場合だけを考えない。)
- ※このページに含まれる情報は、掲載時点のものになります。