Error correction for PDF417 and other machine-readable symbologies

• US 5,761,219 A
• Filed: 07/12/1996
• Issued: 06/02/1998
• Est. Priority Date: 07/12/1996
• Status: Expired due to Fees

• Current Assignee: Intermec IP Corporation (Honeywell International Inc.)
• Original Assignee: Intermec Technologies Corporation (Honeywell International Inc.)
• Inventors: Maltsev, Pavel A.
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US08/679,657
• Time in Patent Office: 690 Days
• Field of Search: 235/437, 235/462, 371/37.01, 371/37.11
• US Class Current: 714/752
• CPC Class Codes: G06K 19/06018 one-dimensional coding
• CPC Class Codes: G06K 7/14 using light without selection of wavelength, e.g. sensing reflected white light G06K7/10831 - G06K7/1097 take precedence
• CPC Class Codes: G06K 7/1473 error correction
• CPC Class Codes: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials

Abstract

A method and apparatus is described which provides improved error correction for reading a PDF417 or other machine-readable symbol having a data region with symbol characters representing encoded data. A processor receives the encoded data read from the PDF417 symbol and executes an error correction routine. The error correction routine includes a two dimensional discrete Fourier transform with a reduced number of arithmetic operations. The transform is a variant of the Good-Thomas FFT performed over the Galois field GF(929), and includes a set of first index values i₁ (consisting of all integers from 0 to 28 inclusive) and a second set of index values i₂ (consisting of all integers from 0 to 31 inclusive). For a given first index value, the transform is performed only over a subset of the second index values. The subset of second index values is the first k values of a sequence given by i₁ +29*r, where r=0, 1, 2, . . . , 31, and k is the minimum of values 31 and b/29!+1. The value b is the number of symbol characters in the data region of the PDF417, and b/29! is the least integer function of the quotient b/29. It is particularly advantageous to collect in a single table each of the sequences corresponding to a particular value of i₁.

Claims

1. An apparatus for reading a machine-readable symbol having a data region with symbol characters, the symbol characters including information symbol characters and error correction symbol characters, the apparatus comprising:

a sensor receiving light reflected by the symbol and responsively producing an output signal;

a converter receiving the output signal and responsively producing a data signal indicative of at least some of the symbol characters; and

a processor receiving the data signal and responsively producing an information signal indicative of the information symbol characters, the processor being programmed to perform an error correction routine including a discrete Fourier transform of the data signal, the Fourier transform having a first dimension characterized by a set of first index values and a second dimension characterized by a set of second index values, the Fourier transform being performed over a subset of the second index values, the subset being determined as a function of a given first index value and the number of symbol characters.

2. The apparatus of claim 1 wherein the subset of the second index values consists of specified ones of a sequence of values, the sequence being a function of a given first index value and the specified ones of the sequence being a function of the number of symbol characters.

3. The apparatus of claim 1 wherein the number of symbol characters cannot exceed 928 and the Fourier transform is performed over the Galois field GF(929), and wherein the subset of the second index values consists of specified ones of a sequence of values, the sequence being given by the relation i₁ +29*r counting modulo 32, with i₁ representing the first index value and r representing a sequence index ranging from integers 0 to 31 inclusive, and where the specified ones of the sequence are a first k members of the sequence, k being a minimum one of values 31 and b/29!+1, with b/29! representing the greatest integer less than or equal to a ratio b/29, where b is the number of symbol characters.

4. The apparatus of claim 1 wherein the function of a given first index value and the number of symbol characters is provided as a table of values accessible by the processor.

5. The apparatus of claim 1 wherein the number of symbol characters cannot exceed 928 and the Fourier transform is performed over the Galois field GF(929).

6. The apparatus of claim 1 wherein the number of symbol characters cannot exceed 928, the set of first index values is the set of all integers from 0 to 28 inclusive, the set of second index values is the set of all integers from 0 to 31 inclusive, and the subset of second index values is obtained from a table arranged in 29 rows and 32 columns, the subset of second index values listed at particular column locations in a row corresponding to the given first index value, the particular column locations corresponding to the number of symbol characters.

7. The apparatus of claim 6 wherein the table is algebraically equivalent to

8. An apparatus for reading a machine-readable symbol having a data region with symbol characters, the symbol characters including information symbol characters and error correction symbol characters, the apparatus comprising:

a sensor receiving light reflected by the symbol and responsively producing an output signal;

a converter receiving the output signal and responsively producing an encoded data signal indicative of the symbol characters; and

a processor receiving the encoded data signal and being programmed to perform an error correction routine including the steps of;

