Algebraic Techniques in Coding Theory: Entropy Vectors, Frames, and Constrained Coding

The study of codes, classically motivated by the need to communicate information reliably in the presence of error, has found new life in fields as diverse as network communication, distributed storage of data, and even has connections to the design of linear measurements used in compressive sensing. But in all contexts, a code typically involves exploiting the algebraic or geometric structure underlying an application. In this thesis, we examine several problems in coding theory, and try to gain some insight into the algebraic structure behind them.

The first is the study of the entropy region - the space of all possible vectors of joint entropies which can arise from a set of discrete random variables. Understanding this region is essentially the key to optimizing network codes for a given network. To this end, we employ a group-theoretic method of constructing random variables producing so-called "group-characterizable" entropy vectors, which are capable of approximating any point in the entropy region. We show how small groups can be used to produce entropy vectors which violate the Ingleton inequality, a fundamental bound on entropy vectors arising from the random variables involved in linear network codes. We discuss the suitability of these groups to design codes for networks which could potentially outperform linear coding.

The second topic we discuss is the design of frames with low coherence, closely related to finding spherical codes in which the codewords are unit vectors spaced out around the unit sphere so as to minimize the magnitudes of their mutual inner products. We show how to build frames by selecting a cleverly chosen set of representations of a finite group to produce a "group code" as described by Slepian decades ago. We go on to reinterpret our method as selecting a subset of rows of a group Fourier matrix, allowing us to study and bound our frames' coherences using character theory. We discuss the usefulness of our frames in sparse signal recovery using linear measurements.

The final problem we investigate is that of coding with constraints, most recently motivated by the demand for ways to encode large amounts of data using error-correcting codes so that any small loss can be recovered from a small set of surviving data. Most often, this involves using a systematic linear error-correcting code in which each parity symbol is constrained to be a function of some subset of the message symbols. We derive bounds on the minimum distance of such a code based on its constraints, and characterize when these bounds can be achieved using subcodes of Reed-Solomon codes.

Electrical and optical interconnects for high-performance computing

Technology scaling has enabled drastic growth in the computational and storage capacity of integrated circuits (ICs). This constant growth drives an increasing demand for high-bandwidth communication between and within ICs. In this dissertation we focus on low-power solutions that address this demand. We divide communication links into three subcategories depending on the communication distance. Each category has a different set of challenges and requirements and is affected by CMOS technology scaling in a different manner. We start with short-range chip-to-chip links for board-level communication. Next we will discuss board-to-board links, which demand a longer communication range. Finally on-chip links with communication ranges of a few millimeters are discussed.

Electrical signaling is a natural choice for chip-to-chip communication due to efficient integration and low cost. IO data rates have increased to the point where electrical signaling is now limited by the channel bandwidth. In order to achieve multi-Gb/s data rates, complex designs that equalize the channel are necessary. In addition, a high level of parallelism is central to sustaining bandwidth growth. Decision feedback equalization (DFE) is one of the most commonly employed techniques to overcome the limited bandwidth problem of the electrical channels. A linear and low-power summer is the central block of a DFE. Conventional approaches employ current-mode techniques to implement the summer, which require high power consumption. In order to achieve low-power operation we propose performing the summation in the charge domain. This approach enables a low-power and compact realization of the DFE as well as crosstalk cancellation. A prototype receiver was fabricated in 45nm SOI CMOS to validate the functionality of the proposed technique and was tested over channels with different levels of loss and coupling. Measurement results show that the receiver can equalize channels with maximum 21dB loss while consuming about 7.5mW from a 1.2V supply. We also introduce a compact, low-power transmitter employing passive equalization. The efficacy of the proposed technique is demonstrated through implementation of a prototype in 65nm CMOS. The design achieves up to 20Gb/s data rate while consuming less than 10mW.

An alternative to electrical signaling is to employ optical signaling for chip-to-chip interconnections, which offers low channel loss and cross-talk while providing high communication bandwidth. In this work we demonstrate the possibility of building compact and low-power optical receivers. A novel RC front-end is proposed that combines dynamic offset modulation and double-sampling techniques to eliminate the need for a short time constant at the input of the receiver. Unlike conventional designs, this receiver does not require a high-gain stage that runs at the data rate, making it suitable for low-power implementations. In addition, it allows time-division multiplexing to support very high data rates. A prototype was implemented in 65nm CMOS and achieved up to 24Gb/s with less than 0.4pJ/b power efficiency per channel. As the proposed design mainly employs digital blocks, it benefits greatly from technology scaling in terms of power and area saving.

