Sage编码理论

本教程专为那些希望了解如何使用Sage进行编码理论工作（研究、实验、教学）的初学者而设计，将介绍Sage的编码理论库的几个关键特性，并解释如何查找您要查找的类和方法。

在本教程中，我们将介绍以下部分：

• 你能用什么 一般线性码及其相关方法 ，

• 你能用什么 结构化代码族 ，

• 你能做什么 编码和恢复消息，纠正错误 和

• 你能做什么 很容易给代码添加错误 .

本教程的目标是快速概述如何使用库以及如何使用主要功能。它既不是对所有方法的全面描述，也不是对特定类的全面描述。如果需要一些与编码理论相关的类/方法行为的特定信息，那么应该查看该类/方法的文档。

目录

• Sage编码理论

  • 一、 一般线性码及其相关方法

  • 二。结构码族及其编解码系统概述

    • 二、 1在Sage中创建特定代码

    • 二、 2在Sage中编码和解码

  • 三、 更深入地了解编码器和解码器的结构

    • 三、 1个消息空间

    • 三、 2发电机矩阵

    • 三、 3个解码器和消息

  • 四、 更深入地看频道

    • 错误和删除的通道

  • 五、 结论-后记

一、 一般线性码及其相关方法

让我们从最通用的代码开始：没有任何特定结构的通用线性代码。

要构建这样的代码，只需提供它的生成器矩阵，如下所示：

sage: G = matrix(GF(3), [[1, 0, 0, 0, 1, 2, 1],
....:                    [0, 1, 0, 0, 2, 1, 0],
....:                    [0, 0, 1, 2, 2, 2, 2]])
sage: C = LinearCode(G)

有了这些行，你刚刚创建了一个线性代码，恭喜你！请注意，如果传递的矩阵不是满秩的，Sage将在构建代码之前将其转换为全秩矩阵，如下例所示：

sage: G = matrix(GF(3), [[1, 0, 0, 0, 1, 2, 1],
....:                    [0, 1, 0, 0, 2, 1, 0],
....:                    [0, 0, 1, 2, 2, 2, 2],
....:                    [1, 0, 1, 2, 0, 1, 0]]) #r3 = r0 + r2
sage: C = LinearCode(G)
sage: C.generator_matrix()
[1 0 0 0 1 2 1]
[0 1 0 0 2 1 0]
[0 0 1 2 2 2 2]

我们现在有一个线性代码。。。我们能用它做什么？因为我们可以做很多事情，让我们从基本功能开始。

在上面的例子中，我们已经要求输入代码的生成器矩阵。也可以向代码询问其基本参数：its 长度 和 维 如后所示：

sage: C.length()
7
sage: C.dimension()
3

也可以要求我们的代码的最小距离：

sage: C.minimum_distance()
3

当然，因为 C 是一个一般的线性码，一个穷尽式搜寻演算法来寻找最小距离，随着程式码的成长会越来越慢。

只需输入代码的名称，就可以得到一个简单描述代码并给出其参数的句子：

sage: C
[7, 3] linear code over GF(3)

由于本教程的目的不是全面介绍这些方法，因此我们将不描述任何其他方法。

如果想要获得所有可以在线性代码上运行的方法，可以：

• 或者检查文件的手册页 线性码

• 或类型：

  C.<tab>
  

  在Sage中获取所有可用方法的列表 C . 然后，输入：

  C.method?
  

  将显示的手册页 method .

注解

一些通用方法需要安装可选的Gap包Guava。虽然我们做了一些工作来始终提出一个默认的实现 不 需要一个可选的包，有些方法还不是最新的。如果您收到与Gap相关的错误消息，请检查该方法的文档，以验证是否必须安装Guava。

二。结构码族及其编解码系统概述

二、 1在Sage中创建特定代码

既然我们知道了如何创建通用的线性代码，我们想更深入地创建特定的代码族。在Sage中，可以通过键入以下命令访问所有代码族：

