当サイトの一部ページには、アフィリエイト・アドセンス・アソシエイト・プロモーション広告を掲載しています。

Amazonのアソシエイトとして、Security Akademeiaは適格販売により収入を得ています。

広告配信等の詳細については、プライバシーポリシーページに掲載しています。

消費者庁が、2023年10月1日から施行する景品表示法の規制対象(通称:ステマ規制)にならないよう、配慮して記事を作成しています。もし問題の表現がありましたら、問い合わせページよりご連絡ください。

参考:令和5年10月1日からステルスマーケティングは景品表示法違反となります。 | 消費者庁

Conditions【Turing Complete編】

2023年10月17日

はじめに

いつもブログをご覧いただきありがとうございます。

コーストFIRE中のIPUSIRONです😀

IPUSIRONのプロフィールを見る

Conditionsステージ

Conditionsステージのゴールは、入力バイトデータがビットコードに応じた条件を満たすかを判定する回路を組むことです。

ステージの回路の入出力は次の通りです。

入力・上のInput端子・・・ビットコード。3ビット
・下のInput端子・・・バイトデータ
出力・Output端子・・・判定結果:1ビット
Condtionsステージの回路の入出力
ビットコード判定処理出力
000b判定しないOutputは常にOFF
001b入力バイトデータがゼロか0ならOutputはON、それ以外ならOFF
010b入力バイトデータが0より小さいか0より小さいならOutputはON、それ以外ならOFF
011b入力バイトデータが0以下か0以下ならOutputはON、それ以外ならOFF
100b判定しないOutputは常にON
101b入力バイトデータが非ゼロか0でなければOutputはON、それ以外ならOFF
110b入力バイトデータが0以上か0以上ならOutputはON、それ以外ならOFF
111b入力バイトデータが0より大きいか0より大きいならOutputはON、それ以外ならOFF
ビットコードに対応する判定処理と出力

Conditionsステージを解く

1:シミュレーターのナンバーフォーマットを切り替える

0より小さいパターンが存在するということは、入力バイトデータは符号つき8ビットと考えるということです。

左上のアイコン群の一番右アイコンを押して、「255」から「-1」にします。これでナンバーフォーマットを切り替わります。

2番目のInputのランプをON・OFFすると負の数を表現できていることを確認できます。

2:入力のビットコード側の設計方針を決める

今回の回路には2つの入力があります。

・ビットコード

・バイトデータ

まずはビットコード側の入力から攻めていきましょう。

ビットコードは3ビットであり、それぞれ違うパターンで、合計8パターンあります。それぞれのパターンが選ばれたときにONになるワイヤーが用意できればよいはずです。

これまで何度も登場していますが、8 Bit Splitterと3 Bit decorderの出番になります。

3:入力のバイトデータ側の設計方針を決める

次に、バイトデータ側の入力を考えます。

入力バイトデータとゼロを大小比較する仕組みを実装することになります。

比較対象がゼロなので、次のように考えます。

入力バイトデータのどこかの桁に1が1つでもあれば、0ではありません。

このような1の有無はORで判断できます。ORゲートを通した結果を中間結果Pと呼ぶことにします。

Pに注目すれば、ゼロとの一致・不一致は容易に判定できます。

[1]ゼロとの不一致、すなわち非ゼロとの一致を識別する

入力バイトデータが非ゼロかどうかは、中間結果Pと1をANDゲートに通せば判断できます。

[2]ゼロとの一致を識別する

中間結果PをNOTゲートで反転させれば、入力バイトデータが0000 0000bのときだけ、1になります。あとは、その反転結果と1とANDゲートに通せばゼロか否かを判断できます。

ここまではゼロとの一致回路の設計になります。

[2]ゼロより小さいを識別する

入力バイトデータの最上位ビットが1であれば、他の桁がどうなっていても、常にゼロより小さくなります(-128~-1)。

[3]ゼロより大きいを識別する

「入力バイトデータの最上位ビットが0」かつ「最上位ビット以外に1が1つでもある」ならば、ゼロより大きくなります(1~127)。

[4]ゼロ以上、ゼロ以下を識別する

「以上」(あるいは「以下」)については、「0と一致」+「より大きい」(あるいは「より小さい」)と考えます。「+」は「または」を意味するので、ORゲートを使えばよいのです。

以上で回路の設計方針を終えます。

なお、まとめて一気にやろうとすると思い悩むかもしれません。また、今回のステージの回路はキャンバスがとても狭いです。

私自身完成したと思ったのにうまくテストが通らず、結構はまりました。

条件を実現する回路を徐々に組んでいくと、回路の見通しが悪くなりますし、配置がうまくいかず手戻りが発生する可能性が高いです。

