EFFICIENT ENCODING FOR NON-BINARY ERROR CORRECTION CODES

Abstract

A method for encoding information bits with a Q-ary linear error correction code defined over a binary-extension Galois field GF(2.sup.k), 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(2.sup.k), 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

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(2.sup.k), 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(2.sup.k); 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(2.sup.k), 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(2.sup.k); 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.

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

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

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

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

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

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(2.sup.k), 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(2.sup.k); 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(2.sup.k), 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(2.sup.k); 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.

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

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

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

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

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

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(2.sup.k), 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(2.sup.k); 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(2.sup.k), 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(2.sup.k); 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.

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

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

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

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

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

Description

BRIEF DESCRIPTION OF THE ANNEXED DRAWINGS

[0061] These and other features and advantages of the present invention will be made apparent by the following description of some exemplary and non-limitative embodiments thereof. For its better intelligibility, the following description should be read making reference to the attached drawings, wherein:

[0062] FIG. 1A schematically shows a simplified architecture of a SSD device known in the state of the art;

[0063] FIG. 1B schematically shows a simplified architecture of a typical SSD controller of said SSD device;

[0064] FIG. 2A schematically shows a simplified architecture of a typical flash memory die of said SSD device;

[0065] FIGS. 2B and 2C schematically show exemplary ideal and real threshold voltage distributions of MLC memory cells and of TLC memory cells, respectively, of said flash memory die;

[0066] FIG. 3 schematically shows a simplified architecture of a SSD controller according to the present invention;

[0067] FIG. 4 schematically shows an activity diagram of a procedure according to an embodiment of the present invention.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS OF THE INVENTION

[0068] With reference to the drawings, FIG. 1A schematically shows a simplified architecture of a “Solid State Drive” device (SSD device) 100 known in the state of the art.

[0069] The SSD device 100 preferably comprises a controller (e.g., a processor and/or other control circuitry, referred to herein as SSD controller) 105, a plurality of non-volatile memory chips (e.g. flash memory chips, such as NAND flash memory chips) 110.sub.i for storing bits even in the absence of external power supply (1=1,2,3, . . . , I, with I=64 in the example at issue), and a plurality of (e.g., synchronous and/or asynchronous) channels 115.sub.j (j=1,2,3, . . . , J, with J=4 in the example at issue) communicably coupling the SSD controller 105 and the memory chips 110.sub.i to each other—in the exemplary illustration, each channel 115.sub.j communicably couples the SSD controller 105 to a set of 16 memory chips 110.sub.i (e.g., with the channels 115.sub.1, 115.sub.2, 115.sub.3 and 115.sub.4 that communicably couple the SSD controller 105 to the memory chips 110.sub.1-110.sub.16, 110.sub.17-110.sub.32, 110.sub.33-110.sub.48 and 110.sub.49-110.sub.64, respectively).

[0070] With reference also to FIG. 1B, it schematically shows, in terms of operating units, a simplified architecture of a typical SSD controller 105—the term “unit” being herein intended to emphasize functional (rather than implementation) aspects thereof (each unit including, for example, hardware or circuitry with processing and/or storing capabilities). For the sake of completeness, such a figure also shows, with a smaller size, the memory chips 110.sub.i and the channels 115.sub.j (only some of the memory chips being numbered in such a figure for ease of illustration).

[0071] The SSD controller 105 comprises a SSD interface unit 120 allowing data exchange (i.e., data sending and reception in a bi-directional way) between the SSD device 100 and a host (e.g., a host system such as a personal laptop computer, a desktop computer, a digital camera, a mobile telephone, or a memory card reader, not shown) having compatible receptors for the SSD interface unit 120. The SSD interface unit 120 may be in the form of a standardized interface. For example, when the SSD device 100 is used for data storage in a computing system, the SSD interface unit 120 can be a “Serial advanced technology attachment” (SATA), a “Peripheral Component Interconnect express” (PCIe), or a “Universal Serial Bus” (USB).

[0072] Data exchanged between the SSD device 100 (through the SSD interface unit 120 of the SSD controller 105) and the host may comprise, but are not limited to, information bits to be stored (i.e., the information bits to be written in the memory chips 110.sub.i), read information bits (i.e., the information bits stored in, and read from, the memory chips 110.sub.i), user commands indicative of the operations to be performed by the SSD controller 105 on the memory chips 110.sub.i (such as write, read, diagnosis operations), and other control signals. For the purposes of the present description, the wording “data exchange”, and derivative thereof, will be intended to mean a bi-directional exchange (i.e., sending and reception) of data between two units (although this should not be construed limitatively). This is also conceptually represented in the figure by bi-directional arrow connections between the units.

[0073] The SSD controller 105 also comprises a control unit 125 (or more thereof) for managing SSD device 100 operation, such as for receiving and processing the user commands from the SSD interface unit 120, handling bit transport to and from the memory chips 110.sub.i along the channels 115.sub.j and bit transport to and from the SSD interface unit 120, and coordinating enabling and/or disabling of the memory chips 110.sub.i according to the user commands.

