Sun, 04/08/2012 - 16:22 â€” saichara

**INTRODUCTION**

The aim of Error Correcting Codes study is to transmit a given message in some encoded form such that the maximum possible error can be tolerated during transmission with minimum redundancy. The Big Question in Error Correcting Codes is to study "How much redundancy is needed to correct a given amount of errors?" . Using Relative Distance and Rate of a family of codes analogous to Redundancy and Errors respectively[1], the aforementioned Big Question can be stated in another way i.e., "Given a relative distance of the code to be what is the best rate that can be achieved?" [2]. In this article, MacWilliam's Identities are used to derive a Linear Programming Bound(MRRW Bound) on the Rate of family of codes. The Linear Programming(LP) bound was developed as a consequence of Jessie MacWilliam's research stated as MacWilliam's Identities which relates the "weight enumerator function" of a linear code to its dual. For Binary Codes, the LP Bound gives the best upper bound on as a function of .

___________________________________________________________________________________________________________________

**1. STATEMENT**

The Mac Williams Identities relate the weight enumerator of a linear code to the weight enumerator of its dual code

where is the number of bits in the original message and is the number of bits in the encoded message

**1.1. Dual of a linear code ** :

A linear code is specified by a generator matrix of dimension . The parity check matrix of is of order . The dual of linear code , represented by is generated by the transpose of parity check matrix of .

** 1.2 Properties of duals:**

** Proposition 1 **:

1) If then for every codeword ,

2)If then for any the two sets , have same number of elements.

** Proof**:

The first part follows from the fact that, a linear code is generated by a generator matrix and its dual is generated by the transpose of parity check matrix and we have ** **

For second part, assume . Assume | , . We note that both are non empty. Since it is non empty. As is not a member of dual, we have a codeword such that . Then we have a codeword in with . So which implies that is also nonempty. Next, we prove that both sets have same number of elements from the following observations:

1) if then we have where . Thus

2)=, since if then

3)Now we proved that is a subset of and number of elements in equals . So we can infer that

4) Similarly, we can prove that . Thus we successfully proved that both sets have same cardinality.

** 1.3 Weight Enumerator, Weight distributions and Weight Generating Functions ** :

If we have a linear code and an index then the th weight enumerator of is the number of code words in having a Hamming Weight of .

The weight distribution of linear code C is the sequence where is the th weight enumerator of .

The weight generating function of a linear code is defined as where is the weight distribution of

** 1.4 Extended Generating Function **:

The extended generating function presents all the information about a linear code, unlike weight generating function which does not provides us with any information. The extended generating function is defined for a bit, word and code.

** 1.4.1 Extended weight generating function of a bit **:

For a bit the extended weight generating function is a polynomial in x and y and is defined as

if

if

** 1.4.2 Extended weight generating function of a word ** :

For a vector , the extended generating function is defined as which is a polynomial consisting of variables which are separated as and and is defined as

Example: a = 1000101010111

** 1.4.3 Extended weight generating function of a code **:

For a linear code , the extended generating function is defined as which is again a polynomial consisting of variables which are separated as and and is defined as

Example: Let

These extended generating functions carry all the information(codewords with weight , where can range upto the length of the code, number of codewords of the code etc) about the code, are very useful when studying the combinatorics of the code. They are not very computationally efficient. If we have the extended generating function of a code, then we can easily compute the extended generating function of its dual. As we said contains all the information about , we can derive from it. Now we can derive the dual from and in turn its extended generating function from .

The core theme of Mac Williams identities is based on Discrete Fourier Transform (DFT) or in particular, Hadamard transform. This transform, when applied to the extended weight generating function of a word, transforms it according to the following Lemma

**Lemma 1.4.4:**

.

* Proof*:

From definition of we have

Expanding the term results in terms of the form where and sign is negative if is odd. Let denote the sum of this terms. If is set when , then and the sign of is negative if . Now,

This Lemma is used to prove the following theorem

**Theorem 1.4.5 (Generalized Mac Williams Identity):**

The extended weight generating function of a code and its dual satisfy the equation

* Proof *:

From Lemma 1.4.4,

(From proposition 1)

(From definition of extended weight generating function in section 1.4)

** 1.5 Corollary ** :

Every Linear Code satisfies .

* Proof*:

Considering for all and we get:

** Proposition 2:**

** Proof **:

___________________________________________________________________________________________________________________

**2. THE MAC WILLIAMS IDENTITIES**

** 2.1 Binary Case ** :

** Proof **** ** :

From Proposition 2 , we have

From Theorem (1) we have

=

Again applying the result from proposition 2, we get

From above two equations, we have

** 2.2. General q-ary case ** :

If the alphabet over which is defined is , then the relation between weight enumerator of and its dual is given by

* For complete proof of q-ary case refer IEEE paper on simple derivation of the MacWilliams identity for linear codes *

___________________________________________________________________________________________________________________

**3. WEIGHT DISTRIBUTION OF DUAL CODE AS LINEAR FUNCTION OF WEIGHT DISTRIBUTION OF PRIMAL CODE**

