Varieties of binary linear codes (Q5950785)

The main objective of the paper is to look at (a part of) the problem of coding from the point of view of universal algebras. To this end, the notion of a binary code conceived as an algebra is introduced. Natural properties of codes are then expressed in universal algebraic language. Varieties and some universal algebraic properties of binary codes are investigated. Details follow. A binary code is an algebra \(\langle V,+,0,{}'\rangle \), where \(\langle V,+,0\rangle \) is a vector space over a two-element field and \({}':V\rightarrow V\) satisfies \((x')'=x'\) and \(0'=0\) (\({}'\) plays the role of a correction function, \(x'\in V\) are codewords, \(x+x'\in V\) are errors). A binary code is additive provided \((x'+y')'=x'+y'\) and uniform provided \((x'+(y+y'))'=x'\). These notions are introduced in Section~1, where some of their basic properties are also shown. Section~2 is devoted to varieties of binary codes, especially to the structure of subvarieties of the variety \(\mathcal L\) of all linear binary codes. It is shown that the lattice of subvarieties of \(\mathcal L\) is isomorphic to the linear sum of the four-element Boolean algebra and an \((\omega +1)\)-chain of varieties. Then, invoking a theorem from commutator theory, it is shown that each binary linear code is nilpotent of class \(\leq 2\). Section~3 deals with some classical codes. These codes (parity-check codes, repetition codes, free codes, and Hamming codes) are reviewed from the universal algebraic perspective.