情報通信工学前期中間

6/11 水 1限 60分

持ち込み

電卓

定規

No.1~8

No.2

$ H = \frac{1}{2} \log_2 \frac{1}{2} - \frac{1}{4} \log_2 \frac{1}{4} - \frac{1}{8} \log_2 \frac{1}{8} - \frac{1}{8} \log_2 \frac{1}{8}

$ = -\frac{1}{2} \log_2 2^{-1} - \frac{1}{4} \log_2 2^{-2} - \frac{1}{8} \log_2 2^{-3} - \frac{1}{8} \log_2 2^{-3}

$ = \frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \frac{3}{8} = \frac{4+4+3+3}{8} = \frac{14}{8} = 1.75 \text{ bit}

$ H_{max} = (-\frac{1}{4} \log_2 \frac{1}{4}) \times 4 = 2

$ H = -\frac{1}{8} \log_2 \frac{1}{8} - \frac{1}{4} \log_2 \frac{1}{4} - \frac{1}{8} \log_2 \frac{1}{8} - \frac{1}{2} \log_2 \frac{1}{2}

$ = -\frac{1}{8} \log_2 2^{-3} - \frac{1}{4} \log_2 2^{-2} - \frac{1}{8} \log_2 2^{-3} - \frac{1}{2} \log_2 2^{-1}

$ = \frac{3}{8} + \frac{2}{4} + \frac{3}{8} + \frac{1}{2} = \frac{3+4+3+4}{8} = \frac{14}{8} = 1.75 \text{ bit}

演習問題3. 情報源記号 A, B, C, D がそれぞれ確率 0.6, 0.25, 0.1, 0.05 で発生するときエントロピーを計算せよ。

$ H = -0.6 \log_2 0.6 - 0.25 \log_2 0.25 - 0.1 \log_2 0.1 - 0.05 \log_2 0.05

$ = -(0.6 \log_2 0.6 + 0.25 \log_2 0.25 + 0.1 \log_2 0.1 + 0.05 \log_2 0.05)

$ = 1.49047... \approx 1.49 \text{ bit}

追加

$ H = -p_i \log_2 p_i = -1 \log_2 1 - 0 \log_2 0 - 0 \log_2 0 - 0 \log_2 0 = 0 \text{ bit}

$ H = -p_i \log_2 p_i = -(\frac{1}{4} \log_2 \frac{1}{4}) \times 4 = -\log_2 2^{-2} = 2 \text{ bit} \text{ 最大値}

---

ハフマン符号

演習問題1. A, B, C, D をそれぞれ確率 0.6, 0.25, 0.1, 0.05 で発生する情報源についてハフマン符号を作成し、平均符号長を計算せよ。

演習問題2. 演習問題1 で作成したハフマン符号を使って次の符号列を復号せよ。

1101101001110101111000

C B A D B B D C A A

演習問題3. A, B, C, D をそれぞれ確率 0.35, 0.3, 0.2, 0.15 で発生する情報源についてハフマン符号を作成し、平均符号長を計算せよ。

---

高いレイヤーから

https://scrapbox.io/files/68483a89adfe54b578f5b7cc.png

---

Carrier Sense Multiple Access / Collision Detection（キャリアセンス多重アクセス／衝突検出）

誰も送信していない時

特定のMACアドレスへのデータをケーブルに送信

受信側は自分のアドレス出ない場合無視

利点：衝突を検出して再送する

欠点：台数が増えると回線の使用率が増える

1000BASE-T

1000 : 1000Mbps = 1Gbps

BASE : ベースバンド

T : ツイストペアケーブル

このケーブルは伝送距離100m

---

Ethernetフレーム

https://scrapbox.io/files/68483fbdd965bd9be8dbf67f.png

FCS：エラーチェック用

Ethernetプリアンブル

同期用の信号として使うため、フレームの先頭に置かれる

以下は間違い

フレーム内のデータ誤りを検出するためフレームの最後に置かれる

これはFCS

フレーム内のデータを取り出すためにデータの前後に置かれる

フレームの長さを調整するためにフレームの最後に置かれる

リピーター

中継のみを行う

物理層での動作

ブリッジ

宛先（MACアドレス）を見てそこに流す

L2; データリンク層 での動作

---

問題1 情報源記号 A, B, C, D がそれぞれ確率 0.6, 0.25, 0.1, 0.05 で発生する情報源を考える。

以下の問いに答えよ。

(1) この情報源のエントロピーを計算せよ。

$ -0.6 \log_2(0.6) -0.25 \log_2(0.25) -0.1\log_2(0.1) -0.05\log_2(0.05)

$ = 1.49\text{[bit]}

(2) この情報源記号に固定長符号を割り当てたときの平均符号長を求めよ。

$ L = 2

(3) この情報源記号に対してハフマン符号を作成せよ。

https://scrapbox.io/files/684857de1d638a3da5e6f963.png

$ A : 1

$ B : 01

$ C : 001

$ D : 000

(3)(4) (3)のハフマン符号の平均符号長を計算せよ。

$ L = 0.6 \times 1 + 0.25 \times 2 + 0.1 \times 3 + 0.05 \times 3 = 1.55

(5) (3)で求めたハフマン符号が瞬時符号であることを示せ。

全ての記号が葉ノードに対応している

それぞれの葉ノードが他の葉ノードの接頭語にならない

そもそも 瞬時符号でない＝いずれかの葉ノードが他の葉ノードの接頭語になっている

(例:｛0, 01, 011, 111｝では0が01,011の接頭語になっており、前から読み込んだ時に瞬時には復元できない)ということで、これを否定できたらいい。ということだと思う。

問題2. 図に示すLANにおいて、CSMA/CD方式によるパケット交換通信の原理を説明せよ。

1. 通信を行いたいコンピュータが、他のコンピュータの誰もデータを送信していないことを確認する

2. データを送信する

3. データを送信しながら、電圧を監視する。

4. 衝突が発生した場合は、ランダムな時間だけ待ったあと、再度送信する。

問題3. ネットワークを接続するための機器としてリピータ (Repeater) とブリッジ (Bridge) がある。

これらの機器の機能と違いについて説明せよ。

リピータは、入力された信号を増幅し、整えてから出力する。

ブリッジは、入力された信号が破損している場合、信号を出力させずに止める。

また、パケットの送り先を学習し、ネットワーク中継を制御する、

問題4. EthernetによるLANは最初10Mbpsの速度で始まり、今では1Gbpsの速度を達成している。

この高速化の要因について説明せよ。

同軸ケーブル　→　ツイストペアケーブル　→　光ファイバケーブルと、通信媒体が進化した。

問題5. 次の表はネットワークプログラムにおけるOSI参照モデルと実際のインターネットで使用されるプロトコルの関係を示したものである。空欄に適切な語句と説明を記入せよ。

https://scrapbox.io/files/68485b6a9b28d01f60f62e79.png