情報理論・符号理論

確率変数 $X$ は $\{1,2,3,4,5,6\}$ に値をとり、その確率分布は次のとおりである。
$$P(X=1)=P(X=2)=P(X=3)=\frac{1}{4},P(X=4)=\frac{1}{8},P(X=5)=P(X=6)=\frac{1}{16}$$
$X$ のエントロピー
$$H(X)=-\sum _{x=1}^{6}P(X=x){\log }_{2}P(X=x)$$
を求めよ。

$1$ から $8$ までの整数が $1$ つずつ書かれた正八面体のさいころがある。どの目も同じ確率 $\frac{1}{8}$ で出るものとする。このさいころを $1$ 回投げ、出た目の数を $2$ 進法で表したときの桁数を $X$ とする（たとえば、目が $5$ のときは $5=101_{(2)}$ なので $X=3$ である）。

確率変数 $X$ のエントロピー
$$H(X)=-\sum _{x}P(X=x){\log }_{2}P(X=x)$$
を求めよ（単位はビット）。

確率変数 $X$ は $\{1,2,3,4,5\}$ に値をとり、その確率分布は次の表で与えられる。

$$\begin{array}{cccccc}x& 1& 2& 3& 4& 5\\ P(X=x)& \frac{1}{2}& \frac{1}{4}& \frac{1}{8}& \frac{1}{8}& 0\end{array}$$

$X$ のエントロピー $$H(X)=-\sum _{x}P(X=x){\log }_{2}P(X=x)$$ を求めよ。ただし、$0{\log }_{2}0=0$ と約束する。

5 個の情報源記号 $a_1,a_2,a_3,a_4,a_5$ に、符号アルファベット $\{0,1\}$ の 2 元語頭符号（瞬時符号）を割り当てる。各符号語の長さを
$$l_1=1,l_2=3,l_3=3,l_4=3,l_5=l$$
とするとき、このような 2 元語頭符号が存在するような正の整数 $l$ のうち、最小のものを求めよ。

符号アルファベットを $\{0,1,2\}$ とする 3 元符号を考える。符号長 $1$ の符号語が $2$ 個、符号長 $2$ の符号語が $2$ 個、符号長 $3$ の符号語が $k$ 個からなる語頭符号（瞬時符号）が存在するような正の整数 $k$ の最大値を求めよ。

記号 $0,1$ を使う 2 元符号を考える。長さ $2$ の符号語が $2$ 個、長さ $3$ の符号語が $1$ 個、長さ $4$ の符号語が $k$ 個からなる語頭符号（瞬時符号）を作りたい。ただし、どの 2 つの符号語も互いに異なるものとする。このような語頭符号が存在する 0 以上の整数 $k$ のうち、最大のものを求めよ。

3 元体 ${\mathbb{F}}_3=\{0,1,2\}$（演算は $3$ を法とする）上の符号長 $4$ の線形符号 $C$ を、生成行列
$$G=\left(\begin{array}{cccc}1& 0& 2& 1\\ 0& 1& 1& 0\end{array}\right)$$
によって $C=\{\mathbf{u}G\mid \mathbf{u}\in {\mathbb{F}}_3^2\}$ と定める（$\mathbf{u}$ は行ベクトル）。ベクトルのハミング重みを $0$ でない成分の個数とし、$C$ の最小距離 $d$ を $C$ の $0$ でない符号語のハミング重みの最小値とする。また、ハミング重みがちょうど $d$ である符号語の個数を $A_d$ とする。$d$ と $A_d$ をこの順に組 $(d,A_d)$ で求めよ。

3 元体 ${\mathbb{F}}_3=\{0,1,2\}$（演算は $3$ を法とする）上で、符号長 $4$ の線形符号 $C$ を生成行列
$$G=\left(\begin{array}{cccc}1& 0& 2& 1\\ 0& 1& 1& 0\end{array}\right)$$
で定める。すなわち $C=\{\mathbf{u}G\mid \mathbf{u}=(a,b)\in {\mathbb{F}}_3^2\}$ とする。符号語 $\mathbf{c}$ のハミング重みを $0$ でない成分の個数とし、$C$ の最小距離 $d$ を $C$ の $0$ でない符号語の重みの最小値とする。また、重みがちょうど $d$ である符号語の個数を $A_d$ とする。$d$ と $A_d$ をこの順に組 $(d,A_d)$ で求めよ。

3 元体 ${\mathbb{F}}_3=\{0,1,2\}$（演算は $3$ を法とする）上の符号長 $4$ の線形符号 $C$ を、生成行列
$$G=\left(\begin{array}{cccc}1& 0& 1& 2\\ 0& 1& 1& 0\end{array}\right)$$
によって $C=\{\mathbf{u}G\mid \mathbf{u}=(u_1,u_2)\in {\mathbb{F}}_3^2\}$ と定める。符号語のハミング重みを $0$ でない成分の個数とし、$C$ の最小距離 $d$ を $0$ でない符号語の重みの最小値とする。$C$ の最小距離 $d$ と、重みがちょうど $d$ である符号語の個数 $A_d$ を、組 $(d,A_d)$ の形でこの順に求めよ。

確率変数 $X$ は $\{0,1\}$ に、確率変数 $Y$ は $\{0,1,2\}$ に値をとり、同時分布 $P(X=x,Y=y)$ が次の表で与えられている。
$$\begin{array}{cccc}& Y=0& Y=1& Y=2\\ X=0& \frac{1}{4}& \frac{1}{4}& 0\\ X=1& \frac{1}{8}& \frac{1}{8}& \frac{1}{4}\end{array}$$
$X$ を与えたときの $Y$ の条件付きエントロピー $H(Y\mid X)$ を求めよ。ただし、対数の底は $2$ とし、$0{\log }_{2}0=0$ と約束する。

