JPH03214269A - ２次元配列データ回転機構 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、メモリのアクセスデータ数（データ語長が１
ビットの場合はデータ幅に等価）の拡大によって，高性
能化なけかる画偉処理装置．ノ冫ターン認識装置等にお
いて，コンパクトでかつ高速な２次元配列データの９０
度回転機構を実現する技術に関するものである． ［従来の技術］ メモリに格納されている２次元配列データを，高速に９
０度の整数倍回転する方法としては縦と横がメモリから
一度Ｋアクセスするデータ数Ｋ等しいサブ２次元配列デ
ータの行と列の間を変換する９０度回転器を用いる方法
が知られている（例えば，各データの語長が１ビットの
２次元配列データ（ビットプレーン）を扱う場合につい
てＦｉａ願昭５９−１７０８６３号［イメージ回転処理
方式］参照）． この方法を利用したビットプレーン用の回転機構の一例
の概略ブロック図を第２図に示す。ここで，ＩＦｉＷｘ
Ｗのサブビットプレーン用の９０度回転器．２００はア
クセス幅が１ビットのランダムアクセスメモリ（　ＲＡ
Ｍ　）ユニット２のＷ個からなるＲＡＭユニット配列（
いわゆるＷビット幅のメモリ），３は制御部．４は幅が
Ｗビットのデータバスである。メモリ内の被回転ピット
プレーンをＷｘＷのサブピットデレーンで切り出して，
一旦９０度回転器に行単位で読みだし，その回転結果を
列単位で適当なアドレスに張シ込むことによク，回転後
のピット！レーンをメモリ内に形成するものである。

第３図は，この手順なＷが３の場合について図示したも
のである。図の（ｉ）は被回転ビットデレーンであり、
図の（ｂ）の左側のような形で．ＲＡＭユニット配列２
の中Ｋ格納される。このピットプレーンの格納イメージ
の枠から９０度回転器に向かう矢印は．ＲＡＭユニット
配列から３ピット長のワード単位Ｋ読みだしたデータを
３×３のサブピットプレーンの行として，９０度回転器
に順次入力する様子を示している。この時適当なアドレ
スを順次与えることによって，３×３のサブピットデレ
ーンが，゛図示するように９０度回転器内に形成される
。一方，９０度回転器から，右側のメモリ格納イメージ
に向かう矢印は．９０度回転器内の３×３のサブビット
プレーンの列を順に取シ出し３ピット長のワードとして
、ＲＡＭユニット配列内に再格納する様子を示している
。この再格納された配列データは図の（ｃｌのピットプ
レーンを表しており．ちょうどこれは，被回転ビットプ
レーンを反時計方向に９０度回転したものとなっている
．ところでこの従来例での，サブビットデレーン当たり
の９０度回転の所要時間は，　ＲＡＭユニット配列から
の１ワードのアクセスを１単位時間で，ＲＡＭユニット
配列と９０度回転器間の入出力をＲＡＭユニット配列の
アクセスと並行して行なえるとすると，２Ｗ単位時間と
なる。

［発明が解決しようとする課題コ この方法では，　ＲＡＭユニット配列から一度にアクセ
スするデータ数と回転器の入出力のデータ数とは同一で
あり，この両方をともに太き〈しなければ，回転速度の
向上は望めない。この場合，ＲＡＭユニット配列からの
アクセスデータ数は，メモＩＪ　Ｉ　Ｃを並列に並べる
ことＫより比較的容易に拡張できる。しかし．回転器の
入出力データ数は，入出力データ数の２乗に比例して大
きくなるノ・一ドウェア量がネックとなり，容易に拡張
できない問題点があった。

本発明の目的は，　ＲＡＭユニット配列から一度にアク
セスするデータ数を拡大しても，ハードウェア量１４り
増大させることのない高速の２次元配列データ回転機構
を提供することにある。

〕Ｉを解決ナるための手段と作Ｆ！！］本発明は上記目
的を達成するために．全体で同一のアドレスをアクセス
する手段と行ごとＫ互いに異なるアドレスをアクセスす
る手段とな兼備する行列状に配列した記憶ユニットと．
２次元配列データを行単位に置換する手段と，２次元配
列データを９０度の奇数倍回転する手段とを合わせ持つ
ことを特徴とするものである。

本発明は，回転対象のサブ２次元データ配列のＮ（Ｎは
２以上の整数）行分（あるいけＮ列分）のデータな記憶
ユニット配列から−闇にアクセスすることを最大の特徴
とする。一度に１行分（あるいは１列分）のデータしか
アクセスしない従来方式に比べると，記憶ユニット配列
からのアクセスデータ数が同一の場合．回転対象のサブ
２次元データ配列の行のサイズすなわち９０度回転器の
一辺のサイズが１ハ・にできるために９０ｆ回転器のハ
ードウエア量を大きく低減できる。ここで，回転前のサ
ブ２次元配列データと回転後のサブ２次元配列データは
．いずれも記憶ユニット配列な２次元の配列と見なした
場合のある１行（あるいは列）の記憶ユニットに格納さ
れる。従って，これらのＮ行（あるいはＮ列）は，記憶
ユニット配列の１行（あるいは列）に属する記憶ユニッ
トに格納される状態から効率良くアクセスできる必要が
ある．このために，記憶ユニット配列の１行に格納され
るサブ２次元配列データのＮ行分を記憶ユニット配列全
体に分散させたりあるいはその逆？行なうことな目的と
した記憶ユニット配列の行ごとにアクセスされる配列デ
ータ間で相互に置換する手段と記憶ユニット配列の各行
ごとに互いに異なるアドレスからアクセスする手段な備
える点が本発明の構成上の特徴である。なお，さぎのＮ
行（あるいけＮ列）Ｆｉ．一つの回転対象のサブ２次元
配列データに属する珈合と複数の回転対象のサブ２次元
配列データに属する場合がある。以下，１つの回転対象
の全行を一度にアクセスする場合（Ｎ＝Ｗの場合）の実
施例から順に説明する。

