Constructive spherical codes near the Shannon bound

DOI10.1007/S10623-012-9633-2MaRDI QIDQ1934239zbMATH OpenOpenAlexFDO

Authors Patrick Solé, Jean-Claude Belfiore

Publication date 28 January 2013

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1101.1895

codes for the Euclidean metric saddle point method spherical codes

Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Bounds on codes (94B65) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)

Abstract: Shannon gave a lower bound in 1959 on the binary rate of spherical codes of given minimum Euclidean distance

h o

. Using nonconstructive codes over a finite alphabet, we give a lower bound that is weaker but very close for small values of

h o

. The construction is based on the Yaglom map combined with some finite sphere packings obtained from nonconstructive codes for the Euclidean metric. Concatenating geometric codes meeting the TVZ bound with a Lee metric BCH code over

G F (p),

we obtain spherical codes that are polynomial time constructible. Their parameters outperform those obtained by Lachaud and Stern in 1994. At very high rate they are above 98 per cent of the Shannon bound.

Review text

Let \(X\) be a spherical code of \(\mathbb{R}^n\), i.e., a finite set of points of the unit sphere in a Euclidean space of finite dimension \(n\). If \(\rho\) denotes the Euclidean squared minimum distance of this spherical code, its binary rate is defined by \[ R(\rho):= \limsup{\log_2(|X|)\over n}. \] The lower bound \(R(\rho)\geq R_S(\rho):= 1- (1/2)\log_2(\rho(4-\rho))\) was given by Chabauty in 1953 and Shannon in 1959 (cf. [\textit{C. Chabauty}, C. R. Acad. Sci., Paris 236, 1462--1464 (1953; Zbl 0050.16605); \textit{C. E. Shannon}, ``Probability of error for optimal codes in a Gaussian channel, Bell. Syst. Tech. J. 38, 611--656 (1959); \textit{G. Lachaud} and \textit{J. Stern}, IEEE Trans. Inf. Theory 40, No. 4, 1140--1146 (1994; Zbl 0813.94024)]). The lower bound on the rate \(R_*(\rho)\) of polynomial time constructible spherical codes \[ R_*(\rho)\geq 0.5R_S(\rho) \] was given by Lachaud and Stern [loc. cit.]. In the present paper the authors give the following lower bound based on nonconstructive lattice packings: \[ R(\rho)\geq R_L(\rho):= -(1/2)\log_2(\rho). \] By direct substitution the authors find that \(R_S(\rho)\geq R_L(\rho)\) for all \(0\leq\rho\leq 4\), and for small \(\rho\) the two curves are very close to each other: \[ R(\rho)- R_L(\rho)= O(\rho^2). \] The authors show that using finite alphabet codes for constructing finite packings is as efficient as using truncation of dense infinite sphere packings. The main result of this work is a lower bound \(R_*(\rho)\geq 0.98R_S(\rho)\) for some very small values of \(\rho\) in the range \(0< \rho\leq 1\). This outperforms the Lachaud-Stern bound almost by a factor of 2.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: Constructive spherical codes near the Shannon bound

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1934239)