High density two dimensional bar code symbology

• US 5,504,322 A
• Filed: 10/26/1994
• Issued: 04/02/1996
• Est. Priority Date: 01/05/1990
• Status: Expired due to Term

• Current Assignee: Symbol Technologies, Inc. (Zebra Technologies Corporation)
• Original Assignee: Symbol Technologies, Inc. (Zebra Technologies Corporation)
• Inventors: Wang, Ynjiun P., Swartz, Jerome, Pavlidis, Theodosios
• Primary Examiner(s): Hajec, Donald T.
• Assistant Examiner(s): Frech, Karl D.
• Application Number:
  US08/329,635
• Time in Patent Office: 524 Days
• Field of Search: 235/494, 235/462, 235/472
• US Class Current: 235/494
• CPC Class Codes: G06F 3/002 Specific input/output arrangements not covered by G06F3/01 - G06F3/16 other optical apparatus G02B27/00
• CPC Class Codes: G06F 8/60 Software deployment
• CPC Class Codes: G06F 8/71 Version control security arrangements therefor G06F21/57; Configuration management
• CPC Class Codes: G06K 1/126 by photographic or thermographic registration recording apparatus for measuring instruments G01D15/00
• CPC Class Codes: G06K 17/00 Methods or arrangements for effecting co-operative working between equipments covered by two or more of main groups G06K1/00 - G06K15/00, e.g. automatic card files incorporating conveying and reading operations
• CPC Class Codes: G06K 17/0016 Selecting or retrieving of images by means of their associated code-marks, e.g. coded microfilm or microfiche microfilm reading G03B21/11; computers therefor G06F16/00; teaching devices G09B5/02; accessing record carriers G11B27/002; static digital stores using optical elements G11C13/04; intermediate storage of facsimile picture signals H04N1/21
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06K 19/06046 Constructional details
• CPC Class Codes: G06K 2019/06253 for a specific application
• CPC Class Codes: G06K 7/14 using light without selection of wavelength, e.g. sensing reflected white light G06K7/10831 - G06K7/1097 take precedence
• CPC Class Codes: G06K 7/1417 2D bar codes
• CPC Class Codes: G06K 7/1443 locating of the code in an image
• CPC Class Codes: G06K 7/1456 determining the orientation of the optical code with respect to the reader and correcting therefore
• CPC Class Codes: G06K 7/1486 Setting the threshold-width for bar codes to be decoded
• CPC Class Codes: G06K 7/1491 the method including a reconstruction step, e.g. stitching two pieces of bar code together to derive the full bar code
• CPC Class Codes: H04N 1/00127 Connection or combination of a still picture apparatus with another apparatus, e.g. for storage, processing or transmission of still picture signals or of information associated with a still picture
• CPC Class Codes: H04N 1/00204 with a digital computer or a digital computer system, e.g. an internet server programmed control between transmitter and receiver or between image input and image output device H04N1/32561
• CPC Class Codes: H04N 1/00326 with a data reading, recognizing or recording apparatus, e.g. with a bar-code apparatus arrangements for the associated working of recording or reproducing apparatus with related apparatus G11B31/00
• CPC Class Codes: H04N 1/00334 with an apparatus processing barcodes or the like arrangements for sensing record carriers G06K7/00
• CPC Class Codes: H04N 1/00363 Bar codes or the like
• CPC Class Codes: H04N 1/00374 : on the same page as at least a part of the image
• CPC Class Codes: H04N 1/00392 : Other manual input means, e.g. digitisers or writing tablets
• CPC Class Codes: H04N 1/00968 : by scanning marks on a sheet mark-sheet input means H04N1/00355; sensing record carriers G06K7/00
• CPC Class Codes: H04N 1/32101 : Display, printing, storage or transmission of additional information, e.g. ID code, date and time or title
• CPC Class Codes: H04N 2201/0065 : Converting image data to a format usable by the connected apparatus or vice versa
• CPC Class Codes: H04N 2201/0067 : Converting to still picture data
• CPC Class Codes: H04N 2201/0068 : Converting from still picture data
• CPC Class Codes: H04N 2201/0081 : Image reader H04N2201/0091 - H04N2201/0094 take precedence
• CPC Class Codes: H04N 2201/0082 : Image hardcopy reproducer H04N2201/0091 - H04N2201/0094 take precedence
• CPC Class Codes: H04N 2201/3225 : of data relating to an image, a page or a document
• CPC Class Codes: H04N 2201/3269 : of machine readable codes or marks, e.g. bar codes or glyphs
• CPC Class Codes: H04N 2201/3271 : Printing or stamping
• CPC Class Codes: H04N 2201/3278 : Transmission

