JPH02224018A - ソーティング回路 - Google Patents

Abstract

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

Description

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

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

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

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

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

このためには、メモリ間における全Ｚ軸データのデータ
転送を、多数回に渡って繰返し行わなければならない。

従って、データのソーティング作業を高速で行うことが
できないとい・）問題があった。

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

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

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

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

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

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

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

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

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

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

そして、本発明のソーティング回路では、チェインデー
タ番号記憶エリア内に書込まれたデータ番号を、所定の
読出し規則に従って読出している。

そして、入力された基準軸データを、このように【７で
読出されたデータ番号順に出力するように読出し制御し
Ｃいる。

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

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

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

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

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

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

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

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

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

実施例において、−の基準軸データの読出１７は、デー
タ番号ポインタ１２か〔・読出アドレスと１７でデ〜＝
−り番号が１〜・Ｎの順で順次出力されることにより行
われる。そ【、て、データ番すによりアトｉノスが指定
されると、指定された尼準軸デ・−・−夕記憶エリフ゛
］４から一ツアーストバッファメモリ２０およびラスト
バッファメモリ３０　ｉ、：向け基準軸データが読出さ
れ０．乙。

（ｂ）　　バッツ丁メモリ２０，３０への筈込みまた、
前記ファー・ストパップアメモリ２０およびラストバッ
ファメモリ３０は、基準軸データが取り得る値の全てに
１対１に対応するファーストデータ番号記憶ボリア２４
、ラス［・データ番号記憶エリア３４を有する。

実施例のように、基準軸データがＭビットで構成されて
いる場合にζｔ、０，し２・・・（２’−１）の合計２
Ｍ個の値を取り得る。

従って、前記ファーストバッファメモリ２０には、少な
くとも０．し２・・・（２′Ａ−１）の名アドレスで指
定される２Ｍ個のファーストデータ番号記憶エリア２４
が設けられている。同様にして、前記ラストバッファメ
モリ３０に、少なくとも０゜し２・・・（２’−１）の
各アドレスで指定される２Ｍ個のラストデータ番号記憶
エリア３４が設けらている。

また、これらファーストデータ番号記憶エリア２４およ
びラストデータ番号記憶エリア３４には、基準軸データ
メモリ１０から出力される基準軸データのデータ番号が
書込まれる。本実施例において、データ番号は１〜・Ｎ
で表わされ、ぞのが・大値はＮである３、従って、前記
各データ番号記憶エリア２４．３４は、それぞれ（Ｉ　
ｏ　ｇ　２　Ｎ　ｌ　　ビット（但し７、（）は小数点
以下を切り」二げた整数を意味する記号とする）の容量
をもつように形成すればよい。

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

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

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

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

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

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

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

このため、チェインバッファメモリ４０内には、アドレ
スポインタ４２の出力するデータ番号に基づきＯ〜Ｎの
順にアドレスが指定されるチェインデータ番号記憶エリ
゛ア４４が設けられている。これら各チェインデータ番
号記憶エリア４４も、前記ファーストデータ番号記憶エ
リア２４およびラストデータ番号記憶ボリア３４と同様
に、少なくても（ｌｏｇ＋Ｎｌ　　ビットの記憶容量を
有するように形成すればよい。

そｌ−て、ラストデータ番号記憶エリア３４の内容が更
新記録されると、更新前のデータ番号がアドレスポイン
タ４２に設定され、チェインデータ番号記憶エリア４４
のアドレス指定が行われる。

そして、指定されれたチェインデータ番号記憶エリア４
４には更新後の新なデータ番号が書込まれる。

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

以上説明し、たように、本実施例によれば、基準軸デー
タメモリ１０からデータ番号順に基準軸データが出力さ
れると、出力された基準軸データを・書込みアドレスと
して、そのデータ番号が、］−］５杆−ストバッファメ
モリ２０．ラストバッファメモリ３に書き込まれ、さら
に、これに付随して一′２ストバッファメモリ３０から
チエインバラノアメモリ４０へのデータの転送書込みが
行われる。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（１））　　Ｉ’ッフ１メモリ２０．３０への書込みこ
のようにして、基準軸データが読出されると、読出され
た基準軸データをアドレスとして、対応するデータ番号
がファーストデータ番号記憶エリア２４およびラストデ
ータ番号記憶エリア３４に順次書込まれる。

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

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

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

次に、データ番号「４」で特定される基準軸データ「３
」が出力されるど、この基準軸データ「３」をアドレス
として、データ番号記憶エリア２４．３４には、データ
番号「４」が入力される。

このとき、ファーストデータ番号記憶エリア２４には、
すでにデータ番号が書込まれているため、新なデータ番
号の書込みは行われない。これに対し、ラストデータ番
号記憶エリア３４は、前のデータ番号「３」を新なデー
タ番号「４」に更新記憶する。このため、ヂエインデー
タ番号記憶エリア４４には、更新前のデータ番号「３」
をアドレスとして、更新後のデータ番号「４」が書込ま
れることとなる。

