Logic Engine【Turing Complete編】

2023年8月31日2023年10月17日

Logic Engineステージ

Logic Engineステージのゴールは、演算装置を作ることです。

入力	・CODE：8ビット。演算の内容をビット列で指示する。 0000 0000bならOR 0000 0001bならNAND 0000 0010bならNOR 0000 0011bならAND それ以外はなし。 ・Input 1：8ビット。演算対象。 ・Input 2：8ビット。演算対象。
出力	・Ouput：8ビット

Logic Engineステージを解く

1：設計の方針を考察する

回路はCODEから来る命令に沿って、実施するべき演算が異なります。

命令に応じて演算を切り替えるというアプローチより、すべての演算についての結果を計算しておき命令に応じてどの結果を出力するのかを切り替えるアプローチの方が設計しやすそうです。

ここでは後者のアプローチを採用します。

2：CODEを解析する処理を設計する

CODEは8ビットですが、0000 0000b～0000 0011bの4パターンは各演算に対応します。

4本のワイヤーを用意しておいて、各パターンに応じて4本の内1本だけがONになるようにできれば、その先にスイッチを用意して命令に対応する演算結果だけを取り出せそうです。

前半の処理については、3ビットデコーダーで実現できます。3ビットデコーダーは入力が3ビット、出力が8ビットであり、今回の仕事をカバーできます。

※CODEの入力として、他のパターンのビット列が来た場合には、無視するようにします。つまり、回路は演算しません。不要なワイヤーを接続しないだけです。

3：入力から伸びるワイヤーを工夫する

今回の問題では、入力ピンや出力ピンを移動できないので、工夫してコンポーネントを配置したりワイヤリングしたりする必要があります。

図のようにワイヤーを伸ばします。後で見やすくなるように、別の色にしています^[1]この辺りは好みでよいでしょう。。

4：OR演算を実装する

右上のコンポーネント一覧において、「8BIT」＞「LOGIC」を見てください。ここに8ビットをまとめて処理するビット演算用のコンポーネントが揃っています。

8 Bit ORコンポーネントを配置します。

8 Bit ORコンポーネントの入力には、入力ピンからのワイヤーを素直につなげます。出力は8ビットなので、8 Bit Switchを介して出力ピンにつなげます。OR演算は0000 0000bに対応するので、3 Bit decoderの出力の0番ピンから伸びたワイヤーを、8 Bit SwitchのEnableピンにつなげます。

以上をまとめると次の回路になります。

※これはシミュレーターなので理解しやすいようにワイヤリングしていますが、本物の回路を組む場合は無駄なワイヤーはなくす必要があります。なるべくワイヤーは短くすべきです。

5：NAND演算を実装する

8 Bit NANDコンポーネントは用意されていませんので、自力で実装します。

なるべく用意されている8 Bit NOTコンポーネントと8 Bit ORコンポーネントで実現する方法を考えます。

※8ビット値をByte Splitterコンポーネントでビットごとに分割・処理して、8ビットのNAND演算を実現するアプローチもありますが、スペースの問題で今回は避けます。

8ビットのNAND演算といっても、各桁は独立しています。つまり、NOTとORでNANDを実現できれば、まったく同じアプローチで8ビット版も作れるということです。

NANDゲートの真理値表は次の通りでした。

A	B	NAND(A, B)
0	0	1
0	1	1
1	0	1
1	1	0

ORゲートの真理値表は書き出します。入力にNOTゲートの有無でどう変化するのか見られるように列を追加します。

A	NOT(A)	B	NOT(B)	OR(A, B)	OR(NOT(A), B))	OR(A, NOT(B))	OR(NOT(A), NOT(B))
0	1	0	1	0	1	1	1
0	1	1	0	1	1	0	1
1	0	0	1	1	0	1	1
1	0	1	0	1	1	1	0

表を見比べてください。

NAND(A, B)は上から1、1、1、0と並んでいます。これと同じ並びをORゲートの真理値表から探します。

一番右端が一致することがわかります。

つまり、NAND(A, B)はOR(NOT(A), NOT(B))で実現できるということです。

