The Two-Tap Input-Erasure Gaussian Channel and its Application to Cellular Communications

This paper considers the input-erasure Gaussian channel. In contrast to the output-erasure channel where erasures are applied to the output of a linear time-invariant (LTI) system, here erasures, known to the receiver, are applied to the inputs of the LTI system. Focusing on the case where the input symbols are independent and identically distributed (i.i.d)., it is shown that the two channels (input- and output-erasure) are equivalent. Furthermore, assuming that the LTI system consists of a two-tap finite impulse response (FIR) filter, and using simple properties of tri-diagonal matrices, an achievable rate expression is presented in the form of an infinite sum. The results are then used to study the benefits of joint multicell processing (MCP) over single-cell processing (SCP) in a simple linear cellular uplink, where each mobile terminal is received by only the two nearby base-stations (BSs). Specifically, the analysis accounts for ergodic shadowing that simultaneously blocks the mobile terminal (MT) signal from being received by the two BS. It is shown that the resulting ergodic per-cell capacity with optimal MCP is equivalent to that of the two-tap input-erasure channel. Finally, the same cellular uplink is addressed by accounting for dynamic user activity, which is modelled by assuming that each MT is randomly selected to be active or to remain silent throughout the whole transmission block. For this alternative model, a similar equivalence results to the input-erasure channel are reported.


I. INTRODUCTION
In recent years various variants of erasure networks have been the focal point of many works in the fields of information theory, coding theory, communication, and digital signal processing (DSP). It turns out that the idealization of situations where symbols are detectable with very high or very low probability is useful in providing accurate and tractable assessment of practical interest. Applications of erasure networks, in general, and erasure channels, in particular, include packet-switched networks, wireless fading channels, impulse noise channels, and sensor networks with faulty transducers. Another interesting DSP application is decimation using frequency shaped random erasures [1] (see also [2] for a somewhat dual problem).
The simplest non-trivial setting incorporating erasures is perhaps a memoryless discrete channel observed through a memoryless erasure channel. In this case, it is straightforward to see that the capacity of the concatenated channel is the capacity of the discrete channel times the erasure rate [3]. Moreover, even if the erasures have memory, the latter result holds [3] [4]. However, adding memory to the discrete channel changes the picture considerably. In [5], Tulino et al. have calculated the capacity of an input power-constrained Gaussian channel concatenated with a memoryless erasure channel. The problem requires obtaining the asymptotic spectral distribution of a sub-matrix of a nonnegative definite Toeplitz matrix obtained by randomly deleting rows and columns. In addition, [5] presents an explicit expression for the optimal input power spectral density (PSD) function. Asymptotic capacity expressions in various regimes such as extreme-SNR, sporadic erasures events, and sporadic non-erasure events, are reported as well. In addition, several useful bounds (lower and upper) in closed form are presented. Recently, the results of [5] were extended in [6] to include any flat fading distribution, not necessarily the on-off process obtained by erasures.
In this paper, we consider the input-erasure Gaussian channel. According to this setup, erasures (known at the receiver only) are applied directly to the Gaussian input of a linear time-invariante (LTI) system (e.g. a finite input response filter, FIR), whose output samples are affected by additive Gaussian noise. To simplify the analysis, we consider independent and identically distributed (i.i.d.) input signaling, and show that in this case the input-erasure channel and the output-erasure channel of [5] are equivalent. Focusing on the case where the channel filter includes two taps, we present an alternative analysis to [5] that obtains the achievable rate without relying on random matrix theory tools. The analysis is based on a simple observation that in the two-tap case, each erasure splits the output vector into two independent sub-vectors. In addition, it uses a useful property of tri-diagonal matrices, which states that their determinant can be expressed as a weighted sum of the determinants of their two main principal sub-matrices. It is also shown that the analysis can be extended to the case in which the erasures are not memoryless.
The results are then used to find the achievable rate supported by a simple cellular uplink model (where intercell interference is limited only to adjacent cells), in which the transmission of each mobile terminal (MT) undergoes erasures due to ergodic shadowing, which simultaneously blocks it from being received by all the base-stations (BSs). We show that with optimal joint decoding of the received signals from all the BSs (that is, multicell processing, MCP), the ergodic per-cell capacity of this cellular uplink equals the rate of the two-tap input-erasure channel considered earlier.
The performance of MCP is compared to that of single-cell processing (SCP), demonstrating that the benefits of MCP decrease with the erasure rate (the reader is referred to [7] and [8] for recent surveys on MCP). We then consider a similar cellular uplink setup but with a dynamic user activity model, in which each user is randomly active or silent for the whole transmission block. We show that with MCP the system throughput per active user is equal to the rate of the two-tap input-erasure channel divided by the probability of an arbitrary user being active. Similar benefits of MCP over SCP, as those reported for the shadowing scenario, are observed also for the user activity model.
It is finally noted that a related analysis has been recently reported in [9], where the outage capacity supported by a similar cellular uplink and user activity model was derived with both MCP and SCP.

