4507.sagews

Bose, Ray-Chaudhuri, Hocquenghem (BCH) Codes

We study in this worksheet a familiar and large family of cyclic codes. These codes are constructed with a specific minimal distance and error-correction ability in mind. They were developed independently by C. Bose and Ray-Chaudhuri (1960), and Hocquenghem (1959). There are primitive and non-primitive codes depending on the polynomial generator, and also there are binary and non-binary codes depending on the alphabet used to construct the generator polynomial.

 1. Constructing a generator polynomial

      Assume we want to construct a $t$-error correcting $q$-ary code of length $n$.

     Choose $m$ such that $t<q^{m-1}$ and $n$ divides $q^{m-1}$.

     Construct $\mathbb{F}_{q^m}$ using an irreducible polynomila $f \in\mathbb{F}_q[x]$ of degree $m$.

     Let $\beta\neq 0 \in \mathbb{F}_{q^m}$ with order $n$ (meaning $n$ is the smallest integer such that $\beta^n=1$) and $m_i=m_{\beta^i}$

     be  the minimal polynomials of $\beta^i$  over $\mathbb{F}_q$. Let $\delta=2t+1$,  and $a$ be an integer.

                        $g=\text{ lcm }(m_a,m_{a+1}, ... , m_{a+\delta-2})$ is the generator polynomial.

     The number $\delta$ is called the designed distance, and $\delta \leq d$.

2. Creating the Code

    The polynomial above is the generator polynomial for a code of lenth $n$ equal to the order of $\beta$. Since $n$ must divide $q^m-1$ (the order of an element of a field must divide the size of the field)

     we can always choose the smallest posiive integer $m$ such that $n$ divides $q^m-1$ in the above construction.

 

   Since $n$ is the order of $\beta$, then $\beta^i$ is a root of the polynomial $1-x^n$ for each $i$.

   Hence $g$ divides $1-x^n$ and thus $g$ is the generator polynomial for a cyclic code of length $n$. Codes created in this manner are called BCH codes.

   If we choose $\beta$ to be a primitive element of $\mathbb{F}_q^m$ we will have necessarily $n=q^m-1$.

  In this case the code is called primitive.

  The code is called narrow sense if $a=1$.

  $\beta$ is called the seed.

3. Primitive Single Error Correcting, Narrow Sense Binary BCH Codes

 For single error correcting codes, $t=1$, designed distance $\delta=3$, $n=2^m-1$, $a=1$.

Choose primitive polynomial $f\in \mathbb{F}_2[x]$ of degree $m$.

Let $\beta$ be a primitive element of $\mathbb{F}_{2^m}$. Thus order $(\beta)=2^m-1=n$.

$g=\text{lcm}\{m_1(x),m_2(x)\}=m_1(x)=f$.

Thus $n=2^m-1$, $k=n-\text{deg}(f)=n-m=2^m-1-m$.

Using the Hamming Bound, we can show $d=3$.

Thus the primitive single error correcting narrow-sense, binary BCH codes are the binary Hamming Codes.

 

 

Example 1

To construct a single error correcting binary code of length 7,

$\delta=3$, $n=7$,  7 divides $2^3-1$ so $m=3$.

 We will use $f=1+x+x^3$, a primitive polynomial,  to construct $\mathbb{F}_8$.

 Let $\beta$ be a root of $f$. Then $\beta$ is a primitive element and so order $(\beta)=2^3-1=7$.

 $g=\text{lcm}(m_1,m_2)$. Since $m_1=m_2=m_\beta=f$, $g=1+x+x^3$.

 We recognize the code generated by $g$ to be $\mathcal{H}_3$.

 

Example 2

Let's use SAGE to consturct a double error correcting BCH code of length $15$.

$\delta=5$, $n=15$.

15 divides $2^4-1=15$ So we need to construct $\mathbb{F}_{16}$. In the Cyclic Codes worksheet, we learned how to construct polynomial rings over finite fields.

Recall we learned how to find minimal polynomials in the Finite Fields and Minimum Polynomials worksheet. There is actually a command that will find them for you.

If we construct the field using $z$, then $z$ is a primitive element of the field.

 

