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

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

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

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

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

Multiplication【NandGame編】

はじめに

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

セミリタイア・ミジンコのIPUSIRONです😀

IPUSIRONのプロフィールを見る

Multiplicationレベル

Multiplicationレベルのゴールは、2つの正の数を乗算する回路を組むことです。

ただし、オーバーフローしたビットは切り捨てます。

乗算結果の桁数

乗算なので、計算結果をすべて表示しようとすると最大で2n-1(=n+(n-1))桁が必要です。

例えば、2進4ビットの1111b同士を乗算すると、次のように計算できます。

1111b×1111b=1111b+11110b+111100b+1111000b=11100001b

今回の回路の出力は16ビットなので、15(=n-1=16-1)桁が切り捨てられます。

Multiplicationレベルを解く

乗算回路の設計については、次の記事を参考にしてください。

1:回路の設計方針を検討する

上記の記事では4ビットの乗算でしたが、それでも複雑な回路でした。

NandGameのMultiplicationレベルでは16ビットを扱うので、普通に回路を実装すると見にくくなりそうです。

そこで、カスタムコンポーネント機能を活用して、独自のコンポーネントを追加します。

1段の処理(各桁ビットbiごとの加算処理)を実現するコンポーネントを作成するわけですが、この内部も次の3つの処理に分けられます。

  • 処理①「各桁でANDゲートを通す処理」
  • 処理②「全加算器を通す処理」
  • 処理③「1桁左にスライドする処理」

初段については処理①③しかありませんが、2段目以降はすべての処理があります。

2:処理①をカスタムコンポーネント化する

そこで、初段の処理をコンポーネント化して"digit deciding 16″と名づけて実装します。

3:処理②と処理③を組み合わせた処理をカスタムコンポーネント化する

(「各桁でANDゲートを通す処理」+「全加算器を通す処理」)を"digit deciding+add 16″と名づけて実装します。

4:処理③をコンポーネント化する

次段のためにスライド処理を施します。これを"shift 1″と名づけて回路を実装します。

5:回路を実装する

カスタムコンポーネントを組み合わせて、16段分を実装します。

ただし、最終段については処理③は不要です。さらに、出力値は16ビットと制限されていますので、最終段の出力値の最終ビットだけを使います。

6:テストする

テストにパスするとクリアになります。

※テストパターンを見ると4桁同士しかないため、回路はここまで複雑化せず、半分に縮小してもテストにパスするはずです。