Linear code over \(G\)

Linear code over \(G\)[1–3]

Description

Block code that encodes \(K\) states (codewords) in \(n\) coordinates over a group \(G\) such that the codewords form a subgroup of \(G^n\). In other words, the set of codewords is closed under the componentwise group operation. This notion generalizes linear codes over finite fields, but it does not require \(G\) to be a field or even Abelian.

For codes endowed with the Hamming metric on \(G^n\), the ambient isometry group contains coordinate permutations together with coordinatewise left translations by elements of \(G\). The automorphism group of a particular group code is the subgroup of those isometries that preserves the code, rather than the entire ambient group.

Rate

Linear codes over non-Abelian \(G\) cannot have better parameters than those for Abelian groups [4] and are asymptotically bad [5,6].

Encoding

Canonical encoder [7].

Cousins

Group GKP code
Slepian group-orbit code— Any finite-group code can be mapped to a Slepian group-orbit code by representing the group using orthogonal matrices [3].

Member of code lists

Primary Hierarchy

Classical Domain

Group Kingdom

Group-alphabet codeECC

Parents

Group-alphabet code

Group-orbit codeECC

The set of codewords of a linear code over \(G\) can be thought of as an orbit of a particular codeword under the group formed by the code. However, group orbit codes do not have to be linear [8; Remark 8.4.3].

Block codeECC

Linear codes over \(G\) are linear block codes with \(\Sigma=G\).

Linear code over \(G\)

Children

Lattice

Lattice-based codes are linear codes over \(G=\mathbb{R}\). Because any orthogonal matrix leaving the lattice invariant has a corresponding integer matrix (see lattice description), integer representations of groups can be used to obtain lattices [9; Ch. 3, Sec. 4.2].

Additive \(q\)-ary codeSelf-dual additive Linear \(q\)-ary Gray Evaluation MDS GRS Self-dual linear Cyclic GRM QR Projective geometry Quantum-inspired classical block Tanner \(q\)-ary LDPC Divisible

Additive \(q\)-ary codes are linear over the additive group \(G=\mathbb{F}_q\). If \(q=p^m\), they are always \(\mathbb{F}_p\)-linear, but for \(m>1\) they need not be \(\mathbb{F}_q\)-linear.

\(R\)-linear codeLinear \(q\)-ary Evaluation MDS GRS Cyclic GRM QR Projective geometry Quantum-inspired classical block Tanner \(q\)-ary LDPC Divisible Self-dual linear Linear code over \(\mathbb{Z}_q\) Gray

\(R\)-linear codes are linear over \(G=R\) since rings and submodules are Abelian groups under addition.

References

[1]: F. R. Kschischang, P. G. de Buda, and S. Pasupathy, “Block coset codes for M-ary phase shift keying”, IEEE Journal on Selected Areas in Communications 7, 900 (1989) DOI
[2]: G. D. Forney, “Geometrically uniform codes”, IEEE Transactions on Information Theory 37, 1241 (1991) DOI
[3]: H.-A. Loeliger, “Signal sets matched to groups”, IEEE Transactions on Information Theory 37, 1675 (1991) DOI
[4]: G. D. Forney, “On the Hamming distance properties of group codes”, IEEE Transactions on Information Theory 38, 1797 (1992) DOI
[5]: E. Biglieri and M. Elia, “On the construction of group block codes”, Annales Des Télécommunications 50, 817 (1995) DOI
[6]: J. C. Interlando, R. Palazzo, and M. Elia, “Group block codes over nonabelian groups are asymptotically bad”, IEEE Transactions on Information Theory 42, 1277 (1996) DOI
[7]: G. D. Forney and M. D. Trott, “The dynamics of group codes: state spaces, trellis diagrams, and canonical encoders”, IEEE Transactions on Information Theory 39, 1491 (1993) DOI
[8]: T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
[9]: J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI

Page edit log

Victor V. Albert (2022-11-07) — most recent
Victor V. Albert (2022-03-24)

Cite as:

“Linear code over \(G\)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/group_linear

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/groups/group_linear.yml.