# US 11,115,051 B2 · Systems and methods for decoding error correcting codes

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

- Number: US 11,115,051 B2
- Document ID: US11115051B2
- Status: Granted
- Kind: B2
- Application number: 16/663,484
- Filed: 2019-10-25
- Published: 2020-02-20
- Granted: 2021-09-07
- Earliest claimed: 2017-11-14
- Assignees: Innogrit Technologies Co., Ltd.
- Applicants: Innogrit Technologies Co., Ltd.
- Inventors: Yuan-mao Chang; Jie Chen; Chung-Li Wang
- Web page: https://patentgrep.com/patent/US11115051B2

## CPC

- H03M 13/1111: {Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms}
- H03M 13/1108: {Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping}
- H03M 13/3715: {Adaptation to the number of estimated errors or to the channel state}
- H03M 13/658: {Scaling by multiplication or division}
- 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

Systems and methods are provided for decoding a codeword encoded by a linear block code. A method may comprise performing a hard decision decoding on a codeword, determining which check nodes are satisfied and which check nodes are unsatisfied after the hard decision decoding, scheduling a check node processing order by moving at least one unsatisfied check node to be processed ahead of at least one satisfied check node and performing a soft decision decoding on the codeword according to the check node processing order.

## Claims

### Claim 1

A method, comprising:
performing a hard decision decoding on a codeword to generate check constraints satisfaction information by a hard decision decoder, the hard decision decoding being based on a parity check matrix for the codeword being represented in a bipartite graph with symbols in the codeword represented as bit nodes and parity check equations for the codeword represented as check nodes, and the check constrains satisfaction information including which parity check equations are satisfied and which parity check equations are unsatisfied;
sending the check constraints satisfaction information from the hard decision decoder to a soft decision decoder;
determining which check nodes are satisfied and which check nodes are unsatisfied based on which parity check equations are satisfied and which parity check equations are unsatisfied in the check constraints satisfaction information generated by the hard decision decoder;
scheduling a check node processing order based on which parity check equations are satisfied and which parity check equations are unsatisfied in the check constraints satisfaction information generated by the hard decision decoder by moving at least one unsatisfied check node that would be processed after at least one satisfied check node in a sequential order to be processed ahead of the at least one satisfied check node, the sequential order being an order of the parity check equations in the parity check matrix; and
performing a soft decision decoding by the soft decision decoder on the codeword to go over the parity check equations in the parity check matrix according to the check node processing order.

### Claim 2 (depends on 1)

The method of claim 1, wherein the soft decision decoding processes the check nodes in batches and the check node processing order is scheduled by arranging any batch of check nodes containing at least one unsatisfied check node ahead of every batch containing only satisfied check nodes.

### Claim 3 (depends on 1)

The method of claim 1, further comprising updating the check node processing order after each iteration of the soft decision decoding with updated check nodes satisfaction information.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
determining, for a symbol value of the codeword, a number of satisfied check nodes and a number of unsatisfied check nodes for a decoding result of the hard decision decoding;
generating a soft log-likelihood ratio (LLR) for the symbol value based on the number of satisfied check nodes and the number of unsatisfied check nodes; and
performing the soft decision decoding on the codeword using the soft LLR as an input.

### Claim 5 (depends on 4)

The method of claim 4, wherein the soft LLR for the symbol value is generated based on a difference between the number of satisfied check nodes and the number of unsatisfied check nodes.

### Claim 6 (depends on 5)

