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.

Random response of nonlinear continuous systems

This thesis presents a technique for obtaining the stochastic response of a nonlinear continuous system. First, the general method of nonstationary continuous equivalent linearization is developed. This technique allows replacement of the original nonlinear system with a time-varying linear continuous system. Next, a numerical implementation is described which allows solution of complex problems on a digital computer. In this procedure, the linear replacement system is discretized by the finite element method. Application of this method to systems satisfying the one-dimensional wave equation with two different types of constitutive nonlinearities is described. Results are discussed for nonlinear stress-strain laws of both hardening and softening types.

On erasure coding for distributed storage and streaming communications

The work presented in this thesis revolves around erasure correction coding, as applied to distributed data storage and real-time streaming communications.

First, we examine the problem of allocating a given storage budget over a set of nodes for maximum reliability. The objective is to find an allocation of the budget that maximizes the probability of successful recovery by a data collector accessing a random subset of the nodes. This optimization problem is challenging in general because of its combinatorial nature, despite its simple formulation. We study several variations of the problem, assuming different allocation models and access models, and determine the optimal allocation and the optimal symmetric allocation (in which all nonempty nodes store the same amount of data) for a variety of cases. Although the optimal allocation can have nonintuitive structure and can be difficult to find in general, our results suggest that, as a simple heuristic, reliable storage can be achieved by spreading the budget maximally over all nodes when the budget is large, and spreading it minimally over a few nodes when it is small. Coding would therefore be beneficial in the former case, while uncoded replication would suffice in the latter case.

Second, we study how distributed storage allocations affect the recovery delay in a mobile setting. Specifically, two recovery delay optimization problems are considered for a network of mobile storage nodes: the maximization of the probability of successful recovery by a given deadline, and the minimization of the expected recovery delay. We show that the first problem is closely related to the earlier allocation problem, and solve the second problem completely for the case of symmetric allocations. It turns out that the optimal allocations for the two problems can be quite different. In a simulation study, we evaluated the performance of a simple data dissemination and storage protocol for mobile delay-tolerant networks, and observed that the choice of allocation can have a significant impact on the recovery delay under a variety of scenarios.

Third, we consider a real-time streaming system where messages created at regular time intervals at a source are encoded for transmission to a receiver over a packet erasure link; the receiver must subsequently decode each message within a given delay from its creation time. For erasure models containing a limited number of erasures per coding window, per sliding window, and containing erasure bursts whose maximum length is sufficiently short or long, we show that a time-invariant intrasession code asymptotically achieves the maximum message size among all codes that allow decoding under all admissible erasure patterns. For the bursty erasure model, we also show that diagonally interleaved codes derived from specific systematic block codes are asymptotically optimal over all codes in certain cases. We also study an i.i.d. erasure model in which each transmitted packet is erased independently with the same probability; the objective is to maximize the decoding probability for a given message size. We derive an upper bound on the decoding probability for any time-invariant code, and show that the gap between this bound and the performance of a family of time-invariant intrasession codes is small when the message size and packet erasure probability are small. In a simulation study, these codes performed well against a family of random time-invariant convolutional codes under a number of scenarios.

Finally, we consider the joint problems of routing and caching for named data networking. We propose a backpressure-based policy that employs virtual interest packets to make routing and caching decisions. In a packet-level simulation, the proposed policy outperformed a basic protocol that combines shortest-path routing with least-recently-used (LRU) cache replacement.

Random propagation in complex systems : nonlinear matrix recursions and epidemic spread

This dissertation studies long-term behavior of random Riccati recursions and mathematical epidemic model. Riccati recursions are derived from Kalman filtering. The error covariance matrix of Kalman filtering satisfies Riccati recursions. Convergence condition of time-invariant Riccati recursions are well-studied by researchers. We focus on time-varying case, and assume that regressor matrix is random and identical and independently distributed according to given distribution whose probability distribution function is continuous, supported on whole space, and decaying faster than any polynomial. We study the geometric convergence of the probability distribution. We also study the global dynamics of the epidemic spread over complex networks for various models. For instance, in the discrete-time Markov chain model, each node is either healthy or infected at any given time. In this setting, the number of the state increases exponentially as the size of the network increases. The Markov chain has a unique stationary distribution where all the nodes are healthy with probability 1. Since the probability distribution of Markov chain defined on finite state converges to the stationary distribution, this Markov chain model concludes that epidemic disease dies out after long enough time. To analyze the Markov chain model, we study nonlinear epidemic model whose state at any given time is the vector obtained from the marginal probability of infection of each node in the network at that time. Convergence to the origin in the epidemic map implies the extinction of epidemics. The nonlinear model is upper-bounded by linearizing the model at the origin. As a result, the origin is the globally stable unique fixed point of the nonlinear model if the linear upper bound is stable. The nonlinear model has a second fixed point when the linear upper bound is unstable. We work on stability analysis of the second fixed point for both discrete-time and continuous-time models. Returning back to the Markov chain model, we claim that the stability of linear upper bound for nonlinear model is strongly related with the extinction time of the Markov chain. We show that stable linear upper bound is sufficient condition of fast extinction and the probability of survival is bounded by nonlinear epidemic map.

