Minimum distance and decoding of Coxeter codes
2026-07-12 • Information Theory
Information Theory
AI summaryⓘ
The authors study special codes called binary Coxeter codes, which come from a type of mathematical group called a finite Coxeter system. These codes generalize known Reed--Muller codes, which are important in error correction. An earlier paper by Coble and Barg had a guess about the smallest error that could happen in these codes, called the minimum distance. In this work, the authors prove that guess is correct and use it to extend a well-known decoding method (Reed's majority-logic decoding) to their more general Coxeter codes.
binary Coxeter codefinite Coxeter systemReed--Muller codeminimum distanceerror correctionReed's majority-logic decodingCoxeter group${\mathbb F}_2$-linear spancosetcoding theory
Authors
Alexander Barg, Qëndrim R. Gashi, Tianyuan Xu
Abstract
A binary Coxeter code associated with a finite Coxeter system $(W,S)$ is an ${\mathbb F}_2$-linear span of indicators of standard cosets of a fixed rank. Coxeter codes, introduced in a recent paper by N. Coble and A. Barg, are a generalization of Reed--Muller codes which arise when $W={\mathbb Z}_2^m$ is the Coxeter group of type $mA_1$. In that paper, the authors proposed a conjectural value for the minimum distance of a general Coxeter code. This conjecture is proved in the present work. As a consequence, we obtain a Coxeter-theoretic generalization of Reed's majority-logic decoding algorithm for Reed--Muller codes.