codes.<tab>

这样，您将得到Sage可以构建的所有代码系列的综合列表。

在本节的其余部分中，我们将通过操作来说明这些代码族的特定功能 sage.coding.grs_code.GeneralizedReedSolomonCode .

因此，首先，我们要创建一个通用的Reed-Solomon（GRS）代码。

单击上面提供的链接，或键入：

codes.GeneralizedReedSolomonCode?

您可以访问GRS代码的文档页面，找到这些代码的定义，并了解在Sage中构建GRS代码所需的内容。

在这里我们选择建立一个 [12，6] GRS代码结束 \(\GF{{13}}\) . 为此，我们最多需要三个元素：

• 这个 评价点一览表 ，

• 这个 代码的维度 和

• 或者 列乘数列表 .

我们按照如下方式构建代码：

sage: F = GF(13)
sage: length, dimension = 12, 6
sage: evaluation_pts = F.list()[:length]
sage: column_mults = F.list()[1:length+1]
sage: C = codes.GeneralizedReedSolomonCode(evaluation_pts, dimension, column_mults)

我们的GRS代码现在已经创建。我们可以询问它的参数，就像我们在上一节中所做的那样：

sage: C.length()
12
sage: C.dimension()
6
sage: C.base_ring()
Finite Field of size 13

也可以通过调用 sage.coding.grs_code.GeneralizedReedSolomonCode.evaluation_points() 和 sage.coding.grs_code.GeneralizedReedSolomonCode.column_multipliers() .

现在，如果你知道GRS码的一些理论，你知道计算它们的最小距离特别容易，即： \(d = n - k + 1\) 在哪里 \(n\) 是代码的长度 \(k\) 是代码的维度。

因为Sage知道 C 是一个GRS代码，它不会运行第一节介绍的穷尽搜索算法来查找 C 的最小距离，但使用上面介绍的操作。你马上就会得到：

sage: C.minimum_distance()
7

所有这些参数都在代码的字符串表示形式中进行了总结：

sage: C
[12, 6, 7] Generalized Reed-Solomon Code over GF(13)

注解

为代码族编写适当的类是一项正在进行的工作。一些建筑 codes.<tab> 因此可能是构建通用线性代码的函数，在这种情况下只能使用泛型算法。请参考一个构造的文档来检查它是一个函数还是一个类。

二、 2在Sage中编码和解码

在上一部分中，我们学习了如何在Sage中找到特定的代码族并创建这些族的实例。

在这一部分，我们将学习如何编码和解码。

首先，我们想生成一个可以玩的码字。有两种不同的方法：

• 可以只生成代码的随机元素，如下所示：

  sage: c = C.random_element()
  sage: c in C
  True
  

• 或者，我们可以创建一条消息，然后将其编码为码字：

  sage: msg = random_vector(C.base_field(), C.dimension())
  sage: c = C.encode(msg)
  sage: c in C
  True
  

不管怎样，我们得到了一个密码。因此，我们可能需要在其中加入一些错误，然后尝试更正这些错误。显然，我们可以通过改变码字的一些随机位置的值来实现这一点，但是我们在这里提出了更一般的方法：通信信道。 sage.coding.channel.Channel 对象是指通信通道和数据表示操作的抽象。在这种情况下，我们要模拟一个通信信道，它会给一个传输的字添加一些错误，但不会太多：

sage: err = 3
sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(), err)
sage: Chan
Static error rate channel creating 3 errors, of input and output space Vector space of dimension 12 over Finite Field of size 13
sage: r = Chan.transmit(c)
sage: len((c-r).nonzero_positions())
3

如果您想了解更多有关频道的信息，请参阅本教程的第四节。

多亏了我们的频道，我们收到了“收到的消息”， r ，作为一个有错误的码字。我们可以尝试更正错误并恢复原始码字：

sage: c_dec = C.decode_to_code(r)
sage: c_dec == c
True

