JPH0226477A

JPH0226477A - 行列要素転置装置

Info

Publication number: JPH0226477A
Application number: JP63177320A
Authority: JP
Inventors: Hisataka Fujii; 寿隆藤井; Hiroshi Hamada; 浜田　博; Yoshitaka Morikawa; 良孝森川; Nobumoto Yamane; 山根　延元
Original assignee: Matsushita Electric Works Ltd
Current assignee: Panasonic Electric Works Co Ltd
Priority date: 1988-07-15
Filing date: 1988-07-15
Publication date: 1990-01-29

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】［産業上の利用分野］本発明は、画像データのように行列表現されるデータの
ブロックに対して２次元直交変換を行う行列演算器を行
変換器および列変換器とともに構成し、行変換器と列変
換器との間に挿入されて行変換器の演算結果から転置行
列を作成する行列要素転置装置に関するものである。

［従来の技術］従来より、画像データ等から冗長性を除去してデータの
圧縮を図る場合に、データを行列表現し、これに直交変
換を施す方法が知られている。画像データの圧縮に用い
られる直交変換としては、アダマール変換、カルーネン
ーレーブ変換、バール変換、離散コサイン変換、外挿予
測離散サイン変換等がある。

たとえば、Ｎ次の直交行列をΦ＝（Φ。。ｌ　（ｎ・１
．２゜−・・・、Ｎ）とするとき、この行列Φを用いて
列ベクトルｘ　＝　ｆｘ、ｌ　（ｎ＝１．２．−・−・
・、Ｎ）に１次元直交変換を施した結果の変換係数ベク
トルＸ＝（Ｘゎ）（口・１　、２　、　、、、、、。

Ｎ）は、次式で表すことができる。

Ｘ＝ΦＸ　　　　　　・・・■ 画像データを圧縮する場合には、原画像のデータな適当
な大きさのブロックに分割し、データが行列表現された
各ブロックに対して２次元直交変換を施す。２次元直交
変換は、■式を２次元に拡張したものであって、ブロッ
クが行列ｘ　＝　（ｘａｎｌ（慣・１，２．・・−１Ｍ
、ｎ・１，２．・・・・、Ｎ）で表されているとして、
直交行列Φ−（Φ、、ｌ　（ｍ□１，２．−、Ｍ）およ
びＭ／＝ｌ？、、１（ｎ・１，２．・・・−、Ｎ）を用
いることにより、次式によって変換係数行列Ｘ　＝　＋
Ｘ、。）に変換するものである。

Ｘ＝ΦｘＶ　　　　　　・・・■ ■式について検討すれば、ｘ　’１１／の演算は、行列
Ｘの各行について１次元直交変換をＭ回繰り返している
とみなすことができ、また、ΦＸの演算は、行列Ｘの各
列について１次元直交変換をＮ回繰り返しているとみな
すことができる。

このように、２次元直交変換は第１段階とじて各行ごと
の１次元直交変換を行い、第２段階として各列ごとの１
次元直交変換を行うがら（順序は逆でもよい）、第１段
階として行変換器で求めた行列に対し、この行列の転置
行列を作成し、求めた転置行列に対して第２段階として
列変換器で演算すれば、行変換器と列変換器とを同等の
構成にすることができる。このような転置行列を作成す
る手段とＬ７て、一般にトランスポートメモリと呼ばれ
る行列要素転置装置が考えられている。

従来より提供されているトランスポートメモリは、１ブ
ロック分の記憶容量を有し、第３図に示すように、行変
換器により求めた行列を一時記憶し、記憶している行列
を列方向から読み出すことにより、行と列との位置を入
れ換えるのであり、書込を行った行列に対する転置行列
として読出を行うのである。

この構成によれば、１ブロック分のデータが全部揃って
からでないと、列変換器への読出が行えないから、行変
換器と列変換器とは同時に並行動作させることができず
、処理時間が長くなるという問題がある。

この問題を解決するものとして、第４図に示すように、
２ブロック分の記憶容量をもたせる構成が考えられろく
米国特許第４，３０２，７７５号、米国特許第４，３９
４，７７４号参照）、この構成では、それぞれ１ブロッ
ク分の記憶容量を有した２個のメモリＲＡＭ　１．　Ｒ
Ａ　Ｍ　２を有し、一方が書込状態のときに、他方が読
出状態になるようにマルチプレクサＭＰＸ１〜ＭＰＸ、
で交互に切り換えるようにしているのである。各メモリ
ＲＡＭ、、ＲＡＭ、は、入力端子ＩＮ、出力端子ＯＵＴ
、アドレス端子＾ＤＤの他に、書込制御端子−Ｒと読出
制御端子ＲＤとを備えている。

