On the Broadcast Rate of Index Coding Problems with Symmetric and Consecutive Interference
Mahesh Babu Vaddi B. Sundar Rajan
cs.IT math.IT



 
Dust in brown dwarfs and extra-solar planets
    Mahesh Babu Vaddi and B. Sundar Rajan
 
 Department of Electrical Communication Engineering, Indian Institute of Science, Bengaluru 560012, KA, India 
 E-mail: {vaddi, bsrajan}@iisc.ac.in 
    Received: 21 Sep 2017 / Accepted: 25 Jan 2018
================================================================================================================================================================================================



A single unicast index coding problem (SUICP) with symmetric and consecutive interference (SCI) has K messages and K receivers, the kth receiver R_k wanting the kth message x_k and having interference ℐ_k= {x_k-U-m,…,x_k-m-2,x_k-m-1}∪{x_k+m+1, x_k+m+2,…,x_k+m+D} and side-information 𝒦_k=(ℐ_k ∪ x_k)^c. In this paper, we derive a lowerbound on the broadcast rate of single unicast index coding problem with symmetric and consecutive interference (SUICP(SCI)). In the SUICP(SCI), if m=0, we refer this as single unicast index coding problem with symmetric and neighboring interference (SUICP(SNI)). 

In our previous work<cit.>, we gave the construction of near-optimal vector linear index codes for SUICP(SNI) with arbitrary K,D,U. In this paper, we convert the SUICP(SCI) into SUICP(SNI) and give the construction of near-optimal vector linear index codes for SUICP(SCI) with arbitrary K,U,D and m. The constructed codes are independent of field size. The near-optimal vector linear index codes of SUICP(SNI) is a special case of near-optimal vector linear index codes constructed in this paper for SUICP(SCI) with m=0. In our previous work<cit.>, we derived an upperbound on broadcast rate of SUICP(SNI). In this paper, we give an upperbound on the broadcast rate of SUICP(SCI) by using our earlier result on the upperbound on the broadcast rate of SUICP(SNI). We derive the capacity of SUICP(SCI) for some special cases.




§ INTRODUCTION AND BACKGROUND


An index coding problem (ICP), comprises a transmitter that has a set of K messages, X={ x_0,x_1,…,x_K-1}, and a set of M receivers, R={ R_0,R_1,…,R_M-1}. Each receiver, R_k=(𝒦_k,𝒲_k), knows a subset of messages, 𝒦_k ⊂ X, called its side-information, and wants to know another subset of messages, 𝒲_k ⊆𝒦_k^𝖼, called its Want-set. The transmitter can take cognizance of the side-information of the receivers and broadcast coded messages, called the index code, over a noiseless channel. Birk and Kol introduced the problem of index coding with side-information in <cit.>. An index coding problem is single unicast if the demand-sets of the receivers are disjoint and the cardinality of demand-set of every receiver is one <cit.>. The single unicast index coding problems were studied in <cit.>.





A solution to the ICP may be linear or nonlinear. A solution of the ICP must specify a finite alphabet 𝒜_P, and an encoding scheme ε:𝒜^t →𝒜_P such that every receiver is able to decode the wanted message from ε(x_0,x_1,…,x_K-1) and the known information. The minimum encoding length l=⌈ log_2|𝒜_P|⌉ for messages that are t bit long (|𝒜|=2^t) is denoted by β_t. The broadcast rate of the ICP is defined <cit.> as,

β≜inf_tβ_t/t.

For an ICP, β is the minimum number of index code symbols required to transmit to satisfy the demands of all the receivers. The capacity C of an ICP is the reciprocal of the broadcast rate β. 







A single unicast index coding problem with symmetric and consecutive interference (SUICP(SCI)) with equal number of K messages and receivers, is one with each receiver having a total of U+D<K-2m interference, corresponding to the D (U ≤ D) messages after and U messages before its desired message. In this setting, the kth receiver R_k demands the message x_k having the interference


    I_k=    {x_k-U-m,…,x_k-m-2,x_k-m-1}∪
            {x_k+m+1, x_k+m+2,…,x_k+m+D},

the side-information being 

    𝒦_k=(ℐ_k ∪ x_k)^c ={x_k+m+D+1,x_k+m+D+2… x_k-m-U-1}
       ∪{x_k-m,x_k-m+1… x_k-1}∪{x_k+1,x_k+2… x_k+m}.


The SUICP(SCI) is pictorially represented in Fig. <ref>. All the subscripts in this paper are to be considered modulo  K.


A single unicast index coding problem with symmetric neighboring interference (SUICP(SNI)) with equal number of K messages and receivers, the kth receiver R_k demands the message x_k having the interference


    I_k= {x_k-U,…,x_k-2,x_k-1}∪{x_k+1, x_k+2,…,x_k+D},

the side-information being 

    𝒦_k=(ℐ_k ∪ x_k)^c={x_k+D+1,x_k+D+2,…,x_k-U-1}.



Note that the SUICP(SNI) is a special case of SUICP(SCI) with m=0. 






























The existing capacity results for SUICP(SNI) were summarized in <cit.>. There exists no capacity and optimal index coding results for SUICP(SCI) with m ≠ 0. The symmetric index coding problems are motivated by topological interference management problems in wireless communication networks <cit.>.


 §.§ AIR matrices

