南方科技大学知识苑(SUSTech KC): On the maximum size of variable-length non-overlapping codes

题名	On the maximum size of variable-length non-overlapping codes
作者	Wang, Geyang 1; Wang, Qi2,3
通讯作者	Wang, Qi
发表日期	2024-06-01
DOI	10.1007/s10623-024-01445-3
发表期刊	DESIGNS CODES AND CRYPTOGRAPHY 影响因子和分区
ISSN	0925-1022
EISSN	1573-7586
摘要	Non-overlapping codes are a set of codewords such that any nontrivial prefix of each codeword is not a nontrivial suffix of any codeword in the set, including itself. If the lengths of the codewords are variable, it is additionally required that every codeword is not contained in any other codeword as a subword. Let C(n, q) be the maximum size of a fixed-length non-overlapping code of length n over an alphabet of size q. The upper bound on C(n, q) has been well studied. However, the nontrivial upper bound on the maximum size of variable-length non-overlapping codes whose codewords have length at most n remains open. In this paper, by establishing a link between variable-length non-overlapping codes and fixed-length ones, we are able to show that the size of a q-ary variable-length non-overlapping code is upper bounded by C(n, q). Furthermore, we prove that the minimum average codeword length of a q-ary variable-length non-overlapping code with cardinality (C) over tilde, is asymptotically no shorter than n-2 as q approaches infinity, where n is the smallest integer such that C(n-1,q) < (C)over tilde> <= C(n, q)
关键词	Non-overlapping code Variable-length Fixed-length Prefix code
相关链接	[来源记录]
收录类别	SCI ; EI
语种	英语
学校署名	通讯
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Theory & Methods ; Mathematics, Applied
WOS记录号	WOS:001254168100001
出版者	SPRINGER
ESI学科分类	COMPUTER SCIENCE
来源库	Web of Science
引用统计
成果类型	期刊论文
条目标识符	http://sustech.caswiz.com/handle/2SGJ60CL/787392
专题	工学院_计算机科学与工程系南方科技大学
作者单位	1.Univ Maryland, Dept Elect & Comp Engn, College Pk, MD 20742 USA 2.Southern Univ Sci & Technol, Dept Comp Sci & Engn, Shenzhen 518055, Guangdong, Peoples R China 3.Southern Univ Sci & Technol, Natl Ctr Appl Math Shenzhen, Shenzhen 518055, Guangdong, Peoples R China
通讯作者单位	计算机科学与工程系; 南方科技大学
推荐引用方式 GB/T 7714	Wang, Geyang,Wang, Qi. On the maximum size of variable-length non-overlapping codes[J]. DESIGNS CODES AND CRYPTOGRAPHY,2024.
APA	Wang, Geyang,&Wang, Qi.(2024).On the maximum size of variable-length non-overlapping codes.DESIGNS CODES AND CRYPTOGRAPHY.
MLA	Wang, Geyang,et al."On the maximum size of variable-length non-overlapping codes".DESIGNS CODES AND CRYPTOGRAPHY (2024).