# US 8,788,922 B2 · Error correction codes for incremental redundancy

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,788,922 B2
- Document ID: US8788922B2
- Status: Granted
- Kind: B2
- Application number: 13/405,308
- Filed: 2012-02-26
- Published: 2012-08-30
- Granted: 2014-07-22
- Earliest claimed: 2011-02-28
- Assignees: Apple Inc.
- Applicants: Micha Anholt; Naftali Sommer
- Inventors: Micha Anholt; Naftali Sommer
- Web page: https://patentgrep.com/patent/US8788922B2

## CPC

- G06F 11/10: Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
- G06F 11/1012: {using codes or arrangements adapted for a specific type of error (G06F11/1048 takes precedence)}
- H03M 13/114: {Shuffled, staggered, layered or turbo decoding schedules}
- H03M 13/118: {Parity check matrix structured for simplifying encoding, e.g. by having a triangular or an approximate triangular structure (H03M13/1165 takes precedence)}
- H03M 13/6393: {Rate compatible low-density parity check [LDPC] codes}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

A method includes accepting input including at least part of a codeword that has been encoded by an ECC defined by a set of parity check equations. The codeword includes data bits and parity bits. A decoding process is applied to the codeword using the data bits and only a first partial subset of parity bits in the input, and using only a second partial subset of equations. Upon a failure to decode the codeword using the partial subsets, the codeword is re-decoded using the data bits and all parity bits in the input, and using all equations. The set of parity check equations is defined such that any parity bit in the codeword appears in multiple equations, and any parity bit in the first partial subset of the parity bits appears in a plurality of equations in the second partial subset of the equations.

## Claims

### Claim 1

A method for error correction, comprising:
accepting input comprising at least part of a code word that has been encoded by an Error Correction Code (ECC) defined by a set of parity check equations, the code word comprising data bits and parity bits, wherein the ECC comprises a systematic ECC that is representable by a parity check matrix having a data sub-matrix and a parity sub-matrix;
applying a decoding process to the code word using the data bits and only a first partial subset of the parity bits that were comprised in the input and using only a second partial subset of the parity check equations; and
upon a failure to decode the code word using the first and second partial subsets, re-decoding the code word using the data bits and all the parity bits that were comprised in the input and using all the parity check equations in the set,
wherein the set of the parity check equations is defined such that any parity bit in the code word appears in multiple parity check equations in the set, and any parity bit in the first partial subset of the parity bits appears in a plurality of parity check equations in the second partial subset of the parity check equations;
wherein a first sub-matrix of the parity sub-matrix corresponding to the first partial subset of the parity bits and to the second partial subset of the parity check equations is lower triangular except for a group of last columns of the first sub-matrix.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the parity sub-matrix comprises a rectangular block of elements that are equal to zero below a main diagonal of the parity sub-matrix.

### Claim 3 (depends on 1)

The method according to claim 1, wherein a first sub-matrix of the parity sub-matrix corresponding to the first partial subset of the parity bits and to the parity check equations other than the second partial subset comprises elements that are equal to zero, except for one or more last columns of one or more first rows of the first sub-matrix.

### Claim 4 (depends on 1)

The method according to claim 1, wherein the second partial subset of the parity check equations is equal in size to the first partial subset of the parity bits.

### Claim 5 (depends on 1)

The method according to claim 1, wherein the second partial subset of the parity check equations is smaller in size than the first partial subset of the parity bits.

### Claim 6 (depends on 1)

The method according to claim 1, wherein accepting the input comprises reading the data bits and the first partial subset of the parity bits from a memory device in order to apply the decoding process, and, upon the failure, reading the parity bits other than the first partial subset from the memory device in order to re-decode the code word.

### Claim 7 (depends on 1)

The method according to claim 1, wherein accepting the input comprises receiving the data bits and the first partial subset of the parity bits from a communication receiver in order to apply the decoding process, and, upon the failure, receiving the parity bits other than the first partial subset from the communication receiver in order to re-decode the code word.

### Claim 8