也许我们想要原版 消息 而不是密码。我们要做的就是 取消编码 返回到消息空间：

sage: m_unenc = C.unencode(c_dec)
sage: m_unenc == msg
True

还可以在一行中执行前面的两个操作（更正错误并恢复原始消息），如下所示：

sage: m_unenc2 = C.decode_to_message(r)
sage: m_unenc2 == msg
True

三、 更深入地了解编码器和解码器的结构

在上一节中，我们看到了直接在code对象上使用方法可以轻松地对向量进行编码、解码和取消编码。这些方法实际上是为了可用性而添加的快捷方式，因为当人们不关心编码和解码是如何发生的时候。然而，在某些时候，人们可能需要更多的控制。

因此，本节将详细介绍编码器和解码器的机制。

在核心，上述三个操作由 sage.coding.encoder.Encoder 和 sage.coding.decoder.Decoder . 这些对象有自己的方法来操作单词。打电话时（如上所示）：

C.encode(msg)

一个实际调用方法 sage.coding.encoder.Encoder.encode() 在的默认编码器上 C . 它可以拥有一个编码器和解码器的每一个使用清单。让我们看看如何探索这个问题：

sage: C = codes.GeneralizedReedSolomonCode(GF(59).list()[:40], 12, GF(59).list()[1:41])
sage: C.encoders_available()
['EvaluationPolynomial', 'EvaluationVector', 'Systematic']
sage: C.decoders_available()
['BerlekampWelch',
 'ErrorErasure',
 'Gao',
 'GuruswamiSudan',
 'InformationSet',
 'KeyEquationSyndrome',
 'NearestNeighbor',
 'Syndrome']

我们得到了一份GRS代码可用的编码器和解码器的列表。我们现在可以要求特定的编码器和解码器，而不是像以前那样使用默认的：

sage: Evect = C.encoder("EvaluationVector")
sage: Evect
Evaluation vector-style encoder for [40, 12, 29] Generalized Reed-Solomon Code over GF(59)
sage: type(Evect)
<class 'sage.coding.grs_code.GRSEvaluationVectorEncoder'>
sage: msg = random_vector(GF(59), C.dimension()) #random
sage: c = Evect.encode(msg)
sage: NN = C.decoder("NearestNeighbor")
sage: NN
Nearest neighbor decoder for [40, 12, 29] Generalized Reed-Solomon Code over GF(59)

打电话：：

C.encoder(encoder_name)

实际上是通过调用 sage.coding.grs_code.EncoderGRSEvaluationVector 你自己。如果你不供应 encoder_name 到 sage.coding.linear_code.AbstractLinearCode.encoder() 你得到代码的默认编码器。 sage.coding.linear_code.AbstractLinearCode.encoder() 还有一个重要的副作用： 它缓存构造的编码器 在归还之前。这意味着每次访问都是相同的 EvaluationVector 编码器 C ，节省施工时间。

以上这些对于解码器来说都是相似的。这加强了编码器和解码器很少被构造，而是被多次使用，这使得它们能够在构造或首次使用时执行昂贵的预计算，以利于将来的使用。

这就很好地了解了元素是如何在内部工作的。现在让我们更详细地讨论一下具体问题。

三、 1个消息空间

编码器的作用是将信息编码成代码。这些消息通常只是代码基字段上的向量，其长度与代码的维度匹配。但它可以是任何东西：向量在其他领域，多项式，甚至是完全不同的东西。因此，每个编码器都有一个 sage.coding.encoder.Encoder.message_space() . 例如，我们在前面看到GRS代码有两个可能的编码器；让我们研究一下我们在前面部分中留下的一个：

sage: Epoly = C.encoder("EvaluationPolynomial")
sage: Epoly
Evaluation polynomial-style encoder for [40, 12, 29] Generalized Reed-Solomon Code over GF(59)
sage: Epoly.message_space()
Univariate Polynomial Ring in x over Finite Field of size 59
sage: msg_p = Epoly.message_space().random_element(degree=C.dimension()-1); msg_p #random
31*x^11 + 49*x^10 + 56*x^9 + 31*x^8 + 36*x^6 + 58*x^5 + 9*x^4 + 17*x^3 + 29*x^2 + 50*x + 46

