PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Learning Methods for Improved Decoding of Linear Codes

Eliya Nachmani, Elad Marciano, Loren Lugosch, Warren J. Gross, David Burshtein, Yair Beery

arXiv:1706.07043v2cs.ITcs.NE

TL;DR

Short-to-moderate linear codes need low-complexity decoding that approaches optimal performance despite standard BP limitations. The paper neuralizes BP and min-sum decoding, ties parameters across iterations, and applies recurrent decoders within close-to-optimal BCH decoding. These methods improve decoding performance, reduce parameters or computational complexity, and remain effective on sparser Tanner graphs.

  • Problem

    Short-to-moderate high-density parity-check codes can perform poorly with standard BP relative to maximum-likelihood decoding, while low-complexity, low-latency decoders are increasingly important.

  • Method

    The paper parameterizes BP and min-sum message passing with learnable weights or offsets, ties parameters across iterations into RNNs, and introduces relaxation-based recurrent decoding.

  • Results

    Neural decoders improve standard BP and min-sum decoding, including up to 1.5dB improvement over standard BP and reduced computational complexity in mRRD-RNN.

  • Takeaways & Limitations

    Machine learning provides a trade-off between error-correction performance and implementation complexity, with the preferred decoder depending on application needs.

  • Takeaways & Limitations

    Decoder choice remains application-dependent because additive-offset designs may perform worse than multiplicative-weight designs, while relaxation requires additional memory.

Abstract

from arXiv · show

The problem of low complexity, close to optimal, channel decoding of linear codes with short to moderate block length is considered. It is shown that deep learning methods can be used to improve a standard belief propagation decoder, despite the large example space. Similar improvements are obtained for the min-sum algorithm. It is also shown that tying the parameters of the decoders across iterations, so as to form a recurrent neural network architecture, can be implemented with comparable results. The advantage is that significantly less parameters are required. We also introduce a recurrent neural decoder architecture based on the method of successive relaxation. Improvements over standard belief propagation are also observed on sparser Tanner graph representations of the codes. Furthermore, we demonstrate that the neural belief propagation decoder can be used to improve the performance, or alternatively reduce the computational complexity, of a close to optimal decoder of short BCH codes.

I. INTRODUCTION

The paper targets low-complexity, near-optimal decoding for short-to-moderate linear codes, where standard BP performs poorly on high-density parity-check codes. It proposes neuralized BP and related architectures to improve decoding performance while reducing parameter or computational costs.

  • Motivation: Short-to-moderate high-density parity-check codes can decode poorly with standard BP compared with maximum-likelihood decoding.LDPC codes approach channel capacity with BP at relatively large block lengths, whereas short HDPC codes remain challenging.
  • Motivation: The work applies deep learning to channel decoding and builds on weighted BP methods that improve HDPC decoding by 0.9dB in the high-SNR regime.The architecture's symmetry permits training on a single codeword, such as the all-zero codeword.
  • Contributions: Parameter tying converts the feed-forward decoder into an RNN, achieving up to 1.5dB improvement over standard BP with fewer parameters.Comparable improvements are also obtained for neural min-sum decoders.
  • Contributions: The work introduces a successive-relaxation RNN decoder with excellent performance using just a single learnable parameter.It also evaluates RNN decoding on lower-density parity-check matrices with fewer short cycles.
  • Contributions: For BCH(63,36), an RNN decoder is used within mRRD to improve decoding performance or reduce the complexity of a close-to-optimal algorithm.The mRRD algorithm uses BP as a component, making replacement with the trained RNN decoder possible.
  • Decoder representation: BP is represented as a trellis whose input contains N channel LLRs, hidden layers represent Tanner-graph edge messages, and the output produces the final decoded codeword.With L full flooding-schedule iterations, the trellis has 2L hidden layers and a final marginalization.

III. A NEURAL BELIEF PROPAGATION DECODER

The neural BP decoder preserves the BP trellis while learning edge weights through stochastic gradient descent. These weights can attenuate unreliable messages associated with short cycles, while maintaining roughly BP-level time complexity.

  • Parameterized decoder: The parameterized decoder retains the BP trellis but replaces BP updates with trainable edge-weighted message-passing equations.The weights are trained using stochastic gradient descent.
  • Training: The decoder can train on noisy realizations of a single codeword because its message-passing rules preserve symmetry on binary memoryless symmetric channels.The training objective uses the final network output and a cross-entropy loss.
  • Motivation: Learned weights can compensate for small Tanner-graph cycles by attenuating messages produced by parity checks with many nearby cycles.The architecture is non-fully connected and follows the Tanner-graph connectivity.
  • Complexity: The neural decoder has roughly the same time complexity as plain BP, with one extra multiplication for each input message.Both architectures use the same number of layers and nonzero Tanner-graph weights.
  • Architecture: For BCH(15,11), the illustrated neural architecture uses five hidden layers corresponding to three full BP iterations before final marginalization.The first two hidden layers are merged in the figure.

IV. NEURAL MIN-SUM DECODING

