Binary codes with covering radius one: Some new lower bounds Original Research Article

We study binary codes of length n with covering radius one via their characteristic functions. The covering condition is expressed as a system of linear inequalities. The excesses then have a natural interpretation that makes congruence properties clear. We present new congruences and give several improvements on the lower bounds for K(n, 1) (the minimal cardinality of such a code) given by Zhang (1991, 1992). We study more specifically the cases n ≡ 5 mod 6 and n ≡ 2, 4 mod 6, and get new lower bounds such as K(14, 1) ⩾ 1172 and K(20, 1) ⩾ 52 456.