Abstract

A nonvolatile electro-optical read-only memory includes a substrate on which is printed (or otherwise inscribed) a complex symbol or "label" with a high density two-dimensional symbology, a variable number of component symbols or "codewords" per row, and a variable number of rows. Codewords in alternating rows are selected from mutually exclusive subsets of a mark pattern such as a (17,4) mark pattern. The subsets are defined in terms of particular values or a discriminator function, which is illustrated as being a function of the widths of bars and spaces in a given codeword. In the illustrated embodiment, each subset includes 929 available codewords; that, plus a two-step method of decoding scanned data, permitting significant flexibility in defining mappings of human-readable symbol sets into codewords. The memory may be used in conjunction with a scanner and a suitable control system in a number of applications, e.g., robotic operations or automated microfilm searching.

Claims

1. A machine readable data file structure comprising:

(a) at least two rows of codewords, one row being adjacent to and beneath another row;

(b) each said codeword representing at least one information-bearing character and being selected from among a set of detectable mark patterns;

(c) each of said mark patterns comprising a pattern of marks, each of said marks being representative of one of a plurality of different states;

(d) the codewords in each said row being selected from a subset of said mark patterns, the subset for said row being defined by a specified rule for each of said rows that differs from the rule specified for said adjacent row; and

(e) each said rule being a function of respective widths of said marks.

2. A machine readable data file structure as set forth in claim 1, wherein each of said mark patterns includes a pattern of markings of varying optical reflectivity.

3. A machine readable data file structure as set forth in claim 1, wherein each of said mark pattern includes a pattern of alternating reflecting and nonreflecting surfaces.

4. A machine readable data file structure as set forth in claim 1, wherein each of said mark pattern includes a pattern of magnetically detectable marks.

5. A machine readable data file structure as set forth in claim 1, wherein each said rule partitions the set of detectable mark patterns into a plurality of subsets of equidistant error distance.

6. A machine readable data file structure as set forth in claim 1, wherein each said subset includes only codewords having said marks of respective widths not greater than a specified upper width limit.

7. A machine readable data file structure as set forth in claim 1, wherein:

(a) said data file structure includes at least three rows of said codewords;

(b) said respective subsets include only codewords X having x-sequence function as follows;

space="preserve" listing-type="equation">f(x)=(x.sub.1 -x.sub.3 +x.sub.5 -x.sub.7) mod 9

said x-sequence functions being equal to respective preselected values; and

(c) each x_i for a codeword representing the width of an i^th mark of the codeword, where i is an integer.

8. A machine readable data file structure as set forth in claim 1, wherein:

(a) said respective subsets include only codewords X having t-sequences as follows;

space="preserve" listing-type="equation">t.sub.i =x.sub.i +x.sub.i+1

said t-sequences being not greater than 9; and

(b) each x_i of a codeword representing the width of an i^th mark of the codework, where i is an integer.

9. The machine readable data file structure according to claim 1, wherein each said rule is a function of the width of each respective mark and the total width of each respective mark pattern.

10. A machine readable data file structure comprising:

(a) at least three rows of codewords, including a second row adjacent to and disposed between a first row and a third row;

(b) each said codewords representing at least one information-bearing character and being selected from among a set of detectable mark patterns;

