CS Paper Radar

Finite BSC-Decomposition of Binary-Input Symmetric-Output Channels and Applications to Channel Simulation

Jianguo Zhao, Cheuk Ting Li

cs.IT ·submitted 2026-10-19 05:02 UTC · v1

Abstract

We propose a finite BSC-decomposition method for representing an arbitrary binary-input symmetric-output channel (BISOC) as a mixture of binary symmetric channels (BSCs) with at most $\ell+1$ distinct crossover probabilities. We show that the weighted average capacity of the component BSCs exceeds the capacity of the original BISOC by at most $(π^2\log e)/(48\ell^2)+O(\ell^{-5/2})$ bits, and the leading term is asymptotically optimal in the worst case. Based on the finite BSC-decomposition, we design a channel simulation scheme for arbitrary BISOCs. Combined with efficient channel simulation algorithms for BSCs, our scheme achieves a communication rate with $O((\log n / n)^{2/3})$ redundancy over the capacity for simulating $n$ copies of a BISOC.

Comment
15pages,5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Binary code rate bounds via classical--quantum channels

cs.IT math.COquant-ph ·2026-08-10 ·Omar Alrabiah, Venkatesan Guruswami
publishedtheoryhighly cited similarity 0.60
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

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

Task-Oriented Boolean Function Computation: Practical Code Constructions

cs.IT ·2026-10-01 ·Yangshuo He, Guanding Yu, Jingge Zhu
similarity 0.58
Abstract

Task-oriented communication conveys information that is necessary for downstream tasks. For binary decision tasks, this paradigm is information-theoretically formalized by Boolean function computation (BFC) via channels, where the receiver aims to determine the value of a function unknown to the transmitter. In this paper, we devise a practical code construction for the BFC problem based on a Reed-Solomon code. For noiseless binary channels, we derive finite-blocklength worst-case error bounds. By defining a rate function that captures how supported message length scales with channel uses, we characterize the rate-reliability tradeoff for different Boolean function families. With respect to this rate function, the proposed construction achieves an asymptotic computation rate of $1/2$. We further extend this construction to noisy channels by packing multiple BFC tasks into a single block and concatenating them with a conventional channel code. The corresponding finite-blocklength guarantees are expressed in terms of effective channel uses per function evaluation. With a channel code rate $R_c$, this construction achieves an asymptotic computation rate of $R_c/2$, yielding $C/2$ when capacity-achieving channel codes are employed. Numerical results illustrate the derived bounds and demonstrate substantial performance gains over conventional transmission. As examples, the proposed scheme achieves SNR coding gains of approximately $3.4$ and $6.4$ dB at an average task error probability of $10^{-5}$ for the exact-weight and rank-test tasks, respectively.

0.07

From Symmetry to Secrecy: Covariant Classical--Quantum Wiretap Channels

cs.IT quant-ph ·2026-10-02 ·Masahito Hayashi, Farzin Salek
benchmark similarity 0.57
Abstract

For classical--quantum wiretap channels with a transitive covariant input action, both output ensembles admit a description as unitary group orbits of fixed seed states. We use this structure to construct finite-block preprocessing schemes whose private information is an entropy difference evaluated at two distributions related by group convolution. Applying the construction to product groups allows correlations across any fixed number of channel uses. We give a sufficient condition for the associated uniform-input bound to equal the single-use private information. Constant-composition channel codes and universal$_2$ hashing achieve the resulting rates, with trace-distance leakage controlled by sandwiched Rényi information. For uniform outer randomization, the representation structure reduces the comparison-state optimization to Eve's invariant states. For the hybrid binary channel considered by Tikku, Berta and Renes, numerical optimization at three and four uses gives rates above our numerical estimate of the optimized noisy-repetition benchmark wherever that estimate is positive on the tested grid. The improvement comes from noise distributions beyond the family of independent physical flips and a symmetric logical flip. We also prove nonadditivity at an explicit channel parameter using a two-use encoder, an analytic single-use converse, and certified entropy bounds. Finally, we relate the hybrid model to binary phase-shift keying with a fixed receiver measurement.

0.46

Scalable Discrete-to-Continuous Channel Simulation for Compression and Privacy

cs.LG cs.IT ·2026-09-10 ·Joseph Rowan, Buu Phan, Ashish J. Khisti
similarity 0.57
Abstract · 39 pages, 9 figures

