付録 A
加算回路
本章では基本的な算術演算回路である加算回路について述べる．ハードウェアで 扱う加算回路は大きく桁上げ伝搬加算器と桁上げ保存加算器に分けられる．以降，そ れぞれについて述べる．
げが伝搬するため，ビット長が大きくなるとより大きな遅延が生じる．したがって，
CPA の高速化の際には，この桁上げをいかに高速に行うかが問題となる．次に，い くつかの代表的な CPA を示す．
A.2.1 順次桁上げ加算器 (Ripple Carry Adder)
FA を単純に直列接続したものを順次桁上げ加算器 (Ripple Carry Adder，RCA) と呼ぶ．RCAの構成を図A.1に示す．RCA はその構造上n ビットの加算を行うた
FA s i +1
c i +1 FA
s i -1
c i-1 FA
y i x i
s i
c i
x i -1 y i -1 y i +1
x i +1 c i +2
図A.1 順次桁上げ加算器 (Ripple Carry Adder，RCA)の構成
めに O(n) の遅延時間が必要であり，加算器の中では最も性能が低い．ただし，演 算器の構造が単純であることからゲート数が少なく，低面積での実装が可能である．
加えて FA の配列が規則的であるためマスク・レベルでの実装において配置配線が 容易であるという利点がある．
A.2.2 桁上げ先見加算器 (Carry Look-ahead Adder)
桁上げ先見加算器は各桁における桁上げを並列に計算し，高速な桁上げを行うこと で加算の遅延時間を削減した加算器である．今，nビットの値 x と y の加算を考え る．i桁において桁上げが発生するのはxi·yi が1 の場合である．また，下位桁から i 桁へ伝搬してきた桁上げ ci がさらに ci+1 へ伝搬するのは，桁上げci が1であり，
かつ xi とyi のどちらかが 1 の場合である．したがって，上記の 2 つの場合のどち らかが成り立つとき，i 桁から i+ 1 桁へ桁上げが発生する．これを論理式で表すと ci+1 =xi·yi+ (xi⊕yi)·ci (A.5)
=gi+pi·ci (A.6)
となる．ここで，gi は i 桁において発生する桁上げを意味することからジェネレー タ (Generator) と呼ばれている．また，pi は下位桁からの桁上げが上位へ伝搬する ことを意味していることから，プロパゲータ (Propagator) と呼ばれている．
式(A.6) において，ci を再帰的に代入していくとi 桁における桁上げを決定する ことができる．この様子を次式に示す．
ci+1 =gi+pi·ci (A.7)
=gi+pi·(gi−1+pi−1·ci−1) (A.8)
=gi+pi·(gi−1+pi−1·(gi−2+pi−2·ci−2)) (A.9)
=gi+pi·(gi−1+pi−1·(gi−2+pi−2·((. . .((g0+p0·c0)). . .))(A.10)
=gi+pi·gi−1+pi·pi−1·gi−2+· · ·pi·pi−1· · ·p0·c0 (A.11) n 桁の全ての桁に対して式(A.11)を用いることで，全ての桁の桁上げを並列に求め ることができる．各桁の桁上げを並列に求める桁上げ先見回路 (Carry Look-ahead Circuit，CLC) を用いて図A.2に示すような桁上げ先見加算器 (Carry Look-ahead
Adder，CLA) を構成することができる．ただし，各桁の加算は FA ではなく HA
で行う．
HA HA
yi xi
si
xi -1 yi -1 yi +1
xi +1
CLC
si +1 si -1
HA
HA HA
HA
ci -1 ci
ci +1 ci +2
gi -1 pi -1
gi gi +1 pi pi +1
HA
HA g0 p0
x0 y0
c0
s0
図A.2 桁上げ先見加算器 (Carry Look-ahead Adder，CLA)の構成
A.2.3 ブロック桁上げ先見加算器 (Block Carry Look-ahead Adder)
図A.2に示した CLA は上位桁になるほど桁上げ先見の論理が複雑になるため，
ビット長が大きい時にハードウェア量が膨大になる．そこで，nビットの数をk ビッ トずつのブロックに分け b 個のブロックを作り，各ブロック内で桁上げ先見回路を 用いる(Block Carry Look-ahead Circuit，BCLC)．すると，bブロック目から出力 される桁上げ Gb は式(A.11)と同様の導出で
Gb =gi+k−1+pi+k−1·gi+k−2+·+pi+k−1·pi+k−2· · · ·pi+1·ci (A.12)
と表される．また，b ブロック内で桁上げが発生し，それがb ブロックの外に伝わる 条件 Pb は
Pb =pi+k·pi+k−1· · · · ·pi+1·pi (A.13) である．b ブロック内の ci+k+1 桁目における桁上げは，下位ブロックからの桁上げ を Ch とすると
ci+k+1 =gi+k+pi+k·gi+k−1+· · ·
+pi+k· · ·pi+k·gi+pi+k· · ·pi+1·pi·Ch (A.14) で表される．
このようなブロック分けを行うことで，ブロック間では桁上げ伝搬が発生するが，
ブロック内部では桁上げを抑制することができる．図A.3にBCLCを用いたブロッ ク桁上げ先見加算器 (Block Carry Look-ahead Adder，BCLA) の構成を示す．前
HA HA
yi xi
si BCLC
HA
HA HA
HA
ci ci +1
gi pi
HA HA
x0 y0
BCLC
s0 HA
HA HA
HA
c0
c1
g0 p0
図A.3 ブロック桁上げ先見加算器(Block Carry Look-ahead Adder，BCLA)の構成
述のとおり，k が大きくなると回路規模の観点から加算器の構成が難しくなるため，
一般に k は 4などの小さな数にする．
BCLA から出力される Gb，Pb を用いて図A.4のように桁上げ先見回路を木構造 に組み上げた桁上げ先見加算器を作ることができる．図に示した木構造の BCLA は 2 ブロックを 1 つのまとまりとして下段の桁上げ先見回路を生成している．k 個の ブロックを 1 つのまとまりとし下段の桁上げ先見回路を生成してゆくことでn ビッ ト加算器の遅延時間を O(logkn) にすることができる．
近年では多くの場合，加算回路として BCLA が利用されるため，単に CLA と いった場合にもこの BCLA を意味することが多い．