JPH07191966A

JPH07191966A - 行列掛け算回路

Info

Publication number: JPH07191966A
Application number: JP4330734A
Authority: JP
Inventors: Jinn-Nan Kao; ナンカオジン; Jinn-Shyan Wang; シャンワンジン
Original assignee: Industrial Technology Research Institute ITRI
Current assignee: Industrial Technology Research Institute ITRI
Priority date: 1992-02-13
Filing date: 1992-12-10
Publication date: 1995-07-28
Anticipated expiration: 2014-07-05
Also published as: JP2916056B2; NL9200899A; US5204830A; DE4217011A1; DE4217011C2

Abstract

(57)【要約】【目的】効率的に３行列の積を取ることのできる回路お
よびアルゴリズムを提供する。【構成】第１のステ−ジ１２は、第１の行列と第２の行
列の掛け算を行い中間行列を生成し、第２のステ−ジは
第３の行列と中間行列の積を求め最終的な行列を計算す
る。各ステ−ジは、当該ステ−ジが生成する行列の要素
を生成するために、ット掛け算処理部のパイプライン１
６、１８を複数有している。各パイプライン１６、１８
は、同ステ−ジの他のパイプラインと並列に動作し、そ
れぞれ、当該ステ−ジが生成する行列の各列を生成す
る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、行列の掛け算を行う回
路およびアルゴリズムに関するものである。本発明に係
る回路およびアルゴリズムは、特に、データ行列の離散
コサイン変換（以下、「ＤＣＴ」と記す）の実現に適し
ている。

【０００２】

【従来の技術】２次元ＤＣＴは、遠隔地間の通信や記憶
のための映像信号の圧縮にとって重要である。

【０００３】Ｎ×Ｎの入力データ行列の２次元ＤＣＴ
は、式１ａで定義することができる。

【０００４】なお、以下の記載では、行列は大文字の英
字で示す。また、行列の要素は小文字の英字で示す。

【０００５】

【数５】

【０００６】また、この逆変換は、式１ｂで同様に定義
することができる。

【０００７】

【数６】

【０００８】Ｘ（ｎ₁，ｎ₂）は入力データ行列を示し、
Ｚ（ｋ１，ｋ２）は変換係数の行列を示している。

【０００９】ここで、数５は、行列形式で、Ｚ＝ＣＸＣ^ − 式２と各ことができる。ここで、Ｃはコサイン係数行列を示
し、Ｃ^はＣの転置行列を表している。

【００１０】詳細な表現によれば、式２は式３に書き直
すことができる。

【００１１】

【数７】

【００１２】このように、互いに掛け合わされている３
つのＮ×Ｎ行列がある。ここで、行列Ｙを、Ｙ＝ＸＣ
^、または、式４で定義する。

【００１３】

【数８】

【００１４】ここのようにすると、行列Ｚは、式５のよ
うに書くことができる。

【００１５】

【数９】

【００１６】２×２の場合を例にとると、式４は、式６
のように表される。

【００１７】

【数１０】

【００１８】また、式５は、式７のように表される。

【００１９】

【数１１】

【００２０】従来、ＤＣＴの実施に関して種々の提案が
成されている。このような提案は、たとえば、Discrete
Cosine Transform(N.Ahmed,T.Matarajan and K.Rao,19
74 IEEE.Trans.on Comp.90)や、VLSI Implementation of
16×16 Discrete cosine transform(M.Sung,T.Chen an
d A.Gottlieb,IEEE Trans. on Cir.and Sys.,Apr.,198
9,610)や、Fast Algorithm and Implementation of a 2-
D Discrete Cosine Transform(N chou and S Lee,IEEE
Trans. on Cir.and Sys.,Mar.,1991,297)や、A Fast Rec
ursive Algorithm for Computing the Discrete Cosine
Transform(H.Hou、IEEE Trans. on Cir.and Sys.,Oct.,
1987,1455)等に記載されている。

【００２１】

【発明が解決しようとする課題】しかし、これら従来の
技術技法には、次のような問題点がある。

【００２２】１．行−列分解法（ｒｏｗ−ｃｏｌｕｍｎ
ｄｅｃｏｍｐｏｓｉｔｉｏｎ）を用いた場合には、解
を得るために転置メモリが必要となり、パイプラインデ
ータ処理が、とても困難になる。

【００２３】２．２次元ＤＣＴを直接的に実施しようと
すると、実現のために必要となるハ−ドウェアのコスト
が、その利益を超えて大きくなる。

【００２４】３．ほとんど解法は、モジュ−ル化されて
いないために、低速で非効率的にしか実施できない。

【００２５】そこで、本発明の特徴の１つは、これら従
来の技術の問題点を解決することのできるアルゴリズム
および回路を提供する点である。

【００２６】さて、先に示したように、ＤＣＴを行うた
めには、３つの行列の積をとることが必要である。そこ
で、本発明は、効率的に３行列の積を取ることのできる
回路およびアルゴリズムを提供することを目的とする。
ここで、本発明に係る回路は、ＤＣＴに必要な３行列の
積算に適用することができる。

【００２７】

【課題を解決するための手段】前記目的達成のために、
本発明は、要素ｘ_ij ｉ＝１，．．，Ｉ，ｊ＝
１，．．，Ｊよりなる第１の行列Ｘと、要素ｃ^_jk Ｊ
＝１，．．，Ｊ，ｋ＝１，．．，Ｋより成る行列Ｃ^の
掛け算を行い、要素ｙｉｋよりなる中間行列Ｙを出力す
る第１の掛け算ステ−ジと、要素ｃ_li ｌ＝１，．．，
Ｌ，ｉ＝１，．．，Ｉよりなる第１の行列Ｃと、中間行
列Ｙの掛け算を行う第２の掛け算ステ−ジを有する行列
掛け算回路およびアルゴリズムを提供する。ここで、た
とえば、行列Ｘはデータ行列であり、行列Ｃ^はコサイ
ン係数行列の転置行列、行列Ｃはコサイン係数行列とし
てもよい。

【００２８】

【作用】本発明の一実施態様によれば、この第１のステ
−ジは、複数の処理部パイプラインと、レジスタパイプ
ラインを有している。各処理部パイプラインは、たとえ
ば、ビット掛け算処理部の縦並びの列である。ｘ₁₁，ｘ
₁₂，．．，ｘ_1J，ｘ₂₁，ｘ₂₂，．．，ｘ_2J，．．，ｘ_IJ
の順序の行列Ｘの要素より成る第１の入力シ−ケンスは
レジスタパイプラインに入力される。レジスタパイプラ
インにおいて、行列要素は、レジスタからレジスタへと
順次シフトされる。レジスタパイプラインは、連続する
サイクルにおいて、前記第１のシ−ケンスの要素の第ｍ
ビットを、第１ステ−ジの各パイプライン回路のｍ番目
の処理部に出力する。ここで、ｍは、１から要素ｘ_ijの
ビットの数までの間のインデックスである。各処理部パ
イプラインは、また、それぞれ、行列Ｃ^の特定の列ｋ
の要素のＩ回の繰り返しを第２のシ−ケンスとして受け
取る。ここでＩは、行列Ｘの行数と同じ数である。言い
替えるならば、各処理部パイプラインは、行列Ｃ^の１
列の要素を、行列Ｘの各行につき１度づつ繰り返し受け
取る。これらの行列要素は、処理部パイプラインにそっ
て処理部から処理部へと送られる。各シ−ケンスよりの
行列要素は、１サイクル毎に入力される。各処理部パイ
プラインは、特定のｋの値について、積ｘ_ijｃ_jkをシ−
ケンシャルに計算する。したがい、処理部パイプライン
の数は、Ｋに等しく、インデックスｋの各値について、
１つの処理部パイプラインがある。すなわち、行列Ｃ^
の要素の各列に対して、１つの処理部パイプラインがあ
る。

【００２９】第１ステ−ジの各処理部パイプライン最後
には、パイプラインの最後から２番目の処理部から出力
された全てのｉについての積ｘ_ijｃ_jkを累積するアキュ
ムレ−タを備えた処理部が設けられている。このような
累積機構は、中間行列Ｙの要素を生じる。このようにし
て、各パイプラインの最後の処理部のアキュムレ−タ
は、行列Ｃ^の特定の１列の要素と行列Ｘの特定の１行
の要素の引数ペアのグル−プから産じた積結果を互いに
加算する。

【００３０】第２のステ−ジも、また、複数の処理部パ
イプラインと、１つのレジスタパイプラインを有してい
る。各処理部パイプラインは、ビット掛け算処理部の縦
並びの列である。ｃ₁₁，ｃ₂₁，．．，ｃ_L1，ｃ₂₁，
ｃ₂₂，．．，ｃ_L2，．．，ｃ_LIの順序の行列Ｃの要素ｃ
_liより成る第１の入力シ−ケンスはレジスタパイプライ
ンに入力される。レジスタパイプラインにおいて、行列
要素は、レジスタからレジスタへと順次シフトされる。
レジスタパイプラインは、連続するサイクルにおいて、
前記第１のシ−ケンスの要素の第ｐビットを、第１ステ
−ジの各パイプライン回路のｐ番目の処理部に出力す
る。ここで、ｐは、１から要素ｃ_liのビットの数までの
間のインデックスである。各処理部パイプラインは、ま
た、それぞれ、行列Ｙの特定の列ｋの要素ｙ_ikのＬ回の
繰り返しを第２のシ−ケンスとして受け取る。ここでＬ
は、行列Ｃの行数と同じ数である。言い替えるならば、
第２ステ−ジの各処理部パイプラインは、行列Ｙの１列
の要素を、行列Ｃの各行につき１度づつ繰り返し受け取
る。なお、各シ−ケンスよりの要素は、１クッロク毎に
入力される。

【００３１】各処理部パイプラインは、特定のｋの値に
ついて、積ｃ_liｙ_ikをシ−ケンシャルに計算する。した
がい、処理部パイプラインの数は、Ｋに等しく、インデ
ックスｋの各値について、１つの処理部パイプラインが
ある。

