Gilbert–Varshamov Bound For Linear Codes
   HOME

TheInfoList



OR:

The Gilbert–Varshamov bound for linear codes is related to the general Gilbert–Varshamov bound, which gives a lower bound on the maximal number of elements in an
error-correcting code In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The centra ...
of a given block length and minimum
Hamming weight The Hamming weight of a string (computer science), string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the mo ...
over a field \mathbb_q. This may be translated into a statement about the maximum rate of a code with given length and minimum distance. The Gilbert–Varshamov bound for
linear code In coding theory, a linear code is an error-correcting code for which any linear combination of Code word (communication), codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although t ...
s asserts the existence of ''q''-ary linear codes for any relative minimum distance less than the given bound that simultaneously have high rate. The existence proof uses the probabilistic method, and thus is not constructive. The Gilbert–Varshamov bound is the best known in terms of relative distance for codes over alphabets of size less than 49. For larger alphabets, algebraic geometry codes sometimes achieve an asymptotically better rate vs. distance tradeoff than is given by the Gilbert–Varshamov bound.


Gilbert–Varshamov bound theorem

:Theorem: Let q \geqslant 2. For every 0 \leqslant \delta < 1 - \tfrac and 0 < \varepsilon \leqslant 1 - H_q (\delta ), there exists a q-ary linear code with rate R \geqslant 1 - H_q (\delta ) - \varepsilon and relative distance \delta. Here H_q is the ''q''-ary entropy function defined as follows: : H_q(x) = x\log_q(q-1)-x\log_qx-(1-x)\log_q(1-x). The above result was proved by Edgar Gilbert for general codes using the greedy method. Rom Varshamov refined the result to show the existence of a linear code. The proof uses the probabilistic method. ''High-level proof:'' To show the existence of the linear code that satisfies those constraints, the probabilistic method is used to construct the random linear code. Specifically, the linear code is chosen by picking a generator matrix G \in \mathbb_q^ whose entries are randomly chosen elements of \mathbb_q. The minimum
Hamming distance In information theory, the Hamming distance between two String (computer science), strings or vectors of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number ...
of a linear code is equal to the minimum weight of a nonzero codeword, so in order to prove that the code generated by G has minimum distance d, it suffices to show that for any m \in \mathbb_q^k \smallsetminus \left\, \operatorname(mG) \ge d. We will prove that the probability that there exists a nonzero codeword of weight less than d is exponentially small in n. Then by the probabilistic method, there exists a linear code satisfying the theorem. ''Formal proof:'' By using the probabilistic method, to show that there exists a linear code that has a Hamming distance greater than d, we will show that the
probability Probability is a branch of mathematics and statistics concerning events and numerical descriptions of how likely they are to occur. The probability of an event is a number between 0 and 1; the larger the probability, the more likely an e ...
that the random linear code having the distance less than d is exponentially small in n. The linear code is defined by its
generator matrix In coding theory, a generator matrix is a matrix whose rows form a basis for a linear code. The codewords are all of the linear combinations of the rows of this matrix, that is, the linear code is the row space of its generator matrix. Terminolo ...
, which we choose to be a random k \times n generator matrix; that is, a matrix of kn elements which are chosen independently and uniformly over the field \mathbb_q. Recall that in a
linear code In coding theory, a linear code is an error-correcting code for which any linear combination of Code word (communication), codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although t ...
, the distance equals the minimum weight of a nonzero codeword. Let \operatorname(y) be the weight of the codeword y. So : \begin P & = \Pr_ (\text G\text < d) \\ pt& = \Pr_ (\text y \textG\text \operatorname(y) < d) \\ pt&= \Pr_ \left (\text 0 \neq m \in \mathbb_q^k \text \operatorname(mG) < d \right ) \end The last equality follows from the definition: if a codeword y belongs to a linear code generated by G, then y = mG for some vector m \in \mathbb_q^k. By
Boole's inequality In probability theory, Boole's inequality, also known as the union bound, says that for any finite or countable set of events, the probability that at least one of the events happens is no greater than the sum of the probabilities of the indiv ...
, we have: : P \leqslant \sum_ \Pr_ (\operatorname(mG) < d) Now for a given message 0 \neq m \in \mathbb_q^k, we want to compute :W = \Pr_ (\operatorname(mG) < d). Let \Delta(m_1,m_2) be a Hamming distance of two messages m_1 and m_2. Then for any message m, we have: \operatorname(m) = \Delta(0,m). Therefore: : W = \sum_ \Pr_ (mG = y) Due to the randomness of G, mG is a uniformly random vector from \mathbb_q^n. So :\Pr_ (mG = y) = q^ Let \operatorname_q(r,n) be the volume of a Hamming ball with the radius r. Then: : P \leqslant q^k W = q^k \left ( \frac \right ) \leqslant q^k \left ( \frac \right ) = q^k q^ By choosing k = (1-H_q(\delta)-\varepsilon)n, the above inequality becomes : P \leqslant q^ Finally q^ \ll 1, which is exponentially small in n, that is what we want before. Then by the probabilistic method, there exists a linear code C with relative distance \delta and rate R at least (1-H_q(\delta)-\varepsilon), which completes the proof.


Comments

# The Varshamov construction above is not explicit; that is, it does not specify the deterministic method to construct the linear code that satisfies the Gilbert–Varshamov bound. A naive approach is to search over all generator matrices G of size kn over the field \mathbb_q to check if the linear code associated to G achieves the predicted Hamming distance. This exhaustive search requires exponential runtime in the worst case. # There also exists a Las Vegas construction that takes a random linear code and checks if this code has good Hamming distance, but this construction also has an exponential runtime. #For sufficiently large non-prime q and for certain ranges of the variable δ, the Gilbert–Varshamov bound is surpassed by the Tsfasman–Vladut–Zink bound.


See also

* Gilbert–Varshamov bound due to Gilbert construction for the general code *
Hamming bound In mathematics and computer science, in the field of coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the sphere-packing bound or the volume bound from an interpretation in terms of Spher ...
* Probabilistic method


References


Lecture 11: Gilbert–Varshamov Bound. Coding Theory Course. Professor Atri Rudra

Lecture 9: Bounds on the Volume of Hamming Ball. Coding Theory Course. Professor Atri Rudra

Coding Theory Notes: Gilbert–Varshamov Bound. Venkatesan Guruswami
{{DEFAULTSORT:Gilbert-Varshamov bound for linear codes Coding theory