CS Paper Radar

KKTCode: Asymptotically Optimal Linear Codes for Noisy Feedback AWGN Channels

Hongjae Nam, Jonggyu Jang, Vishrant Tripathi, David J. Love

cs.IT ·submitted 2026-09-26 00:43 UTC · v1
theory

Abstract

The design of optimal causal linear feedback schemes for additive white Gaussian noise (AWGN) channels with noisy output feedback has remained an open problem for over 60 years. Prior work has focused on restricted policy classes, especially passive (uncoded) noisy output feedback, where only the transmitter performs feedback coding. However, passive noisy output feedback fundamentally lacks the degrees of freedom required to attain the information-theoretic performance limit in general. In this paper, we consider the active (coded) noisy output feedback setting, where both the transmitter and the receiver perform feedback coding. We then develop a constructive KKT-optimal active linear feedback design that asymptotically attains the Elias-Butman SNR converse bound, thereby establishing MSE/SNR optimality over the entire class of causal linear schemes. Furthermore, we prove that the optimal passive feedback solution is recovered as a special case of the active design. This passive solution admits a Geometric Toeplitz (GT) structure with a Chance-Love (CL)-style one-shot polynomial characterization, and can be computed with O(log T) complexity. Thus, our results provide an affirmative answer to the long-standing optimality question for noisy output feedback under causal linear feedback coding, and our numerical results support the theoretical findings.

Closest papers

Nearest neighbours by meaning across the whole index.

Feedback Capacity of Stationary Gaussian Channels: An Optimal Schalkwijk-Kailath Scheme

cs.IT ·2026-09-10 ·David Fay, Oron Sabag
theory similarity 0.65
Abstract

We consider channels with additive colored Gaussian noise and noiseless feedback. Kim's seminal work derived a stationary variational characterization of feedback capacity and further asserted that the capacity-achieving stationary input need not contain a feedback-independent Gaussian component. These results led to the construction of a simple coding scheme, based on the Schalkwijk--Kailath (SK) refinement principle, which was shown to be capacity-achieving. A recent note identified a gap in the proof of the feedback-independent component-removal assertion, thereby leaving the optimality of the SK scheme and subsequent results that rely on it incomplete. In this paper, we prove the component-removal assertion for channels with stationary Gaussian noise that has a rational power spectral density. Our proof uses a perturbation analysis of a convex optimization formulation of feedback capacity and, indeed, shows that every optimizer assigns zero power to the feedback-independent component. Using this stronger property, we construct from any optimizer an explicit SK coding scheme that achieves every rate below feedback capacity with doubly-exponentially decaying maximal error probability.

0.43

A Hardy-Space Proof of the Filter-Only Gaussian Feedback-Capacity Formula

cs.IT ·2026-09-14 ·Jun Su, Yang Xu, Guangyue Han
theory similarity 0.64
Abstract

The feedback capacity of power-constrained channels with additive stationary Gaussian noise was formulated by Kim in [Kim, 2010] as an infinite-dimensional optimization over the spectrum of an independent stationary Gaussian component and a strictly causal feedback filter. Kim further asserted that the independent stationary component can be omitted. However, Derpich and Østergaard [Derpich and Østergaard, 2022] identified a gap in the original proof, leaving the original derivation of the filter-only capacity formula incomplete. In this paper, we establish the filter-only formula at the level of capacity suprema for noise spectra satisfying the Paley-Wiener condition. In particular, we show that polynomial feedback filters suffice in the capacity supremum, without a positive lower bound on the noise spectrum or a rationality assumption. Under a positive essential lower bound, a complementary approximation preserves the output spectrum and rate exactly, while its input power converges to that of the original pair. An interleaved AR(1) example connects these results with the SK(2) coding scheme. The argument does not assert attainment by a single filter.

0.34

Nonlinear Posterior-Mean Feedback Codes for AWGN Channels

cs.IT ·2026-10-04 ·Yingyao Zhou, Natasha Devroye, Milos Zefran, Gyorgy Turan
similarity 0.58
Abstract

Feedback can improve the reliability of communication over additive white Gaussian noise (AWGN) channels. Classical feedback codes are interpretable, or easy to understand, but often rely on linear estimation, while deep-learned feedback codes can achieve strong performance but require many learned parameters and are often black boxes that are difficult to interpret. In this work, we propose a new posterior-mean feedback coding framework for AWGN channels with feedback. The proposed scheme uses posterior-mean refinement to construct nonlinear feedback codes under both noiseless passive feedback and noisy active feedback, with maximum a posteriori (MAP) decoding at the receiver. This scheme is analytically described, but a few learned parameters related to power allocation, and hence we consider this an ``interpretable,'' or human-understandable code. We further develop a projection-based design to improve robustness under noisy feedback and support larger message sizes. Numerical results show that the proposed schemes achieve strong finite-blocklength performance and outperform several analytical and learned feedback coding baselines, while using only a small number of learned design parameters.

0.21

Achievable Information Rate for FTN under a Reduced Complexity BCJR Receiver

cs.IT eess.SP ·2026-11-15 ·Zichao Zhang, Gokhan M. Guvensen, Melda Yuksel, Halim Yanikomeroglu
theory similarity 0.57
Abstract

The capacity of faster-than-Nyquist (FTN) signaling in additive white Gaussian noise (AWGN) channels has been established and is achieved by Gaussian inputs. However, the capacity of FTN signaling with finite-constellations is not yet fully characterized. The achievable information rate (AIR) provides a lower bound on this constrained capacity by quantifying the rate supported by a specified input distribution and receiver. This paper investigates the AIR of FTN signaling with finite constellations using full-state and reduced-state Bahl-Cocke-Jelinek-Raviv (BCJR) receivers, with bidirectional decision feedback incorporated into the reduced-state receiver. Especially, the detection problem is formulated in a reproducing kernel Hilbert space (RKHS), where a geometric foundation is established to understand FTN under severe time packing. The formulation establishes that the Ungerboeck metric remains valid even when the noise covariance is singular. We further characterize detection errors geometrically using RKHS distances between competing sequences. We also study outage probability for reduced-state detection, which occurs when AIR is zero, in addition to deriving the zero-AIR outage criterion for reduced-state detection. Unlike ISI-free Nyquist signaling, reduced-state FTN detection can retain residual ISI that causes the receiver to assign excessive confidence to incorrect symbols, leading to outage even at high signal-to-noise ratio (SNR). Our results confirm both the spectral efficiency gains and the feasibility of FTN systems employing finite constellations and realistic receiver architectures.

0.16

Capacity regimes for Boolean function computation via channels

cs.IT ·2026-08-11 ·Jingge Zhu, Matthias Frey
similarity 0.56
Abstract · A part of this work has been reported in https://arxiv.org/pdf/2601.12640

Consider a point-to-point communication system in which the transmitter holds a binary message of length $m$ and transmits a corresponding codeword of length $n$. The receiver's goal is to recover a Boolean function of that message, where the function is unknown to the transmitter, but chosen from a known class $F$. We are interested in the asymptotic relationship of $m$ and $n$: given $n$, how large can $m$ be (asymptotically), such that the value of the Boolean function can be recovered reliably? This problem generalizes the identification-via-channels framework introduced by Ahlswede and Dueck. In this paper, we formulate the notion of computation capacity, and derive achievability and converse results for a large class of functions $F$, characterized by the Hamming weight of functions. Different from the classical transmission problem, the performance of the function computation problem is jointly characterized by the computation capacity and the rate function, namely how $m$ scales with $n$ asymptotically. Our results give a complete characterization of the rate function of the computation problem, and provide upper and lower bounds on the computation capacity, where they differ by a factor of at most $2$.

0.52

Second-Order Asymptotics for the Gaussian Multiple-Access Channel at Corner Points

cs.IT ·2026-08-18 ·Vincent Y. F. Tan
theory similarity 0.55
Abstract · 28 pages, 4 figures

We establish exact second-order coding rate regions at the two corner points of the capacity region of the two-user Gaussian multiple-access channel. For any average error probability $\varepsilon\in(0,1)$, we characterize the $n^{-1/2}$-scale fluctuations of achievable rates around each corner point, proving a converse that matches the previously known achievability bound. The proof first extracts a rectangular subcode that preserves the independence of the two transmitted codewords. The Polyanskiy--Verdú good-code output distribution theorem then yields log-determinant constraints that induce a spectral decomposition of a trimmed codebook into diffuse and exceptional subspaces. An entropic Brascamp--Lieb projection inequality controls the codeword inner product on the diffuse subspace, while variance-inflated Gaussian output distributions handle the low-dimensional exceptional subspace. Combining these two treatments yields the joint Gaussian limit required for the matching second-order converse.

0.51

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

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

Second-Order Asymptotics for the Scalar Gaussian Broadcast Channel

cs.IT ·2026-11-01 ·Vincent Y. F. Tan
similarity 0.55
Abstract · 34 pages, 9 figures

This paper characterizes the second-order coding region of the scalar Gaussian broadcast channel along the curved boundary of its capacity region. The characterization holds under both average and maximal error criteria and allows correlation between the receiver noises. At each interior point of this boundary, the second-order region is a halfspace, as in the work of Scarlett and the author on Gaussian multiple-access channels with degraded message sets. Achievability follows from spherical superposition coding with a blocklength-dependent power allocation. The main innovation lies in the converse. Using Ornstein--Uhlenbeck entropy dissipation and Gaussian functional inequalities, we construct an auxiliary observation through an additive Gaussian noise channel and establish quantitative relative entropy bounds for the channel output distributions conditioned on this observation. The strong functional representation lemma of Li and El Gamal then allows us to select a realization of its independent random seed to obtain a deterministic partition of the retained receiver-1 message set. The component label plays a role analogous to the auxiliary random variable in the capacity characterization, while providing the distributional control needed at the second-order scale. These properties guide the construction of auxiliary output measures whose likelihood ratios admit the cancellations and normal approximation needed to evaluate an information spectrum converse.

0.38