BCH code¶

Let \(F = \GF{q}\) and \(\Phi\) be the splitting field of \(x^{n} - 1\) over \(F\), with \(n\) a positive integer. Let also \(\alpha\) be an element of multiplicative order \(n\) in \(\Phi\). Finally, let \(b, \delta, \ell\) be integers such that \(0 \le b \le n\), \(1 \le \delta \le n\) and \(\alpha^\ell\) generates the multiplicative group \(\Phi^{\times}\).

A BCH code over \(F\) with designed distance \(\delta\) is a cyclic code whose codewords \(c(x) \in F[x]\) satisfy \(c(\alpha^{a}) = 0\), for all integers \(a\) in the arithmetic sequence \(b, b + \ell, b + 2 \times \ell, \dots, b + (\delta - 2) \times \ell\).

class sage.coding.bch_code.BCHCode(base_field, length, designed_distance, primitive_root=None, offset=1, jump_size=1, b=0)[source]¶

Bases: CyclicCode

Representation of a BCH code seen as a cyclic code.

INPUT:

base_field – the base field for this code
length – the length of the code
designed_distance – the designed minimum distance of the code
primitive_root – (default: None) the primitive root to use when creating the set of roots for the generating polynomial over the splitting field. It has to be of multiplicative order length over this field. If the splitting field is not field, it also has to be a polynomial in zx, where x is the degree of the extension field. For instance, over \(\GF{16}\), it has to be a polynomial in z4.
offset – (default: 1) the first element in the defining set
jump_size – (default: 1) the jump size between two elements of the defining set. It must be coprime with the multiplicative order of primitive_root.
b – (default: 0) is exactly the same as offset. It is only here for retro-compatibility purposes with the old signature of codes.BCHCode() and will be removed soon.

EXAMPLES:

As explained above, BCH codes can be built through various parameters:

Sage

sage: C = codes.BCHCode(GF(2), 15, 7, offset=1)
sage: C
[15, 5] BCH Code over GF(2) with designed distance 7
sage: C.generator_polynomial()
x^10 + x^8 + x^5 + x^4 + x^2 + x + 1

sage: C = codes.BCHCode(GF(2), 15, 4, offset=1, jump_size=8)
sage: C
[15, 7] BCH Code over GF(2) with designed distance 4
sage: C.generator_polynomial()
x^8 + x^7 + x^6 + x^4 + 1

Python

>>> from sage.all import *
>>> C = codes.BCHCode(GF(Integer(2)), Integer(15), Integer(7), offset=Integer(1))
>>> C
[15, 5] BCH Code over GF(2) with designed distance 7
>>> C.generator_polynomial()
x^10 + x^8 + x^5 + x^4 + x^2 + x + 1

>>> C = codes.BCHCode(GF(Integer(2)), Integer(15), Integer(4), offset=Integer(1), jump_size=Integer(8))
>>> C
[15, 7] BCH Code over GF(2) with designed distance 4
>>> C.generator_polynomial()
x^8 + x^7 + x^6 + x^4 + 1

Sage Live

C = codes.BCHCode(GF(2), 15, 7, offset=1)
C
C.generator_polynomial()
C = codes.BCHCode(GF(2), 15, 4, offset=1, jump_size=8)
C
C.generator_polynomial()

BCH codes are cyclic, and can be interfaced into the CyclicCode class. The smallest GRS code which contains a given BCH code can also be computed, and these two codes may be equal:

Sage

sage: C = codes.BCHCode(GF(16), 15, 7)
sage: R = C.bch_to_grs()
sage: codes.CyclicCode(code=R) == codes.CyclicCode(code=C)
True

Python

>>> from sage.all import *
>>> C = codes.BCHCode(GF(Integer(16)), Integer(15), Integer(7))
>>> R = C.bch_to_grs()
>>> codes.CyclicCode(code=R) == codes.CyclicCode(code=C)
True

Sage Live

C = codes.BCHCode(GF(16), 15, 7)
R = C.bch_to_grs()
codes.CyclicCode(code=R) == codes.CyclicCode(code=C)

The \(\delta = 15, 1\) cases (trivial codes) also work:

Sage

sage: C = codes.BCHCode(GF(16), 15, 1)
sage: C.dimension()
15
sage: C.defining_set()
[]
sage: C.generator_polynomial()
1
sage: C = codes.BCHCode(GF(16), 15, 15)
sage: C.dimension()
1

Python

>>> from sage.all import *
>>> C = codes.BCHCode(GF(Integer(16)), Integer(15), Integer(1))
>>> C.dimension()
15
>>> C.defining_set()
[]
>>> C.generator_polynomial()
1
>>> C = codes.BCHCode(GF(Integer(16)), Integer(15), Integer(15))
>>> C.dimension()
1

Sage Live

C = codes.BCHCode(GF(16), 15, 1)
C.dimension()
C.defining_set()
C.generator_polynomial()
C = codes.BCHCode(GF(16), 15, 15)
C.dimension()

bch_to_grs()[source]¶

Return the underlying GRS code from which self was derived.

EXAMPLES:

Sage

sage: C = codes.BCHCode(GF(2), 15, 3)
sage: RS = C.bch_to_grs()
sage: RS
[15, 13, 3] Reed-Solomon Code over GF(16)
sage: C.generator_matrix() * RS.parity_check_matrix().transpose() == 0
True

Python

>>> from sage.all import *
>>> C = codes.BCHCode(GF(Integer(2)), Integer(15), Integer(3))
>>> RS = C.bch_to_grs()
>>> RS
[15, 13, 3] Reed-Solomon Code over GF(16)
>>> C.generator_matrix() * RS.parity_check_matrix().transpose() == Integer(0)
True

Sage Live

C = codes.BCHCode(GF(2), 15, 3)
RS = C.bch_to_grs()
RS
C.generator_matrix() * RS.parity_check_matrix().transpose() == 0

designed_distance()[source]¶

Return the designed distance of self.

EXAMPLES:

Sage

sage: C = codes.BCHCode(GF(2), 15, 4)
sage: C.designed_distance()
4

Python

>>> from sage.all import *
>>> C = codes.BCHCode(GF(Integer(2)), Integer(15), Integer(4))
>>> C.designed_distance()
4

Sage Live

C = codes.BCHCode(GF(2), 15, 4)
C.designed_distance()

jump_size()[source]¶

Return the jump size between two consecutive elements of the defining set of self.

EXAMPLES:

Sage

sage: C = codes.BCHCode(GF(2), 15, 4, jump_size = 2)
sage: C.jump_size()
2

Python

>>> from sage.all import *
>>> C = codes.BCHCode(GF(Integer(2)), Integer(15), Integer(4), jump_size = Integer(2))
>>> C.jump_size()
2

Sage Live

C = codes.BCHCode(GF(2), 15, 4, jump_size = 2)
C.jump_size()

offset()[source]¶

Return the offset which was used to compute the elements in the defining set of self.

EXAMPLES:

Sage

sage: C = codes.BCHCode(GF(2), 15, 4, offset = 1)
sage: C.offset()
1

Python

>>> from sage.all import *
>>> C = codes.BCHCode(GF(Integer(2)), Integer(15), Integer(4), offset = Integer(1))
>>> C.offset()
1

Sage Live

C = codes.BCHCode(GF(2), 15, 4, offset = 1)
C.offset()

class sage.coding.bch_code.BCHUnderlyingGRSDecoder(code, grs_decoder='KeyEquationSyndrome', **kwargs)[source]¶

Bases: Decoder

A decoder which decodes through the underlying sage.coding.grs_code.GeneralizedReedSolomonCode code of the provided BCH code.

INPUT:

code – the associated code of this decoder
grs_decoder – the string name of the decoder to use over the underlying GRS code
**kwargs – all extra arguments are forwarded to the GRS decoder

bch_word_to_grs(c)[source]¶

Return c converted as a codeword of grs_code().

EXAMPLES:

Sage

sage: C = codes.BCHCode(GF(2), 15, 3)
sage: D = codes.decoders.BCHUnderlyingGRSDecoder(C)
sage: c = C.random_element()
sage: y = D.bch_word_to_grs(c)
sage: y.parent()
Vector space of dimension 15 over Finite Field in z4 of size 2^4
sage: y in D.grs_code()
True