入力端子ＩＮには、行変換器の演算結果が入力され、出
力端子ＯＵＴからは列変換器への出力が取り出される。

書込制御端子−Ｒには、マルチプレクサＭＰ×１を介し
て書込信号ＷＲＩＴＥが入力され、読出制御端子ＲＤに
は、マルチプレクサＭＰＸ２を介して読出信号ＲＥＡＤ
が入力される。さらに、各メモリＲＡＭ、、ＲＡＭ２の
アドレス端子へ〇〇には、それぞれマルチプレクサＭＰ
Ｘ、、ＭＰＸ、を介して行アドレス発生回路ＨＡＤＤと
列アドレス発生回路ＶＡＤＤとが接続される。各マルチ
プレクサＭＰＸ、〜ＭＰＸ、は、セレクト信号ＳＥＬに
より切り換えられ、一方ノメモリＲＡ　Ｍ　＋　（ＲＡ
　Ｍ　２　）に書込信号ＷＲＩＴＥが入力される状態で
は、他方のメモリＲＡ　Ｍ　２　（ＲＡＭ、）に読出信
号ＲＥＡＤが入力され、書込信号−ＲＡＴＥが入力され
ているメモリＲＡ　Ｍ　Ｌ　（ＲＡ　Ｍ　２　）に行ア
ドレス発生回路ＨＡＤＤが接続され、浸出信号ＲＥＡＤ
が入力されているメモリＲＡ　Ｍ　２　（ＲＡ　Ｍ　ｌ
）に列アドレス発生回路ＶＡＤＤが接続されるのである
。

以上のようにして、各メモリＲＡＭ、、ＲＡＭ。

に対し、行方向への書込が行われ、列方向からの読出が
行われるのである。また、異なるメモリＲＡ　Ｍ　＋　
、　ＲＡ　Ｍ　２に対して書込と読出とが同時に行われ
るから、行変換器と列変換器とは同時に並列動作させる
ことができるのであり、ブロックが正方行列で行変換器
と列変換器とが同じ動作速度を有していれば、空き時間
がなく効率よく処理できることになる。

［発明が解決しようとする課題］上記構成では、処理時間は短縮されるが、メモリが２ブ
ロック分必要であり、また、マルチプレクサもデータや
アドレスのビット数に比例した数が必要であるから、ハ
ードウェアの規模が大きくなるという問題を有していた
。

本発明は上記問題点を解決することを目的とするもので
あり、ハードウェアの規模が比較的小さく、しかも、比
較的高速な処理が行えるようにした行列要素転置装置を
提供しようとするものである。

［課題を解決するための手段］本発明では、上記目的を達成するために、行変換器の出
力の１ブロック分の演算結果を記憶できる容量を有した
記憶部と、１ブロック分を処理する毎に記憶部への書込
方向を行方向と列方向とに交互に切り換える入力制御部
と、１ブロック分を処理する毎に記憶部からの読出方向
を行方向と列方向とに交互に切り換える出力制御部と、
入力制御部を介して行方向と列方向とのいずれか一方向
で書込をしたデータを出力制御部を介して他方向で読出
をするとともに、読出が終了した領域に入力制御部を介
して上記他方向から書込を行うように制御する全体制御
部とを備えるのである。

［作用］本発明は、第３図に示した従来構成において、行変換器
の結果の書込時に、これからデータの書込を行う領域が
空き領域となり、また、列変換器による読出時に、すで
にデータの読出が終了した領域が空き領域となる点に着
目してなされており、上記構成により、列変換器による
読出が終了して空いた領域に行変換器の演算結果を順次
書き込むから、記憶領域の利用にむだがなく、パイプラ
イン処理が可能になって、高速動作が期待できるのであ
る。

［実施例］本実施例では、処理すべきブロックサイズが４×４であ
る場合を例示するが、ブロックサイズについてなんら制
限を加えるものではない、また、ブロックが正方行列で
はない場合、行数と列数とのうちいずれか大きい方の値
の次数を有した正方行列が記憶可能な容量にする。たと
えば、処理すべきブロックのサイズがＭＸＮであって、
Ｍ＞Ｎならば、ＭＸＭ行列が記憶できる容量を有するよ
うに設定する。

行変換器および列変換器は１０ビツトのデータを演算す
る能力があり、行変換器の出力データは、１０ビツトシ
リアルになっている。また、行変換器において１行分の
４個のデータに関しては並行処理され、行変換器から出
力される１行分の４個のデータは記憶部１１に同時に入
力されるようになっている。

