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.

Quantifying Earthquake Collapse Risk of Tall Steel Braced Frame Buildings Using Rupture-to-Rafters Simulations

This thesis examines collapse risk of tall steel braced frame buildings using rupture-to-rafters simulations due to suite of San Andreas earthquakes. Two key advancements in this work are the development of (i) a rational methodology for assigning scenario earthquake probabilities and (ii) an artificial correction-free approach to broadband ground motion simulation. The work can be divided into the following sections: earthquake source modeling, earthquake probability calculations, ground motion simulations, building response, and performance analysis.

As a first step the kinematic source inversions of past earthquakes in the magnitude range of 6-8 are used to simulate 60 scenario earthquakes on the San Andreas fault. For each scenario earthquake a 30-year occurrence probability is calculated and we present a rational method to redistribute the forecast earthquake probabilities from UCERF to the simulated scenario earthquake. We illustrate the inner workings of the method through an example involving earthquakes on the San Andreas fault in southern California.

Next, three-component broadband ground motion histories are computed at 636 sites in the greater Los Angeles metropolitan area by superposing short-period (0.2~s-2.0~s) empirical Green's function synthetics on top of long-period ($>$ 2.0~s) spectral element synthetics. We superimpose these seismograms on low-frequency seismograms, computed from kinematic source models using the spectral element method, to produce broadband seismograms.

Using the ground motions at 636 sites for the 60 scenario earthquakes, 3-D nonlinear analysis of several variants of an 18-story steel braced frame building, designed for three soil types using the 1994 and 1997 Uniform Building Code provisions and subjected to these ground motions, are conducted. Model performance is classified into one of five performance levels: Immediate Occupancy, Life Safety, Collapse Prevention, Red-Tagged, and Model Collapse. The results are combined with the 30-year probability of occurrence of the San Andreas scenario earthquakes using the PEER performance based earthquake engineering framework to determine the probability of exceedance of these limit states over the next 30 years.

Entrainment of fine sediments by turbulent flows

A study was made of the means by which turbulent flows entrain sediment grains from alluvial stream beds. Entrainment was considered to include both the initiation of sediment motion and the suspension of grains by the flow. Observations of grain motion induced by turbulent flows led to the formulation of an entrainment hypothesis. It was based on the concept of turbulent eddies disrupting the viscous sublayer and impinging directly onto the grain surface. It is suggested that entrainment results from the interaction between fluid elements within an eddy and the sediment grains.

A pulsating jet was used to simulate the flow conditions in a turbulent boundary layer. Evidence is presented to establish the validity of this representation. Experiments were made to determine the dependence of jet strength, defined below, upon sediment and fluid properties. For a given sediment and fluid, and fixed jet geometry there were two critical values of jet strength: one at which grains started to roll across the bed, and one at which grains were projected up from the bed. The jet strength K, is a function of the pulse frequency, ω, and the pulse amplitude, A, defined by

K = Aω^-s

Where s is the slope of a plot of log A against log ω. Pulse amplitude is equal to the volume of fluid ejected at each pulse divided by the cross sectional area of the jet tube.

Dimensional analysis was used to determine the parameters by which the data from the experiments could be correlated. Based on this, a method was devised for computing the pulse amplitude and frequency necessary either to move or project grains from the bed for any specified fluid and sediment combination.

Experiments made in a laboratory flume with a turbulent flow over a sediment bed are described. Dye injection was used to show the presence, in a turbulent boundary layer, of two important aspects of the pulsating jet model and the impinging eddy hypothesis. These were the intermittent nature of the sublayer and the presence of velocities with vertical components adjacent to the sediment bed.

A discussion of flow conditions, and the resultant grain motion, that occurred over sediment beds of different form is given. The observed effects of the sediment and fluid interaction are explained, in each case, in terms of the entrainment hypothesis.

The study does not suggest that the proposed entrainment mechanism is the only one by which grains can be entrained. However, in the writer’s opinion, the evidence presented strongly suggests that the impingement of turbulent eddies onto a sediment bed plays a dominant role in the process.

Wave induced oscillations in harbors of arbitrary shape

Theoretical and experimental studies were conducted to investigate the wave induced oscillations in an arbitrary shaped harbor with constant depth which is connected to the open-sea.

A theory termed the “arbitrary shaped harbor” theory is developed. The solution of the Helmholtz equation, ∇²f + k²f = 0, is formulated as an integral equation; an approximate method is employed to solve the integral equation by converting it to a matrix equation. The final solution is obtained by equating, at the harbor entrance, the wave amplitude and its normal derivative obtained from the solutions for the regions outside and inside the harbor.

Two special theories called the circular harbor theory and the rectangular harbor theory are also developed. The coordinates inside a circular and a rectangular harbor are separable; therefore, the solution for the region inside these harbors is obtained by the method of separation of variables. For the solution in the open-sea region, the same method is used as that employed for the arbitrary shaped harbor theory. The final solution is also obtained by a matching procedure similar to that used for the arbitrary shaped harbor theory. These two special theories provide a useful analytical check on the arbitrary shaped harbor theory.

Experiments were conducted to verify the theories in a wave basin 15 ft wide by 31 ft long with an effective system of wave energy dissipators mounted along the boundary to simulate the open-sea condition.

Four harbors were investigated theoretically and experimentally: circular harbors with a 10° opening and a 60° opening, a rectangular harbor, and a model of the East and West Basins of Long Beach Harbor located in Long Beach, California.

Theoretical solutions for these four harbors using the arbitrary shaped harbor theory were obtained. In addition, the theoretical solutions for the circular harbors and the rectangular harbor using the two special theories were also obtained. In each case, the theories have proven to agree well with the experimental data.

It is found that: (1) the resonant frequencies for a specific harbor are predicted correctly by the theory, although the amplification factors at resonance are somewhat larger than those found experimentally,(2) for the circular harbors, as the width of the harbor entrance increases, the amplification at resonance decreases, but the wave number bandwidth at resonance increases, (3) each peak in the curve of entrance velocity vs incident wave period corresponds to a distinct mode of resonant oscillation inside the harbor, thus the velocity at the harbor entrance appears to be a good indicator for resonance in harbors of complicated shape, (4) the results show that the present theory can be applied with confidence to prototype harbors with relatively uniform depth and reflective interior boundaries.

Transonic wind tunnel for investigation of turbomachinery blades

The design of a two-stream wind tunnel was undertaken to allow the simulation and study of certain features of the flow field around the blades of high-speed axial-flow turbomachineries. The mixing of the two parallel streams with designed Mach numbers respectively equal to 1.4 and 0.7 will simulate the transonic Mach number distribution generally obtained along the tips of the first stage blades in large bypass-fan engines.

The GALCIT hypersonic compressor plant will be used as an air supply for the wind tunnel, and consequently the calculations contained in the first chapter are derived from the characteristics and the performance of this plant.

The transonic part of the nozzle is computed by using a method developed by K. O. Friedrichs. This method consists essentially of expanding the coordinates and the characteristics of the flow in power series. The development begins with prescribing, more or less arbitrarily, a Mach number distribution along the centerline of the nozzle. This method has been programmed for an IBM 360 computer to define the wall contour of the nozzle.

A further computation is carried out to correct the contour for boundary layer buildup. This boundary layer analysis included geometry, pressure gradient, and Mach number effects. The subsonic nozzle is calculated {including boundary layer buildup) by using the same computer programs. Finally, the mixing zone downstream of the splitter plate was investigated to prescribe the wall contour correction necessary to ensure a constant-pressure test section.