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 source of Pyrrhonism comes from failing to distinguish between a demonstration, a proof and a probability. A demonstration supposes that the contradictory idea is impossible; a proof of fact is where all the reasons lead to belief, without there being any pretext for doubt; a probability is where the reasons for belief are stronger than those for doubting.”
    —Andrew Michael Ramsay (1686–1743)

    “The fact that several men were able to become infatuated with that latrine is truly the proof of the decline of the men of this century.”
    —Charles Baudelaire (1821–1867)

    “He who has never failed somewhere, that man can not be great. Failure is the true test of greatness. And if it be said, that continual success is a proof that a man wisely knows his powers,—it is only to be added, that, in that case, he knows them to be small.”
    —Herman Melville (1819–1891)