0
$\begingroup$

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}$ ?

$\endgroup$
7
  • 2
    $\begingroup$ The characteristic of the field is $2$. Can you take it from there? $\endgroup$
    – Dilip Sarwate
    Commented Jul 1 at 19:44
  • $\begingroup$ That makes sense, but I'm not sure how we get from a "normal" Extended euclidian algorithm to the matrix form $\endgroup$
    – user159729
    Commented Jul 1 at 20:21
  • 1
    $\begingroup$ I may be wrong, but are you simply asking about the matrix form of the extended Euclidean algorithm? In this old answer I describe what it looks like in the ring of integers. In the ring of polynomials $GF(2^4)[x]$ it works much the same way, but instead of looking for "small" remainders we need "low degree" remainders. $\endgroup$
    – Jyrki Lahtonen
    Commented Jul 4 at 4:11
  • 1
    $\begingroup$ As is the case with all elementary row operations, performing one such an operation amounts to multiplying a given matrix by an elementary matrix (from the left). $\endgroup$
    – Jyrki Lahtonen
    Commented Jul 4 at 4:13
  • $\begingroup$ The more common term for unreadable characters is erasures (as opposed to errors). $\endgroup$
    – rcgldr
    Commented Jul 8 at 8:01

1 Answer 1

Reset to default
1
$\begingroup$

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 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
```
$\endgroup$
5
  • $\begingroup$ An alternative to this method of handling erasures is to only use the inner values of S(x) Gamma(x), where the number of terms = number of syndromes - number of erasures. In this case T(x) = 9 c 9 6 (the middle 4 values). This will generate the same Lambda(x), but would require calculating Omega(x) rather than using last row of r $\endgroup$
    – rcgldr
    Commented Jul 10 at 7:00
  • $\begingroup$ I'm not sure why this "decoding" uses negative exponents for α . "The exponents of $ \alpha $ correspond to the error locations. " why do they become negative ? $\endgroup$
    – user159729
    Commented Jul 10 at 17:49
  • $\begingroup$ why is $\alpha^4 + \alpha^{-6} + \alpha^{-1} = 0$ ? $\endgroup$
    – user159729
    Commented Jul 10 at 20:28
  • 1
    $\begingroup$ @user159729 - the roots of Lambda(x) are of the form $\alpha^{-location}$. If the coefficients of Lambda(x) are reversed, in this case from $8 + 7 x + c x^2$ to $c + 7 x + 8 x^2$, then the roots are of the form $\alpha^{location}$, but the math that follows to calculate the error values needs to use the unreversed coefficients. What I disagree with is using negative values for constants, $\alpha^{-7} = \alpha^8$, and in general, when $i$ represents a constant, then $z^{-i}= z^{15-i}$. $\endgroup$
    – rcgldr
    Commented Jul 11 at 1:54
  • 1
    $\begingroup$ @user159729 - doing the math, for $GF(2^4)$ modulo $x^4 + x +1$ or $x^4 + x^3 + 1$ or $x^4 + x^3 + x^2 + x + 1$, then for any $z$ that is a element of $GF(2^4)$, then $z^4 + z^{-6}+ z^{-1} = 0$. If using positive only constants for powers, then it becomes $z^4 + z^9 + z^{14} = 0$ . An addition table based on powers of $\alpha$ could be used. As for why, the extended euclidean algorithm decreases degree of result by at least 1, but in cases where the degree decreases by more than 1 in a single step, you'd have multiple sums = 0. $\endgroup$
    – rcgldr
    Commented Jul 11 at 2:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .