Optimal Linear Error-Correcting Index Codes for Single-Prior Index-Coding with Side Information
Simon Samuel, Balaji Sundar Rajan · 2017
In an index coding with side-information (ICSI) problem there is a sender with a set of n independent messages ℳ = {x1, x2, ..., xn} and there are m receivers ℛ = {R1, R2,..., Rm}, each identified with (Wi, Ki), where Wi⊆ ℳ is the set of messages wanted by receiver Riand Ki⊂ ℳ is the set of messages known a priori to receiver Ri. We call a ICSI problem to be single-prior if |Ki| = 1, ∀i. In addition, if Ki∩ Ki= φ, it is called a single-uniprior problem and has been studied in detail by Ong, Ho and Lim [1]. Error Correcting index codes (ECIC) have been studied by Dau, Skachek and Chee [2] and lower and upper bounds on the optimal length of ECICs have been reported. In this paper we show that for single-prior ICSI problems the lower and upper bounds on the optimal ECICs coincide. This leads to construction of optimal length linear ECICs.