米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> ソニー株式会社

発明の名称 3入力比較器、並びにこれを用いた飽和演算装置およびその演算方法
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開平11−3210
公開日 平成11年(1999)1月6日
出願番号 特願平9−154631
出願日 平成9年(1997)6月12日
代理人 【弁理士】
【氏名又は名称】船橋 國則
発明者 平入 孝二
要約 目的


構成
特許請求の範囲
【請求項1】 nビット幅の3つの2進数(A,B,Ref)を入力とし、その総和をnビット幅の2つの2進数(Co,S)に変換して出力する3:2コンプレッサ段と、前記3:2コンプレッサ段から出力される前記2つの2進数(Co,S)に基づいて前記総和の値が非負であるか否かを判定する非負判定段とを備えたことを特徴とする3入力比較器。
【請求項2】 前記3:2コンプレッサ段は、2つの2進数(A,B)をそのままビット毎に入力とするとともに、1つの2進数(Ref)をビット毎の否定をとって入力とするnビット幅の3:2コンプレッサからなることを特徴とする請求項1記載の3入力比較器。
【請求項3】 前記3つの2進数(A,B,Ref)が2の補数表現による符号付き2進数のとき、前記非負判定段は、前記3:2コンプレッサ段のS出力の第(i+1)桁とCo出力の第i桁(n−2≧i≧0)を第(i+1)桁の入力とし、前記S出力の第0桁と論理“1”を第0桁の入力とし、前記S出力の第(n−1)桁と前記Co出力の第(n−1)桁を第n桁の入力とし、和出力の第n桁Snを判定出力とする(n+1)ビット幅加算器からなり、前記(n+1)ビット幅加算器の和出力の第n桁Snを判定出力とすることを特徴とする請求項2記載の3入力比較器。
【請求項4】 前記(n+1)ビット幅加算器は、その和出力の第n桁Snの生成に関わる論理ゲートのみによって構成されていることを特徴とする請求項3記載の3入力比較器。
【請求項5】 前記3つの2進数(A,B,Ref)が2の補数表現による符号付き2進数のとき、前記非負判定段は、前記3:2コンプレッサ段のS出力の第(i+1)桁とCo出力の第i桁(n−2≧i≧0)を第(i+1)桁の入力とし、前記S出力の第0桁と論理“0”を第0桁の入力とし、前記S出力の第(n−1)桁と前記Co出力の第(n−1)桁を第n桁の入力とし、和出力の第n桁Snを判定出力とする(n+1)ビット幅加算器からなり、前記前記(n+1)ビット幅加算器の和出力の第n桁Snを判定出力とすることを特徴とする請求項2記載の3入力比較器。
【請求項6】 前記(n+1)ビット幅加算器は、その和出力の第n桁Snの生成に関わる論理ゲートのみによって構成されていることを特徴とする請求項5記載の3入力比較器。
【請求項7】 前記3つの2進数(A,B,Ref)が2の補数表現による符号付き2進数のとき、前記非負判定段は、前記3:2コンプレッサ段のS出力の第(i+1)桁とCo出力の第i桁(n−2≧i≧0)を第(i+1)桁の入力とし、前記S出力の第0桁と第1機能選択入力を第0桁の入力とし、前記S出力の第(n−1)桁と前記Co出力の第(n−1)桁を第n桁の入力とする(n+1)ビット幅加算器と、前記(n+1)ビット幅加算器の和出力の第n桁Snと第2機能選択入力を2入力とするEX‐ORゲートとからなり、前記EX‐ORゲートの出力を判定出力とすることを特徴とする請求項2記載の3入力比較器。
【請求項8】 前記(n+1)ビット幅加算器は、その和出力の第n桁Snの生成に関わる論理ゲートのみによって構成されていることを特徴とする請求項7記載の3入力比較器。
【請求項9】 前記3つの2進数(A,B,Ref)が符号無し2進数のとき、前記非負判定段は、前記3:2コンプレッサ段のS出力の第(i+1)桁とCo出力の第i桁(n−2≧i≧0)を第(i+1)桁の入力とし、前記S出力の第0桁と論理“1”を第0桁の入力とし、前記Co出力の第(n−1)桁と論理“1”を第n桁の入力とし、桁上げ出力Coutを判定出力とする(n+1)ビット幅加算器からなり、前記(n+1)ビット幅加算器の桁上げ出力Coutを判定出力とすることを特徴とする請求項2記載の3入力比較器。
【請求項10】 前記(n+1)ビット幅加算器は、その桁上げ出力Coutの生成に関わる論理ゲートのみによって構成されていることを特徴とする請求項9記載の3入力比較器。
【請求項11】 前記3つの2進数(A,B,Ref)が符号無し2進数のとき、前記非負判定段は、前記3:2コンプレッサ段のS出力の第(i+1)桁とCo出力の第i桁(n−2≧i≧0)を第(i+1)桁の入力とし、前記S出力の第0桁と論理“0”を第0桁の入力とし、前記Co出力の第(n−1)桁と論理“1”を第n桁の入力とし、桁上げ出力Coutを判定出力とする(n+1)ビット幅加算器からなり、前記(n+1)ビット幅加算器の桁上げ出力Coutを判定出力とすることを特徴とする請求項2記載の3入力比較器。
【請求項12】 前記(n+1)ビット幅加算器は、その桁上げ出力Coutの生成に関わる論理ゲートのみによって構成されていることを特徴とする請求項11記載の3入力比較器。
【請求項13】 前記3つの2進数(A,B,Ref)が符号無し2進数のとき、前記非負判定段は、前記3:2コンプレッサ段のS出力の第(i+1)桁とCo出力の第i桁(n−2≧i≧0)を第(i+1)桁の入力とし、前記S出力の第0桁と第1機能選択入力を第0桁の入力とし、前記Co出力の第(n−1)桁と論理“1”を第n桁の入力とする(n+1)ビット幅加算器と、前記(n+1)ビット幅加算器の桁上げ出力Coutと第2機能選択入力を2入力とするEX‐ORゲートとからなり、前記EX‐ORゲートの出力を判定出力とすることを特徴とする請求項2記載の3入力比較器。
【請求項14】 前記(n+1)ビット幅加算器は、その桁上げ出力Coutの生成に関わる論理ゲートのみによって構成されていることを特徴とする請求項13記載の3入力比較器。
【請求項15】 前記3つの2進数(A,B,Ref)が2の補数表現による符号付き2進数、あるいは符号無し2進数のとき、前記非負判定段は、前記S出力の第(n−1)桁と第3機能選択入力を2入力とするORゲートと、前記3:2コンプレッサ段のS出力の第(i+1)桁とCo出力の第i桁(n−2≧i≧0)を第(i+1)桁の入力とし、前記S出力の第0桁と第1機能選択入力を第0桁の入力とし、前記Co出力の第(n−1)桁と前記ORゲートの出力を第n桁の入力とする(n+1)ビット幅加算器と、前記第3機能選択入力が“1”のとき前記(n+1)ビット幅加算器の桁上げ出力Coutを、“0”のとき前記(n+1)ビット幅加算器の和出力の第n桁Snの否定をそれぞれ選択するセレクタと、前記セレクタの選択結果の否定と第2機能選択入力を2入力とするEX‐ORゲートとからなり、前記EX‐ORゲートの出力を判定出力とすることを特徴とする請求項2記載の3入力比較器。
【請求項16】 前記(n+1)ビット幅加算器は、その桁上げ出力Coutと和出力および第n桁Snの生成に関わる論理ゲートのみによって構成されていることを特徴とする請求項15記載の3入力比較器。
【請求項17】 2つの入力の加算又は減算を行う演算器と、前記演算器に対して並列に設けられ、前記演算器の演算結果が所定の基準値で定められる範囲を逸脱しているか否かを判定する3入力比較器と、前記3入力比較器の判定結果に基づいて前記演算器の演算結果と所定の飽和値のいずれか一方を選択して出力するセレクタとを備えたことを特徴とする飽和演算装置。
【請求項18】 前記3入力比較器は、nビット幅の3つの2進数(A,B,Ref)を入力とし、その総和をnビット幅の2つの2進数(Co,S)に変換して出力する3:2コンプレッサ段と、前記3:2コンプレッサ段から出力される前記2つの2進数(Co,S)に基づいて前記総和の値が非負であるか否かを判定する非負判定段とを有することを特徴とする請求項17記載の飽和演算装置。
【請求項19】 前記3入力比較器は複数個並列に設けられ、前記演算器の演算結果が複数の基準値で定められる範囲を逸脱しているか否かを判定することを特徴とする請求項17記載の飽和演算装置。
【請求項20】 桁上げ伝搬保存又は冗長2進数の演算部と、前記演算部から出力される2つの2進数の加算又は減算を行う最終段演算器とからなり、2つの入力の乗算、あるいは3以上の入力を持つ複合演算を行う演算手段と、前記最終段演算器に対して並列に設けられ、前記最終段演算器の演算結果が所定の基準値で定められる範囲を逸脱しているか否かを判定する3入力比較器と、前記3入力比較器の判定結果に基づいて前記最終段演算器の演算結果と所定の飽和値のいずれか一方を選択して出力するセレクタとを備えたことを特徴とする飽和演算装置。
【請求項21】 前記3入力比較器は、nビット幅の3つの2進数(A,B,Ref)を入力とし、その総和をnビット幅の2つの2進数(Co,S)に変換して出力する3:2コンプレッサ段と、前記3:2コンプレッサ段から出力される前記2つの2進数(Co,S)に基づいて前記総和の値が非負であるか否かを判定する非負判定段とを有することを特徴とする請求項20記載の飽和演算装置。
【請求項22】 前記3入力比較器は複数個並列に設けられ、前記最終段演算器の演算結果が複数の基準値で定められる範囲を逸脱しているか否かを判定することを特徴とする請求項20記載の飽和演算装置。
【請求項23】 2つの入力の加算又は減算を行い、その演算結果が所定の基準値で定められる範囲を逸脱しているとき、その演算結果を所定の飽和値と置換して出力する飽和演算方法であって、前記2つの入力の演算処理と、前記2つの入力の演算結果が所定の基準値で定められる範囲を逸脱しているか否かの判定処理とを並行して実行し、前記判定処理の判定結果に基づいて前記演算処理の演算結果と前記飽和値のいずれか一方を選択して出力することを特徴とする飽和演算方法。
発明の詳細な説明
【0001】
【発明の属する技術分野】本発明は、半導体集積回路におけるデジタル演算装置、特に飽和演算装置に関する。
【0002】ここで言う飽和演算装置とは、ある演算を行った結果値が、ある与えられた基準値(reference value :以降、単にRefと略す)で定められる範囲内の場合には演算結果値を出力し、当該範囲を越えた場合には与えられた飽和値(saturation value:以降、単にSatと略す)を出力する演算装置である。この飽和演算装置としては、飽和加算装置、飽和減算装置、飽和乗算装置などがある。
【0003】
【従来の技術】飽和演算装置の一種である例えば飽和加算装置は、加算結果が正の最大値を越えた場合には出力を正の最大値に補正し、負の最大値を越えた場合は出力を負の最大値に補正するものである。この一般的な飽和加算装置において、越えたか否かの基準となる値は、正の最大値・負の最大値に固定されており、任意の値を基準値にすることは出来ない。
【0004】ところで、飽和加算装置と言う場合、それは加算のオーバーフローによる飽和演算を指す。加算のオーバーフローとは、加算の結果値がその加算装置の出力のビット数で表現できる範囲を超えた場合に起こり、オーバーフロー・フラグとして表現される。すなわち、オーバーフローが起こったならば“1”、そうでないならば“0”というフラグ状態となる。
【0005】入出力する数値が符号無しの2進数の場合には、加算装置の桁上げ出力(キャリーアウト)がオーバーフローも意味している。しかし、入出力する数値が2の補数表現による符号有り2進数の場合には、桁上げ出力はオーバーフローを意味しない。例えば、入力が4ビット、出力が4ビットの加算を例に採る。
0111 + 0001 = 桁上げ出力0 , 数値1000のとき、符号無しの場合は7+1を意味し、結果は+8を意味している。結果は正しく、桁上げ出力は0であり、オーバーフローでない。一方、符号有りの場合は7+1を意味し、結果は−8を意味している。結果は誤りで、桁上げ出力は0であるが、オーバーフローである。
【0006】また、1001 + 1111 = 桁上げ出力1 , 数値1000のとき、符号無しの場合は9+15を意味し、結果は8である。結果は誤りで、桁上げ出力が1であり、オーバーフローである。符号有りの場合は−7+(−1)を意味し、結果は−8を意味している。結果は正しく、桁上げ出力は1であるが、オーバーフローではない。
【0007】以上のように、入出力する数値が符号無しか、符号付きかによって、オーバーフローの検出の仕方は異なる。符号付きの場合、普通の加算器の内部に簡単な回路を付加することによって、オーバーフロー・フラグを作ることが出来る。桁上げ出力とオーバーフロー・フラグは加算の終了とともに出力される。結局、符号無し/符号付きのいずれの場合であっても、オーバーフローか否かは、加算結果と同時に判明する。
【0008】飽和加算装置の出力がnビットのとき、加算結果値が符号無しの場合に2n 以上、符号有りの場合に2n-1 以上、又は−(2n-1 +1) 以下でオーバーフローが起こる。飽和加算装置での飽和加算は、このオーバーフローに基づいて行われる。例えば、(0111+0001)の演算のとき、符号無しの場合はオーバーフローではないので、加算結果1000 (8)を出力する。符号有りの場合はオーバーフローなので、飽和値0111 (7)を出力する。また、(1001+1111)の演算のとき、符号無しの場合はオーバーフローなので、飽和値1111 (15) を出力する。符号有りの場合はオーバーフローではないので、加算結果 1000 (-8)を出力する。
【0009】通常はオーバーフローが起こる境界の値、即ち正の最大値か、負の最大値を飽和値とする。しかしながら、従来の飽和加算装置においては、正の最大値あるいは負の最大値以外の数値を基準値として、これを越えた場合を判定することは原理的に不可能である。なぜなら、加算結果が最大値でない基準値を逸脱したとしても、オーバーフローが起こらないからである。
【0010】ところで、コンピュータによって、ディスプレイ上の任意の矩形領域内の描画を行う場合、任意基準値・任意飽和値の飽和演算が頻繁に行われる。例えば、ある図形をディスプレイ上の矩形領域内に描画するとき、その領域をはみ出す部分は描画しないように処理する必要がある。このときの描画座標の計算過程においては、常に、X,Y座標が領域内であるか否かの判定と、領域を越えた場合には境界値に補正する演算処理、即ち飽和演算が行われている。矩形領域が画面上のどこにあっても、このような境界値への補正を行うためには、基準値・飽和値をそれぞれ任意に指定可能な飽和加算装置が必要である。
【0011】従来、この基準値・飽和値をそれぞれ任意に指定可能な飽和加算を実現する飽和加算装置として、図15に示すように、加算入力Aと加算入力Bとを加算器101で加算してその加算結果(和)Sを得た後、比較器102によってその加算結果Sを基準値Refと比較し、その比較結果に基づき、セレクタ103によって加算結果Sもしくは飽和値Satのどちらか一方を選択して出力する構成のものが知られている。
【0012】
【発明が解決しようとする課題】しかしながら、上述した従来の飽和加算装置では、飽和加算結果が得られるまでに「加算→比較→選択」という3つの段階を経る必要がある。ここで、入力数値のビット幅がnビットのとき、高速な加算器、高速な比較器の遅延時間はそれぞれlog nに比例し、セレクタ103の遅延時間はビット幅nに依らず定数Csであると仮定すると、従来の飽和加算装置の総遅延時間は、(Ka・2・log n+Cs;Kaは比例定数)と見積もることが出来る。すなわち、従来技術では、加算処理後に比較処理を行うため、遅延時間が増加し、高速演算に適さないという問題点がある。
【0013】本発明は、上記課題に鑑みてなされたものであり、その目的とするところは、飽和加算、飽和減算あるいは飽和乗算の演算処理において、高速演算の実現を可能とする3入力比較器を提供することにある。
【0014】本発明はさらに、基準値・飽和値を任意に指定可能で、かつ高速演算に適した飽和演算装置およびその演算方法を提供することを目的とする。
【0015】
【課題を解決するための手段】本発明による3入力比較器は、nビット幅の3つの2進数(A,B,Ref)を入力とし、その総和をnビット幅の2つの2進数(Co,S)に変換して出力する3:2コンプレッサ段と、この3:2コンプレッサ段から出力される2つの2進数(Co,S)に基づいて3つの2進数(A,B,Ref)の総和の値が非負であるか否かを判定する非負判定段とを備えた構成となっている。
【0016】上記構成の3入力比較器では、“(A+B)≧Ref”,“(A+B)<Ref”,“(A+B)>Ref”,“(A+B)≦Ref”の4つの不等式の評価を行う。例えば、“(A+B)≧Ref”の評価が“(A+B)−Ref≧0”と等価であることに着目し、先ず、3:2コンプレッサ段で左辺(A+B)−Refの値を2つの2進数に変換し、次いでこの2つの2進数に基づいて非負判定段で不等式の真偽を決定する。
【0017】本発明による飽和演算装置は、2つの入力の加算又は減算を行う演算器(加算器/減算器)を有する飽和演算装置、もしくは桁上げ伝搬保存又は冗長2進数の演算部と、この演算部から出力される2つの2進数の加算又は減算を行う最終段演算器とからなり、2つの入力の乗算、あるいは3以上の入力を持つ複合演算を行う演算手段を有する飽和演算装置であって、演算器又は最終段演算器に対して並列に設けられ、この演算器又は最終段演算器の演算結果が所定の基準値で定められる範囲を逸脱しているか否かを判定する3入力比較器と、この3入力比較器の判定結果に基づいて演算器又は最終段演算器の演算結果と所定の飽和値のいずれか一方を選択して出力するセレクタとを備えた構成となっている。
【0018】上記構成の飽和演算(加算/減算/乗算)装置において、3入力比較器は、演算器又は最終段演算器による演算処理と並行して2つの入力の演算結果が所定の基準値で定められる範囲を逸脱しているか否かの判定を行う。そして、セレクタは、2つの入力の演算結果が所定の基準値で定められる範囲内であれば演算器又は最終段演算器の演算結果を選択し、当該範囲を逸脱していれば所定の飽和値を選択する。すなわち、演算処理と比較処理とを並行して行うことで、「演算/比較→選択」の2つの段階で飽和演算が行われる。
【0019】本発明による飽和演算方法は、2つの入力の加算又は減算を行い、その演算結果が所定の基準値で定められる範囲を逸脱しているとき、その演算結果を所定の飽和値と置換して出力する飽和演算方法であって、2つの入力の演算処理と、2つの入力の演算結果が所定の基準値で定められる範囲を逸脱しているか否かの判定処理とを並行して実行し、この判定処理の判定結果に基づいて演算処理の演算結果と所定の飽和値のいずれか一方を選択して出力する。
【0020】飽和演算処理において、2つの入力の演算結果が所定の基準値で定められる範囲を逸脱しているか否かの判定を演算処理と並行して行い、当該範囲内であれば演算結果を選択し、当該範囲を逸脱していれば所定の飽和値を選択することで、「演算/比較→選択」の2つの段階で飽和演算が行われる。
【0021】
【発明の実施の形態】以下、本発明の実施の形態について図面を参照しつつ詳細に説明する。
【0022】図1は、本発明の第1実施形態を示すブロック図であり、基準値Refが1つの場合、即ち上限/下限値のいずれかを指定可能な飽和加算装置に適用した場合を示している。
【0023】第1実施形態に係る飽和加算装置は、nビットの2つの入力A,Bの加算を行う加算器11と、この加算器11に対して並列に設けられ、2つの入力A,Bの加算結果がnビットの基準値Refで定められる範囲を逸脱しているか否かを判定する3入力比較器12と、この3入力比較器12の1ビットの比較結果に基づいて加算器11の加算結果とnビットの飽和値Satのいずれか一方を選択して出力するセレクタ13とから構成されている。
【0024】上記構成の第1実施形態に係る飽和加算装置において、基準値Refおよび飽和値Satは、外部にて任意に設定可能である。ここで、入力数値のビット幅がnビットの場合、加算器11および3入力比較器12の遅延時間はどちらもlognに比例し、両者の遅延時間はほぼ同等である。
【0025】したがって、加算器11に対して3入力比較器12を並列に配置し、加算と比較を並列処理することにより、セレクタ13の遅延時間はビット幅nに依らず定数Csと仮定すると、本実施形態に係る飽和加算装置の総遅延時間は、(Kb・log n+Cs;Kbは比例定数)となり、従来の飽和加算装置の総遅延時間(Ka・2・log n+Cs;Kaは比例定数)と比べ約2倍高速となり、高速動作が可能となる。但し、比例定数Kaと比例定数Kbはほぼ同じで、定数Csは加算器11の遅延時間に比べて十分小さいものと仮定する。
【0026】ここで、3入力比較器11の原理について説明する。今、2つの入力A,Bの加算結果Sum(=A+B)と基準値Refの不等式Sum≧Ref …(1)
の判定を考える。この不等式(1)を次式のように変形する。
A+B≧RefA+B+(−Ref)≧0 …(2)
【0027】(2)式から明らかなように、(1)式の不等式の評価というものは、3変数(A,B,−Ref)の加算結果が非負か否かの評価に等しい。すなわち、加算結果Sum(=A+B)と基準値Refの比較を行うことは、3変数の加算結果の符号を調べることと等しい。3変数の加算は、3:2(3入力2出力)コンプレッサを用いることによって、ビット幅nに依存せず定数段(通常、EX‐ORゲート2段)で、2変数の加算に置き換えることが出来る。
【0028】2変数の加算は、一般に用いられている加算器を用いる。但し、ここで必要なのは計算結果が非負か否かを知ることであり、符号ビット(和の最上位ビットMSB)を求めることである。全ての和を求める必要はないので、符号ビットの生成に関わらない論理ゲートを除去し、単純化された加算器を用いる。回路の単純さから、通常の加算器よりも若干高速となる。このため、3:2コンプレッサ段で生じる遅延を相殺することが可能となる。
【0029】この非負か否かを判定する加算器が、Sum(=A+B)を求める加算器と同等な速度を持つものならば、不等式(2)の評価結果と加算結果Sumを同時に得ることが出来る。すなわち、基準値を越えたか否かの判定(不等式(2)の評価)と加算を並列に行うことが出来る。この後、一般的なセレクタを用いることによって、不等式(2)の評価に基づき加算結果あるいは飽和値のいずれかを出力する。このようにすることによって、任意基準値・任意飽和値を指定可能な高速飽和加算装置を実現出来ることになる。
【0030】本実施形態に係る飽和加算装置は、先述したように、基準値Refを越えたか否かの判定処理(不等式(2)の評価)と加算処理を並行して行うことにより、従来の飽和加算装置よりも高速に飽和演算を行うことを特徴とするものである。そして、その主たる構成要素は、図1から明らかなように、2入力A,Bを加算する加算器11と、(2)式を評価する3入力比較器12と、セレクタ13である。加算器11およびセレクタ13としては、従来より用いられている一般的なものを用いて良い。
【0031】本発明の独自な点であり、高速飽和演算装置を実現する技術の核心は、(2)式を評価するための3入力比較器12にある。この3入力比較器12は、後述するように、基本的に、「3:2コンプレッサ段」と「非負判定段」の2つの構成要素からなる。
【0032】ところで、上述した3入力比較器12の原理説明では、A+B≧Refという不等式の評価を行うとした。しかしこれを実現する論理回路は、後述するように、その回路の一部を若干変更することによって、A+B>Refという不等式の評価を行う3入力比較器に作り替えることが出来る。また、この不等式について、符号付き/符号無し2進数、双方における3入力比較器も簡単に作ることが出来る。
【0033】ここでは、話を簡単にするため、2の補数表示を用いた符号付き2進数における、A+B≧Refの不等式評価を行う3入力比較器の構成について説明するものとする。
【0034】先ず、3:2コンプレッサ段について説明する。3:2コンプレッサ段は、3変数の加算(A+B+C)を2つの2進数D,Eの加算(D+2×E)(“2×E”はビットシフトを意味し、実質的に加算である)に置き換える機能を持つ。具体的には、入力された3つの2進数の各ビット位置における“1”の数を出力するものである。
【0035】例えば、
【0036】上のように、入力A,B,Cの各桁の“1”の数が、E,Dの各桁のビットをペアとして2進数で表現される。DとEから(A+B+C)の和を得るには、Dに対してEを1桁左にずらして加算を行う(即ち、D+2×E)。例えば、D = P 0 1 0 1 0E = 0 0 1 1 0 Qここで空欄“P”に符号拡張するように符号を補い、また空欄“Q”に0を補って、
この結果は、(A+B+C)=14+6+2=22に等しい。
【0037】このような3:2コンプレッサ処理を行う演算器としては、キャリー・セーブ(Carry Save)方式加算器が一般的に知られている。このキャリー・セーブ方式加算器とは、1ビット全加算器を必要なビット幅分並列に並べたものである。個々の全加算器は互いに接続されておらず、全く独立している。
【0038】1ビット全加算器の真理値表は、入力数値A,B、桁上げ入力Ci、桁上げ出力Co、和Sumとしたとき、表1のようになる。
【表1】