In <cit.>, we constructed binary matrices of size m × n (m≥ n) such that any n adjacent rows of the matrix are linearly independent over every field. We refer these matrices as adjacent row independent (AIR) matrices. The matrix obtained by Algorithm <ref> is called the (m,n) AIR matrix and it is denoted by 𝐋_m× n. The general form of the (m,n) AIR matrix is shown in Fig. <ref>. 



The description of the submatrices are as follows: Let c and d be two positive integers and d divides c. The following matrix  denoted by 𝐈_c × d is a rectangular  matrix.

    𝐈_c × d=.[[ 𝐈_d; 𝐈_d;   ⋮; 𝐈_d ]]}c/d number of 𝐈_d matrices

and 𝐈_d × c is the transpose of 𝐈_c × d.

Towards explaining the other quantities in the AIR matrix shown in Fig. <ref>, for a given K,D  and U, let  λ_-1=n,λ_0=m-n and
    n   =β_0 λ_0+λ_1, 
    λ_0   =β_1λ_1+λ_2, 
    λ_1   =β_2λ_2+λ_3, 
    λ_2   =β_3λ_3+λ_4, 
             ⋮
    λ_i   =β_i+1λ_i+1+λ_i+2, 
             ⋮
    λ_l-1   =β_lλ_l.

where λ_l+1=0 for some integer l, λ_i,β_i are positive integers and λ_i < λ_i-1 for i=1,2,…,l.


		










 §.§ Contributions

The contributions of this paper are summarized below:


  * We derive a lowerbound on the broadcast rate of SUICP(SCI) to be 1+D+m/m+1.

  * For the SUICP(SCI) with arbitrary K,D,U and m, we define a set 𝐒_K,D,U,m consisting of pairs of integers (a,b) and prove that the rate 1+D+m+a/b/m+1 for every (a,b) ∈𝐒_K,D,U,m is achievable by b(m+1)-dimensional vector linear index codes and an appropriate sized AIR matrix. The constructed codes are independent of field size.    

  * We show that the constructed vector linear index codes are atmost K mod (D+2m+1)/(m+1)⌊K/D+2m+1⌋ away from the lowerbound on the broadcast rate of SUICP(SCI).

  * By using our results in <cit.>, we give an upperbound on the broadcast rate of SUICP(SCI). 

  * We obtain the capacity of SUICP(SCI) with arbitrary K,D and U with m satisfying the relation gcd(K,D+2m+1) ≥ U+2m+1. 



For a subset I={i_1,i_2,…,i_l}⊆{1,2,…,K}, let x_I={x_i_1,x_i_2,…,x_i_l}. Let L_k be the kth row of an AIR matrix for k ∈ [0:K-1] and let L_I={L_i_1,L_i_2,…,L_i_l}. For vector subspaces 𝐒_i_1,𝐒_i_2,…,𝐒_i_l, let 𝐒_I={𝐒_i_1,𝐒_i_2,…,𝐒_i_l} and <𝐒_I>=<𝐒_i_1,𝐒_i_2,…,𝐒_i_l> denote the vector subspace spanned by all the vectors present in 𝐒_i_1,𝐒_i_2,…,𝐒_i_l. 


The remaining part of this paper is organized as follows. In Section <ref>, we derive a lowerbound on the broadcast rate of SUICP(SCI). In Section <ref>, for SUICP(SCI), we define a set 𝐒_K,D,U,m of 2-tuples such that for every (a,b) ∈𝐒_K,D,U,m, the rate 1+D+m+a/b/m+1 is achievable by using AIR matrices with vector linear index codes over every field. We also derive an upperbound on the broadcast rate of SUICP(SCI). In Section <ref>, we derive the capacity of SUICP(SCI) for some special cases. We conclude the paper in Section <ref>.
 




§ LOWERBOUND ON THE BROADCAST RATE OF SUICP(SCI)


In this section, we derive a lowerbound on the broadcast rate of SUICP(SCI). In an t-dimensional vector linear index code, x_k ∈𝔽^t_q for k ∈ [0:K-1]. A t-dimensional vector linear index code of length N is represented by an encoding matrix 𝐋 (∈𝔽^Kt× N_q), where the jth column contains the coefficients used for mixing the t-dimensional messages x_0,x_1,…,x_K-1 to get the jth index code symbol. Let L_0,L_1,…, L_Kt-1 be the Kt rows of the encoding matrix 𝐋. Let 𝐒̃_k be the t × N matrix 

    𝐒̃_k=.[[     L_kt;   L_kt+1;        ⋮; L_kt+t-1 ]].

for k ∈ [0:K-1]. A codeword of the index code is 

    [c_0 c_1 … c_N-1]=𝐱𝐋=∑_i=0^K-1x_i𝐒̃_k,

where 𝐱=[x_0,1 x_0,2 … x_0,t x_1,1 x_1,2 … x_1,t … x_K-1,t]. The kth matrix 𝐒̃_k (∈𝔽^t × N_q) contains the coefficients used for mixing the t-dimensional message x_k in the N index code symbols. That is, <L_kt, L_kt+1,…, L_kt+t-1> is the subspace assigned to the message x_k in 𝔽_q^N for k ∈ [0:K-1].














