The Hamming sphere-packing bound

A code correcting \(t = \lfloor (d-1)/2 \rfloor\) errors has disjoint balls of radius \(t\), so \(|C| \le q^n / \sum_{i \le t} \binom{n}{i}(q-1)^i\).

Usage

morie_hamming_bound(n, d, q = 2)

Arguments

n

Length.

d

Minimum distance.

q

Alphabet size.

Value

A list with bound, ball_volume, is_perfect_possible.

Details

A code meeting it is PERFECT, and perfect codes barely exist: over a prime power alphabet the only ones are the trivial codes, the Hamming codes and the two Golay codes.

References

Hamming RW (1950) Bell Syst Tech J 29:147-160.

Examples

morie_hamming_bound(n = 5L, d = 5L)
#> $bound
#> [1] 2
#> 
#> $bound_exact
#> [1] "2"
#> 
#> $errors_corrected
#> [1] 2
#> 
#> $ball_volume
#> [1] 16
#> 
#> $total_words
#> [1] "32"
#> 
#> $is_perfect_possible
#> [1] TRUE
#> 
#> $n
#> [1] 5
#> 
#> $d
#> [1] 5
#> 
#> $q
#> [1] 2
#> 
#> $method
#> [1] "Hamming sphere-packing bound (Hamming 1950)"
#>