シンボルパターンを作成する際の方法、それにより取得されるシンボルパターン、このようなシンボルパターンで位置を突き止めるための方法およびシステム、ならびに該方法を実行するためのコンピュータプログラム製品
本発明は、例えばペン状の機器によって手書き情報を記録するためにパターンによってカバーされる大きな領域の中で位置を決定するために活用されてよい二次元シンボルパターンを作成する際の方法に関する。本発明は所望の特性、すなわち任意の十分に大きな観察された部分が一意であり、位置の明確な決定を可能にするという特性を有するシンボルパターンを作成するために役立つ。該シンボルパターンは、各々がＰ（ｘ）を法としてｘｋにおける単項式の係数の固定された線形組み合わせに対応するシンボル値Ｓｋの非反復シーケンスに基づいており、ここでＰ（ｘ）はフィールドＦｑにおける度ｎの任意の多項式である。シンボルパターンはラッピングスキームに従ってシーケンスを折り畳むことにより生成される。本発明は、このシンボルパターンにおける観察されたシンボル値のグループの位置を発見するための方法およびシステム、ならびに該方法を実行するコンピュータプログラム製品にも関する。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の相互参照）
本願は、ともに２００４年７月８日に出願され、参照として本書に組み込まれるスウェーデン特許出願番号第０４０１８１２−３号、および米国仮特許出願番号第６０／５８５，８５６号の利益を主張する。
【０００２】
本発明は、例えばペン状の機器によって手書き情報を記録するためにパターンによってカバーされる大きな領域の中で位置を決定するために活用されてよい二次元シンボルパターンを作成する際の方法に関する。本発明は位置の明確な決定を可能にする所望の特性を有するシンボルパターンを作成するために役立つ。
【０００３】
本発明は、このシンボルパターンの中で観察されるシンボル値のグループの位置を突き止めるための方法およびシステム、ならびに該方法を実行するコンピュータプログラム製品にも関する。
【背景技術】
【０００４】
本分野では、メモリと、例えば用紙の上に印字される、またはコンピュータ画面に表示されるパターンを基準にしてペンの位置を計算するためのコンピュータ処理能力を組み込んだペン状の機器の中に走査されてよいパターンを形成することは既知である。
【０００５】
線形フィードバックシフトレジスタ（ＬＦＳＲ）によって反復シーケンスまたは非反復シーケンスを生成することも公知である。非反復シーケンスは、既定数の連続値の各サブシーケンスがシーケンスの中で一度だけ発生するという特性を有する。したがって、非反復シーケンスにおいては、既定の長さの各サブシーケンスの場所は明確に決定される。このような反復シーケンスを二次元シンボルパターンにラップ（ｗｒａｐ）または折り畳み（ｆｏｌｄ）、このようなパターンにおける位置を突き止めることは公知である。マイクロソフト社（Ｍｉｃｒｏｓｏｆｔ Ｃｏｒｐｏｒａｔｉｏｎ）に譲渡されている公開特許出願、米国第２００４／００８５２８７号、米国第２００４／００８５３０２号、米国第２００４／００８６１８１号、および米国第２００４／００８６１９１号を参照すること。
【特許文献１】スウェーデン特許出願番号第０４０１８１２−３号
【特許文献２】米国仮特許出願番号第６０／５８５，８５６号
【特許文献３】公開特許出願、米国第２００４／００８５２８７号
【特許文献４】米国第２００４／００８５３０２号
【特許文献５】米国第２００４／００８６１８１号
【特許文献６】米国第２００４／００８６１９１号
【特許文献７】米国特許第６，６７４，４２７号
【特許文献８】米国特許第６，６６７，６９５号
【非特許文献１】Ｒ．ＬｉｄｌおよびＨ．Ｎｉｅｄｅｒｒｅｉｔｅｒによる「有限体およびそれらの応用例入門（Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｆｉｎｉｔｅ ｆｉｅｌｄｓ ａｎｄ ｔｈｅｉｒ ａｐｐｌｉｃａｔｉｏｎｓ）」、第６章−線形再発性シーケンス（Ｌｉｎｅａｒ Ｒｅｃｕｒｒｉｎｇ Ｓｅｑｕｅｎｃｅｓ）、改訂版１９９４年、ケンブリッジ大学出版（Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ）
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従来の技術においてラップされたシーケンスにまつわる問題は、非反復シーケンスをラップすることにより取得されるこのような二次元パターンが所望の特性を有するか否か、つまり任意の十分に大きな観察されたパターンの部分が一意であることを見分ける方法がないことである。それが一意ではない場合には、明確にその位置を決定することは不可能である。
【課題を解決するための手段】
【０００７】
本発明はシンボルパターンの観察されたグループ（マスク）と有効な非反復シーケンスとの間の関係性を決定する条件を作成するためのツールを提供する。さらに、本発明はシンボルパターン内で位置を回復するためだけではなく、ラップされたシーケンスが位置決定のために適切な特性を有するか否かをもテストするための効率的な技法を提供する。
【０００８】
本発明は添付請求項に定義される。
【０００９】
本発明を添付図面を参照して詳しく後述する。
【発明を実施するための最良の形態】
【００１０】
さらなる理解のために、その内のいくつかが従来技術をも形成する本発明の背景にある数学について説明する。以下の用語と定義が使用される。
【００１１】
用語および定義
Ｓ 要素Ｓｋのシーケンス
Ｌ Ｓの長さ（ｋ＝０からＬ−１）
ＰＷ シーケンスＳおよびラッピングスキームＷによって形成されるシンボルパターン
Ｐ（ｘ）度ｎの多項式
ｎ 多項式Ｐ（ｘ）の度およびＬＦＳＲのサイズ
Ｎ Ｔのランク
ｒｋ 度ｎの剰余多項式で、Ｆｑ［ｘ］／Ｐ（ｘ）でカウントする
（Ｐ（ｘ）を法として）として定義される
Ｆｑ 典型的にはｑ＝２であるが、必ずしもｑ＝２ではない次数ｑの有限体
Ｇ（ｆ（ｘ））ｒｋにおける単項式ｘｎ−１の係数等の補助関数
Ｗ ラッピングシーケンス
ｗ ラップ長（行に関して、あるいは列に関してラッピングするとき）
Ｂ マスク＝幾何学的な走査パターン（＝球体）によって観察される要素の列ベクトル
Ｂ’ 同上、別の走査パターンを用いる
ＢＰ シンボルパターンの細分
ｍ Ｂのサイズ（＝“ｋｘ１”、矩形走査パターンの場合）；（ｍ≧ｎ）
Ｃ シーケンスＳにおける場所ｋに対応する剰余多項式ｒｋの（サイズｎの）係数の列ベクトル
Ｔ Ｂ＝ＴＣを履行する変換行列Ｔ、ＴはランクＮ＝ｎを有する
Ｔ’ Ｂ＝Ｔ’Ｃを履行する変換行列Ｔ’、ＴはランクＮ＝ｎ−ｊを有する
Ｘ、Ｙ 求められる位置（Ｂが不規則な形である場合、Ｂの左上隅、つまり「第1の」要素）
ＢＸ，Ｙ 求められた位置（Ｘ、Ｙ）でのＢ（およびＢ’）の要素
ＣＸ、Ｙ 求められた位置（Ｘ、Ｙ）に対応するＣの係数
ｋ Ｃの係数がＣＸ、Ｙに等しいシーケンスＳにおける場所
Ｈ ＨＴ＝０を履行し、一意のゼロ以外の列のあるチェックマトリックス
ｈｉ Ｈの列ｉ、Ｂのビットｉで発生するビットエラーの一連の徴候
ＬＦＳＲ 線形フィードバックシフトレジスタ
第1のタスクは所望の特性を有するシンボルパターンＰＷを作成することである。これは、長い非反復シーケンスＳを形成し、ラッピングしてから、十分に大きな観察されたマスクとシーケンスとの間の変換行列Ｔによって表される変換関係が規定される条件を履行することを確認することによって行われてよい。シンボルパターンの例は図１に示されており、白のピクセルと黒のピクセルが各々シンボル値１と０を表している。このようにして、シンボルパターンは、各々が少なくとも一つのシンボル値またはシーケンスＳの要素を表すシンボルの並べられた集合から構成される。
【００１２】
以下の説明はバイナリシンボル値から構成されているシーケンスＳに基づいているが、本発明の根本的な原理は概して任意のベース（つまり、フィールドＦｑの任意の次数ｑについて）におけるシンボル値に適用できる。
【００１３】
線形フィードバックシフトレジスタＬＦＳＲが、任意の十分に大きいサブシーケンスがシーケンスの中で一意となるように長い非反復バイナリシーケンスを生成するために使用できることが周知である。ｎサイズのＬＦＳＲは、閉鎖有向回路に沿って接続されるｒ０、ｒ１、．．．、ｒｎ−１と名前が付けられるｎ個のビットホルダーと、例えば図２に示されているような少なくとも一つのＸＯＲ−ゲートから成る簡略な計算装置である。該装置は離散時間ｔ０、ｔ１．．．で更新される。時間ｔｋでｋ＞０であり、あらゆるビットホルダーがそれを指す矢印の最後で計算された値で同時に更新される。時間ｔｋでの内容Ｃｋ＝（ｃ０（ｋ）、ｃ１（ｋ）、．．．、ｃｎ−１（ｋ））は時間ｔｋでのＬＦＳＲの状態と呼ばれる。時間ｔ０では、状態は例えば｛１、０、０、．．．、０｝である。各時間ｔｋでは、ｒｎ−１に含まれるビットは、バイナリシーケンスＳのｋ番目のビットを生成するためにシフトアウトされる。この多くの一意の状態があり、事実上、いくつかのＬＦＳＲについてはシーケンスの期間はこれほど長いため、生成されたシーケンスＳは、多くとも２ｎ−１という期間を有してよい。本発明の目的のために望ましい別の特性は、期間中のｎ個の連続ビットの任意のシーケンスが一意であるという点である。
【００１４】
図２の例では、ＬＦＳＲは五つのビットホルダーと一つのＸＯＲゲートを含む。描かれているＬＦＳＲは多項式Ｐ（ｘ）＝ｘ５＋ｘ２＋１を表し、Ｐ（ｚ）およびビットホルダーの初期値に応じて特定の長さの非反復シーケンスを生成してよい。ＬＦＳＲおよび反復シーケンスと非反復シーケンスの生成に関する詳細は、ｉ．ａ．Ｒ．ＬｉｄｌおよびＨ．Ｎｉｅｄｅｒｒｅｉｔｅｒによる「有限体およびそれらの応用例入門（Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｆｉｎｉｔｅ ｆｉｅｌｄｓ ａｎｄ ｔｈｅｉｒ ａｐｐｌｉｃａｔｉｏｎｓ）」、第６章−線形再発性シーケンス（Ｌｉｎｅａｒ Ｒｅｃｕｒｒｉｎｇ Ｓｅｑｕｅｎｃｅｓ）、改訂版１９９４年、ケンブリッジ大学出版（Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ）に記載されている。
【００１５】
ＬＦＳＲはシーケンスを生成するための実用的な装置である。幸運なことに、ＬＦＳＲは、次に説明する多項式環における生成作用素という点で自然な数理処理も認める。
【００１６】
Ｆ２をバイナリフィールドとする。Ｆ２［ｘ］を、Ｆ２からの係数を伴うｘのすべての多項式のフィールドとする。最後に、Ｆ２［ｘ］における多項式Ｐ（ｘ）の場合のＲ（ｘ、Ｐ（ｘ））に、Ｆ２［ｘ］／Ｐ（ｘ）におけるｋ＝０、１、２．．．の場合の要素ｘｋ、つまりＰ（ｘ）を法としてｘｋから成る環を示させ、ここで各単項式係数はＦ２にある。ｘｏ−１がＦ２［ｘ］におけるＰ（ｘ）により除算可能となるように最小の正のｏは、環の次数と呼ばれる。
【００１７】
環Ｒ（ｘ、Ｐ（ｘ））は次のようにＬＦＳＲに関連付けられる。ｎを（Ｐｘ）の度とし、ＸＯＲゲートがｐ（ｘ）の各単項式ｘＬについてｃＬ−１とｃＬとの間にあるｎサイズのＬＦＳＲを考える。ここで時間ｔｋでのＬＦＳＲの状態Ｃｋ＝（ｃ０（ｋ）、ｃ１（ｋ）、．．．、ｃｎ−１（ｋ））が、ｘでの乗算がＬＦＳＲのシフトに相当し、Ｐ（ｘ）による除算後の剰余を出すための減算がＸＯＲゲートの計算に相当するため、
に従うことを観察する。別段に定めをした場合、ＬＦＳＲの状態はＲ（ｘ，Ｐ（ｘ））の要素で一意に識別できる。したがって、ＬＦＳＲで生成されるシーケンスの期間はＲ（ｘ、Ｐ（ｘ））の次数に等しい。特にＦ２［ｘ］の度ｎの原始多項式に対応するＬＦＳＲは、全ゼロ文字列を除く長さｎのすべての考えられる０／１文字列が、シーケンスの中で一度（および一度だけ）発生するように期間２ｎ−１の周期的なシーケンスを生成する。
【００１８】
便宜上、何らかの補助記号を導入する。
とし、任意の多項式ｆ（ｘ）の場合、単項式ｘｎ−１がＰ（ｘ）を法として剰余多項式ｆ（ｘ）の一部である場合には、Ｇ（ｆ（ｘ））を１とし、それ以外の場合を０とする。
【００１９】
これまでの観察を踏まえ、ＬＦＳＲ生成シーケンスＳのｋ番目のビットＳｋと過去の任意の時点でのＬＦＳＲの状態との間に接続を確立する準備が完了している。
【００２０】
事実１：ＬＦＳＲ生成シーケンスＳのｋ番目のビットＳｋは、任意の
について
に従う。
【００２１】
ｎサイズのＬＦＳＲシーケンスＳを考え、ｗ番目のシンボルごとにＳを行に関してラッピングすることによって取得されるパターンＰＷが、任意の十分に大きい部分行列がＰＷの中で一意であるという特性をいつ得るのかを特徴付けることを希望する。正式には、パターンの行Ｙと列ＸでのエントリＰＷ（Ｘ、Ｙ）は、ＰＷ（Ｘ、Ｙ）＝ＳＹｗ＋Ｘによって指定される。
【００２２】
ｋ＝Ｙｘ＋Ｘである（Ｘ、Ｙ）の左上隅で、ＬＦＳＲ状態ＣｋをＰＷにおけるａ ｘ ｂ−部分行列に関連付ける。前記事実１は以下を行わせるに過ぎない。
【００２３】
Ｇ（ｆ（ｘ））は一次関数であるため、前記方程式を以下のように行列形式にすることができる。
【００２４】
簡潔にするため、この関係をＢ＝ＴＣとして書き、この場合、Ｇはパターン部分行列ベクトルであり、ＴはＬＦＳＲ状態からパターン部分行列への線形変換であり、ＣはＬＦＳＲ状態ベクトルである。我々の主要定理を前提とする。
【００２５】
定理：Ｆ２［ｘ］のＰ（ｘ）を度ｎの多項式とする。ＬをＲ（ｘ，Ｐ（ｘ））の次数とする。したがって、Ｒ（ｘ，Ｐ（ｘ））についてＬＦＳＲによって生成される長さＬのシーケンスＳから得られるパターンＰＷは、対応するＧがＦ２を超えるランクｎを有する場合に、ＰＷにおけるａ ｘ ｂ-部分行列が一意であるという特性を有する。さらに、次数が最大（Ｌ＝２ｎ−１）である場合に、必要な要件でもある。
【００２６】
前述のパターンＰＷは、ｗ番目のシンボルごとに行に関してシーケンスＳをラッピングすることによって取得された。代わりに、例えばｗ番目のシンボルごとに列に関してラッピングする、あるいはシーケンスの斜めの埋め込み等二次元パターンを形成するために、シーケンスの他の埋め込みまたはラッピングスキームが使用されてよい。さらに他の埋め込みが役立ってよいが、好ましくは隣接位置でのシーケンス要素の指数間の差異は一定である。明確にするために、パターンにおける各位置（Ｘ、Ｙ）について、シンボル値Ｓｋがパターンにおける位置（Ｘ，Ｙ）にあることを意味するｑ（Ｘ，Ｙ）＝ｋで示すことができるシーケンスＳにおける一意の場所ｋを関連付けた。ここで、Ｌを法としてｑ（Ｘ＋１，Ｙ）−ｑ（Ｘ，Ｙ）、そしてＬを法としてｑ（Ｘ，Ｙ＋１）−ｑ（Ｘ，Ｙ）が一定である場合、位置（Ｘ，Ｙ）の選択に関係なく、さらに明確にされるように、本発明により明らかな優位点が得られてよい。
【００２７】
さらに、本発明の技法は改変されるラッピングスキームを認めるだけではなく、一意性を調べ、前述のような単なる矩形と対照的にシンボル／シンボル値のグループの任意の形状の位置復号を処理するために使用されてもよい。以下では、小さい球体の形状におけるシンボル値のグループが一意であり、ラッピングスキームが列に関するラッピングを含むパターンの例を示す。
【００２８】
以下の多項式を検討し、
Ｆ２［ｘ］／Ｐ（ｘ）でカウントし、ベクトル
を定義する。
【００２９】
Ｐ（ｘ）は原始多項式であるため、ｒｋ＝ｒ０である第１のｋ＞０はｋ＝２１６−１である。
【００３０】
ｋ＝０，１，２、．．．、２１６−２の場合にシーケンスＧ（ｒｋ）をラッピングすることによって取得されるパターンを検討し、ここで任意の多項式ｆ（ｘ）のＧ（ｆ（ｘ））はＰ（ｘ）を法としてｆ（ｘ）における単項式ｘ１５の（バイナリ）係数である。一般的にはＧ（ｆ（ｘ））は、Ｐ（ｘ）を法としてｆ（ｘ）における単項式の係数の任意の線形組み合わせであってよい。
【００３１】
シンボルパターンＰＷの例が、白のピクセルと黒のピクセルが各々値１と０を表す図１に示されている。シーケンスは左上隅で開始し、下方へ続き、各１８７ビットをラッピングし、前の列の右の次の列で再び上部から開始する。シーケンスの選択、つまりＰ（ｘ）とラップ長１８７は任意ではない。対照的に、それらはいくつかの望ましい復号特性を取得するために細心の注意をもって選ばれる。
【００３２】
第一に、パターンの十分に大きな領域の各々がパターンの中で一意であり、高速反転、つまり見られている領域のパターンの中で座標の位置を突き止める高速アルゴリズムを認めることを保証することを希望する。
【００３３】
第二に、エラーの起こりにくい埋め込み、つまり数個の誤って解釈されたビットが存在する場合にも、ビットの見られた部分の座標を計算する能力を好むであろう。
【００３４】
（以下ではマスクまたは球体Ｂと呼ばれている）シンボル値のグループの例が図３に示されている。前記に示されたシンボルパターンは以下の特性を有する。
【００３５】
１．例えば図３の形状のシンボル値の任意のグループはパターンの中で一意である。つまり、パターンのいずれかで球体を見る場合、見られた球体がパターン内でどこに位置しているのかを区別することができる。さらに、一致を求めてパターンを完全に隈なく探すよりはるかに速く、これを行い、すべての考えられる球体対位置のペアを含む大きなルックアップテーブルを依然として利用するより、はるかに少ない記憶域の使用することが可能である。
【００３６】
２．パターンのいずれかで見られた球体における２１個のシンボル値（ビット）の内の多くとも一つが誤って解釈される、または見当たらない場合、これを検出し、その適切な値を速く計算することができる。これにはパターンにおける任意の二個の異なる球体が少なくとも三つの異なるシンボル値でなければならないことが求められることに留意する。
【００３７】
ラップ長１８７と組み合わされるＰ（ｘ）の選択がどのようにしてこれらの特性を有すると検証されたのか。これは、球体（位置（Ｘ、Ｙ））の（仮想）左上隅Ｇ（ｒｋ）を占めるｒｋを球体の見られているビットに関連付けることによって達成された。球体のビットが以下の表に示されるようにｒｋに関して書かれてよいことに留意する。
【００３８】
Ｇ（ｒｋ＋ｌ）が
における単項式の係数ｃｉの線形組み合わせとして表されてよいことを観察することによって、前述の数学的な説明に従って
を表す関係をＢ＝ＴＣと書くことができる。ここでＢはパターンＰＷの観察された要素に対応し、Ｃは剰余多項式ｒｋに対応する。有効なシーケンスＳにおいて、ＴはシーケンスＳ、ラッピングスキームＷおよびマスクＢの形状に依存するにすぎない。剰余多項式ｒｋ（つまりＰ（ｘ））を法としたｘｋ）、およびそれにより係数Ｃは再発関係を使用する反復二乗によって〜ｌｏｇ（ｋ）乗算を使用して計算できるため、
変換行列Ｔは効率的に計算できる。本例では、主要定理（前記）は、一意の高速反転可能球体を得るために行列がランク１６を有することを必要とすると規定している。ｗ＝１８７の場合、行列Ｔは、事実上Ｆ２を超えるランク１６を有する
のように見える。
【００３９】
有効なシーケンスＳを形成するために、以下のステップが実行されてよい。
【００４０】
・シーケンスＳがバイナリである、つまりフィールドｑ＝２であることを選択する。
【００４１】
・例えばｎの度＝１６で適切な多項式Ｐ（ｘ）を選択する。
【００４２】
・ラップ長ｗ＝１８７で列に関してラッピングする等、ラッピングスキームＷを選択する。行に関して、あるいは斜めにラップすることも可能である。斜めのラッピングの場合、パターンの幅と高さとの間の最大の公約数が１となることが望ましい場合がある。しかしながら、原則的には、ラッピングスキームに関する唯一の要件は、それがマスクＢにおける要素とシーケンスＳの対応する係数Ｃとの間で相対的な幾何学的な順序と関係性を維持することである。
【００４３】
・特定の形状、および例えばｍ＝２１等のビットｍの数をもつマスクパターンＢを選択する。
【００４４】
・ラッピングスキームＷ、マスクＢの形状および多項式Ｐ（ｘ）を使用して変換行列Ｔを計算する。
【００４５】
・ＴのランクＮ＝ｎであることをチェックする。そうである場合、シンボルパターンＰＷ、つまりラッピングスキームＷでラップされたシーケンスＳは所望の特性を有する。そうではない場合、ＴのランクＮ＝ｎとなるまでラッピングスキームＷ、マスクＢの形状、および多項式Ｐ（ｘ）の内の１つ以上を変える。
【００４６】
変換行列Ｔは反復二乗により適切に計算される。
【００４７】
また、図１に示されているように、例えば細分ＢＰ等、シンボルパターンＰＷの細分を形成することも可能である。これは、例えば一枚の用紙に印字することによってシンボルパターンＰＷの一部によってカバーされる領域を生成することが所望されるときに有効である。位置（Ｘ、Ｙ）でのＢＰの第一の要素は、ｒｋ≡ｘｋ（Ｐ（ｘ）を法として）を計算することによって、適切には反復二乗によって、それからｋ＝ｑ（Ｘ，Ｙ）についてシンボル値を得るためにＧ（ｒｋ）を評価することによって生成される。右側に次の要素を得るために、ｑ（Ｘ＋１、Ｙ）−ｑ（Ｘ，Ｙ）＝ｄが一定であるという事実を使用してよく、つまりｒｋ＋ｄを得るためにｒｋをｘｄで乗算することができ、シンボル値を得るためにＧ（ｒｋ＋ｄ）を計算してよい。したがって、パターンの一部を生成するときに右側の次のシンボルに移動することは簡単である。一般的には位置（Ｘ、Ｙ）の剰余多項式ｒｋを考えると、位置（Ｘ＋ｕ、Ｙ＋ｖ）で要素を生成することは、ベクトル（ｕ，ｖ）に対応するｘの累乗でｒｋを乗算してから、関数Ｇを適用することにより実行される。
【００４８】
序文によって言及されたように、シンボルパターンの一つの用途は、例えば用紙またはコンピュータ画面上等、表示されているパターンの上で動かされる検出装置の位置を決定することであってよい。例えば、参照として本書に組み込まれている出願人の米国特許第６，６７４，４２７号および第６，６６７，６９５号は位置決定のためのペン状の手動操作機器をさらに説明している。これらのペン状の機器は適切にプログラミングされている場合に本発明に従って位置決定のために使用できる。
【００４９】
以下では、このような検出装置の一実施形態を、図４を参照して説明する。本実施形態の検出装置４００は、画像がパターンの多くのシンボルを走査するように構成される捕捉手段４０３によって捕捉されるウィンドウまたは開口部４０２を形成するペンの形をした筺体またはシェル４０１を備える。
【００５０】
捕捉手段４０３は、シンボルの画像が白黒で、グレースケールで、またはカラーで取得されるようにシンボルパターンを撮像するために適した任意の種類のセンサを含んでよい。このようなセンサは、任意の適切な波長範囲内の電磁放射線に敏感であるソリッドステートシングルチップデバイスまたはマルチチップデバイスとすることができる。例えば、センサはＣＣＤ素子、ＣＭＯＳ素子、またはＣＩＤ素子（電荷注入装置）を含んでよい。代わりに、センサはシンボルの磁気特性を検出するための磁気センサを含んでよい。なおさらに、センサはシンボルの任意の化学的性質、音響特性、容量特性または誘導特性を有する画像を形成するように設計されてよい。
【００５１】
図４の検出装置４００は、ユーザが検出装置４００をシンボルパターン上の特定の位置に指すことを可能にし、場合により、ユーザがシンボルパターン上で自分が書いているまたは描画しているものを見ることができるように、通常の色素ベースのマーキングインクをシンボルパターンの上に付着するペン先または筆記用具４０４も備える。接触センサ４０５は、それが表面にいつペン先が表面に下ろされるのか、および／または表面から持ち上げられるのかを検出するためにペン先４０４に動作可能に接続される。接触センサ４０５の出力に基づき、捕捉手段４０３はペンダウンとペンアップとの間で、ペン先４０１の近くまたは周辺の領域の画像を捕捉するために制御される。検出装置４００は、バッテリおよび／または主電源コネクタ等の電源４０６と、有線または無線の短距離通信または遠隔通信のためのコンポーネントを備える通信インタフェース４０７と、ユーザにフィードバックを提供するためのディスプレイ、インジケータランプ、バイブレータ、またはスピーカ等のＭＭＩ（マンマシンインタフェース）４０８と、ユーザが検出装置４００を起動および／または制御できるようにする１個以上のボタンとも備える。
【００５２】
検出装置４００は、捕捉手段４０３によって走査されるシンボルを表すパターンデータを記憶するためのメモリ４１０と、多様な計算を実行するための信号処理装置４１１も含む。信号処理装置４１１は、例えば適切にプログラミングされたプロセッサによって、ＡＳＩＣ（特定用途向け集積回路）、ＤＳＰ（「デジタル信号プロセッサ」）またはＦＰＧＡ（フィールドプログラマブルゲートアレイ）等の特に適応されたハードウェアによって、離散デジタルコンポーネントまたはアナログコンポーネントによって、あるいはその任意の組み合わせによって実現されてよい。代わりに、メモリ４１０および／または信号処理装置４１１は、検出装置４００と通信する外部受信装置（不図示）に配置されてよい。
【００５３】
信号処理装置４１１によって行われる計算は、ここで図３に例示するマスクを参照して簡略に説明する。前述のように、捕捉手段４０３によって走査されるシンボルはシーケンスを基準にして公知の幾何学的な順序および関係性で配置される。マスクＢが、マスクＢの左上隅の座標（Ｘ、Ｙ）によって定義される位置に配置されると仮定する。マスクＢにおける観察されたシンボルはシンボル値、つまりシーケンスＳにおける要素を表す。マスクＢのこれらの観察された要素ＢＸ，Ｙは、シーケンスＳの特殊な係数ＣＸ，Ｙに相当する。要素ＢＸ，ＹとＣＸ，Ｙとの間の関係性は行列方程式Ｂ＝ＴＣで表される。
【００５４】
シンボルパターンＰＷの中で観察されたマスクＢの位置を突き止めることは、以下のステップを含んでよい。第一に、位置（Ｘ，Ｙ）にあるマスクＢの要素ＢＸ，Ｙが捕捉され、メモリに記憶される。次に、行列方程式ＢＸ，Ｙ＝ＴＣＸ，ＹがＣＸ，Ｙについて解かれる。
【００５５】
一実施形態では、変換行列Ｔ（適切には迅速な解答を可能にする因数分解として）、つまりその反形Ｔ−１がシーケンスＳについて事前に計算され、検出装置／受信装置のメモリに記憶されてよい。また、マスクＢは所定の固定形状を有してよい。変化する位置（Ｘ，Ｙ）での連続する場所について、対応する係数ＣＸ，Ｙが前述の行列方程式で解かれる。
【００５６】
係数ＣＸ，ＹはシーケンスＳにおける唯一の位置ｋに対応する。いったん係数ＣＸ，Ｙが見つけられると、ｋは例えば公開鍵暗号解読法（Ｓｉｌｖｅｒ−Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎ）アルゴリズムによって計算される。公開鍵暗号解読法方式は、（Ｐ（ｘ）を法として）
が係数ＣＸ，Ｙを有する離散値対数ｋを発見する。
【００５７】
Ｐ（ｘ）の次数は２１６−１＝３＊５＊１７＊２５７であり、公開鍵暗号解読法アルゴリズムは、次数の最大素数（この場合はは２５７）が十分に小さく、ｋの高速決定が可能であるときにはつねに効率的である。
【００５８】
ｋから、球体の左上隅の（Ｘ，Ｙ）−座標が、ｗ＝１８７の列に関するラップ長で（ｗを法としてｋ除数ｗ，（ｋ ｄｉｖ ｗ））で示される。
【００５９】
別の実施形態では、マスクＢ’の形状は変化してよい。例えば、マスクＢ’は図３で破線により示されている三つの要素を組み込んでよい。要素の数ｍは他の三つの要素を除外することによって一定にされてよい、あるいはさらに多くの要素を組み込むことによって増加されてよい。これは、復号されたシンボルの値が不確定である場合には、役立つことがある。したがって、有効な変換行列Ｔが見つけられるまで、マスクＢ’の多様な形状が試されてよい。この場合、変換行列Ｔ、つまりその反形Ｔ−１は、検出装置／受信装置において動的に計算されてよい。有効な変換行列ＴはランクＮ＝ｎを有するものとして定義されてよい。したがって、行列方程式Ｂ’＝ＴＣが解かれ、場所が上記において定義されたように突き止められてよい。
【００６０】
以下の復号方法が使用されてよい。解釈されたシンボル値を確実性に従って並べ替える。つまり画像処理がその解釈について最も確実であるシンボルで開始する。次に、線形変換行列がランクｎを得るまでシンボル値を一個づつ加算し、位置について解く。隣接する要素の矩形または球体だけではなく、マスクの任意の形状が使用されてよいことに留意する。
【００６１】
さらに追加の実施形態では、有効な変換行列Ｔ’がランクＮ＝ｎ−ｊを有するものとして定義される。この場合、行列方程式Ｂ＝Ｔ’Ｃは、異なる位置（Ｘ、Ｙ）およびシーケンスＳにおける場所ｋに対応する最大２ｊの解を有することになる。言うまでもなく、一つの解だけが正しい解であり、偽の解は、覆っている（ｏｖｅｒｌｙｉｎｇ）経験則によって排除されてよい。例えば、偽の解は、１つ以上の先行のおよび／または後続の位置に関して連続性条件（例えば、空間距離、加速度等）をチェックすることによって排除されてよい。
【００６２】
マスクＢ’を変化させ、そして、有効な変換行列Ｔ’をランクＮ＝ｎ−ｊを有するものとして定義させることもできる。第一に、有効な変換行列Ｔ’が突き止められるまで、マスクＢ’の多様な形状が試されてよい。次に、多様な解のある行列方程式Ｂ’＝Ｔ’Ｃが解かれ、偽の解が排除されてよい。
【００６３】
本発明は、サンプリングされた観察済みのビットのエラー訂正を実行するためのツールをも提供する。Ｔｔ（Ｔ転置済み）の零空間は、ＨＴ＝０を達成する線形に独立した行でバイナリ行列Ｈを取得するための公知の技法によって評価できる。
【００６４】
本例では、Ｈは５ｘ２１行列であり、Ｈ＝［ｈ１ｈ２ｈ３．．．ｈ２１］は以下のとおりである。
【００６５】
このような行列Ｈは、Ｔにより生成される線形コードのエラー訂正コードとの関連においってチェックマトリックスとして知られている。我々のＨが、すべての列ｈｉが全ゼロベクトルと異なり、一意であるという特性を有することに留意する。パターンにおけるすべての考えられる観察されたマスクＢは係数ベクトルＣの何らかの選択のために、フォーマットＢ＝ＴＣであるため、ｉで誤りビットのひとつの見られたマスクは、Ｂ＊＝Ｂ＋ｅｉと書き込まれ、ｅｉはビット位置ｉの中で値一（１）を、および他のすべての位置で値ゼロ（０）を有する列ベクトルである。チェックマトリックスによる乗算は以下を生じさせる。
【００６６】
つまり、Ｈで見られたマスクを乗算し、エラーの場所を突き止めるために取得された文字列を調べることによって単一のエラーを突き止め、訂正することができる。誤りビットを反転すると正しい値が与えられ、ガウス消去法および例えば前述のように公開鍵暗号解読法アルゴリズムを用いて等、Ｔを介した後退代入を使用してＣについて解くことができる。
【００６７】
前記エラー訂正は、ランクＮ＝ｎ−ｊ（すなわちＨ’Ｔ’＝０）を有する変換行列Ｔ’と関連するチェックマトリックスＨ’で等しく適応できる。
【００６８】
ｖ個のビットが誤っているのを許すことを許容しうるであろうパターンを発見することを希望する場合は、任意の２ｖの列が線形に独立しているという特性のあるチェックマトリックスＨを見つける必要がある。これは線形符号の理論から周知である。
【００６９】
検出装置が、例えば文字と画像を形成するためにシンボルパターンのある表面上を動かされると、一連の復号動作または一発見動作が実行される。そこでは、各位置は前述のように、固定または可変マスクＢ、Ｂ’を用い、ランクＮ＝ｎまたはＮ＝ｎ−ｊを有する変換行列Ｔ、Ｔ’を用いて復号されてよい。復号方式も位置との間で変化してよい。
【００７０】
本発明は、当業者によって理解されるように、ソフトウェアとハードウェアの多様な組み合わせにより実現されてよい。本発明の範囲は以下の請求項によってのみ制限される。
【図面の簡単な説明】
【００７１】
【図１】シンボルパターンとして具体化されるラップされたシーケンスの例である。
【図２】線形フィードバックシフトレジスタの概略図である。
【図３】シンボルパターンの観察された部分集合を定義する例示的なマスクの概略図である。
【図４】本発明の実施形態によるペン形状をした検出装置の、部分的断面の概略側面図である。
【技術分野】
【０００１】
（関連出願の相互参照）
本願は、ともに２００４年７月８日に出願され、参照として本書に組み込まれるスウェーデン特許出願番号第０４０１８１２−３号、および米国仮特許出願番号第６０／５８５，８５６号の利益を主張する。
【０００２】
本発明は、例えばペン状の機器によって手書き情報を記録するためにパターンによってカバーされる大きな領域の中で位置を決定するために活用されてよい二次元シンボルパターンを作成する際の方法に関する。本発明は位置の明確な決定を可能にする所望の特性を有するシンボルパターンを作成するために役立つ。
【０００３】
本発明は、このシンボルパターンの中で観察されるシンボル値のグループの位置を突き止めるための方法およびシステム、ならびに該方法を実行するコンピュータプログラム製品にも関する。
【背景技術】
【０００４】
本分野では、メモリと、例えば用紙の上に印字される、またはコンピュータ画面に表示されるパターンを基準にしてペンの位置を計算するためのコンピュータ処理能力を組み込んだペン状の機器の中に走査されてよいパターンを形成することは既知である。
【０００５】
線形フィードバックシフトレジスタ（ＬＦＳＲ）によって反復シーケンスまたは非反復シーケンスを生成することも公知である。非反復シーケンスは、既定数の連続値の各サブシーケンスがシーケンスの中で一度だけ発生するという特性を有する。したがって、非反復シーケンスにおいては、既定の長さの各サブシーケンスの場所は明確に決定される。このような反復シーケンスを二次元シンボルパターンにラップ（ｗｒａｐ）または折り畳み（ｆｏｌｄ）、このようなパターンにおける位置を突き止めることは公知である。マイクロソフト社（Ｍｉｃｒｏｓｏｆｔ Ｃｏｒｐｏｒａｔｉｏｎ）に譲渡されている公開特許出願、米国第２００４／００８５２８７号、米国第２００４／００８５３０２号、米国第２００４／００８６１８１号、および米国第２００４／００８６１９１号を参照すること。
【特許文献１】スウェーデン特許出願番号第０４０１８１２−３号
【特許文献２】米国仮特許出願番号第６０／５８５，８５６号
【特許文献３】公開特許出願、米国第２００４／００８５２８７号
【特許文献４】米国第２００４／００８５３０２号
【特許文献５】米国第２００４／００８６１８１号
【特許文献６】米国第２００４／００８６１９１号
【特許文献７】米国特許第６，６７４，４２７号
【特許文献８】米国特許第６，６６７，６９５号
【非特許文献１】Ｒ．ＬｉｄｌおよびＨ．Ｎｉｅｄｅｒｒｅｉｔｅｒによる「有限体およびそれらの応用例入門（Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｆｉｎｉｔｅ ｆｉｅｌｄｓ ａｎｄ ｔｈｅｉｒ ａｐｐｌｉｃａｔｉｏｎｓ）」、第６章−線形再発性シーケンス（Ｌｉｎｅａｒ Ｒｅｃｕｒｒｉｎｇ Ｓｅｑｕｅｎｃｅｓ）、改訂版１９９４年、ケンブリッジ大学出版（Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ）
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従来の技術においてラップされたシーケンスにまつわる問題は、非反復シーケンスをラップすることにより取得されるこのような二次元パターンが所望の特性を有するか否か、つまり任意の十分に大きな観察されたパターンの部分が一意であることを見分ける方法がないことである。それが一意ではない場合には、明確にその位置を決定することは不可能である。
【課題を解決するための手段】
【０００７】
本発明はシンボルパターンの観察されたグループ（マスク）と有効な非反復シーケンスとの間の関係性を決定する条件を作成するためのツールを提供する。さらに、本発明はシンボルパターン内で位置を回復するためだけではなく、ラップされたシーケンスが位置決定のために適切な特性を有するか否かをもテストするための効率的な技法を提供する。
【０００８】
本発明は添付請求項に定義される。
【０００９】
本発明を添付図面を参照して詳しく後述する。
【発明を実施するための最良の形態】
【００１０】
さらなる理解のために、その内のいくつかが従来技術をも形成する本発明の背景にある数学について説明する。以下の用語と定義が使用される。
【００１１】
用語および定義
Ｓ 要素Ｓｋのシーケンス
Ｌ Ｓの長さ（ｋ＝０からＬ−１）
ＰＷ シーケンスＳおよびラッピングスキームＷによって形成されるシンボルパターン
Ｐ（ｘ）度ｎの多項式
ｎ 多項式Ｐ（ｘ）の度およびＬＦＳＲのサイズ
Ｎ Ｔのランク
ｒｋ 度ｎの剰余多項式で、Ｆｑ［ｘ］／Ｐ（ｘ）でカウントする
（Ｐ（ｘ）を法として）として定義される
Ｆｑ 典型的にはｑ＝２であるが、必ずしもｑ＝２ではない次数ｑの有限体
Ｇ（ｆ（ｘ））ｒｋにおける単項式ｘｎ−１の係数等の補助関数
Ｗ ラッピングシーケンス
ｗ ラップ長（行に関して、あるいは列に関してラッピングするとき）
Ｂ マスク＝幾何学的な走査パターン（＝球体）によって観察される要素の列ベクトル
Ｂ’ 同上、別の走査パターンを用いる
ＢＰ シンボルパターンの細分
ｍ Ｂのサイズ（＝“ｋｘ１”、矩形走査パターンの場合）；（ｍ≧ｎ）
Ｃ シーケンスＳにおける場所ｋに対応する剰余多項式ｒｋの（サイズｎの）係数の列ベクトル
Ｔ Ｂ＝ＴＣを履行する変換行列Ｔ、ＴはランクＮ＝ｎを有する
Ｔ’ Ｂ＝Ｔ’Ｃを履行する変換行列Ｔ’、ＴはランクＮ＝ｎ−ｊを有する
Ｘ、Ｙ 求められる位置（Ｂが不規則な形である場合、Ｂの左上隅、つまり「第1の」要素）
ＢＸ，Ｙ 求められた位置（Ｘ、Ｙ）でのＢ（およびＢ’）の要素
ＣＸ、Ｙ 求められた位置（Ｘ、Ｙ）に対応するＣの係数
ｋ Ｃの係数がＣＸ、Ｙに等しいシーケンスＳにおける場所
Ｈ ＨＴ＝０を履行し、一意のゼロ以外の列のあるチェックマトリックス
ｈｉ Ｈの列ｉ、Ｂのビットｉで発生するビットエラーの一連の徴候
ＬＦＳＲ 線形フィードバックシフトレジスタ
第1のタスクは所望の特性を有するシンボルパターンＰＷを作成することである。これは、長い非反復シーケンスＳを形成し、ラッピングしてから、十分に大きな観察されたマスクとシーケンスとの間の変換行列Ｔによって表される変換関係が規定される条件を履行することを確認することによって行われてよい。シンボルパターンの例は図１に示されており、白のピクセルと黒のピクセルが各々シンボル値１と０を表している。このようにして、シンボルパターンは、各々が少なくとも一つのシンボル値またはシーケンスＳの要素を表すシンボルの並べられた集合から構成される。
【００１２】
以下の説明はバイナリシンボル値から構成されているシーケンスＳに基づいているが、本発明の根本的な原理は概して任意のベース（つまり、フィールドＦｑの任意の次数ｑについて）におけるシンボル値に適用できる。
【００１３】
線形フィードバックシフトレジスタＬＦＳＲが、任意の十分に大きいサブシーケンスがシーケンスの中で一意となるように長い非反復バイナリシーケンスを生成するために使用できることが周知である。ｎサイズのＬＦＳＲは、閉鎖有向回路に沿って接続されるｒ０、ｒ１、．．．、ｒｎ−１と名前が付けられるｎ個のビットホルダーと、例えば図２に示されているような少なくとも一つのＸＯＲ−ゲートから成る簡略な計算装置である。該装置は離散時間ｔ０、ｔ１．．．で更新される。時間ｔｋでｋ＞０であり、あらゆるビットホルダーがそれを指す矢印の最後で計算された値で同時に更新される。時間ｔｋでの内容Ｃｋ＝（ｃ０（ｋ）、ｃ１（ｋ）、．．．、ｃｎ−１（ｋ））は時間ｔｋでのＬＦＳＲの状態と呼ばれる。時間ｔ０では、状態は例えば｛１、０、０、．．．、０｝である。各時間ｔｋでは、ｒｎ−１に含まれるビットは、バイナリシーケンスＳのｋ番目のビットを生成するためにシフトアウトされる。この多くの一意の状態があり、事実上、いくつかのＬＦＳＲについてはシーケンスの期間はこれほど長いため、生成されたシーケンスＳは、多くとも２ｎ−１という期間を有してよい。本発明の目的のために望ましい別の特性は、期間中のｎ個の連続ビットの任意のシーケンスが一意であるという点である。
【００１４】
図２の例では、ＬＦＳＲは五つのビットホルダーと一つのＸＯＲゲートを含む。描かれているＬＦＳＲは多項式Ｐ（ｘ）＝ｘ５＋ｘ２＋１を表し、Ｐ（ｚ）およびビットホルダーの初期値に応じて特定の長さの非反復シーケンスを生成してよい。ＬＦＳＲおよび反復シーケンスと非反復シーケンスの生成に関する詳細は、ｉ．ａ．Ｒ．ＬｉｄｌおよびＨ．Ｎｉｅｄｅｒｒｅｉｔｅｒによる「有限体およびそれらの応用例入門（Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｆｉｎｉｔｅ ｆｉｅｌｄｓ ａｎｄ ｔｈｅｉｒ ａｐｐｌｉｃａｔｉｏｎｓ）」、第６章−線形再発性シーケンス（Ｌｉｎｅａｒ Ｒｅｃｕｒｒｉｎｇ Ｓｅｑｕｅｎｃｅｓ）、改訂版１９９４年、ケンブリッジ大学出版（Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ）に記載されている。
【００１５】
ＬＦＳＲはシーケンスを生成するための実用的な装置である。幸運なことに、ＬＦＳＲは、次に説明する多項式環における生成作用素という点で自然な数理処理も認める。
【００１６】
Ｆ２をバイナリフィールドとする。Ｆ２［ｘ］を、Ｆ２からの係数を伴うｘのすべての多項式のフィールドとする。最後に、Ｆ２［ｘ］における多項式Ｐ（ｘ）の場合のＲ（ｘ、Ｐ（ｘ））に、Ｆ２［ｘ］／Ｐ（ｘ）におけるｋ＝０、１、２．．．の場合の要素ｘｋ、つまりＰ（ｘ）を法としてｘｋから成る環を示させ、ここで各単項式係数はＦ２にある。ｘｏ−１がＦ２［ｘ］におけるＰ（ｘ）により除算可能となるように最小の正のｏは、環の次数と呼ばれる。
【００１７】
環Ｒ（ｘ、Ｐ（ｘ））は次のようにＬＦＳＲに関連付けられる。ｎを（Ｐｘ）の度とし、ＸＯＲゲートがｐ（ｘ）の各単項式ｘＬについてｃＬ−１とｃＬとの間にあるｎサイズのＬＦＳＲを考える。ここで時間ｔｋでのＬＦＳＲの状態Ｃｋ＝（ｃ０（ｋ）、ｃ１（ｋ）、．．．、ｃｎ−１（ｋ））が、ｘでの乗算がＬＦＳＲのシフトに相当し、Ｐ（ｘ）による除算後の剰余を出すための減算がＸＯＲゲートの計算に相当するため、
に従うことを観察する。別段に定めをした場合、ＬＦＳＲの状態はＲ（ｘ，Ｐ（ｘ））の要素で一意に識別できる。したがって、ＬＦＳＲで生成されるシーケンスの期間はＲ（ｘ、Ｐ（ｘ））の次数に等しい。特にＦ２［ｘ］の度ｎの原始多項式に対応するＬＦＳＲは、全ゼロ文字列を除く長さｎのすべての考えられる０／１文字列が、シーケンスの中で一度（および一度だけ）発生するように期間２ｎ−１の周期的なシーケンスを生成する。
【００１８】
便宜上、何らかの補助記号を導入する。
とし、任意の多項式ｆ（ｘ）の場合、単項式ｘｎ−１がＰ（ｘ）を法として剰余多項式ｆ（ｘ）の一部である場合には、Ｇ（ｆ（ｘ））を１とし、それ以外の場合を０とする。
【００１９】
これまでの観察を踏まえ、ＬＦＳＲ生成シーケンスＳのｋ番目のビットＳｋと過去の任意の時点でのＬＦＳＲの状態との間に接続を確立する準備が完了している。
【００２０】
事実１：ＬＦＳＲ生成シーケンスＳのｋ番目のビットＳｋは、任意の
について
に従う。
【００２１】
ｎサイズのＬＦＳＲシーケンスＳを考え、ｗ番目のシンボルごとにＳを行に関してラッピングすることによって取得されるパターンＰＷが、任意の十分に大きい部分行列がＰＷの中で一意であるという特性をいつ得るのかを特徴付けることを希望する。正式には、パターンの行Ｙと列ＸでのエントリＰＷ（Ｘ、Ｙ）は、ＰＷ（Ｘ、Ｙ）＝ＳＹｗ＋Ｘによって指定される。
【００２２】
ｋ＝Ｙｘ＋Ｘである（Ｘ、Ｙ）の左上隅で、ＬＦＳＲ状態ＣｋをＰＷにおけるａ ｘ ｂ−部分行列に関連付ける。前記事実１は以下を行わせるに過ぎない。
【００２３】
Ｇ（ｆ（ｘ））は一次関数であるため、前記方程式を以下のように行列形式にすることができる。
【００２４】
簡潔にするため、この関係をＢ＝ＴＣとして書き、この場合、Ｇはパターン部分行列ベクトルであり、ＴはＬＦＳＲ状態からパターン部分行列への線形変換であり、ＣはＬＦＳＲ状態ベクトルである。我々の主要定理を前提とする。
【００２５】
定理：Ｆ２［ｘ］のＰ（ｘ）を度ｎの多項式とする。ＬをＲ（ｘ，Ｐ（ｘ））の次数とする。したがって、Ｒ（ｘ，Ｐ（ｘ））についてＬＦＳＲによって生成される長さＬのシーケンスＳから得られるパターンＰＷは、対応するＧがＦ２を超えるランクｎを有する場合に、ＰＷにおけるａ ｘ ｂ-部分行列が一意であるという特性を有する。さらに、次数が最大（Ｌ＝２ｎ−１）である場合に、必要な要件でもある。
【００２６】
前述のパターンＰＷは、ｗ番目のシンボルごとに行に関してシーケンスＳをラッピングすることによって取得された。代わりに、例えばｗ番目のシンボルごとに列に関してラッピングする、あるいはシーケンスの斜めの埋め込み等二次元パターンを形成するために、シーケンスの他の埋め込みまたはラッピングスキームが使用されてよい。さらに他の埋め込みが役立ってよいが、好ましくは隣接位置でのシーケンス要素の指数間の差異は一定である。明確にするために、パターンにおける各位置（Ｘ、Ｙ）について、シンボル値Ｓｋがパターンにおける位置（Ｘ，Ｙ）にあることを意味するｑ（Ｘ，Ｙ）＝ｋで示すことができるシーケンスＳにおける一意の場所ｋを関連付けた。ここで、Ｌを法としてｑ（Ｘ＋１，Ｙ）−ｑ（Ｘ，Ｙ）、そしてＬを法としてｑ（Ｘ，Ｙ＋１）−ｑ（Ｘ，Ｙ）が一定である場合、位置（Ｘ，Ｙ）の選択に関係なく、さらに明確にされるように、本発明により明らかな優位点が得られてよい。
【００２７】
さらに、本発明の技法は改変されるラッピングスキームを認めるだけではなく、一意性を調べ、前述のような単なる矩形と対照的にシンボル／シンボル値のグループの任意の形状の位置復号を処理するために使用されてもよい。以下では、小さい球体の形状におけるシンボル値のグループが一意であり、ラッピングスキームが列に関するラッピングを含むパターンの例を示す。
【００２８】
以下の多項式を検討し、
Ｆ２［ｘ］／Ｐ（ｘ）でカウントし、ベクトル
を定義する。
【００２９】
Ｐ（ｘ）は原始多項式であるため、ｒｋ＝ｒ０である第１のｋ＞０はｋ＝２１６−１である。
【００３０】
ｋ＝０，１，２、．．．、２１６−２の場合にシーケンスＧ（ｒｋ）をラッピングすることによって取得されるパターンを検討し、ここで任意の多項式ｆ（ｘ）のＧ（ｆ（ｘ））はＰ（ｘ）を法としてｆ（ｘ）における単項式ｘ１５の（バイナリ）係数である。一般的にはＧ（ｆ（ｘ））は、Ｐ（ｘ）を法としてｆ（ｘ）における単項式の係数の任意の線形組み合わせであってよい。
【００３１】
シンボルパターンＰＷの例が、白のピクセルと黒のピクセルが各々値１と０を表す図１に示されている。シーケンスは左上隅で開始し、下方へ続き、各１８７ビットをラッピングし、前の列の右の次の列で再び上部から開始する。シーケンスの選択、つまりＰ（ｘ）とラップ長１８７は任意ではない。対照的に、それらはいくつかの望ましい復号特性を取得するために細心の注意をもって選ばれる。
【００３２】
第一に、パターンの十分に大きな領域の各々がパターンの中で一意であり、高速反転、つまり見られている領域のパターンの中で座標の位置を突き止める高速アルゴリズムを認めることを保証することを希望する。
【００３３】
第二に、エラーの起こりにくい埋め込み、つまり数個の誤って解釈されたビットが存在する場合にも、ビットの見られた部分の座標を計算する能力を好むであろう。
【００３４】
（以下ではマスクまたは球体Ｂと呼ばれている）シンボル値のグループの例が図３に示されている。前記に示されたシンボルパターンは以下の特性を有する。
【００３５】
１．例えば図３の形状のシンボル値の任意のグループはパターンの中で一意である。つまり、パターンのいずれかで球体を見る場合、見られた球体がパターン内でどこに位置しているのかを区別することができる。さらに、一致を求めてパターンを完全に隈なく探すよりはるかに速く、これを行い、すべての考えられる球体対位置のペアを含む大きなルックアップテーブルを依然として利用するより、はるかに少ない記憶域の使用することが可能である。
【００３６】
２．パターンのいずれかで見られた球体における２１個のシンボル値（ビット）の内の多くとも一つが誤って解釈される、または見当たらない場合、これを検出し、その適切な値を速く計算することができる。これにはパターンにおける任意の二個の異なる球体が少なくとも三つの異なるシンボル値でなければならないことが求められることに留意する。
【００３７】
ラップ長１８７と組み合わされるＰ（ｘ）の選択がどのようにしてこれらの特性を有すると検証されたのか。これは、球体（位置（Ｘ、Ｙ））の（仮想）左上隅Ｇ（ｒｋ）を占めるｒｋを球体の見られているビットに関連付けることによって達成された。球体のビットが以下の表に示されるようにｒｋに関して書かれてよいことに留意する。
【００３８】
Ｇ（ｒｋ＋ｌ）が
における単項式の係数ｃｉの線形組み合わせとして表されてよいことを観察することによって、前述の数学的な説明に従って
を表す関係をＢ＝ＴＣと書くことができる。ここでＢはパターンＰＷの観察された要素に対応し、Ｃは剰余多項式ｒｋに対応する。有効なシーケンスＳにおいて、ＴはシーケンスＳ、ラッピングスキームＷおよびマスクＢの形状に依存するにすぎない。剰余多項式ｒｋ（つまりＰ（ｘ））を法としたｘｋ）、およびそれにより係数Ｃは再発関係を使用する反復二乗によって〜ｌｏｇ（ｋ）乗算を使用して計算できるため、
変換行列Ｔは効率的に計算できる。本例では、主要定理（前記）は、一意の高速反転可能球体を得るために行列がランク１６を有することを必要とすると規定している。ｗ＝１８７の場合、行列Ｔは、事実上Ｆ２を超えるランク１６を有する
のように見える。
【００３９】
有効なシーケンスＳを形成するために、以下のステップが実行されてよい。
【００４０】
・シーケンスＳがバイナリである、つまりフィールドｑ＝２であることを選択する。
【００４１】
・例えばｎの度＝１６で適切な多項式Ｐ（ｘ）を選択する。
【００４２】
・ラップ長ｗ＝１８７で列に関してラッピングする等、ラッピングスキームＷを選択する。行に関して、あるいは斜めにラップすることも可能である。斜めのラッピングの場合、パターンの幅と高さとの間の最大の公約数が１となることが望ましい場合がある。しかしながら、原則的には、ラッピングスキームに関する唯一の要件は、それがマスクＢにおける要素とシーケンスＳの対応する係数Ｃとの間で相対的な幾何学的な順序と関係性を維持することである。
【００４３】
・特定の形状、および例えばｍ＝２１等のビットｍの数をもつマスクパターンＢを選択する。
【００４４】
・ラッピングスキームＷ、マスクＢの形状および多項式Ｐ（ｘ）を使用して変換行列Ｔを計算する。
【００４５】
・ＴのランクＮ＝ｎであることをチェックする。そうである場合、シンボルパターンＰＷ、つまりラッピングスキームＷでラップされたシーケンスＳは所望の特性を有する。そうではない場合、ＴのランクＮ＝ｎとなるまでラッピングスキームＷ、マスクＢの形状、および多項式Ｐ（ｘ）の内の１つ以上を変える。
【００４６】
変換行列Ｔは反復二乗により適切に計算される。
【００４７】
また、図１に示されているように、例えば細分ＢＰ等、シンボルパターンＰＷの細分を形成することも可能である。これは、例えば一枚の用紙に印字することによってシンボルパターンＰＷの一部によってカバーされる領域を生成することが所望されるときに有効である。位置（Ｘ、Ｙ）でのＢＰの第一の要素は、ｒｋ≡ｘｋ（Ｐ（ｘ）を法として）を計算することによって、適切には反復二乗によって、それからｋ＝ｑ（Ｘ，Ｙ）についてシンボル値を得るためにＧ（ｒｋ）を評価することによって生成される。右側に次の要素を得るために、ｑ（Ｘ＋１、Ｙ）−ｑ（Ｘ，Ｙ）＝ｄが一定であるという事実を使用してよく、つまりｒｋ＋ｄを得るためにｒｋをｘｄで乗算することができ、シンボル値を得るためにＧ（ｒｋ＋ｄ）を計算してよい。したがって、パターンの一部を生成するときに右側の次のシンボルに移動することは簡単である。一般的には位置（Ｘ、Ｙ）の剰余多項式ｒｋを考えると、位置（Ｘ＋ｕ、Ｙ＋ｖ）で要素を生成することは、ベクトル（ｕ，ｖ）に対応するｘの累乗でｒｋを乗算してから、関数Ｇを適用することにより実行される。
【００４８】
序文によって言及されたように、シンボルパターンの一つの用途は、例えば用紙またはコンピュータ画面上等、表示されているパターンの上で動かされる検出装置の位置を決定することであってよい。例えば、参照として本書に組み込まれている出願人の米国特許第６，６７４，４２７号および第６，６６７，６９５号は位置決定のためのペン状の手動操作機器をさらに説明している。これらのペン状の機器は適切にプログラミングされている場合に本発明に従って位置決定のために使用できる。
【００４９】
以下では、このような検出装置の一実施形態を、図４を参照して説明する。本実施形態の検出装置４００は、画像がパターンの多くのシンボルを走査するように構成される捕捉手段４０３によって捕捉されるウィンドウまたは開口部４０２を形成するペンの形をした筺体またはシェル４０１を備える。
【００５０】
捕捉手段４０３は、シンボルの画像が白黒で、グレースケールで、またはカラーで取得されるようにシンボルパターンを撮像するために適した任意の種類のセンサを含んでよい。このようなセンサは、任意の適切な波長範囲内の電磁放射線に敏感であるソリッドステートシングルチップデバイスまたはマルチチップデバイスとすることができる。例えば、センサはＣＣＤ素子、ＣＭＯＳ素子、またはＣＩＤ素子（電荷注入装置）を含んでよい。代わりに、センサはシンボルの磁気特性を検出するための磁気センサを含んでよい。なおさらに、センサはシンボルの任意の化学的性質、音響特性、容量特性または誘導特性を有する画像を形成するように設計されてよい。
【００５１】
図４の検出装置４００は、ユーザが検出装置４００をシンボルパターン上の特定の位置に指すことを可能にし、場合により、ユーザがシンボルパターン上で自分が書いているまたは描画しているものを見ることができるように、通常の色素ベースのマーキングインクをシンボルパターンの上に付着するペン先または筆記用具４０４も備える。接触センサ４０５は、それが表面にいつペン先が表面に下ろされるのか、および／または表面から持ち上げられるのかを検出するためにペン先４０４に動作可能に接続される。接触センサ４０５の出力に基づき、捕捉手段４０３はペンダウンとペンアップとの間で、ペン先４０１の近くまたは周辺の領域の画像を捕捉するために制御される。検出装置４００は、バッテリおよび／または主電源コネクタ等の電源４０６と、有線または無線の短距離通信または遠隔通信のためのコンポーネントを備える通信インタフェース４０７と、ユーザにフィードバックを提供するためのディスプレイ、インジケータランプ、バイブレータ、またはスピーカ等のＭＭＩ（マンマシンインタフェース）４０８と、ユーザが検出装置４００を起動および／または制御できるようにする１個以上のボタンとも備える。
【００５２】
検出装置４００は、捕捉手段４０３によって走査されるシンボルを表すパターンデータを記憶するためのメモリ４１０と、多様な計算を実行するための信号処理装置４１１も含む。信号処理装置４１１は、例えば適切にプログラミングされたプロセッサによって、ＡＳＩＣ（特定用途向け集積回路）、ＤＳＰ（「デジタル信号プロセッサ」）またはＦＰＧＡ（フィールドプログラマブルゲートアレイ）等の特に適応されたハードウェアによって、離散デジタルコンポーネントまたはアナログコンポーネントによって、あるいはその任意の組み合わせによって実現されてよい。代わりに、メモリ４１０および／または信号処理装置４１１は、検出装置４００と通信する外部受信装置（不図示）に配置されてよい。
【００５３】
信号処理装置４１１によって行われる計算は、ここで図３に例示するマスクを参照して簡略に説明する。前述のように、捕捉手段４０３によって走査されるシンボルはシーケンスを基準にして公知の幾何学的な順序および関係性で配置される。マスクＢが、マスクＢの左上隅の座標（Ｘ、Ｙ）によって定義される位置に配置されると仮定する。マスクＢにおける観察されたシンボルはシンボル値、つまりシーケンスＳにおける要素を表す。マスクＢのこれらの観察された要素ＢＸ，Ｙは、シーケンスＳの特殊な係数ＣＸ，Ｙに相当する。要素ＢＸ，ＹとＣＸ，Ｙとの間の関係性は行列方程式Ｂ＝ＴＣで表される。
【００５４】
シンボルパターンＰＷの中で観察されたマスクＢの位置を突き止めることは、以下のステップを含んでよい。第一に、位置（Ｘ，Ｙ）にあるマスクＢの要素ＢＸ，Ｙが捕捉され、メモリに記憶される。次に、行列方程式ＢＸ，Ｙ＝ＴＣＸ，ＹがＣＸ，Ｙについて解かれる。
【００５５】
一実施形態では、変換行列Ｔ（適切には迅速な解答を可能にする因数分解として）、つまりその反形Ｔ−１がシーケンスＳについて事前に計算され、検出装置／受信装置のメモリに記憶されてよい。また、マスクＢは所定の固定形状を有してよい。変化する位置（Ｘ，Ｙ）での連続する場所について、対応する係数ＣＸ，Ｙが前述の行列方程式で解かれる。
【００５６】
係数ＣＸ，ＹはシーケンスＳにおける唯一の位置ｋに対応する。いったん係数ＣＸ，Ｙが見つけられると、ｋは例えば公開鍵暗号解読法（Ｓｉｌｖｅｒ−Ｐｏｈｌｉｇ−Ｈｅｌｌｍａｎ）アルゴリズムによって計算される。公開鍵暗号解読法方式は、（Ｐ（ｘ）を法として）
が係数ＣＸ，Ｙを有する離散値対数ｋを発見する。
【００５７】
Ｐ（ｘ）の次数は２１６−１＝３＊５＊１７＊２５７であり、公開鍵暗号解読法アルゴリズムは、次数の最大素数（この場合はは２５７）が十分に小さく、ｋの高速決定が可能であるときにはつねに効率的である。
【００５８】
ｋから、球体の左上隅の（Ｘ，Ｙ）−座標が、ｗ＝１８７の列に関するラップ長で（ｗを法としてｋ除数ｗ，（ｋ ｄｉｖ ｗ））で示される。
【００５９】
別の実施形態では、マスクＢ’の形状は変化してよい。例えば、マスクＢ’は図３で破線により示されている三つの要素を組み込んでよい。要素の数ｍは他の三つの要素を除外することによって一定にされてよい、あるいはさらに多くの要素を組み込むことによって増加されてよい。これは、復号されたシンボルの値が不確定である場合には、役立つことがある。したがって、有効な変換行列Ｔが見つけられるまで、マスクＢ’の多様な形状が試されてよい。この場合、変換行列Ｔ、つまりその反形Ｔ−１は、検出装置／受信装置において動的に計算されてよい。有効な変換行列ＴはランクＮ＝ｎを有するものとして定義されてよい。したがって、行列方程式Ｂ’＝ＴＣが解かれ、場所が上記において定義されたように突き止められてよい。
【００６０】
以下の復号方法が使用されてよい。解釈されたシンボル値を確実性に従って並べ替える。つまり画像処理がその解釈について最も確実であるシンボルで開始する。次に、線形変換行列がランクｎを得るまでシンボル値を一個づつ加算し、位置について解く。隣接する要素の矩形または球体だけではなく、マスクの任意の形状が使用されてよいことに留意する。
【００６１】
さらに追加の実施形態では、有効な変換行列Ｔ’がランクＮ＝ｎ−ｊを有するものとして定義される。この場合、行列方程式Ｂ＝Ｔ’Ｃは、異なる位置（Ｘ、Ｙ）およびシーケンスＳにおける場所ｋに対応する最大２ｊの解を有することになる。言うまでもなく、一つの解だけが正しい解であり、偽の解は、覆っている（ｏｖｅｒｌｙｉｎｇ）経験則によって排除されてよい。例えば、偽の解は、１つ以上の先行のおよび／または後続の位置に関して連続性条件（例えば、空間距離、加速度等）をチェックすることによって排除されてよい。
【００６２】
マスクＢ’を変化させ、そして、有効な変換行列Ｔ’をランクＮ＝ｎ−ｊを有するものとして定義させることもできる。第一に、有効な変換行列Ｔ’が突き止められるまで、マスクＢ’の多様な形状が試されてよい。次に、多様な解のある行列方程式Ｂ’＝Ｔ’Ｃが解かれ、偽の解が排除されてよい。
【００６３】
本発明は、サンプリングされた観察済みのビットのエラー訂正を実行するためのツールをも提供する。Ｔｔ（Ｔ転置済み）の零空間は、ＨＴ＝０を達成する線形に独立した行でバイナリ行列Ｈを取得するための公知の技法によって評価できる。
【００６４】
本例では、Ｈは５ｘ２１行列であり、Ｈ＝［ｈ１ｈ２ｈ３．．．ｈ２１］は以下のとおりである。
【００６５】
このような行列Ｈは、Ｔにより生成される線形コードのエラー訂正コードとの関連においってチェックマトリックスとして知られている。我々のＨが、すべての列ｈｉが全ゼロベクトルと異なり、一意であるという特性を有することに留意する。パターンにおけるすべての考えられる観察されたマスクＢは係数ベクトルＣの何らかの選択のために、フォーマットＢ＝ＴＣであるため、ｉで誤りビットのひとつの見られたマスクは、Ｂ＊＝Ｂ＋ｅｉと書き込まれ、ｅｉはビット位置ｉの中で値一（１）を、および他のすべての位置で値ゼロ（０）を有する列ベクトルである。チェックマトリックスによる乗算は以下を生じさせる。
【００６６】
つまり、Ｈで見られたマスクを乗算し、エラーの場所を突き止めるために取得された文字列を調べることによって単一のエラーを突き止め、訂正することができる。誤りビットを反転すると正しい値が与えられ、ガウス消去法および例えば前述のように公開鍵暗号解読法アルゴリズムを用いて等、Ｔを介した後退代入を使用してＣについて解くことができる。
【００６７】
前記エラー訂正は、ランクＮ＝ｎ−ｊ（すなわちＨ’Ｔ’＝０）を有する変換行列Ｔ’と関連するチェックマトリックスＨ’で等しく適応できる。
【００６８】
ｖ個のビットが誤っているのを許すことを許容しうるであろうパターンを発見することを希望する場合は、任意の２ｖの列が線形に独立しているという特性のあるチェックマトリックスＨを見つける必要がある。これは線形符号の理論から周知である。
【００６９】
検出装置が、例えば文字と画像を形成するためにシンボルパターンのある表面上を動かされると、一連の復号動作または一発見動作が実行される。そこでは、各位置は前述のように、固定または可変マスクＢ、Ｂ’を用い、ランクＮ＝ｎまたはＮ＝ｎ−ｊを有する変換行列Ｔ、Ｔ’を用いて復号されてよい。復号方式も位置との間で変化してよい。
【００７０】
本発明は、当業者によって理解されるように、ソフトウェアとハードウェアの多様な組み合わせにより実現されてよい。本発明の範囲は以下の請求項によってのみ制限される。
【図面の簡単な説明】
【００７１】
【図１】シンボルパターンとして具体化されるラップされたシーケンスの例である。
【図２】線形フィードバックシフトレジスタの概略図である。
【図３】シンボルパターンの観察された部分集合を定義する例示的なマスクの概略図である。
【図４】本発明の実施形態によるペン形状をした検出装置の、部分的断面の概略側面図である。
【特許請求の範囲】
【請求項１】
シンボルパターンで観察され、サイズｍを有するシンボル値の任意の部分集合が一意であるという特性を有する二次元シンボルパターンＰＷを作成する際の方法であって、
各々Ｐ（ｘ）を法としてｘｋにおける単項式の係数Ｃの固定された線形組み合わせに対応するシンボル値Ｓｋの非反復シーケンスＳを定義し、ここでＰ（ｘ）がフィールドＦｑの度ｎの任意の多項式であることと、
定義された形状のマスクパターンを定義し、観察される前記ｍ個のシンボル値を備えるマスクベクトルＢを生じさせることと、
該シーケンスを前記二次元シンボルパターンＰＷの中に折り畳むためにラッピングスキームＷを定義することと、
を備え、
前記多項式Ｐ（ｘ）、前記マスクパターン、および前記ラッピングスキームＷが、該行列方程式Ｂ＝ＴＣを履行する変換行列ＴがＦｑを超えるランクＮ＝ｎを有するように定義される方法。
【請求項２】
前記ラッピングスキームが相対的な幾何学的な順序と、マスクパターンにおけるシンボル値と前記係数との間の関係性を維持するように定義される請求項１に記載のシンボルパターンを作成する際の方法。
【請求項３】
Ｓｋ＝Ｇ（ｆ（ｘ））であり、任意の多項式ｆ（ｘ）のためのＧ（ｆ（ｘ））がＰ（ｘ）を法としてｆ（ｘ）における単項式ｘｎ−１の係数である請求項１または２に記載のシンボルパターンを作成する際の方法。
【請求項４】
該変換行列Ｔが反復二乗によって計算される、請求項１から３のいずれか一項に記載のシンボルパターンを作成する際の方法。
【請求項５】
該ラッピングスキームＷが、行（または列）におけるシーケンスＳをラップ長ｗでラップすることから成る請求項１から４のいずれか一項に記載のシンボルパターンを作成する際の方法。
【請求項６】
該ラッピングスキームＷが該シーケンスＳを斜めにラッピングすることから成る請求項１から４のいずれか一項に記載のシンボルパターンを作成する際の方法。
【請求項７】
前記係数Ｃが、サイズｎを有し、ｘｎ−１から１のビットホルダー付きの線形フィードバックシフトレジスタＬＦＳＲの状態を表す請求項１から６のいずれか一項に記載のシンボルパターンを作成する際の方法。
【請求項８】
前記ラッピングスキームＷが、Ｌを法として［ｑ（Ｘ＋１，Ｙ）−ｑ（Ｘ，Ｙ）］およびＬを法として［ｑ（Ｘ，Ｙ＋１）−ｑ（Ｘ，Ｙ）］が該シンボルパターンＰＷ内の任意の位置（Ｘ，Ｙ）について一定であるように定義され、ｑ（Ｘ，Ｙ）＝ｋが該シンボルパターンＰＷにおける位置（Ｘ，Ｙ）と該シーケンスＳにおける場所ｋとの間の関係性であり、Ｌが該シーケンスＳの長さである請求項１から７のいずれか一項に記載のシンボルパターンを作成する際の方法。
【請求項９】
定義された形状および少なくともｍ個のシンボル値というサイズの任意のマスクＢが一意であるという特性を有する二次元シンボルパターンＰＷで観察されるマスクＢの位置（Ｘ，Ｙ）を突き止める方法であって、該シンボルパターンが、各々Ｐ（ｘ）を法としてｘｋにおける単項式の該係数Ｃの固定された線形組み合わせに対応するシンボル値Ｓｋの非反復シーケンスＳに基づいており、ここでＰ（ｘ）はフィールドＦｑにおける度ｎの任意の多項式であり、該シンボルパターンＰＷはラッピングスキームＷに従って前記シーケンスＳを折り畳むことによって形成され、
該マスクＢにおける該シンボル値と該対応する係数Ｃとの間の関係性についての情報を取り出すことと、
前記位置（Ｘ，Ｙ）で前記マスクＢの該シンボル値を抽出することと、
前記関係性によってＢＸ，Ｙから該対応する係数ＣＸ，Ｙを計算し、ここでＢＸ，Ｙが前記位置（Ｘ，Ｙ）でのＢという該抽出されたシンボル値であることと、
該シーケンスＳにおける該場所ｋを計算し、ここで該係数ＣがＣＸ，Ｙに等しいことと、
該場所ｋと該ラッピングスキームＷに基づいて該シンボルパターンＰＷにおける前記位置（Ｘ，Ｙ）を計算することと、
を備える方法。
【請求項１０】
前記関係性は該行列方程式Ｂ＝ＴＣを履行し、Ｆｑを超えるランクＮ＝ｎを有する変換行列Ｔである請求項９に記載の位置を突き止める方法。
【請求項１１】
前記関係性が該行列方程式Ｂ＝Ｔ’Ｃを履行し、Ｆｑを超えるランクＮ＝ｎ−ｊを有する変換行列であり、前記計算することが、
ＢＸ，Ｙ＝Ｔ’ＣＸ，Ｙの対応する係数ＣＸ，Ｙの複数の解を計算することと、
Ｃの係数がＣＸ，Ｙに等しい該シーケンスにおける複数の候補場所ｋを計算することと、
該場所ｋと該ラッピングスキームＷに基づいてシンボルパターンＰＷにおける複数の候補位置（Ｘ，Ｙ）を計算することと、
該求められていた位置の偽の候補位置を排除することと、
をさらに備える請求項９に記載の位置を突き止める方法。
【請求項１２】
該偽の候補位置が継続性条件をチェックすることにより排除される請求項１１に記載の位置を突き止める方法。
【請求項１３】
エラー訂正のために、該方程式ＨＴ＝０（またはＨ’Ｔ’＝０）を解くことによってチェックマトリックスＨ（またはＨ’）を形成することと、ＨＢＸ，Ｙ＝ｈｉ（またはＨ’ＢＸ，Ｙ＝ｈｉ）を形成することと、ｈｉ＝０の場合、ＢＸ，Ｙを維持するが、ｈｉ≠０の場合には、ＢＸ，Ｙの位置ｉで該シンボル値を変更することとをさらに備える請求項１０から１２のいずれか一項に記載の位置を突き止める方法。
【請求項１４】
該このようにして計算された候補変換行列Ｔ、Ｔ’がＦｑを超えるランクＮ＝ｎまたはｎ−ｊを有するまで該マスクＢの形状の集合の各々について候補変換行列Ｔ、Ｔ’を計算することと、ＢＸ，Ｙ＝ＴＣＸ，Ｙ（またはＢＸ，Ｙ＝Ｔ’ＣＸ，Ｙ）で該対応する係数ＣＸ，Ｙを計算する際に使用するための該このようにして計算された候補変換行列Ｔ、Ｔ’を選択することとをさらに備える請求項１０から１３のいずれか一項に記載の位置を突き止める方法。
【請求項１５】
該マスクＢにおけるシンボル値の数ｍは、形状の前記集合の中で連続的に増加する請求項１４に記載の位置を突き止める方法。
【請求項１６】
該ラッピングスキームＷが、ラップ長ｗの列内で該シーケンスＳを折り畳むことを含み、該位置（Ｘ，Ｙ）が（（ｗを法としてk除数w（ｋ ｄｉｖ ｗ））として計算される請求項９から１５のいずれか一項に記載の位置を突き止める方法。
【請求項１７】
該係数ＣがＣＸ，Ｙに等しい該シーケンスＳにおける該場所ｋが、（Ｐ（ｘ）を法として）ｒｋ≡ｘｋが係数ＣＸ，Ｙを有するｋの離散的対数を見つけるためのアルゴリズムで計算さえる請求項９から１６のいずれか一項に記載の位置を突き止める方法。
【請求項１８】
該マスクＢの多くの異なる位置について反復される請求項９から１７のいずれか一項に記載の方法。
【請求項１９】
該マスクの形状および前記関係性が維持、固定される請求項１８に記載の位置を突き止める方法。
【請求項２０】
各々が、Ｐ（ｘ）を法としてｘｋにおける単項式の係数Ｃの固定線形組み合わせＧに対応するシンボル値の非反復シーケンスＳ内のシンボル値Ｓｋを計算する方法であって、ここでＰ（ｘ）が該フィールドＦｑの度ｎの任意の多項式であり、
反復二乗によって
を計算することと、
Ｇ（ｒｋ）からシンボル値Ｓｋを引き出すことと、
を備える方法。
【請求項２１】
該二乗が再帰性関係ｘ２ｋ＝（ｘｋ）２およびｘ２ｋ＋１＝ｘ・ｘ２ｋを使用する請求項２０に記載のシンボル値を計算する方法。
【請求項２２】
定義された形状および少なくともｍ個のシンボル値というサイズの任意のマスクＢが一意であるという特性を有するシンボルパターンＰＷの細分ＢＰを計算する方法であって、該シンボルパターンが、各々Ｐ（ｘ）を法としてｘｋにおける単項式の係数の固定線形組み合わせに対応するシンボル値Ｓｋの非反復シーケンスＳに基づき、ここでＰ（ｘ）が該フィールドＦｑにおける度の任意の多項式であり、該シンボルパターンＰＷがラッピングスキームＷに従って前記シーケンスＳを折り畳むことによって形成され、前記細分ＢＰが該シンボルパターンＰＷにおける位置の集合を表し、
位置の前記集合を取り出すことと、
該ラッピングスキームＷに基づき、前記位置の内の少なくとも一つを該シーケンスＳにおける場所ｋに変換することと、
請求項２０または２１に記載の該方法で前記場所ｋの該シンボル値Ｓｋを計算することと、
を備える前記方法。
【請求項２３】
前記ラッピングスキームＷが、Ｌ＝ｄ１を法として［ｑ（Ｘ＋１，Ｙ）−ｑ（Ｘ，Ｙ）］およびＬ＝ｄ２を法として［ｑ（Ｘ，Ｙ＋１）−ｑ（Ｘ，Ｙ）］が該シンボルパターンＰＷにおける任意の位置（Ｘ，Ｙ）について一定であるように定義され、ｑ（Ｘ，Ｙ）＝ｋが該シンボルパターンＰＷと該シーケンスＳにおける場所ｋとの間の関係性であり、Ｌが該シーケンスの長さであり、
変位ベクトル（ｕ，ｖ）で前記少なくとも一つの位置から変位される少なくとも一つの別の位置について、ｘｐ・ｒｋを計算し、ｐが、前記変位ベクトル（ｕ，ｖ）を表すｄ１とｄ２の線形組み合わせであることと、
Ｇ（ｘｐ・ｒｋ）から少なくとも一つの別の位置のシンボル値を引き出すことと、
をさらに備える前記方法。
【請求項２４】
該パターンＰＷの該細分ＢＰが、印字される領域をカバーするように適応される請求項２２または２３に従って細分を計算する方法。
【請求項２５】
少なくともｍ個のシンボル値の定義された形状およびサイズが一意であるという特性を有する二次元シンボルパターンＰＷであって、
各々Ｐ（ｘ）を法としてｘｋにおける単項式の係数Ｃの固定線形組み合わせに対応し、ここでＰ（ｘ）が該フィールドＦｑの度ｎの任意の多項式であるシンボル値Ｓｋの非反復シーケンスＳと、
を備え、
該シーケンスＳがラッピングスキームＷに従って前記二次元シンボルパターンＰＷに折り畳まれ、
前記多項式（Ｐｘ）、前記マスクＢおよび前記ラッピングスキームＷが、該行列方程式Ｂ＝ＴＣを履行する変換行列がＦｑを超えるランクＮ＝ｎを有するように定義される。
【請求項２６】
前記ラッピングスキームＷが該マスクＢと前記係数Ｃにおけるシンボル値との間の相対的な幾何学的な順序と関係性を維持するために定義される請求項２５に記載のシンボルパターン。
【請求項２７】
Ｓｋ＝Ｇ（ｆ（ｘ））であり、任意の多項式ｆ（ｘ）のためのＧ（ｆ（ｘ））がＰ（ｘ）を法としてｆ（ｘ）における単項式ｘｎ−１の係数である、請求項２５または２６に記載のシンボルパターン。
【請求項２８】
該ラッピングスキームＷが、ラップ長ｗで行で（列で）ラッピングすることから成る請求項２５から２７のどれか１つに記載のシンボルパターン。
【請求項２９】
該ラッピングスキームＷが該シーケンスＳを斜めにラップすることから成る請求項２５から２７のいずれか一項に記載のシンボルパターン。
【請求項３０】
前記ラッピングスキームＷが、Ｌを法として［ｑ（Ｘ＋１，Ｙ）−ｑ（Ｘ，Ｙ）］およびＬを法として［ｑ（Ｘ，Ｙ＋１）−ｑ（Ｘ，Ｙ）］が任意の位置（Ｘ，Ｙ）について一定であるように定義され、ｑ（Ｘ，Ｙ）ｋが該シンボルパターンＰＷにおける位置（Ｘ，Ｙ）と該シーケンスＳ中の場所ｋとの間の関係性であり、Ｌが該シーケンスＳの長さである請求項２５から２９の任意のどれかに記載のシンボルパターン。
【請求項３１】
定義された形状と少なくともｍシンボル値のサイズの任意のマスクＢが一意であるという特性を有する二次元シンボルパターンＰＷの中で観察されるマスクＢの位置（Ｘ，Ｙ）を突き止めるためのシステムであって、該シンボルパターンが、各々Ｐ（ｘ）を法としてｘｋにおける該単項式の該係数Ｃの固定された線形組み合わせに対応するシンボル値Ｓｋの非反復シーケンスＳに基づいており、ここでＰ（ｘ）は該フィールドＦｑの度ｎの任意の多項式であり、該シンボルパターンＰＷがラッピングスキームＷに従って前記シーケンスＳを折り畳むことによって形成され、
Ｂにおけるシンボル価と対応する係数Ｃとの間の関係性についての情報を記憶するためのメモリ手段と、
前記位置（Ｘ，Ｙ）で前記マスクＢの該シンボル値を抽出し、
ＢＸ，Ｙが前記位置（Ｘ，Ｙ）での該抽出されたシンボル値Ｂである前記関係性によって対応する係数ＣＸ，ＹをＢＸ，Ｙから計算する
係数ＣがＣＸ，Ｙに等しいシーケンスＳにおける場所ｋを計算し、
該場所ｋと該ラッピングスキームＷに基づいて、該シンボルパターンＰＷにおける前記位置（Ｘ，Ｙ）を計算する
ように適応された計算手段と、
を備える前記システム。
【請求項３２】
前記関係性が該行列方程式Ｂ＝ＴＣを履行し、Ｆｑより大きいランクＮ＝ｎを有する変換行列Ｔである請求項３１に記載の位置を突き止めるためのシステム。
【請求項３３】
前記関係性が、行列方程式Ｂ＝Ｔ’Ｃを履行し、Ｆｑを超えるランクＮ＝ｎ−ｊを有する遷移行列Ｔ’あり、前記計算手段が、
ＢＸ，Ｙ＝Ｔ’ＣＸ，Ｙで、対応する係数ＣＸ，Ｙのための複数の解を計算する、
係数ＣがＣＸ，Ｙに等しい該シーケンスＳにおける複数の場所ｋを計算する、
場所ｋと該ラッピングスキームＷに基づいてシンボルパターンＰＷにおける候補位置（Ｘ，Ｙ）を計算する、および
該求められている位置の偽の候補位置を排除する
ように適応される該システム。
【請求項３４】
該計算手段が継続性条件をチェックすることにより偽の候補位置を排除するように適応される請求項３３に記載の位置を突き止めるためのシステム。
【請求項３５】
方程式ＨＴ＝０（またはＨ’Ｔ’＝０）を解くことによってチェックマトリックスＨ（
またはＨ’）を形成し、ＨＢＸ，Ｙ＝ｈｉ（またはＨＢＸ、Ｙ＝ｈｉ）を形成し、ｈｉ＝０の場合、ＢＸ，Ｙを維持するが、
の場合、ＢＸ，Ｙの位置ｉのシンボル値を変更するように適応されるエラー訂正手段をさらに備える請求項３２から３４のいずれか一項に記載の位置を突き止めるためのシステム。
【請求項３６】
該計算手段が、該このようにして計算された候補変換行列Ｔ、Ｔ’がＦｑを超えるランクＮ＝ｎまたはｎ−ｊを有するまで該マスクＢの形状の集合の各々について候補変換行列を計算し、該このようにして計算される変換行列Ｔ，Ｔ“を、該対応する係数ＣＸ，ＹをＢＸ，Ｙ＝ＴＣＸ，Ｙ（つまりＢＸ，Ｙ＝Ｔ’ＣＸ，Ｙ）で計算する際に使用するために選択するように適応される請求項３２から３５のいずれか一項に記載の位置を突き止めるためのシステム。
【請求項３７】
該計算手段が、形状の前記集合の中で、該マスクＢのシンボル値の数ｍを引き続いて増加するように適応される請求項３６に記載の位置を突き止めるためのシステム。
【請求項３８】
該マスクＢの多くの異なる位置について繰り返し動作される請求項３１から３７のいずれか一項に記載の位置を突き止めるためのシステム。
【請求項３９】
該計算手段が該マスクＢの形状および関係性を維持するように適応される請求項３８に記載の位置を突き止めるためのシステム。
【請求項４０】
該計算手段が、（Ｐ（ｘ）を法として）
がＣＸ，Ｙの係数を有するｋの離散的対数を検出するためのアルゴリズムで、該シーケンスＳにおける該場所ｋを計算するように適応され、該係数ＣがＣＸ，Ｙと等しい、請求項３１から３９のいずれか一項に記載の位置を突き止めるためのシステム。
【請求項４１】
コンピュータに請求項１から２４の内のいずれか一項に記載の方法を実行させるためのプログラム命令を備えるコンピュータプログラム製品。
【請求項１】
シンボルパターンで観察され、サイズｍを有するシンボル値の任意の部分集合が一意であるという特性を有する二次元シンボルパターンＰＷを作成する際の方法であって、
各々Ｐ（ｘ）を法としてｘｋにおける単項式の係数Ｃの固定された線形組み合わせに対応するシンボル値Ｓｋの非反復シーケンスＳを定義し、ここでＰ（ｘ）がフィールドＦｑの度ｎの任意の多項式であることと、
定義された形状のマスクパターンを定義し、観察される前記ｍ個のシンボル値を備えるマスクベクトルＢを生じさせることと、
該シーケンスを前記二次元シンボルパターンＰＷの中に折り畳むためにラッピングスキームＷを定義することと、
を備え、
前記多項式Ｐ（ｘ）、前記マスクパターン、および前記ラッピングスキームＷが、該行列方程式Ｂ＝ＴＣを履行する変換行列ＴがＦｑを超えるランクＮ＝ｎを有するように定義される方法。
【請求項２】
前記ラッピングスキームが相対的な幾何学的な順序と、マスクパターンにおけるシンボル値と前記係数との間の関係性を維持するように定義される請求項１に記載のシンボルパターンを作成する際の方法。
【請求項３】
Ｓｋ＝Ｇ（ｆ（ｘ））であり、任意の多項式ｆ（ｘ）のためのＧ（ｆ（ｘ））がＰ（ｘ）を法としてｆ（ｘ）における単項式ｘｎ−１の係数である請求項１または２に記載のシンボルパターンを作成する際の方法。
【請求項４】
該変換行列Ｔが反復二乗によって計算される、請求項１から３のいずれか一項に記載のシンボルパターンを作成する際の方法。
【請求項５】
該ラッピングスキームＷが、行（または列）におけるシーケンスＳをラップ長ｗでラップすることから成る請求項１から４のいずれか一項に記載のシンボルパターンを作成する際の方法。
【請求項６】
該ラッピングスキームＷが該シーケンスＳを斜めにラッピングすることから成る請求項１から４のいずれか一項に記載のシンボルパターンを作成する際の方法。
【請求項７】
前記係数Ｃが、サイズｎを有し、ｘｎ−１から１のビットホルダー付きの線形フィードバックシフトレジスタＬＦＳＲの状態を表す請求項１から６のいずれか一項に記載のシンボルパターンを作成する際の方法。
【請求項８】
前記ラッピングスキームＷが、Ｌを法として［ｑ（Ｘ＋１，Ｙ）−ｑ（Ｘ，Ｙ）］およびＬを法として［ｑ（Ｘ，Ｙ＋１）−ｑ（Ｘ，Ｙ）］が該シンボルパターンＰＷ内の任意の位置（Ｘ，Ｙ）について一定であるように定義され、ｑ（Ｘ，Ｙ）＝ｋが該シンボルパターンＰＷにおける位置（Ｘ，Ｙ）と該シーケンスＳにおける場所ｋとの間の関係性であり、Ｌが該シーケンスＳの長さである請求項１から７のいずれか一項に記載のシンボルパターンを作成する際の方法。
【請求項９】
定義された形状および少なくともｍ個のシンボル値というサイズの任意のマスクＢが一意であるという特性を有する二次元シンボルパターンＰＷで観察されるマスクＢの位置（Ｘ，Ｙ）を突き止める方法であって、該シンボルパターンが、各々Ｐ（ｘ）を法としてｘｋにおける単項式の該係数Ｃの固定された線形組み合わせに対応するシンボル値Ｓｋの非反復シーケンスＳに基づいており、ここでＰ（ｘ）はフィールドＦｑにおける度ｎの任意の多項式であり、該シンボルパターンＰＷはラッピングスキームＷに従って前記シーケンスＳを折り畳むことによって形成され、
該マスクＢにおける該シンボル値と該対応する係数Ｃとの間の関係性についての情報を取り出すことと、
前記位置（Ｘ，Ｙ）で前記マスクＢの該シンボル値を抽出することと、
前記関係性によってＢＸ，Ｙから該対応する係数ＣＸ，Ｙを計算し、ここでＢＸ，Ｙが前記位置（Ｘ，Ｙ）でのＢという該抽出されたシンボル値であることと、
該シーケンスＳにおける該場所ｋを計算し、ここで該係数ＣがＣＸ，Ｙに等しいことと、
該場所ｋと該ラッピングスキームＷに基づいて該シンボルパターンＰＷにおける前記位置（Ｘ，Ｙ）を計算することと、
を備える方法。
【請求項１０】
前記関係性は該行列方程式Ｂ＝ＴＣを履行し、Ｆｑを超えるランクＮ＝ｎを有する変換行列Ｔである請求項９に記載の位置を突き止める方法。
【請求項１１】
前記関係性が該行列方程式Ｂ＝Ｔ’Ｃを履行し、Ｆｑを超えるランクＮ＝ｎ−ｊを有する変換行列であり、前記計算することが、
ＢＸ，Ｙ＝Ｔ’ＣＸ，Ｙの対応する係数ＣＸ，Ｙの複数の解を計算することと、
Ｃの係数がＣＸ，Ｙに等しい該シーケンスにおける複数の候補場所ｋを計算することと、
該場所ｋと該ラッピングスキームＷに基づいてシンボルパターンＰＷにおける複数の候補位置（Ｘ，Ｙ）を計算することと、
該求められていた位置の偽の候補位置を排除することと、
をさらに備える請求項９に記載の位置を突き止める方法。
【請求項１２】
該偽の候補位置が継続性条件をチェックすることにより排除される請求項１１に記載の位置を突き止める方法。
【請求項１３】
エラー訂正のために、該方程式ＨＴ＝０（またはＨ’Ｔ’＝０）を解くことによってチェックマトリックスＨ（またはＨ’）を形成することと、ＨＢＸ，Ｙ＝ｈｉ（またはＨ’ＢＸ，Ｙ＝ｈｉ）を形成することと、ｈｉ＝０の場合、ＢＸ，Ｙを維持するが、ｈｉ≠０の場合には、ＢＸ，Ｙの位置ｉで該シンボル値を変更することとをさらに備える請求項１０から１２のいずれか一項に記載の位置を突き止める方法。
【請求項１４】
該このようにして計算された候補変換行列Ｔ、Ｔ’がＦｑを超えるランクＮ＝ｎまたはｎ−ｊを有するまで該マスクＢの形状の集合の各々について候補変換行列Ｔ、Ｔ’を計算することと、ＢＸ，Ｙ＝ＴＣＸ，Ｙ（またはＢＸ，Ｙ＝Ｔ’ＣＸ，Ｙ）で該対応する係数ＣＸ，Ｙを計算する際に使用するための該このようにして計算された候補変換行列Ｔ、Ｔ’を選択することとをさらに備える請求項１０から１３のいずれか一項に記載の位置を突き止める方法。
【請求項１５】
該マスクＢにおけるシンボル値の数ｍは、形状の前記集合の中で連続的に増加する請求項１４に記載の位置を突き止める方法。
【請求項１６】
該ラッピングスキームＷが、ラップ長ｗの列内で該シーケンスＳを折り畳むことを含み、該位置（Ｘ，Ｙ）が（（ｗを法としてk除数w（ｋ ｄｉｖ ｗ））として計算される請求項９から１５のいずれか一項に記載の位置を突き止める方法。
【請求項１７】
該係数ＣがＣＸ，Ｙに等しい該シーケンスＳにおける該場所ｋが、（Ｐ（ｘ）を法として）ｒｋ≡ｘｋが係数ＣＸ，Ｙを有するｋの離散的対数を見つけるためのアルゴリズムで計算さえる請求項９から１６のいずれか一項に記載の位置を突き止める方法。
【請求項１８】
該マスクＢの多くの異なる位置について反復される請求項９から１７のいずれか一項に記載の方法。
【請求項１９】
該マスクの形状および前記関係性が維持、固定される請求項１８に記載の位置を突き止める方法。
【請求項２０】
各々が、Ｐ（ｘ）を法としてｘｋにおける単項式の係数Ｃの固定線形組み合わせＧに対応するシンボル値の非反復シーケンスＳ内のシンボル値Ｓｋを計算する方法であって、ここでＰ（ｘ）が該フィールドＦｑの度ｎの任意の多項式であり、
反復二乗によって
を計算することと、
Ｇ（ｒｋ）からシンボル値Ｓｋを引き出すことと、
を備える方法。
【請求項２１】
該二乗が再帰性関係ｘ２ｋ＝（ｘｋ）２およびｘ２ｋ＋１＝ｘ・ｘ２ｋを使用する請求項２０に記載のシンボル値を計算する方法。
【請求項２２】
定義された形状および少なくともｍ個のシンボル値というサイズの任意のマスクＢが一意であるという特性を有するシンボルパターンＰＷの細分ＢＰを計算する方法であって、該シンボルパターンが、各々Ｐ（ｘ）を法としてｘｋにおける単項式の係数の固定線形組み合わせに対応するシンボル値Ｓｋの非反復シーケンスＳに基づき、ここでＰ（ｘ）が該フィールドＦｑにおける度の任意の多項式であり、該シンボルパターンＰＷがラッピングスキームＷに従って前記シーケンスＳを折り畳むことによって形成され、前記細分ＢＰが該シンボルパターンＰＷにおける位置の集合を表し、
位置の前記集合を取り出すことと、
該ラッピングスキームＷに基づき、前記位置の内の少なくとも一つを該シーケンスＳにおける場所ｋに変換することと、
請求項２０または２１に記載の該方法で前記場所ｋの該シンボル値Ｓｋを計算することと、
を備える前記方法。
【請求項２３】
前記ラッピングスキームＷが、Ｌ＝ｄ１を法として［ｑ（Ｘ＋１，Ｙ）−ｑ（Ｘ，Ｙ）］およびＬ＝ｄ２を法として［ｑ（Ｘ，Ｙ＋１）−ｑ（Ｘ，Ｙ）］が該シンボルパターンＰＷにおける任意の位置（Ｘ，Ｙ）について一定であるように定義され、ｑ（Ｘ，Ｙ）＝ｋが該シンボルパターンＰＷと該シーケンスＳにおける場所ｋとの間の関係性であり、Ｌが該シーケンスの長さであり、
変位ベクトル（ｕ，ｖ）で前記少なくとも一つの位置から変位される少なくとも一つの別の位置について、ｘｐ・ｒｋを計算し、ｐが、前記変位ベクトル（ｕ，ｖ）を表すｄ１とｄ２の線形組み合わせであることと、
Ｇ（ｘｐ・ｒｋ）から少なくとも一つの別の位置のシンボル値を引き出すことと、
をさらに備える前記方法。
【請求項２４】
該パターンＰＷの該細分ＢＰが、印字される領域をカバーするように適応される請求項２２または２３に従って細分を計算する方法。
【請求項２５】
少なくともｍ個のシンボル値の定義された形状およびサイズが一意であるという特性を有する二次元シンボルパターンＰＷであって、
各々Ｐ（ｘ）を法としてｘｋにおける単項式の係数Ｃの固定線形組み合わせに対応し、ここでＰ（ｘ）が該フィールドＦｑの度ｎの任意の多項式であるシンボル値Ｓｋの非反復シーケンスＳと、
を備え、
該シーケンスＳがラッピングスキームＷに従って前記二次元シンボルパターンＰＷに折り畳まれ、
前記多項式（Ｐｘ）、前記マスクＢおよび前記ラッピングスキームＷが、該行列方程式Ｂ＝ＴＣを履行する変換行列がＦｑを超えるランクＮ＝ｎを有するように定義される。
【請求項２６】
前記ラッピングスキームＷが該マスクＢと前記係数Ｃにおけるシンボル値との間の相対的な幾何学的な順序と関係性を維持するために定義される請求項２５に記載のシンボルパターン。
【請求項２７】
Ｓｋ＝Ｇ（ｆ（ｘ））であり、任意の多項式ｆ（ｘ）のためのＧ（ｆ（ｘ））がＰ（ｘ）を法としてｆ（ｘ）における単項式ｘｎ−１の係数である、請求項２５または２６に記載のシンボルパターン。
【請求項２８】
該ラッピングスキームＷが、ラップ長ｗで行で（列で）ラッピングすることから成る請求項２５から２７のどれか１つに記載のシンボルパターン。
【請求項２９】
該ラッピングスキームＷが該シーケンスＳを斜めにラップすることから成る請求項２５から２７のいずれか一項に記載のシンボルパターン。
【請求項３０】
前記ラッピングスキームＷが、Ｌを法として［ｑ（Ｘ＋１，Ｙ）−ｑ（Ｘ，Ｙ）］およびＬを法として［ｑ（Ｘ，Ｙ＋１）−ｑ（Ｘ，Ｙ）］が任意の位置（Ｘ，Ｙ）について一定であるように定義され、ｑ（Ｘ，Ｙ）ｋが該シンボルパターンＰＷにおける位置（Ｘ，Ｙ）と該シーケンスＳ中の場所ｋとの間の関係性であり、Ｌが該シーケンスＳの長さである請求項２５から２９の任意のどれかに記載のシンボルパターン。
【請求項３１】
定義された形状と少なくともｍシンボル値のサイズの任意のマスクＢが一意であるという特性を有する二次元シンボルパターンＰＷの中で観察されるマスクＢの位置（Ｘ，Ｙ）を突き止めるためのシステムであって、該シンボルパターンが、各々Ｐ（ｘ）を法としてｘｋにおける該単項式の該係数Ｃの固定された線形組み合わせに対応するシンボル値Ｓｋの非反復シーケンスＳに基づいており、ここでＰ（ｘ）は該フィールドＦｑの度ｎの任意の多項式であり、該シンボルパターンＰＷがラッピングスキームＷに従って前記シーケンスＳを折り畳むことによって形成され、
Ｂにおけるシンボル価と対応する係数Ｃとの間の関係性についての情報を記憶するためのメモリ手段と、
前記位置（Ｘ，Ｙ）で前記マスクＢの該シンボル値を抽出し、
ＢＸ，Ｙが前記位置（Ｘ，Ｙ）での該抽出されたシンボル値Ｂである前記関係性によって対応する係数ＣＸ，ＹをＢＸ，Ｙから計算する
係数ＣがＣＸ，Ｙに等しいシーケンスＳにおける場所ｋを計算し、
該場所ｋと該ラッピングスキームＷに基づいて、該シンボルパターンＰＷにおける前記位置（Ｘ，Ｙ）を計算する
ように適応された計算手段と、
を備える前記システム。
【請求項３２】
前記関係性が該行列方程式Ｂ＝ＴＣを履行し、Ｆｑより大きいランクＮ＝ｎを有する変換行列Ｔである請求項３１に記載の位置を突き止めるためのシステム。
【請求項３３】
前記関係性が、行列方程式Ｂ＝Ｔ’Ｃを履行し、Ｆｑを超えるランクＮ＝ｎ−ｊを有する遷移行列Ｔ’あり、前記計算手段が、
ＢＸ，Ｙ＝Ｔ’ＣＸ，Ｙで、対応する係数ＣＸ，Ｙのための複数の解を計算する、
係数ＣがＣＸ，Ｙに等しい該シーケンスＳにおける複数の場所ｋを計算する、
場所ｋと該ラッピングスキームＷに基づいてシンボルパターンＰＷにおける候補位置（Ｘ，Ｙ）を計算する、および
該求められている位置の偽の候補位置を排除する
ように適応される該システム。
【請求項３４】
該計算手段が継続性条件をチェックすることにより偽の候補位置を排除するように適応される請求項３３に記載の位置を突き止めるためのシステム。
【請求項３５】
方程式ＨＴ＝０（またはＨ’Ｔ’＝０）を解くことによってチェックマトリックスＨ（
またはＨ’）を形成し、ＨＢＸ，Ｙ＝ｈｉ（またはＨＢＸ、Ｙ＝ｈｉ）を形成し、ｈｉ＝０の場合、ＢＸ，Ｙを維持するが、
の場合、ＢＸ，Ｙの位置ｉのシンボル値を変更するように適応されるエラー訂正手段をさらに備える請求項３２から３４のいずれか一項に記載の位置を突き止めるためのシステム。
【請求項３６】
該計算手段が、該このようにして計算された候補変換行列Ｔ、Ｔ’がＦｑを超えるランクＮ＝ｎまたはｎ−ｊを有するまで該マスクＢの形状の集合の各々について候補変換行列を計算し、該このようにして計算される変換行列Ｔ，Ｔ“を、該対応する係数ＣＸ，ＹをＢＸ，Ｙ＝ＴＣＸ，Ｙ（つまりＢＸ，Ｙ＝Ｔ’ＣＸ，Ｙ）で計算する際に使用するために選択するように適応される請求項３２から３５のいずれか一項に記載の位置を突き止めるためのシステム。
【請求項３７】
該計算手段が、形状の前記集合の中で、該マスクＢのシンボル値の数ｍを引き続いて増加するように適応される請求項３６に記載の位置を突き止めるためのシステム。
【請求項３８】
該マスクＢの多くの異なる位置について繰り返し動作される請求項３１から３７のいずれか一項に記載の位置を突き止めるためのシステム。
【請求項３９】
該計算手段が該マスクＢの形状および関係性を維持するように適応される請求項３８に記載の位置を突き止めるためのシステム。
【請求項４０】
該計算手段が、（Ｐ（ｘ）を法として）
がＣＸ，Ｙの係数を有するｋの離散的対数を検出するためのアルゴリズムで、該シーケンスＳにおける該場所ｋを計算するように適応され、該係数ＣがＣＸ，Ｙと等しい、請求項３１から３９のいずれか一項に記載の位置を突き止めるためのシステム。
【請求項４１】
コンピュータに請求項１から２４の内のいずれか一項に記載の方法を実行させるためのプログラム命令を備えるコンピュータプログラム製品。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公表番号】特表２００８−５０８５７６（Ｐ２００８−５０８５７６Ａ）
【公表日】平成２０年３月２１日（２００８．３．２１）
【国際特許分類】
【出願番号】特願２００７−５２０２７１（Ｐ２００７−５２０２７１）
【出願日】平成１７年７月５日（２００５．７．５）
【国際出願番号】ＰＣＴ／ＳＥ２００５／００１１０８
【国際公開番号】ＷＯ２００６／００６９２２
【国際公開日】平成１８年１月１９日（２００６．１．１９）
【出願人】（５０６１４５３２６）アノト アクティエボラーク (49)
【Ｆターム（参考）】
【公表日】平成２０年３月２１日（２００８．３．２１）
【国際特許分類】
【出願日】平成１７年７月５日（２００５．７．５）
【国際出願番号】ＰＣＴ／ＳＥ２００５／００１１０８
【国際公開番号】ＷＯ２００６／００６９２２
【国際公開日】平成１８年１月１９日（２００６．１．１９）
【出願人】（５０６１４５３２６）アノト アクティエボラーク (49)
【Ｆターム（参考）】
[ Back to top ]