Source-linked AI summary
Broadcast Capacity Region of Two-Phase Bidirectional Relaying
Tobias J. Oechtering, Igor Bjelakovic, Clemens Schnurr, Holger Boche
TL;DR
The paper determines the broadcast capacity region for a two-phase bidirectional relay channel, addressing an unresolved general relay-channel capacity problem and spectral-efficiency loss. It uses a blowing-up technique to sharpen the converse, showing that the achievable region can exceed XOR-based rates and establishing a strong converse for maximum error.
Problem
The general relay-channel capacity problem remains unsolved, while existing approaches can suffer inherent spectral-efficiency loss.
Method
The paper uses the blowing-up technique to sharpen the converse for the broadcast phase.
Results
The paper presents the broadcast capacity region and proves a strong converse under the maximum error criterion; the achievable region is generally larger than the region achieved by XOR.
Takeaways & Limitations
XOR achieves the bidirectional broadcast capacity if and only if the maximizing input distribution equalizes I(X; Y1) and I(X; Y2).
Abstract
from arXiv · showhide
In a three-node network a half-duplex relay node enables bidirectional communication between two nodes with a spectral efficient two phase protocol. In the first phase, two nodes transmit their message to the relay node, which decodes the messages and broadcast a re-encoded composition in the second phase. In this work we determine the capacity region of the broadcast phase. In this scenario each receiving node has perfect information about the message that is intended for the other node. The resulting set of achievable rates of the two-phase bidirectional relaying includes the region which can be achieved by applying XOR on the decoded messages at the relay node. We also prove the strong converse for the maximum error probability and show that this implies that the $[\eps_1,\eps_2]$-capacity region defined with respect to the average error probability is constant for small values of error parameters $\eps_1$, $\eps_2$.
I. INTRODUCTION
The paper studies half-duplex, time-divided bidirectional relaying and derives the broadcast-phase capacity region using classical channel coding. It also establishes strong-converse and error-criterion results for the protocol.
- I. INTRODUCTION: Half-duplex operation separates relay communication into a multiple access phase and a succeeding broadcast phase.The MAC phase sends information to the relay, which forwards it during the BC phase.
- I. INTRODUCTION: Two-phase bidirectional relaying reduces the spectral-efficiency loss associated with orthogonal link resources.Bidirectional communication can be performed efficiently in two phases rather than assigning exclusive resources to each link.
- I. INTRODUCTION: The optimal broadcast coding strategy and capacity region are obtained using classical channel coding, with all rate pairs achieved by time-sharing.The auxiliary random variable need take only two values, and the result connects to Slepian-Wolf-based joint source and channel coding.
A. Two Phase Bidirectional Relay Channel
The two-phase model assumes an error-free MAC decoding outcome before the relay broadcasts both messages to receivers that already know the message intended for the other node. The section formulates the broadcast channel and states its capacity-region theorem.
- A. Two Phase Bidirectional Relay Channel: Nodes 1 and 2 send messages w1 and w2 to the relay in the MAC phase, after which the relay broadcasts to both destinations.The two phases are considered separately before optimizing their time division.
- B. Capacity Region of Multiple Access Phase: The MAC phase uses the classical multiple-access capacity region CMAC with a joint distribution built from an auxiliary variable U and conditional input distributions.The auxiliary variable has cardinality bounded by |U| ≤ 2.
- A. Two Phase Bidirectional Relay Channel: The overall two-phase error probability is at most the sum of the error probabilities of the MAC and broadcast phases.This motivates treating the MAC phase as error-free when rates lie within its capacity region and coding length is sufficient.
- A. Two Phase Bidirectional Relay Channel: Node 1 decodes w2 and node 2 decodes w1 because each receiver knows the message intended for the other node.The relay is assumed to have successfully decoded both messages in the MAC phase.
- II. CAPACITY REGION OF BROADCAST PHASE: The bidirectional broadcast capacity region CBC is defined through rate-pair achievability under the relay encoder and two receiver decoders.The theorem is proved through achievability, a maximum-error weak converse, and a cardinality-two auxiliary-variable argument.
A. Proof of Achievability
The achievability proof constructs independent relay codewords for message pairs and uses typical-set decoding. It first proves selected rate pairs achievable, then extends the result to the closure of their convex hull.
- A. Proof of Achievability: The proof extends fixed-distribution achievability to the closure of the convex hull, yielding the capacity region stated in Theorem 2.5.This establishes all points generated by time-sharing among the underlying rate pairs.
- A. Proof of Achievability: Independent codewords X^n(v) are generated for each message pair v = [w1, w2].To transmit a pair, the relay sends its corresponding codeword.
- A. Proof of Achievability: Typical-set decoding is used at the receiving nodes to decode the unknown source message from the relay transmission.The proof begins by characterizing the achievable rate pairs for a fixed input distribution.
3) Decoding:
The decoding analysis defines error events through typical-set membership and competing codewords, then bounds their averaged probabilities. For rates below the relevant mutual-information bounds, the average error probability vanishes, exponentially fast with an explicit margin.
- Error events: Each decoder errors if the transmitted codeword is absent from its typical set or an incorrect codeword is jointly typical.The incorrect-codeword event differs by receiving node because each node knows the other message.
- Error events: For uniformly distributed messages, the probability of error is averaged over all message pairs and codebooks.
- Achievability: When R→R_k ≤ I(X;Y_k) − 2ε, the averaged error probability tends to zero exponentially fast.The proof uses the law of large numbers and analyzes the competing-codeword term separately for the two receiving nodes.
- Error analysis: For distinct messages differing at one destination, the relevant decoding-distance terms are independent for each received sequence.
- Achievability: If R→R_k < I(X;Y_k) for k = 1, 2, the average probability of error becomes arbitrarily small as n grows.
5) Code Construction with arbitrary small maximum probability of error:
The construction extracts a structured subcode from an average-error code and remaps its message indices so that both receivers obtain uniformly small maximum error. The resulting rates approach every pair satisfying equation (2).
- Subcode selection: A subset of message pairs is selected so that each retained first-message index has many compatible second-message choices.The construction uses the set T and associated index sets to obtain a structured subcode.
- Subcode selection: The selected message pairs are remapped through one-to-one mappings into a product-form index set.
- Maximum-error guarantee: 8ε bounds the maximum error λ_k(w1,w2) for k = 1, 2 on the constructed subcode.
- Decoder construction: The new decoder mappings use the known message at each receiving node together with the original decoder output.
- Maximum-error guarantee: Codewords outside the selected index set cause an erasure decision and therefore add no decoding error because the encoder never transmits them.
- Conclusion: The constructed code approaches [R→R2, R→R1] as n →∞ and establishes achievability for every rate pair satisfying equation (2).
6) Convex hull:
The achievable rate region is extended from fixed input distributions to their convex hull by introducing an auxiliary variable and time-sharing. The argument also addresses the relation between average and maximum error regions.
- Region construction: For each input distribution p(x), R(p(x)) denotes the corresponding achievable rate set, and the overall region is formed from these sets.
- Time-sharing: Conditional mutual-information rate pairs associated with p(x|u) are achievable for every auxiliary-variable value u.
- Time-sharing: Convex combinations of achievable rate pairs are realized by time-sharing over the auxiliary variable U.
B. Proof of weak converse
The weak converse bounds message entropies using Fano’s inequality and single-letter mutual informations under an auxiliary-variable distribution. A cardinality reduction completes the capacity-region characterization and supports the stated error-criterion results.
- Setup: The converse considers codes whose maximum error probabilities λ_1^(n) and λ_2^(n) tend to zero.
- Entropy bounds: Fano’s inequality bounds the uncertainty of each destination’s unknown message given its received sequence and known message.
- Entropy bounds: The resulting entropy inequalities use independence, mutual information, the chain rule, positivity, and data processing.
- Single-letterization: Introducing U as a time index converts empirical per-coordinate distributions into a joint distribution q1(u)q2(x|u)p(y1,y2|x).
- Cardinality: Fenchel–Bunt’s theorem reduces the auxiliary-variable alphabet to |U| = 2 while preserving the relevant convexified rate region.
- Conclusion: The proof finishes the bidirectional broadcast capacity-region characterization, and CBC remains valid for average probability of error.
- Strong converse: The strong-converse argument is then introduced for maximum probability error and yields the stated small-error [ε1,ε2]-capacity conclusion.
III. SHARPER VERSIONS OF THE CONVERSE PART FOR THE BROADCAST PHASE
The section sharpens the converse for the bidirectional broadcast channel and establishes a strong converse under maximum error. It then extends the result to average error for sufficiently small error parameters.
- The authors derive a sharper converse for the bidirectional broadcast coding theorem.
- Theorem 3.3 states that the maximum-error capacity region equals the ordinary capacity region for all ε1, ε2 ∈ (0, 1).
- For sufficiently small ε1 and ε2, the average-error capacity region coincides with the ordinary capacity region.
- The proof uses decoding sets, entropy inequalities, and the blowing-up technique to convert a weak converse into a strong converse.The blowing-up technique is identified as the main tool, with a variant of Fano’s inequality used in the conversion.
- The strong converse means the maximum-error region cannot be a proper superset of the capacity region.
IV. DISCUSSION
The discussion compares the proposed broadcast coding strategy with XOR-based network coding. The proposed strategy can avoid the worst-receiver limitation and makes the two receivers’ input distributions separately optimizable.
- The proposed coding strategy gives each achievable rate dependence on its own channel transfer distribution rather than both channels jointly.
- XOR-based network coding is generally inferior because its broadcast rates are limited by the worst receiver.
- The broadcast coding strategy achieves the capacity of the bidirectional broadcast channel if and only if a maximizing input distribution equalizes I(X;Y1) and I(X;Y2).
A. Binary Symmetric Broadcast Channel
For the binary symmetric broadcast channel, uniform input is optimal, yielding a capacity region that includes the XOR-achievable region.
- For the binary symmetric broadcast channel, p1 and p2 are the relay-input complementation probabilities at the two outputs.
- A uniform input distribution maximizes the binary symmetric channel.
- The broadcast capacity region includes [0, 1 − max{H(p1), H(p2)}] × [0, 1 − max{H(p1), H(p2)}].
- The included region is achievable using XOR at the relay node.
B. Achievable Bidirectional Rate Region
The two-phase bidirectional relay achieves rates through time division between multiple-access and broadcast phases. Its region includes rates achievable by interference cancellation and network coding, including XOR-based decoding.
- Scope: The fixed two-phase strategy need not be optimal for the overall bidirectional relay channel.The caveat concerns the prior separation of communication into MAC and broadcast phases.
- Time division: The protocol divides n channel uses into MAC and BC phases using a time-division factor α.The phase lengths satisfy nMAC + nBC = n, with α governing the division as n grows.
- Achievability: Arbitrary small decoding error is achievable when the directional rate pairs satisfy the MAC and broadcast constraints.The constraints include nR2 ≤ min{nMAC R→2R, nBC R→R1}.
- Achievable region: RBRC is the achievable rate region formed by all rate pairs attainable with any α ∈ [0, 1].The region is collected in Proposition 4.1 for the two-phase bidirectional relay channel.
- Comparison: RBRC includes the regions achieved by interference cancellation and network coding, including XOR on the relay’s decoded messages.This follows because CBC is larger than the broadcast region obtained by those approaches.
- Binary example: For the binary example, Fig. 2 compares CMAC and CBC with RBRC and illustrates an optimal time division geometrically.The boundary construction uses an angle φ and the corresponding boundary rate pairs.
V. CONCLUSION
The paper determines the broadcast capacity region for a two-phase bidirectional relay channel with receivers knowing the other node’s message. It shows that the achievable region can exceed network-coding rates and establishes a strong converse for maximum error, yielding constancy under average error for small parameters.
- Contribution: The broadcast capacity region is characterized when each receiving node has perfect knowledge of the other node’s message.The result concerns the broadcast phase of the two-phase bidirectional relay channel.
- Rate region: The proposed achievable region is in general larger than the region obtained by applying network coding to decoded data.The coding theorem and weak converse are also extended to Gaussian channels with input power constraints.
- Converse: A strong converse is proved for the broadcast phase under the maximum error criterion.This establishes a converse result for the maximum probability of error.