JPH0782425B2

JPH0782425B2 - ソーティング回路

Info

Publication number: JPH0782425B2
Application number: JP1295382A
Authority: JP
Inventors: 誠市佐藤; 繁一中村
Original assignee: Namco Ltd
Current assignee: Namco Ltd
Priority date: 1988-11-16
Filing date: 1989-11-14
Publication date: 1995-09-06
Anticipated expiration: 2010-09-06
Also published as: JPH02224018A

Description

【発明の詳細な説明】［産業上の利用分野］本発明はソーティング回路、特に複数の基準軸データを
ソーティングする回路に関する。

［背景技術］画像合成回路は、外部から供給される画像情報に基づ
き、CRT表示用の各種画像信号を合成出力するものであ
り、単に２次元的な平面画像ばかりでなく、立体的な３
次元画像をも合成出力することができることから、例え
ば３次元画像用のビデオゲーム、飛行機および各種乗物
の操縦シュミレータ、コンピュータグラフィックス、CA
D装置のディスプレイおよびその他の用途に幅広く用い
られている。

ところで、画像合成回路を用いて奥行をもった３次元画
像をリアルタイムで合成する場合には、各標体の３次元
データを画像奥行方向の座標値、すなわちＺ軸データに
基づき各フレーム毎に高速でソーティングしてやる必要
がある。

このために、複数の３次元データを所定の基準軸デー
タ、すなわちＺ軸データに基づき高速ソーティングでき
る回路の開発が望まれていた。

しかし、従来このようなソーティングは、各データに含
まれるＺ軸データの隣接するものどうしを逐次比較して
その都度並べ変えるという作業を、全データに対して行
っていた。

このためには、メモリ間における全Ｚ軸データのデータ
転送を、多数回に渡って繰返し行われなければならな
い。従って、データのソーティング作業を高速で行うこ
とができないという問題があった。

特に、この従来技術では、比較対象とするＺ軸データの
個数が多くなると、ソーティング作業に時間と手間がか
かりすぎる。従って、これを高速ソーティングしようと
する場合には、比較的大型のコンピュータを用いなけれ
ばならず、装置全体が複雑かつ高価のものとなってしま
うという問題があった。

［発明が解決しようとする課題］本発明の目的は、複数のデータのソーティングを簡単な
構成で高速に行うことができ、特にソーティング対象と
なる基準軸データの個数が多いような場合でもソーティ
ングを高速で行うことが可能なソーティング回路を提供
することにある。

［課題を解決するための手段］前記目的を達成するため、本発明は、複数のデータとこれに１対１に対応する所定の基準軸デ
ータが入力され、前記複数のデータを前記基準軸データ
に基づきソーティングする回路であって、前記複数のデータを、この複数のデータと前記基準軸デ
ータに共通するデータ番号に対応させて記憶する情報メ
モリと、前記基準軸データが入力されるソーティング手段と、を含み、前記ソーティング手段は、入力される各基準軸データに対応したデータ番号を発生
するデータ番号発生手段と、前記基準軸データに基づきアドレスが指定されるファー
ストデータ番号記憶エリアを有し、各記憶エリアに対応
する基準軸データが最初に入力されたとき、この記憶エ
リアにデータ番号発生手段の発生するデータ番号を記憶
するファーストバッファメモリと、前記基準軸データに基づきアドレスが指定されるラスト
データ番号記憶エリアを有し、各記憶エリアに対応する
基準軸データが入力される毎に、この記憶エリアにデー
タ番号発生手段の発生するデータ番号を更新記憶するラ
ストバッファメモリと、データ番号に基づきアドレスが指定されるチェインデー
タ番号記憶エリアを有するチェインバッファメモリと、前記ラストバッファメモリのデータ番号が更新される毎
に、更新前のデータ番号で指定されるチェインデータ番
号記憶エリアに、更新される新たなデータ番号を書き込
む第１の制御手段と、前記ファーストバッファメモリおよびラストバッファメ
モリへのデータ番号書き込み終了後、ラストデータ番号
記憶エリアに記憶されたデータ番号で指定されるチェイ
ンデータ番号記憶エリアに、該ラストデータ番号記憶エ
リアと所定の対応関係にある前記ファーストデータ番号
記憶エリアに記憶されたデータ番号を書込むことによ
り、チェインデータ番号記憶エリア内に基準軸データが
昇順または降順に連鎖するようデータ番号を書込む第２
の制御手段と、チェインデータ番号記憶エリア内に書込まれたデータ番
号を所定の読出し規則に従い読出し、読出したデータ番
号順に前記情報メモリからデータを読み出す第３の制御
手段と、を含み、複数のデータを基準軸データに基づきソーティ
ング出力することを特徴とする。

また、本発明は、複数桁からなる複数の基準軸データをソーティングする
回路であって、入力される各基準軸データに対応するデータ番号を発生
するデータ番号発生手段と、前記各基準軸データを、そのデータ番号に対応させて記
憶する基準時データメモリと、前記基準軸データメモリから出力される複数桁の基準軸
データを１乃至複数桁からなる複数のサーチ群に分割し
た場合に、各サーチ群の値に基づきアドレスが指定され
るファーストデータ番号記憶エリアを有し、各記憶エリ
アに対応する各サーチ群が最初に入力されたとき、この
記憶エリアにデータ番号発生手段の発生するデータ番号
を記憶するファーストバッファメモリと、前記基準軸データメモリから出力される前記各サーチ群
の値に基づきアドレスが指定されるラストデータ番号記
憶エリアを有し、各記憶エリアに対応する各サーチ群が
入力される毎に、この記憶エリアにデータ番号発生手段
の発生するデータ番号に更新するラストバッファメモリ
と、データ番号に基づきアドレスが指定されるチェインデー
タ番号記憶エリアをそれぞれが有する少なくとも２つの
チェインバッファメモリと、前記ラストバッファメモリのデータ番号が更新される毎
に、更新前のデータ番号で指定される前記少なくとも２
つのチェインバッファメモリの中のいずれか一の前記チ
ェインデータ番号記憶エリアに、更新される新たなデー
タ番号を書き込む第１の制御手段と、前記ファーストバッファメモリおよびラストバッファメ
モリへのデータ番号書き込み終了後、ラストデータ番号
記憶エリアに記憶されたデータ番号で指定される前記い
ずれか一のチェインデータ番号記憶エリアに、該ラスト
データ番号記憶エリアと所定の対応関係にある前記ファ
ーストデータ番号記憶エリアに記憶されたデータ番号を
書込むことにより、前記いずれか一つのチェインデータ
番号記憶エリア内に前記各サーチ群の値が昇順または降
順に連鎖するようデータ番号を書き込む第２の制御手段
と、前記基準軸データのサーチの対象となるサーチ群を下位
桁から上位桁に向けて更新し、新たにサーチ対象となっ
た前記サーチ群を前記第２の制御手段によってチェイン
データ番号記憶エリアに書き込まれた順に前記基準軸デ
ータメモリから読み出して、前記第１の制御手段および
前記第２の制御手段による処理を前記チェインバッファ
メモリを切り替えながら前記基準軸データの最上位側に
位置するサーチ群に至るまで繰り返し行う第４の制御手
段と、最上位側のサーチ群のソーティング処理が終了した後、
対応する前記チェインデータ番号記憶エリア内に書き込
まれたデータ番号を所定の読み出し規則に従い読み出
し、読み出したデータ番号順に基準軸データメモリから
各基準軸データをソーティング出力する第３の制御手段
と、を含むことを特徴とする。

また、本発明は、複数のデータとこれに１対１に対応する所定の桁からな
る所定の基準時データをソーティングする回路であっ
て、前記複数のデータを、これら複数のデータと前記基準軸
データに共通するデータ番号に対応させて記憶する情報
メモリと、前記基準軸データが入力されるソーティング手段と、を含み、前記ソーティング手段は、各基準軸データに対応する前記データ番号を発生するデ
ータ番号発生手段と、各基準軸データを、そのデータ番号に対応させて記憶す
る基準軸データメモリと、前記基準軸データメモリから出力される複数桁の基準軸
データを１乃至複数桁からなる複数のサーチ群に分割し
た場合に、各サーチ群の値に基づきアドレスが指定され
るファーストデータ番号記憶エリアを有し、各記憶エリ
アに対応する各サーチ群が最初に入力されたとき、この
記憶エリアにデータ番号発生手段の発生するデータ番号
を記憶するファーストバッファメモリと、前記基準軸データメモリから出力される前記各サーチ群
の値に基づきアドレスが指定されるラストデータ番号記
憶エリアを有し、各記憶エリアに対応する各サーチ群が
入力される毎に、この記憶エリアにデータ番号発生手段
の発生するデータ番号を更新記憶するラストバッファメ
モリと、データ番号に基づきアドレスが指定されるチェインデー
タ番号記憶エリアをそれぞれが有する少なくとも２つの
チェインバッファメモリと、前記ラストバッファメモリのデータ番号が更新される毎
に、更新前のデータ番号で指定される前記少なくとも２
つのチェインバッファメモリの中のいずれか一の前記チ
ェインデータ番号記憶エリアに、更新される新たなデー
タ番号を書き込む第１の制御手段と、前記ファーストバッファメモリおよびラストバッファメ
モリへのデータ番号書き込み終了後、ラストデータ番号
記憶エリアに記憶されたデータ番号で指定される前記い
ずれか一のチェインデータ番号記憶エリアに、該ラスト
データ番号記憶エリアと所定の対応関係にある前記ファ
ーストデータ番号記憶エリアに記憶されたデータ番号を
書き込むことにより、前記いずれか一のチェインデータ
番号記憶エリア内に前記各サーチ群の値が昇順または降
順に連鎖するようデータ番号を書き込む第２の制御手段
と、前記基準軸データのサーチの対象となるサーチ群を下位
桁から上位桁に向けて変更し、新たにサーチ対象となっ
た前記サーチ群を前記第２の制御手段によってチェイン
データ番号記憶エリアに書き込まれた順に前記基準軸デ
ータメモリから読み出して、前記第１の制御手段および
前記第２の制御手段による処理を前記チェインバッファ
メモリを切り替えながら前記基準軸データの最上位側に
位置するサーチ群に至るまで繰り返し行う第４の制御手
段と、最上位側のサーチ群のソーティング処理が終了した後、
対応する前記チェインデータ番号記憶エリア内に書き込
まれたデータ番号を所定の読み出し規則に従い読み出
し、読み出したデータ番号順に前記情報メモリからデー
タを読み出す第３の制御手段と、を含み、複数のデータを基準軸データに基づきソーティ
ング出力することを特徴とする。

［作用］このように、本発明によれば、ソーティングの対象とな
る基準軸データを、そのデータ番号順にファーストバッ
ファメモリおよびラストバッファメモリへ入力する。

そして、ファーストバッファメモリは、そのファースト
データ番号記憶エリアに、対応する基準軸データが最初
に入力されたときのデーア番号を記憶する。

同様にして、ラストバッファメモリは、そのラストデー
タ番号記憶エリアに、対応する基準軸データが読出され
る毎に、そのデータ番号を順次更新記憶する。従って、
各ラストデータ番号には、対応する基準軸データが最後
に読出されたときのデータ番号が記憶されることにな
る。

また、ラストデータ番号記憶エリアに記憶されているデ
ータ番号が更新記憶されると、その記憶エリアに記憶さ
れていたデータ番号と新たに記憶されるデータ番号とが
チェインバッファメモリへ向け入力される。

そして、チェインバッファメモリは、ラストデータ番号
記憶エリアのデータが更新される毎に、更新前のデータ
番号で指定されるチェインデータ番号記憶エリアに、更
新後の新たなデータ番号を書込む。従って、値が同じで
かつデータ番号のみ異なる基準軸データが繰返して入力
された場合は、その基準軸データの履歴、すなわち、そ
の基準軸データがどのようなデータ番号順で入力された
かがチェインデータ番号記憶エリアに書込まれることに
なる。

