High density two-dimensional bar code symbol

• US 5,304,786 A
• Filed: 01/05/1990
• Issued: 04/19/1994
• 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, Yajium P., Swartz, Jerome, Pavlidis, Theodosios
• Primary Examiner(s): Weinhardt, Robert A.
• Application Number:
  US07/461,881
• Time in Patent Office: 1,565 Days
• Field of Search: 235/462, 235/472, 235/454, 235/456, 235/487, 235/494
• US Class Current: 235/462.07
• 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 of 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 method of generating a signal representative of information encoded in a machine-readable label,

(A) said machine-readable label including at least two rows of codewords, one row adjacent to and beneath another

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

(C) each said mark/space pattern having a determinable discriminator function value and comprising a pattern of marks and spaces, each said mark and space being representative of one of a plurality of different states,

(D) each said row having codewords selected from one of a plurality of subsets of said mark/space patterns, each said subset comprising mark/space patterns having discriminator function values that are mutually exclusive of discriminator values corresponding to the mark/space patterns comprising any other subset, said method including the steps of:

(a) scanning the codewords;

(b) computing the discriminator function value for each of the scanned codewords;

(c) determining, from the value of the computed discriminator function, the row containing each of the scanned codewords;

(d) decoding each of the scanned codewords to obtain a plurality of corresponding symbolic values; and

(e) generating a signal representative of the presence of each of said corresponding symbolic values in the determined row.

2. A method of generating a signal representative of information encoded in a machine-readable label,

(A) said machine-readable label including first, second, and third rows of codewords and at least one control word, each said codeword representing at least one information-bearing character and being selected from among first, second, and third subsets of detectable mark/space patterns,

(B) each said mark/space pattern comprising a fixed width pattern of at least eight marks and spaces of varying widths representing on states and off states,

(C) each said mark and space having a width x_i of an integral multiple of a basic width unit,

(D) each of said first, second, and third subsets including only codewords X matching all of the following criteria:

(i) a discriminator function f(X)=(x₁ -x₃ +x₅ -x₇) mod 9 of each codeword X in the respective first, second, and third subsets is equal to 0, 3, or 6, respectively, (ii) all t-sequences t_i =x_i +x_i+1 of each codeword X are not greater than 9 basic width units, and (iii) each codeword X includes only marks and spaces whose widths are not greater than 6 basic width units, said method including the steps of;

(a) scanning said mark/space patterns within said machine-readable label and generating an electronic image of each of said scanned mark/space patterns;

(b) determining whether each of said scanned mark/space patterns is a codeword;

(c) if any of said scanned mark/space patterns is a codeword, then classifying each of the codewords as a member of one of the first, second, or third subsets;

(d) decoding each of the codewords in the corresponding classified subset; and

(e) generating a signal uniquely representing the codewords.

3. The method as set forth in claim 2 in which said step of determining whether each of said scanned mark/space patterns is a codeword includes the steps of:

(a) computing for each of the scanned mark/space patterns a t-sequence of N-1 digits whose i^th digit is t_i, where N is the number of marks and spaces in a scanned mark/space pattern;

(b) computing the discriminator function of each of the scanned mark/space patterns; and

(c) if the computed t-sequence and the computed discriminator function for any of the scanned mark/space patterns fail to satisfy the criteria for said first, second, and third subsets, then indicating that each said failed mark/space pattern is not a codeword.

4. A method of generating a signal representative of information encoded in a machine-readable label,

(A) said machine-readable label including first, second, and third rows of codewords and at least one control word, each said codeword representing at least one information-bearing character and being selected from among first, second, and third subsets of detectable mark/space patterns,

(B) each said mark/space pattern comprising a fixed width pattern of at least eight marks and spaces of varying widths representing on states and off states,

(C) each said mark and space having a width x_i of an integral multiple of a basic width unit,

(D) each of said first, second, and third subsets including only codewords X matching all of the following criteria:

(i) a discriminator function f(X)=(x₁ -x₃ +x₅ -x₇) mod 9 of each codeword X in the respective first, second, and third subsets is equal to 0, 3, or 6, respectively, (ii) all t-sequences t_i =x_i +x_i+1 of each codeword X are not greater than 9 basic width units, and (iii) each codeword X includes only marks and spaces whose widths are not greater than 6 basic width units, said method including the steps of;

(a) scanning said mark/space patterns within said machine-readable label and generating an electronic image of each of said scanned mark/space patterns;

(b) computing for each of the scanned mark/space patterns a t-sequence of N-1 digits whose i^th digit is t_i, where N is the number of marks and spaces in a scanned mark/space pattern;

(c) computing the discriminator functions of each of the scanned mark/space patterns;

(d) if the computed t-sequence and the computed discriminator function for any of the scanned mark/space patterns fail to satisfy the criteria for said first, second, and third subsets, then indicating that each said failed mark/space pattern is not a codeword;

(e) if any of said scanned mark/space patterns is a codeword, then classifying each of the codewords as a member of one of the first, second, or third subsets;

(f) according to the classified subset, performing a first level of decoding each of the codewords including obtaining from one of three lookup tables in a first memory, the three tables respectively representing the first, second, and third subsets, a plurality of index numbers uniquely corresponding to the computed t-sequences;

(g) performing a second level of decoding the codewords including;

(1) converting each said index number into a two-digit number in base 30, the first digit of said two-digit number being a high value and the second digit being a low value;

(2) for each of the high values and the low values in succession, (i) determining, from the state of a decoding-mode variable stored in a second memory, which of a plurality of decoding modes is a currently active decoding mode, (ii) determining a symbol character associated with the high value or low value from a lookup table in said second memory associated with the active mode, and (iii) if the symbol character is a shift character, changing to a specified new current decoding mode and changing the state of the decoding-mode variable to correspond to the new decoding mode; and

(h) generating a signal uniquely representing the codewords.

5. A method of generating a signal representative of information encoded in a machine-readable label,

(A) said machine-readable label including first, second, and third rows each comprising a plurality of codewords and at least one control word,

(B) each said codeword representing at least one information-bearing character and being selected from among first, second, and third subsets of detectable mark/space patterns,

(C) each said mark/space pattern comprising a fixed width pattern of at least eight marks and spaces of varying widths representing on states and off states,

(D) each said mark and space having a width x_i of an integral multiple of a basic width unit,

(E) each of said first, second, and third subsets including only codewords X matching all of the following criteria:

(i) a discriminator function f(X)=(x₁ -x₃ +x₅ -x₇) mod 9 of each codeword X in the respective first, second, and third subsets is equal to 0, 3, or 6, respectively, (ii) all t-sequences t_i =x_i +x_i+1 of each codeword X are not greater than 9 basic width units, and (iii) each codeword X includes only marks and spaces whose widths are not greater than 6 basic width units,

(F) each said row including a checksum codeword representing a checksum function of the other codewords in the row, the checksum function being a function of unique respective values of each codeword in the row, said method including the steps of;

