Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs

Abstract

Two sets $A,B\subseteq \{0,1{\}}^n$ form a Uniquely Decodable Code Pair (UDCP) if every pair $a\in A$, $b\in B$ yields a distinct sum $a+b$, where the addition is over ${\mathbb{Z}}^n$. We show that every UDCP $A,B$, with $|A|=2^{(1-\epsilon )n}$ and $|B|=2^{\beta n}$, satisfies $\beta \le 0.4228+\sqrt{\epsilon }$. For sufficiently small $\epsilon$, this bound significantly improves previous bounds by Urbanke and Li~[Information Theory Workshop '98] and Ordentlich and Shayevitz~[2014, arXiv:1412.8415], which upper bound $\beta$ by $0.4921$ and $0.4798$, respectively, as $\epsilon$ approaches $0$.

11 pages; to appear at ISIT 2016