次に、基準軸データメモリ１０からデータ番号「５」で
特定される基準軸データ［０，１が読出されると、この
基準軸データ［０」をアドレスと］７て、各データ番号
記憶エリア２４．３４にはそのデータ番号「５」が書込
まれる。

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

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

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

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

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

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

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

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

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

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

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

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

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

このようにするためには、アドレス「０」で指定される
ラストデータ番号記憶エリア３４内のデータ番号「５」
を書込みアドレスとして読み出す。

ぞして、このアドレス「５」で指定されるチェインデー
タ番号記憶エリア４４に、アドレス「１」で指定される
ファーストデータ番号記憶エリア２４内のデータを書込
めばよい。

次に、同様にして基準軸データ「１」が最後に出現した
ときのデータ番号を書込みアドレスとし。

て、これより上の基準軸データ「２」が初めて出現した
ときのデータ番号をチェインデータ番号記憶エリア４４
に書込む。

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

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

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

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

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

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

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

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

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

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

（ａ）　　ｉｌｌデータメモＨ（ｈの書込み／！ＩＩ！
Ｌこの動作は、基準軸データを昇順にソーティングする
場合と同じであるので、その説明は省略する。

（ｂ）　　パフフＴメモ’１２０．３０への書込みこの
動作もデータを昇順にソーティングする場合と同様であ
るので、ここではその説明は省略する。

（ｅ）　　バッフ１メモリ４０へのデータの転送書込ミ
基準軸データを昇順にソーティグする場合と降順にソー
ティングする場合とでは、バッフアメ七り４０へのデー
タの転送書込み作業のしがたが若干光なる。

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

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

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

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

なお、アドレスｒＯＪの記憶エリア４４を他の用途に使
用する場合には、スタートアドレスポインタ３１０にセ
ットするようにする。

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

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

次に、同様にして基準軸データ「２」が最後に出現した
ときのデータ番号を書込みアドレスとり。

て、これより下の基準軸データ「１」が初めて出現した
ときのデータ番号をチェインデータ番号記憶エリア４４
に書込む。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（以下余白） 第２実施例 第２１図には、本発明の好適な第２実施例が示されてい
る。

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

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

このとき、データ番号カウンタ１，３は、基準軸データ
が入力される毎に対応するデータ番号を発生ずる。実施
例では、基準軸データの入力に同期しでＯ：　　し２・
・・（２Ｍ−１，）の順にデータ番号を出力する。

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

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

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

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

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

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

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

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

実施例のソーティング回路は、基準軸データメモリ〕０
と、情報メモリ５８とを含む。そして、：’：　＋７）
回路は、データ発生回路８から出力されるソティングデ
ータに含まれる基準軸データを基準軸）１−クメモリ１
０に格納【２、各基準軸データと＋４　ｔな１組合せ情
報を情報メモリ５８内に格納するよう形成されている。

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

また、前記情報メモリ５８も、データ番号ポインタ１２
によって指定される少なくとも１　＝Ｎまでの合計Ｎ個
の組合仕情報記憶エリア５８　ａをζｆする。

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

このようにして、本実施例のソーヅイ−・グ回”°、へ
に、外部からソーティングデータが入力され、　、４１
１　、’そのソーティングデータに含まれる基準軸デー
タとその組合せ情報は、データ番号ポインタ１２により
指定される各記憶エリア１４．５８ａに所定の対応関係
をもって順に書込まれることになる。

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

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

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

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

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

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

そして、基準軸データが入力されると、各バッファメモ
リ２０，３０．４０．データ番号カラン！−１３および
ソーティング制御回路８０は、前記第２実施例と同様に
動作する。従って、チェーンバッファメモリ４０のチェ
ーンデータ記憶エリア４／；には、基準軸データが昇順
または降順に連鎖するようデータ番号が記憶されること
になる。

そし７て、第３の制御回路８０ｅは、チェーンデータ番
号記憶エリア４４に記憶されたデータ番号を、前記第１
実施例と同様にして読み出し、読み出したデータ番号順
に情報メモリ５８から組合せ情報を読み出し制御する。

これにより、情報メモリ５８から一連の組合せ情報が基
準軸データに基イき昇順または降順にソーティング出力
されることになる。

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

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

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

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

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

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

本実施例の特徴は、基準軸データを構成する３Ｍビット
データを所定ビット毎に複数のサーチ桁に分割し、基準
軸データメモリ１０からの基準軸データメモリの読出し
を、サーチ桁単位で行なうことにある。

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

このようにして読み出された各基準軸データの下位Ｍビ
ットデータは、前記第１実施例と同様にソーティング処
理される。このとき、２組設けられたチェーンバッファ
メモリ４０の内の一方にデータの書き込みが行われる。

