Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-02-09
2003-04-29
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06557138
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a method for correction of errors in a binary word stored in multi-level memory cells, with minimum number of correction bits.
BACKGROUND OF THE INVENTION
In order to detect and correct errors in a binary word which contains m bits, which is indicated hereinafter as a source word, techniques are known which are based on the addition of “redundancy” to the source word, i.e., techniques based on the association with the source word, and consequent storage, of a binary word which contains k bits, and is indicated hereinafter as the correction word, in which the k bits are obtained by carrying out k parity checks on k sub-groups selected appropriately from the m bits in the source word.
This association is carried out in the so-called coding process, in which the 2
m
possible source words, which can be defined by means of m bits, are mapped in a set of an equivalent number of binary words of m+k bits, which are indicated hereinafter as the code words, each of which can be obtained by disposing a source word and the corresponding correction word one after the other and is then stored in the memory.
The value of each of the k correction bits associated during the coding process, depends on the type of parity check carried out. For example, the values of the k correction bits can be associated according to the so-called even parity checking criterion, i.e., the logic value 0 or 1, according to whether in the i-th sub-group there is respectively an even or odd number of logic values 1, is associated with the bit in the i-th position in the correction word, or the values can be associated according to the so-called odd parity checking criterion, i.e., the logic value 0 or 1, according to whether in the i-th sub-group there is respectively an odd or even number of logic values 1, is associated with the bit in the i-th position in the correction word.
The decoding process, in which, on the basis of a code word containing m+k bits stored, there is determination of the corresponding source word with m bits, with detection and correction of any errors which have been generated in it during the storage period, is carried out by executing once again the k parity checks on the bits in the source word, and comparing the correction word thus obtained with the correction word which is read by the memory, in order to generate a check word, which is also of the binary type and indicates the position of the error(s) present in the source word.
In detail, in the decoding process the i-th bit in the correction word, which is obtained by executing the i-th parity check on the i-th sub-group of the binary source word, is compared with the bit which is present in the i-th position in the correction word read by the memory and the logic value 0 or 1, according to whether the two bits compared are respectively the same as one another or different, is then associated with the i-th bit in the check word.
The check word is then compared with a plurality of error codes, each of which is constituted by a binary word which has the same length as the check word, and is associated with a bit or a group of bits in the source word and in the correction word, and is thus indicative of the position of this bit or group of bits. If there is an error, the check word is identical to one of the error codes, and thus, by means of the said association, it is possible to identify the incorrect bit(s).
With the bits in an error code having the logic value 1, there is associated a meaning which is linked to the composition of the sub-groups in the source word, of which the parity is to be checked.
In particular, a bit which is at the logic level 1 in the i-th position in the error code is indicative of the fact that the bit in the source word, which is located in the position associated with this error code, is part of the i-th sub-group of bits in the source word, on which the i-th parity check is carried out.
For example, in the case of the error code “0101” and on the assumption that this is associated with the error in the first bit in the source word, this error code is indicative of the fact that the first bit in the binary source word must form part of the sub-groups of bits on which the first and third parity checks are carried out.
In fact, by this means, if the first bit in the source word is incorrect, both the first bit and the third bit in the correction word which is generated during decoding (obtained from the first and the third parity checks) are different from the corresponding bits in the correction word generated during coding (during which the bit was different), and thus the error code which is obtained by comparing the two correction words has both the first and the third bit set to the logic value 1.
If the k sub-groups in the source word on which the k parity checks are to be carried out are selected appropriately, the error code is in bi-univocal correspondence with the position, within the code word, of the single incorrect bit(s) and thus when this bi-univocal correspondence is known the incorrect bit(s) can be corrected.
If conventional memories are used, in which a single bit is stored in each memory cell, the malfunctioning of a memory cell gives rise to deterioration of a single bit.
If, as is usually the case for this type of memory, the probability of failure of a cell is relatively low, it is sufficient to use a correction code which can detect and correct a single error in the source word; in fact, the probability of occurrence of a plurality of errors within the source word is negligible.
On the other hand, in a multi-level memory, in which several bits are stored in each memory cell, the malfunctioning of even a single memory cell can give rise to a multiple error, i.e., an error in several bits simultaneously.
In fact, as is known, in a floating gate multi-level memory cell the data to be stored is associated with the quantity of electric charge which is stored in the floating gate region (which in turn defines the value of the threshold voltage of the memory cell) and thus the loss or gain of electric charges in the floating gate region of one of the memory cells which is used in order to store the code word can generate, within the code word, a maximum number of errors which is equivalent to the number n of bits stored in the memory cell in which the deterioration of the electric charge has taken place.
In order to be efficient, a method for correction of the errors in a multi-level memory thus makes it necessary to be able to detect and correct multiple errors.
By using the known methods for the correction of multiple errors, there would be a considerable increase in the number of bits in the correction word, for the same length of source word, compared with the number required for correction of a single error, and thus an increase in the memory area, for the same data storage capacity.
It should however be noted that the deterioration of the electric charge stored in the floating gate region of a multi-level memory cell means that the n possible errors which this deterioration generates within the code word are present in positions which are correlated to one another and are known on the basis of the law of association, established a priori in the memory design stage, according to which the bits in the code word have been stored in the memory cells.
If, for example, in each memory cell there are stored n bits, which are disposed in adjacent positions in the binary word, the n possible errors generated by the faultiness of this memory cell can also only be disposed in positions which are adjacent within the binary word.
In order to correct a single error and dual errors present in any positions which are non-correlated to one another, within a code word stored in a conventional memory, for a binary word with m bits to be stored there is required a number k of correction bits such that the following inequality is fulfilled:
2
k
>1+
m+k+
½·(
m+k
)·(
m+k−
1) 1)
The preceding in
Chase Shelly A
De'cady Albert
Iannucci Robert
STMicroelectronics S.r.l.
LandOfFree
Method for correction of errors in a binary word stored in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for correction of errors in a binary word stored in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for correction of errors in a binary word stored in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3053108