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.

Control of wettability of carbon nanotube array by reversible dry oxidation for superhydrophobic coating and supercapacitor applications

In this thesis, dry chemical modification methods involving UV/ozone, oxygen plasma, and vacuum annealing treatments are explored to precisely control the wettability of CNT arrays. By varying the exposure time of these treatments the surface concentration of oxygenated groups adsorbed on the CNT arrays can be controlled. CNT arrays with very low amount of oxygenated groups exhibit a superhydrophobic behavior. In addition to their extremely high static contact angle, they cannot be dispersed in DI water and their impedance in aqueous electrolytes is extremely high. These arrays have an extreme water repellency capability such that a water droplet will bounce off of their surface upon impact and a thin film of air is formed on their surface as they are immersed in a deep pool of water. In contrast, CNT arrays with very high surface concentration of oxygenated functional groups exhibit an extreme hydrophilic behavior. In addition to their extremely low static contact angle, they can be dispersed easily in DI water and their impedance in aqueous electrolytes is tremendously low. Since the bulk structure of the CNT arrays are preserved during the UV/ozone, oxygen plasma, and vacuum annealing treatments, all CNT arrays can be repeatedly switched between superhydrophilic and superhydrophobic, as long as their O/C ratio is kept below 18%.

The effect of oxidation using UV/ozone and oxygen plasma treatments is highly reversible as long as the O/C ratio of the CNT arrays is kept below 18%. At O/C ratios higher than 18%, the effect of oxidation is no longer reversible. This irreversible oxidation is caused by irreversible changes to the CNT atomic structure during the oxidation process. During the oxidation process, CNT arrays undergo three different processes. For CNT arrays with O/C ratios lower than 40%, the oxidation process results in the functionalization of CNT outer walls by oxygenated groups. Although this functionalization process introduces defects, vacancies and micropores opening, the graphitic structure of the CNT is still largely intact. For CNT arrays with O/C ratios between 40% and 45%, the oxidation process results in the etching of CNT outer walls. This etching process introduces large scale defects and holes that can be obviously seen under TEM at high magnification. Most of these holes are found to be several layers deep and, in some cases, a large portion of the CNT side walls are cut open. For CNT arrays with O/C ratios higher than 45%, the oxidation process results in the exfoliation of the CNT walls and amorphization of the remaining CNT structure. This amorphization process can be implied from the disappearance of C-C sp2 peak in the XPS spectra associated with the pi-bond network.

The impact behavior of water droplet impinging on superhydrophobic CNT arrays in a low viscosity regime is investigated for the first time. Here, the experimental data are presented in the form of several important impact behavior characteristics including critical Weber number, volume ratio, restitution coefficient, and maximum spreading diameter. As observed experimentally, three different impact regimes are identified while another impact regime is proposed. These regimes are partitioned by three critical Weber numbers, two of which are experimentally observed. The volume ratio between the primary and the secondary droplets is found to decrease with the increase of Weber number in all impact regimes other than the first one. In the first impact regime, this is found to be independent of Weber number since the droplet remains intact during and subsequent to the impingement. Experimental data show that the coefficient of restitution decreases with the increase of Weber number in all impact regimes. The rate of decrease of the coefficient of restitution in the high Weber number regime is found to be higher than that in the low and moderate Weber number. Experimental data also show that the maximum spreading factor increases with the increase of Weber number in all impact regimes. The rate of increase of the maximum spreading factor in the high Weber number regime is found to be higher than that in the low and moderate Weber number. Phenomenological approximations and interpretations of the experimental data, as well as brief comparisons to the previously proposed scaling laws, are shown here.

Dry oxidation methods are used for the first time to characterize the influence of oxidation on the capacitive behavior of CNT array EDLCs. The capacitive behavior of CNT array EDLCs can be tailored by varying their oxygen content, represented by their O/C ratio. The specific capacitance of these CNT arrays increases with the increase of their oxygen content in both KOH and Et4NBF4/PC electrolytes. As a result, their gravimetric energy density increases with the increase of their oxygen content. However, their gravimetric power density decreases with the increase of their oxygen content. The optimally oxidized CNT arrays are able to withstand more than 35,000 charge/discharge cycles in Et4NBF4/PC at a current density of 5 A/g while only losing 10% of their original capacitance.

Studies on photoblastic germination in lettuce seed

It was shown, with the aid of osmotic inhibition of germination, that the action of the far-red-absorbing form of phytochrome (Pf) in promoting germination can be completed even if the seed is held under conditions where germination is not possible. An effect of the continuing action of Pf beyond the point of complete germination promotion was demonstrated by enhancement of germination rate after removal of the osmotically active solute.

Previous reports that the rate of growth in water of seeds freed from the expansion-restricting endosperm is independent of the state of phytochrome were confirmed. However, a marked, phytochrome-mediated enhancement of the growth potential of such seeds was demonstrated through restricting water uptake by incubation in an osmoticum.

An experimental system, utilizing the appearance of a geotropic curvature in the radicle of the excised axial portion of the seed, was developed for more detailed studies of the phytochrome-enhanced growth potential. It was possible to demonstrate the light effect in water as well as in osmotica; this apparently is not possible with de-endospermed entire seeds. As in intact seeds, the effect of the continuing action of Pf is to enhance the rate of the response. Secretion of a chemical inhibitor of growth by the endosperm as a possible mechanism of induction of light sensitivity has been ruled out.

The phytochrome-dependent rate of appearance of geotropic curvature in osmotica is paralleled in time by a similar dependence of the rate of early extension growth of the embryonic axis. Only the first small increment of growth is a differentially responsive to red (R) and far-red (F); the rate of later increase in length is independent of the light regime.

It was shown that the high concentrations of gibberellic acid required for germination promotion in the intact seed are due at least in part to a diffusion barrier in the endosperm, and that the occasional reports in the literature of the ineffectiveness of kinetin are probably due to the same phenomenon. It was shown that gibberellin, like red light, enhances the growth potential of the axis, but kinetin does not. The difference in rates of response obtained after R-irradiation or gibberellin treatment, together with other results reported in the literature, strongly suggests that gibberellic acid and red light promote germination by different means. The idea that kinetin promotes germination by yet another mechanism, probably operating in the cotyledons, was supported through two different experimental approaches.

The phenomenon of temperature-dependent dark germination was examined in detail, using a wide range of both temperatures and incubation times. With the aid of the half-seed system, it was demonstrated that the promotive effect of low temperature on germination could not be due to a low optimum temperature for early growth of the radicle, since the rate of that process increased with increasing temperature, up to the highest temperature used.

It was shown that phytochrome does not function at high temperatures. This fact is of considerable importance in interpreting the phenomenon of thermodormancy, since in the literature only a small part of the effect of high temperature has been ascribed to an effect on phytochrome, and at that, only to an acceleration of dark reversion of Pf to the red-absorbing form of phytochrome (Pr). Partial denaturation of phytochrome may also make some contribution.

It was shown that the germination-promoting effect of low temperature depends on the presence of Pf, and concluded that low temperatures act by delaying or preventing transformation of Pf. Support for the assumption that Pf, not Pr, is the active form of phytochrome in lettuce seeds was drawn from the same evidence.

Attempts to stimulate germination by repeated irradiation with F over relatively prolonged incubation times resulted in failure, as have similar attempts reported in the literature. However, an enhancement of growth potential in the half-seed system by the maintenance of a small amount of Pf over long periods at ordinary temperatures by repeated irradiation with F was demonstrated.

It was observed that cold storage of the dry seed prevents or delays loss of dark dormancy during post-harvest storage. No change in the response of the half-seed in osmoticum to R and F was observed in seeds that has lost dark dormancy; that is, no internal change took place to measurably increase the growth potential of the embryonic axis. This suggests that the endosperm is the seat of changes responsible for after-ripening of photoblastic lettuce seed.