JP3675111B2 - 3-input comparator - Google Patents

Description

【００３６】
上のように、入力Ａ，Ｂ，Ｃの各桁の“１”の数が、Ｅ，Ｄの各桁のビットをペアとして２進数で表現される。ＤとＥから（Ａ＋Ｂ＋Ｃ）の和を得るには、Ｄに対してＥを１桁左にずらして加算を行う（即ち、Ｄ＋２×Ｅ）。例えば、
D = P 0 1 0 1 0
E = 0 0 1 1 0 Q
ここで空欄“Ｐ”に符号拡張するように符号を補い、また空欄“Ｑ”に０を補って、

この結果は、（Ａ＋Ｂ＋Ｃ）＝１４＋６＋２＝２２に等しい。
【００３７】
このような３：２コンプレッサ処理を行う演算器としては、キャリー・セーブ（Carry Save）方式加算器が一般的に知られている。このキャリー・セーブ方式加算器とは、１ビット全加算器を必要なビット幅分並列に並べたものである。個々の全加算器は互いに接続されておらず、全く独立している。
【００３８】
１ビット全加算器の真理値表は、入力数値Ａ，Ｂ、桁上げ入力Ｃｉ、桁上げ出力Ｃｏ、和Ｓｕｍとしたとき、表１のようになる。
【表１】

【００３９】
この真理値表から、Ａ，Ｂ，Ｃｉにおける“１”の数が、Ｃｏ，Ｓｕｍをペアとして２進数で表現されていることが明らかである。全加算器の論理構成としては様々なものが知られているが、その遅延はＥＸ‐ＯＲゲート２段程度である。このような全加算器を用いることによって、３つの変数の加算（Ａ＋Ｂ＋Ｃ）を２つの変数の加算（Ｄ＋２×Ｅ）に置き換える、即ち３：２コンプレッサ処理が出来る。
【００４０】
３：２コンプレッサ段の遅延は１つの全加算器の遅延に等しく、入力数値Ａ，Ｂ，Ｃのビット幅ｎに依存しない。なぜなら、入力数値のビット幅分ある全加算器は相互に接続されておらず、各全加算器は全く独立に動作するからである。したがって、３：２コンプレッサ段の遅延は、常に定数（全加算器１個の遅延）である。
【００４１】
今、実現しようとしている演算は、（２）式のＡ＋Ｂ＋（−Ｒｅｆ）≧０の評価である。ＡとＢはそのままキャリー・セーブ方式加算器に加える。しかし、基準値Ｒｅｆは２の補数を取って符号を反転する必要がある。２の補数は全ビットを反転した後、１を加えることによって得られる。すなわち、反転Ｒｅｆを〜Ｒｅｆで表すものとすると、−Ｒｅｆ＝〜Ｒｅｆ＋１となる。
【００４２】
本発明のポイントの１つは、この基準値Ｒｅｆの２の補数を求める過程を３：２コンプレッサ段の前後で分けた点にある。通常の方法で２の補数を求めようとすると、＋１を行う段階で桁上げ伝搬が発生し、log ｎに比例した遅延時間が生じてしまう。
【００４３】
そこで、本発明では、（〜Ｒｅｆ）を３：２コンプレッサ段の前で行い、（＋１）を後の非負判定段で行う方法をとる。つまり、基準値Ｒｅｆが入力されるキャリー・セーブ方式加算器の入力端子にはＮＯＴゲート（インバータ）を付加する。後述するように、非負判定段で＋１を行うようにすると、遅延・ゲートが全く増加しない。３：２コンプレッサ段で行う演算は本質的に加算であり、＋１もまた加算である。したがって、演算の対称性・加算の交換則から、３：２コンプレッサ処理を行った後で＋１を行っても差し支えない。
【００４４】
３：２コンプレッサ段の構成を図２に示す。同図から明らかなように、３：２コンプレッサ段２０は、入力数値のビット幅がｎビットの場合、ｎ個の全加算器２１0 〜２１n-1 と、これら全加算器２１0 〜２１n-1 の各Ｃｉ入力端子に接続されたインバータ（ＮＯＴゲート）２２0 〜２２n-1 とから構成されている。そして、２つの入力Ａ0 〜Ａn-1 ，Ｂ0 〜Ｂn-1 の各ビットを全加算器２１0 〜２１n-1 の各Ａ，Ｂ入力、インバータ２２0 〜２２n-1 で反転された基準値Ｒｅｆ0 〜Ｒｅｆn-1 の各ビットを全加算器２１0 〜２１n-1 の各Ｃｉ入力とし、全加算器２１0 〜２１n-1 の各Ｃｏ出力およびＳ出力を２の出力Ｅ0 〜Ｅn-1 ，Ｄ0 〜Ｄn-1 とする。
【００４５】
次に、非負判定段について説明する。非負判定段の構成を図３に示す。非負判定段３０は、和Ｓｎを生成する（ｎ＋１）ビット幅加算器３１によって構成されている。この非負判定段３０では、３：２コンプレッサ段２０において得られたＤ，Ｅについて、Ｒｅｆの２の補数（＋１）を得るために（Ｄ＋２×Ｅ＋１）の演算処理を行い、その演算結果が非負か否かについて判定を行う。
【００４６】
ある加算結果が非負であるか否かを知るには、加算出力Ｓｎの符号ビット（ＭＳＢ）を参照すればよい。符号ビットが“０”ならば非負であり、“１”ならば負である。符号ビット以外の出力は求める必要がない。したがって、図３から明らかなように、和ＳｎのＭＳＢ生成に関わらない論理ゲートを削除した加算器３１が用いられている。
【００４７】
ここで、非負判定段３０で行われる計算の例を示す。
D = P 1 1 0 1 0
E = 0 1 1 0 0 Q
ならば、空欄“Ｐ”に符号拡張するように符号を補い、空欄“Ｑ”に１を補って（２の補数を得る“＋１”に相当）、

となり、結果は非負（ＭＳＢ＝０）である。
【００４８】
先述した例では、空欄“Ｑ”には０を補った。ここでは、Ｒｅｆの２の補数のための“＋１”を実現するため、空欄“Ｑ”に１を補う。これは、図３中の（ｎ＋１）ビット幅加算器３１の入力端子Ａ０に１を入力することで実現できる。このように、Ｒｅｆの２の補数を得るために必要な“＋１”が、ハードウェアおよび遅延時間を増加させることなく実現できる。
【００４９】
以下、３入力比較器の構成の具体例について説明する。図４は、３入力比較器の第１具体例を示すブロック図である。この第１具体例に係る３入力比較器は、図２の３：２コンプレッサ段２０と図３の非負判定段３０とからなり、全加算器２１0 〜２１n-2 の各Ｓ端子が（ｎ＋１）ビット幅加算器３１のＢ0 〜Ｂn-2 端子にビット対応で接続されかつ全加算器２１n-1 のＳ端子が（ｎ＋１）ビット幅加算器３１のＢn-1 端子およびＢn 端子にそれぞれ接続されるとともに、全加算器２１0 〜２１n-1 の各Ｃｏ端子が（ｎ＋１）ビット幅加算器３１の１ビット上位のＡ1 〜Ａn 端子にそれぞれ接続されかつ最下位ビットのＡ0 端子に論理“１”が与えられ、（ｎ＋１）ビット幅加算器３１のＳｎ出力を比較結果出力として導出する構成となっている。
【００５０】
上記構成の第１具体例に係る３入力比較器では、不等式“Ａ＋Ｂ≧Ｒｅｆ”又は“Ａ＋Ｂ＜Ｒｅｆ”（Ａ，Ｂ，Ｒｅｆは符号付き２進数）の評価が行われる。この３入力比較器の比較結果出力は以下のように解釈できる。すなわち、比較結果出力が“０”の場合は、“Ａ＋Ｂ＋（−Ｒｅｆ）≧０”、即ち“Ａ＋Ｂ≧Ｒｅｆ”である。比較結果出力が“１”の場合は、“Ａ＋Ｂ＋（−Ｒｅｆ）＜０”、即ち“Ａ＋Ｂ＜Ｒｅｆ”である。
【００５１】
図５は、３入力比較器の第２具体例を示すブロック図である。この第２具体例に係る３入力比較器は、第１具体例の場合と同様に、図２の３：２コンプレッサ段２０と図３の非負判定段３０とからなり、かつ全加算器２１0 〜２１n-1 の各Ｓ，Ｃｏ端子と（ｎ＋１）ビット幅加算器３１のＡ0 〜Ａn ，Ｂ0 〜Ｂn 端子の接続関係も第１具体例の場合と同じである。異なるのは、（ｎ＋１）ビット幅加算器３１の最下位ビットのＡ0 端子に論理“０”が与えられている点である。
【００５２】
上記構成の第２具体例に係る３入力比較器では、不等式“Ａ＋Ｂ＞Ｒｅｆ”又は“Ａ＋Ｂ≦Ｒｅｆ”（Ａ，Ｂ，Ｒｅｆは符号付き２進数）の評価が行われる。この３入力比較器の比較結果出力は以下のように解釈できる。ここで、自明な次の命題を利用する。
【００５３】
「Ａ＋Ｂ＞Ｒｅｆを満たす整数Ａ，Ｂ，Ｒｅｆが存在するとき、必ず、Ａ＋Ｂ−１≧Ｒｅｆである。」
すなわち、不等式
Ａ＋Ｂ＞Ｒｅｆ …（３）
を評価することは、不等式
Ａ＋Ｂ−１≧Ｒｅｆ …（４）
を評価することと等しい。したがって、不等式
Ａ＋Ｂ＋（−Ｒｅｆ）−１≧０ …（５）
を評価することを考えれば良い。
【００５４】
（５）式において、左辺の“−１”は実に単純な方法で実現できる。評価する不等式を以下のように変形する。
Ａ＋Ｂ＋（−Ｒｅｆ）＝（Ｄ＋２×Ｅ＋１）
より、
Ａ＋Ｂ＋（−Ｒｅｆ）−１≧０
Ｄ＋２×Ｅ≧０ …（６）
【００５５】
第１具体例では、“Ｄ＋２×Ｅ＋１”という演算を非負判定段３０で行っている。すなわち、図４において、（ｎ＋１）ビット幅加算器３１の最下位ビットのＡ０端子に論理“１”を与えることで、“＋１”を実現している。これに対し、第２具体例では、（ｎ＋１）ビット幅加算器３１の最下位ビットのＡ0 端子に論理“０”を与えることで、“Ｄ＋２×Ｅ”という演算を非負判定段３０で行うようにしている。
【００５６】
図６は、３入力比較器の第３具体例を示すブロック図である。この第３具体例に係る３入力比較器は、図２の３：２コンプレッサ段２０、図３の非負判定段３０およびＥＸ‐ＯＲゲート４１からなるとともに、全加算器２１0 〜２１n-1 の各Ｓ，Ｃｏ端子と（ｎ＋１）ビット幅加算器３１のＡ0 〜Ａn ，Ｂ0 〜Ｂn 端子とが第１，第２具体例の場合と同じ接続関係にあり、加えて、（ｎ＋１）ビット幅加算器３１の最下位ビットのＡ0 端子に機能選択入力Ｓ０を与えるとともに、（ｎ＋１）ビット幅加算器３１のＳｎ出力と機能選択入力Ｓ１をＥＸ‐ＯＲゲート４１の２入力とし、このＥＸ‐ＯＲゲート４１の出力を比較結果出力として導出する構成となっている。
【００５７】
上記構成の第３具体例に係る３入力比較器は、機能選択入力Ｓ１，Ｓ０によって評価する不等式を選択することが可能な符号付き機能選択型３入力比較器である。すなわち、機能選択入力Ｓ０は、（ｎ＋１）ビット幅加算器３１のＡ０入力であって、“Ａ＋Ｂ−１≧Ｒｅｆ”か“Ａ＋Ｂ−１＞Ｒｅｆ”を選択するためのものである。また、機能選択入力Ｓ１は、各不等式の評価結果が“真”のときには“１”、“偽”のときには“０”と表現されるように、非負判定段３０の出力を適宜反転／非反転するためのものである。
【００５８】
機能選択入力Ｓ１，Ｓ０と評価する不等式の対応関係を表２に示す。
【表２】

