Griesmer Bound - Proof

Proof

Let denote the minimum length of a binary code of dimension k and distance d. Let C be such a code. We want to show that .

Let G be a generator matrix of C. We can always suppose that the first row of G is of the form r = (1, ..., 1, 0, ..., 0) with weight d.

G= \begin{bmatrix} 1 & \dots & 1 & 0 & \dots & 0 \\ \ast & \ast & \ast & & G' & \\ \end{bmatrix}

The matrix G' generates a code C', which is called the residual code of C. C' has obviously dimension and length . C' has a distance d', but we don't know it. Let s.t. . There exists a vector s.t. the concatenation . Then . On the other hand, also, since and is linear, so . But

,

so this becomes . By summing this with, we obtain . But, so we get . This implies, therefore (due to the integrality of n'), so that . By induction over k we will eventually get (note that at any step the dimension decreases by 1 and the distance is halved, and we use the identity for any integer a and positive integer k).

Read more about this topic:  Griesmer Bound

Famous quotes containing the word proof:

    “The chief contribution of Protestantism to human thought is its massive proof that God is a bore.”
    —H.L. (Henry Lewis)

    “There are some persons in this world, who, unable to give better proof of being wise, take a strange delight in showing what they think they have sagaciously read in mankind by uncharitable suspicions of them.”
    —Herman Melville (1819–1891)

    “When children feel good about themselves, it’s like a snowball rolling downhill. They are continually able to recognize and integrate new proof of their value as they grow and mature.”
    —Stephanie Martson (20th century)