Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Information Theory

Some Necessary Conditions for Codes to Be Good for Error Detection

Irina Naydenova, Torleiv Kløve

Published Mar 1, 2010• 0 citations
Publisher

Abstract

Codes for error detection on aq-ary symmetric channel are studied. Whether a code is good or not for error detection (in the technical sense) depends on the structure of the code. For some combinations of the main parameters length, size, and minimum distance, all code are good and for some other combinations all are ugly (stronger than not good). The purpose of this paper is to give bounds on the parameters for codes that are not good for error detection. In particular, it is shown that if the minimum distance is below some bound, which depends on the length and size of the code as well as a lower bound on the number of codewords of minimum distance, then the code is ugly and, hence, not good for error detection.

DOI
10.1109/tit.2009.2039044

Related papers

Codes for error detection, good or not good

Irina Naydenova, Torleiv Kløve

Linear codes for error detection on a q-ary symmetric channel are studied. It is shown that for given dimension k and minimum distance d, there exists a value μ(d,k) such that if C is a code of length n >= μ(d,k), then neither C nor its dual are good for error detection. For d >> k or k << d good approximations for μ(d,k) are given. A generalization to non-linear codes is also given.

arXiv:cs/0508035•Aug 4, 2005•0 citations

Codes for error detection, good or not good

I. Gancheva, Torleiv Kløve

Linear codes for error detection on a q-ary symmetric channel are studied. It is shown that for given dimension k and minimum distance d, there exists a value /spl mu/(d, k) such that if C is a code of length n /spl ges/ /spl mu/(d,k), then neither C nor its dual C/sup /spl perp// are good for error detection. For d /spl Gt/ k or k /spl Gt/ d good approximations for /spl mu/(d, k) are given. A generalization to nonlinear codes is also given.

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•1 citation

Necessary conditions for good error detection

P.N. Perry

The problem of determining the error detection capabilities of linear codes where the channel is a binary symmetric channel is addressed. Necessary conditions are given on the number of codewords in an (n,k) linear code and its dual for the probability of an undetected error to be upper bounded by 2/sup -(n-k)/.>

IEEE Transactions on Information Theory•Mar 1, 1991•17 citations

Using codes for error correction and detection (Corresp.)

Torleiv Kløve

A linear codeCover GF(q)is good fort-error-correction and error detection ifP(C,t;\epsilon) \leq P(C,t;(q - 1)/q)for all\epsilon, 0 \leq \epsilon \leq (q - 1)/q, whereP(C, t; \epsilon)is the probability of an undetected error after a codeword inCis transmitted over aq-ary symmetric channel with error probability\epsilonand correction is performed for all error patterns withtor fewer errors. A sufficient condition for a code to be good is derived. This sufficient condition is easy to check, and examples to illustrate the method are given.

IEEE Transactions on Information Theory•Nov 1, 1984•6 citations

Reed-Muller codes for error detection: the good, the bad, and the ugly

Torleiv Kløve

The error detecting capability of Reed-Muller codes is analyzed. If a block code is used for error detection only, then an error is undetectable if it transforms a codeword into another codeword. The probability of undetected error for a binary [n,k] code C used on a binary-symmetric channel with crossover probability p, is given.

IEEE Transactions on Information Theory•Jan 1, 1996•12 citations

Error detection, correction and decoding

San Ling, Chaoping Xing

We saw in Chapter 1 that the purpose of channel coding is to introduce redundancy to information messages so that errors that occur in the transmission can be detected or even corrected. In this chapter, we formalize and discuss the notions of error-detection and error-correction. We also introduce some well known decoding rules, i.e., methods that retrieve the original message sent by detecting and correcting the errors that have occurred in the transmission. Communication channels We begin with some basic definitions. Definition 2.1.1 Let A = { a 1 , a 2 , …, a q } be a set of size q , which we refer to as a code alphabet and whose elements are called code symbols . (i) A q-ary word of length n over A is a sequence w = w 1 w 2 … w n with each w i ∈ A for all i . Equivalently, w may also be regarded as the vector ( w 1 , …, w n ). (ii) A q-ary block code of length n over A is a nonempty set C of q -ary words having the same length n . (iii) An element of C is called a codeword in C . (iv) The number of codewords in C , denoted by ∣ C ∣, is called the size of C . (v) The (information) rate of a code C of length n is defined to be (log q ∣ C ∣)/ n . (vi) A code of length n and size M is called an (n, M)-code .

Cambridge University Press eBooks•Feb 12, 2004•0 citations
Codes for error detection on aq-ary symmetric channel are studied. Whether a code is good or not for error detection (in the technical sense) depends on the structure of the code. For some combinations of the main parameters length, size, and minimum distance, all code are good and for some other combinations all are ugly (stronger than not good). The purpose of this paper is to give bounds on the parameters for codes that are not good for error detection. In particular, it is shown that if the minimum distance is below some bound, which depends on the length and size of the code as well as a lower bound on the number of codewords of minimum distance, then the code is ugly and, hence, not good for error detection.
A linear codeCover GF(q)is good fort-error-correction and error detection ifP(C,t;\epsilon) \leq P(C,t;(q - 1)/q)for all\epsilon, 0 \leq \epsilon \leq (q - 1)/q, whereP(C, t; \epsilon)is the probability of an undetected error after a codeword inCis transmitted over aq-ary symmetric channel with error probability\epsilonand correction is performed for all error patterns withtor fewer errors. A sufficient condition for a code to be good is derived. This sufficient condition is easy to check, and examples to illustrate the method are given.
We saw in Chapter 1 that the purpose of channel coding is to introduce redundancy to information messages so that errors that occur in the transmission can be detected or even corrected. In this chapter, we formalize and discuss the notions of error-detection and error-correction. We also introduce some well known decoding rules, i.e., methods that retrieve the original message sent by detecting and correcting the errors that have occurred in the transmission. Communication channels We begin with some basic definitions. Definition 2.1.1 Let A = { a 1 , a 2 , …, a q } be a set of size q , which we refer to as a code alphabet and whose elements are called code symbols . (i) A q-ary word of length n over A is a sequence w = w 1 w 2 … w n with each w i ∈ A for all i . Equivalently, w may also be regarded as the vector ( w 1 , …, w n ). (ii) A q-ary block code of length n over A is a nonempty set C of q -ary words having the same length n . (iii) An element of C is called a codeword in C . (iv) The number of codewords in C , denoted by ∣ C ∣, is called the size of C . (v) The (information) rate of a code C of length n is defined to be (log q ∣ C ∣)/ n . (vi) A code of length n and size M is called an (n, M)-code .