Optimal Solution for the Index Coding Problem Using Network Coding over GF(2)

Prof. Chuan Heng FOH
Nanyang Technological University, Singapore
Tuesday, 19 June, 2012
11:00 am - 12:00 pm
Room 833, Ho Sin Hang Engineering Building The Chinese University of Hong Kong

The index coding problem is a fundamental transmission problem which occurs in a wide range of multicast networks. Network coding over a large finite field size has been shown to be a theoretically efficient solution to the index coding problem. However the high computational complexity of packet encoding and decoding over a large finite field size, and its subsequent penalty on encoding and decoding throughput as well as the higher energy cost makes it unsuitable for practical implementation in processor and energy constraint devices like mobile phones and wireless sensors. 

In this talk, we present our recent solutions for the index coding problem using network coding over GF(2). We first show some existing investigations on advantages of using XOR operation over finite-field operation on mobile devices. We then present our first solution called BENEFIT. BENEFIT uses XOR operation and achieves a near optimal solution in terms of performance. We finally introduce a breakthrough design in network coding for index coding problem which we call Triangular Network Coding. This new design combines both finite-field and real-field operations in the encoding process in such a way that the decoding process only requires XOR operation. This property makes our proposed coding scheme suitable for mobile devices. Besides, Triangular Network Coding offers endless supply of linearly independent coded packets which is often a limitation in Linear Network Coding over a finite-field. We close the talk by sharing some potential research opportunities in index coding and extensions of Triangular Network Coding.


Chuan Heng FOH (Ph.D, The University of Melbourne, 2002) is an Assistant Professor at the School of Computer Engineering, Nanyang Technological University (NTU) since December 2002. He is the author of 90 research papers and 1 patent. He is the Associate Editor of International Journal of Communication Systems and guest editor of International Journal of Distributed Sensor Networks, TPC member of many mainstream IEEE conferences. His main research interests include performances of computer networks, network coding, multimedia transmission, cloud computing, and data center technology.