【００３２】第２ステ−ジの各処理部パイプラインより
の出力先は、スイッチングアレイと、第２のアキュムレ
−タが積行列Ｚの要素を出力するように選択的に積結果
ｃ_liｙ_ikを累積するアキュムレ−タである。第２のアキ
ュムレ−タは、式８を満足するように、積を選択的に累
積する。

【００３３】

【数１２】

【００３４】

【実施例】以下、本発明の一実施例を説明する。

【００３５】図１、図２に、２×２ＤＣＴをサポ−トす
ることのできる行列掛け算回路１０を示す。図１は、行
列掛け算器の前半部分（後述する第１ステ−ジ）、図２
は後半部分（後述する第２ステ−ジ以降）を示してい
る。行列掛け算回路１０は、１２と１４の２つのステ−
ジを有している。ＤＣＴは、Ｚ＝ＣＸＣ^により実施す
ることができる。ここで、Ｃは変換係数の行列であり、
Ｃ^は行列Ｃの転置行列、Ｘはデータ行列である。第１
ステ−ジ１２は、ＸＣ^の掛け算を行い、中間行列Ｙを
生成する。第２ステ−ジは、ＣＹの掛け算を実行し、行
列Ｚを生成する。第１ステ−ジ１２は、レジスタ列２０
と２つの処理部列１６、１８を有している。２つの処理
部列１６と１８は、同じ構成を有している。処理部列１
６、１８は、複数の（本実施例では２つ）の処理部ＰＥ
２、（１６−２、１６−３、１８−２、１８−３）に接
続した処理部ＰＥ１（１６−１、１８−１を有してい
る。レジスタ列２０に供給されるデータ要素の各ビット
に対して、１つの処理部ＰＥ１もしくはＰＥ２が必要と
なる。したがい、１列あたりの処理部ＰＥ１とＰＥ２の
総数は、レジスタ列２０に入力されるデータ要素のビッ
ト数と等しくなる。なお、図１においては、処理部列１
６、１８に、２つのＰＥ２を設けているが、回路１０に
任意の数のＰＥ２を追加して調節してもよい。さて、処
理部列１６、１８の最後のＰＥ２には、処理部ＰＥ３
（１６−４、１８−４）が接続されている。第１の処理
部列１６は、行列Ｘの要素に、行列Ｃ^の第１列の要素
を乗じる。第２の処理部列１８は、行列Ｘに行列Ｃ^の
第２列の要素を乗じる。

【００３６】処理部列１６の動作をレジスタ列に関連さ
せて説明する。第２の処理部列１８は、第１の処理部と
同じであるので、第１の処理部列１６についての説明
は、量列についてあてはまる。ｘ₁₁，ｘ₁₂，ｘ₂₁，ｘ₂₂
の要素を持つ２×２の行列が、１度に１要素ずつ、ライ
ン２０−１を介して、レジスタ欠２０に入力される。同
様に、行列Ｃ^のｃ^₁₁、ｃ^₂₁の要素よりなる第１列
が、１度に１要素ずつ、ライン３４−１を介して、処理
部列１６の最初の処理部ＰＥ１（１６−１）に入力され
る。行列の掛け算において、この行列Ｃ^の第１列は、
行列Ｘの全ての行について繰り返されなければならな
い。たとえば、本実施例では、Ｃ^の第１列は、ライン
３４−１より２度入力される。

【００３７】ライン２０−１よりの第１番目の入力は、
行列Ｘよりのｘ₁₁である。また、ライン３４−１よりの
最初の入力は行列Ｃ^よりの要素ｃ^₁₁である。以下、ど
のように、処理部列がｘ₁₁ｃ^₁₁を計算するかを説明す
る。ＰＥ１（１６−１）のｃ^１１の処理は次のように
行われる。入力ライン２０−１の第１ビットに接続した
タップラインは、処理部列１６−１のＰＥ１に要素ｘ₁₁
の第１ビットを供給する。すなわち、ライン３８−１よ
り、マルチプレクサ３６の選択制御入力に第１ビットが
供給される。このマルチプレクサ３６−１は、データ入
力として、ライン３４−１より要素ｃ^１１を受け取
る。入力された第１ビットがセットされていれば（論理
１に等しければ）ライン３４−１上のｃ^₁₁が選択され
る。第１ビットがクリアさていれば（論理ゼロに等しけ
れば）、論理ゼロが選択される。マルチプレクサの出力
は、ライン２８−１を介して、クロックの立ち下がりで
記憶を行うレジスタ２４−１に与えられる。この値は、
第１の入力要素ｘ₁₁とｃ^₁₁の積の結果の一部分である
部分結果を構成する。行列Ｃ^の第１列の最初の入力で
あるｃ^₁₁は、ライン３２−２を介して、処理部列１６
のＰＥ１のレジスタ３０−１に供給され、記憶される。
これで、ｘ₁₁とｃ^₁₁のＰＥ１（１６−１）による処理
は終了する。

【００３８】また、前記クロックの立ち下がりエッジ
で、行列Ｘの最初の入力要素がｘ₁₁が、ライン２０−１
を介して、レジスタ列２０の最初のレジスタ２０−１に
供給され記憶される。次のクロックでは、ｘ₁₁の第２ビ
ットの値とｃ^₁₁がＰＥ２（１６−２）で処理される。
また、この間に、次の組であるｃ^₂₁とｘ₁₂が、ＰＥ１
（１６−１）とレジスタ列でＡよりされる。

【００３９】要素ｘ₁₁とｃ^₁₁のＰＥ２での処理を説明
する。タップライン３８−２よりｘ₁ ₁の第２ビットが、
ＰＥ２（１６−２）のマルチプレクサ３６−２の選択制
御入力に供給される。また、この間に、第１列の要素ｃ
^₁₁が、ライン３４−２を介して、ＰＥ２（１６−２）
のマルチプレクサ３６−２のデータ入力に供給される。
もし、ライン３８−２より供給されたｘ₁₁の第２ビット
がセットされていれば、マルチプレクサ３６−２によっ
て、ｃ^₁₁が選択される。もし、第２ビットがクリアさ
れていれば、論理ゼロが選択される。マルチプレクサ３
６−２の出力は、ライン２８−２を介して、加算レジス
タ２４−２に供給される。加算レジスタ２４−２は、ラ
イン２６−１を介して、ＰＥ１のレジスタ２４−１に記
憶されている部分結果をも受け取る。そして、これらの
２つの値は、加算レジスタ２４−２中において、新たな
部分結果を計算するために、加算され、記憶される。な
お、このＰＥ２（１６−２）のマルチプレクサのデータ
は、データｘ₁₁の第２ビットによる掛け算を示してい
る。このため、マルチプレクサ３６−２の出力は、レジ
スタ２４−１の部分結果との加算に先立ち、レジスタ２
４−１の部分結果に対して左（上位）へ１ビットシフト
されなければならない。さて、第２クロックの立ち下が
りで、新たな部分結果が加算レジスタ２４−２に記憶さ
れる。また、ｘ₁₁が、ライン２０−２を介して、レジス
タ列２０のレジスタ２１−２に入力され記憶される。同
様に、要素ｃ^₁₁が、ライン３２−２を介して、ＰＥ２
（１６−２）のレジスタ３０−２に入力され記憶され
る。また、同様に、第２の入力引数組（ｘ₁₂，ｃ^₂₁）
と、その第１の部分結果は、それぞれ、レジスタ列２０
のレジスタ２１−１と、レジスタ３０−１、２４−１に
記憶される。

【００４０】次のクロックでは、３番目の引数組
（ｘ₂₁，ｃ^₁₁）が、それぞれ、ライン２０−１と３４
−１を介して、ＰＥ１（１６−１）とレジスタ列２０
に、処理のために入力される。前述した第１の引数組
（ｘ₁₁，ｃ^₁₁）と同じく、前記第２の引数組（ｘ₁₂，
ｃ^₂₁）のデータフロ−は、ＰＥ２（１６−２）とレジ
スタ列２０中で継続する。第１の引数組の処理は、レジ
スタ列２０と次のＰＥ２（１６−３）中に継続する。タ
ップライン３８−３は、入力ｘ₁₁の第３ビットを、第３
段階のＰＥ”（１６−３）のマルチプレクサ３６−３の
選択制御入力に供給する。同様に、ライン３４−３を介
して、要素ｃ^₁₁がマルチプレクサ３６−３のデータ入
力に与えられる。ｘ₁₁の第３ビットがセットされていれ
ば、列入力ｃ^₁₁が出力として選択される。もし、第３
ビットがクリアされていれば、論理ゼロが出力として選
択される。この出力は、ライン２８−３を介して、加算
レジスタ２４−３に与えられ、左（上位）へ２ビットシ
フトされ、ライン２６−２を介して加算レジスタ２４−
２から供給された部分結果と加算される。この結果は、
加算レジスタ２４−３に、第３クロックの立ち下がりエ
ッジで記憶される。

【００４１】行列Ｘの要素は３ビット以上有している場
合には、さらなるＰＥ２を、ＰＥ２（１６−３）の下
に、以上に説明してきたように接続し、追加する。ま
た、同様に、追加した各ＰＥ２について、レジスタをレ
ジスタ列２０に、先に示したように追加する。この場合
の、ｍ段目（１≦ｍ≦行列Ｘの要素のビット数）のＰＥ
２の動作を簡単に説明する。行列Ｘの要素の第ｍビット
は、レジスタ列のｍ−１番目のレジスタより、ｍ段目の
ＰＥ２のマルチプレクサに、選択制御入力として供給さ
れる。もし、このビットがセットされていれば、ｍ−１
番目のＰＥ２のレジスタより取りだした、対応するＣ^
の入力が選択される。もし、このビットがクリアされて
いれば、論理ゼロが選択される。このマルチプレクサよ
りの出力は、加算レジスタに与えられ、新たな部分結果
を得るために、左（上位）へｍ−１ビットシフトされ、
ｍ−１段目の部分結果と加算される。

