Approximate Capacity of a Class of Partially Connected Interference Channels
Muryong Kim Yitao Chen Sriram Vishwanath







Approximate Capacity of a Class of
 Partially Connected Interference Channels
    Muryong Kim, Yitao Chen, and Sriram Vishwanath, Senior Member, IEEE



The authors are with the University of Texas at Austin, Austin, TX 78701 USA (e-mail: muryong@utexas.edu, yitaochen@utexas.edu, sriram@ece.utexas.edu).
    December 30, 2023
==================================================================================================================================================================================================================================




We derive inner and outer bounds on the capacity region for a class of three-user partially connected interference channels. We focus on the impact of topology, interference alignment, and interplay between interference and noise. The representative channels we consider are the ones that have clear interference alignment gain. For these channels, Z-channel type outer bounds are tight to within a constant gap from capacity. We present near-optimal achievable schemes based on rate-splitting and lattice alignment.



Interference channel, interference alignment, nested lattice code, side information graph, topological interference management.








§ INTRODUCTION



 §.§ Motivation

The capacity of the Interference channel remains one of the most challenging open problems in the domain of network information theory. The capacity region is not known in general, except for a specific range of channel parameters. For the two-user scalar Gaussian interference channel, where the interference alignment is not required, the approximate capacity region to within one bit is known <cit.>. For the channels where interference alignment is required such as the K-user Gaussian interference channel <cit.> and the Gaussian X-channel <cit.>, a tight characterization of the capacity region is not known, even for symmetric channel cases.

A tractable approach to the capacity of interference channels is to consider partial connectivity of interference links and analyze the impact of topology on the capacity. Topological interference management <cit.> approach gives important insights on the degrees-of-freedom (DoF) of partially connected interference channels and their connection to index coding problems <cit.>. It is shown that the symmetric DoF of a partially connected interference channel can be found by solving the corresponding index coding problem.

In this paper, we consider a class of three-user partially connected interference channels and characterize approximate capacity regions at finite SNR. We focus on the impact of interference topology, interference alignment, and interplay between interference and noise. We choose a few representative topologies where we can achieve clear interference alignment gain. For these topologies, Z-channel type outer bounds are tight to within a constant gap from the corresponding inner bound. For each topology, we present an achievable scheme based on rate-splitting, lattice alignment, and successive decoding.



 §.§ Related Work

Lattice coding based on nested lattices is shown to achieve the capacity of the single user Gaussian channel in <cit.>. The idea of lattice-based interference alignment by decoding the sum of lattice codewords appeared in the conference version of <cit.>. This lattice alignment technique is used to derive capacity bounds for three-user interference channel in <cit.>. The idea of decoding the sum of lattice codewords is also used in <cit.> to derive the approximate capacity of the two-way relay channel. An extended approach, compute-and-forward <cit.> enables to first decode some linear combinations of lattice codewords and then solve the lattice equation to recover the desired messages. This approach is also used in <cit.> to characterize approximate sum-rate capacity of the fully connected K-user interference channel.

The idea of sending multiple copies of the same sub-message at different signal levels, so-called Zigzag decoding, appeared in <cit.> where receivers collect side information and use them for interference cancellation.

The K-user cyclic Gaussian interference channel is considered in <cit.> where an approximate capacity for the weak interference regime (_k≥_k for all k) and the exact capacity for the strong interference regime (_k≤_k for all k) are derived. Our type 4 and 5 channels are K=3 cases in mixed interference regimes, which were not considered in <cit.>.



 §.§ Main Results

We consider five channel types defined in Table <ref> and described in Fig. <ref> (a)–(e). Each channel type is a partially connected three-user Gaussian interference channel. Each transmitter is subject to power constraint 𝔼[X_k^2]≤ P_k=P. Let us denote the noise variance by N_k=𝔼[Z_k^2]. Without loss of generality, we assume that N_1≤ N_2≤ N_3.


The side information graph representation of an interference channel satisfies the following.


  * A node represents a transmitter-receiver pair, or equivalently, the message.

  * There is a directed edge from node i to node j if transmitter i does not interfere at receiver j.


The side information graphs for five channel types are described in Fig. <ref> (f)–(j). We state the main results in the following two theorems, of which the proofs will be given in the main body of the paper.


For the five channel types, if (R_1,R_2,R_3) is achievable, it must satisfy

    ∑_j∈𝒦 R_j ≤(1+|𝒦|P/min_j∈𝒦{N_j})

for every subset 𝒦 of the nodes {1,2,3} that does not include a directed cycle in the side information graph over the subset.


 

For any rate triple (R_1,R_2,R_3) on the boundary of the outer bound region, the point (R_1-1,R_2-1,R_3-1) is achievable.








 §.§ Paper Organization and Notation

The capacity outer bounds are derived in Section II. The inner bounds for each channel type and the corresponding gap analysis are given in Section III, IV, V, VI, VII, respectively. Section VIII concludes the paper. While lattice coding-based achievable rate regions for channel types 4 and 5 are presented in Section VI and VII, random coding achievability is given in Appendix.

Signal 𝐱_ij is a coded version of message M_ij with code rate R_ij unless otherwise stated. The single user capacity at receiver k is denoted by C_k=(1+P/N_k). Let 𝒞 denote the capacity region of an interference channel. Also, let ℛ_i and ℛ_o denote the capacity inner bound and the capacity outer bound, respectively. Thus, ℛ_i⊂𝒞⊂ℛ_o. Let δ_k denote the gap on the rate R_k between ℛ_i and ℛ_o. Let δ_jk denote the gap on the sum-rate R_j+R_k between ℛ_i and ℛ_o. For example, if

    ℛ_i={(R_j,R_k): R_k≤ L_k, R_j+R_k≤ L_jk}
          ℛ_o={(R_j,R_k): R_k≤ U_k, R_j+R_k≤ U_jk},

then δ_k=U_k-L_k and δ_jk=U_jk-L_jk. For side information graph, we use graph notation of <cit.>. For example, 𝒢_1={(1|3),(2),(3|1)} means that node 1 has an incoming edge from node 3, that node 2 has no incoming edge, and that node 3 has an incoming edge from node 1.







§ CAPACITY OUTER BOUNDS

We prove the capacity outer bound in Theorem 1 for each channel type. The result is summarized in Table <ref>. The shape of the outer bound region is illustrated in Fig. <ref>. For all channel types, we assume P_1=P_2=P_3=P and N_1≤ N_2≤ N_3.



 §.§ Channel Type 1

In this section, we present an outer bound on the capacity region of Type 1 channel defined by

    [ [ Y_1; Y_2; Y_3;     ]]
    =[ [ 1 1 0; 1 1 1; 0 1 1;   ]]
    [ [ X_1; X_2; X_3;     ]]
    +[ [ Z_1; Z_2; Z_3;     ]].

We state the outer bound in the following theorem.

The capacity region of Type 1 channel is contained in the following outer bound region:

    R_k≤ C_k, k=1,2,3
          R_1+R_2≤(1+P/N_1)+(2P+N_2/P+N_2)
          R_2+R_3≤(1+P/N_2)+(2P+N_3/P+N_3).


The individual rate bounds are obvious. We proceed to sum-rate bounds.

    n(R_1+R_2-ϵ)
            ≤ I(X_1^n;Y_1^n)+I(X_2^n;Y_2^n)
            ≤ I(X_1^n;Y_1^n|X_2^n)+I(X_2^n;Y_2^n|X_3^n)
            = h(Y_1^n|X_2^n)-h(Y_1^n|X_1^n,X_2^n)
                 +h(Y_2^n|X_3^n)-h(Y_2^n|X_2^n,X_3^n)
            = h(X_1^n+Z_1^n)-h(Z_1^n)
                 +h(X_1^n+X_2^n+Z_2^n)-h(X_1^n+Z_2^n)
            ≤n/2log(P+N_1/N_1)+n/2log(2P+N_2/P+N_2)

where the first inequality is by Fano's inequality, the second inequality due to the independence of X_1,X_2,X_3. The third inequality holds from the fact that Gaussian distribution maximizes differential entropy and that h(X_1^n+Z_1^n)-h(X_1^n+Z_2^n) is also maximized by Gaussian distribution. Similarly,

    n(R_2+R_3-ϵ)
            ≤ I(X_2^n;Y_2^n)+I(X_3^n;Y_3^n)
            ≤ I(X_2^n;Y_2^n|X_1^n,X_3^n)+I(X_3^n;Y_3^n)
            = h(Y_2^n|X_1^n,X_3^n)-h(Y_2^n|X_1^n,X_2^n,X_3^n)
                 +h(Y_3^n)-h(Y_3^n|X_3^n)
            = h(X_2^n+Z_2^n)-h(Z_2^n)
                 +h(X_2^n+X_3^n+Z_3^n)-h(X_2^n+Z_3^n)
            ≤n/2log(P+N_2/N_2)+n/2log(2P+N_3/P+N_3).







 §.§ Channel Type 2

In this section, we present an outer bound on the capacity region of Type 2 channel defined by

    [ [ Y_1; Y_2; Y_3;     ]]
    =[ [ 1 1 1; 1 1 0; 1 0 1;   ]]
    [ [ X_1; X_2; X_3;     ]]
    +[ [ Z_1; Z_2; Z_3;     ]].

We state the outer bound in the following theorem.

The capacity region of Type 2 channel is contained in the following outer bound region:

    R_k≤ C_k, k=1,2,3
          R_1+R_2≤(1+P/N_1)+(2P+N_2/P+N_2)
          R_1+R_3≤(1+P/N_1)+(2P+N_3/P+N_3).



    n(R_1+R_2-ϵ)
            ≤ I(X_1^n;Y_1^n)+I(X_2^n;Y_2^n)
            ≤ I(X_1^n;Y_1^n|X_2^n,X_3^n)+I(X_2^n;Y_2^n)
            = h(Y_1^n|X_2^n,X_3^n)-h(Y_1^n|X_1^n,X_2^n,X_3^n)
                 +h(Y_2^n)-h(Y_2^n|X_2^n)
            = h(X_1^n+Z_1^n)-h(Z_1^n)
                 +h(X_1^n+X_2^n+Z_2^n)-h(X_1^n+Z_2^n)
            ≤n/2log(P+N_1/N_1)+n/2log(2P+N_2/P+N_2).


    n(R_1+R_3-ϵ)
            ≤ I(X_1^n;Y_1^n)+I(X_3^n;Y_3^n)
            ≤ I(X_1^n;Y_1^n|X_2^n,X_3^n)+I(X_3^n;Y_3^n)
            = h(Y_1^n|X_2^n,X_3^n)-h(Y_1^n|X_1^n,X_2^n,X_3^n)
                 +h(Y_3^n)-h(Y_3^n|X_3^n)
            = h(X_1^n+Z_1^n)-h(Z_1^n)
                 +h(X_1^n+X_3^n+Z_3^n)-h(X_1^n+Z_3^n)
            ≤n/2log(P+N_1/N_1)+n/2log(2P+N_3/P+N_3).







 §.§ Channel Type 3

In this section, we present an outer bound on the capacity region of Type 3 channel defined by

    [ [ Y_1; Y_2; Y_3;     ]]
    =[ [ 1 0 1; 0 1 1; 1 1 1;   ]]
    [ [ X_1; X_2; X_3;     ]]
    +[ [ Z_1; Z_2; Z_3;     ]].

We state the outer bound in the following theorem.

The capacity region of Type 3 channel is contained in the following outer bound region:

    R_k≤ C_k, k=1,2,3
          R_1+R_3≤(1+P/N_1)+(2P+N_3/P+N_3)
          R_2+R_3≤(1+P/N_2)+(2P+N_3/P+N_3).



    n(R_1+R_3-ϵ)
            ≤ I(X_1^n;Y_1^n)+I(X_3^n;Y_3^n)
            ≤ I(X_1^n;Y_1^n|X_3^n)+I(X_3^n;Y_3^n|X_2^n)
            = h(Y_1^n|X_3^n)-h(Y_1^n|X_1^n,X_3^n)
                 +h(Y_3^n|X_2^n)-h(Y_3^n|X_2^n,X_3^n)
            = h(X_1^n+Z_1^n)-h(Z_1^n)
                 +h(X_1^n+X_3^n+Z_3^n)-h(X_1^n+Z_3^n)
            ≤n/2log(P+N_1/N_1)+n/2log(2P+N_3/P+N_3).


    n(R_2+R_3-ϵ)
            ≤ I(X_2^n;Y_2^n)+I(X_3^n;Y_3^n)
            ≤ I(X_2^n;Y_2^n|X_3^n)+I(X_3^n;Y_3^n|X_1^n)
            = h(Y_2^n|X_3^n)-h(Y_2^n|X_2^n,X_3^n)
                 +h(Y_3^n|X_1^n)-h(Y_3^n|X_1^n,X_3^n)
            = h(X_2^n+Z_2^n)-h(Z_2^n)
                 +h(X_2^n+X_3^n+Z_3^n)-h(X_2^n+Z_3^n)
            ≤n/2log(P+N_2/N_2)+n/2log(2P+N_3/P+N_3).










 §.§ Channel Type 4

