Sharper upper bounds for unbalanced Uniquely Decodable Code Pairs

Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)

Abstract

Two sets A, B ⊆ {0, 1}n form a Uniquely Decodable Code Pair (UDCP) if every pair a ⋯ A, b ⋯ B yields a distinct sum a+b, where the addition is over ℤn. We show that every UDCP A, B, with |A| = 2(1-ϵ)n and |B| = 2βn, satisfies equation. For sufficiently small ϵ, 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 ϵ approaches 0.

Original languageEnglish
Title of host publicationProceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
PublisherIEEE
Pages335-339
Number of pages5
Volume2016-August
ISBN (Electronic)9781509018062
DOIs
Publication statusPublished - 10 Aug 2016
MoE publication typeA4 Article in a conference publication
EventIEEE International Symposium on Information Theory - Barcelona, Spain
Duration: 10 Jul 201615 Jul 2016
http://www.isit2016.org/

Conference

ConferenceIEEE International Symposium on Information Theory
Abbreviated titleISIT
CountrySpain
CityBarcelona
Period10/07/201615/07/2016
Internet address

Fingerprint

Dive into the research topics of 'Sharper upper bounds for unbalanced Uniquely Decodable Code Pairs'. Together they form a unique fingerprint.

Cite this