Reduced Complexity Index Codes and Improved Upperbound on Broadcast Rate\n for Neighboring Interference Problems

2019/01/21 by Mahesh Babu Vaddi, Vaddi, Mahesh Babu, B. Sundar Rajan +1
Computer Science · Engineering · #Coding theory and cryptography #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Information Theory (cs.IT) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1901.07123

openalex publication_date 2019/01/21 · openalex created_date 2022/07/30 · openalex updated_date 2026/07/28

Abstract

A single unicast index coding problem (SUICP) with symmetric neighboring\ninterference (SNI) has K messages and K receivers, the kth receiver\nR_k wanting the kth message x_k and having the interference with D\nmessages after and U messages before its desired message. Maleki, Cadambe and\nJafar studied SUICP(SNI) because of its importance in topological interference\nmanagement problems. Maleki \et. al. derived the lowerbound on the\nbroadcast rate of this setting to be D+1. In our earlier work, for SUICP(SNI)\nwith arbitrary K,D and U, we defined set \S of 2-tuples and for\nevery (a,b) \∈ \S, we constructed b-dimensional vector linear\nindex code with rate D+1+\(a)/(b) by using an encoding matrix of dimension\nKb \× (b(D+1)+a). In this paper, we use the symmetric structure of the\nSUICP(SNI) to reduce the size of encoding matrix by partitioning the message\nsymbols. The rate achieved in this paper is same as that of the existing\nconstructions of vector linear index codes. More specifically, we construct\nb-dimensional vector linear index codes for SUICP(SNI) by partitioning the\nKb messages into b(U+1)+c sets for some non-negative integer c. We use an\nencoding matrix of size \(Kb)/(b(U+1)+c) \× \(b(D+1)+a)/(b(U+1)+c)\nto encode each partition separately. The advantage of this method is that the\nreceivers need to store atmost \(b(D+1)+a)/(b(U+1)+c) number of broadcast\nsymbols (index code symbols) to decode a given wanted message symbol. We also\ngive a construction of scalar linear index codes for SUICP(SNI) with arbitrary\nK,D and U. We give an improved upperbound on the braodcast rate of\nSUICP(SNI).\n

Related

• A New Upperbound on the Broadcast Rate of Index Coding Problems with Symmetric Neighboring Interference
• Near-Optimal Vector Linear Index Codes For Single Unicast Index Coding Problems with Symmetric Neighboring Interference
• On the Broadcast Rate of Index Coding Problems with Symmetric and Consecutive Interference
• Reduced Dimensional Optimal Vector Linear Index Codes for Index Coding Problems with Symmetric Neighboring and Consecutive Side-information
• Optimal Scalar Linear Index Codes for Symmetric and Neighboring Side-information Problems