Now that we have obtained expressions for MacWilliams Identities for -ary and binary codes,we now determine the exact relationship between the weight distribution of a code and its dual. The following corollary proves the same:

**3.1 Corollary**

For a given linear code with weight distribution vector and let be the weight distribution of its dual then they are related by where is a x matrix such that elements of are

*Proof*

We can see that is the coefficient of in the expression for that we had derived as MacWilliams Identity i.e.,

This can be expressed as :

Thus any power raised to say is given by product of coefficients of in and in i.e., by expanding using Binomial theorem

Thus we have obtained in term of linear function of in the above corollary. Thus using MacWilliams Identity we try to derive an upper bound on rate of a linear code(actually linear and non linear codes, but we will restrict our discussion to linear codes). This forms basis for the following section where we use Linear Programming methodology for the Rate of a code.

___________________________________________________________________________________________________________________

**4. LINEAR PROGRAMMING BOUND**

In 1973, Philippe Delsarte proposed a bound on the Rate of a code with prescribed minimum distance using Linear Programming method. The LP Bound can be stated as one of the most powerful applications of Mac Williams identities and is one of the best known upper bound on Rate of binary codes.

Let be the weight distributions of a Linear Code of length ,rank and distance . For any given code, the number of codewords is given by . We can see that and all weight distributions less than minimum distance are all zeroes i.e., and .

We define rate of any code as ratio of (length of original message) to i.e.,

Rate of a code.

For deriving an upper bound on rate R, it is enough to maximize the Linear function . However this expression is subject to the following restrictions:

a)

b)

c)

d)

___________________________________________________________________________________________________________________

**5. MRRW BOUNDS**

A breakthrough in deriving an asymptotic analysis of LP bound was done by McEliece, R., Rodemich, E. , Rumsey, H. , Welch, L. They gave two upper bounds based on the linear function described above . These bounds are formally known as MRRW bounds. The first bound is the best known asymptotic bound of a binary code for rough ranges of .

We shall state the bounds for binary and -ary linear codes in its simplest forms in the following sections.

For complete proof of -ary codes see New Upper bounds on the Rate of a code via the DelSarte-Macwilliams Inequalities- IEEE Xplore

**5.1 First MRRW Bound for -ary Codes**

The Rate of a family of codes(-ary code) of relative distance , where is

where is a -ary entropy function defined by

**5.2 First MRRW Bound for binary Codes**

The MMRW bound for binary codes is understandably obtained by putting in the -ary MMRW bound and is stated as follows:

The Rate of a family of binary codes of relative distance is given by

where

*Proof*

The above bound is proved on the basis of following theorem stated.

**5.2.1 Theorem : Dual Codes have a small "essential covering radius" **

Let be a linear code with minimum distance ,length and dual then :

where is a Hamming Ball of radius such that for all vectors

where denotes distance between and

*Proof*

By inspection we can say that . Then we proceed by considering two propositions.

(i) Consider a set with sufficiently large maximum eigenvalue, so that covers a significant , in precise fraction of the whole space i.e,

For {} and ,

where is the maximal eigenvalue of adjacency matrix of the subgraph of induced by the vertices of .

(ii) achieves the required maximum eigenvalue even when r is not too large i.e.,

We pick a radius such that

This is satisfied if :

The proof of these propositions in 5.2.1 can be found in Venkat Guruswami's lecture notes .

Having stated the propositions we are ready to prove the First MRRW Bound on Binary linear Codes.

Consider the following expression :

This follows since volume of each ball is exactly . But the sizes of a code and its dual are related by : .

Combining the above two relations we can say that

Substituting the bound on in the earlier theorem and substituting , we get

i.e.,

The graph below plots the comparison for the First MRRW Bound alongside the Gilbertâ€“Varshamov bound and Elias_Bassalygo_bound. This represents the Rate of a Code (on axis) versus Relative distance (on axis).

**5.3 Second MRRW Bound for binary Codes**

Let for a binary Code, the rate of this code is given by

where

if else

The second MRRW Bounds are stated for binary codes and is not generally extended for larger alphabets.

___________________________________________________________________________________________________________________

** See Also**:

1. Hamming Bound

2. Singleton Bound

3. Gilbert Varshamov Bound

4. Plotkin Bound

___________________________________________________________________________________________________________________

** REFERENCES**:

1. ^ Chapter 2 : A Look at Some Nicely Behaved Codes: Linear Codes.

2. ^ Chapter 4 : What can and what cannot be Done

1. Madhu Sudan's Algorithmic Introduction to Coding theory

2. Lecture Notes from Introduction to Coding Theory by Venkatesan Guruswami on Fourier Transform, MacWilliam's Identities and LP Bound

3. Lecture Notes from Introduction to Coding Theory by Venkatesan Guruswami on Proof of the MRRW Bound

4. Linear programming bounds for codes via a covering argument by Michael Navon and Alex Samorodnitsky

5. Chapter 1: The Fundamental Question: Essential Coding Theory By Venkatesan Guruswami, Atri Rudra and Madhu Sudan

- Login to post comments