加算器

加算器は最も基本的な回路で、減算は2の補数の加算として、乗算は加算の繰り返しで、除算は減算の繰り返しで計算できるので、加算器を高速化することで、四則演算すべてを高速化することができる。

半加算器 (half adder)

2進数の加算を行う論理回路で、繰り上がりを考慮せず単に2つの和を求める。

全加算器 (full adder)

2進数の加算を行う論理回路で、下の桁からのくり上がりを考慮して3つの和を求める。 CMOSではANDゲートやORゲートを直接実装することは非効率的。XORゲートはトランスミッションゲートとNOTゲートで実装できるので、ANDゲートやORゲートをNANDゲートやNORゲートで置き換えることで実装する。

RC遅延モデルによる全加算器の遅延の計算

2入力以上のゲートではRC遅延モデルは煩雑になり計算が難しい。

単位遅延による遅延の計算

CMOSゲート1個あたりの伝播遅延を1と仮定する。 ゲートの規模や複雑さによらず遅延は全て同じだとみなすことで、おおよその回路の伝播遅延を求める。

  • XORゲート
    • NOTゲートとトランスミッションゲートから成る
    • 単位遅延は2
  • 出力の遅延は最大でXORゲートを2つ通過するから単位遅延は4
  • 桁上がり出力の遅延はXORゲートとNANDゲート2つを通過するから同じく単位遅延は4
    • AOI21を複合ゲートで実装することにより、単位遅延を2に抑えられる

桁上伝播加算器

最も基本的な加算器。 必要な桁数だけ全加算器を並べ、下位桁の桁揚げ出力を上位桁に繋げたもので、2進数の筆算をそのまま回路にしたらこうなる。

伝播遅延は で、回路規模も全加算器がn個繋がったものであるから 。 最下位桁の全加算器に繋がる桁上げ入力は非負整数の加算の範囲では不要だが、減算器に拡張する際に必要になる。

桁上伝播加算器のクリティカルパスは桁上げ伝播であり、これをできるだけ減らすのが目標になる。

桁上選択加算器

桁を上半分とした半分に分けて、独立に加算を実行する。 上半分は、桁上げ入力が0の場合と1の場合を並列にどちらも計算しておき、確定したらセレクタでどちらかの結果を選択する。 桁上伝播加算器に比べると、遅延は約半分になる。 セレクタ間の桁上げ伝播は逐次的なままなので、分割数を増やせば増やすほど高速になるわけではない。