CS Paper Radar

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

Amos Lapidoth, Baohua Ni

cs.IT ·submitted 2026-10-30 15:14 UTC · v1

Abstract

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.

Comment
31 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Capacity of a Mixed Multiple-Access Channel with Causal Observation

cs.IT ·2026-09-18 ·Xianwei Meng
similarity 0.66
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.

0.23

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

cs.IT ·2026-09-18 ·Xianwei Meng
similarity 0.66
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

Joint Identification, Transmission, and Sensing over State-Dependent Channels with Noiseless Feedback

cs.IT ·2026-10-14 ·Vida Gholamian, Marcel A. Mross, Roberto Ferrara, Eduard A. Jorswieck, Christian Deppe
similarity 0.61
Abstract

We consider a discrete memoryless state-dependent channel with noiseless feedback, where the transmitter uses randomized encoding to jointly perform message transmission, identification, and state sensing. In this setting, the transmitter sends a conventional transmission message and an identification message while estimating the unknown channel state sequence under an average distortion constraint. We establish a single-letter characterization of the randomized identification-transmission-sensing capacity-distortion region. The result reveals a single-letter separation structure: the communication rates are determined by the averaged channel, subject to the sensing-induced constraint on admissible input distributions. Specifically, the transmission rate is characterized by mutual information, while the identification rate is characterized by output entropy under the same distortion constraint. The achievability proof combines constant-composition transmission coding, output partitioning, and combinatorial identification coding, while the converse follows from an averaged-channel reduction, distortion lower bounds, and feedback-identification converse arguments.

0.22

MacKay-Neal Codes Achieve Capacity under MAP Decoding

cs.IT ·2026-10-07 ·Kenta Kasai
theory similarity 0.60
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.43

Universal Decoding for Unequal Error Protection

cs.IT ·2026-10-11 ·Seyed AmirPouya Moeini, Albert Guillén i Fàbregas
similarity 0.60
Abstract

We study universal unequal error protection of a single special message over discrete memoryless channels. We construct a sequence of codes with a decoding rule that does not depend on the channel transition law. We derive an achievable error exponent for the special message while ensuring reliable decoding of the ordinary messages. The resulting exponent strictly improves on the natural equal-error-protection random-coding baseline and remains positive as the rate approaches capacity. For symmetric channels, it converges to the optimal red-alert exponent at capacity.

0.17

An Upper Bound to the Undetected Error Exponent with Erasure Decoding at Positive Rates

cs.IT ·2026-10-11 ·Seyed AmirPouya Moeini, Marco Dalai, Albert Guillén i Fàbregas
theory similarity 0.59
Abstract

We study the undetected-error exponent of discrete memoryless channels with erasure decoding. Assuming that the undetected-error and erasure probabilities vanish, we derive an upper bound on the undetected-error exponent at positive rates. The bound uses Somekh-Baruch's genie-aided argument where an auxiliary output provides the decoder with a list of codewords. It recovers Telatar's tight rate-zero converse and is at least as tight as the straight-line bound. A numerical example shows that the improvement over the straight-line bound can be strict.

0.16

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

cs.IT ·2026-09-22 ·Kenta Kasai
theory similarity 0.56
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

Fano's Inequality and Channel Capacity in the Individual-Sequence Regime

cs.IT ·2026-11-04 ·Neri Merhav
theory similarity 0.56
Abstract · 31 pages; submitted for publication

We derive an individual-sequence analogue of Fano's inequality, replacing entropy by Lempel--Ziv (LZ) complexity and probability of error by empirical error frequency. In the setting considered, an arbitrary encoder maps a message to a channel input sequence $\{x_t\}$, the channel maps the input to an output $\{y_t\}$ in a completely arbitrary manner, and a block finite-state decoder produces an estimate of the channel input from the output. The individual-sequence Fano inequality lower-bounds the empirical symbol-error frequency in terms of the LZ complexity of the channel input conditioned on the channel output. This leads to a channel coding converse: reliable communication at a given rate is possible only if that rate does not exceed the individual-sequence LZ channel capacity, defined as the LZ mutual information maximized over channel inputs and minimized (worst-case) over a noise set. We also prove a matching achievability theorem for the class of \emph{symbol-wise invertible} channels, in which the channel output at each time $t$ is $y_t = f(x_t, v_t)$, $v_t$ being a `noise' variable, and $f(\cdot,v)$ is a bijection for every fixed $v$. This class includes group-additive channels $y_t = x_t \oplus v_t$ studied by Feder and coworkers. For such a channel, any rate below the LZ capacity is achievable with vanishing per-message error frequency, simultaneously for every $v^n$ in a given noise set $\mathcal{N}$, provided $\mathcal{N}$ is closed under block permutations; this condition is satisfied by any noise set that depends on $v^n$ only via its type class with respect to such blocks. The achievability uses a universal decoder that requires no knowledge of the channel and no feedback.

0.22