Coded Water-Filling for Multi-User Interference Cancellation

In a single-user scenario, the capacity loss associated with fixed-length codes is directly proportional to the square root of the code length [1]. A finite-length analysis of the relationship between the maximum coding rate and error probability in a point-to-point communication model with a fixed code length is established in [2]. The maximum number of information bits for a fixed-length code can be approximated by:

where $M^{*}(n,\epsilon)$ is the maximum number of codewords with a code length of $n$ and an error probability of $\epsilon$, $C$ represents the channel capacity, $V$ is the channel dispersion, and $Q(x)=\int_{x}^{\infty}\frac{1}{\sqrt{2\pi}}e^{-\frac{t^{2}}{2}}dt$. Shannon demonstrated that while feedback does not augment the capacity of point-to-point memoryless channels [3], it can simplify the coding scheme, as noted in [4] and [5]. Variable-length feedback codes, however, can flexibly adjust the code length according to channel noise power, thereby minimizing the finite-length capacity loss. In contrast, fixed-length codes must maintain a codeword length that ensures successful decoding under most channel noise realizations. However, variable-length feedback codes typically require the noiseless feedback about the received message to derive the noise of the forward channel. This can be both demanding and impractical. Therefore, stop-feedback codes are introduced to reduce the amount of feedback to one bit, and hence received considerable attention due to their simpler implementation. In variable-length stop-feedback (VLSF) codes, the receiver signals an acknowledgment to the transmitter by sending a single-bit ACK once it has gathered sufficient information to decode the message. Despite the minimal feedback overhead required, [2] and [6] demonstrate that VLSF codes can mitigate the finite-length rate loss efficiently. The finite-length achievable coding rate for a VLSF code can be approximated by:

where $0<\epsilon<1$, and $M_{f}^{*}(\ell,\epsilon)$ is the maximum number of codewords with an average code length of $\ell$ and an error probability of $\epsilon$. It is evident that the capacity is enhanced by a factor of $\frac{1}{1-\epsilon}$, and the gap to capacity narrows down from $O(\sqrt{\ell})$ to $O(\log\ell)$. This underscores the efficacy of VLSF codes in optimizing capacity under finite-length constraints.

The findings obtained in the single-user scenario are extended to the multiple access channel (MAC). Under the discrete memoryless two-user MAC model, [7] provides the achievability bounds for the joint decoding performance of VLSF codes by considering the joint mutual information $i(X_{1},X_{2};Y)$ under joint decoding. This means that users stop transmission simultaneously once the receiver has the capability to jointly decode messages from both users. Moreover, the authors also present the achievability bounds under successive interference cancellation (SIC) decoding. Here, the receiver first decodes the message of one user, then cancels the inference from the already-decoded user before decoding the other message. Although joint decoding significantly outperforms SIC decoding in terms of performance, the complexity of the former grows exponentially as the number of users increases. The results in [7] are extended to the Gaussian MAC with power constraints [8]. The researchers developed techniques to obtain achievability and converse bounds for Gaussian channels, and provided the second-order asymptotic term for the Gaussian MAC. Inspired by concepts related to composite channels [9], Trillingsgaard et. al. studied discrete memoryless broadcast channels with stop feedback for two users [10] and for $K$ users [11] with a common message transmission. Although users in [11] have distinct stopping times, the interference cancellation benefits of early termination are not manifested, as inter-user interference is not taken into account.

In an effort to minimize the number of decoding attempts, feedback is made available only at $L$ predetermined decoding times. In [12], Williamson et. al. numerically optimized the value of the decoding time $L$, and employed punctured convolutional codes and a Viterbi decoding algorithm to provide a practical scheme. R. C. Yavas et. al.. [13] devised an integer programming procedure aimed at minimizing the upper bound of the average block length across all decoding times, subject to constraints imposed by the average error probability and the integer condition. Recently, in [14], R. C. Yavas et. al. compiled an overview of the findings on VSLF codes, examining the achievability bounds and converse bounds of VSLF codes in point-to-point, multiple access, and random access communication scenarios.

