Error protecting groups of data words

• US 7,350,131 B2
• Filed: 01/22/2005
• Issued: 03/25/2008
• Est. Priority Date: 01/22/2005
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Trainin, Oded
• Primary Examiner(s): Chase; Shelly
• Assistant Examiner(s): ABRAHAM, ESAW T
• Application Number:
  US11/040,678
• Publication Number:
  US 20060168494A1
• Time in Patent Office: 1,158 Days
• Field of Search: 714/752, 714/753, 714/758, 714/763, 714/799
• US Class Current: 714/758
• CPC Class Codes: H03M 13/2915 with an error detection code in one dimension
• CPC Class Codes: H03M 13/2942 wherein a block of parity bits is computed only from combined information bits or only from parity bits, e.g. a second block of parity bits is computed from a first block of parity bits obtained by systematic encoding of a block of information bits, or a block of parity bits is obtained by an XOR combination of sub-blocks of information bits

Abstract

Disclosed are, inter alia, methods, apparatus, data structures, computer-readable media, and mechanisms, for use in protecting groups of data words. One embodiment manipulates these data words to generate a resultant data word and an error correction code thereon for use in identifying a position of a bit error, with error detection codes used to identify which data word actually has the bit error. One embodiment retrieves a stored particular data word and its error detection code from memory or other storage. If an error is detected, the other data words in the group corresponding to the error correction code are acquired and are manipulated to produce a new resultant data word. The error correction code and the new resultant data word are used to identify the position of the bit error, with a corresponding bit position corrected in the particular data word.

Claims

1. A method for protecting data, the method comprising:

manipulating a plurality of data words to generate a resultant data word;

generating an error correction code for the resultant data word, the error correction code including a plurality of error correction bits;

associating different portions of the plurality of error correction bits with at least two of the plurality of data words;

for each particular data word of the plurality of data words;

generating an error detection code based on said particular data word and said associated portion of the plurality of error correction bits if any; and

transmitting or storing said plurality of data words, said error correction code, and said plurality of error detection codes;

after said transmitting or storing operation;

acquiring data, said acquired data including;

a particular data word of the plurality of data words, its associated said error detection code, and its said associated portion of the plurality of error correction bits if any; and

performing an error detection operation on said acquired data.

2. The method of claim 1, comprising:

in response to said error detection operation identifying an error condition;

performing an error correction operation on said acquired data.

3. The method of claim 2, including in response to said identifying the error condition, acquiring one or more additional portions of said different portions of the plurality of error correction bits.

4. The method of claim 3, wherein said one or more additional portions of said different portions of the plurality of error correction bits are only acquired if said error detection operation identifies the error condition.

5. The method of claim 2, wherein said performing the error correction operation includes generating a new resultant word based on the current values of the plurality of data words, identifying a bit position in the resultant data word to correct based on the resultant word and the error correction code, and correcting a corresponding bit position in said acquired data.

6. The method of claim 1, wherein said storing said plurality of data words, said error correction code, and said plurality of error detection codes includes:

for each said data word of the plurality of data words, storing its value, its said error detection code, and its associated portion of the plurality of error correction bits if any in a same memory line in one or more memories.

7. The method of claim 1, wherein said manipulating the plurality of data words to generate the resultant data word includes exclusively-OR'"'"'ing bits of the plurality of data words.

8. A method for protecting data, the method comprising:

performing an error detection check on a particular data word of a plurality of data words based on the particular data word and a particular error detection code;

in response to an error condition identified by said error detection check, manipulating data to generate a resultant data word, said data including the plurality of data words;

performing an error correction operation based on the resultant data word and on an associated predetermined error correction code to identify a bit position of an error; and

error correcting a bit in the particular data word corresponding to the bit position;

wherein each of the plurality of data words is included in a different one of a plurality of data lines;

wherein the plurality of data lines includes the error correction code and a plurality of error detection codes, with each of the plurality of data words associated with a different one of the plurality of error detection codes.

9. The method of claim 8, wherein different portions of the error correction code are stored in different data lines of the plurality of data lines.

10. A method for protecting data, wherein each of a plurality of data words is included in a plurality of data lines which are stored in one or more memories, each of the plurality of data lines includes one of the plurality of data words and one of a plurality of error detection codes;

and the method comprises;

retrieving a particular data word of the plurality of data words and a particular error detection code of the plurality of error detection codes from said one or more memories;

performing an error detection check on the particular data word based on the particular data word and the particular error detection code;

in response to an error condition identified by said error detection check, manipulating data to generate a resultant data word, said data including the plurality of data words;

performing an error correction operation based on the resultant data word and on an associated predetermined error correction code to identify a bit position of an error; and

error correcting a bit in the particular data word corresponding to the bit position.

11. The method of claim 10, wherein the error correction code is maintained in a register independent of said one or more memories;

and wherein the method includes retrieving the error correction code from the register.

12. The method of claim 10, wherein different portions of the error correction code are included in different lines of the plurality of data lines.

