CS Paper Radar

Exact Common Information and Exact Channel Synthesis for Correlated Discrete Sources

Lei Yu

cs.IT ·submitted 2026-09-21 05:18 UTC · v1

Abstract

In this paper, we provide a single-letter characterization of the exact common information for a pair of correlated discrete sources, as well as a single-letter characterization of the admissible region for the shared randomness rate and the communication rate in exact channel synthesis.

Comment
12 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Common Information and Exact Channel Synthesis for Correlated Gaussian Sources

cs.IT ·2026-08-26 ·Lei Yu
similarity 0.76
Abstract · 16 pages, 2 figures

In this paper, we resolve two conjectures posed by Yu and Tan in 2020 (in two separate papers published in the IEEE Trans. Inf. Theory). Specifically, we establish that: 1) the exact common information for a pair of $ρ$-correlated Gaussian sources is given by the conjectured expression $\frac{1}{2}\log\frac{1+ρ}{1-ρ}+\fracρ{1+ρ}$; and 2) the admissible region for the shared randomness rate and the communication rate in exact channel synthesis is exactly the conjectured one. These results yield two important consequences. First, for any $ρ>0$, the exact common information of a correlated Gaussian pair strictly exceeds Wyner's common information. Second, for $ρ>0$, the exact channel synthesis of such a pair requires strictly higher rates than the total-variation version. The proof combines an exact optimal-transport representation of the worst-case Gaussian cross-entropy, Fathi's Gaussian transport inequality, and a determinant inequality arising from the covariance structure of the conditional means.

0.36

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

A Sharp Mutual Information Bound for Binary Pairs

cs.IT ·2026-11-02 ·Qianmian Guo
theory similarity 0.59
Abstract

We prove a sharp upper bound on the mutual information between two binary random variables in terms of their distribution-dependent KL contraction coefficient. This resolves the binary-pair conjecture of Anantharam, Gohari, Kamath, and Nair. Equality holds if and only if the variables are independent or form a doubly symmetric binary source. The proof uses supporting tangents of an entropy curve to vary the input distribution and the channel while preserving the contraction coefficient. Together with tensorization and data processing, the result also bounds the mutual information between binary outputs obtained separately from two correlated observation sequences. When the observation pairs are independent copies of a finite-alphabet pair, this bound depends only on the law of one pair and not on the number of observations.

0.24

Exact Redundancy under Average and Almost-Sure Distortion Constraints

cs.IT ·2026-11-15 ·Yijun Fan
hot direction similarity 0.58
Abstract

We characterize the exact redundancy of lossy source coding under average and almost-sure distortion constraints. For general source and output alphabets, we establish the asymptotic redundancy coefficients under suitable regularity conditions. Under the average distortion constraint, the coefficient is half of the minimum probability that an output reveals information about the source, among all rate-distortion optimal channels. Under the almost-sure distortion constraint, the coefficient is either $1/2$ or $1$, depending on whether the $D$-tilted information is constant or not. Both converse results follow from a common change-of-measure inequality. Finally, we verify the required conditions under both distortion requirements always hold for finite alphabets.

0.23

Deterministic Identification over Additive Gaussian Channels

cs.IT ·2026-08-27 ·Jonathan E. W. Huffmann, Holger Boche
similarity 0.58
Abstract · gap in proof

Modern communication systems impose strict demands on data rate, reliability, and power efficiency. In this context, emerging communication paradigms such as identification via channels have become an important topic in post-Shannon information theory, offering the potential for substantially higher identification rates than in conventional channel coding.Deterministic identification is particularly interesting for specialized communication scenarios because it provides a balance between implementation complexity and the communication gains due to higher identification rates. It is therefore a promising communication scheme for future communication systems, including molecular communication systems. Additive Gaussian channels, particularly the additive white Gaussian channel, are among the most important channel models for analyzing the performance of communication systems in information and communication theory. This importance stems from both their mathematical tractability and their ubiquitous appearance in practical applications. To date the deterministic identification capacity for additive Gaussian channels remains unknown even for the simplest case of the additive white Gaussian channel. In this paper, we establish tight bounds on the deterministic identification capacity of additive Gaussian channels by introducing a new perspective on deterministic identification. To this end, we apply results from lattice theory to obtain new capacity results.

0.10

Movable Antenna-Assisted Secret Key Generation over Temporally Correlated Channels

cs.IT cs.CReess.SP ·2026-11-02 ·Zhiyu Huang, Chen Sun, Guyue Li, Guanghui Wen, Xianbin Wang
similarity 0.56
Abstract

Physical-layer key generation (PLKG) exploits reciprocal channel dynamics to generate symmetric keys, addressing the key distribution problem in wireless communications. However, strong temporal correlation in slow-fading environments limits fresh randomness and results in low key generation rates. Movable antennas (MAs) introduce spatial degrees of freedom through antenna repositioning, providing a new approach to addressing the limitation. This paper investigates MA-assisted PLKG over temporally correlated channels. A first-order Gauss-Markov process is utilized to characterize the temporal correlation of multipath gains. We characterize the full-sequence mutual information (MI) over temporally correlated channels. For fixed antenna positions and beamforming, we establish a finite-horizon approximation error bound that vanishes as both effective signal-to-noise ratios (SNRs) increase. We derive a closed-form expression for the one-step conditional MI and adopt it as a tractable key-information metric. A nonconvex problem is formulated to jointly optimize antenna positions and per-slot beamforming under transmit-power and minimum-spacing constraints. We develop an alternating optimization algorithm, combining an exact principal-eigenvector beamforming solution with feasible SCA-based projected gradient position updates. Simulation results demonstrate that the MA-assisted scheme outperforms the fixed-position antenna baseline. At a high temporal correlation coefficient, position optimization achieves approximately $51\%$ higher rates than fixed antennas. Joint position and beamforming optimization provides a further $106\%$ gain over position optimization alone, demonstrating more pronounced gains under strong temporal correlation.

0.20

MacKay-Neal Codes Achieve Capacity under MAP Decoding

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

The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach

cs.IT ·2026-09-20 ·Yiyu Qiu, Wei Chen, H. Vincent Poor
published similarity 0.55
Abstract

The general broadcast channel (BC) has attracted considerable attention because it is a central problem in network or multi-user information theory. The deterministic BC (det-BC), in which both output symbols are functions of the input symbol, plays a vital role in understanding general BCs. In the 1970s, Marton and Pinsker investigated the det-BC independently using a random coding approach and hence quantified its capacity region as functions of the entropy of output symbols. In this paper, we present a purely deterministic and combinatorial treatment of the deterministic BC, which is in contrast to Marton and Pinsker's probabilistic treatment. In particular, we show that each det-BC can be uniquely and completely characterized by a bipartite graph. Based on the bipartite graph model, we present the explicit capacity region of the general det-BC and a deterministic capacity-achieving coding scheme. Specifically, each point on the capacity region boundary is expressed as an explicit function of the degree sequences of the two parts, with boundary coordinates parametrized by the tangent slope. As a result, a closed-form capacity region, which was previously unknown except for special cases such as the Blackwell channel, can be analytically determined, without optimizing the probability distribution of input symbols numerically. For a bipartite graph consisting of multiple isolated subgraphs, there can exist a commonly decodable message while preserving the maximum achievable sum rate, and its achievable rate is explicitly characterized. Finally, the bipartite-graph formulation allows us to construct optimal finite-blocklength coding for the det-BC through binary linear programming.

0.40