記憶部１１は、１０ビツトシフトレジスタを、第１１１
］に示すように、１６個並べて構成されており、各シフ
トレジスタ１１　ｚ（ｉ、ｊ４，２，３．４）の対で特
定される。記憶部１１の前後にはそれぞれ入力制御部１
．２と出力制御部１３が設けられており、また、各シフ
トレジスタ１１４．は、外部から入力されるシフト信号
が１になっている期間にクロック信号ＣＬＱＣＫに同期
してデータをシフトさせるようになっている。このシフ
ト信号は、全体制御部１４により発生する。全体制御部
１４は、カウンタ部１５の出力によりクロック信号ＣＬ
ＯＣＫに同期するのであり、カウンタ部１５は、クロッ
ク信号ＣＬＯＣＫを１０分周する分周器１６と、分周器
１６の出力をカウントする２ビツトカウンタ１７とで構
成される。

モード信号ＭＯＤＥは、記憶部１１に対する読み書きを
行方向で行うか列方向で行うかを設定する。

すなわち、モード信号ＭＯＤＥが１のときには、行変換
器の４個の出力のうち第１の入力端ＩＮ、に入力される
データは、シフトレジスタ１１．、（ｉ・１，２，３゜
４）のいずれかに入力されるように設定され、他の入力
端ＩＮ２〜ＩＮ、も同様に、対応する各列のいずれかの
シフトレジスタ１１１２〜１１１．に入力されるように
設定される。モード信号ＭＯＤＥが０となると、各入力
端ＩＮ、〜ＩＮ、へのデータは、それぞれ対応する各行
のいずれかのシフトレジスタ１１．ｊ〜１１４Ｊ（Ｊ・
１，２，３．４）に入力されることになる。っまり−モ
ード信号ＭＯＤＥが１のときには、行を指定すれば記憶
部１１の行方向における１行分のデータを記憶すること
ができ、モード信号ＭＯＤＥが０のときには、列を指定
すれば記憶部１１の列方向における１列分のデータを記
憶することができるのである。

モード信号ＭＯＤＥが１のときの行指定、およびモード
信号ＭＯＤＥが０のときの列指定は、全体制御部１４に
より行われる。すなわち、２ビツトカウンタ１７の一方
の両出力端Ｑ、、Ｑ、は４状態を取り得るのであって、
出力値がＯＯのときに、モード信号ＭＯＤＥが１である
とすれば、第１行のシフトレジスタ１１１Ｊにシフト信
号が入力されるから、結局、記憶部１１の第１行にデー
タが書き込まれることになる。ここに、各シフトレジス
タ１１．Ｊは、それぞれ１０ビツトを有しているから、
クロック信号ＣＬＯＣＫが１０個出される間、シフト信
号は同じ状態に保たれる。この状態はクロック信号ＣＬ
ＯＣＫを１０分の１に分周する分周器１６により実現さ
れている。２ビツトカウンタ１７の出力が同じで、モー
ド信号ＭＯＤＥが０のときには、全体制御部１４が記憶
部１１の第１列のシフトレジスタ１１１．を指定するか
ら、入力制御部１２の設定と合わせると、第１列のシフ
トレジスタ１１□１にデータの書込が行われることにな
る。モード信号ＭＯＤＥと、２ビツトカウンタ１７の出
力Ｑｏ、Ｑ、とを組み合わせると、記憶部１１は次表の
ように指定される。

一方、出力制御部１３は、４対１のマルチプレクサが８
個、２対１のマルチプレクサが４個で構成されている。

出力制御部１３は、全体制御部１４と同様に、モード信
号ＭＯＤＥと２ビツトカウンタ１７の出力とにより制御
されるのであって、モード信号ＭＯＤＥにより２対１の
マルチプレクサが制御され、２ビツトカウンタ１７の出
力により４対１のマルチプレクサが制御されている。４
対１のマルチプレクサの入力端を第１図中の上から入力
端をＡ、Ｂ、Ｃ，Ｄとずれば、２ビツトカウンタ１７の
出力値のＯＯ→１１に対応して、Ａ→Ｄとなるように設
定されている。また、２対１のマルチプレクサについて
は、第１図中の上から入力端Ａ。

Ｂとすれば、モード信号ＭＯＤＥが１のときにＡ、モー
ド信号ＭＯＤＥが０のときにＢが選択されるようになっ
ている。したがって、２ビツトカウンタ１７の出力値が
００であれば、記憶部１１の第１行または第１列からの
読出が可能となっており、さらに、モード信号ＭＯＤＥ
が１であれば、第１行、モード信号ＭＯＤＥが０であれ
ば、第１列が選択され、出力端ＯＵＴ、〜０ＩＩＴ、か
らデータの読出が行われるのである。つまり、上表と同
じ選択が行われるのである。

