(57)【要約】【課題】全加算回路グループを変更し、所定の数の入力ビットの論理関数を計算する方法を提供する。【解決手段】前記全加算回路のそれぞれは、第１及び第２データ入力、データ出力、桁上げ入力、及び桁上げ出力を有する。前記全加算回路は相互に接続されて桁上げチェーンを構成する。前記方法は、前記全加算回路のそれぞれの第１の入力を同じ固定値に設定する工程と、前記所定の数の入力ビットをそれぞれ前記全加算回路の第２の入力に接続する工程と、前記全加算回路のアレイからなる桁上げチェーンの出力を前記論理関数の結果として用いる工程とを備える。【選択図】図１
2010009592.tif 000002
【特許請求の範囲】
【請求項１】
全加算回路グループを変更し、所定の数の入力ビットの論理関数を計算する方法であって、前記全加算回路のそれぞれは、第１及び第２データ入力、データ出力、桁上げ入力、及び桁上げ出力を有し、前記全加算回路は相互に接続されて桁上げチェーンを構成し、
前記全加算回路のそれぞれの第１の入力を同じ固定値に設定する工程と、
前記所定の数の入力ビットをそれぞれ前記全加算回路の第２の入力に接続する工程と、
前記全加算回路のアレイからなる桁上げチェーンの出力を前記論理関数の結果として用いる工程とを備える方法。
【請求項２】
前記固定値は論理ＬＯＷであり、前記論理関数は論理積又は否定論理積である、請求項１に記載の方法。
【請求項３】
前記固定値は論理ＨＩＧＨであり、前記論理関数は論理和又は否定論理和である、請求項１に記載の方法。
【請求項４】
前記全加算回路はそれぞれブース乗算器の一部を構成する、請求項１に記載の方法。
【請求項５】
全加算回路グループを変更し、所定の数の入力ビットの論理関数を計算する装置であって、前記全加算回路のそれぞれは、第１及び第２データ入力、データ出力、桁上げ入力、及び桁上げ出力を有し、前記全加算回路は相互に接続されて桁上げチェーンを構成し、
前記全加算回路のそれぞれの第１の入力を同じ固定値に設定するための設定手段と、
前記所定の数の入力ビットをそれぞれ前記全加算回路の第２の入力に接続するための接続手段と、
前記全加算回路のアレイからなる桁上げチェーンの出力を前記論理関数の結果として伝播するための伝播手段とを備える装置。
【請求項６】
前記固定値は論理ＬＯＷであり、前記論理関数は論理積又は否定論理積である、請求項５に記載の装置。
【請求項７】
前記固定値は論理ＨＩＧＨであり、前記論理関数は論理和又は否定論理和である、請求項５に記載の装置。
【請求項８】
前記全加算回路はそれぞれブース乗算器の一部を構成する、請求項５に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、乗算回路等に用いる加算回路のアレイ又はAND/OR面として機能できる専用論理回路に関する。
【背景技術】
【０００２】
一般的に、リコンフィギュラブル装置／構造は、ユーザがプログラム可能な単一の論理ブロック又はタイル、すなわちシステムにおける基本の構成ブロック、の複数のインスタンスから構成される。この構成により、一様な規則的構造をした容易に拡張可能な構成メカニズムを利用しやすくなる。
【０００３】
リコンフィギュラブル装置／構造内に組み込まれた専用機能ブロックの挿入は、特定の使用状況において装置／構造の性能を向上させるためにしばしば行われる。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、これらの専用ブロックは、それらの特定の機能を必要とする用途でしか役に立たない。別の用途に対してはほとんどあるいは全く利点が無く、コストがかさむだけである。これは、特に乗算器やプログラマブル論理アレイ（ＰＬＡ）の場合に当てはまる。乗算器はデータ処理の用途でのみ用いられ、一方、ＰＬＡは主に制御構造であってデータパスに用途が極めて限られている。
【０００５】
更に、機能ブロックを配置する場所を決定する際に問題が生じる。例えば、単一のリコンフィギュラブル回路を２つの異なる用途に用いる場合、一方の用途に対してはＰＬＡと乗算器とのローカライズされた集団を用い、他の用途に対してはＰＬＡと乗算器との均一な配列を用いることが望ましい。したがって、それぞれの用途に対して回路を最適化するＰＬＡと乗算器との最適な配列を見つけるという点が問題である。
【０００６】
以上の問題を部分的に解決するために、アレイにわたってＰＬＡと乗算器との設定配列が設けられた。これらの設定配列は、例えば、乗算器とＰＬＡとの同種の配列である。しかしこれは、特定の構成においてアレイの特定の領域で一定の数の乗算器が必要でありかつその数が設定配列の前記特定の領域内での乗算器の数を超えている場合に、他の乗算器を領域外で使用する必要があり、その結果、回路の経路選択がより複雑になるという点において、問題を部分的に解決するにすぎない。
【０００７】
上に述べた問題を更に解決するために、それぞれ異なる数の種類の埋め込みブロックを有する、プログラマブル論理装置における標準の「ファミリー」が作られた。各用途では、乗算器とＰＬＡに対してそれぞれ特有の要求がある。しかし、それぞれ多数の特徴を共有するアプリケーションドメインにおいて、用途はグループ化される。したがって、それぞれ１つのアプリケーションドメインに特によく適している有限数の異なるテンプレート装置を製造することが可能である。しかし、ファミリーの作成によって１つの設定配列から有限数の構成へとアーキテクチャの種類は増えるものの、この解決策は、完全に用途に特有な構成の柔軟性を提供するには至らない。
【０００８】
したがって、乗算器又はAND/OR面（AND/OR plane）として機能するように容易に再構築可能な専用論理回路が必要であることは明らかである。
【課題を解決するための手段】
【０００９】
上述した従来の問題を解決するために、本発明は、全加算回路グループを変更し、所定の数の入力ビットの論理関数を計算する方法であって、前記全加算回路のそれぞれは、第１及び第２データ入力、データ出力、桁上げ入力、及び桁上げ出力を有し、前記全加算回路は相互に接続されて桁上げチェーンを構成し、前記全加算回路のそれぞれの第１の入力を同じ固定値に設定する工程と、前記所定の数の入力ビットをそれぞれ前記全加算回路の第２の入力に接続する工程と、前記全加算回路のアレイからなる桁上げチェーンの出力を前記論理関数の結果として用いる工程とを備えることを特徴とする方法を提供する。
【００１０】
前記前記固定値は論理ＬＯＷであり、前記論理関数は論理積又は否定論理積であってもよい。
【００１１】
前記固定値は論理ＨＩＧＨであり、前記論理関数は論理和又は否定論理和であってもよい。
【００１２】
前記全加算回路はそれぞれブース乗算器の一部を構成してもよい。
【００１３】
本発明は更に、全加算回路グループを変更し、所定の数の入力ビットの論理関数を計算する装置であって、前記全加算回路のそれぞれは、第１及び第２データ入力、データ出力、桁上げ入力、及び桁上げ出力を有し、前記全加算回路は相互に接続されて桁上げチェーンを構成し、前記全加算回路のそれぞれの第１の入力を同じ固定値に設定するための設定手段と、前記所定の数の入力ビットをそれぞれ前記全加算回路の第２の入力に接続するための接続手段と、前記全加算回路のアレイからなる桁上げチェーンの出力を論理関数の結果として伝播するための伝播手段とを備えることを特徴とする装置を提供する。
【００１４】
前記固定値は論理ＬＯＷであり、前記論理関数は論理積又は否定論理積であってもよい。
【００１５】
前記固定値は論理ＨＩＧＨであり、前記論理関数は論理和又は否定論理和であってもよい。
【００１６】
前記全加算回路はそれぞれブース乗算器の一部を構成してもよい。
【発明の効果】
【００１７】
周知のように、本発明は従来技術にまさる幾つかの効果を有する。例えば、本発明では全体として必要な組み込みユニットの数が少なく、アレイにわたるAND/OR面と乗算器の相対的な配列を決定する際の諸問題や、ネットワーク経路領域を増加なければならないコストを解消できる。例えば、特定のアプリケーションドメインで全体として計１００個の乗算器及び／又はAND/OR面が必要であれば、アプリケーションドメイン内の特定の用途において乗算器２５個：AND/OR面７５個から乗算器７５個：AND/OR面２５個まで比を変化させる必要がある。従来の方法では、単一の装置が全てのアプリケーションを実行するので、７５個のAND/OR面と７５個の乗算器（合計１５０ユニット）が必要である。一方、本発明に係る装置では、必要なユニットは合計で１００個以下である。したがって、本発明に係る装置では必要な組み込みユニットの数が少ないことは明らかである。さらに、本発明においては、どの単一ユニットも乗算器又はAND/OR面として機能することのできるという点で、乗算器及びAND/OR面の配列に関して柔軟性がある。
【図面の簡単な説明】
【００１８】
【図１】本発明の例に係る４×４符号なし２進乗算回路の高レベルブロック図である。
【図２】図１に示す高レベルブロック図の別の図である。
【図３】図１及び図２に示す４×４符号なし２進乗算回路の加算回路を示す論理図である。
【図４】本発明の別の例に係るブース乗算回路の高レベルブロック図である。
【図５】図６に示すブース乗算回路の加算回路を示す論理図である。
【図６】本発明の別の例に係るブース乗算回路をより詳細に示すブロック図である。
【図７】本発明の別の例に係る桁上げバイパス加算回路を示す図である。
【図８】本発明の別の例に係る桁上げバイパスツリー回路を示す図である。
【図９】本発明の別の例に係る桁上げ先見回路を示す図である。
【図１０】図９に示す回路の別の実施例を示す図である。
【図１１】図９に示す回路の別の実施例を示す図である。
【発明を実施するための形態】
【００１９】
以下、本発明の第１の例を、図１を参照しながら説明する。図１は、４×４符号なし２進乗算器の可能な実現例を示す高レベルブロック図である。図１に示す回路における各加算回路は全加算器を備えている。図２は図１の回路の別の形態を示す図であり、図３は図１及び図２の回路における加算回路の１つを詳しく説明した図である。
【００２０】
図２から分かるように、回路のX及びY入力はそれぞれ垂直及び水平に伝わる。桁上げ信号(Cout)は垂直に伝わり、和(Σ)は斜めに伝わる。
【００２１】
図３において、得られる回路は以下の論理式を実現する。
【数１】
2010009592.tif 000003
ここで、もし各加算セルにおいてB（伝達中の総入力）が０にされると、
【数２】
2010009592.tif 000004
となる。各セルのCoutは別のセルのCinに接続しているため、１行のセルに沿って
【数３】
2010009592.tif 000005
となる。したがって、Bを０にすると、Coutは入力ビット群のAND関数となる。同様に、Bを１にすると、
【数４】
2010009592.tif 000006
となる。よって、Bを１にすると、Coutは入力ビット群のOR関数となる。
【００２２】
したがって、Bの値を０又は１に制限して乗算器アレイにおいて和が伝播することを効果的に防ぐことにより、桁上げチェーンを介してAND及びOR関数を生成することが可能になる。周知のように、AND及びOR関数は、プログラマブル論理アレイ（ＰＬＡ）で実現される論理関数（logic function, Boolean function）の積和の基本の構成ブロックである。
【００２３】
次に、図４及び図５を参照しながら本発明の第２の例について説明する。図４は本発明に係るブース符号化乗算器の変形例を示す。図５は、図４に示すブース符号化乗算器の加算回路の変形例を示す。
【００２４】
ブース符号化乗算器（Booth-encoded multiplier）において、加算回路は、各段階で以下の３つの動作のうちのいずれかを行うように変更される。第１の動作では、桁送りされた入力を現時点での合計に加算する。第２の動作では、桁送りした入力を現時点での合計から減算する。最後の動作では、変更されていない現時点での合計を伝播する。
【００２５】
減算を実現するため、入力のうち１つを反転し、最下位の加算回路のCinを１に設定する。これは、２の補数演算において、-YがNOT(Y)+1として表されるからである。
【００２６】
図５は、ブース乗算器の加算回路の変形例を示す。図５に示す加算回路の基本構造は前述した例と同様であるが、加算される適切な値を選択するために乗算器を更に設けている。
【００２７】
図３の加算回路は、全ての加算回路がXi及びXi+1とラベル付けした信号のそれぞれ異なる有効値を持つように変更されている。従来の乗算器では、これらの信号は一般に一列に並んだ全ての加算器で共有される。しかし、様々なOR面関数の出力をそれぞれ異ならせるためには、これらの信号を独立して設定できるようにすることが必要である。したがって、図５に示す例では、これらの信号を局部的に設定することのできる２つの構成ビットが設けられている。これらの加算器は乗算器の選択入力に接続し、Y、NOT(Y)、又は０をマルチプレクサの出力として選択できるようにする。図５は、この加算器の変形例を示す。この例において、OR面の場合、入力マルチプレクサ５０１はXi及びXi+1並びに２つの構成ビットで制御される。上記選択は、（そのような全てのセルで共有される）第３の構成ビットにより制御され、それにより動作の全体のモードを制御する。そのため、本例において、マルチプレクサ５０２を０に設定すると、Xi及びXi+1の値が共有された外部ソースから入力され、マルチプレクサ５０２を１に設定すると、Xi及びXi+1の値はローカルメモリから入力される。
【００２８】
図５からわかるように、ブース乗算器セルはYとNOT(Y)の両方に接続している。この入力を本発明の第１の例で述べたように制限すれば、ドモルガンの定理を利用することによりAND/OR機能を別の方法で実現することができる。例えば、回路のOR機能を利用してBを１に制限し、以下の動作モードが可能になる。
【００２９】
Y入力を通過させるようにマルチプレクサ５０１を設定すると、出力は以下の式で示すような複数のY入力の論理和となる。
【数５】
2010009592.tif 000007
【００３０】
しかし、NOT(Y)入力を通過させるようにマルチプレクサ５０１を設定すると、出力は以下の式に示すような複数のY入力の論理和となる。
【数６】
2010009592.tif 000008
又は
【数７】
2010009592.tif 000009
【００３１】
これらの式から分かるように、出力は、反転していない入力のNAND関数とみなすことができる。
【００３２】
最後に、マルチプレクサ５０１の一部のみがY入力を通過させそれ以外の部分はNOT(Y)入力を通過させるように設定した場合、出力は以下の式で示すようなNAND及びOR関数の組合となる。
【数８】
2010009592.tif 000010
又は
【数９】
2010009592.tif 000011
【００３３】
したがって、本発明の本例において、AND及びOR機能の両方を得るためには、B入力を１つの値に制限すればよい。ブース乗算器はマルチプレクサ出力において定数０を生成することができるが定数１（A|0=Aのため）は生成できないため、本発明の第１の例で説明した回路のOR形を用いて、それによりBを１に制限することが好ましい。このことにより、Y入力項の幾つかを出力において無視することが可能になる。そのため、以下の形の関数を得ることも可能である。
【数１０】
2010009592.tif 000012
又は
【数１１】
2010009592.tif 000013
又は
【数１２】
2010009592.tif 000014
【００３４】
図６は本発明に係るブース乗算回路の完全な実施を示す。
【００３５】
本発明の第１及び第２の実施形態を表す式は、生成／伝播構造を有する桁上げチェーンを備えている。このため、前記チェーンは、出力に伝播された桁上げ入力のコピー又は（B入力からコピーされた）新しく生成した値である。上記桁上げチェーンは以下の「伝播」信号により決定される。
【数１３】
2010009592.tif 000015
【００３６】
桁上げ信号を幾つかの単一ビット段階へ伝送できるようにバイパス路を設けることにより、マルチビット加算器における桁上げ伝播を加速することが望ましい。図７に示す実施形態において、これを達成するために必要なマルチプレクサは、それぞれの段階でのP出力の論理積をとることで生成される信号で制御される。図７に示す回路は、Z=A+Bという４ビットセクションを実行する。各Pi信号は４入力ANDゲートへ入力される。Cout信号が全てＨＩＧＨに設定されれば、マルチプレクサは入力１を選択し、CinをCout i+3へ伝播させる。したがってこの回路は、そうでなければ全ての加算器により桁上げ入力が伝播する場合、より高速なCin iからCout i+3への経路を選択する。
【００３７】
周知のように、Bを本発明の最初の２つの例に制約することにより、生成されうる桁上げ値を効果的に制限することができる。しかし、本発明の桁上げチェーンは通常の加算器や乗算器と同じように動作する。そのため、上述した桁上げバイパス回路は、桁上げ信号の伝播を加速するように動作可能である。
【００３８】
なお、図７に示すバイパスマルチプレクサを制御するANDゲートの出力をゲートツリーの一部として直接用いて、より広範囲の加算器における全てのP信号の論理積を生成してもよい。図８は、これを実行する回路を示す。図８の回路は、図７に示す回路を２つ備えると効果的である。しかし、これらの回路のANDゲートの出力自体は１つのANDゲートに入力され、その出力は論理関数出力として用いられる。
【００３９】
マルチビット加算器の桁上げ回路を加速する別の方法として、桁上げ先見回路を用いてもよい。ある桁上げビットの式を幾つかの加算器ビットに拡張すると、より項の多い式になるが、AND及びORゲートの簡単なツリーとして構築することができる。この式を実現する回路は、上述したリップルキャリー回路よりも大きいが、それよりも高速である。例えば、２段階桁上げ先見回路は以下の式で表される。
【数１４】
2010009592.tif 000016
【００４０】
上記式を実現する回路を図９に示す。B＝１の固定値に制限すると、次のようになる。
【数１５】
2010009592.tif 000017
【００４１】
これにより、A入力のOR関数が別の方法で得られる。上述のような桁上げチェーンを用いる代わりに、これらのノードに直接タップを取り付けて論理ゲートの専用ツリーへの入力とし、OR関数を生成してもよい。この方法を図１０に示す。
【００４２】
同様に、上述の式も単一のAi+1Ai項を有するため、図１１に示すように、直接タップを取り付けてA入力のAND関数を生成するツリーを駆動してもよい。このことにより、桁上げチェーンを経てOR関数を生成しつつ、同時にAND関数を生成することができる。更に、Bに対する単一の制限値を用いてAND及びOR関数の両方を得ることができる。また、ブース乗算器の例では、取得可能な関数の範囲を広げるために入力の補数を利用することもできる。
【００４３】
したがって、上記実施形態はアレイ乗算器を備えているが、本発明を、相互に接続されて桁上げチェーンを構成する多数の加算回路を備える他の回路と共に用いてもよい。このような回路としては、例えば、分周器や有限長インパルス応答（ＦＩＲ）フィルタが挙げられる。
【図１】
2010009592.tif 000018
【図２】
2010009592.tif 000019
【図３】
2010009592.tif 000020
【図４】
2010009592.tif 000021
【図５】
2010009592.tif 000022
【図６】
2010009592.tif 000023
【図７】
2010009592.tif 000024
【図８】
2010009592.tif 000025
【図９】
2010009592.tif 000026
【図１０】
2010009592.tif 000027
【図１１】
2010009592.tif 000028