(a) scanning said mark/space patterns within a row and generating an electronic image of each of said scanned mark/space patterns;

(b) computing for each of the scanned mark/space patterns a t-sequence of N-1 digits whose i^th digit is t_i, where N is the number of marks and spaces in a scanned mark/space pattern;

(c) computing the discriminator function of each of the scanned mark/space patterns;

(d) if the computed t-sequence and the computed discriminator function for any of the scanned mark/space patterns fail to satisfy the criteria for said first, second, and third subsets, then indicating that each said failed mark/space pattern is not a codeword;

(e) if any of the scanned mark/space patterns is a codeword, then classifying each of the codewords as a member of one of the first, second, or third subsets;

(f) according to the classified subset, performing a first level of decoding each of the codewords including obtaining from one of three lookup tables in a first memory, the three tables respectively representing the first, second, and third subsets, a plurality of initial index numbers uniquely corresponding to the computed t-sequences;

(g) storing said initial index numbers for each of the codewords in corresponding storage locations in an initial decoding array DA in a second memory;

(h) if an initial index number has been stored in the initial decoding array DA for all codewords in each of said rows, then computing checksum functions of the codewords represented in the initial decoding array DA;

(i) if any of the computed checksum functions does not match the checksum codeword for the respective row, then indicating an error;

(j) if a computed checksum function does match the checksum codeword for the row, then performing a second level of decoding the codewords including (1) converting each said initial index number into a two-digit number in base 30, the first digit of said two-digit number being a high value and the second digit being a low value, (2) for each of the high values and the low values in succession, (i) determining, from the state of a decoding-mode variable stored in a third memory, which of a plurality of decoding modes is a currently active decoding mode, (ii) determining a symbol character associated with the high value or low value from a lookup table in said third memory associated with the active mode, and (iii) if the symbol character is a shift character, changing to a specified new current decoding mode and changing the state of the decoding-mode variable to correspond to the new decoding mode; and

(k) generating a signal uniquely representing the codewords.

6. The method as claimed in claim 5, further including the following steps:

(l) determining a plurality of initial confidence level values corresponding to each of said initial index numbers stored in the initial decoding array (DA) and storing the determined initial confidence level values in a corresponding initial confidence array (FA) in a second memory;

(m) rescanning, redecoding, and redetermining a plurality of updated index numbers and corresponding updated confidence level values;

(n) storing in an updated decoding array in said first memory and in an updated confidence array in said second memory the respective updated index numbers and updated confidence level values;

(o) if, for each said codeword, the updated index number equals the initial index number and the updated and initial index numbers each equal one of a plurality of known codewords, then (i) adding the corresponding initial and updated confidence level values to obtain a final confidence value, (ii) storing the final confidence level value in a final confidence array, and (iii) storing the initial index number in a final decoding array;

(p) if, for each said codeword, the updated index number does not equal the initial index number and the updated and initial index numbers each equal one of said plurality of known codewords, then

(1) if the corresponding initial confidence value is greater than the updated confidence value, then storing the initial index number in a final decoding array, calculating a corresponding final confidence value by subtracting the updated confidence value from the initial confidence value, and storing the final confidence value in a final confidence array,

(2) if the corresponding updated confidence value is greater than the initial confidence value, then storing the updated index number in said final decoding array, calculating the corresponding final confidence value by subtracting the initial confidence value from the updated confidence value, and storing the final confidence value in said final confidence array, and

(3) if the corresponding initial and updated confidence values are equal, then storing a predetermined unknown index number in said final decoding array, setting the corresponding final confidence value to zero, and storing the final confidence value in said final confidence array; and

(q) if, for each said codeword, either the initial index number or the updated index number equals the predetermined unknown index number and the other index number equals one of said plurality of known index numbers, then storing the known index number and the corresponding confidence value in said final decoding array and said final confidence array, respectively.

7. A method of scanning and decoding a series of patterns representative of information encoded in a machine-readable label,

(A) said machine-readable label including first, second, and third rows each comprising a plurality of codewords and at least one control word,

(B) each said codeword representing at least one information-bearing character and being selected from among first, second, and third subsets of detectable mark/space patterns,

(C) each said mark/space pattern comprising a fixed width pattern of at least eight marks and spaces of varying widths representing on states and off states,

(D) each said mark and space having a width x_i of an integral multiple of a basic width unit,

(E) each of said first, second, and third subsets including only codewords X matching all of the following criteria:

(i) a discriminator function f(X)=(x₁ -x₃ +x₅ -x₇) mod 9 of each codeword X in the respective first, second, and third subsets is equal to 0, 3, or 6, respectively, (ii) all t-sequences t_i =x_i +x_i+1 of each codeword X are not greater than 9 basic width units, and (iii) each codeword X includes only marks and spaces whose widths are not greater than 6 basic width units,

(F) each said row including a row checksum codeword representing a checksum function of the other codewords in the row, the checksum function being a function of unique respective values of each codeword in the row,

(G) the machine-readable label including a sequence of one or more codewords representing a structure checksum for the machine-readable label, said method including the steps of;

(a) scanning a mark/space pattern within a row and generating an electronic image of said scanned mark/space pattern;

(b) computing a t-sequence of N-1 digits whose i^th digit is t_i, where N is the number of marks and spaces in the scanned mark/space pattern;

(c) computing the discriminator function of the scanned mark/space pattern; and

(d) if the computed t-sequence and the computed discriminator function fail to satisfy the criteria for said first, second, and third subsets, then indicating that the scanned mark/space pattern is not a codeword;

(e) if the scanned mark/space pattern is a codeword, then classifying the codeword as a member of one of the first, second, or third subsets;

(f) according to the classified subset, performing a first level of decoding the codeword including obtaining from one of three lookup tables in a first memory, the three tables corresponding to the first, second, and third subsets, an initial index number uniquely corresponding to the computed t-sequence;

(g) storing said initial index number for the codeword in a corresponding storage location in an initial decoding array DA in a second memory;

(h) repeatedly performing steps (a) through (g) until an initial index number has been stored in the initial decoding array DA for (i) each of the row checksum codewords for each said row and the structure checksum codeword sequence, and (ii) all but at most two of all codewords in all rows of the machine-readable label;

(i) if an initial index number has not been stored for an unknown codeword in any of said rows, then computing an initial index number for each said unknown codeword as a function of one or both of the initial index numbers corresponding to the respective row checksum codeword and the structure checksum codeword sequence;

(j) if an initial index number has been stored in the initial decoding array DA for all codewords in any of said rows, then computing the respective checksum function of the codewords represented in the initial decoding array DA for each said row;

(k) if the computed checksum function does not match the row checksum codeword for any of said rows, then indicating an error for each unmatched checksum function.

8. The method as set forth in claim 7 including the additional steps, if the computed checksum does match the checksum codeword for the row, of:

(l) performing a second level of decoding the codewords including;