［実施例コ 第１図は本発明のｔＪ．１の実施例のブロック構成を示
した図であり，１は９０度回転器，２０〜ｚ　ｓ　１２
　ＲＡＭ　ユ＝ット，ｓｏＦｉ行間のデータの置換？行
なうためのスイッチングネットワーク．５ｂ５ｃｔｉア
ドレス修飾器，６はアト゜レス信号入力端子，７はアド
レス修飾器を修飾モードと非修飾モードの間で切り換え
るための制御入力端子，８け９０度回転器Ｊ，スイッチ
ングネットワークＳＯ．ＲＡＭユニット２０〜２８間ケ
結ぶ，パスである。

アドレス修飾器５ｂ　，５ｅけ，特許請求の範囲でいう
全体で同一のアドレスと行ごとに異なるアドレスを発生
するための手段であり，非修飾モードでは入力？そのま
ま出力し，修飾モート゜では入力信号な次のように修飾
して出力する。

５ｂのアドレス修飾器：ｏｕｒ　＝Ａ＋１−｛３［Ａ＋
１／３］−３［Ａ／３］｝・・・・・〈１） ５ｃのアドレス修飾器：　ＯＵＴ　＝Ａ＋２−（３「Ａ
＋２／３コー３［＆３］）・・・・・｛２） ここで．　ＯＵＴは出力のアドレス信号値，人け入力の
アドレス信号値，［］けガウス記号である。第４図は，
９０度回転器ｌの構成を示しており、１０ケ基本の回転
エレメント．１）ｔ’ｉマスタスレイプ型のＤ−ＦＦ．
　　ノ２ｉｊ｝ライステートノぐクファ，１３はセレク
タである。第５図はスイッチングネットワーク３０の構
成図であり，３ノはローテート可能なシフタ，３２けパ
ス８につながる入出力端子である一 次に第６図のように２０〜２８のＲＡＭユニット配列の
ＡからＡ＋１番地に格納されたＯＯから８８までの２次
元配列データを本実施例によって回転ナる手順について
ステップ？追って貌明する。

◎ステノデ１ アドレス修飾器５ｂ　，５ｃを非修飾モードとして、２
（Ｉ−２１１のＲＡＭユニット配列のＡ＋１．Ａ＋４．
Ａ＋７ｉＩ地のデータをスイッチングネットワーク３０
に読みだし．行単位で距離】だけ紙面の奥の方向から手
前に向かってローテートシフトし結果をＤ＋ｌ　．Ｄ＋
４　ｔ　Ｄ＋７番地に格納することを順に行なう。２０
〜２８のＲＡＭユニクト配列のＡ＋２番地、Ａ＋５番地
，Ａ＋８番地のデータについてもスイッチングネットワ
ーク３０に読みだして，行単位で同方向Ｋ距離２だけロ
ーテートシフトし結果をＤ＋２，Ｄ＋５　，Ｄ＋８番地
に格納することを順に行なう。Ａ　，　Ａ＋３　，　Ａ
＋６番地については、そのまま，Ｄ，Ｄ＋３，Ｄ＋６番
地に転送する。その結果．２０〜２８のＲＡＭユニット
配列内のＤ−Ｄ＋８番地に．第７図に示す２次元配列デ
ータが得られる。

◎ステッデ２ アト゜レス修飾器５ｂ．５ｃを修飾モードに設定し、２
０〜２８のアト゜レス修飾器の入力にＤを加えて、２０
〜２８のＲＡＭユニット配列からデータを９０度回転器
ｌに読みだ寸，．ＲＡＭユニット２０，２１．２２Ｋ対
しては入力Ｄがそのままアドレスとして加わるため，Ｄ
番地がアクセスされるが、ＲＡＭユニットの２３ｔ２４
．２５および２６，２７，２１３についてはアドレス修
飾器５ｂ，５ｃを介してアドレスが供給されるために．
入力Ｄが修飾され．それぞれＤ＋１とＤ＋２がアドレス
としてＷわり，Ｄ＋１番地とＤ＋２番地がアクセスされ
る。結果として，もともと２０〜２８のＲＡＭユニット
配列内に格納されていたサブ２次元配列が１次元配列に
展開された形で一回のアクセスで読みだされ．第８図ｆ
ａ）のサブ２次元配列として９０度回転器１に格納され
る。なお．９０度回転器Ｊへの格納は、第４図のセレク
タ１３をＲＡＭユニット２０〜２８からの入力を選ぶよ
う設定することで行なえる・ ◎ステップ３ このサブ２次元配列を，９０度回転器１のセレクタ１３
を左側の他の回転エレメントからの入力な選ぶことによ
り，第８図の（ｂ）に示すように時計方向に９０度回転
する。

◎ステッデ４ この９０度回転したサブ２次元配列データな，バス８を
介してスイッチングネットワーク３０に転送し、行単位
で紙面の奥から手前に向かって距離１だけローテートシ
フトし，アドレス修飾器５ｂ．５ｃを修飾モード、入力
アト゜レスｔＢ＋２として，第９図（ａｌのように格納
する。

◎ステップ５ ステップ２ｆｆ入カアドレスをＤ＋３として繰り返す。

結果として第１０図（轟）のサブ２次元配列が９０度回
転器７Ｋ読みだされる。

◎ステップ６ ステップ３と同様の処理を行ない，第ｌＯ図（ｂｌのよ
うに回転する。

