# US 2012/0240002 A1 · Method for controlling a basic parity node of a non-binary ldpc code decoder, and corresponding basic parity node processor

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

- Number: US 2012/0240002 A1
- Document ID: US20120240002A1
- Status: Published application
- Kind: A1
- Application number: 13/319,033
- Filed: 2010-05-05
- Published: 2012-09-20
- Earliest claimed: 2009-05-05
- Assignees: Universite De Bretagne Sud
- Inventors: Emmanuel Boutillon; Laura Conde-Canencia
- Web page: https://patentgrep.com/patent/US20120240002A1

## 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/6502: {Reduction of hardware complexity or efficient processing}
- H03M 13/6505: {Memory efficient implementations}
- 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 method for controlling an elementary parity node of a decoder for decoding non-binary LDPC codes or a code decoder using at least one non-binary parity constraint, and to the corresponding elementary parity node. The elementary parity node receives first and second input lists (U1,U2) having nm elements sorted in ascending or descending order, nm being greater than 1, and gives an output list (Uout) of nm, elements sorted in said ascending or descending order, nm, being greater than 1, each element of the output list (Uout) being the result of a computing operation φ between an element of the first input list (U1) and an element of the second input list (U2). A limited number of candidates is selected for each element of the output list to be generated so as to reduce the number of operations to be carried out in the elementary parity node.

## Claims

### Claim 1

A method for controlling an elementary parity node of a decoder for decoding non-binary LDPC codes or a code decoder using at least one non-binary parity constraint, said elementary parity node receiving first and second lists (U1,U2), referred to as first and second input lists, having nm elements sorted in an order defined among a descending order and an ascending order, nm being greater than 1, and delivering a list (Uout), referred to as the output list, having nm′ elements sorted in said defined order, nm′ being greater than 1, each element of the output list (Uout), being the result of a computing operation φ between an element of the first input list (U1) and an element of the second input list (U2), said computing operation φ being such that, if a≧b and c≧d, then φ(a, c)≧φ(b, d), said method including the following steps:
a) selecting the p first elements of the first input list (U1) and the first element of the second input list (U2), p being a predetermined number less than nm,
b) carrying out computing operations φ between the elements selected from the first input list (U1) and the element selected from the second input (U2) list so as to generate a list of p candidate elements for the output list,
c) determining, from among the p candidate elements, the candidate element having the highest value if the defined order is the descending order, or the candidate element having the lowest value if the defined order is the ascending order, and inserting it into the output list (Uout), the candidate element inserted into the output list being the result of the computing operation φ between an element of order i of the first input list and an element of order j of the second input list, i and j being between 1 and nm,
d) selecting, according to a predetermined criterion, the element of order i of the first input list and the element of order j+1 of the second input list or the element of order i+1 of the first input list and the element of order j of the second input list,
e) carrying out a computing operation φ between the elements selected in the preceding step so as to generate a new candidate element, and replacing, in the list of p candidate elements, the last candidate element inserted into the output list by said new candidate element,
f) determining, from among the p candidate elements, the candidate element having the highest value if the defined order is the descending order, or the candidate element having the lowest value if the defined order is the ascending order, and inserting it into the output list (Uout) in the order of determination, the candidate element inserted into the output list being the result of the computing operation between an element of order i of the first input list and an element of order j of the second input list, and
g) repeating steps d) to f) until the output list comprises nm′ elements.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the number p is equal to
⌈
-
1
+
-
7
+
8

n
m
′
2
⌉
wherein ┌x┐ represents the smallest integer greater than or equal to the real number x.

### Claim 3 (depends on 1)

The method according to claim 1, wherein, according to a first predetermined criterion, the selection made in step d) depends on the order i of the element of the first input list (U1) and/or the order j of the element of the second input list (U2) associated with the candidate element inserted into the output list.

### Claim 4 (depends on 1)

The method according to claim 1, wherein, according to a second predetermined criterion, the selection made in step d) depends on the order i of the element of the first input list (U1) and the order j of the element of the second input list (U2) associated with the candidate element inserted into the output list and on a flag representative of the selection made in the preceding step d).

### Claim 5 (depends on 1)

The method according to claim 1, wherein the elements of the input list and the output list are log likelihood ratios.

### Claim 6 (depends on 5)

The method according to claim 5, wherein the computing operation is an addition operation.

### Claim 7 (depends on 1)

The method according to claim 1, wherein, each of the elements of said first and second input lists (U1,U2) being associated with a symbol in the Galois field, the step f) further includes, after determining the candidate having the lowest or highest value, a step for determining the symbol associated with said determined candidate element, said determined candidate element being inserted into the output list if and only if the symbol associated with said determined candidate element is not associated with a candidate element present in the output list.

### Claim 8 (depends on 1)

An elementary parity node, including:
first and second inputs for receiving first and second lists, said first and second input lists (U1,U2), having nm elements sorted in an order defined among a descending order and an ascending order, nm being greater than 1,
an output for delivering a list (Uout), referred to as an output list, having nm′ elements sorted in the defined order, nm′ being greater than or equal to 1, each element of the output list being the result of a computing operation φ between an element of the first input list and an element of the second input list, said computing operation φ being such that, if a≧b and c≧d then φ(a, c)≧φ(b, d),
first storage means for storing the elements of said first and second input lists (U1,U2),
a computing circuit for carrying out computing operations φ between elements of the first input list and elements of the second input list, which are stored in said first storage means, so as to generate a candidate element upon each operation,
second storage means for storing the candidate elements computed by said computing means,
a comparison circuit for determining, from among the candidate elements stored in the second storage means, the candidate element having the highest value if the defined order is the descending order, or the candidate element having the lowest value if the defined order is the ascending order, and providing said determined candidate element to the output, the candidate element provided to the output being the result of the computing operation φ between an element of order i of the first input list and an element of order j of the second input list, i and j being between 1 and nm, and
a control circuit for controlling the selection of the elements stored in said first storage means, to be provided to the computing circuit and storage of the computed candidate elements in the second storage means,
wherein the second storage means include p registers for storing p candidate elements, p being a predetermined number lower than nm,
the comparison circuit is capable of providing information to the control circuit, which is representative of the orders i and j associated with said candidate element provided to the output,
and the control circuit is capable of controlling said first storage means and said second storage means for implementing the control method according to claim 1.
