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

被引：34

作者：

Chee, Yeow Meng ^{[1
]}

Kiah, Han Mao ^{[1
]}

Purkayastha, Punarbasu ^{[1
]}

Wang, Chengmin ^{[2
]}

机构：

[1] Nanyang Technol Univ, Div Math Sci, Sch Phys & Math Sci, Singapore 637371, Singapore

[2] Jiangnan Univ, Sch Sci, Wuxi 214122, Peoples R China

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2013年 / 59卷 / 07期

基金：

新加坡国家研究基金会;

关键词：

Cross-bifix-free code; Fibonacci sequence; synchronization sequence; SEARCH;

D O I：

10.1109/TIT.2013.2252952

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：4668 / 4674

页数：7

共 14 条

[1] Distributed sequences and search process [J].

Bajic, D ;

Stojanovic, J .

2004 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS, VOLS 1-7, 2004, :514-518

[2]

Bajic D, 2003, 2003 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY - PROCEEDINGS, P249

[3]

Bajic D., 2007, 2 MCM LISB PORT FEB

[4] A New Approach to Cross-Bifix-Free Sets [J].

Bilotta, Stefano ;

Pergola, Elisa ;

Pinzani, Renzo .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2012, 58 (06) :4058-4063

[5]

Dresden G. P. B., 2011, SIMPLIFIED BINET FOR

[6]

Konc J, 2007, MATCH-COMMUN MATH CO, V58, P569

[7]

LEVESQUE C, 1985, FIBONACCI QUART, V23, P290

[8] OPTIMUM FRAME SYNCHRONIZATION [J].

MASSEY, JL .

IEEE TRANSACTIONS ON COMMUNICATIONS, 1972, CO20 (02) :115-&

[9]

Miles EP., 1960, Am. Math. Mon, V67, P745, DOI [DOI 10.1080/00029890.1960.11989593, 10.1080/00029890.1960.11989593]

[10] GENERALIZED FIBONACCI NUMBERS [J].

MILLER, MD .

AMERICAN MATHEMATICAL MONTHLY, 1971, 78 (10) :1108-&

← 1 2 →