(57)【要約】【課題】  向上された性能を有するデータ抽出装置及び方法を提供すること。【解決手段】  データを抽出する装置及び方法が提供される。一実施形態に係るデータ抽出装置は、入力データと入力データの補数を利用して、最右側に現れる対象値のビット位置を抽出し、対象値のビット位置を順次的に抽出して出力することができる。【選択図】      図１
2017151986.tif 000002
【特許請求の範囲】
【請求項１】
第０乃至第Ｎ−１ビット位置を含むビット位置に任意に配置された対象値を含む入力データを受信する、ように構成されるデータ受信部（但し、Ｎは１より大きい整数）と、
前記入力データの前記ビット位置をビット値を反転し、前記反転された入力データに１の値を追加することによって、前記入力データの補数（ｃｏｍｐｌｅｍｅｎｔ）を生成する、ように構成される補数生成部と、
前記入力データ及び前記補数に基づいて、前記入力データの前記ビット位置の目標値の中で前記入力データで第０ビット位置、および、最も短いか又は配置された前記目標値を含むビット位置を抽出する、ように構成されるビット位置抽出部と、
前記抽出されたビット位置を出力する、ように構成されるプロセッサと、
を含む、データ抽出装置。
【請求項２】
前記ビット位置抽出部は、前記入力データから前記目標値を含む前記ビット位置を順次的に出力する、
請求項１に記載のデータ抽出装置。
【請求項３】
現在サイクルで抽出された前記ビット位置のビット値を初期化することによって前記入力データを変換し、次のサイクルで使用されるように前記変換された入力データを出力するように構成されるデータ変換部、
をさらに含む、請求項１または２に記載のデータ抽出装置。
【請求項４】
前記データ変換部は、
前記抽出されたビット位置及び前記入力データの対応するビット値に対してビット間（ｂｉｔｗｉｓｅ）排他的論理和（ＸＯＲ；ｅｘｃｌｕｓｉｖｅ  ＯＲ）演算を遂行する、ように構成される排他的論理和ゲート、
を含む、請求項３に記載のデータ抽出装置。
【請求項５】
前記ビット位置抽出部は、前記入力データから前記対象値を含む最右側（ｒｉｇｈｔｍｏｓｔ）ビット位置を順次的に抽出する、ように構成され、
前記最右側ビット位置は、前記対象値を含み、前記ビット位置抽出部に入力される前記入力データの前記第０ビット位置に近接するように位置するビット位置である、
請求項１または２に記載のデータ抽出装置。
【請求項６】
前記ビット位置抽出部は、
前記補数及び前記入力データの対応するビット値に対するビット間論理積ＡＮＤ演算を遂行することによって、１つのビット位置のみが前記対象値と対応する値を有するビット位置データを生成するように構成される論理積ゲート（ＡＮＤ  ｇａｔｅ）を含む回路、を有し、
前記ビット位置抽出部は、前記ビット位置データから前記第０ビット位置と近接するか、又は位置する前記対象値を含む前記ビット位置を抽出する、ように構成される、
請求項１乃至５いずれか一項に記載のデータ抽出装置。
【請求項７】
前記補数生成部は、
前記入力データに対するビット間ＮＯＴ演算を遂行することによって前記ビット値が前記入力データの前記ビット値に対して反転される、反転された入力データを生成する、ように構成されるＮＯＴゲートと、
前記反転された入力データに１の値を加算することによって前記補数を生成する、ように構成される加算器と、
を含む、請求項１乃至６いずれか一項に記載のデータ抽出装置。
【請求項８】
出力部をさらに含み、
前記プロセッサは、クロック信号を生成し、前記クロック信号に基づいて順次的に抽出された前記ビット位置の各々を出力するように前記出力部を制御する、ように構成される、
請求項１乃至７いずれか一項に記載のデータ抽出装置。
【請求項９】
前記出力部は、二進ログ（ｂｉｎａｒｙ  ｌｏｇ）値の形態に前記抽出されたビット位置の各々を出力する、ように構成される、
請求項８に記載のデータ抽出装置。
【請求項１０】
前記対象値を含む前記ビット位置の全部が前記入力データから抽出されたものと判別されたことに応答して、終了信号を生成する、ように構成される終了決定部（ｔｅｒｍｉｎａｔｉｏｎ  ｄｅｔｅｒｍｉｎｅｒ）、
をさらに含む、請求項１乃至９いずれか一項に記載のデータ抽出装置。
【請求項１１】
前記データ受信部は、前記入力データに対してビット間ＮＯＴ演算を遂行するように構成され、前記ビット間ＮＯＴ演算を通じて獲得された前記入力データを前記補数生成部及び前記ビット位置抽出部に伝送する、ように構成される、
請求項１乃至１０いずれか一項に記載のデータ抽出装置。
【請求項１２】
ピクセルを含むイベントセンサーをさらに含み、
イベントが発生する時の前記ピクセルの位置は、前記データ受信部によって受信された前記入力データとして使用される、
請求項１乃至１１いずれか一項に記載のデータ抽出装置。
【請求項１３】
第０ビット位置乃至第Ｎ−１ビット位置（但し、Ｎは１より大きい整数）を含むビット位置で任意に配置された対象値を含む入力データを受信する段階と、
前記入力データの前記ビット位置のビット値を反転し、前記反転された入力データに１の値を追加することによって前記入力データの補数を生成する段階と、
前記入力データ及び前記補数に基づいて前記入力データの前記ビット位置の前記対象値の中で前記入力データの前記第０ビット位置と近接するか、又は、位置する対象値を含むビット位置を抽出する段階と、
前記抽出されたビット位置を出力する段階と、
を含む、データ抽出方法。
【請求項１４】
前記対象値を含む前記ビット位置を順次的に抽出する段階、
をさらに含む、請求項１３に記載のデータ抽出方法。
【請求項１５】
前記抽出されたビット位置及び前記入力データの対応するビット値でビット間排他的論理積（ＸＯＲ；ｅｘｃｌｕｓｉｖｅ  ＯＲ）演算を遂行することによって前記入力データを変換し、次のサイクルで前記変換された入力データを使用する段階、
をさらに含む、請求項１３または１４に記載のデータ抽出方法。
【請求項１６】
前記ビット位置を抽出する段階は、
前記補数及び前記入力データの対応するビット値に対してビット間論理積（ｂｉｔｗｉｓｅ  ＡＮＤ）演算を遂行することによって、一つのビット位置のみが前記対象値に対応する値を有するビット位置データを生成する段階と、
前記ビット位置データから前記対象値を有する最右側ビット位置を抽出する段階と、を含み、
前記最右側ビット位置は、前記第０ビット位置に近接したビット位置である、
請求項１３乃至１５いずれか一項に記載のデータ抽出方法。
【請求項１７】
クロック信号に基づいて前記ビット位置の各々を順次的に抽出し、出力する段階、
をさらに含む、請求項１６に記載のデータ抽出方法。
【請求項１８】
前記出力する段階は、
前記抽出されたビット位置の各々を二進ログ（ｂｉｎａｒｙ  ｌｏｇ）値の形態として出力する段階、
を含む、請求項１７に記載のデータ抽出方法。
【請求項１９】
前記対象値を含む前記ビット位置の全部が前記入力データから抽出されたものと判別されたことに応答して、終了信号を生成する段階、
をさらに含む、請求項１７または１８に記載のデータ抽出方法。
【請求項２０】
前記入力データを受信する段階は、ピクセルを含むイベントセンサーから前記入力データを受信する段階、を含み、
イベントが発生する場合の前記ピクセルの位置は、前記入力データとして使用される、
請求項１３乃至１９いずれか一項に記載のデータ抽出方法。
【請求項２１】
入力データをグループに分類することによってグループデータを生成するように構成されるグループ化部と、
前記グループデータから対象グループ値のグループビット位置を抽出するように構成されるグループ抽出部と、
前記グループビット位置に基づいて前記グループを選択し、前記入力データから前記選択されたグループに対応する部分データを選択するように構成されるグループ選択部と、
前記部分データから対象値のビット位置を順次的に抽出するように構成されるデータ抽出部と、
前記抽出されたビット位置を出力するように構成されるプロセッサと、
を含む、データ抽出装置。
【請求項２２】
前記グループ抽出部は、前記対象値に対応するすべてのビット位置が前記部分データから前記データ抽出部によって抽出されたものと判別されたことに応答して、前記対象グループ値の次のグループビット位置を抽出する、ように構成され、
前記グループ選択部は、前記次のグループビット位置に基づいて次の部分データを選択する、ように構成される、
請求項２１に記載のデータ抽出装置。
【請求項２３】
ソフトウェアプログラムを含む有形のコンピュータ読出し可能な記録媒体であって、
前記ソフトウェアプログラムがプロセッサによって実行されると、データ抽出方法が遂行され、前記データ抽出方法は、
第０ビット位置乃至第Ｎ−１ビット位置（但し、Ｎは１より大きい整数）を含むビット位置で任意に配置された対象値を含む入力データを受信する段階と、
前記入力データの前記ビット位置のビット値を反転し、前記反転された入力データに１の値を追加することによって、前記入力データの補数を生成する段階と、
前記入力データ及び前記補数に基づいて、前記入力データの前記ビット位置の目標値の中で前記第０ビット位置と近接するか、又は、前記第０ビット位置に位置する第１ビット位置のみを維持される対象値を含むビット位置データを生成する段階と、
前記ビット位置データに基づいて、前記対象値を含む前記第１ビット位置を抽出する段階と、
前記抽出されたビット位置をセンサーの検出結果として出力する段階と、
を含む有形のコンピュータ読出し可能な記録媒体。
【請求項２４】
前記データ抽出方法は、クロック信号に基づいて各サイクルで再生成された前記ビット位置データに基づいて、前記対象値を含む第２ビット位置を順次的に抽出する段階、をさらに含み、
前記第２ビット位置の各々は、連続されたサイクルの各々で前記対象値を含み、前記第１ビット位置と近接した連続的なビット位置である、
請求項２３に記載の有形のコンピュータ読出し可能な記録媒体。
【請求項２５】
前記データ抽出方法は、
前記ビット位置データで、現在サイクルで抽出された前記第１ビット位置のビット値を初期化することによって前記入力データを変換する段階と、
次のサイクルで使用されるように前記変換された入力データを出力する段階と、
前記変換された入力データの前記ビット位置の前記ビット値を反転し、前記反転された変換された入力データに１の値を追加することによって前記変換された入力データの補数を生成する段階と、
次のサイクルで前記変換された入力データの前記補数及び前記変換された入力データに基づいて生成された前記ビット位置データから前記対象値を含む第２ビット位置を抽出する段階と、をさらに含み、
前記第２ビット位置は、前記次のサイクルで前記対象値を含み、前記第１ビット位置と隣接するビット位置である、
請求項２３または２４に記載の有形のコンピュータ読出し可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
以下、データを抽出する装置及び方法が提供される。
【背景技術】
【０００２】
複数のエレメントを含むセンサーは各々のエレメント毎に信号を感知するための検出素子、検出素子で感知された信号を増幅するためのアナログ回路、及び、増幅された信号を処理するデジタル回路（ｄｉｇｉｔａｌ  ｃｉｒｃｕｉｔ）を含むことができる。
【０００３】
但し、複数のエレメントを含むセンサーは一定な位置のエレメントでデータが均一に発生することではなく、使用条件、環境、及び状況等によって無作為に発生し得るが、この時、各エレメントの全部を探索する場合、不必要な電力消耗が発生することがあり、デジタル回路での信号処理効率が減少されることがある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許公開第２０１３／００３８５８３号明細書
【特許文献２】特開２０１４−０１７５８３４号公報
【特許文献３】特開２００５−００６５３４０号公報
【特許文献４】特開２００９−０２７３０７９号公報
【特許文献５】韓国特許公開第１０−２００３−００８２２５５号明細書
【特許文献６】韓国登録特許第１０−０４５０７５０号公報
【特許文献７】特開２００５−００６３５４０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の目的は向上された性能を有するデータ抽出装置及び方法を提供することにある。
【課題を解決するための手段】
【０００６】
一実施形態によれば、入力データ（ｉｎｐｕｔ  ｄａｔａ）を受信するデータ受信部、入力データの補数（ｃｏｍｐｌｅｍｅｎｔ）を生成する補数生成部、及び、入力データ及び補数に基づいて、入力データから対象値（ｔａｒｇｅｔ  ｖａｌｕｅ）のビット位置（ｂｉｔ  ｐｏｓｉｔｉｏｎ）を抽出するビット位置抽出部を含むデータ抽出装置が提供され得る。
【０００７】
データ抽出装置は、入力データから対象値が存在するビット位置を順次的に抽出することができる。
【０００８】
データ抽出装置は、入力データから対象値のビット位置を抽出した後、抽出されたビット位置の値を初期化して入力データを変換するデータ変換部をさらに含み、データ受信部は変換された入力データをデータ変換部から受信して、補数生成部、ビット位置抽出部、及び、データ変換部の中で少なくとも１つに伝達することができる。
【０００９】
データ変換部は、入力データ及び抽出されたビット位置に対してビット間（ｂｉｔｗｉｓｅ）排他的論理和（ＸＯＲ、ｅｘｃｌｕｓｉｖｅ  ＯＲ）演算を遂行する排他的論理和ゲート（ＸＯＲ  ｇａｔｅ）を含むことができる。
【００１０】
ビット位置抽出部は、入力データで対象値が示す最右側（ｒｉｇｈｔｍｏｓｔ）のビット位置を抽出することができる。
【００１１】
ビット位置抽出部は、入力データ及び補数に対してビット間論理積（ｂｉｔｗｉｓｅ  ＡＮＤ）演算を遂行する論理積ゲート（ＡＮＤ  ｇａｔｅ）を含むことができる。
【００１２】
補数生成部は、入力データに対してビット間ＮＯＴ（ｂｉｔｗｉｓｅ  ＮＯＴ）演算を遂行するＮＯＴゲート（ＮＯＴ  ｇａｔｅ）、及び、ＮＯＴ演算（ＮＯＴ  ｏｐｅｒａｔｉｏｎ）が遂行された入力データに対して１の値を付加（ａｄｄ）する加算器（ａｄｄｅｒ）を含むことができる。
【００１３】
データ抽出装置は、抽出されたビット位置を出力する出力部をさらに含むことができる。
【００１４】
出力部は、ビット位置を二進ログ（ｂｉｎａｒｙ  ｌｏｇ）値の形態に出力することができる。
【００１５】
データ抽出装置は、入力データから対象値が存在するすべてのビット位置が抽出されたものと判断された場合に応答して、終了信号を生成する終了決定部（ｔｅｒｍｉｎａｔｉｏｎ  ｄｅｔｅｒｍｉｎｅｒ）をさらに含むことができる。
【００１６】
データ受信部は、入力データに対してビット間ＮＯＴ演算（ｂｉｔｗｉｓｅ  ＮＯＴ  ｏｐｅｒａｔｉｏｎ）を遂行し、ＮＯＴ演算が遂行された入力データを補数生成部及びビット位置抽出部の中で少なくとも１つに伝達することができる。
【００１７】
一実施形態に係るデータ抽出方法は入力データ（ｉｎｐｕｔ  ｄａｔａ）を受信する段階、入力データの補数（ｃｏｍｐｌｅｍｅｎｔ）を生成する段階、及び、入力データ及び補数に基づいて、入力データから対象値（ｔａｒｇｅｔ  ｖａｌｕｅ）のビット位置（ｂｉｔ  ｐｏｓｉｔｉｏｎ）を抽出する段階、を含むことができる。
【００１８】
データ抽出方法は、入力データから対象値が存在するビット位置を順次的に抽出する段階をさらに含むことができる。
【００１９】
データ抽出方法は、入力データから対象値のビット位置を抽出した後、抽出されたビット位置の値を初期化して入力データを変換する段階、変換された入力データの補数を利用して、変換された入力データから対象値のビット位置を抽出する段階をさらに含むことができる。
【００２０】
ビット位置を抽出する段階は、入力データで対象値が現れる最右側（ｒｉｇｈｔｍｏｓｔ）のビット位置を抽出する段階を含むことができる。
【００２１】
データ抽出方法は、抽出されたビット位置を出力する段階をさらに含むことができる。
【００２２】
出力する段階は、ビット位置を二進ログ（ｂｉｎａｒｙ  ｌｏｇ）値の形態に出力する段階を含むことができる。
【００２３】
データ抽出方法は、入力データから対象値が存在するすべてのビット位置が抽出されたものと判断された場合に応答して、終了信号を生成する段階をさらに含むことができる。
【００２４】
他の一実施形態によれば、入力データを複数のグループに分類してグループデータを生成するグループ化部、グループデータから対象グループ値のグループビット位置を抽出するグループ抽出部、グループビット位置に基づいてグループを選択し、入力データから選択されたグループに対応する部分データを選択するグループ選択部、及び、選択されたグループに対応する部分データから対象値のビット位置を順次的に抽出するデータ抽出部を含むグループに基づいたデータ抽出装置が提供され得る。
【００２５】
グループ抽出部は、データ抽出部が部分データから対象値のすべてのビット位置を抽出したものと判断された場合に応答して、グループ対象値の次のグループビット位置を抽出し、グループ選択部は、次のグループビット位置に基づいて次の部分データを選択することができる。
【発明の効果】
【００２６】
本発明によれば、データ抽出装置は、複数のエレメントを含むセンサー（例えば、光の変化などのようなイベントに基づいたビジョンセンサー等）でイベントが発生したエレメントの位置を速やかに検索して、ディレイ無しで各イベントに対応するデータを抽出することができる。従って、向上した性能を有するデータ抽出装置及び方法が提供される。
【図面の簡単な説明】
【００２７】
【図１】一実施形態に係るデータ抽出装置の構成図である。
【図２】一実施形態に係るデータ抽出技法を活用するデータ抽出装置を説明する図面である。
【図３】一実施形態に係るデータ抽出技法を活用するデータ抽出装置を説明する図面である。
【図４】一実施形態に係るデータ抽出装置の詳細な構成を示したブロック図である。
【図５】一実施形態に係る出力部の構成を示したブロック図である。
【図６】一実施形態に係るデータの例示を示した図面である。
【図７】一実施形態に係るデータ抽出方法を示したフローチャートである。
【図８】一実施形態に係るデータ抽出方法を示したフローチャートである。
【図９】一実施形態に係るデータ抽出方法を示したフローチャートである。
【図１０】一実施形態に係るデータ抽出方法を示したフローチャートである。
【図１１】他の一実施形態に係るグループに基づいたデータ抽出装置の構成を示したブロック図である。
【発明を実施するための形態】
【００２８】
以下、実施形態を添付された図面を参照して詳細に説明する。しかし、特許出願の範囲がこのような実施形態によって制限されるか、或いは、限定されることではない。各図面に提示された同一の参照符号は同一の部材を示す。
【００２９】
下に説明する実施形態には多様な変更が行われ得る。下に説明する実施形態は、実施形態ついて限定しようとすることはなく、これらに対するすべての変更、均等物乃至代替物を含むものと理解されるべきである。
【００３０】
実施形態で使用した用語は、単なる特定の実施形態を説明するために使用されたものであって、実施形態を限定しようとする意図ではない。単数の表現は文脈上で明確に異なるように表現されない限り、複数の表現を含む。本明細書で、“含む”又は“有する”等の用語は明細書上に記載された特徴、数字、段階、動作、構成要素、部品、又は、これらを組合せたものが存在することを指定しようとするものであり、１つ又はそれ以上の他の特徴や数字、段階、動作、構成要素、部品、又はこれらを組合せたものの存在又は付加可能性を予め排除しないものと理解されなければならない。
【００３１】
異なりに定義されない限り、技術的であるか、或いは科学的な用語を含んでここで使用されるすべての用語は実施形態が属する技術分野で通常の知識を有する者によって一般的に理解されるものと同一の意味を有する。一般的に使用される事前に定義されているような用語は関連技術の文脈の上に有する意味と一致する意味を有するものと解釈されなければならず、本出願で明確に定義しない限り、理想的であるか、或いは、過度に形式的な意味として解釈されない。
【００３２】
また、添付図面を参照して説明することにおいて、図面符号に関わらず同一の構成要素は同一の参照符号を付し、これに対して重複する説明は省略する。実施形態を説明することにおいて、関連した公知技術に対する具体的な説明が実施形態の要旨を不必要に曖昧にするものと判断される場合、その詳細な説明を省略する。
【００３３】
複数のエレメントを含むセンサーにおいて、アナログドメインで複雑なトリ構造を通じて仲裁（ａｒｂｉｔｒａｔｉｏｎ）に基づいて出力データを生成する場合、入力データのビットが多くなれば、トリのデプス（ｄｅｐｔｈ）が大きくなるにつれて、処理する時間が増加し、センサーのサイズ（ｓｉｚｅ）も大きくなる。該当センサーに対して、デジタルドメインで入力データのすべてのビットを特定値に従って選択することができる複雑な回路（例えば、特定ビットのみを選択するＭＵＸ（ｍｕｌｔｉｐｌｅｘｅｒ）のような回路がシフトレジスター（ｓｈｉｆｔ  ｒｅｇｉｓｔｅｒ）に追加されながら、入力データのビットが多くなれば、サイズが大きくなり、１つのクロックサイクル（ｃｌｏｃｋ  ｃｙｃｌｅ）として具現化が難しくなる。
【００３４】
下記では、ディレイを最少化しながら、データを抽出する装置に対して説明する。
【００３５】
図１は、一実施形態に係るデータ抽出装置の構成図である。
【００３６】
データ抽出装置１００は、入力データ（ｉｎｐｕｔ  ｄａｔａ）（図１でＸで図示される）から対象値（ｔａｒｇｅｔ  ｖａｌｕｅ）に該当するビット（ｂｉｔ、ｂｉｎａｒｙ  ｄｉｇｉｔ）を抽出できる装置である。一実施形態に係るデータ抽出装置１００は、データ受信部（ｄａｔａ  ｒｅｃｅｉｖｅｒ）１１０、補数生成部（ｃｏｍｐｌｅｍｅｎｔ  ｇｅｎｅｒａｔｏｒ）１２０、及び、ビット位置抽出部（ｂｉｔ  ｐｏｓｉｔｉｏｎ  ｅｘｔｒａｃｔｏｒ）１３０を含む。
【００３７】
データ受信部１１０は、入力データ（ｉｎｐｕｔ  ｄａｔａ）を受信する。入力データは、ビットのシーケンスからなされたデータを示すことができる。例えば、入力データは０から２Ｎの間の値を有することができ、入力データの長さ（ｌｅｎｇｔｈ）はＮ（例えば、Ｎは１以上の整数）である。入力データで各ビット位置ｉ（例えば、ｉは０からＮ−１の間の整数）の二進値（ｂｉｎａｒｙ  ｖａｌｕｅ）は０又は１であり、ｉ番目のビット位置の二進値が１であれば、該当入力データは２ｉを含む。入力データで最右側（ｒｉｇｈｔｍｏｓｔ）のビット位置はＬＳＢ（Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）を示し、最左側（ｌｅｆｔｍｏｓｔ）のビット位置はＭＳＢ（Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）を示す。入力データは下記の図３でより詳細に説明する。
【００３８】
補数生成部１２０は入力データの補数（ｃｏｍｐｌｅｍｅｎｔ）（図１で−Ｘで図示される）を生成する。本明細書において、補数は、特別に１の補数（ｏｎｅ’ｓ  ｃｏｍｐｌｅｍｅｎｔ）であると明示されない限り、二進法上２の補数（ｔｗｏ’ｓ  ｃｏｍｐｌｅｍｅｎｔ）を示し、負数を示す。入力データがＮビットである場合、入力データの２の補数は、２Ｎに対する補数を示す。例えば、入力データに対する２の補数は、２Ｎから入力データの値を減算（ｓｕｂｔｒａｃｔ）した結果として、入力データの二進形態で０と１の二進値を反転（ｉｎｖｅｒｔ）した後、１を加えた値と同一である。例えば、入力データの二進形態の値が“１１１０”であれば、該当入力データの２の補数（以下、補数と称する）は“００１０”である。
【００３９】
ビット位置抽出部１３０は、入力データ及び補数に基づいて、入力データから対象値（ｔａｒｇｅｔ  ｖａｌｕｅ）のビット位置（ｂｉｔ  ｐｏｓｉｔｉｏｎ）（図１でＹで図示される）を抽出する。対象値は入力データで抽出されなければならない値又は抽出されることを望む（ｄｅｓｉｒｅｄ）値を示す。対象値のビット位置は入力データで対象値が存在するＬＳＢを基準にする位置を示す。例えば、抽出されなければならない対象値が１であり、入力データの二進形態の値が“１１１０”であれば、ビット位置はＬＳＢから１番目である（ＬＳＢは最右側のビット位置として０番目であると示す）。
【００４０】
一実施形態に係るデータ抽出装置１００は、複数のエレメントを含むセンサー（例えば、光の変化等のようなイベントに基づいたビジョンセンサー等）でイベントが発生されたエレメントの位置を速やかに検索して、ディレイ無しで各イベントに対応するデータを抽出することができる。下記でデータ抽出装置１００の構成及び動作を詳細に説明する。
【００４１】
図２及び図３は、一実施形態に係るデータ抽出技法を活用するデータ抽出装置を説明する図面である。
【００４２】
図２は、データ変換部２４０をさらに含むデータ抽出装置２００を図示する。一実施形態に係るデータ抽出装置２００は入力データから対象値が存在するビット位置を順次的に抽出することができる。
【００４３】
データ受信部１１０は、入力データ（図２でＸで図示される）を受信して補数生成部１２０、ビット位置抽出部１３０、及び、データ変換部２４０に伝達する。また、データ受信部１１０は、データ変換部２４０によって変換された入力データ（図２でＸ’で図示される）をデータ変換部２４０から受信して、補数生成部１２０、ビット位置抽出部１３０、及び、データ変換部２４０に伝達する。
【００４４】
一実施形態によれば、データ変換部２４０によって変換された入力データＸ’が、抽出が完了したビット位置の値が初期化されたデータとして、データ受信部１１０は、変換された入力データＸ’を補数生成部１２０、ビット位置抽出部１３０、及び、データ変換部２４０に伝達することによって、データ抽出装置２００が入力データから対象値が存在するビット位置を順次的に抽出できるようにループ（ｌｏｏｐ）を形成することができる。例えば、入力データが最初に受信された場合、データ受信部１１０は、該当入力データをそのまま伝達し、その後に入力データから対象値が存在するすべてのビット位置が抽出される時まで順次的に初期化される変換された入力データを受信して伝達することができる。
【００４５】
補数生成部１２０は、データ受信部１１０から伝達された入力データＸ又は変換された入力データＸ’の補数を生成する。例えば、補数生成部１２０は、入力データＸが伝達された場合、入力データＸの補数−Ｘを生成し、変換された入力データＸ’が伝達された場合、変換された入力データＸ’の補数−Ｘ’を生成する。具体的に、補数生成部１２０は入力データＸ又は変換された入力データＸ’の各ビットを反転（例えば、任意のビット位置の値が０であれば、１に変更し、又は、任意のビット位置の値が１であれば、０に変更）させた後、１を付加する。補数生成部１２０の具体的な動作は下記の図５で詳細に説明する。
【００４６】
ビット位置抽出部１３０は、下記の数式（１）に従がうデータ抽出技法を利用して、入力データＸ（又は変換された入力データＸ’）及び該当入力データの補数−Ｘ（又は変換された入力データの補数−Ｘ’）に基づいて、対象値が存在するビット位置を抽出する。
【００４７】
例えば、図３に図示されたように、入力データＸはＸ［Ｎ−１］、Ｘ［Ｎ−２］、Ｘ［Ｎ−３］、Ｘ［Ｎ−４］、…、Ｘ［３］、Ｘ［２］、Ｘ［１］、Ｘ［０］のＮ個のビットのシーケンスを含むものと仮定する。ここで、Ｘ［ｉ］（例えば、ｉは０以上Ｎ−１以下の整数）は、ＬＳＢからｉ番目のビット位置の二進値を示す。図３でＸ［Ｎ−５］乃至Ｘ［０］の二進値は０を仮定し、Ｘ［Ｎ−４］がＬＳＢから最初に１であるビットであることを仮定する。ビット位置Ｙは入力データＸで対象値（例えば、図３では１）が現れる最右側のビットのみを維持し、残るビットは非対象値（ｎｏｎ−ｔａｒｇｅｔ  ｖａｌｕｅ）（例えば、図３では０）に変更されたデータを示す。
【００４８】
【数１】
2017151986.tif 000003
上述した数式（１）で、Ｘは入力データ、−Ｘは入力データの補数、Ｙは最右側の対象値が存在するビット位置、＆はビット間論理積（ｂｉｔｗｉｓｅ  ＡＮＤ）演算を示す。数式（１）のように、入力データＸ及び入力データの補数−Ｘに対してビット間論理積が適用されれば、その結果であるビット位置Ｙは常に入力データＸで最右側の対象値のみを維持しながら、残りは非対象値に変更された値を示す。例えば、図３に図示されたように、ビット位置ＹはＬＳＢからＭＳＢの方向に入力データＸのビットの中でＬＳＢから第１番目の‘１’があるビット（例えば、最右側対象値が存在するビット）のみが‘１’になり、残りは‘０’になる。従って、上述した数式（１）に基づいて、データ抽出装置２００は、常にＬＳＢから第１番目の対象値（例えば、‘１’）が存在するビット位置の値が分かる。
【００４９】
例えば、図３で上述したように、ＬＳＢからＮ−４番目のビットであるＸ［Ｎ−４］が最右側の対象値が存在するビット位置に仮定されたので、Ｘ［Ｎ−５］乃至Ｘ［０］のビット位置の値は‘０’であると仮定される。入力データＸと入力データの補数−Ｘは、互いに加算（ａｄｄｉｔｉｏｎ）が適用されれば、その結果が０にならなければならない補数関係にある。補数−Ｘの−Ｘ［０］乃至−Ｘ［Ｎ−５］は‘０’であり、−Ｘ［Ｎ−４］は入力データＸのＸ［Ｎ−４］と同一の値を有するので、常にキャリー（ｃａｒｒｙ）が発生し得る。このように、補数−Ｘの−Ｘ［Ｎ−３］乃至−Ｘ［Ｎ−１］は、入力データＸのＸ［Ｎ−３］乃至Ｘ［Ｎ−１］に対する１の補数（１’ｓ  ｃｏｍｐｌｅｍｅｎｔ）になり、Ｘ［Ｎ−４］＋−Ｘ［Ｎ−４］を通じて発生したキャリー（ｃａｒｒｙ）が２の補数のための‘１’である。
【００５０】
このような入力データＸと入力データの補数−Ｘとの関係は、ＬＳＢからＭＳＢ方向に第１番目の‘１’があるビットまでは同様に‘０’の値を有し、第１番目の‘１’がビットは同様に‘１’を有し、残る上位ビットは互いに反転（ｉｎｖｅｒｓｉｏｎ）された値を有する特性がある。従って、このような特性によって、上述した数式（１）に従って入力データＸ及び入力データの補数−Ｘに対して論理積（“ＡＮＤ”）演算が適用されて算出されたビット位置Ｙは最右側に存在する１（例えば、ＬＳＢから最も近い１）を示すことができる。ビット位置ＹはＬＳＢから第１番目の‘１’があるビットの十進数値として、ＬＳＢから第１番目の‘１’があるビットがＬＳＢからｍ番目である場合、抽出されたビット位置Ｙは２ｍ（ここで、ｍは０以上Ｎ−１以下の整数）である。図３の例示で、ビット位置Ｙは２Ｎ−４の値を示す。
【００５１】
一実施形態に係るデータ抽出装置２００は、入力データＸが複数のビットで構成されており、その中で対象値（例えば、０又は１）を有するビットをディレイ無しで出力するか、或いは識別するために、上述したように対象値が存在するビット位置Ｙをディレイ無しで抽出することによって、該当ビット位置Ｙに存在するビットをビット位置と共に出力することができる。
【００５２】
データ変換部２４０は、入力データＸから対象値のビット位置Ｙを抽出した後、抽出されたビット位置の値を初期化して入力データを変換する。例えば、データ変換部２４０は下記の数式（２）によって変換された入力データＸ’を生成する。
【００５３】
【数２】
2017151986.tif 000004
上述した数式（２）でＸは入力データ、Ｙはビット位置、Ｘ’は変換された入力データ、ｘｏｒはビット間排他的論理和（ｂｉｔｗｉｓｅ  ＸＯＲ）を示す。数式（２）で変換された入力データＸ’は、数式（１）で算出されたビット位置Ｙと入力データＸとの間の排他的論理和の結果として、入力データＸでＬＳＢから最右側の１が存在するビット位置の値が０になる。上述したように、ＬＳＢから第１番目の‘１’があるビットのみが‘０’に変更され、変換された入力データＸ’の残る上位ビットは入力データＸの上位ビットと同一であるので、データ抽出装置２００は、数式（２）を通じて数式（１）によって抽出された第１番目の‘１’を入力データＸから除外する。
【００５４】
一実施形態によれば、データ変換部２４０は、数式（２）によって変換された入力データＸ’をデータ受信部１１０にフィードバックすることができる。データ受信部１１０が変換された入力データＸ’を補数生成部１２０、ビット位置抽出部１３０、及び、データ変換部２４０に提供することによって、データ抽出装置２００は変換された入力データＸ’を次の入力データとして使用する。データ抽出装置２００は、変換された入力データＸ’に対してビット位置を抽出するための一連の過程を繰り返すことができ、最右側の１が存在するビット位置をディレイ無しで順次的に抽出することができる。データ抽出装置２００は、変換された入力データＸ’が０になる時まで（例えば、最初入力データＸのすべての‘１’の値が全部出力される時まで）ビット位置Ｙを抽出する一連の過程を繰り返すことによって、‘１’を有するビットのビット位置に対する十進数値をディレイ無しで連続的に出力することができる。
【００５５】
図４は、一実施形態に係るデータ抽出装置の詳細な構成を示したブロック図である。
【００５６】
一実施形態に係るデータ抽出装置４００のゲートレベル（ｇａｔｅ  ｌｅｖｅｌ）の回路図が図４のように図示される。
【００５７】
先ず、データ受信部１１０は、ＭＵＸ（ｍｕｌｔｉｐｌｅｘｅｒ）で具現化され得る。一実施形態によれば、データ受信部１１０は制御部４７０から伝達される印加信号ＥＮによってデータＤｉｎ［Ｎ−１：０］及び変換された入力データＸ’の中で１つを補数生成部１２０、ビット位置抽出部１３０、及びデータ変換部２４０に伝達する。例えば、制御部４７０で印加信号ＥＮとして１が伝達される場合、ＭＵＸはデータＤｉｎを伝達し、印加信号として０が伝達される場合、ＭＵＸは変換された入力データＸ’を伝達する。データＤｉｎが最初に受信された場合、データ受信部１１０はデータＤｉｎを入力データＸとして伝達し、１度ビット位置Ｙを抽出した後からデータＤｉｎ内で対象値が存在するすべてのビット位置を抽出する時までは変換された入力データＸ’を入力データとして伝達する。
【００５８】
補数生成部１２０は、入力データＸに対してビット間ＮＯＴ（ｂｉｔｗｉｓｅ  ＮＯＴ）演算を遂行するＮＯＴゲート（ＮＯＴ  ｇａｔｅ）４２１、及びＮＯＴ演算（ＮＯＴ  ｏｐｅｒａｔｉｏｎ）が遂行された入力データに対して１の値を付加（ａｄｄ）する加算器（ａｄｄｅｒ）４２２を含む。補数生成部１２０は、上述したＮＯＴ演算及び１の付加に基づいて入力データＸに対する２の補数−Ｘを生成する。
【００５９】
ビット位置抽出部１３０は、入力データＸ及び補数−Ｘに対してビット間論理積（ｂｉｔｗｉｓｅ  ＡＮＤ）演算を遂行する論理積ゲート（ＡＮＤ  ｇａｔｅ）４３１を含む。ビット位置抽出部１３０は入力データＸ及び補数−Ｘにビット間論理積を適用してビット位置Ｙを生成する。ここで、ビット位置抽出部１３０は、上述したように入力データＸで対象値が示す最右側（ｒｉｇｈｔｍｏｓｔ）のビット位置Ｙを抽出する。
【００６０】
データ変換部２４０は、入力データＸ及び抽出されたビット位置Ｙに対してビット間（ｂｉｔｗｉｓｅ）排他的論理和（ＸＯＲ、ｅｘｃｌｕｓｉｖｅ  ＯＲ）演算を遂行する排他的論理和ゲート（ＸＯＲ  ｇａｔｅ）４４１を含む。データ変換部２４０は、入力データＸ及びビット位置Ｙに対してビット間排他的論理和を適用することによって、変換された入力データＸ’を生成する。データ変換部２４０は、フリップフロップ（Ｆ／Ｆ、ｆｌｉｐ  ｆｌｏｐ）４４２をさらに含み、変換された入力データＸ’をフリップフロップ４４２を利用して次のクロックサイクルでデータ受信部１１０に伝達する。
【００６１】
また、データ抽出装置４００は、出力部４５０、終了決定部４６０、及び、制御部４７０等をさらに含む。
【００６２】
出力部４５０は、抽出されたビット位置Ｙを出力する。一実施形態によれば、出力部４５０は、ビット位置を二進ログ（ｂｉｎａｒｙ  ｌｏｇ）値の形態（Ｄｏｕｔ［ｌｏｇ２（Ｎ−１）：０］）に出力する。例えば、ＬＳＢからｍ番目のビットが第１番目の対象値が現れるビットである場合、抽出されたビット位置Ｙは２ｍの値を有し、出力部４５０は該当ビット位置Ｙの値に対する二進ログ値であるｍとして出力する。また、ｍはＤｏｕｔ［ｌｏｇ２（Ｎ−１）］、Ｄｏｕｔ［ｌｏｇ２（Ｎ−１）−１］、…、Ｄｏｕｔ［２］、Ｄｏｕｔ［１］、Ｄｏｕｔ［０］のように、ｌｏｇ２（Ｎ−１）＋１個のビットとして出力される。出力部４５０はＬＳＢからの対象値のビット位置Ｙに対して、クロックサイクル毎に１回ずつ該当ビット位置の２の累乗値を出力する。
【００６３】
終了決定部（ｔｅｒｍｉｎａｔｉｏｎ  ｄｅｔｅｒｍｉｎｅｒ）４６０は入力データＸから対象値が存在するすべてのビット位置が抽出されたものと判断された場合に応答して、終了信号Ｓｃｔｒｌを生成する。一実施形態によれば、終了決定部４６０は、ビット間論理和演算を遂行する論理和ゲート（ＯＲ  ｇａｔｅ）４６１及び論理和ゲートの出力を反転するＮＯＴゲート４６２を含む。例えば、入力データＸからすべての１が抽出された場合、データ変換部２４０の出力はすべてのビットが０になり、変換された入力データＸ’のすべてのビットが０であれば、終了決定部４６０に含まれた論理和ゲート４６１の出力も０になって、結果的にＮＯＴゲート４６２の出力が１になる。終了決定部４６０は、上述したことによって生成された終了信号Ｓｃｔｒｌを制御部４７０に伝達する。
【００６４】
制御部４７０は、データ抽出装置４００の全般的な動作を制御するモジュールとして、終了決定部４６０で生成された終了信号ＳｃｔｒｌによってデータＤｉｎからすべての対象値が抽出されたか否かを判断して印加信号ＥＮを生成し、データ抽出装置４００内にクロックサイクルｃｌｋを供給する。一実施形態によれば、制御部４７０は、データＤｉｎが受信された時から最初１サイクルの間のみに印加信号ＥＮを印加して、最初１回だけデータＤｉｎをデータ抽出装置４００の入力として使用されるようにデータ受信部１１０を制御し、次のサイクルから終了信号Ｓｃｔｒｌが‘１’になる時まではフリップフロップ４４２の出力である変換された入力データＸ’が入力データとして使用するようにデータ受信部１１０を制御する。
【００６５】
上述したデータ受信部１１０、補数生成部１２０、ビット位置抽出部１３０、データ変換部２４０、出力部４５０、終了決定部４６０、制御部４７０は、多様な論理ゲート（ｌｏｇｉｃａｌ  ｇａｔｅ）、回路素子（ｃｉｒｃｕｉｔｒｙ  ｅｌｅｍｅｎｔ）、電子的素子（ｅｌｅｃｔｒｉｃａｌ  ｅｌｅｍｅｎｔ）、アナログ素子（ａｎａｌｏｇ  ｅｌｅｍｅｎｔ）、及び、デジタル素子（ｄｉｇｉｔａｌ  ｅｌｅｍｅｎｔ）等によって具現化され得る。また、上述したＮＯＴゲート、論理和ゲート、排他的論理和ゲート、論理積ゲート、及び、加算器等は多様な回路素子によって具現化され得る。
【００６６】
図５は、一実施形態に係る出力部の構成を示したブロック図である。
【００６７】
出力部４５０は、１から２Ｎ−１の間の値を有するビット位置Ｙを二進ログの形態（ｌｏｇ２Ｙ）に出力し、ビット位置Ｙの二進ログ値（ｌｏｇ２Ｙ）は０からＮ−１の間の値を有する。従って、出力部４５０は、ＬＳＢからＭＳＢ方向に第１番目の対象値が存在するビットの十進数値であるビット位置Ｙを二進ログの形態に出力する。ここで、二進ログ値（ｌｏｇ２Ｙ）は、対象値が存在するビットがＬＳＢから何番目であるかを示す。
【００６８】
一実施形態によれば、ビット位置Ｙを二進ログ値（ｌｏｇ２Ｙ）に変換するためのログ関数は、図５のように論理和ゲート（ＯＲ  ｇａｔｅ）５５０で具現化され得る。図５に図示されたように、出力部４５０の論理和ゲート５５０はビット位置ＹをＹ［Ｎ−１］乃至Ｙ［０］までビット単位に受信して、二進ログ値（ｌｏｇ２Ｙ）をＤｏｕｔ［ｌｏｇ２（Ｎ−１）］乃至Ｄｏｕｔ［０］までビット単位に出力することができる。
【００６９】
例えば、図５に図示されたように、出力部４５０は第１論理和ゲート５５１、第２論理和ゲート５５２、第３論理和ゲート５５３、及び、第４論理和ゲート５５４等で具現化され得る。但し、論理和ゲートのノード連結方式及び論理和ゲートの個数を図示されたことに限定することではない。
【００７０】
第１論理和ゲート５５１は、ビット位置Ｙの２ｋ−１番目のビットを入力として該当ビット位置Ｙを二進ログ値で表現した時、０番目のビット（Ｄｏｕｔ［０］）を出力する。例えば、入力データＸが“０１１００”である場合、第１番目のビット位置Ｙは“００１００”になり、これは十進数の上に２２＝４になり、Ｙ［４］＝０、Ｙ［３］＝０、Ｙ［２］＝１、Ｙ［１］＝０、Ｙ［０］＝０で示すことができる。従って、該当例示において、Ｙ［３］、Ｙ［１］は０であるので、Ｄｏｕｔ［０］＝０として出力される。
【００７１】
第２論理和ゲート５５２は、ビット位置Ｙの２、３番目、６、７番目、１０、１１番目、１４、１５番目等のビットを入力として、該当ビット位置Ｙを二進ログ値で表現した時、１番目のビット（Ｄｏｕｔ［１］）を出力する。例えば、上述した例示では、Ｙ［２］＝１であるので、Ｄｏｕｔ［１］＝１として出力される。
【００７２】
第３論理和ゲート５５３は、ビット位置Ｙの４、５、６、７番目、１２、１３、１４、１５番目等のビットを入力として、該当ビット位置Ｙを二進ログ値で表現した時、２番目のビット（Ｄｏｕｔ［２］）を出力する。例えば、上述した例示では、Ｙ［４］＝０であるので、Ｄｏｕｔ［２］＝０として出力される。
【００７３】
第４論理和ゲート５５４は、ビット位置Ｙの８、９、１０、１１、１２、１３、１４、１５番目、２４、２５、２６、２７、２８、２９、３０、３１番目等のビットを入力として、該当ビット位置Ｙを二進ログ値で表現した時、３番目のビット（Ｄｏｕｔ［３］）を出力する。但し、上述した例示は第４論理和ゲート５５４と関係ないので、説明を省略する。
【００７４】
上述した例示では、二進ログ値ＤｏｕｔはＤｏｕｔ［１］＝１であるので、２１＝２として、該当二進ログ値Ｄｏｕｔは対象位置が存在するビットの位置がＬＳＢから２番目であることを指示する。
【００７５】
このように論理和ゲートの数によって表現され得る二進ログ値の範囲を増加することができる。二進ログ値のｗ番目のビットは、ビット位置Ｙの
【００７６】
【数３】
2017151986.tif 000005
番目のビットを入力とする論理和ゲートの出力である（ここで、ｗは０以上の整数、ｕは０以上の整数）。ここで、％は残る演算として、例えば１０％４＝２のように計算される。
【００７７】
【数４】
2017151986.tif 000006
は、フロア（ｆｌｏｏｒ）演算としてｘより小さいか、或いは同一の整数を示し（ここで、ｘは実数）、例えば、
【００７８】
【数５】
2017151986.tif 000007
等のように計算される。論理和ゲート５５０の数が図５に図示されたものに限定されることではなく、出力されなければならない二進ログ値の範囲によって変更され得るものである。
【００７９】
図６は、一実施形態に係るデータの例示を示した図面である。図６は、図４に図示されたデータ抽出装置でのデータ値の変更をクロックサイクル単位に説明する図面である。
【００８０】
例えば、データＤｉｎとして“１１００１０”をデータ受信部１１０が受信する。印加信号ＥＮによって、データ受信部１１０は、入力データＸとして“１１００１０”を補数生成部１２０、ビット位置抽出部１３０、及び、データ変換部２４０に伝達する。ビット位置抽出部１３０は、第１番目のクロックサイクルで最右側（図６ではＬＳＢから１番目）に存在する１を抽出する。該当クロックサイクルでデータ変換部２４０は、変換された入力データＸ’の値を“１１００００”であると決定し、変換された入力データＸ’を次のクロックサイクルに入力受信部１１０に伝達する。
【００８１】
２番目のクロックサイクルで、入力受信部１１０は、印加信号ＥＮが０であるので、変換された入力データＸ’を他のモジュールに伝達する。ビット位置抽出部１３０は、２番目のクロックサイクルで変換された入力データＸ’の最右側（図６では４番目）に存在する１を抽出する。該当クロックサイクルでデータ変換部２４０は、変換された入力データＸ’の値を“１０００００”であると決定し、変換された入力データＸ’を次のクロックサイクルに入力受信部１１０に伝達する。
【００８２】
３番目のクロックサイクルで、入力受信部１１０は、印加信号ＥＮが０であるので、変換された入力データＸ’の値である“１０００００”を他のモジュールに伝達する。ビット位置抽出部１３０は、３番目のクロックサイクルで変換された入力データＸ’の最右側（図６で５番目）に存在する１を抽出する。該当クロックサイクルでデータ変換部２４０は、変換された入力データＸ’の値を“００００００”であると決定し、終了決定部４６０はすべてのビットの値が０であるので、終了信号Ｓｃｔｒｌの値を１であると決定する。制御部４７０は終了信号ＳｃｔｒｌによってデータＤｉｎに対する抽出を完了したものと判断する。
【００８３】
すべてのビットを検索する場合、６クロックサイクルが必要とされるが、上述したように、一実施形態に係るデータ抽出装置４００は合わせて６ビットの入力データに対して３クロックサイクルのみですべての対象値を抽出することができる。但し、上述した図６の過程は単なる例示的なものであって、設計によって細部事項は変更され得るものである。
【００８４】
図７乃至図１０は、一実施形態に係るデータ抽出方法を示したフローチャートである。
【００８５】
図７乃至図９は、データ抽出装置がデータを抽出する方法を示したフローチャートである。
【００８６】
先ず、段階（７１０）で、データ受信部は、入力データを受信する。図１乃至図６で上述したように、データ受信部は、現在クロックサイクルで変換された入力データを次のクロックサイクルの入力データとして使用する。例えば、図９に図示されたように、データ受信部は、入力データとして“１１１０”を受信して伝達する。
【００８７】
そして、段階（７２０）で、補数生成部は、入力データの補数を生成する。図１乃至図６で上述したように、補数生成部は、入力データのビット間演算を通じて入力データの補数を生成する。例えば、図９の段階（９２０）のように、補数生成部は、２の補数を生成し、入力データである“１１１０”に対する補数は“００１０”である。
【００８８】
続いて段階（７３０）で、ビット位置抽出部は、入力データ及び補数に基づいて、入力データから対象値のビット位置を抽出する。図１乃至図６で上述したように、ビット位置抽出部は、入力データ及び補数に基づいたビット間演算を通じてビット位置を抽出する。ビット位置抽出部は入力データで対象値が現れる最右側（ｒｉｇｈｔｍｏｓｔ）のビット位置を抽出する。例えば、図９の段階（９３０）のように、ビット位置抽出部は、入力データ及び補数に対して論理積演算を遂行し、入力データである“１１１０”及び補数である“００１０”に対する論理積結果は“００１０”である。
【００８９】
そして、図８に図示されたように、段階（８４０）で、出力部は、ビット位置を出力する。出力部は、ビット位置を二進ログ値の形態に出力するが、これに限定することではない。
【００９０】
続いて段階（８５０）で、データ変換部は、入力データから対象値のビット位置を抽出した後、抽出されたビット位置の値を初期化して入力データを変換する。例えば、データ変換部は、図９の段階（９５０）で入力データ及びビット位置に対して排他的論理和演算を遂行し、入力データである“１１１０”及びビット位置である“００１０”に対する排他的論理和演算の結果は“１１００”である。
【００９１】
そして、段階（８６０）で、終了決定部は、すべてのビット位置が抽出されたか否かを判断する。例えば、図９の段階（９６０）のように、終了決定部は、すべてのビットが０であるか否かを判断する。ここで、終了決定部は、入力データから対象値が存在するすべてのビット位置が抽出されたものと判断された場合に応答して、終了信号を生成し、データ抽出装置は動作を終了する。すべてのビット位置が抽出されない場合、データ抽出装置は、段階（８５０）で変換された入力データ（図９で“１１００”で図示される）を段階（７２０）に戻って補数を生成するのに使用する。一実施形態によれば、データ抽出装置は、すべてのビット位置が抽出される時まで、入力データから対象値が存在するビット位置を順次的に抽出することができる。図９の段階（９６０）で図示されたように、すべてのビットが０ではない場合、変換された入力データ（図９では“１１００”であると例示される）は、段階（７２０、７３０、８５０）にフィードバック（ｆｅｅｄｂａｃｋ）されて使用される。
【００９２】
例えば、図７及び図８の段階（７２０）で、補数生成部は、段階（８６０）ですべてのビット位置が抽出されないので、次のクロックサイクルで変換された入力データを受信した場合、変換された入力データの補数を生成する。以後、段階（７３０）では、ビット位置抽出部が、変換された入力データの補数を利用して、変換された入力データから対象値のビット位置を抽出する。
【００９３】
図１０は、対象値が０であると設定された場合のデータ抽出方法を示したフローチャートである。
【００９４】
段階（１０１１）では、データ受信部が、入力データに対してＮＯＴ演算を遂行する。一実施形態によれば、データ受信部は、入力データに対してビット間ＮＯＴ演算（ｂｉｔｗｉｓｅ  ＮＯＴ  ｏｐｅｒａｔｉｏｎ）を遂行し、ＮＯＴ演算が遂行された入力データを補数生成部及びビット位置抽出部の中で少なくとも１つに伝達する。例えば、図１０に図示されたように、入力データとして“０００１”が受信された場合、データ受信部は、入力データを反転した“１１１０”を段階（８２０、８３０、８５０）に提供する。
【００９５】
上述したように、入力データに対してＮＯＴ演算を追加することによって、データ抽出装置は、入力データで０が存在するビット位置を順次的に抽出する。
【００９６】
図１１は、他の一実施形態に係るグループに基づいたデータ抽出装置の構成を示したブロック図である。
【００９７】
他の一実施形態に係るグループに基づいたデータ抽出装置１１００は、入力データをグループに分類して処理することができる。入力データで２の補数を算出するためには、入力データを反転した値に１を加える加算器が要求されるので、入力データのビットが大きいほど、加算器の大きさが増加され得る。ここで、入力データを特定数のビットにグループ化して、グループ単位に上述した図１乃至図１０に図示されたデータ抽出装置に入力させる。このようなグループに基づいたデータ抽出装置１１００は、具現化に必要であるサイズが減少され得る。
【００９８】
上述したグループに基づいたデータ抽出装置１１００は、情報受信部１１１０、グループ抽出部１１２０、グループ選択部１１３０、データ抽出部１１４０、及び、出力部１１５０を含む。
【００９９】
情報受信部１１１０は、入力データを受信し、該当入力データをグループ単位に分類し、グループ単位の入力データをグループ選択部１１３０に提供する。例えば、情報受信部１１１０は、グループ化部１１１９を含む。
【０１００】
グループ化部１１１９は、入力データを複数のグループに分類してグループデータを生成する。一実施形態によれば、グループ化部１１１９は、入力データに含まれたビットを複数のグループに分類し、該当グループに分類されたビットの中で一つでも‘１’があれば、該当グループのグループ値は１として出力する。例えば、グループ化部１１１９は、入力データをｊ個のビット単位に１つのグループを生成することができ、Ｍ個のグループを生成することができる。Ｍ、ｊは、１以上の整数としてＭ＝Ｎ／ｊである。グループ化部１１１９は、各々のグループに対して、該当グループ内に含まれたｊ個のビットをビット間論理和演算を適用して、一つでも１があれば、該当グループのグループ値を１として決定し、１が１つもなければ、該当グループのグループ値を０として決定する。グループデータはすべてのグループに該当する一連のグループ値のシーケンスを示すデータとして、例えばＭ−１番目のグループ１１１５の値乃至３番目のグループ１１１４の値、２番目のグループ１１１３の値、１番目のグループ１１１２の値、及び０番目のグループ１１１１値の順に構成され得る。
【０１０１】
グループ抽出部１１２０はグループデータから対象グループ値のグループビット位置を抽出する。対象グループ値は一つでも対象値（例えば、１）を有するビットが存在するグループを識別するための値を示す。グループビット位置は一つでも対象値を有するビットが存在するグループを指示する値を示す。グループビット位置の抽出は、図１乃至図１０で上述したビット位置の抽出と類似な過程を通じて遂行される。例えば、合わせて４個のグループに分類されたものと仮定し、３番目のグループ１１１４に１が存在し、２番目のグループ１１１３に１が存在し、１番目のグループ１１１２及び０番目のグループ１１１１には１が存在しない場合、グループデータは“１１００”として示す。グループ抽出部１１２０は、該当グループデータから最右側の対象グループ値（例えば、１）のグループビット位置として“０１００”（例えば、ＬＳＢから２番目であることを指示する）の値を抽出する。例えば、グループ抽出部１１２０は図１乃至図１０で上述したデータ抽出装置と類似に構成される。
【０１０２】
グループ選択部１１３０は、グループビット位置に基づいてグループを選択し、入力データから選択されたグループに対応する部分データを選択する。上述したように、グループデータが“１１００”である例示において、グループ選択部１１３０は、グループビット位置である“０１００”に対応するグループとして２番目のグループ１１１３（図１１においてＧｒｏｕｐ２と図示される）を選択し、入力データから２番目のグループ１１１３に対応するビットを部分データとして選択してデータ抽出部１１４０に伝達する。
【０１０３】
データ抽出部１１４０は、選択されたグループに対応する部分データから対象値のビット位置を順次的に抽出する。例えば、データ抽出部１１４０は、図１乃至図１０で上述したデータ抽出装置と類似に構成され得る。一実施形態によれば、データ抽出部１１４０は部分データから図１乃至図１０で上述したデータ抽出技法を利用して、対象値のビット位置を順次的に抽出して出力部１１５０に提供する。
【０１０４】
出力部１１５０は、データ抽出部１１４０から抽出されたビット位置を出力する。例えば、出力部１１５０は、現在クロックサイクルで選択されたグループ（例えば、グループビット位置）と該当グループ内でのビット位置を共に出力することができる。ここで、ビット位置等を出力部１１５０は、二進ログ形態で出力することもできる。
【０１０５】
以後、グループ抽出部１１２０は、データ抽出部１１４０が部分データから対象値のすべてのビット位置を抽出したものと判断された場合に応答して、グループ対象値の次のグループビット位置を抽出することができる。グループ選択部１１３０は、次のグループビット位置に基づいて次の部分データを選択する。例えば、データ抽出部１１４０は、１つのグループですべての対象値の抽出が完了されれば、グループ抽出部１１２０に終了信号を伝達する。グループ抽出部１１２０は、終了信号に応答して、第１番目の対象グループ値が存在したビットを初期化し、第２番目の対象グループ値が存在するグループビット位置を抽出する。以後に、グループ選択部１１３０が、第２番目のグループビット位置に対応するグループに属する部分データを選択すれば、データ抽出部１１４０は、選択された部分データの１があるビット位置を出力する。
【０１０６】
上述したように、グループに基づいたデータ抽出装置１１００は、すべてのグループの出力が‘０’になる時まで繰り返して、ビット位置を順次的に出力することができる。グループに基づいたデータ抽出装置１１００は、入力データのビット数が多い場合にも、グルーピングを通じて、ディレイが無いシフトレジスターとして動作することができる。
グループに基づいたデータ抽出装置１１００に含まれる情報受信部１１１０、グループ抽出部１１２０、グループ選択部１１３０、データ抽出部１１４０、及び出力部１１５０等は、多様な論理ゲート（ｌｏｇｉｃａｌ  ｇａｔｅ）、回路素子（ｃｉｒｃｕｉｔｒｙ  ｅｌｅｍｅｎｔ）、電子的素子（ｅｌｅｃｔｒｉｃａｌ  ｅｌｅｍｅｎｔ）、アナログ素子（ａｎａｌｏｇ  ｅｌｅｍｅｎｔ）、及び、デジタル素子（ｄｉｇｉｔａｌ  ｅｌｅｍｅｎｔ）等によって具現化され得る。
【０１０７】
以上で説明された装置は、ハードウェア構成要素、ソフトウェア構成要素、及び／又は、ハードウェア構成要素及びソフトウェア構成要素の組合せで具現化され得る。例えば、実施形態で説明された装置及び構成要素は、例えばプロセッサ、コントローラ、ＡＬＵ（ａｒｉｔｈｍｅｔｉｃ  ｌｏｇｉｃ  ｕｎｉｔ）、デジタル信号プロセッサ（ｄｉｇｉｔａｌ  ｓｉｇｎａｌ  ｐｒｏｃｅｓｓｏｒ）、マイクロコンピューター、ＦＰＡ（ｆｉｅｌｄ  ｐｒｏｇｒａｍｍａｂｌｅ  ａｒｒａｙ）、ＰＬＵ（ｐｒｏｇｒａｍｍａｂｌｅ  ｌｏｇｉｃ  ｕｎｉｔ）、マイクロプロセッサ、又は、命令（ｉｎｓｔｒｕｃｔｉｏｎ）を実行し応答することができる他の何らかの装置のように、１つ以上の汎用コンピュータ又は特殊目的コンピュータを利用して具現化され得る。処理装置はオペレーティングシステム（ＯＳ）及びオペレーティングシステム上で遂行される１つ以上のソフトウェアアプリケーションを遂行することができる。また、処理装置は、ソフトウェアの実行に応答して、データを接近、格納、操作、処理及び生成することもできる。理解を容易にするために、処理装置は１つが使用されるものと説明された場合もあるが、該当技術分野で通常の知識を有する者は、処理装置が複数個の処理要素（ｐｒｏｃｅｓｓｉｎｇ  ｅｌｅｍｅｎｔ）及び／又は複数類型の処理要素を含むことができることが分かる。例えば、処理装置は複数個のプロセッサ又は１つのプロセッサ及び１つのコントローラを含むことができる。また、並列プロセッサ（ｐａｒａｌｌｅｌ  ｐｒｏｃｅｓｓｏｒ）のような、他の処理構成（ｐｒｏｃｅｓｓｉｎｇｃｏｎｆｉｇｕｒａｔｉｏｎ）も可能である。
【０１０８】
ソフトウェアは、コンピュータプログラム（ｃｏｍｐｕｔｅｒ  ｐｒｏｇｒａｍ）、コード（ｃｏｄｅ）、命令（ｉｎｓｔｒｕｃｔｉｏｎ）、又はこれらの中で１つ以上の組合せを含むことができ、望み通りに動作するように処理装置を構成するか、独立的又は結合的に（ｃｏｌｌｅｃｔｉｖｅｌｙ）処理装置を命令することができる。ソフトウェア及び／又はデータは、処理装置によって解釈されるか、或いは処理装置に命令又はデータを提供するために、いくつかの類型の機械、構成要素（ｃｏｍｐｏｎｅｎｔ）、物理的装置、仮想装置（ｖｉｒｔｕａｌ  ｅｑｕｉｐｍｅｎｔ）、コンピュータ格納媒体又は装置、又は、伝送される信号波（ｓｉｇｎａｌ  ｗａｖｅ）に永久的又は一時的に具体化（ｅｍｂｏｄｙ）され得る。ソフトウェアは、ネットワークに連結されたコンピュータシステム上に分散されて、分散された方法に格納されるか、或いは実行され得る。ソフトウェア及びデータは、１つ以上のコンピュータ読出し可能記録媒体に格納され得るものである。
【０１０９】
実施形態に係る方法は、多様なコンピュータ手段を通じて遂行され得るプログラム命令形態に具現化されてコンピュータ読出し可能媒体に記録され得る。コンピュータ読出し可能媒体はプログラム命令、データファイル、データ構造等を単独に又は組合せて含むことができる。媒体に記録されるプログラム命令は、実施形態のために特別に設計され、構成されたものであるか、或いは、コンピュータソフトウェア当業者に公知されて使用可能なものであってもよい。コンピュータ読出し可能記録媒体の例としては、ハードディスク、フロッピー（登録商標）ディスク及び磁気テープのような磁気媒体（ｍａｇｎｅｔｉｃ  ｍｅｄｉａ）、ＣＤ−ＲＯＭ、ＤＶＤのような光記録媒体（ｏｐｔｉｃａｌ  ｍｅｄｉａ）、フロプティカルディスク（ｆｌｏｐｔｉｃａｌ  ｄｉｓｋ）のような磁気−光媒体（ｍａｇｎｅｔｏ−ｏｐｔｉｃａｌ  ｍｅｄｉａ）、及びＲＯＭ（ＲＯＭ）、ＲＡＭ（ＲＡＭ）、フラッシュメモリ等のようなプログラム命令を格納し、遂行するように特別に構成されたハードウェア装置が含まれる。プログラム命令の例としては、コンパイラによって生成されたコードのような機械コードのみならず、インタプリタ等を使用してコンピュータによって実行され得る高級言語コードを含む。上述されたハードウェア装置は実施形態の動作を遂行するために１つ以上のソフトウェアモジュールとして作動するように構成され得るものであり、その逆も同様である。
【０１１０】
以上のように、実施形態がたとえ限定された図面によって説明されていても、該当技術分野で通常の知識を有する者であれば、上述したことに基づいて多様な技術的な修正及び変形を適用することができる。例えば、説明された技術が説明された方法と異なる順序に遂行されるか、及び／又は、説明されたシステム、構造、装置、回路等の構成要素が説明された方法と異なる形態に結合又は組合されるか、他の構成要素又は均等物によって置き換えるか、或いは、置換されても適切な結果が達成され得るものである。
【０１１１】
従って、他の具現化、他の実施形態、及び、特許請求の範囲と均等なものも後述する特許請求範囲の範囲に属する。
【符号の説明】
【０１１２】
１１０  データ受信部
１２０  補数生成部
１３０  データ抽出部
１００  データ抽出装置
【図１】
2017151986.tif 000008
【図２】
2017151986.tif 000009
【図３】
2017151986.tif 000010
【図４】
2017151986.tif 000011
【図５】
2017151986.tif 000012
【図６】
2017151986.tif 000013
【図７】
2017151986.tif 000014
【図８】
2017151986.tif 000015
【図９】
2017151986.tif 000016
【図１０】
2017151986.tif 000017
【図１１】
2017151986.tif 000018