従って、該一方のチェーンバッファメモリ４０のチェー
ンデータ番号記憶エリア４４には、基準軸データの下位
Ｍビットデータが昇順または降順に連鎖するよう、デー
タ番号が書込まれることになる。

本実施例において、第４の制御回路８０ｄは、一方のチ
ェーンバッファメモリ４０のチェーンデータ番号記憶エ
リア４４へ書込まれたデータ番号を、前記第１実施例と
同様に、所定の読み出し、規則にしたがって読み出す。

そして、読み出されノ、データ番号順に、基準軸データ
メモリ１０から基準軸データの中位Ｍビットデータを各
バッファメモリ２０．３０へ向け読み出し制御する。

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

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

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

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

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

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

次に、基準軸データを昇順にソーティングする場合の具
体的な動作を第２４図に基づき説明する。

ここでは説明を簡単なものとするために、３進数で構成
された基準軸データをその最下位の桁から１桁ずつソー
ティングする場合を例にとり説明する。

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

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

次に、このチェーンデータ番号記憶エリア４４内に書き
込まれたデータ番号を、所定の読み出し。

規則に従って読み出し、読み出されたデータ番号順に基
準軸データメモリ１０から基準軸データのｍ−１のサー
チ桁の読み出す。このとき、基準軸データメモリ１０か
ら読み出される基準軸データの読み出し順序は、第２４
図（Ｂ）に示すようになる。同図から明らかなように、
基準軸データのｍ−ｍｌの桁の値は、ｍ−０のサーチ桁
の値にしたがって昇順にソーティングされて読み出され
ることが理解されよう。

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

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

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

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

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

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

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

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

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

ことになる。

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

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

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

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

ここにおいて、Ｎ−１０２３個、Ｍ−１５ビツト、ＲＡ
Ｍアクセスを６．１４４ＭＩＩｚのサイクルスチールと
すると、全処理時間は、 ８２４３７サイクル／　［ｔ、し４４　Ｍ　Ｈｚ　−１
０，２ｍ　ｓｅｃとなり、１フイ一ルド時間（約１８．
５ｍｍ　５ｅｃ）内に十分に間にあう。

ところが、データ数が増え、Ｎ−２０４７個、Ｍ−１５
ビツトのように、なった場合には、この処理時間は、 １２４９０１サイクル／　６．１４４　Ｍ　ｆｉｚ　−
２０，３ｍ　ｓｅｃとなってしまい、１フイ一ルド時間
では間にあわなくなってしまう。

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

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

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

まず、基準軸データメモリ１，０は、−同全での基準軸
データを読出すので、Ｎサイクルを必要とする。

才だ、ファーストバッファメモリ２０は、データの書込
みにＮサイクル、チェインバッファメ工。

す５０へのデータ転送の際の読出しに２Ｍサイクルを必
要する。

ラストバッファメモリ３０は、データのチエ・ツクのた
めの読出にＮサイクル、データの書込みに同じくＮサイ
クル、チェインバッファメモリ４０へのデータ転送のた
めに２Ｍサイクルを必要イシする。

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

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

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

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

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

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

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

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

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

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

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

ポリゴン情報発生回路５０が、このようにし４各多角形
のポリゴン情報（多角形の頂点位置におけるＸＹ座標、
中心点におけるＺ座標および色情報）を演算すると、ポ
リゴン情報転送回路５２は、第７図に示すように、各多
角形のポリゴン情報を５Ｚ座標データと、それ以外のデ
ータとに分離し、Ｚ座標データを基準軸データメモリ１
−０に書込み、それ以外のデータ（組合せ情報）をＸＹ
ＲＡＭ５８へ書込む。

このように【７て、ポリゴン情報発生回路５０から、各
多角形のポリゴン情報が演算出力されるたびに、このポ
リゴン情報のＺ座標は基準軸データメモリ１０内に順次
入力され、またＺ座標以外のポリゴン情報はＸ　Ｙ　Ｒ
Ａ　Ｍ　５８へ順次入力される。

このとき、データ数１７ジスタ５４は、ポリゴン情報発
生回路５０から演算出力される多角形の数をカウントし
、各ラスク走査ごとに表示多角形の数を検出している。

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

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

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

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

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

そして、メインＣＰＵ回路５０−２から、飛行機の現在
位置を表す移動座標が出力されると、この三次元演算回
路５０−４は三次元情報メモリ５０−３から所定の多面
体データの読出しを行う。

実施例において、三次元情報メモリ５０−３に書き込ま
れた情報は、固定座標系を用いて表されているため、三
次元演算回路５０−４は、三次元情報メモリ５０−３か
ら読み出（７た情報を移動座標系の座標データに変換す
る必要がある。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ここにおいて、前記基準軸データメモリ１０は、ファー
ストバッファメモリ２０．ラス１〜バツフアメモリ３０
およびチェインバッファメモリ４０とともに一群のソー
ティングＲＡＭ７０として形成されている。