【００５９】
ところで、上述した第１〜第３具体例では、Ａ，Ｂ，Ｒｅｆが２の補数表示された符号付き２進数であると仮定し、３入力比較器を構成した場合を例にとって示した。この第１〜第３具体例に係る３入力比較器に対して符号無し２進数を入力した場合、その結果は正しいものとはならない。
【００６０】
例えば、Ａ＝１１１１，Ｂ＝１１１１，Ｒｅｆ＝１１１１のとき、これを符号付き２進数と受け取れば、Ａ＝−１，Ｂ＝−１，Ｒｅｆ＝−１であり、Ａ＋Ｂ＜Ｒｅｆが成立する。一方、符号無し２進数と見た場合、Ａ＝１５，Ｂ＝１５，Ｒｅｆ＝１５であり、Ａ＋Ｂ＜Ｒｅｆではない。
【００６１】
一般に、符号無し２進数は、そのＭＳＢ側に“０”を拡張（符号拡張）することにより、符号付き２進数の処理系で正の数値として正しく扱われる。符号拡張を行ったＡ，Ｂ，Ｒｅｆについて、符号付き２進数の３入力比較の行程を適応した例を以下に示す。

【００６２】

結果は＋１５であり、非負である。
【００６３】
ここに示した過程をそのままハードウェアで実現すると、符号拡張を行ったため、（ｎ＋２）ビット幅加算器が必要となる。これは符号付きの場合に比べて１ビット分多い。しかし、最上位ビットが明示的に定まっていることを利用して、（ｎ＋１）ビット幅加算器を用いることが出来る。具体的には、以下に示すように、Ａ，Ｂ，Ｒｅｆがどんな値であっても、Ｄ，Ｅの最上位ビットはＤが１で、Ｅが０であることを利用する。
【００６４】

【００６５】