Maleki,  Cadambe and Jafar <cit.> found the capacity of single unicast index coding problems with symmetric and neighboring side-information (SUICP(SNC)) with K messages and K receivers, each receiver has a total of Ũ+D̃<K side-information, corresponding to the Ũ messages before and D̃ messages after its desired message. In this setting, the kth receiver R_k demands the message x_k having the side-information

    K_k= {x_k-Ũ,…,x_k-2,x_k-1}∪{x_k+1, x_k+2,…,x_k+D̃}.


The capacity of this ICP is:

    C={[  1               Ũ+D̃=K-1; Ũ+1/K-D̃+Ũ     Ũ+D̃≤ K-2. ].

where Ũ,D̃∈ ℤ, 0 ≤Ũ≤D̃.

Maleki,  Cadambe and Jafar <cit.> prove the capacity given in (<ref>) by using dimension counting outerbound. 



Suppose 𝒱_k denote the subspace assigned to each message x_k for k ∈ [0:K-1]. Define α_j as follows.

    α_j=∑_i=0^K-1dim<𝒱_k,𝒱_k+1,…,𝒱_k+j-1>.



















In SUICP(SNC), every j (j≤Ũ+1) consecutive messages satisfy the property that for every receiver R_k whose wanted message is in these j consecutive messages, every other message in the j messages is in the side-information to R_k. Maleki et.al proved the following Lemma (Lemma 4 in <cit.>) to bound α_j in SUICP(SNC).


For j=2,3,…,Ũ+1,

    α_j ≥Ũ+j/Ũ+1α_1.



In SUICP(SCI), every j (j ≤ m+1) consecutive messages satisfy the property that for every receiver R_k whose wanted message is in these consecutive j messages, every other message in these j consecutive messages is in the side-information to R_k. Hence, for SUICP(SCI), we  prove the following lemma which is analogous to Lemma <ref> for SUICP(SNC).


For j=2,3,…,m+1,  

    α_j ≥m+j/m+1α_1.



We have 

    ∑_i=1^K dim<𝒱_i,𝒱_i+1,…,𝒱_i+j-2,𝒱_i+j-2+m+1>
        =∑_i=1^K dim<𝒱_i,𝒱_i+1,… ,𝒱_i+j-2>_α_j-1+∑_i=1^Kdim( 𝒱_i+j-2+m+1)_α_1.


(<ref>) follows from the fact that for the receiver R_i+j-2+m+1, the message symbols x_i,x_i+1,…,x_i+j-2 are in interference and hence <𝒱_i,𝒱_i+1, …𝒱_i+j-2> ∩𝒱_i+j-2+m+1=ϕ.
 
In (<ref>), we upperbound 
    ∑_i=1^K dim<𝒱_i,𝒱_i+1,…,𝒱_i+j-2,𝒱_i+j-2+m+1>
 by using the submodular property of dimension function (for subspaces 𝒱_i_1 and 𝒱_i_2, we have dim(𝒱_i_1)+dim(𝒱_i_2)=dim(𝒱_i_1∪𝒱_i_2)+dim(𝒱_i_1∩𝒱_i_2)).

From (<ref>) and (<ref>), we have 

    α_j-1+α_1 ≤ (m+1)α_j-mα_j-1.

Hence, we have

    (m+1)α_j    ≥ (m+1)α_j-1+α_1 
       ≥ (m+1)α_j-2+2α_1 
       ≥ (m+1)α_j-3+3α_1 
       ≥…≥ (m+1)α_1+(j-1)α_1.

This proves Lemma <ref>.



For SUICP(SCI) with arbitrary K,D,U and m, define t and j as follows,

    if D mod (m+1) = 0 
                    t= D/m+1-1,  j=m+1, 
       if D mod (m+1) ≠ 0
                    t=⌊D/m+1⌋,  j=D mod (m+1).

then, α_D≥ tα_1+α_j.



    α_D   =α_tm+j
       =∑_i=1^K dim<𝒱_i,𝒱_i+1,…,𝒱_tm+j-1>
       ≥∑_i=1^K dim<𝒱_i,𝒱_i+1,…,𝒱_i+j-1,𝒱_i+j-1+m+1, 
                𝒱_i+j-1+2(m+1),…,𝒱_i+j-1+t(m+1)>
       =∑_i=1^K {dim<𝒱_i,𝒱_i+1,…,𝒱_i+j-1>
                 +dim(𝒱_i+j-1+m+1)+    dim(𝒱_i+j-1+2(m+1))
                 +…+dim(𝒱_i+j-1+t(m+1))}
       = tα_1+α_j.




Consider a SUICP(SCI) with arbitrary K,D,U and m. The broadcast rate β of this ICP is lowerbounded by 
    β≥ 1 + D+m/m+1.



From Lemma <ref> and <ref>, we have 

    α_D≥ tα_1+α_j    ≥  tα_1 + m+j/m+1α_1 
       = t(m+1)+j+m/m+1α_1=D+m/m+1α_1.


Then the dimension of the desired message plus the dimension of the interference at all receivers should be less than or equal to 

    α_D+α_1  ≥D+m/m+1α_1 + α_1.


The broadcast rate should be greater than or equal to the number of dimensions required by wanted message and interference per message symbol. Hence, we have

    β≥α_D+α_1/α_1≥ 1+ D+m/m+1.

This completes the proof.





§ NEAR-OPTIMAL VECTOR LINEAR INDEX CODES OF SUICP(SCI)


In this section, we define a set 𝐒_K,D,U,m of 2-tuples such that for every (a,b) ∈𝐒_K,D,U,m, the rate 1+D+m+a/b/m+1 is achievable by using AIR matrices with vector linear index codes over every field. Constructing vector linear index codes for SUICP(SCI) follows from the two steps given below.


  * First we convert the SUICP(SCI) problem into SUICP(SNI) problem by converting the m+1 message symbols into one extended message symbol.

  * We construct vector linear index codes for SUICP(SCI) by constructing vector linear index codes for SUICP(SNI).
 



In <cit.>, we proved the following interference alignment Lemma for SUICP(SNI).


Consider a SUICP(SNI) with K messages, D and U interfering messages after and before the desired message. Let 𝐋 be a t-dimensional vector encoding matrix (not necessarily an AIR matrix) of size Kt × N for this index coding problem. Let the vector index code be generated by multiplying Kt message symbols [x_0,1 x_0,2 … x_0,t x_1,1 x_1,2 … x_1,t … x_K-1,t] with the encoding matrix 𝐋. Let 𝐒_k be the row space of 𝐒̃_k and 𝐒_k ∖ i be the subspace spanned by the t-1 rows in 𝐒̃_k after deleting the row L_kt+i. The receiver R_k can decode x_k,1,x_k,2,…,x_k,t if and only if 

    L_kt+i∉  < 𝐒_I_k,𝐒_k ∖ i >

for k∈ [0:K-1], i ∈ [0:t-1].




Consider the SUICP(SNI) with K messages, D interference after and U interference before the desired message. Let 𝐋 be a scalar linear encoding matrix (not necessarily an AIR matrix) of size K × N for this index coding problem. The receiver R_k can decode x_k if and only if 

    L_k∉  < L_I_k>

for k∈ [0:K-1].


In <cit.>, we proved the following property of an AIR matrix. We use Lemma <ref> in the proof of Theorem <ref>.












In the AIR matrix of size g × h for some positive integers g and h ≤ g, every row L_k is not in the span of h-1 rows above and gcd(g,h)-1 rows below L_k for k ∈ [0:g-1].












Consider a SUICP(SCI) with arbitrary K,D,U and m. Define the set 𝐒_K,D,U,m as  

    𝐒_K,D,U,m={(a,b):gcd(bK,b(D+   2m+1)+a)≥
        b(U+2m+1)}

for a ∈ Z_≥ 0 and b ∈ Z_>0. 


In Theorem <ref>, we convert the SUICP(SCI) into SUICP(SNI) and give the construction of near-optimal vector linear index codes for SUICP(SCI) with arbitrary K,U,D and m.



Given arbitrary positive integers K,D,U and m, consider the SUICP(SCI) with K messages {x_0,x_1,⋯,x_K-1} and the receivers being K, and the receiver R_k for k ∈ [0:K-1] wanting the message x_k and having the interference given by 

    I_k=    {x_k-U-m,…,x_k-m-2,x_k-m-1} ∪
       {x_k+m+1,x_k+m+2,…,x_k+m+D}.

Let (a,b) ∈𝐒_K,D,U,m and x_k=(x_k,1,x_k,2,⋯,x_k,b(m+1)) be the message vector wanted by the kth receiver R_k, where x_k ∈𝔽_q^b(m+1), x_k,i∈𝔽_q for every k ∈ [0:K-1] and i ∈ [1:b(m+1)]. Let

    y_k,j=∑_i=1^m+1 x_k+1-i,(j-1)(m+1)+i

for k ∈ [0:K-1] and j ∈ [1:b]. Let 𝐋 be the AIR matrix of size Kb × (b(D+2m+1)+a) and L_k be the kth row of 𝐋 for every k ∈ [0:Kb-1]. The b(m+1) dimensional vector linear index code for the given SUICP(SCI) is given by 

    [c_0 c_1 … c_b(D+2m+1)+a-1]=∑_k=0^K-1∑_j=1^by_k,jL_kb+j-1.
 




We prove that every receiver R_k for k ∈ [0:K-1] decodes its b(m+1) wanted message symbols x_k,1,x_k,2,…,x_k,b(m+1). We have

    y_k,j=∑_i=1^m+1 x_k+1-i,(j-1)(m+1)+i

for k ∈ [0:K-1] and j ∈ [1:b]. We refer y_k,j as extended message symbol. The alignment of extended message symbols y_k,1 for k ∈ [0:K-1] is shown in Fig. <ref>.


The extended message symbol y_k,j comprises of m+1 message symbols x_k,(j-1)(m+1)+1, x_k-1,(j-1)(m+1)+2,…, x_k-m,(j-1)(m+1)+m+1. The Kb(m+1) message symbols x_k,i for k ∈ [0:K-1] and i ∈ [1:b(m+1)] appear exactly once in Kb extended message symbols y_k,j for k ∈ [0:K-1] and j ∈ [1:b].

We say that the extended message symbol y_t is in the interference of R_k if 


  * y_t comprises of atleast one message symbol belonging to ℐ_k (or)

  * y_t comprises of a message symbol belonging to x_k and R_k is yet to decode this message symbol. 


For the receiver R_k, its wanted message symbol x_k,(j-1)(m+1)+t is present in in the extended message symbol y_k+t-1,j for every j ∈ [1:b] and t ∈ [1:m+1]. We have 

    y_k+t-1,j=∑_i=1^m+1 x_k+t-i,(j-1)(m+1)+i.


In y_k+t-1,j, every message symbol other than  x_k,(j-1)(m+1)+t is in side-information of R_k for every k ∈ [0:K-1],j ∈ [1:b] and t ∈ [1:m+1].

From the the alignment of the extended message symbols y_k,j for every k ∈ [0:K-1] and j ∈ [1:b], we can conclude the following observations regarding the number of interfering extended messages after y_k-t+1,j.  



  * In y_k+s,j, every message symbol is in the side-information of R_k except x_k,(j-1)(m+1)+s+1 for s ∈ [t:m]. If R_k has not decoded x_k,(j-1)(m+1)+s+1, then y_k+s,j acts as an interference to R_k. There exists atmost b(m-t) interfering extended message symbols like this.

  * In y_k+m+s,j, the message symbol x_k+m+s,(j-1)(m+1)+1 is in the interference 
to R_k for every j ∈ [1:b] and s ∈ [1:D]. There exists bD interfering extended message symbols like this.

  * In y_k+m+D+s,j, the message symbol x_k+m+D,(j-1)(m+1)+s+1 is in the interference to R_k for every j ∈ [1:b] and s ∈ [1:m]. There exists bm interfering extended message symbols like this.

  * In y_k+t-1,j^' for j^'∈ [1:b] and j^'≠ j, the message symbol x_k,(j^'-1)(m+1)+t is present and it contributes to interference to R_k if R_k has not decoded it before. There exists atmost b-1 interfering extended message symbols like this.


