Method, apparatus and program storage device for correcting a burst of errors together with a random error using shortened cyclic codes
First Claim
1. A method for correcting a burst of errors having a length of b bits together with a random error, comprising:
- providing a received word in a syndrome register for analysis, the syndrome register being defined by a polynomial of degree n-k generating a cyclic code of length n and dimension k, k being the number of information bits in each codeword of said code, the received word being shifted in a first direction in the syndrome register M times, wherein M is less than or equal to n;
analyzing the syndrome register to determine whether the first n-k-b bits in the syndrome register are zero;
when a bit in the first n-k-b bits in the syndrome register is determined to be non-zero, XORing the vector in the syndrome register with all possible syndromes corresponding to one error; and
identifying a random error and an error burst in the last b bits of the syndrome register when an XOR of the first n-k-b bits in the syndrome register results in the first n-k-b bits equaling zero.
1 Assignment
0 Petitions
Accused Products
Abstract
A method, apparatus and program storage device for correcting a burst of errors together with a random error using cyclic or shortened cyclic codes is disclosed. The present invention solves the above-described problems by providing a received word to a syndrome register defined by a polynomial of degree n-k, said polynomial generating a cyclic or shortened cyclic code, wherein n is the length and k is the number of information bits in the codeword. The syndrome gets modified each time the received (possibly noisy) word is shifted. The contents of the syndrome register are processed to identify a random error together with an error burst of the received word. Then correction of the random error and the burst is made and a corrected codeword is generated.
12 Citations
30 Claims
-
1. A method for correcting a burst of errors having a length of b bits together with a random error, comprising:
-
providing a received word in a syndrome register for analysis, the syndrome register being defined by a polynomial of degree n-k generating a cyclic code of length n and dimension k, k being the number of information bits in each codeword of said code, the received word being shifted in a first direction in the syndrome register M times, wherein M is less than or equal to n;
analyzing the syndrome register to determine whether the first n-k-b bits in the syndrome register are zero;
when a bit in the first n-k-b bits in the syndrome register is determined to be non-zero, XORing the vector in the syndrome register with all possible syndromes corresponding to one error; and
identifying a random error and an error burst in the last b bits of the syndrome register when an XOR of the first n-k-b bits in the syndrome register results in the first n-k-b bits equaling zero. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. An apparatus for correcting a burst of errors having a length b together with a random error, comprising:
-
a trap decoder comprising a syndrome register and a buffer register, the syndrome register defined by a polynomial of degree n-k generating a cyclic code of length n and dimension k, k being the number of information bits in each codeword of said code, the received word being shifted in a first direction in the syndrome register M times, wherein M is less than or equal to n; and
a module, coupled to the syndrome register, for determining, for each shift of the received word, whether a bit in the first n-k-b bits in the syndrome register is non-zero, XORing a vector in the syndrome register with all possible syndromes corresponding to one error and identifying a random error and an error burst in the last b bits of the syndrome register when an XOR of the first n-k-b bits in the syndrome register results in the first n-k-b bits equaling zero. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. An apparatus for correcting a burst of errors having a length b together with a random error, comprising:
-
memory for receiving a word representing bits of received data; and
a processor, coupled to the memory, the processor being configured for calculating an n-k bit syndrome for each shift of the received word defined by a polynomial of degree n-k generating a cyclic code of length n and dimension k, k being the number of information bits in each codeword of said code, the received word being shifted in a first direction in the syndrome register M times, wherein M is less than or equal to n, the processor determining, for each shift of the received word, whether a bit in the first n-k-b bits in the syndrome register is non-zero, XORing a vector in the syndrome register with all possible syndromes corresponding to one error and identifying a random error and an error burst in the last b bits of the syndrome register when an XOR of the first n-k-b bits in the syndrome register results in the first n-k-b bits equaling zero. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27)
-
-
28. A storage system, comprising:
-
at least one magnetic recording medium for recording data thereon;
at least one transducer, associated with each of the at least one magnetic recording medium, for reading and writing data on the magnetic recording medium;
a motor, coupled to the at least one magnetic recording medium, for translating the magnetic recording medium;
an actuator, coupled to the transducer, for translating the at least one transducer relative to the at least one magnetic recording medium; and
a storage device signal processor, coupled to the motor, transducer and actuator, for controlling the operation of the motor and actuator and for correcting a burst of errors having a length b together with a random error in a word received from the transducer, the storage device signal processor being configured for calculating an n-k bit syndrome for each shift of the received word defined by a polynomial of degree n-k generating a cyclic code of length n and dimension k, k being the number of information bits in each codeword of said code, the received word being shifted in a first direction in the syndrome register M times, wherein M is less than or equal to n, the processor determining, for each shift of the received word, whether a bit in the first n-k-b bits in the syndrome register is non-zero, XORing a vector in the syndrome register with all possible syndromes corresponding to one error and identifying a random error and an error burst in the last b bits of the syndrome register when an XOR of the first n-k-b bits in the syndrome register results in the first n-k-b bits equaling zero.
-
-
29. A program storage device readable by a computer, the program storage device tangibly embodying one or more programs of instructions executable by the computer to perform a method for correcting a burst of errors together with a random error using shortened cyclic codes, the method comprising:
-
providing a received word in a syndrome register for analysis, the syndrome register being defined by a polynomial of degree n-k generating a cyclic or shortened cyclic code of length n and dimension k, k being the number of information bits in each codeword of said code, the received word being shifted in a first direction in the syndrome register M times, wherein M is less than or equal to n;
analyzing the syndrome register to determine whether the first n-k-b bits in the syndrome register are zero;
when a bit in the first n-k-b bits in the syndrome register is determined to be non-zero, XORing the vector in the syndrome register with all possible syndromes corresponding to one error; and
identifying a random error and an error burst in the last b bits of the syndrome register when an XOR of the first n-k-b bits in the syndrome register results in the first n-k-b bits equaling zero.
-
-
30. An apparatus for correcting a burst of errors having length b together with a random error, comprising:
-
means for receiving a word representing bits of received data;
means, coupled to the memory, for calculating an n-k bit syndrome for each shift of the received word defined by a polynomial of degree n-k generating a cyclic code of length n and dimension k, k being the number of information bits in each codeword of said code, the received word being shifted in a first direction in the syndrome register M times, wherein M is less than or equal to n;
means for determining for each shift of the received word, whether a bit in the first n-k-b bits in the syndrome register is non-zero;
means for XORing a vector in the syndrome register with all possible syndromes corresponding to one error; and
means for identifying a random error and an error burst in the last b bits of the syndrome register when an XOR of the first n-k-b bits in the syndrome register results in the first n-k-b bits equaling zero.
-
Specification