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 \ell-wise independent source. That is, the set of vectors from the input vector space are mapped to an \ell-wise independent source. The proof of this fact below as the following Lemma and Corollary is useful in derandomizing the algorithm for a 1-2^{-\ell}-approximation to MAXEkSAT.

Lemma

Let C\subseteq F_2^n be a linear code such that C^\perp has distance greater than  \ell +1. Then C is an \ell-wise independent source.

Proof of Lemma

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

Since M has rank l, we can write M as two matrices of the same size, M_1 and M_2, where M_1 has rank equal to l. This means that xM can be rewritten as x_1M_1 + x_2M_2 for some x_1 and x_2.

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

Now any value y, where y=xM, can be written as x_1M_1+x_2M_2 for some vectors x_1, x_2.

We can rewrite this as:

x_1M_1 = y - x_2M_2

Fixing the value of the last k-l coordinates of x_2\in F_2^k (note that there are exactly 2^{k-l} such choices), we can rewrite this equation again as:

x_1M_1 = b for some b.

Since M_1 has rank equal to l, there is exactly one solution x_1, so the total number of solutions is exactly 2^{k-l}, proving the lemma.

Corollary

Recall that BCH2,m,d is an  [n=2^m, n-1 -\lceil {d-2}/2\rceil m, d]_2 linear code.

Let C^\perp be BCH2,log n,+1. Then C is an \ell-wise independent source of size O(n^{\lfloor \ell/2 \rfloor}).

Proof of Corollary

The dimension d of C is just \lceil{(\ell +1 -2)/{2}}\rceil \log n +1 . So d = \lceil {(\ell -1)}/2\rceil \log n +1 = \lfloor \ell/2 \rfloor \log n +1.

So the cardinality of C considered as a set is just  2^{d}=O(n^{\lfloor \ell/2 \rfloor}), proving the Corollary.

References

Coding Theory notes at University at Buffalo

Coding Theory notes at MIT

This article is issued from Wikipedia - version of the Sunday, November 29, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.