如何编写自己的编码理论类 ¶

本教程是为想要构建自己的类的高级用户设计的，它将一步一步地解释编写与编码理论框架很好地集成的代码需要做什么。在本教程中，我们将介绍以下部分：

如何编写新的 代码族
如何编写新的 编码器
如何编写新的 解码器
如何编写新的通道

在本教程中，我们将遵循相同的示例，即重复代码的实现。在每一部分的最后，我们将总结实施过程中的每一个重要步骤。如果一个人只想快速访问上面提到的某个对象的实现，可以直接跳到相关部分的末尾，该部分给出了要做什么的摘要。

如何编写自己的编码理论类

一、重复代码 ¶

我们想在Sage中实现众所周知的重复代码。其定义如下：

这个 \((n, 1)\) -重复代码结束 \(\GF{{q}}\) 代码是由 \(\GF{{q}}^{{n}}\) 形式的 \((i, i, i, \dots, i)\) 为了所有 \(i \in \GF{{q}}\) .

例如， \((3, 1)\) -重复代码结束 \(\GF{{2}}\) 是： \(C = \{{(0, 0, 0), (1, 1, 1)\}}\) .

编码非常简单，它只包含重复 \(n\) 乘以输入符号并选取这样形成的向量。

解码使用多数投票来选择正确的符号（结束 \(\GF{{2}}\) ). 如果我们收到消息 \((1, 0, 1)\) 最初的例子是我们推断的（续） \((1)\) . 它可以修正到 \(\left\lceil \frac{{n-1}}{{2}} \right\rceil\) 错误。

通过本教程，我们将演示 \((n, 1)\) -重复代码结束 \(\GF{{2}}\) .

二。编写新的代码类 ¶

编写新代码类的第一件事是标识以下元素：

密码的长度，
代码的基字段，
代码的默认编码器，
代码和的默认解码器
我们想在构建时设置的任何其他有用的参数。

对于我们的代码，我们知道它的长度、尺寸、基域、一个编码器和一个解码器。

现在我们隔离了代码的参数，我们可以编写类的构造函数。每个线性代码类都必须从 sage.coding.linear_code.AbstractLinearCode . 这个类提供了很多有用的方法，并且，正如我们后面所说明的，一个默认的构造函数设置长度 , the 基本字段 , the 默认编码器 以及 默认解码器 作为类参数。我们还需要为类创建已知编码器和解码器的字典。

现在让我们为代码类编写构造函数，它存储在一个名为 repetition_code.py ：：

sage: from sage.coding.linear_code import AbstractLinearCode
sage: from sage.rings.finite_rings.finite_field_constructor import FiniteField as GF
sage: class BinaryRepetitionCode(AbstractLinearCode):
....:     _registered_encoders = {}
....:     _registered_decoders = {}
....:     def __init__(self, length):
....:         super(BinaryRepetitionCode, self).__init__(GF(2), length,
....:           "RepetitionGeneratorMatrixEncoder", "MajorityVoteDecoder")
....:         self._dimension = 1

正如您所注意到的，构造函数非常简单。大部分的工作确实是由顶级管理人员通过 super 声明。请注意，维度不是由抽象类设置的，因为对于某些代码族，精确的维度很难计算。如果知道确切的尺寸，请使用 _dimension 作为类参数。

我们现在可以为代码类编写表示方法了：

sage: def _repr_(self):
....:     return "Binary repetition code of length %s" % self.length()
sage: def _latex_(self):
....:     return "\textnormal{Binary repetition code of length } %s" % self.length()

我们还编写了一个检查等式的方法：

sage: def __eq__(self, other):
....:     return (isinstance(other, BinaryRepetitionCode)
....:             and self.length() == other.length()
....:             and self.dimension() == other.dimension())

在这些例子之后，您可能注意到我们使用了两种方法，即 length() 和 dimension() 没有定义它们。这是因为它们的实现在 sage.coding.linear_code.AbstractLinearCode . 抽象类提供以下getter方法的默认实现：

sage.coding.linear_code.AbstractLinearCode.dimension()
sage.coding.linear_code.AbstractLinearCode.length() ，
sage.coding.linear_code.AbstractLinearCode.base_field() 和
sage.coding.linear_code.AbstractLinearCode.ambient_space() .

