Verilog 2001で実装されたBooth乗算器を調査する (2. 2ビット乗算器)

MorrisMA/Booth_Multipliersリポジトリをベースに、Booth乗算アルゴリズムの実装と検証についてまとめる。

2ビットずつBooth乗算器の実装例

次は、2ビットずつ処理するBooth乗算器の実装例だ：

module Booth_Multiplier_2x #(
    parameter N = 16                // Width = N: multiplicand & multiplier
)(
    input   Rst,                    // Reset
    input   Clk,                    // Clock
    
    input   Ld,                     // Load Registers and Start Multiplier
    input   [(N - 1):0] M,          // Multiplicand
    input   [(N - 1):0] R,          // Multiplier
    output  reg Valid,              // Product Valid
    output  reg [((2*N) - 1):0] P   // Product <= M * R
);

基本的なインタフェースは1ビット毎のバージョンと変わらない。

計算のサイクル数は、ビット数Nに対して ほとんど N/2 で実行できるので、1ビット版に比べて2倍の速度になっている。

localparam pNumCycles = ((N + 1)/2);    // No. of cycles required for product

肝心のBoothの計算部分は以下だ。Product Registerの上部には計算対象となる値が入っているということだ。

always @(*) Booth <= {Prod[1:0], Guard};    // Booth's Multiplier Recoding fld
assign Hi = Prod[((2*N) + 1):N];    // Upper Half of the Product Register

always @(*)
begin
    case(Booth)
        3'b000  : S <= Hi;              // Prod <= (Prod + 0*A) >> 2;
        3'b001  : S <= Hi +  A;         // Prod <= (Prod + 1*A) >> 2;
        3'b010  : S <= Hi +  A;         // Prod <= (Prod + 1*A) >> 2;
        3'b011  : S <= Hi + {A, 1'b0};  // Prod <= (Prod + 2*A) >> 2;
        3'b100  : S <= Hi - {A, 1'b0};  // Prod <= (Prod - 2*A) >> 2;
        3'b101  : S <= Hi -  A;         // Prod <= (Prod - 1*A) >> 2;
        3'b110  : S <= Hi -  A;         // Prod <= (Prod - 1*A) >> 2;
        3'b111  : S <= Hi;              // Prod <= (Prod - 0*A) >> 2;
    endcase
end

2ビットずつBooth乗算器の動作例

2ビットずつ処理するBooth乗算器の具体的な動作例を示す。8ビットの乗算器で A = 13 と B = 7 の乗算を行う例である。

入力値

• 被乗数 A = 13 (2進数: 00001101)
• 乗数 B = 7 (2進数: 00000111)

2ビットBoothエンコーディング

2ビットBooth乗算では、乗数の3ビット（現在のビットと前のビット、次のビット）を見て、以下のルールで部分積を決定する：

Next Bit	Cur Bit	Prev Bit	Op
0	0	0	+0
0	0	1	+A
0	1	0	+A
0	1	1	+2A
1	0	0	-2A
1	0	1	-A
1	1	0	-A
1	1	1	+0

計算過程

乗数 B = 00000111 を2ビットずつ処理する：

1. ステップ1: ビット位置 0-1

   • {Next Bit, Cur Bit, Prev Bit} = 110 --> 操作: -A
   • 部分積: -13 = 11110011 (2の補数)
   • シフト: 右に2ビット → 11111100

2. ステップ2: ビット位置 2-3

   • {Next Bit, Cur Bit, Prev Bit} = 011 --> 操作: +2A
   • 部分積: +26 = 00011010
   • 累積結果: 11111100 + 00011010 = 00010110
   • シフト: 右に2ビット → 00000101

3. ステップ3: ビット位置 4-5

   • {Next Bit, Cur Bit, Prev Bit} = 000 --> 操作: +0
   • 部分積: +0 = 00000000
   • 累積結果: 00000101 + 00000000 = 00000101
   • シフト: 右に2ビット → 00000001

4. ステップ4: ビット位置 6-7

   • {Next Bit, Cur Bit, Prev Bit} = 000 --> 操作: +0
   • 部分積: +0 = 00000000
   • 累積結果: 00000001 + 00000000 = 00000001
   • シフト: 右に2ビット → 00000000

最終結果

それぞれで計算した結果をまとめて、 01 01 10 11 = 91 となる。