II. CHANNEL MODEL
In this work we consider a channel (see Fig. 1.a), where erasures {e n }, known to the receiver only, are applied to the inputs symbols {x n } of a discrete time LTI system with transfer function H(f ). For simplicity, we assume that the LTI system is causal and has a finite 1 impulse response of length (L + 1) symbols. Accordingly, the received signal at time index n, is given by where {h m } L m=0 are the impulse response coefficients such that and z n is the additive complex Gaussian noise z n ∼ CN (0, 1). The erasures e n , are assumed to be i.i.d. Bernoulli 1 It is easily verified that the results extend to any LTI system with finite gain distributed random variables (r.v.'s) e n ∼ B(q) (i.e., e n ∈ {0, 1}, P r(e n = 0) = q, P r(e n = 1) = 1 − q). We consider transmissions in blocks of N symbols. The received vector of an arbitrary block is given by where Y N +L (y 1 , . . . , y N +L ) † is the (N + L) × 1 output vector, Recalling that the receiver is aware of the erasures, it is easy to prove that a Gaussian input distribution is a capacityachieving distribution and that the capacity is given by where the expectation is taken over the diagonal entries of the erasure matrix E N , and I N +L is an (N + L) × (N + L) identity matrix. Unfortunately, finding the optimal covariance matrix and calculating (4) is still an open problem. Instead, we focus in the rest of this work on assessing achievable rates resulting by using i.i.d. inputs, hence, by setting Q N = P I N .

A. Arbitrary FIR Filter
Here we consider an arbitrary L-length FIR filter and rewrite the logdet term of (4) as: By noting that the left-hand-side (LHS) of the last equation is the same as the one resulting from the analysis of the output-erasure channel with i.i.d. inputs, considered in [5] (see Fig. 1.b), we can state the following. This result implies that with i.i.d. inputs, both channels achieve the same rate. Hence, all the results reported in [5] hold verbatim for the input-erasure channel with i.i.d. inputs, by setting the PSD accordingly (i.e., S(f ) = P |H(f )| 2 ) in the results of [5]. The analysis in [5] uses random matrix theory tools to derive the main result which is the rate of the output-erasure channel for any channel FIR filter and any input PSD. The rate result of [5] involves a fixed-point integral equation and in general it is not explicitly formulated. Next, we present an alternative analysis for the special case of i.i.d. inputs and a two-tap channel filter. The resulting rate expression is considerably different than that of [5], and may shed some further light on the problem.

B. Two-Tap Filter (L = 1)
In this section we consider a two-tap channel filter (i.e., its impulse-response includes only two non-zero coefficient h 0 , and h 1 ). Hence, the channel transfer matrix H N +1 reduces to a bi-diagonal Toeplitz matrix. For this special case we have the following.

Proposition 2 The achievable rate of the two-tap inputerasure Gaussian channel with i.i.d. inputs is given by
where and Proof: See Appendix The proof relies on a simple observation that in the twotap case, each erasure splits the output vector into two independent sub-vectors. In addition, it uses a useful property of tri-diagonal matrices, which states that their determinant can be expressed as a weighted sum of their first two main principal sub-matrices. It is noted that this analysis does not involve classical random matrix theory. Moreover, since it relies heavily on the two-tap assumption, it cannot be applied to input-erasure channels with filter lengths larger than two.
Examining the rate expression (6), a few comments are in place. Although the rate expression is an infinite sum, any finite sum, which is evidently a lower bound, can be calculated numerically in a straightforward manner. In addition, convergence is assured since the expression is a power series and (1 − q) ≤ 1. It is also observed that the rate is independent of the filter coefficients' phases, and hence, random phases (known to the receiver) can be added to the channel model without changing the end result. By applying Hadamard's inequality directly to the covariance matrix (I N + G N ) (see (27)), it can be shown that for a fixed filter gain, filter memory reduces the rate. Hence, the rate is maximized for a one-tap filter with equal gain. On this note, it is easily verified that for the special case of h 1 = 0 (memoryless Gaussian channel with erasures), s = 0 and (6) reduces to which was already reported in [10]. Another special case, which is also an upper bound, is the case where q = 0. The capacity of this two-tap channel with i.i.d. inputs is given by [11] R 2tap−ub = log r , where r is defined in (8).
Turning to asymptotic analyses, we refer the reader to [5], where compact closed-form expressions are reported for the rate low-SNR characterization, the rate with sporadic erasures, and the rate with sporadic non-erasures. These expressions can be used verbatim for the two-tap inputerasure channel of interest by setting i.i.d. inputs in [5]. In addition, [5] provides also the high-SNR characterization of the output-erasure channel rate, albeit the calculation of the high-SNR power offset involves a fixed point-equation. Applying definitions of [12] to the rate expression (6), we provide an alternative expression for the high-SNR power offset as well.

Proposition 3 The two-tap input-erasure Gaussian channel rate with i.i.d. inputs is characterized in the high-SNR regime by
And the deleterious effects of increasing erasure rate q are clearly visible. 1) Erasures with Memory: Following the proof of Prop. 2, it can be verified that the presented analysis method can handle also erasures with memory (stationary and ergodic). The only stage that should be altered is the calculation of (35), that is, the probability of having an isolated sequence ℓ of n consecutive non-erasures should be recalculated for the new erasure source. For example, assuming the erasures follow a first order Markov chain with transition probabilities P r(0 → 1) = 1 − q 0 , and P r(1 → 0) = q 1 , it is easily verified that and the corresponding rate of the two-tap input erasure channel with i.i.d. inputs is given by (13) As expected, for q 0 = q 1 = q the erasure source is i.i.d. and (13) reduces to (6). It is interesting to note that for the special case h 1 = 0, which corresponds to a memoryless channel followed by an erasure channel with memory, the rate reduces to where   is the steady-state erasure rate. This results is in agreement with [4], where it has been shown that the capacity of a concatenation of a discrete memoryless channel with capacity C, and an erasure channel (possibly with memory) with erasure rate q, is equal to (1 − q)C.

