NDLI: Optimal Coding for the Binary Deletion Channel With Small Deletion Probability

Content Provider	IEEE Xplore Digital Library
Author	Kanoria, Y. Montanari, A.
Copyright Year	1963
Abstract	The binary deletion channel is the simplest point-to-point communication channel that models lack of synchronization. Input bits are deleted independently with probability d, and when they are not deleted, they are not affected by the channel. Despite significant effort, little is known about the capacity of this channel and even less about optimal coding schemes. In this paper, we develop a new systematic approach to this problem, by demonstrating that capacity can be computed in a series expansion for small deletion probability. We compute three leading terms of this expansion, and find an input distribution that achieves capacity up to this order. This constitutes the first optimal random coding result for the deletion channel. The key idea employed is the following: We understand perfectly the deletion channel with deletion probability d=0. It has capacity 1 and the optimal input distribution is iid Bernoulli (1/2). It is natural to expect that the channel with small deletion probabilities has a capacity that varies smoothly with d, and that the optimal input distribution is obtained by smoothly perturbing the iid Bernoulli (1/2) process. Our results show that this is indeed the case.
Sponsorship	IEEE Information Theory Society
Starting Page	6192
Ending Page	6219
Page Count	28
File Size	9825372
File Format	PDF
ISSN	00189448
Volume Number	59
Issue Number	10
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Encoding Upper bound Markov processes Synchronization Capacity planning Channel capacity Systematics series expansion Capacity achieving code channel capacity deletion channel
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Upper Bounds on the Capacity of Deletion Channels Using Channel Fragmentation

Novel Bounds on the Capacity of the Binary Deletion Channel

Improved Lower Bounds for the Capacity of i.i.d. Deletion and Duplication Channels

Bounds on the Capacity of Random Insertion and Deletion-Additive Noise Channels

Refinement of the Random Coding Bound

A new bound on the capacity of the binary deletion channel with high deletion probabilities

Bounds on the capacity of deletion channels

An upper bound on the capacity of non-binary deletion channels

A Simple Lower Bound for the Capacity of the Deletion Channel

Optimal Coding for the Binary Deletion Channel With Small Deletion Probability

Similar Documents

Upper Bounds on the Capacity of Deletion Channels Using Channel Fragmentation

Novel Bounds on the Capacity of the Binary Deletion Channel

Improved Lower Bounds for the Capacity of i.i.d. Deletion and Duplication Channels

Bounds on the Capacity of Random Insertion and Deletion-Additive Noise Channels

Refinement of the Random Coding Bound

A new bound on the capacity of the binary deletion channel with high deletion probabilities

Bounds on the capacity of deletion channels

An upper bound on the capacity of non-binary deletion channels

A Simple Lower Bound for the Capacity of the Deletion Channel

Optimal Coding for the Binary Deletion Channel With Small Deletion Probability