(57)【特許請求の範囲】
【請求項１】
積和演算を行ってその積和演算値がオーバーフローしたときは逐次飽和演算を行う積和演算方法であって、前記積和演算を行うに際して、事前に積和演算対象となる一方の数列の絶対値の総和ともう一方の数列の絶対値の最大値の積を求め、前記積を前記積和演算のとりうる範囲の上限値または下限値とする予備計算を行って前記積和演算による積和演算値のとりうる範囲を調べ、前記範囲から前記オーバーフローの可能性を判断し、前記オーバーフローの可能性ありと判断した場合には、前記逐次飽和演算を行い、前記オーバーフローの可能性なしと判断した場合には、前記逐次飽和演算を含まない積和演算を行うことを特徴とする積和演算方法。
【請求項２】
前記オーバーフローの可能性を判断する処理は、前記上限値または下限値が、逐次飽和演算を行うべき領域を超えたか否かを判定し、前記領域を超えれば前記オーバーフローの可能性有りと判断し、前記領域を超えなければ前記オーバーフローの可能性なしと判断する処理であることを特徴とする請求項１記載の積和演算方法。
【請求項３】
積和演算を行ってその積和演算値がオーバーフローしたときは逐次飽和演算を行う積和演算方法であって、前記積和演算の対象となる一方の数列の絶対値の総和がある値を超えなければオーバーフローの可能性なしと判断できる場合に、前記積和演算を行うに際して、事前に前記一方の数列の絶対値の総和を計算する予備計算を行い、前記総和が前記ある値を超えるか否かを判定するオーバーフローの可能性を判断する処理を行い、前記オーバーフローの可能性を判断する処理において、前記ある値を超えれば前記オーバーフローの可能性ありと判断し、前記逐次飽和演算を行い、前記ある値を超えないと判定された場合は前記オーバーフローの可能性なしと判断し、前記逐次飽和演算を含まない積和演算を行うことを特徴とする積和演算方法。
【請求項４】
積和演算を行ってその積和演算値がオーバーフローしたときは逐次飽和演算を行う積和演算方法において、前記積和演算を行うに際して、事前に積和演算対象となる複数の数列の2乗和を計算し、前記複数の数列の2乗和値の和を求め、前記2乗和値の和を前記積和演算のとりうる範囲の上限値または下限値とする予備計算を行い、前記上限値または下限値が、逐次飽和演算を行うべき領域を超えたか否かを判定するオーバーフローの可能性を判断する処理を行い、前記オーバーフローの可能性を判断する処理において前記領域を超えれば前記オーバーフローの可能性有りと判断し、前記逐次飽和演算を行い、前記領域を超えなければ前記オーバーフローの可能性なしと判断し、前記逐次飽和演算を含まない積和演算を行うことを特徴とする積和演算方法。
【請求項５】
前記予備計算は、前記積和演算対象となる複数の数列の2乗和値の和を、前記数列を構成する要素範囲において１つ以上の要素ごとに逐次的に求めて累積する処理であり、前記オーバーフローの可能性を判断する処理は、前記累積された２乗和値の和が前記逐次飽和演算を行うべき領域を超えるか否かを、前記１つ以上の要素ごとに逐次的に判断する処理であることを特徴とする請求項４記載の積和演算方法。
【請求項６】
前記予備計算は、前記積和演算対象となる数列の要素数をｎとしたときに、前記2乗和値の和の計算をｎより小さい数ｍまで行う処理であり、前記オーバーフローの可能性を判断する処理は、前記ｍまでの２乗和値の和が前記逐次飽和演算を行うべき領域を超えるか否かを判断し、前記ｍまでの２乗和値の和が前記逐次飽和演算を行うべき領域を超えない場合は、ｍ＋１以降の数列の２乗和を計算して、前記ｍ+１以降の数列の２乗和値の和と前記ｍまでの２乗和値の和の累積値を求め、前記累積値が前記逐次飽和演算を行うべき領域を超えるか否かを再度判断する処理であることを特徴とする請求項４記載の積和演算方法。
【請求項７】
前記要素数を分割してそれぞれの予備計算を行う処理を再帰的に行うことを特徴とする請求項６記載の積和演算方法。
【請求項８】
前記積和演算対象となる数列の要素数をｎとしたときに、ｎより小さいｍまでの前記予備計算を行い、前記オーバーフローの可能性がないと判断した場合には、前記ｍまでの積和演算処理を行い、ｍ+１以降の積和演算処理のオーバーフローの可能性の判断は、前記ｍまでの積和演算の結果の絶対値と前記ｍ+１から前記ｎまでの数列の2乗和値の和によって判断することを特徴とする請求項５から７のいずれかに記載の積和演算方法。
【請求項９】
コンピュータに積和演算を行うに際して、事前に積和対象となる一方の数列の絶対値の総和ともう一方の数列の絶対値の最大値の積を求め、前記積を前記積和演算のとりうる範囲の上限値または下限値とする予備計算を行なって前記積和演算による積和演算値のとりうる範囲を調べる手順と、前記予備計算によって得られた積和演算のとりうる範囲からオーバーフローの可能性を判断する手順と、前記オーバーフローの可能性ありと判断した場合には、前記逐次飽和演算を行い、前記オーバーフローの可能性なしと判断した場合には、逐次飽和演算を含まない積和演算を行う手順と、を実行させることを特徴とする積和演算処理プログラム。
【請求項１０】
前記オーバーフローの可能性を判断する処理は、前記上限値または下限値が、前記逐次飽和演算を行うべき領域を超えたか否かを判定し、前記逐次飽和演算を行うべき領域を超えれば前記オーバーフローの可能性有りと判断し、前記逐次飽和演算を行うべき領域を超えなければ前記オーバーフローの可能性なしと判断する処理であることを特徴とする請求項９記載の積和演算処理プログラム。
【請求項１１】
積和対象となる一方の数列の絶対値の総和がある値を超えなければオーバーフローの可能性なしと判断できる場合、コンピュータに積和演算を行うに際して、事前に積和対象となる一方の数列の絶対値の総和を求める予備計算を行う手順と、前記予備計算によって得られた絶対値の総和がある値を超えたか否かを判定し、前記ある値を超えれば前記オーバーフローの可能性有りと判断し、前記ある値を超えなければ前記オーバーフローの可能性なしと判断するオーバーフローの可能性を判断する手順と、前記オーバーフローの可能性ありと判断した場合には、前記逐次飽和演算を行い、前記オーバーフローの可能性なしと判断した場合には、前記逐次飽和演算を含まない積和演算を行う手順と、を実行させることを特徴とする積和演算処理プログラム。
【請求項１２】
コンピュータに積和演算を行うに際して、事前に積和演算対象となる複数の数列の2乗和を計算し、前記2乗和値の和を求め、前記2乗和値の和を当該積和演算のとりうる範囲の上限値または下限値とする予備計算を行う手順と、前記上限値または下限値が、逐次飽和演算を行うべき領域を超えたか否かを判定し、前記逐次飽和演算を行うべき領域を超えれば前記オーバーフローの可能性有りと判断し、前記逐次飽和演算を行うべき領域を超えなければ前記オーバーフローの可能性なしと判断するオーバーフローの可能性を判断する手順と、前記オーバーフローの可能性ありと判断した場合には、前記逐次飽和演算を行い、前記オーバーフローの可能性なしと判断した場合には、前記逐次飽和演算を含まない積和演算を行う手順と、を実行させることを特徴とする積和演算処理プログラム。
【請求項１３】
前記予備計算は、前記積和演算対象となる前記複数の数列の要素の2乗和値の和を、前記数列を構成する要素範囲において１つ以上の要素ごとに逐次的に求めて累積する手順であり、前記オーバーフローの可能性を判断する処理は、前記累積された２乗和値の和が前記逐次飽和演算を行うべき領域を超えるか否かを、前記１つ以上の要素ごとに逐次的に判断する手順であることを特徴とする請求項１２記載の積和演算処理プログラム。
【請求項１４】
前記予備計算は、前記積和演算対象となる数列の要素数をｎとしたときに、前記2乗和値の和の計算をｎより小さい数ｍまで行う手順であり、前記オーバーフローの可能性を判断する処理は、前記ｍまでの２乗和値の和が前記逐次飽和演算を行うべき領域を超えるか否かを判断し、前記ｍまでの２条和値の和が前記逐次飽和演算を行なうべき領域を越えない場合にはｍ＋１以降の数列の２乗和を計算して、前記ｍ+１からｎまでの２乗和値の和と前記ｍまでの２乗和値の和の累積値を求め、前記累積値が前記逐次飽和演算を行うべき領域を超えるか否かを再度判断する手順であることを特徴とする請求項１２記載の積和演算処理プログラム。
【請求項１５】
前記要素数を分割して前記予備計算を行う手順と、前記累積値が前記逐次飽和演算を行うべき領域を超えるか否かを再度判断する手順を再帰的に行うことを特徴とする請求項１４記載の積和演算処理プログラム。
【請求項１６】
前記積和演算対象となる数列の要素数をｎとしたときに、ｎより小さいｍまでの前記予備計算を行い、前記オーバーフローの可能性がないと判断した場合には、前記ｍまでの積和演算処理を行い、ｍ+１以降の積和演算処理のオーバーフローの可能性の判断は、前記ｍまでの積和演算の結果の絶対値と前記ｍ+１から前記ｎまでの数列の2乗和値の和によって判断することを特徴とする請求項１３から１５のいずれかに記載の積和演算処理プログラム。
【請求項１７】
コンピュータに積和演算を行うに際して、事前に積和対象となる一方の数列の絶対値の総和ともう一方の数列の絶対値の最大値の積を求め、前記積を前記積和演算のとりうる範囲の上限値または下限値とする予備計算を行なって前記積和演算による積和演算値のとりうる範囲を調べる手順と、前記予備計算よって得られた積和演算のとりうる範囲からオーバーフローの可能性を判断する手順と、前記オーバーフローの可能性ありと判断した場合には、前記逐次飽和演算を行い、前記オーバーフローの可能性なしと判断した場合には、逐次飽和演算を含まない積和演算を行う手順と、を実行させることを特徴とする積和演算処理プログラムを記録したコンピュータに読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は音声などのデータ処理に用いられる積和演算を効率よく行うようにした積和演算方法および積和演算処理プログラムに関する。
【０００２】
【従来の技術】
音声や画像などのデータ処理は、大量の積和演算を必要とするため、積和演算を高速に実行可能なハードウエアを用い、ＭＡＣ命令によって行われるのが一般的である。
【０００３】
この積和演算を行う際、その積和演算値がオーバーフローを起こすことがしばしばあり、オーバーフローを起こすと、そのオーバーフローがノイズとして現れ、特に音声の場合は、耳障りな音として現れてくる。
【０００４】
そこで、従来から積和演算におけるオーバーフロー対策がとられ、その代表的な対策としては、飽和演算を用いる方法や計算有効桁を増やす方法などがある。
【０００５】
飽和演算は、１回の積和演算を行うごとに、その結果を最大値ＭＡＸ、最小値ＭＩＮと比較し、最大値と最小値の範囲内に収まるように計算値を補正するものである。たとえば、
【０００６】
【数１】
0003726746.tif 000002
【０００７】
のように、２つの数列ｘｉ，ｙｉの積和をｉ＝０，１，・・・，ｎ−１まで行うような積和演算を行う場合、その演算結果が図１０のように単調増加するとすれば、その演算結果が最大値ＭＡＸに達したところで、得られる値をその最大値ＭＡＸでクリッピングする。この図１０の例は、単調増加の例であるが単調減少する場合も同様であり、その場合、ここでは図示しないが、演算結果が最小値ＭＩＮに達したところで得られる値をその最小値ＭＩＮでクリッピングすればよい。
【０００８】
しかし、単調増加するとは限らないので、結局は、図１１のフローチャートで示すアルゴリズムに従った演算を行う。
【０００９】
すなわち、まず、（１）式において、ｉ＝０、Ｚ＝０とし（ステップｓ２０１）、Ｚ＝Ｚ＋ｘｉ・ｙｉを行い（ステップｓ２０２）、Ｚ≦ＭＡＸを判断し（ステップｓ２０３）、 Ｚ≦ＭＡＸを満たさなければ、つまり、Ｚが最大値よりも大きければ、Ｚ＝ＭＡＸとする（ステップｓ２０４）。また、 Ｚ≦ＭＡＸを満たせば、今度は、 Ｚ≧ＭＩＮを判断し（ステップｓ２０５）、 Ｚ≧ＭＩＮを満たさなければ、つまり、Ｚが最小値よりも小さければ、Ｚ＝ＭＩＮとする（ステップｓ２０６）。そして次に、ｉ＝ｉ＋１して（ステップｓ２０７）、ｉ＜ｎを判断し（ステップｓ２０８）、ｉがｎに達していなければ、ステップｓ２０２に戻って、ステップｓ２０２以降の処理を繰り返し行う。
【００１０】
この図１１のフローチャートで示すように、１回の積和演算を行うごとに最大値ＭＡＸおよび最小値ＭＩＮと比較し、その範囲内に積和演算の値が収まるように計算値の修正がなされ、これによって、積和演算結果がオーバーフローすることはなくなる。
【００１１】
一方、計算有効桁を増やす方法としては、例えば、特開平１０−１３４０３２に記載されている技術がある。この特開平１０−１３４０３２には、１６ビット×１６ビットの乗算に対し、６４ビットの積和演算フィールドを用いることで、オーバーフローを起こしにくくすることが記載されている。
【００１２】
【発明が解決しようとする課題】
音声符号化規格G723.1、G729では、積和演算において、図１１で示すような飽和演算を用いることが規定されている。たとえば、１６ビット×１６ビットの積和演算を行ったら、３２ビットで飽和させるというものである。なお、この音声符号化規格は、ビットイグザクトであることが要求されているので、積和演算による誤差が許されない。
【００１３】
そこで問題となるのが、前述した計算有効桁を増やすことによってオーバーフローを起こしにくくする手法を用いた場合であり、この手法では、オーバーフローした以降に、積和演算による結果が違ってくるということである。これは主に、積和演算結果が単調増加（または単調減少）でない場合に問題が生じる。一例として、図１２に示すように、積和演算結果が単調増加でない場合を考える。
【００１４】
計算有効桁を増やすことにより、積和演算による演算結果が、上限である最大値ＭＡＸを超えても計算は可能である。しかしながら、図１２に示すように、ｐ１における積和演算結果Ｚが最大値ＭＡＸを超えたとすると、その点で飽和処理がなされ、その積和演算結果Ｚは最大値ＭＡＸでクリッピングされる。それ以降、実際の演算結果（実線で示す）と、最大値ＭＡＸにてクリッピングされた結果（点線で示す）とに差が出てしまうことになる。なお、前述した（１）式において、ｉ＝０からｉ＝ｎ−１までの積和演算の途中の或る積和演算段階をｐ１，ｐ２，ｐ３，・・・で表すものとする。
【００１５】
たとえば、この図１２の例のように、ｐ２にてそのときの積和演算結果Ｚが減少し始め、ｐ３点で積和演算結果Ｚが最大値ＭＡＸよりも小さくなり、ｐ４で再び増加してｐ５で最大値ＭＡＸを超えるような変化をしたとすると、本来は、ｐ１からｐ３までの積和演算結果Ｚはクリッピングされた値（最大値ＭＡＸ）に保持され、ｐ３からｐ５の最大値ＭＡＸを超えない積和演算結果Ｚ（実線で示す）はそのままの積和演算結果として得られ、ｐ５にて最大値を超えた以降、再び、クリッピングされた値（最大値ＭＡＸ）となるべきである。
【００１６】
しかし、現実的には、ｐ１でクリッピングされた状態（最大値ＭＡＸ）に保持されているので、 ｐ２で計算結果が減少し始めると、その最大値ＭＡＸから減少し始めてしまうといった現象が生じてしまう。
【００１７】
このように、前述の音声符号化規格G723.1、G729を、計算有効桁を増やすことによってオーバーフローに対応する手法（特開平１０−１３４０３２に記載されている技術）によって実現しようとすると、積和演算結果が単調増加（または単調減少）でない場合などで、上述したような問題が生じる。
【００１８】
それを回避するためには、図１１のフローチャートで示したように、１回の積和演算を行うごとに、その結果を最大値ＭＡＸ、最小値ＭＩＮと比較し、最大値ＭＡＸと最小値ＭＩＮの範囲内に収まるように計算値を補正するといった飽和演算を行えばよいが、１回の積和演算ごとにこのような飽和演算（これをここでは逐次飽和演算と呼ぶ）をソフトウエアで行うのは、演算量の増大を招き、処理の高速化を図る上で大きな障害ともなる。
【００１９】
特に、処理対象データが音声データである場合には、音声データは全体的にみれば、大きな信号値が比較的少なく、オーバーフローする可能性は低いにもかかわらず、上述したような逐次飽和演算を行うのは非能率的であるといえる。
【００２０】
そこで本発明は、計算有効桁を増やすことによってオーバーフローを起こしにくくする手法を用いて、音声符号化規格G723.1、G729に適合した処理を行う際、上述した問題点を解決し、できるだけ演算量を少なくして高速な処理を可能とすることを目的としている。
【００２１】
【課題を解決するための手段】
上述の目的を達成するために、本発明の積和演算方法は、積和演算を行ってその積和演算値がオーバーフローしたときは逐次飽和演算を行う積和演算方法であって、前記積和演算を行うに際して、事前に積和演算対象となる一方の数列の絶対値の総和ともう一方の数列の絶対値の最大値の積を求め、前記積を前記積和演算のとりうる範囲の上限値または下限値とする予備計算を行って前記積和演算による積和演算値のとりうる範囲を調べ、前記範囲から前記オーバーフローの可能性を判断し、前記オーバーフローの可能性ありと判断した場合には、前記逐次飽和演算を行い、前記オーバーフローの可能性なしと判断した場合には、前記逐次飽和演算を含まない積和演算を行うことを特徴としている。
【００２２】
また本発明の積和演算方法において、前記オーバーフローの可能性を判断する処理は、前記上限値または下限値が、逐次飽和演算を行うべき領域を超えたか否かを判定し、前記領域を超えれば前記オーバーフローの可能性有りと判断し、前記領域を超えなければ前記オーバーフローの可能性なしと判断する処理であることを特徴としている。
【００２３】
また本発明の積和演算方法は、積和演算を行ってその積和演算値がオーバーフローしたときは逐次飽和演算を行う積和演算方法であって、前記積和演算の対象となる一方の数列の絶対値の総和がある値を超えなければオーバーフローの可能性なしと判断できる場合に、前記積和演算を行うに際して、事前に前記一方の数列の絶対値の総和を計算する予備計算を行い、前記総和が前記ある値を超えるか否かを判定する前記オーバーフローの可能性を判断する処理を行い、前記オーバーフローの可能性を判断する処理において、前記ある値を超えれば前記オーバーフローの可能性ありと判断し、前記逐次飽和演算を行い、前記ある値を超えないと判定された場合は前記オーバーフローの可能性なしと判断し、前記逐次飽和演算を含まない積和演算を行うことを特徴としている。
【００２４】
また本発明の積和演算方法は、積和演算を行ってその積和演算値がオーバーフローしたときは逐次飽和演算を行う積和演算方法において、前記積和演算を行うに際して、事前に積和演算対象となる複数の数列の2乗和を計算し、前記複数の数列の2乗和値の和を求め、前記2乗和値の和を前記積和演算のとりうる範囲の上限値または下限値とする予備計算を行い、前記上限値または下限値が、逐次飽和演算を行うべき領域を超えたか否かを判定するオーバーフローの可能性を判断する処理を行い、前記オーバーフローの可能性を判断する処理において前記領域を超えれば前記オーバーフローの可能性有りと判断し、前記逐次飽和演算を行い、前記領域を超えなければ前記オーバーフローの可能性なしと判断し、前記逐次飽和演算を含まない積和演算を行うことを特徴としている。
【００２５】
また本願発明の積和演算方法において前記予備計算は、前記積和演算対象となる複数の数列の2乗和値の和を、前記数列を構成する要素範囲において１つ以上の要素ごとに逐次的に求めて累積する処理であり、前記オーバーフローの可能性を判断する処理は、前記累積された２乗和値の和が前記逐次飽和演算を行うべき領域を超えるか否かを、前記１つ以上の要素ごとに逐次的に判断する処理であることを特徴としている。
【００２６】
また本願発明の積和演算方法において前記予備計算は、前記積和演算対象となる数列の要素数をｎとしたときに、前記2乗和値の和の計算をｎより小さい数ｍまで行う処理であり、前記オーバーフローの可能性を判断する処理は、前記ｍまでの２乗和値の和が前記逐次飽和演算を行うべき領域を超えるか否かを判断し、前記ｍまでの２乗和値の和が前記逐次飽和演算を行うべき領域を超えない場合は、ｍ＋１以降の数列の２乗和を計算して、前記ｍ+１以降の数列の２乗和値の和と前記ｍまでの２乗和値の和の累積値を求め、前記累積値が前記逐次飽和演算を行うべき領域を超えるか否かを再度判断する処理であることを特徴としている。
【００２７】
また本発明の積和演算方法において、前記要素数を分割してそれぞれの予備計算を行う処理を再帰的に行うことを特徴としている。
【００２８】
また本発明の積和演算方法において、前記積和演算対象となる数列の要素数をｎとしたときに、ｎより小さいｍまでの前記予備計算を行い、前記オーバーフローの可能性がないと判断した場合には、前記ｍまでの積和演算処理を行い、ｍ+１以降の積和演算処理のオーバーフローの可能性の判断は、前記ｍまでの積和演算の結果の絶対値と前記ｍ+１から前記ｎまでの数列の2乗和値の和によって判断することを特徴としている。
【００２９】
また本発明の積和演算プログラムは、コンピュータに積和演算を行うに際して、事前に積和対象となる一方の数列の絶対値の総和ともう一方の数列の絶対値の最大値の積を求め、前記積を前記積和演算のとりうる範囲の上限値または下限値とする予備計算を行なって前記積和演算による積和演算値のとりうる範囲を調べる手順と、前記予備計算によって得られた積和演算のとりうる範囲からオーバーフローの可能性を判断する手順と、前記オーバーフローの可能性ありと判断した場合には、前記逐次飽和演算を行い、前記オーバーフローの可能性なしと判断した場合には、逐次飽和演算を含まない積和演算を行う手順と、を実行させることを特徴としている。
【００３０】
また本発明の積和演算プログラムにおいて、前記オーバーフローの可能性を判断する処理は、前記上限値または下限値が、前記逐次飽和演算を行うべき領域を超えたか否かを判定し、前記逐次飽和演算を行うべき領域を超えれば前記オーバーフローの可能性有りと判断し、前記逐次飽和演算を行うべき領域を超えなければ前記オーバーフローの可能性なしと判断する処理であることを特徴としている。
【００３１】
また本発明の積和演算プログラムにおいて、積和対象となる一方の数列の絶対値の総和がある値を超えなければオーバーフローの可能性なしと判断できる場合、コンピュータに積和演算を行うに際して、事前に積和対象となる一方の数列の絶対値の総和を求める予備計算を行う手順と、前記予備計算によって得られた絶対値の総和がある値を超えたか否かを判定し、前記ある値を超えれば前記オーバーフローの可能性有りと判断し、前記ある値を超えなければ前記オーバーフローの可能性なしと判断するオーバーフローの可能性を判断する手順と、前記オーバーフローの可能性ありと判断した場合には、前記逐次飽和演算を行い、前記オーバーフローの可能性なしと判断した場合には、前記逐次飽和演算を含まない積和演算を行う手順と、を実行させることを特徴としている。
【００３２】
また本発明の積和演算プログラムにおいて、コンピュータに積和演算を行うに際して、事前に積和演算対象となる複数の数列の2乗和を計算し、前記2乗和値の和を求め、前記2乗和値の和を当該積和演算のとりうる範囲の上限値または下限値とする予備計算を行う手順と、前記上限値または下限値が、逐次飽和演算を行うべき領域を超えたか否かを判定し、前記逐次飽和演算を行うべき領域を超えれば前記オーバーフローの可能性有りと判断し、前記逐次飽和演算を行うべき領域を超えなければ前記オーバーフローの可能性なしと判断するオーバーフローの可能性を判断する手順と、前記オーバーフローの可能性ありと判断した場合には、前記逐次飽和演算を行い、前記オーバーフローの可能性なしと判断した場合には、前記逐次飽和演算を含まない積和演算を行う手順と、を実行させることを特徴としている。
【００３３】
また本発明の積和演算プログラムにおいて、前記予備計算は、前記積和演算対象となる前記複数の数列の要素の2乗和値の和を、前記数列を構成する要素範囲において１つ以上の要素ごとに逐次的に求めて累積する手順であり、前記オーバーフローの可能性を判断する処理は、前記累積された２乗和値の和が前記逐次飽和演算を行うべき領域を超えるか否かを、前記１つ以上の要素ごとに逐次的に判断する手順であることを特徴としている。
また本発明の積和演算プログラムにおいて、前記予備計算は、前記積和演算対象となる数列の要素数をｎとしたときに、前記2乗和値の和の計算をｎより小さい数ｍまで行う手順であり、前記オーバーフローの可能性を判断する処理は、前記ｍまでの２乗和値の和が前記逐次飽和演算を行うべき領域を超えるか否かを判断し、前記ｍまでの２条和値の和が前記逐次飽和演算を行なうべき領域を越えない場合にはｍ＋１以降の数列の２乗和を計算して、前記ｍ+１からｎまでの２乗和値の和と前記ｍまでの２乗和値の和の累積値を求め、前記累積値が前記逐次飽和演算を行うべき領域を超えるか否かを再度判断する手順であることを特徴としている。
また本発明の積和演算プログラムにおいて、前記要素数を分割して前記予備計算を行う手順と、前記累積値が前記逐次飽和演算を行うべき領域を超えるか否かを再度判断する手順を再帰的に行うことを特徴としている。
また本発明の積和演算プログラムにおいて、前記積和演算対象となる数列の要素数をｎとしたときに、ｎより小さいｍまでの前記予備計算を行い、前記オーバーフローの可能性がないと判断した場合には、前記ｍまでの積和演算処理を行い、ｍ+１以降の積和演算処理のオーバーフローの可能性の判断は、前記ｍまでの積和演算の結果の絶対値と前記ｍ+１から前記ｎまでの数列の2乗和値の和によって判断することを特徴としている。
また本発明の積和演算プログラム記録媒体は、コンピュータに積和演算を行うに際して、事前に積和対象となる一方の数列の絶対値の総和ともう一方の数列の絶対値の最大値の積を求め、前記積を前記積和演算のとりうる範囲の上限値または下限値とする予備計算を行なって前記積和演算による積和演算値のとりうる範囲を調べる手順と、前記予備計算よって得られた積和演算のとりうる範囲からオーバーフローの可能性を判断する手順と、前記オーバーフローの可能性ありと判断した場合には、前記逐次飽和演算を行い、前記オーバーフローの可能性なしと判断した場合には、逐次飽和演算を含まない積和演算を行う手順と、を実行させることを特徴としている。
【００３４】
このように本発明は、事前に予備計算を行うことによって、積和演算値のとりうる範囲を調べ、その範囲からオーバーフローの可能性を判断し、オーバーフローの可能性ありと判断した場合には、前記逐次飽和演算を行い、オーバーフローの可能性なしと判断した場合には、逐次飽和演算を含まない単純な積和演算を行うようにしているので、オーバーフローの可能性ありと判断された場合のみに従来から行われている逐次飽和演算を行えばよく、始めからすべて逐次飽和演算を行う場合に比べると演算量を大幅に少なくすることができる。
【００３５】
特に、処理対象となるデータが音声データである場合には、全体的にみれば、大きな信号値が少ないので、オーバーフローする可能性は低い。したがって、本発明を適用した場合は、通常の積和演算で済む可能性の方が、逐次飽和演算を行う可能性よりも高い。通常の積和演算は、演算そのものは単純であるので高速処理が可能である。これに対して、逐次飽和演算は判断処理など手間のかかる処理を繰り返し行う必要があるので、通常の積和演算に比べればより多くの演算量が必要となり、総合的に見れば本発明を適用することによって演算量を削減することができ、高速な処理が可能となる。
【００３６】
なお、本発明によって行われる予備計算は、積和対象となる一方の数列の絶対値の総和を計算するとともに、もう一方の数列の絶対値の最大値を計算し、それらの積を求め、その積を当該積和演算のとりうる範囲の上限値または下限値とする処理であり、また、オーバーフローの可能性を判断する処理は、前記予備計算によって得られた当該積和演算の取りうる範囲の上限値または下限値が、逐次飽和演算を行うべき領域を超えればオーバーフローの可能性有りと判断し、逐次飽和演算を行うべき領域を超えなければオーバーフローの可能性なしと判断する処理である。このように、本発明が適用されることによってなされる処理内容は比較的単純な処理であるので、従来のように、たくさんの逐次飽和演算を行う場合に比べれば総合的には演算量を削減することができる。
【００３７】
また、予備計算によって得られた一方の数列の絶対値の総和がある値を超えなければオーバーフローの可能性なしと判断できる場合には、前記一方の数列の絶対値の総和を計算する処理のみを前記予備計算として行えばよい。そして、その場合の前記オーバーフローの可能性を判断する処理は、その予備計算によって得られた絶対値の総和がある値を超える否かを判定し、その値を超えないと判定された場合はオーバーフローの可能性なしと判断し、その値を超えればオーバーフローの可能性ありと判断する処理であるので、処理の簡略化を図ることができる。
【００３８】
これは、たとえば、積和の対象となる数列のうち、一方の数列については絶対値の総和をとるといった予備計算を行うことが可能であるが、他方の数列は時刻ごとの計測値のように予め特定できないデータであるような場合の積和演算に適用することで効果を発揮するものである。その場合、一方の数列だけを予備計算する（絶対値の総和を求める）だけで、その積和演算がオーバーフローするかしないかを判断できるので、音声データ処理に用いられるフィルタ演算における積和演算などに有効なものとなる。
【００３９】
また、本発明によって行われる予備計算は、積和演算対象となる複数の数列の2乗和を計算し、その2乗和値の和を求め、この２乗和値の和を当該積和演算のとりうる範囲の上限値または下限値とする処理であってもよく、このような予備計算を行うことによっても、従来の逐次飽和演算を行う場合に比べれば総合的には演算量を削減することができる。
【００４０】
また、上述した2乗和値の和を当該積和演算のとりうる範囲の上限値または下限値とする予備計算として、積和演算対象となる複数の数列の要素の2乗和値の和を逐次的に求めてそれを累積する処理とした場合も、従来の逐次飽和演算を行う場合に比べれば総合的には演算量を削減することができる。特に、この2乗和値の和を逐次的に求めてそれを累積する予備計算を行う場合は、それぞれの逐次的な予備計算ごとにオーバーフローするか否かを判定することができるので、全体ではオーバーフローすると判定される場合でも、逐次的な予備計算結果ではオーバフローしないと判定される場合もある。これによって、累積された予備計算値が逐次飽和演算を行うべき領域を超えると判定されるまでは、通常の積和演算を行うことができるので、逐次演算を行う確率をより少なくすることができ、積和演算をより高速に行うことができる。
【００４１】
また、前記積和演算対象となる数列の要素数をｎとしたときに、前記2乗和値の和の計算をｎより小さい数ｍまで行う処理を行い、その予備計算結果が、前記逐次飽和演算を行うべき領域を超えるか否かを判断し、当該ｍまでの２乗和値が前記逐次飽和演算を行うべき領域を超えない場合は、ｍ＋１以降の数列の２乗和を計算して、その２乗和値の和とそれまでの２乗和値の和の累積値を求める予備計算を行い、この予備計算による値が前記逐次飽和演算を行うべき領域を超えるか否かを判断する処理とした場合も、従来の逐次飽和演算を行う場合に比べれば総合的には演算量を削減することができる。このように、数列の要素数を分割し、その分割したそれぞれの区間ごとに、累積した予備計算値が逐次飽和演算を行うべき領域を超えるか否かを判定するので、全体ではオーバーフローすると判定される場合でも、ｍまでの区間ではオーバーフローしないと判定される場合もある。これによって、逐次飽和演算を行うべき領域を超えると判定されるまでは、通常の積和演算を行うことができるので、逐次飽和演算を行う確率をより少なくすることができ、積和演算をより高速に行うことができる。
【００４２】
また、この要素数を分割してそれぞれの予備計算を行う処理を再帰的に行うことも可能であり、それによれば、より細分化して逐次飽和演算を行うか否かを判断することができるので、逐次飽和演算を行う確率をより少なくすることができ、積和演算をより高速に行うことができる。
【００４３】
また、前記予備計算を前記積和演算対象となる数列の要素数の途中まで行い、オーバーフローの可能性がないと判断した場合には、そこまでの積和演算処理を行い、以降の積和演算処理のオーバーフローの可能性の判断は、その積和演算の結果の絶対値と残りの数列の要素数の2乗和値の和によって判断することも可能であり、これによれば、逐次飽和演算に進む確率をより小さくすることができ、積和演算をより高速に行うことができる。
【００４４】
【発明の実施の形態】
以下、本発明の実施の形態について説明する。なお、この実施の形態で説明する内容は、本発明の積和演算方法についての説明であるとともに、本発明の積和演算処理プログラムの具体的な処理内容をも含むものである。
【００４５】
本発明の考え方としては、事前に予備計算をして、その積和演算値がとりうる範囲を計算し、その積和演算値がとりうる範囲が飽和演算を行うべき領域を超えたか否かを判定し、飽和演算を行うべき領域を超えていないと判断された場合は、その積和演算はオーバーフローする可能性がないので、通常の積和演算を行い、予備計算による積和演算値のとりうる範囲が飽和演算を行うべき領域を超えると判定された場合は、その積和演算はオーバーフローする可能性があるので、前述した逐次飽和演算を行うというものである。
【００４６】
〔第１の実施の形態〕
この第１の実施の形態における事前に行う予備計算は、積和を行う数列のうち一方の数列については絶対値の総和を計算し、もう一方の数列については絶対値の最大値を計算して、その積を求め、それを当該積和演算のとりうる範囲の上限値または下限値とする。以下、図１のフローチャートを参照しながら詳細に説明する。
【００４７】
図１のフローチャートにおいて、ステップｓ１からステップｓ３までの処理が予備計算を行う部分であり、このステップｓ１からステップｓ３によって予備計算を行い、その予備計算結果（その積和演算値がとりうる範囲の上限値または下限値）が逐次飽和演算を行うべき領域を超えているか否かを判断し（ステップｓ４）、逐次飽和演算を行うべき領域を超えていないと判断された場合は、オーバーフローする可能性がないので、ステップｓ５によって通常の積和演算を行い、予備計算による積和演算値のとりうる範囲が、逐次飽和演算を行うべき領域を超えていると判断された場合は、オーバーフローする可能性があるので、ステップｓ６以降の処理に入り、逐次飽和演算を行う。
【００４８】
なお、ここでの積和演算は前述した（１）式によるものとする。したがって、上述の予備計算は、この場合、まず、積和を行う一方の数列ｘｉの絶対値の総和Ｘと、積和を行う他方の数列ｙｉの絶対値の最大値Ｙを計算する（ｉ＝０，１，２，・・・．，ｎ−１）。すなわち、積和を行う数列ｘｉの絶対値の総和Ｘは、
【００４９】
【数２】
0003726746.tif 000003
【００５０】
で計算される。また、積和を行う数列ｙｉの絶対値の最大値Ｙは、
【００５１】
【数３】
0003726746.tif 000004
【００５２】
で計算される。
【００５３】
このようにして得られた数列ｘｉの絶対値の総和Ｘと、数列ｙｉの絶対値の最大値Ｙとの積Ｘ・Ｙが、（１）式の積和演算がとりうる範囲の上限値または下限値である。その理由について以下に説明する。
【００５４】
上述の（１）式の積和演算におけるｘｉ・ｙｉの計算を行う際、ｘｉとｙｉについて、それぞれが正または負のいずれかをとるかによる組み合わせを考えれば、４通りの組み合わせが存在する。つまり、ｘｉとｙｉがともに正（ｘｉ＞０でｙｉ＞０）、 ｘ１が負でｙｉが正（ｘｉ＜０でｙｉ＞０）、 ｘ１が正でｙｉが負（ｘｉ＞０でｙｉ＜０）、 ｘｉとｙｉがともに負（ｘｉ＜０でｙｉ＜０）の組み合わせが存在する。
【００５５】
ここで、ｘｉとｙｉについてそれぞれの絶対値｜ｘｉ｜，｜ｙｉ｜をとれば、この絶対値｜ｘｉ｜，｜ｙｉ｜の積｜ｘｉ｜・｜ｙｉ｜と、上述の４通りの組み合わせのいずれの組み合わせによるｘｉ，ｙｉの積ｘｉ・ｙｉとの関係は、ｘｉ・ｙｉ≦｜ｘｉ｜・｜ｙｉ｜が成り立つ。これらのことから、
【００５６】
【数４】
0003726746.tif 000005
【００５７】
で表すことができる。さらに、この（４）式において、｜ｙｉ｜のｉを０，１，２，・・・，ｎ−１と変化させたときのｙｉの最大値に置き換えても、当然のことながら（４）式は成り立つ。つまり、（４）式は、
【００５８】
【数５】
0003726746.tif 000006
【００５９】
と表すことができる。なお、この（５）式において、 ｙｉのｉを、０，１，２，・・・，ｎ−１と変化させたときに得られる最大値は１つの値であるので、それをΣの前に出すことができる。よって、（５）式は、
【００６０】
【数６】
0003726746.tif 000007
【００６１】
と表すことができ、この（６）式は、上述の（２）式と（３）式から、
【００６２】
【数７】
0003726746.tif 000008
【００６３】
と表すことができる。さらに、下限値−Ｘ・Ｙを考えれば、（７）式は、
【００６４】
【数８】
0003726746.tif 000009
【００６５】
と表すこともできる。つまり、ｘｉとｙｉにおいて、ｉを０，１，２，・・・，ｎ−１と変化させたときのｘｉとｙｉの積和演算値は、下限値−Ｘ・Ｙと上限値Ｘ・Ｙの間に収まるということがいえる。よって、予備計算を行って、Ｘ・Ｙまたは−Ｘ・Ｙを求めれば、実際の積和演算を行わなくても、その積和演算の値のとりうる範囲は、Ｘ・Ｙと−Ｘ・Ｙの範囲内であるということがわかる。
【００６６】
図１のフローチャートに説明が戻って、ステップｓ１，ｓ２，ｓ３における予備計算で、積和を行う数列ｘｉの絶対値の総和Ｘと、積和を行う数列ｙｉの絶対値の最大値Ｙを求め、さらに、それらの積Ｘ・Ｙを求める（ここでは、上限値のみについて考えるものとする）。
【００６７】
このＸ・Ｙは、 ｘｉとｙｉにおいてｉを０，１，２，・・・，ｎ−１と変化させたときのｘｉとｙｉの積和演算値、つまり、（１）式によって得られる値の上限値であるといえるので、このＸ・Ｙが前述の図４で示した最大値ＭＡＸに対し、Ｘ・Ｙ＜ＭＡＸを判定し（ステップｓ４）、 Ｘ・Ｙが最大値ＭＡＸよりも小さいと判定された場合には、その積和演算はオーバーフローする可能性はないと判定することができる。
【００６８】
図２は、予備計算によって得られたＸ・Ｙが最大値ＭＡＸよりも小さいと判定された場合の、ｘｉとｙｉの積和計算結果の一例を示すもので、この場合、図２で示されるように、ｘｉとｙｉの積和計算値はＭＡＸを超えることはない。
【００６９】
このように、 Ｘ・Ｙが最大値ＭＡＸよりも小さいと判定された場合には、オーバーフローする可能性はないと判定することができ、その場合には、ステップｓ５に示すような通常の積和計算を行う。この通常の積和計算は、たとえば、特開平１０−１３４０３２による積和演算である。
【００７０】
一方、ステップｓ４における処理において、 Ｘ・Ｙが最大値ＭＡＸを超えると判定された場合には、オーバーフローする可能性があるとして、ステップｓ６以降に処理が入る。このステップｓ６以降の処理は、逐次飽和演算処理、つまり、１回の積和演算を行うごとに、その結果を最大値ＭＡＸまたは最小値ＭＩＮと比較し、最大値ＭＡＸと最小値ＭＩＮの範囲内に収まるように計算値を補正するといった演算である。
【００７１】
この逐次飽和演算処理は、（１）式において、まず、積和演算値の最初の値を初期化、つまり、ｉ＝０のときのＺをＺ＝０とし（ステップｓ６）、そのＺにｘｉ・ｙｉを足し算（Ｚ＝Ｚ＋ ｘｉ・ｙｉ）したあとｉ＝ｉ＋１する（ステップｓ７）、そして、その時の｜Z｜と最大値ＭＡＸとの大きさの関係（｜Ｚ｜≦ＭＡＸ）を判断し（ステップｓ８）、｜Ｚ｜≦ＭＡＸであれば、オーバーフローしていないので、ｉ＜ｎを判断し（ステップｓ９）、ｉがｎに達していれば処理が終了し、ｉ＜ｎであれば、ステップｓ７に処理が戻る。
一方、ステップｓ８の処理において、｜Ｚ｜が最大値ＭＡＸを超えると判断された場合には、オーバーフローしたとして、ステップｓ１０の処理を行う。このステップｓ１０では、Ｚの値が正（Ｚ＞０）であれば、Ｚを最大値ＭＡＸにクリッピングし（Ｚ＝ＭＡＸ）、Ｚの値が負（Ｚ＜０）であれば、Ｚを最小値ＭＩＮにクリッピングする（Ｚ＝ＭＩＮ）。そして、ｉ＜ｎを判断し（ステップｓ９）、ｉがｎに達していれば処理が終了し、ｉ＜ｎであれば、ステップｓ７に処理が戻る。
このようにして、ｉ＝０，１，２，・・・として、それぞれのときの｜Ｚ｜を求め、｜Ｚ｜≦ＭＡＸを判断して、｜Ｚ｜が最大値ＭＡＸを超えるごとに飽和処理を行う。なお、この図1のフローチャートに示した逐次飽和演算処理は、Ｚの大きさを絶対値で考え、ｉ＝ｉ＋１の処理を｜Ｚ｜≦ＭＡＸの判断の前に持ってきているので，図１１の逐次飽和演算処理に対して見かけ上は異なるように見えるがその処理内容は図１１と全く同じである。
【００７２】
以上説明したように、予備計算をして、その積和演算値がとりうる範囲としての上限値Ｘ・Ｙを計算し、その上限値Ｘ・Ｙが、最大値（ＭＡＸ）または最小値（ＭＩＮ）の範囲内であると判断された場合は、オーバーフローする可能性がないので、通常の積和演算（ステップｓ５）を行い、予備計算による上限値Ｘ・Ｙが、最大値ＭＡＸを外れると判断された場合は、オーバーフローする可能性があるので、ステップｓ６からステップｓ１３で示される逐次飽和演算を行う。なお、このステップｓ６からステップｓ１３で示される逐次飽和演算は、図１１で示した従来の逐次飽和演算を指している。
【００７３】
このように本発明では、積和演算値がとりうる範囲としての上限値Ｘ・Ｙが、最大値ＭＡＸの範囲を超えると判断された場合には、従来から行われていた逐次飽和演算を行う必要があるが、始めからすべて逐次飽和演算を行う場合に比べるとトータルでの演算量は少なくすることができる。
【００７４】
特に、処理対象となるデータが音声データである場合には、全体的にみれば、大きな信号値が少ないので、オーバーフローする可能性は低い。したがって、本発明を適用した場合は、通常の積和演算を行う可能性の方が、逐次飽和演算を行う可能性よりも高い。通常の積和演算は、演算そのものは単純であるので高速処理が可能である。これに対して、逐次飽和演算は判断処理など手間のかかる処理が多く含まれるので、通常の積和演算に比べればより多くの演算量が必要となり、総合的に見れば本発明を適用することによって演算量を削減することができ、高速な処理が可能となる。
【００７５】
なお、予備計算を行う際、絶対値の総和を計算する処理と、絶対値の最大値を計算する処理は、それぞれの数列を相互に入れ替えて計算しても差し支えない。そして、いずれかの予備計算によって得られた当該積和演算のとりうる範囲の上限値または下限値が最大値ＭＡＸを超えなければ、オーバーフローの可能性なしと判断できる。
【００７６】
たとえば、前述の説明では、ｘｉの絶対値の総和を求め、ｙｉの絶対値の最大値を求めるようにしたが、ｘｉとｙｉを逆に用い、 ｙｉの絶対値の総和を求め、ｘｉの絶対値の最大値を求めるようにしてもよい。そして、どちらかがステップｓ４の条件を満たせばよい。すなわち、 ｘｉの絶対値の総和Ｘとｙｉの絶対値の最大値Ｙの積Ｘ・Ｙが、 Ｘ・Ｙ＜ＭＡＸを満たさなくても、 ｘｉとｙｉを逆に用い、 ｙｉの絶対値の総和Ｙを求め、ｘｉの絶対値の最大値Ｘを求めて、それらの積Ｘ・Ｙが、 Ｘ・Ｙ＜ＭＡＸを満たせば、その積和演算は最大値ＭＡＸを超えないと判断できる。
【００７７】
また、上述の予備計算を行う際、数列ｙｉの絶対値の最大値Ｙ（(3)式参照）を求めなくても、前述の（１）式で示す積和演算がオーバーフローするかどうか判断することができる。これは、予備計算によって得られた絶対値の総和が、ある値を超えなければオーバーフローの可能性なしと判断できるような場合であり、その予備計算によって得られた絶対値の総和が、ある値を超える否かを判定するだけで、その積和演算のオーバーフローの可能性を判断することができる。
【００７８】
たとえば、１６ビット×１６ビットの符号付き積和演算を３２ビットで計算する場合、前述の（２）式で示した数列ｘｉの絶対値の総和Ｘが、0x00010000以下であればオーバーフローは起こらない。その理由は、１６ビットであれば、Ｙ＝max|yi|は、0x00008000以下であるからである。
【００７９】
図３はその場合のフローチャートを示すもので、図１のフローチャートに対して予備計算の処理が異なるだけで、あとは図１と同じである。すなわち、この図３では、積和を行う数列ｘｉの絶対値の総和Ｘ を求めると（ステップｓ１１）、その数列ｘｉの絶対値の総和Ｘが、0x00010000以下であるかどうか（Ｘ≦0x00010000）を判断して（ステップｓ１２）、 Ｘ≦0x00010000であれば、ステップｓ１３の処理（図１におけるステップｓ５と同じ処理）を行い、Ｘ≦0x00010000でなければ、ステップｓ１４からステップｓ１８までの処理（図１におけるステップｓ６からステップｓ１０までと同じ処理）を行う。
【００８０】
この図３で示す処理は、たとえば、
【００８１】
【数９】
0003726746.tif 000010
【００８２】
で示されるようなフィルタ演算に有効なものとなる。このフィルタ演算は音声データ処理などでよく用いられるもので、ｓ(n)という入力信号をフィルタを通すことでｅ(n)という出力を得るものである。（９）式において、ｎは時系列における各時刻に対応する数値であり、ここでは、ｎ＝０，１，・・・，Ｎの値をとり、また、ｉは次数（積和演算回数）を示し、ここではｉ＝０，１，・・・，Ｍの値をとる。
【００８３】
このようなフィルタ演算において、ａｉはこれまで説明したｘｉに対応し、ｓ（ｎ−ｉ）がこれまで説明したｙｉに対応する。なお、ここで、ａｉはフィルタ係数であり、このａｉは予め値を特定することが可能である。また、ｓ（ｎ−ｉ）は時系列における各時刻に対応した観測値であるのでどのような数値が入るかは未知である。そこで、予め値を特定することのできるａｉに注目し、そのａｉの絶対値の総和をとって、その総和をＸとし、そのＸがどのような値をとるかで、（９）式の積和演算がオーバーフローするかしないかを判断することができる。
【００８４】
つまり、上述の例に当てはめて考えると、Ｘ≦0x00010000であれば、（９）式の積和演算はオーバーフローしないと判断でき、すべてのｎについてオーバーフローは起こらないといえる。したがって、その場合は、図３のフローチャートにおけるステップｓ１３の処理で示すように、通常の積和演算処理を行うことができる。また、 Ｘ≦0x00010000でなければ、（９）式の積和演算はオーバーフローする可能性があるとして、その場合は、図３のフローチャートにおけるステップｓ１４からステップｓ１８の処理（逐次飽和演算処理）を行う。
【００８５】
このように、 ｓ（ｎ−ｉ）は時系列における各時刻に対応した観測値であるのでどのような数値が入るかが未知であって、フィルタ係数ａｉはそのフィルタの性能からその値を予め特定できる場合、ａｉの絶対値の総和Ｘを求め、その総和Ｘがどのような値をとるかを調べることで、（９）式の積和演算がオーバーフローするかしないかを判断できる。したがって、 ｓ（ｎ−ｉ）がどのような値であるかにかかわらず、 ａｉの絶対値の総和Ｘのみを予備計算として求めるだけで、（９）式に示す積和演算がオーバーフローするかしないかを判断することができる。
【００８６】
このように、積和の対象となる２つの数列のうち、一方の数列については値を特定することができるが、他方の値が特定できないような場合、その特定することのできる側の絶対値の総和を求めるだけで、その積和演算がオーバーフローするかしないかを判断できるので、この種のフィルタ演算には好都合なものとなり、しかも、その積和演算を行う際、その演算量を削減することができ、高速な処理が可能となる。
【００８７】
次に具体的な例について説明する。ここでは、１６ビットの数列として、以下に示すような２つの数列ａｉ，ｂｉについて考える。この場合、ｉの次数は４（ｉ＝０，１，２，３）とする。
【００８８】
ａｉ＝（5044，32530，−1136，10516）                        （１０）
ｂｉ＝（28744，30360，−21504，−26472）                    （１１）
この２つの数列ａｉ，ｂｉの積和演算Σａｉ・ｂｉを３２ビットで計算することを考える。ここで、まず、ａｉの絶対値の最大値を求めるとともに、ｂｉの絶対値の総和を求めてみる。ａｉの絶対値の最大値max|ai|は、（１０）式から最も大きい値を選べば、
max|ai|＝32530                                              （１２）
である。また、 ｂｉの絶対値の総和Σ｜bi｜は、（１１）式から、28744，30360，−21504，−26472のそれぞれの絶対値を足し算することによって、
Σ｜bi｜＝107080                                             （１３）
と求められる。
【００８９】
次に、これらを乗算、つまり、 max|ai|・Σ｜bi｜を計算すると、 max|ai|・Σ｜bi｜＝3483312400  が得られる。これは、３２ビットのとりうる範囲の上限0x7fffffff（１０進法で表すと、2147483647)を超えるので、上述の２つの数列ａｉ，ｂｉの積和演算Σａｉ・ｂｉはオーバーフローする可能性がある。
【００９０】
このため、今度は、ａｉとｂｉを入れ替えて、つまり、 ｂｉの絶対値の最大値を求め、ａｉの絶対値の総和を求めてみる。ｂｉの絶対値の最大値max|bi|は、（１１）式から最も大きい値を選べば、
max|bi|＝30360                                              （１４）
である。また、 ａｉの絶対値の総和Σ｜ai｜は、5044，32530，−1136，10516のそれぞれの絶対値を足し算することによって、
Σ｜ai｜＝49226                                              （１５）
と求められる。
【００９１】
次に、これらを乗算、つまり、 max|bi|・Σ｜ai｜を計算すると、 max|bi|・Σ｜ai｜＝1494501360が得られる。これは、３２ビットのとりうる範囲の上限0x7fffffff（１０進法で表すと、2147483647)を超えないので、上述の２つの数列ａｉ，ｂｉの積和演算Σａｉ・ｂｉは、オーバーフローの可能性はないと判定できる。ここまでの処理を、図１のフローチャートに対応させれば、ステップｓ１からステップｓ４までの処理である。
【００９２】
そして、ステップｓ４においてオーバーフローの可能性はないと判定されれば、ステップｓ５の処理に入ることができ、逐次飽和演算を行うことなく通常の積和演算で処理することができる。実際にΣａｉ・ｂｉを計算すると、Σａｉ・ｂｉ＝878644528となり、確かにオーバーフローしない。
【００９３】
また、ここで用いた数列ａｉをフィルタ係数としたフィルタ演算を考える。この場合の積和演算式は前述の（９）式で与えられ、（９）式におけるａｉが（１０）式で与えられるとする。
【００９４】
この場合、処理手順としては図３のフローチャートを用いる。したがって、前述したように、 Σ｜ai｜≦0x00010000であれば、（９）式の積和演算はオーバーフローしないと判断できる。ここで、Σ｜ai｜は（１５）式からもわかるように、Σ｜ai｜＝49226であり、これは、0x00010000（＝65536）を超えないので、ｓ（ｎ）が１６ビットである限り、このフィルタ演算はオーバーフローは起こらないといえる。よって、図３におけるフローチャートにおけるステップｓ１３の処理に入ることができ、逐次飽和演算を行うことなく通常の積和演算で処理することができる。
【００９５】
〔第２の実施の形態〕
この第２の実施の形態は前述の第１の実施の形態に対して事前の予備計算の部分が異なるものである。以下、この第２の実施の形態について図４を参照しながら説明する。
【００９６】
図４のフローチャートにおいて、ステップｓ４１とステップｓ４２の処理が予備計算を行う部分である。なお、この場合も積和演算は前述した（１）式によるものとする。
【００９７】
この第２の実施の形態においても、このステップｓ４１とステップｓ４２によって予備計算を行い、その予備計算結果（その積和演算値がとりうる範囲の上限値または下限値）が、逐次飽和演算を行うべき領域を超えているか否かを判断し（ステップｓ４３）、逐次飽和演算を行うべき領域を超えていないと判断された場合は、オーバーフローする可能性がないので、ステップｓ４４によって通常の積和演算を行う。
【００９８】
また、予備計算による積和演算値のとりうる範囲が、逐次飽和演算を行うべき領域を超えていると判断された場合は、オーバーフローする可能性があるので、ステップｓ４５以降の処理に入り、逐次飽和演算を行う。なお、このステップｓ４５からステップｓ５２の処理は図１１で示したフローチャートにおけるステップｓ２０１からステップｓ２０８と同じであるので、ここではその処理手順の説明は省略する。
【００９９】
この第２の実施の形態における予備計算は、前述の（１）式が、
【０１００】
【数１０】
0003726746.tif 000011
【０１０１】
を満たすことを利用して、この（１６）式の右辺を計算するものである。ここで、ｉはｉ＝０，１，２，・・・，ｎ−１である。この（１６）式の右辺の値が（１）式の積和演算がとりうる範囲の上限値または下限値となる。その理由について以下に説明する。
【０１０２】
まず、（ｘｉ＋ｙｉ）２を考えると、この（ｘｉ＋ｙｉ）２は、
（ｘｉ＋ｙｉ）２≧０
である。これを展開すると、
ｘｉ２＋２ｘｉ・ｙｉ＋ ｙｉ２≧０
となり、これは、
２ｘｉ・ｙｉ≧−（ｘｉ２＋ｙｉ２）
と表すことができる。同様に、（ｘｉ−ｙｉ）２を考えると、この（ｘｉ−ｙｉ）２は、
（ｘｉ−ｙｉ）２≧０
である。これを展開すると、
ｘｉ２−２ｘｉ・ｙｉ＋ ｙｉ２≧０
となり、これは、
２ｘｉ・ｙｉ≦（ｘｉ２＋ｙｉ２）
と表すことができる。
【０１０３】
よって、２ｘｉ・ｙｉは、−（ｘｉ２＋ｙｉ２）と（ｘｉ２＋ｙｉ２）との間に存在する。つまり、
−（ｘｉ２＋ｙｉ２）≦２ｘｉ・ｙｉ ≦（ｘｉ２＋ｙｉ２）
で表すことができ、これは、
｜２ｘｉ・ｙｉ｜ ≦（ｘｉ２＋ｙｉ２）                          （１７）
と表せるため、上述の（１６）式が得られる。つまり、ｘｉ，ｙｉの積和の絶対値の総和（(16)式の左辺）は、ｘｉ，ｙｉの２乗和値の和（(16)式の右辺）を超えることはなく、この（１６）式の右辺の値が（１）式の積和演算がとりうる範囲の上限値または下限値であるといえる。
【０１０４】
すなわち、図４において、まず、ステップｓ４１により、
【０１０５】
【数１１】
0003726746.tif 000012
【０１０６】
を計算し、この計算結果Ｓ０を用いて、ステップｓ４２により、
【０１０７】
【数１２】
0003726746.tif 000013
【０１０８】
を計算する。このステップｓ４１とステップｓ４２の予備計算によって求められた２乗和値の和Ｓ０が、（１）式の積和演算がとりうる範囲の上限値または下限値となり、この２乗和値の和Ｓ０が、最大値ＭＡＸと最小値ＭＩＮを超えなければ、積和演算結果は、最大値ＭＡＸと最小値ＭＩＮの間に存在することになり、オーバーフローすることはない。
【０１０９】
なお、通常、積和演算の範囲は正負対象であり、たとえば、３２ビット飽和演算の場合、最大値ＭＡＸとして0x7fffffff、最小値ＭＩＮとして0x80000000が用いられる。ここでは、２つの値の絶対値の小さい方を考慮すればよいので、範囲の対象は最大値ＭＡＸで代表することができる。
【０１１０】
すなわち、図４のフローチャートにおいて、ステップｓ４１とステップｓ４２によって、（１６）式の右辺で示される２乗和値の和Ｓ０を予備計算として求め、その２乗和値の和Ｓ０と最大値ＭＡＸと比較し（ステップｓ４３）、２乗和値の和Ｓ０が最大値ＭＡＸを超えないと判断されれば、積和演算結果は、最大値ＭＡＸと最小値ＭＩＮの間に存在することになり、オーバーフローする可能性はないので、ステップｓ４４における通常の積和演算を行う。
【０１１１】
逆に、２乗和値の和Ｓ０と最大値ＭＡＸと比較し（ステップｓ４３）、２乗和値の和Ｓ０が最大値ＭＡＸを超えると判断された場合は、積和演算結果は、オーバーフローする可能性があるので、ステップｓ４５からステップｓ５２で示される従来の逐次飽和演算を行う。
【０１１２】
図５は本発明を実行するための処理プロセッサが図４のフローチャートにおけるループ部分を実行する際の処理サイクル数の見積もりを従来の逐次飽和演算と比較して示すもので、この処理プロセッサは、加算および乗算に要する処理サイクル数を１、比較に要する処理サイクル数を２、比較してジャンプする処理に要する処理サイクル数を４、ｎ回の単純積和演算に要する処理サイクル数を２ｎと仮定する。この処理サイクル数は処理時間に対応するもので、処理サイクル数が大きいほど多くの処理時間を要することを意味している。
【０１１３】
なお、図１１で示した従来の逐次飽和演算を実行するに要する処理サイクル数を図５（ａ）に示し、図４に示す本発明の第２の実施の形態を実行する要する処理サイクル数を同図（ｂ）に示す。
【０１１４】
上述したような処理サイクル数の仮定において、図１１で示した従来の逐次飽和演算におけるステップｓ２０３の処理ブロックにおいては、ｘｉ・ｙｉの乗算が１回とそれにＺをプラスする加算が１回あるので、合計の処理サイクル数は２であり、ステップｓ２０３の処理ブロックは比較であるので、最短の場合（判断結果がYesの場合）での処理サイクル数は２、ステップｓ２０５の処理ブロックも同様に比較であるので、最短の場合（判断結果がYesの場合）での処理サイクル数は２、また、ステップｓ２０７の処理ブロックは、１回の加算であるのでその処理サイクル数は１、ステップｓ２０８の処理ブロックは、比較してジャンプであるのでその処理サイクル数は４であり、これをｎ回繰り返すので、結局、その合計の処理サイクル数は１１ｎとなる。
【０１１５】
これに対して、本発明の第２の実施の形態である図４のフローチャートにおける処理サイクル数を考える。
【０１１６】
図４におけるステップｓ４１の処理ブロックとステップｓ４２の処理ブロックはともに、積算と加算であるのでその処理サイクル数は２であり、それがｎ回繰り返されることから２ｎの処理サイクル数である。なお、Σに係る１／２や、ステップｓ４２におけるＳ０の加算は、ｎがある程度の大きくなれば無視できるので、ここではそれを無視する。また、ステップｓ４４の処理ブロックも同様に処理サイクル数は２ｎである。
【０１１７】
したがって、ステップｓ４３における判断がYesであれば、合計の処理サイクル数は６ｎ（図５(b)において小計Ａで示す）となる。また、ステップｓ４３における判断がNoの場合は、ステップｓ４１，ｓ４２における合計の処理サイクル数４ｎと逐次飽和演算処理であるステップｓ４５からステップｓ５２の処理サイクル数１１ｎとを合計した１５ｎの処理サイクル数（図５(b)において小計Ｂで示す）となる。
【０１１８】
なお、ステップｓ４３における判断において、Yesとなる確率、つまり、ステップｓ４４の処理（通常の積和演算処理）に進む確率をｐで表せば、小計Ａと小計Ｂを合わせた合計の処理サイクル数は、
ｐ・６ｎ＋（１−ｐ）・１５ｎ＝（１５−９ｐ）ｎ                （２０）と表すことができる。
【０１１９】
これは、たとえば、p=0.5、つまり、ステップｓ４３における判断がステップｓ４４に進む確率とステップｓ４５に進む確率が半々であったとすれば、p=0.5を（２０）式の右辺に代入すると10.5ｎとなり、約１１ｎの処理サイクル数となる。また、 p=1.0、つまり、ステップｓ４３における判断においてステップｓ４４に進む確率が１００％であったとすれば、p=1.0を（２０）式の右辺に代入すると、６ｎとなり、６ｎの処理サイクルとなり、図１１で示す逐次飽和演算の約１／２の処理サイクル数ですむ。
【０１２０】
また、最悪のケースとして、 p=０、つまり、ステップｓ４３における判断において、ステップｓ４５に進む確率、つまり、逐次飽和演算に進む確率が１００％であったとすれば、p=０を（２０）式の右辺に代入すると、１５ｎの処理サイクル数となり、図１１で示す逐次飽和演算の１１ｎを上回ってしまうが、実際には、一般的な積和演算ではオーバーフローにより飽和処理がなされると信号処理としては計算誤差になることから、オーバーフローしにくいように信号のレンジが調整されているので、ｐはある程度の大きさとなるのが普通であり、ｐ＝０となることは殆どないと考えられる。
【０１２１】
ここで、図１１で示す逐次飽和演算よりもこの第２の実施の形態の方が、より処理サイクルを小さく抑えることのできるｐの値を考えると、そのｐは、
（１５−９ｐ）ｎ＜１１ｎ
で求めることができるから、ｐ＞0.44となり、これによって、ｐが0.5より大きければ、図１１で示す逐次飽和演算よりもこの第２の実施の形態の方が、より処理サイクルを小さく抑えることができ、高速な処理が可能となる。
【０１２２】
なお、上述したように、一般的な積和演算ではオーバーフローしにくいように信号のレンジが調整されているので、ｐは0.5よりも十分大きい値になると考えられることから、演算処理の高速化に関しては、この第２の実施の形態の優位性は高いといえる。
【０１２３】
〔第３の実施の形態〕
この第３の実施の形態は上述の第２の実施の形態の変形例ともいうべきものである。すなわち、図４のフローチャートで説明した第２の実施の形態では、予備演算として、（１６）式の右辺をｉ＝０からｉ＝ｎ−１まで計算して、その計算結果と最大値ＭＡＸとを比較するようにしているが、この第３の実施の形態では、（１６）式の右辺を、たとえば、最初はｉ＝０として計算し、その計算結果と最大値ＭＡＸとを比較し、次に、 ｉ＝１として計算してｉ＝０の計算結果とその計算結果との累計を最大値ＭＡＸとを比較するというように、その数列を構成する要素範囲（この場合は、ｉ＝０からｎ−１）において１つ以上の要素ごとに逐次的な予備計算を行うようにしている。以下、この第３の実施の形態を図６のフローチャートを参照しながら説明する。
【０１２４】
図６において、まず、ｉ＝０，Ｓ１＝０，Ｚ＝０とし（ステップｓ６１）、 Ｓ１＝ Ｓ１＋（１／２）ｘｉ２＋（１／２）ｙｉ２の予備計算を行う（ステップｓ６２）。このステップｓ６２の予備計算は、図４におけるステップｓ４１，ｓ４２において、この場合、ｉ＝０としたときの１回分の演算である。
【０１２５】
そして、このステップｓ６２で計算された予備計算結果Ｓ１と最大値ＭＡＸとを比較し（ステップｓ６３）、 Ｓ１≦ＭＡＸを満たさなければ、オーバーフローの可能性があるとして、ステップｓ６４からステップｓ７０の逐次飽和演算を行う。なお、このステップｓ６４からステップｓ７０の逐次飽和演算は、図１１で示したフローチャートにおけるステップｓ２０２からステップｓ２０８と同じ処理であるのでここではその説明は省略する。
【０１２６】
一方、ステップｓ６３における判断の結果、 Ｓ１≦ＭＡＸであれば、オーバーフローの可能性はないとして、Ｚ＝Ｚ＋ｘｉ・ｙｉの積和演算を行い（ステップｓ７１）、次に、ｉ＝ｉ＋１して（ステップｓ７２）、ｉ＜ｎを判断し（ステップｓ７３）、ｉ＜ｎを満たさなければ、ステップｓ６２に戻って、このステップｓ６２以降の処理を繰り返し行う。結果として、ステップｓ６２におけるＳ１には２つの数列ｘｉ，ｙｉの２乗和が累積されて行き、 Ｓ１が最大値ＭＡＸを超えるまで、積和演算の結果がオーバーフローすることはない。
【０１２７】
この第３の実施の形態における図６のフローチャートのステップｓ６２からステップｓ７３の処理ループと従来の逐次飽和演算のフローチャートである図１１のステップｓ２０１からステップｓ２０８の処理ループを比較すると、この第３の実施の形態における図６のフローチャートのステップｓ６２からステップｓ７３の処理ループの方が、条件分岐が１回少ないことがわかる。したがって、この第３の実施の形態は、条件分岐にペナルティの大きな処理プロセッサにおいて、より高速な処理が行える。
【０１２８】
なお、この第３の実施の形態において、上述の説明では、ｉを０から順に１つづプラスして、１回ごとに演算を行うようにしたが、２回ごとあるいは３回ごとというように、複数回づつ計算することもできる。たとえば、２回ごとに行う場合は、ステップｓ６２における演算は、まず、ｉ＝０とｉ＝１についてそれぞれ行い、その演算結果Ｓ１と最大値ＭＡＸとを比較する処理を行ったのち、ステップｓ７１の演算をｉ＝０とｉ＝１についてそれぞれ行うというようにすれば、ステップｓ６３における判断の回数を１／２にすることができ、さらに高速化が図れる。
【０１２９】
〔第４の実施の形態〕
この第４の実施の形態も前述の第２の実施の形態の変形例であるといえる。この第４の実施の形態は、（１）式におけるｉが０からｎ−１までの積和演算において、積和演算するｉ＝０からｉ＝ｎ−１までの区間を分割して予備計算を行うようにすることで処理の高速化を図るものである。以下、この第４の実施の形態の具体例について図７のフローチャートを参照しながら説明する。
【０１３０】
なお、この図７のフローチャートでは、積和演算する区間をｉ＝０からｉ＝ｎ／２までの区間と、ｉ＝（ｎ／２）＋１からｉ＝ｎ−１の区間とに分割して処理を行う例について説明する。
【０１３１】
図７において、ステップｓ８１がこの第４の実施の形態における予備計算（第１の予備計算という）の処理であり、その第１の予備計算結果Ｓ２は、この場合、
【０１３２】
【数１３】
0003726746.tif 000014
【０１３３】
で表される。
【０１３４】
このように、まず、ｉ＝０からｎ／２までの第１の予備計算を行い、その第１の予備計算結果Ｓ2と最大値ＭＡＸとを比較し（ステップｓ８２）、Ｓ2≦ＭＡＸを満たさなければ、ステップｓ８３からステップｓ９０で示される従来の逐次飽和演算を行う。このステップｓ８３からステップｓ９０の逐次飽和演算は、図１１で示したフローチャートにおけるステップｓ２０１からステップｓ２０８と同じ処理であるのでここではその説明は省略する。
【０１３５】
一方、ステップｓ８２における比較の結果、 Ｓ２≦ＭＡＸ であると判断された場合は、（１）式で示される通常の積和演算を行う。ただし、この積和演算はｉ＝０からｉ＝ｎ／２までの積和演算である。
【０１３６】
そして次に、ステップｓ９２において再び予備計算（第２の予備計算という）を行う。この第２の予備計算は、ステップＳ８１における第１の予備計算の次の区間、つまり、この場合、ｉ＝（ｎ／２）＋１からｉ＝ｎ−１までの区間の第２の予備演算を行い、その第２の予備計算結果を第１の予備計算結果に加算するものである。
【０１３７】
つまり、この第２の予備計算では、
【０１３８】
【数１４】
0003726746.tif 000015
【０１３９】
を計算する。そして、その第２の予備計算結果Ｓ２と最大値ＭＡＸとを比較する（ステップｓ９３）。この比較の結果、 Ｓ２≦ＭＡＸを満たさなければ、ステップｓ８４からステップｓ９０で示される従来の逐次飽和演算を行うが、ステップｓ８４に入る前に、逐次飽和演算処理を開始すべきｉの位置（処理開始先頭ポインタという）を指示する。この場合、処理開始先頭ポインタは、ｉ＝（ｎ／２）＋１であるから、それを指示する（ステップｓ９４）。これによって、ステップ８４以降の逐次飽和演算は、処理開始先頭ポインタであるｉ＝（ｎ／２）＋１から開始される。
【０１４０】
一方、ステップｓ９３における比較の結果、 Ｓ２≦ＭＡＸ であると判断された場合は、ステップｓ９１で求められたＺに、ｉをｉ＝（ｎ／２）＋１からｎ−１まで変化させたときの数列ｘｉ，ｙｉの積和演算結果を加算する処理、つまり、
【０１４１】
【数１５】
0003726746.tif 000016
【０１４２】
を行う。
【０１４３】
このように、 ｉが０からｎ−１までの２つの数列ｘｉ，ｙｉの積和演算において、ｉ＝０からｉ＝ｎ−１までの区間を分割してそれぞれ予備計算を行うようにすることにより、あるデータについてｉ＝０からｎ−１までを一度に予備計算するのに比べて無駄な逐次飽和演算を行わなくても済む場合がある。
【０１４４】
すなわち、あるデータについて、ｉ＝０からｎ−１までを一度に予備計算した場合にオーバーフローの可能性有りと判定される場合でも、この第４の実施の形態のような処理を行えば、 たとえば、前半の区間（この例ではｉ＝０からｎ／２）だけはオーバーフローしないと判定される場合もあるので、その場合は、前半の区間は従来の逐次飽和演算を行わなくて済み、結果として、処理をより高速化することができる。
【０１４５】
なお、この第４の実施の形態における区間の分割は、ｉ＝０からｎ−１の間の任意の位置で分割することができる。また、分割してそれをさらに分割するというように、分割を再帰的に繰り返すことも可能であり、これによれば、より速くオーバーフローする可能性の要素数を特定することができ、より高速な処理が可能となる。
【０１４６】
〔第５の実施の形態〕
この第５の実施の形態は、たとえば、前述の第３の実施の形態の説明で用いた図６のフローチャートにおいて、すでにｉ＝０からｍ（ｍ＜ｎとする）までの積和演算処理が終了していて、残りｍ＋１からｎー１までの積和演算がオーバーフローするか否かについて判断するものである。この第４の実施の形態について図８のフローチャートを参照しながら説明する。
【０１４７】
図８のフローチャートは図６のフローチャートに対応するものであるが、予備計算の処理が異なっている。つまり、図８におけるステップｓ１０２の処理が図６におけるステップｓ６２の処理と異なっている。それ以外は図６と同じであるので、この図８の全体的な処理については説明を省略する。
【０１４８】
この図８においては、すでに積和演算処理の終了した積和演算値Ｚ（負側も考えるので｜Ｚ｜とする）をオーバーフローの判断の基準に用いる。つまり、ステップｓ１０２の予備計算を、
Ｓ３＝|Z|＋（１／２）ｘｉ２＋（１／２）ｙｉ２                  （２４）
で行い、この予備計算結果Ｓ３と最大値ＭＡＸとを比較するようにしている（ステップｓ１０３）。
【０１４９】
このように、予備計算を（２４）式のようにしても、その予備計算結果Ｓ１と最大値ＭＡＸの大きさの比較は、図６と同様に適正に判断することができる。すなわち、今、ｉ＝ｍまでの積和演算処理が終了しているとして、その次（ｉ＝ｍ＋１）の積和演算を考える。ここでも、前述したように（１６）式の関係があることを前提にして考える。ここで、ｉ＝ｍ＋１における積和演算は、
【０１５０】
【数１６】
0003726746.tif 000017
【０１５１】
で表すことができる。ここで、
【０１５２】
【数１７】
0003726746.tif 000018
【０１５３】
の関係があることは前述したとおりであるので、（２５）式の右辺に（２６）式を代入すれば
【０１５４】
【数１８】
0003726746.tif 000019
【０１５５】
と表すことができる。この（２７）式は、すでに計算された積和演算値（ｉ＝０からｍまでの積和演算値）に、ｉ＝ｍ＋１における数列ｘｉ，ｙｉの２乗和値の和を加算したものは、ｉ＝０からｉ＝ｍ＋１の数列ｘｉ・ｙｉの積和演算値よりも大きくなることを意味している。
【０１５６】
すなわち、この（２７）式は、その右辺であるｉ＝０からｍまでの積和演算値に、ｉ＝ｍ＋１における数列ｘｉ，ｙｉの２乗和値の和を加算したものが、最大値ＭＡＸよりも小さければ、 ｉ＝０からｉ＝ｍ＋１の数列ｘｉ・ｙｉの積和演算値は最大値ＭＡＸよりも小さくなることを意味している。
【０１５７】
よって、図８のステップｓ１０２で求められた予備計算結果Ｓ1と最大値ＭＡＸとを比較し（ステップｓ１０３）、Ｓ１≦ＭＡＸを満たさなければ、オーバーフローする可能性が有るので、図６と同様、従来の逐次飽和演算（ステップｓ１０４からステップｓ１１０）を行い、 Ｓ１≦ＭＡＸであれば、オーバーフローする可能性が無いので、ステップｓ１１１からステップｓ１１３の処理（図６のステップｓ７１からステップｓ７３と同じ処理）を行う。
【０１５８】
なお、この図８のステップｓ１０２において得られる予備計算結果Ｓ１は、図６のステップｓ６２において得られる同じ時点における予備計算結果Ｓ１よりも小さい値となるので、ステップｓ１０３における判断においては、Yesとなる確率、つまり、通常の積和演算処理に進む確率は、図６の場合よりも大きくなる。よって、積和演算をより高速化することができる。
【０１５９】
また、図９は図７に対して上述したと同様の処理を行った場合のフローチャートを示すもので、図９におけるステップｓ１３２の処理が図７のステップｓ９２の処理と異なり、それ以外は図７と同じであるのでこの図９の全体的な処理については説明を省略する。
【０１６０】
この図９の場合は、図７と同様、予備計算する区間をｉ＝０からｉ＝ｎ／２までと、ｉ＝（ｎ／２）＋１からｉ＝ｎ−１とに分割して処理を行っているが、ｉ＝（ｎ／２）＋１からｉ＝ｎ−１の処理における予備計算（ステップｓ１３２）において、 ｉ＝０からｉ＝ｎ／２までの区間で既に計算された積和演算結果|Z|をステップｓ１２１で計算された予備計算結果Ｓ２の代わりに用いている点が図７と異なっている。
【０１６１】
この図９においても上述の図８と同様に考えることができ、この図９のステップｓ１３２において得られる ｉ＝（ｎ／２）＋１からｉ＝ｎ−１の予備計算結果Ｓ４は、図７のステップｓ９２において得られる同じ時点における予備計算結果Ｓ２よりも小さい値となるので、ステップｓ１３３における判断においては、Yesとなる確率、つまり、通常の積和演算処理（ステップｓ１３５）に進む確率が図７の場合よりも大きくなる。よって、積和演算をより高速化することができる。
【０１６２】
以上説明したようにこれまで説明した第１から第５の実施の形態によれば、事前に予備計算をして、その積和演算値がとりうる範囲を計算し、その積和演算値がとりうる範囲が飽和演算を行うべき領域を超えたか否かを判定し、飽和演算を行うべき領域を超えていないと判断された場合は、その積和演算はオーバーフローする可能性がないので、通常の積和演算を行い、予備計算による積和演算値のとりうる範囲が飽和演算を行うべき領域を超えると判定された場合は、その積和演算はオーバーフローする可能性があるので、前述した逐次飽和演算を行うようにしている。これによって、無駄に逐次飽和演算を行うことが少なくなり、結果として積和演算処理の高速化が図れる。
【０１６３】
なお、本発明は以上説明した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲で種々変形実施可能となるものである。また、本発明は、以上説明した本発明を実現するための処理手順が記述された処理プログラムを作成し、その処理プログラムをフロッピィディスク、光ディスク、ハードディスクなどの記録媒体に記録させておくことができ、本発明はその処理プログラムが記録された記録媒体をも含むものである。また、ネットワークから当該処理プログラムを得るようにしてもよい。
【０１６４】
【発明の効果】
以上説明したように本発明は、事前に予備計算を行うことによって、積和演算値のとりうる範囲を調べ、その範囲からオーバーフローの可能性を判断し、オーバーフローの可能性ありと判断した場合には、前記逐次飽和演算を行い、オーバーフローの可能性なしと判断した場合には、逐次飽和演算を含まない単純な積和演算を行うようにしているので、オーバーフローの可能性ありと判断された場合のみに従来から行われている逐次飽和演算を行えばよく、始めからすべて逐次飽和演算を行う場合に比べると演算量を少なくすることができる。
【０１６５】
特に、処理対象となるデータが音声データである場合には、全体的にみれば、大きな信号値が少ないので、オーバーフローする可能性は低い。したがって、本発明を適用した場合は、通常の積和演算で済む可能性の方が、逐次飽和演算を行う可能性よりも高い。通常の積和演算は、演算そのものは単純であるので高速処理が可能である。これに対して、逐次飽和演算は判断処理など手間のかかる処理を繰り返し行う必要があるので、通常の積和演算に比べればより多くの演算量が必要となり、総合的に見れば本発明を適用することによって演算量を削減することができ、高速な処理が可能となる。
【０１６６】
なお、本発明によって行われる予備計算は、積和対象となる一方の数列の絶対値の総和を計算するとともに、もう一方の数列の絶対値の最大値を計算し、それらの積を求め、その積を当該積和演算のとりうる範囲の上限値または下限値とする処理であり、また、オーバーフローの可能性を判断する処理は、前記予備計算によって得られた当該積和演算の取りうる範囲の上限値または下限値が、逐次飽和演算を行うべき領域を超えればオーバーフローの可能性有りと判断し、逐次飽和演算を行うべき領域を超えなければオーバーフローの可能性なしと判断する処理である。このように、本発明が適用されることによってなされる処理内容は比較的単純な処理であるので、従来のように、たくさんの逐次飽和演算を行う場合に比べれば総合的には演算量を削減することができる。
【０１６７】
また、予備計算によって得られた一方の数列の絶対値の総和がある値を超えなければオーバーフローの可能性なしと判断できる場合には、前記一方の数列の絶対値の総和を計算する処理のみを前記予備計算として行えばよい。そして、その場合の前記オーバーフローの可能性を判断する処理は、その予備計算によって得られた絶対値の総和がある値を超える否かを判定し、その値を超えないと判定された場合はオーバーフローの可能性なしと判断し、その値を超えればオーバーフローの可能性ありと判断する処理であるので、処理の簡略化を図ることができる。これは、たとえば、積和の対象となる数列のうち、一方の数列については絶対値の総和をとるといった予備計算を行うことが可能であるが、他方の数列は時刻ごとの計測値のように予め特定できないデータであるような場合の積和演算に適用することで効果を発揮するものである。その場合、一方の数列だけを予備計算する（絶対値の総和を求める）だけで、その積和演算がオーバーフローするかしないかを判断できるので、音声データ処理に用いら得るフィルタ演算における積和演算などに有効なものとなる。
【０１６８】
また、本発明によって行われる予備計算は、積和演算対象となる複数の数列の2乗和を計算し、その2乗和値の和を求め、この２乗和値の和を当該積和演算のとりうる範囲の上限値または下限値とする処理であってもよく、このような予備計算を行うことによっても、逐次飽和演算を行う場合に比べれば総合的には演算量を削減することができる。
【０１６９】
また、上述した2乗和値の和を当該積和演算のとりうる範囲の上限値または下限値とする予備計算として、積和演算対象となる複数の数列の要素の2乗和値の和を逐次的に求めてそれを累積する処理とした場合も、従来の逐次飽和演算を行う場合に比べれば総合的には演算量を削減することができる。特に、この2乗和値の和を逐次的に求めてそれを累積する予備計算を行う場合は、それぞれの逐次的な予備計算ごとにオーバーフローするか否かを判定することができるので、全体ではオーバーフローすると判定される場合でも、逐次的な予備計算結果ではオーバーフローしないと判定される場合もある。これによって、累積された予備計算値が逐次飽和演算を行うべき領域を超えると判定されるまでは、通常の積和演算を行うことができるので、逐次演算を行う確率をより少なくすることができ、積和演算をより高速に行うことができる。
【０１７０】
また、前記積和演算対象となる数列の要素数をｎとしたときに、前記2乗和値の和の計算をｎより小さい数ｍまで行う処理を行い、その予備計算結果が、前記逐次飽和演算を行うべき領域を超えるか否かを判断し、当該ｍまでの２乗和値が前記逐次飽和演算を行うべき領域を超えない場合は、ｍ＋１以降の数列の２乗和を計算して、その２乗和値の和とそれまでの２乗和値の和の累積値を求める予備計算を行い、この予備計算による値が前記逐次飽和演算を行うべき領域を超えるか否かを判断する処理とした場合も、従来の逐次飽和演算を行う場合に比べれば総合的には演算量を削減することができる。このように、積和演算対処となる数列の要素数を分割し、その分割したそれぞれの区間ごとに、累積した予備計算値が逐次飽和演算を行うべき領域を超えるか否かを判定するので、全体ではオーバーフローすると判定される場合でも、ｍまでの区間ではオーバーフローしないと判定される場合もある。これによって、逐次飽和演算を行うべき領域を超えると判定されるまでは、通常の積和演算を行うことができるので、逐次飽和演算を行う確率をより少なくすることができ、積和演算をより高速に行うことができる。
【０１７１】
また、この要素数を分割してそれぞれの予備計算を行う処理を再帰的に行うことも可能であり、それによれば、より細分化して逐次飽和演算を行うか否かを判断することができるので、逐次飽和演算を行う確率をより少なくすることができ、積和演算をより高速に行うことができる。
【０１７２】
また、前記予備計算を前記積和演算対象となる数列の要素数の途中まで行い、オーバーフローの可能性がないと判断した場合には、そこまでの積和演算処理を行い、以降の積和演算処理のオーバーフローの可能性の判断は、その積和演算の結果の絶対値と残りの数列の要素数の2乗和値の和によって判断することも可能であり、これによれば、逐次飽和演算に進む確率をより小さくすることができ、積和演算をより高速に行うことができる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態の積和演算処理手順を説明するフローチャートである。
【図２】予備計算によって得られた上限値Ｘ・Ｙが最大値ＭＡＸより小さい場合の積和演算値の例を示す図である。
【図３】本発明の積和演算方法の第１の実施の形態の他の例を説明するフローチャートである。
【図４】本発明の第２の実施の形態の積和演算処理手順を説明するフローチャートである。
【図５】本発明の第２の実施の形態の積和演算処理による処理サイクル数と従来の逐次飽和演算による処理サイクル数を比較する図である。
【図６】本発明の第３の実施の形態の積和演算処理手順を説明するフローチャートである。
【図７】本発明の第４の実施の形態の積和演算処理手順を説明するフローチャートである。
【図８】本発明の第５の実施の形態の積和演算処理手順を説明するフローチャートであり、図６で示す積和演算処理手順に対応ししたフローチャートである。
【図９】本発明の第５の実施の形態の積和演算処理手順を説明するフローチャートであり、図７で示す積和演算処理手順に対応ししたフローチャートである。
【図１０】積和演算結果が単調増加する場合の従来の飽和演算処理を説明する図である。
【図１１】従来の逐次飽和演算の処理手順をを説明するフローチャートである。
【図１２】積和演算結果が単調増加でない場合の従来の飽和演算処理を説明する図である。
【符号の説明】
ｘｉ，ｙｉ  積和演算対象となる数列
Ｘ  ｘｉの絶対値の総和
Ｙ  ｙｉの絶対値の最大値
Ｓ０， Ｓ１，Ｓ２，Ｓ３ ，Ｓ４  予備計算結果
【図１】
0003726746.tif 000020
【図２】
0003726746.tif 000021
【図３】
0003726746.tif 000022
【図４】
0003726746.tif 000023
【図５】
0003726746.tif 000024
【図６】
0003726746.tif 000025
【図７】
0003726746.tif 000026
【図８】
0003726746.tif 000027
【図９】
0003726746.tif 000028
【図１０】
0003726746.tif 000029
【図１１】
0003726746.tif 000030
【図１２】
0003726746.tif 000031