IV. NUMERICAL RESULTS
The rate (6) is plotted in Figure 2 In addition, the erasure-free (q = 0) rate curve (10) is included as a reference.

V. APPLICATION TO CELLULAR COMMUNICATIONS
Cellular systems are currently the main media to provide high-data rate services to mobile users. Therefore, a continued search for techniques that provide better service and coverage in cellular systems is under way. A promising cooperation-based technique is joint MCP, proposed by Wyner in [13]. Accordingly, clusters of BSs jointly process their signals to mitigate or eliminate the overall interference, since more signals are useful. Unlike conventional approaches that treats interference stemming from other cells as noise, or tries to avoids it, this approach (also referred to as distributed antenna array) exploits the interference to provide better rates to the clusters' MTs.
Here we are interested in further exploring the benefits of MCP when ergodic erasures affect the MTs' transmissions in the uplink. Such erasures account for a scenario where an MT may undergo ergodic deep fading (or shadowing) such that its transmission cannot be received by any of its cluster's antennas.
Motivated by the fact that inter-cell interference is essentially limited to only a small number of BSs, and with mathematical tractability in mind, we assume a synchronous Wyner-like cellular uplink setup. According to this setup (see Fig. 5), an infinite number of cells are arranged on a line, as along a highway. Moreover, the each MT "sees" its own BS antenna (with unit path gain), and the adjacent BS antenna (with path gain α ∈ [0, 1]) only. This model, which was first introduced in [11], focuses on users lying on the cells' boundaries and is thus sometimes referred to as the soft-handoff model. Specifically, assuming a single active user per-cell (intra-cell time-division multiple-access), the received signal at the nth BS antenna, for an arbitrary time index, is given by y n = e n x n + e n−1 αx n−1 + z n , where x n and x n−1 are the MTs' transmissions x n , x n−1 ∼ CN (0, P ), e n and e n−1 are the erasures e n , e n−1 ∼ B(q), and z n is the additive noise z n ∼ CN (0, 1). It is noted that the erasures are assumed to be i.i.d. among different users (along the cells' indices n), and ergodic along the time index for each user. Finally, it is noted that users are not allowed to cooperate.

A. Single Cell Processing
As a reference results we consider two conventional SCP approaches.

1) No Frequency Planning:
The simplest approach is for each cell to decode its own signals while treating the signals from the interfering cell as noise. Assuming that each cell is aware of its own user's erasures and those of the interfering cell's user (see [14] for a similar setting), it is easily verified that the achievable rate is given by where the expectation is taken over e sig and e int which represent arbitrary i.i.d. erasure r.v.'s of the useful signal and interference, respectively, e sig , e int ∼ B(q). By straightforward calculation we get that (17) is given by (18) The high-SNR characterization of R scp is given by It is interesting to observe that the rate above demonstrates a non-interference limited behavior, although the receiver treats the other cell's signals as noise. This is easily explained by noting that with probability q(1 − q) the useful signal is received without interference.

