Factor Graph Optimization of Error-Correcting Codes for Belief Propagation Decoding

## Abstract

Abstract The design of optimal linear block codes capable of being efficiently decoded is of major concern, especially for short block lengths.
As near capacity-approaching codes, Low-Density Parity-Check (LDPC) codes possess several advantages over
other families of codes, the most notable being its efficient decoding via Belief Propagation.
While many LDPC code design methods exist, the development of efficient sparse codes that meet the constraints of modern short code lengths and accommodate new channel models remains a challenge.
In this work, we propose for the first time a gradient-based data-driven approach for the design of sparse codes. We develop locally optimal codes with respect to Belief Propagation decoding via the learning of the Factor graph under channel noise simulations.
This is performed via a novel complete graph tensor representation of the Belief Propagation algorithm, optimized over finite fields via backpropagation and coupled with an efficient line-search method.
The proposed approach is shown to outperform the decoding performance of existing popular codes by orders of magnitude and demonstrates the power of data-driven approaches for code design.

## 1 Introduction

Reliable digital communication is of major importance in the modern information age and involves the design of codes that can be robustly and efficiently decoded despite noisy transmission channels.
Over the last half-century, significant research has been dedicated to the study of capacity-approaching Error Correcting Codes (ECC) (Shannon, ).
Despite the initial focus on short and medium-length linear block codes (Berlekamp, ), the development of long channel codes (Forney, ; Costello & Forney, ) has emerged as a viable approach to approaching channel capacity (Berrou et al., ; MacKay, ; Richardson et al., ; Richardson & Urbanke, ; Arikan, ; Luby et al., ; Kudekar et al., ).

While the NP-hard maximum likelihood rule defines the target decoding of a given code, developing more practical solutions generally relies on theories grounded upon asymptotic analysis over conventional communication channels.
However, modern communication systems rely on the design of short and medium-block-length codes (Liva et al., ) and the latest communication settings provide new types of channels.
This is mainly due to emergent applications in the modern wireless realm requiring the transmission of short data units, such as remote command links, Internet of Things, and messaging services (De Cola et al., ; Boccardi et al., ; Paolini et al., ; Durisi et al., ; ESTI, ).
These challenges call for the formulation of data-driven solutions, capable of adapting to various settings of interest and constraints, generally uncharted by existing theories.

The vast majority of existing machine-learning solutions to the ECC problem concentrate on the design of *neural decoders*. The first neural models focused on the implementation of parameterized versions of the legacy Belief Propagation (BP) decoder (Nachmani et al., ; ; Lugosch & Gross, ; Nachmani & Wolf, ; Buchberger et al., ).
Recently, state-of-the-art learning-based de novo decoders have been introduced, borrowing from well-proven architectures from other domains.
A Transformer-based decoder that incorporates the code into the architecture has been recently proposed by (Choukroun & Wolf, ), outperforming existing methods by sizable margins and at a fraction of their time complexity.
This architecture has been subsequently integrated into a denoising diffusion models paradigm, further improving results (Choukroun & Wolf, ).
Subsequently, a universal neural decoder has been proposed in (Choukroun & Wolf, ), capable of unified decoding of codes from different families, lengths, and rates.
Most recently and related to our work, (Choukroun & Wolf, ) developed an end-to-end learning framework capable of co-learning binary linear block codes along with the neural decoder.

However, neural decoding methods require increased computational and memory complexity compared to their well-established classical counterparts. Due to these challenges, and the non-trivial acceleration and implementation required, neural decoders were never deployed in real-world systems, as far as we know.

In this work, given the ubiquity and advantages of the Belief Propagation (BP) algorithm (Pearl, ; Richardson et al., ) for sparse codes, we consider the optimization of codes with respect to BP via the learning of the underlying factor/Tanner graph.
From a graphical probabilistic model perspective Koller & Friedman (), BP being a marginalization algorithm, a gradient-based of a score metric method is given for the *structure learning* of BP’s underlying Bayesian network in an end-to-end fashion.
As far as we can ascertain, this is the first time a gradient-based data-driven solution is given for the design of the codes themselves based on a classical decoder. Such a solution induces a very low overhead (if any) for integration into the existing decoding solutions.

Beyond the conceptual novelty, we make three technical contributions: (i) we formulate the data-driven optimization objective adapted to the setting of interest (e.g., channel noise, code structure), (ii) we reformulate BP in a tensor fashion to learn the connectivity of the factor graph through backpropagation, and (iii) we propose a differentiable and fast optimization approach via a line-search method adapted to the relaxed binary programming setting.
Applied to a wide variety of codes, our method produces codes that outperform existing codes on various channel noise settings, demonstrating the power and flexibility of the method in adapting to realistic settings of interest.

## 2 Related Works

Neural decoder or data-driven contributions generally focus on short and moderate-length codes for two main reasons.
First, classical decoders reach the capacity of the channel for large codes, and
second, the emergence of applications driven by the Internet of Things requires effective decoders for short to moderate-length codes. For example, 5G Polar codes have code lengths of 32 to 1024 (Liva et al., ; ESTI, ).

Previous work on neural decoders is generally divided into two main classes: model-free and model-based. Model-free decoders employ general types of neural network architectures (Cammerer et al., ; Gruber et al., ; Kim et al., ; Bennatan et al., ; Jiang et al., ; Choukroun & Wolf, ; ; ; ). Model-based decoders implement parameterized versions of classical Belief Propagation (BP) decoders, where the Tanner graph is unfolded into an NN in which scalar weights are assigned to each variable edge. This results in an improvement in comparison to the baseline BP method for short codes (Nachmani et al., ; Nachmani & Wolf, ; Raviv et al., ; ; Kwak et al., ). While model-based decoders benefit from a strong theoretical background, the architecture is overly restrictive, which generally enforces its coupling with high-complexity NN (Nachmani & Wolf, ). Also, the improvement gain generally vanishes for more iterations and longer codewords (Hoydis et al., ) and the integration cost remains very high due to both computational and memory requirements.

While neural decoders show improved performance in various communication settings, there has been very limited success in the design of novel neural coding methods, which remain impracticable for deployment (O’Shea & Hoydis, ; Kim et al., ; Jiang et al., ).
Recently, (Choukroun & Wolf, ) provided a new differentiable way of designing binary linear block codes (i.e., parity-check matrices) for a given neural decoder also showing improved performance with classical decoders.

Belief-propagation decoding has multiple advantages for LDPC codes (Gallager, ; Richardson & Urbanke, ; Richardson et al., ).
A large number of LDPC code (parity check matrix) design techniques exist in the literature, depending on the design criterion.
Among them, Gallager (Gallager, ) developed the first regular LDPC codes as the concatenations of permuted sub-matrices. MacKay (MacKay & Neal, ) demonstrated the ability of sparse codes to reach near-capacity limits via semi-randomly generated matrices. Irregular LDPC codes have been developed by (Richardson et al., ; Luby et al., ; Chung et al., ) where the decoding threshold can be optimized via density-evolution.
Progressive Edge Growth (Hu et al., ; ) has been proposed to design large girth codes.
Certain classes of LDPC array codes have been presented in (Eleftheriou & Olcer, ) and LDPC codes with combinatorial design constraints have been developed in (Vasic & Milenkovic, ).
Finite geometry codes have been developed in (Lucas et al., ; Kou et al., ) and repeat-accumulate codes have been proposed by (Yang et al., ; Jin et al., ; Narayanaswami, ).
However, the classical methods are not data-driven and are difficult to adapt to the design of codes under constrained settings of interest (e.g., short codes, modern channels, structure constraints, etc.).
Most related to our work are methods for structure learning Koller & Friedman () for Bayesian networks such as the Chow-Liu Algorithm Chow & Liu () or search-based methods Tian ().
Related to greedy search-based methods, Elkelesh et al. () recently suggested the application of classical genetic algorithms for the discovery of better IRA codes.

## 3 Background

We assume a standard transmission protocol using a linear block code $C$. The code is defined by a generator matrix $G\in\{0,1\}^{k\times n}$ and the parity check matrix $H\in\{0,1\}^{(n-k)\times n}$ is defined such that $GH^{T}=0$ over the order 2 Galois field $GF(2)$.
The parity check matrix $H$ entails what is known as a Tanner graph (Tanner, ), which consists of $n$ variable nodes and $(n-k)$ check nodes. The edges of this bipartite graph correspond to the on-bits of the matrix $H$.

The input message $m\in\{0,1\}^{k}$ is encoded by $G$ to a codeword $c\in C\subset\{0,1\}^{n}$ satisfying $Hc=H(mG)=0$ and transmitted via a Binary-Input Symmetric-Output channel, e.g., an AWGN channel.
Let $y$ denote the channel output represented as $y=c_{s}+\varepsilon$, where $c_{s}$ denotes the transmission modulation of $c$ (e.g., Binary Phase Shift Keying (BPSK)), and $\varepsilon$ is random noise independent of the transmitted $c$.
The main goal of the decoder $f_{H}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ conditioned on the code (i.e., $H$) is to provide a soft approximation $\hat{x}=f_{H}(y)$ of the codeword.

The Belief Propagation algorithm allows the iterative transmission (propagation) of a current codeword estimate (belief) via a Trellis graph determined according to a *factor graph* defined by the code (i.e., the Tanner graph). The factor graph is unrolled into a Trellis graph, initiated with $n$ variable nodes, and composed of two types of interleaved layers defined by the check/factor nodes and variable nodes.
An illustration of the Tanner graph unrolled to the Trellis graph is given in Figure  1.

As a message-passing algorithm, Belief Propagation operates on the Trellis graph by propagating the messages from variable nodes to check nodes and from check nodes to variable nodes, in an alternative and iterative fashion. The input layer generally corresponds to the vector of log-likelihood ratios (LLR) $L\in\mathbb{R}^{n}$ of the channel output $y$ defined as

$$ $L_{v}=\log\bigg{(}\frac{\Pr\left(c_{v}=1|y_{v}\right)}{\Pr\left(c_{v}=0|y_{v} \right)}\bigg{)}.$ $$