它还提供了 __ne__ 它返回 __eq__ 还有其他一些非常有用的方法，比如 __contains__ . 请注意，其他许多方法都依赖于生成器矩阵的计算。因此，强烈建议设置一个知道如何计算这样一个矩阵的编码器作为默认编码器。作为默认编码器将被所有这些方法使用，这些方法期望一个生成器矩阵，如果一个提供的默认编码器没有 generator_matrix 方法，很多泛型方法都会失败。

由于我们的代码族非常简单，我们不需要任何其他东西，上面提供的代码足以正确地描述重复代码。

线性码实现概述¶

继承自 sage.coding.linear_code.AbstractLinearCode .
添加 _registered_encoders = {{}} 和 _registered_decoders = {{}} 作为类变量。

在类的构造函数中添加以下行：

super(ClassName, self).__init__(base_field, length, "DefaultEncoder", "DefaultDecoder")

实施表示方法（不是强制性的，但高度建议） _repr_ 和 _latex_ .
实施 __eq__ .
__ne__ ， length 和 dimension 跟抽象课来。

请注意 dimension 不会工作，因为没有领域 _dimension 作为类参数。

我们现在知道了如何编写一个新的代码类。让我们看看如何编写一个新的编码器和一个新的解码器。

三、编写一个新的编码器类 ¶

让我们继续我们的例子。我们问的问题和以前一样：我们需要什么来描述编码器？对于大多数情况（包括本例），我们只需要关联的代码。在这种情况下，编写构造函数非常简单（我们将代码存储在相同的 .py 文件作为代码类）：：

sage: from sage.coding.encoder import Encoder
sage: class BinaryRepetitionCodeGeneratorMatrixEncoder(Encoder):
....:     def __init__(self, code):
....:         super(BinaryRepetitionCodeGeneratorMatrixEncoder, self).__init__(code)

和以前一样，因为编码器总是需要知道它的相关代码，所以工作可以由基类来完成。记住继承自 sage.coding.encoder.Encoder 你说什么？

我们还想重写表示方法 _repr_ 和 _latex_ ：：

sage: def _repr_(self):
....:     return "Binary repetition encoder for the %s" % self.code()
sage: def _latex_(self):
....:     return "\textnormal{Binary repetition encoder for the } %s" % self.code()

我们还想进行平等检查：

sage: def __eq__(self, other):
....:     return (isinstance(other, BinaryRepetitionCodeGeneratorMatrixEncoder)
....:             and self.code() == other.code())

如前所述，默认的getter方法由topclass提供，即 sage.coding.encoder.Encoder.code() .

我们所要做的就是实现与编码相关的方法。不管我们是否有生成器矩阵，这个实现都会有很大的变化。

我们有一个生成矩阵¶

在这种情况下，消息空间是一个向量空间，它特别容易：您需要实现的唯一方法是 generator_matrix .

继续我们的例子，它将是：

sage: def generator_matrix(self):
....:     n = self.code().length()
....:     return Matrix(GF(2), 1, n, [GF(2).one()] * n)

因为topclass为encode和逆操作提供了默认实现，我们调用 取消编码 （参见： sage.coding.encoder.Encoder.encode() 和 sage.coding.encoder.Encoder.unencode() )，以及的默认实现 sage.coding.encoder.Encoder.message_space() ，我们的工作完成了。

注解

违约 encode 方法将提供的字乘以生成器矩阵，而默认情况下 unencode 为生成器矩阵计算一个信息集，将其求逆并执行矩阵向量乘法以恢复原始消息。如果某个特定的代码族有更好的实现，那么显然应该覆盖默认值 encode 和 unencode .

我们没有矩阵发生器¶

在这种情况下，我们需要重写几个方法，即 encode ， unencode_nocheck 而且可能 message_space （在消息空间不是向量空间的情况下）。注意，默认实现 sage.coding.encoder.Encoder.unencode() 依赖于 unencode_nocheck ，所以没有必要重新实现前者。

在我们的例子中，很容易创建一个编码器，它不需要生成矩阵来执行编码和取消编码。我们建议如下实施：

sage: def encode(self, message):
....:     return vector(GF(2), [message] * self.code().length())

sage: def unencode_nocheck(self, word):
....:     return word[0]