◎ステップ７ この９０度回転したサブ２次元配列データを，パス８な
介して、アドレス修飾器５ｂ＋５ｃを修飾モード，入力
アドレスなＢとして，第９図（ｂ１のように２０〜２８
のＲＡＭユニット配列に格納する。

◎ステッデ８ ステップ２な人カアドレスをＤ＋６として繰り返す。結
果として第１１図（１）のサブ２次元配列が９０度回転
器７Ｋ読みだされる。

◎ステッデ９ ステップ３と同梯の処理を行ない、第１１図（ｂｌのよ
うに回転する。

◎ステッデ１０ この９０度回転したサブ２次元配列データを，パス８を
介してスイッチングネットワーク３０に転送し，行単位
で距離１だけステップ４とは逆方向にローテートシフト
し，アドレス修飾器ｓｂ．５ｃを修飾モート９，入カア
ドレスをＢ＋１として、第９図１ｃｌのように格納する
。

◎ステッデＩノ 第９図（ｃ）の結果な，スイッチングネットワーク３０
を用いて，行単位に列方向にローテートシフトシ，結果
をＣからＣ＋２番地に格納する。その結果が、第９図（
ｄｔである。これは元の２次元配列データの左側３列が
時計方向に９０度回転された形である。ここまでのステ
ッ＋′２から１１を繰リ返すことで，００から８８の２
次元配列データ全体を時計方向に９０度回転することが
できる。この際．回転対象の列と結果の格納先が変わる
のに応じて．ａみだしアドレス，書き込みアドレス，シ
フト量等は適宜変更される必要がある、本実施例でのＷ
ｘＷのサブビットプレーン当たりの回転所要時間は，２
０〜２８の副ユニット配列から回転器１あるいはスイッ
チングネットワーク３０に対するアクセス所要時間を１
単位時間，スイッチングネットワーク３０での任意量の
ローテートシフトを１単位時間，９０度回転器１での９
０度回転を１単位時間，スイッチングネットワーク３０
・回転器Ｊ開の転送の所！時間を１単位時間とすると，
ステッデ１で３単位時間，ステンｆ２　，　５　．　８
で１単位時間、ステップ３．６．９で１単位時間，ステ
ップ４，７．１０で３単位時間，ステン７′１ノで３単
位時間となり，全体で１１単位時間となる。この所要時
間は短いとは言えないが，これはパイプライン的な処理
機構を導入することで解決可能である。

第３０図は，その実現例の一つである本発明の第２の実
施例を示している。ここで，１′は入出力の方向を上方
向でも下方向でも設定可能な双方回の９０度回転器．３
０社双方向のスイッチングネットワーク，９０〜９８は
もう一つのＲＡＭユニット．９９はもう一つのアドレス
信号入力端子Ｊ８＃−１　ＲＡＭユニット２０〜２８と
スイッチングネットワーク３０′の開を結ぶパス，８８
′はスイッチングネットワークｓ　ｏｌと９０度回転器
１′の間を結ぶパス．８８竹９０度回転器１′とＲＡＭ
ユニット９０〜９８の間を結ぶパスである。本実施例の
動作は基本酌に第１の実施例と同じである。違いは，Ａ
〜Ａ＋８番地とＣ−Ｃ＋Ｓ番地を９０〜９８のＲＡＭユ
ニット配列に割付け．回転処理の各々をＲＡＭユニノト
ＭＰ列の２０〜２８と９０〜９８の間な往復する間に行
なうようにする点である．９０度回転器１′における回
転処理，スイッチングネットワーク３０Ｑｌｃおケルロ
ーテートシフ｝．ＲＡＭユニット２０〜２８と９０〜９
８の読みだしと書き込みの任意の組み合わせが１単位時
間で実行できれば．あるいはこれが不可能でも，各処理
をパイデラインの一段ずつに割り当てて・ぞイプライ／
処理を行ない等価的に１麺位時間で実行すれば、先の所
要時間は大きく低減される。′ｆなわち，ステップの１
お・よび４は．　ＲＡＭユニット配列９０〜９８から，
ＲＡＭユニット配列２０〜２８に向かう処理としてそれ
ぞれ１単位時間で，ステッデ２，３および１ｚｌ′ｉＲ
ＡＭユニット配列２０〜２８から．　ＲＡＭユニット配
列９０〜９８に向かう処理としてそれぞれ１単位時間で
実行できる。従って，全体の所要時間は４単位時間とな
る。

Ｗ．１２図は本発明の第３の実施例のブロック構成図で
あり，２０〜Ｚ８はＲＡＭユニット，４０〜４８はシフ
トレジスタ，６竹アドレス信号入力端子，７′はシフト
レジスタ制御信号入力端子，９は２次元シフトユニット
制御信号入力端子，１０′は２次元シフトエレメント，
８′はシフトレジスタ４０〜イ８．ＲＡ１１１ユニット
２０〜２８、２次元シフトエレメントｉ　ｏ’間を結ぶ
バスである。２次元シフトエレメント１　０’の３×３
の配列と隣接エレメント間の接続ノソス全体でスイッチ
ングネットワークと９０度回転器な兼ねる２次元シフト
ユニットな構成する。第１３図の（ｍｌ　，　（ｂ）　
，（ｃｌは、それぞれ，４０〜４２．４３〜４５　．４
６〜４８のシフトレジスタの内部檜成を示ナブロック樽
成図であり，５Ｊ，５２はセレクタ，５３，５４．５５
はマスタスレイプ型のＤ−ＦＦ．５６はデータ入力端子
，５７はデータ出力端子である。Ｄ−　ＦＦ５５の出力
はセレクタ５１にフィート０バックされており，５３〜
５５のデータけローテートシ７トナることが可能である
（ローテート可能なシフトレジスタ）。なお．第１３図
の（轟１　，　（ｂｌ　，　（ｃｌのシフトレジスタ間
の違いは，セレクタ５２に対する入力のパスが異なる点
である。これによって行単位で一段ずつずれたアドレス
から出力することができる。従って，本実施例ではこの
シフトレジスタの配列が．％．＊請求の範囲でいう全体
で同一のアドレスのアクセスと行ごとに異なるアドレス
のアクセスの両方を行なう手段な有する記憶ユニット配
列となる。第１４図は，２次元シフトエレメントＪＯ′
のブロック構成を示した図であｌ），Ｊｘ，１１′はマ
スタスレイプ型のＤ−ＦＦ．１２はトライステートノぐ
ツファ，１３’，１３”は入カセレクタ，ノ５．１６，
１７．１８はそれぞれ，紙面に関して奥行き側，手前側
，右側，左側の隣接エレメントとの間を結ぶための入出
力端子，１９はバス８／に対する入出力端子である。