As the technology scales, the number of transistors on the chip grows. This necessitates a corresponding increase in the bandwidth of the on-chip wires. In this dissertation, we take a close look at wire scaling and investigate its effect on wire performance metrics. We explore a novel on-chip communication link based on a double-sampling architecture and dynamic offset modulation technique that enables low power consumption and high data rates while achieving high bandwidth density in 28nm CMOS technology. The functionality of the link is demonstrated using different length minimum-pitch on-chip wires. Measurement results show that the link achieves up to 20Gb/s of data rate (12.5Gb/s/$\mu$m) with better than 136fJ/b of power efficiency.

Effects of particle size ratio on single particle motion in colloidal dispersions

The motion of a single Brownian particle of arbitrary size through a dilute colloidal dispersion of neutrally buoyant bath spheres of another characteristic size in a Newtonian solvent is examined in two contexts. First, the particle in question, the probe particle, is subject to a constant applied external force drawing it through the suspension as a simple model for active and nonlinear microrheology. The strength of the applied external force, normalized by the restoring forces of Brownian motion, is the Péclet number, Pe. This dimensionless quantity describes how strongly the probe is upsetting the equilibrium distribution of the bath particles. The mean motion and fluctuations in the probe position are related to interpreted quantities of an effective viscosity of the suspension. These interpreted quantities are calculated to first order in the volume fraction of bath particles and are intimately tied to the spatial distribution, or microstructure, of bath particles relative to the probe. For weak Pe, the disturbance to the equilibrium microstructure is dipolar in nature, with accumulation and depletion regions on the front and rear faces of the probe, respectively. With increasing applied force, the accumulation region compresses to form a thin boundary layer whose thickness scales with the inverse of Pe. The depletion region lengthens to form a trailing wake. The magnitude of the microstructural disturbance is found to grow with increasing bath particle size -- small bath particles in the solvent resemble a continuum with effective microviscosity given by Einstein's viscosity correction for a dilute dispersion of spheres. Large bath particles readily advect toward the minimum approach distance possible between the probe and bath particle, and the probe and bath particle pair rotating as a doublet is the primary mechanism by which the probe particle is able to move past; this is a process that slows the motion of the probe by a factor of the size ratio. The intrinsic microviscosity is found to force thin at low Péclet number due to decreasing contributions from Brownian motion, and force thicken at high Péclet number due to the increasing influence of the configuration-averaged reduction in the probe's hydrodynamic self mobility. Nonmonotonicity at finite sizes is evident in the limiting high-Pe intrinsic microviscosity plateau as a function of bath-to-probe particle size ratio. The intrinsic microviscosity is found to grow with the size ratio for very small probes even at large-but-finite Péclet numbers. However, even a small repulsive interparticle potential, that excludes lubrication interactions, can reduce this intrinsic microviscosity back to an order one quantity. The results of this active microrheology study are compared to previous theoretical studies of falling-ball and towed-ball rheometry and sedimentation and diffusion in polydisperse suspensions, and the singular limit of full hydrodynamic interactions is noted.

Second, the probe particle in question is no longer subject to a constant applied external force. Rather, the particle is considered to be a catalytically-active motor, consuming the bath reactant particles on its reactive face while passively colliding with reactant particles on its inert face. By creating an asymmetric distribution of reactant about its surface, the motor is able to diffusiophoretically propel itself with some mean velocity. The effects of finite size of the solute are examined on the leading order diffusive microstructure of reactant about the motor. Brownian and interparticle contributions to the motor velocity are computed for several interparticle interaction potential lengths and finite reactant-to-motor particle size ratios, with the dimensionless motor velocity increasing with decreasing motor size. A discussion on Brownian rotation frames the context in which these results could be applicable, and future directions are proposed which properly incorporate reactant advection at high motor velocities.

Preparation and characterization of an intramolecular electron transfer in a pentaammineruthenium derivative of Candida krisei cytochrome c

A semisynthetic binuclear metalloprotein has been prepared by appending the pentaammineruthenium moiety to histidine 39 of the cytochrome c from the yeast Candida krusei. The site of ruthenium binding was identified by peptide mapping. Spectroscopic and electrochemical properties of the derivative indicate the protein conformation is unperturbed by the modification. A preliminary (minimum) rate constant of 170s^(-1) has been determined for the intramolecular electron transfer from ruthenium(II) to iron(III), which occurs over a distance of at least 13Å (barring major conformational changes). Electrochemical studies indicate that this reaction should proceed with a driving force of ~170mV. The rate constant is an order of magnitude faster than that observed in horse heart cytochrome c for intramolecular electron transfer from pentaammineruthenium(II)(histidine 33) to iron(III) (over a similar distance, and with a similar driving force), suggesting a medium or orientation effect makes the Candida intramolecular electron transfer more favorable.

The theory of long distance electron transfer reactions

The rate of electron transport between distant sites was studied. The rate depends crucially on the chemical details of the donor, acceptor, and surrounding medium. These reactions involve electron tunneling through the intervening medium and are, therefore, profoundly influenced by the geometry and energetics of the intervening molecules. The dependence of rate on distance was considered for several rigid donor-acceptor "linkers" of experimental importance. Interpretation of existing experiments and predictions for new experiments were made.

The electronic and nuclear motion in molecules is correlated. A Born-Oppenheimer separation is usually employed in quantum chemistry to separate this motion. Long distance electron transfer rate calculations require the total donor wave function when the electron is very far from its binding nuclei. The Born-Oppenheimer wave functions at large electronic distance are shown to be qualitatively wrong. A model which correctly treats the coupling was proposed. The distance and energy dependence of the electron transfer rate was determined for such a model.

Influence of composition on the structure, electric and magnetic properties of Pd-Mn-P and Pd-Co-P amorphous alloys

The influence of composition on the structure and on the electric and magnetic properties of amorphous Pd-Mn-P and Pd-Co-P prepared by rapid quenching techniques were investigated in terms of (1) the 3d band filling of the first transition metal group, (2) the phosphorus concentration effect which acts as an electron donor and (3) the transition metal concentration.

The structure is essentially characterized by a set of polyhedra subunits essentially inverse to the packing of hard spheres in real space. Examination of computer generated distribution functions using Monte Carlo random statistical distribution of these polyhedra entities demonstrated tile reproducibility of the experimentally calculated atomic distribution function. As a result, several possible "structural parameters" are proposed such as: the number of nearest neighbors, the metal-to-metal distance, the degree of short-range order and the affinity between metal-metal and metal-metalloid. It is shown that the degree of disorder increases from Ni to Mn. Similar behavior is observed with increase in the phosphorus concentration.

The magnetic properties of Pd-Co-P alloys show that they are ferromagnetic with a Curie temperature between 272 and 399°K as the cobalt concentration increases from 15 to 50 at.%. Below 20 at.% Co the short-range exchange interactions which produce the ferromagnetism are unable to establish a long-range magnetic order and a peak in the magnetization shows up at the lowest temperature range . The electric resistivity measurements were performed from liquid helium temperatures up to the vicinity of the melting point (900°K). The thermomagnetic analysis was carried out under an applied field of 6.0 kOe. The electrical resistivity of Pd-Co-P shows the coexistence of a Kondo-like minimum with ferromagnetism. The minimum becomes less important as the transition metal concentration increases and the coefficients of ℓn T and T^2 become smaller and strongly temperature dependent. The negative magnetoresistivity is a strong indication of the existence of localized moment.

The temperature coefficient of resistivity which is positive for Pd- Fe-P, Pd-Ni-P, and Pd-Co-P becomes negative for Pd-Mn-P. It is possible to account for the negative temperature dependence by the localized spin fluctuation model and the high density of states at the Fermi energy which becomes maximum between Mn and Cr. The magnetization curves for Pd-Mn-P are typical of those resulting from the interplay of different exchange forces. The established relationship between susceptibility and resistivity confirms the localized spin fluctuation model. The magnetoresistivity of Pd-Mn-P could be interpreted in tenns of a short-range magnetic ordering that could arise from the Rudennan-Kittel type interactions.

Structure and properties of an amorphous ferromagnetic alloy

