## Primitive Cyclic Codes (BCH-Bound)

A cyclic code C is a linear [*s*, *n*, *d*]-code such that with every code word (*x*_{1},…, *x*_{s}) ∈ C the cyclic shift (*x*_{s}, *x*_{1},…, *x*_{s−1}) is also in C. Cyclic codes are isomorphic to ideals in **F**_{b}[*X*]/⟨*X*^{s} – 1⟩ and are usually studied using this ring-theoretic approach. However, here we describe them following the more elementary approach introduced by Bierbrauer [1, Chapter 13].

### Preliminaries

Let **F**_{b} denote a finite field and *F* := **F**_{br} = **F**_{b}(*ω*) an extension field of **F**_{b} generated by *ω*. Let tr : *F*→**F**_{b} denote the trace from *F* to **F**_{b}. Let *s* be a divisor of *b*^{r} − 1. Let

*W*:= {

*x*∈

*F*:

*x*

^{s}= 1},

i.e., the subgroup of order *s* of the multiplicative group of *F*, and let *α* denote a generating element of *W*, i.e.,

*W*= {1,

*α*,

*α*

^{2},…,

*α*

^{s−1}}.

For an *i* ∈ ℤ_{s} let *C*_{s}(*i*) denote the cyclotomic coset

*C*

_{s}(

*i*) := {

*ib*

^{j}∈ ℤ

_{s}:

*j*∈ ℕ

_{0}}.

These cosets define a partition of ℤ_{s}. For an arbitrary subset *A* ⊆ ℤ_{s} the Galois closure *A*ʹ is defined as

*A*ʹ :=

*C*

_{s}(

*i*) = {

*ib*

^{j}:

*i*∈

*A*,

*j*∈ ℕ

_{0}}.

Obviously, *A* ⊆ *A*ʹ ⊆ ℤ_{s}.

A subset *I* ⊆ ℤ_{s} is called an interval if it is of the form

*I*= {

*u*,

*u*+

*v*,

*u*+ 2

*v*,…,

*u*+ (

*k*– 1)

*v*}

for some *u*, *v* ∈ ℤ_{s} with *v* denoting a primitive element in ℤ_{s}, i.e., *v* and *s* are coprime.

### The Cyclic Code and its Generator and Check Matrix

For every subset *A* ⊆ ℤ_{s} let *R*(*A*) denote a subset of ℤ_{s} such that *A*ʹ is the disjoint union

*A*ʹ =

*C*

_{s}(

*i*).

Based thereupon, the | *A*ʹ|×*s*-matrix * H*(

*A*) over

**F**

_{b}consists of

*s*columns indexed by

*β*∈

*W*and |

*R*(

*A*)| row-blocks indexed by

*i*∈

*R*(

*A*) of

*n*(

*i*) := |

*C*

_{s}(

*i*)| rows each. The entry for each column and row-block is obtained from writing

*β*

^{i}∈

**F**

_{bn(i)}as a vector over

**F**

_{b}using some fixed basis of

**F**

_{bn(i)}over

**F**

_{b}.

Now the cyclic code C(*A*) of length *s* over **F**_{b} generated by *A* ⊆ ℤ_{s} is the [*s*, *s*−| *A*ʹ|, *d*]-code with parity check matrix * H*(

*A*) and generator matrix

*=*

**G***( – (ℤ*

**H**_{s}∖

*A*ʹ)). Its dual is a linear orthogonal array OA(

*b*

^{| Aʹ|},

*s*,

**F**

_{b},

*d*−1) with generator matrix

*(*

**H***A*).

### Terminology

A cyclic code is called primitive if

*s*=*b*^{r}− 1.A cyclic code C(

*A*) is called a BCH-code if*A*is an interval.A BCH-code C(

*A*) is a called a BCH-code in the narrow sense if*A*is of the form*A*= [1,*k*] = {1, 2,…,*k*}, i.e., an interval with*u*= 1 and*v*= 1.A BCH-code C(

*A*) is a called an expurgated narrow-sense BCH-code if*A*is of the form*A*= [0,*k*– 1] = {0, 1,…,*k*– 1}. Ordinary narrow-sense BCH-codes (with*A*of the form*A*= [1,*k*]) are also called augmented narrow-sense BCH-codes.

### The Minimum Distance of a Cyclic Code

MinT uses the following lower bounds on the minimum distance *d* of C(*A*):

If there exists and interval

*I*⊆ ℤ_{s}with*I*⊆*A*ʹ, then the BCH-bound [2][3][4] states that*d*≥ |*I*| + 1.If

*A*is itself an interval (and C(*A*) therefore a BCH-code), it follows from the BCH-bound and from*A*⊆*A*ʹ that*d*≥ |*A*| + 1. This bound is called the designed distance of the BCH-code C(*A*).If there exist intervals

*I*,*J*⊆ ℤ_{s}with{*i*+*j*:*i*∈*I*,*j*∈*J*} ⊆*A*ʹ,then the Roos-bound [5] states that

*d*≥ |*I*| + |*J*|. The BCH-bound follows from the Roos-bound by setting*J*= {0}.In [5] the Roos-bound is given in an even more general form: If there exist interval

*I*,*J*⊆ ℤ_{s}and a subset*J*_{0}⊆*J*with{*i*+*j*:*i*∈*I*,*j*∈*J*_{0}} ⊆*A*ʹand |

