Plotkin Bound

STATEMENT OF THE BOUND

Let

C

be a binary code of length

n

, i.e. a subset of

\mathbb{F}_2^n

. Let

d

be the minimum distance of

C

, i.e.

:

d = \min_{x,y \in C, x 
eq y} d(x,y)

where

d(x,y)

is the Hamming Distance between

x

and

y

. Let

r

be the number of elements in

C

.

Theorem (Plotkin bound):

If

2d > n

, then

:

r \leq 2 \lfloorrac{d}{2d-n}
floor

where

\lfloor ~ 
floor

denotes the Floor Function .

PROOF

Let

d(x,y)

be the Hamming Distance of

x

and

y

. The bound is proved by bounding the quantity

\sum_{x,y \in C}  d(x,y)

in two different ways.

On the one hand, there are

r

choices for

x

and for each such choice, there are

r-1

choices for

y

. Since by definition

d(x,y) \geq d

for all

x

and

y

, it follows that

:

\sum_{x,y \in C} d(x,y) \geq r(r-1) d

On the other hand, let

A

be an

r 	imes n

matrix whose rows are the elements of

C

. Let

s_i

be the number of zeros contained in the

i

'th column of

A

. This means that the

i

'th column contains

r-s_i

ones. Each choice of a zero and a one in the same column contributes exactly

2

to the sum

\sum_{x,y \in C} d(x,y)

and therefore

:

\sum_{x,y \in C} d(x,y) = \sum_{i=1}^N 2s_i (r-s_i)

r

is even, then the quantity on the right is maximized when

s_i = r/2

and then,

:

\sum_{x,y \in C} d(x,y) \leq rac{1}{2} N r^2

Combining the upper and lower bounds for

\sum_{x,y \in C} d(x,y)

that we have just derived,

:

r(r-1) d \leq rac{1}{2} N r^2

which given that

2d>n

is equivalent to

:

r \leq rac{2d}{2d-n}

Since

r

is even, it follows that

:

r \leq 2 \lfloor rac{d}{2d-n} 
floor

On the other hand, if

r

is odd, then

\sum_{i=1}^N 2s_i (r-s_i)

is maximized when

s_i = rac{r \pm 1}{2}

which implies that

:

\sum_{x,y \in C} d(x,y) \leq rac{1}{2} N (r^2-1)

Combining the upper and lower bounds for

\sum_{x,y \in C} d(x,y)

, this means that

:

r(r-1) d \leq rac{1}{2} N (r^2-1)

or, using that

2d > n

,

:

r \leq rac{2d}{2d-n} - 1

Since r is an integer,

:

r \leq \lfloor rac{2d}{2d-n} - 1 
floor = \lfloor rac{2d}{2d-n} 
floor -1 \leq 2 \lfloor rac{d}{2d-n} 
floor

This completes the proof of the bound.

REFERENCE

Binary codes with specified minimum distance, M. Plotkin, IRE Transactions on Information Theory, 6:445-450, 1960.

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

	CATEGORIES ABOUT PLOTKIN BOUND

	coding theory

Information About

Plotkin Bound