Integer Codes Correcting Asymmetric Errors in Nand Flash Memory

Abstract

Memory devices based on floating-gate transistor have recently become dominant technology for non-volatile storage devices like USB flash drives, memory cards, solid-state disks, etc. In contrast to many communication channels, the errors observed in flash memory device use are not random but of special, mainly asymmetric, type. Integer codes which have proved their efficiency in many cases with asymmetric errors can be applied successfully to flash memory devices, too. This paper presents a new construction and integer codes over a ring of integers modulo $A=2^n+1$ capable of correcting single errors of type $(1,2),(\pm 1,\pm 2)$, or $(1,2,3)$ that are typical for flash memory devices. The construction is based on the use of cyclotomic cosets of 2 modulo A. The parity-check matrices of the codes are listed for $n\le 10.$

1. Introduction

The NAND (NOT AND) logic type memory devices based on floating-gate transistor have recently become dominant technology for non-volatile storage devices like USB flash drives, memory cards, solid-state disk, etc. This technology has advantages regarding storage density, cost, power consumption and erase and write times but bytes cannot be addressed independently. The hierarchical structure of NAND flash is as follows: A series of NAND cells is connected in strings which are organized in pages, pages are organized in blocks and so on. This architecture requires reading and writing to be done only in pages. Moreover, before writing any data in a page of a block this block must be erased. Hence erasing is block-wise.

Data processing in NAND flash memories is realized by changing the voltage at inputs. The corresponding physical processes in the cells can generates errors in the work of the memory. Recently used technology for 3D NAND memory of vertically stacked cells additionally increases the probability of errors. Therefore, NAND flash memory requires error control coding. In many commercial flash memory devices classical error correcting codes are implemented, e.g., Hamming codes, BCH codes, Reed–Solomon codes. However, these codes are designed for channels where the errors with the same weight are equally probable, which is not true for flash memories.

Abstractly, flash memory can be considered as a device comprising blocks of “cells” that can take on a given number of different states (levels). The process of writing involves an increasing level of the cell or erasing the entire block before increasing the level of a cell in that block. Errors can be a wrong increase of the level or more rarely a decrease during the process of storage.

A mathematical model that describes well the processes in flash memory is the following. Let the cells have A states, that is, store ${log}_2\left(A\right)$ bits. Then we can consider pages and blocks as vectors over the ring ${\mathbb{Z}}_A$ of integers modulo A. Then errors can be considered as changes of the values of vectors’ entries. The aforesaid shows that usually changes of the entries of the vectors are in an upward direction but with limited-magnitude values. Moreover, decreasing mainly with 1 is observed. Hence we can say that dominant errors are symmetric of type $\pm 1$ and $(2,3,\dots l)$ for a small l. This fact gives rise to the need to invent and study asymmetric limited-magnitude error correcting codes over ${\mathbb{Z}}_A$ (known also as integer codes).

Asymmetric limited-magnitude error-correcting codes were proposed by Varshamov and Tenengolz [1,2] and in a more general form by Ahlswede et al. [3]. Another general method for constructionof asymmetric limited-magnitude error-correcting codes is provided by Cassuto et al. [4]. In 2011, T. Klove and B. Bose [5] proposed systematic codes that correct single limited-magnitude systematic asymmetric errors and achieve a higher rate than the ones given in [4]. They also showed how their code construction can be slightly modified to give codes correcting symmetric errors of limited magnitude. Later T. Klove et al. [6] extended their results and gave a necessary and sufficient condition for the existence of a code over $GF\left(p\right)$ correcting a single asymmetric error.

In this paper we propose a constructions of codes over ${\mathbb{Z}}_{2^n+1}$ correcting single asymmetric errors of type $(1,2)$, $(\pm 1,\pm 2)$ or $(1,2,3)$. The argument $A=2^n+1$ is chosen due to the fact that it is the closest to, while greater than, a power of two. The choice of A is essential since the use of the unsuitable size of the alphabet can generate problems in implementation of encoding and decoding procedures. Moreover, as we shall see later, the proposed codes are perfect.

The next parts of the paper are organized as follows. A summary of existing results and necessary notations and definitions which are used in this paper are given in Section 2. In Section 3 new constructions of integer codes for flash memory are proposed. Concluding remarks and some open problems are presented and discussed in Section 4. In the Appendix, more detailed information about constructed codes is presented.

2. Preliminaries

