(57)【要約】少なくともｎ個のシンボルの系列５０に関する少なくとも１つのポイントのオフセットを、モジュロｎの下で決定する方法であって、その系列は、巡回位置符号の繰り返しコードワードから成り、その巡回位置符号は、長さがｎ、最小距離がｄｍｉｎであり、少なくとも１つのポイントに対応する位置において、ｗ≧ｎ−ｄｍｉｎ＋１という条件の下で、その系列５０から長さがｗシンボルの部分列５２を得るステップと、その部分列５２を、その部分列内にシンボル・エラー６０、６２があるときに、その部分列に最もマッチしそうな巡回位置符号のコードワード５８に写像するステップと、このようにして得られたそのコードワード５８の、その系列５０におけるオフセット５４を決定することによって、少なくとも１つのポイントのオフセットを決定するステップとを備える方法。【選択図】  図２
2004527045.tif 000002
【特許請求の範囲】
【請求項１】
少なくともｎ個のシンボルの第１の系列に関する少なくとも１つのポイントの第１のオフセットを、モジュロｎの下で決定する方法であり、
前記第１の系列は、第１の巡回位置符号の第１の繰り返しコードワードから成り、
前記第１の巡回位置符号は、長さがｎ、最小距離がｄｍｉｎである前記方法であって、
前記少なくとも１つのポイントに対応する位置において、ｗ≧ｎ−ｄｍｉｎ＋１という条件の下で、前記第１の系列から長さがｗシンボルの第１の部分列を得るステップと、
前記第１の部分列を前記第１の巡回位置符号のコードワードに写像するステップと、
このようにして得られた前記コードワードの前記第１の系列におけるオフセットを決定することによって、前記第１のオフセットを決定するステップと、
を備える方法。
【請求項２】
前記第１の部分列を写像する前記ステップは、前記第１の部分列にマッチする前記第１の巡回位置符号のコードワードを選択するステップを含む請求項１に記載の方法。
【請求項３】
前記第１の部分列を写像する前記ステップは、前記第１の部分列内に［（ｄｍｉｎ−１）／２］個までのシンボル・エラーがあるときに、前記第１の部分列に最もマッチしそうな前記第１の巡回位置符号のコードワードを選択するステップを含む請求項１に記載の方法。
【請求項４】
前記第１の部分列とコードワードとの間に如何なるマッチもないとき、エラーのフラグを立てる請求項１に記載の方法。
【請求項５】
前記第１の部分列を写像する前記ステップは、前記第１の部分列へのハミング距離が最も近い前記第１の巡回位置符号のコードワードを選択するステップを含む請求項１に記載の方法。
【請求項６】
前記ハミング距離は、前記第１の巡回位置符号のｗ個の座標で定義される請求項５に記載の方法。
【請求項７】
前記第１の系列は、第１の面上に配置、又は該第１の面中に形成された第１のパターンによって表され、
前記第１のパターンの少なくとも一部を検出又は検知することによって前記第１の部分列を得るステップを備える請求項１〜６の何れか一項に記載の方法。
【請求項８】
前記第１の系列の連続するシンボルは、実質的に線形状に配列された、前記第１のパターンの連続する部分によって表される請求項７に記載の方法。
【請求項９】
前記第１の巡回位置符号はシンプレックス符号である請求項１〜８の何れか一項に記載の方法。
【請求項１０】
前記第１の巡回位置符号が表３に記載されている符号、又は表３に記載されている符号の逆符号、補数若しくは逆符号の補数である請求項１〜９の何れか一項に記載の方法。
【請求項１１】
ｗがｗ≧ｎ−ｄｍｉｎ＋２を満たす請求項１〜１０の何れか一項に記載の方法。
【請求項１２】
ｗがｗ≧ｎを満たす請求項１〜１１の何れか一項に記載の方法。
【請求項１３】
少なくともｎ個のシンボルの第２の系列に関する少なくとも１つのポイントの第２のオフセットを、モジュロｎの下で決定するステップと、
前記少なくとも１つのポイントに対応する位置において、前記第２の系列から長さがｗシンボルの第２の部分列を得るステップと、
前記第２の部分列を前記第１の巡回位置符号のコードワードに写像するステップと、
このようにして得られた前記コードワードの前記第２の系列におけるオフセットを決定することによって、前記第２のオフセットを決定するステップと、を備え、
前記第２の系列は、前記第１の巡回位置符号の前記第１の繰り返しコードワードから成る請求項１〜１２の何れか一項に記載の方法。
【請求項１４】
前記第１のオフセットと前記第２のオフセットとの間の第１の差分を取り出すステップを備える請求項１３に記載の方法。
【請求項１５】
前記第２の系列は、前記第１の面上に配置、又は該第１の面中に形成された第２のパターンによって表され、
前記第２のパターンの少なくとも一部を検出又は検知することによって前記第２の部分列を得るステップを備える請求項１４に記載の方法。
【請求項１６】
少なくともｎ個のシンボルの複数の付加的系列のそれぞれに関する少なくとも１つのポイントの複数の付加的オフセットを、モジュロｎの下で決定するステップと、
前記少なくとも１つのポイントに対応する位置において、前記各付加的系列から長さがｗシンボルの付加的部分列を得るステップと、
前記付加的部分列を、それぞれの前記第１の巡回位置符号のコードワードに写像するステップと、
このようにして得られた前記各コードワードの対応する前記付加的系列におけるオフセットを決定することによって、前記付加的オフセットを決定するステップと、を備え、
前記各付加的系列は、前記第１の巡回位置符号の前記第１の繰り返しコードワードから成る請求項１３に記載の方法。
【請求項１７】
前記付加的オフセットの対間の付加的差分を複数取り出すステップを備える請求項１６に記載の方法。
【請求項１８】
前記各付加的系列は、前記第１の面上に配置、又は該第１の面中に形成された複数の付加的パターンのうちの１つによって表され、
対応する前記付加的パターンの少なくとも一部を検出又は検知することによって、対応する前記付加的部分列を得るステップを備える請求項１７に記載の方法。
【請求項１９】
少なくともｗ個の相異なる系列のそれぞれにおけるｗ個のシンボルを検出又は検知するステップを備える請求項１８に記載の方法。
【請求項２０】
複数の第１の系列に関する少なくとも１つのポイントの第１の座標値を決定する方法であり、
前記各第１の系列は、第１の巡回位置符号の第１の繰り返しコードワードから成り、
前記第１の巡回位置符号は、長さがｎ１、最小距離がｄｍｉｎ１である前記方法であって、
前記少なくとも１つのポイントに対応する位置において、ｈ１≧２およびｗ１≧ｎ１−ｄｍｉｎ１＋１という条件の下で、ｈ１個の前記各第１の系列から長さがｗ１シンボルの第１の部分列を得るステップと、
前記第１の部分列を、それぞれの前記第１の巡回位置符号のコードワードに写像するステップと、
このようにして得られた前記各コードワードの対応する前記第１の系列におけるオフセットを決定することによって、それぞれの前記少なくとも１つのポイントの第１のオフセットを決定するステップと、
前記第１の系列のｈ１−１個の対それぞれについて、対応する対をなす２つの前記第１のオフセット間の差分を取り出すことによって、第１の差分を取り出すステップと、
複数の前記第１の差分から、前記第１の座標値を取り出すステップと、
を備える方法。
【請求項２１】
前記第１の差分の少なくとも１つを前記第１の座標値のディジットとして解釈するステップを備える請求項２０に記載の方法。
【請求項２２】
前記第１の差分の少なくとも１つを、隣接する座標値から前記第１の座標値を分離するマーカーとして解釈するステップを備える請求項２０又は２１に記載の方法。
【請求項２３】
ｗ１がｗ１≧ｎ１−ｄｍｉｎ１＋２を満たす請求項２０〜２２の何れか一項に記載の方法。
【請求項２４】
ｗ１がｗ１≧ｎ１を満たす請求項２０〜２２の何れか一項に記載の方法。
【請求項２５】
前記第１の巡回位置符号はシンプレックス符号である請求項２０に記載の方法。
【請求項２６】
前記第１の巡回位置符号が表３に記載されている符号、又は表３に記載されている符号の逆符号、補数若しくは逆符号の補数である
請求項２０に記載の方法。
【請求項２７】
複数の第２の系列に関する前記少なくとも１つのポイントの第２の座標値を決定するステップを備え、
前記各第２の系列は、第２の巡回位置符号の第２の繰り返しコードワードから成り、
前記第２の巡回位置符号は、長さがｎ２、最小距離がｄｍｉｎ２であり、
前記少なくとも１つのポイントに対応する位置において、ｈ２≧２およびｗ２≧ｎ２−ｄｍｉｎ２＋１という条件の下で、ｈ２個の前記各第２の系列から長さがｗ２シンボルの第２の部分列を得るステップと、
前記第２の部分列を、それぞれの前記第２の巡回位置符号のコードワードに写像するステップと、
このようにして得られた前記各コードワードの対応する前記第２の系列における１つのオフセットを決定することによって、それぞれの前記少なくとも１つのポイントの第２のオフセットを決定するステップと、
複数の前記第２のオフセットから前記第２の座標値を取り出すステップと、を備える請求項２０に記載の方法。
【請求項２８】
前記第２のオフセットの少なくとも１つを前記第２の座標値のディジットとして解釈するステップを備える請求項２７に記載の方法。
【請求項２９】
前記第２のオフセットの少なくとも１つを、隣接する座標値から前記第２の座標値を分離するマーカーとして解釈するステップを備える請求項２７又は２８に記載の方法。
【請求項３０】
前記第２の系列のｈ２−１個の対それぞれについて、対応する対をなす２つの前記第２のオフセット間の差分を取り出すことによって、第２の差分を取り出すステップと、
複数の前記第２の差分から、前記第２の座標値を取り出すステップを備える請求項２７に記載の方法。
【請求項３１】
ｗ２がｗ２≧ｎ２−ｄｍｉｎ２＋２を満たす請求項２７〜３０の何れか一項に記載の方法。
【請求項３２】
ｗ２がｗ２≧ｎ２を満たす請求項２７〜３０の何れか一項に記載の方法。
【請求項３３】
前記各第１の系列は、第１の面上に配置、又は該第１の面中に形成された複数の第１のパターンのうちの１つによって表され、
対応する前記第１のパターンの少なくとも一部を検出又は検知することによって、対応する前記第１の部分列を得るステップを備える請求項２７に記載の方法。
【請求項３４】
前記各第１の系列の連続するシンボルは、実質的に線形状に配列された、対応する前記第１のパターンの連続する部分によって表され、
前記第１のパターンは、互いに実質的に平行に、且つ互いに間隔を置いて配列される請求項３３に記載の方法。
【請求項３５】
前記各第２の系列は、前記第１の面上に配置、又は該第１の面中に形成された複数の第２のパターンのうちの１つによって表され、
対応する前記第２のパターンの少なくとも一部を検出又は検知することによって、対応する前記第２の部分列を得るステップを備える請求項３３又は３４に記載の方法。
【請求項３６】
前記各第２の系列の連続するシンボルは、実質的に線形状に配列された、対応する前記第２のパターンの連続する部分によって表わされ、
前記第２のパターンは、互いに実質的に平行に、且つ互いに間隔を置いて配列され、
前記第１のパターンと前記第２のパターンとが互いに実質的に直交するように配列されている請求項３５に記載の方法。
【請求項３７】
前記第１の座標値と前記第２の座標値の両者によって２次元座標が定められる請求項２７に記載の方法。
【請求項３８】
前記第２の巡回位置符号はシンプレックス符号である請求項２７に記載の方法。
【請求項３９】
前記第２の巡回位置符号が表３に記載されている符号、又は表３に記載されている符号の逆符号、補数若しくは逆符号の補数である請求項２０に記載の方法。
【請求項４０】
ｎ１とｎ２の値が等しい請求項２７に記載の方法。
【請求項４１】
ｎ１とｎ２の値が等しくない請求項２７に記載の方法。
【請求項４２】
前記第１の巡回位置符号と前記第２の巡回位置符号とが等しい請求項２７に記載の方法。
【請求項４３】
前記第１の巡回位置符号と前記第２の巡回位置符号とが等しくない請求項２７に記載の方法。
【請求項４４】
少なくともｎ個のシンボルの第１の系列に関する少なくとも１つのポイントの第１のオフセットを決定する方法であり、
前記第１の系列は、第１の巡回位置符号の第１の繰り返しコードワードから成り、
前記第１の巡回位置符号は、長さがｎである前記方法であって、
図面を参照して本明細書に実質的に記載されている方法。
【発明の詳細な説明】
【発明の分野】
【０００１】
本発明は、誤りを検出し、誤りを訂正する巡回位置符号、および面上の位置符号化時におけるそれらの符号の使用に関する。
【０００２】
（同時係属中の特許出願）
本発明に関連する各種の方法、システムおよび装置は、本発明の出願人または譲受人が２０００年１１月２７日出願した同時係属中の以下の特許出願に開示されている。
ＰＣＴ／ＡＵ００／０１４４２，ＰＣＴ／ＡＵ００／０１４４４，ＰＣＴ／ＡＵ００／０１４４６，ＰＣＴ／ＡＵ００／０１４４５，ＰＣＴ／ＡＵ００／０１４５０，ＰＣＴ／ＡＵ００／０１４５３，ＰＣＴ／ＡＵ００／０１４４８，ＰＣＴ／ＡＵ００／０１４４７，ＰＣＴ／ＡＵ００／０１４５９，ＰＣＴ／ＡＵ００／０１４５１，ＰＣＴ／ＡＵ００／０１４５４，ＰＣＴ／ＡＵ００／０１４５２，ＰＣＴ／ＡＵ００／０１４４３，ＰＣＴ／ＡＵ００／０１４５５，ＰＣＴ／ＡＵ００／０１４５６，ＰＣＴ／ＡＵ００／０１４５７，ＰＣＴ／ＡＵ００／０１４５８，及びＰＣＴ／ＡＵ００／０１４４９。
これらの同時出願中の特許出願の開示内容は、参考として本明細書に組み込まれている。
【０００３】
本発明に関連する各種の方法、システムおよび装置は、本発明の出願人または譲受人が２０００年１０月２０日出願した同時係属中の以下の特許出願に開示されている。
ＰＣＴ／ＡＵ００／０１２７３，ＰＣＴ／ＡＵ００／０１２７９，ＰＣＴ／ＡＵ００／０１２８８，ＰＣＴ／ＡＵ００／０１２８２，ＰＣＴ／ＡＵ００／０１２７６，ＰＣＴ／ＡＵ００／０１２８０，ＰＣＴ／ＡＵ００／０１２７４，ＰＣＴ／ＡＵ００／０１２８９，ＰＣＴ／ＡＵ００／０１２７５，ＰＣＴ／ＡＵ００／０１２７７，ＰＣＴ／ＡＵ００／０１２８６，ＰＣＴ／ＡＵ００／０１２８１，ＰＣＴ／ＡＵ００／０１２７８，ＰＣＴ／ＡＵ００／０１２８７，ＰＣＴ／ＡＵ００／０１２８５，ＰＣＴ／ＡＵ００／０１２８４，及びＰＣＴ／ＡＵ００／０１２８３。
これらの同時出願中の特許出願の開示内容は、参考として本明細書に組み込まれている。
【０００４】
本発明に関連する各種の方法、システムおよび装置は、本発明の出願人または譲受人が２０００年９月１５日出願した同時係属中の以下の特許出願に開示されている。ＰＣＴ／ＡＵ００／０１１０８、ＰＣＴ／ＡＵ００／０１１１０、及びＰＣＴ／ＡＵ００／０１１１１。これらの同時出願中の特許出願の開示内容は、参考として本明細書に組み込まれている。
【０００５】
本発明に関連する各種の方法、システムおよび装置は、本発明の出願人または譲受人が２０００年６月３０日出願した同時係属中の以下の特許出願に開示されている。
ＰＣＴ／ＡＵ００／００７６２，ＰＣＴ／ＡＵ００／００７６３，ＰＣＴ／ＡＵ００／００７６１，ＰＣＴ／ＡＵ００／００７６０，ＰＣＴ／ＡＵ００／００７５９，ＰＣＴ／ＡＵ００／００７５８，ＰＣＴ／ＡＵ００／００７６４，ＰＣＴ／ＡＵ００／００７６５，ＰＣＴ／ＡＵ００／００７６６，ＰＣＴ／ＡＵ００／００７６７，ＰＣＴ／ＡＵ００／００７６８，ＰＣＴ／ＡＵ００／００７７３，ＰＣＴ／ＡＵ００／００７７４，ＰＣＴ／ＡＵ００／００７７５，ＰＣＴ／ＡＵ００／００７７６，ＰＣＴ／ＡＵ００／００７７７，ＰＣＴ／ＡＵ００／００７７０，ＰＣＴ／ＡＵ００／００７６９，ＰＣＴ／ＡＵ００／００７７１，ＰＣＴ／ＡＵ００／００７７２，ＰＣＴ／ＡＵ００／００７５４，ＰＣＴ／ＡＵ００／００７５５，ＰＣＴ／ＡＵ００／００７５６，及びＰＣＴ／ＡＵ００／００７５７。
これらの同時出願中の特許出願の開示内容は、参考として本明細書に組み込まれている。
【０００６】
本発明に関連する各種の方法、システムおよび装置は、本発明の出願人または譲受人が２０００年５月２４日出願した同時係属中の以下の特許出願に開示されている。
ＰＣＴ／ＡＵ００／００５１８，ＰＣＴ／ＡＵ００／００５１９，ＰＣＴ／ＡＵ００／００５２０，ＰＣＴ／ＡＵ００／００５２１，ＰＣＴ／ＡＵ００／００５２２，  ＰＣＴ／ＡＵ００／００５２３，ＰＣＴ／ＡＵ００／００５２４，ＰＣＴ／ＡＵ００／００５２５，ＰＣＴ／ＡＵ００／００５２６，ＰＣＴ／ＡＵ００／００５２７，ＰＣＴ／ＡＵ００／００５２８，ＰＣＴ／ＡＵ００／００５２９，ＰＣＴ／ＡＵ００／００５３０，ＰＣＴ／ＡＵ００／００５３１，ＰＣＴ／ＡＵ００／００５３２，ＰＣＴ／ＡＵ００／００５３３，ＰＣＴ／ＡＵ００／００５３４，ＰＣＴ／ＡＵ００／００５３５，ＰＣＴ／ＡＵ００／００５３６，ＰＣＴ／ＡＵ００／００５３７，ＰＣＴ／ＡＵ００／００５３８，ＰＣＴ／ＡＵ００／００５３９，ＰＣＴ／ＡＵ００／００５４０，ＰＣＴ／ＡＵ００／００５４１，ＰＣＴ／ＡＵ００／００５４２，ＰＣＴ／ＡＵ００／００５４３，ＰＣＴ／ＡＵ００／００５４４，  ＰＣＴ／ＡＵ００／００５４５，ＰＣＴ／ＡＵ００／００５４７，ＰＣＴ／ＡＵ００／００５４６，ＰＣＴ／ＡＵ００／００５５４，ＰＣＴ／ＡＵ００／００５５６，ＰＣＴ／ＡＵ００／００５５７，ＰＣＴ／ＡＵ００／００５５８，ＰＣＴ／ＡＵ００／００５５９，ＰＣＴ／ＡＵ００／００５６０，ＰＣＴ／ＡＵ００／００５６１，ＰＣＴ／ＡＵ００／００５６２，ＰＣＴ／ＡＵ００／００５６３，ＰＣＴ／ＡＵ００／００５６４，ＰＣＴ／ＡＵ００／００５６５，ＰＣＴ／ＡＵ００／００５６６，ＰＣＴ／ＡＵ００／００５６７，ＰＣＴ／ＡＵ００／００５６８，ＰＣＴ／ＡＵ００／００５６９，ＰＣＴ／ＡＵ００／００５７０，ＰＣＴ／ＡＵ００／００５７１，ＰＣＴ／ＡＵ００／００５７２，ＰＣＴ／ＡＵ００／００５７３，ＰＣＴ／ＡＵ００／００５７４，ＰＣＴ／ＡＵ００／００５７５，ＰＣＴ／ＡＵ００／００５７６，ＰＣＴ／ＡＵ００／００５７７，ＰＣＴ／ＡＵ００／００５７８，  ＰＣＴ／ＡＵ００／００５７９，ＰＣＴ／ＡＵ００／００５８１，ＰＣＴ／ＡＵ００／００５８０，ＰＣＴ／ＡＵ００／００５８２，ＰＣＴ／ＡＵ００／００５８７，ＰＣＴ／ＡＵ００／００５８８，ＰＣＴ／ＡＵ００／００５８９，ＰＣＴ／ＡＵ００／００５８３，ＰＣＴ／ＡＵ００／００５９３，ＰＣＴ／ＡＵ００／００５９０，ＰＣＴ／ＡＵ００／００５９１，ＰＣＴ／ＡＵ００／００５９２，ＰＣＴ／ＡＵ００／００５９４，ＰＣＴ／ＡＵ００／００５９５，ＰＣＴ／ＡＵ００／００５９６，ＰＣＴ／ＡＵ００／００５９７，ＰＣＴ／ＡＵ００／００５９８，ＰＣＴ／ＡＵ００／００５１６，ＰＣＴ／ＡＵ００／００５１７，及びＰＣＴ／ＡＵ００／００５１１。
これらの同時出願中の特許出願の開示内容は、参考として本明細書に組み込まれている。
【背景技術】
【０００７】
コンピュータ・システムに関連するプリントされたドキュメントにある程度の「対話性」を加える各種の仕組みが提案されてきた。これらの仕組みは、そのドキュメント中に、世界共通のリソース・ロケータを符号化するプリント用バーコードを含み、それによりプリントされた「ハイパーリンク」を作動させる。プリントされたドキュメントの対話性をよりシームレスにし、手書き入力等のより高度な機能をサポートするために、人間の目では事実上見ることができない、位置又は機能を示すデータによって、文書の表面を符号化することが提案されてきた。ドキュメントには通常、ユーザの目に見えるデータが含まれ、ユーザは、目に見えない符号化データを現実に検出し復号化する検出装置を用いることにより、この目に見えるデータとみかけ上対話する。
【０００８】
符号化されたデータが離散的なタグの形式であり、各タグが、他の離散的なタグとは別に、データを符号化するものであってもよい。離散的なタグのデータを復号化するためには、先ず、離散的なタグを識別するとともに、検出装置に対するそのタグのオリエンテーション（定位）を決定する必要がある。したがって、通常、各タグの全体サイズに加えられるターゲット構造がタグ中に含まれることが必要とされる。ターゲット構造は、各タグの実効的な全体サイズを小さくするために、隣接するタグ間で共有してもよい。離散的なタグの１つの欠点は、検出装置がその視野中に少なくとも一つの完全なタグを有する必要があることである。本出願人による同時係属中の国際特許出願ＰＣＴ／ＷＯ００／７２２４９号において論じられているように、検出装置を表面に対して傾斜させなければならない可能性があることに関連して、検出装置の視野はタグサイズよりもかなり大きい必要がある。
【０００９】
自己登録式パターンを使用することにより明示ターゲットを使用しなくてよい各種仕組みが提案されてきた。自己登録式パターンを使用するとき、検出装置に対するパターンのオリエンテーションの決定及びパターン内のデータの配列構造の決定等、通常は明示ターゲットによってサポートされる動作を、データパターンそれ自体によって暗黙的にサポートすることができる。
【００１０】
自己登録式パターンは、その最も簡単な形式として、長方形状又は他の標準的な格子状のグリフからなる。各グリフは、近接するグリフと区別できるように、それらのグリフから空間的に独立している。これによって、第１レベルの登録が行われる。すると、オリエントされた（場合によっては視覚的に歪んだ）長方形の格子を識別できるように、グリフによって定義されたポイントを通るように格子線をフィッティングすることができる。これにより、第２のレベルの登録が行われ、格子に関連するグリフを抽出することが可能になる。自己登録式パターンは、ターゲット・パターンを含まなければならない。該ターゲット・パターンが一度位置決めされると、グリフ格子のオリエンテーション及びトランスレーション（移行）を決定することができる。これにより、第３及び最終レベルの登録が行われて、グリフ・データがデータ・パケットに組み立てられて、該データを解釈することができる。いわゆるＭ系列は、最大の長さ及び巡回的な特性をもつために、各種の自己登録式の位置符号化パターンのベースとして提案されてきた。
【００１１】
面上の位置を符号化するパターンを検出して続いて復号化するときには、例えば、表面の破損又は汚れに起因するエラーが起こりやすい。自己登録式パターンが、エラーの検出及び／又は訂正を直接サポートすることはない。
【発明の概要】
【００１２】
ｑ進の巡回（ｎ，ｋ）符号Ｃのコードワードを任意の回数だけ繰り返すことにより、任意の長さの系列を形成することができる。このとき、その系列へのサイズｎのウィンドウによって、Ｃのコードワードが生成されることが保証されている。その符号が丁度ｎ個のコードワードを含むように設計されるならば、符号の「次元」は、ｋ＝ｌｏｇｑｎである。ｎ個のコードワード全てが唯一の同一サイクルに属するようにその符号が設計されるならば、そのウィンドウは、ｎ個の連続する位置においてｎ個の異なるコードワードを生成する。系列（モジュロｎ）内の位置とコードワードとの間には直接的な対応関係があるので、各々のコードワードをｎ個の（相対）位置の１つに一意に写像することができる。このような符号を巡回位置符号と呼ぶことにする。最小距離がｄｍｉｎとなるように符号が設計されるとき、ｄｍｉｎ−１個までの如何なる個数のエラーも検出でき、また［（ｄｍｉｎ−１）／２］個までの如何なる個数のエラーも訂正できる。
【００１３】
したがって、本発明によって、１つの広い形式において、次の方法が提供される。この方法は、少なくともｎ個のシンボルの第１の系列に関する少なくとも１つのポイントの第１のオフセットを、モジュロｎの下で決定する方法であり、第１の系列は、第１の巡回位置符号の第１の繰り返しコードワードから成り、第１の巡回位置符号は、長さがｎ、最小距離がｄｍｉｎである前記方法であって、少なくとも１つのポイントに対応する位置において、ｗ≧ｎ−ｄｍｉｎ＋１という条件の下で、第１の系列から長さがｗシンボルの第１の部分列を得るステップと、第１の部分列を第１の巡回位置符号のコードワードに写像するステップと、このようにして得られたコードワードの第１の系列におけるオフセットを決定することによって、第１のオフセットを決定するステップと、を備える。
【００１４】
第１の部分列を写像するステップは、第１の部分列にマッチする第１の巡回位置符号のコードワードを選択するステップを含むことが好適である。第１の部分列とコードワードとの間に如何なるマッチもないとき、エラーのフラグを立てることとしてもよい。
【００１５】
または、第１の部分列を写像するステップは、第１の部分列内に［（ｄｍｉｎ−１）／２］個までのシンボル・エラーがあるときに、第１の部分列に最もマッチしそうな第１の巡回位置符号のコードワードを選択するステップを含む。第１の部分列を写像するステップは、第１の部分列へのハミング距離が最も近い第１の巡回位置符号のコードワードを選択するステップを含むこととしてもよい。ハミング距離は、第１の巡回位置符号のｗ個の座標で定義されることが好適である。
【００１６】
第１の系列は、第１の面上に配置、又は該第１の面中に形成された第１のパターンによって表され、第１のパターンの少なくとも一部を検出又は検知することによって第１の部分列を得るステップを備えることが好適である。第１の系列の連続するシンボルは、実質的に線形状に配列された、第１のパターンの連続する部分によって表されることが好適である。
【００１７】
最低限のエラー訂正を可能にするためには、ｗがｗ≧ｎ−ｄｍｉｎ＋２を満たすことが好ましい。より程度の高いエラー訂正を可能にするためには、ｗがｗ≧ｎを満たすことが好ましい。
【００１８】
この方法には、付加的な系列から付加的な部分列を得ることによって、付加的なオフセットを得るステップが含まれてもよい。この方法には、隣接する系列の対から得られるオフセットの間の差分を取り出すステップがさらに含まれてもよい。
【００１９】
また、本発明によって、別の広い形式において、次の方法が提供される。その方法は、複数の第１の系列に関する少なくとも１つのポイントの第１の座標値を決定する方法であり、各第１の系列は、第１の巡回位置符号の第１の繰り返しコードワードから成り、
第１の巡回位置符号は、長さがｎ１、最小距離がｄｍｉｎ１である前記方法であって、少なくとも１つのポイントに対応する位置において、ｈ１≧２およびｗ１≧ｎ１−ｄｍｉｎ１＋１という条件の下で、ｈ１個の各第１の系列から長さがｗ１シンボルの第１の部分列を得るステップと、第１の部分列を、それぞれの第１の巡回位置符号のコードワードに写像するステップと、このようにして得られた各コードワードの対応する第１の系列におけるオフセットを決定することによって、それぞれの少なくとも１つのポイントの第１のオフセットを決定するステップと、第１の系列のｈ１−１個の対それぞれについて、対応する対をなす２つの第１のオフセット間の差分を取り出すことによって、第１の差分を取り出すステップと、複数の第１の差分から、第１の座標値を取り出すステップと、を備える。
【００２０】
第１の差分の少なくとも１つを第１の座標値のディジットとして解釈するステップを備えることが好ましい。また、第１の差分の少なくとも１つを、隣接する座標値から第１の座標値を分離するマーカーとして解釈するステップを備えることが好ましい。
【００２１】
また、この差分符号化方法を使用して、明示的な位置及びコードワードの両方を符号化することができ、このとき、そのコードワードはエラー検出に使用される。例えば、そのコードワードを、１ビットの差分それぞれを使用して符号化することができる。また、そのようなコードワードは、巡回的であれば、位置データの登録を決定するために使用することもでき、その場合には明示的なマーカー差分は必要なくなる。一般的に、巡回位置符号は、他のデータに対する登録信号を提供するために、そのデータに組み込む（又はそのデータと共存させる）ことができる。
【００２２】
１座標あたりに１つ又は複数の列（及び／又は、行）をロケーションを特定するデータとして保存できる。
【００２３】
この方法は、複数の第２の系列に関する少なくとも１つのポイントの第２の座標値を決定するステップを備え、各第２の系列は、第２の巡回位置符号の第２の繰り返しコードワードから成り、
第２の巡回位置符号は、長さがｎ２、最小距離がｄｍｉｎ２であり、少なくとも１つのポイントに対応する位置において、ｈ２≧２およびｗ２≧ｎ２−ｄｍｉｎ２＋１という条件の下で、ｈ２個の各第２の系列から長さがｗ２シンボルの第２の部分列を得るステップと、第２の部分列を、それぞれの第２の巡回位置符号のコードワードに写像するステップと、このようにして得られた各コードワードの対応する第２の系列における１つのオフセットを決定することによって、それぞれの少なくとも１つのポイントの第２のオフセットを決定するステップと、複数の第２のオフセットから第２の座標値を取り出すステップと、を備えることが好ましい。
【００２４】
第２のオフセットの少なくとも１つを第２の座標値のディジットとして解釈するステップを備えることが好ましい。または、この方法は、第２の系列のｈ２−１個の対それぞれについて、対応する対をなす２つの第２のオフセット間の差分を取り出すことによって、第２の差分を取り出すステップと、複数の第２の差分から、第２の座標値を取り出すステップを備える。
【００２５】
各第１の系列は、第１の面上に配置、又は該第１の面中に形成された複数の第１のパターンのうちの１つによって表され、対応する第１のパターンの少なくとも一部を検出又は検知することによって、対応する第１の部分列を得るステップを備えることが好適である。
【００２６】
各第１の系列の連続するシンボルは、実質的に線形状に配列された、対応する第１のパターンの連続する部分によって表され、第１のパターンは、互いに実質的に平行に、且つ互いに間隔を置いて配列されることが好適である。
【００２７】
第１の座標及び第２の座標によって、直交する座標、例えば、デカルト座標系におけるｘ座標及びｙ座標が定義されてもよい。直交する座標を符号化するために使用される第１及び第２の巡回位置符号は、それらの長さが互いに同じであっても異なっていてもよい。また、その符号が同じであっても異なっていてもよい。
【００２８】
表３には、様々な長さをもつ、最適な２進（ｑ＝２）の巡回位置符号が示されている。表３に記載されている符号の逆符号（reverse）、補数（complement）及び逆符号の補数（reverse complement）も同様に最適である。他の多くの巡回位置符号もまた本発明に適用することができる。多くの最適な符号は、シンプレックス符号である。
【００２９】
本発明は、図を参照して以下で行われる、本発明の好ましい実施形態の限定されない説明によってより理解されよう。
【好適な実施形態と他の実施形態の説明】
【００３０】
本発明の実施形態では、面上の位置及び機能に関する情報を符号化するときに、主に自己登録式パターンの形式で巡回位置符号が利用されている。
【００３１】
（Ｍ系列を使用する位置符号化）
長さｋの線形フィードバック・シフトレジスタ（ＬＦＳＲ）は、第０段から第ｋ−１段までのｋ個の段から成っている。各段は、１ビットである。各クロックにおいて、第０段の内容は、出力系列における次のビットを形成する。第ｉ段の内容は、第ｉ‐１段に移動する。また、第ｋ−１段の新しい内容は、モジュロ２の下で複数の段の固定部分集合における前の内容の和をとることによって計算されたフィードバック・ビットである（Menezes, A. J., P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, 1997, CRC Press 参照）。最長のＬＦＳＲは、いわゆるＭ系列を出力として生成する。Ｍ系列は、長さが２ｋ−１であり、その１つの周期において、非零値として考え得る全てのレジスタ値が１回現れる。Ｍ系列においては各ｋビット値がちょうど１回ずつ現れるので、既知のＭ系列へのｋビットウィンドウは、Ｍ系列内における固有の位置として次々に解釈することができる固有のｋビット部分列を生成する。Ｍ系列の周期性に起因して、循環Ｍ系列へのｋビットウィンドウは、局所的に固有の位置、すなわちＭ系列の長さｎのモジュロを生成する。繰返し又は循環Ｍ系列は、擬似雑音（ＰＮ）系列としても知られている。ＰＮ系列の特徴及び構造は、（Golomb, S. W., Shift Register Sequences, Aegean Park Press, 1982）において広範に渡って論じられている。その内容は、参照として本明細書に組み込まれている。
【００３２】
''Pseudo-Random Sequence and Arrays''(Proceedings of the IEEE, Vol. 64, No. 12, December 1976, その内容は参照として本明細書に組み込まれている）の中で、F. J. Mac Williams 及び N. J. A. Sloane が述べているように、Ｍ系列を二次元配列に収めることにより、Ｍ系列のこのウィンドウ特性を二次元に拡張することができる。Ｍ系列の長さは、ｎ１＝２ｋ１−１とｎ２＝ｎ／ｎ１とが互いに素であって且つそれらが共に１より大であるように、ｎ＝２ｋ１ｋ２−１という形式でなければならない。ｎ１×ｎ２ビットの出力配列は、配列の主対角線にＭ系列を書き、エッジに達するたびに反対側から続けることによって満たされる。
【００３３】
国際特許出願ＰＣＴ／ＷＯ９２／１７８５９（J. Burns and S. Lloyd）の中に記載されているように、循環Ｍ系列をコラムに配列し、第２のＭ系列を隣接するコラムの垂直方向の相対配列構造に符号化することによっても、上述のウィンドウ特性を二次元に拡張することができる。コラムのシフトは循環的に行われ、配列全体として長方形の形状が維持される。２つの系列の長さがそれぞれ２ｋ１−１、２ｋ２−１であるとすると、（２ｋ１−１）×２ｋ２ビットの配列へのｋ１×（ｋ２＋１）のウィンドウは、固有のｋ１×（ｋ２＋１）部分配列を生成する。部分配列におけるｋ１ビットのコラムのそれぞれは、相対的なｋ１ビットの位置を生成し、複数のコラムの各対は、ｋ２ビットの合計について１ビットの差分を生成し、それにより更にｋ２ビットの水平位置を生成する。水平位置がいったん分かると、水平位置に関連する垂直シフト累積量を第１の列の垂直相対位置に加えることにより垂直絶対位置を生成することができる。
【００３４】
１ビットよりむしろｋ１ビットを一対の列それぞれの垂直方向の相対配列構造に符号化することによって、すなわち、垂直Ｍ系列の長さが許容する最大の相対シフト量を利用することによって、符号化するアレイの位置の密度を水平方向にｋ１×ｋ２に拡大できる。そして、ｋ１ビットの差分値は、ｋ１進のＭ系列の１つの要素を表す。
【００３５】
両次元においてｋ１×ｋ２ビットを回復するために、水平次元に使用される差分符号化の手法を垂直次元にも利用できる。すなわち、循環Ｍ系列を行に配列し、Ｍ系列を隣接する行の相対配列構造に符号化することによって行う。Ｍ系列の列と行は、既知の方法で空間的にインターリーブされ復号化が可能となる。Ｍ系列は、列（または、行）内で何度でも循環することができ、全体として充分なサイズパターンを形成する。
【００３６】
米国特許第6,208,771（D. A. Jared et al)）に記述されているように、互いに平行に置かれたＭ系列を使用して、直交座標を符号化することができる。それぞれのＭ系列は、偶数番号の行を連続的に左側へ２ビットオフセットさせ、奇数番号の行を連続的に右側へ２ビットオフセットさせることにより、１行おきに繰り返えされる。その結果、偶数番号の行は、４５°の定座標の線を定義し、奇数番号の行は―４５°の定座標の線を定義する。すなわち、これらの行は、互いに９０°をなす。したがって、それらの交点それぞれが２次元の位置を定める。これらの角度は、Ｍ系列を多数回繰り返しオフセットすることによって生じるので、この手法は非常に効率が悪い。
【００３７】
純粋のＭ系列手法においては、より高い位置精度が要求されるほど、与えられる部分列（又はサブアレイ）を位置に変換する費用が高価になるのが１つの欠点である。
【００３８】
国際特許出願ＰＣＴ／ＷＯ００／７３８８７（P. Ericsson）に記述されているように、差分符号化手法を、座標を直接符号化するのに使用できる。すなわち、１組の循環Ｍ系列の列の垂直方向の相対配列構造によって、１つの水平位置座標の隣接する部分を符号化することができ、また、１組の循環Ｍ系列の行の水平方向の相対配列構造によって、１つの垂直位置座標の隣接する部分を符号化することができる。したがって、純粋のＭ系列手法とは異なり、マーカ値（又は範囲）を使用して、どの列（又は行）によって１つのの座標の最下位桁部分を次の座標の最上位桁部分から切り離すのかを示さなければなければならない。最適な差分符号化手法として、差分符号化手法を使用してただ１つの座標のみが符号化され、他方の座標は直接符号化される。これが可能なのは、差分符号化された座標を復号化すると、それらの相対配列構造どころか、直交座標を符号化する循環Ｍ系列の絶対配列構造が判るからである。上述の手法では、空間的に一致するビットを対にするとともに、ビット対がとり得る４つの値のうちの１つを表すことのできる単一のグリフによって各ビット対を表すことによって、直交する２つのＭ系列を結合する。
【００３９】
国際特許出願ＰＣＴ／ＷＯ９２／１７８５９（J. Burns and S. Lloyd）に記述されているように、いわゆるオリエンテーションできる（向き付け可能な）Ｍ系列を様々な方法で利用して、サブ・アレイのオリエンテーションを正しく決定することが確実にできる。オリエンテーションできるＭ系列は、その系列が特定の部分列を含んでいるのならば、その部分列の逆行列は含まないように構成される。ウィンドウのサイズがｋ×ｋであることを要求されるアレイをイメージするとき、イメージセンサに対するアレイのオリエンテーションに制約がなければ、少なくともｋ√２の直径の視野が必要とされる。
【００４０】
（エラーの検出及び訂正）
符号化されるべきデータが、ガロア域ＧＦ（ｑ）から取り出されたｑ進シンボルを有するｋシンボル・ブロックに分解されていると仮定する。すべての可能なｋ組：ｍ＝（ｍ０，ｍ１，…，ｍｋ−１）の集まりは、ｑｋの可能なベクトルを含むＧＦ（ｑ）上にベクトル空間を形成する。長さｎの対応するブロック・エラー符号Ｃは、Ｍ個のｎ−シンボル・コードワード｛ｃ０，ｃ１・・・，ｃＭ−１｝からなる。ここで、Ｍ＝ｑｋ、ｎ＞ｋであり、各々のコードワードの形式は、ｃ＝（ｃ０，ｃ１,…，ｃｎ−１）である。符号化されるべきデータブロックがあるとすれば、符号器は、そのデータブロックをＣ内の１つのコードワードに写像する。ＧＦ（ｑ）の上のすべての可能なｎ組の集まりは、ｑｎ個のベクトルを含むが、コードワードはＭ＝ｑｋ個なので、その符号には冗長性がある。上記を対数的に言い表せば、γ＝ｎ−１ｏｇｑＭ＝ｎ−ｋ、または、符号レートＲ＝ｋ／ｎとなる。コードＣがベクトルサブ空間をＧＦ（ｑ）の上に形成するならば、すなわち、符号Ｃがスカラによる加法および乗法の下で閉じられているならば、その符号Ｃは線形符号である（したがって、ゼロ・ベクトルを含んでいる）。そして、その符号は、次元ｋを有するといわれ、（ｎ，ｋ）符号として参照される。
【００４１】
２つのコードワードの間のハミング距離は、その２つのコードワードの間の異なっているシンボルの数である。ブロック符号の最小距離ｄｍｉｎは、符号内のすべてのコードワード対における最小のハミング距離である。最大距離ｄｍａｘは、符号内のすべてのコードワード対における最大のハミング距離である。
【００４２】
エラー・パターンによって、コードワードにシンボル・エラーを導入する。それはその重み、すなわち、損なわれた（不正の）シンボルの数によって特徴付けられる。エラー・パターンが検出されないためには、コードワードが別のコードワードに見えるようにしなければならない。このようにして、ｄｍｉｎの最小距離を有する符号によって、重みがｄｍｉｎ−１以下の全てのエラー・パターンを検出することができる。したがって、与えられた符号は、より重みのある多くのエラー・パターンを検出することができるけれども、符号がすべてのエラー・パターンを検出することができる重みの限界を与える。
【００４３】
あるエラー・パターンによって損なわれたであろうコードワードが抽出されたとすると、復号器は、そのコードワードが元々書かれたコードワードと異なる確率を最小にするように、抽出されたワードをＣ内のコードワードに写像する。そして、次にそのコードワードをデータ・ブロックに写像する。特性についてより詳細に指定されなければ、比較的重みの小さいのエラー・パターンは比較的重みの大きいエラー・パターンより高い確率で生じ、重みが等しい全てのエラーパターンは同じ確率で生じると推測される。。したがって、記述されたコードワードのうち最大確率のものは、抽出ワードに最も近いハミング距離をもつコードワードである。抽出されたワードが、正しい（正しく記述された）コードワードよりも不正確なコードワードに近い距離にあるならば、復号器の処理にはエラーがある。それらのコードワードは定義で少なくとも距離ｄｍｉｎ離れているので、復号器のエラーは、エラー・パターンの重みがｄｍｉｎ／２以上の場合のみ起こり得る。その結果、最大確率法による復号器によって、[（ｄｍｉｎ−１）／２]以下のエラー・パターンすべてを訂正できる。同様に、その復号器は、２ｔ＜ｄｍｉｎの条件下でｔ個のエラーを訂正できる。
【００４４】
線形符号の最小距離は、Singletonの限界式：ｄｍｉｎ≦ｎ−ｋ＋１によって制限される。Singletonの限界式を満足する符号は、分離可能な最大距離（ＭＤＳ）と呼ばれる。Reed−Solomon符号（Wicker, S. B. and V. K. Bhargava, eds., Reed-Solomon Codes and Their Applications, IEEE Press, 1994 を参照のこと。その内容は、参考として本明細書に組み込まれている。）は、最も一般的に使用されているＭＤＳ符号である。いかなる２進符号もＭＤＳではない。
【００４５】
消去箇所は、損なわれたと仮定している抽出されたワードのシンボルである。コードワード内におけるその位置は既知なので、復号化という目的からみたとき、エラーとして扱うのではなく、むしろ無視できるものとして扱う。例えば、抽出されたワード内の消去されたシンボルとコードワード内の対応するシンボルとの間の距離は、最大確率法による復号化を行うためのベースとして使用されるハミング距離には含まれない。したがって、消去箇所それぞれは、１つずつ有効に最小距離を減少させる。すなわち、ｆ個の消去箇所があるとき、[（ｄｍｉｎ−ｆ−１）／２]個までのエラーを訂正することができる。同様に、復号器は、２ｔ＋ｆ＜ｄｍｉｎの条件下でｔ個のエラーとｆ個の消去箇所を訂正することができる。ＭＤＳ符号については、上記条件は、２ｔ＋ｆ＜ｎ−ｋ＋１となる。
【００４６】
符号のコードワードそれぞれが、固定ロケーションにおいて対応するデータ・ブロックを変更なしに含んでいるのであれば、その符号は系統的である。そのとき、その符号のデータ（又は、メッセージ）の座標とその符号の冗長（又は、パリティ）座標とを区別することが可能である。
【００４７】
パンクチャド符号を作成して、すなわち、１つ又は複数の冗長座標を削除することによって線形符号のレートを増加させることができる。ｇ座標の削除によって、（ｎ，ｋ）符号は、（ｎ−ｇ，ｋ）符号に変換される。パンクチャド符号の最小距離は、ｄｍｉｎ−ｇである。明らかに、ｄｍｉｎ−ｇ＜２であれば、パンクチャリングによって、符号は、１つのエラーすら訂正できなくなる。また、ｄｍｉｎ−ｇ＜１であれば、パンクチャリングによって、符号は、１つのエラーすら検出できなくなる。同様に、パンクチャド符号の長さ：ｗ＝ｎ−ｇは、エラー検出のためにはｗ≧ｎ−ｄｍｉｎ＋１の条件を、また、エラー訂正のためには、ｗ≧ｎ−ｄｍｉｎ＋２の条件を満たさなければならない。パンクチャド符号用の復号器は、削除した座標を元の符号に関する消去箇所として取り扱う。
【００４８】
あらゆるコードワードｃ＝（ｃ０，ｃ１，…，ｃｎ−２，ｃｎ−１）∈Ｃについて、コードワード  ｃ’＝（ｃｎ−１，ｃ０，ｃ１，…，ｃｎ−２）∈Ｃがあれば、すなわちｃ’がｃの右循環シフトであれば、ブロック符号Ｃは巡回符号である。また、ｃのｎ循環シフトすべてがＣ内のコードワードであるということになる。コードワードｑｋの数が符号ｎの長さを超えるならば、その符号は、いくつかの相異なるサイクルを含み、各々のサイクルｉは、ｓｉ個の固有のコードワードを含む。ここで、ｎは、ｓｉで割り切れる。その符号がゼロ・ベクトルを含んでいるならば、ゼロ・ベクトルは独自のサイクルを形成する。
【００４９】
（巡回位置符号）
ｋシンボル・ウィンドウを通して長さｎ＝２ｋ−１の循環Ｍ系列へ位置復号化を行うことによっては、エラー検出または訂正ができない。しかしながら、ｎシンボル・ウィンドウを通して長さｎの循環巡回コードワード（recurring cyclic codeword）へ位置復号化を行うことによっては、エラー検出または訂正ができる。
【００５０】
巡回（ｎ，ｋ）符号Ｃのコードワードにおける任意の繰り返し数を連結して任意の長さの系列を形成することができる。その時、その系列へのサイズｎのウィンドウによって、Ｃのコードワードが生成されることが保証されている。その符号が丁度ｎ個のコードワードを含むように設計されるならば、そのとき、符号の次元は、定義によりｋ＝ｌｏｇｑｎである。すべてのｎ個のコードワードがただ１つの同じサイクルに属するように、その符号が設計されるならば、そのウィンドウは、ｎ個の異なるコードワードをｎ個の連続する位置に生成する。あるコードワードと系列（モジュロｎ）内のある位置との間には直接的な対応関係があるので、各々のコードワードをｎ個の（相対）位置の１つに一意に写像することができる。重要なのは、[（ｄｍｉｎ−１）／２]個までのシンボル・エラーがあるときでも位置を決定することができるということである。このような符号を巡回位置符号と呼ぶことにする。巡回位置符号のいかなるコードワードもそのような符号を定義する。ゼロ・ベクトルが含まれていないので、巡回位置符号は線形コードではない。しかしながら、以下の議論と特徴づけにおいては、線形コードの用語法を使用するのが便宜である。多くの望ましい巡回位置符号は、ゼロ・ベクトルが取り除かれた線形符号である。
【００５１】
ここで、以下のことに留意すべきである。長さ２ｋ−１の２進のＭ系列の循環シフトは、長さｎ＝２ｋ−１、次元ｋ、および最小距離ｄｍｉｎ＝２ｋ−１の線形巡回符号のノンゼロコードワードすべてを構成する（F. J. Mac William and N. J. A. Sloane, ‘‘Pseudo-Random Sequences and Arrays'', Proceedings of the IEEE, Vol. 64, No. 12, December 1976 を参照のこと）。したがって、２進のＭ系列は、巡回位置符号を定義する。しかしながら、ここで、以下のことにもまた留意すべきである。前述したＭ系列ベースの位置符号化の仕組みにおいては、ウィンドウ・サイズｎよりもウィンドウ・サイズｋを使用しているので、Ｍ系列をコードワードとして使用していないことである。
【００５２】
より一般的には、Ｍ系列は、１組のシンプレックス符号の部分集合を定義する。シンプレックス符号は、長さがｎ＝４ｍ−１、最小距離がｄｍｉｎ＝（ｎ＋１）／２＝２ｍである。名前が示唆するように、シンプレックス符号のコードワードは、ｎシンプレックスの等距離にある頂点を定義する。したがって、シンプレックス符号の最小距離及び最大距離は同じである。ｎ素数については、平方剰余を用いて巡回的なシンプレックス符号を構成するために、Paley構造を使用することができる（Mac Williams, F. J. and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977, and Wicker, S. B., Error Control Systems for Digital Communication and Storage, Prentice Hall, 1995を参照のこと。これらの内容は、参考として本明細書に組み込まれている）。そのとき、ｎが素数又はｎ＝２ｋ−１の場合は、シンプレックス符号は循環的であり、したがって巡回位置符号を定義する。
【００５３】
長さｎ＝４ｍ−１の巡回的なシンプレックス符号は、その長さに対してだけではなくｎ＜４（ｍ＋１）−１なるいかなる長さｎに対しても最大の最小距離を有しているという意味で、最適の巡回位置符号を定義する。
【００５４】
符号の長さがシンボル・サイズの整数乗でない限り、巡回位置符号の「次元」は分数である。巡回位置符号のコードワードすべてが、ｋ’＝[ｌｏｇｑｎ]シンボルにおいて互いに異なっているならば、その巡回位置符号は「系統的」と一般的に考えられている。Ｍ系列は系統的な巡回位置符号を定義するが、一方で、巡回的なシンプレックス符号は系統的な巡回位置符号を定義しないのが一般的である。
【００５５】
パンクチャド巡回位置符号が生成されると、１つまたは複数のシンボルが符号のコードワードそれぞれから系統的に削除される。しかしながら、パンクチャド巡回位置符号は巡回的でないので、パンクチャド位置復号化のベースとなる任意の長さの符号系列を構成するために、引き続き元のコードワードが使用される。パンクチャド符号の長さがｎ−ｇであれば、元のコードから長さｎの循環巡回コードワードへの位置復号化に、（ｎ−ｇ）シンボル・ウィンドウが使用される。
【００５６】
（巡回位置符号の例）
表１は、例として、２進の７ビット巡回位置符号のコードワードを７個示す。この符号は巡回的なシンプレックス符号であり、系統的である。その符号では、最小（及び最大）距離が４であり、それゆえ訂正されるべき１つのエラーが認められる。
【表１】
2004527045.tif 000003
【００５７】
表２は、その符号の第１のコードワードとその符号の他のコードワードとの間のハミング距離を示し、その際、コードワードにおいて７つのロケーションが可能であり、その７つのロケーションにおいて１ビットのエラーを伴って逐次計算されている。各々の場合において、損なわれた（すなわち、逆の）ビットは、◆で示されている。損なわれたコードワードと損なわれていない元のコードワードとの間の距離は各々の場合において丁度１であるが、損なわれたコードワードと他のコードワードの各々との間の距離は必ず３以上である。（定義による）符号は単一のサイクルを含むだけなので、表２は、いかなるコードワードであれ、すべての１ビット・エラーを訂正できる能力をその符号がもつことを示している。
【表２】
2004527045.tif 000004
【００５８】
図１は系列５０を示し、該系列は、複数回繰り返される７ビットの２進巡回位置符号の第１のコードワードから構成されている。また、図１は、８つの隣接する７ビットの該系列へのウィンドウ５２を示している。それぞれのウィンドウによって、その符号のコードワードが生成され、その結果表１に従い、シフト値５４が生成される。図２は、２つの１ビット・エラー６０，６２があるときの、図１と同じ系列５０を示す。したがって、８個の７ビット・ウィンドウ５２のうちの７個に、１ビット・エラーが含まれている。これらのエラーは、表２において例証されるように訂正可能であり、対応する有効なコードワード５８が生成され、その結果、元のシフト値５４が生成される。
【００５９】
（最適な巡回位置符号）
妥当な符号長さとシンボル・サイズを得るために、徹底的な検索によって、特定の長さとシンボル・サイズの最適な巡回位置符号を見出すことができる。表３は、様々な長さの最適な２進の巡回位置符号の特性を、特定の例と併せて記載している。多くの場合、最適な符号は系統的であるが、長さ１１と１２の符号については、系統的ではない符号が最適である。ここで、長さ７と１５（一般的に長さｎ＝２ｋ−１）の最適符号は、前述のようにＭ系列で定義される。
【表３】
2004527045.tif 000005
ａ．系統的ではない
【００６０】
符号化の目的からは、１つの符号は、その符号の逆符号、その補数、およびその逆符号の補数と等価であると考えられる。したがって、各々の場合、これらのうち１つだけが表中に含まれている。
【００６１】
表には、系統的な巡回位置符号を（ほとんど）記載しているが、７を超える符号長さについては、多くの最適のより系統的ではない最適（反復記号によって示されている）符号がある。
【００６２】
特定のパンクチャド巡回位置符号を形成して、その長さを減少させ、それによりその位置符号化の精度（及び対応するウィンドウ・サイズ）を減少させることができる。表３は、パンクチャド符号が巡回的なシンプレックス符号であるとき、パンクチャド符号が同じ長さのいかなる他の符号よりも優位であることを示している。その理由は、表中の巡回的なシンプレックス符号それぞれが、表中においてその先行符号よりも２だけ大きい最小距離を有しているからである。
【００６３】
例えば、表中の長さ１９の最適（巡回的なシンプレックス）符号は、長さ１８までパンクチャされているとき、表中にある長さ１８の４つの最適符号よりも優位である。長さ１８の最適符号は、最小距離８，および最小逆距離６をそれぞれ有するが、長さ１９のパンクチャド符号は優位にある最小距離９と最小逆距離７を有する。
【００６４】
表４の第１の列は、表３の長さ１９の最適符号コードワード１９個を示す。表４の第２列は、長さ１９の符号をパンクチャすることによって得た、長さ１８の最適符号のコードワード１９個を示している。
【表４】
2004527045.tif 000006
【００６５】
系統的ではない特定の符号に有利となるであろう１つの設計目標は、コードワードにおけるセット・ビットの数を最大にすることにある。これは、画一的なグリフの有無を使用して各々のビットを表すならば適切なものである。その理由は、グリフ・アレイ全体の構造を識別する我々の能力を最大にすることができるからである。
【００６６】
長さｎの巡回位置符号は、ｎ個のコードワードのみを含んでいるので、妥当な符号長さについては、抽出されたワードと各々のコードワードとの間のハミング距離を順番に計算し、その後最も近いコードワードを選択することによって、抽出されたワードを復号化するのは容易である。非常に短い符号については、参照用テーブルを使用することも可能である。より長い符号については、代数的な復号化を使用することができる（Wicker, S. B., Error control Systems for Digital Communication and Storage, Prentice Hall, 1995, and Berlekamp, E. R., Algebraic Coding Theory, Aegean Park Press, 1984 を参照のこと。これらの内容は、参考として本明細書に組み込まれている）。抽出されたワードが２つまたはそれ以上のコードワードから等距離にあるとすると、復号化によってエラーを報告することが好ましい。同様に、直接に（例えば、参照することによって）又は代数学的に符号化を実行することができる。
【００６７】
ｑｎ個の可能なすべてのコードワードを順番に発生させるとともに、各コードワードについて、ｎ個の循環シフトを含む符号を定義することによって、長さｎ、シンボル・サイズｑの最適な巡回位置符号の検索を進めることができる。そのとき、符号の最小距離および最小逆距離が計算される。その符号がそれまでに見いだされた中でベストのものならば、その符号は記録される。すべての最適な符号を２つのパスにおいて見出すことができる。すなわち、最適符号の特性を決定する第１のパスと最適特性を示す符号を数え上げる第２のパスの２つである。
【００６８】
最適巡回位置符号が巡回的なシンプレックス符号ならば、対応する構成技法を使用することができる。すなわち、ｎが素数の場合にはPaley構成方法を、ｎ＝２ｋ−１の場合にはＬＦＳＲ構成方法を用いることができる。ここで留意すべきことは、あるｋ（例えば５）に対しては、長さｎ＝２ｋ−１（例えば３１）が素数となり、Ｐａｌｅｙ構成方法を使用できるということである。
【００６９】
（Ｑ進の巡回位置符号）
ｑ個の相異なるシンボルを１つのコードワードに連結することによって、長さｎ＝ｑのｑ進の巡回位置符号を構成することができる。その符号の最小（及び最大）距離は、その長さに等しく、すなわちｄｍｉｎ＝ｄｍａｘ＝ｎである。例として、表５は、７シンボルで７進の巡回位置符号のコードワードを７個示している。これらの符号の最小距離は７である。ｎ＝ｑ＝２ｍ−１のとき、その巡回位置符号は、ゼロ・ベクトルが取り除かれた（ｎ，１）リード−ソロモン符号（Reed-Solomon code）と等価である。例えば、表５中の符号は、（７，１）のリード−ソロモン符号に対応している。ｑ進の巡回位置符号はゼロ・シンボルを含むことがあるが、ゼロ・シンボルはゼロ・ベクトルに現れるだけであるので、（ｎ，１）リード−ソロモン符号のノン・ゼロ・コードワードがゼロ・シンボルを含むことはない。また、リード−ソロモン符号は、通常、異なるシンボル配列を有する。
【表５】
2004527045.tif 000007
【００７０】
長さがｎ＝ｑでｑ進のパンクチャド巡回位置符号によって、任意の長さｎｐ＜ｑ  のｑ進の巡回位置符号を得ることができる。パンクチャド長さの値にかかわらず、ｄｍｉｎ＝ｎｐとなる。
【００７１】
長さがｎ＞ｑでｑ進の位置符号を、リード−ソロモン符号のようなｑ進の巡回符号の１サイクル（ただし、ｋ＞１）から設計或いは引き出すことができる。ｎ＞ｑのとき、ｄｍｉｎ＜ｎである。リード−ソロモン符号などのＭＤＳ符号に対しては、例えば、ｄｍｉｎ＝ｎ−ｋ＋１である。
【００７２】
（巡回位置符号を用いた差分符号化法）
上述の様々なＭ系列ベースの位置符号化方法は、エラー検出及びエラー訂正を助けるためにｋ個以上のシンボルを抽出しなければならないが、繰り返しＭ系列よりもむしろ巡回位置符号からの循環コードワードを使用することにより実現できる。
【００７３】
例として、図３は、隣接する７ビット符号の系列の７通りの配列７０を示す。これらは、差分符号化のための基本的な要素を提供している。垂直位置における差分７２が、列の対それぞれの下に示されている。
【００７４】
図４は、底６の差分として連続する２つの水平座標のディジットを符号化するために列に配列された７ビット符号の、１４個の隣接する系列１００を示す。それらの座標は、符号１０２，１０４にそれぞれ示されているように、１０３１２６と１０３１３６である。図中に示される細長い長方形があるので、読者は、参照コードワードの実例の各々を容易に見分けることができる。実際には、ビット値のみが符号化される。図から分かるように、コードワード０００１０１１が、各々の列において端から端まで繰り返される。差分６は、ある座標の最下位のディジットと、次の座標の最上位のディジットとを分離するためのマーカー値（図中では、●で表されている）として使用されている。
【００７５】
また、図４は、列の集合体への３つの７×７ウィンドウ１０６，１０７，１０８を示す。図５、図６及び図７は、それぞれウィンドウ１０６，１０７，１０８の内容を示す。各ウィンドウ内の７ビット列それぞれは、７ビット符号のコードワードとして解釈することができ、表１に従って順番にシフト値とその結果として相対位置を生成する。抽出された７ビット・コードワードにはエラーが含まれているかもしれないので、例えば上述の最大確率法による復号器を使用して(すなわち、直接的に又は代数的に)先ず該コードワードを復号化し、有効なコードワードを生成する。図４〜図７において、例として、各ウィンドウ内の抽出された多くのビットがエラーとして示されている。◆によって表される各々のビットは、エラーであることを示し、すなわち対応するビットが逆になっている。本例では、所与のコードワード内に多くても１つの損なわれたビットがあり、そのようなエラーは（上述の通り）それぞれ完全に訂正することができる。各々のコードワードを復号化した後、隣接する列の対それぞれの間のシフト値の差分によって、座標値のディジットが得られる。各々の列におけるコードワードのオフセットは垂直方向では変化しないので、モジュロ７の下で、隣接している２つのシフト値の間の差分は、ウィンドウの垂直位置について不変である。
【００７６】
水平方向については、各ウィンドウは、丁度１つのマーカーと同様に、同じ座標から又は２つの隣接する座標から５つのディジットを生成する。
【００７７】
図５から分かるように、ウィンドウ１０６は、上部から下向きに抽出されるとき抽出された７つの列に対して、｛１，１，５，４，２，３，２｝というシフト値１１０を生成する。これらは、順番に｛０，３，１，２，６，１｝という差分値１１２を生成する。
【００７８】
ウィンドウ１０６，１０７の場合のようにディジットが２つの隣接する座標にまたがっている場合でも、単一の座標を組み立てることは、簡単な事柄である。マーカーの右側の最上位のディジットは、そのマーカーの左側の最下位ディジットに付加されるだけである。
【００７９】
図４〜図７に示される例では、上述のように、差分６がマーカー（図中では●によって示されている）として使用される。このようにして、｛０，３，１，２，６，１｝という第１のウィンドウ１０６における差分値１１２の系列は、マーカー６によって分離された２つの部分列｛０，３，１，２｝及び｛１｝として扱われる。したがって、これらは、２つの座標フラグメント０３１２６及び１６として扱われる。これらは、第２のフラグメントに第１のフラグメントの精度（すなわち１００００６又は６４、ここで、４は、第１のフラグメントのディジットの数である）を掛けて、両フラグメントを合計することによって、１０３１２６という座標値１１４に変換される。最下位フラグメントに１を加えてケタ上げになるならば、１が最上位フラグメントから差し引かれる。
【００８０】
第２のウィンドウ１０７が、順番に｛１，２，６，１，０，３｝という差分値と１０３１２６という座標値を生成する｛０，６，４，５，４，４，１｝というシフト値を生成する。第３のウィンドウ１０８が、｛１，０，３，１，３，６｝という差分値と１０３１３６という座標値を生成する｛３，４，３，３，０，６，３｝というシフト値を生成する。
【００８１】
ウィンドウ内のマーカーの位置は、座標に関するウィンドウの相対的な配置を反映しているので、より高精度の座標値を発生させるのに用いることができる。図５〜図７に示すように、マーカーの右側の部分列の長さを使用して、付加する端数のディジットを発生する。すなわち、マーカーが右側の端部に隣接しているとき、そのウィンドウは座標と一直線をなすものと定義される。他の形式の配列も当然可能である。第１のウィンドウ１０６では、第２の部分列の長さは１であって、したがって、端数の座標値１１６は１６となる。第２のウィンドウ１０７では、第２の部分列の長さは３であって、したがって端数の座標値は、３６となる。第３のウィンドウ１０８では、第２の部分列の長さは０であって、したがって、端数の座標値は０６となる。検出装置の視野において検知され符号化されたデータの相対位置、検知され符号化されたデータの透視変換、及び検出装置の既知の形状寸法から、さらに高精度の座標値を生成することができる。これについては、本出願人による同時係属中の国際特許出願ＰＣＴ／ＷＯ００／７２２８７号により詳細に記述されている。
【００８２】
ｎ−１という差分は、それぞれが直接底ｎ−１ディジットに写像され得る０からｎ−２までの連続する範囲の差分値となるので特に便利であるが、マーカーはいかなる差分値もとることができる。一般的に、差分値から座標値への所定の写像については、いかなる方法も利用することができるのは当然である。
【００８３】
（空間配列）
２次元の位置符号化アレイは、空間的に結合又はインターリーブ（介在）された、直交する２つの１次元位置符号化アレイ２つから成る。３次元の位置符号化アレイは、空間的に結合又はインターリーブされた、直交する３つの１次元位置符号化アレイから成る。より高次元の位置符号化アレイについても同様である。２次元の位置符号化アレイは、面（surface）上で符号化されることができる。３次元の位置符号化アレイは３次元空間（volume）内で符号化できる。
【００８４】
１次元の位置符号化系列は、ｑ進のシンボルを含むことができる。ただし、ｑ≧２である。シンボル・レベルにおいて位置決めする必要性がないようにするためには、ｑ個の異なるシンボル値を表すのにｑ個の異なったグリフを使用することが有利である。逆に、必要なグリフの数を減少させるために、ｑは最小化されてもよい。しかしながら、空間的にコーヒーレントな（バースト）雑音が存在すれば、より大きいシンボル・サイズによって、より効率的なエラー訂正が行われる。
【００８５】
直交する系列に属するシンボルを区別する必要性を避けるために、シンボルを対にするとともに、２つの直交位置符号化系列の間の各交点においてそれらのシンボルを連結して、１組のｑ２個のグリフの１つで表されるようにしてもよい。
【００８６】
国際特許出願ＰＣＴ／ＷＯ９２／１７８５９号（J. Burns and S. Lloyd）の手法においては、２つの直交する１次元アレイを空間的にインターリーブして、それらを異なるカラーの対によって表すことにより、部分列への分離が可能になる。また、異なる基準系列を利用することによって、直交する系列を区別することもできる。
【００８７】
国際特許出願ＰＣＴ／ＷＯ００／７３８８７号（P. Ericsson）の手法においては、空間的に一致するビットを連結するとともに、とり得る４つの値の１つを表すことができる単一のグリフによって各ビット対を表すことによって、２つの直交する１次元のアレイが結合される。とり得る４つの値は、形式的な格子位置に対する４つの位置のうちの１つにおけるドットで表す。格子自身の配列は、オフ格子のドットを通る直線をフィッティングすることにより決定される。
【００８８】
図８は、２つの直交する２進の１次元位置アレイ１２０，１２２の空間的なインターリービング１１８の一例を示す。異なるグリフを区別する必要性を避けるために、図９に示すように、２つの明示的なグリフに代わって単一の画一的なグリフの有無を使用することができる。または、図１０に示すように、２つの相異なるグリフを使用することができる。
【００８９】
図１１は、２つの直交する２進の１次元位置アレイ１２６，１２８の空間的なインターリービング１２４の他の例を示す。ここで、２つのアレイにおける空間的に一致するシンボル値が結合されている。図１２は、３つの相異なるグリフと１つの空のグリフとを用いて表されるインターリービングを示す。図１３は、その形式上の位置（nominal position）からの４方向のうちの１方向にオフセットされた単一の画一的なグリフを使用して表された、インターリービングを示す（これは、国際特許出願ＰＣＴ／ＷＯ００／７３８８７号に示唆されている）。
【００９０】
グリフ・アレイ全体の構造を識別できるとすると、その構造は、その構成要素としての直交する２つの１次元の位置符号化サブアレイに分割できる。グリフの各サブアレイは、４種類の方法により、１組の１次元の位置符号系列に割当てることができる。すなわち、その４つの方法は、サブアレイの４つの可能なオリエンテーションに対応する。１次元の位置符号は、冗長性をもつので、他の要因によるエラーがある場合であっても正しい割当てにより生じるエラーが不正な割当てにより生じるエラーに比して少なくなるように、設計することができる。あるサブアレイのオリエンテーションが分かると、他方のサブアレイのオリエンテーションも分かる。または、正しいオリエンテーションを選ぶために、両方のサブアレイにまたがるエラーを最小にすることができる。
【００９１】
ある不正なサブアレイの割り当てから生じるエラーの数を定量化することができる。そのために、１次元の巡回位置符号の逆最小距離を定義することにする。
【００９２】
逆符号とは、その符号の各コードワードをシンボル方向に逆にしたものを含む符号である。ある符号の逆最小距離ｄｒｍｉｎは、その符号のコードワードと逆符号のコードワードとの間の最小のハミング距離である。
【００９３】
他の要因によるエラーがないとき、サブアレイの正しい割当てによるエラーの数はゼロである。不正な１８０°回転に起因する不正な割当てによるエラーの数には、ｎ×ｄｒｍｉｎという下側限界がある。
【００９４】
（累積シフト量）
２次元の位置符号化アレイは、通常単独のフラグメントに生じ、各々のフラグメントは、物理的なページなどの単一の表面の座標範囲を符号化する。フラグメントの間を適切に連続させるために、各フラグメントにおける最初の行及び列のシフト量は、前の行及び列の全てと関連付けられる累積シフト量を反映しなければならない。しかしながら、フラグメント間の連続性は必ずしも厳密に要求されないので、あるフラグメントの最初の行及び列はシフト量ゼロとすることができる。
【００９５】
以下の議論では、フラグメント間が連続していることが望ましいとしている。簡単のため、列間の差分を使用してｘ座標の符号化を行うことについて扱う。行間の差分を使用してｙ座標を符号化するにあたっても、同じ方法が適用される。
【００９６】
所与のｘ座標に関しては、１対の前の列間の差分それぞれは累積シフト量に寄与し、その結果、座標を符号化する第１の列のシフト量に寄与する。ここで、列の対それぞれがゼロとｂ−１との間の差分を符号化するとする。さらに、ｘ座標ｘは、ｐ、底ｂ、ディジットａｉによって表わされ、それぞれは、以下のように、差分によって符号化される。
【数１】
2004527045.tif 000008
【００９７】
隣接している座標は、値ｖを有するマーカー「ディジット」によって分離されるとする。
【００９８】
ｂｉによる累積シフト量Ｂ（ｂ，ｉ）は以下のように与えられる。
【数２】
2004527045.tif 000009
【００９９】
ａｉｂｉによる累積シフト量Ａ（ａｉ，ｂ，ｉ）は以下のように与えられる。
【数３】
2004527045.tif 000010
【０１００】
ｘまでの累積シフト量（ただし、ｘは含まない）は、以下のように与えられる。
【数４】
2004527045.tif 000011
【０１０１】
本出願人による同時係属中の国際特許出願ＰＣＴ／ＷＯ００／７２ｌ２６号及びＷＯ００／７２１２７号において論じられているように、累積されたシフト量を効率的に計算する機能は、位置符号化された面をプリントする装置において好適に実行することができる。
【０１０２】
（位置符号化の変形例）
上述のように、差分符号化の手法を使用して、明示的に又はＭ系列を通して位置を符号化できる。また、その手法は、コードワードとして位置を符号化するのに使用することができ、エラー検出及びエラー訂正を可能にする。
【０１０３】
また、差分符号化の手法によって、明示的な位置及びコードワードの両方を符号化することができ、このコードワードはエラー検出に用いられる。例えば、コードワードを、１ビットの差分それぞれを使用して符号化することができる。また、そのようなコードワードは、巡回的であれば、位置データの登録を決定するために使用することもでき、その場合には明示的なマーカー差分は必要なくなる。
【０１０４】
一般的に、巡回位置符号は、他のデータに対する登録信号を提供するために、そのデータに組み込む（又はそのデータと共存させる）ことができる。
【０１０５】
（組み込まれた機能フラッグ）
差分符号化方法自体では、機能フラッグのようなロケーションを特定するデータを２次元の位置符号化アレイに組み込むのは簡単ではない（このことは、本出願人による同時係属中の国際特許出願ＰＣＴ／ＷＯ０１／４１０５５号において論じられている）。その理由は、２次元位置符号化アレイが、直交する２つの１次元位置符号化アレイの相互作用によって２次元の位置を定義するからである。
【０１０６】
しかしながら、１座標について１つ又は複数の列（及び行）をロケーションを特定するデータとして保存できる。この場合、差分符号化方法では、差分符号化の目的のため、それらの列（及び行）を無視しなければならない。逆に、ロケーションを特定するデータは、例えばマーカー差分をまねることによって、偽の登録を行うことはできない。
【０１０７】
前節で論じられたように、１組の列（又は行）の間における差分によってエラー検出及び登録目的のためにコードワードを符号化するならば、そのコードワードによって、そのデータ列を無視するのに充分な情報が提供される。しかしながら、データ列が任意のデータを含むかもしれないので、コードワード内にエラーが生じる可能性がある。コードワードがエラー訂正可能で、エラー訂正の間にエラー中の唯一のシンボルがデータ列と関連づけられることがわかっていれば、そのときは全てがうまくいっている。また、エラーが他にもあれば、位置データ自身が疑わしく、復号器はエラーを報告しなければならない。
【０１０８】
ロケーションを特定するデータを符号化するためにほんの数ビットだけが必要とされるのであれば、隣接する列に関連するマーカー差分を誘導しないように隣接するビットを選ぶことができる。したがって、データは、解釈される前にエラーが訂正されることを考慮に入れる必要がある。この方法によれば、登録コードワードが必要なくなる。
【０１０９】
ロケーションを特定するデータにおけるエラーを検出して、あるいは訂正するためには、冗長性を導入する必要がある。巡回符号に基づく連続した冗長性の仕組みは任意のデータをサポートしないので、ロケーションを特定するデータは、標本抽出ウィンドウが少なくとも１つの完全なコードワードを含むことが保証されるようなサイズのコードワードにアレンジされることが最適である。抽出ウィンドウのサイズがｎ×ｎ（すなわち、長さｎの１対の直交する巡回位置符号に関連して機能するためのサイズ）であるならば、ロケーションを特定するデータのコードワードのサイズｎ’は、ｎ’≦ｎ／２の条件を満たさねばならない。
【０１１０】
直交する２つの１次元の位置符号化アレイにおいて、長さｎ’の２つの独立したコードワードを有するよりも、２つのアレイから対応するデータを結合することにより、長さｎまでの単一のコードワードを形成することができる。単一のより大きいコードワードが有する、バースト誤りを検出及び訂正する能力は、２つのより小さいコードワードが有するそれよりも優れている。しかし、以下で論じるように、より広い範囲を抽出するというコストが加わる。
【０１１１】
図１４は、４つの２次元位置を符号化する２次元の位置符号化アレイの一部１３０を示す。すなわち、破線の輪郭で示された４つの「タグ」１３２，１３４，１３６，１３８に対応している。また、図中には、位置符号化差分よりもむしろロケーションを特定するデータを符号化するのに使用される列１４０，１４２及び行１４４，１４６が、それらのタグに重ねられて示されている。
【０１１２】
１つのデータ列のタグ高さ部分（又は、データ行のタグ幅部分）それぞれが４つのクォータ（黒塗りの正方形１４８で表されている）に分割されて示されている。行と列とがタグの中心で交差している図１５を参照すると、対応するクォータを単一のコードワード１５０に結合するのが自然である。他の場所では、４つの相異なる行及び列からの４つのクォータ１５２，１５４，１５６，１５８をそれらの隙間に位置するコードワード１６０に系統的に結合するのが自然である。これについては、図１６に示されており、隙間の各クォータに対応する元のクォータが矢印で示されている。その結果、ロケーションを特定するデータは、タグ周波数の√２倍の周波数で符号化されることになる。図１７は、そのようにして得られたコードワード１５０，１６０のみを、対応する位置に示している。
【０１１３】
結合されたロケーションを特定するデータのコードワードのサイズがｎであるとしたとき、抽出ウィンドウのサイズを３ｎ／２に広げられるならば、この仕組みを使用して、ロケーションを特定するデータを任意の位置において回復することができる。
【０１１４】
（巡回的でない自己登録式パターン）
前節では、ターゲット・パターンとして巡回的な系列の部分列を使用することを考えたが、ターゲット・パターンとして巡回的でないパターンを使用することも考えられる。以下に説明されるように、マッチ（match）を誤る確率は充分に低いとは言えないので、一般的には、ターゲット・パターンとしてパターン全体のうちの純粋なデータ部分を使用することはできない。
【０１１５】
以下に行う分析の目的のために、Ｒｅｅｄ−Ｓｏｌｏｍｏｎコードは、エラー訂正可能な（error-correctable）符号化を産出するのに使用される。
【０１１６】
（ｎ，ｋ）リード−ソロモン符号は、その長さｎ及び次元ｋによって特徴付けられる。その符号のシンボル・サイズｑは、以下のように与えられる。
【数５】
2004527045.tif 000012
【０１１７】
訂正可能なエラーの最大数ｔは以下のように与えられる。
【数６】
2004527045.tif 000013
【０１１８】
特定のコードワードに対して、正しく復号化することが可能な、すなわちエラーにｔ個以下のシンボルを含む「エイリアス」の数は、以下のように与えられる。
【数７】
2004527045.tif 000014
【０１１９】
これは、以下のように近似（及び制限）される。
【数８】
2004527045.tif 000015
【０１２０】
エラーを含まない、異なるコードワードの数は、以下のように与えられる。
【数９】
2004527045.tif 000016
【０１２１】
（数８）及び（数９）から、有効なコードワードの数は以下のように近似される。
【数１０】
2004527045.tif 000017
【０１２２】
コードワードの総数は、以下のように与えられる。
【数１１】
2004527045.tif 000018
【０１２３】
（数１０）及び（数１１）から、マッチを誤る確率Ｐは以下のように近似される。
【数１２】
2004527045.tif 000019
【０１２４】
これは、（数６）から以下のように簡素化される。
【数１３】
2004527045.tif 000020
【０１２５】
（数１３）から、（１５，５）符号については、Ｐは、近似的に１／２５６の上限を有する。（数１０）したがって（数１３）に対するより正確なベースとして（数７）を使用すると、Ｐは近似的に１／３４１となる。
【０１２６】
したがって、任意の値のデータ・コードワードをターゲット・パターンとして使用するとき、マッチを誤る確率は充分に低いとは言えない。
【０１２７】
（数８）及び（数１１）から、特定の値のターゲット・パターンを使用をするときのマッチを誤る確率Ｑは、近似的に以下のように示される。
【数１４】
2004527045.tif 000021
【数１５】
2004527045.tif 000022
【０１２８】
（数１５）から、（１５，５）符号について、Ｑは、近似的に１／250,000,000の上限を有する。この値は、多くのアプリケーションにおいて許容されうるものである。
【０１２９】
本発明の趣旨又は範囲から逸脱しない限り、本明細書において述べた実施形態に対して様々な自明な変更及び変形をしてもよいことは、当技術分野の専門家にとって明らかである。
【図面の簡単な説明】
【０１３０】
【図１】７ビット巡回位置符号を用いた位置復号化を示す。
【図２】エラーがある場合における７ビット巡回位置符号を用いた位置復号化を示す。
【図３】７ビット巡回位置符号を用いた差分符号化の要素を示す。
【図４】水平座標の差分符号化を可能にするよう列に配置された７ビット巡回位置符号の系列１３個のアレイを示す。
【図５】図４のアレイへの第１のウィンドウからの第１座標位置の取り出しを示す。
【図６】図４のアレイへの第２のウィンドウからの第２座標位置の取り出しを示す。
【図７】図４のアレイへの第３のウィンドウからの第３座標位置の取り出しを示す。
【図８】直交する２つの１次元位置符号のインターリービングの一例を示す。
【図９】単一の画一的なグリフの有無を使用して表される図８のインターリービングを示す。
【図１０】２つの相異なるグリフを使用して表される図８のインターリービングを示す。
【図１１】直交する２つの１次元位置符号のインターリービングの別の例を示す。
【図１２】３つの相異なるグリフと１つの空のグリフを使用して表される図１１のインターリービングを示す。
【図１３】その形式上の位置からの４方向のうちの１方向にオフセットされた単一の画一的なグリフを使用して表される図１１のインターリービングを示す。
【図１４】ロケーションを特定するデータの列及び行を有する位置符号化アレイを示す。
【図１５】図１４のアレイにおけるロケーションを特定する列及び行からのデータの、タグの中心にあるロケーションを特定するコードワードへの写像を示す。
【図１６】図１４のアレイにおけるロケーションを特定する列及び行からのデータの、隙間にあるロケーションを特定するコードワードへの写像を示す。
【図１７】面上において対応するロケーションにある図１５と図１６のコードワードを示す。
【国際公開パンフレット】
2004527045.tif 000023
2004527045.tif 000024
2004527045.tif 000025
2004527045.tif 000026
2004527045.tif 000027
2004527045.tif 000028
2004527045.tif 000029
2004527045.tif 000030
2004527045.tif 000031
2004527045.tif 000032
2004527045.tif 000033
2004527045.tif 000034
2004527045.tif 000035
2004527045.tif 000036
2004527045.tif 000037
2004527045.tif 000038
2004527045.tif 000039
2004527045.tif 000040
2004527045.tif 000041
2004527045.tif 000042
2004527045.tif 000043
2004527045.tif 000044
2004527045.tif 000045
2004527045.tif 000046
2004527045.tif 000047
2004527045.tif 000048
2004527045.tif 000049
2004527045.tif 000050
2004527045.tif 000051
2004527045.tif 000052
2004527045.tif 000053
2004527045.tif 000054
2004527045.tif 000055
2004527045.tif 000056
2004527045.tif 000057
2004527045.tif 000058
2004527045.tif 000059
2004527045.tif 000060
2004527045.tif 000061
2004527045.tif 000062
2004527045.tif 000063
2004527045.tif 000064
2004527045.tif 000065
2004527045.tif 000066
【国際調査報告】
2004527045.tif 000067
2004527045.tif 000068