4608.sagews

Decoding BCH Codes

We assume $C$ is a narrow-sense BCH code of length $n$ and designed distance $\delta$.

As usual:

• $v(x)$ is the codeword sent
• $e(x)$ is the error polynomial with weight $\leq t=\frac{\delta-1}{2}$
• $w(x)$ is the recieved word
• $g(x)$ is the generator polynomial of $C$.
• The seed, $\beta$, is a primitive $nth$ root of unity, with $n|q^m-1$. (the order of $\beta$ is $n$)
• $\beta, \beta^2,\beta^3,...,\beta^{\delta-1}$ are the roots of $g(x)$
• $m_i=m_{\beta^i}$ are the minimal polynomials of $\beta^i$
• Parity check matrix $H$ obtained as in BCH code worksheet.

Syndromes

Consider the generating roots of $g: \beta,\beta^2,...,\beta^{2t}$.  ($2t=\delta-1$)

Define $s_i(w)=w(\beta^{i+1}) \in \mathbb{F}_{q^m}$.

$s_i(w)=s_i(e)=e(\beta^{i+1})=w(\beta^{i+1})$

By the division algorithm:

$w=qm_i+r_i\rightarrow w(\beta^i)=q(\beta^i)m_i(\beta^i)+r(\beta^i)=r_i(\beta^i)$

Hence, $s_i(w)=(w \pmod{m_{\beta^{i+1}}})(\beta^{i+1})$.

The Syndrome Polynomial  is defined as $S(w):=s_0+s_1z+s_2z^2+...+s_{2t-1}z^{2t-1}$.

 

Reconstructing the error

Representing the error as a polynomial:

$e(x)=\sum\limits_{j=0}^l \lambda_{i_j}x^{i_j}$      $0\leq i_j\leq n-1$,      $\lambda_{i_j}\neq 0 \in \mathbb{F}_q$

First we want to find the $i_j$'s, the error location numbers, or error positions.

We can do this by finding the values of $u_j:=\beta^{i_j}$. These are called the error locators.

Second, we want to find the error magnitudes $\lambda_{i_j}$ at each error location.

For simpliciy of notation let $\gamma_j:=\lambda_{i_j}$. in the case of binary codes, these are all 1.

 

Error Locator Polynomial

We find the error locators by finding the roots of a polymonial $\sigma(z)$ called the error locator polynomial. The error locators will be the inverses of the roots of this polynomial. ($l=wt(e)$).

$\sigma(z):=\prod\limits_{j=0}^{l-1}(1-u_jz)$

There are several algorithms to find the error locator poynomial. A popular one is the Berlekamp-Massey Algorithm. Here we use a very clever and beautiful algorithm developed by Sugiyama.

Define the error evaluator polynomial:

$\omega(z):=\sum\limits_{j=0}^{l-1}\gamma_ju_j\frac{\sigma(z)}{(1-u_jz)}$

 

$\omega(z)$ is a polynomial of degree $\leq l-1$. Expanding as a power series:

$\omega(z)=\sigma(z)\sum\limits_{j=0}^{l-1}\gamma_ju_j\sum\limits_{r=0}^\infty (u_jz)^r$

$\omega(z)=\sigma(z)\sum\limits_{r=0}^\infty\left(\sum\limits_{j=0}^{l-1}\gamma_ju_j^{r+1}\right)z^r$

$\omega(z) \equiv \sigma(z)\sum\limits_{r=0}^{2t-1}\left(\sum\limits_{j=0}^{l-1}\gamma_ju_j^{r+1}\right)z^r \pmod{z^{2t}}$

$\omega(z) \equiv \sigma(z)\sum\limits_{r=0}^{2t-1}(s_r)z^r \pmod{z^{2t}}$

 

Key Equation

This gives us the key equation to solve:

 $\omega(z) \equiv \sigma(z)S(z) \pmod{z^{2t}}$

With deg$(\omega)\leq t-1$ and deg$(\sigma)\leq t$

The roots of $\sigma$ are $u_i^{-1}$, but $\omega(u_i^{-1})=\gamma_ju_j\prod_{i\neq j}(1-u_ju_i^{-1})\neq 0$.

Thus $\sigma$ and $\omega$ are relatively prime polynomials.

The solution to the key equation is unique up to scalar (in $\mathbb{F}_{q^m}$) multiple (see Theorem  8.1.21)

To solve the key equation means to find such pair $\omega(z), \sigma(z)$.

 

