Technical Program

Paper Detail

Paper IDM.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

Visit Website!