</script> The purpose of this survey is to describe recent progress in the study of the binary deletion channel and related channels with synchronization errors, including a clear description of open problems in this area, with the hope of spurring further research. As an example, while the capacity of the binary symmetric error channel and the binary erasure channel have been known since Shannon, we still do not have a closed-form description of the capacity of the binary deletion channel. We highlight a recent result that shows that the capacity is at least ((1-p)/9) when each bit is deleted independently with fixed probability (p).">
Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 6 (2009) open journal systems 


A survey of results for deletion channels and related synchronization channels

Michael Mitzenmacher, Harvard School of Engineering and Applied Sciences


Abstract
The purpose of this survey is to describe recent progress in the study of the binary deletion channel and related channels with synchronization errors, including a clear description of open problems in this area, with the hope of spurring further research. As an example, while the capacity of the binary symmetric error channel and the binary erasure channel have been known since Shannon, we still do not have a closed-form description of the capacity of the binary deletion channel. We highlight a recent result that shows that the capacity is at least \((1-p)/9\) when each bit is deleted independently with fixed probability \(p\).

AMS 2000 subject classifications: Primary 94B50; secondary 68P30.

Keywords: Deletion channels, synchronization channels, capacity bounds, random subsequences.

Creative Common LOGO

Full Text: PDF
Mitzenmacher, Michael, A survey of results for deletion channels and related synchronization channels, Probability Surveys, 6, (2009), 1-33 (electronic). DOI: 10.1214/08-PS141.

References

[1]     Abdel-Ghaffar, K.A.S. Capacity per unit cost of a discrete memoryless channel. IEE Electronic Letters, 29:142-144, 1993.

[2]     Batu,T., Kannan, S., Khanna, S. and McGregor A. Reconstructing strings from random traces. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 910–918, 2004. MR2290981

[3]     Chen, J., Mitzenmacher, M., Ng, C. and Varnica N. Concatenated codes for deletion channels. In Proceedings of the 2003 IEEE International Symposium on Information Theory, p. 218, 2003.

[4]     Chung, S.Y., Forney, Jr., G.D., Richardson, T.J. and Urbanke, R. On the design of low-density parity-check codes within 0.0045 dB ofthe Shannon limit. IEEE Communications Letters, 5(2):58–60, 2001.

[5]     Davey, M.C. and Mackay, D.J.C. Reliable communication over channels with insertions, deletions, and substitutions. IEEE Transactions on Information Theory, 47(2):687–698, 2001. MR1820484

[6]     Diggavi, S. and Grossglauser, M. On Transmission over Deletion Channels. In Proceedings of the 39th Annual Allerton Conference on Communication, Control, and Computing, pp. 573-582, 2001.

[7]     Diggavi, S. and Grossglauser, M. On information transmission over a finite buffer channel. IEEE Transactions on Information Theory, 52(3):1226–1237, 2006. MR2238087

[8]     Diggavi, S., Mitzenmacher, M. and Pfister, H. Capacity Upper Bounds for Deletion Channels. In Proceedings of the International Symposium on Information Theory, pp. 1716-1720, Nice, France, June 2007.

[9]     Dobrushin, R.L. Shannon’s Theorems for Channels with Synchronization Errors. Problems of Information Transmission, 3(4):11-26, 1967. Translated from Problemy Peredachi Informatsii, vol. 3, no. 4, pp 18-36, 1967. MR0289198

[10]     Dolgopolov, A.S. Capacity Bounds for a Channel with Synchronization Errors. Problems of Information Transmission, 26(2):111-120, 1990. Translated from Problemy Peredachi Informatsii, vol. 26, no. 2, pp 27-37, April-June, 1990. MR1074126

[11]     Dolecek, L. and Anantharam, V. Using Reed-Muller(1,m) Codes over Channels with Synchronization and Substitution Errors. IEEE Transactions on Information Theory, 53(4):1430-1443, 2007. MR2303012

[12]     Dolecek, L. and Anantharam, V. A Synchronization Technique for Array-based LDPC Codes in Channels with Varying Sampling Rate. In Proceedings of the 2006 IEEE International Symposium on Information Theory (ISIT), pages 2057–2061, 2006.

[13]     Drinea, E. and Kirsch, A. Directly lower bounding the information capacity for channels with i.i.d. deletions and duplications. In Proceedings of the 2007 IEEE International Symposium on Information Theory (ISIT), pages 1731–1735, 2007.

[14]     Drinea, E. and Mitzenmacher, M. On Lower Bounds for the Capacity of Deletion Channels. IEEE Transactions on Information Theory, 52:10, pp. 4648-4657, 2006. MR2300847

[15]     Drinea, E. and Mitzenmacher, M. Improved lower bounds for the capacity of i.i.d. deletion and duplication channels. IEEE Transactions on Information Theory, 53:8, pp. 2693-2714, 2007. MR2400490

[16]     Ferreira, H.C., Clarke, W.A., Helberg, A.S.J., Abdel-Ghaffar, K.A.S. and Winck, A.J.H. Insertion/deletion correction with spectral nulls. IEEE Transactions on Information Theory, volume 43, number 2, pp. 722-732, 1997.

[17]     Fertonani, D. and Duman, T.M. Novel bounds on the capacity of binary channels with deletions and substitutions, In Proceedings of the 2009 IEEE International Symposium on Information Theory (ISIT), 2009.

[18]     Gallager, R.G. Sequential decoding for binary channels with noise and synchronization errors. Lincoln Lab. Group Report, October 1961.

[19]     Gusfield, D. Algorithms on Stings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997. MR1460730

[20]     Holenstein, T., Mitzenmacher, M., Panigrahy, R. and Wieder, U. Trace reconstruction with constant deletion probability and related results. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 389–398, 2008. MR2487606