The analysis of Gaussian channel capacity was first undertaken by Shannon in 1948 [15], a seminal work that laid the groundwork for modern information theory. Building upon this, the water-filling solution, a pivotal technique for maximizing the capacity of parallel Gaussian channels, was introduced in [16]. This approach has since been refined and adapted to accommodate the complexities of time-continuous Gaussian channels, as evidenced by the comprehensive studies in [17, 18, 19, 20, 21]. The classical water-filling method was introduced in detail in [22], this method ingeniously parallels the allocation of power across channels to the distribution of water in a series of containers. The water-filling technique has been successfully applied to a wide range of communication scenarios, as showcased in [23], [24], and [25]. Notably, its utility extends to optimizing objectives beyond capacity maximization, such as the minimization of bit-error rate (BER) across a set of parallel channels, as explored in [26].

In [27], the authors studied a discrete-time fading channel model for a single-user scenario. They investigated the capacity of this fading channel under the constraint of average transmission power. The signal-to-noise ratio (SNR) fluctuations induced by random channel fading coefficients resemble those of parallel Gaussian channels. Recognizing the complexity involved in the computation of the optimal water-filling method, the authors of [28] observed that by “allocating zero power to channels that would receive zero power under precise water-filling and a constant power in the remaining subchannels”, the optimal solution can be approximated. An approximate water-filling method, incorporating constant power allocation, is proposed in [29]. After deriving the lower bound of the dual optimization problem, the author proved that the approximate water-filling scheme is close to optimal. A similar result is shown in [30], as the signal-to-noise ratio approaches infinity, the water-filling power allocation function converges pointwise to a function that allocates fixed power to all non-zero channel gain states. In [31], the water-filling problem is extended to the MAC scenario. The optimal strategy is again water-filling, albeit a condition that transmission privileges are granted to the user with the most favorable channel conditions. This adaptation ensures that the benefits of water-filling are maximized while mitigating the effects of interference among multiple users.

The exploration of water-filling problems has been extended to encompass the Multiple-Input Multiple-Output (MIMO) scenario. In the Single-Input Single-Output (SISO) systems, traditional water-filling techniques offer a closed-form solution to the optimal transmission problem. In contrast, the MIMO variant of the water-filling problem often presents a more intricate challenge, leading to nonconvex problem formulations that are notably harder to solve. [32] broadens the scope of water-filling research by considering various optimization criteria, including the mean square error (MSE), SNR, and BER, demonstrating the versatility of the water-filling approach across different design metrics. [33] further demonstrates a system that aims at minimizing the MSE matrix determinant in MIMO configurations. The iterative water-filling algorithm, as presented in [34], has become a prevalent algorithm for tackling power allocation optimization in MIMO broadcast channels [35] [36]. For a sufficiently large number of users, the channel capacity achieved with a water-filling scheme converges to a constant value, irrespective of the inherent randomness of the MIMO channel [37]. Given the widespread utility of the water-filling method, the design and optimization of water-filling algorithms have become important research topics. Works such as [38], [39], and [40] continue to enhance the efficiency and performance of water-filling techniques.

Water-filling is also extended to a variety of communication scenarios, showcasing its adaptability and significance across diverse contexts. In [41], the authors tackle the water-filling problem under a fading channel model with multiple users in the presence of crosstalk. They propose a modified iterative water-filling algorithm that incorporates an updated crosstalk term. The work of [42] studies a scenario where a specific user communicates through dual base stations. The authors derive a closed-form solution to the optimal power allocation problem in this complex setting, upon which they propose a novel joint power allocation scheme. [43] examines a MAC with time-varying Gaussian fading for multiple users, where the channel remains static within each unit of time. Departing from the conventional constraint of constant total power, the optimization problem is redefined to focus on a scheduling strategy that minimizes energy consumption. Building upon this novel constraint, the authors propose an iterative dynamic water-filling algorithm, which dynamically adjusts power allocation to optimize energy efficiency in time-varying channels. The water-filling method can be combined with the game theory, as demonstrated in [44]. Here, the water-filling power allocation problem is characterized as a game, with power allocation corresponding to each user’s strategic control of power to maximize their individual code rates. The authors prove that, within this game model, the water-filling game reaches a unique Nash equilibrium.

