网络编码

NetworkInformationFlow最大流最小截定理主要结论典型举例总结讨论相关定义1网络编码定义2网络编码的出现意义3图论中的相关定义4讨论范围NetworkInformationFlow主要结论典型举例总结讨论相关定义最大流最小截定理•什么是网络编码相比于传统网络通信系统中中间节点只做转发或复制储存功能，网络编码就是在通信网络中各个节点对各个信道接受到的信息进行编码处理。即中间节点扮演着编码器或信号处理器的角色。NetworkInformationFlow主要结论典型举例总结讨论相关定义最大流最小截定理网络编码的产生背景和意义传统的组播路由技术通常采用最大流算法找到一个信宿与信源之间的实现途径。然后依次寻找信源与其他信宿之间的路径。因为传统的组播传播认为节点只能进行存储转发操作，而认为网络中传输的信息是不能叠加的。这就导致信源于第二个和其后的所有信宿之间不能以最大流传输。这就导致整个组播的传输容量远小于最大流最小截定理上限。而网络编码就能够解决这个问题。NetworkInformationFlow主要结论典型举例总结讨论相关定义最大流最小截定理图论中的相关定义G={V,E}表示有向图V为节点集合，i，jVE为边集合，（i，j）E通信量在有向图中的表示有向图G表示一个通信网络所有发送节点和接受节点都映射到V的相关集合中m个发射节点表示：a（1,…,m）→V相对应的接收节点表示：b（1,…,m）→2v（a（i），b（i））E，表示传输路径我们同时定义x1,…xm为m个独立信息源，h=（h1,…,hm）分别表示信息源的信息传输率。NetworkInformationFlow主要结论典型举例总结讨论相关定义最大流最小截定理讨论范围问题的讨论范围讨论中的信息源相互独立，本此讨论主要是单一信息源。多源情况下的特殊情况可以用单一信息源情况进行推广编码形式认为是多级多样式编码和分布式编码。且在编码传输过程中不考虑失真本次讨论中的图表网络需求配置是任意的。NetworkInformationFlow主要结论典型举例总结讨论相关定义最大流最小截定理图论中的最大流最小截定理由相关定义中图论的相关定义，简介最大流最小截定理由图论中定理的引申说明举例进行说明从举例中进行推论信息论总的最大流最小截定理NetworkInformationFlow主要结论典型举例总结讨论相关定义最大流最小截定理图论中的最大流最小截定理st12345446253114322图中是一个典型的有向图，s表示源点，t表示汇点。图中方框外的数字表示路径容量，方框内的数字表示路径流量。NetworkInformationFlow主要结论典型举例总结讨论相关定义最大流最小截定理st12345446253114322图论中的最大流最小截定理截的定义：（cut）是网络中顶点的一个划分，它把网络中所有顶点划分为俩个集合S和T，其中s属于S，t属于T。截的流量定义：正向割边流量—逆向割边流量截的容量定义：正向割边容量和上述截的流量为2+4-1=5上述截的容量为4+4=8在任何网络中，如果f是一个流，（cut）是一个截，且f的值等于（cut）的容量，则称f是一个最大流NetworkInformationFlow主要结论典型举例总结讨论义相关定义最大流最小截定理网络编码中的最大流最小截定理通过上述的图论理论引申到网络编码中来，我们将上述传输量问题转化成编码速率（codingrate）问题。上述中的容量我们将之转换成编码速率（codingrate）容量，用Rij来表示，i,j为俩传输节点。而上述中的流量我们将之转化成编码速率（codingrate）流量，用fij来表示。上述的Rij,fij沿用了图论中边的容量和流量定义。而通过从图论中的引申，我们得出：0≤fij≤Rij。同时我们考虑传输无损耗则∑fi’i=∑fij。根据以上定义我们重新定义网络编码中整体网络的R=∑[Rij,，(i,j)E]。单一汇情况下的F=∑fsj-∑fis或F=∑fjt-∑ftj而整体的F=min{F1,…,Fn}。而整体的最大流F可以通过最大流最小截定理（通过R）来获得。NetworkInformationFlow主要结论典型举例总结讨论相关定义最大流最小截定理举例说明图(a)表示容量图，图（b）表示流量图，由最大流最小截理论得出该流量图为最大流。NetworkInformationFlow主要结论典型举例总结讨论相关定义最大流最小截定理举例说明图（a）表示的是容量图图（b）为最大流实际图NetworkInformationFlow主要结论典型举例总结讨论相关定义最大流最小截定理举例引申出的推论推论1我们从上面的例子中的网络结构得出网络的最大流。则对应一个确定网络结构（R,h,G）的最大流应该大于或等于信息源传输率h。推论2为了达到传输最大流，当汇点L=1时，是不需要编码的。L≥2时，一般情况下需要进行网络编码。俩点说明：1网络编码中在编码和解码输入端处，没有编码，认为R=∞,所以不影响网络结构。2虽然R和f都为边的codingrate，但都由输入节点的codingrate控制，因此符合网络编码理论相关定义主要结论典型举例总结讨论NetworkInformationFlow最大流最小截定理网络编码基本原理网络编码优点网络编码基本思想网络编码的得出定理结构架构相关定义主要结论典型举例总结讨论NetworkInformationFlow最大流最小截定理网络编码基本原理传统路由方式：X和Y的传送分开处理。传播X时，走红色路径；传播Y时，走蓝色路径。这样，在节点3和节点4那会产生冲突，这是用传统的路由方式无法解决的。将X和Y编码成X+Y，这个冲突就能解决了。显然，汇结点都可以解码X和Y。相关定义主要结论典型举例总结讨论NetworkInformationFlow最大流最小截定理网络编码的优点增加网络整体的吞吐量节约带宽主要优点相关定义主要结论典型举例总结讨论NetworkInformationFlow最大流最小截定理提高网络吞吐量由基本原理可知，相比于传统组播路由技术，网络编码使用后，在同一时刻t1和t2都能够接受2bit数据。因此提高了网络吞吐量。相关定义主要结论典型举例总结讨论NetworkInformationFlow最大流最小截定理提高网络吞吐量使用这个模型，如果每个边传输2比特，则4比特信息可以传输到每个汇结点用这个模型，不采用网络编码，如果每个边传输2比特信息，则每个汇结点只能收到3比特信息相关定义主要结论典型举例总结讨论NetworkInformationFlow最大流最小截定理节约带宽两幅图中各个汇点都能接受到两bit信息，但第一幅图只传输了9bit，而第二副图中传输了10bit。因此两者相比较采用网络编码的方法可以节省10%的带宽。相关定义主要结论典型举例总结讨论NetworkInformationFlow最大流最小截定理网络编码的基本思想介绍一种分组的编码的基本思想设n为码长度，为信息的集合，且均匀分布，x是有关系的值。相关定义主要结论典型举例总结讨论NetworkInformationFlow最大流最小截定理网络编码的基本思想对于上述的一般性编码，其思想就是通过在中间节点处通过局部编码核进行编码映射，在接收点处通过全局编码核进行解码。上述的编码并不是分组码的最一般定义，我们还可以通过信息X的值进行排序分组，还可以进行概率编码（但不提高编码性能）。包括分组码也可以由可变长度码进行替代相关定义主要结论典型举例总结讨论NetworkInformationFlow最大流最小截定理网络编码的重要定理依据上述α编码我们得到：对于一个图表G=(V,E)，并且这个图表中每条边的信息容量是，是满足最大流最小截定理中所有R的集合，是按照α编码的所有R的集合，定理表示ijRNetworkInformationFlow相关定义主要结论典型举例总结讨论最大流最小结定理典型举例介绍一种网络编码的应用网络结构图NetworkInformationFlow相关定义主要结论典型举例总结讨论最大流最小结定理编码方式在这种编码方式中，k表示时间，Xl（k）表示k时刻发送的信息，当k=0时Xl（k）=0.NetworkInformationFlow相关定义主要结论典型举例总结讨论最大流最小结定理典型举例sv0v1v2t0t1u0t2U1u2x0（k）X2（k）X1(k)X1(k)X1(k)X0(k)X2(k)X0(k)X1(k)x1(k)+x2(k)+x0（k）X0(k)X0(k)X2(k)x0(k)+x1(k)X2(k)X0(k)X0(k)+X1(k)x1(k)+x2(k)+x0（k）K=1NetworkInformationFlow相关定义主要结论典型举例总结讨论最大流最小结定理典型举例sv0v1v2t0t1u0t2U1u2x0（k）X2（k）X1(k)X1(k)X1(k)x0(k)+x1(k-1)+x2(k-1)X2(k)X0(k)X1(k)x1(k)+x2(k)+x0(k）X0(k)X0(k)X2(k)x0(k)+x1(k)+x2(k-1)X2(k)x0(k)+x1(k-1)+x2(k-2)x0(k)+x1(k)+x2(k-1)x1(k)+x2(k)+x0（k）K1x0(k-1),x0(k-1)+x1(k-1)+x2(k-1)x0(k-1),x1(k-1)x2(k-1),x0(k-1)+x1(k-1)+x2(k-1)NetworkInformationFlow相关定义主要结论典型举例总结讨论最大流最小结定理典型举例而上述的编码过程也可以通过下面的树形图表示出来。s1v0v2v)(0x)(1x)(2x0t)(0x1u)(0x2t)(0x)(1x)(1x2t)(1x1t0u0t)(2x2u)(2x1t)(2x1u)(0x2t)(0x2u)(10xx0t)(10xx0u)(210xxx1t)(210xxx0v)(0x1v)(1x2v)(2x1t)(0x0u)(0x2t)(0x0t)(1x1u)(1x2t)(1x0t)(2x2u)(2x1t)(2x1u)(22110xxx2t)(22110xxx2u)(2210xxx0t)(2210xxx0u)(210xxx1t)(210xxxsK=1K＞1NetworkInformationFlow相关定义主要结论典型举例总结讨论最大流最小结定理典型举例通过上面的例子，我们得出1例子再次证明了网络编码满足最大流传输。即在此网络中三个汇点都能接受3bit数据。2例子中的编码可以看作是卷积码编码，即证明了在非循环网络中卷积码进行网络编码的可行性。NetworkInformationFlow相关定义主要结论典型举例总结讨论最大流最小结定理未来问题发展方向总结单源问题向多源问题的延伸总结讨论总结讨论部分分为三部分，将对论文中讨论的问题进行延伸，总结和进一步展望。NetworkInformationFlow相关定义主要结论典型举例总结讨论最大流最小结定理多源问题的延伸多源的复杂性首先考虑信源相互独立，还要考虑信源的编码相互分开，即要考虑编码的重叠，因此情况相对复杂多源中的特例多源中有一种情况是可以转换为单源问题进行解决的。NetworkInformationFlow相关定义主要结论典型举例总结讨论最大流最小结定理多源问题的特殊情况分析当在一个网络中存在m个信息源xi相互独立，且对应在节点si中生成，对应共有L个汇点t1.。。。tL。这m个信源传输率为hi条件加入一个s节点，和m个边（s，si）。令这些边的容量R=hi，这样就把m个信息源转化为一个信息源。转换方法NetworkInformationFlow相关定义主要结论典型举例总结讨论最大流最小结定理总结从网络编码思想中我们可以看出，对于整个传输系统，在汇点大于1时，信息已经不在想象成信息流或实体，而是通过“痕迹”我们需要把信息想象成通过网络编码在源节点和汇结点间散布的点（而不是一个信息流）整体