# US 2016/0365873 A1 · Non-Binary LDPC Codes Over Non-Associative Finite Division Near Rings

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

- Number: US 2016/0365873 A1
- Document ID: US20160365873A1
- Status: Published application
- Kind: A1
- Application number: 14/734,749
- Filed: 2015-06-09
- Published: 2016-12-15
- Earliest claimed: 2015-06-09
- Assignees: Broadcom Corporation
- Applicants: Broadcom Corporation
- Inventors: Matthias KORB; Andrew Blanksby
- Web page: https://patentgrep.com/patent/US20160365873A1

## CPC

- H03M 13/1114: {Merged schedule message passing algorithm with storage of sums of check-to-bit node messages or sums of bit-to-check node messages, e.g. in order to increase the memory efficiency}
- H03M 13/1111: {Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms}
- 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/1171: {Parity-check or generator matrices with non-binary elements, e.g. for non-binary LDPC codes}
- 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

The present disclosure is directed to an apparatus and method for decoding non-binary LDPC codes over non-associative finite division near rings. A non-associative finite division near ring is a type of algebraic structure that includes a finite set of elements on which the operations of addition and multiplication are defined. The operation of addition is commutative, associative, and closed, and may have an additive identity for all elements in the finite set. The operation of multiplication is closed but not commutative or associative, and has a multiplicative inverse but not a multiplicative identity for all elements in the finite set. The two operations of addition and multiplication may be related by the distributive property.

## Claims

### Claim 1

A message passing (MP) decoder, comprising:
a plurality of variable-nodes;
a plurality of check-nodes; and
a permutation network configured to receive messages from the plurality of check-nodes for decoding a non-binary low-density parity-check (LDPC) code over a non-associative finite division near ring, permute the messages in accordance with a Cayley table that describes a multiplication operation of the non-associative finite division near ring, and provide the permuted messages to the plurality of variable-nodes.

### Claim 2 (depends on 1)

The MP decoder of claim 1, wherein the plurality of check-nodes are configured to compute the messages in accordance with a sum-product MP decoding algorithm, a min-sum MP decoding algorithm, a min-max MP decoding algorithm, a Fourier transform MP decoding algorithm, or a layered decoding algorithm.

### Claim 3 (depends on 1)

The MP decoder of claim 1, wherein the plurality of check-nodes are configured to compute each of the messages in an extrinsic manner.

### Claim 4 (depends on 1)

The MP decoder of claim 1, wherein the MP decoder is implemented for a Binary Symmetric channel, an Additive White Gaussian Noise channel, a Fading channel, or an Erasure channel.

### Claim 5 (depends on 1)

The MP decoder of claim 1, wherein the Cayley table is given by:
x
0
1
2
3
0
0
0
0
0
1
3
2
0
1
2
2
1
3
0
3
0
1
3
2,
x
0
1
2
3
0
0
0
0
0
1
3
0
2
1
2
2
3
1
0
3
2
1
3
0,
or
x
0
1
2
3
0
0
0
0
0
1
2
0
1
3
2
1
2
3
0
3
1
3
2
0
where the value at the intersection of each row and column in the Cayley table is the product of the corresponding row and column numbers.

### Claim 6 (depends on 1)

The MP decoder of claim 1, wherein the Cayley table is given by:
x
0
1
2
3
0
0
0
0
0
1
3
1
0
2
2
2
1
0
3
3
2
0
1
3
3
0
2
3
1,
x
0
1
2
3
0
0
0
0
0
1
2
3
0
1
2
1
3
0
2
3
1
0
3
2
3
0
1
2
3,
or
x
0
1
2
3
0
0
0
0
0
1
3
1
0
2
2
2
1
0
3
3
2
0
1
3
3
0
2
3
1
where the value at the intersection of each row and column in the Cayley table is the product of the corresponding row and column numbers.

### Claim 7 (depends on 1)

The MP decoder of claim 1, wherein the permutation network is further configured to permute the messages in accordance with a parity-check matrix of the non-binary LDPC code.

### Claim 8 (depends on 1)

The MP decoder of claim 1, wherein the permutation network is further configured to be dynamically reconfigured to permute messages in accordance with a Cayley table that describes a multiplication operation of a finite Galois field or general linear group.

### Claim 9

A method, comprising:
receiving a message from a check-node for decoding a non-binary low-density parity-check (LDPC) code over a non-associative finite division near ring;
permuting the message in accordance with a Cayley table that describes a multiplication operation of the non-associative finite division near ring; and
providing the permuted message to a variable-node.

### Claim 10 (depends on 9)

The method of claim 9, further comprising:
receiving, by the check node, messages from a plurality of variable-nodes connected to the check-node; and
computing, by the check node, the message, in an extrinsic manner, as a function of the messages from the plurality of variable-nodes.

### Claim 11 (depends on 9)

