*[Lecture scribed by Srivatsan Narayanan]*

We will discuss the last and most sophisticated of our (upper) bounds on rate of codes with certain relative distance, namely the first linear programming bound or the first JPL bound due to McEliece, Rodemich, Rumsey, and Welch, 1977 (henceforth, MRRW). This bound is the best known asymptotic upper bound on the rate of a binary code for a significant range of relative distances (which is roughly ). We will present a complete and self-contained proof of the this bound. A variant called the second JPL bound gives the best known upper bound for the remainder of the range, and we will mention this bound (without proof) at the end.

The linear programming bound is so-called because it is based on Delsarte’s linear programming approach which shows that the distance distribution of a binary code satisfies a family of linear constraints whose coefficients are the evaluations of a certain family of orthogonal polynomials (in this case, the Krawtchouk polynomials). The optimum (maximum) of this linear program gives an upper bound on . MRRW constructed good feasible solutions to the dual of linear program using tools from the theory of orthogonal polynomials, and their value gave an upper bound on by weak duality.

In these notes, we will use Fourier analysis of functions defined on the hypercube to derive a relationship between the weight distribution of a linear code and its dual, called the MacWilliams identifies. These give the linear constraints of the above-mentioned linear program.

Instead of the using the linear program or its dual and the theory of orthogonal polynomials (and specifically properties of Krawtchouk polynomials), in the second part of these notes, we will give a *self-contained proof* of the first linear programming bound for binary linear codes using a Fourier analytic approach. This is based on the methods of Friedman and Tillich, which was later extended also to general codes by Navon and Samorodnitsky, that shows that the dual of a linear code of large distance must have small “essential covering radius” (which means that Hamming balls of small radii around the dual codewords will cover a large fraction of the Hamming space ). This shows that the dual must have large size, and therefore the code itself cannot be too large. The method can be extended to non-linear codes, but we will be content with deriving the linear programming bound for (binary) linear codes.

**1. Fourier analysis over the Boolean hypercube **

Let be set of all real-valued functions over the boolean hypercube, *i.e.*, . Then the following characterization is straightforward.

Exercise 1Show that forms a vector space with dimension . In fact, show that forms a basis for , where is defined by:

In fact, the above exercise views a function as simply a vector of dimension , indexed by the ”coordinates” . This motivates us to define an inner product on :

Definition 1For , define the inner product between and to be:

(This is just the standard inner product for vectors over reals, but suitably normalized.)

Now, we will define another basis for , called the *Fourier basis*. This needs the following simple lemma.

Lemma 2For every binary linear code ,

where denotes the dot product modulo .

*Proof:* If , then the claim is obvious. Suppose that . Then, there exists a such that . Now, for each ,

Summing Equation 1 for all , we get:

giving the claim.

*Proof:* In Lemma 2, take to be the whole vector space , so that .

Remark 1In this lecture, the notation is typically overloaded to mean either a single alphabet symbol, or the zero vector () of the vector space. However, the right definition should be clear from the context.

For each , define by (where refers to the inner product between vectors, taken modulo ). The function is often called a *character function*. We show that the set of all character functions also forms an orthonormal basis for .

*Proof:*

using Corollary 3. The claim follows from the definition of .

Corollary 5Let be the set of character functions,i.e., . Then, is an orthonormal basis for , called itsFourier basis.

*Proof:* From Lemma 4, it follows that is a linearly independent set. Also the cardinality of is , which equals the dimension of the whole space . Therefore, must be a basis. The orthonormality of is directly implied again by Lemma 4.

By the definition of a basis, any function can be expressed uniquely as a linear combination of the character functions. That is, there exist such that

(We use the notation , instead of the conventional to remind us that the coefficients depend on .) Note that this is equivalent to saying

for all .

The following are some immediate consequences of this fact.

Lemma 6Let . Then the following hold.

(Parseval’s identity)

*Proof:* Each of the above claims can be shown by a straightforward calculation.

**2. Dual codes, Fourier analysis, and MacWilliams identities **

Let us introduce the following notation: for any , define , called the *characteristic function of *, by

We will now show that Fourier transform of the characteristic function of a code is *essentially the same* (up to a constant scaling factor) as the characteristic function of its dual. This is useful because the Fourier transform can be viewed as a notion of duality for functions. Fortunately, there is a natural correspondence between the two notions (dual codes and Fourier transforms).

