In the

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are stud ...

, the Griesmer bound, named after James Hugo Griesmer, is a bound on the length of

linear Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...

binary Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two digits (0 and 1) * Binary function, a function that takes two arguments * Binary operation, a mathematical operation that t ...

code In communications and information processing, code is a system of rules to convert information—such as a letter, word, sound, image, or gesture—into another form, sometimes shortened or secret, for communication through a communication ...

s of dimension ''k'' and minimum distance ''d''. There is also a very similar version for non-binary codes.

Statement of the bound

For a binary linear code, the Griesmer bound is: :

n\geqslant \sum_^ \left\lceil\frac\right\rceil.

Proof

Let

N(k,d)

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 :

N(k,d)\geqslant \sum_^ \left\lceil\frac\right\rceil.

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
1 & \dots & 1 & 0 & \dots & 0 \\
\ast & \ast  & \ast &   & G' &   \\
\end

The matrix

G'

generates a code

C'

, which is called the residual code of

C.

C'

obviously has dimension

k'=k-1

and length

n'=N(k,d)-d.

C'

has a distance

d',

but we don't know it. Let

u\in C'

be such that

w(u)=d'

. There exists a vector

v\in \mathbb_2^d

such that the concatenation

(v, u)\in C.

Then

w(v)+w(u)=w(v, u)\geqslant d.

On the other hand, also

(v, u)+r\in C,

since

r\in C

and

C

is linear:

w((v, u)+r)\geqslant d.

But :

w((v, u)+r)=w(((1,\cdots,1)+v), u)=d-w(v)+w(u),

so this becomes

d-w(v)+w(u)\geqslant d

. By summing this with

w(v)+w(u)\geqslant d,

we obtain

d+2w(u)\geqslant 2d

. But

w(u)=d',

so we get

2d'\geqslant d.

d'

is integral, we get

d'\geqslant \left\lceil \tfrac \right\rceil.

This implies :

n'\geqslant N\left (k-1,\left\lceil \tfrac \right\rceil \right ),

so that :

N(k,d)\geqslant d + N\left (k-1, \left\lceil \tfrac \right\rceil \right ).

By induction over ''k'' we will eventually get :

N(k,d)\geqslant  \sum_^ \left\lceil\frac\right\rceil.

Note that at any step the dimension decreases by 1 and the distance is halved, and we use the identity :

\left\lceil\frac\right\rceil = \left\lceil\frac\right\rceil

for any integer ''a'' and positive integer ''k''.

The bound for the general case

For a linear code over

\mathbb_q

, the Griesmer bound becomes: :

n\geqslant \sum_^ \left\lceil\frac{q^i}\right\rceil.

The proof is similar to the binary case and so it is omitted.

References

*J. H. Griesmer, "A bound for error-correcting codes," IBM Journal of Res. and Dev., vol. 4, no. 5, pp. 532-542, 1960. Coding theory Articles containing proofs

Statement of the bound

Proof

The bound for the general case

See also

References