Dual of BCH is an independent source

A certain family of BCH codes have a particularly useful property, which is that treated as linear operators, their dual operators turns their input into an -wise independent source. That is, the set of vectors from the input vector space are mapped to an -wise independent source. The proof of this fact below as the following Lemma and Corollary is useful in derandomizing the algorithm for a -approximation to MAXEkSAT.

Lemma

edit

Let   be a linear code such that   has distance greater than  . Then   is an  -wise independent source.

Proof of lemma

edit

It is sufficient to show that given any   matrix M, where k is greater than or equal to l, such that the rank of M is l, for all  ,   takes every value in   the same number of times.

Since M has rank l, we can write M as two matrices of the same size,   and  , where   has rank equal to l. This means that   can be rewritten as   for some   and  .

If we consider M written with respect to a basis where the first l rows are the identity matrix, then   has zeros wherever   has nonzero rows, and   has zeros wherever   has nonzero rows.

Now any value y, where  , can be written as   for some vectors  .

We can rewrite this as:

 

Fixing the value of the last   coordinates of   (note that there are exactly   such choices), we can rewrite this equation again as:

  for some b.

Since   has rank equal to l, there is exactly one solution  , so the total number of solutions is exactly  , proving the lemma.

Corollary

edit

Recall that BCH2,m,d is an   linear code.

Let   be BCH2,log n,+1. Then   is an  -wise independent source of size  .

Proof of corollary

edit

The dimension d of C is just  . So  .

So the cardinality of   considered as a set is just  , proving the Corollary.

References

edit

Coding Theory notes at University at Buffalo

Coding Theory notes at MIT