Dual of BCH is an independent source

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.


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.


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.


Coding Theory notes at University at Buffalo

Coding Theory notes at MIT