Martina Cardone
email: cardone@eurecom.fr

Daniela Tuninetti
email: danielat@uic.edu

Raymond Knopp
email: knopp@eurecom.fr

Umer Salim
email: umer.salim@intel.com

On the Interference Channel with Causal Cognition

This paper considers the causal cognitive interference channel that consists of two full-duplex transmitter-receiver pairs sharing the same channel, where one transmitter can causally learn the message of the other transmitter through a noisy link. This channel models unilateral source cooperation. The work focuses on the generalized degrees-of-freedom of the symmetric, i.e. the two interfering links and the two direct links have the same strength, sum-capacity for the Gaussian noise channel. It is shown through evaluation of various achievable schemes that known sum-rate upper-bounds are achievable to within a constant gap regardless of the strength of the channel parameters. The achievable schemes are quite simple in the sense that only superposition coding is used, while it is shown that more complex schemes using binning can achieve a smaller gap.

I. INTRODUCTION

We consider the Gaussian cognitive overlay system shown in Fig. 1 consisting of two transmitters PTx and CTx and two receivers PRx and CRx. PTx and PRx are so-called primary nodes while CTx and CRx are cognitive nodes. The objectives of the overlay techniques considered here are to firstly allow the cognitive nodes to communicate without hindering the communication of the primary nodes and secondly to enhance the communication reliability of the primary link. To this end, we exploit a lossy communication link between PTx and CTx and we assume that CTx can operate in full-duplex mode on the same communication channel (i.e. same carrier frequency). We treat the case of causal transmission at CTx, in the sense that the knowledge of the primary transmission is only used for encoding at CTx after some processing delay to allow for (partial) decoding or compression of the signal observed at CTx. We shall denote the above described system as Causal Cognitive Interference Channel (CCIC).

Related Work. The presence of a lossy communication link between PTx and CTx enables the CTx to cooperate with the PTx in order to send its message. CTx, in fact, through this noisy channel overhears the signal sent by the PTx and gathers information about its activity. This serves as a basis for unilateral source cooperation, which represents a special case of generalized feedback or bilateral source cooperation [START_REF] Yang | Interference channel with generalized feedback (a.k.a. with source cooperation): Part I: Achievable region[END_REF]. Regarding bilateral source cooperation, the largest known achievable region, to the best of our knowledge, is the one presented in [START_REF] Yang | Interference channel with generalized feedback (a.k.a. with source cooperation): Part I: Achievable region[END_REF]. Here each source splits the message into two sub-messages, i.e. common and private, as in the Han-Kobayashi's scheme for the non-cooperative IC [START_REF] Han | A new achievable rate region for the interference channel[END_REF]. Moreover each of these two messages is further sub-divided into a noncooperative and a cooperative part. The former is transmitted as in the classical IC, the latter is delivered to the destination by exploiting the cooperation among the two sources. Bilateral source cooperation has received lots of attention recently. Host-Madsen [START_REF] Host-Madsen | Capacity bounds for cooperative diversity[END_REF] first studied outer and inner-bounds for the sum capacity of the Gaussian IC with either source or destination bilateral cooperation. Concerning the outer-bound, the author firstly evaluated the cut-set bound, which is easily computable, but turns out to be loose. Consequently, the author tightened the bound by extending to the cooperative case the bounds originally developed by Kramer [4] for the classical IC. Prabhakaran and Viswanath [START_REF] Prabhakaran | Interference channels with source cooperation[END_REF] extended the idea in [6, Th.1] and studied an outer-bound for the Gaussian IC with bilateral source cooperation, by treating the noises as independent (this assumption is not without loss of generality for the general cooperative IC). Tuninetti [START_REF] Tuninetti | An outer bound region for interference channels with generalized feedback[END_REF] derived a general outer-bound for the IC with bilateral cooperation by extending Kramer's idea [START_REF] Kramer | Outer bounds on the capacity of gaussian interference channels[END_REF]Th.1] to general memoryless IC with source cooperation. Concerning unilateral source cooperation, in [START_REF] Wu | Partial decode-forward binning schemes for the causal cognitive relay channels[END_REF] the authors studied both the cases when the collaborating transmitter works in full-duplex and half-duplex mode. With regard to the full-duplex mode, they developed two achievable schemes: one exploits Partial-Decode-Forward relaying and Gelfand-Pinsker binning and the second extends the first by adding rate splitting and superposition coding. These two schemes can be obtained as special cases of [START_REF] Yang | Interference channel with generalized feedback (a.k.a. with source cooperation): Part I: Achievable region[END_REF].

One of the simplest unilateral source cooperation models is the non-causal cognitive interference channel [START_REF] Devroye | Achievable rates in cognitive radio channels[END_REF]. This channel is similar to the classical IC with the difference that CTx has a full non-causal knowledge of the primary message. For this channel model the capacity region is exactly known for some parameter regimes and to within 1 bit otherwise [START_REF] Rini | Inner and outer bounds for the gaussian cognitive interference channel and new capacity results[END_REF]. In this paper we remove this ideal assumption by considering the more realistic scenario that CTx learns the message of PTx through a noisy channel. An interesting question we answer in this work is when causal cooperation achieves the same generalized Degrees-of-Freedom (gDoF) as non-causal message knowledge.

Contributions and Paper Outline. This work characterizes the symmetric gDoF of the Gaussian CCIC (G-CCIC), described in Section II. The symmetric sum-capacity is defined to be the maximum sum-rate that PTx and CTx can achieve in the symmetric G-CCIC, i.e., a system with equal interfering links and equal direct links. Our main contribution is twofold (see Section III). First, for the different parameter regimes, we identify simple achievable schemes that are gDoF optimal, from the very general but highly complex scheme of [START_REF] Yang | Interference channel with generalized feedback (a.k.a. with source cooperation): Part I: Achievable region[END_REF]. Then the sum-capacity gap of these gDoF-optimal schemes is shown to be bounded by constants in all regimes. These schemes can be used as guidelines to deploy practical cognitive radio systems. Interestingly, the schemes only use superposition coding. It is shown that more complex schemes employing binning / Dirty Paper Coding (DPC) [START_REF] Costa | Writing on dirty paper (corresp.)[END_REF] could be used to achieve a smaller gap, thereby pointing to a trade-off between complexity and performance. The proof can be found in Section IV. Secondly, we explicitly identify the parameter regimes where causal cognitive radio offers unbounded gain with respect to the non-cooperative IC and the regimes where it achieves the same gDoF as non-causal cognition.

II. SYSTEM MODEL AND BACKGROUND

General Memoryless Channel Model. A CCIC consists of two input alphabets (X p , X c ), three output alphabets (Y f , Y p , Y c ) and a memoryless transition probability P Y f ,Yp,Yc|Xp,Xc . PTx has a message W p ∈ [1 : 2 N Rp ] for PRx and CTx has a message W c ∈ [1 : 2 N Rc ] for CRx, where N denotes the codeword length and R p and R c are the transmission rates for PTx and CTx, respectively, measured in bits per channel use (logarithms are in base 2). The messages W p and W c are independent and uniformly distributed on their respective domains. At time i ∈ [1 : N ] the PTx maps its message W p into a channel input symbol X p,i (W p ) and CTx maps its message W c and its past channel observations into a channel input symbol X c,i (W c , Y i-1 f ). At time N , the PRx outputs an estimate of its intended message W p based on all its channel observations as W p (Y N p ), and similarly CRx provides W c (Y N c ). The capacity region is defined as the convex closure of all non-negative rate pairs

(R p , R c ) such that max u∈{c,p} P[ W u = W u ] → 0 as N → ∞.
Gaussian Noise Channel and gDoF. A single-antenna full-duplex G-CCIC, shown in Fig. 1, is described by the

input/output relationship   Y f Y p Y c   =   h pf ⋆ h pp h cp h pc h cc   X p X c +   Z f Z p Z c   , (1)
where ⋆ indicates the channel gain that does not affect the capacity region (because CTx can remove its transmit signal X c from its channel output Y f ). The channel gains are complexvalued constants and therefore known to all terminals. The channel inputs are subject to the average power constraints

E |X i | 2 ≤ P i ∈ R + , i ∈ {p, c}.
We assume without loss of generality that Z k ∼ CN (0, 1), k ∈ {f, p, c}. In the following we shall assume that the noises are independent. An often adopted figure of merit for the Gaussian channel is gDoF defined as follows. Let S > 0 and parameterize

P p |h pp | 2 = P c |h cc | 2 := S = S 1 , P p |h pf | 2 := C = S α f , P p |h pc | 2 := I c = S αc , P c |h cp | 2 := I p = S αp ,
where α c and α p measure the strength of the interference/cross links compared to the direct link, and α f that of the cooperation/feedback link. The gDoF of a Gaussian noise channel is defined as [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF], [START_REF] Prabhakaran | Interference channels with source cooperation[END_REF]

d := lim S→+∞ max{R p + R c } 2 log(1 + S) (2)
where the maximization is over all achievable rates (R c , R p ).

In this work we focus on the interference symmetric G-CCIC with α c = α p = α i . Interference-asymmetric scenarios, with either α c = 0 or α p = 0, are studied in [START_REF] Cardone | On the gaussian interference channel with causal cognition, or with unilateral source cooperation[END_REF].

Known Outer-Bounds. In the literature several outerbounds are known for bilateral source cooperation [START_REF] Host-Madsen | Capacity bounds for cooperative diversity[END_REF], [START_REF] Prabhakaran | Interference channels with source cooperation[END_REF], [START_REF] Tuninetti | An outer bound region for interference channels with generalized feedback[END_REF].

Here we specialize them for the case of unilateral cooperation on the complex-valued Gaussian channel with independent noises. We define E [X p X * c ] = ρ P p P c for some ρ ∈ C such that |ρ| ≤ 1. The outer-bounds we will use are obtained by upper bounding each individual mutual information term over ρ in the bounds in [START_REF] Host-Madsen | Capacity bounds for cooperative diversity[END_REF], [START_REF] Prabhakaran | Interference channels with source cooperation[END_REF], [START_REF] Tuninetti | An outer bound region for interference channels with generalized feedback[END_REF]. In particular, the sum-capacity of the G-CCIC can be characterized to within a constant gap by the cut-set bound [START_REF] Host-Madsen | Capacity bounds for cooperative diversity[END_REF] in (4), the bound from [START_REF] Tuninetti | An outer bound region for interference channels with generalized feedback[END_REF] in [START_REF] Prabhakaran | Interference channels with source cooperation[END_REF] and the bound from [START_REF] Prabhakaran | Interference channels with source cooperation[END_REF] in [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF], all given at the top of the next page.

III. GDOF AND CAPACITY TO WITHIN A CONSTANT GAP

Our main result is to show that the sum-capacity upper bound in (3) is achievable to within a constant gap for the interference-symmetric G-CCIC. By setting α c = α p = α i , the upper bounds in (4), ( 5) and ( 6) imply

2d ≤ min d (CS) , d (DT) , d (PV) , (7a)
where

d (CS) := 1 + min {max {1, α i } , max {1, α f }} , (7b)
d (DT) := [1 -α i ] + + max {1, α i } , (7c)
d (PV) := max {1 -α i , α i } + max {1 -α i + α f , α i } . ( 7d
)
The gDoF upper bound in (7a) has been obtained by applying (2) with the upper bounds in (4), ( 5) and [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF]. The details of the proof are omitted for sake of space and can be found in [START_REF] Cardone | On the gaussian interference channel with causal cognition, or with unilateral source cooperation[END_REF]. Fig. 2 shows the gDoF and the gap for the symmetric G-CCIC. The whole set of parameters has been partitioned into multiple sub-regions depending upon different levels of cooperation (α f ) and interference (α i ) strengths. These regimes are numbered from 1 to 6 and the details appear in Section IV. Our main result, proved in Section IV, is

(R p + R c ) OB ≤ min (R p + R c ) (CS) , (R p + R c ) (DT) , (R p + R c ) (PV) (3)
(R p + R c ) (CS) ≤ log (1 + S) + min log 1 + ( √ S + I p ) 2 , log (1 + C + S) , (4)
(R p + R c ) (DT) ≤ min log 1+max{I p , S} 1 + I p 1+( √ S + I p ) 2 , log 1+C +max{I c , S} 1+I c 1+( √ S + I c ) 2 , (5)
(R p + R c ) (PV) ≤ log   1 + √ S √ I c + I p 2   + log (1 + C) + log   1 + √ S I p + √ I c √ C 2   . ( 6
)
Theorem 1 The sum-capacity upper bound in (3) is achievable to within a constant gap of 7.3 bits per channel use regardless of the actual value of the channel parameters.

