Editing BCH code (section)

== Definition and illustration ==

=== 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]]).

=== General BCH codes ===
General BCH codes differ from primitive narrow-sense BCH codes in two respects.

First, the requirement that <math>\alpha</math> be a primitive element of <math>\mathrm{GF}(q^m)</math> can be relaxed. By relaxing this requirement, the code length changes from <math>q^m - 1</math> to <math>\mathrm{ord}(\alpha),</math> the [[Order (group theory)|order]] of the element <math>\alpha.</math>

Second, the consecutive roots of the generator polynomial may run from <math>\alpha^c,\ldots,\alpha^{c+d-2}</math> instead of <math>\alpha,\ldots,\alpha^{d-1}.</math>

'''Definition.''' Fix a finite field <math>GF(q),</math> where <math>q</math> is a prime power. Choose positive integers <math>m,n,d,c</math> such that <math>2\leq d\leq n,</math> <math>{\rm gcd}(n,q)=1,</math>  and <math>m</math> is the [[multiplicative order]] of <math>q</math> modulo <math>n.</math>

As before, let <math>\alpha</math> be a [[primitive nth root of unity|primitive <math>n</math>th root of unity]] in <math>GF(q^m),</math> and let <math>m_i(x)</math> be the [[minimal polynomial (field theory)|minimal polynomial]] over <math>GF(q)</math> of <math>\alpha^i</math> for all <math>i.</math>
The generator polynomial of the BCH code is defined as the [[least common multiple]] <math>g(x) = {\rm lcm}(m_c(x),\ldots,m_{c+d-2}(x)).</math>

'''Note:''' if <math>n=q^m-1</math> as in the simplified definition, then <math>{\rm gcd}(n,q)</math> is 1, and the order of <math>q</math> modulo <math>n</math> is <math>m.</math>
Therefore, the simplified definition is indeed a special case of the general one.

=== Special cases ===
* A BCH code with <math>c=1</math> is called a ''narrow-sense BCH code''.
* A BCH code with <math>n=q^m-1</math> is called ''primitive''.

The generator polynomial <math>g(x)</math> of a BCH code has coefficients from <math>\mathrm{GF}(q).</math>
In general, a cyclic code over <math>\mathrm{GF}(q^p)</math> with <math>g(x)</math> as the generator polynomial is called a BCH code over <math>\mathrm{GF}(q^p).</math>
The BCH code over <math>\mathrm{GF}(q^m)</math> and generator polynomial <math>g(x)</math> with successive powers of <math>\alpha</math> as roots is one type of [[Reed–Solomon code]] where the decoder (syndromes) alphabet is the same as the channel (data and generator polynomial) alphabet, all elements of <math>\mathrm{GF}(q^m)</math> .<ref>{{Harvnb|Gill|n.d.|p=3}}</ref> The other type of Reed Solomon code is an [[Reed–Solomon error correction#Reed & Solomon's original view: The codeword as a sequence of values|original view Reed Solomon code]] which is not a BCH code.