https://msyksphinz.hatenablog.com/entry/2025/08/04/040000

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

Booth乗算アルゴリズムの概要

Booth乗算アルゴリズムは、2の補数表現での符号付き乗算を効率的に実行するための手法である。従来のシフト加算方式と比較して、連続する1のビット列を効率的に処理できる特徴がある。

このリポジトリでは、以下の3種類のBooth乗算アルゴリズムが実装されている：

1ビットずつ処理するBooth乗算 (1x)
2ビットずつ処理するBooth乗算 (2x)
4ビットずつ処理するBooth乗算 (4x)

実装ファイル構成

リポジトリには以下の主要なVerilogファイルが含まれている：

非最適化版（直接実装）

Booth_Multiplier.v              - 1ビットずつBooth乗算器
Booth_Multiplier_2x.v           - 2ビットずつBooth乗算器  
Booth_Multiplier_4x.v           - 4ビットずつBooth乗算器

最適化版

Booth_Multiplier_1xA.v          - 1ビットずつBooth乗算器（最適化版）
Booth_Multiplier_4xA.v          - 4ビットずつBooth乗算器（最適化版）
Booth_Multiplier_4xB.v          - 符号付き/符号なし4ビットずつBooth乗算器

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

以下は、1ビットずつ処理するBooth乗算器の基本的な実装例である：

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

Ld (input): ロード信号。アクティブ時に乗数・被乗数をレジスタにロードし、乗算処理を開始する。
M (input): 被乗数（Multiplicand）。乗算される値。ビット幅は 2**pN となる。
R (input): 乗数（Multiplier）。掛ける値。ビット幅は 2**pN となる。
Valid (output): 積（Product）が有効であることを示す信号。計算完了時にアサートされる。
P (output): 積（Product）。M と R の乗算結果が出力される。ビット幅は 2**(pN+1) となる。

一つ一つ見ていこう：

値がロードされると、1桁ずつ計算していく。pNサイクルかけて計算している。

always @(posedge Clk)
begin
    if(Rst)
        Cntr <= #1 0;
    else if(Ld)
        Cntr <= #1 2**pN;
    else if(|Cntr)
        Cntr <= #1 (Cntr - 1);
end

また、被乗数レジスタAは、最上位ビットをガードビットとして拡張して格納することで、負の最小値（2の補数表現での最小値）にも対応できるようになっている。

//  Multiplicand Register
//      includes an additional bit to guard sign bit in the event the
//      most negative value is provided as the multiplicand.

always @(posedge Clk)
begin
    if(Rst)
        A <= #1 0;
    else if(Ld)
        A <= #1 {M[2**pN - 1], M};  
end

Prod は、最初に R を設定した後に、下位の2ビットを見ながら S を設定していく。 Prod は上の方から設定され、1サイクルごとに下位に移っていく。

//  Compute Upper Partial Product: (2**pN + 1) bits in width

always @(*)
begin
    case(Prod[1:0])
        2'b01   : S <= Prod[(2**(pN+1) + 1):(2**pN + 1)] + A;
        2'b10   : S <= Prod[(2**(pN+1) + 1):(2**pN + 1)] - A;
        default : S <= Prod[(2**(pN+1) + 1):(2**pN + 1)];
    endcase
end

//  Register Partial products and shift rigth arithmetically.
//      Product register has guard bits on both ends.

always @(posedge Clk)
begin
    if(Rst)
        Prod <= #1 0;
    else if(Ld)
        Prod <= #1 {R, 1'b0};
    else if(|Cntr)
        Prod <= #1 {S[2**pN], S, Prod[2**pN:1]};    // Arithmetic Shift Right
end

下記のコードは、最後に P を設定して出力を行う。

//  Assign the product less the two guard bits to the output port

always @(posedge Clk)
begin
    if(Rst)
        P <= #1 0;
    else if(Cntr == 1)
        P <= #1 {S[2**pN], S, Prod[2**pN:2]};
end

//  Count the number of shifts
//      This implementation does not use any optimizations to perform multiple
//      bit shifts to skip over runs of 1s or 0s.

always @(posedge Clk)
begin
    if(Rst)
        Valid <= #1 0;
    else
        Valid <= #1 (Cntr == 1);
end