Dual of BCH is an independent source explained
A certain family of BCH codes have a particularly useful property, which is thattreated 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
Let
be a linear code such that
has distance greater than
. Then
is an
-wise independent source.
Proof of lemma
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, thereis exactly one solution
, so the total number of solutions is exactly
, proving the lemma.
Corollary
Recall that BCH2,m,d is an
[n=2m,n-1-\lceil{d-2}/2\rceilm,d]2
linear code.
Let
be BCH
2,log n,ℓ+1. Then
is an
-wise independent source of size
.
Proof of corollary
The dimension d of C is just
\lceil{(\ell+1-2)/{2}}\rceillogn+1
. So
d=\lceil{(\ell-1)}/2\rceillogn+1=\lfloor\ell/2\rfloorlogn+1
.
So the cardinality of
considered as a set is just
, proving the Corollary.
References
Coding Theory notes at University at Buffalo
Coding Theory notes at MIT