In this paper, we study the system-level advantages provided by early termination and power allocation strategy for multiple users distributed across multiple cells. Our innovation lies in the fact that, unlike traditional multi-user variable-length codes where all users stop simultaneously, we consider varying stopping times for different users. Once a user stops transmission, interference cancellation can further enhance the SINR for other users, thereby increasing the system throughput. Regarding power allocation, we find that within a multi-user framework, each user should adopt a more assertive power allocation strategy. This entails elevating the water-filling threshold relative to a single-user environment, therefore minimizing the interference to other users by transmissions conducted at low SNR levels.

Our main contributions and findings are summarized as follows:

1. 1.

   Given that users are distributed across distinct cells, implementing joint decoding or SIC is not feasible. Consequently, users within every cell treat messages originating from other cells as interference. We prove the advantages of variable-length feedback codes within this context. These codes not only mitigate the finite-length loss, scaling it down from $O(\sqrt{\ell})$ to $O(\log\ell)$, as observed in single-user scenarios, but also introduce additional capacity enhancements. The early termination of transmission coupled with interference cancellation contributes to boosting the overall system throughput, underscoring the significant gains on the system level.

2. 2.

   We develop a multi-user queuing model. Within this scenario, during periods when all cells are experiencing congestion, interference reaches its peak level. Under such circumstances, the early termination of transmissions does not facilitate interference cancellation, but only obtains the feedback gain. Conversely, when the queue exhibits sufficient sparsity, both interference cancellation gain and feedback gain can be obtained. Our findings highlight that throughput enhancements is maximized when user density falls within a moderate range. This reveals the interplay between user density, interference management, and system throughput in multi-user scenarios.

3. 3.

   The intrinsic gain from early stopping fundamentally stems from the disparity in stopping times among users. In fading channel conditions, even when all users transmit the same number of bits at identical power levels, variations in channel fading coefficients result in different perceived SNRs, leading to varying decoding times. We also demonstrate under fading channel scenarios that early stopping concurrently yields both feedback and interference cancellation gains. This shows the robustness of coded water-filling approach.

4. 4.

   Finally, we address power allocation in fast fading channel. In a MAC scenario, transmission privileges are granted to the user with the most favorable channel conditions. This requires every user to have knowledge of all other users’ channel fading coefficients. However, achieving this in a multi-cell environment is impractical due to the excessive channel state information exchange across cells. To circumvent this, we formulate an optimization model where users can independently determine their power allocation solely based on their own channel fading coefficients. Our findings reveal that, by taking into account interference cancellation among multiple users, elevating the power allocation threshold contributes to interference reduction, therefore enhancing the overall system capacity.

The remainder of this paper is organized as follows. Section II revisits the concepts of variable-length feedback codes and water-filling solutions, providing a comprehensive overview for both single-user environments and MAC. Section III introduces a multi-cell VLSF model, illustrating the dual benefits of feedback gain and interference cancellation. We further extend this model to a queuing context. In Section IV, we provide robust evidence that in fading channel conditions, the gains derived from feedback and interference cancellation remain steadfast, even when all users share symmetric characteristics. Section V introduces an innovative water-filling methodology specifically designed for multi-user scenarios, where power allocation decisions are based exclusively on each user’s individual channel fading coefficients. Finally, Section VI summarizes the key findings of our study.

In this paper, we consider memoryless channels characterized by input and output alphabets $\mathcal{A}$ and $\mathcal{B}$, respectively. $X=(X_{1},\dots,X_{n},\dots)$ and $\bar{X}=(\bar{X}_{1},\dots,\bar{X}_{n},\dots)$ denote the true and false codewords, both of which are independent and identically distributed. $Y=(Y_{1},\dots,Y_{n},\dots)$ represents the channel output. Given that the codeword length is variable, the transmission and reception sequences may extend to infinite lengths, accommodating the flexibility inherent in variable-length coding schemes.

