CS Paper Radar

Capacity of a Mixed Multiple-Access Channel with Causal Observation

Xianwei Meng

cs.IT ·submitted 2026-09-18 07:01 UTC · v1

Abstract

We determine the capacity region of a mixed binary multiple-access channel whose receiver can choose how each observation is formed. Two ports reveal the sum modulo two of the transmitted symbols with retention probabilities $\pg>\pb$; their roles are interchanged by an unknown state that remains fixed during the block. With one observation per channel use, no transmitter feedback, and zero switching cost, the region is $R_1+R_2\le\pg$ for every fixed error threshold below one, and a strong converse holds. For error thresholds below one half, the largest open-loop sum rate is $(\pg+\pb)/2$, whereas a fixed port permits only $\pb$. A causal receiver attains the larger region by learning the state from erasure flags while using every channel use for data. A posterior port rule makes only finitely many incorrect selections almost surely, with a uniformly bounded expected number of mistakes. Exact random linear-code formulas and output-counting converses quantify the finite-block consequences. At blocklength 256 with $(\pg,\pb)=(0.9,0.4)$, independent numerical validation supports 214 message bits at a one-percent ensemble failure target, compared with 148 bits for the best open-loop allocation in the same code ensemble. The resulting 44.59\% increase is achieved with the same transmission and observation budgets. The analysis exhibits an explicit capacity gain from controlling the observation axis and separates that gain from information lost after a record has already been formed.

Closest papers

Nearest neighbours by meaning across the whole index.

Interference-Free Capacity of a Binary Interference Channel with Causal Observation

cs.IT ·2026-09-18 ·Xianwei Meng
similarity 0.83
Abstract

We determine the capacity region of a two-user binary interference channel with receiver-controlled observation and prove that causal port selection attains the interference-free limit. The physical--observation dual-axis formulation makes the observation kernel a design variable subject to explicit causal and resource constraints. For two equiprobable, initially unknown block states, matching converses and coding constructions give exact sum capacities of 1, $4/3$, and 2 bits per channel use for fixed-port, open-loop, and causal policies, respectively. These results hold for every fixed joint error threshold below $1/2$, under both average and maximal message error, with error averaged over the block state. Every receiver makes one observation per slot and switches ports at most once; the transmitters receive no feedback and the receivers do not cooperate. Causal observation thus doubles the optimal fixed-port sum capacity and exceeds the optimal open-loop sum capacity by 50\%. With independent erasures of retention probability $p$, the exact causal region is $[0,p]^2$. A finite-blocklength bound accounts jointly for state-identification pilots and coding redundancy. We also optimize observation policies for fixed codes: an exact finite-horizon solution reduces message error from 10.76\% to 7.52\%, and a second-order approximation bound controls optimization over continuous observation directions. Linear-array designs and coding experiments examine the corresponding training, reliability, and control costs. The capacity result identifies a setting in which observation design removes the entire interference penalty, with the gain established by a converse as well as an achievable construction.

0.30

Binary Deletion Channel Capacity to Within One Hundredth of a Bit

cs.IT ·2026-09-16 ·Dimitris Papailiopoulos
theorycode/datahighly cited similarity 0.68
Abstract · 122 pages. Source, exact certificate tables, and verification programs: https://github.com/anadim/binary-deletion-channel-capacity

The exact capacity of the binary deletion channel remains unknown despite decades of work on achievable rates and converse bounds. We establish a computer-assisted approximation whose error is below $0.0095$ bits per transmitted bit, uniformly over all deletion probabilities. The mean certified error bound, with uniform weighting of deletion probability, is below $0.006522$. The estimate is the midpoint of explicit lower and upper bounds. For the converse, a stationary-source reduction is combined with finite inequalities covering every allowed input configuration. Two constructions control the unobserved input beyond a finite window: one uses a common outside survivor sequence and bounds omitted deletion patterns, while the other cancels an entropy term to make outside probabilities enter linearly. For the lower bound, finite-state inputs combine output-entropy estimates with selected disjoint counts of compatible deletion masks; independent-run inputs retain additional uncertainty about output-run boundaries. Directed numerical checks establish the finite inequalities. An analytic comparison between deletion probabilities then extends the pointwise bounds over the entire parameter range. The lower endpoint supplies rates within $0.019$ bits of capacity in the asymptotic coding sense. We give the derivations, recorded computational costs, and complete numerical inputs and programs needed to verify the result.

0.61

The Asymptotic Capacity of the Grabbag Channel With and Without Feedback

cs.IT ·2026-11-18 ·Jun Chen, Yuta Sakai
theory similarity 0.68
Abstract

The grabbag channel models communication through a randomly mixed store. At each use, an input ball of one of $K$ colors is inserted into a bag containing $M$ balls, and one of the resulting $M+1$ balls is selected uniformly, observed, and removed. We show that, when $2\leq K\leq M+1$, both the capacity without feedback and the capacity with noiseless strictly causal output feedback are at most $9.77(K/(M+1))^{2/3}$, and that, when moreover $M+1\geq2^{22}$, both are at least an absolute constant times $(K/(M+1))^{2/3}$. Hence, both capacities are of order $(K/M)^{2/3}$, and of order $M^{-2/3}$ for every fixed $K$. The converse is a single bound on the information that a feedback code conveys in $n$ uses, valid for every initial state. For each initial state, it bounds the information in each output by the change of a potential of the posterior law of the state given the earlier outputs, defined through noisy cube roots of the color counts. A budget on the true state bounds the total cost of the uses in which the inserted color is rare. The lower bound uses a statistic of two output histograms whose expectation does not depend on the unknown initial composition, an outer code, and words with prescribed compositions. We also show that the channel is indecomposable and relate its capacities to the finite-state-channel information formulas.

