東京大学 情報理工学系研究科 創造情報学専攻 2018年8月実施 筆記試験 第2問
Author
Description
太陽光発電システムについて考えよう。ソーラーパネルの維持管理のため、以下のような運用規則が定められているとする。
- (i)
枚のパネルが一つのグループとして維持管理される。 - (ii) パネルはグループごとに定期的に点検される。
- (iii) パネルの状態は各グループごとに
ビットデータとして報告される。
ここで各ビットは対応するパネルに不具合があれば
まず、ソフトウェアによる解法を考えよ。ここでは、
四則演算、論理演算、シフト演算、および表引きには
(1) 単純な方式として各ビットの値をチェックし、
(2) 実際、表引き操作を行うことで上述の方式 (1) を高速化できる。その計算時間を答えよ。
(3) 方式 (1) より高速かつ方式 (2) よりストレージを必要としない方式の擬似コードを示せ。その計算時間を答えよ。
ハードウェアによる解決を考えよう。ここでは、入力はビット列、出力は
(4) 入力
(5) 入力
(6) 入力
Kai
(1)
k = 0
i = 0
while i < 32:
k = k + (1 & n) // (2 time units)
n = n >> 1 // shift to the right (1 time unit)
i = i + 1
return k
Time complexity would be
(2)
In the case where we use lookup tables we can save the shift operation. This means that the computation time would be:
(3)
k = 0
i = 1
while i < 2**32:
k = k + (i & n) // (2 time units)
i = i << 1
return k
In this method we take only and
operation.
(4)
Let us use AND, OR and NOT to define a new gate called XOR.

Using XOR, AND, OR and NOT we will creatre P3
as follows:

The truth table for it would be:
In0 | In1 | In2 | Out0 | Out1 |
---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 0 |
0 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 |
1 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 1 | 1 |
(5)
For P6
the logic will be as follows:

(6)
Note: I am not sure about my answer, I think propogation delay is correct but not sure. The question itself isn't clear as well. Should I solve the latency problem or give a reason. Not clear.
Since any of the