東京大学 工学系研究科 電気系工学専攻 2019年度サンプル 問題3 情報理論

标签：

• 东京大学
• 条件熵
• 信道容量
• 信道编码

Author

祭音Myyura (Based on donguri0912's answer refined with GPT 6 Astra)

Description

$\mathcal F=\{0,1,2,3\}$ を入力・出力とする通信路 $\mathcal C$ を考える。入力 $x\in\mathcal F$ に対して出力 $y\in\mathcal F$ が得られる確率を

$$P(y\mid x)= \begin{cases} p(1-q),&y=x,\\ (1-p)q,&y=(x+1)\bmod4,\\ (1-p)(1-q),&y=(x+2)\bmod4,\\ pq,&y=(x+3)\bmod4 \end{cases}$$

と定める。$a\bmod b$ は $a$ を $b$ で割った余りを表し、$0\le p,q\le1$ とする。対数の底は $2$、通信路容量を $C$ とする。

(1) $q=1$ の場合の通信路線図を示せ。

(2) 入力を $x$ に固定したときの出力のエントロピーを $p,q$ の関数として求めよ。

(3) 通信路容量 $C(p,q)$ を求めよ。

(4) $C(p,q)$ の最小値と、それを与えるすべての $(p,q)$ を求め、その理由を2行程度で述べよ。

(5) $C(p,q)$ の最大値と、それを与えるすべての $(p,q)$ を求め、その理由を2行程度で述べよ。

(6) $p+q=1/2$ の制約の下で、$C(p,q)$ の最大値と、それを与えるすべての $(p,q)$ を導出せよ。

(7) $\mathcal A=\{a,b,c,d\}$ の1文字を $\mathcal F$ の2文字に符号化して送信する。$p=1/2,q=1$ のとき、誤りを最小化する符号の割当を一つ求めよ。ただし $a\mapsto00$ は固定する。求めた割当と通信路容量との関係を2行程度で述べよ。

题目描述

考虑输入和输出字母表均为 $\mathcal F=\{0,1,2,3\}$ 的信道。给定输入 $x$，输出 $x$、$(x+1)\bmod4$、$(x+2)\bmod4$、$(x+3)\bmod4$ 的概率依次为 $p(1-q)$、$(1-p)q$、$(1-p)(1-q)$、$pq$。其中 $0\le p,q\le1$，所有对数以 $2$ 为底。

(1) 画出 $q=1$ 时的信道转移图。

(2) 求固定输入 $x$ 时输出的熵。

(3) 求信道容量 $C(p,q)$。

(4) 求容量的最小值及所有对应的 $(p,q)$，用约两行解释原因。

(5) 求容量的最大值及所有对应的 $(p,q)$，用约两行解释原因。

(6) 在 $p+q=1/2$ 的约束下，推导容量的最大值及所有对应的 $(p,q)$。

(7) 将 $\mathcal A=\{a,b,c,d\}$ 的一个字母编码为 $\mathcal F$ 的两个符号。在 $p=1/2,q=1$、且 $a\mapsto00$ 固定的条件下，给出使错误概率最小的编码，并用约两行说明其与信道容量的关系。

Kai

二項エントロピー関数を $h(u)=-u\log_2u-(1-u)\log_2(1-u)$ とおき、$h(0)=h(1)=0$ とする。

(1)

$q=1$ なら、入力 $x$ に対して $(x+1)\bmod4$ が確率 $1-p$、$(x+3)\bmod4$ が確率 $p$ で出力される。

(2)

各入力について、出力確率は $p,1-p$ と $q,1-q$ の積を並べ替えたものである。したがって

$$\begin{aligned} H(Y\mid X=x) &=-\sum_yP(y\mid x)\log_2P(y\mid x)\\ &=-p\log_2p-(1-p)\log_2(1-p) -q\log_2q-(1-q)\log_2(1-q)\\ &=\boxed{h(p)+h(q)}. \end{aligned}$$

この値は $x$ に依存しない。

(3)

任意の入力分布について

$$I(X;Y)=H(Y)-H(Y\mid X)=H(Y)-h(p)-h(q) \le2-h(p)-h(q)$$

である。遷移行列の各列の和も $1$ なので、一様な入力 $P_X(x)=1/4$ に対して出力も一様となり、$H(Y)=2$ が達成される。よって

$$\boxed{C(p,q)=2-h(p)-h(q)\quad\text{bit/記号}}.$$

(4)

$h(u)\le1$ であり、等号は $u=1/2$ のときに限る。したがって

$$\boxed{\min C(p,q)=0,\qquad (p,q)=(1/2,1/2)}.$$

このとき、どの入力に対しても四つの出力が確率 $1/4$ で現れ、入力と出力が独立になるため、入力についての情報を伝えられない。

(5)

$h(u)\ge0$ であり、等号は $u=0,1$ のときに限る。したがって

$$\boxed{\max C(p,q)=2,\qquad(p,q)\in\{(0,0),(0,1),(1,0),(1,1)\}}.$$

いずれも出力は入力を一定量だけ巡回シフトした値となり、入力と出力が一対一に対応する。一様な四元入力の $2$ bit をすべて伝えられる。

(6)

$q=1/2-p$、$0\le p\le1/2$ とおく。容量の最大化は

$$g(p)=h(p)+h(1/2-p)$$

の最小化に等しい。$0<p<1/2$ で

$$h''(u)=-\frac{1}{u(1-u)\ln2}<0, \qquad g''(p)=h''(p)+h''(1/2-p)<0$$

であり、$g$ は厳密に凹である。両端で $g(0)=g(1/2)=1$ なので、内点では $g(p)>1$。したがって

$$\boxed{\max_{p+q=1/2}C(p,q)=1,\qquad (p,q)=(0,1/2),(1/2,0)}.$$

(7)

$q=1$ のとき出力の偶奇は必ず入力と反対になる。そこで、入力の偶奇の組を四つの文字に対応させる。

文字	符号語	取り得る受信語
$a$	$00$	$11,13,31,33$
$b$	$01$	$10,12,30,32$
$c$	$10$	$01,03,21,23$
$d$	$11$	$00,02,20,22$

受信語の集合は互いに交わらず、全 $16$ 通りを尽くす。したがって、受信語の偶奇から送信文字を一意に復元でき、誤り確率は最小値 $0$ となる。

この符号の情報速度は $R=\log_2 4/2=1$ bit/記号であり、$C(1/2,1)=1$ bit/記号に一致する。2回の通信路使用で4文字を誤りなく識別できる。

Reference

• 東京大学 電気系工学専攻：試験科目・サンプル問題の案内
• 2019年度サンプル問題の公開保存版：問題3、日本語 PDF 9ページ
• donguri0912：東大院電気系の過去問解説・2019年問題3（問7）