Elias Bassalygo bound

Definition

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.

Proof

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 )