Building frames from codes

Suppose you want to build a short, fat matrix with certain properties, such as a unit norm tight frame. How might you construct it? There happens to be an iterative technique to build every such frame, but what if you also wanted low coherence between the columns? Or entries of equal size? In this entry, I will describe how to build such frames using binary codes. For the most part, these ideas come from my Ph.D. thesis advisor, Robert Calderbank.

First, let’s review some basic coding theory. Given a finite alphabet, say , a codeword is an -long string of letters from that alphabet, and a codebook is a collection of such codewords. Messages can be represented as codewords using a code. To be clear, a code is a map from messages to codewords, but oftentimes the codebook referred to as the code. It’s all semantics, really.

When communicating over a noisy channel, codes are used for robustness. Specifically, if one of the letters in your codeword is changed (a bit flip), then a well-designed code will allow you to determine the intended codeword. Such codes are called error-correcting codes, and they can be robust to multiple bit flips. This robustness is measured in terms of something called Hamming distance: Two strings have Hamming distance if they differ in exactly letters. For example, and have Hamming distance since they only differ in the first and fourth letters. Considering the Hamming distance between all pairs of codewords in a given codebook, the distance of the code is defined to be the minimum of these Hamming distances. Notice that a code is robust to bit flips if its distance is .

At this point, it should be clear that codes lead to interesting combinatorial problems. For example, how many codewords can you pack in with distance ? Generally, extremal combinatorics is difficult, so it would be nice to restrict ourselves to a more interesting family of codes. To this end, note that it would be a pain to have to define each codeword individually. Indeed, since error correction requires us to find the closest codeword, it would be nice if the code had a simpler description.

Viewing as the finite field , a linear code is a -dimensional subspace of , and as such, contains codewords. The description of such a code is very short: pick codewords which span the subspace, and then every codeword is a combination of these. In addition to this short description, there’s a nice way of determining the distance of a linear code. Define the weight of a codeword to be the number of its “” entries. Then the Hamming distance between two codewords and is ; since is a nonzero codeword, we therefore have that the distance of the entire code is precisely the minimum weight.

As promised, we can use codes to build frames with important properties. Before we state how to do this, we need a small technical definition: A repetition in a code is a pair of distinct entries for which for every codeword . Perhaps the most naive (linear) code exclusively makes use of repetitions; for example, a so-called repetition code might map . While repetition codes are particularly easy to implement, the distance of such codes is far from optimal. Having established this, we now build frames by exponentiating binary codes:

Theorem 1. Given a -dimensional linear code in , define an matrix entrywise:

,

where is the th entry of the th codeword. Then is a unit norm tight frame if and only if there are no repetitions in the code.

Proof: Since all of the entries of have size , we already know the rows have equal norm and the columns have unit norm. To prove that is a UNTF, it remains to show that the rows are orthogonal. To this end, the inner product between the th and th rows of is

Note that defines a homomorphism from the additive group of codewords to the multiplicative group . Furthermore, the fact that there are no repetitions in the code is equivalent to the existence of a nontrivial coset of the kernel. Since the size of this coset equals the size of the kernel, we conclude that the sum in is zero precisely when the code has no repetitions.    

Theorem 2. Given a -dimensional linear code , define an matrix as in Theorem 1. If the all-ones codeword is in , then the worst-case coherence of is . Otherwise, consider the code spanned by and the all-ones codeword. Then the worst-case coherence of is

,

where is the distance of the code .

Proof: Note that the inner product between columns of has the form

.

Thus, if , then we can take so that , and so the worst-case coherence is in this case.

For the second claim, note that precisely when . Since , we therefore have

Since and are both members of , the claim immediately follows.    

It’s nice that we can use the well-established literature on linear codes to build unit norm tight frames with low coherence. Moreover, the fact that the entries have the same size makes them particularly attractive for code-division multiple access. In general, various applications of frames require different features, and these often translate naturally to a well-studied code parameter.