このような一連のファーストバッファメモリ、ラストバ
ッファメモリおよびチェインバッファメモリへのデータ
書込み終了後、ラストデータ番号記憶エリアに記憶され
たデータ番号で指定されるチェインデータ番号記憶エリ
アに、該ラストデータ番号と記憶エリア所定の対応関係
にあるファーストデータ番号記憶エリアに記憶されたデ
ータ番号が順次書込まれる。このようにして、チェイン
データ番号記憶エリアの各記憶エリアには、基準軸デー
タが昇順または降順に連鎖するようデータ番号が書込ま
れることになる。

そして、本発明のソーティング回路では、チェインデー
タ番号記憶エリア内に書込まれたデータ番号を、所定の
読出し規則に従って読出している。そして、入力された
基準軸データを、このようにして読出されたデータ番号
順に出力するように読出し制御している。

このようにすることにより、入力された基準軸データが
昇順または降順にソーティング出力されることになる。

特に、請求項（１）記載のソーティング回路では、この
ように読出されたデータ番号順に、情報メモリからデー
タが出力されるよう読出し制御している。このようにす
ることにより、情報メモリからは、複数のデータが基準
軸データに基づき昇順または降順にソーティング出力さ
れることとなる。

以上説明したように、本発明によれば、大まかに分け
て、入力される基準軸のデータのファーストバッファメ
モリ、ラストバッファメモリおよびチェインバッファメ
モリへのデータ転送と、ファーストバッファメモリ、ラ
ストバッファメモリからチェインバッファメモリへのデ
ータ転送とからなる２回の転送作業により、基準軸デー
タのソーティングを行うことができる。このため、従来
のように互いに隣接する基準軸データを比較して、基準
軸データそのものを逐次並べ変えるというソーティング
技術に比べ、データ転送の回数が大巾に減少し、ソーテ
ィングを高速で行うことができる。

さらに、本発明によれば、基準時データそのものを用い
てソーティングするのではなく、基準軸データのデータ
番号を利用し、基準軸データを間接的にソーティングす
るために、仮に基準軸の桁数およびデータ数が多い場合
でも、簡単かつ高速にソーティングを行うことができ
る。

特に、請求項（１）の発明によれば、入力された基準軸
データを記憶しておくためのメモリが不要であり、より
簡単な回路でソーティングを行うことが可能となる。

また、請求項（２）および（３）の発明によれば、基準
軸データの桁数が長い場合であっても、各バッファメモ
リのメモリ容量を増やさずにすみ、より簡単な回路でソ
ーティングを行うことが可能となる。

［実施例］次に本発明の好適な実施例を図面に基づき説明する。

第１実施例第１図には本発明に係るソーティング回路の好適な実施
例が示されている。実施例の回路は、データ発生回路８
から出力される基準軸データをソーティング出力するも
のであり、基準軸データメモリ10と、データ番号ポイン
タ12と、ファーストバッファメモリ20と、ラストバッフ
ァメモリ30と、チェインバッファメモリ40と、これら各
メモリに対するデータの書込読出を制御するソーティン
グ制御回路80とを含む。

（ａ）基準軸データメモリ10への書込／読出前記基準軸データメモリ10は、データ番号ポインタ12に
よって指定される１〜Ｎまでの合計Ｎ個の基準軸データ
記憶エリア14を有する。ここにおいて、基準軸データ
が、Ｍビットデータで構成されているとすれば、各基準
軸データ記憶エリア14はそれぞれＭビットの記憶容量を
もつように形成すればよい。

そして、外部からソーティング対象となる複数の基準軸
データが入力されると、その基準軸データにはその入力
順に１〜Ｎのデータ番号が割振られ、データ番号ポイン
タ12によってアドレス指定される１〜Ｎの基準軸データ
記憶エリア14に順次書込まれる。

このようにして、基準軸データメモリ10内へソーティン
グの対象となる基準軸データの書込みが終了すると、次
にこの基準軸データメモリ10から基準軸データが１〜Ｎ
のデータ番号順に順に読出され、ファーストバッファメ
モリ20およびラストバッファメモリ30に向け出力され
る。

実施例において、この基準軸データの読出しは、データ
番号ポインタ12から読出アドレスとしてデータ番号が１
〜Ｎの順で順次出力されることにより行われる。そし
て、データ番号によりアドレスが指定されると、指定さ
れた基準軸データ記憶エリア14からファーストバッファ
メモリ20およびラストバッファメモリ30に向け基準軸デ
ータが読出される。

（ｂ）バッファメモリ20、30への書込みまた、前記ファーストバッファメモリ20およびラストバ
ッファメモリ30は、基準軸データが取り得る値の全てに
１対１に対応するファーストデータ番号記憶エリア24、
ラストデータ番号記憶エリア34を有する。

実施例のように、基準軸データがＭビットで構成されて
いる場合には、0,1,2…（2^M−１）の合計2^M個の値を取
り得る。

従って、前記ファーストバッファメモリ20には、少なく
とも0,1,2…（2^M−１）の各アドレスで指定される2^M個
のファーストデータ番号記憶エリア24が設けられてい
る。同様にして、前記ラストバッファメモリ30に、少な
くとも0,1,2…（2^M−１）の各アドレスで指定される2^M
個のファーストデータ番号記憶エリア34が設けられてい
る。

また、これらファーストデータ番号記憶エリア24および
ラストデータ番号記憶エリア34には、基準軸データメモ
リ10から出力される基準軸データのデータ番号が書込ま
れる。本実施例において、データ番号は１〜Ｎで表わさ
れ、その最大値はＮである。従って、前記各データ番号
記憶エリア24、34は、それぞれ｛log₂N｝ビット（但
し、｛｝は小数点以下を切り上げた整数を意味する記
号とする）の容量をもつように形成すればよい。

そして、基準軸データメモリ10からファーストバッファ
メモリ20およびラストバッファメモリ30に基準軸データ
が入力されると、これらファーストバッファメモリ20お
よびラストバッファメモリ30は、対応するアドレスポイ
ンタ22および32によって指定されるデータ番号記憶エリ
ア24、34へその基準軸データのデータ番号の書込みを行
う。

本実施例において、この様なデータの書込みは、ソーテ
ィング制御回路80の第１の制御回路80aを用い、次のよ
うにして行われる。

すなわち、基準軸データメモリ10から、データ番号ポイ
ンタ12によって指定されるデータ番号の基準軸データが
出力されると、その基準軸データはアドレスポインタ2
2、32にセットされ、これらアドレスポインタ22、32か
らは、セットされた基準軸データが書込アドレスとして
出力される。そして、この書込アドレスによって指定さ
れる各データ番号記憶エリア24、34に、データ番号ポイ
ンタ12によって指定されるデータ番号（基準軸データに
対応するデータ番号）が書込まれることになる。

ここにおいて、ファーストデータ番号記憶エリア24は、
一旦データ番号が記憶されると、基準軸データメモリ10
から同じ値の新たな基準軸データが順次出力されても、
新たなデータ番号は重ね書きされないように形成されて
いる。これに対し、ラストデータ番号記憶エリア34は、
一旦データ番号が記憶されても、次に基準軸データメモ
リ10から同じ値の基準軸データが出力されると、その基
準軸データのデータ番号が新たに更新記憶されるように
形成されている。

このように、ファーストデータ番号記憶エリア24には、
この基準軸データの値が初めて出現したときのデータ番
号が記憶される。これに対し、ラストデータ番号記憶エ
リア34には、各基準軸データの値が最後に出現したとき
のデータ番号が記憶されることになる。

このため、ファーストデータ番号記憶エリア24およびラ
ストデータ番号記憶エリア34の同じアドレスには、基準
軸データメモリ10から同じ値の基準軸データが１回しか
出力されない場合には同じデータ番号が書込まれること
になるが、同じ値の基準軸データが複数回にわたって出
力されると、最終的には異なるデータ番号が記憶される
ことになる。

従って、ラストバッファメモリ30のラストデータ番号記
憶エリア34の値が、複数回にわたって更新記憶された場
合に、この更新がどのように行われたかが判れば、基準
軸データを昇順または降順にソーティングしたときの各
基準軸データのデータ番号の並びが判明する。

このため、チェインバッファメモリ40内には、アドレス
ポインタ42の出力するデータ番号に基づき０〜Ｎの順に
アドレスが指定されるチェインデータ番号記憶エリア44
が設けられている。これら各チェインデータ番号記憶エ
リア44も、前記ファーストデータ番号記憶エリア24およ
びラストデータ番号記憶エリア34と同様に、少なくとも
｛log₂N｝ビットの記憶容量を有するように形成すれば
よい。

そして、ラストデータ番号記憶エリア34の内容が更新記
録されると、更新前のデータ番号がアドレスポインタ42
に設定され、チェインデータ番号記憶エリア44のアドレ
ス指定が行われる。そして、指定されたチェインデータ
番号記憶エリア44には更新後の新なデータ番号が書込ま
れる。

このようにして、ラストデータ番号記憶エリア34が更新
記憶されると、その更新の履歴はチェインバッファメモ
リ40内に順次書込まれることになる。

以上説明したように、本実施例によれば、基準軸データ
メモリ10からデータ番号順に基準軸データが出力される
と、出力された基準軸データを書込みアドレスとして、
そのデータ番号が、ファーストバッファメモリ20,ラス
トバッファメモリ30に書き込まれ、さらに、これに付随
してラストバッファメモリ30からチェインバッファメモ
リ40へのデータの転送書込みが行われる。

このようなデータ転送書込みが終了すると、次にファー
ストバッファメモリ20およびラストバッファメモリ30か
らチェインバッファメモリ40へのデータ転送が開始され
る。

（ｃ）バッファメモリ40へのデータの転送書込みこのようなデータ転送が開始されると、ソーティング制
御回路80の第２の制御回路80bは、次のような転送制御
を行う。

まず、ラストデータ番号記憶エリア34に記憶されたデー
タ番号がアドレスポインタ42にセットされる。次に、こ
のアドレスポインタ42によりアドレス指定されるチェイ
ンデータ番号記憶エリア44に、その指定アドレスと所定
の対応関係にあるファーストデータ番号記憶エリア24の
データ番号を書込む。

このようなデータ番号の書き込みは、データを昇順にソ
ーティングする場合と、降順にソーティングする場合と
では若干異なるが、ここでは、データを昇順にソーティ
ングする場合を例にとり説明する。

例えば、アドレス０で指定されるラストデータ番号記憶
エリア34にデータ番号が記憶されているときには、まず
アドレス０番地に記憶されているデータ番号がアドレス
ポインタ42にセットされる。

そして、次にアドレス１で指定されるファーストデータ
番号記憶エリア24からデータ番号が読出され、このデー
タ番号が、アドレスポインタ42で指定されるチェインデ
ータ番号記憶エリア44に書込まれる。

また、このときアドレス１で指定されるファーストデー
タ番号記憶エリア24にデータ番号が記憶されていない場
合には、アドレス２で指定される記憶エリア24からデー
タ番号を読出し、チェインデータ番号記憶エリア44に書
き込む。また、アドレス２で指定されるファーストデー
タ番号記憶エリア24にもデータ番号が記憶されていない
場合には、データが見つかるまで同様にアドレス3,アド
レス４…と順次アドレスｋをインクリメントしていく。

そして、アドレスｋで指定される記憶エリア24からデー
タ番号が読出されると、このデータ番号が、アドレスポ
インタ42で指定されるチュインデータ番号記憶エリア44
に書込まれる。

この様な読出書込みが完了すると、次に、アドレスｋで
指定されるラストデータ番号記憶エリア34から、データ
番号が読出され、それを書込みアドレスとして前回と同
様にして、チェインデータ番号記憶エリア44へのデータ
の書込みが行われる。

実施例の装置は、この様なチェインデータ番号記憶エリ
ア44へのデータの書込みを繰り返して行う。

そして、このような一連の書込み動作が終了すると、チ
ェインバッファメモリ40のチェインデータ番号記憶エリ
ア44には、基準軸データが昇順に連鎖するようデータ番
号が記憶されることになる。

そして、ソーティング制御回路80の第３の制御回路80c
は、チェインデータ番号記憶エリア44内に書込まれたデ
ータ番号を、所定の読出し規則に従って読出す。そし
て、このようにして読出されたデータ番号順に、基準軸
データメモリ10から基準軸データが出力されるように読
出し制御している。

