Error correction codes for incremental redundancy

Patent metadata

Field	Value
Publication number	US-8954831-B2
Application number	US-201414336066-A
Country	US
Kind code	B2
Filing date	Jul 21, 2014
Priority date	Feb 28, 2011
Publication date	Feb 10, 2015
Grant date	Feb 10, 2015

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.

First claim

The invention claimed is:

1. An apparatus, comprising:
a front-end unit configured to:
receive a radio frequency (RF) signal, wherein the RF signal includes data encoded with an error correction code (ECC), wherein the ECC is defined by a plurality of parity check equations, and wherein a parity check matrix representing the ECC includes a data sub-matrix and a parity sub-matrix;
convert the RF signal to an intermediate frequency (IF) signal; and
sample the IF signal to generate a digitized signal;

a modem unit configured to demodulate the digitized signal to generate a plurality of code words, wherein each code word of the plurality of code words includes a plurality of data bits and a plurality of parity bits; and
an decoder unit configured to:
decode a given one of the plurality of code words using each data bit of the plurality of data bits and a first partial subset of the plurality of parity bits of the given one of the plurality of code words and dependent upon a second partial subset of the plurality of parity check equations; and
re-decode, responsive to a determination that the decode of the given one of the plurality of code words failed, the given one of the plurality of code words using the data bits and each parity bit of the plurality of parity bits and dependent upon each parity check equation of the plurality of parity check equations;

wherein a first sub-matrix of the parity sub-matrix corresponding to the first partial subset of the plurality of parity bits and to the second partial subset of the plurality of parity check equations comprises a lower triangular matrix.

2. The apparatus of claim 1 , wherein sub-matrix comprises a rectangular block of elements, wherein elements of the rectangular block of elements below a main diagonal of the parity sub-matrix are zero.

3. The apparatus of claim 1 , wherein each parity check equation of the plurality of parity check equations evaluates to zero for a valid code word.

4. The apparatus of claim 1 , wherein the ECC comprises a Low Density Parity Check (LDPC) code.

5. The apparatus of claim 1 , wherein a number of parity check equations included in the second partial subset of the plurality of parity check equations is equal a number of parity bits included in the first partial subset of the plurality of parity bits of the given one of the plurality of code words.

6. A method, comprising:
receiving a radio frequency (RF) signal, wherein the RF signal includes data encoded with an error correction code (ECC), wherein the ECC is defined by a plurality of parity check equations, and wherein a parity check matrix representing the ECC includes a data sub-matrix and a parity sub-matrix;
converting the RF signal to an intermediate frequency (IF) signal;
sampling the IF signal to generate a digitized signal;
demodulating the digitized signal to generate a plurality of code words, wherein each code word of the plurality of code words includes a plurality of data bits and a plurality of parity bits;
decoding a given one of the plurality of code words using each data bit of the plurality of data bits and a first partial subset of the plurality of parity bits of the given one of the plurality of code words and dependent upon a second partial subset of the plurality of parity check equations; and
re-decoding, responsive to determining that the decode of the given one of the plurality of code words failed, the given one of the plurality of code words using the data bits and each parity bit of the plurality of parity bits and dependent upon each parity check equation of the plurality of parity check equations;
wherein a first sub-matrix of the parity sub-matrix corresponding to the first partial subset of the plurality of parity bits and to the second partial subset of the plurality of parity check equations comprises a lower triangular matrix.

7. The method of claim 6 , wherein sub-matrix comprises a rectangular block of elements, wherein elements of the rectangular block of elements below a main diagonal of the parity sub-matrix are zero.

8. The method of claim 6 , wherein each parity check equation of the plurality of parity check equations evaluates to zero for a valid code word.

9. The method of claim 6 , wherein the ECC comprises a Low Density Parity Check (LDPC) code.

10. The method of claim 6 , wherein a number of parity check equations included in the second partial subset of the plurality of parity check equations is equal a number of parity bits included in the first partial subset of the plurality of parity bits of the given one of the plurality of code words.

11. The method of claim 6 , wherein a number of parity check equations included in the second partial subset of the plurality of parity check equations is less than a number of parity bits included in the first partial subset of the plurality of parity bits of the given one of the plurality of code words.

12. A computer-accessible non-transitory storage medium having program instructions stored therein that, in response to execution by a computer system, cause the computer system to perform operations including:
receiving a radio frequency (RF) signal, wherein the RF signal includes data encoded with an error correction code (ECC), wherein the ECC is defined by a plurality of parity check equations, and wherein a parity check matrix representing the ECC includes a data sub-matrix and a parity sub-matrix;
converting the RF signal to an intermediate frequency (IF) signal;
sampling the IF signal to generate a digitized signal;
demodulating the digitized signal to generate a plurality of code words, wherein each code word of the plurality of code words includes a plurality of data bits and a plurality of parity bits;
decoding a given one of the plurality of code words using each data bit of the plurality of data bits and a first partial subset of the plurality of parity bits of the given one of the plurality of code words and dependent upon a second partial subset of the plurality of parity check equations; and
re-decoding, responsive to determining that the decode of the given one of the plurality of code words failed, the given one of the plurality of code words using the data bits and each parity bit of the plurality of parity bits and dependent upon each parity check equation of the plurality of parity check equations;
wherein a first sub-matrix of the parity sub-matrix corresponding to the first partial subset of the plurality of parity bits and to the second partial subset of the plurality of parity check equations comprises a lower triangular matrix.

13. The computer-accessible non-transitory storage medium of claim 12 , wherein sub-matrix comprises a rectangular block of elements, wherein elements of the rectangular block of elements below a main diagonal of the parity sub-matrix are zero.

14. The computer-accessible non-transitory storage medium of claim 12 , wherein each parity check equation of the plurality of parity check equations evaluates to zero for a valid code word.

15. The computer-accessible non-transitory storage medium of claim 12 , wherein the ECC comprises a Low Density Parity Check (LDPC) code.

16. The computer-accessible non-transitory storage medium of claim 12 , wherein a number of parity check equations included in the second partial subset of the plurality of parity check equations is equal a number of parity bits included in the first partial subset of the plurality of parity bits of the given one of the plurality of code words.

17. The computer-accessible non-transitory storage medium of claim 12 , wherein a number

Assignees

• Apple Inc

Inventors

• Anholt Micha
• Sommer Naftali

Classifications

• G06F11/1012 Primary

  using codes or arrangements adapted for a specific type of error (G06F11/1048 takes precedence) · CPC title

• G06F11/10 Primary

  Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's · CPC title

• H03M13/6393

  Rate compatible low-density parity check [LDPC] codes · CPC title

• H03M13/118

  Parity check matrix structured for simplifying encoding, e.g. by having a triangular or an approximate triangular structure (H03M13/1165 takes precedence) · CPC title

• H03M13/114

  Shuffled, staggered, layered or turbo decoding schedules · CPC title