Error Correction for Index Coding With Coded Side Information

Files in This Item:
 File SizeFormat
DownloadICCSI_final_3_col.pdf461.9 kBAdobe PDF
Title: Error Correction for Index Coding With Coded Side Information
Authors: Byrne, EimearCalderini, Marco
Permanent link:
Date: 6-Jun-2017
Online since: 2017-10-17T17:13:04Z
Abstract: Index coding is a source coding problem in which a broadcaster seeks to meet the different demands of several users, each of whom is assumed to have some prior information on the data held by the sender. A well-known application is satellite communications, as described in one of the earliest papers on the subject (Birk and Kol, 1998). It is readily seen that if the sender has knowledge of its clients’ requests and their side-information sets, then the number of packet transmissions required to satisfy all users’ demands can be greatly reduced if the data are encoded before sending. The collection of side-information indices as well as the indices of the requested data is described as an instance I of the index coding with side-information (ICSI) problem. The encoding function is called the index code of I , and the number of transmissions, resulting from the encoding is referred to as its length. The main ICSI problem is to determine the optimal length of an index code and instance I . As this number is hard to compute, bounds approximating it are sought, as are algorithms to compute efficient index codes. These questions have been addressed by several authors (e.g., see Alon et al. 2008, Bar-Yossef et al. 2011, Blasiak et al. 2013), often taking a graph-theoretic approach. Two interesting generalizations of the problem that have appeared in the literature are the subject of this paper. The first of these is the case of index coding with coded side information (Dai et al. 2014), in which linear combinations of the source data are both requested by and held as users’ side-information. This generalization has applications, for example, to relay channels and necessitates algebraic rather than combinatorial methods. The second is the introduction of error-correction in the problem, in which the broadcast channel is subject to noise (Dau et al. 2013). In this paper, we characterize the optimal length of a scalar or vector linear index code with coded side information (ICCSI) over a finite field in terms of a generalized min-rank and give bounds on this number based on constructions of random codes for an arbitrary instance. We furthermore consider the length of an optimal δ -error correcting code for an instance of the ICCSI problem and obtain bounds analogous to those described in (Dau et al. 2013), both for the Hamming metric and for rank-metric errors. We describe decoding algorithms for both categories of errors.
Type of material: Journal Article
Publisher: IEEE
Journal: IEEE Transactions on Information Theory
Volume: 63
Issue: 6
Copyright (published version): 2017 IEEE
Keywords: Index codingMin-rankError correctionMinimum distanceNetwork codingCoded side-information
DOI: 10.1109/TIT.2017.2687933
Language: en
Status of Item: Peer reviewed
This item is made available under a Creative Commons License:
Appears in Collections:Mathematics and Statistics Research Collection

Show full item record

Citations 20

Last Week
Last month
checked on Sep 11, 2020

Page view(s)

Last Week
Last month
checked on Jul 1, 2022


checked on Jul 1, 2022

Google ScholarTM



If you are a publisher or author and have copyright concerns for any item, please email and the item will be withdrawn immediately. The author or person responsible for depositing the article will be contacted within one business day.