Booth 乗算器の解説（例付き）

基数 2 と基数 4 の Booth 再符号化を学び、-3 × 5 を段階的に追跡し、反復型ハードウェア乗算器での符号付き幅の誤りを防ぎます。

Denny

2026年5月7日読了まで約9分

Chalkboard feature illustration for “Booth 乗算器の解説（例付き）”

要約： Booth 再符号化は、乗数中の 1 の連続を符号付き桁へ書き換えます。基数 2 Booth は各反復で $(Q_0,Q_{-1})$ を見ます。01 なら被乗数を加算、10 なら減算し、00 または 11 なら何もせず算術右シフトします。幅が安全な $n$ ビット実装は被乗数を符号拡張し、 $(n+1)$ ビットのアキュムレータを用いるため、最小負値で起こる特別な失敗を避けられます。基数 4 の修正 Booth は $0,\pm M,\pm2M$ を選び、部分積数をおよそ半分にします。

二進乗算はシフトと加算で構成できます。Booth なしでは 2 の補数の被演算子を乗算できないわけではありません。必要なのは、符号処理と部分積生成を正しく設計することです。

Booth 法は一様な符号付き再符号化を与え、1 の連続を圧縮します。これは、複数サイクルで一つの加算器を使い回す 反復型乗算器 と、再符号化部分積を作って加算器／コンプレッサツリーで縮約する 並列乗算器 で利用できます。両者は再符号化の考え方を共有しますが、レイテンシ、面積、タイミングは異なります。

連続する 1 の恒等式

ビット $j$ から $k$ （ $k\ge j$ ）まで二進の 1 が連続すると考えます。

2^j + 2^{j+1} + \cdots + 2^k = 2^{k+1} - 2^j

たとえば次のとおりです。

001111_2 = 010000_2 - 000001_2

通常の符号なしシフト加算は 1111 に対して被乗数のシフトコピーを四つ加えます。Booth 再符号化では、連続の下端で減算し、上端の一つ上で加算します。

これはあらゆるビットパターンで非ゼロ演算数を減らす保証ではありません。長い連続には有利ですが、孤立した 1 や交互の 1 では削減がなく、加減算判断が増えることもあります。固定レイテンシの基数 2 反復型乗算器は依然として $n$ 回反復します。再符号化は各反復での算術動作を変えるのであって、サイクル数を自動的に減らすものではありません。

基数 2 Booth 再符号化

乗数の下に暗黙のゼロを追加します。

Q_{-1}=0

反復 $i$ では、現在の最下位乗数ビット $Q_0$ と保存した前ビット $Q_{-1}$ を調べます。

$Q_0$	$Q_{-1}$	アキュムレータの操作
0	0	変更なし
0	1	$M$ を加算
1	0	$M$ を減算
1	1	変更なし

その後、アキュムレータ、乗数、保存ビットを連結した全体を一ビット算術右シフトします。

組 $(Q_0,Q_{-1})$ は境界を検出します。

10 は 1 の連続の下端なので減算します。
01 は連続をシフトして通過した後の上端なので加算します。
等しい隣接ビットは一定の連続の内部なので、算術操作は不要です。

表のビット順は重要です。 $(Q_{-1},Q_0)$ と印刷する文献もあり、その場合は行のラベルが逆になります。常に規約を明記してください。

幅が安全な反復データパス

両入力を符号付き $n$ ビット 2 の補数値とします。

$M$ ：被乗数
$Q$ ：乗数

次を使用します。

$M_e$ ： $n+1$ ビットへ符号拡張した $M$
$A$ ：初期値ゼロの $n+1$ ビットアキュムレータ
$Q$ ： $n$ ビット乗数レジスタ
$Q_{-1}$ ：初期値ゼロの保存ビット一つ
0 から $n-1$ までの反復カウンター

$n$ 回の各反復で、(1) $(Q_0,Q_{-1})$ を調べ、(2) 01 なら $A \leftarrow A+M_e$ 、(3) 10 なら $A \leftarrow A-M_e$ 、(4) 00 または 11 なら $A$ を保持し、(5) $\{A,Q,Q_{-1}\}$ 全体を一ビット算術右シフトします。