Python

>>> from sage.all import *
>>> C = codes.BCHCode(GF(Integer(2)), Integer(15), Integer(3))
>>> D = codes.decoders.BCHUnderlyingGRSDecoder(C)
>>> c = C.random_element()
>>> y = D.bch_word_to_grs(c)
>>> y.parent()
Vector space of dimension 15 over Finite Field in z4 of size 2^4
>>> y in D.grs_code()
True

Sage Live

C = codes.BCHCode(GF(2), 15, 3)
D = codes.decoders.BCHUnderlyingGRSDecoder(C)
c = C.random_element()
y = D.bch_word_to_grs(c)
y.parent()
y in D.grs_code()

decode_to_code(y)[source]¶

Decodes y to a codeword in sage.coding.decoder.Decoder.code().

EXAMPLES:

Sage

sage: F = GF(4, 'a')
sage: a = F.gen()
sage: C = codes.BCHCode(F, 15, 3, jump_size=2)
sage: D = codes.decoders.BCHUnderlyingGRSDecoder(C)
sage: y = vector(F, [a, a + 1, 1, a + 1, 1, a, a + 1,
....:                a + 1, 0, 1, a + 1, 1, 1, 1, a])
sage: D.decode_to_code(y)
(a, a + 1, 1, a + 1, 1, a, a + 1, a + 1, 0, 1, a + 1, 1, 1, 1, a)
sage: D.decode_to_code(y) in C
True

Python

>>> from sage.all import *
>>> F = GF(Integer(4), 'a')
>>> a = F.gen()
>>> C = codes.BCHCode(F, Integer(15), Integer(3), jump_size=Integer(2))
>>> D = codes.decoders.BCHUnderlyingGRSDecoder(C)
>>> y = vector(F, [a, a + Integer(1), Integer(1), a + Integer(1), Integer(1), a, a + Integer(1),
...                a + Integer(1), Integer(0), Integer(1), a + Integer(1), Integer(1), Integer(1), Integer(1), a])
>>> D.decode_to_code(y)
(a, a + 1, 1, a + 1, 1, a, a + 1, a + 1, 0, 1, a + 1, 1, 1, 1, a)
>>> D.decode_to_code(y) in C
True

Sage Live

F = GF(4, 'a')
a = F.gen()
C = codes.BCHCode(F, 15, 3, jump_size=2)
D = codes.decoders.BCHUnderlyingGRSDecoder(C)
y = vector(F, [a, a + 1, 1, a + 1, 1, a, a + 1,
               a + 1, 0, 1, a + 1, 1, 1, 1, a])
D.decode_to_code(y)
D.decode_to_code(y) in C

We check that it still works when, while list-decoding, the GRS decoder output some words which do not lie in the BCH code:

Sage

sage: C = codes.BCHCode(GF(2), 31, 15)
sage: C
[31, 6] BCH Code over GF(2) with designed distance 15
sage: D = codes.decoders.BCHUnderlyingGRSDecoder(C, "GuruswamiSudan", tau=8)
sage: Dgrs = D.grs_decoder()
sage: c = vector(GF(2), [1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0,
....:                    1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0])
sage: y = vector(GF(2), [1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1,
....:                    1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0])
sage: print (c in C and (c-y).hamming_weight() == 8)
True
sage: Dgrs.decode_to_code(y)
[(1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1,
     0, 1, 1, 0, 1, 0, 0),
 (1, z5^3 + z5^2 + z5 + 1, z5^4 + z5^2 + z5, z5^4 + z5^3 + z5^2 + 1, 0, 0,
     z5^4 + z5 + 1, 1, z5^4 + z5^2 + z5, 0, 1, z5^4 + z5, 1, 0, 1, 1, 1, 0,
     0, z5^4 + z5^3 + 1, 1, 0, 1, 1, 1, 1, z5^4 + z5^3 + z5 + 1, 1, 1, 0, 0)]
sage: D.decode_to_code(y) == [c]
True

Python

