# US 8,543,889 B2 · Method of list decoding and relative decoder 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 8,543,889 B2
- Document ID: US8543889B2
- Status: Granted
- Kind: B2
- Application number: 13/171,716
- Filed: 2011-06-29
- Published: 2011-12-29
- Granted: 2013-09-24
- Earliest claimed: 2010-06-29
- Assignees: STMicroelectronics S.r.l.
- Applicants: Mauro Natuzzi; Angelo Poloni; Stefano Valle
- Inventors: Mauro Natuzzi; Angelo Poloni; Stefano Valle
- Web page: https://patentgrep.com/patent/US8543889B2

## CPC

- H03M 13/1111: {Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms}
- H03M 13/1171: {Parity-check or generator matrices with non-binary elements, e.g. for non-binary LDPC codes}
- H04L 1/0045: {Arrangements at the receiver end}
- 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

A method is for generating, for each check node related to a parity check equation of a LDPC code, signals representing a first output table of corrected values of symbols of a word received through a communication channel and transmitted according to the LDPC code, and signals representing a second output table of the logarithm of the ratio between the respective probability of correctness of the values of same coordinates in the first output table and their corresponding maximum probability of correctness. The method is implemented by processing the components of a first input table of values of a Galois Field of symbols that may have been transmitted and of a second input table of corresponding probability of correctness of each value.

## Claims

### Claim 1

A method of generating, for each check node related to a parity check equation of a LDPC code, a first output table of corrected values of symbols of a word received through a communication channel and transmitted according to the LDPC code, wherein each row of the first output table, from first to last, stores, in order, a most probable value down to a least probable value, and each column of the first output table stores possible values of each symbol, the method also for generating a second output table of a logarithm of a ratio between a respective probability of correctness of values of same coordinates in the first output table and their corresponding maximum probability of correctness, by processing components of a first input table of values of a Galois Field of symbols and of a second input table of corresponding probability of correctness of each value, the method comprising:
filling in a first row of the second output table by copying a first row of the first input table into a first row of the second output table, and filling in the first row of the first output table by computing a most likely symbol that satisfies the parity check equation;
determining probability values of a second row of the second output table for each symbol if one symbol different from a considered one of the received word is assuming its second best value, and determining a corresponding corrected value in the first output table by applying the parity check equation;
determining probability values of a third row of the second output table for each symbol if one symbol different from a considered one of the received word is assuming a value different from its most probable value and a value previously considered in determining the probability values for the second output table, and determining a corresponding corrected value in the first output table by applying the parity check equation; and
determining probability values of fourth and successive rows of the second output table for each symbol, by at least
for each symbol, calculating a first probability value in a case that one symbol different from a considered one of the received word is assuming a value different from its most probable value and a value previously considered, and calculating a second probability value in a case that two symbols different from the considered one of the received word are not assuming their most probable values, and
checking which of the first and second probability values is greater, and determining a corresponding corrected value in the first output table by applying the parity check equation;
outputting the first and second output tables.

### Claim 2 (depends on 1)

The method of claim 1, further comprising filling in the second row of the first and second output tables by:
a1) identifying in the first and second input tables a symbol having a greatest second best probability of correctness;
a2) identifying in the first and second input tables a symbol different from the symbol having the second greatest second best probability of correctness;
a3) generating a corrected value of the second best probability of correctness of the symbol using the parity check equation if a value assumed by the symbol is the second best probability of correctness;
a4) generating corrected values of a second best probability of correctness of all symbols but the symbol using the parity check equation if a value assumed by the symbol is the second best probability of correctness;
a5) filling in the second row of the first output table with the corrected values of the second best probability of correctness of all symbols but the symbol using the parity check equation; and
a6) filling in the second row of the second output table according to Moutput(2, a1)=Minput(2, b1), and Moutput(2, j)=Minput(2, a1) ∀j≠a1, where a1 is the symbol having the greatest second best probability of correctness, and where b1 is the symbol having the second greatest second best probability of correctness.

### Claim 3 (depends on 2)