このようにすることにより、基準軸データメモリ10から
は、基準軸データが昇順にソーティング出力されること
になる。

具体的なソーティング動作次に、このようなソーティング回路を用いて、データ発
生回路８から出力される７個の基準軸データを昇順にソ
ーティングする場合と降順にソーティングする場合を例
にとり説明する。

（Ｉ）昇順にソーティングする場合第２図にはこのようなソーティング回路の一例が示され
ている。

本実施例においては、７個の基準軸データをソーティン
グ対象とするため、基準軸データメモリ10は、１〜７の
データ番号で指定される合計７個の基準軸データ記憶エ
リア14を有するよう形成すればよい。

また、前記基準軸データは、０〜３のいずれかの値をと
るよう２ビットデータで構成されているものとする。こ
のようにすると、ファーストバッファメモリ20およびラ
ストバッファメモリ30は、それぞれ０〜３の基準軸デー
タをアドレスとする４つのデータ番号記憶エリア24,24
を有するよう形成すればよい。

（ａ）基準軸データメモリ10への書込み／読出ここにおいて、まず外部のデータ発生回路８から基準軸
データメモリ10に向け、基準軸データが、２→１→３→３→０→２→３の順で入力されると、入力された基準軸データは順次1,
2,3…のデータ番号をアドレスとする記憶エリア14に書
込まれることになる。

本発明の特徴の一つは、このようにしてデータメモリ10
内に基準軸データが書込まれると、この基準軸データの
ソーティングを、基準軸データそのものではなくデータ
番号を用いて行うことにある。

このようにすることにより、ソーティング対象となる基
準軸データの桁数が多い場合でも、この基準軸データの
ソーティングを簡単な回路で高速に行うことが可能とな
る。

本実施例においては、このように基準軸データメモリ10
内に基準軸データが書込まれると、この基準軸データメ
モリ10から、そのデータ番号順に基準軸データが順次読
出される。

（ｂ）バッファメモリ20、30への書込みこのようにして、基準軸データが読出されると、読出さ
れた基準軸データをアドレスとして、対応するデータ番
号がファーストデータ番号記憶エリア24およびラストデ
ータ番号記憶エリア34に順次書込まれる。

従って、データメモリ10から、まずデータ番号「１」で
特定される基準軸データ「２」が出力されると、この基
準軸データ「２」をアドレスとして、各データ番号記憶
エリア24,34には、データ番号「１」が書込まれる。

同様にして、基準軸データメモリ10から、データ番号
「２」で特定される基準軸データ「１」が出力される
と、この基準軸データ「１」をアドレスとして、データ
番号24,34にはそのデータ番号「２」が書込まれる。

次に、基準軸データメモリ10から同様にしてデータ番号
「３」で特定される基準軸データ「３」が出力される
と、この基準軸データ「３」をアドレスとして、データ
番号記憶エリア24,34には、そのデータ番号「３」が書
込まれる。

次に、データ番号「４」で特定される基準軸データ
「３」が出力されると、この基準軸データ「３」をアド
レスとして、データ番号記憶エリア24,34には、データ
番号「４」が入力される。このとき、ファーストデータ
番号記憶エリア24には、すでにデータ番号が書込まれて
いるため、新なデータ番号の書込みは行われない。これ
に対し、ラストデータ番号記憶エリア34は、前のデータ
番号「３」を新なデータ番号「４」に更新記憶する。こ
のため、チェインデータ番号記憶エリア44には、更新前
のデータ番号「３」をアドレスとして、更新後のデータ
番号「４」が書込まれることとなる。

次に、基準軸データメモリ10からデータ番号「５」で特
定される基準軸データ「０」が読出されると、この基準
軸データ「０」をアドレスとして、各データ番号記憶エ
リア24,34にはそのデータ番号「５」が書込まれる。

次に、基準軸データメモリ10から、データ番号「６」で
特定される基準軸データ「２」が出力されると、この番
号基準軸データ「２」をアドレスをして、デーア記憶エ
リア24,34にはそのデータ番号「６」が入力される。こ
のとき、アドレス「２」で指定されるファーストデータ
番号記憶エリア24には、すでにデータ番号「１」が書込
まれている。このため、新たに入力されたデータ番号
「６」の書込みは行われない。これに対し、アドレス
「２」で指定されるラストデータ番号記憶エリア34の内
容は、新たに入力されるデータ番号「６」に更新記憶さ
れる。

このように、ラストデータ番号記憶エリア34の内容が、
「１」→「６」に更新されると、更新前のデータ番号
「１」をアドレスとしてチェインデータ番号記憶エリア
44には、更新後の新なデータ番号「６」が書込まれる。

次に、基準軸データメモリ10から、データ番号「７」で
特定される最後の基準軸データ「３」が読出されると、
この基準軸データ「３」をアドレスとして、データ番号
24,34にデータ番号「７」が入力される。このとき、フ
ァーストデータ番号記憶エリア24には、すでにデータ番
号「３」が書込まれているため、新たに入力されるデー
タ番号が書込まれることはない。これに対し、ラストデ
ータ番号記憶エリア34の内容は、新たに入力されるデー
タ番号「７」に更新記憶される。

このように、ラストデータ番号記憶エリア34の内容が、
「４」→「７」に更新されると、更新前のデータ番号
「４」をアドレスとして、チェインデータ番号記憶エリ
ア44には、更新後の新なデータ番号「７」が記憶され
る。

このような一連の書込作業により、基準軸データをアド
レスとするファーストデータ番号記憶エリア24には、各
基準軸データが最初に出現したときのデータ番号が書込
まれることとなる。

また、基準軸デートをアドレスとするラストデータ番号
記憶エリア34には、各基準軸データの値が最後に出現し
たときのデータ番号が記憶されることとなる。

さらに、データ番号をアドレスとするチェインデータ番
号記憶エリア44には、ラストデータ番号記憶エリア34の
データが更新記憶される毎に、更新前のデータ番号をア
ドレスとして更新後のデータ番号が順次書込まれること
にになる。従って、基準軸データメモリ14から同じ基準
軸データが複数回に渡って出力されると、この記憶エリ
ア44には、その基準軸データがどのようなデータ番号順
に出力されたかの履歴が記憶されることになる。

（ｃ）バッファメモリ40へのデータの転送書込みこのような一連の書込み動作が終了すると、次に第３図
に示すよう、ファーストバッファメモリ20およびラスト
バッファメモリ30から、チェインバッファメモリ40への
データ転送が開始される。

このようなデータ転送が開始されると、まず、アドレス
の小さい方から順に、データが記憶されているデータ番
号記憶エリア24を探し出す。そして、その記憶エリア24
に記憶されているデータ番号を、スタートアドレスとし
て読みだし、チェインデータ番号記憶エリア44のアドレ
ス０番地に書き込む。

なお、記憶エリア44のアドレス０番地を他の用途に用い
る場合には、第３図において点線で示すように、前記ス
タートアドレスを、例えば、スタートアドレスポインタ
310にセットするよう形成すればよい。

本実施例において、アドレスの小さい方から順にデータ
が記憶されているデータ番号記憶エリア24を探していく
と、アドレス０の記憶エリア24内にデータ番号が書き込
まれているのが検出される。そして、このデータ番号
「５」が、第３図に、示すようにアドレス０で指定ささ
れるチェインデータ番号記憶エリア44に書込まれる。

なお、アドレス「０」の記憶エリア44を他の用途に使用
する場合には、スタートアドレスポインタ310にセット
するようにする。

次に、基準軸データ「０」が最後に出現したときのデー
タ番号をアドレスとして、これより大きい基準軸データ
「１」が最初に出現したときのデータ番号をチェインデ
ータ番号記憶エリア44に書込む。

このようにするためには、アドレス「０」で指定される
ラストデータ番号記憶エリア34内のデータ番号「５」を
書込みアドレスとして読み出す。そして、このアドレス
「５」で指定されるチェインデータ番号記憶エリア44
に、アドレス「１」で指定されるファーストデータ番号
記憶エリア24内のデータを書込めばよい。

次に、同様にして基準軸データ「１」が最後に出現した
ときのデータ番号を書込みアドレスとして、これより上
の基準軸データ「２」が初めて出現したときのデータ番
号をチェインデータ番号記憶エリア44に書込む。

このような書込みを行うためには、アドレス「１」で指
定されるラストデータ番号記憶エリア34内のデータ番号
「２」を書込みアドレスとして読み出す。そして、この
アドレス「２」で指定されるチェインデータ番号記憶エ
リア44に、アドレス「２」で指定されるファーストデー
タ番号記憶エリア24内のデータ「１」を書込めばよい。

同様にして、基準軸データ「２」が最後に出現したとき
のデータ番号「６」を書込みアドレスとし、基準軸デー
タ「３」が最初に出現するときのデータ番号「３」をチ
ェインデータ番号記憶エリア44に書込む。

このような一連のデータ転送作業が終了すると、チェイ
ンデータ番号記憶エリア44内には、基準軸データが昇順
に連鎖するようデータ番号が書込まれることになる。

（ｄ）基準軸データのソーティング出力このようなデータの転送書込みが終了すると、次にチェ
インバッファメモリ40から、所定の読出し規則にしたが
い、データ番号が基準軸データメモリ10に対する読出し
アドレスとして順次出力される。

本実施例においてはアドレス０により指定されるチェイ
ンデータ番号記憶エリア44に、読出開始アドレスが記憶
されている。このため、まず、アドレス「０」がアドレ
スポインタ42にセットされる。これにより、データ番号
記憶エリア44のアドレス「０」内に記憶されているデー
タ番号「５」が読出開始アドレスとして読出されること
になる。

このようにして、データ番号がデータ番号記憶エリア44
から読出されると、読出されたデータ番号が次にアドレ
スポインタ42にセットされる。

従って、アドレス「５」で指定されるデータ番号記憶エ
リア44から、次のデータ番号「２」が読出され、読出さ
れたデータ番号が新たにアドレスポインタ42にセットさ
れる。

このような読出し規則に従ってデータ番号を順次読出す
と、チェインデータ番号記憶エリア44からは、５→２→１→６→３→４→７の順にデータ番号が順次出力されることになる。

従って、このようにして読出されたデータ番号を、基準
軸データメモリ10に対するデータ読出しアドレスとして
用いると、基準軸データメモリ10からは、０→１→２→２→３→３→３の順で、基準軸データが順次昇順にソーティング出力さ
れることになる。

（II）降順にソーティングする場合次に、本発明のソーティング回路を用いて、基準軸デー
タを降順にソーティングする場合を、第２図に示すよう
に７個の基準軸データを降順にソーティングする場合を
例にとり説明する。

（ａ）基準軸データメモリ10への書込み／読出しこの動作は、基準軸データを昇順にソーティングする場
合と同じであるので、その説明は省略する。

（ｂ）バッファメモリ20,30への書込みこの動作もデータを昇順にソーティングする場合と同様
であるので、ここではその説明は省略する。

（ｃ）バッファメモリ40へのデータの転送書込み基準軸データを昇順にソーティグする場合と降順にソー
ティングする場合とでは、バッファメモリ40へのデータ
の転送書込み作業のしかたが若干異なる。

第20図には、データを降順にソーティングする場合にお
いて、ファーストバッファメモリ20およびラストバッフ
ァメモリ30から、チェインバッファメモリ40へのデータ
転送の一例が示されている。

降順にソーティングを行う場合には、データ転送開始と
共に、まずアドレスの大きい方から順に、データが記憶
されているデータ番号記憶エリア24を捜しだす。そし
て、その記憶エリア24に記憶されているデータ番号を、
スタートアドレスとして読出し、チェインデータ番号記
憶エリア44のアドレス０番地に書込む。

なお、記憶エリア44のアドレス０番地を他の用途に用い
る場合には、第20図において点線で示すように、前記ス
タートアドレスを例えばスタートアドレスポインタ310
にセットするように形成すればよい。

