Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-01-10
2003-08-05
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S761000
Reexamination Certificate
active
06604218
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an apparatus for encoding data when data are stored as an image in a specific two-dimensional region, such as a two-dimensional code, and an apparatus for decoding the stored encoded data.
2. Description of the Prior Art
Bar code-based control systems are widely used in such fields as commodity distribution and parts management at industrial plants. Recent progress in image processing technology and increased availability of charge coupled device (CCD) cameras have promoted development and application of two-dimensional bar codes because of the advantage over the one-dimensional bar codes in information storage capacity.
Appropriate utilization of the large information storage capacity provided by such two-dimensional codes is generally effected by addition of an error-correcting function to protect against noises that could damage or break bit data within the two-dimensional code. Such a function is provided for in the “two-dimensional code technical specification AIMJ-TC-3-1” issued by AIM Japan. The two-dimensional code called the QR code described in the specification has a function of correcting reading errors of bit data caused by such a noise as a stain resting on the two-dimensional code. The error-correcting function is created by adding bit data for error correction through application of either the Reed-Solomon code or the Hamming code.
That function of correcting a reading error of bit data is different in efficiency depending on the encoding mode applied, that is, the noise pattern. There are different noise patterns. One encoding mode is effective against some noise patterns but does not work well on others. To be specific, the Reed-Solomon code mode is effective in correcting burst errors while the Hamming code mode is suitable for correcting random errors. In addition, there are such code modes as the extended Hamming code and BCH (Bose/Chaudhuri/Hocquengen) code, which are effective in dealing with random errors, and the eraser code and adjacency code, which are useful for correction of burst errors.
The problem with the prior art data encoding and data decoding apparatuses is that they can fail to correct some errors caused by linear noises which are liable to appear in the longitudinal direction when a two-dimensional image is printed or by linear noises which are often observed in the latitudinal direction when media such as paper on which a two-dimensional image is printed is bent.
In the Reed-Solomon code mode, bit data is divided into a number of blocks Bo-Bj. Parity blocks Bpo-Bpj are added to those blocks Bo-Bj to provide a function of correcting burst errors—for block-wise correction, as shown in FIG.
20
.
However, the number of correctable blocks is limited. The error-correcting function can not work on linear noises extending over a plurality of blocks exceeding that limit.
In the Hamming code mode, also, bit data is divided into a plurality of fields of sets Qo-Qk to which error-correcting bits Qpo-Qpk are added to produce a function of correcting random errors—a function of correcting the respective bits making up a set, as shown in FIG.
21
.
However, there is a limit to the number of correctable bits in a set. It is impossible to correct errors involving a number of bits exceeding that limit, for example, errors caused by a linear noise in the longitudinal direction in the aforesaid sets.
Another problem with the prior art data encoding and data decoding apparatuses is that they can not select an error correcting code mode in such a way as to minimize the decoding time to beat those frequent noises.
SUMMARY OF THE INVENTION
The present invention is to solve those problems. Accordingly, it is an object of the present invention to provide a data encoding apparatus which encodes bit data using two error-correcting modes—the random error correcting code mode and the burst error correcting code mode—and such a data decoding apparatus. It is another object of the present invention to ensure that the error-correcting function will work without fail, whichever linear noise, longitudinal or latitudinal, may be involved and to minimize the decoding time including the error-correcting time by changing (after mentioned) bit data relocation maps according to the direction of the linear noise liable to get on the two-dimensional image.
To effect those objects, the present invention is built up on the following means.
That is, the data encoding apparatus according to the present invention is characterized in that bit data are encoded using at least one kind of error-correcting code in each of two the error-correcting modes—the random error correcting mode and the burst error correcting mode and that the encoded bit data are then arranged in a matrix in a specific two-dimensional region to produce and print a two-dimensional image on a medium.
In this case, the following alternative is possible: the encoded bit data is relocated on the basis of a relocation map. When that encoded bit data is relocated in a specific two-dimensional region on the basis of the relocation map, the set of bit data to which the random error-correcting code is added is arranged or relocated linearly in the specific two-dimensional region in one direction, that is, either in columns or in rows.
The following arrangement is also suitable. That is, there are provided relocation map holding means holding a plurality of relocation maps as described above and relocation map specifying means that selects a relocation map to be used by the aforesaid relocation means. This relocation map specifying means selects the relocation map in which the direction of the most frequent bit error and the longitudinal direction of the set of the aforesaid bit data cross each other.
Meanwhile, the data encoding apparatus of the present invention is characterized in that it is provided with two-dimensional image reading means which reads in a two-dimensional image printed on the medium and converts the same into electronic data or bit data in the data encoding apparatus according to the present invention. The inventive apparatus is also provided with random error correcting means which corrects errors and decodes in sets of those converted bit data given an addition of the random error correcting code and burst error correcting means which corrects errors and does decoding in sets of those converted bit data given an addition of the burst error correcting code.
In this case, it is possible to provide map location restoring means behind the aforesaid two-dimensional image reading means—map location storing means that converts the aforesaid read two-dimensional image such as two-dimensional code into bit data before the rearrangement on the basis of the above-mentioned relocation map.
In the data encoding apparatus and the data decoding apparatus of the present invention, the aforesaid burst error correcting code will act on noises in the longitudinal direction of the random encoded bit data. Noises that extend over a plurality of blocks of burst encoded bit data are dealt with by the above-mentioned random error correcting code. Therefore, noises in any direction in a two-dimensional image will be picked up by the error correcting function without fail. Furthermore, use of a plurality of error correcting codes—random error correcting code and burst error correcting code—could correct errors caused by noises more complicated in shape.
It is also possible to minimize the decoding time including the error correcting time the following way. A relocation map of bit data is prepared in accordance with the direction of the aforesaid noise. Or the relocation map is changed depending on in which direction the linear noise lies that is liable to appear on the two-dimensional image. The change is effected in such a way that the direction of the bit data block and the noise direction cross each other. That way, priority is given to the random error correcting code mode that is quick in correcting errors, thereby minimizing the decodin
Hisatomi Kenji
Kuwano Hideyuki
Okada Yuji
Takahashi Naoki
Tanaka Joji
De'cady Albert
McDermott & Will & Emery
Torres Joseph D.
LandOfFree
Data encoding apparatus and data decoding apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data encoding apparatus and data decoding apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data encoding apparatus and data decoding apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3104140