6 - Bifix codes

Summary

The object of this chapter is to describe the structure of maximal bifix codes. This family of codes has quite remarkable properties and can be described in a rather satisfactory manner.

As in the rest of this book, we will work here within the family of thin codes. As we will see, this family contains all the usual examples, and most of the fundamental properties extend to this family when they hold in the simple (that is, finite or recognizable) case.

To each thin maximal bifix code, two basic parameters will be associated: its degree and its kernel. The degree is a positive integer which is, as we will see in Chapter 9, the degree of a permutation group associated with the code. The kernel is the set of codewords which are proper factors of some codeword. We shall prove that these two parameters characterize a thin maximal bifix code.

In the first section, we introduce the notion of a parse of a word with respect to a bifix code. It allows us to define an integer-valued function called the indicator of a bifix code. This function will be quite useful in this and later chapters.

In the second section, we give a series of equivalent conditions for a thin code to be maximal bifix. The fact that thin maximal bifix codes are extremal objects is reflected in the observation that a subset of their properties suffices to characterize them completely. We also give a transformation (called internal transformation) which preserves the family of maximal bifix codes.