Condition【NandGame編】

2023年10月24日2023年12月16日

Conditionレベル

Conditionレベルのゴールは、条件判定回路を組むことです。

今回の条件判定は、ゼロと比べての大小比です。

組むべき回路の入出力は次のとおりです。

入力	X：比較対象の16ビット値 lt：Less than zero eq：Equasl to zero gt：Greater than zero
出力	Output：判定結果。1ビット。1を出力する条件は次の表を参照。

lt	eq	gt	1を出力する条件
0	0	0	Never
0	0	1	x > 0
0	1	0	x = 0
0	1	1	x ≧ 0
1	0	0	x < 0
1	0	1	x ≠ 0
1	1	0	x ≦ 0
1	1	1	Always

Conditionレベルを解く

直列的アプローチで解いてみる

1：用意されているコンポーネントに注目します。

新たなコンポーネントとして、is negコンポーネントとis zeroコンポーネントが用意されています。

• is negコンポーネント…入力値（16ビット）が負の数なら、1を出力する。
  • 最上位ビットが1かどうかで負の数かどうかを判定している。
• is zeroコンポーネント…入力値（16ビット）の全桁が0なら、0を出力する。

正直なところ3ビットデコーダーがあれば簡単に回路を設計できますが、本レベルでは用意されていません。

2：gtフラグの処理を実装します。

Xピンをis negとis zeroに分岐させてからorでまとめることで、Xの値が「負の数 or ゼロ」であるときに1を出力します。

上記の回路において、orコンポーネントの出力値をinvコンポーネントに通すことで、Xの値が「0より大」のときに1になります。

そして、gtフラグがON（すなわちgt=1）であるときに、Xの値が「0より大」であることを一致回路（XOR回路＋NOT回路）で識別できます。

しかしフラグはgt以外にもあります。gtフラグのみがONであることを識別しなければならないのです。

残りのltフラグとeqフラグが両方とも0のときに1を出力させるには、NOR（OR＋NOT）を通すことで実現できます。

後は最終的に2つの出力値が一致することを識別すればよいわけです。

8パターンあるうちの1パターンを解く回路ができあがりました。

愚直なアプローチなので冗長な箇所が多数あります。

それだけではありません。レベルを解くには、残り7パターンの回路を組む必要があります。

カイロを配置するキャンバス全体を覆い尽くしかねないので、このアプローチで解くのは諦めます。

素朴に並列的アプローチで解く

「1つの条件に対する回路を組んでから、次の条件の回路を組む」という直列的アプローチは非現実的であることがわかりました。

そこで並列的アプローチを採用します。

• 第1段：is negで負の数であること、is zeroでゼロであること
• 第2段：invを使って、0より大であること、ゼロでないこと
  • ⇒この2つをANDで束ね、0なら負の数、1なら正の数と判定できる。

ポイントはフラグごとにANDを用意し、その出力をORでつないで集約していくのです。

※全フラグが0なら、Xの値に依存せずに常にOutputはゼロになります。

※逆に全フラグが1なら、どこかの判定処理で1になるはずなので、ANDの出力もどこか1になります。ORで集約されるということは、1つでも1があればORの出力は1です。よって、全フラグが1なら、常に出力は1になるわけです。

この回路は9つのコンポーネントを使っており、内部的には62個のNnadゲートを使っています。

ヒントによると、さらに最適化できるとあります。

Nandを使うように最適化する【別解】

「And⇒Nand」に置き換えて、後はつじつまが合うように調整すると次のようになります。

この回路は9つのコンポーネントを使っており、内部的には56個のNandゲートによって構成されます。

別バージョン【別解2】

この回路も56個のNandゲートで構成されます。