[0074] In order to compensate for large “Raw Bit Error Rate” (RBER), and to increase reliability of the SSD device 100, the SSD controller 105 also comprises a “Forward Error Correction” (FEC) unit 130 for locating and correcting bit errors. According to “Forward Error Correction” principles, the information bits to be stored in the memory chips 110.sub.i (and provided either by the control unit 125 or, directly, from the SSD interface unit 105) are encoded in a redundant way (e.g., by adding parity bits) by means of an “Error Correction Code” (ECC code), so that redundancy allows detecting a limited number of bit errors that may occur anywhere in the read bits, and to correct these errors, during decoding, without rereading. The FEC unit 130 may comprise discrete components—such as an “Application Specific Integrated Circuit” (ASIC)—external to the control unit 125 (as herein assumed by way of example only), or the FEC unit 130 may reflect functionalities that do not necessarily have a discrete physical form separate from the control unit 125.

[0075] In order to ease bit transport between the SSD controller 105 and the memory chips 110.sub.i along the respective channels 115.sub.j, the SSD controller 105 comprises one (as herein exemplary illustrated) or more memory interface units 135—alternatively, a memory interface unit 135 for each channel 115.sub.j may be provided, or a memory interface unit 135 for each memory chip 110.sub.i, or for each group of memory chips 110.sub.i may be provided.

[0076] As conceptually depicted in the figure by (unidirectional or bi-directional) arrow connections, which however should not be construed limitatively, the memory interface unit 135 is communicably coupled in a unidirectional manner to the SSD interface 120 (e.g., for receiving from it the information bits to be written when no ECC code is requested), and in a bi-directional manner to the control unit 125 (e.g., for receiving control information from it, such as an indication of the memory chips 110.sub.i to be enabled for write or read operations, and for providing to it the read bits to be transmitted to the SSD interface unit 120) and to the FEC unit 130 (for example, for receiving encoded bits from it, e.g. including the information and parity bits, and for providing to it the read bits to be decoded before transmitting to the control unit 125, and hence to the SSD interface unit 120, the read information bits).

[0077] The SSD controller 105 further comprises a memory unit (e.g., a “Random Access Memory”, RAM) 140 communicably coupled (in a bi-directional manner) to the control unit 125, e.g. for receiving and storing statistical information (such as number of program/erase cycles, and number of bit errors) and/or diagnostic information (such as working temperature, power consumption) retrieved and/or calculated by the control unit 125 (e.g. based on SSD device 100 operation and/or on sensors and/or diagnostic circuits within the SSD device 100, not shown), and, when required, for feeding the control unit 125 with the stored information.

[0078] A typical flash memory chip 110.sub.i may comprise one or more flash memory dice.

[0079] A typical flash memory die, illustrated in FIG. 2A and denoted by the number reference 200, comprises one (as depicted) or more memory arrays 205 of memory cells (e.g., NAND flash memory cells) 210 arranged in rows and columns. Each memory array 205 is typically divided into multiple memory pages. Broadly speaking, each memory page comprises a number of memory cells 210 that can be programmed and read simultaneously. A number of memory pages form a memory block, and the size of the memory block equals to the product of the size of the memory page and the total number of memory pages in the memory block.

[0080] Each memory cell 210 is programmable to store a bit or group of bits (or bit pattern) among a plurality of bit patterns, wherein each bit pattern identifies or is associated with a respective logical state of the memory cell 210. Each memory cell 210 preferably comprises a floating gate transistor (not illustrated). Each bit pattern identifying a respective logical state of the memory cell 210 is physically stored in each memory cell 210 in the form of electric charge in the floating gate, which defines a corresponding threshold voltage of the transistor. The number of bits each memory cell 210 is capable of storing depends on memory cell technology. For example, in “Single-Level Cell” (SLC) technology each memory cell (or SLC memory cell) is capable of storing one bit pattern comprising one bit (i.e. two logical states, 0 or 1, defining, i.e. being associated with, two threshold voltages), in “Multi-Level Cell” (MLC) technology each memory cell (or MLC memory cell) is capable of storing one bit pattern comprising more than one bit, typically two bits (i.e. four logical states, 00, 01, 10, or 11, defining, i.e. being associated with, four threshold voltages), whereas in “Tri-Level Cell” technology each memory cell (or TLC memory cell) is capable of storing one bit pattern comprising three bits (i.e. eight logical states, 000, 001, 010, 011, 100, 101, 110 or 111, defining, i.e. being associated with, eight threshold voltages).

