CS Paper Radar

Rate Optimal Streaming Codes Under an Extended Delay Profile for Three-Node Relay Networks

Ke Wang, Wenjie Ma, Zhipeng Li, Yaqiang Zhang

cs.IT ·submitted 2026-11-13 13:06 UTC · v1
theory

Abstract

We study streaming codes for a three-node relay network with burst lengths $b_1,b_2$ and an end-to-end decoding delay $T$. Let $u=\max\{b_1,b_2\}$ and $v=\min\{b_1,b_2\}$, and write $T-v=pu+q$, where $T\ge u+v$ and $0\le q<u$. We develop two binary constructions, SR and SR-2, using extended delay profiles that allow the relay to forward causally invertible combinations of current and past source symbols. The SR construction attains the non-adaptive rate upper bound whenever \[ \frac{T-u-v}{2u-v}\le\left\lfloor\frac{T-u-v}{u}\right\rfloor. \] SR-2 enlarges this range under the sufficient condition \[ q(v-q)\le(p-1)u(u-v). \] These constructions complement the known divisibility and large-delay regimes. We also establish two limitations of systematic ordinary coordinate forwarding. First, it cannot attain the rate upper bound when $0<T-u-v<v$. Second, for equal burst lengths $b$, it attains the bound if and only if $b\mid(T-2b)$; a quantitative upper bound gives a strictly positive rate gap in every nondivisible case. These converses allow nonlinear components and predetermined time variation within the stated ordinary-forwarding architecture. Existing adaptive schemes for equal bursts approach the same rate upper bound asymptotically using time-varying convolutional codes and lie outside the non-adaptive setting considered here.

Comment
27 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Can Quantum Entanglement Increase the Capacity of a Classical Relay Channel?

cs.IT quant-ph ·2026-10-18 ·Elsa Mizrahi, Uzi Pereg
theory similarity 0.62
Abstract

We show positive and negative results on classical relay channels with entanglement assistance, revealing a sharp contrast between strictly causal and causal relay encoding. First, we consider van der Meulen's setting of a unit-delay relay, with strictly causal encoding. We show that the standard cutset upper bound continues to hold with entanglement assistance, and deduce that entanglement does not increase the capacity for several classes of relay channels. Second, we consider a zero-delay relay, where the encoding is causal. We present an example in which entanglement enables rates that exceed the cutset upper bound by at least 12.5%. Namely, entanglement shared between the source and relay significantly increases the capacity of a classical zero-delay relay channel.

0.14

An Improved Upper Bound on the Capacity of the Primitive Diamond Relay Channel

cs.IT ·2026-10-08 ·Deniz Gündüz, Yanxiao Liu, Yi Liu
theory similarity 0.58
Abstract

We study the capacity of the primitive diamond relay channel and derive an improved upper bound compared with existing upper bounds by employing the Csiszár--Körner--Marton sum identity and Gallager-type identification. For Gaussian primitive diamond relay channels, we show that our proposed bound coincides with the existing strengthened Gaussian upper bound of Wu, Özgür, Peleg, and Shamai. For discrete memoryless channels, our bound can be strictly tighter than both the cut-set bound and the existing upper bound, and we assess the improvement using different channel instances, together with a decode--forward/compress--forward time-sharing inner bound.

0.22

The Capacity of the Relay Channel

cs.IT ·2026-09-14 ·Jonathan Ponniah
similarity 0.55
Abstract

The capacity of the relay channel is characterized by three schemes: decode-forward, coordinated compress-forward, and uncoordinated compress-forward. The proof relies entirely on properties of typical sequences.

0.30

Counterexample to a Proposed Capacity Characterization of the Relay Channel

cs.IT ·2026-09-16 ·Chun Hei Michael Shiu
similarity 0.55
Abstract · 10 pages, 2 figures

We present a counterexample to the relay channel capacity characterization proposed in a recent work, which is based on properties of typical sequences. The counterexample uses a binary relay channel with a noiseless source-destination component and binary symmetric relay links. An achievable scheme exceeds the proposed capacity characterization, thereby disproving the characterization of the capacity for general relay channels. We highlight that the counterexample is obtained with the assistance of ChatGPT-6 Astra and the proofs are simplified with human effort.

0.17

Evict Early, Decode Efficiently: Lightweight Decoding Strategies for Low-Delay Sliding Window RLNC

cs.NI ·2026-10-20 ·Foteini Karetsi, Evangelos Papapetrou
similarity 0.54
Abstract · 14 pages, 7 figures