$n$ 回後、 $A$ の冗長な最上位符号拡張ビットを捨てます。残りの $n$ ビットの $A$ と $Q$ を連結すると、符号付き $2n$ ビット積になります。

余分なアキュムレータビットが重要な理由

$n$ ビット 2 の補数の表現範囲は次です。

-2^{n-1} \le x \le 2^{n-1}-1

$-2^{n-1}$ の正の絶対値は $n$ ビットに収まりません。そのため、 $n$ ビットだけで -M を前計算する設計は、 $M$ が最小負値のとき失敗します。 $M$ を符号拡張し、 $(n+1)$ ビットアキュムレータを使えば、アルゴリズム中に $M_e$ と $-M_e$ の両方を表せます。

例題： $-3 \times 5$

4 ビット被演算子を使います。

M=-3=1101_2,\qquad Q=5=0101_2

被乗数を五ビットへ符号拡張します。

M_e=11101_2

初期値は次です。

A=00000,\quad Q=0101,\quad Q_{-1}=0

表は組と算術操作、および連結算術右シフト後の状態を示します。

反復	組 $(Q_0,Q_{-1})$	シフト前の操作	シフト後の $A$	シフト後の $Q$	$Q_{-1}$
初期	—	—	`00000`	`0101`	`0`
1	`10`	$A-M_e=00011$	`00001`	`1010`	`1`
2	`01`	$A+M_e=11110$	`11111`	`0101`	`0`
3	`10`	$A-M_e=00010$	`00001`	`0010`	`1`
4	`01`	$A+M_e=11110$	`11111`	`0001`	`0`

四回後、 $A$ の冗長な上位符号ビットを捨てます。

A[3:0]\;||\;Q = 1111\;0001_2

これを 8 ビットの 2 の補数として読むと、

11110001_2=-15

となり、 $-3\times5$ と一致します。

連結シフトを一つ追跡する

最初の減算後は次です。

\{A,Q,Q_{-1}\} = \{00011,\ 0101,\ 0\}

算術右シフトはアキュムレータの符号ビットを新しい最上位位置へ複製し、ほかのビットを一つずつ動かします。

\{00001,\ 1010,\ 1\}

シフトは 連結レジスタ全体 に作用しなければなりません。 $A$ と $Q$ を別々にシフトすると、両者の境界を越えるビット転送を失います。

ハードウェアブロック

再利用可能な反復 Booth 乗算器には、 $(n+1)$ ビット被乗数レジスタまたは入力経路、 $(n+1)$ ビットアキュムレータ、 $n$ ビット乗数レジスタと $Q_{-1}$ 、 $(n+1)$ ビット加算／減算器、add／subtract／hold の組デコード制御、連結算術シフタ、反復カウンターと busy／done 制御が含まれます。

加算器を全反復で使い回すため、完全並列乗算器より面積を節約できますが、レイテンシを支払います。一反復が一クロックか複数マイクロステップかは、コントローラとデータパスによります。

ALU コンポーネントは教育用回路で加減算を提供できますが、幅と符号付きオーバーフローの扱いを確認してください。シフトレジスタは直列移動を示しますが、Booth データパスには上位ビットを符号で満たす、より幅広い連結レジスタが必要です。

基数 4 修正 Booth

基数 4 修正 Booth は重なり合う三ビット窓を調べ、乗数ビット二つごとに一桁へ再符号化します。下端にゼロを追加し、必要に応じて上端で乗数を符号拡張します。窓 $(Q_{2i+1},Q_{2i},Q_{2i-1})$ に対して次を選びます。

窓	再符号化した倍数
`000`	$0$
`001`	$+M$
`010`	$+M$
`011`	$+2M$
`100`	$-2M$
`101`	$-M$
`110`	$-M$
`111`	$0$

利用する倍数は次です。

\{0,\ +M,\ -M,\ +2M,\ -2M\}