Solving the Key Equation

(Truncated) Extended Euclidean Algorithm:

Proceed with the steps of the Euclidean Algorithm for the polynomials $f(z)=z^{2t}$, $g(z)=S(z)$, but stop when

the remainder has degree $< t$. You can the use the Extended Euclidean Algorithm to track back and express this "last" remainder as a linear combinaion of $z^{2t}$ and

$S(z)$, obtaining:

$r(z)=h_1(z)z^{2t}+h_2(z)S(z)$

$r(z)\equiv h_2(z)S(z) \pmod{z^{2t}}$.

satisfying the degree condtitions of the key equation. By the uniqueness property $\exists \rho \in \mathbb{F}_{q^m}$ such that

$\omega(z)=\rho r(z)$      and      $\sigma(z)=\rho h_2(z)$

Finding the Error Polynomial

The roots of $h_2(z)$ will be the roots of $\sigma(z)$, from which we can deduce the error locations.

Once we find the error locations, we can determine the error magnitudes $\lambda_{i_j}$ by solving a linear system of equations over $\mathbb{F}_{q^m}$.

simple use of Cramer's Rule gives us:

          $\gamma_j=\frac{-\omega(u_j^{-1})}{\sigma(u_j^{-1})}$

where $\omega$ is the error evalutator polynomial and $\sigma$ is the error locator polynomial.

Example 1

 $C=\langle 1+x+x^2+x^4+x^5+x^8+x^{10}\rangle$ defines a primitive BCH code of length 15 and designed distance 7.

The seed $\beta$ is a root of $1+x+x^4$ which we will use to construct $\mathbb{F}_{2^4}$.

We want to decode the received word $w=100111111000110$.

$w=1+x^3+x^4+x^5+x^6+x^7+x^8+x^{12}+x^{13}$.

The generating roots  are $\beta,\beta^2,\beta^3,\beta^4,\beta^5,\beta^6$.

First we compute the syndrome polynomial.

Recall that $s_i(w)=(w\pmod{m_{i+1}})(\beta_{i+1})$.

F.<x>=PolynomialRing(GF(2),"x")
K.<b>=GF(2^4,name='b',modulus=1+x+x^4)

w=1+x^3+x^4+x^5+x^6+x^7+x^8+x^12+x^13
for i in range(1,7):
    c=b^i
    g=c.minimal_polynomial()
    print "w mod m_",i,w%g

w mod m_ 1 x^3 + x^2 w mod m_ 2 x^3 + x^2 w mod m_ 3 x^2 + 1 w mod m_ 4 x^3 + x^2 w mod m_ 5 x w mod m_ 6 x^2 + 1

def GetPower(element,root):
    power=0
    for i in range(1,multiplicative_order(root)+1):
        temp=root^i
        if temp==element:
            power=i
    return power

s_0=b^3+b^2
power=GetPower(s_0,b)
print "s_0=",s_0, "= b^",power

s_0= b^3 + b^2 = b^ 6

s_1=(b^2)^3+(b^2)^2
power=GetPower(s_1,b)
print "s_1=",s_1, "= b^",power

s_1= b^3 + b^2 + b + 1 = b^ 12

s_2=(b^3)^2+1
power=GetPower(s_2,b)
print "s_2=",s_2, "= b^",power

s_2= b^3 + b^2 + 1 = b^ 13

s_3=(b^4)^3+(b^4)^2
power=GetPower(s_3,b)
print "s_3=",s_3, "= b^",power

s_3= b^3 + b = b^ 9

s_4=(b^5)
power=GetPower(s_4,b)
print "s_4=",s_4, "= b^",power

s_4= b^2 + b = b^ 5

s_5=(b^6)^2+1
power=GetPower(s_5,b)
print "s_5=",s_5, "= b^",power

s_5= b^3 + b^2 + b = b^ 11

So $S(z)=\beta^6+\beta^{12}z+\beta^{13}z^2+\beta^{9}z^3+\beta^5z^4+\beta^{11}x^5$.

Now we apply the (truncated) extended Euclidean Algorithm.

$z^{2t}=z^6=(\beta^{13}+\beta^4z)S(z)+(\beta^4+\beta^6z^2+\beta^{12}z^3+\beta^8z^4)$

$S(z)=(\beta^2+\beta^3z)(\beta^4+\beta^6z^2+\beta^{12}z^3+\beta^8z^4)+(\beta^2z+\beta^3z^2+\beta^{14}z^3)$

