A Caltech Library Service

Miscorrection probability beyond the minimum distance

Cassuto, Yuval and Bruck, Jehoshua (2004) Miscorrection probability beyond the minimum distance. In: International Symposium on Information Theory (ISIT 2004), Chicago IL, 27 June-2 July 2004. IEEE , Piscataway, NJ, p. 524. ISBN 0-7803-8280-3.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


The miscorrection probability of a list decoder is the probability that the decoder will have at least one non-causal codeword in its decoding sphere. Evaluating this probability is important when using a list-decoder as a conventional decoder since in that case we require the list to contain at most one codeword for most of the errors. A lower bound on the miscorrection is the main result. The key ingredient in the proof is a new combinatorial upper bound on the list-size for a general q−ary block code. This bound is tighter than the best known on large alphabets, and it is shown to be very close to the algebraic bound for Reed-Solomon codes. Finally we discuss two known upper bounds on the miscorrection probability and unify them for linear MDS codes.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Cassuto, Yuval0000-0001-6369-6699
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© Copyright 2004 IEEE. Reprinted with permission. Publication Date: 27 June-2 July 2004. Current Version Published: 2005-01-10. This work was supported in part by the Lee Center for Advanced Networking at the California Institute of Technology.
Funding AgencyGrant Number
Lee Center for Advanced Networking ,CaltechUNSPECIFIED
Subject Keywords:Reed-Solomon codes; block codes; linear codes; probability; algebraic bound; combinatorial upper bound; decoding sphere; linear MDS codes; list decoder; minimum distance; miscorrection probability; noncausal codeword; q-ary block code
Record Number:CaltechAUTHORS:CASisit04
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:12406
Deposited On:24 Nov 2008 21:45
Last Modified:08 Nov 2021 22:28

Repository Staff Only: item control page