Breadcrumbs Section. Click here to navigate to respective pages.

Chapter

Chapter

# Codes

DOI link for Codes

Codes book

# Codes

DOI link for Codes

Codes book

## ABSTRACT

If A is a non-empty finite alphabet, then A∗ stands for the set of all the possible finite words which can be formed using letters from A. With the operation of the concatenation of words A∗ is a free semi-group generated by the elements of A. The neutral element is the empty word. A non-empty subset C of A∗ is called a code if for each c1, . . . , cu, d1, . . . , dv ∈ C from

c1 · · · cu = d1 · · · dv it follows that u = v, then c1 · · · cu = d1 · · · du implies that c1 = d1, . . . , cu = du. For further details on variables codes the reader is advised to consult the classical monograph of J. Berstel and D. Perrin [4]. For a crash course on variable length codes we suggest the survey paper of V. Bruye`re and M. Latteux [14]. In order not to be in short supply of examples of codes, we describe a

way to construct codes over a binary alphabet {x, y}. Once a code C is constructed by deleting elements from C we get new codes. There are various ways to construct codes; we choose one related to factorizations. Let B = {b(1), . . . , b(s)} be a set of integers. Suppose A1, . . . , As are subsets of integers such that the sum Ai + B is direct for each i, 1 ≤ i ≤ s. This simply means that

a+ b = a′ + b′, a, a′ ∈ Ai, b, b′ ∈ B imply that a = a′, b = b′. Set

Ci = {xb(i)yxa : a ∈ Ai}, 1 ≤ i ≤ s.