Method and device for error correction coding based on high-rate generalized concatenated codes

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

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.

2. 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.

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

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

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

6. The method according to claim 1, wherein the codeword matrix is arranged as a two-dimensional data matrix having a first dimension n.sub.a equal to a length of the outer codes and a second dimension n.sub.b 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(2.sup.m1) with m.sub.1 elements of each line of the second dimension representing one symbol of the Galois-Field GF(2.sup.m1), wherein m.sub.1 is a positive integer.

7. The method according to claim 6, wherein the cordeword matrix is formed by: applying the L outer codes to respective L*m.sub.1 lines of the first dimension of the data matrix such that each of the L outer codes yields a codeword from respective m.sub.1 lines of the second dimension and in total L*m.sub.1 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 n.sub.bL*m.sub.1 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.

8. The method according to claim 7, wherein a codeword b.sub.j of a j-th line of the second dimension of the codeword matrix is determined by the following formula: $b_j=\underset{i=0}{\overset{L-1}{.Math.}}{b}_j^{\left(i\right)}$ wherein the codewords b.sub.j.sup.(i) are formed by encoding the symbols a.sub.j,i with the extended BCH code B.sup.(i) of an i.sup.th nesting level, where a.sub.j,i is a j-th symbol, of m.sub.1 bits, of the i.sup.th outer RS code A.sup.(i) along the first direction of the intermediate matrix and for this encoding (Li1)*m1 zero bits are prefixed or postfixed onto the symbol a.sub.j,i.

9. 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 L.sup.th RS codeword defined along that direction.

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.

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

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

13. The decoding device according to claim 10, wherein the codeword matrix is arranged as a two-dimensional data matrix having a first dimension n.sub.a equal to a length of the outer codes and a second dimension n.sub.b 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(2.sup.m1) with m.sub.1 elements of each line of the second dimension representing one symbol of the Galois-Field GF(2.sup.m1), wherein m.sub.1 is a positive integer.

14. The decoding device according to claim 13, wherein the cordeword matrix is formed by: applying the L outer codes to respective L*m.sub.1 lines of the first dimension of the data matrix such that each of the L outer codes yields a codeword from respective m.sub.1 lines of the second dimension and in total L*m.sub.1 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 n.sub.bL*m.sub.1 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.

15. The decoding device according to claim 14, wherein a codeword b.sub.j of a j-th line of the second dimension of the codeword matrix is determined by the following formula: $b_j=\underset{i=0}{\overset{L-1}{.Math.}}{b}_j^{\left(i\right)}$ wherein the codewords b.sub.j.sup.(i) are formed by encoding the symbols a.sub.j,i with the extended BCH code B.sup.(i) of an i.sup.th nesting level, where a.sub.i,j is a j-th symbol, of m.sub.1 bits, of the i.sup.th outer RS code A.sup.(i) along the first direction of the intermediate matrix and for this encoding (L1)*m1 zero bits are prefixed or postfixed onto the symbol a.sub.j,i.

16. 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 L.sup.th RS codeword defined along that direction.

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.

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

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

20. The decoding system according to claim 17, wherein the codeword matrix is arranged as a two-dimensional data matrix having a first dimension n.sub.a equal to a length of the outer codes and a second dimension n.sub.b 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(2.sup.m1) with m.sub.1 elements of each line of the second dimension representing one symbol of the Galois-Field GF(2.sup.m1), wherein m.sub.1 is a positive integer.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 schematically illustrates a coding device in the form of a memory controller within a memory system, according to a preferred embodiment of the present invention;

(2) FIG. 2 schematically illustrates an encoding scheme for the transformation of a data matrix containing information to be encoded into a corresponding codeword matrix, according to a preferred embodiment of the present invention;

(3) FIG. 3 schematically illustrates a simplified version of the encoding scheme of FIG. 2 in more detail, according to a preferred embodiment of the present invention;

(4) FIG. 4 schematically illustrates a decoding scheme for a codeword matrix obtainable from the encoding scheme of FIG. 2, according to a preferred embodiment of the present invention; and

(5) FIG. 5 shows a diagram plotting the code rate vs. signal-to-noise ratio for exemplary GC codes according to the present invention in comparison with long BCH codes with algebraic decoding.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