(1) converting each said initial index number into a two-digit number in base 30, the first digit of said two-digit number being a high value and the second digit being a low value;

(2) for each of the high values and the low values in succession, (i) determining, from the state of a decoding-mode variable stored in a third memory, which of a plurality of decoding modes is a currently active decoding mode, (ii) determining a symbol character associated with the high value or low value from a lookup table in said third memory associated with the active mode, and (iii) if the symbol character is a shift character, changing to a specified new current decoding mode and changing the state of the decoding-mode variable to correspond to the new decoding mode; and

(m) generating a signal uniquely representing the codewords.

9. The method as claimed in claim 7 further including the following steps:

(m) determining a plurality of initial confidence level values corresponding to each of said initial index numbers stored in the initial decoding array (DA) and storing the determined initial confidence level values in a corresponding initial confidence array (FA) in a second memory;

(n) rescanning, redecoding, and redetermining a plurality of updated index numbers and corresponding updated confidence level values;

(o) storing in an updated decoding array in said first memory and in an updated confidence array in said second memory the respective updated index numbers and updated confidence level values;

(p) if, for each said codeword, the updated index number equals the initial index number and the updated and initial index numbers each equal one of a plurality of known codewords, then (1) adding the corresponding initial and updated confidence level values to obtain a final confidence value, (2) storing the final confidence level value in a final confidence array, and (3) storing the initial index number in a final decoding array;

(q) if, for each said codeword, the updated index number does not equal the initial index number and the updated and initial index numbers each equal one of said plurality of known codewords, then

(1) if the corresponding initial confidence value is greater than the updated confidence value, then storing the initial index number in a final decoding array, calculating a corresponding final confidence value by subtracting the updated confidence value from the initial confidence value, and storing the final confidence value in a final confidence array,

(2) if the corresponding updated confidence value is greater than the initial confidence value, then storing the updated index number in said final decoding array, calculating the corresponding final confidence value by subtracting the initial confidence value from the updated confidence value, and storing the final confidence value in said final confidence array, and

(3) if the corresponding initial and updated confidence values are equal, then storing a predetermined unknown index number in said final decoding array, setting the corresponding final confidence value to zero, and storing the final confidence value in said final confidence array; and

(r) if, for each said codeword, either the initial index number or the updated index number equals the predetermined unknown index number and the other index number equals one of said plurality of known index numbers, then storing the known index number and the corresponding confidence value in said final decoding array and said final confidence array, respectively.

10. The method as set forth in claim 9, including the additional steps of:

(s) performing, if the computed checksum matches the checksum codeword for the row, a second level of decoding the scanned codewords including;

(1) converting each index number stored in said final decoding array into a two-digit number in base 30, the first digit of said two-digit number being a high value and the second digit being a low value;

(2) for each of the high values and the low values in succession, (i) determining, from the state of a decoding-mode variable stored in a third memory, which of a plurality of decoding modes is a currently active decoding mode, (ii) determining a symbol character associated with the high value or low value from a lookup table in said third memory associated with the active mode, and (iii) if the symbol character is a shift character, changing to a specified new current decoding mode and changing the state of the decoding-mode variable to correspond to the new decoding mode; and

(t) generating a signal uniquely representing the scanned codewords.

11. A method for generating a signal produced by scanning a machine-readable label that includes a plurality of codewords organized into at least two adjacent rows, each said codeword representing at least one human-recognizable symbol and no codeword in any one row being identical to any codeword in an adjacent row, said method including the steps of:

(a) scanning said label to detect said codewords;

(b) determining a detectable characteristic for each said scanned codeword;

(c) computing a unique index number for each said scanned codeword as a function of said detectable characteristic; and

(d) processing each of the index numbers to generate a signal representative of the at least one human-recognizable symbol.

12. The method as set forth in claim 11 in which the step of determining a detectable characteristic for each said scanned codeword includes the step of computing a discriminator function, no codeword in any one row having a discriminator function identical to that of a codeword in an adjacent row.

13. The method as set forth in claim 11 in which each said codeword comprises a fixed width pattern of at least eight marks and spaces of varying widths and each said mark and space has a width x_i of an integral multiple of a basic width unit;

wherein the step of determining a detectable characteristic for each said scanned codeword includes the step of computing a discriminator function f(X)=(x₁ -x₃ +x₅ -x₇) mod 9 of each codeword; and

wherein no codeword in any one row has a function f(X) identical to the function f(X) of any codeword in an adjacent row.

14. The method as set forth in claim 11, wherein no codeword in any one row has a function f(X) identical to the function f(X) of any codeword in an adjacent row, each said codeword comprising a fixed width pattern of at least eight marks and spaces of varying widths and each said mark and space has a width x_i of an integral multiple of a basic width unit, the step of determining a detectable characteristic for each said scanned codeword including the steps of:

(a) computing a function f(X)=(x₁ -x₃ +x₅ -x₇) mod 9 of each codeword; and

(b) computing for each codeword a function t_k =x_k +x_k+1 for k=1, . . . , 7.

15. The method as set forth in claim 11 in which

the determining step represents a first decoding step and the computing step represents a second decoding step;

and

in which the step of processing each of the index numbers includes the substeps of

determining whether each said codeword includes a representation of a mode-switching symbol, and

if so, switching from a first decoding mode to a second decoding mode.

16. A method for storing and retrieving information by scanning indicia on the surface of a substrate,

(A) said indicia including a plurality of codewords scanned sequentially and organized into at least two adjacent rows,

(B) each codeword being either an information codeword or a control codeword,

(C) each information codeword being a representation of at least one information-containing data structure,

(D) no codeword in any one row being identical to any codeword in an adjacent row, said method comprising the steps of:

(a) storing information including applying said indicia to said substrate; and

(b) retrieving said information, including;

(1) scanning said indicia to detect a codeword;

(2) determining whether said scanned codeword is an information codeword or a control codeword,

(3) providing a plurality of different protocols, each said protocol associating said scanned codeword with a corresponding one of said data structures, only one protocol being active at any given time;

(4) if said scanned codeword is an information codeword, decoding and outputting said scanned codeword according to the active protocol,

(5) if said scanned codeword is a control codeword, processing said scanned codeword to decode a symbol representative of a new protocol, and changing the active protocol to the new protocol, and

(6) repeating steps (1) through (5) until all codewords are decoded.

17. An apparatus for generating a signal representative of information encoded in a machine-readable label, said machine-readable label including at least two adjacent rows of codewords, each said codeword representing at least one information bearing character and being selected from a set of detectable mark/space patterns, each said mark/space pattern having a determinable discriminator function, the apparatus comprising:

scanning means for scanning said codewords within the machine-readable label;

means for computing a discriminator function value for each of the each of the scanned codewords;

means for determining, from the value of the discriminator function computed by the computing means, the row of the machine-readable label corresponding to each of the scanned codewords;

means for decoding each of the scanned codewords to obtain a plurality of corresponding symbolic values; and

