与经典信道相关的网络编码

3.1网络编码顺序问题

在网络编码中，节点之间(或边上)的编码顺序是非常重要的。在编码过程中，需要保证在进行编码之前收到了所有输入边的信息，否则就会失败。对于有向无环图，根据图论中拓扑排序的方法就能确定节点之间(或边上)的编码顺序，保证序号小的节点总是比序号大的节点先完成输出边上的编码。但是对于有向有环图，问题就有些复杂。这时必须考虑边上的延迟，以区分不同时刻的消息。文献[5]中指出，如果有向图中有环，则只要在环路的任意边上，加上一个单位时间的延迟就可以解决不同时刻消息的区分问题。文献[5]提出了网络流图的概念，通过将有向有环图按照传输时刻分层的方法，准确刻画了网络信息流的传输过程。

3.2关于可达的描述

网络流图解决了有向图G中的网络编码次序问题后，文献[5]为每条边确定了网络编码函数，对信宿确定了网络译码函数，并且定义了译码差错概率Pe(n )为：

其中Wt表示信宿t译码后的消息，W表示信源发送的消息，T 表示网络中所有信宿的集合，n是码字长度。在网络流图中考虑的网络编码方案都是不变延迟时间的。

在此基础上，文献[5]进一步定义了可达的概念：设(G,C )是一个由单信源s和信宿集合T构成的网络，其中G为有向图，C为以G中每条边上经典信道容量为分量的向量。设ω为信源s的熵率，则是可达的定义为：存在一种不变延迟时间的n长分组网络—信道联合编码方案，使得各边达到经典信道容量，同时信源s可以向信宿集合T 以熵率ω传输消息，并且当n充分大时Pe(n )→0。

3.3网络编码与信道编码的分离定理

在上述模型中，文献[5]中对单信源单信宿的情况指出：(G,C,ω)是可达的当且仅当信源熵率ω不超过信源和信宿之间的最大流值。这个最大流值就是信源到信宿之间最小割中所有边的信道容量之和。具体来说，对G ?劬(V,E )的任意一个割(V1,V2)?劬{(i,j )∈E :i∈V1且j∈V2}，均有

作者：骆源 庄卓俊   来源：通信世界网