Epoly 反映了GRS码通常被构造成多项式的求值，而考虑其信息的一种自然方式至多是次数多项式 \(k-1\) 在哪里 \(k\) 是代码的维度。注意消息空间 Epoly 都是一元多项式： message_space 是消息的环境空间，有时编码器要求消息实际上是从其中的一个子空间中选取的。

代码的默认编码器总是有一个向量空间作为消息空间，因此当我们调用 sage.coding.linear_code.AbstractLinearCode.decode_to_message() 或 sage.coding.linear_code.AbstractLinearCode.unencode() 对于代码本身，如第一个示例所示，这将始终返回长度为代码维数的向量。

三、 2发电机矩阵

每当编码器的消息空间是向量空间并且它使用线性映射进行编码时，编码器将拥有一个生成器矩阵（注意，这个概念对于其他类型的编码器没有意义），它指定线性映射。

生成器矩阵被放置在编码器对象上，因为一个代码有许多生成器矩阵，并且每一个都将以不同的方式对消息进行编码。你也会发现 sage.coding.linear_code.AbstractLinearCode.generator_matrix() 对于代码对象，但这还是一个简单的方法，它将查询转发到默认编码器。

让我们在Sage中看到这一点，使用我们构建的第一个编码器：

sage: Evect.message_space()
Vector space of dimension 12 over Finite Field of size 59
sage: G = Evect.generator_matrix()
sage: G == C.generator_matrix()
True

三、 3个解码器和消息

正如我们之前看到的，任何代码都有两个通用的解码方法，称为 decode_to_codeword 和 decode_to_message . 每个解码器也有这两个方法，代码上的方法只是将调用转发给该代码的默认解码器。

使用这两种方法有两个原因：方便和快速。方便性很明显：根据用户的需要，同时使用这两种方法可以提供一种有用的快捷方式。关于速度，有些解码器自然地直接解码到码字，而有些则直接解码到消息空间。因此，支持这两种方法可以避免不必要的编码和取消编码工作。

然而， decode_to_message 意味着有一个消息空间和从该空间到后台代码的编码。解码器有方法 message_space 和 connected_encoder 告诉用户这一点。让我们用一个很长的例子来说明：

sage: C = codes.GeneralizedReedSolomonCode(GF(59).list()[1:41], 3, GF(59).list()[1:41])
sage: c = C.random_element()
sage: c in C
True

#Create two decoders: Syndrome and Gao
sage: Syn = C.decoder("KeyEquationSyndrome")
sage: Gao = C.decoder("Gao")

#Check their message spaces
sage: Syn.message_space()
Vector space of dimension 3 over Finite Field of size 59
sage: Gao.message_space()
Univariate Polynomial Ring in x over Finite Field of size 59

#and now we unencode
sage: Syn.decode_to_message(c) #random
(55,9,43)

sage: Gao.decode_to_message(c) #random
43*x^2 + 9*x + 55

四、 更深入地看频道

在第二节中，我们简要介绍了通道对象作为一种将错误放入单词中的方法。在本节中，我们将更深入地了解它们的功能并介绍第二个通道。

注解

再一次，我们选择了一个特定的类作为运行示例，因为我们不想对所有通道进行详尽的目录。如果你想得到这个列表，你可以通过输入：

channels.<tab>

在萨奇。

再考虑一下 sage.coding.channel.ChannelStaticErrorRate() 从以前开始。这是一个信道，它将错误放在传输的向量中，但在受控边界内。我们可以用两种方式来描述这些边界：

