JPH11143685A - キャリー・スキップ・アダー - Google Patents
キャリー・スキップ・アダーInfo
- Publication number
- JPH11143685A JPH11143685A JP10091837A JP9183798A JPH11143685A JP H11143685 A JPH11143685 A JP H11143685A JP 10091837 A JP10091837 A JP 10091837A JP 9183798 A JP9183798 A JP 9183798A JP H11143685 A JPH11143685 A JP H11143685A
- Authority
- JP
- Japan
- Prior art keywords
- adder
- circuit
- carry
- group
- output
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
- G06F7/50—Adding; Subtracting
- G06F7/505—Adding; Subtracting in bit-parallel fashion, i.e. having a different digit-handling circuit for each denomination
- G06F7/506—Adding; Subtracting in bit-parallel fashion, i.e. having a different digit-handling circuit for each denomination with simultaneous carry generation for, or propagation over, two or more stages
- G06F7/508—Adding; Subtracting in bit-parallel fashion, i.e. having a different digit-handling circuit for each denomination with simultaneous carry generation for, or propagation over, two or more stages using carry look-ahead circuits
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Pure & Applied Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- Mathematical Optimization (AREA)
- General Engineering & Computer Science (AREA)
- Synchronisation In Digital Transmission Systems (AREA)
Abstract
(57)【要約】 （修正有）
【課題】高速な２段以上のキャリー・スキップ・アダー
を提供すること。 【解決手段】複数のリプル・アダーを有し、この複数の
リプル・アダーのうち少なくとも一部のリプル・アダー
はグループ分けされており、キャリー信号はあるグルー
プか１つ上位のグループへ伝達されている。そして、あ
るグループから１つ上位のグループへのキャリー信号Ｃ
１と、１つ上位のグループ内の全アダーの出力が１ある
か否かを表す信号Ｆと、１つ上位のグループ内において
最も上位のリプル・アダーに関連するキャリー信号Ｃ２
とを用いて、Ｃ＝Ｃ２＋Ｆ・Ｃ１を計算する回路を有す
る。
を提供すること。 【解決手段】複数のリプル・アダーを有し、この複数の
リプル・アダーのうち少なくとも一部のリプル・アダー
はグループ分けされており、キャリー信号はあるグルー
プか１つ上位のグループへ伝達されている。そして、あ
るグループから１つ上位のグループへのキャリー信号Ｃ
１と、１つ上位のグループ内の全アダーの出力が１ある
か否かを表す信号Ｆと、１つ上位のグループ内において
最も上位のリプル・アダーに関連するキャリー信号Ｃ２
とを用いて、Ｃ＝Ｃ２＋Ｆ・Ｃ１を計算する回路を有す
る。
Description
【０００１】
【発明の属する技術分野】本発明は、バイナリ・アダー
に関し、より詳しくは、多ビット数のキャリー・スキッ
プ・アダーに関する。
に関し、より詳しくは、多ビット数のキャリー・スキッ
プ・アダーに関する。
【０００２】
【従来の技術】ＲＳＡ暗号系を高速に処理するために
は、１０２４ビットから２０４８ビットという非常にビ
ット数の多いバイナリ・アダーを高速に動作させる必要
がある。しかし、以下で述べる従来技術では、動作速度
が下位から送られてくるキャリー信号によって制限さ
れ、所望の動作速度を得ることができなかった。以下、
従来技術について述べる。
は、１０２４ビットから２０４８ビットという非常にビ
ット数の多いバイナリ・アダーを高速に動作させる必要
がある。しかし、以下で述べる従来技術では、動作速度
が下位から送られてくるキャリー信号によって制限さ
れ、所望の動作速度を得ることができなかった。以下、
従来技術について述べる。
【０００３】（１）リプル・キャリー方式 リプル・アダーはビット数に等しい数のフル・アダーを
並べて作ることができる。このリプル・キャリー方式の
回路は簡単だが、最大ゲート・ディレイはビット数分の
ゲート・ディレイとなり、所望の動作速度を確保するこ
とは非常に困難である。
並べて作ることができる。このリプル・キャリー方式の
回路は簡単だが、最大ゲート・ディレイはビット数分の
ゲート・ディレイとなり、所望の動作速度を確保するこ
とは非常に困難である。
【０００４】（２）キャリー・モニタ方式 長大なリプル・アダーのゲート・ディレイは、Ｎビット
について最大Ｎ段のゲート・ディレイとなるため、保証
できる動作速度はビット数に反比例して遅くなる。しか
し、キャリーの伝搬が必要な場合は、加算される２つの
数Ｘ，Ｙが排他的に１で、しかも下位からキャリーが来
る場合だけなので、このような条件が連続していること
はまれである。１０２４ビットではこのような条件はせ
いぜい連続して１１ビット程度と計算されていて、平均
動作速度は保証できる動作速度の１００倍を期待でき
る。この方式は、キャリー・モニタ回路を付けることに
より、キャリーが連続する時だけ待ち時間を入れるとい
うものである。しかし、このキャリー・モニタ方式は、
回路サイズが大きく、消費電力が大きくなること、そし
て潜在的に動作が不安定になる危険性という欠点があ
る。
について最大Ｎ段のゲート・ディレイとなるため、保証
できる動作速度はビット数に反比例して遅くなる。しか
し、キャリーの伝搬が必要な場合は、加算される２つの
数Ｘ，Ｙが排他的に１で、しかも下位からキャリーが来
る場合だけなので、このような条件が連続していること
はまれである。１０２４ビットではこのような条件はせ
いぜい連続して１１ビット程度と計算されていて、平均
動作速度は保証できる動作速度の１００倍を期待でき
る。この方式は、キャリー・モニタ回路を付けることに
より、キャリーが連続する時だけ待ち時間を入れるとい
うものである。しかし、このキャリー・モニタ方式は、
回路サイズが大きく、消費電力が大きくなること、そし
て潜在的に動作が不安定になる危険性という欠点があ
る。
【０００５】（３）キャリー・スキップ方式 バイナリ・アダーをいくつかのブロックに分割して、各
々の部分について加算を済ませてから、下位からのキャ
リー信号で＋１の補正をすることができる。この方式に
従うバイナリ・アダーを、キャリー・スキップ・アダー
という。このキャリー・スキップ方式は、回路は複雑に
なるが、消費電力が少なく、動作も安定している。回路
の複雑さについては、リプル・アダーより大きく、キャ
リー・モニター方式によるアダーと同程度である。
々の部分について加算を済ませてから、下位からのキャ
リー信号で＋１の補正をすることができる。この方式に
従うバイナリ・アダーを、キャリー・スキップ・アダー
という。このキャリー・スキップ方式は、回路は複雑に
なるが、消費電力が少なく、動作も安定している。回路
の複雑さについては、リプル・アダーより大きく、キャ
リー・モニター方式によるアダーと同程度である。
【０００６】１段のキャリー・スキップ方式では、Ｎビ
ットの加算について、Ｎ≦ｎ（ｎ＋２）／２＋２なるｎ
を求めて、このｎに対して（ｎ＋３）がゲート・ディレ
イとなる。１０２４ビットでは、Ｎ＝１０２４でｎ＝４
５、すなわち、４８ゲート・ディレイとなる。
ットの加算について、Ｎ≦ｎ（ｎ＋２）／２＋２なるｎ
を求めて、このｎに対して（ｎ＋３）がゲート・ディレ
イとなる。１０２４ビットでは、Ｎ＝１０２４でｎ＝４
５、すなわち、４８ゲート・ディレイとなる。
【０００７】このようなキャリー・スキップ方式につい
ては、例えば、情報処理第３７巻第１号ｐ８０−８５，
情報処理学会発行、１９９６年１月に記載されている。
ては、例えば、情報処理第３７巻第１号ｐ８０−８５，
情報処理学会発行、１９９６年１月に記載されている。
【０００８】また、ＩＢＭ Technical Disclosure Bul
letin Vol. 27, No.11, April 1985, pages 6785-6787
には、スキップするキャリーを２段にすることを記載し
ている。しかし、バイナリー・アダーのブロック分けを
シンメトリックに行っているため、ビット数が少ない場
合には高速であるが、ビット数が多くなると、キャリー
・スキップの効果が少なくなって、動作速度が相対的に
遅くなってしまう。
letin Vol. 27, No.11, April 1985, pages 6785-6787
には、スキップするキャリーを２段にすることを記載し
ている。しかし、バイナリー・アダーのブロック分けを
シンメトリックに行っているため、ビット数が少ない場
合には高速であるが、ビット数が多くなると、キャリー
・スキップの効果が少なくなって、動作速度が相対的に
遅くなってしまう。
【０００９】
【発明が解決しようとする課題】よって、本発明の目的
は、スキップするキャリーを２段以上にし、より高速な
動作速度を可能とするバイナリ・アダーを提供すること
である。
は、スキップするキャリーを２段以上にし、より高速な
動作速度を可能とするバイナリ・アダーを提供すること
である。
【００１０】また、キャリー・スキップ・アダーを応用
した高速マルチプライアを提供することも目的である。
した高速マルチプライアを提供することも目的である。
【００１１】
【課題を解決するための手段】本発明の第１の態様であ
る、Ｎ段（Ｎは３以上の整数）キャリー・スキップ・ア
ダーは、複数のリプル・アダーを有し、この複数のリプ
ル・アダーのうち少なくとも一部のリプル・アダーはグ
ループ分けされている。キャリー信号はあるグループか
ら１つ上位のグループへ伝達されており、グループ内に
複数のリプル・アダーが存在する場合には、当該グルー
プ内のリプル・アダー間でもキャリー信号が伝達されて
いる。そして、あるグループから１つ上位のグループへ
のキャリー信号Ｃ１と、１つ上位のグループ内の全アダ
ーの出力が１であるか否かを表す信号Ｆと、１つ上位の
グループ内において最も上位のリプル・アダーに関連す
るキャリー信号Ｃ２とを用いて、Ｃ＝Ｃ２＋Ｆ・Ｃ１を
計算する回路を有する。また、グループ内に３以上のリ
プル・アダーが存在する場合には、当該グループ内の複
数のリプル・アダーはＮ−２段階のレベルでさらにグル
ープ化されており、当該最も上位のリプル・アダーが属
する、最下段であるレベル１のグループ内におけるリプ
ル・アダー間で前記最も上位のリプル・アダーに伝達さ
れてきたキャリー信号Ｃ３0と、前記最も上位のリプル
・アダーが属する、レベルｎのグループに、レベルｎの
隣接するグループから伝達されてきたキャリー信号Ｃ３
n（１≦ｎ≦Ｎ−２）と、前記最も上位のリプル・アダ
ーのキャリー信号Ｃ４と、前記最も上位のリプル・アダ
ーの全アダーの出力が１であるか否かを表す信号Ｆ２0
と、キャリー信号Ｃ３nを出力している回路に関連する
リプル・アダーより上位で前記最も上位のリプル・アダ
ーまでの全アダーの出力が１であるか否かを表す信号Ｆ
２nとを用いて、Ｃ２1＝Ｃ４＋Ｆ２0・Ｃ３0を計算する
回路と、Ｃ２n+ 1＝Ｃ２n＋Ｆ２n・Ｃ３n（１≦ｎ≦Ｎ−
２，Ｃ２N-1＝Ｃ２）を計算する回路とを含む。これに
より３段以上のキャリー・スキップ・アダーが構成さ
れ、ゲート・ディレイを大幅に削減できる。キャリー信
号は上位に伝搬されるだけで下位に戻されることはな
い。３段キャリー・スキップ・アダーの場合には１段階
のレベルでさらにグループ化されており、Ｃ２1＝Ｃ４
＋Ｆ２0・Ｃ３0を計算する回路と、Ｃ２2＝Ｃ２＝Ｃ1＋
Ｆ２1・Ｃ３1を計算する回路とを含む。４段キャリー・
スキップ・アダーの場合には２段階のレベルでさらにグ
ループ化されており、Ｃ２1＝Ｃ４＋Ｆ２0・Ｃ３0を計
算する回路と、Ｃ2＝Ｃ1＋Ｆ２1・Ｃ３1を計算する回路
と、Ｃ２3＝Ｃ２＝Ｃ2＋Ｆ２2・Ｃ３2を計算する回路と
を含む。なお、本発明の第１の態様は、例えば図３にお
ける、ＡＮＤ回路４３５とＯＲ回路４３７の組、ＡＮＤ
回路４４１とＯＲ回路４４３の組、ＡＮＤ回路４４５と
ＯＲ回路４４７の組、を表している。Ｃ＝Ｃ２＋Ｆ・Ｃ
１、Ｃ２1＝Ｃ４＋Ｆ２0・Ｃ３0、及びＣ２n+1＝Ｃ２n
＋Ｆ２n・Ｃ３nは、あるアダーのキャリーは、そのアダ
ーのキャリーが発生する場合、又はそのアダーが含まれ
るブロックの全てのアダーが１を出力し且つ前のブロッ
クからキャリーが伝搬されている場合に生成されること
を示す。また、「少なくとも一部のリプル・アダー」と
いう文言を用いているのは、本構成のキャリー・スキッ
プ・アダーの下位又は上位に単純なリプル・アダーや他
の方式に基づくアダーを付加する場合も考えられるため
である。特に、マルチプライア中のアダーでは、本発明
の方式によるアダーより下位に、２種類のキャリーが独
立に発生する場合に対応する、本方式の変形の回路が連
結される。なお、前記１つ上位のグループに属するリプ
ル・アダーの数は、前記あるグループに属するリプル・
アダーの数以上とすることもできる。よって、ビット数
が多くなった場合でも飛躍的に加算速度を上げることが
できる。
る、Ｎ段（Ｎは３以上の整数）キャリー・スキップ・ア
ダーは、複数のリプル・アダーを有し、この複数のリプ
ル・アダーのうち少なくとも一部のリプル・アダーはグ
ループ分けされている。キャリー信号はあるグループか
ら１つ上位のグループへ伝達されており、グループ内に
複数のリプル・アダーが存在する場合には、当該グルー
プ内のリプル・アダー間でもキャリー信号が伝達されて
いる。そして、あるグループから１つ上位のグループへ
のキャリー信号Ｃ１と、１つ上位のグループ内の全アダ
ーの出力が１であるか否かを表す信号Ｆと、１つ上位の
グループ内において最も上位のリプル・アダーに関連す
るキャリー信号Ｃ２とを用いて、Ｃ＝Ｃ２＋Ｆ・Ｃ１を
計算する回路を有する。また、グループ内に３以上のリ
プル・アダーが存在する場合には、当該グループ内の複
数のリプル・アダーはＮ−２段階のレベルでさらにグル
ープ化されており、当該最も上位のリプル・アダーが属
する、最下段であるレベル１のグループ内におけるリプ
ル・アダー間で前記最も上位のリプル・アダーに伝達さ
れてきたキャリー信号Ｃ３0と、前記最も上位のリプル
・アダーが属する、レベルｎのグループに、レベルｎの
隣接するグループから伝達されてきたキャリー信号Ｃ３
n（１≦ｎ≦Ｎ−２）と、前記最も上位のリプル・アダ
ーのキャリー信号Ｃ４と、前記最も上位のリプル・アダ
ーの全アダーの出力が１であるか否かを表す信号Ｆ２0
と、キャリー信号Ｃ３nを出力している回路に関連する
リプル・アダーより上位で前記最も上位のリプル・アダ
ーまでの全アダーの出力が１であるか否かを表す信号Ｆ
２nとを用いて、Ｃ２1＝Ｃ４＋Ｆ２0・Ｃ３0を計算する
回路と、Ｃ２n+ 1＝Ｃ２n＋Ｆ２n・Ｃ３n（１≦ｎ≦Ｎ−
２，Ｃ２N-1＝Ｃ２）を計算する回路とを含む。これに
より３段以上のキャリー・スキップ・アダーが構成さ
れ、ゲート・ディレイを大幅に削減できる。キャリー信
号は上位に伝搬されるだけで下位に戻されることはな
い。３段キャリー・スキップ・アダーの場合には１段階
のレベルでさらにグループ化されており、Ｃ２1＝Ｃ４
＋Ｆ２0・Ｃ３0を計算する回路と、Ｃ２2＝Ｃ２＝Ｃ1＋
Ｆ２1・Ｃ３1を計算する回路とを含む。４段キャリー・
スキップ・アダーの場合には２段階のレベルでさらにグ
ループ化されており、Ｃ２1＝Ｃ４＋Ｆ２0・Ｃ３0を計
算する回路と、Ｃ2＝Ｃ1＋Ｆ２1・Ｃ３1を計算する回路
と、Ｃ２3＝Ｃ２＝Ｃ2＋Ｆ２2・Ｃ３2を計算する回路と
を含む。なお、本発明の第１の態様は、例えば図３にお
ける、ＡＮＤ回路４３５とＯＲ回路４３７の組、ＡＮＤ
回路４４１とＯＲ回路４４３の組、ＡＮＤ回路４４５と
ＯＲ回路４４７の組、を表している。Ｃ＝Ｃ２＋Ｆ・Ｃ
１、Ｃ２1＝Ｃ４＋Ｆ２0・Ｃ３0、及びＣ２n+1＝Ｃ２n
＋Ｆ２n・Ｃ３nは、あるアダーのキャリーは、そのアダ
ーのキャリーが発生する場合、又はそのアダーが含まれ
るブロックの全てのアダーが１を出力し且つ前のブロッ
クからキャリーが伝搬されている場合に生成されること
を示す。また、「少なくとも一部のリプル・アダー」と
いう文言を用いているのは、本構成のキャリー・スキッ
プ・アダーの下位又は上位に単純なリプル・アダーや他
の方式に基づくアダーを付加する場合も考えられるため
である。特に、マルチプライア中のアダーでは、本発明
の方式によるアダーより下位に、２種類のキャリーが独
立に発生する場合に対応する、本方式の変形の回路が連
結される。なお、前記１つ上位のグループに属するリプ
ル・アダーの数は、前記あるグループに属するリプル・
アダーの数以上とすることもできる。よって、ビット数
が多くなった場合でも飛躍的に加算速度を上げることが
できる。
【００１２】本発明の第２の態様であるキャリー・スキ
ップ・アダーは、複数のリプル・アダーを有し、当該複
数のリプル・アダーのうち少なくとも一部のリプル・ア
ダーはグループ分けされており、キャリー信号はあるグ
ループから１つ上位のグループへ伝達されており、前記
あるグループから前記１つ上位のグループへのキャリー
信号Ｃ１と、前記１つ上位のグループ内の全アダーの出
力が１であるか否かを表す信号Ｆと、前記１つ上位のグ
ループ内において最も上位のリプル・アダーに関連する
キャリー信号Ｃ２とを用いて、Ｃ＝Ｃ２＋Ｆ・Ｃ１を計
算する回路を有する。また、グループ内に複数のリプル
・アダーが存在する場合には、当該グループ内の複数の
リプル・アダー間でもキャリー信号が伝達されており、
前記最も上位のリプル・アダーより１つ下位のリプル・
アダーに関連するキャリー信号Ｃ３1と、前記最も上位
のリプル・アダーのキャリー信号Ｃ４と、前記最も上位
のリプル・アダーの全アダーの出力が１であるか否かを
表す信号Ｆ２1とを用いて、Ｃ２＝Ｃ４＋Ｆ２1・Ｃ３1
を計算する回路を含む。これにより２段キャリー・スキ
ップ・アダーが構成され、ゲート・ディレイが大幅に削
減される。キャリー信号は上位に伝搬されるだけで、下
位に戻されることはない。Ｃ＝Ｃ２＋Ｆ・Ｃ１を計算す
る回路は、例えば図１では、ＡＮＤ回路７１及びＯＲ回
路７３であり、Ｃ２＝Ｃ４＋Ｆ２1・Ｃ３1を計算する回
路は、ＡＮＤ回路６７及びＯＲ回路６９である。なお、
ハーフ・アダー１１及びフル・アダー１３で構成される
リプル・アダーと、ハーフ・アダー１５及びフル・アダ
ー１７で構成されるリプル・アダーとは一つのグループ
を構成している。このグループ内では２つのリプル・ア
ダーが存在するので、グループ間で伝達されるキャリー
とグループ内で伝達される、２本のキャリーが存在す
る。なお、前記１つ上位のグループよりさらに１つ上位
のグループ中の最下位のリプル・アダー内において最下
位アダーの出力Ｓ０とＣとの排他的論理和を計算する回
路と、当該最下位アダーより１つ上位のアダーの出力Ｓ
１と、Ｃ及びＳ０の論理積との排他的論理和を計算する
回路とをさらに有する。この排他的論理和の出力が、当
該最下位アダーの最終的な出力と、最下位アダーより１
つ上位のアダーの最終的な出力となる。
ップ・アダーは、複数のリプル・アダーを有し、当該複
数のリプル・アダーのうち少なくとも一部のリプル・ア
ダーはグループ分けされており、キャリー信号はあるグ
ループから１つ上位のグループへ伝達されており、前記
あるグループから前記１つ上位のグループへのキャリー
信号Ｃ１と、前記１つ上位のグループ内の全アダーの出
力が１であるか否かを表す信号Ｆと、前記１つ上位のグ
ループ内において最も上位のリプル・アダーに関連する
キャリー信号Ｃ２とを用いて、Ｃ＝Ｃ２＋Ｆ・Ｃ１を計
算する回路を有する。また、グループ内に複数のリプル
・アダーが存在する場合には、当該グループ内の複数の
リプル・アダー間でもキャリー信号が伝達されており、
前記最も上位のリプル・アダーより１つ下位のリプル・
アダーに関連するキャリー信号Ｃ３1と、前記最も上位
のリプル・アダーのキャリー信号Ｃ４と、前記最も上位
のリプル・アダーの全アダーの出力が１であるか否かを
表す信号Ｆ２1とを用いて、Ｃ２＝Ｃ４＋Ｆ２1・Ｃ３1
を計算する回路を含む。これにより２段キャリー・スキ
ップ・アダーが構成され、ゲート・ディレイが大幅に削
減される。キャリー信号は上位に伝搬されるだけで、下
位に戻されることはない。Ｃ＝Ｃ２＋Ｆ・Ｃ１を計算す
る回路は、例えば図１では、ＡＮＤ回路７１及びＯＲ回
路７３であり、Ｃ２＝Ｃ４＋Ｆ２1・Ｃ３1を計算する回
路は、ＡＮＤ回路６７及びＯＲ回路６９である。なお、
ハーフ・アダー１１及びフル・アダー１３で構成される
リプル・アダーと、ハーフ・アダー１５及びフル・アダ
ー１７で構成されるリプル・アダーとは一つのグループ
を構成している。このグループ内では２つのリプル・ア
ダーが存在するので、グループ間で伝達されるキャリー
とグループ内で伝達される、２本のキャリーが存在す
る。なお、前記１つ上位のグループよりさらに１つ上位
のグループ中の最下位のリプル・アダー内において最下
位アダーの出力Ｓ０とＣとの排他的論理和を計算する回
路と、当該最下位アダーより１つ上位のアダーの出力Ｓ
１と、Ｃ及びＳ０の論理積との排他的論理和を計算する
回路とをさらに有する。この排他的論理和の出力が、当
該最下位アダーの最終的な出力と、最下位アダーより１
つ上位のアダーの最終的な出力となる。
【００１３】本発明の第３の態様であるキャリ・スキッ
プ・アダーは、複数のリプル・アダーを有し、複数のリ
プル・アダーのうち少なくとも一部のリプル・アダーに
含まれる第１リプル・アダーについて、第１リプル・ア
ダーのキャリー信号Ｃ１と、第１リプル・アダー内の全
ての出力が１になっているか否かを示す信号Ｆ１と、第
１リプル・アダーより１つ下位のリプル・アダーに関連
するキャリー信号Ｃ０が伝達されている場合には当該キ
ャリー信号Ｃ０とに対して、Ｃ２＝Ｃ１＋Ｆ１・Ｃ０な
る計算を実行する回路を有する。また、第１リプル・ア
ダーから２以上下位のリプル・アダーである第２リプル
・アダーに関連する回路から第１リプル・アダーに当該
第２リプル・アダーに関連するキャリー信号Ｃが伝達さ
れる場合には、各第１リプル・アダー及び各キャリー信
号Ｃについて、第２リプル・アダーより上位で第１リプ
ル・アダーまでの全ての出力が１になっているか否かを
示す信号Ｆ２と、第１リプル・アダーに関連するキャリ
ー信号Ｃ２'とキャリー信号Ｃに対して、Ｃ３＝Ｃ２'＋
Ｆ２・Ｃなる計算を実行する回路をさらに有する。これ
により複数段のキャリー・スキップ・アダーが構成さ
れ、ゲート・ディレイが大幅に削減される。キャリー信
号は上位に伝搬されるだけで、下位に戻されることはな
い。例えば図１においては、第１リプル・アダーがアダ
ー２３及び２５である場合、ＡＮＤ回路９７及びＯＲ回
路１０３がＣ２＝Ｃ１＋Ｆ１・Ｃ０なる計算を実行する
回路であり、ＡＮＤ回路１０１及びＯＲ回路１０５がＣ
３＝Ｃ２'＋Ｆ２・Ｃなる計算を実行する回路である。
プ・アダーは、複数のリプル・アダーを有し、複数のリ
プル・アダーのうち少なくとも一部のリプル・アダーに
含まれる第１リプル・アダーについて、第１リプル・ア
ダーのキャリー信号Ｃ１と、第１リプル・アダー内の全
ての出力が１になっているか否かを示す信号Ｆ１と、第
１リプル・アダーより１つ下位のリプル・アダーに関連
するキャリー信号Ｃ０が伝達されている場合には当該キ
ャリー信号Ｃ０とに対して、Ｃ２＝Ｃ１＋Ｆ１・Ｃ０な
る計算を実行する回路を有する。また、第１リプル・ア
ダーから２以上下位のリプル・アダーである第２リプル
・アダーに関連する回路から第１リプル・アダーに当該
第２リプル・アダーに関連するキャリー信号Ｃが伝達さ
れる場合には、各第１リプル・アダー及び各キャリー信
号Ｃについて、第２リプル・アダーより上位で第１リプ
ル・アダーまでの全ての出力が１になっているか否かを
示す信号Ｆ２と、第１リプル・アダーに関連するキャリ
ー信号Ｃ２'とキャリー信号Ｃに対して、Ｃ３＝Ｃ２'＋
Ｆ２・Ｃなる計算を実行する回路をさらに有する。これ
により複数段のキャリー・スキップ・アダーが構成さ
れ、ゲート・ディレイが大幅に削減される。キャリー信
号は上位に伝搬されるだけで、下位に戻されることはな
い。例えば図１においては、第１リプル・アダーがアダ
ー２３及び２５である場合、ＡＮＤ回路９７及びＯＲ回
路１０３がＣ２＝Ｃ１＋Ｆ１・Ｃ０なる計算を実行する
回路であり、ＡＮＤ回路１０１及びＯＲ回路１０５がＣ
３＝Ｃ２'＋Ｆ２・Ｃなる計算を実行する回路である。
【００１４】第１リプル・アダーに関連してＣ３が出力
される場合には、第１リプル・アダーから１つ上位の第
３リプル・アダー中最下位アダーの出力Ｓ０とＣ３との
排他的論理和を計算する回路と、最下位アダーより１つ
上位のアダーの出力Ｓ１と、Ｃ３及びＳ０の論理積との
排他的論理和を計算する回路とをさらに有し、第１リプ
ル・アダーに関連してＣ３が出力されない場合には、第
３リプル・アダー中最下位アダーの出力Ｓ０とＣ２との
排他的論理和を計算する回路と、最下位アダーより１つ
上位のアダーの出力Ｓ１と、Ｃ２及びＳ０の論理積との
排他的論理和を計算する回路とをさらに有する。これら
排他的論理和の出力は、第３リプル・アダー中最下位ア
ダーの最終的な出力、当該最下位アダーより１つ上位の
アダーの最終的な出力となる。例えば図１において第１
リプル・アダーがハーフ・アダー１５及びフル・アダー
１７である場合には、ハーフ・アダー１９及びフル・ア
ダー２１（第３リプル・アダー）にはＣ３が出力されて
おり、第１ルプル・アダーがハーフ・アダー１９及びフ
ル・アダー２１である場合には、ハーフ・アダー２３及
びフル・アダー２５（第３リプル・アダー）にはＣ２が
出力されている。第３リプル・アダーが３以上のアダー
から構成される場合には、最下位アダーよりｍ（ｍ≧
３）上位のアダーの出力Ｓｍと、Ｃ３及び最下位アダー
から最下位アダーよりｍ−１上位のアダーまでの全出力
の論理積との排他的論理和を計算する回路をさらに有す
る。例えば図４において第１リプル・アダーがハーフ・
アダー４７１及びフル・アダー４７３である場合には、
第３リプル・アダーはハーフ・アダー４７５及びフル・
アダー４７７及び４７９であり、第３リプル・アダーは
３以上のアダーを含む。そして、フル・アダー４７９の
最終的な出力は、ハーフ・アダー４７５及びフル・アダ
ー４７７の出力とＣ３との論理積と、フル・アダー４７
９の出力との排他的論理和となっている（ｍ＝３）。
される場合には、第１リプル・アダーから１つ上位の第
３リプル・アダー中最下位アダーの出力Ｓ０とＣ３との
排他的論理和を計算する回路と、最下位アダーより１つ
上位のアダーの出力Ｓ１と、Ｃ３及びＳ０の論理積との
排他的論理和を計算する回路とをさらに有し、第１リプ
ル・アダーに関連してＣ３が出力されない場合には、第
３リプル・アダー中最下位アダーの出力Ｓ０とＣ２との
排他的論理和を計算する回路と、最下位アダーより１つ
上位のアダーの出力Ｓ１と、Ｃ２及びＳ０の論理積との
排他的論理和を計算する回路とをさらに有する。これら
排他的論理和の出力は、第３リプル・アダー中最下位ア
ダーの最終的な出力、当該最下位アダーより１つ上位の
アダーの最終的な出力となる。例えば図１において第１
リプル・アダーがハーフ・アダー１５及びフル・アダー
１７である場合には、ハーフ・アダー１９及びフル・ア
ダー２１（第３リプル・アダー）にはＣ３が出力されて
おり、第１ルプル・アダーがハーフ・アダー１９及びフ
ル・アダー２１である場合には、ハーフ・アダー２３及
びフル・アダー２５（第３リプル・アダー）にはＣ２が
出力されている。第３リプル・アダーが３以上のアダー
から構成される場合には、最下位アダーよりｍ（ｍ≧
３）上位のアダーの出力Ｓｍと、Ｃ３及び最下位アダー
から最下位アダーよりｍ−１上位のアダーまでの全出力
の論理積との排他的論理和を計算する回路をさらに有す
る。例えば図４において第１リプル・アダーがハーフ・
アダー４７１及びフル・アダー４７３である場合には、
第３リプル・アダーはハーフ・アダー４７５及びフル・
アダー４７７及び４７９であり、第３リプル・アダーは
３以上のアダーを含む。そして、フル・アダー４７９の
最終的な出力は、ハーフ・アダー４７５及びフル・アダ
ー４７７の出力とＣ３との論理積と、フル・アダー４７
９の出力との排他的論理和となっている（ｍ＝３）。
【００１５】本発明の第４の態様であるキャリー・スキ
ップ・アダーは、複数のリプル・アダーを有し、この複
数のリプル・アダーのうち少なくとも一部のリプル・ア
ダーはグループ分けされており、キャリー信号はあるグ
ループから１つ上位のグループへ伝達されている。そし
て、前記あるグループから前記１つ上位のグループへの
キャリー信号Ｃ１と、前記１つ上位のグループ内の全ア
ダーの出力が１であるか否かを表す信号Ｆと、前記１つ
上位のグループ内において最も上位のリプル・アダーに
関連するキャリー信号Ｃ２とを用いて、Ｃ＝Ｃ２＋Ｆ・
Ｃ１を計算する回路を有する。また、２以上のリプル・
アダーを有するグループにおいては、当該グループ内の
複数のリプル・アダーがさらに複数のサブグループに分
けられ、キャリー信号はあるサブグループから１つ上位
のサブグループへ伝達されており、前記あるサブグルー
プから前記１つ上位のサブグループへのキャリー信号Ｃ
３と、前記１つ上位のサブグループ内の全てのアダーの
出力が１であるか否かを表す信号Ｆ１と、前記１つ上位
のサブグループ内において最も上位のリプル・アダーに
関連するキャリー信号Ｃ４とを用いて、Ｃ５＝Ｃ４＋Ｆ
１・Ｃ３を計算する回路を有する。グループは、１つの
リプル・アダーのみを有することもあり、サブ・グルー
プはさらにサブ・グループを持ち得る。例えば、図４に
おいてはアダー４５１乃至４７９は１つのグループであ
り、アダー４５１乃至４６５が第１サブグループでアダ
ー４６７乃至４７９が第２サブグループである。また、
第１サブグループは、アダー４５１乃至４５７のサブグ
ループ、アダー４５９及び４６５のサブグループに分け
られる。さらに、第２サブグループは、アダー４６７及
び４６９のサブグループ、アダー４７１及び４７３のサ
ブグループ、アダー４７５乃至４７９のサブグループに
分けられる。第１サブグループの２つのサブグループ
は、それぞれリプル・アダーの単位でさらにサブグルー
プに分けられる。
ップ・アダーは、複数のリプル・アダーを有し、この複
数のリプル・アダーのうち少なくとも一部のリプル・ア
ダーはグループ分けされており、キャリー信号はあるグ
ループから１つ上位のグループへ伝達されている。そし
て、前記あるグループから前記１つ上位のグループへの
キャリー信号Ｃ１と、前記１つ上位のグループ内の全ア
ダーの出力が１であるか否かを表す信号Ｆと、前記１つ
上位のグループ内において最も上位のリプル・アダーに
関連するキャリー信号Ｃ２とを用いて、Ｃ＝Ｃ２＋Ｆ・
Ｃ１を計算する回路を有する。また、２以上のリプル・
アダーを有するグループにおいては、当該グループ内の
複数のリプル・アダーがさらに複数のサブグループに分
けられ、キャリー信号はあるサブグループから１つ上位
のサブグループへ伝達されており、前記あるサブグルー
プから前記１つ上位のサブグループへのキャリー信号Ｃ
３と、前記１つ上位のサブグループ内の全てのアダーの
出力が１であるか否かを表す信号Ｆ１と、前記１つ上位
のサブグループ内において最も上位のリプル・アダーに
関連するキャリー信号Ｃ４とを用いて、Ｃ５＝Ｃ４＋Ｆ
１・Ｃ３を計算する回路を有する。グループは、１つの
リプル・アダーのみを有することもあり、サブ・グルー
プはさらにサブ・グループを持ち得る。例えば、図４に
おいてはアダー４５１乃至４７９は１つのグループであ
り、アダー４５１乃至４６５が第１サブグループでアダ
ー４６７乃至４７９が第２サブグループである。また、
第１サブグループは、アダー４５１乃至４５７のサブグ
ループ、アダー４５９及び４６５のサブグループに分け
られる。さらに、第２サブグループは、アダー４６７及
び４６９のサブグループ、アダー４７１及び４７３のサ
ブグループ、アダー４７５乃至４７９のサブグループに
分けられる。第１サブグループの２つのサブグループ
は、それぞれリプル・アダーの単位でさらにサブグルー
プに分けられる。
【００１６】本発明の第１乃至第４の態様の変形となる
キャリー・スキップ・アダーは、複数のリプル・アダー
を有し、最下位のアダーの入力が３ビットである、少な
くとも一部のリプル・アダーについて、最下位のアダー
を含むリプル・アダーのキャリー信号Ｃ１と、当該リプ
ル・アダー内の全ての出力が１になっているか否かを示
す信号Ｆ１と、最下位のアダーより１つ下位のアダーに
関連するキャリー信号Ｃ０が伝達されている場合には当
該キャリー信号Ｃ０と、当該リプル・アダーの１つ上位
のリプル・アダーの最下位の出力Ｆ２とに対して、実質
的にＦ１・Ｃ０とＣ１とＦ２を加算する回路を有する。
二種類のキャリーが独立に発生するため、加算回路（フ
ル・アダー）が採用されている。
キャリー・スキップ・アダーは、複数のリプル・アダー
を有し、最下位のアダーの入力が３ビットである、少な
くとも一部のリプル・アダーについて、最下位のアダー
を含むリプル・アダーのキャリー信号Ｃ１と、当該リプ
ル・アダー内の全ての出力が１になっているか否かを示
す信号Ｆ１と、最下位のアダーより１つ下位のアダーに
関連するキャリー信号Ｃ０が伝達されている場合には当
該キャリー信号Ｃ０と、当該リプル・アダーの１つ上位
のリプル・アダーの最下位の出力Ｆ２とに対して、実質
的にＦ１・Ｃ０とＣ１とＦ２を加算する回路を有する。
二種類のキャリーが独立に発生するため、加算回路（フ
ル・アダー）が採用されている。
【００１７】２段のキャリー・スキップ・アダーの場合
には、下位レベルのブロックをセット、上位レベルのブ
ロックをグループとし、下位から、３ビットの第１グル
ープ、２ビットの第２グループ、２ビットのセットと２
ビットのセットからなる第３グループ、第４グループ以
降はグループ番号ｎ−１個のセットを含み（ｎは４以上
の整数）、当該グループ内で第１及び第２のセットは２
ビット、第３のセット以降はセット番号ｍビットとなる
ように、２つのＮビット（足し算を行う２つの数）の入
力を分ける。そして、各々２つのＮビットの入力のうち
同じビット位置の２つの入力に接続された、Ｎ個のアダ
ー（フルー・アダーの場合とハーフ・アダーの場合を含
む）と有し、第１及び第２グループと各セット内では、
あるアダーから次のアダーへ、リプル・キャリーを直接
伝達する。これにより、ブロック分けされたリプル・ア
ダーが構成される。また、第３グループ以降の各グルー
プ内で、あるセットから次のセットへキャリーを伝達す
るラインと、第２グループ以降の各グループ内で、前の
グループからキャリーを伝達するラインとが、スキップ
するキャリー２本を示す。最後に、伝達されるキャリー
とアダーの出力とを用いて、加算結果を補正する回路
（１つに限らない。通常複数。）を設ける。このアダー
は、リプル・アダーのブロック分けに特徴を有する。
には、下位レベルのブロックをセット、上位レベルのブ
ロックをグループとし、下位から、３ビットの第１グル
ープ、２ビットの第２グループ、２ビットのセットと２
ビットのセットからなる第３グループ、第４グループ以
降はグループ番号ｎ−１個のセットを含み（ｎは４以上
の整数）、当該グループ内で第１及び第２のセットは２
ビット、第３のセット以降はセット番号ｍビットとなる
ように、２つのＮビット（足し算を行う２つの数）の入
力を分ける。そして、各々２つのＮビットの入力のうち
同じビット位置の２つの入力に接続された、Ｎ個のアダ
ー（フルー・アダーの場合とハーフ・アダーの場合を含
む）と有し、第１及び第２グループと各セット内では、
あるアダーから次のアダーへ、リプル・キャリーを直接
伝達する。これにより、ブロック分けされたリプル・ア
ダーが構成される。また、第３グループ以降の各グルー
プ内で、あるセットから次のセットへキャリーを伝達す
るラインと、第２グループ以降の各グループ内で、前の
グループからキャリーを伝達するラインとが、スキップ
するキャリー２本を示す。最後に、伝達されるキャリー
とアダーの出力とを用いて、加算結果を補正する回路
（１つに限らない。通常複数。）を設ける。このアダー
は、リプル・アダーのブロック分けに特徴を有する。
【００１８】３段のキャリー・スキップ・アダーの場合
には、最下位レベルのブロックからセット、グループ、
クラスと名付け、下位から、３ビットの第１クラス、２
ビットの第２クラス、２つの２ビットのグループからな
る第３クラス、２つの２ビットのセットからなる第１の
グループと２つの２ビットのセットからなる第２のグル
ープとからなる第４クラス、２つの２ビットのセットか
らなる第１のグループと２つの２ビットのセットからな
る第２のグループと２つの２ビットのセットと３ビット
のセットを含む第３のグループとからなる第５クラス、
第６クラス以降は、クラス番号ｎ−２個のグループを有
し、第１乃至第３のグループは第５クラスと同じで、第
４のグループ以降は、グループ番号ｇ個のセットを有
し、第４のグループ以降の各グループ内では、２ビット
の第１セット、第２セット以降は、セット番号ｓビット
のセットを含むように、２つのＮビットの入力を分け
る。そして、各々２つのＮビットの入力のうち同じビッ
ト位置の２つの入力に接続された、Ｎ個のアダーと、第
１及び第２クラスと第３クラスの各グループ内と各セッ
ト内で、あるアダーから次のアダーへ、リプル・キャリ
ーを直接伝達する。これにより、ブロック分けされたリ
プル・アダーが構成される。また、第３クラス以降の各
グループ内で、あるセットから次のセットへキャリーを
伝達するラインと、第４クラス以降の各クラス内で、あ
るグループから次のグループへキャリーを伝達するライ
ンと、第２クラス以降の各クラスで、前のクラスからキ
ャリーを伝達するラインと、が３本のスキップされたキ
ャリーを示す。最後に、伝達されるキャリーとアダーの
出力とを用いて、加算結果を補正する回路とを含める。
には、最下位レベルのブロックからセット、グループ、
クラスと名付け、下位から、３ビットの第１クラス、２
ビットの第２クラス、２つの２ビットのグループからな
る第３クラス、２つの２ビットのセットからなる第１の
グループと２つの２ビットのセットからなる第２のグル
ープとからなる第４クラス、２つの２ビットのセットか
らなる第１のグループと２つの２ビットのセットからな
る第２のグループと２つの２ビットのセットと３ビット
のセットを含む第３のグループとからなる第５クラス、
第６クラス以降は、クラス番号ｎ−２個のグループを有
し、第１乃至第３のグループは第５クラスと同じで、第
４のグループ以降は、グループ番号ｇ個のセットを有
し、第４のグループ以降の各グループ内では、２ビット
の第１セット、第２セット以降は、セット番号ｓビット
のセットを含むように、２つのＮビットの入力を分け
る。そして、各々２つのＮビットの入力のうち同じビッ
ト位置の２つの入力に接続された、Ｎ個のアダーと、第
１及び第２クラスと第３クラスの各グループ内と各セッ
ト内で、あるアダーから次のアダーへ、リプル・キャリ
ーを直接伝達する。これにより、ブロック分けされたリ
プル・アダーが構成される。また、第３クラス以降の各
グループ内で、あるセットから次のセットへキャリーを
伝達するラインと、第４クラス以降の各クラス内で、あ
るグループから次のグループへキャリーを伝達するライ
ンと、第２クラス以降の各クラスで、前のクラスからキ
ャリーを伝達するラインと、が３本のスキップされたキ
ャリーを示す。最後に、伝達されるキャリーとアダーの
出力とを用いて、加算結果を補正する回路とを含める。
【００１９】４段のキャリー・スキップ・アダーの場合
には、最下位レベルのブロックから、セット、グルー
プ、クラス、ブロックと名付け、下位から、３ビットの
第１ブロック、２ビットの第２ブロック、２ビットのセ
ット２つからなる第３ブロック、２ビットのセット２つ
からなるグループと２ビットのセット２つからなるグル
ープとからなるクラスと、当該クラスの構成と同じ構成
のクラスとからなる第４ブロック、第５ブロック以降
は、ブロック番号ｂ−２個のクラスを有し、ｂ−３番目
のクラスまでは前のブロックと同様の構成を有してお
り、ｂ−２番目のクラスの構成は、ｂ−２個のグループ
を有し、第１グループは２ビットのセット２つ、第２グ
ループは２ビットのセット２つ、第３グループ以降はグ
ループ番号ｇ個のセットを有し、２ビットの第１セット
と第２セット以降は当該セット番号ｓビットからなるセ
ットとを有するように、２つのＮビットの入力を分け
る。
には、最下位レベルのブロックから、セット、グルー
プ、クラス、ブロックと名付け、下位から、３ビットの
第１ブロック、２ビットの第２ブロック、２ビットのセ
ット２つからなる第３ブロック、２ビットのセット２つ
からなるグループと２ビットのセット２つからなるグル
ープとからなるクラスと、当該クラスの構成と同じ構成
のクラスとからなる第４ブロック、第５ブロック以降
は、ブロック番号ｂ−２個のクラスを有し、ｂ−３番目
のクラスまでは前のブロックと同様の構成を有してお
り、ｂ−２番目のクラスの構成は、ｂ−２個のグループ
を有し、第１グループは２ビットのセット２つ、第２グ
ループは２ビットのセット２つ、第３グループ以降はグ
ループ番号ｇ個のセットを有し、２ビットの第１セット
と第２セット以降は当該セット番号ｓビットからなるセ
ットとを有するように、２つのＮビットの入力を分け
る。
【００２０】そして、各々２つのＮビットの入力のうち
同じビット位置の２つの入力に接続された、Ｎ個のアダ
ーと、第１及び第２ブロックと第３ブロック以降の各セ
ット内で、あるアダーから次のアダーへ、リプル・キャ
リーを直接伝達する。これが、ブロック分けされたリプ
ル・アダーである。また、第３ブロック内及び第４ブロ
ック以降の各グループ内で、あるセットから次のセット
へキャリーを伝達するラインと、第４ブロック以降の各
クラス内で、あるグループから次のグループへキャリー
を伝達するラインと、第４ブロック以降の各ブロック内
で、あるクラスから次の前記クラスへキャリーを伝達す
るラインと、第２ブロック以降の各ブロック内で、前の
ブロックからキャリーを伝達するラインとが、３本のス
キップされたキャリーを表す。最後に、伝達されるキャ
リーとアダーの出力とを用いて、加算結果を補正する回
路とを設ける。
同じビット位置の２つの入力に接続された、Ｎ個のアダ
ーと、第１及び第２ブロックと第３ブロック以降の各セ
ット内で、あるアダーから次のアダーへ、リプル・キャ
リーを直接伝達する。これが、ブロック分けされたリプ
ル・アダーである。また、第３ブロック内及び第４ブロ
ック以降の各グループ内で、あるセットから次のセット
へキャリーを伝達するラインと、第４ブロック以降の各
クラス内で、あるグループから次のグループへキャリー
を伝達するラインと、第４ブロック以降の各ブロック内
で、あるクラスから次の前記クラスへキャリーを伝達す
るラインと、第２ブロック以降の各ブロック内で、前の
ブロックからキャリーを伝達するラインとが、３本のス
キップされたキャリーを表す。最後に、伝達されるキャ
リーとアダーの出力とを用いて、加算結果を補正する回
路とを設ける。
【００２１】
【発明の実施の形態】Ａ．２段キャリー・スキップ・ア
ダー 最初に、入力のブロック分けについて示しておく。以下
の数字はバイナリ・アダーの数を示す。 ３ ２ ２，２ ２，２，３ ２，２，３，４ ２，２，３，４，５ ．．．． ．．．． この各行は、上位レベルのブロック分けであるグループ
を示し、列に並んでいる数字は、グループのレベルにお
けるブロック分けでセットを示す。
ダー 最初に、入力のブロック分けについて示しておく。以下
の数字はバイナリ・アダーの数を示す。 ３ ２ ２，２ ２，２，３ ２，２，３，４ ２，２，３，４，５ ．．．． ．．．． この各行は、上位レベルのブロック分けであるグループ
を示し、列に並んでいる数字は、グループのレベルにお
けるブロック分けでセットを示す。
【００２２】図１及び図２に２段キャリー・スキップ・
アダーを示す。第１グループは、３つのフル・アダー１
乃至５を含み、これらはリプル・アダーを構成する。す
なわち、フル・アダー１のキャリーはフル・アダー３
に、フル・アダー３のキャリーはフル・アダー５に入力
される。フル・アダー１には、ａ0という信号も入力さ
れているが、これは任意であり、よって、フル・アダー
でなく、ハーフ・アダーでもよい。それぞれのアダーの
出力は、それぞれＺ0，Ｚ1，Ｚ2となる。また、第１グ
ループ全体のキャリー信号Ｃ1は、第２グループに出力
される。この最下位のグループは、下位からキャリーが
来ないので、ゲート・ディレイをここだけ１段深くする
ことができる。
アダーを示す。第１グループは、３つのフル・アダー１
乃至５を含み、これらはリプル・アダーを構成する。す
なわち、フル・アダー１のキャリーはフル・アダー３
に、フル・アダー３のキャリーはフル・アダー５に入力
される。フル・アダー１には、ａ0という信号も入力さ
れているが、これは任意であり、よって、フル・アダー
でなく、ハーフ・アダーでもよい。それぞれのアダーの
出力は、それぞれＺ0，Ｚ1，Ｚ2となる。また、第１グ
ループ全体のキャリー信号Ｃ1は、第２グループに出力
される。この最下位のグループは、下位からキャリーが
来ないので、ゲート・ディレイをここだけ１段深くする
ことができる。
【００２３】次に、第２グループは、ハーフ・アダー７
及びフル・アダー９を含み、この２つのアダーでリプル
・アダーを構成する。すなわち、ハーフ・アダー７のキ
ャリーはフル・アダー９に入力される。そして、ハーフ
・アダー７の出力とキャリー信号Ｃ1とを入力とする排
他的論理和回路３３の出力がＺ3となる。また、キャリ
ー信号Ｃ1とハーフ・アダー７の出力とがＡＮＤ回路３
５に入力されており、このＡＮＤ回路３５の出力とフル
・アダー９の出力とを入力とする排他的論理和回路３７
の出力がＺ4となる。そして、この第２グループ全体の
キャリー信号Ｃ2を作成するため、アダー７及び９の出
力が入力されたＡＮＤ回路３９と、そのＡＮＤ回路３９
の出力とキャリー信号Ｃ1とが入力されるＡＮＤ回路４
１と、ＡＮＤ回路４１の出力とフル・アダー９のキャリ
ーとが入力されるＯＲ回路４３とが設けられる。このキ
ャリー信号Ｃ2は、第３グループに伝搬される。第２グ
ループでは、第１グループからのキャリー信号Ｃ1１本
のみが入力されており、ＡＮＤ回路３９、ＡＮＤ回路４
１及びＯＲ回路４３にて、キャリー信号Ｃ2が生成でき
る。ここで、キャリーＣ2信号が発生するのは、グルー
プ内の全てのアダーの出力が１であって且つ前のグルー
プからのキャリーが１である場合、又はグループ内の最
高位のアダーがキャリーを生成している場合である。
及びフル・アダー９を含み、この２つのアダーでリプル
・アダーを構成する。すなわち、ハーフ・アダー７のキ
ャリーはフル・アダー９に入力される。そして、ハーフ
・アダー７の出力とキャリー信号Ｃ1とを入力とする排
他的論理和回路３３の出力がＺ3となる。また、キャリ
ー信号Ｃ1とハーフ・アダー７の出力とがＡＮＤ回路３
５に入力されており、このＡＮＤ回路３５の出力とフル
・アダー９の出力とを入力とする排他的論理和回路３７
の出力がＺ4となる。そして、この第２グループ全体の
キャリー信号Ｃ2を作成するため、アダー７及び９の出
力が入力されたＡＮＤ回路３９と、そのＡＮＤ回路３９
の出力とキャリー信号Ｃ1とが入力されるＡＮＤ回路４
１と、ＡＮＤ回路４１の出力とフル・アダー９のキャリ
ーとが入力されるＯＲ回路４３とが設けられる。このキ
ャリー信号Ｃ2は、第３グループに伝搬される。第２グ
ループでは、第１グループからのキャリー信号Ｃ1１本
のみが入力されており、ＡＮＤ回路３９、ＡＮＤ回路４
１及びＯＲ回路４３にて、キャリー信号Ｃ2が生成でき
る。ここで、キャリーＣ2信号が発生するのは、グルー
プ内の全てのアダーの出力が１であって且つ前のグルー
プからのキャリーが１である場合、又はグループ内の最
高位のアダーがキャリーを生成している場合である。
【００２４】ハーフ・アダー１１及びフル・アダー１３
で第１セットを構成し、ハーフ・アダー１５及びフル・
アダー１７で第２セットを構成し、第３グループはこの
２つのセットを有する。各セットはリプル・アダーを構
成し、ハーフ・アダー１１からフル・アダー１３へ、ハ
ーフ・アダー１５からフル・アダー１７にキャリーは伝
搬される。そして、ハーフ・アダー１１の出力とキャリ
ー信号Ｃ2とを入力とする排他的論理和回路４５の出力
が出力Ｚ5となる。また、キャリー信号Ｃ2とハーフ・ア
ダー１１の出力とがＡＮＤ回路４７に入力されており、
このＡＮＤ回路４７の出力とフル・アダー１３の出力と
を入力とする排他的論理和回路４９の出力がＺ6とな
る。第１セットのキャリーとして、フル・アダー１３の
キャリーは第２セットに伝搬される。また、第１セット
に含まれるアダー１１及び１３の出力が共に１であるか
否かを示す信号を作成するために、ＡＮＤ回路５１が設
けられている。このＡＮＤ回路５１の出力も第２セット
に送られる。
で第１セットを構成し、ハーフ・アダー１５及びフル・
アダー１７で第２セットを構成し、第３グループはこの
２つのセットを有する。各セットはリプル・アダーを構
成し、ハーフ・アダー１１からフル・アダー１３へ、ハ
ーフ・アダー１５からフル・アダー１７にキャリーは伝
搬される。そして、ハーフ・アダー１１の出力とキャリ
ー信号Ｃ2とを入力とする排他的論理和回路４５の出力
が出力Ｚ5となる。また、キャリー信号Ｃ2とハーフ・ア
ダー１１の出力とがＡＮＤ回路４７に入力されており、
このＡＮＤ回路４７の出力とフル・アダー１３の出力と
を入力とする排他的論理和回路４９の出力がＺ6とな
る。第１セットのキャリーとして、フル・アダー１３の
キャリーは第２セットに伝搬される。また、第１セット
に含まれるアダー１１及び１３の出力が共に１であるか
否かを示す信号を作成するために、ＡＮＤ回路５１が設
けられている。このＡＮＤ回路５１の出力も第２セット
に送られる。
【００２５】キャリー信号Ｃ2とＡＮＤ回路５１の出力
とを入力とするＡＮＤ回路５３、及びＡＮＤ回路５３の
出力とフル・アダー１３のキャリーを入力とするＯＲ回
路５５は、全体としてこの第１セットまでのキャリー信
号を生成する。そして、ＯＲ回路５５の出力とハーフ・
アダー１５の出力とは排他的論理和回路５７に入力さ
れ、この排他的論理和回路５７の出力は出力Ｚ7とな
る。また、ＯＲ回路５５の出力とハーフ・アダー１５の
出力とはＡＮＤ回路５９に入力され、このＡＮＤ回路５
９の出力とフル・アダー１７の出力とが入力である排他
的論理和回路６１の出力が出力Ｚ8である。次に、この
グループ内での第２セットまでのキャリーを生成する。
このキャリーは、アダー１５及び１７の出力が共に１で
あるか否か判断するＡＮＤ回路６３、フル・アダー１３
からのキャリーとＡＮＤ回路６３の出力とを入力とする
ＡＮＤ回路６７、及びＡＮＤ回路６７の出力とフル・ア
ダー１７のキャリーとを入力とするＯＲ回路６９にて生
成される。加えて、第２グループ全体のキャリー信号Ｃ
3を生成する必要がある。このキャリー信号Ｃ3は、ＡＮ
Ｄ回路５１の出力とＡＮＤ回路６３の出力とを入力にす
るＡＮＤ回路６５と、このＡＮＤ回路６５の出力とキャ
リー信号Ｃ2とを入力とするＡＮＤ回路７１と、このＡ
ＮＤ回路７１の出力と、ＯＲ回路６９の出力とを入力に
するＯＲ回路７３から生成される。このＡＮＤ回路６５
は、このグループ内の全てのアダーの出力が１であるか
否かを示す信号を生成するために設けられる。
とを入力とするＡＮＤ回路５３、及びＡＮＤ回路５３の
出力とフル・アダー１３のキャリーを入力とするＯＲ回
路５５は、全体としてこの第１セットまでのキャリー信
号を生成する。そして、ＯＲ回路５５の出力とハーフ・
アダー１５の出力とは排他的論理和回路５７に入力さ
れ、この排他的論理和回路５７の出力は出力Ｚ7とな
る。また、ＯＲ回路５５の出力とハーフ・アダー１５の
出力とはＡＮＤ回路５９に入力され、このＡＮＤ回路５
９の出力とフル・アダー１７の出力とが入力である排他
的論理和回路６１の出力が出力Ｚ8である。次に、この
グループ内での第２セットまでのキャリーを生成する。
このキャリーは、アダー１５及び１７の出力が共に１で
あるか否か判断するＡＮＤ回路６３、フル・アダー１３
からのキャリーとＡＮＤ回路６３の出力とを入力とする
ＡＮＤ回路６７、及びＡＮＤ回路６７の出力とフル・ア
ダー１７のキャリーとを入力とするＯＲ回路６９にて生
成される。加えて、第２グループ全体のキャリー信号Ｃ
3を生成する必要がある。このキャリー信号Ｃ3は、ＡＮ
Ｄ回路５１の出力とＡＮＤ回路６３の出力とを入力にす
るＡＮＤ回路６５と、このＡＮＤ回路６５の出力とキャ
リー信号Ｃ2とを入力とするＡＮＤ回路７１と、このＡ
ＮＤ回路７１の出力と、ＯＲ回路６９の出力とを入力に
するＯＲ回路７３から生成される。このＡＮＤ回路６５
は、このグループ内の全てのアダーの出力が１であるか
否かを示す信号を生成するために設けられる。
【００２６】第４グループは、３つのセットを有する。
第１セットは、ハーフ・アダー１９及びフル・アダー２
１を含み、これらでリプル・アダーを構成する。第２セ
ットは、ハーフ・アダー２３及びフル・アダー２５を含
み、これらでリプル・アダーを構成する。第３セット
は、ハーフ・アダー２７及びフル・アダー２９及び３１
を含み、これらでリプル・アダーを構成する。
第１セットは、ハーフ・アダー１９及びフル・アダー２
１を含み、これらでリプル・アダーを構成する。第２セ
ットは、ハーフ・アダー２３及びフル・アダー２５を含
み、これらでリプル・アダーを構成する。第３セット
は、ハーフ・アダー２７及びフル・アダー２９及び３１
を含み、これらでリプル・アダーを構成する。
【００２７】ハーフ・アダー１９の出力とキャリー信号
Ｃ3とが排他的論理和回路７５に入力され、この回路７
５の出力は出力Ｚ9となる。また、ハーフ・アダー１９
の出力とキャリー信号Ｃ3とがＡＮＤ回路７７に入力さ
れ、このＡＮＤ回路７７の出力と、フル・アダー２１の
出力とを入力とする排他的論理和回路７９の出力が、出
力Ｚ10となる。アダー１９及び２１の出力はＡＮＤ回路
８１に入力され、このＡＮＤ回路８１の出力は第２セッ
トに伝搬される。加えて、フル・アダー２１のキャリー
も同様に第２セットに伝搬される。全体としてこの第１
セットまでのキャリーを生成するための回路が、キャリ
ー信号Ｃ3及びＡＮＤ回路８１の出力とが入力されるＡ
ＮＤ回路８３と、このＡＮＤ回路８３の出力とフル・ア
ダー２１のキャリーが入力されるＯＲ回路８５とによっ
て構成される。
Ｃ3とが排他的論理和回路７５に入力され、この回路７
５の出力は出力Ｚ9となる。また、ハーフ・アダー１９
の出力とキャリー信号Ｃ3とがＡＮＤ回路７７に入力さ
れ、このＡＮＤ回路７７の出力と、フル・アダー２１の
出力とを入力とする排他的論理和回路７９の出力が、出
力Ｚ10となる。アダー１９及び２１の出力はＡＮＤ回路
８１に入力され、このＡＮＤ回路８１の出力は第２セッ
トに伝搬される。加えて、フル・アダー２１のキャリー
も同様に第２セットに伝搬される。全体としてこの第１
セットまでのキャリーを生成するための回路が、キャリ
ー信号Ｃ3及びＡＮＤ回路８１の出力とが入力されるＡ
ＮＤ回路８３と、このＡＮＤ回路８３の出力とフル・ア
ダー２１のキャリーが入力されるＯＲ回路８５とによっ
て構成される。
【００２８】全体としてこの第１セットまでのキャリー
に対応する信号であるＯＲ回路８５の出力と、ハーフ・
アダー２３の出力とが入力される排他的論理和回路８７
の出力が、出力Ｚ11となる。また、ＯＲ回路８５の出力
と、ハーフ・アダー２３の出力とがＡＮＤ回路８９に入
力され、このＡＮＤ回路８９の出力とフル・アダー２５
の出力とが入力される排他的論理和回路９１の出力が出
力Ｚ12となる。
に対応する信号であるＯＲ回路８５の出力と、ハーフ・
アダー２３の出力とが入力される排他的論理和回路８７
の出力が、出力Ｚ11となる。また、ＯＲ回路８５の出力
と、ハーフ・アダー２３の出力とがＡＮＤ回路８９に入
力され、このＡＮＤ回路８９の出力とフル・アダー２５
の出力とが入力される排他的論理和回路９１の出力が出
力Ｚ12となる。
【００２９】第４グループ内での第２セットまでのキャ
リーを生成するために、アダー２３及び２５の出力を入
力とするＡＮＤ回路９３と、このＡＮＤ回路９３の出力
とフル・アダー２１の出力とが入力されるＡＮＤ回路９
７、及びこのＡＮＤ回路９７の出力及びフル・アダー２
５のキャリーが入力されるＯＲ回路１０３とが設けられ
る。加えて、第１及び第２セットの全てのアダーの出力
が共に１であるか否かを表す信号を、ＡＮＤ回路８１の
出力及びＡＮＤ回路９３の出力とを入力とするＡＮＤ回
路９５が生成する。このＡＮＤ回路９５の出力及びＯＲ
回路１０３の出力は、第３セットに伝搬される。
リーを生成するために、アダー２３及び２５の出力を入
力とするＡＮＤ回路９３と、このＡＮＤ回路９３の出力
とフル・アダー２１の出力とが入力されるＡＮＤ回路９
７、及びこのＡＮＤ回路９７の出力及びフル・アダー２
５のキャリーが入力されるＯＲ回路１０３とが設けられ
る。加えて、第１及び第２セットの全てのアダーの出力
が共に１であるか否かを表す信号を、ＡＮＤ回路８１の
出力及びＡＮＤ回路９３の出力とを入力とするＡＮＤ回
路９５が生成する。このＡＮＤ回路９５の出力及びＯＲ
回路１０３の出力は、第３セットに伝搬される。
【００３０】キャリー信号Ｃ3及びＡＮＤ回路９５の出
力とが入力されるＡＮＤ回路１０１、このＡＮＤ回路１
０１の出力とＯＲ回路１０３の出力とが入力されるＯＲ
回路１０５は、全体として第２セットまでのキャリーを
生成する回路である。このＯＲ回路１０５の出力とハー
フ・アダー２７の出力とが排他的論理和回路１０７に入
力され、この回路１０７の出力が出力Ｚ13となる。ま
た、ＯＲ回路１０５の出力とハーフ・アダー２７の出力
とがＡＮＤ回路１０９に入力され、このＡＮＤ回路１０
９の出力と、フル・アダー２９の出力とが入力される排
他的論理和回路１１１の出力が、出力Ｚ14である。
力とが入力されるＡＮＤ回路１０１、このＡＮＤ回路１
０１の出力とＯＲ回路１０３の出力とが入力されるＯＲ
回路１０５は、全体として第２セットまでのキャリーを
生成する回路である。このＯＲ回路１０５の出力とハー
フ・アダー２７の出力とが排他的論理和回路１０７に入
力され、この回路１０７の出力が出力Ｚ13となる。ま
た、ＯＲ回路１０５の出力とハーフ・アダー２７の出力
とがＡＮＤ回路１０９に入力され、このＡＮＤ回路１０
９の出力と、フル・アダー２９の出力とが入力される排
他的論理和回路１１１の出力が、出力Ｚ14である。
【００３１】アダー２７及び２９の出力はＡＮＤ回路１
１７に入力され、このＡＮＤ回路１１７の出力とＯＲ回
路１０５の出力とがＡＮＤ回路１１３に入力される。こ
のＡＮＤ回路１１３の出力は、フル・アダー３１の出力
と共に排他的論理和回路１１５の入力である。この回路
１１５の出力は、出力Ｚ15である。
１７に入力され、このＡＮＤ回路１１７の出力とＯＲ回
路１０５の出力とがＡＮＤ回路１１３に入力される。こ
のＡＮＤ回路１１３の出力は、フル・アダー３１の出力
と共に排他的論理和回路１１５の入力である。この回路
１１５の出力は、出力Ｚ15である。
【００３２】第４グループ内での第３セットまでのキャ
リーを生成するため、ＡＮＤ回路１１７の出力とフル・
アダー３１の出力とが入力されるＡＮＤ回路１１９、こ
のＡＮＤ回路１１９の出力と本グループの第２セットま
でのキャリーであるＯＲ回路１０３の出力とが入力され
るＡＮＤ回路１２５、及びこのＡＮＤ回路１２５の出力
とフル・アダー３１のキャリーとが入力されるＯＲ回路
１２７が設けられる。
リーを生成するため、ＡＮＤ回路１１７の出力とフル・
アダー３１の出力とが入力されるＡＮＤ回路１１９、こ
のＡＮＤ回路１１９の出力と本グループの第２セットま
でのキャリーであるＯＲ回路１０３の出力とが入力され
るＡＮＤ回路１２５、及びこのＡＮＤ回路１２５の出力
とフル・アダー３１のキャリーとが入力されるＯＲ回路
１２７が設けられる。
【００３３】これに加えて、第４グループまでの全体と
してのキャリー信号Ｃ4を生成するための回路を設け
る。これは、第２セットまでのアダーの出力が全て共に
１であるか否かを示す信号であるＡＮＤ回路９５の出力
とＡＮＤ回路１１９の出力とが入力されるＡＮＤ回路１
２１、このＡＮＤ回路１２１の出力とキャリー信号Ｃ3
とが入力されるＡＮＤ回路１２３と、このＡＮＤ回路１
２３の出力と第３セットまでのキャリーであるＯＲ回路
１２７の出力とが入力されるＯＲ回路１２９から構成さ
れる。このキャリー信号Ｃ4は図２の回路（第５グルー
プ）に伝搬されている。
してのキャリー信号Ｃ4を生成するための回路を設け
る。これは、第２セットまでのアダーの出力が全て共に
１であるか否かを示す信号であるＡＮＤ回路９５の出力
とＡＮＤ回路１１９の出力とが入力されるＡＮＤ回路１
２１、このＡＮＤ回路１２１の出力とキャリー信号Ｃ3
とが入力されるＡＮＤ回路１２３と、このＡＮＤ回路１
２３の出力と第３セットまでのキャリーであるＯＲ回路
１２７の出力とが入力されるＯＲ回路１２９から構成さ
れる。このキャリー信号Ｃ4は図２の回路（第５グルー
プ）に伝搬されている。
【００３４】第５グループを図２に示す。この第５グル
ープは、４つのセットを含んでいる。第１セットは、ハ
ーフ・アダー１３１とフル・アダー１３３を含み、これ
らはリプル・アダーを構成する。第２セットは、ハーフ
・アダー１３５とフル・アダー１３７を含み、これらは
リプル・アダーを構成する。第３セットは、ハーフ・ア
ダー１３９とフル・アダー１４１及び１４３を含み、こ
れらはリプル・アダーを構成する。第４セットは、ハー
フ・アダー１４５とフル・アダー１４７乃至１５１を含
む。
ープは、４つのセットを含んでいる。第１セットは、ハ
ーフ・アダー１３１とフル・アダー１３３を含み、これ
らはリプル・アダーを構成する。第２セットは、ハーフ
・アダー１３５とフル・アダー１３７を含み、これらは
リプル・アダーを構成する。第３セットは、ハーフ・ア
ダー１３９とフル・アダー１４１及び１４３を含み、こ
れらはリプル・アダーを構成する。第４セットは、ハー
フ・アダー１４５とフル・アダー１４７乃至１５１を含
む。
【００３５】ハーフ・アダー１３１の出力とキャリー信
号Ｃ4とは排他的論理和回路１５５に入力され、この回
路１５５の出力は出力Ｚ16となる。また、ハーフ・アダ
ー１３１の出力とキャリー信号Ｃ4とはＡＮＤ回路１５
７に入力され、このＡＮＤ回路１５７の出力とフル・ア
ダー１３３の出力とが入力される排他的論理和回路１５
９の出力が、出力Ｚ17となる。アダー１３１及び１３３
の出力はＡＮＤ回路１５３に入力され、このＡＮＤ回路
１５３の出力と、フル・アダー１３３の出力とが、第２
セットに伝搬される。
号Ｃ4とは排他的論理和回路１５５に入力され、この回
路１５５の出力は出力Ｚ16となる。また、ハーフ・アダ
ー１３１の出力とキャリー信号Ｃ4とはＡＮＤ回路１５
７に入力され、このＡＮＤ回路１５７の出力とフル・ア
ダー１３３の出力とが入力される排他的論理和回路１５
９の出力が、出力Ｚ17となる。アダー１３１及び１３３
の出力はＡＮＤ回路１５３に入力され、このＡＮＤ回路
１５３の出力と、フル・アダー１３３の出力とが、第２
セットに伝搬される。
【００３６】また、第１グループから第５グループの第
１セットまでのキャリーを生成するために、キャリー信
号Ｃ4とＡＮＤ回路１５３の出力とが入力されたＡＮＤ
回路１６１と、このＡＮＤ回路１６１の出力とフル・ア
ダー１３３のキャリーとが入力されたＯＲ回路１６３と
が設けられる。このＯＲ回路１６３の出力とハーフ・ア
ダー１３５の出力とが入力される排他的論理和回路１６
５の出力が、出力Ｚ18となる。また、ＯＲ回路１６３の
出力とハーフ・アダー１３５の出力とがＡＮＤ回路１６
７に入力され、このＡＮＤ回路１６７の出力とフル・ア
ダー１３７の出力とが入力される排他的論理和回路１６
９の出力が、出力Ｚ19となる。
１セットまでのキャリーを生成するために、キャリー信
号Ｃ4とＡＮＤ回路１５３の出力とが入力されたＡＮＤ
回路１６１と、このＡＮＤ回路１６１の出力とフル・ア
ダー１３３のキャリーとが入力されたＯＲ回路１６３と
が設けられる。このＯＲ回路１６３の出力とハーフ・ア
ダー１３５の出力とが入力される排他的論理和回路１６
５の出力が、出力Ｚ18となる。また、ＯＲ回路１６３の
出力とハーフ・アダー１３５の出力とがＡＮＤ回路１６
７に入力され、このＡＮＤ回路１６７の出力とフル・ア
ダー１３７の出力とが入力される排他的論理和回路１６
９の出力が、出力Ｚ19となる。
【００３７】第５グループ内での第２セットまでのキャ
リーを生成するために、アダー１３５及び１３７の出力
が入力されるＡＮＤ回路１７１、このＡＮＤ回路１７１
の出力とフル・アダー１３３のキャリーとが入力される
ＡＮＤ回路１７５、及びこのＡＮＤ回路１７５の出力と
フル・アダー１３７のキャリーが入力されるＯＲ回路１
７７が設けられる。ここで発生された第５グループ内で
の第２セットまでのキャリーは、第３セットに伝搬され
る。また、第２セットまでの全てのアダーの出力が共に
１であるか否かを示す信号を生成するために、ＡＮＤ回
路１５３の出力とＡＮＤ回路１７１の出力とが入力され
るＡＮＤ回路１７３が設けられ、このＡＮＤ回路１７３
の出力も第３セットに伝搬される。
リーを生成するために、アダー１３５及び１３７の出力
が入力されるＡＮＤ回路１７１、このＡＮＤ回路１７１
の出力とフル・アダー１３３のキャリーとが入力される
ＡＮＤ回路１７５、及びこのＡＮＤ回路１７５の出力と
フル・アダー１３７のキャリーが入力されるＯＲ回路１
７７が設けられる。ここで発生された第５グループ内で
の第２セットまでのキャリーは、第３セットに伝搬され
る。また、第２セットまでの全てのアダーの出力が共に
１であるか否かを示す信号を生成するために、ＡＮＤ回
路１５３の出力とＡＮＤ回路１７１の出力とが入力され
るＡＮＤ回路１７３が設けられ、このＡＮＤ回路１７３
の出力も第３セットに伝搬される。
【００３８】第１グループから第５グループの第２セッ
トまでのキャリーを生成するために、キャリー信号Ｃ4
と第２セットまでの全てのアダーの出力が共に１である
か否かを示す信号であるＡＮＤ回路１７３の出力とが入
力されるＡＮＤ回路１７９と、このＡＮＤ回路１７９の
出力と第２セットまでのキャリーであるＯＲ回路１７７
の出力とを入力とするＯＲ回路１８１が設けられる。こ
のＯＲ回路１８１の出力と、ハーフ・アダー１３９の出
力とが排他的論理和回路１８３に入力され、この回路１
８３の出力が出力Ｚ20である。また、ＯＲ回路１８１の
出力とハーフ・アダー１３９の出力とがＡＮＤ回路１８
５に入力され、このＡＮＤ回路１８５の出力とフル・ア
ダー１４１の出力とが入力される排他的論理和回路１８
７の出力が出力Ｚ21である。
トまでのキャリーを生成するために、キャリー信号Ｃ4
と第２セットまでの全てのアダーの出力が共に１である
か否かを示す信号であるＡＮＤ回路１７３の出力とが入
力されるＡＮＤ回路１７９と、このＡＮＤ回路１７９の
出力と第２セットまでのキャリーであるＯＲ回路１７７
の出力とを入力とするＯＲ回路１８１が設けられる。こ
のＯＲ回路１８１の出力と、ハーフ・アダー１３９の出
力とが排他的論理和回路１８３に入力され、この回路１
８３の出力が出力Ｚ20である。また、ＯＲ回路１８１の
出力とハーフ・アダー１３９の出力とがＡＮＤ回路１８
５に入力され、このＡＮＤ回路１８５の出力とフル・ア
ダー１４１の出力とが入力される排他的論理和回路１８
７の出力が出力Ｚ21である。
【００３９】アダー１３９及び１４１の出力は、ＡＮＤ
回路１９３に入力される。このＡＮＤ回路１９３の出力
とＯＲ回路１８１の出力とはＡＮＤ回路１８９に入力さ
れる。このＡＮＤ回路１８９の出力とフル・アダー１４
３の出力とが排他的論理和回路１９１に入力され、この
回路１９１の出力が出力Ｚ22である。
回路１９３に入力される。このＡＮＤ回路１９３の出力
とＯＲ回路１８１の出力とはＡＮＤ回路１８９に入力さ
れる。このＡＮＤ回路１８９の出力とフル・アダー１４
３の出力とが排他的論理和回路１９１に入力され、この
回路１９１の出力が出力Ｚ22である。
【００４０】第５グループ内での第３セットまでのキャ
リーを生成するために、フル・アダー１４３の出力とＡ
ＮＤ回路１９３の出力とが入力されるＡＮＤ回路１９５
と、このＡＮＤ回路１９５の出力と第５グループ内の第
２セットまでのキャリーであるＯＲ回路１７７の出力と
が入力されるＡＮＤ回路１９９と、このＡＮＤ回路１９
９の出力とフル・アダー１４３のキャリーとが入力され
るＯＲ回路２０１とが設けられる。第１乃至第３セット
の全てのアダーの出力が共に１であるか否かを示す信号
を生成するために、第２セットから伝搬されたＡＮＤ回
路１７３の出力とＡＮＤ回路１９５の出力とを入力とす
るＡＮＤ回路１９７が設けられる。このＡＮＤ回路１９
７の出力と、ＯＲ回路２０１の出力である、第５グルー
プ内での第３セットまでのキャリーとが、第４セットに
伝搬される。
リーを生成するために、フル・アダー１４３の出力とＡ
ＮＤ回路１９３の出力とが入力されるＡＮＤ回路１９５
と、このＡＮＤ回路１９５の出力と第５グループ内の第
２セットまでのキャリーであるＯＲ回路１７７の出力と
が入力されるＡＮＤ回路１９９と、このＡＮＤ回路１９
９の出力とフル・アダー１４３のキャリーとが入力され
るＯＲ回路２０１とが設けられる。第１乃至第３セット
の全てのアダーの出力が共に１であるか否かを示す信号
を生成するために、第２セットから伝搬されたＡＮＤ回
路１７３の出力とＡＮＤ回路１９５の出力とを入力とす
るＡＮＤ回路１９７が設けられる。このＡＮＤ回路１９
７の出力と、ＯＲ回路２０１の出力である、第５グルー
プ内での第３セットまでのキャリーとが、第４セットに
伝搬される。
【００４１】第１グループから当該第５グループの第３
セットまでのキャリーを生成するために、キャリー信号
Ｃ4とＡＮＤ回路１９７の出力とが入力されるＡＮＤ回
路２０３と、このＡＮＤ回路２０３の出力と第５グルー
プ内での第３セットまでのキャリーであるＯＲ回路２０
１の出力とが入力されるＯＲ回路２０５が設けられる。
このＯＲ回路２０５の出力は、ハーフ・アダー１４５と
共に排他的論理和回路２０７に入力され、この回路２０
７の出力が出力Ｚ23となる。また、ＯＲ回路２０５の出
力とハーフ・アダー１４５の出力とがＡＮＤ回路２０９
に入力される。このＡＮＤ回路２０９の出力とフル・ア
ダー１４７の出力とが入力された排他的論理和回路２１
１の出力が、出力Ｚ24である。
セットまでのキャリーを生成するために、キャリー信号
Ｃ4とＡＮＤ回路１９７の出力とが入力されるＡＮＤ回
路２０３と、このＡＮＤ回路２０３の出力と第５グルー
プ内での第３セットまでのキャリーであるＯＲ回路２０
１の出力とが入力されるＯＲ回路２０５が設けられる。
このＯＲ回路２０５の出力は、ハーフ・アダー１４５と
共に排他的論理和回路２０７に入力され、この回路２０
７の出力が出力Ｚ23となる。また、ＯＲ回路２０５の出
力とハーフ・アダー１４５の出力とがＡＮＤ回路２０９
に入力される。このＡＮＤ回路２０９の出力とフル・ア
ダー１４７の出力とが入力された排他的論理和回路２１
１の出力が、出力Ｚ24である。
【００４２】アダー１４５及び１４７の出力はＡＮＤ回
路２１５に入力され、そのＡＮＤ回路２１５の出力とＯ
Ｒ回路２０５の出力とはＡＮＤ回路２１３に入力され
る。このＡＮＤ回路２１３の出力とフル・アダー１４９
の出力とが入力される排他的論理和回路２１７の出力
は、出力Ｚ25である。また、フル・アダー１４９の出力
とＡＮＤ回路２１５の出力はＡＮＤ回路２１９に入力さ
れ、このＡＮＤ回路２１９の出力とＯＲ回路２０５の出
力とがＡＮＤ回路２２１に入力される。このＡＮＤ回路
２２１の出力は、フル・アダー１５１の出力と共に、排
他的論理和回路２２３に入力され、この回路２２３の出
力が出力Ｚ26である。
路２１５に入力され、そのＡＮＤ回路２１５の出力とＯ
Ｒ回路２０５の出力とはＡＮＤ回路２１３に入力され
る。このＡＮＤ回路２１３の出力とフル・アダー１４９
の出力とが入力される排他的論理和回路２１７の出力
は、出力Ｚ25である。また、フル・アダー１４９の出力
とＡＮＤ回路２１５の出力はＡＮＤ回路２１９に入力さ
れ、このＡＮＤ回路２１９の出力とＯＲ回路２０５の出
力とがＡＮＤ回路２２１に入力される。このＡＮＤ回路
２２１の出力は、フル・アダー１５１の出力と共に、排
他的論理和回路２２３に入力され、この回路２２３の出
力が出力Ｚ26である。
【００４３】第５グループ内での第４セットまでのキャ
リーを生成するために、ＡＮＤ回路２１９の出力とフル
・アダー１５１の出力とが入力されるＡＤＮ回路２２５
と、このＡＮＤ回路２２５の出力と第３セットまでのキ
ャリーであるＯＲ回路２０１の出力とが入力されるＡＮ
Ｄ回路２２９と、このＡＮＤ回路２２９の出力とフル・
アダー１５１のキャリーとを入力とするＯＲ回路２３１
とが設けられる。さらに、第５グループのキャリー信号
Ｃ5を第６グループに出力するために、ＡＮＤ回路１９
７の出力とＡＮＤ回路２２５の出力とが入力されるＡＮ
Ｄ回路２２７と、このＡＮＤ回路２２７の出力とキャリ
ー信号Ｃ４とが入力されるＡＮＤ回路２３７と、このＡ
ＮＤ回路２３７の出力と第４セットまでのキャリーであ
るＯＲ回路２３１の出力とが入力されるＯＲ回路２３５
が設けられる。このＯＲ回路２３５の出力が、第５グル
ープのキャリー信号Ｃ5である。
リーを生成するために、ＡＮＤ回路２１９の出力とフル
・アダー１５１の出力とが入力されるＡＤＮ回路２２５
と、このＡＮＤ回路２２５の出力と第３セットまでのキ
ャリーであるＯＲ回路２０１の出力とが入力されるＡＮ
Ｄ回路２２９と、このＡＮＤ回路２２９の出力とフル・
アダー１５１のキャリーとを入力とするＯＲ回路２３１
とが設けられる。さらに、第５グループのキャリー信号
Ｃ5を第６グループに出力するために、ＡＮＤ回路１９
７の出力とＡＮＤ回路２２５の出力とが入力されるＡＮ
Ｄ回路２２７と、このＡＮＤ回路２２７の出力とキャリ
ー信号Ｃ４とが入力されるＡＮＤ回路２３７と、このＡ
ＮＤ回路２３７の出力と第４セットまでのキャリーであ
るＯＲ回路２３１の出力とが入力されるＯＲ回路２３５
が設けられる。このＯＲ回路２３５の出力が、第５グル
ープのキャリー信号Ｃ5である。
【００４４】以上は２６ビット分の回路であるが、先に
示した分割方法に従って、図２より上位の回路を構成す
ることができる。
示した分割方法に従って、図２より上位の回路を構成す
ることができる。
【００４５】図１及び図２の回路では、フル・アダー１
及び他のハーフ・アダーは、前のキャリーを見ずに加算
の実行を開始する。そして、第１及び第２グループ、及
び第３グループ以降の各セットにおいてリプル・キャリ
ー方式で加算を実行する。後は、排他的論理和、ＡＮＤ
及びＯＲ回路それぞれの処理を実施すると、出力が生成
される。
及び他のハーフ・アダーは、前のキャリーを見ずに加算
の実行を開始する。そして、第１及び第２グループ、及
び第３グループ以降の各セットにおいてリプル・キャリ
ー方式で加算を実行する。後は、排他的論理和、ＡＮＤ
及びＯＲ回路それぞれの処理を実施すると、出力が生成
される。
【００４６】特に注意すべきは、第３グループ以降の各
セットごとに、当該グループ内の当該セットまでのキャ
リーを生成するための回路、当該セットまでを全て（前
のグループをも含める）考慮したキャリーを生成するた
めの回路を設ける点である。前者は、セット内の全ての
アダーの出力が共に１であるか否かを示す信号Ｆ１を生
成するための１又は複数のＡＮＤ回路、前のセットから
伝搬されたキャリーＣ０と先のＡＮＤ回路の出力Ｆ１と
が入力されるＡＮＤ回路、そしてこのＡＮＤ回路の出力
と当該セットのリプル・キャリーＣ１とが入力されるＯ
Ｒ回路から構成される。これらの回路を数式にすると、
Ｃ２＝Ｃ１＋Ｆ１・Ｃ０となる。後者についても、グル
ープ内の当該セットまでの全てのアダーの出力が共に１
であるか否かを表す信号Ｆ２を生成するための１又は複
数のＡＮＤ回路、先のＡＮＤ回路の出力Ｆ２と前のグル
ープからキャリー信号とＣが入力されるＡＮＤ回路、及
びこのＡＮＤ回路の出力と当該セットに関するキャリー
Ｃ２'が入力されるＯＲ回路から構成される。これらの
回路を数式にするとＣ３＝Ｃ２'＋Ｆ２・Ｃとなる。
セットごとに、当該グループ内の当該セットまでのキャ
リーを生成するための回路、当該セットまでを全て（前
のグループをも含める）考慮したキャリーを生成するた
めの回路を設ける点である。前者は、セット内の全ての
アダーの出力が共に１であるか否かを示す信号Ｆ１を生
成するための１又は複数のＡＮＤ回路、前のセットから
伝搬されたキャリーＣ０と先のＡＮＤ回路の出力Ｆ１と
が入力されるＡＮＤ回路、そしてこのＡＮＤ回路の出力
と当該セットのリプル・キャリーＣ１とが入力されるＯ
Ｒ回路から構成される。これらの回路を数式にすると、
Ｃ２＝Ｃ１＋Ｆ１・Ｃ０となる。後者についても、グル
ープ内の当該セットまでの全てのアダーの出力が共に１
であるか否かを表す信号Ｆ２を生成するための１又は複
数のＡＮＤ回路、先のＡＮＤ回路の出力Ｆ２と前のグル
ープからキャリー信号とＣが入力されるＡＮＤ回路、及
びこのＡＮＤ回路の出力と当該セットに関するキャリー
Ｃ２'が入力されるＯＲ回路から構成される。これらの
回路を数式にするとＣ３＝Ｃ２'＋Ｆ２・Ｃとなる。
【００４７】図１及び図２は正論理にて記述している
が、負論理で記述することも可能である。その際にはＡ
ＮＤやＯＲ回路は、ＮＡＮＤやＮＯＲ回路となる。よっ
て、図１及び図２どおりの回路でなくとも、実質的に同
様の処理を実施することができる。また、その際には上
記数式も変形されるが、実質的に同一の処理を行うもの
であればよい。
が、負論理で記述することも可能である。その際にはＡ
ＮＤやＯＲ回路は、ＮＡＮＤやＮＯＲ回路となる。よっ
て、図１及び図２どおりの回路でなくとも、実質的に同
様の処理を実施することができる。また、その際には上
記数式も変形されるが、実質的に同一の処理を行うもの
であればよい。
【００４８】このような２段キャリー・スキップ・アダ
ーでは、ビット数Ｎについて、Ｎ≦ｎ（ｎ＋１）（ｎ＋
２）／６＋ｎ＋３なるｎについて、全体のゲート・ディ
レイは（ｎ＋５）となる。ｎとＮの関係を以下に示す。 ｎ Ｎ ４ ２７ ５ ４３ ６ ６５ ７ ９４ ８ １３１ ９ １７７ ・ ・・ １７ ９８９ １８ １１６１ ・・ ・・・ ２２ ２０４９ よって、２段キャリー・スキップ・アダーでは、１０２
４ビットでゲート・ディレイは２３に、２０４８ビット
でゲート・ディレイ２７となる。
ーでは、ビット数Ｎについて、Ｎ≦ｎ（ｎ＋１）（ｎ＋
２）／６＋ｎ＋３なるｎについて、全体のゲート・ディ
レイは（ｎ＋５）となる。ｎとＮの関係を以下に示す。 ｎ Ｎ ４ ２７ ５ ４３ ６ ６５ ７ ９４ ８ １３１ ９ １７７ ・ ・・ １７ ９８９ １８ １１６１ ・・ ・・・ ２２ ２０４９ よって、２段キャリー・スキップ・アダーでは、１０２
４ビットでゲート・ディレイは２３に、２０４８ビット
でゲート・ディレイ２７となる。
【００４９】Ｂ．３段キャリー・スキップ・アダー ３重にキャリー・スキップを行った場合の分割法を以下
に示す。 ３ −− ２ −−− ２，２ −−−−− ２，２ ２，２ −−−−− ２，２ ２，２ ２，２，３ −−−−−− ２，２ ２，２ ２，２，３ ２，２，３，４ −−−−−−− ここで、横線は最上位のブロック分け（クラスと呼ぶ）
を示し、第４クラス以降は、クラス内の行はグループの
ブロック分けを示し、各グループ内のブロック分け（セ
ットと呼ぶ）は列の数字により表される。
に示す。 ３ −− ２ −−− ２，２ −−−−− ２，２ ２，２ −−−−− ２，２ ２，２ ２，２，３ −−−−−− ２，２ ２，２ ２，２，３ ２，２，３，４ −−−−−−− ここで、横線は最上位のブロック分け（クラスと呼ぶ）
を示し、第４クラス以降は、クラス内の行はグループの
ブロック分けを示し、各グループ内のブロック分け（セ
ットと呼ぶ）は列の数字により表される。
【００５０】それでは、図３にこの回路を示す。第１ク
ラスは、フル・アダー３０１乃至３０５を含み、これら
はリプル・アダーを構成する。そして、各フル・アダー
の出力は、それぞれＺ0，Ｚ1，Ｚ2となる。最初のフル
・アダー３０１には、ａ0信号が入力されているが、こ
れは無くともよい。よって、ハーフ・アダーを用いるこ
とも可能である。フル・アダー３０５のキャリー信号Ｃ
1は、第２クラスに伝搬される。
ラスは、フル・アダー３０１乃至３０５を含み、これら
はリプル・アダーを構成する。そして、各フル・アダー
の出力は、それぞれＺ0，Ｚ1，Ｚ2となる。最初のフル
・アダー３０１には、ａ0信号が入力されているが、こ
れは無くともよい。よって、ハーフ・アダーを用いるこ
とも可能である。フル・アダー３０５のキャリー信号Ｃ
1は、第２クラスに伝搬される。
【００５１】第２クラスは、ハーフ・アダー３０７及び
フル・アダー３０９を含み、これらはリプル・アダーを
構成する。そして、キャリー信号Ｃ1とハーフ・アダー
３０７の出力とが入力される排他的論理和回路３３５の
出力は、出力Ｚ3となる。また、ハーフ・アダー３０７
の出力とキャリー信号Ｃ1とはＡＮＤ回路３３７に入力
され、このＡＮＤ回路３３７の出力とフル・アダー３０
９の出力とが入力される排他的論理和回路３４５の出力
が、出力Ｚ4となる。
フル・アダー３０９を含み、これらはリプル・アダーを
構成する。そして、キャリー信号Ｃ1とハーフ・アダー
３０７の出力とが入力される排他的論理和回路３３５の
出力は、出力Ｚ3となる。また、ハーフ・アダー３０７
の出力とキャリー信号Ｃ1とはＡＮＤ回路３３７に入力
され、このＡＮＤ回路３３７の出力とフル・アダー３０
９の出力とが入力される排他的論理和回路３４５の出力
が、出力Ｚ4となる。
【００５２】アダー３０７及び３０９の出力はＡＮＤ回
路３３９に入力される。このＡＮＤ回路３３９の出力と
キャリー信号Ｃ1とはＡＮＤ回路３４１に入力され、こ
のＡＮＤ回路３４１の出力とフル・アダー３０９のキャ
リーとが入力されるＯＲ回路３４３にて、第２クラスま
でのキャリー信号Ｃ2が生成される。このキャリー信号
Ｃ2は、第３クラスに伝搬される。
路３３９に入力される。このＡＮＤ回路３３９の出力と
キャリー信号Ｃ1とはＡＮＤ回路３４１に入力され、こ
のＡＮＤ回路３４１の出力とフル・アダー３０９のキャ
リーとが入力されるＯＲ回路３４３にて、第２クラスま
でのキャリー信号Ｃ2が生成される。このキャリー信号
Ｃ2は、第３クラスに伝搬される。
【００５３】第３クラスは、２つのセットを含む。第１
セットは、ハーフ・アダー３１１とフル・アダー３１３
とを含み、これらはリプル・アダーを構成する。第２セ
ットは、ハーフ・アダー３１５とフル・アダー３１７と
を含み、これらはリプル・アダーを構成する。
セットは、ハーフ・アダー３１１とフル・アダー３１３
とを含み、これらはリプル・アダーを構成する。第２セ
ットは、ハーフ・アダー３１５とフル・アダー３１７と
を含み、これらはリプル・アダーを構成する。
【００５４】キャリー信号Ｃ2とハーフ・アダー３１１
の出力とが入力される排他的論理回路３４７の出力は、
出力Ｚ5である。また、ハーフ・アダー３１１の出力と
キャリー信号Ｃ2は、ＡＮＤ回路３４９に入力され、こ
のＡＮＤ回路３４９の出力とフル・アダー３１３の出力
とが入力される排他的論理和回路３５１の出力は、出力
Ｚ6である。
の出力とが入力される排他的論理回路３４７の出力は、
出力Ｚ5である。また、ハーフ・アダー３１１の出力と
キャリー信号Ｃ2は、ＡＮＤ回路３４９に入力され、こ
のＡＮＤ回路３４９の出力とフル・アダー３１３の出力
とが入力される排他的論理和回路３５１の出力は、出力
Ｚ6である。
【００５５】アダー３１１及び３１３の出力はＡＮＤ回
路３５３に入力され、このＡＮＤ回路３５３の出力と、
フル・アダー３１３のキャリーは、第２セットに伝搬さ
れる。
路３５３に入力され、このＡＮＤ回路３５３の出力と、
フル・アダー３１３のキャリーは、第２セットに伝搬さ
れる。
【００５６】第１クラスから第３クラスの第１セットま
でのキャリーを生成するために、ＡＮＤ回路３５３の出
力とキャリー信号Ｃ2とが入力されるＡＮＤ回路３５５
と、このＡＮＤ回路３５５の出力とフル・アダー３１３
の出力と入力されるＯＲ回路３５７が設けられる。この
ＯＲ回路３５７の出力と、ハーフ・アダー３１５の出力
は、排他的論理和回路３５９に入力され、この回路３５
９の出力は出力Ｚ7となる。また、ＯＲ回路３５７の出
力とハーフ・アダー３１５の出力とはＡＮＤ回路３６１
に入力され、このＡＮＤ回路３６１の出力とフル・アダ
ー３１７の出力とが入力される排他的論理和回路３６３
の出力は、出力Ｚ8となる。
でのキャリーを生成するために、ＡＮＤ回路３５３の出
力とキャリー信号Ｃ2とが入力されるＡＮＤ回路３５５
と、このＡＮＤ回路３５５の出力とフル・アダー３１３
の出力と入力されるＯＲ回路３５７が設けられる。この
ＯＲ回路３５７の出力と、ハーフ・アダー３１５の出力
は、排他的論理和回路３５９に入力され、この回路３５
９の出力は出力Ｚ7となる。また、ＯＲ回路３５７の出
力とハーフ・アダー３１５の出力とはＡＮＤ回路３６１
に入力され、このＡＮＤ回路３６１の出力とフル・アダ
ー３１７の出力とが入力される排他的論理和回路３６３
の出力は、出力Ｚ8となる。
【００５７】アダー３１５及び３１７の出力はＡＮＤ回
路３６５に入力される。この第３クラス内での第２セッ
トまでのキャリーを生成するために、ＡＮＤ回路３６５
の出力とフル・アダー３１３のキャリーとが入力される
ＡＮＤ回路３７１、このＡＮＤ回路３７１の出力とフル
・アダー３１７の出力とが入力されるＯＲ回路３７３が
設けられる。また、第３クラスに存在する全てのアダー
の出力が共に１であるか否かを示す信号を生成するた
め、ＡＮＤ回路３５３の出力とＡＮＤ回路３６５の出力
とを入力とするＡＮＤ回路３６７が設けられる。そし
て、第３クラスまでのキャリー信号Ｃ3を生成するため
に、キャリー信号Ｃ2とこのＡＮＤ回路３６７の出力と
が入力されるＡＮＤ回路３６９と、このＡＮＤ回路３６
９の出力とＯＲ回路３７３の出力とが入力されるＯＲ回
路３７５が設けられる。このＯＲ回路３７５の出力が、
第３クラスのキャリー信号Ｃ3である。キャリー信号Ｃ3
は第４クラスに伝搬される。
路３６５に入力される。この第３クラス内での第２セッ
トまでのキャリーを生成するために、ＡＮＤ回路３６５
の出力とフル・アダー３１３のキャリーとが入力される
ＡＮＤ回路３７１、このＡＮＤ回路３７１の出力とフル
・アダー３１７の出力とが入力されるＯＲ回路３７３が
設けられる。また、第３クラスに存在する全てのアダー
の出力が共に１であるか否かを示す信号を生成するた
め、ＡＮＤ回路３５３の出力とＡＮＤ回路３６５の出力
とを入力とするＡＮＤ回路３６７が設けられる。そし
て、第３クラスまでのキャリー信号Ｃ3を生成するため
に、キャリー信号Ｃ2とこのＡＮＤ回路３６７の出力と
が入力されるＡＮＤ回路３６９と、このＡＮＤ回路３６
９の出力とＯＲ回路３７３の出力とが入力されるＯＲ回
路３７５が設けられる。このＯＲ回路３７５の出力が、
第３クラスのキャリー信号Ｃ3である。キャリー信号Ｃ3
は第４クラスに伝搬される。
【００５８】ここまでは、２段キャリー・スキップ回路
の第３グループまでと同様である。
の第３グループまでと同様である。
【００５９】次に、第４クラスについて説明する。この
第４クラスは、２つのグループを有している。そして、
各グループは２つのセットを有している。第１グループ
の第１セットは、ハーフ・アダー３１９及びフル・アダ
ー３２１を含み、これらはリプル・アダーを構成する。
また、第１グループの第２セットは、ハーフ・アダー３
２３及びフル・アダー３２５を含み、これらはリプル・
アダーを構成する。第２グループの第１セットは、ハー
フ・アダー３２７及びフル・アダー３２９を含み、これ
らはリプル・アダーを構成する。第２グループの第２セ
ットは、ハーフ・アダー３３１及びフル・アダー３３３
とを含み、これらはリプル・アダーを構成する。
第４クラスは、２つのグループを有している。そして、
各グループは２つのセットを有している。第１グループ
の第１セットは、ハーフ・アダー３１９及びフル・アダ
ー３２１を含み、これらはリプル・アダーを構成する。
また、第１グループの第２セットは、ハーフ・アダー３
２３及びフル・アダー３２５を含み、これらはリプル・
アダーを構成する。第２グループの第１セットは、ハー
フ・アダー３２７及びフル・アダー３２９を含み、これ
らはリプル・アダーを構成する。第２グループの第２セ
ットは、ハーフ・アダー３３１及びフル・アダー３３３
とを含み、これらはリプル・アダーを構成する。
【００６０】ハーフ・アダー３１９の出力とキャリー信
号Ｃ3は、排他的論理和回路３７７に入力され、この回
路３７７の出力が出力Ｚ9である。また、キャリー信号
Ｃ3とハーフ・アダー３１９の出力は、ＡＮＤ回路３７
９に入力され、このＡＮＤ回路３７９の出力とフル・ア
ダー３２１の出力とが入力される排他的論理和回路３８
１の出力は、出力Ｚ10である。アダー３１９及び３２１
の出力は、ＡＮＤ回路３８３に入力される。このＡＮＤ
回路３８３の出力と、フル・アダー３２１のキャリー
は、第２セットに伝搬される。
号Ｃ3は、排他的論理和回路３７７に入力され、この回
路３７７の出力が出力Ｚ9である。また、キャリー信号
Ｃ3とハーフ・アダー３１９の出力は、ＡＮＤ回路３７
９に入力され、このＡＮＤ回路３７９の出力とフル・ア
ダー３２１の出力とが入力される排他的論理和回路３８
１の出力は、出力Ｚ10である。アダー３１９及び３２１
の出力は、ＡＮＤ回路３８３に入力される。このＡＮＤ
回路３８３の出力と、フル・アダー３２１のキャリー
は、第２セットに伝搬される。
【００６１】第１クラスから第４クラスのこの第１セッ
トまでのキャリーを生成するため、ＡＮＤ回路３８３の
出力及びキャリー信号Ｃ3とが入力されるＡＮＤ回路３
８５と、このＡＮＤ回路３８５の出力とフル・アダー３
２１の出力とが入力されるＯＲ回路３８７とが設けられ
る。このＯＲ回路３８７の出力は、ハーフ・アダー３２
３の出力と共に排他的論理和回路３８９に入力され、こ
の回路３８９の出力は出力Ｚ11である。また、ＯＲ回路
３８７の出力とハーフ・アダー３２３の出力はＡＮＤ回
路３９１に入力され、このＡＮＤ回路３９１の出力とフ
ル・アダー３２５の出力とが入力される排他的論理和回
路３９３の出力は出力Ｚ12である。
トまでのキャリーを生成するため、ＡＮＤ回路３８３の
出力及びキャリー信号Ｃ3とが入力されるＡＮＤ回路３
８５と、このＡＮＤ回路３８５の出力とフル・アダー３
２１の出力とが入力されるＯＲ回路３８７とが設けられ
る。このＯＲ回路３８７の出力は、ハーフ・アダー３２
３の出力と共に排他的論理和回路３８９に入力され、こ
の回路３８９の出力は出力Ｚ11である。また、ＯＲ回路
３８７の出力とハーフ・アダー３２３の出力はＡＮＤ回
路３９１に入力され、このＡＮＤ回路３９１の出力とフ
ル・アダー３２５の出力とが入力される排他的論理和回
路３９３の出力は出力Ｚ12である。
【００６２】第２セット内のアダー３２３及び３２５の
出力が共に１であるか否か表す信号を生成するため、ア
ダー３２３及び３２５の出力が入力されるＡＮＤ回路３
９５が設けられる。また、第２セットまで、すなわち、
第１グループまでのキャリーを生成するために、このＡ
ＮＤ回路３９５の出力と第１セットのフル・アダー３２
１のキャリーとが入力されるＡＤＮ回路３９９と、この
ＡＮＤ回路３９９の出力とフル・アダー３２５の出力と
が入力されたＯＲ回路４０１が設けられる。この第１グ
ループのキャリーは第２グループに伝搬される。さら
に、ＡＮＤ回路３８３の出力とＡＮＤ回路３９５の出力
とが入力されたＡＮＤ回路３９７の出力も、第２グルー
プに伝搬される。このＡＮＤ回路３９７の出力は、第１
グループ内の全てのアダーが共に１を出力しているか否
かを示す信号である。
出力が共に１であるか否か表す信号を生成するため、ア
ダー３２３及び３２５の出力が入力されるＡＮＤ回路３
９５が設けられる。また、第２セットまで、すなわち、
第１グループまでのキャリーを生成するために、このＡ
ＮＤ回路３９５の出力と第１セットのフル・アダー３２
１のキャリーとが入力されるＡＤＮ回路３９９と、この
ＡＮＤ回路３９９の出力とフル・アダー３２５の出力と
が入力されたＯＲ回路４０１が設けられる。この第１グ
ループのキャリーは第２グループに伝搬される。さら
に、ＡＮＤ回路３８３の出力とＡＮＤ回路３９５の出力
とが入力されたＡＮＤ回路３９７の出力も、第２グルー
プに伝搬される。このＡＮＤ回路３９７の出力は、第１
グループ内の全てのアダーが共に１を出力しているか否
かを示す信号である。
【００６３】第１クラスから第４クラスの第１グループ
までのキャリーを生成するために、ＡＮＤ回路３９７の
出力とキャリー信号Ｃ3が入力されるＡＮＤ回路４０３
と、このＡＮＤ回路４０３の出力とＯＲ回路４０１の出
力とが入力されるＯＲ回路４０５が設けられる。このＯ
Ｒ回路４０５の出力は、ハーフ・アダー３２７の出力と
共に、排他的論理和回路４０７に出力され、この回路４
０７の出力は出力Ｚ13となる。また、ＯＲ回路４０５の
出力と、ハーフ・アダー３２７の出力はＡＮＤ回路４０
９に入力され、このＡＮＤ回路４０９の出力とフル・ア
ダー３２９の出力とが入力される排他的論理和回路４１
１の出力が、出力Ｚ14となる。
までのキャリーを生成するために、ＡＮＤ回路３９７の
出力とキャリー信号Ｃ3が入力されるＡＮＤ回路４０３
と、このＡＮＤ回路４０３の出力とＯＲ回路４０１の出
力とが入力されるＯＲ回路４０５が設けられる。このＯ
Ｒ回路４０５の出力は、ハーフ・アダー３２７の出力と
共に、排他的論理和回路４０７に出力され、この回路４
０７の出力は出力Ｚ13となる。また、ＯＲ回路４０５の
出力と、ハーフ・アダー３２７の出力はＡＮＤ回路４０
９に入力され、このＡＮＤ回路４０９の出力とフル・ア
ダー３２９の出力とが入力される排他的論理和回路４１
１の出力が、出力Ｚ14となる。
【００６４】第２グループの第１セットのアダー３２７
及び３２９の出力はＡＮＤ回路４１３に入力される。こ
のＡＮＤ回路４１３の出力と、フル・アダー３２９の出
力は、第２グループの第２セットに伝搬される。そし
て、第４クラス内における第２グループの第１セットま
でのキャリーを生成するため、ＡＮＤ回路４１３の出力
とＯＲ回路４０１の出力とが入力されるＡＮＤ回路４１
９と、このＡＮＤ回路４１９の出力とフル・アダー３２
９の出力とが入力されるＯＲ回路４２３が設けられる。
及び３２９の出力はＡＮＤ回路４１３に入力される。こ
のＡＮＤ回路４１３の出力と、フル・アダー３２９の出
力は、第２グループの第２セットに伝搬される。そし
て、第４クラス内における第２グループの第１セットま
でのキャリーを生成するため、ＡＮＤ回路４１３の出力
とＯＲ回路４０１の出力とが入力されるＡＮＤ回路４１
９と、このＡＮＤ回路４１９の出力とフル・アダー３２
９の出力とが入力されるＯＲ回路４２３が設けられる。
【００６５】さらに、第１クラスから第４クラスの第２
グループの第１セットまでのキャリーを生成するため
に、ＡＮＤ回路３９７の出力とＡＮＤ回路４１３の出力
とが入力されるＡＮＤ回路４１５と、このＡＮＤ回路４
１５の出力とキャリー信号Ｃ3とが入力されるＡＮＤ回
路４１７と、このＡＮＤ回路４１７の出力とＯＲ回路４
２３の出力とが入力されるＯＲ回路４２１が設けられ
る。
グループの第１セットまでのキャリーを生成するため
に、ＡＮＤ回路３９７の出力とＡＮＤ回路４１３の出力
とが入力されるＡＮＤ回路４１５と、このＡＮＤ回路４
１５の出力とキャリー信号Ｃ3とが入力されるＡＮＤ回
路４１７と、このＡＮＤ回路４１７の出力とＯＲ回路４
２３の出力とが入力されるＯＲ回路４２１が設けられ
る。
【００６６】ＯＲ回路４２１の出力とハーフ・アダー３
３１の出力とが排他的論理和回路４２５に入力され、こ
の回路４２５の出力が出力Ｚ15となる。また、ＯＲ回路
４２１の出力とハーフ・アダー３３１の出力とはＡＮＤ
回路４２７に入力される。このＡＮＤ回路４２７の出力
とフル・アダー３３３の出力とが排他的論理和回路４２
９に入力され、この回路４２９の出力が出力Ｚ16とな
る。
３１の出力とが排他的論理和回路４２５に入力され、こ
の回路４２５の出力が出力Ｚ15となる。また、ＯＲ回路
４２１の出力とハーフ・アダー３３１の出力とはＡＮＤ
回路４２７に入力される。このＡＮＤ回路４２７の出力
とフル・アダー３３３の出力とが排他的論理和回路４２
９に入力され、この回路４２９の出力が出力Ｚ16とな
る。
【００６７】第２グループ第２セットのアダーの出力が
共に１であるか否か示す信号を作成するために、アダー
３３１及び３３３の出力はＡＮＤ回路４３１に入力され
る。そして、第２グループにおけるキャリーを生成する
ために、ＡＮＤ回路４３１の出力とフル・アダー３２９
のキャリーとが入力されるＡＮＤ回路４３５と、このＡ
ＮＤ回路４３５の出力とフル・アダー３３３のキャリー
が入力されるＯＲ回路４３７が設けられる。
共に１であるか否か示す信号を作成するために、アダー
３３１及び３３３の出力はＡＮＤ回路４３１に入力され
る。そして、第２グループにおけるキャリーを生成する
ために、ＡＮＤ回路４３１の出力とフル・アダー３２９
のキャリーとが入力されるＡＮＤ回路４３５と、このＡ
ＮＤ回路４３５の出力とフル・アダー３３３のキャリー
が入力されるＯＲ回路４３７が設けられる。
【００６８】さらに、第１グループ及び第２グループを
合わせたキャリーを生成するために、ＡＮＤ回路４１３
の出力とＡＮＤ回路４３１の出力とが入力されるＡＮＤ
回路４３３と、このＡＮＤ回路４３３の出力とＯＲ回路
４０１の出力とが入力されるＡＮＤ回路４４１と、この
ＡＮＤ回路４４１の出力とＯＲ回路４３７の出力とが入
力されるＯＲ回路４４３が設けられる。
合わせたキャリーを生成するために、ＡＮＤ回路４１３
の出力とＡＮＤ回路４３１の出力とが入力されるＡＮＤ
回路４３３と、このＡＮＤ回路４３３の出力とＯＲ回路
４０１の出力とが入力されるＡＮＤ回路４４１と、この
ＡＮＤ回路４４１の出力とＯＲ回路４３７の出力とが入
力されるＯＲ回路４４３が設けられる。
【００６９】さらに、第４クラスまでの全体のキャリー
信号Ｃ4を生成するために、ＡＮＤ回路３９７の出力と
ＡＮＤ回路４３３の出力とが入力されるＡＮＤ回路４３
９と、このＡＮＤ回路４３９の出力とキャリー信号Ｃ3
とが入力されるＡＮＤ回路４４５と、このＡＮＤ回路４
４５の出力及びＯＲ回路４４３の出力が入力されるＯＲ
回路４４７が設けられる。
信号Ｃ4を生成するために、ＡＮＤ回路３９７の出力と
ＡＮＤ回路４３３の出力とが入力されるＡＮＤ回路４３
９と、このＡＮＤ回路４３９の出力とキャリー信号Ｃ3
とが入力されるＡＮＤ回路４４５と、このＡＮＤ回路４
４５の出力及びＯＲ回路４４３の出力が入力されるＯＲ
回路４４７が設けられる。
【００７０】図４には図３の続きの回路であって、第５
クラスが示されている。この第５クラスは、３つのグル
ープを有している。第１グループは、２つのセットを、
第２グループは２つのセットを、第３グループは３つの
セットを有している。第１グループの第１セットは、ハ
ーフ・アダー４５１及びフル・アダー４５３を含み、こ
れらはリプル・アダーを構成する。第１グループの第２
セットは、ハーフ・アダー４５５及びフル・アダー４５
７を含み、これらはリプル・アダーを構成する。第２グ
ループの第１セットは、ハーフ・アダー４５９及びフル
・アダー４６１を含み、これらはリプル・アダーを構成
する。第２グループの第２セットは、ハーフ・アダー４
６３及びフル・アダー４６５を含み、これらはリプル・
アダーを構成する。第３グループの第１セットは、ハー
フ・アダー４６７及びフル・アダー４６９を含み、これ
らはリプル・アダーを構成する。第３グループの第２セ
ットは、ハーフ・アダー４７１及びフル・アダー４７３
を含み、これらはリプル・アダーを構成する。第３グル
ープの第３セットは、ハーフ・アダー４７５とフル・ア
ダー４７７及び４７９を含み、これらはリプル・アダー
を構成する。
クラスが示されている。この第５クラスは、３つのグル
ープを有している。第１グループは、２つのセットを、
第２グループは２つのセットを、第３グループは３つの
セットを有している。第１グループの第１セットは、ハ
ーフ・アダー４５１及びフル・アダー４５３を含み、こ
れらはリプル・アダーを構成する。第１グループの第２
セットは、ハーフ・アダー４５５及びフル・アダー４５
７を含み、これらはリプル・アダーを構成する。第２グ
ループの第１セットは、ハーフ・アダー４５９及びフル
・アダー４６１を含み、これらはリプル・アダーを構成
する。第２グループの第２セットは、ハーフ・アダー４
６３及びフル・アダー４６５を含み、これらはリプル・
アダーを構成する。第３グループの第１セットは、ハー
フ・アダー４６７及びフル・アダー４６９を含み、これ
らはリプル・アダーを構成する。第３グループの第２セ
ットは、ハーフ・アダー４７１及びフル・アダー４７３
を含み、これらはリプル・アダーを構成する。第３グル
ープの第３セットは、ハーフ・アダー４７５とフル・ア
ダー４７７及び４７９を含み、これらはリプル・アダー
を構成する。
【００７１】第４クラスから伝達されてくるキャリー信
号Ｃ4とハーフ・アダー４５１の出力とは排他的論理和
回路４８３に入力され、この回路４８３の出力が出力Ｚ
17となる。また、キャリー信号Ｃ4とハーフ・アダー４
５１の出力はＡＮＤ回路４８１に入力され、このＡＮＤ
回路４８１の出力とフル・アダー４５３の出力とが入力
される排他的論理和回路４８５の出力は出力Ｚ18とな
る。
号Ｃ4とハーフ・アダー４５１の出力とは排他的論理和
回路４８３に入力され、この回路４８３の出力が出力Ｚ
17となる。また、キャリー信号Ｃ4とハーフ・アダー４
５１の出力はＡＮＤ回路４８１に入力され、このＡＮＤ
回路４８１の出力とフル・アダー４５３の出力とが入力
される排他的論理和回路４８５の出力は出力Ｚ18とな
る。
【００７２】第１セットのアダー４５１及び４５３の出
力は、ＡＮＤ回路４８１に入力される。このＡＮＤ回路
４８１の出力と、フル・アダー４５３のキャリーは、第
２セットに伝搬される。また、第１クラスからこのクラ
スの第１グループの第１セットまでのキャリーを生成す
るために、ＡＮＤ回路４８１の出力とキャリー信号Ｃ4
の出力とが入力されるＡＮＤ回路４８９と、このＡＮＤ
回路４８９の出力とフル・アダー４５３のキャリーとが
入力されるＯＲ回路４９１が設けられる。
力は、ＡＮＤ回路４８１に入力される。このＡＮＤ回路
４８１の出力と、フル・アダー４５３のキャリーは、第
２セットに伝搬される。また、第１クラスからこのクラ
スの第１グループの第１セットまでのキャリーを生成す
るために、ＡＮＤ回路４８１の出力とキャリー信号Ｃ4
の出力とが入力されるＡＮＤ回路４８９と、このＡＮＤ
回路４８９の出力とフル・アダー４５３のキャリーとが
入力されるＯＲ回路４９１が設けられる。
【００７３】ＯＲ回路４９１の出力は、ハーフ・アダー
４５５の出力と共に、排他的論理和回路４９３に入力さ
れ、この排他的論理和回路４９３の出力は出力Ｚ19であ
る。また、ＯＲ回路４９１の出力とハーフ・アダー４５
５の出力は、ＡＮＤ回路４９５に入力される。このＡＮ
Ｄ回路４９５の出力とフル・アダー４５７の出力とが排
他的論理和回路４９７に入力され、この回路４９７の出
力が出力Ｚ20となる。
４５５の出力と共に、排他的論理和回路４９３に入力さ
れ、この排他的論理和回路４９３の出力は出力Ｚ19であ
る。また、ＯＲ回路４９１の出力とハーフ・アダー４５
５の出力は、ＡＮＤ回路４９５に入力される。このＡＮ
Ｄ回路４９５の出力とフル・アダー４５７の出力とが排
他的論理和回路４９７に入力され、この回路４９７の出
力が出力Ｚ20となる。
【００７４】第２セットのアダー４５５及び４５７の出
力は、ＡＮＤ回路５０３に入力される。第１グループに
おけるキャリーを生成するために、ＡＮＤ回路５０３の
出力とフル・アダー４５３の出力とが入力されるＡＮＤ
回路５０７と、このＡＮＤ回路５０７の出力とフル・ア
ダー４５７のキャリーが入力されるＯＲ回路５０９とが
設けられる。また、第１グループの全てのアダーの出力
が共に１であるか否かを示す信号を生成するため、ＡＮ
Ｄ回路４８１の出力とＡＮＤ回路５０３の出力とが入力
されるＡＮＤ回路５０５が設けられる。このＡＮＤ回路
５０５の出力とＯＲ回路５０９の出力が第２グループに
伝搬される。
力は、ＡＮＤ回路５０３に入力される。第１グループに
おけるキャリーを生成するために、ＡＮＤ回路５０３の
出力とフル・アダー４５３の出力とが入力されるＡＮＤ
回路５０７と、このＡＮＤ回路５０７の出力とフル・ア
ダー４５７のキャリーが入力されるＯＲ回路５０９とが
設けられる。また、第１グループの全てのアダーの出力
が共に１であるか否かを示す信号を生成するため、ＡＮ
Ｄ回路４８１の出力とＡＮＤ回路５０３の出力とが入力
されるＡＮＤ回路５０５が設けられる。このＡＮＤ回路
５０５の出力とＯＲ回路５０９の出力が第２グループに
伝搬される。
【００７５】第１クラスからこのクラスの第１グループ
までのキャリーを生成するために、キャリー信号Ｃ4と
ＡＮＤ回路５０５の出力とが入力されるＡＮＤ回路４９
９と、このＡＮＤ回路４９９の出力とＯＲ回路５０９の
出力が入力されるＯＲ回路５０１とが設けられる。この
ＯＲ回路５０１の出力は、ハーフ・アダー４５９の出力
と共に、排他的論理和回路５１１に入力され、この回路
５１１の出力が出力Ｚ21となる。また、ＯＲ回路５０１
の出力とハーフ・アダー４５９の出力とがＡＮＤ回路５
１３に入力される。このＡＮＤ回路５１３の出力とフル
・アダー４６１の出力とが排他的論理和回路５１５に入
力され、この回路５１５の出力が出力Ｚ22となる。
までのキャリーを生成するために、キャリー信号Ｃ4と
ＡＮＤ回路５０５の出力とが入力されるＡＮＤ回路４９
９と、このＡＮＤ回路４９９の出力とＯＲ回路５０９の
出力が入力されるＯＲ回路５０１とが設けられる。この
ＯＲ回路５０１の出力は、ハーフ・アダー４５９の出力
と共に、排他的論理和回路５１１に入力され、この回路
５１１の出力が出力Ｚ21となる。また、ＯＲ回路５０１
の出力とハーフ・アダー４５９の出力とがＡＮＤ回路５
１３に入力される。このＡＮＤ回路５１３の出力とフル
・アダー４６１の出力とが排他的論理和回路５１５に入
力され、この回路５１５の出力が出力Ｚ22となる。
【００７６】第２グループの第１セットのアダー４５９
及び４６１の出力はＡＮＤ回路５１７に入力される。こ
のＡＮＤ回路５１７とフル・アダー４６１のキャリー
は、共に第２グループの第２セットに伝搬される。
及び４６１の出力はＡＮＤ回路５１７に入力される。こ
のＡＮＤ回路５１７とフル・アダー４６１のキャリー
は、共に第２グループの第２セットに伝搬される。
【００７７】また、第５クラス内の第２グループの第１
セットまでのキャリーを生成するために、ＯＲ回路５０
９の出力とＡＮＤ回路５１７の出力とが入力されるＡＮ
Ｄ回路５２５と、フル・アダー４６１のキャリーとＡＮ
Ｄ回路５２５の出力とが入力されるＯＲ回路５２７が設
けられる。さらに、全体として、第５クラスの第２グル
ープの第１セットまでのキャリーを生成するために、Ａ
ＮＤ回路５０５の出力とＡＮＤ回路５１７の出力とが入
力されるＡＮＤ回路５１９と、キャリー信号Ｃ4とＡＮ
Ｄ回路５１９の出力とが入力されるＡＮＤ回路５２１
と、このＡＮＤ回路５２１の出力とＯＲ回路５２７の出
力とが入力されるＯＲ回路５２３とが設けられる。
セットまでのキャリーを生成するために、ＯＲ回路５０
９の出力とＡＮＤ回路５１７の出力とが入力されるＡＮ
Ｄ回路５２５と、フル・アダー４６１のキャリーとＡＮ
Ｄ回路５２５の出力とが入力されるＯＲ回路５２７が設
けられる。さらに、全体として、第５クラスの第２グル
ープの第１セットまでのキャリーを生成するために、Ａ
ＮＤ回路５０５の出力とＡＮＤ回路５１７の出力とが入
力されるＡＮＤ回路５１９と、キャリー信号Ｃ4とＡＮ
Ｄ回路５１９の出力とが入力されるＡＮＤ回路５２１
と、このＡＮＤ回路５２１の出力とＯＲ回路５２７の出
力とが入力されるＯＲ回路５２３とが設けられる。
【００７８】このＯＲ回路５２３の出力は、ハーフ・ア
ダー４６３の出力と共に、排他的論理和回路５２９に入
力され、この回路５２９の出力は出力Ｚ23である。ま
た、ＯＲ回路５２３の出力とハーフ・アダー４６３の出
力はＡＮＤ回路５３１に入力される。このＡＮＤ回路５
３１の出力とフル・アダー４６５の出力は排他的論理和
回路５３３に入力され、この回路５３３の出力は出力Ｚ
24である。
ダー４６３の出力と共に、排他的論理和回路５２９に入
力され、この回路５２９の出力は出力Ｚ23である。ま
た、ＯＲ回路５２３の出力とハーフ・アダー４６３の出
力はＡＮＤ回路５３１に入力される。このＡＮＤ回路５
３１の出力とフル・アダー４６５の出力は排他的論理和
回路５３３に入力され、この回路５３３の出力は出力Ｚ
24である。
【００７９】第２グループ第２セットのアダー４６３及
び４６５の出力はＡＮＤ回路５３５に入力される。第２
グループとしてのキャリーを生成するために、ＡＮＤ回
路５３５の出力とフル・アダー４６１の出力とが入力さ
れるＡＮＤ回路５４１と、このＡＮＤ回路５４１の出力
とフル・アダー４６５のキャリーとが入力されるＯＲ回
路５４５とが設けられる。
び４６５の出力はＡＮＤ回路５３５に入力される。第２
グループとしてのキャリーを生成するために、ＡＮＤ回
路５３５の出力とフル・アダー４６１の出力とが入力さ
れるＡＮＤ回路５４１と、このＡＮＤ回路５４１の出力
とフル・アダー４６５のキャリーとが入力されるＯＲ回
路５４５とが設けられる。
【００８０】さらに、第１グループ及び第２グループに
ついてのキャリーを生成するために、ＡＮＤ回路５１７
の出力及びＡＮＤ回路５３５の出力が入力されるＡＮＤ
回路５３７と、このＡＮＤ回路５３７の出力と第１グル
ープから伝搬されるキャリーであるＯＲ回路５０９の出
力とが入力されるＡＮＤ回路５４３と、このＡＮＤ回路
５４３の出力とＯＲ回路５４５の出力とが入力されるＯ
Ｒ回路５４７とが設けられる。ＡＮＤ回路５３７の出力
と、第１グループから伝搬されるＡＮＤ回路５０５の出
力とはＡＮＤ回路５３９に入力される。このＡＮＤ回路
５３９の出力とＯＲ回路５４７の出力は第３グループに
伝搬される。
ついてのキャリーを生成するために、ＡＮＤ回路５１７
の出力及びＡＮＤ回路５３５の出力が入力されるＡＮＤ
回路５３７と、このＡＮＤ回路５３７の出力と第１グル
ープから伝搬されるキャリーであるＯＲ回路５０９の出
力とが入力されるＡＮＤ回路５４３と、このＡＮＤ回路
５４３の出力とＯＲ回路５４５の出力とが入力されるＯ
Ｒ回路５４７とが設けられる。ＡＮＤ回路５３７の出力
と、第１グループから伝搬されるＡＮＤ回路５０５の出
力とはＡＮＤ回路５３９に入力される。このＡＮＤ回路
５３９の出力とＯＲ回路５４７の出力は第３グループに
伝搬される。
【００８１】また、全体として第５クラスの第２グルー
プまでのキャリーを生成するために、ＡＮＤ回路５３９
の出力とキャリー信号Ｃ4とが入力されるＡＮＤ回路５
４９と、このＡＮＤ回路５４９の出力とＯＲ回路５４７
の出力とが入力されるＯＲ回路５５１とが設けられる。
プまでのキャリーを生成するために、ＡＮＤ回路５３９
の出力とキャリー信号Ｃ4とが入力されるＡＮＤ回路５
４９と、このＡＮＤ回路５４９の出力とＯＲ回路５４７
の出力とが入力されるＯＲ回路５５１とが設けられる。
【００８２】このＯＲ回路５５１の出力は、ハーフ・ア
ダー４６７の出力と共に、排他的論理和回路５５３に入
力される。この回路５５３の出力は出力Ｚ25である。Ｏ
Ｒ回路５５１の出力とハーフ・アダー４６７の出力とは
ＡＮＤ回路５５５に入力される。このＡＮＤ回路５５５
の出力とフル・アダー４６９の出力は排他的論理和回路
５５７に入力され、この回路５５７の出力は出力Ｚ26で
ある。
ダー４６７の出力と共に、排他的論理和回路５５３に入
力される。この回路５５３の出力は出力Ｚ25である。Ｏ
Ｒ回路５５１の出力とハーフ・アダー４６７の出力とは
ＡＮＤ回路５５５に入力される。このＡＮＤ回路５５５
の出力とフル・アダー４６９の出力は排他的論理和回路
５５７に入力され、この回路５５７の出力は出力Ｚ26で
ある。
【００８３】第３グループの第１セットのアダー４６７
及び４６９の出力はＡＮＤ回路５５９に入力される。こ
のＡＮＤ回路５５９の出力及びフル・アダー４６９のキ
ャリーは第２セットに伝搬される。また、第５クラス内
において第３グループの第１セットまでのキャリーを生
成するために、ＡＮＤ回路５５９の出力とＯＲ回路５４
７の出力とが入力されるＡＮＤ回路５６５と、このＡＮ
Ｄ回路５６５の出力とフル・アダー４６９のキャリーと
が入力されるＯＲ回路５６７とが設けられる。
及び４６９の出力はＡＮＤ回路５５９に入力される。こ
のＡＮＤ回路５５９の出力及びフル・アダー４６９のキ
ャリーは第２セットに伝搬される。また、第５クラス内
において第３グループの第１セットまでのキャリーを生
成するために、ＡＮＤ回路５５９の出力とＯＲ回路５４
７の出力とが入力されるＡＮＤ回路５６５と、このＡＮ
Ｄ回路５６５の出力とフル・アダー４６９のキャリーと
が入力されるＯＲ回路５６７とが設けられる。
【００８４】さらに、全体として第５クラスの第３グル
ープの第１セットまでのキャリーを生成するために、Ａ
ＮＤ回路５３９の出力とＡＮＤ回路５５９の出力とが入
力されるＡＮＤ回路５６１と、このＡＮＤ回路５６１の
出力とキャリー信号Ｃ4とが入力されるＡＮＤ回路５６
３と、このＡＮＤ回路５６３の出力とＯＲ回路５６７の
出力とが入力されるＯＲ回路５６９が設けられる。
ープの第１セットまでのキャリーを生成するために、Ａ
ＮＤ回路５３９の出力とＡＮＤ回路５５９の出力とが入
力されるＡＮＤ回路５６１と、このＡＮＤ回路５６１の
出力とキャリー信号Ｃ4とが入力されるＡＮＤ回路５６
３と、このＡＮＤ回路５６３の出力とＯＲ回路５６７の
出力とが入力されるＯＲ回路５６９が設けられる。
【００８５】また、ＯＲ回路５６９の出力とハーフ・ア
ダー４７１の出力とは排他的論理和回路５７１に出力さ
れ、この回路５７１の出力は出力Ｚ27である。また、Ｏ
Ｒ回路５６９の出力とハーフ・アダー４７１の出力はＡ
ＮＤ回路５７３に入力される。このＡＮＤ回路５７３の
出力とフル・アダー４７３の出力とが排他的論理和回路
５７５に入力され、この回路５７５の出力は出力Ｚ28で
ある。
ダー４７１の出力とは排他的論理和回路５７１に出力さ
れ、この回路５７１の出力は出力Ｚ27である。また、Ｏ
Ｒ回路５６９の出力とハーフ・アダー４７１の出力はＡ
ＮＤ回路５７３に入力される。このＡＮＤ回路５７３の
出力とフル・アダー４７３の出力とが排他的論理和回路
５７５に入力され、この回路５７５の出力は出力Ｚ28で
ある。
【００８６】第３グループの第２セットのアダー４７１
及び４７３の出力はＡＮＤ回路５７７に入力される。こ
の第３グループの第２セットまでのキャリーを生成する
ために、ＡＮＤ回路５７７の出力とフル・アダー４６９
のキャリーとが入力されるＡＮＤ回路５８１と、このＡ
ＮＤ回路５８１の出力とフル・アダー４７３のキャリー
とが入力されるＯＲ回路５８３とが設けられる。さら
に、第５クラス内でこの第３グループの第２セットまで
のキャリーを生成するために、ＡＮＤ回路５５９の出力
及びＡＮＤ回路５７７の出力とが入力されるＡＮＤ回路
５７９と、このＡＮＤ回路５７９の出力と第２グループ
から伝搬されるキャリーであるＯＲ回路５４７の出力と
が入力されるＡＮＤ回路５８７と、このＡＮＤ回路５８
７の出力とＯＲ回路５８３の出力とが入力されるＯＲ回
路５８９とが設けられる。
及び４７３の出力はＡＮＤ回路５７７に入力される。こ
の第３グループの第２セットまでのキャリーを生成する
ために、ＡＮＤ回路５７７の出力とフル・アダー４６９
のキャリーとが入力されるＡＮＤ回路５８１と、このＡ
ＮＤ回路５８１の出力とフル・アダー４７３のキャリー
とが入力されるＯＲ回路５８３とが設けられる。さら
に、第５クラス内でこの第３グループの第２セットまで
のキャリーを生成するために、ＡＮＤ回路５５９の出力
及びＡＮＤ回路５７７の出力とが入力されるＡＮＤ回路
５７９と、このＡＮＤ回路５７９の出力と第２グループ
から伝搬されるキャリーであるＯＲ回路５４７の出力と
が入力されるＡＮＤ回路５８７と、このＡＮＤ回路５８
７の出力とＯＲ回路５８３の出力とが入力されるＯＲ回
路５８９とが設けられる。
【００８７】さらに、全体として第３グループの第２セ
ットまでのキャリーを生成するために、第２グループか
ら伝搬されるＡＮＤ回路５３９の出力とＡＮＤ回路５７
９の出力とが入力されるＡＮＤ回路５８５と、このＡＮ
Ｄ回路５８５の出力とキャリー信号Ｃ4とが入力される
ＡＮＤ回路５９１と、このＡＮＤ回路５９１の出力とＯ
Ｒ回路５８９の出力とが入力されるＯＲ回路５９３とが
設けられる。
ットまでのキャリーを生成するために、第２グループか
ら伝搬されるＡＮＤ回路５３９の出力とＡＮＤ回路５７
９の出力とが入力されるＡＮＤ回路５８５と、このＡＮ
Ｄ回路５８５の出力とキャリー信号Ｃ4とが入力される
ＡＮＤ回路５９１と、このＡＮＤ回路５９１の出力とＯ
Ｒ回路５８９の出力とが入力されるＯＲ回路５９３とが
設けられる。
【００８８】このＯＲ回路５９３の出力は、ハーフ・ア
ダー４７５の出力と共に、排他的論理和回路５９５に入
力され、この回路５９５の出力は出力Ｚ29である。ま
た、ＯＲ回路５９３の出力とハーフ・アダー４７５の出
力とは、ＡＮＤ回路５９７に入力される。そして、ＡＮ
Ｄ回路５９７の出力とフル・アダー４７７の出力は排他
的論理和回路５９９に入力され、この回路５９９の出力
は出力Ｚ30となる。アダー４７５及び４７７の出力はＡ
ＮＤ回路６０１に入力される。このＡＮＤ回路６０１の
出力とＯＲ回路５９３の出力とがＡＮＤ回路６０３に入
力される。このＡＮＤ回路６０３の出力とフル・アダー
４７９の出力とが排他的論理和回路６０５に入力され、
この回路６０５の出力が出力Ｚ31となる。
ダー４７５の出力と共に、排他的論理和回路５９５に入
力され、この回路５９５の出力は出力Ｚ29である。ま
た、ＯＲ回路５９３の出力とハーフ・アダー４７５の出
力とは、ＡＮＤ回路５９７に入力される。そして、ＡＮ
Ｄ回路５９７の出力とフル・アダー４７７の出力は排他
的論理和回路５９９に入力され、この回路５９９の出力
は出力Ｚ30となる。アダー４７５及び４７７の出力はＡ
ＮＤ回路６０１に入力される。このＡＮＤ回路６０１の
出力とＯＲ回路５９３の出力とがＡＮＤ回路６０３に入
力される。このＡＮＤ回路６０３の出力とフル・アダー
４７９の出力とが排他的論理和回路６０５に入力され、
この回路６０５の出力が出力Ｚ31となる。
【００８９】第３グループの第３セットの全てのアダー
が共に１を出力しているか否か示す信号を作成するため
に、ＡＮＤ回路６０１の出力とフル・アダー４７９の出
力とが入力されるＡＮＤ回路６０７が設けられる。そし
て、第３グループにおけるキャリーを生成するために、
ＡＮＤ回路６０７の出力と第２セットから伝搬されてく
るキャリーであるＯＲ回路５８３の出力とが入力される
ＡＮＤ回路６１１と、このＡＮＤ回路６１１の出力とフ
ル・アダー４７９のキャリーとが入力されるＯＲ回路６
１３とが設けられる。
が共に１を出力しているか否か示す信号を作成するため
に、ＡＮＤ回路６０１の出力とフル・アダー４７９の出
力とが入力されるＡＮＤ回路６０７が設けられる。そし
て、第３グループにおけるキャリーを生成するために、
ＡＮＤ回路６０７の出力と第２セットから伝搬されてく
るキャリーであるＯＲ回路５８３の出力とが入力される
ＡＮＤ回路６１１と、このＡＮＤ回路６１１の出力とフ
ル・アダー４７９のキャリーとが入力されるＯＲ回路６
１３とが設けられる。
【００９０】さらに、第５クラスとしてのキャリーを生
成するために、ＡＮＤ回路５７９の出力とＡＮＤ回路６
０７の出力とが入力されるＡＮＤ回路６０９と、このＡ
ＮＤ回路６０９の出力と第２グループから伝搬されるキ
ャリーであるＯＲ回路５４７の出力とが入力されるＡＮ
Ｄ回路６１７と、このＡＮＤ回路６１７の出力とＯＲ回
路６１３の出力とが入力されるＯＲ回路６１９とが設け
られる。
成するために、ＡＮＤ回路５７９の出力とＡＮＤ回路６
０７の出力とが入力されるＡＮＤ回路６０９と、このＡ
ＮＤ回路６０９の出力と第２グループから伝搬されるキ
ャリーであるＯＲ回路５４７の出力とが入力されるＡＮ
Ｄ回路６１７と、このＡＮＤ回路６１７の出力とＯＲ回
路６１３の出力とが入力されるＯＲ回路６１９とが設け
られる。
【００９１】また、全体として第５クラスまでのキャリ
ー信号Ｃ5を生成するために、ＡＮＤ回路５３９の出力
とＡＮＤ回路６０９の出力とが入力されるＡＮＤ回路６
１５と、このＡＮＤ回路６１５の出力とキャリー信号Ｃ
4とが入力されるＡＮＤ回路６２１と、このＡＮＤ回路
６２１の出力とＯＲ回路６１９の出力とが入力されるＯ
Ｒ回路６２３とが設けられる。
ー信号Ｃ5を生成するために、ＡＮＤ回路５３９の出力
とＡＮＤ回路６０９の出力とが入力されるＡＮＤ回路６
１５と、このＡＮＤ回路６１５の出力とキャリー信号Ｃ
4とが入力されるＡＮＤ回路６２１と、このＡＮＤ回路
６２１の出力とＯＲ回路６１９の出力とが入力されるＯ
Ｒ回路６２３とが設けられる。
【００９２】以上は３２ビット分の回路であるが、先に
示した分割方法に従って、図４以下の回路を構成するこ
とができる。
示した分割方法に従って、図４以下の回路を構成するこ
とができる。
【００９３】図３及び図４の回路では、フル・アダー３
０１及び他のハーフ・アダーは、前のキャリーを見ずに
加算の実行を開始する。そして、第１及び第２クラス、
及び第３クラス以降の各セットにおいてリプル・キャリ
ー方式で加算を実行する。後は、排他的論理和、ＡＮＤ
及びＯＲ回路それぞれの処理を実施すると、出力が生成
される。
０１及び他のハーフ・アダーは、前のキャリーを見ずに
加算の実行を開始する。そして、第１及び第２クラス、
及び第３クラス以降の各セットにおいてリプル・キャリ
ー方式で加算を実行する。後は、排他的論理和、ＡＮＤ
及びＯＲ回路それぞれの処理を実施すると、出力が生成
される。
【００９４】図３及び図４で注意すべき点は、あるセッ
トのキャリー信号Ｃ１と、あるセットの１つ前のセット
に関連するキャリーＣ０と、当該セット内の全てのアダ
ーの出力が共に１であるか否かを示す信号Ｆ１とが用意
され、これらに対してＣ２＝Ｃ１＋Ｆ１・Ｃ０なる信号
を生成するＡＮＤ回路とＯＲ回路が存在することであ
る。また、あるセットより２以上下位のセットからこの
２以上下位のセットに関連するキャリー信号Ｃが当該あ
るセットに伝達されている場合には、この２以上下位の
セットより上位で当該あるセットまでの各セットに含ま
れるアダーの出力が共に１であるか否かを示す信号Ｆ２
と、キャリー信号Ｃと、先に述べた信号Ｃ２とから、Ｃ
３＝Ｃ２＋Ｆ２・Ｃなる信号を生成するＡＮＤ回路とＯ
Ｒ回路が存在することである。さらに、３本目のスキッ
プされたキャリー信号が存在するため、あるセットより
２以上下位のセットからこの２以上下位のセットに関連
するキャリー信号Ｃが当該あるセットに伝達されている
場合には、この２以上下位のセットより上位で当該ある
セットまでの各セットに含まれるアダーの出力が共に１
であるか否かを示す信号Ｆ２と、キャリー信号Ｃと、先
に述べた信号Ｃ３とから、Ｃ４＝Ｃ３＋Ｆ２・Ｃなる信
号を生成するＡＮＤ回路とＯＲ回路が存在することであ
る。
トのキャリー信号Ｃ１と、あるセットの１つ前のセット
に関連するキャリーＣ０と、当該セット内の全てのアダ
ーの出力が共に１であるか否かを示す信号Ｆ１とが用意
され、これらに対してＣ２＝Ｃ１＋Ｆ１・Ｃ０なる信号
を生成するＡＮＤ回路とＯＲ回路が存在することであ
る。また、あるセットより２以上下位のセットからこの
２以上下位のセットに関連するキャリー信号Ｃが当該あ
るセットに伝達されている場合には、この２以上下位の
セットより上位で当該あるセットまでの各セットに含ま
れるアダーの出力が共に１であるか否かを示す信号Ｆ２
と、キャリー信号Ｃと、先に述べた信号Ｃ２とから、Ｃ
３＝Ｃ２＋Ｆ２・Ｃなる信号を生成するＡＮＤ回路とＯ
Ｒ回路が存在することである。さらに、３本目のスキッ
プされたキャリー信号が存在するため、あるセットより
２以上下位のセットからこの２以上下位のセットに関連
するキャリー信号Ｃが当該あるセットに伝達されている
場合には、この２以上下位のセットより上位で当該ある
セットまでの各セットに含まれるアダーの出力が共に１
であるか否かを示す信号Ｆ２と、キャリー信号Ｃと、先
に述べた信号Ｃ３とから、Ｃ４＝Ｃ３＋Ｆ２・Ｃなる信
号を生成するＡＮＤ回路とＯＲ回路が存在することであ
る。
【００９５】図３及び図４は正論理にて記述している
が、負論理で記述することも可能である。その際にはＡ
ＮＤやＯＲ回路は、ＮＡＮＤやＮＯＲ回路となる。よっ
て、図３及び図４どおりの回路でなくとも、実質的に同
様の処理を実施することができる。また、その際には上
記数式も変形されるが、実質的に同一の処理を行うもの
であればよい。
が、負論理で記述することも可能である。その際にはＡ
ＮＤやＯＲ回路は、ＮＡＮＤやＮＯＲ回路となる。よっ
て、図３及び図４どおりの回路でなくとも、実質的に同
様の処理を実施することができる。また、その際には上
記数式も変形されるが、実質的に同一の処理を行うもの
であればよい。
【００９６】このような三段キャリー・スキップ・アダ
ーでは、ビット数Ｎについて、Ｎ≦ｎ（ｎ＋１）（ｎ＋
２）（ｎ＋３）／２４＋ｎ（ｎ＋１）／２＋２ｎ＋５な
るｎについて、ゲート・ディレイはｎ＋７となる。１０
２４ビットであればゲート・ディレイは１８となる。２
０４８ビットではゲート・ディレイは２１となる。
ーでは、ビット数Ｎについて、Ｎ≦ｎ（ｎ＋１）（ｎ＋
２）（ｎ＋３）／２４＋ｎ（ｎ＋１）／２＋２ｎ＋５な
るｎについて、ゲート・ディレイはｎ＋７となる。１０
２４ビットであればゲート・ディレイは１８となる。２
０４８ビットではゲート・ディレイは２１となる。
【００９７】ｎとＮの関係を以下に示す。
【００９８】Ｃ．四段キャリー・スキップ・アダー 以上述べた事項の延長としてキャリー・スキップを４重
にかけることもできる。この場合のリプル・アダーの分
割方法は以下のとおりである。
にかけることもできる。この場合のリプル・アダーの分
割方法は以下のとおりである。
【００９９】 ３ −− ２ −−− ２，２ −−−− ２，２ ２，２ ２，２ ２，２ −−−−− ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２，３ −−−−−−−− ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２，３ ２，２ ２，２ ２，２，３ ２，２，３，４ −−−−−−−−− ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２，３ ２，２ ２，２ ２，２，３ ２，２，３，４ ２，２ ２，２ ２，２，３ ２，２，３，４ ２，２，３，４，５ −−−−−−−−−−−
【０１００】横線で一番上位のクラスの区分けがなさ
れ、次にそのクラスのなかで空行が入れられたところで
二番目に上位のクラスの区分けがなされる。そして、２
番目に上位のクラスの中で各行が三番目のクラスの区分
けであり、各数字が最下位のクラスの区分けである。数
字は、リプル・アダーに含まれるアダーの数を示す。
れ、次にそのクラスのなかで空行が入れられたところで
二番目に上位のクラスの区分けがなされる。そして、２
番目に上位のクラスの中で各行が三番目のクラスの区分
けであり、各数字が最下位のクラスの区分けである。数
字は、リプル・アダーに含まれるアダーの数を示す。
【０１０１】この場合、ビット数ＮについてＮ≦ｎ（ｎ
＋１）（ｎ＋２）（ｎ＋３）（ｎ＋４）／１２０＋ｎ
（ｎ＋１）（ｎ＋２）／６＋ｎ（ｎ＋１）＋５ｎ＋７な
るｎについて、ゲート・ディレイは（ｎ＋９）となる。
よって、１０２４ビットの場合には１７で、２０４８ビ
ットの場合には１９となる。以下、ｎとＮの関係を示
す。
＋１）（ｎ＋２）（ｎ＋３）（ｎ＋４）／１２０＋ｎ
（ｎ＋１）（ｎ＋２）／６＋ｎ（ｎ＋１）＋５ｎ＋７な
るｎについて、ゲート・ディレイは（ｎ＋９）となる。
よって、１０２４ビットの場合には１７で、２０４８ビ
ットの場合には１９となる。以下、ｎとＮの関係を示
す。
【０１０２】Ｄ．五段キャリー・スキップ・アダー キャリー・スキップを５重にかけた場合の分割法を以下
に示す。 ３ −− ２ −−− ２，２ −−−− ２，２ ２，２ ２，２ ２，２ −−−−− ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２，３ −−−−−−−− ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２，３ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２，３ ２，２ ２，２ ２，２，３ ２，２，３，４ −−−−−−−−− ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２，３ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２，３ ２，２ ２，２ ２，２，３ ２，２，３，４ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２，３ ２，２ ２，２ ２，２ ２，２ ２，２，３ ２，２，３，４ ２，２ ２，２ ２，２，３，４ ２，２，３，４，５ −−−−−−−−−−−
に示す。 ３ −− ２ −−− ２，２ −−−− ２，２ ２，２ ２，２ ２，２ −−−−− ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２，３ −−−−−−−− ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２，３ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２，３ ２，２ ２，２ ２，２，３ ２，２，３，４ −−−−−−−−− ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２，３ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２，３ ２，２ ２，２ ２，２，３ ２，２，３，４ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２ ２，２，３ ２，２ ２，２ ２，２ ２，２ ２，２，３ ２，２，３，４ ２，２ ２，２ ２，２，３，４ ２，２，３，４，５ −−−−−−−−−−−
【０１０３】この場合、ビット数Ｎについて、 Ｎ≦ｎ（ｎ＋１）（ｎ＋２）（ｎ＋３）（ｎ＋４）（ｎ
＋５）／７２０＋ｎ（ｎ＋１）（ｎ＋２）（ｎ＋３）／
２４＋ｎ（ｎ＋１）（ｎ＋２）／３＋５ｎ（ｎ＋１）／
２＋７ｎ＋９ なるｎについて、ゲート・ディレイはｎ＋１１となる。
１０２４ビットの場合にはゲート・ディレイは１８にな
り、２０４８ビットの場合には１９となる。以下、ｎと
Ｎの関係について示す。
＋５）／７２０＋ｎ（ｎ＋１）（ｎ＋２）（ｎ＋３）／
２４＋ｎ（ｎ＋１）（ｎ＋２）／３＋５ｎ（ｎ＋１）／
２＋７ｎ＋９ なるｎについて、ゲート・ディレイはｎ＋１１となる。
１０２４ビットの場合にはゲート・ディレイは１８にな
り、２０４８ビットの場合には１９となる。以下、ｎと
Ｎの関係について示す。
【０１０４】これ以上の段数のキャリー・スキップを実
施することも可能であるが、回路サイズは大きくなり、
現実的ではない。また、１０２４ビットのレベルでは４
段が最高速であるが、回路サイズとパフォーマンスとの
トレード・オフで段数を決定すべきである。
施することも可能であるが、回路サイズは大きくなり、
現実的ではない。また、１０２４ビットのレベルでは４
段が最高速であるが、回路サイズとパフォーマンスとの
トレード・オフで段数を決定すべきである。
【０１０５】理論的考察 一般にビット数をＮとして、キャリー・スキップの深さ
をｘとすると、 Ｎ≦ｎ（ｎ＋１）・・（ｎ＋ｘ）／（（ｘ＋１）！） （１） なるｎを求めて（ｎ＋２ｘ＋１）がゲート・ディレイに
なる。実際にはＮとｎとの関係には次数の低い補正項が
入っているが、本願発明で問題にするような長大なバイ
ナリ・アダーについては第１項が優勢であり、この近似
により式を解くことができる。ｘの値をいろいろ変えて
いくと、ゲート・ディレイを最小にするｘが存在する。
一般的には、Ｎが決まればゲート・ディレイを最小にす
るｘとｎを一義的に決めることができる。この関係は次
のように求めることができる。
をｘとすると、 Ｎ≦ｎ（ｎ＋１）・・（ｎ＋ｘ）／（（ｘ＋１）！） （１） なるｎを求めて（ｎ＋２ｘ＋１）がゲート・ディレイに
なる。実際にはＮとｎとの関係には次数の低い補正項が
入っているが、本願発明で問題にするような長大なバイ
ナリ・アダーについては第１項が優勢であり、この近似
により式を解くことができる。ｘの値をいろいろ変えて
いくと、ゲート・ディレイを最小にするｘが存在する。
一般的には、Ｎが決まればゲート・ディレイを最小にす
るｘとｎを一義的に決めることができる。この関係は次
のように求めることができる。
【０１０６】すなわち、ゲート・ディレイをｄとする
と、ｄ＝ｎ＋２ｘ＋１より， ｎ＝ｄ−２ｘ−１ となる。最適曲線上ではｘをｘ＋１に変更しても、ｄの
値が一定になるところが存在する。これはキャリー・ス
キップをかけた場合のＮとディレイの関係をグラフにし
た場合、２つの曲線が交わるところがある事から分かる
（図５参照）。
と、ｄ＝ｎ＋２ｘ＋１より， ｎ＝ｄ−２ｘ−１ となる。最適曲線上ではｘをｘ＋１に変更しても、ｄの
値が一定になるところが存在する。これはキャリー・ス
キップをかけた場合のＮとディレイの関係をグラフにし
た場合、２つの曲線が交わるところがある事から分かる
（図５参照）。
【０１０７】ｘとｘ＋１の場合、式（１）は、以下のよ
うになる。但し、ｘの時のＮをＮ１、ｘ＋１の時のＮを
Ｎ２とする。
うになる。但し、ｘの時のＮをＮ１、ｘ＋１の時のＮを
Ｎ２とする。
【数１】 先に述べた交点では、Ｎ１とＮ２とは等しいので、
【数２】 となる。数２をｄについて解くと、 ｄ2−（５ｘ＋７）ｄ＋（５ｘ2＋１３ｘ＋８）＝０ これをさらに解くと、以下のようになる。但し、正の値
を解としている。
を解としている。
【数３】 これにより、
【数４】 となる。
【０１０８】これがキャリー・スキップをした時の、キ
ャリー・スキップの深さとその時の最適なｎの関係とな
る。このｎを式（１）に入力して、バイナリ・アダーの
長さＮをＮ＝ｆ（ｘ）とすることができる。以下、ｘ，
ｎ，Ｎの関係について示す。 ｘ ｎ Ｎ ０ ４ ４ １ ６ ２２ ２ ７ ９４ ３ ９ ５６３ ４ １１ ３４８３ ５ １２ １４９５２
ャリー・スキップの深さとその時の最適なｎの関係とな
る。このｎを式（１）に入力して、バイナリ・アダーの
長さＮをＮ＝ｆ（ｘ）とすることができる。以下、ｘ，
ｎ，Ｎの関係について示す。 ｘ ｎ Ｎ ０ ４ ４ １ ６ ２２ ２ ７ ９４ ３ ９ ５６３ ４ １１ ３４８３ ５ １２ １４９５２
【０１０９】このようにして、４ビットまではバイナリ
・アダーはキャリー・スキップなし、８ビット、１６ビ
ットのバイナリ・アダーは１段のキャリー・スキップ
が、３２ビット、６４ビットのバイナリ・アダーには２
段のキャリー・スキップが、１２８ビット、２５６ビッ
トのバイナリ・アダーには３段のキャリー・スキップ
が、１０２４ビット、２０４８ビットのバイナリ・アダ
ーには４段のキャリー・スキップが最速であることがわ
かる。
・アダーはキャリー・スキップなし、８ビット、１６ビ
ットのバイナリ・アダーは１段のキャリー・スキップ
が、３２ビット、６４ビットのバイナリ・アダーには２
段のキャリー・スキップが、１２８ビット、２５６ビッ
トのバイナリ・アダーには３段のキャリー・スキップ
が、１０２４ビット、２０４８ビットのバイナリ・アダ
ーには４段のキャリー・スキップが最速であることがわ
かる。
【０１１０】以上は、アダーについてのみ記載したが、
ワラス・ツリー（Wallace Tree）と上述のキャリー・ス
キップ・アダーを変形したものの組み合わせによりマル
チプライアを作成することも可能である。ワラス・ツリ
ー部分は、出力の項数列を、ある決まったパターンにす
る。また、キャリー・スキップ・アダーは、ワラス・ツ
リーの出力を最小のディレイで加算するもので、このア
ダー自体が３つの部分に分けられる。以下、各部分につ
いて説明する。
ワラス・ツリー（Wallace Tree）と上述のキャリー・ス
キップ・アダーを変形したものの組み合わせによりマル
チプライアを作成することも可能である。ワラス・ツリ
ー部分は、出力の項数列を、ある決まったパターンにす
る。また、キャリー・スキップ・アダーは、ワラス・ツ
リーの出力を最小のディレイで加算するもので、このア
ダー自体が３つの部分に分けられる。以下、各部分につ
いて説明する。
【０１１１】（ａ）ワラス・ツリーの出力項数列 ｎビットのマルチプライアで２つのｎビット入力の最大
値は２n−１なので、これを２つ掛けたものがマルチプ
ライアの取り得る値の最大値となる。この最大値は、 （２n−１）×（２n−１）＝２2n−２n+1＋１ である。これを変形すると、以下のようになる。 ２2n−２n+1＋１＝（２2n-1−１）＋（２2n-1−２n+1−
２）＋４ この計算結果は、以下のように解釈される。すなわち、
第１項は、（２ｎ−１）ビットのすべてのビットが'１'
になったものである。これは図６（ａ）のような状態で
ある。一方、第２項は、ＬＳＢから（ｎ＋２）番目のビ
ットが'０'であり、さらにＬＳＢが０となっている。よ
って、図６（ｂ）のような状態である。第３項は４なの
で、図６（ｃ）のような状態である。これらを加える
と、図６（ｄ）のような項数列が求められる。これが、
本発明における指定の項数列である。以下、この項数列
をＷnと呼ぶ。
値は２n−１なので、これを２つ掛けたものがマルチプ
ライアの取り得る値の最大値となる。この最大値は、 （２n−１）×（２n−１）＝２2n−２n+1＋１ である。これを変形すると、以下のようになる。 ２2n−２n+1＋１＝（２2n-1−１）＋（２2n-1−２n+1−
２）＋４ この計算結果は、以下のように解釈される。すなわち、
第１項は、（２ｎ−１）ビットのすべてのビットが'１'
になったものである。これは図６（ａ）のような状態で
ある。一方、第２項は、ＬＳＢから（ｎ＋２）番目のビ
ットが'０'であり、さらにＬＳＢが０となっている。よ
って、図６（ｂ）のような状態である。第３項は４なの
で、図６（ｃ）のような状態である。これらを加える
と、図６（ｄ）のような項数列が求められる。これが、
本発明における指定の項数列である。以下、この項数列
をＷnと呼ぶ。
【０１１２】マルチプライアを作る時には、まず二進数
である乗数及び被乗数の全てのビット組み合わせに対す
る積項を作成し、位を揃えて並べる。この積項の並べ方
は、１，２，３，４，・・・・ｎ−１，ｎ，ｎ−１，ｎ
−２，・・・・３，２，１というように自然数が単調増
加してｎになった後、単調減少するように並べる。これ
にフル・アダーを作用させていくと、同位になるビット
数は１／３の等比級数で減り、出力と同じ数のキャリー
がＭＳＢ側にひとつずれて現れる。このようにして全体
としてはＭＳＢ側に少しずれながら、積項のシンメトリ
ックな三角山はフル・アダーを介すごとに平に押しつぶ
されるような形で、Ｗnの項数列になる。Ｗnを得るため
にワラス・ツリーを以下のような手順で作成する。
である乗数及び被乗数の全てのビット組み合わせに対す
る積項を作成し、位を揃えて並べる。この積項の並べ方
は、１，２，３，４，・・・・ｎ−１，ｎ，ｎ−１，ｎ
−２，・・・・３，２，１というように自然数が単調増
加してｎになった後、単調減少するように並べる。これ
にフル・アダーを作用させていくと、同位になるビット
数は１／３の等比級数で減り、出力と同じ数のキャリー
がＭＳＢ側にひとつずれて現れる。このようにして全体
としてはＭＳＢ側に少しずれながら、積項のシンメトリ
ックな三角山はフル・アダーを介すごとに平に押しつぶ
されるような形で、Ｗnの項数列になる。Ｗnを得るため
にワラス・ツリーを以下のような手順で作成する。
【０１１３】（１）項数が３、２、１である最下位には
手を付けない。 （２）項数が３以上で３ｘ＋ａ（ａ＝０，１，２）と書
くことができる時、これにｘ個のフル・アダーを接続
し、その桁の項数をｘ＋ａ個に減らし、またその際に発
生したｘ個のキャリーを上位の桁に渡す。 （３）フル・アダーの必要が無くなれば終了し、それ以
外の場合には（２）に戻る。
手を付けない。 （２）項数が３以上で３ｘ＋ａ（ａ＝０，１，２）と書
くことができる時、これにｘ個のフル・アダーを接続
し、その桁の項数をｘ＋ａ個に減らし、またその際に発
生したｘ個のキャリーを上位の桁に渡す。 （３）フル・アダーの必要が無くなれば終了し、それ以
外の場合には（２）に戻る。
【０１１４】（ｂ）アダー部分の分割 このようにして作られたワラス・ツリーの出力Ｗnは、
ＬＳＢからＭＳＢまでを３分割し、それぞれの部分につ
いて別の方式の回路で加算する。第１アダー部分は、Ｌ
ＳＢから２つ目までで、項数は１及び２である。第２ア
ダー部分は、ＬＳＢから３番目の項からｎ＋２番目の項
までで、最上位の項数は１、最下位の項数は３である。
第３アダー部分は、ＬＳＢからｎ＋３番目の項から２ｎ
−１番目項までである。以下、第１乃至第３アダーにつ
いて説明する。
ＬＳＢからＭＳＢまでを３分割し、それぞれの部分につ
いて別の方式の回路で加算する。第１アダー部分は、Ｌ
ＳＢから２つ目までで、項数は１及び２である。第２ア
ダー部分は、ＬＳＢから３番目の項からｎ＋２番目の項
までで、最上位の項数は１、最下位の項数は３である。
第３アダー部分は、ＬＳＢからｎ＋３番目の項から２ｎ
−１番目項までである。以下、第１乃至第３アダーにつ
いて説明する。
【０１１５】（ｂ１）第１アダー 第１アダーのＬＳＢは、項数１だから、そのまま出力す
る。また、第２項は恒数２なので、ハーフ・アダーで加
算して、キャリーを第２アダーに送る。
る。また、第２項は恒数２なので、ハーフ・アダーで加
算して、キャリーを第２アダーに送る。
【０１１６】（ｂ２）第２アダー 先に述べた多重キャリー・スキップ・アダーは、まずキ
ャリーを考慮しないで加算をし、加算が終わった後でキ
ャリーが発生すれば＋１の補正をするという計算をリカ
ーシブに、多重の数だけ繰り返すというものである。項
数が２以下ならば、補正は＋１するか否かなので、＋１
の補正回路（１−インクリメンタ）は１セットあればよ
い。なぜなら、項数２の加算の最大値は加算する２つの
数の全ビット（ｎビット）が'１'になっている場合だ
が、これらを加算した値の最大値は、 （２n−１）＋（２n−１）＋carry＝２n+1−２＋carry となり、これは２n+1より小さいので、最終的なキャリ
ーはたかだか１本しか発生しない。すなわち、ローカル
なリプル・アダーで発生したキャリーと、スキップして
きたキャリーは排他的にしか１にならないことがわか
る。但し、＋１の補正回路を起動する条件だけは多重の
分だけ複雑になる。
ャリーを考慮しないで加算をし、加算が終わった後でキ
ャリーが発生すれば＋１の補正をするという計算をリカ
ーシブに、多重の数だけ繰り返すというものである。項
数が２以下ならば、補正は＋１するか否かなので、＋１
の補正回路（１−インクリメンタ）は１セットあればよ
い。なぜなら、項数２の加算の最大値は加算する２つの
数の全ビット（ｎビット）が'１'になっている場合だ
が、これらを加算した値の最大値は、 （２n−１）＋（２n−１）＋carry＝２n+1−２＋carry となり、これは２n+1より小さいので、最終的なキャリ
ーはたかだか１本しか発生しない。すなわち、ローカル
なリプル・アダーで発生したキャリーと、スキップして
きたキャリーは排他的にしか１にならないことがわか
る。但し、＋１の補正回路を起動する条件だけは多重の
分だけ複雑になる。
【０１１７】この第２アダーの場合、最下位が項数３な
ので、最大値を計算してみると、 (２n−１)＋(２n−１)＋carry1＋carry2＝２n+1−２＋c
arry1＋carry2 となり、ローカルなリプル・アダーで発生したキャリー
に加えてスキップしてきたキャリーも'１'になる可能性
がある。すなわち、２つのキャリーは独立して発生す
る。このためアダーのブロックの切れ目では２つのキャ
リーはＯＲ条件でなく、本当に加算する必要がある。具
体的には、リプル・アダーのブロックの最上位で、自分
が発したキャリーと、下位からスキップしてきたキャリ
ーと、次段のアダーのＬＳＢとをフル・アダーで加算
し、このフル・アダーのキャリーで＋１の補正回路を起
動する。このためリプル・アダーのブロック間でのディ
レイの成長は２になる。
ので、最大値を計算してみると、 (２n−１)＋(２n−１)＋carry1＋carry2＝２n+1−２＋c
arry1＋carry2 となり、ローカルなリプル・アダーで発生したキャリー
に加えてスキップしてきたキャリーも'１'になる可能性
がある。すなわち、２つのキャリーは独立して発生す
る。このためアダーのブロックの切れ目では２つのキャ
リーはＯＲ条件でなく、本当に加算する必要がある。具
体的には、リプル・アダーのブロックの最上位で、自分
が発したキャリーと、下位からスキップしてきたキャリ
ーと、次段のアダーのＬＳＢとをフル・アダーで加算
し、このフル・アダーのキャリーで＋１の補正回路を起
動する。このためリプル・アダーのブロック間でのディ
レイの成長は２になる。
【０１１８】この補正回路を説明するために、第１アダ
ーと第２アダーの最初のリプル・アダーのブロックを図
７に示す。第１アダー部分は、最下位項のライン７３４
と、ハーフ・アダーであるＡＮＤ回路７０２及び排他的
論理和回路７００とで構成される。このハーブ・アダー
のキャリーが第２アダーの最初のリプル・アダーに伝搬
される。第２アダーのＬＳＢは項数３であり、このワラ
ス・ツリーからの入力が、フル・アダー７０４に接続さ
れる。このフル・アダー７０４の出力と、第１アダーの
ハーフ・アダーのキャリーとは排他的論理和回路７２０
に入力され、この排他的論理和回路７２０の出力が第３
ビットの出力となる。第２アダーの次の入力は項数２で
あり、この入力は、フル・アダー７０４のキャリーと共
に、フル・アダー７０６に入力される。フル・アダー７
０４の出力と第１アダーのハーフ・アダーの出力はＡＮ
Ｄ回路７１４に入力され、このＡＮＤ回路７１４の出力
と、このフル・アダー７０６の出力は排他的論理和回路
７２２に入力される。この排他的論理和回路７２２の出
力が、第４ビットの出力になる。第２アダーの第３項目
の入力は項数２であり、この入力及びフル・アダー７０
６のキャリーがフル・アダー７０８に入力される。フル
・アダー７０４とフル・アダー７０６の出力はＡＮＤ回
路７１０に入力され、このＡＮＤ回路７１０の出力及び
第１アダーのハーフ・アダーのキャリーとはＡＮＤ回路
７１６に入力される。このＡＮＤ回路７１６の出力は、
フル・アダー７０８の出力と共に排他的論理和回路７２
４に入力され、この排他的論理和回路７２４の出力が第
５ビットの出力になる。さらに、ＡＮＤ回路７１０の出
力とフル・アダー７０８の出力はＡＮＤ回路７１２に入
力される。このＡＮＤ回路７１２の出力は、第１アダー
のハーフ・アダーのキャリーと共にＡＮＤ回路７１８に
入力される。
ーと第２アダーの最初のリプル・アダーのブロックを図
７に示す。第１アダー部分は、最下位項のライン７３４
と、ハーフ・アダーであるＡＮＤ回路７０２及び排他的
論理和回路７００とで構成される。このハーブ・アダー
のキャリーが第２アダーの最初のリプル・アダーに伝搬
される。第２アダーのＬＳＢは項数３であり、このワラ
ス・ツリーからの入力が、フル・アダー７０４に接続さ
れる。このフル・アダー７０４の出力と、第１アダーの
ハーフ・アダーのキャリーとは排他的論理和回路７２０
に入力され、この排他的論理和回路７２０の出力が第３
ビットの出力となる。第２アダーの次の入力は項数２で
あり、この入力は、フル・アダー７０４のキャリーと共
に、フル・アダー７０６に入力される。フル・アダー７
０４の出力と第１アダーのハーフ・アダーの出力はＡＮ
Ｄ回路７１４に入力され、このＡＮＤ回路７１４の出力
と、このフル・アダー７０６の出力は排他的論理和回路
７２２に入力される。この排他的論理和回路７２２の出
力が、第４ビットの出力になる。第２アダーの第３項目
の入力は項数２であり、この入力及びフル・アダー７０
６のキャリーがフル・アダー７０８に入力される。フル
・アダー７０４とフル・アダー７０６の出力はＡＮＤ回
路７１０に入力され、このＡＮＤ回路７１０の出力及び
第１アダーのハーフ・アダーのキャリーとはＡＮＤ回路
７１６に入力される。このＡＮＤ回路７１６の出力は、
フル・アダー７０８の出力と共に排他的論理和回路７２
４に入力され、この排他的論理和回路７２４の出力が第
５ビットの出力になる。さらに、ＡＮＤ回路７１０の出
力とフル・アダー７０８の出力はＡＮＤ回路７１２に入
力される。このＡＮＤ回路７１２の出力は、第１アダー
のハーフ・アダーのキャリーと共にＡＮＤ回路７１８に
入力される。
【０１１９】一方、第２アダーの４項目の入力は項数２
であり、リプル・アダーの第２のブロックであるので、
前のフル・アダーからのキャリーは存在しない。よっ
て、この第２アダーの４項目の入力はハーフ・アダー７
２８に入力される。このハーフ・アダー７２８の出力
は、フル・アダー７０８のキャリーとＡＮＤ回路７１８
の出力と共に、フル・アダー７２６に出力される。この
フル・アダー７２６の出力が第６ビットの出力となり、
キャリーがこのリプル・アダーの第２のブロックに伝搬
される。第２アダーの５項目の入力は項数２であり、ハ
ーフ・アダー７２８のキャリーと共にフル・アダー７３
０に入力される。このフル・アダー７３０の出力とフル
・アダー７２６のキャリーとは、排他的論理和回路７３
２に入力され、この回路７３２の出力が第７ビットの出
力となる。このように、次のリプル・アダーのブロック
に伝搬されるキャリーは、フル・アダー７２６で生成さ
れる。
であり、リプル・アダーの第２のブロックであるので、
前のフル・アダーからのキャリーは存在しない。よっ
て、この第２アダーの４項目の入力はハーフ・アダー７
２８に入力される。このハーフ・アダー７２８の出力
は、フル・アダー７０８のキャリーとＡＮＤ回路７１８
の出力と共に、フル・アダー７２６に出力される。この
フル・アダー７２６の出力が第６ビットの出力となり、
キャリーがこのリプル・アダーの第２のブロックに伝搬
される。第２アダーの５項目の入力は項数２であり、ハ
ーフ・アダー７２８のキャリーと共にフル・アダー７３
０に入力される。このフル・アダー７３０の出力とフル
・アダー７２６のキャリーとは、排他的論理和回路７３
２に入力され、この回路７３２の出力が第７ビットの出
力となる。このように、次のリプル・アダーのブロック
に伝搬されるキャリーは、フル・アダー７２６で生成さ
れる。
【０１２０】先に述べたように、リプル・アダーのブロ
ック間でディレイが２発生するため、それに合わせて次
のブロックのリプル・アダーのディレイは前段より２づ
つ多くなるように構成される。２キャリー・１スキップ
・アダーであれば、リプル・アダーのブロック・サイズ
は、次のようになる。 ２，２，４，６，８，１０，１２．．．． ２キャリー・２スキップ・アダーであれば、 ２，２ ２，２，３，４ ２，２，３，４，５，６ ２，２，３，４，５，６，７，８ というようになる。なお、２キャリー・多スキップ・ア
ダーの場合、一番外側のスキップについてはフル・アダ
ーによって生成されたキャリーを次段のリプル・キャリ
ーに伝搬するが、その他の内側のスキップについては、
最初に述べた例と同じで、キャリーはＯＲ回路を含む回
路（Ｃ２＝Ｃ１＋Ｆ１・Ｃ０などで表される回路）にて
作成される。
ック間でディレイが２発生するため、それに合わせて次
のブロックのリプル・アダーのディレイは前段より２づ
つ多くなるように構成される。２キャリー・１スキップ
・アダーであれば、リプル・アダーのブロック・サイズ
は、次のようになる。 ２，２，４，６，８，１０，１２．．．． ２キャリー・２スキップ・アダーであれば、 ２，２ ２，２，３，４ ２，２，３，４，５，６ ２，２，３，４，５，６，７，８ というようになる。なお、２キャリー・多スキップ・ア
ダーの場合、一番外側のスキップについてはフル・アダ
ーによって生成されたキャリーを次段のリプル・キャリ
ーに伝搬するが、その他の内側のスキップについては、
最初に述べた例と同じで、キャリーはＯＲ回路を含む回
路（Ｃ２＝Ｃ１＋Ｆ１・Ｃ０などで表される回路）にて
作成される。
【０１２１】（ｂ３）第３アダー この第２アダーの最上位ビットの入力は項数１であった
ので、第３アダーは最初に説明した１キャリー・多重ス
キップ・アダーで問題ない。
ので、第３アダーは最初に説明した１キャリー・多重ス
キップ・アダーで問題ない。
【０１２２】以上のようにすると、ワラス・ツリーの入
力のＬＳＢから入力項数が増加していって、ワラス・ツ
リーによるディレイが多くなってしまう部分は第１及び
第２アダーで、ワラス・ツリーの入力の項数が減少して
いって、ワラス・ツリーによるディレイが減少する部分
は、よりディレイの少ない第３アダーにより対応するこ
とにより、より高速なマルチプライアが構成される。お
おまかなマルチプライアの構成を図８に示す。
力のＬＳＢから入力項数が増加していって、ワラス・ツ
リーによるディレイが多くなってしまう部分は第１及び
第２アダーで、ワラス・ツリーの入力の項数が減少して
いって、ワラス・ツリーによるディレイが減少する部分
は、よりディレイの少ない第３アダーにより対応するこ
とにより、より高速なマルチプライアが構成される。お
おまかなマルチプライアの構成を図８に示す。
【０１２３】
【効果】スキップするキャリーを２段以上にし、より高
速な動作速度を可能とするバイナリ・アダーを提供する
ことができた。
速な動作速度を可能とするバイナリ・アダーを提供する
ことができた。
【０１２４】高速なマルチプライアも提供することがで
きた。
きた。
【図１】２段のキャリー・スキップの回路図である。
【図２】２段のキャリー・スキップの回路図である。
【図３】３段のキャリー・スキップの回路図である。
【図４】３段のキャリー・スキップの回路図である。
【図５】ゲート・ディレイとビット数の関係を示した図
である。
である。
【図６】ワラス・ツリーの出力項数を説明するための図
である。
である。
【図７】本発明のマルチプライア中の第１アダー及び第
２アダーの下位の部分を示す回路図である。
２アダーの下位の部分を示す回路図である。
【図８】本発明のマルチプライアのブロック図である。
１ フル・アダー ７ ハーフ・アダー
───────────────────────────────────────────────────── フロントページの続き (72)発明者 佐藤 証 神奈川県大和市下鶴間1623番地14 日本ア イ・ビー・エム株式会社 東京基礎研究所 内 (72)発明者 宗藤 誠治 神奈川県大和市下鶴間1623番地14 日本ア イ・ビー・エム株式会社 東京基礎研究所 内
Claims (12)
- 【請求項１】複数のリプル・アダーを有するＮ段（Ｎは
３以上の整数）キャリー・スキップ・アダーであって、 前記複数のリプル・アダーのうち少なくとも一部のリプ
ル・アダーはグループ分けされており、 キャリー信号はあるグループから１つ上位のグループへ
伝達されており、 前記グループ内に複数のリプル・アダーが存在する場合
には、当該グループ内のリプル・アダー間でもキャリー
信号が伝達されており、 前記あるグループから前記１つ上位のグループへのキャ
リー信号Ｃ１と、前記１つ上位のグループ内の全アダー
の出力が１であるか否かを表す信号Ｆと、前記１つ上位
のグループ内において最も上位のリプル・アダーに関連
するキャリー信号Ｃ２とを用いて、Ｃ＝Ｃ２＋Ｆ・Ｃ１
を計算する回路を有し、 前記グループ内に３以上のリプル・アダーが存在する場
合には、当該グループ内の複数のリプル・アダーはＮ−
２段階のレベルでさらにグループ化されており、 前記最も上位のリプル・アダーが属する、最下段である
レベル１のグループ内におけるリプル・アダー間で前記
最も上位のリプル・アダーに伝達されてきたキャリー信
号Ｃ３0と、前記最も上位のリプル・アダーが属する、
レベルｎのグループに、前記レベルｎの隣接するグルー
プから伝達されてきたキャリー信号Ｃ３ n（１≦ｎ≦Ｎ
−２）と、前記最も上位のリプル・アダーのキャリー信
号Ｃ４と、前記最も上位のリプル・アダーの全アダーの
出力が１であるか否かを表す信号Ｆ２0と、前記キャリ
ー信号Ｃ３nを出力している回路に関連するリプル・ア
ダーより上位で前記最も上位のリプル・アダーまでの全
アダーの出力が１であるか否かを表す信号Ｆ２nとを用
いて、 Ｃ２1＝Ｃ４＋Ｆ２0・Ｃ３0を計算する回路と、 Ｃ２n+1＝Ｃ２n＋Ｆ２n・Ｃ３n（１≦ｎ≦Ｎ−２，Ｃ２
N-1＝Ｃ２）を計算する回路と、 を有するＮ段キャリー・スキップ・アダー。 - 【請求項２】前記１つ上位のグループに属するリプル・
アダーの数は、前記あるグループに属するリプル・アダ
ーの数以上であることを特徴とする請求項１記載のキャ
リー・スキップ・アダー。 - 【請求項３】複数のリプル・アダーを有し、 前記複数のリプル・アダーのうち少なくとも一部のリプ
ル・アダーはグループ分けされており、 キャリー信号はあるグループから１つ上位のグループへ
伝達されており、 前記あるグループから前記１つ上位のグループへのキャ
リー信号Ｃ１と、前記１つ上位のグループ内の全アダー
の出力が１であるか否かを表す信号Ｆと、前記１つ上位
のグループ内において最も上位のリプル・アダーに関連
するキャリー信号Ｃ２とを用いて、Ｃ＝Ｃ２＋Ｆ・Ｃ１
を計算する回路を有し、 前記グループ内に複数のリプル・アダーが存在する場合
には、当該グループ内の複数のリプル・アダー間でもキ
ャリー信号が伝達されており、前記最も上位のリプル・
アダーより１つ下位のリプル・アダーに関連するキャリ
ー信号Ｃ３1と、前記最も上位のリプル・アダーのキャ
リー信号Ｃ４と、前記最も上位のリプル・アダーの全ア
ダーの出力が１であるか否かを表す信号Ｆ２1とを用い
て、 Ｃ２＝Ｃ４＋Ｆ２1・Ｃ３1を計算する回路と、 を有するキャリー・スキップ・アダー。 - 【請求項４】前記１つ上位のグループよりさらに１つ上
位のグループ中の最下位のリプル・アダー内において最
下位アダーの出力Ｓ０と前記Ｃとの排他的論理和を計算
する回路と、 前記最下位アダーより１つ上位のアダーの出力Ｓ１と、
前記Ｃ及び前記Ｓ０の論理積との排他的論理和を計算す
る回路と、 をさらに有する、請求項３記載のキャリー・スキップ・
アダー。 - 【請求項５】複数のリプル・アダーを有し、 前記複数のリプル・アダーのうち少なくとも一部のリプ
ル・アダーに含まれる第１リプル・アダーについて、 前記第１リプル・アダーのキャリー信号Ｃ１と、前記第
１リプル・アダー内の全ての出力が１になっているか否
かを示す信号Ｆ１と、前記第１リプル・アダーより１つ
下位のリプル・アダーに関連するキャリー信号Ｃ０が伝
達されている場合には当該キャリー信号Ｃ０とに対し
て、 Ｃ２＝Ｃ１＋Ｆ１・Ｃ０なる計算を実行する回路を有
し、 前記第１リプル・アダーから２以上下位のリプル・アダ
ーである第２リプル・アダーに関連する回路から前記第
１リプル・アダーに当該第２リプル・アダーに関連する
キャリー信号Ｃが伝達される場合には、各前記第１リプ
ル・アダー及び各キャリー信号Ｃについて、 前記第２リプル・アダーより上位で前記第１リプル・ア
ダーまでの全ての出力が１になっているか否かを示す信
号Ｆ２と、前記第１リプル・アダーに関連するキャリー
信号Ｃ２'と前記キャリー信号Ｃに対して、 Ｃ３＝Ｃ２'＋Ｆ２・Ｃなる計算を実行する回路をさら
に有するキャリー・スキップ・アダー。 - 【請求項６】前記第１リプル・アダーに関連して前記Ｃ
３が出力される場合には、 前記第１リプル・アダーから１つ上位の第３リプル・ア
ダー中最下位アダーの出力Ｓ０と前記Ｃ３との排他的論
理和を計算する回路と、 前記最下位アダーより１つ上位のアダーの出力Ｓ１と、
前記Ｃ３及び前記Ｓ０の論理積との排他的論理和を計算
する回路と、 をさらに有し、 前記第１リプル・アダーに関連して前記Ｃ３が出力され
ない場合には、 前記第３リプル・アダー中最下位アダーの出力Ｓ０と前
記Ｃ２との排他的論理和を計算する回路と、 前記最下位アダーより１つ上位のアダーの出力Ｓ１と、
前記Ｃ２及び前記Ｓ０の論理積との排他的論理和を計算
する回路と、 をさらに有する、請求項５記載のキャリー・スキップ・
アダー。 - 【請求項７】前記第３リプル・アダーが３以上のアダー
から構成される場合には、 前記最下位アダーよりｍ（ｍ≧３）上位のアダーの出力
Ｓｍと、前記Ｃ３及び前記最下位アダーから前記最下位
アダーよりｍ−１上位のアダーまでの全出力の論理積と
の排他的論理和を計算する回路をさらに有する、請求項
６記載のキャリー・スキップ・アダー。 - 【請求項８】複数のリプル・アダーを有し、 前記複数のリプル・アダーのうち少なくとも一部のリプ
ル・アダーはグループ分けされており、 キャリー信号はあるグループから１つ上位のグループへ
伝達されており、 前記あるグループから前記１つ上位のグループへのキャ
リー信号Ｃ１と、前記１つ上位のグループ内の全アダー
の出力が１であるか否かを表す信号Ｆと、前記１つ上位
のグループ内において最も上位のリプル・アダーに関連
するキャリー信号Ｃ２とを用いて、Ｃ＝Ｃ２＋Ｆ・Ｃ１
を計算する回路を有し、 ２以上のリプル・アダーを有するグループにおいては、
当該グループ内の複数のリプル・アダーがさらに複数の
サブグループに分けられ、キャリー信号はあるサブグル
ープから１つ上位のサブグループへ伝達されており、 前記あるサブグループから前記１つ上位のサブグループ
へのキャリー信号Ｃ３と、前記１つ上位のサブグループ
内の全てのアダーの出力が１であるか否かを表す信号Ｆ
１と、前記１つ上位のサブグループ内において最も上位
のリプル・アダーに関連するキャリー信号Ｃ４とを用い
て、Ｃ５＝Ｃ４＋Ｆ１・Ｃ３を計算する回路を有するキ
ャリー・スキップ・アダー。 - 【請求項９】下位から、３ビットの第１グループ、２ビ
ットの第２グループ、２ビットのセットと２ビットのセ
ットからなる第３グループ、第４グループ以降はグルー
プ番号ｎ−１個のセットを含み（ｎは４以上の整数）、
当該グループ内で第１及び第２のセットは２ビット、第
３のセット以降はセット番号ｍビットとなるように分け
られた（ｍは３以上の整数）、２つのＮビットの入力
と、各々前記２つのＮビットの入力のうち同じビット位
置の２つの入力に接続された、Ｎ個のアダーと、 前記第１及び第２グループと各前記セット内で、ある前
記アダーから次の前記アダーへ、リプル・キャリーを直
接伝達するラインと、 前記第３グループ以降の各グループ内で、ある前記セッ
トから次の前記セットへキャリーを伝達するラインと、 前記第２グループ以降の各グループ内で、前の前記グル
ープからキャリーを伝達するラインと、 伝達されるキャリーと前記アダーの出力とを用いて、加
算結果を補正する回路と、 を有する二段キャリー・スキップ・アダー。 - 【請求項１０】下位から、３ビットの第１クラス、２ビ
ットの第２クラス、２つの２ビットのグループからなる
第３クラス、２つの２ビットのセットからなる第１のグ
ループと２つの２ビットのセットからなる第２のグルー
プとからなる第４クラス、２つの２ビットのセットから
なる第１のグループと２つの２ビットのセットからなる
第２のグループと２つの２ビットのセットと３ビットの
セットを含む第３のグループとからなる第５クラス、第
６クラス以降は、クラス番号ｎ−２個のグループを有
し、第１乃至第３のグループは前記第５クラスと同じ
で、第４のグループ以降は、グループ番号ｇ個のセット
を有し、前記第４のグループ以降の各グループ内では、
２ビットの第１セット、第２セット以降は、セット番号
ｓビットのセットを含むように分けられた、２つのＮビ
ットの入力と、 各々前記２つのＮビットの入力のうち同じビット位置の
２つの入力に接続された、Ｎ個のアダーと、 前記第１及び第２クラスと前記第３クラスの各グループ
内と各前記セット内で、ある前記アダーから次の前記ア
ダーへ、リプル・キャリーを直接伝達するラインと、 前記第３クラス以降の各グループ内で、ある前記セット
から次の前記セットへキャリーを伝達するラインと、 前記第４クラス以降の各クラス内で、ある前記グループ
から次の前記グループへキャリーを伝達するラインと、 前記第２クラス以降の各クラスで、前の前記クラスから
キャリーを伝達するラインと、 伝達されるキャリーと前記アダーの出力とを用いて、加
算結果を補正する回路と、 を有する三段キャリー・スキップ・アダー。 - 【請求項１１】下位から、３ビットの第１ブロック、２
ビットの第２ブロック、２ビットのセット２つからなる
第３ブロック、２ビットのセット２つからなるグループ
と２ビットのセット２つからなるグループとからなるク
ラスと、当該クラスの構成と同じ構成のクラスとからな
る第４ブロック、第５ブロック以降は、ブロック番号ｂ
−２個のクラスを有し、ｂ−３番目のクラスまでは前の
ブロックと同様の構成を有しており、ｂ−２番目のクラ
スの構成は、ｂ−２個のグループを有し、第１グループ
は２ビットのセット２つ、第２グループは２ビットのセ
ット２つ、第３グループ以降はグループ番号ｇ個のセッ
トを有し、２ビットの第１セットと第２セット以降は当
該セット番号ｓビットからなるセットとを有するように
分割された、２つのＮビットの入力と、 各々前記２つのＮビットの入力のうち同じビット位置の
２つの入力に接続された、Ｎ個のアダーと、 前記第１及び第２ブロックと前記第３ブロック以降の各
セット内で、ある前記アダーから次の前記アダーへ、リ
プル・キャリーを直接伝達するラインと、 前記第３ブロック内及び前記第４ブロック以降の各グル
ープ内で、ある前記セットから次の前記セットへキャリ
ーを伝達するラインと、 前記第４ブロック以降の各クラス内で、ある前記グルー
プから次の前記グループへキャリーを伝達するライン
と、 前記第４ブロック以降の各ブロック内で、ある前記クラ
スから次の前記クラスへキャリーを伝達するラインと、 前記第２ブロック以降の各ブロック内で、前のブロック
からキャリーを伝達するラインと、 伝達されるキャリーと前記アダーの出力とを用いて、加
算結果を補正する回路と、 を有する四段キャリー・スキップ・アダー。 - 【請求項１２】複数のリプル・アダーを有し、 最下位のアダーの入力が３ビットである、少なくとも一
部のリプル・アダーについて、 前記最下位のアダーを含むリプル・アダーのキャリー信
号Ｃ１と、当該リプル・アダー内の全ての出力が１にな
っているか否かを示す信号Ｆ１と、前記最下位のアダー
より１つ下位のアダーに関連するキャリー信号Ｃ０が伝
達されている場合には当該キャリー信号Ｃ０と、当該リ
プル・アダーの１つ上位のリプル・アダーの最下位の出
力Ｆ２とに対して、 実質的にＦ１・Ｃ０とＣ１とＦ２を加算する回路を有す
ることを特徴とするキャリー・スキップ・アダー。
Priority Applications (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP10091837A JPH11143685A (ja) | 1997-06-24 | 1998-04-03 | キャリー・スキップ・アダー |
| US09/102,532 US6199091B1 (en) | 1997-06-24 | 1998-06-22 | Carry skip adder |
| US09/699,976 US6735612B1 (en) | 1997-06-24 | 2000-10-30 | Carry skip adder |
Applications Claiming Priority (5)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP16729297 | 1997-06-24 | ||
| JP9-167292 | 1997-09-08 | ||
| JP24309197 | 1997-09-08 | ||
| JP9-243091 | 1997-09-08 | ||
| JP10091837A JPH11143685A (ja) | 1997-06-24 | 1998-04-03 | キャリー・スキップ・アダー |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH11143685A true JPH11143685A (ja) | 1999-05-28 |
Family
ID=27306855
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP10091837A Pending JPH11143685A (ja) | 1997-06-24 | 1998-04-03 | キャリー・スキップ・アダー |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US6199091B1 (ja) |
| JP (1) | JPH11143685A (ja) |
Families Citing this family (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6584484B1 (en) * | 2000-05-11 | 2003-06-24 | Agere Systems Inc. | Incorporation of split-adder logic within a carry-skip adder without additional propagation delay |
| US7007059B1 (en) * | 2001-07-30 | 2006-02-28 | Cypress Semiconductor Corporation | Fast pipelined adder/subtractor using increment/decrement function with reduced register utilization |
| DE10201449C1 (de) * | 2002-01-16 | 2003-08-14 | Infineon Technologies Ag | Rechenwerk, Verfahren zum Ausführen einer Operation mit einem verschlüsselten Operanden, Carry-Select-Addierer und Kryptographieprozessor |
| DE10215785A1 (de) * | 2002-04-10 | 2003-10-30 | Infineon Technologies Ag | Rechenwerk und Verfahren zum Addieren |
| DE10215784A1 (de) * | 2002-04-10 | 2003-10-30 | Infineon Technologies Ag | Rechenwerk und Verfahren zum Subtrahieren |
| JP3540807B2 (ja) * | 2002-08-27 | 2004-07-07 | 沖電気工業株式会社 | 加算器，乗算器，及び集積回路 |
| US7516173B2 (en) * | 2004-08-04 | 2009-04-07 | Intel Corporation | Carry-skip adder having merged carry-skip cells with sum cells |
| CN103631560B (zh) * | 2013-12-06 | 2016-10-05 | 重庆邮电大学 | 基于可逆逻辑的4位阵列乘法器 |
| US20220244912A1 (en) * | 2021-02-02 | 2022-08-04 | Efinix, Inc. | Dynamic block size carry-skip adder construction on fpgas by combining ripple carry adders with routable propagate/generate signals |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5166899A (en) | 1990-07-18 | 1992-11-24 | Hewlett-Packard Company | Lookahead adder |
| US5337269A (en) * | 1993-03-05 | 1994-08-09 | Cyrix Corporation | Carry skip adder with independent carry-in and carry skip paths |
| KR950004225B1 (ko) * | 1993-04-16 | 1995-04-27 | 현대전자산업주식회사 | 고속 캐리 증가 가산기 |
| US5539332A (en) | 1994-10-31 | 1996-07-23 | International Business Machines Corporation | Adder circuits and magnitude comparator |
| KR100197354B1 (ko) * | 1995-06-28 | 1999-06-15 | 김영환 | 클럭 위상을 이용한 캐리증가 가산기 |
-
1998
- 1998-04-03 JP JP10091837A patent/JPH11143685A/ja active Pending
- 1998-06-22 US US09/102,532 patent/US6199091B1/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| US6199091B1 (en) | 2001-03-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| KR920007029B1 (ko) | X×y 비트 배열 배율기/어큐뮬레이터 회로 | |
| JPH11143685A (ja) | キャリー・スキップ・アダー | |
| US5231415A (en) | Booth's multiplying circuit | |
| US5477480A (en) | Carry look ahead addition method and carry look ahead addition device | |
| JPH07191832A (ja) | ２進数２乗回路 | |
| JPH0713741A (ja) | アルファ合成演算器 | |
| JPH10307706A (ja) | 半及び全加算器を用いたウォレスツリー乗算器 | |
| US4348736A (en) | Programmable logic array adder | |
| KR950005522B1 (ko) | 룩어헤드 가산기의 캐리 발생기 | |
| US5113362A (en) | Integrated interpolator and method of operation | |
| JPH082014B2 (ja) | 多段デジタル・フィルタ | |
| JP2803601B2 (ja) | 有限体元の反転回路 | |
| JPH06236255A (ja) | 並列桁上げ発生ネットワーク、並列加算器ネットワーク、桁上げ発生モジュール、マルチビット加算器ネットワークおよびモジュラー桁上げ伝ぱんユニット | |
| US6735612B1 (en) | Carry skip adder | |
| JPH0326114A (ja) | 乗算剰余演算器 | |
| JP2606326B2 (ja) | 乗算器 | |
| JP2991788B2 (ja) | 復号器 | |
| JP3255251B2 (ja) | 配列型桁上げ保存加算器を有する乗算器 | |
| JP2606339B2 (ja) | 乗算器 | |
| US7111034B2 (en) | Carry foreknowledge adder | |
| JPH1011267A (ja) | 乗算器 | |
| JP2699358B2 (ja) | デコーダ回路 | |
| SU1083185A1 (ru) | Матричный вычислитель | |
| JP2633165B2 (ja) | 分散算術を用いる演算装置 | |
| JPH0199325A (ja) | エンコーダ回路 |