(57)【要約】ノイズが混入した無線の存在において無線周波数識別（RFID）タグ（１１２）を読み込んだり、書き込んだりするための方法を提供する。この方法に基づき、２進木データ構造は唯一の識別番号と関連するそれぞれの複数のＲＦＩＤタグ（１０２ａ−１０２ｇ）を識別するために使われる。識別タグの読み取り器（１０４）と１つ以上のＲＦＩＤタグ（１０２ａ−１０２ｇ）相互間での通信の間、タグの読み取り器（１０４）は、唯一のＩＤ番号をもつ１つのタグが孤立化および検出されるまで通信からタグを除去しながら、二進木を横断する。２進木が横断されるにつれて、木の中にあるそれぞれのノードに関連するカウンタ（２６０および２６５）はタグの一致に基づいて増加され、その結果、時間を経て、タグの集められる枝におけるノードと関連するカウンタは高い値を持つ傾向があり、集められない木の枝におけるノードに関連するカウンタは低い値をもつ傾向がある。
2006503502.tif 000002
【特許請求の範囲】
【請求項１】
複数の無線周波数識別（ＲＦＩＤ）タグを用いた通信方法であって、
（ａ）複数のＲＦＩＤタグから一連のビットを受け取り、２進木において対応するノードでの該一連のビットを記憶すること、ここで、該２進木におけるそれぞれのノードが１つのカウンタと関連し；
（ｂ）該複数のＲＦＩＤタグから受け取られた１ビットが該ノードで記憶された１つのビットと一致するとき、該２進木中のノードと関連するカウンタを増やすこと；
（ｃ）該複数のＲＦＩＤタグから受け取られた１ビットが該ノードで記憶された１つのビットと一致しないとき、該２進木中のノードと関連するカウンタを減らすこと；および
（ｄ）該２進木における１つのノードと関連するカウンタの値に基づいた該複数のＲＦＩＤタグから受け取った１つのビットに対し１つの値を与えること；を包含する方法。
【請求項２】
２進木を横切るプロトコルを用いたタグの集合に呼出しするための無線周波数識別（ＲＦＩＤ）読み取り器における方法であって、
（ａ）２進木における１つの論理ノードに入る工程；
（ｂ）タグの集合に記号を伝達する工程；
（ｃ）少なくとも１つの記号が、タグの集合から受け取られたかどうかを判断する工程；
（ｄ）前記工程（ｃ）において、少なくとも１つの記号が受け取られたと判断された場合、タグの集合から受け取られた１つの記号が第一の論理値に一致するかどうかを判断する工程；
（ｅ）前記工程（ｄ）において、受け取られた１つの記号が第一の論理値と一致すると判断された場合、最初の論理値に関連するノードのカウンタの値を増加させる工程；
（ｆ）前記工程（ｄ）において、受け取られた１つの記号が第一の論理値と一致しないと判断された場合、第一の論理値に関連するノードのカウンタの値を減少させる工程；
（ｇ）前記工程（ｃ）において、少なくとも１つの記号が受け取られたと判断された場合、タグの集合から受け取られた１つの記号が第２の論理値に一致するかどうかを判断する工程；
（ｈ）前記工程（ｇ）において、受け取られた１つの記号が第２の論理値に一致すると判断された場合、第２の論理値に関連するノードのカウンタの値を増加させる工程；
（ｉ）前記工程（ｇ）において、受け取られた１つの記号が第１の論理値に一致しないと判断された場合、第２の論理値に関連するノードのカウンタの値を減少させる工程；
（ｊ）１つのタグのビットパターンとして記憶すべきどちらかの論理値を選択する工程；
（ｋ）タグのビットパターンの該ビットとして選択された論理値を記憶する工程；
（ｌ）ビットパターンが完全であるかどうかを判断する工程；および
（ｍ）ビットパターンが完全ではない場合；前記工程（ａ）に進む工程、
を包含する方法。
【請求項３】
請求項２に記載の方法であって、前記工程（ｊ）が、
タグの集合から受け取られた１つの記号が第一の論理値に一致し、およびタグの集合から受け取られた第２の記号が第２の論理値に一致するかどうかを判断する工程；
どちらか一方の記号がノイズによって引き起こされ得たかどうかを判断する工程；および
もし受け取られた１つの記号がノイズによって引き起こされ得たと判断された場合、タグのビットパターンのビットとして受け取られた記号と関連する論理値を選択する工程、を包含する方法。
【請求項４】
請求項３に記載の方法であって、受け取られたいずれか一方の記号がノイズによって引き起こされたという可能性を判断する工程が、
第１の論理値に関連するカウンタ値および第２の論理値と関連するカウンタ値の値を評価すること、を包含する方法。
【請求項５】
請求項４に記載の方法であって、
前記工程（ｃ）において、少なくとも１つの記号がタグの集合から受け取られたことが判断される場合、１つのノードの活動レジスタ値を増加させる工程、をさらに包含する方法。
【請求項６】
請求項５に記載の方法であって、
受け取られたいずれか１つの記号がノイズによって引き起こされたという可能性を判断する工程が、活動レジスタを回復すること；および
活動レジスタの値を評価すること、
をさらに包含する方法。
【請求項７】
請求項２に記載の方法であって、前記工程（ｊ）が、
タグの集合から受け取られた１つの記号が第１の論理値と一致するかどうか、およびタグの集合から受け取られた第２の記号が第２の理論値に一致するかどうかを判断する工程；
受け取られたいずれか一方の記号が弱いタグによって発生したかどうかを判断する工程；および
受け取られた１つの記号が弱いタグによって発生した可能性がある場合に、タグのビットパターンのビットとして１つの受け取られた記号と関連する理論値を選択する工程、
を包含する方法。
【請求項８】
請求項７に記載の方法であって、
受け取られたいずれか一方の記号がノイズによって引き起こされたという可能性を判断する工程が、
第１の理論値と関連するカウンタ値と第２の理論値と関連するカウンタ値を評価すること、を包含する方法。
【請求項９】
請求項８に記載の方法であって、
前記工程（ｃ）において、少なくとも１つの記号がタグの集合から受け取られたと判断される場合、１つのノードの活動レジスタ値を増加させる工程、
をさらに包含する方法。
【請求項１０】
請求項９に記載の方法であって、受け取られたいずれか１つの記号がノイズによって引き起こされたという可能性を判断する工程が、
活動レジスタを回復すること；および
活動レジスタの値を評価すること、
をさらに包含する方法。
【請求項１１】
請求項２に記載の方法であって、
タグのビットパターンが１つのタグの識別番号を含む方法。
【請求項１２】
請求項１１に記載の方法であって、
前記工程（ｌ）において、タグのビットパターンが完全であると判断された場合、記憶されたビットパターンが正当なタグの識別番号を含むかどうかを判断すること、
をさらに包含する方法。
【請求項１３】
請求項１２に記載の方法であって、
タグのビットパターンにおけるそれぞれのビットが２進木における理論ノードに対応する方法。
【請求項１４】
請求項１３に記載の方法であって、
ビットパターンが正当なタグの識別番号を含まない場合、タグのビットパターンにおけるそれぞれのビットに対応する理論ノードに対してノードのカウンタを減少させること、
をさらに包含する方法。
【請求項１５】
請求項２に記載の方法であって、
前記工程（ｃ）において、少なくとも１つの記号が受け取られなかったことが判断された場合、ビットパターンにおいて最後に記憶されたビットに対応するノードのカウンタを減少させること、
をさらに包含する方法。
【請求項１６】
請求項２に記載の方法であって、
第１の理論値が”０”という１つのデータであり、第２の理論値が”１”という１つのデータである方法。
【請求項１７】
無線周波数識別（ＲＦＩＤ）読み取り器において２進木横断プロトコルを用いたタグの集合に呼出しするための方法であって、
（ａ）２進木における１つの論理ノードに入る工程；
（ｂ）タグの集合に記号を送信する工程；
（ｃ）少なくとも１つの記号がタグの集合から受け取られたかどうかを判断する工程；
（ｄ）前記工程（ｃ）において、少なくとも１つの記号が受け取られたと判断された場合、記憶された情報を理論ノードと適合させる工程；
（ｅ）タグのビットパターンの１つのビットとしてどちらの理論値を記憶すべきかを選択する工程
（ｆ）該タグのビットパターンの該ビットとして選択された理論値を記憶する工程；
（ｇ）該ビットパターンが完全であるかどうかを判断する工程；および
（ｈ）該ビットパターンが不完全である場合、前記工程（ａ）に進む工程、
を包含する方法。
【請求項１８】
請求項１７に記載の方法であって、前記工程（ｄ）が、
前記工程（ｃ）において、少なくとも１つの記号が受け取られたことが判断される場合、タグの集合から受け取られた１つの記号が第１の理論値に対応するかどうかを判断する工程；
受け取られた１つの記号が第１の理論値に対応することが工程において判断される場合、第１の理論値に関連する１つのノードカウンタの値を増加させる工程；
受け取られた１つの記号が第１の理論値に対応しないことが工程において判断される場合、第１の理論値に関連する１つのノードカウンタの値を減少させる工程；
少なくとも１つの記号が受け取られたことが前記工程（ｃ）において判断される場合、タグの集合から受け取られた１つの記号が第２の理論値に対応するかどうかを判断する工程；
受け取られた１つの記号が第２の理論値に対応することが工程において判断される場合、第２の理論値と関連する１つのノードカウンタの値を増加させる工程；および
受け取られた１つの記号が第１の理論値に対応しないことが工程において判断される場合、第２の理論値と関連するノードカウンタの値を減少させる工程、
を包含する方法。
【請求項１９】
請求項１８に記載の方法であって、前記工程（ｄ）が、
少なくとも１つの記号がタグの集合から受け取られたことが前記工程（ｃ）において判断される場合、１つのノードの活動レジスタの値を増加させる工程、
をさらに包含する方法。
【請求項２０】
無線周波数識別（ＲＦＩＤ）読み取り器における、２進木横断プロトコルを用いた、タグの集合に呼出しするための方法であって、
タグの集合においてタグの２進木横断呼出しの結果としてタグの識別ビットパターンを読み込む工程；
該タグから誤り検出符号を受け取る工程；
ノイズによる汚染可能性がある読み取りタグ識別ビットパターンにおいて１以上のビット位置を識別する工程；
１以上の識別されたビット位置において代替のビット値をもつ潜在的ビットパターンを識別する工程；
収集されたタグの識別ビットパターンの誤り検出符号値を計算する工程；
それぞれ識別された潜在的なビットパターンに対する誤り検出符号値を計算する工程；および
計算誤り検出符号値が受け取られた誤り検出符号と一致するかどうかを判断する工程、
を包含する方法。
【請求項２１】
請求項１４に記載の方法であって、誤り検出符号値は巡回助長符号値である方法。
【請求項２２】
２進木横断プロトコルを用いた、タグの集合を呼出しするための無線周波数識別（ＲＦＩＤ）読み取り器の方法であって、
タグの集合と関連するデータを記憶する工程で、タグの集合データが２進木中のそれぞれ集められるノードと関連する情報を含む工程；
２進木を横切る間にタグの集合データに基づく横断路を判断する工程、
を包含する方法。
【請求項２３】
請求項２２に記載の方法であって、
２進木において集められるノードそれぞれに関する情報が情報の重みをつけるノードを含む方法で、該記憶する工程が、
（ｌ）それぞれの集められるノードに対して情報の重みをつけるノードを記憶すること、
を包含する方法。
【請求項２４】
請求項２３に記載の方法であって、
情報の重みをつけるノードが、
第１の論理ビット値に関する、１番目に記憶されるカウンタの値；および
第２の論理ビット値に関する、２番目に記憶されるカウンタの値、
を包含する方法であって、工程（ｌ）が１番目に記憶されるカウンタの値およびそれぞれ集められるノードに２番目に記憶されるカウンタの値を記憶すること、
を包含する方法。
【請求項２５】
請求項２２に記載の方法であって、
外部から読み取り器へのタグの集合データの少なくともいくつかを取得すること
をさらに包含する方法。
【請求項２６】
請求項２５に記載の方法であって、タグの集合データの少なくともいくつかが第２の読み取り器から取得される方法。
【請求項２７】
請求項２６に記載の方法であって、タグの集合データの少なくともいくつかがデータベースから取得される方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は無線周波数識別（ＲＦＩＤ）タグとＲＦＩＤの読み取り器の相互間の通信方法に関する。
【背景技術】
【０００２】
ＲＦＩＤシステムでは、ＲＦＩＤ読み取り器は与えられた通信範囲内で非常に多くの異なるＲＦＩＤタグを識別し、通信することが求められている。異なるＲＦＩＤタグのそれぞれは唯一の識別番号によって識別されるが、ＲＦＩＤ読み取り器はそれぞれのタグに関連付けられた識別番号を迅速にかつ正確に読み取ることが必須とされている。しかしながら、ＲＦＩＤの読み取り器とタグ相互間の通信チャネルがノイズによって汚染されているとき、ＲＦＩＤタグを迅速にかつ正確に識別するためのＲＦＩＤ読み取り器の能力は損なわれ得る。
【０００３】
今までのＲＦＩＤ読み取り器は、ＲＦＩＤタグの集合を読み込むためのアルゴリズムをいくらか変化させたものを典型的に使用している。このアルゴリズムは最も強い信号から弱いリターン信号まで要求されたタグを連続して読み込もうとする。それぞれのＲＦＩＤタグが読み込まれた後、そのアルゴリズムは終了する。読み込まれたタグ相互間では、なにも情報が実行されない。この技術はＲＦＩＤ読み取り器において実行するには単純であるが、ノイズが存在している場合十分なものではない。
【０００４】
ＲＦＩＤシステムで１つの主要な用途は電子目録である。現代経済では、商品の正確な目録を管理することが重要である。今までは、目録をとることはほとんど手動過程であり、そしてそれゆえ時間がかかり、かつ高価であった。ＲＦＩＤ電子目録システムでは、ＲＦＩＤタグが管理されるべき商品のそれぞれに付着される。それぞれのＲＦＩＤタグは唯一のタグ識別番号を割り当てられる。
【０００５】
典型的な用途では、多数のタグを付けられた商品はパレット上に記憶される。読み取り器はタグを付けられた商品を読み込んだり、目録化するために流通網の中の様々な場所に存在している。たとえば、１以上の読み取り器はドック扉に位置し得る。パレットがドック扉を通って移動するにつれて、読み取り器パレット上にあるタグの集合を問いただす。スタック内部にある商品上のタグは、外部のタグよりも多くのパレットの商品を通過しなければならないそれらの信号のために外部のタグよりも弱い信号をもつ傾向がある。結果として、内部のタグの信号は読み取りづらい。さらに、ノイズが存在するＲＦ環境においてＲＦＩＤ目録アプリケーションの多くが作用する。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
その結果として、ノイズに強固である方法又はＲＦＩＤ読み取り器、他のＲＦＩＤ読み取り器又はＲＦＩＤ読み取り器に関する情報をコンパイルするシステムによって得られた過去の情報を、読み取り中又は読み取り前に最適に利用する方法で、ＲＦＩＤ読み取り器がＲＦＩＤタグの集合を効率よく読み取ることを許可する代替技術に関する需要がそれゆえ存在する。
【０００７】
さらに、読み取り比率、並びにＲＦＩＤタグに弱々しく応答する読み取り精度を最大化にするＲＦＩＤ読み取り器とＲＦＩＤタグの集合相互間の通信手段も必要である。
【課題を解決するための手段】
【０００８】
（発明の簡単な要約）
本発明は、ノイズチャネルの存在上で唯一の識別番号を用いて無線周波数識別（ＲＦＩＤ）タグの集合を効率よく読み込むためのシステムおよび方法に向けている。本発明の局面によると、ＲＦＩＤシステムは、それぞれ処理モジュールと記憶装置をもった１以上の読み取り器を包含している。該記憶装置は２進木データ構造（２進木）にあるノードについて一連の情報を記憶する。その一連の情報は”０”ビットのカウンタと”１”ビットのカウンタである活動レジスタを包含する。例えばノードまでの経路の長さといった、このノードのその他の特徴もまた記憶し得る。
【０００９】
他の局面では、処理モジュールが論理を包含する。この論理は、読み取り器の通信範囲内で唯一の識別番号をもつＲＦＩＤタグの収集を特徴付ける２進木をＲＦＩＤ読み取り器に効率よく読み取らせる。本発明の局面では、読み取り器がタグの集合から１つ以上の応答信号を受信したとき、読み取り器は、横切られる現在のノードに対して記憶された情報を調整する。もし単に”０”が受信された場合、読み取り器は活動レジスタの値を増加させ、”０”カウンタを増加させ、”１”カウンタを減少させる。もし単に”１”が受信された場合、読み取り器は活動レジスタの値を増加させ、”１”カウンタを増加させ、”０”カウンタを減少させる。もしどちらの信号も受信された場合は、両カウンタと活動レジスタを増加させる。さらに、読み取り器もまた、読み取りサイクルの効率を最適化するために、どの分岐を横切るべきかを判断するために記憶されたノード情報を評価する。
【００１０】
本発明は、誤り検出符号処理を用いた２進木の横断中に見つかった誤りの存在の中で、有効なタグを識別するためのシステムおよび方法に向けている。本発明の局面によると、２進木横断中、タグの識別番号の１以上のビット位置は潜在的に汚染されることを読み取り器は判断する。この情報を用いると、読み取り器は潜在的に有効な一連の識別番号を判断する。それぞれの潜在的な識別番号に対して、読み取り器は誤り検出符号の値を計算する。その後、読み取り器は計算された誤り検出符号の値が、読み込まれたタグから受信した誤り検出符号と一致するかどうかを判断する。もし、計算された値が一致した場合、関連した識別番号は正しいタグの識別番号である。
【００１１】
これらまたは他の目的、利点並びに特徴は、発明の詳細な説明の観点から直ちに明らかにする。
【発明を実施するための最良の形態】
【００１２】
本明細書中に取り込まれ、説明の一部を形成する添付の図面は、本発明を示しており、この詳述とともに本発明の原理を説明すること、および当業者が発明を実施し、使用することを可能にすることを助ける。
【００１３】
添付の図面を参照しつつ、今から本発明を説明する。図面の中では、同じ参照番号が同一又は機能的に同一の要素を示し得る。さらに、参照番号のレフトモーストディジットは参照番号が初めに現れる図面を識別し得る。
（１．導入）
（１．１  タグ問合せ環境）
本発明の詳細を記載する前に、発明が実施される環境例について記載しておくと役に立つ。本発明はノイズが存在する環境で操作する、無線周波数識別の適用において特に有効である。本発明によれば、図１は１つ以上のＲＦＩＤタグ読み取り器１０４とＲＦＩＤタグ１２０の例示的な集合とが通信している環境１００を示している。図１をみると、タグ１２０の集合は７つのタグ１０２ａ−１０２ｇを包含している。本発明の実施例によると、タグ１２０の集合はいずれのタグの番号１０２をも含み得る。ある実施例では、タグの非常に大きい番号は１００、１０００又はそれ以上のタグ１２０の集合の中に包含され得る。
【００１４】
例示の環境１００はまた１つ以上の読み取り器１０４をも含んでいる。これらの読み取り器１０４は独立に動作し得、また図２に示すように、読み取りネットワークを形成するために連結もし得る。読み取り器１０４はタグ１２０の集合にアドレスする外部のアプリケーションによって要求され得る。もしくは、読み取り器は通信を始める内部の論理を有し得る。もし、読み取り器がタグの集合と通信していない場合、読み取り器１０４は通常ＲＦエネルギーを放射しない。このことから、異なる配向からではあるが、タグの集合の全体へのＲＦ信号の完全範囲をできるだけ達成するように、他の読み取り器がタグの集合のいくつかと通信することとなる。さらに、同じ読み取り器が、タグの範囲を増加するために異なる周波数を使ってタグの同じ集合のいくつかに作用し得る。
【００１５】
本発明によると、１以上の呼掛けプロトコルにしたがって読み取り器１０４とタグ１０２相互間で信号１１０と１１２が交換される。具体的な呼掛けプロトコルは以下に述べる２進木横断規則である。信号１１０と１１２は、例えば無線周波数（ＲＦ）伝達のような無線信号である。信号１１０を受信したとき、タグ１０２は、時間に依存したパターンや周波数による信号１１０の一部を２者択一的に反射したり、吸収することによって応答信号１１２を発生し得る。信号１１０を択一的に吸収したり、反射するためのこの技術は本明細書では後方散乱モジュレーションとして参照される。本発明はさらに他の方法で通信するＲＦＩＤタグに適用もできる。
【００１６】
本発明の実施例によれば、図２Ａは１つ以上の読み取り器１０４とタグ１０２相互間の通信を提供するＲＦＩＤシステム２００の例のブロック図式である。ＲＦＩＤシステム２００は使用者用のドメイン２５０、読み取り器１０４ａからｎのネットワーク、並びに１つ以上のタグ１０２を包含する。図２に示されるようにネットワークにおいて連結された複数の読み取り器同様、１つの読み取り器に対しても本発明が適用できるということに注目されたい。それ故、明細書に”読み取り器”はしばしば参照されるけれども、本発明は特別な用途によって要求されるどのような形態においてもいかなる数の読み取り器に対しても適用できることに理解すべきである。
【００１７】
読み取り器１０４のそれぞれは、１つ以上のアンテナ（ｅ）２１０を経由してタグ１０２と通信する。種々のアンテナの構成が利用可能である。例えば、１つの実施例では、読み取り器１０４ａは４つのアンテナ（例えば、アンテナ２１０ａから２１０ｄ）までに対して直接に接続され得る。他の実施例では、読み取り器１０４ｂはマルチプレクサに連結され、制御する。マルチプレクサは非常に多くのアンテナが読み取り器の単一のアンテナポートに切り替えられることを許容する。このようにして、読み取り器１０４ｂは非常に多くのアンテナを収容し得る。
【００１８】
使用者用のドメイン２９０は１つ以上の使用者の適用を包含し得る。使用者の適用は、通信ネットワーク又はデータリンクを経由して１つ以上の読み取り器１０４と通信し得る。高水準では、読み取り器は、使用者用のドメイン２９０から１つ以上のタグ１０２に関する要求を受け取ってもよい。例えば、アプリケーションは読み取り器１０４にタグの集合を問合せするように要求し得る。
【００１９】
読み取り器１０４ａからｎのそれぞれは、処理モジュール２４０と記憶装置２５０を包含する。図２Ｂは、本発明の実施による図解のＲＦＩＤ読み取り器１０４のブロック図である。図２Ｂの実施例において示されているように、処理モジュール２４０は、記憶装置２５０の中に記憶されているノード情報に基づいた横断路を判断する論理２７０を包含し得る。読み取り器の通信範囲内の唯一の識別番号を持つＲＦＩＤタグの収集を特徴付ける２進木をＲＦＩＤ読み取り器が効率的に読み取ることを可能にする。読み取りサイクル中にタグの集合内のすべてのタグを読み取ることは、複数のタグに共通するビット列を通って繰り返し通過する結果となる。そのうえ、読み取り器は一般的にタグの集合上で複数の読み取りサイクルを行う。ゆえに、タグの唯一の識別番号でさえ複数時間で読み取られる。本発明の処理論理は、２進木を通ったこれらの繰り返し通過中に収集した情報を捨てない。その代わりに、読み取り器は２進木の中にあるそれぞれのノードの占有を示す情報に編集する。多くの標本上のある特定のノードでの不規則なノイズは平均するとゼロになり、系統的な信号は平均をゼロにしないので、２進木中のどのビットのＳＮ（ノイズに対する信号）比は何度も試行することによって改善される。この読み取り器の論理は非常に高いビットの割合でマグニチュードの同等の単位によってタグの読み取り割合を改善することができる。
【００２０】
さらに、処理モジュール２４０は、誤り検出処理に基づくタグの識別番号を識別するために論理２８０をも包含し得る。
【００２１】
記憶装置２５０はタグの集合１２０と関連するデータを記憶する。実施例においては、記憶装置２５０は２進横断木の中のすべてのノードに対する２つのレジスタとカウンタを格納するために構成されている。第１のカウンタ２６０は、そのノードにおいて”１”の記号の重みを記憶し、第２のカウンタ２６５は”０”記号の重みを記憶する。さらに、記憶装置２５０は、２進横断木の中でそれぞれのノードに対する活動レジスタ２３０を格納するために構成されている。
【００２２】
実施例においては、記憶装置２５０は、利用される２進木の中のノードに対してのみ情報を格納するために構成されている。例えば、集めらる路の中にあるそれぞれのノードに対して、記憶装置２５０は１以上のカウンタを格納するために構成されている。当業者によって理解されるように、記憶装置２５０においてタグ集合データを記憶するための他の選択肢が存在する。
【００２３】
ノードの特別な情報の記憶を実施する方法は、読み取り器１０４の実行と基本設計概念への依存を変化しうる。記憶実行の例は１以上のデータアレーまたはリンクされたリストを包含する。当業者によって理解されるように、記憶装置に対する他の選択肢は存在する。
【００２４】
さらに、用語”カウンタ”の使用は、特別な実行を示すことを意図しない。それぞれのカウンタは、レジスタとして又はハードウェア、ソフトウェア、ファームウェア、又はそのいずれの組み合わせを包含する他の方法で実施され得る。
【００２５】
記憶装置２５０の中に記憶されたタグの集合１２０に関するデータは、他の読み取り器１０４又は他のアプリケーションと共有され得る。例えば、読み取り器１０４ａは、読み取り器１０４ｂをもつタグの集合１２０に関連する編集データを共有し得る（例えば、重みを付けられた木の情報）。編集データは使用者のドメイン２９０又は他の位置の中のデータベースに記憶をもされ得る。実施例では、タグの集合１２０に関連する編集される知識又はその知識を包含する位置に対するインデックスは、例えばタグ１０２又はバーコードのような分離装置上に記憶される。例えば、バーコードはタグ集合データの記憶位置に対するインデックスを包含し得る。実施例においては、読み取り器１０４（又はアプリケーション）は、他の読み取り器、データベース、若しくは他の装置に記憶されるタグ集合１２０に関するデータを用いて、その記憶装置２５０を事前に読み取れ得る。
【００２６】
図３は、記憶装置２５０の中に記憶されるノードのデータの例の一連の理論的な説明を示している。図３は、ルートレベル以下に３つのレベルを持つ２進横断木３００を示しており、該２進横断木では、それぞれのレベルがタグの識別番号の中の１つのビット位置に対応する。３つのレベルは例証目的で示されており、本発明はノードデータのいかなる大きさのセットに対しても適用されるということを注目すべきである。２進木は３１０ａからｏの１４個のノードを持つ。それぞれのノードは、以上で説明したように、関連する”０”カウンタ２６５および”１”カウンタ２６０を持ち得る。それぞれのノードは活動レジスタをも有し得る。さらに、そのノードでの横断路の長さのような、ノードを特徴付ける他のパラメータは記憶され得る。２つの枝は、木の一番低いレベルにあるノード（ノード３１０ｈからo）を除いたそれぞれのノードから伸びる。それぞれの枝の対に対し、”０”の枝は左のほうに降下し、”１”の枝は右の方に降下する。
【００２７】
実施例においては、読み取り器がノードを横切っている間に”０”記号を受信するたびに、ノードでの”０”カウンタ２６５の値は増加する。ノードでの”０”カウンタ２６５の値は、読み取り器がノードを横切る間に”０”記号を受信しないときはいつでも、減少する。同様に、ノードでの”１”カウンタ２６０の値は、読み取り器がノードを横切る間に”１”記号を受信するたびに増加する。ノードでの”１”カウンタ２６０の値は、読み取り器がノードを横断する間、”１”記号を受信しないときはいつでも減少する。代替の実施例では、当業者に対して理解されるように、カウンタは、受信された記号を書き込むためのほかの方法で増加又は減少し得る。
【００２８】
実施例においては、活動レジスタは、存在するとき、２進木の不使用又は休止状態の部分を検出するために使用され得る。例えば、実施例において、ノードがタグ集合の読み取りサイクルの間に横断するときはいつでも、活動レジスタは増加する。２進木流通のの外側では、アプリケーションに対して設定される初めに決定された間隔で、２進木の中におけるすべての活動レジスタが減少する。最小の閾値よりも下に落ちる活動レジスタを持つノードは死としてマークされ、また木の新しく又は他の枝に再度移転するのに現在利用できる。このようにして、２進木および木中の情報は、ＲＦＩＤ集合を持つ連続した方法において成長し、進化する。
【００２９】
当業者によって理解されるように、本発明は、読み取り器のプラットフォームおよびネットワーク構成の多様性に基づいて実行され得る。
（1.2  応答プロトコル）
本発明の実施によると、２進木横断方法論は読み取り器の通信範囲内の読み取り器１０４とタグの集合１２０の１つとの通信を確立するために使用されている。このような実施例によると、それぞれのタグ１０２は唯一の識別番号によって識別される。唯一のタグ識別番号のレイアウトは以下に示される。
【００３０】
【数０１】
2006503502.tif 000003
唯一のタグの識別番号のそれぞれはタグの識別ビットと誤り検出符号ビットを内蔵している。例えば、唯一のタグ識別番号のそれぞれは、９６ビットの識別番号と１６ビットの誤り検出符号の値を持ち得る。しかしながら、本発明は他のタグの識別番号の長さや誤り検出符号の長さに対しても適用できる。この明細書を通して、内蔵されたタグの識別番号（例えば、９６ビット番号）はタグの識別番号として参照される。
【００３１】
この実施例では、周波数の分離で唯一となった、それぞれのタグ１０２から読み取り器１０４までの通信を要求することにより、タグ１０２相互間の競合が避けられるが、他の方法によっても回避し得る。この競合は、互いの試行通信を破壊的に干渉する同周波数、同時刻、同位相における複数の通信による通信として定義し得る。このようにして、例示的な２進横断アルゴリズムにおいて、情報の１ビットが、読み取り器１０４と読み取り器がアドレスしている現在のタグ１０２の集合の間で同時に交渉する。それぞれのタグの応答は２つの周波数、０に対する１つの周波数および１に対するその他の周波数によって定義される。このようにして、多くのタグが同時におよび非破壊的にデータ０と通信し得る。読み取り器は、データ０が丁度存在する時に、単一のデータ０と複数のデータ０を区別できないことは重要ではない。代わりに、例えばタグの応答は、２つの時間周期、”０”に対する１つの時間周期および”１”に対するその他の時間周期によって定義され得る。
【００３２】
実施例では、２進木横断処理は唯一の番号をもった１つのタグのみが孤立化されかつ確認されるまで通信からタグを削除する。上記のように、２進木の中にあるそれぞれのレベルはタグの識別番号中のビット位置を表現する。読み取り器が２進木の中のノード（またはレベル）を経過するにつれて、アクティブのままでタグの集合の下位集合に向かい、そしてタグのタグの集合の下位集合へ向かうとアクティブでなくなる。例えば、一致するビットを最後に送信したタグはアクティブのままである；一致するビットを最後に送信しなかったタグはアクティブにならない。統計的に、それぞれのビット交換上で、タグの集合の２分の１はアクティブにならないであろう。この処理は、読み取り器が２進木の最終レベルの中のノードに到達するまで続き、唯一ののタグの孤立または削除の結果となる。この処理は、タグの集合の中のそれぞれのタグが孤立化されるまで繰り返される。
【００３３】
２進木横断の方法論に関するさらなる情報としては、次の同時係属中の米国特許出願を参照のこと。出願番号１０／０７２、８８５で、２００２年２月１２日に出願され”タグ集合の２進横断に関する方法、システム、装置”という表題をつけられ、代理人番号は１６８９．０２１０００１であるもの；および出願番号が１０／０７３、０００で、２００２年２月１２日に出願され、”ＲＦＩＤタグの集合を用いた通信に関する方法、システム、装置”という題目を付けられ、代理人番号が１６８９．０２６００００であるものである。ＲＦＩＤの読み取り器とＲＦＩＤタグの集合の相互間の通信に関するさらなる情報としては、米国特許番号６，００２，３４４で、”電子目録に関するシステムおよび方法”および出願番号０９／３２３、２０６で、１９９９年６月１日に出願された”電子目録に関するシステムおよび方法”という題目を付けられたもので、代理人番号は１６８９．００１０００１のものを参照のこと。
（２．重み横断路を用いた２進木横断）
図４は、実施例による本発明の操作を表現するフローチャート４００である。このフローチャートは、タグの集合の応答の効率を増加することに重きを置く横断路の本発明の使用を示している。本発明は、読み取り器によって使用される２進木横断プロトコルと連帯して働く。２進木横断プロトコルの例は上記されている。フローチャート４００は、上記の図２中に例示された環境への連続した言及をもって記載されている。しかしながら、当該発明はその環境に限られない。フローチャート４００において示されたいくつかの工程は必ずしも順序で起こらなければならないことはない。
【００３４】
フローチャート４００は、読み取り器１０４がタグの集合１２０の２進木横断を始めるとき、工程４１０で始まる。本発明は、いかなる２進木横断応答技術を用いて使用され得る。例示された応答技術は、一般的な読み取り技術（読み込まれたすべてのフィールドとして参照されもする）、特別な読み取り技術およびグループ読み込み技術を包含する。一般的な読み取り技術は、検出され得るタグの集合において、すべてのタグを読み込むことを包含する。特別な読み取り技術は特殊なビットパターンを使用するタグの集合を横断する。グループ読み取り技術は特別な読み取り技術と一般的な読み取り技術の混成である。
【００３５】
２進木横断を始めた後、工程４１５において、読み取り器は２進木のノードに入る（例えば、ノード３１０ａからｏの１つとして図３に示されている）。２進木横断プロトコルの一部として、２進木の中のそれぞれのノードで、読み取り器はタグの集合からの応答を始めるために信号を送信する。典型的な２進木横断プロトコルでは、その応答は少なくとも１つのタグの識別番号においてビットを示す記号を有する。
【００３６】
工程４２０において、読み取り器は、応答がタグの集合から受信されたかどうかを判断する。応答が受信されなかった場合、操作は工程４９０に進む。応答が受信された場合、操作は工程４３０に進む。
【００３７】
工程４３０において、読み取り器はどちらの枝を横断すべきかを判断する（例えば、読み込まれたタグの識別番号における次のビットとしてどのビットを蓄積すべきか）。工程４３０に対する実施例として、図５Ａはどの枝を横断すべきかを判断するためのフローチャート５３０Ａを示す。読み取り器は、例えば、読み取り処理がノイズの影響を受けやすいという可能性が存在するという判断がされた場合、フローチャート５３０Ａの方法を用い得る。フローチャート５３０Ａはノイズの存在においてタグの応答の孤立化に重みをおく横断路を用いる。
【００３８】
５４１の工程において、読み取り器は現在のノードが分岐ノードであるかどうかを判断する。分岐ノードは、”０”の応答値と”１”の応答値の両方が受信され、読み取り器がどちらの枝を横断すべきかを決定しなければならないノードである。ノードが分岐ノードでない場合（例えば、唯一の応答値が受信された場合）、動作は工程５４２に進む。もしノードが分岐ノード（つまり、どちらの応答値も受信された場合）、操作は工程５４５に進む。
【００３９】
工程５４２において、読み取り器は受信された信号値に対応する枝を選択し、操作は４５２に進む。
【００４０】
工程５４３において、読み取り器は、受信される信号のうちの１つまたは両方がノイズ又は他の問題によって引き起こされた可能性もしくは見込みがあるかどうかを判断する。読み取り器は、この判断を記憶装置２５０に記憶されるノード情報の評価に基づかせる。例えば、読み取り器は読み取りサイクル中に何度も特別なノードを通過し得るので、集合されない枝が長時間にわたって相対的に低い値をもつカウンタ２６０と２６５をもつ間、タグの集合路における枝と関連するカウンタ２６０と２６５は長時間にわたって高い値を持つ。結果として、カウンタ２６０と２６５は、判断工程の間、重みのある要因として使用され得る。例えば、”０”カウンタ２６５が大きいマイナス又はゼロである間に”１”カウンタ２６０が大きくプラスである場合、その時読み取り器１０４は、”０”記号がノイズによって引き起こされた可能性があると判断し、それゆえプラスの重みがついた横断すべき”１”の枝を選択する。読み取り器は、誤り路の可能性のある兆候としてそのノードで横断路（つまり、このノードよりも先に横断されるノードの数）の長さも考慮し得る。
【００４１】
工程５４９において、読み取り器が工程５４３においてどちらの信号もノイズによって引き起こされないという可能性もしくは見込みがあると判断する場合、読み取り器は横断すべき枝を選択するために省略の選択を適用する。例えば、読み取り器は最大強度の信号に対して省略の選択を有し得る。代わりに、読み取り器は、例えばビット”０”もしくはビット”１”のような特別なビット値として省略の選択を有し得る。
【００４２】
工程５４４において、１つの受信された記号が工程５４３においてノイズによって引き起こされた可能性もしくは見込みがあると読み取り器が判断する場合、読み取り器はその他の受信される信号値に対応する枝を選択する。この技術は通信路上で正当なタグが発見される可能性を高め得る。ノイズの過渡的な性質ために、次の横断中に同じノードでノイズが存在するという可能性は非常に小さい。それゆえ、読み取り器があとの横断中に同じノードに到着する場合、ノイズ信号はそのノードで存在する可能性は低い。このように、読み取り器はノイズのために非集合路を誤って横断することがないことによって効率性を高める。
【００４３】
読み取り器が受信された記号の両方がノイズによってひきおこされた可能性もしくは見込みがあると判断する場合、読み取り器は路の横断を終了することを選択し、そしてもう一つの路の横断を始める。その代わりに、読み取り器は横断すべき（工程５４４と類似）枝を選択し得、工程４５２への通過を動作し得る。どちらの信号もノイズである場合、タグの応答は次のノードで”消えてなくなる”。
【００４４】
図５Ｂは、工程４３０に対する本発明の代替的な実施例において、次の読み取りビット値を判断するためのフローチャート５３０Ｂを示す。読み取り器は、例えば読み取り処理はノイズの影響をうけるという可能性が低い又は存在しないという判断がなされた場合、フローチャート５３０Ｂの方法を使用し得る。フローチャート５３０Ｂは、弱い又は読み込まれないタグを孤立化したり読み込むことに重みをおく横断路を使用する。弱いタグは読み取りが困難である信号をもつタグになり得る。
【００４５】
工程５４１と５４２は、フローチャート５３０Ａの言及で以上に記載される工程５４１と５４２と同一である。工程５４１においては、読み取り器は現在のノードが分岐ノードであるかどうかを判断する。ノードが分岐ノードでない場合（つまり、１つの受信値のみが受信された）、操作は工程５４２へ進む。ノードが分岐ノードである場合（つまり、応答値の両方が受信された）、操作は工程５４７へ進む。
【００４６】
工程５４２において、読み取り器は受信される信号値に対応する枝を選択し、操作は工程４５２へ進む。
【００４７】
工程５４７において、読み取り器は受信される信号のうち１つ又は両方が弱いもしくは読み込まれないタグからである可能性又は見込みがあるかどうかを判断する。読み取り器はこの判断を記憶装置２５０に記憶されるノード情報の評価に基づかせる。例えば、”０”カウンタが陰性又はゼロである間に”１”カウンタ２６０が高度に陽性である場合、そのとき読み取り器は、受信される”０”の信号が弱いタグからのものである可能性があると判断し、横断すべき”０”枝を選択する。
【００４８】
工程５４７において読み取り器が１つの受信される記号は弱いタグからのものである可能性もしくは見込みがあると判断する場合、操作は工程５４８へ進む。工程５４８において、読み取り器は弱いタグとして受信される信号値に対応する枝を選択する。
【００４９】
工程５４７において読み取り器がどちらの信号も弱いタグからのものではない可能性もしくは見込みがあると判断する場合、操作は工程５４９へ進む。
【００５０】
工程５４９において、読み取り器は省略の選択を適用して横断すべき枝を選択する。例えば、読み取り器は最大信号に対する省略の選択を持ち得る。その代わり、読み取り器はビット”０”又はビット”１”のような特別なビット値に対して省略の選択を有し得る。
【００５１】
フローチャート５３０Ａもしくは５３０Ｂの完成の後、操作は工程４５２に進む。工程４５２においては、読み取り器は活動レジスタ（”０”又は”１”の記号のいずれか一方が工程４２０において受信された場合）を増加させる。
【００５２】
工程４５３において、受信されるビットが０に等しい場合、操作は工程４５４に進む。工程４５４において、読み取り器のネットワークはノードに対する”０”カウンタ２６５を増加させ、操作は工程４５６に進む。工程４５３において、受信されるビットが０に等しくない場合、操作は工程４５５に進む。工程４５５において、読み取り器のネットワークは”０”カウンタ２５６を減少させ、操作は工程４５６へ進む。
【００５３】
工程４５６において、受信されるビットが１に等しい場合、操作は４５７へ進む。工程４５７において、読み取り器のネットワークはノードとして”１”カウンタ２６０を増加させ、操作は工程４６０へ進む。工程４５６において、受信されるビットが１に等しくない場合、操作は工程４５８へ進む。工程４５８においては、読み取り器のネットワークはノードとして”１”カウンタ２６０を減少させ、操作は工程４６０へ進む。
【００５４】
本発明の実施例においては、”１”カウンタ２６０および”０”カウンタ２６５は陰性の値を反映し得る。代替的な実施例では、減少工程がカウンタに陰性の値を持たせる場合、”１”カウンタ２６０および”０”カウンタ２６５は０に保持される。工程４５２から４５８は初めに０ビットをチェックしその後１ビットをチェックする読み取り器を示すが、本発明の精神もしくは範囲から外れることなく、読み取り器はどのような順序でも又は同時にこれらの工程を実行し得る。本発明の代替的な実施例においては、読み取り器がどちらの枝を横断（工程４３０）すべきかを判断する前に、ノード情報（工程４５０から４５８）の適合が起こり得る。
【００５５】
工程４６０において、読み取り器１０４はタグの識別の流れの中で次のビットとしての読み取りビットを蓄積する。工程４６０の一連の実行中、読み取り器１０４は現在のタグの識別番号のビットの流れを形成する。
【００５６】
工程４６５おいて、読み取り器は、完成したタグの識別番号が蓄積されたかどうかを判断する。タグの識別番号が完全でない場合、操作は工程４９８へ進み、読み取り器は２進木横断を続ける。
【００５７】
完全な識別番号が蓄積された場合、操作は工程４７０へ進む。工程４７０において、読み取り器は正当なタグが読み取られたかどうかを判断するために誤り検出処理を実行する。本発明の実施例においては、誤り検出処理は巡回冗長検査（ＣＲＣ）処理である。ＣＲＣはデータ通信の適用において使用される共通の誤り検出プロトコルである。当業者に理解されるように、他の誤り検出プロトコルは使用され得る。
【００５８】
工程４７２において、タグの識別番号が正当である場合、操作は工程４９８へ進む。工程４７２において、タグの識別番号が正当でない場合、正当でないタグの識別番号が蓄積され、操作は工程４７４へ進む。工程４７０と４７２は別個の工程として表現されるが、それらは読み取り器によって同時に実行され得る。
【００５９】
工程４７４において、読み取り器は現在の横断路中の全ての先行するノードの適切なカウンタを減少させる。その後、操作は４９８へ進む。
【００６０】
２進木横断中、読み取り器はいずれかのタグが既に読み取られる場合又はノイズによって短時間に２進木データ構造の非集合の枝が集合しているとうに見えるという点で、読み取り器がタグの集合からの応答を受信し得ない。工程４９０において、タグの集合から全く応答を受信しない場合、読み取り器は現在の横断の間、タグの識別ビットが蓄積されたかどうかを判断する。タグの識別ビットが蓄積されなかった場合、操作は工程４９８へ進む。
【００６１】
読み取り器がタグの識別ビットが工程４９０において蓄積されたかどうかを判断する場合、読み取り器は、読み取り器が２進木の中の誤った経路へ降り進んだことを確かめる。誤った経路によるタグの応答のこの消失は、第１の誤った枝が選択されたノードの後ろで直接的に最も起こり得るだろう。それ故、本発明の実施例において、工程４９５では、読み取り器は消失にすぐに先行するノードで誤った経路に対応するカウンタの重みを減少させる。代替的な実施例では、読み取り器は、誤った枝が選択されたところよりも前のノードのような、横断経路中の付加的ノードでカウンタを減少し得る。カウンタが適合される後に、操作は工程４９８へ進む。
【００６２】
工程４９８において、読み取り器１０４は２進木横断を再開する。２進木横断の再開は２進木横断のプロトコル中で様々な点で起こり得る。例えば、完全な正当なタグの識別番号が受信された場合、読み取り器１０４は命令処理点で２進木横断を再開し得る。代わりに、正当でないタグの識別番号が受信される又は部分的なタグの識別番号が受信された場合、読み取り器はスタート／ルートのノードで２進木横断を再始動し得る。タグの識別番号中の付加的ビットが蓄積されるままである場合、読み取り器１０４は２進木中の次のノードへ進みもし得る。
【００６３】
タグの集合の応答が完成された場合（例えば、２進木横断が完成する場合）、読み取り器１０４はそれぞれのノードでビットカウンタをクリアーし得る。代わりに、読み取り器１０４は一定時間周期又は読み取りサイクルの一定数でカウンタの値を記憶し続け得る。例えば、読み取り器１０４が同じタグの集合の第２の読み取りを実行している場合、読み取り器１０４は第１の読み取りサイクルからのカウンタ値を使用し、これらの値を増加又は減少し得る。実施例では、読み取り器１０４は処理より前にタグ集合１２０と関連する情報を記憶装置２５０へ取り込みをもし得る。このタグの集合の情報は他の読み取り器１０４又は使用者のドメイン２９０の中のデータベースから得られ得る。
【００６４】
当業者にすぐに評価されるように、本発明の実施例に基づきＲＦＩＤの読み込みおよびトラッキングの上記される方法は、ＲＦＩＤ読み取りフィールド（ポーリング）の中の全てのタグの唯一のＩＤ番号を求めたり、受け入れたりするシステム、又はＲＦＩＤタグがＲＦＩＤの読み取りフィールド（イベントレポート）の内又は外を通過する時間を判断しようとするシステムに適応され得る。
【００６５】
タグの効率よい読み取りに関するもう一つの技術はスタック上のタグの識別番号の間で共通であるビット列を識別および記憶する。該スタック上では、順次にスタックから引っぱって外され、読み出される。そして、この識別番号は、読み取り器１０４はタグの識別番号の第１のｎビットを蓄積し得る。次のビット位置を交渉している間に、読み取り器はタグの集合から２つの記号を受信し得る。読み取り器は横断すべき１つの記号に関連する枝を選択する。その後、読み取り器はスタック上の他の記号に関連するビット列を記憶する。このスタッキングは分岐ノードが到達されるときはいつでも読み取り器によって実行される。スタックから引っぱって外される１つのビット列は除外されるので、これらのビットは誤りビットの影響を受けにくい。この技術は複雑であるが、ノイズに対して強靭である。しかしながら、この”スタック”技術は、ＲＦＩＤタグの集合の読み取りの処理の間に、ＲＦＩＤ読み取り器によって得られた情報のすべてを最適に活用するわけではない。
タグの効率よい読み取りに関するもう一つの技術は、タグの応答の消失が２進木横断中に起こる後に、記憶された横断経路を使用する。この技術においては、応答の消失の後、読み取り器が、２進木横断中に蓄積される記憶される横断経路を取り戻す。その後、読み取り器は、新たな”修正される”２進木横断中に、記憶された横断経路のそれぞれのビットを読み取り器に伝える。記憶される横断経路の中のビットを交渉している間、読み取り器はタグからの応答を無視し、記憶される横断経路を通って進む。これは、読み取り器が、記憶される経路の中のすべてのビットに関連するノードを横断し、又は一連のビットに関連するノードを横断した時まで続く。その後、この読み取り器は、蓄積された残存するビットに対する基準２進木横断を再開する。
（３．誤り検出処理を用いたタグ識別）
ノイズ操作環境において、読み取り処理中に、タグに対する蓄積されるタグの識別番号はノイズによって汚染され得る。結果として、タグから受信される誤り検出符号値は、蓄積されるタグ識別番号を用いて読み取り器によって計算される誤り検出符号値と一致しない。共通のタグの応答プロトコルにおいて、読み取り器は識別番号における１つ以上のどのビットが汚染されているかわらない。これらのプロトコルにおいて、読み取り器は全体の識別番号を捨て、タグを識別するために１以上の付加時間でタグの読み取り処理を実行しなければならない。
【００６６】
本発明では、読み取り器は１以上のどのビットがノイズによって潜在的に汚染されたかを判断し得る。読み取り器は、他の読み取り処理を実行せずに個々のタグを正しく識別するためにこの知見を使用し得る。図６は、１０ビットの識別番号６９２と誤り検出符号値６９３をもつ例示的なタグを示す。読み取り処理の間、読み取り器は、ノイズ（図６に示されているように０と１の値を両方もつ）によって潜在的に汚染された２つのビット位置６９５と６９６を識別した。このようにして、読み取り器は、２つの未知のビットの４つの可能な組み合わせによる４つの潜在的な１０ビットの識別番号６７７ａからｄのうち１つを正当なタグが持っていることを判断し得る。４つの潜在的な１０ビットの識別番号６７７ａからｄのそれぞれは関連する誤り検出符号値６７８ａからｄを有する。誤り検出符号値６７８ａからｄは読み取り器１０４によって計算される。その後、正当なタグの識別番号が、誤り検出符号値６７８ａからｄに対する読み取り処理の一部としてタグから受信された誤り検出符号値６９３と一致することにより識別し得る。照合される誤り検出符号値に関連する識別番号６７７ａからｄは、正当な識別番号として読み取り器によって示される。
【００６７】
図７は、本発明の実施によるタグ１０２と読み取り器１０４相互間の通信の間に導入される誤りの存在の中でタグを識別するために誤り検出コード処理を用いるフローチャート７００を示す。本発明の実施例として、誤り検出符号処理は巡回冗長（ＣＲＣ）処理である。当業者に理解されるように、フローチャート７００は、この明細書中に記載されるように重きを置く横断経路を用いるタグ集合の応答を組み合わせて使用され得る。
【００６８】
フローチャート７００は、読み取り器がタグ１０２又はタグの集合１２０と通信し始める時、工程７１０から始める。実施例では、通信は、タグ１０２又は複数のタグがタグと読み取り器の通信中に無音状態に置かれない読み取り処理又は他の処理を有し得る。工程７２０において、読み取り器はノイズによって潜在的に汚染されるビット位置を識別する。例えば、読み取り器が”０”および”１”の記号の両方を受信する場合、読み取り器は潜在的に汚染されるとき関連するビット位置を識別し得る。読み取り器は、例えばノードの横断経路の長さ又はビットカウンタおよび活動ノードレジスタの値などの他の利用できる情報をビット位置がノイズによって汚染されたかどうかを判断するするためにも使用し得る。
【００６９】
通信中に、読み取り器は正当であることを確かめる識別番号を蓄積する。それ故、工程７２０の後に、読み取り器は１つの確かめられる正当な識別番号を有し、１つ以上の潜在的に正当な識別番号をも識別し得る。この記載を通して、確かめられる正当な識別番号は読み取り識別番号として言及される。
【００７０】
工程７３０において、読み取り器は、読み取られる識別番号およびいずれも潜在的に正当である識別番号に対する誤り検出符号値を計算する。
【００７１】
工程７４０において、その後、読み取り器は、タグから受信される誤り検出符号値が計算された誤り検出符号値のいずれかに一致するかどうかを判断する。
【００７２】
工程７４５において、一致が発見される場合、操作は工程７５０に進む。工程７５０において、関連するタグの識別番号は正当な識別番号である。工程７４５において、一致が発見されない場合、操作は工程７６０に進む。工程７６０においては、正当な識別番号が識別されず、必要ならば、次の読み取り処理が実行され得る。
【００７３】
当業者に理解されているように、方法７００の様々な実行は本発明の精神や範囲から離れることなく使用され得る。図８は、本発明の実施例による複数の処理を用いるフローチャート７００の１つの潜在的な実行のフローチャート８００を示す。
【００７４】
フローチャート８００は、読み取り器がタグ１０２又はタグの集合１２０と通信を始める場合、フローチャート８００は工程８１０で始まる。工程８２０では、読み取り器はタグの集合から１以上の応答を受信する。
【００７５】
工程８２５において、読み取り器は”０”記号および”１”記号の両方が受信されたかどうかを判断する。両方とも受信された場合、読み取り器は現在のビット位置がノイズによって潜在的に汚染されたことを確かめる。本発明の代替的な実施例では、読み取り器は、ビット位置が汚染されるかどうかを判断するために記憶装置に記憶された付加的なノード情報をも使用し得る。いずれか一方の実施例では、読み取り器がビット位置がノイズによって潜在的に汚染されることを判断する場合、操作は工程８４０へ進む。
【００７６】
１つの記号のみが受信された場合（又は読み取り器がビット位置が汚染されないと判断する場合）、操作は工程８３０へ進む。工程８３０では、読み取り器は、現在のビット位置で読み取り識別番号中の受信される記号を蓄積する。
【００７７】
工程８３２において、読み取り器は誤り検出符号処理が存在するかどうかを判断する。誤り検出符号処理は、単一の潜在的な識別番号に対して誤り検出符号アルゴリズムを実行する論理である。このようにして、潜在的な識別番号それぞれに対して１つの処理が存在する。１以上の処理が存在する場合、操作は工程８３４へ進む。
【００７８】
工程８３４において、読み取り器は、それぞれの処理で使用されている識別番号中の次のビットとして読み取られた記号を蓄積する。それぞれの誤り検出符号処理は唯一の識別番号を使用することは注目すべきである。誤り検出符号処理が存在しない場合、操作は工程８５０へ進む。
【００７９】
工程８４０では、読み取り器は受信されたどのビットが正当であるかについて判断を行う。一度判断がなされると、工程８４０において、選択されたビットは現在のビット位置で読み込まれた識別番号のビットの流れの中に蓄積される。
【００８０】
工程８４２では、読み取り識別番号ビットと一致する前のビットを有する潜在的な識別番号および現在のビット位置における他の記号をもって、新たな誤り検出符号処理を始める。
【００８１】
工程８４４において、読み取り器は誤り検出符号処理が存在するかどうかを判断する。もし、１以上の処理が存在する場合、操作は工程８４６に進む。工程８４６では、読み取り器は存在するそれぞれの処理において使用されている識別番号中の次のビットとして１つの記号を蓄積する。工程８４４においては、処理が存在しない場合、操作は工程８５０に進む。
【００８２】
工程８４８において、読み取り器はそれぞれの存在する処理に由来する新たな処理を始める。それぞれ新たな処理は親処理の識別番号に一致する前のビットおよび現在のビット位置における他の記号をもつ識別番号を有する。
【００８３】
工程８５０において、読み取り器は完全なタグの識別番号が蓄積された（読み取り識別番号として明細書中に言及される）かどうかを判断する。読み取り識別番号が完全でない場合、操作は工程８５２に進む。工程８５２では、読み取り器は通信を続ける。読み取り識別番号が完全である場合、操作は工程８５４に進む。
【００８４】
工程８５４において、読み取り器は蓄積された読み取られたタグ識別番号に対する誤り検出符号値を計算する。代替的な実施例では、読み取られたタグ識別番号に対する誤り検出符号計算はタグと読み取り器の通信と同時に起こる。
【００８５】
工程８５５において、読み取り器はタグから受信される読み取り誤り検出符号値と計算された読み取り誤り検出符号値およびいずれの誤り検出符号処理の結果との一致を試みる。工程８６０では、一致が発見される場合、操作は工程８６２に進む。工程８６２では、計算される誤り検出符号値に関連する識別番号は正当なタグの識別番号として識別される。工程８６０では、不一致が発見される場合、操作は工程８６４に進む。工程８６４では、その後、正当でない識別番号が発見される。工程８５５と８６０は別個の工程として記載されるが、それらは同時に実行され得る。次に示す工程８６２と８６４では、読み取り器は通信を再開し得る。
【００８６】
フローチャート７００の代替的な実行において、読み取り器は、潜在的に汚染されたそれぞれのビット位置を記憶装置に記憶し得る。読み取り器が完全なタグの識別番号を蓄積した場合、読み取り器は読み取り識別番号および汚染されるビット位置に対応するそれぞれの潜在的な識別番号に対する誤り検出コードを計算し得る。その後、正当なタグの識別番号を識別するために計算される誤り検出符号値と受信された誤り検出符号値を比較する。
（４．結論）
本発明の様々な実施例を上記したが、それらは単なる例示の方法によって示されたのであり、限定ではないということを理解すべきである。当業者には明らかであるように、形式および詳細において様々な変形が本発明の思想および範囲から逸脱することなくここでなされ得る。このように、本発明の広さおよび範囲は上記される例示的な実施例のいずれかによって限定されるべきではなく、請求の範囲およびそれらの均等物に基づいてのみ定義されるべきである。
【図面の簡単な説明】
【００８７】
【図１】図１は、本発明の実施例により１以上のタグの読み取り器が１以上のタグと通信する環境のブロック図である。
【図２Ａ】図２Ａは、本発明の実施例による１以上の読み取り器と１以上のタグ相互間の通信の構造上の概観を示すブロック図である。
【図２Ｂ】図２Ｂは、本発明の実施例による例示的な読み取り器のブロック図である。
【図３】図３は、本発明の実施例による、一致するそれぞれのノードに関連する情報を持つ例示的な２進木の図である。
【図４】図４は、本発明の実施例による、読み取り器の見通しから重みを付ける横断路を用いる読み取り呼出し動作のフローチャートである。
【図５Ａ】図５Ａは、本発明の実施例に基づいて次の読み取りビットを判断するための方法を示すフローチャートである。
【図５Ｂ】図５Ｂは本発明の実施例に基づいて次の読み取りビットを判断するための代替方法を示すフローチャートである。
【図６】図６はノイズによって汚染されたビット位置をもつ例示的なタグの図である。
【図７】図７は本発明の実施例によりタグを識別するために誤り検出符合を用いる方法を示す。
【図８】図８は本発明の例示的な実施例によりタグを識別するために複数の誤り検出符合を用いる方法を示すフローチャートである。
【図１】
2006503502.tif 000004
【図２Ａ】
2006503502.tif 000005
【図２Ｂ】
2006503502.tif 000006
【図３】
2006503502.tif 000007
【図４】
2006503502.tif 000008
【図５Ａ】
2006503502.tif 000009
【図５Ｂ】
2006503502.tif 000010
【図６】
2006503502.tif 000011
【図７】
2006503502.tif 000012
【図８】
2006503502.tif 000013
【国際調査報告】
2006503502.tif 000014
2006503502.tif 000015