>>> from sage.all import *
>>> C = codes.BCHCode(GF(Integer(2)), Integer(31), Integer(15))
>>> C
[31, 6] BCH Code over GF(2) with designed distance 15
>>> D = codes.decoders.BCHUnderlyingGRSDecoder(C, "GuruswamiSudan", tau=Integer(8))
>>> Dgrs = D.grs_decoder()
>>> c = vector(GF(Integer(2)), [Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0),
...                    Integer(1), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1), Integer(1), Integer(1), Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0)])
>>> y = vector(GF(Integer(2)), [Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1),
...                    Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1), Integer(1), Integer(1), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0)])
>>> print (c in C and (c-y).hamming_weight() == Integer(8))
True
>>> Dgrs.decode_to_code(y)
[(1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1,
     0, 1, 1, 0, 1, 0, 0),
 (1, z5^3 + z5^2 + z5 + 1, z5^4 + z5^2 + z5, z5^4 + z5^3 + z5^2 + 1, 0, 0,
     z5^4 + z5 + 1, 1, z5^4 + z5^2 + z5, 0, 1, z5^4 + z5, 1, 0, 1, 1, 1, 0,
     0, z5^4 + z5^3 + 1, 1, 0, 1, 1, 1, 1, z5^4 + z5^3 + z5 + 1, 1, 1, 0, 0)]
>>> D.decode_to_code(y) == [c]
True

Sage Live

C = codes.BCHCode(GF(2), 31, 15)
C
D = codes.decoders.BCHUnderlyingGRSDecoder(C, "GuruswamiSudan", tau=8)
Dgrs = D.grs_decoder()
c = vector(GF(2), [1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0,
                   1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0])
y = vector(GF(2), [1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1,
                   1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0])
print (c in C and (c-y).hamming_weight() == 8)
Dgrs.decode_to_code(y)
D.decode_to_code(y) == [c]

decoding_radius()[source]¶

Return maximal number of errors that self can decode.

EXAMPLES:

Sage

sage: C = codes.BCHCode(GF(4, 'a'), 15, 3, jump_size=2)
sage: D = codes.decoders.BCHUnderlyingGRSDecoder(C)
sage: D.decoding_radius()
1

Python

>>> from sage.all import *
>>> C = codes.BCHCode(GF(Integer(4), 'a'), Integer(15), Integer(3), jump_size=Integer(2))
>>> D = codes.decoders.BCHUnderlyingGRSDecoder(C)
>>> D.decoding_radius()
1

Sage Live

C = codes.BCHCode(GF(4, 'a'), 15, 3, jump_size=2)
D = codes.decoders.BCHUnderlyingGRSDecoder(C)
D.decoding_radius()

grs_code()[source]¶

Return the underlying GRS code of sage.coding.decoder.Decoder.code().

Note

Let us explain what is the underlying GRS code of a BCH code of length \(n\) over \(F\) with parameters \(b, \delta, \ell\). Let \(c \in F^n\) and \(\alpha\) a primitive root of the splitting field. We know:

\[\begin{split}\begin{aligned} c \in \mathrm{BCH} &\iff \sum_{i=0}^{n-1} c_i (\alpha^{b + \ell j})^i =0, \quad j=0,\dots,\delta-2\\ & \iff H c = 0 \end{aligned}\end{split}\]

where \(H = A \times D\) with:

\[\begin{split}\begin{aligned} A = &\, \begin{pmatrix} 1 & \dots & 1 \\ ~ & ~ & ~ \\ (\alpha^{0 \times \ell})^{\delta-2} & \dots & (\alpha^{(n-1) \ell})^{\delta-2} \end{pmatrix}\\ D =&\, \begin{pmatrix} 1 & 0 & \dots & 0 \\ 0 & \alpha^b & ~ & ~ \\ \dots & & \dots & 0 \\ 0 & \dots & 0 & \alpha^{b(n-1)} \end{pmatrix} \end{aligned}\end{split}\]

The BCH code is orthogonal to the GRS code \(C'\) of dimension \(\delta - 1\) with evaluation points \(\{1 = \alpha^{0 \times \ell}, \dots, \alpha^{(n-1) \ell} \}\) and associated multipliers \(\{1 = \alpha^{0 \times b}, \dots, \alpha^{(n-1) b} \}\). The underlying GRS code is the dual code of \(C'\).

