Error and loss correction in a data base stored on a two dimensional medium and method

• US 5,479,418 A
• Filed: 07/10/1992
• Issued: 12/26/1995
• Est. Priority Date: 07/10/1992
• Status: Expired due to Term

• Current Assignee: Canon Inc.
• Original Assignee: Canon Inc.
• Inventors: Hughes-Hartogs, Dirk
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): BROWN, THOMAS
• Application Number:
  US07/911,695
• Time in Patent Office: 1,264 Days
• Field of Search: 371/38.1, 371/39.1, 371/40.1-40.4, 371/37.3, 371/37.1, 371/37.4, 371/37.5
• US Class Current: 714/755
• CPC Class Codes: G06K 19/06037 multi-dimensional coding
• CPC Class Codes: G06K 19/06075 the marking containing means for error correction

Abstract

A digital data base 10 having record data codes representing an initial digital record is printed at predetermined code sites 12 within two dimensional code storage area 14 on the surface of on base medium 10B. The digital data base includes redundant check codes and one or more redundant check-check codes for permitting data error and data loss correction. The two dimensional code storage area has a coordinate system for defining code positions therein. The code sites are physically positioned within the code storage area at predetermined coordinates. A plurality of error checking sets are formed by the code sites, each containing one or more data codes and one or more check codes. The bits in the check codes in each error checking set are determined by the bits in the data codes of the same error checking set, and are in error correcting relationship therewith. Each data code and each check code are included in "L" error checking sets to provide "L" levels of inter-locking error checking and correcting. In addition, a of plurality error checking-checking sets are also formed by the code sites. Each error checking-checking set contains one or more check codes and one or more check-check codes in error correcting relationship therewith. Each check code and each check-check code are also included in "L" error checking-checking.

Claims

1. A digital data base having record data codes representing an initial digital record, and having redundant check codes and one or more redundant check-check codes, comprising:

a base medium

a two dimensional code storage area on the surface of the base medium having a coordinate system for defining positions therein;

code sites physically positioned within the code storage area at predetermined coordinates for containing the record data codes and the redundant check codes and the redundant check-check codes, and having code bit states defined by the presence or absence of toner material deposited on the base medium;

a plurality of error checking sets formed by the code sites, each error checking set containing one or more data codes and one or more check codes, the bits in the check codes in each error checking set determined by the bits in the data codes of the same error checking set and in error correcting relationship therewith, each data code site and each check code site are included in "L" error checking sets to provide "L" levels of inter-locking error checking; and

a plurality of error checking-checking sets formed by the code sites, each error checking-checking set containing one or more check codes and one or more check-check codes, the bits in the check-check codes in the error checking-checking set determined by the bits in the check codes thereof and in error correcting relationship therewith.

2. The digital data base of claim 1, wherein each check code site and each check-check code site are included in "L" error checking-checking sets to provide "L" levels of inter-locking error checking-checking.

3. The digital data base of claim 1, wherein each code site within the code storage area is positioned along a row axis and along a column axis forming a pattern of intersecting rows and columns having "R" rows and "C" columns, and the coordinate system for defining the position of each code site is a row and column coordinate system.

4. The digital data base of claim 3, wherein the number or rows "R" is equal to the number of columns "C".

5. The digital data base of claim 3, wherein the number or rows "R" and the number of columns "C" do not have a common divisor.

6. The digital data base of claim 3, wherein each of the error checking sets is contained along a row or column forming (R-1) row error checking sets and (C-1) column error checking sets, and each of the error checking-checking sets is contained along a row or column forming one row error checking-checking set and one column error checking-checking set.

7. The digital data base of claim 6, wherein each of the R-1 error checking sets has C code sites containing C-1 data codes and one check code, and each of the C-1 column error checking sets has R code sites containing R-1 data codes and one check code, and the one row error checking-checking set has C sites containing (C-1) check codes plus one check-check code, and the one column error checking-checking set has R sites containing (R-1) check codes plus one check-check code.

8. The digital data base of claim 7, wherein"L" =2, and each data code and each check code are included in one row checking set and in one intersecting column checking set, and each check code and each check-check code are included in one row checking-checking set and in one intersecting column checking-checking set.

9. The digital data base of claim 8, wherein each of the data codes occupies a code site at the intersection of a row and column, and is in error correcting relationship with the C-2 other data codes plus the one check code along that row, and is also in error correcting relationship with the R-2 other data codes plus the one check code along that column.

10. The digital data base of claim 9, wherein each of the check codes occupies a code site at the intersection of a row and column, and is in error correcting relationship with the C-2 other check codes plus one check-check code along that row, and is also in error correcting relationship with the R-2 other check codes plus one check-check code along that column.

