CODING PATTERN COMPRISING NON-REPLICATED COORDINATE DATA SYMBOLS

• US 20110180614A1
• Filed: 01/27/2010
• Published: 07/28/2011
• Est. Priority Date: 01/27/2010
• Status: Abandoned Application

• Current Assignee: Silverbrook Research Pty Limited
• Original Assignee: Silverbrook Research Pty Limited
• Inventors: Napper, Jonathon Leigh, Lapstun, Paul
• Application Number:
  US12/694,271
• Publication Number:
  US 20110180614A1
• Time in Patent Office: Days
• US Class Current: 235/494
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06K 7/14 using light without selection of wavelength, e.g. sensing reflected white light G06K7/10831 - G06K7/1097 take precedence

Abstract

A substrate having a coding pattern disposed thereon or therein. The coding pattern comprises a plurality of square tags of length l identifying two-dimensional location coordinates. Each tag comprises: a plurality n₁ of x-coordinate data symbols encoding a respective (n₂, k) Reed-Solomon code for an x-coordinate; a plurality n₁ of y-coordinate data symbols encoding a respective (n₂, k) Reed-Solomon code for a y-coordinate; a number z of the x-coordinate data symbols positioned in a central column of width q in each tag with a remaining (n₁−z) x-coordinate data symbols distributed evenly on either side of the central column; and a number z of the y-coordinate data symbols positioned in a central row of the tag of width q with a remaining (n₁-z) y-coordinate data symbols distributed evenly above and below the central row. Any square portion of the coding pattern of length (l+q) is guaranteed to contain at least (n₁+z)/2 data symbols from each of the Reed-Solomon codes.

Claims

1. A substrate having a coding pattern disposed thereon or therein, said coding pattern comprising a plurality of square tags of length l identifying two-dimensional location coordinates, each tag comprising:

a plurality n₁ of x-coordinate data symbols encoding a respective (n₂, k) Reed-Solomon code for an x-coordinate;

a plurality n₁ of y-coordinate data symbols encoding a respective (n₂, k) Reed-Solomon code for a y-coordinate;

a number z of said x-coordinate data symbols positioned in a central column of width q in each tag with a remaining (n₁−

z) x-coordinate data symbols distributed evenly on either side of said central column; and

a number z of said y-coordinate data symbols positioned in a central row of said tag of width q with a remaining (n₁−

z) y-coordinate data symbols distributed evenly above and below said central row;

wherein n₁≧

n₂ and z≧

1, such that any square portion of said coding pattern of length (l+q) is guaranteed to contain at least (n₁+z)/2 data symbols from each of said Reed-Solomon codes.

2. The substrate of claim 1, wherein n₁=n₂ and none of said x-coordinate or y-coordinate data symbols is replicated within each tag.

3. The substrate of claim 1, wherein n₂>

2k.

4. The substrate of claim 1, wherein z≧

k.

5. The substrate of claim 1, wherein each of said Reed-Solomon codes is a natural full-length code or a shortened code.

6. The substrate of claim 1, wherein:

z is from 1 to 253;

k is from 1 to 253;

n₁ is from 2 to 255; and

n₂ is from 2 to 255.

7. The substrate of claim 6, wherein up to 126 symbol errors are corrected during said decoding.

8. The substrate of claim 1, wherein:

z is from 1 to 15;

k is from 1 to 15;

n₁ is from 3 to 31; and

n₂ is from 3 to 31.

9. The substrate of claim 1, wherein each data symbol is encoded using multi-pulse position modulation.

10. The substrate of claim 9, wherein each data symbol is represented by d macrodots, each of said d macrodots occupying a respective position from a plurality of predetermined possible positions p, the respective positions of said d macrodots representing one of a plurality of possible data values, wherein p>

d.

11. The substrate of claim 10, wherein d is an integer value of 2 to 6 and p is an integer value of 4 to 12.

12. The substrate of claim 10, wherein each data symbol provides i possible symbol values, and wherein any unused symbol values are treated as erasures.

13. The substrate of claim 10, wherein q=2 s, 3 s, 4 s or 5 s, and s is defined as a spacing between adjacent macrodots.

14. The substrate of claim 1, wherein said coding pattern comprises a plurality of target elements defining a target grid, said target grid comprising a plurality of grid cells, wherein neighboring grid cells share target elements and wherein each tag is defined by a plurality of contiguous grid cells.

15. The substrate of claim 14, wherein each tag comprises M² contiguous square grid cells, wherein M is an integer having a value of 2, 3, 4, 5 or 6.

16. The substrate of claim 14, wherein each grid cell defines a symbol group containing a plurality of data symbols, wherein each symbol group comprises at least one of said x-coordinate symbols or at least one of said y-coordinate symbols.

17. The substrate of claim 16, wherein each tag comprises one or more common Reed-Solomon codewords, each common codeword being common to a plurality of contiguous tags, each common codeword comprising a respective set of common data symbols.

18. The substrate of claim 17, wherein said one or more common codewords identify a region identity, said region identity uniquely identifying said substrate or a region thereof

19. The substrate of claim 16, wherein each symbol group comprises one or more registration symbols, said registration symbols identifying one or more of:

a tag encoding format;

a translation of a symbol group relative to a tag containing said symbol group;

an orientation of a layout of said data symbols with respect to said target grid; and

a flag.

20. The substrate of claim 19, wherein said tag encoding format identifies a number of macrodots contained in each data symbol of said coding pattern.