论文标题
关于具有特征三的字段上线性索引编码的最佳性
On the Optimality of Linear Index Coding over the Fields with Characteristic Three
论文作者
论文摘要
众所周知，实现一般索引编码问题最佳速率的线性编码不足植根于其对场大小的依赖性。但是，这种依赖性仅通过两个众所周知的矩阵实例来描述，即Fano和非Fano Matroids，这反过来又将其范围限制在具有特征性的两个领域。在本文中，我们扩展了此范围，以证明线性索引编码率在特征三的字段上的依赖。通过构建两个尺寸29的索引编码实例，我们证明，对于首先，线性编码仅在特征三的字段上是最佳的，而对于第二个实例，在任何具有特征三的字段上的线性编码都不是最佳的。然后，第二个实例的变体被设计为大小58的第三个索引编码实例。在这种情况下，事实证明，虽然在任何特征三的字段上进行线性编码不能是最佳的，但在特征三的字段上存在非线性代码，从而实现了其最佳速率。通过两种特定方式连接第一个和第三个索引编码实例，称为No-Fay和Twie-way Connections，将导致两个新的索引编码实例87和91的新索引编码实例，其中线性编码均优于非线性代码。 本文的另一个主要贡献是将关键约束减少在第一个和第二个索引编码实例的线性编码空间上，每个索引编码实例，每个尺寸29的每个尺寸为29，都具有尺寸9的接地集，其线性表示性取决于具有特征性三的字段。本文通过使用这两个相对较小的矩阵实例提供的证明和讨论将阐明根本原因，从而导致线性编码不足以解决一般索引编码问题。
It has been known that the insufficiency of linear coding in achieving the optimal rate of the general index coding problem is rooted in its rate's dependency on the field size. However, this dependency has been described only through the two well-known matroid instances, namely the Fano and non-Fano matroids, which, in turn, limits its scope only to the fields with characteristic two. In this paper, we extend this scope to demonstrate the reliance of linear index coding rate on fields with characteristic three. By constructing two index coding instances of size 29, we prove that for the first instance, linear coding is optimal only over the fields with characteristic three, and for the second instance, linear coding over any field with characteristic three can never be optimal. Then, a variation of the second instance is designed as the third index coding instance of size 58. For this instance, it is proved that while linear coding over any field with characteristic three cannot be optimal, there exists a nonlinear code over the fields with characteristic three, which achieves its optimal rate. Connecting the first and third index coding instances in two specific ways, called no-way and two-way connections, will lead to two new index coding instances of size 87 and 91, for which linear coding is outperformed by nonlinear codes. Another main contribution of this paper is the reduction of the key constraints on the space of the linear coding for the first and second index coding instances, each of size 29, into a matroid instance with the ground set of size 9, whose linear representability is dependent on the fields with characteristic three. The proofs and discussions provided in this paper through using these two relatively small matroid instances will shed light on the underlying reason causing the linear coding to become insufficient for the general index coding problem.
