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

Katedra Matematyki (RMS/RMS1)

Wyniki badań: Wkład do czasopisma › Artykuł › recenzja

4 Cytowania z bazy Scopus

Abstrakt

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.

Język oryginału	angielski
Strony (od–do)	51-57
Liczba stron	7
Czasopismo	Discrete Mathematics
Tom	340
Numer wydania	2
Identyfikatory DOI	https://doi.org/10.1016/j.disc.2016.08.013
Status publikacji	Opublikowano - 6 lut 2017

Obszary tematyczne ASJC Scopus

Informatyka teoretyczna
Matematyka dyskretna i kombinatoryka

Uzyskaj dostęp do dokumentu

10.1016/j.disc.2016.08.013

Inne pliki i linki

Link do publikacji w Scopus

Cytowanie

@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

Abstrakt

Obszary tematyczne ASJC Scopus

Uzyskaj dostęp do dokumentu

Inne pliki i linki

Fingerprint

Cytowanie