[0081] While, ideally, all memory cells 210 in the flash memory die 200 should feature and be associated with same (nominal) threshold voltages for same logical states (or, equivalently, for same bit patterns), practically each threshold voltage associated with a corresponding logical state (or, equivalently, associated with a corresponding bit pattern) differs across the memory cells 210 and defines a respective threshold voltage distribution D.sub.j (typically, a Gaussian-type probability distribution), thus resulting in a number of threshold voltage distributions D.sub.j equal to the possible logical states each memory cell 210 can take; otherwise stated, memory cells programmed to store a same bit pattern among the plurality of bit patterns exhibit actual threshold voltages that are variable over the memory cells 210 around the corresponding nominal threshold voltage thereby defining a respective threshold voltage distribution D.sub.j associated with that same bit pattern. This is schematically shown in the top drawing of FIG. 2B for a MLC memory cell and in the top drawing of FIG. 2C for a TLC memory cell.

[0082] The threshold voltage distributions D.sub.j are (ideally) spaced apart from one another, and a corresponding hard reference voltage V.sub.k is set between each pair of adjacent threshold voltage distributions D.sub.j for sensing/reading the logical state of the memory cells 210 (k=1,2,3 in the example of FIG. 2B and k=1,2,3,4,5,6,7 in the example of FIG. 2C). Therefore, each pair of adjacent bit patterns, which are associated with a corresponding adjacent pair of nominal threshold voltages (and hence with a corresponding adjacent pair of threshold voltage distributions D.sub.j), can be discriminated, during a read operation, by a respective hard reference voltage V.sub.k which is between the corresponding adjacent nominal threshold voltages.

[0083] In the case of SLC memory cell (k=1), during a read operation a threshold voltage below the hard reference voltage V.sub.1 represents the symbol “1”, and a threshold voltage above the hard reference voltage V.sub.1 represents the symbol “0”.

[0084] In the case of MLC memory cell, during a read operation, a threshold voltage below the hard reference voltage V.sub.1 represents the symbol “11”, a threshold voltage between the hard reference voltages V.sub.1 and V.sub.2 represents the symbol “01”, a threshold voltage between the hard reference voltages V.sub.2 and V.sub.3 represents the symbol “00”, and a threshold voltage above the hard reference voltage V.sub.3 represents the symbol “10”.

[0085] In the case of TLC memory cell and in the exemplary considered coding distributions, during a read operation, a threshold voltage below the hard reference voltage V.sub.1 represents the symbol “111”, a threshold voltage between the hard reference voltages V.sub.1 and V.sub.2 represents the symbol “011”, a threshold voltage between the hard reference voltages V.sub.2 and V.sub.3 represents the symbol “001”, a threshold voltage between the hard reference voltages V.sub.3 and V.sub.4 represents the symbol “101”, a threshold voltage between the hard reference voltages V.sub.4 and V.sub.5 represents the symbol “100”, a threshold voltage between the hard reference voltages V.sub.5 and V.sub.6 represents the symbol “000”, a threshold voltage between the hard reference voltages V.sub.6 and V.sub.7 represents the symbol “010”, and a threshold voltage above the hard reference voltage V.sub.7 represents the symbol “110”.

[0086] To read a memory cell 210, the threshold voltage of the memory cell 210 is compared to the hard reference voltages V.sub.k. According to an embodiment, reading a memory cell 210 that stores a bit pattern of m bits requires, for at least one page of memory cells (hereinafter, memory page), m such comparisons.

[0087] For example, when m=3, such as in the TLC memory cell, the threshold voltage is first compared to the hard reference voltage V.sub.4. Depending on the outcome of that comparison, the threshold voltage is then compared either to the hard reference voltage V.sub.2 or to the hard reference voltage V.sub.6. Depending on the outcome of the second comparison, the threshold voltage is then compared either to the hard reference voltages V.sub.1 or V.sub.3 or to the hard reference voltages V.sub.5 or V.sub.7.

[0088] Back to FIG. 2A, the memory die 200 preferably comprises peripheral circuits (such as decoders, multiplexers, drivers, buffers, sense amplifiers), which, being not relevant for the present description, are represented in the figure by means of a single functional block (denoted by the number reference 215). Such peripheral circuits 215 are configured, in general, for accessing selected (pages of) memory cells (as conceptually represented in the figure by arrow connection between the peripheral circuits 215 and the memory array 205) and for running selected operations thereon (e.g. write, read, diagnosis operations).

[0089] The increasing of the number of bits per memory cell causes, for a same threshold voltage distribution space (i.e., for the same allowed maximum and minimum threshold voltages), a higher number of threshold voltage distributions. A higher number of threshold voltage distributions in the same threshold voltage distribution space results in threshold voltage distributions that are closer to each other. This makes the memory cells more prone to suffer severe cell-to-cell interference, mainly arising from floating gate coupling effect between a target memory cell (i.e., a memory cell to be read or written) and the surrounding memory cells, and retention, i.e. a loss of the capability of the memory cells to retain the stored bits over time caused by progressive damage of the oxide layer (due to the high electrical fields applied at each program/erase operation) that determines an undesired flow of electrons away/in the floating gate.

[0090] Cell-to-cell interference and retention translate into partially overlapping areas of adjacent threshold voltage distributions D.sub.j (shown in the bottom drawings of FIGS. 2B and 2C) and, hence, into increasing of the probability of the number of bit errors per unit time (i.e., the RBER).

