检索结果-内蒙古大学图书馆

On the maximum size of variable-length non-overlapping codes

DESIGNS codeS AND CRYPTOGRAPHY 2025年第4期93卷 871-878页

作者： Wang, Geyang Wang, Qi Univ Maryland Dept Elect & Comp Engn College Pk MD 20742 USA Southern Univ Sci & Technol Dept Comp Sci & Engn Shenzhen 518055 Guangdong Peoples R China Southern Univ Sci & Technol Natl Ctr Appl Math Shenzhen Shenzhen 518055 Guangdong Peoples R China

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

来源：评论

学校读者我要写书评

暂无评论

Two-dimensional q-ary non-overlapping codes

引用

CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES 2025年第1期17卷 265-281页

作者： Cai, Qinlin Wang, Xiaomiao Feng, Tao Ningbo Univ Sch Math & Stat Ningbo 315211 Peoples R China Beijing Jiaotong Univ Sch Math & Stat Beijing 100044 Peoples R China

Two matrices are said to be non-overlapping if there is no way to put one of them on the other one such that the top-left corner of one matrix coincides with the bottom-right corner of another matrix, or the top-right corner of one matrix coincides with the bottom-left corner of another matrix. A two-dimensional non-overlapping code is a set of mxn matrices (called codewords) over a q-ary alphabet if every pair of matrices within the set (whether identical or not) are non-overlapping. We provide a new construction for two-dimensional q-ary non-overlapping codes and compare sizes of our codes and those in the literature. Especially, the set of binary non-overlapping matrices obtained from our construction can be listed in a Gray code sense. We also initialize the study on two-dimensional non-expandable non-overlapping codes over a q-ary alphabet for any q>2 by generalizing the two-dimensional binary non-expandable non-overlapping codes in the literature.

关键词： non-overlapping code Two-dimensional non-overlapping matrix non-expandable Gray code Cross-bifix-free

来源：评论

学校读者我要写书评

暂无评论

On maximal almost balanced non-overlapping codes and non-overlapping codes with restricted run-lengths ( vol 44 , 109 , 2025)

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2025年第2期44卷 1-19页

作者： Stanovnik, Lidija Moskon, Miha Mraz, Miha Univ Ljubljana Fac Comp & Informat Sci Vecna Pot 113 Ljubljana 1000 Slovenia

This paper concerns non-overlapping codes, block codes motivated by synchronisation and DNA-based storage applications. Most existing constructions of these codes do not account for the restrictions posed by the physical properties of communication channels. If undesired sequences are not avoided, the system using the encoding may start behaving incorrectly. Hence, we aim to characterise all non-overlapping codes satisfying two additional constraints. For the first constraint, where approximately half of the letters in each word are positive, we derive necessary and sufficient conditions for the code’s non-expandability and improve known bounds on its maximum size. We also determine exact values for the maximum sizes of polarity-balanced non-overlapping codes having small block and alphabet sizes. For the other constraint, where long sequences of consecutive equal symbols lead to undesired behaviour, we derive bounds and constructions of constrained non-overlapping codes. Moreover, we provide constructions of non-overlapping codes that satisfy both constraints and analyse the sizes of the obtained codes.

关键词： (almost) balanced code Dyck words non-overlapping code Restricted words Run-length limit

来源：评论

学校读者我要写书评

暂无评论

codes with restricted overlaps: expandability, constructions, and bounds

引用

JOURNAL OF APPLIED MATHEMATICS AND COMPUTING 2025年 1-26页

作者： Stanovnik, Lidija Univ Ljubljana Fac Comp & Informat Sci Vecna Pot 113 Ljubljana 1000 Slovenia

