3
$\begingroup$

The book Theory of codes by J. Berstel and D. Perrin from 1985 studies variable-length codes. The focus is less on error-correction and compression, but more on algebraic properties, synchronization and connections to automata (especially unambiguous transducers). A code over a finite alphabet $A$ is any subset $X$ of the free monoid $A^*$ generated by $A$ which satisfies:

If $x_1\dots x_n=y_1\dots y_m$ with $x_i,y_j\in X$, then $n=m$ and $x_t =y_t$ for $t=1,...,n$,

or equivalently, any subset $X$ of $A^*$ which is of the form $h(B)$, where $h: B^* \to A^*$ is an injective morphism (and $B$ need not be finite).

A key insight for me was that codes in this sense are well behaved under composition, and that a suitable automaton (for a prefix code, a deterministic automaton is suitable) can decode such a code without delay, i.e. each symbol can be decoded as soon as its complete code has been transmitted, no need to wait for the beginning of the code for the next symbol.

However, this nice theory fails to capture codes like the Morse code, where a long pause is used to separate individual codes. Separators somehow don't fit into the given framework:

You probably agree that there is no block code which can encode all integers. So we could use a prefix code to encode integers. But then a deterministic machine is no longer able to read the numbers backwards. We could use a separator, which actually works, but somehow doesn’t fit into the framework of (pure) codes (for whatever reason).

One idea to force separators into the given framework is to consider alternating codes. Alternating codes are used for example in fax encoding of BW images, where the run-lengths of black and while pixels alternate, and are encoded by two different codes, because the statistical distributions of run-lengths for black and while pixels are different.

A general question concerns the need for this long introduction: The writing style of J. Berstel, D. Perrin and C. Reutenauer is fine for me, but the length and depth of their presentations makes them less suitable for a cursory introduction to the subject, and hence also less suitable as a place to link to for the basic definitions and concepts. Is there a nice introduction to this subject online that I could link to instead? (I linked to the review of their book instead of the book itself, because the review at least tries to give definitions of some basic concepts.)


I tried several definitions of alternating codes, and guess that the following definition should work fine: An alternating code over a finite alphabet $A$ is any pair of subsets $(X,Y)$ of $A^*$ such that $XY$ has no duplicate elements (as multiset) and is a code over $A$. Here "should work fine" means that I hope the following to be true:

  • A pair of subsets $(X,Y)$ of $A^*$ is an alternating code iff $(Y,X)$ is an alternating code.
  • If $(X,Y)$ is an alternating code and $Y$ is a prefix code, then $XY$ is a prefix code.

Is it true? Is there a better definition of alternating codes? (One issue is the behavior under composition. I wonder how to force separators into the given framework without degrading the behavior under composition.)

$\endgroup$
  • $\begingroup$ It is not true that "If $(X,Y)$ is an alternating code and $Y$ is a prefix code, then $XY$ is a prefix code." The counterexample is to use $Y=A$, which is even a block code, and some suffix code for $X$, which is not prefix. $\endgroup$ – Thomas Klimpel Sep 20 '16 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.