PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Offset Min-Sum Decoding

Loren Lugosch, Warren J. Gross

arXiv:1701.05931v3cs.ITcs.LG

TL;DR

The paper addresses the hardware cost of neural belief-propagation decoders, whose learned multiplicative weights require many multiplications. It proposes neural offset min-sum decoding with learnable additive offsets and reports performance close to neural SPA while improving on traditional SPA for the studied codes.

  • Problem

    Learned multiplicative weights can improve belief-propagation decoding but require many costly multiplications, limiting efficient hardware implementation.

    Source: §I · p. 1

  • Method

    NOMS augments offset min-sum decoding with multiple learnable additive offsets optimized by treating the decoder as a deep neural network.

    Source: §III · p. 3, A. Decoding · p. 3

  • Results

    NOMS performs close to neural SPA at high SNRs, while neural decoders outperform SPA by as much as 1 dB for the codes studied.

    Source: B. Results · p. 3

  • Takeaways & Limitations

    NOMS offers a more efficient, potentially hardware-friendly alternative to neural SPA while retaining similar error-correction performance.

    Source: §I · p. 1, §III · p. 3

Abstract

from arXiv · show

Recently, it was shown that if multiplicative weights are assigned to the edges of a Tanner graph used in belief propagation decoding, it is possible to use deep learning techniques to find values for the weights which improve the error-correction performance of the decoder. Unfortunately, this approach requires many multiplications, which are generally expensive operations. In this paper, we suggest a more hardware-friendly approach in which offset min-sum decoding is augmented with learnable offset parameters. Our method uses no multiplications and has a parameter count less than half that of the multiplicative algorithm. This both speeds up training and provides a feasible path to hardware architectures. After describing our method, we compare the performance of the two neural decoding algorithms and show that our method achieves error-correction performance within 0.1 dB of the multiplicative approach and as much as 1 dB better than traditional belief propagation for the codes under consideration.

I. INTRODUCTION

Belief-propagation decoders can be improved with learned parameters, but conventional neural weighting is costly to implement. The paper motivates hardware-friendly alternatives based on min-sum decoding and learnable offsets.

Motivation

  • Neural decoders unroll Tanner-graph belief propagation and learn multiplicative edge weights to mitigate cycles and improve error correction.They can also require fewer iterations and approach maximum-likelihood performance for some high-density codes.Source: §I · p. 1
  • The multiplicative approach requires many costly multiplications, hindering efficient implementation in real-time hardware.The paper therefore targets a decoder without multiplication-heavy operations.Source: §I · p. 1

Belief propagation

  • Traditional SPA performs iterative message passing between variable and check nodes on a Tanner graph to compute soft outputs and hard decisions.The Tanner graph is derived from the code’s parity-check matrix.Source: A. Traditional Belief Propagation · pp. 1–2

Min-sum decoding

  • SPA check-node computation uses multiplications and hyperbolic functions, motivating the min-sum approximation.Min-sum replaces this computation with a simpler operation, but its approximation can degrade BER relative to SPA.Source: A. Traditional Belief Propagation · p. 2
  • Offset min-sum adds a correction offset β, and properly selecting β can bring its error-correction performance close to SPA.This provides the basis for learning multiple offsets rather than using a single fixed correction.Source: A. Traditional Belief Propagation · p. 2

B. Neural Belief Propagation

Neural belief propagation improves BP by learning multiplicative message and input weights, addressing cycle-related decoding weaknesses through gradient-based optimization. Its differentiable structure supports minibatch training with cross-entropy loss.

Motivation

  • Traditional SPA can perform poorly on high-density parity-check codes because their many short cycles prevent guaranteed optimal decoding.Cycle-less codes would permit exact posterior computation but have poor optimal performance, so practical codes contain cycles.Source: B. Neural Belief Propagation · p. 2

Neural SPA

  • Neural SPA weights input LLRs and exchanged messages with learned multiplicative parameters to bring BP performance closer to optimal performance.Setting all weights to 1 recovers ordinary SPA decoding.Source: B. Neural Belief Propagation · p. 2

Training

  • A neural SPA decoder is a differentiable composition of affine and nonlinear functions that can be trained with backpropagation and minibatch stochastic optimization.Gradients update the weight vector to reduce training loss.Source: B. Neural Belief Propagation · p. 2
  • The training objective is expected cross-entropy between decoder outputs and transmitted codewords, estimated by averaging over minibatches.The sigmoid provides a differentiable version of the hard decision used in the loss.Source: B. Neural Belief Propagation · p. 2
  • Because neural SPA preserves message-passing symmetry, training data can use AWGN-corrupted all-zeros codewords without changing the error probability.This reduces the variety of transmitted codewords needed during training.Source: B. Neural Belief Propagation · p. 3