Consider a q-ary block code satisfying the property that no l-letters long codeword's prefix occurs as a suffix of any codeword for l inside some interval. We determine a general upper bound on the maximum size of these codes and a tighter bound for codes where overlaps with lengths not exceeding k are prohibited. We then provide constructions for codes with various restrictions on overlap lengths and use them to determine lower bounds on the maximum sizes. In particular, we construct (1,k)-overlap-free codes where k >= n/2 and n denotes the block size, expand a known construction of (k, n-1)-overlap-free codes, and combine the ideas behind both constructions to obtain (t(1),t(2))-overlap-free codes and codes that are simultaneously (1,k) and (n-k, n-1)-overlap-free for some . In the case when overlaps of lengths between 1 and k are prohibited, we complete the characterisation of non-expandable codes initiated by Cai, Wang, and Feng (IEEE Trans Inf Theory, 2023).

关键词： (1,k)-overlap-free code (t(1),t(2))-overlap-free code non-overlapping code Weakly mutually uncorrelated code

来源：评论

学校读者我要写书评

暂无评论

q-ary (1, k)-overlap-free codes with given restrictions

引用

DISCRETE MATHEMATICS 2025年第1期348卷

作者： Wang, Xiaomiao Fang, Yu Feng, Tao Ningbo Univ Sch Math & Stat Ningbo 315211 Peoples R China Beijing Jiaotong Univ Sch Math & Stat Beijing 100044 Peoples R China

Two words u and v have a t-overlap if the length t prefix of u is equal to the length t suffix of v, or vice versa. A code C is t-overlap-free if no two words u and v in C (including u = v) have a t-overlap. A code of length n is said to be (t(1), t(2))-overlap-free if it is t-overlap-free for all t such that 1 <= t(1) <= t <= t(2) <= n - 1. A (1, n - 1)-overlap-free code of length n is called non-overlapping, which has applications in DNA-based data storage systems and frame synchronization. In this paper, we initialize the study for codes of length n which are simultaneously (1, k)-overlap-free and (n - k, n - 1)-overlap-free, and establish lower and upper bounds for the size of balanced and error-correcting (1, k)-overlap-free codes. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： (1,k)-overlap-free-code non-overlapping code Balanced code Error-correcting code

来源：评论

学校读者我要写书评

暂无评论

non-overlapping codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2015年第9期61卷 4890-4894页

作者： Blackburn, Simon R. Univ London Royal Holloway & Bedford New Coll Dept Math Egham TW20 0EX Surrey England

We say that a q-ary length n code is non-overlapping if the set of non-trivial prefixes of codewords and the set of non-trivial suffices of codewords are disjoint. These codes were first studied by Levenshtein in 1964, motivated by applications in synchronization. More recently these codes were independently invented (under the name cross-bifix-free codes) by Bajic and Stojanovic. We provide a simple construction for a class of non-overlapping codes which has optimal cardinality whenever n divides q. Moreover, for all parameters n and q, we show that a code from this class is close to optimal, in the sense that it has cardinality within a constant factor of an upper bound due to Levenshtein from 1970. Previous constructions have cardinality within a constant factor of the upper bound only when q is fixed. Chee, Kiah, Purkayastha, and Wang showed that a q-ary length n non-overlapping code contains at most q(n)/(2n-1) codewords;this bound is weaker than the Levenshtein bound. Their proof appealed to the application in synchronization: we provide a direct combinatorial argument to establish the bound of Chee et al. We also consider codes of short length, finding the leading term of the maximal cardinality of a non-overlapping code when n is fixed and q ->infinity. The largest cardinality of non-overlapping codes of lengths 3 or less is determined exactly.

关键词： non-overlapping code cross-bifix-free code comma-free code

来源：评论

学校读者我要写书评

暂无评论

Q-Ary non-overlapping codes: A Generating Function Approach

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2022年第8期68卷 5154-5164页

作者： Wang, Geyang Wang, Qi Southern Univ Sci & Technol Res Inst Trustworthy Autonomous Syst Dept Comp Sci & Engn Shenzhen 518055 Peoples R China Southern Univ Sci & Technol Dept Comp Sci & Engn Shenzhen 518055 Peoples R China Southern Univ Sci & Technol Natl Ctr Appl Math Shenzhen Shenzhen 518055 Peoples R China

