A Discrete Polymatroidal Framework for Differential Error-Correcting Index Codes
- 11 April 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 67 (7) , 4593-4604
Abstract
In the conventional index coding problem, the messages transmitted by the source to satisfy the demands of the receivers are error-free. However, in practice, the messages may be error prone which led to the introduction of error-correcting index codes. An error-correcting index code is an encoding scheme which enables every receiver to decode its demanded message even in the presence of certain number of transmission errors. Formally, an index code capable of correcting at most δ errors at all its receivers is defined as a δ-error-correcting index code. In this paper, we explore the connections between vector linear error-correcting index codes and discrete polymatroids. This is motivated from the connections between linear network error-correcting codes and matroids. It is shown that a vector linear error-correcting index code exists if and only if there exists a representable discrete polymatroid satisfying certain conditions. Differential error-correcting index codes which allow different receivers to have different error-correcting capabilities are also studied. Note that the δ-error-correcting code is a special case of a differential error-correcting index code. Error correction at a subset of receivers is another special case which is discussed.Keywords
Funding Information
- Science and Engineering Research Board (SERB) of Department of Science and Technology (DST), Government of India, through J.C. Bose National Fellowship to B. Sundar Rajan
This publication has 31 references indexed in Scilit:
- Storage Capacity of Repairable NetworksIEEE Transactions on Information Theory, 2015
- An Equivalence Between Network Coding and Index CodingIEEE Transactions on Information Theory, 2015
- A Matroidal Framework for Network-Error Correcting CodesIEEE Transactions on Information Theory, 2014
- Data Dissemination With Side Information and FeedbackIEEE Transactions on Wireless Communications, 2014
- Fundamental Limits of CachingIEEE Transactions on Information Theory, 2014
- Ideal Multipartite Secret Sharing SchemesJournal of Cryptology, 2011
- Network Error Correction, II: Lower BoundsCommunications in Information and Systems, 2006
- Network Error Correction, I: Basic Concepts and Upper BoundsCommunications in Information and Systems, 2006
- Insufficiency of Linear Coding in Network Information FlowIEEE Transactions on Information Theory, 2005
- Matroid representations by partitionsDiscrete Mathematics, 1999