# US 10,484,012 B1 · Systems and methods for decoding quasi-cyclic (QC) low-density parity-check (LDPC) codes

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

- Number: US 10,484,012 B1
- Document ID: US10484012B1
- Status: Granted
- Kind: B1
- Application number: 15/688,628
- Filed: 2017-08-28
- Granted: 2019-11-19
- Earliest claimed: 2017-08-28
- Assignees: Xilinx, Inc.
- Applicants: Xilinx, Inc.
- Inventors: Nihat E. Tunali; Richard L. Walke; Christopher H. Dick
- Web page: https://patentgrep.com/patent/US10484012B1

## CPC

- H03M 13/1162: {Array based LDPC codes, e.g. array codes}
- H03M 13/1111: {Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms}
- H03M 13/1125: {using different domains for check node and bit node processing, wherein the different domains include probabilities, likelihood ratios, likelihood differences, log-likelihood ratios or log-likelihood difference pairs}
- H03M 13/1137: {Partly parallel processing, i.e. sub-blocks or sub-groups of nodes being processed in parallel}
- H03M 13/114: {Shuffled, staggered, layered or turbo decoding schedules}
- H03M 13/1117: {using approximations for check node processing, e.g. an outgoing message is depending on the signs and the minimum over the magnitudes of all incoming messages according to the min-sum rule}
- H03M 13/116: {Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices}
- 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: 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 decoder circuit includes an input configured to receive an encoded message generated based on a QC-LDPC code. A first layer process unit is configured to process a first layer of a parity check matrix to generate a plurality of log-likelihood ratio (LLR) values corresponding to a plurality of variable nodes associated with the encoded message respectively. The first layer process unit includes a plurality of row process units configured to process a first plurality of rows of the first layer in parallel to generate a plurality of row update values. A layer update unit is configured to generate a first LLR value for a first variable node using first and second row update values for the first variable node. An output is configured to provide a decoded message generated based the plurality of LLR values.

## Claims

### Claim 1

A decoder circuit, comprising:
an input configured to receive an encoded message generated based on a quasi-cyclic low-density parity check (QC-LDPC) code associated with a parity check matrix,
wherein the parity check matrix is constructed by expanding a plurality of elements of a base matrix using a plurality of submatrices respectively,
wherein a submatrix of the plurality of submatrices has a circulant weight greater than one;
a layer process unit configured to process a plurality of layers of the parity check matrix respectively to generate a plurality of log-likelihood ratio (“LLR”) values corresponding to a plurality of variable nodes associated with the encoded message, each layer including a plurality of rows of the parity check matrix,
wherein the layer process unit configured to process a first layer includes:
a plurality of row process units configured to process a first plurality of rows of the first layer in parallel to generate a plurality of row update values for the plurality of variable nodes; and
a layer update unit coupled to the plurality of row process units and configured to generate a first LLR value associated with a first variable node using first and second row update values for the first variable node; and
an output configured to provide a decoded message generated based on the plurality of LLR values.

### Claim 2 (depends on 1)

The decoder circuit of claim 1, where the first layer corresponds to a row of the base matrix.

### Claim 3 (depends on 2)

The decoder circuit of claim 2, where an element of the row of the base matrix is expanded with a submatrix having a circulant weight greater than one.

### Claim 4 (depends on 1)

The decoder circuit of claim 1, wherein the layer process unit further includes a storage element configured to store the first row update value and the second row update value, and
wherein the layer update unit is configured to retrieve, from the storage element, the first and second row update values for generating the first LLR value.

### Claim 5 (depends on 4)

The decoder circuit of claim 4, wherein a first row process unit of the plurality of row process units includes:
a first sub-row process unit configured to:
receive the first row update value corresponding to the first variable node; and
determine that the first variable node is updated two or more times in the first plurality of rows and in response, send the first row update value to the storage element.

### Claim 6 (depends on 5)

The decoder circuit of claim 5, wherein the first row process unit of the plurality of row process units includes:
a second sub-row process unit configured to:
receive a third row update value corresponding to a second variable node; and
determine that the second variable node is updated once in the first plurality of rows and in response, generate a second LLR value for the second variable node using the third row update value.

### Claim 7 (depends on 5)

