「計算機アーキテクチャ１」講義資料２
-- 加算器と乗算器 -高木 直史
１．加算器
ｎビット符号なし２進整数の加算について考える。被加数、加数、和をそれぞれ X=[xn-1xn-2…x0]、
Y=[yn-1yn-2…y0]、S=[snsn-1sn-2…s0]（xi, yi, si ∊ {0, 1}）とする。また、最下位への桁上げ入力を c0 とす
る。
1.1 順次桁上げ加算器
加算は、下位桁から順に、各桁において、その桁の演算数 xi、yi と下位からの桁上げ ci から、その桁
の和 si と上位への桁上げ ci+1 を計算することにより行える。xi、yi、ci の値の組合せに対し、si、ci+1 は
表１のように定まる。
si および ci+1 は、以下の論理式で表される。
表１：加算の真理値表
＋ yi○
＋ci
si = xi○
＋ yi) ∧c i または、xi∧yi∨(xi∨yi) ∧c i
ci+1 = xi∧yi∨(xi○
＋ は排他的論理和を表す。以降、
ここに∧は論理積、∨は論理和、○
∧を省略することがある。この一桁分の計算を行う回路を全加算器
（full adder：ＦＡ）と呼ぶ。
人が加算を行う手順をそのまま実現したのが、順次桁上げ加算器
（ripple carry adder）である。順次桁上げ加算器は、図１に示すよ
うに全加算器を直列に接続することにより構成される。すなわち、
各全加算器の桁上げ出力が一つ上位の全加算器の桁上げ入力になる。
回路の素子数はｎに比例する。ハードウェア量が少なく、また、規
xi
yi
ci
si
ci+1
0
0
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
則正しい一次元セル配列構造になる。しかし、最悪の計算時間（回
路の段数）はｎに比例する。
図１：順次桁上げ加算器
1.2 桁上げ飛び越し加算器
順次桁上げ加算において、第ｉ桁を下位からの桁上げが通過して上位に伝搬するのは、その桁の二つ
＋ yiが１のときである。以降、xi○
＋ yiをpiと表
の演算数xiとyiの一方が０で他方が１のとき、すなわち、xi○
記する。連続する桁のブロックを考えると、そのブロック内のすべての桁で二つの演算数の値が異なれ
ば、すなわち、piが１であれば、下位からの桁上げがそのブロックを通過して上位に伝搬する。
そこで、計算をいくつかのブロックに分け、各ブロックで桁上げ伝搬条件が成立するかどうかを求め
ておき、条件が成立する場合、下位からの桁上げがそのブロックを飛び越して上位に伝搬するようにす
1
るのが、桁上げ飛び越し加算器（carry skip adder または carry bypass adder）である。各ブロック内
では、桁上げが順次伝搬する。ブロックの桁上げ伝搬条件は、ブロック内のすべての桁の pi の論理積が
１であることであり、全ブロックで独立に並列に計算できる。
第ｊ桁からのｋ個の桁からなるブロックｈの桁上げ伝搬条件は、Ph=pjpj+1 … pj+k-1 が１になることで
あり、ブロックｈからの桁上げ Ch+1 は、Ch+1=cj+k∨PhCh となる。ここに cj+k はブロックの最上位の全
加算器からの桁上げ、Ch は一つ下位のブロックからの桁上げである。
図２に示すように、桁上げ飛び越し加算器は、順次桁上げ加算器に桁上げ飛び越し回路を付加した構
成になる。
（pi は全加算器内で計算されるものとしている。）順次桁上げ加算器に比べ、桁上げ飛び越し
回路が増加するだけで、ハードウェア量は比較的少ない。また、規則正しい回路構造になる。特に、ブ
ロックの大きさを同一にすれば、同じブロックの繰り返しにより構成できる。
ある桁で発生した桁上げがいくつか上位のブロックの桁まで伝搬する場合、桁上げは、発生したブロ
ック内を順次上位へ伝搬し、いくつかのブロックを飛び越し、さらに伝搬先の桁が属するブロック内を
順次伝搬する。したがって、桁上げ伝搬に要する時間は、桁上げが二つのブロック内を順次伝搬する時
間といくつかのブロックを飛び越す時間の合計になる。
各ブロックの大きさを √ｎに比例する一定値にすると、ブロックの個数も√ｎに比例し、計算時間
は√ｎにに比例するようになる。素子数は、ブロックの分け方によらず、ｎに比例する。見掛け上、回
路の段数は順次桁上げ加算器より若干大きくなるが、桁上げ信号がバイパスするので、計算時間は小さ
くなる。すなわち、最長経路はフォールスパスになる。
図２：桁上げ飛び越し加算器(上)と桁上げ飛び越し回路(下)
1.3 桁上げ選択加算器
順次桁上げ加算において、隣り合う全加算器の間で受け渡される情報は桁上げであり、０か１の二通
りしかない。そこで、計算を上位と下位に分け、上位では、下位での計算と並行して、下位からの桁上
げが０の場合と１の場合の二通りを同時に計算しておき、下位からの桁上げが確定した時点で、この桁
上げにより、上位の正しい結果を選択するようにすれば高速化が可能である。この考えに基づくのが、
桁上げ選択加算器（carry select adder）である。
図３に示すように、加算器をほぼ同じ桁数の二つのブロックに分け、各ブロックでの加算を順次桁上
げ方式で行えば、上位のブロックでの両方の場合の計算の完了とほぼ同時に下位からの桁上げが確定し、
全体として各ブロックでの計算時間とセレクタ（マルチプレクサ）一段分の計算時間で加算が行える。
2
したがって、順次桁上げ加算に比べ計算時間がおよそ半分になる。
図４に示すように、より多くのブロックに分けることにより、さらに高速化が可能である。すなわち、
最下位を除く各ブロックで、下位からの桁上げが０の場合と１の場合の両方について和と桁上げを計算
しておき、下位からの桁上げによりいずれかを選択する。選択され確定した桁上げが、次のブロックの
セレクタの制御入力になる。
図３：桁上げ選択加算器（２ブロック）
図４：桁上げ選択加算器（多ブロック）
ある桁で発生した桁上げは、発生したブロック内を順次上位へ伝搬し、一つ上位のブロックのセレク
タの制御入力になる。以後、より上位のブロックの和および桁上げが次々と確定する。したがって、加
算に要する時間は、桁上げが一つのブロック内を順次伝搬する時間とセレクタを何段か通過する時間に
なる。
ブロックの大きさを√ｎに比例する一定値にすると、計算時間は √ｎに比例するようになる。素子
数は、ブロックの分け方によらず、ｎに比例する。
1.4 桁上げ先見加算器
加算において、各桁での桁上げは、演算数のそれより下位の桁だけから定まる。したがって、原理的
には、演算数が入力された時点ですべての桁で並列に桁上げを計算できる。この考えに基づくのが、桁
上げ先見加算器（carry look-ahead adder）である。
＋ yiとすると、giが１のときこの桁で桁上げが発生し、piが１のとき
第ｉ桁において、gi=xiyi、pi= xi○
下位からの桁上げが上位に伝搬する。すなわち、上位への桁上げは、ci+1= gi∨piciと表される。これに ci=
gi-1∨pi-1ci-1 を代入すると、ci+1= gi∨pigi-1∨pipi-1ci-1 となる。さらに代入を繰り返すと、
ci+1= gi∨pigi-1∨pipi-1gi-2∨…∨pipi-1…p0c0
3
となる。この式は、ある桁で上位への桁上げが１となるのは、その桁で新たに桁上げが発生する場合と、
下位のどこかの桁で発生した桁上げがその桁まで伝搬しさらに上位に伝搬する場合のいずれかである
ことを示している。すべての桁でこの計算を行えば、すべての桁の桁上げが求まる。しかし、後者の計
算は、桁上げの発生箇所が下位の任意の桁である場合について行う必要がある。したがって、この計算
を各桁で別々に並列に行う純粋な桁上げ先見加算器は、論理ゲートの入力数（ファンイン）やハードウ
ェア量の観点から、数桁程度のものしか構成できない。
第ｊ桁からのｋ個の桁からなるブロックｈの桁上げ生成条件、すなわち、ブロック内で発生した桁上
げがブロックから出力される条件は、Gh=gj+k-1∨p j+k-1g j+k-2∨…∨pj+k-1pj+k-2…pj+1gj が１になることであ
る。また、桁上げ伝搬条件は、Ph（= pj+k-1pj+k-2…pj）が１になることである。Gh と Ph の計算を行う回
路をブロック桁上げ先見回路という。
ブロック内の第 j+i 桁での桁上げ cj+i+1 は、ブロックへの桁上げ入力を Ch とすると、
cj+i+1=gj+i∨pj+igj+i-1∨…∨pj+i…pj+1gj∨pj+i…pj+1pjCh
となる。この計算を行う回路を上記の回路と組み合わせたものをブロック桁上げ先見生成回路という。
４桁（k=4）程度のブロックが一般的である。
＋ c iにより、計算できる。
各桁で桁上げが求まれば、和は、si=pi○
桁上げ先見の考え方は、連続する桁のブロックの間でも成り立つ。すなわち、あるブロックで上位へ
の桁上げが１となるのは、そのブロック内で桁上げが発生する場合と、下位のどこかのブロックで発生
した桁上げがそのブロックまで伝搬しさらに上位に伝搬する場合のいずれかである。したがって、いく
つかの連続するブロックのグループを考えると、上記と全く同じ計算により、ブロックの桁上げ生成／
伝搬条件から、グループにおける桁上げ生成／伝搬条件を計算できる。また、グループへの桁上げ入力
から、グループ内の各ブロック（の最上位桁）での桁上げも上記と同様に計算できる。
この考え方は、さらにグループのグループにも適用できる。したがって、図５に示すように、数桁分
のブロック桁上げ先見生成回路を多段に木状に接続することにより、高速の加算器を構成できる。加算
器は同一の回路から構成され、回路の素子数はｎに比例する。計算時間（回路の段数）は log n に比例
する。木状の構成になるため、一次元配列に較べ、配線などは複雑になる。
図５：木状構造の桁上げ先見加算器
4
２．乗算器
ｎビット符号なし２進整数の乗算について考える。被乗数、乗数、積をそれぞれ X=[xn-1xn-2…x0]、
Y=[yn-1yn-2…y0]、P=[p2n-1 p2n-2…p0]（xi, yi, pi ∊ {0, 1}）とする。
2.1 直並列型乗算器
乗算は、乗数の下位ビットから順に、対応する部分積 X yj 2j を生成し累算していくことによって行
える。すなわち、累算値（中間結果）の初期値 P0 を０とし、Pj+1:= Pj+ X yj 2j という計算を繰り返せば
よい。この乗数の１ビット分の計算を行う回路は、部分積生成回路と加算器で構成できる。これと被乗
数を記憶するレジスタと乗数および中間結果を記憶するレジスタからなる回路で、１ステップに乗数の
１ビット分ずつ計算を行うのが、教科書 180 頁の図 3.5 の乗算器である。乗数についてビット直列に、
被乗数については並列に処理されるので、直並列乗算器と呼ばれる。逐次型乗算器と呼ばれることもあ
る。
部分積生成回路は、X の各ビットと yj の論理積を計算する回路であり、ｎ個の AND ゲートで構成で
きる。１ステップの計算時間は、加算器の計算時間によって決まる。順次桁上げ加算器を用いればｎに
比例し、木状の桁上げ先見加算器などを用いれば log n に比例する。桁上げ保存加算により、計算を大
幅に高速化できる。すなわち、中間結果（累算値）を桁上げ保存形で表し、各ステップでの加算におい
て、部分積と前段からの桁上げと中間和を桁上げ保存方式で加え、新しい桁上げと中間和を計算するよ
うにすればよい。
桁上げ保存加算器を用いれば、１ステップの計算時間はｎに関係なく、AND 一つと全加算器一つ分
になる。加算器のハードウェア量は、順次桁上げ加算器と同じで、桁上げ先見加算器などよりも少なく
て済む。ただし、中間結果を記憶するシフトレジスタの上位半分では、桁上げと中間和からなる桁上げ
保存形を記憶するために、一桁当り２ビット必要である。また、最後に桁上げと中間和を加算し、２進
表現の積を求める計算が必要である。
2.2 配列型乗算器
逐次型乗算を組合せ回路に展開
した並列乗算器が配列型乗算器で
ある。すべての部分積を並列に生
成し、これらを順次、桁上げ保存
加算で加え合わせて行く。配列型
乗算器は、図６に示すように、全
加算器を２次元配列状に並べた構
成になる。回路の段数はｎに比例
する。回路の素子数は n2 に比例す
る。規則正しいセル配列構造でレ
イアウトが容易である。最終加算
は桁上げ先見加算などにより高速
化できる。
図６：配列型乗算器
5
2.3 ２次の Booth の方法
２次の Booth の方法により、生成される部分積の個
表２：２ビットの Booth の方法における
乗数のリコード規則
y2j+1
y2j
y2j-1
．
yj
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
2
という計算によって求める。これは、2=4-2 であること
1
0
0
-2
を用いている。表２に２次の Booth の方法における乗
1
0
1
-1
数のリコード規則を示す。たとえば、
1
1
0
-1
1
1
1
0
数をおよそ半分（n/2 個）にすることができる。
２ 次 の Booth の 方 法 で は 、 乗 数 を 桁 集 合 が
{-2,-1,0,1,2} の４進ＳＤ表現にリコードする。リコード
．
された乗数（４進数）のｊ桁目 yj は、乗数の２ビット
y2j+1、y2j と一つ下位のビット y2j-1 より、
．
yj=-2 y2j+1+ y2j + y2j-1
0111101011111001→2 0 -1 -1 0 0 -2 1
と変換される。この変換は、乗数の２ビットずつの約
n/2 個のグループの各々で、他のグループとは独立に行える。
前節で述べた配列型乗算器に適用すると、配列部での計算時間がおよそ半分になる。桁上げ保存加算
器の個数もおよそ半分になるが、乗数の変換回路が必要になり、また、部分積生成回路も複雑になる。
2.4 Wallace 木を用いた乗算
桁上げ保存加算では、三つの２進数をそれらの
合計を保存して二つの２進数に変換していること
になる。すなわち、A、B、C という三つの２進
数を桁上げ保存加算器に入力すれば、R、S とい
う二つの２進数が得られ、A+B+C=R+S となる。
この計算が、ビット長に関係なく、全加算器一つ
分の計算時間で行える。
乗算において、ｎ個の部分積に対して、n/3 個
の桁上げ保存加算器を用い、上記の計算を並列に
行えば、部分積の個数が 2n/3 になる。この計算を
およそ log3/2 n 回繰り返えせば、部分積が二数に
なる。最後に、この二数を桁上げ先見加算器など
で加え合わせる。これが Wallace 木を用いた乗算
である。
図７に Wallace 木を用いた乗算器の構成を示
す。回路の段数は log n に比例し、高速である。
素子数は配列型乗算器と大差なく、
n2 に比例する。
しかし、配線が複雑で、レイアウトが複雑になる。
一つの桁上げ保存加算器を飛び越す配線の本数は、
ビットスライス当たり最大 log n に比例する。
図７：Wallace 木を用いた乗算器
6
Wallace 木を用いた乗算法にも、２次の Booth の方法を採用できる。しかし、部分積の個数が約半
分になっても、桁上げ保存加算の段数は一段ないし二段減るだけである。２次の Booth の方法の採用
にあたっては、計算時間およびハードウェア量について、乗数の変換および部分積の生成のために増加
する分と、桁上げ保存加算の数が減り減少する分を十分に考慮する必要がある。
2.5 冗長２進加算木を用いた乗算
桁上げ保存加算と同様に繰り返し加算を高速化する方法として、冗長２進表現の利用がある。冗長２
進表現は基数２、桁集合{-1,0,1}の位取り記数法である。以降、-1 を T で表す。一つの数に対していく
つかの表現が存在する。たとえば「５」は４桁で、[0101]、[011T]、[1T01]、[1T1T]、[10TT]の五通り
の表現がある。この冗長性を利用し、二数の加算において桁上げの伝搬をなくすことができる。
二つの冗長２進数 X=[xn-1xn-2…x0]と Y=[yn-1yn-2…y0]の加算について考える。桁上げ伝搬のない加算は
二つのステップで行う。第１ステップでは、各桁で、xi+yi=2ci+1+di を満たすように、中間桁上げ ci+1（∊
{T, 0, 1}）と中間和 di（∊ {T, 0, 1}）を求める。第２ステップでは、各桁で、中間和 di と一つ下位の桁か
らの中間桁上げ ci を加え合わせ、和 si（∊ {T, 0, 1}）を得る。第１ステップでは、第２ステップで新た
桁 i で、被加数と加数の一方が 1 で他方が 0 のとき、
な桁上げが生じないように ci+1 および di を定める。
第１ステップで ci+1 を 0、di を 1 とすると、ci が 1 なら、第２ステップにおいて新たな桁上げが生じる。
そこで、ci が 1 になる可能性がある場合は、ci+1 を 1、di を T とする。逆に、ci が T になる可能性のあ
る場合は、ci+1 を 0、di を 1 とする。これは、「１」を２桁で [01]と[1T] の２通りに表すことができる
ことを利用している。ci が 1 あるいは T になる可能性は、一つ下位の桁の被加数と加数、すなわち、xi-1
と yi-1 を調べることにより知ることができる。
表３に、桁上げ伝搬のない加算の各桁での計算規則の例を示す。
表３．冗長２進表現における桁上げ伝搬のない加算の各桁での計算規則の例
ci+1, di
ステップ１
ステップ２
si
xi|yi
T
0
1
di|ci
T
0
1
T
T,0
*0,T / T,1
0,0
T
×
T
0
0
*0,T / T,1
0,0
*1,T / 0,1
0
T
0
1
1
0,0
*1,T / 0,1
1,0
1
0
1
×
*： xi-1 と yi-1 の両方とも非負／少なくとも一方が負
×：起こらない
図 10 に、表３の規則による冗長２進加算の例を示す。
1 0 T 0 T 0 0
被加数
+
加数
0 1 0
中間和
中間桁上げ
和
1 T 1 0 0
+
1 1 T
0 T T 1
1 T 0 0 0
T
0
1 0 T
1 T 1 0 0 0
T 0 0
図 10：冗長２進加算の例
7
ステップ１
ステップ２
ｎ桁の冗長２進加算器は一桁分の冗長２進加算回路をｎ個並べることにより構成できる。回路の段数
はｎに依らない定数となる。回路の素子数はｎに比例する。
通常の２進数は、特殊な冗長２進数と見なすことができる。加算において、被加数と加数の一方が通
常の２進数である場合、上記の一般の冗長２進数同士の
加算よりも計算が簡単になり、第１ステップにおいて、一つ下位の桁を調べることなく、中間桁上げと
中間和を決定できる。もちろん、被加数と加数の両方が通常の２進数であれば、計算はもっと簡単にな
る。
２進数は、そのままで冗長２進数であり、２進表現から冗長２進表現への変換には、計算の必要がな
い。
（２の補数表現の場合は、最上位ビットが 1 なら、これを T にする。
） 一方、冗長２進表現から２
進表現への変換には、通常の２進減算が必要である。すなわち、冗長２進表現で 1 の桁を集めた２進数
から、T の桁を集めた２進数を減ずればよい。たとえば、[1T01] は、[1001]－[0100] の減算により、
[00101]に変換される。
（一般に２の補数表現の２進数に変換され、符号ビットが必要になる。）この減
算は通常の２進減算であり、桁借りが伝搬する。
冗長２進加算木を用いた乗算では、部分積を冗長２進数とみなし、冗長２進加算を基本計算として、
二分木状に加え合わせる。最後に積を冗長２進表現から２進表現に変換する。変換に高速の加算器を用
いれば、乗算器全体の回路段数は log n に比例する。冗長２進加算木を用いた乗算器は、高速でかつレ
イアウトが比較的容易である。素子数は n2 に比例する。
8
© Copyright 2024 ExpyDoc
