バイナリ乗算器

2進乗算器は、コンピューターなどのデジタル電子機器で2 つの2 進数を乗算するために使用される電子回路です。

デジタル乗算器を実装するには、さまざまなコンピュータ演算技術を使用できます。ほとんどの技術では、部分積のセットを計算し、バイナリ加算器を使用して合計します。このプロセスは、基数 2 (バイナリ)の数値システムを使用することを除けば、長整数乗算に似ています。

1947年から1949年の間、アーサー・アレック・ロビンソンは、イングリッシュ・エレクトリック社で学生見習いとして、その後開発エンジニアとして働いていました。この時期に彼が博士号を取得するためにマンチェスター大学で学んだことは、初期のマーク1コンピュータのハードウェア乗算器の設計に携わったことの重要な点でした。しかし、1970年代後半まで、ほとんどのミニコンピュータには乗算命令がなかったため、プログラマーは「乗算ルーチン」^{[1] [2] [3]}を使用していました。 これは、ループアンワインドを使用して記述されることが多かったです。メインフレームコンピュータにも乗算命令はありましたが、同じ種類のシフトと加算を「乗算ルーチン」として実行していました。

初期のマイクロプロセッサには乗算命令もありませんでした。乗算命令は16ビット世代で一般的になりましたが、^[4] 少なくとも2つの8ビットプロセッサには乗算命令があります。 1978年に発表されたMotorola 6809、^[5]と1980年に開発されたIntel MCS-51ファミリ、そして後にATMega、ATTiny、ATXMegaマイクロコントローラに搭載されている最新のAtmel AVR 8ビットマイクロプロセッサです。

大規模集積化によりチップあたりのトランジスタ数が増えると、1 つの加算器を再利用して各部分積を 1 つずつ処理するのではなく、1 つのチップに十分な数の加算器を配置してすべての部分積を一度に合計することが可能になりました。

一般的なデジタル信号処理アルゴリズムの中には、乗算にほとんどの時間を費やすものもあるため、デジタル信号プロセッサの設計者は、乗算をできるだけ高速にするためにかなりのチップ領域を犠牲にしています。初期の DSP では、シングル サイクルの乗算累算ユニットがチップ領域の大部分を占めることがよくありました。

学校で教えられる小数の掛け算の方法は、部分積を計算し、それを左にシフトしてから足し合わせるというものです。最も難しいのは部分積を求める部分で、長い数字に 1 つの数字 (0 から 9) を掛け算する必要があるためです。

     123
   × 456
   =====
     738（これは123×6です）
    615（これは123×5で、1つ左にシフトされています）
 + 492 (これは 123 × 4 で、2 つ左にシフトされます)
   =====
   56088

バイナリ コンピュータは、10 進数とまったく同じ乗算を 2 進数で行います。バイナリ エンコードでは、各長い数字に 1 つの数字 (0 または 1) を掛けますが、0 または 1 の積は 0 または同じ数だけなので、10 進数よりもはるかに簡単です。したがって、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進数です)

これは、覚えておくべき掛け算の表がなく、シフトと加算だけなので、10 進法よりもはるかに簡単です。

この方法は数学的に正しく、小型の CPU で、専用回路ではなく算術論理ユニットのシフトと加算機能を使用して乗算を実行できるという利点があります。ただし、この方法は中間加算を多く必要とするため、処理速度が遅くなります。これらの加算には時間がかかります。より高速な乗算器を設計して、より少ない加算で実行できます。最新のプロセッサは、2 つの 64 ビット数を 6 回 (64 回ではなく) の加算で乗算でき、複数のステップを並列に実行できます。^{[引用が必要]}

2 つ目の問題は、基本的な学校での方法で符号を別の規則で処理することです (「+ を + とすると + になる」、「+ を - とすると - になる」など)。 現代のコンピューターでは、通常は2 の補数表現で、数値自体に符号が埋め込まれます。 そのため、乗算プロセスは 2 の補数を処理するように調整する必要があり、プロセスが少し複雑になります。 同様に、1 の補数、符号と絶対値、IEEE-754などのバイナリ表現を使用するプロセッサーでは、乗算プロセスに特定の調整が必要です。