そして、ソーティング制御回路８０は、このソーティン
グＲＡＭ７０のデータの書込み、読出しを制御し、基準
軸データが昇順に連鎖するようそのデータ番号をチエイ
ンバッファ４０に書込む。

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

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

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

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

この第１の制御回路８０ａは、基準軸データメモリ］０
に書込まれたＺ軸データを、そのデータ番号順に順次に
読出す。そして、読出したＺ軸データをアドレスとして
、対応するデータ番号をファーストバッファメモリ２０
．　　ラストバッファメモリ３０へ書込む。これと共に
、ラストバッファメモリ３０のデータ番号が更新記憶さ
れたとき、更新前のデータ番号をアドレスとして、更新
後のデータ番号をチェインバッファメモリ４ｏへ書込む
。

本実施例において、この第１の制御回路８０ａは、デー
タ番号ポインタ１２と、データ数レジスタ５４と、比較
判定回路１１０と、ステップ１制御回路１１２とを含む
。

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

従って、基準軸データメモリ１ｏがらＺ軸データを、各
バッファメモリ２０．３０および４０へ向け出力する場
合に、このデータ番号ポインタ１２は、第３図に示すよ
うにデータ番号を１，２゜３、・・・の順に順次インク
リメント出力する。

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

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

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

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

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

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

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

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

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

この第２の制御回路８０ｂは、ステップ２制御回路２１
０と、スタートアドレスセレクタ２１２と、スタートア
ドレスポインタ２１４と、アドレスポインタ２２および
３２とを八む。

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

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

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

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

そして、デ・−・・夕番号が記憶されたファーストデー
タ番号記憶ユ、リア２４が検出されると同時に、フロー
２２００に従っ゛Ｃチェインデータ番号記憶エリア４４
へのデータ番号書込みを同様にＬ２で行う。

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

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

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

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

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

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

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

そして、ステップ２制御回路２し０は、シフト１ノジス
ク２１０ａの内容を、１ビツトずつ右へシフ］・シてい
き、データ番号が書込まれているファ−ストデータ番号
記憶エリア２４を検出する。

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

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

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

また、このようなフラグメモリ２１４を用れば、このフ
ラグメモリ２１４を零クリアすることにより、これらバ
ッファメモリ２０．３０を零クリアする必要はなくなる
。

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

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

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

第１７図には、このようなステップ３の動作を行う第３
の制御回路８０ｅの具体的な回路構成が説明されており
、第１８図にはその動作を示すフローチャー１・が示さ
れている。

本実施例において、前記第３の制御回路８０ｅは、ステ
ップ３制御回路３１２．データ数カウンタ３１４．比較
判定回路３１６．アドレスポインタ４２．スタートアド
レスポインタ３１０．セレクタ３１８．ラッチ３２０を
含む。

そして、ステップ３制御回路３し２は、ステップ３の動
作が開始されると、まずアドレスポインタ４２およびデ
ータ数カウンタ３１−４をリセットする。次に、セレク
タ３１８をスター・ドアドレスポインタ３し０側に切り
替え、スタートアドレスポインタ３１０内に多めセット
されているデータ番号をスタートアドレスとしてセレク
タ３］８゜ラッチ３２０を介し、てＸＶＲＡＭ５８へ向
け出力する。

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

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

このようにして、最初のポリゴン情報が読出されると、
次にステップ３制御回路３１２は、セレクタ３１８をス
タータアドレスポインタ３１０側からチェインバッファ
メモリ４０側へ切換える。

そして、ステップ３制御回路３１２は、第１８図に示す
フロー３０００にしたがいＸＹＲＡＭ５８からポリゴン
情報をＺ軸データに基づきソーティング出力する。

すなわち、前記アドレスポインタ４２から、読出しアド
レスとしてデータ番号が出力されると、この読出しアド
レスによって指定されるチェインデータ記憶エリア４４
からセレクタ３１８．ラッチ３２０を介してデータ番号
が読出Ｎれる。そして、読出されたデータ番号を読出し
アドレスとしてＸＹＲＡＭ５８からポリゴン情報が出力
されると共に、前記データ番号は、新たな読出しアドレ
スとしてアドレスポインタ４２にセットされる。

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

このとき、データ数カウンタ３１４は、ＸＹＲＡＭ５８
をアクセスした回数、すなわちＸＹＲＡＭ５８からソー
ティング出力されるポリゴン情報の数をカウント［７、
そのカウント値を比較判定回路３１６へ向け出力してい
る。

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

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

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

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

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

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

【図面の簡単な説明】