The paper replaces computationally expensive min-sum operations with trainable normalized or offset variants. Learned parameters correct min-sum magnitude errors and also address Tanner-graph cycle effects.

  • Motivation: The min-sum approximation is used because standard BP check-node computations involve repeated multiplications and hyperbolic functions that are expensive to implement.Min-sum is a practical decoder approximation.
  • Min-sum variants: Min-sum can overstate message reliability through excessively large magnitudes, degrading bit-error rate.Normalized min-sum shrinks message magnitudes with a weight w in (0,1].
  • Neural normalized min-sum: Neural normalized min-sum assigns a learnable weight to each Tanner-graph edge and trains the decoder as a neural network.The learned weights address both min-sum approximation error and cycle effects.
  • Neural offset min-sum: Offset min-sum shrinks message magnitudes by subtracting an offset rather than multiplying by a weight, avoiding multiplications.Neural offset min-sum generalizes this method with learnable offsets.
  • Neural offset min-sum: In neural offset min-sum, max(...,0) prevents the offset from flipping the message sign, while β_i,e is the learnable edge offset.The offset is indexed by iteration and edge in the untied formulation.

V. RNN DECODING

The paper ties decoder parameters across iterations to form recurrent neural decoders, reducing the parameter count while retaining comparable decoding behavior. It also extends neural min-sum and introduces relaxation-based recurrence.

  • BP-RNN: Tying Tanner-graph edge weights across iterations transforms the feed-forward neural BP decoder into the recurrent BP-RNN architecture.The tied parameters are shared at every iteration.
  • Training: The BP-RNN initializes all edge messages to zero, preserves symmetry, and trains with a final-time-step cross-entropy objective.Final marginalization can also be added after every time step to compute intermediate losses.
  • Architecture: The recurrent architecture is illustrated with an unfold of four, corresponding to four full BP iterations.Variable, parity, and marginalization layers implement the recurrent update and output operations.
  • Recurrent min-sum: Neural min-sum decoders can likewise share the same weights or offsets at every time step by removing the iteration index from their learnable parameters.This produces recurrent versions of the neural min-sum architectures.

VI. LEARNING TO RELAX

The paper learns successive-relaxation parameters within a recurrent neural decoder instead of selecting them through trial-and-error, while preserving the decoder’s iterative structure.

  • Relaxation: Relaxation combines the previous iteration’s message with the current raw message using an exponentially weighted moving average.The relaxation factor γ controls this combination: γ = 0 gives a normal decoder, while γ approaching 1 gives a more relaxed decoder.
  • Learning relaxation: The relaxation factor can be learned with stochastic gradient descent because the relaxation operation is differentiable with respect to γ.This replaces choosing γ by simulating several candidate values and selecting the best-performing one.
  • Parameterization: A separate relaxation parameter may be assigned to each Tanner-graph edge, although a single parameter was found to perform nearly as well.The authors describe the methodology as the first approach they know that optimizes decoder relaxation factors without simple trial-and-error.
  • Architecture: The relaxed decoder is effectively a recurrent neural network with an additional shortcut connection and constrained relaxation factors in [0,1).The constraint follows from treating relaxation as an IIR filter.
  • Cost: Relaxation requires extra multiplications, additions, and memory for previous messages, making it relatively expensive compared with other neural decoder techniques.Power-of-two relaxation factors can enable multiplier-free hardware, leaving memory and additions as the additional overhead.

VII. AN MRRD ALGORITHM WITH A NEURAL BP DECODER

The paper integrates its recurrent neural BP decoder into the modified random redundant iterative decoder, replacing its BP blocks while retaining parallel branches and code automorphisms.

  • mRRD algorithm: The mRRD decoder is a close to maximum-likelihood, low-complexity decoder for short algebraic codes such as BCH codes.Its design is based on the random redundant iterative and multiple-basis belief propagation algorithms.
  • mRRD algorithm: The mRRD algorithm uses m parallel decoder branches, each applying c groups of BP iterations followed by random code automorphisms.Each branch stops when it produces a valid codeword, and a least metric selector chooses the most likely final word.
  • Neural integration: The proposed mRRD-RNN replaces the BP blocks in mRRD with the BP-RNN decoding scheme.The authors state that this combination should target near-maximum-likelihood performance with lower computational complexity.

VIII. EXPERIMENTS AND RESULTS

Experiments evaluate neural BP decoders on BCH codes with N = 63 and report improved BER over plain BP, including for cycle-reduced parity-check matrices, while using fewer parameters in the recurrent model.

  • Experimental setup: The experiments cover BCH(63,45), BCH(63,36), BCH(127,64), and BCH(127,99), with identical training, validation, and test results reported.The authors state that they did not observe overfitting in these experiments.
  • Right-regular matrices: 0.2dB: the BP-RNN decoder outperforms the BP feed-forward decoder for BCH codes with N = 63 and right-regular parity-check matrices.The BP-RNN uses fewer parameters, while multiloss training gives comparable results to BP-FF.
  • Cycle-reduced matrices: 0.6dB and 1.0dB: neural BP improves over plain BP for BCH(63,45) and BCH(63,36), respectively, with cycle-reduced parity-check matrices.The results support neural BP improvements even when the Tanner-graph representation has fewer cycles.
  • Matrix sparsity: Sparser parity-check matrices yield lower error rates for BP, but the neural decoder’s gain over plain BP is lower for these matrices.This describes the reported performance trade-off associated with sparsifying the parity-check representation.

