デジタル情報学概論 2004年10月7日 第2回資料 担当 重定 如彦
情報の正確で高速な伝達 以下の3つが重要。現在デジタル情報の伝達手段として最も使われているインターネットを例に挙げて解説する 以下の3つが重要。現在デジタル情報の伝達手段として最も使われているインターネットを例に挙げて解説する どうやって目的地に情報を届けるか? 情報を高速に届けるための様々な工夫 情報の劣化に対する対処
インターネットの構成 インターネットは世界中のコンピュータ同士を通信回線でつないだもの インターネット
IPアドレス インターネットに接続されたコンピュータはIPアドレスとよばれる住所が割り当てられている
ドメイン名 IPアドレスは人間にとっては扱いにくい(覚えるのが困難)なので、人間がコンピュータの住所を扱う場合は一般にIPアドレスではなく、ドメイン名と呼ばれる方法で表現する ドメイン名はアルファベットを . (ピリオド)で区切ったもの ドメイン名は階層化されており、右にいけばいくほどアルファベットの表す情報が広くなる(郵便の住所と逆) IPアドレス 133.25.252.152 www.i.hosei.ac.jp ドメイン名 WWW:ウェブサーバ Hosei:法政 Japan:日本 Ichigaya:市ヶ谷 Academic:大学
DNSサーバ ドメイン名は人間にとってはわかりやすいがデータのサイズが大きく、 不定長(長さが決まってない)のでコンピュータにとっては扱いにくい ドメイン名 文字の長さバイト www.i.hosei.ac.jp 17バイト IPアドレス 4バイト 133.25.252.152 4バイト そこで、ドメイン名をDNS(Domain Name System)サーバと呼ばれるコンピュータを使ってIPアドレスに変換する DNSサーバはインターネットに接続されたコンピュータで、ドメイン名とIPアドレスの対応表を管理する www.i.hosei.ac.jp DNSサーバを使って変換 133.25.252.152
DNSサーバの仕組み (略) (略) (略) (略) インターネットには何億というコンピュータが接続されているので、一つのDNSサーバがすべてのコンピュータのIPアドレスを管理するのは不可能。 そこで、DNSサーバはコンピュータを階層ごとに管理を行う。 下の図でそれぞれのDNSサーバは矢印のDNSサーバのIPアドレスを管理している。ルートのDNSサーバから順番に問い合わせていけばあらゆるドメイン名のコンピュータのIPアドレスを調べることが可能 (略) (略) (略) (略) .com .co.jp ルート .jp .ac.jp .hosei.ac.jp .i.hosei.ac.jp
ルータ(router) インターネットはルータと呼ばれる機械で繋がれている ルータは道案内を行う機能を持つ 目的のIPアドレスのコンピュータにたどり着くためにはどちらの方向へ行けばよいか(どの通信回線を通ればよいか)を教えてくれる機能を持つ ルータはルーティングテーブルという表を持つ ルーティングテーブルは、「IPアドレス」と「そのIPアドレスにたどり着くにはどちらへ行けばよいか」を表にしたもの (略) ルータ ルータ 133.25.252.152 (www.i.hosei.ac.jp)
デジタルデータ転送の手順 ドメイン名をIPアドレスに変換 DNSサーバを使い、ドメイン名からコンピュータの住所で あるIPアドレスを調べる デジタルデータを転送する 経路にデジタルデータを電気信号に変換して転送する
データ転送の工夫(その1) データを細かく分割して転送する インターネットの場合、デジタル情報をパケットと呼ばれる約1000バイト程度のデータに細かく分割して転送を行う これは、大きなデータをそのまま一度に送ってしまうと以下のような問題が発生する可能性があるため 転送途中で失敗すると、一からすべてやり直さなければならない 巨大なデータを途切れなく送信してしまうと、長時間の間そのデータを転送する通信回線が占有されてしまい、他の用途に使えなくなる
パケットを使った転送の流れ パケットは、転送するデジタル情報を細かく分割し、それにヘッダ(下図の黄色い部分)と呼ばれる情報を付加したもの パケットを受け取ったコンピュータはヘッダを取り除き、元のデータに復元する 転送するデータ ・・・・・ パケット1 パケット2 パケットn インターネットに分割したパケットを送信 ・・・・・ 元に戻す
パケットのヘッダ パケットのヘッダには以下のような情報が記述される パケットのヘッダには以下のような情報が記述される パケットの送信先のIPアドレス ルータはこの情報を元にパケットをどこに転送するかを判断する パケットが転送するデータ本体に関する情報 元のデータのどの部分(元のデータの先頭から何バイト目から、何バイト分)のデータであるかの情報 パケットを受け取ったコンピュータはこの情報を元にデータを復元する その他の情報 上記以外にもデータの通信に必要な様々な情報を格納
パケットの利点 一部のパケットの転送が失敗しても、失敗したパケットだけを再転送すれば良い 様々な転送経路を使って転送効率を上げることができる 道路と同じように、目的のコンピュータまでの通信回路の経路は複数存在する。空いている経路を使ったり、パケットを異なる経路を使って別々に転送することで転送効率を向上することが可能
データ転送の工夫(その2) データを圧縮する デジタル情報は様々な工夫を行うことによって、データのサイズを小さくすることが可能である。これをデータの圧縮と呼ぶ データの転送に必要な時間は以下の式で計算することができる。 データの量 / 通信回線の転送速度 当然データの量を小さくすれば、データを高速に転送することが可能 画像や動画は、データのサイズが非常に大きくなる傾向があるため、 データの圧縮はデータの高速な転送に欠かせない技術である。 高速なデータ転送が必要な例:10分の動画をデータを転送しながら見るためには、10分以内にデータの転送が終わらなければならない
データ圧縮の例(その1) 画像の圧縮 データの圧縮はデータの中の冗長な(=余分な、無駄な)データを見つけ、その性質を使って別の方法で表現する 例:左下の6*6ドットの画像の符号化の例 普通に符合化を行うと点の数が6*6=36個。色を4バイト(1600万色)で表現したとすると 36*4=144バイトのデータが必要 色がいくつ並んでいるかという方法で符号化するとこの画像は、 青2、赤2、青3、赤4、青1、赤12、青1、赤4、青3、赤2、青2 と表現できる。色を4バイト、色の並んだ個数を1バイトで表現したとすると、11*(4+1)=55バイトで表現可能 この2つを比較すると後者は前者の 55/144=約0.38=38%のデータで同じ画像を表現できることがわかる この比率を圧縮率と呼ぶ
データの圧縮の例(その2) 動画の圧縮例 動画を普通の方法で符号化すると、動画を構成する画像データを一つ一つ符号化しそれを集めるということになる。 しかし、動画の「連続する画像データはほとんどその内容が変化しない」という性質を利用すればかなりのデータを圧縮することが可能になる 例:ある動画で、画像が右のように変化した場合 通常の方法で符号化すると、2枚分のデータが必要なので 144*2=288バイトのデータが必要 2枚目の画像と1枚目と画像の違いは (2,0)、(3,0)、(0,2)、(0,3)、(5,2)、(5,3)、(2,5)、(3,5) の8つの点がそれぞれ青に変化したということ。 点を2バイト、色を4バイトで表したとすると2枚目の画像は たった8*(2+4)=48バイトで表すことができる。 従って圧縮率は (144+48)/288=約67%となる
圧縮に関する補足 紹介した圧縮方法は一例であり、実際にはもっと複雑な方法を使ってさらに高い圧縮率が実現されている 圧縮には様々な方法があり、圧縮するデータの性質に合わせて圧縮方法を選ぶ必要がある。 例えば、先ほど紹介した画像の圧縮方法は、アニメのような同じ色が連続する画像には適しているが、写真のような画像には適していない 圧縮されたデータを実際に使う際にはデータを元の形に戻す必要がある。この操作をデータの解凍と呼ぶ
データ転送の工夫(その3) データのキャッシュ 転送されてきたデータを、メモリに一定期間保存し、もう一度同じデータが欲しくなった場合は、そのデータが更新されているかどうかをまずチェックし、更新されていた場合のみデータを転送する。これにより同じデータを 再度インターネットから取得しなくてもよくなり、効率があがる。 このように、再利用する事を目的としてメモリーやハードディスクなどに 一時的に保存するデータのことをキャッシュ(cache)と呼ぶ。 なお、キャッシュはコンピュータでは非常に良く使われる技術で、データの転送に限らず様々な所で利用される。
1.午前11以降に更新されているかを問い合わせる キャッシュの具体例 Aさんが午前11時にあるウェブサイトを見に行った時の動作 画面に表示する ウェブサーバ コンピュータのメモリ 午前11時に取ってきた ウェブページのデータ メモリにキャッシュする Aさんが午前12時に同じウェブサイトを見に行った時の動作 1.午前11以降に更新されているかを問い合わせる ウェブサーバ コンピュータのメモリ 午前11時に取ってきた ウェブページのデータ 2.問い合わせの返事を返す (更新されていた場合は 新しいデータを転送する) 3.更新されていなければ キャッシュを表示する
デジタル情報の劣化 前回の授業で、デジタル情報はコピーや転送によって情報が劣化しないと説明したが、実はデジタルデータもコピーや転送の際に様々な原因で情報が劣化する可能性がある。 電磁波などの影響 通信回線を使ったデータの転送は、電気信号を使って転送を行うが、転送の途中で電磁波などの影響で電気信号が正しく伝わらない場合がある。 通信回線の渋滞や切断 通信回線も道路と同様に、一度に転送できる情報の量に上限がある。上限を超えて通信回線を利用しようとすると、通信回線が渋滞してデータの転送に時間がかかったり、データが届かなかったりする場合がある。 また、通信回線が物理的に切断したりした場合も転送は不可能である。 インターネットの場合パケットが一つでも届かなければ情報が劣化する
情報の劣化に対する対処 情報の劣化が起きる可能性があるにもかかわらず、デジタル情報のコピーや転送が正確に行われているように見えるのは、情報の劣化に対して以下の対処(これらを誤り制御と呼ぶ)がなされているからである。 誤りの検出 コピーまたは、転送したデータが元のデータと異なることを検出する 誤りの訂正 誤りが検出された場合、それを訂正する 注:この授業では、話をわかりやすくするために、様々なデータを10進数で表しているが、実際にはコンピュータは2進数を使っている
一致しないのでデータが誤っていることがわかる 誤りの検出方法 誤りを検出する為に余分なデータを付加する データの転送の際に、受け取った側が誤りを検出できるように、誤り検出符号と呼ばれる余分なデータを転送の際に付け加える 例: 10 20 30 40 50 という5バイトのデータを転送する際に、 5つのデータの合計である 10+20+30+40+50=150 を付加し、 10 20 30 40 50 150 という6バイトのデータを送信する。 このデータを受け取った側は、最初の5バイトのデータの合計が6バイト目のデータと一致しなければ何かが誤っていることを検出することが可能 10 20 30 40 50 150 10 20 30 40 60 150 転送中に情報が劣化 10+20+30+40+60=160 となり、6バイト目の150と 一致しないのでデータが誤っていることがわかる
一致してしまうので、誤りを検出することができない 誤りの検出の限界 先ほどの例では、誤りの数が一つであれば必ず誤りを検出することが可能だが、2つ以上誤りが発生した場合は以下のように誤りを検出できない場合がある。 誤り訂正符号を増やすことでさらなる誤りを検出できるようになるが、そのかわり、データの量が増えてしまうという欠点がある 10 20 30 40 50 150 10 20 30 30 60 150 転送中に情報が劣化 10+20+30+30+60=150 となり、6バイト目の150と 一致してしまうので、誤りを検出することができない
誤りの検出確率 誤り訂正符号を増やすことで、誤りの検出確率を高くすることができるが、転送するデータの量が増えるのが問題となってしまう。そこで、ある一定以上の確率で誤りが検出できれば良しとするのが一般的である。 先ほどの2つの誤り検出符号を使った場合の誤りの検出確率 転送中にあるデータが一つ変化する確率を約1%とすると、データが二つ変化する確率は約0.01%である。二つ変化した場合で、誤りを検出できないのは、二つの数字の変化の量の合計が0の場合だけである。このことからこの方法で誤りを検出できない確率は0.0001%以下であると言える。 注:上記の確率の数値はかなり大雑把な数字です。正確な確率の計算方法は確率の知識が必要なのでこの授業では省略します インターネットで実際に使われている誤り検出符号はもっと複雑な計算によって作成され、かなりの確率で誤りを検出できるようになっています
誤りの訂正 誤りが発見できた場合は、その誤りを訂正する必要がある インターネットでのデータ転送時の誤りの訂正方法 誤りが発見できた場合は、その誤りを訂正する必要がある インターネットでのデータ転送時の誤りの訂正方法 受け取った側が誤り検出符号によって誤りを検出した場合 送信側に、もう一度同じデータを転送するように要求する データが届かなかった場合 データを転送した場合、データがちゃんと送られたかどうかを確認するために、受け取り側はデータを受け取った際に必ず届いたことを確認するメッセージを送り返す決まりになっている。データを転送してから一定時間内に転送確認のメッセージが返ってこなかった場合は、データが届かなかったとみなし、もう一度同じデータを転送する
誤り訂正符号 誤り検出符号と同様に、誤り訂正符号をデータに付加するという方法がある。誤り訂正符号は、誤り検出符号よりも多くのデータを付加する必要がある。 例: 1 2 3 4 5 6 7 8 9 という9バイトのデータを転送する際に、データを3バイト毎に以下のように並べ、それぞれの行と列の合計を誤り訂正符号として付加し、16バイトのデータを転送する(水色の枠の数字が誤り訂正符号) 1 2 3 6 4 5 15 7 8 9 24 12 18 45 1 2 3 6 4 10 15 7 8 9 24 12 18 45 転送中に 5が10に変化 数字の合計が一致しない2つの誤り訂正符号(黄色い部分)の場所からどこが誤ったかを知ることができ、15-6-4=5という計算から誤りを訂正することができる。
その他の誤り訂正 フロッピーディスク、ハードディスク、CD、DVDなどに保存したデータは、それらの装置が物理的に壊れてしまうと当然データは失われてしまう。 また、どんな装置であれ、時間の経過と共に様々な原因によって、中に保存されたデータが劣化する可能性がある。 最も単純な誤り訂正の方法に、データが壊れたときに復元する為に、デジタルデータを他の装置にコピーしバックアップをとるというものがある。 この方法は単純であるが実に効果的で、実際に企業や大学などでは、大事なデータを保存する装置は定期的にバックアップを取ることで、万が一にデータが失われた時のために備えるのが一般的である。 皆さんも、失ったら困るような大事なデータは日ごろからバックアップをとっておくことを強くお勧めします。