13. The method of claim 12, wherein a particular data line of said plurality of data lines includes the particular data word, the particular error detection code, and a particular portion of said different portions of the error correction code, said different portions including the particular portion and remaining portions;

and the method includes;

in response to the error condition identified by said error detection check, retrieving the remaining portions of said error correction code.

14. A method for protecting data, the method comprising:

performing an error detection check on a particular data word of a plurality of data words based on the particular data word and a particular error detection code, wherein the plurality of data words includes the particular data word and remaining data words;

in response to an error condition identified by said error detection check;

retrieving the remaining data words from one or more memories, and manipulating data to generate a resultant data word, said data including the plurality of data words;

performing an error correction operation based on the resultant data word and on an associated predetermined error correction code to identify a bit position of an error; and

error correcting a bit in the particular data word corresponding to the bit position.

15. An apparatus for protecting data, the apparatus comprising:

means for manipulating a plurality of data words to generate a resultant data word;

means for generating an error correction code for the resultant data word, the error correction code including a plurality of error correction bits;

means for associating different portions of the plurality of error correction bits with at least two of the plurality of data words;

means for generation for each particular data word of the plurality of data words;

an error detection code based on said particular data word and said associated portion of the plurality of error correction bits if any; and

means for storing said plurality of data words, said error correction code, and said plurality of error detection codes;

means for acquiring data, said acquired data including;

a particular data word of the plurality of data words, its associated said error detection code, and its said associated portion of the plurality of error correction bits if any; and

means for performing an error detection operation on said acquired data.

16. The apparatus of claim 15, comprising:

means for performing an error correction operation on said acquired data in response to said error detection operation identifying an error condition.

17. The apparatus of claim 16, including means for acquiring one or more additional portions of said different portions of the plurality of error correction bits in response to said identifying the error condition.

18. The apparatus of claim 16, wherein said means for performing the error correction operation includes means for generating a new resultant word based on the current values of the plurality of data words, means for identifying a bit position in the resultant data word to correct based on the resultant word and the error correction code, and means for correcting a corresponding bit position in said acquired data.

19. The apparatus of claim 15, wherein said means for storing said plurality of data words, said error correction code, and said plurality of error detection codes includes:

for each said data word of the plurality of data words, storing its value, its said error detection code, and its associated portion of the plurality of error correction bits if any in a same memory line in one or more memories.

20. One or more computer-readable media tangibly encoded thereon with computer-executable instructions for performing operations when executed by one or more processing elements, said operations comprising:

performing an error detection check on a particular data word of a plurality of data words based on the particular data word and a particular error detection code;

in response to an error condition identified by said error detection check, manipulating data to generate a resultant data word, said data including the plurality of data words;

performing an error correction operation based on the resultant data word and on an associated predetermined error correction code to identify a bit position of an error; and

error correcting a bit in the particular data word corresponding to the bit position;

wherein each of the plurality of data words is included in a different one of a plurality of data lines;

wherein the plurality of data lines includes the error correction code and a plurality of error detection codes, with each of the plurality of data words associated with a different one of the plurality of error detection codes.

21. An apparatus for protecting data, the apparatus comprising:

one or more memories, wherein each of a plurality of data words is included in a plurality of data lines stored in said one or more memories, each of the plurality of data lines includes one of the plurality of data words and one of a plurality of error detection codes;

means for retrieving a particular data word of the plurality of data words and a particular error detection code of the plurality of error detection codes from said one or more memories;

means for performing an error detection check on the particular data word based on the particular data word and the particular error detection code;

means for, in response to an error condition identified by said error detection check, manipulating data to generate a resultant data word, said data including the plurality of data words;

means for performing an error correction operation based on the resultant data word and on an associated predetermined error correction code to identify a bit position of an error; and

means for error correcting a bit in the particular data word corresponding to the bit position.

22. The apparatus of claim 21, comprising:

a register independent of said one or more memories, wherein the error correction code is maintained in the register; and

means for retrieving the error correction code from the register.

23. The apparatus of claim 21, wherein different portions of the error correction code are included in different lines of the plurality of data lines.

24. The apparatus of claim 23, wherein a particular data line of said plurality of data lines includes the particular data word, the particular error detection code, and a particular portion of said different portions of the error correction code, said different portions including the particular portion and remaining portions;

and wherein the apparatus includes means for, in response to the error condition identified by said error detection check, retrieving the remaining portions of said error correction code.

25. An apparatus for protecting data, the apparatus comprising:

means for performing an error detection check on a particular data word of a plurality of data words based on the particular data word and a particular error detection code, wherein the plurality of data words includes the particular data word and remaining data words;

means for performing operations in response to an error condition identified by said error detection check, said operations including;

retrieving the remaining data words from one or more memories, and manipulating data to generate a resultant data word, said data including the plurality of data words;

means for performing an error correction operation based on the resultant data word and on an associated predetermined error correction code to identify a bit position of an error; and

means for error correcting a bit in the particular data word corresponding to the bit position.