Neural Network Decoders for Permutation Codes Correcting Different Errors

Yeow Meng Chee, Hui ZhangarXiv 2022 · DOI · arXiv

Introduction

Permutation codes are essential for specialized hardware applications such as Power Line Communication (PLC) and Rank Modulation (RM) in flash memory. These environments present unique noise challenges that classical algebraic decoders often struggle to address simultaneously. In PLC, synchronization issues lead to insertion and deletion errors, while RM suffers from translocation errors where the relative ranks of stored charges shift.

This paper introduces the first general neural network-based decoders for permutation codes, treating decoding as a "one-shot" classification task using Multi-layer Perceptrons (MLPs). This approach offers a flexible solution capable of correcting a mixture of complex errors—including insertions, deletions, and translocations—where traditional algorithms are often too mathematically rigid.

Methodology

The proposed decoder utilizes an MLP architecture to perform parallel classification. Instead of predicting a single codeword, the network executes $n$ parallel classification tasks, where $n$ is the code length. Each task predicts the symbol for a specific coordinate of the codeword.

For Rank Modulation, the input retrieved permutation is passed through an embedding layer to map discrete symbols into a continuous vector space, followed by flattening and multiple fully connected layers with ReLU activations. The output layer uses Softmax to produce probability distributions for each symbol position. The model is trained by minimizing the sum of cross-entropy losses across all $n$ positions.

The MLP decoder architecture for permutation codes, featuring an embedding layer and parallel classification outputs.

Experimental Setup

The decoders were evaluated using synthetic datasets simulating real-world conditions:

  • PLC Models: Simulations included additive background noise, impulse noise, and a Markov-chain-based model for synchronization errors (insertions and deletions).
  • RM Models: Gaussian noise models were used to perturb cell charges, mimicking charge leakage and over-injection.
  • Code Families: The authors tested the decoders on known permutation code families, including Tenengolts’ codes (for sync errors) and interleaved codes (for translocations).

Results and Key Insights

The MLP decoder demonstrates a remarkable ability to learn "local features" of noise patterns, making it code-agnostic. Unlike algebraic decoders, it does not rely on specific code properties, allowing it to adapt to any error type present in the training data. Furthermore, the "one-shot" nature of the forward pass ensures very low latency compared to iterative decoding methods.

Comparison of Block Error Rate (BLER) between the optimal Minimum Distance (MD) decoder and the proposed MLP decoder across different code lengths.

As shown in the performance plots, the MLP decoder's Block Error Rate (BLER) closely approaches that of the mathematically optimal Minimum Distance (MD) decoder for short code lengths (e.g., $n=6$). Even as the code length increases to $n=8$, the MLP maintains competitive performance. Notably, the decoder proved robust against synchronization errors, achieving a BLER below $10^{-4}$ for $n=6$ in mixed error scenarios. In Rank Modulation tests, the decoder remained reliable even under significant Gaussian noise that reordered multiple cell ranks.

Conclusion and Future Work

While the "one-shot" MLP decoder provides low-latency, high-accuracy decoding for short permutation codes, scalability remains a challenge. As code length $n$ and codebook size $M$ increase, the number of parameters grows rapidly, and performance tends to decay. Future research will explore more sophisticated neural architectures beyond basic MLPs to maintain high accuracy for larger-scale permutation codes.

Summary updated

BibTeX
@misc{chee2022neural,
  author = {Yeow Meng Chee and Hui Zhang},
  title = {{Neural Network Decoders for Permutation Codes Correcting Different Errors}},
  year = {2022},
  eprint = {2206.03315},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2206.03315},
}
Figure