Cross-Bifix-Free Codes Within a Constant Factor of Optimality

A cross-bifix-free code is a set of words in which no prefix of any length of any word is the suffix of any word in the set. Cross-bifix-free codes arise in the study of distributed sequences for frame synchronization. We provide a new construction of cross-bifix-free codes which generalizes the con...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2013-07, Vol.59 (7), p.4668-4674
Main Authors: Chee, Y. M., Kiah, H. M., Purkayastha, P., Chengmin Wang
Format: Article
Language:English
Subjects:
Applied sciences
Codes
Cross-bifix-free code
Estimates
Exact sciences and technology
Fibonacci sequence
Information theory
Information, signal and communications theory
Polynomials
Receivers
Reliability
Synchronization
synchronization sequence
Telecommunications and information theory
Transmitters
Upper bound
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A cross-bifix-free code is a set of words in which no prefix of any length of any word is the suffix of any word in the set. Cross-bifix-free codes arise in the study of distributed sequences for frame synchronization. We provide a new construction of cross-bifix-free codes which generalizes the construction by Bajic to longer code lengths and to any alphabet size. The codes are shown to be nearly optimal in size. We also establish new results on Fibonacci sequences, which are used in estimating the size of the cross-bifix-free codes.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2013.2252952