From the the alignment of the extended message symbols y_k,j for every k ∈ [0:K-1] and j ∈ [1:b], we can conclude the following observations regarding the number of interfering extended messages before y_k-t+1,j. 


  * In y_k+s,j for s ∈ [0:t-2], every message symbol is in side-information of R_k except x_k,(j-1)(m+1)+s+1. If R_k has not decoded x_k,(j-1)(m+1)+s+1, then y_k+s,j acts as an interference to R_k. There exists atmost bt interfering extended message symbols like this.

  * In the extended message symbol y_k-s,j, the message symbol x_k-m-s,(j-1)(m+1)+m+1 is in the interference 
to R_k for every j ∈ [1:b] and s ∈ [1:U]. There exists bU interfering extended message symbols like this.

  * In the extended message symbol y_k-U-s,j, the message symbol x_k-m-U,(j-1)(m+1)+m+1-s is in the interference to R_k for every j ∈ [1:b] and s ∈ [1:m]. There exists bm interfering extended message symbols like this.

  * In y_k+t-1,j^' for j^'∈ [1:b] and j^'≠ j, the message symbol x_k,(j^'-1)(m+1)+t is present and it contributes to interference to R_k if R_k has not decoded it before. There exists atmost b-1 interfering extended message symbols like this.


For t ∈ [0:K-1]/[k-m-U:k+D+2m], every message symbol in y_t,j is in side-information of R_k for every k ∈ [0:K-1] and j ∈ [1:b].

