Rewriting Schemes for Flash Memory

Flash memory is a leading storage media with excellent features such as random access and high storage density. However, it also faces significant reliability and endurance challenges. In flash memory, the charge level in the cells can be easily increased, but removing charge requires an expensive erasure operation. In this thesis we study rewriting schemes that enable the data stored in a set of cells to be rewritten by only increasing the charge level in the cells. We consider two types of modulation scheme; a convectional modulation based on the absolute levels of the cells, and a recently-proposed scheme based on the relative cell levels, called rank modulation. The contributions of this thesis to the study of rewriting schemes for rank modulation include the following: we

•propose a new method of rewriting in rank modulation, beyond the previously proposed method of “push-to-the-top”;

•study the limits of rewriting with the newly proposed method, and derive a tight upper bound of 1 bit per cell;

•extend the rank-modulation scheme to support rankings with repetitions, in order to improve the storage density;

•derive a tight upper bound of 2 bits per cell for rewriting in rank modulation with repetitions;

•construct an efficient rewriting scheme that asymptotically approaches the upper bound of 2 bit per cell.

The next part of this thesis studies rewriting schemes for a conventional absolute-levels modulation. The considered model is called “write-once memory” (WOM). We focus on WOM schemes that achieve the capacity of the model. In recent years several capacity-achieving WOM schemes were proposed, based on polar codes and randomness extractors. The contributions of this thesis to the study of WOM scheme include the following: we

•propose a new capacity-achievingWOM scheme based on sparse-graph codes, and show its attractive properties for practical implementation;

•improve the design of polarWOMschemes to remove the reliance on shared randomness and include an error-correction capability.

The last part of the thesis studies the local rank-modulation (LRM) scheme, in which a sliding window going over a sequence of real-valued variables induces a sequence of permutations. The LRM scheme is used to simulate a single conventional multi-level flash cell. The simulated cell is realized by a Gray code traversing all the relative-value states where, physically, the transition between two adjacent states in the Gray code is achieved by using a single “push-to-the-top” operation. The main results of the last part of the thesis are two constructions of Gray codes with asymptotically-optimal rate.

Investigation of competitive antagonist binding to the nicotinic acetylcholine receptor using voltage-jump and light-flash techniques

1. The effect of 2,2’-bis-[α-(trimethylammonium)methyl]azobenzene (2BQ), a photoisomerizable competitive antagonist, was studied at the nicotinic acetycholine receptor of Electrophorus electroplaques using voltage-jump and light-flash techniques.

2. 2BQ, at concentrations below 3 μΜ, reduced the amplitude of voltage-jump relaxations but had little effect on the voltage-jump relaxation time constants under all experimental conditions. At higher concentrations and voltages more negative than -150 mV, 2BQ caused significant open channel blockade.

3. Dose-ratio studies showed that the cis and trans isomers of 2BQ have equilibrium binding constants (K _ᵢ) of .33 and 1.0 μΜ, respectively. The binding constants determined for both isomers are independent of temperature, voltage, agonist concentration, and the nature of the agonist.

4. In a solution of predominantly cis-2BQ, visible-light flashes led to a net cis→trans isomerization and caused an increase in the agonist-induced current. This increase had at least two exponential components; the larger amplitude component had the same time constant as a subsequent voltage-jump relaxation; the smaller amplitude component was investigated using ultraviolet light flashes.

5. In a solution of predominantly trans-2BQ, UV-light flashes led to a net trans→cis isomerization and caused a net decrease in the agonist-induced current. This effect had at least two exponential components. The smaller and faster component was an increase in agonist-induced current and had a similar time constant to the voltage-jump relaxation. The larger component was a slow decrease in the agonist-induced current with rate constant approximately an order of magnitude less than that of the voltage-jump relaxation. This slow component provided a measure of the rate constant for dissociation of cis-2BQ (k_ = 60/s at 20°C). Simple modelling of the slope of the dose-rate curves yields an association rate constant of 1.6 x 10⁸/M/s. This agrees with the association rate constant of 1.8 x 10⁸/M/s estimated from the binding constant (K_i). The Q₁₀ of the dissociation rate constant of cis-2BQ was 3.3 between 6° and 20°C. The rate constants for association and dissociation of cis-28Q at receptors are independent of voltage, agonist concentration, and the nature of the agonist.

6. We have measured the molecular rate constants of a competitive antagonist which has roughly the same K _ᵢ as d-tubocurarine but interacts more slowly with the receptor. This leads to the conclusion that curare itself has an association rate constant of 4 x 10⁹/M/s or roughly as fast as possible for an encounter-limited reaction.

Dielectric recovery of short A-C arcs between low-boiling-point electrodes

The re-ignition characteristics (variation of re-ignition voltage with time after current zero) of short alternating current arcs between plane brass electrodes in air were studied by observing the average re-ignition voltages on the screen of a cathode-ray oscilloscope and controlling the rates of rise of voltage by varying the shunting capacitance and hence the natural period of oscillation of the reactors used to limit the current. The shape of these characteristics and the effects on them of varying the electrode separation, air pressure, and current strength were determined.

