# US 2022/0094372 A1 · Efficient encoding for non-binary error correction codes

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

- Number: US 2022/0094372 A1
- Document ID: US20220094372A1
- Status: Published application
- Kind: A1
- Application number: 17/031,066
- Filed: 2020-09-24
- Published: 2022-03-24
- Earliest claimed: 2020-09-24
- Assignees: Gylicon Ltd
- Applicants: Gylicon Ltd
- Inventors: Claudio Tocalli
- Web page: https://patentgrep.com/patent/US20220094372A1

## CPC

- 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/1171: {Parity-check or generator matrices with non-binary elements, e.g. for non-binary LDPC codes}
- H03M 13/118: {Parity check matrix structured for simplifying encoding, e.g. by having a triangular or an approximate triangular structure (H03M13/1165 takes precedence)}
- H03M 13/155: {Shortening or extension of codes}
- H03M 13/2735: {Interleaver using powers of a primitive element, e.g. Galois field [GF] interleaver}
- G06F 11/1048: {using arrangements adapted for a specific error detection or correction feature}
- 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)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for encoding information bits with a Q-ary linear error correction code defined over a binary-extension Galois field GF(2k), and defined by a quasi-cyclic parity-check matrix comprising: first, second and third circulant sub-matrices respectively comprising first, second and third circulants respectively having first, second and third shifts and being defined respectively by first, second and third parameters belonging to the Galois field GF(2k), said second parameter being the inverse of the first parameter, and the second shift being equal to a difference between a number of rows of each circulant and the first shift. The method comprises determining: a first set of parity-check bits according to a fourth circulant having a fourth shift equal to a difference between said number of rows and said first and third shifts and being defined by the multiplicative inverse of a fourth parameter given by a product between the first and third parameters, and to the second and third circulant sub-matrices, and a second set of parity-check bits according to the determined first set of parity-check bits and said first and second circulant sub-matrices.

## Claims

### Claim 1

A method for encoding, in a solid state storage device, information bits with a Q-ary linear error correction code defined over a binary-extension Galois field GF(2k), wherein the Q-ary linear error correction code is defined by a quasi-cyclic parity-check matrix having an information section associated with the information bits and a parity section associated with parity bits, wherein the parity section has an approximate lower triangular form and comprises a plurality of circulants, and wherein the parity section comprises:
a first circulant sub-matrix which comprises a first circulant having a first shift and being defined by a first parameter belonging to the Galois field GF(2k);
a second circulant sub-matrix which has a triangular structure and comprises a second circulant having a second shift and being defined by a second parameter belonging to the Galois field GF(2k), said second parameter being the inverse of the first parameter, the second shift being equal to a difference between a number of rows of each circulant and the first shift;
a third circulant sub-matrix which comprises a third circulant having a third shift and being defined by a third parameter belonging to the Galois field GF(2k);
and
a fourth circulant sub-matrix,
the method comprising:
determining a first set of parity-check bits according to the information bits, to said second and third circulant sub-matrices, and to a fourth circulant, the fourth circulant having a fourth shift and being defined by the multiplicative inverse of a fourth parameter given by a product between the first and third parameters, wherein the fourth shift is equal to a difference between said number of rows and said first and third shifts, and
determining a second set of parity-check bits according to the determined first set of parity-check bits, to said first and second circulant sub-matrices and to the information bits.

### Claim 2 (depends on 1)

The method of claim 1, wherein the information section of the parity-check matrix comprises a fifth and a sixth circulant sub-matrices, said determining a first set of parity-check bits being further performed according to said fifth and a sixth circulant sub-matrices.

### Claim 3 (depends on 2)

The method of claim 2, wherein said determining the first set of parity-check bits comprises determining the first set of parity-check bits according to an amount given by:
the sum between the fifth circulant sub-matrix, the sixth circulant sub-matrix, and the third circulant sub-matrix multiplied by the inverse of the second circulant sub-matrix.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
periodically and/or aperiodically updating the fifth and sixth circulant sub-matrices and said amount according to the updated fifth and sixth circulant sub-matrices, and
determining the first set of parity-check bits according to said updated amount.

### Claim 5 (depends on 1)

The method of claim 1, wherein the information section of the parity-check matrix comprises a fifth circulant sub-matrix, said determining a second set of parity-check bits being further performed according to said fifth circulant sub-matrix.

### Claim 6 (depends on 1)

The method of claim 1, wherein the Q-ary linear error correction code is a Q-ary “Low-Density Parity-Check” (LDPC) code.

### Claim 7