【0039】この真理値表から、A,B,Ciにおける“1”の数が、Co,Sumをペアとして2進数で表現されていることが明らかである。全加算器の論理構成としては様々なものが知られているが、その遅延はEX‐ORゲート2段程度である。このような全加算器を用いることによって、3つの変数の加算(A+B+C)を2つの変数の加算(D+2×E)に置き換える、即ち3:2コンプレッサ処理が出来る。
【0040】3:2コンプレッサ段の遅延は1つの全加算器の遅延に等しく、入力数値A,B,Cのビット幅nに依存しない。なぜなら、入力数値のビット幅分ある全加算器は相互に接続されておらず、各全加算器は全く独立に動作するからである。したがって、3:2コンプレッサ段の遅延は、常に定数(全加算器1個の遅延)である。
【0041】今、実現しようとしている演算は、(2)式のA+B+(−Ref)≧0の評価である。AとBはそのままキャリー・セーブ方式加算器に加える。しかし、基準値Refは2の補数を取って符号を反転する必要がある。2の補数は全ビットを反転した後、1を加えることによって得られる。すなわち、反転Refを〜Refで表すものとすると、−Ref=〜Ref+1となる。
【0042】本発明のポイントの1つは、この基準値Refの2の補数を求める過程を3:2コンプレッサ段の前後で分けた点にある。通常の方法で2の補数を求めようとすると、+1を行う段階で桁上げ伝搬が発生し、log nに比例した遅延時間が生じてしまう。
【0043】そこで、本発明では、(〜Ref)を3:2コンプレッサ段の前で行い、(+1)を後の非負判定段で行う方法をとる。つまり、基準値Refが入力されるキャリー・セーブ方式加算器の入力端子にはNOTゲート(インバータ)を付加する。後述するように、非負判定段で+1を行うようにすると、遅延・ゲートが全く増加しない。3:2コンプレッサ段で行う演算は本質的に加算であり、+1もまた加算である。したがって、演算の対称性・加算の交換則から、3:2コンプレッサ処理を行った後で+1を行っても差し支えない。
【0044】3:2コンプレッサ段の構成を図2に示す。同図から明らかなように、3:2コンプレッサ段20は、入力数値のビット幅がnビットの場合、n個の全加算器210 〜21n-1 と、これら全加算器210 〜21n-1 の各Ci入力端子に接続されたインバータ(NOTゲート)220 〜22n-1 とから構成されている。そして、2つの入力A0 〜An-1 ,B0 〜Bn-1 の各ビットを全加算器210 〜21n-1 の各A,B入力、インバータ220 〜22n-1 で反転された基準値Ref0 〜Refn-1 の各ビットを全加算器210 〜21n-1 の各Ci入力とし、全加算器210 〜21n-1 の各Co出力およびS出力を2の出力E0 〜En-1 ,D0〜Dn-1 とする。
【0045】次に、非負判定段について説明する。非負判定段の構成を図3に示す。非負判定段30は、和Snを生成する(n+1)ビット幅加算器31によって構成されている。この非負判定段30では、3:2コンプレッサ段20において得られたD,Eについて、Refの2の補数(+1)を得るために(D+2×E+1)の演算処理を行い、その演算結果が非負か否かについて判定を行う。
【0046】ある加算結果が非負であるか否かを知るには、加算出力Snの符号ビット(MSB)を参照すればよい。符号ビットが“0”ならば非負であり、“1”ならば負である。符号ビット以外の出力は求める必要がない。したがって、図3から明らかなように、和SnのMSB生成に関わらない論理ゲートを削除した加算器31が用いられている。
【0047】ここで、非負判定段30で行われる計算の例を示す。
D = P 1 1 0 1 0E = 0 1 1 0 0 Qならば、空欄“P”に符号拡張するように符号を補い、空欄“Q”に1を補って(2の補数を得る“+1”に相当)、
となり、結果は非負(MSB=0)である。
【0048】先述した例では、空欄“Q”には0を補った。ここでは、Refの2の補数のための“+1”を実現するため、空欄“Q”に1を補う。これは、図3中の(n+1)ビット幅加算器31の入力端子A0に1を入力することで実現できる。このように、Refの2の補数を得るために必要な“+1”が、ハードウェアおよび遅延時間を増加させることなく実現できる。
【0049】以下、3入力比較器の構成の具体例について説明する。図4は、3入力比較器の第1具体例を示すブロック図である。この第1具体例に係る3入力比較器は、図2の3:2コンプレッサ段20と図3の非負判定段30とからなり、全加算器210 〜21n-2 の各S端子が(n+1)ビット幅加算器31のB0 〜Bn-2 端子にビット対応で接続されかつ全加算器21n-1 のS端子が(n+1)ビット幅加算器31のBn-1 端子およびBn 端子にそれぞれ接続されるとともに、全加算器210 〜21n-1 の各Co端子が(n+1)ビット幅加算器31の1ビット上位のA1 〜An 端子にそれぞれ接続されかつ最下位ビットのA0 端子に論理“1”が与えられ、(n+1)ビット幅加算器31のSn出力を比較結果出力として導出する構成となっている。
【0050】上記構成の第1具体例に係る3入力比較器では、不等式“A+B≧Ref”又は“A+B<Ref”(A,B,Refは符号付き2進数)の評価が行われる。この3入力比較器の比較結果出力は以下のように解釈できる。すなわち、比較結果出力が“0”の場合は、“A+B+(−Ref)≧0”、即ち“A+B≧Ref”である。比較結果出力が“1”の場合は、“A+B+(−Ref)<0”、即ち“A+B<Ref”である。
【0051】図5は、3入力比較器の第2具体例を示すブロック図である。この第2具体例に係る3入力比較器は、第1具体例の場合と同様に、図2の3:2コンプレッサ段20と図3の非負判定段30とからなり、かつ全加算器210 〜21n-1 の各S,Co端子と(n+1)ビット幅加算器31のA0 〜An ,B0 〜Bn 端子の接続関係も第1具体例の場合と同じである。異なるのは、(n+1)ビット幅加算器31の最下位ビットのA0 端子に論理“0”が与えられている点である。
【0052】上記構成の第2具体例に係る3入力比較器では、不等式“A+B>Ref”又は“A+B≦Ref”(A,B,Refは符号付き2進数)の評価が行われる。この3入力比較器の比較結果出力は以下のように解釈できる。ここで、自明な次の命題を利用する。
【0053】「A+B>Refを満たす整数A,B,Refが存在するとき、必ず、A+B−1≧Refである。」
すなわち、不等式A+B>Ref …(3)
を評価することは、不等式A+B−1≧Ref …(4)
を評価することと等しい。したがって、不等式A+B+(−Ref)−1≧0 …(5)
を評価することを考えれば良い。
【0054】(5)式において、左辺の“−1”は実に単純な方法で実現できる。評価する不等式を以下のように変形する。
A+B+(−Ref)=(D+2×E+1)
より、A+B+(−Ref)−1≧0D+2×E≧0 …(6)
【0055】第1具体例では、“D+2×E+1”という演算を非負判定段30で行っている。すなわち、図4において、(n+1)ビット幅加算器31の最下位ビットのA0端子に論理“1”を与えることで、“+1”を実現している。これに対し、第2具体例では、(n+1)ビット幅加算器31の最下位ビットのA0 端子に論理“0”を与えることで、“D+2×E”という演算を非負判定段30で行うようにしている。
【0056】図6は、3入力比較器の第3具体例を示すブロック図である。この第3具体例に係る3入力比較器は、図2の3:2コンプレッサ段20、図3の非負判定段30およびEX‐ORゲート41からなるとともに、全加算器210 〜21n-1 の各S,Co端子と(n+1)ビット幅加算器31のA0 〜An ,B0 〜Bn 端子とが第1,第2具体例の場合と同じ接続関係にあり、加えて、(n+1)ビット幅加算器31の最下位ビットのA0 端子に機能選択入力S0を与えるとともに、(n+1)ビット幅加算器31のSn出力と機能選択入力S1をEX‐ORゲート41の2入力とし、このEX‐ORゲート41の出力を比較結果出力として導出する構成となっている。
【0057】上記構成の第3具体例に係る3入力比較器は、機能選択入力S1,S0によって評価する不等式を選択することが可能な符号付き機能選択型3入力比較器である。すなわち、機能選択入力S0は、(n+1)ビット幅加算器31のA0入力であって、“A+B−1≧Ref”か“A+B−1>Ref”を選択するためのものである。また、機能選択入力S1は、各不等式の評価結果が“真”のときには“1”、“偽”のときには“0”と表現されるように、非負判定段30の出力を適宜反転/非反転するためのものである。
【0058】機能選択入力S1,S0と評価する不等式の対応関係を表2に示す。
【表2】