本実施例において、アドレス（基準軸データ）の大きい
方から順にデータが記憶されているデータ番号記憶エリ
ア24を探していくと、アドレス「３」の記憶エリア24内
にデータ番号が書き込まれているのが検出される。そし
て、このデータ番号「３」が、第20図に示すようにアド
レス「０」で指定されるチェインデータ番号記憶エリア
44に書込まれる。

次に、基準値データ「３」が最後に出現したときのデー
タ番号をアドレスとして、これより小さい基準軸データ
「２」が最初に出現したときのデータ番号をチェインデ
ータ番号記憶エリア44に書込む。

このようにするためには、アドレス「３」で指定される
ラストデータ番号記憶エリア34内のデータ番号「７」
を、書込みアドレスとして読み出す。そして、このアド
レス「７」で指定されるチェインデータ番号記憶エリア
44に、アドレス「２」で指定されるファーストデータ番
号記憶エリア24内のデータ「１」を書込めばよい。

次に、同様にして基準軸データ「２」が最後に出現した
ときのデータ番号を書込みアドレスとして、これより下
の基準軸データ「１」が初めて出現したときのデータ番
号をチェインデータ番号記憶エリア44に書込む。

このような書込みを行うためには、アドレス「２」で指
定されるラストデータ番号記憶エリア34内のデータ番号
「６」を書込みアドレスとして読み出す。そして、この
アドレス「６」で指定されるチェインデータ番号記憶エ
リア44に、アドレス「１」で指定されるファーストデー
タ番号記憶エリア24内のデータ「２」を書込めばよい。

同様にして、基準軸データ「１」が最後に出現したとき
のデータ番号「２」を書込みアドレスとし、基準軸デー
タ「０」が最初に出現するときのデータ番号「５」をチ
ェインデータ番号記憶エリア44に書込む。

このような一連のデータ転送作業が終了すると、チェイ
ンデータ番号記憶エリア44内には、基準軸データが降順
に連鎖するようデータ番号が書込まれることになる。

本実施例においてはアドレス「０」により指定されるチ
ェインデータ番号記憶エリア44に、読出開始アドレスが
記憶されている。このため、まず、アドレス「０」がア
ドレスポインタ42にセットされる。これにより、データ
番号記憶エリア44のアドレス「０」内に記憶されている
データ番号「３」が読出開始アドレスとして読出される
ことになる。

従って、アドレス「３」で指定されるデータ番号記憶エ
リア44から、次のデータ番号「４」が読出され、読出さ
れたデータ番号が新たにアドレスポインタ42にセットさ
れる。

このような読出し規則に従ってデータ番号を順次読出す
と、チェインデータ番号記憶エリア44からは、３→４→７→１→６→２→５の順にデータ番号が順次出力されることになる。

従って、このようにして読出されたデータ番号を、基準
軸データメモリ10に対するデータ読出しアドレスとして
用いると、基準軸データメモリ10からは、３→３→３→２→２→１→０の順で、基準軸データが順次降順にソーティング出力さ
れることになる。

（III）昇順および降順のコーティング作業についての
まとめこのようにして、本発明によれば、基準軸データを昇順
にソーティングする場合でも、降順にソーティングする
場合でも、基準軸データそのものを用いるものではな
く、基準軸データに対応して割り付けられたデータ番号
を用いて行うことにより、基準軸データのビット数が多
い場合でも、これにそれほど影響されることなくソーテ
ィング作業を高速でしかも簡単に行うことが可能とな
る。

特に、本発明によれば、基準軸データのソーティング
を、従来のように一つの基準軸データを残りのすべての
基準軸データと比較しながら並べ変える作業を、各基準
軸データごとに繰返して行うものに比べ、データの転送
回数が大幅に少なくてすみ、しかも転送対象となるデー
タ数量も大幅に少なくすむため、基準軸データの転送作
業を簡単な回路でしかも極めて高速で行うことが可能と
なる。

なお、前記実施例においては、０〜３の４つの基準軸デ
ータが全て存在する場合を例にとり説明したが、本発明
はこれに限らず、この中の一つの基準軸データ、例えば
基準軸データ「１」が存在しない場合でも同様にしてソ
ーティング作業を行うこともできる。

この場合には、第４図に示すように、基準軸データメモ
リ10からファーストバッファメモリ20およびラストバッ
ファメモリ30へのデータ転送が終了しても、これら各バ
ッファメモリ20,30のアドレス「１」で指定されるデー
タ番号記憶エリア24,34には何らデータ番号は書込まれ
ない。

従って、例えばデータを昇順にソーティングする場合に
は、各バッファメモリ20,30からチェインバッファメモ
リ40へのデータ転送作業を行うにあたって、基準軸デー
タ「０」が最後に出力されたときのデータ番号「５」を
アドレスとして、次にこれ以上の基準軸データ、すなわ
ち基準軸データ２が最初に出現するときのデータ番号１
をチェインデータ番号記憶エリア44へ書込めばよい。な
お、後のデータ書込みは前記第３図に示す実施例と同様
にして行う。

第２実施例第21図には、本発明の好適な第２実施例が示されてい
る。

前記第１実施例では、基準軸データメモリ10のデータ番
号ポインタ12がデータ番号発生手段として機能する場合
を例にとり説明した。本実施例ではそのかわりにデータ
番号発生カウンタ13を用い、このカウンタ13をデータ番
号発生手段として機能させることを特徴とするものであ
る。

すなわち、外部のデータ発生回路８から、ソーティング
対象となる基準軸データが順次出力されると、この基準
軸データは前記第１実施例と同様にして基準軸データメ
モリ10内へ順に書き込み記憶されると共に、データ番号
カウンタ13,ファーストバッファメモリ20,ラストバッフ
ァメモリ30へ入力される。

このとき、データ番号カウンタ13は、基準軸データが入
力される毎に対応するデータ番号を発生する。実施例で
は、基準軸データの入力に同期して0,1,2…（2^M−１）
の順にデータ番号を出力する。

そして、ファーストバッファメモリ20,ラストバッファ
メモリ30の各記憶エリア24,34には、データ発生回路８
から出力される基準軸データを書き込みアドレスとし
て、データ番号カウンタ13から出力されるデータ番号が
前記第１実施例と同様にして書込まれる。このとき、チ
ェーンバッファメモリ40にも、前記第１実施例と同様に
してデータの書き込みが行われる。

このような各バッファメモリ20,30,40へのデータ転送書
き込みが終了した時点で、基準軸データメモリ10への基
準軸データの書き込みも終了している。そして、このよ
うなデータ転送書き込み終了後、次に前記第１実施例と
同様にしてファーストバッファメモリ20およびラストバ
ッファメモリ30から、チェーンバッファメモリ40へのデ
ータ転送が行われる。

そして、チェーンバッファメモリ40へのデータ転送書き
込みが終了すると、このチェーンバッファメモリ40に
は、基準軸データが昇順または降順に連鎖するようデー
タ番号が記憶されることになる。

従って、第３の制御回路80cは、チェーンデータ番号記
憶エリア44に書込まれたデータ番号を、所定の読み出し
規則に従って読み出す。そして、読み出されたデータ番
号順に、基準軸データメモリ10から基準軸データが出力
されるよう読み出し制御する。これにより、基準軸デー
タメモリ10から、基準軸データが昇順または降順にソー
ティング出力されることになる。

このように、本実施例によれば、基準軸データメモリ10
への基準軸データの書き込みと、この基準軸データのソ
ーティング作業とを同時に平行して行うことができるた
め、前記第１実施例に比べ基準軸データのソーティング
をより高速に行うことができる。

これにより、前記第１実施例と同様に、基準軸データを
昇順または降順にソーティング出力することができる。

第３実施例なお、前記第１および第２実施例においては、入力され
た基準軸データをソーティングする場合を例にとり説明
したが、本発明はこれに限らず、基準軸データおよびそ
の組合せ情報（基準軸データとペアを成す情報）からな
るソーティングデータに対しても同様にしてソーティン
グを行うことができる。

第19図には、このような組合せ情報を含むソーティング
データを、その基準軸データに基づきソーティングする
場合の好適な実施例が示されている。なお、本実施例の
回路は、前記第１実施例又は第２実施例のいずれの回路
を用いても形成することができるが、ここでは前記第１
実施例の回路を用いて形成した場合を例にとり説明す
る。

実施例のソーティング回路は、基準軸データメモリ10
と、情報メモリ58とを含む。そして、この回路は、デー
タ発生回路８から出力されるソーティングデータに含ま
れる基準軸データを基準軸データメモリ10に格納し、各
基準軸データと対をなす組合せ情報を情報メモリ58内に
格納するよう形成されている。

ここにおいて、前記基準軸データメモリ10は、データ番
号ポインタ12によって指定される少なくとも１〜Ｎまで
の合計Ｎ個の基準軸データ記憶エリア14を有する。

また、前記情報メモリ58も、データ番号ポインタ12によ
って指定される少なくとも１〜Ｎまでの合計Ｎ個の組合
せ情報記憶エリア58aを有する。

そして、外部のデータ発生回路８からソーティング対象
となる複数の基準軸データが入力されると、その基準軸
データにはその入力順に１〜Ｎのデータ番号が割振られ
る。そして、ソーティングデータに含まれる基準軸デー
タおよびその組み合わせ情報は、データ番号ポインタ12
によって指定される１〜Ｎの基準軸データ記憶エリア14
および組合せ情報記憶エリア58aに順次書込まれる。

このようにして、本実施例のソーティング回路に、外部
からソーティングデータが入力されると、そのソーティ
ングデータに含まれる基準軸データとその組合せ情報
は、データ番号ポインタ12により指定される各記憶エリ
ア14、58aに所定の対応関係をもって順に書込まれるこ
とになる。

このため、基準軸データメモリ10内に記憶されている基
準軸データを前記第１実施例と同様にしてソーティング
処理すれば、チェインバッファメモリ40のチェインデー
タ記憶エリア44には、この基準軸データが昇順または降
順に連鎖するようデータ番号が記憶されることになる。

従って、このようにチェインデータ番号記憶エリア44内
に記憶されたデータ番号を、前記第１実施例と同様にし
て読出し、読出したデータ番号順に情報メモリ58から組
合せ情報を読出せば、情報メモリ58からは、一連の組合
せ情報が基準軸データに基づき昇順または降順にソーテ
ィング出力されることになる。

以上説明したように本実施例によれば、ソーティングデ
ータ自体の情報量が多い場合にも、基準軸データメモリ
10、各バッファメモリ20,30,40を用いたソーティング処
理が短時間で済む。このため、ソーティングデータ１単
位あたりの情報量が多い場合でも、このソーティング処
理を短時間で効率よく行うことが可能となる。

第４実施例第22図には、本発明の好適な第４実施例が示されてい
る。前記第３実施例では、組合せ情報を含むソーティン
グデータを基準軸データに基づきソーティングする回路
を、前記第１の実施例の回路を用いて形成した場合を例
にとり説明した。本実施例では、このようなソーティン
グ回路を前記第２実施例の回路を用いて形成したことを
特徴とする。尚、前記各実施例と対応する部材には同一
符号を付しその説明は省略する。

本実施例のソーティング回路は、情報メモリ58と、前記
第２実施例に示す回路とから構成されている。なお、基
準軸データメモリ10は設けられていない。

そして、外部のデータ発生回路８から出力されるソーテ
ィングデータに含まれる基準軸データは、データ番号カ
ウンタ13,各バッファメモリ20,30へ入力され、各基準軸
データと対をなす組合せ情報は前記第３実施例と同様に
して情報メモリ58内に順次記憶される。もちろん、情報
メモリ58内に順次記憶される組合せ情報の中には、基準
軸データが含まれていてもよい。

そして、基準軸データが入力されると、各バッファメモ
リ20,30,40,データ番号カウンタ13およびソーティング
制御回路80は、前記第２実施例と同様に動作する。従っ
て、チェーンバッファメモリ40のチェーンデータ記憶エ
リア44には、基準軸データが昇順または降順に連鎖する
ようデータ番号が記憶されることになる。