The results show that short arc spaces recover dielectric strength in two distinct stages. The first stage agrees in shape and magnitude with a previously developed theory that all voltage is concentrated across a partially deionized space charge layer which increases its breakdown voltage with diminishing density of ionization in the field-tree space. The second stage appears to follow complete deionization by the electric field due to displacement of the field-free region by the space charge layer, its magnitude and shape appearing to be due simply to increase in gas density due to cooling. Temperatures calculated from this second stage and ion densities determined from the first stage by means of the space charge equation and an extrapolation of the temperature curve are consistent with recent measurements of arc value by other methods. Analysis or the decrease with time of the apparent ion density shows that diffusion alone is adequate to explain the results and that volume recombination is not. The effects on the characteristics of variations in the parameters investigated are found to be in accord with previous results and with the theory if deionization mainly by diffusion be assumed.

Class two p groups as fixed point free automorphism groups

Suppose that AG is a solvable group with normal subgroup G where (|A|, |G|) = 1. Assume that A is a class two odd p group all of whose irreducible representations are isomorphic to subgroups of extra special p groups. If p^c ≠ r^d + 1 for any c = 1, 2 and any prime r where r^2d+1 divides |G| and if C_G(A) = 1 then the Fitting length of G is bounded by the power of p dividing |A|.

The theorem is proved by applying a fixed point theorem to a reduction of the Fitting series of G. The fixed point theorem is proved by reducing a minimal counter example. IF R is an extra spec r subgroup of G fixed by A₁, a subgroup of A, where A₁ centralizes D(R), then all irreducible characters of A₁R which are nontrivial on Z(R) are computed. All nonlinear characters of a class two p group are computed.

Freshwater survey of the ditches around Hinkley Point Power Station, 20 June 1985

Sampling was concentrated on the North Moor region and the series of ditches which drained this area to the Bristol Channel. Although most ditches were not deep the mud substratum precluded sampling from within the habitat. All samples were taken with a pond net from the banks. Efforts were made to sample each part of the habitat although in some ditches the macrophyte growth was so intense as to make sampling difficult particularly of the sediments. Organisms were identified on the 10 sampling sites.

On the Cesari fixed point method in a Banach space

In a paper published in 1961, L. Cesari [1] introduces a method which extends certain earlier existence theorems of Cesari and Hale ([2] to [6]) for perturbation problems to strictly nonlinear problems. Various authors ([1], [7] to [15]) have now applied this method to nonlinear ordinary and partial differential equations. The basic idea of the method is to use the contraction principle to reduce an infinite-dimensional fixed point problem to a finite-dimensional problem which may be attacked using the methods of fixed point indexes.

The following is my formulation of the Cesari fixed point method:

Let B be a Banach space and let S be a finite-dimensional linear subspace of B. Let P be a projection of B onto S and suppose Г≤B such that pГ is compact and such that for every x in PГ, P^-1x∩Г is closed. Let W be a continuous mapping from Г into B. The Cesari method gives sufficient conditions for the existence of a fixed point of W in Г.

Let I denote the identity mapping in B. Clearly y = Wy for some y in Г if and only if both of the following conditions hold:

(i) Py = PWy.

(ii) y = (P + (I - P)W)y.

Definition. The Cesari fixed paint method applies to (Г, W, P) if and only if the following three conditions are satisfied:

(1) For each x in PГ, P + (I - P)W is a contraction from P^-1x∩Г into itself. Let y(x) be that element (uniqueness follows from the contraction principle) of P^-1x∩Г which satisfies the equation y(x) = Py(x) + (I-P)Wy(x).

(2) The function y just defined is continuous from PГ into B.

(3) There are no fixed points of PWy on the boundary of PГ, so that the (finite- dimensional) fixed point index i(PWy, int PГ) is defined.

Definition. If the Cesari fixed point method applies to (Г, W, P) then define i(Г, W, P) to be the index i(PWy, int PГ).

The three theorems of this thesis can now be easily stated.

Theorem 1 (Cesari). If i(Г, W, P) is defined and i(Г, W, P) ≠0, then there is a fixed point of W in Г.

Theorem 2. Let the Cesari fixed point method apply to both (Г, W, P₁) and (Г, W, P₂). Assume that P₂P₁=P₁P₂=P₁ and assume that either of the following two conditions holds:

(1) For every b in B and every z in the range of P₂, we have that ‖b=P₂b‖ ≤ ‖b-z‖

(2)P₂Г is convex.

Then i(Г, W, P₁) = i(Г, W, P₂).

Theorem 3. If Ω is a bounded open set and W is a compact operator defined on Ω so that the (infinite-dimensional) Leray-Schauder index i_LS(W, Ω) is defined, and if the Cesari fixed point method applies to (Ω, W, P), then i(Ω, W, P) = i_LS(W, Ω).

Theorems 2 and 3 are proved using mainly a homotopy theorem and a reduction theorem for the finite-dimensional and the Leray-Schauder indexes. These and other properties of indexes will be listed before the theorem in which they are used.

Coincidence point theorems in quasi-metric spaces without assuming the mixed monotone property and consequences in G-metric spaces

In this paper, we present some coincidence point theorems in the setting of quasi-metric spaces that can be applied to operators which not necessarily have the mixed monotone property. As a consequence, we particularize our results to the field of metric spaces, partially ordered metric spaces and G-metric spaces, obtaining some very recent results. Finally, we show how to use our main theorems to obtain coupled, tripled, quadrupled and multidimensional coincidence point results.

Coincidence and common fixed point theorems for Suzuki type hybrid contractions and applications

Coincidence and common fixed point theorems for a class of Suzuki hybrid contractions involving two pairs of single-valued and multivalued maps in a metric space are obtained. In addition, the existence of a common solution for a certain class of functional equations arising in a dynamic programming is also discussed.