[21]     Jimbo, M. and Kunisawa, K. An Iteration Method for Calculating the Relative Capacity. Information and Control, 43:216-233, 1979. MR0553700

[22]     Kannan, S. and McGregor, A. More on reconstructing strings from random traces: insertions and deletions. In Proceedings of the 2005 IEEE International Symposium on Information Theory, pp. 297–301, 2005.

[23]     Kavcic, A. and Motwani, R. Insertion/deletion channels: Reduced-state lower bounds on channel capacities. In Proceedings of the 2004 IEEE International Symposium on Information Theory, p. 229.

[24]     Kesten, H. Random difference equations and renewal theory for products of random matrices. Acta Mathematica, 131:207-248, 1973. MR0440724

[25]     Levenshtein, V.I. Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics - Doklady, vol. 10, no. 8, pp. 707–710, 1966. (In Russsian, Dolkady Akademii Nauk SSR, vol. 163, no. 14 pp. 845-848, 1966. MR0189928

[26]     Levenshtein, V.I. Efficient reconstruction of sequences. IEEE Transactions on Information Theory, 47(1):2–22, 2001. MR1819952

[27]     Levenshtein, V.I. Efficient reconstruction of sequences from their subsequences or supersequences. Journal of Combinatorial Theory, Series A, 93(2):310–332, 2001. MR1805300

[28]     Liu, Z. and Mitzenmacher, M. Codes for deletion and insertion channels with segmented errors. In Proceedings of the 2007 IEEE International Symposium on Information Theory (ISIT), pages 846–850, 2007.

[29]     Lothaire, M. Applied Combinatorics on Words. Vol. 105 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2005. MR2165687

[30]     Luby, M.G., Mitzenmacher, M., Shokrollahi, M.A. and Spielman, D.A. Efficient erasure correcting codes. IEEE Transactions on Information Theory, 47(2):569–584, 2001. MR1820477

[31]     Luby, M.G. and Mitzenmacher, M. Verification-based decoding for packet-based low-density parity-check codes. IEEE Transactions on Information Theory, 51(1):120–127, 2005. MR2234576

[32]     Metzner, J.J. Packet-symbol decoding for reliable multipath reception with no sequence numbers. In Proceedings of the IEEE International Conference on Communications, pp. 809-814, 2007.

[33]     Mitzenmacher, M. A note on low density parity check codes for erasures and errors. SRC Technical Note 17, 1998.

[34]     Mitzenmacher, M. A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet Mathematics, vol. 1, No. 2, pp. 226-251, 2004. MR2077227

[35]     Mitzenmacher, M. Polynomial time low-density parity-check codes with rates very close to the capacity of the q-ary random deletion channel for large q. IEEE Transactions on Information Theory, 52(12):5496–5501, 2006. MR2300707

[36]     Mitzenmacher, M. Capacity bounds for sticky channels. IEEE Transactions on Information Theory, 54(1):72, 2008. MR2446740

[37]     Mitzenmacher, M. and Drinea, E. A simple lower bound for the capacity of the deletion channel. IEEE Transactions on Information Theory, 52:10, pp. 4657-4660, 2006. MR2300848

[38]     Mitzenmacher, M. and Upfal, E. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. MR2144605

[39]     Ratzer, E. Marker codes for channels with insertions and deletions. Annals of Telecommunications, 60:1-2, p. 29-44, January-February 2005.

[40]     Richardson, T.J., Shokrollahi, M.A. and Urbanke, R.L. Design of capacity-approaching irregular low-density parity-check codes. IEEE Transactions on Information Theory, 47(2):619–637, 2001. MR1820480

[41]     Richardson, T.J. and Urbanke, R.L. The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2):599–618, 2001. MR1820479

[42]     Schulman, L.J. and Zuckerman, D. Asymptotically good codes correcting insertions, deletions, and transpositions. IEEE Transactions on Information Theory, 45(7):2552–2557, 1999. MR1725152

[43]     Shannon, C.E. A mathematical theory of communication. Bell Systems Technical Journal, 27(3):379–423, 1948. MR0026286

[44]     Sloane, N.J.A. On single-deletion-correcting codes. Codes and Designs: Proceedings of a Conference Honoring Professor Dijen K. Ray-Chaudhuri on the Occasion of His 65th Birthday, Ohio State University, May 18-21, 2000, 2002. MR1948149

[45]     Ullman, J.D. On the capabilities of codes to correct synchronization errors. IEEE Transactions on Information Theory, 13 (1967), 95-105.

[46]     Varshamov, R.R. and Tenengolts, G.M. Codes which correct single asymmetric errors. Automation and Remote Control, 26:2, pp. 286-290, 1965. Translated from Automatika i Telemekhanika, 26:2, pp. 288-292, 1965.

[47]     Viswanathan, K. and Swaminathan, R. Improved string reconstruction over insertion-deletion channels. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 399–408, 2008. MR2487607

[48]     Vvedenskaya, N.D. and Dobrushin, R.L. The Computation on a Computer of the Channel Capacity of a Line with Symbol Drop-out. Problems of Information Transmission, 4(3):76-79, 1968. Translated from Problemy Peredachi Informatsii, vol. 4, no. 3, pp 92-95, 1968.

[49]     van Wijngaarden, A.J., Morita, H. and Vinck, A.J.H. Prefix synchronized codes capable of correcting single insertion/deletion errors. In Proceedings of the International Symposium on Information Theory, p. 409, 1997.

[50]     Zigangirov, K.S. Sequential decoding for a binary channel with drop-outs and insertions. Problems of Information Transmission, vol. 5, no. 2, pp. 17–22, 1969. Translated from Problemy Peredachi Informatsii, vol. 5, no. 2, pp 23–30, 1969.




Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787