Content deleted Content added
Line 84:
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>.▼
▲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}}
Line 96 ⟶ 93:
: <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}▼
\begin{bmatrix}▼
\end{bmatrix} = \begin{bmatrix}
▲b_1 \\ b_2 \\ \vdots \\ b_{d-1}
0 \\ 0 \\ \vdots \\ 0▼
▲\begin{bmatrix}
▲0 \\ 0 \\ \vdots \\ 0
</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}}
| |||