- Source: Johnson bound
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.
Definition
Let
C
{\displaystyle C}
be a q-ary code of length
n
{\displaystyle n}
, i.e. a subset of
F
q
n
{\displaystyle \mathbb {F} _{q}^{n}}
. Let
d
{\displaystyle d}
be the minimum distance of
C
{\displaystyle C}
, i.e.
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)}
is the Hamming distance between
x
{\displaystyle x}
and
y
{\displaystyle y}
.
Let
C
q
(
n
,
d
)
{\displaystyle C_{q}(n,d)}
be the set of all q-ary codes with length
n
{\displaystyle n}
and minimum distance
d
{\displaystyle d}
and let
C
q
(
n
,
d
,
w
)
{\displaystyle C_{q}(n,d,w)}
denote the set of codes in
C
q
(
n
,
d
)
{\displaystyle C_{q}(n,d)}
such that every element has exactly
w
{\displaystyle w}
nonzero entries.
Denote by
|
C
|
{\displaystyle |C|}
the number of elements in
C
{\displaystyle C}
. Then, we define
A
q
(
n
,
d
)
{\displaystyle A_{q}(n,d)}
to be the largest size of a code with length
n
{\displaystyle n}
and minimum distance
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)}
to be the largest size of a code in
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}
, then define the variable
e
{\displaystyle e}
as follows. If
d
{\displaystyle d}
is even, then define
e
{\displaystyle e}
through the relation
d
=
2
e
{\displaystyle d=2e}
; if
d
{\displaystyle d}
is odd, define
e
{\displaystyle e}
through the relation
d
=
2
e
−
1
{\displaystyle d=2e-1}
. Let
q
∗
=
q
−
1
{\displaystyle q^{*}=q-1}
. Then,
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 }
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
)
{\displaystyle A_{q}(n,d)}
.
See also
Elias Bassalygo bound
Gilbert–Varshamov bound
Griesmer bound
Hamming bound
Plotkin bound
Singleton bound
References
Johnson, Selmer Martin (April 1962). "A new upper bound for error-correcting codes". IRE Transactions on Information Theory: 203–207.
Huffman, William Cary; Pless, Vera S. (2003). Fundamentals of Error-Correcting Codes. Cambridge University Press. ISBN 978-0-521-78280-7.
Kata Kunci Pencarian:
- Amerika Serikat
- George Weah
- Globalisasi
- Wagon Master
- LeBron James
- Rotavirus
- Kim Kardashian
- Weipa, Queensland
- Andrew Garfield
- Ronny Cox
- Johnson bound
- Hamming bound
- Gilbert–Varshamov bound
- Block code
- Singleton bound
- Lyndon B. Johnson
- Elias Bassalygo bound
- Bound Brook, New Jersey
- Seth Johnson
- Boris Johnson
