Multiplication【NandGame編】

2023年12月10日

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段の処理（各桁ビットb_iごとの加算処理）を実現するコンポーネントを作成するわけですが、この内部も次の3つの処理に分けられます。

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

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

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

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

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

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

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

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

5：回路を実装する

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

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

6：テストする

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

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