Encoding subshifts through sliding block codes

Abstract

Shannon’s coding theorem establishes conditions under which a given stochastic source can be encoded by a given stochastic channel with zero probability of error. One can also consider a deterministic channel, given by a function from one space of sequences to another, and ask which sources can be transmitted by that channel not just with zero error probability but in fact injectively. Working with an existing formalization of this idea in symbolic dynamics, I will present a characterization of the subshifts that can be transmitted injectively by a given sliding block code on a mixing shift of finite type (i.e. the space of sequences realizable by an ergodic Markov chain). The result generalizes a classical embedding theorem of Krieger and answers a question posed to me by Tom Meyerovitch.