We consider the capacity of binary deletion channels, where bits are deleted independently with probability d. We improve significantly upon the framework used in [1, 2] to lower bound this capacity, by utilizing a stronger definition of a typical output from the channel. In this paper, we specifically focus on codeword sequences given by a first order Markov chain. Our results give the best bounds on the capacity for all values of d; in particular, for d ≥ 0.65, we surpass Ullman's combinatorial upper bound for channels with an asymptotic fraction of d synchronization errors. Hence our results explicitly indicate a need for new upper bounds in the case of channels with i.i.d. synchronization errors.
展开▼