III. NEURAL OFFSET MIN-SUM DECODING

Neural offset min-sum (NOMS) generalizes offset min-sum decoding by learning multiple additive offsets. It targets neural-SPA-like performance with lower implementation cost and potential hardware advantages.

NOMS decoding

  • NOMS learns multiple additive offsets instead of OMS’s single global offset.The offsets are optimized by treating the decoder as a deep neural network.Source: §III · p. 3
  • The learnable offsets reduce error from the min-sum approximation and attenuate cycles in the Tanner graph.This gives NOMS two roles within the same decoding mechanism.Source: §III · p. 3
  • NOMS is designed to achieve performance similar to neural SPA while being more efficient and potentially easier to implement in hardware.The section presents it as a learning algorithm rather than a fixed offset-min-sum rule.Source: §III · p. 3

A. Decoding

NOMS computes messages using OMS equations while replacing one update with learnable edge-specific offsets. These offsets are trained per iteration and preserve codeword-independent error-correction performance.

  • NOMS uses the OMS message equations, replacing Equation (14) with a modified update.Source: A. Decoding · p. 3
  • Each edge connecting check node c to variable node v has a learnable offset parameter during iteration t.Source: A. Decoding · p. 3
  • NOMS decoder performance is independent of the transmitted codeword, as in neural SPA decoding.Source: A. Decoding · p. 3

B. Training

NOMS offset parameters are learned offline with minibatch stochastic gradient descent through piecewise differentiable decoder operations.

  • NOMS offset parameters are learned offline using minibatch stochastic gradient descent.Subgradients handle nondifferentiable points in ReLU, min, abs, and sign operations.Source: B. Training · p. 3
  • Backpropagation effectively sends gradients through the ReLU branch because the derivative of sign() is zero almost everywhere.Source: B. Training · p. 3

C. Implementation Cost

NOMS reduces implementation cost relative to neural SPA by requiring fewer parameters and avoiding the additional multiplications used by neural SPA decoding.

D. Constraining Offset Count

The number of learnable NOMS offsets can be reduced by tying multiple edges to share one offset, with a single shared offset recovering OMS.

IV. EXPERIMENTS

The experiments compare NOMS with traditional and neural SPA on three BCH codes using Monte Carlo simulations, with controlled training and evaluation procedures.

  • NOMS, traditional SPA, and neural SPA were evaluated on BCH(63,36), BCH(63,45), and BCH(127,106) codes.Source: A. Experimental Setup · p. 3
  • Monte Carlo tests generated random messages, encoded them with BCH matrices, modulated codewords using BPSK, and added AWGN noise.Source: A. Experimental Setup · p. 3
  • Each SNR evaluation required at least 100 frame errors and 100,000 simulated frames to reduce BER-estimate variance.Source: A. Experimental Setup · p. 3
  • Training used 20,000 minibatches of 120 received words per SNR, all-zeros transmitted codewords, random-normal offset initialization, and Adam with learning rate 0.1.Source: A. Experimental Setup · p. 3

B. Results

Across the tested BCH codes, neural decoders outperform SPA at higher SNRs, while NOMS approaches neural SPA after training and its offsets evolve during optimization.

  • At higher SNRs, both neural decoding methods outperform SPA by as much as 1 dB.Source: B. Results · p. 3
  • NOMS performs close to neural SPA until the highest simulated SNRs.Source: B. Results · p. 3
  • Early training leaves most offsets near their standard-normal initialization, while later-iteration offsets partly match common OMS β values.Source: B. Results · p. 4
  • After 3,000 minibatches, each iteration's offset histogram develops a second mode around 7 as NOMS begins matching neural SPA's BER curve.Source: B. Results · p. 4, Figure 5 · p. 5
  • The later offset distribution is interpreted as NOMS learning both to correct the min-sum approximation and to attenuate cycles.Source: B. Results · p. 4

V. RELATED WORK

Related work uses degree-dependent OMS offsets selected by a genetic algorithm, whereas NOMS learns edge-specific offsets and can address short-cycle effects in regular BCH codes.

  • Degree-dependent OMS offsets can match SPA performance and lower some codes' BER error floors, according to prior work.Source: §V · p. 5
  • NOMS differs by assigning offsets along Tanner-graph paths, giving it potential to overcome short cycles even when all BCH check nodes share one degree.Source: §V · p. 5
  • For the regular BCH codes studied here, the prior degree-based method collapses to a single βd and therefore reverts to OMS.Source: §V · p. 5
  • The paper reports NOMS as a neural-network generalization of OMS with up to 1 dB improvement for the considered codes at a small complexity cost.Source: §VI · p. 5
  • The authors plan to study constraining the number of offsets and applying NOMS to other code types, including LDPC codes.Source: §VI · p. 5

Related papers

Loading 1701.05931v3…