Source-linked AI summary
Learning to Decode Linear Codes Using Deep Learning
Eliya Nachmani, Yair Beery, David Burshtein
TL;DR
The paper addresses poor belief-propagation decoding for high-density parity-check codes and the need to avoid infeasible training over exponentially many codewords. It generalizes belief propagation with trainable Tanner-graph edge weights while preserving codeword-independent error performance. The resulting decoder improves BER over plain belief propagation, including up to 0.9 dB with multiloss training and equivalent performance to 50-iteration belief propagation using 5 iterations.
Problem
Belief propagation performs poorly for high-density parity-check codes, while training without code structure would require an infeasible collection of exponentially many codewords.
Method
The decoder retains the belief-propagation trellis architecture and trains weights assigned to Tanner-graph edges using stochastic gradient descent.
Results
The deep neural decoder consistently matches or improves belief-propagation BER, with up to 0.9 dB improvement and 50-iteration BP performance achieved using 5 iterations.
Takeaways & Limitations
The trained decoder can improve plain belief propagation without increasing required computational complexity and can learn the channel and linear code simultaneously.
Takeaways & Limitations
The method was not evaluated on parity-check matrices designed to reduce the number of small cycles.
Abstract
from arXiv · showhide
A novel deep learning method for improving the belief propagation algorithm is proposed. The method generalizes the standard belief propagation algorithm by assigning weights to the edges of the Tanner graph. These edges are then trained using deep learning techniques. A well-known property of the belief propagation algorithm is the independence of the performance on the transmitted codeword. A crucial property of our new method is that our decoder preserved this property. Furthermore, this property allows us to learn only a single codeword instead of exponential number of code-words. Improvements over the belief propagation algorithm are demonstrated for various high density parity check codes.
I. INTRODUCTION
Deep learning motivates improved decoding for high-density parity-check codes, where belief propagation performs poorly despite strong performance on LDPC codes. The proposed decoder trains Tanner-graph edge weights while preserving codeword-independent performance, enabling training from one codeword.
- LDPC codes can approach Shannon capacity with belief propagation, typically at relatively large block lengths.
- Belief propagation obtains poor results for high-density parity-check codes, including powerful algebraic codes.
- The proposed method assigns trainable weights to Tanner-graph edges, creating a soft Tanner graph.
- Preserving belief propagation's codeword-independent performance makes it sufficient to train decoder parameters using noisy versions of a single codeword.
- Improvements over belief propagation are demonstrated for BCH(63,36), BCH(63,45), and BCH(127,106) codes.
II. THE BELIEF PROPAGATION ALGORITHM
The paper represents flooding-schedule belief propagation as a trellis-based message-passing network. Channel LLRs enter through variable-node inputs, hidden layers represent Tanner-graph edge messages, and the output produces the decoded codeword.
- The Tanner graph represents the parity-check matrix, and belief propagation transmits messages over its edges.
- The trellis input layer contains N channel log-likelihood ratios, one for each variable node.
- Each hidden layer has E processing elements corresponding to Tanner-graph edges, while the final layer outputs N decoded codeword components.
- Odd and even hidden layers represent variable-to-check and check-to-variable messages, respectively, across successive belief propagation iterations.
- For an odd layer, an edge message uses messages from the same variable node on all other incident edges and also the variable's input LLR.
- The final output is the belief propagation algorithm's marginalization for each variable node.
III. THE PROPOSED DEEP NEURAL NETWORK DECODER
The proposed decoder generalizes belief propagation by training weights assigned to Tanner-graph edges while retaining BP’s trellis-based architecture. Its symmetry preserves codeword-independent error rates, allowing training from noisy versions of a single codeword.
- The decoder uses the same trellis architecture as belief propagation but assigns trainable weights to Tanner-graph edges.The weights are trained using stochastic gradient descent.
- Setting all weights to one recovers plain belief propagation, so optimal training cannot make performance inferior to BP.A sigmoid output enables cross-entropy training while preserving this initialization relationship.
- The proposed message-passing algorithm preserves symmetry conditions, making its error rate independent of the transmitted codeword on BMS channels.This property is inherited from the stated message-passing symmetry conditions.
- Training can therefore use noisy versions of only one codeword rather than an exponentially large collection of codewords.The paper uses the zero codeword for convenience.
- Edge weights can attenuate messages from parity-check nodes whose local neighborhoods contain many small cycles.The weighting is motivated as compensation for unreliable messages caused by such cycles.
- The deep neural network has time complexity similar to plain BP because both use the same number of layers and nonzero Tanner-graph weights.The architecture is illustrated for BCH(15,11).
A. Neural Network Training
The decoder is trained with cross-entropy and stochastic gradient methods in a network whose hidden layers represent multiple BP iterations. Figure 1 illustrates the architecture for BCH(15,11).
- Figure 1 depicts a BCH(15,11) network with 5 hidden layers corresponding to 3 full BP iterations and final marginalization.The first two hidden layers described in the text are merged in the figure.
- Cross entropy is used as the training loss, with accelerated training implemented in TensorFlow on an NVIDIA Tesla K40c GPU.
- The network has 10 hidden layers corresponding to 5 full BP iterations, and training uses minibatches of 120 examples with RMSPROP at learning rate 0.001.
B. Neural Network Training With Multiloss
The multiloss architecture adds intermediate final-marginalization outputs after odd-indexed hidden layers. These outputs provide additional loss terms during training.
- Final marginalization can be added after every odd-indexed hidden layer of the proposed architecture.
- Additional intermediate loss terms can increase backpropagation gradient updates and help train lower layers.
- Figure 2 illustrates the BCH(15,11) architecture with training multiloss and marks self LLR messages as small bold lines.
C. Dataset
Training data are generated by transmitting the zero codeword through an AWGN channel across SNRs from 1dB to 6dB, with matched-SNR test data.
- The dataset uses noisy transmissions of the zero codeword over an AWGN channel at SNRs ranging from 1dB to 6dB.
- Each minibatch contains 20 codewords for each SNR, totaling 120 examples.
- Test data use codewords across the same SNR range as the training dataset, with parity-check matrices taken from.
D. Results
Across various BCH block codes, the trained deep neural decoder improves or matches belief propagation, with larger gains under multiloss training and substantially fewer iterations.
- The deep neural network consistently achieves BER no larger than belief propagation across the evaluated BCH codes, with improvements up to 0.75dB in the high-SNR region.For BCH(15,11), performance approaches maximum likelihood, while larger codes remain separated from maximum likelihood.
- Multiloss training improves performance by up to 0.9dB compared to plain BP.
- Five iterations of the deep neural decoder achieve the same BER performance as 50-iteration BP, corresponding to a complexity reduction of factor 10.
- For BCH(63,45), trained neural-network weights range from −0.8 to 2.2, unlike BP weights restricted to binary 1 or 0 values.The trained hidden-layer weight distributions are close to normal, and most non-Tanner-graph weights are zero.
- Figure 3 reports BER results for the BCH(63,36) code.
V. CONCLUSIONS
The work uses trained edge weights to improve belief propagation decoding while preserving its codeword-independence property. It reports lower BER without increasing computational complexity, but remains an initial study with limited parity-check-matrix evaluation.
- V. CONCLUSIONS: Deep learning produces a “soft” Tanner graph that improves belief propagation by properly weighting messages.The authors suggest this weighting partially compensates for small cycles in the Tanner graph.
- V. CONCLUSIONS: The evaluation used parity-check matrices obtained from and did not test matrices designed to reduce the number of small cycles.
- V. CONCLUSIONS: Figures 4 and 5 report BER results for BCH(63,45) and BCH(127,106), respectively.
- V. CONCLUSIONS: After training, the decoder improves performance over plain BP without increasing the required computational complexity.
- V. CONCLUSIONS: The neural decoder learns the channel and the linear code simultaneously.
- V. CONCLUSIONS: The authors characterize the work as a first step and propose exploring new architectures, other decoding methods, and the connection between parity-check matrices and neural decoding.