Codes over finite alphabets of integers for correcting asymmetric errors are constructed in [1,2]. With the name “integer codes”, such codes are applied to magnetic recording and frame synchronization in [7]. For that, time integer codes have been studied for various purposes and used in many applications. Coding for flash multilevel memory is an area they can be successfully applied to.

Let us recall basic definitions.

Definition 1.

Let ${\mathbb{Z}}_A$ be the ring of integers modulo A. An integer code of length n with parity-check matrix $\mathbf{H}\in {\mathbb{Z}}_A^{m\times n}$ is said to be a subset of ${\mathbb{Z}}_A^n$, defined by

$$\mathcal{C}\left(\mathbf{H}\right)=\{\mathbf{c}\in {\mathbb{Z}}_A^n|\mathbf{c}{\mathbf{H}}^T=\mathbf{0}\}$$

where all zeros vector $\mathbf{0}\in {\mathbb{Z}}_A^m.$ (We will write only $\mathcal{C}$ if there is no possibility for ambiguity.)

We shall say that $\mathcal{C}$ is ${[n,n-m]}_A$ integer code. This notation is widely used for linear code with block length n and dimension $n-m$ but in this paper it only means that $\mathbf{H}$ has m rows, n columns and entries from ${\mathbb{Z}}_A$. We remind the reader that if A is not a prime then C is not a linear subspace. It is a submodule whose properties, although very close to ones of linear subspaces, are different. In partial, the size of C may differ from $A^{n-m}$. However the differences do not impact correcting properties of considered codes. The aforesaid notation is used only for convenience with no reference to the dimension of the code.

In contrast to conventional codes, integer codes are intended to correct specific types of errors. By choosing a proper parity-check matrix one can construct a code correcting specific types of errors like as given below.

Definition 2.

Let $l_j$ and $k_i$ be positive integers, $j=1,\dots ,m,i=1,\dots ,s.$ The code $\mathcal{C}\left(\mathbf{H}\right)$ is said to be a single $(\pm k_1,\pm k_2,\dots ,\pm k_s,l_1,l_2,\dots ,l_m)$ error correctable if it can correct any error vector with only one nonzero entry with value $l_j$ or $\pm k_i.$

In order for $\mathcal{C}\left(\mathbf{H}\right)$ to be single $(\pm k_1,\pm k_2,\dots ,\pm k_s,l_1,l_2,\dots ,l_m)$ error correctable the corresponding error vectors must have pairwise disjoint syndromes ${\mathbf{eH}}^T$. However, there are $(2s+m)n$ possible single $(\pm k_1,\pm k_2,\dots ,\pm k_s,l_1,l_2,\dots ,l_m)$ error vectors $\mathbf{e}$. Hence, we obtain a lower bound for the size A of the alphabet

$$A\ge (2s+m)n+1.$$

Definition 3.

A single $(\pm k_1,\pm k_2,\dots ,\pm k_s,l_1,l_2,\dots ,l_m)$ error correctable code $\mathcal{C}\left(\mathbf{H}\right)$ of block length n over ${\mathbb{Z}}_A$ is called perfect if $A=(2s+m)n+1.$ If the size A of the alphabet is the minimal possible for which a single $(\pm k_1,\pm k_2,\dots ,\pm k_s,l_1,l_2,\dots ,l_m)$ error correctable code $\mathcal{C}\left(\mathbf{H}\right)$ of block length n over ${\mathbb{Z}}_A$ exists, we say that $\mathcal{C}$ is optimal.

For many parameters, perfect codes do not exist. In these cases the goal is to construct an optimal code.

3. New Construction of Integer Codes Correcting Single Error of Type $\mathbf{(}\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{)}\mathbf{,}\mathbf{(}\mathbf{\pm }\mathbf{1}\mathbf{,}\mathbf{\pm }\mathbf{2}\mathbf{)}\mathbf{,}$ or $\mathbf{(}\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{3}\mathbf{)}$

To construct a single error correctable code it is sufficient to find a parity-check matrix with one row, i.e.,

$$\mathbf{H}=(h_1,h_2,\dots ,h_n),h_i\in {\mathbb{Z}}_A$$

and

$$\mathcal{C}\left(\mathbf{H}\right)=\{\mathbf{c}\in {\mathbb{Z}}_A^n|\sum _{i=1}^n{c}_i{h}_i=0\}$$

Such codes have only one parity-check symbol, i.e., the best possible rate $(n-1)/n.$ The syndrome corresponding to a single error e in position i is $e{h}_i$. Therefore such a code can correct a single error e if all $e{h}_i$ are distinct.

Theorem 1.

