(57)【特許請求の範囲】
【請求項１】
第１の所定数より成る列成分と第２の所定数より成る行成分により構成される行列データを符号部分と絶対値部分とにより表現して順次蓄積する行列データ蓄積手段と、
前記行列データ蓄積手段に蓄積された行列データの特定の列成分の列番号を指定するアドレス制御信号を出力すると共に前記行列データ前記符号部分を符号制御信号として出力する符号制御部と、前記アドレス制御信号に対応する前記行列データの前記絶対値部分を加算制御信号として出力する加算制御部と、を含む演算制御手段と、
前記行列データの列成分に対応する係数データとその反対符号のデータとを予め符号部分と絶対値部分とにより表現して格納すると共に前記符号制御部より出力される前記アドレス制御信号および前記符号制御信号に基づいて対応する列成分のデータを順次出力する読出し専用記憶手段と、
前記行列データの前記行成分ごとに設けられて前記読出し専用記憶手段より供給された前記列成分の符号に対応する前記係数データを一時的に蓄積すると共に前記符号制御信号および加算制御信号に基づいて前記アドレス制御信号の１周期ごとに前記係数データの前記絶対値部分を所定量ずつ所定方向に移動させる複数の入力蓄積部と、前記加算制御信号に応じて前記読出し専用記憶手段からのデータの加算・非加算を切り換える複数の加算部と、前記複数の加算部の各々の積算値を一時的に蓄積すると共にこの積算値を前記所定量ずつ前記所定方向に移動させる複数の出力蓄積部と、より各々が構成される複数の累積加算回路より成る累積加算手段と、
を備えることを特徴とする行列ベクトル乗算器。
【請求項２】
前記累積加算手段の入力蓄積部は前記符号制御信号および加算制御信号に基づいて前記係数データの前記絶対値部分を１ビットずつ左へシフトさせるシフト機能を備えた入力レジスタにより構成され、前記出力蓄積部は前記符号制御信号および加算制御信号に基づいて前記加算部の積算値を１ビットずつ左へシフトさせて出力する出力レジスタにより構成されていることを特徴とする請求項１に記載の行列ベクトル乗算器。
【請求項３】
前記累積加算手段の入力蓄積部は前記符号制御信号および加算制御信号に基づいて前記係数データの前記絶対値部分を１ビットずつ右へシフトさせるシフト機能を備えた入力レジスタにより構成され、前記出力蓄積部は前記符号制御信号および加算制御信号に基づいて前記加算部の積算値を１ビットずつ右へシフトさせて出力する出力レジスタにより構成されていることを特徴とする請求項１に記載の行列ベクトル乗算器。
【請求項４】
前記累積加算手段の前記累積加算回路は前記行列データの列数である前記第１の所定数と同数設けられ、前記読出し専用記憶手段は前記行列データの前記第１の所定数と同数の行成分データを同時に出力し、前記累積加算回路が並列に動作して前記読出し専用記憶手段からの行成分のデータを積算することを特徴とする請求項１に記載の行列ベクトル乗算器。
【請求項５】
前記累積加算回路は、前記行列データ蓄積手段からの前記加算制御信号およびアドレス制御信号の組合せにより、内容を０に設定するリセットモード，現在の値を更新する通常モード，現在の値を保持するホールドモード，および入力を１ビットシフトして内部に設定するシフトモードのそれぞれのモードを切り換える機能を有する１対の前記入力蓄積部および出力蓄積部が一方の入力と出力とに接続され、さらに前記出力蓄積部の出力が分岐して他方の入力に接続されるように構成されていることを特徴とする請求項１に記載の行列ベクトル乗算器。
【請求項６】
前記演算制御手段の前記符号制御部は、クロック信号ごとにその内容を１つずつ積算するカウンタにより構成されていることを特徴とする請求項１に記載の行列ベクトル乗算器。
【請求項７】
前記演算制御手段の前記符号制御部は、前記カウンタの前記クロック信号の下位側の複数のビット数により前記アドレス制御信号を発生させることを特徴とする請求項６に記載の行列ベクトル乗算器。
【請求項８】
前記累積加算手段は、前記行列データ蓄積手段の蓄積する行列データの特定位のビット列を前記加算制御信号として用いて、前記アドレス制御信号が１周期を経過するごとに前記加算制御信号として用いる前記ビット列の位置を１ビット右シフトすることを特徴とする請求項１に記載の行列ベクトル乗算器。
【請求項９】
前記累積加算手段は、前記行列データ蓄積手段の入力データビット幅分だけ左シフトした位置に、前記読出し専用記憶手段から読出されたデータの符号拡張を行なってから保持するように構成されていることを特徴とする請求項８に記載の行列ベクトル乗算器。
【請求項１０】
前記演算制御手段の前記加算制御部は、前記行列データ蓄積手段の任意の桁から成るビット列を選択して、これを前記加算制御信号である選択信号として送出する機能を備えるセレクタより構成されていることを特徴とする請求項１に記載の行列ベクトル乗算器。
【請求項１１】
前記演算制御手段の前記符号制御部は、クロック信号ごとにその内容を１つずつ積算するカウンタにより構成され、このカウンタの上位側の複数のビットを前記セレクタの選択信号として前記累積加算手段が用いることを特徴とする請求項１０に記載の行列ベクトル乗算器。
【請求項１２】
前記累積加算手段は、前記行列データ蓄積手段の蓄積する行列データの特定位のビット列を前記加算制御信号として用いて、前記アドレス制御信号が１周期を経過するごとに前記加算制御信号として用いる前記ビット列の位置を１ビット左シフトすることを特徴とする請求項１に記載の行列ベクトル乗算器。
【請求項１３】
前記累積加算手段は、前記行列データ蓄積手段の入力データビット幅分だけ右シフト位置に、前記読出し専用記憶手段から読出されたデータの符号拡張を行なってから保持するように構成されていることを特徴とする請求項１２に記載の行列ベクトル乗算器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、行列ベクトル乗算器に係り、特に行列（マトリックス）とベクトルの演算処理を高速かつ低消費電力で行なうことができる行列ベクトル乗算器に関するものである。
【０００２】
【従来の技術】
画像データ圧縮のための基礎的な要素アルゴリズムとして広く用いられているものに、離散コサイン変換（以下、ＤＣＴ― Discrete Cosine Transform―と略記する。）方法およびその逆変換（以下、ＩＤＣＴ―Inverse Discrete Cosine Transform ―と略記する。）方法を用いた帯域圧縮技術がある。上記のＤＣＴやＩＤＣＴはいずれも直交変換の一種であるが、実際の演算においては定数係数のマトリックスとベクトルの乗算であり、画素値のベクトルｘn 、ＤＣＴ係数のベクトルＸk に対し下式で定義される：
【０００３】
【数１】
0003895031.tif 000002
動画像圧縮の国際標準規格であるＭＰＥＧ（Moving Picture Experts Group）１、ＭＰＥＧ２等においては水平方向・垂直方向に各々８画素ずつの６４画素からなる正方形型の領域（ブロック）を単位としたＮ＝８の２次元ＤＣＴおよびＩＤＣＴが用いられている。
【０００４】
動画像圧縮装置は一般に演算量が非常に大きく、特に実時間処理が必要な利用形態（ＨＤＴＶ放送、ＴＶ電話、映像監視システム等）における動画像圧縮符号化・復号化はその処理系に対して要求される性能が非常に高くなっている。このため、上記離散コサイン変換および逆変換の計算も高速アルゴリズムと専用ハードウェアを用いて処理するのが一般的であり、積和演算の回数を大幅に削減できるチェン（Ｃｈｅｎ）の高速アルゴリズムや、乗算器を用いずに計算を実行できる分散演算（ＤＡ―Distributed Arithmetic―）法などの方式が広範に用いられており、これらを応用した専用ハードウェアの構成としては、例えば文献IEICE Trans. Electron., Vol. E75-C(1992), No.4 pp.390-397 等に開示されている。ここではＤＡ法による離散コサイン変換の計算方法、およびハードウェアの構成方法を簡単に説明する。
【０００５】
まず、上記式（１）のマトリックス−ベクトル乗算の第ｋ行は次のような内積の形に表すことができる：
【０００６】
【数２】
0003895031.tif 000003
さらに、ハードウェアのデータパスのビット幅をＭとする時、各Ｘn は２進数（２の補数表現）で：
【０００７】
【数３】
0003895031.tif 000004
と表されるので、上記式（２）は内積の線形性を用いると：
【０００８】
【数４】
0003895031.tif 000005
の形となる。ここで、部分和
【０００９】
【数５】
0003895031.tif 000006
は入力データ｛ｘn ｝のｉビット目｛ｂn,i ｝の関数であるが、予めあらゆるビットパターン（２N 通り）について計算しメモリに格納しておけば、｛ｂn,i ｝をＮビットのアドレスとみなして読み出すことができる。また、２i-1 の乗算はｉ−１ビットの左シフトに対応していることに注意すると、結局上記式（４）はＮビットアドレスのメモリ参照と左シフト、加算および減算の組み合わせにより求めることができることが分かる。
【００１０】
ＤＡ法は上述の原理を応用したものであり、以下、Ｎ＝８の場合の具体的な乗算器の構成とその手順の一例について図１０ないし図１２を参照しながら説明する。まず、図１０を用いて従来の行列ベクトル乗算器の回路構成について説明する。図１０において、従来の行列ベクトル演算回路は、各行毎に入力ポートを有し、第１の所定数であるｎ列と第２の所定数であるｋ行の縦横方向に０か１の情報が配列されたデータとしてのマトリックス１と、図１１を用いて後述するようなテーブルを格納すると共にアドレス信号により前記マトリックス１のｉビット目毎の行方向から読み出された情報により前記テーブルの対応する項目が読み出される読出し専用メモリ（以下、ＲＯＭ―Read Only Memory―と略記する。）２と、このＲＯＭ２より読出された値を累積加算する累積加算器５と、を備えている。
【００１１】
累積加算器５は、ＲＯＭ２に格納されたテーブルより読み出したビットスライスを所定量、例えば３ビットずつシフトさせるシフタ６と、このシフタ６の出力を順次に累積加算する２入力１出力の加算器７と、加算器７の出力を一時的に蓄積すると共に前記加算器７の他方の入力側にその出力を供給する出力レジスタ８と、を備えている。この従来の演算回路によれば、実質上はシフタ３と加算器４だけでマトリックス・ベクトル演算を行なっているために、簡単な構成で複雑な演算を処理することができ、汎用の演算器回路を適用できる長所がある。
【００１２】
上記構成の従来の行列ベクトル乗算器の動作について説明する。まず、図１１に示すように、全ての８ビットパターン｛ｂn ｝（２8 ＝２５６通り）についてマトリックスの各行ｋ（ｋ＝０，…，７）に対応する部分和をあらかじめ必要な精度（例えば１６ビット）で計算したテーブルを作成する。図１１に示されるテーブルは、上述したように、図１０に示すＲＯＭ２に予め格納されている。このＲＯＭ２は、８ビットのアドレスで１６ビットの精度を有する場合、その容量は４キロバイトとなる。
【００１３】
次に、８個の入力データ｛ｘn ；ｎ＝０，…，７｝の各々から２進表現の最下位ビット（以下、ＬＳＢ― Least Significant Bit―と略記する。）を取り出して、この８ビット｛ｂn,0 ｝をアドレス信号として前記ＲＯＭ２から読出した部分和のデータを各行ごとに累積加算器５により積算する。続いて、下から２番目のビット｛ｂn,1 ｝をアドレスとして部分和のデータをＲＯＭ２から読み出した後、１ビット左シフトを行ない（これが２を乗算することに相当している）、累積加算器５により積算する。以下同様に、図１１に示すように、下からｉ番目のビットについて部分和をｉ−１ビット左シフトして積算する動作｛図１２（ａ）（ｂ）参照｝を最上位ビット（以下、ＭＳＢ―Most Significant Bit―と略記する。）の直前まで繰り返すことにより、上記式（４）の第２項が累積加算器に積算される。ＭＳＢについては符号ビットであるため、｛ｂn,M-1 ｝のアドレスで部分和を読み出して、これを「Ｍ−１」ビットだけ左へシフトした後、符号を反転してから積算を行なうと上記式（４）の第１項が加算されて、式（４）の解が求められることになる。
【００１４】
この方法を用いると、乗算専用のハードウェアを用意することなく図１０に示すようにな簡単な汎用の演算回路により行列（マトリックス）とベクトルデータとの積を簡単に計算することができるため、ハードウェア量を節約して高速に処理をする目的には適している。
【００１５】
【発明が解決しようとする課題】
しかしながら、上述した従来の行列ベクトル乗算器によれば、入力データの性質や内容の相関に関係なく、その演算量やハードウェアの稼働率は常に一定であるため、例えば「０」を連続的に演算する等のように、自明な計算や不必要な計算についても累積加算器５を動作させなければならず、演算効率が良好でないという問題があった。
【００１６】
また、良く知られているように、ＤＡ法においてはどのような性質を持ったデータ列に対しても常に同じ動作を行なうことになり、上述の例のように不要な計算や自明な計算を繰り返すことに起因するスイッチング動作の機会が増加し、このため効率が悪いばかりでなく、消費電力の増加を招くという問題もあった。さらに、メモリへのアクセスが入力データの各桁をアドレスとしたランダムアクセスとなるので、メモリに高度な機能が要求されることになり、マトリックス１を読み込むＲＯＭ２の構造が複雑になってしまうという問題点もあった。
【００１７】
本発明の目的は、画像処理等に頻繁に現れる定数成分の行列（マトリックス）とベクトル変数の乗算を行なう演算回路を、汎用の乗算器を用いるのではなく、並列に動作する加算器およびシフタと、マトリックスの成分を保持する読み出し専用メモリとを用いて構成することにより、不必要な演算を省略して演算効率の改善を図ると共に消費電力の上昇を抑え、更にマトリックス回路の構造が簡単なもので済む行列ベクトル乗算器を提供することにある。
【００１８】
【課題を解決するための手段】
上記目的を達成するため、本発明に係る行列ベクトル乗算器は、第１の所定数より成る列成分と第２の所定数より成る行成分により構成される行列データを符号部分と絶対値部分とにより表現して順次蓄積する行列データ蓄積手段と、前記行列データ蓄積手段に蓄積された行列データの特定の列成分の列番号を指定するアドレス制御信号を出力すると共に前記行列データの前記符号部分を符号制御信号として出力する符号制御部と、前記アドレス制御信号に対応する前記行列データの前記絶対値部分を加算制御信号として出力する加算制御部と、を含む演算制御手段と、前記行列データの列成分に対応する係数データとその反対符号のデータとを予め符号部分と絶対値部分とにより表現して格納すると共に前記符号制御部より出力される前記アドレス制御信号および前記符号制御信号に基づいて対応する列成分のデータを順次出力する読出し専用記憶手段と、前記行列データの前記行成分ごとに設けられて前記読出し専用記憶手段より供給された前記列成分の符号に対応する前記係数データを一時的に蓄積すると共に前記符号制御信号および加算制御信号に基づいて前記アドレス制御信号の１周期ごとに前記係数データの前記絶対値部分を所定量ずつ所定方向に移動させる複数の入力蓄積部と、前記加算制御信号に応じて前記読出し専用記憶手段からのデータの加算・非加算を切り換える複数の加算部と、前記複数の加算部の各々の積算値を一時的に蓄積すると共にこの積算値を前記所定量ずつ前記所定方向に移動させる複数の出力蓄積部と、より各々が構成される複数の累積加算回路より成る累積加算手段と、を備えることを特徴としている。
【００１９】
また、請求項２に係る行列ベクトル乗算器は、請求項１に記載の乗算器において、前記累積加算手段の入力蓄積部が前記符号制御信号および加算制御信号に基づいて前記行列データの前記絶対値部分を１ビットずつ左へシフトさせるシフト機能を備えた入力レジスタにより構成され、前記出力蓄積部が前記符号制御信号および加算制御信号に基づいて前記加算部の積算値を１ビットずつ左にシフトさせて出力する出力レジスタにより構成されていることを特徴としている。
【００２０】
また、請求項３に係る行列ベクトル乗算器は、請求項１に記載の乗算器において、前記累積加算手段の入力蓄積部が前記符号制御信号および加算制御信号に基づいて前記行列データの前記絶対値部分を１ビットずつ右へシフトさせるシフト機能を備えた入力レジスタにより構成され、前記出力蓄積部が前記符号制御信号および加算制御信号に基づいて前記加算部の積算値を１ビットずつ右にシフトさせて出力する出力レジスタにより構成されていることを特徴としている。
【００２１】
また、請求項４に係る行列ベクトル乗算器は、請求項１に記載の乗算器において、前記累積加算手段の前記累積加算回路が前記行列データの列数である前記第１の所定数と同数設けられ、前記読出し専用記憶手段は前記行列データの前記第１の所定数と同数の行成分データを同時に出力し、前記累積加算回路が並列に動作して前記読出し専用記憶手段からの行成分のデータを積算することを特徴としている。
【００２２】
また、請求項５に係る行列ベクトル乗算器は、請求項１に記載の乗算器において、前記累積加算回路が、前記行列データ蓄積手段からの前記加算制御信号およびアドレス制御信号の組合せにより、内容を０に設定するリセットモード，現在の値を更新する通常モード，現在の値を保持するホールドモード，および入力を１ビットシフトして内部に設定するシフトモードのそれぞれのモードを切り換える機能を有する１対の前記入力蓄積部および出力蓄積部が一方の入力と出力とに接続され、さらに前記出力蓄積部の出力が分岐して他方の入力に接続されるように構成されていることを特徴としている。
【００２３】
また、請求項６に係る行列ベクトル乗算器は、請求項１に記載の乗算器において、前記演算制御手段の前記符号制御部が、クロック信号ごとにその内容を１つずつ積算するカウンタにより構成されていることを特徴としている。
【００２４】
さらに、請求項７に係る行列ベクトル乗算器は、請求項６に記載の乗算器において、前記演算制御手段の符号制御部は、前記カウンタの前記クロック信号の下位側の複数のビットにより前記アドレス制御信号を発生させることを特徴としている。
【００２５】
請求項８に係る行列ベクトル乗算器は、請求項１に記載の乗算器において、前記累積加算手段は、前記行列データ蓄積手段の蓄積する行列データの特定位のビット列を前記加算制御信号として用いて、前記アドレス制御信号が１周期を経過するごとに前記加算制御信号として用いる前記ビット列の位置を１ビット右シフトすることを特徴としている。
【００２６】
さらに、請求項９に係る行列ベクトル乗算器は、請求項８に記載の乗算器において、前記累積加算手段が、前記入力蓄積部の入力データビット幅分だけ左シフトした位置に、前記読出し専用記憶手段から読出されたデータの符号拡張を行なってから保持するように構成されていることを特徴としている。
【００２７】
また、請求項１０に係る行列ベクトル乗算器は、請求項１に記載の乗算器において、前記演算制御手段の前記加算制御部が、前記行列データ蓄積手段の任意の桁からなるビット列を選択して、これを前記加算制御信号である選択信号として送出する機能を備えるセレクタより構成されていることを特徴としている。
【００２８】
また、請求項１１に係る行列ベクトル乗算器は、請求項１０に記載の乗算器において、  前記演算制御手段の前記符号制御部は、クロック信号ごとにその内容を１つずつ積算するカウンタにより構成され、このカウンタの上位側の複数のビットを前記セレクタの選択信号として前記累積加算手段が用いることを特徴としている。
また、請求項１２に係る行列ベクトル乗算器は、請求項１に記載の乗算器において、前記累積加算手段は、前記行列データ蓄積手段の蓄積する行列データの特定位のビット列を前記加算制御信号として用いて、前記アドレス制御信号が１周期を経過するごとに前記加算制御信号として用いる前記ビット列の位置を１ビット左シフトすることを特徴としている。
また、請求項１３に係る行列ベクトル乗算器は、請求項１２に記載の乗算器において、 前記累積加算手段は、前記行列データ蓄積手段の入力データビット幅分だけ右シフト位置に、前記読出し専用記憶手段から読出されたデータの符号拡張を行なってから保持するように構成されていることを特徴としている。
【００２９】
したがって、本発明に係る行列ベクトル乗算器によれば、Ｎ成分からなる入力データの各成分を上位の桁よりビットごとに取り出して、得られたビット列（Ｎ bit）を制御信号として加算器の動作モードを順次切り替え、ＲＯＭから読み出された各ビットに対応する係数データを積算する。この際、制御ビットが１ならばレジスタに保持されたデータを加算し、０ならばレジスタをホールドするようにモードを切り替えることにより、不必要な加算動作をレジスタの更新によるスイッチングを減らすことができ、低消費電力動作が可能となる。Ｎ個の係数データを処理したら結果を１ビット左シフトし、入力データの次の桁について同様の操作を繰り返す。以下同様に全桁を処理するまで繰り返すことになる。
【００３０】
上述の手順により、行列の乗算を正しく行なうために、累積加算手段の入力データに２の補数表現ではなく符号−絶対値表現を用いている。ＭＰＥＧ等の動き補償を用いた動画像圧縮処理においては、Ｐ−ピクチャ等の差分画像のデータは０の周辺に集中している確率が高いため、符号−絶対値表現を用いて表すと上位ビットの０の個数が多くなるため、０が連続的に現れるマトリックスにおいては動作モードをホールド状態にすることにより、スイッチングの回数を一層少なくすることができる。
【００３１】
【発明の実施の形態】
以下、本発明に係る行列ベクトル乗算器の実施形態について図面を参照しながら詳細に説明する。まず、図１を参照して本発明の基本原理としての第１実施形態に係る行列ベクトル乗算器の構成について説明する。
【００３２】
図１において、第１実施形態に係る行列ベクトル乗算器１０は、第１の所定数であるｎ個より成る列成分と第２の所定数であるｋ個より成る行成分により構成される行列データを符号部分と絶対値部分とにより表現して順次蓄積する行列データ蓄積手段１１と、前記行列データ蓄積手段に蓄積された行列データの特定の列成分の列番号を指定するアドレス制御信号を出力すると共に前記行列データの前記符号部分を符号制御信号として出力する符号制御部１３と、前記アドレス制御信号に対応する前記行列データの前記絶対値部分を加算制御信号として出力する加算制御部１４と、を含む演算制御手段１２と、前記行列データの列成分に対応する係数データとその反対符号のデータとを予め符号部分と絶対値部分とにより表現して格納すると共に前記符号制御部１３より出力される前記アドレス制御信号および前記符号制御信号に基づいて対応する列成分のデータを順次出力する読出し専用記憶手段（以下、ＲＯＭ）１５と、前記行列データの前記第１の所定数ｎと同数のｎ個設けられた複数の累積加算回路２１ａないし２１ｎを有する累積加算手段２０と、を備えている。
【００３３】
上記累積加算手段２０は並列接続された複数の累積加算回路２１ａ〜２１ｎを有しており、この複数の累積加算回路２１ａ〜２１ｎは、前記行列データの前記行成分ごとに設けられて前記ＲＯＭ１５より供給された前記列成分の符号に対応する前記係数データを一時的に蓄積すると共に前記符号制御信号および加算制御信号に基づいて前記アドレス制御信号の１周期ごとに前記係数データの前記絶対値部分を所定量ずつ所定方向に移動させる複数の入力蓄積部２３ａ〜２３ｎと、前記複数の入力蓄積部２３ａ〜２３ｎのそれぞれに入力される前記加算制御信号に応じて前記ＲＯＭ１５からのデータの加算・非加算を切り換える複数の加算部２４ａ〜２４ｎと、前記複数の加算部２４ａ〜２４ｎの各々の積算値を一時的に蓄積すると共にこの積算値を前記所定量ずつ前記所定方向に移動させる複数の出力蓄積部２５ａ〜２５ｎと、をそれぞれ備えている。
【００３４】
なお、第１実施形態に係る行列ベクトル乗算器の動作については、以降に詳述する第２ないし第４実施形態の動作の説明により補完するものとしてその詳細説明を省略する。
【００３５】
次に、本発明の第２実施形態に係る行列ベクトル乗算器について、図２ないし図６を参照しながら詳細に説明する。この第２実施形態に係る行列ベクトル乗算器は、上記第１実施形態に係る乗算器の構成を更に具体的なものにして説明するものである。
【００３６】
第２実施形態に係る乗算器は、Ｎ個の入力データを符号−絶対値表現の形で格納するＮ個のＭビットのレジスタと、そのレジスタ群のＭ−１桁目から取り出したＮビットのうち１つを指定するＮ：１セレクタ、マトリックスの成分のデータを格納し列ごとに読み出すことのできるＲＯＭ、Ｎ個が並列に動作してＲＯＭからのデータを積算する累積加算器、マトリックスの列番号を指定する信号を発生するカウンタとから構成される。以下、Ｎ＝８、Ｍ＝１２の場合についてそのアルゴリズム、構成方法、機能および効果を説明する。ここで、上記第１実施形態に係る乗算器１０の構成において、第１の所定数が「８」であり第２の所定数が「１２」ということになる。
【００３７】
まず、第２実施形態に係る乗算器のアルゴリズムについて説明する。入力データのｘnはビット幅を１２として符号−絶対値表現を用いると：
【００３８】
【数６】
0003895031.tif 000007
と表すことができるので、前記（２）の内積計算は線形性を用いると、
【００３９】
【数７】
0003895031.tif 000008
と書くことができる。「ｂi ＝０or１」なので、結局のところ式（６）はマトリックスの各行ｋについて「＋ａk,n 」または「−ａk,n 」または「０」の加算とシフト演算との組み合わせにより求められる。
【００４０】
具体的には、まずマトリックスの各成分のデータおよびその反対符号のデータを格納した読み出し用メモリを用意しておき、このメモリからｎ＝０，…の順にｘn の符号に応じて＋ａk,n または−ａk,n を順次読み出す。８個の入力データｘn は符号−絶対値表現で表しておき、この絶対値部分の最上位ビット（１０桁目）を取り出したビット列｛ｂn,10；ｎ＝０，…，７｝について、ｂn,10＝１の場合のみ対応する＋ａk,n （または−ａk,n ）を累積加算器で積算し、０の場合は演算しない。ｎ＝０，…，７について処理を終えた後、積算結果を１ビット左シフトし、絶対値部分の次のビット（９桁目）についても同様に＋ａk,n （または−ａk,n ）を累積加算器で積算する処理を繰り返す。以下、最下位ビットに至るまでこの処理を繰り返すことにより式（６）を求めることができる。
【００４１】
以上のアルゴリズムにおいて、ａk,n に付随する符号は各列ｎごとにｘn の符号によって（ｋによらずに）決定されるので、あらかじめマトリックスの第ｎ列の８個のデータを一組に、その反対符号のデータを一組にしてメモリに格納しておき、各列ごとにどちらかの符号をまとめて参照することによってｋ＝０，…，７の計算を並列に行なうことが可能となる。
【００４２】
次に、第２実施形態に係る乗算器の全体構成について、図２を参照しながら説明する。ｎ列のＭ行（有意データはｋ行）の行列より成るデータとしてのマトリックス１と、このマトリックス１の各成分についての累積加算を制御する演算制御手段１２と、乗算に必要なデータをテーブルとして格納し演算制御手段の制御信号により必要なデータを出力する読出し専用記憶手段としてのＲＯＭ１５と、ＲＯＭ１５と演算制御手段１２からの制御信号に基づいて乗算を行なうと共に並列に設けられた複数（ｎ個）の累積加算加算回路２１ａないし２１ｎを備える累積加算手段２０と、を備えている。上記演算制御手段１２は符号制御部として機能するカウンタ１３と、加算制御部として機能するセレクタ１４と、を備えており、カウンタ１３はアドレス指定手段１１としても機能している。なお、ｉｎ０〜ｉｎ７は行列データ蓄積手段１１の各列成分を蓄積する入力レジスタであり、Ａｃｃ０〜Ａｃｃ７は累積加算手段２０を構成する個々の累積加算回路２１ａ〜２１ｎの演算対象としての行成分であり、この第２実施形態においては、最上位ビットから演算処理を開始する。
【００４３】
上記構成を更に詳しく説明すると、まず、マトリックスを構成する「８×８」の各成分とその符号を反転したデータ（すなわち、２の補数で表現されたもの）との合計１２８個が、要求される精度に応じたビット幅により用意される。必要なビット幅は応用分野によって異なるが、例えばＭＰＥＧ１やＭＰＥＧ２等の場合であれば１６ビット程度の精度が要求される。これらのデータは読み出し専用メモリに格納することもできるが、本発明の場合アドレス参照によるメモリへのランダムアクセスは発生しないので、組合せ回路を用いたシーケンサ等を用いてもよい。上記ＲＯＭ１５は、これら種々の機能構成を総称してこの用語を用いるものとする。
【００４４】
このＲＯＭ１５は、図３に示すように、マトリックスの列番号（０〜７）を指定する信号と各列の符号を指定する信号Ｓ１（ＳＩＧＮ）によって対応する列の対応する符号のデータを８個（精度が１６ビットであれば１２８ビット分）ずつ同時に出力するように構成されているものとする。ＲＯＭ１５の出力に含まれる各データは、マトリックスの各行ごとに設けられ、各々が並列に動作する８個の累積加算回路２１ａないし２１ｎへ供給される。この累積加算回路２１ａないし２１ｎの各々の回路は、本質的には図４に示すように２入力１出力の加算器２４であり、各々の加算器２４が、ＲＯＭデータＤ１が供給される１個の入力レジスタ２３と、加算器２４の出力ポートに接続されると共に積算用に設けられた１個の出力レジスタ２５と、を備えると共に、加算器２４の出力ポートからの信号線が出力レジスタ２５に接続された後、２つに分岐してその一方が加算器２４の他方の入力ポートに接続されたものである。
【００４５】
加算器２４の各レジスタ２３，２５は、図５に示すように、クロック信号に同期して入力値を内部に設定するノーマルモードと、入力値に関係なく直前の値を保持するホールドモードと、内容を０にリセットするリセットモードと、入力を１ビット左シフトして内部にセットするシフトモードとを有しており、符号制御信号としての信号Ｓ２（ＳＨＩＦＴ）と加算制御信号としての信号Ｓ４（ＥＸＥＣ）との２種類の制御信号の組合せに応じてその動作モードが切り換えられている。
【００４６】
加算器のビット幅はＲＯＭデータが１６ビット、入力データが１２ビット（Ｍ＝１２）、入力８成分（Ｎ＝８）の場合、１６＋１１＋３ビット必要になるが、この第２実施形態においては後述の理由により更に１ビットを用意しておく。８個の入力データは通常は２の補数表現で与えられているが、これを符号−絶対値表現に変換して入力データレジスタに格納しておく。これは、例えば周知の方法であるが、入力データの最上位ビット（ＭＳＢ；１２桁目）が１の時に限り１〜１１桁目をビット反転し、その結果に１１ビット幅で１を加算して最上位ビットと再び連結すればよい。ＭＳＢが０の時は何も操作する必要はない。各データのＭＳＢは符号信号Ｓ１（ＳＩＧＮ）としてＲＯＭ１５へ供給され、それぞれ対応する列の出力データの符号が決定される。
【００４７】
また、入力データレジスタのうち絶対値部分（１〜１１桁目）の最上位（１１桁目）から取り出した８ビットのビット列（ビットスライス）｛ｂn ；ｎ＝０，…，７｝を８：１セレクタで選択し、このセレクタの出力を各累積加算器の入力側および出力側レジスタのＥＸＥＣ信号として用いて通常モード（ＥＸＥＣ＝１）とホールドモード（ＥＸＥＣ＝０）を切り換える。また入力データレジスタはシフターを備えており、ＳＨＩＦＴ＝１を受けると次のクロックに伴ってその絶対値部分が１ビット左シフトを行なう。
【００４８】
カウンタ（７ビット幅）の下位３ビットの出力信号Ｓ３は０〜７の値をとり、ＲＯＭ１５の列番号を指定する信号Ｓ１と、セレクタの選択信号Ｓ４の両方に用いられる。すなわち、入力レジスタの符号ビットカウンタの値とによりＲＯＭの出力データが決まり、これに同期して累積加算器の動作モードも定まる。またカウンタの下位３ビットが０００の時に限りＳＨＩＦＴ＝１を累積加算器および入力データレジスタに送出する。またカウンタの上位４ビットは入力データの何桁目までが処理済みであるかを判定するのに用いられる。
【００４９】
次に、図５を用いて、第２実施形態に係る乗算器における累積加算器の動作について説明する。演算処理に先立ってカウンタおよび累積加算器の入出力レジスタをリセットして、入力データは符号−絶対値表現に変換して予め入力レジスタに格納しておく。演算処理が開始されると、カウンタ値と符号に対応したＲＯＭデータが累積加算回路２１ａ〜２１ｎに順次供給され、またセレクタ１４はカウンタ１３の値に応じて、入力レジスタ２３ａ〜２３ｎの１１ビット目ｂ0 ，…，ｂ7 をこの順でＥＸＥＣ信号として加算器２４ａ〜２４ｎに送出する。例えば、カウンタ１３の下位３ビットが０００の時はマトリックスの第０列成分が、入力データの第０列成分の符号に対応して正または負符号で累積加算器の入力側レジスタに渡されることになる。このとき、もしもＥＸＥＣ＝１（入力データの第０列成分の絶対値の最上位ビットが１）であると累積加算回路２１のレジスタ２３はノーマルモードなので、次のクロックで累積加算回路２１の入力レジスタ２３にＲＯＭ１５からのデータが符号拡張してセットされ、出力ポートにはこの値と出力レジスタ２５の内容を加算した値が現れる。このとき、ＥＸＥＣ＝１であればこの値はその次のクロックで出力レジスタ２５にセットされる。一方、ＥＸＥＣ＝０であれば累積加算回路２１のレジスタ２３，２５はどちらもホールド状態となり、ＲＯＭ１５からのデータが入力レジスタ２３にセットされず、加算器２４の出力ポートの値も出力レジスタ２５にセットされないので、図６に示すように、加算器２４は以前の状態を保ったままとなりスイッチング動作をしないことになる。
【００５０】
上の動作を８回行なってカウンタの下位３ビットが１１１を示すとＳＨＩＦＴ＝１が累積加算器に送られ、次のクロックに伴って出力ポートのデータが１ビット左シフトして（２を乗算することに相当）出力レジスタ２５にセットされる。このとき、入力レジスタ２３の絶対値部分も１ビット左シフトされて入力データの１０桁目が入力レジスタ２３の１１桁目に入る。以降は上の手順を絶対値部分の全ての桁について（１１回）繰り返せばよい。出力ポートがシフトされるごとに結果に２が乗算されるので、最終的に１１桁目の部分和には２11が、１０桁目の部分和には２10が乗じられ、以下同様に第ｉ桁目の計算結果には２i が乗じられたものの総和が求められる。カウンタ１３が「１０１０１１１」を示したその次のクロックで全ての桁に関する処理が終了しているので、累積加算器の出力レジスタから必要なビット幅のデータを取り出せば積和演算の結果が得られる。ここで、各部分和に対する２の乗数が一つ多くなっているので、これを考慮してあらかじめ出力レジスタのビット幅を予め１ビット分増やしておいて、計算結果を取り出す時に出力の最下位ビットを無視することで正しい結果を得ることができる。
【００５１】
上述の構成により上述のように動作する第２実施形態に係る行列ベクトル乗算器の効果について説明する。まず、通常モードではクロックに伴って入力レジスタ２３および出力レジスタ２５の内容が更新されると、加算器２４の内部におけるスイッチング動作により積算が行なわれるが、ホールドモードでは加算器２４の２つの入力ポートはともにクロック以前の値に固定されているため、スイッチング動作が行なわれず、余分な電力消費が抑えられる。
【００５２】
したがって、２進表現の入力データに含まれる０の個数が多いほど電力消費が少なくなるが、特に動き補償を用いた動画像圧縮符号化・復号化処理における差分画像データではデータ分布は０の周囲に集中しているため、符号−絶対値表現を用いた場合にその上位ビットが０である確率が高く、このような性質を持つデータ列に適用すると通常のＤＡ法等に比較して消費電力を大幅に削減できる。また、マトリックスの成分を格納しているＲＯＭはランダムアクセスされることがなく、一定の順序でデータを順次送出するだけなので非常に構造が単純であるという効果もある。
【００５３】
次に、本発明の第３実施形態に係る行列ベクトル乗算器について、図７および図８を用いて説明する。本発明の第３実施形態に係る乗算器は、本質的に第２実施形態と同様のアルゴリズムを用い、その加算の順序を反対に（下位の桁から）行なうように変更したものである。以下、Ｎ＝８、Ｍ＝１２の場合について、その構成方法、機能および効果を説明する。
【００５４】
本発明の第３実施形態による乗算器の基本構成を図７に示す。図７において、第２実施形態と同様な構成、つまりカウンタ１３およびセレクタ１４を有する演算制御手段１２、ＲＯＭ１５、累積加算手段２０が設けられている。また、行列データ蓄積手段１１も第２実施形態とほぼ同様に構成されているが、絶対値部分の最上位ビットではなく最下位ビットについてビットスライスを取り出してから８：１セレクタにより選択してＥＸＥＣ信号として送出する。また累積加算器の入力側レジスタはＲＯＭからのデータを取得するにあたり、１１ビット左シフトした上で符号拡張して内部にセットし（あらかじめ２11を乗ずることに相当）、下位１１ビットは常に０とする。また、累積加算器の出力側レジスタは、シフトモードのとき、その入力を１ビット右シフトして内部にセットしている。
【００５５】
このような第３実施形態に係る乗算器の機能も第２実施形態と同様である。すなわち、演算処理に先立ってカウンタおよび累積加算器の入出力側レジスタをリセットし、入力データは符号−絶対値表現で入力レジスタに格納しておく。処理が開始されると、カウンタの下位３ビットと符号に対応したＲＯＭデータが累積加算器に順次出力される。またセレクタは入力データレジスタの最下位ビットから取り出されたビットスライスｂ0 ，…，ｂ7 をカウンタの下位３ビットの示す値に応じて選択してこの順でＥＸＥＣ信号として累積加算器に送る。例えばカウンタの下位３ビットが０１０の時はマトリックスの第２列成分（０１０に対応）が、入力データの第２成分の符号に対応した符号で累積加算器の入力側レジスタに供給されることになる。この時ＥＸＥＣ＝１（入力データの第２成分の絶対値の最下位ビットが１）で累積加算回路２１のレジスタ２３，２５がノーマルモードであるならば、次のクロックで入力レジスタ２３の１２ビット目以上にＲＯＭ１５からのデータが符号拡張してセットされ、第２の実施形態の場合と同様に加算器２４の出力ポートには、この値と出力側レジスタの内容を加算した値が現れる。一方、ＥＸＥＣ＝０であればこれも第２実施形態の場合と同様に累積加算回路のレジスタ２３，２５は、図５のように何れもホールド状態となり、ＲＯＭからのデータが入力側のレジスタ２３にセットされず、出力ポートの値も出力側レジスタ２５にセットされないので、加算器２４は以前の状態を保ったままスイッチング動作を行なうことはない。
【００５６】
以下、第２実施形態と同様の動作を８回行なって、カウンタの下位３ビットが１１１を示すとＳＨＩＦＴ＝１が累積加算器に送られ、次のクロックに伴って出力ポートのデータが１ビット右シフトして（１／２を乗算することに相当）出力側レジスタ２５にセットされる。このとき、入力レジスタ２３の絶対値部分も１ビット右シフトされ、入力データの２桁目が入力データレジスタの１桁目に入り入力データの１桁目に関する処理が終了する。これ以降は、上記の手順を絶対値部分の全ての桁につき１１回繰り返せばよい。入力レジスタにあらかじめ２11を乗じたデータが供給されているが、出力ポートが右シフトされるごとにその結果に１／２が乗算されるので、最終的に１桁目の部分和には２0 が、２桁目の部分和には２が、以下同様に第ｉ桁目の計算結果には２i-1 が乗じられたものの総和が求められる。各桁ともにカウンタが１０１０１１１を示したその次のクロックで全ての桁に関する処理が終了しているので、累積加算器の出力レジスタから必要なビット幅のデータを取り出せば積和演算の結果が得られる。
【００５７】
以上のような構成・動作を有する第３実施形態に係る行列ベクトル乗算器の効果について説明する。まず、ＲＯＭからのデータを入力レジスタに供給する際に、ＲＯＭデータのビット幅と累積加算器のビット幅の差に相当する部分は符号拡張を行なわなければならず、図８に示すように、ＲＯＭから渡されるデータが負であるのならばＲＯＭデータの最上位から入力側レジスタの最上位までのビット（Ｍ＝１２、Ｎ＝８ならば１４ビット）を全て１にセットし、正ならば０にしてレジスタにセットする必要がある。差分画像のデータは０を中心に正負の両側にほぼ一様に分布しているため、ＲＯＭから渡されるデータの正負の比率は、ほぼ１：１で順序の予測ができず、この部分のスイッング確率が非常に大きくなる可能性があるが、あらかじめ１１ビットシフトして代入して下位１１ビットを常に０にしておくと、符号拡張に伴う上位ビットのスイッチング回数を少なくすることができ、さらなる低消費電力化が可能となる。
【００５８】
最後に、本発明の第４実施形態に係る行列ベクトル乗算器の構成，機能および効果について、図９を参照しながら説明する。この第４実施形態に係る乗算器も、第１の所定数であるｎ列で８、第２の所定数である行数も８であるがビット数Ｍが１２の場合について説明する。
【００５９】
まず、第４実施形態に係る行列ベクトル乗算器の構成を図９に示す。この第４実施形態に係る乗算器は、第２，第３実施形態に係る乗算器と同様な構成のＲＯＭ１５と、累積加算手段２０と、カウンタ１３が設けられている。また、行列データ蓄積手段１１も第１ないし第３実施形態とほぼ同様の構成とするが、絶対値部分の最上位ビットだけではなく任意のビットについてビットスライスを取り出すことができ、信号Ｓ５により１１：１の選択比率の第２のセレクタ３４がカウンタの上位４ビットに応じてどの桁を取り出すかを制御するものである。カウンタ１３の上位４ビットと蓄積手段１１との桁の対応は任意でよいが、例えば００００の時が１１桁目、１０１０の時が、１桁目のように対応づけておくと、構成をより簡単にすることができる。
【００６０】
上記構成に基づく第４実施形態に係る乗算器の機能動作について説明する。第２実施形態に係る乗算器と同様に、演算処理に先立ってカウンタ１３および累積加算回路２１の入出力側のレジスタ２３，２５をリセットし、入力データは符号−絶対値表現で入力側のレジスタ２３に格納しておく。演算処理が開始されるとカウンタ１３の下位３ビットと符号に対応したＲＯＭデータが累積加算回路２１の加算器２４に順次渡される。また、第２のセレクタ３４は、行列データ蓄積手段１１のある桁（カウンタの上位４ビットで指定）から取り出されたビットスライスｂ0 ，…，ｂ7 を、カウンタ１３の下位３ビットの示す値に応じてセレクタ１４により選択してこの順でＥＸＥＣ信号Ｓ４として累積加算回路２１に送る。例えば、カウンタ１３が００１１１０１の時は蓄積手段１１に格納されているマトリックスの第５列成分（１０１に対応）が、入力データの第５成分の符号に対応して正または負符号で累積加算回路２１の入力側レジスタ２３に渡され、入力レジスタの８桁目（００１１に対応）から取り出されたビットスライスの第５成分が累積加算器へＥＸＥＣ信号として渡されることになる。以下第２実施形態と同様の手順で累積加算を行なう。
【００６１】
第２実施形態に係る乗算器の場合、ある桁の加算を終了するごとに入力レジスタの１ビット左シフトを行なっていたが、ここではカウンタの上位４ビットに応じてビットスライスを取り出す桁を切り換えるためのハードウェアとして第２のセレクタ３４を追加するだけで、左シフトのための機構を省略し、さらにシフトに伴って生じるレジスタの更新を抑制するので、さらなる低消費電力化が可能となる。
【００６２】
【発明の効果】
以上、詳細に説明したように、本発明に係る行列ベクトル乗算器によれば、入力された行列データのビットが０の時は加算を行なわないので、消費電力を大幅に低減することが可能となると共に、各行に関する積算を並列接続された複数の累積加算回路により並列に演算処理することができるので、演算処理の高速化が可能となる。
【００６３】
さらに、並列に設けられた累積加算回路の入出力レジスタのスイッチング動作の回数を削減することもできるので、この点においても消費電力の低減が可能となるばかりでなく、読出し専用記憶手段へのランダムアクセスが発生しないことになるので、読出し専用記憶手段（ＲＯＭ）の構造を簡単化するこもできる。
【００６４】
また、符号拡張の際のスイッチングの回数も削減することができ、消費電力の低減化が期待でき、また、行列データ蓄積手段のシフト機能が不要となるので、蓄積手段の構造を簡略化でき、スイッチングの回数も削減される。さらに、カウンタを共用することでハードウェア量の削減を図ることもできる。
【図面の簡単な説明】
【図１】本発明の基本概念としての第１実施形態に係る行列ベクトル乗算器の構成を示すブロック図。
【図２】本発明の第２実施形態に係る行列ベクトル乗算器の構成を示すブロック図。
【図３】第２ないし第４実施形態の乗算器において共通に用いられるＲＯＭの機能を表すテーブルと、第５列の＋符号を指定された場合とを示す説明図。
【図４】本発明に係る行列ベクトル乗算器において共通して用いられる累積加算回路を示すブロック図。
【図５】図４における入出力レジスタ２３，２５にそれぞれ入力される制御信号に対するモード割り当てテーブルを示す説明図。
【図６】第２実施形態に係る乗算器における累積加算回路の動作状態の一例を説明するため入力データ絶対値部分の最上位ビットのビットスライスが（０１１０１１００）、次の桁のビットスライスが（０１１０．．．．）の場合を示す説明図。
【図７】本発明の第３実施形態に係る行列ベクトル乗算器の構成を示すブロック図。
【図８】本発明に係る乗算器の（ａ）第２実施形態における累積加算回路の入力側レジスタへのデータのセット方法、（ｂ）第３実施形態における累積加算回路の入力側レジスタへのデータのセット方法をそれぞれ示す説明図。
【図９】本発明の第４実施形態に係る行列ベクトル乗算器の構成を示すブロック図。
【図１０】ＤＡ法を用いた従来の行列ベクトル乗算器の構成を示すブロック図。
【図１１】従来の行列ベクトル乗算器のＲＯＭに格納されたテーブルを示す説明図。
【図１２】従来の乗算器における計算アルゴリズムを示す説明図。
【符号の説明】
１０  行列ベクトル乗算器
１１  行列データ蓄積手段
１２  演算制御手段
１３  符号制御部（アドレス指定カウンタ）
１４  加算制御部（セレクタ）
１５  読出し専用記憶手段（ＲＯＭ）
２０  累積加算手段
２１（ａ〜ｎ）  累積加算回路
２３（ａ〜ｎ）  入力蓄積部（入力レジスタ―ＡＲＥＧ―）
２５（ａ〜ｎ）  出力蓄積部（出力レジスタ―ＢＲＥＧ―）
３４  符号制御部（第２のセレクタ）
【図１】
0003895031.tif 000009
【図２】
0003895031.tif 000010
【図３】
0003895031.tif 000011
【図４】
0003895031.tif 000012
【図５】
0003895031.tif 000013
【図６】
0003895031.tif 000014
【図７】
0003895031.tif 000015
【図８】
0003895031.tif 000016
【図９】
0003895031.tif 000017
【図１０】
0003895031.tif 000018
【図１１】
0003895031.tif 000019
【図１２】
0003895031.tif 000020