確率変数 $X$ は $\{0,1\}$ に、確率変数 $Y$ は $\{0,1,2\}$ に値をとり、同時分布 $P(X=x,Y=y)$ が次の表で与えられている。

エントロピーの対数の底は $2$ とし、$0{\log }_{2}0=0$ と約束する。同時エントロピー $H(X,Y)$ と条件付きエントロピー $H(Y\mid X)$ を、この順に組 $(H(X,Y),H(Y\mid X))$ の形で求めよ。

確率変数 $X\in \{0,1\}$ と $Y\in \{0,1,2\}$ の同時分布 $P(X=x,Y=y)$ が次の表で与えられている。
$$\begin{array}{cccc}& Y=0& Y=1& Y=2\\ X=0& \frac{1}{4}& \frac{1}{4}& 0\\ X=1& \frac{1}{8}& \frac{1}{8}& \frac{1}{4}\end{array}$$
対数の底を $2$ とし、$0{\log }_{2}0=0$ と約束する。同時エントロピー $H(X,Y)$ と条件付きエントロピー $H(Y\mid X)$ を、この順に組で求めよ。

情報源の記号 $a,b,c,d$ が、それぞれ確率
$$\frac{2}{5},\frac{3}{10},\frac{1}{5},\frac{1}{10}$$
で出力される。この情報源に対して 2 元ハフマン符号（符号記号は $0,1$）を構成するとき、1 記号あたりの平均符号長 $\bar{L}={\sum }_i{p}_i{l}_i$ を求めよ。

情報源の記号 $a_1,a_2,a_3,a_4,a_5$ が、それぞれ確率
$$\frac{7}{20},\frac{1}{4},\frac{1}{5},\frac{1}{10},\frac{1}{10}$$
で独立に出力される無記憶情報源を考える。この情報源に対して 2 元（記号 $0,1$）のハフマン符号を構成するとき、1 記号あたりの平均符号長 $\bar{L}={\sum }_i{p}_i{l}_i$ を求めよ。ただし $p_i$ は $a_i$ の確率、$l_i$ は $a_i$ に割り当てられた符号語の長さとする。

情報源の記号 $a_1,a_2,a_3,a_4$ が、それぞれ確率
$$\frac{9}{20},\frac{1}{4},\frac{1}{5},\frac{1}{10}$$
で出力される。この情報源に対して $2$ 元ハフマン符号（符号アルファベット $\{0,1\}$）を構成するとき、$1$ 記号あたりの平均符号長 $\bar{L}={\sum }_i{p}_i{l}_i$ を求めよ。ただし $p_i$ は $a_i$ の確率、$l_i$ は $a_i$ の符号語の長さである。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上の符号長 $6$ の線形符号 $C$ が、組織形の生成行列
$$G=(I_3\mid P)=\left(\begin{array}{cccccc}1& 0& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 1\\ 0& 0& 1& 1& 0& 1\end{array}\right)$$
で与えられている。$C$ の検査行列 $H=(-P^{\mathsf{T}}\mid I_3)$ を求め、$H$ の列の一次独立性を調べることで、$C$ の最小距離 $d$ と、ハミング重みが $d$ である符号語の個数 $A_d$ を求めよ。答えは $(d,A_d)$ の順の組で答えよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上の符号長 $6$ の線形符号 $C$ を、検査行列
$$H=\left(\begin{array}{cccccc}1& 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1\end{array}\right)$$
を用いて $C=\{\mathbf{x}\in {\mathbb{F}}_2^6\mid H{\mathbf{x}}^{\mathsf{T}}=0\}$ と定める。$C$ の次元 $k$、最小距離 $d$、ハミング重みが $d$ である符号語の個数 $A_d$ を、組 $(k,d,A_d)$ の形でこの順に求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上の符号長 $6$ の線形符号 $C$ を、検査行列
$$H=\left(\begin{array}{cccccc}1& 1& 0& 1& 0& 0\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 1& 0& 0& 1\end{array}\right)$$
によって $C=\{\mathbf{x}\in {\mathbb{F}}_2^6\mid H{\mathbf{x}}^{\mathsf{T}}=0\}$ と定める。$C$ の次元 $k$、最小距離 $d$、重み $d$ の符号語の個数 $A_d$ を求め、組 $(k,d,A_d)$ の形で答えよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成行列
$$G=\left(\begin{array}{ccccc}1& 1& 1& 0& 0\\ 0& 0& 1& 1& 1\end{array}\right)$$
で定まる符号長 $5$ の線形符号 $C$ を考える。$C$ の最小距離を $d$ とし、$t=\lfloor \frac{d-1}{2}\rfloor$ とする。

$C$ の符号語を、各ビットが互いに独立に確率 $p=\frac{1}{10}$ で反転する（$0$ と $1$ が入れ替わる）2 元対称通信路で送信し、受信語を最小距離復号する。ただし、送信語に生じた誤りの個数が $t$ 個以下のときは正しく復号され、$t+1$ 個以上のときは正しく復号されないものとする。

正しく復号される確率を求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成行列
$$G=\left(\begin{array}{ccccc}1& 1& 1& 1& 1\end{array}\right)$$
で定まる符号長 $5$ の線形符号 $C$ を考える。$C$ の符号語を、ビット誤り確率 $p=\frac{1}{10}$ の 2 元対称通信路で送る。各ビットの誤りは互いに独立に起こるものとする。受信側では最小距離復号（受信語にハミング距離が最も近い符号語に復号する）を行う。

送った符号語が正しく復号される確率を、既約分数で求めよ。

符号長 $5$ の 2 元符号
$$C=\{00000,11100,00111,11011\}$$
を考える。$C$ の符号語を、ビット誤り確率 $p=\frac{1}{10}$ の 2 元対称通信路で送る。各ビットは互いに独立に確率 $p$ で反転する。

受信側では次のように復号する。$C$ の最小距離を $d$ とし、$t=\lfloor \frac{d-1}{2}\rfloor$ とおく。受信語とのハミング距離が $t$ 以下の符号語があれば、その符号語に復号する。そのような符号語がなければ、復号失敗とする。

