The Product of Nibbles【Turing Complete編】

2023年9月12日2023年12月5日

目次 [hide]

1 はじめに
2 2進数値の乗算
3 ブースのアルゴリズム
4 （符号なし）4ビット乗算器
- 4.1 1ビット加算器から4ビット乗算器を構築する
- 4.2 4ビット加算器から4ビット乗算器を構築する
5 The Product of Nibblesステージ
6 The Product of Nibblesステージを解く
- 6.1 8 Bit Makerコンポーネントの力を借りる【別解】
- 6.2 マルチプレクサーを活用する【別解2】

はじめに

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

コーストFIRE中のIPUSIRONです

IPUSIRONのプロフィールを見る

2進数値の乗算

A×Bという乗算（掛け算）であれば、Aを被乗数（multiplicand）、Bを乗数（multiplier）といいます。

・被乗数･･･乗数を掛けられる値。一般的に値は変わらない。

・乗数･･･被乗数に掛けて、結果である積（product）を求める数。

2の倍数を掛ける場合は左シフトするだけ

2ⁿを乗じる計算するには、2をn個掛け合わせてることになりますが、n回左シフトしても計算できます。

※2ⁿの除算は右シフトで実現できます。

それ以外の数を掛ける場合はどうするか

問題は2ⁿ以外を乗ずる場合です。

一番素朴な方法は、被乗数を乗数の回数だけ加算して積を求めるというアプローチです。C言語で実現すると次のような処理になります。multiplicandとmultiplierの数は与えられているものとします。

int product = 0;
int i;
for (i = 0; i < multiplier; i++) {
    product = product + multiplicand;
}

2進数でもこのアプローチは通用します。しかし、8ビットの乗算だと、最大で255回のループと加算処理が実行される可能性があります。つまり、このアプローチは、乗数の値が大きいときに、その分だけループの回数が増えて低速なのです。さらに、デジタル回路で実装するのは非常に困難です。

乗算の筆算のアルゴリズムは2進数でも通用する

各桁に対して基数を繰り返し被乗数に乗ずるのではなく、被乗数は乗数の各ビットに対して左シフトします。乗数ビットが1なら積に加算し、0なら積に加算せずに次の処理に移ります。

シフトと加算を使う方法なので、デジタル回路にも相性がよいといえます。

product = 0;
for (i = 0; i &lt; log(multiplier); i++) {
    if ( (multiplier &amp; 1) == 1) {  // LSビットがセットされていたら.
        product = product + multiplicand;  // 計算結果に加算する.
    }
    multiplier = multiplier &gt;&gt; 1;      // 乗数をシフトダウン.
    multiplicand = multiplicand &lt;&lt; 1;  // 被乗数をシフトアップ.
}

ブースのアルゴリズム

機会があれば、解説を追加する予定です。

（符号なし）4ビット乗算器

1ビット加算器から4ビット乗算器を構築する

$a_{3} a_{2} a_{1} a_{0} \times b_{3} b_{2} b_{1} b_{0}$

$= (a_{3} a_{2} a_{1} a_{0} \times b_{0}) + (a_{3} a_{2} a_{1} a_{0} \times b_{1} \times 10 b) + (a_{3} a_{2} a_{1} a_{0} \times b_{1} \times 100 b) + (a_{3} a_{2} a_{1} a_{0} \times b_{1} \times 1000 b)$ 　←(*)

[1] $a_{3} a_{2} a_{1} a_{0} \times b_{0}$ の回路

[2] $a_{3} a_{2} a_{1} a_{0} \times b_{1}$ の回路

[3] $a_{3} a_{2} a_{1} a_{0} \times b_{2}$ の回路

[4] $a_{3} a_{2} a_{1} a_{0} \times b_{3}$ の回路

新しい変数を用いると、(*)式は次のように書き換えられます。

$c_{3} c_{2} c_{1} c_{0} + (d_{3} d_{2} d_{1} d_{0} \times 10 b) + (e_{3} e_{2} e_{1} e_{0} \times 100 b) + (f_{3} f_{2} f_{1} f_{0} \times 1000 b)$

10b、100b、1000bを掛けるというのは、桁がずれていくことを意味します。

このことを考慮して、1ビット加算器を12個使えば、次の回路ができあがります。

$a_{3} a_{2} a_{1} a_{0} \times b_{3} b_{2} b_{1} b_{0} = g_{7} g_{6} g_{5} g_{4} g_{3} g_{2} g_{1} g_{0}$

4ビット加算器から4ビット乗算器を構築する

4ビット加算器を3つ使えば、次の回路に書き換えられます。

The Product of Nibblesステージ

The Product of Nibblesステージのゴールは、乗算回路を組むことです。

2つの4ビット列が入力として与えられたとき、その乗算結果は8ビットになります。

The Product of Nibblesステージを解く

1：入力端子と出力端子を確認する

キャンバス上に入力端子と出力端子が配置されています。

特に入力端子が2つあるので、被乗数と乗数がどちらに対応するか、ランプをON・OFFさせて確認しておきます。

2：乗算回路の設計方針を検討する

筆算のアプローチを見ると、可能性のある各乗算値に対して、すべての被乗数ビットを加算するように配線します。乗数ビットは、被乗数ビットのそれぞれに対してAND演算することで計算します。ANDを使えば、0のときに必ず0となるからです。もし乗算ビットがゼロなら、シフトアップした非常算ビットは加算器に渡されません。

よって、全加算器とAND回路を組み合わせれば実現できそうです。左にシフトするところは、回路上で1つずつ左シフトのようにずれていく回路を作ればよいのです。

シミュレーターでは、ANDコンポーネントとFull Adderコンポーネント（1ビット全加算器）を組み合わせて加算器を構築していきます。

3：回路を実装する

4ビット加算器があればよいのですが、シミュレーターには1ビット加算器と8ビット加算器しかありません。今回は1ビット加算器を使うことにします。

1ビット加算器であるFull Adderコンポーネントの入出力を再確認しておきましょう。Input 1～3があり、どこをCarry Inに使っても加算器の機能上問題ありません。ただし、使い方に統一性がないと回路が見づらくなるので、今回はInput 1をCarry Inとして扱うことにします。