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 \{0,1\}, a codeword is an n-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 d if they differ in exactly d letters. For example, 0010 and 1011 have Hamming distance 2 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 e bit flips if its distance is \geq 2e+1.

At this point, it should be clear that codes lead to interesting combinatorial problems. For example, how many codewords can you pack in \{0,1\}^n with distance d? 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 \{0,1\} as the finite field \mathbb{F}_2, a linear code is a k-dimensional subspace of \mathbb{F}_2^n, and as such, contains 2^k codewords. The description of such a code is very short: pick k 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 \mathrm{wt} of a codeword to be the number of its “1” entries. Then the Hamming distance between two codewords c and c' is \mathrm{wt}(c+c'); since c+c' 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 i,j for which c[i]=c[j] for every codeword c. Perhaps the most naive (linear) code exclusively makes use of repetitions; for example, a so-called repetition code might map 1011\mapsto11001111. 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 k-dimensional linear code in \mathbb{F}_2^n, define an n\times 2^k matrix F entrywise:

\displaystyle{F[i,j]=\frac{1}{\sqrt{n}}(-1)^{c_j[i]}},

where c_j[i] is the ith entry of the jth codeword. Then F is a unit norm tight frame if and only if there are no repetitions in the code.

Proof: Since all of the entries of F have size 1/\sqrt{n}, we already know the rows have equal norm and the columns have unit norm. To prove that F is a UNTF, it remains to show that the rows are orthogonal. To this end, the inner product between the ith and i'th rows of F is

\displaystyle{\sum_{j=1}^{2^k}F[i,j]F[i',j]=\frac{1}{n}\sum_{j=1}^{2^k}(-1)^{c_j[i]+c_j[i']}.\qquad (1)}

Note that (-1)^{c_j[i]+c_j[i']} defines a homomorphism from the additive group of codewords to the multiplicative group \{\pm 1\}. 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 (1) is zero precisely when the code has no repetitions.     \Box

Theorem 2. Given a k-dimensional linear code C\subseteq\mathbb{F}_2^n, define an n\times 2^k matrix F=[f_1\cdots f_{2^k}] as in Theorem 1. If the all-ones codeword is in C, then the worst-case coherence of F is 1. Otherwise, consider the code C' spanned by C and the all-ones codeword. Then the worst-case coherence of F is

\displaystyle{\max_{\substack{i,j\in\{1,\ldots,2^k\}\\i\neq j}}|\langle f_i,f_j\rangle|=1-\frac{2d}{n}},

where d is the distance of the code C'.

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

\displaystyle{\langle f_j,f_{j'}\rangle=\sum_{i=1}^nF[i,j]F[i,j']=\frac{1}{n}\sum_{i=1}^n(-1)^{c_j[i]+c_{j'}[i]}=\frac{n-2\mathrm{wt}(c_j+c_{j'})}{n}}.

Thus, if 1\in C, then we can take c_{j'}:=c_j+1 so that \langle f_j,f_{j'}\rangle=-1, and so the worst-case coherence is 1 in this case.

For the second claim, note that \langle f_j,f_{j'}\rangle<0 precisely when \mathrm{wt}(c_j+c_{j'})>n/2. Since \mathrm{wt}(c+1)=n-\mathrm{wt}(c), we therefore have

\displaystyle{|\langle f_j,f_{j'}\rangle|=\left\{\begin{array}{ll}1-\frac{2}{n}\mathrm{wt}(c_j+c_{j'})&\mbox{if }\mathrm{wt}(c_j+c_{j'})\leq n/2,\\1-\frac{2}{n}\mathrm{wt}(c_j+c_{j'}+1)&\mbox{if }\mathrm{wt}(c_j+c_{j'})>n/2.\end{array}\right.}

Since c_j+c_{j'} and c_j+c_{j'}+1 are both members of C', the claim immediately follows.     \Box

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.

Advertisements

One thought on “Building frames from codes

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s