(6) Referring now to the figures of the drawing in detail and first, particularly, to FIG. 1 thereof, there is shown an exemplary memory system 1 comprising a memory controller 2 and a memory device 3, which may particularly be a flash memory device, e.g. of the NAND type. The memory system 1 is connected to a host 4, such as a computer to which the memory system 1 pertains, via a set of address lines A1, a set of data lines D1 and set of control lines C1. The memory controller 2 comprises a processing unit 2a and an internal memory 2b, typically of the embedded type, and is connected to the memory 3 via an address bus A2, a data bus D2, and a control bus C2. Accordingly, host 4 has indirect read and/or write access to the memory 3 via its connections A1, D1 and C1 to the memory controller 2, which in turn can directly access the memory 3 via the buses A2, D2 and C2. Each of the set of lines respectively buses A1, D1, C1, A2, D2 and C2 may be implemented by one or more individual communication lines.

(7) The memory controller 2 is also configured as a coding device and thus adapted to perform the encoding and decoding methods of the present invention, particularly as described below with reference to FIGS. 2 to 4. To that purpose, the memory controller 2 may comprise a computer program residing in its internal memory 2b which is configured to perform one or more of these coding methods when executed on the processing unit 2a of the memory controller 2. Alternatively, the program may for example reside, in whole or in part, in memory 3 or in an additional program memory (not shown) or may even be implemented by a hard-wired circuit.

(8) The coding methods illustrated by FIGS. 2 to 4 are based on the use of GC codes for error correction in memories, such as flash memories, that require high-rate codes. The GC codes are constructed from inner nested binary Bose-Chaudhuri-Hocquenghem (BCH) codes and outer Reed-Solomon (RS) codes. For the inner codes extended BCH codes are used, where single parity-check codes are applied in the first level of the GC code (cf. FIGS. 2 and 3). This construction enables high-rate GC codes. A corresponding decoding method for the GC codes is illustrated in FIG. 4. A detailed general discussion of GC codes can be found in [5].

(9) Reference is now made to FIG. 2, which illustrates the encoding process of a GC code, according to a preferred embodiment of the present invention. The GC codeword is arranged in an n.sub.bn.sub.a matrix, where n.sub.a and n.sub.b are the lengths of the outer and inner codes, respectively. The encoding starts with the outer codes. The rows are protected by L Reed-Solomon codes of length n.sub.a, i.e. L denotes the number of levels. m elements of each column represent one symbol from the Galois field GF(2.sup.m). Hence, m neighboring rows form a codeword of an outer code A.sup.(i), i=0 L1. Note that the code rate of the outer codes increases from level to level. The outer codes protect Lm rows of the matrix. The remaining n.sub.bLm rows are used for the redundancy of the inner codes.

(10) The shaded area in FIG. 2 illustrates the redundancy of the component codes that are filled by outer and inner encoding. After the outer encoding the columns of the codeword matrix are encoded with binary inner codes of length n.sub.b. Each column of the codeword matrix is the sum of L codewords of nested linear BCH codes.
B.sup.(L-1)B.sup.(L-2) . . . B.sup.(0)(1)

(11) Hence, a higher level code is a sub-code of its predecessor, where the higher levels have higher error correcting capabilities, i.e., t.sub.b,L-1t.sub.b,L-2 . . . , t.sub.b,0, where t.sub.b,i is the error correcting capability of level i. The code dimensions are k.sup.(0)=Lm, k.sup.(1)=(L1)m, . . . , k.sup.(L-1)=m.

(12) The codeword b.sub.j of the j-th column is the sum of L codewords.

(13) $\begin{array}{cc}{b}_j=\underset{i=0}{\overset{L-1}{.Math.}}{b}_j^{\left(i\right)}& \left(2\right)\end{array}$

(14) These codewords b.sub.j.sup.(i) are formed by encoding the symbols a.sub.j,i with the corresponding sub-code B.sup.(i), where a.sub.j,i is the j-th symbol (m bits) of the outer code A.sup.(i). For this encoding (Li1)m zero bits are prefixed onto the symbol a.sub.j,i. Note that the j-th column b.sub.j is a codeword of B.sup.(0), because of the linearity of the nested codes.

