Math @ Duke

Publications [#319312] of Henry Pfister
Papers Published
 Kudekar, S; Kumar, S; Mondelli, M; Pfister, HD; Urbankez, R, Comparing the bitMAP and blockMAP decoding thresholds of reedmuller codes on BMS channels,
Ieee International Symposium on Information Theory Proceedings, vol. 2016August
(August, 2016),
pp. 17551759, IEEE, ISBN 9781509018062 [doi]
(last updated on 2019/07/22)
Abstract: © 2016 IEEE. The question whether RM codes are capacityachieving is a longstanding open problem in coding theory that was recently answered in the affirmative for transmission over erasure channels [1], [2]. Remarkably, the proof does not rely on specific properties of RM codes, apart from their symmetry. Indeed, the main technical result consists in showing that any sequence of linear codes, with doublytransitive permutation groups, achieves capacity on the memoryless erasure channel under bitMAP decoding. Thus, a natural question is what happens under blockMAP decoding. In [1], [2], by exploiting further symmetries of the code, the bitMAP threshold was shown to be sharp enough so that the block erasure probability also converges to 0. However, this technique relies heavily on the fact that the transmission is over an erasure channel. We present an alternative approach to strengthen results regarding the bitMAP threshold to blockMAP thresholds. This approach is based on a careful analysis of the weight distribution of RM codes. In particular, the flavor of the main result is the following: assume that the bitMAP error probability decays as Nδ, for some δ > 0. Then, the blockMAP error probability also converges to 0. This technique applies to transmission over any binary memoryless symmetric channel. Thus, it can be thought of as a first step in extending the proof that RM codes are capacityachieving to the general case.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