第１図は本発明に係るソーティング回路の基本的な構成
を示す説明図、 第２図は基準軸データメモリから各バッファメモリへの
データ転送動作を示す説明図、第３図、第４図はファー
ストバッファメモリおよびラストバッファメモリからチ
ェインバッファメモリへのデータ転送作業を示す説明図
、第５図は本発明のソーティング回路が適用された三次
元画像合成装置の一例を示すブロック回路図、 第６図および第７図は、第５図に示すポリゴン情報発生
回路から演算出力されるポリゴン情報の説明図、 第８図は第５図に示す三次元画像合成装置に用いられる
本発明のソーティング回路のブロック回路図、 第９図は第５図に示す回路を用いて表示される画像の三
次元概念図、 第１０図は第５図に示すポリゴン情報発生回路の具体的
な構成を示すブロック回路図、第１１図は本発明のソー
ティング回路の回路構成の一例を示すブロック回路図、 第１２図は第１１図に示す回路の動作を示すフローチャ
ート図、 第１３図は本発明のソーティング回路の具体的な回路構
成の一例を示すブロック回路図、第１４図は第１３図に
示す回路の動作を示すフローチャート図、 第１５図は第１３図に示す回路のシフトレジスタ内に登
録されたフラグの説明図、 第１６図は、第１３図に示す回路で用いられるフラグメ
モリの構成を、ファーストデータ番号記憶エリアと対応
付けて示す説明図、 第１７図は本発明のソーティング回路の具体的な回路構
成の一例を示すブロック回路図、第１８図は第１７図に
示す回路の動作を示すフローチャート図、 第１９図は、本発明の好適な第３実施例の説明図、 第２０図は、データを降順にソーティングする場合に、
ファーストバッファメモリおよびラストバッファメモリ
からチェインバッファメモリへデータを転送する動作を
示す説明図 第２１図は、本発明の好適な第２実施例の説明図、 第２２図は、本発明の好適な第４実施例の説明図、 第２３図は、本発明の好適な第５実施例の説明図である
。 １０・・・基準軸データメモリ、 １２・・・データ番号ポインタ、 １３・・・データ番号カウンタ、 ２０・・・ファーストバッファメモリ、２４・・・ファ
ーストデータ番号記憶エリア、３０・・・ラストバッフ
ァメモリ、 ３４・・・ラストデータ番号記憶エリア、４０・・・チ
ェインバッファメモリ、 ４４・・・チェインデータ番号記憶エリア、５８・・・
情報メモリ ８０・・・ソーティング制御回路、 ８０ａ・・・第１の制御回路、 ８０ｂ・・・第２の制御回路、 ８０ｅ・・・第３の制御回路、 ８０ｄ・・・第４の制御回路。 −ティング回路のソーティンク動作の一例を示す説明図
、 第２５図は、本発明の好適な第６実施例の説明代理人　
弁理士　布　施　行　夫 （他２名） 第 図 第 図 第 図 第 図 ＼ 第 図 第 図 第 図 第 １０図 第 図 第 １２図 第 １５図 第 １６図 第 １８図 第２０図 第２１ 図 第 ２２図

Claims (10)

【特許請求の範囲】
1. （１）入力される複数の基準軸データをソーティングす
   る回路であって、 入力される各基準軸データに対応したデータ番号を発生
   するデータ番号発生手段と、 前記基準軸データに基づきアドレスが指定されるファー
   ストデータ番号記憶エリアを有し、各記憶エリアに対応
   する基準軸データが最初に入力されたとき、この記憶エ
   リアにデータ番号発生手段の発生するデータ番号を記憶
   するファーストバッファメモリと、 前記基準軸データに基づきアドレスが指定されるラスト
   データ番号記憶エリアを有し、各記憶エリアに対応する
   基準軸データが入力される毎に、この記憶エリアにデー
   タ番号発生手段の発生するデータ番号を更新記憶するラ
   ストバッファメモリデータ番号に基づきアドレスが指定
   されるチェインデータ番号記憶エリアを有するチェイン
   バッファメモリと、 前記ラストバッファメモリのデータ番号が更新される毎
   に、更新前のデータ番号で指定されるチェインデータ番
   号記憶エリアに、更新される新たなデータ番号を書込む
   第１の制御手段と、 前記ファーストバッファメモリおよびラストバッファメ
   モリへのデータ番号書き込み終了後、ラストデータ番号
   記憶エリアに記憶されたデータ番号で指定されるチェイ
   ンデータ番号記憶エリアに、該ラストデータ番号記憶エ
   リアと所定の対応関係にある前記ファーストデータ番号
   記憶エリアに記憶されたデータ番号を書込むことにより
   、チェインデータ番号記憶エリア内に基準軸データが昇
   順または降順に連鎖するようデータ番号を書込む第２の
   制御手段と、 チェインデータ番号記憶エリア内に書込まれたデータ番
   号を所定の読出し規則に従い読出し、入力された各基準
   軸データを読出したデータ番号順にソーティング出力す
   る第３の制御手段と、を含むことを特徴とするソーティ
   ング回路。