The structure and the electrical and magnetic properties of an amorphous alloy containing approximately 80 at .% iron, 13 at.% phos phorus and 7 at.% carbon (Fe_(80)Fe_(13)C_7) obtained by rapid quenching from the liquid state have been studied. Transmission electron diffraction data confirm the amorphous nature of this alloy. An analysis of the radial distribution function obtained from X-ray diffraction data indicates that the number of nearest neighbors is approximately seven, at a distance of 2.6A. The structure of the alloy can be related to that of silicate glasses and is based on a random arrangement of trigonal prisms of Fe_2P and Fe_3C types in which the iron atoms have an average ligancy of seven. Electrical resistance measurements show that the alloys are metallic. A minimum in the electrical resistivity vs. temperature curve is observed between 10° K to 50° K depending on the specimen, and the temperature at which the minimum occurs is related to the degree of local ordering. The Fe-P-C amorphous alloys are ferromagnetic. The Curie temperature measured by the induction method and by Mossbauer spectroscopy is 315° C. The field dependence of the magneto-resistance at temperatures from liquid helium to room temperature is similar to that found in crystalline iron. The ordinary Hall coefficient is approximately 10^(-11) volt-cm/amp-G. The spontaneous Hall coefficient is about 0.6 x 10^(-9) volt-cm/amp-G and is practically independent of temperature from liquid helium temperature up to 300° c.

Regional variations in upper mantle structure beneath North America

Several types of seismological data, including surface wave group and phase velocities, travel times from large explosions, and teleseismic travel time anomalies, have indicated that there are significant regional variations in the upper few hundred kilometers of the mantle beneath continental areas. Body wave travel times and amplitudes from large chemical and nuclear explosions are used in this study to delineate the details of these variations beneath North America.

As a preliminary step in this study, theoretical P wave travel times, apparent velocities, and amplitudes have been calculated for a number of proposed upper mantle models, those of Gutenberg, Jeffreys, Lehman, and Lukk and Nersesov. These quantities have been calculated for both P and S waves for model CIT11GB, which is derived from surface wave dispersion data. First arrival times for all the models except that of Lukk and Nersesov are in close agreement, but the travel time curves for later arrivals are both qualitatively and quantitatively very different. For model CIT11GB, there are two large, overlapping regions of triplication of the travel time curve, produced by regions of rapid velocity increase near depths of 400 and 600 km. Throughout the distance range from 10 to 40 degrees, the later arrivals produced by these discontinuities have larger amplitudes than the first arrivals. The amplitudes of body waves, in fact, are extremely sensitive to small variations in the velocity structure, and provide a powerful tool for studying structural details.

Most of eastern North America, including the Canadian Shield has a Pn velocity of about 8.1 km/sec, with a nearly abrupt increase in compressional velocity by ~ 0.3 km/sec near at a depth varying regionally between 60 and 90 km. Variations in the structure of this part of the mantle are significant even within the Canadian Shield. The low-velocity zone is a minor feature in eastern North America and is subject to pronounced regional variations. It is 30 to 50 km thick, and occurs somewhere in the depth range from 80 to 160 km. The velocity decrease is less than 0.2 km/sec.

Consideration of the absolute amplitudes indicates that the attenuation due to anelasticity is negligible for 2 hz waves in the upper 200 km along the southeastern and southwestern margins of the Canadian Shield. For compressional waves the average Q for this region is > 3000. The amplitudes also indicate that the velocity gradient is at least 2 x 10^-3 both above and below the low-velocity zone, implying that the temperature gradient is < 4.8°C/km if the regions are chemically homogeneous.

In western North America, the low-velocity zone is a pronounced feature, extending to the base of the crust and having minimum velocities of 7.7 to 7.8 km/sec. Beneath the Colorado Plateau and Southern Rocky Mountains provinces, there is a rapid velocity increase of about 0.3 km/sec, similar to that observed in eastern North America, but near a depth of 100 km.

Complicated travel time curves observed on profiles with stations in both eastern and western North America can be explained in detail by a model taking into account the lateral variations in the structure of the low-velocity zone. These variations involve primarily the velocity within the zone and the depth to the top of the zone; the depth to the bottom is, for both regions, between 140 and 160 km.

The depth to the transition zone near 400 km also varies regionally, by about 30-40 km. These differences imply variations of 250 °C in the temperature or 6 % in the iron content of the mantle, if the phase transformation of olivine to the spinel structure is assumed responsible. The structural variations at this depth are not correlated with those at shallower depths, and follow no obvious simple pattern.

The computer programs used in this study are described in the Appendices. The program TTINV (Appendix IV) fits spherically symmetric earth models to observed travel time data. The method, described in Appendix III, resembles conventional least-square fitting, using partial derivatives of the travel time with respect to the model parameters to perturb an initial model. The usual ill-conditioned nature of least-squares techniques is avoided by a technique which minimizes both the travel time residuals and the model perturbations.