Before concluding this section, we make some comments on the results we obtained regarding the computation of the gap:

• The gap result of region 6 in Section IV also holds for a big part of region 4. In particular, it does not apply in the regime α i ∈ [2/3, 1], α f < 1α i where the proposed scheme for region 6 does not achieve the optimal gDoF.

• The largest gap in region 6 is 5 bits. This gap may be decreased in several ways. For example, one can optimize the power split between common and private messages instead of using the one presented in [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF]. Alternatively, one can develop more complex coding schemes. An example of latter method is represented by the DPC-based achievable scheme that can be found at the end of Section IV. It can be proved [START_REF] Cardone | On the gaussian interference channel with causal cognition, or with unilateral source cooperation[END_REF] that for the regime α i < 1 and α f > 1 this DPC-scheme achieves the optimal gDoF within 2 bits, rather than 3 bits as the proposed scheme based on superposition coding only.

• The largest gap occurs when the upper bound in ( 6) is the tightest. A possible way to reduce the gap would due to develop a tighter upper bound than the one in (6) used here.

• Cooperation does not improve on the gDoF of the classical IC when 2 3

≤ α i ≤ 2 or α i ≥ 2, α f ≤ 1 or 1 2 ≤ α i ≤ 2 3 , α f ≤ 2α i -1. i.e.
, in these regimes, as far as gDoF is concerned, there is no need for allowing source cooperation.

• Similarly, cooperation does not improve on the gDoF of the classical relay channel when 1 ≤ α i ≤ α f , i.e., in this parameter regime the secondary user acts as a pure relay for the primary user (R c = 0). In other words cognitive radio might not be worth implementing in practical systems.

• Finally, the gDoF of the G-CCIC is equal to that of the non-causal cognitive IC when 2 3

≤ α i ≤ 2 or α i ≥ 2, α f ≥ α i -1 or 0 ≤ α i ≤ 2 3 , α f ≥ min{1 -α i , α i }, i.e.
, in these parameter regimes causal cognition attains the ultimate performance limits of non-causal cognition.

IV. PROOF

We define the gap as ) . We analyze different regimes: Region 1: for α i > 2 and α f ≤ 1 the tightest upper bound gives d ≤ 1. The classical IC in very strong interference with only common messages gives (R p + R c ) (IB) = 2 log (1 + S), which using (2) implies d ≥ 1. This shows the achievability

GAP = (R p + R c ) (OB) - (R p + R c ) (IB
T 1 = T 2 = U 1 = V 2 = ∅, V 1 = X 1 , U 2 = X 2 ,
and by identifying Node1 with PTx, Node2 with CTx, Node3 with PRx and Node4 with CRx, the following sum-rate is achievable

(R p + R c ) (IB) = max PQP X 1 |Q P X 2 |Q min{I(Y p ; Q, X c , X p ), I(Y c ; Q, X c , X p ), I(Y f ; X p |X c , Q) + I(Y c ; X c |X p , Q)}.
In Gaussian noise, we choose Q, U c , U p to be i.i.d. N (0, 1) and define X j = P j (β j Q + γ j U j ) :

|β j | 2 + |γ j | 2 ≤ 1, j ∈ {p, c}.
By assuming ∠h cc -∠h pc = ∠h cp -∠h pp , an achievable sum-rate is

(R p + R c ) (IB) = max (|βc|,|βp|)∈[0,1] 2 min log 1 + C(1 -|β p | 2 ) + log 1 + S(1 -|β c | 2 ) , log 1 + S + I + 2 √ SI |β p ||β c | ≥ log(1 + C) + log(1 + S) if C(1 + S) ≤ I, log (1 + S + I) if C(1 + S) > I.
The pair (β p , β c ) = (0, 0) represents the optimal choice when C(1 + S) ≤ I. The sum-rate corresponding to C(1 + S) > I has been found by equating the two arguments of the max min and by expressing β p as a function of β c . It can be demonstrated that a possibly suboptimal value is β c = 0 that leads to the expression of the sum-rate when C(1 + S) > I holds. By using (2), the derived achievable sum-rate implies d ≥ 1 2 min{1 + α f , α i } since α i > 1. For the case S < C ≤ I/(1 + S) using ( 4) we obtain

GAP ≤ log (1 + C + S) -log(1 + C) ≤ 1bit,
while for C > I/(1 + S) using ( 5) with S ≤ I we obtain

GAP ≤ log 1 + S + I + 2 √ SI -log (1 + S + I) ≤ 1 bit, since 2 √ SI ≤ 1 + S + I ⇐⇒ 0 ≤ 1 + ( √ S - √ I) 2 . Region 3: for α i ∈ [1, 2] the tightest upper bound gives d ≤ 1 2 α i . The classical IC in strong interference with only common messages gives (R p +R c ) (IB) = log (1+S +I), which using (2) implies d ≥ 1 2 α i since α i > 1. From (5) by using S ≤ I GAP ≤ log 1 + S + I + 2 √ SI -log (1 + S + I) ≤ 1 bit, since 2 √ SI ≤ 1 + S + I ⇐⇒ 0 ≤ 1 + ( √ S - √ I) 2 . Region 4: for α i ∈ [2/3, 1) the tightest upper bound gives d ≤ 1 -αi 2 .
The classical IC with common and private messages and with the power split of [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF] gives

(R p + R c ) (IB) = log (1 + S + I) + log 2 + S I -2, which using (2) implies d ≥ 2-αi 2 since α i < 1. From (5) by using I ≤ S GAP ≤ log 1 + 2 √ SI 1 + S + I + log I(1 + S) S(1 + I) + 2 ≤ 3, since 2 √ SI ≤ 1 + S + I ⇐⇒ 0 ≤ 1 + ( S - √ I) 2 . Region 5: α i ∈ [1/2, 2/3
) and α f ≤ 2α i -1 in which case the tightest upper bound gives d ≤ α i . The classical IC with common and private messages and with the power split of [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF] gives [START_REF] Rini | Inner and outer bounds for the gaussian cognitive interference channel and new capacity results[END_REF].

(R p + R c ) (IB) = 2 log 1 + I + S I -2, which using (2) implies d ≥ max{α i , [1 -α i ] + } = α i since α i ∈ [1/2, 1]. From (6) GAP ≤ 2 log   1 + √ S √ I + √ I 2   + ∆+ -2 log 1 + I + S I + 2 ≤ 4 + ∆ < 7.322 bits, ∆ := max C∈[1,I 2 /S] log (1 + C) 1 + √ S √ I + √ I √ C 2 1 + √ S √ I + √ I 2 ≤ log
The upper bound on ∆ is derived as follow: as a function of C, ∆ is a parabola with a minimum in C, so its maximum is attained either for C = 1 or for C = I 2 /S. It can be demonstrated that ∆ is maximum for C = I 2 /S and here ∆ = log [START_REF] Rini | Inner and outer bounds for the gaussian cognitive interference channel and new capacity results[END_REF]

where the maximization is over all joint input distributions P V1,T1,X1,U2,T2,X2 = P V1,T1,X1 P U2,T2,X2 .

In Gaussian noise, we choose V 1 , T 1 , U 2 , T 2 to be i.i.d. N (0, 1) and by identifying Node1 with PTx, Node2 with CTx, Node3 with PRx and Node4 with CRx we let

X j = P j (β j U j + γ j T j ) : |β j | 2 + |γ j | 2 ≤ 1, j ∈ {p, c}.
In the following, inspired by the scheme of [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF] for the classical IC in weak interference, we set

(1-|β c | 2 )I = (1-|β p | 2 )I = 1.
We do not report here the equations characterizing the achievable region for sake of space. It can be shown, [START_REF] Cardone | On the gaussian interference channel with causal cognition, or with unilateral source cooperation[END_REF]Appendix G], that the sum-rate in [START_REF] Wu | Partial decode-forward binning schemes for the causal cognitive relay channels[END_REF] is equal to the term in (8b). Since [1, eq.(8f)] is equal to [1, eq.(8e)] by symmetry, the sum-rate is given by For future use we note that the second term in the above min is the smallest if S ≥ C(I + 1). Using (2) the derived achievable rate in

