Graph Decoding of Array Error-Correcting Codes

S. A. Madkour

Matan Levy, Yoni Choukroun, Lior Wolf

Error correction codes (ECC) are crucial for ensuring reliable information transmission in communication systems. Choukroun & Wolf (2022b) recently introduced the Error Correction Code Transformer (ECCT), which has demonstrated promising performance across various transmission channels and families of codes. However, its high computational and memory demands limit its practical applications compared to traditional decoding algorithms. Achieving effective quantization of the ECCT presents significant challenges due to its inherently small architecture, since existing, very low-precision quantization techniques often lead to performance degradation in compact neural networks. In this paper, we introduce a novel acceleration method for transformer-based decoders. We first propose a ternary weight quantization method specifically designed for the ECCT, inducing a decoder with multiplication-free linear layers. We present an optimized self-attention mechanism to reduce computational complexity via codeaware multi-heads processing. Finally, we provide positional encoding via the Tanner graph eigendecomposition, enabling a richer representation of the graph connectivity. The approach not only matches or surpasses ECCT's performance but also significantly reduces energy consumption, memory footprint, and computational complexity. Our method brings transformer-based error correction closer to practical implementation in resource-constrained environments, achieving a 90% compression ratio and reducing arithmetic operation energy consumption by at least 224 times on modern hardware.

Martin Bossert, F. Hergert

W.E. Ryan, Shu Hwa Lin

Combinatorial designs [1–8] form an important branch in combinatorial mathematics. In the late 1950s and during the 1960s, special classes of combinatorial designs, such as balanced incomplete block designs , were used to construct error correcting codes, especial majority-logic-decodable codes. More recently, combinatorial designs were successfully used to construct structured LDPC codes [9–12]. LDPC codes of practical lengths constructed from several classes of combinatorial designs were shown to perform very well over the binary-input AWGN channel with iterative decoding. Graphs form another important branch in combinatorial mathematics. They were also used to construct error-correcting codes in the early 1960s, but not very successfully. Only a few small classes of majority-logic-decodable codes were constructed. However, since the rediscovery of LDPC codes in the middle of the 1990s, graphs have become an important tool for constructing LDPC codes. One example is to use protographs for constructing iteratively decodable codes as described in Chapters 6 and 8. This chapter presents several methods for constructing LDPC codes based on special types of combinatorial designs and graphs. Balanced Incomplete Block Designs and LDPC Codes Balanced incomplete block designs (BIBDs) form an important class of combinatorial designs. A special subclass of BIBDs can be used to construct RC-constrained matrices or arrays of CPMs from which LDPC codes can be constructed. This section gives a brief description of BIBDs. For an in-depth understanding of this subject, readers are referred to [1–8].

Abdullah A. Hashim

Linh Nguyen, Quoc Bao Phan, Tuy Tan Nguyen

Neural decoders have recently advanced error correction performance, with transformer-based architectures in the error correction code transformer (ECCT) framework achieving state-of-the-art results among neural decoders. However, the multiple-masks ECCT suffers from suboptimal mask selection, which impacts decoding performance. In this work, we propose spectral-guided ECCT, leveraging the Laplacian matrix and its eigenvectors from the variable-variable graph to identify weakly connected node clusters for optimized mask generation. By embedding spectral properties into the decoding process, our method constructs more effective masks that improve information flow across variable and check nodes. Experimental results demonstrate consistent gains over existing ECCT-based models, achieving superior decoding accuracy and reliability while significantly improving training efficiency. This work highlights the potential of spectral graph theory to address structural challenges in neural decoders and provides a principled direction for future error correction design.