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.

Optimization and Control of Power Flow in Distribution Networks

Climate change is arguably the most critical issue facing our generation and the next. As we move towards a sustainable future, the grid is rapidly evolving with the integration of more and more renewable energy resources and the emergence of electric vehicles. In particular, large scale adoption of residential and commercial solar photovoltaics (PV) plants is completely changing the traditional slowly-varying unidirectional power flow nature of distribution systems. High share of intermittent renewables pose several technical challenges, including voltage and frequency control. But along with these challenges, renewable generators also bring with them millions of new DC-AC inverter controllers each year. These fast power electronic devices can provide an unprecedented opportunity to increase energy efficiency and improve power quality, if combined with well-designed inverter control algorithms. The main goal of this dissertation is to develop scalable power flow optimization and control methods that achieve system-wide efficiency, reliability, and robustness for power distribution networks of future with high penetration of distributed inverter-based renewable generators.

Proposed solutions to power flow control problems in the literature range from fully centralized to fully local ones. In this thesis, we will focus on the two ends of this spectrum. In the first half of this thesis (chapters 2 and 3), we seek optimal solutions to voltage control problems provided a centralized architecture with complete information. These solutions are particularly important for better understanding the overall system behavior and can serve as a benchmark to compare the performance of other control methods against. To this end, we first propose a branch flow model (BFM) for the analysis and optimization of radial and meshed networks. This model leads to a new approach to solve optimal power flow (OPF) problems using a two step relaxation procedure, which has proven to be both reliable and computationally efficient in dealing with the non-convexity of power flow equations in radial and weakly-meshed distribution networks. We will then apply the results to fast time- scale inverter var control problem and evaluate the performance on real-world circuits in Southern California Edison’s service territory.

The second half (chapters 4 and 5), however, is dedicated to study local control approaches, as they are the only options available for immediate implementation on today’s distribution networks that lack sufficient monitoring and communication infrastructure. In particular, we will follow a reverse and forward engineering approach to study the recently proposed piecewise linear volt/var control curves. It is the aim of this dissertation to tackle some key problems in these two areas and contribute by providing rigorous theoretical basis for future work.

High frequency wave propagation in the earth: theory and observation

The wave-theoretical analysis of acoustic and elastic waves refracted by a spherical boundary across which both velocity and density increase abruptly and thence either increase or decrease continuously with depth is formulated in terms of the general problem of waves generated at a steady point source and scattered by a radially heterogeneous spherical body. A displacement potential representation is used for the elastic problem that results in high frequency decoupling of P-SV motion in a spherically symmetric, radially heterogeneous medium. Through the application of an earth-flattening transformation on the radial solution and the Watson transform on the sum over eigenfunctions, the solution to the spherical problem for high frequencies is expressed as a Weyl integral for the corresponding half-space problem in which the effect of boundary curvature maps into an effective positive velocity gradient. The results of both analytical and numerical evaluation of this integral can be summarized as follows for body waves in the crust and upper mantle:

1) In the special case of a critical velocity gradient (a gradient equal and opposite to the effective curvature gradient), the critically refracted wave reduces to the classical head wave for flat, homogeneous layers.

2) For gradients more negative than critical, the amplitude of the critically refracted wave decays more rapidly with distance than the classical head wave.

3) For positive, null, and gradients less negative than critical, the amplitude of the critically refracted wave decays less rapidly with distance than the classical head wave, and at sufficiently large distances, the refracted wave can be adequately described in terms of ray-theoretical diving waves. At intermediate distances from the critical point, the spectral amplitude of the refracted wave is scalloped due to multiple diving wave interference.

These theoretical results applied to published amplitude data for P-waves refracted by the major crustal and upper mantle horizons (the Pg, P*, and Pn travel-time branches) suggest that the 'granitic' upper crust, the 'basaltic' lower crust, and the mantle lid all have negative or near-critical velocity gradients in the tectonically active western United States. On the other hand, the corresponding horizons in the stable eastern United States appear to have null or slightly positive velocity gradients. The distribution of negative and positive velocity gradients correlates closely with high heat flow in tectonic regions and normal heat flow in stable regions. The velocity gradients inferred from the amplitude data are generally consistent with those inferred from ultrasonic measurements of the effects of temperature and pressure on crustal and mantle rocks and probable geothermal gradients. A notable exception is the strong positive velocity gradient in the mantle lid beneath the eastern United States (2 x 10^-3 sec^-1), which appears to require a compositional gradient to counter the effect of even a small geothermal gradient.

New seismic-refraction data were recorded along a 800 km profile extending due south from the Canadian border across the Columbia Plateau into eastern Oregon. The source for the seismic waves was a series of 20 high-energy chemical explosions detonated by the Canadian government in Greenbush Lake, British Columbia. The first arrivals recorded along this profile are on the Pn travel-time branch. In northern Washington and central Oregon their travel time is described by T = Δ/8.0 + 7.7 sec, but in the Columbia Plateau the Pn arrivals are as much as 0.9 sec early with respect to this line. An interpretation of these Pn arrivals together with later crustal arrivals suggest that the crust under the Columbia Plateau is thinner by about 10 km and has a higher average P-wave velocity than the 35-km-thick, 62-km/sec crust under the granitic-metamorphic terrain of northern Washington. A tentative interpretation of later arrivals recorded beyond 500 km from the shots suggests that a thin 8.4-km/sec horizon may be present in the upper mantle beneath the Columbia Plateau and that this horizon may form the lid to a pronounced low-velocity zone extending to a depth of about 140 km.