*J*∖*J*_{0}| < |*I*|, then the general Roos-bound states that*d*≥ |*I*| + |*J*_{0}|. The normal Roos-bound follows from setting*J*_{0}= ∅.If C(

*A*) ⊆ C(*A*)^{⊥}(equivalent to – (ℤ_{s}∖*A*ʹ) ⊆*A*ʹ) and*b*∈ {2, 3}, the weight of each code word of C(*A*) is a multiple of*b*. In some cases this observation can be used for improving the bound on*d*.Sporadic results:

### Cyclic Codes Included in MinT

Obviously it is impossible to fully evaluate all possible bounds for all possible cyclic codes in the parameter range of MinT. Currently at least the following results are known to MinT:

The best possible BCH bound for all narrow-sense BCH codes in the parameter range of MinT.

The best possible BCH bound for all cyclic codes with

*s*≤ 100.The best possible simple Roos-bound for all narrow-sense BCH codes with

*s*≤ 2000 and all cyclic codes with*s*≤ 60.The best possible general Roos-bound for all narrow-sense BCH codes with

*s*≤ 200 and all cyclic codes with*s*≤ 40.All BCH codes with

*s*≤ 10000 and*r*not too large.

### Subcode Structure

We have C(*A*_{1}) ⊆ C(*A*_{2}) if and only if *A*_{2}ʹ ⊆ *A*_{1}ʹ. Based on such a pair C(*A*_{1}) ⊂ C(*A*_{2}) construction X can be applied in the usual way. A systematic search for possible applications of construction X and related methods to BCH codes has been performed by Edel in [8] (see also [9]). MinT can reproduce most of these results.

### Extended Narrow-Sense BCH Codes

If construction X is applied to the narrow-sense BCH-codes C_{1} = C([0, *k*]) ⊂ C_{2} = C([0, *k*]) together with the [1, 1, 1]-code, an [*s*, *s*−|[1, *k*]ʹ|, *k* + 2]-code C_{e}(*k*) is obtained, the so called extended narrow-sense BCH-code with defining interval [1, *k*]. These codes are again nested: C_{e}(*k*_{1}) ⊆ C_{e}(*k*_{2}) if *k*_{1} ≥ *k*_{2} and construction X can be applied again.

### Special Cases

C(∅) is the [

*s*,*s*, 1]-code without redundancy.C(ℤ

_{s}) is the [*s*, 0,*s*+ 1]-trivial code·C({0}) is the [

*s*,*s*−1, 2]-parity check code.C(ℤ

_{s}∖ {0}) is the [*s*, 1,*s*]-repetition code.A primitive BCH-code C({1}) over ℤ

_{2}is the [2^{r}– 1, 2^{r}− 1−*r*, 3]-Hamming code.For

*s*=*b*−1 (i.e.,*r*= 1), Reed-Solomon codes are obtained.

### See Also

### References

[1] | Jürgen Bierbrauer.Introduction to Coding Theory.Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, London, New York, Washington D.C., 2004. MR2079734 (2005f:94001) |

[2] | A. Hocquenghem. Codes correcteurs dʹerreurs. Chiffres, 2:147–156, 1959. |

[3] | Raj Chandra Bose and Dwijendra K. Ray-Chaudhuri. On a class of error correcting binary group codes. Information and Control, 3(1):68–79, March 1960.doi:10.1016/S0019-9958(60)90287-4 MR0112768 (22 #3619) |

[4] | Raj Chandra Bose and Dwijendra K. Ray-Chaudhuri. Further results on error correcting binary group codes. Information and Control, 3(3):279–290, September 1960.doi:10.1016/S0019-9958(60)90870-6 MR0118575 (22 #9348) |

[5] | Cornelis Roos. A new lower bound for the minimum distance of a cyclic code. IEEE Transactions on Information Theory, 29(3):330–332, May 1983. |

[6] | Tadao Kasami and Nobuki Tokura. Some remarks on BCH bounds and minimum weights of binary primitive BCH codes. IEEE Transactions on Information Theory, 15(3):408–413, May 1969.MR0250745 (40 #3977) |

[7] | Daniel Augot, Pascale Charpin, and Nicolas Sendrier. Studying the locator polynomials of minimum weight codewords of BCH codes. IEEE Transactions on Information Theory, 38(3):960–973, May 1992.doi:10.1109/18.135638 MR1162823 (93a:94030) |

[8] | Yves Edel.Eine Verallgemeinerung von BCH-Codes.PhD thesis, Ruprecht-Karls-Universität, Heidelberg, 1996. |

[9] | Jürgen Bierbrauer and Yves Edel. Extending and lengthening BCH-codes. Finite Fields and Their Applications, 3(4):314–333, October 1997.doi:10.1006/ffta.1997.0188 MR1478832 (99c:94052) |

[10] | F. Jessie MacWilliams and Neil J. A. Sloane.The Theory of Error-Correcting Codes.North-Holland, Amsterdam, 1977. |

### Copyright

Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.

Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Primitive Cyclic Codes (BCH-Bound).”
From MinT—the database of optimal net, code, OA, and OOA parameters.
Version: 2008-04-04.
http://mint.sbg.ac.at/desc_CCyclic-PrimitiveBCHBound.html