【００６６】
ここで、Ｆの符号ビットＳは、以下のようにして求められる。
Ｓ＝０（＋）１（＋）（“Ｄ′の第４〜第０ビット＋Ｅ′の第４〜第０ビット”の桁上げ）
＝〜（“Ｄ′の第４〜第０ビット＋Ｅ′の第４〜第０ビット”の桁上げ）
すなわち、結果Ｆの符号を求めるには、“Ｄ′の第４〜第０ビットとＥ′の第４〜第０ビット”を加算したとき、桁上げ出力が有るか否かを求めれば良い。桁上げが１なら非負であり、０なら負であると解釈できる。ここに、（＋）とは、排他的論理和を示す演算記号である。
【００６７】
したがって、符号無し２進数の場合であっても、（ｎ＋１）ビット幅加算器で不等式の評価を行うことが出来る。この例でＤ′の第４ビットが常に“１”であることに注意して、（ｎ＋１）ビット幅加算器の入力Ｂn には常に“１”を入力する。そして、桁上げ出力Ｃｏｕｔ生成に関わらない論理ゲートを全て除去して単純化した加算器を用いる。符号付きの場合は、和のＭＳＢ生成に関わらない論理ゲートを全て除去して単純化した加算器を用いていた。
【００６８】
また、符号無しの場合の非負判定段が符号付きの場合と同じ（ｎ＋１）ビット幅加算器であるから、Ｄ，Ｅ生成の３：２コンプレッサ段も符号付きの場合と全く同じものを用いて良い。以下、符号無し入力に対応した３入力比較器の具体例について説明する。
【００６９】
図７は、３入力比較器の第４具体例を示すブロック図である。この第４具体例に係る３入力比較器は、図２の３：２コンプレッサ段２０と図３の非負判定段３０とからなる。但し、第１〜第３具体例では、非負判定段３０として、和Ｓｎを生成する（ｎ＋１）ビット幅加算器３１が用いられたが、本例では、桁上げ出力Ｃｏｕｔを生成する（ｎ＋１）ビット幅加算器３２が用いられる。この場合、Ｃｏｕｔ生成に関わらない論理ゲートを削除することにより、回路構成を単純化できる。
【００７０】
そして、全加算器２１0 〜２１n-1 の各Ｓ端子が（ｎ＋１）ビット幅加算器３２のＢ０〜Ｂｎ−１端子にビット対応で接続されるとともに、全加算器２１0 〜２１n-1 の各Ｃｏ端子が（ｎ＋１）ビット幅加算器３２の１ビット上位のＡ1 〜Ａn 端子にそれぞれ接続される。また、（ｎ＋１）ビット幅加算器３２の最下位ビットのＡ0 端子および最上位ビットのＢn 端子にそれぞれ論理“１”が与えられ、Ｃｏｕｔ出力を比較結果出力として導出する構成となっている。
【００７１】
上記構成の第４具体例に係る３入力比較器では、不等式“Ａ＋Ｂ≧Ｒｅｆ”又は“Ａ＋Ｂ＜Ｒｅｆ”（Ａ，Ｂ，Ｒｅｆは符号無し２進数）の評価が行われる。この３入力比較器の比較結果出力は以下のように解釈できる。すなわち、比較結果出力が“１”の場合は、“Ａ＋Ｂ＋（−Ｒｅｆ）≧０”、即ち“Ａ＋Ｂ≧Ｒｅｆ”である。比較結果出力が“０”の場合は、“Ａ＋Ｂ＋（−Ｒｅｆ）＜０”、即ち“Ａ＋Ｂ＜Ｒｅｆ”である。
【００７２】
図８は、３入力比較器の第５具体例を示すブロック図である。この第５具体例に係る３入力比較器の構成要素および接続関係は、基本的には、第４具体例の場合と同じである。異なるのは、第４具体例の場合には、（ｎ＋１）ビット幅加算器３２の最下位ビットのＡ0 端子および最上位ビットのＢn 端子にそれぞれ論理“１”が与えられていたのに対し、本例では、（ｎ＋１）ビット幅加算器３２の最下位ビットのＡ０端子に論理“１”が与えられ、最上位ビットのＢn 端子に論理“１”が与えられている点である。
【００７３】
上記構成の第５具体例に係る３入力比較器では、不等式“Ａ＋Ｂ＞Ｒｅｆ”又は“Ａ＋Ｂ≦Ｒｅｆ”（Ａ，Ｂ，Ｒｅｆは符号無し２進数）の評価が行われる。この３入力比較器の比較結果出力については、第２具体例の場合と同様に解釈することができる。
【００７４】
図９は、３入力比較器の第６具体例を示すブロック図である。この第６具体例に係る３入力比較器は、３：２コンプレッサ段２０、（ｎ＋１）ビット幅加算器３２からなる非負判定段３０およびＥＸ‐ＯＲゲート４１からなるとともに、全加算器２１0 〜２１n-1 の各Ｓ，Ｃｏ端子と（ｎ＋１）ビット幅加算器３２のＡ0 〜Ａn ，Ｂ0 〜Ｂn 端子とが第４，第５具体例の場合と同じ接続関係にあり、さらに（ｎ＋１）ビット幅加算器３２の最上位ビットのＢn 端子に論理“１”が与えられおり、加えて、（ｎ＋１）ビット幅加算器３２の最下位ビットのＡ0 端子に機能選択入力Ｓ０を与えるとともに、（ｎ＋１）ビット幅加算器３２のＳｎ出力と機能選択入力Ｓ１をＥＸ‐ＯＲゲート４１の２入力とし、このＥＸ‐ＯＲゲート４１の出力を比較結果出力として導出する構成となっている。
【００７５】
上記構成の第６具体例に係る３入力比較器は、機能選択入力Ｓ１，Ｓ０によって評価する不等式を選択することが可能な符号無し機能選択型３入力比較器である。すなわち、機能選択入力Ｓ０は、（ｎ＋１）ビット幅加算器３２のＡ0 入力であって、“Ａ＋Ｂ−１≧Ｒｅｆ”か“Ａ＋Ｂ−１＞Ｒｅｆ”を選択するためのものである。また、機能選択入力Ｓ１は、各不等式の評価結果が“真”のときには“１”、“偽”のときには“０”と表現されるように、非負判定段３０の出力を適宜反転／非反転するためのものである。機能選択入力Ｓ１，Ｓ０と評価する不等式の対応関係は、第３具体例の場合と同じである（表２を参照）。
【００７６】
図１０は、３入力比較器の第７具体例を示すブロック図である。この第７具体例に係る３入力比較器は、３：２コンプレッサ段２０、非負判定段３０、ＥＸ‐ＯＲゲート４１、セレクタ４２およびＯＲゲート４３から構成されている。３：２コンプレッサ段２０としては、図２に示す構成のものが用いられる。３：２コンプレッサ段２０としては、Ｃｏｕｔ，Ｓｎの両方を生成する（ｎ＋１）ビット幅加算器３３が用いられる。この場合、Ｃｏｕｔ，Ｓｎ生成に関わらない論理ゲートを削除することにより、回路構成の単純化が図れる。
【００７７】
また、３：２コンプレッサ段２０の全加算器２１0 〜２１n-1 の各Ｓ，Ｃｏ端子と（ｎ＋１）ビット幅加算器３３のＡ0 〜Ａn ，Ｂ0 〜Ｂn 端子とが第４〜第６具体例の場合と同じ接続関係にある。そして、（ｎ＋１）ビット幅加算器３３の最下位ビットのＡ0 端子に機能選択入力Ｓ０を与える。また、３：２コンプレッサ段２０の最上位の全加算器２１n-1 のＳ出力と機能選択入力Ｓ２がＯＲゲート４３の２入力となり、ＯＲゲート４３の出力が（ｎ＋１）ビット幅加算器３３の最上位ビットのＢn 端子に与えられる。
【００７８】
セレクタ４２は、（ｎ＋１）ビット幅加算器３３のＣｏｕｔ出力およびＳｎ出力を２入力とし、機能選択入力Ｓ２の論理状態に応じて２入力のいずれかを選択して出力する。この機能選択入力Ｓ２は、論理“０”のときＡ，Ｂ，Ｒｅｆが符号付き２進数、論理“１”のときＡ，Ｂ，Ｒｅｆが符号無し２進数である。したがって、セレクタ４２は、機能選択入力Ｓ２が論理“０”のときＳｎ出力を、機能選択入力Ｓ２が論理“１”のときＣｏｕｔ出力を選択する。そして、セレクタ４２の選択出力と機能選択入力Ｓ１がＥＸ‐ＯＲゲート４１の２入力となり、このＥＸ‐ＯＲゲート４１の出力が比較結果出力として導出される。
【００７９】
上記構成の第７具体例に係る３入力比較器は、第３具体例に係る符号付き機能選択型３入力比較器と、第６具体例に係る符号無し機能選択型３入力比較器とを一体化し、符号付き／符号無しおよび評価する不等式をそれぞれ動的に設定可能な全機能統合型３入力比較器である。
【００８０】
すなわち、機能選択入力Ｓ０は、（ｎ＋１）ビット幅加算器３３のＡ0 入力であって、“Ａ＋Ｂ−１≧Ｒｅｆ”か“Ａ＋Ｂ−１＞Ｒｅｆ”を選択する。また、機能選択入力Ｓ１は、各不等式の評価結果が“真”のときには“１”、“偽”のときには“０”と表現されるように、非負判定段３０の出力を適宜反転／非反転する（表２を参照）。さらに、機能選択入力Ｓ２は、符号付き／符号無しの設定を行う。
【００８１】
以上説明した第１〜第７具体例に係る３入力比較器において、各非負判定段で用いられる（ｎ＋１）ビット幅加算器のゲート数は、従来装置で用いられる比較器とほぼ等しい。一方、３：２コンプレッサ段で用いられるキャリー・セーブ方式加算器の分だけ若干ゲート数が増加する。しかし、飽和演算装置全体のゲート数に関して支配的なのは比較器の方ではなく、（Ａ＋Ｂ）を行う加算器である。したがって、本発明を適用することで増加するゲート数はあまり問題とはならない。
【００８２】
図１１は、本発明の第２実施形態を示すブロック図であり、基準値Ｒｅｆが２つの場合、即ち上限値および下限値の双方を指定可能な飽和加算装置に適用した場合を示している。
【００８３】
第２実施形態に係る飽和加算装置は、ｎビットの２つの入力Ａ，Ｂの加算を行う加算器５１と、この加算器５１に対して並列に設けられ、２つの入力Ａ，Ｂのｎビットの加算結果がｎビットの上限基準値Ｒｅｆ(upper) で定められる範囲を逸脱しているか否かを判定する３入力比較器５２と、加算器５１に対して並列に設けられ、２つの入力Ａ，Ｂの加算結果がｎビットの下限基準値Ｒｅｆ(lower) で定められる範囲を逸脱しているか否かを判定する３入力比較器５３と、これら３入力比較器５２，５３の各１ビット（計２ビット）の比較結果に基づいて加算器５１の加算結果、ｎビットの上限飽和値Ｓａｔ(upper) およびｎビットの下限飽和値Ｓａｔ(lower) のいずれか１つを選択して出力するセレクタ５４とから構成されている。
【００８４】
上記構成の第２実施形態に係る飽和加算装置において、２つの基準値Ｒｅｆ(upper),Ｒｅｆ(lower) および２つの飽和値Ｓａｔ(upper),Ｓａｔ(lower) は、外部にて任意に設定可能である。２つの３入力比較器５２，５３としては、先述した第１具体例〜第７具体例に係る３入力比較器の中から、評価したい不等式や選択できる機能に応じて適切なものを選定して用いる。また、３入力比較器５２，５３の出力の意味を良く判断した上でセレクタ５４との接続を行う。ここで用いるセレクタ５４は３入力のものである。
【００８５】
ここで、入力数値のビット幅がｎビットの場合、加算器５１および２つの３入力比較器５２，５３の遅延時間はどちらもlog ｎに比例し、両者の遅延時間はほぼ同等である。実際には、先述したように、３入力比較器５２，５３のハードウェアの単純さから、加算器５１に比べて３入力比較器５２，５３の遅延時間が若干短い。したがって、加算器５１に対して２つの３入力比較器５２，５３を並列に配置し、加算と比較を並列処理することにより、総遅延時間は第１実施形態の場合と同等となる。すなわち、高速動作が可能となる。
【００８６】
ところで、以下の４つの命題は自明である。
▲１▼Ａ−Ｂ＞Ｒｅｆを満たす整数Ａ，Ｂ，Ｒｅｆがあるとき必ず、Ｒｅｆ＋Ｂ＜Ａである。
▲２▼Ａ−Ｂ≧Ｒｅｆを満たす整数Ａ，Ｂ，Ｒｅｆがあるとき必ず、Ｒｅｆ＋Ｂ≦Ａである。
▲３▼Ａ−Ｂ≦Ｒｅｆを満たす整数Ａ，Ｂ，Ｒｅｆがあるとき必ず、Ｒｅｆ＋Ｂ≧Ａである。
▲４▼Ａ−Ｂ＜Ｒｅｆを満たす整数Ａ，Ｂ，Ｒｅｆがあるとき必ず、Ｒｅｆ＋Ｂ＞Ａである。
【００８７】
以上の命題から、減算（Ａ−Ｂ）を含む不等式の評価は全て、加算（Ｒｅｆ＋Ｂ）を含む不等式の評価に置き換えられることが分かる。すなわち、第１実施形態に係る飽和加算装置における３入力加算器１２（図１を参照）に対し、入力Ａと基準値Ｒｅｆを置換して入力することによって、何らハードウェアに変更を加えることなく、減算（Ａ−Ｂ）を含む不等式の評価をすることが出来る。
【００８８】
図１２は、本発明の第３実施形態を示すブロック図であり、基準値Ｒｅｆが１つの場合、即ち上限／下限値のいずれかを指定可能な飽和減算装置に適用した場合を示している。
【００８９】
第３実施形態に係る飽和減算装置は、ｎビットの２つの入力Ａ，Ｂの減算を行う減算器６１と、この減算器６１に対して並列に設けられ、２つの入力Ａ，Ｂの減算結果がｎビットの基準値Ｒｅｆで定められる範囲を逸脱しているか否かを判定する３入力比較器６２と、この３入力比較器６２の１ビットの比較結果に基づいて減算器６１の減算結果とｎビットの飽和値Ｓａｔのいずれか一方を選択して出力するセレクタ６３とから構成されている。
【００９０】
上記構成の第３実施形態に係る飽和減算装置において、基準値Ｒｅｆおよび飽和値Ｓａｔは、外部にて任意に設定可能である。ここで、本実施形態に係る飽和減算装置と第１実施形態に係る飽和加算装置とを比べると、３入力比較器６２に対する入力Ａ，Ｒｅｆが相互に置き換わっている。３入力比較器６２としては、先述した第１具体例〜第７具体例に係る３入力比較器の中から、評価したい不等式や選択できる機能に応じて適切なものを選定して用いる。但し、その選定の際には注意が必要である。
【００９１】
例えば、“Ａ−Ｂ＜ＲＥＦ”という不等式を評価したい場合、３入力比較器６２としては、“ａ＋ｂ＞ｒｅｆ”を評価するものを用いる。ＲＥＦ，ｒｅｆに対する不等号の向きが反対なので間違えやすい。これは、“ａ＋ｂ＞ｒｅｆ”に対しａ＝ＲＥＦ，ｂ＝Ｂ，ｒｅｆ＝Ａと入力し、“ＲＥＦ＋Ｂ＞Ａ”、即ち“Ａ−Ｂ＜ＲＥＦ”と評価するからである。
【００９２】
したがって、“Ａ−Ｂ＜ＲＥＦ”を評価するときは、“ａ＋ｂ＞ｒｅｆ”を評価する３入力比較器を、“Ａ−Ｂ≦ＲＥＦ”を評価するときは、“ａ＋ｂ≧ｒｅｆ”を評価する３入力比較器を、“Ａ−Ｂ≧ＲＥＦ”を評価するときは、“ａ＋ｂ≦ｒｅｆ”を評価する３入力比較器を、“Ａ−Ｂ＞ＲＥＦ”を評価するときは、“ａ＋ｂ＜ｒｅｆ”を評価する３入力比較器をそれぞれ用いるようにする。
【００９３】
このように、第３実施形態に係る飽和減算装置においては、図１の第１実施形態に係る飽和加算装置に対して、３入力比較器６２に対する入力結線を変更しただけであるから、総遅延時間は図１の飽和加算装置のものと同等であり、高速動作が可能である。
【００９４】
図１３は、本発明の第４実施形態を示すブロック図であり、第２実施形態に係る飽和減算装置の場合のように、基準値Ｒｅｆが２つの場合、即ち上限値および下限値の双方を指定可能な飽和減算装置に適用した場合を示している。
【００９５】
第４実施形態に係る飽和減算装置は、ｎビットの２つの入力Ａ，Ｂの減算を行う減算器７１と、この減算器７１に対して並列に設けられ、２つの入力Ａ，Ｂの減算結果がｎビットの上限基準値Ｒｅｆ(upper) で定められる範囲を逸脱しているか否かを判定する３入力比較器７２と、減算器７１に対して並列に設けられ、２つの入力Ａ，Ｂのｎビットの減算結果がｎビットの下限基準値Ｒｅｆ(lower) で定められる範囲を逸脱しているか否かを判定する３入力比較器７３と、これら３入力比較器７２，７３の各１ビット（計２ビット）の比較結果に基づいて減算器７１の減算結果、ｎビットの上限飽和値Ｓａｔ(upper) およびｎビットの下限飽和値Ｓａｔ(lower) のいずれか１つを選択して出力するセレクタ７４とから構成されている。
【００９６】
上記構成の第４実施形態に係る飽和減算装置において、２つの基準値Ｒｅｆ(upper),Ｒｅｆ(lower) および２つの飽和値Ｓａｔ(upper),Ｓａｔ(lower) は、外部にて任意に設定可能である。ここで、本実施形態に係る飽和減算装置と第２実施形態に係る飽和加算装置とを比べると、３入力比較器７２，７３に対する入力ＡとＲｅｆ(upper),Ｒｅｆ(lower) が相互に置き換わっている。３入力比較器７２，７３としては、第３実施形態の場合と同様にして、先述した第１具体例〜第７具体例に係る３入力比較器の中から適切なものを選定して用いる。
【００９７】
ここまでは、飽和加算装置および飽和減算装置に適用した場合について説明したが、続いて、飽和乗算装置に適用した場合について説明する。
【００９８】
一般的な高速乗算器として、キャリー・セーブ方式加算器（３：２コンプレッサ）や４：２コンプレッサ、冗長２進加算器などを用いたものがある。これらの乗算器では、部分積を求める段階では桁上げ伝搬を抑制し、部分積加算を高速に行う。最終的に部分積は２つの２進数Ａ，Ｂで表現され、本当の積はＡ＋Ｂ（冗長２進では、Ａ−Ｂ）で求められる。これを最終段加算と言う。
【００９９】
乗算結果がある基準値を越えたか否かを判定することは、最終段加算で行う部分積和（Ａ＋Ｂ）（冗長２進なら、Ａ−Ｂ）が基準値を越えたか否かを判定することと等しい。したがって、最終段加算と並列に３入力比較器を設けることによって、飽和乗算装置を構成することが出来る。
【０１００】
図１４は、本発明の第５実施形態を示すブロック図であり、基準値Ｒｅｆが１つの場合、即ち上限／下限値のいずれかを指定可能な飽和乗算装置に適用した場合を示している。
【０１０１】
第５実施形態に係る飽和乗算装置は、ｎ／２ビットの２つの入力Ｘ，Ｙの部分積加算を行う部分積加算器８１と、この部分積加算器８１から供給されるｎビットの２つの入力Ａ，Ｂの最終段加算を行う最終段加算器８２と、この最終段加算器８２に対して並列に設けられ、２つの入力Ａ，Ｂの最終段加算結果がｎビットの基準値Ｒｅｆで定められる範囲を逸脱しているか否かを判定する３入力比較器８３と、この３入力比較器８３の１ビットの比較結果に基づいて最終段加算器８２の加算結果とｎビットの飽和値Ｓａｔのいずれか一方を選択して出力するセレクタ８４とから構成されている。
【０１０２】
上記構成の第５実施形態に係る飽和乗算装置において、基準値Ｒｅｆおよび飽和値Ｓａｔは、外部にて任意に設定可能である。また、部分積加算器８１の出力以降の構成は、図１に示す第１実施形態に係る飽和加算器装置と同じである。したがって、部分積加算器８１の出力以降における総遅延時間は図１の飽和加算装置のものと同等であるため、高速動作が可能である。
【０１０３】
なお、本実施形態においては、最終段で部分積和（Ａ＋Ｂ）をとる場合を例にとって説明したが、冗長２進のように（Ａ−Ｂ）を行う場合には、第３実施形態に係る飽和減算装置と同様な原理で３入力比較器を選定し、その入力Ａ，Ｒｅｆの接続関係を置換することによって実現出来る。
【０１０４】
また、第２実施形態に係る飽和加算装置や、第４実施形態に係る飽和減算装置の場合と同様に、最終段加算器８２に対して２つの３入力比較器を並列に設けることにより、上限値および下限値の双方を指定可能な飽和乗算装置を実現することが出来る。
【０１０５】
以上、飽和加算装置、飽和減算装置および飽和乗算装置に適用した場合について説明したが、これらに限定されるものではなく、第５実施形態に係る飽和乗算装置のように、最終的に加算あるいは減算を行う演算装置であれば全て、３入力比較器を用いて高速な飽和演算処理を行うことが出来る。すなわち、最終段の加算器あるいは減算器と並列に３入力比較器を設けることで、加算・減算と同時に不等式の評価が行われ、加算・減算の終了時点で、基準値を超えたか否かが判明する。この後、セレクタを適切に用いることにより、加算・減算値か飽和値（単数か複数）を選ぶ。
【０１０６】
こうすることで、任意基準値・任意飽和値を指定可能な飽和演算処理を追加することが出来る。なお、加算・減算・乗算を複合的に行う演算処理（多項式の演算）においては、キャリー・セーブ方式の加算器や冗長２進加算器を用いて桁上げ伝搬を抑制した演算が行われる。このとき必ず、最終結果は２つの２進数の和（あるいは差）で求められ、必ず最終段で桁上げ伝搬を伴う加算器・減算器が用いられる。
【０１０７】
以上説明した各実施形態に係る飽和演算装置は、一例として、ディスプレイ上の任意の位置に存在する矩形領域内に描画を行うような場合に用いて好適なものである。すなわち、ディスプレイ上の任意の位置に任意の大きさの矩形領域があり、その領域内に描画を行う場合に、任意基準値・任意飽和値の飽和演算が必要となる。
【０１０８】
画面座標の計算は一般的に加算・乗算あるいは多項式演算によって行われる。描画しようとする座標が領域を逸脱した場合、領域の境界値あるいは適当な飽和値に補正するか、または、別の例外処理の起動を行う必要がある。このような場合に、各実施形態に係る飽和演算装置を用いることによって、これらの処理を高速に実行することができる。
【０１０９】
一般的な信号処理においても、線形多項式の演算、即ち積和演算が頻繁に行われる。このとき飽和演算処理は必須である。ある信号処理アルゴリズムによっては、加算器の最大値（オーバーフロー）未満で飽和演算を行う場合がある。また、ある信号処理においては、線形多項式（積和演算）の値を分母に持つ分数の評価を行う場合がある。この場合、この多項式は０となることは許されない。以上のような加算器の最大値（オーバーフロー）以外を基準値とした飽和演算処理を行う場合に、各実施形態に係る飽和演算装置を用いることによって、高速に行うことができる。
【０１１０】
このように、加算器の最大値以外の値を基準値とする飽和演算処理の用途は多く、また常に高速性が要求される。各実施形態に係る飽和演算装置を用いることによって、これらの処理を高速化することが可能である。
【０１１１】
【発明の効果】
以上説明したように、本発明によれば、ｎビット幅の３つの２進数（Ａ，Ｂ，Ｒｅｆ）の総和をｎビット幅の２つの２進数に変換し、この２つの２進数に基づいてその総和の値が非負であるか否かを判定することで、２つの入力Ａ，Ｂの演算結果が所定の基準値Ｒｅｆで定められる範囲を逸脱しているか否かを迅速に判定できるので、飽和演算の高速処理に寄与できることになる。
【０１１２】
また、２つの入力の演算処理と、その演算結果が所定の基準値で定められる範囲を逸脱しているか否かの判定処理とを並行して行い、この判定結果に基づいて演算結果と所定の飽和値のいずれか一方を選択して出力することで、「演算／比較→選択」の２つの段階で飽和演算を行うことができるので、基準値・飽和値を任意に指定できるとともに、高速演算を実現できることになる。
【図面の簡単な説明】
【図１】本発明の第１実施形態を示すブロック図である。
【図２】３：２コンプレッサ段の構成を示すブロック図である。
【図３】非負判定段の構成を示すブロック図である。
【図４】３入力比較器の第１具体例を示すブロック図である。
【図５】３入力比較器の第２具体例を示すブロック図である。
【図６】３入力比較器の第３具体例を示すブロック図である。
【図７】３入力比較器の第４具体例を示すブロック図である。
【図８】３入力比較器の第５具体例を示すブロック図である。
【図９】３入力比較器の第６具体例を示すブロック図である。
【図１０】３入力比較器の第７具体例を示すブロック図である。
【図１１】本発明の第２実施形態を示すブロック図である。
【図１２】本発明の第３実施形態を示すブロック図である。
【図１３】本発明の第４実施形態を示すブロック図である。
【図１４】本発明の第５実施形態を示すブロック図である。
【図１５】従来例を示すブロック図である。
【符号の説明】
１１，５１，８２…加算器、１２，５２，５３，６２，７２，７３，８３…３入力比較器、１３，４２，５４，６３，７４，８４…セレクタ、２０…３：２コンプレッサ段、３０…非負判定段、３１…（ｎ＋１）ビット幅加算器、４１…ＥＸ‐ＯＲゲート、２１0 〜２１n-1 …全加算器、２２0 〜２２n-1 …インバータ[0001]
BACKGROUND OF THE INVENTION
  The present invention relates to a digital arithmetic device in a semiconductor integrated circuit, particularly a saturation arithmetic device.3 input comparator suitable for use inAbout.
