Expurgated Narrow-Sense BCH-Codes (BCH-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 : 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ʹ := $\displaystyle \bigcup_{{i\in 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ʹ = $\displaystyle \bigcup_{{i\in R(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

The Minimum Distance of a Cyclic Code

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

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:

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 k1k2 and construction X can be applied again.

Special Cases

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. PDF
[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. “Expurgated Narrow-Sense BCH-Codes (BCH-Bound).” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. http://mint.sbg.ac.at/desc_CCyclic-ExpurgatedBCHBound.html

Show usage of this method