Chordal Codes: Code Construction and Efficient Gaussian-Elimination Decoding

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.