Random Linear Network Coding (RLNC), and in particular Sliding Window RLNC (SW-RLNC), is a promising approach for reliable, low-latency communication in dynamic environments such as 6G and non-terrestrial networks. While prior work has largely focused on encoder-side parameter tuning, such as the code rate and coding window size, decoder-side design remains comparatively underexplored despite its direct impact on end-to-end performance. This paper addresses decoding window management, namely the policies governing window-boundary updates, removal of obsolete packets, and delivery of recovered packets to upper layers, and shows that these policies critically shape the trade-off between computational complexity and decoding performance, particularly in-order delivery delay. We derive sufficient conditions under which packets can be safely removed from the decoding window without compromising decodability or violating in-order delivery guarantees, and, building on these conditions, propose two lightweight decoding window management schemes. Through extensive simulation-based evaluation across a range of channel conditions and code rates, we show that both schemes preserve decoding efficiency while substantially reducing decoding complexity, and that one additionally achieves a marked reduction in in-order delivery delay. These results establish decoding window management as a key design dimension for practical SW-RLNC systems.

0.27

Rates and Nearly-Lossless State over a Multi-Access Channel with Causal State Information

cs.IT ·2026-10-30 ·Amos Lapidoth, Baohua Ni
similarity 0.54
Abstract · 31 pages, 2 figures

The problem of transmitting both data and state over a memoryless state-dependent multi-access channel with causal state information is addressed. The state comprises three independent components: a common component, which is revealed to both en- coders, and two private components, each of which is revealed to a different encoder. The data are to be recovered with arbitrarily-small probability of error, and the state sequence with arbitrarily-small symbol-error rate. Under the assumption that the capacity region in the absence of a state recon- struction constraint is nonempty, the capacity region is derived and is shown to be achievable using a Block-Markov coding scheme employing binning and superposition coding.

0.23

Second-Order Asymptotics for the Gaussian MAC on the Relative Interior of the Sum-Rate Face

cs.IT ·2026-09-16 ·Vincent Y. F. Tan
similarity 0.53
Abstract · 37 pages; 9 figures

We completely characterize the second-order coding rate region of the two-user Gaussian multiple-access channel at points in the relative interior of the sum-rate face, under maximal per-codeword power constraints. For any fixed average error probability $0 < \varepsilon < 1/2$, a nontrivial mixture of power splits reduces the sum-rate dispersion and strictly improves upon standard inner bounds based on a constant power split. Thus, a constant power split, although sufficient to attain the first-order capacity region, is insufficient for second-order optimality in this regime. Our achievability proof builds on the constant composition and coded time-sharing framework of Scarlett, Martinez, and Guillén i Fàbregas, with an optimization over admissible power splits. A matching second-order converse establishes the optimality of the resulting coded time-sharing strategy.

0.44

Concatenation Locality under Successive Adjacent Transpositions

cs.IT ·2026-11-01 ·Adelin Ataba, Aryeh Lev Zabokritskiy
theory similarity 0.53
Abstract · 32 pages

We study codes correcting up to $t\geq1$ successive adjacent transpositions, using block concatenation to support blockwise encoding and decoding. A fixed set $P$ of words of length $b$ over a $q$-symbol alphabet generates, for every $m$, the length-$mb$ code of all concatenations of $m$ words from $P$. For our explicit constructions, the prepared encoder and decoder depend only on the block parameters and are reused at every concatenation length. We first prove that correction at every concatenation length is certified by a single finite test at $2t+1$ blocks, and this test is tight over a $q$-symbol alphabet exactly when $\binom q2\geq2t$. For binary words and $b\geq2t+1$, we give an explicit construction with total redundancy at most $mt\log_2 b+O_t(m)$, matching the optimal per-block redundancy $t\log_2 b+O_t(1)$ among block sets correcting at every concatenation length. Among all binary $t$-correcting codes of length $mb$, the optimal total redundancy is $t\log_2(mb)+O_t(1)$. Using all concatenations of one block set makes our total redundancy grow linearly in $m$ and buys independent block encoding, with one encoder and decoder at every length. The construction encodes and decodes in time linear in $mb$ for fixed $b,t$, and recovers the $j$-th source block from the first $jb$ received symbols. We also prove that, whenever the length-$mb$ code corrects $t$ transpositions, the $j$-th source block is determined within $2tb$ received symbols beyond position $jb$, and that explicit binary block sets with rates tending to one as $b$ grows with $t$ fixed attain this bound in the worst case. Finally, we prove that every ordinary correcting code contains a constant fraction of its words whose arbitrary concatenations retain correction, for fixed $q,t$.

0.28