(R p + R c ) (IB) = min {[
α i ≤ 1 implies that d ≥        1-α i /2 for 1 < α i +α f , 1-α i /2 for 1 ≥ α i +α f , α f ≥ α i , 1-α i +α f /2 for 1 ≥ α i +α f , α f < α i , α i < 1/2, (1+α f )/2 for 1 ≥ α i +α f , α f < α i , α i ∈ [1/2, 1].
The gDoF upper bound is achievable in α i ≤ 2/3. We analyze separately the different subregimes. For the regimes where d ≤ 1α i /2 we use the upper bound in (5) with S ≥ I, otherwise we use the upper bound in [START_REF] Etkin | Gaussian interference channel capacity to within one bit[END_REF]. Subregion 6a: In Gaussian noise, we choose Q, U c , U p to be i.i.d. N (0, 1) and define X j = P j (β j Q + γ j U c ) :

GAP ≤ 2+log 1+S 2I +S • I 1+I +log 1+S +I +2 √ SI S + I + 1 ≤ 3 bits, since I 1+I ≤ 1, 1+S 2I+S ≤ max{1, 1 2I } = 1 because I > 1, 2 √ SI ≤ 1 + S + I ⇐⇒ 0 ≤ 1 + ( √ S - √ I)
Q = V 1 = U 1 = T 1 = S 2 = Z 2 = V 2 = U 2 = ∅, Z 1 = X 1 ,
|β j | 2 + |γ j | 2 ≤ 1, j ∈ {c, p},
and T 2 = U c + λ c Q with λ c as in [START_REF] Costa | Writing on dirty paper (corresp.)[END_REF] so as to "cancel" Q from Y c , that is, so that I(T 2 ; Y c ) -I(T 2 ; Q) = I(T 2 ; Y c |Q). Then, by assuming ∠h cc -∠h pc = ∠h cp -∠h pp , an achievable sum-rate is V. CONCLUSIONS In this work we studied the CCIC, a network with two source-destination pairs sharing the same channel. In contrast to the classical IC, one transmitter, the CTx, exploits information about the other transmitter, the PTx, from its own channel observations; in contrast to the classical cognitive IC, the CTx learns the message of the PTx in a causal way. We used known outer bounds for bilateral source cooperation by adapting them to the case of unilateral cooperation. Our main contribution consisted in showing that for the interference-symmetric case the sum-capacity of the Gaussian CCIC can be achieved to within a constant gap. Interestingly, the achievable schemes only use superposition coding. It is shown that more complex schemes employing DPC may be used to achieve smaller gaps.

(R p + R c ) (IB) = max

Fig. 1 .

 1 Fig. 1. The 2-user Gaussian Causal Cognitive Interference Channel.

Fig. 2 .Region 2 :

 22 Fig. 2. Optimal gDoF and constant gap for the symmetric G-CCIC in the different regimes of (α i , α f ). of the gDoF upper bound. From (4) by using C ≤ S GAP ≤ log (1 + C + S)log (1 + S) ≤ 1 bit. Region 2: for α i > 2 and α f > 1 the tightest upper bound gives d ≤ 1 2 min{α i , 1+α f }. By using [1, Theorem IV.1] withT 1 = T 2 = U 1 = V 2 = ∅, V 1 = X 1 , U 2 = X 2 ,and by identifying Node1 with PTx, Node2 with CTx, Node3 with PRx and Node4 with CRx, the following sum-rate is achievable

1+α f 2 .

 2 By using [1, Theorem 4.1] with Q = U 1 = V 2 = ∅ and by applying Fourier-Motzkin elimination on the resulting region in [1, Theorem 4.1] we get the following achievable sum-rate, (R p + R c ) (IB) = max min{ min{[1, eq.(8a)], [1, eq.(8b)]} + [1, eq.(8d)] (8a) [1, eq.(8e)], [1, eq.(8f )], [1, eq.(8g)], (8b) min{[1, eq.(8a)], [1, eq.(8b)]} + [1, eq.(8ℓ)] 2 ,

  by identifying Node1 with PTx, Node2 with CTx, Node3 with PRx and Node4 with CRx, and by renaming S 1 = Q, we have(R p + R c ) (IB) = max PQP Xp |Q P T 2 ,Xc |Q min{I(X p ; Y f |Q, T 2 , X c ),I(Q, X p ; Y p )} + I(T 2 ; Y c ) -I(T 2 ; Q).

  (|βc|,|βp|)∈[0,1] 2 log 1 + (1 -|β c | 2 )S 1 + (1 -|β p | 2 )I + min log 1+C(1-|β p | 2 ) ,log 1+ S +I + 2|β c ||β p | √ SI 1+(1-|β c | 2 )I .Gap for α i < 1 and α f > 1 with DPC. By using the upper bound in (5) under the condition S ≥ I and the above DPC-based achievable rate, we obtain the following gapGAP ≤ log 1 + 2 √ SI 1 + S + 2I + log 1 + S C ≤2bits using 0 ≤ I and S ≤ C.

  holds. Region 6: α i < 2/3 and α f > [2α i -1] + . We split this region in different sub-regions: Subregion 6a:1 < α i + α f ;here the tightest upper bound gives d ≤ 1 -αi 2 . Subregion 6b: 1 ≥ α f + α i and α f ≥ α i ; here the tightest upper bound gives d ≤ 1 -αi 2 . Subregion 6c: 1 > α f + α i , α i < 1/2 and α f < α i ; here the tightest upper bound gives d ≤ 1α i + ≥ α f + α i , α f < α i and α i ∈ [1/2, 1]; here the tightest upper bound gives d ≤

	Subregion 6d: 1	α f 2 .

  + I 2 + I and 2I < 2I 2 + SI. Subregion 6d: GAP ≤ 5 bits, by following exactly the same steps as done for the subregion 6c.

	Subregion 6b:
	GAP ≤ 2 + log	1 + S 1 + I	+ log 1 + S + I + 2	√ SI +
	-log (2I + S) + log (I) -log	1 + I 2I	-log S + I 2 + I
	= 3 + log + log 1 + S + I + 2 1 + S 2I + S + 2 log √ SI S + I 2 + I	I 1 + I ≤ 4 bits,	+
	since 1 + S + I < S + I 2 + I and 2	√ SI < S + I 2 + I.
	Subregion 6c:
	√ S + SC +log (I + C)+ GAP ≤ 2 + log I + S + I 2 + 2I +log IC + SC + I 2 + 2I √
	-log (IC) -log (2I + S) -log S + I 2 + I ≤ 3 + log 1 + 2I √ S S + I 2 + I + log 1 + 2I √ SI 2I 2 + SI	≤ 5,
	since 2I	√ S < S

2

and I < S. A DPC-based achievable scheme. From [1, Theorem IV.1] with

ACKNOWLEDGMENT

The work of Dr. D. Tuninetti was partially funded by NSF under award number 0643954. The work of Dr. D. Tuninetti was possible thanks to the generous support of Telecom-ParisTech, Paris France, while the author was on a sabbatical leave at the same institution. Eurecom's research is partially supported by its industrial partners: BMW Group Research & Technology, IABG, Monaco Telecom, Orange, SAP, SFR, ST Microelectronics, Swisscom and Symantec. The research carried out at Eurecom leading to these results has received funding from the EU Celtic+ Framework Program Project SPECTRA. The research at IMC leading to these results has received funding from the EU FP7 grants SACRA (n • 249060) and iJOIN (n • 317941).


Martina Cardone
email: cardone@eurecom.fr

Daniela Tuninetti
email: danielat@uic.edu

Raymond Knopp
email: knopp@eurecom.fr

Umer Salim
email: umer.salim@intel.com

Gaussian Half-Duplex Relay Channels: Generalized Degrees of Freedom and Constant Gap Result

This paper considers the Gaussian relay channel where the relay node operates in half-duplex mode. The exact capacity of the linear deterministic approximation of the Gaussian channel at high SNR is derived first. This result is then used to inspire an achievable scheme valid for any SNR in the original channel. The scheme is quite simple: it uses successive decoding and does not incur in the typical delay of backward decoding. The achievable rate is then showed to be at most 3 bits away from the cut-set upper bound, which allows to analytically determine the generalized Degrees-of-Freedom of the channel. A closed form expression for the gDoF-optimal fraction of time the relay node transmits is found as well.

I. INTRODUCTION

In wireless systems, cooperation among nodes that share the same resources results in an overall system performance enhancement. One of the simplest form of cooperation is represented by the Relay Channel (RC), where a source terminal communicates to a destination with the help of a relay node. The relay can primarily operate in two modes: Full-Duplex (FD) and Half-Duplex (HD). In the former the relay simultaneously transmits and receives over the same communication resource; in the latter the relay can either transmit or receive at any given time, but not both. FD relaying in wireless networks has practical restrictions; the enormous difference in transmit and received powers, in fact, makes it infeasible to suppress self-interference. As a result HD relaying proves to be a more realistic and practical technology with its relatively simple signal processing. From an application point of view, the HD model fits future 4G network with relays [START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network[END_REF].

Related Work. The RC has been widely studied in information theory but its capacity is still not known in general [START_REF] Gamal | Network Information Theory[END_REF]. The RC was first introduced by van der Meulen [START_REF] Van Der Meulen | Three-terminal communication channel[END_REF] and then thoroughly studied by Cover and El Gamal [START_REF] Cover | Capacity theorems for the relay channel[END_REF]. In this pioneering work they found a max-flow min-cut outer bound, or cut-set for short, and developed two achievable relaying strategies: the Decode-and-Forward (DF) and the Compressand-Forward (CF). In the DF, the relay fully decodes the information coming from the source, then re-encodes it and sends it to the destination. On the other hand in the CF, the relay compresses the information received and then sends it to the destination. The combination of CF and DF is known to be the best achievable rate for the RC [START_REF] Cover | Capacity theorems for the relay channel[END_REF].

Recently, research on HD relaying has received considerable attention both from an information and communication point of view. In [START_REF] Pawar | Diversity-multiplexing tradeoff of the half-duplex relay channel[END_REF] authors investigated the Diversity Multiplexing Tradeoff for the single HD RC and they proved that it meets the 2 × 1-MISO bound. In [START_REF] Zhang | Study of gaussian relay channels with correlated noises[END_REF] both the FD and the HD RCs are analyzed; in particular the effect of correlated noises at the destination and at the relay is discussed. In [START_REF] Özgür | Approximately achieving gaussian relay network capacity with lattice codes[END_REF], the authors studied multi-relay networks and demonstrated that Quantize-Map-and-Forward (QMF) scheme, i.e., a network extension of CF, based on nested lattice codes achieves the capacity to within a constant gap; this gap, in the single-relay case, is of 5 bits as originally computed in [START_REF] Avestimehr | Wireless network information flow: a deterministic approach[END_REF] but where Gaussian codes were used. In [START_REF] Ong | On capacity and optimal scheduling for the half-duplex multiple-relay channel[END_REF], authors considered a network with multiple relays where the relays listen and transmit phases are fixed and known a priori to all nodes; here authors developed an iterative algorithm to find the optimal relay scheduling, i.e., the time fraction each relay either transmits or receives. In [START_REF] Cardone | The capacity of the gaussian half-duplex multiple-relay network to within a constant gap[END_REF] we also studied the multi-relay network and proposed a scheme based on Noisy-Network-Coding (NNC), i.e., a network extension of CF, and found a smaller gap than that in [START_REF] Özgür | Approximately achieving gaussian relay network capacity with lattice codes[END_REF].

This work concentrates on the single HD relay case with the objective to develop a practical scheme, that is less complex than DF or variations of CF presented in the literature, and still achieves capacity to within a constant gap.

Contributions and Paper Organization. In this work we study the Gaussian HD RC, described in Section II, whose capacity is still unknown. In Section III, we first analyze the Linear Deterministic Approximation (LDA) of the Gaussian channel at high SNR in the spirit of [START_REF] Avestimehr | Wireless network information flow: a deterministic approach[END_REF] and characterize its capacity; we show that a random relay switch and non i.i.d. Ber(1/2) bits are optimal. We then move, in Section IV, to the Gaussian HD RC; we analytically determine its gDoF and show that the cut-set upper bound is achievable to within a constant gap. This is accomplished by developing a simple achievable scheme inspired by the LDA which is quite simple both in the encoding and decoding phases. We also derive the gDoF-wise optimal fraction of time the relay transmits in closed form. We remark here that in deriving the outer bound we do not develop a separate theory for memoryless networks with HD nodes, but we incorporate the HD constraints into the memoryless FD framework as in [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF]. Section V concludes the paper. Some of the proofs can be found in the Appendix.

II. SYSTEM MODEL

In the following we use the notation convention of [START_REF] Gamal | Network Information Theory[END_REF]. The General Memoryless FD RC. A general FD RC consists of two input alphabets (X s , X r ), two output alphabets (Y r , Y d ) and a memoryless channel with transition probability P Yr ,Y d |Xs,Xr . The source has a message W uniformly distributed on [1 : 2 N R ] for the destination, where N denotes the codeword length and R ≥ 0 the transmission rate measured in bits per channel use (i.e., logarithms are in base 2). At time i, i ∈ [1 : N ], the source maps the message W into the input symbol X s,i (W ), and the relay maps its past channel observations into the input symbol X r,i Y i-1 r . At time N , the destination makes an estimate of W based on all its channel observations as W Y N d . The capacity is the largest rate R such that P[ W = W ] → 0 as N → +∞.

The capacity of the general memoryless FD RC is unknown. The best upper bound is the cut-set bound [2, Thm.16.1]

R ≤ r (CS) := max PX s ,Xr min I(X s , X r ; Y d ), I(X s ; Y r , Y d |X r ) .
The best inner bound is a combination of CF and DF [START_REF] Cover | Capacity theorems for the relay channel[END_REF].

The Gaussian HD RC. A HD RC is a special memoryless FD RC [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF] where, with a slight abuse of notation compared to the previous paragraph, the channel input of the relay is the pair (X r , S r ), with X r ∈ X r and S r ∈ {0, 1} representing the state random variable that indicates whether the relay is in receive-mode (S r = 0) or in transmit-mode (S r = 1). The single-antenna Gaussian HD RC has input/output relationship

Y r = h sr X s (1 -S r ) + Z r , (1a)
Y d = h sd X s + h rd X r S r + Z d , (1b)
where the channel gains h sd , h sr , h rd are complex-valued and constant, and the channel inputs are subject to the average power constraints

E |X i | 2 ≤ P i ∈ R + , i ∈ {s, r}.
We assume without loss of generality that the noises are propercomplex Gaussian random variables with zero-mean and unit variance. We further assume that Z d is independent of Z r . Note that the relay can convey at most 1 bit of information to the destination through the binary state S r ; in this case we say that the relay employs random switch between the receiveand transmit-phases [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF]. On the other hand, if the receive-and transmit-phases are fixed and a priori known to all nodes, we say that the relay employs a deterministic switch.

The capacity of the channel in ( 1) is unknown. Here we make progress towards determining its capacity by first establishing its gDoF, i.e., an approximate capacity characterization at high-SNR [START_REF] Avestimehr | Wireless network information flow: a deterministic approach[END_REF], and then showing that the capacity outer bound is achievable to within a constant gap for any choice of the channel parameters. For a SNR > 0 consider the parameterization

P s |h sd | 2 = S = SNR β sd , source-destination link (2a) P r |h rd | 2 = C = SNR β rd , relay-destination link (2b) P s |h sr | 2 = I = SNR βsr , source-relay link, (2c)
for some non-negative (β sd , β rd , β sr ). The gDoF is defined as

d := lim SNR→+∞ C(S, I, C) log(1 + SNR)
,

where C(S, I, C) = max{R} is the capacity of the channel in [START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network[END_REF]. The gDoF characterizes the capacity in the limit for infinite SNR. At finite SNR the capacity is said to be known to within b bits if one can show rates r (in) and r (out) such that

r (in) ≤ C(S, I, C) ≤ r (out) ≤ r (in) + b log(2).
To obtain insights into the behavior of the capacity of the Gaussian HD RC in (1), we consider first its LDA at high SNR [START_REF] Avestimehr | Wireless network information flow: a deterministic approach[END_REF]. The LDA is a noiseless HD RC which input/output relationship is

Y r = S n-βsr X s (1 -S r ), (3a)
Y d = S n-β sd X s + S n-β rd X r S r , (3b)
where (β sr , β sd , β rd ) are integer numbers, (X s , X r , Y r , Y d ) are vectors of length n := max{β sr , β sd , β rd }, S is the n × n shift matrix [START_REF] Avestimehr | Wireless network information flow: a deterministic approach[END_REF], and S r is the state of the relay.

III. THE CAPACITY OF THE LDA AND A SIMPLE ACHIEVABLE SCHEME (OPTIMAL TO WITHIN 1 BIT)

In this section we characterize the capacity of the LDA in [START_REF] Van Der Meulen | Three-terminal communication channel[END_REF]. It is well known that the capacity of a general noiseless RC is given by the cut-set bound r (CS) [START_REF] Gamal | Network Information Theory[END_REF]. We first evaluate the cut-set bound for the LDA and show that the optimal input distribution has a random switch and does not correspond to i.i.d. Ber(1/2) bits. We then derive a simple achievable scheme (with deterministic switch and i.i.d. Ber(1/2) input bits) that is optimal to within 1 bit. This latter scheme motivates the asymptotically optimal scheme for the Gaussian HD RC presented in Section IV.

Theorem 1

The capacity of the LDA in (3) is given by

C (HD-LDA) = β sd + max γ∈[0,1] min (1 -θ * (γ)) log 1 1 -θ * (γ) + θ * (γ) log L -1 θ * (γ) , γ[β sr -β sd ] + for β sr > β sd , β rd > β sd , C (HD-LDA) = β sd for β sr ≤ β sd or β rd ≤ β sd .
where θ * (γ) = 1 -max{2 -[β rd -β sd ] + , γ}.

Proof: We distinguish two cases. Case 1: β rd ≤ β sd or β sr ≤ β sd . In general the capacity of any HD RC is upper bounded by that of the corresponding FD RC. The capacity of the FD version of the LDA in (3) is

C (FD-LDA) = max PX s ,Xr min H(Y d ), H(Y r , Y d |X r ) = β sd + min{[β rd -β sd ] + , [β sr -β sd ] + },
H(Y d ) ≤ H(Y d,u ) + H(Y d,l ) ≤ H(Y d,u ) + β sd , since Y d,l contains β sd bits. Next the distribution of Y d,u P[Y d,u = y] = γδ[y] + (1 -γ)P[X r,u = y|S r = 1]
for y ∈ [0 : L -1], L := 2 β rd -β sd > 1, where δ[y] = 1 if y = 0 and zero otherwise, and where γ := P[S r = 0] (i.e., the fraction of time the relay listens to the channel). Note that Y d,u is zero when either the relay is silent (with probability γ) or the relay is active and sends the whole-zero vector (with probability (1 -γ)). Then

H(Y d,u ) ≤ (1 -θ) log 1 1 -θ + θ log L -1 θ where θ := P[Y d,u = 0] ∈ [0, 1 -γ]. The upper bound on H(Y d,u ) is maximized by θ = θ * := 1 -max{1/L, γ}. Thus C (HD-LDA) = max PX s ,Xr ,Sr min H(Y d ), H(Y r , Y d |X r , S r ) ≤ β sd + max γ∈[0,1] min (1 -θ * ) log 1 1 -θ * + θ * log L -1 θ * , γ[β sr -β sd ] + , since H(Y r , Y d |X r , S r ) ≤ γ max{β sr , β sd } + (1 -γ)β sr .
The above upper bound on C (HD-LDA) is achievable. Let S r ∼ Ber(1 -γ) independent of everything else, and X s and X r be independent. The source uses i.i.d. Ber(1/2) bits; the relay uses i.i.d. Ber(0) bits for X r,l and P[X r,u = y|S r

= 1] = p * 0 if y = 0 and P[X r,u = y|S r = 1] = (1 -p * 0 )/(L - 1) otherwise, for p * 0 = [1/L-γ] + 1-γ
, for X r,u ; the distribution of X r,u in state S r = 0 is irrelevant since its contribution at the destination is zero anyway, so we can assume that the input distribution for X r is independent of the state S r . With this choice, straightforward computations show that the upper bound on C (HD-LDA) is achievable thereby concluding the proof.

The capacity in Thm. 1 shows that i.i.d. Ber(1/2) input bits and random switch are not optimal. Indeed, with i.i.d. Ber(1/2) input bits and deterministic switch one can achieve

r (HD-LDA) = β sd + γ (LDA) [β sr -β sd ] + since r (HD-LDA) = max PX s ,Xr ,Sr min H(Y d |S r ), H(Y r , Y d |X r , S r ) = max γ∈[0,1] min{γβ sd + (1 -γ) max{β sd , β rd }, γ max{β sd , β sr } + (1 -γ)β sd }
and where the optimal γ is

γ (LDA) = (β rd -β sd ) (β rd -β sd )+(βsr-β sd ) for β rd > β sd , β sr > β sd 0 otherwise.
Notice that C (HD-LDA) -r (HD-LDA) ≤ H(S r ) ≤ log(2), that is, i.i.d. Ber(1/2) input bits and deterministic switch are optimal to within 1 bit. The scheme that achieves r (HD-LDA) is shown in Figs. 1(a the duration of Phase II is such that all the bits accumulated in Phase I can be delivered to the destination, that is γ(β srβ sd ) = (1 -γ)(β rd -β sd ), which gives precisely the optimal γ (LDA) . The total number of bits decoded at the destination is

1 • β sd + γ (LDA) • (β sr -β sd ), as claimed.
IV. THE GDOF AND THE CAPACITY TO WITHIN 3 BITS FOR THE GAUSSIAN HD RC In this section we shall mimic the strategy in Figs. 1(a) and 1(b) for the HD Gaussian RC. With this we can show: Theorem 2 The cut-set upper bound for the HD Gaussian RC is achievable to within 3 bits. This characterizes the gDoF as

d = β sd + γ (LDA) [β sr -β sd ] + . ( 4
)
Proof: Upper Bound. The capacity of the HD Gaussian RC is upper bounded by C(S, I, C) ≤ r (CS-HD-G) := max (γ,Ps,0,Ps,1,Pr,0,Pr,1)∈R 5

+ min H(S r ) + γI 1 + (1 -γ)I 2 , γI 3 + (1 -γ)I 4 , (5)
where

I 1 := log 1 + |h sd | 2 P s,0 , I 2 := log 1 + |h sd | 2 P s,1 + |h rd | 2 P r,1 2
I 3 := log 1 + (|h sr | 2 + |h sd | 2 )P s,0 , I 4 := log 1 + |h sd | 2 P s,1 ,
with γP u,0 + (1 -γ)P u,1 ≤ P u , u ∈ {s, r}. This upper bound follows from the cut-set bound r (CS) by using

I(S r ; Y d ) ≤ H(S r ) = -γ log(γ) -(1 -γ) log(1 -γ),
and by the fact that in state S r = ℓ ∈ [0 : 1] joint Gaussian inputs with powers (P s,ℓ , P r,ℓ ), such that the average power constraints are satisfied, maximize the differential entropies. The upper bound r (CS-HD-G) implies that (4) is a gDoF upper bound (the details of the proof are in Appendix). Lower Bound. We can mimic the strategy developed for the LDA as follows. We assume S ≤ C, otherwise we use direct transmission to achieve R = log(1 + S). The transmission is divided into two phases. In Phase I of duration γ the transmit signals are

X s [1] = √ 1 -δX b1[1] + √ δX b2 , X r [1] = 0, δ := 1 1 + S .
The relay applies successive decoding of X b1 [START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network[END_REF] followed by

X b2 from Y r [1] = √ C √ 1 -δX b1[1] + √ C √ δX b2 + Z r [1], which is possible if R b1[1] ≤ γ log (1 + C) -γ log (1 + Cδ) R b2 ≤ γ log (1 + Cδ) . (6)
The destination decodes X b1 [START_REF]LTE-A, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network[END_REF] treating X b2 as noise from

Y d [1] = √ S √ 1 -δX b1[1] + √ S √ δX b2 + Z d [1], which is possible if R b1[1] ≤ γ log (1 + S) -γ log (1 + Sδ) . (7)
Finally, since we assume S ≤ C, Phase I is successful if ( 6) and ( 7) are satisfied. In Phase II of duration 1 -γ the transmit signals are

X s [2] = X b1[2] , X r [2] = X b2 .
The destination applies successive decoding of X b2 followed by X b1 [START_REF] Gamal | Network Information Theory[END_REF] from

Y d [2] = √ SX b1[2] + √ I X b2 + Z d [2], which is possible if R b2 ≤ (1 -γ) log (1 + Iδ) (8) R b1[2] ≤ (1 -γ) log(1 + S). (9)
By imposing that the rate R b2 is the same in both phases, that is, that ( 6) and ( 8) are equal, we get that γ should be chosen equal to

γ * = log 1 + I 1+S log 1 + I 1+S + log 1 + C 1+S .
Note: lim SNR→∞ γ * = γ (LDA) . The rate sent directly from the relay to the destination, that is, the sum of ( 7) and ( 9), is

R b1[1] + R b1[2] = log(1 + S) -γ * log 1 + S 1 + S ,
therefore the total rate in the two phases is

C(S, I, C) ≥ R b1[1] + R b1[2] + R b2 ≥ r (HD-G) := log(1 + S) 1 + (c 1 -1)(c 2 -1) (c 1 -1) + (c 2 -1) , (10)
where

c 1 := log (1 + I + S) log (1 + S) ≥ 1 c 2 := log (1 + C + S) log (1 + S) ≥ 1.
Note: the above rate is completely symmetric with respect C and I. By similar steps as done in the Appendix, one can show that r (HD-G) in [START_REF] Cardone | The capacity of the gaussian half-duplex multiple-relay network to within a constant gap[END_REF] implies that (4) is achievable.

Gap. We upper bound r (CS-HD-G) -r (HD-G) . Case 1: S ≤ C. The gap is given by GAP ≤ 2 log(2) +

x 2 + y 2 + xy + x x 2 + y 2 + 2xy + x + y ≤ 3 bits, where x := log 1 + I

1+S

and y := log 1 + C 1+S . Case 2: S > C. In this case the relay stays silent and the achievable rate is R = log(1 + S). The gap is

GAP ≤ 2 log(2) + log (1 + S) (b 1 -1)(b 2 -1) (b 1 -1) + (b 2 -1) ≤ 2 log(2) + log (1 + S) (b 2 -1) = 2 log(2) + log 1 + C 1 + S ≤ 3 bits,
where the last inequality is due to the fact that C < S.

We conclude by pointing out some important practical aspects of our LDA-inspired achievable scheme: (a) the destination does not use backward decoding, which simplifies the decoding procedure and incurs no delay, (b) the destination uses successive decoding, which is simpler than joint decoding, and (c) no power allocation has been applied at the relay or at the source, which simplifies the encoding procedure. These observations point to an interesting practical tradeoff between complexity and performance: our simple scheme is at most 3 bits far from the capacity but a more complex (both in the encoding and decoding phases) scheme based on Partial-DF (PDF) is at most 1 bit from the capacity [START_REF] Cardone | The capacity to within a constant gap of the gaussian half-duplex relay channel[END_REF]. However, the gap found here is smaller than the 5 bits gap found in previous works based on CF-like schemes [START_REF] Avestimehr | Wireless network information flow: a deterministic approach[END_REF], [START_REF] Özgür | Approximately achieving gaussian relay network capacity with lattice codes[END_REF]. In [START_REF] Cardone | The capacity to within a constant gap of the gaussian half-duplex relay channel[END_REF], we succeeded to further reduce this gap to 1.61 bits by using CF. In other words, more involved techniques (PDF and CF) are found to match the capacity to within a smaller gap at the cost of more complexity both in the encoding and decoding phases.

V. CONCLUSIONS

In this work we considered the half duplex relay channel. First we derived the exact capacity of the linear deterministic approximation of the Gaussian noise channel at high SNR; we showed that random switch is optimal and characterized the optimal input distribution; we also proposed a simple scheme that is optimal to within 1 bit. This simple scheme inspired an achievable scheme for the Gaussian noise channel at any SNR which we showed to be optimal to within 3 bits. Interestingly our simple scheme does not use power allocation or joint backward decoding. This leads to a tradeoff between complexity and performance. On the other hand, the relay transmits only (1 -γ) the time and so in this phase it exploits all its available power, so P r,0 = 0, P r,1 = P r 1 -γ .

Based on the CS outer bound given in [START_REF] Pawar | Diversity-multiplexing tradeoff of the half-duplex relay channel[END_REF] we have r (CS-HD-G) ≤ max

  Fig.1. A scheme for the LDA that is optimal to within one 1 bit.

  ) and 1(b) for the case min{β sr , β rd } > β sd . In Phase I/Fig.1(a) the relay listens and the source sends b 1 (of length β sd bits) directly to the destination and b 2 (of length β sr -β sd bits) to the relay; the duration of Phase I is γ, hence the relay has accumulated γ(β sr -β sd ) bits to forward to the destination. In Phase II/Fig.1(b) the relay forwards the bits learnt in Phase I to the destination by 'repackaging' them into a (of length β rd -β sd bits); the source keeps sending a new b 1 (of length β sr -β sd bits) directly to the destination;

ACKNOWLEDGMENT

  The work of Dr. D. Tuninetti was partially funded by NSF under award number 0643954 and by Telecom-ParisTech, Paris France, while the author was on a sabbatical leave at the same institution. Eurecom's research is partially supported by its industrial partners: BMW Group Research & Technology, IABG, Monaco Telecom, Orange, SAP, SFR, ST Microelectronics, Swisscom and Symantec. The research at Eurecom leading to these results has received funding from the EU FP7 grant agreement CONECT n • 257616. The research at IMC leading to these results has received funding from the EU FP7 grants SACRA (n • 249060) and iJOIN (n • 317941). APPENDIX Since the source transmits in both phases we let P s,0 = βP s γ , P s,1 = (1 -β)P s 1 -γ , β ∈ [0, 1].

+ √ S 2 ,≥ 1 ,

 21 -γ) log 1 + S 1 -γ = max γ∈[0,1] min {2H(γ) + γ log (γ + S) + +(1 -γ) log 1 -γ + √ I H(γ) + γ log (γ + C + S) + (1 -γ) log (1 -γ + S)} ≤ 2+log (1+S) max γ∈[0,1] min {γ +(1-γ)b 1 , γb 2 +(1-γ)} = 2 + log (1 + S) 1 + (b 1 -1) (b 2 -1) (b 1 -1) + (b 2and H(γ) = H(S r ) = -γ log(γ) -(1 -γ) log(1 -γ). The optimal γ = (b1-1) (b1-1)+(b2-1) ∈ [0, 1]is found by equating the two arguments of the max min (this is so becauseγ+(1-γ)b 1 is decreasing in γ while γb 2 + (1 -γ) is increasing in γ). The rate above implies d ≤ lim SNR→+∞ log (1 + S) log (1 + SNR) 1 + (b 1 -1)(b 2 -1) (b 1 -1) + (b 2 -1) = β sd + [β rd -β sd ] + [β sr -β sd ] + [β rd -β sd ] + + [β sr -β sd ] + ,which is equivalent to (4) after straightforward manipulations.


Martina Cardone
email: cardone@eurecom.fr

Daniela Tuninetti
email: danielat@uic.edu

Raymond Knopp
email: knopp@eurecom.fr

Umer Salim
email: umer.salim@intel.com

Gaussian Half-Duplex Relay Networks: Improved Gap and a Connection with the Assignment Problem

published or not. The documents may come

I. INTRODUCTION

Cooperation between nodes in a network has been proposed as a potential and promising technique to enhance the performance of wireless systems in terms of coverage, throughput, and diversity. The simplest form of collaboration can be modeled as a Relay Channel (RC) [START_REF] Cover | Capacity theorems for the relay channel[END_REF]. The RC is a multi-terminal network where a source conveys information to a destination with the help of one relay. A relay is said to work in Half-Duplex (HD) mode if at any time / frequency instant it can not simultaneously transmit and receive. The HD modeling assumption is, at present, more practical than the Full-Duplex (FD) one since practical restrictions, such as the inability to perfectly cancel the self-interference, make the implementation of FD relays challenging. Motivated by the undeniable practical importance of the RC, in this paper we analyze a system where the communication between a source and a destination is assisted by multiple HD relays.

Despite the large amount of work on the RC, its capacity is still not known in general. [START_REF] Cover | Capacity theorems for the relay channel[END_REF] developed two coding schemes, Decode-and-Forward (DF) and Compress-and-Forward (CF), a general upper bound on the capacity (cut-set) and showed capacity for certain classes of RCs. [START_REF] Host-Madsen | On the capacity of wireless relaying[END_REF] derived upper and lower bounds on the capacity of the Gaussian HD RC; the former is based on the cut-set argument; the latter exploits Partial DF; the relay listen/transmit switch is considered as fixed (i.e., deterministic switch). [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF] showed that larger achievable rates can be attained with a random switch at the relay; moreover it argued that HD constraints can be incorporated into the general memoryless FD framework by considering appropriate state random variables. Here we follow the approach of [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF] and specialize known FD inner and outer bounds to the HD case.

For Gaussian HD relay networks with K nodes (a source, a destination and K -2 relays), [START_REF] Avestimehr | Wireless network information flow: a deterministic approach[END_REF] showed that quantize-mapforward (QMF) achieves the cut-set upper bound to within 5K bits but did not consider random switch in the upper bound. [START_REF] Özgür | Approximately achieving gaussian relay network capacity with lattice codes[END_REF] showed that QMF can be implemented with lattice codes and it reduced the gap to 5(K -2) while also properly accounting for the random switch in the upper bound. In Theorem 1 we show that, for fairly broad range of relay network sizes (from networks with few relays to up to 239 relays), the gap of [START_REF] Özgür | Approximately achieving gaussian relay network capacity with lattice codes[END_REF] can be reduced to (K/2) log(4K) by using Noisy Network Coding (NNC) [START_REF] Lim | Noisy network coding[END_REF]. Our derived gap is valid for a general fully connected HD relay network. In the FD literature, it is well known that the gap of 1.26K bits for a general network [START_REF] Lim | Noisy network coding[END_REF] can be reduced to 2 log(K -1) bits for a diamond network [START_REF] Chern | Achieving the capacity of the n-relay gaussian diamond network within log(n) bits[END_REF]. In a diamond network the network topology is restricted compared to a general network, i.e., the source can not communicate directly with the destination and the relays can not communicate among themselves. In Theorem 2 we show that similar conclusions hold for HD networks, namely, we derive a reduced gap for HD diamond networks.

In a HD network with K -2 relays, there are 2 K-2 possible combinations of listen/transmit states for the relays. For the diamond network with K -2 = 2 relays, [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF] showed that at most K -1 = 3 states, out of the 2 K-2 = 4 possible ones, with strictly positive probability suffice to achieve capacity to within 4 bits; in this case we say that there are K -1 active states. Inspired by [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF], [START_REF] Brahma | Simple schedules for half-duplex networks[END_REF] showed that for a special HD diamond network with 3 relays, at most 4 states are active. In [START_REF] Brahma | Simple schedules for half-duplex networks[END_REF], it was also numerically verified that for a general HD diamond network with (K-2) ≤ 7 relays, at most K -1 states are active; it was conjectured that this result holds for any K.

Here we show that these results do not depend on the particular topology of diamond networks. In particular, in Theorem 5 we analytically show that at most 3 states are active in a general HD network with 2 relays by using a proof technique different from [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF]. Based on numerical evidences we conjecture that the conjecture of [START_REF] Brahma | Simple schedules for half-duplex networks[END_REF] holds for a general HD relay network, namely that in a network with K -2 HD relays, at most K -1 states are active, out of the 2 K-2 possible states.

In [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF], [START_REF] Brahma | Simple schedules for half-duplex networks[END_REF] it was shown that determining the optimal values of the state probabilities of a diamond network is equivalent to solving a Linear Program (LP). Not surprisingly, the same holds for a general HD network as stated in Theorem 3 where we show, by properly accounting for power allocation and random switch, that a LP gives the asymptotic optimal values of the state probabilities at high SNR, i.e., in a generalized Degrees of Freedom (gDoF) sense [START_REF] Avestimehr | Wireless network information flow: a deterministic approach[END_REF]. One of the difficulties in determining the gDoF lies in the absence of known numerically efficient ways to evaluate the coefficients of the constraints in the LP, which are log-det expressions similar to the capacity of a MIMO channel. In a HD network with K -2 relays, one has to evaluate 2 2(K-2) such log-det terms. In Theorem 4 we make a connection between the problem of finding the gDoF of a MIMO channel with the graph theoretic problem of determining the maximum weighted bipartite matching (MWBM) of a bigraph, also known as assignment problem. As a result, known polynomial time algorithms for the MWBM problem, such as the Hungarian algorithm, can be readily used to efficiently determine the gDoF of a general HD relay network. Citations from the graph theory literature on these problems are omitted for sake of space.

II. SYSTEM MODEL

We use the following notation convention: [n 1 : n 2 ] is the set of integers from n 1 to n 2 ≥ n 1 ; [x] + := max{0, x} for x ∈ R; Y j is a vector of length j with components (Y 1 , . . . , Y j ); for an index set A we let Y A = {Y j : j ∈ A}; 0 j is the all zero row vector of length j; 1 j is the all one column vector of length j; I j is the identity matrix of dimension j;

f 1 (x) . = f 2 (x) means that lim x→+∞ f 1 (x)/f 2 (x) = 1.
A relay network has one source (node 1) that sends a message to one destination (node K) with the help of K -2 causal HD relays (numbered from 2 to K -1) through a shared memoryless channel. We use here the standard definition of capacity, which we do not repeat for sake of space.

A single-antenna complex-valued power-constrained Gaussian HD relay network has input/output relationship

Y = (I K -S)HSX + Z, (1)
where:

Y := [Y 1 , . . . , Y K ] T ∈ C K is the vector of the received signals, X := [X 1 , . . . , X K ] T ∈ C K is the vector of the transmitted signals, S := diag[S 1 , . . . , S K ]
is the diagonal matrix that indicates the state of the relays (here S 1 = 1 since the source always sends,

S k ∈ {0, 1}, k ∈ [2 : K -1],
since a relay can either receive or transmit, and S K = 0 since the destination always receives), H = [h ij ] ∈ C K×K is the constant channel matrix known to all terminals, where h ij with (i, j) ∈ [1 : K] 2 represents the channel from node j to node i. Without loss of generality, we assume that the channel inputs are subject to the average power constraint

E |X k | 2 ≤ 1, k ∈ [1 : K -1],
and that the noises at all nodes are jointly Gaussian with zero mean and unit variance. Furthermore we assume that the noises are independent. The capacity C of the Gaussian HD relay network in (1) is not known. We say that C is known to within GAP bits if one can show an achievable rate R (in) and an outer bound R (out) such that R (out) ≤ R (in) + GAP, and where GAP is a constant that does not depend on the channel gain matrix H in [START_REF] Cover | Capacity theorems for the relay channel[END_REF]. Knowing the capacity to within a constant gap implies the exact knowledge of the gDoF defined as

d := lim SNR→+∞ C log(1 + SNR) , (2)
where the channel gains are parameterized as

|h ij | 2 = SNR βij for some fixed set {β ij ≥ 0 : (i, j) ∈ [1 : K] 2 }.

III. CAPACITY TO WITHIN A CONSTANT GAP

This section characterizes the capacity of the Gaussian HD relay network in (1) to within a constant gap. To accomplish this, we adapt the cut-set upper bound [START_REF] Kramer | Cooperative strategies and capacity theorems for relay networks[END_REF] and the NNC lower bound [START_REF] Lim | Noisy network coding[END_REF] to the HD case by following the approach proposed in [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF]. Our main result is:

Theorem 1 The cut-set upper bound for a general Gaussian HD relay network with K -2 relays is achievable to within

GAP ≤ max ℓ∈[0:K-2] {min{1 + ℓ, K -1 -ℓ} log (1 + ℓ) (3) + min {1 + 3ℓ, ℓ + K -1}} ≤ (K/2) log(4K) bits. (4)
Proof: The proof can be found in Appendix A. The linear part of the gap in (3) is partly due to the random switch at the relays, which can convey at most 1 bit of information per relay per channel use. In the cut-set bound, we upper bounded this amount of information by the number of relays. For large K, the optimal value of ℓ in [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF]

is ℓ ∼ = K-2
2 , which provides the looser gap in (4). For fairly broad range of relay network sizes (up to 239 relays), our NNC-based gap in (4) improves on the gap of 5(K -2) bits in [START_REF] Özgür | Approximately achieving gaussian relay network capacity with lattice codes[END_REF].

The gap in Theorem 1 grows with K and for large K it could be too large to give an approximate capacity characterization. A smaller gap may be obtained by several means: • Inspired by [START_REF] Lim | Noisy network coding[END_REF], one could envisage to use more sophisticated bounding techniques. In [START_REF] Cardone | Gaussian halfduplex relay networks: improved constant gap and connections with the assignment problem[END_REF], we proved that a more involved strategy based on a water-filling power allocation reduces the gap to 2.021K bits, which is smaller than that in [START_REF] Özgür | Approximately achieving gaussian relay network capacity with lattice codes[END_REF] for K ≥ 4, i.e., for strictly more than one relay.

• By employing other achievable schemes. For example, Partial DF gives a smaller gap than NNC in a single relay case [START_REF] Cardone | The capacity to within a constant gap of the gaussian half-duplex relay channel[END_REF]. However, Partial DF seems not to extend easily to networks with an arbitrary number of relays [START_REF] Kramer | Cooperative strategies and capacity theorems for relay networks[END_REF], which is the main reason why we considered NNC here.

• By deriving tighter bounds on specific network topologies, such as the diamond network [START_REF] Chern | Achieving the capacity of the n-relay gaussian diamond network within log(n) bits[END_REF], for which we can show Theorem 2 The cut-set upper bound for the Gaussian HD diamond network with K -2 relays is achievable to within GAP ≤ (K -4) log(2) + 4 log(K) + 2 log(e).

Proof: The proof directly follows from Appendix A, by taking into consideration the fact that in the diamond network the channel matrix H has rank 2 (and thus Rank[H A,s ] = 2) and by using the possibly suboptimal value σ 2 = K/2 -1.

As expected, the gap in Theorem 2 for the HD diamond network is, in general, smaller than that in (4), which is in line with what happens in FD. However, for the FD diamond network the gap is logarithmic in K [START_REF] Chern | Achieving the capacity of the n-relay gaussian diamond network within log(n) bits[END_REF], while the gap in Theorem 2 is linear in K. This is a consequence of further upper bounding, in the cut-set upper bound, the entropy of [1, S 2:K-1 , 0] by the number of relays, which is linear in K.

IV. ANALYSIS OF OPTIMAL SCHEDULES

With the result of Theorem 1, and by substituting the expression in [START_REF] Brahma | Simple schedules for half-duplex networks[END_REF] from Appendix A into (2), we can evaluate the gDoF of the Gaussian HD relay network. Similarly to [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF], [START_REF] Brahma | Simple schedules for half-duplex networks[END_REF], the gDoF is the solution of the LP

d = max{f T x} s.t. -A 1 2 K-2 1 T 2 K-2 0 x ≤ f , x ≥ 0, (5)
where

f T := [0 2 K-2 , 1], x T := [λ 1 , . . . , λ 2 K-2 , d],
and the square matrix A, of dimension 2 K-2 , contains the high-SNR pre-log factors of the different log-determinant terms from the expression in (9) in Appendix A.

We next describe how to evaluate the entries of A by establishing an interesting connection between this problem and the assignment problem in graph theory. The importance of this connection stems for the fact that the computation of the entries of A can be performed very efficiently by using known polynomial time algorithms for the assignment problem.

We start with few definitions. A weighted bipartite graph, or bigraph, is a graph whose vertices can be separated into two sets such that each edge in the graph has exactly one endpoint in each set. Moreover, a non-negative weight is associated with each edge in the bigraph. A matching, or independent edge set, is a set of edges without common vertices. The MWBM problem, or assignment problem, is defined as a matching where the sum of the edge weights in the matching has the maximal value. The Hungarian algorithm is a polynomial time algorithm that efficiently solves the assignment problem. Equipped with these definitions we can show Theorem 3 For a general HD relay network, the (i, j) ∈ [1 : 2 K-2 ] 2 entry of the matrix A in (5) evaluates to the MWBM of a bigraph with weight matrix

(I K -diag[1, s j , 0]) B diag[1, s j , 0] {K}∪A c i ,{1}∪Ai (6)
where B is the 'SNR-exponent matrix' defined as

[B] ℓk = β ℓk ≥ 0 : |h ℓk | 2 = SNR β ℓk , (ℓ, k) ∈ [1 : K] 2 .
The index set A i and the vector s j in (6) are determined from the pair of indices (i, j), which gives the position within the matrix A, as explained in the footnote 1.

The proof of Theorem 3 is a straightforward application of the following general result that establishes the equality between the gDoF of a MIMO channel, i.e., its high-SNR pre-log factor, and the MWBM problem. Theorem 4 Let H ∈ R k×n be a full-rank matrix, where without loss of generality k ≤ n. Let S n,k be the set of all k-combinations of the integers in [1 : n] and P n,k be the set of all k-permutations of the integers in [1 : n]. Then,

|I k + HH H | . = SNR MWBM(B) (7) MWBM(B) := max ς∈S n,k max π∈P n,k k i=1 [B ς ] i,π(i) ( 8
)
where B is the 'SNR-exponent matrix' defined as

[B] ℓk = β ℓk ≥ 0 : |h ℓk | 2 = SNR β ℓk , (ℓ, k) ∈ [1 : K] 2
, and B ς is a square matrix obtained from B by retaining all the rows and the columns indexed by ς.

Proof: We only provide a sketch of the proof (the details may be found in [START_REF] Cardone | Gaussian halfduplex relay networks: improved constant gap and connections with the assignment problem[END_REF]). First we prove that |I k + HH H | . = |HH H | at high SNR, then we apply the Cauchy-Binet formula, the determinant Leibniz formula and the Cauchy-Swartz inequality to |HH H |. In Appendix B, we provide two examples on how (8) can be applied.

With Theorem 4 we can now compute the matrix A in (6) for a general HD relay network and so find the gDoF. A closed form solution for the LP in ( 5) is not available in general. Even for networks with restricted topology, like diamond networks, the analytical solution of ( 5) is elusive. Nonetheless, it is possible to make statements on the 'sparsity' of an optimal solution for the state probability vector [λ 1 , . . . , λ 2 K-2 ].

For the case of the HD diamond network, it was noted in [START_REF] Brahma | Simple schedules for half-duplex networks[END_REF] that, out of the 2 K-2 states, at most K -1 are active. An interesting question is whether this is a consequence of the special topology of a diamond network or whether it holds for any HD relay network. For K -2 = 2 relays we can show: Theorem 5 For a general HD relay network with 2 relays, there exists an optimal schedule, i.e., an optimal value of the 2 2 possible listen-receive configurations/states for the relays, that optimizes d in [START_REF] Özgür | Approximately achieving gaussian relay network capacity with lattice codes[END_REF] with at most 3 active states.

Proof: We only provide a sketch of the proof (the details can be found in [START_REF] Cardone | Gaussian halfduplex relay networks: improved constant gap and connections with the assignment problem[END_REF]). The key idea -and main difference with respect to [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF] -is to determine the channel parameters under which setting one of the λ's to zero is without loss of optimality. The result is the following generalization of [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF]: if

[β 21 -β 41 ] + [β 31 -β 41 ] + ≥ [β 42 -β 41 ] + [β 43 -β 41 ] + ,
1 Index i refers to a "cut" in the network and index j to a "state of the relays". Both indices range in [1 : 2 K-2 ] and must be seen as the decimal representation of a binary number with K-2 bits. A i , i ∈ [1 : 2 K-2 ], is the set of those relays who have a one in the corresponding binary representation of i (e.g., for K-2 = 3 and i

= 6 = 1•2 2 +1•2 1 +0•2 0 we have A 6 = {2, 3} and therefore A c 6 = {4}). s j , such that P(S [2:K-1] = s j ) = λ j , j ∈ [1 : 2 K-2 ]
, sets the state of a relay to the corresponding bit in the binary representation of j (e.g., for K -2 = 3 and j = 6 we have s 6 = [1, 1, 0], which means that nodes 2 and 3 are sending and node 4 is receiving). Average, minimum and maximum number of active states to characterize the capacity of a HD relay network.

then λ 1 = 0 without loss of optimality, otherwise λ 4 = 0.

We conjecture that, for a general HD relay network with any number of relays, Theorem 5 continues to hold, similarly to the conjecture in [START_REF] Brahma | Simple schedules for half-duplex networks[END_REF] for the diamond network. Namely: Conjecture: For a general HD relay network with K -2 relays, there always exists an optimal schedule that maximizes the gDoF with at most K -1 active states.

The conjecture holds for the case of 2 relays as proved in Theorem 5. We proceeded through the following numerical evaluations: for each value of K -2 ∈ [2 : 8], we generated uniformly at random the SNR exponents of the channel gains, we computed the entries of A in [START_REF] Lim | Noisy network coding[END_REF] with the Hungarian algorithm, we solved the LP in [START_REF] Özgür | Approximately achieving gaussian relay network capacity with lattice codes[END_REF] with the simplex method and we counted the number of constraints that equal the optimal gDoF (which is a known upper bound on the number of non-zero entries of an optimal solution). The minimum and the maximum number of active states were found to be 1 and K -1, respectively, as shown in Fig. 1, which also shows the average number of active states computed by giving an equal weight to all the tried channels. Note that the minimum number of active states for a generic HD relay network with K-2 relays has to be at least K-1. To see this, consider a 'line network' where the source can only communicate with relay 1, relay 1 can only communicate with relay 2, etc, and relay K-2 can only communicate with the destination; in a line network, K -1 non-zero states are necessary to enable the source to communicate with the destination. It is interesting that the minimum number of active states given by K -1 appears to be also the required maximum number of active states for optimal gDoF-wise network operation. If the reduction of the number of active states from exponential to linear as conjectured holds, it offers a simpler and more amenable way to design the network [START_REF] Brahma | Simple schedules for half-duplex networks[END_REF].

V. CONCLUSIONS

In this work we studied the Gaussian HD relay network and characterized its capacity to within a constant gap by considering a random switch at the relays. We showed that this gap may be further reduced by considering more structured systems, such as the diamond network. We conjectured that, in a (K-2)-relay network, the optimal schedule has at most K-1 active states, instead of the possible 2 K-2 . This conjecture has been supported by the analytical proof in the case of 2 relays and in general by numerical results. An interesting feature of our conjecture is the formal proof of the equivalence between the problem of finding the coefficients of the gDoF linear program and the associated assignment problem.

ACKNOWLEDGMENT

The work of D. Tuninetti was partially funded by NSF under award number 0643954. Eurecom's research is partially supported by its industrial partners: BMW Group Research & Technology, IABG, Monaco Telecom, Orange, SAP, SFR, ST Microelectronics, Swisscom and Symantec. The research at Eurecom leading to these results has received funding from the EU FP7 grant agreement CONECT n • 257616. The research at IMC leading to these results has received funding from the EU FP7 grant agreement iJOIN n • 317941.

APPENDIX A PROOF OF THEOREM 1

We partition the relays into two sets: those in A lie on the node 1 side of the cut while those in A c lie on the node K side of the cut, for all A ⊆ [2 :

K -1], A c := [2 : K -1]\A.
Upper Bound. The cut-set bound for the general FD network [START_REF] Kramer | Cooperative strategies and capacity theorems for relay networks[END_REF] adapted to the HD case [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF] gives for each A

max{R} ≤ I(X 1 , X A , S A ; Y K ,Y A c |X A c,S A c, S 1 =1, S K =0) (a) ≤ |A|+ s∈[1:2 K-2 ] λ s log I |A c |+1 +H A,s K {1}∪A,s H H A,s (b) ≤ |A| + s∈[1:2 K-2 ] λ s log I |A c |+1 + H A,s H H A,s + s∈[1:2 K-2 ] λ s Rank[H A,s ] log max{1, Tr[K {1}∪A,s ]} (c) ≤ |A| + s∈[1:2 K-2 ] λ s log I |A c |+1 + H A,s H H A,s +min{1+|A|,1+|A c |} log max    1, s∈[1:2 K-2 ] λ s Tr[K {1}∪A,s ]    (d) ≤ s∈[1:2 K-2 ] λ s log I |A c |+1 + H A,s H H A,s (9)
+ min{1 + |A|, 1 + |A c |} log (1 + |A|) + |A| (10)
where the inequalities are due to the following facts: Inequality (a): chain rule of the mutual information, by considering that the discrete random variable S [2:K-1] has at most 2 K-2 masses and by letting

λ s := P[S [2:K-1] = s] ∈ [0, 1] for s ∈ [1 : 2 K-2 ] such that s∈[1:2 K-2 ] λ s = 1.
Here we use the convention that "S [2:K-1] = s" means that the j-th entry of S [2:K-1] is equal to the j-th digit in the binary expansion of the number s. For example: with K = 5 and s

= 4 = 1 • 2 2 + 0 • 2 1 + 0 • 2 0 , the notation "S [2:K-1] = s means S 2 = 1, S 3 = 0, S 4 = 0". K A,s represents the covariance matrix of X A conditioned on [S [2:K-1] = s, S 1 = 1, S K = 0] and H A,s = [(I K -diag[1, s j , 0])Hdiag[1, s j , 0]] {K}∪A c ,{1}∪A .
Because of the power constraint we must have Lower Bound. The NNC lower bound for the general FD network [START_REF] Lim | Noisy network coding[END_REF] adapted to the HD case [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF] gives for each A max{R}≥I

s∈[1:2 K-2 ] λ s K [1:K],s k,k ≤ 1, k ∈ [1 : K].
(X 1 ,X A ; Y A c ,Y K |X A c ,X K ,S [2:K-1] ,S 1 =1,S K =0) -I(Y A ; Y A |X [1:K] , Y A c , Y K , S [2:K-1] , S 1 =1, S K =0) (a) ≥ s∈[1:2 K-2 ] λ s log I |A c |+1 + 1 1+σ 2 H A,s H H A,s -|A| log 1+ 1 σ 2 (b) ≥ s∈[1:2 K-2 ] λ s log I |A c |+1 + H A,s H H A,s -|A| log 1 + 1 σ 2 + s∈[1:2 K-2 ] λ s Rank[H A,s ] log min 1, 1 1 + σ 2 (c) ≥ s∈[1:2 K-2 ] λ s log I |A c |+1 + H A,s H H A,s (11)
-min{1+|A|, 1+|A c |}log(1+σ 2 )-|A| log 1+ 1 σ 2 (12)
where the inequalities are due to the following facts: Inequality (a): in all states, we consider i.i.d. N (0, 1) inputs with Q = S One possible matching assigns node 3 to node 1 and node 4 to node 2 (total weight β 31 + β 42 ), while the other assigns node 3 to node 2 and node 4 to node 1 (total weight β 32 + β 41 ); the best assignment is the one that gives the largest total weight. This MWBM is exactly the pre-log of the log-det formula.

To exclude the case of rank deficient channel matrix in our setting we pose a reasonable distribution, such as for example the i.i.d. uniform distribution, on the phases θ ij , i = 3, 4, j = 1, 2, so that almost surely the channel matrix is full rank. which can also be obtained, with enough patience, by computing the limiting value of the corresponding log-det formula.

  Fig. 1.Average, minimum and maximum number of active states to characterize the capacity of a HD relay network.

  Inequality (b): by exploiting the following relation: 0 K λ max (K)I Tr[K]I, where 'Tr' is the trace. Moreover for a = 0 the following holds |I + |a| K| ≤ max{1, |a|} Rank[K] |I + K|. Inequality (c): since the rank of a matrix is at most the minimum between the number of rows and columns. Inequality (d): by using Jensen's inequality and because of the input power constraints.

  [1:K] to allow the relays to coordinate, and with Y k :=Y k + Z k for Z k ∼N (0, σ 2 ) independent of everything else. Inequality (b): for a = 0 the following holds |I + |a| K| ≥ min{1, |a|} Rank[K] |I + K|. Inequality (c): since the rank of a matrix is the minimum between the number of rows and columns.Gap. By taking the difference between the upper and the lower bounds and by using the possibly suboptimal value σ 2 = 1 we immediately obtain the gap in Theorem 1.APPENDIX B EXAMPLES OF MWBM PROBLEMSExample 1: Case k = n = 2. Consider log I 2 + HH H SNR≫1 . = log SNR max{β31+β42,β32+β41}H := h 31 h 32 h 41 h 42 = SNR β31/2 e jθ31 SNR β32/2 e jθ32 SNR β41/2 e jθ41 SNR β42/2 e jθ42 . The corresponding MWBM problem has one set of vertices A 1 consisting of k = |A 1 | = 2 nodes (refer to these vertices as nodes 1 and 2 -see second subscript in the channel gains) and the other set of vertices A 2 consisting also of n = |A 2 | = 2 nodes (refer to these vertices as nodes 3 and 4 -see first subscript in the channel gains). The weights of the edges connecting the vertices in A 1 to the vertices in A 2 can be represented as the non-negative weights β ij , i = 3, 4, j = 1, 2.

Example 2 :

 2 Case k = 2, n = 3. The MWBM allows to find the high-SNR approximation of the capacity for any MIMO system. As an example, consider a full-rank MIMO systems with n = 3 transmit antennas (nodes 1, 2, 3) and k = 2 receive antennas (nodes 4 and 5) and with SNR-exponent matrix B = β 41 β 42 β 43 β 51 β 52 β 53 . In this case we have MWBM(B) = max β 41 + β 52 , β 41 + β 53 , β 42 + β 51 , β 42 + β 53 , β 43 + β 51 , β 43 + β 52


Christoph Aistleitner
email: aistleitner@math.tugraz.at.

Markus Hofer
email: markus.hofer@tugraz.at.

Manfred Madritsch
email: madritsch@tugraz.at.

On the distribution functions of two oscillating sequences

Keywords: Mathematics Subject Classification: 11K31 (11K06 11K38 11L07) Distribution modulo 1, uniform distribution, set of all distribution functions, oscillating sequences

We investigate the set of all distribution functions of two special sequences on the unit interval, which involve logarithmic and trigonometric terms. We completely characterise the set of all distribution functions G(xn) for (xn) n≥1 = ({cos(αn) n }) n≥1 and arbitrary α, where {x} denotes the fractional part of x. Furthermore we give a sufficient number-theoretic condition on α for which (xn) n≥1 = ({log(n) cos(αn)}) n≥1 is uniformly distributed. Finally we calculate G(xn) in the case when α 2π ∈ Q.

Introduction

In the present paper we consider the set of all distribution functions G(x n ) of sequences (x n ) n≥1 , x n ∈ [0, 1). For an interval I ⊆ [0, 1) we set A(I, N, x n ) to be the number of hits of I among the first N elements of (x n ) n≥1 , i.e.,

A(I, N, x n ) = #{n ≤ N : x n ∈ I} = N n=1 1 I (x n ).
A non-decreasing function g(x) satisfying g(0) = 0, g(1) = 1, is called a distribution function of a sequence (x n ) n≥1 if there exists an increasing sequence (N k ) k≥1 such that

g(x) = lim k→∞ A([0, x), N k , x n ) N k , x ∈ [0, 1], (1)
holds in every point of continuity of g. In the sequel G(x n ) denotes the set of all functions for which (1) holds. Furthermore a sequence (x n ) n≥1 is said to have the asymptotic distribution function g(x) if (1) holds for N k = k. Then the set G(x n ) reduces to a singleton. Moreover if G(x n ) = {x} the sequence (x n ) n≥1 is called uniformly distributed (u.d.). Closely connected to distribution functions of sequences is the concept of the discrepancy of sequences. For a sequence (x n ) n≥1 the discrepancy of the first N elements of (x n ) n≥1 is given as The following problem concerning the set of all distribution functions of a sequence is stated in the open problem section on the web site of Uniform distribution theory1 :

D N ((x n ) n≥1 ) = sup 0≤α<β≤1 A([α, β), N, x n ) N -(β -α) .
Find the set G(x n ) for the following sequences:

(x n ) n≥1 = ({cos(n) n }) n≥1 , (2) (x n ) n≥1 = ({log(n) cos(αn)}) n≥1 , (3) (x n ) n≥1 = ({cos(n + log(n))}) n≥1 , (4)
where {x} denotes the fractional part of x ∈ R.

For the sequence in (4) this problem has already been solved by S.

(x n ) n≥1 = ({cos(αn) n }) n≥1 ,
which is a generalised version of (2).

Theorem 2.1 For α 2π / ∈ Q we set a = 3/4, in the case α 2π = p q ∈ Q for p, q co-prime let

a = lim N →∞ #{n ≤ N : (cos(αn)) n ≥ 0} N = q+1 2q + q-1 4q , if 4 | (q -1), q-1 2q + q+1 4q , if 4 (q -1) (5)
for q odd and let

a = lim N →∞ #{n ≤ N : (cos(αn)) n ≥ 0} N = #{1 ≤ n ≤ q : (cos(αn)) n ≥ 0} q =          1 2 + q-2 4q , if 4 q and 8 | (q -2), 1 2 + q+2 4q , if 4 q and 8 (q -2), q+2 2q + 1 4 , if 4 | q and 8 q, q+2 2q + q-4 4q , if 8 | q (6)
for q even. Then the set of all distribution functions of (x n ) n≥1 is given by G(x n ) = {g a (x)}, with

g a (x) =    0, if x = 0, a, if 0 < x < 1, 1, if x = 1.
Proof:

First we consider the case α 2π / ∈ Q. Let , δ > 0 be small and fixed. Then for sufficiently large

N 0 ∈ N we have λ({x ∈ [0, 1] : cos(2πx) N0 > δ}) < ,
where λ denotes the Lebesgue measure. By the fact that

({ α 2π n}) n≥1 is u.d. in [0, 1) if α 2π / ∈ Q (see e.g. [?]) it follows that lim N →∞ #{1 ≤ n ≤ N : |cos(αn) n | > δ} N < . Furthermore since λ({x ∈ [0, 1] : cos(2πx) < 0}) = 1 2 and by the fact that also ({(2 α 2π n}) n≥1 is u.d. in [0, 1) it follows that lim N →∞ #{1 ≤ n ≤ N : cos(αn) n < 0} N = 1 4 . Noting that | cos(αn) n | ≤ δ and cos(αn) n < 0 imply {cos(αn) n } ≥ 1 -δ. Thus we have lim N →∞ #{1 ≤ n ≤ N : cos(αn) n > δ} N ≥ 3 4 - and lim N →∞ #{1 ≤ n ≤ N : cos(αn) n < 1 -δ} N ≤ 3 4 +
Since and δ are arbitrary, this proves the first part of the theorem.

In the case α 2π = p q ∈ Q we easily see that ({cos(αn)}) n≥1 takes only finitely many different values of the form cos 2π j q , j = 1, . . . , q, which appear periodically with period q. Consider the case that q is odd. We want to calculate k given as k = # j ∈ {1, . . . , q} : cos 2π j q ≥ 0 .

By cos 2π q q = 1 and cos 2π j q = cos 2π q -j q , for j = 1, . . . , q, it follows that k = 2l -1, where l is the maximal value in {1, . . . , q} for which

2π l q < π 2 ⇔ l < q 4 .
Thus if 4 | (q -1) we have l = q-1 4 and it follows cos 2π j q ≥ 0 for q+1 2 values of j = 1, . . . , q. Similarly if 4 (q -1) we have l = q-3 4 and cos 2π j q ≥ 0 for q-1 2 values of j = 1, . . . , q.

Since q is odd it follows for every j = 1, . . . , q that the term cos 2π j q appears in (cos(αn) n ) n≥1

alternating with odd and even exponent, thus for i such that cos(αi) < 0 it follows that

lim N →∞ #{n ≤ N : cos(αi) qn+i > 0} N = 1 2 .
This, together with the above considerations, proves (5).

Assume now that q is even and 4 q. Then cos(αi) = 0 for i = 1, . . . , q and by similar considerations as above we have cos(αi) > 0 for q 2 values of i and q 2 is an odd number. Furthermore for every j = 1, . . . , q, the exponent of the term cos 2π j q in (cos(αn) n ) n≥1 is either always odd or always even. Moreover it is easy to see that the exponents of cos 2π j q and cos 2π j+1 q in (cos(αn) n ) n≥1 cannot be both even or both odd. Thus the number of j's such that cos 2π j q < 0 and which appear with even exponent is q-2 4 when 8 | (q -2) and q+2 4 when 8 (q -2). In the case 4 | q, it follows that cos(αi) = 0 for two values of i. Thus cos(αi) ≥ 0 for q+2 2 values of i = 1, . . . , q. Formula (6) follows now by the similar arguments as above. This completes the proof.

3 The set of all distribution functions of ({log(n) cos(αn)}) n≥1

Properties of the sequence (3) have been studied by Berend, Boshernitzan and Kolesnik [?]. They proved the denseness of (3) in [0, 1) for arbitrary α. Furthermore they also concluded in [?] that sequences of the form

({n a log b (n) cos(2πnα)}) n≥1 (7)
are dense in [0, 1), provided α is irrational and either a > 0 or a = 0, b > 0. Moreover they showed that the sequence in ( 7) is u.d. for α irrational and either a > 0 or a = 0, b > 1. Additionally they remarked without proof that the sequence (3) is not u.d. for uncountably many α, see [?].

The next theorem gives a condition on the parameter α which implies the u.d. property for the sequence in (3).

Theorem 3.1 Let α be such that the discrepancy of the sequence (z n ) n≥1 = { α 2π n} n≥1 is of asymptotic order o 1 log(N ) . Then the sequence

(x n ) n≥1 = ({log(n) cos(αn)}) n≥1 is u.d.
Remark 3.1 It is well-known that there is a close connection between the coefficients of the continued fraction expansion of α and the asymptotic order of the discrepancy of ({αn}) n≥1 . By a classical result of Khintchine [?] from the metric theory of continued fractions, the discrepancy of ({αn}) n≥1 satisfies

D N ({α}, . . . , {αN }) = O(N -1 (log log N ) 1+ )
as N → ∞ for almost all α. Thus the conclusion of Theorem 3.1 holds for almost all α.

Proof:

We have to show that for every interval [a, b) ⊆ [0, 1) lim

N →∞ A([a, b), N, x n ) N = b -a holds.
Fix N sufficiently large and , δ > 0 small and let the sequence (y n ) n≥ N +1 be given by

(y n ) n≥ N +1 = {log( N (1 + δ) k(n) ) cos(αn)} n≥ N +1
where k(n) : {1, . . . , N } → N is such that

N (1 + δ) k(n)-1 < n ≤ N (1 + δ) k(n) .
For the sake of simplicity we assume that and δ are chosen such that N ∈ N and

N (1 + δ) k(N ) = N . Note that k(n) is uniformly bounded from above for all 1 < n ≤ N by k(n) ≤ -log( ) log(1 + δ) .
We have

1 N N k=1 1 {x k ∈[a,b)} -(b -a) = 1 N N k=1 1 {x k ∈[a,b)} + 1 N N k= N +1 1 {x k ∈[a,b)} -1 {y k ∈[a,b)} + 1 {y k ∈[a,b)} -(b -a) ≤ 1 N N k=1 1 {x k ∈[a,b)} + 1 N k= N +1 1 {x k ∈[a,b)} -1 {y k ∈[a,b)} + 1 N N k= N +1 1 {y k ∈[a,b)} -(b -a) . (8)
Furthermore note that we can write

cos(αn) = cos 2π αn 2π + αn 2π = cos 2π αn 2π ,
where x denotes the largest integer smaller than x.

Thus we get for the third term on the right hand-side of (8) by using the Koksma inequality for the functions

f i (x) = 1 {{log( N (1+δ) i ) cos(2πx)}∈[a,b)} and the sequence (z n ) n≥1 that 1 N N k= N +1 1 {y k ∈[a,b)} -(b -a) ≤ k(N ) i=1 c i N N 1 c i N   N (1+δ) (i-1) <k≤ N (1+δ) i 1 {y k ∈[a,b)}   -(b -a) + N N (b -a) ≤ k(N ) i=1 c i N N V (f i (x))D Ni (z n ) N (1+δ) (i-1) <n≤ N (1+δ) i + (b -a) ≤k(N )c k(N ) V (f k(N ) (x))D Ni (z n ) N (1+δ) (i-1) <n≤ N (1+δ) i + (b -a) = (b -a) + o log( N (1 + δ) k(N ) ) log(N ) = (b -a) + o log(N ) log(N ) = (b -a) + o(1), (9)
where

c i = (1 + δ) i -(1 + δ) (i-1) , i = 1, . . . , k(N ), V (f (x)
) denotes the variation of the function f and D N ((z n ) a≤n≤b ) denotes the discrepancy of N consecutive elements of the sequence (z n ) a≤n≤b . Note that for any M >= N for some fixed > 0 we have 1/ log M = O(1/ log N ). This implies D M = O(1/ log N ), uniformly for all M >= N .

For n ≥ N we have

|x n -y n | = log(n) cos(αn) -log( N (1 + δ) k(n) ) cos(αn) = (log( N (1 + δ) k(n) ) -log(n)) |cos(αn)| ≤ (log( N (1 + δ) k(n) ) -log( N (1 + δ) k(n)-1 ) = log(1 + δ).
By ( 9) it follows for sufficiently large N that the number of

N < n ≤ N for which |1 {xn∈[a,b)} -1 {yn∈[a,b)} | = 1 is at most 5 log(1 + δ)N .
Thus for the second term on the right hand-side of (8) we get

lim N →∞ 1 N N k= N +1 1 {x k ∈[a,b)} -1 {y k ∈[a,b)} ≤ 5 log(1 + δ).
Finally it follows for (8) that

lim N →∞ 1 N N k=1 1 {x k ∈[a,b)} + lim N →∞ 1 N N k= N +1 1 {x k ∈[a,b)} -1 {y k ∈[a,b)} + lim N →∞ 1 N N k= N +1 1 {y k ∈[
where

lim k→∞ {c log N k } = β implies F N k (x) → g β (x) and F N (x) = #{n≤N ;xn∈[0,x)} N . Moreover G({c log(n)})
is the set of all distribution functions of the form (10).

Remark 3.2 Note that it follows as a corollary of Lemma 3.1 that the sequence (x n ) n≥1 = ({c log(n)}) n≥1 , c < 0, has distribution functions of the form 1 -g β,|c| (1 -x), where lim k→∞ {|c| log N k } = β and g β,|c| (x) is given in (10). Thus we define the function f β,c (x) as

f β,c (x) =    g β,c (x), if c > 0, 1 -g β,|c| (1 -x) if c < 0, 1 {(0,1]} (x) if c = 0, (11)
theorem. Assume that ({cos(αi) log N k }) k≥1 does not converge for at least one i, then it follows that there are at least two convergent subsequences of ({cos(αi) log N k }) k≥1 which have different limits. If the limit distributions along all these subsequences are equal then the limit distribution of ({cos(αi) log N k }) k≥1 along the whole sequence (N k ) k≥1 is (if it exists) can be written as f β,c (h(x)) as the limit along a sequence for which (12) holds. If at least two limit distributions along subsequences are not equal the limit distribution along ({cos(αi) log N k }) k≥1 does not exist.

Remark 3.4 We illustrate the set G(x n ) in the simple case when α = π, which means that p = 1 and q = 2 in the notation of Theorem 3.2. Note that cos(α) = -1 and cos(2α) = 1, thus as a sequence (N k ) k≥1 which satisfies (12) one can choose for example N k = exp(k + β 1 ) . In this case we have We can calculate the corresponding distribution function by using the previous theorem. Figure 1 illustrates the range of distribution functions which one can achieve by varying β.

Set_of_dist_pictures-eps-converted-to.pdf

  a,b)} -(b -a) ≤ + 5 log(1 + δ) + (b -a) + o(1) = 2 + 5 log(1 + δ) which proves the theorem. The following lemma by Pólya and Szegö [?] characterises the set of distribution functions G({c log(n)}) and is the main tool for the proof of Theorem 3.2. Lemma 3.1 (Pólya and Szegö) The sequence (x n ) n≥1 = ({c log n}) n≥1 , c > 0, has distribution functions of the form g β,c (x) = e

  log(N k )} = β 1 and lim k→∞ {cos(2α) log(N k )} = β 2 = 1 -β 1 .

Figure 1 :

 1 Figure 1: Distribution functions of (x n ) n≥1 for α = π and β = 0, 1 10 , . . . , 9 10 .

1

  Note that by a theorem of Weyl, see e.g. [?], it follows that lim N →∞ D N ((x n ) n≥1 ) = 0 holds if and only if that the sequence (x n ) n≥1 is u.d. in [0, 1). For general results on uniform distribution of sequences and discrepancy theory see [?], [?] or [?].

  Steinerberger. One can find a short version of the proof in the open problem section of Uniform distribution theory 1 . The fact that the sequence in (4) is not u.d. has previously been proved by Kuipers, see[?]. The outline of the rest of the paper is as follows: in the second section we characterise the set of all distribution functions of a general version of the sequence given in (2). We use the Koksma inequality, see e.g. [?], in the third section to find a sufficient condition on the parameter α for which (x n ) n≥1 given in (3) is u.d. Furthermore we give a complete solution of the problem in the case α 2π ∈ Q.

	2 The set of all distribution functions of ({cos(αn) n }) n≥1
	Former results on the sequence (2) are due to Bukor [?] and in more generality Luca [?]. Bukor showed
	that (cos(n) n ) n≥1 is everywhere dense in the interval [-1, 1]. The following theorem characterises the
	set of distribution functions G(x n ) for

Problem 1.10 in the open problem collection as of 11. December

(http://www.boku.ac.at/MATH/udt/unsolvedproblems.pdf)

ACKNOWLEDGEMENTS

The authors want to thank Kurt Girstmair from University of Innsbruck for helpful remarks on linear relations between the values of trigonometric functions. They also appreciate the interesting and fruitful discussions with Volker Ziegler from TU Graz on this topic.

Research supported by the Austrian Research Foundation (FWF), Project S9603-N23. Research supported by the Austrian Research Foundation (FWF), Project S9603-N23 and by the DOC [Doctoral Fellowship Programme of the Austrian Academy of Sciences].

where lim k→∞ {|c| log N k } = β. Theorem 3.2 Let p q := α 2π ∈ Q where p, q are co-prime and

Then for a fixed subsequence (N k ) k≥1 of N with

the asymptotic distribution of (x n ) n≥1 along the subsequence (N k ) k≥1 is given by

where h q,βi,ci (x) is given in (11),

where

Moreover, the set G(x n ) is the set of all distribution functions of the form (13) for those (β 1 , . . . , β q ) for which a subsequence (N k ) k≥1 satisfying (12) exists.

Remark 3.3 For arbitrary q, it is a difficult problem to determine all possible vectors (β 1 , . . . , β q ) for which there exists a subsequence (N k ) k≥1 for which (12) holds, because there can exist non-trivial linear relations between the values cos(αi), i = 1, . . . , q (depending on number-theoretic properties of q). We will not further investigate this issue, the interested reader is referred to a Galois theoretic approach to this problem by Girstmair [?].

Proof:

As mentioned in the proof of Theorem 2.1 the function cos(αn), n ∈ N takes only finitely many different values which appear in a period of length q. Let (N k ) k≥1 be a sequence of N for which (12) holds for some numbers β 1 , . . . , β q . We are interested in the asymptotic behavior of (x n ) n≥1 and by

we get that the limit distribution of (x n ) n≥1 is a mixture of limit distributions of q sequences of the form

Since log(qn) cos(αi) = log(q) cos(αi)+log(n) cos(αi) we get that the distribution function of (z i n ) n≥1 is given as the distribution function of log(n) cos(αi) shifted by a constant and thus it is easy to see that the right hand-side of ( 14) is the distribution function of (z i n ) n≥1 . This proves (13). In order to prove that all functions in G(x n ) can be characterised by (13) we use the Bolzano-Weierstrass