Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" Punctured code
Let `C` be a linear code. Let `C_i` be the set of all words of `C` with the `i`-th coordinate being removed. `C_i` is the punctured code of `C` on the `i`-th position. """
#***************************************************************************** # Copyright (C) 2015 David Lucas <david.lucas@inria.fr> # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ #*****************************************************************************
r""" Returns v punctured as the positions listed in ``points``.
INPUT:
- ``v`` -- a vector or a list of vectors
- ``points`` -- a set of integers, or an integer
EXAMPLES::
sage: v = vector(GF(7), (2,3,0,2,1,5,1,5,6,5,3)) sage: from sage.coding.punctured_code import _puncture sage: _puncture(v, {4, 3}) (2, 3, 0, 5, 1, 5, 6, 5, 3) """ raise TypeError("points must be either a Sage Integer, a Python int, or a set") size = len(v[0]) S = VectorSpace(v[0].base_ring(), size - len(points)) l = [] for i in v: new_v = [i[j] for j in range(size) if j not in points] l.append(S(new_v)) return l
r""" Returns ``l`` with ``value`` inserted in the corresponding position from ``punctured_points``.
INPUT:
- ``l`` -- a list
- ``punctured_points`` -- a set of integers
- ``value`` -- (default: ``None``) an element to insert in every position given in``punctured_points``. If it is let to ``None``, a random value will be chosen for each insertion.
EXAMPLES::
sage: from sage.coding.punctured_code import _insert_punctured_positions sage: _insert_punctured_positions([1,2,3,4], {2,4,5}, 1) [1, 2, 1, 3, 1, 1, 4] """ final[i] = F.random_element() else:
r""" Representation of a punctured code.
- ``C`` -- A linear code
- ``positions`` -- the positions where ``C`` will be punctured. It can be either an integer if one need to puncture only one position, a list or a set of positions to puncture. If the same position is passed several times, it will be considered only once.
EXAMPLES::
sage: C = codes.random_linear_code(GF(7), 11, 5) sage: Cp = codes.PuncturedCode(C, 3) sage: Cp Puncturing of [11, 5] linear code over GF(7) on position(s) [3]
sage: Cp = codes.PuncturedCode(C, {3, 5}) sage: Cp Puncturing of [11, 5] linear code over GF(7) on position(s) [3, 5] """
r""" TESTS:
If one of the positions to puncture is bigger than the length of ``C``, an exception will be raised::
sage: C = codes.random_linear_code(GF(7), 11, 5) sage: Cp = codes.PuncturedCode(C, {4,8,15}) Traceback (most recent call last): ... ValueError: Positions to puncture must be positive integers smaller than the length of the provided code """ raise TypeError("positions must be either a Sage Integer, a Python int, a set or a list") raise TypeError("if positions is a list or a set, it has to contain only Python ints or Sage Integers") positions = set(positions) raise ValueError("Provided code must be a linear code") "PuncturedMatrix", "OriginalCode")
r""" Tests equality between two Punctured codes.
EXAMPLES::
sage: C = codes.random_linear_code(GF(7), 11, 5) sage: Cp1 = codes.PuncturedCode(C, 2) sage: Cp2 = codes.PuncturedCode(C, 2) sage: Cp1 == Cp2 True """ and self.punctured_positions() == other.punctured_positions() \ and self.original_code() == other.original_code()
r""" Returns a string representation of ``self``.
EXAMPLES::
sage: C = codes.random_linear_code(GF(7), 11, 5) sage: Cp = codes.PuncturedCode(C, 3) sage: Cp Puncturing of [11, 5] linear code over GF(7) on position(s) [3] """ % (self.original_code(), list(self.punctured_positions()))
r""" Returns a latex representation of ``self``.
EXAMPLES::
sage: C = codes.random_linear_code(GF(7), 11, 5) sage: Cp = codes.PuncturedCode(C, 3) sage: latex(Cp) \textnormal{Puncturing of [11, 5] linear code over GF(7) on position(s) } [3] """ % (self.original_code(), list(self.punctured_positions()))
r""" Returns the list of positions which were punctured on the original code.
EXAMPLES::
sage: C = codes.random_linear_code(GF(7), 11, 5) sage: Cp = codes.PuncturedCode(C, 3) sage: Cp.punctured_positions() {3} """
r""" Returns the linear code which was punctured to get ``self``.
EXAMPLES::
sage: C = codes.random_linear_code(GF(7), 11, 5) sage: Cp = codes.PuncturedCode(C, 3) sage: Cp.original_code() [11, 5] linear code over GF(7) """
r""" Returns the dimension of ``self``.
EXAMPLES::
sage: set_random_seed(42) sage: C = codes.random_linear_code(GF(7), 11, 5) sage: Cp = codes.PuncturedCode(C, 3) sage: Cp.dimension() 5 """ return self._dimension
r""" Returns a random codeword of ``self``.
This method does not trigger the computation of ``self``'s :meth:`sage.coding.linear_code.generator_matrix`.
INPUT:
- ``agrs``, ``kwds`` - extra positional arguments passed to :meth:`sage.modules.free_module.random_element`.
EXAMPLES::
sage: C = codes.random_linear_code(GF(7), 11, 5) sage: Cp = codes.PuncturedCode(C, 3) sage: Cp.random_element() in Cp True """
r""" Transforms an element of the message space into an element of the code.
INPUT:
- ``m`` -- a vector of the message space of the code.
- ``original_encode`` -- (default: ``False``) if this is set to ``True``, ``m`` will be encoded using an Encoder of ``self``'s :meth:`original_code`. This allow to avoid the computation of a generator matrix for ``self``.
- ``encoder_name`` -- (default: ``None``) Name of the encoder which will be used to encode ``word``. The default encoder of ``self`` will be used if default value is kept
OUTPUT:
- an element of ``self``
EXAMPLES::
sage: M = matrix(GF(7), [[1, 0, 0, 0, 3, 4, 6], [0, 1, 0, 6, 1, 6, 4], [0, 0, 1, 5, 2, 2, 4]]) sage: C_original = LinearCode(M) sage: Cp = codes.PuncturedCode(C_original, 2) sage: m = vector(GF(7), [1, 3, 5]) sage: Cp.encode(m) (1, 3, 5, 5, 0, 2) """ c = self.original_code().encode(m, encoder_name, **kwargs) return _puncture(c, self.punctured_positions, self)
def structured_representation(self): r""" Returns ``self`` as a structured code object.
If ``self`` has a specific structured representation (e.g. a punctured GRS code is a GRS code too), it will return this representation, else it returns a :class:`sage.coding.linear_code.LinearCode`.
EXAMPLES:
We consider a GRS code::
sage: C_grs = codes.GeneralizedReedSolomonCode(GF(59).list()[:40], 12)
A punctured GRS code is still a GRS code::
sage: Cp_grs = codes.PuncturedCode(C_grs, 3) sage: Cp_grs.structured_representation() [39, 12, 28] Reed-Solomon Code over GF(59)
Another example with structureless linear codes::
sage: set_random_seed(42) sage: C_lin = codes.random_linear_code(GF(2), 10, 5) sage: Cp_lin = codes.PuncturedCode(C_lin, 2) sage: Cp_lin.structured_representation() [9, 5] linear code over GF(2) """ cur_pts = list(C.punctured_positions()) list_len = len(list_pts) for p in cur_pts: for i in range(list_len): if (p <= list_pts[i]): list_pts[i] += 1 list_pts += cur_pts C = C.original_code()
r""" Encoder using original code generator matrix to compute the punctured code's one.
INPUT:
- ``code`` -- The associated code of this encoder.
EXAMPLES::
sage: C = codes.random_linear_code(GF(7), 11, 5) sage: Cp = codes.PuncturedCode(C, 3) sage: E = codes.encoders.PuncturedCodePuncturedMatrixEncoder(Cp) sage: E Punctured matrix-based encoder for the Puncturing of [11, 5] linear code over GF(7) on position(s) [3] """
r""" TESTS:
If ``code`` is not a ``PuncturedCode``, an exception is raised::
sage: C = codes.random_linear_code(GF(7), 11, 5) sage: codes.encoders.PuncturedCodePuncturedMatrixEncoder(C) Traceback (most recent call last): ... TypeError: code has to be an instance of PuncturedCode class """
r""" Returns a string representation of ``self``.
EXAMPLES::
sage: C = codes.random_linear_code(GF(7), 11, 5) sage: Cp = codes.PuncturedCode(C, 3) sage: E = codes.encoders.PuncturedCodePuncturedMatrixEncoder(Cp) sage: E Punctured matrix-based encoder for the Puncturing of [11, 5] linear code over GF(7) on position(s) [3] """
r""" Returns a latex representation of ``self``.
EXAMPLES::
sage: C = codes.random_linear_code(GF(7), 11, 5) sage: Cp = codes.PuncturedCode(C, 3) sage: E = codes.encoders.PuncturedCodePuncturedMatrixEncoder(Cp) sage: latex(E) \textnormal{Punctured matrix-based encoder for the }\textnormal{Puncturing of [11, 5] linear code over GF(7) on position(s) } [3] """
def generator_matrix(self): r""" Returns a generator matrix of the associated code of ``self``.
EXAMPLES::
sage: set_random_seed(10) sage: C = codes.random_linear_code(GF(7), 11, 5) sage: Cp = codes.PuncturedCode(C, 3) sage: E = codes.encoders.PuncturedCodePuncturedMatrixEncoder(Cp) sage: E.generator_matrix() [1 0 0 0 0 5 2 6 0 6] [0 1 0 0 0 5 2 2 1 1] [0 0 1 0 0 6 2 4 0 4] [0 0 0 1 0 0 6 3 3 3] [0 0 0 0 1 0 1 3 4 3] """
r""" Decoder decoding through a decoder over the original code of its punctured code.
INPUT:
- ``code`` -- The associated code of this encoder
- ``strategy`` -- (default: ``None``) the strategy used to decode. The available strategies are:
* ``'error-erasure'`` -- uses an error-erasure decoder over the original code if available, fails otherwise.
* ``'random-values'`` -- fills the punctured positions with random elements in ``code``'s base field and tries to decode using the default decoder of the original code
* ``'try-all'`` -- fills the punctured positions with every possible combination of symbols until decoding succeeds, or until every combination have been tried
* ``None`` -- uses ``error-erasure`` if an error-erasure decoder is available, switch to ``random-values`` behaviour otherwise
- ``original_decoder`` -- (default: ``None``) the decoder that will be used over the original code. It has to be a decoder object over the original code. This argument takes precedence over ``strategy``: if both ``original_decoder`` and ``strategy`` are filled, ``self`` will use the ``original_decoder`` to decode over the original code. If ``original_decoder`` is set to ``None``, it will use the decoder picked by ``strategy``.
- ``**kwargs`` -- all extra arguments are forwarded to original code's decoder
EXAMPLES::
sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7) sage: Cp = codes.PuncturedCode(C, 3) sage: codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp) Decoder of Puncturing of [15, 7, 9] Reed-Solomon Code over GF(16) on position(s) [3] through Error-Erasure decoder for [15, 7, 9] Reed-Solomon Code over GF(16)
As seen above, if all optional are left blank, and if an error-erasure decoder is available, it will be chosen as the original decoder. Now, if one forces ``strategy `` to ``'try-all'`` or ``'random-values'``, the default decoder of the original code will be chosen, even if an error-erasure is available::
sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7) sage: Cp = codes.PuncturedCode(C, 3) sage: D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp, strategy="try-all") sage: "error-erasure" in D.decoder_type() False
And if one fills ``original_decoder`` and ``strategy`` fields with contradictory elements, the ``original_decoder`` takes precedence::
sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7) sage: Cp = codes.PuncturedCode(C, 3) sage: Dor = C.decoder("Gao") sage: D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp, original_decoder = Dor, strategy="error-erasure") sage: D.original_decoder() == Dor True """
r""" TESTS:
If ``code`` is not a ``PuncturedCode``, an exception is raised::
sage: C = codes.random_linear_code(GF(7), 11, 5) sage: codes.decoders.PuncturedCodeOriginalCodeDecoder(C) Traceback (most recent call last): ... TypeError: code has to be an instance of PuncturedCode class
If one tries to pass an original_decoder whose associated code is not the original code of ``self``, it returns an error::
sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7) sage: Cp = codes.PuncturedCode(C, 3) sage: C2 = codes.GeneralizedReedSolomonCode(GF(7).list()[:6], 3) sage: D = Cp.decoder(original_decoder = C2.decoder()) Traceback (most recent call last): ... ValueError: Original decoder must have the original code of its associated punctured code as associated code
If one tries to use ``'error-erasure'`` strategy when the original code has no such decoder, it returns an error::
sage: C = codes.random_linear_code(GF(7), 11, 5) sage: Cp = codes.PuncturedCode(C, 3) sage: D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp, strategy = 'error-erasure') Traceback (most recent call last): ... ValueError: Original code has no error-erasure decoder """
raise TypeError("original_decoder must be a decoder object") strategy = 'error-erasure' error_erasure = True self._original_decoder = D(original_code, **kwargs) break else: self._original_decoder = original_code.decoder(**kwargs) self._original_decoder.connected_encoder())
r""" Returns a string representation of ``self``.
EXAMPLES::
sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7) sage: Cp = codes.PuncturedCode(C, 3) sage: D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp) sage: D Decoder of Puncturing of [15, 7, 9] Reed-Solomon Code over GF(16) on position(s) [3] through Error-Erasure decoder for [15, 7, 9] Reed-Solomon Code over GF(16)
"""
r""" Returns a latex representation of ``self``.
EXAMPLES::
sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7) sage: Cp = codes.PuncturedCode(C, 3) sage: D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp) sage: latex(D) \textnormal{Decoder of } Puncturing of [15, 7, 9] Reed-Solomon Code over GF(16) on position(s) [3] \textnormal{ through } Error-Erasure decoder for [15, 7, 9] Reed-Solomon Code over GF(16) """
r""" Returns the decoder over the original code that will be used to decode words of :meth:`sage.coding.decoder.Decoder.code`.
EXAMPLES::
sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7) sage: Cp = codes.PuncturedCode(C, 3) sage: D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp) sage: D.original_decoder() Error-Erasure decoder for [15, 7, 9] Reed-Solomon Code over GF(16) """
r""" Decodes ``y`` to an element in :meth:`sage.coding.decoder.Decoder.code`.
EXAMPLES::
sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7) sage: Cp = codes.PuncturedCode(C, 3) sage: D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp) sage: c = Cp.random_element() sage: Chan = channels.StaticErrorRateChannel(Cp.ambient_space(), 3) sage: y = Chan(c) sage: y in Cp False sage: D.decode_to_code(y) == c True """ y, e = y[0], y[1] e_list = e.list() e_list = _insert_punctured_positions(e_list, pts, one) else: elif self._strategy == 'try-all': end = False yl = y.list() I = iter(VectorSpace(F, len(pts))) list_pts = list(pts) list_pts.sort() shift = 0 for i in list_pts: yl.insert(i + shift, zero) shift += 1 values = next(I) while not end: try: shift = 0 for i in list_pts: yl[i + shift] = values[shift] shift += 1 y = A(yl) values = next(I) try: c_or = self.original_decoder().decode_to_code(y) end = True break except Exception: pass except StopIteration: raise DecodingError return _puncture(c_or, pts) A = Cor.ambient_space() yl = y.list() yl = _insert_punctured_positions(yl, pts) y = A(yl) return _puncture(D.decode_to_code(y), pts)
r""" Returns maximal number of errors that ``self`` can decode.
EXAMPLES::
sage: C = codes.GeneralizedReedSolomonCode(GF(16, 'a').list()[:15], 7) sage: Cp = codes.PuncturedCode(C, 3) sage: D = codes.decoders.PuncturedCodeOriginalCodeDecoder(Cp) sage: D.decoding_radius(2) 2 """ if D.decoding_radius() - punctured >= 0: return D.decoding_radius() - punctured else: return 0 raise ValueError("The number of erasures exceeds decoding capability") elif "error-erasure" in D.decoder_type() and number_erasures is None: raise ValueError("You must provide the number of erasures")
####################### registration ###############################
|