(15) FIG. 3 illustrates this encoding scheme in more detail based on a simple exemplary case (Example 1) where L=2, m=3 and n.sub.a=n.sub.b=7. Thus, in this example there are only L=2 levels and with m.sub.1=m=3 bits per symbol the outer RS codes are constructed over the Galois field GF(2.sup.3), while for the sake of simplicity the inner extended BCH codes are defined over GF(2.sup.1), i.e. m.sub.2=1. In a first step S1, a data structure representing a n.sub.bn.sub.a (i.e. 77) matrix D is filled with data to be encoded and consisting of 24 information bits i.sub.0 to i.sub.23. The filling scheme corresponds to that of the data matrix D in FIG. 2. Accordingly, in the first level (i=0) the number of information bits is lower than in the second level (i=1) and the remaining prefixed bits of both levels are reserved for the redundancy added by the outer encoding in a next step S2. Each symbol comprises three neighboring bits of the same column, such that for example in the fifth column of D the bits i.sub.0, i.sub.3 and i.sub.6 form a first symbol in the column, and the bits i.sub.11, i.sub.16 and i.sub.21 form another symbol. In addition, the final row of the matrix D is reserved for redundancy to be added by the inner encoding in a further step S3.

(16) In the outer encoding step S2, the information in each of the two levels i=0 and i=1 is encoded by a respective RS code, wherein the code dimension of the outer RS code for level 0 is only k.sub.a.sup.(0)=3 while the code dimension of level 1 is increased to k.sub.a.sup.(1)=5. Performing the outer encoding step S2 results in an intermediate matrix A comprising the code symbols a.sub.i,j, wherein each of these symbols a.sub.i,j comprises m.sub.1=3 bits and the rows of the matrix A are codewords of the outer code.

(17) In the second level i=1, the respective extended BCH code B.sup.(1), which unlike the SPC code does have an error correction capability of 1 Bit, is applied in each column of the matrix A to the respective symbol a.sub.j,1. As in this simple example this is already the final level, no prefixing of 0 symbols is necessary. Again, an SPC code is applied to the resulting BCH codeword and added in the final row of the respective column j.

(18) In order to arrive at the final GC codeword matrix C, on a column by column basis all of the individual codewords b.sub.j.sup.(i) of all levels i of column j are added according to formula (2) above in order to receive the corresponding codeword b.sub.j which then forms column j of the resulting GC codeword matrix C, as again exemplarily illustrated in FIG. 3 for column j=4.

(19) In a further example (Example 2) corresponding to FIG. 2, we consider a GC code suitable for error correction in flash memories. The GC code is designed for 2 KB information blocks, i.e., a code which can be used to store 2 KB of data plus 4 bytes of meta information. For this GC code we use L=13 levels with inner nested BCH codes over GF (2.sup.7), i.e. m.sub.2=7, and outer RS codes over GF (2.sup.9) (i.e. m.sub.1=9). In the first level i=0, we apply single parity-check codes SPC. Hence, all inner codes are extended BCH codes of length n.sub.b=13.Math.9+1=118.

(20) The outer RS codes are constructed over the Galois field GF (2.sup.9). Hence, the code dimension of the inner codes is reduced by m.sub.1=9 bits with each level. The GC code is constructed from L=13 outer RS codes of length n.sub.a=152. The parameters of the codes are summarized in Table I, where we use the same RS code in each of levels 4 to 12. The code has overall code dimension k=m .sub.f=0.sup.L-1k.sub.a,j=16416 and length n=n.sub.a.Math.n.sub.b=17936.

(21) In the inner encoding step S3 each of the symbols a.sub.i,j of the intermediate matrix A is individually encoded by a corresponding inner code in the form of an extended BCH code B.sup.(i). In the first level i=0, the respective extended BCH code B.sup.(0) is a mere Single Parity Check (SPC) code. Accordingly, as exemplarily illustrated in FIG. 3 for symbol a.sub.4,0, each of symbols a.sub.0,j, of level 0 (j=0, . . . , 6) is encoded by prefixing (Li1)m.sub.1, i.e. (201)*3=3 zero bits (i.e. a 0 symbol) onto the symbol and applying an SPC code to the two symbols which is added in the final row of the column representing a resulting codeword b.sub.j.sup.(0) for column j and level 0.