(c) each of said mark patterns comprising a pattern of marks, each said mark being representative of exactly one of two different states;

(d) the codewords in each said row being selected from a subset of said mark patterns;

(e) each respective said subset including only codewords X having;

said marks of respective widths not greater than a specified upper width limit,

x-sequence function as follows;

space="preserve" listing-type="equation">f(X)=(x.sub.1 -x.sub.3 +x.sub.5 -x.sub.7) mod 9

said f(X) being equal to one of 0, 3, and 6, respectively, and

t-sequences as follows;

space="preserve" listing-type="equation">t.sub.i =x.sub.i +x.sub.i+1

said t_i being not greater than 9; and

each x_i for a codeword representing the width of an i^th mark of the codeword, where i is an integer.

11. A nonvolatile read-only memory including a substrate having a machine readable data file structure comprising:

at least two rows of codewords, one row being adjacent to and beneath another row;

each said codeword representing at least one information-bearing character and being selected from among a set of detectable mark patterns;

each of said mark patterns comprising a pattern of marks, each of said marks being representative of one of a plurality of different states;

the codewords in each said row being selected from a subset of said mark patterns, the subset for said row being defined by a specified rule for each of said rows that differs from the rule specified for said adjacent row; and

each said rule being a function of respective widths of said marks.

12. A nonvolatile read-only memory as set forth in claim 11, wherein each of said mark patterns includes a pattern of marks of varying optical reflectivity.

13. A nonvolatile read-only memory as set forth in claim 11, wherein each of said mark pattern includes a pattern of alternating reflecting and nonreflecting surfaces.

14. A nonvolatile read-only memory as set forth in claim 11, wherein each of said mark pattern includes a pattern of magnetically detectable marks.

15. A nonvolatile read-only memory as set forth in claim 11, wherein each said rule partitions the set of detectable mark patterns into a plurality of subsets of equidistant error distance.

16. A nonvolatile read-only memory as set forth in claim 11, wherein each said subset includes only codewords having said marks of respective widths not greater than a specified upper width limit.

17. A nonvolatile read-only memory as set forth in claim 11, wherein:

said machine readable data file structure includes at least three rows of said codewords;

said respective subsets include only codewords X having x-sequence functions as follows;

space="preserve" listing-type="equation">f(X)=(x.sub.1 -x.sub.3 +x.sub.5 -x.sub.7) mod 9

said x-sequence functions being equal to respective preselected values; and

each x_i for a codeword representing the width of an ith mark of the codeword, where i is an integer.

18. A nonvolatile read-only memory as set forth in claim 11, wherein:

said respective subsets include only codewords X having t-sequences as follows;

space="preserve" listing-type="equation">t.sub.i =x.sub.i +x.sub.i+1

said t-sequences being not greater than 9; and

each x_i of a codeword representing the width of an ith mark on the codework, where i is an integer.

19. The nonvolatile read-only memory according to claim 11, wherein each said rule is a function of the width of each respective mark and the total width of each respective mark pattern.

20. A nonvolatile read-only memory including a substrate having a machine readable data file structure comprising:

at least three rows of codewords, including a second row adjacent to and disposed between a first row and a third row;

each said codewords representing at least one information-bearing character and being selected from among a set of detectable mark patterns;

each of said mark patterns comprising a pattern of marks, each said mark being representative of exactly one of two different states;

the codewords in each said row being selected from a subset of said mark patterns;

each respective said subset including only codewords X having;

said marks of respective widths not greater than a specified upper width limit,

x-sequence functions as follows;

space="preserve" listing-type="equation">f(X)=(x.sub.1 -x.sub.3 +x.sub.5 -x.sub.7) mod 9

said f(X) being equal to one of 0, 3, and 6, respectively, and

t-sequences as follows;

space="preserve" listing-type="equation">t.sub.i =x.sub.i+x.sub.i+1

said t_i being not greater than 9; and

each x_i for a codeword representing the width of an ith mark of the codeword, where i is an integer.