$2M$ は左シフトなので、部分積は比較的安価に生成できます。 $n$ ビット乗数では、基数 2 の $n$ 桁ではなく、およそ $\lceil n/2\rceil$ 個の再符号化桁を作ります。これは反復型基数 4 設計の反復数を半減し、並列設計の部分積行数を減らせます。ただし再符号化、符号補正、部分積生成、縮約、配線、最終加算、パイプラインのすべてがタイミングに寄与するので、完成乗算器が自動的に二倍速くなるわけではありません。

並列縮約：Wallace、Dadda、最終加算器

高スループット乗算器は部分積を並列生成し、キャリーセーブコンプレッサで列を縮約し、最後にキャリー伝播加算器で仕上げます。Wallace 木と Dadda 木は古典的な縮約スケジュールです。修正 Booth をその前に置けば行数を減らせます。最終加算器には、ターゲット技術に応じてキャリールックアヘッド、並列プレフィックス、キャリーセレクトなどを選びます。

「組み合わせ回路」は必ずしも「一プロセッササイクル」ではありません。幅広い乗算器は目標クロック周期のため複数段へパイプライン化されることがあり、面積や電力のため反復ユニットを使うプロセッサもあります。これは実装上の選択です。

Booth とほかの乗算構造

方式	符号付き演算	部分積またはサイクル数	代表的なトレードオフ
基本反復シフト／加算	正しい符号処理で可能	通常 $n$ 回	小さいデータパス、単純な制御
基数 2 反復 Booth	2 の補数をネイティブに再符号化	$n$ 回	一様な符号付きアルゴリズム、加算／減算／スキップ
基数 4 反復 Booth	2 の補数をネイティブに再符号化	約 $\lceil n/2\rceil$ 回	より複雑なデコードと倍数選択
並列部分積配列／木	符号付き・符号なしの変種	行を同時処理	より多いハードウェア、パイプライン可能
基数 4 Booth + 縮約木	ネイティブな符号付き再符号化	初期行数が約半分	高性能設計で一般的な選択肢

万能な勝者はありません。被演算子幅、ターゲットセルまたは FPGA 資源、スループット、レイテンシ、面積、電力、検証量が適切な構造を決めます。

DigiSim で作る

4 ビットの教育用実装では、(1) 可視の記憶要素から 5 ビットアキュムレータを作り、(2) 4 ビット被乗数を 5 ビットへ符号拡張し、(3) 5 ビット加減算経路を使い、(4) 4 ビット乗数と別の $Q_{-1}$ ビットを保存し、(5) (Q0, Q−1) を加算・減算・保持へデコードし、(6) {A,Q,Q−1} 全体の算術シフトを実装し、(7) 正確に四回反復し、(8) busy、done、最終 8 ビット積を公開します。

$-3\times5$ の表を段階実行し、各シフト後の状態を比較してください。最初の反復で不一致なら組順か減算極性の逆転、負のアキュムレータをシフトした後なら論理シフトを使っていることが疑われます。

検証チェックリスト

小さい $n$ ビット乗算器を網羅検証するなら、符号付き参照積を $2n$ ビットで表し、次のすべてを試験します。

2^n \times 2^n = 2^{2n}

少なくとも $0\times x$ と $1\times x$ 、正×正、正×負、負×正、負×負、最大正値、最小負値 $-2^{n-1}$ 、 $-2^{n-1}\times -1$ 、乗数パターン 0000、1111、0101、1010、動作中のリセットまたは再開始を含めます。

さらに、基数 2 で正確に $n$ 回反復すること、受理された演算ごとに done が一度だけ出ること、入力がラッチされるか契約上安定を要求されること、結果が有効前に消費されないこと、連結シフトがアキュムレータ符号を保存することを検証します。理想的な機能シミュレーションは算術の順序を証明しますが、最大ハードウェアクロックは証明しません。ターゲットへマッピングした後に静的タイミング解析を使ってください。

続けて学ぶ

符号拡張と範囲については 2 の補数算術を復習し、リップルキャリー加算とキャリールックアヘッド構造を比較してください。

Andrew D. Booth は 1951 年の論文 “A Signed Binary Multiplication Technique” で一様な符号付き手法を導入しました。中心となる再符号化は現在も有用ですが、専門的な実装には明示的な幅、定義されたレイテンシ契約、網羅的な符号付き試験、ターゲット固有のタイミング解析が必要です。