F.<z> = GF(2^4, "z")
P.<x> = PolynomialRing(F,"x")

Since $z$ is a primitive element of $\mathbb{F}_{16}$, so order$(z)=2^4-1=15=n$.

To contruct the genenerator polynomial for a narrow sense code, taking $a$ to be 1,  $g=\text{lcm}\{m_1,m_2,m_3,m_4\}$.

 

z.minimal_polynomial()

x^4 + x + 1

b=z^2
b.minimal_polynomial()

x^4 + x + 1

b=z^3
b.minimal_polynomial()

x^4 + x^3 + x^2 + x + 1

b=z^4
b.minimal_polynomial()

x^4 + x + 1

g=(1+x+x^4)*(1+x+x^2+x^3+x^4);g

x^8 + x^7 + x^6 + x^4 + 1

F.<u>=PolynomialRing(GF(2),"u");
C=CyclicCode(15,1+u^4+u^6+u^7+u^8)
C

Linear code of length 15, dimension 7 over Finite Field of size 2

C.minimum_distance()

5

Since $m_1=m_2=m_4$,

$g=m_1m_3=(1+x+x^4)(1+x+x^2+x^3+x^4)=1+x^4+x^6+x^7+x^8$

$C=\langle g \rangle$ is a [15,7,5] binary 5.

 

If we let $a=3$ and follow the same procedure, we will construct a different BCH code of the same length  ability which is not narrow sense.

So then $g=\text{lcm}\{m_3,m_4,m_5,m_6\}$.

b=z^3
m3=b.minimal_polynomial();m3

x^4 + x^3 + x^2 + x + 1

b=z^4
m4=b.minimal_polynomial();m4

x^4 + x + 1

b=z^5
m5=b.minimal_polynomial();m5

x^2 + x + 1

b=z^6
m6=b.minimal_polynomial();m6

x^4 + x^3 + x^2 + x + 1

g=m3*m4*m5;g

x^10 + x^8 + x^5 + x^4 + x^2 + x + 1

F.<u>=PolynomialRing(GF(2),"u");
C=CyclicCode(15,1+u+u^2+u^4+u^5+u^8+u^10);C

Linear code of length 15, dimension 5 over Finite Field of size 2

C.minimum_distance()

7

4. Parameters for BCH codes

   For primitive codes, $n=q^m-1$

   For non-primitive codes, $n$ divides $q^m-1$ (choose the least $m$ such integer, i.e. oerder of $q$ modulo $n$).

   The  dimension   $k=n-\text{deg}(g)$.

   $m_i=m_{\beta^i}=\prod_{j \in C_i} ((\beta^i)^{q^j}-x).$  where $C_i$ is the $q$-cyclotomic coset of $i$.

   deg$(m_i)=|C_i|, \Rightarrow \text{deg}(g)\leq \sum_{i=1}^{a+\delta-2}|C_i|$.

   Theorem

    $k\geq n-\sum_{i=a}^{a+\delta-2}|C_i|$.

    For narrow-sense, primitive codes, $k\geq q^m-1-m(\delta-1)$.

   For narrow-sense, primitive binary codes, $k\geq 2^m-1-\frac{m(\delta-1)}{2}$.

5. Characterization of Codewords

    $c=\langle g \rangle$ be an $[n,k]$ BCH code, with designed distance $\delta$ and seed $\beta \in \mathbb{F}_{q^m}$.

     $\beta^a,\beta^a+1, ..., \beta^{a+\delta-2}$ are roots of $g$ in $\mathbb{F}_{q^m}$

     $w\in C \Rightarrow w=hg, \Rightarrow \beta^a, ...,\beta^{a+\delta-2}$ are also roots of $w$ in $\mathbb{F}_{q^m}$.

     Conversely, if $f\in \mathbb{F}_q[x]$ has roots $\beta^a, \beta^{a+1}, ... , \beta^{a+\delta-2}$ in $\mathbb{F}_{q^m}$ ,

     then $m_i$ divides $f$ for each $i$ and so $g$ divides $f$. Thus $f\in C$.

     Theorem

     A polynomial $f\in C$ if and only if $\beta^a, \beta^{a+1}, ... , \beta^{a+\delta-2}$ are roots of $f$ in $\mathbb{F}_{q^m}$.

