US 6,789,227 B2 · System and method for generating low density parity check codes using bit-filling

Abstract

A computer-implemented system and method is for generating low-density parity check (LDPC) codes. One aspect of the invention includes a method for generating high rate LDPC codes that first constructs a matrix (H) of size m×n having m rows of check nodes and n columns of bit nodes. The matrix meets the following requirements: the weight of the j−th column equals aj; each row, r, has weight at most br; and the matrix H can be represented by a Tanner graph that has a girth of at least g≧g. The method then iteratively adds an (n+1)th column (U1) to matrix H, wherein the size of U1, is initially empty and is at most an+1, and wherein U1, comprises a set of i check nodes such that i is greater than or equal to 0 and i is less than an+1. The method then iteratively adds check nodes to U1. such that each check node does not violate predetermined girth and check-degree constraints. The matrix H is updated when a new column is added. The iterations are terminated if there are no new check nodes that do not violate the girth and check-degree constraints. The method can be modified to optimize various parameters, including the following cases: maximizing the rate for a fixed girth; maximizing the girth for a fixed rate; and maximizing the rate for a fixed girth and fixed length.

Claims16

Dependent claims

A computer-implemented method for generating low-density parity check (LDPC) codes comprising:

(a) constructing an m×n matrix H having m rows of check nodes and n columns of bit nodes, wherein the jth column has weight aj, each row, r, has a weight at most br the matrix H is representable by a Tanner graph having a girth g;
(b) iteratively adding an (n+1)th column (U1) to matrix H, wherein the size of U1 is initially empty and is at most an+1, and wherein U1 comprises a set of i check nodes such that i is greater than or equal to 0 and i is less than an+1;
(c) iteratively adding check nodes to U1 such that each check node does not violate predetermined girth constraint g, and check-degree constraint deg (c)<b(c);
(d) updating matrix H when a new column is added;
and
(e) terminating the iterations if there are no new check nodes that do not violate the girth and check-degree constraints.

3 more elements

An LDPC code generator for creating LDPC codes for use in an LDPC error correcting system, the LDPC error correcting system including an LDPC encoder that receives digital data and encodes said data using the LDPC codes, the LDPC code generator comprising:

processing module for generating an m×n matrix H having m rows of check nodes and n columns of bit nodes, wherein the respective weight of each respective jth column is aj, no row, c, has a weight greater than b(c), and wherein the matrix H can be represented by a Tanner graph that has a girth of at least g;
processing module for iteratively adding (n+1)th columns (U1) to matrix H, wherein the size of U1 is initially empty and is at most an+1, and wherein U1 comprises a set of i check nodes such that i is greater than or equal to 0 and i is less than an+1;
processing module for iteratively adding check nodes to U1 such that each check node does not violate predetermined girth and check-degree constraints;
processing module for updating matrix H when a new column is added;
and
processing module for decrementing the girth constraint if there are no new check nodes that do not violate the current girth constraint.

3 more elements

Dependencies are inferred from the claim text.

System and method for generating low density parity check codes using bit-filling

Life of this patent

System and method for generating low density parity check codes using bit-filling

Life of this patent

Abstract

Claims16