The Voronoi Spherical CDF for Lattices and Linear Codes: New Bounds for Quantization and Coding

Author:
Publisher website
Google Scholar
Abstract
For a lattice/linear code, we define the Voronoi spherical cumulative density function (CDF) as the CDF of the $\ell _{2}$ -norm/Hamming weight of a random vector uniformly distributed over the Voronoi cell. Using the first moment method together with a simple application of Jensen’s inequality, we develop lower bounds on the expected Voronoi spherical CDF of a random lattice/linear code. Our bounds are valid for any finite dimension and are quite close to a ball-based lower bound. They immediately translate to new non-asymptotic upper bounds on the normalized second moment and the error probability of a random lattice over the additive white Gaussian noise channel, as well as new non-asymptotic upper bounds on the Hamming distortion and the error probability of a random linear code over the binary symmetric channel. In particular, we show that for most lattices in $\mathbb {R}^{n}$ the second moment is greater than that of a Euclidean ball with the same covolume only by a $\left ({{1+O\left ({{\frac {1}{n}}}\right)}}\right)$ multiplicative factor. Similarly, for most linear codes in $\mathbb {F}_{2}^{n}$ the expected Hamming distortion is greater than that of a corresponding Hamming ball only by an additive universal constant.
Funding Information
  • under (ISF 1641/21)
  • under (ISF 2878/25)

This publication has 70 references indexed in Scilit: