On the binary codes with parameters of triply-shortened 1-perfect codes

Abstract

We study properties of binary codes with parameters close to the parameters of 1-perfect codes. An arbitrary binary (n = 2^m − 3, 2^n-m-1, 4) code C, i.e., a code with parameters of a triply-shortened extended Hamming code, is a cell of an equitable partition of the n-cube into six cells. An arbitrary binary (n = 2^m − 4, 2^n-m, 3) code D, i.e., a code with parameters of a triply-shortened Hamming code, is a cell of an equitable family (but not a partition) with six cells. As a corollary, the codes C and D are completely semiregular; i.e., the weight distribution of such codes depends only on the minimal and maximal codeword weights and the code parameters. Moreover, if D is self-complementary, then it is completely regular. As an intermediate result, we prove, in terms of distance distributions, a general criterion for a partition of the vertices of a graph (from rather general class of graphs, including the distance-regular graphs) to be equitable.