次に先の第１の実施例の場合と同様に，第６図のように
２０〜２８のＲＡＭユニット配列のＡからＡ＋１番地に
格納されたＯＯ〜８８までの２次元配列データな時計方
向に９０度回転する手順についてステップを追って説明
する。

◎ステップ１ ２０〜２８のＲＡＭユニット配列のＡ＋１番地，Ａ＋４
番地，Ａ＋７番地のデータを，２次元シフトユニットに
読みだし（２次元シフトエレメント７（７／のセレクタ
１３′ケパス８′からの入力を選ぶように設定し、列方
向のシフト機能を利用して，紙面の奥から手前に向かっ
て行単位に１だけローテートシ７トし結果を元の番地に
戻すことを順に行なう。２０〜２８のＲＡＭユニット配
列のＡ＋２番地，Ａ＋５番地、Ａ＋８番地についても２
次元シフトユニットに読みだし，同方向に行単位で２（
逆方向に１でもよい）ローテートシフトし結果を元の番
地に戻すことな順に行なう。その結果は先の第１の実施
例の第７図に示ナようになる。ただし，この場合にはア
ドレスはＤではなくＡのままである。ここで，２次元シ
フトユニットにおける行方向のシフトは、２次元シフト
エレメントＪ（）／で端子１５を入力に，端子１７を出
力Ｋ，セレクタ１３′を端子１５からの入力を選択する
ように設定することで実現される。

◎ステッデ２ シフトレジスタ４０〜４８のセレクタ５ノをパス８′か
らの入力を選択するよう設定し，２０〜２８のＲＡＭユ
ニット配列のＡ番地からＡ＋２番地着で順次，シフトレ
ゾスタ配列に読みだす。その結果、各シフトレジスタ４
０〜４８のＤ−ＦＦ５３〜５５の内容の配列は第１５図
に示すとおりとなる。

◎ステッｆ３ 〔サブステッデＪ〕 シフトレジスタユニットの入カセレクタ５ノは左側の入
力を，出力セレクタ５２は右側からの入力を選択するよ
う設定し，シフトレジスタ４０〜４８内でローテートシ
フトを行ないながら２次元シフトユニットに読みだナ。

この読みだしは，２次元シフトユニットの各２次元シフ
トエレメントｌＯ′でパス８′からの入力シ取り込むよ
うにセレクタ１　３’を設定することで行なえる。この
結果，２次元シフトユニットのＤ−ＦＦＭ１の配列には
、初めに第８図（ａｌのデータ配列が入る。

〔サブステッデ２〕 このデータ配列を列方向のシフトユニット？用いて手前
から奥に向かって行単位でシフトナるとともに、そのシ
フトデータな行方向のシフト転送系に逐一取り込み，右
から左方向に向かって列単位でシフト転送することによ
って，時計方向に９０度回転した結果（第８図（ｂ））
を，シフト転送ユニットのＤ−ＦＦＩＩ’の配列に得る
。この回転結果をＲＡＭユニット２０〜２８のＣ番地に
格納する。ここで、２次元シフトユニットにおける右か
ら左に向かう行方向のシフトは，２次元シフトエレメン
ト１０′の入出力端子１６を入力に，入出力端子ｌ８を
出力に，セレクタＩ　Ｊ”を端子Ｊ６からの入力を選ぶ
ように設定することによって実籾できる。この際、右端
の２次元シフトエレメントＪ　Ｏ’には２同時に行なわ
れている列方向のシフトデータが順次入るようパスが接
続されているので，列・行方向同時のシフト転送を３回
繰り返すことで，時計方向の９０度回転を実現すること
ができる。

〔サブステッ−ｙ’　３　） サブステッデ１と同様の処理な行なう。この場合，Ｄ−
ＦＦＩＩに読みだされるデータは，第１６図（ａ）のよ
うに列方向にシフトがかかった形になっている。この場
合には逆方向に１回シフトし第１６図ｆｂ）のような正
規のサブ２次元配列を得る。

〔サブステッデ４〕 サブステッデ２と同様の処理を行なう。ただし格納先は
Ｃ＋１番地とする。

〔サブステップ５〕 サプステッ′７″３と同様の処理な行なう。

［サブステッｆ６］ サブステップ２と同様の処理を行なう。ただし，格納先
けＣ＋２番地と干る。

以上により，第６図のＡからＡ＋２番地のデータ配列は
第１７図ＣからＣ＋２番地のように変換される。

◎ステップ４ ステッデ２と同様の処理を行なう。ただし，読みだしア
ト゛レスけＡ＋３〜Ａ＋５番地とする。

◎ステッデ５ ステッデ３と同様の処理を行なう。ただし，書き込みア
ドレスけＣ＋３〜ｃ＋５番地とする。結果は、第１７図
Ｃ＋３〜Ｃ＋５番地のようになる。

◎ステッデ６ ステッ＋′２と同様の処理な行なう。ただし，読みだし
アドレスはＡ＋６〜Ａ＋８番地とする。

