Anti-codes in terms of Berlekamp's switching game

Uwe Schauz

The electronic journal of combinatorics, Tome 19 (2012) no. 1

Résumé

We view a linear code (subspace) $C\leq\mathbb{F}_{q}^n$ as a light pattern on the \(n\)-dimensional Berlekamp Board $\mathbb{F}_{q}^n$ with $q^n$ 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^\perp$ contains a vector $v$ of full weight, i.e. $v_1,v_2,\dots,v_n\neq0$, if and only if the light pattern $C$ cannot be switched off. Generalizations of this allow us to describe anti-codes with maximal weight $\delta$ 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 $\mathbb{Z}_k^n$. 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.

Détail

DOI : 10.37236/17

Classification : 94B05, 51E20, 91A46
Mots-clés : linear code, light pattern, Berlekamp board, dual code, anti-code, switching game, projective space