2) Inter-Cell Frequency Sharing:
Here we consider a more involved approach that requires static resource sharing between the cells. Since, according to the soft-handoff model, interference stems from one cell only, by dividing the available bandwidth of W [Hz] into two orthogonal subbands with bandwidth of W/2 [Hz] each, and assigning them alternately to even and odd indexed cells, interference is totally avoided. Accordingly, it is easily verified that the achievable rate is given by where e is an arbitrary erasure r.v., e ∼ B(q).
The high-SNR characterization of R icfs is given by where the deleterious effects of both the erasures, and the bandwidth sharing are clearly observed in the multiplexing gain expression. Comparing the multiplexing gains of the SCP and inter-cell frequency sharing (ICFS) rates, reveals the superiority of the latter for erasure rates q < 1/2 in the high-SNR regime.

B. Multicell Processing
With MCP, the BSs send their received signals to a central processor (CP) via an ideal backhaul network. The CP collects the received signals and jointly decodes the MTs' messages. Since the CP is aware of all the erasures, the overall channel is an ergodic multiple-access channel (MAC) for which the sum-rate capacity divided by the number of cells is given by where E N diag(e 1 , . . . , e N ) is the N × N diagonal erasure matrix, and H N +1 is an (N + 1) × N bi-diagonal Toeplitz channel transfer matrix with [H N +1 ] n,n = 1 and [H N +1 ] n,n−1 = α (where out-of-range indices should be ignored). It is noted that, by the symmetry of the model, the ergodic per-cell sum-capacity derived above is also the equal per-cell capacity.
Comparing the rate expression of the two-tap input-erasure channel with i.i.d. inputs (see (4)) to the per-cell sumrate supported by the soft-handoff model, the following is evident.

Corollary 4
The per-cell sum-rate supported by the softhandoff model with optimal joint decoding and no MT cooperation equals the rate of the two-tap input-erasure Gaussian channel with i.i.d. inputs and h 0 = 1, h 1 = α. Since the shoft-handoff model is equivalent in terms of its per-cell sum-rate to the input-erasure channel, all the results and conclusions reported in Section III also hold here. In particular the high-SNR characterization reduces to The benefits of MCP are evident in the high-SNR regime since its rate has two-fold degrees of freedom relative to the ICFS rate, and 1/q-fold degrees of freedom relative to the SCP rate. It is noted that the MCP rate is an increasing function of the inter-cell interference factor α. This is since: (a) r and s are increasing with α ; (b) r > s ; and (c) by recalling that which is a summation of multiplications of increasing functions of α and hence is an increasing function of α.
It is also worth mentioning that a similar analysis in [9] facilitates also to address the issue of successful transmission per a given user, and when the average rate per user is examined, the results are in agreement with Prop. 6 (or Corr. 4).

C. Numerical Results
The achievable rates of the MCP, SCP and ICFS schemes with α 2 = 0.5 and or P = 14 [dB], are plotted as functions of the erasure rate q, in Figure 6. The figure demonstrate the superiority of MCP over both SCP and ICFS schemes. It is also observed that ICFS is beneficial over SCP for erasure rates smaller than a certain threshold.

