# US 10,320,421 B2 · Method and device for error correction coding based on high-rate generalized concatenated codes

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

- Number: US 10,320,421 B2
- Document ID: US10320421B2
- Status: Granted
- Kind: B2
- Application number: 15/593,973
- Filed: 2017-05-12
- Published: 2017-11-16
- Granted: 2019-06-11
- Earliest claimed: 2016-05-13
- Assignees: Hyperstone GmbH
- Applicants: Hyperstone GmbH
- Inventors: Juergen Freudenberger; Christoph Baumhof; Jens Spinner
- Web page: https://patentgrep.com/patent/US10320421B2

## CPC

- H03M 13/253: {with concatenated codes}
- G11C 29/52: Protection of memory contents; Detection of errors in memory contents
- H03M 13/1505: {Golay Codes}
- H03M 13/2906: {using block codes (H03M13/2957 takes precedence)}
- H03M 13/293: {with erasure setting}
- H03M 13/1515: {Reed-Solomon codes}
- H03M 13/152: {Bose-Chaudhuri-Hocquenghem [BCH] 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)
- G11C: STATIC STORES (semiconductor memory devices H10B)

## Abstract

Field error correction coding is particularly suitable for applications in non-volatile flash memories. We describe a method for error correction encoding of data to be stored in a memory device, a corresponding method for decoding a codeword matrix resulting from the encoding method, a coding device, and a computer program for performing the methods on the coding device, using a new construction for high-rate generalized concatenated (GC) codes. The codes, which are well suited for error correction in flash memories for high reliability data storage, are constructed from inner nested binary Bose-Chaudhuri-Hocquenghem (BCH) codes and outer codes, preferably Reed-Solomon (RS) codes. For the inner codes extended BCH codes are used, where only single parity-check codes are applied in the first level of the GC code. This enables high-rate codes.

## Claims

### Claim 1

A method of decoding of a codeword matrix, wherein:
the codeword matrix is constructed from L inner nested binary extended Bose-Chaudhuri-Hocquenghem (BCH) codes and L outer codes;
the extended BCH code in a lowest nesting-level of the inner nested BCH codes is a mere single parity-check (SPC) code; and
the extended BCH code in at least one higher nesting-level of the inner nested BCH codes has an error correction capability and is a sub-code of the BCH code of the lowest nesting level;
the decoding comprising:
a first iteration corresponding to the lowest nesting level of the inner extended BCH codes of the codeword matrix and having the following:
applying SPC-decoding to the lines of the second dimension of the codeword matrix with respect to the lowest nesting level of the inner nested extended BCH codes in which the lines of a second dimension of the codeword matrix are encoded in order to obtain an intermediate decoding data matrix of the first iteration and to determine erasure information characterizing lines of the second dimension of the codeword matrix in which an erasure has been detected based on the SPC-decoding;
inferring the information bits contained in the lines of the second dimension of the intermediate decoding data matrix of the first iteration in order to retrieve code symbols of the outer codes in which the lines of a first dimension of the codeword matrix are encoded;
applying outer decoding corresponding to the respective codes used for obtaining the original codeword matrix during encoding, to the retrieved code symbols in the lines of the first dimension of the intermediate decoding data matrix of the first iteration in order to obtain a partial decoding result matrix of the first iteration, wherein the erasure information is used during outer decoding to identify erroneous symbols in the intermediate decoding data matrix of the first iteration;
re-encoding said partial decoding result matrix of the first iteration by applying SPC-encoding to the second dimension of this matrix to obtain are encoded matrix of the first iteration; and
subtracting there-encoded matrix of the first iteration from the codeword matrix in order to obtain a start matrix for a subsequent further iteration; and
for each of the further nesting levels of the inner extended BCH codes of the codeword matrix, a respective further iteration having the following processes:
applying extended BCH-decoding to the lines of the second dimension of the start matrix of the present iteration with respect to the present nesting level of the inner nested extended BCH codes in which the lines of a second dimension of the start matrix of the present iteration are encoded in order to obtain an intermediate decoding data matrix of the present iteration;
inferring the information bits contained in the lines of the second dimension of the intermediate decoding data matrix of the present iteration in order to retrieve code symbols of the outer codes in which the lines of a first dimension of the codeword matrix are encoded;
applying outer decoding corresponding to the respective outer codes used for obtaining the original codeword matrix during encoding, to the retrieved code symbols in the lines of the first dimension of the intermediate decoding data matrix of the present iteration in order to obtain a partial decoding result matrix of the present iteration;
if the present iteration corresponds to the highest nesting level of the inner nested extended BCH codes in the codeword matrix, outputting the partial decoding result matrix of the present iteration as a data matrix resulting from the decoding, and
otherwise, re-encoding the partial decoding result matrix of the present iteration by applying extended BCH-encoding corresponding to the present nesting level to the second dimension of this matrix to obtain are-encoded matrix of the present iteration, and subtracting the re-encoded matrix of the present iteration from the start matrix of the present iteration in order to obtain a start matrix for a subsequent further iteration.