[0002]
In this case, the saturation arithmetic unit outputs a calculation result value when a result value obtained by performing a certain calculation is within a range defined by a given reference value (hereinafter simply referred to as Ref). The arithmetic unit outputs a given saturation value (hereinafter simply abbreviated as Sat) when the range is exceeded. Examples of the saturation arithmetic unit include a saturation addition device, a saturation subtraction device, and a saturation multiplication device.
[0003]
[Prior art]
For example, a saturation adder, which is a kind of saturation arithmetic device, corrects the output to a positive maximum value when the addition result exceeds the maximum positive value, and outputs the maximum negative value when the result exceeds the negative maximum value. The value is corrected. In this general saturation adder, the reference value as to whether or not the value is exceeded is fixed to a positive maximum value and a negative maximum value, and an arbitrary value cannot be used as a reference value.
[0004]
By the way, the term “saturation adder” refers to a saturation operation due to overflow of addition. Addition overflow occurs when the result of addition exceeds the range that can be expressed by the number of output bits of the adder, and is expressed as an overflow flag. That is, the flag state is “1” if an overflow occurs and “0” otherwise.
[0005]
When the input / output numerical value is an unsigned binary number, the carry output of the adder means an overflow. However, when the input / output numerical value is a binary number with a sign in 2's complement representation, the carry output does not mean overflow. For example, an addition of 4 bits for input and 4 bits for output is taken as an example.
0111 + 0001 = carry output 0, numeric value 1000
In the case of no sign, it means 7 + 1, and the result means +8. The result is correct, the carry output is 0, not overflow. On the other hand, when there is a sign, it means 7 + 1, and the result means -8. The result is incorrect, the carry output is 0, but overflow.
[0006]
Also,
1001 + 1111 = carry output 1, numeric value 1000
In the case of no sign, it means 9 + 15 and the result is 8. The result is incorrect, the carry output is 1, and overflow. When there is a sign, it means −7 + (− 1), and the result means −8. The result is correct and the carry output is 1, but it is not overflow.
[0007]
As described above, the method of detecting overflow differs depending on whether the input / output numerical value is unsigned or signed. When signed, an overflow flag can be created by adding a simple circuit inside a normal adder. The carry output and overflow flag are output at the end of addition. Eventually, whether it is an overflow or not, it is determined simultaneously with the addition result.
[0008]
2 when the output of the saturation adder is n bits and the addition result value is unsigned.ⁿ2 for the case with a sign^n-1 Or-(2^n-1+1) Overflow occurs below. Saturation addition in the saturation adder is performed based on this overflow. For example, in the calculation of (0111 + 0001), if there is no sign, there is no overflow, so the addition result 1000 (8) is output. If there is a sign, it is overflow, so the saturation value 0111 (7) is output. In addition, in the case of calculation of (1001 + 1111), the saturation value 1111 (15) is output because there is an overflow when there is no sign. If there is a sign, it is not an overflow, so the addition result 1000 (-8) is output.
[0009]
Normally, the saturation value is a boundary value at which overflow occurs, that is, a positive maximum value or a negative maximum value. However, in the conventional saturation addition apparatus, it is impossible in principle to determine a case where the numerical value other than the positive maximum value or the negative maximum value is used as a reference value and the reference value is exceeded. This is because even if the addition result deviates from a reference value that is not the maximum value, overflow does not occur.
[0010]
By the way, when drawing in an arbitrary rectangular area on a display by a computer, saturation calculation of an arbitrary reference value and an arbitrary saturation value is frequently performed. For example, when a certain figure is drawn in a rectangular area on the display, it is necessary to process so as not to draw a portion that protrudes from the area. In the process of calculating the drawing coordinates at this time, it is always determined whether or not the X and Y coordinates are within the region, and if the region exceeds the region, an arithmetic processing for correcting the boundary value, that is, a saturation operation is performed. ing. In order to perform correction to such a boundary value no matter where the rectangular area is on the screen, a saturation adder capable of arbitrarily designating a reference value and a saturation value is required.
[0011]
Conventionally, as a saturation addition device that realizes saturation addition in which the reference value and saturation value can be arbitrarily specified, as shown in FIG. 15, an addition input A and an addition input B are added by an adder 101, and the addition After obtaining the result (sum) S, the comparator 102 compares the addition result S with the reference value Ref. Based on the comparison result, the selector 103 selects either the addition result S or the saturation value Sat. An output configuration is known.
[0012]
[Problems to be solved by the invention]
However, in the conventional saturation addition apparatus described above, it is necessary to go through three stages of “addition → comparison → selection” before a saturation addition result is obtained. Here, when the bit width of the input numerical value is n bits, the delay time of the high-speed adder and the high-speed comparator is proportional to log n, and the delay time of the selector 103 is a constant Cs regardless of the bit width n. Assuming that, the total delay time of the conventional saturation adder can be estimated as (Ka · 2 · log n + Cs; Ka is a proportional constant). That is, the conventional technique has a problem in that since the comparison process is performed after the addition process, the delay time increases and it is not suitable for high-speed calculation.
[0013]
The present invention has been made in view of the above problems, and an object of the present invention is to provide a three-input comparator capable of realizing high-speed computation in computation processing of saturation addition, saturation subtraction, or saturation multiplication. There is.
[0015]
[Means for Solving the Problems]
The three-input comparator according to the present invention receives three binary numbers (A, B, Ref) having an n-bit width as input, converts the sum into two binary numbers (Co, S) having an n-bit width, and outputs the result. Whether the sum of the three binary numbers (A, B, Ref) is non-negative based on the 3: 2 compressor stage and the two binary numbers (Co, S) output from the 3: 2 compressor stage And a non-negative determination stage for determining whether or not.
[0016]
  AndThe 3: 2 compressor stage inputs two binary numbers (A, B) as they are for each bit, and inputs 3 binary numbers (Ref) by taking the negation for each bit as an input and has an n-bit width of 3 When the three binary numbers (A, B, Ref) are signed binary numbers in 2's complement representation, the non-negative determination stage is the (i + 1) th output of the S output of the 3: 2 compressor stage. ) Digit and Co output i digit (n−2 ≧ i ≧ 0) are input (i + 1) digit, S output 0 digit and logic “0” are 0 digit input, and S The (n-1) th digit of the output and the (n-1) th digit of the Co output are input as the nth digit, and the nth digit Sn of the sum output is a determination output. The nth digit Sn of the sum output of the (n + 1) -bit width adder is used as a determination output, and the (n + 1) Bit wide adder is constituted only by logic gates relating to generation of the n-digit Sn of the sum output.
[0017]
  The 3: 2 compressor stage inputs two binary numbers (A, B) as they are for each bit, and inputs one binary number (Ref) by taking the negation of each bit as input. When the three binary numbers (A, B, Ref) are signed binary numbers represented by two's complement representation, the non-negative determination stage is the S output of the 3: 2 compressor stage. The (i + 1) digit and the Co output i digit (n-2 ≧ i ≧ 0) are used as the (i + 1) digit input, and the S output 0 digit and the first function selection input are used as the 0th digit input. , An (n + 1) -bit width adder having the (n-1) -th digit of the S output and the (n-1) -th digit of the Co output as the n-th digit input, and the (n + 1) -bit width adder It consists of an n-th digit Sn of the sum output and an EX-OR gate having the second function selection input as two inputs The output of the serial EX-OR gates and a determination output, the (n + 1) bit width adder is constituted only by logic gates relating to generation of the n-digit Sn of the sum output.
