Sharper upper bounds for unbalanced uniquely decodable code pairs

Per Austrin; Petteri Kaski; Mikko Koivisto; Jesper Nederlof

doi:10.1109/TIT.2017.2688378

Sharper upper bounds for unbalanced uniquely decodable code pairs

Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof

Research output: Contribution to journal › Article › Academic › peer-review

8 Citations (Scopus)

Abstract

Two sets of 0-1 vectors of fixed length form a uniquely decodeable code pair if their Cartesian product is of the same size as their sumset, where the addition is pointwise over integers. For the size of the sumset of such a pair, van Tilborg has given an upper bound in the general case. Urbanke and Li, and later Ordentlich and Shayevitz, have given better bounds in the unbalanced case, that is, when either of the two sets is sufficiently large. Improvements to the latter bounds are presented.

Original language	English
Article number	7888502
Pages (from-to)	1368-1373
Number of pages	6
Journal	IEEE Transactions on Information Theory
Volume	64
Issue number	2
DOIs	https://doi.org/10.1109/TIT.2017.2688378
Publication status	Published - Feb 2018

Bibliographical note

to appear

Funding

Manuscript received September 5, 2016; revised February 8, 2017; accepted March 11, 2017. Date of publication March 28, 2017; date of current version January 18, 2018. P. Austrin was supported by the Swedish Research Council, under Grant 621-2012-4546. P. Kaski was supported by the European Research Council, under Grant 338077. M. Koivisto was supported by the Academy of Finland, under Grant 276864. J. Nederlof was supported by the NWO VENI under Project 639.021.438. This paper was presented at the 2016 IEEE International Symposium on Information Theory. (Corresponding Author: Mikko Koivisto.) P. Austrin is with the School of Computer Science and Communication, KTH Royal Institute of Technology, 114 28 Stockholm, Sweden (e-mail: [email protected]).

Keywords

Additive combinatorics
Binary adder channel
Isoperimetric inequality
Uniquely decodeable code pair
Zero-error capacity

Access to Document

10.1109/TIT.2017.2688378

Cite this

@article{b729e1908b374215909e1ef29dfbde0a,

title = "Sharper upper bounds for unbalanced uniquely decodable code pairs",

abstract = "Two sets of 0-1 vectors of fixed length form a uniquely decodeable code pair if their Cartesian product is of the same size as their sumset, where the addition is pointwise over integers. For the size of the sumset of such a pair, van Tilborg has given an upper bound in the general case. Urbanke and Li, and later Ordentlich and Shayevitz, have given better bounds in the unbalanced case, that is, when either of the two sets is sufficiently large. Improvements to the latter bounds are presented.",

keywords = "Additive combinatorics, Binary adder channel, Isoperimetric inequality, Uniquely decodeable code pair, Zero-error capacity",

author = "Per Austrin and Petteri Kaski and Mikko Koivisto and Jesper Nederlof",

note = "to appear",

year = "2018",

month = feb,

doi = "10.1109/TIT.2017.2688378",

language = "English",

volume = "64",

pages = "1368--1373",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers",

number = "2",

}

TY - JOUR

T1 - Sharper upper bounds for unbalanced uniquely decodable code pairs

AU - Austrin, Per

AU - Kaski, Petteri

AU - Koivisto, Mikko

AU - Nederlof, Jesper

N1 - to appear

PY - 2018/2

Y1 - 2018/2

N2 - Two sets of 0-1 vectors of fixed length form a uniquely decodeable code pair if their Cartesian product is of the same size as their sumset, where the addition is pointwise over integers. For the size of the sumset of such a pair, van Tilborg has given an upper bound in the general case. Urbanke and Li, and later Ordentlich and Shayevitz, have given better bounds in the unbalanced case, that is, when either of the two sets is sufficiently large. Improvements to the latter bounds are presented.

AB - Two sets of 0-1 vectors of fixed length form a uniquely decodeable code pair if their Cartesian product is of the same size as their sumset, where the addition is pointwise over integers. For the size of the sumset of such a pair, van Tilborg has given an upper bound in the general case. Urbanke and Li, and later Ordentlich and Shayevitz, have given better bounds in the unbalanced case, that is, when either of the two sets is sufficiently large. Improvements to the latter bounds are presented.

KW - Additive combinatorics

KW - Binary adder channel

KW - Isoperimetric inequality

KW - Uniquely decodeable code pair

KW - Zero-error capacity

UR - http://www.scopus.com/inward/record.url?scp=85040946882&partnerID=8YFLogxK

U2 - 10.1109/TIT.2017.2688378

DO - 10.1109/TIT.2017.2688378

M3 - Article

SN - 0018-9448

VL - 64

SP - 1368

EP - 1373

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 2

M1 - 7888502

ER -

Sharper upper bounds for unbalanced uniquely decodable code pairs

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this