Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-07-18
2002-02-05
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S781000
Reexamination Certificate
active
06345376
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to methods and means for detecting and correcting up to t errors in linear cyclic codewords on the fly. More particularly, the invention relates to methods and means for the ultra-fast resolution of t error locations in each affected codeword from a counterpart degree t error locator polynomial, the polynomial being derived from syndromes processed in a data streaming environment such as an optical or magnetic storage subsystem read channel or the like.
DESCRIPTION OF THE RELATED ART
Data streaming, Moving Magnetic Storage, and Synchronism
It is well known that applications executing on a multimasking CPU, such as an IBM 390 running under an MVS operating system, can randomly or sequentially update tracks of data recordable on one or more IBM 3390 direct access storage devices (DASDs). The transfers to the DASDs are made via an attached IBM 3990 cache-based staged storage subsystem. The transfer of data between the CPU and the IBM 3990 cache and between the 3990 and any one of the 3390 DASDs are data streaming operations. In this regard, data streaming is a point-to-point uninterrupted movement of data serial by bit or serial by character or codeword in order to achieve high data transfer rates.
It should also be appreciated that a DASD includes a cyclic multitracked magnetic storage medium and an access mechanism. The access mechanism, in turn, includes a writing transducer for mapping the binary digital codewords into time-varying magnetic flux streams onto addressed tracks and a reading transducer for the inverse mapping. Reading a DASD track involves executing an analog-to-digital mapping of the time-varying flux changes created by the magnetized track moving past the read transducer into binary digital codewords. It further involves testing of the codewords as to whether they are the same as those originally recorded. Significantly, the disk storage medium is rotating at a constant angular rate, and this imposes a time constraint on the read path processing. In order for the processing of data copied from the disk to perform as a synchronous system, then t selected actions or events coincide in time. This means that the processing of data copied from the disk must complete the handling of a current codeword in time for the next codeword to be read and processed. That is, the processing must be completed no later than the recorded track image of the next codeword that passes under the DASD read transducer.
Some Attributes of Linear Cyclic Codes, Codewords, and Error Detection
Typically, digital data is written out to DASD tracks as sequences of codewords drawn from a linear block or cyclic error correction code. Upon being read back from DASD, these codewords can be tested for any errors or erasures and corrections made thereto before passing it further on.
Reference should be made to copending Hassner et al. application Ser. No. 08/838,375, filed Apr. 8, 1997, entitled, “Method and Means for Computationally Efficient Error and Erasure Correction in Linear Cyclic Codes”, now U.S. Pat. No. 5,942,005. In the Hassner case, a Reed-Solomon (RS) code is used to exemplify linear cyclic codes. Also, the RS code finds use in communication and storage because it maintains maximum distance among codewords for a given codeword length n. In this regard, the term “distance” means the number of bit changes that must be made to a first codeword such that it would appear to be the same as another codeword in the code set for a given amount of checking overhead.
As Hassner et al. explained, an RS code is one in which every codeword c(z) in an (n,k) linear cyclic code over GF(2
m
) is generated by dividing a block of data m(z) by a generator polynomial g(z) and adding the remainder thereto to modulo 2. Relatedly, c(z) is a polynomial of degree n−1 or less, where
m
(
z
)=
m
0
+M
1×1
+m
2×2
+ . . . +m
(n−r−1)×(n−r−1)
and where g(z)=g
0
+g
1×1
+g
2×2
+ . . . +g
r×r
, such that c(z)=m(z)/g(z)+remainder. It should be recalled that codewords are conventionally represented as a collection of coefficients of a rational polynomial of an arbitrary place variable z in low-to-high order.
Significantly, a received or read back codeword is r(z)=c(z)+e(z) where c(z) was the codeword originally transmitted or recorded and e(z) is the error. Relatedly, a syndrome polynomial S(z) is informally defined as S(z)=r(z) mod g(z). Thus, r(z)=c(z) if and only if g(z) divides into r(z) with a remainder of zero, i.e., S(z)=0. Otherwise, it can be shown that S(z) is dependent only on the error function e(z) such that S(z)=e(z) mod g(z).
Aspects of Reed Solomon Codes
An RS code may be said to comprise a set of vectors over a finite field F having p
m
elements, where p is a prime number. The elements of the field F are identified with either of two attributes. That is, they are identified with the p
m
−1 powers of a distinct element “a” and the symbol “0”. Alternatively, they are identified with the set of polynomials of degree of at most m−1 and with the coefficients in the field of integers modulo p. For purposes of convenience, let p
m
=2
8
=256 such that the field F is fixed at F
256
. In this RS code, all operations are performed modulo 2. The field F
256
can be constructed from the primitive polynomial p(z)=z
8
+z
6
+z
5
+z+1 with coefficients in GF(2) and where “a” is a primitive root of the irreducible polynomial p(z).
The defining property of an RS code C is that all vectors c=(c
0
, c
1
, . . . , c
254
) &egr; C satisfy the relations for a given set of numbers j:
∑
k
=
0
k
=
254
c
k
a
jk
=
0
mod
p
(
z
)
In this example, j &egr; {0,1, . . . , 7}. Also, the positions within a codeword may be indexed by the nonzero elements of the field a
0
, a
1
, . . . , a
254
. That is, c(z)=0 where z=a
j
.
Illustratively, assume that errors occurred in predetermined positions in a received codeword are indexed by {a
5
, a
13
, a
28
, a
29
, a
124
, a
136
} and the corresponding error values are {a
4
, a
5
, a
123
, a
3
, a
2
, a
0
}. Thus, if a syndrome from the received codeword r is determined from:
∑
k
=
0
k
=
254
c
k
a
jk
=
0
mod
p
(
z
)
then the nonzero syndromes in the example would be
S
0
=a
86
,S
1
=a
235
,S
3
=a
45
,S
4
=a
205
,S
5
=a
239
,S
6
=a
113
, and S
7
=a
173
.
Berlekamp and Horiguchi References
In the prior art as expressed in E. R. Berlekamp, “Algebraic Coding Theory”, by McGraw-Hill Publishing Co., 1968, pages 178-199, Berlekamp showed that if a linear error correction code had a distance 2t+1 between codewords, then the syndrome S(z) over a codeword c(z) could be expressed formally as the recursion:
∑
k
=
0
k
=
254
c
k
a
jk
=
0
mod
p
(
z
)
where z is a polynomial presentation of the codeword c(z), w(z) is the error evaluator polynomial, and &sgr;(z) is the error locator polynomial. This has been denominated as the “key equation”. Relatedly, Berlekamp showed that the locations of errors within a received codeword r are determined by the index positions j of a
j
as the roots of the locator polynomial &sgr;(z)=&sgr;(a
k
)=0. Note, in this specification, the terms “&sgr;(z)” and “ƒ(z)” are used interchangeably to designate the error locator polynomial.
Toshio Horiguchi of NEC Corporation wrote a seminal paper entitled “High Speed Decoding of BCH Codes Using a New Error Evaluation Algorithm”, published in
Electronics and Communications In Japan Part
3, Vol. 72, No. 12, 1989. Scripta Technica, Inc., made an English language translation available in 1990.
In this article, Horiguchi pointed out that decoding and error processing a linear cyclic code, such as a Re
Cox Charles Edwin
Flickner Myron Dale
Hafner James Lee
Hassner Martin Aureliano
Trager Barry Marshall
Brodie R. Bruce
McSwain Marc D.
Ton David
LandOfFree
Method and means for computationally efficient on-the-fly... 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 and means for computationally efficient on-the-fly..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and means for computationally efficient on-the-fly... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2980213