Quasi-Cyclic Low-Density Parity-Check Codes
AssigneeMitsubishi Electric Research Laboratories, Inc.
InventorsJonathan Yedidia, Yige Wang
Life of this patent
Estimating the term…
Abstract
A system and a method for determining a quasi-cyclic (QC) low-density parity-check (LDPC) code, such that the QC LDPC code has no trapping sets are disclosed. A set of matrices representing a family of QC LDPC codes are acquired, wherein each QC LDPC code is a tail-biting spatially-coupled code of girth not less than eight, and wherein each column of each matrix in the set has a weight not less than four. Based on a trapping set pattern, a matrix from the set of matrices is selected such that the matrix represents the QC LDPC code with no trapping sets. The matrix can be stored into a memory.
Claims20
A method for determining a quasi-cyclic (QC) low-density parity-check (LDPC) code, such that the QC LDPC code has no trapping sets, comprising the steps of:
- acquiring a set of matrices representing a family of QC LDPC codes, wherein each QC LDPC code is a tail-biting spatially-coupled code of girth not less than eight, and wherein each column of each matrix in the set has a weight not less than four;
- selecting, based on a trapping set pattern, a matrix from the set of matrices, such that the matrix represents the QC LDPC code with no trapping sets;
- and
- storing the matrix into a memory, wherein the steps of the method are performed by a processor.
A system for encoding data based on a quasi-cyclic (QC) low-density parity-check (LDPC) code, comprising:
- a source for providing the data;
- a memory for storing a QC LDPC code represented by a parity check matrix, wherein the parity check matrix represents a tail-biting spatially-coupled (TBSC) QC LDPC code with no trapping sets;
- and
- an encoder for encoding the data using the TBSC QC LDPC code to produce an encoded data, and for transmitting the encoded data over a channel.
A method for determining a quasi-cyclic (QC) low-density parity-check (LDPC) code, comprising the steps of:
- determining a skeleton base matrix of a tail-biting spatially-coupled code such that a weight of each column equals four;
- applying to the skeleton base matrix a girth-maximization procedure to produce the set of matrices representing a family of QC LDPC codes, wherein each QC LDPC code is a tail-biting spatially-coupled code of girth not less than eight, and wherein each column of each matrix in the set has a weight not less than four;
- selecting, from the set of matrices, a preliminary matrix having in a corresponding Tanner graph no pattern of fully connected six bits, wherein the full connected six bits form two groups of three bits, wherein every bit in one group is connected to every bit in the other group;
- testing, for each set of candidate elements in the preliminary matrix forming a pattern of nearly-fully connected six bits in the corresponding Tanner graph, whether the set of candidate elements includes a trapping set, wherein the nearly-fully connected six bits form two groups of three bits, including a first group and a second group, wherein a first bit and a second bit of the first group is connected to every bit in the second group, and wherein a third bit of the first group is connected to two bits in the second group;
- and
- finding the preliminary matrix as a matrix representing the QC LDPC code with no trapping sets, if the trapping set is not found;
- and otherwise
- repeating the selecting, the testing, and the finding, wherein the steps of the method are performed by a processor.
Dependencies are inferred from the claim text.