User:Raman Sonkhla/Parvaresh-Vardy codes and list decoder

Introduction

edit

We know that a Reed Solomon code (RS code),  , has a distance   and a list decoding radius  . Hence the list decoding rate, R, of the code is  , where   is the number of fraction errors. Now the next question is can we arithmetically do better than this in polynomial time? For seven years after the Guruswami-Sudan, there was no progress till the break through work of Parvaresh and Vardy. The Parvaresh-Vardy (PV) codes are based on RS codes.

The list decoding algorithm is based on two key ideas. First is the transition from bi-variate polynomial interpolation to multivariate interpolation decoding. The second key idea is to take different approach than that is taken with RS codes as a number of prior attempts to overcome the   rate barrier has already proved unsuccessful. Hence rather than devising a better list-decoder for RS codes, new codes were constructed.

Standard RS encoder view a message as a polynomial   over a field  , and produce the corresponding codeword by evaluating   at   distinct elements of  . In case of PV codes, given  , first related polynomials   are computed and then the corresponding codeword is produced by evaluating all these polynomials. Correlation between   and   is of form   Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. TeX parse error: Extra close brace or missing open brace"): {\displaystyle \mod }  . Here   is an arbitrary irreducible (over  ) polynomial of degree k, and   is an arbitrary (but sufficient large) integer. Correlation between   and   when   provides information that is exploited to break the   fraction of error barrier for adversarial errors.

Decoder

edit

Input for the PV list decoding algorithm will be   and  . Here   is called the agreement parameter. The output of algorithm will be all degree   polynomials   such that the PV codeword corresponding to   agrees with the received word in at least   places. The algorithm consists of the following steps,

  1. Find   such that
    1.   for all  .
    2.        .
  2. While  , put  .
  3. Put      , put   and output all roots of  .

Here note that   and if   and   then  .

Performance analysis of PV codes

edit

In case of PV codes the message corresponds to an element of  , i.e.   symbols from the alphabet  . Hence rate is  . As we can list decode from   agreement, hence we could recover from   fraction of errors. On the other hand RS codes achieved only a rate of  .

Improvements

edit

Some improvements that can be made to PV codes include,

  1. We can insist that   have multiple roots at  . This would eliminate the leading constant factor of 3 in  , and would improve rate to  .
  2. Additionally we can use correlated polynomials to extract additional performance from PV codes. Let   be the message that we want to transmit. For   we put  . This results in following encoding,  .

Now although we pay extra running time in   while decoding, but its still remains a polynomial time algorithm for any fixed m and yield recovery from   fraction of errors. Asymptotically, for large  , this approaches (letting   now)   but doesn’t really do much better for any fixed R. Also since alphabet becomes  -tuples of  , rate can not possibly increase  .


Application in Guruswami-Umans-Vadhan Expander Construction

edit

Expanders are highly connected yet sparse graphs. They have a wide variety of applications in theoretical computer science, in designing algorithms, to construct hash functions in cryptography, error correcting codes, extractors, pseudorandom generators, sorting networks and robust computer networks. The construction of expanders of Guruswami-Umans-Vadhan is based on the list decodable codes of Parvaresh and Vardy.

Let us review the basics of list decodable codes. We take C as the code which is a mapping   encoding messages of bit length   to  symbols over the alphabet   Rate of such a code will be  . We call   as   list decodable if for every , the set LIST  is of atmost K size. With list decodable codes, we wish to optimize the tradeoff between the agreement   and the rate   which do not depend on message length M. Sudan showed that such a property can be achieved by Reed Solomon Codes in polynomial time. This tradeoff was then improved by Guruswami and Sudan and recently by Parvaresh and Vardy who improved the tradeoff by using a variant of Reed Solomon codes.

GUV Constructor

edit

The construction of Guruswami-Umans-Vadhan Expander is based on Parvaresh Vardy codes.We know that a typical Parvaresh Vardy codeword has several related degree   polynomials   evaluated at all points in the field and   where   is a prime power over which the field   is defined. All such evaluations are packaged into larger alphabet   symbol. This extra redundancy enables a better list decoding algorithm than Reed Solomon ones. Elements of   are chosen such that   for   and   integer parameter.

We need to show that for a given set   of size  , the set LIST  is small.


Expander Graphs

edit

Lets start with some definitions : For a bipartite graph   and a set  , define  . Also, a digraph   is a   vertex expander if for all sets   of at most   vertices, the neighborhood   is of size atleast   where neighborhood   s.t.  . Details can be found out in the paper Expander graphs and vertex expansion. This proves the following lemma:

Lemma- A graph   is a  expander if and only if for every set   of size at most   is of size at most  .


Construction

edit

Fix the field   and let  be an irreducible polynomial of degree   over the field  . Elements of   are univariate polynomials over   with degree at most  .  , integer parameter is fixed. The expander is bipartite graph   defined as:                   

The bipartite graph has message polynomials on the left and the   neighbor of   is the   symbol of Parvaresh-Vardy encoding of  . This follows a theorem which can formally be stated as:


Theorem 1: The graph   is a   expander for   and  .


Proof: Let us take any integer  , where   and let  . By the lemma defined above, if we take a   such that   is of at most   size, then we need to show that  .


Parvaresh-Vardy codes view degree   polynomials as elements of field   where   is an irreducible polynomial of degree  . We need   that will have non zero coefficients on monomials of the form   for   and  , where   and   is the base-  representation of  . If we impose a homogeneous linear constraint on   coefficients of  , then we require that   for every  . Since number of constraints is less than the number of unknowns, the linear system thus made has a solution that is not 0. If   has the smallest possible degree in variable  , then


                  

for univariate polynomials  , at least one of   will not be divisible by  . If every   is divisible by   then   will have smaller degree in   and would still vanish on   (since   is irreducible and therefore has no roots in  ).


Let us take   to be any polynomial. Then by our  ,    . This means, the univariate polynomial   has   zeroes. Since   has at most degree  , then it is  . Refer Polynomials and properties for proof. So,


 


Recall that, we have,  . Thus,   since  .


Then   which is an element of the extended field    where   is an irreducible polynomial of degree    is the root of univariate polynomial   over   defined by


  From equation  , the above equation is same as:

 

 


Since this is true for all  ,   has at least   roots in field  . Some  's is not divisible by  ,   is a non zero polynomial. Thus,   is bounded by the degree of  , which is at most  .


By proper instantiation of parameters in Theorem 1, we lead to following results:

Theorem 2: For all positive integers  ,  , all  , and all   for  , there is an explicit   expander   with degree   and  . Moreover,   and   are powers of  .


Theorem 3: For all positive integers  ,  , and all  , there is an explicit   expander   with degree   and  . Again,   and   are powers of  ..

The proofs of the above two theorems can be found from GUV paper.

References

edit
  1. Farzad Parvaresh and Alexander Vardy. Correcting errors beyond the Guruswami-Sudan radius in polynomial time In Proceedings of the 43nd Annual Symposium on Foundations of Computer Science (FOCS), pages 285-294, 2005.
  2. Atri Rudra. Error Correcting Codes: Combinatorics, Algorithms and Applications Lecture 41
  3. Madhu Sudan. Essential coding theory Lecture 15 and Lecture 16
  4. Unbalanced Expanders and Randomness Extractors from Parvaresh–Vardy Codes - GUV paper.
  5. Expander graphs.
  6. Expander graphs and vertex expansion.
  7. Bipartite graph.
  8. Digraph.
  9. Polynomials and their properties.
edit
  • This article incorporates text from a comparable page at the website of SUNY Buffalo