A method for error correction, comprising:
accepting input comprising at least part of a code word that has been encoded by an Error Correction Code (ECC) defined by a set of parity check equations, the code word comprising data bits and parity bits, wherein the ECC comprises a systematic ECC that is representable by a parity check matrix having a data sub-matrix and a parity sub-matrix;
applying a decoding process to the code word using the data bits and only a first partial subset of the parity bits that were comprised in the input and using only a second partial subset of the parity check equations; and
upon a failure to decode the code word using the first and second partial subsets, re-decoding the code word using the data bits and all the parity bits that were comprised in the input and using all the parity check equations in the set,
wherein the set of the parity check equations is defined such that any parity bit in the code word appears in multiple parity check equations in the set, and any parity bit in the first partial subset of the parity bits appears in a plurality of parity check equations in the second partial subset of the parity check equations;
wherein a first sub-matrix of the parity sub-matrix corresponding to the parity bits other than the first partial subset and to the parity check equations other than the second partial subset is lower triangular except for a group of last columns of the first sub-matrix.

### Claim 9

Apparatus for error correction, comprising:
an interface; and
decoding circuitry, which is configured to accept via the interface input comprising at least part of a code word that has been encoded by an Error Correction Code (ECC) defined by a set of parity check equations, the code word comprising data bits and parity bits, to apply a decoding process to the code word using the data bits and only a first partial subset of the parity bits that were comprised in the input and using only a second partial subset of the parity check equations, and, upon a failure to decode the code word using the first and second partial subsets, to re-decode the code word using the data bits and all the parity bits that were comprised in the input and using all the parity check equations in the set,
wherein the set of the parity check equations is defined such that any parity bit in the code word appears in multiple parity check equations in the set, and any parity bit in the first partial subset of the parity bits appears in a plurality of parity check equations in the second partial subset of the parity check equations;
wherein the ECC comprises a systematic ECC that is representable by a parity check matrix having a data sub-matrix and a parity sub-matrix;
wherein a first sub-matrix of the parity sub-matrix corresponding to the first partial subset of the parity bits and to the second partial subset of the parity check equations is lower triangular except for a group of last columns of the first sub-matrix.

### Claim 10 (depends on 9)

The apparatus according to claim 9, wherein the parity sub-matrix comprises a rectangular block of elements that are equal to zero below a main diagonal of the parity sub-matrix.

### Claim 11 (depends on 9)

The apparatus according to claim 9, wherein a first sub-matrix of the parity sub-matrix corresponding to the first partial subset of the parity bits and to the parity check equations other than the second partial subset comprises elements that are equal to zero, except for one or more last columns of one or more first rows of the first sub-matrix.

### Claim 12 (depends on 9)

The apparatus according to claim 9, wherein the second partial subset of the parity check equations is equal in size to the first partial subset of the parity bits.

### Claim 13 (depends on 9)

The apparatus according to claim 9, wherein the second partial subset of the parity check equations is smaller in size than the first partial subset of the parity bits.

### Claim 14 (depends on 9)

The apparatus according to claim 9, wherein the interface is configured to accept the data bits and the first partial subset of the parity bits from a memory device in order to apply the decoding process, and, upon the failure, to accept the parity bits other than the first partial subset from the memory device in order to re-decode the code word.

### Claim 15 (depends on 9)

The apparatus according to claim 9, wherein the interface is configured to accept the data bits and the first partial subset of the parity bits from a communication receiver in order to apply the decoding process, and, upon the failure, to accept the parity bits other than the first partial subset from the communication receiver in order to re-decode the code word.

### Claim 16

Apparatus for error correction, comprising:
an interface; and
decoding circuitry, which is configured to accept via the interface input comprising at least part of a code word that has been encoded by an Error Correction Code (ECC) defined by a set of parity check equations, the code word comprising data bits and parity bits, to apply a decoding process to the code word using the data bits and only a first partial subset of the parity bits that were comprised in the input and using only a second partial subset of the parity check equations, and, upon a failure to decode the code word using the first and second partial subsets, to re-decode the code word using the data bits and all the parity bits that were comprised in the input and using all the parity check equations in the set,
wherein the set of the parity check equations is defined such that any parity bit in the code word appears in multiple parity check equations in the set, and any parity bit in the first partial subset of the parity bits appears in a plurality of parity check equations in the second partial subset of the parity check equations;
wherein the ECC comprises a systematic ECC that is representable by a parity check matrix having a data sub-matrix and a parity sub-matrix;
wherein a first sub-matrix of the parity sub-matrix corresponding to the parity bits other than the first partial subset and to the parity check equations other than the second partial subset is lower triangular except for a group of last columns of the first sub-matrix.