(57)【特許請求の範囲】
【請求項１】
ｎビット幅の３つの２進数（Ａ，Ｂ，Ｒｅｆ）を入力とし、その総和をｎビット幅の２つの２進数（Ｃｏ，Ｓ）に変換して出力する３：２コンプレッサ段と、前記３：２コンプレッサ段から出力される前記２つの２進数（Ｃｏ，Ｓ）に基づいて前記総和の値が非負であるか否かを判定する非負判定段とを備え、
前記３：２コンプレッサ段は、２つの２進数（Ａ，Ｂ）をそのままビット毎に入力とするとともに、１つの２進数（Ｒｅｆ）をビット毎の否定をとって入力とするｎビット幅の３：２コンプレッサからなり、
前記３つの２進数（Ａ，Ｂ，Ｒｅｆ）が２の補数表現による符号付き２進数のとき、前記非負判定段は、前記３：２コンプレッサ段のＳ出力の第（ｉ＋１）桁とＣｏ出力の第ｉ桁（ｎ−２≧ｉ≧０）を第（ｉ＋１）桁の入力とし、前記Ｓ出力の第０桁と論理“０”を第０桁の入力とし、前記Ｓ出力の第（ｎ−１）桁と前記Ｃｏ出力の第（ｎ−１）桁を第ｎ桁の入力とし、和出力の第ｎ桁Ｓｎを判定出力とする（ｎ＋１）ビット幅加算器からなり、前記（ｎ＋１）ビット幅加算器の和出力の第ｎ桁Ｓｎを判定出力とし、
前記（ｎ＋１）ビット幅加算器は、その和出力の第ｎ桁Ｓｎの生成に関わる論理ゲートのみによって構成されている
ことを特徴とする３入力比較器。
【請求項２】
ｎビット幅の３つの２進数（Ａ，Ｂ，Ｒｅｆ）を入力とし、その総和をｎビット幅の２つの２進数（Ｃｏ，Ｓ）に変換して出力する３：２コンプレッサ段と、前記３：２コンプレッサ段から出力される前記２つの２進数（Ｃｏ，Ｓ）に基づいて前記総和の値が非負であるか否かを判定する非負判定段とを備え、
前記３：２コンプレッサ段は、２つの２進数（Ａ，Ｂ）をそのままビット毎に入力とするとともに、１つの２進数（Ｒｅｆ）をビット毎の否定をとって入力とするｎビット幅の３：２コンプレッサからなり、
前記３つの２進数（Ａ，Ｂ，Ｒｅｆ）が２の補数表現による符号付き２進数のとき、前記非負判定段は、前記３：２コンプレッサ段のＳ出力の第（ｉ＋１）桁とＣｏ出力の第ｉ桁（ｎ−２≧ｉ≧０）を第（ｉ＋１）桁の入力とし、前記Ｓ出力の第０桁と第１機能選択入力を第０桁の入力とし、前記Ｓ出力の第（ｎ−１）桁と前記Ｃｏ出力の第（ｎ−１）桁を第ｎ桁の入力とする（ｎ＋１）ビット幅加算器と、前記（ｎ＋１）ビット幅加算器の和出力の第ｎ桁Ｓｎと第２機能選択入力を２入力とするＥＸ‐ＯＲゲートとからなり、前記ＥＸ‐ＯＲゲートの出力を判定出力とし、
前記（ｎ＋１）ビット幅加算器は、その和出力の第ｎ桁Ｓｎの生成に関わる論理ゲートのみによって構成されている
ことを特徴とする３入力比較器。
【請求項３】
ｎビット幅の３つの２進数（Ａ，Ｂ，Ｒｅｆ）を入力とし、その総和をｎビット幅の２つの２進数（Ｃｏ，Ｓ）に変換して出力する３：２コンプレッサ段と、前記３：２コンプレッサ段から出力される前記２つの２進数（Ｃｏ，Ｓ）に基づいて前記総和の値が非負であるか否かを判定する非負判定段とを備え、
前記３：２コンプレッサ段は、２つの２進数（Ａ，Ｂ）をそのままビット毎に入力とするとともに、１つの２進数（Ｒｅｆ）をビット毎の否定をとって入力とするｎビット幅の３：２コンプレッサからなり、
前記３つの２進数（Ａ，Ｂ，Ｒｅｆ）が符号無し２進数のとき、前記非負判定段は、前記３：２コンプレッサ段のＳ出力の第（ｉ＋１）桁とＣｏ出力の第ｉ桁（ｎ−２≧ｉ≧０）を第（ｉ＋１）桁の入力とし、前記Ｓ出力の第０桁と論理“０”を第０桁の入力とし、前記Ｃｏ出力の第（ｎ−１）桁と論理“１”を第ｎ桁の入力とし、桁上げ出力Ｃｏｕｔを判定出力とする（ｎ＋１）ビット幅加算器からなり、前記（ｎ＋１）ビット幅加算器の桁上げ出力Ｃｏｕｔを判定出力とし、
前記（ｎ＋１）ビット幅加算器は、その桁上げ出力Ｃｏｕｔの生成に関わる論理ゲートのみによって構成されている
ことを特徴とする３入力比較器。
【請求項４】
ｎビット幅の３つの２進数（Ａ，Ｂ，Ｒｅｆ）を入力とし、その総和をｎビット幅の２つの２進数（Ｃｏ，Ｓ）に変換して出力する３：２コンプレッサ段と、前記３：２コンプレッサ段から出力される前記２つの２進数（Ｃｏ，Ｓ）に基づいて前記総和の値が非負であるか否かを判定する非負判定段とを備え、
前記３：２コンプレッサ段は、２つの２進数（Ａ，Ｂ）をそのままビット毎に入力とするとともに、１つの２進数（Ｒｅｆ）をビット毎の否定をとって入力とするｎビット幅の３：２コンプレッサからなり、
前記３つの２進数（Ａ，Ｂ，Ｒｅｆ）が符号無し２進数のとき、前記非負判定段は、前記３：２コンプレッサ段のＳ出力の第（ｉ＋１）桁とＣｏ出力の第ｉ桁（ｎ−２≧ｉ≧０）を第（ｉ＋１）桁の入力とし、前記Ｓ出力の第０桁と第１機能選択入力を第０桁の入力とし、前記Ｃｏ出力の第（ｎ−１）桁と論理“１”を第ｎ桁の入力とする（ｎ＋１）ビット幅加算器と、前記（ｎ＋１）ビット幅加算器の桁上げ出力Ｃｏｕｔと第２機能選択入力を２入力とするＥＸ‐ＯＲゲートとからなり、前記ＥＸ‐ＯＲゲートの出力を判定出力し、
前記（ｎ＋１）ビット幅加算器は、その桁上げ出力Ｃｏｕｔの生成に関わる論理ゲートのみによって構成されている
ことを特徴とする３入力比較器。
【請求項５】
ｎビット幅の３つの２進数（Ａ，Ｂ，Ｒｅｆ）を入力とし、その総和をｎビット幅の２つの２進数（Ｃｏ，Ｓ）に変換して出力する３：２コンプレッサ段と、前記３：２コンプレッサ段から出力される前記２つの２進数（Ｃｏ，Ｓ）に基づいて前記総和の値が非負であるか否かを判定する非負判定段とを備え、
前記３：２コンプレッサ段は、２つの２進数（Ａ，Ｂ）をそのままビット毎に入力とするとともに、１つの２進数（Ｒｅｆ）をビット毎の否定をとって入力とするｎビット幅の３：２コンプレッサからなり、
前記３つの２進数（Ａ，Ｂ，Ｒｅｆ）が２の補数表現による符号付き２進数、あるいは符号無し２進数のとき、前記非負判定段は、前記Ｓ出力の第（ｎ−１）桁と第３機能選択入力を２入力とするＯＲゲートと、前記３：２コンプレッサ段のＳ出力の第（ｉ＋１）桁とＣｏ出力の第ｉ桁（ｎ−２≧ｉ≧０）を第（ｉ＋１）桁の入力とし、前記Ｓ出力の第０桁と第１機能選択入力を第０桁の入力とし、前記Ｃｏ出力の第（ｎ−１）桁と前記ＯＲゲートの出力を第ｎ桁の入力とする（ｎ＋１）ビット幅加算器と、前記第３機能選択入力が“１”のとき前記（ｎ＋１）ビット幅加算器の桁上げ出力Ｃｏｕｔを、“０”のとき前記（ｎ＋１）ビット幅加算器の和出力の第ｎ桁Ｓｎの否定をそれぞれ選択するセレクタと、前記セレクタの選択結果の否定と第２機能選択入力を２入力とするＥＸ‐ＯＲゲートとからなり、前記ＥＸ‐ＯＲゲートの出力を判定出力とし、
前記（ｎ＋１）ビット幅加算器は、その桁上げ出力Ｃｏｕｔと和出力および第ｎ桁Ｓｎの生成に関わる論理ゲートのみによって構成されている
ことを特徴とする３入力比較器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、半導体集積回路におけるデジタル演算装置、特に飽和演算装置に用いて好適な３入力比較器に関する。
【０００２】
ここで言う飽和演算装置とは、ある演算を行った結果値が、ある与えられた基準値（reference value ：以降、単にＲｅｆと略す）で定められる範囲内の場合には演算結果値を出力し、当該範囲を越えた場合には与えられた飽和値（saturation value：以降、単にＳａｔと略す）を出力する演算装置である。この飽和演算装置としては、飽和加算装置、飽和減算装置、飽和乗算装置などがある。
【０００３】
【従来の技術】
飽和演算装置の一種である例えば飽和加算装置は、加算結果が正の最大値を越えた場合には出力を正の最大値に補正し、負の最大値を越えた場合は出力を負の最大値に補正するものである。この一般的な飽和加算装置において、越えたか否かの基準となる値は、正の最大値・負の最大値に固定されており、任意の値を基準値にすることは出来ない。
【０００４】
ところで、飽和加算装置と言う場合、それは加算のオーバーフローによる飽和演算を指す。加算のオーバーフローとは、加算の結果値がその加算装置の出力のビット数で表現できる範囲を超えた場合に起こり、オーバーフロー・フラグとして表現される。すなわち、オーバーフローが起こったならば“１”、そうでないならば“０”というフラグ状態となる。
【０００５】
入出力する数値が符号無しの２進数の場合には、加算装置の桁上げ出力（キャリーアウト）がオーバーフローも意味している。しかし、入出力する数値が２の補数表現による符号有り２進数の場合には、桁上げ出力はオーバーフローを意味しない。例えば、入力が４ビット、出力が４ビットの加算を例に採る。
0111 + 0001 = 桁上げ出力0 , 数値1000
のとき、符号無しの場合は７＋１を意味し、結果は＋８を意味している。結果は正しく、桁上げ出力は０であり、オーバーフローでない。一方、符号有りの場合は７＋１を意味し、結果は−８を意味している。結果は誤りで、桁上げ出力は０であるが、オーバーフローである。
【０００６】
また、
1001 + 1111 = 桁上げ出力1 , 数値1000
のとき、符号無しの場合は９＋１５を意味し、結果は８である。結果は誤りで、桁上げ出力が１であり、オーバーフローである。符号有りの場合は−７＋（−１）を意味し、結果は−８を意味している。結果は正しく、桁上げ出力は１であるが、オーバーフローではない。
【０００７】
以上のように、入出力する数値が符号無しか、符号付きかによって、オーバーフローの検出の仕方は異なる。符号付きの場合、普通の加算器の内部に簡単な回路を付加することによって、オーバーフロー・フラグを作ることが出来る。桁上げ出力とオーバーフロー・フラグは加算の終了とともに出力される。結局、符号無し／符号付きのいずれの場合であっても、オーバーフローか否かは、加算結果と同時に判明する。
【０００８】
飽和加算装置の出力がｎビットのとき、加算結果値が符号無しの場合に２n 以上、符号有りの場合に２n-1 以上、又は−（２n-1 ＋１) 以下でオーバーフローが起こる。飽和加算装置での飽和加算は、このオーバーフローに基づいて行われる。例えば、（0111＋0001）の演算のとき、符号無しの場合はオーバーフローではないので、加算結果1000 (8)を出力する。符号有りの場合はオーバーフローなので、飽和値0111 (7)を出力する。また、（1001＋1111）の演算のとき、符号無しの場合はオーバーフローなので、飽和値1111 (15) を出力する。符号有りの場合はオーバーフローではないので、加算結果 1000 (-8)を出力する。
【０００９】
通常はオーバーフローが起こる境界の値、即ち正の最大値か、負の最大値を飽和値とする。しかしながら、従来の飽和加算装置においては、正の最大値あるいは負の最大値以外の数値を基準値として、これを越えた場合を判定することは原理的に不可能である。なぜなら、加算結果が最大値でない基準値を逸脱したとしても、オーバーフローが起こらないからである。
【００１０】
ところで、コンピュータによって、ディスプレイ上の任意の矩形領域内の描画を行う場合、任意基準値・任意飽和値の飽和演算が頻繁に行われる。例えば、ある図形をディスプレイ上の矩形領域内に描画するとき、その領域をはみ出す部分は描画しないように処理する必要がある。このときの描画座標の計算過程においては、常に、Ｘ，Ｙ座標が領域内であるか否かの判定と、領域を越えた場合には境界値に補正する演算処理、即ち飽和演算が行われている。矩形領域が画面上のどこにあっても、このような境界値への補正を行うためには、基準値・飽和値をそれぞれ任意に指定可能な飽和加算装置が必要である。
【００１１】
従来、この基準値・飽和値をそれぞれ任意に指定可能な飽和加算を実現する飽和加算装置として、図１５に示すように、加算入力Ａと加算入力Ｂとを加算器１０１で加算してその加算結果（和）Ｓを得た後、比較器１０２によってその加算結果Ｓを基準値Ｒｅｆと比較し、その比較結果に基づき、セレクタ１０３によって加算結果Ｓもしくは飽和値Ｓａｔのどちらか一方を選択して出力する構成のものが知られている。
【００１２】
【発明が解決しようとする課題】
しかしながら、上述した従来の飽和加算装置では、飽和加算結果が得られるまでに「加算→比較→選択」という３つの段階を経る必要がある。ここで、入力数値のビット幅がｎビットのとき、高速な加算器、高速な比較器の遅延時間はそれぞれlog ｎに比例し、セレクタ１０３の遅延時間はビット幅ｎに依らず定数Ｃｓであると仮定すると、従来の飽和加算装置の総遅延時間は、（Ｋａ・２・log ｎ＋Ｃｓ；Ｋａは比例定数）と見積もることが出来る。すなわち、従来技術では、加算処理後に比較処理を行うため、遅延時間が増加し、高速演算に適さないという問題点がある。
【００１３】
本発明は、上記課題に鑑みてなされたものであり、その目的とするところは、飽和加算、飽和減算あるいは飽和乗算の演算処理において、高速演算の実現を可能とする３入力比較器を提供することにある。
【００１５】
【課題を解決するための手段】
本発明による３入力比較器は、ｎビット幅の３つの２進数（Ａ，Ｂ，Ｒｅｆ）を入力とし、その総和をｎビット幅の２つの２進数（Ｃｏ，Ｓ）に変換して出力する３：２コンプレッサ段と、この３：２コンプレッサ段から出力される２つの２進数（Ｃｏ，Ｓ）に基づいて３つの２進数（Ａ，Ｂ，Ｒｅｆ）の総和の値が非負であるか否かを判定する非負判定段とを備えた構成となっている。
【００１６】
そして、前記３：２コンプレッサ段は、２つの２進数（Ａ，Ｂ）をそのままビット毎に入力とするとともに、１つの２進数（Ｒｅｆ）をビット毎の否定をとって入力とするｎビット幅の３：２コンプレッサからなり、前記３つの２進数（Ａ，Ｂ，Ｒｅｆ）が２の補数表現による符号付き２進数のとき、前記非負判定段は、前記３：２コンプレッサ段のＳ出力の第（ｉ＋１）桁とＣｏ出力の第ｉ桁（ｎ−２≧ｉ≧０）を第（ｉ＋１）桁の入力とし、前記Ｓ出力の第０桁と論理“０”を第０桁の入力とし、前記Ｓ出力の第（ｎ−１）桁と前記Ｃｏ出力の第（ｎ−１）桁を第ｎ桁の入力とし、和出力の第ｎ桁Ｓｎを判定出力とする（ｎ＋１）ビット幅加算器からなり、前記前記（ｎ＋１）ビット幅加算器の和出力の第ｎ桁Ｓｎを判定出力とし、前記（ｎ＋１）ビット幅加算器は、その和出力の第ｎ桁Ｓｎの生成に関わる論理ゲートのみによって構成されている。
【００１７】
また、前記３：２コンプレッサ段は、２つの２進数（Ａ，Ｂ）をそのままビット毎に入力とするとともに、１つの２進数（Ｒｅｆ）をビット毎の否定をとって入力とするｎビット幅の３：２コンプレッサからなり、前記３つの２進数（Ａ，Ｂ，Ｒｅｆ）が２の補数表現による符号付き２進数のとき、前記非負判定段は、前記３：２コンプレッサ段のＳ出力の第（ｉ＋１）桁とＣｏ出力の第ｉ桁（ｎ−２≧ｉ≧０）を第（ｉ＋１）桁の入力とし、前記Ｓ出力の第０桁と第１機能選択入力を第０桁の入力とし、前記Ｓ出力の第（ｎ−１）桁と前記Ｃｏ出力の第（ｎ−１）桁を第ｎ桁の入力とする（ｎ＋１）ビット幅加算器と、前記（ｎ＋１）ビット幅加算器の和出力の第ｎ桁Ｓｎと第２機能選択入力を２入力とするＥＸ‐ＯＲゲートとからなり、前記ＥＸ‐ＯＲゲートの出力を判定出力とし、前記（ｎ＋１）ビット幅加算器は、その和出力の第ｎ桁Ｓｎの生成に関わる論理ゲートのみによって構成されている。
【００１８】
また、前記３：２コンプレッサ段は、２つの２進数（Ａ，Ｂ）をそのままビット毎に入力とするとともに、１つの２進数（Ｒｅｆ）をビット毎の否定をとって入力とするｎビット幅の３：２コンプレッサからなり、前記３つの２進数（Ａ，Ｂ，Ｒｅｆ）が符号無し２進数のとき、前記非負判定段は、前記３：２コンプレッサ段のＳ出力の第（ｉ＋１）桁とＣｏ出力の第ｉ桁（ｎ−２≧ｉ≧０）を第（ｉ＋１）桁の入力とし、前記Ｓ出力の第０桁と論理“０”を第０桁の入力とし、前記Ｃｏ出力の第（ｎ−１）桁と論理“１”を第ｎ桁の入力とし、桁上げ出力Ｃｏｕｔを判定出力とする（ｎ＋１）ビット幅加算器からなり、前記（ｎ＋１）ビット幅加算器の桁上げ出力Ｃｏｕｔを判定出力とし、前記（ｎ＋１）ビット幅加算器は、その桁上げ出力Ｃｏｕｔの生成に関わる論理ゲートのみによって構成されている。
【００１９】
また、前記３：２コンプレッサ段は、２つの２進数（Ａ，Ｂ）をそのままビット毎に入力とするとともに、１つの２進数（Ｒｅｆ）をビット毎の否定をとって入力とするｎビット幅の３：２コンプレッサからなり、前記３つの２進数（Ａ，Ｂ，Ｒｅｆ）が符号無し２進数のとき、前記非負判定段は、前記３：２コンプレッサ段のＳ出力の第（ｉ＋１）桁とＣｏ出力の第ｉ桁（ｎ−２≧ｉ≧０）を第（ｉ＋１）桁の入力とし、前記Ｓ出力の第０桁と第１機能選択入力を第０桁の入力とし、前記Ｃｏ出力の第（ｎ−１）桁と論理“１”を第ｎ桁の入力とする（ｎ＋１）ビット幅加算器と、前記（ｎ＋１）ビット幅加算器の桁上げ出力Ｃｏｕｔと第２機能選択入力を２入力とするＥＸ‐ＯＲゲートとからなり、前記ＥＸ‐ＯＲゲートの出力を判定出力し、前記（ｎ＋１）ビット幅加算器は、その桁上げ出力Ｃｏｕｔの生成に関わる論理ゲートのみによって構成されている。
【００２０】
また、前記３：２コンプレッサ段は、２つの２進数（Ａ，Ｂ）をそのままビット毎に入力とするとともに、１つの２進数（Ｒｅｆ）をビット毎の否定をとって入力とするｎビット幅の３：２コンプレッサからなり、前記３つの２進数（Ａ，Ｂ，Ｒｅｆ）が２の補数表現による符号付き２進数、あるいは符号無し２進数のとき、前記非負判定段は、前記Ｓ出力の第（ｎ−１）桁と第３機能選択入力を２入力とするＯＲゲートと、前記３：２コンプレッサ段のＳ出力の第（ｉ＋１）桁とＣｏ出力の第ｉ桁（ｎ−２≧ｉ≧０）を第（ｉ＋１）桁の入力とし、前記Ｓ出力の第０桁と第１機能選択入力を第０桁の入力とし、前記Ｃｏ出力の第（ｎ−１）桁と前記ＯＲゲートの出力を第ｎ桁の入力とする（ｎ＋１）ビット幅加算器と、前記第３機能選択入力が“１”のとき前記（ｎ＋１）ビット幅加算器の桁上げ出力Ｃｏｕｔを、“０”のとき前記（ｎ＋１）ビット幅加算器の和出力の第ｎ桁Ｓｎの否定をそれぞれ選択するセレクタと、前記セレクタの選択結果の否定と第２機能選択入力を２入力とするＥＸ‐ＯＲゲートとからなり、前記ＥＸ‐ＯＲゲートの出力を判定出力とし、前記（ｎ＋１）ビット幅加算器は、その桁上げ出力Ｃｏｕｔと和出力および第ｎ桁Ｓｎの生成に関わる論理ゲートのみによって構成されている。
【００２１】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照しつつ詳細に説明する。
【００２２】
図１は、本発明の第１実施形態を示すブロック図であり、基準値Ｒｅｆが１つの場合、即ち上限／下限値のいずれかを指定可能な飽和加算装置に適用した場合を示している。
【００２３】
第１実施形態に係る飽和加算装置は、ｎビットの２つの入力Ａ，Ｂの加算を行う加算器１１と、この加算器１１に対して並列に設けられ、２つの入力Ａ，Ｂの加算結果がｎビットの基準値Ｒｅｆで定められる範囲を逸脱しているか否かを判定する３入力比較器１２と、この３入力比較器１２の１ビットの比較結果に基づいて加算器１１の加算結果とｎビットの飽和値Ｓａｔのいずれか一方を選択して出力するセレクタ１３とから構成されている。
【００２４】
上記構成の第１実施形態に係る飽和加算装置において、基準値Ｒｅｆおよび飽和値Ｓａｔは、外部にて任意に設定可能である。ここで、入力数値のビット幅がｎビットの場合、加算器１１および３入力比較器１２の遅延時間はどちらもlog ｎに比例し、両者の遅延時間はほぼ同等である。
【００２５】
したがって、加算器１１に対して３入力比較器１２を並列に配置し、加算と比較を並列処理することにより、セレクタ１３の遅延時間はビット幅ｎに依らず定数Ｃｓと仮定すると、本実施形態に係る飽和加算装置の総遅延時間は、（Ｋｂ・log ｎ＋Ｃｓ；Ｋｂは比例定数）となり、従来の飽和加算装置の総遅延時間（Ｋａ・２・log ｎ＋Ｃｓ；Ｋａは比例定数）と比べ約２倍高速となり、高速動作が可能となる。但し、比例定数Ｋａと比例定数Ｋｂはほぼ同じで、定数Ｃｓは加算器１１の遅延時間に比べて十分小さいものと仮定する。
【００２６】
ここで、３入力比較器１１の原理について説明する。今、２つの入力Ａ，Ｂの加算結果Ｓｕｍ（＝Ａ＋Ｂ）と基準値Ｒｅｆの不等式
Ｓｕｍ≧Ｒｅｆ    …（１）
の判定を考える。この不等式（１）を次式のように変形する。
Ａ＋Ｂ≧Ｒｅｆ
Ａ＋Ｂ＋（−Ｒｅｆ）≧０    …（２）
【００２７】
（２）式から明らかなように、（１）式の不等式の評価というものは、３変数（Ａ，Ｂ，−Ｒｅｆ）の加算結果が非負か否かの評価に等しい。すなわち、加算結果Ｓｕｍ（＝Ａ＋Ｂ）と基準値Ｒｅｆの比較を行うことは、３変数の加算結果の符号を調べることと等しい。３変数の加算は、３：２（３入力２出力）コンプレッサを用いることによって、ビット幅ｎに依存せず定数段（通常、ＥＸ‐ＯＲゲート２段）で、２変数の加算に置き換えることが出来る。
【００２８】
２変数の加算は、一般に用いられている加算器を用いる。但し、ここで必要なのは計算結果が非負か否かを知ることであり、符号ビット（和の最上位ビットＭＳＢ）を求めることである。全ての和を求める必要はないので、符号ビットの生成に関わらない論理ゲートを除去し、単純化された加算器を用いる。回路の単純さから、通常の加算器よりも若干高速となる。このため、３：２コンプレッサ段で生じる遅延を相殺することが可能となる。
【００２９】
この非負か否かを判定する加算器が、Ｓｕｍ（＝Ａ＋Ｂ）を求める加算器と同等な速度を持つものならば、不等式（２）の評価結果と加算結果Ｓｕｍを同時に得ることが出来る。すなわち、基準値を越えたか否かの判定（不等式（２）の評価）と加算を並列に行うことが出来る。この後、一般的なセレクタを用いることによって、不等式（２）の評価に基づき加算結果あるいは飽和値のいずれかを出力する。このようにすることによって、任意基準値・任意飽和値を指定可能な高速飽和加算装置を実現出来ることになる。
【００３０】
本実施形態に係る飽和加算装置は、先述したように、基準値Ｒｅｆを越えたか否かの判定処理（不等式（２）の評価）と加算処理を並行して行うことにより、従来の飽和加算装置よりも高速に飽和演算を行うことを特徴とするものである。そして、その主たる構成要素は、図１から明らかなように、２入力Ａ，Ｂを加算する加算器１１と、（２）式を評価する３入力比較器１２と、セレクタ１３である。加算器１１およびセレクタ１３としては、従来より用いられている一般的なものを用いて良い。
【００３１】
本発明の独自な点であり、高速飽和演算装置を実現する技術の核心は、（２）式を評価するための３入力比較器１２にある。この３入力比較器１２は、後述するように、基本的に、「３：２コンプレッサ段」と「非負判定段」の２つの構成要素からなる。
【００３２】
ところで、上述した３入力比較器１２の原理説明では、
Ａ＋Ｂ≧Ｒｅｆ
という不等式の評価を行うとした。しかしこれを実現する論理回路は、後述するように、その回路の一部を若干変更することによって、
Ａ＋Ｂ＞Ｒｅｆ
という不等式の評価を行う３入力比較器に作り替えることが出来る。また、この不等式について、符号付き／符号無し２進数、双方における３入力比較器も簡単に作ることが出来る。
【００３３】
ここでは、話を簡単にするため、２の補数表示を用いた符号付き２進数における、Ａ＋Ｂ≧Ｒｅｆの不等式評価を行う３入力比較器の構成について説明するものとする。
【００３４】
先ず、３：２コンプレッサ段について説明する。３：２コンプレッサ段は、３変数の加算（Ａ＋Ｂ＋Ｃ）を２つの２進数Ｄ，Ｅの加算（Ｄ＋２×Ｅ）（“２×Ｅ”はビットシフトを意味し、実質的に加算である）に置き換える機能を持つ。具体的には、入力された３つの２進数の各ビット位置における“１”の数を出力するものである。
【００３５】
例えば、
0003675111.tif 000002
【００３６】
上のように、入力Ａ，Ｂ，Ｃの各桁の“１”の数が、Ｅ，Ｄの各桁のビットをペアとして２進数で表現される。ＤとＥから（Ａ＋Ｂ＋Ｃ）の和を得るには、Ｄに対してＥを１桁左にずらして加算を行う（即ち、Ｄ＋２×Ｅ）。例えば、
D  = P  0  1  0  1  0
E  = 0  0  1  1  0  Q
ここで空欄“Ｐ”に符号拡張するように符号を補い、また空欄“Ｑ”に０を補って、
0003675111.tif 000003
この結果は、（Ａ＋Ｂ＋Ｃ）＝１４＋６＋２＝２２に等しい。
【００３７】
このような３：２コンプレッサ処理を行う演算器としては、キャリー・セーブ（Carry Save）方式加算器が一般的に知られている。このキャリー・セーブ方式加算器とは、１ビット全加算器を必要なビット幅分並列に並べたものである。個々の全加算器は互いに接続されておらず、全く独立している。
【００３８】
１ビット全加算器の真理値表は、入力数値Ａ，Ｂ、桁上げ入力Ｃｉ、桁上げ出力Ｃｏ、和Ｓｕｍとしたとき、表１のようになる。
【表１】
0003675111.tif 000004
【００３９】
この真理値表から、Ａ，Ｂ，Ｃｉにおける“１”の数が、Ｃｏ，Ｓｕｍをペアとして２進数で表現されていることが明らかである。全加算器の論理構成としては様々なものが知られているが、その遅延はＥＸ‐ＯＲゲート２段程度である。このような全加算器を用いることによって、３つの変数の加算（Ａ＋Ｂ＋Ｃ）を２つの変数の加算（Ｄ＋２×Ｅ）に置き換える、即ち３：２コンプレッサ処理が出来る。
【００４０】
３：２コンプレッサ段の遅延は１つの全加算器の遅延に等しく、入力数値Ａ，Ｂ，Ｃのビット幅ｎに依存しない。なぜなら、入力数値のビット幅分ある全加算器は相互に接続されておらず、各全加算器は全く独立に動作するからである。したがって、３：２コンプレッサ段の遅延は、常に定数（全加算器１個の遅延）である。
【００４１】
今、実現しようとしている演算は、（２）式のＡ＋Ｂ＋（−Ｒｅｆ）≧０の評価である。ＡとＢはそのままキャリー・セーブ方式加算器に加える。しかし、基準値Ｒｅｆは２の補数を取って符号を反転する必要がある。２の補数は全ビットを反転した後、１を加えることによって得られる。すなわち、反転Ｒｅｆを〜Ｒｅｆで表すものとすると、−Ｒｅｆ＝〜Ｒｅｆ＋１となる。
【００４２】
本発明のポイントの１つは、この基準値Ｒｅｆの２の補数を求める過程を３：２コンプレッサ段の前後で分けた点にある。通常の方法で２の補数を求めようとすると、＋１を行う段階で桁上げ伝搬が発生し、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
ならば、空欄“Ｐ”に符号拡張するように符号を補い、空欄“Ｑ”に１を補って（２の補数を得る“＋１”に相当）、
0003675111.tif 000005
となり、結果は非負（ＭＳＢ＝０）である。
【００４８】
先述した例では、空欄“Ｑ”には０を補った。ここでは、Ｒｅｆの２の補数のための“＋１”を実現するため、空欄“Ｑ”に１を補う。これは、図３中の（ｎ＋１）ビット幅加算器３１の入力端子Ａ０に１を入力することで実現できる。このように、Ｒｅｆの２の補数を得るために必要な“＋１”が、ハードウェアおよび遅延時間を増加させることなく実現できる。
【００４９】
以下、３入力比較器の構成の具体例について説明する。図４は、３入力比較器の第１具体例を示すブロック図である。この第１具体例に係る３入力比較器は、図２の３：２コンプレッサ段２０と図３の非負判定段３０とからなり、全加算器２１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 端子に機能選択入力Ｓ０を与えるとともに、（ｎ＋１）ビット幅加算器３１のＳｎ出力と機能選択入力Ｓ１をＥＸ‐ＯＲゲート４１の２入力とし、このＥＸ‐ＯＲゲート４１の出力を比較結果出力として導出する構成となっている。
【００５７】
上記構成の第３具体例に係る３入力比較器は、機能選択入力Ｓ１，Ｓ０によって評価する不等式を選択することが可能な符号付き機能選択型３入力比較器である。すなわち、機能選択入力Ｓ０は、（ｎ＋１）ビット幅加算器３１のＡ０入力であって、“Ａ＋Ｂ−１≧Ｒｅｆ”か“Ａ＋Ｂ−１＞Ｒｅｆ”を選択するためのものである。また、機能選択入力Ｓ１は、各不等式の評価結果が“真”のときには“１”、“偽”のときには“０”と表現されるように、非負判定段３０の出力を適宜反転／非反転するためのものである。
【００５８】
機能選択入力Ｓ１，Ｓ０と評価する不等式の対応関係を表２に示す。
【表２】
0003675111.tif 000006
【００５９】
ところで、上述した第１〜第３具体例では、Ａ，Ｂ，Ｒｅｆが２の補数表示された符号付き２進数であると仮定し、３入力比較器を構成した場合を例にとって示した。この第１〜第３具体例に係る３入力比較器に対して符号無し２進数を入力した場合、その結果は正しいものとはならない。
【００６０】
例えば、Ａ＝１１１１，Ｂ＝１１１１，Ｒｅｆ＝１１１１のとき、これを符号付き２進数と受け取れば、Ａ＝−１，Ｂ＝−１，Ｒｅｆ＝−１であり、Ａ＋Ｂ＜Ｒｅｆが成立する。一方、符号無し２進数と見た場合、Ａ＝１５，Ｂ＝１５，Ｒｅｆ＝１５であり、Ａ＋Ｂ＜Ｒｅｆではない。
【００６１】
一般に、符号無し２進数は、そのＭＳＢ側に“０”を拡張（符号拡張）することにより、符号付き２進数の処理系で正の数値として正しく扱われる。符号拡張を行ったＡ，Ｂ，Ｒｅｆについて、符号付き２進数の３入力比較の行程を適応した例を以下に示す。
0003675111.tif 000007
【００６２】
0003675111.tif 000008
結果は＋１５であり、非負である。
【００６３】
ここに示した過程をそのままハードウェアで実現すると、符号拡張を行ったため、（ｎ＋２）ビット幅加算器が必要となる。これは符号付きの場合に比べて１ビット分多い。しかし、最上位ビットが明示的に定まっていることを利用して、（ｎ＋１）ビット幅加算器を用いることが出来る。具体的には、以下に示すように、Ａ，Ｂ，Ｒｅｆがどんな値であっても、Ｄ，Ｅの最上位ビットはＤが１で、Ｅが０であることを利用する。
【００６４】
0003675111.tif 000009
【００６５】
0003675111.tif 000010
【００６６】
ここで、Ｆの符号ビットＳは、以下のようにして求められる。
Ｓ＝０（＋）１（＋）（“Ｄ′の第４〜第０ビット＋Ｅ′の第４〜第０ビット”の桁上げ）
＝〜（“Ｄ′の第４〜第０ビット＋Ｅ′の第４〜第０ビット”の桁上げ）
すなわち、結果Ｆの符号を求めるには、“Ｄ′の第４〜第０ビットとＥ′の第４〜第０ビット”を加算したとき、桁上げ出力が有るか否かを求めれば良い。桁上げが１なら非負であり、０なら負であると解釈できる。ここに、（＋）とは、排他的論理和を示す演算記号である。
【００６７】
したがって、符号無し２進数の場合であっても、（ｎ＋１）ビット幅加算器で不等式の評価を行うことが出来る。この例でＤ′の第４ビットが常に“１”であることに注意して、（ｎ＋１）ビット幅加算器の入力Ｂ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 …インバータ
【図１】
0003675111.tif 000011
【図２】
0003675111.tif 000012
【図３】
0003675111.tif 000013
【図４】
0003675111.tif 000014
【図５】
0003675111.tif 000015
【図６】
0003675111.tif 000016
【図７】
0003675111.tif 000017
【図８】
0003675111.tif 000018
【図９】
0003675111.tif 000019
【図１０】
0003675111.tif 000020
【図１１】
0003675111.tif 000021
【図１２】
0003675111.tif 000022
【図１３】
0003675111.tif 000023
【図１４】
0003675111.tif 000024
【図１５】
0003675111.tif 000025