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.

Aqueous ring-opening metathesis polymerizations

Past workers in this group as well as in others have made considerable progress in the understanding and development of the ring-opening metathesis polymerization (ROMP) technique. Through these efforts, ROMP chemistry has become something of an organometallic success story. Extensive work was devoted to trying to identify the catalytically active species in classical reaction mixtures of early metal halides and alkyl aluminum compounds. Through this work, a mechanism involving the interconversion of metal carbenes and metallacyclobutanes was proposed. This preliminary work finally led to the isolation and characterization of stable metal carbene and metallacyclobutane complexes. As anticipated, these well-characterized complexes were shown to be active catalysts. In a select number of cases, these catalysts have been shown to catalyze the living polymerization of strained rings such as norbornene. The synthetic control offered by these living systems places them in a unique category of metal catalyzed reactions. To take full advantage of these new catalysts, two approaches should be explored. The first takes advantage of the unusual fact that all of the unsaturation present in the monomer is conserved in the polymer product. This makes ROMP techniques ideal for the synthesis of highly unsaturated, and fully conjugated polymers, which find uses in a variety of applications. This area is currently under intense investigation. The second aspect, which should lend itself to fruitful investigations, is expanding the utility of these catalysts through the living polymerization of monomers containing interesting functional groups. Polymer properties can be dramatically altered by the incorporation of functional groups. It is this latter aspect which will be addressed in this work.

After a general introduction to both the ring-opening metathesis reaction (Chapter 1) and the polymerization of fuctionalized monomers by transition metal catalysts (Chapter 2), the limits of the existing living ROMP catalysts with functionalized monomers are examined in Chapter 3. Because of the stringent limitations of these early metal catalysts, efforts were focused on catalysts based on ruthenium complexes. Although not living, and displaying unusually long induction periods, these catalysts show high promise for future investigations directed at the development of catalysts for the living polymerization of functionalized monomers. In an attempt to develop useful catalysts based on these ruthenium complexes, efforts to increase their initiation rates are presented in Chapter 4. This work eventually led to the discovery that these catalysts are highly active in aqueous solution, providing the opportunity to develop aqueous emulsion ROMP systems. Recycling the aqueous catalysts led to the discovery that the ruthenium complexes become more activated with use. Investigations of these recycled solutions uncovered new ruthenium-olefin complexes, which are implicated in the activation process. Although our original goal of developing living ROMP catalysts for the polymerization of fuctionalized monomers is yet to be realized, it is hoped that this work provides a foundation from which future investigations can be launched.

In the last chapter, the ionophoric properties of the poly(7-oxanobornene) materials is briefly discussed. Their limited use as acyclic host polymers led to investigations into the fabrication of ion-permeable membranes fashioned from these materials.

Cooperative and market-based solutions to pollution abatement problems

This work concerns itself with the possibility of solutions, both cooperative and market based, to pollution abatement problems. In particular, we are interested in pollutant emissions in Southern California and possible solutions to the abatement problems enumerated in the 1990 Clean Air Act. A tradable pollution permit program has been implemented to reduce emissions, creating property rights associated with various pollutants.

Before we discuss the performance of market-based solutions to LA's pollution woes, we consider the existence of cooperative solutions. In Chapter 2, we examine pollutant emissions as a trans boundary public bad. We show that for a class of environments in which pollution moves in a bi-directional, acyclic manner, there exists a sustainable coalition structure and associated levels of emissions. We do so via a new core concept, one more appropriate to modeling cooperative emissions agreements (and potential defection from them) than the standard definitions.

However, this leaves the question of implementing pollution abatement programs unanswered. While the existence of a cost-effective permit market equilibrium has long been understood, the implementation of such programs has been difficult. The design of Los Angeles' REgional CLean Air Incentives Market (RECLAIM) alleviated some of the implementation problems, and in part exacerbated them. For example, it created two overlapping cycles of permits and two zones of permits for different geographic regions. While these design features create a market that allows some measure of regulatory control, they establish a very difficult trading environment with the potential for inefficiency arising from the transactions costs enumerated above and the illiquidity induced by the myriad assets and relatively few participants in this market.

