## Expurgated Narrow-Sense BCH-Codes

A cyclic code C is a linear [s, n, d]-code such that with every code word (x1,…, xs) ∈ C the cyclic shift (xs, x1,…, xs−1) is also in C. Cyclic codes are isomorphic to ideals in Fb[X]/⟨Xs – 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 Fb denote a finite field and F := Fbr = Fb(ω) an extension field of Fb generated by ω. Let tr : FFb denote the trace from F to Fb. Let s be a divisor of br − 1. Let

W := {xF  :  xs = 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 Cs(i) denote the cyclotomic coset

Cs(i) := {ibj ∈ ℤs  :  j ∈ ℕ0}.

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

Aʹ := Cs(i) = {ibj  :  iA, j ∈ ℕ0}.

Obviously, AAʹ ⊆ ℤs.

A subset I ⊆ ℤs is called an interval if it is of the form

I = {u, u + v, u + 2v,…, 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ʹ = Cs(i).

Based thereupon, the | Aʹ|×s-matrix H(A) over Fb consists of s columns indexed by βW and | R(A)| row-blocks indexed by iR(A) of n(i) := | Cs(i)| rows each. The entry for each column and row-block is obtained from writing βiFbn(i) as a vector over Fb using some fixed basis of Fbn(i) over Fb.

Now the cyclic code C(A) of length s over Fb 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,Fb, d−1) with generator matrix H(A).

### Terminology

• A cyclic code is called primitive if s = br − 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 IAʹ, then the BCH-bound  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 AAʹ 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  :  iI, jJ} ⊆ Aʹ,

then the Roos-bound  states that d ≥ | I| + | J|. The BCH-bound follows from the Roos-bound by setting J = {0}.

• In  the Roos-bound is given in an even more general form: If there exist interval I, J ⊆ ℤs and a subset J0J with

{i + j  :  iI, jJ0} ⊆ Aʹ

and | J ∖ J0| < | I|, then the general Roos-bound states that d ≥ | I| + | J0|. The normal Roos-bound follows from setting J0 = ∅.

• 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.

• The binary BCH-code C([1, 28]) of length 127 has minimum distance 31 .

• The binary BCH-codes C([1, 58]) and C([1, 60]) of length 255 have minimum distance 61 and 63, respectively .

### 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(A1) ⊆ C(A2) if and only if A2ʹ ⊆ A1ʹ. Based on such a pair C(A1) ⊂ C(A2) 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  (see also ). MinT can reproduce most of these results.

### Extended Narrow-Sense BCH Codes

If construction X is applied to the narrow-sense BCH-codes C1 = C([0, k]) ⊂ C2 = C([0, k]) together with the [1, 1, 1]-code, an [s, s−|[1, k]ʹ|, k + 2]-code Ce(k) is obtained, the so called extended narrow-sense BCH-code with defining interval [1, k]. These codes are again nested: Ce(k1) ⊆ Ce(k2) if k1k2 and construction X can be applied again.

### Special Cases

  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)  A. Hocquenghem.Codes correcteurs dʹerreurs.Chiffres, 2:147–156, 1959.  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)  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)  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.  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)  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)  Yves Edel.Eine Verallgemeinerung von BCH-Codes.PhD thesis, Ruprecht-Karls-Universität, Heidelberg, 1996. 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)  F. Jessie MacWilliams and Neil J. A. Sloane.The Theory of Error-Correcting Codes.North-Holland, Amsterdam, 1977.