Generalized Forms of the Kraft Inequality for Finite-State Encoders

We derive a few extended versions of the Kraft inequality for information lossless finite-state encoders. The main basic contribution is in defining a notion of a Kraft matrix and in establishing the fact that a necessary condition for information losslessness of a finite-state encoder is that none of the eigenvalues of this matrix have modulus larger than unity, or equivalently, the spectral radius of the Kraft matrix cannot exceed one. We then derive several equivalent forms of this condition, which are based on well-known formulas for spectral radius. Even stronger results are presented for the important special case where the finite-state encoder is assumed irreducible. Finally, two extensions are outlined—one concerns the case of side information available to both encoder and decoder, and the other is for lossy compression.