Error Correction for TLC and QLC NAND Flash Memories Using Cell-Wise Encoding

Abstract

The growing error rates of triple-level cell (TLC) and quadruple-level cell (QLC) NAND flash memories have led to the application of error correction coding with soft-input decoding techniques in flash-based storage systems. Typically, flash memory is organized in pages where the individual bits per cell are assigned to different pages and different codewords of the error-correcting code. This page-wise encoding minimizes the read latency with hard-input decoding. To increase the decoding capability, soft-input decoding is used eventually due to the aging of the cells. This soft-decoding requires multiple read operations. Hence, the soft-read operations reduce the achievable throughput, and increase the read latency and power consumption. In this work, we investigate a different encoding and decoding approach that improves the error correction performance without increasing the number of reference voltages. We consider TLC and QLC flashes where all bits are jointly encoded using a Gray labeling. This cell-wise encoding improves the achievable channel capacity compared with independent page-wise encoding. Errors with cell-wise read operations typically result in a single erroneous bit per cell. We present a coding approach based on generalized concatenated codes that utilizes this property.

1. Introduction

Many novel applications, such as medical devices, IoT, and autonomous vehicles, require large storage capacities and fast data access [1,2]. NAND flash-based non-volatile storage is well suited for such applications. Moreover, the development of NAND flash memory with increased storage density is progressing steadily.

The NAND flash cells consist of floating gate transistors in which data are stored in the form of electric charge states. There are different technologies for NAND flash memory. The multi-level cell (MLC) and triple-level cell (TLC) flash memories can store two and three bits, respectively. Quadruple-level cells (QLC) can store four bits per cell [3], and penta-level cells (PLC), which store five bits per cell, are already in development [4].

With the growing storage capacity, error correction codes (ECC) are becoming increasingly important. There are numerous sources of disturbances for a flash cell, such as charge loss over time, cell-to-cell interference, program and erase (P/E) cycle stress, and external influences, such as temperature fluctuations, that reduce the memory’s reliability and influence the threshold voltage distribution [5,6]. Therefore, the noise level and the error probability of the flash channels change during the device’s lifetime.

With MLC flash memories, hard-decision decoding based on Bose–Chaudhuri–Hocquenghem (BCH) codes was sufficient for error correction [7,8]. Due to the high memory density and fabrication tolerances, errors during the readout are becoming more probable, and more sophisticated error correction algorithms are necessary. To improve the error correction performance, soft reading is applied to the flash cell [9,10,11,12]. Low-density parity-check codes (LDPC) are well-suited for flash systems with hard-input or soft-input decoding [10,13,14,15,16,17]. However, the error floor of LDPC codes may cause reliability issues for industrial applications, which have to guarantee word error rates below ${10}^{-16}$ [18]. Such error rates cannot be analyzed by simulations. Generalized concatenated (GC) codes are suitable for flash-based storage systems that require low guaranteed residual error rates [18,19,20,21,22]. For GC codes, it is possible to bound the residual error probability.

During the flash readout, different reference voltages are applied to infer the charge state of the cell. The soft information for soft-input decoding is obtained by applying additional reference voltages. These additional read operations improve the reliability but increase the latency and the power consumption. Furthermore, soft-input decoding is more complex than hard-input decoding, which also leads to higher power consumption.

In this work, we consider a coding approach with the objective of avoiding the soft reading operation as long as possible. This approach is based on a cell-wise encoding instead of the typically used page-wise encoding. Flash memories are organized in pages where usually the different bits of a cell are assigned to different pages and different codewords of the error-correcting code. This page-wise encoding minimizes the read latency with hard-input decoding. Depending on the bit labeling, a different number of read operations is needed for the different pages, and accordingly, the read latency depends on the bit labeling. In addition, bit labeling affects the error probability of the pages [23].

In the case of a cell-wise read, code bits from all pages associated with a flash cell must be read together. Depending on the flash technology, this reading procedure may increase the read latency. On the other hand, the dependencies between the different bits stored in a cell can be exploited with cell-wise read operations. For instance, a method that improves the decoding performance of LDPC codes with cell-wise reading was presented in [24,25]. This method calculates log-likelihood ratios for the different bits depending on the estimated charge state. However, this method requires soft-input decoding, which is more complex and causes a higher power consumption than hard-input decoding. Moreover, channel estimation is required to determine the log-likelihood ratios. In contrast, we consider a joint encoding approach for GC codes that requires only algebraic hard-input decoding and avoids additional channel estimation.

The bit labeling or coding of the cell states was addressed in the literature with different aims. In [26], a coding scheme was introduced that reduces inter-cell interference for various flash types, including QLC and PLC. These constrained codes exclude problematic bit patterns from the set of possible code patterns. However, these constrained codes significantly reduce the code rate. The achievable code rates are low considering the spare space provided by today’s flash memories. Another coding approach was pursued with write-once memory (WOM) codes [27,28]. This coding technique attacks the aging due to program and erase cycles by reducing the number of erasures. The bit labeling of available flash memories is usually based on Gray codes [7]. A Gray code is a binary code where the codewords of neighboring charge states differ only in one bit position. Such an encoding scheme minimizes latency for page-wise random access. However, the error probability and the total cell capacity is not completely balanced with Gray codes [23].

The multiple sources of errors in flash memory due to different physical effects are problematic for modeling the flash channel [6]. There are numerous publications on modeling flash memories [29,30,31,32,33,34]. Similarly to [9,23], we consider a capacity analysis for the flash cells. For the capacity calculation, we fit a model to measured voltage distributions. Based on these measured voltage distributions for a TLC flash, we demonstrate that the page-wise read operations lead to a loss in terms of the overall achievable channel capacity which is comparable to the capacity gain that is obtained by the soft read operation. In other words, the joint processing of all pages with hard-input decoding can achieve a channel capacity similar to a page-wise soft-input decoding approach.

