期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 67, 期 6, 页码 3251-3277出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2020.3004749
关键词
Reed-Muller codes; Shannon capacity; weight enumerator; decoding algorithms; polarization
资金
- NSF CAREER Award [CCF-1552131]
- Israel Science Foundation [552/16]
- Blavatnik Family Foundation
RM codes are one of the oldest and simplest codes in coding theory, which are still under investigation for their important properties. Recent developments have been made in the weight enumerator, capacity-achieving properties, and algorithmic improvements for RM codes. The paper discusses connections between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and techniques for approximating low weight codewords using lower degree polynomials.
Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under investigation. This paper covers some of the recent developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, the paper discusses the recent connections established between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and the techniques of approximating low weight codewords using lower degree polynomials (when codewords are viewed as evaluation vectors of degree r polynomials in m variables). It then overviews some of the algorithms for decoding RM codes. It covers both algorithms with provable performance guarantees for every block length, as well as algorithms with state-of-the-art performances in practical regimes, which do not perform as well for large block length. Finally, the paper concludes with a few open problems.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据