Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs

DOI10.1109/TIT.2017.2688378MaRDI QIDQ4566709zbMATH OpenOpenAlexFDO

Authors Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof

Publication date 27 June 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.00462

Mathematics Subject Classification ID

Decoding (94B35)

Abstract: Two sets $A,Bsubseteq{0,1}^n$ form a Uniquely Decodable Code Pair (UDCP) if every pair $ainA$, $binB$ 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 $$, satisfies $$. 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 $$ by $0.4921$ and $0.4798$, respectively, as $epsilon$ approaches $0$.

Recommendations

• On optimal binary codes with unbalanced coordinates
• Upper bound for uniquely decodable codes in a binary input N-user adder channel
• New lower bounds for asymmetric and unidirectional codes
• Sharp Bounds for Optimal Decoding of Low-Density Parity-Check Codes
• A Unified Random Coding Bound
• Improved upper bounds for codes with unequal error protection
• Bounds and constructions for codes correcting unidirectional errors
• New upper bounds on the size of codes correcting asymmetric errors (Corresp.)
• scientific article; zbMATH DE number 3301962
• scientific article; zbMATH DE number 3543912

Cited in

(4)

• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
• A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
• A faster algorithm for pigeonhole equal sums
• New algorithms for pigeonhole equal subset sum

This page was built for publication: Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4566709)