Anti-codes in terms of Berlekamp's switching game

Uwe Schauz*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

We view a linear code (subspace) C ≤ Fnq as a light pattern on the n-dimensional Berlekamp Board Fnq with qn light bulbs. The lights corresponding to elements of C are ON, the others are OFF. Then we allow axis-parallel switches of complete rows, columns, etc. We show that the dual code C contains a vector v of full weight, i.e. v1,v2,...,vn≠0,it and only if the light pattern C cannot be switched off. Generalizations of this allow us to describe anti-codes with maximal weight 6 in a similar way, or, alternatively, in terms of a switching game in projective space. We provide convenient bases and normal forms to the modules of all light patterns of the generalized games. All our proofs are purely combinatorial and simpler than the algebraic ones used for similar results about anti-codes in Znk. Aside from coding theory, the game is also of interest in the study of nowhere-zero points of matrices and nowhere-zero flows and colorings of graphs.

Original languageEnglish
JournalElectronic Journal of Combinatorics
Volume19
DOIs
Publication statusPublished - 2012
Externally publishedYes

Cite this