A game-theoretic interpretation of iterative decoding

Bit interleaved Coded Modulation with iterative decoding is known to provide excellent performance over both Gaussian and fading channels. However a complete analysis of the iterative demodulation is still missing. In this paper, the iterative decoding is analyzed from a game-theoretic point of view in order to explain the good performance of turbo-decoding. It is shown that iterative decoding is a game seeking a solution to an optimization problem obtained from parallel approximations of the maximum likelihood decoding. Surprisingly, the decoder and demapper are not antagonist players. They are involved in a cooperative process in which n selfish players attempt to optimize their own bit-marginals. An interpretation is given in terms of pure Nash Equilibrium and social welfare. The approximate criterion of the sub-optimal problem is the social welfare of the game and is also a performance rating on the distributed optimization process. The convergence is analysed and it is proved that it always exists a convergent iterative sequence leading to a Nash equilibrium of the game. Experimental results are provided in the particular case of BICM decoding.