The search for gravitational waves from the coalescence of black hole binary systems in data from the LIGO and Virgo detectors. Or: A dark walk through a random forest

The LIGO and Virgo gravitational-wave observatories are complex and extremely sensitive strain detectors that can be used to search for a wide variety of gravitational waves from astrophysical and cosmological sources. In this thesis, I motivate the search for the gravitational wave signals from coalescing black hole binary systems with total mass between 25 and 100 solar masses. The mechanisms for formation of such systems are not well-understood, and we do not have many observational constraints on the parameters that guide the formation scenarios. Detection of gravitational waves from such systems — or, in the absence of detection, the tightening of upper limits on the rate of such coalescences — will provide valuable information that can inform the astrophysics of the formation of these systems. I review the search for these systems and place upper limits on the rate of black hole binary coalescences with total mass between 25 and 100 solar masses. I then show how the sensitivity of this search can be improved by up to 40% by the the application of the multivariate statistical classifier known as a random forest of bagged decision trees to more effectively discriminate between signal and non-Gaussian instrumental noise. I also discuss the use of this classifier in the search for the ringdown signal from the merger of two black holes with total mass between 50 and 450 solar masses and present upper limits. I also apply multivariate statistical classifiers to the problem of quantifying the non-Gaussianity of LIGO data. Despite these improvements, no gravitational-wave signals have been detected in LIGO data so far. However, the use of multivariate statistical classification can significantly improve the sensitivity of the Advanced LIGO detectors to such signals.

Magnetospheric access of solar particles and the configuration of the distant geomagnetic field

The access of 1.2-40 MeV protons and 0.4-1.0 MeV electrons from interplanetary space to the polar cap regions has been investigated with an experiment on board a low altitude, polar orbiting satellite (OG0-4).

A total of 333 quiet time observations of the electron polar cap boundary give a mapping of the boundary between open and closed geomagnetic field lines which is an order of magnitude more comprehensive than previously available.

Persistent features (north/south asymmetries) in the polar cap proton flux, which are established as normal during solar proton events, are shown to be associated with different flux levels on open geomagnetic field lines than on closed field lines. The pole in which these persistent features are observed is strongly correlated to the sector structure of the interplanetary magnetic field and uncorrelated to the north/south component of this field. The features were observed in the north (south) pole during a negative (positive) sector 91% of the time, while the solar field had a southward component only 54% of the time. In addition, changes in the north/south component have no observable effect on the persistent features.

Observations of events associated with co-rotating regions of enhanced proton flux in interplanetary space are used to establish the characteristics of the 1.2 - 40 MeV proton access windows: the access window for low polar latitudes is near the earth, that for one high polar latitude region is ~250 R_⊕ behind the earth, while that for the other high polar latitude region is ~1750 R_⊕ behind the earth. All of the access windows are of approximately the same extent (~120 R_⊕). The following phenomena contribute to persistent polar cap features: limited interplanetary regions of enhanced flux propagating past the earth, radial gradients in the interplanetary flux, and anisotropies in the interplanetary flux.

These results are compared to the particle access predictions of the distant geomagnetic tail configurations proposed by Michel and Dessler, Dungey, and Frank. The data are consistent with neither the model of Michel and Dessler nor that of Dungey. The model of Frank can yield a consistent access window configuration provided the following constraints are satisfied: the merging rate for open field lines at one polar neutral point must be ~5 times that at the other polar neutral point, related to the solar magnetic field configuration in a consistent fashion, the migration time for open field lines to move across the polar cap region must be the same in both poles, and the open field line merging rate at one of the polar neutral points must be at least as large as that required for almost all the open field lines to have merged in 0 (one hour). The possibility of satisfying these constraints is investigated in some detail.

The role played by interplanetary anisotropies in the observation of persistent polar cap features is discussed. Special emphasis is given to the problem of non-adiabatic particle entry through regions where the magnetic field is changing direction. The degree to which such particle entry can be assumed to be nearly adiabatic is related to the particle rigidity, the angle through which the field turns, and the rate at which the field changes direction; this relationship is established for the case of polar cap observations.

Stationary random response of multidegree-of-freedom systems

An approximate approach is presented for determining the stationary random response of a general multidegree-of-freedom nonlinear system under stationary Gaussian excitation. This approach relies on defining an equivalent linear system for the nonlinear system. Two particular systems which possess exact solutions have been solved by this approach, and it is concluded that this approach can generate reasonable solutions even for systems with fairly large nonlinearities. The approximate approach has also been applied to two examples for which no exact or approximate solutions were previously available.

Also presented is a matrix algebra approach for determining the stationary random response of a general multidegree-of-freedom linear system. Its derivation involves only matrix algebra and some properties of the instantaneous correlation matricies of a stationary process. It is therefore very direct and straightforward. The application of this matrix algebra approach is in general simpler than that of commonly used approaches.