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$ ?


1 Answer 1


(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

  • 1
    $\begingroup$ @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". $\endgroup$ Commented Dec 13, 2011 at 16:16
  • 1
    $\begingroup$ @arnab The link appears to have died. Do you have another location? $\endgroup$ Commented Jul 5, 2017 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.