(57)【要約】  【課題】消費電力を増大させることなく高速に加算を実行できる加算回路と、そのような加算回路を最終段に有する乗算回路および乗算加算回路を提供する。  【解決手段】ワレスの木から最終段の加算回路へ入力される信号の遅延は、中位のビット範囲において最大となり、下位，上位のビット範囲においてこれより小さくなる特徴を持つ。そこで、下位のビット範囲では、上位桁へのキャリー伝播が比較的遅い１レベルのキャリー・インクリメント・アダー１により加算を行い、中位のビット範囲では、これよりもキャリー伝播が高速な２レベルのキャリー・インクリメント・アダー１により加算を行い、上位のビット範囲では、高速なキャリー・セレクト・アダー３により加算を行う。このように、それぞれのビット範囲において信号入力タイミングの遅延傾向に適合した加算方式により加算を行うため、回路規模および消費電力を抑えつつ演算を高速化できる。【選択図】      図３
2005182346.tif 000002
【特許請求の範囲】
【請求項１】
入力される加算対象の信号のそれぞれ異なるビット範囲を加算する複数の加算ユニットを有し、
上記複数の加算ユニットの少なくとも２つは、その加算を行うビット範囲において加算対象のビット信号の入力タイミングが上位桁に向かうにつれて変化する当該変化の傾向にそれぞれ適合した加算方式であって、各桁の加算値の算出タイミングが上位桁に向かうにつれて変化する傾向に違いを有する異なる加算方式により加算を行う、
加算回路。
【請求項２】
上記複数の加算ユニットは、
ビット信号の入力タイミングが上位桁に向かうにつれて遅延する傾向を有する第１のビット範囲の入力信号に対して、上記加算値算出タイミングが上位桁に向かうにつれて遅延する第１の加算方式により加算を行う第１の加算ユニットと、
上記入力タイミングが上位桁に向かうにつれて上記第１のビット範囲より緩やかに遅延するか若しくは早くなる傾向を有する第２のビット範囲の入力信号に対して、上記加算値算出タイミングが上位桁に向かうにつれて上記第１の加算方式より緩やかに遅延する第２の加算方式により加算を行う第２の加算ユニットと、を含む、
請求項１に記載の加算回路。
【請求項３】
上記第１の加算ユニットおよび上記第２の加算ユニットは、
第Ｋ桁（Ｋは正の整数を示す）へのキャリー信号に応じて第ｉ桁（ｉは、ｉ＞Ｋを満たす整数を示す）で生じるキャリー信号が変化するか否かを示すキャリー伝播信号ｐ（ｉ，Ｋ）を前段からのキャリー伝播信号ｐ（ｉ−１，Ｋ）に基づいて生成する、縦続に接続された複数の回路を含む第１のキャリー伝播信号生成回路と、
第Ｋ桁へのキャリー信号に依存せずに第ｉ桁で生じるキャリー信号が所定のビット値になるか否かを示すキャリー生成信号ｇ（ｉ，Ｋ）を前段からのキャリー生成信号ｇ（ｉ−１，Ｋ）に基づいて生成する、縦続に接続された複数の回路を含む第１のキャリー生成信号生成回路と、
上記第１のキャリー伝播信号生成回路より出力されるキャリー伝播信号ｐ（ｉ，Ｋ）と、上記第１のキャリー生成信号生成回路より出力されるキャリー生成信号ｇ（ｉ，Ｋ）と、第Ｋ桁へのキャリー信号にとに基づいて、第ｉ桁で生じるキャリー信号を生成するキャリー信号生成回路と、を含む、
請求項２に記載の加算回路。
【請求項４】
第ｋのキャリー伝播信号生成回路（ｋは、２以上の整数を示す）は、第（ｋ−１）のキャリー伝播信号生成回路の縦続接続回路の終段から出力されるキャリー伝播信号ｐ（Ｍ２，Ｍ１）（Ｍ２，Ｍ１は、Ｍ２＞Ｍ１を満たす正の整数を示す）と、前段からのキャリー伝播信号ｐ（Ｍ１−１，Ｍ０）（Ｍ０は、Ｍ１＞Ｍ０を満たす正の整数を示す）とに基づいてキャリー伝播信号ｐ（Ｍ２，Ｍ０）を生成する、縦続に接続された複数の回路を含む回路であり、
第ｋのキャリー生成信号生成回路は、第（ｋ−１）のキャリー生成信号生成回路の縦続接続回路の終段から出力されるキャリー生成信号ｇ（Ｍ２，Ｍ１）と、前段からのキャリー生成信号ｇ（Ｍ１−１，Ｍ０）と、第（ｋ−１）のキャリー伝播信号生成回路の縦続接続回路の終段から出力されるキャリー伝播信号ｐ（Ｍ２，Ｍ１）とに基づいてキャリー生成信号ｇ（Ｍ２，Ｍ０）を生成する、縦続に接続された複数の回路を含む回路であり、
上記第１の加算ユニットは、
ｋが最大でｍ（ｍは、１以上の整数を示す）までの第ｋのキャリー伝播信号生成回路および第ｋのキャリー生成信号生成回路を含み、
上記第２の加算ユニットは、
ｋが最大でｎ（ｎは、ｍより大きい整数を示す）までの第ｋのキャリー伝播信号生成回路および第ｋのキャリー生成信号生成回路を含む、
請求項３に記載の加算回路。
【請求項５】
上記複数の加算ユニットは、上記入力タイミングが上位桁に向かうにつれて早くなる傾向を有するビット範囲の入力信号に対して、当該ビット範囲に供給される下位桁からのキャリー信号のそれぞれの仮定値に対応する各桁のキャリー信号の予測値を予め算出し、当該下位桁から供給されるキャリー信号と当該予測値とに基づいて各桁のキャリー信号を生成する第３の加算方式により加算を行う第３の加算ユニットを含む、
請求項１乃至４の何れか一に記載の加算回路。
【請求項６】
上記複数の加算ユニットは、上記入力タイミングが上位桁に向かうにつれて遅延する傾向を有するビット範囲の入力信号に対して、下位桁から上位桁に向かって順番にキャリー信号を算出する第４の加算方式により加算を行う第４の加算ユニットを含む、
請求項１乃至５の何れか一に記載の加算回路。
【請求項７】
２を超える複数の部分積を加算した結果として２つの信号を出力する第１の加算回路と、上記第１の加算回路から出力される２つの信号を加算する第２の加算回路とを有する乗算回路であって、
上記第２の加算回路は、上記第１の加算回路から出力される２つの信号のそれぞれ異なるビット範囲を加算する複数の加算ユニットを有する、請求項１乃至６の何れか一に記載の加算回路である、
乗算回路。
【請求項８】
上記第２の加算回路は、
上記２つの信号の最下位桁から所定の中位桁までのビット範囲を加算する請求項４に記載の第１の加算ユニットと、
上記２つの信号の上記中位桁から所定の上位桁までのビット範囲を加算する請求項４に記載の第２の加算ユニットと、
上記２つの信号の上記上位桁から最上位桁までのビット範囲を加算する請求項５に記載の第３の加算ユニットと、を含む、
請求項７に記載の乗算回路。
【請求項９】
上記第２の加算回路は、最下位桁の加算結果として上記２つの信号のうちの一方の最下位桁のビット信号を出力するとともに、当該最下位桁の上位桁の加算結果として当該上位桁のビット信号同士の排他的論理和を出力する、
請求項７または８に記載の乗算回路。
【請求項１０】
上記第２の加算回路は、最上位桁の加算結果として下位桁から最上位桁へのキャリー信号の論理反転信号を出力する、
請求項７乃至９の何れか一に記載の乗算回路。
【請求項１１】
上記第１の加算回路は、ツリー状に接続された複数の全加算器を含む、
請求項７乃至１０の何れか一に記載の乗算回路。
【請求項１２】
２を超える複数の部分積を加算した結果として２つの信号を出力する第１の加算回路と、上記第１の加算回路から出力される２つの信号を加算する第２の加算回路とを有する乗算加算回路であって、
上記第２の加算回路は、上記第１の加算回路から出力される２つの信号のそれぞれ異なるビット範囲を加算する複数の加算ユニットを有する、請求項１乃至６の何れか一に記載の加算回路である、
乗算加算回路。
【請求項１３】
上記第２の加算回路は、
上記２つの信号の最下位桁から所定の中位桁までのビット範囲を加算する請求項４に記載の第１の加算ユニットと、
上記２つの信号の上記中位桁から所定の上位桁までのビット範囲を加算する請求項４に記載の第２の加算ユニットと、
上記２つの信号の上記上位桁から最上位桁までのビット範囲を加算する請求項５に記載の第３の加算ユニットと、を含む、
請求項１２に記載の乗算加算回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は加算回路に係り、特に、乗算回路又は乗算加算回路の最終段に用いられる加算回路に関するものである。
【背景技術】
【０００２】
一般に乗算回路は、図１６に示すような筆算による乗算と同様に、まず乗数の各ビットと被乗数との部分積を計算し、これらの部分積を加算することにより乗算結果を得る構成を有している。
【０００３】
部分積の加算回路には、加算器の段数増加に伴うキャリー信号の伝播遅延を抑えるために、例えばワレスの木（Wallace tree）と称される加算回路が用いられる。ワレスの木は、全加算器をツリー状に接続して構成された回路であり、図１６に示すように、多数の部分積を最終的に２つの信号にまとめる働きを有する。ワレスの木では、加算に伴うキャリー信号の伝播が部分的にしか行われないため、キャリー信号の伝播遅延が抑えられる。
【０００４】
乗算結果は、ワレスの木より出力される２つの信号を、最終段の加算回路において加算することにより得られる。ワレスの木で残されたキャリー信号の伝播はこの最終段の加算によって実行されるため、最終段の加算回路にはキャリー信号を高速に伝播する能力が要求される。
【０００５】
このような乗算回路の最終段の加算回路として、例えば、次に述べるような回路が用いられる。
【０００６】
（１）リプル・キャリー・アダー（ripple carry adder）
リプル・キャリー・アダーは、入力信号の各桁を全加算器によって加算する回路であり、下位の全加算器から出力されるキャリー信号を上位の全加算器へ順に伝播させることにより和出力を得るものである。キャリー信号が１ビットずつ伝播するため、桁上げ速度が遅いという欠点がある。しかしながら、以降に述べる加算回路と比較して回路構成が単純であり、消費電力が少ないという利点もある。
【０００７】
（２）キャリー・ルックアヘッド・アダー（carry look ahead adder）
キャリー・ルックアヘッド・アダーは、上位のキャリー信号の一部を桁上げ先見回路によって生成することにより、キャリー信号の生成を高速化した加算回路である。例えばリプル・キャリー・アダーに桁上げ先見回路を用いることにより、キャリー信号の伝播遅延を改善することができる。
【０００８】
図１７は、４桁のキャリー・ルックアヘッド・アダーの構成例を示すブロック図である。
図１７において、全加算器２０１〜２０４は、入力信号の第０桁〜第３桁の加算を行う回路であり、ＡＮＤ回路２０５〜２０９およびセレクタ２１０で構成される回路は、第３桁のキャリー信号ｃ３を生成する桁上げ先見回路である。
【０００９】
全加算器２０１，…，２０４は、第０桁のビット信号（ａ０，ｂ０），…，第３桁の信号（ａ３，ｂ３）をそれぞれ入力するとともに、キャリー信号ＣＩＮ，ｃ０，ｃ１，ｃ２をそれぞれ入力し、和信号ｓ０，…，ｓ３およびキャリー信号ｃ０，…，ｃ３をそれぞれ出力する。ただし、全加算器２０１，２０２，２０３より出力されるキャリー信号ｃ０，ｃ１，ｃ２は、それぞれ上位桁の全加算器２０２，２０３，２０４へ入力される。
【００１０】
また、全加算器２０１，…，２０４は、和信号およびキャリー信号を算出する過程において、キャリー伝播信号ｐ０，…，ｐ３およびキャリー生成信号ｇ０，…，ｇ３をそれぞれ生成する。キャリー伝播信号ｐ０，…，ｐ３は、各桁のビット信号の排他的論理和であり、キャリー生成信号ｇ０，…，ｇ３は、各桁のビット信号の論理積である。
【００１１】
桁上げ先見回路は、このキャリー伝播信号ｐ０，…，ｐ３およびキャリー伝播信号ｐ０，…，ｐ３に基づいて、第３桁のキャリー信号ｃ３を生成する。
すなわち、４入力ＡＮＤ回路２０５はキャリー伝播信号ｐ３，ｐ２，ｐ１およびキャリー生成信号ｇ０の論理積を、３入力ＡＮＤ回路２０６はキャリー伝播信号ｐ３，ｐ２およびキャリー生成信号ｇ１の論理積を、２入力ＡＮＤ回路２０８はキャリー伝播信号ｐ３およびキャリー生成信号ｇ２の論理積をそれぞれ演算する。４入力ＯＲ回路２０８は、これら３つの論理積とキャリー生成信号ｇ３との論理和を演算する。セレクタ２１０は、４入力ＡＮＤ回路２０９においてキャリー伝播信号ｐ０，…，ｐ３の論理積を演算した結果が‘０’の場合、４入力ＯＲ回路２０８の論理和を出力し、４入力ＡＮＤ回路２０９の論理積が‘１’の場合、キャリー信号ＣＩＮを出力する。このセレクタ２１０の出力信号が、キャリー信号ｃ３として上位桁の演算に用いられる。
【００１２】
キャリー・ルックアヘッド・アダーは、キャリー信号の計算を複数の回路で並列に行うため、キャリー信号の生成は高速であるが、回路規模および消費電力が増大する欠点を持つ。
【００１３】
（３）キャリー・セレクト・アダー（carry select adder）
キャリー・セレクト・アダーは、下位からのキャリー信号が‘０’の場合と‘１’の場合の２通りの加算結果を予め計算し、当該キャリー信号が到着したところで２通りの加算結果の一方をセレクタにより選択して出力する回路である。各桁の加算回路には、例えば上述したリプル・キャリー・アダーが用いられる。
入力信号に比べて下位からのキャリー信号が遅い場合、特に、キャリー信号の到着前に各桁の加算結果の予測値が得られる場合には、キャリー信号の到着とともにセレクタから加算結果を出力することができるため、キャリー・セレクト・アダーは高速である。しかしながら、内部に２通りの加算を行う回路を含むため、回路規模および消費電力が増大する欠点を持つ。
【００１４】
（４）キャリー・セレクト・アダー＋キャリー・ルックアヘッド・アダー
図１８は、全ビットの和出力をキャリー・セレクト・アダー２１１〜２１３によって算出するとともに、上位のキャリー信号ｃ３１を桁上げ先見回路２１４によって生成する加算回路である。このように、キャリー・セレクト・アダーとキャリー・ルックアヘッド・アダーとを組み合わせることにより和信号とキャリー信号を何れも高速に生成することが可能であるが、桁上げ先見回路を余分に必要とするため、キャリー・セレクト・アダーよりも更に回路規模および消費電力が増大する。
【００１５】
（５）１レベルのキャリー・インクリメント・アダー（carry increment adder）
キャリー・インクリメント・アダーは、局所的なキャリー生成信号およびキャリー伝播信号を下位から上位に向かって順番に生成する回路をそれぞれ有しており、下位からのキャリー信号が到着した場合に、この局所的なキャリー生成信号およびキャリー伝播信号を用いて各桁のキャリー信号および和信号を計算する。１レベルのキャリー・インクリメント・アダーは、こうした局所的なキャリー生成信号およびキャリー伝播信号の生成回路をそれぞれ１重に持つものである。
１レベルのキャリー・インクリメント・アダーは、キャリー・セレクト・アダーに比べて和出力の生成が若干遅いものの、リプル・キャリー・アダーに相当する回路が１系列分で済むため、回路規模および消費電力についてはキャリー・セレクト・アダーより小さくなる。
【００１６】
（６）２レベルのキャリー・インクリメント・アダー
１レベルのキャリー・インクリメント・アダーでは、加算するビット長が長くなると、局所的なキャリー生成信号およびキャリー伝播信号の生成が下位からのキャリー信号の到着より遅れてしまう場合が生じ得る。この欠点を改良するため、２レベルのキャリー・インクリメント・アダーは、局所的なキャリー生成信号およびキャリー伝播信号の生成回路をそれぞれ２重に持ち、これらの局所的信号の生成を並列に実行させることにより、上述した遅延を抑えるものである。
【発明の開示】
【発明が解決しようとする課題】
【００１７】
図１９は、上述した従来の加算回路の性能を速度、消費電力、回路面積の点で比較した図である。図１９において‘○’は性能が優れていることを示し、‘×’は性能が劣っていることを示し、‘△’は中間の性能であることを示す。
図１９に示すように、従来の加算回路では、速度を重視すると消費電力や回路面積が大きくなってしまう傾向があり、その両方を良好に保つことが困難であるという不利益が存在する。
【００１８】
本発明はかかる事情に鑑みてなされたものであり、その目的は、消費電力を増大させることなく高速に加算を実行できる加算回路と、そのような加算回路を有する乗算回路を提供することにある。
【課題を解決するための手段】
【００１９】
上記の目的を達成する第１の発明の加算回路は、入力される加算対象の信号のそれぞれ異なるビット範囲を加算する複数の加算ユニットを有し、上記複数の加算ユニットの少なくとも２つは、その加算を行うビット範囲において加算対象のビット信号の入力タイミングが上位桁に向かうにつれて変化する当該変化の傾向にそれぞれ適合した加算方式であって、各桁の加算値の算出タイミングが上位桁に向かうにつれて変化する傾向に違いを有する異なる加算方式により加算を行う。
【００２０】
好適には、上記複数の加算ユニットは、ビット信号の入力タイミングが上位桁に向かうにつれて遅延する傾向を有する第１のビット範囲の入力信号に対して、上記加算値算出タイミングが上位桁に向かうにつれて遅延する第１の加算方式により加算を行う第１の加算ユニットと、上記入力タイミングが上位桁に向かうにつれて上記第１のビット範囲より緩やかに遅延するか若しくは早くなる傾向を有する第２のビット範囲の入力信号に対して、上記加算値算出タイミングが上位桁に向かうにつれて上記第１の加算方式より緩やかに遅延する第２の加算方式により加算を行う第２の加算ユニットとを含む。
【００２１】
この第１の加算ユニットおよび第２の加算ユニットは、第Ｋ桁（Ｋは正の整数を示す）へのキャリー信号に応じて第ｉ桁（ｉは、ｉ＞Ｋを満たす整数を示す）で生じるキャリー信号が変化するか否かを示すキャリー伝播信号ｐ（ｉ，Ｋ）を前段からのキャリー伝播信号ｐ（ｉ−１，Ｋ）に基づいて生成する、縦続に接続された複数の回路を含む第１のキャリー伝播信号生成回路と、第Ｋ桁へのキャリー信号に依存せずに第ｉ桁で生じるキャリー信号が所定のビット値になるか否かを示すキャリー生成信号ｇ（ｉ，Ｋ）を前段からのキャリー生成信号ｇ（ｉ−１，Ｋ）に基づいて生成する、縦続に接続された複数の回路を含む第１のキャリー生成信号生成回路と、上記第１のキャリー伝播信号生成回路より出力されるキャリー伝播信号ｐ（ｉ，Ｋ）と、上記第１のキャリー生成信号生成回路より出力されるキャリー生成信号ｇ（ｉ，Ｋ）と、第Ｋ桁へのキャリー信号にとに基づいて、第ｉ桁で生じるキャリー信号を生成するキャリー信号生成回路とを含んでも良い。
【００２２】
また、第ｋのキャリー伝播信号生成回路（ｋは、２以上の整数を示す）は、第（ｋ−１）のキャリー伝播信号生成回路の縦続接続回路の終段から出力されるキャリー伝播信号ｐ（Ｍ２，Ｍ１）（Ｍ２，Ｍ１は、Ｍ２＞Ｍ１を満たす正の整数を示す）と、前段からのキャリー伝播信号ｐ（Ｍ１−１，Ｍ０）（Ｍ０は、Ｍ１＞Ｍ０を満たす正の整数を示す）とに基づいてキャリー伝播信号ｐ（Ｍ２，Ｍ０）を生成する、縦続に接続された複数の回路を含む回路であり、第ｋのキャリー生成信号生成回路は、第（ｋ−１）のキャリー生成信号生成回路の縦続接続回路の終段から出力されるキャリー生成信号ｇ（Ｍ２，Ｍ１）と、前段からのキャリー生成信号ｇ（Ｍ１−１，Ｍ０）とに基づいてキャリー生成信号ｇ（Ｍ２，Ｍ０）を生成する、縦続に接続された複数の回路を含む回路であるとする。
この場合、上記第１の加算ユニットは、ｋが最大でｍ（ｍは、１以上の整数を示す）までの第ｋのキャリー伝播信号生成回路および第ｋのキャリー生成信号生成回路を含み、上記第２の加算ユニットは、ｋが最大でｎ（ｎは、ｍより大きい整数を示す）までの第ｋのキャリー伝播信号生成回路および第ｋのキャリー生成信号生成回路を含んでも良い。
【００２３】
また、上記複数の加算ユニットは、上記入力タイミングが上位桁に向かうにつれて早くなる傾向を有するビット範囲の入力信号に対して、当該ビット範囲に供給される下位桁からのキャリー信号のそれぞれの仮定値に対応する各桁のキャリー信号の予測値を予め算出し、当該下位桁から供給されるキャリー信号と当該予測値とに基づいて各桁のキャリー信号を生成する第３の加算方式により加算を行う第３の加算ユニットを含んでも良い。
【００２４】
また、上記複数の加算ユニットは、上記入力タイミングが上位桁に向かうにつれて遅延する傾向を有するビット範囲の入力信号に対して、下位桁から上位桁に向かって順番にキャリー信号を算出する第４の加算方式により加算を行う第４の加算ユニットを含んでも良い。
【００２５】
上記の目的を達成する第２の発明は、２を超える複数の部分積を加算した結果として２つの信号を出力する第１の加算回路と、上記第１の加算回路から出力される２つの信号を加算する第２の加算回路とを有する乗算回路であり、上記第２の加算回路として、上記第１の加算回路から出力される２つの信号のそれぞれ異なるビット範囲を加算する複数の加算ユニットを有した、上記第１の発明の加算回路を有する。
【００２６】
上記第２の加算回路は、上記２つの信号の最下位桁から所定の中位桁までのビット範囲を加算する上記第１の加算ユニットと、上記２つの信号の上記中位桁から所定の上位桁までのビット範囲を加算する上記第２の加算ユニットと、上記２つの信号の上記上位桁から最上位桁までのビット範囲を加算する上記第３の加算ユニットとを含んでも良い。
【００２７】
また、上記第２の加算回路は、最下位桁の加算結果として上記２つの信号のうちの一方の最下位桁のビット信号を出力するとともに、当該最下位桁の上位桁の加算結果として当該上位桁のビット信号同士の排他的論理和を出力しても良い。
【００２８】
更には、上記第２の加算回路は、最上位桁の加算結果として下位桁から最上位桁へのキャリー信号の論理反転信号を出力しても良い。
この乗算回路は、乗算加算回路としても構成され得る。
【発明の効果】
【００２９】
本発明の加算回路によれば、回路規模と消費電力を低減しつつ高速に加算を行うことができる。
また、本発明の乗算回路又は乗算加算回路によれば、回路規模と消費電力を低減しつつ高速に乗算を行うことができる。
【発明を実施するための最良の形態】
【００３０】
以下、本発明の５つの実施形態について、図面を参照して説明する。
【００３１】
＜第１の実施形態＞
図１は、本発明の第１の実施形態に係る乗算回路の構成の一例を示すブロック図である。
図１に例示する乗算回路は、部分積生成回路１００と、第１の加算回路１０１と、第２の加算回路１０２とを有する。
第１の加算回路１０１は、本発明の第１の加算回路の一実施形態である。
第２の加算回路１０２は、本発明の第２の加算回路の一実施形態である。
【００３２】
部分積生成回路１００は、乗数および被乗数の信号Ｄ１およびＤ２を入力し、２を超える複数の部分積ｐ１〜ｐＸを生成する。部分積生成回路１００は、例えばブース（Booth）の符号化などの方法によりこれらの部分積を生成する。
【００３３】
第１の加算回路１０１は、部分積生成回路１００より出力される複数の部分積ｐ１〜ｐＸを加算した結果として２つの信号ＡおよびＢを出力する。第１の加算回路１０１は、例えば、ワレスの木のように全加算器をツリー状に接続した構成や、他の並列型乗算器における部分積の加算回路と同様な構成を有する。
【００３４】
第２の加算回路１０２は、第１の加算回路１０１より出力される信号ＡおよびＢを加算し、加算結果Ｓを出力する。
【００３５】
被乗数をＬビット、乗数をＭビットとすると、部分積生成回路１００はＭ個の部分積を生成する。第１の加算回路１０１は、このＭ個の部分積が最終的に２つの信号ＡおよびＢになるまで加算を行う。例えばワレスの木による加算を行う場合、キャリー信号の伝播が完全には行われないため、第１の加算回路１０１の出力が最も遅れる桁は上位桁でなく加算段数の多い中央部の桁（図１６参照）である。こうした特徴はワレスの木による加算に限らず、全加算器などを用いる他の並列型乗算器における部分積の加算回路においても同様である。
【００３６】
図２は、４０ビットの信号出力を有するワレスの木の出力遅延の一例を図解した図である。横軸は第０桁〜第３９桁までの各桁を番号で表しており、縦軸は出力信号の遅延時間を表している。図に示すように、下位側のビット範囲では上位桁に向かうほど遅延が大きくなり、中央部のビット範囲では遅延が最も大きい状態でほぼ一定となり、上位側のビット範囲では上位桁に向かうほど遅延が小さくなる傾向を有している。
【００３７】
第２の加算回路１０２は、こうした前段回路の出力信号の遅延傾向に合わせて、下位，中位，上位の各ビット範囲をそれぞれ異なる加算方式により加算する。
すなわち、ビット信号の入力タイミングが上位桁に向かうにつれて遅くなる傾向を有する下位ビット範囲の入力信号に対しては、加算値の算出タイミングが上位桁に向かうにつれて遅延する第１の加算方式により加算を行う。
ビット信号の入力タイミングが上位桁に向かうにつれて上記下位ビット範囲より緩やかに遅延するか若しくは早くなる傾向を有する中位ビット範囲の入力信号に対しては、上記加算値算出タイミングが上位桁に向かうにつれて上記第１の加算方式より緩やかに遅延する第２の加算方式により加算を行う。
また、ビット信号の入力タイミングが上位桁に向かうにつれて早くなる傾向を有する上位ビット範囲の入力信号に対しては、上記中位ビット範囲から供給されるキャリー信号が‘０’の場合と‘１’の場合のそれぞれに対応する各桁のキャリー信号，和信号の予測値を予め算出し、当該キャリー信号と当該予測値とに基づいて各桁のキャリー信号，和信号を生成する第３の加算方式により加算を行う。
【００３８】
次に、図３〜図１０を参照して、第２の加算回路１０２の詳細な構成を説明する。
【００３９】
以下では、一例として、第１の加算回路１０１に入力される加算対象の入力信号ＡおよびＢ、ならび第１の加算回路１０１から出力される和信号Ｓをそれぞれ４０ビットとする。
【００４０】
また、各信号を次の記号で表す。
入力信号Ａ，入力信号Ｂ，和信号Ｓの第０桁〜第３９桁のビット信号をそれぞれ‘ａ０’〜‘ａ３９’，‘ｂ０’〜‘ｂ３９’，‘ｓ０’〜‘ｓ３９’とする。
第０桁〜第３９桁で生じるキャリー信号をそれぞれ‘ｃ０’〜‘ｃ３９’とする。
第０桁に供給されるキャリー信号を‘ＣＩＮ’とする。
第ｊ桁（ここで、ｊは０から３９までの整数を示す）のビット信号ａｊおよびｂｊの排他的論理和に相当する第ｊ桁のキャリー伝播信号を‘ｐｊ’とする。
第ｊ桁（同様に、ｊは０から３９までの整数を示す）のビット信号ａｊおよびｂｊの論理積に相当する第ｊ桁のキャリー生成信号を‘ｇｊ’とする。
【００４１】
更に、次の信号を定義する
キャリー伝播信号ｐｉ＿Ｋは、第Ｋ桁（Ｋは正の整数を示す）へのキャリー信号ｃ（Ｋ−１）に応じて第ｉ桁（ｉは、ｉ＞Ｋを満たす整数を示す）で生じるキャリー信号ｃｉが変化するか否かを示す信号である。
キャリー生成信号ｇｉ＿Ｋは、第Ｋ桁へのキャリー信号ｃ（Ｋ−１）に依存せずに第ｉ桁で生じるキャリー信号ｃｉが‘１’になるか否かを示す信号である。
キャリー伝播信号ｐｉ＿Ｋおよびキャリー生成信号ｇｉ＿Ｋは、それぞれ次式で表される。
【００４２】
【数１】
2005182346.tif 000003
【００４３】
なお、ｉ＝Ｋの場合、キャリー伝播信号ｐｉ＿Ｋはキャリー伝播信号ｐｉと等しいものとし、キャリー生成信号ｇｉ＿Ｋはキャリー生成信号ｇｉと等しいものとする。
【００４４】
式（１）から分かるように、キャリー伝播信号ｐｉ＿Ｋが‘１’の場合、入力ビット信号（ａＫ，ｂＫ），…，（ａｉ，ｂｉ）は何れも一方が‘１’で他方が‘０’となる。そのため、キャリー信号ｃ（Ｋ−１）が‘１’になるとキャリー信号ｃｉが‘１’になり、キャリー信号ｃ（Ｋ−１）が‘０’になるとキャリー信号ｃｉが‘０’になる。すなわち、キャリー信号ｃ（Ｋ−１）に応じてキャリー信号ｃｉが変化する。一方、キャリー伝播信号ｐｉ＿Ｋが‘０’の場合、両方が‘０’または両方が‘１’となる入力ビット信号（ａｊ，ｂｊ）（ここで、ｊはＫからｉまでの整数を示す）が存在するため、キャリー信号ｃ（Ｋ−１）の変化はこのビットを超えて第ｉ桁に伝播しない。
【００４５】
また、式（２）から分かるように、キャリー生成信号ｇｉ＿Ｋが‘１’の場合、第Ｋ桁から第ｉ桁の間には、入力ビット信号（ａｊ，ｂｊ）が両方‘１’となる桁が少なくとも１つ存在し、この桁より第ｉ桁までの各桁のビット信号は少なくとも一方が‘１’になる。したがって、この場合、キャリー信号ｃ（Ｋ−１）がどのような値でもキャリー信号ｃｉが‘１’になる。一方、キャリー生成信号ｇｉ＿Ｋが‘０’の場合は、キャリー信号ｃ（Ｋ−１）がどのような値でもキャリー信号ｃｉが‘０’になるか、あるいはキャリー信号ｃ（Ｋ−１）に応じてキャリー信号ｃｉが変化する（すなわちｐｉ＿Ｋ＝‘１’）。
【００４６】
図３は、第２の加算回路１０２の構成の一例を示すブロック図である。
【００４７】
第２の加算回路１０２は、例えば図３に示すように、第０桁から第１５桁までの下位ビット範囲の加算を行う１レベルのキャリー・インクリメント・アダー１と、第１６桁から第３０桁までの中位ビット範囲の加算を行う２レベルのキャリー・インクリメント・アダー２と、第３１桁から第３９桁までの上位ビット範囲の加算を行うキャリー・セレクト・アダー３とを有する。以降、キャリー・インクリメント・アダーをＣＩＡ、キャリー・セレクト・アダーをＣＳＡと略記する
ＣＩＡ１は、本発明の第１の加算ユニットの一実施形態である。
ＣＩＡ２は、本発明の第２の加算ユニットの一実施形態である。
ＣＳＡ３は、本発明の第３の加算ユニットの一実施形態である。
【００４８】
図４は、ＣＩＡ１の構成の一例を示すブロック図である。
【００４９】
ＣＩＡ１は、例えば図４に示すように、ＡＮＤ回路１０＿１，…，１０＿１５の縦続接続回路と、ＡＮＤ−ＯＲ複合回路１２＿１，…，１２＿１５の縦続接続回路と、キャリー信号ｃ０，…，ｃ１５を出力するＡＮＤ−ＯＲ複合回路１１＿０，…，１１＿１５と、和信号ｓ０，…，ｓ１５を出力する排他的ＯＲ回路１３＿０，…，１３＿１５と、キャリー生成信号ｇ０，…，ｇ１５を出力するＡＮＤ回路１４＿０，…，１４＿１５と、キャリー伝播信号ｐ０，…，ｐ１５を出力する排他的ＯＲ回路１５＿０，…，１５＿１５とを有する。
ＡＮＤ回路１０＿１，…，１０＿１５の縦続接続回路は、本発明の第１のキャリー伝播信号生成回路の一実施形態である。
ＡＮＤ−ＯＲ複合回路１２＿１，…，１２＿１５の縦続接続回路は、本発明の第１のキャリー生成信号生成回路の一実施形態である。
ＡＮＤ−ＯＲ複合回路１１＿０，…，１１＿１５は、本発明のキャリー信号生成回路の一実施形態である。
【００５０】
この図４を参照して、ＣＩＡ１の各構成要素の接続関係を説明する。
【００５１】
ＡＮＤ回路１０＿１は、キャリー伝播信号ｐ０およびｐ１の論理積を演算し、その演算結果をキャリー伝播信号ｐ１＿０として出力する。
ＡＮＤ回路１０＿ｊ（ここで、ｊは２から１５までの整数を示す）は、前段のＡＮＤ回路１０＿（ｊ−１）より出力されるキャリー伝播信号ｐ（ｊ−１）＿０とキャリー伝播信号ｐｊとの論理積を演算し、その演算結果をキャリー伝播信号ｐｊ＿０として出力する。
【００５２】
ＡＮＤ−ＯＲ複合回路１２＿１は、キャリー生成信号ｇ０とキャリー伝播信号ｐ１との論理積とキャリー生成信号ｇ１との論理和を演算し、その演算結果をキャリー生成信号ｇ１＿０として出力する。
ＡＮＤ−ＯＲ複合回路１２＿ｊ（ここで、ｊは２から１５までの整数を示す）は、前段のＡＮＤ−ＯＲ複合回路１２＿（ｊ−１）より出力されるキャリー生成信号ｇ（ｊ−１）＿０とキャリー伝播信号ｐｊとの論理積とキャリー生成信号ｇｊとの論理和を演算し、その演算結果をキャリー生成信号ｇｊ＿０として出力する。
【００５３】
ＡＮＤ−ＯＲ複合回路１１＿０は、キャリー信号ＣＩＮとキャリー伝播信号ｐ０との論理積とキャリー生成信号ｇ０との論理和を演算し、その演算結果をキャリー信号ｃ０として出力する。
ＡＮＤ−ＯＲ複合回路１１＿ｊ（ここで、ｊは１から１５までの整数を示す）は、キャリー信号ＣＩＮとキャリー伝播信号ｐｊ＿０との論理積とキャリー生成信号ｇｊ＿０との論理和を演算し、その演算結果をキャリー信号ｃｊとして出力する。
【００５４】
排他的ＯＲ回路１３＿０は、キャリー信号ＣＩＮとキャリー伝播信号ｐ０との排他的論理和を演算し、その演算結果を和信号ｓ０として出力する。
排他的ＯＲ回路１３＿ｊ（ここで、ｊは１から１５までの整数を示す）は、キャリー信号ｃ（ｊ−１）とキャリー伝播信号ｐｊとの排他的論理和を演算し、その演算結果を和信号ｓｊとして出力する。
【００５５】
ＡＮＤ回路１４＿ｊ（ここで、ｊは０から１５までの整数を示す）は、入力ビット信号ａｊおよびｂｊの論理積を演算し、その演算結果をキャリー生成信号ｇｊとして出力する。
【００５６】
排他的ＯＲ回路１５＿ｊ（ここで、ｊは０から１５までの整数を示す）は、入力ビット信号ａｊおよびｂｊの排他的論理和を演算し、その演算結果をキャリー伝播信号ｐｊとして出力する。
以上が、ＣＩＡ１の各構成要素の説明である。
【００５７】
図５および図６は、ＣＩＡ２の構成の一例を示すブロック図である。
【００５８】
ＣＩＡ２は、例えば図５および図６に示すように、ＡＮＤ−ＯＲ複合回路２０＿０，…，２０＿３の縦続接続回路と、ＡＮＤ−ＯＲ複合回路２０＿０に接続されるＡＮＤ−ＯＲ複合回路２１＿０と、ＡＮＤ−ＯＲ複合回路２０＿１に接続されるＡＮＤ−ＯＲ複合回路２１＿１と、ＡＮＤ−ＯＲ複合回路２０＿２に接続されるＡＮＤ−ＯＲ複合回路２１＿２，…，２１＿４の縦続接続回路と、ＡＮＤ−ＯＲ複合回路２０＿３に接続されるＡＮＤ−ＯＲ複合回路２１＿５，…，２１＿９の縦続接続回路と、ＡＮＤ回路２２＿０，…，２２＿３の縦続接続回路と、ＡＮＤ回路２２＿０に接続されるＡＮＤ回路２３＿０と、ＡＮＤ回路２２＿１に接続されるＡＮＤ回路２３＿１と、ＡＮＤ回路２２＿２に接続されるＡＮＤ回路２３＿２，…，２３＿４の縦続接続回路と、ＡＮＤ回路２２＿３に接続されるＡＮＤ回路２３＿５，…，２３＿９の縦続接続回路と、キャリー信号ｃ１６，…，ｃ３０を出力するＡＮＤ−ＯＲ複合回路２４＿０，…，２４＿１４と、和信号ｓ１６，…，ｓ３０を出力する排他的ＯＲ回路２５＿０，…，２５＿１４と、キャリー生成信号ｇ１６，…，ｇ３０を出力するＡＮＤ回路２６＿０，…，２６＿１４と、キャリー伝播信号ｐ１６，…，ｐ３０を出力する排他的ＯＲ回路２７＿０，…，２７＿１４とを有する。
ＡＮＤ−ＯＲ複合回路２０＿０，…，２０＿３の縦続接続回路は、本発明の第２のキャリー生成信号生成回路の一実施形態である。
ＡＮＤ−ＯＲ複合回路２１＿０、ＡＮＤ−ＯＲ複合回路２１＿１、ＡＮＤ−ＯＲ複合回路２１＿２，…，２１＿４の縦続接続回路、およびＡＮＤ−ＯＲ複合回路２１＿５，…，２１＿９の縦続接続回路は、本発明の第１のキャリー生成信号生成回路の一実施形態である。
ＡＮＤ回路２２＿０，…，２２＿３の縦続接続回路は、本発明の第２のキャリー伝播信号生成回路の一実施形態である。
ＡＮＤ回路２３＿０、ＡＮＤ回路２３＿１、ＡＮＤ回路２３＿２，…，２３＿４の縦続接続回路、およびＡＮＤ回路２３＿５，…，２３＿９の縦続接続回路は、本発明の第１のキャリー伝播信号生成回路の一実施形態である。
ＡＮＤ−ＯＲ複合回路２４＿０，…，２４＿１４は、本発明のキャリー信号生成回路の一実施形態である。
【００５９】
また図７は、ＣＩＡ２において局所的なキャリー伝播信号およびキャリー生成信号の生成に関わる部分の接続関係を示すブロック図であり、図８は、ＣＩＡ２においてキャリー信号の生成に関わる部分の接続関係を示すブロック図である。
ただし、図５〜図８の同一符号は同一の構成要素を示す。
【００６０】
この図５〜図８を参照して、ＣＩＡ２の各構成要素の接続関係を説明する。
【００６１】
ＡＮＤ回路２３＿０は、キャリー伝播信号ｐ１７およびｐ１８の論理積を演算し、その演算結果をキャリー伝播信号ｐ１８＿１７として出力する。
ＡＮＤ回路２２＿０は、キャリー伝播信号ｐ１６とキャリー伝播信号ｐ１８＿１７との論理積を演算し、その演算結果をキャリー伝播信号ｐ１８＿１６として出力する。
【００６２】
ＡＮＤ回路２３＿１は、キャリー伝播信号ｐ１９およびｐ２０の論理積を演算し、その演算結果をキャリー伝播信号ｐ２０＿１９として出力する。
ＡＮＤ回路２２＿１は、キャリー伝播信号ｐ１８＿１６とキャリー伝播信号ｐ２０＿１９との論理積を演算し、その演算結果をキャリー伝播信号ｐ２０＿１６として出力する。
【００６３】
ＡＮＤ回路２３＿２は、キャリー伝播信号ｐ２１およびｐ２２の論理積を演算し、その演算結果をキャリー伝播信号ｐ２２＿２１として出力する。
ＡＮＤ回路２３＿ｊ（ここで、ｊは３または４を示す）は、キャリー伝播信号ｐ（２０＋ｊ）とキャリー伝播信号ｐ（１９＋ｊ）＿２１との論理積を演算し、その演算結果をキャリー伝播信号ｐ（２０＋ｊ）＿２１として出力する。
ＡＮＤ回路２２＿２は、キャリー伝播信号ｐ２０＿１６とキャリー伝播信号ｐ２４＿２１との論理積を演算し、その演算結果をキャリー伝播信号ｐ２４＿１６として出力する。
【００６４】
ＡＮＤ回路２３＿５は、キャリー伝播信号ｐ２５およびｐ２６の論理積を演算し、その演算結果をキャリー伝播信号ｐ２６＿２５として出力する。
ＡＮＤ回路２３＿ｊ（ここで、ｊは６から９までの整数を示す）は、キャリー伝播信号ｐ（２１＋ｊ）とキャリー伝播信号ｐ（２０＋ｊ）＿２５との論理積を演算し、その演算結果をキャリー伝播信号ｐ（２１＋ｊ）＿２５として出力する。
ＡＮＤ回路２２＿３は、キャリー伝播信号ｐ３０＿２５とキャリー伝播信号ｐ２４＿１６との論理積を演算し、その演算結果をキャリー伝播信号ｐ３０＿１６として出力する。
【００６５】
ＡＮＤ−ＯＲ複合回路２１＿０は、キャリー伝播信号ｐ１８とキャリー生成信号ｇ１７との論理積とキャリー生成信号ｇ１８との論理和を演算し、その演算結果をキャリー生成信号ｇ１８＿１７として出力する。
ＡＮＤ−ＯＲ複合回路２０＿０は、キャリー伝播信号ｐ１８＿１７とキャリー生成信号ｇ１６との論理積とキャリー生成信号ｇ１８＿１７との論理和を演算し、その演算結果をキャリー生成信号ｇ１８＿１６として出力する。
【００６６】
ＡＮＤ−ＯＲ複合回路２１＿１は、キャリー伝播信号ｐ２０とキャリー生成信号ｇ１９との論理積とキャリー生成信号ｇ２０との論理和を演算し、その演算結果をキャリー生成信号ｇ２０＿１９として出力する。
ＡＮＤ−ＯＲ複合回路２０＿１は、キャリー伝播信号ｐ２０＿１９とキャリー生成信号ｇ１８＿１６との論理積とキャリー生成信号ｇ２０＿１９との論理和を演算し、その演算結果をキャリー生成信号ｇ２０＿１６として出力する。
【００６７】
ＡＮＤ−ＯＲ複合回路２１＿２は、キャリー伝播信号ｐ２２とキャリー生成信号ｇ２１との論理積とキャリー生成信号ｇ２２との論理和を演算し、その演算結果をキャリー生成信号ｇ２２＿２１として出力する。
ＡＮＤ−ＯＲ複合回路２１＿ｊ（ここで、ｊは３または４を示す）は、キャリー伝播信号ｐ（２０＋ｊ）とキャリー生成信号ｇ（１９＋ｊ）＿２１との論理積とキャリー生成信号ｇ（２０＋ｊ）との論理和を演算し、その演算結果をキャリー生成信号ｇ（２０＋ｊ）＿２１として出力する。
ＡＮＤ−ＯＲ複合回路２０＿２は、キャリー伝播信号ｐ２４＿２１とキャリー生成信号ｇ２０＿１６との論理積とキャリー生成信号ｇ２４＿２１との論理和を演算し、その演算結果をキャリー生成信号ｇ２４＿１６として出力する。
【００６８】
ＡＮＤ−ＯＲ複合回路２１＿５は、キャリー伝播信号ｐ２６とキャリー生成信号ｇ２５との論理積とキャリー生成信号ｇ２６との論理和を演算し、その演算結果をキャリー生成信号ｇ２６＿２５として出力する。
ＡＮＤ−ＯＲ複合回路２１＿ｊ（ここで、ｊは６から９までの整数を示す）は、キャリー伝播信号ｐ（２１＋ｊ）とキャリー生成信号ｇ（２０＋ｊ）＿２５との論理積とキャリー生成信号ｇ（２１＋ｊ）との論理和を演算し、その演算結果をキャリー生成信号ｇ（２１＋ｊ）＿２５として出力する。
ＡＮＤ−ＯＲ複合回路２０＿３は、キャリー伝播信号ｐ３０＿２５とキャリー生成信号ｇ２４＿１６との論理積とキャリー生成信号ｇ３０＿２５との論理和を演算し、その演算結果をキャリー生成信号ｇ３０＿１６として出力する。
【００６９】
ＡＮＤ−ＯＲ複合回路２４＿０は、キャリー伝播信号ｐ１６とキャリー信号Ｃ１５との論理積とキャリー生成信号ｇ１６との論理和を演算し、その演算結果をキャリー信号ｃ１６として出力する。
ＡＮＤ−ＯＲ複合回路２４＿１は、キャリー伝播信号ｐ１７とキャリー信号Ｃ１６との論理積とキャリー生成信号ｇ１７との論理和を演算し、その演算結果をキャリー信号ｃ１７として出力する。
【００７０】
ＡＮＤ−ＯＲ複合回路２４＿２は、キャリー伝播信号ｐ１８＿１６とキャリー信号Ｃ１５との論理積とキャリー生成信号ｇ１８＿１６との論理和を演算し、その演算結果をキャリー信号ｃ１８として出力する。
ＡＮＤ−ＯＲ複合回路２４＿３は、キャリー伝播信号ｐ１９とキャリー信号Ｃ１８との論理積とキャリー生成信号ｇ１９との論理和を演算し、その演算結果をキャリー信号ｃ１９として出力する。
【００７１】
ＡＮＤ−ＯＲ複合回路２４＿４は、キャリー伝播信号ｐ２０＿１６とキャリー信号Ｃ１５との論理積とキャリー生成信号ｇ２０＿１６との論理和を演算し、その演算結果をキャリー信号ｃ２０として出力する。
ＡＮＤ−ＯＲ複合回路２４＿５は、キャリー伝播信号ｐ２１とキャリー信号Ｃ２０との論理積とキャリー生成信号ｇ２１との論理和を演算し、その演算結果をキャリー信号ｃ２１として出力する。
ＡＮＤ−ＯＲ複合回路２４＿ｊ（ここで、ｊは６または７の整数を示す）は、キャリー伝播信号ｐ（１６＋ｊ）＿２１とキャリー信号Ｃ２０との論理積とキャリー生成信号ｇ（１６＋ｊ）＿２１との論理和を演算し、その演算結果をキャリー信号ｃ（１６＋ｊ）として出力する。
【００７２】
ＡＮＤ−ＯＲ複合回路２４＿８は、キャリー伝播信号ｐ２４＿１６とキャリー信号Ｃ１５との論理積とキャリー生成信号ｇ２４＿１６との論理和を演算し、その演算結果をキャリー信号ｃ２４として出力する。
ＡＮＤ−ＯＲ複合回路２４＿９は、キャリー伝播信号ｐ２５とキャリー信号Ｃ２４との論理積とキャリー生成信号ｇ２５との論理和を演算し、その演算結果をキャリー信号ｃ２５として出力する。
ＡＮＤ−ＯＲ複合回路２４＿ｊ（ここで、ｊは１０から１３までの整数を示す）は、キャリー伝播信号ｐ（１６＋ｊ）＿２５とキャリー信号Ｃ２４との論理積とキャリー生成信号ｇ（１６＋ｊ）＿２５との論理和を演算し、その演算結果をキャリー信号ｃ（１６＋ｊ）として出力する。
【００７３】
ＡＮＤ−ＯＲ複合回路２４＿１４は、キャリー伝播信号ｐ３０＿１６とキャリー信号Ｃ１５との論理積とキャリー生成信号ｇ３０＿１６との論理和を演算し、その演算結果をキャリー信号ｃ３０として出力する。
【００７４】
排他的ＯＲ回路２５＿ｊ（ここで、ｊは０から１４までの整数を示す）は、キャリー信号ｃ（１５＋ｊ）とキャリー伝播信号ｐ（１６＋ｊ）との排他的論理和を演算し、その演算結果を和信号ｓ（１６＋ｊ）として出力する。
【００７５】
ＡＮＤ回路２６＿ｊ（ここで、ｊは０から１４までの整数を示す）は、入力ビット信号ａ（１６＋ｊ）およびｂ（１６＋ｊ）の論理積を演算し、その演算結果をキャリー生成信号ｇ（１６＋ｊ）として出力する。
【００７６】
排他的ＯＲ回路２７＿ｊ（ここで、ｊは０から１４までの整数を示す）は、入力ビット信号ａ（１６＋ｊ）およびｂ（１６＋ｊ）の排他的論理和を演算し、その演算結果をキャリー伝播信号ｐ（１６＋ｊ）として出力する。
以上が、ＣＩＡ２の各構成要素の説明である。
【００７７】
図９は、ＣＳＡ３の構成の一例を示すブロック図である。
ＣＳＡ３は、例えば図９に示すように、全加算器３０＿０，…，３０＿８および３１＿０，…，３１＿８と、セレクタ３２＿０，…，３２＿８を有する。
【００７８】
この図９を参照して、ＣＳＡ３の各構成要素の接続関係を説明する。
【００７９】
全加算器３０＿０は、第３１桁のビット信号（ａ３１，ｂ３１）を入力し、キャリー信号ｃ３０が‘０’と仮定した場合における第３１桁の和信号ｓ３１＿０およびキャリー信号ｃ３１＿０を算出する。
全加算器３０＿ｊ（ここで、ｊは１から８までの整数を示す）は、第（３１＋ｊ）桁のビット信号ａ（３１＋ｊ）およびｂ（３１＋ｊ）を入力するとともに、前段の全加算器３０＿（ｊ−１）で算出されたキャリー信号ｃ（３０＋ｊ）＿０を入力し、これに応じた第（３１＋ｊ）桁の和信号ｓ（３１＋ｊ）＿０およびキャリー信号ｃ（３１＋ｊ）＿０を算出する。
【００８０】
全加算器３１＿０は、第３１桁のビット信号（ａ３１，ｂ３１）を入力し、キャリー信号ｃ３０が‘１’と仮定した場合における第３１桁の和信号ｓ３１＿１およびキャリー信号ｃ３１＿１を算出する。
全加算器３１＿ｊ（ここで、ｊは１から８までの整数を示す）は、第（３１＋ｊ）桁のビット信号ａ（３１＋ｊ）およびｂ（３１＋ｊ）を入力するとともに、前段の全加算器３１＿（ｊ−１）で算出されたキャリー信号ｃ（３０＋ｊ）＿１を入力し、これに応じた第（３１＋ｊ）桁の和信号ｓ（３１＋ｊ）＿１およびキャリー信号ｃ（３１＋ｊ）＿１を算出する。
【００８１】
図１０は、全加算器３０＿１，…，３０＿８および３１＿１，…，３１＿８の構成の一例を示すブロック図である。
これらの全加算器は、例えば図１０に示すように、入力ビット信号ａ，ｂの論理積を演算するＡＮＤ回路３５と、入力ビット信号ａ，ｂの排他的論理和を演算する排他的ＯＲ回路３６と、前桁からのキャリー信号ｃｉｎと排他的ＯＲ回路３６より出力されるキャリー伝播信号ｐとの排他的論理和を演算する排他的ＯＲ回路３３と、当該キャリー信号ｃｉｎと当該キャリー伝播信号ｐとの論理積とＡＮＤ回路３５より出力されるキャリー生成信号ｇとの論理和を演算するＡＮＤ−ＯＲ複合回路３４とを有する。排他的ＯＲ回路３３の演算結果が和信号ｓとなり、ＡＮＤ−ＯＲ複合回路３４の演算結果が次桁へのキャリー信号ｃｏｕｔとなる。
【００８２】
なお、全加算器３０＿０および全加算器３１＿０についても図１０と同様の回路で実現可能であるが、前桁からのキャリー信号ｃｉｎが固定値と見なせるため、これよりも回路を簡略化することができる。
例えば全加算器３０＿０では、排他的ＯＲ回路３３を削除し、キャリー伝播信号ｐを和信号ｓとして出力しても良い。また、ＡＮＤ−ＯＲ複合回路３４を削除し、キャリー生成信号ｇをキャリー信号ｃｏｕｔとして出力しても良い。
全加算器３１＿１では、排他的ＯＲ回路３３をＮＯＴ回路に置き換えて、信号ｐの論理反転信号を和信号ｓとして出力しても良い。また、ＡＮＤ−ＯＲ複合回路３４をＯＲ回路に置き換えて、キャリー伝播信号ｐおよびキャリー生成信号ｇの論理和をキャリー信号ｃｏｕｔとして出力しても良い。
【００８３】
セレクタ３２＿ｊ（ここで、ｊは０から８までの整数を示す）は、和信号ｓ（３１＋ｊ）＿０および和信号ｓ（３１＋ｊ）＿１を入力し、キャリー信号ｃ３０が‘０’の場合に和信号ｓ（３１＋ｊ）＿０、キャリー信号ｃ３０が‘１’の場合に和信号ｓ（３１＋ｊ）＿１を選択して出力する。セレクタ３２＿ｊの出力信号が、第（３１＋ｊ）桁の和信号ｓ（３１＋ｊ）となる。
以上が、ＣＳＡ３の各構成要素の説明である。
【００８４】
次に、上述した構成を有する本実施形態に係る乗算回路の動作を説明する。
【００８５】
被乗数および乗数の信号Ｄ１およびＤ２が与えられると、部分積生成回路１００は、図１６に示すような複数個の部分積ｐ１〜ｐＸを生成する。
第１の加算回路１０１は、この部分積ｐ１〜ｐＸを加算して、２つの信号ＡおよびＢを生成する。この際、信号ＡおよびＢの各ビット信号は全ビット同時に生成されるのではなく、図２に示すようにビットごとに異なる遅延時間を経て生成され、第２の加算回路１０２に入力される。すなわち、第２の加算回路１０２への入力タイミングは、下位のビット範囲において上位桁に向かうほど遅くなり、中位のビット範囲においてはほぼ一定となり、上位のビット範囲では上位桁に向かうほど早くなる。
【００８６】
下位のビット範囲（第０桁〜第１５桁）では、図４に示す１レベルのＣＩＡ１によって加算が行われる。
１レベルのＣＩＡ１では、ＡＮＤ回路１０＿１〜１０＿１５の縦続接続回路において下位桁から順番にキャリー伝播信号ｐ１＿０〜ｐ１５＿０が生成されるとともに、ＡＮＤ−ＯＲ複合回路１２＿１〜１２＿１５の縦続接続回路において下位桁から順番にキャリー生成信号ｇ１＿０〜ｇ１５＿０が生成される。そして、このキャリー伝播信号ｐ１＿０〜ｐ１５＿０およびキャリー生成信号ｇ１＿０〜ｇ１５＿０ならびに第０桁へのキャリー信号ＣＩＮに基づいて、下位桁から順番に各桁のキャリー信号ｃ１〜ｃ１５が生成される。
したがって、第１の加算回路１０１からの信号の入力タイミングが上位桁に向かうほど遅くなる傾向と、各桁の加算値の算出タイミングが上位桁に向かうほど遅くなる傾向とが一致している。
【００８７】
中位のビット範囲（第１６桁〜第３０桁）では、図５および図６に示す２レベルのＣＩＡ２によって加算が行われる。
２レベルのＣＩＡ２は、図７に示すように、局所的なキャリー伝播信号およびキャリー生成信号の生成回路をそれぞれ２重に持っている。
すなわち、局所的キャリー伝播信号は、第１のキャリー伝播信号生成回路（ＡＮＤ回路２３＿０、ＡＮＤ回路２３＿１、ＡＮＤ回路２３＿２〜２３＿４の縦続接続回路、ＡＮＤ回路２３＿５〜２３＿９の縦続接続回路）と、第２のキャリー伝播信号生成回路（ＡＮＤ回路２２＿０〜２２＿３の縦続接続回路）とにおいて２段階に分けて生成される。
局所的キャリー生成信号は、第１のキャリー生成信号生成回路（ＡＮＤ−ＯＲ複合回路２１＿０、ＡＮＤ−ＯＲ複合回路２１＿１、ＡＮＤ−ＯＲ複合回路２１＿２〜２１＿４の縦続接続回路、ＡＮＤ−ＯＲ複合回路２１＿５〜２１＿９の縦続接続回路）と、第２のキャリー生成信号生成回路（ＡＮＤ−ＯＲ複合回路２０＿０〜２０＿３の縦続接続回路）とにおいて２段階に分けて生成される。
【００８８】
第１段階の回路（第１のキャリー伝播信号生成回路、第１のキャリー生成信号生成回路）は、各桁のビット信号に基づいて局所的なキャリー伝播信号，キャリー生成信号を直接生成する。
例えば、ＡＮＤ回路２３＿５〜２３＿９の縦続接続回路は、第２５桁〜第３０桁のキャリー伝播信号ｐ２５〜ｐ３０に基づいてキャリー生成信号ｇ２６＿２５〜ｇ３０＿２５を直接生成する。
【００８９】
第２段階の回路（第２のキャリー伝播信号生成回路、第２のキャリー生成信号生成回路）は、第１段階の回路の終段から出力される信号を用いて、局所的なキャリー伝播信号，キャリー生成信号を生成する。
例えば、ＡＮＤ回路２２＿３は、ＡＮＤ回路２３＿５〜２３＿９の縦続接続回路の終段から出力されるキャリー伝播信号ｐ３０＿２５と、前段のＡＮＤ回路２２＿２から出力されるキャリー伝播信号ｐ２４＿１６とに基づいて、キャリー伝播信号ｐ３０＿１６を生成する。
１段のみの回路も縦続接続回路と見なせば、ＡＮＤ回路２２＿０，２２＿１、ＡＮＤ−ＯＲ複合回路２０＿０，２０＿１についても同様な議論が成り立つ。
【００９０】
このように、２レベルのＣＩＡ２は、第１段階の回路を複数有しており、この第１段階の回路から第２段階の回路へ局所的なキャリー伝播信号，キャリー生成信号が供給される構造を持つ。そのため、複数の第１段階の回路においては、局所的なキャリー伝播信号，キャリー生成信号の生成がそれぞれ並列に実行される。すなわち、キャリー生成信号ｇ１８＿１７，ｇ２０＿１９，ｇ２４＿２１，ｇ３０＿２５の生成動作がそれぞれ並列に実行されるとともに、キャリー伝播信号ｐ１８＿１７，ｐ２０＿１９，ｐ２４＿２１，ｐ３０＿２５の生成動作がそれぞれ並列に実行される。
したがって、全ての局所的なキャリー伝播信号，キャリー生成信号が下位桁から順番に生成される１レベルのＣＩＡに比べて、上位側のキャリー信号の生成が高速化される。言い換えると、各桁の加算値の算出タイミングは上位桁に向かうにつれて遅延するものの、その遅延の傾向は１レベルのＣＩＡに比べて緩やかである。
【００９１】
つまり、中位のビット範囲においては、下位のビット範囲と比較して、上位側における加算値算出タイミングの遅延が小さくなる。
【００９２】
また、上位のビット範囲（第３１桁〜第３９桁）では、図９に示すＣＳＡ３によって加算が行われる。
ＣＳＡ３では、キャリー信号ｃ３０が‘０’の場合と‘１’の場合における第３１桁〜第３９桁のキャリー信号および和信号の予測値が予め算出される。そして、キャリー信号ｃ３０がＣＳＡ３へ到着すると、この予め算出された和信号の一方がセレクタにより選択され、加算結果として出力される。そのため、キャリー信号ｃ３０の到着より早く予測値が算出されるものとすると、キャリー信号ｃ３０が到着してから各桁のキャリー信号，和信号が生成されるまでの遅延ははほぼ等しくなる。
【００９３】
つまり、上位のビット範囲においては、下位，中位のビット範囲と比較して、上位側における加算値算出タイミングの遅延がより一層小さくなる。
【００９４】
以上説明したように、本実施形態に係る第２の加算回路１０２よれば、ビット信号の入力タイミングが上位桁ほど遅くなる下位のビット範囲においては、下位側に対する上位側の加算値算出タイミングを多少遅らせても実質的な加算値の出力タイミングが変わらないため、上位側へのキャリーの伝播が比較的低速な１レベルのＣＩＡを使って加算が行われる。ビット信号の入力タイミングがほぼ一定になるか、上位側で若干早くなる中位のビット範囲においては、下位のビット範囲と比較して上位側の加算値算出タイミングを早める必要があるため、１レベルのＣＩＡよりもキャリーの伝播が高速な２レベルのＣＩＡを使って加算が行われる。また、ビット信号の入力タイミングが上位桁に向かうほど早くなる上位のビット範囲においては、下位，中位のビット範囲よりも上位側の加算値算出タイミングを早める必要があるため、１レベル，２レベルのＣＩＡよりも上位側の加算値を更に高速に生成できるＣＳＡを用いて加算が行われる。
このように、各ビット範囲におけるビット信号の入力タイミングの遅延傾向に合わせて、それぞれ異なる加算方式により加算が行われるため、回路規模と消費電力を低減しつつ高速に加算を行うことができる。例えば、上位のビット範囲へのキャリー信号ｃ３０を高速化するために桁上げ先見回路を設ける回路方式に比べて、回路規模を大幅に減少させることができるとともに、下位のビット範囲に１レベルＣＩＡ、中位のビット範囲に２レベルＣＩＡを用いることで、桁上げ先見回路を設けた場合と比較しても遜色のないスピードを実現することが可能になる。
【００９５】
＜第２の実施形態＞
次に、第２の実施形態について述べる。
上述した第１の実施形態では下位，中位のビット範囲の加算に１レベル，２レベルのＣＩＡを用いる例が示されているが、第２の実施形態では、これらに他のレベルのＣＩＡを用いる例が示される。
【００９６】
図１１は、本発明の第２の実施形態に係る第２の加算回路１０２Ａの構成の一例を示すブロック図である。
第２の加算回路１０２Ａは、図１に示す乗算回路における第２の加算回路１０２と置き換えられる４０ビットの加算回路であり、例えば図１１に示すように、下位ビット範囲（第０桁〜第１５桁）の加算を行うＣＩＡ４と、中位ビット範囲（第１６桁〜第３０桁）の加算を行うＣＩＡ５と、上位ビット範囲（第３１桁〜第３９桁）の加算を行うＣＳＡ３とを有する。
ＣＳＡ３は、図９を参照して既に述べたものと同様であるので、ここではＣＩＡ４およびＣＩＡ５について説明する。
【００９７】
まず、第ｋのキャリー伝播信号生成回路および第ｋのキャリー生成信号生成回路（ここで、ｋは２以上の整数を示す）を次のように定義する。
第ｋのキャリー伝播信号生成回路は、第（ｋ−１）のキャリー伝播信号生成回路の縦続接続回路の終段から出力されるキャリー伝播信号ｐＭ２＿Ｍ１（ここで、Ｍ２，Ｍ１は、Ｍ２＞Ｍ１を満たす正の整数を示す）と、前段からのキャリー伝播信号ｐ（Ｍ１−１）＿Ｍ０（ここで、Ｍ０は、Ｍ１＞Ｍ０を満たす正の整数を示す）とに基づいてキャリー伝播信号ｐ（Ｍ２，Ｍ０）を生成する、縦続に接続された複数の回路を含む回路である。
第ｋのキャリー生成信号生成回路は、第（ｋ−１）のキャリー生成信号生成回路の縦続接続回路の終段から出力されるキャリー生成信号ｇＭ２＿Ｍ１と、前段からのキャリー生成信号ｇ（Ｍ１−１）＿Ｍ０と、第（ｋ−１）のキャリー伝播信号生成回路の縦続接続回路の終段から出力されるキャリー伝播信号ｐＭ２＿Ｍ１とに基づいてキャリー生成信号ｇＭ２＿Ｍ０を生成する、縦続に接続された複数の回路を含む回路である。
したがって、第ｋ段階の回路（第ｋのキャリー伝播信号生成回路、第ｋのキャリー生成信号生成回路）は、その下位段階（第（ｋ−１）段階）の回路の終段から出力される信号を用いて、局所的なキャリー伝播信号，キャリー生成信号を生成する。
【００９８】
ｍレベル（ｍは、１以上の整数を示す）のＣＩＡは、上述した定義を用いて、次のように定義する。
ｋが最大でｍ（ｍは、１以上の整数を示す）までの第ｋのキャリー伝播信号生成回路および第ｋのキャリー生成信号生成回路を含む回路を、ｍレベルのＣＩＡとする。
【００９９】
このような定義を使って述べると、下位，中位ビット範囲のＣＩＡ４，ＣＩＡ５は、互いにレベルが異なるＣＩＡであるとともに、ＣＩＡ５はＣＩＡ４より高レベルのＣＩＡである。
【０１００】
上述した定義によると、ＣＩＡは、レベルが高くなるほど並列して生成される局所的なキャリー生成信号，キャリー伝播信号の数が増えるため、下位から上位へのキャリー伝播が高速になる。そのため、本実施形態においても、第１の実施形態と同様に、下位のビット範囲に比較して中位のビット範囲のキャリー伝播が高速になり、上位側の加算値算出タイミングの遅延が小さくなる。したがって、第１の実施形態と同様に、ビット信号の入力タイミングの遅延傾向に合った加算方式で各ビット範囲の加算を行うことができる。
【０１０１】
なお、下位，中位ビット範囲におけるビット信号の入力タイミングの遅延傾向が上述と逆の傾向を有する場合は、上述とは逆に、ＣＩＡ４をＣＩＡ５より高レベルのＣＩＡにしても良い。
【０１０２】
＜第３の実施形態＞
次に、第３の実施形態について述べる。
図１２は、本発明の第３の実施形態に係る第２の加算回路１０２Ｂの構成の一例を示すブロック図である。
第２の加算回路１０２Ｂも、図１に示す乗算回路における第２の加算回路１０２と置き換えられる４０ビットの加算回路であり、例えば図１２に示すように、下位ビット範囲（第０桁〜第１５桁）の加算を行うリプル・キャリー・アダー６と、中位ビット範囲（第１６桁〜第３０桁）の加算を行うＣＩＡ７と、上位ビット範囲（第３１桁〜第３９桁）の加算を行うＣＳＡ３とを有する。以降、リプル・キャリー・アダーをＲＣＡと略記する。
ＲＣＡ６は、本発明の第４の加算ユニットの一実施形態である。
【０１０３】
ＲＣＡ６は、第０桁から第１５桁に向かって順番にキャリー信号を算出し、当該算出したキャリー信号を用いて和信号を算出する。例えば図１３Ａに示すように、第０桁，…，第１５桁にそれぞれ対応する全加算器６０＿０，…，６０＿１５を有する。
【０１０４】
全加算器６０＿０は、第０桁のビット信号（ａ０，ｂ０）およびキャリー信号ＣＩＮを入力し、これに基づいて第０桁の和信号ｓ０およびキャリー信号ｃ０を算出する。
全加算器６０＿ｊ（ここで、ｊは１から１５までの整数を示す）は、第ｊ桁のビット信号（ａｊ，ｂｊ）を入力するとともに、前段の全加算器６０＿（ｊ−１）で算出されたキャリー信号ｃ（ｊ−１）を入力し、これに基づいて第ｊ桁の和信号ｓｊおよびキャリー信号ｃｊを算出する。
全加算器６０＿０，…，６０＿１の内部構成（図１３Ｂ）は、図１０に示す回路と同様である。
【０１０５】
ＣＩＡ７は、任意のレベルのＣＩＡであり、下位桁から順番にキャリー信号を生成するＲＣＡに比べてキャリーの伝播速度が速い。
【０１０６】
本実施形態においても、第１の実施形態と同様に、下位のビット範囲に比較して中位のビット範囲のキャリー伝播が高速になり、上位側の加算値算出タイミングの遅延が小さくなる。したがって、第１の実施形態と同様に、ビット信号の入力タイミングの遅延傾向に合った加算方式で各ビット範囲の加算を行うことができる。本実施形態は、特に、下位のビット範囲における下位側と上位側との間の加算値算出タイミングの遅延差が大きい場合に有効である。
【０１０７】
＜第４の実施形態＞
次に、第４の実施形態について述べる。
図１４は、本発明の第４の実施形態に係る第２の加算回路１０２Ｃの構成の一例を示すブロック図である。
第２の加算回路１０２Ｃも、図１に示す乗算回路における第２の加算回路１０２と置き換えられる４０ビットの加算回路であり、例えば図１４に示すように、下位ビット範囲（第０桁〜第１５桁）の加算を行うＣＩＡ８と、中位ビット範囲（第１６桁〜第３０桁）の加算を行うＲＣＡ９と、上位ビット範囲（第３１桁〜第３９桁）の加算を行うＣＳＡ３とを有する。
【０１０８】
本実施形態においては、ＣＩＡ８によって加算を行う下位のビット範囲と比較して、ＲＣＡ９によって加算を行う中位のビット範囲のキャリー伝播が低速になり、上位側の加算値算出タイミングの遅延が大きくなる。
したがって、本実施形態は、下位のビット範囲より中位のビット範囲の方が、上位側の入力タイミングの遅延傾向が強い場合に適している。例えば、下位のビット範囲においてビット信号の入力タイミングが一定しているか、上位桁に向かうほど入力タイミングが早くなる傾向があり、中位のビット範囲において上位桁に向かうほどビット信号の遅延が急増する傾向がある場合に適している。
【０１０９】
＜第５の実施形態＞
次に、第５の実施形態について述べる。
図１５は、本発明の第５の実施形態に係る第２の加算回路１０２Ｄの構成の一例を示すブロック図である。
第２の加算回路１０２Ｄも、図１に示す乗算回路における第２の加算回路１０２と置き換えられる４０ビットの加算回路であり、例えば図１５に示すように、下位ビット範囲（第０桁〜第１５桁）の加算を行う加算ユニット１０と、上位ビット範囲（第１６桁〜第３９桁）の加算を行う加算ユニット１１とを有する。
【０１１０】
加算ユニット１０および１１は、任意レベルのＣＩＡまたはＲＣＡの何れかの構成を有する。ただし、両者は異なる加算方式を有する。
【０１１１】
本実施形態においては、第１〜第４の実施形態において設けられていた上位ビット範囲のＣＳＡが省略されており、その代わりに、ＣＩＡまたはＲＣＡの加算ユニットが設けられている。そのため、上位のビット範囲における加算値の算出タイミングは第１〜第４の実施形態と比べて遅延する。したがって、本実施形態は、上位のビット範囲において、上位側の入力タイミングが早くなる傾向が比較的緩やかであり、ＣＳＡほど高速に加算値を算出する必要がない場合に適している。
【０１１２】
なお、本発明は上述した実施形態に限定されず、種々の改変が可能である。
【０１１３】
通常、乗算回路の最終段において加算される２つの信号の最下位桁に入力されるキャリー信号ＣＩＮは‘０’であるため、このことを利用して、下位ビット範囲における回路を簡略化することが可能である。例えば図４に示すＣＩＡ１では、ＡＮＤ−ＯＲ複合回路１１＿１〜１１＿１５を省略し、キャリー生成信号ｇ１＿０〜ｇ１５＿０をそれぞれキャリー信号ｃ１〜ｃ１５として出力しても良い。
【０１１４】
また、乗算回路の最終段において加算される最下位桁のビット信号ａ０，ｂ０のうちの一方は通常存在しない、すなわち‘０’であるため、このことを利用して、最下位桁についても回路の簡略化が可能である。
例えばｂ０が‘０’の場合、最下位桁の和信号ｓ０としてビット信号ａ０をそのまま出力しても良い。また、この場合、最下位桁のキャリー信号ｃ０が‘０’になることから、第１桁の和信号ｓ１としてキャリー伝播信号ｐ１、すなわち第１桁のビット信号ａ１およびｂ１の排他的論理和をそのまま出力しても良い。このような簡略化により、例えば図４に示すＣＩＡ１では、ＡＮＤ−ＯＲ複合回路１１＿０、排他的ＯＲ回路１３＿０および１３＿１、ＡＮＤ回路１４＿０、ならびに排他的ＯＲ回路１５＿０を省略することが可能である。
【０１１５】
また、乗算回路の最終段における最上位桁の加算では、符号拡張処理のために、通常、２つのビット信号の一方を論理反転して元の信号に加算し、これを和信号として出力する。したがって、このことを利用すれば、最上位桁についても回路の簡略化が可能である。
例えば図９に示すＣＳＡ３における最上位桁の全加算器３０＿８および３１＿８では、キャリー伝播信号ｐが‘１’になる。このため、これらの全加算器では、図１０に示す排他的ＯＲ回路３３をＮＯＴ回路に置換し、下位桁からのキャリー信号ｃｉｎの論理反転信号を和信号ｓとして出力する構成としても良い。
【０１１６】
上述した実施形態における各信号の桁数や、ビット範囲のとり方は一例であり、これに限定されず任意に設定可能である。また、上述した実施形態において挙げた回路構成も説明上の一例であり、同等な機能を有する別の構成へ任意に改変可能である。
図３、図４においては、キャリー・インクリメント・アダー１として、１つの１レベルＣＩＡを例示したが、これを複数個の１レベルＣＩＡで構成することもできる。例えば、１ビット入力の１レベルＣＩＡ、１ビット入力の１レベルＣＩＡ、２ビット入力の１レベルＣＩＡ、４ビット入力の１レベルＣＩＡ、８ビット入力の１レベルＣＩＡを縦続接続してキャリー・インクリメント・アダー１を構成し、１６ビットの演算を行なえばよい。このように、１レベルＣＩＡについては、複数個の１レベルＣＩＡで実現してもよい。
【図面の簡単な説明】
【０１１７】
【図１】本発明の第１の実施形態に係る乗算回路の構成の一例を示すブロック図である。
【図２】４０ビットの信号出力を有するワレスの木の出力遅延の一例を図解した図である。
【図３】本発明の第１の実施形態に係る第２の加算回路の構成の一例を示すブロック図である。
【図４】図３に示す第２の加算回路における、１レベルのキャリー・インクリメント・アダーの構成の一例を示すブロック図である。
【図５】図３に示す第２の加算回路における、２レベルのキャリー・インクリメント・アダーの構成の一例を示す第１のブロック図である。
【図６】図３に示す第２の加算回路における、２レベルのキャリー・インクリメント・アダーの構成の一例を示す第２のブロック図である。
【図７】図６に示すキャリー・インクリメント・アダーにおいて、局所的なキャリー伝播信号およびキャリー生成信号の生成に関わる部分の接続関係を示すブロック図である。
【図８】図６に示すキャリー・インクリメント・アダーにおいて、キャリー信号の生成に関わる部分の接続関係を示すブロック図である。
【図９】図３に示す第２の加算回路における、キャリー・セレクト・アダーの構成の一例を示すブロック図である。
【図１０】全加算器の構成の一例を示すブロック図である。
【図１１】本発明の第２の実施形態に係る第２の加算回路の構成の一例を示すブロック図である。
【図１２】本発明の第３の実施形態に係る第２の加算回路の構成の一例を示すブロック図である。
【図１３】図１２に示す第２の加算回路におけるリプル・キャリー・アダーの構成の一例を示すブロック図である。
【図１４】本発明の第４の実施形態に係る第２の加算回路１０２の構成の一例を示すブロック図である。
【図１５】本発明の第５の実施形態に係る第２の加算回路１０２の構成の一例を示すブロック図である。
【図１６】一般的な乗算の過程を説明するための図である。
【図１７】４桁のキャリー・ルックアヘッド・アダーの構成例を示すブロック図である。
【図１８】全ビットの和出力をキャリー・セレクト・アダーによって算出するとともに、上位桁のキャリー信号を桁上げ先見回路によって生成する加算回路である。
【図１９】従来の加算回路の性能を速度、消費電力、回路面積の点で比較した図である。
【符号の説明】
【０１１８】
１，２，４，５，７，８…キャリー・インクリメント・アダー（ＣＩＡ）、３…キャリー・セレクト・アダー（ＣＳＡ）、６，９…リプル・キャリー・アダー（ＲＣＡ）、１０，１１…加算ユニット、１０＿１〜１０＿１５，１４＿０〜１４＿１５，２２＿０〜２２＿３，２３＿０〜２３＿９，２６＿０〜２６＿１４，３５…ＡＮＤ回路、１１＿０〜１１＿１５，１２＿１〜１２＿１５，２０＿０〜２０＿３，２１＿０〜２１＿９，２４＿０〜２４＿１４，３４…ＡＮＤ−ＯＲ複合回路、１３＿０〜１３＿１５，１５＿０〜１５＿１５，２５＿０〜２５＿１４，２７＿０〜２７＿１４，３３，３６…排他的ＯＲ回路、３０＿０〜３０＿８，３１＿０〜３１＿８，６０＿０〜６０＿１５…全加算器、３２＿０〜３２＿８…セレクタ、１００…部分積生成回路、１０１…第１の加算回路、１０２…第２の加算回路
【図１】
2005182346.tif 000004
【図２】
2005182346.tif 000005
【図３】
2005182346.tif 000006
【図４】
2005182346.tif 000007
【図５】
2005182346.tif 000008
【図６】
2005182346.tif 000009
【図７】
2005182346.tif 000010
【図８】
2005182346.tif 000011
【図９】
2005182346.tif 000012
【図１０】
2005182346.tif 000013
【図１１】
2005182346.tif 000014
【図１２】
2005182346.tif 000015
【図１３】
2005182346.tif 000016
【図１４】
2005182346.tif 000017
【図１５】
2005182346.tif 000018
【図１６】
2005182346.tif 000019
【図１７】
2005182346.tif 000020
【図１８】
2005182346.tif 000021
【図１９】
2005182346.tif 000022