2. （２）請求項（１）において、 入力さる各基準軸データを、そのデータ番号順に記憶す
   る基準軸データメモリを含み、 前記データ番号発生手段は、 基準軸データメモリに向けデータ番号を読出アドレスと
   して出力し、基準軸データメモリから各基準軸データを
   データ番号順に読み出すデータ番号ポインタを用いて形
   成され、 前記ファーストバッファメモリは、基準軸データメモリ
   から各記憶エリアに、対応する基準軸データが最初に入
   力されたとき前記アドレスポインタから出力されるデー
   タ番号を記憶するよう形成され、 前記ラストバッファメモリは、基準軸データメモリから
   各記憶エリアに、対応する基準軸データが読出される毎
   に、該記憶エリアに記憶されたデータ番号を前記アドレ
   スポインタから出力されるデータ番号に更新するよう形
   成され、 前記第３の制御手段は、チェインデータ番号記憶エリア
   内に書込まれたデータ番号を所定の読出し規則に従い読
   出し、読出したデータ番号順に基準軸データメモリから
   基準軸データをソーティング出力するよう形成されたこ
   とを特徴とするソーティング回路。
3. （３）請求項（１）において、 入力さる各基準軸データを、そのデータ番号順に記憶す
   る基準軸データメモリを含み、 前記データ番号発生手段は、 各基準軸データが入力される毎に対応するデータ番号を
   前記各バッファメモリへ向け出力するカウンタを用いて
   形成され、 前記ファーストバッファメモリは、各記憶エリアが入力
   される基準軸データにより最初にアドレス指定されたと
   き、前記カウンタから出力されるデータ番号を該記憶エ
   リアに記憶するよう形成され、 前記ラストバッファメモリは、各記憶エリアが入力され
   る基準軸データによりアドレス指定される毎に、該記憶
   エリアに書き込まれたデータ番号を、前記カウンタから
   出力されるデータ番号に更新するよう形成され、 前記第３の制御手段は、チェインデータ番号記憶エリア
   内に書込まれたデータ番号を所定の読出し規則に従い読
   出し、読出したデータ番号順に基準軸データメモリから
   基準軸データをソーティング出力するよう形成されたこ
   とを特徴とするソーティング回路。
4. （４）入力される複数のデータを所定の基準軸データに
   基づきソーティングする回路であって、前記各データの
   必要部分を、そのデータ番号に対応して記憶する情報メ
   モリと、 前記各データに含まれる基準軸データが入力されるソー
   ティグ手段と、 を含み、前記ソーティング手段は、 入力される各基準軸データに対応したデータ番号を発生
   するデータ番号発生手段と、 前記基準軸データに基づきアドレスが指定されるファー
   ストデータ番号記憶エリアを有し、各記憶エリアに対応
   する基準軸データが最初に入力されたとき、この記憶エ
   リアにデータ番号発生手段の発生するデータ番号を記憶
   するファーストバッファメモリと、 前記基準軸データに基づきアドレスが指定されるラスト
   データ番号記憶エリアを有し、各記憶エリアに対応する
   基準軸データが入力される毎に、この記憶エリアにデー
   タ番号発生手段の発生するデータ番号を更新記憶するラ
   ストバッファメモリと、 データ番号に基づきアドレスが指定されるチェインデー
   タ番号記憶エリアを有するチェインバッファメモリと、 前記ラストバッファメモリのデータ番号が更新される毎
   に、更新前のデータ番号で指定されるチェインデータ番
   号記憶エリアに、更新される新たなデータ番号を書込む
   第１の制御手段と、 前記ファーストバッファメモリおよびラストバッファメ
   モリへのデータ番号書き込み終了後、ラストデータ番号
   記憶エリアに記憶されたデータ番号で指定されるチェイ
   ンデータ番号記憶エリアに、該ラストデータ番号記憶エ
   リアと所定の対応関係にある前記ファーストデータ番号
   記憶エリアに記憶されたデータ番号を書込むことにより
   、チェインデータ番号記憶エリア内に基準軸データが昇
   順または降順に連鎖するようデータ番号を書込む第２の
   制御手段と、 チェインデータ番号記憶エリア内に書込まれたデータ番
   号を所定の読出し規則に従い読出し、読出したデータ番
   号順に前記情報メモリからデータを読み出す第３の制御
   手段と、 を含み、複数のデータを基準軸データに基づきソーティ
   ング出力することを特徴とするソーティング回路。
