Optimization of low density parity-check code encoder based on a search for an independent set of nodes

Patent metadata

Field	Value
Publication number	US-10033407-B2
Application number	US-201715431559-A
Country	US
Kind code	B2
Filing date	Feb 13, 2017
Priority date	Apr 8, 2016
Publication date	Jul 24, 2018
Grant date	Jul 24, 2018

Abstract

Techniques are described for optimizing a parity-check matrix for a low density parity check (LDPC) encoder. In an example, a first parity-check matrix is accessed. Based on a set of rules, an independent set of check nodes and variable nodes is determined. The set of rules specifies that a check node associated with the first parity-check matrix belongs to the independent set when the check node is connected to only one variable node from the independent set. The set of rules further specifies that a variable node associated with the first parity-check matrix belongs to the independent set when the variable node is connected to only one check node from the independent set. A size of the independent set is based on the set of rules. A second parity-check matrix is generated by at least applying a permutation to the first parity-check matrix based on the independent set.

First claim

What is claimed is:

1. A computer-implemented method of generating a parity-check matrix for a low density parity-check (LDPC) encoder, the computer-implemented method comprising:
accessing, by a computer system, a first parity-check matrix defined for an LDPC decoder;
determining, by the computer system and based on a set of rules, an independent set of check nodes and variable nodes associated with the first parity-check matrix, wherein:
the set of rules specifies that a check node associated with the first parity-check matrix belongs to the independent set when the check node is connected to only one variable node from the independent set,
the set of rules further specifies that a variable node associated with the first parity-check matrix belongs to the independent set when the variable node is connected to only one check node from the independent set, and
a size of the independent set is based on the set of rules; and

generating, by the computer system, a second parity-check matrix by at least applying a permutation to the first parity-check matrix based on the independent set, wherein the LDPC encoder is configured to encode bits based on the second parity-check matrix for decoding by the LDPC decoder.

2. The computer-implemented method of claim 1 , wherein generating the second matrix comprises:
generating, by the computer system, an independent matrix based on the independent set of check nodes and variable nodes; and
permuting, by the computer system, rows and columns from the first parity-check matrix to define an arrangement of the rows and the columns that comprises the independent matrix, wherein the second parity-check matrix comprises the arrangement of the rows and the columns.

3. The computer-implemented method of claim 2 , wherein the independent matrix is the largest independent matrix available from the first parity-check matrix.

4. The computer-implemented method of claim 1 , wherein determining the independent set of check nodes and variable nodes is based on a search graph, and further comprising generating, by the computer system, the search graph by at least:
setting, as a vertex in the search graph, an edge from a bipartite graph corresponding to the first parity-check matrix, wherein the edge connects a pair of check node and variable node in the bipartite graph; and
connecting vertices in the search graph based on the set of rules.

5. The computer-implemented method of claim 4 , wherein the set of rules specifies that two vertices in the search graph are connected in the search graph when two corresponding edges from the bipartite graph share a same check node.

6. The computer-implemented method of claim 4 , wherein the set of rules specifies that two vertices in the search graph are connected in the search graph when two corresponding edges from the bipartite graph share a same variable node.

7. The computer-implemented method of claim 4 , wherein the set of rules specifies that two vertices in the search graph are connected in the search graph when each of the two corresponding edges from the bipartite graph is connected to a different check node and when the two corresponding edges from the bipartite graph are connected to a same variable node.

8. The computer-implemented method of claim 4 , wherein the set of rules specifies that two vertices in the search graph are connected in the search graph when each of the two corresponding edges from the bipartite graph is connected to a different variable node and when the two corresponding edges from the bipartite graph are connected to a same check node.

9. The computer-implemented method of claim 4 , wherein determining the independent set of check nodes and variable nodes comprises applying a greedy algorithm to the search graph by at least iteratively:
selecting a particular vertex in the search graph based on the set of rules, wherein the particular vertex has a number of connections to one or more other vertices, wherein the set of rules specifies a selection of the particular vertex based on the number of connections;
adding the particular vertex to a set of vertices; and
removing the one or more other vertices from the search graph.

10. The computer-implemented method of claim 9 , wherein the particular vertex is selected based on having a lowest number of connections across the vertices in the search graph, and wherein the independent set of check nodes and variable nodes is generated from the set of vertices by, for each particular vertex from the set of vertices, at least:
identifying a corresponding edge in the bipartite graph and a corresponding pair of check node and variable node connected by the corresponding edge; and
adding the corresponding pair of check node and variable node to the independent set.

11. The computer-implemented method of claim 1 , wherein determining the independent set of check nodes and variable nodes comprises applying a find-matching algorithm to nodes from a bipartite graph corresponding to the first parity-check matrix by at least:
selecting a candidate set of check nodes from the bipartite graph;
for each variable node from the bipartite graph, at least:
generating a connected set of check nodes for the variable node, wherein the variable node is connected to each check node in the connected set,
determining whether a size of an intersection between the candidate set and the connected set is equal to one, and
marking, based on a determination that the size of the intersection is equal to one, a particular check node as being associated with the variable node, wherein the particular check node belongs to the candidate set and is connected to the variable node in the bipartite graph; and

for a candidate check node in the candidate set, at least:
determining whether the candidate check node is marked as being associated with a particular variable node,
adding the candidate check node and the particular variable node to a potential independent set based on a determination that the check node is marked as being associated with the particular check node; and

setting the potential independent set as the independent set of check nodes based on a size of the potential independent set.

12. The computer-implemented method of claim 11 , further comprising:
generating a second potential independent set by at least varying a size of the candidate set of check nodes; and
selecting the potential independent set over the second potential independent set based on the set of rules specifying a selection according to a larger set size, and wherein the size of the potential independent set is larger than the size of the second potential independent set.

13. The computer-implemented method of claim 11 , wherein sizes of potential independent sets are varied based on a binary search for a largest size set, and wherein the set of rules specifies a selection of the potential independent set based on the potential independent set having the largest size from the potential independent sets.

14. A system comprising:
one or more processors; and
one or more memories communicatively coupled with the one or more processors and storing instructions that, upon execution by the one or more processors, configure the system to at least:
access a first parity-check matrix; and
generate a low density parity-check (LDPC) codeword by at least encoding bits based on the first parity-check matrix, wherein the first parity-check matrix is generated by at least:
determining, based on a set of rules, an independent set of check nodes and variable nodes associated with a second parity-check matrix, wherein:
the set of rules spec

Assignees

• Sk Hynix Inc

Inventors

• Bhatia Aman
• Yuan Wei-Hao
• Lin Yi-Min
• Kumar Naveen
• Zhang Fan
• Yen Johnson

Classifications

• H03M13/611

  Specific encoding aspects, e.g. encoding by means of decoding · CPC title

• H03M13/616

  Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations · CPC title

• H03M13/116 Primary

  Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices · 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/1108 Primary

  Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping · CPC title