Coding for information storage

Storage systems are widely used and have played a crucial rule in both consumer and industrial products, for example, personal computers, data centers, and embedded systems. However, such system suffers from issues of cost, restricted-lifetime, and reliability with the emergence of new systems and devices, such as distributed storage and flash memory, respectively. Information theory, on the other hand, provides fundamental bounds and solutions to fully utilize resources such as data density, information I/O and network bandwidth. This thesis bridges these two topics, and proposes to solve challenges in data storage using a variety of coding techniques, so that storage becomes faster, more affordable, and more reliable.

We consider the system level and study the integration of RAID schemes and distributed storage. Erasure-correcting codes are the basis of the ubiquitous RAID schemes for storage systems, where disks correspond to symbols in the code and are located in a (distributed) network. Specifically, RAID schemes are based on MDS (maximum distance separable) array codes that enable optimal storage and efficient encoding and decoding algorithms. With r redundancy symbols an MDS code can sustain r erasures. For example, consider an MDS code that can correct two erasures. It is clear that when two symbols are erased, one needs to access and transmit all the remaining information to rebuild the erasures. However, an interesting and practical question is: What is the smallest fraction of information that one needs to access and transmit in order to correct a single erasure? In Part I we will show that the lower bound of 1/2 is achievable and that the result can be generalized to codes with arbitrary number of parities and optimal rebuilding.

We consider the device level and study coding and modulation techniques for emerging non-volatile memories such as flash memory. In particular, rank modulation is a novel data representation scheme proposed by Jiang et al. for multi-level flash memory cells, in which a set of n cells stores information in the permutation induced by the different charge levels of the individual cells. It eliminates the need for discrete cell levels, as well as overshoot errors, when programming cells. In order to decrease the decoding complexity, we propose two variations of this scheme in Part II: bounded rank modulation where only small sliding windows of cells are sorted to generated permutations, and partial rank modulation where only part of the n cells are used to represent data. We study limits on the capacity of bounded rank modulation and propose encoding and decoding algorithms. We show that overlaps between windows will increase capacity. We present Gray codes spanning all possible partial-rank states and using only ``push-to-the-top'' operations. These Gray codes turn out to solve an open combinatorial problem called universal cycle, which is a sequence of integers generating all possible partial permutations.

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.

Photochemical electron transfer at fixed distance : a synthetic model of the photosynthetic primary process

A series of meso-phenyloctamethylporphyrins covalently bonded at the 4'phenyl position to quinones via rigid bicyclo[2.2.2]octane spacers were synthesized for the study of the dependence of electron transfer reaction rate on solvent, distance, temperature, and energy gap. A general and convergent synthesis was developed based on the condensation of ac-biladienes with masked quinonespacer-benzaldehydes. From picosecond fluorescence spectroscopy emission lifetimes were measured in seven solvents of varying polarity. Rate constants were determined to vary from 5.0x10⁹sec^-1 in N,N-dimethylformamide to 1.15x10¹⁰ Sec^-1 in benzene, and were observed to rise at most by about a factor of three with decreasing solvent polarity. Experiments at low temperature in 2-MTHF glass (77K) revealed fast, nearly temperature-independent electron transfer characterized by non-exponential fluorescence decays, in contrast to monophasic behavior in fluid solution at 298K. This example evidently represents the first photosynthetic model system not based on proteins to display nearly temperature-independent electron transfer at high temperatures (nuclear tunneling). Low temperatures appear to freeze out the rotational motion of the chromophores, and the observed nonexponential fluorescence decays may be explained as a result of electron transfer from an ensemble of rotational conformations. The nonexponentiality demonstrates the sensitivity of the electron transfer rate to the precise magnitude of the electronic matrix element, which supports the expectation that electron transfer is nonadiabatic in this system. The addition of a second bicyclooctane moiety (15 Å vs. 18 Å edge-to-edge between porphyrin and quinone) reduces the transfer rate by at least a factor of 500-1500. Porphyrinquinones with variously substituted quinones allowed an examination of the dependence of the electron transfer rate constant κ_ET on reaction driving force. The classical trend of increasing rate versus increasing exothermicity occurs from 0.7 eV≤ |ΔG^0'(R)| ≤ 1.0 eV until a maximum is reached (κ_ET = 3 x 10⁸ sec^-1 rising to 1.15 x 10¹⁰ sec^-1 in acetonitrile). The rate remains insensitive to ΔG⁰ for ~ 300 mV from 1.0 eV≤ |ΔG^0’(R)| ≤ 1.3 eV, and then slightly decreases in the most exothermic case studied (cyanoquinone, κ_ET = 5 x 10⁹ sec^-1).

Development of roll waves in open channels

This study is concerned with some of the properties of roll waves that develop naturally from a turbulent uniform flow in a wide rectangular channel on a constant steep slope . The wave properties considered were depth at the wave crest, depth at the wave trough, wave period, and wave velocity . The primary focus was on the mean values and standard deviations of the crest depths and wave periods at a given station and how these quantities varied with distance along the channel.

The wave properties were measured in a laboratory channel in which roll waves developed naturally from a uniform flow . The Froude number F (F = u_n/√gh_n, u_n = normal velocity , h_n = normal depth, g =acceleration of gravity) ranged from 3. 4 to 6. 0 for channel slopes S_o of . 05 and . 12 respectively . In the initial phase of their development the roll waves appeared as small amplitude waves with a continuous water surface profile . These small amplitude waves subsequently developed into large amplitude shock waves. Shock waves were found to overtake and combine with other shock waves with the result that the crest depth of the combined wave was larger than the crest depths before the overtake. Once roll waves began to develop, the mean value of the crest depths h_nmax increased with distance . Once the shock waves began to overtake, the mean wave period T_av increased approximately linearly with distance.

For a given Froude number and channel slope the observed quantities h^-_max/h_n , T' (T' = S_o T_av √g/h_n), and the standard deviations of h^-_max/h_n and T', could be expressed as unique functions of l/h_n (l = distance from beginning of channel) for the two-fold change in h_n occurring in the observed flows . A given value of h^-_max/h_n occurred at smaller values of l/h_n as the Froude number was increased. For a given value of h /hh^-_max/h_n the growth rate of δh^-_max/h^-_maxδl of the shock waves increased as the Froude number was increased.

A laboratory channel was also used to measure the wave properties of periodic permanent roll waves. For a given Froude number and channel slope the h^-_max/h_n vs. T' relation did not agree with a theory in which the weight of the shock front was neglected. After the theory was modified to include this weight, the observed values of h^-_max/h_n were within an average of 6.5 percent of the predicted values, and the maximum discrepancy was 13.5 percent.

For h^-_max/h_n sufficiently large (h^-_max/h_n > approximately 1.5) it was found that the h^-_max/h_n vs. T' relation for natural roll waves was practically identical to the h^-_max/h_n vs. T' relation for periodic permanent roll waves at the same Froude number and slope. As a result of this correspondence between periodic and natural roll waves, the growth rate δh^-_max/h^-_maxδl of shock waves was predicted to depend on the channel slope, and this slope dependence was observed in the experiments.

Imaging the earth with ambient noise and earthquakes

In this thesis, I develop the velocity and structure models for the Los Angeles Basin and Southern Peru. The ultimate goal is to better understand the geological processes involved in the basin and subduction zone dynamics. The results are obtained from seismic interferometry using ambient noise and receiver functions using earthquake- generated waves. Some unusual signals specific to the local structures are also studied. The main findings are summarized as follows:

(1) Los Angeles Basin

The shear wave velocities range from 0.5 to 3.0 km/s in the sediments, with lateral gradients at the Newport-Inglewood, Compton-Los Alamitos, and Whittier Faults. The basin is a maximum of 8 km deep along the profile, and the Moho rises to a depth of 17 km under the basin. The basin has a stretch factor of 2.6 in the center decreasing to 1.3 at the edges, and is in approximate isostatic equilibrium. This "high-density" (~1 km spacing) "short-duration" (~1.5 month) experiment may serve as a prototype experiment that will allow basins to be covered by this type of low-cost survey.

(2) Peruvian subduction zone

Two prominent mid-crust structures are revealed in the 70 km thick crust under the Central Andes: a low-velocity zone interpreted as partially molten rocks beneath the Western Cordillera – Altiplano Plateau, and the underthrusting Brazilian Shield beneath the Eastern Cordillera. The low-velocity zone is oblique to the present trench, and possibly indicates the location of the volcanic arcs formed during the steepening of the Oligocene flat slab beneath the Altiplano Plateau.

The Nazca slab changes from normal dipping (~25 degrees) subduction in the southeast to flat subduction in the northwest of the study area. In the flat subduction regime, the slab subducts to ~100 km depth and then remains flat for ~300 km distance before it resumes a normal dipping geometry. The flat part closely follows the topography of the continental Moho above, indicating a strong suction force between the slab and the overriding plate. A high-velocity mantle wedge exists above the western half of the flat slab, which indicates the lack of melting and thus explains the cessation of the volcanism above. The velocity turns to normal values before the slab steepens again, indicating possible resumption of dehydration and ecologitization.

(3) Some unusual signals

Strong higher-mode Rayleigh waves due to the basin structure are observed in the periods less than 5 s. The particle motions provide a good test for distinguishing between the fundamental and higher mode. The precursor and coda waves relative to the interstation Rayleigh waves are observed, and modeled with a strong scatterer located in the active volcanic area in Southern Peru. In contrast with the usual receiver function analysis, multiples are extensively involved in this thesis. In the LA Basin, a good image is only from PpPs multiples, while in Peru, PpPp multiples contribute significantly to the final results.