【００４２】処理部列１６の処理を続け、最初の組（ｘ
₁₁，ｃ^₁₁）の掛け算の最終結果が加算レジスタ２４−
３から、第４クロックで出力される。第の行列Ｘの１つ
の行の要素と、第２の行列Ｃ^の一つの列の積の結果の
和は、中間行列Ｙ＝ＸＣ^の一つの要素となる。たとえ
ば、ｙ₁₁＝ｘ₁₁ｃ^₁₁＋ｘ₁₂ｃ^₂₁であり、ｙ₂₁＝ｘ₂₁ｃ
^₁₁＋ｘ₂₂ｃ^₂₁である。

【００４３】入力引数組のシ−ケンスを考察すると、Ｐ
Ｅ２（１６−３）における第１と第２の結果、すなわち
ｘ₁₁ｃ^₁₁，ｘ₁₂ｃ^₂₁を加算すればｙ₁₁を生成でき、第
３と第４の結果を加算すればｙ₂₁を生成できることが分
かる。そこで、このために、処理部１６の最後にＰＥ３
（１６−４）を設けている。

【００４４】第４のクロックにおいて、ライン２６−３
を介して、積結果ｘ₁₁ｃ^₁₁が、アキュムレ−タ４０に
供給される。アキュムレ−タ４０は、第５クロックにお
いて、第１の積結果ｘ₁₁ｃ^₁₁を、再度アキュムレ−タ
に入力するためにのフィ−ドバックパス４６を有してい
る。第５クロックにおいて、アキュムレ−タ４０は、ラ
イン２６−３を介して、第２番目の入力として、第２の
積結果ｘ₁₂ｃ^₂₁を受け取る。これは、第１の積結果に
対して１計算段階遅れている第２の積結果が追い着くよ
うにするためである。この２つの積結果は加算され、第
５クロックの立ち下がりエッジでアキュムレ−タ４０に
記憶される。

【００４５】第５クロックにおいて、第３の積結果ｘ₂₁
ｃ^₁₁が、ライン２６−３を介してアキュムレ−タ４０
に入力される。そこで、この時点までにアキュムレ−タ
４０の内容（ｙ₁₁）は、移動されていなければならな
い。このため、ｙ₁₁は、アキュムレ−タ４０よりライン
４２を介してレジスタ４４に出力される。要素ｙ₁₁は、
要素ｙ₂₁が計算されレジスタ４４に入力される２クロッ
ク後までの期間、レジスタ４４より出力される。

【００４６】このように、処理部列１６は、行列Ｙの第
１列を構成する要素ｙ₁₁，ｙ₂₁を生成することができ
る。また、同様な処理により、処理部列１８は、行列Ｃ
^の第２列を受取り、行列Ｙの第２列の要素ｙ₁₂とｙ₂₂
を生成する。処理部列１６、１８は同時に動作する。ま
た、行列Ｙの各列について、完全な並列計算を行うに
は、行列計算回路１０に、行列Ｙの列毎に、１つの処理
部列を設けなければならないが、図１、２の行列掛け算
回路１０は、２列を有する行列Ｙについて、このような
要求を見たしている。例をあげて説明したように、この
ような回路は、２×２のＤＣＴの計算に用いることがで
きる。

【００４７】さて、第２ステ−ジ１４も、２つの処理部
列２２、２４と、レジスタ列２６を有している。処理部
列１６と１８のように、処理部列２２と２４は互いに同
じものである。処理部列２２は、２つの処理部ＰＥ２
（２２−２、２２−３）が後に続く、処理部ＰＥ１（２
２−１）を有している。同様に、処理部列２４は、２つ
の処理部ＰＥ２（２４−２、２４−３）が後に続く、処
理部ＰＥ１（２４−１）を有している。したがい、処理
部列２２についての説明は、処理部列２４についても同
様にあてはまる。レジスタ列２６は、たとえば、第３の
行列Ｃの要素を、ｃ₁₁，ｃ₂₁，ｃ₁₂，ｃ₂₂の順に、ライ
ン２６−１を介して受け取る。処理部列２２は、行列Ｙ
の第１列の要素を、ｙ₁₁，ｙ₁₁，ｙ₂₁，ｙ₂₁の順に繰り
返し受け取る。

【００４８】処理部列２２の動作を、レジスタ列２２と
関連させて説明する。先に述べた処理部列１６説明に続
けると、第６６クロックにおいて、ｙ₁₁の値がレジスタ
４４からライン４８を介して出力される。このライン４
８は、処理部列２２のＰＥ１（２２−１）の入力ライン
５０−１に接続している。ＰＥ１（２２−１）は、処理
部列１６のＰＥ１（１６−１）と同じ構成を有してい
る。したがい、ｙ₁₁は、ライン５０−１を介して、マル
チプレクサ５６−１のデータ入力に与えられる。レジス
タ列２６も、第１ステ−ジ１２のレジスタ列２０と同じ
構成を有している。そして、第３の行列Ｃの第１の入力
要素ｃ₁₁は、ライン２６−１を介して、第１のノレジス
タ２７−１に一度に入力される。タップライン５４−１
は、第１の要素ｃ₁₁の第１ビットを、マルチプレクサ５
６−１の選択制御入力に供給する。これにより、もし、
この第１ビットがセットされていれば、要素ｙ₁₁が選択
され、第１ビットがクリアされていれば、論理ゼロが選
択される。マルチプレクサ５６−１の出力は、ライン５
８−１を介して、レジスタ６２−１に与えられ記憶され
る。一方で、ｙ₁₁は、ライン５２−１を介して、レジス
タ６０−１に送られ部分結果として記憶される。これ
で、ＰＥ１におけるｃ₁₁の第１ビットとｙ₁₁の処理を終
了する。

【００４９】次のクロックでは、第２の引数組（ｃ₂₁，
ｙ₁₁）が、処理部列２２とレジスタ列２６に入力され
る。一方、この間にも、第１の引数組（ｃ₁₁，ｙ₁₁）の
処理は、ＰＥ２（２２−２）とレジスタ列２６で続けら
れる。第１の引数組（ｃ₁₁，ｙ₁₁）について説明を続け
る。ｙ₁₁は、レジスタ６０−１より、ライン５０−２を
介して、ＰＥ２（２２−２）のマルチプレクサ５６−２
に供給される。また、レジスタ２７−１に記憶されてい
るｃ₁₁の第２ビットが抽出され、ライン５４−２を介し
てマルチプレクサ５６−２の選択制御入力に供給され
る。これによりこの第２ビットがセットされている場合
は、データｙ₁₁が選択され。第２ビットがクリアされて
いる場合には、論理ゼロが選択される。マルチプレクサ
５６−２の出力は、ライン５８−２を介して加算レジス
タ６２−２に送られる。加算レジスタは、また、レジス
タ６２−１から、ライン６４−１を介して部分結果を受
け取る。マルチプレクサ５６−２の出力は、左（上位）
へ１ビットシフトされ、新たな部分結果を得るために、
今までの部分結果と加算される。この新たな部分結果
は、加算レジスタ６２−２に記憶される。データｙ
₁₁は、ライン５２−２を介して、レジスタ６０−２に送
られ記憶され、データｃ₁₁は、ライン２６−２を介し
て、レジスタ列２６のレジスタ２７−２に送られ記憶さ
れる。これで、ＰＥ２におけるｃ₁₁の第２ビットとｙ₁₁
の処理を終了する。

【００５０】次のクロックでは、第３の引数組（ｃ₁₂，
ｙ₂₁）が、ＰＥ１（２２−１）での処理のために、レジ
スタ列２６と、処理部列２２に入力されるの第１、第２
の引数組（ｃ₁₁，ｙ₁₁）（ｃ₂₁，ｙ₁₁）についての処理
は、レジスタ列２６、ＰＥ２（２２−３）、ＰＥ２（２
２−４）で、それぞれ続けられる。第１の引数組
（ｃ₁₁，ｙ₁₁）についての説明を続ける。ｙ₁₁は、レジ
スタ６０−２より、ライン５０−３を介して、ＰＥ２
（２２−３）のマルチプレクサ５６−３のデータ入力に
供給される。レジスタ２７−２に記憶されているｃ₁₁の
第３ビットは抽出され、ライン５４−３を介して、マル
チプレクサ５６−３の選択制御入力に与えられる。これ
により、この第３ビットがセットされている場合は、デ
ータｙ₁₁が選択され、第３ビットがクリアされている場
合は、論理ゼロが選択される。マルチプレクサ５６−３
の出力は。ライン５８−３を介して、加算レジスタ６２
−３に与えられる。加算レジスタ６２−３は、加算レジ
スタ６２−２よりライン６４−２を介して部分結果を受
け取る。マルチプレクサ５６−３の出力は、左（上位）
に２ビットシフトされ、最終結果を得るために、今まで
の部分結果と加算される。そして、この最終結果は、加
算レジスタ６２−３に記憶される。

【００５１】そして、次のクロックで、加算レジスタ内
の結果は、ライン６４−３を介してセレクタ６６−１に
出力される。セレクタ６６−１は、スイッチ７０−１、
７０−２を介して、アキュムレ−タ６８−１、６８−２
の一方を選択し、ライン６４−３にシ−ケンシャルに表
われる結果を記憶する。セレクタ６６−１は、各スイッ
チ７０−１、７０−２が矛盾なく交互に閉じるように、
システムクロックに基づいて供給されるクロックによっ
て制御される。

