2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | C.1.5 | ||
| Paper Title | Graceful degradation over the BEC via non-linear codes | ||
| Authors | Hajir Roozbehani, Yury Polyanskiy, MIT, United States | ||
| Session | C.1: Coding for Communications I | ||
| Presentation | Lecture | ||
| Track | Coding for Communications | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | We study a problem of constructing codes that transform a channel with high bit error rate (BER) into one with low BER (at the expense of rate). Our focus is on obtaining codes with smooth (``graceful'') input-output BER curves (as opposed to threshold-like curves typical for long error-correcting codes). This paper restricts attention to binary erasure channels (BEC) and contains three contributions. First, we introduce the notion of Low Density Majority Codes (LDMCs). These codes are non-linear sparse-graph codes, which output majority function evaluated on randomly chosen small subsets of the data bits. This is similar to Low Density Generator Matrix codes (LDGMs), except that the XOR function is replaced with the majority. We show that even with a few iterations of belief propagation (BP) the attained input-output curves provably improve upon performance of any linear systematic code. The effect of non-linearity bootstraping the initial iterations of BP, suggests that LDMCs should improve performance in various applications, where LDGMs have been used traditionally. %(e.g., pre-coding for optics, tornado raptor codes, protograph constructions). Second, we establish several \textit{two-point converse bounds} that lower bound the BER achievable at one erasure probability as a function of BER achieved at another one. The novel nature of our bounds is that they are specific to subclasses of codes (linear systematic and non-linear systematic) and outperform similar bounds implied by the area theorem for the EXIT function. Third, we propose a novel technique for rigorously bounding performance of BP-decoded sparse-graph codes (over arbitrary binary input-symmetric channels). This is based on an extension of Mrs.Gerber's lemma to the $\chi^2$-information and a new characterization of the extremality under the less noisy order. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