sage: def message_space(self):
....:     return GF(2)

我们这里的工作完成了。

我们需要做一件额外的事情：在相关代码类的已知编码器字典中设置这个编码器。为此，只需在文件末尾添加以下行：

BinaryRepetitionCode._registered_encoders["RepetitionGeneratorMatrixEncoder"] = BinaryRepetitionCodeGeneratorMatrixEncoder

注解

如果您正在实现一个通用编码器（一个编码器可以与任何系列的线性代码一起工作），请在中添加以下语句 AbstractLinearCode 的构造函数改为： self._registered_encoders["EncName"] = MyGenericEncoder . 这将使它立即可用于继承自的任何代码类 AbstractLinearCode .

编码器实现概述¶

继承自 sage.coding.encoder.Encoder .

在类的构造函数中添加以下行：

super(ClassName, self).__init__(associated_code)

实现表示方法（非强制） _repr_ 和 _latex_ .
实施 __eq__
__ne__ ， code 跟抽象课来。
如果已知生成器矩阵，则重写 generator_matrix .
Else覆盖 encode ， unencode_nocheck 如果需要的话 message_space .
将编码器添加到 CodeClass._registered_encoders .

四、编写一个新的解码器类 ¶

让我们继续写一个解码器。和以前一样，我们需要知道描述解码器需要什么。我们当然需要解码器的相关代码。我们还想知道 Encoder 当我们试图从收到的包含错误的单词中恢复原始消息时，应该使用。我们称之为编码器 connected_encoder . 由于不同的解码算法不具有相同的行为（例如概率解码与确定性解码），我们想提供一些关于解码器类型的线索。所以我们可以在class参数中存储一个关键字列表 _decoder_type . 最后，我们还需要知道解码器的输入空间。通常，初始化这些参数可以委托给topclass，我们的构造函数如下所示：

sage: from sage.coding.decoder import Decoder
sage: class BinaryRepetitionCodeMajorityVoteDecoder(Decoder):
....:     def __init__(self, code):
....:         super((BinaryRepetitionCodeMajorityVoteDecoder, self).__init__(code,
....:            code.ambient_space(), "RepetitionGeneratorMatrixEncoder"))

记住继承自 sage.coding.decoder.Decoder 你说什么？

AS _decoder_type 实际上是一个类参数，应该在任何方法之外的文件中设置它。为了可读性，我们建议在文件底部添加此语句。我们一会儿再谈这个。

我们还想重写表示方法 _repr_ 和 _latex_ ：：

sage: def _repr_(self):
....:     return "Majority vote-based decoder for the %s" % self.code()
sage: def _latex_(self):
....:     return "\textnormal{Majority vote based-decoder for the } %s" % self.code()

我们还想进行平等检查：

sage: def __eq__(self, other):
....:     return isinstance((other, BinaryRepetitionCodeMajorityVoteDecoder)
....:           and self.code() == other.code())

和以前一样，默认的getter方法由topclass提供，即 sage.coding.decoder.Decoder.code() ， sage.coding.decoder.Decoder.input_space() ， sage.coding.decoder.Decoder.decoder_type() 和 sage.coding.decoder.Decoder.connected_encoder() .

我们只需要知道实现与解码相关的方法。

有两种方法，即 sage.coding.decoder.Decoder.decode_to_code() 和 sage.coding.decoder.Decoder.decode_to_message() .

由于默认实现的魔力，这两个是链接在一起的，如 decode_to_message 先打电话 decode_to_code 然后 unencode ，同时 decode_to_code 连续呼叫 decode_to_message 和 encode . 所以我们只需要实现其中的一个，我们选择重写 decode_to_code ：：

sage: def decode_to_code(self, word):
....:     list_word = word.list()
....:     count_one = list_word.count(GF(2).one())
....:     n = self.code().length()
....:     length = len(list_word)
....:     F = GF(2)
....:     if count_one > length / 2:
....:         return vector(F, [F.one()] * n)
....:     elif count_one < length / 2:
....:         return vector(F, [F.zero()] * n)
....:     else:
....:         raise DecodingError("impossible to find a majority")

注解

