On the set of uniquely decodable codes with a given sequence of code word lengths

Adam Woryna

doi:10.1016/j.disc.2016.08.013

On the set of uniquely decodable codes with a given sequence of code word lengths

Adam Woryna

Department of Mathematics (RMS/RMS1)

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

4 Citations (Scopus)

Abstract

For every natural number n≥2 and every finite sequence L of natural numbers, we consider the set UD_n(L) of all uniquely decodable codes over an n-letter alphabet with the sequence L as the sequence of code word lengths, as well as its subsets PR_n(L) and FD_n(L) consisting of, respectively, the prefix codes and the codes with finite delay. We derive the estimation for the quotient |UD_n(L)|∕|PR_n(L)|, which allows to characterize those sequences L for which the equality PR_n(L)=UD_n(L) holds. We also characterize those sequences L for which the equality FD_n(L)=UD_n(L) holds.

Original language	English
Pages (from-to)	51-57
Number of pages	7
Journal	Discrete Mathematics
Volume	340
Issue number	2
DOIs	https://doi.org/10.1016/j.disc.2016.08.013
Publication status	Published - 6 Feb 2017

Keywords

Code with finite delay
Kraft's procedure
Prefix code
Sardinas–Patterson algorithm
Uniquely decodable code

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2016.08.013

Cite this

@article{f639bea62dfa4f7b90909268845e62e5,

title = "On the set of uniquely decodable codes with a given sequence of code word lengths",

abstract = "For every natural number n≥2 and every finite sequence L of natural numbers, we consider the set UDn(L) of all uniquely decodable codes over an n-letter alphabet with the sequence L as the sequence of code word lengths, as well as its subsets PRn(L) and FDn(L) consisting of, respectively, the prefix codes and the codes with finite delay. We derive the estimation for the quotient |UDn(L)|∕|PRn(L)|, which allows to characterize those sequences L for which the equality PRn(L)=UDn(L) holds. We also characterize those sequences L for which the equality FDn(L)=UDn(L) holds.",

keywords = "Code with finite delay, Kraft's procedure, Prefix code, Sardinas{\textendash}Patterson algorithm, Uniquely decodable code",

author = "Adam Woryna",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier B.V.",

year = "2017",

month = feb,

day = "6",

doi = "10.1016/j.disc.2016.08.013",

language = "English",

volume = "340",

pages = "51--57",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - On the set of uniquely decodable codes with a given sequence of code word lengths

AU - Woryna, Adam

PY - 2017/2/6

Y1 - 2017/2/6

N2 - For every natural number n≥2 and every finite sequence L of natural numbers, we consider the set UDn(L) of all uniquely decodable codes over an n-letter alphabet with the sequence L as the sequence of code word lengths, as well as its subsets PRn(L) and FDn(L) consisting of, respectively, the prefix codes and the codes with finite delay. We derive the estimation for the quotient |UDn(L)|∕|PRn(L)|, which allows to characterize those sequences L for which the equality PRn(L)=UDn(L) holds. We also characterize those sequences L for which the equality FDn(L)=UDn(L) holds.

AB - For every natural number n≥2 and every finite sequence L of natural numbers, we consider the set UDn(L) of all uniquely decodable codes over an n-letter alphabet with the sequence L as the sequence of code word lengths, as well as its subsets PRn(L) and FDn(L) consisting of, respectively, the prefix codes and the codes with finite delay. We derive the estimation for the quotient |UDn(L)|∕|PRn(L)|, which allows to characterize those sequences L for which the equality PRn(L)=UDn(L) holds. We also characterize those sequences L for which the equality FDn(L)=UDn(L) holds.

KW - Code with finite delay

KW - Kraft's procedure

KW - Prefix code

KW - Sardinas–Patterson algorithm

KW - Uniquely decodable code

UR - https://www.scopus.com/pages/publications/84984656815

U2 - 10.1016/j.disc.2016.08.013

DO - 10.1016/j.disc.2016.08.013

M3 - Article

AN - SCOPUS:84984656815

SN - 0012-365X

VL - 340

SP - 51

EP - 57

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -

On the set of uniquely decodable codes with a given sequence of code word lengths

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this