[0018]
  The 3: 2 compressor stage inputs two binary numbers (A, B) as they are for each bit, and inputs one binary number (Ref) by taking the negation of each bit as input. When the three binary numbers (A, B, Ref) are unsigned binary numbers, the non-negative determination stage is the (i + 1) th digit of the S output of the 3: 2 compressor stage. The Co output i digit (n−2 ≧ i ≧ 0) is the (i + 1) digit input, the S output 0 digit and logic “0” are the 0 digit input, and the Co output No. The (n-1) digit and logic “1” are used as the nth digit input, and the carry output Cout is used as the determination output. The (n + 1) bit width adder carries the carry output. Cout is used as a determination output, and the (n + 1) -bit width adder outputs the carry output. It is constituted only by logic gates relating to generation of the Cout.
[0019]
  The 3: 2 compressor stage inputs two binary numbers (A, B) as they are for each bit, and inputs one binary number (Ref) by taking the negation of each bit as input. When the three binary numbers (A, B, Ref) are unsigned binary numbers, the non-negative determination stage is the (i + 1) th digit of the S output of the 3: 2 compressor stage. The i-th digit (n−2 ≧ i ≧ 0) of the Co output is the (i + 1) th digit input, the 0th digit of the S output and the first function selection input are the 0th digit input, and the Co output The (n + 1) -bit width adder having the (n-1) -th digit and logic “1” as the n-th digit input, and the carry output Cout and the second function selection input of the (n + 1) -bit width adder are 2 It consists of an EX-OR gate as input, and the output of the EX-OR gate is determined and output. And the (n + 1) bit width adder is constituted only by logic gates relating to generation of the carry output Cout.
[0020]
  The 3: 2 compressor stage inputs two binary numbers (A, B) as they are for each bit, and inputs one binary number (Ref) by taking the negation of each bit as input. When the three binary numbers (A, B, Ref) are signed binary numbers with 2's complement representation or unsigned binary numbers, the non-negative determination stage is the first output of the S output. OR gate having (n-1) digit and third function selection input as two inputs, (i + 1) digit of S output of the 3: 2 compressor stage, and i digit of Co output (n-2 ≧ i ≧) 0) is the (i + 1) th digit input, the 0th digit of the S output and the first function selection input are the 0th digit input, the (n-1) th digit of the Co output and the output of the OR gate (N + 1) bit width adder with the nth digit input and the third function selection input A selector for selecting the carry output Cout of the (n + 1) -bit width adder when “1” is “1”, and negation of the n-th digit Sn of the sum output of the (n + 1) -bit width adder when “0”. , And an EX-OR gate having the second function selection input as two inputs, the output of the EX-OR gate as a determination output, and the (n + 1) bit width adder It is composed only of the logic output involved in the generation of the carry output Cout, the sum output, and the nth digit Sn.
[0021]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
[0022]
FIG. 1 is a block diagram showing a first embodiment of the present invention, and shows a case where one reference value Ref is applied, that is, a case where the present invention is applied to a saturation adder capable of designating either an upper limit / lower limit value.
[0023]
The saturation adder according to the first embodiment includes an adder 11 that adds two n-bit inputs A and B, and an adder 11 that is provided in parallel with the adder 11 and adds the two inputs A and B. Is determined to be out of the range defined by the n-bit reference value Ref, and the addition result of the adder 11 based on the 1-bit comparison result of the 3-input comparator 12 The selector 13 selects and outputs one of the n-bit saturation values Sat.
[0024]
In the saturation addition apparatus according to the first embodiment having the above-described configuration, the reference value Ref and the saturation value Sat can be arbitrarily set outside. Here, when the bit width of the input numerical value is n bits, the delay times of the adder 11 and the 3-input comparator 12 are both proportional to log n, and the delay times of both are substantially equal.
[0025]
Therefore, assuming that the delay time of the selector 13 is a constant Cs regardless of the bit width n by arranging the three-input comparator 12 in parallel with the adder 11 and processing the addition and the comparison in parallel, this embodiment The total delay time of the saturation adder according to the above becomes (Kb · log n + Cs; Kb is a proportional constant), which is about 2 compared with the total delay time of the conventional saturation adder (Ka · 2 · log n + Cs; Ka is a proportional constant) Double speed and high speed operation is possible. However, it is assumed that the proportionality constant Ka and the proportionality constant Kb are substantially the same, and the constant Cs is sufficiently smaller than the delay time of the adder 11.
[0026]
Here, the principle of the three-input comparator 11 will be described. Now, the inequality of the sum (= A + B) of the two inputs A and B and the reference value Ref
Sum ≧ Ref (1)
Consider the judgment. This inequality (1) is transformed into the following equation.
A + B ≧ Ref
A + B + (− Ref) ≧ 0 (2)
[0027]
As is clear from the equation (2), the evaluation of the inequality of the equation (1) is equivalent to the evaluation of whether or not the addition result of the three variables (A, B, -Ref) is non-negative. That is, comparing the addition result Sum (= A + B) with the reference value Ref is equivalent to examining the sign of the addition result of the three variables. The addition of three variables can be replaced with the addition of two variables at a constant stage (usually two stages of EX-OR gates) without depending on the bit width n by using a 3: 2 (3-input 2-output) compressor. I can do it.
[0028]
For the addition of two variables, a commonly used adder is used. However, what is necessary here is to know whether the calculation result is non-negative, and to obtain the sign bit (the most significant bit MSB of the sum). Since it is not necessary to obtain all the sums, logic gates that are not involved in the generation of the sign bit are removed, and a simplified adder is used. Because of the simplicity of the circuit, it is slightly faster than a normal adder. This makes it possible to cancel the delay that occurs in the 3: 2 compressor stage.
[0029]
If the adder for determining whether or not it is non-negative has the same speed as the adder for calculating Sum (= A + B), the evaluation result of inequality (2) and the addition result Sum can be obtained simultaneously. That is, it is possible to determine whether or not the reference value has been exceeded (evaluation of inequality (2)) and addition in parallel. Thereafter, by using a general selector, either the addition result or the saturation value is output based on the evaluation of the inequality (2). By doing so, it is possible to realize a high-speed saturation adder capable of designating an arbitrary reference value and an arbitrary saturation value.
[0030]
As described above, the saturation adder according to the present embodiment performs the determination process (evaluation of inequality (2)) on whether or not the reference value Ref has been exceeded and the addition process in parallel, whereby a conventional saturation adder is obtained. It is characterized in that the saturation calculation is performed at a higher speed. The main components are an adder 11 that adds two inputs A and B, a three-input comparator 12 that evaluates equation (2), and a selector 13, as is apparent from FIG. As the adder 11 and the selector 13, a general one that has been conventionally used may be used.
[0031]
The unique point of the present invention, and the core of the technology for realizing the high-speed saturation arithmetic unit is the three-input comparator 12 for evaluating the expression (2). As will be described later, the three-input comparator 12 basically includes two components: a “3: 2 compressor stage” and a “non-negative determination stage”.
[0032]
By the way, in the above description of the principle of the three-input comparator 12,
A + B ≧ Ref
The inequality is evaluated. However, the logic circuit that realizes this, as described later, by slightly changing a part of the circuit,
A + B> Ref
It can be remade as a three-input comparator that evaluates the inequality. For this inequality, a 3-input comparator for both signed and unsigned binary numbers can be easily created.
[0033]
Here, for the sake of simplicity, a configuration of a three-input comparator that performs inequality evaluation of A + B ≧ Ref in a signed binary number using two's complement notation will be described.
[0034]
First, the 3: 2 compressor stage will be described. The 3: 2 compressor stage adds three variables (A + B + C) to two binary numbers D and E (D + 2 × E) (“2 × E” means a bit shift and is essentially an addition) Has a function to replace. Specifically, the number of “1” in each bit position of the three input binary numbers is output.
[0035]
For example,

[0036]
As described above, the number of “1” in each digit of the inputs A, B, and C is represented by a binary number with the bit in each digit of E and D as a pair. In order to obtain the sum of (A + B + C) from D and E, addition is performed by shifting E to the left by one digit with respect to D (ie, D + 2 × E). For example,
D = P 0 1 0 1 0
E = 0 0 1 1 0 Q
Here, the sign is expanded to sign-extend to the blank “P”, and the blank “Q” is supplemented with 0,

This result is equal to (A + B + C) = 14 + 6 + 2 = 22.
[0037]
As an arithmetic unit for performing such 3: 2 compressor processing, a carry save type adder is generally known. The carry-save type adder is a one-bit full adder arranged in parallel for the required bit width. The individual full adders are not connected to each other and are completely independent.
[0038]
The truth table of the 1-bit full adder is as shown in Table 1 when the input numerical values A and B, carry input Ci, carry output Co, and sum Sum are used.
[Table 1]

[0039]
From this truth table, it is clear that the number of “1” in A, B, and Ci is expressed in binary with Co and Sum as a pair. Various logic configurations of full adders are known, but the delay is about two EX-OR gates. By using such a full adder, the addition of three variables (A + B + C) can be replaced with the addition of two variables (D + 2 × E), that is, 3: 2 compressor processing can be performed.
[0040]
The delay of the 3: 2 compressor stage is equal to the delay of one full adder and does not depend on the bit width n of the input numbers A, B, C. This is because the full adders corresponding to the bit width of the input numerical value are not connected to each other and each full adder operates completely independently. Therefore, the delay of the 3: 2 compressor stage is always a constant (the delay of one full adder).
[0041]
The operation to be realized now is an evaluation of A + B + (− Ref) ≧ 0 in the equation (2). A and B are added as they are to the carry-save type adder. However, it is necessary to invert the sign of the reference value Ref by taking 2's complement. The two's complement is obtained by inverting all bits and adding one. That is, if the inversion Ref is represented by ~ Ref, -Ref = ~ Ref + 1.
[0042]
One of the points of the present invention is that the process of obtaining the 2's complement of the reference value Ref is divided before and after the 3: 2 compressor stage. If an attempt is made to obtain 2's complement by a normal method, carry propagation occurs at the stage of performing +1, and a delay time proportional to log n occurs.
[0043]
Therefore, the present invention adopts a method in which (˜Ref) is performed before the 3: 2 compressor stage and (+1) is performed in the subsequent non-negative determination stage. That is, a NOT gate (inverter) is added to the input terminal of the carry / save adder to which the reference value Ref is input. As will be described later, if +1 is performed in the non-negative determination stage, the delay / gate does not increase at all. The operation performed in the 3: 2 compressor stage is essentially an addition, and +1 is also an addition. Therefore, +1 may be performed after performing the 3: 2 compressor processing due to the symmetry of the operation and the exchange rule of addition.
[0044]
The configuration of the 3: 2 compressor stage is shown in FIG. As can be seen from the figure, the 3: 2 compressor stage 20 includes n full adders 210 to 21n-1 and these full adders 210 to 21n-1 when the bit width of the input numerical value is n bits. Inverters (NOT gates) 220 to 22n-1 connected to each Ci input terminal. The reference values Ref0 to Refn obtained by inverting the bits of the two inputs A0 to An-1 and B0 to Bn-1 by the A and B inputs of the full adders 210 to 21n-1 and the inverters 220 to 22n-1, respectively. -1 bits are used as Ci inputs of full adders 210 to 21n-1, and Co outputs and S outputs of full adders 210 to 21n-1 are used as two outputs E0 to En-1, D0 to Dn-1. And
[0045]
Next, the non-negative determination stage will be described. The configuration of the non-negative determination stage is shown in FIG. The non-negative determination stage 30 includes an (n + 1) -bit width adder 31 that generates a sum Sn. In this non-negative determination stage 30, a calculation process of (D + 2 × E + 1) is performed on D and E obtained in the 3: 2 compressor stage 20 in order to obtain 2's complement (+1) of Ref, and the calculation result is non-negative. It is determined whether or not.
[0046]
To know whether a certain addition result is non-negative, the sign bit (MSB) of the addition output Sn may be referred to. If the sign bit is “0”, it is non-negative, and if it is “1”, it is negative. There is no need to obtain an output other than the sign bit. Therefore, as is apparent from FIG. 3, the adder 31 is used in which the logic gates not related to the MSB generation of the sum Sn are deleted.
[0047]
Here, an example of calculation performed in the non-negative determination stage 30 is shown.
      D = P 1 1 0 1 0
