65.112 UpperBoundHamming

UpperBoundHamming( n, d, q )

The Hamming bound (also known as sphere packing bound) returns an upper bound on the size of a code of length n, minimum distance d, over a field of size q. The Hamming bound is obtained by dividing the contents of the entire space GF(<q>) ^<n> by the contents of a ball with radius lfloor(<d>-1) / 2rfloor. As all these balls are disjoint, they can never contain more than the whole vector space. M leq q^n over V(n,e) where M is the maxmimum number of codewords and V(<n>,e) is equal to the contents of a ball of radius e (see SphereContent). This bound is useful for small values of d. Codes for which equality holds are called perfect (see IsPerfectCode).

    gap> UpperBoundHamming( 15, 3, 2 );
    2048
    gap> C := HammingCode( 4, GF(2) );
    a linear [15,11,3]1 Hamming (4,2) code over GF(2)
    gap> Size( C );
    2048 

Previous Up Top Next
Index