Extended euclidian algorithm

euclidean-algorithmfinite-fieldspolynomials

I'm trying to understand how the matrix form of the extended euclidian algorithm for polynomials works for a BCH code with coefficients from $GF(2^4)$ in https://en.wikipedia.org/wiki/BCH_code

for error positions $ \Gamma (x)=(\alpha ^{8}x-1 ) (\alpha ^{11}x-1) $ and syndrom $S(x)=\alpha ^{-7}+\alpha ^{1}x+\alpha ^{4}x^{2}+\alpha ^{2}x^{3}+\alpha ^{5}x^{4}+\alpha ^{-7}x^{5},$

Run the extended Euclidean algorithm:
\begin{aligned}&{\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](1)={}&{\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](2)={}&{\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{aligned}

What happened between (1) and (2) with terms $2\alpha ^{7}x^{6}+2\alpha ^{-3}x^{7}$ ?

Best Answer

The matrix form used in the wiki article is mostly a notation difference. The actual math is essentially the same. In order for the algorithm to function, at some point it needs to use $GF(2^4)$ values instead of powers of $\alpha$, in order to determine when upper coefficients have become zero. Although it's obvious that $\alpha^7 + \alpha^7 = 0$, it's not obvious that $\alpha^4 + \alpha^{-6} + \alpha^{-1} = 0$. I don't like the usage of using $2 \cdot \alpha^7$ to represent $\alpha^7 + \alpha^7$, since it depends on context (repeated addition versus multiply in $GF(2^4)$).

For each step, a 2x2 matrix that includes the quotient is inserted and the right matrix is advanced. The left two matrices are then combined on the next step. Inserting and combining the two left matrices could be done in the current step, but separating the operations is one way to display the quotient for each step. For each step, the right matrix will always decrease by 1 degree or more. In a zero error + zero erasure case, it drops to degree zero on the first step (early drop out).

Below is the matrix form and standard form for extended euclidean algorithm, using the wiki article data, using hex values to make it easier to read:

S(x)          = 5 2 3 4 6 5           (syndromes)
Gamma(x)      = 1 b 3                 (erasures)
S(x)Gamma(X)  = 5 3 9 c 9 6 b f  
x^6           = 0 0 0 0 0 0 1

matrix:

                                      | 5 3 9 c 9 6 b f |
                                      | 0 0 0 0 0 0 1   |

      | b f : 1 |                     | 0 0 0 0 0 0 1 |
      | 1   : 0 |                     | 5 3 9 c 9 6   |

      | b f : 1 |   | 3 7 : 1 |       | 5 3 9 c 9 6 |
      | 1   : 0 |   | 1   : 0 |       | f d 1 d a   |

      | f 6 b : b f |   | 7 e : 1 |   | f d 1 d a |
      | 3 7   : 1   |   | 1   : 0 |   | e 3 4 7   |
 
      | 0 b 6 8 : f 6 b |             | f d 1 d a |   (not a step)
      | 8 7 c   : 3 7   |             | e 3 4 7   |   (just combines left 2 matrices)

standard extended euclidean
                                   t is not needed for decoding
       r                 s         t         q

       5 3 9 c 9 6 b f   1         0
       0 0 0 0 0 0 1     0         1
       5 3 9 c 9 6       1         b f       b f
       f d 1 d a         3 7       f 6 b     3 7
       e 3 4 7           8 7 c     0 b 6 8   7 e

Omega(x)  = (last row of r) = e 3 4 7    
Lambda(x) = (last row of s) = 8 7 c    (errors)  roots: 4 7 
Xi(x) = Gamma(x) Lambda(x)  = 8 0 3 4 7
Xi'(x)                      = 0 0 4
```
Related Question