Lemma 7For any linear code ,

*Proof:* For every ,

using Lemma 2. Therefore,

for all , giving the claim.

Definition 8For any , let

that is, denotes the number of points in of weight . Further, byweight distributionof , we denote the -tuple .

Now, our goal is to relate the “weight distribution” of a code to that of its dual . Let . Then,

For completeness, we calculate the sum in the following lemma. The exact sum is not of any significance for our purposes in this course. We will however use the fact that this sum depends *only* on the weight of .

Lemma 9For any with ,

The latter quantity will be denoted as — the value of the Krawtchouk polynomial at .

*Proof:* Notice that summation is taken over all of a given weight . So, by symmetry, it depends only the number of ‘s in , and not on their positions. Hence, without any loss in generality, assume that . A vector of weight must have ‘s in the first positions, and in the last positions, for some , and in this case . The number of ‘s satisfying this condition for any particular equals . The claim thus follows.

Remark 2 (Krawtchouk polynomial)The quantity , denoted , can be regarded as the evaluation of a polynomial at . is usually called the Krawtchouk polynomial and is defined as

(The function also depends on , but we supress this dependence for notational convenience.) Note that is a polynomial of degree and and , etc.

Now, we will complete the calculation of .

for every .

Equation 2, called the MacWilliams identity, tells us that the weight distribution of the dual code is completely determined once we are given the weight distribution of the code .

Remark 3We can write the MacWilliams identitities (2) equivalently as:

or as a functional equation

Exercise 2Extend the MacWilliams identities to linear codes over any finite field . Specifically, if is a -ary linear code of block length , and as before (resp. ) denote the number of codewords of (resp. ) of Hamming weight , then

where the -ary Krawtchouk polynomial is defined as

[[Hint: When the field size equals a prime , replace in the proof for the binary case by where is a primitive ‘th root of unity and is, as usual, computed over the underlying field .

When for a prime , the role of can be played by where is the trace map from to : .]]

Exercise 3Using the above, compute the weight distribution of the Hamming code.

**3. A linear program bounding **

In this section, we will use the MacWilliams identity to derive a linear program that bounds the size of every code with a given minimum distance , and thus bounds . (Recall that is the maximum size of any binary code with block length and minimum distance .)

For the moment, we will focus on linear codes . Consider the linear program:

We claim that for any *linear* code of distance at least , the assignment is a feasible solution. Indeed, the first two constraints are satisfied trivially. The constraint for enforces that the minimum distance of the code (that is, the minimum Hamming weight of any nonzero code word) is at least . The last set of constraints follow from the MacWilliams identities for any ,

For this assignment, the objective function takes the value

Therefore, the optimum of the linear program upper bounds the size of any linear code of distance at least .

Now, we consider general codes , and prove that they satisfy the same bound. Without loss of generality, assume that . Define:

We claim that is a feasible solution to the linear program. The first three sets of constraints are trivially satisfied as before, whereas the last set of constraints can be verified in a straightforward manner:

The value of the objective function is:

Therefore, the optimum value of the linear program upper bounds the size of any code with minimum distance at least .

** 3.1. Dual program and the MRRW bound **

Consider the dual program for the above linear program. The dual program has variables (where ). Define to be the polynomial

Then the dual program is given by:

By the weak duality theorem, the value of *any* feasible solution to the dual program upper bounds the optimum value of the linear program, and hence also upper bounds . Hence, in order to upper bound the size of the code, it suffices to exhibit a dual feasible solution with a small objective function. This was, in fact, the approach followed by MRRW, leading to the first linear programming bound. However, this involves studying several properties of Krawtchouk polynomials. In the second installment of these notes, we will prove the same bound by following a different approach based on Fourier analysis.

[…] “Notes 5.1: Fourier Transform, MacWillams identities, and LP bound. Filed under: Lecture notes — Venkat Guruswami @ 3:47 pm [Lecture scribed by Srivatsan […]

Pingback by linear programming, dual codes, fourier analysis | Peter's ruminations — August 10, 2011 @ 11:43 am |

[…] Regarding https://errorcorrectingcodes.wordpress.com/2010/02/07/notes-5-1-fourier-transform-macwillams-identiti… […]

Pingback by fourier, duals; weights | Peter's ruminations — August 13, 2011 @ 9:06 pm |