CHAPTER 5 - FINITE-STATE CODES

Summary

In §2.5 we saw why it is useful to transform arbitrary binary sequences into sequences that obey certain constraints. In particular, we used Modified Frequency Modulation to code binary sequences into sequences from the (1,3) run-length limited shift. This gave a more efficient way to store binary data so that it is not subject to clock drift or intersymbol interference.

Different situations in data storage and transmission require different sets of constraints. Thus our general problem is to find ways to transform or encode sequences from the full n-shift into sequences from a preassigned sofic shift X. In this chapter we will describe one encoding method called a finite-state code. The main result, the Finite-State Coding Theorem of §5.2, says that we can solve our coding problem with a finite-state code precisely when h(X) ≥ log n. Roughly speaking, this condition simply requires that X should have enough “information capacity” to encode the full n-shift.

We will begin by introducing in §5.1 two special kinds of labelings needed for finite-state codes. Next, §5.2 is devoted to the statement and consequences of the Finite-State Coding Theorem. Crucial to the proof is the notion of an approximate eigenvector, which we discuss in §5.3. The proof itself occupies §5.4, where an approximate eigenvector is used to guide a sequence of state splittings that converts a presentation of X into one with out-degree at least n at every state.