$(\beta^4+\beta^6z^2+\beta^{12}z^3+\beta^{8}z^4)=(\beta^9z)(\beta^2z+\beta^3z^2+\beta^{14}z^3)+(\beta^4+\beta z^2)$

 

Working Backwords now:

$(\beta^4+\beta z^2)=(\beta^4+\beta^6 z^2+\beta^{12}z^3+\beta^8 z^4)+(\beta^9 z)(\beta^2 z+ \beta^3 z^2+\beta^{14} z^3)$

$=(\beta^4+\beta^6 z^2+\beta^{12} z^3+\beta^8 z^4)+(\beta^9z)S(z) + (\beta^2+\beta^3 z)(\beta^4+\beta^6 z^2 +\beta^{12} z^3 +\beta^8 z^4)$

$=(\beta^9 z) S(z) +(1+\beta^{11} z+ \beta^{12} z^2)(\beta^4+\beta^6 z^2 +\beta^{12} z^3+ \beta^8 z^4)$

$=(\beta^{13}+\beta^4 z +\beta^5 z^2+\beta z^3)S(z)+ (1+\beta^{11} z + \beta^{12}z^2)z^6$

 

$\sigma(z)=\rho(\beta^{13}+\beta^4z+\beta^5z^2+\beta z^3)$

$\omega(z)=\rho(\beta^4+\beta z^2)$

 

Before we find the roots of $\sigma(z)$ let me give you an idea of how to do the first step of the euclidean algorithm in SAGE.

P.<z>=PolynomialRing(K,"z")
S=b^6+(b^12)*z+(b^13)*z^2+(b^9)*z^3+(b^5)*z^4+(b^11)*z^5
rem=z^6%S
quo=(z^6-rem)/S
print "rem=",rem,"quo=",quo

rem= (b^2 + 1)*z^4 + (b^3 + b^2 + b + 1)*z^3 + (b^3 + b^2)*z^2 + b + 1 quo= (b + 1)*z + b^3 + b^2 + 1