• 第一种方法在第二节中进行了说明，包括传递一个整数，如下所示：

  sage: C = codes.GeneralizedReedSolomonCode(GF(59).list()[:40], 12)
  sage: t = 14
  sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(), t)
  sage: Chan
  Static error rate channel creating 14 errors, of input and output space Vector space of dimension 40 over Finite Field of size 59
  

• 我们也可以传递两个整数的元组，第一个比第二个小。然后，每次发送一个字时，这两个整数之间的随机错误数将相加：

  sage: t = (1, 14)
  sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(), t)
  sage: Chan
  Static error rate channel creating between 1 and 14 errors, of input and output space Vector space of dimension 40 over Finite Field of size 59
  

我们已经知道一个频道有一个 sage.coding.channel.Channel.transmit() 方法，它将在通道上执行传输；在这种情况下，它将返回包含一些错误的已发送字。此方法将始终检查所提供的字是否属于通道的输入空间。在一个情况下，一个人绝对肯定自己的字是在输入空间，可能要避免这种检查，这是很耗时的-特别是如果一个人是模拟数百万的传输。这种用法有 sage.coding.channel.Channel.transmit_unsafe() 它的作用与 sage.coding.channel.Channel.transmit() 但不检查输入，如下所示：

sage: c = C.random_element()
sage: c in C
True
sage: c_trans = Chan.transmit_unsafe(c)
sage: c_trans in C
False

注意有一个有用的快捷方式 sage.coding.channel.Channel.transmit() ：：

sage: r = Chan(c)
sage: r in C
False

错误和删除的通道

让我们介绍一个新的通道对象，它添加了错误和擦除。当它传输一个单词时，它既增加了一些错误，也删除了一些位置：

sage: Chan = channels.ErrorErasureChannel(C.ambient_space(), 3, 4)
sage: Chan
Error-and-erasure channel creating 3 errors and 4 erasures of input space Vector space of dimension 40 over Finite Field of size 59 and output space The Cartesian product of (Vector space of dimension 40 over Finite Field of size 59, Vector space of dimension 40 over Finite Field of size 2)

第一个参数是通道的输入空间。接下来的两个分别是错误数和删除数。每一个都可以是元组，就像以前一样 sage.coding.channel.StaticErrorRateChannel . 与此通道相反 sage.coding.channel.ErrorErasureChannel 与输入空间不同，即C的环境空间。相反，它将返回两个向量：第一个是发送的字，其错误添加和删除位置设置为0。第二种是擦除向量，其擦除位置包含一个。这反映在 sage.coding.channel.output_space() ：：

sage: C = codes.random_linear_code(GF(7), 10, 5)
sage: Chan.output_space()
The Cartesian product of (Vector space of dimension 40 over Finite Field of size 59, Vector space of dimension 40 over Finite Field of size 2)
sage: Chan(c) # random
((0, 3, 6, 4, 4, 0, 1, 0, 0, 1),
 (1, 0, 0, 0, 0, 1, 0, 0, 1, 0))

注意，它是由构造保证的，错误和删除永远不会重叠，所以当你要求 e 错误和 t 删除，你将始终收到一个向量 e 错误和 t 删除的位置。

五、 结论-后记

最后一节结束了我们关于编码理论的教程。

读完这篇文章之后，你应该知道如何在Sage中创建和操作代码！

在本教程中，我们没有说明库的所有内容。例如，我们没有提到Sage如何管理代码的边界。

所有与编码理论相关的对象、结构和方法都隐藏在前缀之下 codes 在萨奇。

例如，可以通过键入以下命令找到所有可以构建的编码器：

codes.encoders.<tab>

因此，如果要查找与代码相关的特定对象，则应始终键入：

codes.<tab>

并检查是否有符合您需要的子类别。

尽管我们做了很多努力，但总有很多事情要做！

也许在某个时候你可能想为Sage创建自己的代码。如果是这样，如果你不知道怎么做，不要惊慌！我们还为这个具体案例编写了一个教程，您可以在这里找到： 如何编写自己的编码理论类 .