65.154 LowerBoundCoveringRadiusEmbedded1

LowerBoundCoveringRadiusEmbedded1( n, M, false )

LowerBoundCoveringRadiusEmbedded1( n, r [, true ] )

If the last argument of LowerBoundCoveringRadiusEmbedded1 is false, then it returns a lower bound for the covering radius of a code of size M and length n. Otherwise, it returns a lower bound for the size of a code of length n and covering radius r.

This bound only works for binary codes.

It is based on the following inequality:
M left( V_2(n,r) - binomial2rr right) geq 2^n - A( n, 2r+1 ) binomial2rr,

where A(n,d) denotes the maximal cardinality of a (binary) code of length n and minimum distance d. The function UpperBound is used to compute this value.

Sometimes LowerBoundCoveringRadiusEmbedded1 is better than
LowerBoundCoveringRadiusEmbedded2, sometimes it is the other way around.

Previous Up Top Next
Index

GAP 3.4.4
April 1997