Global sampling for sequential filtering over discrete state space

In many situations, it is required to approximate sequence of probability measures over a growing product of finite spaces. This is typically the case in digital communications, where the finite space is the symbol alphabet and the probability measures to be approximated are the posterior distribution of the transmitted symbols given the observations. Whereas it is in general possible to compute explicitly these probability measures, the typical complexity of these computations grow exponentially, precluding real time-implementations. In this paper, an efficient approach for approximating these distributions is presented using a particular implementation of the sequential Monte-Carlo filter (SMC). SMC consists in approximating the sequence of probability measures by the empirical distribution of a finite set N of trajectories which evolve under a random mechanism. Since the space is finite, it is possible to consider every offspring of the trajectory of particles: contrary to the classical sequential importance sampling and resampling (SISR) procedure, it is thus not required to develop a sophisticated strategy to build an appropriate importance distribution. The procedure is therefore straightforward to implement, and is well-suited for real-time implementation. The approach compares favorably with SMC techniques proposed in the literature and appears to be extremely robust even when the number of particles is small. An illustration on joint channel estimation / symbol detection on a flat fading channel is presented to support the claims.