Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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$ ?
(I'm not an expert in this subject, but here's my understanding.)
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.
Here are some notes which describe the BCH code construction: http://www.uotiq.org/dep-eee/lectures/4th/Communication/Information%20theory/2.pdf
