《Sage》中的编码理论

本教程面向那些想要了解如何将Sage用于他们在编码理论方面的工作(研究、实验、教学)的初学者，将介绍Sage的编码理论库的几个关键特性，并解释如何找到您正在寻找的类和方法。

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

• 你能用它做什么？ generic linear codes and associated methods ，

• 你能用它做什么？ structured code families ，

• 你能做些什么来 encode and recover messages, correct errors 和

• 你能做些什么来 easily add errors to codewords ，

• 你能用它做什么？ codes in general 。

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

I.一般线性码及其相关方法

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

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

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]

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

在上面的例子中，我们已经请求了代码的生成器矩阵。还可以向代码询问其基本参数：其 length 和 dimension 如下所示：

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

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

sage: C.minimum_distance()
3

当然，作为 C 是一般的线性代码，则运行穷举搜索算法来寻找最小距离，该最小距离将随着代码的增长而变得越来越慢。

只需键入代码的名称，我们就会得到一个简短描述它并给出它的参数的句子：：

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

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

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

• 或者查看文件的手册页 sage.coding.linear_code

• 或键入：：

  C.<tab>
  

  获取所有可用方法的列表 C 。然后，键入：：

  C.method?
  

  将显示以下项目的手册页 method 。

备注

一些通用方法需要安装Gap的可选程序包Guava。虽然做了一些工作以始终建议 does not 需要一个可选的包，有一些方法还不是最新的。如果您收到一条与Gap相关的错误消息，请查看该方法的文档以验证是否必须安装Guava。

二、结构化码族和编码和解码系统概览

II.1在Sage中创建特定代码

既然我们已经知道了如何创建泛型代码，我们想要更深入地创建特定的代码族。在Sage中，可以通过键入：：访问所有代码族

codes.<tab>

这样做，您将获得Sage可以构建的所有代码族的完整列表。

在本节的其余部分中，我们将通过操作 sage.coding.grs_code.GeneralizedReedSolomonCode 。

因此，对于初学者来说，我们想要创建一个通用的里德-所罗门(GRS)码。

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

codes.GeneralizedReedSolomonCode?

用户可以访问GRS代码的文档页面，找到这些代码的定义，并了解在Sage中构建GRS代码需要什么。

在这里，我们选择构建一个 [12, 6] GRS码已结束 \(\GF{13}\) 。要做到这一点，我们最多需要三个要素：

• 这个 list of evaluation points ，

• 这个 dimension of the code ，以及

• 可选的， list of column multipliers 。

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

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\) 是代码的维度。

因为塞奇知道 C 是一个GRS码，它不会运行第一节中提出的穷举搜索算法来查找 C 的最小距离，但使用上面介绍的操作。您会立即得到：：

sage: C.minimum_distance()
7

所有这些参数都汇总在代码的字符串表示中：：

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

备注

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

II.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

也许我们想要原版 message 返回而不是代码字。那么我们所要做的就是 unencode 它返回到消息空间：：

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

对编解码器结构的更深层次的了解

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

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

在核心部分，上述三个操作由 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() 也有一个重要的副作用： it caches the constructed encoder 在归还它之前。这意味着用户每次都将访问相同的 EvaluationVector 编码器，用于 C ，节省了施工时间。

对于解码者来说，上述所有事情都是相似的。这加强了编码器和解码器很少被构建，但被多次使用，这使得它们能够在构建或第一次使用时执行昂贵的预计算，以便将来使用。

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

III.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() 在代码本身上，如第一个示例所示，这将始终返回长度为代码维度的向量。

III.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 。每个Decoder也有这两个方法，代码上的方法只是将调用转发到该代码的默认解码器。

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

然而， 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

四、深入挖掘渠道

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

备注

再一次，我们选择了一个特定的类作为整个小节的运行示例，因为我们不想对所有频道进行详尽的分类。如果用户想要获取此列表，可以通过键入：：

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

用于错误和擦除的通道

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

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的传输字。第二个是擦除位置包含1的擦除向量。这一点反映在 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 删除了位置。

V.代码总则

到目前为止，我们只讨论了线性和超过汉明度量的代码。SAGE还支持非线性和/或基于不同度量的代码。由于使用这些类通常涉及创建新类，因此将在 如何编写自己的编码理论类 。

在本教程中，我们将包括一个小示例，说明线性码在秩度量上的应用。与汉明度量不同，在汉明度量中，两个字之间的距离是它们不同的位置的数量，而秩度量将距离视为两个码字的差异的排名，这两个码字表示为矩阵。

我们将在秩度量上创建一个通用的线性码，而不需要任何额外的结构。要构建这样的代码，我们只需要一个生成器矩阵：：

sage: G = Matrix(GF(4), [[1,1,0], [0,0,1]])
sage: C = codes.LinearRankMetricCode(G)

我们可以做我们在汉明度量上线性码的例子中所做的所有事情。因此，我们将重点关注不同的指标。

请在我们的代码中使用一个单词：：

sage: c = C[1]
sage: c
(1, 1, 0)

在通常的汉明度量上，这个词的权重将是 2 。然而，在排名度量上，我们得到了不同的结果：：

sage: C.rank_weight_of_vector(c)
1

单词在排名度量中的权重只是单词的矩阵形式的排名：：

sage: C.matrix_form_of_vector(c)
[1 1 0]
[0 0 0]

正如我们前面所说的，两个单词之间的距离是它们的差异的等级：：

sage: d = C[2]
sage: d
(z2, z2, 0)
sage: C.rank_distance_between_vectors(c, d)
1

即使这句话 c 和 d 两个位置不同，则它们在秩度量上的距离为 1 **

sage: C.matrix_form_of_vector(c - d)
[1 1 0]
[1 1 0]

有关线性秩度量代码的更多详细信息，请参阅 sage.coding.linear_rank_metric 。

六.结论--后记

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

阅读本文后，您应该知道如何在Sage中创建和操作代码！

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

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

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

codes.encoders.<tab>

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

codes.<tab>

并检查是否有与您的需求匹配的子类别。

尽管我们为此付出了艰苦的努力，但总有很多事情要做！

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