◎ステッデ７ ステッデ３と同様の処理な行なう。ただし、省き込みア
ドレスけＣ＋６〜Ｃ＋８番地とする。結果は、第１７図
Ｃ＋６〜Ｃ＋８番地のようになる。

ｆｔ５）ステップ８ ２０〜２８のＲＡＭユニット配列のＣ−Ｃ＋２番地のデ
ータを２次元シフトユニットに鯖．みだし，列方向のシ
フト機能を利用して，紙面の奥から手前に向かって行単
位に２（逆方向に１でもよい）ローテートシフトし結果
な元の番地に戻すことを順に行なう。２０〜２８のＲＡ
Ｍユニット配列のＣ＋３〜Ｃ＋５番地についても２次元
シフトユニットに読みだし，同方向に行単位で１だけロ
ーテートシフトし２結果な元の番地に戻すことを順に行
なう。その結果は第１８図に示すとおりとなる。

◎ステップ９ シフトレジスタのセレクタ５ノをパス８′からの入力を
選択するよう設定し，２０〜２８のＲＡＭユニット配列
のＣ＋５，Ｃ＋３，Ｃ番地の順次，４０〜４８のシフト
レジスタ配列に読みだす。結果は第１９に示すとおりと
なる。

（Ｑ）ステップ１０ シフトレ・クスタユニットの入力セレクタ５１は左側の
入力？．出力セレクタ５２は右側からの入力ケ選択する
よう設定し，シフトレジスタ４０〜４８内でローテート
シフトを行ないながら２次元シフトユニットに読みだす
。この結果，２次元シ７ｈユニットのＤ−ＦＦＩＩの配
列には，第２０図（ａ）　＊　（ｂｌ　ｅ　（ｃ）のデ
ータ配列が順次読みだされる。

第２０図（１）についてはそのまｉ　ＲＡＭユニット２
０〜２８のＢ番地に，第２０図（ｂ）　，　（ｃ）につ
いてはシフトがかかっているので．２次元シフトユニッ
トの列方向のシフト機能を利用して．正規の形に戻して
から、１３＋ｌ　，Ｂ＋２番地に格納する。この結果は
ちょうど第６図の左側３列が時計方向に９０度回転した
第９図（ｄｌとなる。ステッデ９．１０を，Ｃ＋３〜Ｃ
＋５およびＣ＋６〜Ｃ＋８番地のデータに対し繰り返す
ことで第６図の２次元配列データの全体に対する９０度
回転データを得ることができる。

本発明の第１ｌ第２および第３の実施例では、ＲＡＭユ
ニット２０〜２８内に格納された２次元配列データを１
次元配列データに展開する際に，実効的に１，２式のよ
うなアドレスの修飾ケ．行単位の置換としてローテート
シフトナ，それぞれ用いている。しかし，サブ２次元配
列データの１次元配列デー，夕への展開は．２次元アド
レスアクセスメモ１）を構成する漸合［文献二元岡他「
２次元記憶を甲いた速想処理システム」信学技報Ｅ　Ｃ
　７６−８０］と同様，こねとは違つ九行単位の置換，
アドレス修飾によって本可能である。

第２１図は本発明の第４の実施例のブロック構成図であ
って、ｌ　０　０　，　Ｊ　０　０’，　１　０　０Ｎ
は記憶ユニットと９０度回転器を兼ねる２次元シフトユ
ニット，６はアドレス信号入力端子，２０〜２８はＲＡ
Ｍユニット，３０＃′ｌｌｔスイッチングネットワーク
．ｓｉｄ　ＲＡＭユニット２０〜２８．スイッチングネ
ットワーク３０．２次元シフトユニット１００，１　０
　０’，１　０　０’の間を結ぶバス．６０〜６８は２
次元シフトユニットのデータ入出力端子である。

第２２図の（ａｌ　Ｔ　（ｂｌ　ｙ　（ｅ）はそれぞれ
２次元シフトユニットＪ　００　，　Ｊ　００’，１　
００“のブロック構成図であって，６０〜６８はデータ
入出力端子，７０は入カセレクタ．７１は出力セレクタ
．１１０〜ノ１８，１２０〜１２８，１３０〜１３８は
２次元シフトエレメント．ｇ　ｏは２次元シフト二二ツ
トを構成する列ユニットである。第２３図は２次元シフ
トエレメントのブロック構成図であクて，１　１　．　
Ｉ　Ｊ’はマスタスレープ型のＤ−ＦＦ．７２は入カセ
レクタ，７５は紙面の上方向への出力端子，７６Ｆｉ紙
面の右方向からの入力端子，７７は紙面の下方向からの
入力端子，７８は紙面の左方向への出力端子である。

次に本実施例により第６図のＲＡＭユニット配列内の２
次元配列データを時計方向に９０度回転する場合につい
てステッザを追って説明する。

◎ステッデＩ ＡからＡ＋２番地まで順に読みだして、２次元シフトユ
ニット２　０　０　，　１　０　０’，　２　０　０”
の各Ｄ一ＦＦＩＩに，第２４図に示すように格納する。

ここでます目の内容は対応する２次元シフトエレメント
内のＤ−ＦＦ７Ｊの内容な表している。

◎ステッデ２ ２次元シフトユニット１００．１００’，１００”の各
々の２次元シフトエレメントにおいてセレクタ７２をＤ
−ＦＦＭ　１の出力を選択することで，Ｄ−ＦＦＩＪの
内容をＤ−ＦＦＭＪ’に移す。

