CaltechTHESIS
  A Caltech Library Service

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

Citation

Thill, Matthew David (2016) Algebraic Techniques in Coding Theory: Entropy Vectors, Frames, and Constrained Coding. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z9F18WNW. http://resolver.caltech.edu/CaltechTHESIS:09042015-171723764

Abstract

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.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Coding theory; group-characterizable entropy vectors; group codes; frames; coherence; constrained coding; Reed-Solomon codes
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Hassibi, Babak
Thesis Committee:
  • Hassibi, Babak (chair)
  • Bruck, Jehoshua
  • Chandrasekaran, Venkat
  • Divsalar, Dariush
  • Kostina, Victoria
  • Vaidyanathan, P. P.
Defense Date:19 August 2015
Record Number:CaltechTHESIS:09042015-171723764
Persistent URL:http://resolver.caltech.edu/CaltechTHESIS:09042015-171723764
DOI:10.7907/Z9F18WNW
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9141
Collection:CaltechTHESIS
Deposited By: Matthew Thill
Deposited On:04 Dec 2015 23:11
Last Modified:18 May 2017 19:54

Thesis Files

[img]
Preview
PDF - Final Version
See Usage Policy.

1734Kb

Repository Staff Only: item control page