Noisy Constrained Capacity

We study the classical problem of noisy constrained capacity in the case of the binary symmetric channel (BSC), namely, the capacity of a BSC whose input is a sequence from a constrained set. As stated in [4] "... while calculation of the noise-free capacity of constrained sequences is well known, the computation of the capacity of a constraint in the presence of noise ... has been an unsolved problem in the half-century since Shannon\´s landmark paper ...." We express the constrained capacity of a binary symmetric channel with (d, k)-constrained input as a limit of the top Lyapunov exponents of certain matrix random processes. We compute asymptotic approximations of the noisy constrained capacity for cases where the noise parameter epsiv is small. In particular, we show that when kles2d, the error term with respect to the constraint capacity is O(epsiv), whereas it is O(epsiv log epsiv) when k > 2d. In both cases, we compute the coefficient of the error term. We also extend previous results on the entropy of a hidden Markov process to higher-order finite memory processes.