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

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.