Here, we describe ECC’s classical notation of BP with, $v\in\{1,\dots,n\}$ denotes the index corresponding to the $v^{th}$ element of the channel output $y$, for the corresponding bit $c_{v}$ we wish to recover.

Let $x^{i}$ be the vector of messages that a column/layer in the Trellis graph propagates to the next one.
At the first round of message passing, a variable node type of computation is performed such that

$$ $x^{2k+1}_{e}=x^{2k+1}_{(c,v)}=L_{v}+\sum_{e^{\prime}\in N(v)\setminus\{(c,v)\} }x^{2k}_{e^{\prime}}.$ (1) $$

Here, each message indexed by the edge $e=(c,v)$ on the Tanner graph and $N(v)=\{(c,v)|H(c,v)=1\}$, i.e, the set of all edges in which $v$ participates. By definition $x^{0}=0$ such that the messages are directly determined by the vector $L$ for $k=1$.

For even layers, the check layer performs the following

$$ $x^{2k}_{e}=x^{2k}_{(c,v)}=2\text{arctanh}\left(\prod_{e^{\prime}\in N(c) \setminus\{(c,v)\}}{\tanh\left(\frac{x^{2k-1}_{e^{\prime}}}{2}\right)}\right)$ (2) $$

where $N(c)=\{(c,v)|H(c,v)=1\}$ is the set of edges in the Tanner graph in which row $c$ of the parity check matrix $H$ participates.

The final $v^{th}$ output layer of the BP algorithm, which corresponds to the soft-decision output of the codeword, is given by

$$ $o_{v}=L_{v}+\sum_{e^{{}^{\prime}}\in N(v)}x_{e^{{}^{\prime}}}^{2L}$ (3) $$

Figure: Figure 1: For the Hamming(7,4) Code: (a) parity check matrix, the induced (b) Tanner graph, and (c) the corresponding unrolled Trellis graph with two iterations, with odd layers in blue and even layers in red. In (d) we present our approach for structure learning via the learned binary weighting of the edges of the *complete* bipartite factor graph unlike the conventional sparse representation.
Refer to caption: extracted/5916351/Images/Illustrations/treillis3.png

## 4 Method

The performance of BP is strongly tied to the underlying Tanner graph induced by the code. BP and its variants are generally implemented over a *fixed* sparse graph, such that the only degree of freedom resides in the number of decoding iterations.
While several recent contributions (Nachmani et al., ; Nachmani & Wolf, ) aim to enhance the BP algorithm by augmenting the Trellis graph with neural networks, these approaches assume and maintain fixed codes.
Here, we propose optimizing the code for the BP algorithm on a decoding setting of interest. Given a trainable binary parity check matrix $H$, we wish to obtain BP-optimized codes by solving the following parameterized optimization problem

$$ $\displaystyle H^{*}=\operatorname*{arg\,min}_{H\in\{0,1\}^{(n-k)\times n}} \mathbb{E}_{m\sim\text{Bern}^{k}({\nicefrac{{1}}{{2}}}),\varepsilon\sim \mathcal{Z},T\in\mathbb{N}_{+}}$ $\displaystyle\mathcal{D}\bigg{(}f_{H,T}\big{(}\phi(G(H)m)+{\varepsilon}\big{)} ,m\bigg{)}+\mathcal{R}(H)$ (4) $$

Here, $G(H)$ denotes the generator matrix defined by $H$ (i.e., $GH^{T}=0$), $\phi$ denotes the modulation function such that $c_{s}=\phi(c)$, and $\mathcal{Z}$ is the channel noise distribution.
$f_{H,T}$ denotes the BP decoder built upon $H$ with $T$ iterations (sampled uniformly from a given set), $\mathcal{D}$ denotes the distance metric of interest, and $\mathcal{R}$ denotes the potential hard/soft regularization of interest, e.g., sparsity or constraints on the code structure.

Several challenges arise from this optimization problem:
(i) the optimization is highly non-differentiable and results in an NP-hard binary non-linear integer programming problem,
(ii) the computation of the codewords $c=Gm$ is both highly non-differentiable (matrix-vector multiplication over $GF(2)$) and computationally expensive (inverse via Gaussian elimination of $H$),
(iii) the modulation $\phi(\cdot)$ can be non-differentiable, and
last but most important, (iv) BP assumes a *fixed* code (i.e., the factor graph edges) upon which the decoder is implemented.

### Learning the Factor graph via Tensor Belief Back propagation

To obtain BP codes, we propose a *structure/Tanner graph learning* approach, where the bipartite graph is assumed as complete with learnable binary-weighted edges. This way, the tensor reformulation of BP weighted by $H$ allows a differentiable optimization of the Tanner graph itself. The two alternating stages of BP can now be represented in a differentiable matrix form rather than its static graph formulation, where the variable layers can be rewritten as

$$ $\displaystyle Q_{ij}$ $\displaystyle=L_{i}+\sum_{j^{\prime}\in C_{i}\setminus j}{R_{j^{\prime}i}} \equiv L_{i}+\sum_{j^{\prime}}{R_{j^{\prime}i}H_{j^{\prime}i}}-R_{ji}\,,$ (5) $$

where $R_{ij}$ are the check layers, which are now represented as

$$ $\displaystyle R_{ji}$ $\displaystyle=2\text{arctanh}\left(\prod_{i^{\prime}\in V_{j}\setminus i}{ \tanh\left(\frac{Q_{i^{\prime}j}}{2}\right)}\right)$ (6) $\displaystyle=2\text{arctanh}\left(\prod_{i^{\prime}}\left({\tanh\left(\frac{Q _{i^{\prime}j}H_{ji^{\prime}}}{2}\right)+\left(1-H_{ji^{\prime}}\right)}\right )/(\tanh\left(\frac{Q_{ij}}{2}\right)\right)\,,$ $$

where $C_{i}$ and $V_{j}$ correspond to the non-zero elements in column $i$ and row $j$ of $H$, respectively, while the ones elements in $(1-H)\in\{0,1\}^{(n-k)\times n}$ satisfy the identity element of multiplication.
Potential zero denominators have not been observed but can be handled via regularization or omission.
As we can observe, BP remains differentiable with respect to $H$ as a composition of differentiable functions.

We provide in Algorithm 1 the pseudo-code for the tensor formulation of the BP algorithm, implementing Eq. 6 and 5.

Figure: Algorithm 1 Tensor Belief Propagation

### Belief Propagation Codes Optimization

The tensor reformulation solves the major challenge of graph learning (challenge (iv)). Challenges (ii) and (iii) are also eliminated in our formulation.
First, since for any given $H$ the conditional independence of error probability under symmetry (Richardson & Urbanke, ) is satisfied for message passing algorithms, it is enough to optimize the zero codeword only, i.e., $c=Gm=0$, removing then any dependency on $G$ in the objective (challenge (ii)).
As a byproduct, we obtain that the optimization problem is invariant to the choice of modulation, whether differentiable or not (challenge (iii)).

To optimize $H$ (challenge (i)) we relax the NP-hard binary programming problems to an unconstrained objective where, given a parameter matrix $\Omega\in\mathbb{R}^{(n-k)\times n}$, we have $H\coloneqq H(\Omega)=\operatorname{bin}(\Omega)$. Here $\operatorname{bin}(\cdot)$ refers to the element-wise binarization operator implemented via the shifted straight-through-estimator (STE) (Bengio et al., ) defined such that

$$ $\displaystyle\operatorname{bin}(u)=(1-\text{sign}(u))/2\,,\quad{\partial \operatorname{bin}(u)}/{\partial u}\coloneqq-0.5\text{1}_{|u|\leq 1}$ (7) $$

Finally, opting for the binary cross-entropy loss (BCE) as the Bit Error rate (BER) discrepancy measure $\mathcal{D}=\text{BCE}$, we obtain the following empirical risk objective

$$ $\displaystyle\mathcal{L}(\Omega)=\sum_{t=1}^{T}\sum_{i=1}^{n}\text{BCE}\bigg{( }f_{\operatorname{bin}(\Omega),t}\big{(}c_{s}+{\varepsilon_{i}}\big{)},c\bigg{ )}+\mathcal{R}(\operatorname{bin}(\Omega))$ (8) $$

where $c_{s}=\phi(c)$ denotes the modulated *zero codeword* and $\varepsilon_{i}$ denotes the $i^{th}$ noise sample drawn from the channel noise distribution.
This objective aims to provide optimal decoding on different numbers of (variable) decoding iterations $t$.

While highly non-convex, the objective is (sub)differentiable when considering the STE definition of the gradient (Bengio et al., ; Yin et al., ) and thus optimizable via classical first-order methods.
Since $H$ is binary, only changes in the sign of $\Omega$ are relevant for the optimization, so most gradient descent iterations remain ineffective in reducing the objective using conventional small learning-rate regimes.
Thus, given the gradient $\nabla_{\Omega}\mathcal{L}$ computed on sufficient statistics, we propose a line-search procedure capable of finding the optimal step size.

### Binary Line-Search

Conventional first-order optimization methods with small learning rate regimes have two major drawbacks with binarization (Rastegari et al., ; Courbariaux et al., ). First, they are generally slow since only gradient steps modifying the sign of the binarized tensor induce a modification of the loss. Second, they have difficulties in converging to local minima because of oscillating behavior around zero.

In general, efficient line search methods (Nocedal & Wright, ) assume local convexity or a smooth objective (Wolf, ) or, alternatively, apply exhaustive search on a given interval. Since this is not our case, we propose a novel efficient *grid*-search approach optimized to our binary programming setting.
While classical grid search methods look for the optimal step size on handcrafted predefined sample points, in our binary setting we can search only for the step sizes inducing a flip of the sign in $\Omega$, provably limiting the maximum number of *relevant* grid samples to $n(n-k)$.
Thus, the line-search problem is now given by

$$ $\displaystyle\lambda^{*}=\operatorname*{arg\,min}_{\lambda\in\mathcal{I}_{ \Omega}}\mathcal{L}(\Omega-\lambda\nabla_{\Omega}\mathcal{L}),\ \ \ \ \ \ \ \mathcal{I}_{\Omega}=\{s_{i}=\frac{(\Omega)_{i}}{(\nabla_{\Omega}\mathcal{L})_ {i}}|s_{i}>0\}\,,$ (9) $$

which corresponds to the (parallelizable) objective evaluation on the obtained grid.
The same formulation can support other more practical line-search objectives instead of the cross-entropy loss $\mathcal{L}$, such as BER or Frame Error Rate (FER).

Figure: Algorithm 2 Belief Propagation Codes Optimization

### Training

The optimization parameters are the following: the initial $H$ (i.e., initial $\Omega$), the maximum number of optimization steps (if convergence is not reached), the number and quality of the data samples, the grid search length, and the number of BP iterations.

We assume that an initial $H$ is given by the user as the code to be improved. The number of optimization steps is set to 20 iterations. The training noise is sampled randomly per batch in the $\{3,\dots,7\}$ normalized SNR (i.e. $E_{b}/N_{0}$) range but can be modified according to the noise setting of interest. The number of data samples per optimization iteration is set to 4.9M for every code as sufficient gradient estimation, and the data samples are required to have non-zero syndrome. Because of computational constraints, the number of BP iterations during training is fixed and set to 5, while other ranges or values of interest can be used instead.
For faster optimization, the grid search is heuristically restricted to the first 50 smallest step sizes as the optimal step size is generally in the vicinity of the working point (Appendix C) . Training and experiments are performed on $8\times 12\mathrm{GB}$ GeForce RTX 2080 Ti GPUs and require 2.96 minutes on average per optimization step.

The full training algorithm (pseudocode) is given in Algorithm 2.
Given an initial parity check matrix, the algorithm optimizes $H$ iteratively upon convergence.
At each iteration, after computing the gradient on sufficiently large statistics (line 7), the line search procedure (line 10) searches for the optimal step size among those that flip the values of $H$ (line 9).

## 5 Experiments

**Table 1: A comparison of the negative natural logarithm of Bit Error Rate (BER) for several normalized SNR values of our method with classical codes. Higher is better. BP results are provided for 5 iterations in the first row and 15 in the second row. The best results are in bold. PEG$X$ means the degree of each node is of $X\%$ under the Progressive Edge Growth construction.**
| Channel | AWGN | Fading | Bursting |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Method | BP | Our | BP | Our | BP | Our |  |  |  |  |  |  |  |  |  |  |  |  |
| $E_{b}/N_{0}$ | 4 | 5 | 6 | 4 | 5 | 6 | 4 | 5 | 6 | 4 | 5 | 6 | 4 | 5 | 6 | 4 | 5 | 6 |
| BCH(63,45) | 4.06<br>4.21 | 4.91<br>5.24 | 6.04<br>6.59 | 5.44<br>5.70 | 6.93<br>7.35 | 8.60<br>9.16 | 3.09<br>3.13 | 3.46<br>3.55 | 3.90<br>4.04 | 3.96<br>4.10 | 4.58<br>4.80 | 5.27<br>5.56 | 3.60<br>3.67 | 4.32<br>4.52 | 5.19<br>5.59 | 4.05<br>4.21 | 5.07<br>5.40 | 6.27<br>6.85 |
| CCSDS(128,64) | 6.46<br>7.32 | 9.61<br>10.83 | 13.99<br>15.43 | 7.34<br>8.61 | 10.48<br>12.26 | 14.37<br>16.00 | 5.72<br>6.43 | 7.42<br>8.29 | 9.47<br>10.28 | 6.73<br>8.05 | 8.45<br>10.07 | 10.45<br>12.37 | 5.29<br>5.98 | 7.81<br>8.85 | 11.25<br>12.53 | 6.23<br>7.39 | 8.80<br>10.43 | 11.90<br>13.28 |
| LDPC(121,60) | 4.81<br>5.31 | 7.17<br>7.96 | 10.75<br>11.85 | 7.70<br>8.86 | 10.87<br>11.91 | 14.25<br>14.41 | 4.10<br>4.42 | 5.23<br>5.61 | 6.68<br>7.04 | 6.68<br>7.71 | 8.47<br>9.67 | 10.50<br>11.76 | 3.97<br>4.31 | 5.75<br>6.37 | 8.40<br>9.25 | 6.23<br>7.26 | 8.89<br>10.03 | 11.98<br>12.88 |
| LDPC(121,80) | 6.59<br>7.35 | 9.68<br>10.94 | 13.43<br>15.46 | 7.77<br>8.75 | 11.21<br>12.45 | 15.06<br>15.67 | 4.60<br>4.97 | 5.80<br>6.29 | 7.22<br>7.82 | 5.55<br>6.25 | 6.90<br>7.80 | 8.36<br>9.47 | 5.30<br>5.81 | 7.60<br>8.50 | 10.66<br>12.15 | 6.23<br>6.99 | 8.87<br>10.09 | 12.19<br>13.74 |
| LDPC(128,64) | 3.66<br>4.00 | 4.65<br>5.16 | 5.80<br>6.42 | 5.54<br>6.56 | 7.37<br>8.70 | 9.44<br>10.81 | 3.22<br>3.51 | 3.80<br>4.18 | 4.44<br>4.84 | 4.86<br>5.64 | 5.94<br>6.85 | 7.15<br>8.14 | 3.23<br>3.48 | 4.08<br>4.51 | 5.09<br>5.66 | 3.72<br>4.13 | 5.00<br>5.72 | 6.54<br>7.66 |
| LDPC(32,16) | 4.36<br>4.64 | 5.59<br>6.07 | 7.18<br>7.94 | 5.48<br>5.76 | 7.02<br>7.44 | 8.92<br>9.41 | 4.03<br>4.29 | 4.70<br>5.06 | 5.47<br>5.90 | 5.26<br>5.43 | 6.02<br>6.23 | 6.82<br>6.97 | 3.88<br>4.09 | 4.89<br>5.26 | 6.18<br>6.76 | 4.77<br>5.01 | 6.02<br>6.35 | 7.52<br>7.96 |
| LDPC(96,48) | 6.73<br>7.50 | 9.48<br>10.61 | 12.98<br>14.26 | 7.22<br>8.29 | 9.96<br>11.12 | 13.37<br>14.06 | 3.83<br>4.17 | 4.57<br>4.94 | 5.35<br>5.73 | 5.37<br>6.14 | 6.51<br>7.38 | 7.71<br>8.65 | 5.68<br>6.33 | 7.94<br>8.91 | 10.90<br>11.99 | 5.90<br>6.71 | 8.19<br>9.28 | 10.91<br>11.75 |
| LTE(132,40) | 2.94<br>3.37 | 3.32<br>3.79 | 3.57<br>4.09 | 3.25<br>3.93 | 3.71<br>4.49 | 4.04<br>4.89 | 3.17<br>3.60 | 3.45<br>3.82 | 3.67<br>4.01 | 4.49<br>5.32 | 4.99<br>5.81 | 5.47<br>6.31 | 2.75<br>3.17 | 3.17<br>3.62 | 3.47<br>3.96 | 2.99<br>3.53 | 3.44<br>4.03 | 3.78<br>4.41 |
| MACKAY(96,48) | 6.75<br>7.59 | 9.45<br>10.52 | 12.85<br>14.09 | 7.03<br>7.99 | 9.63<br>10.97 | 12.78<br>14.05 | 6.28<br>7.04 | 7.86<br>8.76 | 9.55<br>10.64 | 6.53<br>7.47 | 8.06<br>9.32 | 9.77<br>11.19 | 5.72<br>6.39 | 7.97<br>8.90 | 10.81<br>11.91 | 5.95<br>6.82 | 8.23<br>9.41 | 10.91<br>12.71 |
| POLAR(128,86) | 3.76<br>4.02 | 4.17<br>4.67 | 4.58<br>5.38 | 4.83<br>5.37 | 5.87<br>6.88 | 6.58<br>8.10 | 3.15<br>3.28 | 3.53<br>3.73 | 3.91<br>4.18 | 3.64<br>3.92 | 4.28<br>4.70 | 4.94<br>5.52 | 3.48<br>3.65 | 3.96<br>4.31 | 4.37<br>4.97 | 3.69<br>3.87 | 4.51<br>4.91 | 5.18<br>5.91 |
| RS(60,52) | 4.41<br>4.54 | 5.32<br>5.52 | 6.41<br>6.64 | 5.02<br>5.07 | 6.38<br>6.47 | 7.99<br>8.12 | 3.11<br>3.13 | 3.41<br>3.43 | 3.77<br>3.81 | 3.37<br>3.38 | 3.73<br>3.75 | 4.12<br>4.15 | 3.85<br>3.91 | 4.58<br>4.72 | 5.44<br>5.67 | 4.17<br>4.21 | 5.18<br>5.27 | 6.40<br>6.56 |
| LDPC PEG2(64,32) | 4.38<br>4.38 | 5.12<br>5.13 | 6.04<br>6.04 | 4.45<br>4.44 | 5.19<br>5.19 | 6.10<br>6.10 | 4.08<br>4.08 | 4.44<br>4.44 | 4.81<br>4.81 | 4.10<br>4.10 | 4.46<br>4.47 | 4.85<br>4.85 | 4.07<br>4.06 | 4.69<br>4.69 | 5.43<br>5.43 | 4.07<br>4.06 | 4.70<br>4.69 | 5.43<br>5.44 |
| LDPC PEG5(64,32) | 6.02<br>6.63 | 8.20<br>9.06 | 10.95<br>12.30 | 6.53<br>7.13 | 8.73<br>9.48 | 11.56<br>12.20 | 5.63<br>6.19 | 6.86<br>7.52 | 8.31<br>9.02 | 6.22<br>6.96 | 7.48<br>8.34 | 8.82<br>9.85 | 5.18<br>5.68 | 6.97<br>7.75 | 9.34<br>10.19 | 5.59<br>6.12 | 7.41<br>8.06 | 9.51<br>10.13 |
| LDPC PEG10(64,32) | 3.98<br>4.27 | 5.17<br>5.77 | 6.70<br>7.67 | 5.56<br>6.25 | 7.22<br>8.28 | 9.13<br>10.59 | 3.52<br>3.71 | 4.18<br>4.47 | 4.95<br>5.30 | 5.02<br>5.60 | 6.00<br>6.72 | 7.11<br>7.90 | 3.48<br>3.67 | 4.47<br>4.90 | 5.75<br>6.46 | 4.26<br>4.73 | 5.50<br>6.22 | 7.01<br>8.01 |

We evaluate our framework on five classes of linear codes: various Low-Density Parity Check (LDPC) codes (Gallager, ; Abu-Surra et al., ), Polar codes (Arikan, ), Reed Solomon codes (Reed & Solomon, ), Bose–Chaudhuri–Hocquenghem (BCH) codes (Bose & Ray-Chaudhuri, ) and random codes.
All the parity check matrices are taken from (Helmling et al., ) except the LDPC codes created using the popular Progressive Edge Growth framework (Hu et al., ; ).

We consider three types of channel noise under BPSK modulation. We first test our framework with the canonical AWGN channel given as $y=c_{s}+\varepsilon$ with $\varepsilon\sim\mathcal{N}(0,\sigma I_{n})$.
We also consider the Rayleigh fading channel, where $y=h\odot c_{s}+\varepsilon$, with $h$ the iid Rayleigh distributed fading vector with coefficient $1$ and $\varepsilon$ the regular AWGN noise, where we assume ideal channel state information. Finally, we consider the AWGN channel with Gaussian mixture channel (also referred to as bursty noise) simulating wireless channel interference as $y=c_{s}+\varepsilon+\zeta$ with $\varepsilon$ the AWGN and $\zeta_{i}\sim\mathcal{N}(0,\sqrt{2}\sigma)$ with probability $\rho=0.1$ and $\zeta_{i}=0$ with probability $1-\rho$.

The results are reported as negative natural logarithm bit error rates (BER) for three different normalized SNR values ($E_{b}/N_{0}$), following the conventional testing benchmark, e.g., (Nachmani & Wolf, ; Choukroun & Wolf, ). BP-based results are obtained after $\ell=5$ BP iterations in the first row and $\ell=15$ in the second row of the results tables. During testing, at least $10^{5}$ random codewords are decoded, to obtain at least $50$ frames with errors at each SNR value.
For this section, we performed a small hyperparameter search as reported in Appendix A, where the final code is selected to have the lowest average BER on the SNR test range.

The results are provided in Table 1, where *our* method means BP applied on the learned code initialized by the given classical code.
We also provide in Appendix B the same table with a broader SNR range ($E_{b}/N_{0}\in\{3,\dots,7\})$.
We provide the improvement statistics (i.e., mean, std, min, max) in dB on all the sparse codes in Figure 2 and we extend the analysis to all the codes in Appendix F.
For completeness, we provide in Appendix H a comparison with the genetic algorithm of Elkelesh et al. () where our method demonstrates much better performance while being faster by orders of magnitude.

Evidently, our method improves by large margins all code families on the three different channel noise scenarios and with both numbers of decoding iterations, demonstrating the capacity of the framework to provide improved codes on multiple settings of interest.

Figure: Figure 2: Statistics of improvement in dB for the (a) AWGN, (b) fading, and (c) bursting channel on the *sparse codes* only. We provide the mean and standard deviation as well as the minimum and maximum improvements.
Refer to caption: x1.png

## 6 Analysis

### Initialization and Random Codes

We provide in Figure 3 the performance of the proposed method on random codes initialized with different sparsity rates. The parity check matrix is initialized in a systematic form $H=[I_{n-k},P]$ for full rank initialization, where $P\sim\text{Bern}^{(n-k)\times k}(p)$.
We can observe that the framework can greatly improve the performance of the original random code. Most importantly, we can observe that different initializations provide convergence to different local optima and that better initialization generally induces convergence to a better minimum.
Performance on other code lengths is provided in Appendix G.
Finally, good initialization (i.e., (large) well-performing sparse codes under BP decoding) requires perturbation at initialization or during training (c.f., Appendix A) in order to get extracted from local minima.

Figure: Figure 3: Performance of the method on random codes under different sparsity rate initialization $p$.
Refer to caption: x7.png

### Constrained Codes

In Figure 4 we provide the performance of the method on constrained systematic random codes as described in the previous paragraph, while here, we constrain them to maintain their systematic form during the optimization, i.e., only the parity matrix elements of $P$ are optimized (via $\Omega$). The optimization is performed by backpropagating over the $P$ tensor only, similarly to having a hard structure constraint on the identity part of $H$.
While maintaining a structure of interest, we can observe this regularization can further improve the convergence quality (e.g., $p=0.1$)
compared to the unconstrained setting of Figure 3.
Performance on other code lengths is provided in Appendix G.

Figure: Figure 4: Performance of the method on constrained systematic random codes under different sparsity rate initialization $p$ on the AWGN channel.
Refer to caption: x11.png

In Figure 6 we present the sparsification of the codes created by the framework.
Here, $\Delta=100({S_{b}-S_{o}})/{S_{b}}$ represents the sparsity ratio, with $S_{b}$ and $S_{o}$ being the sparsity of the baseline code and our code, respectively.
We can observe that optimization always provides sparser code.
Nevertheless, we also observed that the optimization does not modify the girth of the code.

In Figure 6 we present the performance of the method on random codes with sparsity constraint, i.e., $\mathcal{R}(H)=\lambda\|H\|_{1}$, with $\lambda\in\mathbb{R}_{+}$.
We can observe that adding a sparsity constraint is generally not profitable, since the optimization over BP already induces sparse codes.

Figure: Figure 5: Sparsity reduction of the proposed codes.
Refer to caption: extracted/5916351/Ablations/SPARSITY.png

### Learned Codes Visualization

We depict in Figure 7 the learned codes via the visualization of the parity-check matrices.
We can observe that for low-density codes the modifications remain small, since the code is already near local optimum, while for denser codes the change can be substantial. Also, the optimized codes tend to be more sparse than the original.

Figure: Figure 7: Visualization of the original (first row) and the learned parity check matrices (second row) for (a) LDPC(32,16), (b) LDPC(128,64), (c) BCH(63,45) and (d) Random(64,32,$p=0.5$). "PCM iter X" denotes the final iteration Parity Check Matrix of the optimization.
Refer to caption: x17.png

We provide in Appendix C visualizations of the line search optimization, demonstrating the high non-convexity and the proximity of the optimum to the current estimate.
We provide in Appendix D statistics on convergence rates and typical convergence curves demonstrating the fast and monotonic convergence.
Finally, we provide in Appendix E the performance of the learned code on the efficient Min-Sum approximation of the BP algorithm and show that the learned code outperforms the baseline codes over the Min-Sum framework as well.

## 7 Conclusions

We present a novel gradient-based optimization method of binary linear block codes for the Belief Propagation algorithm.
The proposed framework enables the differentiable optimization of the factor graph via weighted tensor representation.
The optimization is efficiently carried out via a tailor-made grid search procedure that is aware of the binary constraint of the optimization problem.

A common criticism of ML-based ECC is that the neural decoder cannot be deployed directly without the application of massive deep-learning acceleration methods. Here, we show that the code can be designed efficiently in a data-driven fashion on differentiable formulations of classical decoders. The optimization of codes may open the door to the establishment of new industry standards and the creation of new families of codes.

## Appendix A Hyper-Parameter Tuning

Under the problem’s stochastic optimization, we provide here the different modifications used to obtain better performance.
The first set of training/optimization hyperparameters is the $E_{b}/N_{0}$ range defined as $(u,7)$ with $u\in\{3,4,5\}$.
The second set of hyperparameters is the data sampling, where we experimented with random data (i.e., classical setting) and data with non-zero syndromes only.
Finally, for better backpropagation, we also experimented with a soft approximation $\tilde{H}$ of the binary $H$ during the optimization, defined as

$$ $\tilde{H}_{ij}=\left\{\begin{array}[]{ll}(-1)^{z}\epsilon,\ \ \ \ \ \ \ if\ \ \ H_{ij}=0\\ 1,\ \ \ \ \ \ \ else\end{array}\right.$ $$

where $z\sim Bern(0.5)$ and $\epsilon$ is a small scalar ($10^{-7}$ in our experiments).
We note we only used a size 15 random subset of all the possible permutations of the hyperparameters mentioned above.

## Appendix B More SNR results

We provide results on a larger range of SNRs in Table 2.

**Table 2: A comparison of the negative natural logarithm of Bit Error Rate (BER) for several normalized SNR values of our method with classical codes. Higher is better. BP results are provided for 5 iterations in the first row and 15 in the second row. The best results are in bold.**
| Channel | AWGN | Fading | Bursting |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Method | BP | Our | BP | Our | BP | Our |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| $E_{b}/N_{0}$ | 3 | 4 | 5 | 6 | 7 | 3 | 4 | 5 | 6 | 7 | 3 | 4 | 5 | 6 | 7 | 3 | 4 | 5 | 6 | 7 | 3 | 4 | 5 | 6 | 7 | 3 | 4 | 5 | 6 | 7 |
| BCH(63,45) | 3.35<br>3.40 | 4.06<br>4.21 | 4.91<br>5.24 | 6.04<br>6.59 | 7.47<br>8.35 | 4.23<br>4.36 | 5.44<br>5.70 | 6.93<br>7.35 | 8.60<br>9.16 | 10.27<br>11.10 | 2.77<br>2.79 | 3.09<br>3.13 | 3.46<br>3.55 | 3.90<br>4.04 | 4.37<br>4.61 | 3.42<br>3.50 | 3.96<br>4.10 | 4.58<br>4.80 | 5.27<br>5.56 | 5.99<br>6.36 | 3.00<br>3.02 | 3.60<br>3.67 | 4.32<br>4.52 | 5.19<br>5.59 | 6.25<br>6.93 | 3.24<br>3.31 | 4.05<br>4.21 | 5.07<br>5.40 | 6.27<br>6.85 | 7.67<br>8.55 |
| CCSDS(128,64) | 4.32<br>4.82 | 6.46<br>7.32 | 9.61<br>10.83 | 13.99<br>15.43 | 18.27<br>18.51 | 4.99<br>5.80 | 7.34<br>8.61 | 10.48<br>12.26 | 14.37<br>16.00 | 17.38<br>18.15 | 4.37<br>4.89 | 5.72<br>6.43 | 7.42<br>8.29 | 9.47<br>10.28 | 11.84<br>12.88 | 5.22<br>6.22 | 6.73<br>8.05 | 8.45<br>10.07 | 10.45<br>12.37 | 12.36<br>14.87 | 3.62<br>3.97 | 5.29<br>5.98 | 7.81<br>8.85 | 11.25<br>12.53 | 15.59<br>17.10 | 4.32<br>5.05 | 6.23<br>7.39 | 8.80<br>10.43 | 11.90<br>13.28 | 14.76<br>15.56 |
| LDPC(121,60) | 3.33<br>3.53 | 4.81<br>5.31 | 7.17<br>7.96 | 10.75<br>11.85 | 15.69<br>17.01 | 5.29<br>6.18 | 7.70<br>8.86 | 10.87<br>11.91 | 14.25<br>14.41 | 16.82<br>17.04 | 3.24<br>3.44 | 4.10<br>4.42 | 5.23<br>5.61 | 6.68<br>7.04 | 8.56<br>8.77 | 5.18<br>6.04 | 6.68<br>7.71 | 8.47<br>9.67 | 10.50<br>11.76 | 12.31<br>14.21 | 2.87<br>2.98 | 3.97<br>4.31 | 5.75<br>6.37 | 8.40<br>9.25 | 12.16<br>13.10 | 4.32<br>5.02 | 6.23<br>7.26 | 8.89<br>10.03 | 11.98<br>12.88 | 14.91<br>15.14 |
| LDPC(121,80) | 4.50<br>4.85 | 6.59<br>7.35 | 9.68<br>10.94 | 13.43<br>15.46 | 18.51<br>19.61 | 5.28<br>5.85 | 7.77<br>8.75 | 11.21<br>12.45 | 15.06<br>15.67 | 18.40<br>18.30 | 3.67<br>3.89 | 4.60<br>4.97 | 5.80<br>6.29 | 7.22<br>7.82 | 8.95<br>9.58 | 4.42<br>4.89 | 5.55<br>6.25 | 6.90<br>7.80 | 8.36<br>9.47 | 10.00<br>11.21 | 3.74<br>3.94 | 5.30<br>5.81 | 7.60<br>8.50 | 10.66<br>12.15 | 14.88<br>16.45 | 4.32<br>4.73 | 6.23<br>6.99 | 8.87<br>10.09 | 12.19<br>13.74 | 16.31<br>17.55 |
| LDPC(128,64) | 2.88<br>3.04 | 3.66<br>4.00 | 4.65<br>5.16 | 5.80<br>6.42 | 7.03<br>7.77 | 4.07<br>4.71 | 5.54<br>6.56 | 7.37<br>8.70 | 9.44<br>10.81 | 11.71<br>12.92 | 2.73<br>2.90 | 3.22<br>3.51 | 3.80<br>4.18 | 4.44<br>4.84 | 5.14<br>5.54 | 3.95<br>4.55 | 4.86<br>5.64 | 5.94<br>6.85 | 7.15<br>8.14 | 8.38<br>9.59 | 2.58<br>2.68 | 3.23<br>3.48 | 4.08<br>4.51 | 5.09<br>5.66 | 6.21<br>6.88 | 2.80<br>2.97 | 3.72<br>4.13 | 5.00<br>5.72 | 6.54<br>7.66 | 8.30<br>9.86 |
| LDPC(32,16) | 3.45<br>3.59 | 4.36<br>4.64 | 5.59<br>6.07 | 7.18<br>7.94 | 9.19<br>10.23 | 4.29<br>4.47 | 5.48<br>5.76 | 7.02<br>7.44 | 8.92<br>9.41 | 11.23<br>12.03 | 3.44<br>3.62 | 4.03<br>4.29 | 4.70<br>5.06 | 5.47<br>5.90 | 6.31<br>6.83 | 4.53<br>4.67 | 5.26<br>5.43 | 6.02<br>6.23 | 6.82<br>6.97 | 7.61<br>7.81 | 3.10<br>3.21 | 3.88<br>4.09 | 4.89<br>5.26 | 6.18<br>6.76 | 7.82<br>8.58 | 3.78<br>3.93 | 4.77<br>5.01 | 6.02<br>6.35 | 7.52<br>7.96 | 9.22<br>9.72 |
| LDPC(96,48) | 4.72<br>5.20 | 6.73<br>7.50 | 9.48<br>10.61 | 12.98<br>14.26 | 16.87<br>17.80 | 5.17<br>5.85 | 7.22<br>8.29 | 9.96<br>11.12 | 13.37<br>14.06 | 16.45<br>17.19 | 3.19<br>3.44 | 3.83<br>4.17 | 4.57<br>4.94 | 5.35<br>5.73 | 6.17<br>6.58 | 4.38<br>4.99 | 5.37<br>6.14 | 6.51<br>7.38 | 7.71<br>8.65 | 8.94<br>9.77 | 4.03<br>4.40 | 5.68<br>6.33 | 7.94<br>8.91 | 10.90<br>11.99 | 14.27<br>15.55 | 4.23<br>4.71 | 5.90<br>6.71 | 8.19<br>9.28 | 10.91<br>11.75 | 13.61<br>14.06 |
| LTE(132,40) | 2.49<br>2.85 | 2.94<br>3.37 | 3.32<br>3.79 | 3.57<br>4.09 | 3.81<br>4.32 | 2.72<br>3.26 | 3.25<br>3.93 | 3.71<br>4.49 | 4.04<br>4.89 | 4.36<br>5.22 | 2.82<br>3.29 | 3.17<br>3.60 | 3.45<br>3.82 | 3.67<br>4.01 | 3.89<br>4.21 | 3.97<br>4.78 | 4.49<br>5.32 | 4.99<br>5.81 | 5.47<br>6.31 | 5.96<br>6.84 | 2.30<br>2.63 | 2.75<br>3.17 | 3.17<br>3.62 | 3.47<br>3.96 | 3.70<br>4.19 | 2.48<br>2.92 | 2.99<br>3.53 | 3.44<br>4.03 | 3.78<br>4.41 | 4.05<br>4.70 |
| MACKAY(96,48) | 4.77<br>5.28 | 6.75<br>7.59 | 9.45<br>10.52 | 12.85<br>14.09 | 16.37<br>17.43 | 5.03<br>5.63 | 7.03<br>7.99 | 9.63<br>10.97 | 12.78<br>14.05 | 16.11<br>17.49 | 4.98<br>5.55 | 6.28<br>7.04 | 7.86<br>8.76 | 9.55<br>10.64 | 11.30<br>12.58 | 5.18<br>5.93 | 6.53<br>7.47 | 8.06<br>9.32 | 9.77<br>11.19 | 11.58<br>13.14 | 4.08<br>4.47 | 5.72<br>6.39 | 7.97<br>8.90 | 10.81<br>11.91 | 13.92<br>15.23 | 4.28<br>4.79 | 5.95<br>6.82 | 8.23<br>9.41 | 10.91<br>12.71 | 14.02<br>15.81 |
| POLAR(128,86) | 3.25<br>3.36 | 3.76<br>4.02 | 4.17<br>4.67 | 4.58<br>5.38 | 5.12<br>6.19 | 3.72<br>3.96 | 4.83<br>5.37 | 5.87<br>6.88 | 6.58<br>8.10 | 7.21<br>9.00 | 2.80<br>2.87 | 3.15<br>3.28 | 3.53<br>3.73 | 3.91<br>4.18 | 4.26<br>4.60 | 3.10<br>3.26 | 3.64<br>3.92 | 4.28<br>4.70 | 4.94<br>5.52 | 5.58<br>6.30 | 2.95<br>3.02 | 3.48<br>3.65 | 3.96<br>4.31 | 4.37<br>4.97 | 4.78<br>5.66 | 2.96<br>3.03 | 3.69<br>3.87 | 4.51<br>4.91 | 5.18<br>5.91 | 5.73<br>6.88 |
| RS(60,52) | 3.65<br>3.70 | 4.41<br>4.54 | 5.32<br>5.52 | 6.41<br>6.64 | 7.80<br>8.04 | 3.98<br>4.00 | 5.02<br>5.07 | 6.38<br>6.47 | 7.99<br>8.12 | 9.73<br>9.80 | 2.86<br>2.87 | 3.11<br>3.13 | 3.41<br>3.43 | 3.77<br>3.81 | 4.16<br>4.24 | 3.05<br>3.06 | 3.37<br>3.38 | 3.73<br>3.75 | 4.12<br>4.15 | 4.53<br>4.56 | 3.26<br>3.27 | 3.85<br>3.91 | 4.58<br>4.72 | 5.44<br>5.67 | 6.43<br>6.78 | 3.42<br>3.42 | 4.17<br>4.21 | 5.18<br>5.27 | 6.40<br>6.56 | 7.75<br>8.01 |
| PGE2(64,32) | 3.78<br>3.78 | 4.38<br>4.38 | 5.12<br>5.13 | 6.04<br>6.04 | 7.17<br>7.16 | 3.84<br>3.84 | 4.45<br>4.44 | 5.19<br>5.19 | 6.10<br>6.10 | 7.22<br>7.23 | 3.74<br>3.74 | 4.08<br>4.08 | 4.44<br>4.44 | 4.81<br>4.81 | 5.20<br>5.20 | 3.75<br>3.75 | 4.10<br>4.10 | 4.46<br>4.47 | 4.85<br>4.85 | 5.24<br>5.24 | 3.54<br>3.54 | 4.07<br>4.06 | 4.69<br>4.69 | 5.43<br>5.43 | 6.29<br>6.29 | 3.54<br>3.54 | 4.07<br>4.06 | 4.70<br>4.69 | 5.43<br>5.44 | 6.30<br>6.30 |
| PGE5(64,32) | 4.41<br>4.78 | 6.02<br>6.63 | 8.20<br>9.06 | 10.95<br>12.30 | 14.40<br>15.75 | 4.82<br>5.26 | 6.53<br>7.13 | 8.73<br>9.48 | 11.56<br>12.20 | 14.41<br>14.90 | 4.56<br>4.98 | 5.63<br>6.19 | 6.86<br>7.52 | 8.31<br>9.02 | 9.78<br>10.76 | 5.09<br>5.67 | 6.22<br>6.96 | 7.48<br>8.34 | 8.82<br>9.85 | 10.16<br>11.24 | 3.84<br>4.13 | 5.18<br>5.68 | 6.97<br>7.75 | 9.34<br>10.19 | 12.25<br>13.40 | 4.19<br>4.55 | 5.59<br>6.12 | 7.41<br>8.06 | 9.51<br>10.13 | 11.84<br>12.27 |
| PGE10(64,32) | 3.08<br>3.20 | 3.98<br>4.27 | 5.17<br>5.77 | 6.70<br>7.67 | 8.49<br>9.72 | 4.21<br>4.62 | 5.56<br>6.25 | 7.22<br>8.28 | 9.13<br>10.59 | 11.11<br>12.84 | 2.96<br>3.08 | 3.52<br>3.71 | 4.18<br>4.47 | 4.95<br>5.30 | 5.81<br>6.24 | 4.16<br>4.60 | 5.02<br>5.60 | 6.00<br>6.72 | 7.11<br>7.90 | 8.33<br>9.24 | 2.75<br>2.82 | 3.48<br>3.67 | 4.47<br>4.90 | 5.75<br>6.46 | 7.28<br>8.26 | 3.30<br>3.57 | 4.26<br>4.73 | 5.50<br>6.22 | 7.01<br>8.01 | 8.80<br>10.06 |

## Appendix C Line Search Optimization

In Figure 8 we provide visualizations of the line search procedure.
We provide BER with respect to the step size $\lambda_{i}$ indexed by $i$ ($\lambda_{0}\equiv 0$).
We can observe the high non-convexity of the objective, with the presence of several local minima. We can also notice the proximity of the optimum to the current parity-check estimate (i.e., $\lambda_{0}$).

Figure: Figure 8: BER in function of the step size index $i$ on AWGN channel. (a) Averaged BER over the optimization iterations for 4 codes. (b,c,d) BER per optimization iteration for the first 5 optimization iterations and the first 10 indices for three different codes. Here $\lambda_{0}=0$ denotes the original BER.
Refer to caption: x25.png

## Appendix D Convergence Rate

In Figure 9 we provide statistics on the number of optimization iterations for convergence (a). We also provide (b,c,d) typical convergence. We can observe that the framework typically converges within a few iterations and that the loss decreases monotonically.

Figure: Figure 9: (a) Histogram of the number of required iterations until convergence. (b) Convergence rate of the Frame Error Rate for three codes on (b) AWGN, (c) fading, and (d) bursting channel. We selected the three codes with the largest number of iterations. The FER is averaged over all the tested $E_{b}/N_{0}=\{3,\dots 7\}$ range.
Refer to caption: x29.png

## Appendix E Impact on other BP Variants

In Table 3 we provide the performance of the learned code on the more efficient Min-Sum approximation of the Sum-Product algorithm. We can observe that the codes learned with BP consistently outperform the performance of the Min-Sum approximation as well. For some codes, the training range may need to be adjusted.
We note our method can be applied to neural BP decoders as well.
The direct optimization over BP approximations and augmentations is left for future work.

**Table 3: A comparison of the negative natural logarithm of Bit Error Rate (BER) for five normalized SNR values of our method applied on the Min-Sum BP algorithm. $NE=$ no errors spotted under the testing limits.**
| BP Method | Sum-Product | Min-Sum |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Method | Baseline | Our | Baseline | Our |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| $E_{b}/N_{0}$ | 3 | 4 | 5 | 6 | 7 | 3 | 4 | 5 | 6 | 7 | 3 | 4 | 5 | 6 | 7 | 3 | 4 | 5 | 6 | 7 |
| BCH(63,45) | 3.35<br>3.40 | 4.06<br>4.22 | 4.92<br>5.24 | 5.98<br>6.60 | 7.39<br>8.33 | 3.48<br>3.57 | 4.30<br>4.49 | 5.29<br>5.69 | 6.51<br>7.17 | 8.12<br>9.17 | 3.04<br>3.22 | 3.79<br>4.09 | 4.89<br>5.41 | 6.33<br>7.06 | 8.13<br>9.14 | 3.21<br>3.40 | 4.09<br>4.44 | 5.32<br>5.89 | 6.84<br>7.60 | 8.65<br>10.00 |
| CCSDS(128,64) | 4.32<br>4.82 | 6.47<br>7.30 | 9.62<br>10.70 | 13.80<br>15.50 | 18.40<br>17.90 | 4.44<br>4.99 | 6.66<br>7.57 | 9.73<br>11.00 | 13.60<br>15.60 | 18.30<br>$NE$ | 4.21<br>4.76 | 6.62<br>7.66 | 10.40<br>12.20 | 15.10<br>17.70 | 19.40<br>$NE$ | 4.35<br>4.97 | 6.82<br>8.03 | 10.50<br>12.30 | 15.00<br>17.40 | 21.00<br>$NE$ |
| LDPC(32,16) | 3.46<br>3.61 | 4.39<br>4.66 | 5.60<br>6.07 | 7.20<br>7.87 | 9.23<br>10.30 | 3.62<br>3.80 | 4.59<br>4.91 | 5.83<br>6.36 | 7.45<br>8.16 | 9.52<br>10.70 | 3.36<br>3.55 | 4.38<br>4.69 | 5.75<br>6.21 | 7.65<br>8.21 | 10.10<br>10.90 | 3.53<br>3.74 | 4.61<br>4.93 | 6.01<br>6.50 | 7.92<br>8.44 | 10.10<br>11.10 |
| LDPC(96,48) | 4.70<br>5.20 | 6.73<br>7.55 | 9.52<br>10.70 | 13.20<br>14.40 | 17.30<br>18.50 | 5.01<br>5.70 | 7.11<br>8.13 | 9.92<br>11.30 | 13.50<br>14.70 | 16.90<br>17.40 | 4.71<br>5.23 | 6.96<br>7.89 | 9.95<br>11.50 | 14.20<br>15.10 | 18.30<br>19.10 | 4.98<br>5.68 | 7.16<br>8.32 | 10.10<br>12.00 | 14.00<br>14.80 | 15.80<br>15.80 |

## Appendix F Improvement Statistics on all the Codes

We provide in Figure 10 the statistics of improvement on all the codes presented in Table 2.

Figure: Figure 10: Statistics of improvement in dB for the (a) AWGN, (b) fading, and (c) bursting channel on all the codes from Table 2. We provide the mean and standard deviation as well as the minimum and maximum improvements.
Refer to caption: x33.png

## Appendix G More Random Codes

We provide in Figure 11 the performance of the proposed method on random codes initialized with different sparsity rates on different lengths.
We also provide in Figure 12 the performance of the proposed method on constrained systematic random codes initialized with different sparsity rates on different lengths.

Figure: Figure 11: Performance of the method on random codes under different sparsity rate initialization $p$.
Refer to caption: x39.png

Figure: Figure 12: Performance of the method on constrained systematic random codes under different sparsity rate initialization $p$ on the AWGN channel.
Refer to caption: x47.png

## Appendix H Comparison with Genetic Algorithm

We provide in table 4 a comparison with the genetic algorithm of Elkelesh et al. ().
We note that the method requires 230 offspring/code evaluations per iteration, with 300 iterations (Fig. 7 in (Elkelesh et al., )) or even an infinite loop (cf. the provided MATLAB code).
Our algorithm is tested on 50 line-search steps as described in in the paper on 2 to 25 iterations (cf. App. D), which means that Elkelesh et al. () requires approximately 25 to 313 times more computations than our proposed method.
The performance presented are for 75 and 150 iterations of the algorithm, representing around 70 and 140 times slower performance than our approach, respectively, while they remain below our performance.
We note here, as described in the paper, that combining the methods by allowing the perturbation of the parity-check matrix at a local minima may allow the discovery of other better local optimum.

**Table 4: A comparison of the negative natural logarithm of Bit Error Rate (BER) for several normalized SNR values of our method with classical codes. Higher is better. BP results are provided for 5 iterations in the first row and 15 in the second row. The best results are in bold. The training range is defined as $E_{b}/N_{0}=\{5\}$. GA denotes the genetic algorithm of Elkelesh et al. () with $k$ iterations.**
| Channel | AWGN |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Method | BP | Our | GA $k=75$ | GA $k=150$ |  |  |  |  |  |  |  |  |
| $E_{b}/N_{0}$ | 4 | 5 | 6 | 4 | 5 | 6 | 4 | 5 | 6 | 4 | 5 | 6 |
| CCSDS(128,64) | 6.46<br>7.32 | 9.61<br>10.83 | 13.99<br>15.43 | 7.34<br>8.61 | 10.48<br>12.26 | 14.37<br>16.00 | 6.86<br>7.87 | 9.95<br>11.31 | 13.38<br>15.56 | 7.09<br>8.23 | 10.40<br>11.79 | 14.08<br>16.04 |

## Peer Reviews

confidence: 4
contribution: 1
initial_rating: 3
presentation: 2
questions: Questions are included in the "Weakness" section. 

Suggestions: 
1. Around Line 131: Please clarify whether vectors are column or row vectors. Anyway, the dimensions of the multiplication in $H(mG)$ are incorrect. 
2. Line 157: $k=1$ should be $k=0$ because the first iterations is $2k+1=1$.
3. Eq. (4): Under $\mathbb E$, what does the expectations w.r.t. $T$ mean? Is $T$ a random variable, not a constant number? 
4. Line 197: A generator matrix is not unique in general. Is the form of the matrix fixed in this paper?
5. Line 204 etc.: $c=Gm$ should be $c=mG$ accourding to Line 131.
6. Eq. (6): "(" should be removed.
7. Eq. (8): The cumulative loss function w.r.t. iteration $t$ in (8) has been proposed in previous studies on neural BP decoders. Please add some references.
8. Line 291: What is the meaning of "sufficient statistics"? It is unclear whether the gradient is sufficiently statistical in terms of statistics. It is recommended to rephrase the term correctly. 
9. Eq. (9): What does index $i$ stand for? Since $\Omega$ represents a matrix, indices are given like $ i,j$.
10. Line 310: What is the meaning of "line-search objectives"? Is it the cost function for the optimal learning rate?
11. Line 373: The i.i.d. Gaussian mixture model is called bursty noise in this paper. It seems incorrect because bursty noise generally implies time-dependent noise. 
12. Line 457: "sparse code" should be "a sparser code" or "sparser codes."
soundness: 1
strengths: * The proposed method is the first gradient-based optimization of a parity-check matrix for error-correcting codes.
* In addition, a grid-search approach for finding the learning rate is proposed, which is an alternative to the line-search approach.
* Numerical results show that optimized codes by the proposed method can be decoded more accurately than conventional codes.
summary: The paper proposes an optimization scheme of a Tanner graph for low-density parity-check (LDPC) codes. Particularly, the scheme aims to improve decoding performance by a belief propagation (BP) decoder. Since the problem is a non-convex binary optimization problem whose cost function is implicitly defined, a gradient-based approach is applied by relaxing variables and using a straight-through estimator. In addition, a grid search is proposed to find an optimal learning rate. From numerical results, the proposed method outperforms the decoding performance of existing codes.
weaknesses: The reviewer understands the motivation of the work and the numerical effectiveness of the proposed method. However, the paper contains  some flaws as follows: 

1. **Technical contributions of the proposed method** 

The contributions that the authors claim are threefold: (i) formulation of the problem, (ii) reformulation of BP in tensor fashion, and (iii) differentiable and fast optimization method for the problem. Here, the reviewer wants to evaluate each contribution in detail. 

* (i) Formulation of the problem: In the paper, Eq. (4) (or (8)) is the formulation of the problem, whose novelty is claimed by the authors. However, a similar formulation (mainly focusing on "expectation w.r.t. random codewords and noise") has already been proposed in [Choukroun & Wolf, 2024a] cited in the paper. Eq. (4) is different from [Choukroun & Wolf, 2024a] in that Eq. (4) includes the regularization terms. However, the authors do not compare the differences explicitly and claim that the whole formulation in this paper is novel. In addition, the effect of regularization needs to be included in numerical experiments. The reviewer suggests that the author carefully clarify the novelty of the formulation.

* (ii) Reformulation of BP in Tensor fashion: The reviewer does not consider this part technically novel because a similar "tensorization" technique has been used for the implementation of neural BP decoders. 

* (iii) Differentiable and fast optimization method for the problem: The reviewer agrees with this point. However, there are some flaws, as shown below.

Overall, the technical contributions that the authors claim seem partly insufficient. In addition, the paper does not contain any mathematical or analytical contributions, which is obviously a weak point. 

2. **Contributions of the grid-search approach**

Related to the above point, the authors claim the novelty of the grid-search approach for learning rate. However, the reviewer wonders about the novelty due to the following reasons.

* No comparison with line-search methods: the authors claim that the conventional line-search methods assume the convexity of a cost function, and they are unsuitable for non-convex problems like Tanner graph optimization in this paper. However, the assumption is required to show the optimality of line-search methods. Practically, line-search methods are used for non-convex optimizations without assumptions. Therefore, numerical comparison in terms of optimization performance and/or execution time should be necessary to show the effectiveness of the grid-search method. 

* No theoretical guarantee: In contrast to the above discussion, there is no guarantee of the grid-search method for finding the optimal learning rate. It is a weakness of the proposed method. 

* Effectiveness of the grid-search approach: It is reported in Sec. 6 that an optimized matrix depends on the initial matrix, suggesting that the proposed method finds a suboptimal solution, not an optimal one. This fact may weaken the effectiveness of the method. At least, a comparison with other learning-rate optimizations will be required. 

3. **Missing advantage of the gradient-based optimization**

The authors claim that the proposed gradient-based optimization is fast but no evidence is provided in the paper. How much is the method fast compared with what?

---

confidence: 5
contribution: 3
initial_rating: 5
presentation: 3
questions: See weaknesses
soundness: 3
strengths: The main strong point are as follows:
- the first gradient-based data-driven approach via a novel complete graph tensor representation of the Belief Propagation algorithm.
- automating the process of finding a good code.

These point are indeed important as usually in practice people construct LDPC codes via heuristics, or some optimization algorithms like genetic algorithm or simulated annealing, which takes a lot of time and computational resources.
summary: The paper deals with factor graph (or parity-check matrix, PCM) optimization of error-correcting codes for Belief Propagation (BP) decoding. Actually, this optimization is difficult as it is an integer optimization problem: the elements of the PCM are either 0 or 1 and even small changes (e.g. the replacement of one element can drastically worsen the performance). The authors propose a gradient-based data-driven approach via a novel complete graph tensor representation of the Belief Propagation algorithm. The demonstrate the efficiency of the resulting codes by simulations.
weaknesses: I list the main weaknesses below:
- Given that LDPC codes are known to perform poorly at short lengths due to short cycles in the Tanner graph ( the length of the minimal cycle (the girth) of the Tanner graph is O(log n) ), could the authors elaborate on their motivation for focusing on LDPC optimization for short codes? Are there specific applications or theoretical insights they hope to gain from this approach?
- Could the authors provide BER vs SNR (or Eb/N0) curves for their results, in addition to the current tabular format? This would allow for easier comparison with existing literature and help identify potential error floors.
- To better understand the performance of your constructed codes, could you include a comparison with polar codes under SCL decoding (L=8) for short lengths? Such results can be found e.g. here https://rptu.de/channel-codes/channel-codes-database.
- To provide theoretical context for your results, could you compare them to the finite length achievability and converse bounds from Polyanskiy et al. (2010)? This would help situate your method's performance relative to fundamental limits.
- Could you provide an analysis of the final Tanner graphs produced by your method, including metrics such as column weight distribution, minimum distance, and trapping sets? This would offer insights into the structural properties of the optimized codes.
- [Minor] You write about the generator matrix and the problems related to obtaining G from H. But for the BP decoder you can perform training on zero codeword only (as you mention later). I suggest to shift to zero codeword from the very beginning.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: Additionally, I have a few questions:

1.	The purpose of showing Figure 2 is unclear. I can observe that the variation increases significantly at high SNRs; a discussion on this would be helpful.

2.	What exactly is the meaning of PEG X? In Table 1, there appear to be significant performance differences between PEG2, PEG5, and PEG10 (with PEG5 showing particularly superior performance). It would be helpful to clarify this.

3.	In line 251, it is stated that the method can be applied regardless of modulation. If there are experimental results for modulations other than BPSK, it would be useful to include them.

4.	In line 428, an experiment was proposed to optimize only $P$ while keeping III fixed in the systematic form of $H=[I P]$. However, most LDPC standards use a dual diagonal form rather than the systematic form $[I P]$. Therefore, an optimization experiment assuming the dual diagonal form would be more appropriate.

5.	Overall, the code lengths are very short, with a maximum length of 128. In this range, Polar codes are known to be superior, so the practicality of LDPC code optimization seems somewhat limited.

6.	Further research on additional properties of the modified code, such as minimum distance or cycles, is necessary.
soundness: 3
strengths: In the field of model-based neural decoder research, previous work has focused on optimizing decoder weights with a given $H$. However, this study differentiates itself by optimizing $H$ itself, which is both novel and distinctive. The derivation of trainable BP decoding equations for $H$ is particularly commendable. The paper presents a significant amount of experimental results, demonstrating performance gains through $H$ optimization for various code types.
summary: In this study, the authors propose a method to optimize the parity check matrix (PCM) $H$ using deep learning techniques. They modified the BP decoding equations that rely on $H$ so that $H$ could become trainable. To accelerate the training process, they utilized a line search method. The proposed code optimization method has the advantage of being applicable to codes with constraints or in arbitrary channels.
weaknesses: In Table 1, the optimization is performed for a wide range of initial codes, but for high-density codes like BCH, Polar, and LTE Turbo, which have their own optimized decoders instead of BP decoders, the improvements in BP performance seem less meaningful. It seems more appropriate to compare LDPC codes, but there are concerns about the "representativeness of the LDPC codes" used in the comparison. Both the MAKCAY and CCSDS codes are quite outdated (and indeed seem to show limited performance improvement). Furthermore, the PEG construction used for the LDPC PEGX code appears to be an early-stage method. In addition, The CCSDS code is known to ensure efficient encoding, but as shown in Figure 7, modifying $H$ without constraints (as it seems to have been done in Table 1) may no longer guarantee this property. 

Therefore, it would be better to evaluate whether the performance can be improved for more representative LDPC codes (e.g., short-length ARJA code class or 5G LDPC codes) while maintaining the functionalities of these code types (efficient encoding, QC structure, and rate compatibility).

Additionally, a comparison with Elkelesh et al. (2019), another data-driven code construction method, does not seem fair. In Table 4, the authors compared their optimized $H$ matrix for iterations of 5 and 15, whereas the Elkelesh method was optimized at iterations of 75 and 150. Since the Elkelesh method is also a data-driven construction approach, it seems feasible to optimize it with a smaller iteration count, such as 15. A comparison under such conditions would be necessary.

The proposed method appears to be a local optimization method highly dependent on the initial $H$ matrix. As shown in Figure 7, only a small number of edges were changed in sparse cases. As the goal of code construction is to create a globally optimized $H$ for a given code length, the proposed method does not seem to align with this objective.

---

confidence: 4
contribution: 2
initial_rating: 8
presentation: 3
questions: * For the computational complexity issues, could authors provide more discussions on how to lower the computational costs or future directions on lowering the computational costs?
* The paper shows that initializing from known sparse codes would already result in performance improvements. However, initializing from these known codes would probably result in codes that are very close to the existing codes. It would be interesting to see whether other types of initialization would give us more diverse or new codes that are totally different from all the hand-crafted codes and outperform the known codes. I think initializing the optimization from the all zero parity-check matrix would impose a very challenging optimization problem, because of the symmetry breaking issues. Could the authors try to initialize the optimization by random picking a code from the code ensemble satisfying a particular pair of degree distributions? Or the authors could provide a discussion on why initialization from known codes makes more sense.
* For the sparsity regularization, the authors provide very little discussions in the draft. In my opinion, the sparsity regularization may need more careful considerations. For example, what we may want to achieve is a sparse parity-check matrix satisfying a certain pair of degree distributions (or a regular LDPC code). Thus, each row(column) should be sparse with a designed number of non-zero elements. The authors could argue that a simple L1 regularization would already guarantee that the optimization would end-up with a regular code or a code satisfying a designed degree distribution, of course by providing more experimental results. Could the author try to use a combined L1 and L2 regularization, where L1 is applied to each row and each column, and L2 is applied to row weights and column weights?   
* For the loss weighting, I think the authors could try equal weighting at the beginning epochs and weight the losses at large decoding iterations more at later epochs. Or, the author could provide more discussions on why equally weighting is desired in certain senses.

In a summary, it is suggested that the authors could
* provide more discussions on how to lower the computational costs either in this paper or as a future direction
* provide more experiments on different optimization initialization or a discussion on why the current way of initialization makes more sense
* provide more experiments on using a combined L1, L2 sparsity regularization or a discussion on whether the L1 regularization already results in desired sparse parity-check matrices
* provide more experiments on using adaptive loss weighting or a discussion on justifying the current equal weighting.
soundness: 3
strengths: * The paper contains a novel idea of constructing low-density parity-check codes using a end-to-end differentiable data-driven approach. The idea of using STE (an approach usually used in deep learning quantization and sparsity design) for converting the original NP-complete discrete optimization into a differentiable optimization problem is novel.
* The approach in this paper open-up a new research direction of using end-to-end differentiable optimization for constructing low-density parity-check codes.
* The proposed binary line search method is novel.
* The experimental results in the paper show that the differentiable end-to-end approach results in improved coding performance
* The paper is well-written and clear.
summary: The paper presents a novel gradient-based data-drive approach for constructing low-density parity-check codes. The belief-propagation algorithms on sparse graph codes are reformulated into a differentiable matrix representation. The paper further relaxes the 0-1 constraints on the parity-check matrix bits into learnable continuous weights. Combined with a STE (Straight-Through Estimator) method, paper reformulate the optimization problem into a differentiable end-to-end optimization problem. The paper also proposes binary line-search method for solving the optimization problem.
weaknesses: * It seems that the computational complexities of the algorithm would be quadratic with respect to the code length. For example, every element of the parity-check matrix is a learnable continuous variable. Also, in the binary line search, during each optimization step, the relevant grid samples can be as large as n(n−k), which is quadratic with respect to the code length n.
* In the experimental results, the optimizations are initialized from a known sparse codes. There is a question that whether we can start the optimization from a randomly initialized code design and still ends up with a code with outperforming decoding performance.
* It seems that the sparsity regularization term is a L1 regularization. The paper lacks a in-depth discussion on other possible sparsity regularization and whether L1 regularization is optimal.
* From equation 8, it seems that the losses are equally weights at different decoding iteration steps. Because, the losses should be large at the first several iteration steps, it is my opinion that if we train the model using such equally weighted losses, we are mainly optimize the codes for its performance at the first several decoding iteration.

---

confidence: 5
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. Sections 3 and 4 can be presented in a much clearer and accessible manner. Currently, these sections make relatively straightforward concepts appear unnecessarily complex.

2. The experiments/results section should be thoroughly reworked. It is not unexpected that the authors' obtained  codes outperform the baseline codes they started with. Indeed, most of them are not particularly good codes (compared to the best-existing ones). Some of them, indeed are clearly poor codes for BP decoding. The authors should benchmark the performance of their newly-designed codes against SOTA codes.

For example, the authors should consider benchmarking their (128,64) codes with the SOTA codes reported in Figure 10 of the paper ``Efficient error-correcting codes in the short blocklength regime'' (the details of the codes are given in the paper). Without such a comparison and similar ones for other lengths, the relevance of the proposed approach is questionable.

Furthermore, the  authors should also benchmark the performance of their codes  against finite-length performance bounds, such as the Gallager's random coding bound, the random coding union bound (see same paper for details). In this sense, please report results in terms of block error rate, rather than bit error rate, as it is more relevant.

3. Rather than reporting results in terms of the negative natural logarithm of the BER, please plot BLER curves (as the ones in the paper cited above). Only in this way one is can fully understand how the proposed codes perform against SOTA codes and performance bounds. In other words, for the (128,64) codes you should reproduce Figure 10 in the paper above and include your own curves.

4. I do not see much value in the results in Figures 3, 4, 5, and 7. The results are unsurprising and provide limited insight. These results would be better suited for the appendix rather than the main body of the paper.

For example, in Figure 3 you show improvements with respect to random codes with different sparsity rates. For such lengths, random codes, particularly with higher density, are not good codes under BP decoding, so it is not surprising the your learned code works better! What do we learn from this figure that we don't know yet?

The same applies to Figure 7. I quote the paper: "We can observe that for low-density codes the modifications remain small,
since the code is already near local optimum, while for denser codes the change can be substantial". This is what any relatively knowledgeable coding expert would expect, so the figures do not bring any new insight.
soundness: 3
strengths: The proposed approach to design codes is interesting and, as the authors show, leads to codes that outperform some existing codes.
summary: This paper presents a gradient-based, data-driven method for the design of sparse-graph codes tailored to belief propagation (BP) decoding. The main contribution of the paper is to learn the factor graph structure through a differentiable representation that facilitates backpropagation. Specifically, the authors start with a complete bipartite graph where the edges are learnable.
weaknesses: Despite that the method proposed by the authors is interesting, I believe this paper should be rejected, primarily for reasons concerning its limited contribution scope and weak experimental comparisons. My argumentation is detailed below:

1. Limited contribution: While the approach presented in the paper is conceptually interesting, the contribution of this paper is too narrow to merit  publication in a major conference like ICLR. The work is more appropriate for  a coding conference such as ISIT or ITW. I believe that this work is valuable for the coding community and deserves publication, but I lacks depth and broader impact typically expected at  a  major machine learning venue or for a major coding journal.

2. Unconvincing experiments and comparisons: The experimental results are insufficient to answer the core question this paper seeks (or should seek) to address: Does this method allow to design  codes that perform better than state-of-the-art codes? This question remains unanswered. This casts doubt on the interest of the proposed approach. The authors should compare the performance of the designed codes with that of the best available codes, as well as with relevant performance bounds. Without these comparisons, the results merely demonstrate the construction of improved codes over baselines, which still underperform relative to the best codes. This weakens the impact of the method. 

Please, see my Comment 2 in Section "questions" for some suggested comparisons.

3. Non-standard metrics: The paper reports performance using the negative natural logarithm of the BER. This is very unconventional for a coding paper (and this IS a coding paper) and complicates unnecessarily the interpretation of the results.  Standard practice in coding theory involves presenting BER or block error rate (BLER) results directly (the latter is more suitable!), which allows for clearer, more interpretable results. The authors should adhere to these standard metrics. 

Please, see my Comment 3 in Section "questions".

Meta-review: **Summary:**
This paper proposes optimization of parity-check matrices of short-codelength linear codes assuming the belief-propagation (BP) decoding. For this purpose, a continuously-relaxed representation $\Omega$ of the parity-check matrix $H$ is introduced, on the basis of which a gradient-based optimization is considered, where the gradient of the piecewise-constant objective function $\mathcal{L}(\Omega)$ (equation (8)) is approximated by utilizing the shifted straight-through estimator (STE). To deal with the non-convexity of the optimization objective, the authors also propose a line-search-based heuristic.

**Strengths:**
According to the authors, this is the first proposal to learn the parity-check matrices of linear error-correcting codes. The efficiency of the proposal has been demonstrated experimentally in various scenarios.

**Weaknesses:**
- Reviewer 6Jjp mentioned several suggestions, and Reviewer 7LZc raised concern on clarity, which would imply that the quality of presentation of this paper is not satisfactory. Although Reviewer 1Q14 wrote that this paper is well written, upon my own reading of this paper my evaluation on quality aligns with Reviewers 6Jjp and 7LZc. See Additional points below as well.
- Line search: As the problem of optimizing the parity-check matrix is formulated as a non-convex optimization, as the authors states one would resort to some heuristic. On the other hand, why one can expect the proposed line search to work well in this particular problem formulation is not discussed.

**Reasons:**
All the reviewers agree the significance of the proposal as well as the demonstrated performance gains. On the other hand, several concerns have been raised by the reviewers, and the authors have not been successful in resolving many of them, resulting in ratings that are mostly below the acceptance threshold.

Additional points:
- The formula $HG^T=0$ in lines 126 and 196 should read $HG=O$ according to the definitions in this paper.
- The sentence in lines 147-9 has broken grammar and does not make sense.
- The sets $N(v),N(c)$ in Section 3 and the sets $V_j,C_i$ in Section 4 are equivalent. It is preferable to use the same symbols throughout.
- The authors claim in lines 241-2 that BP is differentiable, but at this point $H$ is still binary, so that BP is not differentiable with respect to $H$. It is only after introducing the continuous relaxation $\Omega$ that BP may be (piecewise) differentiable.
- Reviewer j4us questioned the claim that the proposal can be applied regardless of modulation. This claim has not been justified.
- The authors claim that they chose the BCE as the BER measure (lines 260-1), but they are different notions: $\mathrm{BCE}(\hat{c},c)=-c\log\hat{c}-(1-c)\log(1-\hat{c})$, whereas the bit error is defined as $1(\hat{c}\not=c)$, whose expectation is the BER.
- I feel that the subdifferentiability (line 269) is irrelevant here. Subdifferentiability is a notion associated with convex functions, whereas the objective here is non-convex, as the authors mention on the same line.
- Berlekamp (1974): "(No Title)" should be removed.

Decision: Reject