理系学生日記

おまえはいつまで学生気分なのか

問題3-32 (3.3.4 A Simulator for Digital Circuits)

time segment に置かれているイベントキューが LIFO ではなく FIFO なのはなぜかという問題.
今回はこのヒントに従った方が分かりやすそう.

In particular, trace the behavior of an and-gate whose inputs change from 0,1 to 1,0 in the same segment and say how the behavior would differ if we stored a segment's procedures in an ordinary list, adding and removing procedures only at the front (last in, first out).

and-gate を題材にして,入力が (A,B)=(0,1) から (A,B)=(1,0) へ遷移するときのことを考えるて,キューに "A が 1 になるイベント","B が 0 になるイベント" という順番でイベントが格納されている状況を考える.

まず,"A が 1 になるイベント"が消費される.このとき,(A,B)=(1,1)であるから,(未来の)イベントキューには "出力が 1 になるイベント" が新たに格納されるようになる.次に "B が 0 になるイベント" が消費されると,(A,B)=(1,0) であるから,(未来の)イベントキューには "出力が 0 になるイベント" が新たに格納される.このときイベントキューが FIFO だと,未来において最初に "出力が 0 になるイベント" が消費され,次に "出力が 1 になるイベント" が消費される.出力の wire は最後の状態を保つので,未来において入力が (A,B)=(1,0) なのにも関わらず,出力が 1 になってる状況が発生してしまう.