有人注意到，如果违约 decode_to_code 调用默认值 decode_to_message 和违约 decode_to_message 调用默认值 decode_to_code ，如果没有重写，并且调用了一个，它将最终陷入无限循环。我们添加了一个触发器保护来防止这种情况，因此，如果没有一个被重写并且调用了一个，则会引发一个异常。

只缺少一种方法：向用户提供解码器可以解码的错误数。这就是方法 sage.coding.decoder.Decoder.decoding_radius() ，我们覆盖：

sage: def decoding_radius(self):
....:     return (self.code().length()-1) // 2

在某些情况下，解码可能并不确切，其实现在 sage.coding.decoder.Decoder 的子类。

我们需要做一件额外的事情：在相关代码类的已知解码器字典中设置这个编码器。为此，只需在文件末尾添加以下行：

BinaryRepetitionCode._registered_decoders["MajorityVoteDecoder"] = BinaryRepetitionCodeMajorityVoteDecoder

也把这条线放在 decoder_type ：：

BinaryRepetitionCode._decoder_type = {"hard-decision", "unique"}

注解

如果您正在实现一个通用解码器（一个与任何线性代码族一起工作的解码器），请在中添加以下语句 AbstractLinearCode 的构造函数改为： self._registered_decoders["DecName"] = MyGenericDecoder . 这将使它立即可用于继承自的任何代码类 AbstractLinearCode .

解码器实现概述¶

继承自 sage.coding.decoder.Decoder .

在类的构造函数中添加以下行：

super(ClassName, self).__init__(associated_code, input_space, connected_encoder_name, decoder_type)

实现表示方法（非强制） _repr_ 和 _latex_ .
实施 __eq__ .
__ne__ ， code ， connected_encoder ， decoder_type 跟抽象课来。
重写 decode_to_code 或 decode_to_message 和 decoding_radius .
将编码器添加到 CodeClass._registered_decoders .

五、编写新通道类 ¶

除了所有这些与代码直接相关的新结构之外，我们还提出了一种全新的、闪亮的结构来对代码进行实验，更具体地说是对其解码。

实际上，我们实现了一种结构来模拟真实世界的通信信道。

例如，我将在这里建议一个虚拟通道的逐步实现。

我们将实现一个非常幼稚的通道，它只对单词over有效 \(\GF{{2}}\) 根据用户的要求和翻转次数。

由于通道与代码族不直接相关，而更多地与向量和单词相关，因此我们有一个特定的文件， channel.py 储存它们。

所以我们只需在这个文件中添加我们的新类。

首先，我们问自己一个永恒的问题：我们需要什么来描述一个频道？好吧，我们必须 input_space 及其 output_space . 当然，在大多数情况下，用户将能够提供一些关于频道行为的额外信息。在我们的例子中，它是要翻转的位数（也就是错误数）。

正如您可能已经猜到的，有一个抽象类来处理强制参数！另外，在我们的例子中，这个频道只对 \(\GF{{2}}\) ，输入和输出空间相同。让我们编写新通道类的构造函数：

sage: from sage.coding.channel import Channel
sage: class BinaryStaticErrorRateChannel(Channel):
....:     def __init__(self, space, number_errors):
....:         if space.base_ring() is not GF(2):
....:             raise ValueError("Provided space must be a vector space over GF(2)")
....:         if number_errors > space.dimension():
....:             raise ValueErrors("number_errors cannot be bigger than input space's dimension")
....:         super(BinaryStaticErrorRateChannel, self).__init__(space, space)
....:         self._number_errors = number_errors

记住继承自 sage.coding.channel.Channel 你说什么？

我们还想重写表示方法 _repr_ 和 _latex_ ：：

sage: def _repr_(self):
....:     return ("Binary static error rate channel creating %s errors, of input and output space %s"
....:             % (format_interval(no_err), self.input_space()))

sage: def _latex_(self):
....:     return ("\\textnormal{Static error rate channel creating %s errors, of input and output space %s}"
....:             % (format_interval(no_err), self.input_space()))

我们真的看不到等式方法的任何用例 (__eq__ 和 __ne__ )所以不要提供任何默认实现。如果需要这些，当然可以覆盖Python的默认方法。

我们当然需要getter方法。提供了的默认实现 input_space 和 output_space ，所以我们只需要一个 number_errors ：：

sage: def number_errors(self):
....:     return self._number_errors