non-overlapping codes are a set of codewords in boolean OR(n >= 2) Z(q)(n), where Z(q) = {0, 1, ..., q - 1}, such that, the prefix of each codeword is not a suffix of any codeword in the set, including itself;and for variable-length codes, a codeword does not contain any other codeword as a subword. In this paper, we investigate a generic method to generalize binary codes to q-ary for q > 2, and analyze this generalization on the two constructions given by Levenshtein (also by Gilbert;Chee, Kiah, Purkayastha, and Wang) and Bilotta, respectively. The generalization on the former construction gives large non-expandable fixed-length non-overlapping codes whose size can be explicitly determined;the generalization on the later construction is the first attempt to generate q-ary variable-length non-overlapping codes. More importantly, this generic method allows us to utilize the generating function approach to analyze the cardinality of the underlying q-ary non-overlapping codes. The generating function approach not only enables us to derive new results, e.g., recurrence relations on their cardinalities, new combinatorial interpretations for the constructions, and the limit superior of their cardinalities for some special cases, but also greatly simplifies the arguments for these results. Furthermore, we give an exact formula for the number of fixed-length words that do not contain the codewords in a variable-length non-overlapping code as subwords. This thereby solves an open problem by Bilotta and induces a recursive upper bound on the maximum size of variable-length non-overlapping codes.

关键词： non-overlapping code variable-length code generating function

来源：评论

学校读者我要写书评

暂无评论

In search of maximum non-overlapping codes

引用

DESIGNS codeS AND CRYPTOGRAPHY 2024年第3期92卷 833-862页

作者： Stanovnik, Lidija Moskon, Miha Mraz, Miha Univ Ljubljana Fac Comp & Informat Sci Vecna Pot 113 Ljubljana 1000 Slovenia

non-overlapping codes are block codes that have arisen in diverse contexts of computer science and biology. Applications typically require finding non-overlapping codes with large cardinalities, but the maximum size of non-overlapping codes has been determined only for cases where the codeword length divides the size of the alphabet, and for codes with codewords of length two or three. For all other alphabet sizes and codeword lengths no computationally feasible way to identify non-overlapping codes that attain the maximum size has been found to date. Herein we characterize maximal non-overlapping codes. We formulate the maximum non-overlapping code problem as an integer optimization problem and determine necessary conditions for optimality of a non-overlapping code. Moreover, we solve several instances of the optimization problem to show that the hitherto known constructions do not generate the optimal codes for many alphabet sizes and codeword lengths. We also evaluate the number of distinct maximum non-overlapping codes.

关键词： non-overlapping code Cross-bifix-free code Mutually uncorrelated code Strong comma-free code

来源：评论

学校读者我要写书评

暂无评论

Constructions and Bounds for q-Ary (1, k)-Overlap-Free codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第6期70卷 4439-4444页

作者： Cai, Qinlin Wang, Xiaomiao Feng, Tao Ningbo Univ Sch Math & Stat Ningbo 315211 Peoples R China Beijing Jiaotong Univ Sch Math & Stat Beijing 100044 Peoples R China

A(1, k)-overlap-free code, motivated by applications in DNA-based data storage systems and synchronization between communication devices, is a set of words in which no prefix of length t of any word is the suffix of any word for every integer t such that1 <= t <= k. A(1, n-1)-overlap-free code of length n is said to be non-overlapping. We provide a construction for q-ary(1, k)-overlap-free codes of length2k, which can be viewed as a generalization of the Zero Block Construction presented by Blackburn, Esfahani, Kreher and Stinson recently over a binary alphabet, and analyze the asymptotic behavior of their sizes. When n >= 2k, an explicit general lower bound and an asymptotic lower bound for the size of an optimal q-ary (1, k)-overlap-free code of length n are presented. The exact value of the maximum size of q-ary (1,2)-overlap-free codes of length n is determined for any n >= 4, and a construction for q-ary (1, k)-overlap-free codes of length k+ 2 is given.

关键词： codes DNA Synchronization Behavioral sciences Symbols Upper bound Memory (1, k)-overlap-free code non-overlapping code Fibonacci number

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：