A controller for a solid state storage device, wherein the controller is configured for encoding information bits with a Q-ary linear error correction code defined over a binary-extension Galois field GF(2k), wherein the Q-ary linear error correction code is defined by a quasi-cyclic parity-check matrix having an information section associated with the information bits and a parity section associated with parity bits, wherein the parity section has an approximate lower triangular form and comprises a plurality of circulants, the parity section comprises:
a first circulant sub-matrix which comprises a first circulant having a first shift and being defined by a first parameter belonging to the Galois field GF(2k);
a second circulant sub-matrix which has a triangular structure and comprises a second circulant having a second shift and being defined by a second parameter belonging to the Galois field GF(2k), said second parameter being the inverse of the first parameter, the second shift being equal to a difference between a number of rows of each circulant and the first shift;
a third circulant sub-matrix which comprises a third circulant having a third shift and being defined by a third parameter belonging to the Galois field GF(2k); and
a fourth circulant sub-matrix,
the controller being configured for:
determining a first set of parity-check bits according to the information bits, to said second and third circulant sub-matrices, and to a fourth circulant, the fourth circulant having a fourth shift and being defined by the multiplicative inverse of a fourth parameter given by a product between the first and third parameters, wherein the fourth shift is equal to a difference between said number of rows and said first and third shifts;
determining a second set of parity-check bits according to the determined first set of parity-check bits, to said first and second circulant sub-matrices and to the information bits, and
storing the information bits and the first and second sets of parity-check bits in memory cells of the solid state storage device.

### Claim 8 (depends on 7)

The controller of claim 7, wherein the information section of the parity-check matrix comprises a fifth and a sixth circulant sub-matrices, the controller being configured to determine said first set of parity-check bits further according to said fifth and a sixth circulant sub-matrices.

### Claim 9 (depends on 8)

The controller of claim 8, wherein the controller is configured to determine the first set of parity-check bits according to an amount given by:
the sum between the fifth circulant sub-matrix, the sixth circulant sub-matrix, and the third circulant sub-matrix multiplied by the inverse of the second circulant sub-matrix.

### Claim 10 (depends on 9)

The controller of claim 9, further configured to:
periodically and/or aperiodically update the fifth and sixth circulant sub-matrices and said amount according to the updated fifth and sixth circulant sub-matrices, and
determine the first set of parity-check bits according to said updated amount.

### Claim 11 (depends on 7)

The controller of claim 7, wherein the information section of the parity-check matrix comprises a fifth circulant sub-matrix, the controller being configured to determine said second set of parity-check bits further according to said fifth circulant sub-matrix.

### Claim 12 (depends on 7)

The controller of claim 7, wherein the Q-ary linear error correction code is a Q-ary “Low-Density Parity-Check” (LDPC) code.

### Claim 13

A solid state storage device comprising memory cells and a controller, wherein the controller is configured for encoding information bits with a Q-ary linear error correction code defined over a binary-extension Galois field GF(2k), wherein the Q-ary linear error correction code is defined by a quasi-cyclic parity-check matrix having an information section associated with the information bits and a parity section associated with parity bits, wherein the parity section has an approximate lower triangular form and comprises a plurality of circulants, wherein the parity section comprises:
a first circulant sub-matrix which comprises a first circulant having a first shift and being defined by a first parameter belonging to the Galois field GF(2k);
a second circulant sub-matrix which has a triangular structure and comprises a second circulant having a second shift and being defined by a second parameter belonging to the Galois field GF(2k), said second parameter being the inverse of the first parameter, the second shift being equal to a difference between a number of rows of each circulant and the first shift;
a third circulant sub-matrix which comprises a third circulant having a third shift and being defined by a third parameter belonging to the Galois field GF(2k); and
a fourth circulant sub-matrix,
the controller being configured for:
determining a first set of parity-check bits according to the information bits, to said second and third circulant sub-matrices, and to a fourth circulant, the fourth circulant having a fourth shift and being defined by the multiplicative inverse of a fourth parameter given by a product between the first and third parameters, wherein the fourth shift is equal to a difference between said number of rows and said first and third shifts, and
determining a second set of parity-check bits according to the determined first set of parity-check bits, to said first and second circulant sub-matrices and to the information bits, and
storing the information bits and the first and second sets of parity-check bits in the memory cells of the solid state storage device.

### Claim 14 (depends on 13)

The solid state storage device of claim 13, wherein the information section of the parity-check matrix comprises a fifth and a sixth circulant sub-matrices, the controller being configured to determine said first set of parity-check bits further according to said fifth and a sixth circulant sub-matrices.

### Claim 15 (depends on 14)

The solid state storage device of claim 14, wherein the controller is configured to determine the first set of parity-check bits according to an amount given by:
the sum between the fifth circulant sub-matrix, the sixth circulant sub-matrix, and the third circulant sub-matrix multiplied by the inverse of the second circulant sub-matrix.

### Claim 16 (depends on 15)

The solid state storage device of claim 15, wherein the controller is further configured to:
periodically and/or aperiodically update the fifth and sixth circulant sub-matrices and said amount according to the updated fifth and sixth circulant sub-matrices, and
determine the first set of parity-check bits according to said updated amount.

### Claim 17 (depends on 13)

The solid state storage device of claim 13, wherein the information section of the parity-check matrix comprises a fifth circulant sub-matrix, the controller being configured to determine said second set of parity-check bits further according to said fifth circulant sub-matrix.

### Claim 18 (depends on 13)

The solid state storage device of claim 13, wherein the Q-ary linear error correction code is a Q-ary “Low-Density Parity-Check” (LDPC) code.
