(57)【要約】【課題】  回路規模を縮減し、高速化を図るデータ選択回路及び方法の提供。【解決手段】  前段の並び替え回路1-1〜1-S/2と、後段の並び替え回路2-1〜2-S/2を備え、並び替え回路1-1では初期化後入力1から選択対象データが順次入力され大のデータは破棄され、後段の各並び替え回路2-iは入力1、2から前段の並び替え回路1-ｉ、1-(i+1）の小、大出力を入力し、後段の並び替え回路2-S/2は入力1、2から並び替え回路1-S/2の小出力と保持回路4-1の出力を入力し、前段の並び替え回路1-1は入力2の初期化後、並び替え回路2-1の大出力を入力し、前段の並び替え回路1-iは、後段の並び替え回路2-(i-1)、2-iの小、大出力を入力し、保持回路4-1は並び替え回路2-S/2の小出力を入力し、後段の並び替え回路2-1〜2-S/2の２つの出力を受ける出力制御回路５は選択対象データの中から小さな値のＳ個のデータを多重出力する。【選択図】            図１
2005209092.tif 000002
【特許請求の範囲】
【請求項１】
２つの入力からそれぞれ入力された２つのデータの大小を判別し、判別結果に基づき、前記入力された２つのデータのうち、小のデータ、大のデータをそれぞれ第１、第２の出力から出力する並び替え回路をＳ個（ただし、Ｓは所定の偶数）有し、このうち、Ｓ／２個の並び替え回路が１つの保持回路とともに、前段に並置され、Ｓ／２個の並び替え回路は、後段に並置され、
前段の第１の並び替え回路において、２つの入力の一方から、選択対象データが順次入力され、第２の出力からのデータは破棄され、
後段の第ｉ（ただし、ｉは１〜Ｓ／２−１の整数）の並び替え回路は、２つの入力から、前段の第ｉの並び替え回路の第１の出力と、前段の（ｉ＋１）の並び替え回路の第２の出力とを入力して並び替えを行い、
後段の第Ｓ／２の並び替え回路は、２つの入力から、前段の第Ｓ／２の並び替え回路の第１の出力と、前記保持回路の出力とを入力して並び替えを行い、
前段の第１の並び替え回路は、２つの入力の他方から、後段の第１の並び替え回路の第２の出力を入力して、前記一方の入力からのデータとの並び替え処理を行い、
前段の第ｉ（ただし、ｉは２〜Ｓ／２の整数）の並び替え回路は、２つの入力から、後段の第（ｉ−１）の並び替え回路の第１の出力と、後段の第ｉの並び替え回路の第２の出力とを入力して並び替え処理を行い、
前記保持回路は、後段の第Ｓ／２の並び替え回路の第１の出力を入力し、
後段のＳ／２個の並び替え回路の第１、第２の出力より、前記入力された複数の選択対象データの中から値が小さなＳ個のデータが取り出される、ことを特徴とするデータ選択回路。
【請求項２】
２つの入力からそれぞれ入力された２つのデータの大小を判別し、判別結果に基づき、前記入力された２つのデータのうち、小のデータ、大のデータをそれぞれ第１、第２の出力から出力する並び替え回路を、少なくとも、選択するデータの個数Ｓ個（ただし、Ｓは所定の奇数）有し、このうち、（Ｓ＋１）／２個の並び替え回路は、前段に並置され、（Ｓ−１）／２個の並び替え回路が、１つの保持回路とともに後段に並置され、
前段の第１の並び替え回路において、２つの入力の一方から、選択対象データが順次入力され、第２の出力からのデータは破棄され、
後段の第ｉ（ただし、ｉは１〜（Ｓ−１）／２の整数）の並び替え回路は、２つの入力から、前段の第ｉの並び替え回路の第１の出力と、前段の（ｉ＋１）の並び替え回路の第２の出力とを入力して並び替えを行い、
前記保持回路は、前段の第（Ｓ＋１）／２の並び替え回路の第１の出力を入力し、
前段の第１の並び替え回路は、２つの入力の他方から、後段の第１の並び替え回路の第２の出力を入力して前記一方の入力からのデータとの並び替えを行い、
前段の第ｉ（ただし、ｉは２〜（Ｓ＋１）／２−１の整数）の並び替え回路は、２つの入力から、後段の第（ｉ−１）の並び替え回路の第１の出力と、後段の第ｉの並び替え回路の第２の出力とを入力して並び替えを行い、
前段の第（Ｓ＋１）／２の並び替え回路は、２つの入力から、後段の第（Ｓ−１）／２の並び替え回路の第１の出力と、後段の保持回路の出力とを入力して並び替えを行い、
後段の（Ｓ−１）／２個の並び替え回路の第１、第２の出力、及び、前記保持回路の出力より、前記入力された複数の選択対象データの中から、値が小さなＳ個のデータが取り出される、ことを特徴とするデータ選択回路。
【請求項３】
２つの入力からそれぞれ入力された２つのデータの大小を判別し、判別結果に基づき、前記入力された２つのデータのうち、大のデータ、小のデータをそれぞれ第１、第２の出力から出力する並び替え回路をＳ個（ただし、Ｓは所定の偶数）有し、このうち、Ｓ／２個の並び替え回路が１つの保持回路とともに、前段に並置され、Ｓ／２個の並び替え回路は、後段に並置され、
前段の第１の並び替え回路において、２つの入力の一方から、選択対象データが順次入力され、第２の出力からのデータは破棄され、
後段の第ｉ（ただし、ｉは１〜Ｓ／２−１の整数）の並び替え回路は、２つの入力から、前段の第ｉの並び替え回路の第１の出力と、前段の（ｉ＋１）の並び替え回路の第２の出力とを入力して並び替えを行い、
後段の第Ｓ／２の並び替え回路は、２つの入力から、前段の第Ｓ／２の並び替え回路の第１の出力と、前記保持回路の出力とを入力して並び替えを行い、
前段の第１の並び替え回路は、２つの入力の他方から、後段の第１の並び替え回路の第２の出力を入力して、前記一方の入力からのデータとの並び替え処理を行い、
前段の第ｉ（ただし、ｉは２〜Ｓ／２の整数）の並び替え回路は、２つの入力から、後段の第（ｉ−１）の並び替え回路の第１の出力と、後段の第ｉの並び替え回路の第２の出力とを入力して並び替え処理を行い、
前記保持回路は、後段の第Ｓ／２の並び替え回路の第１の出力を入力し、
後段のＳ／２個の並び替え回路の第１、第２の出力より、前記入力された複数の選択対象データの中から値が大きなＳ個のデータが取り出される、ことを特徴とするデータ選択回路。
【請求項４】
２つの入力からそれぞれ入力された２つのデータの大小を判別し、判別結果に基づき、前記入力された２つのデータのうち、大のデータ、小のデータをそれぞれ第１、第２の出力から出力する並び替え回路を、少なくとも、選択するデータの個数Ｓ個（ただし、Ｓは所定の奇数）有し、このうち、（Ｓ＋１）／２個の並び替え回路は、前段に並置され、（Ｓ−１）／２個の並び替え回路が、１つの保持回路とともに後段に並置され、
前段の第１の並び替え回路において、２つの入力の一方から、選択対象データが順次入力され、第２の出力からのデータは破棄され、
後段の第ｉ（ただし、ｉは１〜（Ｓ−１）／２の整数）の並び替え回路は、２つの入力から、前段の第ｉの並び替え回路の第１の出力と、前段の（ｉ＋１）の並び替え回路の第２の出力とを入力して並び替えを行い、
前記保持回路は、前段の第（Ｓ＋１）／２の並び替え回路の第１の出力を入力し、
前段の第１の並び替え回路は、２つの入力の他方から、後段の第１の並び替え回路の第２の出力を入力して前記一方の入力からのデータとの並び替えを行い、
前段の第ｉ（ただし、ｉは２〜（Ｓ＋１）／２−１の整数）の並び替え回路は、２つの入力から、後段の第（ｉ−１）の並び替え回路の第１の出力と、後段の第ｉの並び替え回路の第２の出力とを入力して並び替えを行い、
前段の第（Ｓ＋１）／２の並び替え回路は、２つの入力から、後段の第（Ｓ−１）／２の並び替え回路の第１の出力と、後段の保持回路の出力とを入力して並び替えを行い、
後段の（Ｓ−１）／２個の並び替え回路の第１、第２の出力、及び、前記保持回路の出力より、前記入力された複数の選択対象データの中から、値が大きなＳ個のデータが取り出される、ことを特徴とするデータ選択回路。
【請求項５】
前記前段の第１の並び替え回路の前記一方の入力に、選択対象データの入力が行われない場合、前記前段の第１の並び替え回路の前記一方の入力には、所定の値が入力される、ことを特徴とする請求項１乃至４のいずれか一に記載のデータ選択回路。
【請求項６】
前記前段の第１の並び替え回路の前記他方の入力、及び、前記前段の第２乃至第Ｓ／２の並び替え回路の２つの入力は、初期化時に、所定の値が入力される、ことを特徴とする請求項１又は３に記載のデータ選択回路。
【請求項７】
前記前段の第１の並び替え回路の前記他方の入力、及び前記前段の第２乃至第（Ｓ＋１）／２の並び替え回路の２つの入力には、初期化時に、所定の値が入力される、ことを特徴とする請求項２又は４に記載のデータ選択回路。
【請求項８】
前記各並び替え回路が、２つの入力からそれぞれ入力された２つのデータをラッチする保持回路と、
前記２つのデータの大小を判定する判定器と、
前記判定器での判定結果に基づき、前記保持回路に保持されている前記２つのデータの出力先を、大小に応じて、前記第１、第２の出力のいずれにするか選択する選択回路と、
を備え、前記２つのデータの値が等しい場合、前記第１、第２の出力には同一の値が出力される、ことを特徴とする請求項１乃至４のいずれか一に記載のデータ選択回路。
【請求項９】
同期用のクロック信号と同一又は所定倍の周期を単位に、選択対象データが、前記第１の並び替え回路の前記一方の入力に１つずつ順次入力される、ことを特徴とする請求項１乃至４のいずれか一に記載のデータ選択回路。
【請求項１０】
前記前段の第１の並び替え回路の前記一方の入力への、選択対象のＮ個（ただし、Ｎは所定の正整数）のデータの順に入力が終了した次のサイクルから、選択されたＳ個のデータの取り出しが可能とされる、ことを特徴とする請求項１乃至４のいずれか一に記載のデータ選択回路。
【請求項１１】
前記後段のＳ／２個の並び替え回路の第１、第２の出力を入力し、多重化して出力する出力制御回路を備えている、ことを特徴とする請求項１又は３に記載のデータ選択回路。
【請求項１２】
前記後段の（Ｓ−１）／２個の並び替え回路の第１、第２の出力と、前記保持回路の出力を入力し、多重化して出力する出力制御回路を備えている、ことを特徴とする請求項２又は４に記載のデータ選択回路。
【請求項１３】
前記Ｓ／２個の後段の並び替え回路に対応してＳ個のセレクタ回路を備え、
前記後段の各並び替え回路の第１、第２の出力に対応して２つ設けられる前記セレクタ回路のそれぞれは、前記２つの出力の一方と初期設定値と、前記２つの出力の他方と初期設定値とを入力し、それぞれの出力は、対応する前記前段の並び替え回路と前記保持回路の入力に接続され、
前記Ｓ個のセレクタ回路は、初期化時に、初期設定値を選択出力する、ことを特徴とする請求項１又は３に記載のデータ選択回路。
【請求項１４】
前記（Ｓ−１）／２個の後段の並び替え回路に対応して（Ｓ−１）個のセレクタ回路を備え、前記後段の保持回路に対応して１つのセレクタ回路を備え、
前記後段の各並び替え回路の第１、第２の出力に対応して２つ設けられる前記セレクタ回路のそれぞれが前記２つの出力の一方と初期設定値と、前記２つの出力の他方と初期設定値とを入力し、それぞれの出力は、対応する前段の並び替え回路の入力に接続され、
前記１つのセレクタ回路は、前記後段の保持回路の出力を入力し、出力が対応する前記前段の並び替え回路の入力に接続され、
前記Ｓ個のセレクタ回路は、初期化時に初期設定値を選択出力する、ことを特徴とする請求項２又は４に記載のデータ選択回路。
【請求項１５】
前記選択対象データと、所定の初期設定値を入力とし、出力が、前記前段の第１の並び替え回路の前記一方の入力に接続され、入力イネーブル信号を選択制御信号として入力する入力段のセレクタ回路を備え、
前記入力段のセレクタ回路は、前記入力イネーブル信号が入力許可状態のとき、前記選択対象データを選択出力して、前記前段の第１の並び替え回路の前記一方の入力に供給し、前記入力イネーブル信号が入力不許可のとき、前記所定の初期設定値を選択出力して、前記前段の第１の並び替え回路の前記一方の入力に供給する、ことを特徴とする請求項１乃至４のいずれか一に記載のデータ選択回路。
【請求項１６】
前段に並置される、第１乃至第Ｓ／２（ただし、Ｓは所定の正の偶数）の並び替え回路、及び保持回路と、
後段に並置される第１乃至第Ｓ／２の並び替え回路と、
前記後段の並び替え回路の出力に対応して並置される第１乃至第Ｓのセレクタ回路と、
出力制御回路と、
を備え、
前記各並び替え回路は、第１、第２の入力からそれぞれ入力された２つのデータの大小を判別し、判別結果に基づき、前記入力された２つのデータのうち、小のデータ、大のデータをそれぞれ第１、第２の出力から出力し、
後段の第ｉ（ただし、ｉは１〜Ｓ／２−１の整数）並び替え回路は、第１の入力に、前段の第ｉの並び替え回路の第１の出力を入力し、第２の入力に、前段の第（ｉ＋１）の並び替え回路の第２の出力を入力し、
後段の第Ｓ／２の並び替え回路は、第１の入力に、前段の第Ｓ／２の並び替え回路の第１の出力を入力し、第２の入力に、前記保持回路の出力を入力し、
前段の第１の並び替え回路の第２の出力はオープンとされ、
後段の第ｊ（ただし、ｊは１〜Ｓ／２−１の整数）の並び替え回路の第２の出力は、第｛２×（ｊ−１）＋１｝のセレクタ回路の第１の入力に接続され、前記後段の第ｊの並び替え回路の第１の出力は、第２×ｊのセレクタ回路の第１の入力に接続され、
前記第１乃至第Ｓのセレクタ回路の第２の入力には、所定の最大値が入力され、共通に入力される選択信号に基づき、前記セレクタ回路の第１又は第２の入力の一方を選択して出力し、
前記第１のセレクタ回路の出力は、前記前段の第１の並び替え回路の第２の入力に帰還入力され、
第｛２×（ｌ−１）｝（ただし、ｌは２乃至Ｓ／２の整数）のセレクタ回路の出力は、前記前段の第ｌの並び替え回路の第１の入力に帰還入力され、
第｛２×（ｌ−１）＋１｝（ただし、ｌは１乃至Ｓ／２の整数）のセレクタ回路の出力は、前記前段の第ｌの並び替え回路の第２の入力に帰還入力され、
前記第Ｓのセレクタ回路の出力は前記保持回路に帰還入力され、
前記第１乃至第Ｓのセレクタ回路は、選択対象データの先頭を示す選択信号により、第１の入力を選択して出力し、
前記選択対象データ列と所定の最大値とを入力し、出力が前記前段の第１の並び替え回路の第１の入力に接続され、入力イネーブル信号が活性状態のとき、選択対象データ列を出力する入力段セレクタ回路をさらに備え、
前記出力制御回路は、前記後段の第１乃至第Ｓ／２の並び替え回路の第１、第２の出力を入力し、Ｓ個の選択データを多重化して出力する、ことを特徴とするデータ選択回路。
【請求項１７】
前段に並置される第１乃至第（Ｓ＋１）／２（ただし、Ｓは所定の正の奇数）の並び替え回路と、
後段に並置される、第１乃至第（Ｓ−１）／２の並び替え回路、及び保持回路と、
前記後段の第１乃至第（Ｓ−１）／２の並び替え回路、及び前記保持回路に対応して並置される第１乃至第Ｓのセレクタ回路と、
出力制御回路と、
を備え、
前記各並び替え回路は、第１、第２の入力からそれぞれ入力された２つのデータの大小を判別し、判別結果に基づき、前記入力された２つのデータのうち、小のデータ、大のデータをそれぞれ第１、第２の出力から出力し、
後段の第ｉ（ただし、ｉは１〜（Ｓ−１）／２の整数）並び替え回路は、第１の入力に、前段の第ｉの並び替え回路の第１の出力を入力し、第２の入力に、前段の第（ｉ＋１）の並び替え回路の第２の出力を入力し、
後段の前記保持回路は、前段の第（Ｓ＋１）／２の並び替え回路の第１の出力を入力し、
前記前段の第１の並び替え回路の第２の出力はオープンとされ、
後段の第ｊ（ただし、ｊは１〜（Ｓ−１）／２の整数）の並び替え回路の第２の出力は、第｛２×（ｊ−１）＋１｝のセレクタ回路の第１の入力に接続され、前記後段の第ｊの並び替え回路の第１の出力は、第２×ｊのセレクタ回路の第１の入力に接続され、
後段の前記保持回路の出力は、第Ｓのセレクタ回路の第１の入力に接続され、
前記第１乃至第Ｓのセレクタ回路の第２の入力には、所定の最大値が入力され、共通に入力される選択信号に基づき、前記セレクタ回路の第１又は第２の入力の一方を選択して出力し、
前記第１のセレクタ回路の出力は、前段の第１の並び替え回路の第２の入力に入力され、
前記第｛２×（ｌ−１）｝（ただし、ｌは２乃至（Ｓ＋１）／２の整数）のセレクタ回路の出力は、前段の第ｌの並び替え回路の第１の入力に入力され、
前記第｛２×（ｌ−１）＋１｝（ただし、ｌは１乃至（Ｓ＋１）／２の整数）のセレクタ回路の出力は、前段の第ｌの並び替え回路の第２の入力に入力され、
前記第Ｓのセレクタ回路の出力は、前段の第（Ｓ＋１）／２の並び替え回路の第２の入力に入力され、
前記第１乃至第Ｓのセレクタ回路は、選択対象データの先頭を示す選択信号により、第１の入力を選択して出力し、
前記選択対象データ列と所定の最大値とを入力し、出力が前記前段の第１の並び替え回路の第１の入力に接続され、入力イネーブル信号が活性状態のとき、選択対象データ列を出力する入力段セレクタ回路をさらに備え、
前記出力制御回路は、後段の第１乃至第（Ｓ−１）／２の並び替え回路の第１、第２の出力、及び前記保持回路の出力を入力し、Ｓ個の選択データを多重化して出力する、ことを特徴とするデータ選択回路。
【請求項１８】
前段に並置される、第１乃至第Ｓ／２（ただし、Ｓは所定の正の偶数）の並び替え回路、及び保持回路と、
後段に並置される第１乃至第Ｓ／２の並び替え回路と、
前記後段の並び替え回路の出力に対応して並置される第１乃至第Ｓのセレクタ回路と、
出力制御回路と、
を備え、
前記各並び替え回路は、第１、第２の入力からそれぞれ入力された２つのデータの大小を判別し、判別結果に基づき、前記入力された２つのデータのうち、大のデータ、小のデータをそれぞれ第１、第２の出力から出力し、
後段の第ｉ（ただし、ｉは１〜Ｓ／２−１の整数）並び替え回路は、第１の入力に、前段の第ｉの並び替え回路の第１の出力を入力し、第２の入力に、前段の第（ｉ＋１）の並び替え回路の第２の出力を入力し、
後段の第Ｓ／２の並び替え回路は、第１の入力に、前段の第Ｓ／２の並び替え回路の第１の出力を入力し、第２の入力に、前記保持回路の出力を入力し、
前段の第１の並び替え回路の第２の出力はオープンとされ、
後段の第ｊ（ただし、ｊは１〜Ｓ／２−１の整数）の並び替え回路の第２の出力は、第｛２×（ｊ−１）＋１｝のセレクタ回路の第１の入力に接続され、前記後段の第ｊの並び替え回路の第１の出力は、第２×ｊのセレクタ回路の第１の入力に接続され、
前記第１乃至第Ｓのセレクタ回路の第２の入力には、所定の最小値が入力され、共通に入力される選択信号に基づき、前記セレクタ回路の第１又は第２の入力の一方を選択して出力し、
前記第１のセレクタ回路の出力は、前記前段の第１の並び替え回路の第２の入力に帰還入力され、
第｛２×（ｌ−１）｝（ただし、ｌは２乃至Ｓ／２の整数）のセレクタ回路の出力は、前記前段の第ｌの並び替え回路の第１の入力に帰還入力され、
第｛２×（ｌ−１）＋１｝（ただし、ｌは１乃至Ｓ／２の整数）のセレクタ回路の出力は、前記前段の第ｌの並び替え回路の第２の入力に帰還入力され、
前記第Ｓのセレクタ回路の出力は前記保持回路に帰還入力され、
前記第１乃至第Ｓのセレクタ回路は、選択対象データの先頭を示す選択信号により、第１の入力を選択して出力し、
前記選択対象データ列と所定の最小値とを入力し、出力が前記前段の第１の並び替え回路の第１の入力に接続され、入力イネーブル信号が活性状態のとき、選択対象データ列を出力する入力段セレクタ回路をさらに備え、
前記出力制御回路は、前記後段の第１乃至第Ｓ／２の並び替え回路の第１、第２の出力を入力し、Ｓ個の選択データを多重化して出力する、ことを特徴とするデータ選択回路。
【請求項１９】
前段に並置される第１乃至第（Ｓ＋１）／２（ただし、Ｓは所定の正の奇数）の並び替え回路と、
後段に並置される、第１乃至第（Ｓ−１）／２の並び替え回路、及び保持回路と、
前記後段の第１乃至第（Ｓ−１）／２の並び替え回路、及び前記保持回路に対応して並置される第１乃至第Ｓのセレクタ回路と、
出力制御回路と、
を備え、
前記各並び替え回路は、第１、第２の入力からそれぞれ入力された２つのデータの大小を判別し、判別結果に基づき、前記入力された２つのデータのうち、大のデータ、小のデータをそれぞれ第１、第２の出力から出力し、
後段の第ｉ（ただし、ｉは１〜（Ｓ−１）／２の整数）並び替え回路は、第１の入力に、前段の第ｉの並び替え回路の第１の出力を入力し、第２の入力に、前段の第（ｉ＋１）の並び替え回路の第２の出力を入力し、
後段の前記保持回路は、前段の第（Ｓ＋１）／２の並び替え回路の第１の出力を入力し、
前記前段の第１の並び替え回路の第２の出力はオープンとされ、
後段の第ｊ（ただし、ｊは１〜（Ｓ−１）／２の整数）の並び替え回路の第２の出力は、第｛２×（ｊ−１）＋１｝のセレクタ回路の第１の入力に接続され、前記後段の第ｊの並び替え回路の第１の出力は、第２×ｊのセレクタ回路の第１の入力に接続され、
後段の前記保持回路の出力は、第Ｓのセレクタ回路の第１の入力に接続され、
前記第１乃至第Ｓのセレクタ回路の第２の入力には、所定の最小値が入力され、共通に入力される選択信号に基づき、前記セレクタ回路の第１又は第２の入力の一方を選択して出力し、
前記第１のセレクタ回路の出力は、前段の第１の並び替え回路の第２の入力に入力され、
前記第｛２×（ｌ−１）｝（ただし、ｌは２乃至（Ｓ＋１）／２の整数）のセレクタ回路の出力は、前段の第ｌの並び替え回路の第１の入力に入力され、
前記第｛２×（ｌ−１）＋１｝（ただし、ｌは１乃至（Ｓ＋１）／２の整数）のセレクタ回路の出力は、前段の第ｌの並び替え回路の第２の入力に入力され、
前記第Ｓのセレクタ回路の出力は、前段の第（Ｓ＋１）／２の並び替え回路の第２の入力に入力され、
前記第１乃至第Ｓのセレクタ回路は、選択対象データの先頭を示す選択信号により、第１の入力を選択して出力し、
前記選択対象データ列と所定の最小値とを入力し、出力が前記前段の第１の並び替え回路の第１の入力に接続され、入力イネーブル信号が活性状態のとき、選択対象データ列を出力する入力段セレクタ回路をさらに備え、
前記出力制御回路は、後段の第１乃至第（Ｓ−１）／２の並び替え回路の第１、第２の出力、及び前記保持回路の出力を入力し、Ｓ個の選択データを多重化して出力する、ことを特徴とするデータ選択回路。
【請求項２０】
前記各並び替え回路が、前記第１、第２の入力からそれぞれ入力された２つのデータをラッチする保持回路と、
前記２つのデータを減算する減算器と、
前記２つのデータの減算結果から大小関係を判定する判定器と、
前記判定器での判定結果に基づき、前記保持回路に保持されている前記２つのデータを、大小に応じて、前記第１、第２の出力のうちいずれに出力するか出力先を選択する選択回路と、
を備え、前記２つのデータが同一値のとき、前記第１、第２の出力から同一値のデータが出力される、ことを特徴とする請求項１６乃至１９のいずれか一に記載のデータ選択回路。
【請求項２１】
前記出力制御回路は、出力の許可、不許可を制御する制御信号に基づき、選択データの出力を行う、ことを特徴とする請求項１６乃至１９のいずれか一に記載のデータ選択回路。
【請求項２２】
前記出力制御回路は、出力端子から出力するデータが有効であるか無効であるかを示す制御信号を制御信号出力端子から出力する、ことを特徴とする請求項１６乃至１９のいずれか一に記載のデータ選択回路。
【請求項２３】
前記前段の第１の並び替え回路の前記第１の入力へＮ個（ただし、Ｎは所定の正整数）の選択対象のデータが入力された次のクロックサイクルから、前記出力制御回路より、選択されたＳ個のデータが順次出力される、ことを特徴とする請求項１６乃至１９のいずれか一に記載のデータ選択回路。
【請求項２４】
請求項１乃至２３のいずれか一に記載のデータ選択回路を備えた電子装置。
【請求項２５】
請求項１乃至２３のいずれか一に記載のデータ選択回路を備えた携帯端末装置。
【請求項２６】
２つの入力からそれぞれ入力された２つのデータの大小を判別し、判別結果に基づき、入力された２つのデータのうち小のデータ、大のデータをそれぞれ第１、第２の出力から出力する、Ｓ個（ただし、Ｓは所定の偶数）の並び替え回路のうち、Ｓ／２個の並び替え回路を１つの保持回路とともに前段に並置し、Ｓ／２個の並び替え回路を後段に並置してなる装置によりデータ選択を行う方法であって、
（ａ）選択対象データの入力にあたり、前記前段のＳ／２個の並び替え回路と前記保持回路が初期化される工程と、
（ｂ）前段の第１の並び替え回路の２つの入力の一方に、選択対象データが順次入力されて、並び替えが行われ、前段の第１の並び替え回路の第２の出力から出力されるデータは破棄される工程と、
（ｃ）後段の第ｉ（ただし、ｉは１〜Ｓ／２−１の整数）の並び替え回路は、その２つの入力から、前段の第ｉの並び替え回路の第１の出力と、前段の（ｉ＋１）の並び替え回路の第２の出力とを入力して並び替えを行い、
後段の第Ｓ／２の並び替え回路では、その２つの入力から、前段の第Ｓ／２の並び替え回路の第１の出力と、前記保持回路の出力とを入力して並び替えを行う工程と、
（ｄ）前段の第１の並び替え回路は、２つの入力の他方から、後段の第１の並び替え回路の第２の出力を入力し、前記一方からのデータとの並び替えを行い、
前段の第ｉ（ただし、ｉは２〜Ｓ／２の整数）の並び替え回路では、その２つの入力から、後段の第（ｉ−１）の並び替え回路の第１の出力と、後段の第ｉの並び替え回路の第２の出力とを入力して並び替えを行い、
前記保持回路は、後段の第Ｓ／２の並び替え回路の第１の出力を入力してサンプル出力する工程と、
（ｅ）後段のＳ／２個の並び替え回路の第１、第２の出力より、前記入力された選択対象データの中から、値が小さなＳ個のデータが取り出される工程と、
を含む、ことを特徴とするデータ選択方法。
【請求項２７】
２つの入力からそれぞれ入力された２つのデータの大小を判別し、判別結果に基づき、入力された２つのデータのうち小のデータ、大のデータをそれぞれ第１、第２の出力から出力する、Ｓ個（ただし、Ｓは所定の奇数）の並び替え回路のうち、（Ｓ＋１）／２個の並び替え回路を前段に並置し、（Ｓ−１）／２個の並び替え回路と１つの保持回路とを後段に並置してなる装置によりデータ選択を行う方法であって、
（ａ）選択対象データの入力にあたり、前記前段の（Ｓ＋１）／２個の並び替え回路が初期化される工程と、
（ｂ）前段の第１の並び替え回路の２つの入力の一方に、選択対象データが順次入力されて並び替えが行われ、前段の第１の並び替え回路の第２の出力から出力されるデータは破棄される工程と、
（ｃ）後段の第ｉ（ただし、ｉは１〜（Ｓ−１）／２の整数）の並び替え回路は、その２つの入力から、前段の第ｉの並び替え回路の第１の出力と、前段の（ｉ＋１）の並び替え回路の第２の出力とを入力して並び替えを行い、
前記保持回路は、前段の第（Ｓ＋１）／２の並び替え回路の第１の出力を入力してサンプル出力する工程と、
（ｄ）前段の第１の並び替え回路は、２つの入力の他方から、後段の第１の並び替え回路の第２の出力を入力し、前記一方の入力からのデータとの並び替えを行い、
前段の第ｉ（ただし、ｉは２〜（Ｓ＋１）／２−１の整数）の並び替え回路では、その２つの入力から、後段の第（ｉ−１）の並び替え回路の第１の出力と、後段の第ｉの並び替え回路の第２の出力とを入力して並び替えを行い、
前段の第（Ｓ＋１）／２の並び替え回路では、その２つの入力から、後段の第（Ｓ−１）／２の並び替え回路の第１の出力と、後段の保持回路の出力とを入力して並び替えを行う工程と、
（ｅ）後段の（Ｓ−１）／２個の並び替え回路の第１、第２の出力、及び前記保持回路の出力より、前記入力された選択対象データの中から、値が小さなＳ個のデータが取り出される工程と、
を含む、ことを特徴とするデータ選択方法。
【請求項２８】
２つの入力からそれぞれ入力された２つのデータの大小を判別し、判別結果に基づき、入力された２つのデータのうち大のデータ、小のデータをそれぞれ第１、第２の出力から出力する、Ｓ個（ただし、Ｓは所定の偶数）の並び替え回路のうち、Ｓ／２個の並び替え回路を１つの保持回路とともに前段に並置し、Ｓ／２個の並び替え回路を後段に並置してなる装置によるデータ選択方法であって、
（ａ）選択対象データの入力にあたり、前記前段のＳ／２個の並び替え回路と前記保持回路が初期化される工程と、
（ｂ）前段の第１の並び替え回路の２つの入力の一方から、選択対象データが順次入力されて、並び替えが行われ、前段の第１の並び替え回路の第２の出力から出力されるデータは破棄される工程と、
（ｃ）後段の第ｉ（ただし、ｉは１〜Ｓ／２−１の整数）の並び替え回路は、その２つの入力から、前段の第ｉの並び替え回路の第１の出力と、前段の（ｉ＋１）の並び替え回路の第２の出力とを入力して並び替えを行い、
後段の第Ｓ／２の並び替え回路では、その２つの入力から、前段の第Ｓ／２の並び替え回路の第１の出力と、前記保持回路の出力とを入力して並び替えを行う工程と、
（ｄ）前段の第１の並び替え回路は、２つの入力の他方から、後段の第１の並び替え回路の第２の出力を入力し、前記一方の入力からのデータとの並び替えを行い、
前段の第ｉ（ただし、ｉは２〜Ｓ／２の整数）の並び替え回路では、その２つの入力から、後段の第（ｉ−１）の並び替え回路の第１の出力と、後段の第ｉの並び替え回路の第２の出力とを入力して並び替えを行い、
前記保持回路は、後段の第Ｓ／２の並び替え回路の第１の出力を入力してサンプル出力する工程と、
（ｅ）後段のＳ／２個の並び替え回路の第１、第２の出力より、前記入力された選択対象データの中から、値が大きなＳ個のデータが取り出される工程と、
を含む、ことを特徴とするデータ選択方法。
【請求項２９】
２つの入力からそれぞれ入力された２つのデータの大小を判別し、判別結果に基づき、入力された２つのデータのうち大のデータ、小のデータをそれぞれ第１、第２の出力から出力する、Ｓ個（ただし、Ｓは所定の奇数）の並び替え回路のうち、（Ｓ＋１）／２個の並び替え回路を前段に並置し、（Ｓ−１）／２個の並び替え回路と１つの保持回路を後段に並置してなる装置によりデータ選択を行う方法であって、
（ａ）選択対象データの入力にあたり、前記前段の（Ｓ＋１）／２個の並び替え回路が初期化される工程と、
（ｂ）前段の第１の並び替え回路の２つの入力の一方から、選択対象データが順次入力されて並び替えが行われ、前段の第１の並び替え回路の第２の出力から出力されるデータは破棄される工程と、
（ｃ）後段の第ｉ（ただし、ｉは１〜（Ｓ−１）／２の整数）の並び替え回路は、その２つの入力から、前段の第ｉの並び替え回路の第１の出力と、前段の（ｉ＋１）の並び替え回路の第２の出力とを入力して並び替えを行い、
前記保持回路は、前段の第（Ｓ＋１）／２の並び替え回路の第１の出力を入力してサンプル出力する工程と、
（ｄ）前段の第１の並び替え回路は、２つの入力の他方から、後段の第１の並び替え回路の第２の出力を入力し、前記一方の入力からのデータとの並び替えを行い、
前段の第ｉ（ただし、ｉは２〜（Ｓ＋１）／２−１の整数）の並び替え回路では、その２つの入力から、後段の第（ｉ−１）の並び替え回路の第１の出力と、後段の第ｉの並び替え回路の第２の出力とを入力して並び替えを行い、
前段の第（Ｓ＋１）／２の並び替え回路では、その２つの入力から、後段の第（Ｓ−１）／２の並び替え回路の第１の出力と、後段の保持回路の出力とを入力して並び替えを行う工程と、
（ｅ）後段の（Ｓ−１）／２個の並び替え回路の第１、第２の出力、及び前記保持回路の出力より、前記入力された選択対象データの中から、値が大きなＳ個のデータが取り出される工程と、
を含む、ことを特徴とするデータ選択方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの選択処理技術に関し、特に、複数の選択対象データの中から小さいデータを選択する処理において、選択対象データの大小を比較、並び替えを行って所定数の小さいデータを出力する処理回路及び方法に関する。
【背景技術】
【０００２】
従来、この種の選択処理は、一般的に、プログラム制御で動作するコンピュータ（ノイマン型コンピュータ等）によるソフトウェアで逐次的に処理されている。ソフトウェア処理の一例として、先行の選択対象データ群から選択された中間結果の中で最大値を探索し、最大値と選択対象データの大小比較を行い、選択対象データの方が小さければ最大値を更新するという処理を、最終データまで反復するものがある。
【０００３】
近時、情報通信のニーズの増大に伴い、動画像配信やビット当りの単価の低減要求等によって、より高速な情報レートを処理する装置の実現が求められている。
【０００４】
ソフトウェアによる選択処理では、コンピュータの演算処理装置上で、多数の比較、分岐命令を順を追って実行するため、一定時間内に、処理できるデータ量が制限される。
【０００５】
図８は、データ処理装置（コンピュータ、プロセッサ、ＣＰＵともいう）で実行されるソフトウェア（プログラム）による処理方法の典型例の１つを示すフローチャートである。この選択処理は、入力される８個の選択対象データＤＡＴＡ[１]〜ＤＡＴＡ[８]の中から、４個の値の小さいデータを選択して出力するものである。
【０００６】
ステップＡ１では、選択対象データポインタｉを１に初期化し、ステップＡ２では、最大選択データポインタｓを１に初期化し、ステップＡ３では、選択データＳＥＬ［１］〜ＳＥＬ［４］の初期化を実行する。ＳＥＬ［１］〜ＳＥＬ［４］には、４ビットバイナリで"１１１１"（ヘキサデシマル表示でＦ）が初期値として設定される。
【０００７】
ステップＡ１０にて、最大選択データＳＥＬ［ｓ］と、選択対象データＤＡＴＡ[ｉ]の比較を行う。ステップＡ１０の判定において、選択対象データＤＡＴＡ[ｉ]の方が小さければ、ステップＡ１１にて、選択対象データＤＡＴＡ[ｉ]を最大選択データＳＥＬ［ｓ］へ転送した後、ステップＡ１２を実行する。一方、ステップＡ１０の判定において、選択対象データＳＥＬ［ｓ］の方が選択対象データＤＡＴＡ[ｉ]より小さくない場合、ステップＡ１１を実行せずに、ステップＡ１２を実行する。
【０００８】
ステップＡ１２では、選択対象データポインタｉが８に等しいか否か、すなわち、選択対象データが終了したか判定し、選択対象データポインタｉが８に等しい場合（選択対象データが終了している場合）、処理を終了する。ステップＡ１２で、選択対象データが終了していない場合、選択対象データポインタｉを１つ加算（インクリメント）し、続いてステップＡ４、Ａ５を実行する。
【０００９】
ステップＡ４では、最大選択データポインタｓを１に初期化し、ステップＡ５では、選択データポインタｎを２に初期化し、ステップＡ６にて、最大選択データＳＥＬ［ｎ］と選択データＳＥＬ［ｓ］の比較を行う。
【００１０】
ステップＡ６の判定で、最大選択データＳＥＬ［ｎ］が選択データＳＥＬ［ｓ］より大きい場合、ステップＡ７において、選択データポインタｎを最大選択データポインタｓへ転送したあと、ステップＡ８に移行する。ステップＡ６の判定で、最大選択データＳＥＬ［ｎ］が選択データＳＥＬ［ｓ］より大きくない場合、ステップＡ７は実行せずに、ステップＡ８の処理を実行する。
【００１１】
ステップＡ８では、選択データポインタｎが４に等しいか否か、すなわち、最大選択データの探索が終了したか否か判定し、終了していなければ、選択データポインタｎを１つ加算して、ステップＡ６の処理を実行する。ステップＡ８で、選択データポインタｎがｎ＝４の場合、ステップＡ１０の処理を実行する。
【００１２】
上記の通り、先行の選択対象データ群から選択された中間結果の中で最大値を探索し、最大値と選択対象データとの比較を行い、選択対象データの方が小さい場合に最大選択データを更新するという処理を最終データまで反復する。このように、ソフトウェアによる選択処理では、多数の処理を順を追って繰り返し実行するため、時間内に処理できるデータ量が制限される。
【００１３】
以下では、選択対象データ数Ｎ＝２１６、小さいデータの選択データ数Ｓ＝２８として、図８のフローチャートに従って実行されるソフトウェアによる選択処理に要する処理時間について説明する。
【００１４】
機械語命令種類を、転送命令（図８のＡ１〜Ａ５、Ａ７、Ａ１１）、算術演算命令（図８のＡ９、Ａ１３）、比較演算命令（図８のＡ６、Ａ８、Ａ１０、Ａ１２）、分岐命令（図８のＡ６、Ａ８、Ａ１０、Ａ１２）の４項目に大別したときの命令実行回数の概算を図９に示す。
【００１５】
プロセッサの処理能力を定量的に示したＭＩＰＳ（Million Instruction Per Second）値を５７６０ＭＩＰＳとし、プロセッサの使用率を７０％、オペレーティングシステムのオーバーヘッドを考慮せずに、平均処理時間を計算すると、約２２．９０ｍｓｅｃとなる。約２２．９０ｍｓｅｃの導出過程を、図９に示した命令種別毎の実行回数と関連して以下に説明する。
【００１６】
（Ａ）転送命令
平均転送命令数＝Ｓ（２Ｎ−Ｓ＋７）／４＋２Ｎ−１／２
＝２８×（２×２１６−２８＋７）／４＋２×２１６−１／２
≒８５０３７４４回
【００１７】
（Ｂ）算術演算命令
算術演算命令数＝Ｎ（Ｓ−１）−Ｓ＋１＝２１６×（２８−１）−２８＋１
＝１６７１１４２５回
【００１８】
（Ｃ）比較演算命令
比較演算命令数＝２{Ｓ（Ｎ−１）＋１}＝２×（２８×（２１６−１）＋１）
＝３３５５３９２２回
【００１９】
（Ｄ）分岐命令
分岐命令数＝２{Ｓ（Ｎ−１）＋１}＝２×（２８×（２１６−１）＋１）
＝３３５５３９２２回
【００２０】
平均合計命令数は、上記（Ａ）乃至（Ｄ）の命令数の総和で与えられる。
平均合計命令数＝８５０３７４４＋１６７１１４２５＋３３５５３９２２＋３３５５３９２２＝９２３２３０１３回
【００２１】
平均処理時間＝平均合計命令数／（ＭＩＰＳ×１０６×プロセッサの使用率）
＝９２３２３０１３／（５７６０×１０６×０．７０）
＝０．０２２８９８ｓｅｃ
≒２２．９０ｍｓｅｃ
【００２２】
一方、選択処理を、ハードウェア回路で実現する例として、ソート回路を用いる手法が知られている。すなわち、Ｎ個の選択対象データをソート回路によって小さい順にデータを並び替え、その中から小さいデータＳ個を取得する。ソート回路としては、入力データを大小比較するデータ比較器と比較結果を用いてデータを大小に並び替えるデータ選択器を構成要素とする基本セルをパイプライン状に結合して形成した回路が知られている（後記特許文献１参照）。この特許文献１には、入力データの大小を比較して第１の選択信号を出力するデータ比較器と、第１の選択信号に基づいて入力データを大小に並び替えるデータ選択器を組み合わせた基本セルを有し、入力データの全比較数と同一の数、該基本セルをパイプライン上に結合した構成のソート処理装置が開示されている。例えば８つの入力に対してソートを行うための回路として、２つのデータを２つの入力に入力して比較し大小に応じて二つの出力から出力する基本セルを４つ並列に配置し、４つの基本セルの後段に基本セルを３つ配置してなる基本ブロックを４段備えて構成される。
【００２３】
なお、ソート回路に関する刊行物として、入力するデータ数や選出するデータ数が多くなればなるほど、導出に要するサイクル数が増加し、処理時間も長くなるという問題の解消を図るソーティング回路も知られている（例えば後記特許文献２）。この特許文献２においては、レジスタとレジスタファイルのデータを比較する比較器を１つ設けた構成とされている。また、ＣＰＵにおけるソーティング処理において、条件分岐命令を不要とし、パイプライン処理の乱れが発生せず高速化を図るようにした構成も知られている（例えば後記特許文献３）。
【００２４】
【特許文献１】特開２００２−２２９７７２号公報（第４、第５頁、第１図）
【特許文献１】特開平９−３０５３７９号公報（第３、第４頁、第１図）
【特許文献１】特開平３−２８６３３２号公報（第５頁、第１図）
【発明の開示】
【発明が解決しようとする課題】
【００２５】
上記の如く、ソフトウエアによる選択処理では、多数の処理を、順を追って、繰り返し実行するため、時間内に処理できるデータ量が制限される、という問題がある。
【００２６】
また、上記特許文献１のように、ソート回路を用いて選択処理を実現しようとすると、ハードウェアの規模が大きくなる、という問題点を有している。この点について、以下に検討してみる。
【００２７】
上記特許文献１の回路のデータ比較器の総数とデータ選択器の総数は、下記の式（１）、（２）で与えられる。
【００２８】
データ比較器総数＝Ｎ（Ｎ−１）／２      …(1)
データ選択器総数＝Ｎ（Ｎ−１）          …(2)
【００２９】
ここで、選択対象データ数Ｎ＝２８とすると、ソート回路のデータ比較器総数と、データ選択器総数は、それぞれ下記（３）、（４）となる。
【００３０】
データ比較器総数＝２８×（２８−１）／２＝３２６４０個          …(3)
データ選択器総数＝２８×（２８−１）＝６５２８０個              …(4)
【００３１】
上式（１）、（２）からも明らかなように、ソート回路の回路規模は、選択対象データ数Ｎに依存しており（Ｎの２乗に依存する）、選択対象データ数が増加するにしたがって、回路規模の増大が顕著になる、という問題がある。
【００３２】
携帯電話端末などの、携帯通信機器は、実装上の空間が限られており、回路規模を縮小し、消費電力を低減した構成が求められる。
【００３３】
ハードウェアのソート回路を用いた選択処理では、特に、選択対象データ数が増大すると回路規模が増大して実装が困難になる、という問題がある。
【００３４】
したがって、本発明は、複数の選択対象データの中から所定個数のデータを取り出すにあたり、高速化を実現するとともに、回路規模の増大を抑止するデータ選択回路及びデータ選択方法を提供することにある。
【課題を解決するための手段】
【００３５】
本願で開示される発明は、上記目的を達成するため、概ね、以下のように構成される。
【００３６】
本発明の第１の側面（アスペクト）に係る回路は、２つの入力からそれぞれ入力された２つのデータの大小を判別し、判別結果に基づき、前記入力された２つのデータのうち、小のデータ、大のデータをそれぞれ第１、第２の出力から出力する並び替え回路をＳ個（ただし、Ｓは所定の偶数）有し、このうち、Ｓ／２個の並び替え回路が１つの保持回路とともに、前段に並置され、Ｓ／２個の並び替え回路は、後段に並置され、前段の第１の並び替え回路において、２つの入力の一方から、選択対象データが順次入力され、第２の出力からのデータは破棄され、後段の第ｉ（ただし、ｉは１〜Ｓ／２−１の整数）の並び替え回路は、２つの入力から、前段の第ｉの並び替え回路の第１の出力と、前段の（ｉ＋１）の並び替え回路の第２の出力とを入力して並び替えを行い、後段の第Ｓ／２の並び替え回路は、２つの入力から、前段の第Ｓ／２の並び替え回路の第１の出力と、前記保持回路の出力とを入力して並び替えを行い、前段の第１の並び替え回路は、２つの入力の他方から、後段の第１の並び替え回路の第２の出力を入力して、前記一方の入力からのデータとの並び替え処理を行い、前段の第ｉ（ただし、ｉは２〜Ｓ／２の整数）の並び替え回路は、２つの入力から、後段の第（ｉ−１）の並び替え回路の第１の出力と、後段の第ｉの並び替え回路の第２の出力とを入力して並び替え処理を行い、前記保持回路は、後段の第Ｓ／２の並び替え回路の第１の出力を入力し、後段のＳ／２個の並び替え回路の第１、第２の出力より、前記入力された複数の選択対象データの中から値が小さなＳ個のデータが取り出される。
【００３７】
本発明の第２のアスペクトに係る回路は、２つの入力からそれぞれ入力された２つのデータの大小を判別し、判別結果に基づき、前記入力された２つのデータのうち、小のデータ、大のデータをそれぞれ第１、第２の出力から出力する並び替え回路を、少なくとも、選択するデータの個数Ｓ個（ただし、Ｓは所定の奇数）有し、このうち、（Ｓ＋１）／２個の並び替え回路は、前段に並置され、（Ｓ−１）／２個の並び替え回路が、１つの保持回路とともに後段に並置され、前段の第１の並び替え回路において、２つの入力の一方から、選択対象データが順次入力され、第２の出力からのデータは破棄され、後段の第ｉ（ただし、ｉは１〜（Ｓ−１）／２の整数）の並び替え回路は、２つの入力から、前段の第ｉの並び替え回路の第１の出力と、前段の（ｉ＋１）の並び替え回路の第２の出力とを入力して並び替えを行い、前記保持回路は、前段の第（Ｓ＋１）／２の並び替え回路の第１の出力を入力し、前段の第１の並び替え回路は、２つの入力の他方から、後段の第１の並び替え回路の第２の出力を入力して前記一方の入力からのデータとの並び替えを行い、
前段の第ｉ（ただし、ｉは２〜（Ｓ＋１）／２−１の整数）の並び替え回路は、２つの入力から、後段の第（ｉ−１）の並び替え回路の第１の出力と、後段の第ｉの並び替え回路の第２の出力とを入力して並び替えを行い、前段の第（Ｓ＋１）／２の並び替え回路は、２つの入力から、後段の第（Ｓ−１）／２の並び替え回路の第１の出力と、後段の保持回路の出力とを入力して並び替えを行い、後段の（Ｓ−１）／２個の並び替え回路の第１、第２の出力、及び、前記保持回路の出力より、前記入力された複数の選択対象データの中から、値が小さなＳ個のデータが取り出される。
【００３８】
本発明の第３のアスペクトに係る回路は、上記第１のアスペクトに係る回路の並び替え回路を、２つの入力から入力されたデータのどちらが大きか判別し大きい方と小さい方をそれぞれ第１、第２の出力から出力する構成とし、後段のＳ／２個の並び替え回路の第１、第２の出力からは、前記入力された選択対象データの中から値が大きなＳ個のデータが選択される構成としたものである。
【００３９】
本発明の第４のアスペクトに係る回路は、上記第２のアスペクトに係る回路の並び替え回路を、２つの入力から入力されたデータのどちらが大きか判別し大きい方と小さい方をそれぞれ第１、第２の出力から出力する構成とし、後段の（Ｓ−１）／２個（ただし、Ｓは奇数）の並び替え回路の第１、第２の出力及び前記保持回路の出力からは、入力された選択対象データの中から、値が大きなＳ個のデータが選択される構成としたものである。
【００４０】
本発明に係る方法は、第１のアスペクトによれば、２つの入力からそれぞれ入力された２つのデータの大小を判別し、判別結果に基づき、入力された２つのデータのうち小のデータ、大のデータをそれぞれ第１、第２の出力から出力する、Ｓ個（ただし、Ｓは所定の偶数）の並び替え回路のうち、Ｓ／２個の並び替え回路を１つの保持回路とともに前段に並置し、Ｓ／２個の並び替え回路を後段に並置してなる処理装置によりデータ選択を行う方法であって、
（ａ）選択対象データの入力にあたり、前記前段のＳ／２個の並び替え回路と前記保持回路が初期化される工程と、
（ｂ）前段の第１の並び替え回路の２つの入力の一方に、選択対象データが順次入力されて、並び替えが行われ、前段の第１の並び替え回路の第２の出力から出力されるデータは破棄される工程と、
（ｃ）後段の第ｉ（ただし、ｉは１〜Ｓ／２−１の整数）の並び替え回路は、その２つの入力から、前段の第ｉの並び替え回路の第１の出力と、前段の（ｉ＋１）の並び替え回路の第２の出力とを入力して並び替えを行い、
後段の第Ｓ／２の並び替え回路では、その２つの入力から、前段の第Ｓ／２の並び替え回路の第１の出力と、前記保持回路の出力とを入力して並び替えを行う工程と、
（ｄ）前段の第１の並び替え回路は、２つの入力の他方から、後段の第１の並び替え回路の第２の出力を入力し、前記一方からのデータとの並び替えを行い、
前段の第ｉ（ただし、ｉは２〜Ｓ／２の整数）の並び替え回路では、その２つの入力から、後段の第（ｉ−１）の並び替え回路の第１の出力と、後段の第ｉの並び替え回路の第２の出力とを入力して並び替えを行い、
前記保持回路は、後段の第Ｓ／２の並び替え回路の第１の出力を入力してサンプル出力する工程と、
（ｅ）後段のＳ／２個の並び替え回路の第１、第２の出力より、前記入力された選択対象データの中から、値が小さなＳ個のデータが取り出される工程と、を含む。
【００４１】
本発明に係る方法は、第２のアスペクトによれば、２つの入力からそれぞれ入力された２つのデータの大小を判別し、判別結果に基づき、入力された２つのデータのうち小のデータ、大のデータをそれぞれ第１、第２の出力から出力する、Ｓ個（ただし、Ｓは所定の奇数）の並び替え回路のうち、（Ｓ＋１）／２個の並び替え回路を前段に並置し、（Ｓ−１）／２個の並び替え回路と１つの保持回路とを後段に並置してなる処理装置によりデータ選択を行う方法であって、
（ａ）選択対象データの入力にあたり、前記前段の（Ｓ＋１）／２個の並び替え回路が初期化される工程と、
（ｂ）前段の第１の並び替え回路の２つの入力の一方に、選択対象データが順次入力されて並び替えが行われ、前段の第１の並び替え回路の第２の出力から出力されるデータは破棄される工程と、
（ｃ）後段の第ｉ（ただし、ｉは１〜（Ｓ−１）／２の整数）の並び替え回路は、その２つの入力から、前段の第ｉの並び替え回路の第１の出力と、前段の（ｉ＋１）の並び替え回路の第２の出力とを入力して並び替えを行い、
前記保持回路は、前段の第（Ｓ＋１）／２の並び替え回路の第１の出力を入力してサンプル出力する工程と、
（ｄ）前段の第１の並び替え回路は、２つの入力の他方から、後段の第１の並び替え回路の第２の出力を入力し、前記一方の入力からのデータとの並び替えを行い、
前段の第ｉ（ただし、ｉは２〜（Ｓ＋１）／２−１の整数）の並び替え回路では、その２つの入力から、後段の第（ｉ−１）の並び替え回路の第１の出力と、後段の第ｉの並び替え回路の第２の出力とを入力して並び替えを行い、
前段の第（Ｓ＋１）／２の並び替え回路では、その２つの入力から、後段の第（Ｓ−１）／２の並び替え回路の第１の出力と、後段の保持回路の出力とを入力して並び替えを行う工程と、
（ｅ）後段の（Ｓ−１）／２個の並び替え回路の第１、第２の出力、及び前記保持回路の出力より、前記入力された選択対象データの中から、値が小さなＳ個のデータが取り出される工程と、を含む。
【００４２】
本発明に係る方法は、第３のアスペクトによれば、上記第１のアスペクトに係る方法において、前記並び替え回路を、２つの入力から入力されたデータのどちらが大きか判別し大きい方と小さい方をそれぞれ第１、第２の出力から出力する構成とし、後段のＳ／２個の並び替え回路の第１、第２の出力からは、前記入力された選択対象データの中から値が大きなＳ個のデータが選択される構成としたものである。
【００４３】
本発明に係る方法は、第４のアスペクトによれば、上記第２のアスペクトに係る方法において、前記並び替え回路を、２つの入力から入力されたデータのどちらが大きか判別し大きい方と小さい方をそれぞれ第１、第２の出力から出力する構成とし、後段の（Ｓ−１）／２個（ただし、Ｓは奇数）の並び替え回路の第１、第２の出力及び前記保持回路の出力からは、入力された選択対象データの中から、値が大きなＳ個のデータが選択される構成としたものである。
【発明の効果】
【００４４】
本発明によれば、選択データ数に関わらず、逐次処理せずに、並び替え回路により並列処理する構成としたことで、データ選択処理の特段の高速化を実現することができる。
【００４５】
また、本発明によれば、回路規模が、選択対象データの数に依存しない構成とされていることから、選択対象データ数が増大しても、回路規模を抑えた構成で、選択処理を行うことができる。このため、本発明によれば、回路面積、チップ面積の縮減、消費電流の低減を可能としており、省スペース化が要求される携帯型の情報処理装置に適用して好適とされる。
【発明を実施するための最良の形態】
【００４６】
本発明をさらに詳細に説述すべく添付図面を参照してこれを説明する。まず、本発明の回路の動作原理を説明し、つづいて実施例について説明する。本発明に係る回路は、ｋビット幅（ｋは所定の正整数）の１組の入力信号に時分割多重されたＮ個（Ｎは所定の正整数）のデータの中から、順序を問わずにＳ個（Ｓは所定の正整数）の値の小さいデータを、ｋビット幅の１組の出力信号に、時分割多重出力するものである。
【００４７】
図１において、前段（第１段）のＳ／２個（ここでは、Ｓは所定の偶数）の並び替え回路１−１〜１−Ｓ／２、及び保持回路４−１を備え、後段（第２段）のＳ／２個の並び替え回路２−１〜２−Ｓ／２とを備えている。前段のＳ／２個（ただし、Ｓは偶数）の並び替え回路１−１〜１−Ｓ／２、後段のＳ／２個の並び替え回路２−１〜２−Ｓ／２は、第１、第２の入力に入力された２つのデータのうち小さい方のデータを第１の出力、大きい方のデータを第２の出力から出力する。
【００４８】
前段の第１の並び替え回路１−１において、第１の入力から、選択対象データが順次入力され、選択対象データと、第２の入力からのデータとの並び替えが行われ、前段の第１の並び替え回路１−１の第２の出力（大）からのデータは破棄される。後段の並び替え回路２−１〜２−Ｓ／２の並び替え処理後のＳ個の出力は、セレクタ回路３−１〜３−Ｓを介して、前段の並び替え回路１−１の第２の入力から、並び替え回路１−Ｓ／２の第１、第２の入力、及び保持回路４−１の入力に帰還入力される。
【００４９】
後段の第ｉ（ただし、ｉは１〜Ｓ／２−１の整数）の並び替え回路２−ｉは、その第１、第２の入力から、前段の第ｉの並び替え回路１−ｉの第１の出力（小）と前段の（ｉ＋１）の並び替え回路１−（ｉ＋１）の第２の出力（大）とを入力して並び替えを行い、後段の第Ｓ／２の並び替え回路２−Ｓ／２は、その第１、第２の入力から、前段の第Ｓ／２の並び替え回路１−Ｓ／２の第１の出力（小）と、前段の保持回路４−１の出力とを入力して並び替えを行う。後段のＳ／２個の並び替え回路２−１〜２−Ｓ／２の並び替え、及び第１、第２の出力からのデータの出力は、並列に行われる。
【００５０】
前段の第１の並び替え回路１−１は、選択処理の開始時に第２の入力が初期化された後、第２の入力から、後段の第１の並び替え回路２−１の第２の出力を入力し、第１の入力のデータとの並び替えを行う。前段の第ｉ（ただし、ｉは２〜Ｓ／２の整数）の並び替え回路１−ｉは、後段の第（ｉ−１）の並び替え回路２−（ｉ−１）の第１の出力と、後段の第ｉの並び替え回路２−ｉの第２の出力とを入力して並び替えを行う。保持回路（フリップフロップ）４−１は、後段の第Ｓ／２の並び替え回路２−Ｓ／２の第１の出力を入力してサンプル出力する。前段のＳ／２個の並び替え回路１−１〜１−Ｓ／２の並び替え及び第１、第２の出力からのデータの出力と、保持回路４−１からのデータの出力は、並列に行われる。
【００５１】
入力された複数の選択対象データに対して、後段のＳ／２個の並び替え回路２−１〜２−Ｓ／２の第１、第２の出力からは、値が小さなＳ個のデータが出力され、さらに選択対象データが、前段の第１の並び替え回路１−１の第１の入力に入力された選択対象データが、後段のＳ／２個の並び替え回路２−１〜２−Ｓ／２の第１、第２の出力のデータよりも大である場合には、並び替え処理の結果、前段の第１の並び替え回路１−１の第２の出力から該選択対象データは破棄される。後段のＳ／２個の並び替え回路２−１〜２−Ｓ／２の第１、第２の出力のデータのうち、該入力された選択対象データよりも大きい値のデータがある場合、該データは、後段、前段の並び替え回路による並び替え処理の結果、前段の第１の並び替え回路１−１の第２の出力から破棄され、代わって、該入力された選択対象データがＳ個のデータの１つが選択される。すなわち、後段のＳ／２個の並び替え回路２−１〜２−Ｓ／２の第１、第２の出力からは、入力されたＮ個（Ｎの大きさは任意）の選択対象データの中から、値が小さなＳ個のデータが取り出される。
【００５２】
本実施形態によれば、後段のＳ／２個の並び替え回路２−１〜２−Ｓ／２の第１、第２の出力を入力とする出力制御回路５を設けることで、入力された選択対象データの中から、値の小さいＳ個のデータを、出力制御回路５の出力から多重化して取得することができる。なお、値の小さいＳ個のデータとして、値が同一のデータが例えば２個ある場合、２個のデータが別々の出力として出力される。また、本実施形態において、選択される値の小さいＳ個（例えば４個）のデータは、最小のデータ、該最小のデータと等しいか次に大きな第２のデータ、第２のデータと等しいかさらに大きな第３のデータ、第３のデータと等しいかさらに大きな第４のデータが選択されるが、その順番は、選択対象データの入力順序に依存しており、選択された４つのデータを、例えば昇順に出力することは行わない。
【００５３】
本実施形態についてさらに詳細に説明すると、後段の並び替え回路２−ｉ（ただし、ｉは１〜Ｓ／２−１の整数）は、第１の入力に、前段の並び替え回路１−ｉの第１の出力を入力し、第２の入力に、前段の並び替え回路１−（ｉ＋１）の第２の出力を入力し、後段の並び替え回路２−Ｓ／２は、第１の入力に、前段の並び替え回路１−Ｓ／２の第１の出力を入力し、第２の入力に、保持回路（フリップフロップ回路）４−１の出力を入力し、並び替え回路１−１の第２の出力はオープンとされる（出力されたデータはそのまま破棄される）。
【００５４】
後段の並び替え回路２−ｊ（ただし、ｊは１〜Ｓ／２−１の整数）の第２の出力は、セレクタ回路３−｛２×（ｊ−１）＋１｝の第１の入力に接続され、後段の並び替え回路２−ｊの第１の出力は、セレクタ回路３−（２×ｊ）の第１の入力に接続され、セレクタ回路３−１〜３−Ｓの第２の入力にはａｌｌ‘１’(例えばｋビット全て１の最大値；初期設定値として用いられる)が入力され、選択信号ＳＰに基づき、第１又は第２の入力を選択して出力する。
【００５５】
セレクタ回路３−１の出力は、並び替え回路１−１の第２の入力に入力される。セレクタ回路３−｛２×（ｌ−１）｝（ただし、ｌは２乃至Ｓ／２の整数）の出力は、前段の並び替え回路１−ｌの第１の入力に入力され、セレクタ回路３−｛２×（ｌ−１）＋１｝（ただし、ｌは１乃至Ｓ／２の整数）の出力は、前段の並び替え回路１−ｌの第２の入力に入力される。セレクタ回路３−Ｓの出力はフリップフロップ４−１に入力される。
【００５６】
後段のＳ／２個の並び替え回路２−１〜２−Ｓ／２の第１、第２の出力を順に入力するＳ個のセレクタ回路３−１〜３−Ｓは、選択制御信号をなすＳＰ信号が論理‘１’のときに、ａｌｌ‘１’（ｋビット全て１）を選択出力し、セレクタ回路３−１の出力を入力とする、前段の並び替え回路１−１の第２の入力、セレクタ回路３−｛２×（ｉ−１）｝とセレクタ回路３−｛２×（ｉ−１）＋１｝の出力を第１、第２の入力に入力する並び替え回路１−ｉ（ただし、ｉは２乃至Ｓ／２の整数）、セレクタ回路３−Ｓの出力を入力とする、フリップフロップ４−１に、ａｌｌ‘１’を供給し、初期化する。
【００５７】
選択制御信号であるＳＰ信号の論理が‘０’のときに、セレクタ回路３−１〜３−Ｓのそれぞれは、後段の並び替え回路２−１〜２−Ｓ／２の第１の出力、第２の出力を受け取り、対応する前段の並び替え回路１−１〜１−Ｓ／２の入力１、入力２及びフリップフロップ回路４−１に順次入力し、選択対象データを、並び替え回路１−１に、順次入力して、最大値を並び替え回路１−１の第２の出力から破棄する処理を繰り返す。
【００５８】
選択対象データを入力し終えると、Ｓ個の小さいデータを、出力制御回路５より選択出力する。
【００５９】
上述したように本発明は、並び替え処理を、並列に実行することで、処理時間を短縮し、回路規模が選択対象データ数に依存しないため、ハードウェア規模を抑えることができる。以下、各種実施例に即して説明する。
【実施例】
【００６０】
図１は、本発明の一実施例の構成を示す図である。図１には、Ｎ個のｋビット幅の選択対象データから順序を問わずにＳ個（Ｓは２以上の偶数）のｋビット幅の小さいデータを選択出力するソート回路が示されている。
【００６１】
２つの値を比較して大小の順序に並び替えて出力する、前段（１段目）の並び替え回路１−１〜１−Ｓ／２と、後段（２段目）の並び替え回路２−１〜２−Ｓ／２、セレクタ回路３−１〜３−Ｓ、セレクタ回路６、フリップフロップ回路４−１、４−２、出力制御回路５を備えている。また、入力されたデータは、ｋビット幅の信号線によって、構成要素内または構成要素間で伝送される。なお、並び替え回路１−１〜１−Ｓ／２、２−１〜２−Ｓ／２、セレクタ回路３−１〜３−Ｓにおいて、参照番号１、２、３につづく記号”−”の後に付加される添え字”１”、”２”、…、”Ｓ／２”、あるいは”Ｓ”は、１番目、２番目、…、Ｓ／２番目、Ｓ番目を表す。
【００６２】
セレクタ回路６は、選択対象データのＮ個の入力（データ列）と、ａｌｌ‘１’（ｋビット全てが１）を入力し、入力イネーブル（ｅｎａｂｌｅ）信号を選択制御信号として入力する。
【００６３】
前段の１番目の並び替え回路１−１は、セレクタ回路６の出力を第１の入力（図１の入力１）から入力し、セレクタ回路３−１の出力を第２の入力（図１の入力２）から入力し、大のデータを第２の出力（図１の大）から出力し、小のデータを第１の出力（図１の小）から出力する。並び替え回路１−１の第２の出力（図１の大）から出力されたデータは、破棄される。
【００６４】
前段の２番目の並び替え回路１−２は、セレクタ回路３−２の出力を入力１、セレクタ回路３−３の出力を入力２として入力する。
【００６５】
前段の３番目の並び替え回路１−３は、セレクタ回路３−４の出力を入力１、セレクタ回路３−５の出力を入力２として入力する。
【００６６】
前段の４番目の並び替え回路１−４は、セレクタ回路３−６の出力を入力１、セレクタ回路３−７の出力を入力２として入力する。
【００６７】
同様にして、前段のＳ／２番目の並び替え回路１−Ｓ／２は、（Ｓ−２）番目のセレクタ回路３−Ｓ−２の出力を入力１、（Ｓ−１）番目のセレクタ回路３−Ｓ−１の出力を入力２として入力する。
【００６８】
フリップフロップ回路４−１は、Ｓ番目のセレクタ回路３−Ｓの出力を入力する。フリップフロップ回路４−１は図示されないサンプリング用クロックに応じて、Ｓ番目のセレクタ回路３−Ｓの出力をサンプルして出力する。
【００６９】
後段の１番目の並び替え回路２−１は、前段の１番目の並び替え回路１−１の第１の出力（小）を入力１、前段の２番目の並び替え回路１−２の第２の出力（大）を入力２として入力する。
【００７０】
後段の２番目の並び替え回路２−２は、前段の２番目の並び替え回路１−２の第１の出力（小）を入力１、前段の３番目の並び替え回路１−３の第２の出力（大）を入力２として入力する。
【００７１】
後段の３番目の並び替え回路２−３は、前段の３番目の並び替え回路１−３の第１の出力（小）を入力１、前段の４番目の並び替え回路１−４の第２の出力（大）を入力２として入力する。
【００７２】
後段のＳ／２番目の並び替え回路２−Ｓ／２は、前段のＳ／２番目の並び替え回路１−Ｓ／２の第２の出力（小）を入力１、フリップフロップ回路４−１の出力を入力２として入力する。
【００７３】
出力制御回路５は、Ｓ／２個の並び替え回路２−１〜２−Ｓ／２の第１の出力（小）、第２の出力（大）を入力し、フリップフロップ４−２の制御のもと、選択データとして、Ｓ個のデータを出力する。
【００７４】
１番目のセレクタ回路３−１は、第１、第２の入力から、後段の１番目の並び替え回路２−１の第２の出力（大）と、ａｌｌ‘１’（ｋビット全て１の初期設定値）とを入力し、選択制御信号であるＳＰ信号が論理‘１’のとき、ａｌｌ‘１’を選択出力し、ＳＰ信号が論理‘０’のとき、並び替え回路２−１の第２の出力を選択出力する。
【００７５】
２番目のセレクタ回路３−２は、第１、第２の入力から、後段の１番目の並び替え回路２−１の第１の出力（小）と、ａｌｌ‘１’とを入力し、ＳＰ信号が論理‘１’のとき、ａｌｌ‘１’を選択出力し、ＳＰ信号が論理‘０’のとき、並び替え回路２−１の第１の出力を選択出力する。
【００７６】
３番目のセレクタ回路３−３は、第１、第２の入力から、後段の２番目の並び替え回路２−２の第２の出力（大）と、ａｌｌ‘１’とを入力し、ＳＰ信号が論理‘１’のとき、ａｌｌ‘１’を選択出力し、ＳＰ信号が論理‘０’のとき、並び替え回路２−２の第２の出力を選択出力する。
【００７７】
４番目のセレクタ回路３−４は、第１、第２の入力から、後段の２番目の並び替え回路２−２の第１の出力（小）と、ａｌｌ‘１’を入力し、ＳＰ信号が論理‘１’のとき、ａｌｌ‘１’を選択出力し、ＳＰ信号が論理‘０’のとき、並び替え回路２−２の第１の出力を選択出力する。
【００７８】
（Ｓ−１）番目のセレクタ回路３−Ｓ−１は、第１、第２の入力から、後段のＳ／２番目の並び替え回路２−Ｓ／２の第２の出力（大）と、ａｌｌ‘１’とを入力し、ＳＰ信号が論理‘１’のとき、ａｌｌ‘１’を選択出力し、ＳＰ信号が論理‘０’のとき並び替え回路２−Ｓ／２の第２の出力を選択出力する。
【００７９】
Ｓ番目のセレクタ回路３−Ｓは、第１、第２の入力から、後段のＳ／２番目の並び替え回路２−Ｓ／２の第１の出力（小）と、ａｌｌ‘１’を入力し、ＳＰ信号が論理‘１’のとき、ａｌｌ‘１’を選択出力し、ＳＰ信号が論理‘０’のとき、並び替え回路２−Ｓ／２の第１の出力を選択出力する。
【００８０】
図２は、図１の並び替え回路の構成を示す図である。図１のＳ個の並べ替え回路１−１〜１−Ｓ／２、２−１〜２−Ｓ／２は、同一構成とされる。図２において、入力１、入力２より供給された２つのデータ（ｋビット幅）を入力して減算する減算器７にて、２つのデータの大小の判別を行い、判別結果は、判定器９を介して、入力１と入力２に接続された２つのセレクタ回路１０−１、１０−２に出力され、並び替え結果を出力１（小）と、出力２（大）に出力する。なお、並び替え回路の入力１、入力２より、供給された２つのデータが互いに等しい場合には、それぞれ、出力１（小）と出力２（大）に出力する。セレクタ回路１０−１、１０−２、及び判定器９の前段に、フリップフロップ回路８が設けられている。セレクタ回路１０−１は、フリップフロップ回路８に保持されている２つのデータを入力し、判定器９の判定結果に基づき、２つのデータのうち小さい方のデータを選択して出力１（小）に出力する。セレクタ回路１０−２は、フリップフロップ回路８に保持されている２つのデータを入力し、判定器９の判定結果に基づき、２つのデータのうち大きい方のデータを選択して出力２（大）を出力する。
【００８１】
図２を参照して、並び替え回路の動作について説明する。減算器７は、入力１のデータと入力２のデータを減算し、入力１のデータが入力２のデータより小さいか、大きいかあるいは同じであるか判別する。
【００８２】
判定器９は、フリップフロップ回路８を介在した減算結果からセレクタ回路１０−１、１０−２の制御信号を作成する。
【００８３】
セレクタ回路１０−１、１０−２は、フリップフロップ回路８からの入力１のデータと入力２のデータを、判定器９の出力に従って出力１または出力２のいずれかを選択出力する。したがって、入力１のデータよりも入力２のデータが大である場合、入力１のデータを出力１へ出力し、入力２のデータを出力２へ出力する。
【００８４】
入力１のデータよりも入力２のデータが小さいか、あるいは同じであるとき、入力１のデータを出力２へ出力し、入力２のデータを出力１へ出力する動作を行う。
【００８５】
以上のことから、入力データが入力１、入力２のどちらの端子に印加されるかによらず、小さいデータが出力１へ、大きいデータが出力２に出力されるように、並び替えを行い、２入力のソート回路として機能する。
【００８６】
さらに、判定器９にて、セレクタ回路１０−１、１０−２の制御信号の論理を、上記と逆にすれば、入力１データより入力２データが大きければ入力１データを出力２へ出力し、入力２データを出力１へ出力する。入力１のデータよりも入力２のデータが小さい、あるいは同じならば、入力１のデータを出力１へ出力し、入力２のデータを出力２へ出力する動作を行うことが可能となる。
【００８７】
また、選択対象データを、順次入力し、新たに入力された選択対象データと、過去に入力された選択対象データとの並び替え動作を繰り返すため、フリップフロップ回路８にて、データを保持する。フリップフロップ回路８は、図示されないサンプリング用クロックに応じて入力１、２、減算器７の出力をサンプルして出力する。
【００８８】
図１を参照して、本実施例の動作について説明する。前段の並び替え回路１−１の第２の出力を除く第１の出力、及び、並び替え回路１−２から並び替え回路１−Ｓ／２の第１及び第２の出力（２×（Ｓ／２−１）＋１＝Ｓ−１個）は、後段の並び替え回路２−１〜２−Ｓ／２の２つの入力に出力される。前段のフリップフロップ回路４−１の出力は、後段のＳ／２番目の並び替え回路２−Ｓ／２の入力２へ入力される。
【００８９】
選択対象となるＮ個の時分割多重データは入力信号線を通ってセレクタ回路６へ入力する。
【００９０】
セレクタ回路６には、選択対象データの有効または無効を示す入力イネーブル（ｅｎａｂｌｅ）信号が入力され、入力イネーブル（ｅｎａｂｌｅ）信号の論理が‘１’のときに、選択対象データ列を並び替え回路１−１の入力１へ入力し、入力イネーブル（ｅｎａｂｌｅ）信号の論理が‘０’のときは、予め設定されている全てのビットを‘１’にしたａｌｌ‘１’（最大値：初期設定値）を、並び替え回路１−１の入力１へ入力する。
【００９１】
前段の１番目の並び替え回路１−１の並び替え出力の大きい方のデータは、第２の出力から出力され、選択対象データの中の最大値として破棄される。すなわち、後段の並び替え回路２−１〜２−Ｓ／２には入力されない。
【００９２】
また、後段の並び替え回路２−１〜２−Ｓ／２の並び替え結果は、セレクタ回路３−１〜３−Ｓに入力される。すなわち、後段の並び替え回路２−１〜２−Ｓ／２の第１、第２の出力よりなるＳ個の出力は、それぞれ、セレクタ回路３−１〜３−Ｓの第１の入力に入力される。
【００９３】
セレクタ回路３−１〜３−Ｓ−１の出力は、並び替え回路１−１〜１−Ｓ／２の入力となり、セレクタ回路３−Ｓの出力は、フリップフロップ回路４−１の入力となる。
【００９４】
セレクタ回路３−１〜３−Ｓは、選択対象データの先頭を示すＳＰ信号によって、全てのビットを‘１’にした最大値ａｌｌ‘１’と、並び替え回路２−１〜２−Ｓ／２での並び替えの結果の一方を選択出力し、セレクタ回路３−１〜３−Ｓの出力は、前段の並び替え回路１−１〜１−Ｓ／２、及び、フリップフロップ回路４−１の対応する入力に帰還入力される。
【００９５】
後段のＳ／２個の並び替え回路２−１〜２−Ｓ／２の第１、第２の出力（Ｓ×ｋビット）は、出力制御回路５に入力され、出力制御回路５は、出力信号線（ｋビット）に、時分割多重したＳ個の選択データを、出力信号の有効又は無効を示す出力イネーブル（ｅｎａｂｌｅ）信号と共に出力する。選択対象データの終了を示すＥＰ信号は、フリップフロップ回路４−２を介して、出力制御回路５に入力される。
【００９６】
以上、上記実施例では、選択データ数Ｓが偶数である場合を例に説明したが、選択データ数Ｓが奇数の場合においても構成の一部を変更することで対応できる。
【００９７】
図４は、本発明の第２の実施例の構成を示す図である。図４には、Ｎ個の選択対象データからＳ個（Ｓは、１以上の奇数）の小さいデータを選択出力する例に、本発明を適用した構成の一例が示されている。
【００９８】
図４に示した第２の実施例と、図１に示した実施例（偶数Ｓ個を選択）との相違点として、前段（１段目）に、（Ｓ＋１）／２個（ただし、Ｓは所定の正の奇数）の並び替え回路１−１〜１−（Ｓ＋１）／２を有し、後段（２段目）に、（Ｓ−１）／２個の並び替え回路２−１〜２−（Ｓ−１）／２と、フリップフロップ回路４−１を備え、前段の（Ｓ＋１）／２番目の並び替え回路１−（Ｓ＋１）／２の第１の出力（小）を、後段のフリップフロップ回路４−１へ入力し、フリップフロップ回路４−１の出力は、Ｓ番目のセレクタ回路３−Ｓに入力されている。
【００９９】
より詳細には、図４を参照すると、前段に並置される並び替え回路１−１〜１−（Ｓ＋１）／２（ただし、Ｓは所定の正の奇数）と、後段に並置される、並び替え回路２−２〜１−（Ｓ＋１）／２、及び保持回路４−１と、Ｓ個のセレクタ回路３−１〜３−Ｓと、出力制御回路５と、を備えている。
【０１００】
後段の並び替え回路２−１は、入力１に、前段の並び替え回路１−１の第１の出力（小）を入力し、第２の入力に、前段の並び替え回路１−２の第２の出力（大）を入力する。後段の並び替え回路２−２は、入力１に、前段の並び替え回路１−２の第１の出力（小）を入力し、第２の入力に、前段の並び替え回路１−３の第２の出力（大）を入力する。すなわち、後段の並び替え回路２−ｉ（ただし、ｉは１〜（Ｓ−１）／２の整数）は、入力１に、前段の並び替え回路２−ｉの第１の出力（小）を入力し、第２の入力に、前段の第（ｉ＋１）の並び替え回路の第２の出力を入力する。保持回路４−１は、前段の並び替え回路１−（Ｓ＋１）／２の第１の出力（小）を入力する。なお、前記実施例と同様、前段の並び替え回路１−１の第２の出力（大）はオープンとされる。
【０１０１】
後段の並び替え回路２−１の第２の出力（大）は、セレクタ回路３−１の第１の入力に接続され、第１の出力（小）は、セレクタ回路３−２の第１の入力に接続されている。後段の並び替え回路２−２の第２の出力（大）は、セレクタ回路３−３の第１の入力に接続され、第１の出力（小）は、セレクタ回路３−４の第１の入力に接続されている。後段の並び替え回路２−３の第２の出力（大）は、セレクタ回路３−５の第１の入力に接続され、第１の出力（小）は、セレクタ回路３−６の第１の入力に接続されている。すなわち、後段の並び替え回路２−ｊ（ただし、ｊは１〜（Ｓ−１）／２の整数）の第２の出力（大）は、セレクタ回路３−｛２×（ｊ−１）＋１｝の第１の入力に接続され、第１の出力（小）は、セレクタ回路３−（２×ｊ）の第１の入力に接続されている。後段の保持回路４−１の出力は、セレクタ回路３−Ｓの第１の入力に接続されている。セレクタ回路３−１〜３−Ｓの第２の入力には、ａｌｌ‘１’が入力され、選択対象データの先頭を示すＳＰ信号を選択制御信号として入力し、第１又は第２の入力の一方を選択して出力する。セレクタ回路３−１〜３−Ｓは、選択対象データの先頭を示すＳＰ信号により、第１の入力を選択して出力する。
【０１０２】
セレクタ回路３−１の出力は、前段の並び替え回路１−１の第２の入力に入力される。セレクタ回路３−２の出力は、前段の並び替え回路１−２の第１の入力に入力され、セレクタ回路３−３の出力は、前段の並び替え回路１−２の第２の入力に入力される。セレクタ回路３−４の出力は、前段の並び替え回路１−３の第１の入力に入力され、セレクタ回路３−５の出力は、前段の並び替え回路１−３の第２の入力に入力される。すなわち、セレクタ回路３−｛２×（ｌ−１）｝（ただし、ｌは２乃至（Ｓ＋１）／２の整数）の出力は、前段の並び替え回路１−ｌの第１の入力に入力され、セレクタ回路３−｛２×（ｌ−１）＋１｝（ただし、ｌは１乃至（Ｓ＋１）／２の整数）の出力は、前段の並び替え回路１−ｌの第２の入力に入力される。セレクタ回路３−Ｓの出力は、前段の並び替え回路１−（Ｓ＋１）／２の第２の入力に入力される。
【０１０３】
また、前記実施例と同様、選択対象データ列とａｌｌ‘１’（ｋビット全て１）とを入力し、出力が前段の並び替え回路１−１の第１の入力に接続され、入力イネーブル信号が活性状態のとき、選択対象データを、並び替え回路１−１の第１の入力に出力するセレクタ回路６を備えている。出力制御回路６は、後段の並び替え回路２−１〜２−（Ｓ−１）／２の第１、第２の出力、保持回路の出力を入力し、Ｓ個の選択データを多重化して、出力信号の有効又は無効を示す出力イネーブル（ｅｎａｂｌｅ）信号と共に出力する。選択対象データの終了を示すＥＰ信号は、フリップフロップ回路４−２を介して、出力制御回路５に入力される。
【０１０４】
次に、図１に示した実施例について、図３のタイミング図を用いて、ｋ＝４ビットの場合の動作を説明する。選択対象データ‘９’、‘２’、‘Ｆ’、‘３’、‘２’、‘Ｆ’、‘４’、‘０’の８個が、２Ｔ毎（Ｔ＝１クロック期間）に、ｔ１〜ｔ１６の間、入力され、値の小さいデータ４個を選択するものとする。但し、この場合、入力される選択対象データの最大値は‘Ｆ’（４ビットが全て１、Ｆはヘキサデシマル表示）とする。選択するデータの個数が４（Ｓ＝４）であるため、図１において、前段の２個の並び替え回路１−１、１−２、後段の２個の並び替え回路２−１、２−２、４個のセレクタ回路３−１〜３−４の構成とされる。図３において、ｔ１、ｔ２、…、ｔ２６は、それぞれ、１クロック分のタイミング期間（１クロックピリオド）を表している。図３には、クロック信号、セレクタ回路６に入力される入力イネーブル信号、並び替え回路１−１の入力１（入力される選択対象データ）、並び替え回路１−１の入力２、並び替え回路１−２の入力１、並び替え回路１−２の入力２、フリップフロップ回路４−１の入力、並び替え回路１−１の出力２、並び替え回路１−１の出力１、並び替え回路１−２の出力２、並び替え回路１−２の出力１、フリップフロップ回路４−１の出力、並び替え回路２−１の出力２、並び替え回路２−１の出力１、並び替え回路２−２の出力２、並び替え回路２−２の出力１、ＳＰ信号、ＥＰ信号、出力制御回路５から出力される出力イネーブル信号、出力制御回路５からシリアルに出力される選択データ出力のタイミング動作、あるいは信号波形が示されている。
【０１０５】
選択対象データは、入力イネーブル（ｅｎａｂｌｅ）信号の論理が‘１’のとき、セレクタ回路６によって、並び替え回路１−１の入力１へ入力される。
【０１０６】
入力イネーブル（ｅｎａｂｌｅ）信号の論理が‘０’のときは、選択対象データが入力されていないと見なし、ｋ＝４ビットのときの最大値である、ダミーデータ（ａｌｌ‘１’；「初期設定データ」ともいう）‘Ｆ’が、並び替え回路１−１の入力１へ入力される。このダミーデータ（ａｌｌ‘１’）‘Ｆ’は破棄され、内部の動作に影響しない。
【０１０７】
ｔ１において、ＳＰ信号によって、セレクタ回路３−１〜３−４が制御され、最大値ａｌｌ‘１’として設定した‘Ｆ’（＝"１１１１"）が、並び替え回路１−１の入力２、並び替え回路１−２の入力１と入力２、フリップフロップ回路４−１に入力される。なお、ＳＰ信号の論理が‘１’のとき、すなわち先頭の選択対象データ入力時に、セレクタ回路３−１〜３−４が選択対象データの最大値‘Ｆ’を選択し、ＳＰ信号の論理が‘０’のとき、すなわち先頭の選択対象データ入力時以外は、並び替え回路２−１、２−２の出力を選択する。ＳＰ信号の論理が‘１’のときに選択入力される最大値‘Ｆ’は、選択対象データと並び替えを行うための初期設定データであり、入力された選択対象データが初期設定データよりも小さければ、該初期設定データは並び替え回路１−１の出力２から出力されて破棄され、選択データに影響は与えない。
【０１０８】
ｔ２において、並び替え回路１−１による並び替え処理が実行され、大きい方のデータ‘Ｆ’は、並び替え回路１−１の出力２から出力されて破棄され、小さい方のデータ‘９’は、並び替え回路１−１の出力１から、並び替え回路２−１の入力１へ出力される。
【０１０９】
ｔ３において、並び替え回路２−１による並び替え処理が実行され、並び替え回路２−１の出力２から大きい方のデータ‘Ｆ’が、セレクタ回路３−１に、並び替え回路２−１の出力１から小さい方のデータ‘９’が、セレクタ回路３−２にそれぞれ出力される。セレクタ回路３−１〜３−４の出力‘Ｆ’、‘９’、‘Ｆ’、‘Ｆ’は、並列に出力され、それぞれ、並び替え回路１−１の入力２、並び替え回路１−２の入力１と入力２、フリップフロップ回路４−１に帰還入力される。
【０１１０】
ｔ４において、並び替え回路１−１による並び替え処理が実行され、大きい方のデータ‘Ｆ’は破棄され、並び替え回路１−１の出力１からの小さい方のデータ‘２’は、並び替え回路２−１の入力１へ出力される。並び替え回路１−２の並び替え処理では、出力２から大きい方のデータ‘Ｆ’が、並び替え回路２−１の入力２へ、出力１から小さい方のデータ‘９’が並び替え回路２−２の入力１へ出力される。
【０１１１】
ｔ５において、並び替え回路２−１の並び替え処理が実行され、大きい方のデータ‘Ｆ’が出力２から、セレクタ回路３−１に、小さい方のデータ‘２’は、出力１からセレクタ回路３−２へ出力される。並び替え回路２−２の並び替え処理では、大きい方のデータ‘Ｆ’が、出力２から、セレクタ回路３−３へ、小さい方のデータ‘９’が、出力１から、セレクタ回路３−４へ出力される。セレクタ回路３−１〜３−４の出力‘Ｆ’、‘２’、‘Ｆ’、‘９’は、並列に出力され、それぞれ、並び替え回路１−１の入力２、並び替え回路１−２の入力１と入力２、フリップフロップ回路４−１に帰還入力される。
【０１１２】
ｔ６において、並び替え回路１−１の並び替え処理が実行され、一方のデータ‘Ｆ’は破棄され、他方のデータ‘Ｆ’が、並び替え回路２−１の入力１へ出力される。並び替え回路１−２の並び替え処理では、大きい方のデータ‘Ｆ’が、出力２から並び替え回路２−１の入力２へ、小さい方のデータ‘２’が、出力１から、並び替え回路２−２の入力１へ出力される。フリップフロップ回路４−１の出力‘９’は、並び替え回路２−２の入力２へ出力される。
【０１１３】
ｔ７において、並び替え回路２−１の並び替え処理が実行され、一方のデータ‘Ｆ’が出力２からセレクタ回路３−１に、他方のデータ‘Ｆ’は、出力１からセレクタ回路３−２へ出力される。並び替え回路２−２の並び替え処理では、大きい方のデータ‘９’が出力２からセレクタ回路３−３へ、小さい方のデータ‘２’が出力１からセレクタ回路３−４へ出力される。セレクタ回路３−１〜３−４の出力‘Ｆ’、‘Ｆ’、‘９’、‘２’は、並列に出力され、並び替え回路１−１の入力２、並び替え回路１−２の入力１と入力２、フリップフロップ回路４−１に帰還入力される。
【０１１４】
上記に示した、サイクルｔ３からの処理を、同様に、サイクルｔ１６まで繰り返す。但し、ｔ１１、ｔ１２の間のように、セレクタ回路６の入力イネーブル（ｅｎａｂｌｅ）信号の論理が‘０’とされた場合、該当期間に入力された選択対象データを無効と見なし、並び替え回路１−１の入力１には、セレクタ回路６によって、ダミーデータ‘Ｆ’を入力して、処理を行う。
【０１１５】
選択対象データの終了を示すＥＰ信号の論理‘１’が、フリップフロップ回路４−２を介在して出力制御回路５にて検出されると、一定時間を経て、ｔ１８から、並び替え回路２−１と２−２のそれぞれの出力１と、出力２の選択されたデータ‘２’、‘２’、‘０’、‘３’の４個が、出力制御回路５にて、シリアルデータに変換されて、２Ｔ毎に出力する。なお、出力制御回路５は選択データを出力している２Ｔ×Ｓ時間の間、出力イネーブル（ｅｎａｂｌｅ）信号の論理を‘１’とし、選択データを出力していない間は出力イネーブル（ｅｎａｂｌｅ）信号の論理‘０’として出力する。
【０１１６】
以上、一例として、値の小さいデータ４個（偶数）選択において説明したが、図４に示した実施例のように、選択データ数Ｓが奇数の場合においても、対応可能である。
【０１１７】
図５は、図４に示した前記実施例において、ｋ＝４ビットにおける値の小さいデータ３個（奇数）選択の動作を説明するためのタイミングチャートである。
【０１１８】
以下では、図４に示した前記実施例において、選択対象データ‘９’、‘２’、‘Ｆ’、‘３’、‘２’、‘Ｆ’、‘４’、‘０’の８個が、２Ｔ毎（Ｔ＝１クロック）に、ｔ１〜ｔ１６の間入力され、値の小さいデータ３個を選択するものとする。但し、この場合、入力される選択対象データの最大値は‘Ｆ’とする。
【０１１９】
選択対象データは入力イネーブル（ｅｎａｂｌｅ）信号の論理が‘１’のとき、セレクタ回路６によって、並び替え回路１−１の入力１へ入力される。入力イネーブル（ｅｎａｂｌｅ）信号の論理が‘０’のときは、選択対象データが入力されていないものと見なし、ｋ＝４ビットのときの最大値であるダミーデータ（ａｌｌ‘1'）‘Ｆ’が並び替え回路１−１の入力１へ入力される。このダミーデータ‘Ｆ’は、並び替え回路１−１の第２の出力から出力されて破棄され、内部の動作に影響しない。
【０１２０】
ｔ１において、ＳＰ信号によって、セレクタ回路３−１〜３−３が制御され、最大値（ａｌｌ‘1'）として設定した‘Ｆ’が、並び替え回路１−１の入力２、並び替え回路１−２の入力１と入力２に入力される。なお、ＳＰ信号の論理が‘１’のとき、すなわち先頭の選択対象データ入力時に、セレクタ回路３−１〜３−３は、それぞれ、選択対象データの最大値‘Ｆ’を選択し、ＳＰ信号の論理が‘０’のとき、すなわち先頭の選択対象データ入力時以外は、それぞれ、並び替え回路２−１、フリップフロップ回路４−１の出力を選択する。ＳＰ信号の論理が‘１’のときに選択入力される最大値‘Ｆ’は選択対象データと並び替えを行うための初期設定データであり、入力された選択対象データが初期設定データより小さければ破棄され、選択データに影響しない。
【０１２１】
ｔ２において、並び替え回路１−１の並び替え処理が実行され、大きい方のデータ‘Ｆ’は破棄され、小さい方のデータ‘９’は、並び替え回路２−１の入力１へ出力される。
【０１２２】
ｔ３において、並び替え回路２−１の並び替え処理が実行され、大きい方のデータ‘Ｆ’がセレクタ回路３−１に、小さい方のデータ‘９’がセレクタ回路３−２へ出力される。セレクタ回路３−１〜３−３の出力‘Ｆ’、‘９’、‘Ｆ’が、並び替え回路１−１の入力２、並び替え回路１−２の入力１と入力２に入力される。
【０１２３】
ｔ４において、並び替え回路１−１の並び替え処理が実行され、大きい方のデータ‘Ｆ’は破棄され、小さい方のデータ‘２’は、並び替え回路２−１の入力１へ出力される。並び替え回路１−２の並び替え処理では、大きい方のデータ‘Ｆ’が、並び替え回路２−１の入力２へ、小さい方のデータ‘９’がフリップフロップ回路４−１へ出力される。
【０１２４】
ｔ５において、並び替え回路２−１の並び替え処理が実行され、大きい方のデータ‘Ｆ’がセレクタ回路３−１に、小さい方のデータ‘２’はセレクタ回路３−２へ出力される。フリップフロップ回路４−１の出力‘９’がセレクタ回路３−３へ出力される。セレクタ回路３−１〜３−３の出力‘Ｆ’、‘２’、‘９’が並び替え回路１−１の入力２、１−２の入力１と入力２に入力される。
【０１２５】
ｔ６において、並び替え回路１−１の並び替え処理が実行され、一方のデータ‘Ｆ’は破棄され、他方のデータ‘Ｆ’が、並び替え回路２−１の入力１へ出力される。並び替え回路１−２の並び替え処理では大きい方のデータ‘９’が並び替え回路２−１の入力２へ、小さい方のデータ‘２’がフリップフロップ回路４−１へ出力される。
【０１２６】
ｔ７において、並び替え回路２−１の並び替え処理が実行され、一方のデータ‘Ｆ’がセレクタ回路３−１に、他方のデータ‘９’はセレクタ回路３−２へ出力される。フリップフロップ回路４−１の出力‘２’がセレクタ回路３−３へ出力される。セレクタ回路３−１〜３−３の出力‘Ｆ’、‘９’、‘２’が並び替え回路１−１の入力２、１−２の入力１と入力２に入力される。
【０１２７】
上記に示したｔ３からの処理を同様に、ｔ１６まで繰り返す。但し、ｔ１１、ｔ１２の間のように、セレクタ回路６の入力イネーブル（ｅｎａｂｌｅ）信号の論理が‘０’になったとすると、該当期間に入力された選択対象データを無効と見なし、並び替え回路１−１の入力１に、セレクタ回路６によって、ダミーデータ‘Ｆ’を入力して処理を行う。
【０１２８】
選択対象データの終了を示すＥＰ信号の論理‘１’がフリップフロップ回路４−２を介在して、出力制御回路５にて検出されると、一定時間を経て、ｔ１８から、並び替え回路２−１の出力２、出力１と、フリップフロップ回路４−１出力より、３個の選択されたデータ‘２’、‘０’、‘２’が、出力制御回路５にてパラレルに入力され、出力制御回路５でシリアルデータに変換されて、２Ｔ毎に出力される。なお、出力制御回路５は、選択データを出力している時間２Ｔ×Ｓの間、出力イネーブル信号の論理を‘１’とし、選択データを出力していない間は、出力イネーブル信号の論理を‘０’として出力する。
【０１２９】
以上、説明したように、本実施例によれば、選択データ数に関わらず、多数の処理を逐次処理せずに、並列処理することで、データ選択処理を高速化できる。このため、本発明を、高速な情報処理装置に用いることができる。
【０１３０】
また、本発明によれば、回路規模が選択対象データ数に依存しない構成とされている。このため、選択対象データ数が増大しても、回路規模を抑えた構成で、選択処理を行うことができる。したがって、省スペース化が要求される携帯型の情報処理装置に適用することができる。
【０１３１】
本発明の処理時間短縮の効果の具体例として、
選択対象データ数：Ｎ＝２１６＝（６５５３６）、
選択データ数：Ｓ＝２８
とした場合について、比較例として、図８に示したソフトウェア処理と比較してみる。
【０１３２】
動作クロック周波数を２５０ＭＨｚ（１クロック周期＝４ｎｓｅｃ）とした場合、処理時間は、約０.５２ｍｓｅｃとなり、図８のソフトウェアによる選択処理の場合、約２２.９０ｍｓｅｃであるから、処理時間が大幅に短縮できる。
【０１３３】
Ｎ個＝２１６個の選択対象データから、Ｓ（＝２５６）個のデータを取り出す計算過程の処理時間は下記の通り導出される。Ｎ個の選択対象データ数の入力には、２×Ｎのクロックサイクルを要する。
【０１３４】
処理時間＝Ｎ／（動作クロック周波数／２）
＝２１６／（２５０×１０６／２）
＝０．０００５２４３
≒０．５２ｍｓｅｃ
【０１３５】
次に本発明の回路規模削減の効果例として、上記特許文献１等に開示されているハードウェアのソート回路による処理例と、データ比較器、データ選択器総数の観点から比較してみる。
【０１３６】
本発明においては、図２の並び替え回路の減算器７の１個と、判定器９の１個を合わせて、データ比較器１個として計算すると、データ比較器と、データ選択器の総数は、下記の通りとなる。
【０１３７】
データ比較器総数＝Ｓ                  …（４）
データ選択器総数＝３×Ｓ＋１          …（５）
【０１３８】
ここで、選択対象データ数：Ｎ＝２８、選択データ数：Ｓ＝２４とすると、
データ比較器総数＝２４＝１６個            …（６）
データ選択器総数＝３×２４＋１＝４９個    …（７）
となる。
【０１３９】
上記（３）、（４）式に示したように、ハードウェアのソート回路を用いた従来方式の構成例では、
データ比較器総数＝３２６４０個、
データ選択器総数＝６５２８０個
である。
【０１４０】
上記（６）、（７）式の本実施例と、上記（３）、（４）の個数の比較からも明らかなように、本発明によれば、データ選択対象数Ｎに依存せずに、ハードウェアの回路規模は特段に削減することができる。
【０１４１】
なお、本発明は、図１、図４等を参照して説明した実施例の構成にのみ限定されるものではない。
【０１４２】
図６は、本発明の第３の実施例の構成を示す図である。図６に示すように、図１の並び替え回路１−１〜１−Ｓ／２、２−１〜２−Ｓ／２の大小出力結果を逆転し、最小値（ダミーデータ）としてａｌｌ‘０’＝‘０’を、セレクタ回路３−１〜３−Ｓ、セレクタ回路６に設定する。図６の並び替え回路１−１〜１−Ｓ／２、２−１〜２−Ｓ／２は、２つの入力データの並び替えの結果、大のデータを第１の出力から出力し、小のデータを第２の出力から出力する。図６の並び替え回路１−１〜１−Ｓ／２、並び替え回路２−１〜２−Ｓ／２は、図２において、セレクタ回路１０−１の出力１を大（大きい方のデータの出力端子）とし、セレクタ回路１０−２の出力２を小（小さい方のデータの出力端子）とする構成とされている。
【０１４３】
図６において、並び替え回路１−１の第２の出力（小）から出力されるデータは破棄される。ＳＰ信号が論理‘１’のとき、セレクタ回路３−１〜３−Ｓは、ａｌｌ‘０’＝‘０’を出力し、並び替え回路１−１の入力２、並び替え回路１−２〜１−Ｓ／２の入力１、入力２、前段のフリップフロップ回路４−１を‘０’に初期化する。
【０１４４】
本実施例においては、選択対象データと、初期値又は、セレクタ回路３−１からの出力との並び替えを行う前段の並び替え回路１−１の出力２（小）から小さい方のデータが順次破棄されていき、後段のＳ／２個の並び替え回路２−１〜２−Ｓ／２の出力１、２からのＳ個のデータは、入力された選択対象データのうち値の大きなデータとされる。すなわち、並び替えの結果、小さなデータが破棄されていくという具合に反転して動作する他は、図１に示した前記実施例の動作原理に従う。よって、本実施例によれば、並び替え回路１−１の入力１に入力されたＮ個（Ｎは任意の整数）の選択対象データの中から、偶数Ｓ個の値の大きなデータを選択出力する処理装置が実現される。
【０１４５】
図７は、本発明の第４の実施例の構成を示す図であり、図６に示した第３の実施例において、Ｓを奇数とした場合の構成に対応し、また図４に示した実施例において、並び替え回路１−１〜並び替え回路１−（Ｓ＋１）／２、並び替え回路２−１〜並び替え回路２−（Ｓ−１）／２の大小出力結果を逆転している。図７の並び替え回路１−１〜１−（Ｓ＋１）／２、並び替え回路２−１〜２−（Ｓ−１）／２は、２つの入力データの並び替えの結果、大のデータを第１の出力から出力し、小のデータを第２の出力から出力する。ＳＰ信号が論理‘１’のとき、セレクタ回路３−１〜３−Ｓは、最小値ａｌｌ‘０’＝‘０’を出力し、前段の並び替え回路１−１の入力２、並び替え回路１−２〜１−（Ｓ＋１）／２の入力１、入力２を‘０’に初期化する。本実施例においては、並び替え回路１−１の入力１に入力されたＮ個の選択対象データの中から、奇数Ｓ個の値の大きなデータを選択出力する装置が実現される。
【０１４６】
上記した各実施例の処理装置は、例えば情報通信機器等における候補選択やグループ選別処理、無線通信装置におけるパスサーチなど、複数の選択対象データＮ個の中から順序を問わずに値の小さいＳ個のデータを選択する用途に適用して好適とされる。
【０１４７】
以上、本発明を上記実施例に即して説明したが、本発明は、上記実施例の構成にのみ限定されるものでなく、本発明の範囲内で、当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【図面の簡単な説明】
【０１４８】
【図１】本発明の第１の実施例の構成を示す図である。
【図２】本発明の第１の実施例の並び替え回路の構成を示す図である。
【図３】本発明の第１の実施例の動作を説明するためのタイミング図である。
【図４】本発明の第２の実施例の構成を示す図である。
【図５】本発明の第２の実施例の動作を説明するためのタイミング図である。
【図６】本発明の第３の実施例の構成を示す図である。
【図７】本発明の第４の実施例の構成を示す図である。
【図８】ソフトウェアによる選択処理の一例を説明するフローチャートである。
【図９】図８のソフトウェアによる選択処理における機械語命令実行回数の概算を一覧で示す図である。
【符号の説明】
【０１４９】
１−１、１−２、…１−Ｓ／２  並び替え回路
１−（Ｓ＋１）／２  並び替え回路
２−１、２−２、…２−Ｓ／２  並び替え回路
２−（Ｓ−１）／２  並び替え回路
３−１、３−２、…、３−Ｓ  セレクタ回路
４−１、４−２  フリップフロップ回路
５  出力制御回路
６  セレクタ回路
７  減算器
８  フリップフロップ回路
９  判別器
１０−１、１０−２  セレクタ回路
【図１】
2005209092.tif 000003
【図２】
2005209092.tif 000004
【図３】
2005209092.tif 000005
【図４】
2005209092.tif 000006
【図５】
2005209092.tif 000007
【図６】
2005209092.tif 000008
【図７】
2005209092.tif 000009
【図８】
2005209092.tif 000010
【図９】
2005209092.tif 000011