The Voronoi Spherical CDF for Lattices and Linear Codes: New Bounds for Quantization and Coding
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910035033980928 |
|---|---|
| author | Ordentlich, Or |
| author_facet | Ordentlich, Or |
| contents | 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(\frac{1}{n})\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_19791 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Voronoi Spherical CDF for Lattices and Linear Codes: New Bounds for Quantization and Coding Ordentlich, Or Information Theory Number Theory 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(\frac{1}{n})\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. |
| title | The Voronoi Spherical CDF for Lattices and Linear Codes: New Bounds for Quantization and Coding |
| topic | Information Theory Number Theory |
| url | https://arxiv.org/abs/2506.19791 |