Abstract
We obtain a new upper bound on the capacity of a class of discrete memoryless relay channels. For this class of relay channels, the relay observes an i.i.d. sequence $T$, which is independent of the channel input $X$. The channel is described by a set of probability transition functions $p(y|x,t)$ for all $(x,t,y)\in \mathcal{X}\times \mathcal{T}\times \mathcal{Y}$. Furthermore, a noiseless link of finite capacity $R_{0}$ exists from the relay to the receiver. Although the capacity for these channels is not known in general, the capacity of a subclass of these channels, namely when $T=g(X,Y)$, for some deterministic function $g$, was obtained in [1] and it was shown to be equal to the cut-set bound. Another instance where the capacity was obtained was in [2], where the channel output $Y$ can be written as $Y=X\oplus Z$, where $\oplus$ denotes modulo-$m$ addition, $Z$ is independent of $X$, $|\mathcal{X}|=|\mathcal{Y}|=m$, and $T$ is some stochastic function of $Z$. The compress-and-forward (CAF) achievability scheme [3] was shown to be capacity achieving in both cases. Using our upper bound we recover the capacity results of [1] and [2]. We also obtain the capacity of a class of channels which does not fall into either of the classes studied in [1] and [2]. For this class of channels, CAF scheme is shown to be optimal but capacity is strictly less than the cut-set bound for certain values of $R_{0}$. We also evaluate our outer bound for a particular relay channel with binary multiplicative states and binary additive noise for which the channel is given as $Y=TX+N$. We show that our upper bound is strictly better than the cut-set upper bound for certain values of $R_{0}$ but it lies strictly above the rates yielded by the CAF achievability scheme.
Introduction
In information theory, determining the capacity—the maximum possible data rate—of a relay channel remains a fundamental challenge. This paper focuses on a primitive relay channel, a simplified model where the relay does not transmit back into the main channel. Instead, it observes the channel state or environment ($T$) and sends "hints" to the receiver over a separate noiseless digital link with a fixed capacity $R_0$.
Historically, the cut-set bound has served as the standard theoretical ceiling for these channels. However, this bound is often "loose," suggesting achievable rates higher than what is physically possible. The core issue is that the cut-set bound does not fully account for the constraint that the relay can only transmit information derived from its specific observations ($T$), especially when those observations are independent of the transmitter's input ($X$).
Methodology
The authors derive a tighter upper bound by applying Fano’s inequality and identifying specific Markov chain relationships within the channel model. The mathematical innovation lies in introducing an auxiliary random variable, $V$, representing the compressed information the relay sends over the $R_0$ link. Unlike the standard cut-set bound, which simply adds $R_0$ to the direct transmission rate, this new bound ($UB$) is constrained by the mutual information between the relay's observation and this auxiliary variable:
$$UB = \sup \min\{I(X, V; Y), I(X; Y|T)\}$$ subject to the constraint: $I(T; V) \leq R_0$.
This approach incorporates the "Observation Constraint": the relay is limited not just by the capacity of its link ($R_0$), but by the correlation between its observations and the channel output.
Key Results and Insights
The proposed bound successfully recovers known capacity results for semi-deterministic and modulo-additive relay channels, demonstrating its robustness. More importantly, for several channel classes, it provides a strictly tighter limit than the traditional cut-set bound.
For example, in a relay channel with binary multiplicative states and additive noise ($Y=TX+N$), the new upper bound is shown to be significantly lower than the cut-set bound as $R_0$ increases. While it remains above the rates achieved by the standard Compress-and-Forward (CAF) scheme, it narrows the gap between theory and practice.
Key findings include:
- Validation of Conjectures: The paper formally proves a 1983 conjecture by Ahlswede and Han regarding state-dependent channels with rate-limited side information.
- Optimality of CAF: For a new class of channels where the state is independent of the input, the authors prove that the CAF strategy is actually optimal, even when it falls short of the cut-set bound.
Conclusion
This work provides a more accurate theoretical ceiling for primitive relay channels by accounting for the relay's observational limits. While the new bound is a significant advancement, a gap still exists between this upper bound and achievable rates in certain complex scenarios, such as multiplicative state channels. Future research may focus on developing more sophisticated relaying strategies to reach this new bound or further refining the mathematical ceiling to close the remaining gap.
Summary updated