Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
1999-10-13
2004-02-10
Moise, Emmanuel L. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
C714S785000, C714S805000
Reexamination Certificate
active
06691278
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to detecting errors in coded bit strings.
Data storage systems, such as disk drives, are prone to various errors that can corrupt data. For example, media and electronic noise can change the content of a magnetic disk, and thereby produce an error. Such errors are not unique to data storage systems. Rather, any system that stores, retrieves, and/or transmits data (e.g., a communication system) is at risk of such errors.
Coding techniques were therefore developed to facilitate detection, and in some cases correction, of data errors. One such coding technique adds parity bits to the data before it is stored or transmitted. A device receives the data and, based on the parity bits, determines if there are errors in the data. Only errors of a particular length, such as one-bit errors, can be detected efficiently using these codes.
Coding techniques which go one step further, and correct errors in the data, require a large number of parity bits. The more parity bits that are used, however, the less storage space/bandwidth can be used for data bits.
SUMMARY OF THE INVENTION
One aspect of the invention relates to detecting and/or correcting predefined errors having various bit (1,0) combinations and lengths. In particular, a parity check matrix is generated that is used to detect the predefined errors based on parity bits in the data. A generation matrix is developed from the parity check matrix for adding the parity bits to the data.
In this aspect, values for elements in a column of the parity check matrix are selected. A predefined error is processed with the selected values in order to produce a syndrome matrix. The selected values are assigned to the column of the parity check matrix if an element of the syndrome has a value indicative of the predefined error.
By including values in the parity check matrix that produce a syndrome element indicative of the predefined error, it is possible to ensure that the parity check matrix can be used detect that error. Doing this for each error in a list of predefined errors produces a parity check matrix that can detect all errors in the list. This can be done for any list of errors, including errors having different lengths. Coding can be performed using a simple variant of the parity check matrix.
One or more of the following features/functions may also be included in this aspect.
Processing the predefined error with the selected value may comprise multiplying the predefined error by the selected value. If a selected element has a value that is not indicative of a predefined error, different values are selected for the elements. The different values are processed with the predefined error to produce a new syndrome, and the different values are assigned to the column of the parity check matrix if the syndrome has a value indicative of the predefined error. A new predefined error may also be selected, and the foregoing process repeated for the new predefined error.
The selecting, processing and assigning described above start at a last column of the parity check matrix and proceed, column-by-column, to a first column of the parity check matrix. The predefined error is included in an n-bit (n>1) string when the predefined error is processed with the selected values. The predefined error is moved to a different location in the n-bit string when it is processed with a different column of the parity check matrix.
Values for elements in the column comprise bit combinations that are possible for the column. The values are selected for the column by selecting each possible bit combination, in turn, for processing. A generation matrix for coding strings of bits is determined from the parity check matrix. A decoder comprised of logic gates is used to generate the parity check matrix.
In another aspect of the invention, a predefined error in a coded string of bits is detected by generating a parity check matrix based on the predefined error, and processing the string with the parity check matrix to produce a syndrome having one or more elements. It is then determined if the syndrome has an element that is indicative of the predefined error.
One or more of the following features/functions may also be included in this aspect.
An element h
i
(i≧1) in a column of the parity check matrix is selected such that:
h
i
≠
∑
k
=
2
min
(
l
j
,
n
-
i
)
h
i
+
k
-
1
e
jk
for
1
≤
j
≤
M
,
where l is a number of bits in an error, n is a number of bits in the coded string, M is a number of errors, and e is a bit in the error. A portion of the parity check matrix comprises an identity matrix.
In another aspect, a string of bits is coded to permit detection of predefined errors. A parity check matrix is generated which detects the predefined errors, and a generation matrix is determined from the parity check matrix. The string of bits is then processed with the generation matrix.
In another aspect, an error detection code (“EDC”) is used to correct a coded bit string. This is done by receiving data for the coded bit string, and determining distances between the data and bit combinations corresponding to the data. A bit combination is selected, to substitute for the data, that is permitted by the error detection code and that has a minimum distance. By using an EDC to perform error correction in this manner, error correction is performed with relatively few bits.
One or more of the following features/functions may also be included in this aspect. The error detection code requires that a number of bits in the coded bit string comply with a condition. The condition may be that the coded bit string have an even number of ones.
This brief summary has been provided so that the nature of the invention can be understood quickly. A detailed description of illustrative embodiments of the invention is set forth below.
REFERENCES:
patent: 4476562 (1984-10-01), Sako et al.
patent: 4775979 (1988-10-01), Oka
patent: 4939733 (1990-07-01), Furutani
patent: 5257272 (1993-10-01), Fredrickson
patent: 5563894 (1996-10-01), Fujiwara et al.
patent: 5745507 (1998-04-01), Chen
patent: 5862005 (1999-01-01), Leis et al.
Bahl et al., “Optimal decoding of linear codes for minimizing symbol error rate”, IEEE Trans. on Information Theory, 1974.
Fomey et al., “The Viterbi algorithm”, Proceedings of the IEEE, 61:3, 1973.
Gilbert “Capacity of u burst-noise channel” The Bell System Technical Journal, pp. 1253-1265, 1960.
Kanak et al., “Models for channels with memory and their applications to error control” Proceedings of the IEEE, 66:7, 1978.
Kuznetsov et al., “On the undetected error probability of Linear block codes on channels with memory”, IEEE Trans. Info. Theory, 42:1, 1996.
Viterbi et al., “Principles of Digital Communication and Coding”MC-GxawHills, 1979.
Wolf et al., “Efficient maximum likelihood decoding of linear block codes using a trellis” 24:1, 1978.
Wolf et al., “The single burst error detection performance a binary cyclic codes”, IEEE Trans. Comm. Theory, 42:1, 1994.
Leis Michael
McEwen Peter
Patapoutian Ara
Shen Ba-Zhong
Daly, Crowley & Mofford LLP
Maxtor Corporation
Moise Emmanuel L.
LandOfFree
Detecting errors in coded bit strings does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Detecting errors in coded bit strings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detecting errors in coded bit strings will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3313103