# Dual BCH codes of design distance $d$

The SODA 2008 Ailon-Liberty paper on fast Johnson-Lindenstrauss transforms uses a "dual BCH code of design distance 5" as part of the construction. They cite the MacWilliams-Sloane book on error-correcting codes as the source for how to construct these codes, but my initial wading through the book doesn't appear to yield the answer (there are dual codes and BCH codes, but...)

Is there an easy way to describe how to construct such a matrix, for general matrix dimensions $m \times d$ ?

The BCH code of code length $n=2^m-1$ and designed distance $2t+1$ is specified in terms of its generator polynomial. Fix $\alpha$ to be a primitive element of $GF(2^m)$. Then, $g$ is the polynomial of smallest degree with coefficients in $GF(2)$ which has its roots $\alpha, \alpha^2,\alpha^3,\dots,\alpha^{2t}$. (The codewords are then given by all multiples of $g$ of degree at most $n-1$; see the wikipedia page for polynomial codes). The designed distance is a lower bound on the distance of the code.
The dual BCH code of design distance $2t+1$ is just the dual of the BCH code in the usual sense, the set of vectors orthogonal to the codewords of the BCH code of design distance $2t+1$. Its generator polynomial is given by $(X^n+1)/g(X)$. I believe the matrix in the Ailon-Liberty paper has the codewords as its rows.
• @SureshVenkat: Observe that arnab's formula only works, when you consider BCH codes of full length $n=2^m-1$. Otherwise even the dimension of the code will be wrong :-) If you are using shortened BCH-codes (or truncated), in addition to that result you need to use the fact that taking the dual swaps the meanings of "shortened" and "punctured". Commented Dec 13, 2011 at 16:16