6. Parity Check Matrices For BCH Codes

Let $C=\langle g \rangle$ be an $[n,k]$ BCH code with designed distance $\delta$ and seed $\beta \in \mathbb{F}$ of order $n$.

 

Let $b_1, b_2, \cdots, b_r$ be the distinct generating roots (powers of $\beta$) of $g$ in $\mathbb{F}_{q^m}$. Thus $r\leq (a+\delta-2)$.

H= 1   $b_1$   $b_1^2$   $\cdots$   $b_1^{n-1}$

      1   $b_2$   $b_2^2$   $\cdots$   $b_2^{n-1}$

      .      .            .          $\cdots$   .

      .      .            .                            .

      .      .            .                            .

      1     $b_r$   $b_r^2$   $\cdots$   $b_r^{n-1}$

     

 

 

By the theorem above, $w \in C$ if and only if  $w(b_i)=0$ for all $i$.

  $wH^T=(w(b_1),w(b_2),\cdots, w(b_r))=0$

 

Example

$t=1\Rightarrow \delta=3$, $n=7$, $\beta$ a root of $1+x+x^3$ over $\mathbb{F}_2$.

$g=m_1$     $H=(1 \: \beta \: \beta^2 \cdots \beta^6)$ expressing powers of $\beta$ as vectors over $\mathbb{F}_2$.

$1+\beta+\beta^3=0$

$1 \rightarrow 100$

$\beta \rightarrow 010$

$\beta^2 \rightarrow 001$

$\beta^3=1+\beta \rightarrow 110$

$\beta^4=\beta+\beta^2 \rightarrow 011$

$\beta^5=\beta2+\beta^3=1+\beta+\beta^2 \rightarrow 111$

$\beta^6=\beta+\beta^2+\beta^3=1+\beta^2  \rightarrow 101$

$\beta^7=1$

So

H=  1  0  0  1  0  1  1

       0  1  0  1  1  1  0

       0  0  1  0  1  1  1

 

Example

for $t=2 \Rightarrow \delta=5$, $n=7$, $\beta$ as above

$g=m_1m_3$

H= 1    $\beta$   $\beta^2$   $\beta^3$   $\beta^4$   $\beta^5$   $\beta^6$

      1   $\beta^3$   $\beta^6$   $\beta^2$   $\beta^5$   $\beta$     $\beta^4$

$H$ is a 6 X 7 matrix over $\mathbb{F}_2$.

 

Just to check the dimensions using SAGE...

F.<z> = GF(2^3, "z")
P.<x> = PolynomialRing(F,"x")

m1=z.minimal_polynomial();
m1

x^3 + x + 1

b=z^2
m2=b.minimal_polynomial();
m2

x^3 + x + 1

b=z^3
m3=b.minimal_polynomial();
m3

x^3 + x^2 + 1

b=z^4
m4=b.minimal_polynomial();
m4;

x^3 + x + 1

g=m1*m3;g

x^6 + x^5 + x^4 + x^3 + x^2 + x + 1

F.<u>=PolynomialRing(GF(2),"u")
C=CyclicCode(7,1+u+u^2+u^3+u^4+u^5+u^6);C

Linear code of length 7, dimension 1 over Finite Field of size 2

C.check_mat()

[1 0 0 0 0 0 1] [0 1 0 0 0 0 1] [0 0 1 0 0 0 1] [0 0 0 1 0 0 1] [0 0 0 0 1 0 1] [0 0 0 0 0 1 1]

Homework #8

Problem 1.

a) Construct a ternary double error correcting BCH code of length 13.

b) Using a different seed, construct another ternary double error correcting $BCH$ code of length 13.

Problem 2.

Construct a binary narrow-sense double error correcting BCH code with seed $\beta \in \mathbb{F}_{2^{11}}$ of order 23.

What is the redundancy of the code?

Problem 3.

Construct a generator polynomial and a parity-check matrix for a binary double-error correcting BCH code of length 15.

Problem 4.

Exercise 8.5 from the text

Problem 5.

Exercise 8.15 from the text

Problem 6.

Exercise 8.7 from the text

Problem 7.

Exercise 8.8 from the text