Channel simulation has recently emerged as a useful component in machine learning systems where samples from a prescribed probability distribution are to be compressed. Yet, general channel simulation algorithms often suffer from high computational costs, random stopping times or, in the worst case, can require generating an infinite number of shared random samples. We introduce a scheme for both exact and approximate simulation of discrete-to-continuous channels which conversely uses a fixed number of random samples, and therefore has a runtime independent of the channel and the input. Unlike existing channel simulation schemes which generate a sequence of independent samples from a proposal distribution, our approach generates one sample, or alternatively a fixed number of samples, from each potential target distribution. We then apply a latent permutation to the samples before performing sample selection using an exponential race. Our scheme provides a flexible tradeoff between the number of generated samples and the compression rate. Using polar and multilevel coding, we scale our approach to handle long blocklengths in $O(n \log n)$ time in order to benefit from reduced per-symbol overhead. We conclude by demonstrating applications to variable-rate compression with stochastic VQ-VAEs and communication-efficient differentially private distributed mean estimation via exact simulation of the Gaussian mechanism.

0.33

Exact Sampling Under Campbell Cost via Rényi Channel Simulation Divergence

cs.IT ·2026-10-11 ·Yijun Fan, Aaron B. Wagner
similarity 0.57
Abstract

We study the communication cost of exact sampling under Campbell's exponential coding criterion. Given a target distribution $P$ and a proposal distribution $Q$, the sender and receiver share i.i.d. $Q$-distributed samples, and the sender communicates an index so that the selected sample has distribution exactly $P$. We introduce a new information measure Rényi channel simulation divergence $R_α(P\Vert Q)$, a Rényi generalization of the channel simulation divergence. We then show that it lower bounds the Campbell cost of every exact sampler and is achievable, via a new layered sampling scheme, within an additive constant depending only on the Campbell parameter. This yields a tighter one-shot characterization than previous bounds based on Rényi divergences of different orders. For i.i.d. product distributions, under suitable non-degeneracy and moment conditions, we further show that the gap beyond the leading Rényi-divergence term is $\frac{1}{2}\log n+O(1)$.

0.40

Spatially Coupled MacKay-Neal Codes Achieve Capacity on BMS Channels at Fixed Degrees

cs.IT ·2026-09-14 ·Kenta Kasai
code/data similarity 0.57
Abstract · 43 pages; expanded preliminaries, proof explanations, BEC comparison, and historical context; exact certificates and verification software: …

We establish two degree-dependent results for spatially coupled MacKay-Neal codes on binary-input memoryless symmetric channels. The ensembles use uniform random smoothing and shorten both variable types outside the active chain. For $r=g=3$, every integer $\ell\geq4$, and each channel of capacity greater than $R=r/\ell$, there is a sequence of code realizations whose actual transmitted rate tends to $R$ and whose average sum-product bit error tends to zero. For $r=g=2$ and each $\ell\in\{3,4,5\}$, an interval of binary symmetric channels has capacity greater than $R$ but retains positive transmitted-bit error under terminated density evolution as chain length grows relative to coupling width. Both results follow from the signs of the same density-valued potential at uncoupled fixed points. The degree-three proof combines analytic bounds for $\ell\geq33$ with exact interval certificates for $4\leq\ell\leq32$, followed by threshold saturation and a projection argument for the actual rate. The degree-two proof analytically constructs a fixed point with negative potential and controls both boundary contributions. We relate the potential and the degree-two bifurcation condition to earlier statistical-mechanical predictions. The finite certificates and verification software are available in a versioned supplement.

0.59

Fine asymptotics for approximate simulation of symmetric channels

cs.IT ·2026-10-11 ·Valentinian Lungu, Aaron B. Wagner, Ioannis Kontoyiannis
similarity 0.57
Abstract

We study the approximate channel simulation problem in the normal approximation regime. Our starting point is the fact established by Cao et al.~\cite{Cao_channel_simulation}, that the minimal codebook size $M_ε^*(W)$ for a fixed error tolerance $ε>0$ is closely related to the $ε$-smooth channel max-information, $I_{\max}^ε(W)$. Using this, we refine earlier large-blocklength approximations to $M_ε^*(W^{\otimes n})$ for discrete memoryless channels. Specifically, we provide tight third-order expansions for Gallager-symmetric channels and demonstrate that the third-order term is channel-dependent. As in corresponding channel coding expansions, we identify a substantial rate gap between singular and nonsingular channels. Notably, the direction of this gap is reversed relative to channel coding: The third-order term is $-\frac{1}{2}\log n$ for singular channels but $O(\log\log n)$ for nonsingular channels.

0.42