Editing BCH code (section)

=== Primitive narrow-sense BCH codes ===
Given a [[prime number]] {{mvar|q}} and [[prime power]] {{math|''q''<sup>''m''</sup>}} with positive integers {{mvar|m}} and {{mvar|d}} such that {{math|''d'' ≤ ''q''<sup>''m''</sup> − 1}}, a primitive narrow-sense BCH code over the [[finite field]] (or Galois field) {{math|GF(''q'')}} with code length {{math|''n'' {{=}} ''q''<sup>''m''</sup> − 1}} and [[Block code#The distance d|distance]] at least {{mvar|d}} is constructed by the following method.

Let {{mvar|α}} be a [[Simple extension#Definition|primitive element]] of {{math|GF(''q''<sup>''m''</sup>)}}.
For any positive integer {{mvar|i}}, let {{math|''m''<sub>''i''</sub>(''x'')}} be the [[minimal polynomial (field theory)|minimal polynomial]] with coefficients in {{math|GF(''q'')}} of {{math|α<sup>''i''</sup>}}.
The [[generator polynomial]] of the BCH code is defined as the [[least common multiple]] {{math|''g''(''x'') {{=}} lcm(''m''<sub>1</sub>(''x''),…,''m''<sub>''d'' − 1</sub>(''x''))}}.
It can be seen that {{math|''g''(''x'')}} is a polynomial with coefficients in {{math|GF(''q'')}} and divides {{math|''x''<sup>''n''</sup> − 1}}.
Therefore, the [[polynomial code]] defined by {{math|''g''(''x'')}} is a cyclic code.

==== Example ====
Let {{math|''q'' {{=}} 2}} and {{math|''m'' {{=}} 4}} (therefore {{math|''n'' {{=}} 15}}). We will consider different values of {{mvar|d}} for {{math|GF(16) {{=}} GF(2<sup>4</sup>)}} based on the reducing polynomial {{math|''z''<sup>4</sup> + ''z'' + 1}}, using primitive element {{math|''α''(''z'') {{=}} ''z''}}. There are fourteen minimum polynomials {{math|''m''<sub>''i''</sub>(''x'')}} with coefficients in {{math|GF(2)}} satisfying
:<math>m_i\left(\alpha^i\right) \bmod \left(z^4 + z + 1\right) = 0.</math>

The minimal polynomials are
:<math>\begin{align}
  m_1(x) &= m_2(x) = m_4(x) = m_8(x) = x^4 + x + 1, \\
  m_3(x) &= m_6(x) = m_9(x) = m_{12}(x) = x^4 + x^3 + x^2 + x + 1, \\
  m_5(x) &= m_{10}(x) = x^2 + x + 1, \\
  m_7(x) &= m_{11}(x) = m_{13}(x) = m_{14}(x) = x^4 + x^3 + 1.
\end{align}</math>

The BCH code with <math>d = 2, 3</math> has the generator polynomial
:<math>g(x) = {\rm lcm}(m_1(x), m_2(x)) = m_1(x) = x^4 + x + 1.\,</math>

It has minimal [[Hamming distance]] at least 3 and corrects up to one error. Since the generator polynomial is of degree 4, this code has 11 data bits and 4 checksum bits. It is also denoted as: '''(15, 11) BCH''' code.

The BCH code with <math>d=4,5</math> has the generator polynomial
:<math>\begin{align}
  g(x) &= {\rm lcm}(m_1(x),m_2(x),m_3(x),m_4(x)) = m_1(x) m_3(x) \\
       &= \left(x^4 + x + 1\right)\left(x^4 + x^3 + x^2 + x + 1\right) = x^8 + x^7 + x^6 + x^4 + 1.
\end{align}</math>

It has minimal Hamming distance at least 5 and corrects up to two errors. Since the generator polynomial is of degree 8, this code has 7 data bits and 8 checksum bits. It is also denoted as: '''(15, 7) BCH''' code.

The BCH code with <math>d=6,7</math> has the generator polynomial
:<math>\begin{align}
  g(x) &= {\rm lcm}(m_1(x),m_2(x),m_3(x),m_4(x),m_5(x),m_6(x)) = m_1(x) m_3(x) m_5(x) \\
       &= \left(x^4 + x + 1\right)\left(x^4 + x^3 + x^2 + x + 1\right)\left(x^2 + x + 1\right) = x^{10} + x^8 + x^5 + x^4 + x^2 + x + 1.
\end{align}</math>

It has minimal Hamming distance at least 7 and corrects up to three errors. Since the generator polynomial is of degree 10, this code has 5 data bits and 10 checksum bits. It is also denoted as: '''(15, 5) BCH''' code. (This particular generator polynomial has a real-world application, in the "format information" of the [[QR code]].)

The BCH code with <math>d=8</math> and higher has the generator polynomial
:<math>\begin{align}
  g(x) &= {\rm lcm}(m_1(x),m_2(x),...,m_{14}(x))  = m_1(x) m_3(x) m_5(x) m_7(x)\\
       &= \left(x^4 + x + 1\right)\left(x^4 + x^3 + x^2 + x + 1\right)\left(x^2 + x + 1\right)\left(x^4 + x^3 + 1\right) = x^{14} + x^{13} + x^{12} + \cdots + x^2 + x + 1.
\end{align}</math>

This code has minimal Hamming distance 15 and corrects 7 errors. It has 1 data bit and 14 checksum bits. It is also denoted as: '''(15, 1) BCH''' code. In fact, this code has only two codewords: 000000000000000 and 111111111111111 (a trivial [[repetition code]]).