Improved Upper and Lower Bounds on the Capacity of the Binary Deletion Channel
share
The binary deletion channel with deletion probability d (BDC_d) is a random channel that deletes each bit of the input message i.i.d with probability d. It has been studied extensively as a canonical example of a channel with synchronization errors. Perhaps the most important question regarding the BDC is determining its capacity. Mitzenmacher and Drinea (ITIT 2006) and Kirsch and Drinea (ITIT 2009) show a method by which distributions on run lengths can be converted to codes for the BDC, yielding a lower bound of ๐(BDC_d) > 0.1185 ยท (1-d). Fertonani and Duman (ITIT 2010), Dalai (ISIT 2011) and Rahmati and Duman (ITIT 2014) use computer aided analyses based on the Blahut-Arimoto algorithm to prove an upper bound of ๐(BDC_d) < 0.4143ยท(1-d) in the high deletion probability regime (d > 0.65). In this paper, we show that the Blahut-Arimoto algorithm can be implemented with a lower space complexity, allowing us to extend the upper bound analyses, and prove an upper bound of ๐(BDC_d) < 0.3745 ยท(1-d) for all d โฅ 0.68. Furthermore, we show that an extension of the Blahut-Arimoto algorithm can also be used to select better run length distributions for Mitzenmacher and Drinea's construction, yielding a lower bound of ๐(BDC_d) > 0.1221 ยท (1 - d).
READ FULL TEXT