Some properties of Fix-Free Codes

Abstract

A (variable length) code is fix -- free code if no codeword is a prefix or a suffix of any other. A database constructed by a fix -- free code is instantaneously decodeable from both sides. We discuss the existence of fix -- free codes, relations to the deBrujin Network and shadow problems. Particulary we draw attention to a remarkable conjecture: For numbers l 1 ; : : : ; l N satisfying N P i=1 2 \\Gammal i 3 4 a fix--free code with lengths l 1 ; : : : l N exists. If true, this bound is best possible. email:[e-mail] y email:[e-mail] 1 BASIC DEFINITIONS 2 1 Basic Definitions For a finite set X = f0; : : : ; a \\Gamma 1g, called alphabet, we form X n = n Q 1 X , the words of length n, with letters from X and X = 1 S n=0 X n , the set of all finite length words including the empty word e from X 0 = feg, X is equipped with an associative operation, called concatenation, defined by (x 1 ; : : : ; x n )(y 1...