[0091] With reference now to FIG. 3, it schematically shows, in terms of operating units, a simplified architecture of a SSD controller 305 according an embodiment the present invention. For the sake of completeness, such a figure also shows, in a smaller size, the memory chips 110.sub.i and the channels 115.sub.j (equivalent to those illustrated in the previous figures), which identify, together with the SSD controller 305, a SSD device 300. Similarly to the above, the term “unit” is herein intended to emphasize functional (rather than implementation) aspects thereof. Indeed, without losing of generality, each unit of the SSD controller 305 may be physically implemented by software, hardware, and/or a combination thereof, and/or within any pre-existing or dedicated entity. In this respect, the operating units may also be intended to represent corresponding method steps of a method according to the present invention.

[0092] As visible in the figure, the SSD controller 305 comprises, similarly to the SSD controller 105, a SSD interface 320, a control unit 325, a memory interface unit 335, and a memory unit 340, which will not be discussed again for the sake of conciseness.

[0093] The SSD controller 305 also comprises an encoding unit 345 for encoding the bits to be stored in the memory array 205 (i.e., the information bits) by means of an ECC code. According to an embodiment of the present invention, the encoding unit 345, and the respective decoding unit (discussed in the following), are implemented in the FEC unit 130.

[0094] Preferably, the ECC code is an ECC code allowing soft decoding—or, otherwise stated, an ECC code that allows determining each bit value by means of hard bits (i.e., the read bits resulting from comparisons to the hard reference voltages V.sub.k) and of additional information including soft bits and an indication of the reliability of each read (hard and soft) bit typically evaluated or estimated according to RBER. More preferably, the ECC code is a “Low Density Parity-Check” (LDPC) code—hence, the encoding unit 345 will be referred to as LDPC encoding unit 345 and the corresponding encoded bits will be referred to as LDPC encoded bits. LDPC code is a linear ECC code (constructed by using a sparse bipartite graph) that allows transmitting data over a noisy channel. LDPC code is a capacity-approaching code, which means that practical constructions exist that allow the noise threshold to be set very close to the theoretical maximum (the Shannon limit given by the Shannon theorem) for a symmetric memory-less channel.

[0095] The Shannon theorem specifies the maximum rate at which data can be transmitted over a channel of a specified bandwidth in the presence of noise. More specifically, according to the Shannon theorem, a bound on the maximum amount of error-free data that can be transmitted with a specified bandwidth in the presence of the noise interference is set, assuming that the signal power is bounded, and that the Gaussian noise process is characterized by a known power or power spectral density. The noise threshold defines an upper bound for the channel noise, up to which the probability of data errors can be made as small as desired.

[0096] Thanks to soft decoding allowed by LDPC code, for a given code rate (the ratio between the information bits to the (LDPC, in the case at issue) encoding unit and the total number of bits created by the encoding unit, the total number of bits created by the encoding unit including the parity bits), LDPC code approaches the Shannon limit more than ECC codes typically used in prior art solutions (such as Bose-Chaudhuri-Hocquenghem (BCH) codes), which translates into area saving while maximizing the probability of accurately recovering the bits after a read operation.

[0097] According to the preferred embodiment herein considered, the LDPC code used to encode the bits to be stored in the memory array 205 is a non-binary LDPC code (i.e. a Q-ary LDPC code (Q ≠ 2)) defined over a binary-extension Galois field GF(2.sup.k)—from now on, whenever LDPC code is mentioned, it should be taken to mean the non-binary (i.e., Q-ary) LDPC code defined over a binary-extension Galois field GF(2.sup.k). A finite field or Galois field (GF) is a field that contains a finite number of elements: as with any field, a Galois field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules.

[0098] Back to FIG. 3, the SSD controller 305 is configured to store the LDPC encoded bits in the memory chips 110.sub.i (e.g., similarly to the above, by means of the memory interface unit 335 that transmits the LDPC encoded bits to the memory chips 110.sub.i, and thanks to control unit 325 action that controls addressing of the memory chips 110.sub.i to be written/programmed). In the exemplary illustrated embodiment the LDPC encoded bits are fed directly to the memory interface unit 335, however this should not be construed limitatively: indeed, depending on the specific implementation, the LDPC encoded bits may be subject to additional processing before their storing in the memory chips 110.sub.i (for example, each codeword of the LDPC code may be advantageously converted into a binary vector of length N*r, N being the length of the LDPC code).

[0099] For the sake of completeness, the SSD controller 305 also comprises a mapping unit 350 for “mapping” the read bits into N symbols, and a decoding unit 355 for decoding, e.g. based on a Q-ary Tanner graph of the Q-ary LDPC code, the N symbols in order to extract the information bits therefrom.

[0100] As mentioned in the introductory part of the present disclosure, non-binary LDPC codes represent better candidates than binary LDPC codes in terms of decoding capability, but the increase in encoding complexity is not negligible and has so far restricted their practical usage.

