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 inputs are sequences chosen from a constrained set. Motivated by a result of Ordentlich and Weissman in [28], we derive an asymptotic formula (when the noise parameter is small) for the entropy rate of a hidden Markov chain, observed when a Markov chain passes through a BSC. Using this result we establish an asymptotic formula for the capacity of a BSC with input process supported on an irreducible flnite type constraint, as the noise parameter tends to zero. 1. Introduction and Background. Let X;Y be discrete random variables with alphabet X;Y and joint probability mass function pX;Y (x;y) 4 P(X = x;Y = y), x 2 X;y 2 Y (for notational simplicity, we will write p(x;y) rather than pX;Y (x;y), similarly p(x);p(y) rather than pX(x);pY (y), respectively, when it is clear from the context). The entropy H(X) of the discrete random variable X, which measures the level of uncertainty of X, is deflned as (in this paper log is taken to mean the natural logarithm)
['Guangyue Han', 'Brian Marcus']
Asymptotics of Input-Constrained Binary Symmetric Channel Capacity