Hence, there exists atmost 
    b(m-t)+bD+bm+b-1
 extended message symbols after y_k+t-1,j and 
    bt+bU+bm+b-1
 extended message below  y_k+t-1,j such that every extended message symbol comprises of atleast one message symbol which belongs to x_k ∪ℐ_k. 

If t=m+1, the receiver R_k sees b(D+m)+b-1 interfering messages after and b(U+2m)+b-1 interfering extended message before the desired extended message. If t=1, the receiver R_k sees b(D+2m)+b-1 interfering messages after and b(U+m)+b-1 interfering extended messages before the desired extended message. For any t ∈ [1:m+1], the receiver R_k sees atmost b(D+2m+1)-1 interfering messages after and b(U+2m+1)-1 interfering extended messages before the desired extended message.

Given (a,b) ∈𝐒_K,D,U,m and 𝐋 is the AIR matrix of size Kb × (b(D+2m+1)+a). From Lemma <ref>, every row L_k is not in the span of b(D+2m+1)+a after and gcd(Kb,b(D+2m+1)+a)-1 rows before to L_k for every k ∈ [0:Kb-1]. From Definition <ref>, a and b are the positive integers satisfying the relation

    gcd(Kb,b(D+2m+1)+a)=b(U+2m+1)+c

for some c ∈ Z_≥ 0. Hence, every row L_k in 𝐋 is not in the span of b(D+2m+1)+a-1 rows above and b(U+2m+1)-1 rows below to L_k for each k ∈ [0:Kb-1]. According to Lemma <ref>,  the matrix 𝐋 can be used as a b-dimensional encoding matrix for SUICP(SNI) with K messages, b(D+2m)+b-1 and b(U+2m)+b-1 interfering messages after and before. Hence, the receiver R_k decodes y_k+t-1,j and then decodes x_k,(j-1)(m+1)+t for every t ∈ [1:m+1],j ∈ [1:b].

For every message symbol x_k,(j-1)(m+1)+i for i ∈ [1:m+1], the decoding is performed as given below.


  * R_k first decodes the extended message symbol y_k-i+1,j for i ∈ [1:m+1], where the message symbol x_k,(j-1)(m+1)+i is present.

  * In y_k-i+1,j, every message symbol present is in the side-information of R_k. Hence, R_k decodes its wanted message symbol x_k,(j-1)(m+1)+i from y_k-i+1,j.