(22) TABLE-US-00002 TABLE I j k.sub.b,j d.sub.b,j k.sub.a,j d.sub.a,j 0 117 2 84 69 1 108 4 130 23 2 99 6 136 17 3 90 8 142 11 4-12 81 12 148 5

(23) Table I shows parameters of the example code. In the table, k.sub.b,j and d.sub.b,j are the code dimension and minimum Hamming Distance of the binary inner code of level j. The terms k.sub.a,j and d.sub.a,j are the code dimension and minimum Hamming Distance of the outer RS codes.

(24) This code has a code rate R=0.915. It is also able to correct burst errors. The minimum distance of all outer RS code is greater than or equal to five. Hence, each outer code can correct at least two erroneous symbols and consequently two columns of the codeword matrix may be corrupted by an arbitrary number of errors.

(25) FIG. 4 schematically illustrates a corresponding decoding scheme for a codeword matrix r obtainable, in principle, from the encoding scheme of FIG. 2, according to a preferred embodiment of the present invention. In fact, the codeword matrix r to be decoded may differ from the original codeword matrix C resulting from application of the encoding scheme of FIG. 2 when the data to be decoded was previously encoded (e.g. before storing it to a memory), by one or more erroneous symbols caused by an undesired modification of the original codeword matrix C. Such modification might for example be caused by one or more failing memory cells within the memory device, by memory degradation, by write or read disturbs or by other impacts on the data.

(26) The decoder, e.g. of the coding device in memory controller 2 of FIG. 1, processes the received data matrix r level by level starting with i=0 up to the last level i=n with n=L1, where i is the index of the current level. FIG. 4 depicts the decoding steps Si-1 to Si-5. First the columns of the data matrix r are decoded with respect to B.sup.(i) (Si-1) and the information bits have to be inferred (re-image, Si-2) in order to retrieve the code symbols a.sub.i,j of A.sup.(i), where j is the column index. If all symbols of the code A.sup.(i) are inferred the RS code can be decoded (Si-3). At this point a partial decoding result a; is available. Finally, this result has to be re-encoded (Si-4) using B.sup.(i). The estimated codewords of the inner code B.sup.(i) are subtracted (Si-5) from the codeword matrix before the next level can be decoded.

(27) A similar encoding and decoding process is also described in detail in [14]. However, in deviation thereof, according to the present invention in the first level i=0, only error detection for the single parity-check codes can be applied (S0-1). The single parity-check code can detect any error of odd weight. If an error is detected in column j, the corresponding symbol a.sub.0,j is considered an erasure. After the evaluation of the single parity-check codes error and erasure decoding for the RS code can be applied (cf. [15]). Starting with the second level, the structure of the nested-BCH codes can be exploited, i.e. a BCH code can be decoded that can correct a single bit error per codeword. Due to the extension of the BCH code any error of weight two can be detected. In this case, a decoding failure is declared for the inner code, where the decoding failures of the inner codes are regarded as erased symbols of the RS code. Hence, error and erasure decoding is used in all levels of the RS code.

(28) FIG. 5 illustrates error correction performance of an exemplary GC code according to the present invention. Specifically, it shows a diagram plotting the code rate vs. signal-to-noise ratio SNR (E.sub.b/N.sub.0) for the exemplary GC code in comparison with long BCH codes with algebraic decoding. As performance measure, the code rate that is required to guarantee an overall block error rate of less than 10.sup.16 for a given channel error probability is used. Clearly, the comparison shows that the achievable code rate of the GC code is higher than the code rate of the long BCH codes across almost all values of the SNR.

(29) All individual codes of this exemplary GC code are constructed similar to the code presented in Example 2 above. In particular, the inner codes are chosen according to Table I above, whereas the error correcting capability of the outer codes is adapted to obtain the highest possible code rate for a channel error probability. Note that in this example, the overall code rate of the GC code is at most R=0.99, because of the choice of the inner code. In contrast, the codes presented in [2], [4] only have a code rate less than or equal to 0.9.

(30) While above at least one exemplary embodiment of the present invention has been described, it has to be noted that a great number of variations thereto exists. Furthermore, it is appreciated that the described exemplary embodiments only illustrate non-limiting examples of how the present invention can be implemented and that it is not intended to limit the scope, the application or the configuration of the herein-described apparatus' and methods. Rather, the preceding description will provide the person skilled in the art with constructions for implementing at least one exemplary embodiment of the invention, wherein it is understood that various changes of functionality and the arrangement of the elements of the exemplary embodiment can be made, without deviating from the subject-matter defined by the appended claims and their legal equivalents.

