(57)【特許請求の範囲】
【請求項１】
第１ないし第４入力信号のＸＯＲを求めて奇数信号として発生させ、前記第１及び第２入力信号のＸＯＲを求めて第１ＸＯＲ信号として出力する奇数検出部と、
前記第１ＸＯＲ信号のロジック‘１’に応答して、前記第３入力信号をキャリ出力信号として出力する第１スイッチと、
反転された前記第１ＸＯＲ信号のロジック‘０’に応答して、前記第１入力信号を前記キャリ出力信号として出力する第２スイッチと、
前記奇数信号に応答して、キャリ入力信号を桁上げとして出力する第３スイッチと、
反転された前記奇数信号に応答して、前記第４入力信号を桁上げとして出力する第４スイッチと、
前記奇数信号に応答して、反転された前記キャリ入力信号を和として出力する第５スイッチと、
反転された前記奇数信号に応答して、前記キャリ入力信号を前記和として出力する第６スイッチと、を備えることを特徴とする４:２ＣＳＡセル。
【請求項２】
前記奇数検出部は、
前記第１及び第２入力信号のＸＯＲを求めて、前記第１ＸＯＲ信号を発生させる第１ＸＯＲゲートと、
前記第３及び第４入力信号のＸＯＲを求めて、第２ＸＯＲ信号を発生させる第２ＸＯＲゲートと、
前記第１及び第２ＸＯＲ信号のＸＯＲを求めて、前記奇数信号を発生させる第３ＸＯＲゲートと、を備えることを特徴とする請求項１に記載の４:２ＣＳＡセル。
【請求項３】
第１ないし第４入力をＸＯＲして第１ＸＯＲ信号を求める段階と、
前記第１及び第３入力をＸＯＲして第２ＸＯＲ信号を求める段階と、
前記第２ＸＯＲ信号のロジック‘０'に応答して、前記第１入力をキャリ出力信号Ｃｏｕｔとして出力する段階と、
前記第２ＸＯＲ信号のロジック‘１'に応答して、前記第３入力を前記キャリ出力信号Ｃｏｕｔとして出力する段階と、
前記第１ＸＯＲ信号のロジック ‘０'に応答して、前記第４入力を桁上げＣｒｙとして出力する段階と、
前記第１ＸＯＲ信号のロジック ‘１'に応答して、キャリ入力信号を桁上げＣｒｙとして出力する段階と、
前記第１ＸＯＲ信号のロジック ‘０'に応答して、前記キャリ入力信号を和Ｓｕｍとして出力する段階と、
前記第１ＸＯＲ信号のロジック ‘１'に応答して、反転された前記キャリ入力信号を前記和Ｓｕｍとして出力する段階と、を備えることを特徴とする４:２キャリ保存加算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル乗算装置に係り、特に単純な構造の４:２キャリ保存加算器(Ｃａｒｒｙ−Ｓａｖｅ Ａｄｄｅｒ：以下、“ＣＳＡ”と称する)及び４:２キャリ保存加算方法に関する。
【背景技術】
【０００２】
デジタルコンピュータ演算は、複雑なロジック回路と有効なハードウェアとを利用するための効率的なアルゴリズムを含む。デジタルコンピュータ内で使われる数は、０または１のストリングで表現され、ハードウェアは相対的に簡単で基本的なブール演算を行う。全ての演算動作は、最も簡単な演算から始まる階層的な演算動作を基に行われる。特定の計算方法、または、特定のアルゴリズムにより行われるコンピュータ演算によりデジタルコンピュータの性能が決定される。
【０００３】
現代のコンピュータシステムにおいて、最も多く使われる演算の一つとして、高速の計算システムを構成する時、乗算速度を向上させることが必須的である。高速の乗算を実現するための方法として、乗数を修正して部分積の総数を減少させるブースアルゴリズムが公知である。そして、部分積をツリー状に加算し、部分積の総数を順次に減少させるウォレスツリを使用する乗算装置も公知である。
【０００４】
図１は、ウォレスツリ部の構成を説明する図である。これを参照すると、３２×３２乗算装置の設計を仮定した場合、４ラディックスブースレコーディング方式を使用して作られる１６個の部分積ＰＰ０−ＰＰ１５がＣＳＡに提供される。図示したように、１６個の部分積ＰＰ０−ＰＰ１５を加算するために、６段階の１４個のＣＳＡセルが必要である。各々のＣＳＡセルは、３:２ＣＳＡセルで構成され、３個の部分積(例えば、ＰＰ１−ＰＰ３)を入力として提供され、２個の出力である和Ｓｕｍと桁上げＣｒｙとを出力する。
【０００５】
このようなウォレスツリ構造において、各ＣＳＡセルは少なくとも３２ビット、多くは６４ビットを処理するための計算空間を要する。これにより、ハードウェアで実現した時、シリコンチップが占める面積が大きくなる。そして、最終のＣＳＡレベルに達するまで、桁上げの計算速度より和の計算速度の方が遅いため、計算が進むにしたがってグリッチ状の波形が生じて計算速度を落とす要因となる。
【０００６】
一方、図１のウォレスツリで計算速度を高めるために、３:２ＣＳＡセルの代りに４:２ＣＳＡセルを使用することができる。図２は、従来の４:２ＣＳＡセルを説明する図である。これを参照すると、４:２ＣＳＡセルは、４個の入力Ａ、Ｂ、Ｃ、Ｄと２個の出力Ｓｕｍ、Ｃｒｙとを有する２個の３:２ＣＳＡセルで構成される。例えば、３個の入力Ａ、Ｂ、Ｃについての和Ｓｕｍと桁上げＣｒｙとを求める３:２ＣＳＡセルは図３に示されている。和Ｓｕｍは入力Ａと入力Ｂとの排他的和３０１と、入力Ｃとの排他的和３０２とで求められ、桁上げＣｒｙは入力Ａと入力ＢとのロジックＮＡＮＤした値３０３、入力Ｂと入力ＣとをロジックＮＡＮＤした値３０４、そして入力Ａと入力ＣとのロジックＮＡＮＤした値３０５をロジックＮＡＮＤした値３０６で求められる。即ち、３:２ＣＳＡセルは、２個の排他的論理和ゲート３０１、３０２と４個のＮＡＮＤゲート３０３、３０４、３０５、３０６とで構成される。
【０００７】
４:２ＣＳＡセルは２個の３:２ＣＳＡセルで構成されるので、内部的に３:２ＣＳＡセルを構成するロジックゲート数の２倍が要求される。したがって、４:２ＣＳＡセルは４個の排他的論理和（ＸＯＲ）ゲートと、８個のＮＡＮＤゲートとで構成されるので、これらを構成するトランジスタは、図１のウォレスツリが占有するシリコンチップの面積の問題は何ら解決されていない。
そこで、ロジック最適化を通じて、ロジック段階を減らして消費電力を最小化できる新しい４:２ＣＳＡセルの存在が必要である。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明が解決しようとする課題は、単純な構造の４:２ＣＳＡセルを提供するところにある。
本発明が解決しようとする他の課題は、４:２キャリ保存加算方法を提供するところにある。
【課題を解決するための手段】
【０００９】
前記課題を解決するために、本発明の４:２ＣＳＡセルは第１ないし第４入力信号のＸＯＲを求めて奇数信号として発生させ、第１及び第２入力信号のＸＯＲを求めて第１ＸＯＲ信号として出力する奇数検出部と、第１ＸＯＲ信号に応答して、第３入力信号をキャリ出力信号として出力する第１スイッチと、反転された第１ＸＯＲ信号に応答して、第１入力をキャリ出力信号として出力する第２スイッチと、奇数信号に応答して、キャリ入力信号を桁上げとして出力する第３スイッチと、反転された奇数信号に応答して、第４入力信号を桁上げとして出力する第４スイッチと、奇数信号に応答して、反転されたキャリ入力信号を和として出力する第５スイッチと、反転された奇数信号に応答して、キャリ入力信号を和として出力する第６スイッチと、を含む。
【００１０】
前記他の課題を解決するために、本発明の４:２キャリ保存加算方法は、第１ないし第４入力のＸＯＲを求める段階と、第１及び第２入力のＸＯＲを求める段階と、第１及び第２入力のＸＯＲ‘０'に応答して、第１入力をキャリ出力信号Ｃｏｕｔとして出力する段階と、第１及び第２入力のＸＯＲ‘１'に応答して、第３入力をキャリ出力信号Ｃｏｕｔとして出力する段階と、第１ないし第４入力のＸＯＲ‘０’に応答して、第４入力を桁上げＣｒｙとして出力する段階と、第１ないし第４入力のＸＯＲ‘１'に応答して、キャリ入力信号を桁上げＣｒｙとして出力する段階と、第１ないし第４入力のＸＯＲ‘０’に応答して、キャリ入力信号を和Ｓｕｍとして出力する段階と、第１ないし第４入力のＸＯＲ‘１'に応答して、反転されたキャリ入力信号を和Ｓｕｍとして出力する段階と、を含む。
【発明の効果】
【００１１】
本発明の４:２ＣＳＡセルによれば、ロジック最適化を通じて、構成要素の数を減らしてその構成要素が占めるシリコンチップの占有面積を最小化し、消費電力を減らすことができる。
【発明を実施するための最良の形態】
【００１２】
本発明と、本発明の動作上の利点及び本発明の実施によって達成される目的を十分に理解するためには、本発明の望ましい実施例を例示する添付図面及び添付図面に記載された内容を参照しなければならない。
以下、添付された図面を参照して本発明の望ましい実施例を説明することにより、本発明を詳細に説明する。各図面に付された同一参照符号は同一部材を示す。
本発明の４:２ＣＳＡセルの説明に先立って、図２の従来の４:２ＣＳＡセルの動作を真理値表で表わせば次の通りである。
【００１３】
【表１】
0004607604.tif 000002
【００１４】
ここで、入力Ａ、Ｂ、Ｃの和Ｓ０は、入力Ａと入力ＢとのＸＯＲ値、入力Ｃと入力ＤとのＸＯＲ値、そして入力Ｄの値で決定されることが分かる。また、入力Ａ、Ｂ、Ｃの桁上げＣｏｕｔは、入力Ａと入力ＢとのＸＯＲ値と、以前桁上げＣｉｎとによって入力Ａと入力Ｃのうち一つで選択されることが分かる。これから表２の通り整理された真理値表が得られる。
【００１５】
【表２】
0004607604.tif 000003
【００１６】
表２の真理値表を見れば、和Ｓｕｍと桁上げＣｒｙとの値は、入力Ａ、Ｂ、Ｃ及びＤのＸＯＲ値０または１によってキャリ入力Ｃｉｎや入力Ｄ値として決定され、キャリ出力Ｃｏｕｔは、入力Ａ及びＢのＸＯＲ値０または１によって入力Ａまたは入力Ｃとして決定される。これを整理すれば、表３の通りである。
【００１７】
【表３】
0004607604.tif 000004
【００１８】
従って、表３の最終真理値表によって実現される４:２ＣＳＡセルロジックは図４の通りである。これを参照すると、４:２ＣＳＡセルロジックは、奇数検出部４０２、第１ないし第３インバータ４０４、４０６、４０８、そして第１ないし第６スイッチ４１０、４１２、４１４、４１６、４１８、４２０を含む。
【００１９】
奇数検出部４０２は、具体的に図５に示されており、入力Ａ、Ｂを入力して第１ＸＯＲＡＢ＿ＸＯＲを出力する第１ゲート５０２、入力Ｃ、Ｄを入力して第２ＸＯＲＣＤ＿ＸＯＲを出力する第２ゲート５０４、そして第１ＸＯＲＡＢ＿ＸＯＲと第２ＸＯＲＣＤ＿ＸＯＲとを入力して奇数信号ＯＤＤを出力する第３ゲート５０６で構成される。奇数信号ＯＤＤは入力Ａ、Ｂ、Ｃ、ＤのＸＯＲを意味する。
【００２０】
また、４:２ＣＳＡセルロジックを見れば、第１インバータ４０４は第１ＸＯＲＡＢ＿ＸＯＲを反転させ、第２インバータ４０６は奇数信号ＯＤＤを反転させ、第３インバータ４０８はキャリ入力信号Ｃｉｎを反転させる。
【００２１】
第１スイッチ４１０は、第１ＸＯＲＡＢ＿ＸＯＲに応答して入力Ｃをキャリ出力信号Ｃｏｕｔとして出力し、第２スイッチ４１２は、反転された第１ＸＯＲ/ＡＢ＿ＸＯＲに応答して入力Ａをキャリ出力信号Ｃｏｕｔとして出力する。
第３スイッチ４１４は、奇数信号ＯＤＤに応答してキャリ入力信号Ｃｉｎを桁上げＣｒｙとして出力し、第４スイッチ４１６は、反転された奇数信号/ＯＤＤに応答して入力Ｄを桁上げＣｒｙとして出力する。
第５スイッチ４１８は、奇数信号ＯＤＤに応答して反転されたキャリ入力信号/Ｃｉｎを和Ｓｕｍとして出力し、第６スイッチ４２０は、反転された奇数信号/ＯＤＤに応答してキャリ入力信号Ｃｉｎを和Ｓｕｍとして出力する。
【００２２】
このような４:２ＣＳＡセルは、全体的に３個のＸＯＲゲートと３個のインバータ、そして６個のスイッチで構成される。これらの構成は、従来の４:２ＣＳＡセル（図２）の構成において必要とした４個のＸＯＲゲートと８個のＮＡＮＤゲートとの配置、及びそれら間の配線によるシリコンチップの占有面積より小さいシリコンチップの占有面積を占める。そして、減った構成要素によって消費電力の減少効果も奏する。
【００２３】
本発明は図面に示した一実施例を参考として説明されたが、これは例示的なものに過ぎず、当業者であれば、これから多様な変形及び均等な他の実施例が可能であるという点を理解できる。従って、本発明の真の技術的な保護範囲は、特許請求範囲の技術的思想により決まらねばならない。
【産業上の利用可能性】
【００２４】
本発明の４:２ＣＳＡと４:２キャリ保存加算方法とは、小さなチップ面積及び少ない消費電力が要求されるデジタル乗算装置に好適に利用できる。
【図面の簡単な説明】
【００２５】
【図１】４ラディックスブースレコーディング方式を利用した３２×３２乗算器を説明する図である。
【図２】従来の４:２ＣＳＡセルを説明する図である。
【図３】図２の３:２ＣＳＡセルの具体的な回路を説明する図である。
【図４】本発明の一実施例による４:２ＣＳＡセルを説明する図である。
【図５】図４の奇数検出部の具体的な回路を説明する図である。
【符号の説明】
【００２６】
４０２    奇数検出部
４０４    第１インバータ
４０６    第２インバータ
４０８    第３インバータ
４１０    第１スイッチ
４１２    第２スイッチ
４１４    第３スイッチ
４１６    第４スイッチ
４１８    第５スイッチ
４２０    第６スイッチ
【図１】
0004607604.tif 000005
【図２】
0004607604.tif 000006
【図３】
0004607604.tif 000007
【図４】
0004607604.tif 000008
【図５】
0004607604.tif 000009