(57)【要約】【課題】データソート回路では、データ数が多くなると、回路規模が増大化して消費電力が増大化し演算速度も低下する。【解決手段】ｎ個の入力データのうち、値の大きいほうからi（n>=i）個選択するために、データ１個毎に、最初の１回だけ各データの大小の比較を比較器CMPで行い、それぞれ１ビットの比較結果、合計（n-1）ビットの比較結果を求める。そして、（n-1）ビットの比較結果だけをセレクタSELで遷移させ、データはレジスタ部１-５に保持しておく。判定部1-4は、遷移された比較結果の内の選択条件に合致する所定のビットのみを監視することで条件に該当するか判定する。バンヤン網を用いた選択回路２は、ｎ個の比較結果により該当するデータを適切なポートに出力する。【選択図】図２
2007206753.tif 000002
【特許請求の範囲】
【請求項１】
ｎ個のデータの内で値の大きい（小さい）方からｉ個のデータを選択し、且つ昇順（降順）にソートするデータソート回路において、
入力するｎ個のデータそれぞれについて、他の（ｎ−１）個のデータと値の大小を比較して１ビットで表現された比較結果を出力する比較部と、
前記ｎ個のデータそれぞれについて、（ｎ−１）個の前記比較結果を遷移させて大きい（小さい）順に並び替える並び替え部と、
ｎ個のデータそれぞれについて、前記並び替えられた比較結果の端からｉ番目の比較結果により当該データが前記選択条件を満たしているか否かを判定する判定部と、
ｎ個のデータについての前記判定結果により前記選択条件を満たしているｉ個のデータを選択して出力する選択部とで構成されることを特徴とするデータソート回路。
【請求項２】
ｎ個のデータの内で値の大きい（小さい）方からｉ個のデータを選択し、且つ昇順（降順）にソートするデータソート回路において、
他の（ｎ−１）個のデータと値の大小を比較して１ビットで表現された比較結果を出力する（ｎ−１）個の比較器から成る比較部と、
（ｎ−１）段それぞれに（ｎ−１）／２個が配備された２入力２出力のセレクタであって、入力されるデータが異なるときは出力ポート０に「0」を、出力ポート１に「1」を出力し、データが同じときはそのままの状態を出力ポートへ出力するセレクタの群から成り、前記比較部に接続された並び替え部と、
前記並び替え部の出力の端からｉ番目の比較結果により当該データが前記選択条件を満たしているか否かを判定する判定部と、
前記判定の結果に対応する当該データを保持・出力するレジスタ部とで構成されるｎ個の判定ブロックと、
前記ｎ個の判定部からの判定の結果により前記選択条件を満たしているｉ個のデータを前記ｎ個のレジスタ部のデータから選択して出力する選択部とで構成されることを特徴とするデータソート回路。
【請求項３】
前記選択部は、対応する判定結果とレジスタ部のデータのｎ組に対して、初期アドレスから順次に当該判定結果を加算した結果を出力先アドレスとして付加する出力先付加部と、
前記出力先アドレスにしたがって指定されたｉ個の出力ポートに前記レジスタ部のデータを出力するバンヤン部とで構成されることを特徴とする請求項２記載のデータソート回路。
【請求項４】
前記バンヤン部は、それぞれが２入力×２出力のスイッチｎ／２個で構成されたｐ（２を底とするｎの対数）段の構成であり、前記出力先付加部から入力する出力先アドレス付き判定結果とレジスタ部のデータのｎ組に対して、各段では、ｐビットで表現された前記出力先アドレスの最下位ビットからビット毎にチェックして出力ポートを指定していくことを特徴とする請求項３記載のデータソート回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動通信システムの一つである符号分割多元接続（CDMA）方式のパスサーチ回路等において、複数のデータのうち、値の大きい（小さい）方から一定の個数のデータを選択し、且つ昇順（降順）にソートするデータソート回路に関する。
【背景技術】
【０００２】
従来、この種のデータソート回路は、任意の数の入力データに対して、２つの入力データ毎に大小比較し、その出力の行き先を決めることでデータを並べ替える回路を複数個設け、これを必要に応じて繰り返すことにより、データを並び替えている（例えば、特許文献１参照）。
【０００３】
【特許文献１】特開平１１−１２１６１５５号公報（第２頁−第３頁、図１）
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上述した従来のデータソート回路では、各入力データを２つずつ比較し、それぞれの大小関係によりデータを並び替え、さらに他のデータと比較し、再度並び替えることを繰り返し実行することで実現しているが、この種の処理はソフトウェアによるのが一般的でもあり、入力データ数がそのまま演算（比較）段数、および演算ビット数（データ幅）に影響するので、入力データ数が多いと演算処理速度が遅くなり高速演算処理に向かないという問題点がある。
【０００５】
一方、演算処理時間の短縮を目指してハードウェア化すると、大小比較のためにデータを保持するレジスタが多く必要となり、データ数の増えた分だけ回路規模が増大するため、入力データ数が増えると、それに比例して回路規模と消費電力も増すという問題が発生する。
【０００６】
そこで、本発明の目的は、回路規模を削減することで、小型・軽量化と低消費電力化を図ると共に、より高速な演算処理を可能にするデータソート回路を提供することにある。
【課題を解決するための手段】
【０００７】
本発明のデータソート回路は、ｎ個のデータの内で値の大きい（小さい）方からｉ個のデータを選択し、且つ昇順（降順）にソートするデータソート回路において、入力するｎ個のデータそれぞれについて、他の（ｎ−１）個のデータと値の大小を比較して１ビットで表現された比較結果を出力する比較部と、ｎ個のデータそれぞれについて、（ｎ−１）個の比較結果を遷移させて大きい（小さい）順に並び替える並び替え部と、ｎ個のデータそれぞれについて、並び替えられた比較結果の端からｉ番目の比較結果により当該データが選択条件を満たしているか否かを判定する判定部と、ｎ個のデータについての判定結果により選択条件を満たしているｉ個のデータを選択して出力する選択部とで構成されることを特徴とする。
【０００８】
より詳しくは、本発明のデータソート回路は、ｎ個のデータの内で値の大きい（小さい）方からｉ個のデータを選択し、且つ昇順（降順）にソートするデータソート回路において、他の（ｎ−１）個のデータと値の大小を比較して１ビットで表現された比較結果を出力する（ｎ−１）個の比較器（図２のCMP0〜CMP6）から成る比較部（図２の1-2）と、（ｎ−１）段それぞれに（ｎ−１）／２個が配備された２入力２出力のセレクタ（図２のSEL0〜SEL20）であって、入力されるデータが異なるときは出力ポート０に「0」を、出力ポート１に「1」を出力し、データが同じときはそのままの状態を出力ポートへ出力するセレクタの群から成り、比較部に接続された並び替え部（図２の1-3）と、並び替え部の出力の端からｉ番目の比較結果により当該データが選択条件を満たしているか否かを判定する判定部と、判定の結果に対応する当該データを保持・出力するレジスタ部とで構成されるｎ個の判定ブロック（図１の1-0-0〜1-0-7））と、ｎ個の判定部からの判定の結果により選択条件を満たしているｉ個のデータをｎ個のレジスタ部のデータから選択して出力する選択部（図１の２）とで構成されることを特徴とする。
【０００９】
更に、選択部（図１の２）は、対応する判定結果とレジスタ部のデータのｎ組に対して、初期アドレスから順次に当該判定結果を加算した結果を出力先アドレスとして付加する（図７）出力先付加部（図６の2-1）と、出力先アドレスにしたがって指定されたｉ個の出力ポートにレジスタ部のデータを出力するバンヤン部（図６の2-2）とで構成されることを特徴とする。
【００１０】
また、バンヤン部（図６の2-2）は、それぞれが２入力×２出力のスイッチｎ／２個で構成されたｐ（２を底とするｎの対数）段の構成であり（図８）、出力先付加部から入力する出力先アドレス付き判定結果とレジスタ部のデータのｎ組に対して、各段では、ｐビットで表現された出力先アドレスの最下位ビットからビット毎にチェックして出力ポートを指定していくことを特徴とする。
【発明の効果】
【００１１】
本発明は、初めにデータを比較した後は、その比較結果を使用してデータの大小を比較し、データ自身を遷移させない構成としたため、回路規模を縮小でき、消費電力も低下させることができるという第１の効果を得ることができる。
【００１２】
また、複数の比較結果を並べ替えて、その並べ替えられた結果のみを監視するだけで、昇順/降順の並び替えと共に、必要データの選別（判別）が容易にできる構成としたため、ソフトウェアに頼る必要がなくなり、処理時間の短縮が可能になるという第２の効果を得ることができる。
【発明を実施するための最良の形態】
【００１３】
本発明では、ｎ個の入力データのうち、値の大きい方からi（n>=i）個を選択するために最初の１回だけ、各データの大小の比較を比較手段で行い、それぞれ１ビットの比較結果、合計（n-1）ビットの比較結果を求める。そして、（n-1）ビットの比較結果を遷移させ、判定手段により、あるビットのみを監視することで条件に該当するか判定し、バンヤン網を用いて該当するデータを適切なポートに出力する。遷移させるデータはメモリに一時格納しておき、最終結果が出た時点で適切なポートに読み出す。以下、本発明について図面を参照しながら詳細に説明する。
【００１４】
図１は本発明のデータソート回路の一実施例を示すブロック図である。このデータソート回路は、８つの入力データID0〜ID7の内で大きい方から４つのデータを選択し、大きい順に出力データOD0〜OD3として出力するものである。８つの入力データIDそれぞれは、他の７つの入力データIDと８つの判定ブロック1-0-0〜1-0-7において比較され、判定結果REが被選択データSDを付して選択回路２へ出力される。選択回路２は、判定結果REに基づき８つの被選択データSDの内から大きい順に４つを選択し、出力データOD0〜OD3として出力する。被選択データSDは実質的には入力データIDである。
【００１５】
入力データID0は被選択データSD0と比較データCD0に分岐され、被選択データSD0は判定ブロック1-0-0、比較データCD0は判定ブロック1-0-0〜1-0-7に供給される。また、入力データID1は被選択データSD1と比較データCD1に分岐され、被選択データSD1は判定ブロック1-0-1、比較データCD1は判定ブロック1-0-0〜1-0-7に供給される。他の入力データIDについても同様である。
【００１６】
入力データID0は、判定ブロック1-0-0において、比較対象の比較データCD0として他の入力データID1〜ID7（比較データCD1〜CD7）と比較され、入力データID1は、判定ブロック1-0-1において、比較対象の比較データCD1として他の入力データID0，ID2〜ID7（比較データCD0，CD2〜CD7）と比較される。他の入力データID3〜ID7も同様である。
【００１７】
判定ブロック1-0-1〜1-0-7は判定ブロック1-0-0の陰に入って明示されていないが、判定ブロック1-0-0と同構成である。また、判定ブロック1-0-1〜1-0-7における動作も同じであって同時進行形で行われる。以下、判定ブロック1-0の構成および動作については判定ブロック1-0-0について行うものとする。
【００１８】
判定ブロック1-0-0は、図２に詳細を示すように、７個の比較器CMP0〜CMP6で構成されて比較データCD0と比較データCD1〜CD7との大小を比較し大小判定を行う比較部1-2と、比較部1-2に判定ブロック1-0-0が判定する比較対象の比較データCD0の番号（比較データ番号）を通知する判定ブロック番号通知部1-1と、２１個のセレクタSEL0〜SEL20で構成されて比較部1-2による比較結果を並べ替える並べ替え部1-3と、並べ替えの結果による判定結果を選択回路２へ出力する判定部1-4と、被選択データSD0を保持するレジスタ部1-5で構成される。
【００１９】
以下、各構成要素について詳述する。判定ブロック番号通知部1-1は、比較部1-2に対して何番の判定ブロックで動作しているかを通知する。判定ブロック1-0-0で通知されるのは１番である。これにより、比較部1-2の各比較器CMP0〜CMP6が比較する比較データ番号を認識することができる。
【００２０】
比較部1-2では、7個の比較器CMP0〜CMP6で比較データCD0〜7の大小比較を行う。比較器CMP0はCD0とCD1を、比較器CMP1はCD0とCD2を、同様に比較器CMP2〜CMP6はCD0とCD3〜CD7をそれぞれ比較する。その結果、比較データCD0の値より他方の比較データCDの値が大きければ「1」を、小さければ「0」を出力する。図３は判定ブロック1-0-0〜1-0-7それぞれにおける比較器CMP0〜CMP6での比較データCDの一覧を示す。
【００２１】
全ての比較器CMP0〜CMP6から出力される「1」の個数でCD0が大きい方から何番目であるかが分かる。この方式の場合、入力データが等しい状況の時には困惑するが、例えば、比較器CMP0〜CMP6に入力される比較データCDが等しい場合、比較データCDの番号が小さい方の比較データCDを大きいと判定するような構成としている。このとき、比較器CMP0〜CMP6は、判定ブロック番号通知部1-1から比較対象の比較データの番号を通知されるので、これによって番号の大小判定をすることができる。
【００２２】
図４は、判定ブロック1-0-0〜1-0-7それぞれにおいて、等しい値の比較データCDが入力された場合に、その比較器CMPが大きいと判定する比較データCDの一覧を示す。ここで、比較データCD0〜CD7が全て等しい場合、比較対象の比較データであるCD0の番号は他の全ての比較データの番号より小さいから、比較データCD0の方が大きいとされるため、判定ブロック1-0-0の比較器CMP0〜CMP6の比較結果はそれぞれ「0,0,0,0,0,0,0」となる。
【００２３】
また、判定ブロック1-0-1の比較器CMP0では、比較対象の比較データであるCD1の番号は比較データであるCD0の番号より大きいから、比較データCD0の方が大きいとされる。しかし、比較器CMP1〜CMP6では、比較対象の比較データであるCD1の番号は比較データであるCD2〜CD7の番号より小さいから、比較データCD1の方が大きいとされる。この結果、比較器CMP0〜CMP6の比較結果は、「1,0,0,0,0,0,0」となる。同様に、判定ブロックは1-0-2では「1,1,0,0,0,0,0」となる。以下、同様である。
【００２４】
各判定ブロック1-0の比較器CMP0〜CMP6がこのような動作をすることで、大小の順位をユニークにつけることができるため、値の等しい比較データCDが複数存在する場合であっても、選択回路２において、希望する個数、ここでは大きい方から４個を選択することができる。
【００２５】
並べ替え部1-3には、比較部1-2から「1」または「0」の比較結果が７つ入力され、比較結果「1」を下詰に、比較結果「0」を上詰に並べ替えて出力する。並べ替え部1-3を構成する２１個のセレクタSEL0〜SEL20の動作を図５に示す。
【００２６】
セレクタSEL0〜SEL20は、入力と出力が共にポートが２つある。入力ポート０、入力ポート１に入力されるデータが、「0」と「1」（図５の[Ａ]）、もしくは「1」と「0」（図５の[Ｂ]）であれば、出力ポート０に「0」を、出力ポート１に「1」を出力する。入力ポート０、入力１に入力されるデータが、両方とも「1」、もしくは「0」（図５の[Ｃ]，［Ｄ］）であれば、そのまま出力する。このようなセレクタSEL0〜SEL20を図１のように３つ並列に並べたものを７段おくことにより、７つの比較結果のうち比較結果「1」を下詰に、比較結果「0」を上詰にすることができる。
【００２７】
次に、並べ替え部1-3からの出力を下から順に、判定部1-4の入力ポート0〜6へ入力する。例えば、比較データCDが大きい方から３番目だった場合、比較結果「1」は２つあることになり、並べ替え部1-3を通過して、判定部1-4の入力ポート0〜6へ「1,1,0,0,0,0,0」が入力される。
【００２８】
また、比較データCDが大きい方から５番目だった場合、比較結果「1」は４つあり、判定部1-4の入力ポート0〜6へは「1,1,1,1,0,0,0」が入力される。つまり、比較結果が「1」になる数が比較データCDの大きさの順位を表し、その「1」が判定部1-4の入力ポート0から下詰に入力されるため、入力ポート3が「0」であれば大きい方から４個に含まれ、「1」であれば大きい方から４個に含まれないことが分かる。
【００２９】
そこで、判定部1-4は、入力ポート3を監視し、そこに入力される比較結果が「1」なら大きい方からの４個に含まれないとして、判定結果RE0に「0」を出力し、一方、「0」なら大きい方からの４個に含まれるとして判定結果RE0に「1」を出力する。また、レジスタ部1-5は判定結果RE0に対応する被選択データSD0を保持・出力する。
【００３０】
他の比較データCD1〜CD7についても、それぞれ同様に1-0-1〜1-0-7判定ブロック1-0-1〜1-0-7で大小比較を行い、その結果を判定結果RE1〜RE7として出力する。また、判定ブロック1-0-1〜1-0-7の各レジスタ部1-5はそれぞれの判定結果RE1〜RE7に対応する被選択データSD1〜SD7を出力する。判定結果RE0〜RE7は、レジスタ部1-5に保持されている被選択データSD0〜SD7と共に選択回路２へ出力される。選択回路２では、判定ブロック1-0-0〜1-0-7からの上記出力を基に、指定された出力ポートに該当データを出力する。
【００３１】
図６は選択回路２の詳細ブロック図である。選択回路２は、出力先のポートを指定する出力先付加部2-1と、出力先にしたがって指定された出力ポートにデータを出力するバンヤン部2-2から構成される。
【００３２】
出力先付加部2-1は、図７に詳細を示すように、対応する判定結果REと被選択データSDの組に出力ポートを指定する出力先アドレスOAを付加する。この出力先アドレスOAは８個のデータの出力先を３ビットで表現し、先ず、SD0 & RE0には「000」を出力先アドレスOA0として付加する。SD1 & RE1には出力先アドレスOA0にRE1を加算した結果を出力先アドレスOA1として付加し、SD2 & RE2には出力先アドレスOA1にRE2を加算した結果を出力先アドレスOA2として付加する。以下同様に、出力先アドレスOA3〜7を生成して、対応する判定結果REと被選択データSDの組に付加する。これらをバンヤン部2-2に入力する。
【００３３】
バンヤン部2-2は、図８に詳細を示すように、３段のスイッチ群4-1〜4-3から成る。スイッチ群4-1〜4-3それぞれは、２入力×２出力のスイッチ４個で構成され、したがってバンヤン部2-2は計１２個のスイッチから成る。スイッチ群4-1の４個のスイッチとスイッチ群4-2の４個のスイッチの間、およびスイッチ群4-2の４個のスイッチとスイッチ群4-3の４個のスイッチの間は、図示のとおりに接続されている。
【００３４】
バンヤン部2-2では、１段目のスイッチ群4-1は出力先アドレスOA0〜OA7のビット0を参照し、同様に２段目のスイッチ4-2はビット1を、さらに３段目のスイッチ4-3はビット2をそれぞれ参照して、データの行き先を切り替える。参照した出力先アドレスOA0〜OA7の該当ビットが「1」ならば、そのデータの行き先はスイッチの出力ポート1に、「0」ならば出力ポート0にデータを出力する。このとき、データの行き先の競合を避けるために、スイッチは下記の条件で動作させる。
（１）２入力の判定結果REが共に「0」ならば、入力側と同じポート番号（前段のスイッチの出力ポート番号）の出力ポートにデータを出力する。
（２）２入力の判定結果REが共に「1」ならば、出力先アドレスの該当ビットに従ってデータを出力する。
（３）２入力の判定結果REが異なる場合には、判定結果が「1」のデータの出力先アドレスのビットに従って優先的にデータを出力し、一方の判定結果が「0」のデータは、左記と異なる出力ポートに出力する。
【００３５】
以上のような行き先の選択を、出力先アドレスOA0〜OA7のLSBからMSBへと1ビットずつ行っていくことで、３段目のスイッチ4-3の４つのスイッチの各出力ポート「0」からの出力データOD0〜OD3には、入力データID0〜ID7のうち、大きい方から４個のデータが出力される。
【００３６】
図９は、バンヤン部2-2における各段のスイッチ群4-1，4-2，4-3へ入力するデータの遷移図の一例を示す。図９において、８つの被選択データSD0〜SD7を「a〜h」とし、その判定結果RE0〜RE7は図示のとおりとする。また、被選択データ「ａ」の出力先アドレスは「000」とすると、他の被選択データ「ｂ〜h」の出力先アドレスは、出力先付加部2-1により図示のとおりに定まる。各段で入出力されるデータはテーブル表示されている。
【００３７】
スイッチ群4-1の１つ目と２つ目のスイッチは上記の条件（３）、３つ目のスイッチは上記の条件（１）、４つ目のスイッチは上記の条件（２）にそれぞれ従う。また、スイッチ群4-2およびスイッチ群4-3の各４つのスイッチは、全てが上記の条件（３）に従う。この結果、出力データOD0〜OD3としては、「ａ，ｇ，ｃ，ｈ」が出力される。
【００３８】
なお、上述のようなバンヤンスイッチの特性として、出力先が順番にソートされていれば、内部競合が発生しないことは、ATMの技術分野では明らかである。この点について理解を得るには、例えば、「ATM入門:マルチメディア時代へのパスポート」（横川ディジタルコンピュータ株式会社SI事業部 著、トッパン発行  1994-09-30出版  P49〜P50）を参照されたい。
【００３９】
本データソート回路を用いる場合は、入力データ数（サンプル数）が多ければ多いほど、その効果が如実に現れる。また、データの選択数は任意に設定可能で、且つ、そのソートに関しては昇順／降順の何れも可能である。
【図面の簡単な説明】
【００４０】
【図１】本発明のデータソート回路の一実施例を示すブロック図
【図２】判定ブロックの詳細図
【図３】判定ブロックそれぞれの各比較器での比較データの一覧を示す図
【図４】判定ブロックそれぞれにおいて等しい値の比較データが入力された場合に大きいと判定する比較データの一覧を示す図
【図５】図１におけるセレクタの基本動作を示す図
【図６】図１における選択回路の構成例を示す図
【図７】選択回路における出力先付加部の詳細図
【図８】選択回路におけるバンヤン部の詳細図
【図９】バンヤン部において各段のスイッチの入出力データの遷移例を表す図
【符号の説明】
【００４１】
1-0-0〜1-0-7   判定ブロック
1-0            判定ブロック番号通知部
1-2            比較部
1-3            並び替え部
1-4            判定部
1-5            レジスタ部
２             選択回路
2-1            出力先付加部
2-2            バンヤン部
4-1〜4-3       スイッチ
CMP0〜CMP7     比較器
SEL0〜SEL20    セレクタ
【図１】
2007206753.tif 000003
【図２】
2007206753.tif 000004
【図３】
2007206753.tif 000005
【図４】
2007206753.tif 000006
【図５】
2007206753.tif 000007
【図６】
2007206753.tif 000008
【図７】
2007206753.tif 000009
【図８】
2007206753.tif 000010
【図９】
2007206753.tif 000011