2) BER For BCH With N = 127:

For BCH codes with N = 127, neural BP and related decoders improve BER over standard BP across right-regular and cycle-reduced parity-check matrices. Parameter tying preserves comparable performance with fewer parameters, while training-range selection affects results.

  • Right-regular parity-check matrix: Up to 1.0dB BER improvement over BP was obtained for the right-regular parity-check matrix, with BP-RNN using significantly fewer parameters than BP-FF.The comparison concerns BCH codes with N = 127.
  • Cycle-reduced parity-check matrices: Up to 0.9dB and 1.0dB improvements were obtained for BCH(127,64) and BCH(127,99), respectively, using cycle-reduced parity-check matrices.These results are reported from Figures 10 and 11.
  • Training SNR range: Performance can be further improved by choosing a training SNR range that matches the region of interest in test conditions.The robustness experiment used BCH(127,64) with a cycle-reduced parity-check matrix.
  • Neural min-sum decoders: For BCH(63,36) and BCH(63,45), multiplicatively weighted neural BP and min-sum decoders achieved similar performance, indicating little impact from the min-sum approximation.The comparisons used nonsparsified parity-check matrices.
  • Neural min-sum decoders: Multiplicative-weight decoders outperformed additive-offset decoders, although NOMS decoders still substantially outperformed non-neural decoders.This result was observed for BCH(63,36) and BCH(63,45).
  • Relaxed decoders: All relaxed decoders outperformed simple min-sum, while constraining γ = 0.875 caused a nearly imperceptible BER increase and enabled multiplier-free hardware implementation.The factor 0.125 equals 2^-3, requiring no multiplier.

C. mRRD-RNN and mRRD-NOMS

Neural decoders integrated into mRRD improve BCH(63,36) decoding over plain mRRD. The RNN variant can trade a small iteration increase for lower complexity, while mRRD-NOMS improves both error rate and decoding time in the examined SNR region.

  • mRRD-RNN: Increasing m reduced the gap to ML performance toward zero.The ML result was estimated using an ordered statistics decoder implementation.
  • mRRD-RNN: mRRD-RNN increased complexity by up to 8% in average BP iterations, but achieved the same error rate with significantly lower computational complexity through smaller m values.The complexity advantage decreased as m increased.
  • mRRD-NOMS: mRRD-NOMS improved both error rate and decoding time over corresponding mRRD decoders with the same parameters throughout the examined SNR region.The NOMS decoder used a fixed attenuation weight of 1/2.

IX. COMPLEXITY AND COMPARISON WITH OTHER

The paper positions neural mRRD decoders as low-complexity alternatives for short BCH codes, with hardware-friendly BP or min-sum operations. OSD remains constrained by soft-information requirements and serial Gaussian elimination, while neural BP can be computed in O(E) operations per iteration.

  • Comparison with other decoders: BCH codes are close to the best possible error rate for a given channel, block length, and rate when transmitting over the BIAWGNC.This motivates low-complexity decoding methods for short block lengths.
  • Comparison with other decoders: OSD combines Gaussian elimination with exhaustive search over candidate codewords, making complexity dependent on the search parameter d.The candidate-codeword distances are computed against the received observation vector.
  • Comparison with other decoders: OSD is efficient on BIAWGNC but less efficient on BSC, because efficient decoding requires soft channel information.The BSC is identified as important for memory-coding applications.
  • Comparison with other decoders: OSD Gaussian elimination is difficult to implement efficiently in low-latency hardware because it is inherently serial.This is a hardware limitation of the OSD approach.
  • Hardware and complexity: Plain and neural mRRD decoders are readily implementable in hardware because their basic operations are neural or conventional BP and min-sum decoding.The paper reports improvements over mRRD using these neural components.
  • Hardware and complexity: Efficient BP-RNN and NOMS implementations require O(E) operations per iteration, with no multiplications for NOMS.E denotes the number of Tanner-graph edges in the cited implementation discussion.

X. CONCLUSION

The paper introduces neural architectures that improve linear-code decoding, while exposing tradeoffs between error-correction performance and implementation complexity. Future work targets richer architectures, channel mismatch, quantized weights, and end-to-end mRRD learning.

  • Neural architectures yield significant improvements over standard BP and min-sum decoders, including up to 1.5dB SNR improvement on cycle-reduced parity-check matrices.
  • The new RNN architecture also improves the mRRD algorithm's performance for short BCH codes.
  • The decoders trade error-correction performance against implementation complexity, so the preferred design depends on application needs.Additive offsets may be more hardware-friendly than multipliers, while relaxed decoders require additional memory.
  • Future work includes new neural architectures, end-to-end mRRD learning, parameter tuning, quantized weights, and robustness to training–test channel mismatch.
Loading 1706.07043v2…