It was with these concerns in mind that the ACE market (Automated Credit Exchange) was designed. The ACE market utilizes an iterated combined-value call market (CV Market). Before discussing the performance of the RECLAIM program in general and the ACE mechanism in particular, we test experimentally whether a portfolio trading mechanism can overcome market illiquidity. Chapter 3 experimentally demonstrates the ability of a portfolio trading mechanism to overcome portfolio rebalancing problems, thereby inducing sufficient liquidity for markets to fully equilibrate.

With experimental evidence in hand, we consider the CV Market's performance in the real world. We find that as the allocation of permits reduces to the level of historical emissions, prices are increasing. As of April of this year, prices are roughly equal to the cost of the Best Available Control Technology (BACT). This took longer than expected, due both to tendencies to mis-report emissions under the old regime, and abatement technology advances encouraged by the program. Vve also find that the ACE market provides liquidity where needed to encourage long-term planning on behalf of polluting facilities.

Reaction of glucose catalyzed by framework and extraframework tin sites in zeolite beta

The isomerization of glucose into fructose is a large-scale reaction for the production of high-fructose corn syrup, and is now being considered as an intermediate step in the possible route of biomass conversion into fuels and chemicals. Recently, it has been shown that a hydrophobic, large pore, silica molecular sieve having the zeolite beta structure and containing framework Sn⁴⁺ (Sn-Beta) is able to isomerize glucose into fructose in aqueous media. Here, I have investigated how this catalyst converts glucose to fructose and show that it is analogous to that achieved with metalloenzymes. Specifically, glucose partitions into the molecular sieve in the pyranose form, ring opens to the acyclic form in the presence of the Lewis acid center (framework Sn⁴⁺), isomerizes into the acyclic form of fructose and finally ring closes to yield the furanose product. Akin to the metalloenzyme, the isomerization step proceeds by intramolecular hydride transfer from C2 to C1. Extraframework tin oxides located within hydrophobic channels of the molecular sieve that exclude liquid water can also isomerize glucose to fructose in aqueous media, but do so through a base-catalyzed proton abstraction mechanism. Extraframework tin oxide particles located at the external surface of the molecular sieve crystals or on amorphous silica supports are not active in aqueous media but are able to perform the isomerization in methanol by a base-catalyzed proton abstraction mechanism. Post-synthetic exchange of Na⁺ with Sn-Beta alters the glucose reaction pathway from the 1,2 intramolecular hydrogen shift (isomerization) to produce fructose towards the 1,2 intramolecular carbon shift (epimerization) that forms mannose. Na⁺ remains exchanged onto silanol groups during reaction in methanol solvent, leading to a near complete shift in selectivity towards glucose epimerization to mannose. In contrast, decationation occurs during reaction in aqueous solutions and gradually increases the reaction selectivity to isomerization at the expense of epimerization. Decationation and concomitant changes in selectivity can be eliminated by addition of NaCl to the aqueous reaction solution. Thus, framework tin sites with a proximal silanol group are the active sites for the 1, 2 intramolecular hydride shift in the isomerization of glucose to fructose, while these sites with Na-exchanged silanol group are the active sites for the 1, 2 intramolecular carbon shift in epimerization of glucose to mannose.

Selectivity, activity, and stability of ruthenium-carbene based olefin metathesis initiators

The olefin metathesis reaction has found many applications in polymer synthesis and more recently in organic synthesis. The use of single component late metal olefin metathesis catalysts has expanded the scope of the reaction to many new applications and has allowed for detailed study of the catalytic species.

