Error detection/correction and fault detection/recovery – Pulse or data error handling – Error count or rate
Reexamination Certificate
2000-08-29
2003-10-28
Dildine, R. Stephen (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error count or rate
C714S784000
Reexamination Certificate
active
06640319
ABSTRACT:
FIELD OF THE INVENTION
The invention is related to systems for detecting synchronization errors.
BACKGROUND OF THE INVENTION
Data are recorded on magnetic disks in tracks that are separated into sectors. Many sectors include, respectively, a header portion that lists the sector number and other information, and a data portion in which the data are recorded. Other sectors include the data portions, but not the headers. Synchronization information is included between the sectors, so that a disk drive can determine the start of the individual sectors and ultimately the start of the data portions of the respective sectors. The drive then, as necessary, counts sectors after reading a header to arrive at the designated sector to be written to or read.
Before recording, the data are typically encoded into data code words using an is error correction code (ECC). The data code word is then recorded in the data portion of the sector. To later read the data, a disk drive moves a read/write head over the appropriate track and, using the recorded synchronization information, determines the start of the data portion of the sector of interest. The head then reads the data code word and supplies it to a decoder. The decoder reproduces the data by manipulating the code word symbols and, as necessary, correcting any errors using the ECC.
If the drive makes a mistake in determining the location of the start of the data code word, that is, if there is a synchronization error, the drive reads a portion of the data code word and either information that precedes the data code word or information that follows the data code word, depending on the direction of the synchronization error. If the decoder mistakenly interprets what is read from the disk as a valid data code word, the decoder then “corrects” what it perceives as errors in the code word, and sends the result as error-free data to an application or a user.
The ECCs that are most often used are Reed-Solomon codes. The Reed-Solomon codes encode the data over a Galois Field (2
q
) where “q” is the number of bits in a code symbol or element. The Reed-Solomon codes are cyclic. Accordingly, if c
0
c
1
. . . c
c
is an unshortened code word, where the c
j
are elements of GF(2
p
), c
1
. . . c
c
c
0
is also a code word, as is c
c
c
0
c
1
. . . c
c-1
. This means that a synchronization error of one or more symbols may produce a different, but valid code word. If the mis-synchronization involves a number of bits rather than full symbols, the decoder most likely detects that every code word symbol is in error, assuming the code word includes a relatively large number of redundancy symbols. The decoder thus cannot correct the errors, and labels the data as erroneous.
To protect against the misinterpretation of the symbol-sized synchronization errors, a certain prior system adds a noise-like sequence into each data code word before the code word is recorded. Using Galois Field operations, the addition is accomplished by XOR'ing the sequence and the data code word. Before decoding, the system removes the sequence from the retrieved code word by XOR'ing the sequence to the code word. If the read operation is synchronized to the start of the codeword, that is, if there is no synchronization error, the XOR'ing of the sequence and the retrieved code word reproduces the original data code word.
Otherwise, the XOR'ing of the sequence to the retrieved code word introduces errors into the code word. Assuming the sequence is properly chosen such that the XOR'ing of the sequence with a shifted, or misaligned, version of the sequence does not result in a valid codeword, the decoder detects more errors in the decoded code word than the ECC can correct. The decoder then labels the mis-synchronized data as erroneous. If the sequence is not properly chosen and the XOR'ing operation instead produces a different and valid code word, the decoder “corrects” the errors using the ECC.
The prior system uses a trial and error approach to finding the noise-like sequence. The trial and error approach is time consuming and does not necessarily produce a sequence that introduces a maximum number of errors into a retrieved code word which contains synchronization errors. Further, the prior systems have to store the selected sequence in the encoder and also in the decoder, which increases the overall storage requirements of the system. Accordingly, the mis-synchronization technique may be impractical for systems that have limited storage capacities.
An error correction system that solves certain of these problems produces a code word for recording by XOR'ing to a data code word, which is encoded in accordance with a distance d Reed-Solomon code, a coset leader that is a code word of a distance d′ super code, but not a code word of the distance d code. When the code word is retrieved, the system XOR's it with the coset leader. If there is no synchronization error, the second XOR'ing operation removes the coset leader from the code word, to reproduce the data code word. If there is a synchronization error, the XOR'ing operation ensures that the retrieved code word includes a term that is a Hamming distance of d′ from every valid code word of the distance d Reed-Solomon code. The system then decodes the result in a conventional manner, and as long as d′>d/2 the system detects more errors than the ECC can correct.
The prior system determines appropriate distance d′ super codes from which to select the coset leader based on the generator polynomial of the distance d Reed-Solomon code. The system then selects from one of these codes a coset leader b(x) that is not also a code word of the distance d code. Next, the system tests that the term j(x)=b(x)*x
s
+b(x) is not a valid code word of the distance d code for every S of interest, where −T≦S<T and T is the maximum number of symbols by which the read/write head may be misaligned. If j(x) is a valid code word of the distance d code, the system selects and tests each of the remaining coset leaders from the distance d′ codes. If none of the coset leaders are appropriate, the system selects and tests the coset leaders from distance d″=d′−1 Reed-Solomon codes, and an appropriate coset leader in the distance d″ code can generally be found.
To reduce the associated storage requirements, the system may select a coset leader to be a code word that contains several versions of a shortened code word of the distance d′ code. The system then stores only the shortened code word, and essentially reproduces the coset leader by XORing the shortened code word to the data code word a number of times. Alternatively, the system may generate the coset leader from the stored shortened code word using, for example, a dedicated shift register.
The prior system thus provides a mechanism to select a coset leader for use in mis-synchronization detection and a way to reduce associated storage requirements. As discussed below, I have developed a system that provides a mechanism for including in a code word for recording a coset leader that has optimum mis-synchronization detection properties for the associated code. Further, the system minimizes storage requirements, while at the same time eliminating the need for dedicated hardware to reproduce the coset leader.
SUMMARY
The inventive system is an error correction system constructed in accordance with a distance d Reed-Soloman code that, during a modified step in the encoding operation, includes in a code word for recording a coset leader of a distance d−1 code. The modified encoding step includes in an appropriate manner in the encoding operation a predetermined non-zero “coset symbol” that results in the encoder producing a modified set of R redundancy symbols. The result of the encoding is a code word that includes in the redundancy symbols a coset leader that is a hamming distance d−1 from every valid code word of the distance d code. As discussed in more d
Cesari and McKenna LLP
Dildine R. Stephen
Maxtor Corporation
LandOfFree
Mis-synchronization detection system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Mis-synchronization detection system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mis-synchronization detection system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3141641