Error-Building Decoding of Linear Block Codes

Abstract

This paper proposes a novel maximum-likelihood (ML) soft-decision decoding framework for linear block codes, termed error-building decoding (EBD). The complete decoding process can be performed using only the parity-check matrix, without requiring any other pre-constructed information (such as trellis diagrams or error-pattern lists), and it has the potential to be further customized if specific properties of the code can be exploited. We formally define error-building blocks, and derive a recursive theorem that allows efficient construction of larger locally optimal blocks from smaller ones, thereby effectively searching for the block associated with the most likely error pattern. The EBD framework is further optimized for extended Hamming codes as an example, through offline and online exclusion mechanisms, leading to a substantial complexity reduction without loss of ML performance. Complexity analysis shows that, for extended Hamming codes of lengths 64, 128, and 256, the fully optimized EBD requires approximately an order of magnitude fewer floating-point operations on average than minimum-edge trellis Viterbi decoding at a frame error rate (FER) of $10^{-3}$.

This is the full version of a paper accepted at 2026 IEEE International Symposium on Information Theory Workshops