The metathesis of terminal olefins of different steric bulk, different geometry as well as electronically different para-substituted styrenes was studied with the ruthenium based metathesis initiators, trans-(PCy₃)₂Cl₂Ru=CHR, of different carbene substituents. Increasing olefin bulk was found to slow the rate of reaction and trans internal olefins were found to be slower to react than cis internal olefins. The kinetic product of a11 reactions was found to be the alkylidene, rather than the methylidene, suggesting the intermediacy of a 2,4-metallacycle. The observed effects were used to explain the mechanism of ring opening cross metathesis and acyclic diene metathesis polymerization. No linear electronic effects were observed.

In studying the different carbene ligands, a series of ester-carbene complexes was synthesized. These complexes were found to be highly active for the metathesis of olefinic substrates, including acrylates and trisubstituted olefins. In addition, the estercarbene moiety is thermodynamically high in energy. As a result, these complexes react to ring-open cyclohexene by metathesis to alleviate the thermodynamic strain of the ester-carbene ligand. However, ester-carbene complexes were found to be thermolytically unstable in solution.

Thermolytic decomposition pathways were studied for several ruthenium-carbene based olefin metathesis catalysts. Substituted carbenes were found to decompose through bimolecular pathways while the unsubstituted carbene (the methylidene) was found to decompose unimolecularly. The stability of several derivatives of the bis-phosphine ruthenium based catalysts was studied for its implications to ring-closing metathesis. The reasons for the activity and stability of the different ruthenium-based catalysts is discussed.

The difference in catalyst activity and initiation is discussed for the bis-phosphine based and mixed N-heterocyclic carbene/phosphine based ruthenium olefin metathesis catalysts. The mixed ligand catalysts initiate far slower than the bis-phosphine catalysts but are far more metathesis active. A scheme is proposed to explain the difference in reactivity between the two types of catalysts.

Oxy anion-accelerated rearrangements

The alkali metal salts of 1,5-hexadien-3-ols undergo accelerated Cope rearrangements to the enolates of δ, ε-unsaturated carbonyl compounds. The generality of the rearrangement was investigated in numerous systems, particularly acyclic cases, and the effect of changes in substituents, counterions, solvents, and geometrical structures were noted and discussed. Applications of this methodology in synthesis included the synthesis of the insect pheromone frontalin, the preparation of selectively monoprotected 1,6-dicarbonyl compounds from 4-methoxy- and 4-phenylthio-1,5-hexadien-3-ols, and the construction of complex ring structures such as a D-homo-estratetraenone derivative.

Thermochemical estimates of the energetics of anionpromoted alkoxide fragmentations were made, and in all cases heterolytic cleavage was favored over hemolytic cleavage by 8.5-53 kcal/mol. The implication of these and other thermochemical estimates is that the anionic oxy-Cope rearrangement occurs via a concerted mechanism rather than a dissociation-recombination process. The concepts of anion-induced bond weakening were successfully applied to an accelerated [1,3]-shift of a dithiane fragment in a cyclohexenyl system. Trapping experiments demonstrated that > 85% of the [1,3]-shift occurred within a solvent cage. Attempts at promoting an intramolecular ene reaction using the potassium salts of 2,7-octadien-1-o1 and 2,8-nonadien-1-o1 were unsuccessful. A general review of anion-promoted bond reorganizations and anion substituent effects is also presented.

Strategies for the Stereoselective Synthesis of Carbon Quaternary Centers via Transition Metal-Catalyzed Alkylation of Enolate Compounds

Notwithstanding advances in modern chemical methods, the selective installation of sterically encumbered carbon stereocenters, in particular all-carbon quaternary centers, remains an unsolved problem in organic chemistry. The prevalence of all-carbon quaternary centers in biologically active natural products and pharmaceutical compounds provides a strong impetus to address current limitations in the state of the art of their generation. This thesis presents four related projects, all of which share in the goal of constructing highly-congested carbon centers in a stereoselective manner, and in the use of transition-metal catalyzed alkylation as a means to address that goal.

The first research described is an extension of allylic alkylation methodology previously developed in the Stoltz group to small, strained rings. This research constitutes the first transition metal-catalyzed enantioselective α-alkylation of cyclobutanones. Under Pd-catalysis, this chemistry affords all–carbon α-quaternary cyclobutanones in good to excellent yields and enantioselectivities.

