Let
C
{\displaystyle C}
q -ary code of length
n
{\displaystyle n}
F
q
n
{\displaystyle \mathbb {F} _{q}^{n}}
d
{\displaystyle d}
C
{\displaystyle C}
d
=
min
x
,
y
∈
C
,
x
≠
y
d
(
x
,
y
)
,
{\displaystyle d=\min _{x,y\in C,x\neq y}d(x,y),}
where
d
(
x
,
y
)
{\displaystyle d(x,y)}
Hamming distance between
x
{\displaystyle x}
y
{\displaystyle y}
Let
C
q
(
n
,
d
)
{\displaystyle C_{q}(n,d)}
q -ary codes with length
n
{\displaystyle n}
d
{\displaystyle d}
C
q
(
n
,
d
,
w
)
{\displaystyle C_{q}(n,d,w)}
C
q
(
n
,
d
)
{\displaystyle C_{q}(n,d)}
w
{\displaystyle w}
Denote by
|
C
|
{\displaystyle |C|}
C
{\displaystyle C}
A
q
(
n
,
d
)
{\displaystyle A_{q}(n,d)}
n
{\displaystyle n}
d
{\displaystyle d}
A
q
(
n
,
d
)
=
max
C
∈
C
q
(
n
,
d
)
|
C
|
.
{\displaystyle A_{q}(n,d)=\max _{C\in C_{q}(n,d)}|C|.}
Similarly, we define
A
q
(
n
,
d
,
w
)
{\displaystyle A_{q}(n,d,w)}
C
q
(
n
,
d
,
w
)
{\displaystyle C_{q}(n,d,w)}
A
q
(
n
,
d
,
w
)
=
max
C
∈
C
q
(
n
,
d
,
w
)
|
C
|
.
{\displaystyle A_{q}(n,d,w)=\max _{C\in C_{q}(n,d,w)}|C|.}
Theorem 1 (Johnson bound for
A
q
(
n
,
d
)
{\displaystyle A_{q}(n,d)}
If
d
=
2
t
+
1
{\displaystyle d=2t+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
)
.
{\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{i=0}^{t}{n \choose i}(q-1)^{i}+{\frac {{n \choose t+1}(q-1)^{t+1}-{d \choose t}A_{q}(n,d,d)}{A_{q}(n,d,t+1)}}}}.}
If
d
=
2
t
+
2
{\displaystyle d=2t+2}
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
)
.
{\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{i=0}^{t}{n \choose i}(q-1)^{i}+{\frac {{n \choose t+1}(q-1)^{t+1}}{A_{q}(n,d,t+1)}}}}.}
Theorem 2 (Johnson bound for
A
q
(
n
,
d
,
w
)
{\displaystyle A_{q}(n,d,w)}
(i) If
d
>
2
w
,
{\displaystyle d>2w,}
A
q
(
n
,
d
,
w
)
=
1.
{\displaystyle A_{q}(n,d,w)=1.}
(ii) If
d
≤
2
w
{\displaystyle d\leq 2w}
e
{\displaystyle e}
d
{\displaystyle d}
e
{\displaystyle e}
d
=
2
e
{\displaystyle d=2e}
d
{\displaystyle d}
e
{\displaystyle e}
d
=
2
e
−
1
{\displaystyle d=2e-1}
q
∗
=
q
−
1
{\displaystyle q^{*}=q-1}
A
q
(
n
,
d
,
w
)
≤
⌊
n
q
∗
w
⌊
(
n
−
1
)
q
∗
w
−
1
⌊
⋯
⌊
(
n
−
w
+
e
)
q
∗
e
⌋
⋯
⌋
⌋
⌋
{\displaystyle A_{q}(n,d,w)\leq \left\lfloor {\frac {nq^{*}}{w}}\left\lfloor {\frac {(n-1)q^{*}}{w-1}}\left\lfloor \cdots \left\lfloor {\frac {(n-w+e)q^{*}}{e}}\right\rfloor \cdots \right\rfloor \right\rfloor \right\rfloor }
where
⌊
⌋
{\displaystyle \lfloor ~~\rfloor }
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
)
{\displaystyle A_{q}(n,d)}
