y i x i
FA FA
s i c i
CSA
図A.5 桁上げ保存加算器(Carry Save Adder，CSA)の構成
付録 B
乗算回路
本章では，本文で扱った多倍長ではなく，32 ビットや 64 ビットなど，比較的小 さな桁の乗算を行う乗算器について述べる．
B.1 筆算式乗算回路 (School Book 乗算 )
乗算の最も基本的な形は図B.1に示す筆算式の乗算である．この方法を School Book法と呼ぶこともある．School Book法による乗算回路の構成は単純である．す
1001 1101 0000 1001 1001 1001 1110101
図B.1 筆算式乗算(School Book乗算)
なわち，被乗数を下位ビットから上位ビットに向かって1 ビットずつ走査し，i 桁に おける値が 1 ならば乗数を i ビット左にシフトしたものを積として累算し，0 なら ば何もしない．この時，n ビットどうしの乗算おいて，最大で n 個の値を累算する 必要がある．累算される値を部分積と呼ぶ．
B.2 Booth Recode
乗算の過程において，はじめに部分積の生成が必要である．School Book 法を用 いた nビットの乗算において，部分積の数は n 個となるが，この部分積の数を減ら すことができれば後の累算を高速に行うことができる．部分積の数を減らす代表的 な方法として Booth Recodeがある．
Booth Recode の基本的な考え方は基数変換と符号付き桁表現の組み合わせであ
る．通常，計算機上で用いられる 2 進数値は 1 ビットで {0，1} を表現する．これ を 2ビットで {-1，0，1}を表現する符号付きの桁表現に変換する．変換式は，変換 後の値の i 桁目を Yi とすると次式で得られる．
Yi =−1·yi+yi−1 (B.1)
特に y−1 = 0 (i = 0 の場合) とする．この変換により，1 が連続する部分において 部分積は 0 となる．そのかわりに連続した 1 が始まる部分で，-1 を乗じた部分積を 生成する．すなわちこれは，01110 = 10000 - 00010 であることを利用した変換であ ると言える．この Booth Recode を用いる際には，変換後の値が符号付きである点 に注意する必要がある．
この考え方をさらに拡張する．上述の方法では単なる 2 進数を符号付き桁表現の 2 進数に変換したが，さらに高い基数の数に変換することを考える．基数を高くする ことで，複数の桁をまとめて演算することができ，部分積の数を減らすことができ る．基数として 4 を選ぶと，1 桁を {-2，-1，0，1，2}で表すことができ，部分積の 生成がシフトのみで実現できるため都合がよい．2 進数から符号付き桁表現の 4 進 数への変換は次式で与えられる．
Yi =−2·yi+2+yi+yi−1 (B.2) 先程と同様に，y−1 = 0 とする．この変換により，部分積の数を大幅に削減するこ とができ，部分積の累算にかかる時間を短縮することができる．この方法は 2 次の
Booth Recode と呼ばれ，現在，多くの乗算器で用いられている．
B.3 Wallace Tree による加算
乗算の次の過程である部分積の累算について，n個の部分積を並列に加算すること で高速な累算を行うことができる．
今，部分積の数を n とすると，並列化をしていない累算ではn 段の加算が必要で
ある．ここで図B.2に示すように，n/2 個の CLA を用いて木構造で加算を行うと，
部分積を logn段の加算で累算することができる．
n
log n
図B.2 木構造による加算
この累算は，最終段以外の加算を CSA で行い，最後に残った 2 値を CPA で加 算すると効率が良い．この考え方に基づいて構成された加算木を Wallace Tree と呼 ぶ．Wallace Tree の構成を図B.3に示す．中間段に CSA を用いることで，桁上げ は最終段でのみ発生するため，累算を高速に行うことが出来る．
B.4 Wallace Tree 乗算器
以上に述べた 2 次の Booth Recode と Wallace Tree を組み合わせることで高 速な乗算器を設計することができる．この乗算器は Wallace Tree 乗算器 (Wallace Tree Multiplier，WTM)と呼ばれている．図B.4に8 ビットの数x と y の積 pを 求める2 次の Booth Recode を用いた Wallace Tree 乗算器の構成を示す．図中の Booth Recoder は 2 次の Booth Recode を行い，結果を出力するモジュールであ る．この例では 8 ビットの値を変換するため，4 個の Booth コードが得られる．次 に，四角で囲まれた P で示されたモジュールは，Booth コードと x から部分積を生 成する回路である．具体的には，x と Booth コードの値によって−2x，−x，0，x， 2x を生成する．同時に，右シフトと，必要に応じて符号拡張も行う．こうして得ら れた部分積を Wallace Tree によって加算する．