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

CRC Press eBooks

Bounds in Coding Theory

Dave K. Kythe, Prem K. Kythe

Published May 10, 2012• 1 citation
Publisher

Abstract

There are some bounds that are placed on the size of error correcting codes. Some of the well-known bounds are discussed in the following sections. 6.1 Definitions Let n be fixed, and let M denote the size of a code C (i.e., the number of codewords in C), and d the minimum distance between the codewords. For example, (i) for the code C = {00, 01, 10, 11} : n = 2,M = 4; d = 1; (ii) for the code C = {000, 011, 101, 110} : n = 3,M = 4, d = 2; and (iii) for the code C = {00000, 00111, 11111} : n = 5,M = 3, d = 2. Then for a q-ary (n,M, d) code, the transmission rate (also known as the information rate) is defined by R(C) = log q M n , and the relative minimum distance by δ(C) = (d − 1)/n. Note that this distance is also defined by d/n, but neater formulas are obtained by defining it as (d − 1)/n. For the binary repetition code C = {00 . . .0︸ ︷︷ ︸ 11 . . .1︸ ︷︷ ︸ n }, which is an (n, 2, n) code, we find that R(C) = log 2 2 n = n → 0 and δ(C) = n− 1 n → 0 as n→∞.

DOI
10.1201/b11707-10

Related papers

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

Bounds on the Probability of Undetected Error for q-Ary Codes

Xuan Wang, Huizhou Liu, Patrick Solé

-ary codes. We give upper and lower bounds on this quantity, by the Linear Programming and the Polynomial methods, as a function of the length, size, and minimum distance. Sharper bounds are obtained in the important special case of binary Hamming codes. Finally, several examples are given to illustrate the results of this paper.

Entropy•Sep 17, 2023•0 citations

Performance of Error-Control Codes

Richard E. Blahut

In any engineering discipline, one looks for methods of solving a given class of problems and then for methods of quantifying the performance and complexity of those solutions. Accordingly, in this chapter, we shall study performance in terms of the composition structure of block codes, and the probabilities of decoding error and of decoding failure. Later, after satisfactory methods are in hand, one turns to questions of optimality. Are these methods the best methods, and if not, in what ways and by how much are they inferior? To answer such questions, one needs to know how good are the known codes and how good are the best possible codes. Generally, we cannot answer either of these questions satisfactorily. Although for any given rate and blocklength, not too small, the best possible code is not known, a number of bounds are known – bounds beyond which no codes can exist, and bounds within which codes are sure to exist. We shall give some such bounds on the best possible codes later in this chapter. Knowledge of these bounds can deepen our understanding of the subject. Weight distributions of block codes If a linear block code has a minimum distance d min , then we know that at least one codeword of weight d min exists. Sometimes, we are not content with this single piece of information; we wish to know how many codewords have weight d min , and what are the weights of the other codewords.

Cambridge University Press eBooks•Feb 6, 2003•0 citations

Asymptotically dense nonbinary codes correcting a constant number of localized errors [Manuskript]

Rudolf Ahlswede, Leonid Alexandrovich Bassalygo, M.S. Pinsker

The binary case was studied in [1], but the method used there doesn't give the tight answer for nonbinary cases and we presented in [2] another method for the corresponding result.Here we formulate the main theorem and prove the auxiliary statements used in [2].During the transmission of q-ary words of length n over the channel at most t errors occur, and the encoder knows the set E of t positions, where these errors are possible.The decoder doesn't know anything about these positions.Let E t = E | E ⊆ {1, 2, . . ., n}, |E| = t be the set of all subsets from {1, 2, . . ., n} of size t and let M be a set of messages (|M| = M ) .A code word x(m, E) depends not only on the message m ∈ M but also on the configuration of possible errors E .So there exists the natural correspondence between the message m ∈ M and the list of code words E∈E t x(m, E) , which we use for the transmission of this message.Thus the code X for the set of messages M represents a collection of M lists E∈E t {x(m, E)}, m ∈ M .Sinde we can use the same word for different configurations, the size of a list can be essentially smaller than the size of the setLet us define the cylinder C(a, A) with the base a = (a, . . ., a n ) and the support A A ⊆ {1, 2, . . ., n} as the set of words (y 1 , . . ., y n ) with y i = a i , if i / ∈ A .It is clear that the size of the cylinder C(a, A) is equal to q |A| and the number of different cylinders with the same support A is equal to q n-|A| .As a result of the transmission of the codeword x(m, E) every word of C x(m, E), E can appear as output of the channel.The code X corrects t localized errors, if the decoder can correctly recover every message m ∈ M .The following condition is necessary and sufficient for it:

Comptes Rendus De L Academie Bulgare Des Sciences•Jan 1, 1993•0 citations

Block codes – some constraints and some geometry

John Baylis