means for generating a signal representing the presence of each of said plurality of corresponding symbolic values in the determined row.

18. An apparatus for generating a signal representative of information encoded in a machine-readable label, said machine-readable label including first, second, and third rows of codewords and at least one control word, each said codeword representing at least one information-bearing character and being selected from first, second, and third subsets of detectable mark/space patterns, each said mark/space pattern comprising a fixed width pattern of at least eight marks and spaces of varying widths representing on states and off states, each said mark and space having a width x_i of an integral multiple of a basic width unit, each of said first, second, and third subsets including only codewords X matching all of the following criteria:

(i) a discriminator function f(X)=(x₁ -x₃ +x₅ -x₇) mod 9 of each codeword in the respective first, second and third subsets is equal to 0, 3, or 6, respectively,

(ii) all t-sequences t_i =x_i +x_i+1 of each codeword X are not greater than 9 basic width units, and

(iii) each codeword X includes only marks and spaces whose widths are not greater than 6 basic width units, the apparatus comprising;

(a) means for scanning said mark/space patterns within said machine-readable label and for generating an electronic image of each of said scanned mark/space patterns;

(b) means for determining whether each of said scanned mark/space patterns is a codeword;

(c) means, coupled to said determining means, for classifying each of the codewords as a member of one of the first, second, or third subsets;

(d) means for decoding in the classified subset each of the codewords; and

(e) means for generating a signal uniquely representing the codewords.

19. The apparatus as set forth in claim 18 in which said means for determining whether each of said scanned mark/space patterns is a codeword includes:

(i) first means for computing, from each of the scanned mark/space patterns, a t-sequence of N-1 digits whose i^th digit is t_i, where N is the number of marks and spaces in a scanned mark/space pattern;

(ii) second means for computing the discriminator function of each of the scanned mark/space patterns; and

(iii) means, coupled to the first and second computing means, for indicating that any of the scanned mark/space patterns is not a codeword, if the computed t-sequence and the computed discriminator function fail to satisfy the criteria for said first, second, and third subsets.

20. An apparatus for generating a signal representative of information encoded in a machine-readable label, said machine-readable label including first, second, and third rows of codewords and at least one control word, each said codeword representing at least one information-bearing character and being selected from first, second, and third subsets of detectable mark/space patterns, each said mark/space pattern comprising a fixed width pattern of at least eight marks and spaces of varying widths representing on states and off states, each said mark and space having a width x_i of an integral multiple of a basic width unit, each of said first, second, and third subsets including only codewords X matching all of the following criteria:

(i) a discriminator function f(X)=(x₁ -x₃ +x₅ -x₇) mod 9 of each codeword in the respective first, second and third subsets is equal to 0, 3, or 6, respectively,

(ii) all t-sequences t_i =x_i +x_i+1 of each codeword X are not greater than 9 basic width units, and

(iii) each codeword X includes only marks and spaces whose widths are not greater than 6 basic width units, the apparatus comprising;

(a) means for scanning said mark/space patterns within said machine-readable label and for generating an electronic image of each of said scanned mark/space patterns;

(b) first means for computing, from each of the scanned mark/space patterns, a t-sequence of N-1 digits whose i^th digit is t_i, where N is the number of marks and spaces in each of the scanned mark/space patterns;

(c) second means for computing the discriminator function of each of the scanned mark/space patterns;

(d) means, coupled to the first and second computing means, for indicating that any of the scanned mark/space patterns is not a codeword, if the computed t-sequence and the computed discriminator function fail to satisfy the criteria for said first, second, and third subsets;

(e) means, coupled to said indicating means, for classifying each of the codewords as a member of one of the first, second, or third subsets;

(f) means, coupled to said classifying means, for performing a first level of decoding each of the codewords including obtaining from one of three lookup tables in a first memory, the three tables corresponding to the first, second, and third subsets, a plurality of index numbers uniquely corresponding to the computed t-sequences from the first computing means;

(g) means for performing a second level of decoding the codewords including;

(1) means for converting each said index number into a two-digit number in base 30, the first digit of said two-digit number being a high value and the second digit being a low value,

(2) for each of the high values and the low values, (i) first means for determining, from the state of a decoding-mode variable stored in a second memory, which of a plurality of decoding modes is a currently active decoding mode, (ii) second means for determining, a symbol character associated with the high value or low value from a lookup table in said second memory associated with the active mode, and (iii) means, coupled to said second determining means, for changing to a specified new current decoding mode, and for changing the state of the decoding-mode variable to correspond to the new decoding mode, if said symbol character is a shift character; and

(h) means for generating a signal uniquely representing the codewords.

21. An apparatus for generating a signal representative of information encoded in a machine-readable label, said machine-readable label including first, second, and third rows each comprising a plurality of codewords and at least one control word, each said codeword representing at least one information-bearing character and being selected from among first, second, and third subsets of detectable mark/space patterns, each said mark/space pattern comprising a fixed-width pattern of at least eight marks and spaces of varying widths representing on states and off states, each said mark and space having a width x_i of an integral multiple of a basic width unit, each of said first, second, and third subsets including only codewords X matching all of the following criteria:

(i) a discriminator function f(X)=(x₁ -x₃ +x₅ -x₇) mod 9 of each codeword in the respective first, second and third subsets is equal to 0, 3, or 6, respectively,

(ii) all t-sequences t_i =x_i +x_i+1 of each codeword X are not greater than 9 basic width units, and

(iii) each codeword X includes only marks and spaces whose widths are not greater than 6 basic width units, each said row including a checksum codeword representing a checksum function of the other codewords in the row, the checksum function being a function of unique respective values of each codeword in the row, the apparatus comprising;

(a) means for scanning each of said mark/space patterns within said machine-readable label and for generating an electronic image of each of said scanned mark/space patterns;

(b) first means for computing, for each of the scanned mark/space patterns, a t-sequence of N-1 digits whose i^th digit is t_i, where N is the number of marks and spaces in each of the scanned mark/space patterns;

(c) second means for computing the discriminator function of each of the scanned mark/space patterns;

(d) means, coupled to the first and second computing means, for indicating that any of the scanned mark/space patterns is not a codeword, if the computed t-sequence and the computed x-sequence fail to satisfy the criteria for said first, second, and third subsets;

(e) means, coupled to said indicating means, for classifying each of the codewords as a member of one of the first, second, or third subsets;

(f) means, coupled to said classifying means, for performing a first level of decoding the codewords including obtaining from one of three lookup tables in a first memory, the three tables corresponding to the first, second, and third subsets, a plurality of initial index numbers uniquely corresponding to the computed t-sequences from the first computing means;

(g) means for storing said initial index numbers for the codewords in a corresponding storage location in an initial decoding array DA in a second memory;

(h) third means for computing checksum functions of the codewords represented in the initial decoding array DA if an initial index number has been stored in the initial decoding array DA for all codewords in each of said rows;

(i) second means for indicating an error if any of the computed checksum functions does not match the checksum codeword for the respective row;

