マルチユーザ・システムでデータ通信を行うための方法とデバイス
【課題】複数の送信元デバイスから情報を送信先デバイスに迅速に、かつ効率よく伝達するための改良された通信方法およびデバイス。
【解決手段】複数の送信元デバイス110、120、130が送信先デバイス100に情報を伝達可能であるようにする通信方法およびデバイスを開示する。送信元デバイスから送信先デバイス100に伝達される情報は、通常、2進数の電子製品コード「EPC」または識別「ID」情報の形をとる。データ・スクランブルおよびスクランブル解析、チャネル選択および送信、グループ送信の有効および無効設定、相関関係決定、および衝突緩和の手法を利用する。
【解決手段】複数の送信元デバイス110、120、130が送信先デバイス100に情報を伝達可能であるようにする通信方法およびデバイスを開示する。送信元デバイスから送信先デバイス100に伝達される情報は、通常、2進数の電子製品コード「EPC」または識別「ID」情報の形をとる。データ・スクランブルおよびスクランブル解析、チャネル選択および送信、グループ送信の有効および無効設定、相関関係決定、および衝突緩和の手法を利用する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、一般に、マルチユーザ・システムでデータ通信を行うための方法とデバイスに関する。
【背景技術】
【0002】
多くの用途にとって、マルチユーザ・システムでデータ通信を行う高速で、効率がよく、信頼性の高い手段が望ましい。(複数の送信元から得られた)複数のデータを迅速に受信器で読み取る必要がある場合に、このような方法が求められる。このような技術の具体的応用の1つは、複数の品目の電子識別(electronic identification)で利用されている。
【0003】
電子識別産業は、リアルタイムの品目追跡および在庫管理を含む多数の商業および軍事用途にとって重要な産業である。電子識別機能を利用することにより、ある種の形態の製造、倉庫業務、流通、および小売に関する実質的にすべての予定計画を含む無数の予定計画において運用効率を大幅に高めることが可能である。正確なリアルタイム在庫追跡を迅速に、効率よく実行し得れば、商品の配置間違い、商品の在庫過剰または不足、および商品の盗難などさまざまな形態の無駄を大幅に減らすことが可能である。
【0004】
現在、電子識別産業は、複数の商品を識別するため、各商品に製品コードを割り当てる手動(光を使った)スキャニングに大きく頼っている。現在、米国の小売り業界全体では、万国製品コード(UPC)システムが広く使用されている。しかし、商品の手動スキャニングは、非常に時間がかかり、また人為的ミスもかなり発生する傾向がある。
【0005】
したがって、複数の送信元から受信器にデータを送信する効率がよく、信頼性が高い方法が必要である。
【特許文献1】米国特許出願第09/981031号
【特許文献2】米国特許出願第09/978890号
【特許文献3】米国特許出願第09/982271号
【特許文献4】米国特許出願第09/982279号
【特許文献5】米国特許出願第09/981476号
【発明の開示】
【発明が解決しようとする課題】
【0006】
本発明では、複数の送信元デバイスから情報を送信先デバイスに迅速に、かつ効率よく伝達するための改良された通信方法を開示する。
【課題を解決するための手段】
【0007】
説明する通信システムでは複数の手法を併用することにより、従来技術に勝る性能を達成する。本発明によれば、手動(光を使用した)スキャニングの排除およびスキャニング(または商品識別)速度の大幅高速化など、さらに特徴と利点を加えながらUPC交換の手段を利用し得る。さらに本発明では、多数の商品を同時識別することが可能であり、在庫、小売りの点検など非常に多くの用途がある。
【発明を実施するための最良の形態】
【0008】
類似の番号は類似の要素を示す付属の図を参照しながら、本発明を例としてのみ説明する。
本発明の好ましい実施形態では、一般に、一方向通信(送信元デバイスから送信先デバ
イスへ)を利用して、送信元デバイスの回路を簡略化しているため、送信元デバイスでは、受信器を使用する必要がない。
【0009】
送信元デバイスから送信先デバイスに伝達される情報は、通常、2進数の電子製品コード(「EPC」)または識別(「ID」)情報の形をとるが、いかなる方法であっても、これらの情報形式に限られるわけではない。電子遠隔計測(または他の種類の測定または割り当てられたデータ)などの他の種類の情報を伝達することも可能である。実際、本発明では、2進(または他の)数形式の表現を持つ情報を伝達することが可能である。
【0010】
図1に示されているように、情報は通常、1組の送信元デバイス110、120、130から単一の送信先デバイス100に伝達され、本発明の好ましい実施形態では、1組の送信元デバイス110、120、130から送信先デバイス100への同時情報通信を使用する。本発明には実施例の内容に応じてさまざまな応用があるので、わかりやすくするため、本説明全体を通して使用される用語を他の用語に置き換えて使用し得る。したがって、送信元デバイス、トランスポンダ、ユーザ、商品、タグなどの用語は、一般性を失うことなく以下の説明全体を通して置き換えて使用することが可能であり、また、送信先デバイス、システム・コントローラ、問合せ器(interrogator)、読取装置、受信器などの用語も一般性を失うことなく以下の説明全体を通して置き換えて使用可能であることにも注意されたい。
【0011】
本発明で採用する通信システムは、光通信、無線周波数(RF)通信、有線(接触)通信、静電結合通信、または誘導結合通信など数種類の通信形態140を包含することが可能である。本発明の好ましい実施形態では、タグ110、120、130と読取装置100との間の静電結合通信リンクを利用するが、他の形態の通信リンクも、制限されることなく利用することが可能である。
【0012】
本発明の以下の詳細な説明は、システムの重要な態様を説明する5つの主要な節とシステム操作の例を取りあげた最終節に分けられる。本発明の好ましい実施形態では、後述の重要な手法をすべて使用するが、他の実施形態では、説明した手法のサブセットのみを使用することが可能である。
【0013】
I.データのスクランブルとスクランブル解析
図2に示されているように、説明しているシステム内のタグ110により読取装置100に伝達されるデータ200は、後述のような測定されたデータまたは他のユーザ定義データなどさまざまな形をとることが可能である。本発明の好ましい実施形態では、伝達されるデータ200は、少なくとも1つの識別データ系列からなる。例えば、データ200は、96ビットの識別データを持つ少なくとも1つのEPCからなり、これについては、デビッドL.ブロック(David L.Brock)著「The Electronic Product Code」(MIT−Auto ID Center,January 2001)に概要が説明されている。EPC 200は、ヘッダ203、オブジェクト・クラス204、ベンダ・コード205、およびシリアル番号206により、システム内の各タグ(または商品)110を一意的に識別するために使用される。例えば、96ビットの情報により膨大な数の一意的ID(296〜8×1028、この数がいかに巨大であるかは、地球の質量が6×1027グラムであることからもわかる)が得られることに留意されたい。
【0014】
通常、ユーザ情報、誤り検査または訂正情報(例えば、前進型誤信号訂正(FEC)、巡回冗長検査(CRC)など)、およびその他の予約ビットなどの補足情報202が、好ましい実施形態のタグ110上に格納されているデータ200に付加される。補足情報(例えば、誤り検出または訂正データ)を後述のデータ・スクランブル工程の前後に追加す
ることが可能であるが、この補足情報をデータ・スクランブリングの後に追加した場合、さらに一様なランダム特性を持つことに注意されたい。
【0015】
当業者であれば、さらに複数の異なる情報形態(例えば、プログラム可能なタイムスタンプ、他のユーザ個人識別番号(PIN)、測定データ、環境データなど)も、予め定めて、タグ110、120、130に格納可能であることを理解するであろう。説明されているシステムのタグ110、120,130に格納されるデータの量または種類に制限は課されないことに注意されたい。
【0016】
タグ機能はすべて、通常は、複雑度の低い(即ち、低コスト)回路で実装される。タグ110上の回路を単純化するため、またシステム内のチャネル選択工程の性能を高めるため(以下で詳述する)、タグ110に格納する前に元のIDデータ200をスクランブルすることが非常に望ましい。これは、通常、タグ110にデータ230を格納する操作の前に実行されるランダム化またはスクランブル工程211により行われる。
【0017】
このスクランブル・アルゴリズム211は、通常、システム全体にわたって普遍的に適用され、EPCデータ200が、スクランブルされた後(220)、望ましい統計的(つまり、一様かつランダムな)特性を示すことが保証される。或いは、他の実施形態では、他のいくつかのスクランブル、暗号化、または番号付けアルゴリズムを格納されているデータ200に適用し、スクランブルされたデータ220を効果的に生成することができる。補足情報のプライバシーを守るため、個々の製造元は暗号化前処理210を任意選択で適用し得る。
【0018】
図3は、本発明の好ましい実施形態によりスクランブルされたデータ220をタグ110に埋め込むためのシステム例を示している。図3では、元のEPC 200は、メーカーなどの、EPCマネージャ310から通常の方法で得られる。その後、EPC 200が、スクランブラ(scrambler)330に入力され、このスクランブラにより、スクランブル・アルゴリズムが実行され、スクランブルされたデータ(S_EPC)220が出力される。次に、RFタグ・プログラマ/ライタ350により、スクランブルされたデータS_EPC 220がタグ110に埋め込まれる。スクランブルされたデータ220は、オリジナルのデータ200の修正版であり、今は、タグ110内に置かれている。
【0019】
図4は、多数のRFタグデバイス110、120、130から電子識別データ200を同時に読み込む高水準ブロック図を示している。この例は、通常棚卸しの際に棚に置かれている製品に関連付けられているタグを読み取る方法を説明している。作動すると、読取装置100は同時に、1組のタグ110、120、130を同時に起動する。その後、起動されたタグ110、120、130は、チャネル選択の基礎としてスクランブルされたタグ・データ220を使用して複数経路伝送アルゴリズムを続行する(以下の第III節で詳述する)。
【0020】
例えば、複数経路・アルゴリズムの第1経路で、S_EPC1の少なくとも一部(タグ110に埋め込まれている)を使用して、チャネルA 240を選択し、S_EPC2の少なくとも一部を使用して、チャネルB 240を選択し、S_EPCnの少なくとも一部を使用してチャネルC 240を選択する。チャネルA、B、およびC、またはそれらの任意の組み合わせは同じであることも、異なっていることもあり得ることに注意されたい。読取装置100は、復調アルゴリズムを続行し、最終的に、棚にあるタグ110、120、130のS_EPC 220を取得する。S_EPC 220は、スクランブル解析アルゴリズムを実行するスクランブル解析器460に送られ、そこで、タグ11、120、130のオリジナルのEPCデータ200が取得される。各タグに対応するEPCデ
ータ200は、読取装置100内に保持するか、または在庫報告書の形でオリジナルのEPCマネージャ310(例えば、メーカー)に送り返すことができる。当業者であれば、スクランブル解析オペレーションは、離れた場所に配置されているコンピュータまたはオンライン・サーバなど、他の場所で実行可能であることを理解するであろう。タグ110、120、130では、構造化の程度の大きいEPCデータ200の代わりに、EPCデータ220のスクランブル版の少なくとも一部を使用して、複数経路伝送アルゴリズムの各経路でチャネルを選択するため、図4のシステム内の衝突は最小限に抑えられる。スクランブルされたデータ220は、一様分布データにきわめてよく似ており、類似のEPC
200を持つ製品間の衝突は最小限である。複数経路伝送アルゴリズムおよびチャネル選択の詳細については、以下の第III節を参照し、衝突および衝突抵抗(collision resistance)の詳細については、以下の第V節を参照されたい。
【0021】
タグ110が伝送に使用するチャネルを必要としない限りタグ110と読取装置100との間で情報交換は行われない(後述)。したがって、本発明のスクランブルおよびスクランブル解析方法は、自己参照的でなければならない、つまりEPC 200をスクランブルするか、またはS_EPC 220をスクランブル解析する必要がある情報のみがデータである。
【0022】
本発明で説明されているシステムは、特定の重要特性を持つスクランブル方法を使用する必要がある。スクランブル方法は通常データ系列(EPCデータ系列など)を一様ランダム分布の特性を示す結果にマッピングするという重要な特性がある。好ましい実施形態では、このスクランブル方法は以下の2つの主要な特性を持つ。
【0023】
1.kを所定の整数とし、k進数で表される2つの通常のEPC 200を与えたとすると(例えば、典型的なEPC 200の対では、k進数の多く(すべてではないが)は同じである)、それらのEPC 200に対応するスクランブルされたS_EPC 220がn個の連続するk進数(チャネル割り当てを決定するためにタグ110で使用される)について一致する確率は約1/knである。
【0024】
2.kを所定の整数とし、スクランブルされた出力がn個の連続するk進数(チャネル割り当てを決定するためにタグ110で使用される)について一致するk進数で表される2つの通常のEPC 200を与えたとすると(例えば、典型的なEPC 200の対では、k進数の多く(すべてではないが)は同じである)、後続のm個のk進数(後続のチャネル割り当てを決定するためにタグ110によって使用される)は約1/kmの確率で一致する。
【0025】
2進数で表されているEPC 200の例では、これらの特性は、強いアバランシェ特性(strong avalanche property)に関係し、そのため、各出力ビットはすべての入力ビットおよび単一入力ビットの変更に左右され、平均して出力ビットの半分を変える。
【0026】
本発明では、図5に示されている再帰的方法を使用した問題の分断攻略によりこのスクランブルおよびスクランブル解析法を実行する。スクランブル・アルゴリズム510は、入力としてデータおよび長さ情報を受け取り、データの左側部分と右側部分を再帰的にスクランブルする。スクランブル解析アルゴリズム520は、スクランブル・アルゴリズム510の逆関数を実行する。再帰の基底(最終)レベルを除くすべてについて実行されるオペレーションは以下のとおりである。
【0027】
スクランブル方法510の場合:
1.1組のデータを第1の部分と第2の部分に分割し、
2.1組のデータの第1の部分に第1のスクランブル方法を実行して、データのスクランブルされた第1の部分を生成し、
3.1組のデータのスクランブルされた第1の部分で1組のデータの第2の部分を修正し、1組のデータの修正された第2の部分を生成し、
4.1組のデータの修正された第2の部分に第2のスクランブル方法を実行して、1組のデータのスクランブルされた第2の部分を生成し、
5.1組のデータのスクランブルされた第2の部分で1組のデータのスクランブルされた第1の部分を修正する。
【0028】
スクランブル解析方法520の場合:
1.1組のデータを第1の部分と第2の部分に分割し、
2.1組のデータの第2の部分で1組のデータの第1の部分を修正し、1組のデータの修正された第1の部分を生成し、
3.1組のデータの第2の部分に第1のスクランブル解析方法を実行して、1組のデータのスクランブル解析された第2の部分を生成し、
4.1組のデータの修正された第1の部分で1組のデータのスクランブル解析された第2の部分を修正し、1組のデータの修正された第2の部分を生成し、
5.1組のデータの修正された第1の部分に対し第2のスクランブル解析方法を実行する。
【0029】
上記のスクランブル510およびスクランブル解析520の両方法では、修正工程は、可逆であり、排他的OR(XOR)、剰余加算、剰余減算などからなるグループから選択される。さらに、第1のおよび第2のスクランブル/スクランブル解析方法は、スクランブル/スクランブル解析すべき1組のデータが所定の長さに達するまで、ステップ1から5までをそれぞれ再帰的に実行し、基底の場合を確立しなければならない。好ましい実施形態では、この所定の長さは1バイトである。
【0030】
1組のデータが所定の長さに達すると、所定の関数が実行される。この所定の関数は可逆であり、ルックアップ関数であるのが好ましく、好ましい実施形態では、置換ボックス(「S−box」)ルックアップ関数が実行される。分割攻略手法でデータの別々のビットをスクランブル/スクランブル解析するのは、ルックアップ関数を単に使用するのと比べて著しく効率が低いため、単一バイトで停止するのがよい。それより大きいサイズで停止すると、一般に、S−boxテーブルは非常に大きくなる。
【0031】
本発明の所定の関数には多数の望ましい特性がある。まず第一に、この関数は可逆でなければならない。スクランブル・アルゴリズム510は、S−boxルックアップ関数を使用するが、スクランブル解析方法520は、S−boxルックアップ関数の逆関数を使用し、この関数は、オリジナルのEPC 200を見つけられるように可逆である必要がある。実際の問題として、ルックアップ関数が可逆であるために、各エントリはちょうど1回だけ現れることになる。本発明では、S−boxへの入力は1バイトであり、出力も1バイトである。S−boxとその逆関数はそれぞれ、256バイトのデータを含む。
【0032】
所定の関数の第2の特性として、強いアバランシェ基準を示す、つまり、すべての出力ビットはすべての入力ビットに依存するという点があげられる。また、厳密アバランシェ基準(Strict Avalanche Criteria)(「SAC」)と呼ばれる追加特性があり、1つの入力ビットを変更すると、ちょうど50%の確率で各出力ビットが変化する。この特性は、本発明にとっては厳密に言うと必要ではないが、弊害があるわけではない。
【0033】
最後に、所定の関数は、低いdpmaxを示す。dpmaxの値は、ルックアップ・テ
ーブルのXOR行列内のエントリの最大値である。XOR行列内の(i,j)エントリは、fをルックアップ・テーブルとし、f(a)^f(a^i)=jとなるような0<a<256の範囲の数である。低dpmaxという特性だと、テーブルの繰り返し反復を使用した場合に、良好なミキシング(good mixing)が継続するが、これは基本的に、本発明のケースに当てはまる。このようなルックアップ・テーブルは、暗号法で検索されることが多い。例えば、高度な暗号化標準(「AES」)暗号アルゴリズムでは、SAC以外のすべてを満たすテーブルが使用され、本発明ではうまく機能する。このテーブルを再利用することで、本発明で説明している用途に無関係の他のシステム機能にAESも使用された場合にコード領域を節約することも可能である。
【0034】
図6は、別々のコンポーネントに展開されるスクランブル工程のブロック図を示している。図6に示されている実施形態では、この工程への入力は、128ビット(または16バイト)のEPCデータ200である。このEPCデータ200は細分され、別々のバイトP0からP15とラベル付けされる。スクランブル(またはスクランブル解析)の工程は、図6の左上から開始し、一番左の2つのバイト(P15とP14)が「MixBytes」ブロック610に入力される。「MixBytes」ブロック610は、「S」というラベルが付いているS−boxルックアップ関数602および608、および「○+」というラベルが付いている排他的ORオペレーション606および604からなる。ブロック図を下ってゆくと、次のステップは、次の2つのバイト(P13およびP12)と「MixBytes」ブロック610の出力との排他的OR 624をとることである。その後、このアルゴリズムは、排他的OR関数622、626、628、632、634、636、642、644、646、648、652、656、および658を使用してデータを連続的に組み合わせ、最終段で出力バイト220(C0からC15まで)が出現するまで関数620、630、640、650、660、670、および680を使用してバイトを混合するというように進む。好ましい実施形態によれば、この工程全体において、全部で16個のS−boxルックアップ・オペレーションと64個の1バイト排他的ORオペレーションが必要である。
【0035】
上述のスクランブル工程に加えて、さらに、万能スクランブル・アルゴリズムを適用する前に(例えば、タグ110をプログラムする前に)データ200を暗号化し(210)、さらにデータ機密保護を確実なものとすることが可能である。このタスクに使用し得る技術において、さまざまな暗号化アルゴリズム(例えば、AES、データ暗号化規格、国際データ暗号化アルゴリズムなど)が知られている。このように機密保護レベルを高められることは、プライバシーが重視される用途(タグに機密にすべき医療または財務データが含まれる可能性がある用途など)の面から重要である。
【0036】
II.パワーオン方式
好ましい実施形態の範囲に収まるタグ110のブロック図が図7に示されている。静電結合システムでは、アンテナ701は、導電性電極(例えば、容量性の板(capacitive plates))の対であるが、一般には、電磁場からエネルギーを回路内に結合する任意の方法とすることが可能である。タグ110に結合されている読取装置100から取り出される交流(「AC」)電力は電力変換装置703内で整流され、得られた直流(「DC」)はタグ110への給電に使用され、またタグ・エネルギー・モニタ704としても使用され、これによりさらに、通信が可能になる(それらの要素については後述する)。状態コントローラ705は、タグ・データ220および通信チャネル選択ブロック240上で動作し、送信情報を出力し、これは、チャネル変調装置708の制御の下で伝送素子702(当業でよく理解されている負荷変調素子など)に適用される。
【0037】
各タグ110に格納されるデータ220は、通常、低複雑度(つまり、低コスト)回路内に格納され、読取装置100からの問い合わせに応答する。各タグ110、120、1
30は、通常、第1の所定の条件が満たされるまで待ち、達した後、本発明によりその情報を複数経路アルゴリズムで伝達する。第1の所定の条件は、通常、タグ110、120、130のそれぞれについて同じに設定されているが、他の実施形態ではランダムに選択したり割り当てたりすることも可能である。タグ伝送状態を示す一般的流れ図の例を図8に示す。この流れ図では、さまざまな測定基準により第2の所定の条件を満たすことが可能である(例えば、第1の所定の条件を満たすことが不可能になったか、または第2の所定の条件が満たされた場合)。
【0038】
好ましい実施形態では、読取装置100は離れた場所からタグ110、120、130に給電し、タグ110の瞬間受電力レベルが所定の閾値(一般に703および704により決定される)を超えたときに第1の所定の伝送状態に達する。図9は、この動作の流れ図であるが、T1およびT2は第1および第2の電力レベル閾値を表す。当業者であれば、本発明の精神から逸脱することなく、他の所定の条件(特定の同期パルスまたは疑似ランダムな休止など)を使用する実装を採用可能であることに注意されたい。(受動的タグについては離れたところにある読取装置100から、または能動的タグについては内蔵電源により)タグ110に電力が届くと、タグ110は、受信信号強度を連続的に監視し、伝送の開始時期を判別する。タグ110がデータの変調および伝送250を開始すると、タグは完全に起動する。システムの好ましい実施形態において、複数のタグ110、120、130は通常、指定時間に完全に起動する。
【0039】
グループ内の完全に起動したタグは、第2の所定の伝送状態に達するまで、その情報を複数の経路(後述する)で送信する動作を続け、達したら、データ伝送を停止する。タグ・エネルギー・モニタ704により観察されたようなタグ110の受信電力レベルが第1の所定の閾値よりも下がるか、または通常は第1の所定の閾値よりも高く設定されている第2の所定の閾値を超えた場合に、好ましい実施形態における第2の所定の伝送状態に達する。
【0040】
このようにして、第1および第2の所定の伝送状態は、タグの各グループが通常、完全に起動する、ある範囲の受信電力レベル(例えば、枠(window))を形成する。本発明の好ましい実施形態では、パワーオン範囲(power−on range)は通常、約3dBの幅であり、タグ110、120、130は1〜2X(ある正規化された受信動作電力レベルに関して)の範囲の電力に応答する。この給電枠(powering window)により、一般的に、タグの伝送は比例して狭くなる電力枠(power window)内に収まり、したがって、(例えば、非直交拡散符号を使用するスペクトル拡散システムのように)一部の通信システムに影響を及ぼす通常の遠近問題が緩和される。
【0041】
好ましい実施形態では、システム内のタグ110、120、130はすべて、通常、同じパワーオン範囲を割り当てられるが、他の実施形態も可能であり、プログラム可能(例えば、事前割り当てされているが、異なる場合がある)またはランダム・パワーオン状態を利用するものなどがある。このような例の1つは、異なるメーカーに異なるパワーオン範囲レベルが割り当てられている場合に生じることがあり、異なるメーカーの製品同士を何らかの形で分離する(または区別する)。
【0042】
説明しているシステムのさらに他の実施形態では、双方向通信機能を持つタグが存在する場合があり、その場合、第1および第2の所定の伝送状態は、ある種の同期パルスまたはその他の信号送出情報からなる。所定の伝送状態がランダムである場合、タグ110上で、またはタグ110のプログラム時に、ランダムに決定可能である。今度もまた、本発明の精神から逸脱することなく、これらの伝送制御の他の実装(例えば、同期信号、タグとの双方向通信など)も可能であることに注意されたい。
【0043】
図10に示されている実施例では、読取装置100は、コントローラ1001により本社から遠隔制御することが可能である装置であり、棚1005に据え付けられているアンテナ1004に伝送媒体1003を介して接続されている。物理的寸法が異なる物体1020、1021、1022において、タグ110、120、130がパッケージのさまざまな部分に配置されているため、読取装置100に関連付けられているアンテナ1004とタグ110、120、130に関連付けられているアンテナ701との間の結合がばらつくことになり、その結果さらに、タグの電子回路1012では異なる電力レベルが受信されることになる。システム内の読取装置のアンテナ1004とさまざまなタグ110、120、130との間の結合特性が異なるため、タグが異なれば、与えられた読取装置アンテナ励起レベル(つまり、読取装置送信電力レベル)に対する受信する電力レベルも異なる(範囲境界線1030と1031により示されている)。さらに、さまざまなタグ110、120、130が異なる読取装置送信電力レベルで、したがって異なる時間に送信を開始するので、このような効果を利用して好ましい実施形態のシステム内に存在するタグの点数をおおよそではあるが減らすことが可能である。しかし、本発明の好ましい実施形態では、複数のタグ110、120、130はそれでも、通常は、特定の電力レベルに対し同時に伝送を開始することに注意されたい。例えば、識別する必要のある商品(タグ)が在庫中に1000点あり得、読取装置100は、1ステップずつ、10個の異なる可能な電力レベルを辿り、各電力レベルでおおよそ100個のタグからなるグループを起動することが可能である(ただし、それよりも少ないタグも、場合によっては、上限および下限の電力レベルで起動される)。本発明の他の実施形態では、複数のタグからの伝送は、送信する特定のタイムスロット(共通の基準に関して)をユーザが選択するタイムスロット化された(チャネル化)システムの場合などにのみ(必ずしも同時でないが)同期処理可能である。1実施形態では、読取装置100は、最低の送電力レベルからスタートして、1ステップずつ、すべての可能な送信電力レベルを辿ることに注意されたい。したがって、タグ110、120、130の特定のパワーオン範囲により、タグの各グループによる伝送の開始および終了を効果的に制御する。この態様は、特定のパワーオン範囲内(例えば、1030から1031の間)のタグ110、120、130のすべてが一意に識別されたときに読取装置100がそのことを判別し、そのときに、次の電力レベル(例えば、1031の上)に1ステップ進むか、または識別工程を終了することが可能である。
【0044】
他の実施形態では、読取装置100は、与えられた在庫プロファイル(inventory profile)に対するある範囲の予想電力レベルを「学習」つまり記憶し、活動の履歴とともに電力レベルに与えられる優先度とともにそのパワー・スイープ(power sweep)をアレンジすることが可能である。後述のように、読取装置100が、起動しているタグがない電力レベルに1ステップ進むと、その状態が感知され(通常は、短いエネルギーまたは変調検出測定を通じて)、次の電力レベルに迅速に1ステップ進み、タグの全読み取り時間を最小にする。
【0045】
III.チャネルの選択および伝送方法
複数の送信元(またはマルチユーザ)通信方法はすべて、本発明のようなある種のチャネル化方法を使用している。本発明では複数のチャネル化方法または手法のうちどれか1つを使用し得る。一般に、本発明で使用しているチャネル化方法は、直交チャネル化方法(orthogonal channelization methods)または疑似直交チャネル化方法(quasi−orthogonal channelization methods)の2つのカテゴリに分類可能である。
【0046】
直交通信チャネルには、選択したチャネル上の通信はリニア・システム内の他のチャネルの通信と(全く)干渉しないという利点がある(つまり、異なるチャネル間の相互相関は0と定義される)。疑似直交チャネルはほぼ直交し(例えば、異なるチャネルについて
相互相関値が0に近い)、通常は、直接系列符号分割多元接続(direct−sequence code division multiple access)(DS−CDMA)システムで使用され、その場合、各ユーザは通常、異なる拡散符号が割り当てられる。
【0047】
当業では、最大長リニア・フィードバック・シフト・レジスタ(linear feedback shift register)(「LFSR」))系列(つまり、m系列)の異なる位相(つまり、タイム・シフト(time shifts))の相互相関特性は低い(つまり、疑似直交する)ということがよく知られている。2つの揃えられていない系列の相互相関値は、−1/N(正規化)と定義され、NはLFSR疑似雑音(「PN」)系列の長さである。同じ基底のm系列の異なる符号位相は、符号分割多元接続システムの異なるユーザをチャネル化するために使用されることが多い。PN系列内の各シンボルまたはビットは、通常、当業でよく知られているように、「チップ」と呼ばれる。
【0048】
直交チャネル化関数の例として、Walsh関数、スロット化システム内のタイムスロット、周波数分割システムにおける周波数、特別に補強されたPN符号などがある。疑似直交チャネル化関数の例としては、上述のようなm系列またはPN系列がある。
【0049】
特別に増大されたPN符号の例として、時間的整合をとった(つまり、同期した)人為的に挿入された0がチャネル上に同じ時間オフセットで現れ、その結果同じm系列の異なる符号位相間の相互相関値が0となるように、系列の中に(符号の位相に応じて系列内の異なる位置に)人為的に挿入された(つまり、LFSRの通常の操作で生成されていない)2進値0を持つものがある。本発明の好ましい実施形態では、同期しているシステムにおいて、これらの特に増大されたm系列(生成の仕方は図11に示されている)を使用して直交符号チャネルを取得することに注意されたい。使用したスペクトル拡散手法の他の利点として、通信技術ではよく知られているように、干渉に対する抵抗(処理または拡散利得とも呼ばれる)も得られる。工場への設置など苛酷な電磁環境では、このような手法を適用することが重要である。
【0050】
上述のように、説明しているシステム内のタグ110、120、130によるデータ送信では、複数経路アルゴリズムを利用する。複数経路伝送アルゴリズムは、タグ110、120、130の全読み取り時間を決定する際に重要なものであり、複数の異なる態様からなる。このアルゴリズムで採用している一般的な考え方は、各タグ110、120、130は各アルゴリズム経路で通信用に特定の(好ましくは一様ランダム)チャネルを選択するというものである。
【0051】
説明しているシステムの好ましい実施形態では、チャネル選択240は、通常、タグ110に格納されているデータ220に直接基づいている。その後、通常、タグ110は情報(つまり、識別データ)を好ましい実施形態では選択したチャネル上でアルゴリズムの次の経路になるまで送信し、次の経路で、新しいチャネルを選択し、工程を繰り返す。本発明の好ましい実施形態では、(第1の所定の条件によって)タグの伝送はおおむね同期していると仮定される。
【0052】
各タグによるチャネルの選択は、所定の情報に基づく(つまり、通常実施形態ではタグ・プログラミング230で、または場合によってはタグ自体の設計で決定される)。本発明の好ましい実施形態では、各タグ110のチャネル選択は、(以下で詳述するように)タグ110に格納されている識別データ220から直接(アルゴリズムによる方法で)決定される。さらに、他の実施形態では、上記の所定の情報はタグ110に格納されているデータに直接は基づかない乱数を含むことが可能であることに注意されたい。
【0053】
上の第I節で詳しく説明したように、本発明の好ましい実施形態では、適切なシステム性能を実現する鍵として、タグ110上に格納する(230)前に、データ200(例えば、EPC、CRCなど)の少なくとも一部をあらかじめランダム化(またはスクランブル)する必要がある(211)。タグ110では本質的に、格納されているデータ220、またはその一部(例えば、221、222)を使用し、複数経路アルゴリズムの各経路で通信チャネルを選択するので(240)、総合的システム性能を最大にするためにデータ220が一様ランダムのように見えることが重要である。これは、上の第I節で詳述した低複雑度の可逆スクランブル・アルゴリズム211を通じて実現される。
【0054】
特に、図12に示されているように、好ましい実施形態の複数の伝送経路のそれぞれでのチャネル選択工程240は、事前にスクランブルした(つまり、ランダム化され格納されている)データ220の所定の部分集合(例えば、221、222、223、224)を利用して各経路内の通信チャネル240を選択することにより実行される。整流器または多重化デバイス1240などのチャネル・セレクタ1220は、通常、チャネルを選択する。タグ220に格納されているデータの新しい部分集合221、222、223、224(つまり、新しく乱数を引く)は、通常、アルゴリズムの後続のそれぞれの経路でチャネル選択に使用され、複数経路伝送アルゴリズム全体を通してチャネルをランダムにかつ独立に選択することが可能である。
【0055】
タグ110は、各アルゴリズム経路でデータ220のすべてを送信するか(好ましい実施形態など)、またはデータの一部のみを送信することが可能である(つまり、一般に、次の経路でタグによって使用されるチャネルを決定可能なだけの十分なデータが送信される)ことに注意されたい。通常、アルゴリズムの各経路のチャネル選択に使用されるデータの一部221、222、223、224は、データ220の一意的な連続するセクションであり、好ましくは事前にランダム化される。複数経路伝送アルゴリズムの複数の経路に対するチャネルの特定の選択のことを、「チャネル選択プロファイル」と呼ぶ。
【0056】
例えば、128ビットの事前にスクランブルされた識別データ220が各タグに格納されるシステムでは、8ビットの一意的ではあるが順次連続するセクションを使用して、16(つまり、128/8)のアルゴリズム経路のそれぞれにおける256(つまり、28)のチャネルの1つを選択することが可能である。したがって、各タグに対するデータの第1のランダム化されたバイト(例えば、221)により、アルゴリズムの第1の経路上でそれぞれ各タグの通信チャネルを選択し(240)、各タグに対するランダム化されたデータの第2の(および望ましくは異なる)バイト(例えば、222)を使用して、アルゴリズムの第2の経路上で伝送用のチャネルを選択し(240)、というように続ける。この複数伝送経路工程は、タグに格納されているデータすべてが尽きるまで(例えば、この例では16番目の経路が完了するまで。図2では、これは224に対応する)、または読取装置100がタグに伝送停止を指示する信号を送信するまで(一般に、上述のように704(1210)で第2の所定の条件が満たされることによりタグ110で感知される)続行する。データが尽きたら、任意選択により工程全体を繰り返すことが可能であるが、通常はタグは同じ(決定論的な)チャネルを選択する。不可避的に発生する衝突をランダム化するために各タグについて各アルゴリズム経路に対しランダムな一意的に決定されたチャネルを選択することが望ましいことにもう一度注意されたい(詳細については以下の第V節を参照)。
【0057】
もちろん、当業者であれば、データの他の(例えば、非連続または完全には一意でない)セクションを使用して、各経路の通信チャネルを直接的にまたは間接的に選択することが可能である。このようにして、実質的に制限なしで、チャネル選択の繰り返しの前に最大数のアルゴリズム経路を拡張することが可能である。ある回数の伝送経路の後にチャネル選択プロファイル(またはチャネル選択アルゴリズム)を修正し、同じデータ220の
異なる部分集合を後のチャネル選択1220に使用することが可能である(パターンの反復が発生する前に一意的なチャネル選択を拡張するため)。例えば、複数経路伝送アルゴリズムの16経路の後、チャネル選択データ(つまり、所定のデータ)を4ビット(上の例で)だけシフトすることで、アルゴリズムの後続の経路に対する新しいチャネル選択に達するようにすることが可能である。このようにして、タグ回路の複雑度は増すが、実質的に制限なしで、一意的なチャネル選択の数を増やすことが可能である。
【0058】
チャネル選択アルゴリズムのさらに他の実施形態では、ある種のマッピング(一般的には、1対1ルックアップ・テーブルまたはその他の代数または論理)関数を適用して、タグ上に格納またはプログラムされている(一般的には制限されている)データからチャネル選択を決定することも可能である。チャネル選択工程で重要な唯一の特性は、チャネル選択は、タグ内のデータに関して情報の一部が知られていれば、読取装置100内で計算可能になるという点である。
【0059】
チャネル資源は限られているため(つまり、それぞれのユーザが複数経路通信アルゴリズムで選択可能であるチャネルの数が限られている)、不可避的に、送信側タグに衝突が生じることになる。衝突は、2つまたはそれ以上のタグが特定のアルゴリズム経路で同じチャネル上の通信を選択する場合として定義される。このような状況は、通常のシステム・オペレーションの下で予想される。例えば、25個のタグが64本のチャネル上で通信を行う標準的なケースについては、衝突が少なくとも1回発生する確率は、経路1回毎に99.6%である。これは、N本のチャネル上でM個のタグが通信している場合に、衝突が発生しない確率に対する式は、
【0060】
【数1】
#1 P{衝突なし}
であるという事実に基づく。
【0061】
タグ伝送衝突のいくつかの数値例とその対策について、以下の第V節「衝突緩和方法」で説明する。
多くの場合、システム内に存在するタグの数(特定のパワーオン・レベルの)は、利用可能なチャネルの数を超えることすらありえる(特に、好ましい実施形態のアルゴリズムの始めのほうの経路で、または利用可能なチャネルの数が後述のように低く設定されている場合)。このような状況は、本発明では、直交チャネル化手段を使用した場合に完全に許容可能であるものである。通常のDS−CDMAシステム(疑似直交チャネル化符を使用する)は、その時点で過負荷になっていると考えられ、信頼し得る通信はいっさい行われない可能性があることに注意されたい(特に、タグの伝送特性について詳しい情報がない場合)。説明されているシステムでは、アクティブにされたタグ母集団は、以下の第V節で詳しく説明している、衝突緩和手法によりさらに効果的に減らすことが可能であるということが重要である。
【0062】
また、本発明の好ましい実施形態では、複数経路伝送アルゴリズムの1経路当たりさまざまな個数のチャネル(221、222、...224により一般に決定される)を使用し、総合的システム性能(例えば、全読み取り時間、全システム容量、信頼性など)を改善することもまた重要なことである。つまり、複数経路伝送アルゴリズムの一方の経路で利用可能なチャネルの個数は、伝送アルゴリズムの他方の経路で利用可能なチャネルの数
と異なる可能性もあるということである。アルゴリズム経路当たりの(つまり、単位時間当たりの)チャネルのさまざまな個数は、この説明では、利用可能なチャネルの個数は時間により動的に変化するため動的チャネル・プロファイル(dynamic channel profile)と呼ばれる。動的チャネル・プロファイルを実装することで、本質的に、予想されるタグ母集団の全伝送時間(または全読み取り時間)が最適化される。
【0063】
アルゴリズムの各経路に対する伝送時間は通常、アルゴリズムのその経路に利用可能なチャネルの数に比例することに注意されたい(使用するチャネル化方法に関係しない)。複数経路伝送アルゴリズムの総伝送時間(TTX)は、
【0064】
【数2】
で表すことが可能であり、Lはデータを正常に送信するために必要な伝送経路の数、Rは伝送(信号送受信またはチャネル・シンボル)レート、Biは1パス当たり送信されるデータ・シンボルの個数、Niはアルゴリズムのi番目のパス(または拡散利得)で利用可能なチャネルの個数である。本発明の好ましい実施形態では、Lは16経路と大きく、Biは128ビットに固定され、Rは62.5KHzに等しく、特定のNi値は上の例で与えられた値であるが、これは、システムの1つの特定の実施形態にすぎないことに注意されたい。1経路当たりの使用可能なチャネルの個数(Ni)は、以下のように(240にも示されているように)一般に、各経路(ni)内の通信チャネルを選択するために使用されるビットの数に依存することに留意されたい。
【0065】
【数3】
システムの好ましい実施形態では、Niは1経路当たりの利用可能な符号位相の拡散利得および個数を表し、Rは毎秒チップ数単位の信号送受信レートである。高度な衝突緩和手法(以下の第V節で説明している)を適用することにより、タグ110、120、130からの伝送経路の必要な個数(L)を大幅に減らすことが可能であることに注意されたい。一般に、説明しているシステムの他の実施形態では、上の式の中の値に制限はない。
【0066】
1経路当たりの伝送時間は図に示されている好ましい実施形態の1経路当たり利用可能なチャネルの数(およびシンボル・レート)に依存しているため、複数経路伝送アルゴリズムの前のほうの経路のより少ないチャネルを使用してシステムの全読み取り(つまり、取得)時間性能を高めることが可能である(このような場合システムにさらにチャネルを追加しても、タグが少ないためほとんどメリットはない)。アルゴリズムの後のほうの経路(潜在的には複数のステップ)でチャネル数を増やすことにより、より多くのタグがシステム内に存在するケースに対応することが可能であり、また読取装置100は、以下の第V節で述べているより高度な信号処理(例えば、高度な衝突緩和)手法を採用しない。
【0067】
このようにして、存在するタグが少ないシステムだと、(前のほうの)チャネル選択の数が多いシステムの伝送時間が長くなるというペナルティは、通常、発生せず、それと同時に、存在するタグが多いシステムでも、著しいペナルティが発生することもない(複数
経路アルゴリズムの前のほうの経路は通常、最初に利用可能なチャネルの数が少ないためかなり短時間になるため)。また、後のほうのアルゴリズム経路のチャネル選択数を増やすと、タグが多数存在するシステムは限られた数のアルゴリズム経路で確実にすべてのデータを正常に取得可能である(したがって、システムの信頼性が増す)。
【0068】
例えば、本発明の好ましい実施形態では、128ビットのデータ220を使用しており、第1と第2のアルゴリズム経路には32のチャネルがあり、3番目から6番目までのアルゴリズム経路には64のチャネルがあり、7番目と8番目の経路に128のチャネルがあり、残り8つのアルゴリズム経路に1024のチャネルがある。ここでもう一度、この実施形態では、データ220の一意的な部分集合を使用して、各経路内の通史にチャネル1260を直接選択し(1220)、またデータの一意的な重なり合わない部分が尽きるまでに最大16のアルゴリズム経路が実行されることに注意されたい。本発明の他の実施形態では、所定の数の経路の後に変わる1伝送アルゴリズム経路当たりの可変個数のチャネルを使用することが可能である。例えば、上記の例の複数経路伝送アルゴリズムの第1の16の経路では、32〜256の利用可能なチャネルからのどの場所をも使用可能であり(つまり、チャネル選択データの5から8ビット)、次の16の経路では、256〜4096の利用可能なチャネル(つまり、8〜12ビットのチャネル選択データ)からのどの場所をも使用可能である。このようにして、実質的に制限なしで、動的チャネル・プロファイル(または、1アルゴリズム経路当たりの利用可能なチャネルの数)を拡張可能である。またここでも、データの重なりあう部分または交互配置されている部分を利用してチャネル選択アルゴリズムを駆動することにより経路の最大数を増やすことが可能であることに注意されたい。
【0069】
このシステムの特定の実施形態における1アルゴリズム経路当たりの利用可能なチャネルの個数(動的チャネル・プロファイルともいう)の実際の選択は、さらに(システム内に存在するタグの予期された個数に加えて)読取装置100で使用される信号処理アルゴリズムの予期された種類または主要な種類(衝突緩和アルゴリズムの種類など)によって異なる。1アルゴリズム経路当たりのチャネルの数はさまざまなので、チャネル・プロファイルは後のほうの経路で減少することがあることに注意されたい。一般に、時間に応じて変化するチャネル・プロファイルは、本発明の目的に関して、動的チャネル・プロファイルと考えられる。
【0070】
特定のタグ110のチャネル・プロファイルは必ずしも、読取装置100によりアプリオリに知られていなければならないわけではないが、一般的には、そういう場合があることに注意されたい。タグ110のチャネル・プロファイルが知られていないと、読取装置100では、例えば(場合によっては、自己相関またはスペクトル特性を測定して)PN(チッピング(chipping))系列の周期を確認し、それに応じて動作(復調)するようにしなければならないであろう。
【0071】
特に、本発明の好ましい実施形態では、ランダムなチャネル選択を使用し、複数パス伝送アルゴリズムの各経路で特定の拡散符号(または1220で符号チャネル)を選択する。さらに具体的には、好ましい実施形態では、タグ110に格納/プログラムされているデータ220の一部を使用して、長さNの特に増大されたm系列の時間オフセット(または1220のように符号位相)を直接指定する(ただし、Nは上述のように、特定のアルゴリズム経路のチャネルの数に等しい)。この工程の概略が、図11に示されている。PN系列の異なる位相は、一般に、2つまたはそれ以上のm系列の2を法とする総和を効果的に計算し、同じm系列の第3の符号位相を出力する、PN生成器(LFSR)状態のマスク関数(またはAND−XORリダクション・ネットワーク(AND−XOR reduction network)1100)を適用することにより得られる。したがって、タグ110、120、130の伝送のすべてが知られている基本初期生成器状態に同期
するように、タグ110、120、130ではすべて、各アルゴリズム経路内で、同じ初期生成器状態から始まる、同じ基本LFSR(m系列)生成器を使用する。これらの態様は、以下の第IV節で説明しているように、読取装置100で素早い効果的復調を行ううえで重要である。基本LFSR系列生成器の長さ(つまり、プリミティブ多項式)は、通常、上述のように、1アルゴリズム経路毎に動的に変化する(チャネルの数が変わる)ことに注意されたい。
【0072】
従来のm系列生成器は、通常、好ましい実施形態において第1のチップ(またはPNビット)時間について0出力を強制することにより、特別に増大されたPN系列生成器になり、異なるタグからの系列の相互相関は与えられた系列周期にわたって必ず0になる。また、他の時点に強制的に0を符号系列に入れると、直交する系列が出力され(他のシステムと同様)、他の実施形態では他の種類の直交関数生成器をLFSR PN生成器(例えば、WalshまたはHadamard関数)の代わりに使用することも可能であることに注意されたい。その後、タグ110に格納されているデータ220は、従来の手段1230を使用し、生成された拡散符号1260により拡散される(例えば、当業者であればよく知っているように、デジタル実装ではXORゲート、またはアナログ実装では除算器)。次に、アクティブにされたタグの拡散データ信号は、与えられた通信チャネル上で(まとめて)送信される。
【0073】
タグはデータの送信にある範囲の変調タイプを使用することも可能であることに注意されたい(例えば、振幅変調、位相変調、周波数変調、またはそれらの組み合わせ)。本発明の好ましい実施形態では、伝送要素702を介して負荷変調からある形式の振幅偏移変調(「ASK」)を使用するが、他の変調タイプおよび実装も確かに可能である(例えば、差動直交位相偏移変調、直交振幅変調、パルス符号変調、パルス振幅変調、パルス位置変調など)。本発明では、さまざまなデータ符号化およびマッピング手法を使用することも可能である。符号化手法の例として、ゼロ復帰(RZ)、非ゼロ復帰(NRZ)、マンチェスタ、および差動符号化があり、当業ではすべてよく知られている。当業者であれば周知のように、本発明では、一般性を失うことなく、さまざまな種類の符号化、変調、符号および信号送受信を使用することが可能であることに注意されたい。符号手法の例としては、CRC符号、畳み込み符号、ブロック符号などがあり、これらもすべて、当業ではよく知られている。
【0074】
また、好ましい実施形態のタグ110、120、130は伝送要素702を介して読取装置100により供給される搬送波を直接変調するため、局部発振器はない(しかし、局部発振搬送波を使用することも、確かに、本発明の範囲内で可能であり、いかなる形でも応用を制限することはない)。本発明の好ましい実施形態では、電力変換装置703が読取装置100からの搬送波信号を整流し、読取装置100が離れた場所からタグ110上の回路に電力を供給する。能動的に電力を供給するタグを使用することも可能であり、いかなる形でも本発明の使用を制限することはないことに注意されたい。本発明の一般的な目標は、タグ110の複雑度を最低限に抑えることであり、好ましい実施形態の説明されている手法を使用することにより、タグ110の回路を最小に保つことが可能である。
【0075】
IV.高速復調方式
図13に示されているように、読取装置100は通常、送信レベル制御装置1320および増幅器1330により信号源1310の出力を初期化し、何らかの最小レベルの電力を送信することにより、タグ110、120、130の読み取り工程を開始する。好ましい実施形態では、次に、読取装置100はそのレベルの連続波の送信を開始する。読取装置100が特定の電力レベルで送信し始めると、通常、タグ110、120、130から戻る信号を監視する(結合デバイス1340およびアンテナ1345により)。この活動検出は、可能な通信チャネル(以下で詳述する)のそれぞれで信号レベルまたは信号振幅
を検出するなどの、変調またはエネルギー検出測定の形を取り得る。この測定期間は、可能な限り短くするのが望ましく、特定の電力レベルでアクティブにされているタグがない場合、読取装置100は迅速に、次の電力レベルに1ステップ進むことが可能である(一般的には、増加する方向で)。特定の送信電力レベルで信号が感知された場合、読取装置100は完全な復調処理1390を開始し得る(場合によっては、以下の第V節で説明しているように、衝突緩和手法を採用する)。システムの他の実施形態では、一般性を失うことなく、読取装置100は、変調された搬送波信号、同期パルス、または非同期搬送波形を送出することも可能である。
【0076】
読取装置100により実行される信号処理は、ハードウェアまたはソフトウェアアーキテクチャ、またはそれらの組み合わせにより実行し得る。代表的な実施形態として、何らかの選択性1365、増幅1370、アナログ・デジタル変換1375、およびDC取得および利得制御関数1380がある。一般に、読取装置100は与えられた送信経路内で可能な通信チャネルのそれぞれを巡回し(順次または同時)、それぞれに対する信号エネルギーを探索する。当業者であれば周知のように、信号の存在を検出し、衝突の有無を検出するための方法が多数利用可能であるが、それは変調および信号送受信の種類によってさまざまである。一般に、読取装置100はさらに、いくつかの実施形態では、搬送波信号の能動的または受動的抑制1360を実行し、干渉または雑音除去を行うことも可能である(システム内の望むタグ以外の発生源からの任意の形の干渉について)。
【0077】
上述のように、本発明の好ましい実施形態では、タグ110、120、130でスペクトル拡散変調を使用する。したがって、当業でよく知られているように、受信したデータは、まずそれぞれの可能な拡散符号を適用して書く符号チャネルについて読取装置100内で逆拡散しなければならない。
【0078】
より具体的には、本発明の好ましい実施形態ではタグ110内の拡散系列として特別に増大されたm系列を使用しているため、非常に高速で、効率がよく、新規性のある復調(つまり、逆拡散およびチャネル化)手法を、読取装置復調処理1390で利用することが可能である。これらの手法を使用すると、実質的に、読取装置復調処理1390内で必要な処理能力が低減され(例えば、好ましい実施形態では約57倍)、その結果、読取装置100の読み取り時間が短縮され、実装コストも低減される。処理に関する実際の節約がどれだけかは、複数経路システムの各経路内で使用されるチャネルの数によって決まり、これは、従来の逆拡散オペレーションの回数と1シンボル当たりの改善された逆拡散オペレーションの回数との比に等しい係数(F)に関して表すことが可能であり(受信系列の順序変更と高速Hadamard変換(FHT)の新規性のある組み合わせを使用して)、
【0079】
【数4】
Lは、送信元データを正常に復調するために必要な経路の数に等しく、Niは(ここでもまた)i番目の経路内のチャネルの数に等しい。この係数は、直接、読取装置復調処理1390内の処理の節約程度(通常は、毎秒100万回オペレーション(MOPS)または毎秒100万命令(MIPS)で表される)を表す。したがって、この例では、57倍能力が低い(例えば、10MOPS対570MOPSの)プロセッサ1390を、最良のケースの好ましい実施形態の読取装置100で使用することが可能である(後述のように衝突緩和はない)。
【0080】
特別に増大されたm系列(図11のボックス1120に示されている)は従来のPN系列の直交拡張であり、直交Walsh符号(図14のボックス1420に示されている)といくつか類似点がある、つまり、この2組の系列は同じ数の2進数の1と0を系列内に含むということに留意されたい。実際、この2種類の系列(つまり、特別に増大されたm系列およびWalsh系列)は単一の特別順序変更関数を使用して関連付けられている。この特別な順序変更関数は、図15の読取装置受信器ブロック1520内の基底m系列を(タグ系列生成器1110で示されているように)生成するために使用されるプリミティブ多項式から直接導かれる。この系列順序変更関数1510を使用することで、受信デバイス1375によるデータ・サンプル(または要素)の受信時にそれらのデータ・サンプル(要素)の順序を直接変更する。受信デバイス1375は、アナログ・デジタル・コンバータ、アナログ・サンプル&ホールド・デバイス、レジスタ、または信号を受信するその他のデバイスとすることも可能である。単一の系列順序変更1510関数は、複数の複合チャネル(または110のように符号位相)を使用する複数のタグ110、120、130からの伝送からなる複合受信信号に適用されることに注意されたい。
【0081】
メモリ・バッファ1530などの記憶媒体内で受信系列の順序が変更された後、これは、1組の有効なWalsh系列からの系列に類似しており、高速Hadamard変換(FHT)などの高速変換手法を使用し、すべてのデータ・チャネルについてタグ110からデータを迅速に(かつ同時に)(1540に示されているように)逆拡散することが可能である。FHTは、当業でよく知られているように、一揃いのWalsh符号に対するデータ系列の相関関係を(並行して)高速に求めるために使用される。本発明の精神から逸脱することなく、FHTに関係する変換(例えば、高速Walsh変換、Walsh−Hadamard変換、再帰的Walsh変換など)を説明した高速相関関係決定方法とともに使用可能である。また、説明している処理手法はすべて、アナログまたはデジタル信号処理の分野で実行することが可能であることに注意されたい。
【0082】
従来のFHTアルゴリズム(例えば、ボックス1410に示されているような)に関する文献は十分にあり、基本的なカーネル・オペレーション(ボックス1400、「バタフライ」と記されている)が図14に示されていることに注意されたい。基数2のFHTバタフライは基数2のFFTバタフライに似ているが、これは、データ要素と+1および−1の値だけの乗算(またはそれと同等の、データ値の加算と減算)からなる。8×8 FHTの格子構造1410も図に示されている。FHT 1550の各出力は、FHTビンまたはFHT符号チャネルと呼ばれる。FHTは高速変換なので、従来の相関を上回る処理の節約(上で表されている係数Fに似ている)はN点直交系列に対して(N2/N log N)に等しいことを証明することが可能である。この同じ節約は、説明した高速相関決定手法を使用して実現される。
【0083】
正確な受信データ順序変更関数1520は、タグのフィボナッチLFSR(1110に示されている)は通常オペレーション時に巡回する状態を観察することにより決定される(以下の例も参照)。LFSRが進行する状態は、着信(拡散)受信データ・サンプルを、時間内に(直線的に)受信されたときに受信データ・メモリ・バッファ(1530または他の記憶媒体)に格納しなければならない間接アドレスに直接対応している。この(1520内の)アドレスの系列は、受信器内で能動的に生成されるのではなく、記憶媒体(例えば、ランダム・アクセス・メモリ、読み取り専用メモリ、ハード・ディスク・ドライブなど)に交互に格納することが可能である。このようにして、受信したm系列(またはm系列の総和)の順序を変更し、Walsh系列内の要素(またはより具体的には、Hadamard行列内の行)を正確に表すようにする。したがって、従来の高速(Hadamard)変換(相関)方法を使用して(1540で)、受信データ・チャネルを並行して逆拡散することが可能である。このデータ系列はさらに、メモリ内にダブル・バッファ
リングし、処理待ち時間に合わせることが可能であることに注意されたい。
【0084】
信号エネルギーを示すFHTの出力インデックス(またはビン)1550は、タグ110、120、130のAND−XORリダクション1100で使用されたマスク値1130(2進数で表した場合)に直接対応する。例えば、チャネル選択符号1130(図11に示されている「c0−c4」)(送信器処理)は、図15のFHTブロック1540の能動的出力1550(受信器処理)に直接対応する。特定の符号チャネル(または符号位相)を選択するために、バイナリ・マスク値(binary mask value)1130がタグ110内で適用されることに留意されたい。これは図7にも示されており、マスク710はタグ・データ240からチャネル選択240へと描かれている。つまり、バイナリ・マスク値1130(およびFHTビン・インデックス(bin index))は、特定のパスでチャネルを選択するために使用されたタグ110に格納されているデータ221、222、223、224に直接対応している(タグ・データとチャネル選択との関係の補助的説明については図17および図18の識別子1710、1820、1830、および1840も参照)。各タグ110は、好ましい実施形態の複数パス・アルゴリズムの各パスの継続時間中にそのデータ220を固定されたチャネル1260で送信する。各FHTビンの出力信号レベルは、逆拡散後の各符号チャネル1260(例えば、符号位相毎に)上の信号レベルに直接対応する。以下で詳述するが、受信データ系列のチャネル選択部分での各アクティブなFHTビンの出力のデータ信号1550は、バイナリFHTインデックス値と照合することにより検証することが可能である(なぜなら、2つのデータ系列は有効データに対して照合すべきだからである)。この手法は、複数パス伝送アルゴリズムのパス#2について図18に示されている。第2のパスに対するチャネル240を選択するために使用される部分222上のデータ系列1820、1830、1840は、FHTビン番号に相当する2進値であることに注意されたい。
【0085】
図15に示されている順序変更とFHTの組み合わせた手法を使用することで、この復調器により好ましい実施形態の可能なすべての符号チャネル(つまり、符号位相)を高速復調(つまり、逆拡散)することが可能である。(それぞれの潜在的データ・チャネルおよびシンボルに対する必要な逆チャネル化および逆拡散オペレーションに対応する)受信器内の受信したシンボル期間毎にNチャネルを復調するために、通常、N点FHTが必要であることに注意されたい。また、トランスポンダ・システムの他の実施形態では、チャネル化関数に直交Walsh符号を使用することが可能であり、その場合、FHTビンはWalsh符号チャネル・インデックスに直接対応する(そして、順序変更工程は必要でない)。しかし、Walshチャネル化符号は周期的であり、周期的干渉源と高い相関関係を持ちうるため、好ましい実施形態と比較したときに、このようなシステムはそれほどよい干渉除去能力を持たない。したがって、このシステムの好ましい実施形態では、特別に増大したm系列をチャネル化関数として使用し、また上述の復調手法を使用する。
【0086】
例えば、タグ送信器内で長さ16(N=16、N=4)の特別に増大されたPN系列を使用するシステムでは、2進数「0001」(1)のチャネル選択値1130(ni)により表される系列1260は、「0111101011001000」であるが、2進数「1001」(9)のチャネル選択(マスク)1130により表される系列1260は「0010110010001111」である(これは、先行0でその後特別に増大されている同じ基本m系列の異なるタイム・シフトまたは符号位相にすぎない)。23(標準8進数表記で表した場合)のプリミティブ多項式のタグPN生成およびマスク回路の例が図11に示されている。2つのタグ送信器は、これらの系列を独立に通信チャネル上で送信するものと仮定されている。読取装置受信器は、(図15に示されているように)特別な順序変更関数1520およびFHT処理を使用してこれら2つの信号を解決する。送信されたPN系列に対し使用しなければならない特別な受信データ・サンプル順序変更は、この例では、{0,15,7,11,5,10,13,6,3,9,4,2,1,8,12
,14、1120で示されているのと同じ}である。この系列は、タグ110内で使用されるm系列生成器1110を複製し、PN生成器の状態を観察するか、または必要な順序変更系列を単にメモリに格納するだけで、読取装置100内で生成することが可能である。順序変更系列を使用し、間接アドレッシングにより、入ってきた受信データ・サンプル・ストリームをメモリに格納する。例えば、読取装置に届いた第1の有効なA/Dサンプルは、記憶媒体1530のメモリ・バッファのロケーション0に格納され(すべての特別に増大された符号の場合と同様)、第2のサンプルはメモリ・ロケーション15に格納され、第3のサンプルはロケーション7に格納され、というように続く。N(この例では16)個のサンプルが受信されると、メモリ・バッファ1530内で新規順序変更されたデータ・サンプルに対し通常のFHT処理1540を実行することが可能である。順序変更関数は、上記の「0001」PN符号を系列「0101010101010101」(Walsh符号1と同じ)に変換し、「1001」PN符号を系列「0101010110101010」(Walsh符号9と同じ)に変換する。FHT 1540は、信号エネルギーが出力1550のビン1(チャネル符号1に対応する)およびビン9(チャネル符号9に対応する)内に存在している(例えば、タグが送信中である)ことを示す。そこで、ビン1とビン9のFHT出力を送信シンボル毎に観察することにより、タグ・データの残りを感知することが可能である。
【0087】
上述の手法は、受信器内で、たとえそのような信号が実際に送信されなかったとしてもタグ110により送信された第1のチップ(またはシンボル)が2進数0(チャネル上の+1正規化信号値に等しい)であると仮定することにより、従来の(つまり、特別に増大されていない)m系列に対し使用することが可能であることに注意されたい。したがって、記憶媒体1530内の第1のバッファ・ロケーションは+1値に初期化され、処理(つまり、順序変更1510およびFHT 1540)は通常のように続行する。このようにして、従来のPN系列の複数符号チャネル(または符号位相)に対する相関関係を非常に高速に求めることが可能である。他の通常増大されているPN系列に対しても、追加チップ(例えば、上記の第1のチップ以外)が系列内に挿入される場所を追跡することにより受け入れることが可能である。
【0088】
上記の高速相関決定手法(つまり、特定の受信系列順序変更1510およびFHT 1540)を、AND−XORリダクション・ネットワーク1100により生成することが可能なPN系列(そのようなネットワークで生成されようとされまいと)を使用する通信システムに適用する。多くの普及している通信システムでは、これらの種類のPN系列、または従来のm系列の組み合わせから生成された系列を使用する(当業でよく知られているように、Gold符号など)。このようなシステムの例として、IS−95、IS−2000、3GPP CDMA携帯電話システム、およびGPS CDMA位置決定システムがある。上記の高速相関決定手法は、それらのシステム内でも等しく効果的である可能性がある。
【0089】
いかなる場合も(採用されている除去手法に関係なく)、複合受信信号は、受信器のフロントエンド1610内で濾波し、増幅してから、図16に示されているように読取装置100内でチャネル化(または逆チャネル化)1620しなければならない。その後、各チャネルは、一般に、信号および衝突検出を目的として別々に(ただし場合によっては同時に)処理される(一般的に1630)。例えば、説明しているm系列の代わりにWalsh符号を使用するシステムの他の実施形態では、上記のように、FHTオペレーションをそのまま使用して、異なるデータ・チャネルすべてを同時に復調することも可能である。システムの他の実施形態では、1バンク分の(並列または時分割方式の)従来の逆拡散器を(1540、1620の代わりに)使用して、逆チャネル化および逆拡散工程を実行することが可能である。逆拡散器は、当業でよく知られているように、通常、乗算器の後に積分およびダンプ関数を配置したものである。
【0090】
他の実施形態では、通信システムの他の例において、直交するタイムスロットをチャネルとして使用することが可能であり(スロット付きALOHAシステムなどで)、その場合、異なるタグからの信号は(別々の時刻に)到着するとともに復調される。後述のように、選択されたチャネル化方法では、読取装置100内に採用することが可能な一般的な種類の衝突緩和アルゴリズムを変えないことに注意されたい。
【0091】
また、すべてのタグが複数パス伝送アルゴリズムの第1のパスでその情報を正常に送信することは通常あり得ないため、本発明の多数の実施形態では、復調工程は一般に複数反復工程となっていることに注意されたい。したがって、読取装置100は、タグからのすべてのデータが正常に受信されるまで(後述の方法をさらに使用して)、電源オン状態のままにし(同じ電力レベルで)、着信データを継続的に復調しなければならない。さらに、高度な衝突緩和手法1630が読取装置100で使用されている場合(後述のように)、複数復調反復法(例えば、FHT)が、複数パス・アルゴリズムのパス毎に必要になることがある。また、複数パス伝送アルゴリズムの後続のパスでは、上記の動的チャネル・プロファイルの説明で説明されているように、新規に設定したチャネル数に復調器を合わせる必要があるかもしれないことに注意されたい。
【0092】
V.衝突緩和方法
上述のように、タグ110、120、130で読取装置100との通信に使用することが可能な通信チャネルの数は、この(および任意の)通信システム内では限りがある。通信チャネルの数は限られているため、また複数のタグ間に組織だった割り当てはないため(つまり、ランダムな割り当てが実際には使用されている)、説明しているシステムはタグからの送信に衝突が生じることは避けられない。衝突は、2つまたはそれ以上のタグが同時(つまり、複数パス伝送アルゴリズムの特定のパスで)に同じチャネル上で通信することを選択する場合またはイベントとして定義される。本明細書の第I節に示されているように、タグに格納されているデータは一様ランダム・データに非常に近いため、割り当ては実際にはランダムであることに留意されたい。
【0093】
説明しているシステムでは、読取装置100の望む複雑度に応じて、(後述のように)読取装置100の衝突緩和手法を使用することも、使用しないことも可能である。例えば、安価な受信器では衝突緩和手法を使用しない場合があるが、高価な(処理能力の高い)受信器では高度な衝突緩和手法を使用する場合がある。
【0094】
以下の概要説明では、まず特定の衝突緩和手法を使用しないことを仮定し、後から、衝突緩和手法を使用するケースについて調べる。タグ110、120、130は一般に、読取装置100で衝突緩和が使用されているかいないかに関係なく同じパターンを送信することに注意されたい。各タグ(例えば、110)は、実質的に、システム内に存在する他のタグ(例えば、120、130)からは認識されない。以下の追加ステップを実行すると、さらに、受信器内の復調工程が実行される。
【0095】
特に、好ましい実施形態では、タグからの逸脱の小さいASK信号が存在することは、通常、チャネルから平均信号レベル(つまり、1380の場合のようなDC値)を差し引いて正規化された信号を取り出し、残りの(正規化された)信号の絶対値を調べることにより検出される。ある形態の自動利得制御(1380にもある)をさらに適用し、信号レベルを正規化することが可能であることにも注意されたい。正規化された信号レベルの絶対値が(一般にある期間にわたって)ある閾値を超えた場合、信号は好ましい実施形態のそのチャネル上に存在しているといわれる。
【0096】
特定のチャネルで信号が検出されると、読取装置100は、通常、衝突がそのチャネル
で発生した場合にそのことを検出しなければならない。これは、通常、ある期間にわたって正規化された信号レベルの絶対値の分散を調べることにより検出可能である。信号の絶対値の分散がある(異なる)閾値を超えた場合、衝突は、その特定のチャネル上で発生したといわれ(異なるタグのIDデータの2進データ値が衝突しているため−図17を参照)、そうでない場合、単一の信号は、そのチャネル上に存在しているといわれる(図18を参照)。ここでもまた、当業者であれば、これらの測定結果のフィルタ処理または平均処理および指標を使用して、その信頼性を高めることが可能であることを理解するであろう(例えば、推定値のSNRを上げる)。こうして、そのような測定に関して観察期間が長いほど(後のフィルタ処理で使用される)、推定値の精度および信頼度は上がることになる。また、衝突は、標準誤差検出(例えば、CRC)手段などの他の手段により検出することも可能であるが、それらの方法はすべての場合において、衝突を正しく検出可能であるわけではない。なお、あるチャネル上で衝突が発生しようとしまいと、標準誤り訂正手段を使用して、伝送誤りを補正し、信号推定値の精度を高めることが可能であることに注意されたい。これらの測定は、通常、与えられたパス内の利用できる(可能な)通信チャネルすべてで実行される(これは、上述のように、複数パス・アルゴリズムのパスの番号によって異なる)。
【0097】
そこで、読取装置100は通常、1パス当たりの可能な通信チャネルの(それぞれおよび)すべてで信号が存在しているかどうか、および信号が存在している場合に各チャネル上で衝突が発生したかどうかを特徴付ける。衝突は一般に、2つまたはそれ以上のタグが複数パス・アルゴリズムの同じパスで同じ通信チャネルを使用する場合として定義されることに留意されたい。与えられたチャネル上で衝突が発生した場合、そのチャネルに対するデータは一般に、衝突緩和手法が使用されていなければ失われることになる。与えられたチャネル上に信号が存在し、衝突が検出されない場合、その(与えられた)チャネル上の特定の信号は、正常に受信されているといわれ、読取装置100は一般的に、その特定のタグのデータ系列全体を認識する。
【0098】
いくつかの実施形態ではさらに、誤り検出または訂正(または何らかの他の種類の信号完全性測定)を実行し、データが有効であり、正しく受信されていることを確認することが可能であることに注意されたい。また、タグ・チャネル選択データが送信された場合、読取装置100はさらに、タグ110が実際に予期されている通信チャネル上で通信を行ったことをチェックすることも可能であることに注意されたい(上述のようにチャネルを決定するために使用されるデータの部分に対する他の形態の誤り検査として使用される−図18も参照のこと。第2のパスに対するチャネル選択データ222は、1820、1830、1840で識別されているように、チャネル選択と一致していなければならない)。
【0099】
タグ110からの信号が認識されると(そして場合によっては確認されると)、これは無視されるか、または信号母集団の残りから除去される(後述)。特定のタグからの信号が信号母集団から実際に除去される場合(さまざまな可能なアルゴリズムを使用して)、ある種の衝突緩和が実装される。信号の除去は、衝突緩和の利点を活かすために正確でなくてもよいことに注意されたい。
【0100】
図19は、衝突緩和手法を使用する場合の読取装置の動作に関する一般的な流れ図を示している。この場合、読取装置100は、可能な限り多くの衝突(例えば、データ中の誤り)を解決しようと試みてから、複数パス伝送アルゴリズムの次のパスに移る(例えば、好ましい実施形態において読取装置の送信電力を一定に保つことにより)。
【0101】
上述のように、読取装置100は、一般に、すべての能動的送信タグが識別されている何らかの信頼度レベル(または確率)が得られるまで送信を指定電力レベルに保つ。
信号が信号母集団(または複合受信信号)から能動的に除去される(差し引かれる)ことがない場合、衝突緩和はいっさい発生していないといわれる。その場合、読取装置100でさまざまなアルゴリズムを使用し、タグからのすべてのデータを正常に取得(または復調)することが可能である。この場合の一般的な考え方では、複数パス送信元デバイス伝送アルゴリズムの複数のパスのうちの少なくとも1つで一意的な(つまり、単一のユーザが占有した)通信チャネルを各タグが選択するのを待つ。この手法は、一般に、読取装置100内で利用可能な最も複雑度が低い識別方法であるが、一般的に、最も低速でもある(つまり、情報のやり取りにかかる全伝送時間が最も長い)。
【0102】
読取装置100により衝突緩和手法が使用されていないケースに対する非常に複雑度も低いアルゴリズムの1つは、タグ110、120、130に、複数パス通信アルゴリズムで最大数のパスを伝送させるという単純な方法をとる。最大数のパスは、通常、タグに格納されているデータの一意的な部分が尽きたら(上述のように)決定される。
【0103】
上述のように、読取装置100は、第1および第2の所定の伝送状態を制御することによりタグが送信する際のパスの数を直接制御する。本発明の好ましい実施形態では、読取装置送信電力レベルは、完全にアクティブにされているタグ間の伝送を続行させるために一定に保たれるが、他の第1および第2の所定の伝送状態はタグからの伝送をグループ単位で制御することが可能である。パスの最大数は、一般に、特定のチャネル選択アルゴリズムにより決定されるが、一般に、完全に一意的な(重なり合わない)チャネル選択項目についてデータ長(ビット数)をデータのチャネル選択部分(ビット数)の総和で除算した値に限られる。したがって、128ビットのデータと、8ビットのチャネルID選択データが各パス内にある上に示した例では、(チャネル選択が繰り返しを開始する前に)複数パス・アルゴリズム内に最大16(つまり、128/8)の通信パスがある。そこで、好ましい実施形態でチャネル(例えば、PN)シンボル・レートを与えた場合、最大インテロゲーション時間(maximum interrogation time)を決定することが可能であり、全取得(または読み取り)時間はすべての場合について固定される(上の式でも示されているように)。
【0104】
衝突緩和手法を使用しない他の(多くの場合、より複雑な)アルゴリズムも可能である。このような代替え手法の1つでは、受信したデータ(または取得されたタグ在庫)が正しいものである指定信頼度レベルが得られるように、タグ110、120、130に限られた数(最大数未満)のパスについて伝送を行わせる。これは、一般に、システムに(または各パワーオン・レベルで)存在する予想される数の送信元デバイス(またはタグ)および望む信頼度レベル(またはシステム内の商品またはタグを正常に識別する確率)により決定される。例えば、上の例で与えられた動的チャネル・プロファイルを使用したシミュレーション(試行回数1000回以上)から、50個のタグを識別するために平均7.73伝送パスを必要とすることがわかっているが、1000回の試行でタグを一意に識別するためには最大10個のパスが必要であった。したがって、読取装置100は、10個のパスの間与えられた電力レベルで電力オン状態を保ち、50個(程度の)タグすべてが一意的なチャネル上でそのデータを正常に送信したという十分な信頼性がありえる。ここでもまた、読取装置100は、IDデータを受信するため、いつチャネル上に1つのタグ110しかないかを判別することが可能であればよい。これにより、上の例で与えられた絶対最大16個のパスの代わりに10個のパスだけ実行したため、全取得時間の実質的短縮がなされることになる。詳細なシミュレーション、統計的または確率分析を適用して、他の信頼度レベルまたは与えられた数のタグに対するパスの数を決定することも可能であろう。いくつかの応用では、読取装置100は、最初に在庫調べをするときに最大数のパスを利用し、その後、システム内に存在すると予想される(または、測定もしくは観察された)数のタグに基づいてパスの数を調整することも可能であることに注意されたい。
【0105】
それとは別に、読取装置100によって使用されるアルゴリズムは各タグの予想される衝突位置(つまり、チャネル)を追跡し(そのデータまたはID情報が正常に受信された後)、システム内にまだ識別されていないタグがいくつ残っているかを推定することも可能である。したがって、読取装置100は、上記の方法よりも早くインテロゲーション工程を停止することが可能である場合がある(システム内に他のタグが存在する可能性がないと判断された後)。つまり、必要な数の伝送パスは、上記のようにタグの予想される数に基づいて事前に計算するのではなく、受信時に読取装置100により様子を見ながら推定されるということである。この手法については、以下の例と図22で詳しく説明される。
【0106】
読取装置100のより高度な実施形態では、複数の形態の衝突緩和手法のうちのどれか1つを使用することが可能である。衝突緩和手法を使用すると、一般に、与えられた通信チャネルに対する衝突の影響が除かれる。チャネル上の特定の衝突の効果が除去されることが理想的である。これは、(少なくとも概念上は)判明している信号を再生し、判明しているその信号を全信号母集団(または複合受信信号)から差し引くことにより、望むシステムにおいて実現することが可能である。この干渉信号除去は、復調工程のどの段階でも行えることに注意されたい(例えば、チップ・レートで行うことも、好ましい実施形態での逆拡散の後に行うことも可能である)。本発明の好ましい実施形態では、実装の複雑さを軽減するために復調(つまり、逆拡散)の後に衝突緩和を実行する。
【0107】
一般に、衝突緩和手法を使用する場合、判明している信号が多いほど、複数パス・アルゴリズムの指定パスについてシステム内に存在するように見えるタグの数は少なくなる。好ましい実施形態ではタグ110に格納されているデータは直接チャネル選択を決定するため(または、読取装置100により他の何らかの手段により知られているため)、読取装置100は、データを正常に受信した後(一般に、タグ110が他の何らかの形で未占有になっているチャネル上で送信する場合に発生する)、タグ110により複数パス通信アルゴリズムのすべてのパスについて実行されるチャネル選択のすべてを認識する。そのため、読取装置100は、上記のようにタグ110が将来の(および過去の)伝送について利用するチャネルを予測することが可能である。タグ110からの観察された信号レベルはさらに、一般的に、通常の信号検出工程において、読取装置100内で測定され(またローパス・フィルタに通され)、与えられた(衝突していない)タグの実際の信号強度の信頼可能である推定値が得られる。この知識を利用すれば、判明している信号を効果的に生成し直し、受信した信号全体から正確に差し引くことが可能であり、それにより、他の伝送パスからその効果を除去することが可能である。
【0108】
概して、さまざまな複雑度レベルの衝突緩和手法の一群が存在しており、一般に、衝突緩和手法を使用しない実装よりも複雑である(例えば、より大きな処理能力、メモリ容量、またはハードウェアを必要とする)。しかし、このような手法を採用すると、一般的に、全タグ・データ取得(読み取り)時間はかなり短縮し、システム能力を大幅に高めることが可能である。ここでもまた、チャネルは疑似静的であると仮定しており、システムは比較的リニアであり、最良のシステム性能が得られる。
【0109】
比較的単純な形態の衝突緩和では、複数パス・アルゴリズムの後続のパスから(時間に関して順方向に)判明している信号を差し引く必要がある。そのため、この形態の衝突緩和は、一般に、順方向衝突緩和(forward collision mitigation)と呼ばれる。図20は、順方向衝突緩和手法を使用する読取装置処理の流れ図の例を示しており、そこでは、処理は、工程をわかりやすくするため、順次(例えば、チャネルを一度に1つずつ)実行する。この工程では、一般に、タグ110、120、130のどれがIDデータを正常に送信したかを判別し(上の受信器アルゴリズムで説明されているように)、複数パス・アルゴリズムのパス毎に判明している(タグの)チャネル選択
および推定信号レベルを含むデータ構造体(またはリスト)を保持する必要がある。タグのIDデータおよび送信されたタグ信号の信号レベルは、認識された後、そのタグを伴う後続の衝突から効果的に除去することが可能である。ここでもまた、信号レベルを測定し、フィルタ処理する時間を長くすることで、干渉信号レベルの精度のレベルを高めることが可能であることに注意されたい。そこで、本発明の1実施形態では、タグ信号は、推定された(あるレベルの精度内で判別された)後、複数パス伝送アルゴリズムの後のほうのパスで適切な(所定の)チャネルから差し引かれ、その(判明している)タグの信号が他のユーザによって送信された他の信号に及ぼす干渉影響が打ち消される。通常、タグ110に格納されているデータに基づく、各タグのチャネル選択の決定論的性質のため、この手法が可能になっている。
【0110】
測定された信号レベルは後続のすべてのパスで保持されると仮定されるため、ここでは疑似チャネルの仮定が重要になる。一般に、チャネル状態がゆっくり変化することに対応するため、信号レベル推定を伝送パス毎に更新することも可能である。このアルゴリズムを実行するために、判明しているタグ信号情報(通常は、データ構造体またはリストに含まれる)および現在の伝送パス(またはバースト)からの複合受信信号を格納するだけでよいことに注意されたい(以下のアルゴリズムで説明しているようにメモリ内にすべての受信バーストを格納することとは対照的である)。一般に、この種の順方向衝突緩和アルゴリズムを使用すると、衝突緩和を実行しない方法に比べて全読み取り時間がかなり(2〜4倍)改善される可能性がある。
【0111】
他のより高度な形態の衝突緩和では、複数パス伝送の後続のパスおよび前のパスの両方から判明している信号を差し引く必要がある。これが可能であるのは、タグ110からのデータが識別された後、前のパスでそのデータが占有していたチャネルを確認し、前の衝突への関わりを無効にすることが可能であるためである。このクラスの衝突緩和アルゴリズムは、一般に、双方向衝突緩和手法と呼ばれる。双方向衝突緩和は、複雑な計算を行うが(一般に通信前パスを格納するためにより多くのメモリを必要とする)、その結果、全タグ読み取り時間は大幅に短縮される(衝突緩和を実行しない方法に比べておおよそ1桁短縮される)。
【0112】
一般に、この方法では、識別されたタグについて各通信パス(上記の場合のように)で判明しているチャネル選択および推定信号レベルを含むデータ構造体を格納する必要がある。しかし、信号は前の伝送パス(順方向衝突緩和アルゴリズムの場合のように現在パスに加えて)から差し引かれるので、さらに衝突があっても解決することが可能である。例えば、複数パス通信アルゴリズムの第3のパスからのデータが解決された場合(つまり、正常に受信された場合)、他のユーザからのデータはアルゴリズムの前のパス(例えば、第2のパス)で解決可能な場合があり、さらにこれにより、すでに伝送の前のパス(例えば、第1のパス)または後続のパス(例えば、第3のパス)のいずれかで衝突していた他のユーザを解放することが可能である。新しいユーザからのデータが解決される毎に、再構成された信号がすべての伝送パスから(現在のパスまで)差し引かれ、衝突の回数も再び評価される(可能なすべての通信チャネルについて)。このようにして、読取装置100は利用可能な伝送パスをすべて(現在のパスを含み現在のパスまで)巡回し、どのパスでも(現在のパスまで)解決することが可能なユーザがそれ以上いなくなる時点に達するまで、さらに多くのタグ信号を実質的に連続して解決することが可能である。読取装置100は、その後、次の電力レベルに1ステップ進み、双方向衝突緩和アルゴリズムを続行する。この効果は、後の伝送パスで極めて強力である可能性があり、通信チャネルの利用可能な個数よりもかなり多いタグ信号を解決することが可能である。
【0113】
タグ・データのすべてが受信されると、読取装置100は、上述の手段(例えば、誤り検出および訂正)を介してデータの完全性をチェックすることが可能である。読取装置1
00は、さらに、データの後処理を行うことも可能であり、通常は、冗長項目のスクランブル解析、暗号解読、分類、および除去などの機能を含む(本発明の好ましい実施形態では複数のパワーオン範囲で電源投入する)。これらの機能の一部または全部を、中央にひとまとめに配置することも可能であり、それにより、複数の読み取り装置またはアンテナを扱うことが可能であることに注意されたい。
【0114】
システム・オペレーションの例
これらのアルゴリズムのオペレーションは、例を使うと内容が最もよくわかるであろう。これらの例は、パス毎にランダム・チャネルを引き込むタグの簡素化された仮説的システムを詳しく示している。図21、23、および24は、この例を説明するために使用される、システムの状態図であり、アルゴリズムを通る後続パス毎に各タグが通信するため選択するチャネルを示している。例に示されている状態は、チャネルを選択するために乱数生成器を使用する実際の実験の元の出力である。物理チャネルの種類(例えば、符号位相、タイムスロットなど)はこの時点では無関係である。これにより、上の第I節で詳述したように本発明のデータ・スクランブル部分があるため、システム全体の比較的正確なモデルを用意しなければならない。
【0115】
図21、23、および24に詳述されている例では、8個のタグからなる母集団を仮定し、さらに、タグが通信のため引き込む引き込み元の8つのチャネルの1パス当たりの固定チャネル・サイズを仮定する。そこで、好ましい実施形態では、各タグのID情報の(一意的な部分集合の)3ビットを使用して、伝送の各パスで各タグ110が送信に使用する8つのチャネルのうちの1つを選択する。8進数を使用して、タグIDの最初の30ビットがランダムに生成されているが、便宜上以下のように繰り返す。
【0116】
タグ1: 0033 0436 07...
タグ2: 1106 2551 65...
タグ3: 4767 4416 41...
タグ4: 2044 6111 36...
タグ5: 6072 3355 74...
タグ6: 1476 5432 40...
タグ7: 5443 3675 34...
タグ8: 2135 5115 64...
タグ1は、パス#1でチャネル0を、パス#2でチャネル0を、パス#3でチャネル3をというように選択を続ける。タグ2は、パス#1でチャネル1を、パス#2でチャネル1を、パス#3でチャネル0をというように選択を続ける。このリストから、第1の8進数からチャネルを引くパス#1については、タグ1はチャネル0の単独占有者であり、タグ3はチャネル4の単独占有者であり、タグ5はチャネル6の単独占有者であり、タグ7はチャネル5の単独占有者であることがわかる。これらのチャネルには衝突がないため、タグ1、3、5、および7は全体として正常に識別されており、タグ1、3、5、および7は、衝突がなかったチャネルでその完全なIDを伝達した。しかし、パス#1では、タグ2および6は、チャネル1で衝突しており、タグ4および8はチャネル2で衝突している。これらのタグは、正常に識別することが不可能であり、後続のパスを解決する必要がある。読取装置100は、衝突が存在していることを観察し、印加されている電力を現在レベルのままにし、それによりすべてのタグがパス#2の第2の8進数から別のチャネルを引くことが可能であるようにする。タグにはIDを正常に伝達可能であったかどうかを知るすべがないことに注意されたい。
【0117】
パス#2では、衝突に関わっていない唯一のタグはタグ3である。このタグはすでにパス#1で識別されていたため、読取装置100は新しい情報を取得しなかった。パス#1で衝突していたタグはどれもまだ識別することは可能でない。統計的に、8つのタグと8
つのチャネルでは、少なくとも1つの衝突が生じる確率は1−8!/88=99.76%である。この結果は、上で与えられたN個のチャネル上のM個のタグの間に衝突がない確率のより一般的なケース
【0118】
【数5】
#1 P{衝突なし}
とP{衝突}=1−P{衝突なし}という事実から得られる。この同じ確率は、アルゴリズムを通るパス毎に衝突が少なくとも1回あるという確率である。タグとチャネルのこのような組み合わせについて、実験を100000回行って平均をとると、8個のチャネルのうち2.7498個は1パス当たり未占有であり、これらのチャネルのうち3.1386個は、単一タグを含み、1.5737個のチャネルは2つのタグを含み、0.4482個のチャネルは3つのタグを含み、0.0796個のチャネルは4つのタグを含み、0.0093個のチャネルは5つのタグを含み、7.2×10−4個のチャネルは6つのタグを含み、4×10−5個のチャネルは7つのタグを含み、1チャネル内に8つのタグというケースは記録されていなかった。
【0119】
衝突緩和のない例
衝突緩和を行わない場合、タグは、識別されるために、チャネル内にすべて自力で現れていなければならない。実験を十分な回数行うことが許されていれば、このようなことが起こる。しかし、タグID 220情報内のビットの数は限られているため、繰り返しを開始する前に、実験は限られた回数しか実行することが可能でない。例えば、タグIDが96ビット長であり、1パス当たり3ビットを使用してチャネルを引いたとすると(8つのうち1つ)、32回の実験後にその工程が繰り返される。1パス当たり少なくとも1回の衝突があるという高い確率(このシナリオでは99.76%)なので、実験を介してタグのIDがパス毎に、また全パスにわたって衝突の中に「隠れる」ことがあり得る確率は小さいが有限の値である。これは、タグのID 220は全体にわたって異なるタグのIDと同じであることを意味しない(一意的なタグIDおよびスクランブルされたタグIDへの一意的な可逆マッピングがあるという仮定により許されていない)。これは、そのパスについてチャネル空間を定義するために使用されている少数のビット(この場合、3)に関して調べたときに、タグのID 220は少なくとも1つの他のタグのIDと同じであると言っているに過ぎない。これにより、タグの在庫がある信頼度でしか判明していない、在庫または商品の不確定性という概念が導入される。
【0120】
図21の実験例では、衝突のないチャネルに現れるためにタグ毎に8回の試行が必要である。すでに述べたように、タグ1、3、5、および7は、パス#1で識別され、タグ2はパス#3で現れ、タグ4および8はパス#4で識別され、タグ6はパス#8まで現れない。タグ6は、一意的なIDを持っているとしても一意的なタグが衝突の中に隠される可能性のあることを示すよい例である。この実験がパス#7でしか行われていないとすれば(つまり、IDの長さが21ビットしかなかった場合)、タグ6は識別されていないであろう。
【0121】
パス#1で、4つのタグが識別される。さらに2つの衝突が識別され、ほかに少なくとも4つのタグがあることが示される(少なくとも2つのタグがあれば単一の衝突が生じるので、2つの衝突が生じるためには少なくとも4つのタグが必要である)。したがって、第1のパスの後、読取装置100は、4つの判明しているタグと少なくとも4つの未知の
タグがあるか、または全部で少なくとも8つのタグがあると判別することが可能である。
【0122】
パス#2では、単一のすでに判明しているタグのみが一意的な(未使用の)チャネルを占有している。読取装置100ではタグ1、3、5、および7の完全なIDがわかっているため、次および後続のすべてのパスでそれらのタグが占有するチャネルがわかる。読取装置100は、タグ1および5がチャネル0に、タグ7がチャネル4に割り当てられることを知る。そこで、読取装置100は、チャネル0に衝突があることを予期するが、チャネル0を占有している未知のタグ(この場合、タグ4)もある可能性がある。チャネル0は、2つの判明しているタグの存在と、1つまたは複数の未知のタグの存在の可能性を示す。読取装置100は、チャネル1での衝突を予期していなかった(判明しているどのタグもそのチャネルを選択することを予期していなかったからである)。ここで、衝突は、少なくともさらに2つの未知のタグ、おそらくさらに多くのタグがあることを示す。タグ7だけが予期されていたチャネル4上の衝突は、ほかに少なくとも1つの未知のタグがあることを示す。したがって、パス#2では、4つのすでに判明しているタグがあり、少なくとも3つの(確実に)未知のタグがある。これは、少なくとも4つの判明しているタグと少なくとも4つの未知のタグであった、第1のパスによって定義されている集合よりも少なく、したがって読取装置100は第2のパスで新しい情報を収集していなかった。
【0123】
パス#3では、タグ2はチャネル0上で識別される。タグ1は、チャネル3に入ることが予期されている唯一のタグであり、したがって衝突はそこでは、少なくとも1つの未知のタグのあることを示す。タグ7は、チャネル4に入ることが予期されている唯一のタグであり、したがって衝突はそこでは、少なくとも2つの未知のタグ(チャネル3上の未知のタグとチャネル4上の未知のタグ)のあることを示す。タグ3は、この場合も単独である。タグ5は、チャネル7に入ることが予期されている唯一のタグであった。衝突は、少なくとも3つの未知のタグがあることを示す(チャネル3、4、および7上の未知のタグを勘定に入れる)。これらも、現在の5つの判明しているタグとともに、この場合も、少なくとも8つのタグのあることを示す。
【0124】
パス#4により、新しいタグ4および8が識別される。タグ3、5、および7は、衝突のないチャネルに現れる。タグ1および2は、チャネル6上で衝突することが予期されていたが、そこにはさらにタグがありうる。そのため、7つの判明しているタグと、前の実験からの、少なくとも1つの未知のタグが残る。
【0125】
パス#5により識別される新しいタグはない。チャネル5上の衝突は予期されておらず、この場合も、7つの判明しているタグと少なくとも1つの未知のタグがあることを示す。パス#6とパス#7から、同様の解釈を行うことが可能である。
【0126】
パス#8では、タグ6が識別される。他の衝突はすべて予期されていた。そこで、8つのタグが識別されており、前のパスから最低限の数が予期されている。しかし、それでも、衝突に隠れているタグがあり得る。例えば、チャネル1、0、4、6、3、1、1、5を選択したタグがあり得、このタグは他の衝突により隠されることになる。タグにこの特定のIDがある確率は、1/88または6×10−8となる。
【0127】
また、チャネル、例えば、2、4、4、6、5、4、5、6を、これもまた確率6×10−8で選択したタグがあり得る。まとめると、パス#1で2つの衝突、パス#2で3つの衝突、パス#3で3つの衝突、パス#4で1つの衝突、パス#5で2つの衝突、パス#6で2つの衝突、パス#7で3つの衝突、およびパス#8で3つの衝突があると、2×3×3×1×2×2×3×3=648通りの可能なIDがあり、それぞれ確率は6×10−8で、追加される単一の隠しタグの確率は648/88=38.6×10−6(38.6ppm)である。追加される2つの隠しタグの確率は、さらに小さいなものとなり、64
8・647/816=1.5×10−9である。他の実施形態では、データをスクランブル解析し、例えば、他のすべての商品が食料雑貨であった場合に隠されているタグが他の予期される商品の全部または一部と関連付けられていることを判別することにより、在庫信頼度のレベルをさらに改善することが可能であろう。
【0128】
隠されているタグの確率は、衝突情報に基づいて最小個数(この場合、8個)の予期されるタグを識別した後に実験を続行させることにより小さくすることが可能である。1パス当たりの衝突の回数を数え、1パス当たりのチャネルの数に基づいて隠されているタグの確率を知ることにより、読取装置100は、何らかの信頼度レベルを満たすか、または一意的なチャネル・パターンを使い尽くしてしまう(IDが枯渇する)まで、パスを続けさせることが可能である。2つの追加パス(全部で10のパス)の後に、1パス当たり6481/8=2.246回の衝突を仮定すると、単一の隠されているタグの確率は、3.04×10−6に下げることが可能である。さらに2つの追加パス(全部で12のパス)の後、単一の隠されているタグの確率は、240×10−9に下げられる。パスを追加する毎に、単一の隠されているタグの確率は、等比級数的におおよそ6481/8/8=0.281倍ずつ減少する。
【0129】
上で説明した干渉除去のない方法に関わるステップを示す流れ図は図22に示されている。開始2210時に、システムは、正のIDも未知商品もないものとして初期化され、これは合わせて、合計0個の商品に対応する。第1のパス2220の分析2230の後に、正のID(例えば、パス#1の商品1、3、5、および7)は、記録され、正のIDのリストに追加される2240。パス2250内の衝突の回数も記録される(例えば、パス#1では2つの衝突)。衝突が予想されていた場合2260、将来のパスで明らかにすることが可能な潜在的未知商品があるが、確実な未知商品はない。衝突が予想されなかった場合2270、2つの未知商品が未知リストに追加される。そこで、商品の総数は、正として識別された商品の個数および記録された衝突の原因になった可能性のある未知商品の最小数であるとして推定される2280。正のIDは推定された商品総数に等しくないと仮定すると、未知商品の合計は0にリセットされ2295、他のパス2220が開始する。最後に、正のIDの個数がすでに識別されているIDの最大数+未知商品の数に等しい場合にこのループを抜け2290、所定の信頼度レベル2296が満たされる。
【0130】
ここまで、チャネルと受信信号レベルの時間的変動に関してはいっさい仮定を置かなかった。「衝突緩和のない方法」は、チャネルが静的であろうと動的であろうと適用することが可能である。静的なチャネル状態の場合、戻り信号の電力レベルと位相が一貫していれば、受信信号レベルという形で読取装置100で利用可能な情報が増える。そこで、判明しているタグが将来のパスで選択するであろうチャネルが判明していることに加えて、その信号レベルも判明していると仮定すれば、予期した衝突にさらに隠されたタグが存在するかどうかを判別することが可能である。例えば、パス#2のチャネル0上の衝突には、2つの判明しているタグと1つの未知のタグが含まれていた。判明しているタグの信号レベルも判明していれば、衝突の総信号レベルを個々の信号レベルと比較して、衝突の中にさらに未知のタグが隠されているかどうかを判別することも可能であろう。このような環境では、衝突はすべて説明されるため隠されたタグがないことが確実であれば、すべてのタグが独立に識別された後(この場合、8パス)、読取装置100は問い合わせを終了することが可能である。
【0131】
したがって、識別されたタグの信号レベルがわかれば、在庫のアカウンティングの信頼度が高まる。しかし、信号レベル情報があれば、すべての判明しているタグが個別に出現した後、問い合わせを単に打ち切ること以上に、収集時間の改善を期待可能することが可能である。これについては、次の節で説明する。
【0132】
順方向衝突緩和の例
タグが個別に識別されると、後続のすべてのパスに対するチャネルの選択が読取装置100側で判明する。タグの信号レベルおよび位相がさらに判明すれば、そのタグが衝突に関わる寄与分を0にすることが可能である。後続の衝突から、タグからの信号を本質的に除去することが可能であり、したがって、母集団からも実際に除去することが可能である。図23に示されている実験を考察する。タグ1、3、5、および7は、パス#1で正として識別されている。その信号レベルおよび位相も決定されていると仮定する。
【0133】
パス#2で、タグ1および5は、チャネル0上でデータを送信することが知られている。その判明している信号レベルでは、タグを差し引くことが可能であり、現在識別することが可能なタグ4のみを残す。同様に、タグ7はパス#2でチャネル4によりデータを送信することが予期されており、このタグを無効にすることにより、タグ6はそのまま残され識別される。チャネル1にはまだ未解決の衝突があり、このアルゴリズムを通る少なくとも1つの他のパスが必要である。
【0134】
パス#3では、タグ2が単独で現れ、識別される。タグ1は、チャネル3上でデータを送信することが予期されており、したがって、差し引かれ、後にはタグ8のみが残り、そこで、識別することが可能である。他のすべての衝突には、判明しているタグのみが含まれ、タグのアカウンティングは、図21に示されているような衝突緩和なしの場合の8つ以上のパス(必要な信頼度レベルに応じて)ではなく100%の信頼度でアルゴリズムを通る3つのパスで完了している。
【0135】
静的チャネルでは、識別されたタグの信号強度は、高い精度で知ることが可能である。増大されたPNチャネルのケースを考察する。この実験では、タグは8チップ長の増大されたPN系列のさまざまな符号位相を選択する。この8チップ長のPN系列は、特定のIDビットの意味に応じて、タグのIDのビット毎に、真または反転で送信される。読取装置100では、受信器内の相関器は、本質的に、1ビット当たり8個のチップにわたり信号レベルを平均する。これは、ID内のすべてのビット(例えば、128)について実行され、信号対雑音比平均利得10 log(1024)=30dBについて8×128=1024サンプルで平均をとる。さらに多くの予期されるタグとさらに多くの(>32)利用可能なチャネルがあるより実際的なケースについては、この利得は大きくなる。32チャネルおよび128ビットでは、信号対雑音比の利得36dBが得られる。
【0136】
双方向衝突緩和の例
読取装置100が前のパスからの波形サンプルを格納していれば、アカウンティング時間はさらに大幅に改善し得る可能性がある。波形が格納されていれば、前のパスをもう一度辿り、それを後続のパスとして処理することが可能であり、そこから前の衝突を無効にすることが可能である。これは、タグが一度でも識別されると、それ以降のすべての活動が判明するだけでなく、前のチャネル選択および信号レベルもすべて、判明するからである。
【0137】
図24に示されている例を考察する。パス#1では、タグ1、3、5、および7は、ビット・パターンおよび信号レベルと位相の両方で識別される。順方向衝突緩和の場合と同様に、タグ4は、パス#2で識別することが可能であるが、タグ1および5の効果をチャネル0上の衝突から除去することが可能だからである。同様に、チャネル4上の衝突からタグ7の効果を除去することで、タグ6を識別することが可能である。パス#2の後、また順方向衝突緩和を適用した後、タグ1、3、4、5、6、および7が判明する。
【0138】
第3のパスを使用せず、順方向衝突緩和を適用した後にパス#1の結果に立ち返ることが可能である。パス#2でタグ4が識別された場合、第1のパスの格納されている結果の
チャネル2からそのタグを除去し、タグ8を解決することが可能である。パス#2でタグ6が識別された場合、第1のパスの格納されている結果のチャネル1からそのタグを除去し、タグ2を解決することが可能である。この場合、8つすべてのタグを正常に識別するために、2つのパスのみが必要である。順方向および双方向衝突緩和の有利性は、関わるチャネルとタグの数が増えると一段と増す。
【0139】
そのため、卓越した性能(例えば、読み取り時間および容量)を発揮する複数パス伝送アルゴリズム(スペクトル拡散手法を採用するのが好ましい)を使用する一方向通信システムについて詳述した。衝突緩和手法、動的チャネル・プロファイル、およびパワーオン範囲を組み込むことで、システム性能がさらに改善される。説明した通信システムには、本明細書で詳述した好ましい実施形態および実際の例に限られない多数の応用がある。さらに、本発明には、双方向通信デバイス、能動的給電ユーザ・デバイス、およびネットワーク接続デバイスの応用もあるが、その本質的特徴(請求項で説明している)から逸脱することはない。
【0140】
本発明は、本発明の精神または本質的特徴から逸脱することなく他の特定の形で実現することが可能である。説明した実施形態は、すべての点で、説明のみを目的としており、制限することを目的としていないとみなすべきである。したがって、本発明の範囲は、上記の説明ではなく、付属の請求項で指示される。請求項の同等性の意味および範囲内にあるすべての変更は本発明の範囲に含まれるものとする。
【図面の簡単な説明】
【0141】
【図1】本発明による単一の送信先デバイスと通信する複数の送信元デバイスを示す高水準の図。
【図2】タグに記録されているデータの変更方法および本発明による動作が行われている間に送信チャネルを判別するための使用方法を説明する図。
【図3】本発明によりタグに記録されるデータをスクランブルするために使用される工程を示す高水準の図。
【図4】本発明による複数のタグ通信および読取装置で実行される逆スクランブル(スクランブル解析法)を示す高水準システムの図。
【図5】本発明によるタグ・データのスクランブルおよび回復に使用される反復アルゴリズムを説明する図。
【図6】本発明によるスクランブル手順の詳細な例を示す図。
【図7】本発明によるタグの高水準のブロック図。
【図8】本発明によるタグ伝送状態の概略を示す一般的流れ図。
【図9】本発明によるタグ伝送状態の概略を示す詳細流れ図。
【図10】本発明による代表的実施形態における読取装置とさまざまなタグとの間の静電結合を使用する応用事例を示す図。
【図11】本発明によりタグに記録されるデータに基づき通信するタグのチャネルを生成する方法を示す図。
【図12】本発明によるパスの依存関係および変調方法を説明する簡略化されたタグ回路の機能ブロック図。
【図13】本発明による読取装置の詳細ブロック図。
【図14】本発明によるWalsh符号化信号の高速変換方式の例を示す図。
【図15】本発明による疑似雑音系列(pseudonoise sequences)の高速相関を求めるための読取装置受信器信号処理の詳細な例を示す図。
【図16】本発明による読取装置信号処理の簡略化された機能ブロック図。
【図17】本発明による、衝突存在時の波形例を示す図。
【図18】本発明による、衝突が存在しないときの複数の波形例を示す図。
【図19】本発明による読取装置の動作の一般的流れ図。
【図20】本発明による前方衝突緩和手法(forward collision mitigation techniques)を使用した読取装置信号処理の詳細な流れ図。
【図21】本発明により衝突緩和手法が適用されない場合の棚卸資産会計の例を示す図。
【図22】本発明により衝突緩和手法が適用されない場合の在庫アルゴリズムの流れ図の例。
【図23】本発明による衝突緩和手法が使用される棚卸資産会計の例を示す図。
【図24】本発明による双方向衝突緩和手法が使用される棚卸資産会計の例を示す図。
【技術分野】
【0001】
本発明は、一般に、マルチユーザ・システムでデータ通信を行うための方法とデバイスに関する。
【背景技術】
【0002】
多くの用途にとって、マルチユーザ・システムでデータ通信を行う高速で、効率がよく、信頼性の高い手段が望ましい。(複数の送信元から得られた)複数のデータを迅速に受信器で読み取る必要がある場合に、このような方法が求められる。このような技術の具体的応用の1つは、複数の品目の電子識別(electronic identification)で利用されている。
【0003】
電子識別産業は、リアルタイムの品目追跡および在庫管理を含む多数の商業および軍事用途にとって重要な産業である。電子識別機能を利用することにより、ある種の形態の製造、倉庫業務、流通、および小売に関する実質的にすべての予定計画を含む無数の予定計画において運用効率を大幅に高めることが可能である。正確なリアルタイム在庫追跡を迅速に、効率よく実行し得れば、商品の配置間違い、商品の在庫過剰または不足、および商品の盗難などさまざまな形態の無駄を大幅に減らすことが可能である。
【0004】
現在、電子識別産業は、複数の商品を識別するため、各商品に製品コードを割り当てる手動(光を使った)スキャニングに大きく頼っている。現在、米国の小売り業界全体では、万国製品コード(UPC)システムが広く使用されている。しかし、商品の手動スキャニングは、非常に時間がかかり、また人為的ミスもかなり発生する傾向がある。
【0005】
したがって、複数の送信元から受信器にデータを送信する効率がよく、信頼性が高い方法が必要である。
【特許文献1】米国特許出願第09/981031号
【特許文献2】米国特許出願第09/978890号
【特許文献3】米国特許出願第09/982271号
【特許文献4】米国特許出願第09/982279号
【特許文献5】米国特許出願第09/981476号
【発明の開示】
【発明が解決しようとする課題】
【0006】
本発明では、複数の送信元デバイスから情報を送信先デバイスに迅速に、かつ効率よく伝達するための改良された通信方法を開示する。
【課題を解決するための手段】
【0007】
説明する通信システムでは複数の手法を併用することにより、従来技術に勝る性能を達成する。本発明によれば、手動(光を使用した)スキャニングの排除およびスキャニング(または商品識別)速度の大幅高速化など、さらに特徴と利点を加えながらUPC交換の手段を利用し得る。さらに本発明では、多数の商品を同時識別することが可能であり、在庫、小売りの点検など非常に多くの用途がある。
【発明を実施するための最良の形態】
【0008】
類似の番号は類似の要素を示す付属の図を参照しながら、本発明を例としてのみ説明する。
本発明の好ましい実施形態では、一般に、一方向通信(送信元デバイスから送信先デバ
イスへ)を利用して、送信元デバイスの回路を簡略化しているため、送信元デバイスでは、受信器を使用する必要がない。
【0009】
送信元デバイスから送信先デバイスに伝達される情報は、通常、2進数の電子製品コード(「EPC」)または識別(「ID」)情報の形をとるが、いかなる方法であっても、これらの情報形式に限られるわけではない。電子遠隔計測(または他の種類の測定または割り当てられたデータ)などの他の種類の情報を伝達することも可能である。実際、本発明では、2進(または他の)数形式の表現を持つ情報を伝達することが可能である。
【0010】
図1に示されているように、情報は通常、1組の送信元デバイス110、120、130から単一の送信先デバイス100に伝達され、本発明の好ましい実施形態では、1組の送信元デバイス110、120、130から送信先デバイス100への同時情報通信を使用する。本発明には実施例の内容に応じてさまざまな応用があるので、わかりやすくするため、本説明全体を通して使用される用語を他の用語に置き換えて使用し得る。したがって、送信元デバイス、トランスポンダ、ユーザ、商品、タグなどの用語は、一般性を失うことなく以下の説明全体を通して置き換えて使用することが可能であり、また、送信先デバイス、システム・コントローラ、問合せ器(interrogator)、読取装置、受信器などの用語も一般性を失うことなく以下の説明全体を通して置き換えて使用可能であることにも注意されたい。
【0011】
本発明で採用する通信システムは、光通信、無線周波数(RF)通信、有線(接触)通信、静電結合通信、または誘導結合通信など数種類の通信形態140を包含することが可能である。本発明の好ましい実施形態では、タグ110、120、130と読取装置100との間の静電結合通信リンクを利用するが、他の形態の通信リンクも、制限されることなく利用することが可能である。
【0012】
本発明の以下の詳細な説明は、システムの重要な態様を説明する5つの主要な節とシステム操作の例を取りあげた最終節に分けられる。本発明の好ましい実施形態では、後述の重要な手法をすべて使用するが、他の実施形態では、説明した手法のサブセットのみを使用することが可能である。
【0013】
I.データのスクランブルとスクランブル解析
図2に示されているように、説明しているシステム内のタグ110により読取装置100に伝達されるデータ200は、後述のような測定されたデータまたは他のユーザ定義データなどさまざまな形をとることが可能である。本発明の好ましい実施形態では、伝達されるデータ200は、少なくとも1つの識別データ系列からなる。例えば、データ200は、96ビットの識別データを持つ少なくとも1つのEPCからなり、これについては、デビッドL.ブロック(David L.Brock)著「The Electronic Product Code」(MIT−Auto ID Center,January 2001)に概要が説明されている。EPC 200は、ヘッダ203、オブジェクト・クラス204、ベンダ・コード205、およびシリアル番号206により、システム内の各タグ(または商品)110を一意的に識別するために使用される。例えば、96ビットの情報により膨大な数の一意的ID(296〜8×1028、この数がいかに巨大であるかは、地球の質量が6×1027グラムであることからもわかる)が得られることに留意されたい。
【0014】
通常、ユーザ情報、誤り検査または訂正情報(例えば、前進型誤信号訂正(FEC)、巡回冗長検査(CRC)など)、およびその他の予約ビットなどの補足情報202が、好ましい実施形態のタグ110上に格納されているデータ200に付加される。補足情報(例えば、誤り検出または訂正データ)を後述のデータ・スクランブル工程の前後に追加す
ることが可能であるが、この補足情報をデータ・スクランブリングの後に追加した場合、さらに一様なランダム特性を持つことに注意されたい。
【0015】
当業者であれば、さらに複数の異なる情報形態(例えば、プログラム可能なタイムスタンプ、他のユーザ個人識別番号(PIN)、測定データ、環境データなど)も、予め定めて、タグ110、120、130に格納可能であることを理解するであろう。説明されているシステムのタグ110、120,130に格納されるデータの量または種類に制限は課されないことに注意されたい。
【0016】
タグ機能はすべて、通常は、複雑度の低い(即ち、低コスト)回路で実装される。タグ110上の回路を単純化するため、またシステム内のチャネル選択工程の性能を高めるため(以下で詳述する)、タグ110に格納する前に元のIDデータ200をスクランブルすることが非常に望ましい。これは、通常、タグ110にデータ230を格納する操作の前に実行されるランダム化またはスクランブル工程211により行われる。
【0017】
このスクランブル・アルゴリズム211は、通常、システム全体にわたって普遍的に適用され、EPCデータ200が、スクランブルされた後(220)、望ましい統計的(つまり、一様かつランダムな)特性を示すことが保証される。或いは、他の実施形態では、他のいくつかのスクランブル、暗号化、または番号付けアルゴリズムを格納されているデータ200に適用し、スクランブルされたデータ220を効果的に生成することができる。補足情報のプライバシーを守るため、個々の製造元は暗号化前処理210を任意選択で適用し得る。
【0018】
図3は、本発明の好ましい実施形態によりスクランブルされたデータ220をタグ110に埋め込むためのシステム例を示している。図3では、元のEPC 200は、メーカーなどの、EPCマネージャ310から通常の方法で得られる。その後、EPC 200が、スクランブラ(scrambler)330に入力され、このスクランブラにより、スクランブル・アルゴリズムが実行され、スクランブルされたデータ(S_EPC)220が出力される。次に、RFタグ・プログラマ/ライタ350により、スクランブルされたデータS_EPC 220がタグ110に埋め込まれる。スクランブルされたデータ220は、オリジナルのデータ200の修正版であり、今は、タグ110内に置かれている。
【0019】
図4は、多数のRFタグデバイス110、120、130から電子識別データ200を同時に読み込む高水準ブロック図を示している。この例は、通常棚卸しの際に棚に置かれている製品に関連付けられているタグを読み取る方法を説明している。作動すると、読取装置100は同時に、1組のタグ110、120、130を同時に起動する。その後、起動されたタグ110、120、130は、チャネル選択の基礎としてスクランブルされたタグ・データ220を使用して複数経路伝送アルゴリズムを続行する(以下の第III節で詳述する)。
【0020】
例えば、複数経路・アルゴリズムの第1経路で、S_EPC1の少なくとも一部(タグ110に埋め込まれている)を使用して、チャネルA 240を選択し、S_EPC2の少なくとも一部を使用して、チャネルB 240を選択し、S_EPCnの少なくとも一部を使用してチャネルC 240を選択する。チャネルA、B、およびC、またはそれらの任意の組み合わせは同じであることも、異なっていることもあり得ることに注意されたい。読取装置100は、復調アルゴリズムを続行し、最終的に、棚にあるタグ110、120、130のS_EPC 220を取得する。S_EPC 220は、スクランブル解析アルゴリズムを実行するスクランブル解析器460に送られ、そこで、タグ11、120、130のオリジナルのEPCデータ200が取得される。各タグに対応するEPCデ
ータ200は、読取装置100内に保持するか、または在庫報告書の形でオリジナルのEPCマネージャ310(例えば、メーカー)に送り返すことができる。当業者であれば、スクランブル解析オペレーションは、離れた場所に配置されているコンピュータまたはオンライン・サーバなど、他の場所で実行可能であることを理解するであろう。タグ110、120、130では、構造化の程度の大きいEPCデータ200の代わりに、EPCデータ220のスクランブル版の少なくとも一部を使用して、複数経路伝送アルゴリズムの各経路でチャネルを選択するため、図4のシステム内の衝突は最小限に抑えられる。スクランブルされたデータ220は、一様分布データにきわめてよく似ており、類似のEPC
200を持つ製品間の衝突は最小限である。複数経路伝送アルゴリズムおよびチャネル選択の詳細については、以下の第III節を参照し、衝突および衝突抵抗(collision resistance)の詳細については、以下の第V節を参照されたい。
【0021】
タグ110が伝送に使用するチャネルを必要としない限りタグ110と読取装置100との間で情報交換は行われない(後述)。したがって、本発明のスクランブルおよびスクランブル解析方法は、自己参照的でなければならない、つまりEPC 200をスクランブルするか、またはS_EPC 220をスクランブル解析する必要がある情報のみがデータである。
【0022】
本発明で説明されているシステムは、特定の重要特性を持つスクランブル方法を使用する必要がある。スクランブル方法は通常データ系列(EPCデータ系列など)を一様ランダム分布の特性を示す結果にマッピングするという重要な特性がある。好ましい実施形態では、このスクランブル方法は以下の2つの主要な特性を持つ。
【0023】
1.kを所定の整数とし、k進数で表される2つの通常のEPC 200を与えたとすると(例えば、典型的なEPC 200の対では、k進数の多く(すべてではないが)は同じである)、それらのEPC 200に対応するスクランブルされたS_EPC 220がn個の連続するk進数(チャネル割り当てを決定するためにタグ110で使用される)について一致する確率は約1/knである。
【0024】
2.kを所定の整数とし、スクランブルされた出力がn個の連続するk進数(チャネル割り当てを決定するためにタグ110で使用される)について一致するk進数で表される2つの通常のEPC 200を与えたとすると(例えば、典型的なEPC 200の対では、k進数の多く(すべてではないが)は同じである)、後続のm個のk進数(後続のチャネル割り当てを決定するためにタグ110によって使用される)は約1/kmの確率で一致する。
【0025】
2進数で表されているEPC 200の例では、これらの特性は、強いアバランシェ特性(strong avalanche property)に関係し、そのため、各出力ビットはすべての入力ビットおよび単一入力ビットの変更に左右され、平均して出力ビットの半分を変える。
【0026】
本発明では、図5に示されている再帰的方法を使用した問題の分断攻略によりこのスクランブルおよびスクランブル解析法を実行する。スクランブル・アルゴリズム510は、入力としてデータおよび長さ情報を受け取り、データの左側部分と右側部分を再帰的にスクランブルする。スクランブル解析アルゴリズム520は、スクランブル・アルゴリズム510の逆関数を実行する。再帰の基底(最終)レベルを除くすべてについて実行されるオペレーションは以下のとおりである。
【0027】
スクランブル方法510の場合:
1.1組のデータを第1の部分と第2の部分に分割し、
2.1組のデータの第1の部分に第1のスクランブル方法を実行して、データのスクランブルされた第1の部分を生成し、
3.1組のデータのスクランブルされた第1の部分で1組のデータの第2の部分を修正し、1組のデータの修正された第2の部分を生成し、
4.1組のデータの修正された第2の部分に第2のスクランブル方法を実行して、1組のデータのスクランブルされた第2の部分を生成し、
5.1組のデータのスクランブルされた第2の部分で1組のデータのスクランブルされた第1の部分を修正する。
【0028】
スクランブル解析方法520の場合:
1.1組のデータを第1の部分と第2の部分に分割し、
2.1組のデータの第2の部分で1組のデータの第1の部分を修正し、1組のデータの修正された第1の部分を生成し、
3.1組のデータの第2の部分に第1のスクランブル解析方法を実行して、1組のデータのスクランブル解析された第2の部分を生成し、
4.1組のデータの修正された第1の部分で1組のデータのスクランブル解析された第2の部分を修正し、1組のデータの修正された第2の部分を生成し、
5.1組のデータの修正された第1の部分に対し第2のスクランブル解析方法を実行する。
【0029】
上記のスクランブル510およびスクランブル解析520の両方法では、修正工程は、可逆であり、排他的OR(XOR)、剰余加算、剰余減算などからなるグループから選択される。さらに、第1のおよび第2のスクランブル/スクランブル解析方法は、スクランブル/スクランブル解析すべき1組のデータが所定の長さに達するまで、ステップ1から5までをそれぞれ再帰的に実行し、基底の場合を確立しなければならない。好ましい実施形態では、この所定の長さは1バイトである。
【0030】
1組のデータが所定の長さに達すると、所定の関数が実行される。この所定の関数は可逆であり、ルックアップ関数であるのが好ましく、好ましい実施形態では、置換ボックス(「S−box」)ルックアップ関数が実行される。分割攻略手法でデータの別々のビットをスクランブル/スクランブル解析するのは、ルックアップ関数を単に使用するのと比べて著しく効率が低いため、単一バイトで停止するのがよい。それより大きいサイズで停止すると、一般に、S−boxテーブルは非常に大きくなる。
【0031】
本発明の所定の関数には多数の望ましい特性がある。まず第一に、この関数は可逆でなければならない。スクランブル・アルゴリズム510は、S−boxルックアップ関数を使用するが、スクランブル解析方法520は、S−boxルックアップ関数の逆関数を使用し、この関数は、オリジナルのEPC 200を見つけられるように可逆である必要がある。実際の問題として、ルックアップ関数が可逆であるために、各エントリはちょうど1回だけ現れることになる。本発明では、S−boxへの入力は1バイトであり、出力も1バイトである。S−boxとその逆関数はそれぞれ、256バイトのデータを含む。
【0032】
所定の関数の第2の特性として、強いアバランシェ基準を示す、つまり、すべての出力ビットはすべての入力ビットに依存するという点があげられる。また、厳密アバランシェ基準(Strict Avalanche Criteria)(「SAC」)と呼ばれる追加特性があり、1つの入力ビットを変更すると、ちょうど50%の確率で各出力ビットが変化する。この特性は、本発明にとっては厳密に言うと必要ではないが、弊害があるわけではない。
【0033】
最後に、所定の関数は、低いdpmaxを示す。dpmaxの値は、ルックアップ・テ
ーブルのXOR行列内のエントリの最大値である。XOR行列内の(i,j)エントリは、fをルックアップ・テーブルとし、f(a)^f(a^i)=jとなるような0<a<256の範囲の数である。低dpmaxという特性だと、テーブルの繰り返し反復を使用した場合に、良好なミキシング(good mixing)が継続するが、これは基本的に、本発明のケースに当てはまる。このようなルックアップ・テーブルは、暗号法で検索されることが多い。例えば、高度な暗号化標準(「AES」)暗号アルゴリズムでは、SAC以外のすべてを満たすテーブルが使用され、本発明ではうまく機能する。このテーブルを再利用することで、本発明で説明している用途に無関係の他のシステム機能にAESも使用された場合にコード領域を節約することも可能である。
【0034】
図6は、別々のコンポーネントに展開されるスクランブル工程のブロック図を示している。図6に示されている実施形態では、この工程への入力は、128ビット(または16バイト)のEPCデータ200である。このEPCデータ200は細分され、別々のバイトP0からP15とラベル付けされる。スクランブル(またはスクランブル解析)の工程は、図6の左上から開始し、一番左の2つのバイト(P15とP14)が「MixBytes」ブロック610に入力される。「MixBytes」ブロック610は、「S」というラベルが付いているS−boxルックアップ関数602および608、および「○+」というラベルが付いている排他的ORオペレーション606および604からなる。ブロック図を下ってゆくと、次のステップは、次の2つのバイト(P13およびP12)と「MixBytes」ブロック610の出力との排他的OR 624をとることである。その後、このアルゴリズムは、排他的OR関数622、626、628、632、634、636、642、644、646、648、652、656、および658を使用してデータを連続的に組み合わせ、最終段で出力バイト220(C0からC15まで)が出現するまで関数620、630、640、650、660、670、および680を使用してバイトを混合するというように進む。好ましい実施形態によれば、この工程全体において、全部で16個のS−boxルックアップ・オペレーションと64個の1バイト排他的ORオペレーションが必要である。
【0035】
上述のスクランブル工程に加えて、さらに、万能スクランブル・アルゴリズムを適用する前に(例えば、タグ110をプログラムする前に)データ200を暗号化し(210)、さらにデータ機密保護を確実なものとすることが可能である。このタスクに使用し得る技術において、さまざまな暗号化アルゴリズム(例えば、AES、データ暗号化規格、国際データ暗号化アルゴリズムなど)が知られている。このように機密保護レベルを高められることは、プライバシーが重視される用途(タグに機密にすべき医療または財務データが含まれる可能性がある用途など)の面から重要である。
【0036】
II.パワーオン方式
好ましい実施形態の範囲に収まるタグ110のブロック図が図7に示されている。静電結合システムでは、アンテナ701は、導電性電極(例えば、容量性の板(capacitive plates))の対であるが、一般には、電磁場からエネルギーを回路内に結合する任意の方法とすることが可能である。タグ110に結合されている読取装置100から取り出される交流(「AC」)電力は電力変換装置703内で整流され、得られた直流(「DC」)はタグ110への給電に使用され、またタグ・エネルギー・モニタ704としても使用され、これによりさらに、通信が可能になる(それらの要素については後述する)。状態コントローラ705は、タグ・データ220および通信チャネル選択ブロック240上で動作し、送信情報を出力し、これは、チャネル変調装置708の制御の下で伝送素子702(当業でよく理解されている負荷変調素子など)に適用される。
【0037】
各タグ110に格納されるデータ220は、通常、低複雑度(つまり、低コスト)回路内に格納され、読取装置100からの問い合わせに応答する。各タグ110、120、1
30は、通常、第1の所定の条件が満たされるまで待ち、達した後、本発明によりその情報を複数経路アルゴリズムで伝達する。第1の所定の条件は、通常、タグ110、120、130のそれぞれについて同じに設定されているが、他の実施形態ではランダムに選択したり割り当てたりすることも可能である。タグ伝送状態を示す一般的流れ図の例を図8に示す。この流れ図では、さまざまな測定基準により第2の所定の条件を満たすことが可能である(例えば、第1の所定の条件を満たすことが不可能になったか、または第2の所定の条件が満たされた場合)。
【0038】
好ましい実施形態では、読取装置100は離れた場所からタグ110、120、130に給電し、タグ110の瞬間受電力レベルが所定の閾値(一般に703および704により決定される)を超えたときに第1の所定の伝送状態に達する。図9は、この動作の流れ図であるが、T1およびT2は第1および第2の電力レベル閾値を表す。当業者であれば、本発明の精神から逸脱することなく、他の所定の条件(特定の同期パルスまたは疑似ランダムな休止など)を使用する実装を採用可能であることに注意されたい。(受動的タグについては離れたところにある読取装置100から、または能動的タグについては内蔵電源により)タグ110に電力が届くと、タグ110は、受信信号強度を連続的に監視し、伝送の開始時期を判別する。タグ110がデータの変調および伝送250を開始すると、タグは完全に起動する。システムの好ましい実施形態において、複数のタグ110、120、130は通常、指定時間に完全に起動する。
【0039】
グループ内の完全に起動したタグは、第2の所定の伝送状態に達するまで、その情報を複数の経路(後述する)で送信する動作を続け、達したら、データ伝送を停止する。タグ・エネルギー・モニタ704により観察されたようなタグ110の受信電力レベルが第1の所定の閾値よりも下がるか、または通常は第1の所定の閾値よりも高く設定されている第2の所定の閾値を超えた場合に、好ましい実施形態における第2の所定の伝送状態に達する。
【0040】
このようにして、第1および第2の所定の伝送状態は、タグの各グループが通常、完全に起動する、ある範囲の受信電力レベル(例えば、枠(window))を形成する。本発明の好ましい実施形態では、パワーオン範囲(power−on range)は通常、約3dBの幅であり、タグ110、120、130は1〜2X(ある正規化された受信動作電力レベルに関して)の範囲の電力に応答する。この給電枠(powering window)により、一般的に、タグの伝送は比例して狭くなる電力枠(power window)内に収まり、したがって、(例えば、非直交拡散符号を使用するスペクトル拡散システムのように)一部の通信システムに影響を及ぼす通常の遠近問題が緩和される。
【0041】
好ましい実施形態では、システム内のタグ110、120、130はすべて、通常、同じパワーオン範囲を割り当てられるが、他の実施形態も可能であり、プログラム可能(例えば、事前割り当てされているが、異なる場合がある)またはランダム・パワーオン状態を利用するものなどがある。このような例の1つは、異なるメーカーに異なるパワーオン範囲レベルが割り当てられている場合に生じることがあり、異なるメーカーの製品同士を何らかの形で分離する(または区別する)。
【0042】
説明しているシステムのさらに他の実施形態では、双方向通信機能を持つタグが存在する場合があり、その場合、第1および第2の所定の伝送状態は、ある種の同期パルスまたはその他の信号送出情報からなる。所定の伝送状態がランダムである場合、タグ110上で、またはタグ110のプログラム時に、ランダムに決定可能である。今度もまた、本発明の精神から逸脱することなく、これらの伝送制御の他の実装(例えば、同期信号、タグとの双方向通信など)も可能であることに注意されたい。
【0043】
図10に示されている実施例では、読取装置100は、コントローラ1001により本社から遠隔制御することが可能である装置であり、棚1005に据え付けられているアンテナ1004に伝送媒体1003を介して接続されている。物理的寸法が異なる物体1020、1021、1022において、タグ110、120、130がパッケージのさまざまな部分に配置されているため、読取装置100に関連付けられているアンテナ1004とタグ110、120、130に関連付けられているアンテナ701との間の結合がばらつくことになり、その結果さらに、タグの電子回路1012では異なる電力レベルが受信されることになる。システム内の読取装置のアンテナ1004とさまざまなタグ110、120、130との間の結合特性が異なるため、タグが異なれば、与えられた読取装置アンテナ励起レベル(つまり、読取装置送信電力レベル)に対する受信する電力レベルも異なる(範囲境界線1030と1031により示されている)。さらに、さまざまなタグ110、120、130が異なる読取装置送信電力レベルで、したがって異なる時間に送信を開始するので、このような効果を利用して好ましい実施形態のシステム内に存在するタグの点数をおおよそではあるが減らすことが可能である。しかし、本発明の好ましい実施形態では、複数のタグ110、120、130はそれでも、通常は、特定の電力レベルに対し同時に伝送を開始することに注意されたい。例えば、識別する必要のある商品(タグ)が在庫中に1000点あり得、読取装置100は、1ステップずつ、10個の異なる可能な電力レベルを辿り、各電力レベルでおおよそ100個のタグからなるグループを起動することが可能である(ただし、それよりも少ないタグも、場合によっては、上限および下限の電力レベルで起動される)。本発明の他の実施形態では、複数のタグからの伝送は、送信する特定のタイムスロット(共通の基準に関して)をユーザが選択するタイムスロット化された(チャネル化)システムの場合などにのみ(必ずしも同時でないが)同期処理可能である。1実施形態では、読取装置100は、最低の送電力レベルからスタートして、1ステップずつ、すべての可能な送信電力レベルを辿ることに注意されたい。したがって、タグ110、120、130の特定のパワーオン範囲により、タグの各グループによる伝送の開始および終了を効果的に制御する。この態様は、特定のパワーオン範囲内(例えば、1030から1031の間)のタグ110、120、130のすべてが一意に識別されたときに読取装置100がそのことを判別し、そのときに、次の電力レベル(例えば、1031の上)に1ステップ進むか、または識別工程を終了することが可能である。
【0044】
他の実施形態では、読取装置100は、与えられた在庫プロファイル(inventory profile)に対するある範囲の予想電力レベルを「学習」つまり記憶し、活動の履歴とともに電力レベルに与えられる優先度とともにそのパワー・スイープ(power sweep)をアレンジすることが可能である。後述のように、読取装置100が、起動しているタグがない電力レベルに1ステップ進むと、その状態が感知され(通常は、短いエネルギーまたは変調検出測定を通じて)、次の電力レベルに迅速に1ステップ進み、タグの全読み取り時間を最小にする。
【0045】
III.チャネルの選択および伝送方法
複数の送信元(またはマルチユーザ)通信方法はすべて、本発明のようなある種のチャネル化方法を使用している。本発明では複数のチャネル化方法または手法のうちどれか1つを使用し得る。一般に、本発明で使用しているチャネル化方法は、直交チャネル化方法(orthogonal channelization methods)または疑似直交チャネル化方法(quasi−orthogonal channelization methods)の2つのカテゴリに分類可能である。
【0046】
直交通信チャネルには、選択したチャネル上の通信はリニア・システム内の他のチャネルの通信と(全く)干渉しないという利点がある(つまり、異なるチャネル間の相互相関は0と定義される)。疑似直交チャネルはほぼ直交し(例えば、異なるチャネルについて
相互相関値が0に近い)、通常は、直接系列符号分割多元接続(direct−sequence code division multiple access)(DS−CDMA)システムで使用され、その場合、各ユーザは通常、異なる拡散符号が割り当てられる。
【0047】
当業では、最大長リニア・フィードバック・シフト・レジスタ(linear feedback shift register)(「LFSR」))系列(つまり、m系列)の異なる位相(つまり、タイム・シフト(time shifts))の相互相関特性は低い(つまり、疑似直交する)ということがよく知られている。2つの揃えられていない系列の相互相関値は、−1/N(正規化)と定義され、NはLFSR疑似雑音(「PN」)系列の長さである。同じ基底のm系列の異なる符号位相は、符号分割多元接続システムの異なるユーザをチャネル化するために使用されることが多い。PN系列内の各シンボルまたはビットは、通常、当業でよく知られているように、「チップ」と呼ばれる。
【0048】
直交チャネル化関数の例として、Walsh関数、スロット化システム内のタイムスロット、周波数分割システムにおける周波数、特別に補強されたPN符号などがある。疑似直交チャネル化関数の例としては、上述のようなm系列またはPN系列がある。
【0049】
特別に増大されたPN符号の例として、時間的整合をとった(つまり、同期した)人為的に挿入された0がチャネル上に同じ時間オフセットで現れ、その結果同じm系列の異なる符号位相間の相互相関値が0となるように、系列の中に(符号の位相に応じて系列内の異なる位置に)人為的に挿入された(つまり、LFSRの通常の操作で生成されていない)2進値0を持つものがある。本発明の好ましい実施形態では、同期しているシステムにおいて、これらの特に増大されたm系列(生成の仕方は図11に示されている)を使用して直交符号チャネルを取得することに注意されたい。使用したスペクトル拡散手法の他の利点として、通信技術ではよく知られているように、干渉に対する抵抗(処理または拡散利得とも呼ばれる)も得られる。工場への設置など苛酷な電磁環境では、このような手法を適用することが重要である。
【0050】
上述のように、説明しているシステム内のタグ110、120、130によるデータ送信では、複数経路アルゴリズムを利用する。複数経路伝送アルゴリズムは、タグ110、120、130の全読み取り時間を決定する際に重要なものであり、複数の異なる態様からなる。このアルゴリズムで採用している一般的な考え方は、各タグ110、120、130は各アルゴリズム経路で通信用に特定の(好ましくは一様ランダム)チャネルを選択するというものである。
【0051】
説明しているシステムの好ましい実施形態では、チャネル選択240は、通常、タグ110に格納されているデータ220に直接基づいている。その後、通常、タグ110は情報(つまり、識別データ)を好ましい実施形態では選択したチャネル上でアルゴリズムの次の経路になるまで送信し、次の経路で、新しいチャネルを選択し、工程を繰り返す。本発明の好ましい実施形態では、(第1の所定の条件によって)タグの伝送はおおむね同期していると仮定される。
【0052】
各タグによるチャネルの選択は、所定の情報に基づく(つまり、通常実施形態ではタグ・プログラミング230で、または場合によってはタグ自体の設計で決定される)。本発明の好ましい実施形態では、各タグ110のチャネル選択は、(以下で詳述するように)タグ110に格納されている識別データ220から直接(アルゴリズムによる方法で)決定される。さらに、他の実施形態では、上記の所定の情報はタグ110に格納されているデータに直接は基づかない乱数を含むことが可能であることに注意されたい。
【0053】
上の第I節で詳しく説明したように、本発明の好ましい実施形態では、適切なシステム性能を実現する鍵として、タグ110上に格納する(230)前に、データ200(例えば、EPC、CRCなど)の少なくとも一部をあらかじめランダム化(またはスクランブル)する必要がある(211)。タグ110では本質的に、格納されているデータ220、またはその一部(例えば、221、222)を使用し、複数経路アルゴリズムの各経路で通信チャネルを選択するので(240)、総合的システム性能を最大にするためにデータ220が一様ランダムのように見えることが重要である。これは、上の第I節で詳述した低複雑度の可逆スクランブル・アルゴリズム211を通じて実現される。
【0054】
特に、図12に示されているように、好ましい実施形態の複数の伝送経路のそれぞれでのチャネル選択工程240は、事前にスクランブルした(つまり、ランダム化され格納されている)データ220の所定の部分集合(例えば、221、222、223、224)を利用して各経路内の通信チャネル240を選択することにより実行される。整流器または多重化デバイス1240などのチャネル・セレクタ1220は、通常、チャネルを選択する。タグ220に格納されているデータの新しい部分集合221、222、223、224(つまり、新しく乱数を引く)は、通常、アルゴリズムの後続のそれぞれの経路でチャネル選択に使用され、複数経路伝送アルゴリズム全体を通してチャネルをランダムにかつ独立に選択することが可能である。
【0055】
タグ110は、各アルゴリズム経路でデータ220のすべてを送信するか(好ましい実施形態など)、またはデータの一部のみを送信することが可能である(つまり、一般に、次の経路でタグによって使用されるチャネルを決定可能なだけの十分なデータが送信される)ことに注意されたい。通常、アルゴリズムの各経路のチャネル選択に使用されるデータの一部221、222、223、224は、データ220の一意的な連続するセクションであり、好ましくは事前にランダム化される。複数経路伝送アルゴリズムの複数の経路に対するチャネルの特定の選択のことを、「チャネル選択プロファイル」と呼ぶ。
【0056】
例えば、128ビットの事前にスクランブルされた識別データ220が各タグに格納されるシステムでは、8ビットの一意的ではあるが順次連続するセクションを使用して、16(つまり、128/8)のアルゴリズム経路のそれぞれにおける256(つまり、28)のチャネルの1つを選択することが可能である。したがって、各タグに対するデータの第1のランダム化されたバイト(例えば、221)により、アルゴリズムの第1の経路上でそれぞれ各タグの通信チャネルを選択し(240)、各タグに対するランダム化されたデータの第2の(および望ましくは異なる)バイト(例えば、222)を使用して、アルゴリズムの第2の経路上で伝送用のチャネルを選択し(240)、というように続ける。この複数伝送経路工程は、タグに格納されているデータすべてが尽きるまで(例えば、この例では16番目の経路が完了するまで。図2では、これは224に対応する)、または読取装置100がタグに伝送停止を指示する信号を送信するまで(一般に、上述のように704(1210)で第2の所定の条件が満たされることによりタグ110で感知される)続行する。データが尽きたら、任意選択により工程全体を繰り返すことが可能であるが、通常はタグは同じ(決定論的な)チャネルを選択する。不可避的に発生する衝突をランダム化するために各タグについて各アルゴリズム経路に対しランダムな一意的に決定されたチャネルを選択することが望ましいことにもう一度注意されたい(詳細については以下の第V節を参照)。
【0057】
もちろん、当業者であれば、データの他の(例えば、非連続または完全には一意でない)セクションを使用して、各経路の通信チャネルを直接的にまたは間接的に選択することが可能である。このようにして、実質的に制限なしで、チャネル選択の繰り返しの前に最大数のアルゴリズム経路を拡張することが可能である。ある回数の伝送経路の後にチャネル選択プロファイル(またはチャネル選択アルゴリズム)を修正し、同じデータ220の
異なる部分集合を後のチャネル選択1220に使用することが可能である(パターンの反復が発生する前に一意的なチャネル選択を拡張するため)。例えば、複数経路伝送アルゴリズムの16経路の後、チャネル選択データ(つまり、所定のデータ)を4ビット(上の例で)だけシフトすることで、アルゴリズムの後続の経路に対する新しいチャネル選択に達するようにすることが可能である。このようにして、タグ回路の複雑度は増すが、実質的に制限なしで、一意的なチャネル選択の数を増やすことが可能である。
【0058】
チャネル選択アルゴリズムのさらに他の実施形態では、ある種のマッピング(一般的には、1対1ルックアップ・テーブルまたはその他の代数または論理)関数を適用して、タグ上に格納またはプログラムされている(一般的には制限されている)データからチャネル選択を決定することも可能である。チャネル選択工程で重要な唯一の特性は、チャネル選択は、タグ内のデータに関して情報の一部が知られていれば、読取装置100内で計算可能になるという点である。
【0059】
チャネル資源は限られているため(つまり、それぞれのユーザが複数経路通信アルゴリズムで選択可能であるチャネルの数が限られている)、不可避的に、送信側タグに衝突が生じることになる。衝突は、2つまたはそれ以上のタグが特定のアルゴリズム経路で同じチャネル上の通信を選択する場合として定義される。このような状況は、通常のシステム・オペレーションの下で予想される。例えば、25個のタグが64本のチャネル上で通信を行う標準的なケースについては、衝突が少なくとも1回発生する確率は、経路1回毎に99.6%である。これは、N本のチャネル上でM個のタグが通信している場合に、衝突が発生しない確率に対する式は、
【0060】
【数1】
#1 P{衝突なし}
であるという事実に基づく。
【0061】
タグ伝送衝突のいくつかの数値例とその対策について、以下の第V節「衝突緩和方法」で説明する。
多くの場合、システム内に存在するタグの数(特定のパワーオン・レベルの)は、利用可能なチャネルの数を超えることすらありえる(特に、好ましい実施形態のアルゴリズムの始めのほうの経路で、または利用可能なチャネルの数が後述のように低く設定されている場合)。このような状況は、本発明では、直交チャネル化手段を使用した場合に完全に許容可能であるものである。通常のDS−CDMAシステム(疑似直交チャネル化符を使用する)は、その時点で過負荷になっていると考えられ、信頼し得る通信はいっさい行われない可能性があることに注意されたい(特に、タグの伝送特性について詳しい情報がない場合)。説明されているシステムでは、アクティブにされたタグ母集団は、以下の第V節で詳しく説明している、衝突緩和手法によりさらに効果的に減らすことが可能であるということが重要である。
【0062】
また、本発明の好ましい実施形態では、複数経路伝送アルゴリズムの1経路当たりさまざまな個数のチャネル(221、222、...224により一般に決定される)を使用し、総合的システム性能(例えば、全読み取り時間、全システム容量、信頼性など)を改善することもまた重要なことである。つまり、複数経路伝送アルゴリズムの一方の経路で利用可能なチャネルの個数は、伝送アルゴリズムの他方の経路で利用可能なチャネルの数
と異なる可能性もあるということである。アルゴリズム経路当たりの(つまり、単位時間当たりの)チャネルのさまざまな個数は、この説明では、利用可能なチャネルの個数は時間により動的に変化するため動的チャネル・プロファイル(dynamic channel profile)と呼ばれる。動的チャネル・プロファイルを実装することで、本質的に、予想されるタグ母集団の全伝送時間(または全読み取り時間)が最適化される。
【0063】
アルゴリズムの各経路に対する伝送時間は通常、アルゴリズムのその経路に利用可能なチャネルの数に比例することに注意されたい(使用するチャネル化方法に関係しない)。複数経路伝送アルゴリズムの総伝送時間(TTX)は、
【0064】
【数2】
で表すことが可能であり、Lはデータを正常に送信するために必要な伝送経路の数、Rは伝送(信号送受信またはチャネル・シンボル)レート、Biは1パス当たり送信されるデータ・シンボルの個数、Niはアルゴリズムのi番目のパス(または拡散利得)で利用可能なチャネルの個数である。本発明の好ましい実施形態では、Lは16経路と大きく、Biは128ビットに固定され、Rは62.5KHzに等しく、特定のNi値は上の例で与えられた値であるが、これは、システムの1つの特定の実施形態にすぎないことに注意されたい。1経路当たりの使用可能なチャネルの個数(Ni)は、以下のように(240にも示されているように)一般に、各経路(ni)内の通信チャネルを選択するために使用されるビットの数に依存することに留意されたい。
【0065】
【数3】
システムの好ましい実施形態では、Niは1経路当たりの利用可能な符号位相の拡散利得および個数を表し、Rは毎秒チップ数単位の信号送受信レートである。高度な衝突緩和手法(以下の第V節で説明している)を適用することにより、タグ110、120、130からの伝送経路の必要な個数(L)を大幅に減らすことが可能であることに注意されたい。一般に、説明しているシステムの他の実施形態では、上の式の中の値に制限はない。
【0066】
1経路当たりの伝送時間は図に示されている好ましい実施形態の1経路当たり利用可能なチャネルの数(およびシンボル・レート)に依存しているため、複数経路伝送アルゴリズムの前のほうの経路のより少ないチャネルを使用してシステムの全読み取り(つまり、取得)時間性能を高めることが可能である(このような場合システムにさらにチャネルを追加しても、タグが少ないためほとんどメリットはない)。アルゴリズムの後のほうの経路(潜在的には複数のステップ)でチャネル数を増やすことにより、より多くのタグがシステム内に存在するケースに対応することが可能であり、また読取装置100は、以下の第V節で述べているより高度な信号処理(例えば、高度な衝突緩和)手法を採用しない。
【0067】
このようにして、存在するタグが少ないシステムだと、(前のほうの)チャネル選択の数が多いシステムの伝送時間が長くなるというペナルティは、通常、発生せず、それと同時に、存在するタグが多いシステムでも、著しいペナルティが発生することもない(複数
経路アルゴリズムの前のほうの経路は通常、最初に利用可能なチャネルの数が少ないためかなり短時間になるため)。また、後のほうのアルゴリズム経路のチャネル選択数を増やすと、タグが多数存在するシステムは限られた数のアルゴリズム経路で確実にすべてのデータを正常に取得可能である(したがって、システムの信頼性が増す)。
【0068】
例えば、本発明の好ましい実施形態では、128ビットのデータ220を使用しており、第1と第2のアルゴリズム経路には32のチャネルがあり、3番目から6番目までのアルゴリズム経路には64のチャネルがあり、7番目と8番目の経路に128のチャネルがあり、残り8つのアルゴリズム経路に1024のチャネルがある。ここでもう一度、この実施形態では、データ220の一意的な部分集合を使用して、各経路内の通史にチャネル1260を直接選択し(1220)、またデータの一意的な重なり合わない部分が尽きるまでに最大16のアルゴリズム経路が実行されることに注意されたい。本発明の他の実施形態では、所定の数の経路の後に変わる1伝送アルゴリズム経路当たりの可変個数のチャネルを使用することが可能である。例えば、上記の例の複数経路伝送アルゴリズムの第1の16の経路では、32〜256の利用可能なチャネルからのどの場所をも使用可能であり(つまり、チャネル選択データの5から8ビット)、次の16の経路では、256〜4096の利用可能なチャネル(つまり、8〜12ビットのチャネル選択データ)からのどの場所をも使用可能である。このようにして、実質的に制限なしで、動的チャネル・プロファイル(または、1アルゴリズム経路当たりの利用可能なチャネルの数)を拡張可能である。またここでも、データの重なりあう部分または交互配置されている部分を利用してチャネル選択アルゴリズムを駆動することにより経路の最大数を増やすことが可能であることに注意されたい。
【0069】
このシステムの特定の実施形態における1アルゴリズム経路当たりの利用可能なチャネルの個数(動的チャネル・プロファイルともいう)の実際の選択は、さらに(システム内に存在するタグの予期された個数に加えて)読取装置100で使用される信号処理アルゴリズムの予期された種類または主要な種類(衝突緩和アルゴリズムの種類など)によって異なる。1アルゴリズム経路当たりのチャネルの数はさまざまなので、チャネル・プロファイルは後のほうの経路で減少することがあることに注意されたい。一般に、時間に応じて変化するチャネル・プロファイルは、本発明の目的に関して、動的チャネル・プロファイルと考えられる。
【0070】
特定のタグ110のチャネル・プロファイルは必ずしも、読取装置100によりアプリオリに知られていなければならないわけではないが、一般的には、そういう場合があることに注意されたい。タグ110のチャネル・プロファイルが知られていないと、読取装置100では、例えば(場合によっては、自己相関またはスペクトル特性を測定して)PN(チッピング(chipping))系列の周期を確認し、それに応じて動作(復調)するようにしなければならないであろう。
【0071】
特に、本発明の好ましい実施形態では、ランダムなチャネル選択を使用し、複数パス伝送アルゴリズムの各経路で特定の拡散符号(または1220で符号チャネル)を選択する。さらに具体的には、好ましい実施形態では、タグ110に格納/プログラムされているデータ220の一部を使用して、長さNの特に増大されたm系列の時間オフセット(または1220のように符号位相)を直接指定する(ただし、Nは上述のように、特定のアルゴリズム経路のチャネルの数に等しい)。この工程の概略が、図11に示されている。PN系列の異なる位相は、一般に、2つまたはそれ以上のm系列の2を法とする総和を効果的に計算し、同じm系列の第3の符号位相を出力する、PN生成器(LFSR)状態のマスク関数(またはAND−XORリダクション・ネットワーク(AND−XOR reduction network)1100)を適用することにより得られる。したがって、タグ110、120、130の伝送のすべてが知られている基本初期生成器状態に同期
するように、タグ110、120、130ではすべて、各アルゴリズム経路内で、同じ初期生成器状態から始まる、同じ基本LFSR(m系列)生成器を使用する。これらの態様は、以下の第IV節で説明しているように、読取装置100で素早い効果的復調を行ううえで重要である。基本LFSR系列生成器の長さ(つまり、プリミティブ多項式)は、通常、上述のように、1アルゴリズム経路毎に動的に変化する(チャネルの数が変わる)ことに注意されたい。
【0072】
従来のm系列生成器は、通常、好ましい実施形態において第1のチップ(またはPNビット)時間について0出力を強制することにより、特別に増大されたPN系列生成器になり、異なるタグからの系列の相互相関は与えられた系列周期にわたって必ず0になる。また、他の時点に強制的に0を符号系列に入れると、直交する系列が出力され(他のシステムと同様)、他の実施形態では他の種類の直交関数生成器をLFSR PN生成器(例えば、WalshまたはHadamard関数)の代わりに使用することも可能であることに注意されたい。その後、タグ110に格納されているデータ220は、従来の手段1230を使用し、生成された拡散符号1260により拡散される(例えば、当業者であればよく知っているように、デジタル実装ではXORゲート、またはアナログ実装では除算器)。次に、アクティブにされたタグの拡散データ信号は、与えられた通信チャネル上で(まとめて)送信される。
【0073】
タグはデータの送信にある範囲の変調タイプを使用することも可能であることに注意されたい(例えば、振幅変調、位相変調、周波数変調、またはそれらの組み合わせ)。本発明の好ましい実施形態では、伝送要素702を介して負荷変調からある形式の振幅偏移変調(「ASK」)を使用するが、他の変調タイプおよび実装も確かに可能である(例えば、差動直交位相偏移変調、直交振幅変調、パルス符号変調、パルス振幅変調、パルス位置変調など)。本発明では、さまざまなデータ符号化およびマッピング手法を使用することも可能である。符号化手法の例として、ゼロ復帰(RZ)、非ゼロ復帰(NRZ)、マンチェスタ、および差動符号化があり、当業ではすべてよく知られている。当業者であれば周知のように、本発明では、一般性を失うことなく、さまざまな種類の符号化、変調、符号および信号送受信を使用することが可能であることに注意されたい。符号手法の例としては、CRC符号、畳み込み符号、ブロック符号などがあり、これらもすべて、当業ではよく知られている。
【0074】
また、好ましい実施形態のタグ110、120、130は伝送要素702を介して読取装置100により供給される搬送波を直接変調するため、局部発振器はない(しかし、局部発振搬送波を使用することも、確かに、本発明の範囲内で可能であり、いかなる形でも応用を制限することはない)。本発明の好ましい実施形態では、電力変換装置703が読取装置100からの搬送波信号を整流し、読取装置100が離れた場所からタグ110上の回路に電力を供給する。能動的に電力を供給するタグを使用することも可能であり、いかなる形でも本発明の使用を制限することはないことに注意されたい。本発明の一般的な目標は、タグ110の複雑度を最低限に抑えることであり、好ましい実施形態の説明されている手法を使用することにより、タグ110の回路を最小に保つことが可能である。
【0075】
IV.高速復調方式
図13に示されているように、読取装置100は通常、送信レベル制御装置1320および増幅器1330により信号源1310の出力を初期化し、何らかの最小レベルの電力を送信することにより、タグ110、120、130の読み取り工程を開始する。好ましい実施形態では、次に、読取装置100はそのレベルの連続波の送信を開始する。読取装置100が特定の電力レベルで送信し始めると、通常、タグ110、120、130から戻る信号を監視する(結合デバイス1340およびアンテナ1345により)。この活動検出は、可能な通信チャネル(以下で詳述する)のそれぞれで信号レベルまたは信号振幅
を検出するなどの、変調またはエネルギー検出測定の形を取り得る。この測定期間は、可能な限り短くするのが望ましく、特定の電力レベルでアクティブにされているタグがない場合、読取装置100は迅速に、次の電力レベルに1ステップ進むことが可能である(一般的には、増加する方向で)。特定の送信電力レベルで信号が感知された場合、読取装置100は完全な復調処理1390を開始し得る(場合によっては、以下の第V節で説明しているように、衝突緩和手法を採用する)。システムの他の実施形態では、一般性を失うことなく、読取装置100は、変調された搬送波信号、同期パルス、または非同期搬送波形を送出することも可能である。
【0076】
読取装置100により実行される信号処理は、ハードウェアまたはソフトウェアアーキテクチャ、またはそれらの組み合わせにより実行し得る。代表的な実施形態として、何らかの選択性1365、増幅1370、アナログ・デジタル変換1375、およびDC取得および利得制御関数1380がある。一般に、読取装置100は与えられた送信経路内で可能な通信チャネルのそれぞれを巡回し(順次または同時)、それぞれに対する信号エネルギーを探索する。当業者であれば周知のように、信号の存在を検出し、衝突の有無を検出するための方法が多数利用可能であるが、それは変調および信号送受信の種類によってさまざまである。一般に、読取装置100はさらに、いくつかの実施形態では、搬送波信号の能動的または受動的抑制1360を実行し、干渉または雑音除去を行うことも可能である(システム内の望むタグ以外の発生源からの任意の形の干渉について)。
【0077】
上述のように、本発明の好ましい実施形態では、タグ110、120、130でスペクトル拡散変調を使用する。したがって、当業でよく知られているように、受信したデータは、まずそれぞれの可能な拡散符号を適用して書く符号チャネルについて読取装置100内で逆拡散しなければならない。
【0078】
より具体的には、本発明の好ましい実施形態ではタグ110内の拡散系列として特別に増大されたm系列を使用しているため、非常に高速で、効率がよく、新規性のある復調(つまり、逆拡散およびチャネル化)手法を、読取装置復調処理1390で利用することが可能である。これらの手法を使用すると、実質的に、読取装置復調処理1390内で必要な処理能力が低減され(例えば、好ましい実施形態では約57倍)、その結果、読取装置100の読み取り時間が短縮され、実装コストも低減される。処理に関する実際の節約がどれだけかは、複数経路システムの各経路内で使用されるチャネルの数によって決まり、これは、従来の逆拡散オペレーションの回数と1シンボル当たりの改善された逆拡散オペレーションの回数との比に等しい係数(F)に関して表すことが可能であり(受信系列の順序変更と高速Hadamard変換(FHT)の新規性のある組み合わせを使用して)、
【0079】
【数4】
Lは、送信元データを正常に復調するために必要な経路の数に等しく、Niは(ここでもまた)i番目の経路内のチャネルの数に等しい。この係数は、直接、読取装置復調処理1390内の処理の節約程度(通常は、毎秒100万回オペレーション(MOPS)または毎秒100万命令(MIPS)で表される)を表す。したがって、この例では、57倍能力が低い(例えば、10MOPS対570MOPSの)プロセッサ1390を、最良のケースの好ましい実施形態の読取装置100で使用することが可能である(後述のように衝突緩和はない)。
【0080】
特別に増大されたm系列(図11のボックス1120に示されている)は従来のPN系列の直交拡張であり、直交Walsh符号(図14のボックス1420に示されている)といくつか類似点がある、つまり、この2組の系列は同じ数の2進数の1と0を系列内に含むということに留意されたい。実際、この2種類の系列(つまり、特別に増大されたm系列およびWalsh系列)は単一の特別順序変更関数を使用して関連付けられている。この特別な順序変更関数は、図15の読取装置受信器ブロック1520内の基底m系列を(タグ系列生成器1110で示されているように)生成するために使用されるプリミティブ多項式から直接導かれる。この系列順序変更関数1510を使用することで、受信デバイス1375によるデータ・サンプル(または要素)の受信時にそれらのデータ・サンプル(要素)の順序を直接変更する。受信デバイス1375は、アナログ・デジタル・コンバータ、アナログ・サンプル&ホールド・デバイス、レジスタ、または信号を受信するその他のデバイスとすることも可能である。単一の系列順序変更1510関数は、複数の複合チャネル(または110のように符号位相)を使用する複数のタグ110、120、130からの伝送からなる複合受信信号に適用されることに注意されたい。
【0081】
メモリ・バッファ1530などの記憶媒体内で受信系列の順序が変更された後、これは、1組の有効なWalsh系列からの系列に類似しており、高速Hadamard変換(FHT)などの高速変換手法を使用し、すべてのデータ・チャネルについてタグ110からデータを迅速に(かつ同時に)(1540に示されているように)逆拡散することが可能である。FHTは、当業でよく知られているように、一揃いのWalsh符号に対するデータ系列の相関関係を(並行して)高速に求めるために使用される。本発明の精神から逸脱することなく、FHTに関係する変換(例えば、高速Walsh変換、Walsh−Hadamard変換、再帰的Walsh変換など)を説明した高速相関関係決定方法とともに使用可能である。また、説明している処理手法はすべて、アナログまたはデジタル信号処理の分野で実行することが可能であることに注意されたい。
【0082】
従来のFHTアルゴリズム(例えば、ボックス1410に示されているような)に関する文献は十分にあり、基本的なカーネル・オペレーション(ボックス1400、「バタフライ」と記されている)が図14に示されていることに注意されたい。基数2のFHTバタフライは基数2のFFTバタフライに似ているが、これは、データ要素と+1および−1の値だけの乗算(またはそれと同等の、データ値の加算と減算)からなる。8×8 FHTの格子構造1410も図に示されている。FHT 1550の各出力は、FHTビンまたはFHT符号チャネルと呼ばれる。FHTは高速変換なので、従来の相関を上回る処理の節約(上で表されている係数Fに似ている)はN点直交系列に対して(N2/N log N)に等しいことを証明することが可能である。この同じ節約は、説明した高速相関決定手法を使用して実現される。
【0083】
正確な受信データ順序変更関数1520は、タグのフィボナッチLFSR(1110に示されている)は通常オペレーション時に巡回する状態を観察することにより決定される(以下の例も参照)。LFSRが進行する状態は、着信(拡散)受信データ・サンプルを、時間内に(直線的に)受信されたときに受信データ・メモリ・バッファ(1530または他の記憶媒体)に格納しなければならない間接アドレスに直接対応している。この(1520内の)アドレスの系列は、受信器内で能動的に生成されるのではなく、記憶媒体(例えば、ランダム・アクセス・メモリ、読み取り専用メモリ、ハード・ディスク・ドライブなど)に交互に格納することが可能である。このようにして、受信したm系列(またはm系列の総和)の順序を変更し、Walsh系列内の要素(またはより具体的には、Hadamard行列内の行)を正確に表すようにする。したがって、従来の高速(Hadamard)変換(相関)方法を使用して(1540で)、受信データ・チャネルを並行して逆拡散することが可能である。このデータ系列はさらに、メモリ内にダブル・バッファ
リングし、処理待ち時間に合わせることが可能であることに注意されたい。
【0084】
信号エネルギーを示すFHTの出力インデックス(またはビン)1550は、タグ110、120、130のAND−XORリダクション1100で使用されたマスク値1130(2進数で表した場合)に直接対応する。例えば、チャネル選択符号1130(図11に示されている「c0−c4」)(送信器処理)は、図15のFHTブロック1540の能動的出力1550(受信器処理)に直接対応する。特定の符号チャネル(または符号位相)を選択するために、バイナリ・マスク値(binary mask value)1130がタグ110内で適用されることに留意されたい。これは図7にも示されており、マスク710はタグ・データ240からチャネル選択240へと描かれている。つまり、バイナリ・マスク値1130(およびFHTビン・インデックス(bin index))は、特定のパスでチャネルを選択するために使用されたタグ110に格納されているデータ221、222、223、224に直接対応している(タグ・データとチャネル選択との関係の補助的説明については図17および図18の識別子1710、1820、1830、および1840も参照)。各タグ110は、好ましい実施形態の複数パス・アルゴリズムの各パスの継続時間中にそのデータ220を固定されたチャネル1260で送信する。各FHTビンの出力信号レベルは、逆拡散後の各符号チャネル1260(例えば、符号位相毎に)上の信号レベルに直接対応する。以下で詳述するが、受信データ系列のチャネル選択部分での各アクティブなFHTビンの出力のデータ信号1550は、バイナリFHTインデックス値と照合することにより検証することが可能である(なぜなら、2つのデータ系列は有効データに対して照合すべきだからである)。この手法は、複数パス伝送アルゴリズムのパス#2について図18に示されている。第2のパスに対するチャネル240を選択するために使用される部分222上のデータ系列1820、1830、1840は、FHTビン番号に相当する2進値であることに注意されたい。
【0085】
図15に示されている順序変更とFHTの組み合わせた手法を使用することで、この復調器により好ましい実施形態の可能なすべての符号チャネル(つまり、符号位相)を高速復調(つまり、逆拡散)することが可能である。(それぞれの潜在的データ・チャネルおよびシンボルに対する必要な逆チャネル化および逆拡散オペレーションに対応する)受信器内の受信したシンボル期間毎にNチャネルを復調するために、通常、N点FHTが必要であることに注意されたい。また、トランスポンダ・システムの他の実施形態では、チャネル化関数に直交Walsh符号を使用することが可能であり、その場合、FHTビンはWalsh符号チャネル・インデックスに直接対応する(そして、順序変更工程は必要でない)。しかし、Walshチャネル化符号は周期的であり、周期的干渉源と高い相関関係を持ちうるため、好ましい実施形態と比較したときに、このようなシステムはそれほどよい干渉除去能力を持たない。したがって、このシステムの好ましい実施形態では、特別に増大したm系列をチャネル化関数として使用し、また上述の復調手法を使用する。
【0086】
例えば、タグ送信器内で長さ16(N=16、N=4)の特別に増大されたPN系列を使用するシステムでは、2進数「0001」(1)のチャネル選択値1130(ni)により表される系列1260は、「0111101011001000」であるが、2進数「1001」(9)のチャネル選択(マスク)1130により表される系列1260は「0010110010001111」である(これは、先行0でその後特別に増大されている同じ基本m系列の異なるタイム・シフトまたは符号位相にすぎない)。23(標準8進数表記で表した場合)のプリミティブ多項式のタグPN生成およびマスク回路の例が図11に示されている。2つのタグ送信器は、これらの系列を独立に通信チャネル上で送信するものと仮定されている。読取装置受信器は、(図15に示されているように)特別な順序変更関数1520およびFHT処理を使用してこれら2つの信号を解決する。送信されたPN系列に対し使用しなければならない特別な受信データ・サンプル順序変更は、この例では、{0,15,7,11,5,10,13,6,3,9,4,2,1,8,12
,14、1120で示されているのと同じ}である。この系列は、タグ110内で使用されるm系列生成器1110を複製し、PN生成器の状態を観察するか、または必要な順序変更系列を単にメモリに格納するだけで、読取装置100内で生成することが可能である。順序変更系列を使用し、間接アドレッシングにより、入ってきた受信データ・サンプル・ストリームをメモリに格納する。例えば、読取装置に届いた第1の有効なA/Dサンプルは、記憶媒体1530のメモリ・バッファのロケーション0に格納され(すべての特別に増大された符号の場合と同様)、第2のサンプルはメモリ・ロケーション15に格納され、第3のサンプルはロケーション7に格納され、というように続く。N(この例では16)個のサンプルが受信されると、メモリ・バッファ1530内で新規順序変更されたデータ・サンプルに対し通常のFHT処理1540を実行することが可能である。順序変更関数は、上記の「0001」PN符号を系列「0101010101010101」(Walsh符号1と同じ)に変換し、「1001」PN符号を系列「0101010110101010」(Walsh符号9と同じ)に変換する。FHT 1540は、信号エネルギーが出力1550のビン1(チャネル符号1に対応する)およびビン9(チャネル符号9に対応する)内に存在している(例えば、タグが送信中である)ことを示す。そこで、ビン1とビン9のFHT出力を送信シンボル毎に観察することにより、タグ・データの残りを感知することが可能である。
【0087】
上述の手法は、受信器内で、たとえそのような信号が実際に送信されなかったとしてもタグ110により送信された第1のチップ(またはシンボル)が2進数0(チャネル上の+1正規化信号値に等しい)であると仮定することにより、従来の(つまり、特別に増大されていない)m系列に対し使用することが可能であることに注意されたい。したがって、記憶媒体1530内の第1のバッファ・ロケーションは+1値に初期化され、処理(つまり、順序変更1510およびFHT 1540)は通常のように続行する。このようにして、従来のPN系列の複数符号チャネル(または符号位相)に対する相関関係を非常に高速に求めることが可能である。他の通常増大されているPN系列に対しても、追加チップ(例えば、上記の第1のチップ以外)が系列内に挿入される場所を追跡することにより受け入れることが可能である。
【0088】
上記の高速相関決定手法(つまり、特定の受信系列順序変更1510およびFHT 1540)を、AND−XORリダクション・ネットワーク1100により生成することが可能なPN系列(そのようなネットワークで生成されようとされまいと)を使用する通信システムに適用する。多くの普及している通信システムでは、これらの種類のPN系列、または従来のm系列の組み合わせから生成された系列を使用する(当業でよく知られているように、Gold符号など)。このようなシステムの例として、IS−95、IS−2000、3GPP CDMA携帯電話システム、およびGPS CDMA位置決定システムがある。上記の高速相関決定手法は、それらのシステム内でも等しく効果的である可能性がある。
【0089】
いかなる場合も(採用されている除去手法に関係なく)、複合受信信号は、受信器のフロントエンド1610内で濾波し、増幅してから、図16に示されているように読取装置100内でチャネル化(または逆チャネル化)1620しなければならない。その後、各チャネルは、一般に、信号および衝突検出を目的として別々に(ただし場合によっては同時に)処理される(一般的に1630)。例えば、説明しているm系列の代わりにWalsh符号を使用するシステムの他の実施形態では、上記のように、FHTオペレーションをそのまま使用して、異なるデータ・チャネルすべてを同時に復調することも可能である。システムの他の実施形態では、1バンク分の(並列または時分割方式の)従来の逆拡散器を(1540、1620の代わりに)使用して、逆チャネル化および逆拡散工程を実行することが可能である。逆拡散器は、当業でよく知られているように、通常、乗算器の後に積分およびダンプ関数を配置したものである。
【0090】
他の実施形態では、通信システムの他の例において、直交するタイムスロットをチャネルとして使用することが可能であり(スロット付きALOHAシステムなどで)、その場合、異なるタグからの信号は(別々の時刻に)到着するとともに復調される。後述のように、選択されたチャネル化方法では、読取装置100内に採用することが可能な一般的な種類の衝突緩和アルゴリズムを変えないことに注意されたい。
【0091】
また、すべてのタグが複数パス伝送アルゴリズムの第1のパスでその情報を正常に送信することは通常あり得ないため、本発明の多数の実施形態では、復調工程は一般に複数反復工程となっていることに注意されたい。したがって、読取装置100は、タグからのすべてのデータが正常に受信されるまで(後述の方法をさらに使用して)、電源オン状態のままにし(同じ電力レベルで)、着信データを継続的に復調しなければならない。さらに、高度な衝突緩和手法1630が読取装置100で使用されている場合(後述のように)、複数復調反復法(例えば、FHT)が、複数パス・アルゴリズムのパス毎に必要になることがある。また、複数パス伝送アルゴリズムの後続のパスでは、上記の動的チャネル・プロファイルの説明で説明されているように、新規に設定したチャネル数に復調器を合わせる必要があるかもしれないことに注意されたい。
【0092】
V.衝突緩和方法
上述のように、タグ110、120、130で読取装置100との通信に使用することが可能な通信チャネルの数は、この(および任意の)通信システム内では限りがある。通信チャネルの数は限られているため、また複数のタグ間に組織だった割り当てはないため(つまり、ランダムな割り当てが実際には使用されている)、説明しているシステムはタグからの送信に衝突が生じることは避けられない。衝突は、2つまたはそれ以上のタグが同時(つまり、複数パス伝送アルゴリズムの特定のパスで)に同じチャネル上で通信することを選択する場合またはイベントとして定義される。本明細書の第I節に示されているように、タグに格納されているデータは一様ランダム・データに非常に近いため、割り当ては実際にはランダムであることに留意されたい。
【0093】
説明しているシステムでは、読取装置100の望む複雑度に応じて、(後述のように)読取装置100の衝突緩和手法を使用することも、使用しないことも可能である。例えば、安価な受信器では衝突緩和手法を使用しない場合があるが、高価な(処理能力の高い)受信器では高度な衝突緩和手法を使用する場合がある。
【0094】
以下の概要説明では、まず特定の衝突緩和手法を使用しないことを仮定し、後から、衝突緩和手法を使用するケースについて調べる。タグ110、120、130は一般に、読取装置100で衝突緩和が使用されているかいないかに関係なく同じパターンを送信することに注意されたい。各タグ(例えば、110)は、実質的に、システム内に存在する他のタグ(例えば、120、130)からは認識されない。以下の追加ステップを実行すると、さらに、受信器内の復調工程が実行される。
【0095】
特に、好ましい実施形態では、タグからの逸脱の小さいASK信号が存在することは、通常、チャネルから平均信号レベル(つまり、1380の場合のようなDC値)を差し引いて正規化された信号を取り出し、残りの(正規化された)信号の絶対値を調べることにより検出される。ある形態の自動利得制御(1380にもある)をさらに適用し、信号レベルを正規化することが可能であることにも注意されたい。正規化された信号レベルの絶対値が(一般にある期間にわたって)ある閾値を超えた場合、信号は好ましい実施形態のそのチャネル上に存在しているといわれる。
【0096】
特定のチャネルで信号が検出されると、読取装置100は、通常、衝突がそのチャネル
で発生した場合にそのことを検出しなければならない。これは、通常、ある期間にわたって正規化された信号レベルの絶対値の分散を調べることにより検出可能である。信号の絶対値の分散がある(異なる)閾値を超えた場合、衝突は、その特定のチャネル上で発生したといわれ(異なるタグのIDデータの2進データ値が衝突しているため−図17を参照)、そうでない場合、単一の信号は、そのチャネル上に存在しているといわれる(図18を参照)。ここでもまた、当業者であれば、これらの測定結果のフィルタ処理または平均処理および指標を使用して、その信頼性を高めることが可能であることを理解するであろう(例えば、推定値のSNRを上げる)。こうして、そのような測定に関して観察期間が長いほど(後のフィルタ処理で使用される)、推定値の精度および信頼度は上がることになる。また、衝突は、標準誤差検出(例えば、CRC)手段などの他の手段により検出することも可能であるが、それらの方法はすべての場合において、衝突を正しく検出可能であるわけではない。なお、あるチャネル上で衝突が発生しようとしまいと、標準誤り訂正手段を使用して、伝送誤りを補正し、信号推定値の精度を高めることが可能であることに注意されたい。これらの測定は、通常、与えられたパス内の利用できる(可能な)通信チャネルすべてで実行される(これは、上述のように、複数パス・アルゴリズムのパスの番号によって異なる)。
【0097】
そこで、読取装置100は通常、1パス当たりの可能な通信チャネルの(それぞれおよび)すべてで信号が存在しているかどうか、および信号が存在している場合に各チャネル上で衝突が発生したかどうかを特徴付ける。衝突は一般に、2つまたはそれ以上のタグが複数パス・アルゴリズムの同じパスで同じ通信チャネルを使用する場合として定義されることに留意されたい。与えられたチャネル上で衝突が発生した場合、そのチャネルに対するデータは一般に、衝突緩和手法が使用されていなければ失われることになる。与えられたチャネル上に信号が存在し、衝突が検出されない場合、その(与えられた)チャネル上の特定の信号は、正常に受信されているといわれ、読取装置100は一般的に、その特定のタグのデータ系列全体を認識する。
【0098】
いくつかの実施形態ではさらに、誤り検出または訂正(または何らかの他の種類の信号完全性測定)を実行し、データが有効であり、正しく受信されていることを確認することが可能であることに注意されたい。また、タグ・チャネル選択データが送信された場合、読取装置100はさらに、タグ110が実際に予期されている通信チャネル上で通信を行ったことをチェックすることも可能であることに注意されたい(上述のようにチャネルを決定するために使用されるデータの部分に対する他の形態の誤り検査として使用される−図18も参照のこと。第2のパスに対するチャネル選択データ222は、1820、1830、1840で識別されているように、チャネル選択と一致していなければならない)。
【0099】
タグ110からの信号が認識されると(そして場合によっては確認されると)、これは無視されるか、または信号母集団の残りから除去される(後述)。特定のタグからの信号が信号母集団から実際に除去される場合(さまざまな可能なアルゴリズムを使用して)、ある種の衝突緩和が実装される。信号の除去は、衝突緩和の利点を活かすために正確でなくてもよいことに注意されたい。
【0100】
図19は、衝突緩和手法を使用する場合の読取装置の動作に関する一般的な流れ図を示している。この場合、読取装置100は、可能な限り多くの衝突(例えば、データ中の誤り)を解決しようと試みてから、複数パス伝送アルゴリズムの次のパスに移る(例えば、好ましい実施形態において読取装置の送信電力を一定に保つことにより)。
【0101】
上述のように、読取装置100は、一般に、すべての能動的送信タグが識別されている何らかの信頼度レベル(または確率)が得られるまで送信を指定電力レベルに保つ。
信号が信号母集団(または複合受信信号)から能動的に除去される(差し引かれる)ことがない場合、衝突緩和はいっさい発生していないといわれる。その場合、読取装置100でさまざまなアルゴリズムを使用し、タグからのすべてのデータを正常に取得(または復調)することが可能である。この場合の一般的な考え方では、複数パス送信元デバイス伝送アルゴリズムの複数のパスのうちの少なくとも1つで一意的な(つまり、単一のユーザが占有した)通信チャネルを各タグが選択するのを待つ。この手法は、一般に、読取装置100内で利用可能な最も複雑度が低い識別方法であるが、一般的に、最も低速でもある(つまり、情報のやり取りにかかる全伝送時間が最も長い)。
【0102】
読取装置100により衝突緩和手法が使用されていないケースに対する非常に複雑度も低いアルゴリズムの1つは、タグ110、120、130に、複数パス通信アルゴリズムで最大数のパスを伝送させるという単純な方法をとる。最大数のパスは、通常、タグに格納されているデータの一意的な部分が尽きたら(上述のように)決定される。
【0103】
上述のように、読取装置100は、第1および第2の所定の伝送状態を制御することによりタグが送信する際のパスの数を直接制御する。本発明の好ましい実施形態では、読取装置送信電力レベルは、完全にアクティブにされているタグ間の伝送を続行させるために一定に保たれるが、他の第1および第2の所定の伝送状態はタグからの伝送をグループ単位で制御することが可能である。パスの最大数は、一般に、特定のチャネル選択アルゴリズムにより決定されるが、一般に、完全に一意的な(重なり合わない)チャネル選択項目についてデータ長(ビット数)をデータのチャネル選択部分(ビット数)の総和で除算した値に限られる。したがって、128ビットのデータと、8ビットのチャネルID選択データが各パス内にある上に示した例では、(チャネル選択が繰り返しを開始する前に)複数パス・アルゴリズム内に最大16(つまり、128/8)の通信パスがある。そこで、好ましい実施形態でチャネル(例えば、PN)シンボル・レートを与えた場合、最大インテロゲーション時間(maximum interrogation time)を決定することが可能であり、全取得(または読み取り)時間はすべての場合について固定される(上の式でも示されているように)。
【0104】
衝突緩和手法を使用しない他の(多くの場合、より複雑な)アルゴリズムも可能である。このような代替え手法の1つでは、受信したデータ(または取得されたタグ在庫)が正しいものである指定信頼度レベルが得られるように、タグ110、120、130に限られた数(最大数未満)のパスについて伝送を行わせる。これは、一般に、システムに(または各パワーオン・レベルで)存在する予想される数の送信元デバイス(またはタグ)および望む信頼度レベル(またはシステム内の商品またはタグを正常に識別する確率)により決定される。例えば、上の例で与えられた動的チャネル・プロファイルを使用したシミュレーション(試行回数1000回以上)から、50個のタグを識別するために平均7.73伝送パスを必要とすることがわかっているが、1000回の試行でタグを一意に識別するためには最大10個のパスが必要であった。したがって、読取装置100は、10個のパスの間与えられた電力レベルで電力オン状態を保ち、50個(程度の)タグすべてが一意的なチャネル上でそのデータを正常に送信したという十分な信頼性がありえる。ここでもまた、読取装置100は、IDデータを受信するため、いつチャネル上に1つのタグ110しかないかを判別することが可能であればよい。これにより、上の例で与えられた絶対最大16個のパスの代わりに10個のパスだけ実行したため、全取得時間の実質的短縮がなされることになる。詳細なシミュレーション、統計的または確率分析を適用して、他の信頼度レベルまたは与えられた数のタグに対するパスの数を決定することも可能であろう。いくつかの応用では、読取装置100は、最初に在庫調べをするときに最大数のパスを利用し、その後、システム内に存在すると予想される(または、測定もしくは観察された)数のタグに基づいてパスの数を調整することも可能であることに注意されたい。
【0105】
それとは別に、読取装置100によって使用されるアルゴリズムは各タグの予想される衝突位置(つまり、チャネル)を追跡し(そのデータまたはID情報が正常に受信された後)、システム内にまだ識別されていないタグがいくつ残っているかを推定することも可能である。したがって、読取装置100は、上記の方法よりも早くインテロゲーション工程を停止することが可能である場合がある(システム内に他のタグが存在する可能性がないと判断された後)。つまり、必要な数の伝送パスは、上記のようにタグの予想される数に基づいて事前に計算するのではなく、受信時に読取装置100により様子を見ながら推定されるということである。この手法については、以下の例と図22で詳しく説明される。
【0106】
読取装置100のより高度な実施形態では、複数の形態の衝突緩和手法のうちのどれか1つを使用することが可能である。衝突緩和手法を使用すると、一般に、与えられた通信チャネルに対する衝突の影響が除かれる。チャネル上の特定の衝突の効果が除去されることが理想的である。これは、(少なくとも概念上は)判明している信号を再生し、判明しているその信号を全信号母集団(または複合受信信号)から差し引くことにより、望むシステムにおいて実現することが可能である。この干渉信号除去は、復調工程のどの段階でも行えることに注意されたい(例えば、チップ・レートで行うことも、好ましい実施形態での逆拡散の後に行うことも可能である)。本発明の好ましい実施形態では、実装の複雑さを軽減するために復調(つまり、逆拡散)の後に衝突緩和を実行する。
【0107】
一般に、衝突緩和手法を使用する場合、判明している信号が多いほど、複数パス・アルゴリズムの指定パスについてシステム内に存在するように見えるタグの数は少なくなる。好ましい実施形態ではタグ110に格納されているデータは直接チャネル選択を決定するため(または、読取装置100により他の何らかの手段により知られているため)、読取装置100は、データを正常に受信した後(一般に、タグ110が他の何らかの形で未占有になっているチャネル上で送信する場合に発生する)、タグ110により複数パス通信アルゴリズムのすべてのパスについて実行されるチャネル選択のすべてを認識する。そのため、読取装置100は、上記のようにタグ110が将来の(および過去の)伝送について利用するチャネルを予測することが可能である。タグ110からの観察された信号レベルはさらに、一般的に、通常の信号検出工程において、読取装置100内で測定され(またローパス・フィルタに通され)、与えられた(衝突していない)タグの実際の信号強度の信頼可能である推定値が得られる。この知識を利用すれば、判明している信号を効果的に生成し直し、受信した信号全体から正確に差し引くことが可能であり、それにより、他の伝送パスからその効果を除去することが可能である。
【0108】
概して、さまざまな複雑度レベルの衝突緩和手法の一群が存在しており、一般に、衝突緩和手法を使用しない実装よりも複雑である(例えば、より大きな処理能力、メモリ容量、またはハードウェアを必要とする)。しかし、このような手法を採用すると、一般的に、全タグ・データ取得(読み取り)時間はかなり短縮し、システム能力を大幅に高めることが可能である。ここでもまた、チャネルは疑似静的であると仮定しており、システムは比較的リニアであり、最良のシステム性能が得られる。
【0109】
比較的単純な形態の衝突緩和では、複数パス・アルゴリズムの後続のパスから(時間に関して順方向に)判明している信号を差し引く必要がある。そのため、この形態の衝突緩和は、一般に、順方向衝突緩和(forward collision mitigation)と呼ばれる。図20は、順方向衝突緩和手法を使用する読取装置処理の流れ図の例を示しており、そこでは、処理は、工程をわかりやすくするため、順次(例えば、チャネルを一度に1つずつ)実行する。この工程では、一般に、タグ110、120、130のどれがIDデータを正常に送信したかを判別し(上の受信器アルゴリズムで説明されているように)、複数パス・アルゴリズムのパス毎に判明している(タグの)チャネル選択
および推定信号レベルを含むデータ構造体(またはリスト)を保持する必要がある。タグのIDデータおよび送信されたタグ信号の信号レベルは、認識された後、そのタグを伴う後続の衝突から効果的に除去することが可能である。ここでもまた、信号レベルを測定し、フィルタ処理する時間を長くすることで、干渉信号レベルの精度のレベルを高めることが可能であることに注意されたい。そこで、本発明の1実施形態では、タグ信号は、推定された(あるレベルの精度内で判別された)後、複数パス伝送アルゴリズムの後のほうのパスで適切な(所定の)チャネルから差し引かれ、その(判明している)タグの信号が他のユーザによって送信された他の信号に及ぼす干渉影響が打ち消される。通常、タグ110に格納されているデータに基づく、各タグのチャネル選択の決定論的性質のため、この手法が可能になっている。
【0110】
測定された信号レベルは後続のすべてのパスで保持されると仮定されるため、ここでは疑似チャネルの仮定が重要になる。一般に、チャネル状態がゆっくり変化することに対応するため、信号レベル推定を伝送パス毎に更新することも可能である。このアルゴリズムを実行するために、判明しているタグ信号情報(通常は、データ構造体またはリストに含まれる)および現在の伝送パス(またはバースト)からの複合受信信号を格納するだけでよいことに注意されたい(以下のアルゴリズムで説明しているようにメモリ内にすべての受信バーストを格納することとは対照的である)。一般に、この種の順方向衝突緩和アルゴリズムを使用すると、衝突緩和を実行しない方法に比べて全読み取り時間がかなり(2〜4倍)改善される可能性がある。
【0111】
他のより高度な形態の衝突緩和では、複数パス伝送の後続のパスおよび前のパスの両方から判明している信号を差し引く必要がある。これが可能であるのは、タグ110からのデータが識別された後、前のパスでそのデータが占有していたチャネルを確認し、前の衝突への関わりを無効にすることが可能であるためである。このクラスの衝突緩和アルゴリズムは、一般に、双方向衝突緩和手法と呼ばれる。双方向衝突緩和は、複雑な計算を行うが(一般に通信前パスを格納するためにより多くのメモリを必要とする)、その結果、全タグ読み取り時間は大幅に短縮される(衝突緩和を実行しない方法に比べておおよそ1桁短縮される)。
【0112】
一般に、この方法では、識別されたタグについて各通信パス(上記の場合のように)で判明しているチャネル選択および推定信号レベルを含むデータ構造体を格納する必要がある。しかし、信号は前の伝送パス(順方向衝突緩和アルゴリズムの場合のように現在パスに加えて)から差し引かれるので、さらに衝突があっても解決することが可能である。例えば、複数パス通信アルゴリズムの第3のパスからのデータが解決された場合(つまり、正常に受信された場合)、他のユーザからのデータはアルゴリズムの前のパス(例えば、第2のパス)で解決可能な場合があり、さらにこれにより、すでに伝送の前のパス(例えば、第1のパス)または後続のパス(例えば、第3のパス)のいずれかで衝突していた他のユーザを解放することが可能である。新しいユーザからのデータが解決される毎に、再構成された信号がすべての伝送パスから(現在のパスまで)差し引かれ、衝突の回数も再び評価される(可能なすべての通信チャネルについて)。このようにして、読取装置100は利用可能な伝送パスをすべて(現在のパスを含み現在のパスまで)巡回し、どのパスでも(現在のパスまで)解決することが可能なユーザがそれ以上いなくなる時点に達するまで、さらに多くのタグ信号を実質的に連続して解決することが可能である。読取装置100は、その後、次の電力レベルに1ステップ進み、双方向衝突緩和アルゴリズムを続行する。この効果は、後の伝送パスで極めて強力である可能性があり、通信チャネルの利用可能な個数よりもかなり多いタグ信号を解決することが可能である。
【0113】
タグ・データのすべてが受信されると、読取装置100は、上述の手段(例えば、誤り検出および訂正)を介してデータの完全性をチェックすることが可能である。読取装置1
00は、さらに、データの後処理を行うことも可能であり、通常は、冗長項目のスクランブル解析、暗号解読、分類、および除去などの機能を含む(本発明の好ましい実施形態では複数のパワーオン範囲で電源投入する)。これらの機能の一部または全部を、中央にひとまとめに配置することも可能であり、それにより、複数の読み取り装置またはアンテナを扱うことが可能であることに注意されたい。
【0114】
システム・オペレーションの例
これらのアルゴリズムのオペレーションは、例を使うと内容が最もよくわかるであろう。これらの例は、パス毎にランダム・チャネルを引き込むタグの簡素化された仮説的システムを詳しく示している。図21、23、および24は、この例を説明するために使用される、システムの状態図であり、アルゴリズムを通る後続パス毎に各タグが通信するため選択するチャネルを示している。例に示されている状態は、チャネルを選択するために乱数生成器を使用する実際の実験の元の出力である。物理チャネルの種類(例えば、符号位相、タイムスロットなど)はこの時点では無関係である。これにより、上の第I節で詳述したように本発明のデータ・スクランブル部分があるため、システム全体の比較的正確なモデルを用意しなければならない。
【0115】
図21、23、および24に詳述されている例では、8個のタグからなる母集団を仮定し、さらに、タグが通信のため引き込む引き込み元の8つのチャネルの1パス当たりの固定チャネル・サイズを仮定する。そこで、好ましい実施形態では、各タグのID情報の(一意的な部分集合の)3ビットを使用して、伝送の各パスで各タグ110が送信に使用する8つのチャネルのうちの1つを選択する。8進数を使用して、タグIDの最初の30ビットがランダムに生成されているが、便宜上以下のように繰り返す。
【0116】
タグ1: 0033 0436 07...
タグ2: 1106 2551 65...
タグ3: 4767 4416 41...
タグ4: 2044 6111 36...
タグ5: 6072 3355 74...
タグ6: 1476 5432 40...
タグ7: 5443 3675 34...
タグ8: 2135 5115 64...
タグ1は、パス#1でチャネル0を、パス#2でチャネル0を、パス#3でチャネル3をというように選択を続ける。タグ2は、パス#1でチャネル1を、パス#2でチャネル1を、パス#3でチャネル0をというように選択を続ける。このリストから、第1の8進数からチャネルを引くパス#1については、タグ1はチャネル0の単独占有者であり、タグ3はチャネル4の単独占有者であり、タグ5はチャネル6の単独占有者であり、タグ7はチャネル5の単独占有者であることがわかる。これらのチャネルには衝突がないため、タグ1、3、5、および7は全体として正常に識別されており、タグ1、3、5、および7は、衝突がなかったチャネルでその完全なIDを伝達した。しかし、パス#1では、タグ2および6は、チャネル1で衝突しており、タグ4および8はチャネル2で衝突している。これらのタグは、正常に識別することが不可能であり、後続のパスを解決する必要がある。読取装置100は、衝突が存在していることを観察し、印加されている電力を現在レベルのままにし、それによりすべてのタグがパス#2の第2の8進数から別のチャネルを引くことが可能であるようにする。タグにはIDを正常に伝達可能であったかどうかを知るすべがないことに注意されたい。
【0117】
パス#2では、衝突に関わっていない唯一のタグはタグ3である。このタグはすでにパス#1で識別されていたため、読取装置100は新しい情報を取得しなかった。パス#1で衝突していたタグはどれもまだ識別することは可能でない。統計的に、8つのタグと8
つのチャネルでは、少なくとも1つの衝突が生じる確率は1−8!/88=99.76%である。この結果は、上で与えられたN個のチャネル上のM個のタグの間に衝突がない確率のより一般的なケース
【0118】
【数5】
#1 P{衝突なし}
とP{衝突}=1−P{衝突なし}という事実から得られる。この同じ確率は、アルゴリズムを通るパス毎に衝突が少なくとも1回あるという確率である。タグとチャネルのこのような組み合わせについて、実験を100000回行って平均をとると、8個のチャネルのうち2.7498個は1パス当たり未占有であり、これらのチャネルのうち3.1386個は、単一タグを含み、1.5737個のチャネルは2つのタグを含み、0.4482個のチャネルは3つのタグを含み、0.0796個のチャネルは4つのタグを含み、0.0093個のチャネルは5つのタグを含み、7.2×10−4個のチャネルは6つのタグを含み、4×10−5個のチャネルは7つのタグを含み、1チャネル内に8つのタグというケースは記録されていなかった。
【0119】
衝突緩和のない例
衝突緩和を行わない場合、タグは、識別されるために、チャネル内にすべて自力で現れていなければならない。実験を十分な回数行うことが許されていれば、このようなことが起こる。しかし、タグID 220情報内のビットの数は限られているため、繰り返しを開始する前に、実験は限られた回数しか実行することが可能でない。例えば、タグIDが96ビット長であり、1パス当たり3ビットを使用してチャネルを引いたとすると(8つのうち1つ)、32回の実験後にその工程が繰り返される。1パス当たり少なくとも1回の衝突があるという高い確率(このシナリオでは99.76%)なので、実験を介してタグのIDがパス毎に、また全パスにわたって衝突の中に「隠れる」ことがあり得る確率は小さいが有限の値である。これは、タグのID 220は全体にわたって異なるタグのIDと同じであることを意味しない(一意的なタグIDおよびスクランブルされたタグIDへの一意的な可逆マッピングがあるという仮定により許されていない)。これは、そのパスについてチャネル空間を定義するために使用されている少数のビット(この場合、3)に関して調べたときに、タグのID 220は少なくとも1つの他のタグのIDと同じであると言っているに過ぎない。これにより、タグの在庫がある信頼度でしか判明していない、在庫または商品の不確定性という概念が導入される。
【0120】
図21の実験例では、衝突のないチャネルに現れるためにタグ毎に8回の試行が必要である。すでに述べたように、タグ1、3、5、および7は、パス#1で識別され、タグ2はパス#3で現れ、タグ4および8はパス#4で識別され、タグ6はパス#8まで現れない。タグ6は、一意的なIDを持っているとしても一意的なタグが衝突の中に隠される可能性のあることを示すよい例である。この実験がパス#7でしか行われていないとすれば(つまり、IDの長さが21ビットしかなかった場合)、タグ6は識別されていないであろう。
【0121】
パス#1で、4つのタグが識別される。さらに2つの衝突が識別され、ほかに少なくとも4つのタグがあることが示される(少なくとも2つのタグがあれば単一の衝突が生じるので、2つの衝突が生じるためには少なくとも4つのタグが必要である)。したがって、第1のパスの後、読取装置100は、4つの判明しているタグと少なくとも4つの未知の
タグがあるか、または全部で少なくとも8つのタグがあると判別することが可能である。
【0122】
パス#2では、単一のすでに判明しているタグのみが一意的な(未使用の)チャネルを占有している。読取装置100ではタグ1、3、5、および7の完全なIDがわかっているため、次および後続のすべてのパスでそれらのタグが占有するチャネルがわかる。読取装置100は、タグ1および5がチャネル0に、タグ7がチャネル4に割り当てられることを知る。そこで、読取装置100は、チャネル0に衝突があることを予期するが、チャネル0を占有している未知のタグ(この場合、タグ4)もある可能性がある。チャネル0は、2つの判明しているタグの存在と、1つまたは複数の未知のタグの存在の可能性を示す。読取装置100は、チャネル1での衝突を予期していなかった(判明しているどのタグもそのチャネルを選択することを予期していなかったからである)。ここで、衝突は、少なくともさらに2つの未知のタグ、おそらくさらに多くのタグがあることを示す。タグ7だけが予期されていたチャネル4上の衝突は、ほかに少なくとも1つの未知のタグがあることを示す。したがって、パス#2では、4つのすでに判明しているタグがあり、少なくとも3つの(確実に)未知のタグがある。これは、少なくとも4つの判明しているタグと少なくとも4つの未知のタグであった、第1のパスによって定義されている集合よりも少なく、したがって読取装置100は第2のパスで新しい情報を収集していなかった。
【0123】
パス#3では、タグ2はチャネル0上で識別される。タグ1は、チャネル3に入ることが予期されている唯一のタグであり、したがって衝突はそこでは、少なくとも1つの未知のタグのあることを示す。タグ7は、チャネル4に入ることが予期されている唯一のタグであり、したがって衝突はそこでは、少なくとも2つの未知のタグ(チャネル3上の未知のタグとチャネル4上の未知のタグ)のあることを示す。タグ3は、この場合も単独である。タグ5は、チャネル7に入ることが予期されている唯一のタグであった。衝突は、少なくとも3つの未知のタグがあることを示す(チャネル3、4、および7上の未知のタグを勘定に入れる)。これらも、現在の5つの判明しているタグとともに、この場合も、少なくとも8つのタグのあることを示す。
【0124】
パス#4により、新しいタグ4および8が識別される。タグ3、5、および7は、衝突のないチャネルに現れる。タグ1および2は、チャネル6上で衝突することが予期されていたが、そこにはさらにタグがありうる。そのため、7つの判明しているタグと、前の実験からの、少なくとも1つの未知のタグが残る。
【0125】
パス#5により識別される新しいタグはない。チャネル5上の衝突は予期されておらず、この場合も、7つの判明しているタグと少なくとも1つの未知のタグがあることを示す。パス#6とパス#7から、同様の解釈を行うことが可能である。
【0126】
パス#8では、タグ6が識別される。他の衝突はすべて予期されていた。そこで、8つのタグが識別されており、前のパスから最低限の数が予期されている。しかし、それでも、衝突に隠れているタグがあり得る。例えば、チャネル1、0、4、6、3、1、1、5を選択したタグがあり得、このタグは他の衝突により隠されることになる。タグにこの特定のIDがある確率は、1/88または6×10−8となる。
【0127】
また、チャネル、例えば、2、4、4、6、5、4、5、6を、これもまた確率6×10−8で選択したタグがあり得る。まとめると、パス#1で2つの衝突、パス#2で3つの衝突、パス#3で3つの衝突、パス#4で1つの衝突、パス#5で2つの衝突、パス#6で2つの衝突、パス#7で3つの衝突、およびパス#8で3つの衝突があると、2×3×3×1×2×2×3×3=648通りの可能なIDがあり、それぞれ確率は6×10−8で、追加される単一の隠しタグの確率は648/88=38.6×10−6(38.6ppm)である。追加される2つの隠しタグの確率は、さらに小さいなものとなり、64
8・647/816=1.5×10−9である。他の実施形態では、データをスクランブル解析し、例えば、他のすべての商品が食料雑貨であった場合に隠されているタグが他の予期される商品の全部または一部と関連付けられていることを判別することにより、在庫信頼度のレベルをさらに改善することが可能であろう。
【0128】
隠されているタグの確率は、衝突情報に基づいて最小個数(この場合、8個)の予期されるタグを識別した後に実験を続行させることにより小さくすることが可能である。1パス当たりの衝突の回数を数え、1パス当たりのチャネルの数に基づいて隠されているタグの確率を知ることにより、読取装置100は、何らかの信頼度レベルを満たすか、または一意的なチャネル・パターンを使い尽くしてしまう(IDが枯渇する)まで、パスを続けさせることが可能である。2つの追加パス(全部で10のパス)の後に、1パス当たり6481/8=2.246回の衝突を仮定すると、単一の隠されているタグの確率は、3.04×10−6に下げることが可能である。さらに2つの追加パス(全部で12のパス)の後、単一の隠されているタグの確率は、240×10−9に下げられる。パスを追加する毎に、単一の隠されているタグの確率は、等比級数的におおよそ6481/8/8=0.281倍ずつ減少する。
【0129】
上で説明した干渉除去のない方法に関わるステップを示す流れ図は図22に示されている。開始2210時に、システムは、正のIDも未知商品もないものとして初期化され、これは合わせて、合計0個の商品に対応する。第1のパス2220の分析2230の後に、正のID(例えば、パス#1の商品1、3、5、および7)は、記録され、正のIDのリストに追加される2240。パス2250内の衝突の回数も記録される(例えば、パス#1では2つの衝突)。衝突が予想されていた場合2260、将来のパスで明らかにすることが可能な潜在的未知商品があるが、確実な未知商品はない。衝突が予想されなかった場合2270、2つの未知商品が未知リストに追加される。そこで、商品の総数は、正として識別された商品の個数および記録された衝突の原因になった可能性のある未知商品の最小数であるとして推定される2280。正のIDは推定された商品総数に等しくないと仮定すると、未知商品の合計は0にリセットされ2295、他のパス2220が開始する。最後に、正のIDの個数がすでに識別されているIDの最大数+未知商品の数に等しい場合にこのループを抜け2290、所定の信頼度レベル2296が満たされる。
【0130】
ここまで、チャネルと受信信号レベルの時間的変動に関してはいっさい仮定を置かなかった。「衝突緩和のない方法」は、チャネルが静的であろうと動的であろうと適用することが可能である。静的なチャネル状態の場合、戻り信号の電力レベルと位相が一貫していれば、受信信号レベルという形で読取装置100で利用可能な情報が増える。そこで、判明しているタグが将来のパスで選択するであろうチャネルが判明していることに加えて、その信号レベルも判明していると仮定すれば、予期した衝突にさらに隠されたタグが存在するかどうかを判別することが可能である。例えば、パス#2のチャネル0上の衝突には、2つの判明しているタグと1つの未知のタグが含まれていた。判明しているタグの信号レベルも判明していれば、衝突の総信号レベルを個々の信号レベルと比較して、衝突の中にさらに未知のタグが隠されているかどうかを判別することも可能であろう。このような環境では、衝突はすべて説明されるため隠されたタグがないことが確実であれば、すべてのタグが独立に識別された後(この場合、8パス)、読取装置100は問い合わせを終了することが可能である。
【0131】
したがって、識別されたタグの信号レベルがわかれば、在庫のアカウンティングの信頼度が高まる。しかし、信号レベル情報があれば、すべての判明しているタグが個別に出現した後、問い合わせを単に打ち切ること以上に、収集時間の改善を期待可能することが可能である。これについては、次の節で説明する。
【0132】
順方向衝突緩和の例
タグが個別に識別されると、後続のすべてのパスに対するチャネルの選択が読取装置100側で判明する。タグの信号レベルおよび位相がさらに判明すれば、そのタグが衝突に関わる寄与分を0にすることが可能である。後続の衝突から、タグからの信号を本質的に除去することが可能であり、したがって、母集団からも実際に除去することが可能である。図23に示されている実験を考察する。タグ1、3、5、および7は、パス#1で正として識別されている。その信号レベルおよび位相も決定されていると仮定する。
【0133】
パス#2で、タグ1および5は、チャネル0上でデータを送信することが知られている。その判明している信号レベルでは、タグを差し引くことが可能であり、現在識別することが可能なタグ4のみを残す。同様に、タグ7はパス#2でチャネル4によりデータを送信することが予期されており、このタグを無効にすることにより、タグ6はそのまま残され識別される。チャネル1にはまだ未解決の衝突があり、このアルゴリズムを通る少なくとも1つの他のパスが必要である。
【0134】
パス#3では、タグ2が単独で現れ、識別される。タグ1は、チャネル3上でデータを送信することが予期されており、したがって、差し引かれ、後にはタグ8のみが残り、そこで、識別することが可能である。他のすべての衝突には、判明しているタグのみが含まれ、タグのアカウンティングは、図21に示されているような衝突緩和なしの場合の8つ以上のパス(必要な信頼度レベルに応じて)ではなく100%の信頼度でアルゴリズムを通る3つのパスで完了している。
【0135】
静的チャネルでは、識別されたタグの信号強度は、高い精度で知ることが可能である。増大されたPNチャネルのケースを考察する。この実験では、タグは8チップ長の増大されたPN系列のさまざまな符号位相を選択する。この8チップ長のPN系列は、特定のIDビットの意味に応じて、タグのIDのビット毎に、真または反転で送信される。読取装置100では、受信器内の相関器は、本質的に、1ビット当たり8個のチップにわたり信号レベルを平均する。これは、ID内のすべてのビット(例えば、128)について実行され、信号対雑音比平均利得10 log(1024)=30dBについて8×128=1024サンプルで平均をとる。さらに多くの予期されるタグとさらに多くの(>32)利用可能なチャネルがあるより実際的なケースについては、この利得は大きくなる。32チャネルおよび128ビットでは、信号対雑音比の利得36dBが得られる。
【0136】
双方向衝突緩和の例
読取装置100が前のパスからの波形サンプルを格納していれば、アカウンティング時間はさらに大幅に改善し得る可能性がある。波形が格納されていれば、前のパスをもう一度辿り、それを後続のパスとして処理することが可能であり、そこから前の衝突を無効にすることが可能である。これは、タグが一度でも識別されると、それ以降のすべての活動が判明するだけでなく、前のチャネル選択および信号レベルもすべて、判明するからである。
【0137】
図24に示されている例を考察する。パス#1では、タグ1、3、5、および7は、ビット・パターンおよび信号レベルと位相の両方で識別される。順方向衝突緩和の場合と同様に、タグ4は、パス#2で識別することが可能であるが、タグ1および5の効果をチャネル0上の衝突から除去することが可能だからである。同様に、チャネル4上の衝突からタグ7の効果を除去することで、タグ6を識別することが可能である。パス#2の後、また順方向衝突緩和を適用した後、タグ1、3、4、5、6、および7が判明する。
【0138】
第3のパスを使用せず、順方向衝突緩和を適用した後にパス#1の結果に立ち返ることが可能である。パス#2でタグ4が識別された場合、第1のパスの格納されている結果の
チャネル2からそのタグを除去し、タグ8を解決することが可能である。パス#2でタグ6が識別された場合、第1のパスの格納されている結果のチャネル1からそのタグを除去し、タグ2を解決することが可能である。この場合、8つすべてのタグを正常に識別するために、2つのパスのみが必要である。順方向および双方向衝突緩和の有利性は、関わるチャネルとタグの数が増えると一段と増す。
【0139】
そのため、卓越した性能(例えば、読み取り時間および容量)を発揮する複数パス伝送アルゴリズム(スペクトル拡散手法を採用するのが好ましい)を使用する一方向通信システムについて詳述した。衝突緩和手法、動的チャネル・プロファイル、およびパワーオン範囲を組み込むことで、システム性能がさらに改善される。説明した通信システムには、本明細書で詳述した好ましい実施形態および実際の例に限られない多数の応用がある。さらに、本発明には、双方向通信デバイス、能動的給電ユーザ・デバイス、およびネットワーク接続デバイスの応用もあるが、その本質的特徴(請求項で説明している)から逸脱することはない。
【0140】
本発明は、本発明の精神または本質的特徴から逸脱することなく他の特定の形で実現することが可能である。説明した実施形態は、すべての点で、説明のみを目的としており、制限することを目的としていないとみなすべきである。したがって、本発明の範囲は、上記の説明ではなく、付属の請求項で指示される。請求項の同等性の意味および範囲内にあるすべての変更は本発明の範囲に含まれるものとする。
【図面の簡単な説明】
【0141】
【図1】本発明による単一の送信先デバイスと通信する複数の送信元デバイスを示す高水準の図。
【図2】タグに記録されているデータの変更方法および本発明による動作が行われている間に送信チャネルを判別するための使用方法を説明する図。
【図3】本発明によりタグに記録されるデータをスクランブルするために使用される工程を示す高水準の図。
【図4】本発明による複数のタグ通信および読取装置で実行される逆スクランブル(スクランブル解析法)を示す高水準システムの図。
【図5】本発明によるタグ・データのスクランブルおよび回復に使用される反復アルゴリズムを説明する図。
【図6】本発明によるスクランブル手順の詳細な例を示す図。
【図7】本発明によるタグの高水準のブロック図。
【図8】本発明によるタグ伝送状態の概略を示す一般的流れ図。
【図9】本発明によるタグ伝送状態の概略を示す詳細流れ図。
【図10】本発明による代表的実施形態における読取装置とさまざまなタグとの間の静電結合を使用する応用事例を示す図。
【図11】本発明によりタグに記録されるデータに基づき通信するタグのチャネルを生成する方法を示す図。
【図12】本発明によるパスの依存関係および変調方法を説明する簡略化されたタグ回路の機能ブロック図。
【図13】本発明による読取装置の詳細ブロック図。
【図14】本発明によるWalsh符号化信号の高速変換方式の例を示す図。
【図15】本発明による疑似雑音系列(pseudonoise sequences)の高速相関を求めるための読取装置受信器信号処理の詳細な例を示す図。
【図16】本発明による読取装置信号処理の簡略化された機能ブロック図。
【図17】本発明による、衝突存在時の波形例を示す図。
【図18】本発明による、衝突が存在しないときの複数の波形例を示す図。
【図19】本発明による読取装置の動作の一般的流れ図。
【図20】本発明による前方衝突緩和手法(forward collision mitigation techniques)を使用した読取装置信号処理の詳細な流れ図。
【図21】本発明により衝突緩和手法が適用されない場合の棚卸資産会計の例を示す図。
【図22】本発明により衝突緩和手法が適用されない場合の在庫アルゴリズムの流れ図の例。
【図23】本発明による衝突緩和手法が使用される棚卸資産会計の例を示す図。
【図24】本発明による双方向衝突緩和手法が使用される棚卸資産会計の例を示す図。
【特許請求の範囲】
【請求項1】
信号系列を受信する工程と、
所定の順序に基づき該信号系列の順序変更をする工程と、
該順序変更された系列に対し変換を実行する工程と、からなる相関方法。
【請求項2】
前記変換は、高速Hadamard変換(FHT)、高速Walsh変換、高速Walsh−Hadamard変換からなるグループから選択される請求項1に記載の方法。
【請求項3】
前記信号系列は少なくとも1つのm系列からなる請求項1に記載の方法。
【請求項4】
前記所定の順序は少なくとも1つのm系列の生成器多項式に基づく請求項3に記載の方法。
【請求項5】
前記信号系列は少なくとも1つの特別に増大されたm系列からなる請求項1に記載の方法。
【請求項6】
前記所定の順序は少なくとも1つの特別に増大されたm系列の生成器多項式に基づく請求項5に記載の方法。
【請求項7】
前記変換の次元は利用可能なチャネルの数に相当する請求項1に記載の方法。
【請求項8】
前記変換の次元は利用可能なチャネルの数と異なる請求項1に記載の方法。
【請求項9】
信号系列の要素を受信する受信器と、
アドレス系列を生成し、疑似雑音系列とWalsh系列との変換を行うための状態生成器と、
該アドレス系列に従って与えられたアドレスに該信号系列の各要素を格納するための、該受信器と該状態生成器に結合される記憶媒体と、からなるデバイス。
【請求項10】
前記状態生成器はリニア・フィードバック・シフト・レジスタからなる請求項9に記載のデバイス。
【請求項11】
前記リニア・フィードバック・シフト・レジスタはフィボナッチ数列生成器である請求項10に記載のデバイス。
【請求項12】
前記状態生成器は第2の記憶媒体である請求項9に記載のデバイス。
【請求項13】
前記疑似雑音系列は特別に増大されたm系列である請求項9に記載のデバイス。
【請求項14】
さらに、前記記憶媒体に格納されている前記信号系列の前記要素の少なくとも一部に対し変換を実行するための、記憶媒体に結合されているプロセッサからなる請求項9に記載のデバイス。
【請求項15】
前記変換は、高速Hadamard変換(FHT)、高速Walsh変換、高速Walsh−Hadamard変換からなるグループから選択される請求項14に記載のデバイス。
【請求項16】
前記受信器はアナログ・デジタル・コンバータからなる請求項9に記載のデバイス。
【請求項17】
通信システム内で使用される衝突緩和方法であって、
第1のチャネル上で受信された信号を推定する工程と、
該信号の受信に使用される1組のチャネルを決定する工程と、
推定および決定の該工程に基づき、第2のチャネル上で受信された複数の信号から該信号を除去する工程と、からなる衝突緩和方法。
【請求項18】
推定する工程は前記信号の受信信号強度を推定する工程からなる請求項17に記載の方法。
【請求項19】
推定する前記工程は、誤り訂正符号化を使用する請求項17に記載の方法。
【請求項20】
請求項1の前記工程はすべての信号が決定されるまで繰り返し実行される請求項17に記載の方法。
【請求項21】
前記信号は、デバイス上に格納されている所定のデータの少なくとも一部を表す請求項17に記載の方法。
【請求項22】
前記第1のチャネルおよび前記第2のチャネルは同じである請求項17に記載の方法。
【請求項23】
前記第1のチャネルと前記第2のチャネルは異なる請求項17に記載の方法。
【請求項24】
前記第1のチャネルは前記第2のチャネルに直交する請求項17に記載の方法。
【請求項25】
前記第1のチャネルは前記第2のチャネルに疑似直交する請求項17に記載の方法。
【請求項26】
複数経路の通信システム内で使用される衝突緩和方法であって、
与えられた経路において、第1のチャネル上で受信された信号を推定する工程と、
前の経路で該信号の受信に使用された、また後の経路で該信号の受信にこれから使用される1組のチャネルを決定する工程と、
推定および決定の該工程に基づき、第2のチャネル上で受信された複数の信号から該信号を除去する工程と、からなる衝突緩和方法。
【請求項27】
前記信号は前の経路と後の経路の少なくとも1つから除去される請求項26に記載の方法。
【請求項28】
各経路においてそれぞれのチャネル上で受信されたすべての信号を格納する工程から更になる請求項26に記載の方法。
【請求項29】
各経路において、複数のデバイスはその選択されたチャネル上でそれぞれの信号を共通デバイスに送信する請求項26に記載の方法。
【請求項30】
推定する前記工程は、誤り訂正符号化を使用する請求項26に記載の方法。
【請求項31】
請求項26の前記工程はすべての信号が決定されるまで繰り返し実行される請求項26に記載の方法。
【請求項32】
通信システム内で使用される衝突緩和方法であって、
第1のチャネル上で信号を受信する工程と、
該信号の受信に使用される1組のチャネルを決定する工程と、
決定する工程に基づき、判明している信号の数と衝突している信号の数に基づき該シス
テム内の信号の総数を推定する工程と、からなる衝突緩和方法。
【請求項33】
請求項32の前記工程は、判明している信号の前記個数が信号の前記推定総数に等しくなるまで繰り返し実行される請求項32に記載の方法。
【請求項34】
請求項32の前記工程は、所定の信頼度レベルが得られるまで繰り返し実行される請求項32に記載の方法。
【請求項35】
チャネル上で信号を受信する工程と、
該信号の絶対値の分散を推定する工程と、
推定する該工程に基づき、該推定された分散が所定の閾値を超えたときに該チャネル上で衝突が発生したことを判別する工程と、からなる方法。
【請求項36】
前記所定の閾値は前記信号の絶対値の平均から求められる請求項35に記載の方法。
【請求項37】
搬送波信号を受信する工程と、
第1の所定の条件と第2の所定の条件について該搬送波信号を連続監視する工程と、
該第1の所定の条件が満たされている場合、データを送信する工程と、
該第1の所定の条件がその後満たされなくなった場合、該データの送信を停止する工程と、
第2の所定の条件が満たされている場合、データの送信を停止する工程と、からなる方法。
【請求項38】
受信電力レベルが閾値を超えたときに前記第1の所定の条件が満たされる請求項37に記載の方法。
【請求項39】
受信電力レベルが閾値を超えたときに前記第2の所定の条件が満たされる請求項37に記載の方法。
【請求項40】
所定の同期パルスが受信されたときに前記第1の所定の条件が満たされる請求項37に記載の方法。
【請求項41】
前記第1および第2の所定の条件がランダムである請求項37に記載の方法。
【請求項42】
搬送波信号を受信する受信器と、
該搬送波信号を連続監視するための、該受信器に結合される、モニタと、
データが格納される記憶媒体と、
第1および第2の条件が満たされた場合に該データの少なくとも一部を送信するための、該受信器、該モニタ、および該記憶媒体に結合される、送信器と、からなる少なくとも1つの第1のデバイス。
【請求項43】
第1のデバイスの前記第1および第2の条件は第2のデバイスの前記第1および第2の条件と同じである請求項42に記載の少なくとも第1のデバイス。
【請求項44】
前記第1および第2のデバイスは同時に送信する請求項43に記載の少なくとも第1のデバイス。
【請求項45】
第1のデバイスの前記第1および第2の条件は第2のデバイスの前記第1および第2の条件と異なる請求項42に記載の少なくとも第1のデバイス。
【請求項46】
前記第1および第2のデバイスは同時に送信する請求項45に記載の少なくとも第1のデバイス。
【請求項47】
前記第1および第2の条件のうち少なくとも一方はランダムに割り当てられる請求項42に記載の少なくとも第1のデバイス。
【請求項48】
前記第1および第2の条件のうち少なくとも一方は均一分布する請求項42に記載の少なくとも第1のデバイス。
【請求項49】
電力レベルが与えられた範囲内にある場合に前記第1および第2の条件が満たされる請求項42に記載の少なくとも第1のデバイス。
【請求項1】
信号系列を受信する工程と、
所定の順序に基づき該信号系列の順序変更をする工程と、
該順序変更された系列に対し変換を実行する工程と、からなる相関方法。
【請求項2】
前記変換は、高速Hadamard変換(FHT)、高速Walsh変換、高速Walsh−Hadamard変換からなるグループから選択される請求項1に記載の方法。
【請求項3】
前記信号系列は少なくとも1つのm系列からなる請求項1に記載の方法。
【請求項4】
前記所定の順序は少なくとも1つのm系列の生成器多項式に基づく請求項3に記載の方法。
【請求項5】
前記信号系列は少なくとも1つの特別に増大されたm系列からなる請求項1に記載の方法。
【請求項6】
前記所定の順序は少なくとも1つの特別に増大されたm系列の生成器多項式に基づく請求項5に記載の方法。
【請求項7】
前記変換の次元は利用可能なチャネルの数に相当する請求項1に記載の方法。
【請求項8】
前記変換の次元は利用可能なチャネルの数と異なる請求項1に記載の方法。
【請求項9】
信号系列の要素を受信する受信器と、
アドレス系列を生成し、疑似雑音系列とWalsh系列との変換を行うための状態生成器と、
該アドレス系列に従って与えられたアドレスに該信号系列の各要素を格納するための、該受信器と該状態生成器に結合される記憶媒体と、からなるデバイス。
【請求項10】
前記状態生成器はリニア・フィードバック・シフト・レジスタからなる請求項9に記載のデバイス。
【請求項11】
前記リニア・フィードバック・シフト・レジスタはフィボナッチ数列生成器である請求項10に記載のデバイス。
【請求項12】
前記状態生成器は第2の記憶媒体である請求項9に記載のデバイス。
【請求項13】
前記疑似雑音系列は特別に増大されたm系列である請求項9に記載のデバイス。
【請求項14】
さらに、前記記憶媒体に格納されている前記信号系列の前記要素の少なくとも一部に対し変換を実行するための、記憶媒体に結合されているプロセッサからなる請求項9に記載のデバイス。
【請求項15】
前記変換は、高速Hadamard変換(FHT)、高速Walsh変換、高速Walsh−Hadamard変換からなるグループから選択される請求項14に記載のデバイス。
【請求項16】
前記受信器はアナログ・デジタル・コンバータからなる請求項9に記載のデバイス。
【請求項17】
通信システム内で使用される衝突緩和方法であって、
第1のチャネル上で受信された信号を推定する工程と、
該信号の受信に使用される1組のチャネルを決定する工程と、
推定および決定の該工程に基づき、第2のチャネル上で受信された複数の信号から該信号を除去する工程と、からなる衝突緩和方法。
【請求項18】
推定する工程は前記信号の受信信号強度を推定する工程からなる請求項17に記載の方法。
【請求項19】
推定する前記工程は、誤り訂正符号化を使用する請求項17に記載の方法。
【請求項20】
請求項1の前記工程はすべての信号が決定されるまで繰り返し実行される請求項17に記載の方法。
【請求項21】
前記信号は、デバイス上に格納されている所定のデータの少なくとも一部を表す請求項17に記載の方法。
【請求項22】
前記第1のチャネルおよび前記第2のチャネルは同じである請求項17に記載の方法。
【請求項23】
前記第1のチャネルと前記第2のチャネルは異なる請求項17に記載の方法。
【請求項24】
前記第1のチャネルは前記第2のチャネルに直交する請求項17に記載の方法。
【請求項25】
前記第1のチャネルは前記第2のチャネルに疑似直交する請求項17に記載の方法。
【請求項26】
複数経路の通信システム内で使用される衝突緩和方法であって、
与えられた経路において、第1のチャネル上で受信された信号を推定する工程と、
前の経路で該信号の受信に使用された、また後の経路で該信号の受信にこれから使用される1組のチャネルを決定する工程と、
推定および決定の該工程に基づき、第2のチャネル上で受信された複数の信号から該信号を除去する工程と、からなる衝突緩和方法。
【請求項27】
前記信号は前の経路と後の経路の少なくとも1つから除去される請求項26に記載の方法。
【請求項28】
各経路においてそれぞれのチャネル上で受信されたすべての信号を格納する工程から更になる請求項26に記載の方法。
【請求項29】
各経路において、複数のデバイスはその選択されたチャネル上でそれぞれの信号を共通デバイスに送信する請求項26に記載の方法。
【請求項30】
推定する前記工程は、誤り訂正符号化を使用する請求項26に記載の方法。
【請求項31】
請求項26の前記工程はすべての信号が決定されるまで繰り返し実行される請求項26に記載の方法。
【請求項32】
通信システム内で使用される衝突緩和方法であって、
第1のチャネル上で信号を受信する工程と、
該信号の受信に使用される1組のチャネルを決定する工程と、
決定する工程に基づき、判明している信号の数と衝突している信号の数に基づき該シス
テム内の信号の総数を推定する工程と、からなる衝突緩和方法。
【請求項33】
請求項32の前記工程は、判明している信号の前記個数が信号の前記推定総数に等しくなるまで繰り返し実行される請求項32に記載の方法。
【請求項34】
請求項32の前記工程は、所定の信頼度レベルが得られるまで繰り返し実行される請求項32に記載の方法。
【請求項35】
チャネル上で信号を受信する工程と、
該信号の絶対値の分散を推定する工程と、
推定する該工程に基づき、該推定された分散が所定の閾値を超えたときに該チャネル上で衝突が発生したことを判別する工程と、からなる方法。
【請求項36】
前記所定の閾値は前記信号の絶対値の平均から求められる請求項35に記載の方法。
【請求項37】
搬送波信号を受信する工程と、
第1の所定の条件と第2の所定の条件について該搬送波信号を連続監視する工程と、
該第1の所定の条件が満たされている場合、データを送信する工程と、
該第1の所定の条件がその後満たされなくなった場合、該データの送信を停止する工程と、
第2の所定の条件が満たされている場合、データの送信を停止する工程と、からなる方法。
【請求項38】
受信電力レベルが閾値を超えたときに前記第1の所定の条件が満たされる請求項37に記載の方法。
【請求項39】
受信電力レベルが閾値を超えたときに前記第2の所定の条件が満たされる請求項37に記載の方法。
【請求項40】
所定の同期パルスが受信されたときに前記第1の所定の条件が満たされる請求項37に記載の方法。
【請求項41】
前記第1および第2の所定の条件がランダムである請求項37に記載の方法。
【請求項42】
搬送波信号を受信する受信器と、
該搬送波信号を連続監視するための、該受信器に結合される、モニタと、
データが格納される記憶媒体と、
第1および第2の条件が満たされた場合に該データの少なくとも一部を送信するための、該受信器、該モニタ、および該記憶媒体に結合される、送信器と、からなる少なくとも1つの第1のデバイス。
【請求項43】
第1のデバイスの前記第1および第2の条件は第2のデバイスの前記第1および第2の条件と同じである請求項42に記載の少なくとも第1のデバイス。
【請求項44】
前記第1および第2のデバイスは同時に送信する請求項43に記載の少なくとも第1のデバイス。
【請求項45】
第1のデバイスの前記第1および第2の条件は第2のデバイスの前記第1および第2の条件と異なる請求項42に記載の少なくとも第1のデバイス。
【請求項46】
前記第1および第2のデバイスは同時に送信する請求項45に記載の少なくとも第1のデバイス。
【請求項47】
前記第1および第2の条件のうち少なくとも一方はランダムに割り当てられる請求項42に記載の少なくとも第1のデバイス。
【請求項48】
前記第1および第2の条件のうち少なくとも一方は均一分布する請求項42に記載の少なくとも第1のデバイス。
【請求項49】
電力レベルが与えられた範囲内にある場合に前記第1および第2の条件が満たされる請求項42に記載の少なくとも第1のデバイス。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【公開番号】特開2008−17460(P2008−17460A)
【公開日】平成20年1月24日(2008.1.24)
【国際特許分類】
【出願番号】特願2007−143755(P2007−143755)
【出願日】平成19年5月30日(2007.5.30)
【分割の表示】特願2007−61794(P2007−61794)の分割
【原出願日】平成14年10月4日(2002.10.4)
【出願人】(390009597)モトローラ・インコーポレイテッド (649)
【氏名又は名称原語表記】MOTOROLA INCORPORATED
【Fターム(参考)】
【公開日】平成20年1月24日(2008.1.24)
【国際特許分類】
【出願日】平成19年5月30日(2007.5.30)
【分割の表示】特願2007−61794(P2007−61794)の分割
【原出願日】平成14年10月4日(2002.10.4)
【出願人】(390009597)モトローラ・インコーポレイテッド (649)
【氏名又は名称原語表記】MOTOROLA INCORPORATED
【Fターム(参考)】
[ Back to top ]