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 codelength
– the length of the codedesigned_distance
– the designed minimum distance of the codeprimitive_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 orderlength
over this field. If the splitting field is notfield
, it also has to be a polynomial inzx
, wherex
is the degree of the extension field. For instance, over \(\GF{16}\), it has to be a polynomial inz4
.offset
– (default:1
) the first element in the defining setjump_size
– (default:1
) the jump size between two elements of the defining set. It must be coprime with the multiplicative order ofprimitive_root
.b
– (default:0
) is exactly the same asoffset
. It is only here for retro-compatibility purposes with the old signature ofcodes.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
>>> 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
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
>>> 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
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
>>> 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
- bch_to_grs()[source]#
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
>>> 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
- designed_distance()[source]#
Return the designed distance of
self
.EXAMPLES:
sage: C = codes.BCHCode(GF(2), 15, 4) sage: C.designed_distance() 4
>>> from sage.all import * >>> C = codes.BCHCode(GF(Integer(2)), Integer(15), Integer(4)) >>> C.designed_distance() 4
- jump_size()[source]#
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
>>> from sage.all import * >>> C = codes.BCHCode(GF(Integer(2)), Integer(15), Integer(4), jump_size = Integer(2)) >>> C.jump_size() 2
- offset()[source]#
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
>>> from sage.all import * >>> C = codes.BCHCode(GF(Integer(2)), Integer(15), Integer(4), offset = Integer(1)) >>> C.offset() 1
- 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 ofgrs_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
>>> 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
- decode_to_code(y)[source]#
Decodes
y
to a codeword insage.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
>>> 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
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
>>> 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
- decoding_radius()[source]#
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
>>> 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
- 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: 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)
>>> 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)
- grs_decoder()[source]#
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)
>>> 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)
- grs_word_to_bch(c)[source]#
Return
c
converted as a codeword ofsage.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)
>>> 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)