The matrix 𝐋 is mapping Kb(m+1) message symbols into b(D+2m+1)+a broadcast symbols. The rate achieved by the proposed encoding scheme is given by

    b(D+2m+1)+a/b(m+1)=1+D+m+a/b/m+1.




In Lemma <ref>, we show that the rate achieved by vector linear index codes constructed in Theorem <ref> are atmost  K mod (D+2m+1)/(m+1)⌊K/D+2m+1⌋ away from the lowerbound on broadcast rate of SUICP(SCI).


For every  SUICP(SCI) with arbitrary K,D,U and m, there exists (a,b) ∈𝐒_K,D,U,m such that

    1+D+m+a/b/m+1≤K/(m+1)⌊K/D+2m+1⌋.



We have 

    K=⌊K/D+2m+1⌋(D+2m+1)+K mod (D+2m+1).

Hence, 

    K/⌊K/D+2m+1⌋=D+2m+1+K mod (D+2m+1)/⌊K/D+2m+1⌋.

From (<ref>), we have 

    K/(m+1)⌊K/D+2m+1⌋   =1+D+m/m+1_lowerbound on β+K mod (D+2m+1)/(m+1)⌊K/D+2m+1⌋
       =1+D+m/m+1+α/(m+1)γ,

where α=K mod (D+2m+1) and γ=⌊K/D+2m+1⌋.

From (<ref>), we have

    α=K-γ(D+2m+1)

and these values of α and γ satisfy the equation gcd(K γ,γ(D+2m+1)+α)≥γ (U+2m+1). Hence, (α,γ) ∈𝐒_K,D,U,m. This completes the proof.




In SUICP(SCI), the vector linear index codes constructed by AIR matrices are within K mod (D+2m+1)/(m+1)⌊K/D+2m+1⌋ symbols per message from the lowerbound on broadcast rate given in Theorem <ref>.

































Consider a SUICP(SCI) with K=18,D=7,U=1 and m=2. For this SUICP(SCI), we have D+2m=11,U+2m=5 and gcd(K,D+2m+1)=gcd(18,12)=6 ≥ U+2m+1. Hence, for this SUICP(SCI), (a,b)=(0,1) ∈𝐒_K,D,U,m. The rate achieved by proposed construction is

    1+D+m+a/b/m+1=1+7/3+2/3=4.

We have y_k=x_k,1+x_k-1,2+x_k-2,3 for k ∈ [0:17]. The index code for this SUICP(SCI) is obtained by 

    [c_0 c_1 … c_11]=[y_0 y_1 … y_17]𝐋_18 × 12,

where 𝐋_18 × 12 is the AIR matrix of size 18 × 12 as given below.

=0.5pt



    𝐋_18 × 12=[
    [ 1 0 0 0 0 0 0 0 0 0 0 0; 0 1 0 0 0 0 0 0 0 0 0 0; 0 0 1 0 0 0 0 0 0 0 0 0; 0 0 0 1 0 0 0 0 0 0 0 0; 0 0 0 0 1 0 0 0 0 0 0 0; 0 0 0 0 0 1 0 0 0 0 0 0; 0 0 0 0 0 0 1 0 0 0 0 0; 0 0 0 0 0 0 0 1 0 0 0 0; 0 0 0 0 0 0 0 0 1 0 0 0; 0 0 0 0 0 0 0 0 0 1 0 0; 0 0 0 0 0 0 0 0 0 0 1 0; 0 0 0 0 0 0 0 0 0 0 0 1; 1 0 0 0 0 0 1 0 0 0 0 0; 0 1 0 0 0 0 0 1 0 0 0 0; 0 0 1 0 0 0 0 0 1 0 0 0; 0 0 0 1 0 0 0 0 0 1 0 0; 0 0 0 0 1 0 0 0 0 0 1 0; 0 0 0 0 0 1 0 0 0 0 0 1;   ]]



The 12 broadcast symbols for this SUICP(SCI) are given in Table <ref> below. 



Receiver R_k required to decode three message symbols x_k,1,x_k,2 and x_k,3 for k ∈ [0:17]. Let τ_k,j be the code symbols used by receiver R_k to decode x_k,j for k ∈ [0:17] and j ∈ [1:3]. Table <ref> gives the code symbols used by each receiver to decode its wanted message symbol.





Consider a SUICP(SCI) with K=13,D=5,U=1 and m=1. For this SUICP(SCI), we have D+2m=7,U+2m=3 and a=2,b=3 satisfy the equation gcd(bK,b(D+2m+1)+a)≥ 6 ≥ b(U+2m+1). The rate achieved by proposed construction is

    1+D+m+a/b/m+1   =1+5+1+2/3/2
        =26/6=3.66.

We have y_k,j=x_k,2(j-1)+1+x_k-1,2(j-1)+2 for k ∈ [0:12] and j ∈ [1:3]. The index code for this SUICP(SCI) is obtained by 

    [c_0 c_1 … c_25]
       =[y_0,1 y_0,2 y_0,3_y_0 y_1,1 y_1,2 y_1,3_y_1 … y_12,1 y_12,2 y_12,3_y_12]𝐋,

where 𝐋 is the AIR matrix of size 26 × 39 as given below.
=0.5pt



    𝐋_39 × 26=[
    [      𝐈_26;          ; 𝐈_13 𝐈_13;           ]]



The 26 broadcast symbols for this SUICP(SCI) are given Table <ref>. 



