Bounds on Box Codes

Let n_q(M, d) be the minimum length of a q-ary code of size M and minimum distance d. Bounding n_q(M, d) is a fundamental problem that lies at the heart of coding theory. This work considers a generalization n_q^•(M, d) of n_q(M, d) corresponding to codes in which codewords have protected and unprotected entries; where (analogs of) distance and of length are measured with respect to protected entries only. Such codes, here referred to as box codes, have seen prior studies in the context of bipartite graph covering. Upper and lower bounds on n_q^{• •}(M, d) are presented.