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
be a linear code such that
has distance greater than
-wise independent source.
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
the same number of times.
Since M has rank l, we can write M as two matrices of the same size,
has rank equal to l. This means that
If we consider M written with respect to a basis where the first l rows are the identity matrix, then
has nonzero rows, and
has nonzero rows.
for some vectors
such choices), we can rewrite this equation again as:
has rank equal to l, there is exactly one solution
, so the total number of solutions is exactly
, proving the lemma.
linear code.
ℓ
-wise independent source of size
⌊ ℓ
2 ⌉ log n + 1 = ⌊ ℓ
considered as a set is just
, proving the Corollary.
Coding Theory notes at University at Buffalo Coding Theory notes at MIT