# US 2011/0087946 A1 · Low complexity finite precision decoders and apparatus for ldpc codes

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

- Number: US 2011/0087946 A1
- Document ID: US20110087946A1
- Status: Published application
- Kind: A1
- Application number: 12/900,584
- Filed: 2010-10-08
- Published: 2011-04-14
- Earliest claimed: 2009-10-09
- Assignees: STMicroelectronics, SA; University of Cergy-Pontoise; University of Arizona
- Inventors: Shiva K. PLANJERY; Shashi Kiran CHILAPPAGARI; Bane VASIC; David DECLERCQ
- Web page: https://patentgrep.com/patent/US20110087946A1

## CPC

- H03M 13/1171: {Parity-check or generator matrices with non-binary elements, e.g. for non-binary LDPC codes}
- 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/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/1142: {using trapping sets}
- H03M 13/3707: {Adaptive decoding and hybrid decoding, e.g. decoding methods or techniques providing more than one decoding algorithm for one code}
- H03M 13/6577: {Representation or format of variables, register sizes or word-lengths and quantization}
- H04L 1/005: {Iterative decoding, including iteration between signal detection and decoding operation}
- 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

In this invention, a new class of finite precision multilevel decoders for low-density parity-check (LDPC) codes is presented. These decoders are much lower in complexity compared to the standard belief propagation (BP) decoder. Messages utilized by these decoders are quantized to certain levels based on the number of bits allowed for representation in hardware. A message update function specifically defined as part of the invention, is used to determine the outgoing message at the variable node, and the simple min operation along with modulo 2 sum of signs is used at the check node. A general methodology is provided to obtain the multilevel decoders, which is based on reducing failures due to trapping sets and improving the guaranteed error-correction capability of a code. Hence these decoders improve the iterative decoding process on finite length graphs and have the potential to outperform the standard floating-point BP decoder in the error floor region. The description and apparatus of 3-bit decoders for column-weight three LDPC codes is also presented.

## Claims

### Claim 1

A message passing decoder, propagating messages from a non-binary finite alphabet, for use with any LDPC codes, comprising a variable node processor defined by a message update function at a variable node.

### Claim 2 (depends on 1)

The message passing decoder of claim 1, wherein the LDPC codes have a fixed column-weight.

### Claim 3 (depends on 1)

The message passing decoder of claim 1 comprising a linear threshold update function.

### Claim 4 (depends on 1)

The message passing decoder of claim 1 comprising a non-linear threshold update function.

### Claim 5 (depends on 1)

The message passing decoder of claims 1 comprising an update function using 3-bits for message representation.

### Claim 6 (depends on 1)

The message passing decoder of claim 1 further comprising a channel quantizer.

### Claim 7 (depends on 1)

The message passing decoder of claim 1 further comprising a check node processor.

### Claim 8

A message passing decoder, propagating messages from a non-binary finite alphabet, for use with any LDPC codes, comprising variable node processors defined by a plurality of message update functions at the variable nodes, to improve the error-correction capability of the code.

### Claim 9 (depends on 8)

The message passing decoder of claim 8, wherein the LDPC codes have a fixed column-weight.

### Claim 10 (depends on 8)

The message passing decoder of claim 8 comprising a plurality of linear threshold update functions.

### Claim 11 (depends on 8)

The message passing decoder of claim 8 comprising a plurality of non-linear threshold update functions.

### Claim 12 (depends on 8)

The message passing decoder of claim 8 comprising a plurality of either linear or non-linear threshold update functions.

### Claim 13 (depends on 8)

The message passing decoder of claim 8 comprising a plurality update functions, all using 3-bits for message representation.

### Claim 14 (depends on 8)

The message passing decoder of claim 8 in which the plurality of update functions is the same for all variable nodes, and update functions may change from one iteration to another.

### Claim 15 (depends on 8)

The message passing decoder of claim 8 in which the plurality of update functions is the same for all iterations, and update functions may be different for different variable nodes.

### Claim 16 (depends on 8)

The message passing decoder of claim 8 in which the plurality of update functions are combined.

### Claim 17 (depends on 8)

The message passing decoder of claim 8 further comprising a channel quantizer.

### Claim 18 (depends on 8)

The message passing decoder of claim 8 further comprising a check node processor.

### Claim 19

A finite alphabet message passing decoding method comprising:
using a specifically defined message update function to update messages at a variable node; and
using a min operation with a modulo 2 sum of signs operation to update messages at the check node.

### Claim 20 (depends on 19)

The method of claim 19, where the specifically defined message update function is chosen to decode isolated subgraphs that could potentially lead to decoding failures.

### Claim 21 (depends on 19)

The method of claim 19 further comprising:
using a plurality of specifically defined message update functions to update messages at the variable node.

### Claim 22 (depends on 21)

The method of claim 21, where the plurality of specifically defined message update functions are chosen to decode isolated subgraphs that could potentially lead to decoding failures.