### Claim 2 (depends on 1)

The method according to claim 1, wherein in at least one of the further iterations includes:
a first process of applying extended BCH-decoding further comprises determining erasure information characterizing lines of the second dimension of the start matrix of the present iteration in which an erasure has been detected based on SPC-decoding a SPC-parity bit contained in the extended BCH code of the present iteration; and
a second process of applying outer decoding comprises using the erasure information of the present iteration during outer decoding to identify erroneous symbols in the intermediate decoding data matrix of the present iteration.

### Claim 3 (depends on 1)

The method according to claim 1, the method further comprising:
accessing the codeword matrix from one or more memory devices.

### Claim 4 (depends on 1)

The method according to claim 1, wherein the outer codes are Reed-Solomon (RS) codes, and wherein the outer decoding is RS decoding.

### Claim 5 (depends on 1)

The method according to claim 1, wherein L is a positive integer, and L is greater than two.

### Claim 6 (depends on 1)

The method according to claim 1, wherein the codeword matrix is arranged as a two-dimensional data matrix having a first dimension na equal to a length of the outer codes and a second dimension nb equal to a length of the inner extended BCH codes, wherein a line of a first dimension of a matrix is a row of the matrix and a line of a second dimension thereof is a column of the matrix, or vice versa, and the outer RS codes are defined over a Galois-Field GF(2m1) with m1 elements of each line of the second dimension representing one symbol of the Galois-Field GF(2m1), wherein m1 is a positive integer.

### Claim 7 (depends on 6)

The method according to claim 6, wherein the cordeword matrix is formed by:
applying the L outer codes to respective L*m1 lines of the first dimension of the data matrix such that each of the L outer codes yields a codeword from respective m1 lines of the second dimension and in total L*m1 lines of the resulting intermediate matrix are protected by the outer codes; and
applying the inner nested extended BCH codes to the lines of the second dimension of the intermediate matrix to obtain a codeword matrix comprising the encoded data, with nb−L*m1 lines of the first dimension of the codeword matrix being used for a coding redundancy of the inner nested extended BCH codes and each line of the second dimension of the codeword matrix being a sum of the L codewords of the individual nested extended BCH codes for the respective line.

### Claim 8 (depends on 7)

The method according to claim 7, wherein a codeword bj of a j-th line of the second dimension of the codeword matrix is determined by the following formula:
b
j
=
∑
i
=
0
L
-
1
⁢
b
j
(
i
)
wherein the codewords bj(i) are formed by encoding the symbols aj,i with the extended BCH code B(i) of an ith nesting level, where aj,i is a j-th symbol, of m1 bits, of the ith outer RS code A(i) along the first direction of the intermediate matrix and for this encoding (L−i−1)*m1 zero bits are prefixed or postfixed onto the symbol aj,i.

### Claim 9 (depends on 7)

The method according to claim 7, wherein the outer codes are RS codes, and wherein the code rate of the first RS codeword defined along the direction of the second dimension of the intermediate matrix is lower than the code rate of the Lth RS codeword defined along that direction.

### Claim 10

