Bi-directional decodable Reed-Solomon codes

• US 6,651,214 B1
• Filed: 01/06/2000
• Issued: 11/18/2003
• Est. Priority Date: 01/06/2000
• Status: Expired due to Fees

• Current Assignee: Maxtor Corporation (Seagate Technology Holdings Plc)
• Original Assignee: Maxtor Corporation (Seagate Technology Holdings Plc)
• Inventors: Hall, Dana E., Weng, Lih-Jyh
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Torres, Joseph D.
• Application Number:
  US09/479,312
• Time in Patent Office: 1,412 Days
• Field of Search: 714/771, 714/784
• US Class Current: 714/771
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing
• CPC Class Codes: H03M 13/159 Remainder calculation, e.g. for encoding and syndrome calculation

Abstract

A bidirectional code decoding method and apparatus is presented. It uses a class of Reed-Solomon codes capable of bidirectional decoding, more specifically, those for which a value of L for a Galois Field element α^L is chosen as −(R−1)/2 for odd values of R and 2^(m−1)−R/2 for even values of R. When the symbols of such codes are received at a decoder in a reverse order (from that in which the symbols are normally received) during a reverse directional read, the decoder produces reverse directional syndromes S^˜(−k) and converts the reverse directional syndromes S^˜(−k) to syndromes S(k) by multiplying S^˜(−k) by α^(n−1)k for k=L, L+1, . . . , L+R−1. Alternatively, the decoder adjusts error location values for errors occurring in reverse order code word symbols to correspond to error location values that correspond to an error locations that would be determined if the symbols were to be received in the order in which the symbols are normally received.

Claims

1. A method of processing a code word comprised of symbols arranged in a forward order, the method comprising:

receiving, from a storage device, symbols of a code word in a reverse order that is opposite the forward order, the symbols received in the reverse order comprising reverse order symbols; and

performing a decoding procedure on the reverse order symbols by processing the symbols in the reverse order, the decoding procedure being performed using a single syndrome generator that is operable on both reverse order symbols and forward order symbols.

2. The method of claim 1, wherein the code word is a Reed-Solomon code word.

3. The method of claim 2, wherein performing a decoding procedure on the reverse order symbols comprises:

generating reverse directional syndrome values from the reverse order symbols.

4. The method of claim 3, wherein performing a decoding procedure on the reverse order symbols further comprises:

converting the reverse directional syndrome values to syndrome values that correspond to syndrome values that would be generated for the symbols if the symbols were to be received in the order in which the symbols are normally received.

5. The method of claim 4, wherein the code word is an m-bit n-symbol code word having R redundancy symbols, and a value L is defined as −

(R−

1)/2 for odd values of R and 2<sup>(m−

1)</sup>−

R/2 for even values of R, the value L comprising a constant of a Galois field factor of a generator polynomial, the code word being a multiple of the generator polynomial.

6. The method of claim 5, wherein converting comprises:

multiplying a first one of the reverse directional syndrome values by a first Galois field element α

of a power (n−

1)*L;

storing the result of the multiplication as a product value; and

for each successive one of the reverse directional syndrome values, updating the product value by multiplying the product value by a second field element α

of a power n−

1.

7. The method of claim 3, wherein performing a decoding procedure on the reverse order symbols comprises:

determining error locator polynomial coefficients from the reverse directional syndromes; and

reversing the order in which the error locator coefficients are applied to an error location computation unit.

8. The method of claim 1, wherein performing a decoding procedure on the reverse order symbols comprises:

determining that an error has occurred in at least one of the reverse order symbols;

determining an error location for the error; and

adjusting the error location for the at least one of the reverse order symbols to an error location that corresponds to an error location that would be determined if the symbols were to be received in the order in which the symbols are normally received.

9. The method of claim 1, further comprising:

receiving from a storage device symbols of a code word in an order in which the symbols are normally received; and

performing the decoding procedure on the code word.

10. A method of processing a code word stored on a storage device, the code word comprising symbols stored in a forward order, the method comprising:

reading symbols of the code word from a storage device in the forward order or in a reverse order that is opposite the forward order; and

decoding the code word;

wherein, in a case that the symbols are read in the reverse order, the code word is decoded by processing the symbols in the reverse order, decoding being performed using a single syndrome generator that is operable on both reverse order symbols and forward order symbols.

11. The method of claim 10, further comprising:

determining if the symbols are read in the order in which the symbols are normally read or in the reverse order from that in which the symbols are normally read.

12. The method of claim 11, further comprising:

performing a decoding procedure on the code word if it is determined that the symbols are read in the order in which the symbols are normally read.

13. The method of claim 11, further comprising:

performing a decoding procedure on the code word if it is determined that the symbols are read in the reverse order from that in which the symbols are normally read.

14. The method of claim 13, wherein the code word is a Reed-Solomon code word.

15. The method of claim 14, wherein performing a decoding procedure on the code word comprises:

generating reverse directional syndrome values from the reverse order symbols; and

converting the reverse directional syndrome values to syndrome values corresponding to syndrome values that would be generated if the symbols were to be read in the order in which the symbols are normally read.

16. The method of claim 15, wherein the code word is an m-bit n-symbol code word having R redundancy symbols, and a value L is defined as −

(R−

1)/2 for odd values of R and 2<sup>(m−

1)</sup>−

R/2 for even values of R, the value L comprising a constant of a Galois field factor of a generator polynomial, the code word being a multiple of the generator polynomial.

17. The method of claim 16, wherein converting comprises:

multiplying a first one of the reverse directional syndrome values by a first Galois field element α

of a power (n−

1)*L;

storing the result of the multiplication as a product value; and

for each successive one of the reverse directional syndrome values, updating the product value by multiplying the product value by a second field element α

of a power n−

1.

18. The method of claim 14, wherein performing a decoding procedure on the code word comprises:

determining that an error has occurred in at least one of the reverse order symbols;

determining an error location for the error; and

adjusting the error location for the at least one of the reverse order symbols to a error location that corresponds to an error location that would be determined if the symbols were to be read in the order in which the symbols are normally read.

19. The method of claim 14, wherein performing a decoding procedure on the code word comprises:

determining error locator polynomial coefficients from the reverse directional syndromes; and

reversing the order in which the error locator coefficients are applied to an error location computation unit.

20. A decoder comprising:

a controller; and

circuitry, responsive to the controller, which performs a bidirectional decoding on symbols of a Reed-Solomon code word, the circuitry receiving the symbols in one of a forward order and a reverse order and, if the symbols are received in the reverse order, performing decoding by processing the symbols in the reverse order, decoding being performed using a single syndrome generator that is operable on both reverse order symbols and forward order symbols.

21. The decoder of claim 20, wherein the controller determines if the symbols are received in the reverse order, and wherein the circuitry comprises:

a syndrome generator which generates reverse directional syndrome values for the code word when the symbols are determined to be reverse order symbols, the syndrome generator including a syndrome conversion unit which converts the reverse directional syndrome values to syndrome values corresponding to syndrome values that would be generated for the symbols if the symbols were received in the forward order.

22. The decoder of claim 20, wherein the controller determines if the symbols are received in the reverse order, and wherein the circuitry comprises:

circuitry which determines an error location value of an error occurring in the code word; and

an error location adjustment unit which modifies the error location value when the symbols are determined to be reverse order symbols.

23. A storage controller comprising:

a controller which reads a code word from a storage device in either a forward or a reverse direction; and

a decoder which decodes the code word in either the forward direction or the reverse direction;

wherein, if the controller reads the code word from the storage device in the reverse direction, the decoder decodes the code word by processing data from the code word ordered in the reverse direction, decoding being performed using a single syndrome generator that is operable on both reverse order symbols and forward order symbols.

24. A data storage system comprising:

a storage device;

a controller which reads a code word from the storage device in either a forward or a reverse direction; and

a decoder which decodes the code word as it is read from the storage device in either the forward direction or the reverse direction;

wherein, if the controller reads the code word in the reverse direction, the decoder decodes the code word by processing data from the code word ordered in the reverse direction, decoding being performed using a single syndrome generator that is operable on both reverse order symbols and forward order symbols.

25. The data storage system of claim 24, wherein the storage device comprises a magnetic tape.

26. A method of processing a code word, comprising:

receiving, from a storage device, symbols of a code word, the symbols being stored in a forward order and being received in a reverse order that is opposite the forward order, the symbols received in the reverse order comprising reverse order symbols; and

performing a decoding procedure on the reverse order symbols, the decoding procedure comprising generating reverse directional syndrome values from the reverse order symbols and decoding the reverse order symbols based on the reverse directional syndrome values, the decoding procedure being performed using a single syndrome generator that is operable on both reverse order symbols and forward order symbols.

27. The method of claim 26, wherein performing a decoding procedure on the reverse order symbols further comprises:

converting the reverse directional syndrome values to syndrome values that correspond to syndrome values that would be generated for the symbols if the symbols were to be received in the forward order.

28. The method of claim 27, wherein the code word is an m-bit n-symbol code word having R redundancy symbols, and a value L is defined as −

(R−

1)/2 for odd values of R and 2<sup>(m−

1)</sup>−