(j) means for performing a second level of decoding the codewords, if a computed checksum function does match the checksum codeword for the row, including;

(1) means for converting each said initial index number into a two-digit number in base 30, the first digit of said two-digit number being a high value and the second digit being a low value,

(2) first means for determining, for each of the high values and the low values, from the state of a decoding-mode variable stored in a third memory, which of a plurality of decoding modes is a currently active decoding mode,

(3) second means for determining, for each of the high values and the low values, a symbol character associated with the high value or low value from a lookup table in said third memory associated with the active mode, and

(4) means, coupled to said second determining means, for changing, for each of the high values and low values, to a specified new current decoding mode and changing the state of the decoding-mode variable to correspond to the new decoding mode if said symbol character is a shift character; and

(k) means for generating a signal uniquely representing the codewords.

22. The apparatus as claimed in claim 21, further comprising:

(m) means for determining a plurality of initial confidence level values corresponding to each of said initial index numbers stored in the initial decoding array (DA) and for storing the determined initial confidence level values in a corresponding initial confidence array (FA) in a second memory;

(n) means for rescanning, redecoding, and redetermining a plurality of updated index numbers and corresponding updated confidence level values;

(o) means for storing in an updated decoding array in said first memory and in an updated confidence array in said second memory the respective updated index numbers and updated confidence level values;

(p) means for adding, for each said codeword, the initial and updated confidence level values to obtain a final confidence level value, for storing the final confidence level value in a final confidence array, and for storing the initial index number in a final decoding array, if the updated index number equals the initial index number and the updated and initial index numbers each equal one of a plurality of known codewords;

(q) means for storing the initial index number in a final decoding array, for computing a final confidence value by subtracting the updated confidence value from the initial confidence value, and for storing the final confidence value in a final confidence array, if the initial confidence value is greater than the updated confidence value, and if, for each said codeword, the updated index number does not equal the initial number value and the updated and initial index numbers each equal one of said plurality of known codewords;

(r) means for storing the updated index number in said final decoding array, for calculating the final confidence value by subtracting the initial confidence value from the updated confidence value, and for storing the final confidence value in said final confidence array, if the updated confidence value is greater than the initial confidence value, and if, for each said codeword, the updated index number does not equal the initial number value and the updated and initial index numbers each equal one of said plurality of known codewords;

(s) means for storing a predetermined unknown index number in said final decoding array, for setting the corresponding final confidence value to zero, and for storing the final confidence value in said final confidence array, if the initial and updated confidence numbers are equal, and if, for each said codeword, the updated index number does not equal the initial number value and the updated and initial index numbers each equal one of said plurality of known codewords; and

(t) means for storing, for each said codeword, the known index number and the corresponding confidence value in said final decoding array and said final confidence array, respectively, if either the initial index number or the updated index number equals the predetermined unknown index number and the other index number equals one of said plurality of known index numbers.

23. An apparatus for scanning and decoding a series of patterns representative of information encoded in a machine-readable label, said machine-readable label including first, second, and third rows each comprising a plurality of codewords and at least one control word, each said codeword representing at least one information-bearing character and being selected from among first, second, and third subsets of detectable mark/space patterns, each said mark/space pattern comprising a fixed-width pattern of marks and spaces of varying widths representing on states and off states, each said mark and space having a width x_i of an integral multiple of a basic width unit, each of said first, second, and third subsets including only codewords X matching all of the following criteria:

(i) a discriminator function f(X)=(x₁ -x₃ +x₅ -x₇) mod 9 of each codeword in the respective first, second and third subsets is equal to 0, 3, or 6, respectively,

(ii) all t-functions t_i =x_i +x_i+1 of each codeword X are not greater than 9 basic width units, and

(iii) each codeword X includes only marks and spaces whose widths are not greater than 6 basic width units, each said row including row checksum a codeword representing a checksum function of the other codewords in the row, the checksum function being a function of unique respective values of each codeword in the row, the machine-readable label including a sequence of one or more codewords representing a structure checksum for the machine-readable label, the apparatus comprising;

(a) means for scanning each of said mark/space patterns within said machine-readable label and for generating an electronic image of each of said scanned mark/space patterns;

(b) first means for computing, for each of the scanned mark/space patterns, a t-sequence of N-1 digits whose i^th digit is t₁, where N is the number of marks and spaces in each of the scanned mark/space patterns;

(c) second means for computing the discriminator function of each of the scanned mark/space patterns; and

(d) means, coupled to the first and second computing means, for indicating that each of the scanned mark/space patterns is not a codeword, if the computed t-sequence and the computed discriminator function fail to satisfy the criteria for said first, second, and third subsets;

(e) means, coupled to the indicating means, for classifying each of the codewords as a member of one of the first, second, or third subsets, if the scanned mark/space pattern is a codeword;

(f) means, coupled to said classifying means, for performing a first level of decoding the codewords including obtaining from one of three lookup tables in a first memory, the three tables corresponding to the first, second, and third subsets, a plurality of initial index numbers uniquely corresponding to the computed t-sequences from the first computing means;

(g) means for storing each of said initial index numbers for each of the codewords in a corresponding storage location in an initial decoding array DA in a second memory;

(h) third means for computing an initial index number for each codeword for which an initial index number has not been stored in the initial decoding array DA;

(i) fourth means for computing the checksum function of the codewords represented in the decoding array DA for any of said rows in which an initial index number has been stored in the initial decoding array DA for all codewords in a row; and

(j) second means for indicating an error for any of said rows in which the computed checksum function does not match the row checksum codeword.

24. The apparatus as set forth in claim 23 further comprising:

(k) means for performing a second level of decoding the codewords including;

(1) means for converting each said initial index number into a two-digit number in base 30, the first digit of said two-digit number being a high value and the second digit being a low value,

(2) first means for determining, for each of the high values and the low values, from the state of a decoding-mode variable stored in a third memory, which of a plurality of decoding modes is a currently active decoding mode,

(3) second means for determining, for each of the high values and the low values, a symbol character associated with each high value and low value from a lookup table in said third memory associated with the active mode, and

(4) means, coupled to the second determining means, for changing, for each of the high values and the low values, to a specified new current decoding mode and changing the state of the decoding-mode variable to correspond to the new decoding mode if said symbol character is a shift character; and

(1) means for generating a signal uniquely representing the codewords.

25. The apparatus as claimed in claim 23 further comprising:

(1) means for determining a plurality of initial confidence level values corresponding to each of said initial index numbers stored in the initial decoding array (DA) and for storing the determined initial confidence level values in a corresponding initial confidence array (FA) in a second memory;

(m) means for rescanning, redecoding, and redetermining a plurality of updated index numbers and corresponding updated confidence level values;

(n) means for storing in an updated decoding array in said first memory and an updated confidence array in said second memory the respective updated index numbers and updated confidence level values;