そこで、条件ごとに分けて回路を組んでいき、その回路を説明します。最後にキャンバスに納まるように、回路を最適化させつつ統合させていきます。

4:ビットコードの解読回路を組む

よく登場する基本回路になります。

ビットコードは3ビットなので、8 Bit Splitterコンポーネントの出力は3本しか使いません。素直に3 Bit decoderコンポーネントに直結します。

5:ビットコード000bのための回路を組む

ビットコードが000bのときは常に出力端子がOFFになるようにします。

このとき、3 Bit decoderコンポーネントの0番ピン[1]ピンは0番から7番まであるものとしました。がONになります。NOTゲートを通せば、このビットパターンのときにOFFになります。

これを素直に回路に組むと次のようになります。

これでも問題ないのですが、ちょっと無駄があります。

「ビットコード000bのとき」

⇒「3 Bit decoderコンポーネントの0番ピンがON」

⇒「3 Bit decoderコンポーネントの0番ピン以外がOFF」

⇒「3 Bit decoderコンポーネントの0番ピンに何もつなげない。Conditons回路の出力端子につなげない。つまり出力はこの条件下で常にOFF」

結局のところ、NOTゲートとワイヤーを不要だったということです。これを回路にすると次のようになります。

6:ビットコード100bのための回路を組む

ビットコードが000bのときは常に出力端子がONになるようにします。

これは単純に出力端子と直結すれば実現できます。

7:ビットコードが101bのための回路を組む

ゼロとの不一致、すなわち非ゼロとの一致を識別させます。

入力バイトデータが非ゼロかどうかは、中間結果Pと1をANDゲートに通せば判断できます。

※Pは入力バイトデータの全桁をORゲートに通した結果です。

8:ビットコードが001bのための回路を組む

中間結果PをNOTゲートで反転させて、その反転結果と「3 Bit decoderの1番ピンからくる1(ON)」とANDゲートに通せばゼロか否かを判断できます。

入力バイトデータが0000 0000bのときだけ、中間結果Pが0なり、その反転が1になるからです。

9:ビットコードが010bのための回路を組む

入力バイトデータが0より小さいときに、出力端子をONにさせます。

「入力バイトデータが0より小さい」

⇒「入力バイトデータが負の数」

⇒「入力バイトデータの最上位ビットが1」(他の桁は任意)

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

10:ビットコードが111bのための回路を組む

入力バイトデータが0より大きいときに、出力端子をONにさせます。

「入力バイトデータが0より大きい」

⇒「入力バイトデータの最上位ビットが0」かつ「最上位ビット以外に1が1つでもある」

「入力バイトデータの最上位ビットが0」かつ「最上位ビット以外に1が1つでもある」という条件について、素直に回路を組むと次のようになります。

しかし、後半の条件「最上位ビット以外に1が1つでもある」に対応する回路が少し冗長です。

これは「どこかの桁に1が1つでもある」と言い換えても問題ありません。なぜなら、前半の条件で「最上位ビットが0」と確定しているからです。

「どこかの桁に1が1つでもある」ことを判定する回路はすでに登場しており、共通化も期待できます。

「入力バイトデータの最上位ビットが0」かつ「どこかの桁に1が1つでもある」という条件について、回路を組むと次のようになります。

11:ビットコードが011bのための回路を組む

入力バイトデーが0以下のときに、出力端子をONにさせます。

「入力バイトデータが0以下」

⇒「入力バイトデータが0」または「入力バイトデータが0より小さい」

比較回路の原型はすでに完成していますので、あとは組み合わせるだけです。

ところで、次の2回路は同値になります。

ABCYY’
00000
00100
01000
01100
10000
10111
11011
11111
真理値表で同値を確認できる

これを踏まえると、回路の組み方としては次の2通りがあります。

回路2は先にORで組み合わせてから、(3 Bit decoderの3番ピンと)ANDを取っています。ゲートを節約できるので、こちらを採用します。

12:ビットコードが110bのための回路を組む

入力バイトデーが0以上のときに、出力端子をONにさせます。

「入力バイトデータが0以上」

⇒「入力バイトデータが0」または「入力バイトデータが0より大きい」

0以上というのは、入力バイトデータの最上位ビットが0と言い換えられます。これを回路に落とし込むと、上の回路よりすっきりします。

13:全パターンの回路を統合・最適化する

上記の回路に説明を入れると次のようになります。

14:テストする

クリアするとCONDコンポーネントがアンロックします。

コンポーネントを最適化する【別解】

2つのByte Splitterコンポーネント、8つの基本的な演算ゲート、合計10つのコンポーネントにまで最適化した回路です。

この回路だと「Condition 10」という実績を解除できます。

References

References
1 ピンは0番から7番まであるものとしました。