(57)【要約】【課題】ソート処理の一層の高速化を図る。【解決手段】複数のユニットＵＮ(1)〜ＵＮ(n)がリング状に複数段接続されており、それぞれが、シンボル列の一部を格納する記憶領域を有し、かつ、それぞれが、自己の記憶領域に格納されたシンボルをサイクル毎に後段へシフトする。このとき、これらのユニットＵＮ(1)〜ＵＮ(n)は、ソートの対象となるシンボル列の論理的な列構成を維持しながらソート処理を実行する比較ユニットを含む。【選択図】図１
2007226744.tif 000002
【特許請求の範囲】
【請求項１】
値の大小を比較可能な複数のシンボルで構成されたシンボル列に対するソート処理を繰り返し実行することによって、シンボル列を所定のソート順序に並び替えるバブルソート回路において、
リング状に複数段接続され、それぞれが、シンボル列の一部を格納する記憶領域を有するとともに、それぞれが、自己の記憶領域に格納されたシンボルをサイクル毎に後段へシフトする複数のユニットと、
外部から入力されたシンボル列を複数の前記記憶領域に格納するとともに、前記複数の記憶領域から読み出されたシンボル列を外部に出力する入出力部と、
前記複数のユニットの同期制御を行うとともに、前記複数のユニットによって構成されたリングにおける、シンボル列の先端シンボルの格納場所と末端シンボルの格納場所との境界を示す境界位置を管理する制御部とを有し、
前記複数のユニットの少なくとも一つは、比較ユニットであり、
前記比較ユニットは、
自己の前記記憶領域から読み出されたシンボルのセットが前記境界位置を跨がない場合、前記シンボルのセットを値の大小も応じて並び替えた上で、前記シンボルのセットの一部を後段のユニットにシフトするとともに、前記シンボルのセットの残りを自己のユニット内に格納し続ける第１の処理を行い、
前記シンボルのセットが前記境界位置を跨ぐ場合、前記シンボルのセットにおける前記境界位置を跨ぐ部分の並び替えを行うことなく、前記シンボルのセットの一部を後段のユニットにシフトするとともに、前記シンボルのセットの残りを自己のユニット内に格納し続ける第２の処理を行うことを特徴とするバブルソート回路。
【請求項２】
前記複数のユニットのいずれもが、各サイクルで互いに並列に動作する前記比較ユニットであることを特徴とする請求項１に記載されたバブルソート回路。
【請求項３】
前記比較ユニットは、
前記第１の処理および前記第２の処理のいずれかを選択的に行う比較器と、
第１のサイクルで前記比較器に入力すべきシンボルを格納するとともに、前記第１のサイクルで前段のユニットからシフトされたシンボルを、前記第１のサイクルに続く第２のサイクルで前記比較器に入力すべきシンボルとして格納する第１の記憶領域と、
前記第１のサイクルで前記比較器に入力すべきシンボルを格納するとともに、前記第１のサイクルで前記比較器から出力された前記他方のシンボルを、前記第２のサイクルで前記比較器に入力すべきシンボルとして格納する第２の記憶領域と
を有することを特徴とする請求項１または２に記載されたバブルソート回路。
【請求項４】
前記制御部は、前記サイクルの回数をカウントし、当該カウントされた回数が所定の回数に到達した場合、当該サイクルの処理の終了後に、前記入出力部に対して前記シンボル列の出力を指示することを特徴とする請求項１に記載されたバブルソート回路。
【請求項５】
前記所定の回数は、少なくとも前記シンボル列を構成するシンボルの個数と、前記比較ユニットの数とに基づいて、予め設定されていることを特徴とする請求項４に記載されたバブルソート回路。
【請求項６】
前記入出力部は、前記制御部からの出力指示を受けた場合、前記境界位置によって特定される順序で、前記複数の記憶領域のそれぞれから読み出されたシンボルを外部に出力することを特徴とする請求項４または５に記載されたバブルソート回路。
【請求項７】
前記制御部は、
前記サイクルの推移に応じて前記境界位置を順次シフトすることによって、前記境界位置を管理し、
あるサイクルにおいて、自己の前記記憶領域から読み出されるシンボルのセットが前記境界位置を跨がない前記比較ユニットに対しては、当該サイクルで前記第１の処理を行うべき旨を指示するとともに、前記シンボルのセットが前記境界位置を跨ぐ前記比較ユニットに対しては、当該サイクルで前記第２の処理を行うべき旨を指示することを特徴とする請求項１に記載されたバブルソート回路。
【請求項８】
前記制御部は、前記入出力部に外部から入力されたシンボル列を前記複数の記憶領域に格納する際、当該シンボル列に前記境界位置を示す境界シンボルを付加することによって、前記境界位置を管理し、
前記比較ユニットは、自己の前記記憶領域から読み出されたシンボルのセットが前記境界シンボルを含む場合、前記境界位置を跨ぐと判断して、前記シンボルのセットにおける前記境界位置を跨ぐ部分について前記第２の処理を行うことを特徴とする請求項１に記載されたバブルソート回路。
【請求項９】
請求項１から８のいずれかに記載されたバブルソート回路と、
前記バブルソート回路によって前記ソート順序に並び替えられた前記シンボル列に基づいてハフマン符号化を行うハフマン符号化回路と
を有することを特徴とするデータ圧縮システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、値の大小を比較可能な複数のシンボルで構成されたシンボル列を所定のソート順序に並び替えるソート処理に関する。
【背景技術】
【０００２】
ソート処理の一つとして、バブルソート（基本交換法または単純交換法）と呼ばれる方法が知られている。従来のバブルソートは、その回路構成が比較的小規模で済む反面、一回のサイクルで実行される処理が隣り合う一対のシンボルを入力とした１回の比較に留まる。そのため、シンボル列中の構成要素が多くなるほど比較処理の回数が多くなり、ソート完了までに長時間を要する。
【０００３】
処理の高速化を図るために、特許文献１には、ソート処理を並列に実行するバブルソート回路が開示されている。このバブルソート回路は、シリアルな入出力に対して多段かつ列状に直列接続された複数の比較回路で構成されており、単一の比較回路は、一つの比較器と、その比較対象となる２つのシンボルを格納するための一対の記憶領域とを有する。この回路の動作としては、まず、直列に接続された比較回路のうち、最前段の比較回路における一方の記憶領域に、ソート対象となるシンボル列を構成する一つのシンボルが入力される。この入力シンボルは、他方の記憶領域に格納されたシンボルと比較される。この比較の結果、大きい方のシンボルは自己の記憶領域に格納され、小さい方のシンボルは後段（２段目）の比較回路に転送され、その一方の記憶領域に格納される（ソート処理）。そして、２段目以降の比較回路においても、一対の記憶領域における格納値の比較およびその並べ替えが実行される。なお、それぞれの記憶領域は、初期時に未設定状態（最小値）として設定されている。このソート処理は、シンボル列を構成する個々のシンボルがシリアルに入力する毎に各比較回路において同時並行的に実行される。そして、全てのシンボルの入力が完了した場合、ソート対象となるシンボル列を構成する個々のシンボルが最前段の比較回路に順次転送され、これを介してシリアルに出力される。その際、シンボルの出力に応じて、出力されなかった一方の記憶領域に格納されたシンボルと、後段の比較回路から出力されたシンボルとを比較が行われ、これらを並び替えた上で記憶領域に格納される。
【０００４】
【特許文献１】特開平１０−１４９２７６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
特許文献１のバブルソート回路は、それぞれの比較回路でのソート処理を同時並行的に行うものである。しかしながら、シンボルのシリアルな入出力と連動して各段のソート処理が行われるため、特にシンボル入力の初期段階およびシンボル出力の後期段階では、全ての比較回路が動作せずに部分的な並列動作に留まる。その結果、初期段階等では並列処理のメリットを十分に活かすことができず、これが全体的な処理の高速化を図る上でのボトルネックとなる。
【０００６】
本発明の目的は、従来の構成とは全く異なる新規なバブルソート回路を提供することである。
【０００７】
また、本発明の別の目的は、ソート処理の一層の高速化を図ることである。
【課題を解決するための手段】
【０００８】
かかる課題を解決するために、第１の発明は、値の大小を比較可能な複数のシンボルで構成されたシンボル列に対するソート処理を繰り返し実行することによって、シンボル列を所定のソート順序に並び替えるバブルソート回路を提供する。このバブルソート回路は、複数のユニットと、入出力部と、制御部とを有する。複数のユニットは、リング状に複数段接続され、それぞれが、シンボル列の一部を格納する記憶領域を有するとともに、それぞれが、自己の記憶領域に格納されたシンボルをサイクル毎に後段へシフトする。入出力部は、外部から入力されたシンボル列を複数の記憶領域に格納するとともに、複数の記憶領域から読み出されたシンボル列を外部に出力する。制御部は、複数のユニットの同期制御を行うとともに、境界位置を管理する。この境界位置は、複数のユニットによって構成されたリングにおける、シンボル列の先端シンボルの格納場所と末端シンボルの格納場所との境界を示す。複数のユニットの少なくとも一つは、比較ユニットである。比較ユニットは第１の処理または第２の処理を行う。第１の処理は、自己の記憶領域から読み出されたシンボルのセットが境界位置を跨がない場合に実行される。この場合、シンボルのセットを値の大小に応じて並び替えた上で、シンボルのセットの一部を後段のユニットにシフトするとともに、シンボルのセットの残りを自己のユニット内に格納し続ける。また、第２の処理は、シンボルのセットが境界位置を跨ぐ場合に実行される。この場合、シンボルのセットにおける境界位置を跨ぐ部分の並び替えを行うことなく、シンボルのセットの一部を後段のユニットにシフトするとともに、シンボルのセットの残りを自己のユニット内に格納し続ける。
【０００９】
ここで、第１の発明において、複数のユニットのいずれもが、各サイクルで互いに並列に動作する比較ユニットであることが好ましい。
【００１０】
また、第１の発明において、比較ユニットは、第１の処理および第２の処理のいずれかを選択的に行う比較器と、第１のサイクルで比較器に入力すべきシンボルを格納するとともに、第１のサイクルで前段のユニットからシフトされたシンボルを、第１のサイクルに続く第２のサイクルで比較器に入力すべきシンボルとして格納する第１の記憶領域と、第１のサイクルで比較器に入力すべきシンボルを格納するとともに、第１のサイクルで比較器から出力された他方のシンボルを、第２のサイクルで比較器に入力すべきシンボルとして格納する第２の記憶領域とを有することが好ましい。
【００１１】
また、第１の発明において、制御部は、サイクルの回数をカウントし、このカウントされた回数が所定の回数に到達した場合、サイクルの処理の終了後に、入出力部に対してシンボル列の出力を指示することが好ましい。このとき、所定の回数は、少なくともシンボル列を構成するシンボルの個数と、比較ユニットの数とに基づいて、予め設定されていることが好ましい。
【００１２】
また、第１の発明において、入出力部は、制御部からの出力指示を受けた場合、境界位置によって特定される順序で、複数の記憶領域のそれぞれから読み出されたシンボルを外部に出力することが好ましい。
【００１３】
さらに、第１の発明において、制御部は、サイクルの推移に応じて境界位置を順次シフトすることによって、境界位置を管理し、あるサイクルにおいて、自己の記憶領域から読み出されるシンボルのセットが境界位置を跨がない比較ユニットに対しては、サイクルで第１の処理を行うべき旨を指示するとともに、シンボルのセットが境界位置を跨ぐ比較ユニットに対しては、サイクルで第２の処理を行うべき旨を指示することが好ましい。また、制御部は、入出力部に外部から入力されたシンボル列を複数の記憶領域に格納する際、シンボル列に境界位置を示す境界シンボルを付加することによって、境界位置を管理してもよく、その場合、比較ユニットは、自己の記憶領域から読み出されたシンボルのセットが境界シンボルを含む場合、境界位置を跨ぐと判断して、シンボルのセットにおける境界位置を跨ぐ部分について第２の処理を行う。
【００１４】
第２の発明は、上述したような構成を有する第１の発明にかかるバブルソート回路と、このバブルソート回路によってソート順序に並び替えられたシンボル列に基づいてハフマン符号化を行うハフマン符号化回路とを有するデータ圧縮システムを提供する。
【発明の効果】
【００１５】
第１の発明によれば、制御部の制御下において、それぞれのユニットが後段に対してシンボルをシフトするので、複数のユニットによって構成されるリング全体で見た場合、このリング内でシンボル列が循環する。複数のユニットには少なくとも一つの比較ユニットが含まれているので、リング内におけるシンボル列の循環に伴い、シンボル列の並び替えが徐々に進行していく。その際、シンボル列の境界位置を管理することによって、シンボル列において本来的に隣り合わない先端・末端に位置するシンボル同士（リングにおいては隣り合って見える）についてはソートが規制される。これにより、シンボル列をリング状に配置しても本来の列構成が論理的に維持され、かつ、この列構成を考慮したソートが行われるので、正しいソート結果が得られるのを保証できる。特に、複数の比較ユニットを用いる場合には、それぞれの比較ユニットが担うソート処理が同時並行的に行われるので、全体的な処理の高速化を図ることが可能になる。
【００１６】
また、第２の発明によれば、ハフマン符号化に先立ち必要となるシンボル列のソート処理が高速化されるので、全体的なデータ圧縮処理の高速化を図ることができる。
【発明を実施するための最良の形態】
【００１７】
図１は、バブルソート回路１の全体構成図である。このバブルソート回路１は、値の大小を比較可能な複数のシンボルで構成されたシンボル列に対するソート処理を繰り返し実行することによって、シンボル列を所定のソート順序に並び替える。バブルソート回路１は、演算部２と、入出力部３と、制御部４とを有するが、この基本的な構成は、後述する各実施形態での具体的な回路構成例においても共通する。
【００１８】
演算部２は、複数のユニットＵＮ(1)〜ＵＮ(n)（ｎ≧２）を有しており、リング状に複数段接続されている。各ユニットＵＮ（ＵＮはＵＮ(1)〜ＵＮ(n)のいずれかを指す）は、シンボル列の一部を格納する記憶領域を有しており、自己の記憶領域に格納された所定個のシンボルを出力シンボルＳｙｍ（ＳｙｍはＳｙｍ(1)〜Ｓｙｍ(n)のいずれかを指す）としてサイクル毎に後段へシフトする。それぞれのユニットＵＮが後段に対して同数のシンボルを並行出力するので、ユニットＵＮ(1)〜ＵＮ(n)によって構成されるリング全体で見た場合、後述するようなソート処理を伴いながら、リング内でシンボル列が循環することになる（ただし、個々のシンボルが一様に循環するわけではない）。
【００１９】
ユニットＵＮには、記憶ユニットＳＵＮ、比較ユニットＣＵＮの二種類がある。記憶ユニットＳＵＮは、制御部４の指示によって実行されるシフト機能を備える。シフト機能は、制御部４から出力された同期信号ＳＮＣに応じて、自己の記憶領域に格納されたシンボルを出力シンボルＳｙｍとしてそのまま後段のユニットＵＮへシフトする機能である。この機能を果たすべく、記憶ユニットＳＵＮの記憶領域は、１回のサイクルでの転送数分のシンボルを格納可能な記憶容量を有する。一方、比較ユニットＣＵＮは、上記シフト機能に加えて、ユニット内に格納されたシンボルセットの並び替えを行うソート機能も有している。この並び替えに応じて、シンボルセットの一部が後段のユニットＵＮにシフトされ、その残りが同じユニット内に格納され続ける。そのため、比較ユニットＣＵＮの記憶領域は、記憶ユニットＳＵＮよりも大きな記憶容量、すなわち、１回のサイクルでの転送数分に格納継続分を加えた個数のシンボルを格納可能な記憶容量を有する。例えば、転送数が２シンボル、格納継続数が１シンボルの場合、比較ユニットＣＵＮの記憶領域は３シンボルを格納可能な容量を有する必要がある。なお、シンボル列の並び替えを行うためには、バブルソート回路１を構成するユニットＵＮ(1)〜ＵＮ(n)のうち、少なくとも一つが比較ユニットＣＵＮであることが前提となる。
【００２０】
入出力部３は、一連のソート処理の開始に先立ち、外部から入力されたシンボル列ＤinをユニットＵＮ(1)〜ＵＮ(n)が備える記憶領域に分散して格納する。また、入出力部３は、一連のソート処理の終了後、これらの記憶領域から読み出されたシンボルをまとめ、シンボル列Ｄoutとして外部に出力する。
【００２１】
制御部４は、ユニットＵＮ(1)〜ＵＮ(n)に同期信号ＳＮＣを出力することにより、これらの同期制御を行う。これによって、ユニットＵＮ(1)〜ＵＮ(n)の処理が同時並行的に行われる。また、制御部４は、サイクルの推移をカウントアップし、このカウントされた回数が予め設定された終了回数に到達した場合、このサイクルの処理の終了後に、入出力部３に対してシンボル列Ｄoutの出力を指示する。シンボル列Ｄinの並び替えが完了するサイクル数は、基本的に、シンボル列Ｄinを構成するシンボルの個数と、比較ユニットＣＵＮの個数とに基づいて一義的に特定される。ユニットＵＮ(1)〜ＵＮ(n)のすべてが比較ユニットの場合（後述する第１の実施形態のようなケース）、並び替えが完了するまでに要する終了回数は、シンボル列Ｄinの個数ｋのみに依存し、ｋサイクルとなる。しかしながら、ユニットＵＮ(1)〜ＵＮ(n)の一部が比較ユニットＣＵＮの場合（後述する第２の実施形態のようなケース）、シンボル列Ｄinの個数ｋ以外に比較ユニットＣＵＮの個数にも依存し、かつ、後述する境界位置の初期状態も関係してくる。なお、境界位置はサイクルの推移に応じて順次シフトするので、制御部４は境界位置の管理も行っている。
【００２２】
図２は、一例としての単一の比較ユニットＣＵＮの構成図である。この比較ユニットＣＵＮは、２つの記憶領域５ａ，５ｂと、比較器６とを有する。記憶領域５ａには、今回のサイクルで比較器６に入力すべきシンボル（比較対象の一方）が格納されている。この格納されているシンボルが比較器６に出力された後、このサイクルで前段のユニットＵＮからシフトされたシンボルＳｙｍ'が記憶領域５ａに格納される（格納内容の更新）。記憶領域５ａに新たに格納されたシンボルは、次回のサイクルで比較器６に入力すべきシンボルとなる。記憶領域５ｂには、今回のサイクルで比較器６に入力すべきシンボル（比較対象の他方）が格納されている。この格納されているシンボルが比較器６に出力された後、このサイクルで比較器６から出力されたシンボルが記憶領域５ｂに格納される（格納内容の更新）。記憶領域５ｂに新たに格納されたシンボルは、次回のサイクルで比較器６に入力すべきシンボルとなる。なお、記憶領域５ａ，５ｂの読み書きは、同期信号ＳＮＣによって制御される。
【００２３】
比較器６は、判定部７と、スイッチ８ａ，８ｂとを有する。スイッチ８ｂの一方の入力端子は、記憶領域５ａに接続されており、その他方の入力端子は、記憶領域５ｂに接続されている。判定部７による切換制御の下、スイッチ８ｂからの出力、すなわち、記憶領域５ａ，５ｂから読み出された一対のシンボルのいずれかがシンボルＳｙｍとして後段のユニットＵＮに出力される。スイッチ８ａの入力端子は、記憶領域５ａに接続されており、その出力端子は、記憶領域５ｂに接続されている。判定部７による導通制御の下、記憶領域５ａから読み出されたシンボルが記憶領域５ｂに適宜格納される。
【００２４】
スイッチ８ａのオン／オフ状態およびスイッチ８ｂの切換状態は、制御部４からの制御信号ＣＴＬと、記憶領域５ａ，５ｂから読み出されたシンボルの大小とに応じて、下表のように設定される。なお、同表において、”Ａ”は記憶領域５ａから読み出されたシンボルを指し、”Ｂ”は記憶領域５ｂから読み出されたシンボルを指す。
【００２５】
［スイッチ８ａ，８ｂの状態］
制御信号ＣＴＬ    シンボルの大小    スイッチ８ａ      スイッチ８ｂ
Ｌ（ソート指示）      Ａ＞Ｂ           オフ          記憶領域５ａ側
Ｌ（ソート指示）      Ｂ＜Ａ           オン          記憶領域５ｂ側
Ｈ（シフト指示）        −             オン          記憶領域５ｂ側
【００２６】
制御信号ＣＴＬによってソート処理が指示された場合（ＣＴＬ＝Ｌレベル）、判定部７は、記憶領域５ａ，５ｂより読み出されたシンボルセットＡ，Ｂの値の大小を比較し、この比較結果に応じてスイッチ８ａ，８ｂの状態を設定する。昇順ソートを例に説明すると、Ａ＞Ｂの場合には、スイッチ８ａがオフ、スイッチ８ｂが記憶領域５ａ側に設定される。これにより、シンボルセットの一部である大きい方のシンボルＡは、スイッチ８ｂを介して、出力シンボルＳｙｍとして後段に出力される。それとともに、このセットの残りである小さい方のシンボルＢは、元の記憶領域５ｂに格納され続ける。シンボルＡを出力することによって空いた記憶領域５ａには、前段から供給されたシンボルＳｙｍ’が格納される。一方、Ａ＜Ｂの場合には、スイッチ８ａがオン、スイッチ８ｂが記憶領域５ｂ側に設定される。これにより、大きい方のシンボルＢは、スイッチ８ｂを介して、出力シンボルＳｙｍとして後段に出力される。それとともに、小さい方のシンボルＡは、スイッチ８ａを介して、同じユニット内の記憶領域５ｂに格納される。シンボルＡの格納先は、記憶領域５ａから記憶領域５ｂに変わるものの、ユニット内で閉じたデータ移動に留まる。シンボルＡを出力することによって空いた記憶領域５ａには、前段から供給されたシンボルＳｙｍ’が格納される。
【００２７】
これに対して、制御信号ＣＴＬによってシフト処理が指示された場合（ＣＴＬ＝Ｈレベル）、判定部７は、シンボルセットＡ，Ｂの大小に関わりなく、スイッチ８ａをオン、スイッチ８ｂを記憶領域５ｂ側に強制的に設定する。これにより、記憶領域５ｂから読み出されたシンボルＢは、スイッチ８ｂを介して、出力シンボルＳｙｍとして後段に出力される。それとともに、記憶領域５ａから読み出されたシンボルＡは、スイッチ８ａを介して、同じユニット内の記憶領域５ｂに格納される。シンボルＡを出力することによって空いた記憶領域５ａには、前段から供給されたシンボルＳｙｍ’が格納される。
【００２８】
つぎに、シンボル列の境界位置について説明する。例えば、図３に示すように、１つの比較ユニットＣＵＮと、３つの記憶ユニットＳＵＮ(1)〜ＳＵＮ(3)とによって構成されたリングを考える。このリングには、５つのシンボルＡ〜Ｅよりなるシンボル列が格納されている。比較ユニットＣＵＮ内のシンボルセットＡ，Ｂについては、回路構成上、その順序関係が一義的に特定されるが、それ以外については順序関係が不明だとすると、”ＡＢＣＤＥ”，”ＣＤＥＡＢ”，”ＤＥＡＢＣ”，”ＥＡＢＣＤ”の４通りが考えられ、シンボル列を一義に特定できない。
【００２９】
一義に特定するためには、リング状に配置された複数のシンボルを列状に展開する位置的な基準を与える必要がある。換言すれば、シンボル列をリング化した場合でも、その本来の列構成を論理的に維持する必要がある。そのために、シンボル列の先端シンボルの格納場所と末端シンボルの格納場所との境界を「境界位置」として管理する。例えば、図３に示すように境界位置を、比較ユニットＣＵＮ−記憶ユニットＳＵＮ(3)間とすることで、シンボル列の先端シンボルがＡ、末端のシンボルがＥであることを示している。境界位置によってリングを管理することで、”ＡＢＣＤＥ”というシンボル列が一義的に特定される。なお、上述したようにシンボルがサイクル毎にシフトする関係上、境界位置もサイクルの推移に伴い、１サイクルで転送されるシンボルの個数分ずつ順次シフトしていく。例えば、図３において１サイクルでの転送シンボル数を１とした場合、比較ユニットＣＵＮ−記憶ユニットＳＵＮ(3)間に存在する境界位置は、次のサイクルでは比較ユニットＣＵＮ内の格納場所間にシフトし、さらにその次のサイクルでは比較ユニットＣＵＮ−記憶ユニットＳＵＮ(1)間にシフトすることになる。
【００３０】
制御部４は、サイクルの推移をカウントアップし、これに応じて境界位置を順次シフトすることによって、現在の境界位置を管理する。それとともに、制御部４は、境界位置に応じて、比較ユニットＣＵＮに供給する制御信号ＣＴＬのレベルを切り替える。具体的には、あるサイクルにおいて、自己の記憶領域から読み出されるシンボルセットが境界位置を跨がない比較ユニットＣＵＮに対しては、このサイクルでソート処理を実行させるべく、制御信号ＣＴＬがＬレベルに設定される。境界位置を跨がないということは、本来の列構成で隣り合ったシンボルであることを意味するので、これに関するソートを許可しても論理的な列構成が崩れることはない。これに対して、あるサイクルにおいて、自己の記憶領域から読み出されるシンボルセットが境界位置を跨ぐ比較ユニットＣＵＮに対しては、制御信号ＣＴＬがＨレベルに設定される（シフト処理の指示）。これにより、本来の列構成に反するようなソート（すなわち、先端・末端シンボル同士のソート）が規制され、リング内でシンボルを循環させるのに必要なシフトだけが実行される。このような観点から、シフト処理は、シンボル列の論理的な列構成を崩さないための一種の例外処理という位置づけで捉えることができる。このように、シンボル列の本来の列構成を維持することを条件としたソートを繰り返すことで、正しいソート結果が保証される。以上のような基本的な構成を踏まえた上で、以下、いくつかのバリエーションを例示しながら、それらの具体的なソート動作について詳述する。
【００３１】
（第１の実施形態）
図４は、第１の実施形態にかかるバブルソート回路１の概略構成図である。なお、同図は、本実施形態の特徴的な部分のみを概略的に示したものであり、入出力部３や制御部４については省略されている点に留意されたい（この点は後出の図６，８についても同様）。このバブルソート回路１では、２つの比較ユニットＣＵＮ(1)，ＣＵＮ(2)によってリングが構成されており、これらは各サイクルで互いに並列に動作する。同図左の比較ユニットＣＵＮ(1)は、２つの記憶領域５ａ(1)，５ｂ(1)を有し、同図右の比較ユニットＣＵＮ(2)は２つの記憶領域５ａ(2)，５ｂ(2)を有する。４つの記憶領域を有する本バブルソート回路１は、４つのシンボルで構成されるシンボル列のソートを行う。
【００３２】
一例として、シンボル列”４３２１”を昇順”１２３４”にソートする昇順ソートの動作について、図５を参照しながら説明する。まず、ソート処理の開始に先立ち、比較ユニットＣＵＮ(1)の記憶領域５ａ(1)，５ｂ(1)にシンボル”４”，”３”がそれぞれ格納され、比較ユニットＣＵＮ(2)の記憶領域５ａ(2)，５ｂ(2)にシンボル”２”，”１”がそれぞれ格納される（初期状態）。なお、シンボル数が４の場合、ソートに要するサイクル数は４回である。また、当初の境界位置は、先端シンボル”４”が格納される記憶領域５ａ(1)と、末端シンボル”１”が格納される記憶領域５ｂ(2)との間にセットされる。
【００３３】
初回のサイクル（ｎ＝１）において、境界位置は、記憶領域５ａ(1)−５ｂ(1)間、記憶領域５ａ(2)−５ｂ(2)間のいずれも跨がない。したがって、比較ユニットＣＵＮ(1)，ＣＵＮ(2)の双方に対してソート処理が指示される。比較ユニットＣＵＮ(1)では、記憶領域５ａ(1)，５ｂ(1)から読み出されたシンボルセット”４”，”３”のうち、大きい方のシンボル”４”が後段の比較ユニットＣＵＮ(2)に出力される。また、小さい方のシンボル”３”は、同じ比較ユニットＣＵＮ(1)内の記憶領域５ｂ(1)に格納される。比較ユニットＣＵＮ(2)では、記憶領域５ａ(2)，５ｂ(2)から読み出されたシンボルセット”２”，”１”のうち、大きい方のシンボル”２”が後段の比較ユニットＣＵＮ(1)に出力され、小さい方のシンボル”１”が記憶領域５ｂ(2)に格納される。比較ユニットＣＵＮ(1)内の空いた記憶領域５ａ(1)には、比較ユニットＣＵＮ(2)から供給されたシンボル”２”が格納される。比較ユニットＣＵＮ(2)内の空いた記憶領域５ａ(2)には、比較ユニットＣＵＮ(1)から供給されたシンボル”４”が格納される。このサイクルでの処理の終了に伴い、境界位置は１つ右側にシフトし、記憶領域５ａ(1)−５ｂ(1)間に位置する。
【００３４】
２回目のサイクル（ｎ＝２）において、境界位置は、記憶領域５ａ(1)−５ｂ(1)間を跨ぎ、記憶領域５ａ(2)−５ｂ(2)間を跨がない。したがって、前者に対応する比較ユニットＣＵＮ(1)には例外処理としてのシフト処理が指示される一方、後者に対応するＣＵＮ(2)にはソート処理が指示される。比較ユニットＣＵＮ(1)では、記憶領域５ａ(1)から読み出されたシンボル”２”が記憶領域５ｂ(1)に格納され、記憶領域５ｂ(1)から読み出されたシンボル”３”が後段の比較ユニットＣＵＮ(2)に出力される。また、比較ユニットＣＵＮ(2)では、記憶領域５ａ(2)，５ｂ(2)から読み出されたシンボルセット”４”，”１”のうち、大きい方のシンボル”４”が後段の比較ユニットＣＵＮ(1)に出力され、小さい方のシンボル”１”が記憶領域５ｂ(2)に格納される。比較ユニットＣＵＮ(1)の空いた記憶領域５ａ(1)には、比較ユニットＣＵＮ(2)から供給されたシンボル”４”が格納される。比較ユニットＣＵＮ(2)の空いた記憶領域５ａ(2)には、比較ユニットＣＵＮ(1)から供給されたシンボル”３”が格納される。このサイクルでの処理の終了に伴い、境界位置は記憶領域５ｂ(1)−５ａ(2)間にシフトする。
【００３５】
３回目のサイクル（ｎ＝３）において、境界位置は、記憶領域５ａ(1)−５ｂ(1)間、記憶領域５ａ(2)−５ｂ(2)間のいずれも跨がない。したがって、比較ユニットＣＵＮ(1)，ＣＵＮ(2)の双方に対してソート処理が指示される。比較ユニットＣＵＮ(1)では、記憶領域５ａ(1)，５ｂ(1)から読み出されたシンボルセット”４”，”２”のうち、大きい方のシンボル”４”が後段の比較ユニットＣＵＮ(2)に出力され、小さい方のシンボル”２”が記憶領域５ｂ(1)に格納される。比較ユニットＣＵＮ(2)では、記憶領域５ａ(2)，５ｂ(2)から読み出されたシンボルセット”３”，”１”のうち、大きい方のシンボル”３”が後段の比較ユニットＣＵＮ(1)に出力され、小さい方のシンボル”１”が記憶領域５ｂ(2)に格納される。比較ユニットＣＵＮ(1)の空いた記憶領域５ａ(1)には、比較ユニットＣＵＮ(2)から供給されたシンボル”３”が格納され、比較ユニットＣＵＮ(2)の空いた記憶領域５ａ(2)には、比較ユニットＣＵＮ(1)から供給されたシンボル”４”が格納される。このサイクルでの処理の終了に伴い、境界位置は記憶領域５ａ(2)−５ｂ(2)間にシフトする。
【００３６】
４回目のサイクル（ｎ＝４）において、境界位置は、記憶領域５ａ(1)−５ｂ(1)間を跨がず、記憶領域５ａ(2)−５ｂ(2)間を跨ぐ。したがって、前者に対応する比較ユニットＣＵＮ(1)にはソート処理が指示される一方、後者に対応するＣＵＮ(2)には例外処理としてのシフト処理が指示される。比較ユニットＣＵＮ(1)では、記憶領域５ａ(1)，５ｂ(1)から読み出されたシンボルセット”３”，”２”のうち、大きい方のシンボル”３”が後段の比較ユニットＣＵＮ(2)に出力され、小さい方のシンボル”２”が記憶領域５ｂ(1)に格納される。また、比較ユニットＣＵＮ(2)では、記憶領域５ａ(2)から読み出されたシンボル”４”が記憶領域５ｂ(2)に格納され、記憶領域５ｂ(2)から読み出されたシンボル”１”が後段の比較ユニットＣＵＮ(1)に出力される。このサイクルでの処理の終了に伴い、境界位置は記憶領域５ｂ(2)−５ａ(1)間にシフトする。
【００３７】
以上のような４回のサイクルを経て、シンボル列”４３２１”は昇順”１２３４”に並び替えられる。カウントアップされたサイクル数ｎが４に到達した場合、４回目のサイクルの処理の終了を以て、制御部４から入出力部３にシンボル列の出力が指示される。この指示を受けた入出力部３は、境界位置（記憶領域５ｂ(2)−５ａ(1)間）によって特定される順序、すなわち、記憶領域５ａ(1)，５ｂ(1)，５ａ(2)，５ｂ(2)の順序でシンボルを読み出して、これらをまとめたシンボル列”１２３４”を外部に出力する。
【００３８】
このように、本実施形態によれば、制御部４の制御下において、それぞれの比較ユニットＣＵＮ(1)〜ＣＵＮ(2)が後段に対してシンボルを並行出力するので、これらによって構成されるリング全体で見た場合、リング内でシンボル列が循環する。そして、リング内におけるシンボルの循環に伴い、シンボル列の並び替えが徐々に進行していく。また、制御部４は、シンボル列の境界位置を管理しているので、シンボル列において本来的に隣り合わない先端・末端に位置するシンボル同士（リングにおいては隣り合って見える）についてはソートが規制され、例外処理としてのシフトのみが行われる。これにより、シンボル列をリング状に配置しても本来の列構成が論理的に維持され、かつ、この列構成を考慮したソートが行われるので、正しいソート結果が得られるのを保証できる。
【００３９】
また、本実施形態によれば、複数の比較ユニットＣＵＮ(1)〜ＣＵＮ(2)を用いることにより、それぞれが担うソート処理が同時並行的に行われるので、全体的な処理の高速化を図ることが可能になる。
【００４０】
なお、上述した本実施形態では、一例として昇順ソートを挙げて説明したが、本発明はこれに限定されるものではなく、降順ソートについても同様に適用可能であるのは当然である。その場合、比較ユニットＣＵＮ(1)〜ＣＵＮ(2)のそれぞれが備える判定部７の判定条件を反転させればよい（この点は以下の実施形態においても同様）。
【００４１】
（第２の実施形態）
上述した実施形態が比較ユニットＣＵＮのみで構成された全比較型リングに関するのに対して、第２の実施形態は、比較ユニットＣＵＮおよび記憶ユニットＳＵＮが混在した混在型リングに関する。
【００４２】
図６は、第２の実施形態にかかるバブルソート回路１の概略構成図である。このバブルソート回路１では、１つの比較ユニットＣＵＮと、２つの記憶ユニットＳＵＮ(1)，ＳＵＮ(2)とによってリングが構成されており、これらは各サイクルで互いに並列に動作する。比較ユニットＣＵＮ(1)は、２つの記憶領域５ａ，５ｂを有し、記憶ユニットＳＵＮ(1)，ＣＵＮ(2)は、それぞれ記憶領域９(1)，９(2)を有する。４つの記憶領域を有する本バブルソート回路１は、４つのシンボルで構成されるシンボル列のソートを行う。
【００４３】
一例として、シンボル列”４３２１”を昇順”１２３４”にソートする昇順ソートの動作について、図７を参照しながら説明する。まず、ソート処理の開始に先立ち、比較ユニットＣＵＮの記憶領域５ａ，５ｂにシンボル”４”，”３”がそれぞれ格納され、記憶ユニットＳＵＮ(1)の記憶領域９(1)にシンボル”２”が、記憶ユニットＳＵＮ(2)の記憶領域９(2)にシンボル”１”がそれぞれ格納される（初期状態）。なお、本ケースにおいて、ソートに要するサイクル数は８回である。また、当初の境界位置は、先頭シンボル”４”が格納される記憶領域５ａと、末端シンボル”１”が格納される記憶領域９(2)との間にセットされる。
【００４４】
初回のサイクル（ｎ＝１）において、境界位置は、記憶領域５ａ−５ｂ間を跨がない。したがって、比較ユニットＣＵＮに対してソート処理が指示される。比較ユニットＣＵＮでは、記憶領域５ａ，５ｂから読み出されたシンボルセット”４”，”３”のうち、大きい方のシンボル”４”が後段の記憶ユニットＳＵＮ(1)に出力される。また、小さい方のシンボル”３”は、記憶領域５ｂに格納される。記憶ユニットＳＵＮ(1)では、記憶領域９(1)から読み出されたシンボル”２”が後段の記憶ユニットＳＵＮ(2)に出力され、前段の比較ユニットＣＵＮから供給されたシンボル”４”が記憶領域９(1)に格納される。記憶ユニットＳＵＮ(2)では、記憶領域９(2)から読み出されたシンボル”１”が後段の比較ユニットＣＵＮに出力され、前段の記憶ユニットＳＵＮ(1)から供給されたシンボル”２”が記憶領域９(2)に格納される。比較ユニットＣＵＮ内の空いた記憶領域５ａには、記憶ユニットＳＵＮ(2)から供給されたシンボル”１”が格納される。このサイクルでの処理の終了に伴い、境界位置は１つ右側にシフトし、記憶領域５ａ−５ｂ間に位置する。
【００４５】
２回目のサイクル（ｎ＝２）において、境界位置は、記憶領域５ａ−５ｂ間を跨ぐ。したがって、比較ユニットＣＵＮには例外処理としてのシフト処理が指示される。比較ユニットＣＵＮでは、記憶領域５ａから読み出されたシンボル”１”が記憶領域５ｂに格納され、記憶領域５ｂから読み出されたシンボル”３”が後段の記憶ユニットＳＵＮ(1)に出力される。それ以外は初回のサイクルと同様の動作でシンボルが右方向にシフトして、記憶ユニットＳＵＮ(1)の記憶領域９(1)にはシンボル”４”、記憶ユニットＳＵＮ(2)の記憶領域９(2)にはシンボル”２”、比較ユニットＣＵＮの記憶領域５ａにはシンボル”２”がそれぞれ格納される。
【００４６】
それ以降、８回目のサイクル（ｎ＝８）が終了するまで、同様のソートが繰り返される。なお、５回目のサイクル（ｎ＝５）では、境界位置が記憶領域５ａ−５ｂ間を再度跨ぐので、比較ユニットＣＵＮではシフト処理が実行される点に留意されたい。８回目のサイクルの処理が終了した時点における境界位置は、記憶領域５ａ−９(2)間である。したがって、この境界位置によって特定される順序、すなわち、記憶領域５ａ，５ｂ，９(1)，９(2)の順序でシンボルが読み出され、これらをまとめたシンボル列”１２３４”が外部に出力される。
【００４７】
このように、本実施形態によれば、第１の実施形態と同様に、列構成を考慮したソートを行うことで、正しいソート結果が得られるのを保証できる。なお、本実施形態のような混在型リングで用いるべき比較ユニットＣＵＮの個数は、処理速度や回路規模といった実装上要求されるスペックに応じて適宜設定すればよい。
【００４８】
（第３の実施形態）
上述した各実施形態が２比較１転送型（比較対象が２シンボルで転送数が１シンボル）のリングに関するのに対して、第３の実施形態は、３比較２転送型の全比較リングに関する。
【００４９】
図８は、第３の実施形態にかかるバブルソート回路１の概略構成図である。このバブルソート回路１では、２つの比較ユニットＣＵＮ(1)，ＣＵＮ(2)によってリングが構成されており、これらは各サイクルで互いに並列に動作する。比較ユニットＣＵＮ(1)は、３つの記憶領域５ａ(1)，５ｂ(1)，５ｃ(1)を有し、比較ユニットＣＵＮ(2)は、記憶領域５ａ(2)，５ｂ(2)，５ｃ(2)を有する。６つの記憶領域を有する本バブルソート回路１は、６つのシンボルで構成されるシンボル列のソートを行う。
【００５０】
一例として、シンボル列”６５４３２１”を昇順”１２３４５６”にソートする昇順ソートの動作について、図１０を参照しながら説明する。まず、ソート処理の開始に先立ち、比較ユニットＣＵＮ(1)の記憶領域５ａ(1)，５ｂ(1)，５ｃ(1)にシンボル”６”，”５”，”４”がそれぞれ格納され、比較ユニットＣＵＮ(2)の記憶領域５ａ(2)，５ｂ(2)，５ｃ(2)にシンボル”３”，”２”，”１”がそれぞれ格納される（初期状態）。なお、本ケースにおいて、ソートに要するサイクル数は５回である。また、当初の境界位置は、先頭シンボル”６”が格納される記憶領域５ａ(1)と、末端シンボル”１”が格納される記憶領域５ｃ(2)との間にセットされる。なお、１サイクルでの転送数が２シンボルなので、境界位置もサイクル毎に２シンボル分シフトする点に留意されたい。
【００５１】
初回のサイクル（ｎ＝１）において、境界位置は、記憶領域５ａ(1)〜５ｃ(1)間、記憶領域５ａ(2)〜５ｃ(2)間のいずれも跨がない。したがって、比較ユニットＣＵＮ(1)，ＣＵＮ(2)の双方に対してソート処理が指示される。比較ユニットＣＵＮ(1)では、記憶領域５ａ(1)〜５ｃ(1)から読み出されたシンボルセット”６”，”５”，”４”のうち、大きい方の２シンボル”６”，”５”が後段の比較ユニットＣＵＮ(2)に出力される。また、残った小さい方のシンボル”４”は、記憶領域５ｃ(1)に格納される。なお、ソート処理の結果、後段に出力されなかったシンボルは、そのユニットＣＵＮ(1)（またはＣＵＮ(2)）における最右の記憶領域５ｃ(1)（または５ｃ(2)）に格納する規則になっている。比較ユニットＣＵＮ(2)では、記憶領域５ａ(2)〜５ｃ(2)から読み出されたシンボルセット”３”，”２”，”１”のうち、大きい方の２シンボル”３”，”２”が後段の比較ユニットＣＵＮ(1)に出力される。また、残った小さい方のシンボル”１”は、記憶領域５ｃ(2)に格納される。比較ユニットＣＵＮ(1)内の空いた記憶領域５ａ(1)，５ｂ(1)には、比較ユニットＣＵＮ(2)から供給されたシンボル”３”，”２”が格納される。比較ユニットＣＵＮ(2)内の空いた記憶領域５ａ(2)，５ｂ(2)には、比較ユニットＣＵＮ(1)から供給されたシンボル”６”，”５”が格納される。なお、前段から供給された２シンボルの格納先は規則化されており、小さい方が最左の記憶領域５ａ(1)（または５ａ(2)）であり、大きい方が真ん中の記憶領域５ｂ(1)（または５ｂ(2)）であるものとする。このサイクルでの処理の終了に伴い、境界位置は２つ右側にシフトし、記憶領域５ｂ(1)−５ｃ(1)間に位置する。
【００５２】
なお、境界位置が比較対象を一切跨がない３回目のサイクル（ｎ＝３）でも、初回のサイクル（ｎ＝１）と同様の処理が行われる。
【００５３】
２回目のサイクル（ｎ＝２）において、境界位置は、記憶領域５ｂ(1)−５ｃ(1)間（記憶領域５ａ(1)−５ｃ(1)の一部）を跨ぎ、記憶領域５ａ(2)−５ｃ(2)間を跨がない。したがって、前者に対応する比較ユニットＣＵＮ(1)には、境界位置を跨ぐ部分５ｂ(1)−５ｃ(1)に関して並び替えを行うことなく、例外処理としてのシフト処理が指示される一方、後者に対応するＣＵＮ(2)にはソート処理が指示される。この場合、境界位置を跨ぐシンボルセットの処理は、境界位置のシフトの前後で、シンボル列の論理的な列構成が維持されるように、以下の規則に則って行われる。
【００５４】
［処理規則］
（１）現在の境界位置によって分離される記憶領域間では並び替え禁止
例えば、２回目のサイクルの場合、シンボルセット”２”，”３”，”４”が境界位置によってシンボル”２”，”３”と、シンボル”４”とに分離されているので、シンボル”２”（または”３”）と、シンボル”４”との並び替えを行わない。３回目のサイクルの場合、シンボル”３”と、シンボル”４”（または”１”）との並び替えを行わない。５回目のサイクルの場合、シンボル”５”（または”６”）と、シンボル”１”との並び替えを行わない。
【００５５】
（２）現在の境界位置によって分離されていない記憶領域間では並び替え許可
例えば、２回目のサイクルの場合、境界位置によって分離されていないシンボル”２”，”３”については並び替えを行う。同様に、３回目のサイクルの場合にはシンボル”４”，”１”、５回目のサイクルの場合にはシンボル”５”，”６”の並び替えについてはそれぞれ行う。
【００５６】
（３）現在の境界位置によって分離された１つのシンボルの格納先は、シフト後の境界位置との位置的関係を維持するように決定
例えば、２回目のサイクルの場合、現在の境界位置（５ｂ(1)−５ｃ(1)間）の右側に位置するシンボル”４”の格納先は、シフト後の境界位置（５ａ(2)−５ｂ(2)間）の右側、すなわち記憶領域５ｂ(2)となる（ユニット間移動）。３回目のサイクルの場合、現在の境界位置（５ａ(2)−５ｂ(2)間）の左側に位置するシンボル”３”の格納先は、シフト後の境界位置（５ａａ(1)−５ｃ(2)間）の左側、すなわち記憶領域５ｃ(2)となる（ユニット内移動）。同様に、５回目のサイクルの場合、現在の境界位置（５ｂ(1)−５ｃ(1)間）の右側に位置するシンボル”１”の格納先は、シフト後の境界位置（５ａ(2)−５ｂ(2)間）の右側、すなわち、記憶領域５ｂ(2)となる（ユニット間移動）。
【００５７】
（４）現在の境界位置によって分離された残りのシンボル（（３）を除く２つのシンボル）の格納先は、転送個数を考慮した上で、シフト後の境界位置との位置的関係を維持するように決定
例えば、２回目のサイクルの場合、上記（３）によって転送すべきシンボルの１つは”４”に決まっているので、もう１つは、現在の境界位置（５ｂ(1)−５ｃ(1)間）の左側に位置するシンボル”２”，”３”の大きい方、すなわち”３”となる。そして、その格納先は、シフト後の境界位置（５ａ(2)−５ｂ(2)間）の左側、すなわち記憶領域５ａ(2)となる。残った小さい方のシンボル”２”は、記憶領域５ｃ(1)に格納される。３回目のサイクルの場合、上記（３）によって転送すべきシンボルが存在しないので、現在の境界位置（５ａ(2)−５ｂ(2)間）の右側に位置するシンボル”４”，”１”がソートされた上で、シフト後の境界位置（５ａ(1)−５ｃ(2)間）の右側、すなわち記憶領域５ａ(1)，５ｂ(1)に格納される。５回目のサイクルの場合、上記（３）によって転送すべきシンボルの１つは”１”に決まっているので、もう１つは、現在の境界位置（５ｂ(1)−５ｃ(1)間）の左側に位置するシンボル”５”，”６”の大きい方、すなわち”６”となる。そして、その格納先は、シフト後の境界位置（５ａ(2)−５ｂ(2)間）の左側、すなわち記憶領域５ａ(2)となる。残った小さい方のシンボル”５”は、記憶領域５ｃ(1)に格納される。
【００５８】
以上のような処理規則にしたがって処理を行うことで、２回目のサイクルの終了時点におけるシンボル列の格納状態は、境界位置を起点として”４５６１２３”となる。それ以降、５回目のサイクル（ｎ＝５）が終了するまで、同様のソートが繰り返される。５回目のサイクルの処理が終了した時点における境界位置は、記憶領域５ａ(2)−５ｂ(2)間である。したがって、この境界位置によって特定される順序、すなわち、記憶領域５ｂ(2)，５ｃ(2)，５ａ(1)，５ｂ(1)，５ｃ(1)，５ａ(2)の順序でシンボルが読み出され、これらをまとめたシンボル列”１２３４５６”が外部に出力される。
【００５９】
このように、本実施形態によれば、上述した各実施形態と同様に、列構成を考慮したソートを行うことで、正しいソート結果が得られるのを保証できる。また、比較対象となるシンボルセットのシンボル数（例えば３つ）を増やし、かつ、１サイクルでのシンボルの転送数（例えば２つ）を増やすことにより、全体的な処理速度の向上を図ることができる。
【００６０】
（第４の実施形態）
上述した各実施形態は、サイクルの推移に応じタイミング境界位置を順次シフトすることによって、制御部４が境界位置を直接的に管理するものであった。第４および第５の実施形態では、境界位置の管理に関する別の手法を提示する。本実施形態は、シンボル列に境界シンボルという特別なシンボルを付加する手法に関する。本実施形態における概略的な回路構成は、図４と同様である（この点は後述する第５の実施形態についても同様）。
【００６１】
一例として、シンボル列”３２１”を昇順”１２３”にソートする昇順ソートの動作について、図１０を参照しながら説明する。まず、ソート処理の開始に先立ち、制御部４は、入出力部３に外部から入力されたシンボル列”３２１”を記憶領域５ａ(1)−５ｂ(2)に格納する際、このシンボル列”３２１”の境界位置を示す境界シンボル”＊”を付加する。そして、付加後のシンボル列”３２１＊”が記憶領域５ａ(1)−５ｂ(2)に格納される（初期状態）。なお、本ケースにおいて、ソートに要するサイクル数は３回である。
【００６２】
比較ユニットＣＵＮ(1)，ＣＵＮ(2)は、比較対象となるシンボルセットが境界シンボル”＊”を含むか否かに応じて、ソート処理またはシフト処理を選択的に実行する。すなわち、境界シンボル”＊”を含まない場合には、比較対象となるシンボルセットが境界位置を跨がないと判断され、通常のソート処理が実行される。これに対して、境界シンボル”＊”を含む場合には、比較対象となるシンボルセットが境界位置を跨ぐと判断され、この境界位置を跨ぐ部分については、例外処理としてのシフト処理が実行される。これにより、サイクルの推移に伴い、境界シンボル”＊”を起点としたシンボル列は、”３２１＊”（ｎ＝１）、”２３１＊”（ｎ＝２）、”２１３＊”（ｎ＝３）と変化し、４回目のサイクル（ｎ＝４）の終了を以て、昇順”１２３＊”に並び替えられる。制御部４からの出力指示を受けた入出力部３は、境界シンボル”＊”を削除した上で、境界シンボル”＊”によって特定される順序、すなわち、記憶領域５ｂ(2)，５ａ(1)，５ｂ(1)の順序でシンボルを読み出して、これらをまとめたシンボル列”１２３”を外部に出力する。
【００６３】
このように、本実施形態によれば、境界位置を直接管理するのに代えて、境界シンボル”＊”という特殊なシンボルを用いることにより、列構成を考慮したソートが可能となり、正しいソート結果が得られるのを保証できる。
【００６４】
なお、境界シンボルは、本実施形態のように特殊なシンボル”＊”を明示的に付加してもよいが、シンボル列の一部（例えば最大値または最小値）を境界シンボルとしてみなすこと、すなわち、暗示的に付加することによっても実現できる。
【００６５】
（第５の実施形態）
図１１は、上述したバブルソート回路１を実装したデータ圧縮システム１０の構成図である。このデータ圧縮システム１０は、上述した第１から第４の実施形態として詳述したバブルソート回路１と、ハフマン符号化回路１１とで構成されている。バブルソート回路１は、ソート処理前の入力シンボル列Ｄinを所定の順序に並び替えた上で、これを出力シンボル列Ｄoutとして出力する。ハフマン符号化回路１１は、周知の構成を有し、ソート処理後の出力シンボル列Ｄoutに基づいてハフマン符号化を行い、圧縮データを出力する。ハフマン符号化処理は、シンボルの出現頻度の規則性に着目してデータ圧縮を行う代表的なアルゴリズムであり、各出現頻度に対応する符号長（または符号）を個々のデータに割り当てる。このハフマン符号化処理においては、パッケージ結合(ノード結合)の各ステップにおいて、最小の出現頻度を抽出する過程が必要となる。つまり、バブルソート回路１は、圧縮対象のデータ列における各シンボルの出現頻度（出現頻度表）を、ソート対象のシンボル列Ｄinとし、ハフマン符号化処理を行う前に、バブルソート回路１による出現頻度表のソート処理を用いることで、整列された出現頻度表が得られ、シームレスなハフマン符号化処理を行うことができる。
【００６６】
本実施形態によれば、ハフマン符号化に先立ち必要となるシンボル列のソート処理が高速化されるので、全体的なデータ圧縮処理の高速化を図ることができる。
【図面の簡単な説明】
【００６７】
【図１】バブルソート回路の全体構成図
【図２】単一の比較ユニットの構成図
【図３】シンボル列の境界位置の説明図
【図４】第１の実施形態にかかるバブルソート回路の概略構成図
【図５】第１の実施形態にかかる昇順ソートの説明図
【図６】第２の実施形態にかかるバブルソート回路の概略構成図
【図７】第２の実施形態にかかる昇順ソートの説明図
【図８】第３の実施形態にかかるバブルソート回路の概略構成図
【図９】第３の実施形態にかかる昇順ソートの説明図
【図１０】第４の実施形態にかかる昇順ソートの説明図
【図１１】第５の実施形態にかかるデータ圧縮システムの構成図
【符号の説明】
【００６８】
ＵＮ  ユニット
ＣＵＮ  比較ユニット
ＳＵＮ  記憶ユニット
１  バブルソート回路
２  演算部
３  入出力部
４  制御部
５ａ，５ｂ，９  記憶領域
６  比較器
７  判定部
８ａ，８ｂ  スイッチ
１０  データ圧縮システム
１１  ハフマン符号化回路
【図１】
2007226744.tif 000003
【図２】
2007226744.tif 000004
【図３】
2007226744.tif 000005
【図４】
2007226744.tif 000006
【図５】
2007226744.tif 000007
【図６】
2007226744.tif 000008
【図７】
2007226744.tif 000009
【図８】
2007226744.tif 000010
【図９】
2007226744.tif 000011
【図１０】
2007226744.tif 000012
【図１１】
2007226744.tif 000013