We saw in Chapter 1 how the 3-fold repetition code would drastically reduce the probability of messages being wrongly decoded, and discussed the price which this entailed. Then in Chapter 2 we saw how the Hamming code solved the same problem of guaranteeing to correct every instance of a single error per codeword at much less cost. The way in which it achieved its impressive performance was by ensuring that amongst the 16 7-bit codewords, no pair of them was separated by a Hamming distance less than 3. We also developed general results, Theorems 2.1 and 2.2, to connect the minimum distance of the code with its error detecting and correcting potential.

Routledge eBooks•May 11, 2018•0 citations

Error-Correction Capability of Binary Linear Codes

Tor Helleseth, Torleiv Kløve, V.I. Levenshtein

The monotone structure of correctable and uncorrectable errors given by the complete decoding for a binary linear code is investigated. New bounds on the error-correction capability of linear codes beyond half the minimum distance are presented, both for the best codes and for arbitrary codes under some restrictions on their parameters. It is proved that some known codes of low rate are as good as the best codes in an asymptotic sense.

IEEE Transactions on Information Theory•Apr 1, 2005•30 citations
There are some bounds that are placed on the size of error correcting codes. Some of the well-known bounds are discussed in the following sections. 6.1 Definitions Let n be fixed, and let M denote the size of a code C (i.e., the number of codewords in C), and d the minimum distance between the codewords. For example, (i) for the code C = {00, 01, 10, 11} : n = 2,M = 4; d = 1; (ii) for the code C = {000, 011, 101, 110} : n = 3,M = 4, d = 2; and (iii) for the code C = {00000, 00111, 11111} : n = 5,M = 3, d = 2. Then for a q-ary (n,M, d) code, the transmission rate (also known as the information rate) is defined by R(C) = log q M n , and the relative minimum distance by δ(C) = (d − 1)/n. Note that this distance is also defined by d/n, but neater formulas are obtained by defining it as (d − 1)/n. For the binary repetition code C = {00 . . .0︸ ︷︷ ︸ 11 . . .1︸ ︷︷ ︸ n }, which is an (n, 2, n) code, we find that R(C) = log 2 2 n = n → 0 and δ(C) = n− 1 n → 0 as n→∞.
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 .
In any engineering discipline, one looks for methods of solving a given class of problems and then for methods of quantifying the performance and complexity of those solutions. Accordingly, in this chapter, we shall study performance in terms of the composition structure of block codes, and the probabilities of decoding error and of decoding failure. Later, after satisfactory methods are in hand, one turns to questions of optimality. Are these methods the best methods, and if not, in what ways and by how much are they inferior? To answer such questions, one needs to know how good are the known codes and how good are the best possible codes. Generally, we cannot answer either of these questions satisfactorily. Although for any given rate and blocklength, not too small, the best possible code is not known, a number of bounds are known – bounds beyond which no codes can exist, and bounds within which codes are sure to exist. We shall give some such bounds on the best possible codes later in this chapter. Knowledge of these bounds can deepen our understanding of the subject. Weight distributions of block codes If a linear block code has a minimum distance d min , then we know that at least one codeword of weight d min exists. Sometimes, we are not content with this single piece of information; we wish to know how many codewords have weight d min , and what are the weights of the other codewords.
The binary case was studied in [1], but the method used there doesn't give the tight answer for nonbinary cases and we presented in [2] another method for the corresponding result.Here we formulate the main theorem and prove the auxiliary statements used in [2].During the transmission of q-ary words of length n over the channel at most t errors occur, and the encoder knows the set E of t positions, where these errors are possible.The decoder doesn't know anything about these positions.Let E t = E | E ⊆ {1, 2, . . ., n}, |E| = t be the set of all subsets from {1, 2, . . ., n} of size t and let M be a set of messages (|M| = M ) .A code word x(m, E) depends not only on the message m ∈ M but also on the configuration of possible errors E .So there exists the natural correspondence between the message m ∈ M and the list of code words E∈E t x(m, E) , which we use for the transmission of this message.Thus the code X for the set of messages M represents a collection of M lists E∈E t {x(m, E)}, m ∈ M .Sinde we can use the same word for different configurations, the size of a list can be essentially smaller than the size of the setLet us define the cylinder C(a, A) with the base a = (a, . . ., a n ) and the support A A ⊆ {1, 2, . . ., n} as the set of words (y 1 , . . ., y n ) with y i = a i , if i / ∈ A .It is clear that the size of the cylinder C(a, A) is equal to q |A| and the number of different cylinders with the same support A is equal to q n-|A| .As a result of the transmission of the codeword x(m, E) every word of C x(m, E), E can appear as output of the channel.The code X corrects t localized errors, if the decoder can correctly recover every message m ∈ M .The following condition is necessary and sufficient for it:
We saw in Chapter 1 how the 3-fold repetition code would drastically reduce the probability of messages being wrongly decoded, and discussed the price which this entailed. Then in Chapter 2 we saw how the Hamming code solved the same problem of guaranteeing to correct every instance of a single error per codeword at much less cost. The way in which it achieved its impressive performance was by ensuring that amongst the 16 7-bit codewords, no pair of them was separated by a Hamming distance less than 3. We also developed general results, Theorems 2.1 and 2.2, to connect the minimum distance of the code with its error detecting and correcting potential.