大阪大学情報科学研究科情報工学 2017年7月実施ネットワーク

标签：

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

(1)

検査行列

H= \begin{pmatrix} 1&1&1&0&1&0&0\\ 1&1&0&1&0&1&0\\ 1&0&1&1&0&0&1 \end{pmatrix}

を持つ2元ハミング符号について答えよ。

この符号の符号長は［あ］、情報記号数は［い］、符号化率は［う］である。生成行列は $G=[I_4\mid(\text{え})]$ である。

一般に2元ハミング符号の最小距離 $d$ は［お］、冗長記号数 $m$ に対する符号長は［か］である。検査行列の列ベクトルはすべて非零かつ相異なる。このため、同じ冗長記号数でハミング符号より符号化率が高い2元ブロック符号の最小距離は［お］より小さい（下線部(i)）。

2元対称通信路で限界距離 $\lfloor(d-1)/2\rfloor$ の復号を行うと、ビット誤りが［き］個以下なら正しく訂正でき、それより多ければ必ず誤復号する（下線部(ii)）。受信語と［く］行列から求める［け］を用いる復号法がよく知られている。限界距離 $t$ の復号では、受信語から距離 $t$ 以内に符号語があればそれに復号し、なければ復号失敗とする。

(1-1) 空欄［あ］～［け］を埋めよ。
(1-2) 下線部(i)が成り立つ理由を述べよ。
(1-3) 下線部(ii)が成り立つ理由を、検査行列の列ベクトルがすべて非零かつ相異なる性質を用いて説明せよ。

(2)

EthernetのCSMA/CDについて答えよ。各ホストは送信前に搬送波検知を行い、他ホストが送信中なら送信を遅らせ、そうでなければ直ちに送信する。送信中も衝突を検知し、衝突があれば送信を中止する。

(2-1) $n$ 回目の再送で $0\le r\le X$ の整数 $r$ を（a）に選び、最大往復伝搬遅延を $D$ として $t=(\text{c})$ だけ待つ。 $X=2^n-1$ （ $1\le n\le10$ ）、 $X=2^{10}-1$ （ $10<n\le15$ ）であり、15回を超える再送は行わない。（a）、この（b）バックオフの名称、（c）を埋めよ。また、連続衝突回数の増加に従って待ち時間 $t$ の平均を大きくする理由を答えよ。
(2-2) 10BASE-5は同軸ケーブルを用い、伝送速度は10 Mbit/s、最小フレーム長は64 byte、最大フレーム長は1518 byte、リピータ使用時の最大ホスト間距離は2.5 km、信号速度は $2\times10^5$ km/sである。最小フレーム長との関係から最大距離の妥当性を示せ。
(2-3) Pure ALOHAでは搬送波検知や衝突検知を行わず直ちにフレームを送出する。受信側はフレームを受信するとACKを返し、送信側は一定時間内にACKを受信しなければ再送する。Pure ALOHAとCSMA/CDのスループット（単位時間当たりの伝送成功フレーム数）を、混雑度が低い場合と高い場合に分けて比較せよ。搬送波検知時間は無視でき、全フレーム長は等しい。

Kai

(1)

(1-1)

\boxed{(\text{あ})=7},\qquad \boxed{(\text{い})=4},\qquad \boxed{(\text{う})=\frac47},

\boxed{ (\text{え})= \begin{pmatrix} 1&1&1\\ 1&1&0\\ 1&0&1\\ 0&1&1 \end{pmatrix}}.

また

\boxed{(\text{お})=3},\quad \boxed{(\text{か})=2^m-1},\quad \boxed{(\text{き})=1},\quad \boxed{(\text{く})=\text{検査}},\quad \boxed{(\text{け})=\text{シンドローム}}.

(1-2)

符号長を $n$ 、情報ビット数を $n-m$ とする。最小距離が3以上なら、各符号語を中心とする半径1のHamming球は互いに交わらないので

2^{n-m}(n+1)\le2^n,\qquad n\le2^m-1.

同じ $m$ に対し符号化率 $1-m/n$ は $n$ とともに増える。ハミング符号は $n=2^m-1$ で上限を達成するため、これより高い符号化率の符号は最小距離3以上を持てない。

(1-3)

$H$ の7列は、非零な3ビット列をすべて一度ずつ含む。送信語を $c$ 、重み2以上の誤りベクトルを $e$ とする。 $He^{\mathsf T}=0$ なら、受信語 $c+e\ne c$ を別の符号語として受理する。 $He^{\mathsf T}\ne0$ なら、そのシンドロームと等しい列に対応する単一誤り $e_j$ を訂正し、 $c+e+e_j$ を出力する。これが $c$ と等しければ $e=e_j$ となり、 $\operatorname{wt}(e)\ge2$ に反する。よって訂正能力を超える誤りでは必ず誤復号する。

(2)

(2-1)

\boxed{(a)=\text{一様ランダム（等確率）}},\qquad \boxed{(b)=\text{2進指数}},\qquad \boxed{(c)=rD}.

衝突回数に応じて待ち時間の候補数を増やすため、衝突した複数ホストが再び同じ待ち時間を選ぶ確率が下がる。

(2-2)

最大距離での片道伝搬遅延は

\tau=\frac{2.5}{2\times10^5}=12.5\ \mu\mathrm{s},

往復伝搬遅延は $2\tau=25\ \mu\mathrm{s}$ である。一方、最小フレームの送信時間は

T_{\min}=\frac{64\times8}{10\times10^6}=51.2\ \mu\mathrm{s}.

よって

\boxed{T_{\min}=51.2\ \mu\mathrm{s}>25\ \mu\mathrm{s}=2\tau},

となり、最遠端の衝突を送信終了前に検出できる。

(2-3)

混雑度が低い場合、衝突確率は小さく、搬送波検知時間も無視できるため、両方式のスループットはほぼ等しい。

混雑度が高い場合、Pure ALOHAは搬送波を確認せず送信する。一方、CSMA/CDは送信前に回線を確認し、衝突時には送信を早期中止する。したがってCSMA/CDの方がスループットは高い。

Author​

Description​

(1)​

(2)​

Kai​

(1)​

(1-1)​

(1-2)​

(1-3)​