◎ステッデ３ ２次元シフトユニット７　００　，　１　００’，　Ｊ
　００’ＫおいてＤ−ＦＦ７Ｊ’の配列に格給されてい
る２次元配列データを．９０度回転し．Ｄ−ＦＦＩ　１
の配列に格納する。その格納結果を第２５図に示す。こ
こで，９０度回転は，各々の２次元シフトエレメントの
入力セレクタを右隣からの入力を選択するように設定し
て，Ｄ−ＦＦＩＩの内容を右から左にシフトしながら，
各列ユニット８０のセレクタ７０を横方向のシフト系か
らの入力な選択するように設定して，２次元シフトユニ
ット１００，Ｊ　０　０’．　１　０　０’の左端から
の出力データな下から上に向かって入力することを３回
繰り返すことで実行する。

◎ステッデ４ ２次元シフトユニット１　０　０　，　Ｊ　０　０’，
　１　０　０’のＤ−ＦＦＩＩの内容を，列ユニット８
０のセレクタ７ノを最上段の入力？選択するようにして
，一旦，スイッチングネットワーク３０に移し，行Ｄ−
ＦＦ７Ｊの内容をＤ−ＦＦＪノ′に移す。

◎ステップ３ ２次元シフトユニット７　０　０　，　１　０　０’，
　Ｊ　０　０’においてＤ−ＦＦＪ７’の配列に格納さ
れている２次元配列データを，９０度回転し，Ｄ−ＦＦ
Ｊ７の配列に格納する。その格納結果を第２５図に示す
。ここで，９０度回転Ｖｉ，各々の２次元シフトエレメ
ントの入力セレクタを右隣からの入力？選択するように
設定して、Ｄ−ＦＦＪ　７の内容を右から左にシフトし
ながら，各列ユニット８０のセレクタｖｏｆ横方向のシ
フト系からの入力を選択するように設定して．２次元シ
フトユニッ｝　１００，１　０　０’，　１　０　０“
の左端からの出力データな下から上に向かって入力する
ことを３回繰り返すことで実行する。

◎ステップ４ ２次元シフトユニットＪ　０　０　，　Ｊ　０　０’，
　７　０　０＃のＤ−ＦＦＩノの内容を，列ユニット８
０のセレクタ７ｌを最上段の入力を選択するようにして
，一旦，スイッチングネットワーク３０に移し．行単位
で紙面の手前から奥に向かって．１．Ｏ，−１だけロー
テートシフトした後、列ユニット８０のセレクタ７０を
外部バス８からの入力を選ぶようにして，再度２次元シ
フトユニットｌｏｏ，Ｊ　０　０’．　Ｊ　０　０’　
に戻し，Ｄ−ＦＦＪ　１の配列に第２６図に示す結果を
得る。ここで角の符号は逆方向への転送な表している。

◎ステッデ５ 列ユニット８０でセレクタ７０を最上段の２次元シフト
エレメントからの入力な選択するように，セレクタ７ノ
を９０度回転器ごとＫ異なる段の２次元シフトエレメン
トからの入力（ブロック図で左側の入力）？選択するよ
うにそれぞれ設定し，各列ユニット８０ごとでＤ−ＦＦ
Ｉ　Ｊの内容を下から上方向にローテートシフトしなが
ら．Ｄ−ＦＦＪノの配列内の２次元配列データケ．パス
８を介して，２０〜２８のＲＡＭユニット配列のＣ＋２
，Ｃ，Ｃ＋１番地の順に格納する。結果の２０〜２８の
ＲＡＭユニット配列の内容？第２７図に示す。

以上のステップ１から５を，２０〜２８のＲＡＭユニッ
ト配！１｛のＡ十３〜Ａ＋５およびＡ＋６〜Ａ＋８番地
に対しても同様に行なう。違いは，ステッデ４における
スイッチングネットワーク３０による行単位のシフト量
を−１．１．０と０．−１．１にすることと，ステッデ
５での格納先をそれぞれＣ＋３〜Ｃ＋５およびＣ＋６〜
Ｃ＋Ｓ番地にすることである。これらの結果として，２
０〜２８のＲＡＭユニット配列のＣ−Ｃ＋８番地に，第
２８図に示す結果を得る。

◎ステップ６ ２次元シフトユニットＪ　００，ｌθ”＋　１　０　０
’の各列ユニット８０のセレクタ７０をパス８からの入
力な選択するように設定し．下から上に向かうシフト動
作な実行しながら，　ＲＡＭユニット２０〜２８のＣ＋
５　，Ｃ＋３　，Ｃ番地の内容を，順次，各２次元シフ
トエレメン｝・のＤ−ＦＦＪ　ＪＯ中に読みだし．第２
９図の結果を得る。ここで各ます目の内容はＤ−　ＦＦ
　１　１の保持データを表している。

◎ステップ７ 列ユニット８０でセレクタ７０ｔｔｉｌ上段の２次元シ
フトエレメントからの入刀な選択するようにセレクタ７
ノを９０度回転器ごとに異なる段の２次元シフトエレメ
ントからの入カを選択するようにそれぞれ設定し，各列
ユニット８ｏごとでＤ−ＦＦＩＩの内容を下から上方向
にローテートシフトシナがら．Ｄ−ＦＦＪ　Ｊの配列内
の２次元配列データを、パス８に出方し，スイッチング
ネットワーク３０を経由してから，２０〜２８のＲＡＭ
ユニット配列のＢ　ｔ　Ｂ　＋　２　＊　Ｂ　＋　１番
地に領次格納し，第９図ｆｄ）と同じ結果を得る。ここ
で、スイッチングネットワーク３θでのシフト量は，紙
面の手前から奥に向かって０，２．１の順である。

