内積演算装置および内積演算方法
【課題】乗算器を使用しないハードウェア量の少ない演算器構成で、高並列に適したサイクルタイムの高速化が図れるとともに、ＲＯＭを用いなくても内積演算が効率よくかつ精度低下なく行うことができる内積演算装置および内積演算方法を提供する。
【解決手段】複数の入力ベクトル要素を格納する入力要素レジスタ２と、定数ベクトル要素の２のべき乗項と入力ベクトル要素との部分積を求めるバレルシフタ３と、部分積の累算を行う加減算器４と、加減算器の累算結果が格納されるアキュムレータ５と、アキュムレータ５に格納された累算途中の結果の切捨てを行うシフタ６と、定数ベクトル要素の最下位の２のべき乗項の同じ項にかかる全ての入力ベクトル要素の部分積の累算を行わせて順次高位の２のべき乗項にかかる部分積の累算を繰り返して最上位の２のべき乗項まで繰り返させる演算制御手段と、を備えている。
【解決手段】複数の入力ベクトル要素を格納する入力要素レジスタ２と、定数ベクトル要素の２のべき乗項と入力ベクトル要素との部分積を求めるバレルシフタ３と、部分積の累算を行う加減算器４と、加減算器の累算結果が格納されるアキュムレータ５と、アキュムレータ５に格納された累算途中の結果の切捨てを行うシフタ６と、定数ベクトル要素の最下位の２のべき乗項の同じ項にかかる全ての入力ベクトル要素の部分積の累算を行わせて順次高位の２のべき乗項にかかる部分積の累算を繰り返して最上位の２のべき乗項まで繰り返させる演算制御手段と、を備えている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、離散コサイン変換などの直交変換において行われるベクトル内積を演算する内積演算装置および内積演算方法に関する。
【背景技術】
【０００２】
ベクトル内積演算は、画像圧縮処理などの分野で多用される離散コサイン変換に代表される直交変換の中核をなす演算であるが、その演算量が膨大となるため実時間処理など高速処理の要求に応えるためには、一般的には大規模なハードウェア量が必要となり装置のコストは増大する傾向にある。以下に内積演算の応用される離散コサイン変換（Discrete Cosine Transform：以下、ＤＣＴという）処理について簡単に説明を行う。以下の式が１次元の数列に対する、Ｎ次ＤＣＴの一般式である。
【０００３】
【数１】
【０００４】
前記式をＮ＝８とした８次のＤＣＴ処理は以下の行列積の式で表される。
【０００５】
【数２】
【０００６】
この式の右辺の行列はＤＣＴ係数行列と称され、小数点数値表現すると以下の行列となる。
【０００７】
【数３】
【０００８】
このような行列式をデジタルハードウェア演算装置で処理するために、例えば固定小数点演算用に正負符号と１０ビット桁の整数で表すと以下の整数行列式となる。
【０００９】
【数４】
【００１０】
平面画像信号を対象とするＤＣＴ処理は前記式のごとく８次のものが多く、例えばＪＰＥＧ（Joint Photographic Experts Group）方式で用いられるＤＣＴは水平方向８画素、垂直方向８画素の８×８画素について、垂直方向の１次元ＤＣＴを施したのち水平方向の１次元ＤＣＴを施して８×８の２次元平面上の周波数成分に分解する、所謂２次元ＤＣＴとして採用されている。以降、説明を容易にするため、入力ベクトルの要素は画素値として一般的な８ビット整数値、ＤＣＴ係数は典型的なハードウェア構成として一般的な８から１６ビット程度の固定小数点表現とする。
【００１１】
ここで数４において、出力ベクトルＺの要素であるＺ１の計算に着目するとＤＣＴ係数行列の２行目の枠で囲まれた部分行ベクトル（５０２，４２６，２８４，１００，−１００，−２８４，−４２６，−５０２）と入力ベクトル（Ｘ０，Ｘ１，Ｘ２，Ｘ３，Ｘ４，Ｘ５，Ｘ６，Ｘ７）の内積演算に他ならず、８回の乗算と７回の加減算が必要となる。このように内積演算は多くの乗算と加算を内包しその演算量が多く、高速に処理するためのハードウェアが多く考案されている。
【００１２】
図１５に従来の内積演算装置の例を示す。図１５に示された内積演算装置１００は、加減算器１０１、１０２、１０３、１０４と、レジスタ１０５、１０６、１０７、１０８と、乗算器１０９、１１０、１１１、１１２と、並列加算器１１３と、備えている。
【００１３】
図１５の内積演算装置１００は、入力ベクトルＸの各要素とＤＣＴ係数の乗算を入力ベクトルＸの要素ごとに乗算器１０９、１１０、１１１、１１２で並列に実行し、それぞれの乗算結果を並列加算器１１３で総和することで内積演算を実行する。入力ベクトルの要素Ｘ０〜Ｘ７は一括してそれぞれの乗算器１０９、１１０、１１１、１１２に並列に入力され、ＤＣＴ係数は定数であることからレジスタに置かれ乗算器１０９、１１０、１１１、１１２に入力される。なお、ＤＣＴ係数はＲＯＭに格納しても良い。
【００１４】
ここで、内積にかかるＤＣＴ係数行列の部分行ベクトルを（Ｃ０，Ｃ１，Ｃ２，Ｃ３，Ｃ４，Ｃ５，Ｃ６，Ｃ７）とすると、ＤＣＴ係数の性質上Ｃ０とＣ７、Ｃ１とＣ６、Ｃ２とＣ５,Ｃ３とＣ４の絶対値が対称関係となるため、対称な係数に対応する入力Ｘの要素すなわちＸ０とＸ７、Ｘ１とＸ６、Ｘ２とＸ５,Ｘ３とＸ４の加算または減算を係数の正負符号にあわせて先に行うことで（バタフライ演算）、乗算回数を４回に減じたハードウェア構成となっている。
【００１５】
しかしながら上述した構成は乗算回数分の複数の乗算器が必要となることが本質であり、乗算器は一般的にハードウェア規模が大きく、費やす素子数、回路面積、消費電力が大きいうえに、演算桁数が増えると回路内の伝播遅延によりサイクルタイムが低下する問題点がある。また、処理の高速化のために複数の内積結果を複数の内積演算器で同時並列に実行しうるように並列化した演算器構成を構築することもできるが、個々の演算器のハードウェア規模が大きいと、ハードウェア資源であるシリコン面積、電子プリント基板面積は、有限かつ小型化を求められるため大規模に並列化することが困難となる問題点もある。さらに、回路規模の制約から、乗算器や加減算器の桁数の制限がある場合は、入力桁を丸めたり、あるいは積項の乗算結果を丸めたりする必要があり、真の下位桁からの部分積の累算が行われず演算精度が低下するという欠点があった。
【００１６】
また、乗算器を使用しない内積演算装置としては、例えば特許文献１や２に記載のものが提案されている。図１６に乗算器を使用しない内積演算装置の例を示す。図１６に示された内積演算装置２００は、ＲＯＭ２０１と、加減算器２０２と、アキュムレータ２０３と、シフタ２０４と、備えている。
【００１７】
図１６に示された内積演算装置２００は、Ａ〜Ｄが入力ベクトル要素で４ビット幅、定数ベクトル要素Ｃ０〜Ｃ３は１６ビット幅としている。内積演算装置２００では、定数ベクトルの各要素が固定値であることから、入力ベクトルとの内積演算において、入力ベクトルが４ビット幅であることからこれをｂ３，ｂ２，ｂ１，ｂ０と二進値で表すと、入力ベクトルにおける最下位のビットスライスはＡ（ｂ０），Ｂ（ｂ０），Ｃ（ｂ０），Ｄ（ｂ０）と表され、これに対する部分内積は、Ｃ０×Ａ（ｂ０）＋Ｃ１×Ｂ（ｂ０）＋Ｃ２×Ｃ（ｂ０）＋Ｃ３×Ｄ（ｂ０）となる。
【００１８】
Ａ（ｂ０），Ｂ（ｂ０），Ｃ（ｂ０），Ｄ（ｂ０）はそれぞれ、１か０の２値の値しかとらないため、ビットスライスに対する部分内積はＣ０〜Ｃ３の単純な加減算に帰結する。Ｃ０〜Ｃ３は固定値の定数ベクトルであるから、ビットスライスＡ（ｂ０），Ｂ（ｂ０），Ｃ（ｂ０），Ｄ（ｂ０）の出現パターンにしたがって、予め計算された部分内積をＲＯＭ２０１に格納しておき、演算では入力ベクトルのビットスライスのビットパターンによりＲＯＭ２０１を読み出すことにより部分内積を読み出すことができる。これをＲＯＭアキュムレータと称しＲＡＣと略称される。内積演算では、最下位のビットスライスから始めて上位に向かって部分内積を累算してゆくことで内積演算が達成される。部分内積の累算は加減算器２０２とアキュムレータ２０３で行われ、アキュムレータ２０３をシフタ２０４で右シフトして上位桁の累算を開始する。
【００１９】
図１６に示された内積演算装置２００では、シフトと加減算で内積演算が実現可能でありハードウェア量が少ないこと、部分内積の演算がＲＡＣとしてＲＯＭ化されているので高速に動作すること、下位桁の部分内積から順に累算してゆくので必要な結果精度に応じて、演算器の語長を選択できてかつそれが乗算の演算語長より小さな桁の構成であっても、下位桁からの部分内積の累算を完遂しているので演算精度が確保される利点がある。
【発明の概要】
【発明が解決しようとする課題】
【００２０】
上述したように、従来の専用の乗算回路と加減算器とアキュムレータとを有するような積和演算装置では、乗算回路の回路量が大きくなり、コストが増大する問題点があった。乗算回路は特に配列型の乗算器を有する場合は、その回路内容が複雑で規則性が低下し、かつ個々のハードウェア量が大きいことから、複数演算器を大規模に並列に構成するようなＳＩＭＤ（Single Instruction-stream Multiple Data-stream）型の演算器構成を選択することが困難であった。また、乗算回路を有する装置では乗算回路が複雑かつ大規模であるために信号伝播時間が増大し演算装置全体のサイクルタイムが低下する問題点があった。さらに、小規模な演算ブロックを大規模高並列に構成して内積演算装置を構成する場合や、既定のマイクロプロセッサなどの演算装置で内積演算をプログラミングするような場合などでは、演算桁数に制限があることから入力自身の桁数を落としたり、あるいは積項の乗算結果を丸めたりして途中の演算桁を制限せざるを得ず、内積演算の精度が落ちてしまうという問題点があった。
【００２１】
また、ＲＯＭアキュムレータを用いて部分内積の累積加減算とシフト動作によって内積演算を行う内積演算装置は、下位桁から順に部分内積を累算してゆく構造であるため、積項の演算精度がすべて保証され、内積演算の精度低下はないが、ＲＯＭアキュムレータの有するＲＯＭの容量は、入力の語長と内積を行うベクトルの要素数すなわち積項の数が増大するにしたがって増大してしまうという問題点があった。このことは、大規模な並列演算器を構成する場合、同一のＲＯＭを多数複製せざるを得ず、ハードウェア面積の利用効率も悪く並列化の規模が制限されてしまう問題点もあった。
【００２２】
本発明はかかる問題を解決することを目的としている。
【００２３】
すなわち、本発明は、乗算器を使用しないハードウェア量の少ない演算器構成で、高並列に適してサイクルタイムの高速化が図れるとともに、ＲＯＭを用いなくても内積演算が精度低下なく行うことができる内積演算装置および内積演算方法を提供することを目的としている。
【課題を解決するための手段】
【００２４】
上記課題を解決するためになされた請求項１に記載された発明は、所定のビット語長を有する複数の入力ベクトル要素から構成される入力ベクトルと複数の定数ベクトル要素から構成される定数ベクトルとの内積を求める内積演算装置において、前記複数の入力ベクトル要素を格納する格納手段と、前記格納手段から前記入力ベクトル要素を選択して、選択された前記入力ベクトルを左ビットシフトさせることにより前記定数ベクトル要素の２のべき乗項と入力ベクトル要素との部分積を求めるシフト手段と、前記シフト手段が求めた前記部分積を累算するとともに、前記入力ベクトル要素と前記定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成された加減算手段と、前記加減算手段の累算結果を格納するアキュムレータと、予め定めた桁数のビットシフトにより前記加減算手段による累算途中の前記アキュムレータに格納された結果の切り捨てを行って演算結果の丸めを行う丸め手段と、前記加減算手段に、前記定数ベクトル要素の最下位の２のべき乗項の同じ項にかかる全ての入力ベクトル要素の部分積の累算を行わせて前記アキュムレータに格納させて、以降、順次高位の２のべき乗項にかかる部分積の累算を繰り返して最上位の２のべき乗項まで繰り返させるとともに、前記加減算手段の桁あふれが発生する前に前記丸め手段により類算途中の前記アキュムレータに格納された結果の下位桁を切捨てさせて、以降の累算の初期値とするように動作させる演算制御手段と、を備えていることを特徴とする内積演算装置である。
【００２５】
請求項２に記載された発明は、請求項１に記載された発明において、前記演算制御手段が、予め定めたテーブルに基づいて、前記シフト手段に対して前記入力ベクトル要素の２ビット毎に前記部分積を求めさせ、前記加減算手段に対して該部分積を累算させることを特徴とするものである。
【００２６】
請求項３に記載された発明は、請求項１または２に記載された発明において、前記丸め手段が前記加減算手段による累算途中の前記アキュムレータに格納された結果の切り捨てを行うビット桁数は、前記加減算手段のビット語長から前記入力ベクトル要素のビット語長および前記入力ベクトル要素数の２を底とする対数を減じた数以下のビット桁数として予め定められていることを特徴とするものである。
【００２７】
請求項４に記載された発明は、所定のビット語長を有する複数の入力ベクトル要素から構成される入力ベクトルと複数の定数ベクトル要素から構成される定数ベクトルとの内積を求める内積演算装置において、前記複数の入力ベクトル要素を格納する格納手段と、前記格納手段から前記入力ベクトル要素を選択して、前記定数ベクトル要素の２のべき乗項と選択された前記入力ベクトル要素との部分積を求めて累算するとともに、前記入力ベクトル要素と前記定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成された加減算手段と、前記加減算手段の累算結果を自身の上位桁側に格納するアキュムレータと、前記アキュムレータの内容を下位桁方向に右ビットシフトして以降の累算値とするとともに、前記入力ベクトル要素と前記定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成された第一シフト手段と、前記加減算手段に、前記定数ベクトル要素の同じ桁の２のべき乗項の同じ項にかかる全ての入力ベクトル要素の部分積の累算を行わせて前記アキュムレータに格納させて、前記第一シフト手段に前記アキュムレータに格納された累算結果を右ビットシフトさせる動作を前記定数ベクトル要素の２のべき乗項の最上位桁まで繰り返させる演算制御手段と、を備えていることを特徴とする内積演算装置である。
【００２８】
請求項５に記載された発明は、請求項４に記載された発明において、前記格納手段に格納された前記入力ベクトル要素を２倍する第二シフト手段を備え、前記演算制御手段が、予め定めたテーブルに基づいて、前記格納手段に格納された前記入力ベクトル要素または前記第二シフト手段が２倍にした入力ベクトル要素のいずれかを選択して前記加減算手段に累算させるとともに、前記第一シフト手段に２ビットシフトさせることを特徴とするものである。
【００２９】
請求項６に記載された発明は、所定のビット語長を有する複数の入力ベクトル要素から構成される入力ベクトルを格納する格納手段と、前記入力ベクトルを左ビットシフトさせることにより複数の定数ベクトル要素から構成される定数ベクトルの２のべき乗項と前記入力ベクトル要素との部分積を求めるシフト手段と、前記シフト手段が求めた前記部分積を累算するとともに、前記入力ベクトル要素と前記定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成された加減算手段と、前記加減算手段の累算結果を格納するアキュムレータと、を備えたマイクロプロセッサでオペランドの加減算とシフトが一体に実行可能な命令を用いて前記入力ベクトルと前記定数ベクトルとの内積を求める内積演算方法において、前記シフト手段が前記格納手段から前記入力ベクトル要素を選択して前記部分積を求める第一の工程と、前記加減算手段に、前記定数ベクトル要素の最下位の２のべき乗項の同じ項にかかる全ての前記入力ベクトル要素の前記部分積の累算を行わせて前記アキュムレータに格納させる第二の工程と、前記加減算手段の桁あふれが発生する前に前記アキュムレータに格納させている類算途中の前記アキュムレータに格納された結果の下位桁を切捨てて、以降の累算の初期値とする第三の工程と、を備え、前記第一の工程と前記第二の工程を順次高位の２のべき乗項にかかる部分積の累算を繰り返して最上位の２のべき乗項まで繰り返すとともに、前記第一の工程と前記第二の工程の繰り返しの途中に少なくとも前記第三の工程を１回以上行うことを特徴とする内積演算方法である。
【００３０】
請求項７に記載された発明は、請求項６に記載された発明において、前記第一の工程は、前記入力ベクトル要素自身または前記入力ベクトル要素の２倍の値のいずれかを選択して前記部分積を求め、前記第二の工程は、前記部分積の累算を２ビット毎に行うことを特徴とするものである。
【００３１】
請求項８に記載された発明は、請求項６または７に記載の発明において、前記第三の工程で前記加減算手段による累算途中の前記アキュムレータに格納された結果の切り捨てを行うビット桁数は、前記加減算手段のビット語長から前記入力ベクトル要素のビット語長および前記入力ベクトル要素数の２を底とする対数を減じた数以下のビット桁数として予め定められていることを特徴とするものである。
【発明の効果】
【００３２】
請求項１に記載の発明によれば、乗算回路を使用せず、加減算手段とアキュムレータとシフト手段とを有する累積加減算構造で装置を構成するために、規則性が高く、高並列に適したハードウェア量の小さい演算装置を構成できる。また、下位桁から順に部分積の累算を実行し、上位桁に必ず下記桁の部分積和結果が反映されるので演算精度が低下することなく内積演算を行うことができる。また、累算途中でアキュムレータの内容を丸め手段によって右シフトして丸めることができるので、積項の乗算語長より小さい桁数の加減算器とアキュムレータであっても桁あふれを起こすことなく精度低下のない内積演算を行うことができる。
【００３３】
請求項２に記載の発明によれば、演算制御手段が、ブースのアルゴリズムを適用して、定数ベクトルの２ビット毎の部分積の累算を行わせることができ、制御ステップが削減され、さらに少ないサイクル数で演算することができる。
【００３４】
請求項３に記載の発明によれば、積項の乗算語長より小さい桁数の加減算器とアキュムレータであっても、確実に桁あふれを起こさずに内積演算を行うことができる。
【００３５】
請求項４に記載の発明によれば、乗算回路を使用せず、加減算手段とアキュムレータと、シフト手段を有する累積加減算構造で装置を構成するために、規則性が高く、高並列に適したハードウェア量の小さい演算装置を構成できる。また、下位桁から順に部分積の累算を実行するよう動作するため、上位桁に必ず下位桁の部分積和結果が完遂し反映されるので演算精度が低下することなく内積演算を行うことができる。また、累算途中でアキュムレータの内容を右シフトして丸めることができるので、積項の乗算語長より小さい桁数の加減算器とアキュムレータを有する演算装置であっても桁あふれを起こすことなく、精度低下のない内積演算を行うことができる。さらに、入力を任意桁左シフトするためのバレルシフタを有しないので、さらに回路規模を小さくすることができる。
【００３６】
請求項５に記載の発明によれば、演算制御手段が、ブースのアルゴリズムを適用して、定数ベクトルの２ビット毎の部分積の累算を行うことができ、制御ステップが削減され、さらに少ないサイクル数で演算することができる。
【００３７】
請求項６に記載の発明によれば、オペランドのシフトが一体となった加減算命令を持つマイクロプロセッサにおいて、下位桁から順に部分積の累算を実行するので、上位桁に必ず下記桁の部分積和結果が完遂し反映されるために演算精度が低下することなく内積演算を行うことができる。また、累算途中でアキュムレータの内容を右シフトして丸める第三のステップを備えるのでので、積項の乗算語長より小さい桁数の加減算器とアキュムレータを有する演算装置でも桁あふれを起こすことなく精度低下のない内積演算を行うことができる方法が提供できる。
【００３８】
請求項７に記載の発明によれば、ブースのアルゴリズムを適用して、定数ベクトルの２ビット毎の部分積の累算を行うので、累算すべき部分積の数が削減され、実行命令数をさらに少なくすることができる。
【００３９】
請求項８に記載の発明によれば、積項の乗算語長より小さい桁数の加減算器とアキュムレータを備えた演算装置であっても、確実に桁あふれを起こさずに内積演算を行うことができる。
【図面の簡単な説明】
【００４０】
【図１】本発明の第１の実施形態にかかる内積演算装置の構成図である。
【図２】図１に示された内積演算装置の内積演算動作を示したプログラムリストである。
【図３】本発明の第２の実施形態にかかる内積演算装置に適用されるブースのアルゴリズム表である。
【図４】本発明の第２の実施形態にかかる内積演算装置の内積演算動作を示したプログラムリストである。
【図５】本発明の第３の実施形態にかかる内積演算装置の構成図である。
【図６】図５に示された内積演算装置の内積演算動作を示したプログラムリストである。
【図７】本発明の第４の実施形態にかかる内積演算装置の構成図である。
【図８】図７に示された内積演算装置の内積演算動作を示したプログラムリストである。
【図９】本発明の第５の実施形態にかかる内積演算方法を実行するマイクロプロセッサの演算器部分の構成図である。
【図１０】図９に示したマイクロプロセッサの機械語命令コードフォーマットである。
【図１１】図９に示したマイクロプロセッサの内積演算動作を示したプログラムリストの一の部分である。
【図１２】図９に示したマイクロプロセッサの内積演算動作を示したプログラムリストの他の部分である。
【図１３】図９に示したマイクロプロセッサで動作する内積演算方法のフローチャートである。
【図１４】本発明の第６の実施形態にかかるマイクロプロセッサの内積演算動作を示したプログラムリストである。
【図１５】従来の内積演算装置を示した構成図である。
【図１６】従来の内積演算装置を示した構成図である。
【発明を実施するための形態】
【００４１】
（第１実施形態）
以下、本発明の第１の実施形態を、図１および図２を参照して説明する。図１は、本発明の第１の実施形態にかかる内積演算装置の構成図である。図２は、図１に示された内積演算装置の内積演算動作を示したプログラムリストである。
【００４２】
図１に本発明の第１の実施形態にかかる内積演算装置１を示す。図１に示した内積演算装置１は、入力要素レジスタ２と、バレルシフタ３と、加減算器４と、アキュムレータ５と、シフタ６と、セレクタ７と、制御部８と、を備えている。
【００４３】
格納手段としての入力要素レジスタ２は、８ビット語長でＲ０〜Ｒ７までの８つのレジスタから構成される。各レジスタに入力ベクトル要素（例えば、数４のＸ０〜Ｘ７）が格納され、制御部８からの制御信号により１つのレジスタが選択されバレルシフタ３に出力される。
【００４４】
シフト手段としてのバレルシフタ３は、入力された入力ベクトル要素を任意の桁数の左シフトを行い、加減算器４の一方の入力に接続される。本実施例では、入力８ビット出力１６ビット語長で、０〜９ビット桁の符号拡張付きの左シフト機能を有する。バレルシフタ３のシフト量は、制御部８からの制御信号によりサイクル毎に選択される。
【００４５】
加減算手段としての加減算器４は、制御部８からの制御信号によりサイクル毎に加算か減算かの動作が選択される入出力とも１６ビットの語長を有する演算器である。すなわち、入力ベクトル要素と定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成されている。加減算器４の出力は、アキュムレータ５に接続される。
【００４６】
アキュムレータ５は、加減算器４による途中および最終の演算結果が格納される１６ビットのレジスタである。アキュムレータ５の出力はシフタ６に接続される。
【００４７】
丸め手段としてのシフタ６は、１６ビット語長で、アキュムレータ５に格納された演算結果を、制御部８からの制御信号により５ビット固定桁の右シフトを行い、演算途中結果の切捨て丸めを行うことができる構成となっている。
【００４８】
セレクタ７は、制御部８からの制御信号によりシフタ６の出力とアキュムレータ５の出力とを選択して加減算器４の他方の入力に接続されるとともに、演算結果として外部へ出力する。
【００４９】
演算制御手段としての制御部８は、内積演算装置１の演算動作を制御し、演算動作ステップに応じて制御信号を、入力要素レジスタ２、バレルシフタ３、加減算器４、アキュムレータ５、シフタ６、セレクタ７に出力する。
【００５０】
上述した構成の内積演算装置１は、ベクトル内積演算を行うために複数の入力ベクトル要素を格納するレジスタとそれを選択する手段を備えた入力要素レジスタ２を備え、乗算語長より小さい桁数の加減算器４を備えて、さらに、部分積の累算途中で加減算演算がオーバーフローしないように、累算が終了して不要となった下位桁を切り捨てるためのシフタ６を備えている。
【００５１】
次に、上述した内積演算装置１の積和演算（内積演算）の処理の内容について説明する。
【００５２】
例えば、符号付８ビット表現された入力ベクトルの要素Ｘ０、Ｘ１、Ｘ２、…Ｘ７と定数ベクトルの要素Ｃ０、Ｃ１、Ｃ２、…Ｃ７との内積演算が上述した内積演算装置１でどのようになされるかを説明する。定数ベクトルは、ＤＣＴ処理のコサイン係数に相当する。以下、数４のＤＣＴ処理を表す整数行列式の出力要素Ｚ１の内積演算方法を例示して説明する。
【００５３】
以下の数値は１０ビット固定小数点表現で表されたＤＣＴ係数行列の第２行ベクタ（数４の２行目）を抜き出してその整数値と符号および絶対値を２進表現したものである。
Ｃ０＝ ５０２ （＋）１＿１１１１＿０１１０
Ｃ１＝ ４２６ （＋）１＿１０１０＿１０１０
Ｃ２＝ ２８４ （＋）１＿０００１＿１１００
Ｃ３＝ １００ （＋）０＿０１１０＿０１００
Ｃ４＝−１００ （−）０＿０１１０＿０１００
Ｃ５＝−２８４ （−）１＿０００１＿１１００
Ｃ６＝−４２６ （−）１＿１０１０＿１０１０
Ｃ７＝−５０２ （−）１＿１１１１＿０１１０
【００５４】
これらの絶対値を２のべき乗項の多項式で表すと以下のとおりとなる（以降の式で＊は乗算を示し、また、例えば２＾１は２の１乗を示す）。
【００５５】
【数５】
【００５６】
ここでベクトル内積Ｚは一般的に、
【００５７】
【数６】
【００５８】
と表され、ＤＣＴ結果の出力ベクトルの第２要素であるＺ１は、下式で求められる。
【００５９】
【数７】
【００６０】
上式で５０２＊Ｘ０の乗算は、
【００６１】
【数８】
【００６２】
と表され、これを展開すると、
【００６３】
【数９】
【００６４】
となる。
【００６５】
２＾１＊Ｘ０は定数“５０２”の２の１乗項の部分積、２＾４＊Ｘ０は定数“５０２”の２の４乗項の部分積を表し、定数“５０２”の最上位桁である２の８乗項の部分積まで加算することで５０２＊Ｘ０の乗算結果が得られる。
【００６６】
つまり、それぞれの部分積はＸ０の２のべき乗倍となっているため、単純にデータの左シフト演算により求めることができ、それらを加減算器４で累算することで乗算結果が得られる。これが以降のシフトと加減算による積和演算の原理となる。以下に５０２＊Ｘ０以外の項についても記載する。
【００６７】
【数１０】
【００６８】
図２に上述した原理に則りＺ１を求めるための動作のプログラムリストを示す。このプログラムは制御部８で動作する。図２の左端はステップ番号（行番号）を表し、ステップ番号の右側の部分で実際の制御内容を表している。
【００６９】
図２のプログラムリストを説明すると、ステップ００１でアキュムレータ５をリセットした後のステップ００２〜００５にかけて定数ベクトルの各要素の最下位のべき乗項であるｂｉｔ１、すなわち２の１乗項に対する部分積を、該当する入力ベクトルの各要素を選択して左シフトすることにより求め、サイクルごとに順に累積加減算している。定数ベクトル要素Ｃ０，Ｃ１，Ｃ２，Ｃ３は正数、Ｃ４，Ｃ５，Ｃ６，Ｃ７は負数なので、その正負に応じて部分積を加算または減算する。このとき３番目の制御項で入力ベクトルの要素を選択し、４番目の制御項でバレルシフタ３による左シフト量、すなわち入力の２のべき乗倍の選択を行う。２番目の制御項は加減算器の加算か、減算か、を選択を表し、定数ベクトルの符号によって、加算か減算かを切替える役割を果たす。
【００７０】
つまり、この１つのステップで、バレルシフタ３が、入力要素レジスタ２から入力ベクトル要素を選択して、選択された入力ベクトルを左ビットシフトさせることにより定数ベクトル要素の２のべき乗項と入力ベクトル要素との部分積を求め、加減算器４が、バレルシフタ３が求めた部分積を累算して、加減算器４の累算結果をアキュムレータ５に格納している。
【００７１】
したがって、ステップ００２〜００５は、２＾１＊Ｘ０＋２＾１＊Ｘ１＋２＾１＊Ｘ６＋２＾１＊Ｘ７の演算、すなわち、数１０の各式の右端の項（定数ベクトルの各要素の最下位のべき乗項）の累積加減算を行っていることを示している。なお、本実施形態に示した定数ベクトルでは２の０乗項がすべて“０”のため２の１乗項を最下位のべき乗項として演算しているが、定数ベクトルの設定によっては２の０乗項が最下位のべき乗項となる場合もあり、その場合は、２の０乗項の累積加減算から行う。
【００７２】
次に、ステップ００６〜０１１にかけて、定数ベクトル各要素の２の２乗項の部分積を生成して累積加減算を行い、以下順にステップ０１２〜０１５にかけて２の３乗項の部分積、ステップ０１６〜０１９にかけて２の４乗項の部分積の加減算を行っている。
【００７３】
この時点でアキュムレータ５の累算結果が最大で１６ビット桁に達するため、以降の演算のオーバーフローを回避するために、次のステップ０２０では、２の５乗項の部分積の累積加減算を開始するにあたり、５番目の制御項でアキュムレータ５の内容をシフタ６で５ビット右シフトさせて、加減算器４に入力することで途中の累算結果の５ビット分、下位桁を切捨て丸めするように動作させる。すなわち、予め定めた桁数のビットシフトにより加減算器４による累算途中のアキュムレータ５に格納された結果の切り捨てを行って演算結果の丸めを行っている。累積加減算する部分積の桁合わせのために、ステップ０２０以降すなわち定数ベクトルの２の５乗項以降の部分積を求めるためのバレルシフト３のシフト量はゼロから開始される。
【００７４】
このように下位桁の部分積から順に累積加減算を行うこと、演算途中で加減算値がオーバーフローしないように既に累積加減算を終えた途中結果の下位桁を右シフトして切捨て丸めを行うことが本発明の特徴である。画像圧縮などで使用されるＤＣＴ等の処理をデジタル演算器で処理する場合は、構成する演算器の語長が限られることから、累積加減算の途中結果の切捨て丸めを行うことで桁あふれを起こすことなく、精度低下のない内積演算を行うことができる。
【００７５】
次に、ステップ０２６〜０２９にかけて２の６乗項の部分積の累積加減算を行い、ステップ０３０〜０３３にかけて２の７乗項の部分積の累積加減算を行い、ステップ０３４〜０３９にかけて２の８乗項の部分積の累積加減算を行っている。
【００７６】
つまり、図２のプログラムリストを実行することで、加減算器４に、定数ベクトル要素の最下位の２のべき乗項の同じ項にかかる全ての入力ベクトル要素の部分積の累算を行わせてアキュムレータ５に格納させて、以降、順次高位の２のべき乗項にかかる部分積の累算を繰り返して最上位の２のべき乗項まで繰り返させるとともに、加減算部４の桁あふれが発生する前にシフタ６により類算途中のアキュムレータ５に格納された結果の下位桁を切捨てさせて、以降の累算の初期値とするように動作させている。
【００７７】
この実施形態では、符号付き８ビットの入力ベクトルと、符号なし小数点以下１０ビットの固定小数点の定数（係数）ベクトルとの内積演算により最終的には最大で整数部符号付１１ビット小数部５ビットで計１６ビットの演算結果が得られ、例えば２次元ＤＣＴであれば次段のＤＣＴ処理の入力として処理されることになる。
【００７８】
本実施形態によれば、専用の乗算器をもたず、入力要素レジスタ２と加減算器４とアキュムレータ５とバレルシフタ３およびシフタ６を備えただけなので、ハードウェア量が少なく規則的な演算装置が構成できる。また、内積演算の片方のベクトル要素が定数であることを前提としているので、入力ベクトル要素（レジスタ）の選択、シフト量と加減算の簡単な制御のみで内積演算を実現することができる。また、従来の乗算器を用いた構成であれば、乗算結果の最大語長の加減算精度が必要であったが、同じ桁の部分積を下位から順に累算して行くことにより、乗算の最大語長より小さい語長の演算器構成でも、下位桁累算からの繰り上がりを落とすことなく、すなわち演算精度を確保して内積演算を行うことができる。また、累算途中でアキュムレータ５の内容をシフタ６によって右シフトして丸めることができるので、積項の乗算語長より小さい桁数の加減算器４とアキュムレータ５であっても桁あふれを起こすことなく精度低下のない内積演算を行うことができる。
【００７９】
なお、本実施形態では演算途中結果の丸め処理において、演算器構成では５ビット固定の右シフトを行うシフタ６を備えるように構成されている。その切捨て桁数については次のようにして算出される。例えば、入力ベクトル要素の語長が８ビット、ベクトル要素の数が８、加減算器の語長が１６ビットであれば、桁あふれを起こさずに累算できる部分積は、定数ベクトル要素の（１６−（８＋ｌｏｇ2８））＋１＝６ビットに相当するものまでである（加減算器４のビット語長から入力ベクトル要素のビット語長および入力ベクトル要素数の２を底とする対数を減じた数以下のビット桁数）。つまり定数ベクトル要素の最大６ビット分に相当する部分積までの累算は桁あふれなく演算可能であり、その時点で、既に累算の終了している６ビット分までの下位桁を切捨てることが可能である。但し本実施形態では内積演算の精度切捨てをなるべく小さくするために最大語長１６ビット（整数部１１ビット、小数部５ビット）で出力しているので、前記した最大切捨て可能桁である６ビット以下である５ビット固定桁の切捨てを、定数ベクトル要素５ビット分に相当する部分積の累算終了後に実行している。このように丸め桁数を予め決めておくことで、ハードウェア規模の大きな任意桁のバレルシフタを使用することなく固定桁数のシフタ６だけを使って途中累算結果の切捨て処理を行うことができる。
【００８０】
（第２実施形態）
次に、本発明の第２の実施形態を図３および図４を参照して説明する。なお、前述した第１の実施形態と同一部分には、同一符号を付して説明を省略する。図３は、本発明の第２の実施形態にかかる内積演算装置に適用されるブースのアルゴリズム表である。図４は、本発明の第２の実施形態にかかる内積演算装置の内積演算動作を示したプログラムリストである。
【００８１】
本実施形態は、構成は第１の実施形態と同じであるが、内積演算の制御を変更することで、よりサイクル数の少ない演算としている。本実施形態では２次のブースのアルゴリズムを適用して定数ベクトル要素の２ビットごとに部分積を生成することで、累算すべき部分積の数を減らし、より高速な演算を行うことができる。
【００８２】
２次のブースのアルゴリズムでは、定数ベクトルの要素を乗数として１０ビット２進値で、ｂ９，ｂ８，ｂ７，ｂ６，ｂ５，ｂ４，ｂ３，ｂ２，ｂ１，ｂ０と表したときに、乗数の各ビットである２のべき乗項ごとに入力ベクトル要素である被乗数との部分積を求めるのではなく、乗数の２ビット分ごと、すなわち下位から（ｂ１，ｂ０）の部分積、（ｂ３，ｂ２）の部分積、（ｂ５，ｂ４）の部分積、（ｂ７，ｂ６）の部分積、（ｂ９，ｂ８）の部分積を順に求めてゆく方法である。ただし、例えば（ｂ１，ｂ０）＝（１，１）の場合は、部分積は被乗数の３倍の値となり別途加算器が必要となるがこれを回避するために図３に示した表にしたがって２のべき乗倍の部分積の生成に置き換える。
【００８３】
図３に示した表の乗数の３ビットは最下位桁については（ｂ１，ｂ０，“０”）、次桁以降は（ｂ３，ｂ２，ｂ１）、（ｂ５，ｂ４，ｂ３）、（ｂ７，ｂ６，ｂ５）、（ｂ９，ｂ８，ｂ７）のビット値を示している。また、加算すべき部分積の“Ｍ”は被乗数自身を示し、“２Ｍ”は被乗数を２倍したものすなわち１ビット左シフトしたものを示している。
【００８４】
ところでブースのアルゴリズムでは、加減算すべき部分積の数を減じるのみで、乗数側が定数であることから加減算すべき部分積は予めわかっており、本実施形態の場合は、第１の実施形態で示した演算器構成に加えて特別なハードウェアが必要となるわけではなく単に加減算すべき部分積が異なるのみであるので制御ステップを変更すればよい。
【００８５】
図４に本実施形態の動作のプログラムリストを示す。図４も図２と同様に数４のＺ１を求める場合のものである。このプログラムは制御部８で動作する。
【００８６】
図４のプログラムリストを説明すると、ステップ００１はアキュムレータ５のリセットを行い、演算をリセットしている。次に、ステップ００２〜００５は定数ベクトルの最下位２ビットすなわちｂ１，ｂ０に対応する部分積の総和、すなわち部分内積を計算する。ここで、定数ベクトル要素Ｃ０〜Ｃ７は、
Ｃ０＝ ５０２ （＋）１＿１１１１＿０１１０
Ｃ１＝ ４２６ （＋）１＿１０１０＿１０１０
Ｃ２＝ ２８４ （＋）１＿０００１＿１１００
Ｃ３＝ １００ （＋）０＿０１１０＿０１００
Ｃ４＝−１００ （−）０＿０１１０＿０１００
Ｃ５＝−２８４ （−）１＿０００１＿１１００
Ｃ６＝−４２６ （−）１＿１０１０＿１０１０
Ｃ７＝−５０２ （−）１＿１１１１＿０１１０
であるからそれぞれの定数ベクトル要素の下位２ビットを含む（ｂ１，ｂ０，“０”）のビットパターンと定数ベクトル要素の符号から図３に示したブースのアルゴリズム表を参照して、部分内積の演算を行う。
【００８７】
したがって、ステップ００２は、定数ベクトル要素Ｃ０が正数で（ｂ１，ｂ０，“０”）が“１００”であるから図３より“−２Ｍ”すなわち被乗数である入力要素Ｘ０の２倍を減算している。ステップ００３は、定数ベクトル要素Ｃ１が正数で（ｂ１，ｂ０，“０”）が“１００”であるから図３より“−２Ｍ”すなわち被乗数である入力要素Ｘ１の２倍を減算している。ステップ００４は、定数ベクトル要素Ｃ６が負数で（ｂ１，ｂ０，“０”）が“１００”であるから図３より“−２Ｍ”すなわち被乗数である入力要素Ｘ６の２倍を加算している。ステップ００５は、定数ベクトル要素Ｃ７が負数で（ｂ１，ｂ０，“０”）が“１００”であるから“−２Ｍ”すなわち被乗数である入力要素Ｘ７の２倍を加算している。なお、定数ベクトルＣ２〜Ｃ５は（ｂ１，ｂ０，“０”）が“０００”であるので、加減算すべき部分積は無い。つまり、各ステップで、バレルシフタ３が入力ベクトル要素の２ビット毎に部分積を求めて、加減算器４が該部分積を累算している。
【００８８】
次に、ステップ００６〜０１３は定数ベクトルの次の２ビットすなわちｂ３，ｂ２に対応する部分積の総和、すなわち部分内積を計算している。ここで部分積の桁位置は２ビット上位のｂ２の位置が基準であり、加算すべき部分積“Ｍ”とは被乗数を４倍したもの、すなわち被乗数を２ビット左シフトしたものとなり、部分積“２Ｍ”とは被乗数を８倍したもの、すなわち被乗数を３ビット左シフトしたものとなる。
【００８９】
したがって、ステップ００６は、定数ベクトルＣ０が正数で（ｂ３，ｂ２，ｂ１）が“０１１”であるから図３より“＋２Ｍ”すなわち被乗数である入力要素Ｘ０の８倍を加算している。ステップ００７は、定数ベクトルＣ１が正数で（ｂ３，ｂ２，ｂ１）が“１０１”であるから図３より“−Ｍ”すなわち被乗数である入力要素Ｘ１の４倍を減算している。ステップ００８は、定数ベクトルＣ２が正数で（ｂ３，ｂ２，ｂ１）が“１１０”であるから図３より“−Ｍ”すなわち被乗数である入力要素Ｘ２の４倍を減算している。ステップ００９は、定数ベクトルＣ３が正数で（ｂ３，ｂ２，ｂ１）が“０１０”であるから図３より“＋Ｍ”すなわち被乗数である入力要素Ｘ３の４倍を加算している。ステップ０１０は、定数ベクトルＣ４が負数で（ｂ３，ｂ２，ｂ１）が“０１０”であるから図３より“＋Ｍ”すなわち被乗数である入力要素Ｘ４の４倍を減算している。ステップ０１１は、定数ベクトルＣ５が負数で（ｂ３，ｂ２，ｂ１）が“１１０”であるから図３より“−Ｍ”すなわち被乗数である入力要素Ｘ５の４倍を加算している。ステップ０１２は、定数ベクトルＣ６が負数で（ｂ３，ｂ２，ｂ１）が“１０１”であるから図３より“−Ｍ”すなわち被乗数である入力要素Ｘ６の４倍を加算している。ステップ０１３は、定数ベクトルＣ７が負数で（ｂ３，ｂ２，ｂ１）が“０１１”であるから図３より“＋２Ｍ”すなわち被乗数である入力要素Ｘ７の８倍を減算している。
【００９０】
次に、ステップ０１４〜０２１は定数ベクトルの次の２ビットｂ５，ｂ４、ステップ０２２〜０２５は定数ベクトルの次の２ビットｂ７，ｂ６、ステップ０２６〜０３１は定数ベクトルの次の２ビットｂ９，ｂ８にそれぞれ対応する部分積の総和すなわち部分内積を累算する。ここで、ステップ０１８では第１の実施形態と同様に加減算器４でのオーバーフローを回避するために累算の途中結果の下位５ビット固定の切捨て処理を行っている。
【００９１】
本実施形態によれば、定数ベクトル要素の２ビットごとに部分内積の累算を行うことで内積演算を遂行しているので、累算すべき部分積の個数が減じられ、制御ステップが削減でき、演算サイクル数をさらに削減できる。例えば第１の実施形態（図２）と本実施形態（図４）とを比較すると、図２では３９ステップ必要であるのに対して、図４では３１ステップと２０％程度の演算速度の改善がなされることが明らかである。
【００９２】
（第３実施形態）
次に、本発明の第３の実施形態を図５および図６を参照して説明する。なお、前述した第１、第２の実施形態と同一部分には、同一符号を付して説明を省略する。図５は、本発明の第３の実施形態にかかる内積演算装置の構成図である。図６は、図５に示された内積演算装置の内積演算動作を示したプログラムリストである。
【００９３】
本実施形態では、図１に示した内積演算装置１に対して、バレルシフタ３とセレクタ７が削除されている。そして、加減算器４が１１ビット語長の加減算器９となり、アキュムレータ５の後段には第一シフト手段としてのシフタ１０が設けられている。
【００９４】
加減算器９は、制御部８からの制御信号によりサイクル毎に加算か減算かの動作が選択される一方の入力が８ビット、他方の入力が１１ビットで出力が１１ビットとなっている演算器であり、８ビットの一方の入力には入力要素レジスタ２の出力が接続されている。すなわち、入力ベクトル要素と定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成されている。
【００９５】
アキュムレータ５には、加減算器９の出力が上位側の１１ビットに入力され、下位側の５ビットは後述するシフタ１０の下位５ビットが入力されている。
【００９６】
シフタ１０は、１６ビット語長で、アキュムレータ５に格納された演算結果を、制御部８からの制御信号により１ビット固定桁の右シフトを行う。
【００９７】
上述した構成の内積演算装置１は、入力要素レジスタ２には複数の入力ベクトル要素を格納し、制御信号により１つが選択されて、加減算器９の一方に接続される。加減算器９は制御信号により、サイクル毎に加算か減算動作が選択される。加減算器９の出力は、アキュムレータ５に接続されており、途中および最終の演算結果が格納される。アキュムレータ５の出力はシフタ１０に接続され、１ビットの右シフトを行い、アキュムレータ５に格納された演算途中結果を１ビット右シフトできる構成となっている。シフタ１０は、同じ桁の部分積を累算している間はシフト動作を行わず、同桁の累算の終了後にシフト動作を行い上位桁の累算を開始する。シフト動作の有無は制御信号によって切替えられる。
【００９８】
図６に本実施形態の動作のプログラムリストを示す。図６も図２、図４と同様に数４のＺ１を求める場合のものである。このプログラムは制御部８で動作する。
【００９９】
図６のプログラムリストを説明すると、ステップ００１はアキュムレータ５のリセットを行い、演算をリセットしている。次に、ステップ００２から００５にかけて定数ベクトルの各要素の最下位のべき乗項であるｂｉｔ１、すなわち２の１乗項に対する部分積を、該当する入力ベクトルの各要素を選択して、サイクルごとに順に累積加減算している。加減算器９の出力はアキュムレータ５の上位１１ビットに接続されているので、アキュムレータ５の６ビット目を最下位ビットとして、最初の累算結果が得られる。定数ベクトル要素Ｃ０，Ｃ１，Ｃ２，Ｃ３は正数、Ｃ４，Ｃ５，Ｃ６，Ｃ７は負数なので、その正負に応じて部分積を加算または減算する。このとき３番目の制御項で入力ベクトルの要素を選択し、4番目の制御項でアキュムレータ出力の右シフトの制御を行う。２番目の制御項は加減算器９の加算か、減算かを選択する項で、定数ベクトル要素の符号によって、加算か減算かを切替える役割を果たす。つまり、この１つのステップで、加減算器９に、定数ベクトル要素の同じ桁の２のべき乗項の同じ項にかかる全ての入力ベクトル要素の部分積の累算を行わせてアキュムレータ５に格納している。
【０１００】
次に、ステップ００６では上位桁の部分積の累算を開始するためにアキュムレータ５の右シフトが選択されて加減算器９に入力される。このステップ００６〜０１１にかけて、定数ベクトル各要素の２の２乗項の部分積の累積加減算が実行され、以下順にステップ０１２〜０１５にかけて２の３乗項、ステップ０１６〜０１９にかけて２の４乗項、ステップ０２０〜０２５にかけて２の５乗項、ステップ０２６〜０２９にかけて２の６乗項、ステップ０３０〜０３３にかけて２の７乗項、ステップ０３４〜０３９にかけて２の８乗項、の部分積の累積加減算をそれぞれ行う。また、本実施形態の数値例では２の９乗項は存在しない。つまり、シフタ１０にアキュムレータ５に格納された累算結果を右ビットシフトさせる動作を行い、上位桁の部分積の累算を行う動作を最上位桁まで繰り返している。
【０１０１】
ステップ０４０、０４１はアキュムレータ５の内容をそれぞれ１ビットずつ右シフトするだけの動作がなされて有効桁の桁合わせが行われる。そして、最終的には整数部符号付１１ビット小数部５ビットで計１６ビットの演算結果が得られる。
【０１０２】
本実施形態によれば、個別の乗算器をもたず、入力要素レジスタ２と加減算器９とアキュムレータ５とシフタ１０を有するだけなので、ハードウェア量が少なく規則的な演算装置が構成できる。また、内積演算の片方のベクトル要素が定数であることを前提としているので、入力ベクトル要素（レジスタ）の選択、シフト量と加減算の簡単な制御のみで内積演算を実現することができる。また、従来の乗算器を用いた構成であれば、乗算結果の最大語長の加減算精度が必要であったが、下位桁の部分積から順に累積加減算を行い、アキュムレータ５の語長を超えて右シフトされた途中の累算結果は自動的に切捨てられるように動作するので、同じ桁の部分積を下位から順に累算することにより、乗算の最大語長より小さい語長の演算器構成でも、下位桁累算からの繰り上がりを落とすことなく、すなわち演算精度を確保して内積演算を行うことができる。さらに、部分積を求める際にバレルシフタを用いていないので回路規模を小さくすることができる。
【０１０３】
（第４実施形態）
次に、本発明の第４の実施形態を図７および図８を参照して説明する。なお、前述した第１〜第３の実施形態と同一部分には、同一符号を付して説明を省略する。図７は、本発明の第４の実施形態にかかる内積演算装置の構成図である。図８は、図７に示された内積演算装置の内積演算動作を示したプログラムリストである。
【０１０４】
本実施形態は、第３の実施形態と基本的な構成は同じであるが、入力要素レジスタ２からの出力が、そのまま出力するか２倍（１ビットシフト）して出力するかを選択するように構成されている。したがって、入力要素レジスタ２の出力を２倍するための符号拡張機能付きの第二シフト手段としてのシフタ１１と、セレクタ１２が追加され、加減算器１３の一方の入力が９ビットとなっている。
【０１０５】
また、第一シフト手段としてのシフタ１４は、アキュムレータ５に格納された演算結果を、制御部８からの制御信号により２ビット固定桁の右シフトを行うように変更されている。
【０１０６】
本実施形態の基本動作は、第３の実施形態と同等であるが、第２の実施形態の説明のごとく２次のブースのアルゴリズムを採用して、定数ベクトル要素の２ビットごとに、下位ビットを付け加えた３ビットのパターンから加減算すべき部分積すなわち入力ベクトル要素自身“Ｍ”もしくは、その２倍値“２Ｍ”を累算する。すなわち、入力ベクトル要素またはシフトタ１１が２倍にした入力ベクトル要素のいずれかを選択して加減算器１３に累算する。自身もしくは２倍値の生成と選択は、シフタ１１とセレクタ１２をサイクルごとに制御することでこれを行う。定数ベクトル要素の２ビットごとに同位桁の部分積の累算を終了すると、上位桁の累算を開始するためにシフタ１４でアキュムレータ５の内容が２ビット右シフトされて、次の加減算の入力となる。
【０１０７】
図８に本実施形態の動作のプログラムリストを示す。図８も図２、図４、図６と同様に数４のＺ１を求める場合のものである。このプログラムは制御部８で動作する。
【０１０８】
図８のプログラムリストを説明すると、ステップ００１はアキュムレータ５のリセットを行い、演算をリセットしている。ステップ００２〜００５にかけて定数ベクトルの各要素の最下位のべき乗項であるｂｉｔ１とｂｉｔ０の２ビットすなわち２の１乗項と２の０乗項に対する加減算すべき部分積として図３に示したブースのアルゴリズム表にしたがって入力ベクトルの各要素自身もしくはその２倍値をサイクルごとに累積加減算している。なお、演算内容については、第２の実施形態と同等であるので説明を省略する。加減算器１３の出力はアキュムレータ５の上位１１ビットに接続されているので、アキュムレータ５の６ビット目を最下位ビットとして、最初の累算結果が得られる。
【０１０９】
次に、ステップ００６ではブースのアルゴリズムにしたがって、２ビット分上位桁の部分積の累算を開始するためにアキュムレータの内容がシフタ１４によって、右シフトされて加減算器１３に入力される。ステップ００６〜０１３にかけては、定数ベクトル各要素の２の２乗項と２の３乗項の部分積の累積加減算が実行され、以下順にステップ０１４〜０２１にかけて２は４乗項と２の５乗項、ステップ０２２〜０２５にかけて２は６乗項と２の７乗項、ステップ０２６〜０３１にかけては２の８乗項と２の９乗項の部分積の累積加減算を行っている。
【０１１０】
ステップ０３２はアキュムレータ５の内容を２ビットずつ右シフトするだけの動作がなされ、有効桁の桁合わせが行われる。そして、最終的には整数部符号付１２ビット小数部４ビットで計１６ビットの演算結果が得られる。
【０１１１】
本実施形態によれば、定数ベクトル要素の２ビットごとに部分内積の累算を行うことで内積演算を遂行するので、累算すべき部分積の個数が減じられ、制御ステップが削減でき、演算サイクル数をさらに削減できる。例えば第３の実施形態（図６）と本実施形態（図８）とを比較すると、図６では４１ステップ必要であるのに対して、図８では３２ステップと２０％程度の演算速度の改善がなされる。
【０１１２】
（第５実施形態）
次に、本発明の第５の実施形態を図９ないし図１３を参照して説明する。なお、前述した第１〜第４の実施形態と同一部分には、同一符号を付して説明を省略する。図９は、本発明の第５の実施形態にかかる内積演算方法を実行するマイクロプロセッサの演算器部分の構成図である。図１０は、図９に示したマイクロプロセッサの機械語命令コードフォーマットである。図１１は、図９に示したマイクロプロセッサの内積演算動作を示したプログラムリストの一の部分である。図１２は、図９に示したマイクロプロセッサの内積演算動作を示したプログラムリストの他の部分である。図１３は、図９に示したマイクロプロセッサで動作する内積演算方法のフローチャートである。
【０１１３】
本実施形態は、マイクロプロセッサなどプログラム命令で実施可能な内積演算方法を示す。特に、専用の乗算回路と命令もしくは内積演算専用の回路と命令を有しないマイクロプロセッサで実現可能な内積演算方法を示す。
【０１１４】
図３に示した演算装置としてのマイクロプロセッサ２０は、論理積・論理和・算術加算・算術減算を行う加減算手段としての算術論理演算器（ＡＬＵ）２２と、ＡＬＵ２２の演算結果が格納されるアキュムレータ２４と、バス３０を介してアキュムレータ２４およびバレルシフタ２８と接続される格納手段としてのレジスタ２６と、レジスタ２６から送り出されたオペランドデータを左シフトしてＡＬＵ２２に送るシフト手段としてのバレルシフタ２８と、を備えている。
【０１１５】
ＡＬＵ２２は、１６ビット語長の算術論理演算器で、一方の入力にはバレルシフタ２８の出力が接続されており、レジスタ２６から送り出されたオペランドデータを左シフトしてＡＬＵ２２に入力する。他方の入力にはアキュムレータ２４の出力が接続され、ＡＬＵ２２の出力はアキュムレータ２４に接続されて、ＡＬＵ２２の演算結果がアキュムレータ２４に蓄積されるようにしてある。
【０１１６】
アキュムレータ２４は、１６ビット語長で構成され、ＡＬＵ２２の他方の入力と、８ビット幅のバス３０を介してレジスタ２６に接続されており、アキュムレータ２４に蓄積されたデータがレジスタ２６に転送できるようにしてある。
【０１１７】
レジスタ２６は、例えば汎用レジスタとしてＲ０〜Ｒ３１の３２本の８ビット幅のレジスタを備えている。
【０１１８】
バレルシフタ２８は、レジスタ２６に格納されている８ビットデータ（オペランドデータ）を後述する機械語命令コードで指定された分のシフト量のシフトを行い１６ビットデータとしてＡＬＵ２２に出力する。
【０１１９】
機械語命令コード３７は、図１０に示したように、演算の種類Ｃ、符号拡張の指定Ｓ、シフト量ＢＳＨの情報を含む。演算の種類Ｃには、加算、減算、論理積、論理和の演算が含まれ、Ｃの値により区別される。符号拡張Ｓには、ゼロ拡張と符号拡張があり、ゼロ拡張の場合はＳに０が指定され、符号拡張の場合はＳに１が指定される。シフト量ＢＳＨはゼロ桁から１５桁まで指定可能となっている。
【０１２０】
図１１および図１２に上述した構成のマイクロプロセッサ２０において内積演算行うためのプログラムリストを示す。ここで入力ベクトル要素はレジスタＴｍＲ０（レジスタ２６のＲ０）からＴｍＲ７（レジスタ２６のＲ７）のラベルのレジスタに格納されているとする。図１１および図１２に示したプログラムリストも図２、図４、図６、図８と同様に数４のＺ１を求める場合のものである。
【０１２１】
次に、命令ニモニックについて説明する。
ｌｄａ ＃０
この命令はアキュムレータ２４にゼロ値をロードする命令のニモニックである。
ａｄｄ ＴｍＲ０：ｓ０
この命令はアキュムレータ２４の値にソースオペランドである“ＴｍＲ０”ラベルのレジスタ値を呼び出して加算する命令のニモニックである。ソースオペランドである“ＴｍＲ０”の右側に“：ｓ０”と補助コードが付加されているがこれは“ｓ”に続く数字のビット数分の符号およびビット拡張つきの左シフトを行ってレジスタ値を読み出す動作を行うことを意味する。同様に“ｓｕｂ”は減算命令である。
【０１２２】
“ｓｔａ”はアキュムレータ２４内容をデスティネーションオペランドに書き出す命令で、例えば、
ｓｔａ ＴｍＲ１２：ｚ５
と記述され、これはデスティネーションオペランドである“ＴｍＲ１２”の右側に“：ｚ５”と補助コードが付加されているが、これは“ｚ”に続くビット数分の右シフトを行ってアキュムレータ２４の内容をレジスタ２６に転送する動作を行う。“ｌｄａ”は即値もしくはソースオペランドのレジスタ値をアキュムレータ２４に読み出す命令である。
【０１２３】
図１１および図１２に示したプログラムリストでセミコロンの付加された行はコメント行であり、その行の命令は実行されない。図中では理解を容易にするためにコメントとして命令ニモニックが残してある。コメント行の命令は定数ベクトルのビット値が“０”である桁の部分積の加減算を表しており、第１の実施形態でも説明したように、これらの部分積の加減算は実行されない。
【０１２４】
図１１および図１２に示したプログラムリストの演算動作については、定数ベクトル要素の数値および動作は第１の実施形態と同じであるが、概略動作を図１３のフローチャートを参照して説明する。
【０１２５】
まず、アキュムレータ２４にゼロ値ロードしてリセットし（ステップＳ１、図１１の先頭行）、定数ベクトル要素の最下位桁の部分積を求め、部分積を累算し、全定数ベクトル要素の累算が終了するまで繰り返す（ステップＳ２〜Ｓ４、例えば図１１のＣＯＥＦ＿ｂｉｔ１ ＭＵＬ／ＡＤＤ以下の８ステップ）。すなわち、ステップＳ２が特許請求の範囲の第一の工程に相当し、ステップＳ３が特許請求の範囲の第二の工程に相当する。
【０１２６】
次に、１つ上の桁に移動して（ステップＳ５）、定数ベクトル要素の最下位桁の部分積を求め、部分積を累算し、全定数ベクトル要素の累算が終了するまで繰り返す（ステップＳ６〜Ｓ８、例えば図１１のＣＯＥＦ＿ｂｉｔ２ ＭＵＬ／ＡＤＤ以下の８ステップ）。そして、この繰り返しは最上位桁が終了するまで繰り返し、最上位桁まで終了した場合は処理を終了する（ステップＳ１１）。すなわち、ステップＳ６が特許請求の範囲の第一の工程に相当し、ステップＳ７が特許請求の範囲の第二の工程に相当する。
【０１２７】
なお、累算結果がアキュムレータ２４の最大桁の達した場合は、５ビット右シフトして切り捨て丸め処理を行う（ステップＳ９、Ｓ１０、図１１の中間結果／Ｏｖｅｒｆｌｏｗ（１６ｂｉｔ）回避の部分）。すなわち、ステップＳ１０が特許請求の範囲の第三の工程に相当する。なお、この切り捨てる５ビットも第１の実施形態と同様に、加減算器４のビット語長から入力ベクトル要素のビット語長および入力ベクトル要素数の２を底とする対数を減じた数以下のビット桁数から算出されて予め決められたものである。
【０１２８】
また、本実施形態において、演算結果はアキュムレータ２４に格納され１６ビット幅であるが、次の段階のプログラム命令に渡すために、ＴｍＲ１２（レジスタ２６のＲ１２）、ＴｍＲ１３（レジスタ２６のＲ１３）のラベルのレジスタに下位、上位に分けて転送している。また、演算途中の５ビット右シフトによる切捨て丸め操作は、レジスタ幅と命令セットの都合上、上位、下位にわけて実施している。
【０１２９】
本実施形態によれば、専用の乗算回路と命令もしくは内積演算専用の回路と命令を有しないマイクロプロセッサ２０において、ソースオペランドのシフトが一体となった加減算命令を使って、同じ桁の部分積を下位から順に累算して行くことにより、下位桁累算からの繰り上がりを落とすことなくすなわち演算精度を確保して内積演算を行うことができる。また累算途中結果を一旦ビットシフトして丸めるステップを備えているので乗算の最大語長より小さい語長の演算器構成のマイクロプロセッサでも精度の良い内積演算を実現できる。
【０１３０】
（第６実施形態）
次に、本発明の第６の実施形態を図１４を参照して説明する。なお、前述した第１〜第５の実施形態と同一部分には、同一符号を付して説明を省略する。図１４は、本発明の第６の実施形態にかかるマイクロプロセッサの内積演算動作を示したプログラムリストである。
【０１３１】
本実施形態は、構成は第５の実施形態と同じであるが、第２、第４の実施形態の説明のごとく２次のブースのアルゴリズムを採用して、定数ベクトル要素の２ビットごとに、下位ビットを付け加えた３ビットのパターンから加減算すべき部分積すなわち入力ベクトル要素自身“Ｍ”もしくは、その２倍値“２Ｍ”を累算する。すなわち、第一の工程は、入力ベクトル要素自身または入力ベクトル要素の２倍の値のいずれかを選択して部分積を求め、第二の工程は、部分積の累算を２ビット毎に行っている。
【０１３２】
図１４に本実施形態の動作のプログラムリストを示す。図１４も図２、図４、図６、図８、図１１、図１２と同様に数４のＺ１を求める場合のものである。なお、演算内容については、第２の実施形態と同等であるので説明を省略する。
【０１３３】
本実施形態によれば、定数ベクトル要素の２ビットごとに部分内積の累算を行うことで内積演算を遂行するので、累算すべき部分積の個数が減じられ、制御ステップが削減でき、演算サイクル数をさらに削減できる。例えば第５の実施形態（図１１、図１２）と本実施形態（図１４）とを比較すると、図６では４８ステップ必要であるのに対して、図８では３８ステップと２０％程度の演算速度の改善がなされる。
【０１３４】
なお、本発明は上記実施形態に限定されるものではない。即ち、本発明の骨子を逸脱しない範囲で種々変形して実施することができる。
【符号の説明】
【０１３５】
１ 内積演算装置
２ 入力要素レジスタ（格納手段）
３ バレルシフタ（シフト手段）
４ 加減算器（加減算手段）
５ アキュムレータ
６ シフタ（丸め手段）
７ セレクタ
８ 制御部（演算制御手段）
９ 加減算器（加減算手段）
１０ シフタ（第一シフト手段）
１１ シフタ（第二シフト手段）
１２ セレクタ
１３ 加減算器（加減算手段）
１４ シフタ（第一シフト手段）
２０ マイクロプロセッサ（演算装置）
２２ ＡＬＵ（加減算手段）
２４ アキュムレータ
２６ レジスタ（格納手段）
２８ バレルシフタ（シフト手段）
【先行技術文献】
【特許文献】
【０１３６】
【特許文献１】特公平５−２６２２９号公報
【特許文献２】特開２０００−１３２５３９号公報
【技術分野】
【０００１】
本発明は、離散コサイン変換などの直交変換において行われるベクトル内積を演算する内積演算装置および内積演算方法に関する。
【背景技術】
【０００２】
ベクトル内積演算は、画像圧縮処理などの分野で多用される離散コサイン変換に代表される直交変換の中核をなす演算であるが、その演算量が膨大となるため実時間処理など高速処理の要求に応えるためには、一般的には大規模なハードウェア量が必要となり装置のコストは増大する傾向にある。以下に内積演算の応用される離散コサイン変換（Discrete Cosine Transform：以下、ＤＣＴという）処理について簡単に説明を行う。以下の式が１次元の数列に対する、Ｎ次ＤＣＴの一般式である。
【０００３】
【数１】
【０００４】
前記式をＮ＝８とした８次のＤＣＴ処理は以下の行列積の式で表される。
【０００５】
【数２】
【０００６】
この式の右辺の行列はＤＣＴ係数行列と称され、小数点数値表現すると以下の行列となる。
【０００７】
【数３】
【０００８】
このような行列式をデジタルハードウェア演算装置で処理するために、例えば固定小数点演算用に正負符号と１０ビット桁の整数で表すと以下の整数行列式となる。
【０００９】
【数４】
【００１０】
平面画像信号を対象とするＤＣＴ処理は前記式のごとく８次のものが多く、例えばＪＰＥＧ（Joint Photographic Experts Group）方式で用いられるＤＣＴは水平方向８画素、垂直方向８画素の８×８画素について、垂直方向の１次元ＤＣＴを施したのち水平方向の１次元ＤＣＴを施して８×８の２次元平面上の周波数成分に分解する、所謂２次元ＤＣＴとして採用されている。以降、説明を容易にするため、入力ベクトルの要素は画素値として一般的な８ビット整数値、ＤＣＴ係数は典型的なハードウェア構成として一般的な８から１６ビット程度の固定小数点表現とする。
【００１１】
ここで数４において、出力ベクトルＺの要素であるＺ１の計算に着目するとＤＣＴ係数行列の２行目の枠で囲まれた部分行ベクトル（５０２，４２６，２８４，１００，−１００，−２８４，−４２６，−５０２）と入力ベクトル（Ｘ０，Ｘ１，Ｘ２，Ｘ３，Ｘ４，Ｘ５，Ｘ６，Ｘ７）の内積演算に他ならず、８回の乗算と７回の加減算が必要となる。このように内積演算は多くの乗算と加算を内包しその演算量が多く、高速に処理するためのハードウェアが多く考案されている。
【００１２】
図１５に従来の内積演算装置の例を示す。図１５に示された内積演算装置１００は、加減算器１０１、１０２、１０３、１０４と、レジスタ１０５、１０６、１０７、１０８と、乗算器１０９、１１０、１１１、１１２と、並列加算器１１３と、備えている。
【００１３】
図１５の内積演算装置１００は、入力ベクトルＸの各要素とＤＣＴ係数の乗算を入力ベクトルＸの要素ごとに乗算器１０９、１１０、１１１、１１２で並列に実行し、それぞれの乗算結果を並列加算器１１３で総和することで内積演算を実行する。入力ベクトルの要素Ｘ０〜Ｘ７は一括してそれぞれの乗算器１０９、１１０、１１１、１１２に並列に入力され、ＤＣＴ係数は定数であることからレジスタに置かれ乗算器１０９、１１０、１１１、１１２に入力される。なお、ＤＣＴ係数はＲＯＭに格納しても良い。
【００１４】
ここで、内積にかかるＤＣＴ係数行列の部分行ベクトルを（Ｃ０，Ｃ１，Ｃ２，Ｃ３，Ｃ４，Ｃ５，Ｃ６，Ｃ７）とすると、ＤＣＴ係数の性質上Ｃ０とＣ７、Ｃ１とＣ６、Ｃ２とＣ５,Ｃ３とＣ４の絶対値が対称関係となるため、対称な係数に対応する入力Ｘの要素すなわちＸ０とＸ７、Ｘ１とＸ６、Ｘ２とＸ５,Ｘ３とＸ４の加算または減算を係数の正負符号にあわせて先に行うことで（バタフライ演算）、乗算回数を４回に減じたハードウェア構成となっている。
【００１５】
しかしながら上述した構成は乗算回数分の複数の乗算器が必要となることが本質であり、乗算器は一般的にハードウェア規模が大きく、費やす素子数、回路面積、消費電力が大きいうえに、演算桁数が増えると回路内の伝播遅延によりサイクルタイムが低下する問題点がある。また、処理の高速化のために複数の内積結果を複数の内積演算器で同時並列に実行しうるように並列化した演算器構成を構築することもできるが、個々の演算器のハードウェア規模が大きいと、ハードウェア資源であるシリコン面積、電子プリント基板面積は、有限かつ小型化を求められるため大規模に並列化することが困難となる問題点もある。さらに、回路規模の制約から、乗算器や加減算器の桁数の制限がある場合は、入力桁を丸めたり、あるいは積項の乗算結果を丸めたりする必要があり、真の下位桁からの部分積の累算が行われず演算精度が低下するという欠点があった。
【００１６】
また、乗算器を使用しない内積演算装置としては、例えば特許文献１や２に記載のものが提案されている。図１６に乗算器を使用しない内積演算装置の例を示す。図１６に示された内積演算装置２００は、ＲＯＭ２０１と、加減算器２０２と、アキュムレータ２０３と、シフタ２０４と、備えている。
【００１７】
図１６に示された内積演算装置２００は、Ａ〜Ｄが入力ベクトル要素で４ビット幅、定数ベクトル要素Ｃ０〜Ｃ３は１６ビット幅としている。内積演算装置２００では、定数ベクトルの各要素が固定値であることから、入力ベクトルとの内積演算において、入力ベクトルが４ビット幅であることからこれをｂ３，ｂ２，ｂ１，ｂ０と二進値で表すと、入力ベクトルにおける最下位のビットスライスはＡ（ｂ０），Ｂ（ｂ０），Ｃ（ｂ０），Ｄ（ｂ０）と表され、これに対する部分内積は、Ｃ０×Ａ（ｂ０）＋Ｃ１×Ｂ（ｂ０）＋Ｃ２×Ｃ（ｂ０）＋Ｃ３×Ｄ（ｂ０）となる。
【００１８】
Ａ（ｂ０），Ｂ（ｂ０），Ｃ（ｂ０），Ｄ（ｂ０）はそれぞれ、１か０の２値の値しかとらないため、ビットスライスに対する部分内積はＣ０〜Ｃ３の単純な加減算に帰結する。Ｃ０〜Ｃ３は固定値の定数ベクトルであるから、ビットスライスＡ（ｂ０），Ｂ（ｂ０），Ｃ（ｂ０），Ｄ（ｂ０）の出現パターンにしたがって、予め計算された部分内積をＲＯＭ２０１に格納しておき、演算では入力ベクトルのビットスライスのビットパターンによりＲＯＭ２０１を読み出すことにより部分内積を読み出すことができる。これをＲＯＭアキュムレータと称しＲＡＣと略称される。内積演算では、最下位のビットスライスから始めて上位に向かって部分内積を累算してゆくことで内積演算が達成される。部分内積の累算は加減算器２０２とアキュムレータ２０３で行われ、アキュムレータ２０３をシフタ２０４で右シフトして上位桁の累算を開始する。
【００１９】
図１６に示された内積演算装置２００では、シフトと加減算で内積演算が実現可能でありハードウェア量が少ないこと、部分内積の演算がＲＡＣとしてＲＯＭ化されているので高速に動作すること、下位桁の部分内積から順に累算してゆくので必要な結果精度に応じて、演算器の語長を選択できてかつそれが乗算の演算語長より小さな桁の構成であっても、下位桁からの部分内積の累算を完遂しているので演算精度が確保される利点がある。
【発明の概要】
【発明が解決しようとする課題】
【００２０】
上述したように、従来の専用の乗算回路と加減算器とアキュムレータとを有するような積和演算装置では、乗算回路の回路量が大きくなり、コストが増大する問題点があった。乗算回路は特に配列型の乗算器を有する場合は、その回路内容が複雑で規則性が低下し、かつ個々のハードウェア量が大きいことから、複数演算器を大規模に並列に構成するようなＳＩＭＤ（Single Instruction-stream Multiple Data-stream）型の演算器構成を選択することが困難であった。また、乗算回路を有する装置では乗算回路が複雑かつ大規模であるために信号伝播時間が増大し演算装置全体のサイクルタイムが低下する問題点があった。さらに、小規模な演算ブロックを大規模高並列に構成して内積演算装置を構成する場合や、既定のマイクロプロセッサなどの演算装置で内積演算をプログラミングするような場合などでは、演算桁数に制限があることから入力自身の桁数を落としたり、あるいは積項の乗算結果を丸めたりして途中の演算桁を制限せざるを得ず、内積演算の精度が落ちてしまうという問題点があった。
【００２１】
また、ＲＯＭアキュムレータを用いて部分内積の累積加減算とシフト動作によって内積演算を行う内積演算装置は、下位桁から順に部分内積を累算してゆく構造であるため、積項の演算精度がすべて保証され、内積演算の精度低下はないが、ＲＯＭアキュムレータの有するＲＯＭの容量は、入力の語長と内積を行うベクトルの要素数すなわち積項の数が増大するにしたがって増大してしまうという問題点があった。このことは、大規模な並列演算器を構成する場合、同一のＲＯＭを多数複製せざるを得ず、ハードウェア面積の利用効率も悪く並列化の規模が制限されてしまう問題点もあった。
【００２２】
本発明はかかる問題を解決することを目的としている。
【００２３】
すなわち、本発明は、乗算器を使用しないハードウェア量の少ない演算器構成で、高並列に適してサイクルタイムの高速化が図れるとともに、ＲＯＭを用いなくても内積演算が精度低下なく行うことができる内積演算装置および内積演算方法を提供することを目的としている。
【課題を解決するための手段】
【００２４】
上記課題を解決するためになされた請求項１に記載された発明は、所定のビット語長を有する複数の入力ベクトル要素から構成される入力ベクトルと複数の定数ベクトル要素から構成される定数ベクトルとの内積を求める内積演算装置において、前記複数の入力ベクトル要素を格納する格納手段と、前記格納手段から前記入力ベクトル要素を選択して、選択された前記入力ベクトルを左ビットシフトさせることにより前記定数ベクトル要素の２のべき乗項と入力ベクトル要素との部分積を求めるシフト手段と、前記シフト手段が求めた前記部分積を累算するとともに、前記入力ベクトル要素と前記定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成された加減算手段と、前記加減算手段の累算結果を格納するアキュムレータと、予め定めた桁数のビットシフトにより前記加減算手段による累算途中の前記アキュムレータに格納された結果の切り捨てを行って演算結果の丸めを行う丸め手段と、前記加減算手段に、前記定数ベクトル要素の最下位の２のべき乗項の同じ項にかかる全ての入力ベクトル要素の部分積の累算を行わせて前記アキュムレータに格納させて、以降、順次高位の２のべき乗項にかかる部分積の累算を繰り返して最上位の２のべき乗項まで繰り返させるとともに、前記加減算手段の桁あふれが発生する前に前記丸め手段により類算途中の前記アキュムレータに格納された結果の下位桁を切捨てさせて、以降の累算の初期値とするように動作させる演算制御手段と、を備えていることを特徴とする内積演算装置である。
【００２５】
請求項２に記載された発明は、請求項１に記載された発明において、前記演算制御手段が、予め定めたテーブルに基づいて、前記シフト手段に対して前記入力ベクトル要素の２ビット毎に前記部分積を求めさせ、前記加減算手段に対して該部分積を累算させることを特徴とするものである。
【００２６】
請求項３に記載された発明は、請求項１または２に記載された発明において、前記丸め手段が前記加減算手段による累算途中の前記アキュムレータに格納された結果の切り捨てを行うビット桁数は、前記加減算手段のビット語長から前記入力ベクトル要素のビット語長および前記入力ベクトル要素数の２を底とする対数を減じた数以下のビット桁数として予め定められていることを特徴とするものである。
【００２７】
請求項４に記載された発明は、所定のビット語長を有する複数の入力ベクトル要素から構成される入力ベクトルと複数の定数ベクトル要素から構成される定数ベクトルとの内積を求める内積演算装置において、前記複数の入力ベクトル要素を格納する格納手段と、前記格納手段から前記入力ベクトル要素を選択して、前記定数ベクトル要素の２のべき乗項と選択された前記入力ベクトル要素との部分積を求めて累算するとともに、前記入力ベクトル要素と前記定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成された加減算手段と、前記加減算手段の累算結果を自身の上位桁側に格納するアキュムレータと、前記アキュムレータの内容を下位桁方向に右ビットシフトして以降の累算値とするとともに、前記入力ベクトル要素と前記定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成された第一シフト手段と、前記加減算手段に、前記定数ベクトル要素の同じ桁の２のべき乗項の同じ項にかかる全ての入力ベクトル要素の部分積の累算を行わせて前記アキュムレータに格納させて、前記第一シフト手段に前記アキュムレータに格納された累算結果を右ビットシフトさせる動作を前記定数ベクトル要素の２のべき乗項の最上位桁まで繰り返させる演算制御手段と、を備えていることを特徴とする内積演算装置である。
【００２８】
請求項５に記載された発明は、請求項４に記載された発明において、前記格納手段に格納された前記入力ベクトル要素を２倍する第二シフト手段を備え、前記演算制御手段が、予め定めたテーブルに基づいて、前記格納手段に格納された前記入力ベクトル要素または前記第二シフト手段が２倍にした入力ベクトル要素のいずれかを選択して前記加減算手段に累算させるとともに、前記第一シフト手段に２ビットシフトさせることを特徴とするものである。
【００２９】
請求項６に記載された発明は、所定のビット語長を有する複数の入力ベクトル要素から構成される入力ベクトルを格納する格納手段と、前記入力ベクトルを左ビットシフトさせることにより複数の定数ベクトル要素から構成される定数ベクトルの２のべき乗項と前記入力ベクトル要素との部分積を求めるシフト手段と、前記シフト手段が求めた前記部分積を累算するとともに、前記入力ベクトル要素と前記定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成された加減算手段と、前記加減算手段の累算結果を格納するアキュムレータと、を備えたマイクロプロセッサでオペランドの加減算とシフトが一体に実行可能な命令を用いて前記入力ベクトルと前記定数ベクトルとの内積を求める内積演算方法において、前記シフト手段が前記格納手段から前記入力ベクトル要素を選択して前記部分積を求める第一の工程と、前記加減算手段に、前記定数ベクトル要素の最下位の２のべき乗項の同じ項にかかる全ての前記入力ベクトル要素の前記部分積の累算を行わせて前記アキュムレータに格納させる第二の工程と、前記加減算手段の桁あふれが発生する前に前記アキュムレータに格納させている類算途中の前記アキュムレータに格納された結果の下位桁を切捨てて、以降の累算の初期値とする第三の工程と、を備え、前記第一の工程と前記第二の工程を順次高位の２のべき乗項にかかる部分積の累算を繰り返して最上位の２のべき乗項まで繰り返すとともに、前記第一の工程と前記第二の工程の繰り返しの途中に少なくとも前記第三の工程を１回以上行うことを特徴とする内積演算方法である。
【００３０】
請求項７に記載された発明は、請求項６に記載された発明において、前記第一の工程は、前記入力ベクトル要素自身または前記入力ベクトル要素の２倍の値のいずれかを選択して前記部分積を求め、前記第二の工程は、前記部分積の累算を２ビット毎に行うことを特徴とするものである。
【００３１】
請求項８に記載された発明は、請求項６または７に記載の発明において、前記第三の工程で前記加減算手段による累算途中の前記アキュムレータに格納された結果の切り捨てを行うビット桁数は、前記加減算手段のビット語長から前記入力ベクトル要素のビット語長および前記入力ベクトル要素数の２を底とする対数を減じた数以下のビット桁数として予め定められていることを特徴とするものである。
【発明の効果】
【００３２】
請求項１に記載の発明によれば、乗算回路を使用せず、加減算手段とアキュムレータとシフト手段とを有する累積加減算構造で装置を構成するために、規則性が高く、高並列に適したハードウェア量の小さい演算装置を構成できる。また、下位桁から順に部分積の累算を実行し、上位桁に必ず下記桁の部分積和結果が反映されるので演算精度が低下することなく内積演算を行うことができる。また、累算途中でアキュムレータの内容を丸め手段によって右シフトして丸めることができるので、積項の乗算語長より小さい桁数の加減算器とアキュムレータであっても桁あふれを起こすことなく精度低下のない内積演算を行うことができる。
【００３３】
請求項２に記載の発明によれば、演算制御手段が、ブースのアルゴリズムを適用して、定数ベクトルの２ビット毎の部分積の累算を行わせることができ、制御ステップが削減され、さらに少ないサイクル数で演算することができる。
【００３４】
請求項３に記載の発明によれば、積項の乗算語長より小さい桁数の加減算器とアキュムレータであっても、確実に桁あふれを起こさずに内積演算を行うことができる。
【００３５】
請求項４に記載の発明によれば、乗算回路を使用せず、加減算手段とアキュムレータと、シフト手段を有する累積加減算構造で装置を構成するために、規則性が高く、高並列に適したハードウェア量の小さい演算装置を構成できる。また、下位桁から順に部分積の累算を実行するよう動作するため、上位桁に必ず下位桁の部分積和結果が完遂し反映されるので演算精度が低下することなく内積演算を行うことができる。また、累算途中でアキュムレータの内容を右シフトして丸めることができるので、積項の乗算語長より小さい桁数の加減算器とアキュムレータを有する演算装置であっても桁あふれを起こすことなく、精度低下のない内積演算を行うことができる。さらに、入力を任意桁左シフトするためのバレルシフタを有しないので、さらに回路規模を小さくすることができる。
【００３６】
請求項５に記載の発明によれば、演算制御手段が、ブースのアルゴリズムを適用して、定数ベクトルの２ビット毎の部分積の累算を行うことができ、制御ステップが削減され、さらに少ないサイクル数で演算することができる。
【００３７】
請求項６に記載の発明によれば、オペランドのシフトが一体となった加減算命令を持つマイクロプロセッサにおいて、下位桁から順に部分積の累算を実行するので、上位桁に必ず下記桁の部分積和結果が完遂し反映されるために演算精度が低下することなく内積演算を行うことができる。また、累算途中でアキュムレータの内容を右シフトして丸める第三のステップを備えるのでので、積項の乗算語長より小さい桁数の加減算器とアキュムレータを有する演算装置でも桁あふれを起こすことなく精度低下のない内積演算を行うことができる方法が提供できる。
【００３８】
請求項７に記載の発明によれば、ブースのアルゴリズムを適用して、定数ベクトルの２ビット毎の部分積の累算を行うので、累算すべき部分積の数が削減され、実行命令数をさらに少なくすることができる。
【００３９】
請求項８に記載の発明によれば、積項の乗算語長より小さい桁数の加減算器とアキュムレータを備えた演算装置であっても、確実に桁あふれを起こさずに内積演算を行うことができる。
【図面の簡単な説明】
【００４０】
【図１】本発明の第１の実施形態にかかる内積演算装置の構成図である。
【図２】図１に示された内積演算装置の内積演算動作を示したプログラムリストである。
【図３】本発明の第２の実施形態にかかる内積演算装置に適用されるブースのアルゴリズム表である。
【図４】本発明の第２の実施形態にかかる内積演算装置の内積演算動作を示したプログラムリストである。
【図５】本発明の第３の実施形態にかかる内積演算装置の構成図である。
【図６】図５に示された内積演算装置の内積演算動作を示したプログラムリストである。
【図７】本発明の第４の実施形態にかかる内積演算装置の構成図である。
【図８】図７に示された内積演算装置の内積演算動作を示したプログラムリストである。
【図９】本発明の第５の実施形態にかかる内積演算方法を実行するマイクロプロセッサの演算器部分の構成図である。
【図１０】図９に示したマイクロプロセッサの機械語命令コードフォーマットである。
【図１１】図９に示したマイクロプロセッサの内積演算動作を示したプログラムリストの一の部分である。
【図１２】図９に示したマイクロプロセッサの内積演算動作を示したプログラムリストの他の部分である。
【図１３】図９に示したマイクロプロセッサで動作する内積演算方法のフローチャートである。
【図１４】本発明の第６の実施形態にかかるマイクロプロセッサの内積演算動作を示したプログラムリストである。
【図１５】従来の内積演算装置を示した構成図である。
【図１６】従来の内積演算装置を示した構成図である。
【発明を実施するための形態】
【００４１】
（第１実施形態）
以下、本発明の第１の実施形態を、図１および図２を参照して説明する。図１は、本発明の第１の実施形態にかかる内積演算装置の構成図である。図２は、図１に示された内積演算装置の内積演算動作を示したプログラムリストである。
【００４２】
図１に本発明の第１の実施形態にかかる内積演算装置１を示す。図１に示した内積演算装置１は、入力要素レジスタ２と、バレルシフタ３と、加減算器４と、アキュムレータ５と、シフタ６と、セレクタ７と、制御部８と、を備えている。
【００４３】
格納手段としての入力要素レジスタ２は、８ビット語長でＲ０〜Ｒ７までの８つのレジスタから構成される。各レジスタに入力ベクトル要素（例えば、数４のＸ０〜Ｘ７）が格納され、制御部８からの制御信号により１つのレジスタが選択されバレルシフタ３に出力される。
【００４４】
シフト手段としてのバレルシフタ３は、入力された入力ベクトル要素を任意の桁数の左シフトを行い、加減算器４の一方の入力に接続される。本実施例では、入力８ビット出力１６ビット語長で、０〜９ビット桁の符号拡張付きの左シフト機能を有する。バレルシフタ３のシフト量は、制御部８からの制御信号によりサイクル毎に選択される。
【００４５】
加減算手段としての加減算器４は、制御部８からの制御信号によりサイクル毎に加算か減算かの動作が選択される入出力とも１６ビットの語長を有する演算器である。すなわち、入力ベクトル要素と定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成されている。加減算器４の出力は、アキュムレータ５に接続される。
【００４６】
アキュムレータ５は、加減算器４による途中および最終の演算結果が格納される１６ビットのレジスタである。アキュムレータ５の出力はシフタ６に接続される。
【００４７】
丸め手段としてのシフタ６は、１６ビット語長で、アキュムレータ５に格納された演算結果を、制御部８からの制御信号により５ビット固定桁の右シフトを行い、演算途中結果の切捨て丸めを行うことができる構成となっている。
【００４８】
セレクタ７は、制御部８からの制御信号によりシフタ６の出力とアキュムレータ５の出力とを選択して加減算器４の他方の入力に接続されるとともに、演算結果として外部へ出力する。
【００４９】
演算制御手段としての制御部８は、内積演算装置１の演算動作を制御し、演算動作ステップに応じて制御信号を、入力要素レジスタ２、バレルシフタ３、加減算器４、アキュムレータ５、シフタ６、セレクタ７に出力する。
【００５０】
上述した構成の内積演算装置１は、ベクトル内積演算を行うために複数の入力ベクトル要素を格納するレジスタとそれを選択する手段を備えた入力要素レジスタ２を備え、乗算語長より小さい桁数の加減算器４を備えて、さらに、部分積の累算途中で加減算演算がオーバーフローしないように、累算が終了して不要となった下位桁を切り捨てるためのシフタ６を備えている。
【００５１】
次に、上述した内積演算装置１の積和演算（内積演算）の処理の内容について説明する。
【００５２】
例えば、符号付８ビット表現された入力ベクトルの要素Ｘ０、Ｘ１、Ｘ２、…Ｘ７と定数ベクトルの要素Ｃ０、Ｃ１、Ｃ２、…Ｃ７との内積演算が上述した内積演算装置１でどのようになされるかを説明する。定数ベクトルは、ＤＣＴ処理のコサイン係数に相当する。以下、数４のＤＣＴ処理を表す整数行列式の出力要素Ｚ１の内積演算方法を例示して説明する。
【００５３】
以下の数値は１０ビット固定小数点表現で表されたＤＣＴ係数行列の第２行ベクタ（数４の２行目）を抜き出してその整数値と符号および絶対値を２進表現したものである。
Ｃ０＝ ５０２ （＋）１＿１１１１＿０１１０
Ｃ１＝ ４２６ （＋）１＿１０１０＿１０１０
Ｃ２＝ ２８４ （＋）１＿０００１＿１１００
Ｃ３＝ １００ （＋）０＿０１１０＿０１００
Ｃ４＝−１００ （−）０＿０１１０＿０１００
Ｃ５＝−２８４ （−）１＿０００１＿１１００
Ｃ６＝−４２６ （−）１＿１０１０＿１０１０
Ｃ７＝−５０２ （−）１＿１１１１＿０１１０
【００５４】
これらの絶対値を２のべき乗項の多項式で表すと以下のとおりとなる（以降の式で＊は乗算を示し、また、例えば２＾１は２の１乗を示す）。
【００５５】
【数５】
【００５６】
ここでベクトル内積Ｚは一般的に、
【００５７】
【数６】
【００５８】
と表され、ＤＣＴ結果の出力ベクトルの第２要素であるＺ１は、下式で求められる。
【００５９】
【数７】
【００６０】
上式で５０２＊Ｘ０の乗算は、
【００６１】
【数８】
【００６２】
と表され、これを展開すると、
【００６３】
【数９】
【００６４】
となる。
【００６５】
２＾１＊Ｘ０は定数“５０２”の２の１乗項の部分積、２＾４＊Ｘ０は定数“５０２”の２の４乗項の部分積を表し、定数“５０２”の最上位桁である２の８乗項の部分積まで加算することで５０２＊Ｘ０の乗算結果が得られる。
【００６６】
つまり、それぞれの部分積はＸ０の２のべき乗倍となっているため、単純にデータの左シフト演算により求めることができ、それらを加減算器４で累算することで乗算結果が得られる。これが以降のシフトと加減算による積和演算の原理となる。以下に５０２＊Ｘ０以外の項についても記載する。
【００６７】
【数１０】
【００６８】
図２に上述した原理に則りＺ１を求めるための動作のプログラムリストを示す。このプログラムは制御部８で動作する。図２の左端はステップ番号（行番号）を表し、ステップ番号の右側の部分で実際の制御内容を表している。
【００６９】
図２のプログラムリストを説明すると、ステップ００１でアキュムレータ５をリセットした後のステップ００２〜００５にかけて定数ベクトルの各要素の最下位のべき乗項であるｂｉｔ１、すなわち２の１乗項に対する部分積を、該当する入力ベクトルの各要素を選択して左シフトすることにより求め、サイクルごとに順に累積加減算している。定数ベクトル要素Ｃ０，Ｃ１，Ｃ２，Ｃ３は正数、Ｃ４，Ｃ５，Ｃ６，Ｃ７は負数なので、その正負に応じて部分積を加算または減算する。このとき３番目の制御項で入力ベクトルの要素を選択し、４番目の制御項でバレルシフタ３による左シフト量、すなわち入力の２のべき乗倍の選択を行う。２番目の制御項は加減算器の加算か、減算か、を選択を表し、定数ベクトルの符号によって、加算か減算かを切替える役割を果たす。
【００７０】
つまり、この１つのステップで、バレルシフタ３が、入力要素レジスタ２から入力ベクトル要素を選択して、選択された入力ベクトルを左ビットシフトさせることにより定数ベクトル要素の２のべき乗項と入力ベクトル要素との部分積を求め、加減算器４が、バレルシフタ３が求めた部分積を累算して、加減算器４の累算結果をアキュムレータ５に格納している。
【００７１】
したがって、ステップ００２〜００５は、２＾１＊Ｘ０＋２＾１＊Ｘ１＋２＾１＊Ｘ６＋２＾１＊Ｘ７の演算、すなわち、数１０の各式の右端の項（定数ベクトルの各要素の最下位のべき乗項）の累積加減算を行っていることを示している。なお、本実施形態に示した定数ベクトルでは２の０乗項がすべて“０”のため２の１乗項を最下位のべき乗項として演算しているが、定数ベクトルの設定によっては２の０乗項が最下位のべき乗項となる場合もあり、その場合は、２の０乗項の累積加減算から行う。
【００７２】
次に、ステップ００６〜０１１にかけて、定数ベクトル各要素の２の２乗項の部分積を生成して累積加減算を行い、以下順にステップ０１２〜０１５にかけて２の３乗項の部分積、ステップ０１６〜０１９にかけて２の４乗項の部分積の加減算を行っている。
【００７３】
この時点でアキュムレータ５の累算結果が最大で１６ビット桁に達するため、以降の演算のオーバーフローを回避するために、次のステップ０２０では、２の５乗項の部分積の累積加減算を開始するにあたり、５番目の制御項でアキュムレータ５の内容をシフタ６で５ビット右シフトさせて、加減算器４に入力することで途中の累算結果の５ビット分、下位桁を切捨て丸めするように動作させる。すなわち、予め定めた桁数のビットシフトにより加減算器４による累算途中のアキュムレータ５に格納された結果の切り捨てを行って演算結果の丸めを行っている。累積加減算する部分積の桁合わせのために、ステップ０２０以降すなわち定数ベクトルの２の５乗項以降の部分積を求めるためのバレルシフト３のシフト量はゼロから開始される。
【００７４】
このように下位桁の部分積から順に累積加減算を行うこと、演算途中で加減算値がオーバーフローしないように既に累積加減算を終えた途中結果の下位桁を右シフトして切捨て丸めを行うことが本発明の特徴である。画像圧縮などで使用されるＤＣＴ等の処理をデジタル演算器で処理する場合は、構成する演算器の語長が限られることから、累積加減算の途中結果の切捨て丸めを行うことで桁あふれを起こすことなく、精度低下のない内積演算を行うことができる。
【００７５】
次に、ステップ０２６〜０２９にかけて２の６乗項の部分積の累積加減算を行い、ステップ０３０〜０３３にかけて２の７乗項の部分積の累積加減算を行い、ステップ０３４〜０３９にかけて２の８乗項の部分積の累積加減算を行っている。
【００７６】
つまり、図２のプログラムリストを実行することで、加減算器４に、定数ベクトル要素の最下位の２のべき乗項の同じ項にかかる全ての入力ベクトル要素の部分積の累算を行わせてアキュムレータ５に格納させて、以降、順次高位の２のべき乗項にかかる部分積の累算を繰り返して最上位の２のべき乗項まで繰り返させるとともに、加減算部４の桁あふれが発生する前にシフタ６により類算途中のアキュムレータ５に格納された結果の下位桁を切捨てさせて、以降の累算の初期値とするように動作させている。
【００７７】
この実施形態では、符号付き８ビットの入力ベクトルと、符号なし小数点以下１０ビットの固定小数点の定数（係数）ベクトルとの内積演算により最終的には最大で整数部符号付１１ビット小数部５ビットで計１６ビットの演算結果が得られ、例えば２次元ＤＣＴであれば次段のＤＣＴ処理の入力として処理されることになる。
【００７８】
本実施形態によれば、専用の乗算器をもたず、入力要素レジスタ２と加減算器４とアキュムレータ５とバレルシフタ３およびシフタ６を備えただけなので、ハードウェア量が少なく規則的な演算装置が構成できる。また、内積演算の片方のベクトル要素が定数であることを前提としているので、入力ベクトル要素（レジスタ）の選択、シフト量と加減算の簡単な制御のみで内積演算を実現することができる。また、従来の乗算器を用いた構成であれば、乗算結果の最大語長の加減算精度が必要であったが、同じ桁の部分積を下位から順に累算して行くことにより、乗算の最大語長より小さい語長の演算器構成でも、下位桁累算からの繰り上がりを落とすことなく、すなわち演算精度を確保して内積演算を行うことができる。また、累算途中でアキュムレータ５の内容をシフタ６によって右シフトして丸めることができるので、積項の乗算語長より小さい桁数の加減算器４とアキュムレータ５であっても桁あふれを起こすことなく精度低下のない内積演算を行うことができる。
【００７９】
なお、本実施形態では演算途中結果の丸め処理において、演算器構成では５ビット固定の右シフトを行うシフタ６を備えるように構成されている。その切捨て桁数については次のようにして算出される。例えば、入力ベクトル要素の語長が８ビット、ベクトル要素の数が８、加減算器の語長が１６ビットであれば、桁あふれを起こさずに累算できる部分積は、定数ベクトル要素の（１６−（８＋ｌｏｇ2８））＋１＝６ビットに相当するものまでである（加減算器４のビット語長から入力ベクトル要素のビット語長および入力ベクトル要素数の２を底とする対数を減じた数以下のビット桁数）。つまり定数ベクトル要素の最大６ビット分に相当する部分積までの累算は桁あふれなく演算可能であり、その時点で、既に累算の終了している６ビット分までの下位桁を切捨てることが可能である。但し本実施形態では内積演算の精度切捨てをなるべく小さくするために最大語長１６ビット（整数部１１ビット、小数部５ビット）で出力しているので、前記した最大切捨て可能桁である６ビット以下である５ビット固定桁の切捨てを、定数ベクトル要素５ビット分に相当する部分積の累算終了後に実行している。このように丸め桁数を予め決めておくことで、ハードウェア規模の大きな任意桁のバレルシフタを使用することなく固定桁数のシフタ６だけを使って途中累算結果の切捨て処理を行うことができる。
【００８０】
（第２実施形態）
次に、本発明の第２の実施形態を図３および図４を参照して説明する。なお、前述した第１の実施形態と同一部分には、同一符号を付して説明を省略する。図３は、本発明の第２の実施形態にかかる内積演算装置に適用されるブースのアルゴリズム表である。図４は、本発明の第２の実施形態にかかる内積演算装置の内積演算動作を示したプログラムリストである。
【００８１】
本実施形態は、構成は第１の実施形態と同じであるが、内積演算の制御を変更することで、よりサイクル数の少ない演算としている。本実施形態では２次のブースのアルゴリズムを適用して定数ベクトル要素の２ビットごとに部分積を生成することで、累算すべき部分積の数を減らし、より高速な演算を行うことができる。
【００８２】
２次のブースのアルゴリズムでは、定数ベクトルの要素を乗数として１０ビット２進値で、ｂ９，ｂ８，ｂ７，ｂ６，ｂ５，ｂ４，ｂ３，ｂ２，ｂ１，ｂ０と表したときに、乗数の各ビットである２のべき乗項ごとに入力ベクトル要素である被乗数との部分積を求めるのではなく、乗数の２ビット分ごと、すなわち下位から（ｂ１，ｂ０）の部分積、（ｂ３，ｂ２）の部分積、（ｂ５，ｂ４）の部分積、（ｂ７，ｂ６）の部分積、（ｂ９，ｂ８）の部分積を順に求めてゆく方法である。ただし、例えば（ｂ１，ｂ０）＝（１，１）の場合は、部分積は被乗数の３倍の値となり別途加算器が必要となるがこれを回避するために図３に示した表にしたがって２のべき乗倍の部分積の生成に置き換える。
【００８３】
図３に示した表の乗数の３ビットは最下位桁については（ｂ１，ｂ０，“０”）、次桁以降は（ｂ３，ｂ２，ｂ１）、（ｂ５，ｂ４，ｂ３）、（ｂ７，ｂ６，ｂ５）、（ｂ９，ｂ８，ｂ７）のビット値を示している。また、加算すべき部分積の“Ｍ”は被乗数自身を示し、“２Ｍ”は被乗数を２倍したものすなわち１ビット左シフトしたものを示している。
【００８４】
ところでブースのアルゴリズムでは、加減算すべき部分積の数を減じるのみで、乗数側が定数であることから加減算すべき部分積は予めわかっており、本実施形態の場合は、第１の実施形態で示した演算器構成に加えて特別なハードウェアが必要となるわけではなく単に加減算すべき部分積が異なるのみであるので制御ステップを変更すればよい。
【００８５】
図４に本実施形態の動作のプログラムリストを示す。図４も図２と同様に数４のＺ１を求める場合のものである。このプログラムは制御部８で動作する。
【００８６】
図４のプログラムリストを説明すると、ステップ００１はアキュムレータ５のリセットを行い、演算をリセットしている。次に、ステップ００２〜００５は定数ベクトルの最下位２ビットすなわちｂ１，ｂ０に対応する部分積の総和、すなわち部分内積を計算する。ここで、定数ベクトル要素Ｃ０〜Ｃ７は、
Ｃ０＝ ５０２ （＋）１＿１１１１＿０１１０
Ｃ１＝ ４２６ （＋）１＿１０１０＿１０１０
Ｃ２＝ ２８４ （＋）１＿０００１＿１１００
Ｃ３＝ １００ （＋）０＿０１１０＿０１００
Ｃ４＝−１００ （−）０＿０１１０＿０１００
Ｃ５＝−２８４ （−）１＿０００１＿１１００
Ｃ６＝−４２６ （−）１＿１０１０＿１０１０
Ｃ７＝−５０２ （−）１＿１１１１＿０１１０
であるからそれぞれの定数ベクトル要素の下位２ビットを含む（ｂ１，ｂ０，“０”）のビットパターンと定数ベクトル要素の符号から図３に示したブースのアルゴリズム表を参照して、部分内積の演算を行う。
【００８７】
したがって、ステップ００２は、定数ベクトル要素Ｃ０が正数で（ｂ１，ｂ０，“０”）が“１００”であるから図３より“−２Ｍ”すなわち被乗数である入力要素Ｘ０の２倍を減算している。ステップ００３は、定数ベクトル要素Ｃ１が正数で（ｂ１，ｂ０，“０”）が“１００”であるから図３より“−２Ｍ”すなわち被乗数である入力要素Ｘ１の２倍を減算している。ステップ００４は、定数ベクトル要素Ｃ６が負数で（ｂ１，ｂ０，“０”）が“１００”であるから図３より“−２Ｍ”すなわち被乗数である入力要素Ｘ６の２倍を加算している。ステップ００５は、定数ベクトル要素Ｃ７が負数で（ｂ１，ｂ０，“０”）が“１００”であるから“−２Ｍ”すなわち被乗数である入力要素Ｘ７の２倍を加算している。なお、定数ベクトルＣ２〜Ｃ５は（ｂ１，ｂ０，“０”）が“０００”であるので、加減算すべき部分積は無い。つまり、各ステップで、バレルシフタ３が入力ベクトル要素の２ビット毎に部分積を求めて、加減算器４が該部分積を累算している。
【００８８】
次に、ステップ００６〜０１３は定数ベクトルの次の２ビットすなわちｂ３，ｂ２に対応する部分積の総和、すなわち部分内積を計算している。ここで部分積の桁位置は２ビット上位のｂ２の位置が基準であり、加算すべき部分積“Ｍ”とは被乗数を４倍したもの、すなわち被乗数を２ビット左シフトしたものとなり、部分積“２Ｍ”とは被乗数を８倍したもの、すなわち被乗数を３ビット左シフトしたものとなる。
【００８９】
したがって、ステップ００６は、定数ベクトルＣ０が正数で（ｂ３，ｂ２，ｂ１）が“０１１”であるから図３より“＋２Ｍ”すなわち被乗数である入力要素Ｘ０の８倍を加算している。ステップ００７は、定数ベクトルＣ１が正数で（ｂ３，ｂ２，ｂ１）が“１０１”であるから図３より“−Ｍ”すなわち被乗数である入力要素Ｘ１の４倍を減算している。ステップ００８は、定数ベクトルＣ２が正数で（ｂ３，ｂ２，ｂ１）が“１１０”であるから図３より“−Ｍ”すなわち被乗数である入力要素Ｘ２の４倍を減算している。ステップ００９は、定数ベクトルＣ３が正数で（ｂ３，ｂ２，ｂ１）が“０１０”であるから図３より“＋Ｍ”すなわち被乗数である入力要素Ｘ３の４倍を加算している。ステップ０１０は、定数ベクトルＣ４が負数で（ｂ３，ｂ２，ｂ１）が“０１０”であるから図３より“＋Ｍ”すなわち被乗数である入力要素Ｘ４の４倍を減算している。ステップ０１１は、定数ベクトルＣ５が負数で（ｂ３，ｂ２，ｂ１）が“１１０”であるから図３より“−Ｍ”すなわち被乗数である入力要素Ｘ５の４倍を加算している。ステップ０１２は、定数ベクトルＣ６が負数で（ｂ３，ｂ２，ｂ１）が“１０１”であるから図３より“−Ｍ”すなわち被乗数である入力要素Ｘ６の４倍を加算している。ステップ０１３は、定数ベクトルＣ７が負数で（ｂ３，ｂ２，ｂ１）が“０１１”であるから図３より“＋２Ｍ”すなわち被乗数である入力要素Ｘ７の８倍を減算している。
【００９０】
次に、ステップ０１４〜０２１は定数ベクトルの次の２ビットｂ５，ｂ４、ステップ０２２〜０２５は定数ベクトルの次の２ビットｂ７，ｂ６、ステップ０２６〜０３１は定数ベクトルの次の２ビットｂ９，ｂ８にそれぞれ対応する部分積の総和すなわち部分内積を累算する。ここで、ステップ０１８では第１の実施形態と同様に加減算器４でのオーバーフローを回避するために累算の途中結果の下位５ビット固定の切捨て処理を行っている。
【００９１】
本実施形態によれば、定数ベクトル要素の２ビットごとに部分内積の累算を行うことで内積演算を遂行しているので、累算すべき部分積の個数が減じられ、制御ステップが削減でき、演算サイクル数をさらに削減できる。例えば第１の実施形態（図２）と本実施形態（図４）とを比較すると、図２では３９ステップ必要であるのに対して、図４では３１ステップと２０％程度の演算速度の改善がなされることが明らかである。
【００９２】
（第３実施形態）
次に、本発明の第３の実施形態を図５および図６を参照して説明する。なお、前述した第１、第２の実施形態と同一部分には、同一符号を付して説明を省略する。図５は、本発明の第３の実施形態にかかる内積演算装置の構成図である。図６は、図５に示された内積演算装置の内積演算動作を示したプログラムリストである。
【００９３】
本実施形態では、図１に示した内積演算装置１に対して、バレルシフタ３とセレクタ７が削除されている。そして、加減算器４が１１ビット語長の加減算器９となり、アキュムレータ５の後段には第一シフト手段としてのシフタ１０が設けられている。
【００９４】
加減算器９は、制御部８からの制御信号によりサイクル毎に加算か減算かの動作が選択される一方の入力が８ビット、他方の入力が１１ビットで出力が１１ビットとなっている演算器であり、８ビットの一方の入力には入力要素レジスタ２の出力が接続されている。すなわち、入力ベクトル要素と定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成されている。
【００９５】
アキュムレータ５には、加減算器９の出力が上位側の１１ビットに入力され、下位側の５ビットは後述するシフタ１０の下位５ビットが入力されている。
【００９６】
シフタ１０は、１６ビット語長で、アキュムレータ５に格納された演算結果を、制御部８からの制御信号により１ビット固定桁の右シフトを行う。
【００９７】
上述した構成の内積演算装置１は、入力要素レジスタ２には複数の入力ベクトル要素を格納し、制御信号により１つが選択されて、加減算器９の一方に接続される。加減算器９は制御信号により、サイクル毎に加算か減算動作が選択される。加減算器９の出力は、アキュムレータ５に接続されており、途中および最終の演算結果が格納される。アキュムレータ５の出力はシフタ１０に接続され、１ビットの右シフトを行い、アキュムレータ５に格納された演算途中結果を１ビット右シフトできる構成となっている。シフタ１０は、同じ桁の部分積を累算している間はシフト動作を行わず、同桁の累算の終了後にシフト動作を行い上位桁の累算を開始する。シフト動作の有無は制御信号によって切替えられる。
【００９８】
図６に本実施形態の動作のプログラムリストを示す。図６も図２、図４と同様に数４のＺ１を求める場合のものである。このプログラムは制御部８で動作する。
【００９９】
図６のプログラムリストを説明すると、ステップ００１はアキュムレータ５のリセットを行い、演算をリセットしている。次に、ステップ００２から００５にかけて定数ベクトルの各要素の最下位のべき乗項であるｂｉｔ１、すなわち２の１乗項に対する部分積を、該当する入力ベクトルの各要素を選択して、サイクルごとに順に累積加減算している。加減算器９の出力はアキュムレータ５の上位１１ビットに接続されているので、アキュムレータ５の６ビット目を最下位ビットとして、最初の累算結果が得られる。定数ベクトル要素Ｃ０，Ｃ１，Ｃ２，Ｃ３は正数、Ｃ４，Ｃ５，Ｃ６，Ｃ７は負数なので、その正負に応じて部分積を加算または減算する。このとき３番目の制御項で入力ベクトルの要素を選択し、4番目の制御項でアキュムレータ出力の右シフトの制御を行う。２番目の制御項は加減算器９の加算か、減算かを選択する項で、定数ベクトル要素の符号によって、加算か減算かを切替える役割を果たす。つまり、この１つのステップで、加減算器９に、定数ベクトル要素の同じ桁の２のべき乗項の同じ項にかかる全ての入力ベクトル要素の部分積の累算を行わせてアキュムレータ５に格納している。
【０１００】
次に、ステップ００６では上位桁の部分積の累算を開始するためにアキュムレータ５の右シフトが選択されて加減算器９に入力される。このステップ００６〜０１１にかけて、定数ベクトル各要素の２の２乗項の部分積の累積加減算が実行され、以下順にステップ０１２〜０１５にかけて２の３乗項、ステップ０１６〜０１９にかけて２の４乗項、ステップ０２０〜０２５にかけて２の５乗項、ステップ０２６〜０２９にかけて２の６乗項、ステップ０３０〜０３３にかけて２の７乗項、ステップ０３４〜０３９にかけて２の８乗項、の部分積の累積加減算をそれぞれ行う。また、本実施形態の数値例では２の９乗項は存在しない。つまり、シフタ１０にアキュムレータ５に格納された累算結果を右ビットシフトさせる動作を行い、上位桁の部分積の累算を行う動作を最上位桁まで繰り返している。
【０１０１】
ステップ０４０、０４１はアキュムレータ５の内容をそれぞれ１ビットずつ右シフトするだけの動作がなされて有効桁の桁合わせが行われる。そして、最終的には整数部符号付１１ビット小数部５ビットで計１６ビットの演算結果が得られる。
【０１０２】
本実施形態によれば、個別の乗算器をもたず、入力要素レジスタ２と加減算器９とアキュムレータ５とシフタ１０を有するだけなので、ハードウェア量が少なく規則的な演算装置が構成できる。また、内積演算の片方のベクトル要素が定数であることを前提としているので、入力ベクトル要素（レジスタ）の選択、シフト量と加減算の簡単な制御のみで内積演算を実現することができる。また、従来の乗算器を用いた構成であれば、乗算結果の最大語長の加減算精度が必要であったが、下位桁の部分積から順に累積加減算を行い、アキュムレータ５の語長を超えて右シフトされた途中の累算結果は自動的に切捨てられるように動作するので、同じ桁の部分積を下位から順に累算することにより、乗算の最大語長より小さい語長の演算器構成でも、下位桁累算からの繰り上がりを落とすことなく、すなわち演算精度を確保して内積演算を行うことができる。さらに、部分積を求める際にバレルシフタを用いていないので回路規模を小さくすることができる。
【０１０３】
（第４実施形態）
次に、本発明の第４の実施形態を図７および図８を参照して説明する。なお、前述した第１〜第３の実施形態と同一部分には、同一符号を付して説明を省略する。図７は、本発明の第４の実施形態にかかる内積演算装置の構成図である。図８は、図７に示された内積演算装置の内積演算動作を示したプログラムリストである。
【０１０４】
本実施形態は、第３の実施形態と基本的な構成は同じであるが、入力要素レジスタ２からの出力が、そのまま出力するか２倍（１ビットシフト）して出力するかを選択するように構成されている。したがって、入力要素レジスタ２の出力を２倍するための符号拡張機能付きの第二シフト手段としてのシフタ１１と、セレクタ１２が追加され、加減算器１３の一方の入力が９ビットとなっている。
【０１０５】
また、第一シフト手段としてのシフタ１４は、アキュムレータ５に格納された演算結果を、制御部８からの制御信号により２ビット固定桁の右シフトを行うように変更されている。
【０１０６】
本実施形態の基本動作は、第３の実施形態と同等であるが、第２の実施形態の説明のごとく２次のブースのアルゴリズムを採用して、定数ベクトル要素の２ビットごとに、下位ビットを付け加えた３ビットのパターンから加減算すべき部分積すなわち入力ベクトル要素自身“Ｍ”もしくは、その２倍値“２Ｍ”を累算する。すなわち、入力ベクトル要素またはシフトタ１１が２倍にした入力ベクトル要素のいずれかを選択して加減算器１３に累算する。自身もしくは２倍値の生成と選択は、シフタ１１とセレクタ１２をサイクルごとに制御することでこれを行う。定数ベクトル要素の２ビットごとに同位桁の部分積の累算を終了すると、上位桁の累算を開始するためにシフタ１４でアキュムレータ５の内容が２ビット右シフトされて、次の加減算の入力となる。
【０１０７】
図８に本実施形態の動作のプログラムリストを示す。図８も図２、図４、図６と同様に数４のＺ１を求める場合のものである。このプログラムは制御部８で動作する。
【０１０８】
図８のプログラムリストを説明すると、ステップ００１はアキュムレータ５のリセットを行い、演算をリセットしている。ステップ００２〜００５にかけて定数ベクトルの各要素の最下位のべき乗項であるｂｉｔ１とｂｉｔ０の２ビットすなわち２の１乗項と２の０乗項に対する加減算すべき部分積として図３に示したブースのアルゴリズム表にしたがって入力ベクトルの各要素自身もしくはその２倍値をサイクルごとに累積加減算している。なお、演算内容については、第２の実施形態と同等であるので説明を省略する。加減算器１３の出力はアキュムレータ５の上位１１ビットに接続されているので、アキュムレータ５の６ビット目を最下位ビットとして、最初の累算結果が得られる。
【０１０９】
次に、ステップ００６ではブースのアルゴリズムにしたがって、２ビット分上位桁の部分積の累算を開始するためにアキュムレータの内容がシフタ１４によって、右シフトされて加減算器１３に入力される。ステップ００６〜０１３にかけては、定数ベクトル各要素の２の２乗項と２の３乗項の部分積の累積加減算が実行され、以下順にステップ０１４〜０２１にかけて２は４乗項と２の５乗項、ステップ０２２〜０２５にかけて２は６乗項と２の７乗項、ステップ０２６〜０３１にかけては２の８乗項と２の９乗項の部分積の累積加減算を行っている。
【０１１０】
ステップ０３２はアキュムレータ５の内容を２ビットずつ右シフトするだけの動作がなされ、有効桁の桁合わせが行われる。そして、最終的には整数部符号付１２ビット小数部４ビットで計１６ビットの演算結果が得られる。
【０１１１】
本実施形態によれば、定数ベクトル要素の２ビットごとに部分内積の累算を行うことで内積演算を遂行するので、累算すべき部分積の個数が減じられ、制御ステップが削減でき、演算サイクル数をさらに削減できる。例えば第３の実施形態（図６）と本実施形態（図８）とを比較すると、図６では４１ステップ必要であるのに対して、図８では３２ステップと２０％程度の演算速度の改善がなされる。
【０１１２】
（第５実施形態）
次に、本発明の第５の実施形態を図９ないし図１３を参照して説明する。なお、前述した第１〜第４の実施形態と同一部分には、同一符号を付して説明を省略する。図９は、本発明の第５の実施形態にかかる内積演算方法を実行するマイクロプロセッサの演算器部分の構成図である。図１０は、図９に示したマイクロプロセッサの機械語命令コードフォーマットである。図１１は、図９に示したマイクロプロセッサの内積演算動作を示したプログラムリストの一の部分である。図１２は、図９に示したマイクロプロセッサの内積演算動作を示したプログラムリストの他の部分である。図１３は、図９に示したマイクロプロセッサで動作する内積演算方法のフローチャートである。
【０１１３】
本実施形態は、マイクロプロセッサなどプログラム命令で実施可能な内積演算方法を示す。特に、専用の乗算回路と命令もしくは内積演算専用の回路と命令を有しないマイクロプロセッサで実現可能な内積演算方法を示す。
【０１１４】
図３に示した演算装置としてのマイクロプロセッサ２０は、論理積・論理和・算術加算・算術減算を行う加減算手段としての算術論理演算器（ＡＬＵ）２２と、ＡＬＵ２２の演算結果が格納されるアキュムレータ２４と、バス３０を介してアキュムレータ２４およびバレルシフタ２８と接続される格納手段としてのレジスタ２６と、レジスタ２６から送り出されたオペランドデータを左シフトしてＡＬＵ２２に送るシフト手段としてのバレルシフタ２８と、を備えている。
【０１１５】
ＡＬＵ２２は、１６ビット語長の算術論理演算器で、一方の入力にはバレルシフタ２８の出力が接続されており、レジスタ２６から送り出されたオペランドデータを左シフトしてＡＬＵ２２に入力する。他方の入力にはアキュムレータ２４の出力が接続され、ＡＬＵ２２の出力はアキュムレータ２４に接続されて、ＡＬＵ２２の演算結果がアキュムレータ２４に蓄積されるようにしてある。
【０１１６】
アキュムレータ２４は、１６ビット語長で構成され、ＡＬＵ２２の他方の入力と、８ビット幅のバス３０を介してレジスタ２６に接続されており、アキュムレータ２４に蓄積されたデータがレジスタ２６に転送できるようにしてある。
【０１１７】
レジスタ２６は、例えば汎用レジスタとしてＲ０〜Ｒ３１の３２本の８ビット幅のレジスタを備えている。
【０１１８】
バレルシフタ２８は、レジスタ２６に格納されている８ビットデータ（オペランドデータ）を後述する機械語命令コードで指定された分のシフト量のシフトを行い１６ビットデータとしてＡＬＵ２２に出力する。
【０１１９】
機械語命令コード３７は、図１０に示したように、演算の種類Ｃ、符号拡張の指定Ｓ、シフト量ＢＳＨの情報を含む。演算の種類Ｃには、加算、減算、論理積、論理和の演算が含まれ、Ｃの値により区別される。符号拡張Ｓには、ゼロ拡張と符号拡張があり、ゼロ拡張の場合はＳに０が指定され、符号拡張の場合はＳに１が指定される。シフト量ＢＳＨはゼロ桁から１５桁まで指定可能となっている。
【０１２０】
図１１および図１２に上述した構成のマイクロプロセッサ２０において内積演算行うためのプログラムリストを示す。ここで入力ベクトル要素はレジスタＴｍＲ０（レジスタ２６のＲ０）からＴｍＲ７（レジスタ２６のＲ７）のラベルのレジスタに格納されているとする。図１１および図１２に示したプログラムリストも図２、図４、図６、図８と同様に数４のＺ１を求める場合のものである。
【０１２１】
次に、命令ニモニックについて説明する。
ｌｄａ ＃０
この命令はアキュムレータ２４にゼロ値をロードする命令のニモニックである。
ａｄｄ ＴｍＲ０：ｓ０
この命令はアキュムレータ２４の値にソースオペランドである“ＴｍＲ０”ラベルのレジスタ値を呼び出して加算する命令のニモニックである。ソースオペランドである“ＴｍＲ０”の右側に“：ｓ０”と補助コードが付加されているがこれは“ｓ”に続く数字のビット数分の符号およびビット拡張つきの左シフトを行ってレジスタ値を読み出す動作を行うことを意味する。同様に“ｓｕｂ”は減算命令である。
【０１２２】
“ｓｔａ”はアキュムレータ２４内容をデスティネーションオペランドに書き出す命令で、例えば、
ｓｔａ ＴｍＲ１２：ｚ５
と記述され、これはデスティネーションオペランドである“ＴｍＲ１２”の右側に“：ｚ５”と補助コードが付加されているが、これは“ｚ”に続くビット数分の右シフトを行ってアキュムレータ２４の内容をレジスタ２６に転送する動作を行う。“ｌｄａ”は即値もしくはソースオペランドのレジスタ値をアキュムレータ２４に読み出す命令である。
【０１２３】
図１１および図１２に示したプログラムリストでセミコロンの付加された行はコメント行であり、その行の命令は実行されない。図中では理解を容易にするためにコメントとして命令ニモニックが残してある。コメント行の命令は定数ベクトルのビット値が“０”である桁の部分積の加減算を表しており、第１の実施形態でも説明したように、これらの部分積の加減算は実行されない。
【０１２４】
図１１および図１２に示したプログラムリストの演算動作については、定数ベクトル要素の数値および動作は第１の実施形態と同じであるが、概略動作を図１３のフローチャートを参照して説明する。
【０１２５】
まず、アキュムレータ２４にゼロ値ロードしてリセットし（ステップＳ１、図１１の先頭行）、定数ベクトル要素の最下位桁の部分積を求め、部分積を累算し、全定数ベクトル要素の累算が終了するまで繰り返す（ステップＳ２〜Ｓ４、例えば図１１のＣＯＥＦ＿ｂｉｔ１ ＭＵＬ／ＡＤＤ以下の８ステップ）。すなわち、ステップＳ２が特許請求の範囲の第一の工程に相当し、ステップＳ３が特許請求の範囲の第二の工程に相当する。
【０１２６】
次に、１つ上の桁に移動して（ステップＳ５）、定数ベクトル要素の最下位桁の部分積を求め、部分積を累算し、全定数ベクトル要素の累算が終了するまで繰り返す（ステップＳ６〜Ｓ８、例えば図１１のＣＯＥＦ＿ｂｉｔ２ ＭＵＬ／ＡＤＤ以下の８ステップ）。そして、この繰り返しは最上位桁が終了するまで繰り返し、最上位桁まで終了した場合は処理を終了する（ステップＳ１１）。すなわち、ステップＳ６が特許請求の範囲の第一の工程に相当し、ステップＳ７が特許請求の範囲の第二の工程に相当する。
【０１２７】
なお、累算結果がアキュムレータ２４の最大桁の達した場合は、５ビット右シフトして切り捨て丸め処理を行う（ステップＳ９、Ｓ１０、図１１の中間結果／Ｏｖｅｒｆｌｏｗ（１６ｂｉｔ）回避の部分）。すなわち、ステップＳ１０が特許請求の範囲の第三の工程に相当する。なお、この切り捨てる５ビットも第１の実施形態と同様に、加減算器４のビット語長から入力ベクトル要素のビット語長および入力ベクトル要素数の２を底とする対数を減じた数以下のビット桁数から算出されて予め決められたものである。
【０１２８】
また、本実施形態において、演算結果はアキュムレータ２４に格納され１６ビット幅であるが、次の段階のプログラム命令に渡すために、ＴｍＲ１２（レジスタ２６のＲ１２）、ＴｍＲ１３（レジスタ２６のＲ１３）のラベルのレジスタに下位、上位に分けて転送している。また、演算途中の５ビット右シフトによる切捨て丸め操作は、レジスタ幅と命令セットの都合上、上位、下位にわけて実施している。
【０１２９】
本実施形態によれば、専用の乗算回路と命令もしくは内積演算専用の回路と命令を有しないマイクロプロセッサ２０において、ソースオペランドのシフトが一体となった加減算命令を使って、同じ桁の部分積を下位から順に累算して行くことにより、下位桁累算からの繰り上がりを落とすことなくすなわち演算精度を確保して内積演算を行うことができる。また累算途中結果を一旦ビットシフトして丸めるステップを備えているので乗算の最大語長より小さい語長の演算器構成のマイクロプロセッサでも精度の良い内積演算を実現できる。
【０１３０】
（第６実施形態）
次に、本発明の第６の実施形態を図１４を参照して説明する。なお、前述した第１〜第５の実施形態と同一部分には、同一符号を付して説明を省略する。図１４は、本発明の第６の実施形態にかかるマイクロプロセッサの内積演算動作を示したプログラムリストである。
【０１３１】
本実施形態は、構成は第５の実施形態と同じであるが、第２、第４の実施形態の説明のごとく２次のブースのアルゴリズムを採用して、定数ベクトル要素の２ビットごとに、下位ビットを付け加えた３ビットのパターンから加減算すべき部分積すなわち入力ベクトル要素自身“Ｍ”もしくは、その２倍値“２Ｍ”を累算する。すなわち、第一の工程は、入力ベクトル要素自身または入力ベクトル要素の２倍の値のいずれかを選択して部分積を求め、第二の工程は、部分積の累算を２ビット毎に行っている。
【０１３２】
図１４に本実施形態の動作のプログラムリストを示す。図１４も図２、図４、図６、図８、図１１、図１２と同様に数４のＺ１を求める場合のものである。なお、演算内容については、第２の実施形態と同等であるので説明を省略する。
【０１３３】
本実施形態によれば、定数ベクトル要素の２ビットごとに部分内積の累算を行うことで内積演算を遂行するので、累算すべき部分積の個数が減じられ、制御ステップが削減でき、演算サイクル数をさらに削減できる。例えば第５の実施形態（図１１、図１２）と本実施形態（図１４）とを比較すると、図６では４８ステップ必要であるのに対して、図８では３８ステップと２０％程度の演算速度の改善がなされる。
【０１３４】
なお、本発明は上記実施形態に限定されるものではない。即ち、本発明の骨子を逸脱しない範囲で種々変形して実施することができる。
【符号の説明】
【０１３５】
１ 内積演算装置
２ 入力要素レジスタ（格納手段）
３ バレルシフタ（シフト手段）
４ 加減算器（加減算手段）
５ アキュムレータ
６ シフタ（丸め手段）
７ セレクタ
８ 制御部（演算制御手段）
９ 加減算器（加減算手段）
１０ シフタ（第一シフト手段）
１１ シフタ（第二シフト手段）
１２ セレクタ
１３ 加減算器（加減算手段）
１４ シフタ（第一シフト手段）
２０ マイクロプロセッサ（演算装置）
２２ ＡＬＵ（加減算手段）
２４ アキュムレータ
２６ レジスタ（格納手段）
２８ バレルシフタ（シフト手段）
【先行技術文献】
【特許文献】
【０１３６】
【特許文献１】特公平５−２６２２９号公報
【特許文献２】特開２０００−１３２５３９号公報
【特許請求の範囲】
【請求項１】
所定のビット語長を有する複数の入力ベクトル要素から構成される入力ベクトルと複数の定数ベクトル要素から構成される定数ベクトルとの内積を求める内積演算装置において、
前記複数の入力ベクトル要素を格納する格納手段と、
前記格納手段から前記入力ベクトル要素を選択して、選択された前記入力ベクトルを左ビットシフトさせることにより前記定数ベクトル要素の２のべき乗項と入力ベクトル要素との部分積を求めるシフト手段と、
前記シフト手段が求めた前記部分積を累算するとともに、前記入力ベクトル要素と前記定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成された加減算手段と、
前記加減算手段の累算結果を格納するアキュムレータと、
予め定めた桁数のビットシフトにより前記加減算手段による累算途中の前記アキュムレータに格納された結果の切り捨てを行って演算結果の丸めを行う丸め手段と、
前記加減算手段に、前記定数ベクトル要素の最下位の２のべき乗項の同じ項にかかる全ての入力ベクトル要素の部分積の累算を行わせて前記アキュムレータに格納させて、以降、順次高位の２のべき乗項にかかる部分積の累算を繰り返して最上位の２のべき乗項まで繰り返させるとともに、前記加減算手段の桁あふれが発生する前に前記丸め手段により類算途中の前記アキュムレータに格納された結果の下位桁を切捨てさせて、以降の累算の初期値とするように動作させる演算制御手段と、
を備えていることを特徴とする内積演算装置。
【請求項２】
前記演算制御手段が、予め定めたテーブルに基づいて、前記シフト手段に対して前記入力ベクトル要素の２ビット毎に前記部分積を求めさせ、前記加減算手段に対して該部分積を累算させることを特徴とする請求項１に記載の内積演算装置。
【請求項３】
前記丸め手段が前記加減算手段による累算途中の前記アキュムレータに格納された結果の切り捨てを行うビット桁数は、前記加減算手段のビット語長から前記入力ベクトル要素のビット語長および前記入力ベクトル要素数の２を底とする対数を減じた数以下のビット桁数として予め定められていることを特徴とする請求項１または２に記載の内積演算装置。
【請求項４】
所定のビット語長を有する複数の入力ベクトル要素から構成される入力ベクトルと複数の定数ベクトル要素から構成される定数ベクトルとの内積を求める内積演算装置において、
前記複数の入力ベクトル要素を格納する格納手段と、
前記格納手段から前記入力ベクトル要素を選択して、前記定数ベクトル要素の２のべき乗項と選択された前記入力ベクトル要素との部分積を求めて累算するとともに、前記入力ベクトル要素と前記定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成された加減算手段と、
前記加減算手段の累算結果を自身の上位桁側に格納するアキュムレータと、
前記アキュムレータの内容を下位桁方向に右ビットシフトして以降の累算値とするとともに、前記入力ベクトル要素と前記定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成された第一シフト手段と、
前記加減算手段に、前記定数ベクトル要素の同じ桁の２のべき乗項の同じ項にかかる全ての入力ベクトル要素の部分積の累算を行わせて前記アキュムレータに格納させて、前記第一シフト手段に前記アキュムレータに格納された累算結果を右ビットシフトさせる動作を前記定数ベクトル要素の２のべき乗項の最上位桁まで繰り返させる演算制御手段と、
を備えていることを特徴とする内積演算装置。
【請求項５】
前記格納手段に格納された前記入力ベクトル要素を２倍する第二シフト手段を備え、
前記演算制御手段が、予め定めたテーブルに基づいて、前記格納手段に格納された前記入力ベクトル要素または前記第二シフト手段が２倍にした入力ベクトル要素のいずれかを選択して前記加減算手段に累算させるとともに、前記第一シフト手段に２ビットシフトさせることを特徴とする請求項４に記載の内積演算装置。
【請求項６】
所定のビット語長を有する複数の入力ベクトル要素から構成される入力ベクトルを格納する格納手段と、前記入力ベクトルを左ビットシフトさせることにより複数の定数ベクトル要素から構成される定数ベクトルの２のべき乗項と前記入力ベクトル要素との部分積を求めるシフト手段と、前記シフト手段が求めた前記部分積を累算するとともに、前記入力ベクトル要素と前記定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成された加減算手段と、前記加減算手段の累算結果を格納するアキュムレータと、を備えたマイクロプロセッサでオペランドの加減算とシフトが一体に実行可能な命令を用いて前記入力ベクトルと前記定数ベクトルとの内積を求める内積演算方法において、
前記シフト手段が前記格納手段から前記入力ベクトル要素を選択して前記部分積を求める第一の工程と、
前記加減算手段に、前記定数ベクトル要素の最下位の２のべき乗項の同じ項にかかる全ての前記入力ベクトル要素の前記部分積の累算を行わせて前記アキュムレータに格納させる第二の工程と、
前記加減算手段の桁あふれが発生する前に前記アキュムレータに格納させている類算途中の前記アキュムレータに格納された結果の下位桁を切捨てて、以降の累算の初期値とする第三の工程と、
を備え、
前記第一の工程と前記第二の工程を順次高位の２のべき乗項にかかる部分積の累算を繰り返して最上位の２のべき乗項まで繰り返すとともに、前記第一の工程と前記第二の工程の繰り返しの途中に少なくとも前記第三の工程を１回以上行う
ことを特徴とする内積演算方法。
【請求項７】
前記第一の工程は、前記入力ベクトル要素自身または前記入力ベクトル要素の２倍の値のいずれかを選択して前記部分積を求め、
前記第二の工程は、前記部分積の累算を２ビット毎に行う
ことを特徴とする請求項６に記載の内積演算方法。
【請求項８】
前記第三の工程で前記加減算手段による累算途中の前記アキュムレータに格納された結果の切り捨てを行うビット桁数は、前記加減算手段のビット語長から前記入力ベクトル要素のビット語長および前記入力ベクトル要素数の２を底とする対数を減じた数以下のビット桁数として予め定められていることを特徴とする請求項６または７に記載の内積演算方法。
【請求項１】
所定のビット語長を有する複数の入力ベクトル要素から構成される入力ベクトルと複数の定数ベクトル要素から構成される定数ベクトルとの内積を求める内積演算装置において、
前記複数の入力ベクトル要素を格納する格納手段と、
前記格納手段から前記入力ベクトル要素を選択して、選択された前記入力ベクトルを左ビットシフトさせることにより前記定数ベクトル要素の２のべき乗項と入力ベクトル要素との部分積を求めるシフト手段と、
前記シフト手段が求めた前記部分積を累算するとともに、前記入力ベクトル要素と前記定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成された加減算手段と、
前記加減算手段の累算結果を格納するアキュムレータと、
予め定めた桁数のビットシフトにより前記加減算手段による累算途中の前記アキュムレータに格納された結果の切り捨てを行って演算結果の丸めを行う丸め手段と、
前記加減算手段に、前記定数ベクトル要素の最下位の２のべき乗項の同じ項にかかる全ての入力ベクトル要素の部分積の累算を行わせて前記アキュムレータに格納させて、以降、順次高位の２のべき乗項にかかる部分積の累算を繰り返して最上位の２のべき乗項まで繰り返させるとともに、前記加減算手段の桁あふれが発生する前に前記丸め手段により類算途中の前記アキュムレータに格納された結果の下位桁を切捨てさせて、以降の累算の初期値とするように動作させる演算制御手段と、
を備えていることを特徴とする内積演算装置。
【請求項２】
前記演算制御手段が、予め定めたテーブルに基づいて、前記シフト手段に対して前記入力ベクトル要素の２ビット毎に前記部分積を求めさせ、前記加減算手段に対して該部分積を累算させることを特徴とする請求項１に記載の内積演算装置。
【請求項３】
前記丸め手段が前記加減算手段による累算途中の前記アキュムレータに格納された結果の切り捨てを行うビット桁数は、前記加減算手段のビット語長から前記入力ベクトル要素のビット語長および前記入力ベクトル要素数の２を底とする対数を減じた数以下のビット桁数として予め定められていることを特徴とする請求項１または２に記載の内積演算装置。
【請求項４】
所定のビット語長を有する複数の入力ベクトル要素から構成される入力ベクトルと複数の定数ベクトル要素から構成される定数ベクトルとの内積を求める内積演算装置において、
前記複数の入力ベクトル要素を格納する格納手段と、
前記格納手段から前記入力ベクトル要素を選択して、前記定数ベクトル要素の２のべき乗項と選択された前記入力ベクトル要素との部分積を求めて累算するとともに、前記入力ベクトル要素と前記定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成された加減算手段と、
前記加減算手段の累算結果を自身の上位桁側に格納するアキュムレータと、
前記アキュムレータの内容を下位桁方向に右ビットシフトして以降の累算値とするとともに、前記入力ベクトル要素と前記定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成された第一シフト手段と、
前記加減算手段に、前記定数ベクトル要素の同じ桁の２のべき乗項の同じ項にかかる全ての入力ベクトル要素の部分積の累算を行わせて前記アキュムレータに格納させて、前記第一シフト手段に前記アキュムレータに格納された累算結果を右ビットシフトさせる動作を前記定数ベクトル要素の２のべき乗項の最上位桁まで繰り返させる演算制御手段と、
を備えていることを特徴とする内積演算装置。
【請求項５】
前記格納手段に格納された前記入力ベクトル要素を２倍する第二シフト手段を備え、
前記演算制御手段が、予め定めたテーブルに基づいて、前記格納手段に格納された前記入力ベクトル要素または前記第二シフト手段が２倍にした入力ベクトル要素のいずれかを選択して前記加減算手段に累算させるとともに、前記第一シフト手段に２ビットシフトさせることを特徴とする請求項４に記載の内積演算装置。
【請求項６】
所定のビット語長を有する複数の入力ベクトル要素から構成される入力ベクトルを格納する格納手段と、前記入力ベクトルを左ビットシフトさせることにより複数の定数ベクトル要素から構成される定数ベクトルの２のべき乗項と前記入力ベクトル要素との部分積を求めるシフト手段と、前記シフト手段が求めた前記部分積を累算するとともに、前記入力ベクトル要素と前記定数ベクトル要素とを乗算した際に必要となる乗算精度よりも小さいビット桁数で構成された加減算手段と、前記加減算手段の累算結果を格納するアキュムレータと、を備えたマイクロプロセッサでオペランドの加減算とシフトが一体に実行可能な命令を用いて前記入力ベクトルと前記定数ベクトルとの内積を求める内積演算方法において、
前記シフト手段が前記格納手段から前記入力ベクトル要素を選択して前記部分積を求める第一の工程と、
前記加減算手段に、前記定数ベクトル要素の最下位の２のべき乗項の同じ項にかかる全ての前記入力ベクトル要素の前記部分積の累算を行わせて前記アキュムレータに格納させる第二の工程と、
前記加減算手段の桁あふれが発生する前に前記アキュムレータに格納させている類算途中の前記アキュムレータに格納された結果の下位桁を切捨てて、以降の累算の初期値とする第三の工程と、
を備え、
前記第一の工程と前記第二の工程を順次高位の２のべき乗項にかかる部分積の累算を繰り返して最上位の２のべき乗項まで繰り返すとともに、前記第一の工程と前記第二の工程の繰り返しの途中に少なくとも前記第三の工程を１回以上行う
ことを特徴とする内積演算方法。
【請求項７】
前記第一の工程は、前記入力ベクトル要素自身または前記入力ベクトル要素の２倍の値のいずれかを選択して前記部分積を求め、
前記第二の工程は、前記部分積の累算を２ビット毎に行う
ことを特徴とする請求項６に記載の内積演算方法。
【請求項８】
前記第三の工程で前記加減算手段による累算途中の前記アキュムレータに格納された結果の切り捨てを行うビット桁数は、前記加減算手段のビット語長から前記入力ベクトル要素のビット語長および前記入力ベクトル要素数の２を底とする対数を減じた数以下のビット桁数として予め定められていることを特徴とする請求項６または７に記載の内積演算方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２０１２−２２３６３（Ｐ２０１２−２２３６３Ａ）
【公開日】平成２４年２月２日（２０１２．２．２）
【国際特許分類】
【出願番号】特願２０１０−１５７５６４（Ｐ２０１０−１５７５６４）
【出願日】平成２２年７月１２日（２０１０．７．１２）
【出願人】（０００００６７４７）株式会社リコー (37,907)
【Ｆターム（参考）】
【公開日】平成２４年２月２日（２０１２．２．２）
【国際特許分類】
【出願日】平成２２年７月１２日（２０１０．７．１２）
【出願人】（０００００６７４７）株式会社リコー (37,907)
【Ｆターム（参考）】
[ Back to top ]