On the proportion of prefix codes in the set of three-element codes

Adam Woryna

doi:10.1016/j.disc.2020.111939

On the proportion of prefix codes in the set of three-element codes

Adam Woryna

Department of Mathematics (RMS/RMS1)

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

Abstract

Let L be a finite sequence of natural numbers. In Woryna (2017, 2018), we derived some interesting properties for the ratio ρ_n,L=|PR_n(L)|∕|UD_n(L)|, where UD_n(L) denotes the set of all codes over an n-letter alphabet and with length distribution L, and PR_n(L)⊆UD_n(L) is the corresponding subset of prefix codes. In the present paper, we study the case when the length distributions are three-element sequences. We show in this case that the ratio ρ_n,L is always greater than α_n, where α_n=(n−2)∕n for n>2 and α₂=1∕6. Moreover, the number α_n is the best possible lower bound for this ratio, as the length distributions of the form L=(1,1,c) and L=(1,2,c) assure that the ratios asymptotically approach α_n. Namely, if L=(1,1,c), then ρ_n,L tends to (n−2)∕n with c→∞, and, if L=(1,2,c), then ρ_2,L tends to 1∕6 with c→∞.

Original language	English
Article number	111939
Journal	Discrete Mathematics
Volume	343
Issue number	8
DOIs	https://doi.org/10.1016/j.disc.2020.111939
Publication status	Published - Aug 2020

Keywords

Code
Kraft inequality
Length distribution of a code
Prefix code
Sardinas–Patterson algorithm

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2020.111939

Cite this

@article{a4f03b59bf3c4f38b73d8201e717fd99,

title = "On the proportion of prefix codes in the set of three-element codes",

abstract = "Let L be a finite sequence of natural numbers. In Woryna (2017, 2018), we derived some interesting properties for the ratio ρn,L=|PRn(L)|∕|UDn(L)|, where UDn(L) denotes the set of all codes over an n-letter alphabet and with length distribution L, and PRn(L)⊆UDn(L) is the corresponding subset of prefix codes. In the present paper, we study the case when the length distributions are three-element sequences. We show in this case that the ratio ρn,L is always greater than αn, where αn=(n−2)∕n for n>2 and α2=1∕6. Moreover, the number αn is the best possible lower bound for this ratio, as the length distributions of the form L=(1,1,c) and L=(1,2,c) assure that the ratios asymptotically approach αn. Namely, if L=(1,1,c), then ρn,L tends to (n−2)∕n with c→∞, and, if L=(1,2,c), then ρ2,L tends to 1∕6 with c→∞.",

keywords = "Code, Kraft inequality, Length distribution of a code, Prefix code, Sardinas–Patterson algorithm",

author = "Adam Woryna",

note = "Publisher Copyright: {\textcopyright} 2020 The Author(s)",

year = "2020",

month = aug,

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

language = "English",

volume = "343",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "8",

}

TY - JOUR

T1 - On the proportion of prefix codes in the set of three-element codes

AU - Woryna, Adam

PY - 2020/8

Y1 - 2020/8

N2 - Let L be a finite sequence of natural numbers. In Woryna (2017, 2018), we derived some interesting properties for the ratio ρn,L=|PRn(L)|∕|UDn(L)|, where UDn(L) denotes the set of all codes over an n-letter alphabet and with length distribution L, and PRn(L)⊆UDn(L) is the corresponding subset of prefix codes. In the present paper, we study the case when the length distributions are three-element sequences. We show in this case that the ratio ρn,L is always greater than αn, where αn=(n−2)∕n for n>2 and α2=1∕6. Moreover, the number αn is the best possible lower bound for this ratio, as the length distributions of the form L=(1,1,c) and L=(1,2,c) assure that the ratios asymptotically approach αn. Namely, if L=(1,1,c), then ρn,L tends to (n−2)∕n with c→∞, and, if L=(1,2,c), then ρ2,L tends to 1∕6 with c→∞.

AB - Let L be a finite sequence of natural numbers. In Woryna (2017, 2018), we derived some interesting properties for the ratio ρn,L=|PRn(L)|∕|UDn(L)|, where UDn(L) denotes the set of all codes over an n-letter alphabet and with length distribution L, and PRn(L)⊆UDn(L) is the corresponding subset of prefix codes. In the present paper, we study the case when the length distributions are three-element sequences. We show in this case that the ratio ρn,L is always greater than αn, where αn=(n−2)∕n for n>2 and α2=1∕6. Moreover, the number αn is the best possible lower bound for this ratio, as the length distributions of the form L=(1,1,c) and L=(1,2,c) assure that the ratios asymptotically approach αn. Namely, if L=(1,1,c), then ρn,L tends to (n−2)∕n with c→∞, and, if L=(1,2,c), then ρ2,L tends to 1∕6 with c→∞.

KW - Code

KW - Kraft inequality

KW - Length distribution of a code

KW - Prefix code

KW - Sardinas–Patterson algorithm

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

U2 - 10.1016/j.disc.2020.111939

DO - 10.1016/j.disc.2020.111939

M3 - Article

AN - SCOPUS:85083891340

SN - 0012-365X

VL - 343

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 8

M1 - 111939

ER -

On the proportion of prefix codes in the set of three-element codes

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this