REFERENCES

(31) [1] A. Fahrner, H. Griesser, R. Klarer, and V. Zyablov, Low-complexity GEL codes for digital magnetic storage systems, IEEE Transactions on Magnetics, vol. 40, no. 4, pp. 3093-3095, July 2004. [2] J. Freudenberger, U. Kaiser, and J. Spinner, Concatenated code constructions for error correction in non-volatile memories, in Int. Symposium on Signals, Systems, and Electronics (ISSSE), Potsdam, October 2012, pp. 1-6. [3] J. Freudenberger, J. Spinner, and S. Shavgulidze, Generalized concatenated codes for correcting two-dimensional clusters of errors and independent errors, in Int. Conference on Communication and Signal Processing (CSP), Castelldefels-Barcelona, February 2014, pp. 1-5. [4] J. Spinner and J. Freudenberger, Decoder architecture for generalized concatenated codes, IET Circuits, Devices & Systems, vol. 9, no. 5, pp. 328-335, 2015. [5] I. Dumer, Concatenated codes and their multilevel generalizations, in Handbook of Coding Theory, Vol. II, Elsevier, Amsterdam, 1998. [6] M. Bossert, Channel coding for telecommunications, Wiley, 1999. [7] V. Zyablov, S. Shavgulidze, and M. Bossert, An introduction to generalized concatenated codes, European Transactions on Telecommunications, vol. 10, no. 6, pp. 609-622, 1999. [8] R. Micheloni, A. Marelli, and R. Ravasio, Error Correction Codes for Non-Volatile Memories, Springer, 2008. [9] X. Zhang and K. K. Parhi, High-speed architectures for parallel long BCH encoders, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 13, no. 7, pp. 872-877, 2005. [10] F. Sun, S. Devarajan, K. Rose, and T. Zhang, Design of on-chip error correction systems for multilevel NOR and NAND flash memories, IET Circuits, Devices Systems, vol. 1, no. 3, pp. 241-249, June 2007. [11] E. Yaakobi, J. Ma, L. Grupp, P. Siegel, S. Swanson, and J. Wolf, Error characterization and coding schemes for flash memories, in IEEE GLOBECOM Workshops, December 2010, pp. 1856-1860. [12] E. Yaakobi, L. Grupp, P. Siegel, S. Swanson, and J. Wolf, Characterization and error-correcting codes for TLC flash memories, in Computing, Networking and Communications (ICNC), 2012 International Conference on, January 2012, pp. 486-491. [13] J. Freudenberger and J. Spinner, A configurable Bose-Chaudhuri-Hocquenghem codec architecture for flash controller applications, Journal of Circuits, Systems, and Computers, vol. 23, no. 2, pp. 1-15, February 2014. [14] J. Spinner and J. Freudenberger, Design and implementation of a pipelined decoder for generalized concatenated codes, in Proceedings of 27th Symposium on Integrated Circuits and Systems Design (SBCCI), Aracaju, Brazil, September 2014, pp. 1-16. [15] L. Weiburn and J. Cavers, Improved performance of Reed-Solomon decoding with the use of pilot signals for erasure generation, in Vehicular Technology Conference, 1998. VTC 98. 48th IEEE, vol. 3, May 1998, pp. 1930-1934 vol. 3. [16] U. Wachsmann, R. Fischer, and J. Huber, Multilevel codes: theoretical concepts and practical design rules, IEEE Transactions on Information Theory, vol. 45, no. 5, pp. 1361-1391, July 1999. [17] J. Spinner and J. Freudenberger, Soft input decoding of generalized concatenated codes using a stack decoding algorithm, in Proceedings of 2nd BW-CAR Symposium on Information and Communication Systems (SlnCom), December 2015, pp. 1-5.

(32) The following is a summary list of reference numerals and the corresponding structure used in the above description of the invention: 1 memory system 2 memory controller, including coding device 2a processing unit 2b embedded memory of memory controller 3 nonvolatile memory, particularly flash memory 4 host A1 address line(s) D1 data line(s) C1 control line(s) A2 address bus D2 data bus C2 control bus