(57)【要約】【課題】２つの２進数の平均値演算を高速化すること。【解決手段】キャリー生成回路２２０が２つの入力データX<15:00>、Y<15:00>の最下位ビットX<00>、Y<00>を用いてキャリーを生成し、加算器２１０が２つの入力データのそれぞれを右に１ビットシフトしたデータX<"0",15:01>、Y<"0",15:01>とキャリー生成回路２２０により生成されたキャリーC'とを加算する。なお、キャリー生成回路２２０は、平均値の求め方が四捨五入ならキャリーC'=X<00>+Y<00>（"+"は論理和）を出力し、切り捨てならC'=X<00>&Y<00>を出力する。【選択図】        図２
2005182294.tif 000002
【特許請求の範囲】
【請求項１】
２つの２進数の平均値を算出する平均値算出装置であって、
前記２つの２進数の最下位ビットから該２進数の平均値演算における最下位ビットへのキャリーを生成するキャリー生成手段と、
前記２つの２進数を右に１ビットシフトした２つの２進数と前記キャリー生成手段により生成されたキャリーを加算して平均値を算出する加算手段と、
を備えたことを特徴とする平均値算出装置。
【請求項２】
前記２つの２進数はパリティービットを有するパリティー付２進数であり、該２つのパリティー付２進数の平均値のパリティーを予測するパリティー予測手段をさらに備えたことを特徴とする請求項１に記載の平均値算出装置。
【請求項３】
前記パリティー予測手段は、それぞれのパリティー付２進数を右に１ビットシフトした２進数のパリティーを予測する２つのシフトパリティー予測手段と、
前記加算手段により算出される平均値のパリティーを前記２つのシフトパリティー予測手段により予測された２つのパリティーを用いて予測する加算パリティー予測手段と、
を備えたことを特徴とする請求項２に記載の平均値算出装置。
【請求項４】
前記キャリー生成手段は、四捨五入により平均値を求める場合には、前記２つの２進数の最下位ビットに対して論理和演算を行ってキャリーを生成し、切り捨てにより平均値を求める場合には、前記２つの２進数の最下位ビットに対して論理積演算を行ってキャリーを生成することを特徴とする請求項１、２または３に記載の平均値算出装置。
【請求項５】
２つの２進数の平均値を算出する平均値算出方法であって、
前記２つの２進数の最下位ビットから該２進数の平均値演算における最下位ビットへのキャリーを生成するキャリー生成工程と、
前記２つの２進数を右に１ビットシフトした２つの２進数と前記キャリー生成工程により生成されたキャリーを加算して平均値を算出する加算工程と、
を含んだことを特徴とする平均値算出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、２つの２進数の平均値を算出する平均値算出装置および平均値算出方法に関し、特に、パリティー付２進数の平均値を高速に算出することができる平均値算出装置および平均値算出方法に関するものである。
【背景技術】
【０００２】
２つのデータの平均値をとる処理は、ＭＰＥＧやＤＶＤなどの画像処理における基本的な処理であり、デジタル画像の普及とともに、データの平均値算出処理に対する高速化の要求が高まっている。
【０００３】
図９−１は、基本的な平均値算出手法を説明するための説明図である。同図に示すように、２つの１６ビットの２進数X<15:00>とY<15:00>の平均値Ｚ<15:00>を四捨五入による丸めによって求める手順は以下のとおりである。なお、ここで、<15:00>は、「ビット０」から「ビット１５」までの１６ビットを示し、「ビット０」は最下位ビットであり、「ビット１５」は最上位ビットである。
【０００４】
（１）X<15:00>とY<15:00>の加算を行ってZ'<16:00>を求める。
（２）求めたZ'を２で割る。ここで、２で割る処理は、２進数では１ビット右にシフトすればよいので、Z'を１ビット右にシフトしてZ”<15:-1>を求める。
（３）丸めが四捨五入であるため、Z”<-1>の位に"1"を加算して平均値Z<15:00>を求める。このとき、"1"が加算されたZ”<-1>の値は結果として使用しない。また、丸めが四捨五入でなく切り捨ての場合は、Z”<-1>の位に"1"を加算することなくZ”<15:00>を平均値Z<15:00>とすればよい。
【０００５】
具体的には、X=49834(10進)=1100 0010 1010 1010(2進)、Y=34085(10進)=1000 0101 0010 0101(2進)として、この２値の四捨五入の平均値Z=41960(10進)=1010 0011 1110 1000(2進)を求めるとすると、Zは以下の手順で求まる。
【０００６】
（１）２数の加算を行う。
Z'(10進)=49834+34085=83919
Z'(2進)=1100 0010 1010 1010+1000 0101 0010 0101
=1 0100 0111 1100 1111
【０００７】
（２）加算結果を１ビット右にシフトする。このとき"."は小数点の位置を示す。
Z”(10進)=83919÷2=41959.5
Z”(2進)=1010 0011 1110 0111.1
【０００８】
（３）小数点第一位に"1"を加算する。
Z(10進)=41959.5+0.5=41960
Z(2進)=1010 0011 1110 0111.1+0.1
=1010 0011 1110 1000
【０００９】
図９−２は、基本的な平均値算出手法で平均値を算出する平均値算出回路を示す図である。同図に示すように、この平均値算出回路では、それぞれ１６ビット長のデータX<15:00>、Y<15:00>を加算器９２１に入力し、１７ビット長の結果Z'<16:00>を求める。そして、Z'をシフタ９２２で1ビット右にシフトし、Z"<15:-1>を求める。さらに、四捨五入で丸めを行うため、Z"の最下位に"1"を加算する。
【００１０】
このように、基本的な平均値算出手法により平均値を求めるのには、加算器９２１、シフタ９２２、丸め回路９２３と３つの演算器が必要となり、演算時間や演算回路の増大を招いていた。そこで、演算時間や演算回路を少なくするために、平均値算出手法の改善が図られてきた。
【００１１】
図９−３は、改善された平均値算出手法を説明するための説明図である。同図に示すように、改善された平均値算出手法で２つの１６ビットの２進数X<15:00>とY<15:00>の平均値Z<15:00>を四捨五入による丸めによって求める手順は以下のとおりである（例えば、特許文献１参照。）。
【００１２】
（１）X<15:00>＋Y<15:00>と丸めが四捨五入であるための"1"の加算を行いZ'<16:00>を求める。
（２）平均値を求めるためZ'を２で割る。この２で割る処理は、２進数では１ビット右にシフトすればよいので、１ビット右シフト処理によってZ<15:0>を求める。このシフト処理でシフトアウトしたZ<-1>の値は結果として使用しない。
【００１３】
具体的には、前と同様に、X=49834(10進)=1100 0010 1010 1010(2進)、Y=34085(10進)=1000 0101 0010 0101(2進)として、この２値の四捨五入の平均値Z=41960(10進)=1010 0011 1110 1000(2進)を改善手法で求めるとすると、Zは以下の手順で求まる。
【００１４】
（１）２数と丸め"1"の加算を行う。この"1"の加算は、最下位のキャリーを"1"とすることで容易に実現される。
Z'(10進)=49834+34085+1=83920
Z'(2進)=1100 0010 1010 1010+1000 0101 0010 0101+1
=1 0100 0111 1101 0000
【００１５】
（２）加算結果を１ビット右にシフトする。このとき"."は小数点の位置を示す。
Z'(10進)=83919÷2=41960
Z(2進)=1010 0011 1110 1000.0
【００１６】
図９−４は、改善された平均値算出手法で平均値を算出する平均値算出回路を示す図である。同図に示すように、この改善された平均値算出回路では、それぞれ１６ビット長のデータX<15:00>、Y<15:00>を加算器９４１に入力するとともに最下位のキャリーを"1"として加算を行い１７ビット長の結果Z'<16:00>を求める。
【００１７】
そして、求めたZ'<16:00>をシフタ９４２で１ビット右にシフトし、平均値Z<15:00>を求める。このシフト処理は、実際は加算結果を１ビット右にずらして出力すればよい。このような改善方式により、加算器９４１とシフタ９４２の２つの演算器で平均値を算出することが可能となる。
【００１８】
このように、平均値算出回路の演算時間や演算回路の改善が図られる一方、計算機の信頼性向上のために、計算機が扱うデータにパリティーを付加することが行われるようになってきた。そこで、パリティーで保護されたデータの平均値を算出する平均値算出回路について説明する。
【００１９】
パリティー付の２つのデータの平均値をパリティー付で求めるには、平均値算出回路の加算器、シフタにおいて、入力データと入力パリティーから出力パリティーを予測する回路を付加する必要がある。そこで、加算器、およびシフタにおけるパリティーの予測論理の概要を以下に示す。
【００２０】
まず、加算器におけるパリティー予測論理の概要を示す。２つの８ビット入力データをX<7:0>、Y<7:0>とし、それらに対するパリティーをそれぞれXP、YPとすると、加算結果Zに対するパリティーZPは、加算における各ビットの半加算データをHとし、各ビットへのキャリーをCとした場合、以下の式で求まる。ここで"∀"は排他的論理和(xor)を,"+"は論理和(or)を,"&"は論理積(and)を、"＾"は反転（not）を表し、ここでのパリティーは奇数パリティーとする。
【００２１】
ZP=^(Z<7>∀Z<6>∀Z<5>∀Z<4>∀Z<3>∀Z<2>∀Z<1>∀Z<0>)
=^[(H<7>∀C<7>)∀(H<6>∀ C<6>)∀(H<5>∀C<5>)∀(H<4>∀C<4>)∀(H<3>∀C<3>)∀(H<2>∀C<2>)∀(H<1>∀C<1>)∀(H<0>∀C<0>)]
=^[(H<7>∀H<6>∀H<5>∀H<4>∀H<3>∀H<2>∀H<1>∀H<0>)∀(C<7>∀C<6>∀C<5>∀C<4>∀C<3>∀C<2>∀C<1>∀C<0>)]
=^[[(X<7>∀Y<7>)∀(X<6>∀Y<6>)∀(X<5>∀Y<5>)∀(X<4>∀Y<4>)∀(X<3>∀Y<3>)∀(X<2>∀Y<2>)∀(X<1>∀Y<1>)∀(X<0>∀Y<0>)]∀(C<7>∀C<6>∀C<5>∀C<4>∀C<3>∀C<2>∀C<1>∀C<0>)]
=^[[(X<7>∀X<6>∀X<5>∀X<4>∀X<3>∀X<2>∀X<1>∀X<0>)]∀[(Y<7>∀Y<6>∀Y<5>∀Y<4>∀Y<3>∀Y<2>∀Y<1>∀Y<0>)]∀(C<7>∀C<6>∀C<5>∀C<4>∀C<3>∀C<2>∀C<1>∀C<0>)]
=^[^XP∀^YP∀(C<7>∀C<6>∀C<5>∀C<4>∀C<3>∀C<2>∀C<1>∀C<0>)]
【００２２】
このように、加算結果のパリティーは、それぞれの入力パリティーの排他的論理和と、入力データの加算処理での各ビットに対するすべてのキャリーの排他的論理和とで求められる。
【００２３】
また、このキャリーCは、各入力ビットのキャリー伝播条件をP、キャリー発生条件をGとすると
C<7>=G<6>+P<6>&G<5>+P<6>&P<5>&G<4>+P<6>&P<5>&P<4>&G<3>+P<6>&P<5>&P<4>&P<3>&G<2>+P<6>&P<5>&P<4>&P<3>&P<2>&G<1>+P<6>&P<5>&P<4>&P<3>&P<2>&P<1>&G<0>+P<6>&P<5>&P<4>&P<3>&P<2>&P<1>&P<0>&CIN
C<6>=G<5>+P<5>&G<4>+P<5>&P<4>&G<3>+P<5>&P<4>&P<3>&G<2>+P<5>&P<4>&P<3>&P<2>&G<1>+P<5>&P<4>&P<3>&P<2>&P<1>&G<0>+P<5>&P<4>&P<3>&P<2>&P<1>&P<0>&CIN
:                        :
:                        :
C<2>=G<1>+P<1>&G<0>+P<1>&P<0>&CIN
C<1>=G<0>+P<0>&CIN
C<0>=CIN
となる。ここで、このCINは、平均値の求め方が四捨五入であれば"1"であり、切り捨てであれば"0"である。
【００２４】
さらに、このP、Gは
P<n>=X<n>+Y<n>
G<n>=X<n>&Y<n>
である。
【００２５】
以上より、この各ビットへのキャリーの排他的論理和に相当する論理を□とすると
ZP=^[^XP∀^YP]∀[X<7:0>□Y<7:0>]
と表すことができる。この□の論理は、加算パリティー反転予測論理と呼ばれ、上記に示すように、非常に複雑な論理となる。また、このパリティーを求めるキャリー論理は、加算回路の正当性をチェックする本来の目的から、加算回路でのキャリーをそのまま使用するのではなく、入力X<7:0>とY<7:0>から別回路により求める必要がある。
【００２６】
図９−５は、従来のパリティー付加算回路の一例を示す図である。同図において、XP<1:0>、YP<1:0>は、X<15:00>、Y<15:00>の１６ビットの各入力データについて、８ビットごとに付けられた２ビットのパリティーとする。また、加算パリティー反転予測回路９５２は、上述したZPを求める式での□の論理をとる回路である。
【００２７】
このパリティー付加算回路９５０でのディレイクリティカルパスは入力X、Yから□の論理をとる加算パリティー反転予測回路９５２を経由し、入力パリティーの排他的論理和結果とさらに排他的論理和をとりパリティーZP<1:0>を出力するパスとなる。
【００２８】
次に、シフト演算におけるパリティー予測論理の概要を示す。入力データをX<7:0>とし、それらに対するパリティーをXPとすると、シフト演算結果Zに対するパリティーZPは、入力パリティーXPと、そのパリティー単位からシフトアウトするデータと、シフトインしてくるデータとのxorで求めることができる。
【００２９】
よって、入力データX<7:0>を１ビット右にシフトした結果のパリティーZPは以下のように求まる。
ZP=XP∀("0"∀X<0>)
【００３０】
図９−６は、このような、従来のパリティー付シフタの一例を示す図である。同図に示すように、このパリティー付シフタ９６０は、１６ビットの１ビット右シフタと、シフトパリティー反転予測回路９６２とを有する。そして、X<15:00>の16ビットデータについて、パリティーをXP<1:0>とすると、結果のパリティーZP<1:0>は
ZP<1>=XP<1>∀X<8>
ZP<0>=XP<0>∀X<8>∀X<0>
で求まる。
【００３１】
このように、従来のパリティー付シフタ９６０でのディレイクリティカルパスは、入力Xの<8,0>とパリティーXP<1:0>の排他的論理和をとり、結果のパリティーZP<1:0>を出力するパスとなる。
【００３２】
次に、このようなパリティー付加算回路９５０とパリティー付シフタ９６０で構成されるパリティー予測回路を有する従来のパリティー予測回路付平均値算出回路について説明する。図９−７は、従来のパリティー予測回路付平均値算出回路の一例を示す図である。
【００３３】
同図に示すように、このパリティー予測回路付平均値算出回路９７０は、２つの１６ビット入力データX<15:00>、Y<15:00>についての平均値を、加算器９５１で加算された結果を１ビット右シフタ９６１で右に１ビットシフトすることで求める。
【００３４】
このときのパリティーは、入力データの加算パリティー反転予測回路９５２からの検出信号と入力パリティーXP<1:0>,YP<1:0>とから求まる加算結果パリティーと、シフト処理のパリティーを求めるためのシフトパリティー反転予測回路９６２からの検出信号との排他的論理和をとることで求まる。
【００３５】
すなわち、平均値は加算結果を１ビットずらして出力すればよいのに対して、パリティーは２つの入力データと入力パリティーとの排他的論理和演算を行う必要がある。したがって、このパリティー予測回路付平均値算出回路９７０でのディレイクリティカルパスは、入力デ−タから加算での加算結果パリティーを算出し、その加算結果パリティーをパリティー付シフタに入力し、そのシフト結果パリティーが出力されるパスとなる。
【００３６】
【特許文献１】特開平１０−１０５３８２号公報
【発明の開示】
【発明が解決しようとする課題】
【００３７】
上述したように、従来のパリティー予測回路付平均値算出回路９７０では、入力データから加算結果パリティーを算出し、算出した加算結果パリティーを用いて平均値のパリティーを算出するパスがディレイクリティカルパスとなり、平均値算出処理の性能低下を招いているという問題がある。
【００３８】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、パリティー付２進数の平均値を高速に算出することができる平均値算出装置および平均値算出方法を提供することを目的とする。
【課題を解決するための手段】
【００３９】
上述した課題を解決し、目的を達成するため、本発明は、２つの２進数の平均値を算出する平均値算出装置であって、前記２つの２進数の最下位ビットから該２進数の平均値演算における最下位ビットへのキャリーを生成するキャリー生成手段と、前記２つの２進数を右に１ビットシフトした２つの２進数と前記キャリー生成手段により生成されたキャリーを加算して平均値を算出する加算手段と、を備えたことを特徴とする。
【００４０】
また、本発明は、２つの２進数の平均値を算出する平均値算出方法であって、前記２つの２進数の最下位ビットから該２進数の平均値演算における最下位ビットへのキャリーを生成するキャリー生成工程と、前記２つの２進数を右に１ビットシフトした２つの２進数と前記キャリー生成工程により生成されたキャリーを加算して平均値を算出する加算工程と、を含んだことを特徴とする。
【００４１】
かかる発明によれば、２つの２進数の最下位ビットから２進数の平均値演算における最下位ビットへのキャリーを生成し、２つの２進数を右に１ビットシフトした２つの２進数と生成したキャリーを加算することとしたので、平均値を算出することができる。
【００４２】
また、本発明は、上記発明において、前記２つの２進数はパリティービットを有するパリティー付２進数であり、該２つのパリティー付２進数の平均値のパリティーを予測するパリティー予測手段をさらに備えたことを特徴とする。
【００４３】
この発明によれば、２つのパリティー付２進数の平均値のパリティーを予測することとしたので、パリティー付２進数の平均値を算出することができる。
【発明の効果】
【００４４】
本発明によれば、２つの２進数の最下位ビットから２進数の平均値演算における最下位ビットへのキャリーを生成し、２つの２進数を右に１ビットシフトした２つの２進数と生成したキャリーを加算し、２つのパリティー付２進数の平均値のパリティーを予測するよう構成したので、パリティー付２進数の平均値を高速に算出することができるという効果を奏する。
【発明を実施するための最良の形態】
【００４５】
以下に添付図面を参照して、この発明に係る平均値算出装置および平均値算出方法の好適な実施例を詳細に説明する。なお、実施例１では、パリティーのないデータの平均値を算出する平均値算出回路について説明し、実施例２では、パリティー付データの平均値を算出するパリティー付平均値算出回路について説明する。
【実施例１】
【００４６】
まず、本実施例１に係る平均値算出手法について説明する。図１は、本実施例１に係る平均値算出手法を説明するための説明図である。同図に示すように、この平均値算出手法では、以下の手順で平均値を算出する。
【００４７】
（１）２つの入力データX<15:00>、Y<15:00>を２で割り、X'<15:00>とY'<15:00>を求める。この２で割る処理は、２進数では１ビット右にシフトすればよいので、１ビット右シフト処理によってX'<15:00>とY'<15:00>を求める。
【００４８】
（２）X'<15:00>とY'<15:00>を最下位へのキャリーをC'として加算し平均値Zを求める。ここで、キャリーC'は、入力データであるX<0>、Y<0>と平均値の求め方により決まる。具体的には、平均値の求め方が四捨五入ならC'=X<0>+Y<0>（"+"は論理和）となり、切り捨てならC'= X<0>&Y<0>となる。
【００４９】
すなわち、本実施例１に係る平均値算出手法では、２つの２進数X、Yの平均値Z=(X+Y)/2＋CをZ=(X/2+Y/2)+C'として求める。なお、（１）での入力データを２で割る処理は、単に１ビット右シフト処理するだけであるため、入力データを１ビット右にずらして加算回路へ入力し、その最下位キャリーをC'として加算するだけで、平均値演算結果を求めることができる。
【００５０】
以下に、本実施例１に係る平均値算出手法を用いて前出と同じ値X=49834(10進)=1100 0010 1010 1010(2進)、Y=34085(10進)=1000 0101 0010 0101(2進)について、この２値の四捨五入の平均値Z=41960(10進)=1010 0011 1110 1000(2進)を求める手順を説明する。
【００５１】
（１）２数を２で割る。すなわち１ビット右にシフトする。このとき"."は小数点の位置を示す。
X'(10進)=24917
X'(2進)=0110 0001 0101 0101.0
Y'(10進)=17042.5
Y'(2進)=0100 0010 1001 0010.1
【００５２】
（２）X'、Y'の小数点以下と四捨五入丸めにより最下位へのキャリーC'='1'として小数点以上の値についてX'とY'の加算を行う。
Z(10進)=24917+17042+1=41960
Z(2進)=0110 0001 0101 0101+0100 0010 1001 0010+1
=1010 0011 1110 1000
【００５３】
このように、本実施例１に係る平均値算出手法では、２数の加算とシフトの実行順序を従来とは反対にして、２数をシフトした後で加算することによって、実施例２で説明するように、パリティー付のデータに対する平均値の算出を高速化することができる。
【００５４】
次に、本実施例１に係る平均値算出回路の構成について説明する。図２は、本実施例１に係る平均値算出回路の構成を示す機能ブロック図である。同図に示すように、この平均値算出回路２００は、加算器２１０と、キャリー生成回路２２０とを有する。
【００５５】
加算器２１０は、２つの１６ビットデータ入力と最下位ビットへのキャリー入力を加算する回路である。この加算器２１０は、平均値を取る２数をX<15:00>、Y<15:00>とすると、X<15:01>、Y<15:01>の上位にそれぞれ"0"を付加した１６ビットデータ入力とキャリー入力を加算する。したがって、この加算器２１０の加算結果Z<15:00>がそのままX<15:00>とY<15:00>の平均値となる。
【００５６】
キャリー生成回路２２０は、X<00>とY<00>を入力して加算器２１０の最下位ビットへのキャリーを生成する回路である。すなわち、このキャリー生成回路２２０は、平均値の求め方が四捨五入ならキャリーC'=X<00>+Y<00>（"+"は論理和）を出力し、切り捨てならC'=X<00>&Y<00>を出力する。
【００５７】
このように、この平均値算出回路２００は、キャリー生成回路２２０がX<00>とY<00>を入力して加算器２１０の最下位ビットへのキャリーを生成し、加算器２１０が、X<15:01>、Y<15:01>の上位にそれぞれ"0"を付加した１６ビットデータ入力とキャリー入力を加算することによって、平均値を算出する。
【００５８】
次に、平均値を算出するデータが、あるデータ長のデータに複数含まれている場合について説明する。図３は、平均値を算出するデータが複数含まれるデータフォーマットの一例を示す図である。同図に示すように、このデータフォーマットでは、６４ビットのデータの中に４つの８ビットデータが含まれている。
【００５９】
図４は、図３に示したフォーマットのデータの平均値を算出する４並列平均値算出回路の一例を示す図である。同図に示すように、この４並列平均値算出回路４００は、４つの平均値算出回路２００を有し、図３に示した６４ビットデータを２つ入力して４つの平均値を並列に生成する。
【００６０】
図５は、図３に示したフォーマットのデータの平均値を既存の加算器を用いて算出する手法を説明するための説明図である。同図に示すように、既存の６４ビット加算器を用いる場合には、平均値を算出するそれぞれの８バイト入力データX<63:00>、Y<63:00>を右に1ビットシフトし、さらにそれぞれのビット位置<63>、<47>、<31>、<15>への入力を"0"とした
X'<63:00>=X<"0",63:49,"0",47:33,"0",31:17,"0",15:01>と
Y'<63:00>=Y<"0",63:49,"0",47:33,"0",31:17,"0",15:01>と
をビット位置<48>、<32>、<16>、<00>へのキャリーをC48、C32、C16、C00として加算する。
【００６１】
すなわち、入力データX、Yのビット<48>、<32>、<16>、<00>データは次に述べるキャリー生成にしか使用されず、実際の加算結果には影響しない。この加算におけるビット位置<48>、<32>、<16>、<00>へのキャリーIN信号C48、C32、C16、C00は、平均値を四捨五入で求める場合は、下位データからのキャリー伝播条件とは無関係に、それぞれC<48>=X<48>+Y<48>、C<32>=X<32>+Y<32>、C<16>=X<16>+Y<16>、C<00>=X<00>+Y<00>（ここで"+"は論理和）とし、切り捨ての場合はC<48>=X<48>&Y<48>、C<32>=X<32>&Y<32>、C<16>=X<16>&Y<16>、C<00>=X<00>&Y<00>とする。
【００６２】
さらに、ビット位置<47>、<31>、<15>からの上位へのキャリー伝播は抑止する。このような手法をとることで、わずかな回路の追加のみで既存の加算器で複数の平均値を算出することができる。
【００６３】
図６は、図３に示したフォーマットのデータの平均値を既存の加算器を用いて算出する４並列平均値算出回路の一例を示す図である。同図において、平均値演算モード信号６３０が"1"の場合、それぞれの入力を右に１ビットシフトして加算器６１０に入力する。
【００６４】
また、同じく平均値演算モード信号６３０が"1"の場合は、加算におけるビット位置<48>、<32>、<16>、<00>へのキャリー信号C48、C32、C16、C00を、キャリー生成回路(CGEN)６２０において、平均値を四捨五入で求める場合はそれぞれC<48>=X<48>+Y<48>、C<32>=X<32>+Y<32>、C<16>=X<16>+Y<16>、C<00>=X<00>+Y<00>（ここで"+"は論理和）とし、切り捨ての場合はC<48>=X<48>&Y<48>、C<32>=X<32>&Y<32>、C<16>=X<16>&Y<16>、C<00>=X<00>&Y<00>として加算する。
【００６５】
さらに、ビット<47>、<31>、<15>からの上位へのキャリー伝播は抑止する。このような回路構成をとることで、既存の加算器にわずかな回路を追加するだけですむため、平均値を算出することができる計算機のハード量を削減することができる。
【００６６】
上述してきたように、本実施例１では、キャリー生成回路２２０が２つの入力データの最下位ビットを用いてキャリーを生成し、加算器２１０が２つの入力データのそれぞれを右に１ビットシフトしたデータとキャリー生成回路２２０により生成されたキャリーとを加算することとしたので、加算器２１０の出力をそのまま平均値とすることができる。
【実施例２】
【００６７】
次に、実施例２では、パリティー付データに対して平均値を算出するパリティー付平均値算出回路について説明する。まず、本実施例２に係るパリティー付平均値算出回路の構成について説明する。
【００６８】
図７は、本実施例２に係るパリティー付平均値算出回路の構成を示す機能ブロック図である。なお、ここでは説明の便宜上、図２および図９−７に示した各部と同様の役割を果たす機能部については同一符号を付すこととしてその詳細な説明を省略する。
【００６９】
同図に示すように、このパリティー付平均値算出回路７００は、加算器２１０と、キャリー生成回路２２０と、加算パリティー反転予測回路９５２と、２つのシフトパリティー反転予測回路９６２とを有する。
【００７０】
このパリティー付平均値算出回路７００は、平均値を以下の手順で算出する。２つの入力データとパリティーをそれぞれX<15:00>、XP<1:0>、Y<15:00>、YP<1:0>とする。これら２つの入力データのX<15:01>、Y<15:01>を上位にそれぞれ"0"を付加してそれぞれ１６ビットとして加算器２１０で最下位へのキャリーCとして加算する。ここで、キャリーCは、キャリー生成回路２２０により生成され、この加算器２１０からの１６ビットの加算結果がそのまま平均値Z<15:00>である。
【００７１】
一方、パリティーZP<1:0>は以下の手順で算出する。まず、２つのシフトパリティー反転予測回路９６２においてシフト結果パリティーXP'<1:0>、YP'<1:0>を算出する。このとき、XP'<1>=XP<1>∀X<8>、XP'<0>=XP<0>∀X<8>∀X<0>、YP'<1>=YP<1>∀Y<8>、YP'<0>=YP<0>∀Y<8>∀Y<0>である。
【００７２】
また、シフト結果パリティーの算出と並行に、加算パリティー反転予測回路９５２が加算パリティー反転信号を生成し、加算パリティー反転信号とシフト結果パリティーXP'<1:0>、YP'<1:0>の排他的論理和を取ることによって加算結果のパリティーすなわち平均値演算結果パリティーZP<1:0>を算出する。
【００７３】
このように、このパリティー付平均値算出回路７００は、加算パリティー反転予測回路９５２が加算パリティー反転予測を算出するのと並行してシフトパリティー反転予測回路９６２がシフト結果パリティーを算出するので、平均値演算結果パリティーZP<1:0>を高速に算出することができる。ここで、この高速化について、図８を用いて説明する。
【００７４】
図８は、従来手法と本実施例２に係る手法との処理時間の比較を示す図である。シフト演算は、従来手法では演算結果を１ビットずらして実現でき、本実施例２に係る手法においては入力データをそれぞれ１ビットシフトして加算することで実現できるため、シフト演算時間は両手法とも実質はないと考えられる。
【００７５】
したがって、図８に示すように、平均値算出時間は、実質は加算の時間と等しくなる。この平均値算出時間のうち平均値演算結果パリティーに関しては、従来の手法の場合には、加算結果（タイミングa-1）より遅く求まった加算結果パリティー（タイミングa-2）からさらにシフト結果パリティーを算出して求まることとなる(タイミングa-3)。
【００７６】
これに対して、本実施例２に係る手法の場合には、シフト演算のパリティー算出処理と加算処理が同時に開始することができ(タイミングb-0)、加算への入力パリティーとなるシフト結果パリティーは、加算におけるパリティー検出回路からパリティーの反転論理が求まるまでに(タイミングb-3)求まればよいため、シフト演算のパリティー演算時間（タイミングb-1）は加算処理時間と完全にオーバラップさせることができ、平均値演算処理時間を短縮させることができる（タイミングb-4）。このように、この本実施例２に係る手法をとることで平均値算出演算を高速に行うことが可能となる。
【００７７】
上述してきたように、本実施例２では、２つのシフトパリティー反転予測回路９６２がシフト結果パリティーXP'<1:0>、YP'<1:0>を算出し、このシフト結果パリティーの算出と並行して加算パリティー反転予測回路９５２が加算パリティー反転信号を生成し、加算パリティー反転信号とシフト結果パリティーXP'<1:0>、YP'<1:0>の排他的論理和を取ることによって平均値演算結果パリティーZP<1:0>を算出することとしたので、パリティー付データに対する平均値算出を高速に行うことができる。
【００７８】
（付記１）２つの２進数の平均値を算出する平均値算出装置であって、
前記２つの２進数の最下位ビットから該２進数の平均値演算における最下位ビットへのキャリーを生成するキャリー生成手段と、
前記２つの２進数を右に１ビットシフトした２つの２進数と前記キャリー生成手段により生成されたキャリーを加算して平均値を算出する加算手段と、
を備えたことを特徴とする平均値算出装置。
【００７９】
（付記２）前記２つの２進数はパリティービットを有するパリティー付２進数であり、該２つのパリティー付２進数の平均値のパリティーを予測するパリティー予測手段をさらに備えたことを特徴とする付記１に記載の平均値算出装置。
【００８０】
（付記３）前記パリティー予測手段は、それぞれのパリティー付２進数を右に１ビットシフトした２進数のパリティーを予測する２つのシフトパリティー予測手段と、
前記加算手段により算出される平均値のパリティーを前記２つのシフトパリティー予測手段により予測された２つのパリティーを用いて予測する加算パリティー予測手段と、
を備えたことを特徴とする付記２に記載の平均値算出装置。
【００８１】
（付記４）前記キャリー生成手段は、四捨五入により平均値を求める場合には、前記２つの２進数の最下位ビットに対して論理和演算を行ってキャリーを生成し、切り捨てにより平均値を求める場合には、前記２つの２進数の最下位ビットに対して論理積演算を行ってキャリーを生成することを特徴とする付記１、２または３に記載の平均値算出装置。
【００８２】
（付記５）前記加算手段は、平均値演算が指定された場合に、前記２つの２進数を右に１ビットシフトした２つの２進数と前記キャリー生成手段により生成されたキャリーを加算して平均値を算出し、平均値演算が指定されない場合に、該２つの２進数を加算することを特徴とする付記１〜４のいずれか一つに記載の平均値算出装置。
【００８３】
（付記６）２つの２進数の平均値を算出する平均値算出方法であって、
前記２つの２進数の最下位ビットから該２進数の平均値演算における最下位ビットへのキャリーを生成するキャリー生成工程と、
前記２つの２進数を右に１ビットシフトした２つの２進数と前記キャリー生成工程により生成されたキャリーを加算して平均値を算出する加算工程と、
を含んだことを特徴とする平均値算出方法。
【００８４】
（付記７）前記２つの２進数はパリティービットを有するパリティー付２進数であり、該２つのパリティー付２進数の平均値のパリティーを予測するパリティー予測工程をさらに含んだことを特徴とする付記６に記載の平均値算出方法。
【００８５】
（付記８）前記パリティー予測工程は、それぞれのパリティー付２進数を右に１ビットシフトした２進数のパリティーを予測する２つのシフトパリティー予測工程と、
前記加算工程により算出される平均値のパリティーを前記２つのシフトパリティー予測工程により予測された２つのパリティーを用いて予測する加算パリティー予測工程と、
を含んだことを特徴とする付記７に記載の平均値算出方法。
【００８６】
（付記９）前記キャリー生成工程は、四捨五入により平均値を求める場合には、前記２つの２進数の最下位ビットに対して論理和演算を行ってキャリーを生成し、切り捨てにより平均値を求める場合には、前記２つの２進数の最下位ビットに対して論理積演算を行ってキャリーを生成することを特徴とする付記６、７または８に記載の平均値算出方法。
【００８７】
（付記１０）前記加算工程は、平均値演算が指定された場合に、前記２つの２進数を右に１ビットシフトした２つの２進数と前記キャリー生成工程により生成されたキャリーを加算して平均値を算出し、平均値演算が指定されない場合に、該２つの２進数を加算することを特徴とする付記６〜９のいずれか一つに記載の平均値算出方法。
【産業上の利用可能性】
【００８８】
以上のように、本発明に係る平均値算出装置および平均値算出方法は、計算機の演算装置に有用であり、特に、パリティー付データの平均値を高速に算出する演算装置に適している。
【図面の簡単な説明】
【００８９】
【図１】本実施例１に係る平均値算出手法を説明するための説明図である。
【図２】本実施例１に係る平均値算出回路の構成を示す機能ブロック図である。
【図３】平均値を算出するデータが複数含まれるデータフォーマットの一例を示す図である。
【図４】図３に示したフォーマットのデータの平均値を算出する４並列平均値算出回路の一例を示す図である。
【図５】図３に示したフォーマットのデータの平均値を既存の加算器を用いて算出する手法を説明するための説明図である。
【図６】図３に示したフォーマットのデータの平均値を既存の加算器を用いて算出する４並列平均値算出回路の一例を示す図である。
【図７】本実施例２に係るパリティー付平均値算出回路の構成を示す機能ブロック図である。
【図８】従来手法と本実施例２に係る手法との処理時間の比較を示す図である。
【図９−１】基本的な平均値算出手法を説明するための説明図である。
【図９−２】基本的な平均値算出手法で平均値を算出する平均値算出回路を示す図である。
【図９−３】改善された平均値算出手法を説明するための説明図である。
【図９−４】改善された平均値算出手法で平均値を算出する平均値算出回路を示す図である。
【図９−５】従来のパリティー付加算回路の一例を示す図である。
【図９−６】従来のパリティー付シフタの一例を示す図である。
【図９−７】従来のパリティー予測回路付平均値算出回路の一例を示す図である。
【符号の説明】
【００９０】
２００，６００    平均値算出回路
２１０，６１０，９２１，９４１，９５１    加算器
２２０，６２０    キャリー生成回路（ＣＧＥＮ）
４００    ４並列平均値算出回路
６３０    平均値演算モード信号
７００    パリティー付平均値算出回路
９２２，９４２    シフタ
９２３    丸め回路
９５０    パリティー付加算回路
９５２    加算パリティー反転予測回路
９６０    パリティー付シフタ
９６１    １ビット右シフタ
９６２    シフトパリティー反転予測回路
【図１】
2005182294.tif 000003
【図２】
2005182294.tif 000004
【図３】
2005182294.tif 000005
【図４】
2005182294.tif 000006
【図５】
2005182294.tif 000007
【図６】
2005182294.tif 000008
【図７】
2005182294.tif 000009
【図８】
2005182294.tif 000010
【図９−１】
2005182294.tif 000011
【図９−２】
2005182294.tif 000012
【図９−３】
2005182294.tif 000013
【図９−４】
2005182294.tif 000014
【図９−５】
2005182294.tif 000015
【図９−６】
2005182294.tif 000016
【図９−７】
2005182294.tif 000017