# US 10,312,937 B2 · Early termination technique for LDPC decoder architecture

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

- Number: US 10,312,937 B2
- Document ID: US10312937B2
- Status: Granted
- Kind: B2
- Application number: 15/619,168
- Filed: 2017-06-09
- Published: 2018-05-03
- Granted: 2019-06-04
- Earliest claimed: 2016-11-02
- Assignees: QUALCOMM Incorporated
- Applicants: QUALCOMM Incorporated
- Inventors: Vincent Loncke; Yi Cao; Girish Varatkar
- Web page: https://patentgrep.com/patent/US10312937B2

## CPC

- 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/1108: {Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping}
- H03M 13/1111: {Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms}
- H03M 13/1128: {Judging correct decoding and iterative stopping criteria other than syndrome check and upper limit for decoding iterations}
- H03M 13/114: {Shuffled, staggered, layered or turbo decoding schedules}
- 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/1188: {wherein in the part with the double-diagonal at least one column has an odd column weight equal or greater than three}
- H03M 13/6566: {Implementations concerning memory access contentions}
- H04L 1/0051: {Stopping criteria}
- H04L 1/0054: {Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms}
- H04L 1/0057: {Block codes (H04L1/0061, H04L1/0064 take 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)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Certain aspects of the present disclosure generally relate to methods and apparatus for decoding low density parity check (LDPC) codes, and more particularly to early termination techniques for low-density parity-check (LDPC) decoder architecture.

## Claims

### Claim 1

A method for performing low-density parity-check (LDPC) decoding, the method comprising:
receiving log-likelihood ratios (LLRs) corresponding to bits encoded using LDPC encoding;
updating the LLRs corresponding to the encoded bits corresponding to columns of a parity check matrix (PCM), the LLRs indicating a probability of a value of each of the encoded bits, wherein each row of the PCM corresponds to a parity check for the encoded bits;
iteratively decoding the encoded bits using the PCM, wherein for each iteration of decoding, for each row of the PCM, the LLRs are updated based on a processing of the row of the PCM;
maintaining an overall parity bit;
setting the overall parity bit to true at a beginning of an iteration of decoding;
for each processing of the row of the PCM, adding a result of the parity check for the LLRs to the overall parity bit during the iteration of decoding;
maintaining a sign flip bit;
setting the sign flip bit to true at the beginning of the iteration of decoding;
setting the sign flip bit to false when a sign of any LLR changes during the iteration of decoding; and
stopping iteratively decoding the encoded bits when the sign flip bit and the overall parity bit are set to true at an end of the iteration of decoding.

### Claim 2 (depends on 1)

The method of claim 1, wherein iteratively decoding the encoded bits comprises utilizing a layered LDPC decoding technique.

### Claim 3 (depends on 1)

The method of claim 1, further comprising determining if a sign of any LLR changes based on a corresponding outdated a posteriori LLR and a corresponding updated a posteriori LLR.

### Claim 4 (depends on 3)

The method of claim 3, wherein processing of the row of the PCM comprises determining for each of the encoded bits an a posteriori LLR for the row of the PCM, wherein for a first set of the encoded bits, determining the a posteriori LLR comprises using a first number of outdated LLRs, and wherein for a second set of the encoded bits, determining the a posteriori LLR comprises using a second number of updated bit LLRs, wherein the first set of the encoded bits and the second set of the encoded bits comprise all of the encoded bits.

### Claim 5 (depends on 1)

The method of claim 1, wherein setting the sign flip bit to false when a sign of any LLR changes during the iteration of decoding comprises setting the sign flip bit to false when a sign of any LLR changes after processing of a first row of the PCM during the iteration.

### Claim 6

An apparatus for performing low-density parity-check (LDPC) decoding, the apparatus comprising:
a memory; and
a processor, the memory and processor being configured to:
receive log-likelihood ratios (LLRs) corresponding to bits encoded using LDPC encoding;
update the LLRs corresponding to the encoded bits corresponding to columns of a parity check matrix (PCM), the LLRs indicating a probability of a value of each of the encoded bits, wherein each row of the PCM corresponds to a parity check for the encoded bits;
iteratively decode the encoded bits using the PCM, wherein for each iteration of decoding, for each row of the PCM, the LLRs are updated based on a processing of the row of the PCM;
maintain an overall parity bit;
set the overall parity bit to true at a beginning of an iteration of decoding;
for each processing of the row of the PCM, add a result of the parity check for the LLRs to the overall parity bit during the iteration of decoding;
maintain a sign flip bit;
set the sign flip bit to true at the beginning of the iteration of decoding;
set the sign flip bit to false when a sign of any LLR changes during the iteration of decoding; and
stop iteratively decoding the encoded bits when the sign flip bit and the overall parity bit are set to true at an end of the iteration of decoding.

### Claim 7 (depends on 6)

The apparatus of claim 6, wherein the memory and processor being configured to iteratively decode the encoded bits comprises the memory and processor being configured to utilize a layered LDPC decoding technique.

### Claim 8 (depends on 6)

The apparatus of claim 6, wherein the memory and processor are further configured to determine if a sign of any LLR changes based on a corresponding outdated a posteriori LLR and a corresponding updated a posteriori LLR.

### Claim 9 (depends on 8)

The apparatus of claim 8, wherein processing of the row of the PCM comprises determining for each of the encoded bits an a posteriori LLR for the row of the PCM, wherein for a first set of the encoded bits, determining the a posteriori LLR comprises using a first number of outdated LLRs, and wherein for a second set of the encoded bits, determining the a posteriori LLR comprises using a second number of updated bit LLRs, wherein the first set of the encoded bits and the second set of the encoded bits comprise all of the encoded bits.

### Claim 10 (depends on 6)

The apparatus of claim 6, wherein the memory and processor being configured to set the sign flip bit to false when a sign of any LLR changes during the iteration of decoding comprises the memory and processor being configured to set the sign flip bit to false when a sign of any LLR changes after processing of a first row of the PCM during the iteration.

### Claim 11

A non-transitory computer readable medium having instructions stored thereon that when executed by an apparatus cause the apparatus to perform a method for performing low-density parity-check (LDPC) decoding, the method comprising:
receiving log-likelihood ratios (LLRs) corresponding to bits encoded using LDPC encoding;
updating the LLRs corresponding to the encoded bits corresponding to columns of a parity check matrix (PCM), the LLRs indicating a probability of a value of each of the encoded bits, wherein each row of the PCM corresponds to a parity check for the encoded bits;
iteratively decoding the encoded bits using the PCM, wherein for each iteration of decoding, for each row of the PCM, the LLRs are updated based on a processing of the row of the PCM;
maintaining an overall parity bit;
setting the overall parity bit to true at a beginning of an iteration of decoding;
for each processing of the row of the PCM, adding a result of the parity check for the LLRs to the overall parity bit during the iteration of decoding;
maintaining a sign flip bit;
setting the sign flip bit to true at the beginning of the iteration of decoding;
setting the sign flip bit to false when a sign of any LLR changes during the iteration of decoding; and
stopping iteratively decoding the encoded bits when the sign flip bit and the overall parity bit are set to true at an end of the iteration of decoding.

### Claim 12 (depends on 11)

The non-transitory computer readable medium of claim 11, wherein iteratively decoding the encoded bits comprises utilizing a layered LDPC decoding technique.

### Claim 13 (depends on 11)

The non-transitory computer readable medium of claim 11, wherein the method further comprises determining if a sign of any LLR changes based on a corresponding outdated a posteriori LLR and a corresponding updated a posteriori LLR.

### Claim 14 (depends on 13)

The non-transitory computer readable medium of claim 13, wherein processing of the row of the PCM comprises determining for each of the encoded bits an a posteriori LLR for the row of the PCM, wherein for a first set of the encoded bits, determining the a posteriori LLR comprises using a first number of outdated LLRs, and wherein for a second set of the encoded bits, determining the a posteriori LLR comprises using a second number of updated bit LLRs, wherein the first set of the encoded bits and the second set of the encoded bits comprise all of the encoded bits.

### Claim 15 (depends on 11)

The non-transitory computer readable medium of claim 11, wherein setting the sign flip bit to false when a sign of any LLR changes during the iteration of decoding comprises setting the sign flip bit to false when a sign of any LLR changes after processing of a first row of the PCM during the iteration.

### Claim 16

An apparatus for performing low-density parity-check (LDPC) decoding, the apparatus comprising:
means for receiving log-likelihood ratios (LLRs) corresponding to bits encoded using LDPC encoding;
means for updating the LLRs corresponding to the encoded bits corresponding to columns of a parity check matrix (PCM), the LLRs indicating a probability of a value of each of the encoded bits, wherein each row of the PCM corresponds to a parity check for the encoded bits;
means for iteratively decoding the encoded bits using the PCM, wherein for each iteration of decoding, for each row of the PCM, the LLRs are updated based on a processing of the row of the PCM;
means for maintaining an overall parity bit;
means for setting the overall parity bit to true at a beginning of an iteration of decoding;
means for, for each processing of the row of the PCM, adding a result of the parity check for the LLRs to the overall parity bit during the iteration of decoding;
means for maintaining a sign flip bit;
means for setting the sign flip bit to true at the beginning of the iteration of decoding;
means for setting the sign flip bit to false when a sign of any LLR changes during the iteration of decoding; and
means for stopping iteratively decoding the encoded bits when the sign flip bit and the overall parity bit are set to true at an end of the iteration of decoding.

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein iteratively means for decoding the encoded bits comprises means for utilizing a layered LDPC decoding technique.

### Claim 18 (depends on 16)

The apparatus of claim 16, further comprising means for determining if a sign of any LLR changes based on a corresponding outdated a posteriori LLR and a corresponding updated a posteriori LLR.

### Claim 19 (depends on 18)

The apparatus of claim 18, wherein processing of the row of the PCM comprises determining for each of the encoded bits an a posteriori LLR for the row of the PCM, wherein for a first set of the encoded bits, determining the a posteriori LLR comprises using a first number of outdated LLRs, and wherein for a second set of the encoded bits, determining the a posteriori LLR comprises using a second number of updated bit LLRs, wherein the first set of the encoded bits and the second set of the encoded bits comprise all of the encoded bits.

### Claim 20 (depends on 16)

The apparatus of claim 16, wherein means for setting the sign flip bit to false when a sign of any LLR changes during the iteration of decoding comprises means for setting the sign flip bit to false when a sign of any LLR changes after processing of a first row of the PCM during the iteration.