【００５２】このように、処理部列２２、２４からは、
それぞれ、４つの掛け算の結果が、各処理部列毎に１結
果が１サイクル毎に、各列よりシ−ケンシャルに出力さ
れる。たとえば、セレクタ６６−１、６６−２は、対応
する処理部列から出力された第１と第３の結果を順番
に、レジスタ６８−１、６８−３に記憶する。さらに、
セレクタ６６−１、６６−２は、第２と第４の結果を、
レジスタ６８−２、６８−４に記憶する。このような順
序付けにより、各結果を正確に計算し、行列Ｚの要素を
生成することができる。すなわち、第２ステ−ジのレジ
スタ列２６と第１の処理部列２２は、順次（ｃ₁₁，
ｙ₁₁），（ｃ₂₁，ｙ₁₁），（ｃ₁₂，ｙ₂₁），（ｃ₂₂，ｙ
₂₁）の組を受け取る。したがい、値ｚ₁₁＝ｃ₁₁ｙ₁₁＋ｃ
₁₂ｙ₂₁、すなわち第１の結果と第３の結果と和がアキュ
ムレ−タ６８−１により生成され、値ｚ₂₁＝ｃ₂₁ｙ₁₁＋
ｃ₂₂ｙ₂₁、すなわち第２の結果と第４の結果と和がアキ
ュムレ−タ６８−２により生成される。同様に、第２ス
テ−ジのレジスタ列２６と第２の処理部列２４は、順次
（ｃ₁₁，ｙ₁₂），（ｃ₂₁，ｙ₁₂），（ｃ₁₂，ｙ₂₂），
（ｃ₂₂，ｙ₂₂）の引数組を順次受け取る。そして、値ｚ
₁₂＝ｃ₁₁ｙ₁₂＋ｃ₁₂ｙ₂₂、値ｚ₂₂＝ｃ₂₁ｙ₁₂＋ｃ₂₂ｙ₂₂
が、セレクタ６６−２の前記奇数、偶数の記憶選択によ
よって、それぞれ第２の処理部列２４に接続する、アキ
ュムレ−タ６８−３、６８−４により生成される。この
ために、セレクタ６６−２は、スイッチ７０−１、７０
−２と同様に動作する２つのスイッチ７０−３と７０−
４を有している。

【００５３】両アキュムレ−タ６８−１と６８−３は、
それぞれ対応する処理部列よりの第１の結果と第３の結
果を同時に受け取る。そして、和であるｚ₁₁と、ｚ₁₂を
同時に計算し、ライン７２−１、７２−３を介して、ス
イッチ７４−１と７４−３に同時に出力する。これらの
スイッチ７４−１と７４−３の機能は、スイイッチ７０
−１、７０３と同様であり、閉じてレジスタ７６−１、
７６−３への出力を可能とする。レジスタ７６−１、７
６−３は、ライン８０−１に、次のクロックで、要素ｚ
１２が、レジスタ７６−３から７６−１にシフトされる
ように、縦並びに接続されている。一方、この間にレジ
スタ７６−１に記憶されていた要素ｚ₁₁は、出力ライン
７８−１上に移動する。

【００５４】アキュムレ−タ６８−１、６８−３と同様
に、アキュムレ−タ６８−２、６８−４は、同時に計算
を行う。そして、これらのアキュムレ−タ６８−２、６
８−４は、同時に要素ｚ₂₁，ｚ₂₂を生成し、ライン７２
−２、７２−４、スイッチ７４−２、７４−４を介し
て、縦並びのレジスタ７６−２、７６−４に、それぞれ
記憶する。そして、レジスタ７６−２、７６−４は、ラ
イン８０−２に、次のクロックで、要素ｚ２２が、レジ
スタ７６−４から７６−２にシフトされるように接続さ
れている。一方、この間にレジスタ７６−２に記憶され
ていた要素ｚ１１は、出力ライン７８−２上に移動す
る。これにより、行列掛け算器回路１０は、３行列の掛
け算、たとえば、２×２ＤＣＴ等を完遂する。

【００５５】図３、４は、８×８ＤＣＴをサポ−トする
ことのできるモジュラ−化行列掛け算回路１００を示し
ている。行列掛け算回路１０と同様に、回路１００は、
Ｙ＝ＸＣ^を計算する第１ステ−ジ１０６と、Ｚ＝ＣＹ
を計算する第２ステ−ジ１０８を有している。図３は第
１ステ−ジを、図４は第２ステ−ジ以降を示している。
第１ステ−ジ１０６は、図中、データが列１０２を、１
サイクルに１レジスタずつ、順次落ちていくように、縦
並びに接続された複数のレジスタを備えてレジスタ列１
０２を有している。また、第１ステ−ジ１０６は、処理
部列１０４−１、１０４−８を有している。各処理部列
１０４−１、１０４−８は、縦並びに接続された８個の
ＰＥ２の列の前段に、処理部ＰＥ１を有している。ＰＥ
１の内部構成を図５に示す。これは、図１、２の回路１
０のＰＥ１（１６−１，１８−１，２２−１，２４−
１）と、全く同じものである。特に、図５のＰＥ１は、
データ選択制御入力１３５と２つのデータ入力１４２、
１４３を備えたマルチプレクサ１４４を有している。デ
ータ選択制御入力は、レジスタ列１０２−１もしくは１
１０−１の第１ビットに接続している。行列Ｃ^もしく
はＹの要素は、ライン１４３に入力され、論理ゼロがラ
イン１４２に入力される。マルチプレクサの出力は、ラ
イン１４１を介して、レジスタ１４１に供給され、そこ
から、ライン１４９上を継続する段階へと出力される。
同様に、Ｃ^もしくはＹ行列の要素が、ライン１３７を
介してレジスタ１４５に供給され、そこから、ライン１
４７に出力される。

【００５６】ＰＥ２の内部構成を図６に示す。これもま
た、図１、２のＰＥ２（１６−２，１６−３，１８−
２，１８−３，２２−２，２２−３，２４−２，２４−
３）と同じものである。特に、図６のＰＥ２は、行列Ｃ
^もしくはＹの要素データ入力ライン１５５と、論理ゼ
ロデータ入力ライン１６９と、選択制御ビット入力ライ
ン１５９とを備えたマルチプレクサ１５１を有してい
る。さらに、マルチプレクサ１５１の、ライン１７１を
介して挙給される出力は、ライン１５７を介して供給さ
れる前段の結果と、加算レジスタ１４８で加算される。
明確化のために、加算レジスタ１４８を、出力ライン１
６５を有するレジスタ１５２と、レジスタ１５３に、ラ
イン１６３を介して接続した加算回路と１５０に分けて
示した。行列Ｃ^もしくはＹの要素は、ライン１６１を
介してレジスタ１５３に供給され、続いて、ライン１６
７に出力される。

【００５７】さて、各処理列は、図１、２のＰＥ３（１
６−４，１８−４）と同様に、その最後にＰＥ３を有し
ている。ＰＥ３の内部構成を図７に示す。ＰＥ２の加算
器レジスタ１４８と同様に、ＰＥ３のアキュムレ−タ１
５６を、アキュムレ−ト部１５８と、レジスタ１６０に
分けて示した。ライン１７３上をアキュムレ−ト部１５
８に入力した前段の結果は、ライン１７５に出力され
る。アキュムレ−タの累積結果は、順次ライン１８１に
出力されるようにライン１７５を介してレジスタ１７９
に供給される。また、パス１７７を介してレジスタ１６
０にフィ−ドバックされる。フィ−ドバックされた値
は、ライン１７３上の継続する入力結果と加算できるよ
う、ライン１８３を介してアキュムレ−タに与えられ
る。

【００５８】図１、２の２×２行列掛け算器１０と同じ
ように、１列中のＰＥ１とＰＥ２を合わせた数は、行列
Ｘの要素のビット数と等しい。この全部で９個のＰＥ１
とＰＥ２は、各処理列１０４−１〜１０４−８が、行列
Ｘの９ビットの要素の掛け算サポ−トするよう、縦並び
に接続される。また、これは、８個のレジスタを備えた
レジスタ列１０２に対応している。言い替えるならば、
レジスタ列１０２に、レジスタを、各処理部列１０４−
１〜１０４−８の各処理部列の各ＰＥ２に入力する行列
Ｘの要素を格納するように備える。

【００５９】図１、２の２×２行列掛け算器と同じよう
に、各処理部列１０４−１〜１０４−８は、２つの入力
を受け取る。１サイクル１要素ずつ、第１のデータ行列
Ｘの要素が、レジスタ列１０２にシ−ケンシャルに
ｘ₁₁，ｘ₁₂，．．，ｘ₁₈，ｘ₂₁，ｘ₂₂，．．，
ｘ₂₈．．．ｘ₈₈の順に一度に一つづつ入力される。そし
て、これらの行列の要素は、レジスタからレジスタへと
シフトされる。引き続くサイクル中において、レジスタ
列は、行列Ｘよりの各要素のｍ番目のビットを、各処理
部列１０４−１〜１０４−８のｍ番目の処理部に出力す
る。第２の入力のシ−ケンスとして、各処理部列１０４
−１〜１０４−８は、第２の行列Ｃ^の１列の要素を、
１サイクルに１要素づつ、行列Ｘの各列について１回づ
つ（８回）受け取る。すなわち、たとえば、処理部列１
０４−４は、ｃ^₁₄，．．，ｃ^₈₄，ｃ^₁₄，．．，ｃ
^₈₄，ｃ^₁₄，．．，ｃ^₈₄，ｃ^₁₄，．．，ｃ^₈₄，ｃ
^₁₄，．．，ｃ^₈₄，ｃ^₁₄，．．，ｃ^₈₄，ｃ
^₁₄，．．，ｃ^₈₄，ｃ^₁₄，．．，ｃ^₈₄のシ−ケンスで
受け取る。これらの行列要素は、処理部列１０４−４に
沿って、処理部から処理部へと渡される。

【００６０】各処理部列１０４−１〜１０４−８は、中
間行列Ｙの要素の１列を出力する。実際の中間行列の掛
け算は図１、２の回路１０と同様に行われる。そして、
各要素は、ＰＥ３で計算され、８個の引数組の積結果が
互いに加算される。これは、行列の掛け算の公式にした
がい、第１の行列Ｘの各行は、第２の行列Ｃ^の列の対
応する要素と掛け算されることによるものである。そし
て、これら積結果は、すべて、行列Ｙの１要素を生成す
るために互いに加算される。第１の行列Ｘの１行あたり
８個の要素と、第２の行列の１列あたり８個の要素は、
行列Ｙの要素を得るために、相互に加算しなければなら
ない８個の積結果を生じる。