To demonstrate that a cell-wise encoding provides practical advantages, we present a coding approach based on generalized concatenated codes. This coding approach improves the average error correction performance without increasing the number of reference voltages. We consider TLC flashes where all bits are jointly encoded using a Gray labeling. The proposed GC codes exploit the fact that errors with cell-wise reading typically result in a single erroneous bit per cell. This results from the fact that almost all errors are caused by detecting a charge state adjacent to the programmed state. This is described in more detail in [35].

In the following, we review the bit mapping with Gray codes for flash-based memory. Then, we describe the channel model and consider the achievable channel capacities in Section 3. We present the GC code construction with inner BCH and outer RS code in Section 4. In Section 5, we investigate the error correction performance with page-wise and cell-wise encoding using GC codes. We present a performance analysis for TLC and QLC flashes with codes for 2 and 4 kB payloads of data and different code rates. While the analysis of the channel capacities is based on measured data, the analysis of the codes uses a unipolar M-ASK channel model.

2. Basics of NAND Flash Memory

This section describes some basics of NAND flash memory. Floating gate transistors are the main components of flash-based storage. NAND flash memory is organized into multiple blocks and pages [36]. The flash technology defines how many bits are stored per NAND flash cell and how many pages are managed per cell. There are three possible operations on a NAND flash cell: program, erase, and read. Reading and programming are done at the page level, and erasing is done at the block level. In addition to the storage capacity for user data, a flash memory provides a spare area which is used for error correction, meta data, or system pointers [36].

The threshold voltage of the floating-gate transistor depends on a value currently stored on the floating gate. During readout, different voltages are applied to the control gate to infer the charge state of the cell and to read out the stored information.

Figure 1 shows an example of the voltage distribution of a TLC flash memory with possible charge states $S_i$. A TLC flash cell stores three bits per cell; thus, it differentiates eight possible charge states. They are denoted $S_0,\cdots ,S_7$. The x-axis represents the gate voltage and the y-axis the state-dependent probability densities. Such a threshold voltage distribution represents the probability that transistors are activated at a certain voltage over a large number of flash memory cells with the same charge level. The threshold voltage distributions are often assumed to be Gaussian distributions [37]. For simplicity, we have illustrated Gaussian distributions in Figure 1. Later, we will consider measured distributions.

To read the charge state of a floating gate transistor, we distinguish between hard and soft reading. In hard reading, several reference voltages $r_i$ are applied one after the other in order to infer the charge state $S_i$ and the corresponding bit values. The reference voltage $r_i$ is determined by the voltage distribution of the states $S_i$ and $S_{i+1}$.

The bits of a charge state are associated with different pages, because mostly a page-wise readout of the data is desired to reduce the read latency. Usually, Gray codes are used as bit labeling of the data on the different charge states, e.g., as depicted in Figure 1. The main characteristic of Gray codes is that neighboring bit patterns only differ by one bit. Each bit is mapped to a page; e.g., the bits of a triple-level flash cell are classified into three different pages. These are called the most significant bit (MSB) page, the center significant bit (CSB) page, and the least significant bit (LSB) page. In Figure 1, the first bit is the MSB and the last bit the LSB. Three examples of possible Gray codes for TLC Flash cells are listed in

Table 1. Possible Gray code bit-labeling for a TLC flash cell.

Charge State	${\mathit{S}}_0$	${\mathit{S}}_1$	${\mathit{S}}_2$	${\mathit{S}}_3$	${\mathit{S}}_4$	${\mathit{S}}_5$	${\mathit{S}}_6$	${\mathit{S}}_7$
Gray code 1	111	110	100	000	010	011	001	101
Gray code 2	111	110	100	101	001	000	010	011
Gray code 3	111	101	100	110	010	011	001	000

.

The soft read provides reliability information about the charge state. Figure 2 shows examples of soft read thresholds between two voltage distributions producing 2 bits of soft information. The soft values are quantized according to the number of additional reference voltages. Here, the reference $r_i$ gives the best distinction between the states $S_i$ and $S_{i+1}$; and the references $r_i^{(-1)}$ and $r_i^{\left(1\right)}$ generate one bit of soft information, and $r_i^{(-2)}$ and $r_i^{\left(2\right)}$ a second bit of soft information. Depending on the bit mapping, a different number of reference voltages must be applied per cell to read out one bit of a page. With the additional readout of soft bits, the number of readouts of an entire cell increases enormously, as do the latency and power consumption. However, this increases the information capacity, and decoding failures and loss of saved information are made less probably in the flash memory.

3. Analysis of the Channel Capacity

The capacity analysis provides an indication of how much information is obtained by reading at a particular reference voltage. Due to aging, the threshold distribution and the channel capacities of a flash memory change with time [38]. In [9,38], the capacities of MLC flash cells over their lifetime are considered. Similarly, reference [23] provides capacity considerations of TLC flash cells at the end of life (EOL) state. EOL is the last state defined by the manufacturer at which the flash memory should be readable. This case is reached when the maximum number of P/E cycles and the maximum data retention time defined by the manufacturer have been reached. The modeling of flash memories is considered in [29,30,31,32,33,34].

3.1. Measured Voltage Distributions

As in [23], we consider measured voltage distributions at the EOL state and apply a parameter estimation approach to estimate the probability distributions. We investigate the channel capacity of an industrial-grade TLC at EOL which is defined by 3000 P/E cycles and a data retention time of one year. The data retention time is simulated by a baking process.

For instance, Figure 3 shows the measured histogram of state $S_7$ of a TLC flash memory at EOL together with the fitted model and a Gaussian model. To obtain the required measurements, a flash memory page is read at 256 possible voltage steps for each reference $r_i$. Figure 3 represents the histogram in a logarithmic scale. The normalized threshold voltage represents the discrete measurement steps.

With the logarithmic scale, one can see that the parabolic shape of the Gaussian distribution is a suitable approximation for the voltage distribution around the mean value. However, the measure distribution has tails that do not follow the Gaussian distribution. The tail to the left impacts the bit error probability and cannot be neglected. Voltage distributions with exponential tails are also reported in [33,34]. To consider such tails, we use a piecewise function $f(x\mid S_i)$ for each state $S_i$ that is defined in two parts, where the left part corresponds to an exponential distribution and the right part to a Gaussian distribution:

$$f(x\mid S_i)=\frac{1}{n_i}·\left\{\begin{array}{cc}{c}_i·e^{{\lambda }_i(x-x_i)}\hfill & x<x_i\hfill \\ \frac{1}{\sqrt{2\pi {\sigma }_i^2}}{e}^{\frac{-{(x-{\mu }_i)}^2}{2{\sigma }_i^2}}\hfill & x\ge x_i\hfill \end{array}\right.$$

(1)

with

$$c_i=\frac{1}{\sqrt{2\pi {\sigma }_i^2}}{e}^{\frac{-{(x_i-{\mu }_i)}^2}{2{\sigma }_i^2}}.$$

(2)

The parameter $n_i$ is chosen to guarantee the normalization, ${\int }_{-\infty }^{\infty }f\left(x\right|S_i)dx=1$. This model allows estimating the probabilities for errors in non-adjacent states, e.g., from state $S_7$ to state $S_5$. Such errors cannot be reliably estimated from the measurement samples.

Figure 4 shows the fitted distributions $f(x\mid S_i)$ for the measured TLC flash at EOL, where the normalized threshold voltage x represents the discrete measurement steps. The dashed lines indicate the reference voltages.

3.2. Capacity Consideration

In the following, we consider the channel capacities of the measured TLC flash in the EOL scenario. The code rate of an error correction code is calculated as $R=k/n$, where k is the dimension and n is the code length. The channel capacity C is the supremum of all achievable rates. The channel capacity limits the possible code rate for reliable communication, resulting in $R<C$. The channel capacity is expressed by

$$C=\underset{f_X\left(x\right)}{sup}I(X;Y)$$

(3)

where $I(X;Y)$ is the mutual information between the random variables X and Y. In our considerations, X is the channel input, i.e., the charge state of the cell. The variable Y denotes the channel output. The supremum is taken over all possible choices of the input distribution $f_X\left(x\right)$.

In the case of hard-input decoding and page-wise read operations, Y is a binary random variable, and we can calculate the level capacities $C_l$ for each page. The channel capacity can be split up according to the chain rule of information theory [39]. The sum of the level capacities $C_l$ gives the total capacity:

$$C=\sum _l{C}_l.$$

(4)

When applying a fixed set of reference voltages, the total capacity C does not depend on the selected bit-mapping, but the page capacities do. That is, each page can have a different capacity. It is possible to achieve the total capacity by a water filling or multilevel coding approach [39,40,41], where the code rates are adjusted to the page capacities; i.e., the code rate of each page l is $R_l=k_l/n_l<C_l$. However, multilevel coding requires shared processing of all pages.

In a practical flash memory, each page has the same number of cells and the same spare area. Hence, page-wise reading typically implies that the same code is used on all pages with $R=R_l<C_{min}$ because the code rate is determined by the smallest page’s capacity. Such a page-wise coding limits the achievable total capacity. The capacity of such an independent coding procedure becomes

$$C_{min}=\underset{l}{min}{C}_l.$$

(5)

Hence, the total achievable capacity of a TLC with page-wise read is $C_p=3C_{min}<C$, and it is $C_p=4C_{min}<C$ for QLC flash. This restricts the achievable error correcting performance.

The capacity of the bit-pages may differ significantly. The main cause for these differences is that different numbers of reference voltages are required to read a particular page. To provide some insight into this issue, we consider a simplified model that demonstrates that the bit error probabilities for the pages mainly depend on the number of reference voltages. Consider, for example, Gray code 2 from Table 1. The MSB is one for states $S_0$ to $S_3$ and zero for states $S_4$ to $S_7$. Hence, only the reference voltage $r_3$ has to be applied to read the MSB page. Assume that each state has the same probability $p\left(S_i\right)=1/8$. The probability of making an error in the MSB page is therefore

$$p_{e,MSB}=\frac{1}{8}\sum _{i=0}^3{\int }_{r_3}^{\infty }f\left(x\right|S_i)dx+\frac{1}{8}\sum _{i=4}^7{\int }_{-\infty }^{r_3}f\left(x\right|S_i)dx,$$

(6)

where $f\left(x\right|S_i)$ is the probability density for the threshold voltage, given state $S_i$ was programmed.

Note that the error probability for each state mainly depends on the distance between the reference $r_3$ and the mean value ${\mu }_i$ for state $S_i$. The probability of an error in a non-adjacent states is extremely low, as can be seen in Figure 4. Assuming that non-adjacent states cannot induce an error, we obtain the simplified estimate

$$p_{e,MSB}\approx \frac{1}{8}{\int }_{r_3}^{\infty }f\left(x\right|S_3)dx+\frac{1}{8}{\int }_{-\infty }^{r_3}f\left(x\right|S_4)dx.$$

(7)

Neglecting the asymmetry of the voltage distributions, we also assume

$$p_e\approx {\int }_{r_i}^{\infty }f\left(x\right|S_i)dx\approx {\int }_{-\infty }^{r_i}f\left(x\right|S_{i+1})dx,\forall i.$$

(8)

This leads to the bit error probability $p_{b,MSB}\approx \frac{1}{4}{p}_e$ for the MSB page. Under this model, the value $p_e$ is the probability that an error occurs at $r_i$ given that the programmed state is an adjacent state, i.e., either $S_i$ or $S_{i+1}$. The factor $\frac{1}{4}$ is the probability that $S_i$ or $S_{i+1}$ is used. Consequently, the symbol error probability is $p_s\approx \frac{14}{8}{p}_e$, because the states $S_0$ and $S_7$ have only one neighboring reference, whereas all other states have two.

In this simplified model, the bit error probability for a page depends on $p_e$ and the number of states that are adjacent to the required reference voltages. The number of states that are adjacent to a reference voltage is determined by the number of references $N_{R,page}$ for the page. Thus, we have the bit error probability

$$p_{b,page}\approx \frac{2N_{R,page}}{8}{p}_e.$$

(9)

For instance, consider the LSB page for Gray code 2. The relevant references for the LSB page are $r_0$, $r_2$, $r_4$, and $r_6$. Hence, all states are adjacent to a reference voltage, which leads to the error probability for the LSB page $p_{b,LSB}of\approx p_e$. Accordingly, Gray code 1 has the page error probabilities $p_{b,MSB}=p_{b,LSB}\approx \frac{1}{2}{p}_e$ and $p_{b,CSB}\approx \frac{3}{4}{p}_e$ and is therefore better balanced than the other Gray codes from Table 1.

While this model is oversimplified to calculate the exact bit error probabilities, it explains the differences in the page capacities in

Table 2. Page capacities of a TLC at EOL depending on the bit-labeling.

	${\mathit{C}}_0$ (MSB Page)	${\mathit{C}}_1$ (CSB Page)	${\mathit{C}}_2$ (LSB Page)	C	${\mathit{C}}_{\mathit{p}}$	Read Thresholds
Gray code 1	0.967	0.958	0.982	2.907	2.874	7
Gray code 2	0.983	0.975	0.949	2.907	2.847	7
Gray code 3	0.983	0.964	0.959	2.906	2.877	7
Gray code 1 with 1 bit soft	0.981	0.975	0.988	2.944	2.926	21
Gray code 1 with 2 bit soft	0.982	0.978	0.991	2.951	2.934	35

. Consider again Gray code 2: the LSB page uses four references, which leads to the highest bit error probability and the lowest page capacity. The CSB page uses two references. The highest capacity is obtained for the MSB page with a single reference voltage.

Table 2 provides the corresponding channel capacities $C_l$ for the Gray codes from Table 1 with hard reading and soft reading. The capacities were calculated using the model with the fitted distributions $f\left(x\right|S_i)$. The reference voltages were obtained by maximizing the mutual information $I(X;Y)$ for the measured voltage distributions. Note that the page capacities are different for different Gray codes. Similarly, the achievable rate $C_p$ with page-wise encoding depends on the bit labeling. In all cases, the capacity with page-wise encoding is smaller than the total capacity C. The capacity C is achieved when all pages are considered jointly, i.e., with cell-wise reading. We can conclude that the bit labeling impacts the page capacities and consequently the achievable capacity with page-wise read operations. It also determines the latency for the random access performance for the different pages, because a larger number of references requires more read operations [9,10]. Note that it is not possible for a TLC to completely balance the number of reference voltages for all pages.

In addition to the hard-input capacities, the capacities with one and two soft bits for Gray code 1 are given in Table 2. The soft read increases the capacity compared to hard read operations, but requires many more read thresholds. In [23], a multilevel coding approach was proposed to reduce the number of read thresholds compared with soft reading. This coding approach is based on a cell-wise encoding of the bits and uses nine read thresholds. Hence, the latency is increased with respect to hard-input encoding with seven read thresholds.

In this work, we also consider joint processing of all pages, but without increasing the number of read references. This approach was motivated by the results in Table 2. For instance, consider Gray code 1. The loss in terms of the overall achievable channel capacity due to page-wise encoding is $2.907-2.874=0.033$ bits per cell. The gain of one bit of soft reading is $2.926-2.874=0.052$, which is only slightly higher than the gain for cell-wise encoding. On the other hand, soft reading increases the number of references significantly. Hence, a cell-wise encoding should also lead to a performance gain compared with page-wise hard-input decoding. Moreover, it should help to postpone the costly soft read operations.

4. Proposed Coding Scheme

In this section, we propose a construct for generalized concatenated codes for a cell-wise encoding of the bits. GC codes are suitable for providing very low residual error rates with low decoding complexity [42]. GC codes also enable efficient soft-input decoding [20,21].

Similarly to coded modulation [39,43], generalized concatenated codes are multilevel codes based on the partitioning of the inner code. The partitioning of a code results in subcodes with smaller cardinalities and higher minimum distances. The proposed construction is similar to the GC codes from [18,19,20,21]; i.e., we use outer RS codes and inner BCH codes. The inner BCH codes enable simple partitioning and efficient algebraic decoding [44]. However, other codes, such as polar codes, can also be used as inner codes [45,46,47].

The main novelty of the proposed construction is the adaptation to cell-wise encoding. Similarly to the approach proposed in Orlitsky [48], we use binary codes which are interpreted over the symbol alphabet of the channel. We assume that m bits of the code are jointly encoded in a flash cell with a Gray code. Hence, for a TLC we have $m=3$ and for QLC we have $m=4$, respectively. Due to the error characteristic of the flash, the probability of multiple bit errors in a single symbol of m bits is extremely low. This property can be used for the code construction. We briefly review the encoding and decoding of GC codes. For more details, we refer to [44,49].

4.1. Encoding

A GC code is constructed from L outer RS codes over the extension field $GF\left(2^{m_a}\right)$ and L binary inner BCH codes. All outer codes have the length $n_a$. We denote the parameters of the l-th outer code by ${\mathcal{A}}^{\left(l\right)}(2^{m_a},n_a,k_a^{\left(l\right)},d_a^{\left(l\right)})$, where $k_a^{\left(l\right)}$ is the dimension and $d_a^{\left(l\right)}$ the minimum Hamming distance. Similarly, the l-th inner code is denoted by ${\mathcal{B}}^{\left(l\right)}(n_b,k_b^{\left(l\right)},d_b^{\left(l\right)})$. The inner codes are nested codes of length $n_b$, i.e., ${\mathcal{B}}^{L-1}\subset {\mathcal{B}}^{L-2}\subset \cdots \subset {\mathcal{B}}^0$. In other words, the code ${\mathcal{B}}^{\left(0\right)}$ is partitioned into sub-codes with smaller dimensions and a higher error-correction capability. The sub-codes of a BCH code can be constructed from the cyclotomic polynomials [44].

The concatenated code has length $N=n_b·n_a$, and each codeword can be represented by an $n_b\times n_a$ binary matrix, as shown in Figure 5. The encoding starts with the outer codes, where $m_a{k}_a^{\left(0\right)}$ bits are mapped to the first outer codeword, $m_a{k}_a^{\left(1\right)}$ to the second, and so on. Hence, the overall dimension is $K=m_a{\sum }_{l=0}^{L-1}{k}_a^{\left(l\right)}$.

Next, the code bits of the outer codes are encoded column-wise with the inner codes. The codeword of the j-th column is the sum of L codewords.

$${\mathbf{b}}_j=\sum _{l=0}^{L-1}{\mathbf{b}}_j^{\left(l\right)}.$$

(10)

These codewords ${\mathbf{b}}_j^{\left(l\right)}$ are formed by encoding the symbols $a_{j,l}$ of the outer codewords with the corresponding sub-code ${\mathcal{B}}^{\left(l\right)}$. The symbol $a_{j,l}$ is the j-th symbol ($m_a$ bits) of the outer code ${\mathcal{A}}^{\left(l\right)}$. The dimensions of ${\mathcal{B}}^{\left(l\right)}$ are $k_b^{\left(l\right)}=(L-l)m_a$. However, only $m_a$ bits are mapped to each codeword ${\mathbf{b}}_j^{\left(l\right)}$. The remaining bits are filled with zero-padding; i.e., $(L-l-1)m_a$ zero bits are prefixed onto the symbol $a_j^{\left(l\right)}$ for encoding ${\mathbf{b}}_j^{\left(l\right)}$. Note that the j-th column ${\mathbf{b}}_j$ is a codeword of ${\mathcal{B}}^{\left(0\right)}$, because of the linearity of the nested codes.

4.2. Decoding

The decoding of a GC code is done level by level, where each level is decoded in the same succession of decoding steps. The decoding starts with the first level, $l=0$. All columns of the received matrix are decoded with respect to ${\mathcal{B}}^{\left(0\right)}$. The inner decoding results in estimates of the outer code symbols $a_j^{\left(0\right)}$ of ${\mathcal{A}}^{\left(0\right)}$, where j is the column index. After decoding all columns with respect to ${\mathcal{B}}^{\left(0\right)}$, the outer RS code ${\mathcal{A}}^{\left(0\right)}$ can be decoded. After successful outer decoding, a partial decoding result $\widehat{a_j}$ is available. This result has to be re-encoded using ${\mathcal{B}}^{\left(0\right)}$. The estimated codewords of the inner code ${\mathcal{B}}^{\left(0\right)}$ are subtracted from the received matrix before the next level can be decoded. The second level can be decoded with respect to ${\mathcal{B}}^{\left(1\right)}$. This code has smaller dimensions and greater error-correcting capability than the code ${\mathcal{B}}^{\left(0\right)}$. Consequently, the error-correction capability of the outer codes can be reduced from level to level. Next, we consider the design of the code parameters for the outer and inner codes.

4.3. Code Design

There exist different design rules for multilevel coding [39]. In order to achieve low residual error rates, we consider a balanced error probability approach for the different levels of the generalized concatenated code. This design aims at balancing the decoding error probability in all levels and is motivated by the error analysis of the GC decoder based on the union bound. We briefly review this concept.

We consider error and erasure decoding for the outer RS codes [44]. The outer RS code ${\mathcal{A}}^{\left(l\right)}(2^{m_a},n_a,k_a^{\left(l\right)},d_a^{\left(l\right)})$ has minimum Hamming distance $d_a^{\left(l\right)}=n_a-k_a^{\left(l\right)}+1$. With an odd minimum distance, it can correct up to $t_a^{\left(l\right)}=\frac{n_a-k_a^{\left(l\right)}}{2}$ errors and up to $n_a-k_a^{\left(l\right)}$ erasures. The probability $P_{a^{\left(l\right)}}$ of a decoding error with error and erasure decoding at the l-th level can be computed as follows [50].

$$\begin{array}{cc}\hfill P_{a^{\left(l\right)}}=& \sum _{j=t_a^{\left(l\right)}+1}^{n_a}\sum _{i=d_a^{\left(l\right)}-2j}^{n_a}\left(\genfrac{}{}{0pt}{}{n_a}{j}\right)\left(\genfrac{}{}{0pt}{}{n_a-j}{i}\right)·\hfill \\ \hfill & {\rho }_{b^{\left(l\right)}}^j{\lambda }_{b^{\left(l\right)}}^i{(1-{\rho }_{b^{\left(l\right)}}-{\lambda }_{b^{\left(l\right)}})}^{n_a-j-i},\hfill \end{array}$$

(11)

where ${\rho }_{b^{\left(l\right)}}$ is the error probability for the inner code ${\mathcal{B}}^{\left(l\right)}$ and ${\lambda }_{b^{\left(l\right)}}$ is the erasure probability. Using the union bound, the word error rate $P_e$ of the GC code can be estimated by the sum of the error probability over all levels

$$P_e\le \sum _{l=0}^{L-1}{P}_{a^{\left(l\right)}}.$$

(12)

The sum in Equation (12) is dominated by the largest probability $P_{a^{\left(l\right)}}$. Hence, the design aims at balancing these error probabilities over all levels for a target channel error rate. The error and erasure probabilities for the inner codes can be estimated based on a computer simulation or by bounds.

We estimate the error probabilities with cell-wise encoding; i.e., we consider the m bits of a flash cell as a code symbol of the inner code. For instance, consider a code over a $2^m$-ary alphabet with an even minimum distance of $d_b^{\left(l\right)}$. This code can correct all patterns where the number of errors is at most $t_b^{\left(l\right)}=\frac{d_b^{\left(l\right)}-2}{2}$, whereas $t_b^{\left(l\right)}+1$ errors can be detected as uncorrectable and an erasure is declared. Under the mentioned assumptions, the erasure probability is bounded by

$${\lambda }_{b^{\left(l\right)}}\le \sum _{j=t_b^{\left(l\right)}+1}^{{\mathfrak{n}}_{\mathfrak{b}}}\left(\genfrac{}{}{0pt}{}{{\mathfrak{n}}_{\mathfrak{b}}}{j}\right)p_s^j{(1-p_s)}^{{\mathfrak{n}}_{\mathfrak{b}}-j},$$

(13)

where $p_s$ denotes the symbol error rate and ${\mathfrak{n}}_{\mathfrak{b}}$ is the code length in $2^m$-ary symbols. Similarly, the error probability is bounded by

$${\rho }_{b^{\left(l\right)}}\le \sum _{j=t_b^{\left(l\right)}+2}^{{\mathfrak{n}}_{\mathfrak{b}}}\left(\genfrac{}{}{0pt}{}{{\mathfrak{n}}_{\mathfrak{b}}}{j}\right)p_s^j{\left(1-p_s\right)}^{{\mathfrak{n}}_{\mathfrak{b}}-j}.$$

(14)

For the code design, we utilize the Gray labeling and the fact that the probability of an error to non-adjacent states is very small. Using a Gray code, the vast majority of symbol errors result in an error pattern where only a single bit out of the m bits of a cell can be in error. Hence, we use binary inner codes and interpret these codes over a $2^m$-ary alphabet, where the number of symbols is ${\mathfrak{n}}_{\mathfrak{b}}=n_b/m$. In this case, the bounds in Equations (13) and (14) are not rigorous, but they can still be used to estimate the error probabilities for the code design and to explain the gain of the cell-wise encoding.

For instance, consider the LSB page for Gray code 2 with the model explained in Section 3. Under the discussed assumptions, the bit error probability for the LSB page $p_{b,LSB}$ is approximately equal to the error rate $p_e$, and we have the symbol error rate $p_s\approx 1.75p_e$. By designing a GC code for page-wise encoding, we can use Equations (13) and (14), but we have to substitute the code length ${\mathfrak{n}}_{\mathfrak{b}}$ with the length of the binary code $n_b$ and $p_s$ with the bit error rate. This leads to much higher error probabilities for the inner code with page-wise encoding. For instance, consider the binary code $\mathcal{B}(120,112,4)$ for $p_{b,LSB}=0.01$. With cell-wise encoding, we have ${\lambda }_b\approx 0.13$ and ${\rho }_b\approx 0.025$ according to Equations (13) and (14), whereas with page-wise encoding we obtain ${\lambda }_b\approx 0.29$ and ${\rho }_b\approx 0.095$.

4.4. Code Examples

Finally, we constructed error correction codes with different sizes and rates that meet requirements for flash memories. The parameters of the GC codes were designed to guarantee a specified word error rate (WER) in certain channel conditions. The code parameters were optimized to balance the error rates in Equation (12) based on the bounds Equations (11), (13), and (14). We used GC codes at this point because we could guarantee a very low residual error rate. We designed the codes such that joint decoding guaranteed a target WER. For comparison, the same code was used for pagewise decoding.

For the mapping, the length of the inner code must be divisible by the number m of bits per cell, i.e., $m=3$ for TLC and $m=4$ for QLC. We used extended BCH codes for the inner codes. Hence, all inner codes had an even minimum Hamming distance. The additional parity bit was used to detect decoding failures. In the case of a decoding failure, an erasure was declared for the outer RS decoder.

First, we consider a code for a TLC Flash memory with rate $R\approx 0.9$ for a 4 kB payload of data. The detailed code parameters are shown in

Table 3. Exemplary GC code (N = 36,414, K = 32,768, $R\approx 0.9$) for TLC (designed for WER ${10}^{-15}$).

Level	Inner Code	Outer Code
1	$\mathcal{B}(153,144,4)$	$\mathcal{A}(2^8,238,148,91)$
2	$\mathcal{B}(153,136,6)$	$\mathcal{A}(2^8,238,202,37)$
3	$\mathcal{B}(153,128,8)$	$\mathcal{A}(2^8,238,220,19)$
4	$\mathcal{B}(153,120,10)$	$\mathcal{A}(2^8,238,226,13)$
5	$\mathcal{B}(153,112,12)$	$\mathcal{A}(2^8,238,230,9)$
6	$\mathcal{B}(153,104,14)$	$\mathcal{A}(2^8,238,232,7)$
7	$\mathcal{B}(153,96,16)$	$\mathcal{A}(2^8,238,234,5)$
8	$\mathcal{B}(153,88,18)$	$\mathcal{A}(2^8,238,234,5)$
9	$\mathcal{B}(149,80,20)$	$\mathcal{A}(2^8,238,236,3)$
10	$\mathcal{B}(149,72,22)$	$\mathcal{A}(2^8,238,236,3)$
11	$\mathcal{B}(149,64,24)$	$\mathcal{A}(2^8,238,236,3)$
12	$\mathcal{B}(149,56,26)$	$\mathcal{A}(2^8,238,236,3)$
13	$\mathcal{B}(149,48,28)$	$\mathcal{A}(2^8,238,236,3)$
14–18	$\mathcal{B}(149,40,30)$	$\mathcal{A}(2^8,238,238,1)$

. For the second example, we consider a code of rate $R\approx 0.87$ for a 2 kB payload of data.

Table 4. Exemplary GC code (N = 18,810, K = 16,386, $R\approx 0.87$) for TLC (designed for WER ${10}^{-15}$).

Level	Inner Code	Outer Code
1	$\mathcal{B}(114,106,4)$	$\mathcal{A}(2^8,165,101,65)$
2	$\mathcal{B}(113,98,6)$	$\mathcal{A}(2^8,165,137,29)$
3	$\mathcal{B}(112,90,8)$	$\mathcal{A}(2^8,165,151,17)$
4	$\mathcal{B}(111,82,10)$	$\mathcal{A}(2^8,165,155,11)$
5	$\mathcal{B}(110,74,12)$	$\mathcal{A}(2^8,165,157,9)$
6	$\mathcal{B}(109,66,14)$	$\mathcal{A}(2^8,165,159,7)$
7	$\mathcal{B}(108,58,16)$	$\mathcal{A}(2^8,165,161,5)$
8	$\mathcal{B}(114,50,22)$	$\mathcal{A}(2^8,165,163,3)$
9	$\mathcal{B}(113,42,24)$	$\mathcal{A}(2^8,165,163,3)$
10–13	$\mathcal{B}(112,34,28)$	$\mathcal{A}(2^8,165,165,1)$

shows the corresponding code parameters.

Table 5. Exemplary GC code (N = 36,300, K = 32,783, $R\approx 0.9$) for QLC (designed for WER ${10}^{-16}$).

Level	Inner Code	Outer Code
1	$\mathcal{B}(220,211,4)$	$\mathcal{A}(2^8,165,51,15)$
2	$\mathcal{B}(220,203,6)$	$\mathcal{A}(2^8,165,113,53)$
3	$\mathcal{B}(220,195,8)$	$\mathcal{A}(2^8,165,139,27)$
4	$\mathcal{B}(220,187,10)$	$\mathcal{A}(2^8,165,149,17)$
5	$\mathcal{B}(220,179,12)$	$\mathcal{A}(2^8,165,155,11)$
6	$\mathcal{B}(220,171,14)$	$\mathcal{A}(2^8,165,157,9)$
7	$\mathcal{B}(220,163,16)$	$\mathcal{A}(2^8,165,159,7)$
8	$\mathcal{B}(220,155,18)$	$\mathcal{A}(2^8,165,161,5)$
9	$\mathcal{B}(216,147,20)$	$\mathcal{A}(2^8,165,161,5)$
10	$\mathcal{B}(216,139,22)$	$\mathcal{A}(2^8,165,161,5)$
11–15	$\mathcal{B}(216,131,24)$	$\mathcal{A}(2^8,165,163,3)$
16–26	$\mathcal{B}(216,91,38)$	$\mathcal{A}(2^8,165,165,1)$

provides a code for QLC Flash memory for 4 kB payload of data and rate $R\approx 0.9$ and

Table 6. Exemplary GC code (N = 38,500, K = 32,773, $R\approx 0.85$) for QLC (designed for WER ${10}^{-16}$).

Level	Inner Code	Outer Code
2	$\mathcal{B}(220,203,6)$	$\mathcal{A}(2^8,175,41,135)$
3	$\mathcal{B}(220,195,8)$	$\mathcal{A}(2^8,175,101,75)$
4	$\mathcal{B}(220,187,10)$	$\mathcal{A}(2^8,175,135,41)$
5	$\mathcal{B}(220,179,12)$	$\mathcal{A}(2^8,175,151,25)$
6	$\mathcal{B}(220,171,14)$	$\mathcal{A}(2^8,175,159,17)$
7	$\mathcal{B}(220,163,16)$	$\mathcal{A}(2^8,175,163,13)$
8	$\mathcal{B}(220,155,18)$	$\mathcal{A}(2^8,175,167,9)$
9	$\mathcal{B}(216,147,20)$	$\mathcal{A}(2^8,175,167,9)$
10	$\mathcal{B}(216,139,22)$	$\mathcal{A}(2^8,175,169,7)$
11	$\mathcal{B}(216,131,24)$	$\mathcal{A}(2^8,175,171,5)$
12	$\mathcal{B}(216,123,26)$	$\mathcal{A}(2^8,175,171,5)$
13	$\mathcal{B}(216,115,28)$	$\mathcal{A}(2^8,175,171,5)$
14–18	$\mathcal{B}(216,107,30)$	$\mathcal{A}(2^8,175,173,3)$
19–26	$\mathcal{B}(216,67,46)$	$\mathcal{A}(2^8,175,173,3)$

provides a code with almost the same code dimension and rate $R\approx 0.85$.

5. Performance Analysis

In this section, we present numerical results for the GC codes with hard-input decoding. Each page of the flash cell has a different channel condition depending on the selected bit-labeling. It is common to plot the word error rate (WER) of an error correction code over the bit error probability of the flash memory. However, the different pages have different bit error rates. Hence, we plot the WER results versus the bit error probability averaged over all pages. Regarding the TLC flash memory, we consider Gray code 1 and Gray code 2 from Table 1. Remember that among the presented TLC codes, Gray code 1 has the best error balance over the pages, and it has the best labeling considering the channel capacities for page-wise read.

We compare the joint encoding to the page-wise encoding for the different pages. In the later case, the bits are interleaved over all pages. In contrast to [24], we applied hard-input decoding. Soft-input decoding would probably achieve higher gains but would also require channel estimation in order to determine the log-likelihood ratios for the different bits.

The channel model from Section 3 is based on measurements of a particular NAND flash memory. In order to analyze the codes for different flash types and different code rates, we calculated the error probabilities according to a unipolar amplitude-shift keying with additive Gaussian noise. This channel model approximates an ideal flash channel where all states have the same noise variance. Nevertheless, the different pages had different error rates and channel capacities due to the bit-labeling. The presented numerical results were calculated with the formulas provided in Section 4. For the analysis, we used the same GC code for each page and for the cell-wise approach.

The channel analysis procedure randomly generated binary symbols, and encoded and converted them to m-ary symbols. Then, an average error probability was calculated, the corresponding variance was determined according to the channel model and applied to the m-ary symbol. The symbol with variance was then hard decoded and converted back to a binary vector. This binary vector was subsequently decoded with the corresponding presented GC decoder.

Figure 6 presents results for the GC code from Table 3 at rate $R=0.9$ using Gray codes 1 and 2. The page-wise encoding in the right figure considers the worst-case page, i.e., the LSB page for Gray code 2. This page has the highest bit error probability, whereas the MSB and CSB pages show relatively good error rates. The curves labeled with joint decoding correspond to a cell-wise encoding where all three pages are used uniformly. Hence, the bit error rate is the average value for all pages.

Next, we compare the GC code with rate $R=0.87$ with 2 kB from Table 4 for a TLC model. The left part of Figure 7 presents the word error rate for the different pages and the joint decoding using Gray code 1. The right part of the figure shows the performance with Gray code 2. Note that the MSB page with Gray code 2 achieves a WER of <${10}^{-15}$ at the average RBER of ${10}^{-2}$ and is therefore not visible in the figure.

Finally, we present results for Gray codes for QLC Flash. A QLC flash has 4=four pages which are sequentially numbered, starting with the MSB page as page 1 and having the LSB page as page 4.

Table 7. Possible Gray code bit-labeling for a QLC flash cell.

Charge State	Page No.	${\mathit{S}}_0$	${\mathit{S}}_1$	${\mathit{S}}_2$	${\mathit{S}}_3$	${\mathit{S}}_4$	${\mathit{S}}_5$	${\mathit{S}}_6$	${\mathit{S}}_7$	${\mathit{S}}_8$	${\mathit{S}}_9$	${\mathit{S}}_{10}$	${\mathit{S}}_{11}$	${\mathit{S}}_{12}$	${\mathit{S}}_{13}$	${\mathit{S}}_{14}$	${\mathit{S}}_{15}$
Gray code 4	1	1	1	0	0	0	1	1	1	1	1	1	0	0	0	0	0
	2	1	0	0	0	0	0	0	1	1	1	0	0	1	1	1	1
	3	1	1	1	0	0	0	0	0	0	1	1	1	1	0	0	1
	4	1	1	1	1	0	0	1	1	0	0	0	0	0	0	1	1
Gray code 5	1	1	1	1	1	0	0	0	0	0	0	0	1	1	1	1	0
	2	1	1	1	0	0	0	0	1	1	1	1	1	0	0	0	0
	3	1	1	0	0	0	0	1	1	1	0	0	0	0	1	1	1
	4	1	0	0	0	0	1	1	1	0	0	1	1	1	1	0	0

shows two possible Gray code labels for QLC Flash. Gray code 4 was presented in [51]. For this code, page 1 has three thresholds, and pages 2 to 4 have four thresholds for bit selection. This labeling results in well-balanced error probabilities. The page error probabilities for good channel conditions are $p_{b,page1}\approx \frac{3}{8}{p}_e$ and $p_{b,page2}=p_{b,page3}=p_{b,page4}\approx \frac{1}{4}{p}_e$.

The left part of Figure 8 presents numerical results using Gray code 4 and the GC code from Table 5. Pages 2, 3, and 4 provide the same WER, whereas page 1 provides a lower WER than the other pages. For this code, the joint encoding using the GC code results only in a small improvement compared to the performance of the worst-case pages.

The right part of Figure 8 shows numerical results using Gray code 5 with the GC code from Table 5. Gray code 5 has 3 thresholds for page 1 and page 2, 4 thresholds for page 3, and 5 thresholds for page 4. The page error probabilities for good channel conditions using Gray code 5 are $p_{b,page1}=p_{b,page2}\approx \frac{3}{8}{p}_e$, $p_{b,page3}\approx \frac{1}{2}{p}_e$, and $p_{b,page4}\approx \frac{5}{8}{p}_e$. In this case, the GCC code with joint encoding achieved a significant gain compared to the worst-case pages.

In Figure 9, results are shown for two Gray codes for the GC code from Table 6. Note that in the left figure, the curves for page 2, 3, and 4 are on top of each other. With page-wise encoding, Gray code 5 provides better performance compared with Gray code 4. The joint encoding improves the reliability compared to the worst pages.

The presented results show that bit-labeling plays a significant role in page-wise decoding approaches. The average error rates of the different Gray codes are dominated by the worst page. The error correction performance can also be improved with larger code lengths. Similarly to the cell-wise encoding, a larger code length also impairs the random access read latency. However, a joint encoding achieves larger gains than longer codes over a single page.

In Figure 10, we compare the rate $R=0.9$ and 4 kB of payload data codes for the QLC and TLC model with respect to the signal-to-noise ratio measured in terms of the energy per bit to noise power spectral density ratio ($E_b/N_0$). Storing more information bits per cell requires a higher signal-to-noise ratio in order to distinguish between different charge states.

6. Conclusions

In this work, we have investigated an error correction approach for TLC and QLC flash memories where all bits stored in a cell are jointly encoded using Gray labeling. This cell-wise encoding improves the achievable channel capacity compared with conventional independent page-wise encoding. The objective of the proposed approach is to avoid the costly soft-input decoding as long as possible. The performance of the joint decoding does not depend on the particular Gray code, whereas the error probabilities with page-wise encoding strongly depend on the bit-labeling. The average error probability of all pages is dominated by the page with the highest error probability. The presented results for joint decoding demonstrate a performance gain due to the cell-wise encoding compared to bit-interleaved coded modulation, where the bits are interleaved over all pages. A bit-interleaved coded modulation (BICM) approach similar to that in [24,25] would achieve better performance. However, such a method requires soft-input decoding and channel estimation to calculate log-likelihood ratios for the different bits depending on the estimated charge state.

The considered GC codes were designed to guarantee residual error probabilities of ${10}^{-15}$ and ${10}^{-16}$. Such residual error rates are required for industrial applications. Moreover, the results presented in this work are focused on hard-input decoding. On the other hand, the cell-wise encoding also improves the achievable capacity for soft-input decoding. We think that the code design for cell-wise encoding with soft-input decoding is an interesting research direction.

PLC flash memories are already being developed [4]. PLC–NAND enables a large number of possible bit-labeling codes. Due to the larger number of bits per cell, codes that reduce the inter-cell interference might be an interesting approach for this technology [26].