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:

    “A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutation—a proof of unwillingness to do much, even where there is a necessity of doing something.”
    —Samuel Johnson (1709–1784)

    “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)

    “If some books are deemed most baneful and their sale forbid, how, then, with deadlier facts, not dreams of doting men? Those whom books will hurt will not be proof against events. Events, not books, should be forbid.”
    —Herman Melville (1819–1891)