Combined group ECC protection and subgroup parity protection

• US 8,468,416 B2
• Filed: 06/26/2007
• Issued: 06/18/2013
• Est. Priority Date: 06/26/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gara, Alan G., Chen, Dong, Heidelberger, Philip, Ohmacht, Martin
• Primary Examiner(s): CHAUDRY, MUJTABA M
• Application Number:
  US11/768,527
• Publication Number:
  US 20090006923A1
• Time in Patent Office: 2,184 Days
• Field of Search: 714/801, 714/758
• US Class Current: 714/758
• CPC Class Codes: G06F 11/1064 in cache or content addressable memories
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2212/403 Error protection encoding, e.g. using parity or ECC codes
• CPC Class Codes: H03M 1/0687 using fault-tolerant coding, e.g. parity check, error correcting codes H03M1/069 takes precedence
• CPC Class Codes: H03M 13/13 Linear codes
• CPC Class Codes: H03M 13/2707 Simple row-column interleaver, i.e. pure block interleaving
• CPC Class Codes: H03M 13/271 Row-column interleaver with permutations, e.g. block interleaving with inter-row, inter-column, intra-row or intra-column permutations
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations

Abstract

A method and system are disclosed for providing combined error code protection and subgroup parity protection for a given group of n bits. The method comprises the steps of identifying a number, m, of redundant bits for said error protection; and constructing a matrix P, wherein multiplying said given group of n bits with P produces m redundant error correction code (ECC) protection bits, and two columns of P provide parity protection for subgroups of said given group of n bits. In the preferred embodiment of the invention, the matrix P is constructed by generating permutations of m bit wide vectors with three or more, but an odd number of, elements with value one and the other elements with value zero; and assigning said vectors to rows of the matrix P.

Claims

1. A method of providing combined error code protection and subgroup parity protection for a given group of n bits, the method comprising the steps of:

identifying a number, m, of redundant bits for said error code protection;

constructing an error correction code (ECC) checkbits generator matrix P for generating an ECC word for said given group of n bits and for generating parity bits for subgroups of said given group of n bits, wherein the matrix P includes a multitude of rows and columns, multiplying said given group of n bits with P produces m redundant error correction code protection bits, and two of the columns of P provide parity bits for parity protection for subgroups of said given group of n bits; and

using a computer system, implementing a matrix construction algorithm, for performing the step of constructing the matrix P.

2. A method according to claim 1, wherein the step of constructing the matrix P includes the steps of:

generating permutations of m bit wide vectors with three or more, but an odd number of, elements with value one and the other elements with value zero; and

assigning said vectors to rows of the matrix P.

3. A method according to claim 2, wherein the matrix P fulfills the following conditions:

i) all elements of P are either one or zero; and

ii) the elements of columns p0 to pk are non-equal to zero for rows for which said columns provide parity protection, and otherwise the elements of said columns p0 to pk are zero.

4. A method according to claim 3, wherein the matrix P fulfills the following further conditions:

iii) each row has an odd number of one-elements; and

iv) each row has at least three one-elements.

5. A method according to claim 4, wherein the step of constructing the matrix P includes the further steps of:

if not all rows of P can be assigned one of said vectors, while satisfying said conditions, then increasing m and repeating the generating and assigning steps.

6. A method according to claim 5, wherein the step of increasing m includes the step of increasing m by one.

7. A method according to claim 1, comprising the further step of regenerating ECC protection bits periodically for groups only covered by parity protection.

8. A data storage system for storing data in a computer system and for providing combined error code protection and subgroup parity protection for said data, the data storage system comprising:

a memory storage unit for storing a given group of n bits, and for generating an error correction code (ECC) word for said given group of n bits and for generating parity bits for subgroups of said given group of n bits matrix P, wherein the matrix P includes a multitude of rows and columns, multiplying said given group of n bits with P provides m redundant protection bits for use as the error correction code for detecting and correcting errors in said given group of n bits, and two of the columns of P provide parity bits for parity protection for subgroups of said given group of n bits.

9. A data storage system according to claim 8, wherein P is constructed by generating m bit wide vectors with three or more, but an odd number of, elements with value one and the other elements with value zero, and assigning said vectors to rows of the matrix P.

10. A data storage system according to claim 9, wherein the matrix P fulfills the following conditions:

i) all elements of P are either one or zero;

ii) the elements of columns p0 to pk are non equal to zero for rows for which said columns provide parity protection, and otherwise the elements of said columns p0 to pk are zero;

iii) each row has an odd number of one-elements; and

iv) each row has at least three one-elements.

11. A data storage system according to claim 8, wherein if the entire given n-bit group is replaced with a new given n-bit group, then a new m-bit ECC for said new group is generated and stored along with said new group.

12. A data storage system according to claim 11, wherein if only a part of, but one or more entire parity protected subgroups of, said given n-bit group are changed, then the parity bits protecting the changed subgroups are changed.

13. A data storage system according to claim 8, wherein, when some components of the given group are changed, the unmodified components of the group are read and merged with the modified components to form a new group, and then a new m-bit ECC for said new group is generated and stored along with the new group.

14. A computer readable storage device, tangibly embodying a program of instructions executable by a computer to perform method steps for providing combined error code protection and subgroup parity protection for a given group of n bits, said method steps comprising:

identifying a number, m, of redundant bits for said error protection code; and

constructing an error correction code (ECC) checkbits generator matrix P for generating an ECC word for said given group of n bits and for generating parity bits for subgroups of said given group of n bits, wherein the matrix P includes a multitude of rows and columns, multiplying said given group of n bits with P produces m redundant error correction code protection bits, and two of the columns of P provide parity bits for parity protection for subgroups of said given group of n bits.

15. A computer readable storage medium according to claim 14, wherein the step of constructing the matrix P includes the steps of:

generating permutations of m bit wide vectors with three or more, but an odd number of, elements with value one and the other elements with value zero; and

assigning said vectors to rows of the matrix P.

16. A computer readable storage medium according to claim 15, wherein the matrix P fulfills the following conditions:

i) all elements of P are either one or zero;

ii) the elements of columns p0 to pk are non equal to zero for rows for which said columns provide parity protection, and otherwise the elements of said columns p0 to pk are zero;

iii) each row has an odd number of one-elements; and

iv) each row has at least three one-elements.