(57)【要約】【課題】条件選択加算器を提供する。【解決手段】条件選択加算器は、第１信号生成部、第２信号生成部、及び合算回路を含む。第１信号生成部は、合算される被演算子対に応答して、キャリー生成信号及びキャリー伝達信号を生成する。第２信号生成部は、キャリー生成信号及びキャリー伝達信号に応答してブロックキャリー信号と入力キャリー信号を生成する。第２信号生成部は、少なくとも１つ以上のリーフセルを具備する少なくとも１つ以上のグループを含む。グループは、各グループに含まれるリーフセルの数が少ない第１グループから各グループに含まれるリーフセルの数が多い第２グループに、リーフセルの個数によって昇冪の順にグループ化され配置される。合算回路は、ブロックキャリー信号、キャリー伝達信号、及び入力キャリー信号に応答して被演算子の和を生成する。合算回路は、グループバイパス回路と合算部を含むことができる。【選択図】    図２
2008033937.tif 000002
【特許請求の範囲】
【請求項１】
合算される被演算子対に応答してキャリー生成信号及びキャリー伝達信号を生成する第１信号生成部と、
前記キャリー生成信号及び前記キャリー伝達信号に応答してブロックキャリー信号及び入力キャリー信号を生成し、少なくとも１つ以上のリーフセルを具備する少なくとも１つ以上のグループを含む第２信号生成部と、
前記ブロックキャリー信号、前記キャリー伝達信号、及び前記入力キャリー信号に応答して、前記被演算子の和を生成する合算回路を含み、
前記グループは、前記各グループに含まれる前記リーフセルの数が少ない第１グループから前記各グループに含まれるリーフセルの数が多い第２グループに、前記リーフセルの個数によって昇冪の順にグループ化され配置されることを特徴とする条件選択加算器。
【請求項２】
前記合算回路は、前記キャリー伝達信号及び前記ブロックキャリー信号の提供を受けて出力キャリー信号を生成するグループバイパス回路を含むことを特徴とする請求項１記載の条件選択加算器。
【請求項３】
前記合算回路は、前記入力キャリー信号及び前記キャリー伝達信号に応答して合算出力信号を生成する合算部を更に含み、前記合算出力信号及び前記出力キャリー信号は、前記被演算子の和を示すことを特徴とする請求項１記載の条件選択加算器。
【請求項４】
前記複数のグループのリーフセルのそれぞれは、前記キャリー生成信号及び前記キャリー伝達信号の該当ビットに対応することを特徴とする請求項１記載の条件選択加算器。
【請求項５】
前記それぞれのグループを代表するリーフセルは、対応するブロックキャリー信号の該当ビットを生成することを特徴とする請求項４記載の条件選択加算器。
【請求項６】
前記複数のグループのリーフセルのそれぞれは、前記キャリー生成信号及び前記キャリー伝達信号の該当ビットに対応することを特徴とする請求項２記載の条件選択加算器。
【請求項７】
前記それぞれのグループを代表するリーフセルは、対応するブロックキャリー信号の該当ビットを生成することを特徴とする請求項６記載の条件選択加算器。
【請求項８】
前記グループバイパス回路は、前記ブロックキャリー信号に対応する該当ビットを受信するリーフセルを含むことを特徴とする請求項７記載の条件選択加算器。
【請求項９】
前記第２グループは、最終グループであることを特徴とする請求項１記載の条件選択加算器。
【請求項１０】
前記第２グループは中間グループで、前記グループの最終グループは、前記中間グループと比べて少ない数のリーフセルを有することを特徴とする請求項１記載の条件選択加算器。
【請求項１１】
Ｎ（Ｎは自然数）ビットの２つの入力に応答してキャリー生成信号及びキャリー伝達信号を生成するキャリー信号生成部と、
前記キャリー生成信号及び前記キャリー伝達信号に応答してブロックキャリーと入力キャリーを生成し、少なくとも１つ以上のリーフセルを具備する少なくとも１つ以上のグループを含むキャリー生成部と、
前記キャリー伝達信号及び前記ブロックキャリーの提供を受けて出力キャリーを生成するグループバイパス部と、
前記キャリー伝達信号及び前記入力キャリーに応答して前記Ｎビットの２つの入力の和を生成する合算部と、を含み、
前記グループは、前記各グループに含まれる前記リーフセルの数が少ない下位グループから前記各グループに含まれるリーフセルの数が多い上位グループに、前記リーフセルの個数によって昇冪の順にグループ化れ配置されることを特徴とする条件選択加算器。
【請求項１２】
前記キャリー生成部の一番目グループのリーフセルの個数は２であることを特徴とする請求項１１記載の条件選択加算器。
【請求項１３】
前記キャリー生成部の最終グループのリーフセルの個数は、各グループに含まれるリーフセルの個数の合計をＫ（Ｋは自然数）とし、前記ＫがＮ以上である時、前記Ｋに最後に加算された数であることを特徴とする請求項１２記載の条件選択加算器。
【請求項１４】
前記Ｎから前記Ｋを引いた数をＭ（Ｍは自然数）とし、前記Ｍ個のリーフセルを有するグループを残りグループとすると、前記Ｍが１である時、前記残りグループは前記リーフセルの数が２であるグループの前に配置されることを特徴とする請求項１３記載の条件選択加算器。
【請求項１５】
前記Ｍが１より大きい数であると、前記残りグループは同じ数のリーフセルを有するグループの前に配置されることを特徴とする請求項１４記載の条件選択加算器。
【請求項１６】
前記グループバイパス部は、前記キャリー生成部の各グループの個数に該当する個数のリーフセルを含むことを特徴とする請求項１５記載の条件選択加算器。
【請求項１７】
前記キャリー生成部の各グループに含まれた最後のリーフセルで前記グループバイパス部の該当リーフセルに前記ブロックキャリーを提供することを特徴とする請求項１６記載の条件選択加算器。
【請求項１８】
前記キャリー生成信号は、前記２つの入力の論理積であることを特徴とする請求項１１記載の条件選択加算器。
【請求項１９】
前記キャリー伝達信号は、前記２つの入力の排他的論理和であることを特徴とする請求項１１記載の条件選択加算器。
【請求項２０】
前記合算部の出力信号は、前記キャリー伝達信号と前記入力キャリー信号との排他的論理和であることを特徴とする請求項１９記載の条件選択加算器。
【請求項２１】
Ｎ（Ｎは自然数）ビットの２つの入力に応答してキャリー生成信号及びキャリー伝達信号を生成する段階と、
前記キャリー生成信号及び前記キャリー伝達信号に応答してブロックキャリー及び入力キャリーを生成する段階と、
前記キャリー伝達信号及び前記ブロックキャリーに応答して出力キャリーを生成する段階と、
前記キャリー伝達信号及び前記入力キャリーに応答して前記Ｎビットの２つの入力を合算する段階と、を含み、
前記ブロックキャリーと前記入力キャリーを生成する段階は、前記Ｎビットに対応するＮ個のリーフセルのうち、少なくとも１つ以上のリーフセルを含み、
前記グループは、前記各グループに含まれるリーフセルの数が少ない下位グループから含まれるリーフセルの数が多い上位グループに、前記リーフセルの個数によって昇冪の順にグループ化され配置されることを特徴とする条件選択加算方法。
【請求項２２】
前記グループのうち、一番目のグループのリーフセルの数は２であることを特徴とする請求項２１記載の条件選択加算方法。
【請求項２３】
前記グループのうち、最終グループのリーフセルの数は、各グループに含まれるリーフセルの個数の合計をＫ（Ｋは自然数）とし、前記ＫがＮ以上である時、前記Ｋに最後に加算された数であることを特徴とする請求項２２記載の条件選択加算方法。
【請求項２４】
前記Ｎから前記Ｋを引いた数をＭ（Ｍは自然数）とし、前記Ｍ個のリーフセルを有するグループを残りグループとすると、前記Ｍが１である時、前記残りグループは、前記リーフセルの数が２であるグループの前に配置されることを特徴とする請求項２３記載の条件選択加算方法。
【請求項２５】
前記Ｍが１より大きい数であると、前記残りグループは同じ数のリーフセルを有するグループの前に配置されることを特徴とする請求項２４記載の条件選択加算方法。
【請求項２６】
前記出力キャリーを生成する段階は、前記グループの個数に該当するリーフセルを含むことを特徴とする請求項２５記載の条件選択加算方法。
【請求項２７】
前記各グループに含まれた最後のリーフセルから前記出力キャリーを生成する段階の該当リーフセルに前記ブロックキャリーが提供されることを特徴とする請求項２６記載の条件選択加算方法。
【請求項２８】
前記キャリー生成信号は、前記２つの入力の排他的論理和であることを特徴とする請求項２１記載の条件選択加算方法。
【請求項２９】
前記キャリー生成信号は、前記２つの入力の論理積であることを特徴とする請求項２１記載の条件選択加算方法。
【請求項３０】
前記２つ入力の合算結果は、前記キャリー伝達信号と前記入力キャリーとの排他的論理和であることを特徴とする請求項２９記載の条件選択加算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は集積回路装置に係り、より詳細には集積回路装置に使用される二進加算器に関する。
【背景技術】
【０００２】
一般的に、半導体集積回路（ＩＣ）は、規格化された標準ＩＣと使用者の注文によって製作されるＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）とに区分することができる。ＡＳＩＣは、特定の用途のために使用される。ＡＳＩＣは、設計方式によって、主に使用者の注文により設計及び製作等の全過程が行われる完全注文型ＩＣと、既に製作されたセルを利用し配線過程を通じて論理回路を構成するスタンダードセル及びゲートアレイとに区分される。
【０００３】
また、ＡＳＩＣライブラリのうち、コンパイルされたマクロセルライブラリは、予め準備されたリーフセルを配置して配線することにより、注文者の要求に応じたビット幅等の多様なパラメータを有する集積回路として構成される。このような特性上、コンパイルされたマクロセルが速度、電源、面積、及び柔軟性（例えば、加算器の一部リーフセルを変更することによりＡＬＵ（ａｒｉｔｈｍｅｔｉｃ  ａｎｄ  ｌｏｇｉｃ  ｕｎｉｔ）等の回路に変更することができる柔軟性）において優れた性能を有するようにするためには、何よりもリーフセルの定義をよく行うべきである。リーフセルの定義は、原則的に、リーフセルがどんなアルゴリズムによって回路で実現されるかによって左右される。
【０００４】
一般的に、加算器は、リップルキャリーアルゴリズム、キャリールックアヘッドアルゴリズム等によって具現される。図示していないが、リップルキャリーアルゴリズムによる加算器は、並列で入力される複数ビットの入力信号を最下位ビット（ＬＳＢ；ｌｅａｓｔ  ｓｉｇｎｉｆｉｃａｎｔ  ｂｉｔ）から最上位ビット（ＭＳＢ；ｍｏｓｔ  ｓｉｇｎｉｆｉｃａｎｔ  ｂｉｔ）までの和と桁上げを示すキャリービットを順次に加算して最終的に加算の結果を出力する方式である。このアルゴリズムによる加算器では、例えば、１６ビットの加算結果ビットのために加算動作を行う時、出力されるビット数だけの時間遅延、即ち、１６ビットの単位時間遅延が発生される。
【０００５】
キャリールックアヘッドアルゴリズムは、加算器を構成しているリーフセルを所定の単位にブロッキングし、キャリービットを同時に計算して、最終結果を出力する方式である。このようなキャリールックアヘッドアルゴリズム方式による加算器は、リップルキャリーアルゴリズム方式による加算器で発生する時間遅延を減少させることができるが、加算器のビット数が増加されるほど、加算器が全体回路で占める面積が大幅増加される。
【０００６】
従って、ビット数の増加によって面積を増加させず、加算器から発生されるデータスキューによる時間遅延を減少させることができる加算器が必要となる。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
前記問題点を解決するための本発明の第１目的は、データスキューを減少させることができる条件選択加算器を提供することにある。
【０００８】
本発明の第２目的は、データスキューを減少させることができる条件選択加算方法を提供することにある。
【課題を解決するための手段】
【０００９】
前記目的を達成するための本発明の一実施例による条件選択加算器は、第１信号生成部、第２信号生成部、及び合算回路を含む。前記第１信号生成部は、合算される被演算子対に応答してキャリー生成信号及びキャリー伝達信号を生成する。前記第２信号生成部は、前記キャリー生成信号及び前記キャリー伝達信号に応答してブロックキャリー信号及び入力キャリー信号を生成し、少なくとも１つ以上のリーフセルを具備する少なくとも１つ以上のグループを含む。前記合算回路は、前記ブロックキャリー信号、前記キャリー伝達信号、及び前記入力キャリー信号に応答して、前記被演算子の和を生成する。前記グループは、前記各グループに含まれる前記リーフセルの数が少ない第１グループから前記各グループに含まれるリーフセルの数が多い第２グループに、リーフセルの個数によって昇冪の順にグループ化され配置される。
【００１０】
実施例において、前記合算回路は、前記キャリー伝達信号及び前記ブロックキャリー信号の提供を受けて出力キャリー信号を生成するグループバイパス回路を含むことができる。
【００１１】
実施例において、前記合算回路は、前記入力キャリー信号及び前記キャリー伝達信号に応答して合算出力信号を生成する合算部を更に含むことができる。前記合算出力信号及び前記出力キャリー信号は、前記被演算子の和を示す。
【００１２】
実施例において、前記複数のグループのリーフセルのそれぞれは、前記キャリー生成信号及び前記キャリー伝達信号の該当ビットに対応することができる。前記それぞれのグループを代表するリーフセルは、対応するブロックキャリー信号の該当ビットを生成することができる。
【００１３】
実施例において、前記グループバイパス回路は、前記ブロックキャリー信号に対応する該当ビットを受信するリーフセルを含むことができる。
【００１４】
実施例において、前記第２グループは最終グループであり得る。
【００１５】
実施例において、前記第２グループは中間グループであってもよく、前記グループの最終グループは、前記中間グループと比べて少ない数のリーフセルを有することができる。
【００１６】
前記他の目的を達成するための本発明の一実施例による条件選択加算器は、キャリー信号生成部、キャリー生成部、グループバイパス部、及び合算部を含む。前記キャリー信号生成部は、Ｎ（Ｎは自然数）ビットの２つの入力に応答してキャリー生成信号及びキャリー伝達信号を生成する。前記キャリー生成部は、前記キャリー生成信号及び前記キャリー伝達信号に応答してブロックキャリー及び入力キャリーを生成し、少なくとも１つ以上のリーフセルを具備する少なくとも１つ以上のグループを含む。前記グループバイパス部は、前記キャリー伝達信号及び前記ブロックキャリーの提供を受けて出力キャリーを生成する。前記合算部は、前記キャリー伝達信号及び前記入力キャリーに応答して、前記Ｎビットの２つの入力の和を生成する。前記グループは、前記各グループに含まれる前記リーフセルの数が少ない下位グループから前記各グループに含まれるリーフセルの数が多い上位グループに、リーフセルの個数によって昇冪に順にグループ化され配置される。
【００１７】
実施例において、前記キャリー生成部の一番目グループのリーフセルの個数は、２であり得る。前記キャリー生成部の最終グループのリーフセルの個数は、各グループに含まれるリーフセルの個数の合計をＫ（Ｋは自然数）とし、前記ＫがＮ以上である時、前記Ｋに最後に加算された数であり得る。前記Ｎから前記Ｋを引いた数をＭ（Ｍは、自然数）とし、前記Ｍ個のリーフセルを有するグループを残りグループとすると、前記Ｍが１である時、前記残りグループは前記リーフセルの数が２であるグループの前に配置されることができる。前記Ｍが１より大きい数であれば、前記残りグループは、同じ数のリーフセルを有するグループの前に配置されることができる。前記グループバイパス部は、前記キャリー生成部の各グループの個数に該当する個数のリーフセルを含むことができる。前記キャリー生成部の各グループに含まれた最後のリーフセルで前記グループバイパス部の該当リーフセルに前記ブロックキャリーを提供することができる。
【００１８】
実施例において、前記キャリー生成信号は、前記２つの入力の排他的論理和であり得る。前記キャリー生成信号は、前記２つの入力の論理積であり得る。前記合算部の出力信号は、前記キャリー伝達信号と前記入力キャリー信号との排他的論理和であり得る。
【００１９】
前記更に他の目的を達成するための本発明の一実施例による条件選択加算方法は、Ｎ（Ｎは自然数）ビットの２つの入力に応答してキャリー生成信号及びキャリー伝達信号を生成する段階、前記キャリー生成信号及び前記キャリー伝達信号に応答してブロックキャリー及び入力キャリーを生成する段階、前記キャリー伝達信号及び前記ブロックキャリーに応答して出力キャリーを生成する段階、前記キャリー伝達信号及び前記入力キャリーに応答して前記Ｎビットの２つの入力を合算する段階を含み、前記ブロックキャリー及び前記入力キャリーを生成する段階は、前記Ｎビットに対応するＮ個のリーフセルのうち、少なくとも１つ以上のリーフセルを含む。前記グループは、前記各グループに含まれるリーフセルの数が少ない下位グループから含まれるリーフセルの数が多い上位グループに、リーフセルの個数によって昇冪の順にグループ化され配置される。
【００２０】
本文に開示している本発明の実施例において、特定の構造的乃至機能的説明は、本発明の実施例を説明することのみを目的として例示されたものであって、本発明の実施例は、多様な形態で実施することができ、本文に説明した実施例に限定されることはない。
【００２１】
本発明は、多様な変更を加えたり、多様な形態を有したりすることができるものであり、特定の実施例のみを図面に例示し、本文で詳細に説明する。しかし、これは、本発明を特定の形態に限定するものではなく、本発明の思想及び技術範囲に含まれる全ての変更、均等物乃至代替物を含むことと理解すべきである。
【００２２】
本出願で用いた用語は、特定の実施例を説明するためにのみ盛り込まれるものであって、本発明を限定しようとする意図はない。単数の表現は、文脈上明確に異なるように意味しない限り、複数の表現を含む。本出願において、「含む」または「有する」などの用語は、説示した特徴、数字、段階、動作、構成要素、部分品またはこれらを組み合わせたものの存在または付加可能性を予め排除しないことと理解すべきである。
【００２３】
異なるものとして定義しない限り、技術的であるか科学的な用語を含めてここで用いられる全ての用語は、本発明が属する技術分野において通常の知識を有する者によって一般的に理解されるものと同一の意味を有している。一般的に用いられる辞典に定義されているもののような用語は、関連技術の文脈上で有する意味と一致する意味を有することと解釈すべきであり、本出願で明白に定義されない限り、異常的または過度に形式的な意味で解釈されない。
【００２４】
一方、ある実施例が異なるように実現可能な場合に、特定ブロック内に明記された機能又は動作は順序図に明記された順序と異なってもよい。例えば、連続する２つのブロックが実際には同時に行われることもでき、関連された機能又は動作によっては前記ブロックが逆に行われることもできる。
【発明の効果】
【００２５】
本発明による条件選択加算機及び条件選択加算方法は、リーフセルを昇冪の順に配置して、残りビットに該当するリーフセルを含むグループを再配置して、データスキューを最小化することができる。従って、面積を増加させることなく、ハイパフォーマンスを具現することができ、演算速度を向上させることができる。
【発明を実施するための最良の形態】
【００２６】
以下、添付図面を参照して、本発明の好ましい実施例をより詳細に説明する。図面上の同じ構成要素には同じ参照符号を使用し、同じ構成要素についての重複説明は省略する。
【００２７】
図１は、本発明の一実施例による条件選択加算器の概略的なブロック図である。
【００２８】
図１を参照すると、本発明の一実施例による条件選択加算器は、キャリー信号生成部１０、キャリー生成部２０、グループバイパス部３０、及び合算部４０を含む。
【００２９】
キャリー信号生成部１０は、Ｎビットの２つの入力に応答して、キャリー生成信号ＧＧ及びキャリー伝達信号ＰＰを生成する。ここで、Ｎは４、８、１６、３２、６４、１２８のうちのいずれか１つであり得る。
【００３０】
キャリー生成部２０は、キャリー生成信号ＧＧ及びキャリー伝達信号ＰＰに応答して、ブロックキャリーＢＣ及び入力キャリーＣＩＮを生成する。キャリー生成部２０はＮビットのリーフセルを含むが、リーフセルは幾つかずつにグループ化されている。これについては、図２を参照して後述する。
【００３１】
グループバイパス部３０は、キャリー伝達信号ＰＰ及び入力キャリーＣＩＮに応答して、出力キャリーＣＯＵＴを生成する。
【００３２】
合算部４０は、キャリー伝達信号ＰＰ及び入力キャリーＣＩＮに応答して、Ｎビットの２つの入力の和ＳＯＵＴを導出する。
キャリー生成信号ＧＧは、次の数式（１）のように、２つの入力の論理積である。
【００３３】
【数１】
2008033937.tif 000003
【００３４】
キャリー伝達信号は、数式（２）のように２つの入力の排他的論理和である。
【００３５】
【数２】
2008033937.tif 000004
【００３６】
合算部４０の出力であるＳＯＵＴは、次の数式（３）のように表される。
【００３７】
【数３】
2008033937.tif 000005
【００３８】
図２は、本発明の一実施例による図１の条件選択加算器のキャリー生成部２０及びグループバイパス部３０のリーフセルを示す概略図である。図２は、図１の条件選択加算器が３２ビット演算を行うことを仮定したものである。
【００３９】
図２を参照すると、キャリー生成部２０は、入力ビットと同数（ここでは、３２）のリーフセル（ＬＣ０乃至ＬＣ３１）を含む。即ち、キャリー生成部２０は、３２個のリーフセルを含む。各リーフセルには、それぞれの入力から生成されたキャリー信号（ＰＰｉ、ＧＧｉ）が入力される。即ち、リーフセルＬＣ０にはＰＰ０とＧＧ０が入力され、リーフセルＬＣ１にはＰＰ１とＧＧ１が入力される。３２個のリーフセルは、一定の規則によってグループ化される。３２個のリーフセルは、含まれるリーフセルの数が２であるグループ１（Ｇ１）、含まれるリーフセルの数が３であるグループ２（Ｇ２）のように上位グループに行くほど、すぐ下のグループよりも含まれるリーフセルの数が１ずつ増加する。図２においては、グループ４（Ｇ４）とグループ５（Ｇ５）のリーフセルの数が同じであるが、これは、リーフセルの個数によりグループを昇冪の順に配置し、さらに、残りビットに対するリーフセルを含むグループを一定の規則によって配置したものである。これについては、図４及び図５を参照して後述する。
【００４０】
それぞれのリーフセルは、それぞれのキャリー生成信号ＧＧｉ及びキャリー伝達信号ＰＰｉの入力を受けて入力キャリーＣＩＮｉを生成し、１つ上のリーフセルに提供する。各グループの最後のリーフセルは、１つ下のリーフセルで生成された入力キャリーＣＩＮｉと該当キャリー生成信号ＧＧｉ及びキャリー伝達信号ＰＰｉとの入力を受けてブロックキャリーＢＣを生成する。このように、ブロックキャリーＢＣは、キャリー生成部２０の各グループの最後のリーフセル（ＬＣ１、ＬＣ４、ＬＣ８、ＬＣ１３、ＬＣ１８、ＬＣ２４、ＬＣ３１）でのみ生成され、グループバイパス部３０の該当リーフセル（ＢＬＣ１、ＢＬＣ２、ＢＬＣ３、ＢＬＣ４、ＢＬＣ５、ＢＬＣ６、ＢＬＣ７）に伝達される。このようにグループバイパス部３０の該当リーフセル（ＢＬＣ１、ＢＬＣ２、ＢＬＣ３、ＢＬＣ４、ＢＬＣ５、ＢＬＣ６、ＢＬＣ７）に伝達されたブロックキャリーＢＣとキャリー伝達信号ＰＰに基づいて、出力キャリーＣＯＵＴが生成されることになる。
【００４１】
図２に示すように、グループバイパス部３０にはキャリー生成部２０に含まれるグループの個数だけのリーフセルがある。即ち、１つのグループにそれぞれ該当する１つのリーフセルが含まれる。
【００４２】
図示していないが、キャリー生成部２０のそれぞれのリーフセル（ＬＣ０乃至ＬＣ３１）で生成された入力キャリーＣＩＮｉは、勿論合算部４０にも伝達され、２つの入力の和ＳＯＵＴを演算するのにも提供される。
【００４３】
図２でブロックキャリーＢＣが発生されるまでの最大のゲート遅延は、最多数のリーフセルを含んでいるグループ７（Ｇ７）で発生する。ここで、ブロックキャリーＢＣに対するゲート遅延は、キャリー生成信号ＧＧｉ及びキャリー伝達信号ＰＰｉの入力を受けた後からグループバイパス部３０の該当リーフセルにブロックキャリーＢＣが伝達されるまでのゲート数である。即ち、キャリー生成部２０で最も多くのリーフセルを含んでいるグループのリーフセルの個数がブロックキャリーＢＣに対するゲート遅延である。図２では、グループ７（Ｇ７）が最も多い７個のリーフセルを含んでいるので、ブロックキャリーＢＣに対するゲート遅延は７になる。
【００４４】
図２の構成において、出力キャリーＣＯＵＴに対するゲート遅延は、キャリー伝達信号ＰＰｉとキャリー生成信号ＧＧｉの伝達を受けた後から出力キャリーＣＯＵＴが生成されるまでのゲート遅延である。グループ１（Ｇ１）のリーフセルＬＣ０から出力キャリーＣＯＵＴまでのゲート遅延は、［１］乃至［８］の矢印で表示された８に１を足して９である。それぞれグループ２（Ｇ２）のリーフセルＬＣ２、グループ３（Ｇ３）のリーフセルＬＣ５、グループ４（Ｇ４）のリーフセルＬＣ９から出力キャリーＣＯＵＴに対するゲート遅延も９である。グループ５（Ｇ５）のリーフセルＬＣ１４、グループ６（Ｇ６）のリーフセルＬＣ１９、グループ７のリーフセルＬＣ２５から出力キャリーＣＯＵＴに対するゲート遅延は（１）乃至（７）で表示された矢印の個数だけの７に１を足して８である。
【００４５】
図２の構成において、データスキューは、最上位グループＧ７で生成された入力キャリーＣＩＮがグループバイパス部３０のリーフセルＢＬＣ７に到着するまでのゲート遅延と最下位グループＧ１で生成された入力キャリーＣＩＮがグループバイパス部３０のリーフセルＢＬＣ７に到着するまでのゲート遅延との差である。図２では、８−７＝１がデータスキューである。このようなデータスキューが小さいほど、加算器の演算速度は速くなるので、データスキューが加算器の演算速度の尺度になることができる。
【００４６】
図３は、本発明の一実施例による条件選択加算器と比較するために、図２の方式とは異なるようにグループ化された加算器のキャリー生成部１１０及びグループバイパス部１２０のリーフセルを示す概略図である。図３は、図１の加算器と他の部分は同じであり、キャリー生成部１１０及びグループバイパス部１２０のみが異なる場合を仮定したものである。図３も図２の場合のように、入力ビットが３２ビットである場合を仮定する。
【００４７】
図３を参照すると、グループバイパス部１１０は、全部で８つのグループ（Ｇ１乃至Ｇ８）に分けられている。各グループを構成するリーフセルの個数は、２、３、４、５、６、５、４、３である。即ち、リーフセルの個数により昇冪の順にグループ化し配置した後、降冪の順にリーフセルをグループ化し配置した。この方法については、図６及び図７を参照して後述する。
【００４８】
図３の動作は、図２と類似なので、これについての詳細な説明は省略する。
図３の構成では、ブロックキャリーＢＣに対するゲート遅延は、リーフセルの個数が一番多いグループ５（Ｇ５）で発生する。グループ５（Ｇ５）のリーフセルの個数は６なので、ブロックキャリーＢＣに対するゲート遅延は６である。図３の構成で出力キャリーＣＯＵＴに対するゲート遅延は、［１］乃至［９］の矢印で表示された９に１を足して１０である。図３の構成において、データスキューは［１］乃至［９］の矢印で表示された９からグループ８（Ｇ８）のゲート遅延である（１）乃至（３）の矢印で表示された３を引いた６である。即ち、図３の構成では、ブロックキャリーＢＣに対するゲート遅延は６なので、図２の構成におけるゲート遅延である７より良く見えるが、データスキューが６であるので、演算速度では図２の構成がずっと優れていることがわかる。
【００４９】
図４及び図５は、本発明の一実施例による条件選択加算器の図２のキャリー生成部２０のリーフセルをグループ化する方法と、残りビットを含むグループをどこに配置するかを示すフローチャートである。
【００５０】
まず、加算される２つの入力ビットを選択する（Ｓ４１０）。その後、ＧＲＯＵＰを１に、ＴＯＴＡＬを０に設定する（Ｓ４２０）。続いて、ＧＲＯＵＰを１増加させる（Ｓ４３０）。即ち、グループに含まれるリーフセルの個数が上位グループに行くほど増加する昇冪の順という意味である。次に、ＴＯＴＡＬとＧＲＯＵＰとの和をＴＯＴＡＬに設定する（Ｓ４４０）。その後、設定されたＴＯＴＡＬ値とＳ４１０で選択されたビット数とを比較する（Ｓ４５０）。比較した結果、設定されたＴＯＴＡＬ＋値が入力ビット数より小さいと、グループを結果ＧＲＯＵＰに設定し（Ｓ４６０）、更にＧＲＯＵＰの値を１増加させる（Ｓ４３０）。比較した結果、設定されたＴＯＴＡＬ値が選択された入力ビット以上であれば、終了する。
【００５１】
図５を参照すると、まず、Ｓ４１０段階で選択されたビット数からＳ４４０段階で設定されたＴＯＴＡＬ値を引いた値をＲＥＭに設定する。このＲＥＭの値が１であるか否かを判断して（Ｓ４８０）、ＲＥＭが１であれば、１つのリーフセルを含むグループを一番目のグループに配置する。このＲＥＭが１でなければ（１より大きければ）、このＲＥＭの値と同一数のリーフセルを有するグループの前に残りビットに該当する数のリーフセルを有するグループを配置する（Ｓ４９５）。３２ビットを例として挙げると、ＲＥＭが５になるので、図２ではグループ５（Ｇ５）の前にグループ４（Ｇ４）が位置することになる。
【００５２】
図６及び図７は、本発明の一実施例による条件選択加算器と比較するための図３のリーフセルをグループ化する方法と、残りビットを含むグループをどこに配置するかを示すフローチャートである。
【００５３】
図６を参照すると、まず、加算される２つの入力ビットを選択する（Ｓ５１０）。その後、ＧＲＯＵＰを１に、ＴＯＴＡＬを０に設定する（Ｓ５２０）。次に、選択されたビット数を２で割る（Ｓ５３０）。その後、選択されたビット数を２で割った値がＴＯＴＡＬより大きいか否かを判定する（Ｓ５４０）。選択されたビット数を２で割った値がＴＯＴＡＬより大きければＧＲＯＵＰの値を１増加させ（Ｓ５５０）、選択されたビット数を２で割った値がＴＯＴＡＬより小さければＧＲＯＵＰの値を１減少させる（Ｓ５６０）。続いて、１減少されたＧＲＯＵＰ値が１であるか否かを判断する（Ｓ５７０）。減少されたＧＲＯＵＰ値が１であれば、終了する。減少されたＧＲＯＵＰ値が１でなければ、ＧＲＯＵＰにＴＯＴＡＬを足した値をＴＯＴＡＬに設定する（Ｓ５８０）。次に、この設定されたＴＯＴＡＬ値が入力ビット数以上であるかを比較する（Ｓ５９０）。比較の結果、設定されたＴＯＴＡＬ値が入力ビット数より小さければ、そのＧＲＯＵＰを結果ＧＲＯＵＰに設定して、更にＳ５４０段階に戻す（Ｓ５９５）。比較の結果、設定されたＴＯＴＡＬ値が入力ビット数以上であれば、終了する。
【００５４】
図７を参照すると、まず、Ｓ５１０段階で選択された入力ビット数からＳ５８０段階で設定されたＴＯＴＡＬ値を引いた値をＲＥＭに設定する（Ｓ６１０）。その後、ＲＥＭが１であるか否かを判断する（Ｓ６２０）。ＲＥＭが１であれば、残りビットに該当する１つのリーフセルを含むグループを一番目の結果グループに配置する。ＲＥＭが１でなければ、リーフセルの個数によって降冪の順に配置されたグループのうちでこのＲＥＭの値と同じ数のリーフセルを有するグループの前に、残りビットに該当するリーフセルを有するグループを配置する（Ｓ６４０）。図３での３２ビットの場合には、Ｓ５９０段階でＴＯＴＡＬの値が３２なので、Ｓ６１０段階でＲＥＭが３２−３２として０になる。
【００５５】
図８は、本発明の一実施例による条件選択加算器と比較するために、残りビットに該当するリーフセルを含むグループを再配置することなく、最終グループに配置する場合を示す概略的なブロック図である。
【００５６】
図８の構成によると、ブロックキャリーＢＣに対するゲート遅延はグループ６（Ｇ６）のリーフセルの個数である６で、出力キャリーＣＯＵＴに対するゲート遅延は９である。データスキューは［１］乃至［８］の矢印で表示された８から（１）乃至（５）の矢印で表示された５を引くと、即ち、８−５をすると、３になる。図８のように、残りビットに該当するリーフセルを含むグループを再配置しないと、再配置する場合よりデータスキューが更に２増加することになる。
【００５７】
図９は、２つの入力が３２ビットである時、ランダム方式のグループ化、図３の昇冪の順及び降冪の順によるグループ化、図８の残りビット未処理時のグループ化、図２の昇冪の順によるグループ化（本発明）の、残りビットを処理した場合におけるそれぞれのブロックキャリーＢＣに対するゲート遅延、出力キャリーＣＯＵＴに対するゲート遅延、ＳＯＵＴまでのゲート遅延及びデータスキューを比較した表である。
【００５８】
図９で、ランダム方式のグループ化では、各グループに含まれるリーフセルの個数が２−４−３−５−９−４−５である。ＳＯＵＴまでのゲート遅延は、２つの入力ビットからＳＯＵＴが出力されるまでのゲート遅延なので、ブロックキャリーＢＣに対するゲート遅延に２を足すと良い。
【００５９】
図９でも示すように、加算器の速度に一番大きな影響を及ぼすのは、キャリーの伝達速度の差異によるデータスキューである。本発明の一実施例による昇冪の順にグループ化し配置して残りビットを一定の位置に配置した場合に、データスキューが１となり、一番小さかった。これは、本発明の一実施例による条件選択加算器の速度が一番速いことを示す。
【００６０】
以上、本発明を実施例によって詳細に説明したが、本発明はこれに限定されず、本発明が属する技術分野において通常の知識を有するものであれば本発明の思想と精神を離れることなく、本発明を修正または変更できる。
【図面の簡単な説明】
【００６１】
【図１】本発明の一実施例による条件選択加算器の概略的なブロック図である。
【図２】本発明の一実施例による図１の条件選択加算器のキャリー生成部及びグループバイパス部のリーフセルを示す概略図である。
【図３】本発明の条件選択加算器と比較するために、昇冪の順及び降冪の順にグループ化された加算器のキャリー生成部及びグループバイパス部のリーフセルを示す概略図である。
【図４】本発明の一実施例による条件選択加算器の図２のリーフセルをグループ化する方法と、残りビットに該当するリーフセルを含む残りグループを配置する方法とを示すフローチャートである。
【図５】本発明の一実施例による条件選択加算器の図２のリーフセルをグループ化する方法と、残りビットに該当するリーフセルを含む残りグループを配置する方法とを示すフローチャートである。
【図６】図３のリーフセルをグループ化する方法と残りビットに該当するリーフセルを含む残りグループを配置する方法とを示すフローチャートである。
【図７】図３のリーフセルをグループ化する方法と残りビットに該当するリーフセルを含む残りグループを配置する方法とを示すフローチャートである。
【図８】図２のリーフセルで残りビットに該当するリーフセルを含むグループを再配置しない場合の概略的なブロック図である。
【図９】多様なグループ化方法によるゲートデレイ及びデータスキューを示す表である。
【符号の説明】
【００６２】
１０    キャリー信号生成部
２０    キャリー生成部
３０    グループバイパス部
４０    合算部
【図１】
2008033937.tif 000006
【図２】
2008033937.tif 000007
【図３】
2008033937.tif 000008
【図４】
2008033937.tif 000009
【図５】
2008033937.tif 000010
【図６】
2008033937.tif 000011
【図７】
2008033937.tif 000012
【図８】
2008033937.tif 000013
【図９】
2008033937.tif 000014