送った符号語が正しく復号される確率を求めよ。

三元体 ${\mathbb{F}}_3=\{0,1,2\}$（$3$ を法とする演算）上で考える。$x^4-1=(x^2+1)(x^2-1)$ より $g(x)=x^2+1$ は $x^4-1$ を割り切るので、$g(x)$ を生成多項式とする符号長 $4$、次元 $2$ の巡回符号 $C$ が定まる。ここで語 $(c_0,c_1,c_2,c_3)$ を多項式 $c(x)=c_0+c_{1}x+c_2{x}^2+c_3{x}^3$ と同一視する。

情報 $(m_0,m_1)$ を $m(x)=m_0+m_{1}x$ で表し、次の組織符号化を行う：$x^{2}m(x)$ を $g(x)$ で割った余りを $r(x)$ として、符号語を
$$c(x)=x^{2}m(x)-r(x)$$
とする。

情報 $(m_0,m_1)=(1,2)$ を符号化したときの符号語 $(c_0,c_1,c_2,c_3)$ を求めよ。各成分は $0,1,2$ のいずれかで答えること。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成多項式
$$g(x)=x^3+x^2+1$$
で定まる符号長 $7$、次元 $4$ の巡回符号 $C$ を考える（$g(x)$ は $x^7-1$ を割り切る）。

語 $c=(c_0,c_1,\dots ,c_6)\in {\mathbb{F}}_2^7$ は多項式 $c(x)=c_0+c_{1}x+\cdots +c_6{x}^6$ と同一視する。情報 $m=(m_0,m_1,m_2,m_3)$ は $m(x)=m_0+m_{1}x+m_2{x}^2+m_3{x}^3$ と同一視し、次のように組織符号化する。

• $x^{3}m(x)$ を $g(x)$ で割った余りを $r(x)=r_0+r_{1}x+r_2{x}^2$ とする。
• 符号語を $c(x)=x^{3}m(x)+r(x)$ とする。すなわち $c=(r_0,r_1,r_2,m_0,m_1,m_2,m_3)$ である。

情報 $m=(1,1,0,1)$ を符号化して得られる符号語 $c=(c_0,c_1,c_2,c_3,c_4,c_5,c_6)$ を求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成多項式
$$g(x)=x^3+x^2+1$$
で定まる符号長 $7$、次元 $4$ の巡回符号 $C$ を考える（$x^7+1=(x+1)(x^3+x+1)(x^3+x^2+1)$ なので、$g(x)$ は $x^7-1$ を割り切る）。

情報語 $m=(m_0,m_1,m_2,m_3)=(1,0,0,1)$ を、情報多項式 $m(x)=m_0+m_{1}x+m_2{x}^2+m_3{x}^3=1+x^3$ で表す。組織符号化では、$x^{3}m(x)$ を $g(x)$ で割った余りを $r(x)$（次数 $2$ 以下）として、符号多項式を $c(x)=r(x)+x^{3}m(x)$ と定める。

このときの余り $r(x)$ を求めよ。ただし、係数の計算はすべて $2$ を法として行う。

確率変数 $X,Z$ は互いに独立で、それぞれ $$P(X=0)=P(X=1)=\frac{1}{2},P(Z=0)=P(Z=1)=\frac{1}{2}$$ に従う。積 $Y=XZ$ とおく。$X$ と $Y$ の相互情報量 $I(X;Y)$ を求めよ。ただし、エントロピーの対数の底は $2$ とする。

表と裏が等しい確率 $\frac{1}{2}$ で出る硬貨を $2$ 回投げる。$2$ 回の結果は互いに独立である。$1$ 回目に表が出れば $X=1$、裏が出れば $X=0$ とし、$2$ 回のうち表が出た回数を $Y$ とする（$Y\in \{0,1,2\}$）。相互情報量 $I(X;Y)$ を求めよ。ただし、エントロピーの対数の底は $2$ とする（単位はビット）。

確率変数 $X$ は $\{0,1\}$ に値をとり、$P(X=0)=P(X=1)=\frac{1}{2}$ に従う。確率変数 $Z$ は $X$ と独立で、$\{0,1,2\}$ に値をとり、$P(Z=0)=P(Z=1)=P(Z=2)=\frac{1}{3}$ に従う。$Y=X+Z$ とおくとき、相互情報量 $I(X;Y)$ を求めよ。ただし、エントロピーの対数の底は $2$ とする。

情報源 $X$ は 4 個の記号 $a_1,a_2,a_3,a_4$ を、それぞれ次の確率で出力する。$$P(a_1)=\frac{2}{5},P(a_2)=\frac{1}{4},P(a_3)=\frac{1}{5},P(a_4)=\frac{3}{20}$$ 符号記号を $\{0,1,2\}$ とする 3 元の語頭符号で $X$ の各記号を 1 個ずつ符号化するとき、1 記号あたりの平均符号長 $\bar{L}={\sum }_{i=1}^{4}P(a_i)l_i$（$l_i$ は $a_i$ の符号語の長さ）の最小値を求めよ。

情報源 $X$ は 4 個の記号 $a_1,a_2,a_3,a_4$ を、それぞれ次の確率で出力する。$$P(a_1)=\frac{2}{5},P(a_2)=\frac{3}{10},P(a_3)=\frac{1}{5},P(a_4)=\frac{1}{10}$$この情報源を、符号記号 $\{0,1,2\}$ を用いる 3 元語頭符号で 1 記号ずつ符号化する。1 記号あたりの平均符号長 $\bar{L}={\sum }_{i=1}^{4}P(a_i)l_i$（$l_i$ は $a_i$ の符号語の長さ）の最小値を、3 元ハフマン符号を構成して求めよ。