ステップ６，７と同様な処理を２０〜２８のＲＡＭ　ユ
ニ，　ト配列のＣ＋１　，Ｃ＋４　．Ｃ＋７およびＣ＋
２　，ｃ＋５　，Ｃ＋８番地に対して行ない．その結果
？それぞれＢ＋３〜Ｂ＋５およびＢ＋６〜Ｂ＋８番地に
格納する（この際，２０〜２８のＲＡＭユニット配列の
アドレスのアク＋スｍ％およびスイッチ／グネ・ノトワ
ーク３ｏ上でのシフト量は適当に変更する必要がある。

）ことで、第６図の２次元配列データを時計方向に９０
度回転した結果なＢ　−　Ｂ　＋　８番地に得ることが
できる。

次に，効果Ｋついて訳明する。

初めにハードウェア規模の低減効果について評価する。

本発明の第１，２および３の実施例では，ＲＡＭユニッ
ト配列のアクセスデータ数がＬの場合ＷはＬで．９０度
回転器のサイズをＷがＬそのものになる従来の方法と比
べると，辺のサイズで１／ＶＬ，ハードウエア規模でＩ
Ａとなる。本発明の第４の実施例では辺のサイズがＬの
９０度回転器をＬ個程度並列に持つためハードウエア却
模が増大するがそれでも従来の方法に比べると．９０度
回転器全体のハードウエア規模は１／ＸＴＪＭ　ｆ＋と
なる。

Ｌが小さい場合には、アト゜レス修飾機構，シフトレジ
スタ配列等の余分に付加するハードウエアで相殺されて
しまい，ハードウェア低減効果は小さいが，Ｌが大きい
場合，例えば６４以上にもなると本発明の効果は非常に
大きｂことがわかる。なお、ハードウェア規模の評価で
．　ＲＡＭユニット配列を除外しているのは、他の用途
で使うものを流用できると考えているからである。この
流用可能性性こそが本発明でハードウェア規模を低減で
きる本質的な理由と貫える。また，Ｗ＝，／τの関係は
，ＲＡＭユニット配列からのアクセスを時分割（分割数
二Ｎ）で行ない等価的にＲＡＭユニット配列のサイズな
大きくすれば，Ｗ＝Ｖ鼠とすることが可能である。これ
によクて，設計条件に応じて，ＬとＷを適宜選択するこ
とができる。

一方，高速化の効果については，従来法の所要時間が２
Ｗ単位時間、本発明の・ぞイプライン的な処理が可能な
構成を採用した第２の実施例が４単位時間であることか
ら、９０度回転器のサイズが同一の東件では、最犬Ｗ／
２倍程度の高速化率が得られる。例えば、Ｗが８（Ｌ＝
６４）の場合に目， 従来の方法の所要時間　　　　：１６単位時間本発明の
第２の実施例所要時間：　４車位時間で，４倍の高速化
が，さらにＷが２倍の１６（Ｌ＝２５６）の場合には． 従来の方波の所要時間　　　　＝３２麺位時関本発明の
第２０寮施例所要時間＝　４単位時間で、８倍の高速化
が，それぞれ達成される６なお，第３，第４の実施例は
このままでは第２の実施例に比べ速度性能は劣るが，パ
イデライン的な処理構成を採用することで、第２の実施
例と同等の値まで所要時開を短縮することができる。

ところで，実施例１と実施ｆｌ．’　３ｔ　４の違いは
主に９０度回転器の構成にある。実施例１の回転器は、
９０度回転を高速に実行する点では優れているが，回転
エレメント間の結線が不規則であり規模の大きなものを
作るのは比較的難しい。一方．実施例２，３の９０度回
転用の２次元シフトユニットは構造が規則的であゆ作る
のは比較的容易である。実施例４はこの回転性訃の向上
のために９０度回転器の数な増やしたものといえる。

このように各実施例はそれぞれ特徴があるので２実際に
本発明を利甲する場合には，性能要求．設計条件？勘案
し，最適な構成を選択する必要がある。

［発明の効！］ 以上説明したように、本発明はＲＡＭユニット配列のア
クセスデータ数（データの語長が１ビットの場合にはア
クセスデータ＠）８−大きくしても、小形でかつ比較的
高速な９０度回転機構を構成できる。従って、本発明は
２次元データ処理装置（例えば画像処理装Ｗ）の全体の
性能の向上のためにＲＡＭユニット配列からのアクセス
データ数（アクセス幅）ケ大きくしようとする際のｌＪ
・形化・高速化の技術として極めて有効である。

【図面の簡単な説明】