Next is described our development of a (trimethylsilyl)ethyl β-ketoester class of enolate precursors, and their application in palladium–catalyzed asymmetric allylic alkylation to yield a variety of α-quaternary ketones and lactams. Independent coupling partner synthesis engenders enhanced allyl substrate scope relative to allyl β-ketoester substrates; highly functionalized α-quaternary ketones generated by the union of our fluoride-triggered β-ketoesters and sensitive allylic alkylation coupling partners serve to demonstrate the utility of this method for complex fragment coupling.

Lastly, our development of an Ir-catalyzed asymmetric allylic alkylation of cyclic β-ketoesters to afford highly congested, vicinal stereocenters comprised of tertiary and all-carbon quaternary centers with outstanding regio-, diastereo-, and enantiocontrol is detailed. Implementation of a subsequent Pd-catalyzed alkylation affords dialkylated products with pinpoint stereochemical control of both chiral centers. The chemistry is then extended to include acyclic β-ketoesters and similar levels of selective and functional group tolerance are observed. Critical to the successful development of this method was the employment of iridium catalysis in concert with N-aryl-phosphoramidite ligands.

On the set of eigenvalues of a class of equimodular matrices

The structure of the set ϐ(A) of all eigenvalues of all complex matrices (elementwise) equimodular with a given n x n non-negative matrix A is studied. The problem was suggested by O. Taussky and some aspects have been studied by R. S. Varga and B.W. Levinger.

If every matrix equimodular with A is non-singular, then A is called regular. A new proof of the P. Camion-A.J. Hoffman characterization of regular matrices is given.

The set ϐ(A) consists of m ≤ n closed annuli centered at the origin. Each gap, ɤ, in this set can be associated with a class of regular matrices with a (unique) permutation, π(ɤ). The association depends on both the combinatorial structure of A and the size of the a_ii. Let A be associated with the set of r permutations, π₁, π₂,…, π_r, where each gap in ϐ(A) is associated with one of the π_k. Then r ≤ n, even when the complement of ϐ(A) has n+1 components. Further, if π(ɤ) is the identity, the real boundary points of ɤ are eigenvalues of real matrices equimodular with A. In particular, if A is essentially diagonally dominant, every real boundary point of ϐ(A) is an eigenvalues of a real matrix equimodular with A.

Several conjectures based on these results are made which if verified would constitute an extension of the Perron-Frobenius Theorem, and an algebraic method is introduced which unites the study of regular matrices with that of ϐ(A).

Normal structures and automorphism groups of t-designs

Combinatorial configurations known as t-designs are studied. These are pairs ˂B, ∏˃, where each element of B is a k-subset of ∏, and each t-design occurs in exactly λ elements of B, for some fixed integers k and λ. A theory of internal structure of t-designs is developed, and it is shown that any t-design can be decomposed in a natural fashion into a sequence of “simple” subdesigns. The theory is quite similar to the analysis of a group with respect to its normal subgroups, quotient groups, and homomorphisms. The analogous concepts of normal subdesigns, quotient designs, and design homomorphisms are all defined and used.

This structure theory is then applied to the class of t-designs whose automorphism groups are transitive on sets of t points. It is shown that if G is a permutation group transitive on sets of t letters and ф is any set of letters, then images of ф under G form a t-design whose parameters may be calculated from the group G. Such groups are discussed, especially for the case t = 2, and the normal structure of such designs is considered. Theorem 2.2.12 gives necessary and sufficient conditions for a t-design to be simple, purely in terms of the automorphism group of the design. Some constructions are given.

Finally, 2-designs with k = 3 and λ = 2 are considered in detail. These designs are first considered in general, with examples illustrating some of the configurations which can arise. Then an attempt is made to classify all such designs with an automorphism group transitive on pairs of points. Many cases are eliminated of reduced to combinations of Steiner triple systems. In the remaining cases, the simple designs are determined to consist of one infinite class and one exceptional case.