英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

附录A 译文

常维码的Johnson型界

夏树涛 · 符方伟

摘 要

最近，Koetter和Kschischang在研究随机网络编码时定义了算子信道.他们还引入了常维码，并证明这些码可用于纠正/擦除信道上的错误.常维码由Wang、Xing和Safavi-Naini在构建分布式认证系统时所提出.本文研究常维码.结果表明，斯坦纳结构是达到Wang-Xing-Safavi-Naini界的最优常维码.此外，我们还证明了当且仅当常维码是某些特定的斯坦纳结构时，常维码达到了Wang-Xing-Safavi-Naini界.然后，我们导出了常维码的两个Johnson型上界.最后，我们利用斯坦纳结构,得到了一族达到Johnson型界的最优常维码.

关键词 常维码；线性认证码；二元常重码；Johnson型界；斯坦纳结构；随机网络编码

1 介绍

在本文中，F_q表示具有q个元素的有限域，其中q是素数的幂.设W是F_q上的n维向量空间，设P(W)表示W的所有子空间的集合，对于任意A,Bisin;P(W)，表示

,

这是包含A和B的最小子空间.已知[1]A和B之间的维数距离定义为

(1)

(2)

是空间P(W)的一个度量.q元码(n，M，D)或(n，M，D)_qC只是P(W)的一个子集，其大小为M，最小维数距离D由下式定义

(3)

对于任意正整数l le; n，让P(W，l)表示的所有l维子空间的集合W.对于0 le; m le; n且q ge; 2的整数，设

表示q二项式系数或高斯二项式系数[2，第443-444页].众所周知，|P(W，l)| = n .一个q元(n，M，2delta;，l)或(n，M，2delta;，l)_q常维码只是(W，l)的子集，大小为M，最小维度距离为2delta;.请注意，通过(2)常维码的任意两个码字的维数距离必须是偶数且1 le; delta; le; l，一个 (n，M，ge; 2delta;，l)_q常维码是大小为M且最小维数距离至少为2delta;的P(W，l)的子集.对于固定数n，l，delta;，q，定义A_q [n，2delta;，l]为(n，M，ge; 2delta;，l)_q常维码中码字的最大个数M.如果M = A_q [n，2delta;，l]，则称（n，M，ge; 2delta;，l)_q常维码是最优的.常维码的主要研究问题之一是确定A_q [n，2delta;，l]并找到相应的最优常维码.

定义X^perp;为Xisin;P(W)的正交补码.对于任意两个l维子空间X,Y isin; P(W，l)，由于X^perp;cap;Y^perp;=(X Y)^perp;，我们有

(4)

设Csube;P(W，l)是一个(n，m，2delta;，l)_q常维码.然后通过(4)我们知道是一个(n，M，2delta;，n-l)_q常维码.这意味着

(5)

因此，我们只需要确定当l le; n/2时的A_q [n，2delta;，l].

研究随机网络编码时[3,4]，Koetter和Kschischang [1]定义了算子信道，并且发现可以使用(n，M，2delta;，l)_q常维码来纠正/擦除操作信道上的错误.在[1]中导出了A_q[n，2delta;，l]上的一些界，如Hamming型上界、Gilbert型下界和Singleton型上界。.众所周知，Hamming型界不是最优[1]并且不存在满足Hamming型界的完美的编码[5,6].[1]中提出的Singleton型界如下：

命题1 [1，定理3](Singleton型界)

.

此外，Koetter和Kschichang[1]设计了一类类里德-所罗门常维码，并给出了解码过程.他们表明，这些码都几乎达到了Singleton型界.

2003年，Wang、Xing和Safavi-Naini[7]在构建分布式认证系统时引入了所谓的线性认证码.[7，定理4.1]证明了(n，M，ge; 2delta;，l)_q常维码恰好是F_q上的[n，M，t = n-l，d = delta;]线性认证码.此外，他们建立了一个上限[7，定理5.2]在线性认证码上，它等价于常维码上的以下界限:

命题2 [7，定理5.2](Wang-Xing-Safavi-Naini界)

此外，Wang-Xing-Safavi-Naini[7]给出了线性认证码(或相应的常维码)的一些构造，它们渐近地接近这个界.

本文证明了斯坦纳结构是实现命题中的Wang-Xing-Safavi-Naini界的最优常维码2.此外，证明了当且仅当常维码是某些斯坦纳结构时，常维码达到Wang-Xing-Safavi-Naini界.导出了常维码的两个Johnson型上界，即Ⅰ和Ⅱ.Johnson型界Ⅱ在Wang-Xing-Safavi-Naini界的基础上稍有改进.观察到非平凡常维码的Ⅱ界总是优于Singleton型界.最后，我们指出一族已知的斯坦纳结构实际上是一族同时达到Johnson型界Ⅰ和Ⅱ的最优常维码.

2 斯坦纳结构

在这一节中，我们首先介绍了斯坦纳结构.然后我们证明了常维码达到Wang-Xing-Safavi-Naini界的充要条件是它们是某些斯坦纳结构.这意味着斯坦纳结构是最佳常维码.最后，我们描述了组合学中唯一已知的非平凡斯坦纳结构族.

回想一下，W是有限域F_q上的n维向量空间，并且(W，l)表示W的所有一维子空间的集合5.

定义1 [5] 如果W的每个t维子空间恰好包含在f的一个l维子空间中，则子集F sube; P(W，l)称为斯坦纳结构S[t，l，n]_q.f中的l维子空间称为斯坦纳结构S[t，l，n]_q的块.

命题3 [5] S[t，l，n]_q中的总块数是

下面我们说明斯坦纳结构是常维码.

命题4 当M=，时，斯坦纳结构S[t，l，n]_q是一个(n，M，2delta;，l)_q常维码.

证明： 通过定义1和命题3，我们只需要证明delta;= l -t 1.对于任意两个不同的块X，Y isin; S[t，l，n]_q，由于每个t维子空间恰好包含在S[t，l，n]_q的一个块中，所以我们有dim(Xcup;Y)le;t - 1.因此，通过(2)，d(X，Y)= 2l -2 dim(Xcup;Y)ge;2(l- t 1)，这意味着delta;ge;l- t 1.另一方面，设V是W的固定的(t-1)维子空间，选择W的两个t维子空间U₁和U₂，使得V = U₁cup;U₂.设X₁和X₂是S[tlt;

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[588287]，资料为PDF文档或Word文档，PDF文档可免费转换为Word