[0101] In fact, the parity-check matrix defining the Q-ary LDPC code is quasi-cyclic, whereby determining the corresponding generator matrix (to perform encoding) proves to be difficult and too computationally expensive as involving a matrix inversion. This would result in physically storing in the SSD device 300 the generator matrix corresponding to the parity-check matrix (which would prevent any changes to the parity-check matrix, e.g. for changing the code rate of the LDPC code due to noise variations caused by different stresses) or implementing an algorithm to derive the parity-check matrix from the generator matrix (which would be too expensive in terms of hardware complexity).

[0102] The present application relates to a solution for performing encoding of information bits with a Q-ary ECC code (such a Q-ary LDPC code) defined over a binary-extension Galois field GF(2.sup.k) in a fast way, without inverting the parity-check matrix or storing the generator matrix, while keeping a rate-compatible structure.

[0103] This solution takes advantage of the properties of the mathematical construction behind non-binary ECC codes, which will be illustrated here below.

[0104] Broadly speaking, based on the mathematical construction behind non-binary ECC codes, the Applicant has devised that, from the parity-check matrix that defines the Q-ary ECC code, operative data can be determined and stored in the control unit 325 (e.g. in proper memory locations thereof, as schematically depicted in FIG. 3) for encoding information bits with the Q-ary ECC code (such as the Q-ary, non-binary, LDPC code) in an efficient and fast way.

[0105] Let be considered the following quasi-cyclic parity-check matrix H defining the (quasi-cyclic) Q-ary LDPC code:

[00001]$H=\left[H_I|H_P\right]=[\begin{array}{cccccc}& P_{q_1}^x& I& 0& \mathrm{.Math.}& 0\\ & I& I& I& \mathrm{.Math.}& 0\\ & 0& P_{q_2}^y& I& \mathrm{.Math.}& 0\\ H_I& 0& 0& 0& \mathrm{.Math.}& 0\\ & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ & 0& 0& 0& \ddots & I\\ & P_{q_1}^x& P_{q_3}^z& 0& \mathrm{.Math.}& I\end{array}]$

[0106] wherein: [0107] H.sub.1 is the information part (or information section) of the parity-check matrix H, the information part being associated with the information bits; [0108] H.sub.P is the parity part (or parity section) of the parity-check matrix H; [0109] 0 is the null circulant, i.e. the matrix made up of zeroes; [0110] I is the identity circulant; [0111] P.sub.q.sub.i.sup.x, P.sub.q.sub.i.sup.y, P.sub.q.sub.i.sup.z are circulants defined by the i-th parameters q.sub.1 belonging to the Galois field GF(2.sup.k), and having shifts x,y,z (x,y,z=0, 1, . . . , L−1, wherein L is the number of rows, or columns, of the circulant); in the example, at issue, H.sub.P contains four (nontrivial) circulants P.sub.q.sub.1.sup.x, P.sub.q.sub.1.sup.x, P.sub.q.sub.2.sup.y, P.sub.q.sub.3.sup.z (two of which are the same) independently from the number of rows.

[0112] An equivalent parity-check matrix having an approximate lower triangular form is determined from the parity-check matrix H, as disclosed in T. J. Richardson; R. L. Urbanke, “Efficient encoding of low-density parity-check codes” (which is incorporated herein by reference).

[0113] According to T. J. Richardson; R. L. Urbanke, “Efficient encoding of low-density parity-check codes”, the equivalent parity-check matrix is obtained by splitting the parity check matrix H into six circulant sub-matrices A, B, C, D, E, T:

[00002]$H=\left[H,|H_P\right]=[\begin{array}{cccccc}& P_{q_1}^x& I& 0& \mathrm{.Math.}& 0\\ & I& I& I& \mathrm{.Math.}& 0\\ & 0& P_{q_2}^y& I& \mathrm{.Math.}& 0\\ H_I& 0& 0& 0& \mathrm{.Math.}& 0\\ & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ & 0& 0& 0& \ddots & I\\ & P_{q_1}^x& P_{q_3}^z& 0& \mathrm{.Math.}& I\end{array}]=\left[\begin{array}{ccc}A& B& T\\ C& D& E\end{array}\right]$$\mathrm{wherein}:B=\left[\begin{array}{c}{P}_{q_1}^x\\ I\\ 0\\ 0\\ \mathrm{.Math.}\\ 0\end{array}\right],D=\left[P_{q_1}^x\right],T=[\begin{array}{cccc}I& 0& \mathrm{.Math.}& 0\\ I& I& \mathrm{.Math.}& 0\\ P_{q_2}^y& I& \mathrm{.Math.}& 0\\ 0& 0& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ 0& 0& \ddots & I\end{array}],E=\left[\begin{array}{cccc}{P}_{q_3}^z& 0& \mathrm{.Math.}& I\end{array}\right]$

[0114] and by multiplying the parity-check matrix H from the left by

[00003]$\hspace{1em}\left[\begin{array}{cc}I& 0\\ E{T}^{-1}& I\end{array}\right]$