The method of claim 2, further comprising filling in third and successive rows of the first and second output tables by:
b1) for symbols that have been identified in a previously executed step, repeating al), a3), a5) and a6), preventively discarding values of the first input table already taken into consideration for the same symbol, b2) for the remaining symbols, repeating the operations a2), a4), a5) and a6) as for the symbol different from the symbol having the second greatest second best probability of correctness, discarding values of the first input table already taken into consideration for that same symbol;
b3) for each symbol, checking whether a calculated corrected value has been obtained for the same symbol in a previous step and, if not, repeating at least one of b1) and b2).

### Claim 4 (depends on 3)

The method of claim 3, further comprising, before calculating values of a fourth best down to a least probability of correctness of the symbols:
c1) determining a probability of correctness of a corrected value of the fourth best down to the least best probability of correctness of the considered symbol calculated using the parity check equation if one symbol is not assuming its value of best probability of correctness;
c2) determining the probability of correctness of the corrected value of fourth best down to the least best probability of correctness of the considered symbol calculated using the parity check equation if two symbols are not assuming their values of best probability of correctness; and
c3) if the probability of correctness determined at C2) is greater than probability of correctness determined at step C1), calculating the corrected value of fourth best down to the least best probability of correctness of the considered symbol using the parity check equation if two symbols are not assuming their values of best probability of correctness.

### Claim 5 (depends on 1)

The method of claim 1, wherein the symbols comprise values of a non-binary Galois Field.

### Claim 6

A decoder for decoding symbols of a word received through a communication channel and transmitted according to a LDPC code having at least one check node related to a parity check equation, the decoder generating a first output table of corrected values of the symbols, wherein each row of the first output table stores, in order, a most probable value down to a least probable value and each column of the first output table stores possible values of each symbol, and a second output table of a logarithm of a ratio between a respective probability of correctness of a values in the first output table and their corresponding maximum probability of correctness, by processing the components of a first input table of values of a Galois Field of symbols and of a second input table of a corresponding probability of correctness of each value, the decoder comprising:
processing circuitry configured to
fill in a first row of the second output table by copying a first row of the first input table into a first row of the second output table, and fill in the first row of the first output table by computing a most likely symbol that satisfies the parity check equation;
determine probability values of a second row of the second output table for each symbol if one symbol different from a considered one of the received word is assuming its second best value, and determine a corresponding corrected value in the first output table by applying the parity check equation;
determine probability values of a third row of the second output table for each symbol if one symbol different from a considered one of the received word is assuming a value different from its most probable value and a value previously considered in determining the probability values for the second output table, and determine a corresponding corrected value in the first output table by applying the parity check equation;
determine probability values of fourth and successive rows of the second output table for each symbol, by at least
for each symbol, calculating a first probability value in a case that one symbol different from a considered one of the received word is assuming a value different from its most probable value and a value previously considered, and calculating a second probability value in a case that two symbols different from the considered one of the received word are not assuming their most probable values, and
checking which of the first and second probability values is greater, and determining a corresponding corrected value in the first output table by applying the parity check equation; and
outputting the first and second output tables.

### Claim 7 (depends on 6)

The decoder of claim 6, wherein said processing circuitry is configured to fill in the second row of the first and second output tables by:
a1) identifying in the first and second input tables a symbol having a greatest second best probability of correctness;
a2) identifying in the first and second input tables a symbol different from the symbol having the second greatest second best probability of correctness;
a3) generating a corrected value of the second best probability of correctness of the symbol using the parity check equation if a value assumed by the symbol is the second best probability of correctness;
a4) generating corrected values of a second best probability of correctness of all symbols but the symbol using the parity check equation if a value assumed by the symbol is the second best probability of correctness; and
a5) filling in the second row of the first output table with the corrected values of the second best probability of correctness of all symbols but the symbol using the parity check equation;
a6) filling in the second row of the second output table according to Moutput(2, a1)=Minput(2, b1), and Moutput(2, j)=Minput(2, a1) ∀j≠a1, where a1 is the symbol having the greatest second best probability of correctness, and where b1 is the symbol having the second greatest second best probability of correctness.

### Claim 8 (depends on 7)