A decoding device, the decoding device comprising:
a memory controller configured to perform decoding of a codeword matrix wherein:
the codeword matrix is constructed from L inner nested binary extended Bose-Chaudhuri-Hocquenghem (BCH) codes and L outer codes;
the extended BCH code in a lowest nesting-level of the inner nested BCH codes is a mere single parity-check (SPC) code; and
the extended BCH code in at least one higher nesting-level of the inner nested BCH codes has an error correction capability and is a sub-code of the BCH code of the lowest nesting level;
the decoding comprising:
a first iteration corresponding to the lowest nesting level of the inner extended BCH codes of the codeword matrix and having the following processes:
applying SPC-decoding to the lines of the second dimension of the codeword matrix with respect to the lowest nesting level of the inner nested extended BCH codes in which the lines of a second dimension of the codeword matrix are encoded in order to obtain an intermediate decoding data matrix of the first iteration and to determine erasure information characterizing lines of the second dimension of the codeword matrix in which an erasure has been detected based on the SPC-decoding;
inferring the information bits contained in the lines of the second dimension of the intermediate decoding data matrix of the first iteration in order to retrieve code symbols of the outer codes in which the lines of a first dimension of the codeword matrix are encoded;
applying outer decoding corresponding to the respective codes used for obtaining the original codeword matrix during encoding, to the retrieved code symbols in the lines of the first dimension of the intermediate decoding data matrix of the first iteration in order to obtain a partial decoding result matrix of the first iteration, wherein the erasure information is used during outer decoding to identify erroneous symbols in the intermediate decoding data matrix of the first iteration;
re-encoding said partial decoding result matrix of the first iteration by applying SPC-encoding to the second dimension of this matrix to obtain are encoded matrix of the first iteration; and
subtracting there-encoded matrix of the first iteration from the codeword matrix in order to obtain a start matrix for a subsequent further iteration; and
for each of the further nesting levels of the inner extended BCH codes of the codeword matrix, a respective further iteration having the following processes:
applying extended BCH-decoding to the lines of the second dimension of the start matrix of the present iteration with respect to the present nesting level of the inner nested extended BCH codes in which the lines of a second dimension of the start matrix of the present iteration are encoded in order to obtain an intermediate decoding data matrix of the present iteration;
inferring the information bits contained in the lines of the second dimension of the intermediate decoding data matrix of the present iteration in order to retrieve code symbols of the outer RS codes in which the lines of a first dimension of the codeword matrix are encoded;
applying outer RS-decoding corresponding to the respective outer RS codes used for obtaining the original codeword matrix during encoding, to the retrieved code symbols in the lines of the first dimension of the intermediate decoding data matrix of the present iteration in order to obtain a partial decoding result matrix of the present iteration;
if the present iteration corresponds to the highest nesting level of the inner nested extended BCH codes in the codeword matrix, outputting the partial decoding result matrix of the present iteration as a data matrix resulting from the decoding, and
otherwise, re-encoding the partial decoding result matrix of the present iteration by applying extended BCH-encoding corresponding to the present nesting level to the second dimension of this matrix to obtain are-encoded matrix of the present iteration, and subtracting the re-encoded matrix of the present iteration from the start matrix of the present iteration in order to obtain a start matrix for a subsequent further iteration.

### Claim 11 (depends on 10)

The decoding device according to claim 10, wherein the outer codes are Reed-Solomon (RS) codes, and wherein the outer decoding is RS decoding.

### Claim 12 (depends on 10)

The decoding device according to claim 10, wherein L is a positive integer, and L is greater than two.

### Claim 13 (depends on 10)

The decoding device according to claim 10, wherein the codeword matrix is arranged as a two-dimensional data matrix having a first dimension na equal to a length of the outer codes and a second dimension nb equal to a length of the inner extended BCH codes, wherein a line of a first dimension of a matrix is a row of the matrix and a line of a second dimension thereof is a column of the matrix, or vice versa, and the outer RS codes are defined over a Galois-Field GF(2m1) with m1 elements of each line of the second dimension representing one symbol of the Galois-Field GF(2m1), wherein m1 is a positive integer.

### Claim 14 (depends on 13)

The decoding device according to claim 13, wherein the cordeword matrix is formed by:
applying the L outer codes to respective L*m1 lines of the first dimension of the data matrix such that each of the L outer codes yields a codeword from respective m1 lines of the second dimension and in total L*m1 lines of the resulting intermediate matrix are protected by the outer codes; and
applying the inner nested extended BCH codes to the lines of the second dimension of the intermediate matrix to obtain a codeword matrix comprising the encoded data, with nb−L*m1 lines of the first dimension of the codeword matrix being used for a coding redundancy of the inner nested extended BCH codes and each line of the second dimension of the codeword matrix being a sum of the L codewords of the individual nested extended BCH codes for the respective line.

### Claim 15 (depends on 14)

The decoding device according to claim 14, wherein a codeword bj of a j-th line of the second dimension of the codeword matrix is determined by the following formula:
b
j
=
∑
i
=
0
L
-
1
⁢
b
j
(
i
)
wherein the codewords bj(i) are formed by encoding the symbols aj,i with the extended BCH code B(i) of an ith nesting level, where ai,j is a j-th symbol, of m1 bits, of the ith outer RS code A(i) along the first direction of the intermediate matrix and for this encoding (L−1)*m1 zero bits are prefixed or postfixed onto the symbol aj,i.

