Achievable rates for noisy channels with synchronization errors

We develop several lower bounds on the capacity of binary input symmetric output channels with synchronization errors, which also suffer from other types of impairments such as substitutions, erasures, additive white Gaussian noise (AWGN), etc. More precisely, we show that if a channel suffering from synchronization errors as well as other type of impairments can be decomposed into a cascade of two component channels where the first one is another channel with synchronization errors and the second one is a memoryless channel (with no synchronization errors), a lower bound on the capacity of the original channel in terms of the capacity of the component synchronization error channel can be derived. A primary application of our results is that we can employ any lower bound derived on the capacity of the component synchronization error channel to find lower bounds on the capacity of the (original) noisy channel with synchronization errors. We apply the general ideas to several specific classes of channels such as synchronization error channels with erasures and substitutions, with symmetric q-ary outputs and with AWGN explicitly, and obtain easy-to-compute bounds. We illustrate that, with our approach, it is possible to derive tighter capacity lower bounds compared to the currently available bounds in the literature for certain classes of channels, e.g., deletion/substitution channels and deletion/AWGN channels (for certain signal-to-noise ratio (SNR) ranges).