Editing BCH code (section)

===Decoding examples===

==== Decoding of binary code without unreadable characters ====
Consider a BCH code in GF(2<sup>4</sup>) with <math>d=7</math> and <math>g(x) = x^{10} + x^8 + x^5 + x^4 + x^2 + x + 1</math>. (This is used in [[QR code]]s.) Let the message to be transmitted be <nowiki>[1 1 0 1 1]</nowiki>, or in polynomial notation, <math>M(x) = x^4 + x^3 + x + 1.</math>
The "checksum" symbols are calculated by dividing <math>x^{10} M(x)</math> by <math>g(x)</math> and taking the remainder, resulting in <math>x^9 + x^4 + x^2</math> or <nowiki>[ 1 0 0 0 0 1 0 1 0 0 ]</nowiki>. These are appended to the message, so the transmitted codeword is <nowiki>[ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 ]</nowiki>.

Now, imagine that there are two bit-errors in the transmission, so the received codeword is [ 1 {{color|red|0}} 0 1 1 1 0 0 0 {{color|red|1}} 1 0 1 0 0 ]. In polynomial notation:
:<math>R(x) = C(x) + x^{13} + x^5 = x^{14} + x^{11} + x^{10} + x^9 + x^5 + x^4 + x^2</math>
In order to correct the errors, first calculate the syndromes. Taking <math>\alpha = 0010,</math> we have <math>s_1 = R(\alpha^1) = 1011,</math> <math>s_2 = 1001,</math> <math>s_3 = 1011,</math> <math>s_4 = 1101,</math> <math>s_5 = 0001,</math> and <math>s_6 = 1001.</math>
Next, apply the Peterson procedure by row-reducing the following augmented matrix.
:<math>\left [ S_{3 \times 3} | C_{3 \times 1} \right ] =
\begin{bmatrix}s_1&s_2&s_3&s_4\\
s_2&s_3&s_4&s_5\\
s_3&s_4&s_5&s_6\end{bmatrix} =
\begin{bmatrix}1011&1001&1011&1101\\
1001&1011&1101&0001\\
1011&1101&0001&1001\end{bmatrix} \Rightarrow
\begin{bmatrix}0001&0000&1000&0111\\
0000&0001&1011&0001\\
0000&0000&0000&0000
\end{bmatrix}</math>
Due to the zero row, {{math|''S''<sub>3×3</sub>}} is singular, which is no surprise since only two errors were introduced into the codeword.
However, the upper-left corner of the matrix is identical to {{closed-closed|''S''<sub>2×2</sub> <nowiki>|</nowiki> ''C''<sub>2×1</sub>}}, which gives rise to the solution <math>\lambda_2 = 1000,</math> <math>\lambda_1 = 1011.</math>
The resulting error locator polynomial is <math>\Lambda(x) = 1000 x^2 + 1011 x + 0001,</math> which has zeros at <math>0100 = \alpha^{-13}</math> and <math>0111 = \alpha^{-5}.</math>
The exponents of <math>\alpha</math> correspond to the error locations.
There is no need to calculate the error values in this example, as the only possible value is 1.

==== Decoding with unreadable characters ====
Suppose the same scenario, but the received word has two unreadable characters [ 1 {{color|red|0}} 0 ? 1 1 ? 0 0 {{color|red|1}} 1 0 1 0 0 ]. We replace the unreadable characters by zeros while creating the polynomial reflecting their positions <math>\Gamma(x) = \left(\alpha^8x - 1\right)\left(\alpha^{11}x - 1\right).</math> We compute the syndromes <math>s_1=\alpha^{-7}, s_2=\alpha^{1}, s_3=\alpha^{4}, s_4=\alpha^{2}, s_5=\alpha^{5},</math> and <math>s_6=\alpha^{-7}.</math> (Using log notation which is independent on GF(2<sup>4</sup>) isomorphisms. For computation checking we can use the same representation for addition as was used in previous example. Hexadecimal description of the powers of <math>\alpha</math> are consecutively 1,2,4,8,3,6,C,B,5,A,7,E,F,D,9 with the addition based on bitwise xor.)

Let us make syndrome polynomial

:<math>S(x)=\alpha^{-7}+\alpha^{1}x+\alpha^{4}x^2+\alpha^{2}x^3+\alpha^{5}x^4+\alpha^{-7}x^5,</math>

compute