R/2 for even values of R, the value L comprising a constant of a Galois field factor of a generator polynomial, the code word being a multiple of the generator polynomial.

29. The method of claim 28, wherein converting comprises:

multiplying a first one of the reverse directional syndrome values by a first Galois field element α

of a power (n−

1)*L;

storing the result of the multiplication as a product value; and

for each successive one of the reverse directional syndrome values, updating the product value by multiplying the product value by a second field element α

of a power n−

1.

30. A mass storage system that stores symbols of a code word in a forward order, the mass storage system comprising:

receiving means for receiving symbols of the code word in a reverse order that is opposite the forward order, the symbols received in the reverse order comprising reverse order symbols; and

decoding means for decoding the reverse order symbols in the reverse order, the decoding means comprising a single syndrome generator that is operable on both reverse order symbols and forward order symbols.

31. The mass storage system of claim 30, wherein the decoding means comprises:

determining means for determining that an error has occurred in at least one of the reverse order symbols; and

locating means for locating the error.

32. The mass storage system of claim 30, wherein the decoding means is also for decoding forward order symbols.

33. The mass storage system of claim 30, wherein the code word is a Reed-Solomon code word and the decoding means further comprises:

generating means for generating reverse directional syndrome values based on the reverse order symbols; and

converting means for converting the reverse directional syndrome values to syndrome values that would be generated for the reverse order symbols received in the forward order.

34. The mass storage system of claim 30, wherein the Reed-Solomon code word is an m-bit n-symbol code word having R redundancy symbols, and a value L corresponds to −

(R−

1)/2 for odd values of R and 2<sup>(m−

1)</sup>−

R/2 for even values of R, the value L comprising a constant of a Galois field factor of a generator polynomial, the Reed-Solomon code word being a multiple of the generator polynomial.

35. The mass storage system of claim 34, wherein the converting means comprises:

multiplying means for multiplying a first one of the reverse directional syndrome values by a first Galois field element α

of a power (n−

1)*L;

storing means for storing an output of the multiplying means as a product value; and

updating means for updating the product value by multiplying the product value by a second field element α

of a power n−

1, for each successive one of the reverse directional syndrome values.

36. A method comprising:

receiving, from a storage device, symbols of a Reed-Solomon code word in a reverse order, the symbols being stored on the storage device in a forward order that is opposite the reverse order, the symbols received in the reverse order comprising reverse order symbols; and

performing a decoding procedure on the reverse order symbols by processing the symbols in the reverse order, the decoding procedure being performed using a single syndrome generator that is operable on both reverse order symbols and forward order symbols;

wherein the decoding procedure comprises;

generating reverse directional syndrome values based on the reverse order symbols; and

converting the reverse directional syndrome values to syndrome values that correspond to syndrome values that would be generated if the reverse order symbols were received in forward order.

37. The method of claim 36, wherein:

the Reed-Solomon code word is an m-bit n-symbol Reed-Solomon code word having R redundancy symbols, and a value L corresponds to −

(R−

1)/2 for odd values of R and 2<sup>(m−

1)</sup>−

R/2 for even values of R, the value L comprising a constant of a Galois field factor of a generator polynomial, the code word being a multiple of the generator polynomial; and

wherein converting comprises;

multiplying a first one of the reverse directional syndrome values by a first Galois field element α

of a power (n−

1)*L;

storing a result of the multiplying as a product value; and

for each successive one of the reverse directional syndrome values, updating the product value by multiplying the product value by a second field element α

of a power n−

1.

38. The method of claim 36, wherein the decoding procedure further comprises:

determining that an error has occurred in at least one of the reverse order symbols;

determining a location of the error; and

adjusting the location of the error.

39. The method of claim 36, further comprising:

receiving, from a storage device, symbols of a Reed-Solomon code word in a forward order, the symbols received in the forward order comprising forward order symbols; and

performing a decoding procedure on the forward order symbols using the single syndrome generator.

40. A storage controller comprising:

a controller that is operable to sequentially read a code word from a storage device in either a forward direction to produce forward order symbols or a reverse direction to produce reverse order symbols, the reverse direction being opposite the forward direction; and

a decoder that is operable to decode the code word using at least one of the forward order symbols and the reverse order symbols, the decoder comprising a single syndrome generator that is operable on the reverse order symbols to produce a reverse directional syndrome and that is operable on the forward order symbols to produce a forward directional syndrome.

41. The storage controller of claim 40, wherein:

the controller determines if the symbols are received in the reverse direction; and

the syndrome generator comprises a syndrome conversion unit for converting the reverse directional syndrome to a corresponding forward directional syndrome.