そして、第３の制御回路80cは、チェーンデータ番号記
憶エリア44に記憶されたデータ番号を、前記第１実施例
と同様にして読み出し、読み出したデータ番号順に情報
メモリ58から組合せ情報を読み出し制御する。これによ
り、情報メモリ58から一連の組合せ情報が基準軸データ
に基づき昇順または降順にソーティング出力されること
になる。

第５実施例第23図には、前記第１実施例の変形例が第５実施例とし
て示されている。

本実施例の特徴は、基準軸データメモリ10に格納される
基準軸データの桁数が多い場合でも、各バッファメモリ
20,30,40のメモリ容量を増やすことなく、基準軸データ
を高速ソーティング可能とすることにある。

本実施例において、前記基準軸データメモリ10は、デー
タ番号によりアドレスが指定される基準軸データ記憶エ
リア14を有する。

また、チェインバッファメモリ40は２組設けられ、一方
メモリ40にデータが書き込まれているとき、他方メモリ
40からデータが読み出されるよう構成されている。

そして、データ発生回路８から出力される基準軸データ
を、そのデータ番号順に対応する記憶エリア14へ順次書
き込み記憶する。実施例では、3Mビットで構成される基
準軸データを対応する記憶エリア14へ書き込むよう構成
されている。

このようにして、基準軸データメモリ10内への基準軸デ
ータの書き込みが終了すると、次にこの基準軸データメ
モリ10から、基準軸データの読出が開始される。

本実施例の特徴は、基準軸データを構成する3Mビットデ
ータを所定ビット毎に複数のサーチ桁（このように所定
ビット毎にまとまったサーチ桁がサーチ群に相当する）
に分割し、基準軸データメモリ10からの基準軸データメ
モリの読出しを、サーチ桁単位で行なうことにある。

本実施例では、基準軸データメモリ10内への基準軸デー
タの書き込みが終了すると、まずこの基準軸データメモ
リ10から、下位Ｍビットデータが１〜Ｎのデータ番号順
に順次読み出され、ファーストバッファメモリ20および
ラストバッファメモリ30へ向け出力される。

このようにして読み出された各基準軸データの下位Ｍビ
ットデータは、前記第１実施例と同様にソーティング処
理される。このとき、２組設けられたチェーンバッファ
メモリ40の内の一方にデータの書き込みが行われる。従
って、該一方のチェーンバッファメモリ40のチェーンデ
ータ番号記憶エリア44には、基準軸データの下位Ｍビッ
トデータが昇順または降順に連鎖するよう、データ番号
が書込まれることになる。

本実施例において、第４の制御回路80dは、一方のチェ
ーンバッファメモリ40のチェーンデータ番号記憶エリア
44へ書込まれたデータ番号を、前記第１実施例と同様
に、所定の読み出し規則にしたがって読み出す。そし
て、読み出されたデータ番号順に、基準軸データメモリ
10から基準軸データの中位Ｍビットデータを各バッファ
メモリ20,30へ向け読み出し制御する。

このようにして読み出された基準軸データの中位Ｍビッ
トデータは、同様にしてソーティング処理される。この
とき、２組設けられたチェーンバッファメモリ40の内の
他方にデータの書き込みが行われる。これにより、該他
方のチェーンバッファメモリ40のチェーンデータ番号記
憶エリア44には、基準軸データの中位Ｍビットデータが
昇順または降順に連鎖するよう、データ番号が書き込ま
れることになる。

実施例の第４の制御回路80dは、このようにして他方の
チェーンデータ番号記憶エリア44に書込まれたデータ番
号を、所定の読み出し規則にしたがって読み出しす。そ
して、読み出されたデータ番号順に、基準軸データメモ
リ10から基準軸データの上位Ｍビットデータを順次読み
出し各バッファメモリ20,30へ向け出力する。

そして、このようにしてバッファメモリ20,30に向け出
力された基準軸データの上位Ｍビットを、同様にしてソ
ーティング処理する。このとき、２組設けられたチェー
ンバッファメモリ40の内の一方にデータの書き込みが行
われる、従って、該一方のチェーンバッファメモリ40の
チェーンデータ番号記憶エリア44には、基準軸データの
上位Ｍビットデータが昇順または降順に連鎖するよう、
データ番号が書き込まれることになる。

このように、基準軸データの所定桁をサーチ桁（実施例
ではＭビットデータで構成される桁）として設定し、各
サーチ桁に基づく基準軸データのソーティング処理を、
基準軸データの最下位のサーチ桁から最上位のサーチ桁
に向けサーチ桁をシフトしながら繰返し行う。これによ
り、最上位のサーチ桁に基づく基準軸データのソーティ
ング処理を終了した段階で、チェーンデータ番号記憶エ
リア44には基準軸データが昇順または降順に連鎖するよ
うデータ番号が書き込まれることになる。

従って、実施例の第３の制御回路80cは、最上位のサー
チ桁に基づく基準軸データのソーティング処理終了後、
チェーンデータ番号記憶エリア44内に書き込まれたデー
タ番号を所定の読み出し規則にしたがい読み出す。そし
て、読み出されたデータ番号順に、基準軸データメモリ
10から基準軸データを出力するよう読み出し制御する。

これにより、基準軸データメモリ10が多数の桁で構成さ
れる場合でも、各バッファメモリ20,30,40のメモリ容量
を増加させることなく、簡単な構成でしかも高速ソーテ
ィングを行うことが可能となる。

次に、基準軸データを昇順にソーティングする場合の具
体的な動作を第24図に基づき説明する。ここでは説明を
簡単なものとするために、３進数で構成された基準軸デ
ータをその最下位の桁から１桁ずつソーティングする場
合を例にとり説明する。

まず、基準軸データメモリ10に、第24図（Ａ）に示すよ
うに基準軸データが格納された場合を想定する。

このようにして格納された基準軸データに対し、１回目
のソーティング動作が開始されると、サーチ桁を表わす
変数ｍが０にセットされる。そして、基準軸データメモ
リ10からｍ＝０のサーチ桁の値がそのデータ番号順に読
み出され、読み出されたｍ＝０のサーチ桁の基準軸デー
タが、前述したようにソーティング処理される。これに
より、チェーンデータ番号記憶エリア44には、基準軸デ
ータのｍ＝０のサーチ桁の値が昇順に連鎖するよう、そ
のデータ番号が記憶されることになる。

次に、このチェーンデータ番号記憶エリア44内に書き込
まれたデータ番号を、所定の読み出し規則に従って読み
出し、読み出されたデータ番号順に基準軸データメモリ
10から基準軸データのｍ＝１のサーチ桁の読み出す。こ
のとき、基準軸データメモリ10から読み出される基準軸
データの読み出し順序は、第24図（Ｂ）に示すようにな
る。同図から明らかなように、基準軸データのｍ＝１の
桁の値は、ｍ＝０のサーチ桁の値にしたがって昇順にソ
ーティングされて読み出されることが理解されよう。

そして、読み出されたｍ＝１のサーチ桁の値を同様にし
てソーティング処理すると、チェーンデータ番号記憶エ
リア44には、基準軸データのｍ＝１のサーチ桁の値が昇
順に連鎖するよう、そのデータ番号が記憶されることに
なる。従って、チェーンデータ番号記憶エリア44内に書
き込まれたデータ番号に基づき、基準軸データメモリ10
から基準軸データのｍ＝２のサーチ桁を読み出ことによ
り、この基準軸データメモリ10からは第24図（Ｃ）に示
す順序で、基準軸データのｍ＝２のサーチ桁の値が読み
出されることになる。

このように、ソーティング処理を、基準軸データの最下
位の桁から最上位の桁に向けサーチ桁を１桁ずつシフト
しながら繰返し行うことにより、最上位のサーチ桁ｍ＝
２のソーティング処理を終了した時点で、チェーンデー
タ番号記憶エリア44には、基準軸データが第24図（Ｄ）
で示すように昇順に連鎖するようにデータ番号が書き込
まれることになる。

従って、第３の制御回路80cは、最上位のサーチ桁ｍ＝
２のソーティング処理終了後、チェーンデータ番号記憶
エリア44に書き込まれたデータ番号を所定の読出し順序
で読み出し、基準軸データメモリ10から基準軸データを
読み出す。これにより、基準軸データメモリ10からは、
基準軸データが第24図（Ｄ）に示すように昇順にソーテ
ィング出力されることとなる。

なお、ここでは、基準軸データを昇順にソーティングす
る場合を例にとり説明したが、各サーチ桁の値を降順に
ソーティング処理する動作を繰返すことにより、基準軸
データを降順にソーティング出力することもできる。

また、本実施例ではチェイバッファアメモリ40を２個設
けた場合を例にとり説明した。しかし、これに限らず、
例えばチェーンバンファメモリ40へ書込まれたデータ番
号を一旦他のメモリへ転送した後、該メモリからデータ
番号を所定の読み出し規則にしたがって読み出し、読み
出されたデータ番号順に、基準軸データメモリ10から所
定サーチ桁のＭビットデータを各バッファメモリ20,30
へ向け読み出し制御するよう構成してもよい。このよう
にすることにより、データのソーティング速度は低下す
るが、チェイバッファアメモリ40は１組設けるのみでよ
い。

第６実施例第25図には、本発明の好適な第６実施例が示されてい
る。前記第３実施例では、組合せ情報を含むソーティン
グデータを基準軸データに基づきソーティングする回路
を、前記第１の実施例の回路を用いて形成した場合を例
にとり説明した。本実施例では、このようなソーティン
グ回路を前記第５実施例の回路を用いて形成したことを
特徴とする。

本実施例のソーティング回路は、情報メモリ58と、前記
第２実施例に示す回路とから構成されている。

そして、外部のデータ発生回路８から出力されるソーテ
ィングデータに含まれる基準軸データは、基準軸データ
メモリ10へ入力され、前記第５実施例と同様にしてソー
ティング処理される。従って、チェーンバッファメモリ
40のチェーンデータ記憶エリア44には、基準軸データが
昇順または降順に連鎖するようデータ番号が記憶される
ことになる。

そして、第３の制御回路80cは、チェーンデータ番号記
憶エリア44に記憶されたデータ番号を、前記第５実施例
と同様にして読み出し、読み出したデータ番号順に、情
報メモリ58から組合せ情報を読み出し制御する。これに
より、情報メモリ58から一連の組合せ情報が基準軸デー
タに基づき昇順または降順にソーティング出力されるこ
とになる。

本願ソーティング回路との比較なお、本出願人は、昭和62年８月31日付にて、本願ソー
ティング回路とは別に新なソーティング回路の出願を行
っている（特願昭62−217044号）。

この先願に係るソーティング回路と、本願第１実施例の
ソーティング回路とのソーティング時間を単純に比較す
ると次のようになる。

まず、ソーティングの対象となる基準軸データ数がＮ個
で、各基準軸データのビット数をＭとすると、そのソー
ティング処理時間（RAMのアクセス）は単純比較で次の
ようになる。

まず、先願に係るソーティング回路ではそのソーティン
グ処理時間は、（4N＋２）×Ｍ＋Ｎ＋４サイクル …（１）で表される。なおこの式の詳細は、先願に係る明細書に
すでに詳述されているので、ここではその説明は省略す
る。

ここにおいて、Ｎ＝1023個,M＝15ビット,RAMアクセスを
6.144MHzのサイクルスチールとすると、全処理時間は、 62437サイクル/6.144MHz＝10.2msec となり、１フィールド時間（約16.5mmsec）内に十分に
間にあう。

ところが、データ数が増え、Ｎ＝2047個、Ｍ＝15ビット
のようになった場合には、この処理時間は、 124901サイクル/6.144MHz＝20.3msec となってしまい、１フィールド時間では間にあわなくな
ってしまう。

このように、先願に係るソーティング回路ではソーティ
ングの対象となるデータのビット数に対してそのデータ
個数が多いと、１フィールド分の時間ではそのソーティ
ング処理が行えなくなり不都合が生じる。

特に、後述する三次元画像合成装置では、ソーティング
の対象となるデータの個数（システム的に言えば、表示
ポリゴン数）が増加の傾向にあるので、より高速のソー
ティング回路が必要とされる。