【００６１】中間行列Ｙの各要素が計算されたら、次の
８サイクル中、これをライン１３２−２〜１３２−８を
介して、第２ステ−ジ１０８に出力するようにする。す
なわち、たとえば処理部列１０４−７は、ライン１３２
−７を介して、ｙ₁₇，ｙ₁₇，ｙ₁₇，ｙ₁₇，ｙ₁₇，ｙ₁₇，
ｙ₁₇，ｙ₁₇，ｙ₂₇，ｙ₂₇，ｙ₂₇，ｙ₂₇，ｙ₂₇，ｙ₂₇，ｙ
₂₇，ｙ₂₇，．．，ｙ₈₇のシ−ケンスで出力を行う。

【００６２】図１、２の第２ステ−ジのように、回路１
００の第２ステ−ジ１０８は、レジスタ列１１０と、８
個の処理部列１２４−１〜１２４−８を、８×８ＤＣＴ
をサポ−トするために有している。ここで、レジスタ列
は、１４ビットの掛け算をサポ−トするために１３個の
レジスタを備えている。また、レジスタ列１１０に応じ
て、各処理部列１２４−１〜１２４−８は、１つのＰＥ
１と１３個のＰＥ２を備えている。

【００６３】第１ステ−ジと同様に、各処理部列１２４
−１〜１２４−８の各処理部は、１サイクルで２つの掛
け算引数を受け取る。すなわち、各処理部列１２４−１
〜１２４−８の各処理部は、第１の掛け算引数として、
１要素／サイクルで、行列Ｃの要素の１ビットを受け取
る。このために、第２ステ−ジののレジスタ列１１０に
は、１サイクル毎に１要素が、ｃ₁₁，ｃ₂₁，．．，
ｃ₈₁，ｃ₁₂，ｃ₂₂，．．，ｃ₈₂，．．ｃ₈₈のシ−ケンス
で入力される。そして、これらより、連続するサイクル
において、行列Ｃの全ての要素のｐ番目のビットが、各
処理部列１２４−１〜１２４−８のｐ番目の処理部に入
力される。一方、これ同時に、各処理部列１２４−１〜
１２４−８は、第２の掛け算引数として、一度に一要素
づつ、中間行列Ｙのひとつの列の要素を受け取る。これ
らの要素は、第１ステ−ジ１０６の処理部列１０４−１
〜１０４−８のＰＥ３から、ライン１３２−１〜１３２
−８を介して、直接、第２ステ−ジ１０８の対応する処
理部列に、繰り返し出力される。ここで、実際の引数の
掛け算は、図１、２の回路１０と同様に行われる。

【００６４】入力された各引数組の最終積結果は、各処
理部列１２４−１〜１２４−６の最終段のＰＥ２より、
ライン１３０−１〜１３０−８を介して出力される。図
１、２の２×２行列掛け算回路１０と同様に、これらの
積結果は、最終行列Ｚを形成するために、選択的に累積
される。行列Ｚの第１の行の一要素を計算するために
は、ライン１３０−１〜１３０−８のうちの一つに出力
された、第１の積結果と、それから８番目毎の全ての積
結果の全てが累積されなけらばならない。同様に行列Ｚ
の第２の行の一つの要素を計算するためには、ライン１
３０−１〜１３０−８のうちの一つに出力された、第２
の積結果と、それから８番目毎の積結果の全てが累積さ
れなけらばならない。すなわち、行列Ｚのｌ（ｌは、１
から８までの数）番目の行の要素を計算するためには、
ライン１３０−１〜１３０−８のうちの一つに出力され
た、ｌ番目の積結果と、それから８番目毎の全ての積結
果を、ＬＫ番目の積結果まで相互に加算しなければ成ら
ない。さらに、図１、２の回路１０と同様に、このよう
にして計算された行列Ｚの要素の列ｋは、中間行列Ｙか
ら特定の処理部列１２４−１〜１２４−８に入力され
た、第２の掛け算引数の列に等しい。すなわち、もし、
処理部列１２４−３がライン１３３２−３から中間行列
の要素を列ｙ₁₃，．．，ｙ₈₃から受け取った場合には、
その処理部列１２４−３は、ライン１３０−３上に、要
素ｚ₁₃，．．，ｚ₈₃を計算するために加算される積結果
を出力する。

【００６５】積結果を出力順に正しく計算するために、
回路１００は、Ｓ−ＢＯＸスイッチアレイ１６２と、ア
キュムレ−タマトリックス１８０と、Ｄ−ＢＯＸスイッ
チアレイと、回路１００から計算した行列Ｚの要素を出
力するシリアル出力メモリ１８２とを有している。これ
らの各部の詳細な構成を図８、９、１０に示す。図９は
Ｓ−ＢＯＸの詳細を、図１０はＤ−ＢＯＸの詳細を、図
１１はこれらのタイミング信号を示したものである。

【００６６】図９を用いて、Ｓ−ＢＯＸスイッチアレイ
とアキュムレ−タ１６４−１−１，．．，１６４−１−
８の動作を説明する。アキュムレ−タマトリックス１６
４は、分離されたアキュムレ−タ１６４−１−
１，．．，１６４−８−８より構成されている。すなわ
ち、行列Ｚの全ての要素に対応するアキュムレ−タが存
在するように、Ｌ行Ｋ列のアキュムレ−タが存在する。
先にも述べたように、行列Ｚの特定の列Ｋを計算するた
めに必要な積結果は、対応するＫ番目の出力ライン１３
０−１，．．１３０−８にのみ出力される。そこで、ア
キュムレ−タの各列は、たとえば、１６４−１−
１，．．，１６４−８−１は、ライン１３０−
１，．．，１３０−８のうちのひとつに対応している。
また、１列のアキュムレ−タは、１３０−１，．．，１
３０−８のうちの、ひとつのラインからのみ積結果を受
け取る。図１１に示すように、サイクルは、積結果の第
１グル−プｃ₁₁ｙ₁₁，ｃ₁₁ｙ₁₂，．．，ｃ₁₁ｙ₁₈が、そ
れぞれライン１３０−１，．．，１３０−８に出力され
るサイクルからカウントされる。クロックライン１９０
−１に表われたパルスは、１８６−１から１８６−８の
各Ｓ−ＢＯＸの第１のスイッチ１８８−１（図９参照）
を閉じ、ライン１３０−１〜１３０−８から。各列の最
初のアキュムレ−タ１６４−１−１，．．，１６４−１
−８、すなわち、アキュムレ−タマトリックスの第１行
にデータを流す。２番目のクロックで、行列Ｚの第２行
を生成するために計算されなければ成らない第２の積結
果のグル−プｃ₂₁ｙ₁₁，ｃ₂₁ｙ₁₂，，．．，ｃ₂₁ｙ
₁₈が、ライン１３０−１〜１３０−８に、それぞれ出力
される。クロックライン１９０−２に表われたパルス
は、各Ｓ−ＢＯＸ１８６−１〜１８６−８の第２番目の
スイッチ１８８−２を閉じ、ライン１３０−１〜１３０
−８から、第２行目のアキュムレ−タ１６４−２−
１，．．，１６４−２−８にデータを流す。このよう
に、図１１のタイミングダイアグラムは、各Ｓ−ＢＯＸ
１８６−１，．．，１８６−８の適当なスイッチ１８８
−１、１８８−２，１８８−３，１８８−４，１８８−
５，１８８−６，１８８−７，１８８−８を閉じること
により、アキュムレ−タの各行が、８サイクルのうちの
一つのサイクルで択一的に選択されることを示してい
る。さらに、このような選択の手順は、８サイクル毎に
繰り返される。このようにして、アキュムレ−タ１６４
−１−１，．．，１６４−８−８は、ライン１３０−１
〜１４０−８に出力された積結果を選択的に累積し、行
列Ｚの要素を、前述した思惑通りに生成する。

【００６７】スイッチ１８８−１〜１８８−８を択一的
に閉じるために、図３、４の回路１００は、クロック生
成器１８４を備えている。このクロック生成機１８４
は、複数のクロックライン１９０（クロックライン１９
０−１〜１９０−８より成る）を介して、各Ｓ−ＢＯＸ
１８６−１，．．，１８６−８に、８個のパルスのシ−
ケンスを提供する。図１１の最初のクロックにおいて
は、ライン１９０−１（図９参照）のみが、パルスを受
取り、各Ｓ−ＢＯＸ１８６−１〜１８６−８の第１のス
イッチ１８８−１を閉じる。第２のクロックにおいて
は、ライン１９０−２（図９参照）のみが、パルスを受
取り、各Ｓ−ＢＯＸ１８６−１〜１８６−８の第１のス
イッチ１８８−２第ｔ番目のクロックにおいては、ｔの
モジュロ８番目のクロックライン１９０がパルスを受
取、各Ｓ−ＢＯＸ１８６−１〜１８６−８のｔのモジュ
ロ８番目のスイッチが閉じられ、ライン１３０−１〜１
３０−８上のデータが、アキュムレ−タマトリックス１
６４のｔのモジュロ８番目の行のアキュムレ−タに送ら
れる。

【００６８】以上のような処理毎に、各ライン１３０−
１〜１３０−８上に出力された１、９、１７、２５、３
３、４１、４９、５７番目の積結果が、それぞれ、アキ
ュメレ−タマトリックスの第１の行のアキュムレ−タ１
６４−１−１，．．，１６４−１−８に蓄えられる。こ
のようにして、５７クロック後には、第１行のアキュム
レ−タ１６４−１−１，．．，１６４−１−８の値の計
算は完了する。第５８クロックでは、残りの行のアキュ
ムレ−タ１６４−２−１，．．，１６４−２−８１６４
−３−１，．．，１６４４−８−８での計算は終了して
いないけれども、第１行のアキュムレ−タ１６４−１−
１，．．，１６４−１−８は、第５８クロックで、記憶
している行列Ｚの要素、すなわち、行列Ｚの第１行の要
素ｚ１１，．．，ｚ１８を、シリアル出力メモリ１８２
に出力するシリアル出力メモリ１８２は、出力ライン２
００２に向かって、１クロックで１つ右のレジスタに、
各レジスタに記憶したデータが伝搬するように縦並びに
接続された５６個のレジスタ２０２−１〜２０２−５６
を有している。したがい、シリアル出力メモリに要素を
読み込むことにより、各要素をシルアルに出力ライン２
００より出力することができる。このために、図３、４
の回路１００は、Ｄ−ＢＯＸ１９６−１〜１９６−８よ
り成るＤ−ＢＯＸアレイ１８０を備えている。

