(57)【特許請求の範囲】
【請求項１】
Ｎ個（Ｎは２以上の整数）のビット列データそれぞれの同一のビット位置から取り出したビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる同一位置ビット列と、前記同一位置ビット列のそれぞれのビットをビット判定の対象として選択する選択ビットあるいはビット判定の対象として非選択とする非選択ビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる選択ビット列を入力し、
前記選択ビット列の選択ビットにより選択された前記同一位置ビット列のビットに基づいて、各ビット列データそれぞれの前記同一のビット位置の次のビット位置から取り出したビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる次同一位置ビット列のそれぞれのビットを選択する前記選択ビットあるいは非選択とする前記非選択ビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる次選択ビット列を出力するビット判定回路において、
前記選択ビット列の前記選択ビットにより選択された前記同一位置ビット列のビットが全て“１”であるか判定する全不一致判定器を備え、
前記全不一致判定器が、前記同一位置ビット列のビットが全て“１”であると判定すると、前記選択ビット列を前記次選択ビット列として外部に出力し、
前記全不一致判定器が、前記選択された前記同一位置ビット列のビットが全て“１”でないと判定すると、前記同一位置ビット列の“０”であるビットに対応する前記次選択ビット列のビットを前記選択ビットとするとともに、前記選択された前記同一位置ビット列の“１”であるビットに対応する前記次選択ビット列のビットを前記非選択ビットとし、前記選択ビット列の前記非選択ビットに対応する前記次選択ビット列のビットを前記非選択ビットとして、前記次選択ビット列を外部に出力すること
を特徴とするビット判定回路。
【請求項２】
Ｎ個（Ｎは２以上の整数）のビット列データそれぞれの同一のビット位置から取り出したビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる同一位置ビット列と、前記同一位置ビット列のそれぞれのビットをビット判定の対象として選択する選択ビットあるいはビット判定の対象として非選択とする非選択ビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる選択ビット列を入力し、
前記選択ビット列の選択ビットにより選択された前記同一位置ビット列のビットに基づいて、各ビット列データそれぞれの前記同一のビット位置の次のビット位置から取り出したビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる次同一位置ビット列のそれぞれのビットを選択する前記選択ビットあるいは非選択とする前記非選択ビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる次選択ビット列を出力するビット判定回路において、
前記選択ビット列の前記選択ビットにより選択された前記同一位置ビット列のビットが全て“０”であるか判定する全不一致判定器を備え、
前記全不一致判定器が、前記同一位置ビット列のビットが全て“０”であると判定すると、前記選択ビット列を前記次選択ビット列として外部に出力し、
前記全不一致判定器が、前記選択された前記同一位置ビット列のビットが全て“０”でないと判定すると、前記同一位置ビット列の“１”であるビットに対応する前記次選択ビット列のビットを前記選択ビットとするとともに、前記選択された前記同一位置ビット列の“０”であるビットに対応する前記次選択ビット列のビットを前記非選択ビットとし、前記選択ビット列の前記非選択ビットに対応する前記次選択ビット列のビットを前記非選択ビットとして、前記次選択ビット列を外部に出力すること
を特徴とするビット判定回路。
【請求項３】
Ｎ個（Ｎは２以上の整数）のビット列データそれぞれの同一のビット位置から取り出したビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる同一位置ビット列と、前記同一位置ビット列のそれぞれのビットをビット判定の対象として選択する選択ビットあるいはビット判定の対象として非選択とする非選択ビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる選択ビット列を入力し、
前記選択ビット列の選択ビットにより選択された前記同一位置ビット列のビットに基づいて、各ビット列データそれぞれの前記同一のビット位置の次のビット位置から取り出したビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる次同一位置ビット列のそれぞれのビットを選択する前記選択ビットあるいは非選択とする前記非選択ビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる次選択ビット列を出力するビット判定回路において、
判定ビットを入力し、
前記選択ビット列の前記選択ビットにより選択された前記同一位置ビット列のビットが全て判定ビットと一致しないか判定する全不一致判定器を備え、
前記全不一致判定器が、前記同一位置ビット列のビットが全て前記判定ビットと一致しないと判定すると、前記選択ビット列を前記次選択ビット列として外部に出力し、
前記全不一致判定器が、前記選択された前記同一位置ビット列のビットの少なくとも１つが前記判定ビットと一致すると判定すると、前記同一位置ビット列のビットが前記判定ビットと一致するビットに対応する前記次選択ビット列のビットを前記選択ビットとするとともに、前記選択された前記同一位置ビット列のビットが前記判定ビットと一致しないビットに対応する前記次選択ビット列のビットを前記非選択ビットとし、前記選択ビット列の前記非選択ビットに対応する前記次選択ビット列のビットを前記非選択ビットとして、前記次選択ビット列を外部に出力すること
を特徴とするビット判定回路。
【請求項４】
請求項１に記載のビット判定回路において、
前記選択ビット列と前記同一位置ビット列とのビット列演算を行い演算結果のビット列を出力する一致判定器であって、前記選択ビット列の前記選択フラグビットと前記同一位置ビット列のビットとの演算では、前記同一位置ビット列のビットが“０”であるか“1”であるかに応じて前記選択ビットあるいは前記非選択ビットを出力し、前記選択ビット列の前記非選択ビットと前記同一位置ビット列のビットとの演算では、前記非選択ビットを出力する一致判定器を備え、
前記全不一致判定器が、前記同一位置ビット列のビットが全て“１”であると判定すると、前記選択ビット列を前記次選択ビット列として外部に出力し、
前記全不一致判定器が、前記同一位置ビット列のビットが全て“１”でないと判定すると、前記一致判定器の出力するビット列を前記次選択ビット列として外部に出力すること
を特徴とするビット判定回路。
【請求項５】
請求項１に記載のビット判定回路において、
前記全不一致判定器が、前記同一位置ビット列のビットが全て“１”であると判定すると、全て前記選択ビットであるＮ個のビットからなるビット列を出力し、前記全不一致判定器が、前記同一位置ビット列のビットが全て“１”でないと判定すると、前記同一位置ビット列を出力する判定結果出力選択器を備え、
前記判定結果出力選択器の出力であるビット列と前記選択ビット列の各ビット同士の論理積をビットとするビット列を前記次選択ビット列として外部に出力すること
を特徴とするビット判定回路。
【請求項６】
請求項１に記載のビット判定回路において、
前記選択ビット列と前記同一位置ビット列とのビット列演算を行い演算結果のビット列を出力する一致判定器であって、前記選択ビット列の前記選択ビットと前記同一位置ビット列のビットとの演算では、前記同一位置ビット列のビットが“０”であるか“1”であるかに応じて前記選択ビットあるいは前記非選択ビットを出力し、前記選択ビット列の前記非選択ビットと前記同一位置ビット列のビットとの演算では、前記非選択ビットを出力する一致判定器を備え、
前記全不一致判定器は、前記選択ビット列の前記選択ビットにより選択された前記同一位置ビット列のビットが全て“１”であるか判定することに替えて、前記一致判定器の出力するビット列のビットが全て“１”であるか判定するものであり、
前記全不一致判定器が、前記一致判定器の出力するビット列が全て“１”であると判定すると、前記選択ビット列を前記次選択ビット列として外部に出力し、
前記全不一致判定器が、前記一致判定器の出力するビット列が全て“１”でないと判定すると、前記一致判定器の出力するビット列を前記次選択ビット列として外部に出力すること
を特徴とするビット判定回路。
【請求項７】
請求項２に記載のビット判定回路において、
前記選択ビット列と前記同一位置ビット列とのビット列演算を行い演算結果のビット列を出力する一致判定器であって、前記選択ビット列の前記選択ビットと前記同一位置ビット列のビットとの演算では、前記同一位置ビット列のビットが“１”であるか“０”であるかに応じて前記選択ビットあるいは前記非選択ビットを出力し、前記選択ビット列の前記非選択ビットと前記同一位置ビット列のビットとの演算では、前記非選択ビットを出力する一致判定器を備え、
前記全不一致判定器が、前記同一位置ビット列のビットが全て“０”であると判定すると、前記選択ビット列を前記次選択ビット列として外部に出力し、
前記全不一致判定器が、前記同一位置ビット列のビットが全て“０”でないと判定すると、前記一致判定器の出力を前記次選択ビット列として外部に出力すること
を特徴とするビット判定回路。
【請求項８】
請求項２に記載のビット判定回路において、
前記全不一致判定器が、前記同一位置ビット列のビットが全て“０”であると判定すると、全て前記選択ビットであるＮ個のビットからなるビット列を出力し、前記全不一致判定器が、前記同一位置ビット列のビットが全て“０”でないと判定すると、前記同一位置ビット列を出力する判定結果出力選択器を備え、
前記判定結果出力選択器の出力であるビット列と前記選択ビット列の各ビット同士の論理積をビットとするビット列を前記次選択ビット列として外部に出力すること
を特徴とするビット判定回路。
【請求項９】
請求項２に記載のビット判定回路において、
前記選択ビット列と前記同一位置ビット列とのビット列演算を行い演算結果のビット列を出力する一致判定器であって、前記選択ビット列の前記選択ビットと前記同一位置ビット列のビットとの演算では、前記同一位置ビット列のビットが“１”であるか“０”であるかに応じて前記選択ビットあるいは前記非選択ビットを出力し、前記選択ビット列の前記非選択ビットと前記同一位置ビット列のビットとの演算では、前記非選択ビットを出力する一致判定器を備え、
前記全不一致判定器は、前記選択ビット列の前記選択ビットにより選択された前記同一位置ビット列のビットが全て“０”であるか判定することに替えて、前記一致判定器の出力するビット列が全て“０”であるか判定するものであり、
前記全不一致判定器が、前記一致判定器の出力するビット列が全て“０”であると判定すると、前記選択ビット列を前記次選択ビット列として外部に出力し、
前記全不一致判定器が、前記一致判定器の出力するビット列が全て“０”でないと判定すると、前記一致判定器の出力するビット列を前記次選択ビット列として外部に出力すること
を特徴とするビット判定回路。
【請求項１０】
請求項３に記載のビット判定回路において、
前記選択ビット列と前記同一位置ビット列とのビット列演算を行い演算結果のビット列を出力する一致判定器であって、前記選択ビット列の前記選択ビットと前記同一位置ビット列のビットとの演算では、前記同一位置ビット列のビットが前記判定ビットであるか判定ビットでないかに応じて前記選択ビットあるいは前記非選択ビットを出力し、前記選択ビット列の前記非選択フラグを有するビットと前記同一位置ビット列のビットとの演算では、前記非選択ビットを出力する一致判定器を備え、
前記全不一致判定器が、前記同一位置ビット列のビットが全て前記判定ビットと一致しないと判定すると、前記選択ビット列を前記次選択ビット列として外部に出力し、
前記全不一致判定器が、前記同一位置ビット列のビットの少なくとも１つが前記判定ビットと一致すると判定すると、前記一致判定器の出力を前記次選択ビット列として外部に出力すること
を特徴とするビット判定回路。
【請求項１１】
請求項３に記載のビット判定回路において、
前記全不一致判定器が、前記同一位置ビット列のビットが全て前記判定ビットと一致しないと判定すると、全て前記選択ビットであるＮ個のビットからなるビット列を出力し、前記全不一致判定器が、前記同一位置ビット列のビットの少なくとも１つが前記判定ビットと一致すると判定すると、前記同一位置ビット列を出力する判定結果出力選択器を備え、
前記判定結果出力選択器の出力であるビット列と前記選択ビット列の各ビット同士の論理積をビットとするビット列を前記次選択ビット列として外部に出力すること
を特徴とするビット判定回路。
【請求項１２】
請求項３に記載のビット判定回路において、
前記選択ビット列と前記同一位置ビット列とのビット列演算を行い演算結果のビット列を出力する一致判定器であって、前記選択ビット列の前記選択ビットと前記同一位置ビット列のビットとの演算では、前記同一位置ビット列のビットが判定ビットであるか判定ビットでないかに応じて前記選択ビットあるいは前記非選択ビットを出力し、前記選択ビット列の前記非選択ビットと前記同一位置ビット列のビットとの演算では、前記非選択ビットを出力する一致判定器を備え、
前記全不一致判定器は、前記選択ビット列の前記選択ビットにより選択された前記同一位置ビット列のビットが全て前記判定ビットと一致しないか判定することに替えて、前記一致判定器の出力するビット列のビットが全て前記判定ビットと一致しないか判定するものであり、
前記全不一致判定器が、前記一致判定器の出力するビット列が全て前記判定ビットと一致しないと判定すると、前記選択ビット列を前記次選択ビット列として外部に出力し、
前記全不一致判定器が、前記一致判定器の出力するビット列の少なくとも１つが前記判定ビットと一致すると判定すると、前記一致判定器の出力するビット列を前記次選択ビット列として外部に出力すること
を特徴とするビット判定回路。
【請求項１３】
それぞれのビット長がｍ（ｍは正の整数）であるＮ個（Ｎは２以上の正の整数）のビット列データのうちの選択されたビット列データから最小の値を有するビット列データを選択するための最小値選択回路において、
請求項１、請求項４乃至請求項６のいずれか１項に記載されたビット判定回路を、前段のビット判定回路の出力である次選択ビット列を後段のビット判定回路の選択ビット列として入力するようにｍ段直列に接続し、
ｍ段目のビット判定回路の出力である次選択ビット列を、初段のビット判定回路に入力する選択ビット列で選択されたビットに対応する最小値のビット列データを選択するための情報として外部に出力すること
を特徴とするビット列データ選択回路。
【請求項１４】
それぞれのビット長がｍ（ｍは正の整数）であるＮ個（Ｎは２以上の正の整数）のビット列データのうちの選択されたビット列データから最大の値を有するビット列データを選択するための最大値選択回路において、
請求項２、請求項７乃至請求項９のいずれか１項に記載されたビット判定回路を、前段のビット判定回路の出力である次選択ビット列を後段のビット判定回路の選択ビット列として入力するようにｍ段直列に接続し、
ｍ段目のビット判定回路の出力である次選択ビット列を、初段のビット判定回路に入力する選択ビット列で選択されたビットに対応する最大値のビット列データを選択するための情報として外部に出力すること
を特徴とするビット列データ選択回路。
【請求項１５】
それぞれのビット長がｍ（ｍは正の整数）であるＮ個（Ｎは２以上の正の整数）のビット列データのうちの選択されたビット列データから最大あるいは最小の値を有するビット列データを選択するための最大値・最小値選択回路において、
請求項３、請求項１０乃至請求項１２のいずれか１項に記載されたビット判定回路を、前段のビット判定回路の出力である次選択ビット列を後段のビット判定回路の選択ビット列として入力するようにｍ段直列に接続し、
ｍ段目のビット判定回路の出力である次選択ビット列を、初段のビット判定回路に入力する選択ビット列で選択されたビットに対応する最大値あるいは最小値のビット列データを選択するための情報として外部に出力すること
を特徴とするビット列データ選択回路。
【請求項１６】
それぞれのビット長がｍ（ｍは正の整数）であるＮ個（Ｎは２以上の正の整数）のビット列データから昇順でビット列データを選択するためのビット列データ順次選択回路において、
請求項１３記載のビット列データ選択回路と、
前記ビット列データ選択回路に入力する選択ビット列を保持する選択ビットレジスタと、
前記ビット列データ選択回路の出力である次選択ビット列を選択結果ビット列として保持する選択結果レジスタと、
前記選択ビットレジスタに保持された選択ビット列の、前記選択結果レジスタに保持された選択結果ビット列の前記選択ビットの存在するビット位置と同一のビット位置のビットを非選択ビットに置換した次の初期選択ビット列を求める次選択ビット設定回路と、
前記次の初期選択ビット列を前記選択ビット列として前記選択ビットレジスタに設定させる第１のクロックを前記選択ビットレジスタに供給するとともに、前記選択結果ビット列を前記選択結果レジスタに保持させる第２のクロックを前記選択結果レジスタに供給する順次選択制御回路と
を備え、
前記次の初期選択ビット列の初期値としてビットが全て前記選択ビットであるビット列を前記第１のクロックに同期して前記選択ビットレジスタに設定し、前記ビット列データ選択回路によるビット列データ選択処理を開始し、該ビット列データ選択処理の結果である選択結果ビット列を前記第２のクロックに同期して前記選択結果レジスタに設定し、かつ該選択結果ビット列を出力し、
さらに、前記次選択ビット設定回路により、前記選択ビットレジスタに保持された選択ビット列の、前記選択結果レジスタに保持された選択結果ビット列の前記選択ビットの存在するビット位置と同一のビット位置のビットを非選択ビットに置換して求められた次の初期選択ビット列を前記選択ビット列として、前記第１のクロックに同期して前記選択ビットレジスタに設定し、前記ビット列データ選択回路によるビット列データ選択処理を実行し、該ビット列データ選択処理の結果である選択結果ビット列を前記第２のクロックに同期して前記選択結果レジスタに設定し、かつ該選択結果ビット列を出力する処理を、前記Ｎ個のビット列データについての、前記ビット列データ選択回路によるビット列データ選択処理と前記選択結果ビット列の出力が終了するまで繰り返すことを特徴とするビット列データ順次選択回路。
【請求項１７】
それぞれのビット長がｍ（ｍは正の整数）であるＮ個（Ｎは２以上の正の整数）のビット列データから降順でビット列データを選択するためのビット列データ順次選択回路において、
請求項１４記載のビット列データ選択回路と、
前記ビット列データ選択回路に入力する選択ビット列を保持する選択ビットレジスタと、
前記ビット列データ選択回路の出力である次選択ビット列を選択結果ビット列として保持する選択結果レジスタと、
前記選択ビットレジスタに保持された選択ビット列の、前記選択結果レジスタに保持された選択結果ビット列の前記選択ビットの存在するビット位置と同一のビット位置のビットを非選択ビットに置換した次の初期選択ビット列を求める次選択ビット設定回路と、
前記次の初期選択ビット列を前記選択ビット列として前記選択ビットレジスタに設定させる第１のクロックを前記選択ビットレジスタに供給するとともに、前記選択結果ビット列を前記選択結果レジスタに保持させる第２のクロックを前記選択結果レジスタに供給する順次選択制御回路と
を備え、
前記次の初期選択ビット列の初期値としてビットが全て前記選択ビットであるビット列を前記第１のクロックに同期して前記選択ビットレジスタに設定し、前記ビット列データ選択回路によるビット列データ選択処理を開始し、該ビット列データ選択処理の結果である選択結果ビット列を前記第２のクロックに同期して前記選択結果レジスタに設定し、かつ該選択結果ビット列を出力し、
さらに、前記次選択ビット設定回路により、前記選択ビットレジスタに保持された選択ビット列の、前記選択結果レジスタに保持された選択結果ビット列の前記選択ビットの存在するビット位置と同一のビット位置のビットを非選択ビットに置換して求められた次の初期選択ビット列を前記選択ビット列として、前記第１のクロックに同期して前記選択ビットレジスタに設定し、前記ビット列データ選択回路によるビット列データ選択処理を実行し、該ビット列データ選択処理の結果である選択結果ビット列を前記第２のクロックに同期して前記選択結果レジスタに設定し、かつ該選択結果ビット列を出力する処理を、前記Ｎ個のビット列データについての、前記ビット列データ選択回路によるビット列データ選択処理と前記選択結果ビット列の出力が終了するまで繰り返すことを特徴とするビット列データ順次選択回路。
【請求項１８】
それぞれのビット長がｍ（ｍは正の整数）であるＮ個（Ｎは２以上の正の整数）のビット列データから昇順あるいは降順でビット列データを選択するためのビット列データ順次選択回路において、
請求項１５記載のビット列データ選択回路と、
前記ビット列データ選択回路に入力する選択ビット列を保持する選択ビットレジスタと、
前記ビット列データ選択回路の出力である次選択ビット列を選択結果ビット列として保持する選択結果レジスタと、
前記選択ビットレジスタに保持された選択ビット列の、前記選択結果レジスタに保持された選択結果ビット列の前記選択ビットの存在するビット位置と同一のビット位置のビットを非選択ビットに置換した次の初期選択ビット列を求める次選択ビット設定回路と、
前記次の初期選択ビット列を前記選択ビット列として前記選択ビットレジスタに設定させる第１のクロックを前記選択ビットレジスタに供給するとともに、前記選択結果ビット列を前記選択結果レジスタに保持させる第２のクロックを前記選択結果レジスタに供給する順次選択制御回路と
を備え、
前記次の初期選択ビット列の初期値としてビットが全て前記選択ビットであるビット列を前記第１のクロックに同期して前記選択ビットレジスタに設定し、前記ビット列データ選択回路によるビット列データ選択処理を開始し、該ビット列データ選択処理の結果である選択結果ビット列を前記第２のクロックに同期して前記選択結果レジスタに設定し、かつ該選択結果ビット列を出力し、
さらに、前記次選択ビット設定回路により、前記選択ビットレジスタに保持された選択ビット列の、前記選択結果レジスタに保持された選択結果ビット列の前記選択ビットの存在するビット位置と同一のビット位置のビットを非選択ビットに置換して求められた次の初期選択ビット列を前記選択ビット列として、前記第１のクロックに同期して前記選択ビットレジスタに設定し、前記ビット列データ選択回路によるビット列データ選択処理を実行し、該ビット列データ選択処理の結果である選択結果ビット列を前記第２のクロックに同期して前記選択結果レジスタに設定し、かつ該選択結果ビット列を出力する処理を、前記Ｎ個のビット列データについての、前記ビット列データ選択回路によるビット列データ選択処理と前記選択結果ビット列の出力が終了するまで繰り返すことを特徴とするビット列データ順次選択回路。
【請求項１９】
請求項１６乃至請求項１８のいずれか一項に記載のビット列データ順次選択回路において、
前記順次選択制御回路は前記第２のクロックをさらに前記次選択ビット設定回路に供給し、
前記次選択ビット設定回路は、
前記選択ビットレジスタに保持された前記選択ビット列を前記第２のクロックに同期して保持する選択ビット列一時保持レジスタと、
前記選択ビット列一時保持レジスタに保持された選択ビット列の、前記選択結果ビット列の前記選択ビットの存在するビット位置と同一のビット位置のビットを非選択ビットとするビット列演算を実行し、前記次の初期選択ビット列を生成する次選択ビット列演算器を含むこと
を特徴とするビット列データ順次選択回路。
【請求項２０】
請求項１６乃至請求項１９のいずれか一項に記載のビット列データ順次選択回路において、
前記第２のクロックは、前記第１のクロックを反転したものであることを
特徴とするビット列データ順次選択回路。
【請求項２１】
請求項１６乃至請求項２０のいずれか一項に記載のビット列データ順次選択回路において、
前記選択結果ビット列のビットが全て非選択ビットであることを検出することにより、前記Ｎ個のビット列データについての前記ビット列データ選択回路によるビット列データ選択処理と前記選択結果ビット列の出力が終了したことを検出することを
特徴とするビット列データ順次選択回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のビット列データの同一ビット位置にあるビットを判定するビット判定回路と、ビット判定回路を用いて複数のビット列データのうちの最小値あるいは最大値のビット列データを選択するための情報を出力するビット列データ選択回路に関する。また、上記ビット列データ選択回路を用いて複数のビット列データの集合から昇順あるいは降順でビット列データを取り出すための情報を出力するビット列データ順次選択回路に関する。
【背景技術】
【０００２】
情報処理の技術分野においては、複数のビット列データから最小値を求める、あるいは最大値を求めることが行われている。この最小値あるいは最大値を求める処理は、例えば、下記特許文献１に示すようにディジタル・シグナル・プロセッサ（ＤＳＰ）を用いたプログラムの実行により実施される。ＤＳＰにはプログラム制御により動作するハードウェアとして最小値あるいは最大値を求める装置が内蔵されている。
【０００３】
図１Ａは、上述の従来の最小値検索処理の処理例を説明する図であり、図１Ｂは、上述の従来の最大値検索処理の処理例を説明する図である。図１Ａ及び図１Ｂに例示するように、従来の最小値検索処理、及び最大値検索処理はビット列データ間の大小比較を繰り返して最小値あるいは最大値を検索するものである。
【０００４】
図１Ａに示す最小値検索処理の例では、複数のビット列データの集合であるビット列データ群１０１は、４つのビット列データ、Ｄ１、Ｄ２、Ｄ３、Ｄ４から構成されており、それぞれのビット列データは、Ｄ１＝１１１、Ｄ２＝０１０、Ｄ３＝０１１、Ｄ４＝１００である。
【０００５】
図１Ａに示すように、ステップ１で例えばビット列データのうち先頭に位置するビット列データＤ１を仮の最小値１１１ａとして設定する。次にステップ２において、ビット列データＤ１と次のビット列データＤ２の大小比較１２１ａを行い、ビット列データＤ２がビット列データＤ１より小さいのでステップ３においてビット列データＤ２を仮の最小値１１１ｂとして設定する。
【０００６】
次にステップ４において、仮の最小値１１１ｂであるビット列データＤ２と次のビット列データＤ３の大小比較１２１ｂを行い、ビット列データＤ２がビット列データＤ３より小さいのでステップ５においてビット列データＤ２を仮の最小値１１１ｃとして設定する。
【０００７】
次にステップ６において、仮の最小値１１１ｃであるビット列データＤ２と最後のビット列データＤ４の大小比較１２１ｃを行い、ビット列データＤ２がビット列データＤ４より小さいのでステップ７においてビット列データＤ２を真の最小値１１１ｄとして決定する。
【０００８】
図１Ｂに示す最大値検索処理の例も、図１Ａに示す最小値検索処理の例と同様にビット列データ群１０１が用いられており、それぞれ、Ｄ１＝１１１、Ｄ２＝０１０、Ｄ３＝０１１、Ｄ４＝１００である。
【０００９】
図１Ｂに示すように、ステップ１で例えばビット列データのうち先頭に位置するビット列データＤ１を仮の最大値１１２ａとして設定する。次にステップ２において、ビット列データＤ１と次のビット列データＤ２の大小比較１２２ａを行い、ビット列データＤ１がビット列データＤ２より大きいのでステップ３においてビット列データＤ１を仮の最大値１１２ｂとして設定する。
【００１０】
次にステップ４において、仮の最大値１１２ｂであるビット列データＤ１と次のビット列データＤ３の大小比較１２２ｂを行い、ビット列データＤ１がビット列データＤ３より大きいのでステップ５においてビット列データＤ１を仮の最大値１１２ｃとして設定する。
【００１１】
次にステップ６において、仮の最大値１１２ｃであるビット列データＤ１と最後のビット列データＤ４の大小比較１２２ｃを行い、ビット列データＤ２がビット列データＤ４より大きいのでステップ７においてビット列データＤ１を真の最大値１１２ｄとして決定する。
【００１２】
上述の最大値・最小値検索処理は、最大値・最小値検索に適したハードウェアを用いたソフトウェア処理により実現するものであるが、下記特許文献２に開示されているように、複数の比較器を用いたハードウェア処理により実現するものも知られている。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特許第３１８８４６７号公報
【特許文献２】特開２０１０−２２４８１８号公報
【発明の概要】
【発明が解決しようとする課題】
【００１４】
上述の特許文献１に記載された最小値・最大値検索処理は、ソフトウェアの制御により処理対象のビット列データを順次２個選択して大小比較を実行するため、ビット列データの個数が増大するとそれに比例して処理時間が増大する。
また、上述の特許文献２に記載された最小値・最大値検索処理は、ビット列データの個数が増大すると多数の比較器を必要とする。
【００１５】
そこで本発明が解決しようとする課題は、処理対象のビット列データが増大してもそれに比例して処理時間が増大せず、多数の比較器を必要とせずに複数のビット列データのうち最小値のビット列データを選択するための情報を出力し、あるいは複数のビット列データのうち最大値のビット列データを選択するための情報を出力するためのハードウェア回路を提供することである。
【課題を解決するための手段】
【００１６】
本発明の一つの態様によれば、Ｎ個（Ｎは２以上の整数）のビット列データそれぞれの同一のビット位置から取り出したビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる同一位置ビット列と、同一位置ビット列のそれぞれのビットをビット判定の対象として選択する選択ビットあるいはビット判定の対象として非選択とする非選択ビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる選択ビット列を入力し、選択ビット列の選択ビットにより選択された同一位置ビット列のビットに基づいて、各ビット列データそれぞれの同一のビット位置の次のビット位置から取り出したビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる次同一位置ビット列のそれぞれのビットを選択する選択ビットあるいは非選択とする非選択ビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる次選択ビット列を出力するビット判定回路を提供する。
【００１７】
また本発明の別の態様によれば、上述のビット判定回路をビット列データのビット幅分直列接続する。そして、最小値のビット列データを選択するための情報を出力し、あるいは複数のビット列データのうち最大値のビット列データを選択するための情報を出力するビット列データ選択回路を提供し、さらに上記ビット列データ選択回路を用いた複数のビット列データの集合から昇順あるいは降順でビット列データを取り出すための情報を出力するビット列データ順次選択回路を提供する。
【発明の効果】
【００１８】
本発明によれば、処理対象のビット列データが増大してもそれに比例して処理時間が増大せず、多数の比較器を必要とせずに複数のビット列データのうちの最小値のビット列データを選択するための情報を出力し、あるいは複数のビット列データのうちの最大値のビット列データを選択するための情報を出力するハードウェア回路、及び、複数のビット列データの集合から昇順あるいは降順でビット列データを取り出すための情報を出力するハードウェア回路を提供することができる。
そして、本発明の提供するハードウェア回路を利用することにより、複数のビット列データのうちの最小値のビット列データを取得し、あるいは複数のビット列データのうちの最大値のビット列データを取得し、あるいは複数のビット列データから昇順あるいは降順でビット列データを取り出すことができる。
【図面の簡単な説明】
【００１９】
【図１Ａ】従来の最小値検索処理について説明する図である。
【図１Ｂ】従来の最大値検索処理について説明する図である。
【図２Ａ】本発明の第１の実施形態における最小値選択処理を概念的に説明する図である。
【図２Ｂ】本発明の第２の実施形態における最大値選択処理を概念的に説明する図である。
【図３Ａ】本発明の第１の実施形態における最小値選択回路を概念的に説明する図である。
【図３Ｂ】本発明の第２の実施形態における最大値選択回路を概念的に説明する図である。
【図４】本発明の第１及び第２の実施形態におけるビット判定回路の第１の実施例を説明する図である。
【図５】本発明の第３の実施形態におけるビット判定回路の第１の実施例を説明する図である。
【図６】本発明の第２の実施形態におけるビット判定回路の第２の実施例を説明する図である。
【図７】本発明の第３の実施形態におけるビット判定回路の第２の実施例を説明する図である。
【図８】本発明の第１及び第２の実施形態におけるビット判定回路の第３の実施例を説明する図である。
【図９】本発明の第３の実施形態におけるビット判定回路の第３の実施例を説明する図である。
【図１０】本発明の第３の実施形態における最大値・最小値選択回路ブロックと周辺回路例を説明する図である。
【図１１Ａ】本発明の第４の実施形態におけるビット列データ昇順選択処理を概念的に説明する図である。
【図１１Ｂ】本発明の第５の実施形態におけるビット列データ降順選択処理を概念的に説明する図である。
【図１２Ａ】本発明の第４及び第５の実施形態におけるビット列データ順次選択回路ブロックと周辺回路例を説明する図である。
【図１２Ｂ】本発明の第６の実施形態におけるビット列データ順次選択回路ブロックと周辺回路例を説明する図である。
【図１３】本発明の第４、第５及び第６の実施形態における次選択ビット設定回路例を説明する図である。
【図１４】本発明の第４の実施形態におけるビット列データ順次選択回路のタイミングチャート例を説明する図である。
【発明を実施するための形態】
【００２０】
以下、本発明を実施するための形態を、図面を参照して説明する。
図２Ａは、本発明の第１の実施形態における最小値選択処理を概念的に説明する図である。本発明の第１の実施形態は、最小値選択に関するものである。図２Ａに例示するビット列データ群１０１は、図１Ａ及び図１Ｂにおいて例示したものと同じである。
【００２１】
図２Ａに示すように、ステップ１では選択ビット列２１０ａには初期値として“１１１１”が設定される。選択ビット列２１０ａの左側に記載されたＥ１、Ｅ２、Ｅ３、Ｅ４は選択ビット列のビットを示しており、Ｅ１、Ｅ２、Ｅ３、Ｅ４の各ビットはビット列データＤ１、Ｄ２、Ｄ３、Ｄ４にそれぞれ対応している。選択ビット列のビットＥｘのビットが“１”であれば、それに対応するビット列データＤｘのビットが、以下において説明するビット判定の対象として選択される。なお、以下の説明において、選択ビット列を符号Ｅにより表記することがある。
【００２２】
ビット列データ群１０１には、各ビット列データのビット位置０、１、２が示されている。ビット位置毎に点線で囲まれたビットを取り出したビット列は同一位置ビット列である。ビット列データＤ１、Ｄ２、Ｄ３、Ｄ４の各ビット位置０、１、２のビットを取り出すことにより、同一位置ビット列２４０、２４１、２４２が構成される。ステップ２以降では、同一ビット列の符号２４０、２４１、２４２は省略されている。なお、以下の説明において同一位置ビット列を符号Ｆにより表記することがある。
【００２３】
ステップ２では、双方向の矢印２２０ａで示すように、選択ビット列２１０ａにより同一位置ビット列２４０のビット判定が行われる。
本発明の第１の実施形態においては、ビット判定は、同一位置ビット列のビットのうち、選択ビット列で選択されたビットが“０”であるかを判定する。この判定結果に基づいて、次のステップで選択ビット列として用いられる次選択ビット列を出力する。
【００２４】
上記判定でビットが“０”であると判定すると、選択されたビット、すなわち“０”であると判定されたビットが属するビット列データに対応する次選択ビット列のビットを“１”とする。ビットが“１”であると判定すると、選択されたビット、すなわち“１”であると判定されたビットが属するビット列データに対応する次選択ビット列のビットを“０”とする。また、同一位置ビット列のビットのうち、選択ビット列で選択されないビットが属するビット列データに対応する次選択ビット列のビットを“０”とする。
【００２５】
図２Ａの例示では、選択ビット列２１０ａは“１１１１”、同一位置ビット列２４０は“１００１”であるから、点線の矢印２３０ｂで示すように、判定結果の次選択ビット列２１１ａは“０１１０”となる。
【００２６】
次のステップ３では、双方向の矢印２２０ｂで示すように、ステップ２における判定結果である次選択ビット列２１１ａが選択ビット列２１０ｂとして用いられ、ビット列データＤ１、Ｄ２、Ｄ３、Ｄ４のビット位置１の同一位置ビット列２４１のビット判定が行われる。
【００２７】
図２Ａの例示では、選択ビット列２１０ｂは“０１１０”、同一位置ビット列２４１は“１１１０”であり、同一位置ビット列２４１の選択されたビットは全て“１”であるから、点線の矢印２３０ｃで示すように、判定結果の次選択ビット列２１１ｂは、選択ビット列２１０ｂと同じ“０１１０”となる。
【００２８】
次のステップ４では、双方向の矢印２２０ｃで示すように、ステップ３における判定結果である次選択ビット列２１１ｂが選択ビット列２１０ｃとして用いられ、ビット列データＤ１、Ｄ２、Ｄ３、Ｄ４のビット位置２の同一位置ビット列２４２のビット判定が行われる。
【００２９】
図２Ａの例示では、選択ビット列２１０ｃは“０１１０”、同一位置ビット列２４２は“１０１０”であるから、点線の矢印２３０ｄで示すように、判定結果の次選択ビット列２１１ｃは、“０１００”となる。
【００３０】
ステップ４で最下位のビット位置におけるビットの判定が終了するので、“１”である次選択ビット列２１１ｃのビットに対応するビット列データがビット列データ群１０１の最小値であることが分かる。
図２Ａの例示では、矢印２５０で示すように、ビットＥ２に対応するビット列データＤ２が最小値であることが分かる。
【００３１】
以上の処理ステップを勝ち残りの競争に例えると、ビット列データの最上位ビットから最下位ビットまで、勝ち残ったビット列データの同一ビット位置のビットが“０”か“１”かの判定を行い“０”のビット列データを勝者、“１”のビット列データを敗者として勝ち残りの選抜を行うものである。同一位置ビット列の選択されたビットが全て“１”であれば次選択ビット列として選択ビット列を出力することは、勝ち残ったビット列データの同一ビット位置のビットが全て“１”であれば、引き分けとして次のビット位置で勝負することに相当する。
【００３２】
上述の説明では、選択ビット列のビットＥｘが“１”であれば、それに対応するビット列データＤｘのビットが、ビット判定の対象として選択される、としたが、ビットＥｘが“０”であれば、それに対応するビット列データＤｘのビットをビット判定の対象として選択することにしても、最小値選択処理が可能であることは明らかである。そこで、ビット列データＤｘのビットをビット判定の対象として選択することを示す選択ビット列のビットＥｘを選択ビット、ビット列データＤｘのビットをビット判定の対象として選択しないことを示す選択ビット列のビットＥｘを非選択ビットということもできる。
【００３３】
また、選択ビット列の初期値として全てのビットを“１”としたが、ビット列データ群の中の一部の最小値のビット列データを選択するのであれば、それら一部のビット列データに対応するビットのみを“１”にすることもできる。
【００３４】
さらに、ビット列データ群の中に同一のビット列データが含まれていてもよい。その場合には、最下位ビット位置のビット判定の出力である次選択ビット列にビットが“１”であるビットが複数存在する可能性が生まれる。
以上の選択ビット列のビット、初期値、及びビット列データの重複についての記述は、第１の実施形態に限らず、後に説明する第２の実施形態及び第３の実施形態、さらには第４の実施形態、第５の実施形態及び第６の実施形態においても同様に成り立つ。
【００３５】
図２Ｂは、本発明の第２の実施形態における最大値選択処理を概念的に説明する図である。本発明の第２の実施形態は、最大値選択に関するものである。図２Ｂに例示するビット列データ群１０１は、図２Ａにおいて例示したものと同じである。図２Ｂに記載されたもののうち、図２Ａに記載されたものと同じものについての説明は省略する。
【００３６】
図２Ｂに示すように、ステップ１では選択ビット列２１２ａには初期値として“１１１１”が設定される。
ステップ２では、双方向の矢印２２１ａで示すように、選択ビット列２１２ａにより同一位置ビット列２４０のビット判定が行われる。
本発明の第２の実施形態においては、ビット判定は、同一位置ビット列のビットのうち、選択ビット列で選択されたビットについて、ビットが“１”であるかを判定する。この判定結果に基づいて、次のステップで選択ビット列として用いられる次選択ビット列を出力する。
【００３７】
上記判定でビットが“１”であると判定すると、選択されたビット、すなわち“１”であると判定されたビットが属するビット列データに対応する次選択ビット列のビットを“１”とする。ビットが“０”であると判定すると、選択されたビット、すなわち“０”であると判定されたビットが属するビット列データに対応する次選択ビット列のビットを“０”とする。また、同一位置ビット列のビットのうち、選択ビット列で選択されないビットが属するビット列データに対応する次選択ビット列のビットを“０”とする。
【００３８】
図２Ｂの例示では、選択ビット列２１２ａは“１１１１”、同一位置ビット列２４０は“１００１”であるから、点線の矢印２３１ｂで示すように、判定結果の次選択ビット列２１３ａは“１００１”となる。
次のステップ３では、双方向の矢印２２１ｂで示すように、ステップ２における判定結果である次選択ビット列２１３ａが選択ビット列２１２ｂとして用いられ、ビット列データＤ１、Ｄ２、Ｄ３、Ｄ４のビット位置１の同一位置ビット列２４１のビット判定が行われる。
【００３９】
図２Ｂの例示では、選択ビット列２１２ｂは“１００１”、同一位置ビット列２４１は“１１１０”であり、点線の矢印２３１ｃで示すように、判定結果の次選択ビット列２１３ｂは“１０００”となる。
【００４０】
次のステップ４では、双方向の矢印２２１ｃで示すように、ステップ３における判定結果である次選択ビット列２１３ｂが選択ビット列２１２ｃとして用いられ、ビット列データＤ１、Ｄ２、Ｄ３、Ｄ４のビット位置２の同一位置ビット列２４２のビット判定が行われる。
【００４１】
図２Ｂの例示では、選択ビット列２１２ｃは“１０００”、同一位置ビット列２４２は“１０１０”であるから、点線の矢印２３１ｄで示すように、判定結果の次選択ビット列２１３ｃは、“１０００”となる。
【００４２】
ステップ４で最下位のビット位置におけるビットの判定が終了するので、“１”である次選択ビット列２１３ｃのビットに対応するビット列データがビット列データ群１０１の最大値であることが分かる。
図２Ｂの例示では、矢印２５１で示すように、ビットＥ１に対応するビット列データＤ１が最大値であることが分かる。
【００４３】
次に本発明の第１の実施形態及び第２の実施形態に係る回路について、図３Ａ及び図３Ｂを参照して説明する。図３Ａ及び図３Ｂにおいて、図２Ａ及び図２Ｂと同様な部分の説明は省略する。
【００４４】
図３Ａは、本発明の第１の実施形態における最小値選択回路の概要を説明する図である。
図３Ａに例示するデータレジスタ群３０１には、図２Ａ及び図２Ｂに例示したビット列データ群１０１が格納されている。また、選択ビットレジスタ３１０には、図２Ａに例示した選択ビット列２１０ａが格納されている。
図３Ａに示すように最小値選択回路３００ａは、同一位置ビット列２４０に対応するビット判定回路３２０ａ、同一位置ビット列２４１に対応するビット判定回路３２０ｂ、及び同一位置ビット列２４２に対応するビット判定回路３２０ｃを含む。第１の実施の形態では、これらのビット判定回路はビットが“０”であるかの判定を行う。これらのビット判定回路は基本的には同じ構成を用いることができる。
【００４５】
データレジスタ群３０１に格納されたビット列データＤ１、Ｄ２、Ｄ３、Ｄ４の同一ビット位置のビットが取り出された同一位置ビット列２４０、２４１、２４２は、それぞれ４ビットの並列バス３４０ａ、３４０ｂ、３４０ｃにより、ビット判定回路３２０ａ、３２０ｂ、３２０ｃに入力される。
【００４６】
選択ビットレジスタ３１０に格納された選択ビット列は、４ビットの並列バス３３０ａにより、ビット判定回路３２０ａに入力される。ビット判定回路３２０ａのビット判定結果出力３１０ｂは、４ビットの並列バス３３０ｂによりビット判定回路３２０ｂに入力される。次に、ビット判定回路３２０ｂのビット判定結果出力３１０ｃは、４ビットの並列バス３３０ｃによりビット判定回路３２０ｃに入力される。さらに、ビット判定回路３２０ｃのビット判定結果出力は、４ビットの並列バス３３０ｄにより選択結果レジスタ３６０に入力される。
図３Ａの例示では、選択結果レジスタ３６０には、図２Ａに示す次選択ビット列２１１ｃが格納され、矢印３５０で示すように、ビットＥ２に対応するビット列データＤ２が最小値であることが分かる。
【００４７】
図３Ｂは、本発明の第２の実施形態における最大値選択回路の概要を説明する図である。
図３Ｂに例示するデータレジスタ群３０１には、図２Ａ及び図２Ｂに例示したビット列データ群１０１が格納されている。また、選択ビットレジスタ３１０には、図２Ｂに例示した選択ビット列２１２ａが格納されている。
図３Ｂに示すように最大値選択回路３００ｂは、同一位置ビット列２４０に対応するビット判定回路３２１ａ、同一位置ビット列２４１に対応するビット判定回路３２１ｂ、及び同一位置ビット列２４２に対応するビット判定回路３２１ｃを含む。第２の実施の形態では、これらのビット判定回路はビットが“１”であるかの判定を行う。これらのビット判定回路は基本的には同じ構成を用いることができる。
【００４８】
データレジスタ群３０１に格納されたビット列データＤ１、Ｄ２、Ｄ３、Ｄ４の同一ビット位置のビットが取り出された同一位置ビット列２４０、２４１、２４２は、それぞれ４ビットの並列バス３４１ａ、３４１ｂ、３４１ｃにより、ビット判定回路３２１ａ、３２１ｂ、３２１ｃに入力される。
【００４９】
選択ビットレジスタ３１０に格納された選択ビット列は、４ビットの並列バス３３１ａにより、ビット判定回路３２１ａに入力される。ビット判定回路３２１ａのビット判定結果出力３１１ｂは、４ビットの並列バス３３１ｂによりビット判定回路３２１ｂに入力される。次に、ビット判定回路３２１ｂのビット判定結果出力３１１ｃは、４ビットの並列バス３３１ｃによりビット判定回路３２１ｃに入力される。さらに、ビット判定回路３２１ｃのビット判定結果出力は、４ビットの並列バス３３１ｄにより選択結果レジスタ３６０に入力される。
図３Ｂの例示では、選択結果レジスタ３６０には、図２Ｂに示す次選択ビット列２１３ｃが格納され、矢印３５１で示すように、ビットＥ１に対応するビット列データＤ１が最大値であることが分かる。
【００５０】
次に、図４から図９を参照して、ビット判定回路の実施例を説明する。
図４は、本発明の第１の実施形態及び第２の実施形態におけるビット判定回路の第１の実施例を説明する図である。図４の（ａ）に示すのは、上記本発明の第１の実施形態及び第２の実施形態に共通なビット判定回路の第１の実施例の回路構成である。図４の（ｂ）に示すのは、本発明の第１の実施形態におけるビット判定回路の第１の実施例の構成要素の入出力論理を説明するものである。また、図４の（ｃ）に示すのは、本発明の第２の実施形態におけるビット判定回路の第１の実施例の構成要素の入出力論理を説明するものである。なお、以下の説明においては、ビット列データ群はｎ個のビット列データを含むものとする。なおｎビットの並列バスの各ビットを添え字ｘで表記することがある。
【００５１】
図４の（ａ）に示すように、ビット判定回路３２１１は、一致判定器４２０、全不一致判定器４３０、判定結果選択器４４０を含んでいる。ビット判定回路３２１１には、ｎビットの並列バス３４０により同一位置ビット列Ｆが入力され、またｎビットの並列バス３３０により選択ビット列Ｅが入力される。
【００５２】
上記入力された同一位置ビット列Ｆと選択ビット列Ｅはそれぞれ一致判定器４２０と全不一致判定器４３０に入力される。一致判定器４２０では同一位置ビット列Ｆと選択ビット列Ｅのビットごとの演算が行われ、新たなビット列Ｑが求められる。（このように、ビット列のビットごとの演算により同じビット幅の新たなビット列を求めること、あるいは１つのビットを求めることをビット列演算ということがある。）全不一致判定器４３０では、同一位置ビット列Ｄと選択ビット列Ｅのビット列演算により１つのビットであるＲを求める。
そして、判定結果選択器４４０は、全不一致判定器４３０の出力Ｒが“１”であれば、その出力ビット列Ｚ（次選択ビット列）として選択ビット列Ｅをｎビットの並列バス３３１に出力し、全不一致判定器４３０の出力Ｒが“０”であれば、その出力ビット列Ｚとして一致判定器４２０の出力であるビット列Ｑをｎビットの並列バス３３１に出力する。
【００５３】
本発明の第１の実施形態における一致判定器４２０のビット列演算Ｑと全不一致判定器４３０のビット列演算Ｒの論理式は図４の（ｂ）に記載され、第２の実施形態における一致判定器４２０のビット列演算Ｑと全不一致判定器４３０のビット列演算Ｒの論理式は図４の（ｃ）に記載されている。
【００５４】
図４の（ｂ）に記載されているように、最小値を選択する第１の実施形態の場合は、一致判定器４２０のビット列演算の出力であるビット列ＱのビットＱｘは同一位置ビット列ＦのビットＦｘの論理否定と選択ビット列ＥのビットＥｘとの論理積であり、Ｅｘが“１”でＦｘが“０”に対するＱｘのみ“１”となり、ビット列Ｑの他のビットは“０”である。また、全不一致判定器４３０のビット列演算Ｒは、ビットごとのＦｘの論理否定とＥｘの論理積の論理否定を全てのビットについて論理積を取ったものである。Ｒの値は、Ｅｘが“１”である全てのビットについてＦｘが“１”のときのみ“１”であり、Ｅｘが“１”でありＦｘが“０”のビットが少なくとも１つ存在する場合は“０”である。
【００５５】
また、図４の（ｃ）に記載されているように、最大値を選択する第２の実施形態の場合は、一致判定器４２０のビット列演算の出力であるビット列ＱのビットＱｘは同一位置ビット列ＦのビットＦｘと選択ビット列ＥのビットＥｘとの論理積であり、Ｅｘが“１”でＦｘが“１”に対するＱｘのみ“１”となり、他のビット列Ｑのビットは“０”である。また、全不一致判定器４３０のビット列演算Ｒは、ビットごとのＦｘとＥｘの論理積の否定を全てのビットについて論理積を取ったものである。Ｒの値は、Ｅｘが“１”である全てのビットについてＦｘが“０”のときのみ“１”であり、Ｅｘが“１”でありＦｘが“１”のビットが少なくとも１つ存在する場合は“０”である。
【００５６】
図５は、本発明の第３の実施形態におけるビット判定回路の第１の実施例を説明する図である。本発明の第３の実施形態は、共通の回路で最小値選択と最大値選択を可能とするものである。
図５の（ａ）に示すのは、上記本発明の第３の実施形態のビット判定回路の第１の実施例の回路構成である。図５の（ｂ）に示すのは、本発明の第３の実施形態におけるビット判定回路の第１の実施例の構成要素の入出力論理を説明するものである。
【００５７】
図５の（ａ）に示すように、ビット判定回路３２３１は、図４に示す一致判定器４２０、全不一致判定器４３０、判定結果選択器４４０に加えて判定ビット設定器４１０を含んでいる。判定ビット設定器４１０は、シリアルバス３２１により入力される判定ビットＩに応じて並列バス３４０から入力される同一位置ビット列Ｆのビットをそのまま、あるいは反転させたビット列Ｐを出力し、一致判定回路４２０と全不一致判定回路４３０に供給する。
【００５８】
最小値を選択する場合は判定ビットＩは“０”であり、最大値を選択する場合には判定ビットＩは“１”である。図５の（ｂ）に示すビット列Ｐの各ビットＰｘはＩの否定とＦｘの否定の論理積とＩとＦｘの論理積との論理和である。すなわち、Ｉが“０”であればＰｘはＦｘであり、Ｉが“０”であればＰｘはＦｘのビットを反転したものである。
図５の（ｂ）に示すＱｘ及びＲに上述のＦｘを代入すると、最小値を選択する場合は図４の（ｂ）に示すものと同じになり、最大値を選択る場合は図４の（ｃ）に示すものと同じになる。したがって、共通の回路を最小値あるいは最大値選択に用いることができる。
上述の第３の実施の形態における判定ビット設定器４１０の導入は、ビット列データ群のうちの最小値のビット列データは、ビット列データ群のビット列データの全てのビットを反転させたとき、最大値のビット列データとなることに基づいている。
【００５９】
図６は、本発明の第２の実施形態におけるビット判定回路の第２の実施例を説明する図である。図６の（ａ）に示すのは、上記本発明の第２の実施形態のビット判定回路の第２の実施例の回路構成である。図６の（ｂ）に示すのは、本発明の第２の実施形態におけるビット判定回路の第２の実施例の構成要素の入出力論理を説明するものである。
【００６０】
図６の（ａ）に示すように、ビット判定回路３２１２は、一致判定器４２０、全不一致判定器４３０、判定結果選択器４４０を含んでいる。ビット判定回路３２１２には、ｎビットの並列バス３４０により同一位置ビット列Ｆが入力され、またｎビットの並列バス３３０により選択ビット列Ｅが入力される。以上の構成は、図４の（ａ）に示す第１の実施形態及び第２の実施形態に共通なビット判定回路の第１の実施例と同様であるが、この第１の実施例では一致判定と全不一致判定を並行して行うのに対して、図６の（ａ）に示すものは、先に全不一致判定を行い、全不一致判定の結果に基づいて判定結果を選択し、さらにその選択結果を基に一致判定を行うものである。
【００６１】
上記入力された同一位置ビット列Ｆは、全不一致判定器４３０と判定結果選択器４４０の０側の端子に入力される。選択ビット列Ｅは、全不一致判定器４３０と一致判定器４２０に入力される。判定結果選択器４４０の１側の端子にはビットが全て“１”であるｎビットのビット列が入力される。このビット“１”は、先に述べた選択ビットとしてのものである。全不一致判定器４３０の出力Ｒは判定結果選択器４４０の選択端子ｓに接続され、Ｒの値が“０”であれば０側の端子に入力される選択ビット列Ｆを、Ｒの値が“１”であれば１側の端子に入力されるビットが全て“１”であるｎビットのビット列を、ビット列Ｚとして一致判定器４２０に出力する。
【００６２】
図６の（ｂ）に記載されているように、最大値を選択する第２の実施形態の場合の全不一致判定器４３０の出力Ｒは、図４の（ｃ）に記載されている第１の実施例と同じである。
図６の（ｂ）には、判定結果選択器４４０の出力Ｚの論理式が記載されているが、これは一致判定器４２０の出力ビット列Ｑの論理式を表すためである。この出力Ｚのビット毎の論理式は、Ｒの否定とＦｘの論理積とＲの論理和である。したがってＲが“１”であればＺｘはＲとなり、全てのＺｘの値は“１”である。Ｒが“０”であればＺｘはＦｘとなることから、先に述べた判定結果の選定が行われる。ＱｘはＺｘとＥｘの論理積であるから、並列バス３３１に出力されるＱｘは、Ｒが“１”であればＥｘ，Ｒが“０”であればＦｘとＥｘの論理積となり、図４の（ｃ）に示すものと同じになる。
【００６３】
なお、先に述べたように、ビット列データ群の最小のビット列データは、ビット列データ群のビット列データの全てのビットを反転させたとき、最大のビット列データとなることから、同一位置ビット列Ｆのビットを反転させたビット列を入力することにより図６の（ａ）に示すビット判定回路３２１２を最小値選択に用いることもできる。
【００６４】
図７は、本発明の第３の実施形態におけるビット判定回路の第２の実施例を説明する図である。図７の（ａ）に示すのは、上記本発明の第３の実施形態のビット判定回路の第２の実施例の回路構成である。図７の（ｂ）に示すのは、本発明の第３の実施形態におけるビット判定回路の第２の実施例の構成要素の入出力論理を説明するものである。
【００６５】
図７の（ａ）に示すように、ビット判定回路３２３２は、図６の（ａ）に示すビット判定回路３２１２の同一位置ビット列Ｆの入力に、図５の（ａ）を参照して説明した判定ビット設定器４１０を挿入したものである。したがって、図７の（ｂ）に示すＲ、Ｚｘ、Ｑｘの論理式は、図６の（ｂ）に示すもののＦｘにＰｘを代入したものであるから、これ以上の説明は省略する。
【００６６】
図８は、本発明の第１の実施形態及び第２の実施形態におけるビット判定回路の第３の実施例を説明する図である。図８の（ａ）に示すのは、上記本発明の第１の実施形態及び第２の実施形態に共通なビット判定回路の第３の実施例の回路構成である。図８の（ｂ）に示すのは、本発明の第１の実施形態におけるビット判定回路の第３の実施例の構成要素の入出力論理を説明するものである。また、図８の（ｃ）に示すのは、本発明の第２の実施形態におけるビット判定回路の第３の実施例の構成要素の入出力論理を説明するものである。
【００６７】
図８の（ａ）に示すように、ビット判定回路３２１３は、一致判定器４２０、全不一致判定器４３１、判定結果選択器４４０を含んでいる。一致判定器４２０には、ｎビットの並列バス３４０により同一位置ビット列Ｆが入力され、またｎビットの並列バス３３０により選択ビット列Ｅが入力され、同一位置ビット列Ｆと選択ビット列Ｅのビット列演算が行われてビット列Ｑが求められる。以上の構成は、先に一致判定を行い、次に一致判定結果に基づいて全不一致判定を行い、さらに不判定結果に基づいて判定結果を選択するものである。
【００６８】
ビット列Ｑは全不一致判定器４３１と判定結果選択器４４０に入力される。全不一致判定器４３１は、ビット列Ｑの各ビットＱｘの値から１つのビットであるＲを求める。
そして、判定結果選択器４４０は、全不一致判定器４３１の出力Ｒが“１”であれば、その出力ビット列Ｚ（次選択ビット列）として選択ビット列Ｅをｎビットの並列バス３３１に出力し、全不一致判定器４３１の出力Ｒが“０”であれば、その出力ビット列Ｚとして一致判定器４２０の出力であるビット列Ｑをｎビットの並列バス３３１に出力する。
【００６９】
図８の（ｂ）に記載されているように、最小値を選択する第１の実施形態の場合は、一致判定器４２０のビット列演算の出力であるビット列ＱのビットＱｘは同一位置ビット列ＦのビットＦｘの否定と選択ビット列ＥのビットＥｘとの論理積であり、Ｅｘが“１”でＦｘが“０”に対するＱｘのみ“１”となり、ビット列Ｑの他のビットは“０”である。また、全不一致判定器４３１の出力Ｒは、Ｑｘの否定の論理積である。したがって、Ｒの値は、Ｅｘが“１”でＦｘが“０”となるビットの組み合わせがないとき、いいかえればＥｘが“１”であるＦｘが全て“１”のときにのみ“１”になり、判定結果選択器４４０は選択ビット列Ｅを出力し、その他のときは“０”であるから判定結果選択器４４０は一致判定器４２０の出力であるビット列Ｑを出力する。
【００７０】
また、図８の（ｃ）に記載されているように、最大値を選択する第２の実施形態の場合は、一致判定器４２０のビット列演算の出力であるビット列ＱのビットＱｘは同一位置ビット列ＦのビットＦｘと選択ビット列ＥのビットＥｘとの論理積であり、Ｅｘが“１”でＦｘが“１”に対するＱｘのみ“１”となり、他のビット列Ｑのビットは“０”である。また、全不一致判定器４３１の出力Ｒは、Ｑｘの否定の論理積である。したがって、Ｒの値は、Ｅｘが“１”でＦｘが“１”となるビットの組み合わせがないとき、いいかえればＥｘが“１”であるＦｘが全て“０”のときにのみ“１”になり、その他のときは“０”である。Ｒの値が“０”であれば判定結果選択器４４０は一致判定器４２０の出力であるビット列Ｑを出力し、Ｒの値が“１”であれば判定結果選択器４４０は選択ビット列Ｅを出力する。
【００７１】
図９は、本発明の第３の実施形態におけるビット判定回路の第３の実施例を説明する図である。図９の（ａ）に示すのは、上記本発明の第３の実施形態のビット判定回路の第３の実施例の回路構成である。図９の（ｂ）に示すのは、本発明の第３の実施形態におけるビット判定回路の第３の実施例の構成要素の入出力論理を説明するものである。
【００７２】
図９の（ａ）に示すように、ビット判定回路３２３３は、図８の（ａ）に示すビット判定回路３２１３の同一位置ビット列Ｆの入力に、図５の（ａ）を参照して説明した判定ビット設定器４１０を挿入したものである。したがって、図９の（ｂ）に示すＲ、Ｑｘの論理式は、図８の（ｃ）に示すもののＦｘにＰｘを代入したものであるから、これ以上の説明は省略する。
【００７３】
図１０は、本発明の第３の実施形態における最大値・最小値選択回路ブロックとその周辺回路例を説明する図である。図１０に示す最大値・最小値選択回路３００ｃは、ｎ個のビット幅がｍのビット列データに適合するものであり、最上位の０ビット目の同一位置ビット列のビットを判定するビット判定回路３２０１から最下位のｍ−１ビット目の同一位置ビット列のビットを判定するビット判定回路３２０ｍまで直列にｍ個のビット判定回路が接続されている。
【００７４】
周辺回路としては、選択ビット列の初期値を設定する選択ビットレジスタ３１０、ビット列データ群を格納するデータレジスタ群３０１、最終段のビット判定回路の出力を保持する選択結果レジスタ３６０、判定ビットを保持する判定フラグ３９０が例示されている。
【００７５】
選択ビットレジスタ３１０に設定された選択ビット列はビット判定回路３２０１に入力される。判定値フラグ３９０に保持された判定ビットはバス３２１を介してｍ段のビット判定回路に並行して供給され、最大値・最小値選択回路が最小値選択回路として動作するのか、最大値選択回路として動作するのかを決定する。
データレジスタ群３０１からは、０ビット目の同一位置ビット列からｍ−１ビット目の同一位置ビット列が、ｎビットの並列バス３４０１から３４０ｍを介してビット判定回路３２０１からビット判定回路３２０ｍに供給される。
【００７６】
各ビット判定回路は入力された選択ビット列に基づいて同一位置ビット列のビットを判定して次選択ビット列を演算し、次段のビット判定回路に選択ビット列として出力する。最終段のビット判定回路３２０ｍの出力は選択結果レジスタ３６０に保持され、データレジスタ群３０１に格納された最小のビット列データあるいは最大のビット列データを特定するために用いることができる。
【００７７】
以上、本発明の第１乃至第３の実施の形態について詳細に説明したことから明らかなとおり、本発明によれば受動回路により最小値選択回路、最大値選択回路及び最大値・最小値選択回路を構成できるので、高速な動作が可能である。また、上述の説明に限らず本発明の実施の形態について種々の変形が可能なことは当業者に明らかである。
【００７８】
次に、上述の最小値選択回路、最大値選択回路あるいは最大値・最小値選択回路を用いた、複数のビット列データの集合から昇順あるいは降順でビット列データを取り出すための情報を出力するビット列データ順次選択処理について説明する。なお、以下の説明において、最大値・最小値選択回路及び最大値・最小値選択処理の用語を、最小値選択回路及び最小値選択処理並びに最大値選択回路及び最大値選択処理を含むものとして使用する場合がある。
【００７９】
先に述べたように、最大値・最小値選択処理において選択ビット列の初期値は全て選択ビットである必要はない。そこで、例えば昇順でビット列データを取り出すためには、最初の最小値選択処理により得られた次選択ビットを非選択ビットに置換した選択ビット列により最小値選択処理を行い、以下得られた次選択ビットをさらに非選択ビットに置換した選択ビット列よる最小値選択処理を繰り返し、各最小値選択処理により得られる次選択ビット列を、ビット列データを昇順で取り出すための情報として出力すればよい。
以下の説明においては、上述の各最小値選択処理により得られる次選択ビット列を選択結果ビット列と呼ぶことがある。同様に、各最大値選択処理により得られる次選択ビット列を選択結果ビット列と呼ぶことがある。
【００８０】
図１１Ａは、本発明の第４の実施形態におけるビット列データ昇順選択処理を概念的に説明する図である。図１１Ａに例示する同一ビット位置ビット列２４０、２４１、２４２は、図２Ａに例示したビット列データ群１０１から得られるものと同じである。
【００８１】
図１１Ａに示すステップ１は最初の最小値選択処理である。図１１Ａに示すように、ステップ１では、選択ビット列２１０ａＡには初期値として“１１１１”が設定されている。双方向の矢印２２０ａＡで示すように、図２Ａに例示したステップ２と同様に選択ビット列２１０ａＡにより同一ビット位置ビット列２４０のビット判定が行われ、引き続き点線の矢印２３０ｂＡで示すように、ビット判定の結果得られる次選択ビット列２１１ａＡによる次のビット判定が行われる。
【００８２】
次のビット判定では、双方向の矢印２２０ｂＡで示すように、図２Ａに例示したステップ３と同様に次選択ビット列２１１ａＡを選択ビット列２１０ｂＡとして同一ビット位置ビット列２４１のビット判定が行われ、引き続き点線の矢印２３０ｃＡで示すように、ビット判定の結果得られる次選択ビット列２１１ｂＡによりさらに次のビット判定が行われる。
【００８３】
次のビット判定では、双方向の矢印２２０ｃＡで示すように、図２Ａに例示したステップ４と同様に次選択ビット列２１１ｂＡを選択ビット列２１０ｃＡとして同一ビット位置ビット列２４２のビット判定が行われ、点線の矢印２３０ｄＡで示すように、ビット判定の結果得られる選択結果ビット列２１１ｃＡのビットＥ２に対応するビット列データＤ２が最小値であることが分かる。
【００８４】
次に双方向の矢印２２０Ａで示す選択ビット列２１０ａＡと選択結果ビット列２１１ｃＡにより次選択ビット設定のためのビット演算がおこなわれ、点線の矢印２３０Ａで示すように、次選択ビット列２１１Ａが求められる。図１１Ａの記載から明らかなように、次選択ビット列２１１Ａは、ステップ１における初期値である選択ビット列２１０ａＡのうち、ステップ１の最小値選択処理の結果得られる選択結果ビット列２１１ｃＡのビットのうちの選択ビットであるＥ２を非選択ビットに置換したものである。
【００８５】
図１１Ａに示すステップ２は次の最小値選択処理である。図１１Ａに示すように、ステップ２では、ステップ１で求めた次選択ビット列２１１Ａを最小値選択処理の初期値である選択ビット列２１０ａＢとして設定する。双方向の矢印２２０ａＢで示すように、図２Ａに例示したステップ２と同様に選択ビット列２１０ａＢにより同一ビット位置ビット列２４０のビット判定が行われ、引き続き点線の矢印２３０ｂＢで示すように、ビット判定の結果得られる次選択ビット列２１１ａＢによる次のビット判定が行われる。
【００８６】
次のビット判定では、双方向の矢印２２０ｂＢで示すように、図２Ａに例示したステップ３と同様に次選択ビット列２１１ａＢを選択ビット列２１０ｂＢとして同一ビット位置ビット列２４１のビット判定が行われ、引き続き点線の矢印２３０ｃＢで示すように、ビット判定の結果得られる次選択ビット列２１１ｂＢによりさらに次のビット判定が行われる。
【００８７】
次のビット判定では、双方向の矢印２２０ｃＢで示すように、図２Ａに例示したステップ４と同様に次選択ビット列２１１ｂＢを選択ビット列２１０ｃＢとして同一ビット位置ビット列２４２のビット判定が行われ、点線の矢印２３０ｄＢで示すように、ビット判定の結果得られる選択結果ビット列２１１ｃＢのビットＥ３に対応するビット列データＤ３が次の最小値であることが分かる。
【００８８】
次に双方向の矢印２２０Ｂで示す選択ビット列２１０ａＢと選択結果ビット列２１１ｃＢにより次選択ビット設定のためのビット演算がおこなわれ、点線の矢印２３０Ｂで示すように、次選択ビット列２１１Ｂが求められる。ステップ１の場合と同様に、次選択ビット列２１１Ｂは、ステップ２における初期値である選択ビット列２１０ａＢのうち、ステップ２の最小値選択処理の結果得られる選択結果ビット列２１１ｃＢのビットうちの選択ビットであるＥ３を非選択ビットに置換したものである。
【００８９】
図１１Ａに示すステップ３はさらに次の最小値選択処理である。図１１Ａに示すように、ステップ３では、ステップ２で求めた次選択ビット列２１１Ｂを最小値選択処理の初期値である選択ビット列２１０ａＣとして設定する。双方向の矢印２２０ａＣで示すように、図２Ａに例示したステップ２と同様に選択ビット列２１０ａＣにより同一ビット位置ビット列２４０のビット判定が行われ、引き続き点線の矢印２３０ｂＣで示すように、ビット判定の結果得られる次選択ビット列２１１ａＣによる次のビット判定が行われる。
【００９０】
次のビット判定では、双方向の矢印２２０ｂＣで示すように、図２Ａに例示したステップ３と同様に次選択ビット列２１１ａＣを選択ビット列２１０ｂＣとして同一ビット位置ビット列２４１のビット判定が行われ、引き続き点線の矢印２３０ｃＣで示すように、ビット判定の結果得られる次選択ビット列２１１ｂＣによりさらに次のビット判定が行われる。
【００９１】
次のビット判定では、双方向の矢印２２０ｃＣで示すように、図２Ａに例示したステップ４と同様に次選択ビット列２１１ｂＣを選択ビット列２１０ｃＣとして同一ビット位置ビット列２４２のビット判定が行われ、点線の矢印２３０ｄＣで示すように、ビット判定の結果得られる選択結果ビット列２１１ｃＣのビットＥ４に対応するビット列データＤ４が次の最小値であることが分かる。
【００９２】
次に双方向の矢印２２０Ｃで示す選択ビット列２１０ａＣと選択結果ビット列２１１ｃＣにより次選択ビット設定のためのビット演算がおこなわれ、点線の矢印２３０Ｃで示すように、次選択ビット列２１１Ｃが求められる。次選択ビット列２１１Ｃは、ステップ３における初期値である選択ビット列２１０ａＣのうち、ステップ３の最小値選択処理の結果得られる選択結果ビット列２１１ｃＣのビットのうちの選択ビットであるＥ４を非選択ビットに置換したものである。
【００９３】
図１１Ａに示すステップ４は最後の最小値選択処理である。結果的には最大値にアクセスするための情報が求められる。図１１Ａに示すように、ステップ４では、ステップ３で求めた次選択ビット列２１１Ｃを最小値選択処理の初期値である選択ビット列２１０ａＤとして設定する。双方向の矢印２２０ａＤで示すように、図２Ａに例示したステップ２と同様に選択ビット列２１０ａＤにより同一ビット位置ビット列２４０のビット判定が行われ、引き続き点線の矢印２３０ｂＤで示すように、ビット判定の結果得られる次選択ビット列２１１ａＤによる次のビット判定が行われる。
【００９４】
次のビット判定では、双方向の矢印２２０ｂＤで示すように、図２Ａに例示したステップ３と同様に次選択ビット列２１１ａＤを選択ビット列２１０ｂＤとして同一ビット位置ビット列２４１のビット判定が行われ、引き続き点線の矢印２３０ｃＤで示すように、ビット判定の結果得られる次選択ビット列２１１ｂＤによりさらに次のビット判定が行われる。
【００９５】
次のビット判定では、双方向の矢印２２０ｃＤで示すように、図２Ａに例示したステップ４と同様に次選択ビット列２１１ｂＤを選択ビット列２１０ｃＤとして同一ビット位置ビット列２４２のビット判定が行われ、点線の矢印２３０ｄＤで示すように、ビット判定の結果得られる選択結果ビット列２１１ｃＤのビットＥ１に対応するビット列データＤ１が次の最小値であることが分かる。
【００９６】
次に双方向の矢印２２０Ｄで示す選択ビット列２１０ａＤと選択結果ビット列２１１ｃＤにより次選択ビット設定のためのビット演算がおこなわれ、点線の矢印２３０Ｄで示すように、次選択ビット列２１１Ｄが求められる。次選択ビット列２１１Ｄは、ステップ４における初期値である選択ビット列２１０ａＤのうち、ステップ４の最小値選択処理の結果得られる選択結果ビット列２１１ｃＤのビットのうちの選択ビットであるＥ１を非選択ビットに置換したものである。
【００９７】
図１１Ａに示すように、次選択ビット列２１１Ｄのビットは全て非選択ビットであり、検索の終了が判定される。以上の処理により、複数のビット列データの集合｛Ｄ１，Ｄ２，Ｄ３，Ｄ４｝から昇順でビット列データを取り出すための情報として選択結果ビット列２１１ｃＡ、２１１ｃＢ、２１１ｃＣ、２１１ｃＤを出力することができる。
【００９８】
図１１Ｂは、本発明の第５の実施形態におけるビット列データ降順選択処理を概念的に説明する図である。図１１Ｂに例示する同一ビット位置ビット列２４０、２４１、２４２は、図２Ｂに例示したビット列データ群１０１から得られるものと同じである。
【００９９】
図１１Ｂに示すステップ１は最初の最大値選択処理である。図１１Ｂに示すように、ステップ１では選択ビット列２１２ａＡには初期値として“１１１１”が設定されている。双方向の矢印２２１ａＡで示すように、図２Ｂに例示したステップ２と同様に選択ビット列２１２ａＡにより同一ビット位置ビット列２４０のビット判定が行われ、引き続き点線の矢印２３１ｂＡで示すように、ビット判定の結果得られる次選択ビット列２１３ａＡによる次のビット判定が行われる。
【０１００】
次のビット判定では、双方向の矢印２２１ｂＡで示すように、図２Ｂに例示したステップ３と同様に次選択ビット列２１３ａＡを選択ビット列２１２ｂＡとして同一ビット位置ビット列２４１のビット判定が行われ、引き続き点線の矢印２３１ｃＡで示すように、ビット判定の結果得られる次選択ビット列２１３ｂＡによりさらに次のビット判定が行われる。
【０１０１】
次のビット判定では、双方向の矢印２２１ｃＡで示すように、図２Ｂに例示したステップ４と同様に次選択ビット列２１３ｂＡを選択ビット列２１２ｃＡとして同一ビット位置ビット列２４２のビット判定が行われ、点線の矢印２３１ｄＡで示すように、ビット判定の結果得られる選択結果ビット列２１３ｃＡのビットＥ１に対応するビット列データＤ１が最大値であることが分かる。
【０１０２】
次に双方向の矢印２２１Ａで示す選択ビット列２１２ａＡと選択結果ビット列２１３ｃＡにより次選択ビット設定のためのビット演算がおこなわれ、点線の矢印２３１Ａで示すように、次選択ビット列２１３Ａが求められる。図１１Ｂの記載から明らかなように、次選択ビット列２１３Ａは、ステップ１における初期値である選択ビット列２１２ａＡのうち、ステップ１の最大値選択処理の結果得られる選択結果ビット列２１３ｃＡのビットのうちの選択ビットであるＥ１を非選択ビットに置換したものである。
【０１０３】
図１１Ｂに示すステップ２は次の最大値選択処理である。図１１Ｂに示すように、ステップ２では、ステップ１で求めた次選択ビット列２１３Ａを最大値選択処理の初期値である選択ビット列２１２ａＢとして設定する。双方向の矢印２２１ａＢで示すように、図２Ｂに例示したステップ２と同様に選択ビット列２１２ａＢにより同一ビット位置ビット列２４０のビット判定が行われ、引き続き点線の矢印２３１ｂＢで示すように、ビット判定の結果得られる次選択ビット列２１３ａＢによる次のビット判定が行われる。
【０１０４】
次のビット判定では、双方向の矢印２２１ｂＢで示すように、図２Ｂに例示したステップ３と同様に次選択ビット列２１３ａＢを選択ビット列２１２ｂＢとして同一ビット位置ビット列２４１のビット判定が行われ、引き続き点線の矢印２３１ｃＢで示すように、ビット判定の結果得られる次選択ビット列２１３ｂＢによりさらに次のビット判定が行われる。
【０１０５】
次のビット判定では、双方向の矢印２２１ｃＢで示すように、図２Ｂに例示したステップ４と同様に次選択ビット列２１３ｂＢを選択ビット列２１２ｃＢとして同一ビット位置ビット列２４２のビット判定が行われ、点線の矢印２３１ｄＢで示すように、ビット判定の結果得られる選択結果ビット列２１３ｃＢのビットＥ４に対応するビット列データＤ４が次の最大値であることが分かる。
【０１０６】
次に双方向の矢印２２１Ｂで示す選択ビット列２１２ａＢと選択結果ビット列２１３ｃＢにより次選択ビット設定のためのビット演算がおこなわれ、点線の矢印２３１Ｂで示すように、次選択ビット列２１３Ｂが求められる。ステップ１の場合と同様に、次選択ビット列２１３Ｂは、ステップ２における初期値である選択ビット列２１２ａＢのうち、ステップ２の最大値選択処理の結果得られる選択結果ビット列２１３ｃＢのビットうちの選択ビットであるＥ４を非選択ビットに置換したものである。
【０１０７】
図１１Ｂに示すステップ３はさらに次の最大値選択処理である。図１１Ｂに示すように、ステップ３では、ステップ２で求めた次選択ビット列２１３Ｂを最大値選択処理の初期値である選択ビット列２１２ａＣとして設定する。双方向の矢印２２１ａＣで示すように、図２Ｂに例示したステップ２と同様に選択ビット列２１２ａＣにより同一ビット位置ビット列２４０のビット判定が行われ、引き続き点線の矢印２３１ｂＣで示すように、ビット判定の結果得られる次選択ビット列２１３ａＣによる次のビット判定が行われる。
【０１０８】
次のビット判定では、双方向の矢印２２１ｂＣで示すように、図２Ｂに例示したステップ３と同様に次選択ビット列２１３ａＣを選択ビット列２１２ｂＣとして同一ビット位置ビット列２４１のビット判定が行われ、引き続き点線の矢印２３１ｃＣで示すように、ビット判定の結果得られる次選択ビット列２１３ｂＣによりさらに次のビット判定が行われる。
【０１０９】
次のビット判定では、双方向の矢印２２１ｃＣで示すように、図２Ｂに例示したステップ４と同様に次選択ビット列２１３ｂＣを選択ビット列２１２ｃＣとして同一ビット位置ビット列２４２のビット判定が行われ、点線の矢印２３１ｄＣで示すように、ビット判定の結果得られる選択結果ビット列２１３ｃＣのビットＥ３に対応するビット列データＤ３が次の最大値であることが分かる。
【０１１０】
次に双方向の矢印２２１Ｃで示す選択ビット列２１２ａＣと選択結果ビット列２１３ｃＣにより次選択ビット設定のためのビット演算がおこなわれ、点線の矢印２３１Ｃで示すように、次選択ビット列２１３Ｃが求められる。次選択ビット列２１３Ｃは、ステップ３における初期値である選択ビット列２１２ａＣのうち、ステップ３の最大値選択処理の結果得られる選択結果ビット列２１３ｃＣのビットのうちの選択ビットであるＥ３を非選択ビットに置換したものである。
【０１１１】
図１１Ｂに示すステップ４は最後の最大値選択処理である。結果的には最小値にアクセスするための情報が求められる。図１１Ｂに示すように、ステップ４では、ステップ３で求めた次選択ビット列２１３Ｃを最小値選択処理の初期値である選択ビット列２１２ａＤとして設定する。双方向の矢印２２１ａＤで示すように、図２Ｂに例示したステップ２と同様に選択ビット列２１２ａＤにより同一ビット位置ビット列２４０のビット判定が行われ、引き続き点線の矢印２３１ｂＤで示すように、ビット判定の結果得られる次選択ビット列２１３ａＤによる次のビット判定が行われる。
【０１１２】
次のビット判定では、双方向の矢印２２１ｂＤで示すように、図２Ｂに例示したステップ３と同様に次選択ビット列２１３ａＤを選択ビット列２１２ｂＤとして同一ビット位置ビット列２４１のビット判定が行われ、引き続き点線の矢印２３１ｃＤで示すように、ビット判定の結果得られる次選択ビット列２１３ｂＤによりさらに次のビット判定が行われる。
【０１１３】
次のビット判定では、双方向の矢印２２１ｃＤで示すように、図２Ｂに例示したステップ４と同様に次選択ビット列２１３ｂＤを選択ビット列２１２ｃＤとして同一ビット位置ビット列２４２のビット判定が行われ、点線の矢印２３１ｄＤで示すように、ビット判定の結果得られる選択結果ビット列２１３ｃＤのビットＥに対応するビット列データＤ２が次の最大値であることが分かる。
【０１１４】
次に双方向の矢印２２１Ｄで示す選択ビット列２１２ａＤと選択結果ビット列２１３ｃＤにより次選択ビット設定のためのビット演算がおこなわれ、点線の矢印２３１Ｄで示すように、次選択ビット列２１３Ｄが求められる。次選択ビット列２１３Ｄは、ステップ４における初期値である選択ビット列２１２ａＤのうち、ステップ４の最大値選択処理の結果得られる選択結果ビット列２１３ｃＤのビットのうちの選択ビットであるＥ２を非選択ビットに置換したものである。
【０１１５】
図１１Ｂに示すように、次選択ビット列２１３Ｄのビットは全て非選択ビットであり、検索の終了が判定される。以上の処理により、複数のビット列データの集合｛Ｄ１，Ｄ２，Ｄ３，Ｄ４｝から降順でビット列データを取り出すための情報として選択結果ビット列２１３ｃＡ、２１３ｃＢ、２１３ｃＣ、２１３ｃＤを出力することができる。
【０１１６】
次に、上述のビット列データ昇順選択処理あるいはビット列データ昇順選択処理を実現する、本発明の最大値・最小値選択回路を用いたビット列データ順次選択回路について説明する。
図１２Ａは、本発明の第４及び第５の実施形態におけるビット列データ順次選択回路ブロックと周辺回路例を説明する図である。
【０１１７】
図１２Ａに示すように、ビット列データ順次選択回路５００ａは最大値・最小値選択回路３００、選択ビットレジスタ３１０、選択結果レジスタ３６０、次選択ビット設定回路３８０及び順次選択制御回路３７０を含む。
【０１１８】
最大値・最小値選択回路３００は、第４の実施形態の場合は、例えば図３Ａに例示する最小値選択回路３００ａであり、第５の実施形態の場合は、例えば図３Ｂに例示する最大値選択回路３００ｂである。選択ビットレジスタ３１０及び選択結果レジスタ３６０は図３Ａ、図３Ｂ及び図１０に記載するものと同様である。
周辺回路であるデータレジスタ群３０１も、図３Ａ、図３Ｂ及び図１０に記載するものと同様である。
【０１１９】
信号線５２０は、データレジスタ群３０１と次選択ビット設定回路３８０に入力されるデータ設定信号であって、データレジスタ群３０１にビット列データを設定するタイミングと、次選択ビット設定回路３８０の次選択ビット列を初期設定するタイミングを与えるものである。
データレジスタ群３０１への入力である並列バス５２１はビット列データを設定するためのものであり、データレジスタ群３０１から最大値・最小値選択回路３００への信号線５２２は、図１０に示す同一位置ビット列を出力する並列バス３４０１、３４０２、・・・３４０ｍを表すものである。
【０１２０】
順次選択制御回路３７０に入力される信号線５３０は、順次選択制御回路３７０に制御開始を指示する順次選択開始信号のためのものであり、順次選択制御回路３７０は制御開始の指示を受けてビット列データ順次選択回路５００ａ内に順次選択動作を制御するためのクロックの供給を開始する。
【０１２１】
上述の信号線５２０、並列バス５２１、及び信号線５３０により供給される信号又はビット列データは、データレジスタ群３０１を含む周辺回路からビット列データ順次選択回路５００ａに供給される。なお、ビット列データ順次選択回路５００ａがデータレジスタ群３０１を含むようにし、データレジスタ群を含まない周辺回路がビット列データ順次選択回路を利用できるようにすることも可能である。
【０１２２】
順次選択制御回路３７０から選択ビットレジスタ３１０への信号線５３２ａと順次選択制御回路３７０から選択結果レジスタ３６０と次選択ビット設定回路３８０への信号線５３２ｂは上述のクロックを供給するものである。信号線５３２ａ上のクロック（以下、クロック５３２ａということがある。）と信号線５３２ｂ上のクロック（以下、クロック５３２ｂということがある。）は、互いに逆相のクロックで、最大値・最小値選択回路３００と次選択ビット設定回路３８０の交互動作を制御するためのものである。信号線５３２ｂと同一のクロックが供給される信号線５３２は、外部回路に選択結果ビット列を取り込むタイミングを与えるものである。なお、外部回路は、ビット列データ順次選択回路に接続された回路であって、ビット列データ順次選択回路から順次出力される選択結果ビット列を利用する任意の回路である。
【０１２３】
次選択ビット設定回路３８０は、選択ビットレジスタ３１０に信号線５６０を介して図１１Ａ及び図１１Ｂに例示する各ステップのように最大値・最小値選択処理を実行する毎に選択ビット列の初期値を再設定する。最初のステップにおける選択ビット列の初期値は全てのビットが選択ビットである。最初のステップ以降には選択ビットレジスタ３１０に保持された選択ビット列が信号線５４０ｘを介して次選択ビット設定回路３８０に入力されるとともに、選択結果レジスタ３６０に保持されている選択結果ビット列が信号線５５０ｘを介して次選択ビット設定回路３８０に入力される。
【０１２４】
そして、信号線５３２ｂ上のクロックに同期して上記選択ビット列と選択結果ビット列間のビット列演算により次選択ビット列が生成され、信号線５６０を介して次の最大値・最小値選択処理の選択ビット列の初期値として選択ビットレジスタ３１０に設定される。
【０１２５】
次に信号線５３２ａ上のクロックに同期して選択ビットレジスタ３１０に設定された選択ビット列の初期値が最大値・最小値選択回路に入力され、最大値・最小値選択回路３００の最終段のビット判定回路の出力である次選択ビット列が信号線５７０を介して選択結果レジスタ３６０に選択結果ビット列として入力される。選択結果ビット列の選択結果レジスタ３６０への設定タイミングは信号線５３２ｂ上のクロックにより制御される。
【０１２６】
選択結果レジスタ３６０に格納された選択結果ビット列は信号線５５０ｘを介して次選択ビット設定回路３８０に入力されるとともに、信号線５５０を介して外部回路に出力される。
【０１２７】
次選択ビット設定回路３８０は、生成した次選択ビット列のビットが全て非選択ビットであることを検出すると、信号線５８０ｘを介して順次選択制御回路３７０に順次選択制御動作の終了を指示する順次選択終了信号を送出するとともに、外部回路に信号線５８０を介して順次選択動作の終了を通知する。順次選択終了信号を受信した順次選択制御回路３７０はクロック送出を停止し、順次選択制御動作を終了する。
【０１２８】
図１２Ｂは、本発明の第６の実施形態におけるビット列データ順次選択回路ブロックと周辺回路例を説明する図である。図１２Ａに示す、本発明の第４及び第５の実施形態におけるビット列データ順次選択回路ブロック及び周辺回路例と比較すると、第６の実施形態におけるビット列データ順次選択回路５００ｂは、最大値・最小値選択回路が第３の実施形態の最大値・最小値選択回路３００ｃである。また、周辺回路として判定ビットを保持する判定フラグ３９０が追加され、信号線５２０は判定フラグ３９０にも接続され、判定フラグ３９０に判定ビットを設定するタイミングを与えている。
【０１２９】
判定フラグ３９０は図１０に記載されたものと同様である。判定フラグから最大値・最小値選択回路３００ｃへの信号線５２４は、図１０に示す判定ビットを出力するバス３２１と同等のものである。判定フラグが追加されたことを除いて、他の部分については第４及び第５の実施形態のものと同様であるので、これ以上の説明は省略する。
【０１３０】
次に図１２Ａ及び図１２Ｂに示す次選択ビット設定回路３８０について、図１３を参照して説明する。
図１３に示すように、次選択ビット設定回路３８０は、選択ビット列一時保持レジスタ３８１、次選択ビット列演算器３８２及び全選択終了検出器３８３を含む。
【０１３１】
選択ビット列一時保持レジスタ３８１は、信号線５３２ｂで与えられるクロックにより、信号線５４０ｘを介して選択ビットレジスタ３１０の値を一時的に保持する。選択ビット列一時保持レジスタ３８１の初期値は、信号線５２０を介して与えられるデータ設定信号により設定される。選択ビット列の初期値は、全てのビットが選択ビット、本願の実施形態における選択ビットの例示では全てのビットが“１”、である。
【０１３２】
次選択ビット列演算器３８２は、信号線５４１ｘを介して選択ビット列一時保持レジスタ３８１から入力される選択ビット列と信号線５５０ｘを介して選択結果レジスタ３６０から入力される選択結果ビット列との間でビット列演算を行い、次のステップの最大値・最小値選択処理で初期値として用いる次の初期選択ビット列を生成する。
【０１３３】
上述のビット列演算は、選択ビット列一時保持レジスタ３８１から入力される選択ビット列の、選択結果レジスタ３６０から入力される選択結果ビット列の選択ビットの存在するビット位置のビットを非選択ビットとして選択済みのビット列データを選択対象から除外するものである。このビット列演算は、例えば排他的論理和で実現することができる。上述のビット列演算により生成された選択ビット列は、信号線５６０を介して選択ビットレジスタに次の初期選択ビット列として入力されるとともに、信号線５６０ｘを介して全選択終了検出器３８３に入力される。
【０１３４】
全選択終了検出器３８３は、信号線５６０ｘ上の選択ビット列の全てのビットが非選択ビットであることにより全てのビット列データが選択されたことを検出し、順次選択終了信号を、信号線５８０ｘを介して順次選択制御回路３７０に出力するとともに、信号線５８０を介して外部回路に出力する。
【０１３５】
次に図１２Ａ及び図１２Ｂに示すビット列データ順次選択回路のタイミングチャートについて説明する。
図１４は、本発明の第４の実施形態におけるビット列データ順次選択回路のタイミングチャート例を説明する図である。
【０１３６】
図１４に示す（１）は、周辺回路から入力されるリセット信号の波形である。図１２Ａ、図１２Ｂ及び図１３ではリセット信号線は省略されている。
図１４に示す（２）及び（３）は、それぞれ信号線５２０上のデータ設定信号及び信号線５３０上の順次選択開始信号の波形である。
そして、図１４に示す（４）は、順次選択制御回路３７０が有するクロック発生回路が生成するクロックの波形である。
【０１３７】
図１４に示す（５）は、クロック５３２ａ及びクロック５３２ｂを供給するためのクロック供給信号の波形である。
図１４に示す（６）は信号線５８０、５８０ｘ上の順次選択終了信号の波形である。
そして、図１４に示す（７）及び（８）は順次選択制御回路３７０から出力されるクロックの波形である。クロック５３２ａに対して、クロック５３２ｂは、クロック５３２ａの逆相信号である。図１４に示すタイミングについては後に説明する。
【０１３８】
図１４に示す（９）は、データレジスタ群３０１に保持されたビット列データの例示であり、図２Ａに例示したものと同じビット列データが保持されている。先に述べたように、これらのビット列データのそれぞれの同一位置のビットから取り出されたビットからなる同一位置ビット列が最大値・最小値選択回路３００に出力される。
図１４に示す（１０）は、次選択ビット設定回路３８０から信号線５６０を介して選択ビットレジスタ３１０に出力される、各最大値・最小値選択処理の選択ビット列の初期値の例示である。
そして、図１４に示す（１１）及び（１２）は、それぞれ選択ビットレジスタ３１０に保持された選択ビット列と選択結果レジスタ３６０に保持された選択結果ビット列の例示である。
【０１３９】
図１４に記載された符号Ｔ０、Ｔ１、乃至Ｔ９は、それぞれ特定のタイミングを示すものである。図１４に示すように、Ｔ０はクロック供給信号が立ち上がるタイミングである。Ｔ１でクロック５３２ａの供給が開始される。以下、Ｔ２乃至Ｔ８は、クロックの半周期ごとのタイミングである。Ｔ９は順次選択終了信号によりクロック供給信号が立ち下がるタイミングである。
【０１４０】
図１４の（１）に示すように、リセット信号が入力されると、矢印５１０ａで示すように、選択ビットレジスタ３１０、選択結果レジスタ３６０、及び次選択ビット設定回路３８０の選択ビット列一時保持レジスタ３８１がリセットされ、それぞれのレジスタ全てのビットは“０”にクリアされる。
【０１４１】
次に図１４の（２）に示す信号線５２０上のデータ設定信号（以下、クロック５３２ａと同様に、信号線上の信号に信号線と同じ符号をつけて説明する。）が立ち上がると、矢印５２０ａで示すように、データレジスタ群３０１にビット列データが設定されるとともに、選択ビット列一時保持レジスタ３８１に、全てのビットが選択ビットであるビット列“１１１１”が設定される。
【０１４２】
次に図１４の（３）に示す順次選択開始信号５３０が立ち上がると、矢印５３０ａ及び点線の輪５３１ａで示すように、クロック５３２ａが状態“０”から供給されるように、クロック供給信号と、順次選択制御回路３７０が有するクロック５３２ａとクロック５３２ｂの基となるクロック発生回路のクロックとの同期がとられ、図１４の（５）に示すクロック供給信号がタイミングＴ０で立ち上がる。矢印５３１ｂで示す点線の輪で囲まれたタイミングにおいて、クロック供給が開始される。
【０１４３】
図１４の（７）に示すように、タイミングＴ１でクロック５３２ａが立ち上がると矢印５３３ａで示すタイミングで、矢印５６０ａで示すように最初の選択ビット列の初期値“１１１１”が選択ビットレジスタ３１０に設定される。そして、矢印２３０Ａで示すように、点線の輪５９１ａで示すデータレジスタ群３０１に設定されたビット列データ５４１ａと選択ビット列レジスタ３１０に設定された５５１ａを入力とする最大値・最小値選択回路３００により選択結果ビット列の最初の値である“０１００”が求められる。
【０１４４】
次にタイミングＴ２において、クロック５３２ｂが立ち上がると、矢印５３５ａで示すタイミングで、最初の最大値・最小値選択の選択結果である選択結果ビット列“０１００”が選択結果レジスタ３６０に設定される。また、図１４には記載を省略しているが、先に述べたとおり、選択ビットレジスタに保持された選択ビット列が次選択ビット列一時保持レジスタ３８１に設定される。そして、矢印２２０Ａで示すように、点線の輪５９０ａで示す選択ビット列５４０ａと選択結果ビット列５５０ａの演算により次の選択ビット列の初期値“１０１１”が求められる。
Ｔ１とＴ２の間隔及びＴ２とＴ３の間隔は、最大値・最小値選択回路３００での遅延時間と次選択ビット設定回路３８０での遅延時間の大きいほうにより規定される。
【０１４５】
次にタイミングＴ３でクロック５３２ａが立ち上がると矢印５３３ｂで示すタイミングで、矢印５６０ｂで示すように次の選択ビット列の初期値“１０１１”が選択ビットレジスタ３１０に設定される。そして、矢印２３０Ｂで示すように、点線の輪５９１ｂで示すデータレジスタ群３０１に設定されたビット列データ５４１ｂと選択ビット列レジスタ３１０に設定された５５１ｂを入力とする最大値・最小値選択回路３００により選択結果ビット列“００１０”が求められる。
【０１４６】
次にタイミングＴ４においてクロック５３２ｂが立ち上がると、矢印５３５ｂで示すタイミングで、次の最大値・最小値選択の選択結果である選択結果ビット列“００１０”が選択結果レジスタ３６０に設定される。そして、矢印２２０Ｂで示すように、点線の輪５９０ｂで示す選択ビット列５４０ｂと選択結果ビット列５５０ｂの演算により次の選択ビット列の初期値“１００１”が求められる。
【０１４７】
次にタイミングＴ５でクロック５３２ａが立ち上がると矢印５３３ｃで示すタイミングで、矢印５６０ｃで示すように次の選択ビット列の初期値“１００１”が選択ビットレジスタ３１０に設定される。そして、矢印２３０Ｃで示すように、点線の輪５９１ｃで示すデータレジスタ群３０１に設定されたビット列データ５４１ｃと選択ビット列レジスタ３１０に設定された５５１ｃを入力とする最大値・最小値選択回路３００により選択結果ビット列“０００１”が求められる。
【０１４８】
次にタイミングＴ６においてクロック５３２ｂが立ち上がると、矢印５３５ｃで示すタイミングで、最大値・最小値選択の選択結果である選択結果ビット列“０００１”が選択結果レジスタ３６０に設定される。そして、矢印２２０Ｃで示すように、点線の輪５９０ｃで示す選択ビット列５４０ｃと選択結果ビット列５５０ｃの演算により次の選択ビット列の初期値“１０００”が求められる。
【０１４９】
次にタイミングＴ７でクロック５３２ａが立ち上がると矢印５３３ｄで示すタイミングで、矢印５６０ｄで示すように次の選択ビット列の初期値“１０００”が選択ビットレジスタ３１０に設定される。そして、矢印２３０Ｄで示すように、点線の輪５９１ｄで示すデータレジスタ群３０１に設定されたビット列データ５４１ｄと選択ビット列レジスタ３１０に設定された５５１ｄを入力とする最大値・最小値選択回路３００により選択結果ビット列“１０００”が求められる。
【０１５０】
次にタイミングＴ８においてクロック５３２ｂが立ち上がると、矢印５３５ｄで示すタイミングで、最大値・最小値選択の選択結果である選択結果ビット列“１０００”が選択結果レジスタ３６０に設定される。そして、矢印２２０Ｄで示すように、点線の輪５９０ｄで示す選択ビット列５４０ｄと選択結果ビット列５５０ｄの演算により次の選択ビット列の初期値として“００００”が求められる。
【０１５１】
すると、次の選択ビット列の初期値のビットが全て非選択ビットであることが全選択終了検出器３９３で検出され、矢印５６０ｅで示すように、順次選択終了信号５８０が立ち上がる。そして、矢印５８０ｄで示すように、図１４の（５）に示すクロック供給信号を立ち下げ、矢印５３１ｄで示すように、タイミングＴ９でクロック５３２ａ及びクロック５３２ｂの供給が停止される。
【０１５２】
以上、本発明の第４の実施形態におけるビット列データ順次選択回路のタイミングチャート例を説明したが、第５の実施形態におけるビット列データ順次選択回路のタイミングチャート例は、図１４の（１０）、（１１）及び（１２）にそれぞれ例示する次の選択ビット列の初期値、選択ビット列及び選択結果ビット列が異なるだけで、他は同じである。また、第６の実施形態におけるビット列データ順次選択回路のタイミングチャート例は、選択ビット列、選択結果ビット列及び次の選択ビット列の初期値が判定ビットにより異なること、及びデータ設定信号により判定フラグに設定される判定ビットが追加されることで異なるだけであるので、説明は省略する。
【０１５３】
以上、本発明の第４乃至第６の実施形態について詳細に説明したことから明らかなとおり、本発明によれば受動回路により構成した最小値・最大値選択回路を用いてビット列データを昇順または降順で取り出すための情報を得ることできるので、高速な動作が可能である。また、上述の説明に限らず本発明の実施の形態について種々の変形が可能なことは当業者に明らかである。
【０１５４】
例えば、全てのビット列データの選択処理が終了したことを、次の選択ビット列の初期値の選択ビットの数が１になったことにより検出することも可能である。
また、図１４のＴ１とＴ２の間隔及びＴ２とＴ３の間隔は、最大値・最小値選択回路３００での遅延時間と次選択ビット設定回路３８０での遅延時間の大きいほうにより規定されるとしたが、Ｔ１とＴ２の間隔を最大値・最小値選択回路３００での遅延時間、Ｔ２とＴ３の間隔を次選択ビット設定回路３８０での遅延時間とするデューティー比のクロックを生成することにより、最小の遅延時間で、ビット列データ順次選択回路を動作させることができる。さらに、順次選択制御回路３７０が有するクロック発生回路を外部クロックに同期させて、順次選択ビット列を出力することや、外部クロックをもとにビット列データ順次選択回路の動作クロックを生成することも可能である。
【符号の説明】
【０１５５】
３００    最大値・最小値選択回路
３０１    データレジスタ群
３１０    選択ビットレジスタ
３２０ａ  ビット判定回路
３６０    選択結果レジスタ
３７０    順次選択制御回路
３８０    次選択ビット設定回路
３８１    選択ビット列一時保持レジスタ
３８２    次選択ビット列演算器
３８３    全選択終了検出器
３９０    判定フラグ
４１０    判定ビット設定器
４２０    一致判定器
４３０    全不一致判定器
４４０    判定結果選択器
【図１Ａ】
0005512031.tif 000002
【図１Ｂ】
0005512031.tif 000003
【図２Ａ】
0005512031.tif 000004
【図２Ｂ】
0005512031.tif 000005
【図３Ａ】
0005512031.tif 000006
【図３Ｂ】
0005512031.tif 000007
【図４】
0005512031.tif 000008
【図５】
0005512031.tif 000009
【図６】
0005512031.tif 000010
【図７】
0005512031.tif 000011
【図８】
0005512031.tif 000012
【図９】
0005512031.tif 000013
【図１０】
0005512031.tif 000014
【図１１Ａ】
0005512031.tif 000015
【図１１Ｂ】
0005512031.tif 000016
【図１２Ａ】
0005512031.tif 000017
【図１２Ｂ】
0005512031.tif 000018
【図１３】
0005512031.tif 000019
【図１４】
0005512031.tif 000020