Error correction for PDF417 and other machine-readable symbologies
First Claim
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 Assignments
0 Petitions
Accused Products
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 i1 (consisting of all integers from 0 to 28 inclusive) and a second set of index values i2 (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 i1 +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 i1.
-
Citations
21 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
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 i1 +29*r counting modulo 32, with i1 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
- space="preserve" listing-type="tabular">__________________________________________________________________________0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31. __________________________________________________________________________
-
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.
-
-
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. - View Dependent Claims (9, 10)
-
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.
-
9. The apparatus of claim 8 wherein the first matrix inversion is performed in accordance with the Berlekamp-Massey 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. - View Dependent Claims (12, 13, 14, 15, 16, 17)
-
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 i1 +29*r counting modulo 32, with i1 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
- space="preserve" listing-type="tabular">__________________________________________________________________________0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31 28 25 22 19 16 13 10 7 4 1 30 28 25 22 19 16 13 10 7 4 1 30 27 24 21 18 15 12 9 6 3 0 29 26 23 20 17 14 11 8 5 2 31. __________________________________________________________________________
-
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.
-
-
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. - View Dependent Claims (19, 20)
-
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.
-
19. The method of claim 18 wherein the first matrix inversion is performed in accordance with the Berlekamp-Massey 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.
-
Specification
- Resources
-
Current AssigneeIntermec IP Corporation (Honeywell International Inc.)
-
Original AssigneeIntermec Technologies Corporation (Honeywell International Inc.)
-
InventorsMaltsev, Pavel A.
-
Primary Examiner(s)Baker, Stephen M.
-
Application NumberUS08/679,657Time in Patent Office690 DaysField of Search235/437, 235/462, 371/37.01, 371/37.11US Class Current714/752CPC Class CodesG06K 19/06018 one-dimensional codingG06K 7/14 using light without selecti...G06K 7/1473 error correctionH03M 13/00 Coding, decoding or code co...H03M 13/151 using error location or err...