Non-Overlapping Codes

DOI10.1109/TIT.2015.2456634zbMATH Open1359.94881arXiv1303.1026OpenAlexW3100437611MaRDI QIDQ2977285FDOQ2977285

Authors: Simon R. Blackburn 

Publication date: 28 April 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We say that a $q$-ary length $n$ code is emph{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 synchronisation. More recently these codes were independently invented (under the name emph{cross-bifix-free} codes) by Baji'c and Stojanovi'c. 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 synchronisation: we provide a direct combinatorial argument to establish the bound of Chee emph{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 $qightarrowinfty$. The largest cardinality of non-overlapping codes of lengths $3$ or less is determined exactly.

Full work available at URL: https://arxiv.org/abs/1303.1026

Recommendations

• Variable-Length Non-Overlapping Codes
• Non-malleable codes
• Repeat-Free Codes
• scientific article; zbMATH DE number 3985119
• Nonrandom binary superimposed codes
• A strong non-overlapping Dyck code
• On codes that avoid specified differences
• Nonsystematic perfect codes
• scientific article; zbMATH DE number 2170443
• Intersecting codes and separating codes

Mathematics Subject Classification ID

Other types of codes (94B60)

Cited In (10)

• Title not available (Why is that?)
• Disjoint difference families and their applications
• A 2D non-overlapping code over a \(q\)-ary alphabet
• Non-overlapping matrices via Dyck words
• On factor-free Dyck words with half-integer slope
• \(q\)-ary \((1, k)\)-overlap-free codes with given restrictions
• In search of maximum non-overlapping codes
• Non-overlapping matrices
• Construction of some nonautomatic sequences by cellular automata
• Cross-bifix-free sets generation via Motzkin paths

This page was built for publication: Non-Overlapping Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977285)