21. A data file structure that includes:

(a) at least two groups of information-containing codewords, each group being discrete and separate from another group, all groups together constituting a single identifiable data record;

(b) each said codeword representing at least one information-bearing character and at least some of said codewords being selected from among a set of detectable mark patterns;

(c) each said mark pattern comprising a pattern of marks, each said mark being representative of one of a plurality of different states;

(d) the codewords in each said group being selected from a subset of said mark patterns, the subset for said group being defined by a specified rule for that group that differs from the rule specified for at least one other group;

(e) each said rule being a function of respective widths of said marks.

22. The data file structure according to claim 21, wherein each said rule is a function of the width of each respective mark and the total width of each respective mark pattern.

23. A data file structure including:

(a) at least three groups of codewords;

(b) each said codeword representing at least one information-bearing character and being selected from among a set of detectable mark patterns;

(c) each said mark pattern comprising a pattern of marks, each said mark being representative of exactly one of two different states;

(d) the codewords in each said group being selected from a subset of said mark patterns;

(e) each respective said subset including only codewords X whose said marks are of respective widths not greater than a specified upper width limit, whose x-sequence functions f(X)=(x₁ -x₃ +x₅ -x₇) mod 9 are equal to 0, 3 or 6, respectively, and whose t-sequence t₁ =x₁ +x₁₊₁ are not greater than 9;

(f) each x₁ for a codeword representing the width of an i^th mark of the codeword.

24. A data file structure that includes:

(a) at least two groups of information-containing codewords, each group being discrete and separate from another group and containing a predetermined number of codewords not necessarily the same in each group, all groups together constituting a single identifiable data record;

(b) each information-bearing data character being represented by one or more codewords, and at least some of said codewords being selected from among a set of detectable mark patterns;

(c) each said mark pattern comprising a pattern of marks, each said mark being representative of one of a plurality of different states;

(d) the codewords in each said group being selected from a subset of said mark patterns, the subset for said group being defined by a specified rule of that group that differs from the rule specified for at least one other group;

(e) each said rule being a function of a detectable characteristic of the respective said marks.

25. A data file structure including:

(a) at least three groups of codewords;

(b) each said codeword representing at least one information-bearing character and being selected from among a set of detectable mark patterns;

(c) each said mark pattern comprising a pattern of marks, each said mark being representative of exactly one of two different states;

(d) the codewords in each said group being selected from a subset of said mark patterns;

(e) each respective said subset including only codewords whose said marks are of respective widths not greater than a specified upper width limit.

26. A method of reading and decoding a machine readable symbol, the symbol including a plurality of groups of codewords, each group comprising a plurality of individual codewords having a detectable mark/space pattern;

at least some of the codewords together defining, when taken in sequence, an encoded version of the data to be decoded, the method comprising;

(a) scanning and reading the codewords, not necessarily in the said sequence;

(b) calculating a function f (x) the value of which distinguishes the group containing x from at least one other group of codewords;

(c) dividing the scanned codewords into a plurality of partial scans, each partial scan consisting wholly of codewords of one group;

(d) recreating the said sequence; and

(e) decoding the codewords and outputting or storing the sequenced decoded data.

27. A data file structure for representing information in the form of machine-readable indicia formed from sets of data records, including:

(a) at least two groups of adjacently disposed codewords, at least one group containing a predetermined number of codewords, at least some of said codewords being selected from among a set of detectable mark patterns, each said mark pattern comprising a pattern of marks, each said mark being representative of exactly one of two different states denoted as "bars" and "spaces," the aggregate of groups of adjacently disposed codewords constituting an identifiable data record;

(b) each information-bearing data character being represented by one or more codewords in at least one of said groups;

(c) the codewords in each said group being selected from a subset of said mark patterns according to a predefined rule so that codewords of one group are distinguishable from codewords of another group, each respective subset including only codewords consisting of exactly four bars, each codeword having a total width equal to a specified upper width limit at least equal to sixteen times the minimum bar width.