The finite length achievability coding rate for a VLSF code can be approximated by:

What’s more, a general achievability bound of single user model is proposed by [6]

where $\bar{\tau}=\inf\{n\geq 0:i(\bar{X}^{n};Y^{n})\geq\gamma\}$, $\tau=\inf\{n\geq 0:i(X^{n};Y^{n})\geq\gamma\}$ and $i(x^{n};y^{n})=log\frac{dP_{Y^{n}|X^{n}}(y^{n}|x^{n})}{dP_{Y^{n}}(y^{n})}$.

In [22], the Lagrange multiplier method was used to solve the optimization problem to maximize the mutual information for $S$ parallel Gaussian channels: $Y_{s}=X_{s}+Z_{s}$, $s=1,\dots,S$ with $Z_{s}\sim\mathcal{N}(0,N_{s})$ and $\mathop{\sum}_{s=1}^{S}X_{s}^{2}\leq P$, then the maximum capacity and the optimal power allocation are

where $v$ satisfies $\sum(v-N_{s})^{+}=P$.

[27] considers a discrete-time fading channel model for single user:

where $t$ is the discrete-time index, $X_{t}$ and $Y_{t}$ are the input and output signals respectively, $Z_{t}$ is the additive white Gaussian noise with distribution $\mathcal{CN}(0,N)$, indicating that its real and imaginary components are independent and identically distributed (i.i.d.) Gaussian random variables with zero mean and variance $N/2$ each. The time-varying channel fading coefficient is represented by $h_{t}$. Under the assumption that $h_{t}$ is perfectly known to both the transmitter and the receiver, and with the noise power normalized to $N=1$, the received signal-to-noise ratio (SNR) at any given time $t$ is calculated as $\gamma_{t}=|h_{t}|^{2}$.

By viewing the SNR fluctuations induced by random channel fading coefficients as a parallel Gaussian channel, the maximum capacity is calculated as

Where $P$ signifies the average power constraint, $P(\gamma)$ represents the power allocated at a given received fading gain $\gamma$, and $p(\gamma)$ denotes the probability distribution of the received fading gain. The authors substantiated both the achievability and converse components of the coding theorem by leveraging the finite division of channel fading statistics. The power allocation strategy aimed at maximizing the expression (12) is shown as follows:

where $\lambda_{0}$ is a certain threshold. Substituting (13) into (12), we obtain $\lambda_{0}$ satisfies

and the channel capacity is

Since the calculation of the optimal water-filling method is complicated, an approximate water-filling method with constant power allocation is proposed in [29]. Using the lower bound of the dual optimization problem, the authors prove that the following constant power allocation is very close to the optimal solution:

if not too few subchannels are used: $\min\limits_{\gamma}\{P(\gamma)+\frac{1}{\gamma}\}=P_{0}+\min\limits_{\gamma}\{\frac{1}{\gamma}\}$. They also give a low complexity algorithm for realizing the smallest duality gap to optimal solution. And simulation shows that the approximate water-filling method is very close to the optimal water-filling method.

In [31], water-filling was extend to MAC scenario

The power constraint is that each user has an average power of $P$ as

where $\gamma_{k}$ is the received fading gain of user-$k$, $P_{k}(\gamma_{1},\dots,\gamma_{K})$ is the allocated power of user-$k$.

The objective is to maximize the sum capacities

The power allocation strategy of user-$k$ for maximizing the sum capacities is as follows:

where $\lambda_{k}$ is the threshold of user-$k$. Assuming symmetry among the users, we have $\lambda_{i}=\lambda_{j}$. The condition $\gamma_{k}>\gamma_{j},\forall j\neq k$ signifies that, at any given instant, the exclusive entity permitted to transmit is the user boasting the highest instantaneous power. Meanwhile, all other users are mandated to maintain silence, awaiting their turn until one among them ascends to the position of possessing the greatest power.