所以，现在我们需要一个方法来给单词添加错误。因为这和在真实的信道上传输消息是一样的，我们提出两种方法， transmit 和 transmit_unsafe . 你可以猜到， transmit_unsafe 尝试在不检查消息是否在输入空间的情况下发送消息，而 transmit 在传输前检查这个。。。也就是说 transmit 有一个默认的实现调用 transmit_unsafe . 所以我们只需要覆盖 transmit_unsafe ! 让我们这样做：

sage: def transmit_unsafe(self, message):
....:     w = copy(message)
....:     number_err = self.number_errors()
....:     V = self.input_space()
....:     F = GF(2)
....:     for i in sample(range(V.dimension()), number_err):
....:         w[i] += F.one()
....:     return w

就这样，我们现在有了新的通道类可以使用了！

渠道实施总结¶

继承自 sage.coding.channel.Channel .

在类的构造函数中添加以下行：

super(ClassName, self).__init__(input_space, output_space)

实现表示方法（非强制） _repr_ 和 _latex_ .
input_space 和 output_space getter方法与抽象类一起提供。
重写 transmit_unsafe .

六、整理我们的新元素 ¶

由于编码理论库中有许多代码族和通道，我们不希望将所有类直接存储在Sage的全局命名空间中。

我们建议使用几个目录文件来存储我们的构造，即：

codes_catalog.py,
encoders_catalog.py,
decoders_catalog.py 和
channels_catalog.py.

每次创建一个新的文件夹时，都应该添加一个新的目录对象 all.py .

这里的意思是：

在中添加以下内容 codes_catalog.py ：

from sage.coding.repetition_code import BinaryRepetitionCode

在中添加以下内容 encoders_catalog.py ：

from sage.coding.repetition_code import BinaryRepetitionCodeGeneratorMatrixEncoder

在中添加以下内容 decoders_catalog.py ：

from sage.coding.repetition_code import BinaryRepetitionCodeMajorityVoteDecoder

在中添加以下内容 channels_catalog.py ：

from sage.coding.channel import BinaryStaticErrorRateChannel

七。本教程的完整代码 ¶

如果您需要一些基础代码来开始，请随意复制粘贴并从下面的代码中派生。

repetition_code.py （带两个编码器）：

from sage.coding.linear_code import AbstractLinearCode
from sage.coding.encoder import Encoder
from sage.coding.decoder import Decoder
from sage.rings.finite_rings.finite_field_constructor import FiniteField as GF

class BinaryRepetitionCode(AbstractLinearCode):

    _registered_encoders = {}
    _registered_decoders = {}

    def __init__(self, length):
        super(BinaryRepetitionCode, self).__init__(GF(2), length, "RepetitionGeneratorMatrixEncoder", "MajorityVoteDecoder")
        self._dimension = 1

    def _repr_(self):
        return "Binary repetition code of length %s" % self.length()

    def _latex_(self):
        return "\textnormal{Binary repetition code of length } %s" % self.length()

    def __eq__(self, other):
        return (isinstance(other, BinaryRepetitionCode)
           and self.length() == other.length()
           and self.dimension() == other.dimension())



class BinaryRepetitionCodeGeneratorMatrixEncoder(Encoder):

    def __init__(self, code):
        super(BinaryRepetitionCodeGeneratorMatrixEncoder, self).__init__(code)

    def _repr_(self):
        return "Binary repetition encoder for the %s" % self.code()

    def _latex_(self):
        return "\textnormal{Binary repetition encoder for the } %s" % self.code()

    def __eq__(self, other):
        return (isinstance(other, BinaryRepetitionCodeGeneratorMatrixEncoder)
           and self.code() == other.code())

    def generator_matrix(self):
        n = self.code().length()
        return Matrix(GF(2), 1, n, [GF(2).one()] * n)



class BinaryRepetitionCodeStraightforwardEncoder(Encoder):

    def __init__(self, code):
        super(BinaryRepetitionCodeStraightforwardEncoder, self).__init__(code)

    def _repr_(self):
        return "Binary repetition encoder for the %s" % self.code()

    def _latex_(self):
        return "\textnormal{Binary repetition encoder for the } %s" % self.code()

    def __eq__(self, other):
        return (isinstance(other, BinaryRepetitionCodeStraightforwardEncoder)
           and self.code() == other.code())

    def encode(self, message):
        return vector(GF(2), [message] * self.code().length())

    def unencode_nocheck(self, word):
        return word[0]

    def message_space(self):
        return GF(2)



