## Narrow-Sense BCH-Codes (Simple Roos-Bound)

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 : Fâ†’Fb denote the trace from F to Fb. Let s be a divisor of br âˆ’ 1. Let

W := {x âˆˆ FÂ  : Â 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Â  : Â 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 + 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 i âˆˆ R(A) of n(i) := | Cs(i)| rows each. The entry for each column and row-block is obtained from writing Î²i âˆˆ Fbn(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 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 J0 âŠ† J with

{i + jÂ  : Â i âˆˆ I, j âˆˆ J0} âŠ† 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 [6].

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

### 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 [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 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 k1 â‰¥ k2 and constructionÂ X can be applied again.