Open Collections

Xia, Xuzhe

Reed–Muller (RM) codes are known to achieve capacity on binary symmetric channels (BSC) under the Maximum a Posteriori (MAP) decoder. However, it remains an open problem to design a capacity achieving polynomial-time RM decoder. Due to a lemma by Liu, Cuff, and Verdú, it can be shown that decoding by sampling from the posterior distribution is also capacity-achieving for RM codes over BSC. The Gibbs decoder is one such Markov Chain Monte Carlo (MCMC) based method, which samples from the posterior distribution by flipping message bits according to the posterior, and can be modified to give other MCMC decoding methods. In this paper, we analyze the mixing time of the Gibbs decoder for RM codes. Our analysis reveals that the Gibbs decoder can exhibit slow mixing for certain carefully constructed sequences. This slow mixing implies that, in the worst-case scenario, the decoder requires super-polynomial time to converge to the desired posterior distribution.

Text

University of British Columbia. CPSC_V 449

Vancouver : University of British Columbia Library

10.14288/1.0448740

Science, Faculty of; Computer Science, Department of

Undergraduate

DSpace