JPH0226476A

JPH0226476A - 行列要素転置装置

Info

Publication number: JPH0226476A
Application number: JP63177319A
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

【特許請求の範囲】

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