【００６９】図８、図１０における、行列Ｚの要素の出
力について説明する。Ｓ−ＢＯＸ１８６−１〜１８６−
８と同様に、各Ｄ−ＢＯＸ１９６−１〜１９６−８は、
クロックライン１９４（ライン１９４−１〜１９４−８
を有する）によって、それぞれ制御される８個の独立し
たスイッチを有している。各Ｄ−ＢＯＸは、アキュムレ
−タマトリックス１６４の１列のアキュムレ−タの出力
をル−ティングするために設けている。また、各スイッ
チ１９８−１〜１９１−８（図１、２参照）は、アキュ
ムレ−タ１６４の特定の列のアキュムレ−タの出力をル
−ティングするために設けている。５８番目のクロック
で、要素が、各Ｄ−ＢＯＸ１９６−１〜１９６−８の第
１番目のスイッチ１９８−１によって、アキュムレ−タ
マトリックス１６４の第１行の各アキュムレ−タ１６４
−１−１、．．、１６４−１−８から移動される。この
ために、クロック生成器１８４は、Ｄ−ＢＯＸ１９６−
１〜１９６−８のスイッチ１９８−１を閉じるパルスを
ライン１９４−１上に生成する。要素ｚ１１は、Ｄ−Ｂ
ＯＸ１９６−８によって、アキュムレ−タ１６４−１−
１から、直接、ライン２００にル−ティングされる。他
のアキュムレ−タ１６４−１−２〜１６４−１−８の７
つの要素は、Ｄ−ＢＯＸ１９６−２〜１９６−８によっ
て、ｚ₁₂，．．，ｚ₁₈の順に、シリアル出力メモリ１８
２の右側の七つのレジスタ２０２−１〜２０２−７に読
み込まれる。

【００７０】５８番目のクロックでは、第２行目のアキ
ュムレ−タ１６４−２−１，．．，１６４−２−８の、
行列Ｚの第２行の要素ｚ₂₁，．．，ｚ₂₈の計算が完了す
る。そこで、５９番目のクロックで、行列Ｚの第２行の
要素ｚ₂₁，．．，ｚ₂₈は、第２行目のアキュムレ−タ１
６４−２−１，．．，１６４−２−８からシルアル出力
メモリの、右側の次の８個のレジスタ２０２−９〜２０
２１６にシフトされる。このために、クロック生成器１
８４は、各Ｄ−ＢＯＸ１９６−１〜１９６−８のスイッ
チ１９８−２を閉じるパルスをクロックライン１９４−
２上に生成する。第２行目のアキュムレ−タ１６４−２
−１，．．，１６４−２−８の要素は、このように、シ
ルアル出力メモリに読み込まれる。第２行目のアキュム
レ−タ１６４−２−１，．．，１６４−２−８より読み
込みは、右側の７つのレジスタ２０２−１〜２０２−７
の要素の一つ右側へのシフトを考慮する。すなわち、５
９番目のクロックの立ち下がりで、ｚ１２がライン２０
０に出力され、要素ｚ₁₃，．．，ｚ₁₉，ｚ₂₁，．．，ｚ
₂₈は、この順序で、右側のレジスタ２０２−１〜２０２
−１４を占めるこのような処理は、次の６つのクロック
において、残りの行のアキュムレ−タ１６４−３−
１，．．，１６４−３−８，１６４−４−１，．．，１
６４−８−８について続けられる。そして、６５番目の
クロックで、５６個のレジスタ２０２−１〜２０２−５
６の全ては、行列Ｚの第２から第８行の要素によって埋
まる。

【００７１】このような出力のシ−ケンスを実現するた
めに、クロック生成器１８４は、複数のクロックライン
１９４（クロックライン１９４−１〜１９４−８より成
る）を備えている。クロックライン１９４−１〜１９４
−８は、５８番目から６５番目のクロック中に、択一的
なパルスを受け取る。６５クロックの後は、Ｄ−ＢＯＸ
のクロックライン１９４は、少なくとも５６クロック目
まで無効化される。この期間、シリアル出力メモリ１８
２は、５６個のレジスタ２０２−１〜２０２−５６に記
憶した要素をシフトアウトする。すなわち、６６番目〜
１２１番目までの全てのクロックで、レジスタ２０２−
１〜２０２−５６は、１サイクルに１レジスタづつ、要
素を右側にシフトし、最も右側のレジスタ２０２−１は
要素をライン２００に出力する。

【００７２】さて、本実施例は、入力行列の連続した計
算にも適用することができる。たとえば、図３、４にお
いて、最初の行列掛け算を行う２つの行列ＸとＣ^が第
１ステ−ジ１０６への入力が済んだら、第２番目の行列
掛け算を行う第２番目の組Ｘ'，Ｃ^'を回路１００に入
力することができる。各掛け算は、連続して同じように
行われる。すなわち、行列ＸとＣ^の最後の引数の組が
処理列１０４−１〜１０４−８に入力されたら、これに
続いて、行列Ｘ'とＣ^'の最初の引数の組を処理列１０
４−１〜１０４−８に入力することができる。

【００７３】ところで、ＤＣＴの計算は、任意の３行列
について行われるのではなく、本実施例でＣ，Ｃ^と名
付けた２つの係数行列は固定されている。これらの行列
の要素は、回路１００に適した入力を提供できるように
記憶されている。図１２〜１４の回路は、このような入
力を提供する係数供給手段を示すための図である。

【００７４】図１２は、係数供給手段を構成するのに用
いる典型的なレジスタ２０６を示したものである。この
レジスタは、Ｄ入力とＱ出力２１２セット２１４とリセ
ット２１６の端子を備えた複数のＤフリップフロップ２
０８を有している。図１３は、図３，４の回路１００の
レジスタ列１１０に係数を供給するための配置を示して
いる。図１３に示すように、行列Ｃの各要素について一
つずつ設けた、６４のレジスタ２０６−１，２０６−
２，２０６−３．．，２０６−６２，２０６−６３，２
０６−６４がリング状に接続されている。各レジスタ２
０６−１，２０６−２，２０６−３．．，２０６−６
２，２０６−６３，２０６−６４のＤ入力は、すぐ右側
に隣接するレジスタのＱ出力に、ライン２１８−２，２
１８−３．．，２１８−６２，２１８−６３，２１８−
６４に接続されている。さらに、最も右側のレジスタ２
０６−６４のＤ入力は、ライン２１８−１を介して、最
も左側のレジスタのＱ出力に接続している。そして、毎
クロック毎に、要素が左周りに１レジスタ回転する。さ
らに、レジスタ２０６−１のＱ出力は、さらにレジスタ
列１１０の入力ライン１１０−１に接続している。そし
て、要素がレジスタ２０６−１を通って回転するに従
い、各要素がレジスタ列１１０に入力される。このよう
に６４クロックで、各要素はレジスタ列１１０に入力さ
れ、供給回路２２０は初めの状態に戻る。

【００７５】さて、係数供給回路を行列Ｃ^の各列の要
素を処理部列１０４−１〜１０４−８に供給するために
も、図１３の回路を修正した係数供給回路を第１ステ−
ジ１０６で用いるようにしてもよい。図１４に示すよう
に、修正した係数供給回路は、前述したように各々がリ
ング状に接続した８個のレジスタを有している。本実施
例では、これらの回路２２０−１、２２０−
２、，．．，２２０−８は、一度のＤＣＴ毎に、各処理
部１０４−１〜１０４−８に、それぞれ８度入力される
８個の要素を記憶している。各回路の動作は、他の回路
２２０と同じである。

【００７６】図１５、１６は、２×２ＤＣＴをサポ−ト
することのできる、さらに高性能化した行列掛け算回路
を示している。図１５が第１ステ−ジ、図１６が第２ス
テ−ジ以降を示している。さて、この回路は、２つのキ
−となる相違点を除き、図１、２の回路１０と同じであ
る。すなわち、各処理部列２３２、２３４、２３６、２
３８の各ＰＥ２２３２−２，２３２−３，２３４−３，
２３６−２，２３６−３，２３８−２，２３８−３にお
いて、加算レジスタは、後に詳述するキャリ−保存加算
レジスタ２４０−１，２４０−２，２４２−１，２４２
−２，２４４−１，２４４−２，２４６−１，２４６−
２に置き換えられている。また、最終段のＰＥ２の次、
最後のＰＥ２２３２−３，２３４−３，２３６−３、２
３８−３とＰＥ３２３２−４、２３４−４の入力ライン
２５２−１、２５２−２もしくはセレクタ２５４−１，
２５４−２の入力ライン２５２−３，２５２−４の間
に、加算レジスタ２４８−１〜２４８−４が挿入されて
いる。この２つの変更を除き、回路２３０の動作は、図
１，２の回路１０と同じである。

【００７７】図１７を用いて、キャリ−保存加算レジス
タ２４０−１，２４０−２，２４２−１，２４２−２，
２４４−１，２４４−２，２４６−１，２４６−２と加
算レジスタ２４８−１〜２４８−４の加算回路の動作を
詳細に説明する。キャリ−保存加算回路３００は、２つ
のキャリ−保存加算ステ−ジ３０１−１、３０１−２と
最終加算ステ−ジ３０１−３を有している。各ステ−ジ
３０１−１、３０１−２、３０１−３は、処理部列の各
ＰＥ２中の１つのキャリ−保存加算レジスタの加算回路
に対応する。たとえば、処理部列２３２では、回路３０
１はキャリ−保存加算レジスタ２４０−１に対応し、ス
テ−ジ３０２−２はキャリ−保存加算レジスタ２４０−
２に対応し、ステ−ジ３０１−３は加算レジスタ２４８
−１に対応する。なお、図１７では、ステ−ジ３０１−
１、３０１−２、３０１−３を互いに直接、接続して示
した。しかし、実際の実施の際には、レジスタが各ステ
−ジ３０１−１、３０１−２、３０１−３の出力のとこ
ろに挿入される。

