Counting Signals【Turing Complete編】
はじめに
いつもブログをご覧いただきありがとうございます。
コーストFIRE中のIPUSIRONです😀
Counting Signalsステージ
Counting Signalsステージのゴールは、4つの入力のうち、ONになっている個数を2進数で出力させる回路を作ることです。
Counting Signalsステージを解く
1:設計方針を検討する
4ビット入力、3ビット出力。
入力の4ビットは0000b~1111bのパターンがあります[1]bは2進数値を強調する印です。。
※Tと1、Fと0が対応するものとしています。
出力の3ビットは000b~100bのパターンがあります。なぜなら、入力が全部ONだったとすれば、出力は100b(=4d)であるためです[2]dは10進数値を強調する印です。。
真理値表から論理式を求めてもよいのですが、手間がかかります。
そこで、出力は3ビットであり、各桁を出力する回路を別々に設計することにします。
2:接続しやすいようにワイヤーを並べる
3:出力の4の位を生成する回路を設計する
OUT2がTになるのは、全入力がTのときだけです。
つまり、INの4つの矢印を4入力型ANDゲートの入力につなげればよいことになります。
ただし、手元に4入力型ANDコンポーネントがないので、3入力型ANDコンポーネントとANDコンポーネントで代用します。
4の位についてだけテストしておきます。
[Run]ボタンを押すと2の位と1の位につながる回路を組んでいないのでエラーになります。[Next]ボタンを押して、一番右の(全入力がON)のところが4を出力してパスすることをチェックします。
4:出力の1の位を生成する回路を設計する
順番的には2の位に注目すべきですが、ここは一番難しいので後回しにして、先に1の位に注目します。
出力の1の位がTになるのは、入力のTが奇数個のときのみです。
つまり、奇数判定回路の出力を1の位につなげればよいことになります。
入力は4つなので、4入力型の奇数判定回路を用います。これはすでにOdd Number of Signalsの問題で作成済みです。これを流用します。
5:出力の2の位を生成する回路を設計する
入力のTの個数に注目して場合分けします。
入力のTの個数 | 2の位は? |
---|---|
0個 | F(2の位まで到達しない) |
1個 | F(2の位まで到達しない) |
2個 | T |
3個 | T |
4個 | F |
次に、「Tが2個の場合」と「Tが3個の場合」の具体的なパターンを見ていきます。
Tの個数 | パターンの総数 | 具体的なパターン |
---|---|---|
2個 | 4C2=6通り | IN=1100b, 1010b, 1001b, 0110b, 0101b, 0011b |
3個 | 4C3=4通り | IN=1110b, 1101b, 1011b, 0111b |
上記の計10パターンのときのみに、2の位(OUT2)がT(1)になればよいのです。
(a)IN=1010b, 1001b, 0110b, 0101bについては、「2つのXOR+AND」で判定できる。
(b)IN=1100b, 0011bについては、「2つのAND+XOR」で判定できる。
(c)IN=1110b, 1101b, 1011b, 0111bついては、「2つのAND+XOR」で判定できる。
まとめると、INPUTを「2つのXOR+AND」につなげる経路と「2つのAND+XOR」につなげる経路を作り、それぞれの経路の出力をORに通します。