Skip to content

An Error Correcting Code From The Book

August 8, 2011

But can we find the pages it is on?

Atri Rudra is a coding theorist who helped organize the recent workshop in Ann Arbor on Coding, Complexity, and Sparsity. He has strong coding theory ancestors:

  • Venkatesan Guruswami
  • Madhu Sudan
  • {\vdots}
  • Leonhard Euler
  • Jacob Bernoulli

Jacob was a member of the great Bernoulli family. They together did remarkable work in many aspects of mathematics, but Jacob is the one who invented the Bernoulli distribution that is used throughout coding theory. Recall this is the distribution that takes on {0} with probability {p} and {1} with probability {q=1-p}, in each of multiple independent trials. It is such a simple idea, but someone had to invent it, and Jacob did.

Atri himself, with his advisor Venkat Guruswami, began making some breakthrough contributions to coding theory several years ago, including this STOC 2006 paper, which was also referenced in a popular article by Bernard Chazelle for the magazine Science. Yet the following simple problem remains. Atri told me about it a few months ago, and it seems too basic to be open. But it is. The problem concerns possibly the simplest good linear code.

Good Codes

Jørn Justesen in his seminal 1972 paper “A class of constructive asymptotically good algebraic codes” gave the first example of a strongly explicit binary codes with constant rate and linear distance. This had been a Holy Grail for years in coding theory, open since its beginning. Before 1972 it was known via randomized constructions that such codes existed, but there were no explicit constructions. His codes, now known as Justesen Codes, were constructive, and so solved the open problem, but they were not very simple.

A linear code is a {k}-dimensional vector subspace given by a {k \times n} generator matrix. Its rate is {k/n}, and its minimum distance {d} equals the minimum number of non-zero entries in a non-zero codeword, which is called the codeword’s weight. A good code has {k} and {d} both {\Theta(n)}. This means the code can detect many errors without excessively extending the length-{k} plaintext words that are given to it.

There is a simple linear code that is attributed to John Wozencraft by Justesen, and this code is known to be good. The problem is that the code, which we will denote by {W(\alpha)}, depends on a parameter {\alpha}. If this parameter is selected randomly, then the code is terrific: its rate in fact lies on the famous Gilbert-Varshamov Bound. This bound is due to Edgar Gilbert and Rom Varshamov who independently discovered it—again that phenomenon of dual discovery.

The main open question with this code is how to de-randomize it: Is there a way to explicitly construct for each length {n} an {\alpha} that works? This has been open going on close to fifty years.

The {W(\alpha)} Codes

The code {W(\alpha)} operates over the finite field {\mathbb{F}_{2^{n}}}. The code consists of the words of the form:

\displaystyle  (x,\alpha \cdot x),

where {x} is viewed as being in the finite field and the product is the finite field multiplication. Clearly this is a simple code: to encode {x} one only needs to do one field operation. Pretty impressive.

I will not give the full proof of why this code has such a good distance for {\alpha} selected randomly, but will give the intuition behind it. The question reduces to what is the least weight of a non-zero code word.

Let {(x,\alpha \cdot x)} be a non-zero code word with the lowest possible weight. Clearly, {x} must be non-zero and of low weight. If its weight is large, then it does not matter what the rest of the code word is. Therefore we can assume that {x} has low weight. But {\alpha} was selected randomly, and since {x} is non-zero, the word {y = \alpha \cdot x} is a random code word. Thus we need only note that such a word is exponentially unlikely to be of low weight. A union-bound argument then applies because there are many fewer low-weight words {x} than possible {\alpha}.

The full proof is mainly a careful analysis of the probability of a word having a low weight. It and more including links to Atri’s own notes can be found here*—the “*” is a footnote. A pretty neat result, a pretty cool code, and a very hard open problem. How can we select {\alpha} deterministically? The proof shows that almost all {\alpha} work, but finding one explicitly seems to be beyond our current abilities.

Complexity Theory Connections

The simplicity of this code {x \rightarrow (x,\alpha \cdot x)} suggest some connection to de-randomization problems of complexity theory. The rough idea is this:

  • Show that {\alpha \cdot x} is computed by some low level complexity class.
  • Then show that there is a method to de-randomize this class.