Spherically symmetric earth models, however, have been found inadequate to explain most of the observed travel times in this study. TVT4, a computer program that performs ray theory calculations for a laterally inhomogeneous earth model, is described in Appendix II. Appendix I gives a derivation of seismic ray theory for an arbitrarily inhomogeneous earth model.

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).

Minimum drag profiles in infinite cavity flows

The problem considered is that of minimizing the drag of a symmetric plate in infinite cavity flow under the constraints of fixed arclength and fixed chord. The flow is assumed to be steady, irrotational, and incompressible. The effects of gravity and viscosity are ignored.

Using complex variables, expressions for the drag, arclength, and chord, are derived in terms of two hodograph variables, Γ (the logarithm of the speed) and β (the flow angle), and two real parameters, a magnification factor and a parameter which determines how much of the plate is a free-streamline.

Two methods are employed for optimization:

(1) The parameter method. Γ and β are expanded in finite orthogonal series of N terms. Optimization is performed with respect to the N coefficients in these series and the magnification and free-streamline parameters. This method is carried out for the case N = 1 and minimum drag profiles and drag coefficients are found for all values of the ratio of arclength to chord.

(2) The variational method. A variational calculus method for minimizing integral functionals of a function and its finite Hilbert transform is introduced, This method is applied to functionals of quadratic form and a necessary condition for the existence of a minimum solution is derived. The variational method is applied to the minimum drag problem and a nonlinear integral equation is derived but not solved.

The geochronology of the plutonic and metamorphic rocks of New Zealand

Extensive Rubidium-Strontium age determinations on both mineral and total rock samples of the crystalline rocks of New Zealand, which almost solely crop out in the South Island, indicate widespread plutonic and metamorphic activity occurred during two periods, one about 100-118 million years ago and the other about 340-370 million years ago. The former results date the Rangitata Orogeny as Cretaceous. They associate extensive plutonic activity with this orogeny which uplifted and metamorphosed the rocks of the New Zealand Geosyncline, although no field association between the metamorphosed geosynclinal rocks and plutonic rocks has been found. The Cretaceous plutonic rocks occur to the west in the Foreland Province in Fiordland, Nelson, and Westland, geographically separated from the Geosynclinal Province. Because of this synchronous timing of plutonic and high pressure metamorphic activity in spatially separated belts, the Rangitata Orogeny in New Zealand is very similar to late Mesozoic orogenic activity in many other areas of the circum-Pacific margin (Miyashiro, 1961).

The 340-370 million year rocks, both plutonic and metamorphic, have been found only in that part of the Foreland Province north of the Alpine Fault. There, they are concentrated along the west coast over a distance of 500 km, and appear scattered inland from the coast. Probably this activity marks the outstanding Phanerozoic stratigraphic gap in New Zealand which occurred after the Lower Devonian.

A few crystalline rocks in the Foreland Province north of the Alpine Fault with measured ages intermediate between 340 and 120 million years have been found. Of these, those with more than one mineral examined give discordant results. All of these rocks are tentatively regarded as 340-370 million year old rocks that have been variously disturbed during the Rangitata Orogeny, 100-120 million years ago.

In addition to these two periods, plutonic activity, dominantly basic and ultrabasic, but including the development of some rocks of intermediate and acidic composition, occurred along the margin of the Geosynclinal Province at its border with the Foreland Province during Permian times about 245 million years ago, and this activity possibly extended into the Mesozoic.

Evidence from rubidium-strontium analyses of minerals and a total rock, and from uranium, thorium, and lead analyses of uniform euhedral zircons from a meta-igneous portion of the Charleston Gneiss, previously mapped as Precambrian, indicate that this rock is a 350-370 million year old plutonic rock metamorphosed 100 million yea rs ago during the Rangitata Orogeny. No crystalline rocks with primary Precambrian ages have been found in New Zealand. However, Pb²⁰⁷/Pb₂₀₆ ages of 1360 million years and 1370 million years have been determined for rounded detrital zircons separated from each of two hornfels samples of one of New Zealand's olde st sedimentary units, the Greenland Series. These two samples were metamorphosed 345- 370 million years ago. They occur along the west coast, north of the Alpine Fault, at Waitaha River and Moeraki River, separated by 135 km. The Precambrian measured ages are most likely minimum ages for the oldest source area which provided the detrital zircons because the uranium, thorium and lead data are highly discordant. These results are of fundamental importance for the tectonic picture of the Southwest Pacific margin and demonstrate the existence of relatively old continental crust of some lateral extent in the neighborhood of New Zealand.