0.35

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.66
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

Spatially Coupled MacKay-Neal Codes on Symmetric Markov Noise: A Reduction to BMS Channels

cs.IT ·2026-09-22 ·Kenta Kasai
theory similarity 0.65
Abstract · 15 pages

We prove a capacity criterion for fixed-degree spatially coupled MacKay--Neal codes on additive symmetric Markov noise. The noise bit flips with probability $p$, so the channel has one parameter and capacity $1-h_2(p)$. For every integer $\ell\geq4$ with $3/\ell<1-h_2(p)$, matched finite-window BCJR and sum-product decoding admit code sequences, possibly depending on $p$, with actual rate tending to $3/\ell$ and vanishing average information-bit error. The proof parallels the GEC-to-BEC argument: a conditional-entropy correction transfers BMS fixed-point positivity to the channel with memory. The correction also covers a capacity deficit of the effective BMS channel. A two-state posterior contraction supplies the additional derivative bound needed for threshold saturation. The result uses the cited BMS positivity theorem, with an analytic proof for $\ell\geq33$ and exact interval certificates for $4\leq\ell\leq32$.

0.17

MacKay-Neal Codes Achieve Capacity under MAP Decoding

cs.IT ·2026-10-07 ·Kenta Kasai
theory similarity 0.64
Abstract · 22 pages

Statistical-mechanical analyses predict that MacKay-Neal codes can achieve channel capacity at fixed degrees. We prove this prediction for the uncoupled $(\ell,3,3)$ MN socket ensemble for every fixed integer $\ell\ge4$. For each binary-input memoryless symmetric channel of capacity strictly greater than $3/\ell$, the ensemble-average block error probability under maximum a posteriori (MAP) decoding is $O(\log N/N)$, where $N$ is the transmitted blocklength. The actual transmitted rate converges to $3/\ell$. The result includes both punctured and transmitted variables and does not condition the sparse square matrix on invertibility. The proof establishes an entropy inequality for six bits subject to even parity by an analytic argument that reduces the domain by symmetry, restricts its interior stationary points, where both partial derivatives vanish, to the diagonal, and controls the resulting scalar functions by explicit polynomial bounds. Exact configuration counts then bound the conditional entropy on the binary symmetric channel. A standard comparison by mutual information extends the entropy bound to general symmetric channels; independent output erasures and a minimum-distance estimate for the transmitted code yield the bit and block error bounds.

0.42

Binary code rate bounds via classical--quantum channels

cs.IT math.COquant-ph ·2026-08-10 ·Omar Alrabiah, Venkatesan Guruswami
publishedtheoryhighly cited similarity 0.64
Abstract · 77 pages, 4 figures

We derive the four principal asymptotic rate-distance tradeoffs for binary codes---Plotkin, Elias--Bassalygo, and the two McEliece--Rodemich--Rumsey--Welch (MRRW) bounds---from one theorem, the ``pretty good criterion.'' If the bit error rate under the pretty good measurement (PGM)---the quantum analog of posterior sampling---of a binary-input output-symmetric classical--quantum (cq) channel lies below $δ$, then every length-$n$ binary code, linear or nonlinear, of relative distance $δ$ has rate at most the channel's capacity, up to an $O(n^{-1/2})$ correction. Rate--distance bounds thereby reduce to a channel design problem, wherein the task is to minimize channel capacity subject to the posterior bit error rate constraint. Via the pretty good criterion, the binary erasure channel (BEC) yields Plotkin, the binary symmetric channel (BSC) yields Elias--Bassalygo, the pure-state channel (PSC) yields the first MRRW bound, and a masked PSC yields the second MRRW bound exactly. This framework is then instantiated with new channels to improve upon the MRRW bounds. Specifically, the mixed-qubit channel (MQC), a mixed-state version of PSC, strictly improves the first MRRW bound at every $0 < δ< \frac{1}{2}$, while the masked mixed-qubit channel (2MQC) strictly improves the second MRRW bound throughout the same interval.

0.68

A Tight Second-Order Converse Bound for Variable-Length Feedback Codes

cs.IT ·2026-09-10 ·Recep Can Yavas
similarity 0.63
Abstract · 26 pages, submitted to Information Theory Transactions

We study variable-length feedback (VLF) codes over a discrete memoryless channel under average decoding-time and error-probability constraints. In the non-vanishing error probability regime, Polyanskiy, Poor, and Verdú (2011) derive achievability and converse bounds on the logarithm of the maximum achievable codebook size. These bounds establish the $ε$-capacity but leave an order-$\log N$ gap in the second-order expansion, where $N$ is the average decoding time. Yavas and Tan (2025) improve the coefficient of $\log N$ in the achievability bound from $-1$ to $-\frac{C}{C_1}$, where $C$ is the channel capacity and $C_1$ is the largest Kullback--Leibler divergence between two conditional output distributions. We derive a converse with the same coefficient, establishing the second-order fundamental limit for every positive-capacity discrete memoryless channel with finite $C_1$. The result also covers the moderate-deviations and error-exponent regimes, including polynomially decaying error probabilities. The converse uses Rényi entropy and the extrinsic Jensen--Shannon divergence. We also derive necessary properties of asymptotically optimal VLF codes. First-order-optimal codes must have an early-stopping branch, and second-order-optimal codes must additionally exhibit communication and confirmation behavior. Finally, for the binary erasure channel, we determine the exact minimum expected decoding time for every message-set size and admissible error probability.

0.11