情報源 $X$ は 4 個の記号 $a_1,a_2,a_3,a_4$ を、それぞれ次の確率で出力する。$$P(a_1)=\frac{2}{5},P(a_2)=\frac{3}{10},P(a_3)=\frac{1}{5},P(a_4)=\frac{1}{10}$$符号記号を $\{0,1,2\}$ とする 3 元語頭符号で $X$ の各記号を符号化するとき、1 記号あたりの平均符号長 $\bar{L}={\sum }_{i=1}^{4}P(a_i)l_i$（$l_i$ は $a_i$ の符号語の長さ）の最小値を求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$（演算は $2$ を法とする）上で、検査行列
$$H=\left(\begin{array}{ccccccc}0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 1\\ 1& 0& 1& 0& 1& 0& 1\end{array}\right)$$
で定まる符号長 $7$ のハミング符号 $C=\{\mathbf{x}\in {\mathbb{F}}_2^7\mid H{\mathbf{x}}^{\mathsf{T}}=0\}$ を考える。$H$ の第 $j$ 列は、$j$ を 2 進法で表したときの各桁を上から $4$ の位・$2$ の位・$1$ の位の順に並べたものである。

ある符号語を送信したところ、ちょうど $1$ か所のビットだけが誤って
$$\mathbf{y}=(0,1,1,1,1,1,0)$$
が受信された。誤りが起きた位置（左から数えて第何成分か）を求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、$3\times 7$ 行列
$$H=\left(\begin{array}{ccccccc}0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 1\\ 1& 0& 1& 0& 1& 0& 1\end{array}\right)$$
を検査行列とする符号長 $7$ のハミング符号 $C=\{\mathbf{x}\in {\mathbb{F}}_2^7\mid H{\mathbf{x}}^{\mathsf{T}}=0\}$ を考える。$H$ の第 $j$ 列 $(j=1,2,\dots ,7)$ は、上から順に $j$ を 2 進数で表したときの $2^2,2^1,2^0$ の位の数字を並べたものである。

ある符号語 $\mathbf{c}=(c_1,c_2,\dots ,c_7)\in C$ を送信したところ、通信路で高々 $1$ か所の成分が反転し、受信語
$$\mathbf{y}=(1,0,1,1,0,0,0)$$
を受け取った。シンドローム $H{\mathbf{y}}^{\mathsf{T}}$ を用いて誤りを訂正し、送信された符号語 $\mathbf{c}$ を $(c_1,c_2,\dots ,c_7)$ の形で求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、検査行列
$$H=\left(\begin{array}{ccccccc}0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 1\\ 1& 0& 1& 0& 1& 0& 1\end{array}\right)$$
で定まる符号長 $7$ のハミング符号 $C=\{\mathbf{x}\in {\mathbb{F}}_2^7\mid H{\mathbf{x}}^{\mathsf{T}}=0\}$ を考える。$H$ の第 $j$ 列 $(j=1,2,\dots ,7)$ は、上から読むと $j$ を 2 進法で表した 3 桁の数になっている。

ある符号語を送信したところ、ちょうど 1 か所のビットが反転して
$$\mathbf{y}=(1,1,0,1,1,0,1)$$
を受信した。シンドローム $H{\mathbf{y}}^{\mathsf{T}}$ を計算して、誤りが生じた位置（左から何番目の成分か）を求めよ。