5. （５）請求項（４）において、 入力さる各基準軸データを、そのデータ番号順に記憶す
   る基準軸データメモリを含み、 前記データ番号発生手段は、 基準軸データメモリに向けデータ番号を読出アドレスと
   して出力し、基準軸データメモリから各基準軸データを
   データ番号順に読み出すデータ番号ポインタを用いて形
   成され、 前記ファーストバッファメモリは、基準軸データメモリ
   から各記憶エリアに、対応する基準軸データが最初に入
   力されたとき前記アドレスポインタから出力されるデー
   タ番号を記憶するよう形成され、 前記ラストバッファメモリは、基準軸データメモリから
   各記憶エリアに、対応する基準軸データが読出される毎
   に、該記憶エリアに記憶されたデータ番号を前記アドレ
   スポインタから出力されるデータ番号に更新するよう形
   成され、 前記第３の制御手段は、チェインデータ番号記憶エリア
   内に書込まれたデータ番号を所定の読出し規則に従い読
   出し、読出したデータ番号順に情報メモリからデータを
   ソーティング出力するよう形成されたことを特徴とする
   ソーティング回路。
6. （６）請求項（４）において、 前記データ番号発生手段は、 各基準軸データが入力される毎に対応するデータ番号を
   前記各バッファメモリへ向け出力するカウンタを用いて
   形成され、 前記ファーストバッファメモリは、各記憶エリアが入力
   される基準軸データにより最初にアドレス指定されたと
   き、前記カウンタから出力されるデータ番号を該記憶エ
   リアに記憶するよう形成され、 前記ラストバッファメモリは、各記憶エリアが入力され
   る基準軸データによりアドレス指定される毎に、該記憶
   エリアに書き込まれたデータ番号を、前記カウンタから
   出力されるデータ番号に更新するよう形成され、 前記第３の制御手段は、チェインデータ番号記憶エリア
   内に書込まれたデータ番号を所定の読出し規則に従い読
   出し、読出したデータ番号順に前記情報メモリからデー
   タをソーティング出力するよう形成されたことを特徴と
   するソーティング回路。
7. （７）複数桁からなる複数の基準軸データを、前記各基
   準軸データに対応して与えられるデータ番号に基づきソ
   ーティングする回路であって、前記各基準軸データを、
   そのデータ番号に対応して記憶する基準軸データメモリ
   と、 基準軸データメモリに向けデータ番号を読出アドレスと
   して出力し、基準軸データメモリから各基準軸データの
   最下位のサーチ桁の値をデータ番号順に読み出すデータ
   番号ポインタと、 前記基準軸データメモリから出力される所定サーチ桁の
   基準軸データに基づきアドレスが指定されるファースト
   データ番号記憶エリアを有し、基準軸データメモリから
   各記憶エリアに、対応する基準軸データが最初に入力さ
   れたとき前記アドレスポインタから出力されるデータ番
   号を記憶するファーストバッファメモリと、 前記基準軸データメモリから出力される所定サーチ桁の
   基準軸データに基づきアドレスが指定されるラストデー
   タ番号記憶エリアを有し、基準軸データメモリから各記
   憶エリアに、対応する基準軸データが読出される毎に、
   該記憶エリアに記憶されたデータ番号を前記アドレスポ
   インタから出力されるデータ番号に更新するラストバッ
   ファメモリと、 データ番号に基づきアドレスが指定されるチェインデー
   タ番号記憶エリアを有するチェインバッファメモリと、 前記ラストバッファメモリのデータ番号が更新される毎
   に、更新前のデータ番号で指定されるチェインデータ番
   号記憶エリアに、更新される新たなデータ番号を書込む
   第１の制御手段と、 前記ファーストバッファメモリおよびラストバッファメ
   モリへのデータ番号書き込み終了後、ラストデータ番号
   記憶エリアに記憶されたデータ番号で指定されるチェイ
   ンデータ番号記憶エリアに、該ラストデータ番号記憶エ
   リアと所定の対応関係にある前記ファーストデータ番号
   記憶エリアに記憶されたデータ番号を書込むことにより
   、チェインデータ番号記憶エリア内に基準軸データが昇
   順または降順に連鎖するようデータ番号を書込む第２の
   制御手段と、 前記基準軸データの次の上位桁をサーチ桁として設定す
   るととももに、前記チェインデータ番号記憶エリア内に
   書込まれたデータ番号を所定の読出し規則に従い読出し
   、読出したデータ番号順に、基準軸データメモリから基
   準軸データの設定サーチ桁を前記各ファースバッファメ
   モリおよびラストバッファメモリへ向け出力するという
   各サーチ桁毎のソーティング処理を、基準軸データの最
   下位の桁から最上位の桁に向けサーチ桁を一桁ずつシフ
   トしながら繰り返し行なう第４の制御手段と、最上位の
   サーチ桁のソーティング処理が終了した後、前記チェイ
   ンデータ番号記憶エリア内に書込まれたデータ番号を所
   定の読出し規則に従い読出し、読出したデータ番号順に
   基準軸データメモリから各基準軸データをソーティング
   出力する第３の制御手段と、 を含むことを特徴とするソーティング回路。
