On index coding with side information

• Main Author: Dau, Son Hoang
• Other Authors: Chee Yeow Meng
• Format: Theses and Dissertations
• Language: English
• Published: 2012
• Subjects: DRNTU::Science::Mathematics
• Online Access: https://hdl.handle.net/10356/48642
• Institution: Nanyang Technological University

Index Coding with Side Information (ICSI) (Birk and Kol (1998)) is a communication scheme dealing with broadcast channels in which receivers have prior side information about the messages to be broadcast. Exploiting the knowledge about the side information, the sender may significantly reduce the number of required transmissions compared with the naive approach. As a consequence, the efficiency of the communication over this type of broadcast channels could be dramatically improved. While most of the known works on ICSI focus on the performances of index codes of various kinds, the security and error correction aspects of those codes have never been examined. One of our goals is to fill in this gap. We are able to show that each linear index code provides a certain level of security, and moreover, the well-known coset coding technique provides us a way to secure any linear index code. Our second goal is to study the computational aspects of the ICSI problem. We discover several new families of ICSI instances for which optimal linear index codes can be found in polynomial time. We also compute the optimal linear index codes for all ICSI instances described by graphs of orders at most 10, using a computer program.