perm2vec: Attentive Graph Permutation Selection for Decoding of Error Correction Codes

Avi Caciularu, Nir Raviv, Tomer Raviv, Jacob Goldberger, Yair Be'ery

TL;DR

This paper introduces perm2vec, a novel deep learning framework that uses self-attention and graph embeddings to intelligently select permutations for decoding error correction codes. By learning to predict the most effective permutation for a given corrupted codeword, perm2vec significantly improves decoding performance and reduces computational complexity compared to traditional methods.

What Problem Does This Paper Address?

Error correction codes are crucial for reliable communication, but finding the optimal way to decode a corrupted signal is computationally very expensive (NP-hard). A common technique, permutation decoding, involves trying different permutations of the received codeword to improve decoding accuracy. However, exhaustively checking all possible permutations is infeasible for most codes due to the sheer size of the permutation group. Existing methods often resort to random permutation selection or limited search strategies, leaving room for significant performance gains. This paper addresses the challenge of efficiently and effectively selecting the "best" permutation for decoding, thereby bridging the gap between theoretical optimality and practical implementation.

Methods

The core of the proposed solution is the perm2vec framework, which consists of two main components:

  • Permutation Embedding (perm2vec): This module learns a compact representation (embedding) for each permutation of a code. It leverages:
  • Node Embeddings: Using node2vec, the structure of the code's Tanner graph is encoded into low-dimensional vectors for each variable node. This captures the inherent graph structure of the code.
  • Self-Attention: A Transformer-based self-attention mechanism is applied to these node embeddings. This allows the model to weigh the importance of different parts of the permutation and learn complex relationships between them, creating a rich, context-aware representation of the permutation.
  • Permutation Classifier: This module takes the corrupted received word and the learned permutation embedding as input. It then predicts the probability that decoding the permuted word will be successful. This prediction is achieved using a neural network (MLP) that processes the permuted input LLRs, the syndrome, and the permutation embedding.

The overall decoding process involves:

  1. For a given corrupted word, generate embeddings for all permutations in the code's permutation group (PG).
  2. Use the permutation classifier to predict the success probability for each permuted word.
  3. Select the permutation with the highest predicted success probability.
  4. Perform the actual decoding on the selected permuted word.

Datasets

The paper does not explicitly mention specific datasets for training the perm2vec and classifier models. Instead, it describes a training procedure that uses generated data:

  • Training Data Generation: The training dataset consists of pairs of received words and labels indicating whether decoding was successful under a specific permutation. The authors mention using an "all-zero transmitted codeword" for training, and that the dataset contains pairs of permuted words and their corresponding labels.
  • Evaluation Data: For evaluation, the authors generated test data by transmitting random binary codewords over an Additive White Gaussian Noise (AWGN) channel. The SNR was varied, and batches contained an equal number of successful and unsuccessful decoding examples.

The paper focuses on evaluating the method on standard Bose-Chaudhuri-Hocquenghem (BCH) codes of varying lengths, rather than using pre-existing benchmark datasets for this specific task.

Key Insights and Ideas

  • Permutation Selection is Key: The paper strongly emphasizes that the choice of permutation is the most critical factor in permutation decoding, and that intelligently selecting it can yield significant gains.
  • Leveraging Graph Structure: By using node2vec to embed the code's Tanner graph, the model incorporates domain knowledge about the code's structure into the permutation representation. This is a novel way to inject structural information into a deep learning model for coding.
  • Power of Self-Attention: The application of self-attention to permutation embeddings allows for a nuanced understanding of permutation relationships, leading to more accurate predictions of decoding success. This is highlighted as a first for physical layer communication systems.
  • Data-Driven Approach for Intractability: The framework provides a data-driven solution to an analytically intractable problem (finding the optimal permutation), making advanced decoding techniques more practical.
  • Scalability: The permutation embeddings can be pre-computed, and the classifier's inference time scales linearly with the number of permutations, making the approach scalable to codes with large permutation groups.

Key Results

The perm2vec method demonstrated significant improvements across various BCH codes:

  • Bit Error Rate (BER) Improvements: The proposed method achieved substantial gains over baseline decoders (random permutation selection with BP and WBP). For example, for BCH(31,16), perm2vec + BP gained up to 2.75 dB over random BP.
  • Top-k Performance: Evaluating the top-k permutations showed that even with a small list (e.g., top 5), performance improvements were observed, with diminishing returns for larger k. This suggests the classifier is well-calibrated.
  • Parity-Check Matrix Exploitation: The method was shown to effectively exploit the structure of different parity-check matrices, outperforming a random selection strategy by up to 0.75 dB for certain BCH codes.
  • Efficiency: The inference time for the permutation classifier was significantly faster (10-100 times) than performing 5 BP iterations for all permutations.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that while the method significantly improves upon random selection, it does not reach the theoretical maximum likelihood lower bound.
  • The training process relies on generated data, and the performance on real-world noisy channels might differ.
  • The current implementation focuses on binary linear codes.
  • Future Work:
    • Extend the method to polar codes by embedding factor graph variable nodes instead of Tanner graph variable nodes.
  • Investigate other code families, such as non-binary Reed-Solomon codes.
  • Explore end-to-end training of perm2vec and the decoder (e.g., WBP) or iterative training approaches.
  • Further research into alternative node embedding models beyond node2vec.

Summary updated

Abstract

Error correction codes are an integral part of communication applications, boosting the reliability of transmission. The optimal decoding of transmitted codewords is the maximum likelihood rule, which is NP-hard due to the curse of dimensionality. For practical realizations, sub-optimal decoding algorithms are employed; yet limited theoretical insights prevent one from exploiting the full potential of these algorithms. One such insight is the choice of permutation in permutation decoding. We present a data-driven framework for permutation selection, combining domain knowledge with machine learning concepts such as node embedding and self-attention. Significant and consistent improvements in the bit error rate are introduced for all simulated codes, over the baseline decoders. To the best of the authors' knowledge, this work is the first to leverage the benefits of the neural Transformer networks in physical layer communication systems.
BibTeX
@article{caciularu2021perm,
  author = {Avi Caciularu and Nir Raviv and Tomer Raviv and Jacob Goldberger and Yair Be'ery},
  title = {{perm2vec: Attentive Graph Permutation Selection for Decoding of Error Correction Codes}},
  journal = {IEEE J. Sel. Areas Commun.},
  year = {2021},
  url = {https://openreview.net/forum?id=6eOXSTbkjp},
}

Loading related content...

Figure