Description
Error Correction and Error Detection Method for Reading of Stored Information Data and a Storage Control Unit for the Same
The invention relates to an error correction and error detection method for reading of stored information data and code data from a storage device according to the preamble of
claim 1, or to a storage control unit for the realization of such a method.
: )
Error correction and error detection methods are known which are used to increase the ' reliability of the operation of storage devices, for example DRAM (Dynamic Random Access Memory), SRAM (Static Random Access Memory), flash or EEPROM (Electrically Erasable Programmable Read-Only Memory) devices deployed in computers or in embedded systems. Such methods are usually based on EC/ED (EC: Error Correction, ED: Error Detection) codes for error correction and error detection.
A similar error correction and error detection method is based on known fundamental principles, such as those described by Richard W. Hemming: Error Detecting and Error Correcting Code, Bell System Technical Journal 29 (2): pp. 147 - 160, 1950. In order to secure, for example, n bit data with single bit error correction (SEC, single bit error ] correction), 1 + login code bits are required. For a so called double bit error detection (DED, Double Bit Error Detection), an extension by another bit is required. SEC/DED ' will thus together require (2 + logan) code bits.
It is assumed that the probability that of the occurrence of each of the two possible errors, that is to say in the case of a storage process in a computer, an error resulting in 0 instead 1 or in 1 instead of 0, is always about the same.
This is also illustrated by Fig. 1, which shows 8 information data items Dl - D8 to be stored in addition to 5 code data items CO - C4 so as to form one data word which is stored with a total of 13 bits. In this example, the code data value designated with CO is used for DED.
For the information data D (8:1) to be stored, code data C (4:1) is determined according to
wherein the combination symbol "x" designates an evaluation of the data values Dl - D8 of the information data D (8:1) to be stored as an X-OR combination. The status of the individual data values Dl - D8 to be stored is in this case evaluated so that it is either determined whether an even parity exists, or determined whether an uneven parity exists. The DED code data value CO is determined according to
For the information data D (8:1) and code data C (4:1) read from a storage device,
a syndrome S (4:1) having syndrome data values SI - S4 is determined according to According to this method, the first four code data values Cl - C4 and the first four syndrome data values SI - S4 are used for SEC, and the code and syndrome data values CO, SO are used for DED. If the syndrome data values SO - S4 equal the value 0 in all 5 , bits of the syndrome S(4:l, 0), no error has occurred during the storage and reading of the
information data D(8:l). In the case of a single error, the first four SEC syndrome data S
; (4:1) indicate the position of the defective bit in the read data word (D (8:1), C (4:1) and
the DED syndrome data value SO equals 1. In this case, the positions SP within the read
data word (D(8:l), C(4:l) in the row after the individual code data values and
information data values are arranged in the sequence Cl, C2, Dl, C3, D2, D3, D4, C4, i D5, D6, D7, D8. In the case of a double error, at least one bit of the SEC syndrome data S (4:1) is not equal to 0, while the DED syndrome data value SO is equal to zero.
A similar method makes it possible to ensure in an advantageous manner that an error will be detected in a storage device during the reading of data from a storage device, and that it can be also corrected in the case of a single bit error.
A disadvantage in this case, however, is the requirement of significantly increased storage, which is needed not only for the information data values, but in addition also to secure the code data values. Increased computing resources are also required in order to determine the code data or the syndrome data. The determination of the code data and oi the syndrome data is usually converted by means of coding and decoding hardware, : :; which is a constituent part of a storage control unit.
An object of this invention is to propose an error correction and error detection method • for reading of stored information data from a storage device, which requires a limited extent of processing resources and thus preferably also a limited amount of hardware resources. Such a method should in particular enable detection of double-bit errors. In addition, a storage device arrangement is proposed, which realizes such a method.
This task is achieved with the error correction and error detection method having the characteristics of the patent claim 1, or with the storage device arrangement having the characteristics of patent claim 11. Advantageous embodiments are the subject of the dependent claims.
According to a preferred embodiment, an error correction and/or error detection method is provided for reading of stored information data from a storage device, wherein in ! addition to the information data, code data is read from the storage data, and syndrome data is generated from the information data and from the code data in order to determine errors and/or error positions in the read data,
wherein in the detection of multiple errors, it is determined whether, in the case of detected error positions, the storage positions associated with the information data or with the code data are either all equal to 0, or are all equal to 1.
The reading from a storage device is preferably performed using a storage device having a low probability that "1" will be stored instead of "0" in comparison to the probability that "0" value will be stored erroneously instead of "1", or vice versa. The probability of an error in a certain possible value state is preferably low with regard to another value state, which should be in particular understood as a significant difference in the frequency of errors, namely to a negligible extent in one of both possible cases.
For at least a double-error correction option with a single-error correction option, n information data values of the code data values of the information data are associated with the code data of the information data in the storage device.
In the case of a verification of the detected value "1" in a detected error position, according to a preferred embodiment, a multiple error, in particular a double error, is present.
According to a preferred arrangement, code data values are assigned at least to the storage positions 1, 2, 4 and 8, and information data values are in this case assigned ai least to the:storage positions 3, 5 through 7 and 9 through 12.
The syndrome data can be compared with associated parity bits of the corresponding
storage positions as the code data.
It is preferable that to employ a storage device having an asymmetrical error performance.
In addition to the method, a storage arrangement is provided, having a storage device and a storage control unit enabling, at least, reading of information data and of code data associated with the information data, wherein the storage control unit is designed and/or controlled to realize the above-described error correction and/or error detection method. The storage device is in this case preferably provided as a storage device which has an asymmetrical error performance.
The method and the storage arrangement are based on the idea to utilize the probability of
i
an asymmetrical occurrence of both possible errors, that is to say 0 instead of 1, or 1 ""' instead of 0, which occurs with some types of storage devices,
in order to save storage space. One bit of code data can be thus saved, without really reducing the operational reliability, when one of these probabilities is negligible whei compared to the other one.
A SEC-DED solution can be then provided for example only with (1 + login) code bits: It is advantageous when the coding and decoding hardware is also used sparingly, which ; would otherwise be required for the calculation of the special DED code data values CO, or of the DED syndrome data values in order to generate or verify these bits.
In many EEPROM or flash storage devices, the probability of an erroneous 1, say 1 instead of 0, is negligibly small, when compared to the probability of an erroneous
0, that is to say 0 instead of 1. Accordingly, only 4 bit codes or code data required in this case for 8 bit data or information data values. The 4-bit SEC is formed first for the SEC according to a known manner for the 8 bit data values information data after they have been read from the storage device. However, DED code data value CO is no longer required for DED, that is to say a parity = required for all data.order to detect a double error, one has to simply verify that all the found error positions in all the data values that have been read (D(8:l), C(4:l)) also contained a 0. If at least ;| one 1 is found, this means that a multiple error is present. Double errors are detected with reliability with such a procedure. Detection of triple or more errors is also possible.
The following is an explanation of an embodiment which is based on the attached figures
The figures show the following:
Fig. 1 is a schematic representation of the data values of information data and
code data which is read from a storage device, and of the steps of the method used for th«
determination of a possible error, and
Fig. 2 shows information data and code data, as well as an instruction for the
encryption method during the storage in a storage device.
As one can from Fig. 2, a sequence of information data dl, d2, d3, ... d!2, ..., from an input and/or output device IO is to be stored in a storage device M. In order to differentiate between the codes to ensure that this storage data dl, ... d!2 will be stored as the proper data or as user data to be stored, the data is stored as information data D(8:l), which is indicated with the individual data values Dl - D8, Dl - D8, and the; data forming a code is stored as code data C(4:l), which is indicated with the code data yalues Cl - C4. The individual codes correspond in this case to each bit. After the reading from the memory device M, syndrome data values SI - S4 are formed as syndrome data S(4:1), wherein each value is formed with one bit.
A variation of the procedure or a realization of the developed hardware can be achieved in a customary manner, so that for example, instead of using 8 bits in each case, a highei or lower number of bits are used with a correspondingly arranged quantity of code dataj be processed.
wherein the combination symbol "x" designates an evaluation of the data of the information data D(8:1) to be stored.
In this case, the status of the individual data values Dl - D8 of the information data D(8:l) to be stored is evaluated so that it is detected whether an even parity exists, or whether an uneven parity exists.
In the case of the determination of whether an even parity exists, it is determined whetr all the n positions have an even number of 1 s. In the case of an uneven parity, it is determined whether an uneven number of Is exists.
For the information data D(8:l) and code data C(4:1), which is read from the memory device as is schematically illustrated by Fig. 1, a syndrome S(4:l) having syndrome values S1 - S4 is determined according to
The combination preferably realized again
with a type, of a parity verification using even or uneven parity according to the parity type which was selected for the coding.
Assuming a negligibly small probability of the occurrence of an erroneous 1 when . compared to the probability of the occurrence of an erroneous 0, a special code value CO for the DED is not required. For the SEC, that is to say the detection of a single-bit error in the information data D(8:l) and/or the code data C(4:l) which is read from the storage device M, a syndrome having syndrome data S(4: 1) is generated in a known manner for these read data values Dl - D8, Cl - C4 according to the equation (3). This generation is performed again by means of parity verification. If all 4 syndrome values SI - S4 are equal to 0, no error is present. In the case of a simple error, the position 1 in the SEC-syndrome data (S(4:l) indicates the position of the erroneous bit in the read data word (D(8:1), C(4:1)) according to a manner and type that is per se known.
According to a preferred procedure, it is also verified whether all the found trigger positions in the read data word (Dl - D8, C(4:l)) contain a 0. If at least one value with 1 is found, this means that a multiple error is present. Moreover, the positions SP are within the read data word (D(8:l), C(4:l)) in the row after the individual code data values and ' information data values allocated in the row sequence: Cl, C2, Dl, C3, D2, D3, D4, C4, D5, D6, D7, D8. A modification of a known procedure is therefore assumed with respect to the detection of a double error.
In order to process information data and code data according to a similar error correction and error detection method,the read information values Dl - D8 are supplied from the input and/or output device IO to a storage control unit MC. The storage control unit MC determines in a first method step 1 the code data C(4:l) for the information data D (8:1) and assigns the information data values Dl - D8 and the code data values Cl - C4 to the storage device M in a known manner. The assignment is performed using equation (1) in the sequence of the ; code or information data values Cl, C2, Dl, C3, D2, D3, D4, C4, D5, D6, D7, D8. When another arrangement of the information data D(8:l) to the code data C(4:l) is used, it optionally also possible to select another sequence for the assignment of the storage
' ' |
locations in the storage device M.
For the read operation, the information data D(8:l) and code data C(4:l), which has been stored in his manner, is read from the storage device M and supplied to the storage device control unit MC, which determines the syndrome data in a third method step. After that, the store control unit MC performs, in a fourth method step 4, a parity comparison and ; thereby determines whether an error is present or not. In the case of a single-bit error, it is verified in the consequent sixth method step 6 whether in the data word (D(8:1), C(4:l)) read from the information data D(8:l) and the code data (C(4:l) at least 1 data value is equal to 1 in order to detect a double- or multiple-bit error. Thereafter, in a seventh method step 7, the error is determined and/or corrected. If no error is present, the nformation data values Dl - D8 are output in a subsequent method step 5 as information data D (8 : 1). The output can be realized in another entityin the same processor, and/or in an input and or/output device

1. An error correction and/or error detection method for reading (3 - 5) information data (D(8:l) stored in a storage device (M), wherein in addition to the information data (D (1:8)), code data (C(4:1)) is read from the memory device M, and syndrome data (S(4:1) is formed from the information data (D(8:1)) and the code data (C(4:1) in order to determine errors and/or error positions in the read data, characterized in thatfor detection of multiple errors, it is verified whether in the case of detected error positions the information data (D(8:l) associated with their storage position or code data (C(4:1)) are either all equal to 0, or are all equal to 1.
2. The method according to claim 1, wherein reading from a memory device is performed, wherein the probability of an erroneously stored vale "1" instead of ' "0" is small, when compared to the probability of an erroneously stored value "0" instead of "1", or vice versa.
3. The method according to claim 1 or 2, wherein the probability of an error in a
certain determined possible value status is small, when compared to another value
status.
4. The method according to one of the preceding claims, wherein for at least a
double-error detection with at least a single-error correction possibility, ninformation data values (dl-d8) of information data (W(8:l)), (1 + Iog2n) codevalues (C1 - C4) of the code data (C(4:1))are assigned to the information data (D(8:l) in the storage device (M).
5 The method according to one of the preceding claims, wherein in the case of,a
; |
determined value "1" in a determined error position, a multiple error is present, in particular a double error.
6 The method according to one of the preceding claims, wherein code data :
values (Cl - C4) are assigned at least to the storage device positions (SP) :
4 and 8 (pi, p2, p4, p8) and information data (D (8:1) are assigned at least
with the storage device positions (SP) 3, 5 through 7 and 9 through 12 (p3,
The method according to one of the preceding claims, wherein the syndrome
data (S(4:l) are compared to the corresponding associated parity bits of
storage device positions (SP) as the code data.
The method according to one of the preceding claims, wherein'the code data
(C(4:1) are determined according to
and the syndrome data (S (4 : 1) are determined according to
9. The method according to one of the preceding claims, wherein a storage
device (M) having an asymmetric error performance is employed.The method according to one of the preceding claims, wherein depending on a
type of the data having particular high reliability requirement, an additional
code data value (CO) and an additional syndrome value (SO) are employed;
which makes it possible to use where data requires a customary high level of
reliability, for example a program code, while for the type of data whose
reliability is less relevant, for example recorded speech, code data having a
reduced number of code data values can be used.
10. A storage device arrangement having a storage device (M) and a storage
control unit (MC), enabling at least reading of information data (D(8:l)) and
of code data (C(4:l) associated with the information data (D(8:l),
characterized by the fact that the storage control unit (MC) is designed and/or
controlled so as to carry out an error correction and/or error detection method
according to one of the preceding claims.
11. A storage device arrangement according to claim 11, wherein the storage
device (M) is characterized by an asymmetric error performance.