(57)【特許請求の範囲】
【請求項１】
ソートデータを並び替えるソート回路であって、
前記ソートデータの比較対象データを少なくとも記憶する比較データ記憶部と、
複数のグループが形成されており、前記比較対象データに対応付けられた識別情報を該グループごとに格納し、格納されたデータのシフト機能を有するタグ回路部と、
前記ソートデータの比較対象データを入力し、前記タグ回路部に格納された識別情報を用い前記各グループの前記比較対象データの代表値を取得し、該取得した代表値と前記入力した比較対象データとを比較し、前記入力した比較対象データの属するグループを該比較結果に基づいて判定し、該判定したグループ内の比較対象データと前記入力した比較対象データとを比較し、前記入力した比較対象データの前記タグ回路部の格納場所を判定し、前記入力した比較対象データに対応付けられた識別情報を該判定結果に基づいて前記タグ回路部の前記格納場所に出力する比較回路部と、を備え、
前記タグ回路部は、前記入力した比較対象データの属するグループを前記比較回路部が判定したときには、前記判定されたグループの最後の識別情報以降の識別情報を少なくともシフトさせ、前記入力した比較対象データに対応付けられた識別情報の格納場所を確保する、ソート回路。
【請求項２】
前記タグ回路部は、複数のレジスターを含む複数のグループにより構成され、該複数のレジスターはパイプライン状に接続されている、請求項１に記載のソート回路。
【請求項３】
前記比較回路部は、前記タグ回路部の前記グループ間において所定間隔で格納された比較対象データを前記代表値として取得する、請求項１又は２に記載のソート回路。
【請求項４】
請求項１〜３のいずれか１項に記載のソート回路であって、
前記ソートデータを記憶するソートデータ記憶部、を備え、
前記比較データ記憶部は、前記ソートデータ記憶部に比して高速なリードライトを実行可能であり、前記ソートデータの比較対象データを格納する、ソート回路。
【請求項５】
前記比較回路部は、前記入力した比較対象データの昇順又は降順の序列を判定し、
前記タグ回路部は、前記識別情報を昇順又は降順の序列で格納する、請求項１〜４のいずれか１項に記載のソート回路。
【請求項６】
請求項１〜５のいずれか１項に記載のソート回路であって、
前記タグ回路部に記憶された前記識別情報の格納場所に基づいて前記ソートデータを読み出す読出回路部、を備えたソート回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソート回路に関する。
【背景技術】
【０００２】
従来、ソート方法としては。複数のデータ群を代表データの値の順番になるよう整列するものが提案されている（例えば、特許文献１参照）。この方法では、複数のデータ群が格納されるデータ格納部と、代表データのビット数で表現される数だけのアドレスを有するソートテーブルとを用意する。そして、データ格納部に複数のデータ群を格納する場合に、リンクアドレス記憶領域を付加し順番に入力されるデータ群を順番に格納し、各データ群が格納されたデータ格納部の格納アドレスを、代表データの値をアドレスとするソートテーブルの記憶領域に記憶する。データ格納部から複数のデータ群を読み出すときに、ソートテーブルの記憶領域の記録内容をアドレス順に読み出し、読み出された格納アドレスのデータ格納部に格納されたデータ群を読み出す。そうして、データ量が増大しても指数関数的に処理時間が増大することのないデータ整列方法を提供することができる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平６−４４０４５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、上述の方法では、複数のデータ群の代表データの値をアドレスとするソートテーブルを用い、データ群としてソートしているが、データ群内部における序列までは考慮されていなかった。即ち、入力したデータについて、データ群内部まで含む全データのどの位置に属するかをソートしようとすることまでは考えられていなかった。また、このようなソートを実行する回路構成についても検討されていなかった。このように、回路構成によりデータのソートをより効率的に実行することが求められていた。
【０００５】
本発明は、このような課題に鑑みなされたものであり、データのソートをより効率的に実行することができるソート回路を提供することを主目的とする。
【課題を解決するための手段】
【０００６】
本発明は、上述の主目的を達成するために以下の手段を採った。
【０００７】
本発明のソート回路は、
ソートデータを並び替えるソート回路であって、
前記ソートデータの比較対象データを少なくとも記憶する比較データ記憶部と、
複数のグループが形成されており、前記比較対象データに対応付けられた識別情報を該グループごとに格納し、格納されたデータのシフト機能を有するタグ回路部と、
前記ソートデータの比較対象データを入力し、前記タグ回路部に格納された識別情報を用い前記各グループの前記比較対象データの代表値を取得し、該取得した代表値と前記入力した比較対象データとを比較し、前記入力した比較対象データの属するグループを該比較結果に基づいて判定し、該判定したグループ内の比較対象データと前記入力した比較対象データとを比較し、前記入力した比較対象データの前記タグ回路部の格納場所を判定し、前記入力した比較対象データに対応付けられた識別情報を該判定結果に基づいて前記タグ回路部の前記格納場所に出力する比較回路部と、を備え、
前記タグ回路部は、前記入力した比較対象データの属するグループを前記比較回路部が判定したときには、前記判定されたグループの最後の識別情報以降の識別情報を少なくともシフトさせ、前記入力した比較対象データに対応付けられた識別情報の格納場所を確保するものである。
【０００８】
このソート回路では、比較対象データ記憶部が、ソート対象であるソートデータに応じた比較対象データを記憶し、タグ回路部が、比較対象データに対応付けられた識別情報をタグ回路部に含まれるグループごとに格納する。次に、比較回路部が、ソートデータの比較対象データを入力すると、タグ回路部に格納された識別情報を用い各グループの比較対象データの代表値を取得し、取得した代表値と入力した比較対象データとを比較し、入力した比較対象データの属するグループを判定する。このとき、タグ回路部は、判定されたグループの最後の識別情報以降の識別情報を少なくともシフトさせ、入力した比較対象データに対応付けられた識別情報の格納場所を確保する。続いて、判定したグループ内の比較対象データと、入力した比較対象データとを比較し、入力した比較対象データのタグ回路部の格納場所を判定し、入力した比較対象データに対応付けられた識別情報をこの判定結果に基づいてタグ回路部の格納場所に出力する。このように、比較対象データをグループ分けし、その代表値を用いて入力した比較対象データが属するグループを求め、その後、グループ内での序列を定めることにより、入力した比較対象データと、既に記憶している比較対象データとの比較回数をより低減するのである。また、タグ回路部は、データ量の小さい識別情報をソート管理するのである。更に、タグ回路部は、格納した識別情報を一群としてシフト可能であるため、入力した比較対象データの識別情報を、より容易に挿入することができる。したがって、データのソートをより効率的に実行することができる。ここで、前記タグ回路部は、前記識別情報をシフトさせるに際して、前記判定されたグループに含まれる識別情報の一部に対してもシフトさせるものとしてもよい。
【０００９】
本発明のソート回路において、前記タグ回路部は、複数のレジスターを含む複数のグループにより構成され、該複数のレジスターはパイプライン状に接続されているものとしてもよい。こうすれば、複数のレジスターを用いてデータのソートをより効率的に実行することができる。また、比較的容易にデータのシフト機能を実現することができる。
【００１０】
本発明のソート回路において、前記比較回路部は、前記タグ回路部の前記グループ間において所定間隔で格納された比較対象データを前記代表値として取得するものとしてもよい。こうすれば、所定間隔の比較対象データを用いて比較するため、回路構成により処理を実行しやすい。ここで、「所定間隔」とは、比較対象データの数（識別情報の数）に基づいて定めるものとしてもよい。このとき、前記所定間隔は、グループに含まれる比較対象データの数としてもよい。こうすれば、代表値はグループに１つとなる。また、比較対象データの代表値は、グループに１つであることが好ましいが、グループに２以上あるものとしてもよい。このとき、すべての代表値が所定間隔であることが好ましい。
【００１１】
本発明のソート回路は、前記ソートデータを記憶するソートデータ記憶部、を備え、前記ソートデータ記憶部は、前記ソートデータを記憶し、前記比較データ記憶部は、前記ソートデータ記憶部に比して高速なリードライトを実行可能であり、前記ソートデータの比較対象データを格納するものとしてもよい。こうすれば、データ本体は低速なデータ記憶部に格納し、比較的頻繁に読み出される比較対象データは高速な比較データ記憶部に記憶するから、データのソートを更に効率的に実行することができる。このとき、前記ソートデータ記憶部はＤＲＡＭであり、前記比較データ記憶部はＳＲＡＭであるものとしてもよい。
【００１２】
本発明のソート回路において、前記比較回路部は、前記入力した比較対象データの昇順又は降順の序列を判定し、前記タグ回路部は、前記識別情報を昇順又は降順の序列で格納するものとしてもよい。
【００１３】
本発明のソート回路は、前記タグ回路部に記憶された前記識別情報の格納場所に基づいて前記ソートデータを読み出す読出回路部、を備えたものとしてもよい。こうすれば、効率的にソートされた識別情報を用いて、ソートデータをソートした状態でより効率的に読み出すことができる。
【図面の簡単な説明】
【００１４】
【図１】マルチファンクションプリンター２０の構成の概略を示す構成図。
【図２】タグ回路４２の構成の概略を示す構成図。
【図３】レジスターグループ５０の構成の概略を示す構成図。
【図４】降順ソート処理ルーチンの一例を示すフローチャート。
【図５】ソート処理の説明図。
【図６】比較対象データの識別情報に対するシフト処理の説明図。
【発明を実施するための形態】
【００１５】
次に、本発明の実施の形態を図面を用いて説明する。図１は、本発明の一実施形態であるマルチファンクションプリンター２０の構成の概略を示す構成図である。図２は、タグ回路４２の構成の概略を示す構成図である。図３は、レジスターグループ５０の構成の概略を示す構成図である。本実施形態のマルチファンクションプリンター２０は、装置全体の制御を司るコントローラー２１と、外部機器との通信を行うネットワークインターフェイス（Ｉ／Ｆ）２６と、表示部と操作部とを有しユーザーによる各種操作が可能な操作パネル２８と、原稿を光学的に読み取ってイメージデータを生成するスキャナーユニット３０と、印刷媒体に画像を印刷するプリンターユニット３５と、を備える。
【００１６】
コントローラー２１は、ＣＰＵ２２を中心とするマイクロプロセッサーとして構成されており、各種処理プログラムや各種データ、各種テーブルなどを記憶したフラッシュメモリー２３と、一時的にスキャンデータや印刷データを記憶するＲＡＭ２４とを備える。コントローラー２１は、スキャナーユニット３０やプリンターユニット３５からの各種動作信号や各種検出信号を入力したり、操作パネル２８のタッチ操作に応じて発生する操作信号を入力したりする。また、コントローラー２１は、操作パネル２８からのスキャン指令に基づいて原稿を画像データとして読み取るようスキャナーユニット３０に指令を出力したり、画像データの印刷を実行するようプリンターユニット３５に指令を出力したりする。
【００１７】
操作パネル２８は、中央に配置された表示部と、この表示部を含んで構成された操作部とを備える。表示部は、タッチパネル式の液晶ディスプレイとして構成されており、モードを選択するモードボタンや、ディスプレイ上に表示される案内に従ってタッチすることによりメニューや項目を選択する選択／設定ボタン，スキャンやコピー、印刷を開始するスタートボタンなどを表示してタッチ操作を受け付ける。
【００１８】
スキャナーユニット３０は、スキャナーＡＳＩＣ３１と、コンタクトイメージセンサーモジュール（ＣＩＳＭ）３４などを有するスキャナーエンジン３２とを備える。スキャナーＡＳＩＣ３１は、スキャナーエンジン３２を制御する集積回路であり、コントローラー２１からのスキャン指令を受けると、原稿をイメージデータとして読み取るようスキャナーエンジン３２を制御する。スキャナーエンジン３２は、赤色光、緑色光及び青色光を点灯し原稿に照射する光源ユニットと、原稿からの反射光を受光素子で受光して電荷として蓄えることにより原稿を読み取るＣＩＳとを搭載したＣＩＳＭ３４により、各色の点灯を順次切り替えながら反射光を一色ずつ読み取ることによりカラーイメージデータを生成する。
【００１９】
プリンターユニット３５は、プリンターＡＳＩＣ３６とプリンターエンジン３７とを備える。プリンターＡＳＩＣ３６は、プリンターエンジン３７を制御する集積回路であり、コントローラー２１から印刷指令を受けると、印刷指令の対象となる画像ファイルに基づいて印刷媒体に画像を印刷するようプリンターエンジン３７を制御する。プリンターエンジン３７は、印刷ヘッドから印刷媒体へインクを吐出することにより印刷を行う周知のインクジェット方式のカラープリンター機構として構成されている。
【００２０】
また、コントローラー２１は、入力したデータ（ソートデータとも称する）を並べ替える機能を有するソート回路４０を備えている。このソート回路４０は、比較回路４１、タグ回路４２、読出回路４４及びメモリー４５を備えている。このソート回路４０では、例えば、ソートデータを画像データとし、並べ替えを行う対象である比較対象データを画像データに含まれる座標ごとの輝度値とし、比較対象データを並べ替えて画像データに含まれる輝度値の高い座標を求めるという場合に、画像データの本体をＲＡＭ２４に記憶すると共に、比較対象データとしての各座標の輝度値をメモリー４５に記憶し、この比較対象データの序列に応じて並べ替えて出力する処理を実行する。このとき、ソート回路４０は、比較対象データに対応する識別情報（例えばメモリー４５のアドレス）をタグ回路４２に格納し、この識別情報を用いて、入力した比較対象データと記憶済みの比較対象データとの比較処理を行い、入力した比較対象データに対応する識別情報を比較結果に基づいてタグ回路４２に挿入する処理を行い、比較対象データのソートを行う。
【００２１】
まず、タグ回路４２から説明する。タグ回路４２は、比較回路４１及び読出回路４４に接続されており、比較回路４１の比較処理に基づいて、比較対象データに対応する識別情報を昇順又は降順の序列で格納する回路として構成されている。このタグ回路４２は、複数のレジスターグループ５０が形成されており、比較対象データに対応付けられた識別情報をこのレジスターグループ５０ごとに格納する。即ち、タグ回路４２は、図２に示すように、複数のレジスターグループ５０と、セレクター５１とを備えており、図３に示すように、このレジスターグループ５０が更に複数のアドレス格納レジスター５２を備えている。このソート回路４０では、１６個のアドレス格納レジスター５２を備えたレジスターグループ５０を１６個備え、全体で２５６個の比較対象データの識別情報を格納可能に構成されている。アドレス格納レジスター５２は、フリップフロップにより構成され、例えば８ｂｉｔのデータを格納可能なレジスターである。このアドレス格納レジスター５２は、比較対象データの記憶されたメモリー４５のアドレスの情報などを格納する。また、タグ回路４２は、上位のレジスターグループ５０の出力の一部が下位のレジスターグループ５０の入力に接続されると共に、各レジスターグループ５０においても、上位のアドレス格納レジスター５２の出力の一部が下位のアドレス格納レジスター５２の入力に接続されて連なった接続状態となっている。即ち、タグ回路４２は、複数のレジスターグループ５０がパイプライン状に接続されると共に、複数のアドレス格納レジスター５２がパイプライン状に接続されている。このように、タグ回路４２は、入力したシフト信号に基づいて、格納された一群のデータを１以上シフトするシフト機能を有した回路として構成されている。このタグ回路４２は、入力した比較対象データの属するレジスターグループ５０を比較回路４１が判定したときには、シフト信号に基づいて、判定されたレジスターグループ５０を含む識別情報をシフトさせ、入力した比較対象データに対応付けられた識別情報の格納場所を確保する処理を行う。また、タグ回路４２は、読出回路４４から出力された信号に基づいて、複数のレジスターグループ５０のうち１つのデータをセレクター５１により選択し、比較回路４１へ出力する機能を有している。
【００２２】
比較回路４１は、図１に示すように、タグ回路４２及びメモリー４５に接続されており、比較対象データを入力すると、入力した比較対象データを入力順にメモリー４５に出力すると共に、入力した比較対象データの昇順又は降順の序列を判定する回路として構成されている。この比較回路４１は、ソートデータの比較対象データを入力し、タグ回路４２に格納された識別情報を用い各レジスターグループ５０の比較対象データの代表値を取得し、取得した代表値と入力した比較対象データとを比較し、入力した比較対象データの属するレジスターグループ５０をこの比較結果に基づいて判定する。このとき、比較回路４１は、入力した比較対象データのデータ数をカウントする処理も行う。比較回路４１は、タグ回路４２のレジスターグループ５０間において所定間隔で格納された比較対象データを代表値として取得する。ここでは、各々のレジスターグループ５０に格納された最後尾の値が、レジスターグループ５０の代表値に定められている。即ち、レジスターグループ５０間の所定間隔は、レジスターグループ５０に格納される比較対象データの数（１６個）に定められており、レジスターグループ５０の代表値は各々のレジスターグループ５０で１つとなっている。また、比較回路４１は、この判定したレジスターグループ５０内の比較対象データと入力した比較対象データとを比較し、入力した比較対象データのタグ回路４２の格納場所を判定し、入力した比較対象データに対応付けられた識別情報をこの判定結果に基づいてタグ回路４２の格納場所に出力する。
【００２３】
読出回路４４は、タグ回路４２及びメモリー４５に接続されており、タグ回路４２に格納された識別情報の格納場所に基づいてソートデータを読み出す機能を有する回路として構成されている。
【００２４】
メモリー４５は、ソートデータの比較対象データを少なくとも記憶する比較データ記憶部であり、ソートデータを記憶するＲＡＭ２４（例えばＤＲＡＭ）に比して高速なリードライトを実行可能なメモリー（例えばＳＲＡＭ）として構成されている。このメモリー４５は、その記憶容量が、タグ回路４２の格納可能なデータ量よりも大きく、ＲＡＭ２４の格納可能なデータ量よりも小さい範囲で設定されている。このメモリー４５は、入力した比較対象データをその入力順に記憶する。
【００２５】
次に、こうして構成された本実施形態のソート回路４０の動作、特に、比較対象データをデータ順に入力し、所定の序列（ここでは、より大きな値を上位とする降順）にソートする処理について説明する。図４は、降順にデータをソートする降順ソート処理ルーチンの一例を示すフローチャートである。図５は、ソート処理の説明図であり、図６は、比較対象データの識別情報をシフトするシフト処理の説明図であり、図６（ａ）がシフト前のレジスターグループ５０の状態、図６（ｂ）がシフト直後のレジスターグループ５０の状態、図６（ｃ）が比較対象データを格納した状態である。降順ソート処理ルーチンは、ソート回路４０の比較回路４１、タグ回路４２、読出回路４４及びメモリー４５などにより実行される。
【００２６】
まず、ソートデータが入力されると、入力したソートデータの比較対象データＸを比較回路４１が入力し（ステップＳ１００）、比較対象データＸをメモリー４５に出力して記憶させると共に、入力した比較対象データＸの識別情報ｘを取得し、入力したデータ数Ｙを更新する（ステップＳ１１０）。次に、データ数Ｙが所定値Ｙ１以上であるか否かを判定する（ステップＳ１２０）。ここでは、所定値Ｙ１は、レジスターグループ５０に含まれるアドレス格納レジスターの数である値１６に設定されている。データ数Ｙが所定値Ｙ１以上でないときには、２番目以降のレジスターグループ５０にはデータが格納されていないものとみなし、入力したデータを格納するレジスターグループ５０の番号ｍを値１に判定する（ステップＳ１３０）。即ち、入力した比較対象データＸの識別情報ｘはレジスターグループｍ＝１のグループに属するものと判定し、この識別情報ｘをレジスターグループｍ＝１のグループに格納する設定とする。
【００２７】
次に、比較回路４１は、設定されたレジスターグループ５０内のアドレス格納レジスターの番号ｎに値１をセットする（ステップＳ２００）。続いて、設定されたレジスターグループ５０内のアドレス格納レジスターｎに格納された識別情報を取得すると共に、それに対応する比較対象データＸｎをメモリー４５から取得する（ステップＳ２１０）。メモリー４５から取得した比較対象データＸｎと入力した比較対象データＸとを比較し（ステップＳ２２０）、比較対象データＸが比較対象データＸｎ以上でないときには、このアドレス格納レジスターｎに比較対象データＸｎの識別情報を格納すると共に、レジスター番号ｎを値１インクリメントし（ステップＳ２３０）、ステップＳ２１０以降の処理を行う。即ち、次のアドレス格納レジスターに格納された識別情報に対応した比較対象データＸｎと比較対象データＸとの比較を行う。なお、比較する対象のデータが存在しない場合、すなわち最初の比較対象データでは、直接タグ回路４２の１番目のアドレス格納レジスターへ識別情報を格納してもよい。続いて、ステップＳ２２０で比較対象データＸが比較対象データＸｎ以上であるときには、入力した比較対象データＸの識別情報を、格納位置であるアドレス格納レジスターに出力する（ステップＳ２４０）。このとき、タグ回路４２は、格納位置であるアドレス格納レジスターに比較対象データＸの識別情報を格納する。ここで、ソート回路４０では、アドレス格納レジスター５２は、図３に示すように、共通のｃｌｏｃｋ信号により動作しており、アドレス格納レジスター５２は、ｃｌｏｃｋ信号に同期したｗｒｉｔｅ信号が値１になることにより更新される。このとき、ｓｈｉｆｔ信号が値１であるか値０であるかにより、アドレス格納レジスター５２へ、入力した比較対象データＸの識別情報を格納するか、格納済みの比較対象データＸｎの識別情報を格納するかを切り替えるものとした。そして、次の比較対象データを入力したか否かを比較回路４１が判定し、比較対象データを入力したときにはステップＳ１００以降の処理を実行する。
【００２８】
一方、ステップＳ１２０でデータ数Ｙが所定値Ｙ１以上であるときには、２番目以降のレジスターグループ５０にもデータが格納されているものとして、比較回路４１は、レジスターグループ５０の番号ｍに値１をセットする（ステップＳ１４０）。次に、比較回路４１は、番号ｍのレジスターグループ５０の代表の識別情報を取得すると共に、それに対応する比較対象データＸｍをメモリー４５から取得する（ステップＳ１５０）。ここでは、代表値は、各レジスターグループ５０の最後尾の値を代表値とするよう設定されている（図６参照）。次に、メモリー４５から取得した比較対象データＸｍと入力した比較対象データＸとを比較し（ステップＳ１６０）、比較対象データＸが比較対象データＸｍを超えないときには、入力した比較対象データＸがこれ以降のグループに属するものとして、レジスター番号ｍを値１インクリメントし（ステップＳ１７０）、ステップＳ１５０以降の処理を行う。即ち、次のレジスターグループ５０の代表値の比較対象データＸｍと比較対象データＸとの比較を行う。一方、ステップＳ１６０で比較対象データＸが比較対象データＸｍを超えるときには、この比較対象データＸがレジスター番号ｍのレジスターグループ５０に属するものと判定する（ステップＳ１８０）。
【００２９】
続いて、比較回路４１は、ステップＳ１９０でタグ回路４２のシフト処理を実行し、入力した比較対象データＸの識別情報の格納位置を確保し、ステップＳ２００以降の処理を実行する。このシフト処理では、タグ回路４２の機能を利用して、比較対象データＸの属するグループの最後の識別情報以降の識別情報を一群として繰り下げる処理を行う（図５，６参照）。具体的には、比較対象データＸｍの属するグループはそのままに、比較対象データＸの属するグループの次以降の識別情報を一群として繰り下げる処理と、比較対象データＸの属するグループの最後の識別情報を次のグループの先頭にコピーする処理を実行する。そして、上述したステップＳ２００以降と同様に、レジスターグループ５０内に含まれる識別情報に対応する比較対象データＸｎと、入力した比較対象データＸとの比較を行い、比較対象データＸの序列を求め、入力した比較対象データＸに対応する識別情報ｘを、レジスターグループ５０内のアドレス格納レジスター５２へ格納する処理を行うのである。
【００３０】
以上説明した降順ソート処理では、図５に示すように、比較回路４１は、比較対象データＸを入力すると（data#in）、タグ回路４２から識別情報を取得し（addr#out）、メモリー４５に比較対象データを出力させる信号を出力し（cmp#addr）、メモリー４５から比較対象データを取得する（cmp#data）。このとき、複数のレジスターグループ５０に識別情報が格納されているときには、レジスターグループ５０の代表値を取得する。そして、比較対象データ同士を比較し、入力した比較対象データの属するレジスターグループ５０を判定する。すると、タグ回路４２では、図６（ｂ）に示すように、レジスターグループ５０に格納されている識別情報を一群としてシフトする。そして、図６（ｃ）に示すように、判定されたグループでの、入力した識別情報の順位を判定し、判定した順位の位置に入力した識別情報ｘを格納させるのである（Tag#write）。
【００３１】
その後、読出回路４４は、所定のタイミングで、ソートされた順に比較対象データを読み出す信号をタグ回路４２へ出力し（select#order）、タグ回路４２の記憶内容に基づいて比較対象データのアドレスを取得する（addr#out）。読出回路４４は、このアドレスに基づいてメモリー４５へ比較対象データを出力する信号を送り（sort#addr）、メモリー４５から出力される比較対象データを取得するのである（read#data）。
【００３２】
ここで、本実施形態の構成要素と本発明の構成要素との対応関係を明らかにする。本実施形態のメモリー４５が本発明の比較データ記憶部に相当し、ＲＡＭ２４がソートデータ記憶部に相当し、タグ回路４２がタグ回路部に相当し、比較回路４１が比較回路部に相当し、アドレス格納レジスター５２がレジスターに相当する。
【００３３】
以上詳述した本実施形態のソート回路４０によれば、ＳＲＡＭであるメモリー４５が、ソートデータに応じた比較対象データを記憶し、タグ回路４２が、比較対象データに対応付けられた識別情報をレジスターグループ５０ごとに格納する。次に、比較回路４１が、ソートデータの比較対象データＸを入力すると、タグ回路４２に格納された識別情報を用い各グループの比較対象データの代表値Ｘｍを取得し、取得した代表値と入力した比較対象データＸとを比較し、入力した比較対象データＸの属するレジスターグループ５０を判定する。このとき、タグ回路４２は、判定されたもの以降のレジスターグループ５０に含まれる識別情報を少なくともシフトさせ、入力した比較対象データＸに対応付けられた識別情報の格納場所を確保する。続いて、判定したグループ内の比較対象データＸｎと、入力した比較対象データＸとを比較し、入力した比較対象データＸのタグ回路４２の格納場所を判定し、入力した比較対象データＸに対応付けられた識別情報をこの判定結果に基づいてタグ回路４２に出力する。このように、比較対象データをグループ分けし、その代表値を用いて入力した比較対象データＸが属するレジスターグループ５０を求め、その後、グループ内での序列を定めることにより、入力した比較対象データＸと、既に記憶している比較対象データとの比較回数をより低減するのである。また、タグ回路４２は、データ量の小さい識別情報をソート管理するのである。更に、タグ回路４２は、格納した識別情報を一群としてシフト可能であるため、入力した比較対象データＸの識別情報を、より容易に挿入することができる。したがって、データのソートをより効率的に実行することができる。
【００３４】
また、ソート回路４０は、複数のアドレス格納レジスター５２を含む複数のレジスターグループ５０により構成され、複数のアドレス格納レジスター５２はパイプライン状に接続されているため、複数のレジスターを用いてデータのソートをより効率的に実行することができるし、比較的容易にデータのシフト機能を付与することができる。更に、所定間隔で格納された比較対象データを代表値として取得して比較するため、回路構成により処理を実行しやすい。更にまた、メモリー４５は、ＲＡＭ２４に比して高速なリードライトを実行可能なＳＲＡＭであるため、ソートデータの本体は低速なＤＲＡＭに格納し、比較的頻繁に読み出される比較対象データは高速なＳＲＡＭに記憶することにより、データのソートを更に効率的に実行することができる。そして、読出回路４４は、効率的にソートされた識別情報を用いて、ソートデータをソートした状態でより効率的に読み出すことができる。
【００３５】
なお、本発明は上述した実施形態に何ら限定されることはなく、本発明の技術的範囲に属する限り種々の態様で実施し得ることはいうまでもない。
【００３６】
例えば、上述した実施形態では、タグ回路４２は、アドレス格納レジスター５２がパイプライン状に接続されているものとしたが、データをシフト可能な構成を有していれば、特にこれに限定されない。こうしても、データのソートをより効率的に実行することができる。
【００３７】
上述した実施形態では、レジスターグループ５０の代表値をレジスターグループ５０に格納された最後尾のデータとしたが、特にこれに限定されず、例えば、レジスターグループ５０に格納された先頭のデータとしてもよいし、中央のデータとしてもよいし、任意の位置のデータとしてもよい。また、レジスターグループ５０に格納された比較対象データの数（識別情報の数）を所定間隔としたが、特にこれに限定されず、任意の間隔としてもよい。なお、代表値はレジスターグループ５０に１つであることが好ましいが、レジスターグループ５０に２以上あるものとしてもよい。このとき、すべての代表値が所定間隔であることが好ましい。
【００３８】
上述した実施形態では、比較対象データを、高速なリードライトを実行可能なＳＲＡＭのメモリー４５に記憶するものとしたが、特にこれに限定されず、ＤＲＡＭとしてもよい。また、ソートデータの本体をＲＡＭ２４に記憶するものとしたが、メモリー４５に記憶するものとしてもよい。また、メモリー４５を省略してＲＡＭ２４に比較対象データを記憶するものとしてもよい。こうしても、データのソートをより効率的に実行することができる。
【００３９】
上述した実施形態では、比較対象データを降順でソートするものとしたが、特にこれに限定されず、昇順でソートしてもよいし、任意の方法でソートしてもよい。
【００４０】
上述した実施形態では、２５６件のデータをソートすることとしたが、特にこれに限定されない。例えば、元のデータは１０００件あるが、使用するデータが昇順或いは降順の上位２５６件である場合に、本発明を適用すれば、１０００件分のメモリー容量を必要とせず、本発明の実施形態のように２５６件分のメモリー容量があれば、上位２５６件のソートしたデータを得ることができる。その場合、２５６件目以降の比較対象データを格納するメモリー内の位置は、昇順或いは降順の最下位である２５６番目の位置に格納されている比較対象データと比較して、採用すべきデータである場合に２５６番目の位置に格納すればよい。
【００４１】
上述した実施形態では、マルチファンクションプリンター２０として説明したが、印刷を実行可能なプリンター単体としてもよいし、印刷、スキャン、コピー及びＦＡＸ機能を備えたＦＡＸ装置などとしてもよい。また、プリンターユニット３５は、インクジェット方式としたが、電子写真方式や、熱転写方式、ドットインパクト方式としてもよい。また、ソート回路４０を備えたマルチファンクションプリンター２０としたが、データをソートするものであれば特にこれに限定されず、例えば、携帯電話や携帯ゲーム機などの携帯機器、ビデオカメラ他デジタルカメラなどの撮影機器、テレビやＨＤＤレコーダーなどの映像機器、ＰＣなどの情報処理機器などとしてもよい。
【符号の説明】
【００４２】
２０  マルチファンクションプリンター、２１  コントローラー、２２  ＣＰＵ、２３  フラッシュメモリー、２４  ＲＡＭ、２６  ネットワークインターフェイス（Ｉ／Ｆ）、２８  操作パネル、３０  スキャナーユニット、３１  スキャナーＡＳＩＣ、３２  スキャナーエンジン、３４  コンタクトイメージセンサーモジュール（ＣＩＳＭ）、３５  プリンターユニット、３６  プリンターＡＳＩＣ、３７  プリンターエンジン、４０  ソート回路、４１  比較回路、４２  タグ回路、４４  読出回路、４５  メモリー、５０  レジスターグループ、５１  セレクター、５２  アドレス格納レジスター。
【図１】
0005919878.tif 000002
【図２】
0005919878.tif 000003
【図３】
0005919878.tif 000004
【図４】
0005919878.tif 000005
【図５】
0005919878.tif 000006
【図６】
0005919878.tif 000007