Top Qs
Timeline
Chat
Perspective
Elias Bassalygo bound
From Wikipedia, the free encyclopedia
Remove ads
The Elias Bassalygo bound is a mathematical limit used in coding theory for error correction during data transmission or communications.
Definition
Summarize
Perspective
Let be a -ary code of length , i.e. a subset of .[1] Let be the rate of , the relative distance and
be the Hamming ball of radius centered at . Let be the volume of the Hamming ball of radius . It is obvious that the volume of a Hamming Ball is translation-invariant, i.e. indifferent to In particular,
With large enough , the rate and the relative distance satisfy the Elias-Bassalygo bound:
where
is the q-ary entropy function and
is a function related with Johnson bound.
Remove ads
Proof
Summarize
Perspective
To prove the Elias–Bassalygo bound, start with the following Lemma:
- Lemma. For and , there exists a Hamming ball of radius with at least
- codewords in it.
- Proof of Lemma. Randomly pick a received word and let be the Hamming ball centered at with radius . Since is (uniform) randomly selected the expected size of overlapped region is
- Since this is the expected value of the size, there must exist at least one such that
- otherwise the expectation must be smaller than this value.
Now we prove the Elias–Bassalygo bound. Define By Lemma, there exists a Hamming ball with codewords such that:
By the Johnson bound, we have . Thus,
The second inequality follows from lower bound on the volume of a Hamming ball:
Putting in and gives the second inequality.
Therefore we have
Remove ads
See also
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads