(57)【要約】複数のビット列データからビット列データを選択するための情報を高速に出力するために、複数のビット列データの同一のビット位置のビットと検索ビット列のビットを最上位から最下位まで順次比較していく。比較の結果一度ビットが検索ビット列のビットと一致しなかったビット列データのビットを比較の対象から外すことにより、最下位のビット位置で選択されたビットが属するビット列データを検索ビット列と一致するビット列データとする。
2014102924.tif 000002
【特許請求の範囲】
【請求項１】
ビット長がｍ（ｍは１以上の整数）であるＮ個（Ｎは２以上の整数）のビット列データの同一のビット位置ｉ（ｉ＝０〜ｍ−１）のビットを判定するビット判定回路において、
前記ビット列データそれぞれの同一のビット位置ｉから取り出したビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる同一位置ビット列のビットそれぞれと、ビット長がｍである検索ビット列のビット位置ｉの検索ビットとのビット比較を行い、前記同一位置ビット列のビットと前記検索ビットが一致するか否かを表す判定ビットからなる判定ビット列を出力するビット比較器と、
前記同一位置ビット列のそれぞれのビットをビット判定の対象として選択するか否かを表すビットであり、それぞれ各ビット列データに対応するＮ個の選択ビットからなる選択ビット列と、前記判定ビット列とのビット列演算を行い、各ビット列データそれぞれの前記同一のビット位置ｉの次のビット位置（ｉ＋１）から取り出したビットであってそれぞれ各ビット列データに対応するＮ個のビットからなる次同一位置ビット列のそれぞれのビットを、ビット判定の対象として選択するか否かを表すビットであり、それぞれ各ビット列データに対応するＮ個の次選択ビットからなる次選択ビット列を出力する次選択ビット設定器と、を備え、
前記次選択ビット設定器は、前記選択ビット列の選択ビットが前記同一位置ビット列のビットをビット判定の対象として選択することを表す有意のビットであれば該選択ビットと対応する前記判定ビットを前記次選択ビットとし、前記選択ビット列の選択ビットが前記有意のビットでなければ該選択ビットを前記次選択ビットとすること
を特徴とするビット判定回路。
【請求項２】
それぞれのビット長がｍ（ｍは１以上の整数）であるＮ個（Ｎは２以上の整数）のビット列データからビット長がｍである検索ビット列と一致するビット列データを選択するためのビット列データ選択回路において、
請求項１に記載されたビット判定回路を、同一のビット位置ｉのビットを判定するビット判定回路の出力である次選択ビット列を同一のビット位置（ｉ＋１）のビットを判定するビット判定回路の選択ビット列として入力するようにｍ段直列に接続し、
ｍ段目のビット判定回路の出力である次選択ビット列を、前記検索ビット列と一致するビット列データを選択するための情報として出力すること
を特徴とするビット列データ選択回路。
【請求項３】
請求項１に記載のビット判定回路において、
判定結果選択器をさらに備え、
前記判定結果選択器は、前記同一のビット位置ｉから取り出されたビットからなる同一位置ビット列のビットをビット判定の対象から除外するか否かを表すビットでありそれぞれ前記同一のビット位置ｉに対応するｍ個のスキップビットからなるスキップビット列のスキップビットが、前記対応する同一位置ビット列を構成するビットをビット判定の対象から除外することを示す有意のビットであれば、前記次選択ビット設定器が出力する前記次選択ビット列に替えて前記選択ビット列を次選択ビット列として出力し、前記スキップビットが有意のビットでなければ、前記次選択ビット設定器が出力する前記次選択ビット列を次選択ビット列として出力すること
を特徴とするビット判定回路。
【請求項４】
それぞれのビット長がｍ（ｍは１以上の整数）であるＮ個（Ｎは２以上の整数）のビット列データからビット長がｍである検索ビット列と部分一致するビット列データを選択するためのビット列データ選択回路において、
請求項３に記載されたビット判定回路を、同一のビット位置ｉのビットを判定するビット判定回路の出力である次選択ビット列を同一のビット位置（ｉ＋１）のビットを判定するビット判定回路の選択ビット列として入力するようにｍ段直列に接続し、
ｍ段目のビット判定回路の出力である次選択ビット列を、前記検索ビット列と部分一致するビット列データを選択するための情報として出力すること
を特徴とするビット列データ選択回路。
【請求項５】
請求項１に記載のビット判定回路において、
全不一致判定器と、判定結果選択器と、をさらに備え、
全不一致判定器は、前記選択ビット列の前記選択ビットにより選択された前記同一位置ビット列のビットが全て前記判定ビットの論理否定であるか判定して判定結果を全不一致ビットとして出力し、
判定結果選択器は、前記全不一致ビットが前記選択ビット列の前記選択ビットにより選択された前記同一位置ビット列のビットが対応する全ての検索ビットと一致しないことを表す有意のビットであるか、あるいは、前記ビット列データからビットを取り出した前記同一のビット位置ｉより上位のビット位置において該上位のビット位置の同一位置ビット列のビットが対応する全ての検索ビットと一致しなければ、前記次選択ビット設定器が出力する前記次選択ビット列に替えて前記選択ビット列を前記次選択ビット列として出力し、前記全不一致ビットが有意でなく、かつ、前記ビット列データからビットを取り出した前記同一のビット位置ｉより上位の全てのビット位置において該上位のビット位置の同一位置ビット列のビットが対応する全ての検索ビットと一致しなければ、前記次選択ビット設定器の出力である次選択ビット列を出力すること、
を特徴とするビット判定回路。
【請求項６】
それぞれのビット長がｍ（ｍは１以上の整数）であるＮ個（Ｎは２以上の整数）のビット列データからビット長がｍである検索ビット列と最長一致するビット列データを選択するためのビット列データ選択回路において、
請求項５に記載されたビット判定回路を、同一のビット位置ｉのビットを判定するビット判定回路の出力である次選択ビット列を同一のビット位置（ｉ＋１）のビットを判定するビット判定回路の選択ビット列として入力するようにｍ段直列に接続するとともに、前段のビット判定回路の出力する全不一致ビットを次段のビット判定回路に入力し、
ｍ段目のビット判定回路の出力である次選択ビット列を、前記検索ビット列と最長一致するビット列データを選択するための情報として出力すること
を特徴とするビット列データ選択回路。
【請求項７】
それぞれのビット長がｍ（ｍは１以上の整数）であるＮ個（Ｎは２以上の整数）のビット列データからビット長がｍである検索ビット列と一致するビット列データを選択するためのビット列データ選択方法において、
前記ビット列データそれぞれの同一のビット位置ｉ（ｉ＝０〜ｍ−１）から取り出したビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる同一位置ビット列のビットそれぞれと、ビット長がｍである検索ビット列のビット位置ｉの検索ビットとのビット比較を行い、前記同一位置ビット列のビットと前記検索ビットが一致するか否かを表す判定ビットからなる判定ビット列を出力するビット比較サブステップと、
前記同一位置ビット列のそれぞれのビットをビット判定の対象として選択するか否かを表すビットであり、それぞれ各ビット列データに対応するＮ個の選択ビットからなる選択ビット列と前記判定ビット列とのビット列演算を行い、各ビット列データそれぞれの前記同一のビット位置ｉの次のビット位置（ｉ＋１）から取り出したビットであってそれぞれ各ビット列データに対応するＮ個のビットからなる次同一位置ビット列のそれぞれのビットを、ビット判定の対象として選択するか否かを表すビットであり、それぞれ各ビット列データに対応するＮ個の次選択ビットからなる次選択ビット列を出力するものであり、前記選択ビット列の選択ビットが前記同一位置ビット列のビットをビット判定の対象として選択することを表す有意のビットであれば該選択ビットと対応する前記判定ビットを前記次選択ビットとし、前記選択ビット列の選択ビットが前記有意のビットでなければ該選択ビットを前記次選択ビットとする次選択ビット設定サブステップと
を含むビット判定ステップを備え、
該ビット判定ステップを、同一のビット位置ｉのビットを判定するビット判定ステップの出力である次選択ビット列を同一のビット位置（ｉ＋１）のビットを判定するビット判定ステップの選択ビット列として入力してｍ回順次繰り返し、
同一のビット位置（ｍ−１）のビットを判定するビット判定ステップで出力される次選択ビット列を、前記検索ビット列と一致するビット列データを選択するための情報として出力する
ことを特徴とするビット列データ選択方法。
【請求項８】
それぞれのビット長がｍ（ｍは１以上の整数）であるＮ個（Ｎは２以上の整数）のビット列データからビット長がｍである検索ビット列と部分一致するビット列データを選択するためのビット列データ選択方法において、
前記ビット列データそれぞれの同一のビット位置ｉ（ｉ＝０〜ｍ−１）から取り出したビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる同一位置ビット列のビットそれぞれと、ビット長がｍである検索ビット列のビット位置ｉの検索ビットとのビット比較を行い、前記同一位置ビット列のビットと前記検索ビットが一致するか否かを表す判定ビットからなる判定ビット列を出力するビット比較サブステップと、
前記同一位置ビット列のそれぞれのビットをビット判定の対象として選択するか否かを表すビットであり、それぞれ各ビット列データに対応するＮ個の選択ビットからなる選択ビット列と前記判定ビット列とのビット列演算を行い、各ビット列データそれぞれの前記同一のビット位置ｉの次のビット位置（ｉ＋１）から取り出したビットであってそれぞれ各ビット列データに対応するＮ個のビットからなる次同一位置ビット列のそれぞれのビットを、ビット判定の対象として選択するか否かを表すビットであり、それぞれ各ビット列データに対応するＮ個の次選択ビットからなる次選択ビット列を出力するものであり、前記選択ビット列の選択ビットが前記同一位置ビット列のビットをビット判定の対象として選択することを表す有意のビットであれば該選択ビットと対応する前記判定ビットを前記次選択ビットとし、前記選択ビット列の選択ビットが前記有意のビットでなければ該選択ビットを前記次選択ビットとする次選択ビット設定サブステップと、
前記同一のビット位置ｉから取り出されたビットからなる同一位置ビット列のビットをビット判定の対象から除外するか否かを表すビットでありそれぞれ前記同一のビット位置ｉに対応するｍ個のスキップビットからなるスキップビット列のスキップビットが、前記対応する同一位置ビット列を構成するビットをビット判定の対象から除外することを示す有意のビットであれば、前記次選択ビット設定サブステップにおいて出力される前記次選択ビット列に替えて前記選択ビット列を次選択ビット列として出力し、前記スキップビットが有意のビットでなければ、前記次選択ビット設定サブステップにおいて出力される前記次選択ビット列を次選択ビット列として出力する判定結果選択サブステップと
を含み、前記判定結果選択サブステップにおいて出力された次選択ビット列を出力するビット判定ステップを備え、
該ビット判定ステップを、同一のビット位置ｉのビットを判定するビット判定ステップの出力である次選択ビット列を同一のビット位置（ｉ＋１）のビットを判定するビット判定ステップの選択ビット列として入力してｍ回順次繰り返し、
同一のビット位置（ｍ−１）のビットを判定するビット判定ステップで出力される次選択ビット列を、前記検索ビット列と部分一致するビット列データを選択するための情報として出力する
ことを特徴とするビット列データ選択方法。
【請求項９】
それぞれのビット長がｍ（ｍは１以上の整数）であるＮ個（Ｎは２以上の整数）のビット列データからビット長がｍである検索ビット列と最長一致するビット列データを選択するためのビット列データ選択方法において、
前記ビット列データそれぞれの同一のビット位置ｉ（ｉ＝０〜ｍ−１）から取り出したビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる同一位置ビット列のビットそれぞれと、ビット長がｍである検索ビット列のビット位置ｉの検索ビットとのビット比較を行い、前記同一位置ビット列のビットと前記検索ビットが一致するか否かを表す判定ビットからなる判定ビット列を出力するビット比較サブステップと、
前記同一位置ビット列のそれぞれのビットをビット判定の対象として選択するか否かを表すビットであり、それぞれ各ビット列データに対応するＮ個の選択ビットからなる選択ビット列と前記判定ビット列とのビット列演算を行い、各ビット列データそれぞれの前記同一のビット位置ｉの次のビット位置（ｉ＋１）から取り出したビットであってそれぞれ各ビット列データに対応するＮ個のビットからなる次同一位置ビット列のそれぞれのビットを、ビット判定の対象として選択するか否かを表すビットであり、それぞれ各ビット列データに対応するＮ個の次選択ビットからなる次選択ビット列を出力するものであり、前記選択ビット列の選択ビットが前記同一位置ビット列のビットをビット判定の対象として選択することを表す有意のビットであれば該選択ビットと対応する前記判定ビットを前記次選択ビットとし、前記選択ビット列の選択ビットが前記有意のビットでなければ該選択ビットを前記次選択ビットとする次選択ビット設定サブステップと、
前記選択ビット列の前記選択ビットにより選択された前記同一位置ビット列のビットが対応する全ての検索ビットと一致しないか判定し、全不一致ビットを出力する全不一致判定サブステップと、
前記全不一致ビットが、前記選択ビット列の前記選択ビットにより選択された前記同一位置ビット列のビットが対応する全ての検索ビットと一致しないことを表す有意のビットであるか、あるいは、前記ビット列データからビットを取り出した前記同一のビット位置ｉより上位のビット位置において該上位のビット位置の同一位置ビット列のビットが対応する全ての検索ビットと一致しないものであれば、前記次選択ビット設定サブステップにおいて出力される前記次選択ビット列に替えて前記選択ビット列を前記次選択ビット列として出力し、前記全不一致ビットが有意でなく、かつ、前記ビット列データからビットを取り出した前記同一のビット位置ｉより上位の全てのビット位置において該上位のビット位置の同一位置ビット列のビットが対応する全ての検索ビットと一致しないものでなければ、前記次選択ビット設定サブステップにおいて出力された次選択ビット列を出力する判定結果選択サブステップと
を含み、前記判定結果選択サブステップにおいて出力された次選択ビット列を出力するとともに前記全不一致ビットを出力するビット判定ステップを備え、
該ビット判定ステップを、同一のビット位置ｉのビットを判定するビット判定ステップの出力である次選択ビット列を同一のビット位置（ｉ＋１）のビットを判定するビット判定ステップの選択ビット列として入力してｍ回順次繰り返し、
同一のビット位置（ｍ−１）のビットを判定するビット判定ステップで出力される次選択ビット列を、前記検索ビット列と最長一致するビット列データを選択するための情報として出力する
ことを特徴とするビット列データ選択方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のビット列データの同一ビット位置にあるビットを判定するビット判定回路と、ビット判定回路を用いて複数のビット列データのうちのビット列データを選択するための情報を出力するビット列データ選択回路及びビット列データ選択方法に関する。
【背景技術】
【０００２】
情報処理の技術分野においては、複数のビット列データからある条件を満たすビット列データ、例えばある検索ビット列と一致するビット列データを求めることが行われている。このような検索ビット列と一致するビット列データを求める処理は、例えば、下記特許文献１に示すように、検索対象のビット列データを記憶したメモリからビット列データを１つずつ読み出して検索ビット列と比較することにより実行されている。【０００３】
図１は、上述の従来の検索処理の処理例を説明する図である。
図１に示す検索処理の例では、複数のビット列データの集合であるビット列データ群１０１は、４つのビット列データ、Ｄ１、Ｄ２、Ｄ３、Ｄ４から構成されており、それぞれのビット列データは、Ｄ１＝１１１、Ｄ２＝０１０、Ｄ３＝０１１、Ｄ４＝１００である。検索ビット列Ｓ２６０は、“０１０”である。【０００４】
図１に示すように、ステップ１で例えばビット列データのうち矢印１１１ａで示す先頭に位置するビット列データＤ１と検索ビット列Ｓ２６０との一致判定１２１ａが行われ、ビット列データＤ１は検索ビット列Ｓと不一致であると判定される。【０００５】
次にステップ２において、矢印１１１ｂで示す次のビット列データＤ２と検索ビット列Ｓ２６０との一致判定１２１ｂが行われ、ビット列データＤ２は検索ビット列Ｓと一致すると判定される。【０００６】
次にステップ３において、矢印１１１ｃで示す次のビット列データＤ３と検索ビット列Ｓ２６０との一致判定１２１ｃが行われ、ビット列データＤ３は検索ビット列Ｓと不一致であると判定される。【０００７】
最後にステップ４において、矢印１１１ｄで示す最後のビット列データＤ４と検索ビット列Ｓ２６０との一致判定１２１ｄが行われ、ビット列データＤ４は検索ビット列Ｓと不一致であると判定される。【０００８】
上述の検索処理は、下記特許文献に記載されたように、検索に適したハードウェアを用いて実行されている。また、ＣＰＵを使用してソフトウェアによる処理で実現することができる。しかし、いずれにしろ、検索対象のビット列データを記憶したメモリからビット列データを１つずつ読み出して検索ビット列と比較することにより実行するものである。【０００９】
一方、下記特許文献２に開示されているように、並列に処理しようとするビット列データの数に相当する複数の比較器を用いてビット列データの比較を行うものも知られている。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開平１０−２２２５３５号公報
【特許文献２】特開２０１０−２２４８１８号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
上述の特許文献１に記載された検索処理は、検索対象のビット列データを記憶したメモリからビット列データを１つずつ読み出して検索ビット列と比較するため、ビット列データの個数が増大するとそれに比例して処理時間が増大する。
また、上述の特許文献２に記載されたビット列データの比較処理は、ビット列データの個数が増大すると多数の比較器を必要とする。【００１２】
そこで本発明が解決しようとする課題は、処理対象のビット列データが増大してもそれに比例して処理時間が増大せず、多数の比較器を必要とせずに複数のビット列データのうち検索ビット列と一致するビット列データを選択するための情報を出力するための手法を提供することである。
【課題を解決するための手段】
【００１３】
本発明の第１の実施形態は、完全一致検索のためのものである。本発明の第１の実施形態の一つの観点によれば、ビット長がｍ（ｍは１以上の整数）であるＮ個（Ｎは２以上の整数）のビット列データそれぞれの同一のビット位置ｉ（ｉ＝０〜ｍ−１）から取り出したビットであり、それぞれ各ビット列データに対応するＮ個のビットからなる同一位置ビット列のビットそれぞれと、ビット長がｍである検索ビット列のビット位置ｉの検索ビットとのビット比較を行い、同一位置ビット列のビットと検索ビットが一致するか否かを表す判定ビットからなる判定ビット列を出力する。そして、同一位置ビット列のそれぞれのビットをビット判定の対象として選択するか否かを表すビットであってそれぞれ各ビット列データに対応するＮ個の選択ビットからなる選択ビット列と判定ビット列とのビット列演算を行い、各ビット列データそれぞれの同一のビット位置ｉの次のビット位置（ｉ＋１）から取り出したビットであってそれぞれ各ビット列データに対応するＮ個のビットからなる次同一位置ビット列のそれぞれのビットをビット判定の対象として選択するか否かを表すビットであり、それぞれ各ビット列データに対応するＮ個の次選択ビットからなる次選択ビット列を、選択ビット列の選択ビットが同一位置ビット列のビットをビット判定の対象として選択することを表す有意のビットであれば該選択ビットと対応する判定ビットを次選択ビットとし、選択ビット列の選択ビットが有意のビットでなければ該選択ビットを次選択ビットとして出力することにより、Ｎ個のビット列データの同一のビット位置ｉのビットをビット判定する。【００１４】
また本発明の第１の実施形態の別の観点によれば、上述のビット判定をビット列データのビット幅分順次実行する。そして、同一のビット位置（ｍ−１）のビットに対するビット判定により出力される次選択ビット列を、検索ビット列に完全一致するビット列データを選択するための情報として出力する。【００１５】
本発明の第２の実施形態は、部分一致検索のためのものである。本発明の第２の実施形態の一つの観点によれば、同一のビット位置ｉから取り出されたビットからなる同一位置ビット列のビットをビット判定の対象から除外するか否かを表すビットでありそれぞれ前記同一のビット位置ｉに対応するｍ個のスキップビットからなるスキップビット列が与えられ、スキップビットが対応する同一位置ビット列を構成するビットをビット判定の対象から除外することを示す有意のビットであれば、上記第１の実施形態のビット判定における選択ビット列を次選択ビット列として出力し、スキップビットが有意のビットでなければ、第１の実施形態のビット判定により出力される次選択ビット列を次選択ビット列として出力することにより、Ｎ個のビット列データの同一のビット位置ｉのビットを判定する。【００１６】
また本発明の第２の実施形態の別の観点によれば、上述のビット判定をビット列データのビット幅分順次実行する。そして、同一のビット位置（ｍ−１）のビットに対するビット判定により出力される次選択ビット列を、検索ビット列に部分一致するビット列データを選択するための情報として出力する。【００１７】
本発明の第３の実施形態は、最長一致検索のためのものである。本発明の第３の実施形態の一つの観点によれば、選択ビット列の選択ビットにより選択された同一位置ビット列のビットが対応する全ての検索ビットと一致しないか判定し、全不一致ビットを出力する。また、全不一致ビットが選択ビット列の選択ビットにより選択された同一位置ビット列のビットが全て対応する検索ビットと一致しないことを表す有意のビットであるか、あるいは、ビット列データからビットを取り出した同一のビット位置ｉより上位のビット位置において該上位のビット位置の同一位置ビット列のビットが全て対応する検索ビットと一致しないものであれば、上記第１の実施形態のビット判定における選択ビット列を次選択ビット列として出力し、全不一致ビットが有意でなく、かつ、ビット列データからビットを取り出した同一のビット位置ｉより上位の全てのビット位置において該上位のビット位置の同一位置ビット列のビットが対応する全ての検索ビットと一致しないものでなければ、第１の実施形態のビット判定により出力される次選択ビット列を次選択ビット列として出力することにより、Ｎ個のビット列データの同一のビット位置ｉのビットを判定する。【００１８】
また本発明の第３の実施形態の別の観点によれば、上述のビット判定をビット列データのビット幅分順次実行する。そして、同一のビット位置（ｍ−１）のビットに対するビット判定により出力される次選択ビット列を、検索ビット列に最長一致するビット列データを選択するための情報として出力する。
【発明の効果】
【００１９】
本発明によれば、処理対象のビット列データが増大してもそれに比例して処理時間が増大せず、多数の比較器を必要とせずに複数のビット列データのうち検索ビット列と一致するビット列データを選択するための情報を出力する手法を提供することができる。
そして、本発明の提供する手法を利用することにより、複数のビット列データのうち検索ビット列と一致するビット列データを取得することができる。
【図面の簡単な説明】
【００２０】
【図１】従来の検索処理について説明する図である。
【図２Ａ】本発明の第１の実施形態における完全一致選択処理の一例を概念的に説明する図である。
【図２Ｂ】本発明の第１の実施形態における完全一致選択処理の別の例を概念的に説明する図である。
【図３】本発明の第１の実施形態における完全一致選択回路を概念的に説明する図である。
【図４】本発明の第１の実施形態におけるビット判定回路の実施例を説明する図である。
【図５】本発明の第２の実施形態における部分一致選択処理を概念的に説明する図である。
【図６】本発明の第２の実施形態における部分一致選択回路を概念的に説明する図である。
【図７】本発明の第２の実施形態におけるビット判定回路の実施例を説明する図である。
【図８】本発明の第３の実施形態における最長一致選択処理を概念的に説明する図である。
【図９】本発明の第３の実施形態における最長一致選択回路を概念的に説明する図である。
【図１０】本発明の第３の実施形態におけるビット判定回路の実施例を説明する図である。
【発明を実施するための形態】
【００２１】
以下、本発明を実施するための形態を、図面を参照して説明する。
図２Ａは、本発明の第１の実施形態における完全一致選択処理の一例を概念的に説明する図である。この例では、図２Ａに例示するビット列データ群１０１及び検索ビット列Ｓ２６０は、図１において例示したものと同じである。この例では、ビット列データ群１０１に検索ビット列Ｓと完全一致するビット列データが含まれる。
【００２２】
図２Ａに示すように、ステップ１では選択ビット列２１０ａには初期値として“１１１１”が設定されている。選択ビット列の初期値は、以下に説明する各実施形態において、全て“１１１１”である。選択ビット列２１０ａの左側に記載されたＥ１、Ｅ２、Ｅ３、Ｅ４は選択ビット列のビットを示しており、Ｅ１、Ｅ２、Ｅ３、Ｅ４の各ビットはビット列データＤ１、Ｄ２、Ｄ３、Ｄ４にそれぞれ対応している。ビットＥｘのビットが“１”であれば、それに対応するビット列データＤｘから取り出したビットをビット判定の対象として選択する。処理の態様としては、後に説明するように、ビット列データＤｘから取り出したビットと検索ビット列Ｓのビットとの比較結果を表すビットに対するビット演算により、ビット列データＤｘから取り出したビットをビット判定の対象として選択する。そこで以下の説明において、上述のビット演算を行うことを、ビット比較の結果に対してビット判定を行うということがある。また、選択ビット列を符号Ｅにより表記することがある。
【００２３】
ビット列データ群１０１には、各ビット列データのビット位置０、１、２が示されている。ビット位置毎に点線で囲まれたビットを取り出したビット列を同一位置ビット列と定義する。ビット列データＤ１、Ｄ２、Ｄ３、Ｄ４の各ビット位置０、１、２のビットを取り出すことにより、同一位置ビット列Ｆ１（２４０）、Ｆ２（２４１）、Ｆ３（２４２）が構成される。ステップ２以降では、同一ビット列の符号２４０、２４１、２４２は省略されている。なお、以下の説明において、同一位置ビット列を、サフィックスを省略して符号Ｆにより表記することがある。
【００２４】
図２Ａにおいて、検索ビット列Ｓ２６０にも、ビット位置０、１、２が示されている。各ビット位置の検索ビットをＳ１、Ｓ２、Ｓ３と表記している。なお、以下の説明において、検索ビットを、サフィックスを省略して符号Ｓにより表記することがある。
【００２５】
ステップ１では、双方向の矢印１６０ａで示すように、検索ビット列Ｓ２６０のビット位置０に位置する検索ビットＳ１と同一位置ビット列Ｆ１（２４０）の各ビットが比較される。さらに双方向の矢印２２０ａで示すように、同一位置ビット列Ｆ１（２４０）の各ビットに対するビット比較１６０ａの結果に対して選択ビット列２１０ａの対応する各選択ビットによりビット判定が行われる。
【００２６】
本発明の各実施形態においては、検索ビットと同一位置ビット列の各ビットの比較により、一致すればビット“１”を不一致であればビット“０”を比較の結果を表すものとする。そしてビット判定は、選択ビット列の“１”である選択ビットに対応するビット比較の結果が“１”であるかを判定する。この判定結果に基づいて、次のステップで選択ビット列として用いられる次選択ビット列を出力する。なお、以下の説明において、次選択ビット列を構成するビットを、次選択ビットに替えて選択ビットと呼ぶことがある。
【００２７】
上記判定でビット比較の結果が“１”であると判定すると、上述の“１”である選択ビットが対応するビット列データと同一のビット列データに対応する次選択ビット列の次選択ビットを“１”とし、ビット比較の結果が“０”であると判定すると、上述の“１”である選択ビットが対応するビット列データと同一のビット列データに対応する次選択ビット列の次選択ビットを“０”とする。また、“０”である選択ビットに対応するビット列データと同一のビット列データに対応する次選択ビット列の次選択ビットを“０”、すなわち上述の“０”である選択ビットとする。
【００２８】
図２Ａの例示では、検索ビットＳ１は“０”、同一位置ビット列Ｆ１（２４０）は“１００１”、選択ビット列２１０ａは“１１１１”、であるから、点線の矢印２３０ａで示すように、判定結果の次選択ビット列２１１ａは“０１１０”となる。
【００２９】
次のステップ２では、双方向の矢印１６０ｂで示すように、検索ビット列Ｓ２６０のビット位置１に位置する検索ビットＳ２と同一位置ビット列Ｆ２（２４１）の各ビットが比較される。さらに双方向の矢印２２０ｂで示すように、ステップ１における判定結果である次選択ビット列２１１ａが選択ビット列２１０ｂとして用いられ、同一位置ビット列Ｆ２（２４１）の各ビットに対するビット比較１６０ｂの結果に対して選択ビット列２１０ｂの対応する各選択ビットによりビット判定が行われる。
【００３０】
図２Ａの例示では、検索ビットＳ２は“１”、同一位置ビット列Ｆ２（２４１）は“１１１０”、選択ビット列２１０ｂは“０１１０”、であるから、点線の矢印２３０ｂで示すように、判定結果の次選択ビット列２１１ｂは“０１１０”となる。
【００３１】
次のステップ３では、双方向の矢印１６０ｃで示すように、検索ビット列Ｓ２６０のビット位置２に位置する検索ビットＳ３と同一位置ビット列Ｆ３（２４２）の各ビットが比較される。さらに双方向の矢印２２０ｃで示すように、ステップ２における判定結果である次選択ビット列２１１ｂが選択ビット列２１０ｃとして用いられ、同一位置ビット列Ｆ３（２４２）の各ビットに対するビット比較１６０ｃの結果に対して選択ビット列２１０ｃの対応する各選択ビットによりビット判定が行われる。
【００３２】
図２Ａの例示では、検索ビットＳ３は“０”、同一位置ビット列Ｆ３（２４２）は“１０１０”、選択ビット列２１０ｃは“０１１０”、であるから、点線の矢印２３０ｃで示すように、判定結果の次選択ビット列２１１ｃは“０１００”となる。
【００３３】
ステップ３までの処理により、最下位のビット位置までのビットの判定が終了するので、“次選択ビット列２１１ｃが検索ビット列Ｓと完全一致するビット列データを選択するための情報となる。
図２Ａの例示では、矢印２５０で示すように、選択ビットＥ２のみが“１”であり、選択ビットＥ２に対応するビット列データＤ２が検索ビット列Ｓと完全一致するビット列データであることが分かる。
【００３４】
以上の処理ステップを勝ち残りの競争に例えると、ビット列データの最上位ビットから最下位ビットまで、勝ち残ったビット列データの同一ビット位置のビットが検索ビット列Ｓの検索ビットと一致するかの判定を行い、一致するビット列データを勝者、一致しないビット列データを敗者として勝ち残りの選抜を行うものに相当する。但し、データ処理としては、検索ビットとのビット比較を先に行い、一致した同一ビット位置のビットが対応するビット列データが勝ち残ってきたものであるかの判定を次に行うものである。
【００３５】
上述の説明では、選択ビットＥｘが“１”であればそれに対応するビット列データＤｘから取り出したビットがビット判定の対象として選択される、としたが、選択ビットＥｘが“０”であればそれに対応するビット列データＤｘから取り出したビットをビット判定の対象として選択することにしても完全一致選択処理が可能であることは明らかである。そこで、ビット列データＤｘから取り出したビットをビット判定の対象として選択することを示す選択ビットＥｘを有意のビットと、あるいはその選択ビットＥｘは有意のビットであると、またビット列データＤｘから取り出したビットをビット判定の対象として選択しないことを示す選択ビットＥｘは有意のビットではないと、いうこともある。
【００３６】
さらに、上述の説明では、ビット比較の結果の一致をビット“１”で、不一致をビット“０”で表すとしたが、これも逆にすることが可能であることは明らかである。そこで、後に再度説明するが、ビット比較の結果を表すビットを判定ビットと定義し、一致を表す判定ビットは有意のビットである、あるいは有意であると、また比較の結果不一致であることを示す判定ビットは有意のビットではない、あるいは有意ではないと、いうこともある。
【００３７】
さらに、ビット列データ群の中に同一のビット列データが含まれていてもよい。その場合には、最下位ビット位置のビット判定の出力である次選択ビット列にビット“１”が複数存在する可能性が生まれる。
以上の選択ビット、判定ビット、及びビット列データの重複についての記述は、第１の実施形態に限らず、後に説明する第２の実施形態及び第３の実施形態においても同様に成り立つ。
【００３８】
図２Ｂは、本発明の第１の実施形態における完全一致選択処理の別の例を概念的に説明する図である。図２Ｂに例示するビット列データ群１０１は、図２Ａにおいて例示したものと同じである。図２Ｂに記載された検索ビット列Ｓ２６１は“００１”であり、図２Ａに記載された検索ビット列Ｓ２６０とは異なる。図２Ｂに記載されたでは、ビット列データ群１０１に検索ビット列Ｓ２６１と完全一致するビット列データは含まれていない。
【００３９】
ステップ１では、双方向の矢印１６１ａで示すように、検索ビット列Ｓ２６１のビット位置０に位置する検索ビットＳ１と同一位置ビット列Ｆ１（２４０）の各ビットが比較される。さらに双方向の矢印２２１ａで示すように、同一位置ビット列Ｆ１（２４０）の各ビットに対するビット比較１６１ａの結果に対して選択ビット列２１２ａの対応する各選択ビットによりビット判定が行われる。
【００４０】
図２Ｂの例示では、検索ビットＳ１は“０”、同一位置ビット列Ｆ１（２４０）は“１００１”、選択ビット列２１２ａは“１１１１”、であるから、点線の矢印２３１ａで示すように、判定結果の次選択ビット列２１３ａは“０１１０”となる。
【００４１】
次のステップ２では、双方向の矢印１６１ｂで示すように、検索ビット列Ｓ２６１のビット位置１に位置する検索ビットＳ２と同一位置ビット列Ｆ２（２４１）の各ビットが比較される。さらに双方向の矢印２２１ｂで示すように、ステップ１における判定結果である次選択ビット列２１３ａが選択ビット列２１２ｂとして用いられ、同一位置ビット列Ｆ２（２４１）の各ビットに対するビット比較１６１ｂの結果に対して選択ビット列２１２ｂの対応する各選択ビットによりビット判定が行われる。
【００４２】
図２Ｂの例示では、検索ビットＳ２は“０”、同一位置ビット列Ｆ２（２４１）は“１１１０”、選択ビット列２１０ｂは“０１１０”、であるから、点線の矢印２３１ｂで示すように、判定結果の次選択ビット列２１３ｂは“００００”となる。
【００４３】
次のステップ３では、双方向の矢印１６１ｃで示すように、検索ビット列Ｓ２６１のビット位置２に位置する検索ビットＳ３と同一位置ビット列Ｆ３（２４２）の各ビットが比較される。さらに双方向の矢印２２１ｃで示すように、ステップ２における判定結果である次選択ビット列２１３ｂが選択ビット列２１２ｃとして用いられ、同一位置ビット列Ｆ３（２４２）の各ビットに対するビット比較１６１ｃの結果に対して選択ビット列２１２ｃの対応する各選択ビットによりビット判定が行われる。
【００４４】
図２Ｂの例示では、検索ビットＳ３は“１”、同一位置ビット列Ｆ３は“１０１０”、選択ビット列２１２ｃは“００００”、であるから、点線の矢印２３１ｃで示すように、判定結果の次選択ビット列２１３ｃは“００００”となる。
【００４５】
ステップ３までの処理により、最下位のビット位置までのビットの判定が終了するので、“次選択ビット列２１３ｃが検索ビット列Ｓと完全一致するビット列データを選択するための情報となる。
図２Ｂの例示では、矢印２５０−１で示すように、“１”である選択ビットが存在しないので、検索ビット列Ｓと完全一致するビット列データに該当するものはビット列データ群には存在しないことが分かる。
【００４６】
次に本発明の第１の実施形態に係る回路について、図３及び図４を参照して説明する。図３及び図４において、図２Ａ及び図２Ｂと同様な部分の説明は省略する。
【００４７】
図３は、本発明の第１の実施形態における完全一致選択回路を概念的に説明する図である。
図３に例示するデータレジスタ群３０１には、図２Ａ及び図２Ｂに例示したビット列データ群１０１が格納されている。また、検索ビットレジスタ３７０には、図２Ａに例示した検索ビット列Ｓ２６０が格納されている。選択ビットレジスタ３１０には、選択ビット列の初期値“１１１１”が格納されている。
【００４８】
図３に示すように完全一致選択回路３００ａは、同一位置ビット列Ｆ１（２４０）に対応するビット判定回路３２０ａ、同一位置ビット列Ｆ２（２４１）に対応するビット判定回路３２０ｂ、及び同一位置ビット列Ｆ３（２４２）に対応するビット判定回路３２０ｃを含む。これらのビット判定回路は基本的には同じ構成を用いることができる。
【００４９】
データレジスタ群３０１に格納されたビット列データＤ１、Ｄ２、Ｄ３、Ｄ４の同一ビット位置のビットが取り出された同一位置ビット列Ｆ１、Ｆ２、Ｆ３は、それぞれ４ビットの並列バス３４０ａ、３４０ｂ、３４０ｃにより、ビット判定回路３２０ａ、３２０ｂ、３２０ｃに入力される。ビット判定回路３２０ａ、３２０ｂ、３２０ｃにおいて、それぞれ図２Ａに示すステップ１、２、３の処理が実行される。
【００５０】
選択ビットレジスタ３１０に格納された選択ビット列は、４ビットの並列バス３３０ａにより、ビット判定回路３２０ａに入力される。ビット判定回路３２０ａのビット判定結果出力３１０ｂは、４ビットの並列バス３３０ｂによりビット判定回路３２０ｂに入力される。次に、ビット判定回路３２０ｂのビット判定結果出力３１０ｃは、４ビットの並列バス３３０ｃによりビット判定回路３２０ｃに入力される。さらに、ビット判定回路３２０ｃのビット判定結果出力は、４ビットの並列バス３３０ｄにより選択結果レジスタ３６０に入力される。
【００５１】
図３の例示では、選択結果レジスタ３６０には、図２Ａに示す次選択ビット列２１１ｃが格納され、矢印３５０で示すように、ビットＥ２に対応するビット列データＤ２が検索ビット列レジスタ３７０に格納された検索ビット列Ｓと完全一致することが分かる。
【００５２】
図４は、本発明の第１の実施形態におけるビット判定回路の実施例を説明する図である。図４の（ａ）に示すのは、上記本発明の第１の実施形態のビット判定回路の実施例の回路構成である。この回路構成は、図３に示すビット判定回路３２０ａ、３２０ｂ、３２０ｃに共通である。図４の（ｂ）に示すのは、本発明の第１の実施形態におけるビット判定回路の実施例の構成要素の入出力論理を説明するものである。なお、以下の説明においては、ビット列データ群はｎ個のビット列データを含むものとする。なおｎビットの並列バスの各ビットを添え字ｘで表記することがある。
【００５３】
図４の（ａ）に示すように、ビット判定回路３２０は、ビット比較器４１０、次選択ビット設定器４２０を含んでいる。ビット判定回路３２０には、ｎビットの並列バス３４０により同一位置ビット列Ｆが入力され、またｎビットの並列バス３３０により選択ビット列Ｅが入力され、さらにシングルビットバス３４１により検索ビットＳが入力される。
【００５４】
上記入力された同一位置ビット列Ｆと検索ビットＳはビット比較器４１０に入力され、同一位置ビット列Ｆの各ビットと検索ビットＳとの論理演算により先に述べた判定ビットからなる判定ビット列Ｐが求められる。判定ビット列Ｐと選択ビット列Ｅは次選択ビット列設定器４２０に入力される。次選択ビット列設定器４２０では判定ビット列Ｐと選択ビット列Ｅのビットごとの論理演算が行われ、新たなビット列Ｑが求められる。ビット列Ｑは、次選択ビット列としてｎビットの並列バス３３１に出力される。なお、上述のように、ビット列のビットごとの論理演算により同じビット幅の新たなビット列を求めること、あるいは１つのビットを求めることをビット列演算ということがある。
【００５５】
図４の（ｂ）に示すのは、本発明の第１の実施の形態におけるビット比較器４１０のビット列演算Ｐと次選択ビット列設定器４２０のビット列演算Ｑの論理式である。記号“＊”は論理積を表すものとしている。
【００５６】
ビット比較器４１０のビット列演算の出力であるビット列ＰのビットＰｘは、同一位置ビット列ＦのビットＦｘの論理否定と検索ビットＳの論理否定との論理積と、ビットＦｘと検索ビットＳの論理積と、の論理和、すなわちビットＦｘと検索ビットＳの排他的論理和であり、ビットＦｘと検索ビットＳが一致するときに“１”となり、一致しないときは“０”である。
【００５７】
また、次選択ビット列設定器４２０のビット列演算の出力であるビット列ＱのビットＱｘは、上記ＰｘとＥｘの論理積である。すなわち、選択ビットＥｘが“１”のときＱｘはＰｘ、選択ビットＥｘが“０”のときＱｘは“０”、すなわちＥｘである。
上述のビット列演算Ｐとビット列演算Ｑにより、検索ビットＳに対する同一位置ビット列Ｆの各ビットのビット判定が行われ、ビット判定回路３２０から次選択ビット列が出力される。
【００５８】
次に図５〜図７を参照して本発明の第２の実施形態を説明する。この第２の実施形態は、部分一致選択に関するものである。
図５は、本発明の第２の実施形態における部分一致選択処理を概念的に説明する図である。図５に示すように、ビット列データ群１０１及び検索ビット列Ｓ２６１は、図２Ｂに記載したものと同じである。したがって、同様な部分の説明は省略する。
【００５９】
図５には、検索ビットＳとの同一性の判定を行わないビット列データＤｘのビットのビット位置を示すスキップビットからなるスキップビット列Ｋ２８０が示されている。ビット位置０のスキップビットＫ１は“０”、ビット位置１のスキップビットＫ２は“１”、ビット位置２のスキップビットＫ３は“０”である。
【００６０】
以下の説明において、スキップビット“１”が、スキップビットのビット位置に対応するビット列データＤｘのビットと検索ビットＳとの同一性の判定を行わないことを示す、とするが、スキップビット“０”が、スキップビットのビット位置に対応するビット列データＤｘのビットと検索ビットＳとの同一性の判定を行わないことを示す、としてもよいことは当業者には明らかである。そこで、選択ビット等と同様に、ビット列データＤｘのビットと検索ビットＳとの同一性の判定を行わないことを示すスキップビットを有意のビットと、あるいはそのスキップビットは有意のビットであると、またビット列データＤｘのビットと検索ビットＳとの同一性の判定をスキップしないことを示すスキップビットは有意のビットではないと、いうこともある。なお、以下の説明において、スキップビットをサフィックスを省略して符号Ｋにより表記することがある。
【００６１】
ステップ１では、双方向の矢印１６２ａで示すように、検索ビット列Ｓ２６１のビット位置０に位置する検索ビットＳ１と同一位置ビット列Ｆ１（２４０）の各ビットが比較される。さらに双方向の矢印２２２ａで示すように、同一位置ビット列Ｆ１（２４０）の各ビットに対するビット比較１６２ａの結果に対して選択ビット列２１４ａの対応する各選択ビットによりビット判定が行われる。
【００６２】
図５の例示では、検索ビットＳ１は“０”、同一位置ビット列Ｆ１（２４０）は“１００１”、選択ビット列２１４ａは“１１１１”、であり、スキップビットＫ１は“０”であるから、点線の矢印２９２ａで示すように、点線の矢印２３２ａで示す判定結果が出力されて次選択ビット列２１５ａは“０１１０”となる。
【００６３】
次のステップ２では、双方向の矢印１６２ｂで示すように、検索ビット列Ｓ２６１のビット位置１に位置する検索ビットＳ２“０”と同一位置ビット列Ｆ２（２４１）の各ビットが比較される。しかし、図５の例ではスキップビットＫ２が“１”であるため、比較結果は無視、あるいは比較されずにビット判定はスキップされ、点線の矢印２９２ｂ及び矢印２７２ｂに示すように、ステップ１における判定結果である次選択ビット列２１５ａが用いられた選択ビット列２１４ｂが、ステップ２の出力である次選択ビット列２１５ｂとされる。
【００６４】
次のステップ３では、双方向の矢印１６２ｃで示すように、検索ビット列Ｓ２６１のビット位置２に位置する検索ビットＳ３と同一位置ビット列Ｆ３（２４２）の各ビットが比較される。さらに双方向の矢印２２２ｃで示すように、ステップ２における判定結果である次選択ビット列２１４ｂが選択ビット列２１４ｃとして用いられ、同一位置ビット列Ｆ３（２４２）の各ビットに対するビット比較１６２ｃの結果に対して選択ビット列２１４ｃの対応する各選択ビットによりビット判定が行われる。
【００６５】
図５の例示では、検索ビットＳ３は“１”、同一位置ビット列Ｆ３（２４２）は“１０１０”、選択ビット列２１４ｃは“０１１０”、であり、スキップビットＫ２は“０”であるから、点線の矢印２９２ｃで示すように、点線の矢印２３２ｃで示す判定結果が出力されて次選択ビット列２１５ｃは“００１０”となる。
【００６６】
ステップ３までの処理により、最下位のビット位置までのビットの判定が終了するので、“次選択ビット列２１５ｃが検索ビット列Ｓと部分一致するビット列データを選択するための情報となる。
図５の例示では、矢印２５１で示すように、選択ビットＥ３が“１”であり、選択ビットＥ３に対応するビット列データＤ３が検索ビット列Ｓと部分一致するビット列データであることが分かる。
【００６７】
次に本発明の第２の実施形態に係る回路について、図６及び図７を参照して説明する。図６及び図７において、図５と同様な部分の説明は省略する。
【００６８】
図６は、本発明の第２の実施形態における部分一致選択回路を概念的に説明する図である。
図６に例示するデータレジスタ群３０１には、図５に例示したビット列データ群１０１が格納されている。また、検索ビットレジスタ３７０には、図５に例示した検索ビット列Ｓ２６１が格納されている。スキップビットレジスタ３８０には、図５に例示したスキップビット列Ｋ２８０が格納されている。選択ビットレジスタ３１０には、選択ビット列の初期値“１１１１”が格納されている。
【００６９】
図６に示すように部分一致選択回路３００ｂは、同一位置ビット列Ｆ１（２４０）に対応するビット判定回路３２１ａ、同一位置ビット列Ｆ２（２４１）に対応するビット判定回路３２１ｂ、及び同一位置ビット列Ｆ３（２４２）に対応するビット判定回路３２１ｃを含む。これらのビット判定回路は基本的には同じ構成を用いることができる。
【００７０】
データレジスタ群３０１に格納されたビット列データＤ１、Ｄ２、Ｄ３、Ｄ４の同一ビット位置のビットが取り出された同一位置ビット列Ｆ１、Ｆ２、Ｆ３は、それぞれ４ビットの並列バス３４２ａ、３４２ｂ、３４２ｃにより、ビット判定回路３２１ａ、３２１ｂ、３２１ｃに入力される。ビット判定回路３２１ａ、３２１ｂ、３２１ｃにおいて、それぞれ図５に示すステップ１、２、３の処理が実行される。
【００７１】
選択ビットレジスタ３１０に格納された選択ビット列は、４ビットの並列バス３３１ａにより、ビット判定回路３２１ａに入力される。ビット判定回路３２１ａのビット判定結果出力３１３ｂは、４ビットの並列バス３３１ｂによりビット判定回路３２１ｂに入力される。次に、ビット判定回路３２１ｂのビット判定結果出力３１３ｃは、４ビットの並列バス３３１ｃによりビット判定回路３２１ｃに入力される。さらに、ビット判定回路３２１ｃのビット判定結果出力は、４ビットの並列バス３３１ｄにより選択結果レジスタ３６０に入力される。
【００７２】
図６の例示では、選択結果レジスタ３６０には、図５に示す次選択ビット列２１５ｃが格納され、矢印３５１で示すように、ビットＥ３に対応するビット列データＤ３が検索ビット列レジスタ３７０に格納された検索ビット列Ｓと部分一致することが分かる。
【００７３】
図７は、本発明の第２の実施形態におけるビット判定回路の実施例を説明する図である。図７の（ａ）に示すのは、上記本発明の第２の実施形態のビット判定回路の実施例の回路構成である。この回路構成は、図６に示すビット判定回路３２１ａ、３２１ｂ、３２１ｃに共通である。図７の（ｂ）に示すのは、本発明の第２の実施形態におけるビット判定回路の実施例の構成要素の入出力論理を説明するものである。
【００７４】
図７の（ａ）に示すように、ビット判定回路３２１は、ビット比較器４１０、次選択ビット設定器４２０及び判定結果選択器４４０を含んでいる。ビット判定回路３２１には、ｎビットの並列バス３４２により同一位置ビット列Ｆが入力され、またｎビットの並列バス３３１により選択ビット列Ｅが入力され、さらにシングルビットバス３４３により検索ビットＳが入力され、シングルビットバス３８１によりスキップビットＫが入力される。
【００７５】
図７の（ａ）に示すビット比較器４１０と次選択ビット設定器４２０は図４の（ａ）に記載したものと同一であり、したがって、それらの入出力論理も同一であるから、ビット比較器４１０と次選択ビット設定器４２０及び図７の（ｂ）に示す論理式の説明は省略する。
判定結果選択器４４０は、スキップビットＫが有意であれば、選択ビット列Ｅを出力ビット列Ｚとし、スキップビットＫが有意でなければ、次選択ビット設定器４２０の出力であるビット列Ｑを出力ビット列Ｚとする。この出力ビット列Ｚが、ビット判定回路３２１から次選択ビット列として出力される。
【００７６】
次に図８〜図１０を参照して本発明の第３の実施形態を説明する。この第３の実施形態は、最長一致選択に関するものである。ここでいう最長一致とは、検索ビット列の最上位側のビットと一致するビット列データの最上位のビットからのビット長が最長であることを言う。
図８は、本発明の第３の実施形態における最長一致選択処理を概念的に説明する図である。図８に示すように、ビット列データ群１０１及び検索ビット列Ｓ２６１は、図２Ｂに記載したものと同じである。したがって、同様な部分の説明は省略する。
【００７７】
ステップ１では、双方向の矢印１６３ａで示すように、検索ビット列Ｓ２６１のビット位置０に位置する検索ビットＳ１と同一位置ビット列Ｆ１（２４０）の各ビットが比較される。さらに双方向の矢印２２４ａで示すように、同一位置ビット列Ｆ１（２４０）の各ビットに対するビット比較１６３ａの結果に対して選択ビット列２１６ａの対応する各選択ビットによりビット判定が行われる。
【００７８】
図８の例示では、検索ビットＳ１は“０”、同一位置ビット列Ｆ１（２４０）は“１００１”、選択ビット列２１６ａは“１１１１”、であるから、点線の矢印２３４ａで示すように、判定結果の次選択ビット列２１７ａは“０１１０”となる。
【００７９】
次のステップ２では、双方向の矢印１６３ｂで示すように、検索ビット列Ｓ２６１のビット位置１に位置する検索ビットＳ２と同一位置ビット列Ｆ２（２４１）の各ビットが比較される。さらに双方向の矢印２２４ｂで示すように、ステップ１における判定結果である次選択ビット列２１７ａが選択ビット列２１６ｂとして用いられ、同一位置ビット列Ｆ２（２４１）の各ビットに対するビット比較１６３ｂの結果に対して選択ビット列２１６ｂの対応する各選択ビットによりビット判定が行われる。
【００８０】
図８の例示では、検索ビットＳ２は“０”、同一位置ビット列Ｆ２（２４１）は“１１１０”、選択ビット列２１６ｂは“０１１０”、であるから、点線の矢印２３４ｂで示すように、判定結果の次選択ビット列２１７ｂ−１は“００００”となり、検索ビット列Ｓとビット位置０からビット位置１までのビットが全て一致するビット列データは存在しない。
【００８１】
そこで、点線の矢印２３５ｂと矢印２２４ｂ−１で示すように、選択ビット列２１６ｂがステップ２における次選択ビット列２１７ｂとして出力される。また、ステップ２において、検索ビット列Ｓと最上位のビット位置であるビット位置０からビット位置１までのビットが全て一致するビット列データは存在しない、すなわち検索ビット列Ｓと完全一致するビット列データは不存在と判定した履歴（以下、判定履歴ということがある。）が、点線の矢印２３５ｃで示すように、ステップ３に継承される。
【００８２】
次のステップ３では、双方向の矢印１６３ｃで示すように、検索ビット列Ｓ２６１のビット位置２に位置する検索ビットＳ３と同一位置ビット列Ｆ３（２４２）の各ビットが比較される。さらに双方向の矢印２２４ｃで示すように、ステップ２における判定結果である次選択ビット列２１７ｂが選択ビット列２１６ｃとして用いられ、同一位置ビット列Ｆ３（２４２）の各ビットに対するビット比較１６３ｃの結果に対して選択ビット列２１６ｃの対応する各選択ビットによりビット判定が行われる。
【００８３】
図８の例示では、検索ビットＳ３は“１”、同一位置ビット列Ｆ３（２４２）は“１０１０”、選択ビット列２１６ｃは“０１１０”、であるから、点線の矢印２３４ｃで示すように、判定結果の次選択ビット列２１７ｃ−１は“００１０”となる。
しかし、点線の矢印２３５ｃで示すように、ステップ２における判定履歴がステップ３に継承されているので、矢印２２４ｃ−１で示すように、選択ビット列２１７ｂがステップ３における次選択ビット列２１７ｃとして出力される。
【００８４】
ステップ３までの処理により、最下位のビット位置までのビットの判定が終了するので、“次選択ビット列２１７ｃが検索ビット列Ｓと最長一致するビット列データを選択するための情報となる。
図８の例示では、矢印２５２で示すように、選択ビットＥ２、Ｅ３が“１”であり、選択ビットＥ２、Ｅ３に対応するビット列データＤ２、Ｄ３が検索ビット列Ｓと最長一致するビット列データであることが分かる。
【００８５】
次に本発明の第３の実施形態に係る回路について、図９及び図１０を参照して説明する。図９及び図１０において、図８と同様な部分の説明は省略する。なお、以下の説明において、図８を参照して説明した判定履歴の有無を表すビットを履歴ビットと呼び、判定履歴ありを表す履歴ビットを有意のビットと、あるいはその履歴ビットは有意であるということがある。また、判定履歴なしを表す履歴ビットは有意のビットではない、あるいは有意ではないということがある。
【００８６】
図９は、本発明の第３の実施形態における最長一致選択回路を概念的に説明する図である。
図９に例示するデータレジスタ群３０１には、図８に例示したビット列データ群１０１が格納されている。また、検索ビットレジスタ３７０には、図８に例示した検索ビット列Ｓ２６１が格納されている。選択ビットレジスタ３１０には、選択ビット列の初期値“１１１１”が格納されている。
【００８７】
図９に示すように最長一致選択回路３００ｃは、同一位置ビット列Ｆ１（２４０）に対応するビット判定回路３２４ａ、同一位置ビット列Ｆ２（２４１）に対応するビット判定回路３２４ｂ、及び同一位置ビット列Ｆ３（２４２）に対応するビット判定回路３２４ｃを含む。これらのビット判定回路は基本的には同じ構成を用いることもできる。
【００８８】
データレジスタ群３０１に格納されたビット列データＤ１、Ｄ２、Ｄ３、Ｄ４の同一ビット位置のビットが取り出された同一位置ビット列Ｆ１、Ｆ２、Ｆ３は、それぞれ４ビットの並列バス３４４ａ、３４４ｂ、３４４ｃにより、ビット判定回路３２４ａ、３２４ｂ、３２４ｃに入力される。ビット判定回路３２４ａ、３２４ｂ、３２４ｃにおいて、それぞれ図８に示すステップ１、２、３の処理が実行される。
【００８９】
選択ビットレジスタ３１０に格納された選択ビット列は、４ビットの並列バス３３４ａにより、ビット判定回路３２４ａに入力される。また、判定履歴の有無を表す履歴ビットは、ビット判定回路３２４ａが最上位のビット位置についての同一位置ビット列に対応するものであるので、初期値として有意でない履歴ビット、図１０の例では“０”がシングルビットバス３３５ａによりビット判定回路３２４ａに入力される。ビット判定回路３２４ａのビット判定結果出力３１４ｂは、４ビットの並列バス３３４ｂによりビット判定回路３２４ｂに入力される。また、ビット判定回路３２４ａの判定履歴の有無を表す履歴ビットは、シングルビットバス３３５ｂによりビット判定回路３２４ｂに入力される。次に、ビット判定回路３２４ｂのビット判定結果出力３１４ｃは、４ビットの並列バス３３４ｃによりビット判定回路３２４ｃに入力される。また、ビット判定回路３２４ｂから出力される履歴ビットは、シングルビットバス３３５ｃによりビット判定回路３２４ｃに入力される。さらに、ビット判定回路３２４ｃのビット判定結果出力は、４ビットの並列バス３３４ｄにより選択結果レジスタ３６０に入力される。
【００９０】
図９の例示では、選択結果レジスタ３６０には、図８に示す次選択ビット列２１７ｃが格納され、矢印３５２で示すように、ビットＥ２に対応するビット列データＤ２とビットＥ３に対応するビット列データＤ３が検索ビット列レジスタ３７０に格納された検索ビット列Ｓと最長一致することが分かる。
【００９１】
図１０は、本発明の第３の実施形態におけるビット判定回路の実施例を説明する図である。図１０の（ａ）に示すのは、上記本発明の第３の実施形態のビット判定回路の実施例の回路構成である。図１０の（ｂ）に示すのは、本発明の第３の実施形態におけるビット判定回路の実施例の構成要素の入出力論理を説明するものである。
【００９２】
図１０の（ａ）に示すように、ビット判定回路３２４は、ビット比較器４１０、次選択ビット設定器４２０、全不一致判定器４３０、判定結果選択器４４０及びＯＲ回路４７０を含んでいる。ビット判定回路３２４には、ｎビットの並列バス３４４により同一位置ビット列Ｆが入力され、またｎビットの並列バス３３４により選択ビット列Ｅが入力され、さらにシングルビットバス３４５により検索ビットＳが入力され、シングルビットバス３３５により履歴ビットＭが入力される。
【００９３】
図１０の（ａ）に示すビット比較器４１０と次選択ビット設定器４２０は図７の（ａ）に記載したものと同一であり、したがって、それらの入出力論理も同一であるから、ビット比較器４１０と次選択ビット設定器４２０及び図７の（ｂ）に示すＰｘとＱｘの論理式の説明は省略する。
図１０の（ａ）に示す判定結果選択器４４０は、図７の（ａ）に記載したものと、セレクタ端子ｓに入力されるビットがスキップビットＫではない点で異なり、入力と出力は同じである。すなわち、入力切り替えの論理が異なるだけである。
【００９４】
全不一致判定器４３０は、判定ビット列Ｐと選択ビット列Ｅとのビット列演算を図１０の（ｂ）に示す論理式により実行し、全不一致ビットＲを求める。全不一致ビットＲは、ビットごとのＰｘとＥｘの論理積の論理否定を全てのビットについて論理積を取ったものである。Ｒの値は、Ｅｘが“１”である全てのビットについてＰｘが“０”のときのみ“１”であり、Ｅｘが“１”でありＰｘが“１”のビットが少なくとも１つ存在する場合は“０”である。すなわち、対応する選択ビットが有意である同一位置ビット列のビットに対応する判定ビットが全て有意でないとき、言い換えれば上記同一位置ビット列のビットが全て対応する検索ビットと不一致であるときのみ、全不一致ビットＲは“１”である。
【００９５】
全不一致ビットＲと履歴ビットＭはＯＲ回路４７０に入力される。全不一致ビットＲと履歴ビットＭの論理和であるＯＲ回路４７０の出力Ｕは、シングルビットバス３３５−１によりビット判定回路３２４から履歴ビットとして出力されるとともに、ライン３３５−２を介して判定結果選択器４４０のセレクタ端子ｓに入力される。
判定結果選択器４４０は、ＯＲ回路４７０の出力Ｕが“０”であれば次選択ビット設定器４２０の出力であるビット列Ｑを出力ビット列Ｚとし、ＯＲ回路４７０の出力Ｕが“１”であれば選択ビット列Ｅを出力ビット列Ｚとする。この出力ビット列Ｚがビット判定回路３２４からｎビットの並列バス３３１により次選択ビット列として出力される。
【００９６】
なお、ビット列データ群に属する全てのビット列データの最上位ビットが検索ビット列の最上位ビットと一致しないという例外的な入力が想定される場合には、図４の（ａ）に示すビット判定回路３２０を用いて、ビット列データの最上位ビットの一致判定を行い、その判定結果出力を選択ビット列として、選択ビットレジスタ３１０に替えて、４ビットの並列バス３３４ａにより、ビット判定回路３２４ａに入力するようにすればよい。
【００９７】
以上、本発明の実施の形態について詳細に説明したことから明らかなとおり、本発明によれば受動回路によりビット列データ群からビット列データを選択する回路を構成できるので、高速な動作が可能である。また、上述の説明に限らず本発明の実施の形態について種々の変形が可能なことは当業者に明らかである。
本発明の実施の形態には、詳細に説明をしたビット判定回路とビット列データ選択回路のほか、図２Ａ、図５、図８に記載した処理ステップによるビット列データ選択方法を含む。これらのビット列データ選択方法をハードウェア回路で実行するものとして説明したが、これらのビット列データ選択方法をコンピュータ上のソフトウェアにより実現できることも当業者に明らかである。
【図１】
2014102924.tif 000003
【図２Ａ】
2014102924.tif 000004
【図２Ｂ】
2014102924.tif 000005
【図３】
2014102924.tif 000006
【図４】
2014102924.tif 000007
【図５】
2014102924.tif 000008
【図６】
2014102924.tif 000009
【図７】
2014102924.tif 000010
【図８】
2014102924.tif 000011
【図９】
2014102924.tif 000012
【図１０】
2014102924.tif 000013
【国際調査報告】
2014102924.tif 000014
2014102924.tif 000015