class BinaryRepetitionCodeMajorityVoteDecoder(Decoder):

    def __init__(self, code):
        super(BinaryRepetitionCodeMajorityVoteDecoder, self).__init__(code, code.ambient_space(),
           "RepetitionGeneratorMatrixEncoder")

    def _repr_(self):
        return "Majority vote-based decoder for the %s" % self.code()

    def _latex_(self):
        return "\textnormal{Majority vote based-decoder for the } %s" % self.code()


    def __eq__(self, other):
        return (isinstance(other, BinaryRepetitionCodeMajorityVoteDecoder)
           and self.code() == other.code())

    def decode_to_code(self, word):
        list_word = word.list()
        count_one = list_word.count(GF(2).one())
        n = self.code().length()
        length = len(list_word)
        F = GF(2)
        if count_one > length / 2:
            return vector(F, [F.one()] * n)
        elif count_one < length / 2:
           return vector(F, [F.zero()] * n)
        else:
           raise DecodingError("impossible to find a majority")

    def decoding_radius(self):
        return (self.code().length()-1) // 2



BinaryRepetitionCode._registered_encoders["RepetitionGeneratorMatrixEncoder"] = BinaryRepetitionCodeGeneratorMatrixEncoder
BinaryRepetitionCode._registered_encoders["RepetitionStraightforwardEncoder"] = BinaryRepetitionCodeStraightforwardEncoder
BinaryRepetitionCode._registered_decoders["MajorityVoteDecoder"] = BinaryRepetitionCodeMajorityVoteDecoder
BinaryRepetitionCodeMajorityVoteDecoder._decoder_type = {"hard-decision", "unique"}

channel.py （续）：

class BinaryStaticErrorRateChannel(Channel):

    def __init__(self, space, number_errors):
        if space.base_ring() is not GF(2):
            raise ValueError("Provided space must be a vector space over GF(2)")
        if number_errors > space.dimension():
            raise ValueErrors("number_errors cannot be bigger than input space's dimension")
        super(BinaryStaticErrorRateChannel, self).__init__(space, space)
        self._number_errors = number_errors

    def _repr_(self):
      return ("Binary static error rate channel creating %s errors, of input and output space %s"
              % (format_interval(no_err), self.input_space()))

    def _latex_(self):
      return ("\\textnormal{Static error rate channel creating %s errors, of input and output space %s}"
              % (format_interval(no_err), self.input_space()))

    def number_errors(self):
      return self._number_errors

    def transmit_unsafe(self, message):
        w = copy(message)
        number_err = self.number_errors()
        V = self.input_space()
        F = GF(2)
        for i in sample(range(V.dimension()), number_err):
            w[i] += F.one()
        return w

codes_catalog.py （续）：

:class:`sage.coding.repetition_code.BinaryRepetitionCode <sage.coding.repetition_code.BinaryRepetitionCode>`
#the line above creates a link to the class in the html documentation of coding theory library
from sage.coding.repetition_code import BinaryRepetitionCode

encoders_catalog.py （续）：

from sage.coding.repetition_code import (BinaryRepetitionCodeGeneratorMatrixEncoder, BinaryRepetitionCodeStraightforwardEncoder)

decoders_catalog.py （续）：

from sage.coding.repetition_code import BinaryRepetitionCodeMajorityVoteDecoder

channels_catalog.py （续）：

from sage.coding.channel import (ErrorErasureChannel, StaticErrorRateChannel, BinaryStaticErrorRateChannel)

如何编写自己的编码理论类 ¶

一、重复代码 ¶

二。编写新的代码类 ¶

线性码实现概述¶

三、编写一个新的编码器类 ¶

我们有一个生成矩阵¶

我们没有矩阵发生器¶

编码器实现概述¶

四、编写一个新的解码器类 ¶

解码器实现概述¶

五、编写新通道类 ¶

渠道实施总结¶

六、整理我们的新元素 ¶

七。本教程的完整代码 ¶

Sage 中文文档

导航

Related Topics