:<math>S(x)\Gamma(x)=\alpha^{-7}+\alpha^{4}x+\alpha^{-1}x^2+\alpha^{6}x^3+\alpha^{-1}x^4+\alpha^{5}x^5+\alpha^{7}x^6+\alpha^{-3}x^7.</math>

Run the extended Euclidean algorithm:

:<math>\begin{align}
      &\begin{pmatrix}S(x)\Gamma(x)\\ x^6\end{pmatrix} \\ [6pt]
  ={} &\begin{pmatrix}\alpha^{-7} +\alpha^{4}x+ \alpha^{-1}x^2+ \alpha^{6}x^3+ \alpha^{-1}x^4+ \alpha^{5}x^5 +\alpha^{7}x^6+ \alpha^{-3}x^7 \\ x^6\end{pmatrix} \\ [6pt]
  ={} &\begin{pmatrix}\alpha^{7}+ \alpha^{-3}x & 1\\ 1 & 0\end{pmatrix}
       \begin{pmatrix}x^6\\ \alpha^{-7} +\alpha^{4}x +\alpha^{-1}x^2 +\alpha^{6}x^3 +\alpha^{-1}x^4 +\alpha^{5}x^5 +2\alpha^{7}x^6 +2\alpha^{-3}x^7\end{pmatrix} \\ [6pt]
  ={} &\begin{pmatrix}\alpha^{7}+ \alpha^{-3}x & 1\\ 1 & 0\end{pmatrix}
       \begin{pmatrix}\alpha^4 + \alpha^{-5}x & 1\\ 1 & 0\end{pmatrix} \\
      &\qquad \begin{pmatrix}\alpha^{-7}+ \alpha^{4}x+ \alpha^{-1}x^2+ \alpha^{6}x^3+ \alpha^{-1}x^4+ \alpha^{5}x^5\\ \alpha^{-3} +\left(\alpha^{-7}+ \alpha^{3}\right)x+ \left(\alpha^{3}+ \alpha^{-1}\right)x^2+ \left(\alpha^{-5}+ \alpha^{-6}\right)x^3+ \left(\alpha^3+ \alpha^{1}\right)x^4+ 2\alpha^{-6}x^5+ 2x^6\end{pmatrix} \\ [6pt]
  ={} &\begin{pmatrix}\left(1+ \alpha^{-4}\right)+ \left(\alpha^{1}+ \alpha^{2}\right)x+ \alpha^{7}x^2 & \alpha^{7}+ \alpha^{-3}x \\ \alpha^4+ \alpha^{-5}x & 1\end{pmatrix}
       \begin{pmatrix}\alpha^{-7}+ \alpha^{4}x+ \alpha^{-1}x^2+ \alpha^{6}x^3+ \alpha^{-1}x^4+ \alpha^{5}x^5\\ \alpha^{-3}+ \alpha^{-2}x+ \alpha^{0}x^2+ \alpha^{-2}x^3+ \alpha^{-6}x^4\end{pmatrix} \\ [6pt]
  ={} &\begin{pmatrix}\alpha^{-3}+ \alpha^{5}x+ \alpha^{7}x^2 & \alpha^{7}+ \alpha^{-3}x \\ \alpha^4+ \alpha^{-5}x & 1\end{pmatrix}
       \begin{pmatrix}\alpha^{-5}+ \alpha^{-4}x & 1\\ 1 & 0 \end{pmatrix} \\
      &\qquad \begin{pmatrix}\alpha^{-3}+ \alpha^{-2}x+ \alpha^{0}x^2+ \alpha^{-2}x^3+ \alpha^{-6}x^4\\ \left(\alpha^{7}+ \alpha^{-7}\right)+ \left(2\alpha^{-7}+ \alpha^{4}\right)x+ \left(\alpha^{-5}+ \alpha^{-6}+ \alpha^{-1}\right)x^2+ \left(\alpha^{-7}+ \alpha^{-4}+ \alpha^{6}\right)x^3+ \left(\alpha^{4}+ \alpha^{-6}+ \alpha^{-1}\right)x^4+ 2\alpha^{5}x^5\end{pmatrix} \\ [6pt]
  ={} &\begin{pmatrix}\alpha^{7}x+ \alpha^{5}x^2+ \alpha^{3}x^3 & \alpha^{-3}+ \alpha^{5}x+ \alpha^{7}x^2\\ \alpha^{3}+ \alpha^{-5}x+ \alpha^{6}x^2 & \alpha^4+ \alpha^{-5}x\end{pmatrix}
       \begin{pmatrix}\alpha^{-3}+ \alpha^{-2}x+ \alpha^{0}x^2+ \alpha^{-2}x^3+ \alpha^{-6}x^4\\ \alpha^{-4}+ \alpha^{4}x+ \alpha^{2}x^2+ \alpha^{-5}x^3\end{pmatrix}.
