Position-coding pattern having tag coordinates encoded by bit-shifted subsequences of cyclic position code

Abstract

A substrate having a position-coding pattern disposed on a surface thereof. The position-coding pattern comprises a plurality of tags. Each tag encodes a w-bit subsequence of a cyclic code sequence. The w-bit subsequence maps to a corresponding coordinate codeword for the tag. Adjacent tags contain a w-bit subsequence shifted by one bit relative to each other in the cyclic code sequence.

1 . A substrate having a position-coding pattern disposed on a surface thereof, said position-coding pattern comprising:
 a plurality of tags, each tag encoding a w-bit subsequence of a cyclic code sequence, said w-bit subsequence mapping to a corresponding coordinate codeword for said tag, wherein adjacent tags contain w-bit subsequences shifted by one bit relative to each other in the cyclic code sequence.   
     
     
         2 . The substrate of  claim 1 , wherein said w-bit subsequence is represented by a set of coordinate data symbols in said tag, each of said coordinate data symbols containing at least one bit of the w-bit subsequence, each coordinate data symbol being represented by one or more data elements disposed on said surface. 
     
     
         3 . The substrate of  claim 1 , wherein the cyclic code sequence is an m-sequence or a simplex code. 
     
     
         4 . The substrate of  claim 1 , wherein said cyclic code sequence has a length n and a dimension k, and wherein: n>w>k. 
     
     
         5 . The substrate of  claim 1 , wherein a given tag contains a w-bit subsequence corresponding to offset i in the cyclic code sequence, and adjacent tags on either side of said given tag contain w-bit subsequences corresponding to offsets (i+1) and (i−1) in the cyclic code sequence. 
     
     
         6 . The substrate of  claim 1 , wherein said position-coding pattern comprises a plurality of target elements defining a target grid, said target grid comprising a plurality of cells, each cell defining a symbol group, wherein neighboring symbol groups share target elements. 
     
     
         7 . The substrate of  claim 6 , wherein each tag is square and contains a plurality of symbol groups. 
     
     
         8 . The substrate of  claim 2 , wherein each coordinate data symbol is a 1-bit symbol such that w coordinate data symbols represent said w-bit subsequence. 
     
     
         9 . The substrate of  claim 2 , wherein said set of coordinate data symbols is arranged in each tag such that at any square portion of the position-coding pattern of length (l+q) is guaranteed to contain at least (w−1) bits of the w-bit subsequence, wherein l is a length of the tag and q is a length or a width of a coordinate data symbol. 
     
     
         10 . The substrate of  claim 2 , wherein each tag contains an x-coordinate codeword mapped from a first cyclic code sequence and a y-coordinate codeword mapped from a second cyclic code sequence, said x-coordinate codeword being defined by a first set of x-coordinate data symbols, and said y-coordinate codeword being defined by a second set of y-coordinate data symbols. 
     
     
         11 . The substrate of  claim 10 , wherein said first set is arranged in subsets of x-coordinate data symbols and said second set is arranged in subsets of y-coordinate data symbols. 
     
     
         12 . The substrate of  claim 11 , wherein each subset of x-coordinate data symbols is configured as a column containing a plurality of said x-coordinate data symbols, and each subset of y-coordinate data symbols is configured as a row containing a plurality of said y-coordinate data symbols, wherein each of said rows and columns has a maximal width v. 
     
     
         13 . The substrate of  claim 12 , wherein said columns of x-coordinate symbols and said rows of y-coordinate symbols are arranged such that any square portion of said position-coding pattern of length (l+v) is guaranteed to contain at least (w−1) bits of a w-bit subsequence in said first cyclic code sequence and at least (w−1) bits of a w-bit subsequence in said second cyclic code sequence, wherein l is a length of each tag. 
     
     
         14 . The substrate of  claim 10 , wherein one ore more of said coordinate data symbols is a merged data symbol, each merged data symbol being represented by said one or more data elements, and wherein each merged data symbol encodes at least two of:
 an x-coordinate data symbol from said first set;   a y-coordinate data symbol from said second set; and   at least one further data symbol which is different from said x- and y-coordinate data symbols.   
     
     
         15 . The substrate of  claim 14 , wherein said at least one further data symbol is a Reed-Solomon symbol defining a fragment of a common codeword, said common codeword being encoded by a set of Reed-Solomon symbols contained in said tag, said common codeword identifying an identity common to a plurality of contiguous tags, 
     
     
         16 . The substrate of  claim 14 , wherein each merged data symbol is represented by said one or more data elements using pulse position modulation. 
     
     
         17 . The substrate of  claim 16 , wherein said data elements are macrodots, and wherein each merged data symbol is represented by m macrodots, each of said macrodots occupying a respective position from a plurality of predetermined possible positions p within said merged data symbol, the respective positions of said macrodots representing one of a plurality of possible data values, wherein m is an integer value of 1 or more, and p>m. 
     
     
         18 . The substrate of  claim 14 , wherein each merged data symbol encodes said x-coordinate data symbol and said y-coordinate data symbol. 
     
     
         19 . The substrate of  claim 14 , wherein said x-coordinate data symbols and said y-coordinate data symbols are contained in different merged symbols. 
     
     
         20 . The substrate of  claim 2 , wherein one or more of said coordinate data symbols is a merged data symbol, each merged data symbol being represented by said one or more data elements, and wherein each merged data symbol encodes at least one of said coordinate data symbols and at least one further data symbol which is different from said coordinate data symbol.