Error-Correcting Codes in Projective Space
Tuvi Etzion, Alexander Vardy · IEEE Transactions on Information Theory · 2011
The projective space of ordernover the finite field \BBFq, denoted here asPq(n), is the set of all subspaces of the vector space \BBFqn. The projective space can be endowed with the distance functiond(U,V) = dimU+ dimV-2 dim(U∩V) which turnsPq(n) into a metric space. With this, an (n,M,d) code \BBC in projective space is a subset ofPq(n) of sizeMsuch that the distance between any two codewords (subspaces) is at leastd. Koetter and Kschischang recently showed that codes in projective space are precisely what is needed for error-correction in networks: an (n,M,d) code can correcttpacket errors and ρ packet erasures introduced (adversarially) anywhere in the network as long as 2t+ 2ρd. This motivates our interest in such codes. In this paper, we investigate certain basic aspects of “coding theory in projective space.” First, we present several new bounds on the size of codes inPq(n), which may be thought of as counterparts of the classical bounds in coding theory due to Johnson, Delsarte, and Gilbert-Varshamov. Some of these are stronger than all the previously known bounds, at least for certain code parameters. We also present several specific constructions of codes and code families inPq(n). Finally, we prove that nontrivial perfect codes inPq(n) do not exist.