Tutorial Sessions

Tutorial 03

Network-Error Correcting Codes

Speaker: Prof. B. Sundar Rajan, Dept. of ECE, IISc. Bangalore, India


Network-error correcting codes aim to correct errors in network communication that employ network coding by introducing redundancies in space domain or in space-time domain. This is a generalization of the classical error control coding that employ redundancies only in time and can also be called “coding for network coding”. The tutorial will initially deal with all the important aspects of network coding, starting from basic notions, major classifications (coding for cyclic and acyclic networks) and description of important classes of linear network codes (linear multicast, linear broadcast, linear dispersion and generic linear network codes) and some of the important algorithms to construct them. These network codes are designed to increase the throughput, reduce the energy consumption or latency and assume that the communication between nodes are error- free. When the communication links between nodes are error-prone network-error correcting codes need to be employed, along with network coding, to achieve reliable communication. Basic concepts of network-error correcting codes will be described along with basic bounds and metrics associated with such codes. Benefits of linear network-error correcting codes over routing in packet networks will be illustrated. Also, the benefits of network-error correction in randomized setting will be described using rank-distance codes. Several adversarial models and resilient schemes for network coding will be discussed. The tutorial will end with pointing out several recent trends and open problems in this area.