2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | M.6.3 | ||
| Paper Title | Polar Codes with Balanced Codewords | ||
| Authors | Utkarsh Gupta, Indian Institute of Technology, New Delhi, India; Han Mao Kiah, Nanyang Technological University, Singapore; Alexander Vardy, Hanwen Yao, University of California San Diego, United States | ||
| Session | M.6: Coding for Storage and Memories II | ||
| Presentation | Lecture | ||
| Track | Coding for Storage and Memories | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | The \emph{imbalance} of a binary word refers to the absolute difference between the number of ones and zeros in the word. Motivated by applications in DNA-based data storage and the success of polar codes, we study the problem of reducing imbalance in the codewords of a polar code. To this end, we adapt the technique of Mazumdar, Roth, and Vontobel by considering balancing sets that correspond to low-order Reed-Muller (RM) codes. Such balancing sets are likely to be included as subcodes in polar codes. Specifically, using the first-order RM code, we show that any message can be encoded into a length-$n$ polar codeword with imbalance at most $o(n)$ in $O(n\log n)$-time. We then reduce the imbalance even further using two methods. First, we constrain the ambient space $\mathbb{X}$ and analyze the imbalance that the first-order RM code can achieve for words in $\mathbb{X}$. We demonstrate that for codelengths up to 128, the first-order RM code achieves zero imbalance for appropriate choices of $\mathbb{X}$ that sacrifice only a few message bits. Second, we augment the balancing set by considering higher order RM codes. We give a simple recursive upper bound for the guaranteed imbalance of RM codes. We also prove that the second-order RM code $\RM(2,m)$ balances all even-weight words for $m \le 5$, while the RM code of order $m-3$ balances all even-weight words for $m \ge 5$. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
