Loading article…
バイナリ乗算器は、コンピュータなどのデジタル電子機器において、2つのバイナリ数を乗算するために使用される電子回路です。
デジタル乗算器を実装するには、さまざまなコンピュータ演算技術を利用できます。ほとんどの技術では、部分積のセットを計算し、それをバイナリ加算器を使用して合計します。このプロセスは、2進数（基数2 ）を使用する点を除けば、筆算による乗算と似ています。
1947年から1949年の間、アーサー・アレック・ロビンソンは学生見習いとして、その後開発エンジニアとしてイングリッシュ・エレクトリックで働いた。この期間に重要なことに、彼はマンチェスター大学で博士号を取得し、初期のMark 1コンピュータのハードウェア乗算器の設計に取り組んだ。しかし、1970年代後半まで、ほとんどのミニコンピュータには乗算命令がなかったため、プログラマはループアンワインディングを使用して記述されることが多い部分的な結果を 繰り返しシフトして累積する「乗算ルーチン」[ 1 ] [ 2 ] [ 3 ]を使用していた。 メインフレームコンピュータには乗算命令があったが、それらは「乗算ルーチン」と同じ種類のシフトと加算を行った。
初期のマイクロプロセッサには乗算命令もありませんでした。乗算命令は16ビット世代で一般的になりましたが、[ 4 ] 少なくとも2つの8ビットプロセッサには乗算命令がありました。1978年に発表されたMotorola 6809 [ 5 ]と、 1980年に開発されたIntel MCS-51ファミリー、そして後にATMega、ATTiny、ATXMegaマイクロコントローラに搭載された最新のAtmel AVR 8ビットマイクロプロセッサです。
大規模集積回路の発展により、チップあたりのトランジスタ数が増加したことで、各部分積を一つずつ処理するために単一の加算器を再利用するのではなく、すべての部分積を一度に合計できるだけの加算器を単一のチップ上に配置することが可能になった。
一般的なデジタル信号処理アルゴリズムの中には、処理時間の大部分を乗算に費やすものがあるため、デジタル信号プロセッサの設計者は、乗算をできるだけ高速化するために、かなりのチップ面積を犠牲にしています。初期のDSPでは、1サイクル乗算・累積演算ユニットがチップ面積の大部分を占めることがよくありました。
学校で教わる小数の掛け算の方法は、部分積を計算し、それを左にシフトして足し合わせるというものです。最も難しいのは部分積を求めることで、そのためには長い数に1桁の数字（0から9まで）を掛ける必要があります。
123 × 456 ===== 738（これは123×6です） 615（これは123×5を左に1つずらしたものです） + 492（これは123×4を左に2桁ずらしたものです） ===== 56088バイナリコンピュータは、10進数とまったく同じ乗算を2進数で行います。2進数では、各長い数値は1桁の数字（0または1）で乗算されます。これは10進数よりもはるかに簡単です。なぜなら、0または1による積は、0または同じ数値になるからです。したがって、2つの2進数の乗算は、部分積（0または最初の数値）を計算し、それを左にシフトし、それらを加算する（もちろん2進数の加算）ことに帰着します。
1011（これは10進数の11を2進数で表したものです） × 1110（これは10進数14の2進数表現です） ====== 0000（これは1011×0です） 1011（これは1011×1を左に1つずらしたものです） 1011（これは1011×1を左に2つずらしたものです） + 1011（これは1011×1を左に3つずらしたものです） ========= 10011010（これは10進数154の2進数表現です）これは十進法よりもはるかに簡単です。覚えるべき掛け算の表はなく、単にシフトと足し算をするだけです。
この方法は数学的に正しく、小型CPUでも専用回路ではなく演算論理ユニットのシフト機能と加算機能を使って乗算を実行できるという利点があります。しかし、この方法は中間加算を多数行うため、処理速度が遅くなります。これらの加算は時間がかかります。加算回数を減らすことで、より高速な乗算器を設計することが可能です。例えば、最新のプロセッサでは部分積専用の並列加算器を実装することで、64ビットの2つの数値の乗算を63回ではなく6回の加算で済ませることができます。
2つの符号なし8ビット整数a [7:0]とb [7:0]を掛け合わせるとします。被乗数aの各ビットに対して1ビットずつ、合計8回の1ビット乗算を行うことで、8つの部分積を生成できます。
p0[7:0] = a[0] × b[7:0] = {8{a[0]}} & b[7:0] p1[7:0] = a[1] × b[7:0] = {8{a[1]}} & b[7:0] p2[7:0] = a[2] × b[7:0] = {8{a[2]}} & b[7:0] p3[7:0] = a[3] × b[7:0] = {8{a[3]}} & b[7:0] p4[7:0] = a[4] × b[7:0] = {8{a[4]}} & b[7:0] p5[7:0] = a[5] × b[7:0] = {8{a[5]}} & b[7:0] p6[7:0] = a[6] × b[7:0] = {8{a[6]}} & b[7:0] p7[7:0] = a[7] × b[7:0] = {8{a[7]}} & b[7:0]ここで、以下のVerilog表記法が使用されます。
&この記号はビットごとのANDを表します。目的の製品を得るためには、ここに示されているように、8つの部分積をすべて合計する必要があります。
p0[7] p0[6] p0[5] p0[4] p0[3] p0[2] p0[1] p0[0] + p1[7] p1[6] p1[5] p1[4] p1[3] p1[2] p1[1] p1[0] 0 + p2[7] p2[6] p2[5] p2[4] p2[3] p2[2] p2[1] p2[0] 0 0 + p3[7] p3[6] p3[5] p3[4] p3[3] p3[2] p3[1] p3[0] 0 0 0 + p4[7] p4[6] p4[5] p4[4] p4[3] p4[2] p4[1] p4[0] 0 0 0 0 + p5[7] p5[6] p5[5] p5[4] p5[3] p5[2] p5[1] p5[0] 0 0 0 0 0 + p6[7] p6[6] p6[5] p6[4] p6[3] p6[2] p6[1] p6[0] 0 0 0 0 0 0 + p7[7] p7[6] p7[5] p7[4] p7[3] p7[2] p7[1] p7[0] 0 0 0 0 0 0 0 ----------------------------------------------------------------------------------------------- P[15] P[14] P[13] P[12] P[11] P[10] P[9] P[8] P[7] P[6] P[5] P[4] P[3] P[2] P[1] P[0]
言い換えれば、P [15:0] は、 p0、p1 << 1、p2 << 2 などを合計して、最終的な符号なし 16 ビット積を生成することによって生成されます。
P [15:0] = p0[7:0] + (p1[7:0] << 1) + (p2[7:0] << 2) + (p3[7:0] << 3) + (p4[7:0] << 4) + (p5[7:0] << 5) + (p6[7:0] << 6) + (p7[7:0] << 7)
ここで、先ほどの8×8ビット乗算器を用いて、符号なし16ビット整数2つ（u [15:0]とv [15:0]）を乗算するとします。部分積法（乗算の結合法則によって正当化される）を用い、8ビット単位で計算すると、次のようになります。
p0[15:0] = u[7:0] × v[7:0] p1[15:0] = u[15:8] × v[7:0] p2[15:0] = u[7:0] × v[15:8] p3[15:0] = u[15:8] × v[15:8]
最終的な製品は以下のようになります。
P[31:0] = p0 + p1 << 8 + p2 << 8 + p3 << 16
P[15:0]（結果の下位16ビット）のみが必要な場合は、p3の計算は不要であることがわかります。
上記のように、乗算のプロセスは 3 つのステップに分けることができます。[ 6 ] [ 7 ]
従来の乗算器アーキテクチャでは、シフタとアキュムレータを使用して各部分積を加算していましたが、多くの場合、1サイクルあたり1つの部分積を加算し、速度とダイ面積のトレードオフが生じていました。1サイクルあたり1つの加算を実行する機能を実現するには、高速加算器（リップルキャリーよりも高速なもの）が必要です。[ 8 ]
現代の乗算器アーキテクチャは、(修正された) Baugh–Wooley アルゴリズム[ 9 ] [ 10 ] [ 11 ] [ 12 ] 、 Wallace ツリー、またはDadda 乗算器を使用して、部分積を単一のサイクルで加算します。
高速乗算器では、部分積の削減（つまり部分和の計算）プロセスが、乗算器の遅延、電力、面積に最も大きく影響します。[ 6 ] 速度のために、「部分積を削減する」ステージは通常、コンプレッサで構成されるキャリーセーブ加算器として実装され、「最終積を計算する」ステップは高速加算器として実装されます。
コンプレッサとは、入力ビット数よりも出力ビット数が多いデバイスのことです。乗算器のエンジニアリングにおいては、キャリー入力とキャリー出力を持つ加算器を指します。基本的なコンプレッサは全加算器、つまり「3:2コンプレッサ」です。多くの高速乗算器は、スタティックCMOSで実装されたこのようなコンプレッサを使用しています。
同じ面積でより良いパフォーマンスを実現するため、またはより小さな面積で同じパフォーマンスを実現するために、乗算器の設計では、7:3 コンプレッサなどの高次コンプレッサを使用する[ 7 ] [ 6 ] 、より高速なロジック（伝送ゲートロジック、パストランジスタロジック、ドミノロジックなど）でコンプレッサを実装する[ 8 ] 、コンプレッサを異なるパターンで接続する、またはこれらの組み合わせを行う場合があります。
ウォレスツリー実装のパフォーマンスは、2つの被乗数のうちの1つを修正ブース符号化することで改善される場合があり、これにより合計する必要のある部分積の数が減少します。
「シングルサイクル」乗算器（または「高速乗算器」）は、純粋な組み合わせ論理回路です。
bが符号なし整数ではなく符号付き整数であった場合、部分積は合計する前に積の幅まで符号拡張される必要があった。aが符号付き整数であった場合、部分積p7は最終的な合計に加算されるのではなく、減算される必要があった。
上記の配列乗算器は、いくつかの積項を反転させ、最初と最後の部分積項の左側に1を挿入することで、2の補数表記の符号付き数をサポートするように変更できます。
1 ~p0[7] p0[6] p0[5] p0[4] p0[3] p0[2] p0[1] p0[0] + ~p1[7] p1[6] p1[5] p1[4] p1[3] p1[2] p1[1] p1[0] 0 + ~p2[7] p2[6] p2[5] p2[4] p2[3] p2[2] p2[1] p2[0] 0 0 + ~p3[7] p3[6] p3[5] p3[4] p3[3] p3[2] p3[1] p3[0] 0 0 0 + ~p4[7] p4[6] p4[5] p4[4] p4[3] p4[2] p4[1] p4[0] 0 0 0 0 + ~p5[7] p5[6] p5[5] p5[4] p5[3] p5[2] p5[1] p5[0] 0 0 0 0 0 + ~p6[7] p6[6] p6[5] p6[4] p6[3] p6[2] p6[1] p6[0] 0 0 0 0 0 0 + 1 p7[7] ~p7[6] ~p7[5] ~p7[4] ~p7[3] ~p7[2] ~p7[1] ~p7[0] 0 0 0 0 0 0 0 --------------------------------------------------------------------------------------------------------------- P[15] P[14] P[13] P[12] P[11] P[10] P[9] P[8] P[7] P[6] P[5] P[4] P[3] P[2] P[1] P[0]
ここで、~p は p の補数（反対の値）を表します。
上記のビット配列には、図示されていない、あるいは明白ではない多くの簡略化が含まれています。
どちらのタイプのシーケンスでも、最後のビットが反転され、MSB の直下に暗黙の -1 が追加されます。ビット位置 0 (LSB) の p7 の 2 の補数否定による +1 と、ビット列 7 から 14 (各 MSB がある場所) のすべての -1 を合計すると、左側に「魔法のように」浮かび上がる単一の 1 に単純化できます。MSB を反転することで符号拡張が不要になる理由の説明と証明については、コンピュータ算術の本を参照してください。[ 13 ]
バイナリ浮動小数点数は、符号ビット、有効ビット（仮数部）、指数ビットで構成されます（簡略化のため、基数と組み合わせ体は考慮しません）。各オペランドの符号ビットをXOR演算して、結果の符号を取得します。次に、2つの指数を加算して、結果の指数を取得します。最後に、各オペランドの仮数部を乗算して、結果の仮数部を取得します。ただし、バイナリ乗算の結果が特定の精度（例えば32、64、128）のビット総数を超える場合は、丸め処理が必要となり、指数が適切に変更されます。