本発明のソーティング回路は、このような要請の下にな
されたものであり、同一の条件で単純計算すると、その
ソーティング処理時間は次のようになる。

まず、基準軸データメモリ10は、一回全ての基準軸デー
タを読出すので、Ｎサイクルを必要とする。

また、ファーストバッファメモリ20は、データの書込み
にＮサイクル、チェインバッファメモリ50へのデータ転
送の際の読出しに2^Mサイクルを必要とする。

ラストバッファメモリ30は、データのチェックのための
読出にＮサイクル、データの書込みに同じくＮサイク
ル、チェインバッファメモリ40へのデータ転送のために
2^Mサイクルを必要とする。

また、チェインバッファメモリ40は、データの書込みの
ためにＮサイクルを必要とする。

これ以外に、各バッファメモリへのデータの書込みに先
だって、ファーストバッファメモリ20およびラストバッ
ファメモリ30の内容を零クリアするために、ファースト
バッファメモリ20の零クリアにＮサイクル、ラストバッ
ファメモリ30の零クリアにＮサイクルを必要とされる。

従って、以上をまとめると、ソーティング処理作業全体
では、７×Ｎ＋２×2^Mサイクル …（２）の処理時間が必要となる。従って、ソーティングの対象
となる基準軸データのビット数をＭ＝15と仮定し、記述
軸データの個数Ｎを変え、そのソーティング処理時間を
前記第１式、第２式に基づき演算すると、先願に係るソ
ーティング処理時間および本発明に係るソーティング回
路の処理時間は次表で表わされる。

この第１表から明らかなように、ソーティングの対象と
なる基準軸データの個数が少ない場合には、先願のソー
ティング回路の処理時間のほうが短いが、ソーティング
対象となる基準軸データの個数が増えるにしたがい、本
発明のソーティング回路の処理時間が大幅に短くなるこ
とが理解されよう。

従って、本発明によれば、基準軸データの個数が増加す
るにしたがい、そのソーティング時間を大幅に短縮した
高速ソーティングが可能となる。

用途以上説明したように、本発明に係るソーティング回路
は、大量の基準軸データを高速ソーティングすることが
できる。このため基準軸データが各種の情報と組合さ
れ、データ量が大きなソーティングデータとなった場合
でも、このようなデータ量の多い各種ソーティングデー
タをその基準軸データに基づき高速でソーティング処理
することが可能となり、例えばデータベースの情報を日
付等の基準軸データに基づきソーティングする場合やそ
の他の用途に広範囲に用いることができる。

具体例第５図には本発明が適用された三次元画像合成装置の好
適な具体例が示されており、実施例の装置は、ポリゴン
情報発生回路50,ポリゴン情報転送回路52,ソーティング
回路S,ポリゴン表示回路60を含み、立体の二次元画像、
すなわち擬似三次元画像を、ポリゴン表示回路60のCRT
上に合成表示するように形成されている。

本実施例において、前記ポリゴン情報発生回路50は、三
次元の立体情報を扱いこれに回転，平行移動，透視，投
影等の各種変換を施して、表示すべき三次元情報を二次
元多角形の組合せ情報に変換し、各多角形の頂点の（X,
Y）座標をポリゴン情報として演算している。

なお、ポリゴン情報発生回路50は、各多角形の奥行方向
の表示地点、すなわち各多角形中心のＺ座標をもポリゴ
ン情報として演算し、さらに必要に応じて多角形の色情
報，輝度情報などを付随情報として演算する。

なお、本実施例においては説明を簡単にするために、付
随情報として色情報が演算されるものとして以後の説明
を行う。

第６図にはこのようにして演算された多角形のポリゴン
情報の一例が示されている。

ポリゴン情報発生回路50が、このようにして各多角形の
ポリゴン情報（多角形の頂点位置におけるXY座標、中心
点におけるＺ座標および色情報）を演算すると、ポリゴ
ン情報転送回路52は、第７図に示すように、各多角形の
ポリゴン情報を、Ｚ座標データと、それ以外のデータと
に分離し、Ｚ座標データを基準軸データメモリ10に書込
み、それ以外のデータ（組分せ情報）をXYRAM58へ書込
む。

このようにして、ポリゴン情報発生回路50から、各多角
形のポリゴン情報が演算出力されるたびに、このポリゴ
ン情報のＺ座標は基準軸データメモリ10内に順次入力さ
れ、またＺ座標以外のポリゴン情報はXYRAM58へ順次入
力される。このとき、データ数レジスタ54は、ポリゴン
情報発生回路50から演算出力される多角形の数をカウン
トし、各ラスタ走査ごとに表示多角形の数を検出してい
る。

第８図には、実施例の三次元画像合成装置に用いられる
ソーティング回路Ｓが示されており、実施例のソーティ
ング回路Ｓは、CRTの一画面ごとに演算される複数のポ
リゴン情報を、そのＺ座標値が小さいものから順に昇順
にソーティングし、ポリゴン表示回路60に向けて出力す
る。

従って、第９図に示すようにCRTの画面上を基準点と
し、その奥行方向に向けてＺ座標が大きくなるようにXY
Zの三次元座標を設定すると、ソーティング回路Ｓから
は、画面の手前に表示される多角形、すなわち優先度の
高い多角形のポリゴン情報から順にソーティング出力さ
れることになる。

そして、ポリゴン表示回路60は、このように出力される
各多角形のポリゴン情報を、その優先度を基にして画像
合成し、例えば複数の多角形が重合せ表示されるような
場合は、その優先度の高い多角形が優先的に表示される
よう三次元画像の合成を行う。

ポリゴン情報発生回路第10図には、飛行機用操縦シュミレータ装置に適用され
たポリゴン情報発生回路50の具体的な構成が示されてお
り、実施例のポリゴン情報発生回路50は、飛行中におけ
る各種フライト条件のシュミレーション画像を演算出力
している。

まず、三次元演算回路50−４は、飛行機を原点とした移
動座標系を想定する。

そして、メインCPU回路50−２から、飛行機の現在位置
を表す移動座標が出力されると、この三次元演算回路50
−４は三次元情報メモリ50−３から所定の多面体データ
の読出しを行う。実施例において、三次元情報メモリ50
−３に書き込まれた情報は、固定座標系を用いて表され
ているため、三次元演算回路50−４は、三次元情報メモ
リ50−３から読み出した情報を移動座標系の座標データ
に変換する必要がある。

この変換には、座標の回転と平行移動という２つの演算
要素の組合せで実現することができ、この演算の過程に
おいて、パイロットの視野に入らないことが判明した情
報（Ｚ＜０など）が除去される。変換により求められた
状況データは、メインCPU回路50−２へ向け出力され
る。そして、座標変換された各多面体情報は、次に表示
画面がＺ−０の平面上にあるとして、Ｚ＜０の視点に向
って透視投影変換される。

このような透視投影変換により、前記各多面体データ
は、多面体の各頂点座標をＸ、Ｙの二次元に変換した点
情報の集りとして表される。

また、このような透視投影変換を行うにあたり、視点と
多面体の各頂点座標との距離を求めておく。

そして、前記透視投影変換により求められた二次元の点
座標（多面体の頂点座標）を、多面体表面を表す各多角
形毎に分類し、分類した多角形がパイロットの視野すな
わち画面の視野に入るか否かをチェックし、視野に全く
入らない多角形は除去する。

その後、この三次元演算回路50−４は、受付け座標範囲
に入る多角形に対し、当該多角形の中心点におけるＺ座
標の値を代表値として決定する。

これと同時に、三次元演算回路50−４は、受付け座標範
囲に入る各多角形の付随データ、実施例においては色情
報を演算する。

そして、三次元演算回路50−４は、このようにして求め
た各多角形の頂点のXY座標、その中心位置のＺ座標およ
び色情報をポリゴン情報として各多角形毎に出力する。

実施例のポリゴン情報発生回路50から出力される各多角
形のポリゴン情報は17ワードで構成され、その中の１ワ
ードが中心点のＺ座標、残りの16ワードが多角形の頂点
のXY座標、色情報などを表すために用いられている。

また、前記１ワードは16ビットで構成されている。

このようにして、実施例のポリゴン情報発生回路50は、
パイロットの視野に入る状況を複数の多角形の組合せ情
報に変換し、各多角形のポリゴン情報をソーティング回
路Ｓへ向け順次出力することになる。

ここにおいて、各多角形はそのポリゴン情報に含まれる
Ｚ座標値が小さいほど画面の手前に表示されるため、ポ
リゴン情報に含まれるＺ座標値の値が小さいほど当該多
角形の優先度が高いことになる。従って、このようにラ
ンダムに出力される各多角形のポリゴン情報をそのＺ座
標値の小さい順にソーティングしてやれば、ポリゴン表
示回路22による三次元画像の合成を簡単かつ迅速に行う
ことが可能となる。

ソーティング回路本発明のソーティング回路は、所定の基準軸データを含
む複数のデータを、前記基準軸データに基づきソーティ
ングすることを特徴とするものである。

第８図には、本実施例に係るソーティング回路Ｓの具体
的な構成が示されている。

このソーティング回路Ｓは、基準軸データメモリ10と、
情報メモリとして用いられるXYRAM58とを含む、そし
て、ポリゴン情報発生回路50から出力される一画面分の
多角形のポリゴン情報のうち、基準軸データとしてのＺ
軸情報が基準軸データメモリ10に書込まれ、残りの情報
がXYRAM58に書込まれる。

ここにおいて、前記基準軸データメモリ10は、ファース
トバッファメモリ20,ラストバッファメモリ30およびチ
ェインバッファメモリ40とともに、一群のソーティング
RAM70として形成されている。

そして、ソーティング制御回路80は、このソーティング
RAM70のデータの書込み，読出し制御し、基準軸データ
が昇順に連鎖するようそのデータ番号をチェインバッフ
ァ40に書込む。

そして、このチェインバッファ40に書込まれたデータ番
号を、前述した所定の読出し規則に従って読出す。その
後、読出したデータ番号順に、前記XYRAM58から一画面
分の多角形のポリゴン情報を読出す。

このようにして、本実施例の装置は、ポリゴン情報発生
回路50から出力される一画面分のポリゴン情報を、その
Ｚ座標に基づき昇順にソーティングし、ポリゴン表示回
路60へ向け出力することができる。

以下、前記第３実施例のソーティング回路（第19図に示
すソーティング回路）を例にとり、その具体的な回路構
成を詳細に説明する。

（ａ）第１の制御回路80a 第11図には、第19図に示す第１の制御回路80aの具体的
な回路構成が示されており、第12図にはその動作を示す
フローチャートが示されている。

この第１の制御回路80aは、基準軸データメモリ10に書
込まれたＺ軸データを、そのデータ番号順に順次に読出
す。そして、読出したＺ軸データをアドレスとして、対
応するデータ番号をファーストバッファメモリ20,ラス
トバッファメモリ30へ書込む。これと共に、ラストバッ
ファメモリ30のデータ番号が更新記録されたとき、更新
前のデータ番号をアドレスとして、更新後のデータ番号
をチェインバッファメモリ40へ書込む。

本実施例において、この第１の制御回路80aは、データ
番号ポインタ12と、データ数レジスタ54と、比較判定回
路110と、ステップ１制御回路112とを含む。

ここにおいて、データ番号ポインタ12は、前述したよう
に、基準軸データメモリ10の書込み／読出しアドレスと
して１〜Ｎのデータ番号を出力するように形成されてい
る。

従って、基準軸データメモリ10からＺ軸データを、各バ
ッファメモリ20,30および40へ向け出力する場合に、こ
のデータ番号ポインタ12は、第３図に示すようにデータ
番号を1,2,3,…の順に順次インクリメント出力する。

これにより、基準軸データメモリ10からは、データ番号
順にＺ軸データが順次各バッファメモリ20,30のアドレ
ス入力端子へ向け出力されると共に、ステップ１制御回
路112へ向け出力されることになる。

このとき、データ番号ポインタ12から出力されるデータ
番号は、ファーストバッファメモリ20、ラストバッファ
メモリ30およびチェインバッファメモリ40のデータ入力
端子Ｉへ向け出力されると共に、比較判定回路110へ向
けても出力されている。