Let $A=2^n+1$ and $A_s=\{s{2}^i(modA)\mid i=0,1,\dots \}$ be the cyclotomic coset of 2 modulo A with leader s. Let $A_s^0=\{s{2}^{2i}(modA)\mid i=0,1,\dots \}$, $A_s^1=\{s{2}^{2i+1}(modA)\mid i=0,1,\dots \}$. Then $|A_s|$ is even with $|A_s|=2n$ for $(s,A)=1$ and both the integer codes with $\mathbf{H}=\left(A_1^0\right)$ and $\mathbf{H}=\left(A_1^1\right)$ are single $(1,2)$ asymmetric error correctable.

Proof. 

$2^n\equiv -1(modA)$ gives $2^{2n}\equiv 1(modA)$. Hence the order m of 2 modulo A is a divisor of $2n$. The assumption $m\mid n$ leads to $2^n\equiv 1(modA)$, which is a contradiction. Thus $m=2k$, where $k|n$. Therefore the number of elements $|A_1|$ of $A_1$ is even. The same holds for one of any cyclotomic coset $A_s=\{s{2}^i(modA)\mid i=0,1,\dots \}$ with $(s,A)=1.$

Now we shall show that the cardinality of $A_1$ is exactly $2n$. If $k<n$ then $A=2^n+1\ge 2^{2k}+1>2^{2k}-1$ which contradicts A dividing $2^{2k}-1$. Hence $k=n.$ For $(s,A)=1$ also $|A_s|=2n$ holds since $s{2}^{2k}\equiv s$ iff $2^{2k}\equiv 1(modA)$.

The integer code with parity-check matrix $\mathbf{H}=\left(A_1^0\right)$ has length n and only one parity-check equation, i.e., rate $(n-1)/n$. The syndrome corresponding to a single error with value 1 is an element of $A_1^0$. If the value is 2 the syndrome belongs to $2A_1^0=A_1^1(modA)$. Hence the syndromes are distinct. □

Corollary 1.

Under the notations of Theorem 1, let $s_1,s_2,\dots ,s_t$ be all different leaders of cyclotomic cosets of 2 modulo A. Then

$$\mathbf{H}=(A_{s_1}^0{A}_{s_2}^0\cdots A_{s_t}^0)$$

is a parity-check matrix of a single $(1,2)$ asymmetric error correctable $[2^{n-1},2^{n-1}-1]$ code over A.

Example 1.

Let $A=2^4+1=17$, i.e., $n=4$. In this case

$$A_1=\{1,2,4,8,16,15,13,9\}\mathrm{and}{A}_3=\{3,6,12,7,14,11,5,10\}$$

are all nonzero cyclotomic cosets. Then

$$A_1^0=\{1,4,16,13\}\equiv \{1,4,-1-4\},A_1^1=\{2,8,15,9\}\equiv \{2,8,-2,-8\};$$

$$A_3^0=\{3,12,14,5\}\equiv \{3,12,-3,-12\},A_3^1=\{6,7,11,10\}\equiv \{6,7,-6,-7\}$$

The code with a parity-check matrix

$$\mathbf{H}=\{1,4,16,13,3,12,14,5\}$$

is a single $(1,2)$ asymmetric error correctable code and is perfect.

Such codes are also ones with parity-check matrices

$$\mathbf{H}=\left(A_1^0{A}_3^1\right),\mathbf{H}=\left(A_1^1{A}_3^1\right),\mathbf{H}=\left(A_1^1{A}_3^0\right).$$

If $A_1^{00}=\{1,4\}$ and $A_3^{00}=\{3,12\}$ it is easy to check that the code with

$$\mathbf{H}=(A_1^{00},A_3^{00})=(1,4,3,12)$$

is single $(\pm 1,\pm 2)$ error correctable. Such codes are also ones with

$$\mathbf{H}=(2,8,3,12),\mathbf{H}=(2,8,6,7),\mathbf{H}=(1,4,6,7).$$

The codes with matrices $\mathbf{H}=\left(A_1^0\right),\left(A_1^1\right),\left(A_3^0\right),$ or $\left(A_3^1\right)$ are a single $(1,2,3)$ asymmetric error correctable.

Corollary 2.

If $n>2$ the code with $\mathbf{H}=\left(A_1^0\right)$ is a single $(1,2,3)$ asymmetric error correctable.

Proof. 

