In applied mathematics, the Johnson bound (named after Selmer Martin Johnson) is a limit on the size of error-correcting codes, as used in coding theory for data transmission or communications.
Let
C
be a q-ary code of length
n
, i.e. a subset of
F
q
n
. Let
d
be the minimum distance of
C
, i.e.
d
=
min
x
,
y
∈
C
,
x
≠
y
d
(
x
,
y
)
,
where
d
(
x
,
y
)
is the Hamming distance 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
∈
C
q
(
n
,
d
)
|
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
∈
C
q
(
n
,
d
,
w
)
|
C
|
.
Theorem 1 (Johnson bound for
A
q
(
n
,
d
)
):
If
d
=
2
t
+
1
,
A
q
(
n
,
d
)
≤
q
n
∑
i
=
0
t
(
n
i
)
(
q
−
1
)
i
+
(
n
t
+
1
)
(
q
−
1
)
t
+
1
−
(
d
t
)
A
q
(
n
,
d
,
d
)
A
q
(
n
,
d
,
t
+
1
)
.
If
d
=
2
t
,
A
q
(
n
,
d
)
≤
q
n
∑
i
=
0
t
(
n
i
)
(
q
−
1
)
i
+
(
n
t
+
1
)
(
q
−
1
)
t
+
1
A
q
(
n
,
d
,
t
+
1
)
.
Theorem 2 (Johnson bound for
A
q
(
n
,
d
,
w
)
):
(i) If
d
>
2
w
,
A
q
(
n
,
d
,
w
)
=
1.
(ii) If
d
≤
2
w
, then define the variable
e
as follows. If
d
is even, then define
e
through the relation
d
=
2
e
; if
d
is odd, define
e
through the relation
d
=
2
e
−
1
. Let
q
∗
=
q
−
1
. Then,
A
q
(
n
,
d
,
w
)
≤
⌊
n
q
∗
w
⌊
(
n
−
1
)
q
∗
w
−
1
⌊
⋯
⌊
(
n
−
w
+
e
)
q
∗
e
⌋
⋯
⌋
⌋
⌋
where
⌊
⌋
is the floor function.
Remark: Plugging the bound of Theorem 2 into the bound of Theorem 1 produces a numerical upper bound on
A
q
(
n
,
d
)
.
