<p>(I'm not an expert in this subject, but here's my understanding.)</p>

<p>The <em>BCH code</em> 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 <a href="http://en.wikipedia.org/wiki/Polynomial_code" rel="nofollow">polynomial codes</a>).  The designed distance is a lower bound on the distance of the code.</p>

<p>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.</p>

<p>Here are some notes which describe the BCH code construction: <a href="http://www.uotiq.org/dep-eee/lectures/4th/Communication/Information%20theory/2.pdf" rel="nofollow">http://www.uotiq.org/dep-eee/lectures/4th/Communication/Information%20theory/2.pdf</a></p>

CC BY-SA 3.0
2011-12-13T16:16:56.687Z
@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".
Jyrki Lahtonen
CC BY-SA 3.0
2017-07-05T15:46:28.043Z
@arnab The link appears to have died. Do you have another location?
Thomas Ahle
CC BY-SA 2.5
2010-08-26T18:21:33.280Z
2010-08-26T18:21:33.280Z
arnab
<p>The <a href="http://portal.acm.org/citation.cfm?id=1347083" rel="noreferrer">SODA 2008 Ailon-Liberty paper</a> on fast Johnson-Lindenstrauss transforms uses a "dual BCH code of design distance 5" as part of the construction. They cite the 
<a href="http://rads.stackoverflow.com/amzn/click/0444851933" rel="noreferrer">MacWilliams-Sloane book on error-correcting codes</a> 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...)</p>

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

<coding-theory>
Dual BCH codes of design distance $d$
Suresh Venkat
# Dual BCH codes of design distance $d$

(Asked by: username_0 on 2010-08-24)

The [SODA 2008 Ailon-Liberty paper](http://portal.acm.org/citation.cfm?id=1347083) 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](http://rads.stackoverflow.com/amzn/click/0444851933) 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$ ?

**Tags:** coding-theory

---

## 1 answers

### Answer by username_1 on 2010-08-26. Score: 4 | Accepted answer

(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](http://en.wikipedia.org/wiki/Polynomial_code)). 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>

> **Comments:**
> **username_2**: @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".  
> **username_3**: @arnab The link appears to have died. Do you have another location?  

---

