Chordal Codes: Code Construction and Efficient Gaussian-Elimination Decoding

@misc{chen2026chordal,
  title = {{Chordal Codes: Code Construction and Efficient Gaussian-Elimination Decoding}},
  author = {Yulin Chen and Laigang Guo and Tong Li and Mingyang Zhu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.17934},
  eprint = {2610.17934},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.17934},
}

TY  - UNPB
TI  - Chordal Codes: Code Construction and Efficient Gaussian-Elimination Decoding
AU  - Yulin Chen
AU  - Laigang Guo
AU  - Tong Li
AU  - Mingyang Zhu
PY  - 2026
DA  - 2026/10/13
PB  - arXiv
DO  - 10.48550/arxiv.2610.17934
UR  - https://arxiv.org/abs/2610.17934
AB  - Maximum-likelihood decoding of linear codes over erasure channels can be considered as solving a linear system of a column submatrix of the parity-check matrix. In practice, Gaussian elimination is usually applied, and its computational cost depends on the structure of the matrix, especially the sparsity and the fill-in generated during the elimination. The \emph{chordal graph}, or \emph{triangulated graph}, first introduced by C. Berge, has a so-called \emph{perfect elimination ordering}, indicating that if the primal graph of a matrix is a chordal graph, then there exists a perfect elimination ordering such that a special class of fill-in under Gaussian elimination following this ordering will be avoided. In this paper, we introduce \emph{chordal codes}, i.e., codes equipped with parity-check matrices such that the primal graphs of the parity-check matrices are chordal. We prove that, for a chordal code, the decoding submatrix associated with any erasure pattern retains a chordal primal graph. So, the complexity of chordal elimination (Gaussian elimination following the perfect elimination ordering applied to the chordal code decoding) will be smaller than decoding a random code by Gaussian elimination. Also, we provide an upper bound on the complexity of chordal elimination.
ER  -