(T is a lower triangular matrix, so it can be easily inverted), thus obtaining:

[00004]$\hspace{1em}\left[\begin{array}{ccc}A& B& T\\ E{T}^{-1}A+C& E{T}^{-1}B+D& E{T}^{-1}T+E\end{array}\right]$

[0115] and hence:

[00005]$\hspace{1em}\left[\begin{array}{ccc}A& B& T\\ E{T}^{-1}A+C& E{T}^{-1}B+D& 0\end{array}\right]$

[0116] since ET.sup.−1T=E and E+E=0 (in fact, doubling an element belonging to the Galois field GF(2.sup.k) always gives 0).

[0117] Considering the defining relationship for a codeword c:

H.Math.c.sup.T=0.sup.T,

[0118] and let c=(s, p.sub.1, p.sub.2), where s denotes the systematic or information bits of the codeword c, and p.sub.1 and p.sub.2 denote first and second sets of parity-check bits (to be used for encoding the information bits), respectively, then the above relationship results in the following linear equation system:

[00006]$\hspace{1em}\{\begin{array}{c}{\mathrm{As}}^T+B{p}_1^T+{\mathrm{Tp}}_2^T=0^T\\ \left(E{T}^{-1}A+C\right)s^T+\left(E{T}^{-1}B+D\right)p_1^T=0^T\end{array}$

[0119] whereby the first set of parity-check bits p.sub.1 can be obtained from the second equation after inverting the amount φ:=ET.sup.−1B+D, and the second set of parity-check bits p.sub.2 can be obtained from the first equation based on the information bits s and on the first set of parity-check bits p.sub.1.

[0120] The Applicant has understood that, although the inversion of the amount φ:=ET.sup.−1B+D for obtaining the first set of parity-check bits p.sub.1 from the second equation is theoretically correct, such an inversion involves computational capabilities higher than those of the conventional SSD devices.

[0121] In order to solve such issue, the Applicant has devised a reformulation of the above-discussed equivalent parity-check matrix that makes determination of the first p.sub.1 and second p.sub.2 sets of parity-check bits (and, hence, the encoding of the information bits s) feasible in nowadays SSD devices.

[0122] Such a reformulation of the equivalent parity-check matrix starts from the ascertaining, by the Applicant, that the inverted circulant sub-matrix T.sup.−1 has the following form (wherein the outlined area comprises a plurality of identity circulants):

[00007]$T^{-1}=[\begin{array}{ccccc}I& 0& 0& \mathrm{.Math.}& 0\\ I& I& 0& \mathrm{.Math.}& 0\\ P_{q_2}^y+I& I& I& \mathrm{.Math.}& 0\\ \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ P_{q_2}^y+I& I& I& \mathrm{.Math.}& I\end{array}]$

[0123] Therefore

ET.sup.−1=[P.sub.q.sub.3.sup.z+P.sub.q.sub.2.sup.y+I I . . . I]

[0124] and

ET.sup.−1B+D=P.sub.q.sub.3.sup.zP.sub.q.sub.1.sup.x+P.sub.q.sub.2.sup.yP.sub.q.sub.1.sup.x+P.sub.q.sub.1.sup.x+I+P.sub.q.sub.1.sup.x=P.sub.q.sub.3.sup.zP.sub.q.sub.1.sup.x+P.sub.q.sub.2.sup.yP.sub.q.sub.1.sup.x+I.

[0125] The Applicant has also recognized that, in order to obtain a reformulation of the equivalent parity-check matrix that provides a simplification of the amount φ:=ET.sup.−1B+D, proper constraints on the parameter q.sub.2 and on the shift y of the circulant P.sub.q.sub.2.sup.y may advantageously be set.

[0126] According to an embodiment of the present invention: [0127] the parameter q.sub.2 of the circulant P.sub.q.sub.2.sup.y is chosen, in a design phase of the LDPC code, as the inverse (q.sub.1INV) of the parameter q.sub.1 of the circulant P.sub.q.sub.1.sup.x in the Galois field GF(2.sup.k), i.e. such that q.sub.1.Math.q.sub.2=1 in the Galois field GF(2.sup.k). In this way, the non-zero element of the circulant P.sub.q.sub.2.sup.yP.sub.q.sub.1.sup.x=P.sub.q.sub.1INV.sup.yP.sub.q.sub.1.sup.x is 1. [0128] the shift y of the circulant P.sub.q.sub.2.sup.y is chosen as y=L−x. Such a choice, which would be the same for the binary LDPC code, ensures that the main diagonal is full of values 1, thanks to the properties of exponents in the matrix product,
whereby P.sub.q.sub.2.sup.yP.sub.q.sub.1.sup.x=I and the amount φ:=ET.sup.−1B+D is reduced to:

ET.sup.−1B+D=P.sub.q.sub.3.sup.zP.sub.q.sub.1.sup.x

[0129] The parity-check matrix H and the linear equation system can therefore be written as follows:

[00008]$H=\left[H,|H_P\right]=[\begin{array}{cccccc}& P_{q_1}^x& I& 0& \mathrm{.Math.}& 0\\ & I& I& I& \mathrm{.Math.}& 0\\ & 0& P_{q_1\mathrm{INV}}^{L-x}& I& \mathrm{.Math.}& 0\\ H_I& 0& 0& 0& \mathrm{.Math.}& 0\\ & \mathrm{.Math.}& \mathrm{.Math.}& \mathrm{.Math.}& \ddots & \mathrm{.Math.}\\ & 0& 0& 0& \ddots & I\\ & P_{q_1}^x& P_{q_3}^z& 0& \mathrm{.Math.}& I\end{array}]=\left[\begin{array}{ccc}A& B& T\\ C& D& E\end{array}\right]$$\{\begin{array}{c}{\mathrm{As}}^T+B{p}_1^T+T{p}_2^T=0^T\\ \left(E{T}^{-1}A+C\right)s^T+\left(P_{q_3}^z{P}_{q_1}^x\right)p_1^T=0^T\end{array}$

[0130] Since a Galois field of order 2.sup.k is considered, the equation:

(ET.sup.−1A+C)s.sup.T+(P.sub.q.sub.3.sup.zP.sub.q.sub.1.sup.x)p.sub.1.sup.T=0.sup.T

can be written as:

(P.sub.q.sub.3P.sub.q.sub.1.sup.x)p.sub.1.sup.T=(ET.sup.−1A+C)s.sup.T

[0131] and, more concisely:

P.sub.q.sub.4.sup.w p.sub.1.sup.T=(ET.sup.−1A+C)s.sup.T

[0132] wherein:

[0133] w:=(x+z) is the shift resulting from the product between P.sub.q.sub.3.sup.z and P.sub.q.sub.1.sup.x, and

[0134] q.sub.4:=q.sub.1.Math.q.sub.3 is the parameter of the circulant P.sub.q.sub.4.sup.w (the equality being intended in the Galois field GF(2.sup.k)).

[0135] Let the parameter q.sub.4INV be the multiplicative inverse of the parameter q.sub.4, so that q.sub.4.Math.q.sub.4INV=1 in the Galois field GF(2.sup.k).

[0136] Multiplying both sides of the previous equation by the parameter q.sub.4INV results in:

q.sub.4INV.Math.P.sub.q.sub.4.sup.w p.sub.1.sup.T=q.sub.4INV.Math.(ET.sup.−1A+C)s.sup.T

[0137] wherein the circulant q.sub.4INV.Math.P.sub.q.sub.4.sup.w, whose nonzero element is 1 by construction, describes a circular shift (as in the binary case). This means that by applying the opposite shift (which is equal to L−w) to both sides of the equation, the explicit expression of p.sub.1.sup.T may be obtained:

p.sub.1.sup.T=P.sub.q.sub.4INV.sup.L−w(ET.sup.−1A+C)s.sup.T

[0138] The more compact way of writing P.sub.q.sub.3.sup.zP.sub.q.sub.1.sup.x avoids inverting the circulant product P.sub.q.sub.3.sup.zP.sub.q.sub.1.sup.x, thus obtaining a reformulation of the equivalent parity-check matrix that is feasible in nowadays SSD devices.

[0139] FIG. 4 schematically shows an activity diagram of a procedure 400 according to an embodiment of the present invention.

[0140] The procedure 400 preferably comprises two phases, namely a first phase (action nodes 405-435), or design phase, taking place at a design phase of the SSD device (and particularly, at a design phase of the Q-ary ECC code), and a second phase (action nodes 440-455), or encoding phase, taking place during operation of the SSD device 300 (i.e., at the SSD controller 305) and allowing information bits s (to be written in selected memory cells) to be encoded by means of the designed Q-ary ECC code.

[0141] During the design phase, based on software simulations (action node 405) and hardware complexity analysis (action node 410), the number of elements (2.sup.k), or order or size, of the Galois field GF(2.sup.k) is chosen (action node 415). The higher the number of elements (2.sup.k) of the Galois field GF(2.sup.k), the better the performances in terms of error correction. In any case, the higher the number of elements (2.sup.k) of the Galois field GF(2.sup.k), the higher the increase in complexity (and, hence, in power consumption and latency). In view of this trade off, typical Galois fields GF(2.sup.k) that may be chosen based on current technology are GF(2.sup.8) and GF (2.sup.16).

[0142] Then, look-up tables for multiplication and addition between the elements of the Galois field Galois field GF(2.sup.k) are preferably pre-computed and advantageously stored in proper memory locations of the SSD device 300 (action node 420).

[0143] As schematically depicted in FIG. 3, the look-up tables for multiplication (*LUT) and for addition (+LUT) may for example be stored in proper memory locations of the control unit 325.

[0144] In any case, at least the look-up table for addition may also be omitted in implementations of the present invention, with the addition of two elements in the Galois field GF(2.sup.k) that may for example be performed by any suitable technique.

[0145] Then, action node 425, the parity-check matrix H is determined and stored in a proper memory location of the SSD device 300, for example in a proper memory location of the control unit 325.

[0146] As discussed in connection with the above mathematical dissertation, the parity-check matrix H is determined at action node 425 by choosing the parameter q.sub.2 of the circulant P.sub.q.sub.2.sup.y as the inverse of the parameter q.sub.1 of the circulant P.sub.q.sub.1.sup.x in the Galois field GF(2.sup.k), (i.e. such that q.sub.1.Math.a.sub.2=1 in the Galois field GF(2.sup.k)), and by choosing the shifty of the circulant P.sub.q.sub.2.sup.y as y=L−x, whereby the above-discussed reformulation of the equivalent parity-check matrix devised by the Applicant is obtained (action node 430).

[0147] Based on the equivalent parity-check matrix H thus obtained, the amount (ET.sup.−1A+C) and the circulant P.sub.q4INV.sup.L−w are computed (advantageously, by exploiting the pre-computed look-up tables for multiplication *LUT and for addition +LUT), and stored in a proper memory location of the SSD device 300, for example, as schematically depicted in FIG. 3, in a proper memory location of the control unit 325—action node 435.

[0148] During the encoding phase, upon reception of the information bits s to be stored in the SSD device 300 (action node 440), the product (ET.sup.−1A+C)s.sup.T is computed (action node 445) based on the stored amount (ET.sup.−1A+C) and on the received information bits s (advantageously, by exploiting the pre-computed look-up table for multiplication *LUT), and the first set of parity check bits p.sub.1 is then determined (action node 450) by multiplying the resulting product (ET.sup.−1A+C)s.sup.T by the stored circulant P.sub.q.sub.4INV.sup.L−w (advantageously, by exploiting the pre-computed look-up table for multiplication *LUT). According to a basic implementation, the first set of parity check bits p.sub.1 may be determined by multiplying the stored circulant P.sub.q.sub.4INV.sup.L−w by a subset of the circulant sub-matrices, for example by the circulant sub-matrices E and T (or an inverse form thereof).

[0149] Then, action node 455, the second set of parity check bits p.sub.2 may be determined by reversing the above-discussed equation A s.sup.T+B p.sub.1.sup.T+T p.sub.2.sup.T=0.sup.T and according to the information bits s and the just determined first set of parity check bits p.sub.1. According to a basic implementation, the second set of parity check bits p.sub.2 may be determined according to the information bits s, the just determined first set of parity check bits p.sub.1, and to a subset of the circulant sub-matrices, for example the circulant sub-matrices B and T (or an inverse form thereof).

[0150] As mentioned above, it could be desired to change the parity-check matrix, for example to change the code rate of the LDPC code so as to take into account noise variations caused by different stresses. The parity-check matrix may for example be changed periodically (e.g., after a predetermined time period of use of the SSD device 300) and/or aperiodically (e.g., triggered by one or more events detected by the SSD device 300).

[0151] Parity-check matrix changes are typically performed by erasing one or more of the leftmost columns of the parity-check matrix. In doing so, only the circulant sub-matrices A and C of the equivalent parity-check matrix are affected.

[0152] In this case, according to a preferred embodiment of the present invention, the method 400 may also comprise updating, periodically and/or aperiodically (as conceptually illustrated by the double arrow “Time/Event” in the figure), the circulant sub-matrices A and C (and, hence, the equivalent parity-check matrix—action block 425) and updating and storing in the control unit 325 the amount (ET.sup.−1A+C)—action block 435—to be for the subsequent encoding phase (action blocks 445 and 450).

[0153] Preferably, although not illustrated, the periodical and/or aperiodical updating is performed if the predetermined time period of use of the SSD device 300 set for the periodical updating and/or the trigger event(s) detected by the SSD device 300 fall within an ongoing encoding phase, with the periodical and/or aperiodical updating that in this case may be performed immediately after completing the ongoing encoding phase.

[0154] Alternatively, if the predetermined time period of use of the SSD device 300 set for the periodical updating and/or the trigger event(s) detected by the SSD device 300 fall within an ongoing encoding phase, the updating may still be performed concurrently with the encoding phase, in which case the ongoing encoding phase may for example take place based on the amount (ET.sup.−1A+C) instead of the updated amount (ET.sup.−1A+C).

[0155] Naturally, in order to satisfy local and specific requirements, a person skilled in the art may apply to the present invention as described above many logical and/or physical modifications and alterations. More specifically, although the present invention has been described with a certain degree of particularity with reference to preferred embodiments thereof, it should be understood that various omissions, substitutions and changes in the form and details as well as other embodiments are possible. In particular, different embodiments of the invention may even be practiced without the specific details set forth in the preceding description for providing a more thorough understanding thereof; on the contrary, well-known features may have been omitted or simplified in order not to encumber the description with unnecessary details. Moreover, it is expressly intended that specific elements and/or method steps described in connection with any disclosed embodiment of the invention may be incorporated in any other embodiment.