(o) means for adding, for each said codeword, the initial and updated confidence level values to obtain a final confidence level value, for storing the final confidence level value in a final confidence array, and for storing the initial index number in a final decoding array, if the updated index number equals the initial index number and the updated and initial index numbers each equal one of a plurality of known codewords;

(p) means for storing the initial index number in a final decoding array, for computing a final confidence value by subtracting the updated confidence value from the initial confidence value, and for storing the final confidence value in a final confidence array, if the initial confidence value is greater than the updated confidence value, and if, for each said codeword, the updated index number does not equal the initial number value and the updated and initial index numbers each equal one of said plurality of known codewords;

(q) means for storing the updated index number in said final decoding array, for calculating the final confidence value by subtracting the initial confidence value from the updated confidence value, and for storing the final confidence value in said final confidence array, if the updated confidence value is greater than the initial confidence value, and if, for each said codeword, the updated index number does not equal the initial number value and the updated and initial index numbers each equal one of said plurality of known codewords;

(r) means for storing a predetermined unknown index number in said final decoding array, for setting the corresponding final confidence value to zero, and for storing the final confidence value in said final confidence array, if the initial and updated confidence numbers are equal, and if, for each said codeword, the updated index number does not equal the initial number value and the updated and initial index numbers each equal one of said plurality of known codewords; and

(s) means for storing, for each said codeword, the known index number and the corresponding confidence value in said final decoding array and said final confidence array, respectively, if either the initial index number or the updated index number equals the predetermined unknown index number and the other index number equals one of said plurality of known index numbers.

26. The apparatus as claimed in claim 25 further comprising:

(r) means for performing a second level of decoding the scanned codewords including

(1) means for converting each said index number into a two-digit number in base 30, the first digit of said two-digit number being a high value and the second digit being a low value,

(2) first means for determining, for each of the high values and the low values, from the state of a decoding-mode variable stored in a third memory, which of a plurality of decoding modes is a currently active decoding mode,

(3) second means for determining, for each of the high values and the low values, a symbol character associated with each high value and low value from a lookup table in said third memory associated with the active mode, and

(4) means, coupled to the second determining means, for changing, for each of the high values and the low values, to a specified new current decoding mode and changing the state of the decoding-mode variable to correspond to the new decoding mode if said symbol character is a shift character; and

(s) means for generating a signal uniquely representing the scanned codewords.

27. An apparatus for generating a signal produced by scanning a machine-readable label, said machine readable label including a plurality of codewords organized into at least two adjacent rows, each said codeword representing at least one human-recognizable symbol and no codeword in any one row being identical to any codeword in an adjacent row, the apparatus comprising:

(a) means for scanning said label to detect said codewords;

(b) first decoding means for determining a detectable characteristic for each said scanned codeword;

(c) second decoding means for computing a unique index number for each said scanned codeword as a function of said detectable characteristic; and

(d) means for processing each of the index numbers to generate a signal representative of said at least one human-recognizable symbol.

28. The apparatus of claim 27, wherein the first decoding means for determining a detectable characteristic for each said scanned codeword includes:

means for computing a discriminator function, no codeword in any one row having a discriminator function identical to that of a codeword in an adjacent row.

29. The apparatus of claim 27, wherein each said codeword comprises a fixed width pattern of at least eight marks and spaces of varying widths and each said mark and space has a width x_i of an integral multiple of a basic width unit, the first decoding means for determining a detectable characteristic for each said codeword including:

means for computing a discriminator function f(X)=(x₁ -x₃ +x₅ -x₇) mod 9 of each codeword.

30. The apparatus of claim 27, wherein each said codeword comprises a fixed width pattern of at least eight marks and spaces of varying widths and each said mark and space has a width x_i of an integral multiple of a basic width unit, the first decoding means for determining a detectable characteristic for each said scanned codeword including:

(i) means for computing a discriminator function f(X)=(x₁ -x₃ +x₅ -x₇) mod 9 of the codewords; and

(ii) means for computing a t-sequence t_k =x_k +x_k+1 for k having values from 1 to 7.

31. The apparatus of claim 27, wherein the determining means represents a first decoding means and the computing means represents a second decoding means, and wherein the means for processing each of the index numbers includes:

second means for determining whether each said scanned codeword includes a representation of a mode-switching symbol, and

means, coupled to the second determining means, for switching from a first decoding mode to a second decoding mode, if a scanned codeword includes a representation of a mode-switching symbol.

32. An apparatus for storing and retrieving information by scanning indicia on the surface of a substrate, said indicia including a plurality of codewords scanned sequentially and organized into at least two adjacent rows, each codeword being either an information codeword or a control codeword, each information codeword being a representation of at least one information-containing data structure, no codeword in any one row being identical to any codeword in an adjacent row, the apparatus comprising:

(a) means for storing information including applying said indicia to said substrate; and

(b) means for retrieving said information including;

(1) means for scanning said indicia to detect said information and control codewords;

(2) means for determining whether each of said scanned codewords is an information codeword or a control codeword,

(3) means for providing a plurality of different protocols, each said protocol associating each said scanned codeword with a corresponding said data structure, only one protocol being active at any given time;

(4) means, coupled to the determining means, for decoding and outputting each of said scanned information codewords according to the active protocol, and

(5) means, coupled to the determining means, for processing each of said scanned control codewords to decode a symbol representative of a new protocol, and for changing the active protocol to the new protocol.

33. A method of reading a machine-readable symbol, the symbol, including a plurality of individual codewords and at least one control word, each codeword and control word having a detectable mark/space pattern, the codewords, when taken in sequence, together defining an encoded version of data to be decoded, the mark/space pattern of each codeword having a detectable characteristic representative of information relating to a position of each said codeword within said sequence, the method comprising the steps, executed using a machine, of:

(a) scanning and reading the codewords;

(b) calculating, for each codeword X, a value of a discriminator function f(X) dependent upon the detectable characteristic;

(c) determining the position in said sequence of each codeword X as a function of the order in which each codeword X has been read and as a function of the corresponding value of said discriminator function f(X); and

(d) decoding, as a function of said determined position, the codewords and outputting a decoded version of said data.

34. The method as claimed in claim 33 wherein the decoding step includes the substep of storing the decoded data.

35. The method as claimed in claim 33 wherein the codewords are arranged in a plurality of subset regions within the symbol, the subset region into which each codeword X lies depending upon the corresponding value of said discriminator function f(X).

36. The method as claimed in claim 33 wherein the codewords are arranged in a plurality of subset regions within the symbol and said discriminator function f(X) may take a plurality of discrete values, the subset region into which each codeword X falls being uniquely determined by the corresponding value of said discriminator function f(X).

37. The method as claimed in claim 36 wherein the mark/space patterns within any given subset region are approximately equidistant in terms of error distance from the mark/space patterns within any other subset region.

38. The method as claimed in claim 33 wherein the codewords are arranged in a plurality of rows within the symbol, the row in which each codeword X lies being at least partially determined by the corresponding value of said discriminator function f(X).

