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

标签：

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元ハミング符号について答えよ。

2元対称通信路を仮定し、限界距離 $\ell=1$ の復号では、受信語から距離1以内に符号語があればその符号語へ復号し、なければ復号失敗とする。また、受信語と検査行列から得るシンドロームを用いる復号法を考える。

(1-1) 符号長（あ）、情報記号数（い）、符号化率（う）、 $G=[I_4\mid(\text{え})]$ となる生成行列の右側部分を求めよ。また、一般の2元ハミング符号の最小距離（お）、冗長記号数が $m$ のときの符号長（か）、訂正可能誤り数（き）、受信語と（く）行列から得る（け）を答えよ。
(1-2) 同じ冗長記号数を持つハミング符号より高い符号化率の2元ブロック符号は、最小距離が3未満となる。その理由を説明せよ。
(1-3) ハミング符号の訂正能力を超える誤りが生じると必ず誤復号する理由を、検査行列の全列が非零かつ相異なることに基づいて説明せよ。

(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$ ）である。（a）、この（b）バックオフの名称、（c）、および再衝突を避けられる理由を答えよ。
(2-2) 10BASE-5の伝送速度は10 Mbit/s、最小フレーム長は64 byte、最大ホスト間距離は2.5 km、信号速度は $2\times10^5$ km/sである。最小フレーム長との関係から最大距離の妥当性を示せ。
(2-3) Pure ALOHAとCSMA/CDのスループットを、混雑度が低い場合と高い場合に分けて比較せよ。搬送波検知時間は無視でき、全フレーム長は等しい。

题目描述

本题前半考查(7,4) Hamming码的校验矩阵、最小距离及完备单错纠正；后半考查Ethernet二进制指数退避、碰撞检测所要求的最小帧长，以及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)

最小距離を3以上とするには、検査行列の各列が非零かつ互いに相異ならなければならない。長さ $m$ の非零列は $2^m-1$ 個しかなく、ハミング符号はすべてを使用している。同じ $m$ のまま符号化率を上げるには符号長を $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)​