(57)【要約】【課題】ソート処理の一層の高速化を図る。【解決手段】入出力部４は、ソート処理の開始に先立ち、外部から入力されたシンボル列を記憶部１に格納するとともに、ソート処理の完了後に、記憶部１から読み出されたシンボル列を外部に出力する。記憶部１の出力側には、複数の比較器２ａ〜２ｄが互いに並列に設けられている。スイッチ３ａ〜３ｃは、あるサイクルで一の比較器２ａから出力された大きい方のシンボルと、そのサイクルで他の比較器２ｃから出力された小さい方のシンボルとが、次のサイクルにおける比較器２ｂの入力となるように、記憶部１におけるシンボル列の格納場所をサイクル毎に切り替える。【選択図】図１
2007213423.tif 000002
【特許請求の範囲】
【請求項１】
値の大小を比較可能な複数のシンボルで構成されたシンボル列に対するソート処理を繰り返し実行することによって、シンボル列を所定のソート順序に並び替えるバブルソート回路において、
シンボル列が格納される記憶部と、
ソート処理の開始に先立ち、外部から入力されたシンボル列を前記記憶部に格納するとともに、一連のソート処理の完了後に、前記記憶部から読み出されたシンボル列を外部に出力する入出力部と、
前記記憶部の出力側に互いに並列に設けられているとともに、それぞれが、前記記憶部から読み出されたシンボルのセットを値の大小に応じて並び替えるソート処理をサイクル毎に並列に実行する複数の比較器と、
第１のサイクルで一の比較器から出力された大きい方のシンボルと、前記第１のサイクルで他の比較器から出力された小さい方のシンボルとが、前記第１のサイクルに続く第２のサイクルにおける比較器の入力となるように、前記記憶部におけるシンボル列の格納場所をサイクル毎に切り替える選択部と
を有することを特徴とするバブルソート回路。
【請求項２】
前記入出力部は、前記シンボル列を構成するシンボルの個数がｋ（ｋ≧３）の場合、ｋ番目のサイクルのソート処理の完了後に、前記記憶部から読み出されたシンボル列を外部に出力することを特徴とする請求項１に記載されたバブルソート回路。
【請求項３】
前記複数の比較器は、前記ソート順序において一方向に隣接したシンボルのセットを比較する第１のグループと、前記一方向とは反対の方向に隣接したシンボルのセットを比較する第２のグループとにグループ化されており、
前記選択部は、前記複数の比較器の出力側で、かつ、前記記憶部の入力側に設けられた第１の選択部を含み、
前記第１の選択部は、
前記第１のサイクルでは、前記第１のグループを選択して、当該第１のグループに属する前記比較器からの出力を前記記憶部の元の格納場所に再格納し、
前記第２のサイクルでは、前記第２のグループを選択して、当該第２のグループに属する前記比較器からの出力を前記記憶部の元の格納場所に再格納することを特徴とする請求項１または２に記載されたバブルソート回路。
【請求項４】
前記選択部は、
前記記憶部の出力側で、かつ、前記複数の比較器の入力側に設けられた第１の選択部と、
前記複数の比較器の出力側で、かつ、前記記憶部の入力側に設けられた第２の選択部とを含み、
前記第１のサイクルにおいて、前記第１の選択部は、前記ソート順序において一方向に隣接したシンボルのセットを前記比較器に出力し、前記第２の選択部は、当該比較器からの出力を前記記憶部の元の格納場所に再格納し、
前記第２のサイクルにおいて、前記第１の選択部は、前記一方向とは反対の方向に隣接したシンボルのセットを前記比較器に出力し、前記第２の選択部は、当該比較器からの出力を前記記憶部の元の格納場所に再格納することを特徴とする請求項１または２に記載されたバブルソート回路。
【請求項５】
請求項１から４のいずれかに記載されたバブルソート回路と、
前記バブルソート回路によって前記ソート順序に並び替えられた前記シンボル列に基づいてハフマン符号化を行うハフマン符号化回路と
を有することを特徴とするデータ圧縮システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、値の大小を比較可能な複数のシンボルで構成されたシンボル列に対するソート処理を繰り返し実行することによって、シンボル列を降順または昇順に並び替えるソート処理に関する。
【背景技術】
【０００２】
ソート処理の一つとして、バブルソート（基本交換法または単純交換法）と呼ばれる方法が知られている。従来のバブルソートは、その回路構成が比較的小規模で済む反面、一回のサイクルで実行される処理は、隣り合う一対のシンボルを入力とした１回の比較に留まる。そのため、シンボル列中の構成要素が多くなるほど比較処理の回数が多くなり、ソート完了までに長時間を要する。このような課題に対して、特許文献１には、ソート処理を一部並列に実行するバブルソート回路が開示されている。このバブルソート回路は、シリアルな入出力に対して多段に直列接続された複数の比較回路で構成されており、単一の比較回路は、１つの比較器と、その比較対象となる２つのシンボルを格納するための一対の記憶領域とを有する。
【０００３】
特許文献１のバブルソート回路の動作は、概ね以下のようになる。まず、直列に接続された比較回路のうち、最前段の比較回路における一方の記憶領域に、ソート対象となるシンボル列を構成する１つのシンボルが入力される。この入力シンボルは、他方の記憶領域に格納されたシンボルと比較される。この比較の結果、大きい方のシンボルは自己の記憶領域に格納され、小さい方のシンボルは後段（２段目）の比較回路に転送され、その一方の記憶領域に格納される（ソート処理）。そして、２段目以降の比較回路においても、一対の記憶領域における格納値の比較およびその並べ替えが実行される。なお、それぞれの記憶領域は、初期時に未設定状態（最小値）として設定されている。このソート処理は、シンボル列を構成する個々のシンボルがシリアルに入力する毎に各比較回路において同時並行的に実行される。そして、全てのシンボルの入力が完了した場合、ソート対象となるシンボル列を構成する個々のシンボルが最前段の比較回路に順次転送され、これを介してシリアルに出力される。その際、シンボルの出力に応じて、出力されなかった一方の記憶領域に格納されたシンボルと、後段の比較回路から出力されたシンボルとを比較が行われ、これらを並び替えた上で記憶領域に格納される。
【０００４】
【特許文献１】特開平１０−１４９２７６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
特許文献１のバブルソート回路は、それぞれの比較回路でのソート処理を同時に行うものであるが、シンボルのシリアルな入出力と連動して各段のソート処理が行われる。そのため、特にシンボル入力の初期およびシンボル出力の後期では、全ての比較回路が動作せずに部分的な並列動作に留まり、並列処理のメリットを十分に活かすことができず、これが全体的な処理の高速化を図る上でのボトルネックとなる。
【０００６】
本発明は、かかる事情に鑑みてなされたものであり、その目的は、従来の構成とは全く異なる新規なバブルソート回路を提供することである。
【０００７】
また、本発明の別の目的は、ソート処理の一層の高速化を図ることである。
【課題を解決するための手段】
【０００８】
かかる課題を解決するために、第１の発明は、値の大小を比較可能な複数のシンボルで構成されたシンボル列に対するソート処理を繰り返し実行することによって、シンボル列を所定のソート順序に並び替えるバブルソート回路を提供する。このバブルソート回路は、記憶部と、入出力部と、複数の比較器と、選択部とを有する。記憶部には、シンボル列が格納される。入出力部は、ソート処理の開始に先立ち、外部から入力されたシンボル列を記憶部に格納するとともに、一連のソート処理の完了後に、記憶部から読み出されたシンボル列を外部に出力する。複数の比較器は、記憶部の出力側に互いに並列に設けられている。それぞれの比較器は、記憶部から読み出されたシンボルのセットを値の大小に応じて並び替えるソート処理をサイクル毎に並列に実行する。選択部は、第１のサイクルで一の比較器から出力された大きい方のシンボルと、第１のサイクルで他の比較器から出力された小さい方のシンボルとが、第１のサイクルに続く第２のサイクルにおける比較器の入力となるように、記憶部におけるシンボル列の格納場所をサイクル毎に切り替える。
【０００９】
ここで、第１の発明において、入出力部は、シンボル列を構成するシンボルの個数がｋ（ｋ≧３）の場合、にはｋ番目のサイクルのソート処理の完了後に、記憶部から読み出されたシンボル列を外部に出力することが好ましい。
【００１０】
また、第１の発明において、複数の比較器は、ソート順序において一方向に隣接したシンボルのセットを比較する第１のグループと、一方向とは反対の方向に隣接したシンボルのセットを比較する第２のグループとにグループ化されていてもよい。この場合、選択部は、複数の比較器の出力側で、かつ、記憶部の入力側に設けられた第１の選択部を含むことが好ましい。この第１の選択部は、第１のサイクルでは、第１のグループを選択して、この第１のグループに属する比較器からの出力を記憶部の元の格納場所に再格納する。また、第１の選択部は、第２のサイクルでは、第２のグループを選択して、この第２のグループに属する比較器からの出力を記憶部の元の格納場所に再格納する。
【００１１】
また、第１の発明において、選択部は、記憶部の出力側で、かつ、複数の比較器の入力側に設けられた第１の選択部と、複数の比較器の出力側で、かつ、記憶部の入力側に設けられた第２の選択部とを含んでいてもよい。この場合、第１のサイクルにおいて、第１の選択部は、ソート順序において一方向に隣接したシンボルのセットを比較器に出力し、第２の選択部は、この比較器からの出力を記憶部の元の格納場所に再格納する。また、第２のサイクルにおいて、第１の選択部は、一方向とは反対の方向に隣接したシンボルのセットを比較器に出力し、第２の選択部は、この比較器からの出力を記憶部の元の格納場所に再格納する。
【００１２】
第２の発明は、上述したような構成を有する第１の発明にかかるバブルソート回路と、このバブルソート回路によってソート順序に並び替えられたシンボル列に基づいてハフマン符号化を行うハフマン符号化回路とを有するデータ圧縮システムを提供する。
【発明の効果】
【００１３】
第１の発明において、複数の比較器は、記憶部の出力側に互いに並列に設けられている。また、選択部は、先のサイクルでの比較結果が次のサイクルでの比較対象に反映されるように、記憶部におけるシンボル列の格納場所をサイクル毎に切り替える。これにより、互いに並列に設けられた各比較器におけるソート処理が並列化されるので、ソート処理の一層の高速化を図ることができる。
【００１４】
また、第２の発明によれば、ハフマン符号化に先立ち必要となるシンボル列のソート処理が高速化されるので、データ圧縮処理の全体的な処理速度の高速化を図ることができる。
【発明を実施するための最良の形態】
【００１５】
（第１の実施形態）
図１は、本実施形態にかかるバブルソート回路の構成図である。このバブルソート回路は、値の大小を比較可能な複数のシンボルで構成されたシンボル列に対するソート処理を繰り返し実行することによって、前記シンボル列を所定のソート順序（例えば、降順または昇順）に並び替える。バブルソート回路は、記憶部１と、比較部２と、選択部３と、入出力部４と、制御部５とで構成されている。
【００１６】
記憶部１は、ソート処理の対象となるシンボル列を格納可能で、複数の記憶領域（格納場所）１ａ〜１ｄを有する。記憶領域１ａ〜１ｄは、互いに並列に設けられ、それぞれがシンボル列を構成する個々の要素（１つのシンボル、本実施形態では値そのもの）を格納する。これらの記憶領域１ａ〜１ｄには、シンボル列のソート処理完了時における入出力部４からの出力順序に対応して、ソート結果の格納順序（ソート順序）が予め割り当てられている。例えば、昇順の場合、記憶領域１ａには、ソート処理の完了時にシンボル列の中で最も小さいシンボルが格納され、以下、記憶領域１ｂには２番目に小さいシンボル、記憶領域１ｃには３番目に小さいシンボル、記憶領域１ｄには４番目に小さいシンボルがそれぞれ格納されるといった如くである。なお、この記憶部１は、１つのシンボルを格納可能な容量を有する物理的な記憶回路（例えばバッファ）を複数並列に並べてもよいが、ＲＡＭ（Random Access Memory）の一部をソート処理用のワーク領域として割り当てることによって構成してもよい。
【００１７】
記憶部１の出力側には、互いに並列に設けられた複数の比較器２ａ〜２ｄで構成された比較部２が接続されている。それぞれの比較器２ａ〜２ｄは、一例として、二入力二出力の回路構成を有し、ソート処理、すなわち、記憶部１より読み出されたシンボルのセット（本実施形態では一対のシンボル）を比較して、これらを値の大小関係に応じた並び替える処理をサイクル毎に並列に実行する。これらの比較器２ａ〜２ｄに比較対象を供給する供給元（格納場所）は、予め割り当てられており、かつ、それぞれに対して割り当てられる記憶領域１ａ〜１ｄが異なっている。具体的には、比較器２ａには記憶領域１ａ，１ｂ、比較器２ｂには記憶領域１ｂ，１ｃ、比較器２ｃには記憶領域１ｃ，１ｄがそれぞれ割り当てられているといった如くである。なお、比較器２ｄの供給元は、一方が記憶領域１ｄ、他方がこの記憶領域１ｄと隣接した記憶領域（図示せず）である。
【００１８】
比較部２の出力側で、かつ、記憶部１の入力側には、互いに並列に設けられた複数のスイッチ３ａ〜３ｃで構成された選択部３が接続されている。それぞれのスイッチ３ａ〜３ｃは、二入力一出力の回路構成を有し、比較部２より出力されたシンボルを選択的に出力する。スイッチ３ａ〜３ｃから出力されたシンボルは、記憶部１の予め割り当てられた格納場所に格納される。具体的には、スイッチ３ａは、奇数番目のサイクルでは比較器２ａから出力された大きい方のシンボル（下方の出力）、偶数番目のサイクルでは比較器２ｂから出力された小さい方のシンボル（上方の出力）をそれぞれ選択し、選択したシンボルを記憶領域１ｂに格納する。スイッチ３ｂは、偶数番目のサイクルでは比較器２ｂから出力された大きい方のシンボル、奇数番目のサイクルでは比較器２ｃから出力された小さい方のシンボルをそれぞれ選択し、これを記憶領域１ｃに格納する。スイッチ３ｃは、奇数番目のサイクルでは比較器２ｃから出力された大きい方のシンボル、偶数番目のサイクルでは比較器２ｃに下方に隣接した比較器（図示せず）から出力された小さい方のシンボルをそれぞれ選択し、これを記憶領域１ｄに格納する。なお、最上および最下の比較器の出力については、一部、例外的な接続関係になっている。すなわち、最上の比較器２ａから出力された小さい方のシンボル（上方の出力）は、選択部３を介することなく、最上の記憶領域１ａにそのまま格納される。また、図示していない最下の比較器から出力された大きい方のシンボル（下方の出力）は、選択部３を介することなく、最下の記憶領域（図示せず）にそのまま格納される。
【００１９】
このような選択部３の選択動作、すなわち、シンボル列の格納場所の切り替え動作に着目すると、比較部２を構成する比較器２ａ〜２ｄは、２つのグループにグループ化される。一方のグループは、奇数番目のサイクルで選択され、偶数番目のサイクルで非選択となる比較器（２ａ，２ｃ，・・・）である。他方のグループは、奇数番目のサイクルで非選択となり、偶数番目のサイクルで選択される比較器（２ｂ，２ｄ，・・・）である。これにより、奇数番目のサイクルでは、一方のグループに属する比較器（２ａ，２ｃ，・・・）のみが選択されるので、記憶領域１ａ，１ｂのシンボル対、記憶領域１ｃ，１ｄのシンボル対といった如く、ソート順序において一方向（図１の上から下に向かう方向）に隣接したシンボル対のセットが比較される。これに対して、偶数番目のサイクルでは、他方のグループに属する比較器（２ｃ，２ｄ，・・・）のみが選択されるので、記憶領域１ｂ，１ｃのシンボル対、記憶領域１ｄおよびその直下の記憶領域のシンボル対といった如く、上記一方向とは反対の方向（図１の下から上に向かう方向）に隣接したシンボル対のセットが比較される。記憶部１から読み出されたシンボルは、比較部２および選択部３を介して記憶部１にフィードバックされ、元の格納場所に再格納される（ただし、一対のシンボルの並べ替えが生じた場合には、両者の間で格納場所が入れ替わる）。
【００２０】
入出力部４は、ソート処理の開始に先立ち、外部から入力されたソート処理前のシンボル列Ｄin[k]を記憶部１に格納する。また、入出力部４は、一連のソート処理の完了後に、記憶部１から読み出されたソート処理後のシンボル列Ｄout[k]を外部に出力する。制御部５は、内蔵カウンタによってサイクルの推移を随時カウントアップし、これに基づいて、上述したような選択部３の切り替え制御を行う。また、制御部５は、ソート処理の完了を判定する。ソート処理の完了は、シンボル列を構成するシンボルの個数ｋ（ｋ≧３）によって一義的に特定される。シンボルの個数がｋの場合、ｋ番目のサイクルのおけるソート処理の完了を以て、一連の処理が終了したと判定される。制御部５からソート終了の通知を受けた入出力部４は、記憶部１から読み出されたシンボル列Ｄout[k]を外部に出力する。
【００２１】
図２は、一例としての単一の比較器の構成図である。なお、同図は、比較器２ａに関するものであるが、これ以外の比較器２ｂ〜２ｄについても構成は同様である。比較器２ａは、１つの判定部２１と、２つのスイッチ２２ａ，２２ｂとを有する。判定部２１は、比較器２ａに入力される２つの値（Ｉa，Ｉb，ただし、Ｉa≠Ｉb）との大小関係を判定し、この判定に基づいて２つのスイッチ２２ａ，２２ｂを制御することで、出力先（Ｏａ，Ｏｂ）を設定する。例えば、Ｉａ＞Ｉｂの場合、スイッチ２２ａによってＩａ側が選択され、スイッチ２２ｂによってＩb側が選択される。これにより、Ｉa＝Ｏa，Ｉb＝Ｏbとなる。逆に、Ｉａ＜Ｉｂの場合、スイッチ２２ａによってＩb側が選択され、スイッチ２２ｂによってＩa側が選択される。これにより、Ｉa＝Ｏb，Ｉb＝Ｏaとなる。判定部２１の判定は、２つの値（Ｉa，Ｉb）の上位ビットにおける減算結果が、正の値であるか否か等に基づいて行われる。
【００２２】
つぎに、一例として、シンボル列を昇順にソートする昇順ソートについて、図３から図６までを参照しつつ具体的に説明する。なお、説明を簡略化すべく、ここでは４つのシンボル”４”，”３”，”２”，”１”のみに着目している。また、図２に示した入出力関係に則り、ある比較器に対する一対の入力を入力シンボル（Ｉa，Ｉb）と表記し、一対の出力を出力シンボル（Ｏa，Ｏb）と表記する。出力シンボル（Ｏa，Ｏb）に関して、前者の出力Ｏaは、図３〜６に示した単一の比較器ブロックにおける上方の出力に相当し、比較結果としての大きい方のシンボルを指す。また、後者の出力Ｏbは、単一の比較器ブロックにおける下方の出力に相当し、比較結果としての小さい方のシンボルを指す。
【００２３】
まず、ソート処理の開始に先立ち、記憶部１には、処理対象となるシンボル列Ｄin[k]が格納される（初期状態）。なお、現在のサイクルは、カウント値ｎ（初期値は１）によって管理されており、このカウント値はサイクルの推移に伴い１ずつ加算される。
【００２４】
図３は、１番目のサイクル（ｎ＝１）における昇順ソートの説明図である。比較器２ａ〜２ｄは、それぞれに供給された比較対象の比較を並列に実行し、値の大小に基づく並べ替えを適宜行った上で比較結果を出力する。これにより、比較器２ａは入力シンボル（４，３）を並べ替えて出力シンボル（３，４）を出力する。同様に、比較器２ｂは入力シンボル（３，２）を並べ替えて出力シンボル（２，３）を、比較器２ｃは入力シンボル（２，１）を並べ替えて出力シンボル（１，２）を、比較器２ｄは入力シンボル（１，＊）を並べ替えて出力シンボル（１，＊）をそれぞれ出力する。なお、シンボル”＊”は、シンボル”１”の直下に位置する格納場所のシンボルを示す。このサイクルでは、スイッチ３ａ〜３ｃのいずれも、自己が備える２つの入力端子のうちの上方の端子を選択している。これにより、比較器２ａの出力シンボル（３，４）は、入力シンボル（４，３）が読み出されたのと同じ格納場所に再格納される（ただし両者の格納場所は入れ替わっている）。同様に、比較器２ｃの出力シンボル（１，２）も入力シンボル（２，１）の格納場所に再格納される。これに対して、比較器２ｂの出力シンボル（２，３）および比較器２ｄの出力シンボル（１，＊）は、スイッチ３ａ〜３ｃが非選択なので、再格納されることなく、いずれも無視される。つまり、このサイクルでは、すべての比較器２ａ〜２ｄが並列に動作するものの、実質的には、スイッチ３ａ〜３ｃによって選択された比較器２ａ，２ｃのみが機能し、それ以外の比較器２ｂ，２ｄは機能しないことになる。
【００２５】
図４は、２番目のサイクル（ｎ＝２）における昇順ソートの説明図である。このサイクルにおいて、比較器２ａは、入力シンボル（３，４）を並べ替えることなくそのまま出力シンボル（３，４）として、また、比較器２ｃは入力シンボル（１，２）をそのまま出力シンボル（１，２）としてそれぞれ出力する。一方、比較器２ｂは、入力シンボル（４，１）を並べ替えて出力シンボル（１，４）として出力し、比較器２ｄは、入力シンボル（２，＊）をそのまま出力シンボル（２，＊）として出力する。このサイクルでは、スイッチ３ａ〜３ｃのいずれも下方の端子を選択している。これにより、比較器２ｂの出力シンボル（１，４）は、入力シンボル（４，１）が読み出されたのと同じ格納場所に再格納される。同様に、比較器２ｄの出力シンボル（２，＊）も入力シンボル（２，＊）の格納場所に再格納される。これに対して、比較器２ａの出力シンボル（３，４）および比較器２ｃの出力シンボル（１，２）は、スイッチ３ａ〜３ｃが非選択なので、基本的に、再格納されることなく無視される。ただし、例外として、最上の比較器２ａからの小さい方のシンボル”３”は、スイッチが介在しない関係上、記憶部１に再格納される（この例外は最下の比較器についても該当する）。このサイクルでは、すべての比較器２ａ〜２ｄが並列に動作するものの、実質的には、スイッチ３ａ〜３ｃによって選択された比較器２ｂ，２ｄのみが機能し、それ以外の比較器２ａ，２ｃは機能しないことになる。このサイクルで留意すべきは、最上および最下を除く中間の比較器（例えば２ｂ）の入力シンボル（４，１）が、１番目のサイクルで比較器２ａから出力された大きい方のシンボル”４”と、１番目のサイクルで比較器２ｃから出力された小さい方のシンボル”１”とによって構成されている点である。
【００２６】
図５は、２番目のサイクルに続く３番目のサイクル（ｎ＝３）での昇順ソートの説明図である。このサイクルにおいて、比較器２ａは入力シンボル（３，１）に対して出力シンボル（１，３）を、比較器２ｃは入力シンボル（４，２）に対して出力シンボル（２，４）をそれぞれ出力する。一方、比較器２ｂは入力シンボル（１，４）に対して出力シンボル（１，４）を、比較器２ｄは入力シンボル（２，＊）に対して出力シンボル（２，＊）をそれぞれ出力する。本サイクルサイクルでは、スイッチ３ａ〜３ｃによって比較器２ａ，２ｃが選択されるので、入力シンボル（３，１）の格納場所に出力シンボル（１，３）が再格納され、入力シンボル（４，２）の格納場所に出力シンボル（２，４）が再格納される。このサイクルにおいて、中間の比較器（例えば２ｃ）の入力シンボル（４，２）は、２番目のサイクルで比較器２ｂから出力された大きい方のシンボル”４”と、２番目のサイクルで比較器２ｃから出力された小さい方のシンボル”２”とによって構成される。
【００２７】
図６は、３番目のサイクルに続く４番目のサイクル（ｎ＝４）での昇順ソートの説明図である。このサイクルにおいて、比較器２ａは入力シンボル（１，３）に対して出力シンボル（１，３）を、比較器２ｃは入力シンボル（２，４）に対して出力シンボル（２，４）をそれぞれ出力する。一方、比較器２ｂは入力シンボル（３，２）に対して出力シンボル（２，３）を、比較器２ｄは入力シンボル（４，＊）に対して出力シンボル（４，＊）をそれぞれ出力する。本サイクルでは、スイッチ３ａ〜３ｃによって比較器２ｂ，２ｄが選択されているので、入力シンボル（３，２）の格納場所に出力シンボル（２，３）が再格納される。なお、このサイクルにおいても、中間の比較器（例えば２ｂ）の入力シンボル（３，２）は、３番目のサイクルで比較器２ａから出力された大きい方のシンボル”３”と、３番目のサイクルで比較器２ｃから出力された小さい方のシンボル”２”とによって構成される。
【００２８】
このように、スイッチ３ａ〜３ｃは、先のサイクルでの比較結果が次のサイクルでの比較対象に反映されるように、記憶部１におけるシンボル列の格納場所をサイクル毎に切り替える。具体的には、ｎ番目のサイクルで一の比較器から出力された大きい方のシンボルと、ｎ番目のサイクルで他の比較器から出力された小さい方のシンボルとが、これに続く（ｎ＋１）番目のサイクルにおける比較器の入力となる。
【００２９】
カウント値ｎがｋ（シンボル列の個数、すなわち４）に到達した場合、ｋ番目のサイクルのソート処理が完了したことを以て、一連のソート処理が完了したものと判断される。これにより、記憶部１からシンボル列”１”，”２”，”３”，”４”が読み出され、ソート結果として入出力部４から外部に出力される。
【００３０】
このように、本実施形態では、ソート処理の開始に先立ちシンボル列を記憶部１に予め格納した状態において、選択部３の切り替え動作を伴いながら、記憶部１の出力側に並列に設けられた比較器２ａ〜２ｄによる並列処理を行っている。その結果、ほぼ全てのサイクルにおいて、ソートの並列処理をロスなく効率的に実行できるので、ソート処理の一層の高速化を図ることができる。この点を従来技術として挙げた特許文献１との対比で説明すると、従来の手法ではソート処理の完了に（２ｋ−１）回のサイクルを要するのに対して、本実施形態ではｋ回のサイクルで済む。
【００３１】
なお、上述した実施形態では、一例として昇順ソートについて説明したが、本発明はこれに限定されるものではなく、降順ソートについても同様に適用可能である。その場合、バブルソート回路を構成する各比較器の判定部の判定条件を反転させればよい。この点は、次に述べる第２の実施形態においても同様である。
【００３２】
（第２の実施形態）
上述した第１の実施形態では、一方のグループに属する比較器は奇数番目のサイクルで実質的に機能せず、また、他方のグループは偶数番目のサイクルで実質的に機能していない。そこで、本実施形態では、各サイクルにおいて全ての比較器が機能するように回路構成を最適化した例について説明する。
【００３３】
図７は、本実施形態にかかるバブルソート回路の構成図である。第１の実施形態との基本的な相違点は、記憶部１と比較部２との間に選択部６を追加した点、および、比較器の個数を減らして比較部２の構成を簡略化した点である。なお、それ以外については、回路の接続関係が若干異なる点を除けば、第１の実施形態と同様なので、図２で用いた符号と同一の符号を付して、ここでの説明を省略する。
【００３４】
記憶部１の出力側で、かつ、比較部２の入力側には、互いに並列に設けられた複数のスイッチ６ａ〜６ｄで構成された選択部６が接続されている。それぞれのスイッチ６ａ〜６ｄは、二入力一出力の回路構成を有し、記憶部１から読み出された一対のシンボルのいずれかを選択的に出力する。これらのスイッチ６ａ〜６ｄへの入力を供給する供給元（格納場所）は、予め割り当てられており、かつ、それぞれに対して割り当てられる記憶領域１ａ〜１ｄが異なっている。具体的には、たスイッチ６ａには記憶領域１ａ，１ｂ、スイッチ６ｂには記憶領域１ｂ，１ｃ、スイッチ６ｃには記憶領域１ｃ，１ｄがそれぞれ割り当てられているといった如くである。なお、スイッチ６ｄの供給元は、一方が記憶領域１ｄ、他方がこの記憶領域１ｄと隣接した記憶領域（図示せず）である。また、スイッチ６ａ，６ｂの出力は比較器２ａに供給され、スイッチ６ｃ，６ｄの出力は比較器２ｂに供給される。
【００３５】
選択部６の選択状態は、制御部５の制御下において、サイクル毎に切り替えられる。具体的には、それぞれのスイッチ６ａ〜６ｄは、奇数番目のサイクルでは上方の入力端子を選択し、偶数番目のサイクルでは下方の入力端子を選択する。これにより、奇数番目のサイクルでは、ソート順序において一方向（図７の上から下に向かう方向）に隣接したシンボル対のセット（すなわち、記憶領域１ａ，２ｂから読み出されたシンボル対、記憶領域１ｃ，１ｄから読み出されたシンボル対）が比較部２に供給される。そして、偶数番目のサイクルでは、これとは反対の方向（図７の下から上に向かう方向）に隣接したシンボル対のセット（すなわち、記憶領域１ｂ，１ｃから読みだれたシンボル対、記憶領域１ｄとその直下の格納場所から読み出されたシンボル対）が比較部２に供給される。そして、比較部２を構成する個々の比較器２ａ，２ｂは、前段の選択部６より供給された一対のシンボルの比較を並列に行い、後段の選択部３に出力する。この選択部３の基本的な機能は、第１の実施形態と同様であるが、比較器２ａ，２ｂの個数が減った関係で、単一の比較器（例えば２ａ）からの一出力が２つのスイッチ（例えば３ａ，３ｂ）の入力になっている点で相違している。
【００３６】
つぎに、一例として、シンボル列を昇順にソートする昇順ソートについて、図８から図１１までを参照しつつ具体的に説明する。まず、ソート処理の開始に先立ち、記憶部１には、処理対象となるシンボル列Ｄin[k]が格納される（初期状態）。
【００３７】
図８は、１番目のサイクル（ｎ＝１）における昇順ソートの説明図である。奇数番目のサイクルでは、スイッチ６ａ〜６ｄはいずれも、自己が備える２つの入力端子のうちの上方の端子を選択している。したがって、記憶部１から読み出されたシンボル列は、上記一方向に隣接したシンボル対のセット（４，３），（２，１）として後段の比較部２に供給される。比較器２ａ，２ｂは、それぞれに供給された比較対象の比較を並列に実行し、値の大小に基づく並べ替えを適宜行った上で比較結果を出力する。これにより、比較器２ａは、入力シンボル（４，３）を並べ替えて出力シンボル（３，４）を出力する。また、比較器２ｂは、入力シンボル（２，１）を並べ替えて出力シンボル（１，２）を出力する。一方、このサイクルでは、スイッチ３ａ〜３ｃのいずれも、自己が備える２つの入力端子のうちの下方の端子を選択している。これにより、比較器２ａの出力シンボル（３，４）は、入力シンボル（４，３）が読み出されたのと同じ格納場所に再格納される。また、比較器２ａと並列に動作する比較器２ｂの出力シンボル（１，２）は、入力シンボル（２，１）の格納場所に再格納される。
【００３８】
図９は、２番目のサイクル（ｎ＝２）における昇順ソートの説明図である。このサイクルにおいて、偶数番目のサイクルでは、スイッチ６ａ〜６ｄはいずれも、自己が備える２つの入力端子のうちの下方の端子を選択している。したがって、記憶部１から読み出されたシンボル列は、上記一方向とは反対の方向に隣接したシンボル対のセット（４，１），（２，＊）として後段の比較部２に供給される。比較器２ａは、入力シンボル（４，１）を並べ替えて出力シンボル（１，４）を出力する。また、比較器２ｂは、入力シンボル（２，＊）をそのまま出力シンボル（２，＊）を出力する。また、スイッチ３ａ〜３ｃのいずれも、自己が備える２つの入力端子のうちの上方の端子を選択している。これにより、比較器２ａの出力シンボル（１，４）は、入力シンボル（４，１）が読み出されたのと同じ格納場所に再格納される。また、比較器２ａと並列に動作する比較器２ｂの出力シンボル（２，＊）は、入力シンボル（２，＊）の格納場所に再格納される。
【００３９】
図１０は、２番目のサイクルに続く３番目のサイクル（ｎ＝３）での昇順ソートの説明図である。記憶部１から読み出されたシンボル列は、スイッチ６ａ〜６ｄの切り替え動作により、上記一方向に隣接したシンボル対のセット（３，１），（４，２）として後段の比較部２に供給される。比較器２ａは入力シンボル（３，１）に対して出力シンボル（１，３）を、比較器２ｂは入力シンボル（４，２）に対して出力シンボル（２，４）をそれぞれ出力する。上述したスイッチ３ａ〜３ｃの切り替え動作により、比較器２ａの出力シンボル（１，３）は、入力シンボル（３，１）が読み出されたのと同じ格納場所に再格納される。また、比較器２ｂの出力シンボル（２，４）は、入力シンボル（４，２）の格納場所に再格納される。
【００４０】
図１１は、３番目のサイクルに続く４番目のサイクル（ｎ＝４）での昇順ソートの説明図である。記憶部１から読み出されたシンボル列は、スイッチ６ａ〜６ｄの切り替え動作により、上記一方向とは反対の方向に隣接したシンボル対のセット（３，２），（４，＊）として後段の比較部２に供給される。比較器２ａは入力シンボル（３，２）に対して出力シンボル（２，３）を、比較器２ｂは入力シンボル（４，＊）に対して出力シンボル（４，＊）をそれぞれ出力する。上述したスイッチ３ａ〜３ｃの切り替え動作により、比較器２ａの出力シンボル（２，３）は、入力シンボル（３，２）が読み出されたのと同じ格納場所に再格納される。また、比較器２ｂの出力シンボル（４，＊）は、入力シンボル（４，＊）の格納場所に再格納される。
【００４１】
このように、比較器２ａ，２ｂの前段に位置するスイッチ６ａ〜６ｄと後段に位置するスイッチ３ａ〜３ｃとが連係して、先のサイクルでの比較結果が次のサイクルでの比較対象に反映されるように、記憶部１におけるシンボル列の格納場所をサイクル毎に切り替える。具体的には、ｎ番目のサイクルで一の比較器から出力された大きい方のシンボルと、ｎ番目のサイクルで他の比較器から出力された小さい方のシンボルが、これに続く（ｎ＋１）番目のサイクルにおける比較器の入力となる。
【００４２】
カウント値ｎがｋ（シンボル列の個数、すなわち４）に到達した場合、ｋ番目のサイクルのソート処理が完了した後に、記憶部１からシンボル列”１”，”２”，”３”，”４”が読み出され、ソート結果として入出力部４から外部に出力される。これによって、一連のソート処理が完了する。
【００４３】
このように、本実施形態では、奇数番目のサイクルにおいて、前段の選択部６は、ソート順序において一方向に隣接したシンボルのセットを比較部２に出力し、後段の選択部３は、比較部２からの出力を記憶部１の元の格納場所に再格納する。また、偶数番目のサイクルにおいて、前段の選択部６は、上記一方向とは反対の方向に隣接したシンボルのセットを比較部２に出力し、後段の選択部３は、比較部２からの出力を記憶部１の元の格納場所に再格納する。これにより、第１の実施形態と同様に、ソート処理の一層の高速化を図ることができる。それとともに、比較部２を構成する比較器の個数を削減できるので、バブルソート回路の全体的な回路規模を縮小することができる。
【００４４】
（第３の実施形態）
図１２は、上述した第１または第２の実施形態にかかるバブルソート回路を用いたデータ圧縮システムの構成図である。このデータ圧縮システム１００は、上述したような構成を有するバブルソート回路１０と、ハフマン符号化回路２０とで構成されている。バブルソート回路１０は、ソート処理前の入力シンボル列Ｄin[k]に対してソート処理を施し、出力シンボル列Ｄout[k]を出力する。ハフマン符号化回路２０は、周知の構成を有し、ソート処理後の出力シンボル列Ｄout[k]に基づいてハフマン符号化を行い、圧縮データを出力する。ハフマン符号化処理は、シンボルの出現頻度の規則性に着目してデータ圧縮を行う代表的なアルゴリズムであり、各出現頻度に対応する符号長（または符号）を個々のデータに割り当てる。このハフマン符号化処理には、パッケージ結合(ノード結合)の各ステップにおいて、最小の出現頻度を抽出する過程が必要となる。つまり、バブルソート回路１０は、圧縮対象のデータ列における各シンボルの出現頻度（出現頻度表）を、ソート対象のシンボル列Ｄin[k]とし、ハフマン符号化処理を行う前に、バブルソート回路１０による出現頻度表のソート処理を用いることで、整列された出現頻度表が得られ、シームレスなハフマン符号化処理を行うことができる。
【００４５】
本実施形態によれば、ハフマン符号化に先立ち必要となるシンボル列のソート処理が高速化されるので、データ圧縮処理の全体的な処理の高速化を図ることができる。
【図面の簡単な説明】
【００４６】
【図１】第１の実施形態にかかるバブルソート回路の構成図
【図２】単一の比較器の構成図
【図３】１番目のサイクルにおける昇順ソートの説明図
【図４】２番目のサイクルにおける昇順ソートの説明図
【図５】３番目のサイクルにおける昇順ソートの説明図
【図６】４番目のサイクルにおける昇順ソートの説明図
【図７】第２の実施形態にかかるバブルソート回路の構成図
【図８】１番目のサイクルにおける昇順ソートの説明図
【図９】２番目のサイクルにおける昇順ソートの説明図
【図１０】３番目のサイクルにおける昇順ソートの説明図
【図１１】４番目のサイクルにおける昇順ソートの説明図
【図１２】第３の実施形態にかかるデータ圧縮システムの構成図
【符号の説明】
【００４７】
１  記憶部
１ａ〜１ｄ  記憶領域
２  比較部
２ａ〜２ｄ  比較器
３，６  選択部
３ａ〜３ｃ，６ａ〜６ｄ  スイッチ
４  入出力部
５  制御部
１０  バブルソート回路
２０  ハフマン符号化回路
２１  判定部
１００  データ圧縮システム
【図１】
2007213423.tif 000003
【図２】
2007213423.tif 000004
【図３】
2007213423.tif 000005
【図４】
2007213423.tif 000006
【図５】
2007213423.tif 000007
【図６】
2007213423.tif 000008
【図７】
2007213423.tif 000009
【図８】
2007213423.tif 000010
【図９】
2007213423.tif 000011
【図１０】
2007213423.tif 000012
【図１１】
2007213423.tif 000013
【図１２】
2007213423.tif 000014