従って、ファーストバッファメモリ20およびラストバッ
ファメモリ30内の各データ番号記憶エリア24,34には、
例えば第12図のフロー1000で示すように、アドレス入力
端子Ａに入力される基準軸データを書込みアドレスとし
て、データ入力端子Ｉに入力されるデータ番号が書込み
記憶されることになる。

このとき、ラストデータ番号記憶エリア34内のデータ番
号が更新記録されると、更新前のデータは、出力端子Ｏ
からチェインバッファメモリ40のアドレス入力端子Ａへ
向け出力される。

従って、第12図のフロー1100で示すように、チェインバ
ッファメモリ40のチェインデータ番号記憶エリア44に
は、ラストバッファメモリ30から出力される更新前のデ
ータ番号をアドレスとして、データ番号ポインタ12から
出力される新なデータ番号が書込み記憶されることにな
る。

このようなデータの転送書込み作業は、データ番号ポイ
ンタ12から新たなデータ番号がインクリメント出力され
る毎に繰返して行われる。

そして、比較判定回路110は、データ番号ポインタ12か
らインクリメント出力されるデータ番号が、データ数レ
ジスタ54から出力されるCRT−画面分のポリゴン情報数
と一致した時点で、ステップ１制御回路112へ向け転送
制御終了信号を出力する。これにより、ステップ１制御
回路112は、バッファメモリ20,30および40に対する、一
連のデータ書込み作業を終了する。

次に、ソーティング回路は、ステップ２の動作に切替わ
る。そして、ラストバッファメモリ30の各データ番号記
憶エリア34に記憶されたデータ番号を書込みアドレスと
して、所定の対応関係にあるファーストバッファ20内の
データ番号記憶エリア24内のデータ番号を、チェインバ
ッファメモリ40内のデータ番号記憶エリア44へ書込むと
いう一連の動作を開始する。

（ｂ）第２の制御回路80b 第13図には、このようなステップ２の転送制御を行う第
２の制御回路80bの具体的な回路構成が示されており、
第14図にはその動作を示すフローチャートが示されてい
る。

この第２の制御回路80bは、ステップ２制御回路210と、
スタートアドレスセレクタ212と、スタートアドレスポ
インタ214と、アドレスポインタ22および32とを含む。

そして、ステップ２制御回路210は、ステップ２の動作
が開始されると、第14図に示すフロー2000に従い各アド
レスポインタ22、32を「０」リセットする。そして、ア
ドレスポインタ22の出力する「０」アドレスで指定され
るファーストデータ記憶エリア24に、データ番号が書込
まれているか否かの判断を行う。このとき、このアドレ
ス０番地にデータ番号が記憶されていない場合には、ア
ドレスポインタ22をインクリメントし、インクリメント
された新たなアドレスで指定されるファーストデータ番
号記憶エリア24に、データ番号が記憶されているか否か
の判別を行う。このような判別操作を、データ番号が記
憶されたファーストデータ番号記憶エリア24が検出され
るまで、第14図に示すフロー2100に従って繰返し行う。

そして、データ番号が記憶されたファーストデータ番号
記憶エリア24が検出されると、そのときのデータ番号を
スタートアドレスとしてスタートアドレスポインタ310
へセットする。従って、例えば第３図に示す場合を例に
とると、最小の基準軸データ記憶されたファーストデー
タ番号記憶エリア24（この場合にはアドレス０で指定さ
れる記憶エリア24）から、その基準軸データに対応する
データ番号「５」が読出され、スタートアドレスとして
スタートアドレスポインタ310にセットされることにな
る。

このようにして、スタートアドレスがセットされると、
次に第14図のフロー2200に従って、ラストデータ番号記
憶エリア34に記憶されたデータ番号を書込みアドレスと
し、これと所定の対応関係にあるファーストデータ番号
記憶エリア24に記憶されたデータ番号を、チェインデー
タ番号記憶エリア44へ書込むという一連の動作を繰返し
て行う。これにより、例えば第３図に示すように、チェ
インデータ番号記憶エリア44には、基準軸データ（この
場合には、Ｚ軸データ）が昇順に連鎖するようにデータ
番号が書込まれることになる。

このとき、例えば第４図に示すように、データ番号記憶
エリア24、34内に、データ番号が書込まれていない記憶
エリアが存在する場合には、第14図に示すフロー2300に
従って、ファーストデータ番号記憶エリア24内にデータ
番号が書込まれているか否か判別しながら、データ番号
が書込まれているファーストデータ番号記憶エリアに24
が検出されるまでアドレスポインタ24をインクリメント
する。

そして、データ番号が記憶されたファーストデータ番号
記憶エリア24が検出されると同時に、フロー2200に従っ
てチェインデータ番号記憶エリア44へのデータ番号書込
みを同様にして行う。

（ｃ）フラグメモリ214 ところで、数百個または数千個の単位で基準軸データを
ソーティングする場合には、基準軸データが書込まれて
いるファーストデータ番号記憶エリア24を検出するため
に、ある程度まとまった時間を必要とする。しかし、三
次元画像装置では、一連のソーティング動作を１フィー
ルド時間（1/60秒）以内に終了しなければならないこと
を考えると、前記検出時間は無視できない値となる。

このため本実施例では、このような検出時間を大幅に短
縮し、ソーティングをより高速で行うことを可能とする
ためにフラグメモリ214を設けている。

第16図には、このフラグメモリ214の構成が、ファース
トデータ番号記憶エリア24と対応付けて示されている。

このフラグメモリ214は、各ファーストデータ番号記憶
エリア24に1:1に対応した複数の１ビットのフラグ記憶
エリア214aを有し、ファーストデータ番号記憶エリア24
にデータが格納されたときは、対応する１ビットフラグ
エリア214aにフラグがセットされるよう形成されてい
る。

実施例においてこのフラグメモリ214は、８個の１ビッ
トフラグエリアを１グループ単位としてフラグアドレス
により指定され、フラグアドレスによって指定される一
群のフラグエリアからフラグ情報をグループ単位（８ビ
ットデータ）で出力するように形成されている。

従って、例えばフラグアドレス000Hを指定すると、この
フラグメモリ214から出力される８ビット分のフラグ情
報から、アドレス0000H〜0007Hで指定される８アドレス
分のファーストデータ記憶エリア24内にデータ番号の書
込まれている記憶エリアが存在するか否かを一度に判別
することができる。

そして、このようなフラグメモリ214を用いてデータ番
号が書込まれているデータ番号記憶エリア24を検出して
る途中で、データ番号の書込みを示すフラグが検出され
ると、このときフラグアドレスによって指定される８ビ
ット分のフラグ情報が、第15図に示すようシフトレジス
タ210aに書込まれる。

そして、ステップ２制御回路210は、シフトレジスタ210
aの内容を、１ビットずつ右へシフトしていき、データ
番号が書込まれているファーストデータ番号記憶エリア
24を検出する。

このようにして、実施例の210はフラグメモリ214のフラ
グアドレスを000Hから順にインクリメントしながら、そ
のフラグメモリ214の内容を８ビットずつ順に読出し、
データ番号が書込まれているファーストデータ番号記憶
エリア24を高速で検出している。

なお、このフラグメモリ214へのフラグの書込みは、第1
1図に示すステップ１制御回路112により行われる。すな
わち、このステップ１制御回路112は、ファーストバッ
ファメモリ20のファーストデータ番号記憶エリアにデー
タ番号を書込むと同時に、フラグメモリ214の対応する
フラグを順次セットしていく。

このようにすることにより、第14図に示すステップ２の
動作、すなわち各バッファメモリ20および30からチェイ
ンバッファメモリ40へのデータ書込み作業をより高速で
行うことが可能となる。

また、このようなフラグメモリ214を用れば、このフラ
グメモリ214を零クリアすることにより、これらバッフ
ァメモリ20,30を零クリアする必要はなくなる。

また、本実施例において、フラグアドレスによって指定
されるフラグメモリ214の１グループ単位を８ビットと
したのは、メモリの物理的なデータサイズと、確率論的
な見地から最適であると考えたからである。

例えば、2¹⁵個のアドレスに、2¹¹個のデータがランダム
に書込まれたときに、何ビット単位で読出せば読出し時
間が最小となるかという問題を考える。このとき、各フ
ラグアドレスによって指定されるビット単位を、16ビッ
ト、８ビット、４ビット、２ビットとして計算すると、
４ビット単位が最小となる。しかし、データが同じアド
レスに重なる場合もあるので、フラグアドレスによって
指定されるビット単位を４ビットと８ビットとした場合
に最小値がくるものと思われるが、物理的なメモリの構
成により、８ビット単位を選んだ。

（ｄ）第３の制御回路80c また以上説明したように、チェインバッファメモリ40内
の各データ番号記憶エリア44内に、基準軸データが昇順
に連鎖するようにデータ番号が書込まれると、次に、書
込まれたデータ番号を所定の読出し規則にしたがい読出
し、読出したデータ番号順にXYRAM58からポリゴン情報
をソーティング出力するというステップ３の動作が開始
される。

第17図には、このようなステップ３の動作を行う第３の
制御回路80cの具体的な回路構成が説明されており、第1
8図にはその動作を示すフローチャートが示されてい
る。

本実施例において、前記第３の制御回路80cは、ステッ
プ３制御回路312,データ数カウンタ314,比較判定回路31
6,アドレスポインタ42,スタートアドレスポインタ310,
セレクタ318,ラッチ320を含む。

そして、ステップ３制御回路312は、ステップ３の動作
が開始されると、まずアドレスポインタ42およびデータ
数カウンタ314をリセットする。次に、セレクタ318をス
タートアドレスポインタ310側に切り替え、スタートア
ドレスポインタ310内に予めセットされているデータ番
号をスタートアドレスとしてセレクタ318,ラッチ320を
介してXYRAM58へ向け出力する。

これにより、例えば第３図に示すように、スタートアド
レスとしてデータ番号「５」が設定されている場合に
は、XYRAM58からは、このデータ番号「５」によって特
定されるポリゴン情報が出力されることになる。

また、このような読出し動作と同期して、データ数カウ
ンタ314の値は一つインクリメントされ、これと同時に
ラッチ320から出力されるデータ番号は次の読出しアド
レスとしてアドレスポインタ42にセットされる。

このようにして、最初のポリゴン情報が読出されると、
次にステップ３制御回路312は、セレクタ318をスタータ
アドレスポインタ310側からチェインバッファメモリ40
側へ切換える。そして、ステップ３制御回路312は、第1
8図に示すフロー3000にしたがいXYRAM58からポリゴン情
報をＺ軸データに基づきソーティング出力する。

すなわち、前記アドレスポインタ42から、読出しアドレ
スとしてデータ番号が出力されると、この読出しアドレ
スによって指定されるチェインデータ記憶エリア44から
セレクタ318,ラッチ320を介してデータ番号が読出され
る。そして、読出されたデータ番号を読出しアドレスと
してXYRAM58からポリゴン情報が出力されると共に、前
記データ番号は、新たな読出しアドレスとしてアドレス
ポインタ42にセットされる。

実施例のソーティング回路は、このようなポリゴン情報
の読出し作業を繰返して行う。

このとき、データ数カウンタ314は、XYRAM58をアクセス
した回数、すなわちXYRAM58からソーティング出力され
るポリゴン情報の数をカウントし、そのカウント値を比
較判定回路316へ向け出力している。

そして、比較判定回路316は、このデータ数カウンタ314
の値が、データ数レジスタ54より予めカウントされるポ
リゴン情報と一致したとき、ステップ３制御回路312へ
終了信号を出力する。

このようにして、本実施例のソーティング回路は、一連
のソーティング作用を終了する。

なお、本発明は、前記実施例に限定されるものではな
く、本発明の要旨の範囲内で各種の変形実施が可能であ
ることをいうまでもない。

［発明の効果］以上説明したように、本発明によれば、多数の基準軸デ
ータを簡単な回路で、しかも高速でソーティング出力す
ることができる。

