Mis-synchronization detection system

Details Mis-synchronization detection system Mis-synchronization detection system

1999-09-14

2002-10-08

Chung, Phung M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S755000, C714S782000

Reexamination Certificate

active

06463564

ABSTRACT:

BACKGROUND OF THE INVENTION
Data is recorded on magnetic disks in tracks that are separated into sectors. Each sector includes a header portion that lists the sector number and other information, and a data portion in which the data are recorded. Synchronization information is also included between the sectors, so that a disk drive can determine the start of the sector and ultimately the start of the data portion of the sector.
Before recording, the data are typically encoded into data code words using an 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. Accordingly, the decoder 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 by XOR'ing it to the retrieved 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, the decoder then detects more errors than the ECC can correct, and it labels the mis-synchronized data as erroneous. If the sequence is not properly chosen, the XOR'ing operation may instead produce a different and valid code word that can be “corrected” by 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 that contains synchronization errors. Further, the prior systems have to store the selected sequence in the encoder, which increases the overall storage requirements of the system. Accordingly, the mis-synchronization technique may be impractical for systems that have limited storage capacities.
SUMMARY OF THE INVENTION
An error correction system produces a code word for recording by XOR'ing to a data code word that 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 of the distance d Reed-Solomon code. The coset leader is chosen such that it is not a code word of the distance d code. When the code word is later retrieved, the system XOR's the coset leader to the retrieved code word. If there is no synchronization error, the XOR'ing operation reproduces the original data code word. If, however, there is a synchronization error, the XOR'ing operation introduces into the retrieved code word a term that is a Hamming distance of d′ from every valid code word of the distance d Reed-Solomon code. The result should then contain more errors than the ECC can correct, as long as
d
′
>
d
2
.
The system determines the super code from which to select the coset leader based on the generator polynomial of the distance d Reed-Solomon code. For a code with a generator polynomial which has consecutive roots &agr;
L
&agr;
L+1
&agr;
L+2
. . . &agr;
L+d−1
, where “&agr;” is a primitive element of GF(2
q
), the system first selects as the super code a distance d−1 Reed-Solomon code with a generator polynomial that has d−1 consecutive roots. Accordingly, the super code has a generator polynomial with roots &agr;
L+1
&agr;
L+2
. . . &agr;
L+d−1
or roots &agr;
L
&agr;
L+1
&agr;
L+2
. . . &agr;
L+d−2
. 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.
The system next checks 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 mis-synchronized, as discussed in more detail below. If j(x), which is necessarily a code word of the distance d−1 code, is not also a code word of the distance d code, the XOR'ing of b(x) to a retrieved code word that includes synchronization errors introduces into the code word a term that is a minimum Hamming distance of d−1 from every valid code word of the distance d code.
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−1 codes. If none of them are appropriate, the system selects and tests the coset leaders from a distance d−2 Reed-Solomon code that has a generator polynomial with d−2 consecutive roots, and so forth.
To reduce the system storage requirements, the coset leader may be selected to be a code word that contains r+1 versions of a shortened code word of the distance d′ code. The coset leader is thus:
b
i
(
x
)=
x
P
*m
(
x
)*
g
′(
x
)*[1
+x
d″
+x
2d″
+x
3d″
+ . . . +x
rd″
]
with d″ greater than or equal to the degree of m(x)*g′(x) and p+rd″+d′−1≦n, where g′(x) is the generator polynomial of the distance d′ code and n is the code length. The term m(x) may be selected to be an irreducible polynomial, and p and d″ are selected as discussed below. The system then stores the shortened code word rather than the entire coset leader, and XOR's the shortened code word r+1 times to the symbols of the data code word.
The system may instead generate the coset leader by repeatedly multiplying the shortened codeword by &agr;
e
, and the coset leader is
b
i
(
x
)=
x
P
*m
(
x
)*
g
′(
x
)*[1+&agr;
e
*x
d″
+&agr;
2e
*x
2d″
+ . . . +&agr;
re
*x
rd″
],
which is readily produced using a linear feedback shift register that in its initial state contains the coefficients of x
P
*m(x)*g′(x) and in each iteration multiplies the contents by &agr;
e
. The desirable values of r and e are such that &agr;
(r+1)e
=1 and the shift register thus returns to its

Affiliated with

Also associated with

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2953265