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

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

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

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

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

Arithmetic Unit【NandGame編】

2023年12月16日

はじめに

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

コーストFIRE中のIPUSIRONです😀

IPUSIRONのプロフィールを見る

Arithmetic Unitレベル

Arithmetic Unitレベルのゴールは、次の機能を持つ算術演算回路を実装することです。

入力・op0とop1:オペコードフラグ。2つで2ビット。
・X:演算される側の16ビット列
・Y:演算する側の16ビット列
出力[1]「op0=0かつop1=0」⇒X+Y
[2]「op1=0かつop1=0」⇒X-Y
[3]「op0=0かつop1=1」⇒X+1
[4]「op0=1かつop1=0」⇒X-1
算術演算回路の入出力

Arithmetic Unitレベルを解く

回路のベースはLogic Unitレベルにしたいのですが、よくみると出力の真理値表がLogic Unitレベルのものとパターンの並びが異なります。パターンを同一の並びにするには、[2]と[3]を入れ替えます。これで準備ができました。

入力・op0とop1:オペコードフラグ。2つで2ビット。
・X:演算される側の16ビット列
・Y:演算する側の16ビット列
出力[1]「op0=0かつop1=0」⇒X+Y
[3]「op0=0かつop1=1」⇒X+1
[2]「op1=0かつop1=0」⇒X-Y

[4]「op0=1かつop1=0」⇒X-1
算術演算回路の入出力

後は論理演算系のコンポーネントを算術演算系のコンポーネントに置き換えるだけです。

この回路は(ロジックを含まない定数0を除いて)8つのコンポーネントを使い、内部的に1,379個のNandゲートを使っています。

もっと最適化できるとヒントが与えられます。

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

内部の算術としては、加算と減算しかありません。それぞれ与えられた入力を使うか、定数1を使うかのどちらかです。つまり、加算器と減算器はそれぞれ1個だけあれば十分といえます。

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

この回路は(ロジックを含まない定数0を除いて)5つのコンポーネントを使い、内部的に754個のNandゲートを使っています。

もっともシンプルな解答であることが示されました。