Receiver R_k required to decode five message symbols x_k,1,x_k,2,…,x_k,6 for k ∈ [0:12]. Let τ_k,j be the code symbols used by receiver R_k to decode x_k,j for k ∈ [0:12] and j ∈ [1:6]. Table <ref> gives the code symbols used by each receiver to decode its wanted message symbol.






Consider a SUICP(SCI) with K=71,D=17,U=3 and m=5. For this SUICP(SCI), we have D+2m=27,U+2m=13 and a=2,b=5 satisfy the equation gcd(bK,b(D+2m+1)+a) ≥ b(U+2m+1). The rate achieved by proposed construction is

    1+D+m+a/b/m+1   =1+17+5+2/5/6
       =142/30=4.733.

We have y_k,j=x_k,6(j-1)+1+x_k,6(j-1)+2+x_k,6(j-1)+3+x_k,6(j-1)+4+x_k,6(j-1)+5+x_k,6(j-1)+6 for k ∈ [0:70] and j ∈ [1:5]. The 30-dimensional vector linear index code for this SUICP(SCI) is obtained by 

    [c_0 c_1 … c_141]=
       
    [y_0,1 y_0,2… y_0,5_y_0 y_1,1 y_1,2… y_1,5_y_1…y_70,1 y_70,2… y_70,5_y_70]𝐋,

where 𝐋 is the AIR matrix of size 355 × 142.




 §.§ Upperbound on the broadcast rate of SUICP(SCI)

In <cit.>, we used extended Euclid algorithm to derive an upperbound on the broadcast rate of SUICP(SNI). In this subsection, we give an upperbound on the broadcast rate of SUICP(SCI) by using the results in <cit.>.


Let 
    a_min=min_(a,b) ∈𝐒_K,D,U,m a.
 Define b_min as the corresponding value of a_min such that (a_min,b_min) ∈𝐒_K,D,U,m.


In <cit.>, we proved that b_min is unique in a given 𝐒_K,D,U,m and a_min/b_min is the value of a/b such that (a,b) ∈𝐒_K,D,U,m and a/b is minimum. In <cit.>, we gave an algorithm to find the values of a_min and b_min for the given SUICP(SNI). The algorithm given in <cit.> can be used to find the values of a_min and b_min for SUICP(SCI) by replacing D with D+2m and U with U+2m.


Consider a SUICP(SCI) with arbitrary K,D,U and m. The broadcast rate β of this index coding problem is upperbounded by 
    β≤ 1 + D+m+a_min/b_min/m+1.



For every (a,b) ∈𝐒_K,D,U,m, Theorem <ref> gives the construction of vector linear index codes for SUICP(SCI) with rate 

    1 + D+m+a/b/m+1.


We have (a_min,b_min) ∈𝐒_K,D,U,m. Hence, Theorem <ref> gives the construction of vector linear index codes for SUICP(SCI) with rate 

    1 + D+m+a_min/b_min/m+1.

The broadcast rate is the infimum of of all achievable rates. This completes the proof. 



Consider a SUICP(SCI) with K=71,D=5,U=5 and m=2. For this SUICP(SCI), we have D+2m=21,U+2m=10. By using the Algorithm given in <cit.>,  we can obtain a_min=1 and b_min=7. Hence, the broadcast rate of this SUICP(SCI) is upperbounded by 
    β≤ 1+D+m+a_min/b_min/m+1=1+5+2+1/7/3=22/5=3.38.



In Section <ref>, we shown that the broadcast rate of SUICP(SCI) is lowerbounded by 

    β≥ 1+D+m/m+1=1+5+2/3=3.33.

Hence, for this SUICP(SCI), we have  

    3.33 ≤β≤ 3.38.




Consider a SUICP(SCI) with K=93,D=11,U=1 and m=4. For this SUICP(SCI), we have D+2m=19,U+2m=9. By using the Algorithm given in <cit.>,  we can obtain a_min=2 and b_min=3. Hence, the broadcast rate of this SUICP(SCI) is upperbounded by 
    β≤ 1+D+m+a_min/b_min/m+1=1+11+4+2/3/5=4.13.



In Section <ref>, we shown that the broadcast rate of SUICP(SCI) is lower bounded by 

    β≥ 1+D+m/m+1=1+11+4/5=4.

Hence, for this SUICP(SCI), we have

    4.00 ≤β≤ 4.13.





§ CAPACITY OF SOME SUICP(SCI)


In this section, we derive the capacity of SUICP(SCI) for arbitrary K,D and U, but m satisfying the condition gcd(K,D+2m+1)≥ U+2m+1.



Consider an SUICP(SCI) with arbitrary K,D and U. For this SUICP(SCI), if m satisfies the condition gcd(K,D+2m+1)≥ U+2m+1, then the capacity of this SUICP(SCI) is given by 

    C=m+1/D+2m+1.



For an SUICP(SCI) with arbitrary K,D,U and m, in Theorem <ref>, we proved that we can combine m+1 message symbols into one extended message symbol and then we can use AIR matrix of size Kb × (b(D+2m+1)+a) to combine Kb extended symbols into b(D+2m+1)+a broadcast symbols to generate a b(m+1) dimensional vector linear index code for the given SUICP(SCI). The rate achieved by using the proposed construction in Theorem <ref> is 

    b(D+2m+1)+a/b(m+1)=1+D+m+a/b/m+1.


Given

    gcd(K,D+2m+1)) ≥ U+2m+1.


Hence, we have (a,b)=(0,1) ∈𝐒_K,D,U,m.  With a=0,b=1, the rate achieved by the proposed construction given in Theorem <ref> reduces to 

    D+2m+1/m+1=1+D+m/m+1.

From Theorem <ref>, we have 

    β≥ 1+D+m/m+1.

From (<ref>) and (<ref>), we have 

    β = 1+D+m/m+1=D+2m+1/m+1.

This completes the proof.



Consider an SUICP(SCI) with arbitrary K,D and m. For this SUICP(SCI), if U satisfies the condition gcd(K,D+2m+1)≥ U+2m+1, then the capacity of this SUICP(SCI) is given by 

    C=m+1/D+2m+1.



In <cit.>, we derived the capacity of SUICP(SNI) for arbitrary K and D, but U=gcd(K,D+1)-1. The capacity result in <cit.> is a special case of Theorem <ref> with m=0.



Consider a SUICP(SCI) with K=18,D=7,U=1 and m=2. For this SUICP(SCI), we have D+2m=11,U+2m=5 and gcd(K,D+2m+1)=gcd(18,12)=6 ≥ U+2m+1. The capacity of this SUICP(SCI) is

    1+D+m/m+1=1+7+2/3=4.

The optimal index code for this SUICP(SCI) is given in Example <ref>. 




Consider a SUICP(SCI) with K=55,D=13,U=2 and m=4. For this SUICP(SCI), we have D+2m=21,U+2m=10 and gcd(K,D+2m+1)=gcd(55,22)=11 ≥ U+2m+1. The capacity of this SUICP(SCI) is

    1+D+m/m+1=1+13+4/5=22/5=4.4.


The optimal index code for this SUICP(SCI) is a five dimensional vector linear index code. The index code for this SUICP(SCI) is given by 

    [c_0 c_1 … c_21]=[y_0,1 y_1,1 … y_54,1]𝐋,

where 𝐋 is the AIR matrix of size 55 × 22 and y_k,1=x_k,1+x_k,2+x_k,3+x_k,4+x_k,5 for k ∈ [0:54]. 


For arbitrary K,D,U and m, the broadcast rate of SUICP(SCI) is bounded by 

    1+D+m/m+1≤β≤ 1+ D+m/m+1+ a_min/b_min/m+1.



Proof follows from Theorem <ref> and <ref>.



§ CONCLUSION


In this paper, we constructed near optimal vector linear index codes for SUICP(SCI) with arbitrary K,U,D and m. The constructed codes are independent of field size. We gave an upperbound and lowerbound on the broadcast rate of the SUICP(SCI) with arbitrary K,U,D and m. We give the capacity of SUICP(SCI) with arbitrary K,D and U with m satisfying the relation gcd(K,D+2m+1) ≥ U+2m+1. The capacity and optimal index coding of SUICP(SCI) with arbitrary K,D,U and m is a challenging open problem.


§ ACKNOWLEDGMENT

This work was supported partly by the 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.

160

ISCO
Y. Birk and T. Kol, “Informed-source coding-on-demand (ISCOD) over broadcast channels", in Proc. IEEE Conf. Comput. Commun., San Francisco, CA, 1998, pp. 1257-1264.
OnH
L Ong and C K Ho, “Optimal index codes for a class of multicast networks with receiver side-information”, in Proc. IEEE ICC, 2012, pp. 2213-2218.
YBJK
Z. Bar-Yossef, Z. Birk, T. S. Jayram and T. Kol, “Index coding with side-information", in Proc. 47th Annu. IEEE Symp. Found. Comput. Sci., Oct. 2006, pp. 197-206.
ICVLP
A. Blasiak, R. Kleinberg and E. Lubetzky, “Broadcasting with side-information: Bounding and approximating the broadcast rate", in IEEE Trans. Inf. Theory,, vol. 59, no.9, pp.5811-5823, Sep. 2013.
VaR5 M. B. Vaddi and B. S. Rajan, “Near-Optimal vector linear index codes for single unicast index coding problems with symmetric neighboring interference,” in arXiv: 1705.10614  [cs.IT] 28 May 2017.
TIM
S. A. Jafar, “Topological interference management through index coding", IEEE Trans. Inf. Theory, vol. 60, no. 1, pp. 529–568,
Jan. 2014.
VaR2
M. B. Vaddi and B. S. Rajan, “Optimal scalar linear index codes for one-sided neighboring side-information problems”, in Proc. IEEE GLOBECOM Workshop on Network Coding and Applications, Washington, USA, Dec. 2016.
MCJ
H. Maleki, V. Cadambe, and S. Jafar, “Index coding – an interference alignment perspective", in IEEE Trans. Inf. Theory,, vol. 60, no.9, pp.5402-5432, Sep. 2014.
VaR4
M. B. Vaddi and B. S. Rajan, “Capacity of some index coding problems with symmetric neighboring interference”, in arXiv: 1705.05060v2 [cs.IT] 18 May 2017 (To appear in the proceedings of IEEE ITW, Kaohsisung, Taiwan, Nov. 2017).
VaR6 M. B. Vaddi and B. S. Rajan, “A new upperbound on the broadcast rate of index coding problems with symmetric neighboring interference,” in arXiv: 1707.00455  [cs.IT] 03 July 2017.