Assume $3\in A_1$. Then $3\equiv 2^{n+k}(modA)$ for $1\le k\le n-1$; thus, $3\equiv -2^k(modA).$ This means that A divides $2^k+3$, which is impossible for $n>2$, since $A=2^n+1\ge 2^k+2^{n-1}+1>2^k+3.$ Therefore, 3 is a leader of a cyclomic coset, namely $A_3$. Now arguments similar to ones used in Example 1 complete the proof. □

Theorem 2.

Under the notations of Theorem 1 let $A_s^{00}$ be the set of first $\lfloor \left(\right|A_s^0\left|\right)/2\rfloor$ elements of $A_s^0$. If $|A_s|\ge 8$ then $A_s^{00}$ is a parity-check matrix of a single $(\pm 1,\pm 2)$ error correctable code.

Proof. 

$A_s$ modulo $A=2^n+1$ has the structure

$$A_s=\{s,2s,\dots ,2^{k-1}s,-s,-2s,\dots ,-2^{k-1}s\},k|n,|A_s|=2k.$$

$$\begin{array}{ccc}\hfill k=2l+1& A_s^0=\{s,4s,\dots ,2^{2l}s,-2s,-2^{3}s,\dots ,-2^{2l-1}s\}& A_s^1=-A_s^0\hfill \\ \hfill k=2l+2& A_s^0=\{s,4s,\dots ,2^{2l},-s,-2^{2}s,\dots ,-2^{2l}s\}& A_s^0=-A_s^0.\hfill \end{array}$$

$A_s^{00}$ consists of first l elements of $A_s^0$ for k odd and first $l+1$ elements when k is even. The condition $|A_s|\ge 8$ guarantees that $|A_s^{00}|\ge 2$ (the minimal possible size of H is $1\times 2$). Hence the multiplication by $(-1)$ maps $A_s^{00}$ into the negative part of $A_s^1$ when k is odd and into the negative part of $A_s^0$ for even k. Multiplying by 2 maps it into the positive part of $A_s^1$, while multiplying by $-2$ maps it into the negative part of $A_s^0$, or $A_s^1$ for k odd or even, respectively. Therefore syndromes are distinct. □

Corollary 3.

Using notation and conditions of Theorem 2 the code with

$$\mathbf{H}=(A_{s_1}^{00}{A}_{s_2}^{00}\cdots A_{s_t}^{00})$$

is a single $(\pm 1,\pm 2)$ error correctable code over A when $|A_{s_i}|\ge 4$ and $s_i$ are distinct leaders.

Remark 1.

Since $t\ge 2$ we can allow $|A_{s_i}^{00}|=1$, i.e., $|A_{s_i}|=4$.

In Example 1 A is a prime and $A_1$ and $A_3$ are all nontrivial cyclotomic cosets both of length $2n=8.$ However in general the structure is more complex. We continue with a simple example.

Example 2.

Let $A=2^5+1=33=3\times 11$. The cyclotomic cosets are

$$A_1=\{1,2,4,8,16,32,31,29,25,17\},A_3=\{3,6,12,24,15,30,27,21,9,18\},$$

$$A_5=\{5,10,20,7,14,28,23,13,26,19\},A_{11}=\{11,22\}.$$

Three of them are with length $2n=10$ and one with length 2. Note that 3 is not coprime with 33 but $|A_3|=10$. The reason is that $2^2\equiv 1(mod3)$; thus, $11\times 2^2\equiv 11(mod33)$, while concerning the order of 2 modulo the prime 11 is 10; thus, $3\times 2^{10}\equiv 3(mod33)$ and 10 is the minimal of such a positive integer.

We can construct a single $(1,2)$ asymmetric error correctable code of length 16 over 33 taking

$$\mathbf{H}=\{1,4,16,31,25,3,12,15,27,9,5,20,14,23,26,11\}.$$

Since

$$A_1^{00}=\{1,4\};A_3^{00}=\{3,12\};A_5^{00}=\{5,20\}.$$

the code with parity-check matrix

$$\mathbf{H}=(1,4,3,12,5,20)$$

is $(\pm 1,\pm 2)$ error correctable.

We can obtain also a single $(1,2,3)$ asymmetric error correctable code of length 10 by taking matrix

$$\mathbf{H}=\{A_1^0,A_5^1\}=\{1,4,16,31,25,10,7,28,13,19\}.$$

We use $A_5^1$ instead of $A_5^0$ because $3A_5^0=3A_1^0$. The reason is that $A_5^0\equiv A_1^0(mod11)$.

Here are several properties of the numbers of the form $2^n+1$ that can be useful. Their proofs are straightforward and we omit them.

P1.

If n has odd divisor d then $2^{\frac{n}{d}}+1$ divides $2^n+1.$ In partial if n is odd $3\left|\right(2^n+1).$

P2.

Let $n=2^{a}m,$ where m is odd positive integer. Then

$$A=2^n+1=2^{2^{a}m}+1=(2^{2^a}+1)B=F_{a}B,$$

where $F_a=2^{2^a}+1$ is Fermat number. $F_a$ is a prime for $a=0,1,2,3,4$ (no other such primes are known) but even $F_4=65,537$ is too large for a divisor of practically interesting value of A.

P3.

If $A=2^n+1=(2^k+1)B$ then $A_B$ has length $2k$. If there is a cyclotomic coset of length $2k$ then $2^k+1$ divides A.

Example 3.

Let $A=2^6+1=65=5\times 13$. The cyclotomic classes of 2 modulo 65 are $A_1,A_3,A_5,A_7,A_{11}$ with cardinality 12 each and

$$A_{13}=\{13,26,52,39\}.$$

Therefore the code with a parity-check matrix

$$\mathbf{H}=(A_1^0,A_3^0,A_5^0,A_7^0,A_{11}^0,A_{13}^0)$$

is a single $(1,2)$ error correctable code with length 32.

The code with a parity-check matrix

$$\mathbf{H}=(1,4,16,3,12,48,5,20,15,7,28,47,11,44,46,13)$$

is a single $(\pm 1,\pm 2)$ error correctable $[16,15]$ code.

The code with

$$\mathbf{H}=(A_1^0,A_7^0,13)=(1,4,16,64,61,49,7,28,47,58,37,18,13)$$

is a single $(1,2,3)$ error correctable code with block length 13 since $3A_1^0\subset A_3,3A_7^0\subset A_{11}$ and $2\times 13\ne 3\times 13\in A_{13}.$

Construction of single $(1,2,3)$ error correctable codes.

Construction of such codes strongly depends on the value of $A=2^n+1$ and we cannot formulate statement more general than the one in Corollary 2 but can formulate some principles to be followed when one searches such codes. The matrix $\mathbf{H}=\left(A_1^0\right)$ is the start point for construction. Next we have to enlarge the code by adding some $A_i^0$ or $A_i^1$, taking into account the following simple observations

• If $A_j=3A_i$ then $A_j$ has to be excluded.
• For n odd 3 divides A and the situation $3A_j=3A_i$ can happen. In this case if $A_i^0$ is included in $\mathbf{H}$ then $A_j\setminus 3A_i^0$ (which is $A_j^0$ or $A_j^1$) can be included. For n even $(3,A)=1$ and the considered situation is impossible.

Table 1. Single $(1,2),(\pm 1,\pm 2)$, or $(1,2,3)$ errors correctable codes over $A=2^n+1$.

n	A	$(1,2)$	$(\pm 1,\pm 2)$	$(1,2,3)$
3	9	[4,3]	no	[2,1]
4	17	[8,7]	[4,3]	[4,3]
5	33	[16,15]	[6,5]	[10,9]
6	65	[32,31]	[16,15]	[13,12]
7	129	[64,63]	[27,26]	[35,34]
8	257	[128,127]	[64,63]	[48,47]
9	513	[256,255]	[113,112]	[64,63]
10	1025	[512,511]	[256,255]	[211,210]

presents parameters of the single error correctable codes constructed by our method over $A=2^n+1$ for $3\le n\le 10$ (the cases $n=1,2$ are trivial). The parity-check matrices are given in Examples 1–3 and in Appendix A.

4. Discussion

In this paper we consider only codes over ${\mathbb{Z}}_A,A=2^n+1,$ with one parity-check equation that is sufficient for correction of a single error. There are constructions using matrices with more rows but they require more parity-check symbols; thus, they have a lower rate. Herein we construct codes only with a maximal rate.

Encoding is a computation of only one linear expression. Decoding can be done by using a syndrome error table. Both operations are very fast and simple for modern digital devices.

All codes correcting single $(1,2)$ error are perfect. The same holds for codes correcting $(\pm 1,\pm 2)$ error but only when n is even.

Parity-check matrices for $n>10$ are too large to be presented in the paper although the fast development of technologies makes such parameters interesting for practice. However, the described construction algorithm is simple to realize and interested readers can easily construct and implement such codes.

Our further investigations aim to develop construction of codes over $A=2^n+1$ correcting two or more errors of the considered type. Examples of double error correctable codes can be found, for example, in [8,9], but they are not applicable to flash memories.