Research

Coding Theory Objectives

All codes are designed to transmit information efficiently, however, efficiently means different things in different contexts. One measure of efficiency is the rate of code, which indicates how long the codewords of the code are compared to the amount of information they encode. The higher the rate of a code, the shorter its codewords are, and the more efficiently the information of the original message is packed into the codeword. Higher rate codes are sought after as they require less space to store and less data to be sent in transmission.

More broadly, however, there are many different codes designed for many different applications. There are codes designed to detect/correct as many errors as possible, codes designed to repair as many erasures as possible, codes designed to fix some errors/erasures but utilize the smallest codewords possible, codes designed to repair erasures using the least information from the remaining codeword as possible, etc, etc. However, we may not both minimize the length of codewords and maximize our error/erasure fixing capabilities in the same code. This is due to what I call the "fundamental relationship in coding theory."

The Fundamental Relationship of Coding Theory

The fundamental relationship in coding theory is the trade off between the number of errors or erasures a code can fix and the length of its constituent codewords. Essentially, every code works by adding redundancy to the information of the original message. This redundancy is often introduced by creating codewords with a structure. An example is the natural code found in the English language. Consider the following sentence which you could say to communicate that you are leaving.

This is not only a beautiful farwell, but also a great demonstration of the structures hidden in natural language. Think about how in the above sentence the structures of the English language force certain words to be used in certain places, irregardless of the intent of the speaker. Take these examples.

(1) Once the subject of the sentence was chosen to be "I", the present "to be" verb in the sentence had to be "am". It could not be "is" or "are" by the conjugations of English.

(2) As "am" indicates present/future tense the action verb here virtually has to end in "ing" to match the present/future tense.

(3) Since the place you are travelling is "away" the only possible travelling "verb" which matches that locale is "go". Drastically oversimplifying here, in English you can essentially "come" or "go". And while you can "come home" and "go home" you cannot "come away". Thus the sentence must employ a "go" verb here.

The point being, the structure of English forces each word of our sentence to be dependent on all of the words around it. This adds redundancy to our message as certain words are not chosen by the speaker, but determined by the rest of the message. The fact that the sentence starts with "I" is completely redundant information, as once the "to be" verb is chosen to be "am" the only possible start of the sentence is "I am".

Importantly, we can use this redundancy to fix errors/erasures! For example, if you heard the sentence "__ am going away" where you missed the first word, you could be pretty sure the missing word should be "I" based on the redundancy we discussed above. Or if you heard "I am joined away" you could detect there is an error somewhere based on how "joined" does not make sense with the present tense of "am" or the locale of "away". And you can even use the structures above to determine that most likely the speaker must have said "I am going away" as "going" is one of the only words that works with both of these structures.

However, while this structure in English is great for fixing errors/erasures it comes with a cost. A very small percent of possible strings of English words are actually valid sentences. Let's say there are M potential ideas that a human might want to communicate via a sentence and q words in the English language. If there was no structure to the English language then every string of English words would represent a sentence. This would mean there are roughly q one-word sentences, q² two-word sentences, q³ three-word sentences etc. Hence, to cover every possible idea, we would roughly need about n words per sentence where n is such that,

But now let's think about the average sentence length given the actual structure of English. Suppose that only 5% of strings of English words are valid sentences. Then very roughly there are 0.05qⁿ n-word sentences. Thus, redoing the math above,

i.e the average length of a sentence must increase. Meaning the same structure which allows us to fix errors/erasures in spoken language also forces our sentences to be longer, requiring more breath, time, and pages to communicate. This is equivalent to lowering the rate of the code.

Another way to think about this is to imagine the length of English sentences if we removed all of the redundancy. For example, as discussed above in the sentence "I am going away" the "I" and the "ing" (and arguably even the "go") are completely redundant. So if we take out all of the redundant information this sentence would just read "am go away". Notice this sentence is shorter, which illustrates the point that adding redundancy to a message must fundamentally increases its length.

This is the fundamental relationship of coding theory, and coding theorists can spend their entire careers optimizing tradeoffs like this for an endless variety of applications.

The Singleton Bound

While I described the so-called fundamental relationship in coding theory above qualitatively, it can also be described quantitatively in the form of a bound. First we need to quantize the amount of errors/erasures a code is capable of fixing. To do this, we will introduce what is called as the minimum distance of a code. The minimum distance of a code is just the minimum number of symbols in which two valid codewords differ. The distance is a measure of the error correcting capability of a code, since it is known if a code has distance d it can correct ⌊(d - 1)/2⌋ errors.

Then, given a linear code (this is a special type of code which is a vector space) with codewords of length n, rate R, and a minimum distance d, the relationship between the rate of this code and the maximum number of errors it can correct may be expressed as

Modern Improvements