たとえば、2 つの符号なし8 ビット整数a [7:0] とb [7:0] を乗算するとします。被乗数aの各ビットに対して 1 ビットの乗算を 8 回実行することで、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]

ここで、{8{a[0]}}はa[0]（aの0番目のビット）を8回繰り返すことを意味します（Verilog表記）。

積を得るためには、次に示すように、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] は、 p 0、p 1 << 1、p 2 << 2 などを合計して生成され、最終的な符号なし 16 ビット積が生成されます。

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 の補数（反対の値）を表します。

上記のビット配列には、示されていない、または明らかではない多くの簡略化があります。1 つの補数ビットの後に非補数ビットが続くシーケンスは、符号拡張を回避するための 2 の補数トリックを実装しています。p7 (非補数ビットの後にすべての補数ビットが続く) のシーケンスは、この項を減算するため、最初はすべて否定された状態になっています (最下位の位置に 1 が追加されています)。両方のタイプのシーケンスでは、最後のビットが反転され、暗黙の -1 が MSB のすぐ下に追加されます。ビット位置 0 (LSB) の p7 の 2 の補数否定からの +1 と、ビット列 7 から 14 (各 MSB が配置されている場所) のすべての -1 を加算すると、それらは「魔法のように」左側に浮かんでいる 1 つの 1 に簡略化できます。MSB を反転すると符号拡張が不要になる理由の説明と証明については、コンピューター算術の本を参照してください。^[6]

2 進浮動小数点数には、符号ビット、有効ビット (仮数部)、指数ビット (簡単にするために、基数と組み合わせフィールドは考慮しません) が含まれます。各オペランドの符号ビットは XOR 演算されて、答えの符号が求められます。次に、2 つの指数が加算されて、結果の指数が求められます。最後に、各オペランドの仮数を乗算すると、結果の仮数が返されます。ただし、2 進乗算の結果が特定の精度 (32、64、128 など) の合計ビット数よりも大きい場合は、丸めが必要となり、指数が適切に変更されます。

掛け算のプロセスは3つのステップに分けられます: ^{[7] [8]}

• 部分積を生成する
• 部分積の削減
• 最終製品の計算

古い乗算器アーキテクチャでは、各部分積を合計するためにシフタとアキュムレータが採用されており、多くの場合、1サイクルあたり1つの部分積であり、速度とダイ面積をトレードオフしていました。現代の乗算器アーキテクチャは、（修正）Baugh-Wooleyアルゴリズム、^{[9] [10] [11] [12]} Wallaceツリー、またはDadda乗算器を使用して、1サイクルで部分積を合計します。Wallaceツリー実装のパフォーマンスは、 2つの被乗数のうちの1つを修正 ブースエンコードすることで改善されることがあり、これにより合計しなければならない部分積の数が減ります。

速度を上げるために、シフトアンド加算乗算器には高速加算器（リップルキャリーよりも高速なもの）が必要です。^[13]

「シングルサイクル」乗算器（または「高速乗算器」）は、純粋な組み合わせ論理です。

高速乗算器では、部分積の削減プロセスが通常、乗算器の遅延、電力、面積に最も大きく影響します。^[7] 速度に関しては、「部分積の削減」段階は通常、コンプレッサで構成されたキャリーセーブ加算器として実装され、「最終積の計算」ステップは高速加算器（リップルキャリーよりも高速なもの）として実装されます。

多くの高速乗算器は、静的CMOSで実装されたコンプレッサ（「3:2コンプレッサ」）として全加算器を使用しています。同じ面積でより良い性能を達成したり、より小さな面積で同じ性能を達成したりするために、乗算器の設計では7:3コンプレッサなどの高次のコンプレッサを使用することがあります。 ^{[8] [7]} コンプレッサをより高速なロジック（トランスミッションゲートロジック、パストランジスタロジック、ドミノロジックなど）で実装します。^[13] コンプレッサを異なるパターンで接続します。または、これらの組み合わせを行います。

• Hennessy, John L.; Patterson, David A. (1990)。「セクション A.2、セクション A.9」。コンピュータ アーキテクチャ: 定量的アプローチ。Morgan Kaufmann。pp. A–3..A–6、A–39..A– 49。ISBN 978-0-12383872-8。

• FPGA をターゲットにした乗算器設計
• 半加算器とデジタル ゲートを使用した 2 進乗算回路。