【００７８】加算ステ−ジ３０１−１の動作について説
明する。加算ステ−ジ３０１−１は、３つの全加算回路
３２２−１、３２２−２、３２２−３を有している。そ
して、図１７に示した全てのステ−ジ３０１−１、３０
１−２、３０１−３は、４ビット値の加算を行う。しか
し、必要に応じて、さらに全加算器を同様につなげてい
けば、任意ビットの加算に適合させることができる。

【００７９】たとえば２３２−２のような最初のＰＥ２
において、ビット積結果は左に１ビットシフトされＰＥ
１の積結果と加算される。ＰＥ１の積結果（Ｂで示す）
は、ライン３０２を介して、加算ステ−ジ３０１−１に
供給される。Ｂの値は、それぞれライン３１２−１、３
１０−１、３０８−１、３０６−１より入力される４ビ
ット（ｂ３ｂ２ｂ１ｂ０で示す）で構成される。ＰＥ２
の積結果（Ｂ'で示す）は、ライン３０４−１を介し
て、加算ステ−ジ３０１−１に与えられる。Ｂ'の値
は、それぞれライン３２０−１、３１８−１、３１６−
１、３１４−１より入力される４ビット（ｂ３'ｂ２'ｂ
１'ｂ０'で示す）で構成される。各全加算回路３２２−
１、３２２−２、３２２−３の第３の入力３２２−１，
３２４−１，３２６−１はグランドである。なお、半加
算器を第１の加算ステ−ジ３１０−１で用いるようにし
てもよい。

【００８０】値ＢとＢ'の和（Ｓで示す）とキャリ−
（Ｃ）は、それぞれ、５ビット（ｓ４ｓ３ｓ２ｓ１ｓ０
で示す）と３ビット（ｃ２ｃ１ｃ０で示す）である。図
１７の第１の加算ステ−ジ３０１−１は、値Ｂに対し
て、左にシフトされる。もしくは、左にオフセットを与
えられる。したがい、ライン３０６−１の入力ビットｂ
０は、和の最下位桁ｓ０を形成し、同様に、ライン３２
０−１の入力ビットｂ３'は和の最上位ビットｓ４を形
成する。ライン３０８−１と３１４−１のビットｂ１，
ｂ０'は、全加算回路３２２−１で加算され、和のビッ
トｓ１とキャリ−のビットｃ１が、それぞれ、ライン３
０６−２、３２２−２に出力される。ライン３１０−１
と３１６−１のビットｂ２とｂ１'は、全加算回路３３
４−１で加算され、和のビットｓ２とキャリ−のビット
ｃ２が、ライン３０８−２、３１４−２に、それぞれ出
力される。最後に、ライン３１２−１と３１８−１のビ
ットｂ３、ｂ２'は、全加算回路３３６−１で加算さ
れ。和のビットｓ３とキャリ−のビットｃ３を、ライン
３１０−２、３２６上に、それぞれ生成する。このよう
にして、第１の加算ステ−ジでの、２つの値Ｂ，Ｂ'
の、キャリ−保存加算が終了する。

【００８１】次のステ−ジ３０１−２における、たとえ
ば２３２−３（図１５、１６参照）のような、第２段目
のＰＥ２の積結果（Ｂ''で示す）と、その前のＰＥ２ス
テ−ジでの結果（たとえば、２３２−２）の加算につい
て説明する。ライン３０４−２にお出力される値Ｂ''
は、和Ｓとキャリ−Ｃと加算され、新たな和Ｓ'とＣ'を
生成する。図１７において、Ｂ''は、それぞれライン３
２０−２、３１８−２、３１６−２、３１４−２に表わ
れる４ビット（ｂ３'，ｂ２'，ｂ１'，ｂ０'で表す）よ
り成る。値Ｓ'とＣ'は、それぞれ、ｓ４'ｓ３'ｓ２'ｓ
１'ｓ０で表す５ビットと、ｃ３'ｃ２'ｃ１'で表す３ビ
ットより成る。続いて行われるＢ''の左へのシフトによ
り、ライン３０６−２の入力ｓ１は、第２の和の最下位
ビットｓ'０を形成する。また、ｂ３''は、最上位ビッ
トｓ４'を形成する。ライン３０８−２、３２２−２、
３１４−２のビットｓ２，ｃ１，ｂ''０は全加算回路３
３２−２で加算され、和のビットｓ'１とキャリ−のビ
ットｃ'１が、ライン３０６−３、３２２−３にそれぞ
れ出力される。また、ライン３１０−２、３２４−２、
３１６−２のビットｓ３，ｃ２，ｂ１''は全加算回路３
３４−２で加算され、和のビットｓ２'とキャリ−のビ
ットｃ'２が、ライン３０８−３、３２４−３にそれぞ
れ出力される。最後に、ライン３１２−２、３２６−
２、３１８−２のビットｓ４，ｃ３，ｂ２''は、全加算
回路３３６−２で加算され、和のビットｓ３'とキャリ
−のビットｃ３'が、ライン３１０−３、３１６−３上
に生成される。このようにして、第２の加算ステ−ジ３
０１−２における、値Ｂ''とＳ，Ｃで表現される前回の
加算結果との、第１のキャリ−保存加算が完了する。な
お、さらなる値の加算を行うために、加算ステ−ジを追
加してもよい。これは、図１５、１６の処理部列２３
２、２３４、２３６、２３８にＰＥ２ユニットを追加す
ることに対応する。

【００８２】図１５、１６の特定の処理部列２３２で最
後のビットの掛け算が終わったら、最後に、和Ｓ'とキ
ャリ−Ｃ'は互いに加算される。このために、加算レジ
スタ２４８−１〜２４８−４（図１５、１６参照）は、
通常の加算回路を備えている。図１７に示すように、通
常加算ステ−ジ３０１−３は、和Ｓ'とキャリ−Ｃ'を受
取り、７ビット（ｃ３''、ｓ３''、ｓ２''、ｓ１''、ｓ
０''、ｓ０'、ｓ０）の最終的な和を生成する。下位の３
ビットｓ０''ｓ０'ｓ０は、計算せずとも求まり、そえ
ぞれライン３０６−３、３０６−２、３０６−１に出力
される。ビットｃ１'とｓ２'は、ライン３２２−３、３
０８を介して、第３の入力がグランドである全加算回路
３２２−３に入力され、和のビットｓ１''とｃ１''が、
それぞれライン３０６−４、３２２−４上に出力する。
ビットｃ１''は、ビットｃ２'，ｓ３'と共に、ライン３
２４−４、３２４−３、３１０−３を介して、全加算回
路３３−４に入力され、和のビットｓ２''とキャリ−の
ビットｃ２''が、ライン３０８−４、３２４−４に、そ
れぞれ出力する。最後に、ビットｃ２''は、ビットｃ
３'とｓ４'と共に、ライン３２４−４、３２６−３、３
１２−３を介して全加算回路３３６−３に入力され、和
のビットｓ３''とキャリ−のビットｃ３''が、ライン３
１０−４と３２６−４に、それぞれ出力される。このよ
うに、最後の加算ステ−ジで、通常の加算レッジスタを
用いて、和Ｓ'とキャリ−Ｃ'を加算し、最終的な和が求
められる。

【００８３】

【発明の効果】以上のように、本発明によれば、効率的
に３行列の積を取ることのできる回路およびアルゴリズ
ムを提供することができる。

【図面の簡単な説明】

【図１】本発明の実施例に係る行列掛け算部の前半部分
の構成を示したブロック図である。

【図２】本発明の実施例に係る行列掛け算部の後半部分
の構成を示したブロック図である。

【図３】本発明の他の実施例に係る行列掛け算部の前半
部分の構成を示したブロック図である。

【図４】本発明の他の実施例に係る行列掛け算部の後半
部分の構成を示したブロック図である。

【図５】処理部ＰＥ１の構成を示すブロック図である。

【図６】処理部ＰＥ２の構成を示すブロック図である。

【図７】処理部ＰＥ３の構成を示すブロック図である。

【図８】Ｓ−ＢＯＸ、Ｄ−ＢＯＸ、アキュムレ−タマト
リックスの詳細構成を示すブロック図である。

【図９】Ｓ−ＢＯＸの構成を示すブロック図である。

【図１０】Ｄ−ＢＯＸの構成を示すブロック図である。

【図１１】スイッチマトリックスの制御タイミングを示
すタイミングチャ−トである。

【図１２】係数供給手段に用いるレジスタを示したブロ
ック図である。

【図１３】レジスタ列に係数を供給する手段の構成を示
すブロック図である。

【図１４】処理部列に係数を供給する手段の構成を示す
ブロック図である。

【図１５】本発明の他の実施例に係る行列掛け算部の前
半部分の構成を示したブロック図である。

【図１６】本発明の他の実施例に係る行列掛け算部の後
半部分の構成を示したブロック図である。

【図１７】キャリ−保存加算レジスタを抜き出して示し
たブロック図である。

【符号の説明】

１０行列掛け算回路１２第１ステ−ジ１４第２ステ−ジ２０レジスタ列１６、１８処理部列１６−１、１８−１処理部ＰＥ１１６−２、１６−３、１８−２、１８−３処理部ＰＥ
２２２、２４処理部列２６レジスタ列２２−２、２２−３、２４−２、２４−３処理部ＰＥ
２２２−１、２４−１処理部ＰＥ１

Claims

【特許請求の範囲】