EXAMPLES:

Sage

sage: C = codes.BCHCode(GF(2), 15, 3)
sage: D = codes.decoders.BCHUnderlyingGRSDecoder(C)
sage: D.grs_code()
[15, 13, 3] Reed-Solomon Code over GF(16)

Python

>>> from sage.all import *
>>> C = codes.BCHCode(GF(Integer(2)), Integer(15), Integer(3))
>>> D = codes.decoders.BCHUnderlyingGRSDecoder(C)
>>> D.grs_code()
[15, 13, 3] Reed-Solomon Code over GF(16)

Sage Live

C = codes.BCHCode(GF(2), 15, 3)
D = codes.decoders.BCHUnderlyingGRSDecoder(C)
D.grs_code()

grs_decoder()[source]¶

Return the decoder used to decode words of grs_code().

EXAMPLES:

Sage

sage: C = codes.BCHCode(GF(4, 'a'), 15, 3, jump_size=2)
sage: D = codes.decoders.BCHUnderlyingGRSDecoder(C)
sage: D.grs_decoder()
Key equation decoder for [15, 13, 3] Generalized Reed-Solomon Code over GF(16)

Python

>>> from sage.all import *
>>> C = codes.BCHCode(GF(Integer(4), 'a'), Integer(15), Integer(3), jump_size=Integer(2))
>>> D = codes.decoders.BCHUnderlyingGRSDecoder(C)
>>> D.grs_decoder()
Key equation decoder for [15, 13, 3] Generalized Reed-Solomon Code over GF(16)

Sage Live

C = codes.BCHCode(GF(4, 'a'), 15, 3, jump_size=2)
D = codes.decoders.BCHUnderlyingGRSDecoder(C)
D.grs_decoder()

grs_word_to_bch(c)[source]¶

Return c converted as a codeword of sage.coding.decoder.Decoder.code().

EXAMPLES:

Sage

sage: C = codes.BCHCode(GF(4, 'a'), 15, 3, jump_size=2)
sage: D = codes.decoders.BCHUnderlyingGRSDecoder(C)
sage: Cgrs = D.grs_code()
sage: Fgrs = Cgrs.base_field()
sage: b = Fgrs.gen()
sage: c = vector(Fgrs, [0, b^2 + b, 1, b^2 + b, 0, 1, 1, 1,
....:                   b^2 + b, 0, 0, b^2 + b + 1, b^2 + b, 0, 1])
sage: D.grs_word_to_bch(c)
(0, a, 1, a, 0, 1, 1, 1, a, 0, 0, a + 1, a, 0, 1)

Python

>>> from sage.all import *
>>> C = codes.BCHCode(GF(Integer(4), 'a'), Integer(15), Integer(3), jump_size=Integer(2))
>>> D = codes.decoders.BCHUnderlyingGRSDecoder(C)
>>> Cgrs = D.grs_code()
>>> Fgrs = Cgrs.base_field()
>>> b = Fgrs.gen()
>>> c = vector(Fgrs, [Integer(0), b**Integer(2) + b, Integer(1), b**Integer(2) + b, Integer(0), Integer(1), Integer(1), Integer(1),
...                   b**Integer(2) + b, Integer(0), Integer(0), b**Integer(2) + b + Integer(1), b**Integer(2) + b, Integer(0), Integer(1)])
>>> D.grs_word_to_bch(c)
(0, a, 1, a, 0, 1, 1, 1, a, 0, 0, a + 1, a, 0, 1)

Sage Live

C = codes.BCHCode(GF(4, 'a'), 15, 3, jump_size=2)
D = codes.decoders.BCHUnderlyingGRSDecoder(C)
Cgrs = D.grs_code()
Fgrs = Cgrs.base_field()
b = Fgrs.gen()
c = vector(Fgrs, [0, b^2 + b, 1, b^2 + b, 0, 1, 1, 1,
                  b^2 + b, 0, 0, b^2 + b + 1, b^2 + b, 0, 1])
D.grs_word_to_bch(c)