【0059】ところで、上述した第1〜第3具体例では、A,B,Refが2の補数表示された符号付き2進数であると仮定し、3入力比較器を構成した場合を例にとって示した。この第1〜第3具体例に係る3入力比較器に対して符号無し2進数を入力した場合、その結果は正しいものとはならない。
【0060】例えば、A=1111,B=1111,Ref=1111のとき、これを符号付き2進数と受け取れば、A=−1,B=−1,Ref=−1であり、A+B<Refが成立する。一方、符号無し2進数と見た場合、A=15,B=15,Ref=15であり、A+B<Refではない。
【0061】一般に、符号無し2進数は、そのMSB側に“0”を拡張(符号拡張)することにより、符号付き2進数の処理系で正の数値として正しく扱われる。符号拡張を行ったA,B,Refについて、符号付き2進数の3入力比較の行程を適応した例を以下に示す。
A = 0 1 1 1 1 (+15) B = 0 1 1 1 1 (+15) 〜Ref = 1 0 0 0 0 (Ref=+15の全ビット反転) ------------------------ (E,D)= 01 10 10 10 10 D = 1 0 0 0 0 E = 0 1 1 1 1【0062】
D + 2 ×E + 1 = P 1 0 0 0 0 ..D:符号拡張のためPに“1”を補う。
+) 0 1 1 1 1 Q ..E:2の補数化の“1”のためにQに“1”を補う。
------------------ 0 0 1 1 1 1 …F 結果は+15であり、非負である。
【0063】ここに示した過程をそのままハードウェアで実現すると、符号拡張を行ったため、(n+2)ビット幅加算器が必要となる。これは符号付きの場合に比べて1ビット分多い。しかし、最上位ビットが明示的に定まっていることを利用して、(n+1)ビット幅加算器を用いることが出来る。具体的には、以下に示すように、A,B,Refがどんな値であっても、D,Eの最上位ビットはDが1で、Eが0であることを利用する。
【0064】
A = 0 * * * *…最上位の0 は符号拡張の0 B = 0 * * * *…最上位の0 は符号拡張の0 〜Ref = 1 * * * *…最上位の1 は符号拡張の0 の反転 ------------------------ (E,D)= 01 ** ** ** ** D = 1 * * * * E = 0 * * * *【0065】
D + 2 ×E + 1 = 1 1 * * * * … D′: 符号拡張のためPは必ず“1”になる。
+) 0 * * * * Q … E′: ------------------ S * * * * * … F【0066】ここで、Fの符号ビットSは、以下のようにして求められる。
S=0(+)1(+)(“D′の第4〜第0ビット+E′の第4〜第0ビッ ト”の桁上げ)
=〜(“D′の第4〜第0ビット+E′の第4〜第0ビット”の桁上げ)
すなわち、結果Fの符号を求めるには、“D′の第4〜第0ビットとE′の第4〜第0ビット”を加算したとき、桁上げ出力が有るか否かを求めれば良い。桁上げが1なら非負であり、0なら負であると解釈できる。ここに、(+)とは、排他的論理和を示す演算記号である。
【0067】したがって、符号無し2進数の場合であっても、(n+1)ビット幅加算器で不等式の評価を行うことが出来る。この例でD′の第4ビットが常に“1”であることに注意して、(n+1)ビット幅加算器の入力Bn には常に“1”を入力する。そして、桁上げ出力Cout生成に関わらない論理ゲートを全て除去して単純化した加算器を用いる。符号付きの場合は、和のMSB生成に関わらない論理ゲートを全て除去して単純化した加算器を用いていた。
【0068】また、符号無しの場合の非負判定段が符号付きの場合と同じ(n+1)ビット幅加算器であるから、D,E生成の3:2コンプレッサ段も符号付きの場合と全く同じものを用いて良い。以下、符号無し入力に対応した3入力比較器の具体例について説明する。
【0069】図7は、3入力比較器の第4具体例を示すブロック図である。この第4具体例に係る3入力比較器は、図2の3:2コンプレッサ段20と図3の非負判定段30とからなる。但し、第1〜第3具体例では、非負判定段30として、和Snを生成する(n+1)ビット幅加算器31が用いられたが、本例では、桁上げ出力Coutを生成する(n+1)ビット幅加算器32が用いられる。この場合、Cout生成に関わらない論理ゲートを削除することにより、回路構成を単純化できる。
【0070】そして、全加算器210 〜21n-1 の各S端子が(n+1)ビット幅加算器32のB0〜Bn−1端子にビット対応で接続されるとともに、全加算器210 〜21n-1 の各Co端子が(n+1)ビット幅加算器32の1ビット上位のA1 〜An 端子にそれぞれ接続される。また、(n+1)ビット幅加算器32の最下位ビットのA0 端子および最上位ビットのBn 端子にそれぞれ論理“1”が与えられ、Cout出力を比較結果出力として導出する構成となっている。
【0071】上記構成の第4具体例に係る3入力比較器では、不等式“A+B≧Ref”又は“A+B<Ref”(A,B,Refは符号無し2進数)の評価が行われる。この3入力比較器の比較結果出力は以下のように解釈できる。すなわち、比較結果出力が“1”の場合は、“A+B+(−Ref)≧0”、即ち“A+B≧Ref”である。比較結果出力が“0”の場合は、“A+B+(−Ref)<0”、即ち“A+B<Ref”である。
【0072】図8は、3入力比較器の第5具体例を示すブロック図である。この第5具体例に係る3入力比較器の構成要素および接続関係は、基本的には、第4具体例の場合と同じである。異なるのは、第4具体例の場合には、(n+1)ビット幅加算器32の最下位ビットのA0 端子および最上位ビットのBn 端子にそれぞれ論理“1”が与えられていたのに対し、本例では、(n+1)ビット幅加算器32の最下位ビットのA0端子に論理“1”が与えられ、最上位ビットのBn 端子に論理“1”が与えられている点である。
【0073】上記構成の第5具体例に係る3入力比較器では、不等式“A+B>Ref”又は“A+B≦Ref”(A,B,Refは符号無し2進数)の評価が行われる。この3入力比較器の比較結果出力については、第2具体例の場合と同様に解釈することができる。
【0074】図9は、3入力比較器の第6具体例を示すブロック図である。この第6具体例に係る3入力比較器は、3:2コンプレッサ段20、(n+1)ビット幅加算器32からなる非負判定段30およびEX‐ORゲート41からなるとともに、全加算器210 〜21n-1 の各S,Co端子と(n+1)ビット幅加算器32のA0 〜An ,B0 〜Bn 端子とが第4,第5具体例の場合と同じ接続関係にあり、さらに(n+1)ビット幅加算器32の最上位ビットのBn 端子に論理“1”が与えられおり、加えて、(n+1)ビット幅加算器32の最下位ビットのA0 端子に機能選択入力S0を与えるとともに、(n+1)ビット幅加算器32のSn出力と機能選択入力S1をEX‐ORゲート41の2入力とし、このEX‐ORゲート41の出力を比較結果出力として導出する構成となっている。
【0075】上記構成の第6具体例に係る3入力比較器は、機能選択入力S1,S0によって評価する不等式を選択することが可能な符号無し機能選択型3入力比較器である。すなわち、機能選択入力S0は、(n+1)ビット幅加算器32のA0 入力であって、“A+B−1≧Ref”か“A+B−1>Ref”を選択するためのものである。また、機能選択入力S1は、各不等式の評価結果が“真”のときには“1”、“偽”のときには“0”と表現されるように、非負判定段30の出力を適宜反転/非反転するためのものである。機能選択入力S1,S0と評価する不等式の対応関係は、第3具体例の場合と同じである(表2を参照)。
【0076】図10は、3入力比較器の第7具体例を示すブロック図である。この第7具体例に係る3入力比較器は、3:2コンプレッサ段20、非負判定段30、EX‐ORゲート41、セレクタ42およびORゲート43から構成されている。3:2コンプレッサ段20としては、図2に示す構成のものが用いられる。3:2コンプレッサ段20としては、Cout,Snの両方を生成する(n+1)ビット幅加算器33が用いられる。この場合、Cout,Sn生成に関わらない論理ゲートを削除することにより、回路構成の単純化が図れる。
【0077】また、3:2コンプレッサ段20の全加算器210 〜21n-1 の各S,Co端子と(n+1)ビット幅加算器33のA0 〜An ,B0 〜Bn 端子とが第4〜第6具体例の場合と同じ接続関係にある。そして、(n+1)ビット幅加算器33の最下位ビットのA0 端子に機能選択入力S0を与える。また、3:2コンプレッサ段20の最上位の全加算器21n-1 のS出力と機能選択入力S2がORゲート43の2入力となり、ORゲート43の出力が(n+1)ビット幅加算器33の最上位ビットのBn 端子に与えられる。
【0078】セレクタ42は、(n+1)ビット幅加算器33のCout出力およびSn出力を2入力とし、機能選択入力S2の論理状態に応じて2入力のいずれかを選択して出力する。この機能選択入力S2は、論理“0”のときA,B,Refが符号付き2進数、論理“1”のときA,B,Refが符号無し2進数である。したがって、セレクタ42は、機能選択入力S2が論理“0”のときSn出力を、機能選択入力S2が論理“1”のときCout出力を選択する。そして、セレクタ42の選択出力と機能選択入力S1がEX‐ORゲート41の2入力となり、このEX‐ORゲート41の出力が比較結果出力として導出される。
【0079】上記構成の第7具体例に係る3入力比較器は、第3具体例に係る符号付き機能選択型3入力比較器と、第6具体例に係る符号無し機能選択型3入力比較器とを一体化し、符号付き/符号無しおよび評価する不等式をそれぞれ動的に設定可能な全機能統合型3入力比較器である。
【0080】すなわち、機能選択入力S0は、(n+1)ビット幅加算器33のA0 入力であって、“A+B−1≧Ref”か“A+B−1>Ref”を選択する。また、機能選択入力S1は、各不等式の評価結果が“真”のときには“1”、“偽”のときには“0”と表現されるように、非負判定段30の出力を適宜反転/非反転する(表2を参照)。さらに、機能選択入力S2は、符号付き/符号無しの設定を行う。
【0081】以上説明した第1〜第7具体例に係る3入力比較器において、各非負判定段で用いられる(n+1)ビット幅加算器のゲート数は、従来装置で用いられる比較器とほぼ等しい。一方、3:2コンプレッサ段で用いられるキャリー・セーブ方式加算器の分だけ若干ゲート数が増加する。しかし、飽和演算装置全体のゲート数に関して支配的なのは比較器の方ではなく、(A+B)を行う加算器である。したがって、本発明を適用することで増加するゲート数はあまり問題とはならない。
【0082】図11は、本発明の第2実施形態を示すブロック図であり、基準値Refが2つの場合、即ち上限値および下限値の双方を指定可能な飽和加算装置に適用した場合を示している。
【0083】第2実施形態に係る飽和加算装置は、nビットの2つの入力A,Bの加算を行う加算器51と、この加算器51に対して並列に設けられ、2つの入力A,Bのnビットの加算結果がnビットの上限基準値Ref(upper) で定められる範囲を逸脱しているか否かを判定する3入力比較器52と、加算器51に対して並列に設けられ、2つの入力A,Bの加算結果がnビットの下限基準値Ref(lower)で定められる範囲を逸脱しているか否かを判定する3入力比較器53と、これら3入力比較器52,53の各1ビット(計2ビット)の比較結果に基づいて加算器51の加算結果、nビットの上限飽和値Sat(upper) およびnビットの下限飽和値Sat(lower) のいずれか1つを選択して出力するセレクタ54とから構成されている。
【0084】上記構成の第2実施形態に係る飽和加算装置において、2つの基準値Ref(upper),Ref(lower) および2つの飽和値Sat(upper),Sat(lower) は、外部にて任意に設定可能である。2つの3入力比較器52,53としては、先述した第1具体例〜第7具体例に係る3入力比較器の中から、評価したい不等式や選択できる機能に応じて適切なものを選定して用いる。また、3入力比較器52,53の出力の意味を良く判断した上でセレクタ54との接続を行う。ここで用いるセレクタ54は3入力のものである。
【0085】ここで、入力数値のビット幅がnビットの場合、加算器51および2つの3入力比較器52,53の遅延時間はどちらもlog nに比例し、両者の遅延時間はほぼ同等である。実際には、先述したように、3入力比較器52,53のハードウェアの単純さから、加算器51に比べて3入力比較器52,53の遅延時間が若干短い。したがって、加算器51に対して2つの3入力比較器52,53を並列に配置し、加算と比較を並列処理することにより、総遅延時間は第1実施形態の場合と同等となる。すなわち、高速動作が可能となる。
【0086】ところで、以下の4つの命題は自明である。
■A−B>Refを満たす整数A,B,Refがあるとき必ず、Ref+B<Aである。
■A−B≧Refを満たす整数A,B,Refがあるとき必ず、Ref+B≦Aである。
■A−B≦Refを満たす整数A,B,Refがあるとき必ず、Ref+B≧Aである。
■A−B<Refを満たす整数A,B,Refがあるとき必ず、Ref+B>Aである。
【0087】以上の命題から、減算(A−B)を含む不等式の評価は全て、加算(Ref+B)を含む不等式の評価に置き換えられることが分かる。すなわち、第1実施形態に係る飽和加算装置における3入力加算器12(図1を参照)に対し、入力Aと基準値Refを置換して入力することによって、何らハードウェアに変更を加えることなく、減算(A−B)を含む不等式の評価をすることが出来る。
【0088】図12は、本発明の第3実施形態を示すブロック図であり、基準値Refが1つの場合、即ち上限/下限値のいずれかを指定可能な飽和減算装置に適用した場合を示している。
【0089】第3実施形態に係る飽和減算装置は、nビットの2つの入力A,Bの減算を行う減算器61と、この減算器61に対して並列に設けられ、2つの入力A,Bの減算結果がnビットの基準値Refで定められる範囲を逸脱しているか否かを判定する3入力比較器62と、この3入力比較器62の1ビットの比較結果に基づいて減算器61の減算結果とnビットの飽和値Satのいずれか一方を選択して出力するセレクタ63とから構成されている。
【0090】上記構成の第3実施形態に係る飽和減算装置において、基準値Refおよび飽和値Satは、外部にて任意に設定可能である。ここで、本実施形態に係る飽和減算装置と第1実施形態に係る飽和加算装置とを比べると、3入力比較器62に対する入力A,Refが相互に置き換わっている。3入力比較器62としては、先述した第1具体例〜第7具体例に係る3入力比較器の中から、評価したい不等式や選択できる機能に応じて適切なものを選定して用いる。但し、その選定の際には注意が必要である。
【0091】例えば、“A−B<REF”という不等式を評価したい場合、3入力比較器62としては、“a+b>ref”を評価するものを用いる。REF,refに対する不等号の向きが反対なので間違えやすい。これは、“a+b>ref”に対しa=REF,b=B,ref=Aと入力し、“REF+B>A”、即ち“A−B<REF”と評価するからである。
【0092】したがって、“A−B<REF”を評価するときは、“a+b>ref”を評価する3入力比較器を、“A−B≦REF”を評価するときは、“a+b≧ref”を評価する3入力比較器を、“A−B≧REF”を評価するときは、“a+b≦ref”を評価する3入力比較器を、“A−B>REF”を評価するときは、“a+b<ref”を評価する3入力比較器をそれぞれ用いるようにする。
【0093】このように、第3実施形態に係る飽和減算装置においては、図1の第1実施形態に係る飽和加算装置に対して、3入力比較器62に対する入力結線を変更しただけであるから、総遅延時間は図1の飽和加算装置のものと同等であり、高速動作が可能である。
【0094】図13は、本発明の第4実施形態を示すブロック図であり、第2実施形態に係る飽和減算装置の場合のように、基準値Refが2つの場合、即ち上限値および下限値の双方を指定可能な飽和減算装置に適用した場合を示している。
【0095】第4実施形態に係る飽和減算装置は、nビットの2つの入力A,Bの減算を行う減算器71と、この減算器71に対して並列に設けられ、2つの入力A,Bの減算結果がnビットの上限基準値Ref(upper) で定められる範囲を逸脱しているか否かを判定する3入力比較器72と、減算器71に対して並列に設けられ、2つの入力A,Bのnビットの減算結果がnビットの下限基準値Ref(lower)で定められる範囲を逸脱しているか否かを判定する3入力比較器73と、これら3入力比較器72,73の各1ビット(計2ビット)の比較結果に基づいて減算器71の減算結果、nビットの上限飽和値Sat(upper) およびnビットの下限飽和値Sat(lower) のいずれか1つを選択して出力するセレクタ74とから構成されている。
【0096】上記構成の第4実施形態に係る飽和減算装置において、2つの基準値Ref(upper),Ref(lower) および2つの飽和値Sat(upper),Sat(lower) は、外部にて任意に設定可能である。ここで、本実施形態に係る飽和減算装置と第2実施形態に係る飽和加算装置とを比べると、3入力比較器72,73に対する入力AとRef(upper),Ref(lower) が相互に置き換わっている。3入力比較器72,73としては、第3実施形態の場合と同様にして、先述した第1具体例〜第7具体例に係る3入力比較器の中から適切なものを選定して用いる。
【0097】ここまでは、飽和加算装置および飽和減算装置に適用した場合について説明したが、続いて、飽和乗算装置に適用した場合について説明する。
【0098】一般的な高速乗算器として、キャリー・セーブ方式加算器(3:2コンプレッサ)や4:2コンプレッサ、冗長2進加算器などを用いたものがある。これらの乗算器では、部分積を求める段階では桁上げ伝搬を抑制し、部分積加算を高速に行う。最終的に部分積は2つの2進数A,Bで表現され、本当の積はA+B(冗長2進では、A−B)で求められる。これを最終段加算と言う。
【0099】乗算結果がある基準値を越えたか否かを判定することは、最終段加算で行う部分積和(A+B)(冗長2進なら、A−B)が基準値を越えたか否かを判定することと等しい。したがって、最終段加算と並列に3入力比較器を設けることによって、飽和乗算装置を構成することが出来る。
【0100】図14は、本発明の第5実施形態を示すブロック図であり、基準値Refが1つの場合、即ち上限/下限値のいずれかを指定可能な飽和乗算装置に適用した場合を示している。
【0101】第5実施形態に係る飽和乗算装置は、n/2ビットの2つの入力X,Yの部分積加算を行う部分積加算器81と、この部分積加算器81から供給されるnビットの2つの入力A,Bの最終段加算を行う最終段加算器82と、この最終段加算器82に対して並列に設けられ、2つの入力A,Bの最終段加算結果がnビットの基準値Refで定められる範囲を逸脱しているか否かを判定する3入力比較器83と、この3入力比較器83の1ビットの比較結果に基づいて最終段加算器82の加算結果とnビットの飽和値Satのいずれか一方を選択して出力するセレクタ84とから構成されている。
【0102】上記構成の第5実施形態に係る飽和乗算装置において、基準値Refおよび飽和値Satは、外部にて任意に設定可能である。また、部分積加算器81の出力以降の構成は、図1に示す第1実施形態に係る飽和加算器装置と同じである。したがって、部分積加算器81の出力以降における総遅延時間は図1の飽和加算装置のものと同等であるため、高速動作が可能である。
【0103】なお、本実施形態においては、最終段で部分積和(A+B)をとる場合を例にとって説明したが、冗長2進のように(A−B)を行う場合には、第3実施形態に係る飽和減算装置と同様な原理で3入力比較器を選定し、その入力A,Refの接続関係を置換することによって実現出来る。
【0104】また、第2実施形態に係る飽和加算装置や、第4実施形態に係る飽和減算装置の場合と同様に、最終段加算器82に対して2つの3入力比較器を並列に設けることにより、上限値および下限値の双方を指定可能な飽和乗算装置を実現することが出来る。
【0105】以上、飽和加算装置、飽和減算装置および飽和乗算装置に適用した場合について説明したが、これらに限定されるものではなく、第5実施形態に係る飽和乗算装置のように、最終的に加算あるいは減算を行う演算装置であれば全て、3入力比較器を用いて高速な飽和演算処理を行うことが出来る。すなわち、最終段の加算器あるいは減算器と並列に3入力比較器を設けることで、加算・減算と同時に不等式の評価が行われ、加算・減算の終了時点で、基準値を超えたか否かが判明する。この後、セレクタを適切に用いることにより、加算・減算値か飽和値(単数か複数)を選ぶ。
【0106】こうすることで、任意基準値・任意飽和値を指定可能な飽和演算処理を追加することが出来る。なお、加算・減算・乗算を複合的に行う演算処理(多項式の演算)においては、キャリー・セーブ方式の加算器や冗長2進加算器を用いて桁上げ伝搬を抑制した演算が行われる。このとき必ず、最終結果は2つの2進数の和(あるいは差)で求められ、必ず最終段で桁上げ伝搬を伴う加算器・減算器が用いられる。
【0107】以上説明した各実施形態に係る飽和演算装置は、一例として、ディスプレイ上の任意の位置に存在する矩形領域内に描画を行うような場合に用いて好適なものである。すなわち、ディスプレイ上の任意の位置に任意の大きさの矩形領域があり、その領域内に描画を行う場合に、任意基準値・任意飽和値の飽和演算が必要となる。
【0108】画面座標の計算は一般的に加算・乗算あるいは多項式演算によって行われる。描画しようとする座標が領域を逸脱した場合、領域の境界値あるいは適当な飽和値に補正するか、または、別の例外処理の起動を行う必要がある。このような場合に、各実施形態に係る飽和演算装置を用いることによって、これらの処理を高速に実行することができる。
【0109】一般的な信号処理においても、線形多項式の演算、即ち積和演算が頻繁に行われる。このとき飽和演算処理は必須である。ある信号処理アルゴリズムによっては、加算器の最大値(オーバーフロー)未満で飽和演算を行う場合がある。また、ある信号処理においては、線形多項式(積和演算)の値を分母に持つ分数の評価を行う場合がある。この場合、この多項式は0となることは許されない。以上のような加算器の最大値(オーバーフロー)以外を基準値とした飽和演算処理を行う場合に、各実施形態に係る飽和演算装置を用いることによって、高速に行うことができる。
【0110】このように、加算器の最大値以外の値を基準値とする飽和演算処理の用途は多く、また常に高速性が要求される。各実施形態に係る飽和演算装置を用いることによって、これらの処理を高速化することが可能である。
【0111】
【発明の効果】以上説明したように、本発明によれば、nビット幅の3つの2進数(A,B,Ref)の総和をnビット幅の2つの2進数に変換し、この2つの2進数に基づいてその総和の値が非負であるか否かを判定することで、2つの入力A,Bの演算結果が所定の基準値Refで定められる範囲を逸脱しているか否かを迅速に判定できるので、飽和演算の高速処理に寄与できることになる。
【0112】また、2つの入力の演算処理と、その演算結果が所定の基準値で定められる範囲を逸脱しているか否かの判定処理とを並行して行い、この判定結果に基づいて演算結果と所定の飽和値のいずれか一方を選択して出力することで、「演算/比較→選択」の2つの段階で飽和演算を行うことができるので、基準値・飽和値を任意に指定できるとともに、高速演算を実現できることになる。また、



 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013