特に、本発明によれば、基準軸データのビット数に対
し、基準軸データの個数が多い場合にそのソーティング
作用を高速で行うことができ、多数のデータをソーティ
ング対象とする場合に極めて有効なものとなる。

さらに、本発明によれば、基準軸データが各種の情報と
組合され、データ量が大きなソーティングデータとなっ
た場合でも、このようなデータ量の多いソーティングデ
ータを、その基準軸データに基づき高速ソーティングす
ることができるため、各種用途に幅広く用いることがで
きる。

【図面の簡単な説明】

第１図は本発明に係るソーティング回路の基本的な構成
を示す説明図、第２図は基準軸データメモリから各バッファメモリへの
データ転送動作を示す説明図、第３図、第４図はファーストバッファメモリおよびラス
トバッファメモリからチェインバッファメモリへのデー
タ転送作業を示す説明図、第５図は本発明のソーティング回路が適用された三次元
画像合成装置の一例を示すブロック回路図、第６図および第７図は、第５図に示すポリゴン情報発生
回路から演算出力されるポリゴン情報の説明図、第８図は第５図に示す三次元画像合成装置に用いられる
本発明のソーティング回路のブロック回路図、第９図は第５図に示す回路を用いて表示される画像の三
次元概念図、第10図は第５図に示すポリゴン情報発生回路の具体的な
構成を示すブロック回路図、第11図は本発明のソーティング回路の回路構成の一例を
示すブロック回路図、第12図は第11図に示す回路の動作を示すフローチャート
図、第13図は本発明のソーティング回路の具体的な回路構成
の一例を示すブロック回路図、第14図は第13図に示す回路の動作を示すフローチャート
図、第15図は第13図に示す回路のシフトレジスタ内に登録さ
れたフラグの説明図、第16図は、第13図に示す回路で用いられるフラグメモリ
の構成を、ファーストデータ番号記憶エリアと対応付け
て示す説明図、第17図は本発明のソーティング回路の具体的な回路構成
の一例を示すブロック回路図、第18図は第17図に示す回路の動作を示すフローチャート
図、第19図は、本発明の好適な第３実施例の説明図、第20図は、データを降順にソーティングする場合に、フ
ァーストバッファメモリおよびラストバッファメモリか
らチェインバッファメモリへデータを転送する動作を示
す説明図第21図は、本発明の好適な第２実施例の説明図、第22図は、本発明の好適な第４実施例の説明図、第23図は、本発明の好適な第５実施例の説明図、第24図は、（Ａ），（Ｂ），（Ｃ），（Ｄ）は、第23図
に示すソーティング回路のソーティング動作の一例を示
す説明図、第25図は、本発明の好適な第６実施例の説明図である。 10……基準軸データメモリ、 12……データ番号ポインタ、 13……データ番号カウンタ、 20……ファーストバッファメモリ、 24……ファーストデータ番号記憶エリア、 30……ラストバッファメモリ、 34……ラストデータ番号記憶エリア、 40……チェインバッファメモリ、 44……チェインデータ番号記憶エリア、 58……情報メモリ 80……ソーティング制御回路、 80a……第１の制御回路、 80b……第２の制御回路、 80c……第３の制御回路、 80d……第４の制御回路。

Claims

【特許請求の範囲】

【請求項１】複数のデータとこれに１対１に対応する所
定の基準軸データが入力され、前記複数のデータを前記
基準軸データに基づきソーティングする回路であって、前記複数のデータを、この複数のデータと前記基準軸デ
ータに共通するデータ番号に対応させて記憶する情報メ
モリと、前記基準軸データが入力されるソーティング手段と、を含み、前記ソーティング手段は、入力される各基準軸データに対応したデータ番号を発生
するデータ番号発生手段と、前記基準軸データに基づきアドレスが指定されるファー
ストデータ番号記憶エリアを有し、各記憶エリアに対応
する基準軸データが最初に入力されたとき、この記憶エ
リアにデータ番号発生手段の発生するデータ番号を記憶
するファーストバッファメモリと、前記基準軸データに基づきアドレスが指定されるラスト
データ番号記憶エリアを有し、各記憶エリアに対応する
基準軸データが入力される毎に、この記憶エリアにデー
タ番号発生手段の発生するデータ番号を更新記憶するラ
ストバッファメモリと、データ番号に基づきアドレスが指定されるチェインデー
タ番号記憶エリアを有するチェインバッファメモリと、前記ラストバッファメモリのデータ番号が更新される毎
に、更新前のデータ番号で指定されるチェインデータ番
号記憶エリアに、更新される新たなデータ番号を書込む
第１の制御手段と、前記ファーストバッファメモリおよびラストバッファメ
モリへのデータ番号書き込み終了後、ラストデータ番号
記憶エリアに記憶されたデータ番号で指定されるチェイ
ンデータ番号記憶エリアに、該ラストデータ番号記憶エ
リアと所定の対応関係にある前記ファーストデータ番号
記憶エリアに記憶されたデータ番号を書込むことによ
り、チェインデータ番号記憶エリア内に基準軸データが
昇順または降順に連鎖するようデータ番号を書込む第２
の制御手段と、チェインデータ番号記憶エリア内に書込まれたデータ番
号を所定の読出し規則に従い読出し、読出したデータ番
号順に前記情報メモリからデータを読み出す第３の制御
手段と、を含み、複数のデータを基準軸データに基づきソーティ
ング出力することを特徴とするソーティング回路。
【請求項２】複数桁からなる複数の基準軸データをソー
ティングする回路であって、入力される各基準軸データに対応するデータ番号を発生
するデータ番号発生手段と、前記各基準軸データを、そのデータ番号に対応させて記
憶する基準軸データメモリと、前記基準軸データメモリから出力される複数桁の基準軸
データを１乃至複数桁からなる複数のサーチ群に分割し
た場合に、各サーチ群の値に基づきアドレスが指定され
るファーストデータ番号記憶エリアを有し、各記憶エリ
アに対応する各サーチ群が最初に入力されたとき、この
記憶エリアにデータ番号発生手段の発生するデータ番号
を記憶するファーストバッファメモリと、前記基準軸データメモリから出力される前記各サーチ群
の値に基づきアドレスが指定されるラストデータ番号記
憶エリアを有し、各記憶エリアに対応する各サーチ群が
入力される毎に、この記憶エリアにデータ番号発生手段
の発生するデータ番号に更新するラストバッファメモリ
と、データ番号に基づきアドレスが指定されるチェインデー
タ番号記憶エリアをそれぞれが有する２つのチェインバ
ッファメモリと、前記ラストバッファメモリのデータ番号が更新される毎
に、更新前のデータ番号で指定される前記少なくとも２
つのチェインバッファメモリの中のいずれか一の前記チ
ェインデータ番号記憶エリアに、更新される新たなデー
タ番号を書き込む第１の制御手段と、前記ファーストバッファメモリおよびラストバッファメ
モリへのデータ番号書き込み終了後、ラストデータ番号
記憶エリアに記憶されたデータ番号で指定される前記い
ずれか一のチェインデータ番号記憶エリアに、該ラスト
データ番号記憶エリアと所定の対応関係にある前記ファ
ーストデータ番号記憶エリアに記憶されたデータ番号を
書込むことにより、前記いずれか一のチェインデータ番
号記憶エリア内に前記各サーチ群の値が昇順または降順
に連鎖するようデータ番号を書き込む第２の制御手段
と、前記基準軸データのサーチの対象となるサーチ群を下位
桁から上位桁に向けて更新し、新たにサーチ対象となっ
た前記サーチ群を前記第２の制御手段によってチェイン
データ番号記憶エリアに書き込まれた順に前記基準軸デ
ータメモリから読み出して、前記第１の制御手段および
前記第２の制御手段による処理を前記チェインバッファ
メモリを切り替えながら前記基準軸データの最上位側に
位置するサーチ群に至るまで繰り返し行う第４の制御手
段と、最上位側のサーチ群のソーティング処理が終了した後、
対応する前記チェインデータ番号記憶エリア内に書き込
まれたデータ番号を所定の読出し規則に従い読出し、読
出したデータ番号順に基準軸データメモリから各基準軸
データをソーティング出力する第３の制御手段と、を含むことを特徴とするソーティング回路。
【請求項３】複数のデータとこれに１対１に対応する複
数の桁からなる所定の基準軸データをソーティングする
回路であって、前記複数のデータを、これら複数のデータと前記基準軸
データに共通するデータ番号に対応させて記憶する情報
メモリと、前記基準軸データが入力されるソーティング手段と、を含み、前記ソーティング手段は、各基準軸データに対応する前記データ番号を発生するデ
ータ番号発生手段と、前記各基準軸データを、そのデータ番号に対応させて記
憶する基準軸データメモリと、前記基準軸データメモリから出力される複数桁の基準軸
データを１乃至複数桁からなる複数のサーチ群に分割し
た場合に、各サーチ群の値に基づきアドレスが指定され
るファーストデータ番号記憶エリアを有し、各記憶エリ
アに対応する各サーチ群が最初に入力されたとき、この
記憶エリアにデータ番号発生手段の発生するデータ番号
を記憶するファーストバッファメモリと、前記基準軸データメモリから出力される前記各サーチ群
の値に基づきアドレスが指定されるラストデータ番号記
憶エリアを有し、各記憶エリアに対応する各サーチ群が
入力される毎に、この記憶エリアにデータ番号発生手段
の発生するデータ番号を更新記憶するラストバッファメ
モリと、データ番号に基づきアドレスが指定されるチェインデー
タ番号記憶エリアをそれぞれが有する２つのチェインバ
ッファメモリと、前記ラストバッファメモリのデータ番号が更新される毎
に、更新前のデータ番号で指定される前記少なくとも２
つのチェインバッファメモリの中のいずれか一の前記チ
ェインデータ番号記憶エリアに、更新される新たなデー
タ番号を書き込む第１の制御手段と、前記ファーストバッファメモリおよびラストバッファメ
モリへのデータ番号書き込み終了後、ラストデータ番号
記憶エリアに記憶されたデータ番号で指定される前記い
ずれか一のチェインデータ番号記憶エリアに、該ラスト
データ番号記憶エリアと所定の対応関係にある前記ファ
ーストデータ番号記憶エリアに記憶されたデータ番号を
書込むことにより、前記いずれか一のチェインデータ番
号記憶エリア内に前記各サーチ群の値が昇順または降順
に連鎖するようデータ番号を書き込む第２の制御手段
と、前記基準軸データのサーチの対象となるサーチ群を下位
桁から上位桁に向けて変更し、新たにサーチ対象となっ
た前記サーチ群を前記第２の制御手段によってチェイン
データ番号記憶エリアに書き込まれた順に前記基準軸デ
ータメモリから読み出して、前記第１の制御手段および
前記第２の制御手段による処理を前記チェインバッファ
メモリを切り替えながら前記基準軸データの最上位側に
位置するサーチ群に至るまで繰り返し行う第４の制御手
段と、最上位側のサーチ群のソーティング処理が終了した後、
対応する前記チェインデータ番号記憶エリア内に書き込
まれたデータ番号を所定の読出し規則に従い読出し、読
出したデータ番号順に前記情報メモリからデータを読み
出す第３の制御手段と、を含み、複数のデータを基準軸データに基づきソーティ
ング出力することを特徴とするソーティング回路。
【請求項４】請求項（１）〜（３）のいずれかにおい
て、前記データ番号発生手段はデータ番号ポインタを用いて
形成されていることを特徴とするソーティング回路。
【請求項５】請求項（１）〜（３）のいずれかにおい
て、前記データ番号発生手段はカウンタを用いて形成されて
いることを特徴とするソーティング回路。
【請求項６】請求項（１）、（３）〜（５）のいずれか
かにおいて、前記情報メモリには、（X,Y,Z）からなる複数の三次元
情報のうち、少なくともその（X,Y）の二次元情報がデ
ータ番号順に記憶され、前記ソーティング手段には、前記三次元情報に含まれる
Ｚ軸データが基準軸データとして入力され、前記情報メモリに含まれる三次元情報をそのＺ軸データ
に基づき昇順または降順にソーティング出力することを
特徴とするソーティング回路。