The method of claim 9, wherein the Cayley table is given by:
x
0
1
2
3
0
0
0
0
0
1
3
2
0
1
2
2
1
3
0
3
0
1
3
2,
x
0
1
2
3
0
0
0
0
0
1
3
0
2
1
2
2
3
1
0
3
2
1
3
0,
or
x
0
1
2
3
0
0
0
0
0
1
2
0
1
3
2
1
2
3
0
3
1
3
2
0
where the value at the intersection of each row and column in the Cayley table is the product of the corresponding row and column numbers.

### Claim 12 (depends on 9)

The method of claim 9, wherein the Cayley table is given by:
x
0
1
2
3
0
0
0
0
0
1
3
1
0
2
2
2
1
0
3
3
2
0
1
3
3
0
2
3
1,
x
0
1
2
3
0
0
0
0
0
1
2
3
0
1
2
1
3
0
2
3
1
0
3
2
3
0
1
2
3,
or
x
0
1
2
3
0
0
0
0
0
1
3
1
0
2
2
2
1
0
3
3
2
0
1
3
3
0
2
3
1
where the value at the intersection of each row and column in the Cayley table is the product of the corresponding row and column numbers.

### Claim 13 (depends on 9)

The method of claim 9, wherein permuting the message further comprises:
permuting the message in accordance with a parity-check matrix of the non-binary LDPC code.

### Claim 14 (depends on 9)

The method of claim 9, further comprising:
receiving a message from the variable-node for decoding the non-binary LDPC code over the non-associative finite division near ring;
permuting the message from the variable-node in accordance with the Cayley table that describes the multiplication operation of the non-associative finite division near ring; and
providing the permuted message from the variable-node to the check-node.

### Claim 15

A message passing (MP) decoder, comprising:
a variable-node;
a check-node; and
a permutation network configured to receive a message from the check-node for decoding a non-binary low-density parity-check (LDPC) code over a non-associative finite division near ring, permute the message in accordance with a Cayley table that describes a multiplication operation of the non-associative finite division near ring, and provide the permuted message to the variable-node.

### Claim 16 (depends on 15)

The MP decoder of claim 15, wherein the Cayley table is given by:
x
0
1
2
3
0
0
0
0
0
1
3
2
0
1
2
2
1
3
0
3
0
1
3
2,
x
0
1
2
3
0
0
0
0
0
1
3
0
2
1
2
2
3
1
0
3
2
1
3
0,
or
x
0
1
2
3
0
0
0
0
0
1
2
0
1
3
2
1
2
3
0
3
1
3
2
0
where the value at the intersection of each row and column in the Cayley table is the product of the corresponding row and column numbers.

### Claim 17 (depends on 15)

The MP decoder of claim 15, wherein the Cayley table is given by:
x
0
1
2
3
0
0
0
0
0
1
3
1
0
2
2
2
1
0
3
3
2
0
1
3
3
0
2
3
1,
x
0
1
2
3
0
0
0
0
0
1
2
3
0
1
2
1
3
0
2
3
1
0
3
2
3
0
1
2
3,
or
x
0
1
2
3
0
0
0
0
0
1
3
1
0
2
2
2
1
0
3
3
2
0
1
3
3
0
2
3
1
where the value at the intersection of each row and column in the Cayley table is the product of the corresponding row and column numbers.

### Claim 18

A method, comprising:
receiving a message to be encoded for a non-binary low-density parity-check (LDPC) code over a non-associative finite division near ring;
encoding the message based on a generator matrix or a parity check matrix in accordance with a Cayley table that describes a multiplication operation of the non-associative finite division near ring to produce a codeword; and
providing the codeword as output.

### Claim 19 (depends on 18)

The method of claim 18, wherein the Cayley table is given by:
x
0
1
2
3
0
0
0
0
0
1
3
2
0
1
2
2
1
3
0
3
0
1
3
2,
x
0
1
2
3
0
0
0
0
0
1
3
0
2
1
2
2
3
1
0
3
2
1
3
0,
or
x
0
1
2
3
0
0
0
0
0
1
2
0
1
3
2
1
2
3
0
3
1
3
2
0
where the value at the intersection of each row and column in the Cayley table is the product of the corresponding row and column numbers.

### Claim 20 (depends on 18)

The method of claim 18, wherein the Cayley table is given by:
x
0
1
2
3
0
0
0
0
0
1
3
1
0
2
2
2
1
0
3
3
2
0
1
3
3
0
2
3
1,
x
0
1
2
3
0
0
0
0
0
1
2
3
0
1
2
1
3
0
2
3
1
0
3
2
3
0
1
2
3,
or
x
0
1
2
3
0
0
0
0
0
1
3
1
0
2
2
2
1
0
3
3
2
0
1
3
3
0
2
3
1
where the value at the intersection of each row and column in the Cayley table is the product of the corresponding row and column numbers.