The decoder of claim 7, wherein said processing circuitry is configured to fill in third and successive rows of the first and second output tables by:
b1) for symbols that have been identified in a previously executed step, repeating a1), a3), a5) and a6), preventively discarding values of the first input table already taken into consideration for the same symbol;
b2) for the remaining symbols, repeating the operations a2), a4), a5) and a6) as for the symbol different from the symbol having the second greatest second best probability of correctness, discarding values of the first input table already taken into consideration for that same symbol; and
b3) for each symbol, checking whether a calculated corrected value has been obtained for the same symbol in a previous step and, if not, repeating at least one of b1) and b2).

### Claim 9 (depends on 8)

The decoder of claim 8, wherein said processing circuit is configured to, before calculating values of a fourth best down to a least probability of correctness of the symbols:
c1) determine a probability of correctness of a corrected value of the fourth best down to the least best probability of correctness of the considered symbol calculated using the parity check equation if one symbol is not assuming its value of best probability of correctness;
c2) determine the probability of correctness of the corrected value of fourth best down to the least best probability of correctness of the considered symbol calculated using the parity check equation if two symbols are not assuming their values of best probability of correctness; and
c3) if the probability of correctness determined at C2) is greater than probability of correctness determined at step C1), calculate the corrected value of fourth best down to the least best probability of correctness of the considered symbol using the parity check equation if two symbols are not assuming their values of best probability of correctness.

### Claim 10 (depends on 6)

The decoder of claim 6, wherein the symbols comprise values of a non-binary Galois Field.

### Claim 11

A method of generating, for each check node related to a parity check equation of a LDPC code, a first output table of corrected values of symbols of a word transmitted according to the LDPC code, wherein each row of the first output table stores, in order, a most probable value down to a least probable value, and each column of the first output table stores possible values of each symbol, the method also for generating a second output table of a logarithm of a ratio between a respective probability of correctness of values of same coordinates in the first output table and their corresponding maximum probability of correctness, by processing components of a first input table and of a second input table of corresponding probability of correctness of each value, the method comprising:
filling in a first row of the second output table by copying a first row of the first input table into a first row of the second output table, and filling in the first row of the first output table by computing a most likely symbol that satisfies the parity check equation;
determining probability values of a second row of the second output table for each symbol if one symbol different from a considered one of the received word is assuming its second best value, and determining a corresponding corrected value in the first output table by applying the parity check equation;
determining probability values of a third row of the second output table for each symbol if one symbol different from a considered one of the received word is assuming a value different from its most probable value and a value previously considered in determining the probability values for the second output table, and determining a corresponding corrected value in the first output table by applying the parity check equation; and
determining probability values of fourth and successive rows of the second output table for each symbol.

### Claim 12 (depends on 11)

The method of claim 11, further comprising filling in the second row of the first and second output tables by:
a1) identifying in the first and second input tables a symbol having a greatest second best probability of correctness;
a2) identifying in the first and second input tables a symbol different from the symbol having the second greatest second best probability of correctness;
a3) generating a corrected value of the second best probability of correctness of the symbol using the parity check equation if a value assumed by the symbol is the second best probability of correctness;
a4) generating corrected values of a second best probability of correctness of all symbols but the symbol using the parity check equation if a value assumed by the symbol is the second best probability of correctness;
a5) filling in the second row of the first output table with the corrected values of the second best probability of correctness of all symbols but the symbol using the parity check equation; and
a6) filling in the second row of the second output table according to Moutput(2, a1)=Minput(2, b1), and Moutput(2, j)=Minput(2, a1) ∀j≠a1, where a1 is the symbol having the greatest second best probability of correctness, and where b1 is the symbol having the second greatest second best probability of correctness.

### Claim 13 (depends on 12)

The method of claim 12, further comprising filling in third and successive rows of the first and second output tables by:
b1) for symbols that have been identified in a previously executed step, repeating al), a3), a5) and a6), preventively discarding values of the first input table already taken into consideration for the same symbol;
b2) for the remaining symbols, repeating the operations a2), a4), a5) and a6) as for the symbol different from the symbol having the second greatest second best probability of correctness, discarding values of the first input table already taken into consideration for that same symbol; and
b3) for each symbol, checking whether a calculated corrected value has been obtained for the same symbol in a previous step and, if not, repeating at least one of b1) and b2).