NDLI: An inequality on guessing and its application to sequential decoding

Content Provider	IEEE Xplore Digital Library
Author	Arikan, E.
Copyright Year	1963
Abstract	Let (X,Y) be a pair of discrete random variables with X taking one of M possible values, Suppose the value of X is to be determined, given the value of Y, by asking questions of the form "Is X equal to x?" until the answer is "Yes". Let G(x\|y) denote the number of guesses in any such guessing scheme when X=x, Y=y. We prove that E[G(X\|Y)/sup /spl rho//]/spl ges/(1+lnM)/sup -/spl rho///spl Sigma//sub y/[/spl Sigma//sub x/P/sub X,Y/(x,y)/sup 1/1+/spl rho//]/sup 1+/spl rho// for any /spl rho//spl ges/0. This provides an operational characterization of Renyi's entropy. Next we apply this inequality to the estimation of the computational complexity of sequential decoding. For this, we regard X as the input, Y as the output of a communication channel. Given Y, the sequential decoding algorithm works essentially by guessing X, one value at a time, until the guess is correct. Thus the computational complexity of sequential decoding, which is a random variable, is given by a guessing function G(X\|Y) that is defined by the order in which nodes in the tree code are hypothesized by the decoder. This observation, combined with the above lower bound on moments of G(X\|Y), yields lower bounds on moments of computation in sequential decoding. The present approach enables the determination of the (previously known) cutoff rate of sequential decoding in a simple manner; it also yields the (previously unknown) cutoff rate region of sequential decoding for multiaccess channels. These results hold for memoryless channels with finite input alphabets.
Sponsorship	IEEE Information Theory Society
Starting Page	99
Ending Page	105
Page Count	7
File Size	706743
File Format	PDF
ISSN	00189448
Volume Number	42
Issue Number	1
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1996-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	Decoding Random variables Entropy Computational complexity Communication channels Memoryless systems Information theory Random processes Probability distribution Estimation theory
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

Comments on An inequality on guessing and its application to sequential decoding

The common randomness capacity of a pair of independent discrete memoryless channels

Joint source-channel coding and guessing with application to sequential decoding

An Efficient Feedback Coding Scheme With Low Error Probability for Discrete Memoryless Channels

The cutoff rate of time correlated fading channels

Random access communication and graph entropy

Computation of total capacity for discrete memoryless multiple-access channels

Wiretap Channel With Side Information

Information and control: matching channels

An inequality on guessing and its application to sequential decoding

Similar Documents

Comments on An inequality on guessing and its application to sequential decoding

The common randomness capacity of a pair of independent discrete memoryless channels

Joint source-channel coding and guessing with application to sequential decoding

An Efficient Feedback Coding Scheme With Low Error Probability for Discrete Memoryless Channels

The cutoff rate of time correlated fading channels

Random access communication and graph entropy

Computation of total capacity for discrete memoryless multiple-access channels

Wiretap Channel With Side Information

Information and control: matching channels

An inequality on guessing and its application to sequential decoding