E = 0 1 1 0 0 Q
Then, the sign is expanded to sign-extend to the blank “P”, the blank “Q” is supplemented with 1 (corresponding to “+1” to obtain 2's complement),

And the result is non-negative (MSB = 0).
[0048]
In the above-described example, 0 is filled in the blank “Q”. Here, in order to realize “+1” for 2's complement of Ref, 1 is added to the blank “Q”. This can be realized by inputting 1 to the input terminal A0 of the (n + 1) bit width adder 31 in FIG. In this way, the “+1” necessary to obtain the 2's complement of Ref can be realized without increasing hardware and delay time.
[0049]
A specific example of the configuration of the three-input comparator will be described below. FIG. 4 is a block diagram showing a first specific example of a three-input comparator. The 3-input comparator according to the first specific example includes the 3: 2 compressor stage 20 in FIG. 2 and the non-negative determination stage 30 in FIG. 3, and each S terminal of the full adders 210 to 21n-2 is (n + 1). The B0 to Bn-2 terminals of the bit width adder 31 are connected in a bit-corresponding manner, and the S terminal of the full adder 21n-1 is connected to the Bn-1 and Bn terminals of the (n + 1) bit width adder 31, respectively. At the same time, the Co terminals of the full adders 210 to 21n-1 are respectively connected to the upper A1 to An terminals of the (n + 1) bit width adder 31 and the logic "1" is given to the A0 terminal of the least significant bit. Thus, the Sn output of the (n + 1) -bit width adder 31 is derived as a comparison result output.
[0050]
The three-input comparator according to the first specific example having the above configuration evaluates the inequality “A + B ≧ Ref” or “A + B <Ref” (A, B, and Ref are signed binary numbers). The comparison result output of this three-input comparator can be interpreted as follows. That is, when the comparison result output is “0”, “A + B + (− Ref) ≧ 0”, that is, “A + B ≧ Ref”. When the comparison result output is “1”, “A + B + (− Ref) <0”, that is, “A + B <Ref”.
[0051]
FIG. 5 is a block diagram showing a second specific example of the three-input comparator. As in the case of the first specific example, the three-input comparator according to the second specific example includes the 3: 2 compressor stage 20 of FIG. 2 and the non-negative determination stage 30 of FIG. The connection relationship between the Sn and Co terminals of 21n-1 and the A0 to An and B0 to Bn terminals of the (n + 1) bit width adder 31 is the same as in the first specific example. The difference is that a logic “0” is given to the A 0 terminal of the least significant bit of the (n + 1) -bit width adder 31.
[0052]
In the three-input comparator according to the second specific example having the above-described configuration, the inequality “A + B> Ref” or “A + B ≦ Ref” (A, B, and Ref are signed binary numbers) is evaluated. The comparison result output of this three-input comparator can be interpreted as follows. Here, we use the following obvious proposition.
[0053]
“When there are integers A, B, and Ref that satisfy A + B> Ref, A + B−1 ≧ Ref always holds.”
That is, the inequality
A + B> Ref (3)
Is an inequality
A + B-1 ≧ Ref (4)
Is equivalent to evaluating Therefore, the inequality
A + B + (− Ref) −1 ≧ 0 (5)
You should think about evaluating.
[0054]
In the formula (5), “−1” on the left side can be realized by a very simple method. The inequality to be evaluated is transformed as follows.
A + B + (− Ref) = (D + 2 × E + 1)
Than,
A + B + (− Ref) −1 ≧ 0
D + 2 × E ≧ 0 (6)
[0055]
In the first specific example, the operation “D + 2 × E + 1” is performed in the non-negative determination stage 30. That is, in FIG. 4, “+1” is realized by applying a logic “1” to the A0 terminal of the least significant bit of the (n + 1) -bit width adder 31. On the other hand, in the second specific example, a logic “0” is given to the A 0 terminal of the least significant bit of the (n + 1) bit width adder 31 so that the operation “D + 2 × E” is performed in the non-negative determination stage 30. I have to.
[0056]
FIG. 6 is a block diagram showing a third specific example of the three-input comparator. The three-input comparator according to the third specific example includes the 3: 2 compressor stage 20 of FIG. 2, the non-negative determination stage 30 of FIG. 3, and the EX-OR gate 41, and each of the full adders 210 to 21n-1. The S, Co terminals and the A0 to An and B0 to Bn terminals of the (n + 1) bit width adder 31 have the same connection relationship as in the first and second specific examples, and in addition, an (n + 1) bit width adder The function selection input S0 is given to the A0 terminal of the least significant bit 31. The Sn output of the (n + 1) bit width adder 31 and the function selection input S1 are used as two inputs of the EX-OR gate 41, and this EX-OR gate 41 Is derived as a comparison result output.
[0057]
The three-input comparator according to the third specific example having the above configuration is a signed function selection type three-input comparator capable of selecting an inequality to be evaluated by the function selection inputs S1 and S0. That is, the function selection input S0 is an A0 input of the (n + 1) -bit width adder 31 and is used to select “A + B−1 ≧ Ref” or “A + B−1> Ref”. The function selection input S1 appropriately inverts / non-inverts the output of the non-negative determination stage 30 so that it is expressed as “1” when the evaluation result of each inequality is “true” and “0” when “false”. Is to do.
[0058]
Table 2 shows the correspondence between the function selection inputs S1 and S0 and the inequality to be evaluated.
[Table 2]

[0059]
By the way, in the first to third specific examples described above, the case where A, B, and Ref are signed binary numbers represented by two's complements is assumed as an example, and a three-input comparator is configured. When an unsigned binary number is input to the three-input comparator according to the first to third specific examples, the result is not correct.
[0060]
For example, when A = 1111, B = 1111 and Ref = 1111, if this is received as a signed binary number, A = −1, B = −1, Ref = −1, and A + B <Ref. On the other hand, when viewed as an unsigned binary number, A = 15, B = 15, and Ref = 15, and A + B <Ref is not satisfied.
[0061]
In general, an unsigned binary number is correctly handled as a positive numerical value in a signed binary number processing system by extending “0” to the MSB side (sign extension). An example in which a signed binary number three-input comparison process is applied to A, B, and Ref subjected to sign extension will be described below.

[0062]

The result is +15 and is non-negative.
[0063]
If the process shown here is realized by hardware as it is, since the sign extension is performed, an (n + 2) bit width adder is required. This is one bit more than the signed case. However, an (n + 1) -bit width adder can be used by taking advantage of the fact that the most significant bit is explicitly determined. Specifically, as shown below, the most significant bits of D and E use D being 1 and E being 0 regardless of the values of A, B, and Ref.
[0064]

[0065]

[0066]
Here, the sign bit S of F is obtained as follows.
S = 0 (+) 1 (+) ("4th to 0th bits of D '+ 4th to 0th bits of E'" carry)
= To (carrying “4th to 0th bits of D ′ + 4th to 0th bits of E ′”)
That is, in order to obtain the sign of the result F, it is only necessary to obtain whether or not there is a carry output when “the 4th to 0th bits of D ′ and the 4th to 0th bits of E ′” are added. If the carry is 1, it can be interpreted as non-negative, and if it is 0, it can be interpreted as negative. Here, (+) is an operation symbol indicating exclusive OR.
[0067]
Therefore, even in the case of an unsigned binary number, the inequality can be evaluated by the (n + 1) bit width adder. Note that the fourth bit of D 'is always "1" in this example, and "1" is always input to the input Bn of the (n + 1) bit width adder. Then, an adder simplified by removing all logic gates not involved in the generation of the carry output Cout is used. In the case of being signed, an adder that is simplified by removing all logic gates that are not involved in the generation of the sum MSB is used.
[0068]
In addition, since the non-negative judgment stage in the case of no sign is the same (n + 1) bit width adder as in the case of being signed, the 3: 2 compressor stage of D and E generation is also exactly the same as in the case of being signed. good. Hereinafter, a specific example of the three-input comparator corresponding to the unsigned input will be described.
[0069]
FIG. 7 is a block diagram showing a fourth specific example of the three-input comparator. The three-input comparator according to the fourth specific example includes a 3: 2 compressor stage 20 in FIG. 2 and a non-negative determination stage 30 in FIG. However, in the first to third specific examples, the (n + 1) -bit width adder 31 that generates the sum Sn is used as the non-negative determination stage 30, but in this example, the carry output Cout is generated (n + 1). A bit width adder 32 is used. In this case, the circuit configuration can be simplified by deleting logic gates that are not involved in Cout generation.
[0070]
The S terminals of the full adders 210 to 21n-1 are connected to the B0 to Bn-1 terminals of the (n + 1) bit width adder 32 in a bit-corresponding manner, and the Cos of the full adders 210 to 21n-1. The terminals are connected to the A1 to An terminals which are one bit higher in the (n + 1) bit width adder 32, respectively. Further, the logic “1” is given to the A0 terminal of the least significant bit and the Bn terminal of the most significant bit of the (n + 1) bit width adder 32, and the Cout output is derived as a comparison result output.
[0071]
In the three-input comparator according to the fourth specific example having the above configuration, the inequality “A + B ≧ Ref” or “A + B <Ref” (A, B, and Ref are unsigned binary numbers) is evaluated. The comparison result output of this three-input comparator can be interpreted as follows. That is, when the comparison result output is “1”, “A + B + (− Ref) ≧ 0”, that is, “A + B ≧ Ref”. When the comparison result output is “0”, “A + B + (− Ref) <0”, that is, “A + B <Ref”.
[0072]
FIG. 8 is a block diagram showing a fifth specific example of the three-input comparator. The components and connection relationships of the three-input comparator according to the fifth specific example are basically the same as those in the fourth specific example. The difference is that in the case of the fourth specific example, the logic “1” is given to the A 0 terminal of the least significant bit and the B n terminal of the most significant bit of the (n + 1) bit width adder 32, respectively. In this example, the logic “1” is given to the A0 terminal of the least significant bit of the (n + 1) bit width adder 32, and the logic “1” is given to the Bn terminal of the most significant bit.
[0073]
In the three-input comparator according to the fifth specific example having the above configuration, the inequality “A + B> Ref” or “A + B ≦ Ref” (A, B, and Ref are unsigned binary numbers) is evaluated. The comparison result output of the three-input comparator can be interpreted in the same manner as in the second specific example.
[0074]
FIG. 9 is a block diagram showing a sixth specific example of the three-input comparator. The three-input comparator according to the sixth specific example comprises a 3: 2 compressor stage 20, a non-negative decision stage 30 comprising an (n + 1) -bit width adder 32, and an EX-OR gate 41, and full adders 210 to 21n. -1 S and Co terminals and the A0 to An and B0 to Bn terminals of the (n + 1) bit width adder 32 have the same connection relationship as in the fourth and fifth specific examples, and further have an (n + 1) bit width Logic “1” is given to the Bn terminal of the most significant bit of the adder 32. In addition, the function selection input S0 is given to the A0 terminal of the least significant bit of the (n + 1) bit width adder 32, and (n + 1) The Sn output of the bit width adder 32 and the function selection input S1 are two inputs of the EX-OR gate 41, and the output of the EX-OR gate 41 is derived as a comparison result output.
[0075]
The three-input comparator according to the sixth specific example having the above configuration is an unsigned function selection type three-input comparator capable of selecting an inequality to be evaluated by function selection inputs S1 and S0. That is, the function selection input S0 is an A0 input of the (n + 1) -bit width adder 32 and is used to select “A + B−1 ≧ Ref” or “A + B−1> Ref”. The function selection input S1 appropriately inverts / non-inverts the output of the non-negative determination stage 30 so that it is expressed as “1” when the evaluation result of each inequality is “true” and “0” when “false”. Is to do. The correspondence relationship between the function selection inputs S1 and S0 and the inequality to be evaluated is the same as in the third specific example (see Table 2).
[0076]
FIG. 10 is a block diagram showing a seventh specific example of the three-input comparator. The three-input comparator according to the seventh specific example includes a 3: 2 compressor stage 20, a non-negative determination stage 30, an EX-OR gate 41, a selector 42, and an OR gate 43. As the 3: 2 compressor stage 20, the one shown in FIG. 2 is used. As the 3: 2 compressor stage 20, an (n + 1) -bit width adder 33 that generates both Cout and Sn is used. In this case, the circuit configuration can be simplified by deleting logic gates that are not involved in Cout and Sn generation.
[0077]
Further, the S and Co terminals of the full adders 210 to 21n-1 of the 3: 2 compressor stage 20 and the A0 to An and B0 to Bn terminals of the (n + 1) bit width adder 33 are the fourth to sixth examples. The connection is the same as in the case of. Then, the function selection input S0 is given to the A0 terminal of the least significant bit of the (n + 1) bit width adder 33. The S output of the highest adder 21n-1 and the function selection input S2 of the 3: 2 compressor stage 20 are two inputs of the OR gate 43, and the output of the OR gate 43 is the (n + 1) bit width adder 33. It is given to the Bn terminal of the most significant bit.
[0078]
The selector 42 receives the Cout output and the Sn output of the (n + 1) -bit width adder 33 as two inputs, and selects and outputs one of the two inputs according to the logic state of the function selection input S2. In the function selection input S2, A, B, and Ref are signed binary numbers when the logic is “0”, and A, B, and Ref are unsigned binary numbers when the logic is “1”. Therefore, the selector 42 selects the Sn output when the function selection input S2 is logic “0”, and selects the Cout output when the function selection input S2 is logic “1”. The selection output of the selector 42 and the function selection input S1 become two inputs of the EX-OR gate 41, and the output of the EX-OR gate 41 is derived as a comparison result output.
[0079]
The three-input comparator according to the seventh specific example having the above-described configuration is formed by integrating the signed function selection type three-input comparator according to the third specific example and the unsigned function selection type three-input comparator according to the sixth specific example. It is a fully integrated three-input comparator that can dynamically set the signed / unsigned and inequality to be evaluated.
[0080]
That is, the function selection input S0 is the A0 input of the (n + 1) -bit width adder 33, and selects “A + B−1 ≧ Ref” or “A + B−1> Ref”. The function selection input S1 appropriately inverts / non-inverts the output of the non-negative determination stage 30 so that it is expressed as “1” when the evaluation result of each inequality is “true” and “0” when “false”. (See Table 2). Furthermore, the function selection input S2 is set with or without a sign.
[0081]
In the three-input comparators according to the first to seventh specific examples described above, the number of gates of the (n + 1) bit width adder used in each non-negative determination stage is substantially equal to the comparator used in the conventional apparatus. On the other hand, the number of gates slightly increases by the carry-save type adder used in the 3: 2 compressor stage. However, it is not the comparator but the adder that performs (A + B) that is dominant with respect to the number of gates of the entire saturation arithmetic unit. Therefore, the number of gates increased by applying the present invention is not a problem.
[0082]
FIG. 11 is a block diagram showing a second embodiment of the present invention, and shows a case where two reference values Ref are applied, that is, a case where the present invention is applied to a saturation adder that can specify both an upper limit value and a lower limit value.
[0083]
The saturation adder according to the second embodiment includes an adder 51 that performs addition of two n-bit inputs A and B, and an n-bit of two inputs A and B provided in parallel to the adder 51. Are added in parallel to the adder 51 and a three-input comparator 52 for judging whether or not the addition result of the above deviates from the range defined by the n-bit upper limit reference value Ref (upper). , B is a 3-input comparator 53 that determines whether or not the addition result of B deviates from the range defined by the n-bit lower limit reference value Ref (lower), and each 1-bit of these 3-input comparators 52 and 53 ( A selector that selects and outputs one of the addition result of the adder 51, the n-bit upper limit saturation value Sat (upper) and the n-bit lower limit saturation value Sat (lower) based on the comparison result of 2 bits in total) 54.
[0084]
In the saturation adder according to the second embodiment having the above-described configuration, the two reference values Ref (upper) and Ref (lower) and the two saturation values Sat (upper) and Sat (lower) can be arbitrarily set externally. It is. As the two three-input comparators 52 and 53, an appropriate one is selected from the three-input comparators according to the first to seventh specific examples described above according to the inequalities to be evaluated and the functions that can be selected. Use. Further, the connection with the selector 54 is performed after the meanings of the outputs of the three-input comparators 52 and 53 are well judged. The selector 54 used here has three inputs.
[0085]
Here, when the bit width of the input numerical value is n bits, the delay times of the adder 51 and the two three-input comparators 52 and 53 are both proportional to log n, and the delay times of both are substantially equal. Actually, as described above, the delay time of the three-input comparators 52 and 53 is slightly shorter than that of the adder 51 due to the simplicity of the hardware of the three-input comparators 52 and 53. Therefore, by arranging two three-input comparators 52 and 53 in parallel with respect to the adder 51 and performing addition and comparison in parallel, the total delay time becomes equivalent to that in the first embodiment. That is, high speed operation is possible.
[0086]
By the way, the following four propositions are obvious.
{Circle around (1)} When there are integers A, B, and Ref satisfying A−B> Ref, Ref + B <A is always satisfied.
(2) When there are integers A, B, and Ref satisfying A−B ≧ Ref, Ref + B ≦ A is always satisfied.
(3) When there are integers A, B, and Ref that satisfy A−B ≦ Ref, Ref + B ≧ A is always satisfied.
(4) When there are integers A, B, and Ref satisfying A−B <Ref, Ref + B> A is always satisfied.
[0087]
From the above proposition, it can be seen that all evaluations of inequalities including subtraction (A−B) are replaced with evaluations of inequalities including addition (Ref + B). That is, by replacing the input A and the reference value Ref and inputting them to the three-input adder 12 (see FIG. 1) in the saturation adder according to the first embodiment, no changes are made to the hardware. , Inequality including subtraction (A-B) can be evaluated.
[0088]
FIG. 12 is a block diagram showing a third embodiment of the present invention, and shows a case where the reference value Ref is one, that is, a case where it is applied to a saturation subtractor capable of designating either an upper limit / lower limit value.
[0089]
The saturation subtraction apparatus according to the third embodiment includes a subtractor 61 that subtracts two n-bit inputs A and B, and a subtraction result of two inputs A and B provided in parallel to the subtractor 61. , And a subtraction result of the subtractor 61 based on the 1-bit comparison result of the 3-input comparator 62. The selector 63 is configured to select and output one of the n-bit saturation values Sat.
[0090]
In the saturation subtraction apparatus according to the third embodiment having the above configuration, the reference value Ref and the saturation value Sat can be arbitrarily set outside. Here, when the saturation subtraction apparatus according to the present embodiment is compared with the saturation addition apparatus according to the first embodiment, the inputs A and Ref to the three-input comparator 62 are replaced with each other. As the three-input comparator 62, an appropriate one is selected from the three-input comparators according to the first to seventh specific examples described above according to the inequalities to be evaluated and the functions that can be selected. However, care must be taken when selecting.
[0091]
For example, when it is desired to evaluate the inequality “A−B <REF”, a three-input comparator 62 that evaluates “a + b> ref” is used. Since the inequality sign is opposite to REF and ref, it is easy to make a mistake. This is because a = REF, b = B, and ref = A are input to “a + b> ref”, and “REF + B> A”, that is, “A−B <REF” is evaluated.
[0092]
Therefore, when evaluating “A−B <REF”, a three-input comparator that evaluates “a + b> ref”, and when evaluating “A−B ≦ REF”, evaluate “a + b ≧ ref”. When evaluating a three-input comparator “A−B ≧ REF”, a three-input comparator evaluating “a + b ≦ ref”, and when evaluating “A−B> REF”, “a + b <ref”. Each of the three-input comparators that evaluate "" is used.
[0093]
As described above, in the saturation subtraction apparatus according to the third embodiment, since the input connection to the three-input comparator 62 is only changed with respect to the saturation addition apparatus according to the first embodiment of FIG. The time is equivalent to that of the saturation adder of FIG. 1, and high speed operation is possible.
[0094]
FIG. 13 is a block diagram showing the fourth embodiment of the present invention. As in the case of the saturation subtraction apparatus according to the second embodiment, there are two reference values Ref, that is, both the upper limit value and the lower limit value. This shows a case where the present invention is applied to a specifiable saturation subtraction device.
[0095]
The saturation subtraction apparatus according to the fourth embodiment includes a subtractor 71 that performs subtraction of two n-bit inputs A and B, and a subtraction result of two inputs A and B provided in parallel to the subtracter 71. Is provided in parallel to a subtracter 71 and a three-input comparator 72 for determining whether or not the value deviates from the range defined by the n-bit upper limit reference value Ref (upper). A three-input comparator 73 for determining whether or not the n-bit subtraction result is out of the range defined by the n-bit lower limit reference value Ref (lower), and each bit of the three-input comparators 72 and 73 ( A selector that selects and outputs one of the subtraction result of the subtractor 71, the n-bit upper limit saturation value Sat (upper), and the n-bit lower limit saturation value Sat (lower) based on the comparison result of 2 bits in total) 74.
[0096]
In the saturation subtraction apparatus according to the fourth embodiment having the above-described configuration, the two reference values Ref (upper), Ref (lower) and the two saturation values Sat (upper), Sat (lower) can be arbitrarily set externally. It is. Here, when comparing the saturation subtraction apparatus according to the present embodiment with the saturation addition apparatus according to the second embodiment, the input A and Ref (upper), Ref (lower) for the three-input comparators 72 and 73 are interchanged. ing. As the three-input comparators 72 and 73, as in the case of the third embodiment, an appropriate one is selected from the three-input comparators according to the first to seventh specific examples described above.
[0097]
Up to this point, the case where the present invention is applied to the saturation adder and the saturation subtractor has been described. Subsequently, the case where the present invention is applied to a saturation multiplier will be described.
[0098]
Some common high-speed multipliers use a carry-save type adder (3: 2 compressor), a 4: 2 compressor, a redundant binary adder, or the like. In these multipliers, carry propagation is suppressed at the stage of obtaining a partial product, and partial product addition is performed at high speed. Finally, the partial product is expressed by two binary numbers A and B, and the true product is obtained by A + B (A−B in redundant binary). This is called final stage addition.
[0099]
To determine whether the multiplication result exceeds a certain reference value is to determine whether the partial product sum (A + B) (A-B for redundant binary) performed in the final stage addition exceeds the reference value. Is equal to Therefore, a saturation multiplication apparatus can be configured by providing a three-input comparator in parallel with the final stage addition.
[0100]
FIG. 14 is a block diagram showing a fifth embodiment of the present invention, and shows a case where there is one reference value Ref, that is, a case where the present invention is applied to a saturation multiplication device that can designate either an upper limit or a lower limit value.
[0101]
The saturation multiplication apparatus according to the fifth embodiment includes a partial product adder 81 that performs partial product addition of two n / 2-bit inputs X and Y, and two n-bit inputs supplied from the partial product adder 81. A final stage adder 82 that performs final stage addition of inputs A and B, and a final stage addition result of two inputs A and B are provided in parallel with the final stage adder 82 as an n-bit reference value Ref. A three-input comparator 83 for determining whether or not a predetermined range is deviated, and based on the one-bit comparison result of the three-input comparator 83, the addition result of the final stage adder 82 and the n-bit saturation value Sat And a selector 84 that selects and outputs one of the two.
[0102]
In the saturation multiplication apparatus according to the fifth embodiment having the above-described configuration, the reference value Ref and the saturation value Sat can be arbitrarily set outside. The configuration after the output of the partial product adder 81 is the same as that of the saturation adder device according to the first embodiment shown in FIG. Therefore, since the total delay time after the output of the partial product adder 81 is equivalent to that of the saturation adder of FIG. 1, high speed operation is possible.
[0103]
In the present embodiment, the case where the partial product sum (A + B) is obtained in the final stage has been described as an example. However, in the case where (A−B) is performed as in redundant binary, the third embodiment is concerned. This can be realized by selecting a three-input comparator based on the same principle as that of the saturation subtractor and replacing the connection relationship between the inputs A and Ref.
[0104]
Further, as in the case of the saturation adder according to the second embodiment and the saturation subtractor according to the fourth embodiment, the upper limit can be obtained by providing two three-input comparators in parallel with the final stage adder 82. It is possible to realize a saturation multiplier that can specify both the value and the lower limit value.
[0105]
As described above, the case where the present invention is applied to the saturation adder, the saturation subtractor, and the saturation multiplier has been described. However, the present invention is not limited to these, and finally addition or subtraction is performed as in the saturation multiplier according to the fifth embodiment. Any arithmetic device that performs the above can perform high-speed saturation arithmetic processing using a three-input comparator. In other words, by providing a 3-input comparator in parallel with the adder or subtracter in the final stage, the inequality is evaluated simultaneously with the addition / subtraction. Prove. After that, by using a selector appropriately, an addition / subtraction value or a saturation value (single or plural) is selected.
[0106]
By doing so, it is possible to add a saturation calculation process that can specify an arbitrary reference value and an arbitrary saturation value. In addition, in the arithmetic processing (polynomial arithmetic) in which addition, subtraction, and multiplication are combined, an arithmetic operation that suppresses carry propagation is performed using a carry / save type adder or a redundant binary adder. At this time, the final result is always obtained by the sum (or difference) of two binary numbers, and an adder / subtracter with carry propagation is always used in the final stage.
[0107]
The saturation calculation device according to each of the embodiments described above is suitable as an example when the drawing is performed in a rectangular area existing at an arbitrary position on the display. That is, there is a rectangular area of an arbitrary size at an arbitrary position on the display, and when drawing is performed in the area, saturation calculation of an arbitrary reference value and an arbitrary saturation value is required.
[0108]
The calculation of screen coordinates is generally performed by addition / multiplication or polynomial calculation. When the coordinates to be drawn deviate from the area, it is necessary to correct the boundary value of the area or an appropriate saturation value, or to start another exception process. In such a case, these processes can be executed at high speed by using the saturation arithmetic device according to each embodiment.
[0109]
In general signal processing, linear polynomial operations, that is, product-sum operations are frequently performed. At this time, saturation calculation processing is essential. Depending on a certain signal processing algorithm, a saturation operation may be performed below the maximum value (overflow) of the adder. In some signal processing, a fraction having the value of a linear polynomial (product-sum operation) as a denominator may be evaluated. In this case, this polynomial is not allowed to be zero. When performing the saturation calculation processing using a reference value other than the maximum value (overflow) of the adder as described above, it can be performed at high speed by using the saturation calculation device according to each embodiment.
[0110]
As described above, there are many applications of saturation calculation processing using a value other than the maximum value of the adder as a reference value, and high speed is always required. By using the saturation calculation device according to each embodiment, it is possible to speed up these processes.
[0111]
【The invention's effect】
As described above, according to the present invention, the sum of three binary numbers (A, B, Ref) having an n-bit width is converted into two binary numbers having an n-bit width, and based on the two binary numbers. By determining whether or not the sum value is non-negative, it is possible to quickly determine whether or not the calculation results of the two inputs A and B are out of the range defined by the predetermined reference value Ref. This can contribute to high-speed processing of saturation calculation.
[0112]
  In addition, the calculation process of two inputs and the determination process of whether or not the calculation result deviates from the range determined by the predetermined reference value are performed in parallel. Based on the determination result, the calculation result and a predetermined value are determined. By selecting and outputting one of the saturation values, saturation calculation can be performed in two stages of “calculation / comparison → selection”, so the reference value and saturation value can be specified arbitrarily, and high-speed calculation can be performed. Can be realized.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a first embodiment of the present invention.
FIG. 2 is a block diagram showing the configuration of a 3: 2 compressor stage.
FIG. 3 is a block diagram illustrating a configuration of a non-negative determination stage.
FIG. 4 is a block diagram showing a first specific example of a three-input comparator.
FIG. 5 is a block diagram showing a second specific example of a three-input comparator.
FIG. 6 is a block diagram showing a third specific example of a three-input comparator.
FIG. 7 is a block diagram showing a fourth specific example of a three-input comparator.
FIG. 8 is a block diagram showing a fifth specific example of a three-input comparator.
FIG. 9 is a block diagram showing a sixth specific example of a three-input comparator.
FIG. 10 is a block diagram showing a seventh example of the three-input comparator.
FIG. 11 is a block diagram showing a second embodiment of the present invention.
FIG. 12 is a block diagram showing a third embodiment of the present invention.
FIG. 13 is a block diagram showing a fourth embodiment of the present invention.
FIG. 14 is a block diagram showing a fifth embodiment of the present invention.
FIG. 15 is a block diagram showing a conventional example.
[Explanation of symbols]
11, 51, 82 ... adder, 12, 52, 53, 62, 72, 73, 83 ... 3-input comparator, 13, 42, 54, 63, 74, 84 ... selector, 20 ... 3: 2 compressor stage, 30 ... Non-negative judgment stage, 31 ... (n + 1) bit width adder, 41 ... EX-OR gate, 210 to 21n-1 ... Full adder, 220 to 22n-1 ... Inverter

Claims (5)

A 3: 2 compressor stage that receives three binary numbers (A, B, Ref) having an n-bit width as input and converts the sum into two binary numbers (Co, S) having an n-bit width and outputs the same. A non-negative determination stage for determining whether or not the sum value is non-negative based on the two binary numbers (Co, S) output from the two compressor stages ;
The 3: 2 compressor stage inputs two binary numbers (A, B) as they are for each bit, and inputs 3 binary numbers (Ref) by taking the negation for each bit as an input and has an n-bit width of 3 : 2 compressors
When the three binary numbers (A, B, Ref) are signed binary numbers represented by 2's complement representation, the non-negative determination stage includes the (i + 1) -th digit of the S output of the 3: 2 compressor stage and the Co output. The i-th digit (n−2 ≧ i ≧ 0) is the (i + 1) th digit input, the 0th digit of the S output and the logic “0” are the 0th digit input, and the (n− 1) An (n + 1) -bit adder having the (n-1) -th digit of the Co output and the (n-1) -th digit of the Co output as an input of the n-th digit and the n-th digit Sn of the sum output as a judgment output. The nth digit Sn of the sum output of the width adder is used as a judgment output,
The three-input comparator, wherein the (n + 1) -bit width adder is constituted only by a logic gate related to generation of the n-th digit Sn of the sum output . A 3: 2 compressor stage that receives three binary numbers (A, B, Ref) having an n-bit width as input and converts the sum into two binary numbers (Co, S) having an n-bit width and outputs the same. A non-negative determination stage for determining whether or not the sum value is non-negative based on the two binary numbers (Co, S) output from the two compressor stages;
The 3: 2 compressor stage inputs two binary numbers (A, B) as they are for each bit, and inputs 3 binary numbers (Ref) by taking the negation for each bit as an input and has an n-bit width of 3 : 2 compressors
When the three binary numbers (A, B, Ref) are signed binary numbers represented by two's complement representation, the non-negative determination stage includes the (i + 1) th digit of the S output of the 3: 2 compressor stage and the Co output. The i-th digit (n−2 ≧ i ≧ 0) is the (i + 1) -th digit input, the 0th digit of the S output and the first function selection input are the 0th digit input, and the (n) th (n) of the S output -1) the (n + 1) -bit width adder with the (n-1) -th digit of the Co output as the n-th digit input; and the n-th digit Sn of the sum output of the (n + 1) -bit width adder; An EX-OR gate having a second function selection input as two inputs, and the output of the EX-OR gate as a determination output,
The (n + 1) -bit width adder is composed only of logic gates related to the generation of the n-th digit Sn of the sum output.
A three-input comparator. A 3: 2 compressor stage that receives three binary numbers (A, B, Ref) having an n-bit width as input and converts the sum into two binary numbers (Co, S) having an n-bit width and outputs the same. A non-negative determination stage for determining whether or not the sum value is non-negative based on the two binary numbers (Co, S) output from the two compressor stages;
The 3: 2 compressor stage inputs two binary numbers (A, B) as they are for each bit, and inputs 3 binary numbers (Ref) by taking the negation for each bit as an input and has an n-bit width of 3 : 2 compressors
When the three binary numbers (A, B, Ref) are unsigned binary numbers, the non-negative determination stage performs the (i + 1) digit of the S output of the 3: 2 compressor stage and the i digit (n of the Co output). −2 ≧ i ≧ 0) as the (i + 1) th digit input, the S output 0th digit and logic “0” as the 0th digit input, and the Co output (n−1) th digit and logic. It is composed of an (n + 1) bit width adder having “1” as the nth digit input and the carry output Cout as the decision output, and the carry output Cout of the (n + 1) bit width adder as the decision output,
The (n + 1) -bit width adder is composed only of logic gates related to generation of the carry output Cout.
A three-input comparator. A 3: 2 compressor stage that receives three binary numbers (A, B, Ref) having an n-bit width as input and converts the sum into two binary numbers (Co, S) having an n-bit width and outputs the same. A non-negative determination stage for determining whether or not the sum value is non-negative based on the two binary numbers (Co, S) output from the two compressor stages;
The 3: 2 compressor stage inputs two binary numbers (A, B) as they are for each bit as it is, and inputs 3 binary numbers (Ref) as an input by taking the negation of each bit as a negative bit. : 2 compressors
When the three binary numbers (A, B, Ref) are unsigned binary numbers, the non-negative determination stage performs the (i + 1) digit of the S output of the 3: 2 compressor stage and the i digit (n of the Co output). −2 ≧ i ≧ 0) as the (i + 1) th digit input, the 0th digit of the S output and the first function selection input as the 0th digit input, and the (n−1) th digit of the Co output An (n + 1) -bit width adder having logic “1” as the n-th digit input; an EX-OR gate having two inputs of the carry output Cout and the second function selection input of the (n + 1) -bit width adder; And determining and outputting the output of the EX-OR gate,
The (n + 1) -bit width adder is composed only of logic gates related to generation of the carry output Cout.
A three-input comparator. A 3: 2 compressor stage that receives three binary numbers (A, B, Ref) having an n-bit width as input and converts the sum into two binary numbers (Co, S) having an n-bit width and outputs the same. A non-negative determination stage for determining whether or not the sum value is non-negative based on the two binary numbers (Co, S) output from the two compressor stages;
The 3: 2 compressor stage inputs two binary numbers (A, B) as they are for each bit, and inputs 3 binary numbers (Ref) by taking the negation for each bit as an input and has an n-bit width of 3 : 2 compressors
When the three binary numbers (A, B, Ref) are signed binary numbers with 2's complement representation or unsigned binary numbers, the non-negative determination stage determines the (n-1) -th digit of the S output. OR function with 3 function selection inputs as 2 inputs, (i + 1) digit of S output of 3: 2 compressor stage, and i digit (n-2 ≧ i ≧ 0) of Co output (i + 1) digit The 0th digit of the S output and the first function selection input are the 0th digit input, and the (n-1) th digit of the Co output and the output of the OR gate are the nth digit input. The carry output Cout of the (n + 1) bit width adder when the (n + 1) bit width adder and the third function selection input are “1”, and the (n + 1) bit width adder of the (n + 1) bit width adder when “0”. Selector for selecting negation of n-th digit Sn of sum output, and negation of selection result of the selector It consists of a EX-OR gate for the second function selection input 2 input, and determines an output of the EX-OR gate,
The (n + 1) -bit width adder is composed only of the carry output Cout, the sum output, and the logic gate related to the generation of the nth digit Sn.
A three-input comparator.

Images