39. The method as claimed in claim 38 wherein the step of scanning and reading the codewords includes the substeps of scanning said codewords substantially row-wise, and assigning the codewords X_i (i=1, 2 . . . ) to a common row so long as the value of f(X_i) remains constant.

40. The method as claimed in claim 39 wherein a first row comprises codewords having values of f(X_i) that are mutually exclusive of values of f(X_i) for codewords lying in a second adjacent row.

41. The method as claimed in claim 40 wherein a third row comprises codewords having values of f(X_i) that are mutually exclusive of values of f(X_i) for codewords lying in said first row and said second row, said third row being adjacent to said second row.

42. The method as claimed in claim 38 wherein said machine-readable symbol includes a symbol checksum codeword and each said row of said machine-readable symbol includes a row checksum codeword, the method further comprising the steps of:

(e) computing a checksum for each said row; and

(f) for each said row, determining that an error has occurred if said calculated checksum does not match a checksum provided by the corresponding row checksum codeword.

43. The method as claimed in claim 42 wherein the step of scanning and reading includes the substep of

scanning each said row to determine whether a scanned mark/space pattern is a codeword, and

wherein the step of decoding the codewords includes, for each said row, the following substeps:

(1) determining, where possible, an index number corresponding to each said codeword;

(2) storing the respective index numbers in a decoding array (DA) in a memory; and

(3) repeating substeps (1) and (2) until an index number has been stored in said decoding array (DA) for (i) the row checksum codeword for the row, and (ii) all but one of the codewords in the row, the method further comprising the step of;

(g) reconstructing the missing one codeword using the row checksum codeword.

44. The method as claimed in claim 42 wherein the step of scanning and reading includes scanning each said row to determine whether a scanned mark/space pattern is a codeword, and wherein the step of decoding the determined codewords further includes the following substeps:

determining, where possible, an initial index number corresponding to each said codeword;

storing the respective initial index numbers in an initial decoding array (DA) in a first memory; and

repeating the determining and storing substeps for each row and for all rows until an initial index number has been stored in the initial decoding array (DA) for;

(i) said symbol checksum codeword, (ii) all but two of the codewords in the symbol, and (iii) the row checksum codewords for each row having the missing codewords, the method further comprising the step of;

(g) reconstructing the missing codewords using said row checksum codewords and said symbol checksum codeword.

45. The method as claimed in claim 44 further comprising the steps of:

(h) determining a plurality of initial confidence level values corresponding to each of said initial index numbers stored in the initial decoding array (DA) and storing the determined initial confidence level values in a corresponding initial confidence array (FA) in a second memory;

(i) rescanning, redecoding, and redetermining a plurality of updated index numbers and corresponding updated confidence level values;

(j) storing in an updated decoding array in said first memory said updated index numbers and storing in an updated confidence array in said second memory the updated confidence level values;

(k) if, for each said codeword, the updated index number equals the initial index number and the updated and initial index numbers each represent one of a plurality of known codewords, then (i) adding the corresponding initial confidence level value to the corresponding updated confidence level value to obtain a final confidence level value, (ii) storing the final confidence level value in a final confidence array, and (iii) storing the initial index number in a final decoding array;

(1) if, for each said codeword, the updated index number does not equal the initial index number and the updated and initial index numbers each represent one of said plurality of known codewords, then

(1) if the corresponding initial confidence value is greater than the updated confidence value, then storing the initial index number in said final decoding array, calculating a corresponding final confidence value by subtracting the updated confidence value from the initial confidence value, and storing the final confidence value in said final confidence array,

(2) if the corresponding updated confidence value is greater than the initial confidence value, then storing the updated index number in said final decoding array, calculating the corresponding final confidence value by subtracting the initial confidence value from the updated confidence value, and storing the final confidence value in said final confidence array, and

(3) if the corresponding initial and updated confidence values are equal, then storing a predetermined unknown index number in said final decoding array, setting the corresponding final confidence value to zero, and storing the final confidence value in said final confidence array; and

(m) if, for each said codeword, either the initial index number or the updated index number represents the predetermined unknown index number and the other index number represents one of said plurality of known index numbers, then storing the known index number and the corresponding confidence value in said final decoding array and said final confidence array, respectively.

46. The method as claimed in claim 33 wherein each said mark/space pattern comprises a fixed width pattern of marks and spaces.

47. The method as claimed in claim 46 wherein said discriminator function f(X) is a function of the widths of the individual marks making up each codeword X.

48. The method as claimed in claim 47 wherein each said mark/space pattern has four marks, and wherein:

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

where;

x_i =width of 1st mark

x₃ =width of 2nd mark

x₅ =width of 3rd mark

x₇ =width of 4th mark.

49. The method as claimed in claim 48 wherein the decoding step includes the substep of determining a scanned mark/space pattern is not a codeword if f(X) does not equal 0, 3 or 6.

50. The method as claimed in claim 46 wherein said discriminator function f(X) is a function of the widths of the individual spaces making up each codeword X.

51. The method as claimed in claim 46 wherein said discriminator function f(X) is a function of the widths of the individual marks and spaces making up each codeword X.

52. The method as claimed in claim 33 wherein each said mark/space pattern comprises a fixed width pattern of marks and spaces, and

wherein the decoding step includes the substep of determining a scanned mark/space pattern is not a codeword if at least one of the marks and spaces making up the pattern is wider than a specified width limit.

53. The method as claimed in claim 52 wherein the total width of a valid codeword is 17 basic width units, and the specified width limit is 6 basic width units.

54. The method as claimed in claim 33 wherein each said mark/space pattern comprises a fixed width pattern of marks and spaces, each said mark and space being a measured distance from one another and having a leading edge and a trailing edge, and

wherein the decoding step includes the substep of determining a scanned mark/space pattern is not a codeword if the measured distance between the leading edge of any one of the marks and the leading edge of a following mark in said pattern, or the leading edge of any one of the spaces and the leading edge of a following space in said pattern, is greater than a specified width limit.

55. The method as claimed in claim 54 wherein the total width of a valid codeword is 17 basic width units, and the specified width limit is 9 basic width units.

56. The method as claimed in claim 33 wherein a scanned mark/space pattern comprises a plurality of marks and spaces, and

wherein the decoding step includes the substep of determining each said scanned pattern is not a codeword if the scanned pattern does not comprise exactly a given number of marks and spaces.

57. The method as claimed in claim 56 wherein the total width of a valid codeword is 17 basic width units, said given number of marks and spaces being 4 marks and 4 spaces.

58. A method of reading a machine-readable symbol, the symbol including a plurality of individual codewords and at least one control word, each codeword and control word having a detectable mark/space pattern, the codewords, when taken in sequence, together defining an encoded version of data to be decoded, the mark/space pattern of each codeword having a detectable characteristic representative of information relating to a position of each said codeword within said sequence, the method comprising the steps, executed using a machine, of:

(a) scanning and reading the codewords;

