Covering radius of binary codes having parity-check matrices with constant-weight columns

Abstract

The binary code with parity-check matrix H_q,m whose columns are all distinct binary strings of length m and weight q ≥ 2 is denoted by C _q,m. In this paper, except for a very limited cases, the covering radius p_q,m of C_q,m, m > q, is formulated. Given an odd integer q ≥ 3, it is shown that the covering radius p_q,m, m ≥ 3q-1/2, , is 4 if m < 2q - 1, else p_q,m = [m+2q-2/qJ. Also p _q,q+1 = q + 1 and P_q,q+2 = q+3/2. The covering radius p_q,m, q an even integer and m ≥ ⌊5q+1/4⌋. is 3 if m < 2q - 1, else p_q,m = ⌊m+q-2/q⌋. For even integer q we have p_q,q+1 = q/2, and p_q,q+2 = ⌊q+4/4⌋ for q ≥ 8.