Granted Patent B2

US 8,560,920 · App. 12/444,061 · Granted Oct 15, 2013

Abstract

Claims (48)

1. An error correction apparatus comprising:

an input for receiving data that includes error-check data;

a processing resource arranged to calculate parity check data; and

a data store coupled to the processing resource and arranged to store look-up data for identifying, when in use, a location of an error in the received data, wherein:

the look-up data is a compressed form of indexed error location data; and

the processing resource is arranged to determine locations of entries in the look-up data based upon parity check calculations and to verify that values of the entries correspond to the parity check calculations.

2. An apparatus as claimed in claim 1 , wherein the compressed form of the indexed error location data consists of a first array of data and a second array of data.

3. An apparatus as claimed in claim 2 , wherein the second array of data comprises a plurality of vectors.

4. An apparatus as claimed in claim 3 , wherein:

a first dimension of each vector of the second array constitutes an index and a second dimension of each vector of the second array identifies an error location; and

the verifying that values of the entries correspond to the parity check calculations comprises verifying that an index of a vector corresponds to a parity check calculation, wherein a location of an entry of the vector was determined based upon the parity check calculation.

5. The apparatus of claim 4 , wherein verifying that the index of the vector corresponds to the parity check calculation comprises verifying that the index of the vector equals the parity check calculation.

6. An apparatus as claimed in claim 2 , wherein:

the first array of data comprises identifying data to identify data within the second array of data to be accessed; and

the processing resource is arranged to use an index value to determine a first value in the first array of data and to use the index value and the first value to determine a second value in the second array of data.

7. The apparatus as claimed in claim 6 , wherein:

the index value comprises a number; and

using the index value to determine a first value in the first array of data comprises calculating the quotient of the index value by another number.

8. The apparatus as claimed in claim 7 , wherein:

using the index value to determine a second value in the second array of data comprises calculating the remainder of the division of the index value by the other number.

9. The apparatus of claim 1 , wherein:

a location of an entry in the look-up data is determined by a plurality of values of parity check calculations;

a value of the entry corresponds to one of the values of parity check calculations; and

the verifying that the value of the entry corresponds to a parity check calculation value used to determine the location of the entry comprises verifying that the one value of parity check calculations corresponds to the parity check calculation value.

10. An apparatus as claimed in claim 1 , wherein the compressed form of the indexed error location data is a compression of a matrix representation of a table of the indexed error location data.

11. An apparatus as claimed in claim 1 , wherein the compressed form of the indexed error location data is formed using a matrix compression algorithm.

12. An apparatus as claimed in claim 1 , wherein the received data is a header of a data structure.

13. An apparatus as claimed in claim 1 , wherein the received data is a part of an Asynchronous Transfer Mode cell.

14. A method of correcting an error in data that includes error-check data, the method comprising the steps of:

receiving data comprising error-check data;

generating parity check data from the data;

accessing look-up data to identify a location of an error in the data, the accessing comprising determining a location of an entry of the look-up data based upon the parity check data, wherein access of the look-up data comprises access of a compressed form of indexed error location data; and

verifying that a value of the entry of the look-up data corresponds to the parity check data.

15. A method of generating error location data, the method comprising the steps of:

generating a table of error location data indexed by parity check value;

forming a matrix from the table of error location data; and

compressing the matrix to form a first array of data and a second array of data, wherein:

each entry of the second array of data comprises an error location value and a parity check value; and

the parity check value of an entry is to be used to verify that the error location value of the entry corresponds to a parity check value used as an index to the entry.

16. A method as claimed in claim 15 , wherein a mapping exists between the table of error location data and the first array of data and the second array of data.

17. A method as claimed in claim 15 wherein the second array of data comprises a plurality of vectors.

18. A method as claimed in claim 17 , wherein a first dimension of each vector constitutes an index and a second dimension of each vector identifies as error location.

19. A method as claimed in claim 15 , wherein the matrix is compressed using a matrix compression algorithm to form the first array of data and the second array of data.

20. A non-transitory computer-readable storage medium comprising computer program product, including program code portions for performing operations when run on a programmable apparatus, the operations comprising:

receiving data comprising error-check data;

generating parity check data from the data;

accessing look-up data to identify a location of an error in the data, the accessing comprising determining a location of an entry of the look-up data based upon the parity check data, wherein

access of the look-up data comprises access of a compressed form of indexed error location data; and verifying that a value of the entry corresponds to the parity check data.

Assignments (31)