跳到主要内容

東京大学 工学系研究科 電気系工学専攻 2019年8月実施 問題3 情報工学I

Author

donguri0912

Description

I

Answer the following questions on information theory. Suppose that we transmit information by using a time-discrete communication channel , whose input and output are designated as and , respectively. The input and output relation of the -th communication via is represented as , where means the multiplication of integers. is an internal state of the channel at the -th communication, and its value can change depending on the current or past states of the input and on the past states of the output. Both sender and receiver are unable to observe the value of directly although they can have knowledge about how changes depending on the input and output. Use the logarithm base for your answers of the following questions. You may also use the following approximations upon necessity: , , .

(1) Let be an ideally independent random variable that takes with probability and with probability . Assume that becomes with probability when and that it takes either or with equal probability when .

  • (1-i) Obtain the entropies and and the conditional entropy of .
  • (1-ii) Obtain the channel capacity of .

(2) Assume that takes either or with equal probability and that, for , the value of becomes the same as the previous output value with probability as .Obtain the maximum bits that can be transmitted by using this channel times.

(3) Assume that takes either or with equal probability when is odd and that keeps its previous value with probability as when is even.Obtain the channel capacity of and show a code that can achieve the capacity.

(4) Assume that with probability and that, for , the value of becomes the same as the previous input value with probability as . Let be an ideally independent random variable that takes with probability and with probability .Calculate the probability that at the stationary state for sufficiently large .

II

Answer the following questions on signal processing. Consider the two infinite impulse response systems shown in Figs. and . and are the input and output signal sequences of system in Fig. , respectively, and represent the signal values at time for .Similarly, and are the input and output sequences of system in Fig. . The circuits consist of adders, coefficient multipliers, and delays, whose respective functions are described in Fig. .

(1) Obtain the impulse response of system , , and its -transform .

(2) Calculate the frequency response of system 1 and explain the filtering function of this system on the input signal.

(3) Obtain the parameter values of and that makes system equivalent to system .

(4) Draw an equivalent circuit of system that has a smaller number of delays than the original system shown in Fig. .

Kai

I

(1)

はエントロピー関数

(1-i)
(1-ii)

となる時、つまり で最小となる。

このとき

よって、求める通信路容量

(2)

回目に送信できる最大のビットは 回目の通信路容量 に等しく、 回目の通信路はそれぞれ 元対称通信路として考えられることから と計算できる。

のとき、 回目の が分かっているので、 よって、 回で遅れるビット数は ビットである。

(3)

通信路は 元対称通信路として考えられることから、奇数回目の時、

偶数回目の時、前回の が分かっていれば、符号は連続した奇数回目と偶数回目を一つの符号として、 を符号語にし、復号領域としてそれぞれ を設ければよい。

(4)

が十分大きい場合について、, は独立な確率変数である。よって、 となる確率

II

(1)

変換を となる。

をつけても良い。

(2)

ゼロ点は 、極は である。 よって高周波をカットするローパスフィルタである。

(3)

変換を とする。

これが と一致するとき、

(4)