2000年,Ahlswede等人从信息论角度创造性地提出“网络编码”这一新概念,首次将网络和路由有机融合为一体,建立了一种全新的网络体系结构.不同于传统信息传输方法,通过网络编码可以将传输过程中的信息流再次进行压缩,从而解决了多播网络传输中Shannon信息论上界不可达的问题.网络编码彻底改变了现有通信中信息处理和传输模式,是信息论研究领域的重大突破,已经引起了学术界和工程界的高度重视。目前,网络编码理论研究有如下几个重要问题：一是网络编码的编码复杂性问题.由于编码相对于路由转发操作更为复杂,因此需要尽可能的减少编码操作.特别是研究一个多播网络中需要编码操作的节点个数与网络结构之间的关系问题；二是网络编码的构造问题.如何用较低的复杂度构造网络编码是将其应用于现实网络通信中的重要一步.对于无环网络,已经存在多项式时间的网络编码算法,现存的算法复杂度是否可以进一步降低也是大家关注的重要问题.对于带环网络,主要集中在卷积网络算法的研究上.虽然已经有多项式时间的构造算法,但是复杂性还是较高,不利于程序化实现.如何进一步结合无环网络上的某些思想来构造带环网络上的网络编码是下一步研究的突破口；三是安全网络编码的构造问题.自从蔡宁和杨伟豪首次提出将网络编码用于安全通信的几年时间里,安全网络编码得到了蓬勃发展.特别是抗主动攻击(或称拜占庭攻击)的安全网络编码,不但引起了信息学专家的关注,也引起了密码学专家的关注.信息学专家从信息论的角度设计能够在信宿节点检测篡改的安全网络编码,但是这种办法对具体网络的限制较多,不利于实际应用.密码学专家用数字签名的方法给编码的消息进行签名,中间节点通过验证收到的消息是否为真来决定下一步的消息处理.虽然这些方法能够阻止错误消息的传播,但是它们的计算复杂度较高.因此,如何结合这两种方法设计新的安全网络编码是下一步研究的重点.本文针对上述问题进行了深入研究,获得了几个关键性的研究成果,主要概括为：1.通过为路着色和对网络的组合分解给出了无环多播网络上最少编码节点的最优解.在无环网络结果的基础上,作者进一步分析了带环网络上的最少编码节点个数,得到了较Langberg等人更优的结果.对于多播上网络编码的编码复杂性,Langberg等人虽然已经有了一些重要成果,但并没有完全解决编码节点个数问题,特别是带环网络上的编码节点个数问题.2.在得到无环多播网络上最少编码节点个数最优解的基础上,进一步分析了Langberg算法的计算复杂度,并得到了最好的结果.同时也对构造整型网络编码和分型网络编码的时间复杂度进行了重新分析.3.结合无环网络中的Jaggi-Sanders算法和控制论中的梅森公式设计了一种新的卷积网络编码算法.4.结合信息学和密码学理论,设计了一类可扩展的网络编码算法.一是防窃听的安全网络编码算法；二是拜占庭攻击检测的安全网络编码算法；三是前两种算法的结合算法,它即可以做到防窃听又可以做到拜占庭攻击检测.