Combined group ECC protection and subgroup parity protection

• US 9,252,814 B2
• Filed: 06/14/2013
• Issued: 02/02/2016
• Est. Priority Date: 06/26/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gara, Alan, Chen, Dong, Heidelberger, Philip, Ohmacht, Martin
• Primary Examiner(s): CHAUDRY, MUJTABA M
• Application Number:
  US13/918,127
• Publication Number:
  US 20130283123A1
• Time in Patent Office: 963 Days
• Field of Search: 714/758, 714/801
• US Class Current: 1/1
• 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 tangible computer readable hardware storage device, tangibly embodying computer readable code for providing an error correction code and parity protection for a given group of bits, wherein the given group of the bits comprises a plurality of subgroups of the bits, the computer readable code, when executing in a computer system, performing the following:

using a specified error correction code checkbits generator matrix P comprising a plurality of rows and a plurality of columns to provide an error correction code and parity bits, including

using the specified error correction code checkbits generator matrix P to provide an error correction code (ECC) for the given group of bits; and

using two of the columns of said error correction code checkbits generator matrix P to provide parity bits for parity protection across the subgroups of said given group of bits.

2. The computer readable storage device according to claim 1, wherein said matrix 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 the rows of the matrix P.

3. A method of providing an error correction code and parity protection for a given group of bits, wherein the given group of bits comprises a plurality of subgroups of the bits, the method comprising:

using a specified error correction code checkbits generator matrix P comprising a plurality of rows and a plurality of columns to provide an error correction code and parity bits, including

using the specified error correction code checkbits generator matrix P to provide an error correction code (ECC) for the given group of bits; and

using two of the columns of said error correction code checkbits generator matrix P to provide parity bits for parity protection across the subgroups of said given group of bits.

4. The method according to claim 3, wherein said matrix 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 the rows of the matrix P.

5. The method according to claim 3, comprising the further step of:

using a computer system, implementing a code providing algorithm, for performing the using the specified matrix P to provide the error correction code and the using two of the columns of said matrix P to provide parity bits for parity protection.

6. The method according to claim 3, wherein the using the specified matrix P to provide on error correction code includes:

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

multiplying said given group of bits with the matrix P to produce m redundant error correction code protection bits.

7. The method according to claim 3, wherein the matrix P simultaneously represents ECC on the group of bits and party across subgroups of said group bits.

8. The method according to claim 3, wherein:

the group of bits includes n bits; and

the using the specified error correction code checkbits generator matrix P includes

using m redundant bits to protect said group of n bits, and

generating the m redundant bits by multiplying an n bit wide data word with P.

9. A system for providing an error correction code and parity protection for a given group of bits, wherein the given group of bits comprises a plurality of subgroups of the bits, the system comprising:

one or more processing units configured for;

using a specified error correction code checkbits generator matrix P comprising a plurality of rows and a plurality of columns to provide an error correction code and parity bits, including

using the specified error correction code checkbits generator matrix P to provide an error correction code (ECC) for the given group of bits; and

using two of the columns of said error correction code checkbits generator matrix P to provide parity bits for parity protection across the subgroups of said given group of bits.

10. The system according to claim 9, wherein:

said matrix 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 the rows of the matrix P.