The Elias-Bassalygo bound is a mathematical limit used in coding theory for error correction during data transmission or communications. The properties of the Elias-Bassalygo bound are defined, below, using mathematical expressions.
Let
C
be a
q
-ary code of length
n
, i.e. a subset of
[
q
]
n
. Let
R
be the rate of
C
,
δ
the relative distance and
B
q
(
y
,
ρ
n
)
=
{
x
∈
[
q
]
n
:
Δ
(
x
,
y
)
⩽
ρ
n
}
be the Hamming ball of radius
ρ
n
centered at
y
. Let
Vol
q
(
y
,
ρ
n
)
=
|
B
q
(
y
,
ρ
n
)
|
be the volume of the Hamming ball of radius
ρ
n
. It is obvious that the volume of a Hamming Ball is translation-invariant, i.e. indifferent to
y
.
In particular,
|
B
q
(
y
,
ρ
n
)
|
=
|
B
q
(
0
,
ρ
n
)
|
.
With large enough
n
, the rate
R
and the relative distance
δ
satisfy the Elias-Bassalygo bound:
R
⩽
1
−
H
q
(
J
q
(
δ
)
)
+
o
(
1
)
,
where
H
q
(
x
)
≡
def
−
x
log
q
(
x
q
−
1
)
−
(
1
−
x
)
log
q
(
1
−
x
)
is the q-ary entropy function and
J
q
(
δ
)
≡
def
(
1
−
1
q
)
(
1
−
1
−
q
δ
q
−
1
)
is a function related with Johnson bound.
To prove the Elias–Bassalygo bound, start with the following Lemma:
Lemma. For
C
⊆
[
q
]
n
and
0
⩽
e
⩽
n
, there exists a Hamming ball of radius
e
with at least
|
C
|
Vol
q
(
0
,
e
)
q
n
codewords in it.
Proof of Lemma. Randomly pick a received word
y
∈
[
q
]
n
and let
B
q
(
y
,
0
)
be the Hamming ball centered at
y
with radius
e
. Since
y
is (uniform) randomly selected the expected size of overlapped region
|
B
q
(
y
,
e
)
∩
C
|
is
|
C
|
Vol
q
(
y
,
e
)
q
n
Since this is the expected value of the size, there must exist at least one
y
such that
|
B
q
(
y
,
e
)
∩
C
|
⩾
|
C
|
Vol
q
(
y
,
e
)
q
n
=
|
C
|
Vol
q
(
0
,
e
)
q
n
,
otherwise the expectation must be smaller than this value.
Now we prove the Elias–Bassalygo bound. Define
e
=
n
J
q
(
δ
)
−
1.
By Lemma, there exists a Hamming ball with
B
codewords such that:
B
⩾
|
C
|
Vol
(
0
,
e
)
q
n
By the Johnson bound, we have
B
⩽
q
d
n
. Thus,
|
C
|
⩽
q
n
d
⋅
q
n
Vol
q
(
0
,
e
)
⩽
q
n
(
1
−
H
q
(
J
q
(
δ
)
)
+
o
(
1
)
)
The second inequality follows from lower bound on the volume of a Hamming ball:
Vol
q
(
0
,
⌊
d
−
1
2
⌋
)
⩽
q
H
q
(
δ
2
)
n
−
o
(
n
)
.
Putting in
d
=
2
e
+
1
and
δ
=
d
n
gives the second inequality.
Therefore we have
R
=
log
q
|
C
|
n
⩽
1
−
H
q
(
J
q
(
δ
)
)
+
o
(
1
)
