Data Processing System With Error Correction

The present invention relates to the error processing of a data error which occurs in the recording or playing back of picture data and code data onto and from an optical disk in a picture data record/playback system for recording picture data on a document; e.g., for recording picture data onto an optical disk and playing it back therefrom, as required.

In recent years, a tremendous amount of documents have been produced, in offices and factories, for example. For the electronic processing of such documents, a picture data record/playback system has been developed. In this system, the picture data on a document is optically read out by a two dimensional scanning method. The picture data thus read out is sequentially stored in a recording medium, such as an optical disk. The retrieval data for individual picture data is stored in a recording medium, such as a floppy disk. In reading out the desired picture data from the optical disk, a retrieval code associated with the desired picture data is input into the system. The data read out is visualized by a CRT device or a printer.

This type system is defective, however, in that the optical disk used is physically damaged by dust particles attached thereto or being deposited thereon when it is handled. When damaged, the damaged optical disk incorrectly plays back the picture data from a damaged portion of the optical disk.

Generally, the picture data has high redundancy. Accordingly, the picture data may be recorded on the optical disk, allowing for the errors contained therein, to some extent. Code data such as character text and retrieval words has a much lower quantity than picture data. Therefore, for the code data, the probability of the error occurrence must be extremely low. As for the data amount of both the picture data and the code data, one page of a document of A4 size needs a memory capacity of approximately 600 KB in case that the picture data in the one page document is treated as binary picture with a 0.1 mm resolution. A character test (in Japanese) having picture data of 60 characters.times.50 lines on one page of an A4 size document may be expressed by 6 kilo bytes (5 KB), at most.

Errors contained in two types of data with different error tolerances must be appropriately processed. In so far as we know, however, data processors with such error correction ability have not yet been developed.

Accordingly, a primary object of the present invention is to provide a data processing system which can perform error correction on two types of data having different error tolerances, with a high degree of accuracy.

To achieve the above object, a data processing system is provided which handles a large amount of primary data allowing error occurrence at a low frequency level, and a small amount of secondary data allowing error occurrence at a very low frequency level, which system has a memory device with a large capacity for storing the primary and secondary type data at an insufficiently low error frequency; said data processing system being comprised of: first error correction means for correcting errors in the primary and secondary data, so that the primary and secondary data is set within its tolerable error ranges when the primary and secondary data is read out from or written into the memory with a large capacity; and secondary correction means for correcting the errors in the secondary data, so that the primary and secondary data is set within a tolerable error range, in order to apply two stages of error correction to the secondary data.

Other objects and features of the present invention will be apparent from the descriptions of the accompanying drawings summarized below:

FIG. 1 is a block diagram illustrating an overall data processing system which is an embodiment of the present invention;

FIG. 2 is a plan view of an optical disk;

FIGS. 3A and 3B are block diagrams schematically illustrating a compander circuit;

FIGS. 4 and 5 are block diagrams of an example of an encoding circuit;

FIGS. 6 and 7 schematically illustrate an example of an encoding circuit;

FIG. 8 shows a record format for 31-bit interleaving;

FIG. 9 illustrates a format of a read/write data unit for an application program;

FIG. 10 shows an example of a data format used in a driver routine;

FIG. 11 is a memory map of a program executed by the CPU;

FIG. 12 is a flowchart illustrating the control flow of a write operation;

FIG. 13 is a flowchart illustrating the control flow of a read operation;

FIG. 14 shows a format for doubling the code data; and

FIG. 15 is a block diagram of an optical disk unit adaptor of another embodiment of a data processing system according to the present invention.

One embodiment of a picture data record/playback system according to the present invention may be described as follows, with reference to the accompanying drawings.

FIG. 1 shows the scheme of a picture data record/playback system according to the present invention. In this system, reference numeral 11 designates a main control unit. A CPU 12 executes various types of controls in this system. Numeral 13 designates a main memory. A buffer memory 14, e.g., a page buffer, has a memory capacity capable of storing picture data of at least one unit (with the data amount corresponding to 2304 lines of one page of an A4 size document). A compander 15 compresses the picture data (lessens the redundancy of the picture data) and expands the picture data (restores the compressed redundancy to the original state). A pattern generator 16 stores pattern data such as characters and symbols. Numeral 17 represents a display interface. A title memory 13 stores retrieval data read out from a keyboard 23 to be given later. A read device or a two-dimensional scanner 20 two-dimensionally scans an original (document) 21 by a laser beam to produce electrical signals representing the picture data on the original 21. An optical disk unit 22 is used for sequentially storing in a data recording medium 19, such as an optical disk, picture data read out by the two-dimensional scanner 20 and supplied through the main control unit 11. An optical disk unit adaptor 26 contains a DMA 29 and a CRC computing circuit 30. A 8257 Programmable DMA Controller, manufactured by Intel Corp. in USA, may be used as the DMA 29. A MC8503 UNIVERSAL POLYNOMIAL GENERATOR, manufactured by Motorola Inc. in USA may be used for the CRC computing circuit 30. Since the data transfer speed of the floppy disk unit 27 is high, the computation of the CRC is executed by the hardware 30.

As shown in FIG. 2, the surface of a circular substrate made of, e.g., glass or plastic, has a metal layer laid thereon in a spiral fashion, which substrate is made of tellurium or plastic, for example. A cut away portion, i.e., a reference position mark 19.sub.1, is formed near the center of the metal layer. The disk surface is divided into 32 sectors 0 to 31, with sector 0 serving as the reference position mark 19.sub.1. Further, the track number 1 and the succeeding ones are assigned to the spiral grooves on the optical disk 19, from the inside to the outside, respectively.

A keyboard 23 is employed in keying in the specific retrieval codes associated with the picture data and various types of operation codes. An output unit 24, for example, a CRT unit as a display unit, displays the picture data which is read out by the two-dimensional scanner 20 and supplied through the main control unit 11. The CRT unit and the display interface 17 in the main control unit 11 cooperate to form a picture data display device. A recorder 25 produces, in the form of a hard-copy, the picture data which is read out by the two-dimensional scanner 20 and supplied through the main control unit 11, or the picture data read out from the optical disk unit 22 and supplied through the main control unit 11. A floppy disk unit 27 stores the retrieval data in a floppy disk 28.

The compander 15 has the arrangement shown in FIG. 3. In a compression mode, the compander 15 is comprised of a line buffer 31 with one scanning line; a buffer memory of exactly 1728 bits; a compressor 32 (MH conversion); an EOL generator 33 for generating an end of line code (EOL) of 13 bits, which represents the end of one scanning line; a CRC generator 34 for generating a cyclic redundancy check code of 4 bits as a second check code, for every picture image of one scanning line; and a summing circuit 35 for summing the EOL and CRC codes at the end of one scanning line, for every item of conversion picture data of one scanning line. In this connection, the CRC code is the remainder when the picture data of one scanning line is divided by a generator (X.sup.4 +X+1). In an expansion mode, the compander 15 is composed of the line buffer 31; the expander 36 (MH reverse conversion); an EOL detector 37 for detecting an EOL added to the converted picture; a counter 38 for counting the results of detection by the EOL detector 37; and a judging circuit 39 for judging whether or not the number of lines of the converted picture has reached a predetermined number of lines, e.g., 2297 lines, by the count of the counter 33.

The error correction of the FIG. 1 system is classified into a first error correction and a second error correction. The first error correction is performed in the optical disk unit 22. An error bit rate is reduced from approximately 10.sup.-4 to 10.sup.-8 by the optical disk unit 22. Data is recorded on the optical disk 19 in an array of pits with 2 .mu.m/bit intervals. Therefore, even with dust particles having a diameter of 20 .mu.m, burst errors of 10 bits are caused. Most of the errors to be corrected are caused by dust particles with a diameter of 20 .mu.m or less. The occurrence rate of dust particles of 20 .mu.m or more among existing dust particles is generally from 10.sup.-6 to 10.sup.-7.

Allowing for the nature of the errors, the first error correction means employs a Bose-Chaudhuri-Hocquenghen code (BCH code), in which 10 check bits are used for data of 21 bits. The BCH code has the highest correction capacity among the known random error correction codes, and has versatility in its application. Further, this coding system may be considered an extension of the known Hamming code.

In the Hamming code, the mth degree primitive polynomial is treated as a generator, a code length n is equal to 2.sup.M -1 (i.e., n=2.sup.M -1), and a single error in the data bit may be corrected by a code of k=2.sup.m -1-m. A parity check matrix H is expressed as follows:

where .alpha. is M1(x), which is an irreducible polynomial of the m-th degree on a Galois field GF(2) having a root of the primitive element of a Galois field GF(2.sup.m). In a multiplicative group G, if the elements belonging to the multiplicative group G are all expressed by the power of an element Q in the multiplicative group G, the G is called a cyclic group and the Q is called a primitive element. Hence, the BCH code constitutes a cyclic group. To extend the Hamming code into a BCH code, in correcting double errors, the number of roots satisfying a code polynomial is increased. Another root .alpha..sup.2 of the may be provided as the root of M1(x1), being coincident with the Hamming code.

Let us consider a code having roots of .alpha. and .alpha..sup.3. Let the minimum polynomials of the roots be M1(x) and M3(x), respectively. Under such conditions, this code is composed of a generator and parity check matrix h, as given below.

where S.sub.0 and S.sub.1 are values calculated from the upper and lower halves of the syndrome. If the remainder of the syndrome S is 0, no error is detected. This state either indicates that no error occurs or that error detection is impossible. If the remainder is not zero, it may be judged that an error has occurred.

As indicated above, the syndrome is the superposition of the syndrome values by a single error. Error correction may be performed by solving equation (6).

An encode/decode circuit based on the BCH code is basically composed of shift registers 41 and an adder 42, as shown in FIG. 4. A BCH (31, 21) code has, in the form of a generator, the product G(x) of minimum polynomials M1(x) and M3(x), with the roots of elements .alpha. and .alpha..sup.3 of the Galois field GF (2.sup.5).

The parity check matrix may be expressed as follows: ##EQU3## where .alpha..sup.3 is a vector of the 5th dimension and ##EQU4## Each component of .alpha..sup.3 represents the contents of each register when .alpha..sup.0, as an initial value, is input into an arithmetic circuit (as shown below) and is shifted j times.

Encoding circuit

A code polynomial F(x) is given by the following equation:

where Q(x) and R(x) are a quotient and a remainder, when a code polynomial P(x) of 21 data bits and X.sup.10 P(X) are divided by a generator G(x). This would indicate that, if no error occurs at the time of decoding, the sequence of receiving signals may be exactly divided by the generator G(x). In the encoding circuit of FIG. 5, the contents of each of the resistors are so initialized as to be "0's". Then, switch S1 is turned to the down contact (as viewed in the drawing) and switch S2 is closed. The 21-bit data is sequentially output from the highest order, and downward to the output terminal. The output data is also applied to a shift register (a dividing circuit designed on the basis of the generator). Switch S1 is then turned to the up contact. With this circuit connection, the remainder R(x) is duly sent to the output terminal.

Decoding circuit

The syndrome wherein ##EQU5## may be obtained in the following manner. S.sub.0 and S.sub.1 are both 5th dimensional vectors which may be obtained on the basis of a receiving signal ##EQU6## using the following equations.

Further, in converting a burst error on the disk into a single error (for a burst length of 3 or less) in the code word, or in 2 bit errors for a burst length of 32 through 62, the code word is recorded in the optical disk, after being subjected to a 31-block interleaving process. The code word is recorded in bit serial order, by longitudinally scanning the 31 words formulated as shown in FIG. 8. Specifically, the data is recorded in the following order: D.sub.00, D.sub.1,0, . . . D.sub.30,0, D.sub.0,1, D.sub.1,1, . . . D.sub.30,1, . . . , C.sub.0,0, C.sub.30,0, . . . , C.sub.0,9, . . . , C.sub.30,9. Therefore, a single burst error of up to 62 bits, or double burst errors of 31 bits or less, may be corrected.

The format, 31 bits.times.31, is treated as one segment. Four segments constitute one sector. The sector is used as an addressing unit for the read and write operations. The errors in four segments of the same sector may be independently corrected, through a burst error is located astride the two adjacent segments.

Of the errors which might occur in the picture data, certain types of errors still remain, even after the error correction mentioned above.

An explanation may now be given of a word by word check of such errors. The above error correction approach cannot detect errors of three or more bits, or a multi-bit error incapable of correction. Therefore, the 21 bits word (referred to simply as a word) except the check bits for the BCH error correction code, contains no error or errors of five bits or more, after error correction. Assume now that all of the residual errors are three-bit errors, and that additional bit errors arising from the error correction are not contained in the bit error rate 10.sup.-8 of the residual error. Based on this assumption, the error rate in the word is 10.sup.-8 .times.21.div.3.congruent.10.sup.-7. This value apparently indicates the upper limit of the error rate of the word.

Next, an explanation may be given of the segment by segment check of the residual error. There are two possible causes for the occurrence of three or more bit errors in a word; one being the overlap of a long burst error of 63 bits or more with a plurality of short burst errors, and another being a mixture of this and other types of errors.

It is apparent that, by reason of the single long burst error, errors occur in successive words. For example, when the length l of the original error burst is within the following range, 63.ltoreq.l.ltoreq.92, errors occur in successive words (l-62). If l.gtoreq.93, all of the words within the segment will contain errors.

With a plurality of short burst errors, it is assumed that the words containing errors within the segment are randomly dispersed. In actuality, however, such a case is rare. This fact is empirically confirmed and may also be explained in the following manner. A bit error rate before the 1st error correction is 10.sup.-4. The frequency of triple errors due to the overlapping of burst errors of 31 bits or less is 31C.sub.3 (10.sup.-4).sup.3 .congruent.2.times.10.sup.-9. This is the probability of the occurrence of triple errors in the word. The probability is 2.times.10.sup.9 .times.1/31.times.3=2.times.10.sup.-10, in terms of the residual bit error rate. This value is much smaller than the residual bit error rate mentioned above. Hence, the major causes of the residual error are the long burst error, and an overlapping of the relatively long burst error (32.ltoreq.l.ltoreq.62) and the plurality of short burst errors. Therefore, when errors within the segment are observed word by word, those errors are frequently observed as burst errors.

The second error correction is as follows. In cases where the words with burst errors are successively present within the segment, and the number of error bits is 5 or more, the ordinary error correction code cannot be used. To cope with such cases, it is necessary to greatly increase the redundancy of the code. In the code used for the first error correction, for data of 21 bits, ten bits are additionally used, to correct 2 bits errors. The code word length is 1.48 times the number of data bits. Therefore, for the second error correction, it is necessary to use a coding system with high redundancy, in which the code length is two or more times as great.

Considering this problem from the systems side, it is very important that the size of the minimum unit of the code be properly selected, to provide for complete error correction.

The minimum unit for the read/write operation cannot be smaller than the unit used to provide complete error control. From the systems side, it is desirable to set the minimum unit for the read/write operation to 128 bytes, just as in the case of the minimum unit of the floppy disk. One segment of the optical disk is 21 bits.times.31=651 bits=81 bytes. Therefore, it is desirable to perform error correction control with the unit of one sector being equal to 324 bytes of the optical disk.

The second error correction, which is performed in the CPU 12, the main memory 13 and the optical disk unit 22, may be described as follows. To cope with the above problems, the second error correction is based on a doubling of the record of the coded data and the error detection. Specifically, the coded data is doubly recorded, with error detection codes attached thereto. The physical space between the coded data doubly recorded is set as long as possible, so that the single long burst error will not effect both items of data. The read and write operations of the application program are performed with an access unit of 128 bytes, as shown in FIG. 9. The driver routine for the optical disk device is sent, in the format shown in FIG. 10, to the optical disk device. The flag may be used for storing an address of the control data, or may be empty. CRC3 through CRC0 are error detecting codes for the 64 byte data of each segment. For such codes, it is preferable to use a 16-bit CRC, according to recommendations of the CCITT (The International Telegraph and Telephone Consultative Comittee). Since the number of error bits is large, however, it is impossible to obtain precise error detection. The rate of error check miss is approximately 2.sup.-16 . For judging the read out of the data, the doubled items of data read out from the optical disk are entirely compared with one another. When both items of data are exactly coincident with each other, it is judged that the data has been read out correctly. When the result of this comparison is noncoincidence, both items of recorded data are subjected to a cyclic redundancy check, to judge which item of recorded data is correct. In cases where only one of the CRC in one item of data is checked, and the data is employed on the basis of the judgement that the CRC is correct, the data checking suffers from a data check miss, on the order of 2.sup.-16 (approximately 10.sup.-5). For this reason, it is essential to check the comparison and coincidence between the doubled data.

FIG. 11 shows a memory map of a program executed by the CPU 12. As shown, this program is composed of a control program 51 forming an operating system, a magnetic disk driver routine 52, a driver routine 52 for a magnetic disk, a driver routine 53 for an optical disk, and an application program 54.

The operation of an embodiment of the present invention may be described as follows, with reference to the flowcharts of FIGS. 12 and 13. The flow chart shown in FIG. 12 illustrates the control flow occurring when the picture data and code data is written into the optical disk 19. To begin with, in step 61, it is judged whether the input data is code data or picture data. When it is code data, in step 62, the data of 128 bytes (FIG. 9) received from the application program is halved, and the halved items of data are doubly loaded into the page buffer 14, according to the format of FIG. 14. In this example, the flag 1 in FIG. 10 is composed of 52 bytes, and stores, for example, a file ID when a file is opened from the application program. The flag 2 of 2 bytes is used for recording a serial number of a 128 bytes record in a file by counting up in a driver routine on the basis of the initial value applied from the application. In this example, there is a considerable difference between a conventional optical disk format and the 128 byte length record of the CPU. Therefore, the flag field appears to have a relatively large area in the format. The reason such a format is used is that, when considering such use in terms of the overall system, the amount of code data is greatly reduced. In step 64, the DMA controller 29 and the CRC circuit 30 are triggered. Then, the DMA the controller 29 sequentially reads out the data of 118 bytes, as shown in FIG. 10, and sends this data to the CRC circuit 30. The CRC circuit 30 computes the CRC of the data. The CRC which is thus computed is added to the original data of 118 bytes. The optical disk unit 22 performs the first error correction of the data received, and then writes the data onto the optical disk. While one sector of the optical disk has 31.times.31.times.4=3844 bits, as described above, the data sent from the optical disk unit 26 has 8.times.120.times.4=3840 bits. "0" is written into these remaining four bits. Then, in a step 65, a general post processing such as an error processing in a write mode, is performed. In this example, the write operation is described using the flowchart shown in FIG. 12, for the sake of simplicity. Actually, however, to improve the efficiency of the write operation, a known technique is used for this write operation. For example, the interrupt is applied to the interrupt acceptable portion of the write operation. Further, the processing of the next 128 bytes record processing is performed concurrently with the read/write access to the optical disk unit 22. When the input data is the picture data of step 61, the picture data, being intact, is transferred to the page buffer 14. Then, the CPU proceeds to step 64.

The read operation may be described as follows, with reference to the flowchart of FIG. 13. In step 71, it is judged whether the input data is picture code or code data. When it is code data, a predetermined optical disk sector is designated in block 73, and the optical disk unit 22 is driven. The optical disk unit 22 performs the first error correction. The code data received from the optical disk unit 22 is applied to the CRC 30, where the CRC code is being computed. The computed CRC code and the CRC code recorded at the time of writing are compared, to judge whether the read out data is correct or not. The code data is stored in the main memory 13 by the DMA controller 29. The CRC 30 informs the CPU 12 of the results of the CRC check as a status. In step 74, the CPU 12 compares the doubled portions of the read out data, i.e., data D.sub.127, . . . , D.sub.64 and data D.sub.63, . . . , D.sub.6, to thereby check where an error is contained or not. The entire data D.sub.127 to D.sub.0 are compared, in addition to the CRC check. When the result of the comparison is the coincidence between them, one of the data is selected in a step 75. When the comparison indicates noncoincidence in step 76, the results of the CRC check are checked. When one item of code data has an error, the other valid item of code data is selected. Where the results of comparison indicate noncoincidence, and the CRC check indicates that both items of data are correct, the error in question is deemed uncorrectable. Then, in the next step 77, the correct data is transferred to the application program, with the occurrence of an uncorrectable error being prevented. When, in step 71, the input data is picture data, the ordinary picture data readout is performed in step 72. The data so read out is transferred to the application program, in step 77.

In the above-mentioned embodiment, the comparing check in a write mode is executed by the driver routine 53, which is executed by the CPU 12. Alternatively, this routine 53 may be executed by the hardware. In an optical disk adaptor, the DMA 29 has a plurality of channels 82, 83. Channel 82 is used for transferring the data coming from the optical disk unit 22 to the main memory 13. In the latter half of each sector read, channel 83 again reads out the data written by channel 82, for the comparison of the data, in synchronism with the data sent to channel 82.

In this example, each sector produces an excess of 4 bits. The excess bits must be divided into two-bit groups for the first and second halves of the sector. Specifically, additional clocks corresponding to 2 bits must be applied to the optical disk unit 22, at the center and at the end of the sector.