论文部分内容阅读
摘要：网络编码对网络中的传输错误或恶意攻击十分敏感，如果网络拓扑和网络码对于网络的收点和发点都是已知的，这种类型的网络称为Coherent网络。在Coherent网络中，网络汉明重量的概念拉近了网络纠错码和传统纠错码之间的距离，传统纠错码的一些理论和方法有望在将来应用于网络纠错码。类似于传统纠错码，极小距离反映了网络纠错码的纠错能力。利用陪集码理论去描述和研究网络纠错码是一个令人感兴趣的研究方向。
关键词：网络纠错码；Coherent网络；网络汉明重量；最小距离；最大码字数
Abstract: Network coding is very sensitive to the transmission errors or malicious attacks in network. If the knowledge of network topology and network code is known at the source and destination codes, the network is called coherent. In coherent network, the concept of network Hamming weight narrows the gap between network error-correcting codes and classical error-correcting codes. Some theories and methods in classical error-correcting codes have chances to be applied to network error-correcting codes in the future. Similar to classical error-correcting codes, minimum distance characterizes the error-correcting capability of network error-correcting codes. Employing the theories of coset codes to describe and study network error-correcting codes is an interesting research topic.
Key words: network error correction codes; coherent network; network Hamming weight; minimum distance; maximum number of code words
网络编码[1]由于可以提升网络的传输效率而得到了人们的广泛研究，但网络编码对网络中的传输错误或恶意攻击十分敏感，一个关键性错误足以导致译码失败，这引发了对网络纠错码的研究。文献[2-4]提出了网络纠错码的基础概念。
1 Coherent网络模型
设G =(V,E)为一个有向无环网络，其中V表示节点集，E表示边集。由G的无环特性，我们可对E中所有的边进行排(偏)序并编号，例如：E={eｉ:i =1……|E|}，这些编号与稍后定义的矩阵的行或列一一对应。
如果存在从节点a∈V到节点b∈V的一条有向边e∈E，则称tail(e)=a，head(e )=b，并定义In(a)={e:head(e)=a, e∈E}为a所有入边的集合，Out(a)={e:tail(e)=a, e∈E}为a所有出边的集合。
设Fq 是一个包含q (其中q为素数幂)个元素的有限域，E中每条边的容量都为1，即在单位时间内每条边只能传输Fq 中的一个元，但一对节点之间可以存在多条边。本文只考虑单源情形，设s∈V为单源发点，T ?哿V \{s}为收点集合。设需要传送的信息为Fq上的ω维行向量x=(x 1,x 2……xω)，其分量位置分别对应单源节点s的ω条虚拟输入信道，用In(s)表示，注意ω=|In(s)|且In(s)∩E=φ。
设n s=|Out(s)|, 单位时间内发点s发送出去的信息可表示为n s维行向量，称之为码字，用c=(c 1,c 2……cn)表示，表示码字集。设发点s的局部编码核矩阵是ω×|E|的矩阵K(s)=[k d,e:d∈In(s),e∈E]，当e?埸Out(s)时k d,e=0。定义n s×|E|矩阵A=[Aij ]在ej为Out(s)的第i 条边时为1，否则为0。注意A的非0列构成一个n s×n s置换矩阵。信息字x与码字c存在如下的关系：xK(s)=cA，设网络G的局部编码核为{k e,e':e,e'∈E}，定义|E|×|E|一步转移矩阵K=[ｋij]在存在节点a使得ei∈In(a),
ej∈Out(a)时为k ei,ej，否则为0。
网络G中包含|E|条边，每条边都可能出现传输错误，我们用一个|E|维行向量 z=(z 1,z 2……z |E |)来表示网络中发生的错误，简称错误向量，其分量zi∈Fq表示边ei上发生的错误偏移，
zi =0表示该边没有发生错误。一个向量的支撑定义为该向量的非零分量位置的集合，错误向量z的支撑称为错误模式，记为ρz，显然，ρz?哿E。一般来说，E的任何一个子集ρ都可称作差错模式，表示网络中的错误只在ρ中的边上发生。
一个线性网络码由发点s的局部编码核矩阵K(s)和一步转移矩阵K给出，记为{ K(s), K}线性网络码，注意此时码字集ｃ构成一个q元[n s,ω]传统线性码。如果不使用K(s)而任意选取的一个子集作为码字集ｃ，此时称{ｃ,K}为一个网络码。由文献[5]知，对于网络G 和一步转移矩阵K，必存在正整数N使得K N=0成立。定义网络G上|E|×|E|的全局转移矩阵为：F=(I-K)-1= I+K……K N-1，其中I表示|E|×|E|单位矩阵。
如果网络拓扑和网络码对于网络的收点和发点都是已知的，这种类型的网络称为Coherent网络，本文假定网络G是一个Coherent网络。设t∈T为一个收点，设n t=|In(t)|为t的入边数目。定义|E|×n t矩阵Bt=[Bij]在ej为In(s)的第i 条边时为1，否则为0，注意Bt的非0行构成一个n t×n t置换矩阵。收点t接收到的信息可表示为Fq上的一个n t维行向量，通常记为y t。由文献[6-9]知，如果网络中没有错误发生，则y t=xK(s)FB；否则设z为错误向量，则y t=(cA+z)FBt=cFs,t+zFt，或表示为y t=(xK(s)+z)FBt=(x,z)F't。其中Fs,t＝AFBt, Ft＝FBt, 。易知Ft是F的子矩阵，Ft的列对应In(t)中的边；Fs,t是Ft的子矩阵，Fs,t的行对应Out(s)中的边。显而易见，这两种表示方法是等价的，在讨论译码时前者使用起来更为方便，在讨论网络纠错码与传统纠错码的联系时后者使用起来更胜一筹。
2 网络汉明重量和极小距离
类似于传统纠错码，极小距离也反映了网络纠错码的纠错/检错能力。文献[6]和文献[7]两文分别定义了网络纠错码的极小距离，虽然表示方法不同，但实际上是等价的。
2.1 网络汉明重量
文献[6]提出了网络汉明重量的概念，这拉近了网络纠错码和传统纠错码之间的距离，使得传统纠错码的很多理论和方法有望在将来可以更容易地应用于网络纠错码之中。
由上文可知，F满秩，故Ft列满秩。任给y∈，令γ(y)={z∈ :zFt=y}。因为Ft列满秩，所以γ(0)是一个(|E|-n t)维线性子空间，γ(y)是γ(0)的一个陪集。对收点t，接收向量y、错误向量z和码字向量c的网络汉明重量分别定义如下：
Wtrec(y)=min{WH(z):z∈γ(y)},
Wteer(z)=Wtrec(zFt),
Wtcod(z)=Wtrec(cFS,t).
其中WH(•)表示向量的汉明重量。对收点t，相应的网络汉明距离定义为：
D trec(y,y')=Wtrec(y-y'),
D tcod(c,c')=Wtcod(c-c').
从而定义网络码{C,K }的单播极小距离为d min,t=min{D tcod(c,c'):?坌c≠c'∈C },单播极小距离还可写成以下更为直接的形式：d min,t=min{WH(z):zFt=(c-c')Fs,t, ?坌c≠c'∈C }。
考虑以下退化情形，网络G 中只有一个发点s和一个收点t, 并且s与t之间恰有n条边相连。容易看出，此时K=0, F=Ft=FS,t=I，从而网络汉明重量退化为汉明重量，网络纠错码退化为一个码长为n 的传统纠错码。由此可知，网络纠错码是传统纠错码的推广。对于收点集T，网络码{C,K}的组播极小距离定义为dmin=min{dmin,t:t∈T }，错误向量或码字的网络汉明重量不超过其汉明重量，即Wteer(z)≤WH(z),Wtcod(c)≤WH(c)。
另外，网络汉明距离满足对称性和三角不等式。
类似于传统纠错码，极小距离反映了网络纠错码的纠错能力。考虑以下最小距离译码准则：给定接收向量yt，查找c∈C使得cFs,t与yt的网络汉明距离最小，即 ，由此容易证明定理1。
定理1 对于收点和单播极小距离，以下结论等价：{C,K}的单播极小距离满足dmin,t≥d；若错误向量z满足Wteer(z)≤(d -1)/2，则{C,K}能纠正该错误；若错误向量z满足WH(z) ≤(d -1)/2，则{C,K}能纠正该错误；若错误向量z满足0＜Wteer(z)≤d -1，则{C,K}能检测该错误；若错误向量z满足0＜WH(z)≤d -1，则{C,K}能检测该错误。对于组播情形，也可得出类似结论。
2.2 极小秩
在文献[7]中，错误模式的秩被用来定义单播极小距离，(ω+|E|)×n t矩阵F't的前ω行张成一个线性子空间Φ(t)，即：Φ(t)={(x,0)F't:x∈Fqω}。
F't的后|E|行对应E的每一条边，设ρ?哿E为一个错误模式，F't中对应ρ的行张成一个线性子空间，用Δ(t,ρ)表示，即：Δ(t,ρ)={(0,z)F't:z∈, ρz?哿ρ}。
设ρ、ρ'为两个错误模式，如果对于收点t成立Δ(t,ρ) Δ(t,ρ')，则称ρ'关于t决定ρ，记作ρ?刍tρ'。错误模式ρ关于收点t的秩(rank)定义为rankt(ρ)=min{|ρ'|: ρ?刍tρ'}。
线性网络码{K(s),K}的(单播)极小秩被定义为dmin(t)=min{rankt(ρ):dim(Δ(t,ρ)∩Φ(t))＞0}。
众所周知，在传统纠错码理论中，线性码的极小距离等于最小重量，从而极小距离等于一个码字成为另一个码字所需要变更的最小位置数目。我们可以从这个角度去理解极小秩dmin(t)，当存在一个错误模式ρ使得dim(Δ(t,ρ)∩Φ(t))＞0时，表示一个码字受到错误向量的影响成为了另一个码字。Zhang进一步证明了极小秩扮演了与传统纠错码极小距离类似的角色，即：一个极小秩等于dmin(t)的线性网络码可以检测dmin(t)-1个错误或纠正(dmin(t)-1)/2个错误。
令Ct=maxflow(s,t)表示从发点s到收点t的网络最大流，δt=Ct-ω称为收点的冗余，一个极小秩等于冗余加1的线性网络码称为最大距离可分(MDS)线性网络码。文献[7] 给出的定理2说明：当q足够大时，MDS线性网络码存在。
定理2 当q＞时，必然存在Fq上的线性网络码{K(s),K}，使得对于所有t∈T 都有dmin(t)=δt +1成立。
定理3证明了单播极小距离与单播极小秩的等价性。
定理3 dmin(t)=dmin,t。
从以上的介绍我们看到两种极小距离的定义殊途同归，只是表达方式存在差异。对于具有传统纠错码背景的读者，网络汉明重量的引入会使得网络纠错码理论变得更容易理解，极大地拉近了网络纠错码与传统纠错码之间的距离。尽管如此，我们认为网络纠错码的数学表示仍有改进之处，例如：γ(0)是一个(|E|-n t)维线性子空间，γ(y)是γ(0)的一个陪集，容易知道，位于同一个陪集的错误向量是等价的；同样的思想在码字集所在的空间 中也可以应用，故码字集C的构造问题本质上是陪集的选择问题，这启示我们采用陪集码的理论框架去研究网络纠错码。
3 最大码字数的上界和下界
给定一个具有单源发点s、收点集T和固定拓扑的网络G, 每一个收点的最大流值可由快速算法求出。如何选择局部编码核矩阵K和码字集C, 使得在保证一定纠错性能的条件下网络的传输效率最高，就是网络码{C,K}的一般构造问题，给定正整数d, 定义最大码字数为M(d )=max{|C|:dmin≥d }，达到最大码字数的网络码{C,K}称为最优网络码。
如果进一步固定局部编码核矩阵K和收点t∈T (此时F、Ft和Fs,t都已固定)，如何选择码字集C使得在保证一定纠错性能的条件下从s到t的传输效率最高，就是网络码{C,K}的单播构造问题。给定正整数d, 定义单播最大码字数为M t(d,K)=max{|C|:dmin,t≥d }，达到最大码字数的网络码{C,K}称为关于t的单播最优网络码。
定理4 设G为一个单源网络，d为正整数。
汉明界：令 ,n =mint∈T maxflow
Singleton界：令n =mint∈T maxflow(s,t)，则M(d )≤q n -d +1。
定理5 设G为单源网络，K为一步转移矩阵，d为正整数。
汉明界：令 ，m t=rank(Fs,t)，
Singleton界：令m t=rank(Fs,t)，则M(d,K)≤qm t-d +1。
注1 设{C,K}为一个网络码，?坌t∈T，其单播和组播极小距离分别
易知m t≤maxflow(s,t)且r≤r t。由定理
t∈T 都成立，故可立刻得到定理4的相应结论。因此文献[8]称定理5是定理4的改进版本。类似的结果对于Singleton界也成立。
对于收点t∈T, 令Δt(c,d )={c'∈
:D tcod(c',c)≤d }。
定理6 (Gilbert界)给定一个具有一步转移矩阵K的网络G，设码字集C关于每一个收点t的单播极小距离不小于正整数d t，|Cmax|为满足该性质的C的最大码字数目，则 其中Δ（0）=∪t∈TΔ(0,d t-1)。
注2 在定理6中，如果限制码字集C为线性码，并设|ωmax|为满足该性质的码字集的最大维数，则有以下的Varshamov界ωmax≥n s-logq |Δ（0）|。
4 结束语
通过构建统一的网络模型，本文对文献[6-9]中的主要结果做了介绍。
网络汉明重量的引入使得网络纠错码理论变得容易理解，这为具有传统纠错码基础的研究人员进入网络纠错码领域架设了桥梁。我们认为利用陪集码的理论框架[10]去描述和研究网络纠错码是一个值得深入研究的理论方向，现有的理论结果从陪集码的角度去描述可能会变得更为简洁和容易理解。
5 参考文献
[1] YEUNG R W, LI S Y R, CAI N, et al. Network coding theory[J]. Foundation and Trends in Communications and Information Theory, 2005, 2(4 -5):241–381.
[2] CAI N, YEUNG R W. Network coding and error correction[C]// Proceedings of IEEE Information Theory Workshop (ITW’02), Oct 20-25, 2002, Bangalore, India. 2002:119–122.
[3] YEUNG R W, CAI N. Network error correction, part I: Basic concepts and upper bounds[J]. Communications in Information and Systems, 2006, 6(1):19-36.
[4] CAI N, YEUNG R W. Network error correction, part II: Lower bounds[J]. Communications in Information and Systems, 2006, 6(1): 37–54.
[5] KOETTER R, MEDARD M. An algebraic approach to network coding[J]. IEEE/ACM Transactions on Networking, 2003, 11(5): 782-795.
[6] YANG S, YEUNG R W. Characterizations of network error corrections/detection and erasure correction [C]// Proceedings of Third Workshop on Network Coding, Theory, and Applications (NETCOD’07), Jan 2007, San Diego, CA, USA. 2007.
[7] ZHANG Z. Linear network error correction codes in packet networks[J]. IEEE Transactions on Information Theory, 2008, 54(1): 209-218.
[8] YANG S, YEUNG R W. Refined coding bounds for network error correction[C]// Proceedings of IEEE Information Theory Workshop (ITW’07), Sep 2-6, 2007, Lake Tahoe, CA, USA. 2007:1-5.
[9] YANG S, NGAI C K, YEUNG R W. Construction of linear network codes that achieve a refined singleton bound[C]//Proceedings of 2007 IEEE International Symposium on Information Theory (ISIT 2007), Jul 24-29, 2007, Nice, France. Los Alamitis, CA, USA: IEEE Computer Society, 2007: 1576-1580.
[10] FORNEY G D. Coset codes—II: Binary lattices and related codes[J]. IEEE Transactions on Information Theory, 1988, 34(5): 1152-1187.
收稿日期：2008-11-06
胡伟，清华大学深圳研究生院就读硕士研究生，主要研究方向为网络纠错码理论及其应用。
夏树涛，博士毕业于南开大学数学学院信息科学与概率统计系，现任清华大学深圳研究生院教授，主要从事信道编码特别是LDPC码和网络纠错码等方向的教学与科研工作，已在国内外重要期刊及会议论文集上发表学术论文30余篇。
关键词：网络纠错码；Coherent网络；网络汉明重量；最小距离；最大码字数
Abstract: Network coding is very sensitive to the transmission errors or malicious attacks in network. If the knowledge of network topology and network code is known at the source and destination codes, the network is called coherent. In coherent network, the concept of network Hamming weight narrows the gap between network error-correcting codes and classical error-correcting codes. Some theories and methods in classical error-correcting codes have chances to be applied to network error-correcting codes in the future. Similar to classical error-correcting codes, minimum distance characterizes the error-correcting capability of network error-correcting codes. Employing the theories of coset codes to describe and study network error-correcting codes is an interesting research topic.
Key words: network error correction codes; coherent network; network Hamming weight; minimum distance; maximum number of code words
网络编码[1]由于可以提升网络的传输效率而得到了人们的广泛研究，但网络编码对网络中的传输错误或恶意攻击十分敏感，一个关键性错误足以导致译码失败，这引发了对网络纠错码的研究。文献[2-4]提出了网络纠错码的基础概念。
1 Coherent网络模型
设G =(V,E)为一个有向无环网络，其中V表示节点集，E表示边集。由G的无环特性，我们可对E中所有的边进行排(偏)序并编号，例如：E={eｉ:i =1……|E|}，这些编号与稍后定义的矩阵的行或列一一对应。
如果存在从节点a∈V到节点b∈V的一条有向边e∈E，则称tail(e)=a，head(e )=b，并定义In(a)={e:head(e)=a, e∈E}为a所有入边的集合，Out(a)={e:tail(e)=a, e∈E}为a所有出边的集合。
设Fq 是一个包含q (其中q为素数幂)个元素的有限域，E中每条边的容量都为1，即在单位时间内每条边只能传输Fq 中的一个元，但一对节点之间可以存在多条边。本文只考虑单源情形，设s∈V为单源发点，T ?哿V \{s}为收点集合。设需要传送的信息为Fq上的ω维行向量x=(x 1,x 2……xω)，其分量位置分别对应单源节点s的ω条虚拟输入信道，用In(s)表示，注意ω=|In(s)|且In(s)∩E=φ。
设n s=|Out(s)|, 单位时间内发点s发送出去的信息可表示为n s维行向量，称之为码字，用c=(c 1,c 2……cn)表示，表示码字集。设发点s的局部编码核矩阵是ω×|E|的矩阵K(s)=[k d,e:d∈In(s),e∈E]，当e?埸Out(s)时k d,e=0。定义n s×|E|矩阵A=[Aij ]在ej为Out(s)的第i 条边时为1，否则为0。注意A的非0列构成一个n s×n s置换矩阵。信息字x与码字c存在如下的关系：xK(s)=cA，设网络G的局部编码核为{k e,e':e,e'∈E}，定义|E|×|E|一步转移矩阵K=[ｋij]在存在节点a使得ei∈In(a),
ej∈Out(a)时为k ei,ej，否则为0。
网络G中包含|E|条边，每条边都可能出现传输错误，我们用一个|E|维行向量 z=(z 1,z 2……z |E |)来表示网络中发生的错误，简称错误向量，其分量zi∈Fq表示边ei上发生的错误偏移，
zi =0表示该边没有发生错误。一个向量的支撑定义为该向量的非零分量位置的集合，错误向量z的支撑称为错误模式，记为ρz，显然，ρz?哿E。一般来说，E的任何一个子集ρ都可称作差错模式，表示网络中的错误只在ρ中的边上发生。
一个线性网络码由发点s的局部编码核矩阵K(s)和一步转移矩阵K给出，记为{ K(s), K}线性网络码，注意此时码字集ｃ构成一个q元[n s,ω]传统线性码。如果不使用K(s)而任意选取的一个子集作为码字集ｃ，此时称{ｃ,K}为一个网络码。由文献[5]知，对于网络G 和一步转移矩阵K，必存在正整数N使得K N=0成立。定义网络G上|E|×|E|的全局转移矩阵为：F=(I-K)-1= I+K……K N-1，其中I表示|E|×|E|单位矩阵。
如果网络拓扑和网络码对于网络的收点和发点都是已知的，这种类型的网络称为Coherent网络，本文假定网络G是一个Coherent网络。设t∈T为一个收点，设n t=|In(t)|为t的入边数目。定义|E|×n t矩阵Bt=[Bij]在ej为In(s)的第i 条边时为1，否则为0，注意Bt的非0行构成一个n t×n t置换矩阵。收点t接收到的信息可表示为Fq上的一个n t维行向量，通常记为y t。由文献[6-9]知，如果网络中没有错误发生，则y t=xK(s)FB；否则设z为错误向量，则y t=(cA+z)FBt=cFs,t+zFt，或表示为y t=(xK(s)+z)FBt=(x,z)F't。其中Fs,t＝AFBt, Ft＝FBt, 。易知Ft是F的子矩阵，Ft的列对应In(t)中的边；Fs,t是Ft的子矩阵，Fs,t的行对应Out(s)中的边。显而易见，这两种表示方法是等价的，在讨论译码时前者使用起来更为方便，在讨论网络纠错码与传统纠错码的联系时后者使用起来更胜一筹。
2 网络汉明重量和极小距离
类似于传统纠错码，极小距离也反映了网络纠错码的纠错/检错能力。文献[6]和文献[7]两文分别定义了网络纠错码的极小距离，虽然表示方法不同，但实际上是等价的。
2.1 网络汉明重量
文献[6]提出了网络汉明重量的概念，这拉近了网络纠错码和传统纠错码之间的距离，使得传统纠错码的很多理论和方法有望在将来可以更容易地应用于网络纠错码之中。
由上文可知，F满秩，故Ft列满秩。任给y∈，令γ(y)={z∈ :zFt=y}。因为Ft列满秩，所以γ(0)是一个(|E|-n t)维线性子空间，γ(y)是γ(0)的一个陪集。对收点t，接收向量y、错误向量z和码字向量c的网络汉明重量分别定义如下：
Wtrec(y)=min{WH(z):z∈γ(y)},
Wteer(z)=Wtrec(zFt),
Wtcod(z)=Wtrec(cFS,t).
其中WH(•)表示向量的汉明重量。对收点t，相应的网络汉明距离定义为：
D trec(y,y')=Wtrec(y-y'),
D tcod(c,c')=Wtcod(c-c').
从而定义网络码{C,K }的单播极小距离为d min,t=min{D tcod(c,c'):?坌c≠c'∈C },单播极小距离还可写成以下更为直接的形式：d min,t=min{WH(z):zFt=(c-c')Fs,t, ?坌c≠c'∈C }。
考虑以下退化情形，网络G 中只有一个发点s和一个收点t, 并且s与t之间恰有n条边相连。容易看出，此时K=0, F=Ft=FS,t=I，从而网络汉明重量退化为汉明重量，网络纠错码退化为一个码长为n 的传统纠错码。由此可知，网络纠错码是传统纠错码的推广。对于收点集T，网络码{C,K}的组播极小距离定义为dmin=min{dmin,t:t∈T }，错误向量或码字的网络汉明重量不超过其汉明重量，即Wteer(z)≤WH(z),Wtcod(c)≤WH(c)。
另外，网络汉明距离满足对称性和三角不等式。
类似于传统纠错码，极小距离反映了网络纠错码的纠错能力。考虑以下最小距离译码准则：给定接收向量yt，查找c∈C使得cFs,t与yt的网络汉明距离最小，即 ，由此容易证明定理1。
定理1 对于收点和单播极小距离，以下结论等价：{C,K}的单播极小距离满足dmin,t≥d；若错误向量z满足Wteer(z)≤(d -1)/2，则{C,K}能纠正该错误；若错误向量z满足WH(z) ≤(d -1)/2，则{C,K}能纠正该错误；若错误向量z满足0＜Wteer(z)≤d -1，则{C,K}能检测该错误；若错误向量z满足0＜WH(z)≤d -1，则{C,K}能检测该错误。对于组播情形，也可得出类似结论。
2.2 极小秩
在文献[7]中，错误模式的秩被用来定义单播极小距离，(ω+|E|)×n t矩阵F't的前ω行张成一个线性子空间Φ(t)，即：Φ(t)={(x,0)F't:x∈Fqω}。
F't的后|E|行对应E的每一条边，设ρ?哿E为一个错误模式，F't中对应ρ的行张成一个线性子空间，用Δ(t,ρ)表示，即：Δ(t,ρ)={(0,z)F't:z∈, ρz?哿ρ}。
设ρ、ρ'为两个错误模式，如果对于收点t成立Δ(t,ρ) Δ(t,ρ')，则称ρ'关于t决定ρ，记作ρ?刍tρ'。错误模式ρ关于收点t的秩(rank)定义为rankt(ρ)=min{|ρ'|: ρ?刍tρ'}。
线性网络码{K(s),K}的(单播)极小秩被定义为dmin(t)=min{rankt(ρ):dim(Δ(t,ρ)∩Φ(t))＞0}。
众所周知，在传统纠错码理论中，线性码的极小距离等于最小重量，从而极小距离等于一个码字成为另一个码字所需要变更的最小位置数目。我们可以从这个角度去理解极小秩dmin(t)，当存在一个错误模式ρ使得dim(Δ(t,ρ)∩Φ(t))＞0时，表示一个码字受到错误向量的影响成为了另一个码字。Zhang进一步证明了极小秩扮演了与传统纠错码极小距离类似的角色，即：一个极小秩等于dmin(t)的线性网络码可以检测dmin(t)-1个错误或纠正(dmin(t)-1)/2个错误。
令Ct=maxflow(s,t)表示从发点s到收点t的网络最大流，δt=Ct-ω称为收点的冗余，一个极小秩等于冗余加1的线性网络码称为最大距离可分(MDS)线性网络码。文献[7] 给出的定理2说明：当q足够大时，MDS线性网络码存在。
定理2 当q＞时，必然存在Fq上的线性网络码{K(s),K}，使得对于所有t∈T 都有dmin(t)=δt +1成立。
定理3证明了单播极小距离与单播极小秩的等价性。
定理3 dmin(t)=dmin,t。
从以上的介绍我们看到两种极小距离的定义殊途同归，只是表达方式存在差异。对于具有传统纠错码背景的读者，网络汉明重量的引入会使得网络纠错码理论变得更容易理解，极大地拉近了网络纠错码与传统纠错码之间的距离。尽管如此，我们认为网络纠错码的数学表示仍有改进之处，例如：γ(0)是一个(|E|-n t)维线性子空间，γ(y)是γ(0)的一个陪集，容易知道，位于同一个陪集的错误向量是等价的；同样的思想在码字集所在的空间 中也可以应用，故码字集C的构造问题本质上是陪集的选择问题，这启示我们采用陪集码的理论框架去研究网络纠错码。
3 最大码字数的上界和下界
给定一个具有单源发点s、收点集T和固定拓扑的网络G, 每一个收点的最大流值可由快速算法求出。如何选择局部编码核矩阵K和码字集C, 使得在保证一定纠错性能的条件下网络的传输效率最高，就是网络码{C,K}的一般构造问题，给定正整数d, 定义最大码字数为M(d )=max{|C|:dmin≥d }，达到最大码字数的网络码{C,K}称为最优网络码。
如果进一步固定局部编码核矩阵K和收点t∈T (此时F、Ft和Fs,t都已固定)，如何选择码字集C使得在保证一定纠错性能的条件下从s到t的传输效率最高，就是网络码{C,K}的单播构造问题。给定正整数d, 定义单播最大码字数为M t(d,K)=max{|C|:dmin,t≥d }，达到最大码字数的网络码{C,K}称为关于t的单播最优网络码。
定理4 设G为一个单源网络，d为正整数。
汉明界：令 ,n =mint∈T maxflow
Singleton界：令n =mint∈T maxflow(s,t)，则M(d )≤q n -d +1。
定理5 设G为单源网络，K为一步转移矩阵，d为正整数。
汉明界：令 ，m t=rank(Fs,t)，
Singleton界：令m t=rank(Fs,t)，则M(d,K)≤qm t-d +1。
注1 设{C,K}为一个网络码，?坌t∈T，其单播和组播极小距离分别
易知m t≤maxflow(s,t)且r≤r t。由定理
t∈T 都成立，故可立刻得到定理4的相应结论。因此文献[8]称定理5是定理4的改进版本。类似的结果对于Singleton界也成立。
对于收点t∈T, 令Δt(c,d )={c'∈
:D tcod(c',c)≤d }。
定理6 (Gilbert界)给定一个具有一步转移矩阵K的网络G，设码字集C关于每一个收点t的单播极小距离不小于正整数d t，|Cmax|为满足该性质的C的最大码字数目，则 其中Δ（0）=∪t∈TΔ(0,d t-1)。
注2 在定理6中，如果限制码字集C为线性码，并设|ωmax|为满足该性质的码字集的最大维数，则有以下的Varshamov界ωmax≥n s-logq |Δ（0）|。
4 结束语
通过构建统一的网络模型，本文对文献[6-9]中的主要结果做了介绍。
网络汉明重量的引入使得网络纠错码理论变得容易理解，这为具有传统纠错码基础的研究人员进入网络纠错码领域架设了桥梁。我们认为利用陪集码的理论框架[10]去描述和研究网络纠错码是一个值得深入研究的理论方向，现有的理论结果从陪集码的角度去描述可能会变得更为简洁和容易理解。
5 参考文献
[1] YEUNG R W, LI S Y R, CAI N, et al. Network coding theory[J]. Foundation and Trends in Communications and Information Theory, 2005, 2(4 -5):241–381.
[2] CAI N, YEUNG R W. Network coding and error correction[C]// Proceedings of IEEE Information Theory Workshop (ITW’02), Oct 20-25, 2002, Bangalore, India. 2002:119–122.
[3] YEUNG R W, CAI N. Network error correction, part I: Basic concepts and upper bounds[J]. Communications in Information and Systems, 2006, 6(1):19-36.
[4] CAI N, YEUNG R W. Network error correction, part II: Lower bounds[J]. Communications in Information and Systems, 2006, 6(1): 37–54.
[5] KOETTER R, MEDARD M. An algebraic approach to network coding[J]. IEEE/ACM Transactions on Networking, 2003, 11(5): 782-795.
[6] YANG S, YEUNG R W. Characterizations of network error corrections/detection and erasure correction [C]// Proceedings of Third Workshop on Network Coding, Theory, and Applications (NETCOD’07), Jan 2007, San Diego, CA, USA. 2007.
[7] ZHANG Z. Linear network error correction codes in packet networks[J]. IEEE Transactions on Information Theory, 2008, 54(1): 209-218.
[8] YANG S, YEUNG R W. Refined coding bounds for network error correction[C]// Proceedings of IEEE Information Theory Workshop (ITW’07), Sep 2-6, 2007, Lake Tahoe, CA, USA. 2007:1-5.
[9] YANG S, NGAI C K, YEUNG R W. Construction of linear network codes that achieve a refined singleton bound[C]//Proceedings of 2007 IEEE International Symposium on Information Theory (ISIT 2007), Jul 24-29, 2007, Nice, France. Los Alamitis, CA, USA: IEEE Computer Society, 2007: 1576-1580.
[10] FORNEY G D. Coset codes—II: Binary lattices and related codes[J]. IEEE Transactions on Information Theory, 1988, 34(5): 1152-1187.
收稿日期：2008-11-06
胡伟，清华大学深圳研究生院就读硕士研究生，主要研究方向为网络纠错码理论及其应用。
夏树涛，博士毕业于南开大学数学学院信息科学与概率统计系，现任清华大学深圳研究生院教授，主要从事信道编码特别是LDPC码和网络纠错码等方向的教学与科研工作，已在国内外重要期刊及会议论文集上发表学术论文30余篇。