NDLI: Generalized sphere packing bound: Basic principles

Content Provider	IEEE Xplore Digital Library
Author	Fazeli, A. Vardy, A. Yaakobi, E.
Copyright Year	2014
Description	Author affiliation: Univ. of California San Diego, La Jolla, CA, USA (Fazeli, A.; Vardy, A.) \|\| Comput. Sci. Dept., Technion - Israel Inst. of Technol., Haifa, Israel (Yaakobi, E.)
Abstract	Kulkarni and Kiyavash recently introduced a new method to establish upper bounds on the size of deletion-correcting codes. This method is based upon tools from hypergraph theory. The deletion channel is represented by a hypergraph whose edges are the deletion balls (or spheres), so that a deletion-correcting code becomes a matching in this hypergraph. Consequently, a bound on the size of such a code can be obtained from bounds on the matching number of a hypergraph. Classical results in hypergraph theory are then invoked to compute an upper bound on the matching number as a solution to a linear-programming problem: the problem of finding fractional transversals. The method by Kulkarni and Kiyavash can be applied not only for the deletion channel but also for other channels, and in particular for those where the error spheres sizes are not all the same. This paper studies this method in its most general setup. We first show that if the error channel is regular and symmetric then the upper bound by this method coincides with the well-known sphere packing bound and thus is called here the generalized sphere packing bound. Even though this bound is explicitly given by a linear programming problem, finding its exact value may still be a challenging task. The art of finding the exact upper bound or slightly weaker ones is the assignment of weights to the hypergraph's vertices in a way that the satisfy the constraints in the linear programming problem. Every valid assignment yields an upper bound and the goal is to find assignments that provide strong upper bounds. We show that for graphs which satisfy a monotonicity property it is possible to find a general formula for such an assignment. Lastly, in order to simplify the complexity of the linear programming, we present a technique based upon graph automorphisms that in many cases can significantly reduce the number of variables and constraints in the linear programming problem. All of our results will be demonstrated and calculated for the Z channel which will be a case study in our work.
Starting Page	1256
Ending Page	1260
File Size	386607
Page Count	5
File Format	PDF
ISBN	9781479951864
ISSN	21578117
DOI	10.1109/ISIT.2014.6875034
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2014-06-29
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Upper bound Linear programming Vectors Tin Integer linear programming Binary codes
Content Type	Text
Resource Type	Article

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