(57)【特許請求の範囲】
【請求項１】
複数ビットからなる２進数値Ａ、Ｂを同様に下位から１以上の任意のビット数でｎ（ｎはｎ≧２の正の整数）分割した各々の値をＡ（１），Ａ（２）、・・・、Ａ（ｎ）および、Ｂ（１），Ｂ（２），・・・，Ｂ（ｎ）とし、分割された各ビットの桁毎に下位桁値から加算を実施する際に、Ａ、Ｂ各々の下位桁値の演算結果から生成される第（ｎ−ｍ）（ｍはｎ＞ｍ≧０の正の整数）の桁上げ信号ＣＯ（ｎ−ｍ）と、Ａ、Ｂ各々の当該加算桁値の第（ｎ−ｍ＋１）の演算結果とから、上位桁の第（ｎ−ｍ＋２）の演算部への第（ｎ−ｍ＋１）の桁上げ信号ＣＯ（ｎ−ｍ＋１）を出力する回路であって、
数値Ａ、Ｂ各々の下位桁の各値を演算して桁上げ信号ＣＯ（ｎ−ｍ）を出力する第（ｎ−ｍ）の桁上げ部と、
数値Ａ、Ｂ各々の当該加算桁の各値のＯＲ出力値が全て１であることを検出する第（ｎ−ｍ＋１）の全１検出部と、
前記第（ｎ−ｍ）の桁上げ部と、前記第（ｎ−ｍ＋１）の全１検出部との双方から入力があった時に、上位桁の各値を演算する第（ｎ−ｍ＋２）の演算部への第１の仮桁上げ信号ＩＣＯ１（ｎ−ｍ＋１）を出力する第（ｎ−ｍ＋１）のＡＮＤ出力部と、
数値Ａ、Ｂ各々の当該加算桁の各値を演算して、上位桁の第（ｎ−ｍ＋２）の演算部への第２の仮桁上げ信号ＩＣＯ２（ｎ−ｍ＋１）を出力する第（ｎ−ｍ＋１）の桁上げ部と、
前記第１の仮桁上げ信号ＩＣＯ１（ｎ−ｍ＋１）と、前記第２の仮桁上げ信号ＩＣＯ２（ｎ−ｍ＋１）との少なくとも何れかが入力された時に、上位桁の第（ｎ−ｍ＋２）の演算部への桁上げ信号ＣＯ（ｎ−ｍ＋１）を出力する第（ｎ−ｍ＋１）のＯＲ出力部と
を有することを特徴とする２進数加算時の桁上げ出力回路。
【請求項２】
前記第（ｎ−ｍ＋１）の全１検出部、前記第（ｎ−ｍ＋１）の桁上げ部、および、前記第（ｎ−ｍ＋１）のＡＮＤ出力部は、連続する桁値に対応して複数個が設けられ、
前記複数の各ＡＮＤ出力部には、前記当該桁中の下位となる全ての全１検出部と当該桁上げ部からの出力が入力され、ＯＲ出力部には、前記複数の全ＡＮＤ出力部からの出力が入力される
ことを特徴とする請求項１記載の桁上げ出力回路。
【請求項３】
前記上位桁の第（ｎ−ｍ＋２）の演算部は、
数値Ａ、Ｂ各々の上位桁のＯＲ出力値が全て１であることを検出する第（ｎ−ｍ＋２）の全１検出部と、
前記第（ｎ−ｍ＋１）のＯＲ出力部と、前記第（ｎ−ｍ＋２）の全１検出部との双方から入力があった時に、さらに上位桁の第（ｎ−ｍ＋３）の演算部への第１の仮桁上げ信号ＩＣＯ１（ｎ−ｍ＋２）を出力する第（ｎ−ｍ＋２）のＡＮＤ出力部と、
数値Ａ、Ｂ各々の前記上位桁の各値を演算し、さらに上位桁の第（ｎ−ｍ＋３）の演算部への第２の仮桁上げ信号ＩＣＯ２（ｎ−ｍ＋２）を出力する第（ｎ−ｍ＋２）の桁上げ部と、
前記第１の仮桁上げ信号ＩＣＯ１（ｎ−ｍ＋２）と、前記第２の仮桁上げ信号ＩＣＯ２（ｎ−ｍ＋２）との少なくとも何れかが入力された時に、さらに上位桁の第（ｎ−ｍ＋３）の演算部への桁上げ信号ＣＯ（ｎ−ｍ＋２）を出力する第（ｎ−ｍ＋２）のＯＲ出力部と
を有することを特徴とする請求項１または２に記載の桁上げ出力回路。
【請求項４】
前記第（ｎ−ｍ＋２）の全１検出部および前記第（ｎ−ｍ＋２）の桁上げ部は、前記第（ｎ−ｍ）の桁上げ部、前記第（ｎ−ｍ＋１）の全１検出部および前記第（ｎ−ｍ＋１）の桁上げ部と並列に配置され、
前記第（ｎ−ｍ＋２）のＡＮＤ出力部および前記第（ｎ−ｍ＋２）のＯＲ出力部は、前記第（ｎ−ｍ＋１）のＡＮＤ出力部および前記第（ｎ−ｍ＋１）のＯＲ出力部と直列に配置される
ことを特徴とする請求項３に記載の桁上げ出力回路。
【請求項５】
分割使用が可能となるように切り替え用のＡＮＤ回路を、前記第（ｎ−ｍ＋１）のＯＲ出力部の出力段、および、前記第（ｎ−ｍ＋２）の全１検出部内に各々設けることを特徴とする請求項４に記載の桁上げ出力回路。
【請求項６】
加算される２進数値Ａ、Ｂを分割した各値毎の遅延時間を予め検出しておき、
遅延時間が少ない各値については、前記下位桁のＡＮＤ出力部あるいはＯＲ出力部に入力されるように接続し、
遅延時間が多い各値については、前記上位桁のＡＮＤ出力部あるいはＯＲ出力部に入力されるように接続することを特徴とする請求項４又は５に記載の桁上げ出力回路。
【請求項７】
前記各桁上げ信号を生成するために、前記ＡＮＤ出力部および前記ＯＲ出力部がツリー形状に組み合わされることを特徴とする請求項１〜４の何れかに記載の桁上げ出力回路。
【請求項８】
前記各桁上げ信号を生成する各桁上げ出力回路は、階層的に構成され、且つ、
下位の桁上げ出力回路における桁上げ信号が、ＡＮＤ出力部およびＯＲ出力部を介して、上位の桁上げ出力回路に入力されることを、繰り返すことにより、最終的な桁上げ信号が得られるように構成されることを特徴とする請求項１〜４の何れかに記載の桁上げ出力回路。
【請求項９】
下位からの桁上げ信号による当該桁の桁上げが有るか否かを判別するために、当該加算桁の各値のＯＲ出力値が全て１であることを検出する全１検出部を用いることを特徴とする請求項請求項１〜４の何れかに記載の桁上げ出力回路。
【請求項１０】
複数ビットからなる２進数値Ａ、Ｂを同様に下位から１以上の任意のビット数でｎ（ｎはｎ≧２の正の整数）分割した各々の値をＡ（１），Ａ（２）、・・・、Ａ（ｎ）および、Ｂ（１），Ｂ（２），・・・，Ｂ（ｎ）とし、分割された各ビットの桁毎に下位桁値から加算を実施する際に、Ａ、Ｂ各々の下位桁値の演算結果から生成される第（ｎ−ｍ）（ｍはｎ＞ｍ≧０の正の整数）の桁上げ信号ＣＯ（ｎ−ｍ）と、Ａ、Ｂ各々の当該加算桁値の第（ｎ−ｍ＋１）の演算結果とから、加算結果となる数値出力Ｓ（ｎ−ｍ＋１）と共に、上位桁の第（ｎ−ｍ＋２）の演算部への第（ｎ−ｍ＋１）の桁上げ信号ＣＯ（ｎ−ｍ＋１）を出力する回路であって、
数値Ａ、Ｂ各々の下位桁の各値を演算して、加算結果となる数値出力Ｓ（ｎ−ｍ）と共に、桁上げ信号ＣＯ（ｎ−ｍ）を出力する第（ｎ−ｍ）の加算部と、
数値Ａ、Ｂ各々の当該加算桁の各値を演算して加算結果となる数値出力Ｓ（ｎ−ｍ＋１）＋１と共に、ＯＲ出力値が全て１であることを検出する第（ｎ−ｍ＋１）の＋１加算部と、
前記第（ｎ−ｍ）の加算部と、前記第（ｎ−ｍ＋１）の＋１加算部との双方から入力があった時に、上位桁の各値を演算する第（ｎ−ｍ＋２）の演算部への第１の仮桁上げ信号ＩＣＯ１（ｎ−ｍ＋１）を出力する第（ｎ−ｍ＋１）のＡＮＤ出力部と、
数値Ａ、Ｂ各々の当該加算桁の各値を演算して、加算結果となる数値出力Ｓ（ｎ−ｍ＋１）と共に、上位桁の第（ｎ−ｍ＋２）の演算部への第２の仮桁上げ信号ＩＣＯ２（ｎ−ｍ＋１）を出力する第（ｎ−ｍ＋１）の加算部と、
前記第１の仮桁上げ信号ＩＣＯ１（ｎ−ｍ＋１）と、前記第２の仮桁上げ信号ＩＣＯ２（ｎ−ｍ＋１）との少なくとも何れかが入力された時に、上位桁の第（ｎ−ｍ＋２）の演算部への桁上げ信号ＣＯ（ｎ−ｍ＋１）を出力する第（ｎ−ｍ＋１）のＯＲ出力部と、
前記第（ｎ−ｍ＋１）の＋１加算部の加算結果Ｓ（ｎ−ｍ＋１）＋１と、前記第（ｎ−ｍ＋１）の加算部の加算結果Ｓ（ｎ−ｍ＋１）が入力されて、前記第（ｎ−ｍ）の加算部からの桁上げ信号ＣＯ（ｎ−ｍ）により一方の加算結果を選択して出力する第（ｎ−ｍ＋１）のマルチプレックス部と
を有することを特徴とする２進数加算回路。
【請求項１１】
前記第（ｎ−ｍ＋１）の＋１加算部、前記第（ｎ−ｍ＋１）の加算部、および、前記第（ｎ−ｍ＋１）のＡＮＤ出力部は、連続する桁値に対応して複数個が設けられ、
前記複数の各ＡＮＤ出力部には、前記当該桁中の下位となる全ての＋１加算部と加算部からの出力が入力され、ＯＲ出力部には、前記複数の全ＡＮＤ出力部からの出力が入力される
ことを特徴とする請求項１０記載の２進数加算回路。
【請求項１２】
前記上位桁の第（ｎ−ｍ＋２）の演算部は、
数値Ａ、Ｂ各々の上位桁の各地を演算して加算結果＋１となる数値出力Ｓ（ｎ−ｍ＋２）＋１を演算して出力すると共に、前記上位桁のＯＲ出力値が全て１であることを検出する第（ｎ−ｍ＋２）の＋１加算部と、
前記第（ｎ−ｍ＋１）のＯＲ出力部と、前記第（ｎ−ｍ＋２）の＋１加算部との双方から入力があった時に、さらに上位桁の第（ｎ−ｍ＋３）の演算部への第１の仮桁上げ信号ＩＣＯ１（ｎ−ｍ＋２）を出力する第（ｎ−ｍ＋２）のＡＮＤ出力部と、
数値Ａ、Ｂ各々の前記上位桁の各値を演算して加算結果となる数値出力Ｓ（ｎ−ｍ＋２）を出力すると共に、さらに上位桁の第（ｎ−ｍ＋３）の演算部への第２の仮桁上げ信号ＩＣＯ２（ｎ−ｍ＋２）を出力する第（ｎ−ｍ＋２）の加算部と、
前記第１の仮桁上げ信号ＩＣＯ１（ｎ−ｍ＋２）と、前記第２の仮桁上げ信号ＩＣＯ２（ｎ−ｍ＋２）との少なくとも何れかが入力された時に、さらに上位桁の第（ｎ−ｍ＋３）の演算部への桁上げ信号ＣＯ（ｎ−ｍ＋２）を出力する第（ｎ−ｍ＋２）のＯＲ出力部と、
前記第（ｎ−ｍ＋２）の＋１加算部の加算結果Ｓ（ｎ−ｍ＋２）＋１と、前記第（ｎ−ｍ＋２）の加算部の加算結果Ｓ（ｎ−ｍ＋２）が入力されて、前記桁上げ信号ＣＯ（ｎ−ｍ＋１）により一方の加算結果を選択して出力する第（ｎ−ｍ＋２）のマルチプレックス部と
を有することを特徴とする請求項１０または１１に記載の２進数加算回路。
【請求項１３】
前記第（ｎ−ｍ＋２）の＋１加算部および前記第（ｎ−ｍ＋２）の加算部は、前記第（ｎ−ｍ）の加算部、前記第（ｎ−ｍ＋１）の＋１加算部および前記第（ｎ−ｍ＋１）の加算部と並列に配置され、
前記第（ｎ−ｍ＋２）のＡＮＤ出力部および前記第（ｎ−ｍ＋２）のＯＲ出力部は、前記第（ｎ−ｍ＋１）のＡＮＤ出力部および前記第（ｎ−ｍ＋１）のＯＲ出力部と直列に配置される
ことを特徴とする請求項１２に記載の２進数加算回路。
【請求項１４】
前記第（ｎ−ｍ＋２）のマルチプレックス部は、
前記加算結果を選択するために、前記第（ｎ−ｍ＋１）のＯＲ出力部からの桁上げ信号ＣＯ（ｎ−ｍ＋１）に加え、前記第（ｎ−ｍ＋２）の＋１加算部の出力Ｓ（ｎ−ｍ＋２）＋１および前記第（ｎ−ｍ＋２）の加算部の出力Ｓ（ｎ−ｍ＋２）を用い、
前記第（ｎ−ｍ＋１）のＯＲ出力部と、前記第（ｎ−ｍ＋２）の＋１加算部との双方から入力があった時に、前記第（ｎ−ｍ＋２）のマルチプレックス部への第１の仮選択信号を出力する選択ＡＮＤ出力部と、
前記選択ＡＮＤ出力部からの第１の仮選択信号と、前記第（ｎ−ｍ＋２）の加算部からの出力である第２の仮選択信号との少なくとも何れかが入力された時に、前記第（ｎ−ｍ＋２）のマルチプレックス部への選択信号を出力する選択ＯＲ出力部と
を有することを特徴とする請求項１３に記載の２進数加算回路。
【請求項１５】
分割使用が可能となるように切り替え用のＡＮＤ回路を、前記第（ｎ−ｍ＋１）のＯＲ出力部の出力段、および、前記第（ｎ−ｍ＋２）の＋１加算部内に各々設けることを特徴とする請求項１４に記載の２進数加算回路。
【請求項１６】
加算される２進数値Ａ、Ｂを分割した各値毎の遅延時間を予め検出しておき、
遅延時間が少ない各値については、前記下位桁のＡＮＤ出力部あるいはＯＲ出力部に入力されるように接続し、
遅延時間が多い各値については、前記上位桁のＡＮＤ出力部あるいはＯＲ出力部に入力されるように接続することを特徴とする請求項１４又は１５に記載の２進数加算回路。
【請求項１７】
前記第（ｎ−ｍ＋２）のマルチプレックス部に入力する加算結果を選択するための選択信号を生成するために、前記ＡＮＤ出力部および前記ＯＲ出力部がツリー形状に組み合わされることを特徴とする請求項１０〜１６の何れかに記載の２進数加算回路。
【請求項１８】
前記第（ｎ−ｍ＋２）のマルチプレックス部に入力する加算結果を生成するための各加算回路は階層的に構成され、且つ、
下位の加算回路における桁上げ信号が、ＡＮＤ出力部およびＯＲ出力部を介して、上位のマルチプレックス部に選択信号として入力されることを、繰り返すことにより、最終的な加算結果が得られるように構成されることを特徴とする請求１０９〜１６の何れかに記載の２進数加算回路。
【請求項１９】
前記第（ｎ−ｍ＋１）のマルチプレックス部および第（ｎ−ｍ＋２）のマルチプレックス部に代えて、第（ｎ−ｍ＋１）の加算部あるいは第（ｎ−ｍ＋２）の加算部からの出力に対して、前記第１の仮選択信号が入力された場合に＋１の加算を実行する＋１加算回路を用いることを特徴とする請求項請求項１０〜１６の何れかに記載の２進数加算回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、多数の論理ゲートを有する集積回路等に用いられる演算回路に関し、さらに詳しくは、２進数を加算する際に桁上がりに要する処理時間を短縮できる加算回路に関する。
【０００２】
【従来の技術】
集積回路中の演算回路は、多数の論理ゲートから構成されている。また、加減乗除の全ての演算は、演算回路の基本となる加算回路により実現することができる。例えば、減算回路は、減数の２の補数を加算回路で加算することにより実現できる。乗算回路は、被乗数を乗数回分加算することで実現できる。除算回路は、被除数から除数が何回減算できるかを調べ、減算できる回数が除算結果の商であり、残りが剰余となる。何れの演算でも下位桁からの桁上がり等の桁移動を考慮する必要がある。例えば、加算では各桁毎の演算と桁上がりにより演算結果が得られる。
【０００３】
以上のように全ての演算の基本は加算回路であることから、加算回路について改善することは全ての四則演算について改善することができることになる。また、一般的に加算回路では、各桁毎の演算については、並列処理が可能であるが、桁上がりについては、下位桁の加算結果を待つ必要がある。つまり、加算回路における上位桁の加算処理部では、下位桁の桁上がり処理の結果を待って、その処理結果を考慮して処理を実施する必要がある。従って、加算処理の速度を改善するためには、上記した下位桁の桁上がり処理の結果を待つ時間を短縮させなければならない。
【０００４】
以下に、従来の多数桁が入力される加算回路について説明する。
【０００５】
図４１は、従来のフルアダー（ＦＡ）及びフルアダーを各桁毎に直列に接続した非同期型（リップルキャリ型）アダー（ＲＣＡ）の構成を示すブロック図である。
【０００６】
図４１（ａ）に示したフルアダー１０は、下位桁からの桁上げ信号ＣＩ、２進数値Ａおよび２進数値Ｂが入力されて何れか１入力がある場合のみ出力値Ｓを送出する入力の排他的論理和回路２と、２進数値Ａおよび２進数値Ｂが入力される２入力のＡＮＤ回路３と、２進数値Ｂおよび下位桁からの桁上げ信号ＣＩが入力される２入力のＡＮＤ回路４と、下位桁からの桁上げ信号ＣＩおよび２進数値Ａが入力される２入力のＡＮＤ回路５と、ＡＮＤ回路３〜５が入力されて上位桁への桁上げ信号ＣＯ(Carry Out)を出力する３入力のＯＲ回路６とから構成される。
【０００７】
フルアダー１０の最長経路となるクリティカルパス（ＣＰ）は、例えば、２入力ＡＮＤ回路３と３入力ＯＲ回路の経路となる。ここでＣＰの遅延時間については、本来回路毎に異なるが、以下の説明では、説明を簡単にするために仮にＡＮＤ回路およびＯＲ回路等の各回路における遅延（ディレイ）を全て一定時間の０．５（ｄｅｌ）とする。すると、図４１（ａ）のクリティカルパス（ＣＰ）の遅延時間は１．０（ｄｅｌ）となる。なお、３入力ＯＲ回路については、２入力ＯＲよりも遅延時間が増加するが、ここでは後述する図４１（ｂ）に示したリップルキャリ型アダー等の多桁入力の加算回路の一部に用いられる回路としての説明であるので簡略化して２入力ＯＲ回路と同等と仮定する。また、遅延時間の単位‘ｄｅｌ’は、例えば、‘ｎＳ’等と読み替えても良い。
【０００８】
図４１（ｂ）に示したリップルキャリ型アダーでは、図４１（ａ）に示した８個のフルアダー（ＦＡ）を桁上げ信号（ＣＯ）の入出力が直列となるように接続されている。なお、図４１（ｂ）では、各フルアダーにおける排他的論理和回路２と出力値Ｓは表示を省略している。
【０００９】
図４１（ｂ）は、Ａ（０）〜Ａ（７）の８桁の２進数値と、Ｂ（０）〜Ｂ（７）の８桁の２進数値とを加算する場合であり、１段目の加算回路であるフルアダーＦＡ（０）には、２進数値の最下位の桁値であるＡ（０）およびＢ（０）が入力され、１段目の桁上げ信号１ＣＯ（ＲＣＡ）が２段目の加算回路であるフルアダーＦＡ（１）に出力される。２段目の加算回路であるフルアダーＦＡ（１）には、２進数値の最下位から２番目の桁値であるＡ（１）およびＢ（１）が入力され、２段目の桁上げ信号２ＣＯ（ＲＣＡ）が３段目の加算回路であるフルアダーＦＡ（２）に出力される。３段目の加算回路であるフルアダーＦＡ（２）には、２進数値の最下位から３番目の桁値であるＡ（２）およびＢ（２）が入力され、３段目の桁上げ信号３ＣＯ（ＲＣＡ）が４段目の加算回路であるフルアダーＦＡ（３）に出力される。同様にして、各段のフルアダーＦＡ（ｎ）（ｎは正の整数）には、２進数値の最下位からｎ番目の桁値であるＡ（ｎ−１）およびＢ（ｎ−１）が入力され、ｎ段目の桁上げ信号ｎＣＯ（ＲＣＡ）がｎ＋１段目の加算回路であるフルアダーＦＡ（ｎ＋１）に出力される。図４０（ｂ）の場合には、最後に、８段目の加算回路であるフルアダーＦＡ（７）から、８桁の２進数値の最上位の桁値であるＡ（７）およびＢ（７）が入力され、８段目の桁上げ信号８ＣＯ（ＲＣＡ）が出力される。
【００１０】
このように、図４１（ｂ）に示すリップルキャリ型アダーでは、入力される２進数値の桁数が増加するほど、フルアダーの段数も増加して遅延時間も増加する。そのため、入力される２進数値の各桁における加算は先に実施しておき、各桁の桁上げ信号ＣＯが発生する場合の当該桁の入力及び下位桁の出力状況を場合分けして場合毎に対応するＡＮＤ回路を設置し、その何れかのＡＮＤ回路から出力があった場合には桁上げがある時の加算出力を実施するキャリールックアヘッド型アダー（ＣＬＡ）が知られている。
【００１１】
キャリールックアヘッド型アダーでは、全ての下位桁の桁上げ信号と全ての下位桁のＡＮＤ回路の出力から当該桁の桁上がりを演算により予測するので、下位の各桁の桁上げ出力を待つ必要が無くなるが、上位の桁になるほど桁上がりの予測を実施するための入力数が増加する。例えば、４桁の２進数値を加算するキャリールックアヘッド型アダーでは、クリティカルパスに５入力のＡＮＤ素子及びＯＲ素子が用いられるが、８桁の２進数値を加算する場合には、クリティカルパスに９入力のＡＮＤ素子及びＯＲ素子が用いられることになり、１２桁の２進数値を加算する場合には、クリティカルパスに１３入力のＡＮＤ素子及びＯＲ素子が用いられることになる。
【００１２】
５入力で１段として表されるＡＮＤ素子及びＯＲ素子は、２入力の素子に置き換えるとクリティカルパスが３段に増加する。同様にして、９入力あるいは１３入力で１段として表されるＡＮＤ素子及びＯＲ素子は、２入力の素子に置き換えるとクリティカルパスが４段に増加する。同様に、１７以上３２以下の入力数で１段として表されるＡＮＤ素子及びＯＲ素子は、２入力の素子に置き換えるとクリティカルパスが５段に増加する。
【００１３】
ここで、上記した各桁数の加算回路における遅延時間としては、２入力の素子の場合に基づくので、ＡＮＤ素子及びＯＲ素子の入力数が２倍に増加した場合に、クリティカルパスの遅延時間はＡＮＤ素子およびＯＲ素子が１段分だけ増大することになる。従って、例えば、４桁の２進数値を加算する場合から、８桁の２進数値を加算する場合になると、遅延時間が１．０ｄｅｌだけ増加して４．５ｄｅｌになる。リップルキャリ型アダーでは、８桁の２進数値を加算する場合のクリティカルパスの遅延時間が８．０ｄｅｌであったので、キャリールックアヘッド型アダーでは、遅延時間をリップルキャリ型アダーよりも減少させることができることになる。
【００１４】
しかし、キャリールックアヘッド型アダーでは、クリティカルパスとなる回路の他にも、全ての下位桁の桁上げ信号と全ての下位桁のＡＮＤ回路の出力により桁上げがある組み合わせを場合分けして、各々の場合を演算するために個別のＡＮＤ素子が必要になるので、桁数の増加により回路規模が増大し回路が複雑化する。例えば、１２桁以上が入力されるキャリールックアヘッド型アダーでは、上記した１３入力のＡＮＤ素子及びＯＲ素子に加え、１２，１１、１０，９，８，７，６，５，４，３，および、２入力のＡＮＤ素子を備え、各ＡＮＤ素子への配線を実施する必要があり、素子数の増加および回路の複雑化という点からも問題である。
【００１５】
図４１（ｂ）に示すリップルキャリ型アダーにおける入力桁数の増加に伴う遅延時間の増加を解決するために、上記したキャリールックアヘッド型アダーの他に、入力される２進数値の各桁毎あるいは複数桁毎における、桁上げがある場合の加算結果と無い場合の加算結果を予め演算しておき、下位桁の桁上げ信号ＣＯにより何れかの加算結果を選択するキャリーセレクト回路が知られている。
【００１６】
図４２は、従来のキャリーセレクト型アダー（ＣＳＡ）の構成を示すブロック図である。
【００１７】
図４２（ａ）のキャリーセレクト型アダー９００は、８桁の２進数値の加算を実施する回路であり、下位４桁であるＡ（０）〜Ａ（３）およびＢ（０）〜Ｂ（３）が入力されて加算結果と桁上げ信号ＩＣＯ９０１を出力するリップルキャリ型アダー（ＲＣＡ）９０１と、上位４桁であるＡ（４）〜Ａ（７）およびＢ（４）〜Ｂ（７）が入力されて加算結果に１を加えた値と桁上げ信号ＩＣＯ９０２を出力するＲＣＡ９０２と、Ａ（４）〜Ａ（７）およびＢ（４）〜Ｂ（７）が入力されて加算結果と桁上げ信号ＩＣＯ９０３を出力するＲＣＡ９０３と、ＡＮＤ回路とＯＲ回路を一体化させたＡＮＤ−ＯＲ回路９０４とから構成される。
【００１８】
ＡＮＤ−ＯＲ回路９０４のＡＮＤ入力部には、ＲＣＡ９０１から出力されるＩＣＯ９０１およびＲＣＡ９０１から出力されるＩＣＯ９０２が入力され、ＡＮＤ−ＯＲ回路９０４のＯＲ入力部には、ＲＣＡ９０３から出力されるＩＣＯ９０３が入力される。即ち、下位４桁の加算部からの桁上げ信号が有る（１であり）場合で、且つ、上位４桁の加算結果に１を足した値が１である場合か、あるいは、上位４桁の加算結果が１である場合に桁上げ信号８ＣＯが出力される。
【００１９】
図４２（ｂ）は、ＲＣＡ９０１あるいはＲＣＡ９０３の内部構成を示すブロック図である。
【００２０】
ＲＣＡ９０１あるいはＲＣＡ９０３の内部には、４段のフルアダーが設置されている。ＲＣＡ９０１では、各段毎にＡ（０）〜Ａ（３）およびＢ（０）〜Ｂ（３）が入力されて最終段から桁上げ信号ＩＣＯ９０１が出力され、ＲＣＡ９０３では、各段毎にＡ（４）〜Ａ（７）およびＢ（４）〜Ｂ（７）が入力されて最終段から桁上げ信号ＩＣＯ９０３が出力される。各フルアダーの遅延時間が１．０ｄｅｌとすると、ＩＣＯ９０１あるいはＩＣＯ９０３は、クリティカルパスを経由しているので、遅延時間が４．０ｄｅｌとなる。
【００２１】
図４２（ｃ）は、ＲＣＡ９０２の内部構成を示すブロック図である。
【００２２】
ＲＣＡ９０２の内部にも、４段のフルアダーが設置されているが、最下位桁のフルアダーには桁上げ信号として’１’が入力される。ＲＣＡ９０２では、各段毎にＡ（４）〜Ａ（７）およびＢ（４）〜Ｂ（７）が入力されて最終段から桁上げ信号ＩＣＯ９０２が出力される。ＲＣＡ９０３とＲＣＡ９０２の違いは、最下位桁のフルアダーに桁上げ信号として’１’が入力されるか否かとなる。また、ＩＣＯ９０１あるいはＩＣＯ９０３と同様に、ＩＣＯ９０２の遅延時間は４．０ｄｅｌとなる。
【００２３】
図４２に示した８桁の加算を実施するキャリーセレクト型アダー９００は、ＡＮＤ−ＯＲ回路９０４の遅延時間を１．０ｄｅｌとすると、クリティカルパスの遅延時間は、５．０ｄｅｌとなる。例えば、２倍の１６桁の加算を実施する場合には、クリティカルパスの遅延時間は、１０．０ｄｅｌとなり、さらにその２倍の３２桁の加算を実施する場合には、クリティカルパスの遅延時間は、２０．０ｄｅｌとなる。
【００２４】
【発明が解決しようとする課題】
しかしながら、上記した従来のリップルキャリ型アダーあるいはキャリーセレクト型アダーでは、入力桁数の増加により桁上げ出力回路による遅延時間が増加するという問題があり、キャリールックアヘッド型アダーでは、入力桁数の増加による遅延時間の増加についてはある程度抑制できるが、桁上げ出力を予測する回路が複雑化し、製造が困難になるという問題があった。
【００２５】
本発明は、上述した如き従来の問題を解決するためになされたものであって、入力桁数が増加しても、回路を複雑化させずに遅延時間を抑制できる桁上げ出力回路およびアダーを提供することを目的とする。
【００２６】
【課題を解決するための手段】
上述の目的を達成するため、本発明の２進数加算時の桁上げ出力回路は、複数ビットからなる２進数値Ａ、Ｂを同様に下位から１以上の任意のビット数でｎ（ｎはｎ≧２の正の整数）分割した各々の値をＡ（１），Ａ（２）、・・・、Ａ（ｎ）および、Ｂ（１），Ｂ（２），・・・，Ｂ（ｎ）とし、分割された各ビットの桁毎に下位桁値から加算を実施する際に、Ａ、Ｂ各々の下位桁値の演算結果から生成される第（ｎ−ｍ）（ｍはｎ＞ｍ≧０の正の整数）の桁上げ信号ＣＯ（ｎ−ｍ）と、Ａ、Ｂ各々の当該加算桁値の第（ｎ−ｍ＋１）の演算結果とから、上位桁の第（ｎ−ｍ＋２）の演算部への第（ｎ−ｍ＋１）の桁上げ信号ＣＯ（ｎ−ｍ＋１）を出力する回路であって、数値Ａ、Ｂ各々の下位桁の各値を演算して桁上げ信号ＣＯ（ｎ−ｍ）を出力する第（ｎ−ｍ）の桁上げ部と、数値Ａ、Ｂ各々の当該加算桁の各値のＯＲ出力値が全て１であることを検出する第（ｎ−ｍ＋１）の全１検出部と、第（ｎ−ｍ）の桁上げ部と、第（ｎ−ｍ＋１）の全１検出部との双方から入力があった時に、上位桁の各値を演算する第（ｎ−ｍ＋２）の演算部への第１の仮桁上げ信号ＩＣＯ１（ｎ−ｍ＋１）を出力する第（ｎ−ｍ＋１）のＡＮＤ出力部と、数値Ａ、Ｂ各々の当該加算桁の各値を演算して、上位桁の第（ｎ−ｍ＋２）の演算部への第２の仮桁上げ信号ＩＣＯ２（ｎ−ｍ＋１）を出力する第（ｎ−ｍ＋１）の桁上げ部と、第１の仮桁上げ信号ＩＣＯ１（ｎ−ｍ＋１）と、第２の仮桁上げ信号ＩＣＯ２（ｎ−ｍ＋１）との少なくとも何れかが入力された時に、上位桁の第（ｎ−ｍ＋２）の演算部への桁上げ信号ＣＯ（ｎ−ｍ＋１）を出力する第（ｎ−ｍ＋１）のＯＲ出力部とを有する。
【００２７】
また、本発明の桁上げ出力回路では、第（ｎ−ｍ＋１）の全１検出部、第（ｎ−ｍ＋１）の桁上げ部、および、第（ｎ−ｍ＋１）のＡＮＤ出力部は、連続する桁値に対応して複数個が設けられ、複数の各ＡＮＤ出力部には、当該桁中の下位となる全ての全１検出部と当該桁上げ部からの出力が入力され、ＯＲ出力部には、複数の全ＡＮＤ出力部からの出力が入力される。
【００２８】
また、本発明の桁上げ出力回路では、上位桁の第（ｎ−ｍ＋２）の演算部は、数値Ａ、Ｂ各々の上位桁のＯＲ出力値が全て１であることを検出する第（ｎ−ｍ＋２）の全１検出部と、第（ｎ−ｍ＋１）のＯＲ出力部と、第（ｎ−ｍ＋２）の全１検出部との双方から入力があった時に、さらに上位桁の第（ｎ−ｍ＋３）の演算部への第１の仮桁上げ信号ＩＣＯ１（ｎ−ｍ＋２）を出力する第（ｎ−ｍ＋２）のＡＮＤ出力部と、数値Ａ、Ｂ各々の上位桁の各値を演算し、さらに上位桁の第（ｎ−ｍ＋３）の演算部への第２の仮桁上げ信号ＩＣＯ２（ｎ−ｍ＋２）を出力する第（ｎ−ｍ＋２）の桁上げ部と、第１の仮桁上げ信号ＩＣＯ１（ｎ−ｍ＋２）と、第２の仮桁上げ信号ＩＣＯ２（ｎ−ｍ＋２）との少なくとも何れかが入力された時に、さらに上位桁の第（ｎ−ｍ＋３）の演算部への桁上げ信号ＣＯ（ｎ−ｍ＋２）を出力する第（ｎ−ｍ＋２）のＯＲ出力部とを有する。
【００２９】
また、本発明の桁上げ出力回路では、第（ｎ−ｍ＋２）の全１検出部および前記第（ｎ−ｍ＋２）の桁上げ部は、第（ｎ−ｍ）の桁上げ部、第（ｎ−ｍ＋１）の全１検出部および第（ｎ−ｍ＋１）の桁上げ部と並列に配置され、第（ｎ−ｍ＋２）のＡＮＤ出力部および第（ｎ−ｍ＋２）のＯＲ出力部は、第（ｎ−ｍ＋１）のＡＮＤ出力部および第（ｎ−ｍ＋１）のＯＲ出力部と直列に配置される。
【００３０】
また、本発明の桁上げ出力回路では、分割使用が可能となるように切り替え用のＡＮＤ回路を、第（ｎ−ｍ＋１）のＯＲ出力部の出力段、および、第（ｎ−ｍ＋２）の全１検出部内に各々設ける。
【００３１】
また、本発明の桁上げ出力回路では、加算される２進数値Ａ、Ｂを分割した各値毎の遅延時間を予め検出しておき、遅延時間が少ない各値については、下位桁のＡＮＤ出力部あるいはＯＲ出力部に入力されるように接続し、遅延時間が多い各値については、上位桁のＡＮＤ出力部あるいはＯＲ出力部に入力されるように接続する。
【００３２】
また、本発明の桁上げ出力回路では、各桁上げ信号を生成するために、ＡＮＤ出力部およびＯＲ出力部がツリー形状に組み合わされる。
【００３３】
また、本発明の桁上げ出力回路では、各桁上げ信号を生成する各桁上げ出力回路は、階層的に構成され、且つ、下位の桁上げ出力回路における桁上げ信号が、ＡＮＤ出力部およびＯＲ出力部を介して、上位の桁上げ出力回路に入力されることを、繰り返すことにより、最終的な桁上げ信号が得られるように構成される。
【００３４】
また、本発明の桁上げ出力回路では、下位からの桁上げ信号による当該桁の桁上げが有るか否かを判別するために、当該加算桁の各値のＯＲ出力値が全て１であることを検出する全１検出部を用いる。
【００３５】
また、本発明の２進数加算回路では、複数ビットからなる２進数値Ａ、Ｂを同様に下位から１以上の任意のビット数でｎ（ｎはｎ≧２の正の整数）分割した各々の値をＡ（１），Ａ（２）、・・・、Ａ（ｎ）および、Ｂ（１），Ｂ（２），・・・，Ｂ（ｎ）とし、分割された各ビットの桁毎に下位桁値から加算を実施する際に、Ａ、Ｂ各々の下位桁値の演算結果から生成される第（ｎ−ｍ）（ｍはｎ＞ｍ≧０の正の整数）の桁上げ信号ＣＯ（ｎ−ｍ）と、Ａ、Ｂ各々の当該加算桁値の第（ｎ−ｍ＋１）の演算結果とから、加算結果となる数値出力Ｓ（ｎ−ｍ＋１）と共に、上位桁の第（ｎ−ｍ＋２）の演算部への第（ｎ−ｍ＋１）の桁上げ信号ＣＯ（ｎ−ｍ＋１）を出力する回路であって、数値Ａ、Ｂ各々の下位桁の各値を演算して、加算結果となる数値出力Ｓ（ｎ−ｍ）と共に、桁上げ信号ＣＯ（ｎ−ｍ）を出力する第（ｎ−ｍ）の加算部と、数値Ａ、Ｂ各々の当該加算桁の各値を演算して加算結果となる数値出力Ｓ（ｎ−ｍ＋１）＋１と共に、ＯＲ出力値が全て１であることを検出する第（ｎ−ｍ＋１）の＋１加算部と、第（ｎ−ｍ）の加算部と、第（ｎ−ｍ＋１）の＋１加算部との双方から入力があった時に、上位桁の各値を演算する第（ｎ−ｍ＋２）の演算部への第１の仮桁上げ信号ＩＣＯ１（ｎ−ｍ＋１）を出力する第（ｎ−ｍ＋１）のＡＮＤ出力部と、数値Ａ、Ｂ各々の当該加算桁の各値を演算して、加算結果となる数値出力Ｓ（ｎ−ｍ＋１）と共に、上位桁の第（ｎ−ｍ＋２）の演算部への第２の仮桁上げ信号ＩＣＯ２（ｎ−ｍ＋１）を出力する第（ｎ−ｍ＋１）の加算部と、第１の仮桁上げ信号ＩＣＯ１（ｎ−ｍ＋１）と、第２の仮桁上げ信号ＩＣＯ２（ｎ−ｍ＋１）との少なくとも何れかが入力された時に、上位桁の第（ｎ−ｍ＋２）の演算部への桁上げ信号ＣＯ（ｎ−ｍ＋１）を出力する第（ｎ−ｍ＋１）のＯＲ出力部と、第（ｎ−ｍ＋１）の＋１加算部の加算結果Ｓ（ｎ−ｍ＋１）＋１と、第（ｎ−ｍ＋１）の加算部の加算結果Ｓ（ｎ−ｍ＋１）が入力されて、第（ｎ−ｍ）の加算部からの桁上げ信号ＣＯ（ｎ−ｍ）により一方の加算結果を選択して出力する第（ｎ−ｍ＋１）のマルチプレックス部とを有する。
【００３６】
また、本発明の２進数加算回路では、第（ｎ−ｍ＋１）の＋１加算部、第（ｎ−ｍ＋１）の加算部、および、第（ｎ−ｍ＋１）のＡＮＤ出力部は、連続する桁値に対応して複数個が設けられ、複数の各ＡＮＤ出力部には、当該桁中の下位となる全ての＋１加算部と加算部からの出力が入力され、ＯＲ出力部には、複数の全ＡＮＤ出力部からの出力が入力される。
【００３７】
また、本発明の２進数加算回路では、上位桁の第（ｎ−ｍ＋２）の演算部は、数値Ａ、Ｂ各々の上位桁の各地を演算して加算結果＋１となる数値出力Ｓ（ｎ−ｍ＋２）＋１を演算して出力すると共に、上位桁のＯＲ出力値が全て１であることを検出する第（ｎ−ｍ＋２）の＋１加算部と、第（ｎ−ｍ＋１）のＯＲ出力部と、第（ｎ−ｍ＋２）の＋１加算部との双方から入力があった時に、さらに上位桁の第（ｎ−ｍ＋３）の演算部への第１の仮桁上げ信号ＩＣＯ１（ｎ−ｍ＋２）を出力する第（ｎ−ｍ＋２）のＡＮＤ出力部と、数値Ａ、Ｂ各々の上位桁の各値を演算して加算結果となる数値出力Ｓ（ｎ−ｍ＋２）を出力すると共に、さらに上位桁の第（ｎ−ｍ＋３）の演算部への第２の仮桁上げ信号ＩＣＯ２（ｎ−ｍ＋２）を出力する第（ｎ−ｍ＋２）の加算部と、第１の仮桁上げ信号ＩＣＯ１（ｎ−ｍ＋２）と、第２の仮桁上げ信号ＩＣＯ２（ｎ−ｍ＋２）との少なくとも何れかが入力された時に、さらに上位桁の第（ｎ−ｍ＋３）の演算部への桁上げ信号ＣＯ（ｎ−ｍ＋２）を出力する第（ｎ−ｍ＋２）のＯＲ出力部と、第（ｎ−ｍ＋２）の＋１加算部の加算結果Ｓ（ｎ−ｍ＋２）＋１と、第（ｎ−ｍ＋２）の加算部の加算結果Ｓ（ｎ−ｍ＋２）が入力されて、桁上げ信号ＣＯ（ｎ−ｍ＋１）により一方の加算結果を選択して出力する第（ｎ−ｍ＋２）のマルチプレックス部とを有する。
【００３８】
また、本発明の２進数加算回路では、第（ｎ−ｍ＋２）の＋１加算部および第（ｎ−ｍ＋２）の加算部は、第（ｎ−ｍ）の加算部、第（ｎ−ｍ＋１）の＋１加算部および第（ｎ−ｍ＋１）の加算部と並列に配置され、第（ｎ−ｍ＋２）のＡＮＤ出力部および第（ｎ−ｍ＋２）のＯＲ出力部は、第（ｎ−ｍ＋１）のＡＮＤ出力部および第（ｎ−ｍ＋１）のＯＲ出力部と直列に配置される。
【００３９】
また、本発明の２進数加算回路では、第（ｎ−ｍ＋２）のマルチプレックス部は、加算結果を選択するために、第（ｎ−ｍ＋１）のＯＲ出力部からの桁上げ信号ＣＯ（ｎ−ｍ＋１）に加え、第（ｎ−ｍ＋２）の＋１加算部の出力Ｓ（ｎ−ｍ＋２）＋１および第（ｎ−ｍ＋２）の加算部の出力Ｓ（ｎ−ｍ＋２）を用い、第（ｎ−ｍ＋１）のＯＲ出力部と、第（ｎ−ｍ＋２）の＋１加算部との双方から入力があった時に、第（ｎ−ｍ＋２）のマルチプレックス部への第１の仮選択信号を出力する選択ＡＮＤ出力部と、選択ＡＮＤ出力部からの第１の仮選択信号と、第（ｎ−ｍ＋２）の加算部からの出力である第２の仮選択信号との少なくとも何れかが入力された時に、第（ｎ−ｍ＋２）のマルチプレックス部への選択信号を出力する選択ＯＲ出力部とを有する。
【００４０】
また、本発明の２進数加算回路では、分割使用が可能となるように切り替え用のＡＮＤ回路を、第（ｎ−ｍ＋１）のＯＲ出力部の出力段、および、第（ｎ−ｍ＋２）の＋１加算部内に各々設ける。
【００４１】
また、本発明の２進数加算回路では、加算される２進数値Ａ、Ｂを分割した各値毎の遅延時間を予め検出しておき、遅延時間が少ない各値については、下位桁のＡＮＤ出力部あるいはＯＲ出力部に入力されるように接続し、遅延時間が多い各値については、上位桁のＡＮＤ出力部あるいはＯＲ出力部に入力されるように接続する。
【００４２】
また、本発明の２進数加算回路では、第（ｎ−ｍ＋２）のマルチプレックス部に入力する加算結果を選択するための選択信号を生成するために、ＡＮＤ出力部およびＯＲ出力部がツリー形状に組み合わされる。
【００４３】
また、本発明の２進数加算回路では、第（ｎ−ｍ＋２）のマルチプレックス部に入力する加算結果を生成するための各加算回路は階層的に構成され、且つ、下位の加算回路における桁上げ信号が、ＡＮＤ出力部およびＯＲ出力部を介して、上位のマルチプレックス部に選択信号として入力されることを、繰り返すことにより、最終的な加算結果が得られるように構成される。
【００４４】
また、本発明の２進数加算回路では、第（ｎ−ｍ＋１）のマルチプレックス部および第（ｎ−ｍ＋２）のマルチプレックス部に代えて、第（ｎ−ｍ＋１）の加算部あるいは第（ｎ−ｍ＋２）の加算部からの出力に対して、第１の仮選択信号が入力された場合に＋１の加算を実行する＋１加算回路を用いる。
【００４５】
【発明の実施の形態】
（第１の実施形態）
以下、本発明を図示した実施形態に基づいて説明する。
【００４６】
図１は、本発明の第１の実施形態の桁上げ出力回路の構成を示すブロック図である。
【００４７】
図１（ａ）の４桁の２進数値の加算を実施する際の桁上げ出力回路１００は、下位２桁であるＡ（０）〜Ａ（１）およびＢ（０）〜Ｂ（１）が入力されて下位桁側中間桁上げ信号ＬＣを出力する下位桁側桁上げ出力回路（ＬＣＡ）１５１と、上位２桁であるＡ（２）〜Ａ（３）およびＢ（２）〜Ｂ（３）が入力されて各桁の加算結果が全て‘１’であることを検出して、各桁の加算出力が全て‘１’であることを示す全１信号ＡＬ１を出力するＨＡＬ（１）１５２と、Ａ（２）〜Ａ（３）およびＢ（２）〜Ｂ（３）が入力されて上位桁側中間桁上げ信号ＩＣＯ２を出力する上位桁側桁上げ出力回路（ＨＣＡ）１５３と、ＡＮＤ回路４４ａとＯＲ回路４４ｂを一体化させたＡＮＤ−ＯＲ回路４４とから構成される。ＡＮＤ−ＯＲ回路４４のクリティカルパスの遅延時間は、０．５ｄｅｌのＡＮＤ回路４４ａと０．５ｄｅｌのＯＲ回路４４ｂとの和となるので１．０ｄｅｌとなる。
【００４８】
ＡＮＤ−ＯＲ回路４４のＡＮＤ入力部には、ＬＣＡ１５１から出力される信号ＬＣおよびＨＡＬ（１）１５２から出力される信号ＡＬ１が入力され、ＡＮＤ−ＯＲ回路４４のＯＲ入力部には、ＨＣＡ１５３から出力される信号ＩＣＯ２が入力される。即ち、下位２桁の加算部であるＬＣＡ１５１の桁上げ出力が‘１’であることから下位桁側中間桁上げ信号ＬＣが出力される場合で、且つ、上位２桁の加算結果が全て‘１’であることを示すＡＬ１が出力される場合か、あるいは、上位２桁の桁上げ出力が‘１’となる上位桁側中間桁上げ信号ＩＣＯ２が出力される場合に桁上げ信号４ＣＯが出力される。また、ＡＮＤ回路４４ａからＯＲ回路４４ｂへは中間桁上げ信号ＩＣ１が出力され、ＯＲ回路４４ｂでは、中間桁上げ信号ＩＣ１あるいは中間桁上げ信号ＩＣＯ２が入力された場合に、桁上げ信号４ＣＯを出力する。
【００４９】
つまり、本実施形態のＡＮＤ−ＯＲ回路４４では、一方では、下位２桁の加算部であるＬＣＡ１５１からの桁上げ信号ＬＣ、および、上位２桁の出力が全て１であることを検出するＨＡＬ１５２からの全１信号ＡＬ１をＡＮＤ演算することにより、下位２桁の加算部からの桁上げにより上位２桁からの桁上げがあるか否かを判断し、他方では、上位２桁の加算部であるＨＣＡ１５３からの桁上げ信号ＩＣＯ２により、上位２桁の加算部であるＨＣＡ１５３のみによる桁上げがあるか否かを判断する。
【００５０】
図１（ｂ）は、図１（ａ）中のＬＣＡ１５１の内部構成を示すブロック図である。
【００５１】
ＬＣＡ１５１の内部には、２入力のＡＮＤ回路１１１と、２入力のＯＲ回路１１２および１１３が設置されている。ＡＮＤ回路１１１には、加算される４桁の２進数値Ａ，Ｂの最下位桁Ａ（０）およびＢ（０）が入力されて、双方の入力が１である場合に１が出力される。ＯＲ回路１１２には、加算される４桁の２進数値Ａ，Ｂの最下位から２番目の桁Ａ（１）およびＢ（１）が入力されて、何れかの入力が１である場合に１が出力される。ＯＲ回路１１３には、ＡＮＤ回路１１１からの出力およびＯＲ回路１１２からの出力が入力されて、何れかの入力が１である場合に下位桁側中間桁上げ信号ＬＣとして１が出力される。ＬＣＡ１５１のクリティカルパスの遅延時間は、各ＯＲ回路およびＡＮＤ回路の遅延時間が０．５ｄｅｌであることから、１．０ｄｅｌとなる。
【００５２】
図１（ｃ）は、図１（ａ）中のＨＡＬ（１）の内部構成を示すブロック図である。
【００５３】
ＨＡＬ（１）１５２の内部には、２入力のＯＲ回路１２１および１２２と、２入力のＡＮＤ回路１２３が設置されている。ＯＲ回路１２１には、加算される４桁の２進数値Ａ，Ｂの最上位から２番目の桁Ａ（２）およびＢ（２）が入力されて、何れかの入力が１である場合に１が出力される。ＯＲ回路１２２には、加算される４桁の２進数値Ａ，Ｂの最上位桁Ａ（３）およびＢ（３）が入力されて、何れかの入力が１である場合に１が出力される。ＡＮＤ回路１２３には、ＯＲ回路１２１からの出力およびＯＲ回路１２２からの出力が入力されて、双方の入力が１である場合に上位桁側の全桁の値が１であることを示す全１信号ＡＬ１が出力される。ＨＡＬ（１）１５２のクリティカルパスの遅延時間は、ＬＣＡ１５１と同様に１．０ｄｅｌとなる。
【００５４】
図１（ｄ）は、図１（ａ）中のＨＣＡ１５３の内部構成を示すブロック図である。
【００５５】
ＨＣＡ１５３の内部には、２入力のＡＮＤ回路１３１と、２入力のＯＲ回路１３２および１３３が設置されている。ＡＮＤ回路１３１には、加算される４桁の２進数値Ａ，Ｂの最上位から２番目の桁Ａ（２）およびＢ（２）が入力されて、双方の入力が１である場合に１が出力される。ＯＲ回路１３２には、加算される４桁の２進数値Ａ，Ｂの最上位桁Ａ（３）およびＢ（３）が入力されて、何れかの入力が１である場合に１が出力される。ＯＲ回路１３３には、ＡＮＤ回路１３１からの出力およびＯＲ回路１３２からの出力が入力されて、何れかの入力が１である場合に上位桁側中間桁上げ信号ＩＣＯ２として１が出力される。ＨＣＡ１５３のクリティカルパスの遅延時間は、ＬＣＡ１５１と同様に１．０ｄｅｌとなる。
【００５６】
図２（ａ）は、ＨＡＬ（１）１５２の入力と出力を場合分けした図表である。
【００５７】
図２（ａ）のＡ（２）、Ａ（３）、Ｂ（２）、Ｂ（３）欄は、ＨＡＬ（１）１５２の入力内容を上段にＡの入力内容、下段にＢの入力内容として、各場合毎に示した欄である。また、ＡＬ１の欄は、ＨＡＬ（１）１５２の出力内容（１または０）を示した欄である。この図表に示すように、Ａ（２）とＢ（２）の加算結果が１となり、且つ、Ａ（３）とＢ（３）の加算結果が１となる場合のみに、ＨＡＬ（１）１５２からは全１信号であるＡＬ１が出力される。
【００５８】
図２（ｂ）は、ＩＣＯ２、ＬＣ、および、ＡＬ１について桁上げがある場合と無い場合を、４桁の２進数値を例示と共に示した図表である。
【００５９】
図２中で、ｅｘの欄は、加算される４桁の２進数値ＡおよびＢを上下２段に例示した欄であり、ＩＣＯ２の欄は、各例示数値におけるＨＣＡ１５３の出力内容（１または０）を示す欄であり、ＬＣの欄は、各例示数値におけるＬＣＡ１５１の出力内容（１または０）を示す欄であり、ＡＬ１の欄は、各例示数値におけるＨＡＬ（１）の出力内容（１または０）を示す欄である。ｅｘの欄では、まず、上位桁側の演算により桁上げ信号ＩＣＯ２が出力される場合、および出力されない場合、に場合分けしている。また、上位桁側のみの演算により桁上げ信号ＩＣＯ２が出力されない場合については、下位桁側の中間桁上げ信号ＬＣが出力される場合と出力されない場合に場合分けし、さらに、中間桁上げ信号ＬＣが出力される場合とされない場合の各々について、上位桁が全１である場合の信号ＡＬ１が出力される場合と出力されない場合について場合分けしている。
【００６０】
上位桁側の演算により桁上げ信号ＩＣＯ２が出力される場合は、加算される４桁の２進数値ＡおよびＢの最上位桁が双方とも１である場合であり、桁上げ信号ＩＣＯ２が出力されない場合は、２進数値ＡおよびＢの最上位桁のうち少なくとも一方が０である場合である。同様にして、下位桁側の中間桁上げ信号ＬＣが出力される場合は、加算される４桁の２進数値ＡおよびＢの最下位から２番目の桁が双方とも１である場合であり、中間桁上げ信号ＬＣが出力されない場合は、２進数値ＡおよびＢの最下位から２番目の桁のうち少なくとも一方が０である場合である。信号ＡＬ１が出力される場合は、上位桁側の演算により最上位桁および最上位から２番目の桁の演算結果が双方ともに１となる場合であり、信号ＡＬ１が出力されない場合は、最上位桁および最上位から２番目の桁の演算結果のうち少なくとも一方が０である場合である。
【００６１】
上記したように、４桁の２進数値を加算する桁上げ出力回路１００におけるクリティカルパスの遅延時間は、ＬＣＡ又はＨＡＬ（１）又はＨＣＡの１．０ｄｅｌと、ＡＮＤ−ＯＲ回路４４の１．０ｄｅｌとの和であるので２．０ｄｅｌとなる。４桁の２進数値の加算を例えば図３０に示したリップルキャリ型アダーで実施した場合には、クリティカルパスの遅延時間が４．０ｄｅｌとなるので、桁上げ出力回路１００では遅延時間を減少させることができる。また、４桁の２進数値の加算をキャリールックアヘッド型アダーで実施した場合にも、クリティカルパスの遅延時間が３．５ｄｅｌまたは３．０ｄｅｌとなるので、桁上げ出力回路１００では遅延時間を抑制できる。
【００６２】
ここで、本実施形態の桁上げ出力回路１００が従来のキャリールックアヘッド型アダー（ＣＬＡ）に対して回路構成を簡単にできることを説明するために、キャリールックアヘッド型アダーについて説明する。
【００６３】
図３は、キャリールックアヘッド型アダーの構成の一例を示すブロック図である。
【００６４】
図３（ａ）のＣＬＡ２１では、４桁の２進数値であるＡ（０）〜Ａ（３）とＢ（０）〜Ｂ（３）の加算が実施される。たとえば、Ａ（３）およびＢ（３）が入力される部分では、以下の回路が必要になる。
【００６５】
回路１．：Ａ（３）およびＢ（３）の加算結果のみで桁上げ信号が発生される場合を検出する２入力ＡＮＤ回路。
【００６６】
回路２．：Ａ（２）およびＢ（２）の加算結果と、Ａ（３）およびＢ（３）の中間桁上げ信号により桁上げ信号が発生する場合を検出する２入力ＡＮＤ回路。
【００６７】
回路３．：Ａ（１）およびＢ（１）の加算結果と、Ａ（２）およびＢ（２）の中間桁上げ信号と、Ａ（３）およびＢ（３）の中間桁上げ信号により桁上げ信号が発生する場合を検出する３入力ＡＮＤ回路。
【００６８】
回路４．：Ａ（０）およびＢ（０）の加算結果と、Ａ（１）およびＢ（１）の中間桁上げ信号と、Ａ（２）およびＢ（２）の中間桁上げ信号と、Ａ（３）およびＢ（３）の中間桁上げ信号により桁上げ信号が発生する場合を検出する４入力ＡＮＤ回路。
【００６９】
回路５．：下位桁からの桁上げ信号ＣＩと、Ａ（０）およびＢ（０）の中間桁上げ信号と、Ａ（１）およびＢ（１）の中間桁上げ信号と、Ａ（２）およびＢ（２）の中間桁上げ信号と、Ａ（３）およびＢ（３）の中間桁上げ信号により桁上げ信号が発生する場合を検出する５入力ＡＮＤ回路。
【００７０】
回路６．：上記各ＡＮＤ回路のいずれか１入力があった時に桁上げ出力を発生させる５入力ＯＲ回路。
【００７１】
また、図３（ａ）のキャリールックアヘッド型アダー２１のクリティカルパスとしては、例えば、２入力ＯＲ回路２２、５入力ＡＮＤ回路２３、及び、５入力ＯＲ回路の経路となり、２入力回路の遅延時間を０．５ｄｅｌとしたときの遅延時間は、３．５ｄｅｌ又は３．０ｄｅｌとなる。
【００７２】
キャリールックアヘッド型アダー２１は、上記のように全ての下位桁の中間桁上げ信号と全ての下位桁のＡＮＤ回路の出力を利用して各桁の桁上がりを演算により予測することができるので、下位の各桁の桁上げ出力を待つ必要が無くなり、遅延時間を減少させることができると言う利点を有する一方で、上位の桁になるほど桁上がりの予測を実施するための入力数が増加して回路規模が増大し回路が複雑化するという問題を有している。そのため、４桁程度までの加算には適しているが、それ以上の桁数の加算は回路の複雑化と回路規模の増大の点から好ましくない。そのため、例えば、１２桁の２進数を加算するためには、４桁の加算が可能なＣＬＡ２１を桁上げ出力方向に直列に３段接続したアダーが用いられる。
【００７３】
図３（ｂ）は、図３（ａ）に示したＣＬＡ２１を植列に３段接続したアダーの構成を示すブロック図である。
【００７４】
初段のＣＬＡ３１は、Ａ（０）〜Ａ（３）及びＢ（０）〜Ｂ（３）が入力される。下位桁からの桁上げ信号ＣＩの入力が無いため、クリティカルパスのＡＮＤ回路およびＯＲ回路は４入力となるので、クリティカルパスの遅延時間は２．５ｄｅｌとなる。
【００７５】
２段目のＣＬＡ３２は、Ａ（４）〜Ａ（７）及びＢ（４）〜Ｂ（７）が入力される。下位桁からの桁上げ信号ＣＩとなるＣＬＡ３１からの出力が入力されるため、クリティカルパスのＡＮＤ回路およびＯＲ回路は５入力となり、クリティカルパスの遅延時間は３．０ｄｅｌとなる。ＣＬＡ３１〜ＣＬＡ３２までのトータルの遅延時間は、５．５ｄｅｌとなる。
【００７６】
３段目のＣＬＡ３３は、Ａ（８）〜Ａ（１１）及びＢ（８）〜Ｂ（１１）が入力される。下位桁からの桁上げ信号ＣＩとなるＣＬＡ３２からの出力が入力されるため、クリティカルパスのＡＮＤ回路およびＯＲ回路は５入力となり、クリティカルパスの遅延時間は３．０ｄｅｌとなる。ＣＬＡ３１〜ＣＬＡ３３までのトータルの遅延時間は、８．５ｄｅｌとなる。
【００７７】
以上のように、キャリールックアヘッド型アダー２１を用いる場合、８桁の加算では５．５ｄｅｌの遅延時間が発生し、１２桁の加算では８．５ｄｅｌの遅延時間が発生することから、１６桁の加算ではさらに３．０ｄｅｌ追加されて１１．５ｄｅｌの遅延時間となる。すなわち、加算数値の桁数が４桁増加する毎に３．０ｄｅｌずつ遅延時間が増加する。
【００７８】
ここでは、上記の５入力ＡＮＤ回路及びＯＲ回路が１．５ｄｅｌとしており、以下にその理由を説明するが、５入力ＡＮＤ回路およびＯＲ回路、あるいはその他の回路の遅延時間はＬＳＩの種類等によって異なってくるものであるため、単純ではない、従って、５入力ＡＮＤおよびＯＲ回路は１．０ｄｅｌ程度で済む場合もある。
【００７９】
ただし、２入力ＡＮＤ回路よりも３入力ＡＮＤ回路の方が遅延時間が大きく、３入力ＡＮＤ回路よりも４入力ＡＮＤ回路の方が遅延時間が大きく、４入力ＡＮＤ回路よりも５入力ＡＮＤ回路の方が遅延時間が大きいというように、ＡＮＤ回路の入力数が多くなれば遅延時間も多くなるということは不変である。
【００８０】
このＬＳＩの種類等の違いによる５入力ＡＮＤ回路およびＯＲ回路の遅延時間の差、あるいは、その他の回路の遅延時間の差によって、本発明における桁数の大きい加算器における優位性が失われることはないので、以下の説明では、５入力ＡＮＤ加算器およびＯＲ回路の遅延時間が１．５ｄｅｌであることとして説明を行う。
【００８１】
図４（ａ）は、５入力ＡＮＤ回路を１素子で表した図であり、図４（ｂ）は、２入力ＡＮＤ素子を４個組み合わせて５入力ＡＮＤ回路を表した図である。
【００８２】
図面上で図４（ａ）に示すような５入力ＡＮＤ回路として表される回路は、２入力のＡＮＤ回路を組み合わせて図４（ｂ）に示したような回路となる。図４（ｂ）に示したように、２入力ＡＮＤ素子の遅延時間を０．５ｄｅｌとすると、５入力ＡＮＤ素子のクリティカルパスは、１．５ｄｅｌとなることがわかる。
【００８３】
図５は、図１（ａ）に示した４桁の２進数値を加算する際の桁上げ出力回路１００に、加算結果を出力する回路を追加した２進数加算回路の構成を示すブロック図である。
【００８４】
図５（ａ）の２進数加算回路１００ａにおいて、加算回路であるＸａｄｄ４１は、Ａ（０）〜Ａ（１）およびＢ（０）〜Ｂ（１）が入力されて、中間桁上げ信号ＬＣおよび加算出力Ｓ（０）〜Ｓ（１）を出力する。Ｘａｄｄ４１は、図１（ｂ）に示したＬＣＡ１５１の構成を一部に有していれば、リップルキャリ型アダーでも、キャリルックアヘッド型アダーでも良い。同様にして、加算回路であるＸａｄｄ＋４２は、Ａ（２）〜Ａ（３）およびＢ（２）〜Ｂ（３）が入力されて、全１信号ＡＬ１および各桁の加算結果にさらに１を加算した加算出力Ｓ（２）〜Ｓ（３）を出力する。Ｘａｄｄ＋４２も、図１（ｃ）に示したＨＡＬ（１）１５２の構成を一部に有していれば、リップルキャリ型アダーでも、キャリルックアヘッド型アダーでも良い。また、加算回路であるＸａｄｄ４３は、Ａ（２）〜Ａ（３）およびＢ（２）〜Ｂ（３）が入力されて、中間桁上げ信号ＩＣＯ２および加算出力Ｓ（２）〜Ｓ（３）を出力する。Ｘａｄｄ４３も、図１（ｄ）に示したＨＣＡ１５３の構成を一部に有していれば、リップルキャリ型アダーでも、キャリルックアヘッド型アダーでも良い。マルチプレクサ（ＭＵＸ）４６は、Ｘａｄｄ４１の出力ＬＣにより、Ｘａｄｄ＋４２からのＳ（２）およびＳ（３）出力と、Ｘａｄｄ４３からのＳ（２）およびＳ（３）出力とから一方を選択して出力する。
【００８５】
例えば、Ｘａｄｄ４１、Ｘａｄｄ＋４２、および、Ｘａｄｄ４３がキャリルックアヘッド型アダーの場合には、遅延時間は３．０ｄｅｌとなるので、図３（ａ）に示した全てキャリルックアヘッド型アダーで構成した場合と同等となる。
【００８６】
図５（ｂ）は、マルチプレクサ（ＭＵＸ）４６で出力を選択するために用いられる図表である。
【００８７】
Ｘａｄｄ４１からの中間桁上げ信号ＬＣが、桁上げが無いことを示す０であれば、Ｘａｄｄ４３からの加算出力Ｓ（２）およびＳ（３）を選択し、桁上げが有ることを示す１であれば、Ｘａｄｄ＋４２からの加算出力Ｓ（２）およびＳ（３）を選択する。
【００８８】
このように、本実施形態では、４桁の加算を実施する際に、遅延時間をリップルキャリ型アダーよりも減少させることができる。また、本実施形態は、キャリルックアヘッド型アダーに対しては、遅延時間については同等レベルとなるが、回路の素子数（ゲート数）については減少させることができる。
（第２の実施形態）
上記した第１の実施形態のＬＣＡ１５１、ＨＡＬ（１）１５２、および、ＨＣＡ１５３では、各加算部への入力桁数が２桁の場合を示したが、本発明はこれに限らず、例えば、各加算部への入力桁数が４桁の場合でも適用することができる。
【００８９】
図６は、各加算部への入力桁数が４桁の場合を示す本発明の第２の実施形態の桁上げ出力回路の構成を示すブロック図である。
【００９０】
図６（ａ）の８桁の２進数値の加算を実施する際の桁上げ出力回路２１０は、下位４桁であるＡ（０）〜Ａ（３）およびＢ（０）〜Ｂ（３）が入力されて下位桁側中間桁上げ信号ＬＣを出力する下位桁側桁上げ出力回路（ＬＣＡ）２１１と、上位４桁であるＡ（４）〜Ａ（７）およびＢ（４）〜Ｂ（７）が入力されて各桁の加算結果が全て‘１’であることを検出して、各桁の加算出力が全て‘１’であることを示す全１信号ＡＬ１を出力するＨＡＬ（１）２１２と、Ａ（４）〜Ａ（７）およびＢ（４）〜Ｂ（７）が入力されて上位桁側中間桁上げ信号ＩＣＯ２を出力する上位桁側桁上げ出力回路（ＨＣＡ）２１３と、ＡＮＤ−ＯＲ回路４４とから構成される。ＡＮＤ−ＯＲ回路４４の構成は、第１の実施形態と同様である。
【００９１】
ＡＮＤ−ＯＲ回路４４のＡＮＤ入力部には、ＬＣＡ２１１から出力される信号ＬＣおよびＨＡＬ（１）２１２から出力される信号ＡＬ１が入力され、ＡＮＤ−ＯＲ回路４４のＯＲ入力部には、ＨＣＡ２１３から出力される信号ＩＣＯ２が入力される。即ち、下位４桁の加算部であるＬＣＡ２１１の桁上げ出力が‘１’であることから下位桁側中間桁上げ信号ＬＣが出力される場合で、且つ、上位４桁の加算結果が全て‘１’であることを示すＡＬ１が出力される場合か、あるいは、上位４桁の桁上げ出力が‘１’となる上位桁側中間桁上げ信号ＩＣＯ２が出力される場合に桁上げ信号８ＣＯが出力される。
【００９２】
換言すると、本実施形態のＡＮＤ−ＯＲ回路４４では、一方では、下位４桁の加算部であるＬＣＡ２１１からの桁上げ信号ＬＣ、および、上位４桁の出力が全て１であることを検出するＨＡＬ２１２からの全１信号ＡＬ１をＡＮＤ演算することにより、下位４桁の加算部からの桁上げにより上位４桁からの桁上げがあるか否かを判断し、他方では、上位４桁の加算部であるＨＣＡ２１３からの桁上げ信号ＩＣＯ２により、上位４桁の加算部であるＨＣＡ２１３のみによる桁上げがあるか否かを判断する。
【００９３】
図６（ｂ）は、図６（ａ）中のＬＣＡ２１１およびＨＣＡ２１３の内部構成を示すブロック図である。
【００９４】
ＬＣＡ２１１およびＨＣＡ２１３の内部構成は、中間桁上げ信号を出力できる構成を有していれば、リップルキャリ型アダーでも、キャリルックアヘッド型アダーでも良い。図６（ｂ）には、キャリルックアヘッド型アダーの場合を示した。ＬＣＡ２１１およびＨＣＡ２１３のクリティカルパスの遅延時間は、２．５ｄｅｌとなる。
【００９５】
図６（ｃ）は、図６（ａ）中のＨＡＬ（１）の内部構成を示すブロック図である。
【００９６】
ＨＡＬ（１）２１２の内部には、２入力のＯＲ回路が４個と、４入力のＡＮＤ回路が１個設置されている。各ＯＲ回路には、加算される４桁の２進数値Ａ，Ｂの各桁値が入力されて、何れかの入力が１である場合に１が出力される。ＡＮＤ回路には、各ＯＲ回路からの出力が入力されて、全ての入力が１である場合に上位桁側の全桁の値が１であることを示す全１信号ＡＬ１が出力される。ＨＡＬ（１）２１２のクリティカルパスの遅延時間は、１．５ｄｅｌとなる。
【００９７】
従って、図６（ａ）の桁上げ出力回路２１０におけるクリティカルパスの遅延時間は、３．５ｄｅｌとなるので、図３（ｂ）に示したようにキャリルックアヘッド型アダーを直列に構成する場合の５．５ｄｅｌよりも遅延時間を短縮させることができる。
（第３の実施形態）
また、本発明では、例えば、複数個の第１の実施形態の加算回路を階層構造となるように用いて、２倍桁の加算回路を構成させることができる。
【００９８】
図７は、図５（ａ）に示した第１の実施形態の複数個の加算回路を階層構造となるように用いた第３の実施形態の加算回路の構成を示すブロック図である。
【００９９】
図７の加算回路２５０は、図５（ａ）に示した４桁の加算回路１００ａの２倍桁となる８桁の加算回路である。下位４桁の加算部としては、図５（ａ）と同様な４桁の加算回路１０１ａが用いられる。上位４桁の加算部と、全１信号を出力する回路は、図５（ａ）に示した４桁の加算回路１００ａと同様な構成を有する回路を用いることもできるが、全１信号を出力する回路で必要となる部分のみを残し、上位４桁の加算部と全１信号を出力する回路とで共通する回路となるＸａｄｄ＋４２およびＸａｄｄ４３を統合することにより回路を簡略化することができる。このように全１信号を出力する回路を統合した上位４桁の加算部をＳＢ４ＢＢ＋１０５とする。
【０１００】
加算回路２５０は、上位４桁の加算出力のうちの下位２桁を、ＳＢ４ＢＢ＋１０５中のＸａｄｄ＋４１ａの出力と、Ｘａｄｄ４１の出力とから、加算回路１０１ａからの出力４ＣＯ１を用いて選択するためにマルチプレクサ２９３が設けられる。また、上位４桁の加算出力のうちの上位２桁を、ＳＢ４ＢＢ＋１０５中のＸａｄｄ＋４２の出力と、Ｘａｄｄ４３の出力とから選択するためにマルチプレクサ２９４が設けられる。マルチプレクサ２９４の出力を選択するためには、アンド−オア回路２９２が設けられる。アンド−オア回路２９２は、加算回路１０１ａからの出力４ＣＯ１と、Ｘａｄｄ＋４１ａの出力とが入力されるＡＮＤ回路２９２ａと、ＡＮＤ回路２９２ａの出力と、Ｘａｄｄ４１の出力とが入力されるＯＲ回路２９２ｂとが直列に接続される。出力４ＣＯ１が１の時に、Ｘａｄｄ＋４２から出力されるＳ（６）〜Ｓ（７）が選択され、出力４ＣＯ１が０の時に、Ｘａｄｄ４３から出力されるＳ（６）〜Ｓ（７）が選択される。
【０１０１】
また、加算回路２５０は、加算回路１０１ａからの中間桁上げ信号である出力４ＣＯ１と、ＳＢ４ＢＢ＋１０５からの全１信号である４ＣＯ２とが入力されるＡＮＤ回路と、そのＡＮＤ回路の出力と、ＳＢ４ＢＢ＋１０５からの桁上げ信号である出力４ＣＯ３とが入力されて桁上げ信号８ＣＯが出力されるＯＲ回路が直列に接続されたＡＮＤ−ＯＲ回路２９１を有している。
【０１０２】
このようにして、本実施形態では、８桁の２進数の加算を実施することができ、クリティカルパスの遅延時間は、４桁の加算時よりも、ＡＮＤ−ＯＲ回路２９１で遅延する１．０ｄｅｌだけ増加するので３．０ｄｅｌとなる。つまり、４桁の加算が、２倍の８桁の加算になっても、クリティカルパスの遅延時間が１．０ｄｅｌしか増加しないことがわかる。
（第４の実施形態）
上記から、図７の加算回路２５０を複数個用いて、さらに２倍の１６桁の加算回路を階層構造となるように構成しても、クリティカルパスの遅延時間は１．０ｄｅｌだけしか増加しないことが予想できる。
【０１０３】
図８は、図７に示した第３の実施形態の複数個の加算回路を階層構造となるように用いた第４の実施形態の加算回路の構成を示すブロック図である。
【０１０４】
図８の加算回路７００ｄは、図７に示した８桁の加算回路２５０の２倍桁となる１６桁の加算回路である。下位８桁の加算部としては、図７と同様な８桁の加算回路７５１ｄが用いられる。上位８桁の加算部としても、図７と同様な８桁の加算回路７５１ｃが用いられる。全１信号を出力する回路としては、図７に示した８桁の加算回路２５０と同様な構成を有する回路を用いることもできるが、全１信号を出力する回路で必要となる部分のみでよいので、加算回路Ｘａｄｄ＋７９３と、ＡＮＤ回路７９４、および、ＡＮＤ回路７９５のみの全１信号出力回路７５５とした。この全１信号出力回路７５５と、加算回路７５１ｃとは、８桁の加算回路２５０の場合のように統合した回路としても良い。
【０１０５】
加算出力については、上位８桁のうち最下位から２桁を選択するマルチプレクサ７８３と、上位８桁のうち最下位から数えて３桁目と４桁目を選択するマルチプレクサ７８４と、上位８桁のうち最上位から数えて３桁目と４桁目を選択するマルチプレクサ７９７と、上位８桁のうち最上位から２桁を選択するマルチプレクサ７９９とが追加される。マルチプレクサ７８３は、加算回路７５１ｄの出力８ＣＯ１により選択する。マルチプレクサ７８４は、加算回路７５１ｄの出力８ＣＯ１とＸａｄｄ＋７９３の出力と４桁の加算回路７６１からの出力によりＡＮＤ−ＯＲ回路７８５を用いて選択する。マルチプレクサ７９７は、加算回路７５１ｄの出力８ＣＯ１とＡＮＤ回路７９４の出力と４桁の加算回路７６１の出力によりＡＮＤ−ＯＲ回路７９６を用いて選択する。
【０１０６】
マルチプレクサ７９９は、加算回路７５１ｄの出力８ＣＯ１とＡＮＤ回路７９４の出力と４桁の加算回路７６１からの出力とにより、ＡＮＤ回路７８６，ＡＮＤ−ＯＲ回路７８７およびＡＮＤ−ＯＲ回路７９８を用いて選択する。
【０１０７】
また、加算回路７００ｄは、加算回路７５１ｄからの中間桁上げ信号である出力８ＣＯ１と、全１信号出力回路７５５からの全１信号である８ＣＯ２とが入力されるＡＮＤ回路と、そのＡＮＤ回路の出力と、加算回路７５１ｃからの桁上げ信号である出力８ＣＯ３とが入力されて桁上げ信号１６ＣＯが出力されるＯＲ回路が直列に接続されたＡＮＤ−ＯＲ回路７９１を有している。
【０１０８】
このようにして、本実施形態では、１６桁の２進数の加算を実施することができ、クリティカルパスの遅延時間は、８桁の加算時よりも、ＡＮＤ−ＯＲ回路７９１で遅延する１．０ｄｅｌだけ増加するので４．０ｄｅｌとなる。つまり、８桁の加算が、２倍の１６桁の加算になっても、クリティカルパスの遅延時間が１．０ｄｅｌしか増加しないことになる。このことから、図７の加算回路２５０を複数個用いて、さらに２倍の１６桁の加算回路を階層構造となるように構成しても、クリティカルパスの遅延時間は１．０ｄｅｌだけしか増加しないことが確認できる。
（第５の実施形態）
また、同様にして、図８の加算回路７００ｄを複数個用いて、さらに２倍の３２桁の加算回路を階層構造となるように構成しても、クリティカルパスの遅延時間は１．０ｄｅｌだけしか増加しないことが予想できる。
【０１０９】
図９は、図８に示した第４の実施形態の複数個の加算回路を階層構造となるように用いた第５の実施形態の加算回路の構成を示すブロック図である。
【０１１０】
図９の加算回路８００ｄは、図８に示した１６桁の加算回路７００ｄの２倍桁となる３２桁の加算回路である。下位１６桁の加算部としては、図８と同様な１６桁の加算回路７００ｄが用いられる。上位１６桁の加算部としても、図８と同様な１６桁の加算回路７００ｃが用いられる。全１信号を出力する回路としては、図８に示した１６桁の加算回路７００ｄと同様な構成を有する回路を用いることもできるが、全１信号を出力する回路で必要となる部分のみでよいので、加算回路と、複数のＡＮＤ回路のみからなる全１信号出力回路８５５とした。この全１信号出力回路８５５と、加算回路７００ｃとは、８桁の加算回路２５０の場合のように統合した回路としても良い。
【０１１１】
加算出力については、上位１６桁のうち最下位から各２桁を選択する複数のマルチプレクサを追加し、各桁毎に、ＡＮＤ−ＯＲ回路およびＡＮＤ回路を必要に応じて使用して選択する。
【０１１２】
また、加算回路８００ｄは、加算回路７００ｄからの中間桁上げ信号である出力１６ＣＯ１と、全１信号出力回路８５５からの全１信号である１６ＣＯ２とが入力されるＡＮＤ回路と、そのＡＮＤ回路の出力と、加算回路７００ｃからの桁上げ信号である出力１６ＣＯ３とが入力されて桁上げ信号３２ＣＯが出力されるＯＲ回路が直列に接続されたＡＮＤ−ＯＲ回路８９１を有している。
【０１１３】
図１０は、上記した図５、図７〜図９の加算回路では、加算回路の桁数を２倍にした場合にクリティカルパスの遅延時間が１個のＡＮＤ−ＯＲ回路の遅延時間分である１．０ｄｅｌずつ増加することを視覚的に示した図である。
【０１１４】
図１０に示したように、本実施形態では４桁の加算回路を２倍の８桁の加算回路にし、さらに２倍にすることを繰り返して１６桁および３２桁の加算回路にしても、クリティカルパスの遅延時間は、桁数２倍毎に１．０ｄｅｌしか増加しないことが確認できるので、例えば、さらに２倍の６４桁の加算回路を階層構造となるように構成した場合、３２桁の加算回路よりもクリティカルパスで１．０ｄｅｌのみ遅延時間が増加するだけとなる。同様に、１２８桁の加算回路を階層構造となるように構成しても、クリティカルパスの遅延時間は６４桁から１．０ｄｅｌしか増加しないことになる。
【０１１５】
具体的には、図５（ａ）の４桁の加算回路１００ａのクリティカルパスの遅延時間が３．０ｄｅｌとすると、図７の８桁の加算回路２５０のクリティカルパスの遅延時間が４．０ｄｅｌとなり、図８の１６桁の加算回路７００ｄのクリティカルパスの遅延時間が５．０ｄｅｌとなり、図９の３２桁の加算回路８００ｄのクリティカルパスの遅延時間が６．０ｄｅｌとなる。
【０１１６】
それに対し、例えば、リップルキャリ型アダーでは、図４１（ｂ）に示したように８桁の加算回路でもクリティカルパスの遅延時間は８．０ｄｅｌとなる。また、図３（ｂ）のキャリルックアヘッド型アダーを多段に接続した加算器では、８桁の加算回路におけるクリティカルパスの遅延時間は５．５ｄｅｌであり、１６桁にすると、３．０ｄｅｌ＋３．０ｄｅｌが加算されるので、１１．５ｄｅｌとなってしまう。
【０１１７】
このようにして、本実施形態では、３２桁の２進数の加算を実施することができ、クリティカルパスの遅延時間は、１６桁の加算時よりも、ＡＮＤ−ＯＲ回路８９１で遅延する１．０ｄｅｌだけ増加するので５．０ｄｅｌとなる。つまり、１６桁の加算が、２倍の３２桁の加算になっても、クリティカルパスの遅延時間が１．０ｄｅｌしか増加しないことになる。このことから、図８の加算回路７００ｄを複数個用いて、さらに２倍の３２桁の加算回路を階層構造となるように構成しても、クリティカルパスの遅延時間は１．０ｄｅｌだけしか増加しないことが確認できる。従って、本実施形態では、桁数を増加させた場合であっても、クリティカルパスの遅延時間の増加を最小限に抑えることができる。
（第６の実施形態）
上記した各実施形態は、加算する数値を上下に２分割した場合の下位の桁と上位の桁が各々２の倍数となる場合についての実施形態であった。しかし、加算する数値によっては、上下に２分割した場合の下位の桁と上位の桁が各々３の倍数となる場合も考えられる。
【０１１８】
図１１は、各加算部への入力桁数が３桁の場合を示す本発明の第６の実施形態の桁上げ出力回路の構成を示すブロック図である。
【０１１９】
図１１（ａ）の６桁の２進数値の加算を実施する際の桁上げ出力回路２００は、下位３桁であるＡ（０）〜Ａ（２）およびＢ（０）〜Ｂ（２）が入力されて下位桁側中間桁上げ信号ＬＣを出力する下位桁側桁上げ出力回路（ＬＣＡ）５１と、上位３桁であるＡ（３）〜Ａ（５）およびＢ（３）〜Ｂ（５）が入力されて各桁の加算結果が全て‘１’であることを検出して、各桁の加算出力が全て‘１’であることを示す全１信号ＡＬ１を出力するＨＡＬ（１）５２と、Ａ（３）〜Ａ（５）およびＢ（３）〜Ｂ（５）が入力されて上位桁側中間桁上げ信号ＩＣＯ２を出力する上位桁側桁上げ出力回路（ＨＣＡ）５３と、ＡＮＤ−ＯＲ回路４４とから構成される。ＡＮＤ−ＯＲ回路４４の構成は、第１の実施形態あるいは第２の実施形態と同様である。
【０１２０】
ＡＮＤ−ＯＲ回路４４のＡＮＤ入力部４４ａには、ＬＣＡ５１から出力される信号ＬＣおよびＨＡＬ（１）５２から出力される信号ＡＬ１が入力され、ＡＮＤ−ＯＲ回路４４のＯＲ入力部には、ＨＣＡ５３から出力される信号ＩＣＯ２が入力される。即ち、下位３桁の加算部であるＬＣＡ５１の桁上げ出力が‘１’であることから下位桁側中間桁上げ信号ＬＣが出力される場合で、且つ、上位３桁の加算結果が全て‘１’であることを示すＡＬ１が出力される場合か、あるいは、上位３桁の桁上げ出力が‘１’となる上位桁側中間桁上げ信号ＩＣＯ２が出力される場合に桁上げ信号６ＣＯが出力される。
【０１２１】
換言すると、本実施形態のＡＮＤ−ＯＲ回路４４では、一方では、下位３桁の加算部であるＬＣＡ５１からの桁上げ信号ＬＣ、および、上位３桁の出力が全て１であることを検出するＨＡＬ５２からの全１信号ＡＬ１をＡＮＤ演算することにより、下位３桁の加算部からの桁上げにより上位３桁からの桁上げがあるか否かを判断し、他方では、上位３桁の加算部であるＨＣＡ５３からの桁上げ信号ＩＣＯ２により、上位３桁の加算部であるＨＣＡ５３のみによる桁上げがあるか否かを判断する。
【０１２２】
図１１（ｂ）は、図１１（ａ）中のＬＣＡ５１およびＨＣＡ５３の内部構成を示すブロック図である。
【０１２３】
ＬＣＡ５１およびＨＣＡ５３の内部構成は、中間桁上げ信号を出力できる構成を有していれば、リップルキャリ型アダーでも、キャリルックアヘッド型アダーでも良い。図１１（ｂ）には、キャリルックアヘッド型アダーの場合を示した。ＬＣＡ５１およびＨＣＡ５３のクリティカルパスの遅延時間は、２．０ｄｅｌとなる。なお、ここでは、簡易的に３入力ＡＮＤ回路は１．０ｄｅｌ、３入力ＯＲ回路は０．５ｄｅｌとして計算している。これらの遅延時間はＬＳＩの種類等によって異なるが、前述したように、このことにより本発明の優位性が損なわれるものではない。
【０１２４】
図１１（ｃ）は、図１１（ａ）中のＨＡＬ（１）の内部構成を示すブロック図である。
【０１２５】
ＨＡＬ（１）５２の内部には、２入力のＯＲ回路が３個と、３入力のＡＮＤ回路が１個設置されている。各ＯＲ回路には、加算される３桁の２進数値Ａ，Ｂの各桁値が入力されて、何れかの入力が１である場合に１が出力される。ＡＮＤ回路には、各ＯＲ回路からの出力が入力されて、全ての入力が１である場合に上位桁側の全桁の値が１であることを示す全１信号ＡＬ１が出力される。ＨＡＬ（１）５２のクリティカルパスの遅延時間は、１．５ｄｅｌとなる。
【０１２６】
従って、図１１（ａ）の桁上げ出力回路２００におけるクリティカルパスの遅延時間は、３．０ｄｅｌとなる。
【０１２７】
図１２は、図１１（ａ）に示した６桁の２進数値を加算する際の桁上げ出力回路２００に、加算結果を出力する回路を追加した２進数加算回路の構成を示すブロック図である。
【０１２８】
図１２（ａ）の２進数加算回路２００ａにおいて、加算回路であるＸａｄｄ６１は、Ａ（０）〜Ａ（２）およびＢ（０）〜Ｂ（２）が入力されて、中間桁上げ信号ＬＣおよび加算出力Ｓ（０）〜Ｓ（２）を出力する。Ｘａｄｄ６１は、図１１（ｂ）に示したＬＣＡ５１の構成を一部に有していれば、リップルキャリ型アダーでも、キャリルックアヘッド型アダーでも良い。同様にして、加算回路であるＸａｄｄ＋６２は、Ａ（３）〜Ａ（５）およびＢ（３）〜Ｂ（５）が入力されて、全１信号ＡＬ１および各桁の加算結果にさらに１を加算した加算出力Ｓ（３）〜Ｓ（５）を出力する。Ｘａｄｄ＋６２も、図１１（ｃ）に示したＨＡＬ（１）５２の構成を一部に有していれば、リップルキャリ型アダーでも、キャリルックアヘッド型アダーでも良い。また、加算回路であるＸａｄｄ６３は、Ａ（３）〜Ａ（５）およびＢ（３）〜Ｂ（５）が入力されて、中間桁上げ信号ＩＣＯ２および加算出力Ｓ（３）〜Ｓ（５）を出力する。Ｘａｄｄ６３も、図１１（ｂ）に示したＨＣＡ５３の構成を一部に有していれば、リップルキャリ型アダーでも、キャリルックアヘッド型アダーでも良い。マルチプレクサ（ＭＵＸ）６５は、Ｘａｄｄ６１の出力ＬＣにより、Ｘａｄｄ＋６２からのＳ（３）〜Ｓ（５）出力と、Ｘａｄｄ４３からのＳ（３）〜Ｓ（５）出力とから一方を選択して出力する。
【０１２９】
例えば、Ｘａｄｄ６１、Ｘａｄｄ＋６２、および、Ｘａｄｄ６３がキャリルックアヘッド型アダーの場合には、遅延時間は３．５ｄｅｌとなる。
【０１３０】
図１２（ｂ）は、マルチプレクサ（ＭＵＸ）６５で出力を選択するために用いられる図表である。
【０１３１】
Ｘａｄｄ６１からの中間桁上げ信号ＬＣが、桁上げが無いことを示す０であれば、Ｘａｄｄ６３からの加算出力Ｓ（３）〜Ｓ（５）を選択し、桁上げが有ることを示す１であれば、Ｘａｄｄ＋６２からの加算出力Ｓ（３）〜Ｓ（５）を選択する。
【０１３２】
このように、本実施形態では、６桁の加算を実施する際に、遅延時間を図４１（ｂ）に示したリップルキャリ型アダーよりも減少させることができる。また、本実施形態は、キャリルックアヘッド型アダーに対しては、遅延時間については同等レベルとなるが、回路の素子数（ゲート数）については減少させることができる。
（第７の実施形態）
また、第３の実施形態と同様に、複数個の第６の実施形態の加算回路を階層構造となるように用いて、２倍桁の加算回路を構成させることができる。
【０１３３】
図１３は、図１１（ａ）に示した第６の実施形態の複数個の桁上げ出力回路を階層構造となるように用いた第７の実施形態の桁上げ出力回路の構成を示すブロック図である。
【０１３４】
図１３の桁上げ出力回路４００は、図１１（ａ）に示した６桁の桁上げ出力回路２００の２倍桁となる１２桁の桁上げ出力回路である。下位６桁の桁上げ出力部としては、図１１（ａ）と同様な６桁の桁上げ出力回路２０１が用いられる。上位６桁の桁上げ出力回路と、全１信号を出力する回路には、図１１（ａ）に示した６桁の桁上げ出力回路２００と同様な構成を有する桁上げ出力回路２０２および２０３を用いる。桁上げ出力回路２０２は、図１５を用いて次の実施形態で後述するように、全１信号を出力する回路で必要となる部分のみを残すようにして、例えば、下位桁側桁上げ出力＋１の回路であるＬＣＡ＋５１ａを下位桁側全１検出回路ＬＡＬ（１）としてもよい。さらに、上位６桁の桁上げ出力回路２０３と桁上げ出力回路２０２とで共通する回路となるＨＡＬ（１）５２およびＨＣＡ５３を統合することにより回路を簡略化することができるが、本実施形態では、桁上げ出力回路２００の構成をそのまま用いて桁上げ出力回路２０２とする。また、桁上げ出力回路４００は、ＡＮＤ−ＯＲ回路９１を備える。ＡＮＤ−ＯＲ回路９１の構成は、第１の実施形態あるいは第３の実施形態等と同様である。
【０１３５】
ＡＮＤ−ＯＲ回路９１のＡＮＤ入力部９１ａには、桁上げ出力回路２０１から出力される中間桁上げ信号６ＣＯ１、および、桁上げ出力回路２０２から出力される中間桁上げ信号６ＣＯ２が入力され、ＡＮＤ−ＯＲ回路９１のＯＲ入力部９１ｂには、桁上げ出力回路２０３から出力される中間桁上げ信号６ＣＯ３が入力される。即ち、下位６桁の加算部である桁上げ出力回路２０１の桁上げ出力が‘１’であることから下位桁側中間桁上げ信号として６ＣＯ１が出力される場合で、且つ、６ＣＯ２が出力される場合か、あるいは、上位６桁の桁上げ出力が‘１’となる上位桁側中間桁上げ信号６ＣＯ３が出力される場合に桁上げ信号１２ＣＯが出力される。
【０１３６】
換言すると、本実施形態のＡＮＤ−ＯＲ回路９１では、一方では、下位６桁の加算部である桁上げ出力回路２０１からの桁上げ信号６ＣＯ１、および、桁上げ出力回路２０２からの中間桁上げ信号６ＣＯ２をＡＮＤ演算することにより、下位６桁の加算部からの桁上げにより上位６桁からの桁上げがあるか否かを判断し、他方では、上位６桁の加算部である桁上げ出力回路２０３からの桁上げ信号６ＣＯ３により、上位６桁の加算部である桁上げ出力回路２０３のみによる桁上げがあるか否かを判断する。
【０１３７】
図１４は、図１３に示した１２桁の２進数値を加算する際の桁上げ出力回路４００に、加算結果を出力する回路を追加した２進数加算回路の構成を示すブロック図である。
【０１３８】
図１４の２進数加算回路４００ａにおいて、６桁の加算回路２０１ａは、Ａ（０）〜Ａ（５）およびＢ（０）〜Ｂ（５）が入力されて、中間桁上げ信号６ＣＯ１および加算出力Ｓ（０）〜Ｓ（５）を出力する。加算回路２０２ａは、Ａ（６）〜Ａ（１１）およびＢ（６）〜Ｂ（１１）が入力されて、中間桁上げ信号６ＣＯ２および加算結果に１を加えた加算出力Ｓ（６）〜Ｓ（１１）を出力する。加算回路２０３ａは、Ａ（６）〜Ａ（１１）およびＢ（６）〜Ｂ（１１）が入力されて、中間桁上げ信号６ＣＯ３および加算出力Ｓ（６）〜Ｓ（１１）を出力する。
また、上記した加算回路としては、リップルキャリ型アダーでも、キャリルックアヘッド型アダーでも良い。マルチプレクサ（ＭＵＸ）９２は、加算回路２０１ａの出力６ＣＯ１により、加算回路２０２ａからのＳ（６）〜Ｓ（１１）出力と、加算回路２０３ａからのＳ（６）〜Ｓ（１１）出力とから一方を選択して出力する。
【０１３９】
本実施形態では、例えば、加算回路２０１ａ、加算回路２０２ａ、および、加算回路２０３ａがキャリルックアヘッド型アダーの場合には、クリティカルパスの遅延時間は４．５ｄｅｌとなるので、図３（ｂ）に示した全てキャリルックアヘッド型アダーで構成した場合の８．５ｄｅｌよりもクリティカルパスの遅延時間を減少させることができる。
（第８の実施形態）
上記した第７の実施形態では、６桁の桁上げ出力回路あるいは６桁の加算回路を複数個用いて階層的に回路を構成することにより、１２桁の桁上げ出力回路あるいは１２桁の加算回路を構成でき、それらによるクリティカルパスの遅延時間の増加量が少ないことを示した。第７の実施形態では、使用回路の標準化のために同様な回路を使用できることが示されたが、桁上げ出力回路あるいは加算回路については、必要な回路のみとして素子数（ゲート数）を減少させることもできる。
【０１４０】
図１５は、図１３の桁上げ出力回路を簡略化した第８の実施形態の桁上げ出力回路の構成を示すブロック図である。
【０１４１】
図１５の桁上げ出力回路４００ｃでは、図１３の桁上げ出力回路２０２から、全１信号を出力する回路で必要となる部分のみを残すようにして、さらに、その全１出力回路と、上位６桁の桁上げ出力回路２０３とで共通する回路となるＨＡＬ（１）５２およびＨＣＡ５３を統合することにより回路を簡略化している。
【０１４２】
図１６は、図１４の加算回路を簡略化した加算回路の構成を示すブロック図である。
【０１４３】
図１６の加算回路４００ｄでは、図１４の加算回路２０２ａから、全１信号を出力する回路で必要となる部分のみを残すようにして、さらに、その全１出力回路と、上位６桁の桁上げ出力回路２０３ａとで共通する回路となるＸａｄｄ＋６２およびＸａｄｄ６３を統合することにより回路を簡略化している。
【０１４４】
このように、本実施形態では、１２桁の加算を実施する際に、上記した第７の実施形態に示したクリティカルパスの遅延時間を減少させることができることに加えて、回路の素子数（ゲート数）を減少させることができる。
（第９の実施形態）
上記した第７および第８の実施形態では、１２桁の桁上げ出力回路あるいは加算回路として、６桁の桁上げ出力回路あるいは加算回路を複数個用いて階層的に回路を構成したが、例えば、３桁の桁上げ出力回路や３桁の加算回路を用いて、６桁の回路を作らずに１２桁の桁上げ出力回路あるいは加算回路を構成することができる。
【０１４５】
図１７は、３桁の桁上げ出力回路を用いて構成した第９の実施形態の１２桁の桁上げ出力回路の構成を示すブロック図である。
【０１４６】
図１７（ａ）の１２桁の２進数値の加算を実施する際の桁上げ出力回路４００ｆは、最下位３桁であるＡ（０）〜Ａ（２）およびＢ（０）〜Ｂ（２）が入力されて最下位桁側中間桁上げ信号ＬＣを出力するＬＣＡ１１１と、最下位桁から４桁目〜６桁目のＡ（３）〜Ａ（５）およびＢ（３）〜Ｂ（５）が入力されて、中央下位桁側の各桁の加算結果が全て‘１’であることを検出して、各桁の加算出力が全て‘１’であることを示す全１信号ＭＬ１を出力するＭＬＡＬ（１）１１２と、Ａ（３）〜Ａ（５）およびＢ（３）〜Ｂ（５）が入力されて中央下位桁側中間桁上げ信号ＭＬＣを出力する中央下位桁側桁上げ出力回路ＭＬＣＡ１１３と、最上位桁から４桁目〜６桁目のＡ（６）〜Ａ（８）およびＢ（６）〜Ｂ（８）が入力されて、中央上位桁側の各桁の加算結果が全て‘１’であることを検出して、各桁の加算出力が全て‘１’であることを示す全１信号ＭＨ１を出力するＭＨＡＬ（１）１１４と、Ａ（６）〜Ａ（８）およびＢ（６）〜Ｂ（８）が入力されて中央上位桁側中間桁上げ信号ＭＨＣを出力する中央上位桁側桁上げ出力回路ＭＨＣＡ１１５と、最上位３桁であるＡ（９）〜Ａ（１１）およびＢ（９）〜Ｂ（１１）が入力されて各桁の加算結果が全て‘１’であることを検出して、各桁の加算出力が全て‘１’であることを示す全１信号ＡＬ１を出力するＨＡＬ（１）１１６と、Ａ（９）〜Ａ（１１）およびＢ（９）〜Ｂ（１１）が入力されて最上位桁側中間桁上げ信号ＩＣＯ４を出力する上位桁側桁上げ出力回路（ＨＣＡ）１１７と、ＡＮＤ回路１２０ａ、ＡＮＤ回路１２０ｂ、ＡＮＤ回路１２０ｃ、とＯＲ回路１２０ｄを一体化させたＡＮＤ−ＯＲ回路１２０とから構成される。
【０１４７】
ＡＮＤ−ＯＲ回路１２０のクリティカルパスの遅延時間は、４入力であることから１．０ｄｅｌのＡＮＤ回路１２０ａと１．０ｄｅｌのＯＲ回路１２０ｄとの和となるので２．０ｄｅｌとなる。
【０１４８】
ＡＮＤ−ＯＲ回路１２０のＡＮＤ入力部１２０ａは、ＬＣＡ１１１から出力される信号ＬＣ、ＭＬＡＬ（１）１１２から出力される信号ＭＬ１、ＭＨＡＬ（１）１１４から出力される信号ＭＨ１、および、ＨＡＬ（１）１１６から出力される信号ＡＬ１が入力されて、中間桁上げ信号ＩＣＯ１を出力する。
【０１４９】
ＡＮＤ入力部１２０ｂは、ＭＬＣＡ１１３から出力される信号ＭＬＣ、ＭＨＡＬ（１）１１４から出力される信号ＭＨ１、および、ＨＡＬ（１）１１６から出力される信号ＡＬ１が入力されて、中間桁上げ信号ＩＣＯ２を出力する。ＡＮＤ入力部１２０ｃは、ＭＨＣＡ１１５から出力される信号ＭＨＣ、および、ＨＡＬ（１）１１６から出力される信号ＡＬ１が入力されて、中間桁上げ信号ＩＣＯ３を出力する。ＡＮＤ−ＯＲ回路１２０のＯＲ入力部１２０ｄには、中間桁上げ信号ＩＣＯ１〜ＩＣＯ３と共に、ＨＣＡ１１７から出力される信号ＩＣＯ４が入力される。
【０１５０】
即ち、本実施形態のＡＮＤ−ＯＲ回路１２０は、以下の４種の場合において最上位３桁からの桁上げがあると判断して桁上げ信号１２ＣＯを出力する。
【０１５１】
場合１：最下位３桁の加算部であるＬＣＡ１１１の桁上げ出力が‘１’であることから最下位桁側中間桁上げ信号ＬＣが出力され、且つ、中央下位桁側の各桁の加算結果が全て‘１’であることを示す全１信号ＭＬ１が出力され、且つ、中央上位桁側の各桁の加算結果が全て‘１’であることを示す全１信号ＭＨ１が出力され、且つ、最上位３桁の加算結果が全て‘１’であることを示す全１信号ＡＬ１が出力される場合。
【０１５２】
場合２：中央下位桁側桁上げ出力回路ＭＬＣＡ１１３から中央下位桁側中間桁上げ信号ＭＬＣが出力され、且つ、中央上位桁側の各桁の加算結果が全て‘１’であることを示す全１信号ＭＨ１が出力され、且つ、最上位３桁の加算結果が全て‘１’であることを示す全１信号ＡＬ１が出力される場合。
【０１５３】
場合３：中央上位桁側桁上げ出力回路ＭＨＣＡ１１５から中央上位桁側中間桁上げ信号ＭＨＣが出力され、且つ、最上位３桁の加算結果が全て‘１’であることを示す全１信号ＡＬ１が出力される場合。
【０１５４】
場合４：上位桁側桁上げ出力回路ＨＣＡ１１７から最上位桁側中間桁上げ信号ＩＣＯ４が出力される場合。
【０１５５】
このようにして、本実施形態では、１２桁の２進数の桁上げ回路を複数の３桁の桁上げ回路およびＡＮＤ−ＯＲ回路により構成することができるので、６桁の桁上げ出力回路を用いて階層的に構成せずに、クリティカルパスの遅延時間（４．５ｄｅｌ）の増加量が少ない桁上げ出力回路を提供することができる。なお、図１７（ｂ）に示したように、４入力ＡＮＤおよび３入力ＡＮＤをそれぞれ２分割することにより、クリティカルパスの遅延時間を減少させることができる。
【０１５６】
図１７（ａ）では、４入力ＡＮＤ回路１２０ａの１．０ｄｅｌと４入力ＯＲ回路１２０ｄの１．０ｄｅｌとの合計である２．０ｄｅｌがクリティカルパスの遅延時間となっていたが、図１７（ｂ）では、２入力ＡＮＤ回路１２０ｅの０．５ｄｅｌと４入力ＯＲ回路１２０ｄの１．０ｄｅｌとの合計の１．５ｄｅｌをクリティカルパスの遅延時間とできるので、遅延時間を減少させることができる。この遅延時間を減少させることは、本実施形態を階層構造に適用する場合には、階層の段数毎に減少させることができるので特に有効である。
（第１０の実施形態）
第７の実施形態と同様に、複数個の第７の実施形態の加算回路を階層構造となるように用いて、２倍桁の加算回路を構成させることができる。
【０１５７】
図１８は、図１３に示した第７の実施形態の複数個の桁上げ出力回路を階層構造となるように用いた第１０の実施形態の桁上げ出力回路の構成を示すブロック図である。
【０１５８】
図１８の桁上げ出力回路５００は、図１３に示した１２桁の桁上げ出力回路４００の２倍桁となる２４桁の桁上げ出力回路である。下位１２桁の桁上げ出力部としては、図１３と同様な１２桁の桁上げ出力回路４０１が用いられる。上位１２桁の桁上げ出力回路と、中間桁上げ信号１２ＣＯ２を出力する回路には、図１３に示した１２桁の桁上げ出力回路４００と同様な構成を有する桁上げ出力回路４０２および４０３を用いる。桁上げ出力回路４０２は、図１９を用いて次の実施形態で後述するように、全１信号を出力する回路で必要となる部分のみを残すようにしても良く、さらに、上位１２桁の桁上げ出力回路４０３と桁上げ出力回路４０２とで共通する回路を統合することにより回路を簡略化することができるが、本実施形態では、桁上げ出力回路４００の構成をそのまま用いて桁上げ出力回路４０２とする。また、桁上げ出力回路５００は、ＡＮＤ−ＯＲ回路５９１を備える。ＡＮＤ−ＯＲ回路５９１の構成は、第１の実施形態あるいは第３の実施形態等と同様である。
【０１５９】
ＡＮＤ−ＯＲ回路５９１のＡＮＤ入力部５９１ａには、桁上げ出力回路４０１から出力される中間桁上げ信号１２ＣＯ１、および、桁上げ出力回路４０２から出力される中間桁上げ信号１２ＣＯ２が入力され、ＡＮＤ−ＯＲ回路５９１のＯＲ入力部５９１ｂには、桁上げ出力回路４０３から出力される中間桁上げ信号１２ＣＯ３が入力される。即ち、下位１２桁の加算部である桁上げ出力回路４０１の加算結果が‘１’であることから下位桁側中間桁上げ信号として１２ＣＯ１が出力される場合で、且つ、中間桁上げ信号１２ＣＯ２が出力される場合か、あるいは、上位１２桁の桁上げ出力が‘１’となる上位桁側中間桁上げ信号１２ＣＯ３が出力される場合に桁上げ信号２４ＣＯが出力される。
【０１６０】
図２０は、図１８に示した２４桁の２進数値を加算する際の桁上げ出力回路５００に、加算結果を出力する回路を追加した２進数加算回路の構成を示すブロック図である。
【０１６１】
図２０の２進数加算回路５００ａにおいて、１２桁の加算回路４０１ａは、Ａ（０）〜Ａ（１１）およびＢ（０）〜Ｂ（１１）が入力されて、中間桁上げ信号１２ＣＯ１および加算出力Ｓ（０）〜Ｓ（１１）を出力する。加算回路４０２ａは、Ａ（１２）〜Ａ（２３）およびＢ（１２）〜Ｂ（２３）が入力されて、全１信号としての中間桁上げ信号１２ＣＯ２および加算結果に１を加えた加算出力Ｓ（１２）〜Ｓ（２３）を出力する。加算回路４０３ａは、Ａ（１２）〜Ａ（２３）およびＢ（１２）〜Ｂ（２３）が入力されて、中間桁上げ信号１２ＣＯ３および加算出力Ｓ（１２）〜Ｓ（２３）を出力する。マルチプレクサ（ＭＵＸ）５９２は、加算回路４０１ａの出力１２ＣＯ１により、加算回路４０２ａからのＳ（１２）〜Ｓ（２３）出力と、加算回路４０３ａからのＳ（１２）〜Ｓ（２３）出力とから一方を選択して出力する。
【０１６２】
本実施形態のクリティカルパスの遅延時間は、第７の実施形態よりも１．０ｄｅｌ増加するのみであるので、５．５ｄｅｌとなりクリティカルパスの遅延時間の増加量を少なくすることができる。
（第１１の実施形態）
上記した第１０の実施形態では、１２桁の桁上げ出力回路を複数個用いて階層的に回路を構成することにより、２４桁の桁上げ出力回路を構成でき、それらによるクリティカルパスの遅延時間の増加量が少ないことを示した。第１０の実施形態では、使用回路の標準化のために同様な回路を使用できることが示されたが、１２ＣＯ２を出力する桁上げ出力回路については、必要な回路のみとして素子数（ゲート数）を減少させることもできる。
【０１６３】
図１９は、図１８の桁上げ出力回路を簡略化した桁上げ出力回路の構成を示すブロック図である。
【０１６４】
図１９の桁上げ出力回路５００ｃでは、図１８の下位１２桁の桁上げ出力回路４０１については、桁上げ出力回路２０２を上位６桁から全１信号を出力するためだけに必要な回路にすると共に、桁上げ出力回路２０２と２０３とで共通にする回路を統合した回路ＳＤ６ＢＢ＋として桁上げ出力回路４０１ｃとした。
【０１６５】
また、図１８の桁上げ出力回路４０２については、上位１２桁から全１信号を出力するためだけの回路にした。図１８の上位１２桁の桁上げ出力回路４０３については、まず、桁上げ出力回路４０１と同様に共通する回路を統合した回路ＳＤ６ＢＢ＋とした後、さらに、出力回路４０２と共通する回路の統合を実施して桁上げ出力回路４０２ｃとした。
【０１６６】
また、全１信号を出力するための桁上げ出力回路４２５は、全１信号を出力する回路で必要となる部分のみを残すようにしたものであるが、ここでさらに、例えば、下位桁側桁上げ出力＋１の回路であるＬＣＡ＋５１０を下位桁側全１検出回路ＬＡＬ（１）とすることができる。
【０１６７】
図２１は、図２０の加算回路を簡略化した加算回路の構成を示すブロック図である。
【０１６８】
図２１の加算回路５００ｄでは、図２０の下位１２桁の桁上げ出力回路４０１ａについては、上位６桁から全１信号を出力するためだけに必要な回路にすると共に、共通する回路を統合して桁上げ出力回路４０１ｄとした。図２０の加算回路４０２ａについては、上位１２桁から全１信号を出力する回路で必要となる部分のみを残すようにして桁上げ出力回路を必要最小限にした。また、図２０の上位１２桁の桁上げ出力回路４０３ａについては、まず、桁上げ出力回路４０１ａと同様に共通する回路を統合した後、さらに、出力回路４０２ａと共通する回路の統合を実施して桁上げ出力回路４０１ｃおよび４５５とした。
【０１６９】
また、マルチプレクサ５８３、５８４、５９７、および、５９９の構成および動作は、各マルチプレクサからの出力数が２から３に増加している点を除けば、図８に示した第４の実施形態におけるマルチプレクサ７８３、７８４、７９７、および、７９９と同様である。
【０１７０】
このようにして、本実施形態では、２４桁の加算を実施する際に、上記した第１０の実施形態に示したクリティカルパスの遅延時間を減少させることができることに加えて、回路の素子数（ゲート数）を減少させることができる。
（第１２の実施形態）
上記した第１１の実施形態の加算回路５００ｄは２４桁の加算回路として使用されるが、加算回路５００ｄを２個の２４桁の加算回路として使用したい場合も考えられる。そのような場合には、切り替え信号により２４桁の加算回路と２個の１２桁の加算回路とを切り替えられるように構成することが好ましい。
【０１７１】
図２２は、図２１の加算回路５００ｄに切り替え回路を付加した加算回路の構成を示すブロック図である。
【０１７２】
図２２の加算回路５００ｅでは、図２１の加算回路５００ｄにおけるＸａｄｄ＋５９３の出力とＡＮＤ回路５９４との間に切り替え信号入力用のＡＮＤ回路５６１を挿入し、加算回路４０１ｄの桁上げ出力とマルチプレクサ５８３との間にも切り替え信号入力用のＡＮＤ回路５６０を挿入する。
【０１７３】
このようにして、本実施形態では、切り替え入力回路としてＡＮＤ回路を２個追加するのみで、２４桁の加算回路と２個の１２桁の加算回路とを、クリティカルパスの遅延時間を悪化させることなく切り替えることができる。同様な方法を用いることにより、上記実施形態とは異なる桁数の加算器も分割使用することができる。
（第１３の実施形態）
上記した第９の実施形態では、３桁の桁上げ出力回路や３桁の加算回路を用いて１２桁の桁上げ出力回路あるいは加算回路を構成したが、例えば、３桁の桁上げ出力回路や３桁の加算回路を用いて９桁の桁上げ出力回路あるいは加算回路を構成することができる。
【０１７４】
図２３は、３桁の桁上げ出力回路を用いて構成した第１３の実施形態の９桁の桁上げ出力回路の構成を示すブロック図である。
【０１７５】
図２３（ａ）の９桁の２進数値の加算を実施する際の桁上げ出力回路３００は、最下位３桁であるＡ（０）〜Ａ（２）およびＢ（０）〜Ｂ（２）が入力されて最下位桁側中間桁上げ信号ＩＣＯ１を出力するＬＣＡ７１と、最下位桁から４桁目〜６桁目のＡ（３）〜Ａ（５）およびＢ（３）〜Ｂ（５）が入力されて、中央桁の各桁の加算結果が全て‘１’であることを検出して、各桁の加算出力が全て‘１’であることを示す全１信号ＩＣＯ２を出力するＭＡＬ（１）７２と、Ａ（３）〜Ａ（５）およびＢ（３）〜Ｂ（５）が入力されて中央桁の中間桁上げ信号ＩＣＯ３を出力する中央桁桁上げ出力回路ＭＣＡ７３と、最上位３桁であるＡ（６）〜Ａ（８）およびＢ（６）〜Ｂ（８）が入力されて各桁の加算結果が全て‘１’であることを検出して、各桁の加算出力が全て‘１’であることを示す全１信号ＩＣＯ４を出力するＨＡＬ（１）７４と、Ａ（６）〜Ａ（８）およびＢ（６）〜Ｂ（８）が入力されて最上位桁の中間桁上げ信号ＩＣＯ５を出力する上位桁側桁上げ出力回路（ＨＣＡ）７５と、ＡＮＤ回路４５ａ、ＡＮＤ回路４５ｂ、とＯＲ回路４５ｃを一体化させたＡＮＤ−ＯＲ回路４５とから構成される。
【０１７６】
ＡＮＤ−ＯＲ回路４５のクリティカルパスの遅延時間は、ＬＳＩの種類により異なるが、ここでは、３入力であることから１．０ｄｅｌのＡＮＤ回路４５ａと０．５ｄｅｌのＯＲ回路４５ｃとの和となるので１．５ｄｅｌとした。ただし、３入力ＡＮＤ回路４５ａを、図２４の２入力ＡＮＤ回路６３０ａ及び６３０ｂのように、２つに分割することで、図２３の回路構成を２入力ＡＮＤ回路と３入力ＯＲ回路とすることができ、このように構成することで遅延時間を２入力ＡＮＤの０．５ｄｅｌと３入力ＯＲ回路の０．５ｄｅｌとすることができ、合計１．０ｄｅｌと短縮させることが可能となる。
【０１７７】
ＡＮＤ−ＯＲ回路４５のＡＮＤ入力部４５ａは、ＬＣＡ７１から出力される信号ＩＣＯ１、ＭＡＬ（１）７２から出力される信号ＩＣＯ２、および、ＨＡＬ（１）７４から出力される信号ＩＣＯ４が入力されて、中間桁上げ信号を出力する。
【０１７８】
ＡＮＤ入力部４５ｂは、ＭＣＡ７３から出力される信号ＩＣＯ３、および、ＨＡＬ（１）７４から出力される信号ＩＣＯ４が入力されて、中間桁上げ信号を出力する。ＡＮＤ−ＯＲ回路４５のＯＲ入力部４５ｃには、ＡＮＤ入力部４５ａおよびＡＮＤ入力部４５ｂからの中間桁上げ信号と共に、ＨＣＡ７５から出力される信号ＩＣＯ５が入力される。
【０１７９】
図２３（ｂ）は、図２３（ａ）に示した９桁の２進数値を加算する際の桁上げ出力回路３００に、加算結果を出力する回路を追加した２進数加算回路の構成を示すブロック図である。
【０１８０】
図２３（ｂ）の２進数加算回路３００ａにおいて、３桁の加算回路８１は、Ａ（０）〜Ａ（２）およびＢ（０）〜Ｂ（２）が入力されて、中間桁上げ信号ＩＣＯ１および加算出力Ｓ（０）〜Ｓ（２）を出力する。加算回路８２は、Ａ（３）〜Ａ（５）およびＢ（３）〜Ｂ（５）が入力されて、全１信号としての中間桁上げ信号ＩＣＯ２および加算結果に１を加えた加算出力Ｓ（３）〜Ｓ（５）を出力する。加算回路８３は、Ａ（３）〜Ａ（５）およびＢ（３）〜Ｂ（５）が入力されて、中間桁上げ信号ＩＣＯ３および加算出力Ｓ（３）〜Ｓ（５）を出力する。加算回路８４は、Ａ（６）〜Ａ（８）およびＢ（６）〜Ｂ（８）が入力されて、全１信号としての中間桁上げ信号ＩＣＯ４および加算結果に１を加えた加算出力Ｓ（６）〜Ｓ（８）を出力する。加算回路８５は、Ａ（６）〜Ａ（８）およびＢ（６）〜Ｂ（８）が入力されて、中間桁上げ信号ＩＣＯ５および加算出力Ｓ（６）〜Ｓ（８）を出力する。マルチプレクサ（ＭＵＸ）８６は、加算回路８１の出力ＩＣＯ１により、加算回路８２からのＳ（３）〜Ｓ（５）出力と、加算回路８３からのＳ（３）〜Ｓ（５）出力とから一方を選択して出力する。マルチプレクサ（ＭＵＸ）８７は、加算回路８１の出力ＩＣＯ１と中間桁上げ信号ＩＣＯ２と中間桁上げ信号ＩＣＯ３とをＡＮＤ−ＯＲ回路４６で演算することにより、加算回路８２からのＳ（３）〜Ｓ（５）出力と、加算回路８３からのＳ（３）〜Ｓ（５）出力とから一方を選択して出力する。
【０１８１】
図２３（ｃ）は、マルチプレクサ（ＭＵＸ）８７において、ＩＣＯ１、ＩＣＯ２、および、ＩＣＯ３について桁上げがある場合と無い場合で、Ｘａｄｄ＋８４からの出力を選択する場合と、Ｘａｄｄ８３からの出力を選択する場合を示した図表である。
【０１８２】
図２３（ｃ）中で、ＩＣＯ３の欄は、Ｘａｄｄ８３の出力内容（１または０）を示す欄であり、ＩＣＯ１の欄は、Ｘａｄｄ８１の出力内容（１または０）を示す欄であり、ＩＣＯ２の欄は、Ｘａｄｄ＋８２の出力内容（１または０）を示す欄である、Ｘａｄｄ＋（８４）／Ｘａｄｄ（８５）の欄は、選択される方の加算回路を示した欄である。
【０１８３】
このようにして、本実施形態では、９桁の２進数の桁上げ回路あるいは加算回路を複数の３桁の桁上げ回路およびＡＮＤ−ＯＲ回路により構成することができるので、クリティカルパスの遅延時間の増加量が少ない９桁の桁上げ出力回路および加算回路を提供することができる。
（第１４の実施形態）
上記した第１３の実施形態の桁上げ出力回路を複数個使用することにより、９桁の３倍の桁上げ出力回路を得ることができる。
【０１８４】
図２４は、図２３の９桁の桁上げ出力回路３００を複数個使用して、２７桁の桁上げ出力回路を構成した場合のブロック図である。
【０１８５】
図２４の２進数加算回路６００において、９桁の加算回路３０１は、Ａ（０）〜Ａ（８）およびＢ（０）〜Ｂ（８）が入力されて、中間桁上げ信号を出力する。加算回路３０２は、Ａ（９）〜Ａ（１７）およびＢ（９）〜Ｂ（１７）が入力されて、加算出力Ｓ（９）〜Ｓ（１７）を出力する。ＬＣＡ＋６１０と直列に接続されたＡＮＤ回路６１１からは全１信号としての中間桁上げ信号が出力される。加算回路３０３は、Ａ（１８）〜Ａ（２６）およびＢ（１８）〜Ｂ（２６）が入力されて、加算出力Ｓ（１８）〜Ｓ（２６）を出力する。ＬＣＡ＋６２０と直列に接続されたＡＮＤ回路６２１からは全１信号としての中間桁上げ信号が出力される。なお、図２４では、表示を簡単にするため、加算出力Ｓ（９）〜Ｓ（２６）は省略している。
【０１８６】
ＡＮＤ−ＯＲ回路６３０のＡＮＤ回路６３０ａおよび６３０ｂでは、加算回路３０１の桁上げ出力と、ＡＮＤ回路６１１から出力される信号と、ＡＮＤ回路６２１から出力される信号とをＡＮＤ演算する。ＡＮＤ入力部６３０ｃでは、加算回路３０２の桁上げ出力と、ＡＮＤ回路６２１から出力される信号とをＡＮＤ演算する。ＯＲ回路６３０ｄでは、ＡＮＤ回路６３０ｂの出力と、ＡＮＤ入力部６３０ｃの出力と、加算回路３０３の桁上げ出力との何れかが入力されたら２７桁の桁上げ信号２７ＣＯを出力する。なお、ＡＮＤ回路６３０ａ及び６３０ｂは、３入力ＡＮＤ回路を２つに分割したものであるが、これは、前述のように遅延時間を短縮するためである。
【０１８７】
図２５は、上記した図２４の加算回路では、加算回路の桁数を３倍にした場合にクリティカルパスの遅延時間が１個のＡＮＤ−ＯＲ回路の遅延時間分である１．０ｄｅｌずつ増加することを視覚的に示した図である。
【０１８８】
図２５に示したように、本実施形態では３桁の加算回路を３倍の９桁の加算回路にし、さらに３倍にすることを繰り返して２７桁の加算回路にしても、クリティカルパスの遅延時間は、桁数３倍毎に１．０ｄｅｌしか増加しないことが確認できるので、例えば、さらに３倍の５４桁の加算回路を階層構造となるように構成した場合、２７桁の加算回路よりもクリティカルパスで１．０ｄｅｌのみ遅延時間が増加するだけとなる。同様に、１０８桁の加算回路を階層構造となるように構成しても、クリティカルパスの遅延時間は５４桁から１．０ｄｅｌしか増加しないことになる。
【０１８９】
具体的には、図２３の９桁の加算回路３００のクリティカルパスの遅延時間が４．０ｄｅｌとすると、図２４の２７桁の加算回路６００のクリティカルパスの遅延時間が５．０ｄｅｌとなる。
【０１９０】
それに対し、例えば、図３（ｂ）のキャリルックアヘッド型アダーを多段に接続した加算器では、上記したように、８桁の加算回路におけるクリティカルパスの遅延時間は５．５ｄｅｌであり、１６桁では１１．５ｄｅｌである。このように、本実施形態では、桁数を増加させた場合であっても、クリティカルパスの遅延時間の増加を最小限に抑えることができる。
（第１５の実施形態）
上記した各実施形態では、加算される２進数値は全桁の遅延時間が同一としてきたが、加算される数値の各桁値の遅延時間が異なる場合がある。
【０１９１】
図２６は、加算される数値の各桁値の遅延時間が異なる場合に、遅延時間を揃えることができる桁上げ出力回路の構成を示すブロック図である。
【０１９２】
図２６（ａ）の桁上げ出力回路７１０では、ＬＣＡ７２１の入力は遅延時間が０ｄｅｌであり、ＭＣＡ７２３およびＨＣＡ７２５の入力は遅延時間が１．０ｄｅｌであり、ＬＣＡ７２７およびＨＣＡ７２９の入力は遅延時間が２．０ｄｅｌであり、ＣＡ７３１の入力は遅延時間が３．０ｄｅｌであり、ＣＡ７３３およびＣＡ７３５の入力は遅延時間が２．０ｄｅｌであり、ＬＣＡ７３７の入力は遅延時間が１．０ｄｅｌであり、ＭＣＡ７３９およびＨＣＡ７４１の入力は遅延時間が０ｄｅｌであるとする。
【０１９３】
図２６（ｂ）のＡＮＤ回路７１５は、例えば、ＭＣＡ７２３およびＨＣＡ７２５のような１ビットの桁上げ出力回路の一例を示し、図２６（ｃ）のＯＲ回路７１６は、例えば、ＭＡＬ（１）７２２およびＨＡＬ（１）７２４のような１ビットの１を検出する回路の一例を示す。
【０１９４】
本実施形態では、加算する桁数が増加する場合にＡＮＤ−ＯＲ回路を追加するのみであるため、ＡＮＤ−ＯＲ回路の接続時の自由度が大きくなる。そのため、各入力桁の遅延状況に応じて、ＡＮＤ−ＯＲ回路を経由させる数を調整することができる。
【０１９５】
図２７は、上記した図２６の加算回路では、各入力桁の遅延状況に応じてＡＮＤ−ＯＲ回路を経由させる数を調整することによりクリティカルパスの遅延時間を均等にできることを視覚的に示した図である。
【０１９６】
図２７に示したように、本実施形態では各桁の遅延状況がＡＮＤ−ＯＲ回路７４８の出力時には均等になっている。従って、クリティカルパスも最小にすることができる。
【０１９７】
図２８は、リップルキャリ型アダー（ＲＣＡ）、キャリルックアヘッド型アダー（ＣＬＡ）、および、本発明の実施形態加算回路毎に加算桁数と遅延時間の関係を示したグラフである。本実施形態では、加算する桁数が増加しても、遅延時間の増加量が少ないことがわかる。
【０１９８】
図２９は、桁上げ出力回路における演算する桁数と遅延時間の関係を、加算桁数を上下２分割する場合と上中下３分割する場合とに分けて示した図である。
【０１９９】
図２９に示したように、加算桁数を２分割するよりも３分割した実施形態の方が、桁数が多い場合には、遅延時間の増加を抑制できる程度が大きいことがわかる。
【０２００】
なお、上記した実施形態では、加算桁数を２分割、３分割あるいは４分割した場合について示したが、本発明はこれに限られるものではなく、例えば、加算桁数を５分割よりも多く分割しても良い。また、上記した各実施形態における各桁上げ出力回路あるいは各加算回路に入力される桁数は、２の倍数や３の倍数に限られるものではなく、４の倍数や５の倍数としても良い。
【０２０１】
次に、上記した各実施形態における桁上げ出力回路を利用した加算回路で加算を実施する際の処理について、更に詳しく説明する。
【０２０２】
図３０は、図２４に示した第１４の実施形態に説明した２７桁の桁上げ出力回路を利用して加算回路を構成した場合のブロック図である。なお、図３０では、２７桁のうち、２５桁（Ｓ（２４））から２７桁（Ｓ（２６））までの加算結果を選択する選択回路部のみについて示し、他の桁の選択回路部については記載を省略している。
【０２０３】
２７桁の２進数加算回路６００ａは、９桁の２進数加算回路３０１ａ、３０２ａ、３０３ａの回路ブロック、＋１回路６１０ａ、６２０ａ、および、ＡＮＤ回路／ＯＲ回路６１１、６２１、６３０から構成される。また、見方を変えると、図３０の２７桁の２進数加算回路６００ａは、２７桁の桁上げ出力回路から、３桁の桁上げ出力回路を加算回路に変更し、全１検出回路を＋１回路に変更し、さらに、選択回路として、マルチプレクサ６５２と、そのマルチプレクサ６５２での選択信号を得るための選択ＡＮＤ回路／選択ＯＲ回路６４１〜６４３等を追加したものと言える。
【０２０４】
９桁の加算回路３０２ａには、３桁の加算回路６１２、６１４、および、６１６が内蔵され、３桁の＋１回路６１３、および、６１５が内蔵される。加算回路６１２は１０桁から１２桁の加算用であり、加算回路６１４および＋１回路６１３は１３桁から１５桁の加算用であり、加算回路６１６および＋１回路６１５は１６桁から１８桁の加算用である。また、＋１回路６１０ａは、加算回路６１２に対する＋１回路である。
【０２０５】
同様に、９桁の加算回路３０３ａには、３桁の加算回路６２１、６２３、および、６２５が内蔵され、３桁の＋１回路６２２、および、６２４が内蔵される。加算回路６２１は１９桁から２１桁の加算用であり、加算回路６２３および＋１回路６２２は２２桁から２４桁の加算用であり、加算回路６２５および＋１回路６２４は２５桁から２７桁の加算用である。また、＋１回路６２０ａは、加算回路６２１に対する＋１回路である。
【０２０６】
次に、図３０の２７桁の２進数加算回路６００ａで記載を一部省略していた選択回路のうち、一例として、１０桁（Ｓ（９））から１２桁（Ｓ（１１））までの選択回路について説明する。
【０２０７】
図３１は、図３０の２７桁の２進数加算回路６００ａにおける、１０桁（Ｓ（９））から１２桁（Ｓ（１１））までの選択回路を示す図である。
【０２０８】
１０桁（Ｓ（９））から１２桁（Ｓ（１１））用のマルチプレクサ６５０には、１０桁から１２桁用の３桁の加算回路（Ｘａｄｄ）６１２の加算結果、および、１０桁から１２桁用の３桁の＋１回路６１０ａの加算結果が入力され、９桁の加算回路３０１ａの内部信号から図３１に示したようにＡＮＤ回路とＯＲ回路（符号４５、７１等）を組み合わせて得られた選択信号により、何れかの信号を選択して出力する。この選択信号を得るためのＡＮＤ回路とＯＲ回路を組み合わせは、各実施形態にて説明した桁上げ出力を得るためのＡＮＤ回路とＯＲ回路の組み合わせと同様な組み合わせを用いている。
【０２０９】
また、図３２は、図３０の２７桁の２進数加算回路６００ａにおける、１６桁（Ｓ（１５））から１８桁（Ｓ（１７））までの選択回路を示す図である。
【０２１０】
１６桁（Ｓ（１５））から１８桁（Ｓ（１７））用のマルチプレクサ６５１には、１６桁から１８桁用の３桁の加算回路（Ｘａｄｄ）６１６の加算結果、および、１６桁から１８桁用の３桁の＋１回路６１５の加算結果が入力され、９桁の加算回路３０１ａおよび３０２ａの内部信号から図３２に示したようにＡＮＤ回路とＯＲ回路（符号４５、７１、６３１および６３２等）を組み合わせて得られた選択信号により、何れかの信号を選択して出力する。この選択信号を得るためのＡＮＤ回路とＯＲ回路を組み合わせも、各実施形態にて説明した桁上げ出力を得るためのＡＮＤ回路とＯＲ回路の組み合わせと同様な組み合わせを用いている。
【０２１１】
さらに、図３３は、図３０の２７桁の２進数加算回路６００ａにおける、２５桁（Ｓ（２４））から２７桁（Ｓ（２６））までの選択回路を示す図である。
【０２１２】
２５桁（Ｓ（２４））から２７桁（Ｓ（２６））用のマルチプレクサ６５２には、２５桁から２７桁用の３桁の加算回路（Ｘａｄｄ）６２５の加算結果、および、２５桁から２７桁用の３桁の＋１回路６２４の加算結果が入力され、９桁の加算回路３０１ａ、３０２ａおよび３０３ａの内部信号から図３３に示したようにＡＮＤ回路とＯＲ回路（符号４５、７１、６３３、６３４および６３５等）を組み合わせて得られた選択信号により、何れかの信号を選択して出力する。この選択信号を得るためのＡＮＤ回路とＯＲ回路を組み合わせも、各実施形態にて説明した桁上げ出力を得るためのＡＮＤ回路とＯＲ回路の組み合わせと同様な組み合わせを用いている。
【０２１３】
このようにして、各桁の加算結果を得ることができる。
【０２１４】
また、上記した各実施形態では、例えば、各３桁の加算回路毎にマルチプレクサで選択し、その選択された加算結果を階層的にさらにマルチプレクサで選択することも可能である。
【０２１５】
図３４は、図３０の２７桁の加算回路の構成を、選択信号が階層的に得られるように変更した場合のブロック図である。
【０２１６】
図３４の加算回路では、９桁の各加算回路３０１ｂ、３０２ｂ、３０３ｂ、そして、９桁の各＋１回路３５２および３５３は、その内部にマルチプレクサを有しており、選択された９桁の加算結果を出力できるように構成されている。また、１０桁（Ｓ（９））から１８桁（Ｓ（１７））までのマルチプレクサ６５３では、加算回路３０２ｂの加算結果と＋１回路３５２の加算結果が入力されて、９桁の加算回路３０１ｂの桁上げ出力信号を選択信号として図３４に示したように、何れかの信号を選択して出力する。
【０２１７】
また、１９桁（Ｓ（１８））から２７桁（Ｓ（２６））までのマルチプレクサ６５４では、加算回路３０３ｂの加算結果と＋１回路３５３の加算結果が入力されて、９桁の加算回路３０１ｂ、３０２ｂおよび＋１回路３５２からの桁上げ出力信号から図３４に示したように選択ＡＮＤ回路と選択ＯＲ回路（符号６４４）を組み合わせて得られた選択信号により、何れかの信号を選択して出力する。
【０２１８】
このようにして、上記した各実施形態では、加算結果を階層的にマルチプレクサで選択することにより、加算結果を得ることも可能である。
【０２１９】
また、上記した各実施形態の加算回路では、各桁の加算結果を得るために、マルチプレクサを用いて、当該桁の加算結果とその加算結果＋１とから選択して出力するようにしていた。しかし、例えば、上記した各実施形態中のマルチプレクサは＋１回路に置き換えることができ、また、上記した各実施形態中の＋１回路は全１検出回路に置き換えることができ、その置き換えを実施しても本発明の効果を得ることができる。
【０２２０】
図３５は、図３０に示した２７桁の加算回路中のマルチプレクサを＋１回路に置き換えた場合のブロック図である。
【０２２１】
図３５では、図３０のマルチプレクサ６５２が、＋１回路６５２ｂに変更されている。それと共に、図３５では、９桁の加算回路３０１ｂ、３０２ｂおよび３０３ｂ中の＋１回路が全１検出回路に変更されている。例えば、図３０では９桁の加算回路３０２ａ中の＋１回路６１３および６１５であったものが、図３５では９桁の加算回路３０２ｂ中の全１検出回路６１３ｂおよび６１５ｂに変更されており、同様に、＋１回路６１０ａは全１検出回路６１０ｂに変更されている。
【０２２２】
また、９桁の加算回路３０３ａ中の＋１回路６２２および６２４であったものが、図３５では９桁の加算回路３０３ｂ中の全１検出回路６２２ｂおよび６２４ｂに変更されており、同様に、＋１回路６２０ａは全１検出回路６２０ｂに変更されている。
【０２２３】
例えば、この構成の＋１回路６５２ｂでは、選択信号により選択を実施するのではなく、選択信号により加算結果に対して＋１の演算を実施する。
【０２２４】
図３６は、図３５の２７桁の２進数加算回路６００ｂにおける、１０桁（Ｓ（９））から１２桁（Ｓ（１１））までの選択回路を示す図である。
【０２２５】
図３６の構成では、図３１に示したマルチプレクサ６５０を用いる場合と異なり、９桁の加算回路３０１ｂからの桁上げ出力信号からＡＮＤ回路とＯＲ回路で演算された選択信号と、全１回路６１０ｂからの全１信号とが＋１回路６５０ｂに入力する場合には、＋１回路６５０ｂは、３桁の加算回路６１２からの加算結果に対して１を加算して出力する。
【０２２６】
図３７は、図３５の２７桁の２進数加算回路６００ｂにおける、１６桁（Ｓ（１５））から１８桁（Ｓ（１７））までの選択回路を示す図である。
【０２２７】
図３７の構成では、図３２に示したマルチプレクサ６５１を用いる場合と異なり、９桁の加算回路３０１ｂ、加算回路６１２および加算回路６１４からの桁上げ出力信号からＡＮＤ回路とＯＲ回路で演算された選択信号と、全１回路６１５ｂからの全１信号とが＋１回路６５１ｂに入力する場合には、＋１回路６５１ｂは、３桁の加算回路６１６からの加算結果に対して１を加算して出力する。
【０２２８】
図３８は、図３５の２７桁の２進数加算回路６００ｂにおける、２５桁（Ｓ（２４））から２７桁（Ｓ（２６））までの選択回路を示す図である。
【０２２９】
図３８の構成では、図３３に示したマルチプレクサ６５２を用いる場合と異なり、９桁の加算回路３０１ｂ、加算回路３０２ｂ、加算回路６２１および加算回路６２３からの桁上げ出力信号からＡＮＤ回路とＯＲ回路で演算された選択信号と、全１回路６２０ｂからの全１信号とが＋１回路６５２ｂに入力する場合には、＋１回路６５２ｂは、３桁の加算回路６２５からの加算結果に対して１を加算して出力する。
【０２３０】
このようにして、上記した各実施形態の加算回路中のマルチプレクサは、＋１回路に置き換えることができ、また、上記した各実施形態中の＋１回路は全１検出回路に置き換えることができるので、マルチプレクサを用いるか＋１回路を用いるか、あるいは、＋１回路を用いるか全１検出回路を用いるかを用途に応じて自由に変更することができ、また、組み合わせを変えることができる。
【０２３１】
図３９は、図３０から図３８までの選択信号を用いて加算出力を選択あるいは演算して出力する回路における選択ＡＮＤ回路および選択ＯＲ回路の接続図である。
【０２３２】
図３９中では、１個のＡＮＤ回路の出力が１個の２入力ＯＲ回路に入力するもの（Ａタイプ出力）と、２個のＡＮＤ回路の出力が１個の３入力ＯＲ回路に入力するもの（Ｂタイプ出力）とが組み合わされている。また、各桁の選択信号Ｓ１〜Ｓ２６は、上記したように、マルチプレクサあるいは＋１回路に入力される。
【０２３３】
図３９（ｂ）は、選択信号Ｓ１〜Ｓ２６がマルチプレクサ９５１に入力されて「Ａタイプ出力＋Ｂタイプ出力」の入力と、「Ａタイプ出力＋Ｂタイプ出力＋１」入力とから選択して出力される場合を示す図であり、図３９（ｃ）は、選択信号Ｓ１〜Ｓ２６が＋１回路９５２に入力されて「Ａタイプ出力＋Ｂタイプ出力」入力をそのまま出力するか「Ａタイプ出力＋Ｂタイプ出力＋１」と１を加算してから出力するかを選択する場合を示す図である。
【０２３４】
このように選択信号を生成することで、マルチプレクサあるいは＋１回路を任意に用いて各桁の加算結果を得ることができる。
【０２３５】
上記した各実施形態では、２桁毎あるいは３桁毎の桁上げ回路や加算回路を元にして、２４桁、２７桁あるいは３２桁等の桁上げ回路や加算回路を示してきたが、本発明はこれに限られるものではなく、例えば、４８桁や６４桁等のさらに多くの桁の加算回路等に適用することができる。また、上記した各実施形態では、２の倍数あるいは３の倍数の組み合わせを主に説明したが、本発明はこれに限られるものではなく、例えば、図２６および図２７に示したように実施することで、任意の桁数の加算回路に対しても適用することができる。
【０２３６】
また、上記した第９の実施形態では、１２桁の桁上げ出力回路あるいは加算回路として、３桁の桁上げ出力回路や３桁の加算回路を用いて、６桁の回路を作らずに１２桁の桁上げ出力回路あるいは加算回路を構成したが、この手法を用いて、任意の桁の桁上げ出力回路あるいは加算回路を構成することができる。
【０２３７】
図４０は、第９の実施形態の手法を用いた任意の桁の桁上げ出力回路の構成を示すブロック図である。
【０２３８】
図４０の桁上げ出力回路１０００は、最下位の数値または最下位から所定桁まで上位の数値が入力されて最下位桁側の桁上げ信号を出力する第１桁上げ出力回路（第１ＣＡ）１００１と、最下位の次の桁の数値または最下位から所定桁だけ上位の数値が入力されて各桁の加算結果が全て‘１’であることを検出して全１信号を出力する第２ＡＬ（１）１００２と、最下位の次の桁の数値または最下位から所定桁だけ上位の数値が入力されてその桁の桁上げ信号を出力する第２桁上げ出力回路（第２ＣＡ）１００３と、最上位の次の桁の数値または最上位から所定桁だけ下位の数値が入力されて各桁の加算結果が全て‘１’であることを検出して全１信号を出力する第（ｎ−１）ＡＬ（１）１００４と、最上位の次の桁の数値または最上位から所定桁だけ下位の数値が入力されてその桁の桁上げ信号を出力する第（ｎ−１）桁上げ出力回路（第（ｎ−１）ＣＡ）１００５と、最上位の桁の数値または最上位から所定桁だけ下位までの数値が入力されて各桁の加算結果が全て‘１’であることを検出して全１信号を出力する第ｎＡＬ（１）１００６と、最上位の桁の数値または最上位から所定桁だけ下位までの数値が入力されてその桁の桁上げ信号を出力する第ｎ桁上げ出力回路（第ｎＣＡ）１００７と、第２のＡＮＤ出力部となるＡＮＤ回路１０２０ａ、第（ｎ−１）のＡＮＤ出力部となるＡＮＤ回路１０２０ｂ、第ｎのＡＮＤ出力部となるＡＮＤ回路１０２０ｃ、とＯＲ回路１０２０ｄを一体化させたＡＮＤ−ＯＲ回路１２０とから構成される。
【０２３９】
ＡＮＤ−ＯＲ回路１０２０の第２のＡＮＤ入力部１０２０ａは、第１ＣＡ１００１から出力される信号、第２ＡＬ（１）１００２から出力される信号、・・・、第（ｎ−１）ＡＬ（１）１００４から出力される信号、および、第ｎＡＬ（１）１００６から出力される信号が入力されて、中間桁上げ信号ＩＣＯ１を出力する。
【０２４０】
第（ｎ−１）のＡＮＤ入力部１０２０ｂは、不図示の第（ｎ−２）ＣＡから出力される信号、第（ｎ−１）ＡＬ（１）１００４から出力される信号、および、第ｎＡＬ（１）１００６から出力される信号が入力されて、中間桁上げ信号ＩＣＯ（ｎ−２）を出力する。
【０２４１】
第ｎのＡＮＤ入力部１０２０ｃは、第（ｎ−１）ＣＡ１００５から出力される信号、および、第ｎＡＬ（１）１００６から出力される信号が入力されて、中間桁上げ信号ＩＣＯ（ｎ−１）を出力する。ＡＮＤ−ＯＲ回路１０２０のＯＲ入力部１０２０ｄには、中間桁上げ信号ＩＣＯ１〜ＩＣＯ（ｎ）と共に、第ｎＣＡ１００７から出力される信号ＩＣＯ（ｎ）が入力される。
【０２４２】
即ち、ＡＮＤ−ＯＲ回路１０２０は、以下の３種の場合において最上位桁からの桁上げがあると判断して桁上げ信号ＣＯを出力する。
【０２４３】
場合１：最下位桁の加算部である第１ＣＡ１００１の加算結果が‘１’であることから最下位桁側中間桁上げ信号が出力され、且つ、それより上位の全ての各桁の加算結果が全て‘１’であることを示す全１信号が出力される場合。
【０２４４】
場合２：任意桁の第（ｎ−ｍ）の桁上げ出力回路から中間桁上げ信号が出力され、且つ、それよりも上位桁の各桁の加算結果が全て‘１’であることを示す全１信号ＭＨ１が出力される場合。
【０２４５】
場合３：第ｎの桁上げ出力回路第ｎＣＡ１００７から中間桁上げ信号ＩＣＯ（ｎ）が出力される場合。
【０２４６】
このようにして、任意の桁の２進数の桁上げ回路を、その２進数を分割した数分の複数の桁上げ回路およびＡＮＤ−ＯＲ回路により構成することができることがわかる。
【０２４７】
また、図４０に示した実施形態では、第５の実施形態あるいは第１４の実施形態と同様の手法を用いて階層的に構成することも可能である。階層構造としては、第５の実施形態では、図１０に示したように２本木のツリー構造となり、第１４の実施形態では、図２５に示したように３本木のツリー構造となるが、本実施形態では、図１０に示したようにｎ（ｎは２以上の整数）本木のツリー構造となる。
【０２４８】
なお、図４０に示した１０２０ａ、１０２０ｂのように多入力ＡＮＤ回路を各々２分割することで、前述したようにクリティカルパスの遅延時間を少なくすることができる。分割しない場合には、多入力ＡＮＤ回路がクリティカルパスに含まれるため、遅延時間が増大する。それに対し、分割した場合には、２入力ＡＮＤ回路の０．５ｄｅｌだけで済むので遅延時間を減少させることができる。この遅延時間の減少は、本実施形態を階層構造に適用した場合には、階層毎に減少させることができるので、遅延時間を減少させる上で特に効果が顕著となる。
【０２４９】
【発明の効果】
上記のように本発明の加算を実施する際の桁上げ出力回路および加算回路では、加算桁数を２倍あるいは３倍等に増加させる場合の遅延時間の増加を抑制することができ、回路の素子数（ゲート数）の増加についても抑制することができる。
【０２５０】
また、本発明の加算を実施する際の桁上げ出力回路および加算回路では、加算桁数については、２の倍数、３の倍数だけでなく、任意桁の桁上げ出力回路および加算回路を設定することができる。
【０２５１】
また、本発明の加算を実施する際の桁上げ出力回路および加算回路では、ＡＮＤ−ＯＲ回路の接続時の自由度が大きくでき、各入力桁の遅延状況に応じて、ＡＮＤ−ＯＲ回路を経由させる数を調整することができ、わずかな回路追加のみで、多数桁の加算回路を２個の半分の桁の加算回路として切り替えて使用することができる。
【図面の簡単な説明】
【図１】  （ａ）〜（ｄ）は本発明の第１の実施形態の桁上げ出力回路の構成を示すブロック図である。
【図２】  （ａ）はＨＡＬ（１）の入力と出力を場合分けした図表であり、（ｂ）はＩＣＯ２、ＬＣおよびＡＬ１について桁上げがある場合と無い場合を４桁の２進数値を例示と共に示した図表である。
【図３】  （ａ）、（ｂ）はキャリールックアヘッド型アダーの構成の一例を示すブロック図である。
【図４】  （ａ）は５入力ＡＮＤ回路を１素子で表した図であり、（ｂ）は２入力ＡＮＤ素子を４個組み合わせて５入力ＡＮＤ回路を表した図である。
【図５】  （ａ）は図１（ａ）の桁上げ出力回路に加算結果を出力する回路を追加した２進数加算回路の構成を示すブロック図であり、（ｂ）はマルチプレクサで出力を選択するために用いられる図表である。
【図６】  （ａ）〜（ｃ）は各加算部への入力桁数が４桁の場合を示す本発明の第２の実施形態の桁上げ出力回路の構成を示すブロック図である。
【図７】  図５（ａ）の複数個の加算回路を階層構造となるように用いた第３の実施形態の加算回路の構成を示すブロック図である。
【図８】  図７の複数個の加算回路を階層構造となるように用いた第４の実施形態の加算回路の構成を示すブロック図である。
【図９】  図８の複数個の加算回路を階層構造となるように用いた第５の実施形態の加算回路の構成を示すブロック図である。
【図１０】  上記した図５、図７〜図９の加算回路における遅延時間の増加分を視覚的に示した図である。
【図１１】  （ａ）〜（ｄ）は各加算部への入力桁数が３桁の場合を示す本発明の第６の実施形態の桁上げ出力回路の構成を示すブロック図である。
【図１２】  （ａ）は図１１（ａ）の桁上げ出力回路に加算結果を出力する回路を追加した２進数加算回路の構成を示すブロック図であり、（ｂ）はマルチプレクサで出力を選択するために用いられる図表である。
【図１３】  図１１（ａ）の複数個の桁上げ出力回路を階層構造となるように用いた第７の実施形態の桁上げ出力回路の構成を示すブロック図である。
【図１４】  図１３の桁上げ出力回路に加算結果を出力する回路を追加した２進数加算回路の構成を示すブロック図である。
【図１５】  図１３の桁上げ出力回路を簡略化した第８の実施形態の桁上げ出力回路の構成を示すブロック図である。
【図１６】  図１４の加算回路を簡略化した加算回路の構成を示すブロック図である。
【図１７】  ３桁の桁上げ出力回路を用いて構成した第９の実施形態の１２桁の桁上げ出力回路の構成を示すブロック図である。
【図１８】  図１３の複数個の桁上げ出力回路を階層構造となるように用いた第１０の実施形態の桁上げ出力回路の構成を示すブロック図である。
【図１９】  図１８の桁上げ出力回路を簡略化した桁上げ出力回路の構成を示すブロック図である。
【図２０】  図１８の桁上げ出力回路に加算結果を出力する回路を追加した２進数加算回路の構成を示すブロック図である。
【図２１】  図２０の加算回路を簡略化した加算回路の構成を示すブロック図である。
【図２２】  図２１の加算回路に切り替え回路を付加した加算回路の構成を示すブロック図である。
【図２３】  （ａ）〜（ｃ）は３桁の桁上げ出力回路を用いて構成した第１３の実施形態の９桁の桁上げ出力回路の構成を示すブロック図である。
【図２４】  図２３の桁上げ出力回路を複数個使用して２７桁の桁上げ出力回路を構成した場合のブロック図である。
【図２５】  図２４の加算回路における遅延時間の増加分を視覚的に示した図である。
【図２６】  （ａ）〜（ｃ）は加算される数値の各桁値の遅延時間が異なる場合に遅延時間を揃えることができる桁上げ出力回路の構成を示すブロック図である。
【図２７】  図２６の加算回路におけるクリティカルパスの遅延時間が均等にできることを視覚的に示した図である。
【図２８】  従来のＲＣＡ、ＣＬＡ、および、本発明の実施形態加算回路毎に加算桁数と遅延時間の関係を示したグラフである。
【図２９】  桁上げ出力回路における演算するステップ数と遅延時間の関係を、加算桁数を上下２分割する場合と上中下３分割する場合とに分けて示した図である。
【図３０】  ２７桁の加算回路を構成した場合のブロック図である。
【図３１】  図３０の加算回路における加算方法を視覚的に示した図である。
【図３２】  図３０の加算回路における、１６桁から１８桁までの選択回路を示す図である。
【図３３】  図３０の加算回路における、２５桁から２７桁までの選択回路を示す図である。
【図３４】  図３０の加算回路の構成を選択信号が階層的に得られるように変更した場合のブロック図である。
【図３５】  図３０の加算回路中のマルチプレクサを＋１回路に置き換えた場合のブロック図である。
【図３６】  図３５の加算回路における１０桁から１２桁までの選択回路を示す図である。
【図３７】  図３５の加算回路における２５桁から２７桁までの選択回路を示す図である。
【図３８】  図３５の加算回路における１０桁から１２桁までの選択回路を示す図である。
【図３９】  図３０から図３８までの選択信号を用いて加算出力を選択あるいは演算して出力する回路におけるＡＮＤ回路およびＯＲ回路の接続図である。
【図４０】  第９の実施形態の手法を用いた任意の桁の桁上げ出力回路の構成を示すブロック図である。
【図４１】  （ａ）〜（ｂ）は従来のフルアダー（ＦＡ）及びフルアダーを各桁毎に直列に接続した非同期型（リップルキャリ型）アダー（ＲＣＡ）の構成を示すブロック図である。
【図４２】  （ａ）〜（ｃ）は従来のキャリーセレクト型アダー（ＣＳＡ）の構成を示すブロック図である。
【符号の説明】
２  ３入力ＥＸ−ＯＲ回路、  ３，４，５，４４ａ，４５，４５ｂ，４６ａ，９１ａ，１１１，１２０ｃ，１２３，１３１，２９２ａ，５１１，５２０，５６０，５６１，５８６，５９１ａ，５９４，５９５，７８６，７９４，７９５  ２入力ＡＮＤ回路、  ６，４５ｃ  ３入力ＯＲ回路、  １０〜１８  フルアダー、２０  ２入力ＥＸ−ＯＲ回路、  ２１，３１，３２，３３  キャリルックアヘッド型アダー、  ２２，４４ｂ，４６ｂ、９１ｂ，１１２，１１３，１２１，１２２，１３１，１３２，２９２ｂ，５９１ｂ  ２入力ＯＲ回路、  ２３  ５入力ＡＮＤ回路、  ２３ａ，１２０ａ  ４入力ＡＮＤ回路、  ２４  ５入力ＯＲ回路、  ２４ａ，１２０ｄ  ４入力ＯＲ回路、  ４１，６１，８１，２０１ａ  加算回路（下位桁側）、  ４２，４１ａ，６２，８２，８４，２０２ａ  １追加算加算回路、  ４３，６３，８５，２０３ａ，２０５  加算回路（上位桁側）、  ４４，４５，４６，７１，８１，９１，９２，１２０，２９１，２９２，５３０，５８５，５８７，５９６，５９８，５９１，６３０，７２１，７３９，７４１，７４２，７４３，７４５，７４７，７４８，７８５，７８７，７９１，７９６，７９８，８９１，９０４  ＡＮＤ−ＯＲ回路、  ４５ａ，６１１，６２１，７４４，７４６  ３入力ＡＮＤ回路、  ５１，７１，１５１，１１１，２１１，７２１，７２７，７３７  下位桁側桁上げ出力回路（ＬＣＡ）、  ５１ａ，６１ａ，６１０，６２０  １追加算下位桁側桁上げ出力回路（ＬＣＡ＋）、  ５２，７４，１１６，１５２，２１２，４２５，４５５，７２４，７２８，７４０，７５５，８５５  全１出力回路（ＨＡＬ（１））、  ５３，５５，７５，１１７，１５３，２１３，７２５，７２９，７４１  上位桁側桁上げ出力回路（ＨＣＡ）、  ６５，８６，８７，９２，９３，９４，２９３，２９４，５８３，５８４，５８７，５９７，５９９，５９２  マルチプレクサ（ＭＵＸ）、  ７２，７２２，７３８  中央桁全１出力回路（ＭＡＬ（１））、  ７３，７２３，７３９  中央桁桁上げ出力回路（ＭＣＡ）、  ８３  加算回路（中央桁側）、  １００，２０１，２０２，２０３，２０４，２１０，３００，３０１，３０２，３０３，４００，４００ｃ，４０１，４０１ａ，４０１ｃ，４０２，４０２ａ，４０２ｃ，４０３，４０３ａ，５００，５００ｃ，６００，７１０  桁上げ出力回路、  １００ａ，１０１ａ，１０５，２００，２００ａ，２５０，３００ａ，４００ａ，４００ｄ，４００ｆ，４０１ｃ，４０１ｄ，５００ａ，５００ｄ，５００ｅ，７００ｃ，７００ｄ，７５１ｃ，７５１ｄ，７６１，７６４，８００ｃ，８００ｄ  加算回路、  １１２  中央低域側全１出力回路（ＭＬＡＬ（１））、  １１３  中央低域側桁上げ出力回路（ＭＬＣＡ）、  １１４  中央高域側全１出力回路（ＭＨＡＬ（１））、  １１５  中央高域側桁上げ出力回路（ＭＨＣＡ）、  １２０ｂ  ３入力ＡＮＤ回路、  ７１５  １桁桁上げ出力回路、  ７１６  １桁全１出力回路、  ７３０，７３２，７３４，７３６  全１出力回路（ＡＬ（１））、  ７３１，７３３，７３５  桁上げ出力回路、  ９００  キャリセレクト型アダー（ＣＳＡ）、  ９０１  リップルキャリ型アダー（下位桁側）、  ９０２  １加算リップルキャリ型アダー、  ９０３  リップルキャ���型アダー（上位桁側）。
【図１】
0003651592.tif 000002
【図２】
0003651592.tif 000003
【図３】
0003651592.tif 000004
【図４】
0003651592.tif 000005
【図５】
0003651592.tif 000006
【図６】
0003651592.tif 000007
【図７】
0003651592.tif 000008
【図８】
0003651592.tif 000009
【図９】
0003651592.tif 000010
【図１０】
0003651592.tif 000011
【図１１】
0003651592.tif 000012
【図１２】
0003651592.tif 000013
【図１３】
0003651592.tif 000014
【図１４】
0003651592.tif 000015
【図１５】
0003651592.tif 000016
【図１６】
0003651592.tif 000017
【図１７】
0003651592.tif 000018
【図１８】
0003651592.tif 000019
【図１９】
0003651592.tif 000020
【図２０】
0003651592.tif 000021
【図２１】
0003651592.tif 000022
【図２２】
0003651592.tif 000023
【図２３】
0003651592.tif 000024
【図２４】
0003651592.tif 000025
【図２５】
0003651592.tif 000026
【図２６】
0003651592.tif 000027
【図２７】
0003651592.tif 000028
【図２８】
0003651592.tif 000029
【図２９】
0003651592.tif 000030
【図３０】
0003651592.tif 000031
【図３１】
0003651592.tif 000032
【図３２】
0003651592.tif 000033
【図３３】
0003651592.tif 000034
【図３４】
0003651592.tif 000035
【図３５】
0003651592.tif 000036
【図３６】
0003651592.tif 000037
【図３７】
0003651592.tif 000038
【図３８】
0003651592.tif 000039
【図３９】
0003651592.tif 000040
【図４０】
0003651592.tif 000041
【図４１】
0003651592.tif 000042
【図４２】
0003651592.tif 000043