The decoder circuit of claim 5, wherein the first row process unit of the plurality of row process units is configured to send a third row update value corresponding to a second variable node to the storage element,
wherein the second variable node is updated once in the first plurality of rows, and
wherein the layer update unit is configured to retrieve, from the storage element, the third row update value and generate a second LLR value for the second variable node using the third row update value.

### Claim 8 (depends on 1)

The decoder circuit of claim 1, wherein the layer process unit is configured to:
after processing the first layer of the parity check matrix, processing a second layer of the parity check matrix adjacent to the first layer to update the variable nodes,
wherein the plurality of row process units of the layer process unit are configured to process a second plurality of rows corresponding to the second layer in parallel to generate a second plurality of row update values for the variable nodes.

### Claim 9 (depends on 1)

The decoder circuit of claim 1, wherein each row process unit is configured to generate the first plurality of row update values using a belief propagation algorithm.

### Claim 10 (depends on 9)

The decoder circuit of claim 9, wherein the belief propagation algorithm includes a sum-product algorithm, a min-sum algorithm, a scaled min-sum algorithm, or a variable scaled min-sum algorithm.

### Claim 11

A method, comprising:
receiving an encoded message generated based on a quasi-cyclic low-density parity check (QC-LDPC) code associated with a parity check matrix,
wherein the parity check matrix is constructed by expanding a plurality of elements of a base matrix using a plurality of submatrices respectively,
wherein a submatrix of the plurality of submatrices has a circulant weight greater than one;
processing, by a layer process unit, a plurality of layers of the parity check matrix to generate a plurality of LLR values for a plurality of variable nodes associated with the encoded message,
wherein the processing, by the layer process unit, a first layer includes:
processing, by a plurality of row process units of the layer process unit, a first plurality of rows of the first layer in parallel, to generate a first plurality of row update values for the plurality of variable nodes; and
generating, by a layer update unit of the layer process unit, a first LLR value for a first variable node using a first row update value corresponding to a first row of the parity check matrix and a second row update value corresponding to a second row of the parity check matrix; and
generating a decoded message based on the plurality LLR values.

### Claim 12 (depends on 11)

The method of claim 11, where the first layer corresponds to a row of the base matrix.

### Claim 13 (depends on 12)

The method of claim 12, wherein an element of the row of the base matrix is expanded with a submatrix having a circulant weight greater than one.

### Claim 14 (depends on 11)

The method of claim 11, wherein the processing the first layer further includes:
storing, in a storage element, the first row update value and the second row update value; and
retrieving, by the layer update unit from the storage element, the first and second row update values for generating the first LLR value.

### Claim 15 (depends on 14)

The method of claim 14, wherein the processing the first layer further includes:
generating, by the first row process unit of the plurality of row process units, the first row update value corresponding to the first variable node;
determining, by the first row process unit, that the first variable node is updated two or more times in the first plurality of rows; and
storing, in the storage element, the first row update value.

### Claim 16 (depends on 15)

The method of claim 15, wherein the processing the first layer further includes:
generating, by the first row process unit, a third row update value corresponding to a second variable node, wherein the second variable node is updated once in the first plurality of rows; and
generating, by the first row process unit, a second LLR value for the second variable node using the third row update value.

### Claim 17 (depends on 16)

The method of claim 16, wherein the processing the first layer further includes:
generating, by the first row process unit, a third row update value corresponding to a second variable node, wherein the second variable node is updated once in the first plurality of rows;
storing, in the storage element, the third row update value;
retrieving, by the layer update unit from the storage element, the third row update value; and
generating, by the layer update unit, the second LLR value for the second variable node using the third row update value.

### Claim 18 (depends on 11)

The method of claim 11, further comprising:
after processing the first layer of the parity check matrix, processing a second layer of the parity check matrix adjacent to the first layer to update the variable nodes,
wherein a second plurality of rows corresponding to the second layer are processed in parallel to generate a second plurality of row update values for the plurality of variable nodes.

### Claim 19 (depends on 11)

The method of claim 11, wherein the first plurality of row update values are generated using a belief propagation algorithm.

### Claim 20 (depends on 19)

The method of claim 19, wherein the belief propagation algorithm is selected from the group consisting of a sum-product algorithm, a min-sum algorithm, a scaled min-sum algorithm, and a variable scaled min-sum algorithm.