In applied mathematics, the Johnson bound (named after

Selmer Martin Johnson Selmer Martin Johnson (21 May 1916 – 26 June 1996) was an American mathematician, a researcher at the RAND Corporation. Biography Johnson was born on May 21, 1916, in Buhl, Minnesota. He earned a B.A. and then an M.A. in mathematics from the ...

) is a limit on the size of

error-correcting code In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The centra ...

s, as used in

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 computer data storage, data sto ...

for

data transmission Data communication, including data transmission and data reception, is the transfer of data, signal transmission, transmitted and received over a Point-to-point (telecommunications), point-to-point or point-to-multipoint communication chann ...

or communications.

Definition

Let

C

be a ''q''-ary

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 communicati ...

of length

n

, i.e. a subset of

\mathbb_q^n

. Let

d

be the minimum distance of

C

, i.e. :

d = \min_ d(x,y),

where

d(x,y)

is the

Hamming distance In information theory, the Hamming distance between two String (computer science), strings or vectors of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number ...

between

x

and

y

. Let

C_q(n,d)

be the set of all ''q''-ary codes with length

n

and minimum distance

d

and let

C_q(n,d,w)

denote the set of codes in

C_q(n,d)

such that every element has exactly

w

nonzero entries. Denote by

, C,

the number of elements in

C

. Then, we define

A_q(n,d)

to be the largest size of a code with length

n

and minimum distance

d

: :

A_q(n,d) = \max_ , C, .

Similarly, we define

A_q(n,d,w)

to be the largest size of a code in

C_q(n,d,w)

: :

A_q(n,d,w) = \max_ , C, .

Theorem 1 (Johnson bound for

A_q(n,d)

): If

d=2t+1

, :

A_q(n,d) \leq \frac.

d=2t+2

, :

A_q(n,d) \leq \frac.

Theorem 2 (Johnson bound for

A_q(n,d,w)

): (i) If

d > 2w,

A_q(n,d,w) = 1.

(ii) If

d \leq 2w

, then define the variable

e

as follows. If

d

is even, then define

e

through the relation

d=2e

; if

d

is odd, define

e

through the relation

d = 2e - 1

. Let

q^* = q - 1

. Then, :

A_q(n,d,w) \leq \left\lfloor \frac  \left\lfloor \frac \left\lfloor \cdots \left\lfloor \frac \right\rfloor \cdots \right\rfloor \right\rfloor \right\rfloor

where

\lfloor ~~ \rfloor

is the

floor function In mathematics, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least integer greater than or eq ...

. Remark: Plugging the bound of Theorem 2 into the bound of Theorem 1 produces a numerical upper bound on

A_q(n,d)

References

* *{{cite book , first1=William Cary , last1=Huffman , first2=Vera S. , last2=Pless , author-link2=Vera Pless , title=Fundamentals of Error-Correcting Codes , url=https://archive.org/details/fundamentalsofer0000huff , url-access=registration , publisher=

Cambridge University Press Cambridge University Press was the university press of the University of Cambridge. Granted a letters patent by King Henry VIII in 1534, it was the oldest university press in the world. Cambridge University Press merged with Cambridge Assessme ...

, year=2003 , isbn=978-0-521-78280-7 Coding theory

Definition

See also

References