On the combinatorial structure of a class of [m2,m−12,3] shortened Hamming codes and their dual-codes

Let HmHm be the binary linear block code with parity-check matrix HmHm whose columns are all distinct binary strings of length mm and Hamming weight 2. It is shown that HmHm is an [n,k,d]=[m(m−1)2,(m−1)(m−2)2,3] code while the dual-code Hm⊥ has dimension k⊥k⊥ and minimum distance d⊥d⊥ satisfying k⊥=d⊥=m−1k⊥=d⊥=m−1. It is in general very difficult to find or even estimate the covering radius of a given code. It is shown here that the covering radius of HmHm, denoted Cr(HmHm), is ⌊m2⌋. We also show that Cr(Hm⊥)=m(m−2)4 if mm is even and Cr(Hm⊥)=(m−1)24 if mm is odd. Thus Cr(Hm⊥)≃Cr(Hm)2. The weight distribution of Hm⊥ is given. This together with the MacWilliams identities results in an expression for the weight distribution of HmHm. It turns out that the covering radius of HmHm is equal to its external distance. From the Tanner graph perspective, the Tanner graphs of HmHm and Hm⊥ have girth 6. It is shown that the Tanner graphs of Hm+1⊥ and HmHm are essentially identical and are structurally representable by the complete graph KmKm on mm vertices.