Graphical codes revisited

The set of all even subgraphs of a connected graph G on p vertices with q edges forms a binary linear code C=C_E(G) with parameters [q,q-p+1,g], where g is the girth of G. Such codes were studied systematically by Bredeson and Hakimi (1967) and Hakimi and Bredeson (1968) who were concerned with the problems of augmenting C to a larger [q,k,g]-code and of efficiently decoding such augmented graphical codes. We give a new approach to these problems by requiring the augmented codes to be graphical. On one hand, we present two construction methods which turn out to contain the methods proposed by Hakimi and Bredeson as special cases. As we show, this not only gives a better understanding of their construction, it also results in augmenting codes of larger dimension. We look at the case of 1-error-correcting graphical codes in some detail. In particular, we show how to obtain the extended Hamming codes as “purely” graphical codes by our approach. On the other hand, we follow a suggestion of Ntafos and Hakimi (1981) and use techniques from combinatorial optimization to give decoding procedures for graphical codes which turn out to be considerably more efficient than the approach via majority logic decoding proposed by Bredeson and Hakimi. We also consider the decoding problem for the even graphical code based on the complete graph K_2n in more detail: we discuss an efficient hardware implementation of an encoding/decoding scheme for these codes and show that things may be arranged in such a way that one can also correct all adjacent double errors. Finally, we discuss nonlinear graphical codes