\end{align}</math>

We have reached polynomial of degree at most 3, and as

:<math>\begin{pmatrix}-\left(\alpha^4+ \alpha^{-5}x\right) & \alpha^{-3}+ \alpha^{5}x+ \alpha^{7}x^2\\ \alpha^{3}+ \alpha^{-5}x+ \alpha^{6}x^2 & -\left(\alpha^{7}x+ \alpha^{5}x^2+ \alpha^{3}x^3\right)\end{pmatrix} \begin{pmatrix}\alpha^{7}x+ \alpha^{5}x^2+ \alpha^{3}x^3 & \alpha^{-3} + \alpha^{5}x + \alpha^{7}x^2\\ \alpha^{3} + \alpha^{-5}x + \alpha^{6}x^2 & \alpha^4 + \alpha^{-5}x\end{pmatrix} = \begin{pmatrix}1 & 0\\ 0 & 1\end{pmatrix},</math>

we get

:<math>\begin{pmatrix}-\left(\alpha^4+ \alpha^{-5}x\right) & \alpha^{-3}+ \alpha^{5}x+ \alpha^{7}x^2\\ \alpha^{3}+ \alpha^{-5}x+ \alpha^{6}x^2 & -\left(\alpha^{7}x+ \alpha^{5}x^2+ \alpha^{3}x^3\right)\end{pmatrix}
\begin{pmatrix}S(x)\Gamma(x)\\ x^6\end{pmatrix} = \begin{pmatrix}\alpha^{-3}+ \alpha^{-2}x+ \alpha^{0}x^2+ \alpha^{-2}x^3+ \alpha^{-6}x^4\\ \alpha^{-4}+ \alpha^{4}x+ \alpha^{2}x^2+ \alpha^{-5}x^3\end{pmatrix}. </math>

Therefore,

:<math>S(x)\Gamma(x)\left(\alpha^{3} + \alpha^{-5}x + \alpha^{6}x^2\right) - \left(\alpha^{7}x + \alpha^{5}x^2 + \alpha^{3}x^3\right)x^6 = \alpha^{-4} + \alpha^{4}x + \alpha^{2}x^2 + \alpha^{-5}x^3.</math>

Let <math>\Lambda(x) = \alpha^{3}+ \alpha^{-5}x+ \alpha^{6}x^2.</math> Don't worry that <math>\lambda_0\neq 1.</math> Find by brute force a root of <math>\Lambda.</math> The roots are <math>\alpha^2,</math> and <math>\alpha^{10}</math> (after finding for example <math>\alpha^2</math> we can divide <math>\Lambda</math> by corresponding monom <math>\left(x - \alpha^2\right)</math> and the root of resulting monom could be found easily).

Let

:<math>\begin{align}
     \Xi(x) &= \Gamma(x)\Lambda(x) = \alpha^3 + \alpha^4x^2 + \alpha^2x^3 + \alpha^{-5}x^4 \\
  \Omega(x) &= S(x)\Xi(x) \equiv \alpha^{-4} + \alpha^4x + \alpha^2x^2 + \alpha^{-5}x^3 \bmod{x^6}
\end{align}</math>

Let us look for error values using formula