以上の動作をまとめると、まず、第２図（ａ）のように
、記憶部１１の第１行が選択されているとすると、各シ
フトレジスタ１１１１〜１１１４に対して同時にデータ
の書込が行われる。このとき、読出も行われるが、初め
は記憶部１１に有効なデータが記憶されていないから無
視される。１０個のクロック信号ＣＬＯＣＫにより第１
行のデータの書込が終了すると、２ビツトカウンタ１７
の出力が０１になり、第２図（ｂ）のように第２行のデ
ータの書込が行われる。こうして、第４行までデータの
書込が終了すると、モード信号ＭＯＤＥが切り換えられ
、第２図（ｃ）のように第１列が選択され、書込と同時
に読出が行われる。こうして、第２図（ｄ）のように第
４列までの書込が終了すると、第２図（ｅ）のように、
再び第１行が選択される。ここに、行方向の選択状態で
データが書き込まれた部位を斜線で示している。このよ
うにして、行方向で書込を行ったデータに対して列方向
での読出を行うから、行変換器１で（ｉ、ｊ）として出
力された行列要素は、列変換器２では（ｊ、ｉ）の行列
要素として読出を行うことになり、転置行列を得ること
になるのである。また、書込と読出とが同時に行われて
いるから、行変換器１と列変換器２とが同時に動作し、
並行処理が可能となってパイプライン化できるのである
。すなわち、１ブロック分の記憶容量で、高速な処理が
可能となるのである。

［発明の効果］本発明は上述のように、行変換器の出力の１ブロック分
の演算結果を記憶できる容量を有した記憶部と、１ブロ
ック分を処理する毎に記憶部への書込方向を行方向と列
方向とに交互に切り換える入力制御部と、１ブロック分
を処理する毎に記憶部からの読出方向を行方向と列方向
とに交互に切り換える出力制御部と、入力制御部を介し
て行方向と列方向とのいずれか一方向で書込をしたデー
タを出力制御部を介して他方向で読出をするとともに、
読出が終了した領域に入力制御部を介してト記他方向か
ら書込を行うように制御する全体制御部とを備えている
ものであり、列変換器による浸出が終了して空いている
領域に行変換器の演算結果を順次書き込むから、記憶領
域の利用にむだがなく、１ブロック分程度の記憶容量が
あれば、パイプライン処理が可能になって、高速動作が
期待できるのである。さらに、記憶部がシフトレジスタ
で構成されているから、シリアルビットスライス構成が
実現でき、ハードウェアの規模が縮小されるという利点
もある。

【図面の簡単な説明】

第１図は本発明の実施例を示す回路図、第２図（ａ）〜
（ｅ）は同上の動作説明図、第３図（ａ）（ｂ）は本発
明に係る行列要素転置装置の動作原理説明図、第４図は
従来例を示すブロック図である。１・・・記憶部、２・・・アドレスカウンタ、３，４・
・・マルチプレクサ、５・・・入力デコーダ、１１・・
・記憶部、１１＋ｔ〜１１４４・・・シフトレジスタ、
１２・・・入力制御部、１３・・・出力制御部、１４・
・・シフト信号発生部、１５・・・全体制御部、２１・
・・行変換器、２２・・・列変換器。代理人　弁理士　石　１）長　七第２図（ａ）第２図（ｅ）第２図（Ｃ）第３図（ａ）（ｂ） ■ り′Ｊ引尭益へ

Claims

【特許請求の範囲】

（１）行列表現されるデータのブロックに対して２次元
直交変換を行う行列演算器を行変換器および列変換器と
ともに構成し、行変換器と列変換器との間に挿入されて
行変換器の演算結果から転置行列を作成する行列要素転
置装置において、行変換器の出力の１ブロック分の演算
結果を記憶できる容量を有し各行列要素をそれぞれ記憶
する複数個のシフトレジスタよりなる記憶部と、１ブロ
ック分を処理する毎に記憶部への書込方向を行方向と列
方向とに交互に切り換える入力制御部と、１ブロック分
を処理する毎に記憶部からの読出方向を行方向と列方向
とに交互に切り換える出力制御部と、入力制御部を介し
て行方向と列方向とのいずれか一方向で書込をしたデー
タを出力制御部を介して他方向で読出をするとともに、
読出が終了した領域に入力制御部を介して上記他方向か
ら書込を行うように制御する全体制御部とを具備して成
ることを特徴とする行列要素転置装置。