11. The digital data base of claim 7, wherein the (C-1) row data code sites with one check code site are positioned along an exterior row along the edge of the code storage area, and the (R-1) column data code sites with one check code site are positioned along an exterior column along the edge of the code storage area, and the one code check-check site is positioned at the intersection site at a corner of the code storage area between the exterior row and the exterior column.

12. The digital data base of claim 7, wherein the (C-1) row check code sites with one check-check code site are positioned along an interior row within the code storage area, and the (R-1) column check code sites with one check-check code site are positioned along an interior column within the code storage area, and the one code check-check site is positioned at the intersection site within the code storage area between the interior row and the interior column.

13. The digital data base of claim 1, wherein the record data codes are arranged within the code storage area generally in the sequence of the initial record represented by the record data codes for providing record continuity between the record data codes within the code storage area and the record.

14. The digital data base of claim 1, wherein the record data codes are arranged within the code storage area are permuted generally out of the sequence of the initial record represented by the record data codes for reducing the record continuity between the record data codes within the code storage area and the record.

15. The digital data base of claim 14, further comprising key data for defining the permuting of the initial record.

16. The digital data base of claim 1, wherein the digital format of the codes is binary based having two code states per bit, one state represented by the presence of toner material and the other state represented by the absence of toner material.

17. The digital data base of claim 1, wherein the digital format of the codes is multinary based having M code states per bit.

18. The digital data base of claim 17, wherein the toner material is a single color and the deposition thereof is in greyscale and the M code states per bit are determined by the intensity of toner material deposited.

19. The digital data base of claim 17, wherein the toner material has M colors and the M code states per bit are determined by the selection of the toner material deposited to form each bit.

20. A method of storing and retrieving and correcting a digital data base having record data codes representing an initial digital record, and having redundant check codes and one or more redundant check-check codes, said method comprising the steps of:

providing a base medium comprising on the surface a two dimensional code storage area having a coordinate system for defining positions therein and carrying the codes of the digital data base by printing the data codes, the redundant check codes, and the redundant check-check codes at code sites in which code bit states are defined by the presence or absence of toner material deposited on the base medium and the code sites are physically positioned within the code storage area at predetermined coordinates, wherein a plurality of error checking sets are formed by the code sites, each error checking set containing one or more data codes and one or more check codes, the bits in the check codes in each error checking set are determined by the bits in the data codes of the same error checking set and are in error correcting relationship therewith, each data code site and each check code site are included in "L" error checking sets to provide "L" levels of inter-locking error checkings and a plurality of error checking-checking sets are formed by the code sites, each error checking-checking set containing one or more check cedes and one or more check-check codes, the bits in the check-check codes in each error checking-checking set are determined by the bits in the check codes thereof and are in error correcting relationship therewith;

retrieving the codes from the base medium into a retrieval memory;

examining the retrieved codes in each of the error checking sets to locate errors revealed by inconsistencies in the error correcting relationships within each error checking set and between the "L" inter-locked error checking sets;

correcting the errors in the codes of the error checking sets if any errors exist; and

iterating the examining and correcting steps until a predetermined error condition has been established in the digital data base.

21. The method of claim 20, wherein the examining and correcting steps are iterated until all of the errors have been corrected.

22. The method of claim 20, wherein the examining and correcting steps are iterated until no changes appear in the iterated codes.

23. The method of claim 20, wherein the examining and correcting steps are iterated a maximum of Imax times.

24. The method of claim 20, wherein the examining and correcting steps are iterated until the number of errors "E" in the iterated codes is less than a predetermined value.

25. The method of claim 20, comprising the further step of printing the iterated data base onto another base medium.

26. The method of claim 20, wherein the sets of error check codes extend in rows and columns within an addressable matrix in the retrieval memory, and the examining step proceeds along the rows and columns by incrementing the access address of the retrieval memory.

27. The method of claim 20, wherein, prior to the step of providing the base medium, said method comprises the further step of providing an initial data base of the digital record in an initial memory.

28. The method of claim 27, in which, prior to the step of providing the base medium, said method comprises the further step of permuting the sequence of the initial data.

29. The method of claim 28, wherein the step of permuting the sequence of the initial data reduces the record continuity of the initial data base as printed on the base medium.

30. The method of claim 29, wherein the step of permuting the initial data is performed using a standard permutation key.

31. The method of claim 28, in which after the step of retrieving, comprises the further step of inverse permuting the sequence of the iterated data in the retrieval memory to restore the sequence of the initial data.

32. The method of claim 31, wherein the step of inverse permuting the sequence of the iterated data distributes storage impairments throughout the printed data base.