確率変数 $X,W,Z$ は互いに独立とします。$X$ と $W$ はそれぞれ $P(X=0)=P(X=1)=\frac{1}{2}$、$P(W=0)=P(W=1)=\frac{1}{2}$ に従います。$Z$ は「スイッチ」を表し、$P(Z=1)=\frac{1}{3}$、$P(Z=0)=\frac{2}{3}$ に従います。確率変数 $Y$ を
$$Y=\{\begin{array}{ll}X& (Z=1)\\ W& (Z=0)\end{array}$$
で定めます。つまり、スイッチが入っているときは $X$ がそのまま $Y$ に伝わり、切れているときは $X$ と無関係な $W$ が $Y$ になります。

条件付き相互情報量 $I(X;Y\mid Z)=H(X\mid Z)-H(X\mid Y,Z)$ を求めてください。ただし、エントロピーの対数の底は $2$ とします（単位はビット）。

確率変数 $X,W,Z$ は互いに独立とする。$X$ と $W$ はそれぞれ $\{0,1,2,3\}$ 上の一様分布に従う。$Z$ は $P(Z=0)=\frac{1}{4}$, $P(Z=1)=\frac{3}{4}$ に従う。確率変数 $Y$ を次のように定める。
$$Y=\{\begin{array}{ll}W& (Z=0)\\ X\text{ を }2\text{ で割った余り}& (Z=1)\end{array}$$
このとき、条件付き相互情報量 $I(X;Y\mid Z)=H(X\mid Z)-H(X\mid Y,Z)$ を求めよ。ただし、エントロピーの対数の底は $2$ とする（単位はビット）。

入力・出力のアルファベットがともに $\{0,1\}$ の 2 元対称通信路を考える。この通信路では、送った記号が確率 $\frac{1}{8}$ で反転し（$0$ が $1$ に、$1$ が $0$ になる）、確率 $\frac{7}{8}$ で正しく届く。各回の伝送は互いに独立とする。この通信路の通信路容量 $C$（単位はビット／通信路 1 回の使用）を求めよ。ただし、対数の底は $2$ とし、答えは ${\log }_{2}7$ を用いて表せ。

入力・出力のアルファベットがともに $\{0,1\}$ である 2 元対称通信路を考える。この通信路では、入力した 1 ビットが確率 $\frac{1}{8}$ で反転して出力され、確率 $\frac{7}{8}$ でそのまま出力される。この通信路の通信路容量 $C$（単位はビット／通信路 1 回の使用、対数の底は 2）を求めよ。答えは ${\log }_{2}7$ を用いた式で表せ。

入力・出力のアルファベットがともに $\{0,1\}$ の 2 元対称通信路（BSC）を考える。この通信路では、送った記号が確率 $\frac{1}{8}$ で反転して受信され、確率 $\frac{7}{8}$ でそのまま受信される。各記号の反転は互いに独立に起こる（無記憶）。この通信路の通信路容量 $C$（単位はビット／通信路使用 1 回）を求めよ。対数の底は $2$ とし、答えは ${\log }_{2}7$ を用いた式で表せ。

入力アルファベット $\{0,1\}$、出力アルファベット $\{0,1,\mathrm{e}\}$ の離散無記憶通信路を考える。ここで $\mathrm{e}$ は「消失」を表す記号である。入力 $X$ と出力 $Y$ の条件付き確率は次の通りとする。
$$P(Y=0\mid X=0)=\frac{1}{2},P(Y=\mathrm{e}\mid X=0)=\frac{1}{2},P(Y=1\mid X=0)=0,$$
$$P(Y=1\mid X=1)=\frac{1}{2},P(Y=0\mid X=1)=\frac{1}{2},P(Y=\mathrm{e}\mid X=1)=0.$$
つまり、$0$ を送ると半分の確率で消失し、$1$ を送ると半分の確率で $0$ に化ける。入力分布を $P(X=1)=q$（$0\le q\le 1$）として、この通信路の通信路容量 $C={\max }_{P_X}I(X;Y)$ を求めよ。ただし、エントロピー・相互情報量の対数の底は $2$ とし、単位はビットとする。

入力アルファベット $\{0,1\}$、出力アルファベット $\{0,1,2\}$ の離散無記憶通信路を考える。入力 $X$ に対して、$X$ と独立な雑音 $Z$ が $P(Z=0)=P(Z=1)=\frac{1}{2}$ で生じ、出力は通常の整数の和
$$Y=X+Z$$
で与えられる。入力分布を $P(X=1)=q$ $(0\le q\le 1)$ とする。この通信路の通信路容量 $C={\max }_{P_X}I(X;Y)$ を求めよ。ただし、対数の底は $2$ とし、単位はビットとする。

入力アルファベットが $\{0,1\}$、出力アルファベットが $\{0,1,2\}$ の離散無記憶通信路を考える。入力 $X$ と出力 $Y$ の条件付き確率は次のとおりである。
$$P(Y=0\mid X=0)=\frac{1}{2},P(Y=1\mid X=0)=\frac{1}{4},P(Y=2\mid X=0)=\frac{1}{4},$$
$$P(Y=0\mid X=1)=\frac{1}{4},P(Y=1\mid X=1)=\frac{1}{4},P(Y=2\mid X=1)=\frac{1}{2}.$$
入力分布を $P(X=1)=q$, $P(X=0)=1-q$（$0\le q\le 1$）とし、相互情報量 $I(X;Y)$ を $q$ の関数として表して最大化することで、この通信路の通信路容量 $C={\max }_{P_X}I(X;Y)$ を求めよ。ただし、対数の底は $2$ とする（単位はビット）。

$\{0,1\}$ に値をとる確率変数 $X,Y$ の同時分布が次で与えられている。
$$P(X=0,Y=0)=\frac{1}{2},P(X=0,Y=1)=\frac{1}{4},P(X=1,Y=0)=0,P(X=1,Y=1)=\frac{1}{4}$$
対数の底を $2$ とするとき、相互情報量 $I(X;Y)$ を求めよ。ただし $0{\log }_{2}0=0$ とする。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上の符号長 $7$ の線形符号 $C$ を、生成行列
$$G=\left(\begin{array}{ccccccc}1& 0& 0& 1& 1& 0& 0\\ 0& 1& 0& 0& 1& 1& 1\\ 0& 0& 1& 1& 0& 1& 1\end{array}\right)$$
の行ベクトルが張る部分空間 $C=\{\mathbf{u}G\mid \mathbf{u}\in {\mathbb{F}}_2^3\}$ と定める。$C$ の最小距離（ハミング距離の最小値）を $d$、ハミング重みがちょうど $d$ である $C$ の符号語の個数を $A_d$ とする。組 $(d,A_d)$ をこの順に求めよ。

入力・出力のアルファベットがともに $\{0,1\}$ で、ビット反転確率が $\frac{1}{4}$ の 2 元対称通信路（BSC）を考える。この通信路を 2 つ直列につなぎ、1 つ目の通信路の出力をそのまま 2 つ目の通信路の入力とする。2 つの通信路でのビット反転は互いに独立に起こるものとする。

1 つ目の通信路の入力 $X$ から 2 つ目の通信路の出力 $Z$ までを 1 つの通信路とみなしたとき、その通信路容量（1 回の使用あたり、単位はビット）を求めよ。ただし、対数の底は $2$ とする。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成多項式
$$g(x)=x^3+x+1$$
で定まる符号長 $7$ の巡回符号 $C$ を考える。すなわち、$C$ は ${\mathbb{F}}_2[x]$ の次数 $6$ 以下の多項式のうち $g(x)$ で割り切れるものの係数ベクトル全体である。

$C$ の符号語を $1$ つ選び、各ビットが互いに独立に確率 $p=\frac{1}{10}$ で反転する二元対称通信路で送る。受信側は、受信語とのハミング距離が最小となる符号語に復号する。復号結果が送信した符号語に一致する確率を求めよ。

入力アルファベット・出力アルファベットがともに $\{0,1,2,3\}$ の離散無記憶通信路を考える。入力 $X=x$ に対して、出力 $Y$ は次のように定まる（和と差は $4$ を法として計算する）。
$$P(Y=x\mid X=x)=\frac{1}{2},P(Y=x+1\mid X=x)=\frac{1}{4},P(Y=x-1\mid X=x)=\frac{1}{4}$$
すなわち、入力の記号はそのまま届くか、「隣の」記号にずれて届く（たとえば $X=0$ のとき $Y$ は $0,1,3$ のいずれか）。

この通信路の通信路容量
$$C=\underset{P_X}{\max }I(X;Y)$$
を求めよ。ただし、最大は入力 $X$ の確率分布 $P_X$ 全体でとり、相互情報量の対数の底は $2$ とする（単位はビット）。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上の符号長 $6$ の線形符号 $C$ を、生成行列
$$G=\left(\begin{array}{cccccc}1& 0& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 1\\ 0& 0& 1& 1& 0& 1\end{array}\right)$$
の行ベクトルが張る ${\mathbb{F}}_2^6$ の部分空間として定める（演算は $2$ を法とする）。

$C$ の最小距離を $d$ とし、$C$ の符号語のうちハミング重み（$1$ である成分の個数）がちょうど $d$ であるものの個数を $A$ とする。組 $(d,A)$ を求めよ。

入力アルファベット・出力アルファベットがともに $\{0,1,2\}$ の離散無記憶通信路を考える。入力 $X$ と出力 $Y$ の条件付き確率は、各 $x\in \{0,1,2\}$ について
$$P(Y=x\mid X=x)=\frac{1}{2},P(Y=y\mid X=x)=\frac{1}{4}(y\ne x)$$
で与えられる。すなわち、送った記号は確率 $\frac{1}{2}$ で正しく届き、残りの $2$ つの記号のそれぞれに確率 $\frac{1}{4}$ ずつで変わる。

この通信路の通信路容量 $C=\underset{P_X}{\max }I(X;Y)$（単位はビット、すなわち対数の底は $2$）を求めよ。ここで最大値は入力 $X$ の確率分布 $P_X$ 全体にわたってとる。

情報源の記号 $a_1,a_2,a_3,a_4,a_5,a_6$ が、それぞれ確率
$$\frac{3}{10},\frac{1}{5},\frac{3}{20},\frac{3}{20},\frac{1}{10},\frac{1}{10}$$
で互いに独立に発生する無記憶情報源がある。この情報源の $1$ 記号ずつに $\{0,1\}$ 上の $2$ 元ハフマン符号を構成するとき、$1$ 記号あたりの平均符号長を求めよ。

$\mathcal{X},\mathcal{Y}$ を空でない有限集合とし、$X$ を $\mathcal{X}$ に値をとる確率変数、$f:\mathcal{X}\to \mathcal{Y}$ を写像として $Y=f(X)$ とおく。$y\in \mathcal{Y}$ に対して $f^{-1}(y)=\{x\in \mathcal{X}\mid f(x)=y\}$ とし、
$$k=\underset{y\in f(\mathcal{X})}{\max }|f^{-1}(y)|$$
（$f$ の像の各点の逆像の元の個数の最大値）とおく。

エントロピーの対数の底は $2$ とし、$0{\log }_{2}0=0$ と約束する。条件付きエントロピーは
$$H(X\mid Y)=\sum _{y:P(Y=y)>0}P(Y=y)H(X\mid Y=y)$$
（$H(X\mid Y=y)$ は条件付き分布 $P(X=\cdot \mid Y=y)$ のエントロピー）で定め、$H(Y\mid X)$ も同様に定める。

このとき
$$H(X)\le H(f(X))+{\log }_{2}k$$
が成り立つことを証明せよ。

なお、連鎖律 $H(X,Y)=H(X)+H(Y\mid X)=H(Y)+H(X\mid Y)$ と、$n$ 個の元からなる有限集合上の確率分布のエントロピーは $0$ 以上 ${\log }_{2}n$ 以下であること、は用いてよい。

入力アルファベットが $\{0,1\}$、出力アルファベットが $\{0,\mathrm{e},1\}$ の通信路を考える（$\mathrm{e}$ は「消失」を表す記号である）。入力 $X$ と出力 $Y$ の条件付き確率は、$x=0,1$ に対して
$$P(Y=x\mid X=x)=\frac{2}{3},P(Y=\mathrm{e}\mid X=x)=\frac{1}{3}$$
であり、それ以外の出力が現れる確率は $0$ である（すなわち、入力が反転して出力されることはない）。入力の分布を
$$P(X=0)=\frac{3}{4},P(X=1)=\frac{1}{4}$$
とするとき、相互情報量 $I(X;Y)$ を求めよ。ただし、エントロピーの対数の底は $2$ とする（単位はビット）。

$2$ つの通信路を縦続接続した次の通信路を考える。

• 第 $1$ 段：入力 $X\in \{0,1\}$ を受け取り、確率 $\frac{3}{4}$ でそのまま、確率 $\frac{1}{4}$ で反転した値 $Z\in \{0,1\}$ を出力する（2 元対称通信路）。
• 第 $2$ 段：$Z$ を受け取り、確率 $\frac{2}{3}$ で $Y=Z$ をそのまま出力し、確率 $\frac{1}{3}$ で消失記号 $Y=\mathrm{e}$ を出力する（2 元消失通信路）。

第 $2$ 段で消失が起こるかどうかは、$X$ や第 $1$ 段の反転とは独立に決まるものとする。入力 $X$ から出力 $Y\in \{0,1,\mathrm{e}\}$ までを $1$ つの離散無記憶通信路とみなしたとき、その通信路容量 $C=\underset{P_X}{\max }I(X;Y)$ を求めよ。ただし、エントロピーと相互情報量の対数の底は $2$ とする（単位はビット）。

情報源記号 $a_1,a_2,\dots ,a_6$ がそれぞれ確率
$$P(a_1)=\frac{1}{3},P(a_2)=\frac{1}{4},P(a_3)=\frac{1}{6},P(a_4)=\frac{1}{8},P(a_5)=\frac{1}{12},P(a_6)=\frac{1}{24}$$
で独立に発生する無記憶情報源がある。この情報源の各記号に、符号アルファベット $\{0,1,2\}$ の語を符号語として割り当てる 3 元の瞬時符号（どの符号語も他の符号語の接頭語にならない符号）を考える。このような符号の平均符号長（1 記号あたりの符号語の長さの期待値）の最小値を求めよ。

入力アルファベットが $\{0,1\}$、出力アルファベットが $\{0,1,e\}$ の離散無記憶通信路を考える。ここで $e$ は「消失」を表す記号である。入力 $X$ と出力 $Y$ の条件付き確率は、$x\in \{0,1\}$ に対して
$$P(Y=x\mid X=x)=\frac{5}{8},P(Y=e\mid X=x)=\frac{1}{4},P(Y=1-x\mid X=x)=\frac{1}{8}$$
で与えられる。この通信路の通信路容量 $C={\max }_{P_X}I(X;Y)$ を求めよ。ただし、エントロピーと相互情報量の対数の底は $2$ とする（単位はビット）。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成多項式
$$g(x)=x^4+x^3+x^2+1$$
で定まる符号長 $7$ の巡回符号 $C$ を考えます。すなわち、$C$ は ${\mathbb{F}}_2[x]$ の次数 $2$ 以下の多項式 $a(x)$ を用いて $a(x)g(x)$ と表される多項式全体です。多項式 $c_0+c_{1}x+\cdots +c_6{x}^6$ を語 $(c_0,c_1,\dots ,c_6)\in {\mathbb{F}}_2^7$ と同一視します。

$C$ の符号語を、ビット誤り確率 $p$ $\left(0<p<\frac{1}{2}\right)$ の二元対称通信路で送ります。各ビットは互いに独立に確率 $p$ で反転します。受信語 $r$ に対して、受信側は次のように復号します。

• $r$ とのハミング距離が $1$ 以下である符号語が存在すれば、その符号語を出力する。
• 存在しなければ、誤りを検出したと判断して何も出力しない。

（この復号法で、ハミング距離 $1$ 以下の符号語は存在すれば $1$ つに定まることも確かめてください。）

送信した符号語とは異なる符号語が出力される確率を、$p$ の式で求めてください。

確率変数 $X$ は $\{0,1,2\}$ に値をとり、
$$P(X=0)=\frac{1}{2},P(X=1)=\frac{1}{4},P(X=2)=\frac{1}{4}$$
に従う。$X$ と独立な確率変数 $Z$ は $\{-1,0,1\}$ に値をとり、
$$P(Z=-1)=\frac{1}{4},P(Z=0)=\frac{1}{2},P(Z=1)=\frac{1}{4}$$
に従う。$Y$ を $X+Z$ を $4$ で割った余り（$Y\in \{0,1,2,3\}$）とする。対数の底を $2$ とするとき、相互情報量 $I(X;Y)$ を求めよ。

3 元体 ${\mathbb{F}}_3=\{0,1,2\}$（演算は $3$ を法とする）上の符号長 $4$ の線形符号 $C$ を、検査行列
$$H=\left(\begin{array}{cccc}1& 0& 1& 1\\ 0& 1& 1& 2\end{array}\right)$$
によって
$$C=\{\mathbf{x}\in {\mathbb{F}}_3^4\mid H{\mathbf{x}}^{\mathsf{T}}=0\}$$
と定める。符号語の重みは $0$ でない成分の個数、$C$ の最小距離 $d$ は $C$ の異なる 2 つの符号語のハミング距離の最小値とする。

$C$ の次元 $k$、最小距離 $d$、重みがちょうど $d$ である符号語の個数 $A_d$ を、組 $(k,d,A_d)$ の形でこの順に求めよ。

情報源 $X$ は 6 個の記号 $a_1,a_2,\dots ,a_6$ を次の確率で出力する。
$$P(a_1)=\frac{3}{10},P(a_2)=\frac{1}{5},P(a_3)=\frac{3}{20},P(a_4)=\frac{3}{20},P(a_5)=\frac{1}{10},P(a_6)=\frac{1}{10}$$
符号アルファベットを $\{0,1,2\}$ とする 3 元の瞬時符号（語頭符号）で $X$ の記号を 1 記号ずつ符号化するとき、1 記号あたりの平均符号長の最小値を求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で考える。${\mathbb{F}}_2^4$ のベクトルのうち、ハミング重み（$1$ である成分の個数）が奇数であるものは全部で $8$ 個ある。これら $8$ 個のベクトルを列ベクトルとして、どれも $1$ 回ずつ、ある順に並べてできる $4\times 8$ 行列を $H$ とし、
$$C=\{\mathbf{x}\in {\mathbb{F}}_2^8\mid H{\mathbf{x}}^{\mathsf{T}}=0\}$$
で定まる符号長 $8$ の線形符号 $C$ を考える（$\mathbf{x}$ は行ベクトル）。$C$ の次元を $k$、最小距離を $d$、$C$ に含まれるハミング重みがちょうど $d$ の符号語の個数を $A_d$ とする。組 $(k,d,A_d)$ をこの順に求めよ。

袋の中に赤玉 $2$ 個と白玉 $2$ 個が入っている。この袋から玉を $1$ 個ずつ $2$ 回、取り出した玉をもとに戻さずに取り出す。どの玉も同じ確率で取り出されるものとする。

$1$ 回目に取り出した玉の色を $X$、$2$ 回目に取り出した玉の色を $Y$ とする（$X,Y$ はそれぞれ「赤」「白」のどちらかの値をとる確率変数）。

$X$ と $Y$ の相互情報量 $I(X;Y)$ を求めよ。ただし、エントロピーの対数の底は $2$ とする。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成多項式
$$g(x)=x^4+x+1$$
で定まる符号長 $15$ の巡回符号 $C$ を考える。すなわち、符号語 $c=(c_0,c_1,\dots ,c_{14})\in {\mathbb{F}}_2^{15}$ を多項式 $c(x)=c_0+c_{1}x+\cdots +c_{14}{x}^{14}$ と同一視し、$C=\{c(x)\mid \mathrm{deg}c(x)\le 14,g(x)\text{ が }c(x)\text{ を割り切る}\}$ とする。なお、$g(x)$ は ${\mathbb{F}}_2$ 上の原始多項式である（既約であり、その根 $\alpha$ は $15$ 個の元 ${\alpha }^0,{\alpha }^1,\dots ,{\alpha }^{14}$ がすべて異なる、${\mathbb{F}}_{16}$ の $0$ でない元すべてとなる）。

この符号を誤り検出のためだけに用いる。送信した符号語 $c$ に誤りパターン $e\in {\mathbb{F}}_2^{15}$ が加わって $r=c+e$ が受信されたとき、$r\in C$ ならば「誤りなし」と判定し、$r\notin C$ ならば「誤りあり」と判定する。$e\ne 0$ で $r\in C$ となるとき、誤りは検出されない。

ハミング重み（$1$ である成分の個数）が $1$ 以上 $4$ 以下の誤りパターン $e$ のうち、検出されないものの個数を求めよ。

情報源記号 $a_1,a_2,\dots ,a_6$ を、それぞれ確率
$$P(a_1)=\frac{3}{10},P(a_2)=\frac{1}{5},P(a_3)=P(a_4)=\frac{3}{20},P(a_5)=P(a_6)=\frac{1}{10}$$
で独立に出力する無記憶情報源がある。各記号に、符号アルファベット $\{0,1,2\}$ の語を $1$ 対 $1$ に割り当てる $3$ 元の語頭符号（どの符号語もほかの符号語の語頭にならない符号）を考える。

$3$ 元の語頭符号のうち、$1$ 記号あたりの平均符号長 $L=\sum _{i=1}^{6}P(a_i){\ell }_i$（${\ell }_i$ は $a_i$ の符号語の長さ）が最小になるものについて、その平均符号長 $L$ を求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、生成多項式 $$g(x)=x^4+x+1$$ で定まる符号長 $15$ の巡回符号 $C$ を考える。すなわち、$C$ は ${\mathbb{F}}_2[x]$ の次数 $14$ 以下の多項式のうち $g(x)$ で割り切れるもの全体（係数の列を長さ $15$ のベクトルとみなす）である。なお、$g(x)$ は ${\mathbb{F}}_2$ 上の原始多項式であり、$x^{15}-1$ を割り切る。

$C$ の符号語を、ビット反転確率が $p$ $\left(0<p<\frac{1}{2}\right)$ の 2 元対称通信路で送る。各ビットの反転は互いに独立に起こるものとする。受信語は、シンドロームを計算し、そのシンドロームをもつベクトルのうちハミング重みが最小のもの（コセットリーダー）を誤りとみなして訂正する方法で復号する。

復号した符号語が送信した符号語と一致する確率を $p$ の式で求めよ。

入力アルファベット $\{0,1\}$、出力アルファベット $\{0,1,\mathrm{e}\}$ の離散無記憶通信路を考える。入力 $X=x$（$x\in \{0,1\}$）に対して、出力 $Y$ は
$$P(Y=x\mid X=x)=\frac{1}{2},P(Y=\mathrm{e}\mid X=x)=\frac{1}{4},P(Y=1-x\mid X=x)=\frac{1}{4}$$
で定まる（$\mathrm{e}$ は消失を表す記号である）。この通信路の通信路容量（$1$ 回の使用あたり、単位はビット）を求めよ。対数の底は $2$ とする。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上の符号長 $8$ の線形符号 $C$ を、生成行列
$$G=\left(\begin{array}{cccccccc}1& 1& 0& 0& 0& 0& 0& 1\\ 0& 1& 0& 0& 1& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 0& 1\\ 0& 0& 0& 1& 0& 1& 1& 0\end{array}\right)$$
の行ベクトルが張る ${\mathbb{F}}_2^8$ の部分空間として定める。$C$ の双対符号を
$$C^{\perp }=\{x\in {\mathbb{F}}_2^8\mid \text{すべての }c\in C\text{ に対して }x\cdot c=0\}$$
とする（$x\cdot c$ は ${\mathbb{F}}_2$ 上の標準内積）。$C^{\perp }$ の最小距離を $d$、$C^{\perp }$ に含まれるハミング重み $d$ の符号語の個数を $A$ とするとき、組 $(d,A)$ を求めよ。

記号 $0,1$ をそれぞれ確率 $\frac{3}{4},\frac{1}{4}$ で、各時刻独立に出力する無記憶情報源 $X$ を考える。$X$ の出力を $3$ 個ずつまとめたブロック（$000,001,\dots ,111$ の $8$ 通り）を $1$ つの記号とみなし、この $8$ 個の記号に対して $2$ 元ハフマン符号（符号記号は $\{0,1\}$）を構成する。

このとき、元の情報源 $X$ の記号 $1$ 個あたりの平均符号長（ブロック $1$ 個あたりの平均符号長を $3$ で割ったもの）を求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上の符号長 $8$ の線形符号 $C$ を、検査行列
$$H=\left(\begin{array}{cccccccc}1& 0& 0& 1& 0& 0& 0& 1\\ 0& 1& 0& 1& 1& 0& 0& 1\\ 0& 1& 1& 0& 0& 0& 1& 1\\ 0& 0& 1& 1& 0& 1& 0& 0\end{array}\right)$$
を用いて $C=\{\mathbf{x}\in {\mathbb{F}}_2^8\mid H{\mathbf{x}}^T=0\}$ で定める。ただし、符号語の重みとは $0$ でない成分の個数であり、$C$ の最小距離 $d$ とは $C$ の $0$ でない符号語の重みの最小値である。$C$ の最小距離 $d$ と、$C$ に含まれる重み $d$ の符号語の個数 $A_d$ を、この順に組 $(d,A_d)$ で求めよ。