以上を踏まえて、8ビット列のNAND演算を実装すると次のようになります。8 Bit Switchのenableピンは、8 Bit decoderの1番ピンとつながります。

6：NOR演算を実装する

8 Bit NORコンポーネントは用意されていませんので、自力で実装します。

1ビット版で考えると、NORは「OR＋NOT」です。これは簡単です。

一気に実装してみましょう。

※ワイヤーやコンポーネントは流用した方が無駄がありませんが、ここでは理解のしやすさを優先しました。後で少しすっきりさせた回路を紹介します。

7：AND演算を実装する

8 Bit ANDコンポーネントは用意されていませんので、自力で実装します。

ANDは「NAND＋NOT」です。

すでに8ビット版のNANDを実装済みであり、出力を8 Bit NOTコンポーネントを通すだけです。

以上を踏まえて実装します。

※実装済みのNAND回路を流用せずに、同じ回路を並べています。

8：テストする

クリアすると8 Bit AND、8 Bit NAND、8 Bit NORコンポーネントがアンロックします。

Logic Engine回路を最適化する

次のステージ（Arithmetic Engine）では、Logic Engine回路がそのまま引き継がれて追加する形で解くことになります。

上記のLogic Engine回路は無駄が少々あるので、整理しておきましょう。整理することでスペースが空きます。

整理のポイントは2つあります。

・重複するコンポーネントを統合する。

・いらないワイヤーをカットする。

※短くしすぎると逆に別の問題が出てくる可能性があるので、このシミュレーターでは余裕を持たせておきます。

1：回路を保存する

せっかく作った回路を失うのはもったいないので、保存することにします。

※クリアできた回路を保存しておくと、別の回路を簡単に試しやすいです。

左上の3番目のSwitch schematicアイコン

すると、次の画面が表示されます。

このDefaultが今作った回路に対応します。

「Default」を選んで、右側に表示される「紙が2枚重なった」アイコンを押します。これはコピーを意味します。

※ゼロから作るために、まっさらな回路用キャンバスを用意したい場合は、「＋ New schematic」を押します。

「Default2」が作成されます。これを選んで、右側の鉛筆アイコンを押します。これで名称を変更できます。ここでは"Optimized circuit"とします。

※ここで保存する回路は、ステージごとに回路は独立しています。つまり、「ステージ1のDefault回路」とステージ2のDefault回路」は別物ということです。シミュレーター全体のセーブデータというわけではないので注意してください。

2：Optimize circuit回路を表示する

“Optimized circuit"を選んでダブルクリックします。

これでコピーした側の回路用キャンバスに切り替わったことになります。

3：内部のNANDとANDを統合する

内部の仕組みは4つに分割できます。

上から2番目がNANDを実現し、4番目がANDを実現しています。

スペースの関係上、4番目を2番目に統合するより、2番目を4番目に統合したほうがよさそうです。

NANDのところをいったん取り除きます。ANDの入力側のワイヤーは共用できます。

そして、8 Bit Switchだけは別物なので、移動します。その後、正しくワイヤーを配線します。

結果は次の通りです。

※注意すべき点は、8 Bit Switchのenableピンが、8 Bit decoderの正しいピンにつながっていることです。

4：ORとNORを統合する

同様にしてORとNORを統合できます。NORは「OR＋NOT」であり、前段は完全に共通化できます。

回路にすると次のようになります。

以上で完成になります。

8ビット向けのコンポーネントのみで作成する【別解】

3 Bit decoderコンポーネントを使わずに、都度マルチプレクサーで分岐処理させています。

この回路だと、実績の「Symmetric ALU」を解除できます。

8 Bit Switchコンポーネントを使わないバージョン【別解2】

8 Bit Switchコンポーネントの代わりに、8 Bit Muxコンポーネントを採用しました。

左シフトと右シフトを追加したバージョン【別解3】

別解の回路に、5dで左シフト、6dで右シフトする回路を組み込んでいます。

ただし、5dと6dをチェックするテストパターンがないため、追加した回路が正しいかはまだ確実には保証されていません。サンドボックスステージで手動で確認してみてください。