print GetPower(b^2+1,b), GetPower(b^3+b^2+b+1,b), GetPower(b^3+b^2,b),GetPower(b+1,b),
GetPower(b+1,b), GetPower(b^3+b^2+1,b)

Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_8.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("cHJpbnQgR2V0UG93ZXIoYl4yKzEsYiksIEdldFBvd2VyKGJeMytiXjIrYisxLGIpLCBHZXRQb3dlcihiXjMrYl4yLGIpLEdldFBvd2VyKGIrMSxiKSwKR2V0UG93ZXIoYisxLGIpLCBHZXRQb3dlcihiXjMrYl4yKzEsYik="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in <module> File "/tmp/tmplaTV7D/___code___.py", line 3, in <module> print GetPower(b**_sage_const_2 +_sage_const_1 ,b), GetPower(b**_sage_const_3 +b**_sage_const_2 +b+_sage_const_1 ,b), GetPower(b**_sage_const_3 +b**_sage_const_2 ,b),GetPower(b+_sage_const_1 ,b), NameError: name 'GetPower' is not defined

XGCD(z^6, S)

(1, (b + 1)*z^3 + (b^3 + b^2 + 1)*z^2 + (b^3 + b^2 + b + 1)*z, (b^2 + 1)*z^4 + (b^3 + b^2 + b)*z^2 + z + b^3 + b)

GCD

Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_10.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("P0dDRA=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in <module> File "/tmp/tmpXyEikJ/___code___.py", line 2 ?GCD ^ SyntaxError: invalid syntax

So we see that $z^6=(\beta^{13}+\beta^4 z)S(z)+(\beta^4+\beta^6z^2+\beta^{12}z^3+\beta^{8}z^4)$.

 

Now to find the roots of $\sigma(z)$...

for i in range(1,16):
    if b^13+b^4*b^i+b^5*(b^i)^2+b*(b^i)^3==0:
        print i

2 11 14

Thus the roots of $\sigma(z)$ are $\beta^{2},\beta^{11},\beta^{14}$

The error locators are the reciprocals. Since $\beta^{15}=1$, $(\beta^2)^{-1}=\beta^{13}, (\beta^{11})^{-1}=\beta^4$, and $(\beta^{14})^{-1}=\beta$.

Since this is a binary code, all of the error magnitutdes are 1.

Thus $e(x)=x+x^4+x^{13}$.

$\hat{v}=1+x+x^3+x^5+x^6+x^7+x^8+x^{12}$

$\hat{v}=110101111000100$

Example 2

$C=\langle 2+2x+x^4+2x^5+x^6+x^7 \rangle$ defines a ternary, non-primitive, $a=0$ , BCH code of length 13 and designed distance 5.

The seed, $\beta=\alpha^2$, where $\alpha$ is a root of $1+2x^2+x^3$ which was used to construct $\mathbb{F}_{3^3}$.

Decode the received word $w=2200211102110$

$w(x)=2+2x+2x^4+x^5+x^6+x^7+2x^9+x^{10}+x^{11}$

The generating roots are $1,\beta,\beta^2,\beta^3$ with minimal polynomials

$m_0=2+x$,   $m_1=2+2x+2x^2+x^3$,   $m_2=2+2x+x^3$,  $m_3=m_1$.

 

We compute the syndrome polynomial:$s_i(w)=(w\pmod{m_{i+1}})(\beta^{i+1})$

$s_0=(1)(\beta^0)=1$

$s_1=(1+2x+x^2)(\beta^1)=1+2\beta+\beta^2=\alpha^{14}$

$s_2=(1+2x)(\beta^{2})=1+2\beta^2=\alpha^{23}$

$s_3=(a+2x+x^2)(\beta^3)=1+2(\beta^3)+(\beta^3)^2=\alpha^{16}$

Thus $s(z)=1+\alpha^{14}z+\alpha^{23}z^2+\alpha^{16}z^3$.

 

Now apply the (truncated) extended Euclidean Algorithm:

$z^4=(\alpha^4+\alpha^{10}z)S(z)+(\alpha^{17}+\alpha^{16}z+2z^2)$

$S(z)=(\alpha^{16}+\alpha^3z)(\alpha^{17}+\alpha^{16}z+2z^2)+(\alpha^{15}+\alpha^{16}z)$

Working backwards:

$(\alpha^{15}+\alpha^{16}z)=S(z)+2(\alpha^{16}+\alpha^3z)(\alpha^{17}+\alpha^{16}z+2z^2)$

$=S(z)+2(\alpha^{16}+\alpha^3z)(z^4+2(\alpha^4+\alpha^{10}z)S(z))$

$=(\alpha^{15}+\alpha^3z+2z^2)S(z)+(\alpha^3+\alpha^{16}z)(z^4)$

 

$\sigma(z)=\rho(\alpha^{15}+\alpha^3z+2z^2)$

$\omega(z)=\rho(\alpha^3+\alpha^{16}z)$

The roots of $\sigma(z)$ are $\alpha^{10}, \alpha^{18}$

Error locators are the reciprocals: $\alpha^{16}=\beta^8$, $\alpha^8=\beta^4$.

Thus $e(x)=\lambda_1 x^4+\lambda_ 2x^8$.

Now we need to compute the error magnitudes.

$s_1=e(\beta^1)=\lambda_1\beta^4+\lambda_2\beta^8=\alpha^{14}$

$s_2=e(\beta^2)=\lambda_1\beta^8+\lambda_2\beta^{16}=\alpha^{23}$

We need to solve a linear system of equations in $\mathbb{F}_{3^3}$.

$\begin{pmatrix}\alpha^8 & \alpha^{16}\\ \alpha^{16} & \alpha^6 \end {pmatrix} \begin{pmatrix}\lambda_1 \\ \lambda_2 \end {pmatrix}=\begin{pmatrix} \alpha^{14}\\ \alpha^{23} \end {pmatrix}$

In general, use matrices. Here try values 0,1,2. Soution is $\lambda_1=2, \lambda_2=2$.

Thus the error polynomial is  $e(x)=2x^4+2x^8$

The received word decodes as $\hat{v}=w(x)-e(x)=2+2x+x^5+x^6+x^7+x^8+2x^9+x^{10}+x^{11}$

$\hat{v}=2200011112110$

 

Homework #9

Problem 1.

Exercise 8.7 from the text

Problem 2.

Exercise 8.8 from the text

Problem 3.

Exercise 8.19 from the text

Problem 4.

Exercise 8.21 from the text

Problem 5.

Consider a $RS(15,9,7)$ code over $\mathbb{F}_-{2^4}$.

a) Obtain the generator polynomial of the code.

b) Suppose that the received polynomial is $w(x)=\alpha^7x^3+\alpha^3x^6+\alpha^4x^{12}$.  Determine the most likely word $v(x)$ sent.