{'fraction_non_alphanumeric': 0.0545031392076207, 'fraction_numerical': 0.012232084866854297, 'mean_word_length': 3.6765375854214124, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Lower Bounds on the Number of Writing Operations by ILIFC with Inversion Cells

Index-less Indexed Flash Code (ILIFC) is a coding scheme for flash memories, in which one bit of a data sequence is stored in a slice consisting of several cells but the index of the bit is stored implicitly. Although several modified ILIFC schemes have been proposed, in this research we consider an ILIFC with inversion cells(I-ILIFC). The I-ILIFC reduces the total number of cell level changes at each writing request. Computer simulation is used to show that the I-ILIFC improves the average performance of the ILIFC in many cases. This paper presents our derivation of the lower bounds on the number of writing operations by I-ILIFC and shows that the worst-case performance of the I-ILIFC is better than that of the ILIFC if the code length is sufficiently large. Additionally, we consider the tight lower bounds thereon. The results show that the threshold of the code length that determines whether the I-ILIFC improves the worst-case performance of the ILIFC is smaller than that in the first lower bounds.


I. INTRODUCTION
In flash memory, data bits are stored in cells in the form of charge levels. One of the most notable characteristics of flash memory is the asymmetricity of charging and discharging operations. That is, the charge level of the cell can be increased in a cell-by-cell manner but cannot be decreased in this manner.
Instead, discharging is achieved by way of a special operation known as block erasure, which discharges the cells in a long block simultaneously. The disadvantage of the block erasure operation is that it partially destroys cells in the flash memory and thus increases the error probability. This necessitates the use of an error correcting code. However, the cells invariably become highly unreliable after block erasure is executed a certain number of times.
This led to the proposal of a flash code to reduce the number of block erasure operations [6], [7]. Mahdavifar et al. addressed the problem by proposing the index-less indexed flash code (ILIFC). The ILIFC is designed in terms of the worst-case performance [1]. In the ILIFC, both the value of one bit of data and the index of the bit are stored in one slice. The ILIFC uses the cell state space very efficiently even though the code rate is not optimal.
Several modified ILIFC schemes capable of improving the performance of the ILIFC have since been proposed [2], [4], [5]. In this paper, we consider an ILIFC with inversion cells (I-ILIFC) [2]. The I-ILIFC reduces the total number of cell level changes at each writing request in order to increase the number of writing operations between two consecutive block erasures. Computer simulation was used to show that the I-ILIFC improves the average performance of the ILIFC in many cases [2], [3].
This work theoretically shows that the worst-case performance of the I-ILIFC is better than that of the ILIFC. Firstly, we derive the lower bounds on the number of writing operations by I-ILIFC and specify a threshold for the code length that determines whether the I-ILIFC improves the worst-case performance of the ILIFC. The results show that the I-ILIFC is better than the ILIFC in the worst case if the code length is sufficiently large.
Additionally, we consider unusual writing in addition to the usual writing by the I-ILIFC and determine the tight lower bounds on the number of writing operations. Consequently, we show that the threshold is smaller than that in the first lower bounds.

II. INDEX-LESS INDEXED FLASH CODE(ILIFC)
In this work, it is assumed that the level of electric charge in a cell of a NAND flash memory is in the range A q = {0, 1, · · · , q − 1}. A block of data bits of length k is encoded and stored in a block of cells of length n. An ILIFC that satisfies these conditions is denoted by ILIFC(n, k, q).
In the ILIFC the block of cells of length n is divided into slices consisting of k cells and, therefore, the number of slices in the block is m = ⌊n/k⌋. If n is not a multiple of k, the remaining cells in the block are unused. Each slice represents one bit of the k data bits. Since k slices are used to store k data bits, we require m ≥ k, that is, n ≥ k 2 .
The state of m slices is denoted by ( Suppose that the value of the i-th bit is changed. If none of the slices represent the i-th bit, an empty slice is reserved for the bit and then the level of the i-th cell in the slice is changed to 1. In the case that no empty slices exist, block erasure is incurred. On the other hand, if there is a slice representing the i-th bit, the weight of the slice is increased by 1. In the beginning, the level of the i-th cell in the slice is increased. If the level of the i-th cell is q − 1, the level of the i ′ -th cell is increased where i ′ = (i mod k) + 1. Similarly, if the level of the i ′ -th cell is also q − 1, the level of the i ′′ -th cell is increased where i ′′ = (i ′ mod k) + 1. This procedure enables the value of the bit, which is represented by bv(x), to be obtained for the active slice x. Additionally, the index of the bit is represented by the position of the first updated cell in x. This updating procedure is performed until the slice is filled to capacity.
Note that any full slice cannot represent the index. In the ILIFC the value of a bit without any corresponding slice is considered to be 0. Therefore, for the full slice x ′ , wt(x ′ ) = k(q − 1) should be even. Thus, in this work it is assumed that k or q − 1 is even.
The state of slices (x 1 | x 2 | · · · | x m ) enables the k bit data (s 1 , s 2 , · · · , s k ) to be obtained as follows. For each Usually, a single writing operation to flash memory involves changing a single data bit stored in the memory [1], [7]. However, in this research, one writing operation entails updating all the cells such that the resulting cells represent the new data. If the new data is equal to the current data, then we assume that no writing operation has occurred. The number of writing operations that can occur between two consecutive block erasures is simply referred to as the number of writings. The number of writings depends on the sequence of data to be stored. The minimum number of writings is termed the worst-case number of writings.
Assume that the state of m slices ( is termed the total number of changes in the cell level.

III. ILIFC WITH INVERSION CELLS
Suppose that a writing operation in which the current data v is changed into the new data v ′ is conducted by ILIFC. If such a writing can be achieved without block erasure, the total number of cell level changes is equal to the Hamming distance between v and v ′ . An ILIFC with inversion cells (I-ILIFC) was proposed in order to reduce the total number of cell level changes [2]. The I-ILIFC has two storing modes, a normal mode and an inverted mode, information about which is contained in the inversion cells.
In this research it is assumed that k bit data are stored in a block of n q-ary cells including r inversion cells. Such an I-ILIFC is denoted by I-ILIFC(n, k, q, r). In the I-ILIFC(n, k, q, r), a block of (n − r) cells except for the r inversion cells is divided into slices consisting of k cells. These cells, which are divided into slices, are termed data cells. Hence, there are m = ⌊(n − r)/k⌋ slices. The restriction of the ILIFC scheme, m ≥ k, determines that n ≥ k 2 + r should hold.
In the I-ILIFC, the storing mode is represented by r inversion cells. We denote the state of these r inversion cells by b = (b 1 , b 2 , · · · , b r ) ∈ A r q . We denote the state of the inversion cells and m slices by is termed the sum of the data cell level changes and wt(b ′ ) − wt(b) is termed the sum of the inversion cell level changes. The sum of these two values is referred to as the total number of cell level changes.
In the I-ILIFC, when a writing operation is executed, one of two modes is selected such that the total number of cell level changes is minimized. The following theorem holds [2]. Theorem 1. Suppose a writing operation, in which the current data v are changed into the new data v ′ , is carried out by I-ILIFC(n, k, q, r), where v, v ′ ∈ {0, 1} k . In order to minimize the total number of cell level changes, the storing mode is changed by writing if and When the mode is changed by writing, the sum of the data cell level changes is and the sum of the inversion cell level changes is 1. Hence, the total number of cell level changes is (k − d + 1). On the other hand, when the mode is not changed by writing, the total number of cell level changes is equal to the sum of the data cell level changes, that is, d > (k + 1)/2, the writing operation that changes the mode is selected such that the total number of cell level changes is minimized. Additionally, if d ≤ (k + 1)/2, the above discussion shows that a writing operation that does not change the mode is selected.
For the state of r inversion cells b = (b 1 , b 2 , · · · , b r ) ∈ A r q , the inversion cells are said to be exhausted if b 1 = b 2 = · · · = b r = q − 1, that is, wt(b) = r(q − 1). Then writing that does not change the storing mode occurs until the next block erasure takes place.

IV. AVERAGE PERFORMANCE OF I-ILIFC
In this section, computer simulation is used to show that the average number of writings by I-ILIFC(n, k, q, r) is greater than that by ILIFC(n, k, q) in many cases when the length of inversion cells r is optimized [2], [3].
The restriction of the ILIFC scheme determines that n − r ≥ k 2 should be satisfied. If (n − r) mod k = 0, there are data cells that will never be used for the slice. Therefore, we consider only values of r that satisfy n − r ≥ k 2 and (n − r) mod k = 0.
For example, the average number of writings by I-ILIFC(640, 16, 4, r) and I-ILIFC(192, 8, 8, r) for each r are shown in Fig. 1 and Fig. 2, respectively. Note that I-ILIFC(n, k, q, 0) is equivalent to ILIFC(n, k, q). In our simulations, the average number of writings was calculated after 10, 000 block erasures took place. It can be seen that the average performance is maximized at r = 32 for I-ILIFC (640, 16, 4, r) and at r = 24 for I-ILIFC (192, 8, 8, r). Similarly the average performance of I-ILIFC(288, 12, 4, r) is shown in Fig. 3. This result indicates that the performance of I-ILIFC(288, 12, 4, r) is maximized at r = 0. That is, the I-ILIFC does not improve the performance of the original ILIFC.
In this research we analyze the worst-case performance and specify a threshold that determines whether the I-ILIFC improves the worst-case performance of the ILIFC. The results show that the I-ILIFC is better than the ILIFC if the code length is sufficiently large.

V. UPPER BOUND ON THE WORST-CASE NUMBER OF WRITINGS BY ILIFC
Under the definition of one writing operation in [1], it is shown that the worst-case number of writings by ILIFC(n, k, q) is k(⌊n/k⌋ − k + 1)(q − 1) + k − 1 [1]. Let t w be the worst-case number of writings by ILIFC(n, k, q) under the definition of one writing in this research. In this section, we derive the upper bound on t w .

VI. MAXIMUM NUMBER OF UNUSED CELL LEVELS IN I-ILIFC
In this work, it is assumed that a sufficient number of inversion cells are reserved such that the inversion cells are not entirely consumed whenever block erasure takes place.
When block erasure takes place, that is, a writing operation that minimizes the total number of cell level changes without the erasure is not possible, we denote the state of slices by (y 1 | y 2 | · · · | y m ), where m = ⌊(n − r)/k⌋. Then the weight of each of the slices wt(y j ) can be increased (k(q − 1) − wt(y j )) more times. The sum of such unused cell levels m j=1 (k(q − 1) − wt(y j )) is termed the number of unused cell levels. In this section, we determine the maximum number of unused cell levels. For , let d be the Hamming distance between v and v ′ . If the data v is changed into v ′ such that the total number of cell level changes is minimized, from Theorem 1 the sum of the data cell level changes is d if d ≤ (k + 1)/2 and (k−d) if d > (k+1)/2. Hence, if k is even, the maximum sum of the data cell level changes δ is as follows.
Similarly, if k is odd, .
For the state of slices (y 1 | y 2 | · · · | y m ), let α 1 be the number of bits without any corresponding slice and let α 2 be the number of empty slices. Then the next writing that minimizes the total number of cell level changes can always be carried out if and only if the changes of any δ bits among k data bits can be stored in slices, that is, (α 1 < δ and α 2 ≥ α 1 ) or (α 1 ≥ δ and α 2 ≥ δ).
This condition is equivalent to the following condition.
Therefore, block erasure may take place if and only if The number of bits that have the corresponding slice is (k − α 1 ). Let y ji be the slice corresponding to the i-th bit from the left among (k − α 1 ) such bits. Since y ji is active, 1 ≤ wt(y ji ) ≤ k(q − 1)− 1. Then the number of unused cell levels is as follows.
When (2) holds, the maximum number of unused cell levels is derived. For fixed values of α 1 and α 2 , the number of unused cell levels is maximized when wt(y j1 ) = · · · = wt(y j k−α 1 ) = 1. Hence, the maximum is expressed as follows.
We have the following theorem.

Theorem 2.
In the I-ILIFC(n, k, q, r), when block erasure takes place, the number of unused cell levels u satisfies the following inequality.

VII. LOWER BOUNDS ON THE NUMBER OF WRITINGS BY I-ILIFC
In this section, we show the lower bounds on the worst-case number of writings by I-ILIFC.
Let (y 1 | y 2 | · · · | y m ) be the state of slices, where m = ⌊(n−r)/k⌋. Then m j=1 wt(y j ) is termed the number of used cell levels. From Theorem 2, we have the following theorem.

Theorem 3.
In the I-ILIFC(n, k, q, r), when block erasure takes place, the number of used cell levels u ′ satisfies the following inequality.
Proof. Let (y 1 | y 2 | · · · | y m ) be the state of slices. From Theorem 2, where m = ⌊(n − r)/k⌋. Corollary 1. If the number of used cell levels u ′ satisfies the following inequality the next writing by I-ILIFC(n, k, q, r) can always be executed without block erasure.
Proof. This is the contraposition of Theorem 3.
For fixed values of n, k and q, we define Then we define t 1 (r) = ⌈U 1 (r)/δ⌉. Let r * 1 be the minimum integer r that satisfies r(q − 1) ≥ U ′ 1 (r)/δ + 1. That is, r * 1 is the integer r that satisfies R 1 ≤ r < R 1 + 1, where The restriction on the ILIFC scheme requires n ≥ k 2 +r * 1 to be satisfied. Note that n > k 2 + r * 1 is satisfied if n ≥ k 2 + R 1 + 1, that is, holds. Then from R 1 > 0, r * 1 ≥ 1 and U 1 (r * 1 ) > 0 hold. In the following, it is assumed that (6) is satisfied.
The following theorem holds.
Proof. In the initial state (i.e., immediately after block erasure) the number of used cell levels is 0 and 0 < U 1 (r * 1 ) holds. Hence, Corollary 1 determines that the first writing by I-ILIFC(n, k, q, r * 1 ) can always be executed. For t < t 1 (r * 1 ) we suppose that t writings by I-ILIFC(n, k, q, r * 1 ) can always occur without block erasure. Let (b | y 1 | y 2 | · · · | y m ) be the state of inversion cells and slices after t writings.
because when one writing operation has occurred, the maximum sum of the inversion cell level changes is 1. Hence, r * 1 inversion cells are not used in their entirety. Additionally, m j=1 wt(y j ) ≤ δt < δ · U 1 (r * 1 )/δ = U 1 (r * 1 ). Therefore, according to Corollary 1, the next (t+1)-th writing can always take place.
The above discussion serves to confirm that t 1 (r * 1 ) writings by I-ILIFC(n, k, q, r * 1 ) can always be carried out without erasure.
The results show that the I-ILIFC(n, k, q, r * 1 ) improves the worst-case performance of ILIFC(n, k, q) if the code length n is sufficiently large.

VIII. TIGHT LOWER BOUND
Thus far, we assumed that block erasure takes place when a writing operation that minimizes the total number of cell level changes cannot be accomplished by I-ILIFC. However, at the moment it remains possible to carry out a writing operation that does not minimize these changes. In this paper, such a writing operation is termed unusual. The number of block erasures can be reduced by ensuring that, if an unusual writing operation can be accomplished without erasure, it occurs before erasure takes place. Therefore, in this section, it is assumed that block erasure takes place if neither a usual writing operation (which minimizes the total number of cell level changes) nor an unusual writing operation can occur. Consequently, we derive the tight lower bounds on the number of writings under this assumption.

A. Maximum number of unused cell levels
We determine the maximum number of unused cell levels when block erasure takes place. We have the following theorem.

Theorem 5.
For the state of slices (y 1 | y 2 | · · · | y m ), let β 1 be the number of bits that do not have a corresponding slice and let β 2 be the number of empty slices. Then block erasure may take place if and only if ⌊β 1 /2⌋ > β 2 .
Proof. Initially, we show that, if ⌊β 1 /2⌋ ≤ β 2 holds, either the next usual or unusual writing can always be executed without block erasure. It is supposed that l bits among β 1 bits without any corresponding slice are changed on the data (not on the sequence stored in the slices) where 0 ≤ l ≤ β 1 .
The inequality l ≤ β 2 determines that the changes that are made to l bits can be stored in l slices among β 2 empty slices. Hence, writing that does not change the mode can be carried out.
Hence, the mode is changed and the changes related to (β 1 −l) bits can be stored in (β 1 −l) slices among β 2 empty slices. Therefore, writing that changes the mode can occur.
The above discussion shows that either usual or unusual writing can be executed if ⌊β 1 /2⌋ ≤ β 2 .

Theorem 6.
In the I-ILIFC(n, k, q, r), when block erasure takes place, the number of unused cell levels u satisfies the following inequality.
From Theorem 6, we have the following theorem.

Theorem 7.
In the I-ILIFC(n, k, q, r), when block erasure takes place, the number of used cell levels u ′ satisfies the following inequality.

Corollary 2.
If the number of used cell levels u ′ satisfies the following inequality either the next usual or unusual writing by I-ILIFC(n, k, q, r) can always be executed without block erasure.
Proof. This is the contraposition of Theorem 7.
The above discussion indicates that t 1 (r * 2 ) usual writings can always be executed without block erasure.