(i) calculating a spectrum polynomial by discrete Fourier transform of the encoded data signal, the Fourier transform having a first dimension characterized by a set of first index values and a second dimension characterized by a set of second index values, the Fourier transform being performed over a subset of the second index values, the subset being determined as a function of a given first index value and the number of symbol characters;

(ii) calculating a convolution of the spectrum polynomial with an erasure location polynomial constructed from the encoded data signal;

(iii) calculating a first matrix inversion to obtain an error location polynomial;

(iv) combining the error location polynomial and erasure location polynomials;

(v) calculating a second matrix inversion to obtain a plurality of error magnitudes; and

(vi) combining the error magnitudes with the encoded data signal to produce an information signal indicative of the information symbol characters.

9. The apparatus of claim 8 wherein the first matrix inversion is performed in accordance with the Berlekamp-Massey algorithm.

10. The apparatus of claim 8 wherein the second matrix inversion is performed in accordance with the Forney algorithm.

11. A method for reading a machine-readable symbol having a data region with symbol characters, the symbol characters including information symbol characters and error correction symbol characters, the method comprising the steps of:

receiving light reflected by the symbol;

producing a data signal indicative of at least some of the symbol characters;

performing an error correction routine including a discrete Fourier transform of the data signal, the transform having a first dimension characterized by a set of first index values and a second dimension characterized by a set of second index values, the Fourier transform being performed over a subset of the second index values, the subset being determined as a function of a given first index value and the number of symbol characters; and

producing an information signal indicative of information encoded in the information symbol characters.

12. The method of claim 11 wherein the subset of the second index values consists of specified ones of a sequence of values, the sequence being a function of a given first index value and the specified ones of the sequence being a function of the number of symbol characters.

13. The method of claim 11 wherein the number of symbol characters cannot exceed 928 and the Fourier transform is performed over the Galois field GF(929), and wherein the subset of the second index values consists of specified ones of a sequence of values, the sequence being given by the relation i₁ +29*r counting modulo 32, with i₁ representing the first index value and r representing a sequence index ranging from integers 0 to 31 inclusive, and where the specified ones of the sequence are a first k members of the sequence, k being a minimum one of values 31 and b/29!+1, with b/29! representing the greatest integer less than or equal to a ratio b/29, where b is the number of symbol characters.

14. The method of claim 11 wherein the function of a given first index value and the number of symbol characters is provided as a table of values.

15. The method of claim 11 wherein the number of symbol characters cannot exceed 928 and the Fourier transform is performed over the Galois field GF(929).

16. The method of claim 11 wherein the number of symbol characters cannot exceed 928, the set of first index values is the set of all integers from 0 to 28 inclusive, the set of second index values is the set of all integers from 0 to 31 inclusive, and the subset of second index values is obtained from a table arranged in 29 rows and 32 columns, the subset of second index values listed at particular column locations in a row corresponding to the given first index value, the particular column locations corresponding to the number of symbol characters.

17. The method of claim 16 wherein the table is algebraically equivalent to

18. A method for reading a machine-readable symbol having a data region with symbol characters, the symbol characters including information symbol characters and error correction symbol characters, the method comprising the steps of:

receiving light reflected by the symbol;

producing an encoded data signal indicative of the symbol characters;

performing an error correction routine including;

(i) calculating a spectrum polynomial by discrete Fourier transform of the encoded data signal, the Fourier transform having a first dimension characterized by a set of first index values and a second dimension characterized by a set of second index values, the Fourier transform being performed over a subset of the second index values, the subset being determined as a function of a given first index value and the number of symbol characters;

(ii) calculating a convolution of the spectrum polynomial with an erasure location polynomial constructed from the encoded data signal;

(iii) calculating a first matrix inversion to obtain an error location polynomial;

(iv) combining the error location polynomial and erasure location polynomials;

(v) calculating a second matrix inversion to obtain a plurality of error magnitudes; and

(vi) combining the error magnitudes with the encoded data signal to produce an information signal indicative of the information symbol characters.

19. The method of claim 18 wherein the first matrix inversion is performed in accordance with the Berlekamp-Massey algorithm.

20. The method of claim 18 wherein the second matrix inversion is performed in accordance with the Forney algorithm.

21. A method for reading a machine-readable symbol having a data region with symbol characters, the symbol characters including information symbol characters and error correction symbol characters, the method comprising the steps of:

determining the maximnum possible number of symbol characters in the data region of the symbol;

receiving light reflected by the symbol;

producing an encoded data signal indicative of the symbol characters; and

performing an error correction routine including;

(i) determining the actual number of symbol characters in the data region of the symbol; and

(ii) determining the number of arithmetic computations required to calculate a plurality of spectral coefficients corresponding to the encoded data signal, the number of arithmetic computations being functionally related both to the maximnum number of symbol characters and the actual number of symbol characters.