D. Discussion
A different scenario which gives rise to a similar, but nonergodic, erasure model in a cellular scenario is one in which the MTs may be active or not in a given block with a given probability accounting for dynamic user activity. According to this model, each user is randomly selected to be active with probability (1 − q) throughout the entire transmission block. This may be implemented by means of control, or simply when the MT has no information to send. In these cases, the erasures are still i.i.d. along the cells' indices but are non-ergodic along the time index for each user. With optimal MCP, the throughput per active user is an r.v., given in the large system limit by (1 − q) due to the strong law of large numbers, we can replace tr (E N ) with (1 − q)N in (25). Following similar argumentations as those made in [15], it can be shown that C mcp−ua converges a.s. to (1 − q) −1 C mcp . Turning to the SCP and ICFS schemes it is easily verified that the throughputs per active user converge a.s. to the corresponding rates of the shadowing setup times (1 − q) −1 . In Figure 7 the throughputs per active user of the MCP, SCP, and ICFS schemes are plotted as functions of the nonactive probability q, for α 2 = 0.5 and P = 14 [dB]. The superiority of MCP over the other schemes is apparent. Also we can observe that both MCP and ICFS are robust and maintain their throughput constant (for ICFS) or almost constant (for MCP) regardless of q, while the throughput of SCP drops sharply with decreasing q. This is easily explained since neither MCP nor ICFS suffers from intercell interference, the first due to the fact that it leverages all received signals as useful, while the second since it avoids interference by frequency planning. On the other hand, SCP treats the other cell's signals as noise and hence, with more active users, more cells have to decrease their rate to overcome the emerging interference.

VI. CONCLUDING REMARKS
In this work we have considered the input-erasure Gaussian channel. We have shown that with i.i.d. inputs, the inputand output-erasure [5] channels are equivalent. Focusing on the two-tap case, we have presented an alternative analysis to the one reported in [5]. In particular, in contrast to [5] where the rate expression involves a fixed-point equation, the new expression is given in the form of an infinite sum, which enables simple calculation of arbitrarily accurate lower bounds. Moreover, the analysis is based on simple properties of tridiagonal matrices and also holds for erasures with memory. An alternative simpler high-SNR rate power offset expression in the form of an infinite sum has also been presented, which contrasts to the one reported in [5] which involves a fixed-point equation. Numerical results have demonstrated the deleterious effects of increasing erasure rate and reveal the nature of the worst-case filter (coefficients with equal amplitudes) and that of the best-case filter (either coefficients is set to zero). The results have then been used to demonstrate the benefits of MCP over SCP schemes for a simple cellular uplink with shadowing fading or with user-activity model. Other settings that include independent shadowing to each BS, and more complex user-activity models, are currently being studied.

APPENDIX
We need to calculate Using (5) and defining the N × N matrix we can rewrite (26) as Straightforward calculations reveal that G N is given explicitly by e.g., for the special case of N = 3 we have It is observed that G N is a tri-diagonal matrix (due to the two-tap filter), and that an erasure of the nth input symbol, i.e., e n = 0, sets the nth row and the nth column of G N to zero. Hence, each erasure splits G N into two block-diagonal sub-matrices. The latter is easily explained by the following example. Assume N = 10 and an erasure realization e ′ = (1, 1, 0, 0, 1, 1, 1, 0, 1, 1). In this case we have where a is defined in (7), and c P h † 0 h 1 . Examining (31) it is evident that log det (I 10 + P G 10 ) = 2 log det (I 2 + PḠ 2 ) + log det (I 3 + PḠ 3 ) , (32) whereḠ n H † n+1 H n+1 is a tri-diagonal n × n Toeplitz matrix (equal to G n with no erasures). Turning to the general case log det (I N + P G N ) = N n=1 n(e ′ ) log det (I n + PḠ n ), (33) where n(e ′ ) is the number of n-length consecutive nonerasure sub-sequences in e ′ . Using (33), we can express the rate for any block size N as Next, we calculate det (I n + PḠ n ) ; n = 1, . . . , N , by recalling the fact that the determinant of any tri-diagonal n × n matrix V obeys the following recursive relation det V n = [V n ] n,n det V n−1 − [V n ] n,n−1 [V n ] n−1,n det V n−2 ; n ≥ 3 , (37) where V n−1 , V n−2 are the first two main principal submatrices of V n (composed of the first n − 1 and n − 2 rows and columns of V n , respectively). Applying the recursive formula to D n I n + PḠ n we get the following difference equation: det (D n ) = a det (D n−1 ) − b 2 det (D n−2 ) ; n ≥ 2 , (38) with initial conditions det (D 0 ) = 1 and det (D 1 ) = a, where a and b are defined in (7). A solution to a difference equation of this form is given by det (D n ) = ϕr n − φs n , where r and s are defined in (8). The initial condition are used to calculate ϕ and φ: Hence, R N can be bounded by (44) This is since the summands in (43) are positive, and by noticing that log det (D n ) ≤ nβ (for some positive β > 0). After some algebra we get that R − 2β(1 − q) N q − β(1 − q) N ((N + 1)q + 1)) ≤ R N ≤ R .