(b) calculating, for each codeword X, a value of a discriminator function f(X) dependent upon the detectable characteristic;

(c) calculating a t-sequence for each said codeword X, the t-sequence being defined as a sequence of N-1 digits whose i^th digit is t_i, where N is the total number of marks and spaces in a mark/space pattern, each mark and space being a measured distance from one another and having a leading edge and a trailing edge, and t_i equals a measured distance between the leading edge of the i^th mark and the leading edge of the following mark in a mark/space pattern, or the leading edge of the i^th space and the leading edge of the following space in a mark/space pattern; and

(d) decoding each said codeword X as a function of the respective t-sequence and discriminator function f(X) and outputting a decoded version of said data.

59. The method as claimed in claim 58 wherein the decoding step includes the substep of performing a first level of decoding for each said codeword X, wherein an index number for each said codeword X is located in a first lookup table in a first memory, each said index number, for a given value of said discriminator function f(X), uniquely corresponding to the calculated t-sequence of the respective codeword X.

60. The method as claimed in claim 59 wherein the decoding step includes the substeps of:

converting each said index number into a respective high level value V_H and a respective low level value V_L, each said high level value and low level value being defined as follows;

space="preserve" listing-type="equation">V.sub.H =(index number) div m,

space="preserve" listing-type="equation">V.sub.L =(index number) mod m; and

performing, for each said codeword X, a second level of decoding, wherein for each said codeword X two predetermined consecutive values are located in a second lookup table in a second memory at addresses corresponding to V_H and V_L.

61. The method as claimed in claim 60 wherein m=30.

62. The method as claimed in claim 59 further comprising the steps of:

(e) maintaining in a second memory a plurality of lookup tables corresponding to a plurality of decoding modes;

(f) maintaining a decoding-mode variable in a third memory representative of the decoding mode currently active; and

(g) when the index value for any said codeword X, or the value of V_H or V_L of any said codeword X, corresponds to a control character specifying a new decoding mode, changing to said new decoding mode and storing in said third memory the decoding-mode variable corresponding to said new decoding mode.

63. A method of reading a machine-readable symbol, the symbol including a plurality of codewords organized into at least two adjacent rows, each codeword being a representation of an item of data, and no codeword in any one row being identical to any codeword in an adjacent row, the method including the steps, executed using a machine, of:

(a) scanning and reading said plurality of codewords within the symbol;

(b) determining whether an individual scanned codeword lies in one said row or in another adjacent row;

(c) computing an index number for said individual scanned codeword as a function of a detectable characteristic of said codeword and as a function of the result of the determining step; and

(d) processing the index number to generate a signal representative of said data item.

64. An apparatus for reading and decoding a machine readable symbol, the symbol including a plurality of individual codewords having a position within the symbol, each codeword having a detectable mark/space pattern, said codewords, when taken in sequence, defining an encoded version of data to be decoded, the apparatus comprising:

(a) means for scanning and reading the codewords;

(b) means for calculating, for each codeword X, a discriminator function f(X);

(c) means for determining the position of each codeword X in said sequence as a function of the order in which each codeword X has been read and as a function of the value of f(X);

(d) means for decoding the codewords to obtain a decoded version of said data; and

(e) means for outputting the decoded version of the data.

65. The apparatus as claimed in claim 64, including means for storing said decoded version of said data.

66. A robotic system for use in selectively moving an object having a machine-readable symbol, said robotic system including a plurality of individual codewords and at least one control word, each codeword and control word having a detectable mark/space pattern, the codewords, when taken in sequence, defining an encoded version of data to be decoded, the mark/space pattern of each codeword having a detectable characteristic representative of information relating to a position of each said codeword within said sequence, said robotic system comprising:

(a) first scanning means for scanning and reading the codewords;

(b) means for calculating, for each codeword X, a value of a discriminator function f(X) dependent upon the detectable characteristic;

(c) means for determining the position in said sequence of each codeword X as a function of the order in which each codeword X has been read and as a function of the corresponding value of said discriminator function f(X);

(d) means for decoding the codewords as a function of said determined position and for outputting a decoded version of said data;

(e) second scanning means for generating a signal as a function of the decoded version of said data; and

(f) means for manipulating said object in response to said signal.

67. An apparatus for generating a signal representative of information encoded in a machine-readable symbol, the symbol including at least two adjacent rows of codewords, each codeword representing an item of data and being selected from a set of detectable mark/space patterns, each said mark/space pattern having a determinable discriminator function, the apparatus comprising:

(a) scanning means for scanning the codewords within the symbol;

(b) means for computing the discriminator function for each of said scanned codewords;

(c) means for determining, from the values of the computed discriminator functions corresponding to each of said scanned codewords, the row of the symbol in which each of said scanned codewords lies;

(d) means for decoding said scanned codewords as a function of the determined row for each of said scanned codewords to obtain a plurality of corresponding symbolic values; and

(e) means for generating a plurality of signals representative of said symbolic values.

68. The apparatus as claimed in claim 67 having means for storing a plurality of stored values representative of said symbolic values.

69. Apparatus for retrieving information by scanning indicia on the surface of a substrate, the indicia including a plurality of codewords organized into at least two adjacent rows, each codeword being either an information codeword or a control codeword, each information codeword being representative of at least one information-containing data structure, and no codeword in any one row being identical to any codeword in an adjacent row, the apparatus comprising:

(a) scanning means for scanning said plurality of codewords within the indicia;

(b) means for determining whether an individual scanned codeword is an information codeword or a control codeword;

(c) means for storing a plurality of different protocols each associating a scanned information codeword with a corresponding data structure, only one protocol being active at any given time;

(d) means, coupled to the determining means, for decoding said individual scanned codeword according to the currently active protocol, if the scanned codeword is an information codeword; and

(e) means, coupled to the determining means, for processing said individual scanned codeword and, if said individual scanned codeword is a control codeword, for decoding a symbol representative of a new protocol and for changing the currently active protocol to said new protocol.

70. A method for storing and retrieving information by scanning indicia on the surface of a substrate, said indicia including a plurality of codewords scanned sequentially and organized into at least two adjacent rows, each codeword being either an information codeword or a control codeword, each information codeword being a representation of at least one information-containing data structure, no codeword in any one row being identical to any codeword in an adjacent row, the method including the steps of:

(a) storing information by applying said indicia to said substrate; and

(b) retrieving said information, the retrieving step including the substeps of;

(1) scanning said indicia to detect said information and control codewords,

(2) determining whether each of said scanned codewords is an information codeword or a control codeword,

(3) providing a plurality of different protocols each associating each codeword with a corresponding data structure, only one protocol being active at any given time,

(4) if any of said scanned codewords is an information codeword as determined in said determining step, then decoding and outputting each of said scanned information codewords according to the active protocol, and

(5) if any of said scanned codewords is a control codeword as determined in said determining step, then processing each of said scanned control codewords to decode a symbol representative of a new protocol, and changing the active protocol to the new protocol.