:<math>e_j = -\frac{\Omega \left(\alpha^{-i_j} \right)}{\Xi' \left(\alpha^{-i_j} \right)},</math>

where <math>\alpha^{-i_j}</math> are roots of <math>\Xi(x).</math> <math>\Xi'(x)=\alpha^{2}x^2.</math> We get

:<math>\begin{align}
  e_1 &=-\frac{\Omega(\alpha^4)}{\Xi'(\alpha^{4})} = \frac{\alpha^{-4}+\alpha^{-7}+\alpha^{-5}+\alpha^{7}}{\alpha^{-5}} =\frac{\alpha^{-5}}{\alpha^{-5}}=1 \\
  e_2 &=-\frac{\Omega(\alpha^7)}{\Xi'(\alpha^{7})} = \frac{\alpha^{-4}+\alpha^{-4}+\alpha^{1}+\alpha^{1}}{\alpha^{1}}=0 \\
  e_3 &=-\frac{\Omega(\alpha^{10})}{\Xi'(\alpha^{10})} = \frac{\alpha^{-4}+\alpha^{-1}+\alpha^{7}+\alpha^{-5}}{\alpha^{7}}=\frac{\alpha^{7}}{\alpha^{7}}=1 \\
  e_4 &=-\frac{\Omega(\alpha^{2})}{\Xi'(\alpha^{2})} = \frac{\alpha^{-4}+\alpha^{6}+\alpha^{6}+\alpha^{1}}{\alpha^{6}}=\frac{\alpha^{6}}{\alpha^{6}}=1
\end{align}</math>

Fact, that <math>e_3=e_4=1,</math> should not be surprising.

Corrected code is therefore [ 1 {{color|green|1}} 0 {{color|green|1}} 1 1 {{color|green|0}} 0 0 {{color|green|0}} 1 0 1 0 0].

==== Decoding with unreadable characters with a small number of errors ====
Let us show the algorithm behaviour for the case with small number of errors. Let the received word is [ 1 {{color|red|0}} 0 ? 1 1 ? 0 0 0 1 0 1 0 0 ].

Again, replace the unreadable characters by zeros while creating the polynomial reflecting their positions <math>\Gamma(x) = \left(\alpha^{8}x - 1\right)\left(\alpha^{11}x - 1\right).</math>
Compute the syndromes <math>s_1 = \alpha^{4}, s_2 = \alpha^{-7}, s_3 = \alpha^{1}, s_4 = \alpha^{1}, s_5 = \alpha^{0},</math> and <math>s_6 = \alpha^{2}.</math>
Create syndrome polynomial

:<math>\begin{align}
           S(x) &= \alpha^{4} + \alpha^{-7}x + \alpha^{1}x^2 + \alpha^{1}x^3 + \alpha^{0}x^4 + \alpha^{2}x^5, \\
  S(x)\Gamma(x) &= \alpha^{4} + \alpha^{7}x + \alpha^{5}x^2 + \alpha^{3}x^3 + \alpha^{1}x^4 + \alpha^{-1}x^5 + \alpha^{-1}x^6 + \alpha^{6}x^7.
\end{align}</math>

Let us run the extended Euclidean algorithm:

:<math>\begin{align}
  \begin{pmatrix}
    S(x)\Gamma(x) \\
    x^6
  \end{pmatrix}
    &= \begin{pmatrix}
         \alpha^{4} + \alpha^{7}x + \alpha^{5}x^2 + \alpha^{3}x^3 + \alpha^{1}x^4 + \alpha^{-1}x^5 + \alpha^{-1}x^6 + \alpha^{6}x^7 \\
         x^6
       \end{pmatrix} \\
    &= \begin{pmatrix}
         \alpha^{-1} + \alpha^{6}x & 1 \\
                                 1 & 0
       \end{pmatrix} \begin{pmatrix}
         x^6 \\
         \alpha^{4} + \alpha^{7}x + \alpha^{5}x^2 + \alpha^{3}x^3 + \alpha^{1}x^4 + \alpha^{-1}x^5 + 2\alpha^{-1}x^6 + 2\alpha^{6}x^7
       \end{pmatrix} \\
    &= \begin{pmatrix}
         \alpha^{-1} + \alpha^{6}x & 1 \\
                                 1 & 0
       \end{pmatrix} \begin{pmatrix}
         \alpha^{3} + \alpha^{1}x & 1 \\
                                1 & 0
       \end{pmatrix} \begin{pmatrix}
         \alpha^{4} + \alpha^{7}x + \alpha^{5}x^2 + \alpha^{3}x^3 + \alpha^{1}x^4 + \alpha^{-1}x^5 \\
         \alpha^{7} + \left(\alpha^{-5} + \alpha^{5}\right)x + 2\alpha^{-7}x^2 + 2\alpha^{6}x^3 +  2\alpha^{4}x^4 + 2\alpha^{2}x^5 + 2x^6
       \end{pmatrix} \\
    &= \begin{pmatrix}
         \left(1 + \alpha^{2}\right) + \left(\alpha^{0} + \alpha^{-6}\right)x + \alpha^{7}x^2 & \alpha^{-1} + \alpha^{6}x \\
         \alpha^{3} + \alpha^{1}x & 1
       \end{pmatrix} \begin{pmatrix}
         \alpha^{4} + \alpha^{7}x + \alpha^{5}x^2 + \alpha^{3}x^3 + \alpha^{1}x^4 + \alpha^{-1}x^5 \\
         \alpha^{7} + \alpha^{0}x
       \end{pmatrix}
\end{align}</math>

We have reached polynomial of degree at most 3, and as
: <math>
  \begin{pmatrix}
                          -1 & \alpha^{-1} + \alpha^{6}x \\
    \alpha^{3} + \alpha^{1}x & -\left(\alpha^{-7} + \alpha^{7}x + \alpha^{7}x^2\right)
  \end{pmatrix} \begin{pmatrix}
    \alpha^{-7} + \alpha^{7}x + \alpha^{7}x^2 & \alpha^{-1} + \alpha^{6}x \\
                     \alpha^{3} + \alpha^{1}x & 1
  \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix},
</math>
we get
: <math>
  \begin{pmatrix}
                          -1 & \alpha^{-1} + \alpha^{6}x \\
    \alpha^{3} + \alpha^{1}x & -\left(\alpha^{-7} + \alpha^{7}x + \alpha^{7}x^2\right)
  \end{pmatrix}\begin{pmatrix}
    S(x)\Gamma(x) \\ x^6
  \end{pmatrix} = \begin{pmatrix}
    \alpha^{4} + \alpha^{7}x + \alpha^{5}x^2 + \alpha^{3}x^3 + \alpha^{1}x^4 + \alpha^{-1}x^5 \\
    \alpha^{7} + \alpha^{0}x
  \end{pmatrix}.
</math>

Therefore,
: <math>S(x)\Gamma(x)\left(\alpha^{3} + \alpha^{1}x\right) - \left(\alpha^{-7} + \alpha^{7}x + \alpha^{7}x^2\right)x^6 = \alpha^{7} + \alpha^{0}x.</math>

Let <math>\Lambda(x) = \alpha^{3} + \alpha^{1}x.</math> Don't worry that <math>\lambda_0 \neq 1.</math> The root of <math>\Lambda(x)</math> is <math>\alpha^{3-1}.</math>

Let 
:<math>\begin{align}
     \Xi(x) &= \Gamma(x)\Lambda(x) = \alpha^{3} + \alpha^{-7}x + \alpha^{-4}x^2 + \alpha^{5}x^3, \\
  \Omega(x) &= S(x)\Xi(x) \equiv \alpha^{7} + \alpha^{0}x \bmod{x^6}
\end{align}</math>

Let us look for error values using formula <math>e_j = -\Omega\left(\alpha^{-i_j}\right)/\Xi'\left(\alpha^{-i_j}\right),</math> where <math>\alpha^{-i_j}</math> are roots of polynomial <math>\Xi(x).</math>
: <math>\Xi'(x) = \alpha^{-7} + \alpha^{5}x^2.</math>

We get
:<math>\begin{align}
  e_1 &= -\frac{\Omega\left(\alpha^4\right)}{\Xi'\left(\alpha^{4}\right)}
       =  \frac{\alpha^{7} + \alpha^{4}}{\alpha^{-7} + \alpha^{-2}}
       =  \frac{\alpha^{3}}{\alpha^{3}}
       =  1 \\
  e_2 &= -\frac{\Omega\left(\alpha^7\right)}{\Xi'\left(\alpha^{7}\right)}
       =  \frac{\alpha^{7} + \alpha^{7}}{\alpha^{-7} + \alpha^{4}}
       =  0 \\
  e_3 &= -\frac{\Omega\left(\alpha^2\right)}{\Xi'\left(\alpha^2\right)}
       =  \frac{\alpha^{7} + \alpha^{2}}{\alpha^{-7} + \alpha^{-6}}
       =  \frac{\alpha^{-3}}{\alpha^{-3}}
       =  1
\end{align}</math>

The fact that <math>e_3 = 1</math> should not be surprising.

Corrected code is therefore [ 1 {{color|green|1}} 0 {{color|green|1}} 1 1 {{color|green|0}} 0 0 0 1 0 1 0 0].