### Claim 16 (depends on 14)

The decoding device according to claim 14, wherein the outer codes are RS codes, and wherein the code rate of the first RS codeword defined along the direction of the second dimension of the intermediate matrix is lower than the code rate of the Lth RS codeword defined along that direction.

### Claim 17

A decoding system, the decoding system comprising:
non-transitory computer readable medium storing instructions executable by a processor to decode a codeword matrix wherein: the codeword matrix is constructed from L inner nested binary extended Bose-Chaudhuri-Hocquenghem (BCH) codes and L outer codes; the extended BCH code in a lowest nesting-level of the inner nested BCH codes is a mere single parity-check (SPC) code; and the extended BCH code in at least one higher nesting-level of the inner nested BCH codes has an error correction capability and is a sub-code of the BCH code of the lowest nesting level; and wherein decoding the codeword matrix includes:
a first iteration corresponding to the lowest nesting level of the inner extended BCH codes of the codeword matrix and having the following processes:
applying SPC-decoding to the lines of the second dimension of the codeword matrix with respect to the lowest nesting level of the inner nested extended BCH codes in which the lines of a second dimension of the codeword matrix are encoded in order to obtain an intermediate decoding data matrix of the first iteration and to determine erasure information characterizing lines of the second dimension of the codeword matrix in which an erasure has been detected based on the SPC-decoding;
inferring the information bits contained in the lines of the second dimension of the intermediate decoding data matrix of the first iteration in order to retrieve code symbols of the outer codes in which the lines of a first dimension of the codeword matrix are encoded;
applying outer decoding corresponding to the respective codes used for obtaining the original codeword matrix during encoding, to the retrieved code symbols in the lines of the first dimension of the intermediate decoding data matrix of the first iteration in order to obtain a partial decoding result matrix of the first iteration, wherein the erasure information is used during outer decoding to identify erroneous symbols in the intermediate decoding data matrix of the first iteration;
re-encoding said partial decoding result matrix of the first iteration by applying SPC-encoding to the second dimension of this matrix to obtain are encoded matrix of the first iteration; and
subtracting there-encoded matrix of the first iteration from the codeword matrix in order to obtain a start matrix for a subsequent further iteration; and
for each of the further nesting levels of the inner extended BCH codes of the codeword matrix, a respective further iteration having the following processes:
applying extended BCH-decoding to the lines of the second dimension of the start matrix of the present iteration with respect to the present nesting level of the inner nested extended BCH codes in which the lines of a second dimension of the start matrix of the present iteration are encoded in order to obtain an intermediate decoding data matrix of the present iteration;
inferring the information bits contained in the lines of the second dimension of the intermediate decoding data matrix of the present iteration in order to retrieve code symbols of the outer RS codes in which the lines of a first dimension of the codeword matrix are encoded;
applying outer RS-decoding corresponding to the respective outer RS codes used for obtaining the original codeword matrix during encoding, to the retrieved code symbols in the lines of the first dimension of the intermediate decoding data matrix of the present iteration in order to obtain a partial decoding result matrix of the present iteration;
if the present iteration corresponds to the highest nesting level of the inner nested extended BCH codes in the codeword matrix, outputting the partial decoding result matrix of the present iteration as a data matrix resulting from the decoding, and
otherwise, re-encoding the partial decoding result matrix of the present iteration by applying extended BCH-encoding corresponding to the present nesting level to the second dimension of this matrix to obtain are-encoded matrix of the present iteration, and subtracting the re-encoded matrix of the present iteration from the start matrix of the present iteration in order to obtain a start matrix for a subsequent further iteration.

### Claim 18 (depends on 17)

The decoding system according to claim 17, wherein the outer codes are Reed-Solomon (RS) codes, and wherein the outer decoding is RS decoding.

### Claim 19 (depends on 17)

The decoding system according to claim 17, wherein L is a positive integer, and L is greater than two.

### Claim 20 (depends on 17)

The decoding system according to claim 17, wherein the codeword matrix is arranged as a two-dimensional data matrix having a first dimension na equal to a length of the outer codes and a second dimension nb equal to a length of the inner extended BCH codes, wherein a line of a first dimension of a matrix is a row of the matrix and a line of a second dimension thereof is a column of the matrix, or vice versa, and the outer RS codes are defined over a Galois-Field GF(2m1) with m1 elements of each line of the second dimension representing one symbol of the Galois-Field GF(2m1), wherein m1 is a positive integer.