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)#

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

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: C = codes.BCHCode(GF(16), 15, 7)
sage: R = C.bch_to_grs()
sage: codes.CyclicCode(code=R) == codes.CyclicCode(code=C)
True

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

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
bch_to_grs()#

Return the underlying GRS code from which self was derived.

EXAMPLES:

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
designed_distance()#

Return the designed distance of self.

EXAMPLES:

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

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

EXAMPLES:

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

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

EXAMPLES:

sage: C = codes.BCHCode(GF(2), 15, 4, offset = 1)
sage: C.offset()
1
class sage.coding.bch_code.BCHUnderlyingGRSDecoder(code, grs_decoder='KeyEquationSyndrome', **kwargs)#

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)#

Return c converted as a codeword of grs_code().

EXAMPLES:

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
decode_to_code(y)#

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

EXAMPLES:

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

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: 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
decoding_radius()#

Return maximal number of errors that self can decode.

EXAMPLES:

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

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: 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)
grs_decoder()#

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

EXAMPLES:

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)
grs_word_to_bch(c)#

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

EXAMPLES:

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)