Editing BCH code (section)

== Properties ==
The generator polynomial of a BCH code has degree at most <math>(d-1)m</math>. Moreover, if <math>q=2</math> and <math>c=1</math>, the generator polynomial has degree at most <math>dm/2</math>.
{{Collapse top|title=Proof}}
Each minimal polynomial <math>m_i(x)</math> has degree at most <math>m</math>. Therefore, the least common multiple of <math>d-1</math> of them has degree at most <math>(d-1)m</math>. Moreover, if <math>q=2,</math> then <math>m_i(x) = m_{2i}(x)</math> for all <math>i</math>. Therefore, <math>g(x)</math> is the least common multiple of at most <math>d/2</math> minimal polynomials <math>m_i(x)</math> for odd indices <math>i,</math> each of degree at most <math>m</math>.
{{Collapse bottom}}

A BCH code has minimal Hamming distance at least <math>d</math>.
{{Collapse top|title=Proof}}
Suppose that <math>p(x)</math> is a code word with fewer than <math>d</math> non-zero terms. Then

: <math>p(x) = b_1x^{k_1} + \cdots + b_{d-1}x^{k_{d-1}},\text{ where }k_1<k_2<\cdots<k_{d-1}.</math>

Recall that <math>\alpha^c,\ldots,\alpha^{c+d-2}</math> are roots of <math>g(x),</math> hence of <math>p(x)</math>. This implies that <math>b_1,\ldots,b_{d-1}</math> satisfy the following equations, for each <math>i \in \{c, \dotsc, c+d-2\}</math>:

: <math>p(\alpha^i) = b_1\alpha^{ik_1} + b_2\alpha^{ik_2} + \cdots + b_{d-1}\alpha^{ik_{d-1}} = 0.</math>

In matrix form, we have
: <math>\begin{bmatrix}
          \alpha^{ck_1} &       \alpha^{ck_2} & \cdots &       \alpha^{ck_{d-1}} \\
      \alpha^{(c+1)k_1} &   \alpha^{(c+1)k_2} & \cdots &   \alpha^{(c+1)k_{d-1}} \\
                 \vdots &              \vdots &        &                  \vdots \\
    \alpha^{(c+d-2)k_1} & \alpha^{(c+d-2)k_2} & \cdots & \alpha^{(c+d-2)k_{d-1}} \\
  \end{bmatrix}\begin{bmatrix}
    b_1 \\ b_2 \\ \vdots \\ b_{d-1}
  \end{bmatrix} = \begin{bmatrix}
    0 \\ 0 \\ \vdots \\ 0
  \end{bmatrix}.
</math>

The determinant of this matrix equals
:<math>\left(\prod_{i=1}^{d-1}\alpha^{ck_i}\right)\det\begin{pmatrix}
                  1 &                 1 & \cdots &                     1 \\
       \alpha^{k_1} &      \alpha^{k_2} & \cdots &      \alpha^{k_{d-1}} \\
             \vdots &            \vdots &        &                \vdots \\
  \alpha^{(d-2)k_1} & \alpha^{(d-2)k_2} & \cdots & \alpha^{(d-2)k_{d-1}} \\
\end{pmatrix} = \left(\prod_{i=1}^{d-1}\alpha^{ck_i}\right) \det(V).</math>

The matrix <math>V</math> is seen to be a [[Vandermonde matrix]], and its determinant is
:<math>\det(V) = \prod_{1\le i<j\le d-1} \left(\alpha^{k_j} - \alpha^{k_i}\right),</math>
which is non-zero. It therefore follows that <math>b_1,\ldots,b_{d-1}=0,</math> hence <math>p(x) = 0.</math>
{{Collapse bottom}}

A BCH code is cyclic.
{{Collapse top|title=Proof}}
A polynomial code of length <math>n</math> is cyclic if and only if its generator polynomial divides <math>x^n-1.</math> Since <math>g(x)</math> is the minimal polynomial with roots <math>\alpha^c,\ldots,\alpha^{c+d-2},</math> it suffices to check that each of <math>\alpha^c,\ldots,\alpha^{c+d-2}</math> is a root of <math>x^n-1.</math> This follows immediately from the fact that <math>\alpha</math> is, by definition, an <math>n</math>th root of unity.
{{Collapse bottom}}