Beyond just applying to codes void of traditional repair schemes, linear exact repair schemes can also be competitive in settings where there are previously well-established alternatives. To start, we need to discuss how we compare different repair schemes. There are many different metrics, but in general we quantify the efficiency of an exact repair scheme with what is known as the bandwidth. The bandwidth of a scheme is the amount of information we need from the remaining symbols of a codeword to repair an erased symbol. Generally this is measured in symbols of the ambient finite field, but is also sometimes measured in bits. In this case it is known as the bitwidth. In almost every setting it is advantageous to minimize the bandwidth as this requires the least amount of information to be transmitted.

Naively, it would seem that linear exact repair schemes have very high bandwidth. For example, using the most general formulation of a linear exact repair scheme above, it would seem that every remaining symbol of the codeword is required to repair a single erased symbol. If there are n symbols in our codeword this would translate to a bandwidth of n - 1. This is literally the maximum bandwidth possible, which is not ideal considering we would like to minimize the bandwidth. However, with some simple additions to the general formulation, it is possible to construct linear exact repair schemes with very competitive bandwidths.

In their 2016 paper Repairing Reed-Solomon Codes, Guruswami and Wootters outlined their twist on linear exact repair schemes that make them more efficient than traditional repair schemes in certain contexts. The core idea of their scheme revolves around a particular finite field operation known as the field trace. Given any finite field with q^t elements there is a polynomial called the field trace and denoted Tr(x) defined as

For reasons beyond the scope of this discussion, the field trace will wind up having the two following properties.

These properties are what allowed Guruswarmi and Wooters to create a competitive linear exact repair scheme. The setting for their scheme is a Reed-Solomon code over a finite field with q^t elements where z₁, ..., z_t is a basis for this field over F_q. Then there must exist some dual basis z₁', ..., z_t' such that for any element of the finite field, f(a*), we have

Notice then, if f(a*) is an erased symbol of a codeword in an evaluation code (f(a₁), ..., f(a_n)) we may recover f(a*) using the t subfield elements Tr(z₁f(a*)), ..., Tr(z_tf(a*)). As the large field is a degree t extension over the subfield F_q, each subfield element contains 1/t the information of an element in the large field. Thus, each trace Tr(z_if(a*)) only contains 1/t the information of a larger field element so theoretically may require less information from the remaining symbols to recover. However, there are t of these traces, so it would appear in the aggregate it will take the same amount of information to recover these traces as it would f(a*). Interestingly, this is not the case.

To see why, let us perform t independent general linear exact repair schemes that we will use to recover Tr(z_if(a*)) for each i. This requires us to construct a polynomial r_i in the dual code such that r_i(a*) = z_i. The brilliance in the Guruswami and Wootters 2016 paper is the construction of this polynomial. In that article, they define

Then, for each i in {1, 2, ..., t} we can proceed with a general linear exact repair scheme like normal,

Taking the trace of both sides

we can compute Tr(z_if(a*)) using the above sum. Let's compare all of these sums for each i in {1, ..., t}.

Master's Thesis

In my master’s thesis I developed a linear exact repair scheme to be used to repair an erasure in a particular type of multivariate evaluation code known as a Cartesian code. The scheme I developed required the construction of a novel multivariate polynomial of the form

which is 0 at exactly one point. Importantly, this idea can be extended to the m-variate case through a recursive construction. It has been shown that in certain situations, the schemes developed here are more efficient than schemes based on Reed-Solomon codes themselves.

Augmented Reed-Muller Codes of High Rate and Erasure Repair (ISIT 2021)

In this ISIT (IEEE Symposium on Information Theory) conference paper I worked to developed new evaluation codes, known as augmented Reed-Muller codes, which are optimized monomial-Cartesian codes designed to have very high rates. It is important to note the higher rate the code, the more efficiently it can store information, so this is a significant contribution. We developed repair schemes specifically for these codes based on the linear exact repair concept. In situations where the data storage capacity of nodes is limited, distributed storage systems based off of Augmented Reed-Muller codes 1 \& 2 are the most efficient or sometimes the only systems capable of both respecting the storage requirements and restoring failed nodes.

Erasure Repair for Decreasing Monomial-Cartesian and Augmented Reed-Muller Codes of High Rate (IEEE Transaction on Information Theory 2021)

In a continuation of the above paper, I worked to develop linear exact repair schemes for a class of codes known as decreasing monomial-Cartesian codes. These codes are the most general multivariate evaluation codes admitting a linear exact repair scheme known thus far. We also developed extended versions of augmented Reed-Muller codes known as augmented Cartesian codes. These codes are an extension of augmented Reed-Muller codes for which the degrees of polynomials can be restricted in each variable independently. The extra degrees of freedom present when constructing decreasing monomial-Cartesian codes allows for the development of highly specialized codes which can be optimized for any situation.