The method of claim 5, wherein the soft LLR for the symbol value is generated according to an equation P=((#S−#U)*Q+1)*D*X, in which P is the soft LLR for the symbol value, #S is the number of satisfied check nodes, #U is the number of unsatisfied check nodes, Q is a scaling factor, D is the symbol value, X is an original LLR magnitude assigned to the symbol value, “*” is a multiplication sign, and the scaling factor Q and the original LLR magnitude X are selected to satisfy a hardware constraint.

### Claim 7 (depends on 4)

The method of claim 4, wherein the hard decision decoding is an iterative decoding and the soft LLR is generated after each iteration of the hard decision decoding, and the soft LLR used as the input to the soft decision decoding is the soft LLR generated after any iteration.

### Claim 8 (depends on 1)

The method of claim 1, further comprising recording unsatisfied check nodes in a first array and satisfied check nodes in a second array, wherein the check node processing order is scheduled by arranging check nodes recorded in the first array to be processed ahead of check nodes recorded in the second array.

### Claim 9

A method, comprising:
performing a hard decision decoding on a codeword to generate check constraints satisfaction information by a first decoder, the hard decision decoding being based on a parity check matrix for the codeword being represented in a bipartite graph with symbols in the codeword represented as bit nodes and parity check equations for the codeword represented as check nodes, the check constraints satisfaction information including which parity check equations are satisfied and which parity check equations are unsatisfied;
sending the check constraints satisfaction information from the first decoder to a second decoder;
determining which check nodes are satisfied and which check nodes are unsatisfied based on which parity check equations are satisfied and which parity check equations are unsatisfied in the check constraints satisfaction information generated by the first decoder;
scheduling a check node processing order for a soft decision decoding based on which parity check equations are satisfied and which parity check equations are unsatisfied in the check constraints satisfaction information generated by the first decoder, wherein the soft decision decoding processes the check nodes in batches and the check node processing order is scheduled by moving at least one batch of check nodes containing at least one unsatisfied check node that would be processed after at least one batch of check nodes containing no unsatisfied check node in a sequential order ahead of the at least one batch of check nodes containing no unsatisfied check node, the sequential order being an order of the parity check equations in the parity check matrix; and
performing the soft decision decoding by the second decoder on the codeword to go over the parity check equations in the parity check matrix according to the check node processing order.

### Claim 10 (depends on 9)

The method of claim 9, further comprising updating the check node processing order after each iteration of the soft decision decoding with updated check nodes satisfaction information.

### Claim 11 (depends on 9)

The method of claim 9, further comprising:
determining, for a symbol value of the codeword, a number of satisfied check nodes and a number of unsatisfied check nodes for a decoding result of the hard decision decoding;
generating a soft log-likelihood ratio (LLR) for the symbol value based on the number of satisfied check nodes and the number of unsatisfied check nodes; and
performing the soft decision decoding on the codeword using the soft LLR as an input.

### Claim 12 (depends on 11)

The method of claim 11, wherein the soft LLR for the symbol value is generated based on a difference between the number of satisfied check nodes and the number of unsatisfied check nodes.

### Claim 13 (depends on 12)

The method of claim 12, wherein the soft LLR for the symbol value is generated according to an equation P=((#S−#U)*Q+1)*D*X, in which P is the soft LLR for the symbol value, #S is the number of satisfied check nodes, #U is the number of unsatisfied check nodes, Q is a scaling factor, D is the symbol value, X is an original LLR magnitude assigned to the symbol value, “*” is a multiplication sign, and the scaling factor Q and the original LLR magnitude X are selected to satisfy a hardware constraint.

### Claim 14 (depends on 11)

The method of claim 11, wherein the hard decision decoding is an iterative decoding and the soft LLR is generated after each iteration of the hard decision decoding, and the soft LLR used as the input to the soft decision decoding is the soft LLR generated after any iteration.

### Claim 15 (depends on 9)

The method of claim 9, further comprising recording batch(es) containing unsatisfied check nodes in a first array and batch(es) satisfied check nodes in a second array, wherein the check node processing order is scheduled by arranging batch(es) of check nodes recorded in the first array to be processed ahead of batch(es) of check nodes recorded in the second array.

### Claim 16

A system, comprising:
a hard decision decoder comprising a bit flip control to perform a hard decision decoding on a codeword and generate check constraints satisfaction information, the hard decision decoding being based on a parity check matrix for the codeword being represented in a bipartite graph with symbols in the codeword represented as bit nodes and parity check equations for the codeword represented as check nodes, the check constraints satisfaction information including which parity check equations are satisfied and which parity check equations are unsatisfied; and
a soft decision decoder coupled to the hard decision decoder to receive the check constraints satisfaction information sent from the hard decision decoder, the soft decision decoder comprising:
a decoding order scheduler to:
determine which check nodes are satisfied and which check nodes are unsatisfied based on which parity check equations are satisfied and which parity check equations are unsatisfied in the check constraints satisfaction information generated by the hard decision decoder; and
schedule a check node processing order based on which parity check equations are satisfied and which parity check equations are unsatisfied in the check constraints satisfaction information generated by the hard decision decoder by moving at least one unsatisfied check node to be processed that would be processed after at least one batch of check nodes containing no unsatisfied check node in a sequential order ahead of at least one satisfied check node, the sequential order being an order of the parity check equations in the parity check matrix; and
a bit node processor and a check node processor to perform a soft decision decoding on the codeword to go over the parity check equations in the parity check matrix according to the check node processing order.

### Claim 17 (depends on 16)

The system of claim 16, wherein the decoding order scheduler is configured to process the check nodes in batches, and the check node processing order is scheduled by arranging any batch of check nodes containing at least one unsatisfied check node ahead of every batch containing only satisfied check nodes.

### Claim 18 (depends on 16)

The system of claim 16, wherein the decoding order scheduler is configured to update the check node processing order after each iteration of the soft decision decoding with updated check nodes satisfaction information.

### Claim 19 (depends on 16)

The system of claim 16, further comprising a soft log-likelihood ratio (LLR) generator comprising circuitry configured to:
determine, for a symbol value of the codeword, a number of satisfied check nodes and a number of unsatisfied check nodes for a decoding result of the hard decision decoding; and
generate a soft log-likelihood ratio (LLR) for the symbol value based on the number of satisfied check nodes and the number of unsatisfied check nodes, wherein the soft decision decoder further comprises circuitry to perform the soft decision decoding on the codeword using the soft LLR as an input.

### Claim 20 (depends on 19)

The system of claim 19, wherein the soft LLR generator is configured to generate the soft LLR according to an equation P=((#S−#U)*Q+1)*D*X, in which P is the soft LLR for the symbol value, #S is the number of satisfied check nodes, #U is the number of unsatisfied check nodes, Q is a scaling factor, D is the symbol value, X is an original LLR magnitude assigned to the symbol value, and “*” is a multiplication sign, wherein the scaling factor Q and the original LLR magnitude X are selected to satisfy a hardware constraint.