Constructive Spherical Codes by Hopf Foliations


Abstract in English

We present a new systematic approach to constructing spherical codes in dimensions $2^k$, based on Hopf foliations. Using the fact that a sphere $S^{2n-1}$ is foliated by manifolds $S_{coseta}^{n-1} times S_{sineta}^{n-1}$, $etain[0,pi/2]$, we distribute points in dimension $2^k$ via a recursive algorithm from a basic construction in $mathbb{R}^4$. Our procedure outperforms some current constructive methods in several small-distance regimes and constitutes a compromise between achieving a large number of codewords for a minimum given distance and effective constructiveness with low encoding computational cost. Bounds for the asymptotic density are derived and compared with other constructions. The encoding process has storage complexity $O(n)$ and time complexity $O(n log n)$. We also propose a sub-optimal decoding procedure, which does not require storing the codebook and has time complexity $O(n log n)$.

Download