In this section, we present an outer bound on the capacity region of Type 4 channel defined by

    [ [ Y_1; Y_2; Y_3;     ]]
    =[ [ 1 0 1; 1 1 0; 0 1 1;   ]]
    [ [ X_1; X_2; X_3;     ]]
    +[ [ Z_1; Z_2; Z_3;     ]].

This is a cyclic Gaussian interference channel <cit.>. We first show that channel type 4 is in the mixed interference regime. By normalizing the noise variances, we get the equivalent channel given by

    [ [ Y_1'; Y_2'; Y_3';      ]]
    =[ [ h_11 h_12 h_13; h_21 h_22 h_23; h_31 h_32 h_33;      ]]
    [ [ X_1; X_2; X_3;     ]]
    +[ [ Z_1'; Z_2'; Z_3';      ]]

where Y_k'=1/√(N_k) Y_k, Z_k'=1/√(N_k)Z_k, N_0=𝔼[Z_k'^2]=1, 𝔼[X_k^2]≤ P_k=P and

    [ [ h_11 h_12 h_13; h_21 h_22 h_23; h_31 h_32 h_33;      ]]
    =[ [ 1/√(N_1)        0 1/√(N_1); 1/√(N_2) 1/√(N_2)        0;        0 1/√(N_3) 1/√(N_3);          ]].

With the usual definitions of _k=h_kk^2 P_k/N_0 and
 _k=h_jk^2 P_k/N_0 for j≠ k as in <cit.>,

    _1=P/N_1≥_1=P/N_2
          _2=P/N_2≥_2=P/N_3
          _3=P/N_3≤_3=P/N_1.

We state the outer bound in the following theorem.

The capacity region of Type 4 channel is contained in the following outer bound region:

    R_k≤ C_k, k=1,2,3
          R_1+R_2≤(1+P/N_1)+(2P+N_2/P+N_2)
          R_1+R_3≤(1+2P/N_1)
          R_2+R_3≤(1+P/N_2)+(2P+N_3/P+N_3).



    n(R_1+R_2-ϵ)
            ≤ I(X_1^n;Y_1^n)+I(X_2^n;Y_2^n)
            ≤ I(X_1^n;Y_1^n|X_3^n)+I(X_2^n;Y_2^n)
            = h(Y_1^n|X_3^n)-h(Y_1^n|X_1^n,X_3^n)
                 +h(Y_2^n)-h(Y_2^n|X_2^n)
            = h(X_1^n+Z_1^n)-h(Z_1^n)
                 +h(X_1^n+X_2^n+Z_2^n)-h(X_1^n+Z_2^n)
            ≤n/2log(P+N_1/N_1)+n/2log(2P+N_2/P+N_2).


    n(R_2+R_3-ϵ)
            ≤ I(X_2^n;Y_2^n)+I(X_3^n;Y_3^n)
            ≤ I(X_2^n;Y_2^n|X_1^n)+I(X_3^n;Y_3^n)
            = h(Y_2^n|X_1^n)-h(Y_2^n|X_1^n,X_2^n)
                 +h(Y_3^n)-h(Y_3^n|X_3^n)
            = h(X_2^n+Z_2^n)-h(Z_2^n)
                 +h(X_2^n+X_3^n+Z_3^n)-h(X_2^n+Z_3^n)
            ≤n/2log(P+N_2/N_2)+n/2log(2P+N_3/P+N_3).


    n(R_1+R_3-ϵ)
            ≤ I(X_1^n;Y_1^n)+I(X_3^n;Y_3^n)
            ≤ I(X_1^n;Y_1^n)+I(X_3^n;Y_3^n|X_2^n)
            ≤ I(X_1^n;Y_1^n)+I(X_3^n;Y_1^n|X_1^n)
            ≤ I(X_1^n,X_3^n;Y_1^n)
            = h(Y_1^n)-h(Y_1^n|X_1^n,X_3^n)
            = h(X_1^n+X_3^n+Z_1^n)-h(Z_1^n)
            ≤n/2log(2P+N_1/N_1)

where we used the fact that I(X_3^n;Y_3^n|X_2^n)=I(X_3^n;X_3^n+Z_3^n)≤ I(X_3^n;X_3^n+Z_1^n)=I(X_3^n;Y_1^n|X_1^n).



















 §.§ Channel Type 5

In this section, we present an outer bound on the capacity region of Type 5 channel defined by

    [ [ Y_1; Y_2; Y_3;     ]]
    =[ [ 1 1 0; 0 1 1; 1 0 1;   ]]
    [ [ X_1; X_2; X_3;     ]]
    +[ [ Z_1; Z_2; Z_3;     ]].

This is a cyclic Gaussian interference channel <cit.>. We first show that channel type 5 is in the mixed interference regime. By normalizing the noise variances, we get the equivalent channel given by

    [ [ Y_1'; Y_2'; Y_3';      ]]
    =[ [ 1/√(N_1) 1/√(N_1)        0;        0 1/√(N_2) 1/√(N_2); 1/√(N_3)        0 1/√(N_3);          ]]
    [ [ X_1; X_2; X_3;     ]]
    +[ [ Z_1'; Z_2'; Z_3';      ]].

We can see that

    _1=P/N_1≥_1=P/N_3
          _2=P/N_2≤_2=P/N_1
          _3=P/N_3≤_3=P/N_2.

We state the outer bound in the following theorem.

The capacity region of Type 5 channel is contained in the following outer bound region:

    R_k≤ C_k, k=1,2,3
          R_1+R_2≤(1+2P/N_1)
          R_2+R_3≤(1+2P/N_2)
          R_1+R_3≤(1+P/N_1)+(2P+N_3/P+N_3).



    n(R_1+R_2-ϵ)
            ≤ I(X_1^n;Y_1^n)+I(X_2^n;Y_2^n)
            ≤ I(X_1^n;Y_1^n)+I(X_2^n;Y_2^n|X_3^n)
            ≤ I(X_1^n;Y_1^n)+I(X_2^n;Y_1^n|X_1^n)
            ≤ I(X_1^n,X_2^n;Y_1^n)
            = h(Y_1^n)-h(Y_1^n|X_1^n,X_2^n)
            = h(X_1^n+X_2^n+Z_1^n)-h(Z_1^n)
            ≤n/2log(2P+N_1/N_1)

where we used the fact that I(X_2^n;Y_2^n|X_3^n)=I(X_2^n;X_2^n+Z_2^n)≤ I(X_2^n;X_2^n+Z_1^n)=I(X_2^n;Y_1^n|X_1^n).

    n(R_2+R_3-ϵ)
            ≤ I(X_2^n;Y_2^n)+I(X_3^n;Y_3^n)
            ≤ I(X_2^n;Y_2^n)+I(X_3^n;Y_3^n|X_1^n)
            ≤ I(X_2^n;Y_2^n)+I(X_3^n;Y_2^n|X_2^n)
            ≤ I(X_2^n,X_3^n;Y_2^n)
            = h(Y_2^n)-h(Y_2^n|X_2^n,X_3^n)
            = h(X_2^n+X_3^n+Z_2^n)-h(Z_2^n)
            ≤n/2log(2P+N_2/N_2)

where we used the fact that I(X_3^n;Y_3^n|X_1^n)=I(X_3^n;X_3^n+Z_3^n)≤ I(X_3^n;X_3^n+Z_2^n)=I(X_3^n;Y_2^n|X_2^n).

    n(R_1+R_3-ϵ)
            ≤ I(X_1^n;Y_1^n)+I(X_3^n;Y_3^n)
            ≤ I(X_1^n;Y_1^n|X_2^n)+I(X_3^n;Y_3^n)
            = h(Y_1^n|X_2^n)-h(Y_1^n|X_1^n,X_2^n)
                 +h(Y_3^n)-h(Y_3^n|X_3^n)
            = h(X_1^n+Z_1^n)-h(Z_1^n)
                 +h(X_1^n+X_3^n+Z_3^n)-h(X_1^n+Z_3^n)
            ≤n/2log(P+N_1/N_1)+n/2log(2P+N_3/P+N_3)






































 §.§ Relaxed Outer Bounds

For ease of gap calculation, we also derive relaxed outer bounds. First, we can see that for N_j≤ N_k,

    (1+P/N_j)+(2P+N_k/P+N_k)≤(1+2P/N_j).

Five outer bound theorems in this section, together with this inequality, give the sum-rate bound expression in Theorem 1.

Next, we can assume that P≥ 3N_j for j=1,2,3. Otherwise, showing one-bit gap capacity is trivial as the capacity region is included in the unit hypercube, i.e., R_j≤(1+P/N_j)< 1. For P≥ 3N_j,

    (1+2P/N_j)=(P/N_j)+(N_j/P+2)
                               ≤(P/N_j)+(7/3)
          (1+P/N_j)≤(P/N_j)+(4/3).

The resulting relaxed outer bounds ℛ_o' are summarized in Table <ref>.




§ INNER BOUND: CHANNEL TYPE 1


Given α=(α_0,α_2)∈ [0,1]^2, the rate region ℛ_α is defined by

    R_1 ≤^+(1-α_0/2-α_0+(1-α_0) P/(α_0+α_2) P+N_2)
                                        +(1+α_0 P/N_1)
          R_2 ≤(1+α_2 P/α_0 P+N_2)
          R_3 ≤^+(1/2-α_0+P/(α_0+α_2) P+N_3)

where log^+(·)=max{0,log(·)}. And, 
    ℛ=conv(⋃_αℛ_α)
 is achievable where conv(·) is convex hull operator.




 §.§ Preliminaries: Lattice Coding

Lattice Λ is a discrete subgroup of ℝ^n, Λ ={𝐭=𝐆𝐮: 𝐮∈ℤ^n} where 𝐆∈ℝ^n× n is a real generator matrix. Quantization with respect to Λ is Q_Λ(𝐱)=min_λ∈Λ𝐱-λ. Modulo operation with respect to Λ is M_Λ(𝐱)=[𝐱]=𝐱-Q_Λ(𝐱). For convenience, we use both notations M_Λ(·) and [·] interchangeably. Fundamental Voronoi region of Λ is 𝒱(Λ)={𝐱:Q_Λ(𝐱)=0}. Volume of the Voronoi region of Λ is V(Λ)=∫_𝒱(Λ) d𝐱. Normalized second moment of Λ is G(Λ)=σ^2(Λ)/V(Λ)^2/n where σ^2(Λ)=1/nV(Λ)∫_𝒱(Λ)𝐱^2 d𝐱. Lattices Λ_1, Λ_2 and Λ are said to be nested if Λ⊆Λ_2⊆Λ_1. For nested lattices Λ_2⊂Λ_1,
Λ_1/Λ_2=Λ_1∩𝒱(Λ_2).

We briefly review the lattice decoding procedure in <cit.>. We use nested lattices Λ⊆Λ_t with σ^2(Λ)=S, G(Λ)=1/2π e, and V(Λ)=(2π e S)^n/2. The transmitter sends 𝐱=[𝐭+𝐝] over the point-to-point Gaussian channel 𝐲=𝐱+𝐳 where the codeword 𝐭∈Λ_t∩𝒱(Λ), the dither signal 𝐝∼Unif(𝒱(Λ)), the transmit power 1/n𝐱^2=S and the noise 𝐳∼𝒩(0,N𝐈). The code rate is given by R=1/nlog(V(Λ)/V(Λ_t)).

After linear scaling, dither removal, and mod-Λ operation, we get

    𝐲'=[β𝐲-𝐝] = [𝐭+𝐳_e]

where the effective noise is 𝐳_e=(β-1)𝐱+β𝐳_1
and its variance
σ_e^2=1/n𝔼[𝐳_e^2]=(β-1)^2 S+β^2 N.
With the MMSE scaling factor β=S/S+N plugged in, we get σ_e^2=β N=SN/S+N. The capacity of the mod-Λ channel <cit.> between 𝐭 and 𝐲 is

    1/n I(𝐭;𝐲)
       =   1/n h(𝐲)-1/n h(𝐲|𝐭)
       =   1/n h(𝐲)-1/n h(𝐳)
       ≥   1/n h(𝐲)-1/n h(𝐳)
       =   1/nlog V(Λ)-1/n h(𝐳)
       =   1/2log(S/β N)
       =   1/2log(1+S/N)
       =    C

where I(·) and h(·) are mutual information and differential entropy, respectively. For reliable decoding of 𝐭, we have the code rate constraint R≤ C.
With the choice of lattice parameters, σ^2(Λ_t)≥β N, G(Λ_t)=1/2π e and V(Λ_t)^n/2=σ^2(Λ_t)/G(Λ_t)≥ 2π e β N,

    R    =   1/nlog(V(Λ)/V(Λ_t))
       ≤   1/nlog((2π e S)^n/2/(2π e β N)^n/2)
       =   1/2log(S/β N).

Thus, the constraint R≤ C can be satisfied. By lattice decoding <cit.>, we can recover 𝐭, i.e.,

    Q_Λ_t(𝐲')=𝐭,

with probability 1-P_e where

    P_e=Pr[Q_Λ_t(𝐲')≠𝐭]

is the probability of decoding error.
If we choose Λ to be Poltyrev-good <cit.>, then P_e→ 0 as n→∞.




 §.§ Achievable Scheme

We present an achievable scheme for the proof of Theorem 8. The achievable scheme is based on rate-splitting, lattice coding, and interference alignment. Message M_1∈{1,2,…,2^nR_1} is split into two parts: M_11∈{1,2,…,2^nR_11} and M_10∈{1,2,…,2^nR_10}, so R_1=R_11+R_10. Transmitter 1 sends 𝐱_1=𝐱_11+𝐱_10 where 𝐱_11 and 𝐱_10 are coded signals of M_11 and M_10, respectively. Transmitters 2 and 3 send 𝐱_2 and 𝐱_3, coded signals of M_2∈{1,2,…,2^nR_2} and M_3∈{1,2,…,2^nR_3}. In particular, 𝐱_11 and 𝐱_3 are lattice-coded signals.

We use the lattice construction of <cit.> with the lattice partition chain Λ_c/Λ_1/Λ_3, so Λ_3⊂Λ_1⊂Λ_c are nested lattices. Λ_c is the coding lattice for both 𝐱_11 and 𝐱_3. Λ_1 and Λ_3 are shaping lattices for 𝐱_11 and 𝐱_3, respectively.  The lattice signals are formed by

    𝐱_11=[𝐭_11+𝐝_11]_1
           𝐱_3=[𝐭_3+𝐝_3]_3

where 𝐭_11∈Λ_c∩𝒱(Λ_1) and 𝐭_3∈Λ_c∩𝒱(Λ_3) are lattice codewords. The dither signals 𝐝_11 and 𝐝_3 are uniformly distributed over 𝒱(Λ_1) and 𝒱(Λ_3), respectively.
To satisfy power constraints, we choose 𝔼[𝐱_11^2]=nσ^2(Λ_1)=(1-α_1) nP, 𝔼[𝐱_10^2]=α_1 nP,
𝔼[𝐱_2^2]=α_2 nP, 𝔼[𝐱_3^2]=nσ^2(Λ_3)=nP.

With the choice of transmit signals, the received signals are given by

    𝐲_1=𝐱_11+𝐱_2+𝐱_10+𝐳_1
          𝐲_2=[𝐱_11+𝐱_3]+𝐱_2+𝐳_2'
          𝐲_3=𝐱_3+𝐳_3'.

where 𝐱_f=[𝐱_11+𝐱_3] is the sum of interference, and 𝐳_2'=𝐱_10+𝐳_2 and 𝐳_3'=𝐱_2+𝐳_3 are the effective Gaussian noise.
The signal scale diagram at each receiver is shown in Fig. <ref> (a).

At the receivers, successive decoding is performed in the following order: 𝐱_11→𝐱_2→𝐱_10 at receiver 1, 𝐱_f→𝐱_2 at receiver 2, and receiver 3 only decodes 𝐱_3.

Note that the aligned lattice codewords 𝐭_11+𝐭_3∈Λ_c, and 𝐭_f=[𝐭_11+𝐭_3]_1 ∈Λ_c∩𝒱(Λ_1). We state the relationship between 𝐱_f and 𝐭_f in the following lemmas.
 The following holds.

    [𝐱_f-𝐝_f]_1=𝐭_f

where 𝐝_f=𝐝_11+𝐝_3.



    [𝐱_f-𝐝_f]_1
          =[M_Λ_1(𝐭_11+𝐝_11)+M_Λ_3(𝐭_3+𝐝_3)-𝐝_f]_1
          =[M_Λ_1(𝐭_11+𝐝_11)+M_Λ_1(𝐭_3+𝐝_3)-𝐝_f]_1
          =[𝐭_11+𝐝_11+𝐭_3+𝐝_3-𝐝_f]_1
          =[𝐭_11+𝐭_3]_1
          =𝐭_f

The second and third equalities are due to distributive law and the identity in the following lemma.




 For any nested lattices Λ_3⊂Λ_1 and
 any 𝐱∈ℝ^n, it holds that

    [M_Λ_3(𝐱)]_1=[𝐱]_1.




    [M_Λ_3(𝐱)]_1
          =[𝐱-λ_3]_1
          =[M_Λ_1(𝐱)-M_Λ_1(λ_3)]_1
          =[M_Λ_1(𝐱)-λ_3 +Q_Λ_1(λ_3)]_1
          =[M_Λ_1(𝐱)]_1
          =[𝐱]_1

where λ_3=Q_Λ_3(𝐱)∈Λ_1, thus Q_Λ_1(λ_3)=λ_3.


 The following holds.

    [𝐭_f+𝐝_f]_1=[𝐱_f]_1.




    [𝐭_f+𝐝_f]_1
          =[M_Λ_1(𝐭_11+𝐭_3)+𝐝_f]_1
          =[𝐭_11+𝐭_3+𝐝_f]_1
          =[M_Λ_1(𝐭_11+𝐝_11)+M_Λ_1(𝐭_3+𝐝_3)]_1
          =[M_Λ_1(𝐭_11+𝐝_11)+M_Λ_3(𝐭_3+𝐝_3)]_1
          =[𝐱_11+𝐱_3]_1
          =[𝐱_f]_1



Receiver 2 does not need to recover the codewords 𝐭_11 and 𝐭_3 but the real sum 𝐱_f to remove the interference from 𝐲_2. Since 𝐱_f=M_Λ_1(𝐱_f)+Q_Λ_1(𝐱_f), we first recover the modulo part and then the quantized part to cancel out 𝐱_f. This idea appeared in <cit.> as an achievable scheme for the many-to-one interference channel.

The mod-Λ_1 channel between 𝐭_f and 𝐲_2' is given by

    𝐲_2'=[β_2𝐲_2-𝐝_f]_1
              = [𝐱_f-𝐝_f +𝐳_e2]_1
              = [𝐭_f +𝐳_e2]_1

where the effective noise 𝐳_e2=(β_2-1)𝐱_f+β_2(𝐱_2+𝐱_10+𝐳_2). Note that 𝔼[𝐱_f^2]=(α̅_0+1)nP, and the effective noise variance σ_e2^2=1/n𝔼[𝐳_e2^2]=(β_2-1)^2(α̅_0+1)P+β_2^2 N_e2 where N_e2=(α_0+α_2) P+N_2. With the MMSE scaling factor β_2=(α̅_0+1)P/(α̅_0+1)P+N_e2 plugged in, we get σ_e2^2=β_2 N_e2=(α̅_0+1)P N_e2/(α̅_0+1)P+N_e2. The capacity of the mod-Λ_1 channel between 𝐭_f and 𝐲_2' is

    1/n I(𝐭_f;𝐲_2')
          ≥1/nlog(V(Λ_1)/2^h(𝐳_e2))
          = 1/2log(α̅_0 P/β_2 N_e2)
          = 1/2log(α̅_0(α̅_0+1)P+α̅_0 N_e2/(α̅_0+1)N_e2)
          = 1/2log(α̅_0/α̅_0+1+α̅_0 P/N_e2)
          = 1/2log(α̅_0/α̅_0+1+α̅_0 P/(α_0+α_2) P+N_2)
          = C_f


For reliable decoding of 𝐭_f at receiver 2, we have the code rate constraint R_11=1/nlog(V(Λ_1)/V(Λ_c))≤ C_f. This also implies that R_3=1/nlog(V(Λ_2)/V(Λ_c))≤ C_f+1/nlog(V(Λ_2)/V(Λ_1))=1/2log(P/β_2 N_e2)=1/2log(1/α̅_0+1+P/(α_0+α_2) P+N_2).
By lattice decoding, we can recover the modulo sum of interference codewords 𝐭_f from 𝐲_2'. Then, we can recover the real sum 𝐱_f in the following way.


  * Recover M_Λ_1(𝐱_f) by calculating [𝐭_f+𝐝_f]_1 (lemma 3).

  * Subtract it from the received signal,

    𝐲_2-M_Λ_1(𝐱_f)=Q_Λ_1(𝐱_f) +𝐳_2”

where 𝐳_2”=𝐱_2+𝐱_10+𝐳_2.

  * Quantize it to recover Q_Λ_1(𝐱_f),

    Q_Λ_1(Q_Λ_1(𝐱_f) +𝐳_2”)=Q_Λ_1(𝐱_f)

with probability 1-P_e where

    P_e=Pr[Q_Λ_1(Q_Λ_1(𝐱_f) +𝐳_2”)≠ Q_Λ_1(𝐱_f)]

is the probability of decoding error.
If we choose Λ_1 to be simultaneously Rogers-good and Poltyrev-good <cit.> with V(Λ_1)≥ V(Λ_c), then P_e→ 0 as n→∞.

  * Recover 𝐱_f by adding two vectors,

    M_Λ_1(𝐱_f)+Q_Λ_1(𝐱_f)=𝐱_f.


We now proceed to decoding 𝐱_2 from 𝐲_2-𝐱_f=𝐱_2+𝐳_2'. Since 𝐱_2 is a codeword from an i.i.d. random code for point-to-point channel, we can achieve rate up to

    R_2≤(α_2 P/α_0 P+N_2).


At receiver 1, we first decode 𝐱_11 while treating other signals 𝐱_2+𝐱_10+𝐳_1 as noise. The effective noise in the mod-Λ_1 channel is 𝐳_e1=(β_1-1)^2𝐱_11+β_1(𝐱_2+𝐱_10+𝐳_1) with variance σ_e1^2=1/n𝔼[𝐳_e1^2]=(β_1-1)^2 α̅_0 P+β_1^2 N_e1 where N_e1=(α_0+α_2)P+N_1. For reliable decoding, the rate R_11 must satisfy

    R_11≤(σ^2(Λ_1)/β_1σ_e1^2)=(1+α̅_0 P/(α_0+α_2) P+N_1)

where the MMSE scaling parameter β_1=α̅_0 P/α̅_0 P+N_e1. Similarly, we have the other rate constraints at receiver 1:

    R_2≤(1+α_2 P/α_0 P +N_1)
           R_10≤(1+α_0 P/N_1).


At receiver 3, the signal 𝐱_3 is decoded with the effective noise 𝐱_2+𝐳_3. For reliable decoding, R_3 must satisfy

    R_3≤(1+P/α_2 P+N_3).


In summary,


  * 𝐱_11 decoded at receivers 1 and 2

    R_11≤ T_11'=(1+(1-α_0) P/(α_0+α_2) P+N_1)
           R_11≤ T_11”=(c_11+(1-α_0) P/(α_0+α_2) P+N_2)

where c_11=(1-α_0)P/(1-α_0)P+P=1-α_0/2-α_0.

  * 𝐱_10 decoded at receiver 1

    R_10≤ T_10=(1+α_0 P/N_1)


  * 𝐱_2 decoded at receivers 1 and 2

    R_2≤ T_2' =(1+α_2 P/α_0 P +N_1)
           R_2≤ T_2” =(1+α_2 P/α_0 P +N_2)


  * 𝐱_3 decoded at receivers 2 and 3

    R_3≤ T_3' =(c_3+P/(α_0+α_2) P+N_2)
           R_3≤ T_3” =(1+P/α_2 P+N_3)

where c_3=P/(1-α_0)P+P=1/2-α_0.

Note that 0≤ c_11≤1/2, c_11+c_3=1, and 1/2≤ c_3≤ 1. Putting together, we can see that the following rate region is achievable.

    R_1 ≤ T_1=min{T_11',T_11”}+T_10=T_11”+T_10
           R_2 ≤ T_2=min{T_2',T_2”}=T_2”
           R_3 ≤ T_3=min{T_3',T_3”}

where

    T_1=(c_11+(1-α_0) P/(α_0+α_2) P+N_2)
                                        +(1+α_0 P/N_1)
           T_2=(1+α_2 P/α_0 P +N_2)
           T_3 ≥(c_3+P/(α_0+α_2) P+N_3).

Thus, Theorem 8 is proved.



 §.§ The Gap


We choose the parameter α_0=N_2/P, which is suboptimal but good enough to achieve a constant gap. This choice of parameter, inspired by <cit.>, ensures making efficient use of signal scale difference between N_1 and N_2 at receiver 1, while keeping the interference of 𝐱_10 at the noise level N_2 at receiver 2. By substitution, we get

    T_1 = (c_11+P-N_2/α_2 P+2N_2)
                                        +(1+N_2/N_1)
          T_2 = (1+α_2 P/2 N_2)
          T_3 ≥(c_3+P/α_2 P+N_2+N_3).

Since α_0=N_2/P∈[0,1/3], it follows that c_11=1-N_2/P/2-N_2/P≥2/5, and c_3=1/2-N_2/P≥1/2.

Starting from ℛ_o from Table <ref>, we can express the two-dimensional outer bound region at R_2 as

    R_1 ≤min{(1+2P/N_1)-R_2,C_1}
              ≤min{(P/N_1·7/3)-R_2,(P/N_1·4/3)}
           R_3 ≤min{(1+2P/N_2)-R_2,C_3}
              ≤min{(P/N_2·7/3)-R_2,(P/N_3·4/3)}.

Depending on the bottleneck of min{·,·} expressions, there are three cases:


  * R_2≤(7/4)

  * (7/4)≤ R_2≤(N_3/N_2·7/4)

  * R_2≥(N_3/N_2·7/4).

At R_2=(α_2 P/N_2·7/4), the outer bound region is

    R_1 ≤min{(P/α_2 P·N_2/N_1·4/3),(P/N_1·4/3)}
           R_3 ≤min{(P/α_2 P·4/3),(P/N_3·4/3)}.

Depending on the bottleneck of min{·,·} expressions, we consider the following three cases:


  * α_2 P≥ N_3

  * N_2≤α_2 P≤ N_3

  * α_2 P≤ N_2.


Case i) α_2 P≥ N_3:
The outer bound region at R_2=(α_2 P/N_2·7/4) is

    R_1 ≤(P/α_2 P·N_2/N_1·4/3), R_3 ≤(P/α_2 P·4/3).


For comparison, let us take a look at the achievable rate region. The first term of T_1 is lower bounded by

    T_11” =(c_11+P-N_2/α_2 P+2N_2)
               ≥(2/5+P-α_2 P/3α_2 P)
               > (P/3α_2 P).

We get the lower bounds:

    T_1 = T_11”+T_10
              > (P/3α_2 P)+(1+N_2/N_1)
              > (P/3α_2 P·N_2/N_1)
          T_3≥(1/2+P/α_2 P+N_2+N_3)
              > (P/3α_2 P).

For fixed α_2 and R_2=(α_2 P/2N_2), the two-dimensional achievable rate region is given by

    R_1 ≤(P/3α_2 P·N_2/N_1), R_3 ≤(P/3α_2 P).


Case ii) N_2≤α_2 P≤ N_3:
The outer bound region at R_2=(α_2 P/N_2·7/4) is

    R_1 ≤(P/α_2 P·N_2/N_1·4/3), R_3 ≤(P/N_3·4/3).


Now, let us take a look at the achievable rate region. We have the lower bounds:

    T_1 > (P/3α_2 P·N_2/N_1)
           T_3 ≥(1/2+P/α_2 P+N_2+N_3)
              > (P/3N_3).

For fixed α_2 and R_2=(α_2 P/2N_2), the two-dimensional achievable rate region is given by

    R_1≤(P/3α_2 P·N_2/N_1), R_3≤(P/3N_3).


Case iii) α_2 P≤ N_2:
The outer bound region at R_2=(α_2 P/N_2·7/4) is

    R_1 ≤(P/N_1·4/3), R_3 ≤(P/N_3·4/3).

For this range of α_2, the rate R_2 is small, i.e., R_2 = (α_2 P/N_2·7/4)≤(7/4)<1/2, and R_1 and R_3 are close to single user capacities C_1 and C_3, respectively.

Let us take a look at the achievable rate region.
The first term of T_1 is lower bounded by

    T_11” =(c_11+P-N_2/α_2 P+2N_2)
               ≥(2/5+P-N_2/3N_2)
               > (P/3N_2).

We get the lower bounds:

    T_1 = T_11”+T_10
              > (P/3N_2)+(1+N_2/N_1)
              > (P/3N_1)
           T_3 ≥(1/2+P/α_2 P+N_2+N_3)
              > (P/3N_3).

For fixed α_2 and R_2=(α_2 P/2N_2), the following two-dimensional rate region is achievable.

    R_1 ≤(P/3N_1), R_3 ≤(P/3N_3).


In all three cases above, by comparing the inner and outer bound regions, we can see that δ_1≤(3·4/3)=1, δ_2≤(2·7/4) = 0.91 and δ_3≤(3·4/3)=1. Therefore, we can conclude that the gap is to within one bit per message.




§ INNER BOUND: CHANNEL TYPE 2


Given α_1∈ [0,1], the region ℛ_α is defined by

    R_1 ≤(1+α_1 P/N_1)
          R_2 ≤^+(1/2+P/α_1 P+N_2)
          R_3 ≤^+(1/2+P/α_1 P+N_3),

and ℛ=conv(⋃_α_1ℛ_α) is achievable.




 §.§ Achievable Scheme

For this channel type, rate splitting is not necessary. Transmit signal 𝐱_k is a coded signal of M_k∈{1,2,…,2^nR_k},k=1,2,3. In particular, 𝐱_2 and 𝐱_3 are lattice-coded signals using the same pair of coding and shaping lattices. As a result, the sum 𝐱_2+𝐱_3 is a dithered lattice codeword. The power allocation satisfies
𝔼[𝐱_1^2]=α_1 nP, 𝔼[𝐱_2^2]=nP, and 𝔼[𝐱_3^2]=nP.
The received signals are

    𝐲_1=[𝐱_2+𝐱_3]+𝐱_1+𝐳_1
          𝐲_2=𝐱_2+𝐱_1+𝐳_2
          𝐲_3=𝐱_3+𝐱_1+𝐳_3.

The signal scale diagram at each receiver is shown in Fig. <ref> (b).
Decoding is performed in the following way.


  * At receiver 1, [𝐱_2+𝐱_3] is first decoded while treating 𝐱_1+𝐳_1 as noise. Next, 𝐱_1 is decoded from 𝐲_1-[𝐱_2+𝐱_3]=𝐱_1+𝐳_1. For reliable decoding, the code rates should satisfy

    R_2 ≤ T_2' =(1/2+P/α_1 P+N_1)
           R_3 ≤ T_3' =(1/2+P/α_1 P+N_1)
           R_1 ≤ T_1 =(1+α_1 P/N_1).


  * At receiver 2, 𝐱_2 is decoded while treating 𝐱_1+𝐳_2 as noise. Similarly at receiver 3, 𝐱_3 is decoded while treating 𝐱_1+𝐳_3 as noise. For reliable decoding, the code rates should satisfy

    R_2≤ T_2” =(1+P/α_1 P+N_2)
          R_3≤ T_3” =(1+P/α_1 P+N_3).


Putting together, we get

    R_1 ≤ T_1
           R_2 ≤ T_2 =min{T_2',T_2”}
           R_3 ≤ T_3 =min{T_3',T_3”}

where

    T_1 =(1+α_1 P/N_1)
           T_2 ≥(1/2+P/α_1 P+N_2)
              ≥(1/2+P/2·max{α_1 P,N_2})
           T_3 ≥(1/2+P/α_1 P+N_3)
              ≥(1/2+P/2·max{α_1 P,N_3}).




 §.§ The Gap

Starting from ℛ_o from Table <ref>, we can express the two-dimensional outer bound region at R_1 as

    R_2 ≤min{(1+2P/N_1)-R_1,C_2}
              ≤min{(P/N_1·7/3)-R_1,(P/N_2·4/3)}
           R_3 ≤min{(1+2P/N_1)-R_1,C_3}
              ≤min{(P/N_1·7/3)-R_1,(P/N_3·4/3)}.

Depending on the bottleneck of min{·,·} expressions, there are three cases:


  * R_1≤(N_2/N_1·7/4)

  * (N_2/N_1·7/4)≤ R_1≤(N_3/N_1·7/4)

  * R_1≥(N_3/N_1·7/4).

At R_1=(α_1 P/N_1·7/4), the region can be expressed as

    R_2 ≤min{(P/α_1 P·4/3),(P/N_2·4/3)}
           R_3 ≤min{(P/α_1 P·4/3),(P/N_3·4/3)}.

Depending on the bottleneck of min{·,·} expressions, we consider the following three cases.

Case i) α_1 P≥ N_3: The two-dimensional outer bound region at R_1=(α_1 P/N_1·7/4) is

    R_2 ≤(P/α_1 P·4/3), R_3 ≤(P/α_1 P·4/3).







For fixed α_1 and R_1=(α_1 P/N_1), the following two-dimensional region is achievable.

    R_2 ≤(P/2α_1 P), R_3 ≤(P/2α_1 P).


Case ii) N_2≤α_1 P≤ N_3: The two-dimensional outer bound region at R_1=(α_1 P/N_1·7/4) is

    R_2 ≤(P/α_1 P·4/3), R_3 ≤(P/N_3·4/3).







For fixed α_1 and R_1=(α_1 P/N_1), the following two-dimensional region is achievable.

    R_2 ≤(P/2α_1 P), R_3 ≤(P/2N_3).


Case iii) α_1 P≤ N_2: The two-dimensional outer bound region at R_1=(α_1 P/N_1·7/4) is

    R_2 ≤(P/N_2·4/3), R_3 ≤(P/N_3·4/3).







For fixed α_1 and R_1=(α_1 P/N_1), the following two-dimensional region is achievable.

    R_2 ≤(P/2N_2), R_3 ≤(P/2N_3).


In all three cases above, by comparing the inner and outer bounds, we can see that δ_1≤(7/4)<0.41, δ_2 ≤(2·4/3)<0.71, and δ_3 ≤(2·4/3)<0.71. We can conclude that the inner and outer bounds are to within one bit.




§ INNER BOUND: CHANNEL TYPE 3


Given α∈ [0,1], the region ℛ_α is defined by

    R_1 ≤(1+α P/N_1)
          R_2 ≤(1+α P/N_2)
          R_3 ≤(1+P/2α P+N_3),

and ℛ=conv(⋃_αℛ_α) is achievable.



 §.§ Achievable Scheme

For this channel type, neither rate splitting nor aligned interference decoding is necessary.
Transmit signal 𝐱_k is a coded signal of M_k∈{1,2,…,2^nR_k},k=1,2,3. The power allocation satisfies 𝔼[𝐱_1^2]=α nP, 𝔼[𝐱_2^2]=α nP, and 𝔼[𝐱_3^2]=nP.
The received signals are

    𝐲_1=𝐱_3+𝐱_1+𝐳_1
          𝐲_2=𝐱_3+𝐱_2+𝐳_2
          𝐲_3=𝐱_3+𝐱_1+𝐱_2+𝐳_3.

The signal scale diagram at each receiver is shown in Fig. <ref> (c). Decoding is performed in the following way.


  * At receiver 1, 𝐱_3 is first decoded while treating 𝐱_1+𝐳_1 as noise. Next, 𝐱_1 is decoded from 𝐲_1-𝐱_3=𝐱_1+𝐳_1. For reliable decoding, the code rates should satisfy

    R_3 ≤ T_3' =(1+P/α P+N_1)
           R_1 ≤ T_1 =(1+α P/N_1).


  * At receiver 2, 𝐱_3 is first decoded while treating 𝐱_2+𝐳_2 as noise. Next, 𝐱_2 is decoded from 𝐲_2-𝐱_3=𝐱_2+𝐳_2. For reliable decoding, the code rates should satisfy

    R_3 ≤ T_3” =(1+P/α P+N_2)
           R_2 ≤ T_2 =(1+α P/N_2).


  * At receiver 3, 𝐱_3 is decoded while treating 𝐱_1+𝐱_2+𝐳_3 as noise. For reliable decoding, the code rates should satisfy

    R_3≤ T_3”' =(1+P/2α P+N_3).


Putting together, we get

    R_1 ≤ T_1
           R_2 ≤ T_2
           R_3 ≤ T_3 =min{T_3',T_3”,T_3”'}

where

    T_1 =(1+α P/N_1)
           T_2 =(1+α P/N_2)
           T_3 =(1+P/2α P+N_3)
              ≥(1+P/3·max{α P,N_3}).




 §.§ The Gap

Starting from ℛ_o from Table <ref>, we can express the two-dimensional outer bound region at R_3 as

    R_1 ≤min{(1+2P/N_1)-R_3,C_1}
              ≤min{(P/N_1·7/3)-R_3,(P/N_1·4/3)}
           R_2 ≤min{(1+2P/N_2)-R_3,C_2}
              ≤min{(P/N_2·7/3)-R_3,(P/N_2·4/3)}.

Depending on the bottleneck of min{·,·} expressions, there are two cases:
R_3≤(7/4) and R_3≥(7/4).
We assume that R_3≥(7/4), equivalently α≤4/7. We also assume that R_3≤(P/N_3), equivalently α P≥ N_3. The other cases are trivial.

The two-dimensional outer bound region at R_3=(P/α P) is

    R_1 ≤min{(α P/N_1·7/3),(P/N_1·4/3)}
           R_2 ≤min{(α P/N_2·7/3),(P/N_2·4/3)}.

For α≤4/7, the two-dimensional outer bound region is

    R_1 ≤(α P/N_1·7/3), R_2 ≤(α P/N_2·7/3).









For α P≥ N_3, the two-dimensional achievable rate region at R_3=(P/3α P) is

    R_1 ≤(α P/N_1), R_2 ≤(α P/N_2).

By comparing the inner and outer bounds, we can see that δ_1≤(7/3)<0.62, δ_2 ≤(7/3)<0.62, and δ_3 ≤(3)<0.8. We can conclude that the inner and outer bounds are to within one bit.






§ INNER BOUND: CHANNEL TYPE 4

The relaxed outer bound region ℛ_o' given by

    R_k ≤(P/N_k)+(4/3), k=1,2,3
           R_1+R_2 ≤(P/N_1)+(7/3)
           R_1+R_3 ≤(P/N_1)+(7/3)
           R_2+R_3 ≤(P/N_2)+(7/3).

The cross-sectional region at a given R_1 is described by

    R_2≤min{(P/N_1·7/3)-R_1,(P/N_2·4/3)}
           R_3≤min{(P/N_1·7/3)-R_1,(P/N_3·4/3)}
           R_2+R_3 ≤(P/N_2·7/3).

Depending on the bottleneck of min{·,·} expressions, there are three cases:


  * R_1≤(N_2/N_1·7/4)

  * (N_2/N_1·7/4)≤ R_1≤(N_3/N_1·7/4)

  * R_1≥(N_3/N_1·7/4).

In this section, we focus on the third case. The other cases can be proved similarly.
If the sum of the righthand sides of R_2 and R_3 bounds is smaller than the righthand side of R_2+R_3 bound, i.e.,

    log(P/N_1·7/3)-2R_1≤(P/N_2·7/3),

then the R_2+R_3 bound is not active at the R_1.
This condition can be expressed as a threshold on R_1 given by

    R_1 > R_1,th= 1/2log(P/N_1·7/3)-1/4log(P/N_2·7/3)
                        = 1/4log(P/N_1·7/3)+1/4log(N_2/N_1).

For this relatively large R_1, the cross-sectional region is a rectangle as described in Fig. <ref> (a). In contrast, for a relatively small R_1, when the threshold condition does not hold, the cross-sectional region is a MAC-like region as described in Fig. <ref> (b). In the rest of the section, we present achievable schemes for each case.




 §.§ Achievable Scheme for Relatively Large R_1




Given α=(α_0,α_1,α_2) ∈ [0,1]^3, the region ℛ_α is defined by

    R_1 ≤min{^+(c_11+(1-α_0-α_1-α_2)P/(α_0+α_1+2α_2)P+N_2),.
                                         .(1+α_2 P/α_0 P+N_1)}
                  +(1+α_1 P/(α_0+α_2) P+N_2)
                  +(1+α_0 P/N_1)
           R_2 ≤(1+α_2 P/α_0 P+N_2)
           R_3 ≤^+(c_3+P/(α_0+α_1+α_2) P+N_3)

where c_11=1-α_0-α_1-α_2/2-α_0-α_1-α_2 and c_3=1/2-α_0-α_1-α_2,
and ℛ=conv(⋃_αℛ_α) is achievable.


We present an achievable scheme for the case of R_1 > R_1,th. Message M_1∈{1,2,…,2^nR_1} is split into three parts: M_10∈{1,2,…,2^nR_10}, M_11∈{1,2,…,2^nR_11} and M_12∈{1,2,…,2^nR_12}, so R_1=R_10+R_11+R_12. We generate the signals in the following way: 𝐱_11 and 𝐱_11' are differently coded signals of M_11, and 𝐱_10 and 𝐱_12 are coded signal of M_10 and M_12, respectively. The transmit signal is the sum

    𝐱_1=𝐱_10+𝐱_11+𝐱_12+𝐱_11'.
 The power allocation satisfies 𝔼[𝐱_10^2]=α_0 nP, 𝔼[𝐱_11^2]=α_2 nP, 𝔼[𝐱_12^2]=α_1 nP, and 𝔼[𝐱_11'^2]=(1-α_0-α_1-α_2) nP.

The transmit signals 𝐱_2 and 𝐱_3 are coded signals of the messages M_2∈{1,2,…,2^nR_2} and M_3∈{1,2,…,2^nR_3}, satisfying 𝔼[𝐱_2^2]=α_2 nP and 𝔼[𝐱_3^2]=nP.

The signals 𝐱_11' and 𝐱_3 are lattice-coded signals using the same coding lattice but different shaping lattices. As a result, the sum 𝐱_11'+𝐱_3 is a dithered lattice codeword.

The received signals are

    𝐲_1=[𝐱_11'+𝐱_3]+𝐱_12+𝐱_11+𝐱_10+𝐳_1
          𝐲_2=𝐱_11'+𝐱_12+𝐱_11+𝐱_2+𝐱_10+𝐳_2
          𝐲_3=𝐱_3+𝐱_2+𝐳_3.

The signal scale diagram at each receiver is shown in Fig. <ref> (a).
Decoding is performed in the following way.


  * At receiver 1, [𝐱_11'+𝐱_3] is first decoded while treating other signals as noise and removed from 𝐲_1. Next, 𝐱_12, 𝐱_11, and 𝐱_10 are decoded successively. For reliable decoding, the code rates should satisfy

    R_11≤ T_11' =(c_11+(1-α_0-α_1-α_2)P/(α_0+α_1+α_2)P+N_1)
          R_3 ≤ T_3' =(c_3+P/(α_0+α_1+α_2)P+N_1)
          R_12≤ T_12' =(1+α_1 P/(α_0+α_2) P+N_1)
          R_11≤ T_11” =(1+α_2 P/α_0 P+N_1)
          R_10≤ T_10 =(1+α_0 P/N_1)

where c_11=(1-α_0-α_1-α_2)P/(1-α_0-α_1-α_2)P+P=1-α_0-α_1-α_2/2-α_0-α_1-α_2 and c_3=P/(1-α_0-α_1-α_2)P+P=1/2-α_0-α_1-α_2. Note that 0≤ c_11≤1/2, c_11+c_3=1, and 1/2≤ c_3≤ 1.

  * At receiver 2, 𝐱_11' is first decoded while treating other signals as noise. Having successfully recovered M_11, receiver 2 can generate 𝐱_11 and 𝐱_11', and cancel them from 𝐲_2. Next, 𝐱_12 is decoded from 𝐱_12+𝐱_2+𝐱_10+𝐳_2. Finally, 𝐱_2 is decoded from 𝐱_2+𝐱_10+𝐳_2. For reliable decoding, the code rates should satisfy

    R_11≤ T_11”' =(1+(1-α_0-α_1-α_2)P/(α_0+α_1+2α_2)P+N_2)
           R_12≤ T_12” =(1+α_1 P/(α_0+α_2)P+N_2)
           R_2 ≤ T_2 =(1+α_2 P/α_0 P+N_2).


  * At receiver 3, 𝐱_3 is decoded while treating 𝐱_2+𝐳_3 as noise. Reliable decoding is possible if

    R_3 ≤ T_3” =(1+P/α_2 P+N_3).


Putting together, we can see that given α_0,α_1,α_2∈[0,1], the following rate region is achievable.

    R_1 ≤ T_1=min{T_11',T_11”,T_11”'}+min{T_12',T_12”}+T_10
           R_2 ≤ T_2
           R_3 ≤ T_3=min{T_3',T_3”}

where

    T_1 = min{T_11',T_11”,T_11”'}+min{T_12',T_12”}+T_10
              = min{min{T_11',T_11”'},T_11”}+T_12”+T_10
              ≥min{(c_11+(1-α_0-α_1-α_2)P/(α_0+α_1+2α_2)P+N_2),.
                                         .(1+α_2 P/α_0 P+N_1)}
                  +(1+α_1 P/(α_0+α_2) P+N_2)
                  +(1+α_0 P/N_1)
           T_2 =(1+α_2 P/α_0 P+N_2)
           T_3 ≥(c_3+P/(α_0+α_1+α_2) P+N_3).




 §.§ The Gap for Relatively Large R_1

We choose α_0, α_1 and α_2 such that α_1≤3/8, that  α_1≥ 3(α_0+α_2), that α_2 P≥ 3N_3, and that α_0 P=N_2. It follows that α_0+α_1+α_2≤4/3α_1≤1/2, that c_11≥1/3, and that (α_0+α_1+2α_2)P+N_2 = 2(α_0+α_2)P+α_1 P≤5/3α_1 P. We get the lower bounds for each term of T_1 expression above.

    min{T_11',T_11”'}
          ≥(c_11+(1-α_0-α_1-α_2)P/(α_0+α_1+2α_2)P+N_2)
          ≥(1/3+(1-(4/3)α_1)P/(5/3)α_1 P)
          = (P/(5/3)α_1 P-7/15)
          = (P/(5/3)α_1 P)+(1-7/15·5/3α_1)
          ≥(P/(5/3)α_1 P)+(17/24)
          ≥(P/α_1 P·17/40)

and

    T_11”=(1+α_2 P/α_0 P+N_1)
               = ((α_0+α_2) P+N_1/α_0 P+N_1)
               ≥((α_0+α_2) P/α_0 P+N_2)
               =((α_0+α_2) P/2 N_2).

Since (α_0+α_2)P≥ N_2+3N_3≥ 4 N_2,

    T_12” = (1+α_1 P/(α_0+α_2)P+N_2)
               ≥(α_1 P/(5/4)(α_0+α_2)P).

Putting together,

    T_1 ≥min{(P/α_1 P·17/40),((α_0+α_2) P/2 N_2)}
                 +(α_1 P/(5/4)(α_0+α_2) P)+(N_2/N_1)
              = min{(P/(α_0+α_2) P·N_2/N_1·17/40·4/5),.
                                              .(α_1 P/ N_1·1/2·4/5)}
              = min{(P/(α_0+α_2) P·N_2/N_1·17/50),.
                                              .(α_1 P/ N_1·2/5)}.

Given α_1, we choose α_2 that satisfies (P/α_1 P·17/40)=((α_0+α_2) P/2N_2). As a result, we can write T_1≥(α_1 P/ N_1·2/5), and also

    T_2 =(1+α_2 P/α_0 P+N_2)
              ≥((α_0+α_2) P/2 N_2)
              =(P/α_1 P·17/40).

Since N_3≤1/3α_2 P≤1/3(α_0+α_2)P ≤1/9α_1 P,

    T_3 ≥(c_3+P/(α_0+α_1+α_2) P+N_3)
              ≥(1/2+P/(4/3)α_1 P+(1/9)α_1 P)
              ≥(P/(13/9)α_1 P).

The following rate region is achievable.

    R_1≤(α_1 P/N_1·2/5)
           R_2≤(P/α_1 P·17/40)
           R_3≤(P/α_1 P·9/13).

For fixed α_1 and R_1=(α_1 P/N_1·2/5), the two-dimensional rate region, given by

    R_2≤(P/α_1 P·17/40), R_3≤(P/α_1 P·9/13)

is achievable.

In comparison, the two-dimensional outer bound region at R_1=(α_1 P/N_1·2/5)+1, given by

    R_2 ≤(P/N_1·7/3)-(α_1 P/N_1·2/5)-1
              = (P/α_1 P)+(7/3·5/2·1/4)
          R_3 ≤(P/N_1·7/3)-(α_1 P/N_1·2/5)-1
              = (P/α_1 P)+(7/3·5/2·1/4).

As discussed above, the sum-rate bound on R_2+R_3 is loose for R_1 larger than the threshold, so the rate region is a rectangle.
By comparing the inner and outer bound rate regions, we can see that δ_2< (40/17·7/3·5/2·1/4) < 0.89 and δ_3< (13/9·7/3·5/2·1/4) < 0.54. Therefore, we can conclude that the gap is to within one bit per message.



 §.§ Achievable Scheme for Relatively Small R_1


Given α=(α_0,α_1,α_2) ∈ [0,1]^3, the region ℛ_α is defined by

    R_1 ≤min{^+(c_11+(1-α_1)P/(α_1+α_2) P+N_2),.
                 .(1+(α_1-α_0) P/α_0 P+N_1)}+(1+α_0 P/N_1)
           R_2 ≤(1+α_2 P/α_0 P+N_2)
           R_3 ≤^+(c_3+P/max{α_1,α_2} P+N_3)

where c_11=1-α_1/2-α_1 and c_3=1/2-α_1,
and ℛ=conv(⋃_αℛ_α) is achievable.


For the case of R_1 < R_1,th, we present the following achievable scheme. At transmitter 1, we split M_1 into M_10 and M_11, so R_1=R_10+R_11. The transmit signal is the sum

    𝐱_1=𝐱_10+𝐱_11+𝐱_11'.


The power allocation satisfies 𝔼[𝐱_10^2]=α_0 nP, 𝔼[𝐱_11^2]=(α_1-α_0) nP, and 𝔼[𝐱_11'^2]=(1-α_1)nP at receiver 1, 𝔼[𝐱_2^2]=α_2 nP at receiver 2, and 𝔼[𝐱_3^2]=nP at receiver 3.

The signals 𝐱_11' and 𝐱_3 are lattice codewords using the same coding lattice but different shaping lattices. As a result, the sum 𝐱_11'+𝐱_3 is a lattice codeword.

The received signals are

    𝐲_1 = [𝐱_11'+𝐱_3]+𝐱_11+𝐱_10+𝐳_1
          𝐲_2 = 𝐱_11'+𝐱_11+𝐱_2+𝐱_10+𝐳_2
          𝐲_3 = 𝐱_3+𝐱_2+𝐳_3.

The signal scale diagram at each receiver is shown in Fig. <ref> (b).
Decoding is performed in the following way.


  * At receiver 1, [𝐱_11'+𝐱_3] is first decoded while treating other signals as noise and removed from 𝐲_1. Next, 𝐱_11 and then 𝐱_10 is decoded successively. For reliable decoding, the code rates should satisfy

    R_11≤ T_11' =(c_11+(1-α_1)P/α_1 P+N_1)
          R_3 ≤ T_3' =(c_3+P/α_1 P+N_1)
          R_11≤ T_11” =(1+(α_1-α_0) P/α_0 P+N_1)
          R_10≤ T_10 =(1+α_0 P/N_1)

where c_11=(1-α_1)P/(1-α_1)P+P=1-α_1/2-α_1 and c_3=P/(1-α_1)P+P=1/2-α_1. Note that 0≤ c_11≤1/2, c_11+c_3=1, and 1/2≤ c_3≤ 1.

  * At receiver 2, 𝐱_11'
is first decoded while treating other signals as noise. Having successfully recovered M_11, receiver 1 can generate 𝐱_11 and 𝐱_11', and cancel them from 𝐲_2. Next, 𝐱_2 is decoded from 𝐱_2+𝐱_10+𝐳_2. At receiver 2, 𝐱_10 is not decoded. For reliable decoding, the code rates should satisfy

    R_11≤ T_11”' =(1+(1-α_1)P/(α_1+α_2) P+N_2)
           R_2 ≤ T_2 =(1+α_2 P/α_0 P+N_2).


  * At receiver 3, 𝐱_3 is decoded while treating 𝐱_2+𝐳_3 as noise. Reliable decoding is possible if

    R_3 ≤ T_3” =(1+P/α_2 P+N_3).



Putting together, we can see that given α_0,α_1α_2∈[0,1], the following rate region is achievable.

    R_1 ≤ T_1 =min{T_11',T_11”,T_11”'}+T_10
           R_2 ≤ T_2 
           R_3 ≤ T_3 = min{T_3',T_3”}

where

    T_1 = min{T_11',T_11”,T_11”'}+T_10
              = min{min{T_11',T_11”'},T_11”}+T_10
              ≥min{(c_11+(1-α_1)P/(α_1+α_2) P+N_2),.
                 .(1+(α_1-α_0) P/α_0 P+N_1)}+(1+α_0 P/N_1)
           T_2 =(1+α_2 P/α_0 P+N_2)
           T_3 ≥(c_3+P/max{α_1,α_2} P+N_3).






 §.§ The Gap for Relatively Small R_1

We choose α_0, α_1, and α_2 such that α_1 ≤α_2≤1/2, that α_1 P≥ 3N_2, that α_2 P≥ 3N_3, and that α_0 P=4/5 N_2. It follows that c_11≥1/3 and that (α_1+α_2)P+N_2≤4/3α_1 P+α_2P≤7/3α_2 P.

    min{T_11',T_11”'}
          =(c_11+(1-α_1)P/(α_1+α_2)P+N_2)
          ≥(1/3+(1-α_2)P/(7/3)α_2 P)
          =(P/(7/3)α_2 P-2/21)
          =(P/(7/3)α_2 P)+(1-2/21·7/3α_2)
          ≥(P/(7/3)α_2 P)+(8/9)
          ≥(P/α_2 P·8/21)

and

    T_11”=(1+(α_1-α_0) P/α_0 P+N_1)
               = (α_1 P+N_1/α_0 P+N_1)
               ≥(α_1 P/α_0 P+N_2)
               =(α_1 P/(9/5)N_2).

Putting together,

    T_1 ≥min{(P/α_2 P·8/21),(α_1 P/(9/5) N_2) }
                 +(N_2/N_1·4/5).

Let us define α_1' by the equality (P/α_1' P·8/21)=(α_1 P/(9/5) N_2). If we choose α_2≤α_1', then (P/α_2 P·8/21)≥(α_1 P/(9/5) N_2), and

    T_1 ≥(α_1 P/(9/5)N_2·N_2/N_1·4/5)=(α_1 P/N_1·4/9).

We can see that the following rate region is achievable.

    R_1≤(α_1 P/N_1·4/9)
           R_2≤(α_2 P/(9/5)N_2)
           R_3≤(P/(4/3)α_2 P).

For fixed α_2∈ [α_1,α_1'] and R_1=(α_1 P/N_1·4/9), the two-dimensional rate region ℛ_α, given by

    R_2≤(α_2 P/(9/5)N_2)
           R_3≤(P/(4/3)α_2 P)

is achievable. The union ⋃_α_2∈ [α_1,α_1']ℛ_α is a MAC-like region, given by

    R_2≤(α_1' P/(9/5)N_2)
                     ≤(P/α_1 P·8/21)
                 R_3≤(P/α_1 P·3/4)
           R_2+R_3 ≤(α_2 P/(9/5)N_2·P/(4/3)α_2 P)
                     ≤(P/N_2·15/36).

This region is described in Fig. <ref> (a).

In comparison, the two-dimensional outer bound region at R_1=(α_1 P/N_1·4/9)+1, given by

    R_2 ≤(P/N_1·7/3)-(α_1 P/N_1·4/9)-1
                     = (P/α_1 P)+(7/3·9/4·1/4)
                 R_3 ≤(P/N_1·7/3)-(α_1 P/N_1·4/9)-1
                     = (P/α_1 P)+(7/3·9/4·1/4)
          R_2+R_3 ≤(P/N_2)+(7/3).

Since δ_2 < (21/8·7/3·9/4·1/4) < 0.90, δ_3 < (4/3·7/3·9/4·1/4) < 0.41 and δ_23 < (36/15·7/3) < 1.25 < √(2), we can conclude that the gap is to within one bit per message.




§ INNER BOUND: CHANNEL TYPE 5




Let us consider the relaxed outer bound region ℛ_o' given by

    R_k ≤(P/N_k)+(4/3), k=1,2,3
          R_1+R_2 ≤(P/N_1)+(7/3)
          R_2+R_3 ≤(P/N_2)+(7/3)
          R_1+R_3 ≤(P/N_1)+(7/3).

The cross-sectional region at a given R_2 is described by

    R_1≤min{(P/N_1·7/3)-R_2,(P/N_1·4/3)}
           R_3≤min{(P/N_2·7/3)-R_2,(P/N_3·4/3)}
           R_1+R_3 ≤(P/N_1·7/3).

Depending on the bottleneck of min{·,·} expressions, there are three cases:


  * R_2≤(7/4)

  * (7/4)≤ R_2≤(N_3/N_2·7/4)

  * R_2≥(N_3/N_2·7/4).

In this section, we focus on the third case. The other cases can be proved similarly.
If the sum of the righthand sides of R_1 and R_3 bounds is smaller than the righthand side of R_1+R_3 bound, i.e.,

    (P/N_1·7/3)+(P/N_2·7/3)-2R_2 ≤(P/N_1·7/3),

then the R_1+R_3 bound is not active at the R_2.
By rearranging, the threshold condition is given by

    R_2 > R_2,th=1/4log(P/N_2·7/3).

Note that R_2,th is roughly half of C_2.
For this relatively large R_2, the cross-sectional region is a rectangle as described in Fig. <ref> (a). In contrast, for a relatively small R_1, when the threshold condition does not hold, the cross-sectional region is a MAC-like region as described in Fig. <ref> (b). In the following subsections, we present achievable schemes for each case.




 §.§ Achievable Scheme for Relatively Large R_2


Given α=(α_1,α_2,α_2') ∈ [0,1]^3, the region ℛ_α is defined by

    R_1 ≤(1+α_1 P/N_1)
           R_2 ≤min{^+(c_21+(1-α_2-α_2')P/(α_1+α_2+α_2')P+N_2),.
                 .(1+α_2' P/N_2)}+(1+α_2 P/α_2' P+N_2) 
           R_3 ≤^+(c_3+P/max{α_1,α_2+α_2'} P+N_3)

where c_21=1-α_2-α_2'/2-α_2-α_2' and c_3=1/2-α_2-α_2',
and ℛ=conv(⋃_αℛ_α) is achievable.


We present an achievable scheme for the case of R_2 > R_2,th. Message M_2∈{1,2,…,2^nR_2} for receiver 2 is split into two parts: M_21∈{1,2,…,2^nR_21} and M_22∈{1,2,…,2^nR_22}, so R_2=R_21+R_22. We generate the signals in the following way: 𝐱_21 and 𝐱_21' are differently coded signals of M_21, and 𝐱_22 is a coded signal of M_22. The transmit signal is the sum

    𝐱_2=𝐱_21+𝐱_22+𝐱_21'.

The power allocation satisfies 𝔼[𝐱_1^2]=α_1 nP, at receiver 1, 𝔼[𝐱_21^2]=α_2' nP, 𝔼[𝐱_22^2]=α_2 nP, and 𝔼[𝐱_21'^2]=(1-α_2-α_2')P at receiver 2, and 𝔼[𝐱_3^2]=nP at receiver 3.

The signals 𝐱_21' and 𝐱_3 are lattice codewords using the same coding lattice but different shaping lattices. As a result, the sum 𝐱_21'+𝐱_3 is a lattice codeword.

The received signals are

    𝐲_1=𝐱_21'+𝐱_22+𝐱_21+𝐱_1+𝐳_1
          𝐲_2=[𝐱_21'+𝐱_3]+𝐱_22+𝐱_21+𝐳_2
          𝐲_3=𝐱_3+𝐱_1+𝐳_3.

The signal scale diagram at each receiver is shown in Fig. <ref> (a). Decoding is performed in the following way.


  * At receiver 1, 𝐱_21' is first decoded while treating other signals as noise. Having successfully recovered M_21, receiver 1 can generate 𝐱_21 and 𝐱_21', and cancel them from 𝐲_1. Next, 𝐱_22 is decoded from 𝐱_22+𝐱_1+𝐳_1. Finally, 𝐱_1 is decoded from 𝐱_1+𝐳_1. For reliable decoding, the code rates should satisfy

    R_21≤ T_21' =(1+(1-α_2-α_2')P/(α_1+α_2+α_2')P+N_1)
           R_22≤ T_22' =(1+α_2 P/α_1 P+N_1)
           R_1 ≤ T_1 =(1+α_1 P/N_1).


  * At receiver 2, [𝐱_21'+𝐱_3] first decoded while treating other signals as noise and removed from 𝐲_2. Next, 𝐱_22 and 𝐱_21 are decoded successively. For reliable decoding, the code rates should satisfy

    R_21≤ T_21” =(c_21+(1-α_2-α_2')P/(α_2+α_2')P+N_2)
          R_3 ≤ T_3' =(c_3+P/(α_2+α_2')P+N_2)
          R_22≤ T_22” =(1+α_2 P/α_2' P+N_2)
          R_21≤ T_21”' =(1+α_2' P/N_2)

where c_21=(1-α_2-α_2')P/(1-α_2-α_2')P+P=1-α_2-α_2'/2-α_2-α_2' and c_3=P/(1-α_2-α_2')P+P=1/2-α_2-α_2'. Note that 0≤ c_21≤1/2, c_21+c_3=1, and 1/2≤ c_3≤ 1.

  * At receiver 3, 𝐱_3 is decoded while treating 𝐱_1+𝐳_3 as noise. Reliable decoding is possible if

    R_3 ≤ T_3” =(1+P/α_1 P+N_3).


Putting together, we can see that given α_1,α_2,α_2'∈[0,1], the following rate region is achievable.

    R_1 ≤ T_1
           R_2 ≤ T_2 =min{T_21',T_21”,T_21”'}+min{T_22',T_22”}
           R_3 ≤ T_3=min{T_3',T_3”}

where

    T_1 =(1+α_1 P/N_1)
           T_2 = min{T_21',T_21”,T_21”'}+T_22”
              = min{min{T_21',T_21”},T_21”'}+T_22”
              ≥min{(c_21+(1-α_2-α_2')P/(α_1+α_2+α_2')P+N_2),.
                 .(1+α_2' P/N_2)}+(1+α_2 P/α_2' P+N_2) 
    
    
    
           T_3 ≥(c_3+P/max{α_1,α_2+α_2'} P+N_3).






 §.§ The Gap for Relatively Large R_2


We choose α_1 and α_2 such that α_1 P≥ N_2, that α_2 P≥ N_3, that α_1=α_2'≤α_2, and that α_1+α_2≤1/2. It follows that c_21≥1/3. We get the lower bounds for each term of T_2 expression above.

    min{T_21',T_21”}
          ≥(c_21+(1-α_1-α_2)P/(2α_1+α_2)P+N_2)
          ≥(1/3+(1-α_1-α_2)P/(3α_1+α_2)P)
          ≥(P/(3α_1+α_2)P).

The first entry of min{·,·} in

    T_2 = min{min{T_21',T_21”}+T_22”,T_21”'+T_22”}
 is lower bounded as follows.

    min{T_21',T_21”}+T_22”
          ≥(P/(3α_1+α_2)P)+((α_1+α_2) P+N_2/α_1 P+N_2)
          = (P/α_1 P+N_2·(α_1+α_2) P+N_2/(3α_1+α_2)P)
          ≥(P/3(α_1 P+N_2))
          ≥(P/6α_1 P).

The second entry of T_2=min{·,·} is lower bounded as follows.

    T_21”'+T_22”
          =(1+α_1 P/N_2)+(1+α_2 P/α_1 P+N_2)
          =(1+(α_1+α_2) P/N_2)
          ≥(α_2 P/N_2).

Putting together, we get the lower bound

    T_2 ≥min{(P/6α_1 P) ,(α_2 P/N_2)}.

Given α_2, we choose α_1 that satisfies (P/6α_1 P)=(α_2 P/N_2). As a result, we can write T_2≥(α_2 P/N_2).
We also have

    T_3 ≥(P/(α_1+α_2) P+N_3) ≥(P/3α_2 P).

Putting together, we can see that the following rate region is achievable.

    R_1≤(α_1 P/N_1)
           R_2≤(α_2 P/N_2)
           R_3≤(P/3α_2 P).

For fixed α_2 and R_2=(α_2 P/N_2), the two-dimensional rate region, given by

    R_1≤(α_1 P/N_1)
              = (P/6α_2 P·N_2/N_1)
           R_3≤(P/3α_2 P)

is achievable.

In comparison, the two-dimensional outer bound region at R_2=(α_2 P/N_2)+1 is given by

    R_1 ≤(P/N_1·7/3)-(α_2 P/N_2)-1
              = (P/α_2 P·N_2/N_1)+(7/3·1/4)
          R_3 ≤(P/N_2·7/3)-(α_2 P/N_2)-1
              = (P/α_2 P)+(7/3·1/4).

As discussed above, the sum-rate bound on R_1+R_3 is loose for R_2 larger than the threshold, so the rate region is a rectangle.

By comparing the inner and outer bound rate regions, we can see that δ_1< (6·7/3·1/4) < 0.91 and δ_3< (3·7/3·1/4) < 0.41. Therefore, we can conclude that the gap is to within one bit per message.



 §.§ Achievable Scheme for Relatively Small R_2


Given α=(α_1,α_2) ∈ [0,1]^2, the region ℛ_α is defined by

    R_1 ≤(1+α_1 P/N_1)
           R_2 ≤min{^+(c_21+(1-α_2)P/(α_1+α_2) P+N_2),.
                                           .(1+α_2 P/N_2)}
           R_3 ≤^+(c_3+P/max{α_1,α_2} P+N_3)

where c_21=1-α_2/2-α_2 and c_3=1/2-α_2,
and ℛ=conv(⋃_αℛ_α) is achievable.


For the case of R_2 < R_2,th, we present the following scheme. At transmitter 2, rate splitting is not necessary. The transmit signal is the sum

    𝐱_2=𝐱_21+𝐱_21'

where 𝐱_21 and 𝐱_21' are differently coded versions of the same message M_2∈{1,2,…,2^nR_2}.

The power allocation: 𝔼[𝐱_1^2]=α_1 nP at receiver 1, 𝔼[𝐱_21^2]=α_2 nP, and 𝔼[𝐱_21'^2]=(1-α_2)nP at receiver 2, and 𝔼[𝐱_3^2]=nP at receiver 3.

The signals 𝐱_21' and 𝐱_3 are lattice codewords using the same coding lattice but different shaping lattices. As a result, the sum 𝐱_21'+𝐱_3 is a lattice codeword.

The received signals are

    𝐲_1=𝐱_21'+𝐱_21+𝐱_1+𝐳_1
          𝐲_2=[𝐱_21'+𝐱_3]+𝐱_21+𝐳_2
          𝐲_3=𝐱_3+𝐱_1+𝐳_3.

The signal scale diagram at each receiver is shown in Fig. <ref> (b).
Decoding is performed in the following way.


  * At receiver 1, 𝐱_21'
is first decoded while treating other signals as noise. Having successfully recovered M_21, receiver 1 can generate 𝐱_21 and 𝐱_21', and cancel them from 𝐲_1. Next, 𝐱_1 is decoded from 𝐱_1+𝐳_1. For reliable decoding, the code rates should satisfy

    R_21≤ T_21' =(1+(1-α_2)P/(α_1+α_2) P+N_1)
           R_1 ≤ T_1 =(1+α_1 P/N_1).


  * At receiver 2, [𝐱_21'+𝐱_3] first decoded while treating other signals as noise and removed from 𝐲_2. Next, 𝐱_21 is decoded from 𝐱_21+𝐳_2. For reliable decoding, the code rates should satisfy

    R_21≤ T_21” =(c_21+(1-α_2)P/α_2 P+N_2)
          R_3 ≤ T_3' =(c_3+P/α_2 P+N_2)
          R_21≤ T_21”' =(1+α_2 P/N_2)

where c_21=(1-α_2)P/(1-α_2)P+P=1-α_2/2-α_2 and c_3=P/(1-α_2)P+P=1/2-α_2. Note that 0≤ c_21≤1/2, c_21+c_3=1, and 1/2≤ c_3≤ 1.

  * At receiver 3, 𝐱_3 is decoded while treating 𝐱_1+𝐳_3 as noise. Reliable decoding is possible if

    R_3 ≤ T_3” =(1+P/α_1 P+N_3).


Putting together, we get

    R_1 ≤ T_1
           R_2 ≤ T_2 =min{T_21',T_21”,T_21”'}
           R_3 ≤ T_3=min{T_3',T_3”}

where

    T_1 =(1+α_1 P/N_1)
           T_2 = min{T_21',T_21”,T_21”'}
              = min{min{T_21',T_21”}, T_21”'}
              ≥min{(c_21+(1-α_2)P/(α_1+α_2) P+N_2),.
                                           .(1+α_2 P/N_2)}
           T_3 ≥(c_3+P/max{α_1,α_2} P+N_3).




 §.§ The Gap for Relatively Small R_2

We choose α_1 and α_2 such that α_1 P≥ N_2, that α_2 P≥ N_3, that α_1+α_2≤1/2, and that α_1≥α_2. It follows that c_21≥1/3. We get the lower bound

    min{T_21',T_21”}
          = (c_21+(1-α_2)P/(α_1+α_2)P+N_2)
          ≥(1/3+(1-α_1)P/3α_1 P)
          = (P/3α_1 P)

and

    T_2 ≥min{(P/3α_1 P), (α_2 P/N_2)}.

Let us define α_2' by the equality (P/3α_2' P)=(α_2 P/N_2). If we choose α_1≤α_2', then T_2 ≥(α_2 P/N_2).
We can see that the following rate region is achievable.

    R_1≤(α_1 P/N_1)
           R_2≤(α_2 P/N_2)
           R_3≤(P/2α_1 P).


For fixed α_1∈ [α_2,α_2'] and R_2=(α_2 P/N_2), the two-dimensional rate region ℛ_α, given by

    R_1≤(α_1 P/N_1)
           R_3≤(P/2α_1 P)

is achievable. The union ⋃_α_1∈ [α_2,α_2']ℛ_α is a MAC-like region, given by

    R_1≤(α_2' P/N_1)
                     = (P/3α_2 P·N_2/N_1)
                 R_3≤(P/2α_2 P)
           R_1+R_3=(P/2N_1).


In comparison, the two-dimensional outer bound region at R_2=(α_2 P/N_2)+1 is given by

    R_1 ≤(P/N_1·7/3)-(α_2 P/N_2)-1
                     = (P/α_2 P·N_2/N_1)+(7/3·1/4)
                 R_3 ≤(P/N_2·7/3)-(α_2 P/N_2)-1
                     = (P/α_2 P)+(7/3·1/4)
          R_1+R_3 ≤(P/N_1·8/3).

Since δ_1 < (3·7/3·1/4) < 0.41, δ_3 < (2·7/3·1/4) < 0.12 and δ_13 < (2·7/3) < 1.12 < √(2), we can conclude that the gap is to within one bit per message.




§ CONCLUSION

We presented approximate capacity region of five important cases of partially connected interference channels. The outer bounds based on Z-channel type argument are derived. Achievable schemes are developed and shown to approximately achieve the capacity to within a constant bit. 

For future work, the channels with fully general coefficients may be considered. In this paper, we presented different schemes for each channel type although they share some principle. A universal scheme is to be developed for unified capacity characterization of all possible topologies. The connection between interference channel and index coding problems is much to explore. In particular, the results on the capacity region for index coding in <cit.> seem to have an interesting connection to our work.





§ RANDOM CODING ACHIEVABILITY: CHANNEL TYPE 4

At transmitter 1, message M_1 is split into three parts (M_12,M_11,M_10), and the transmit signal is 𝐱_1=𝐱_12+𝐱_11+𝐱_10. The signals satisfy 𝔼[𝐱_12^2]=n(P-N_2-N_3), 𝔼[𝐱_11^2]=nN_3, and 𝔼[𝐱_10^2]=nN_2.

At transmitter 2, message M_2 is split into three parts (M_21,M_20), and the transmit signal is 𝐱_2=𝐱_21+𝐱_20. The signals satisfy 𝔼[𝐱_21^2]=n(P-N_3) and 𝔼[𝐱_20^2]=nN_3. Rate-splitting is not performed at transmitter 3, and 𝔼[𝐱_3^2]=nP.

The top layer codewords (𝐱_12,𝐱_21,𝐱_3) are from a joint random codebook for (M_12,M_21,M_3). The mid-layer codewords (𝐱_11,𝐱_20) are from a joint random codebook for (M_11,M_20). The bottom layer codeword 𝐱_10 is from a single-user random codebook for M_10.

The received signals are

    𝐲_1=(𝐱_12+𝐱_3)+𝐱_11+𝐱_10+𝐳_1
          𝐲_2=(𝐱_12+𝐱_21)+(𝐱_11+𝐱_20)+𝐱_10+𝐳_2
          𝐲_3=(𝐱_21+𝐱_3)+𝐱_20+𝐳_3

Decoding is performed from the top layer to the bottom layer. At receiver 1, simultaneous decoding of (𝐱_12,𝐱_3) is performed while treating other signals as noise. And then, 𝐱_11 and 𝐱_10 are decoded successively. At receiver 2, simultaneous decoding of (𝐱_12,𝐱_21) is performed while treating other signals as noise. And then, simultaneous decoding of (𝐱_11,𝐱_20) is performed. At receiver 3, simultaneous decoding of (𝐱_21,𝐱_3) is performed while treating other signals as noise. For reliable decoding, code rates should satisfy

    R_12≤ I_1=(1+P-N_2-N_3/N_1+N_2+N_3)
                  R_3 ≤ I_2=(1+P/N_1+N_2+N_3)
           R_12+R_3 ≤ I_3=(1+2P-N_2-N_3/N_1+N_2+N_3)
                  R_11≤ I_4=(1+N_3/N_1+N_2)
                  R_10≤ I_5=(1+N_2/N_1)

at receiver 1,

    R_12≤ I_6=(1+P-N_2-N_3/2N_2+2N_3)
                  R_21≤ I_7=(1+P-N_3/2N_2+2N_3)
           R_12+R_21≤ I_8=(1+2P-N_2-2N_3/2N_2+2N_3)
                  R_11≤ I_9=(1+N_3/2N_2)
                  R_20≤ I_10=(1+N_3/2N_2)
           R_11+R_20≤ I_11=(1+2N_3/2N_2)

at receiver 2,

    R_21≤ I_12=(1+P-N_3/2N_3)
                  R_3 ≤ I_13=(1+P/2N_3)
           R_21+R_3 ≤ I_14=(1+2P-N_3/2N_3)

at receiver 3. Putting together,

    R_12≤ T_1=min{I_1,I_6}=I_6
                  R_21≤ T_2=min{I_7,I_12}=I_7
                  R_3 ≤ T_3=min{I_2,I_13}
           R_12+R_21≤ T_4=I_8
           R_12+R_3 ≤ T_5=I_3
           R_21+R_3 ≤ T_6=I_14

at the top layer,

    R_11≤ T_7=min{I_4,I_9}=I_9
                  R_20≤ T_8=I_10
           R_11+R_20≤ T_9=I_11

at the mid-layer,

    R_10≤ T_10=I_5

at the bottom layer. Note that the rate variables are not coupled between layers.
We get the achievable rate region

    R_1=R_12+R_11+R_10≤ T_1+T_7+T_10
                 R_2=R_21+R_20≤ T_2+T_8
                 R_3≤ T_3
           R_1+R_2≤ T_4+T_9+T_10
           R_1+R_3≤ T_5+T_7+T_10
           R_2+R_3≤ T_6+T_8.

This region includes the following region.

    R_1≤(2+P/N_1)-1
                 R_2≤(3+P/N_2)-1
                 R_3≤(3+P/N_3)-(3)
           R_1+R_2≤(1+2P/N_1)-1/2
           R_1+R_3≤(1+2P/N_1)-1
           R_2+R_3≤(1+2P/N_2)-1.

Therefore, we can conclude the capacity region to within one bit.




§ RANDOM CODING ACHIEVABILITY: CHANNEL TYPE 5

Transmit signal construction is the same as the one for channel type 4.
The received signals are

    𝐲_1=(𝐱_12+𝐱_21)+(𝐱_11+𝐱_20)+𝐱_10+𝐳_1
          𝐲_2=(𝐱_21+𝐱_3)+𝐱_20+𝐳_2
          𝐲_3=(𝐱_12+𝐱_3)+𝐱_11+𝐱_10+𝐳_3

Decoding is performed from the top layer to the bottom layer. At receiver 1, simultaneous decoding of (𝐱_12,𝐱_21) is performed while treating other signals as noise. And then, simultaneous decoding of 𝐱_11 and 𝐱_20 is performed. Lastly, 𝐱_10 is decoded. At receiver 2, simultaneous decoding of (𝐱_21,𝐱_3) is performed while treating other signals as noise. And then, 𝐱_20 is decoded. At receiver 3, simultaneous decoding of (𝐱_12,𝐱_3) is performed while treating other signals as noise. And then, 𝐱_11 and 𝐱_10 are decoded successively. For reliable decoding, code rates should satisfy

    R_12≤ I_1=(1+P-N_2-N_3/N_1+N_2+2N_3)
                  R_21≤ I_2=(1+P-N_3/N_1+N_2+2N_3)
           R_12+R_21≤ I_3=(1+2P-N_2-2N_3/N_1+N_2+2N_3)
                  R_11≤ I_4=(1+N_3/N_1+N_2)
                  R_20≤ I_5=(1+N_3/N_1+N_2)
           R_11+R_20≤ I_6=(1+2N_3/N_1+N_2)
                  R_10≤ I_7=(1+N_2/N_1)

at receiver 1,

    R_21≤ I_8=(1+P-N_3/N_2+N_3)
                  R_3 ≤ I_9=(1+P/N_2+N_3)
           R_21+R_3 ≤ I_10=(1+2P-N_3/N_2+N_3)
                  R_20≤ I_11=(1+N_3/N_2)

at receiver 2,

    R_12≤ I_12=(1+P-N_2-N_3/N_2+2N_3)
                  R_3 ≤ I_13=(1+P/N_2+2N_3)
           R_12+R_3 ≤ I_14=(1+2P-N_2-N_3/N_2+2N_3)

at receiver 3. Putting together,

    R_12≤ T_1=min{I_1,I_12}=I_1
                  R_21≤ T_2=min{I_2,I_8}=I_2
                  R_3 ≤ T_3=min{I_9,I_13}=I_13
           R_12+R_21≤ T_4=I_3
           R_12+R_3 ≤ T_5=I_14
           R_21+R_3 ≤ T_6=I_10

at the top layer,

    R_11≤ T_7=I_4
                  R_20≤ T_8=min{I_5,I_11}=I_5
           R_11+R_20≤ T_9=I_6

at the mid-layer,

    R_10≤ T_10=I_7

at the bottom layer. Note that the rate variables are not coupled between layers.
We get the achievable rate region

    R_1=R_12+R_11+R_10≤ T_1+T_7+T_10
                 R_2=R_21+R_20≤ T_2+T_8
                 R_3≤ T_3
           R_1+R_2≤ T_4+T_9+T_10
           R_1+R_3≤ T_5+T_7+T_10
           R_2+R_3≤ T_6+T_8.

This region includes the following region.

    R_1≤(2+P/N_1)-1/2
                 R_2≤(2+P/N_2)-1
                 R_3≤(3+P/N_3)-(3)
           R_1+R_2≤(1+2P/N_1)
           R_1+R_3≤(1+2P/N_1)-1/2
           R_2+R_3≤(1+2P/N_2)-1/2.

Therefore, we can conclude the capacity region to within one bit.

1

EtkinTseWang08
R. Etkin, D. Tse and H. Wang, “Gaussian interference channel
capacity to within one bit,” IEEE Trans. Inf. Theory, vol. 54, no. 12, pp. 5534–5562, Dec. 2008.

SridharanVishwanathJafar08
S. Sridharan, S. Vishwanath, and S. A. Jafar, “Capacity of the
symmetric K-user Gaussian very strong interference channel,”
Proc. IEEE Global Telecommun. Conf., vol. 56, Dec. 2008.

SridharanJafarianVishwanathJafarShamai08
S. Sridharan, A. Jafarian, S. Vishwanath, S. Jafar, and
S. Shamai, “A layered lattice coding scheme for a class of
three user Gaussian interference channel,” 46th Annual Allerton Conference on Communication, Control, and Computing, pp. 531–538, 2008.

BreslerParekhTse10
G. Bresler, A. Parekh, and D. N. C. Tse, “The approximate capacity
of the many-to-one and one-to-many Gaussian interference channels,”
IEEE Trans. Inf. Theory, vol. 56, no. 9, pp. 4566–4592, Sep. 2010.

JafarVishwanath10
S. A. Jafar and S. Vishwanath, “Generalized degrees of freedom of the symmetric Gaussian K-user interference channel,” IEEE Trans. Inf. Theory, vol. 56, no. 7, pp. 3297–3303, Jul. 2010.

ZhouYu13
L. Zhou and W. Yu, “On the capacity of the K-user cyclic Gaussian
interference channel,” IEEE Trans. Inf. Theory, vol. 59, no. 1,
pp. 154–165, Jan. 2013.

OrdentlichErezNazer14
O. Ordentlich, U. Erez, and B. Nazer, “The approximate sum capacity of the symmetric Gaussian K-user interference channel,” IEEE Trans. Inf. Theory, vol. 60, no. 6, pp. 3450–3482, Jun. 2014.

Jafar2014
S. A. Jafar, “Topological interference management through index coding,” IEEE Trans. Inf. Theory, vol. 60, no. 1, pp.
529–568, Jan. 2014.

HuangCadambeJafar12
C. Huang, V. R. Cadambe, and S. A. Jafar, “Interference alignment and
the generalized degrees of freedom of the X channel,” IEEE Trans. Inf. Theory, vol. 58, no. 8, pp. 5130–5150, Aug. 2012.

NiesenMaddahAli13
U. Niesen and M. A. Maddah-Ali, “Interference alignment: From degrees-of-freedom to constant-gap capacity approximations,” IEEE Trans. Inf. Theory, vol. 59, no. 8, pp. 4855–4888, Apr. 2013.

MotahariGharanMaddahAliKhandani14
A. S. Motahari, S. O.-Gharan, M.-A. Maddah-Ali, and A. K. Khandani, “Real interference alignment: Exploiting the potential of single antenna systems,” IEEE Trans. Inf. Theory, vol. 60, no. 8, pp. 4799–4810, Aug. 2014.


ErezZamir04
U. Erez and R. Zamir, “Achieving 1/2log(1+) on the AWGN channel
with lattice encoding and decoding,” IEEE Trans. Inf.
Theory, vol. 50, no. 10, pp. 2293–2314, Oct. 2004.

WilsonNarayananPfisterSprintson10
M. P. Wilson, K. Narayanan, H. Pfister, and A. Sprintson, “Joint physical
layer coding and network coding for bidirectional relaying,” IEEE Trans.
Inf. Theory, vol. 56, no. 11, pp. 5641–5654, Nov. 2010.

NamChungLee10
W. Nam, S.-Y. Chung, and Y. H. Lee, “Capacity of the Gaussian
two-way relay channel to within 1/2 bit,” IEEE Trans. Inf. Theory,
vol. 56, no. 11, pp. 5488–5494, Nov. 2010.

NamChungLee11
W. Nam, S.-Y. Chung, and Y. H. Lee, “Nested lattice codes for Gaussian relay networks with interference,” IEEE Trans. Inf. Theory, vol. 57, no. 12, pp. 7733–7745, Dec. 2011.

NazerGastpar11
B. Nazer and M. Gastpar, “Compute-and-forward: Harnessing interference through structured codes,” IEEE Trans. Inf. Theory, vol. 57, no. 10, pp. 6463–6486, Oct. 2011.

GastparNazer11
M. Gastpar and B. Nazer, “Algebraic structure in network information theory,” IEEE ISIT Tutorial, 2011.


BirkKol98
Y. Birk and T. Kol, “Informed-source coding-on-demand (ISCOD) over
broadcast channels,” in Proc. IEEE INFOCOM, vol. 13, pp. 1257–1264, 1998.

Bar-YossefBirkJayramKol06
Z. Bar-Yossef, Y. Birk, T. S. Jayram, and T. Kol, “Index coding with
side information,” in Proc. 47th IEEE Ann. Symp. Found. Comput. Sci.
(FOCS), 2006, pp. 197–-206.

Bar-YossefBirkJayramKol11
Z. Bar-Yossef, Y. Birk, T. S. Jayram, and T. Kol, “Index coding with
side information,” IEEE Trans. Inf. Theory, vol. 57, no. 3, pp.
1479–1494, Mar. 2011.

AlonLubetzkyStavWeinsteinHassidim08
N. Alon, E. Lubetzky, U. Stav, A. Weinstein, and A. Hassidim, “Broadcasting
with side information,” in Proc. 49th IEEE Ann. Symp. Found. Comput. Sci.
(FOCS), 2008, pp. 823–832.

MalekiCadambeJafar2012
H. Maleki, V. Cadambe, and S. A. Jafar, “Index coding–An interference
alignment perspective,” in Proc. IEEE Int. Symp. Inf. Theory, 2012, pp.
2236–2240.

ArbabjolfaeiBandemerKimSasogluWang13
F. Arbabjolfaei, B. Bandemer, Y. -H. Kim, E. Sasoglu, and
L. Wang, “On the capacity region for index coding,” in Proc.
IEEE Int. Symp. Inf. Theory, Istanbul, Turkey, Jul. 2013, pp. 962–966.

Ong14
L. Ong, “Linear codes are optimal for index-coding
instances with five or fewer receivers,” in Proc. IEEE Int. Symp. Inf. Theory, 2014, pp.
491–495.

EffrosElRouayhebLangberg15
M. Effros, S. El Rouayheb, M. Langberg, “An equivalence between network coding and index coding,” 
IEEE Trans. Inf. Theory, vol. 61, no. 5, pp.
2478–2487, May 2015.

ElGamalKim11
A. El Gamal and Y.-H. Kim, Network Information Theory. Cambridge Univ. Press, 2011.

Zamir14
R. Zamir, Lattice Coding for Signals and Networks. Cambridge Univ.
Press, 2014.







































