TY - UNPB

T1 - Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs

AU - Austrin, Per

AU - Kaski, Petteri

AU - Koivisto, Mikko

AU - Nederlof, Jesper

N1 - 11 pages; to appear at ISIT 2016

PY - 2016/5/2

Y1 - 2016/5/2

N2 - 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 \leq 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$.

AB - 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 \leq 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$.

KW - cs.IT

KW - cs.DM

KW - math.IT

U2 - 10.48550/arXiv.1605.00462

DO - 10.48550/arXiv.1605.00462

M3 - Preprint

SP - 1

EP - 11

BT - Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs

PB - arXiv

ER -