The reason I think that this is a possible approach is the very nature of the code. The code only does one finite field operation, which suggests to me that there could be some hope in solving this problem.

A more general question notes that the only property used in building this code is that {\alpha \cdot x} is an invertible operation. This means that for any {x} non-zero, the values of {\alpha \cdot x} are uniformly distributed, if {\alpha} is. Perhaps there is another operation that has this property that will still make the code work, but is easier to de-randomize?

Open Problems

Can you see how to de-randomize this code? Can you relate this problem to other open de-randomization problems from complexity theory?

\displaystyle  \S

The footnote*: Ken fixed typos “Wonzen—” to “Wozen—” in the Wikipedia article on {W(\alpha)}, but the typo persists in the article’s title and hence its URL. This is what the typo-fixed link will be. Is there a good way to automate correcting this kind of link error on the Net? Can error-correcting codes applied to URLs be relevant here?

9 Comments leave one →
  1. August 8, 2011 1:18 pm

    I would guess that good choices of \alpha are complicated in the sense of having minimal polynomials of large degree and/or having large order in the multiplicative group. If that’s true, derandomizing this algorithm might be related to hard number-theoretic problems. (At least, I would guess that finding primitive roots in finite fields is hard.)

  2. August 8, 2011 1:39 pm

    Ken, to fix a problem in the title of a Wikipedia article, you have to move the page.

  3. August 8, 2011 1:41 pm

    I moved the Wikipedia article to the correct title for you: (note lower case in the second title word).

    • August 8, 2011 3:25 pm

      Thanks!—to you and Tyson. Meanwhile I fixed the link in the post by making that ‘e’ lowercase. I’m pretty sure the original link had the uppercase ‘E’, and I know Wikipedia’s style asks lowercase there, so it was a second unit of edit-distance in the URL.

  4. August 8, 2011 2:31 pm

    It’s a very nice open question.

    A more general question notes that the only property used in building this code is that is an invertible operation. This means that for any non-zero, the values of $\alpha\cdot x$ are uniformly distributed, if $\alpha$ is. Perhaps there is another operation that has this property that will still make the code work, but is easier to de-randomize?

    This should be qualified (probably the qualification is already clear to you, but for readers’ benefit).

    Technically, the argument uses that the operation $x \rightarrow \alpha \cdot x$ (over $\mathbb{F}_{2^n}$) is linear, viewed as an operation over $\mathbb{F}^n_{2}$. This ensures that our code is linear over $\mathbb{F}_{2}^n$, which allows us to equate the code’s minimum distance with its minimal nonzero-codeword weight.

    So to make the same argument work, we’d need to find another linear operation, which is fairly restrictive.

    We could use a nonlinear operation and settle for a non-linear code, but then we would have to bound the minimum distance directly. This involves a significantly-larger union bound: rather than ranging over $x$ with $|x|$ small, one would have to range over $x, y$ with $|x – y|$ small.

  5. Alex H. permalink
    August 8, 2011 4:16 pm

    You say:

    > The rough idea is this:
    > Show that (alpha * x) is computed by some low level complexity class.
    > Then show that there is a method to de-randomize this class.

    Well, computing alpha*x is computable in AC^0[mod 2], but it’s not clear to me that this is enough (even if it were in AC^0 or in some class that can be fully derandomized). In particular, it’s not obvious to me that it’s sufficient to compute alpha*x. Don’t you need a low level complexity class that can *recognize* if you have a good alpha, i.e., one with good minimum distance? On the surface, this sounds like a much trickier problem than just doing the arithmetic. (Maybe it’s easier because you can restrict to the case where x has a low weight?)

    • atri permalink
      August 9, 2011 7:38 am

      Alex: You’re right. The main problem seems to be that the only way we can compute the distance of such codes is to go through all possible codewords. The simplicity of the encoding might be useful but we do not know of a way to exploit it.

      There is a derandomization result known. Cheraghchi, Shokrollahi, and Wigderson observed that under standard derandomization complexity assumptions (for much higher complexity classes then what Dick proposed above) the Wozencraft ensemble can be derandomized.


  1. Weekly Picks « — the Blog
  2. Eleventh Linkfest

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s