A Hypergraph Filtering Based Iterative Decoding Approach for Linear Channel Codes

Jiaqi He, Ruyuan Qu, Chongbin Xu, Hui Feng, Xin Wang

In the realm of digital communications, ensuring data integrity across noisy channels is paramount. While traditional algorithms like Belief Propagation (BP) have revolutionized the use of long, sparse codes such as Low-Density Parity-Check (LDPC) codes, they often falter when applied to shorter or denser linear block codes. A recent paper published in IEEE Access proposes a paradigm shift: treating the decoding process not merely as a graph-based message-passing problem, but as a signal processing task on a hypergraph.

The Challenge of Short Cycles

The primary obstacle in decoding general linear codes is the presence of short cycles within the code's Tanner graph. In standard iterative decoding, these cycles cause information to "loop" back on itself, violating the independence assumptions required for BP to reach optimal performance. This leads to sub-optimal error correction. While deep learning-based decoders have been proposed to mitigate this, they typically require massive training datasets and lack the transparency of traditional algebraic methods.

A Hypergraph Signal Processing Framework

To address these limitations, the authors introduce a framework based on Hypergraph Signal Processing (HGSP). By rethinking the decoding architecture, they bridge the gap between coding theory and high-dimensional signal processing.

Hypergraph Modeling

Instead of a standard bipartite graph, the code is modeled as a hypergraph. In this model, each coded bit is represented as a vertex, and each parity-check constraint is a hyperedge. Unlike standard edges that connect only two nodes, a hyperedge can connect any number of vertices simultaneously, capturing the complex, high-dimensional interactions inherent in linear codes.

Hypergraph representation of a linear code where vertices (bits) are connected via multi-node hyperedges (parity checks).

Decoding as Filtering

The core innovation lies in viewing the iterative flow of information as "signal shifting" on the hypergraph. The Log-Likelihood Ratio (LLR) values received from the channel are treated as a signal residing on the vertices. The decoding process then becomes a low-pass filtering operation designed to suppress noise while preserving the underlying codeword signal.

The iterative message flow in the hypergraph filtering process, illustrating how signals are processed across the structure.

The authors propose using Finite Impulse Response (FIR) filters in a cascaded structure. This design is significantly easier to optimize than standard polynomial filters and allows the decoder to effectively "smooth" the signal across the hypergraph structure. To further enhance performance, they combine this with Modified Random Redundant Iterative Decoding (mRRD), which utilizes redundant parity-check matrices to prevent the decoder from becoming trapped in local minima.

Key Results and Performance

The proposed Hypergraph Filter (HF) decoder was evaluated against classic linear block codes, including Hamming (15, 11) and various BCH codes. These codes are notoriously difficult for standard BP due to their dense parity-check matrices.

  • Superior Accuracy: On the BCH(63, 45) code, the HF decoder demonstrated significant gains over both standard BP and the Min-Sum Algorithm (MSA).
  • Outperforming Deep Learning: At a Bit Error Rate (BER) of $10^{-4}$, the HF decoder achieved a 0.1 to 0.4 dB gain over the state-of-the-art BP-RNN (a neural network-based decoder), despite requiring far less training.
  • Near-Optimal Decoding: For the Hamming(15, 11) code, the HF-mRRD variant achieved results nearly identical to the Viterbi decoder—the gold standard for Maximum Likelihood decoding—but with significantly lower computational complexity.
  • Efficiency: The algorithm maintains a computational complexity of $O(E)$, where $E$ is the number of edges, ensuring it remains as efficient as traditional message-passing methods.

Conclusion and Future Directions

By treating decoding as a filtering task, this HGSP approach offers a robust alternative to both traditional algebraic methods and data-heavy deep learning models. One of its greatest strengths is its simplicity; unlike neural decoders that require tuning millions of weights, the HF decoder only requires optimizing one or two global parameters.

Future research may explore moving from the vertex domain to the spectral domain using Hypergraph Fourier Transforms, which could unlock even more powerful filter designs. Furthermore, this framework suggests a new path for code construction: designing channel codes specifically optimized for hypergraph filtering performance.

Summary updated

Abstract

Efficient decoding for general linear channel codes has been a long standing problem. Message passing type algorithms can achieve near-optimal performance for channel codes with sparse check matrices and long code-lengths, but they may suffer from obvious performance loss when the aforementioned two conditions are not satisfied. In this paper, we propose an alternative hypergraph filtering based decoding scheme based on recently developed hypergraph signal processing (HGSP) frameworks. Specifically, we model the coded sequence as a hypergraph signal by regarding each coded bit as a vertex and representing each check constraint by a hyperedge. We then map the message passing in iterative decoding algorithms to the signal shifting in HGSP, based on which a hypergraph filtering (HF) based decoding scheme is developed. By further combining the modified random redundant iterative decoding (mRRD) technique, we finally develop a novel HF-mRRD scheme to approach the near-optimal decoding performance. Simulation results on both Hamming codes and BCH codes show that the proposed scheme obtains significant performance gains over standard message passing type algorithms, and achieve comparable or even better performance than the state-of-the-art deep learning based schemes.
BibTeX
@article{he2021hypergraph,
  author = {Jiaqi He and Ruyuan Qu and Chongbin Xu and Hui Feng and Xin Wang},
  title = {{A Hypergraph Filtering Based Iterative Decoding Approach for Linear Channel Codes}},
  journal = {IEEE Access},
  year = {2021},
  doi = {10.1109/access.2021.3079283},
}
Figure