This paper studies random-coding error exponents of randomised list decoding, in which the decoder randomly selects $L$ messages with probabilities proportional to the decoding metric of the codewords. The exponents (or bounds) are given for mismatched, and then particularised to matched and universal decoding metrics. Two regimes are studied: for fixed list size, we derive an ensemble-tight random-coding error exponent, and show that, for the matched metric, it does not improve the error exponent of ordinary decoding. For list sizes growing exponentially with the block-length, we provide a non-trivial lower bound to the error exponent that is tight at high rates under the matched metric.

International audience

International audience

We study universal decoding over unknown discrete additive channels. Aiming at low-complexity decoders, we study variants of noise-guessing decoders that use estimators for the probability of a noise sequence when the actual channel law is unknown. A deterministic version produces noise sequences in a fixed order, and a new randomised version draws them at random, until finding one that, subtracted from the received sequence, results in a valid codeword. In all cases, we give sufficient conditions on the family of parametric channels for the decoding strategies to be random-coding universal, and derive upper bounds for their complexity. We give examples of common families of channels in which these conditions are satisfied, and a numerical example illustrates the proposed method’s performance.

We study the problem of universal decoding over memoryless channels with a decoder based on the Krichevsky-Trofimov estimator. We show that this decoder is random-coding universal for codebooks of any size, i.e., despite being ignorant of the channel in use, it has asymptotically the same random-coding error exponent as the optimal maximum-likelihood decoder for that channel. Then, we incorporate this decoding rule in schemes to decode practical linear block codes and convolutional codes when the channel is unknown to the receiver. Numerical results show that efficient performance can be achieved even for moderate blocklength or constraint length.

We propose novel compression algorithms for time-varying channel state information (CSI) in wireless communications. The proposed scheme combines (lossy) vector quantisation and (lossless) compression. First, the new vector quantisation technique is based on a class of parametrised companders applied on each component of the normalised CSI vector. Our algorithm chooses a suitable compander in an intuitively simple way whenever empirical data are available. Then, the sequences of quantisation indices are compressed using a context-tree-based approach. Essentially, we update the estimate of the conditional distribution of the source at each instant and encode the current symbol with the estimated distribution. The algorithms have low complexity, are linear-time in both the spatial dimension and time duration, and can be implemented in an online fashion. We run simulations to demonstrate the effectiveness of the proposed algorithms in such scenarios.

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_{\cos \eta }^{n-1} \times S_{\sin \eta }^{n-1}$,$\eta \in [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)$.

We present a new approach to construct spherical codes in 2kdimensions, based on Hopf foliations. Using the fact that a sphere S2n-1is foliated by manifolds Scos ηn-1× Ssin ηn-1, η ∈ [0, π/2], we distribute points in dimension 2kvia a recursive algorithm from a basic construction in R4. Our procedure outperforms some current constructive methods in several small-distance regimes and constitutes a compromise between optimality and computational effort.