Source-linked AI summary
Deep Learning for Decoding of Linear Codes - A Syndrome-Based Approach
Amir Bennatan, Yoni Choukroun, Pavel Kisilev
TL;DR
Neural decoders can overfit because training cannot cover more than a small fraction of the exponentially many codewords. This paper uses syndrome and reliability inputs with unconstrained network designs, and reports strong decoding performance, including results approaching OSD.
Problem
Neural decoders can generalize poorly because training cannot cover even a small fraction of the exponentially many codewords.
Source: §I · p. 1Method
The framework feeds a network the syndrome of hard decisions and channel reliabilities, extending syndrome decoding while allowing unconstrained neural-network designs.
Source: §I · pp. 1–2Results
For BCH(63,45) over AWGN, both proposed architectures substantially outperform belief propagation, while stacked-RNN approaches order-2 OSD closely.
Source: §VI · p. 5Takeaways & Limitations
The analysis finds no loss in optimality for BER and MSE, and the framework is designed to address overfitting while focusing the network on noise estimation.
Source: C. Analysis · p. 3, §VII · p. 6
Abstract
from arXiv · showhide
We present a novel framework for applying deep neural networks (DNN) to soft decoding of linear codes at arbitrary block lengths. Unlike other approaches, our framework allows unconstrained DNN design, enabling the free application of powerful designs that were developed in other contexts. Our method is robust to overfitting that inhibits many competing methods, which follows from the exponentially large number of codewords required for their training. We achieve this by transforming the channel output before feeding it to the network, extracting only the syndrome of the hard decisions and the channel output reliabilities. We prove analytically that this approach does not involve any intrinsic performance penalty, and guarantees the generalization of performance obtained during training. Our best results are obtained using a recurrent neural network (RNN) architecture combined with simple preprocessing by permutation. We provide simulation results that demonstrate performance that sometimes approaches that of the ordered statistics decoding (OSD) algorithm.
I. INTRODUCTION
The paper addresses overfitting in neural decoding by feeding a network channel reliabilities and the syndrome of hard decisions, rather than codewords. It extends syndrome decoding to include reliabilities, analyzes its optimality, and proposes neural architectures and permutation preprocessing.
I. INTRODUCTION
- Training on sampled codewords risks poor generalization because their number grows exponentially with block length, a problem that constrained earlier networks to short block lengths.The paper identifies this as a major obstacle in [4],.Source: §I · p. 1
- Nachmani et al. [2], addressed overfitting but constrained network connections and activations to resemble belief propagation, limiting architectural freedom.The paper argues this prevents applying powerful architectures developed in other contexts.Source: §I · p. 1
- The framework feeds a network channel reliabilities and the syndrome of hard decisions, and its analysis finds no loss in optimality for BER and MSE.The framework is designed to address overfitting while leaving the noise-estimation algorithm unspecified.Source: §I · pp. 1–2
- For BCH(63,45), the proposed RNN-based decoder approaches order-2 OSD performance, and the paper proposes permutation preprocessing to improve decoding.The architectures and permutation preprocessing are described as distinct contributions.Source: §I · p. 1
II. NOTATIONS
- The notation distinguishes binary and bipolar values with superscripts b and s; bipolar(·) maps 0 to 1 and 1 to −1, and bin(·) is its inverse.The identity uses ⊕ for XOR, with vector operations applied componentwise.Source: §II · p. 2
III. BRIEF OVERVIEW OF DEEP NEURAL NETWORKS
The overview describes neural networks as layered computations whose configurable parameters are trained from data. The decoder framework feeds a network channel reliabilities and the syndrome of hard decisions, then combines its output with the channel signs.
III. BRIEF OVERVIEW OF DEEP NEURAL NETWORKS
- A multilayer network passes outputs from its first-layer neurons through successive layers, with the final layer producing the algorithm output.Its directed-graph structure is a blueprint for the associated computation.Source: §III · p. 2, Figure 1 · p. 2
- Training configures neuron weights and biases using sample inputs and, in supervised learning, desired outputs; insufficiently diverse data can impair generalization.The network's configurability allows its parameters to be tailored to different computations.Source: §III · p. 2
A. Framework Definition
- The decoder’s function F receives channel-output magnitudes |y| and the hard-decision syndrome Hyb, then its output is combined componentwise with the channel signs.For hard decisions, the result is signed; the final sign operation is omitted for soft decisions.Source: Figure 2 · p. 2, A. Framework Definition · p. 3
B. Binary-Input Symmetric-Output (BISO) Channels
The analysis considers binary-input symmetric-output channels, including AWGN and binary-symmetric channels. Their transitions can be represented using noise independent of the transmitted input.
B. Binary-Input Symmetric-Output (BISO) Channels
- The BISO class includes binary-input AWGN channels and binary-symmetric channels.Source: B. Binary-Input Symmetric-Output… · p. 3
- A BISO channel has binary input {±1} and transition probabilities satisfying Pr[Y = y | X = 1] = Pr[Y = −y | X = −1] for all outputs y.Here X and Y denote the random channel input and output.Source: B. Binary-Input Symmetric-Output… · p. 3
- For a BISO channel, transitions can be modeled as the transmitted input multiplied by equivalent random noise independent of that input.The equivalent noise is distributed as the channel output conditional on input 1.Source: B. Binary-Input Symmetric-Output… · p. 3
C. Analysis
The analysis establishes that the decoder framework can attain optimal decoding and has codeword-invariant BER and MSE under a BISO channel. The paper then describes neural-network implementations, including vanilla and stacked-RNN architectures, and their training setup.
C. Analysis
- With an appropriately designed F, the framework can achieve MAP or MMSE decoding, and its BER and MSE conditioned on transmission are invariant to the codeword under a BISO channel.The analysis frames this result as avoiding intrinsic performance loss while addressing overfitting.Source: C. Analysis · p. 3
A. Deep Neural Network Architectures
- The vanilla network uses 11 fully connected layers with ReLU activations in its first 10 layers and a tanh output layer; its input is fed to every layer.The first 10 layers use 6N nodes for block length 64 and 15N for block length 127.Source: A. Deep Neural Network Architectures · p. 3, Figure 3 · p. 4
- The stacked RNN uses four GRU levels, hidden-state size 5N, and five time steps; its stacked design is more memory-efficient in practice.The paper notes that temporal processing is not the interpretation used in this setting.Source: A. Deep Neural Network Architectures · p. 4, Figure 4 · p. 4
- Training simulates the all-one codeword and multiplicative noise, while testing uses randomly generated codewords; AWGN training uses a mean-1 Gaussian noise model.Training Eb/N0 was set arbitrarily to 4 dB and could potentially be improved.Source: A. Deep Neural Network Architectures · p. 4
- The reported best training procedure generates new noise samples with each batch; fixed-noise training with methods such as dropout remains worth exploring.Source: A. Deep Neural Network Architectures · p. 4
B. Preprocessing by Permutation
The decoder permutes the channel output before decoding and reverses that permutation afterward. The preprocessing orders the first K components to be more reliable, giving the network additional input structure.
B. Preprocessing by Permutation
- The input is permuted before decoding and the inverse permutation is applied to the decoder output.The preprocessing and postprocessing components are part of training as well as inference.Source: B. Preprocessing by Permutation · pp. 4–5
- The selected permutation maximizes the sum of adjusted reliabilities among the first K components and is restricted to code automorphisms.The adjusted reliability is mutual information conditioned on the channel-output magnitude; the criterion concentrates channel capacity in the first K components.Source: B. Preprocessing by Permutation · pp. 4–5
- Automorphism-restricted permutations preserve valid codewords, while the decoder receives the first K channel outputs as consistently more reliable than the rest.This gives the network additional structure to use; preprocessing was not necessary for the shorter BCH(63,45) code but was used for BCH(127,64).Source: B. Preprocessing by Permutation · p. 5
VI. SIMULATION RESULTS
Simulations show that both syndrome-based methods outperform BP on the tested BCH codes, with results relative to OSD depending on code length and preprocessing. The stacked RNN closely approaches OSD on BCH(63,45), while a gap remains on BCH(127,64).
VI. SIMULATION RESULTS
- The simulations used 10^5 codewords per Eb/N0 point for the proposed algorithms, 10^4 for OSD, and 10^3 for BP.For BCH(127,64), no OSD errors were observed at Eb/N0 of 4 dB or higher.Source: §VI · p. 5
- On BCH(63,45), both architectures substantially outperform BP, and the stacked RNN approaches OSD closely without permutation preprocessing.The comparison uses an AWGN channel; the OSD results are based on 10^4 simulated codewords per Eb/N0 point.Source: Figure 6 · p. 5, §VI · p. 5
- Preprocessing substantially benefits the stacked RNN on BCH(127,64), but both variants retain a gap to OSD that widens with Eb/N0.Both methods outperform BP and the best results of [2].Source: Figure 7 · p. 5, §VI · p. 5
VII. CONCLUSION
The paper concludes that syndrome decoding extended with soft reliabilities addresses overfitting while permitting unconstrained neural-network architectures. Simulations show performance approaching OSD, with further architecture, preprocessing, latency, and complexity questions left for future work.
VII. CONCLUSION
- Syndrome decoding with soft channel reliabilities lets the network estimate noise rather than the transmitted codeword, eliminating overfitting to the training codeword set.The overfitting issue had constrained earlier networks to short block lengths [4],.Source: §VII · p. 6
- Unlike the BP-structured design of Nachmani et al. [2], this framework allows unconstrained neural-network architectures.That freedom allows architectures to draw on broader neural-network design experience.Source: §VII · p. 6
- Simulations show strong performance that approaches OSD, while further work is proposed on architectures beyond RNNs, preprocessing, latency, and complexity.The paper presents this as a direction for future research, not as a completed evaluation.Source: §VII · p. 6
APPENDIX I PROOF OF THEOREM 1
The appendix proves the theorem by establishing matrices that encode both parity checks and message information, then deriving decoder-output properties from the framework. It concludes that the BER and MSE errors considered are independent of the transmitted codeword.
APPENDIX I PROOF OF THEOREM 1
- A matrix A can map each codeword representation to its message, and the concatenated matrix B = [H^T, A^T]^T has full column rank and is injective.The proof constructs A as a left inverse of the generator matrix and establishes the rank claim using a right inverse of H.Source: Appendix I · p. 6
- The proof derives decoder decisions from the channel-output magnitudes and syndrome, using the uniform transmitted-message assumption in its conditioning argument.It treats MAP decisions and MMSE estimates separately; the soft-decision case omits the final sign operation.Source: Appendix I · pp. 6–7
- For both BER and MSE, the decoder error is independent of the transmitted codeword under the stated framework.For BER, the differing indices depend on f(ẑ); for MSE, the expression reduces to ||f(ẑ) − 1||^2.Source: Appendix I · p. 7
APPENDIX II AUTOMORPHISMS OF BCH CODES
The appendix describes automorphisms of primitive narrow-sense binary BCH codes, including those used in Sec VI, and explains how to find an optimal permutation efficiently. It also shows how to incorporate permutation preprocessing and postprocessing into the framework’s function F.
APPENDIX II AUTOMORPHISMS OF BCH CODES
- For primitive narrow-sense binary BCH codes, the blocklength is N = 2^m − 1, and the automorphism group includes permutations parameterized by k and l.These include the codes used in Sec VI.Source: APPENDIX II AUTOMORPHISMS OF BCH CODES · p. 7
- The optimal permutation maximizes the sum of adjusted reliabilities over the first K components of the permuted codeword.For k = 0, the candidate permutations are cyclic, and cumulative sums find the best one; for other k, apply πk,0 before the cyclic-permutation procedure.Source: APPENDIX II AUTOMORPHISMS OF BCH CODES · p. 7
- The optimal permutation across all k is found by combining the results for each k from 0 to m−1.The cumulative sum can be computed in logarithmic time by recursively splitting the range 0, ..., N−1.Source: APPENDIX II AUTOMORPHISMS OF BCH CODES · p. 7
- Although Fig. 5’s decoder formally falls outside the framework, preprocessing and postprocessing can be absorbed into F for BCH codes.The preprocessing permutation is realized by permuting |y| and manipulating the syndrome using identities in; the optimal-permutation selection and postprocessing are also included in F.Source: APPENDIX II AUTOMORPHISMS OF BCH CODES · p. 7