“Elias Bassalygo bound”的意思、由来-开放百科全书

词条

Elias Bassalygo bound

释义

Definition
Proof
See also
References

The Elias Bassalygo bound is a mathematical limit used in coding theory for error correction during data transmission or communications.

Definition

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.

Proof

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

References

1. ^Each

-ary block code of length

is a subset of the strings of

where the alphabet set

has

elements.

{{Citation
| title = New upper bounds for error-correcting codes
| year = 1965
| author = Bassalygo, L. A.
| journal = Problems of Information Transmission
| pages = 32–35
| volume = 1
| issue = 1
}}{{Citation
| title = Lower bounds to error probability for coding on discrete memoryless channels. Part I.
| year = 1967
| journal = Information and Control
| pages = 65–103
| volume = 10
| last1 = Claude E. Shannon | first1 = Robert G. Gallager
| last2 = Berlekamp
| first2 = Elwyn R.
| doi=10.1016/s0019-9958(67)90052-6
}}{{Citation
| title = Lower bounds to error probability for coding on discrete memoryless channels. Part II.
| year = 1967
| journal = Information and Control
| pages = 522–552
| volume = 10
| last1 = Claude E. Shannon | first1 = Robert G. Gallager
| last2 = Berlekamp
| first2 = Elwyn R.
| doi=10.1016/s0019-9958(67)91200-4
}}

2 : Coding theory|Articles containing proofs

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

Definition

Proof

See also

References