第１図は本発明の第１の実施例のブロック構成図、 第２図は従来のピットデレーン用９０度Ｕ転機構のブロ
ック構成図、 第３Ｌシ：は従来回転機構による９０度回転の手順な示
す詐明図， 第４図は本発明に係る９０度回転器の一例を示すブロッ
ク構成図， 第５図は本発明に係るスイッチングネットワークの一例
を示ナブロック構成図， 第６図は本発明に係るＲＡＭユニット配夕１１に格納さ
れている回転対象の２次元配列データのーｆｌ１を示′
″Ｆ説明図， 第７図は第６図の２次元配列データをねじることによっ
て生成した２次元配列データの訣明図、第８図．第１０
図，銅１１図の（ａ）はそれぞれ本発明に係る９０度回
転器に読みだした回転対象のサブ２次元配列データの一
例を示＋設明図，第８図，第１０図，第１１図の［ｂｌ
けそれぞれ同図（ａ）の９０度回転後のサブ２次元配列
データを示す説明図， 第９図は本発明に係る回転後のサブ２次元配列デー汐を
１１１次ＲＡＭユニット配列に格ゼ、していく様子な示
忙戚明図、 第１　２　［’Ｚ＋は本発明の第２の実施例のブロック
構成図， 第１３図：（ａｔ　，　（ｂ）　，　（ｃｌはそれぞれ
本発明に係るシフトし／ノスタのブロック伊成図、 第１４図は本発明に係る２次元シフトエレメントの一例
を示すブロック構成図， 第１５は本発明Ｋ係るＲＡＭユニット配列のＡ〜Ａ＋２
番地を順次シフトレ・ゾスタ配列に読みだした結果のＤ
−ＦＦの配列の内容を示子説明図、第１６図ｂｌ　Ｖｉ
本発明に係る列方向にシフトのかかったＤ−ＦＦの配列
の格納データを示す説明図，第１６図（ｂｌぱ本発明に
係る２次元シフトユニットによる紙面の手前から奥に向
かうシフトにより得た正規のサブ２次元配列データの形
式の格納データを示す説明図， 第１７図は本発明に係るサブ２次元配列データを各アド
レスごとに格納して得たＲＡＭユニット配トレ・ノスタ
に読み出した結果のＤ−ＦＦの配列の内容を示す説明図
、 第２０図は第１９図のシフトレノスタの内容を２次元シ
フトユニットのＤ−　ＦＦの配列に順次読みだした結果
な・示一ｔ説明図， 第２１曖は本発明のｒ３の実旅例のブロック機成図， 第２２図ｆａｌ　，　ｆｂｌ　，　！ｃｌは第２１図の
２次元シフトユニットのブロック楕成図、 第２３図は第２２図の２次元シフトエレメントのブロッ
ク構成図， 第２４図は第６図のＲＡＭユニット配列内の２次元配列
データのＡ−Ａ＋２番地な順次２次元シフトユニットの
Ｄ−ＦＦの配列に読みだした結果を示す説明図， 第２５図は第２４図の配列データを２次元シフトユニッ
トの機能により９０度回転して得たＤ−ＦＦの配列の内
容？示す訣明図． 第２６図は第２５図の配列データをスイッチングネット
ワークによってねじって得たＤ−ＦＦの配列の内容な示
ナ説明図、 第２７図は第２６図のＤ−ＦＦの配列の内容をＲＡＭユ
ニソト配列のＣ　−　Ｃ　＋　２番地に格納した結果を
示す訣明図， 第２８図は第２７区のＣ　−　Ｃ　＋２番地と巨］様に
して得たｃ＋３〜Ｃ＋８番地までｔ合わせたＲＡＭユニ
ット配列内の２次元配列データを示す説明図，第２９図
は第２８図のＣ＋６，Ｃ＋３，Ｃ番地を順次，２次元シ
フトユニットのＤ−ＦＦに読みだした結果を示す訣明図
， 第３０図は本発明の第２の実施例のブロック構成図であ
る。 １．１′・・・９０度回転器、２・・・ＲＡＭユニット
、３・・・制ａ部，４・・・パス．５ｂ，５ｃ・・・ア
ドレス修飾器，６．６’，９９・・・アドレス信号入力
端子．７・・・アドレス修飾制御入力端子、７′・・・
シフトレジスタ制ケ入力端子，　８　．　８’，　８　
ｌｊ　，　８　Ｂ’，　８　８’・・・パス、Ｊｌｌｌ
ｌ・・・回転エレメント％１０′・・・２次元シフトエ
レメント、１１．１１’．５３，５４．５５・・・マス
タスレーブＤ−ＦＦ．１２・・トライステートパノファ
、ｌ　３　，　１　３’，　１　３“，５１　，５２，
７０　．７１７２・・・セレクタ，ノ５・・・上方向の
入出力端子，ｌ６・・・右方向の入出力端子，１７・・
・下方向の入出力端子、Ｊ８・・・左方向の入出力端子
，２０〜２８．９０〜９８・・・ＲＡＭユニノト，３０
・・・スイッチングネットワーク、３ノ・・・シフタ．
３２・・・データ入出力端子、４０〜４８・・・シフト
レジスタ、５６，７６．７７・・・データ入力端子．５
７，７５．７８・・・データ出力端子、６０〜６８・・
・パス８に対する２次元シフトユニットの入出力端子、
８０・・・２次元シフトユニット内の列ユニット．　７
　００　，　１００’，１００”・・・２次元シフトユ
ニット，１１０〜ノ１８，Ｉ２θ〜１：’１１，１３σ
〜１３８・・・２次元シフトエレメント，２θＯ・・・
誠ユニット配列。

Claims (4)

【特許請求の範囲】
1. （１）全体で同一のアドレスをアクセスする手段と行ご
   とに互いに異なるアドレスをアクセスする手段とを兼備
   する行列状に配列した記憶ユニットと、２次元配列デー
   タを行単位に置換する手段と、２次元配列データを９０
   度の奇数倍回転する手段とを合わせ持つことを特徴とす
   る２次元配列データ回転機構。
2. （２）請求項１記載の２次元配列データ回転機構におい
   て、全体で同一のアドレスをアクセスする手段と行ごと
   に互いに異なるアドレスをアクセスする手段とを兼備す
   る行列状に配列した記憶ユニットを、ランダムアクセス
   型のメモリユニットの２次元配列とそれに供給するアド
   レスを必要に応じて行単位で修飾する手段とで構成した
   ことを特徴とする２次元配列データ回転機構。
3. （３）請求項１記載の２次元配列データ回転機構におい
   て、全体で同一のアドレスをアクセスする手段と行ごと
   に互いに異なるアドレスをアクセスする手段とを兼備す
   る行列状に配列した記憶ユニットを、入力の取り込み口
   あるいは出力の引き出し口を行単位に変えられるように
   したローテート可能なシフトレジスタの２次元配列で構
   成したことを特徴とする２次元配列データ回転機構。
4. （４）請求項１記載の２次元配列データ回転機構におい
   て、記憶ユニットの行列状の配列の各行ごとに２次元配
   列データを９０度の奇数倍回転する手段を有することを
   特徴とする２次元配列データ回転機構。