【請求項１】要素ｘ_ij（ｉ＝１．．．Ｉ，ｊ＝１．．．
Ｊ）を有する第１の行列Ｘと要素ｃ^_jk（ｋ＝１．．．
Ｋ）を有する第２の行列Ｃ^との掛け算を行う第１のス
テ−ジであって、それぞれがシ−ケンシャルに特定のｋの値について、中
間行列の（数１）で、【数１】定義される要素を出力する、複数の並列に動作する第１
のパイプライン回路を備えた第１のステ−ジと、前記第１のステ−ジより出力される要素ｙ_ikを受け取
り、要素ｙ_ikと、要素ｃ_liを有する第３の行列Ｃとの掛
け算を行う第２のステ−ジであって、それぞれがシ−ケンシャルに特定のｋの値について積ｃ
_liｙ_ikを出力する、複数の並列に動作する第２のパイプ
ライン回路とを有する第２のステ−ジと、それぞれが、接続した前記第２のパイプライン回路より
の積ｃ_liｙ_ikを、特定のｋの値について、（数２）で、【数２】定義される和を生成するように、選択的に累積する複数
のアキュムレ−タとを有することを特徴とする行列掛け
算回路。
【請求項２】請求項１記載の行列掛け算回路であって、前記第１のステ−ジの各第１のパイプライン回路は、そ
れぞれ第１のシ−ケンスｘ_11,ｘ_12,..,ｘ_1J,ｘ_21,ｘ
_22,..,ｘ_2J,,..,ｘ_IJと、特定のｋについての第２のシ
−ケンスｃ^_1k，ｃ^_2k，，．．，ｃ^_JKをＩ回の繰り返
した第２のシ−ケンスとの掛け算を行うパイプライン回
路であって、かつ、前記第１のシ−ケンスに含まれる各要素の第１ビットと
前記第２のシ−ケンスの各要素との２つの入力を、１サ
イクル毎に同時に受取、１サイクル毎に前記２入力の積
を出力する１番目の処理部と、２からＭ（Ｍは前記第１のシ−ケンスの各要素のビット
数）番目までの複数の処理部とを有し、ｍ（２≦ｍ≦Ｍ）番目の前記処理部は、毎サイクルに、
前記第１の要素のｍ番目のビットと、当該第１の要素に
対応する第２のシ−ケンスの要素との２つの入力を受取
り、ｍ−１番目の処理部における和と前記２入力の積と
の和を出力することを特徴とする行列掛け算回路。
【請求項３】請求項２記載の行列掛け算回路であって、前記１番目の処理部は、前記第２のシ−ケンスの各要素を記憶するレジスタと、前記第１のシ−ケンスの第１ビットを選択制御入力とし
て受け取り、前記第２のシ−ケンスの要素をデータ入力
として受け取り、前記第１ビットが論理１であるときに
前記第２のシ−ケンスの要素を選択し、前記第１ビット
が論理ゼロである場合に論理ゼロを選択するマルチプレ
クサと、前記マルチプレクサの出力を記憶する累積手段とを有す
ることを特徴とする行列掛け算回路。
【請求項４】請求項２記載の行列掛け算回路であって、前記ｍ番目の処理部は、前記第２のシ−ケンスの要素を記憶するレジスタと、前記第１のシ−ケンスの第ｍビットを選択制御入力とし
て受け取り、ｍ−１番目の処理部の前記レジスタよりの
前記第２のシ−ケンスの要素をデータ入力として受け取
り、前記第１ビットが論理１であるときに前記第２のシ
−ケンスの要素を選択し、前記第１ビットが論理ゼロで
ある場合に論理ゼロを選択するマルチプレクサと、累積手段とを有し、当該累積手段は、ｍ−１ビット上位にシフトした前記マ
ルチプレクサの出力とｍ−１番目の処理部の累積手段に
記憶された値との和を計算し、記憶することを特徴とす
る行列掛け算回路。
【請求項５】請求項２記載の行列掛け算回路であって、前記第１のステ−ジは、さらに、連続するサイクルにおいて、前記第１のシ−ケンスを受
け取り、当該シ−ケンスの要素の第ｍビットを、第１ス
テ−ジの各パイプライン回路のｍ番目の処理部に出力す
る、縦並びに接続された複数のレジスタを有することを
特徴とする行列掛け算回路。
【請求項６】請求項１記載の行列掛け算回路であって、前記第２のス−テ−ジの各パイプライン回路は、それぞれ第１のシ−ケンスｃ₁₁，ｃ₂₁，．．，ｃ_L1，ｃ
₁₂，ｃ₂₂，．．，ｃ_L2，，．．，ｃ_LIと、特定のｋにつ
いての第２のシ−ケンスｙ_1K，ｙ_2K，，．．，ｙ_IKをＬ
回の繰り返した第２のシ−ケンスとの掛け算を行うパイ
プライン回路であって、かつ、前記第１のシ−ケンスに含まれる各要素の第１ビットと
前記第２のシ−ケンスの各要素との２つの入力を、１サ
イクル毎に同時に受取、１サイクル毎に前記２入力の積
を出力する１番目の処理部と、２からＰ（Ｍは前記第１のシ−ケンスの各要素のビット
数）番目までの複数の処理部とを有し、ｐ（２≦ｐ≦Ｍ）番目の前記処理部は、毎サイクルに、
前記第１の要素のｐ番目のビットと、当該第１の要素に
対応する第２のシ−ケンスの要素との２つの入力を受取
り、ｐ−１番目の処理部における和と前記２入力の積と
の和を出力することを特徴とする行列掛け算回路。
【請求項７】請求項６記載の行列掛け算回路であって、前記第２のステ−ジの前記１番目の処理部は、前記第２のシ−ケンスの各要素を記憶するレジスタと、前記第１のシ−ケンスの第１ビットを選択制御入力とし
て受け取り、前記第２のシ−ケンスの要素をデータ入力
として受け取り、前記第１ビットが論理１であるときに
前記第２のシ−ケンスの要素を選択し、前記第１ビット
が論理ゼロである場合に論理ゼロを選択するマルチプレ
クサと、前記マルチプレクサの出力を記憶する累積手段とを有す
ることを特徴とする行列掛け算回路。
【請求項８】請求項６記載の行列掛け算回路であって、前記ｐ番目の処理部は、前記第２のシ−ケンスの要素を記憶するレジスタと、前記第１のシ−ケンスの第ｐビットを選択制御入力とし
て受け取り、ｐ−１番目の処理部の前記レジスタよりの
前記第２のシ−ケンスの要素をデータ入力として受け取
り、前記第１ビットが論理１であるときに前記第２のシ
−ケンスの要素を選択し、前記第１ビットが論理ゼロで
ある場合に論理ゼロを選択するマルチプレクサと、累積手段とを有し、当該累積手段は、ｐ−１ビット上位にシフトした前記マ
ルチプレクサの出力とｐ−１番目の処理部の累積手段に
記憶された値との和を計算し、記憶することを特徴とす
る行列掛け算回路。
【請求項９】請求項６記載の行列掛け算回路であって、前記第２のステ−ジは、さらに、連続するサイクルにおいて、前記第１のシ−ケンスを受
け取り、当該シ−ケンスの要素の第ｐビットを、第２ス
テ−ジの各パイプライン回路のｐ番目の処理部に出力す
る、縦並びに接続された複数のレジスタを有することを
特徴とする行列掛け算回路。
【請求項１０】請求項１記載の行列掛け算回路であっ
て、前記行列Ｃは、抽出コサイン係数（ｓａｍｐｌｅｄｃ
ｏｓｉｎｅｃｏｅｆｆｉｃｉｅｎｔｓ）より成り、前
記行列Ｃは抽出コサイン係数行列Ｃの転置行列であっ
て、前記行列Ｘは変換対象の行列であることを特徴とす
る行列掛け算回路。
【請求項１１】請求項４記載の行列掛け算回路であっ
て、前記累積手段は、キャリ−保存加算回路より成ることを
特徴とする行列掛け算回路。
【請求項１２】請求項９記載の行列掛け算回路であっ
て、前記累積手段は、キャリ−保存加算回路より成ることを
特徴とする行列掛け算回路。
【請求項１３】請求項１記載の行列掛け算回路であっ
て、前記各アキュムレ−タは、前記各パイプライン回路に接続し、パイプライン回路よ
りの積を、択一的に振り分ける選択手段と、前記ｚ_lkを要素とする行列Ｚの各行につき一つ設けられ
た複数の、前記選択手段に接続した累積部とを有し、前記選択手段は、前記複数のアキュムレ−タのうちのｔ
のモジュロＬ番目の累積部を、接続したパイプライン回
路からのｔ（ｔは、接続したパイプライン回路より選択
手段に出力される積の数）番目の積を受け取れるように
選択し、当該積を振り分けることを特徴とする行列掛け
算回路。
【請求項１４】３つの行列の掛け算を行う方法であっ
て、第１の掛け算回路ステ−ジで、要素ｘ_ij（ｉ＝１．．．
Ｉ，ｊ＝１．．．Ｊ）を有する第１の行列Ｘと要素ｃ^
_jk（ｋ＝１．．．Ｋ）を有する第２の行列Ｃ^との掛け
算を行う第１のステップであって、複数の第１のパイプライン回路において、各第１のパイ
プライン回路で同時に特定のｋの値について、中間行列
の（数３）で、【数３】定義される要素を、シ−ケンシャルに生成するステップ
を含む第１のステップと、第２の掛け算回路ステ−ジで、前記第１のステ−ジより
出力される要素ｙ_ikを受け取り、要素ｙ_ikと、要素ｃ_li
を有する第３の行列Ｃとの掛け算を行う第２のステップ
であって、複数の第２のパイプライン回路において、各第２のパイ
プライン回路で、同時に、特定のｋの値について積ｃ_li
ｙ_ikをシ−ケンシャルに生成するステップを含む第２の
ステップと、パイプラインに接続してアキュムレ−タで、接続した前
記第２のパイプライン回路よりの積ｃ_liｙ_ikを、特定の
ｋの値について、（数４）で、【数４】定義される和を生成するように、選択的に累積する第３
のステップとを有することを特徴とする３行列の掛け算
方法。