8. （８）入力される複数のデータを所定の基準軸データに
   基づきソーティングする回路であって、前記各データの
   必要部分を、そのデータ番号に対応して記憶する情報メ
   モリと、 前記各データに含まれる基準軸データが入力されるソー
   ティグ手段と、 を含み、前記ソーティング手段は、 前記各基準軸データを、そのデータ番号に対応して記憶
   する基準軸データメモリと、 基準軸データメモリに向けデータ番号を読出アドレスと
   して出力し、基準軸データメモリから各基準軸データの
   最下位のサーチ桁の値をデータ番号順に読み出すデータ
   番号ポインタと、 前記基準軸データメモリから出力される所定サーチ桁の
   基準軸データに基づきアドレスが指定されるファースト
   データ番号記憶エリアを有し、基準軸データメモリから
   各記憶エリアに、対応する基準軸データが最初に入力さ
   れたとき前記アドレスポインタから出力されるデータ番
   号を記憶するファーストバッファメモリと、 前記基準軸データメモリから出力される所定サーチ桁の
   基準軸データに基づきアドレスが指定されるラストデー
   タ番号記憶エリアを有し、基準軸データメモリから各記
   憶エリアに、対応する基準軸データが読出される毎に、
   該記憶エリアに記憶されたデータ番号を前記アドレスポ
   インタから出力されるデータ番号に更新するラストバッ
   ファメモリと、 データ番号に基づきアドレスが指定されるチェインデー
   タ番号記憶エリアを有するチェインバッファメモリと、 前記ラストバッファメモリのデータ番号が更新される毎
   に、更新前のデータ番号で指定されるチェインデータ番
   号記憶エリアに、更新される新たなデータ番号を書込む
   第１の制御手段と、 前記ファーストバッファメモリおよびラストバッファメ
   モリへのデータ番号書き込み終了後、ラストデータ番号
   記憶エリアに記憶されたデータ番号で指定されるチェイ
   ンデータ番号記憶エリアに、該ラストデータ番号記憶エ
   リアと所定の対応関係にある前記ファーストデータ番号
   記憶エリアに記憶されたデータ番号を書込むことにより
   、チェインデータ番号記憶エリア内に基準軸データが昇
   順または降順に連鎖するようデータ番号を書込む第２の
   制御手段と、 前記基準軸データの次の上位桁をサーチ桁として設定す
   るととももに、前記チェインデータ番号記憶エリア内に
   書込まれたデータ番号を所定の読出し規則に従い読出し
   、読出したデータ番号順に、基準軸データメモリから基
   準軸データの設定サーチ桁を前記各ファーストバッファ
   メモリおよびラストバッファメモリへ向け出力するとい
   う各サーチ桁毎のソーティング処理を、基準軸データの
   最下位の桁から最上位の桁に向けサーチ桁を一桁ずつシ
   フトしながら繰り返し行なう第４の制御手段と、 最上位のサーチ桁のソーティング処理が終了した後、前
   記チェインデータ番号記憶エリア内に書込まれたデータ
   番号を所定の読出し規則に従い読出し、読出したデータ
   番号順に前記情報メモリからデータをソーティング出力
   する第３の制御手段と、 を含み、複数のデータを基準軸データに基づきソーティ
   ング出力することを特徴とするソーティング回路。
9. （９）請求項（４）〜（６）、（８）のいずれかにおい
   て、 前記情報メモリには、（Ｘ、Ｙ、Ｚ）からなる複数の三
   次元情報のうち、少なくともその（Ｘ、Ｙ）の２次元情
   報がデータ番号順に記憶され、前記ソーティング手段に
   は、前記三次元情報に含まれるＺ軸データが基準軸デー
   タとして入力され、 前記情報メモリに含まれる三次元情報をそのＺ軸データ
   に基づき昇順または降順にソーティング出力することを
   特徴とするソーティング回路。
10. （１０）請求項（１）〜（９）のいずれかにおいて、 前記第２の制御手段は、 前記ファーストデータ番号記憶エリアに１対１に対応す
    る複数の１ビットフラグエリアを含み、ファーストデー
    タ番号記憶エリアにデータ番号が記憶されたときに対応
    するフラグエリアにフラグがセットされるフラグメモリ
    を備え、 前記フラグエリアには、所定数を１グループ単位として
    フラグアドレスが割付けられ、各フラグアドレスによっ
    て指定される一群のフラグエリアからフラグ情報をグル
    ープ単位で読出すことにより、データ番号記憶エリアか
    らデータ番号を読出すことなく、各データ番号記憶エリ
    アにデータ番号が書込まれているか否かの判断を行うこ
    とを特徴とするソーティング回路。