BCH-Codes

A cyclic code C is a linear [s, n, d]-code such that with every code word (x₁,…, x_s) ∈ C the cyclic shift (x_s, x₁,…, 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_b^r = 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

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

For an i ∈ ℤ_s let C_s(i) denote the cyclotomic coset

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 ∈ â„•₀}.

Obviously, A ⊆ Aʹ ⊆ ℤ_s.

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

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 βⁱ ∈ F_{bⁿ⁽ⁱ⁾} as a vector over F_b using some fixed basis of F_{bⁿ⁽ⁱ⁾} 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₀ ⊆ J with

  {i + j  :  i ∈ I, j ∈ J₀} ⊆ Aʹ

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

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

  • 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(A₁) ⊆ C(A₂) if and only if A₂ʹ ⊆ A₁ʹ. Based on such a pair C(A₁) ⊂ C(A₂) 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₁ = C([0, k]) ⊂ C₂ = 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₁) ⊆ C_e(k₂) if k₁ ≥ k₂ 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 ℤ₂ 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

• [10, Chapter 9] and [1, Chapter 13]

• BCH code at

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. “BCH-Codes.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2024-09-05. http://mint.sbg.ac.at/desc_CCyclic.html