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:

    “From whichever angle one looks at it, the application of racial theories remains a striking proof of the lowered demands of public opinion upon the purity of critical judgment.”
    —Johan Huizinga (1872–1945)

    “There is no better proof of a man’s being truly good than his desiring to be constantly under the observation of good men.”
    —François, Duc De La Rochefoucauld (1613–1680)

    “O, popular applause! what heart of man
    Is proof against thy sweet, seducing charms?”
    —William Cowper (1731–1800)