Source-linked AI summary
Deterministic Identification over Additive Gaussian Channels
Jonathan E. W. Huffmann, Holger Boche
TL;DR
The paper addresses the previously unknown deterministic identification capacity of additive Gaussian channels. It uses lattice-based codebook constructions together with converse arguments, establishing capacity results that are largely unaffected by Gaussian noise power, memory, and input power constraints.
Problem
The deterministic identification capacity of additive Gaussian channels, including the additive white Gaussian channel, remained unknown despite the importance of these models.
Method
The paper combines lattice-theoretic codebook constructions for achievability with a binary hypothesis test and Pinsker’s inequality for the converse.
Results
C^Γc_dID(P) = 1/2, with the result holding under arbitrary Gaussian noise memory and power and a broad class of p-norm input constraints.
Takeaways & Limitations
Deterministic identification capacity is largely unaffected by Gaussian noise power, noise memory, and the specific input power constraint.
Abstract
from arXiv · showhide
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.
I. Introduction
Deterministic identification lets receivers test whether a selected message was sent, achieving higher identification rates than full message decoding. This paper addresses the unknown additive Gaussian capacity using lattice-based codebooks and derives results largely independent of noise and power constraints.
- Higher identification rates and lower implementation requirements make deterministic identification promising for future and molecular communication systems.
- Deterministic identification tests whether a preselected message was sent instead of decoding the transmitted message in full.
- The additive white Gaussian channel’s deterministic identification capacity remained unknown, despite prior bounds improving from 1/4 to 3/8.
- The Poisson channel is relevant to molecular communication, and its reliable-identification codebook size grows on the same scale as the additive white Gaussian channel.
- The paper establishes tight additive Gaussian capacity results with lattice-based codebooks whose constructions asymptotically achieve the capacity.
- The capacity is largely independent of Gaussian noise power, noise memory, and input power constraints, unlike conventional transmission.
II. Notation
The notation represents vectors, random variables, and channel distributions using standard mathematical symbols and treats vector indices as discrete time indices.
- Vectors are written as x = (x_1, . . . , x_n), with dimension n and column-vector interpretation for input and output processes.
- Random variables and vectors use capital letters, while their probability measures use corresponding P notation, including P_Y|X for conditional distributions.
III. Prerequisites
This section introduces lattice geometry and existence results used to construct codebooks, including volume, admissibility, Blichfeldt, and Minkowski–Hlawka tools. It also notes that sharper packing constants exist but do not improve the capacity result.
- Lattice theory results are used later in the achievability proof to construct capacity-achieving codebooks.
- A lattice in R^n consists of all integer linear combinations of linearly independent basis vectors, with unique coefficient representations for a fixed basis.
- The lattice determinant is basis-independent and corresponds geometrically to the volume of a fundamental parallelepiped that tiles R^n under lattice shifts.
- Blichfeldt’s theorem guarantees N + 1 points in a compact set whose pairwise differences belong to a lattice when the volume condition holds.
- An admissible lattice has no nonzero lattice points in a specified set, supporting nonoverlapping sphere packings.
- Minkowski–Hlawka provides lattice existence and sphere-packing density bounds, while sharper constants are noted not to improve deterministic identification capacity.
IV. Deterministic Identification
The paper formalizes deterministic identification codes, rates, capacities, and power constraints, then uses lattice sphere packing to bound codebook growth. These ingredients support the later capacity achievability and converse results.
- Channel model: A channel maps input sequences to output sequences through conditional distributions P_Y|X for each blocklength n.
- Power constraints: Power constraints are represented by average or maximum p-norm costs, including c(y) = |y|^p for 1 ≤ p < ∞.
- Rates and capacity: The deterministic identification capacity is the supremum of achievable rates under the channel and power constraint.
- Sphere packing: The sphere-packing lemma constructs N = e^{M n log(n)} lattice-generated centers inside a p-norm ball while maintaining Euclidean separation.
- Sphere packing: The packing proof combines Minkowski–Hlawka, Blichfeldt, lattice translation, norm-ball volume ratios, and Stirling’s approximation to derive bounds on M.
V. Additive Gaussian Channels
The paper models an arbitrary additive Gaussian channel by adding a finite zero-mean Gaussian noise vector to each input block. The resulting channel is illustrated in Figure 1.
- For an input vector x of blocklength n, the channel output is a random vector Z=(Y1,...,Yn).
- The noise vector Z=(Z1,...,Zn) has zero mean and covariance matrix CZZ derived from a Gaussian noise process.
- Figure 1 depicts the considered additive Gaussian channel model.
V.A Achievability
The achievability proof constructs lattice-based codebooks satisfying broad cost constraints and defines decoding regions using lattice geometry. Under bounded covariance eigenvalues, it achieves deterministic identification capacity approaching 1/2, while zero-noise directions yield infinite rate.
- A lattice construction based on the Minkowski-Hlawka Theorem and sphere-packing provides the achievability proof for general additive Gaussian channels.
- Codewords are placed at points of an optimal lattice with minimum distance dΛ=2^nb, while the construction enforces the power constraint.
- Each codeword is an integer linear combination of the lattice basis vectors, xi=u1,ia1+...+un,ian.
- If the noise covariance has a zero eigenvalue, codewords can be placed along its eigenvector with distances tending to zero, yielding infinite rate.
- The decoding region for each codeword is formed by intersecting halfspaces associated with that codeword and the lattice vectors.
V.B Converse
The converse analyzes deterministic identification over additive Gaussian channels with arbitrary-memory noise under nonzero covariance eigenvalues. It shows that rates above 1/2 cannot be achieved, while the coding theorem establishes achievability at rates 1/2 + b under stated bounded-eigenvalue and input-cost assumptions.
- Assumptions: The converse assumes Gaussian noise covariance eigenvalues are bounded away from zero; otherwise deterministic identification capacity is unbounded.The argument allows arbitrary memory and variance in the noise process.
- Converse result: No rate R = 1/2 + b with b > 0 is achievable under the converse assumptions.Two codewords with distance at most n^-b yield a lower bound on the combined type-1 and type-2 error probability.
- Converse method: The converse treats identification as binary hypothesis testing and bounds the sum of type-1 and type-2 errors using Pinsker’s inequality and Gaussian KL divergence.The proof applies these bounds to two sufficiently close codewords and arbitrary decoding regions.
- Coding theorem: The proof of the coding theorem follows from the deterministic identification capacity definition together with the preceding achievability and converse theorems.The achievability construction uses lattice-derived codebooks and corresponding decoding regions.
VI. Conclusions
The paper determines the deterministic identification capacity of additive Gaussian channels as 1/2 under weak noise assumptions and general p-norm input constraints. Its achievability uses lattice-based codebooks, while the converse uses binary hypothesis testing and Pinsker’s inequality.
- Main result: The deterministic identification capacity is dID(P) = 1/2 for additive Gaussian channels.The result is stated for the considered class of input constraints and positive P.
- Scope: The result allows Gaussian noise with arbitrary memory and noise power, subject to the paper’s stated covariance-eigenvalue assumptions.The capacity is described as largely unaffected by the noise process’s power and memory.
- Scope: The analysis covers a general class of input constraints defined through p-norms.The conclusion states that the specific input power constraint does not substantially affect the capacity result.
- Proof strategy: Achievability relies on lattice-theoretic codebook constructions, whereas the converse relies on a binary hypothesis test and Pinsker’s inequality.The resulting type-1 and type-2 error bounds hold for every blocklength n.
- Future work: The authors identify extending the approach to other continuous-alphabet channels and efficiently constructing corresponding methods as future research directions.These directions concern broader channel classes and practical construction procedures.