Denoising Diffusion Error Correction Codes
Authors: Yoni Choukroun
Lior Wolf
Venue: ICLR 2023 notable top 25% (2023)
Keywords: ECC
Deep Learning
Diffusion Models

Abstract: Error correction code (ECC) is an integral part of the physical communication layer, ensuring reliable data transfer over noisy channels. 
Recently, neural decoders have demonstrated their advantage over classical decoding techniques. 
However, recent state-of-the-art neural decoders suffer from high complexity and lack the important iterative scheme characteristic of many legacy decoders. 
In this work, we propose to employ denoising diffusion models for the soft decoding of linear codes at arbitrary block lengths. 
Our framework models the forward channel corruption as a series of diffusion steps that can be reversed iteratively. 
Three contributions are made: (i) a diffusion process suitable for the decoding setting is introduced, (ii) the neural diffusion decoder is conditioned on the number of parity errors, which indicates the level of corruption at a given step, (iii) a line search procedure based on the code's syndrome obtains the optimal reverse diffusion step size. 
The proposed approach demonstrates the power of diffusion models for ECC and is able to achieve state-of-the-art accuracy, outperforming the other neural decoders by sizable margins, even for a single reverse diffusion step. 

Published as a conference paper at ICLR 2023
DENOISING DIFFUSION ERROR CORRECTION CODES
Yoni Choukroun
Lior Wolf The Blavatnik School of Computer Science Tel Aviv University wolf volffcs.. tau.ac....
The Blavatnik School of Computer Science Tel Aviv University
choukroun, . yoni @gma 1. com
ABSTRACT
Error correction code (ECC) is an integral part of the physical communication layer, ensuring reliable data transfer over noisy channels. Recently, neural de- coders have demonstrated their advantage over classical decoding techniques. However, recent state-of-the-art neural decoders suffer from high complexity and lack the important iterative scheme characteristic of many legacy decoders. In this work, we propose employ denoising diffusion models for the soft decoding of linear codes at arbitrary block lengths. Our framework models the forward chan- nel corruption as series of diffusion steps that can be reversed iteratively. Three contributions are made: (i) a diffusion process suitable for the decoding setting is introduced, (ii) the neural diffusion decoder conditioned on the number par- ity errors, which indicates the level of corruption
given step, (iii) line search procedure based on the code's ' syndrome obtains the optimal reverse diffusion step size. The proposed approach demonstrates the power of diffusion models for ECC and able to achieve state of the art accuracy, outperforming the other neural de- coders by sizable margins, even for single reverse diffusion step. Our code is attached as supplementary material.
INTRODUCTION
Reliable digital communication is of major importance in the modern information age and involves the design of codes that can be robustly decoded despite noisy transmission channels. The target de- coding is defined by the NP-hard maximum likelihood rule, and the efficient decoding of commonly employed families of codes, such algebraic block codes, remains open problem.
Recently, powerful learning- baased techniques have been introduced. Model-free decoders (O'Shea & Hoydis 2017 Gruber et al. 2017 Kim al. 2018 employ generie neural networks and may potentially benefit from the application of powerful deep architectures that have emerged in recent years in various fields. A Transformer-based decoder that is able incorporate the code into the architecture has been recently proposed by [Choukroun & Wolf (002). It outperforms existing methods by sizable margins, fraction of their time complexity. The decoder's 's objective this model is to predict the noise corruption, to recover the transmitted codeword (Bennatan et al. 2018).
Deep generative neural networks have shown significant progress over the last years. Denoising Diffusion Probabilistic Models (DDPM) (Ho et al.) (2200) are an emerging class of likelihood- based generative models. Such methods use diffusion models and denoising score matching to generate new samples, for example, images (Dhariwal & Nichol, 202T) or speech (Chen et al.) 2020a). The DDPM model learns to perform a reversed diffusion process on a Markov chain of latent variables, and generates samples by gradually removing noise from given signal.
One major drawback of model-free approaches the high space/memory requirement and time complexity that hamper its deployment constrained hardware. Moreover, the lack of iterative solution means that both highly and slightly corrupted codewords go through the same computation- ally demanding neural decoding procedure.
In this work, we consider the error correcting code paradigm via the prism diffusion processes. The channel codeword corruption be viewed as iterative forward diffusion process to be

---

Published as a conference paper at ICLR 2023
reversed via adapted DDPM. As far we can ascertain, this is the first adaptation of diffusion models to error correction codes.
Beyond the conceptual novelty, we make three technical contributions: (i) our framework is based on an adapted diffusion process that simulates the coding and transmission processes, (ii) we further condition the denoising model the number of parity-check errors, indicator of the signal's level of corruption, and (iii) we propose a line-search procedure that minimizes the denoised code syndrome, in order to provide an optimal step size for the reverse diffusion.
Applied to a wide variety of codes, our method outperforms the state-of-the-art learning-based solu- tions by very large margins, employing extremely shallow architectures. Furthermore, show that even a single reverse diffusion step with controlled step size can outperform concurrent methods.
2 RELATED WORKS
The emergence of deep learning for communication and information theory applications has demon- strated the advantages of neural networks in many tasks, such as channel equalization, modulation, detection, quantization, compression, and decoding (Ibnkahla 2000). Model-free decoders employ general neural network architectures (Cammerer et 20.] Gruber et al.] 2017] Kim et al.] 2018 Bennatan al., 2018). However, the exponential number of possible codewords makes the decod- ing of large codes unfeasible. [Bennatan et al.] (2018) preprocess the channel output to allow the decoder to remain provably invariant the transmitted codeword and to eliminate risks of over- fitting. Model-free approaches generally make use of multilayer perceptron networks or recurrent neural networks simulate the iterative process existing many legacy decoders (Gruber et al. 2017 Kim et al., 2018 Bennatan et al., 2018). However, many architectures have difficulties in learning the code or analyzing the reliability of the output, and require prohibitive parameterization or expensive graph permutation preprocessing (Bennatan et al. 2018).
Recently, Choukroun & Wolf (2022) proposed the Error Correction Code Transformer (ECCT), obtaining SOTA performance. The model embeds the signal elements into high-dimensional space where analysis is more efficient, while the information about the code is integrated via a masked self-attention mechanism.
Diffusion Probabilistic Models were first introduced by (Soh--Dickstein et al. (2015), who presented the idea of using a slow iterative diffusion process to break the structure of given distribution while learning the reverse neural diffusion process, in order to restore the structure in the data. [Song & Ermon (0199) proposed new score-based generative model, building the work of Hyvärinen & Dayan 2005 as a way of modeling a data distribution using its gradients, and then sampling using
Langevin dynamics (Welling & Tch 2011).
The DDPM method of et al. (2020b) is generative model based on the neural diffusion process that applies score matching for image generation. [Song al. (2020b) leverage techniques from stochastic differential equations to improve the sample quality obtained by score-based models; Song et al. (2020a) and Nichol Dhariwal (2021a) propose methods for improving sampling speed; Nichol & Dhariwal (202 Saharia et al. (2021) demonstrated promising results on the difficult ImageNet generation task, using upsampling diffusion models. Several extensions to other fields,
such as audio (Kong et al. 2020) Chen et al. 2020b), have been proposed.
BACKGROUND
We provide in this section the necessary background error correction coding and DDPM.
Coding We assume standard transmission that uses a linear code C. The code is defined by the binary generator matrix G of size n and the binary parity check matrix H of size (n k)) x n defined such that GH 0 over the order 2 Galois field GF(
The input message m E {0, 11ah is encoded by G to a codeword x E C c f0. 13" satisfying channel, e.g., AWGN channel. Let y denote the channel output represented as = H. + E, where x, denotes the Binary Phase Shift Keying (BPSK) modulation of x (i.e., over (+1)), and is random noise independent of
Hæ = 0 and transmitted via Binary-Input Symmetric-Outpl
2

---

Published as a conference paper at ICLR 2023
the transmitted 2. The main goal of the decoder f R" R" is to provide soft approximation f(y) of the codeword.
We follow the preprocessing of Bennatan al. (2018): Choukroun & Wolf (2022). in order to remain provably invariant to the transmitted codeword and to avoid overfitting. The preprocessing transforms y vector of dimensionality 2n k defined as
ÿ h(y) [[)],
where, 1.-1 denotes vector concatenation, ly denotes the absolute value (magnitude) of and s(y) E [0,1 denotes the binary code syndrome. The syndrome is obtained via the GF(() multiplication of the binary mapping of y with the parity check matrix such that
s Hs = Hbin(y) = (0.5(1 - sign(y)))-
(2)
The induced parameterized decoder cø R + R" with parameters 0 aims to predict the multi- plicative noise denoted as É and defined such that y = 2t The prediction the multiplicative noise instead of the additive physical one is done in order remain invariant the transmitted code- word (lyl = |x,ē] = {,,, thereby avoiding the risk of code overfitting, as described by Bennatan al. (2018) and the proof lemma I of Richhardoonn & Urbanke (2001). The final prediction takes the form T, sign(y ea (ly1, Hy))).
Denoising Diffusion Probability Model (DDPM) Ho al. (2020a) assume data distribution To ((x) and a Markovian noising process that gradually adds noise to the data to produce noisy samples { Each step of the corruption process adds Gaussian noise according to some variance schedule given by Be such that
(()) N(xi V 1 3,xx-11 B,1))
F1 v1 3:00-1 + V 2-1 ~ I)..
(10))20) can be expressed Gaussian distribution such that, with 04 1 -Be and ā = II Oss have
((2,/20) N(xri vanto, - (1)))
(4)
I1 v Vatto + ev1 - ai, ~ (),
The intractable reverse diffusion process ((0, (xx)) approaches a diagonal Gaussian distribution as 3, 0 (Sohl-Dickstein al. 2015) and can be approximated using neural network ps (Ire)
in order to predict the Gaussian statistics. The model is trained by stochastically optimizing the random terms the variational lower bound of the negative log-likelihood function.
One can find via Bayes' theorem that the posterior g( | 2ro ) is also Gaussian, making the objective a sum tractable KL divergences between Gaussians. [H et al. (2020a) found a more DDPM (z,, that predicts the additive noise practical objective, defined via the training of a model eg e from Eq. as follows
CDDPM =
DDPM (xt, 1)1
(5)
The distribution ((xx) assumed to be a nearly isotropic Gaussian distribution, such that sampling IT is trivial. Thus, the reverse diffusion process is given by the following iterative process
It-1
DDPM (xr, (1)1 ai
(6)
Var
4 DENOISING DIFFUSION ERROR CORRECTION CODES
We present the elements of the proposed denoising diffusion for decoding and the proposed archi- tecture, together with its training procedure. An illustration of the coding setting and the proposed decoding framework are given in Figure
3

---

Published as a conference paper at ICLR 2023
Encoder
Decoder
X
BPCK
Xg
h()
E
Reverse Diffusion
Σs
z-N Z~N(O, 11,)
Figure 1: Illustration of the communication system. We train a parameterized iterative decoder co conditioned on the number of parity check errors. The decoding is performed iteratively through the reverse diffusion process, as described in this paper.
4.1 DATA TRANSMISSION AS A FORWARD DIFFUSION PROCESS
Given codeword To sampled from the Code distribution Tn q(x)), propose to define the codeword transmission procedure y = To + tg as a forward diffusion process adding a small amount of Gaussian noise to the sample in steps with & (O...., T), where the step sizes controlled by a variance schedule {Br] In our setting, we propose the following unscaled forward diffusion
(( == y x-) ~ N NN (1,
Thus, for given received word and corresponding I, we consider y as a codeword that has been corrupted gradually, such that for _N(0
y Tt xo oE zo V Bi (x xo, 3,1),
(8)
where 3: = - 1 3 and a defines the level of corruption of the AWGN channel. Thus, the trans- mission of data noisy communication channels be defined as modified iterative diffusion process to be reversed for decoding.
4.2 DECODING AS REVERSE DIFFUSION PROCESS
Following Bayes' theorem, the posterior q Ho)
is a Gaussian
such
that
((T:)=1-1,00) NN 2o), 3,1), where, according to Eq, 8
we have
B2 (e( B, Br
B.
V 3,3 and Br
B,8
3, 3
3, 3
Br 3r
The full derivation is given in the Appendix A Similarly to (Sohi-Dickstein et al. 2015 Ho et al., 2020b), we wish to approximate the intractable Gaussian reverse diffusion process ( (rt) such that
q(z,-1(Z:) pa(z,-1 N( 1),
(10)
with fixed variance 3, Following the simplified objective of Ho et al. (220b)), would adapt the negative log-likelihood approximation such that the decoder predicts the additive noise of the adapted diffusion process and
(())= Fro.(/....eooo@tteeexo0000 co(<o + 0)..
(11)
One interesting property of the syndrome-basee approach Bennatan al, (2018) 8) that, similarly to denoising diffusion models, in order to retrieve the original codeword, the decoder's 's objective is to predict the channel's noise. However, the syndrome-bar the multiplicative noise & instead of the additive noise in contrast classic diffusion models. We note, however, that the exact value the multiplicative noise is not important for hard decoding, but only its sign since x, sygn(
approach enforces the prediction of
Therefore, we propose to learn the hard (i.c., the sign) prediction of the multiplicative noise using the binary entropy loss surrogate objective, such that
4

---

Published as a conference paper at ICLR 2023
20.0
FOLARIE1.321
(C1602241
1
PACKATY00
15.0
12.5
1
10.0
8PC
7.5
2
2.5
-2
KbNo(at)
Figure 2: Reverse diffusion dynamics on (3,1) repetition code. The two points represent the two only signed codewords: =11, 1). The col- are defined by Maximum Likelihood decod- ing. Evidently, the denoising diffusion model reverses noisy codes towards the right distribu- tion. An illustration of the forward process for this code is provided in Appendix B
Figure 3: Influence of the noise or Es/No (nor- malized SNR) on the number of parity check rors for several codes. The greater the noise, the higher the number of parity check errors, which demonstrates that the syndrome conveys infor- mation about the level of noise.
[()) Er. e B.,,,BBEe((aa co( + v).,
(12)
where the target binary multiplicative noise is defined as E, = bin(20 + v BiE)). and BCE de- notes the binary cross entropy loss.
4.3 DENOISING PARITY CHECK CONDITIONING
The reverse denoising process of traditional DDPM is conditioned by the time step. Thus, by sam- pling Gaussian noise, which is assumed as equivalent to step / = T. one can fully reverse the diffusion by up to T iterations. In our case, we are not interested in a generative model, but in an exact iterative denoising scheme, where the original signal is only corrupted to measured extent.
Moreover, a given noisy code conveys information about the level noise via its syndrome, since s(y) = Hy Hx + Hz =I Fig. 3 iillustrates the impact of noise the number of parity check errors. Evidently, one can approximate an injective function between the number of parity check er- rors and the amount of noise. Such function is direction indication of the proximity of the current iterate to a solution (codeword). Therefore, we suggest conditioning the diffusion decoder according to the number of parity check errors such that c(xx) = Di=1 s(xe); (O.... k). The resulting training objective is now given by L()) Er. BCE co(oo 31 c, e,),
nn-k
Following this logic, the number of required denoising steps n. set as the maximum number of parity check errors. Similarly to the classical DDPM training procedure, sampling time step è (O....., produces noise, which in turn induces a certain number of parity errors.
The training procedure of our method is given in Alg. I The framework assumes random "time" sampling, producing a noise and then syndrome to be corrected. Note that, our model-free solution is invariant to the transmitted codeword, and the diffusion decoding be trained with one single codeword (Alg. line 1).
Since the denoising model predicts the multiplicative noise ह, at inference time it needs to be trans- formed into its additive counterpart in order to perform the gradient step in the original additive diffusion process domain. We obtain the additive noise by subtracting the modulated predicted code- word sign(?) from the noisy signal, such that é y - (i) y sign(Ey). Therefore, following

---

Published as a conference paper at ICLR 2023
Algorithm 1: DDECC training procedure.
Algorithm 2: DDECC sampling procedure
20 E C
Input: Parity check matrix H, channel's output
2: Input: Parity check matrix H, noise
schedule B1,,..,,
2: for n iterations do
3: repeat
3: y e(bin(y))
4:
f~ t~U((
4: if y = 0 then
5:
E (0,1
5:
return bin(y)
6:
Ft = 20 V 3.5 σg
6: ? ()) = sign (g))
7:
Take gradient descent step on:
7:
Get according to Eq. 14
BCE( (ae, et), bin(E))
8: y = y 1y 3,)
8:
until converged
9: return bin
Eq. 9 at inference time the reverse process is given by
VBr (z, sign(zz5)) B B.
V 33.3c 3
(x, sign(z)ea(Er.
(13)
Tt-1 24
The inference procedure is defined in Alg 2 If the syndrome is non-zero, predict the multiplica- tive noise, extract the corresponding additive noise, and perform the reverse step. We illustrate in Fig 2 the reverse diffusion dynamics (gradient field) for (3, repetition code, i.e., G = 11,
4.4
SYNDROME-BASER LINE SEARCH FOR REVERSE DIFFUSION STEP SIZE
One major limitation of the generative neural diffusion process is the large number of diffusion steps required- generally a thousand in order to generate high-quality samples. Several methods proposed faster sampling procedures in order to accelerate data generation via schedule subsampling or step size correction (Nichol & Dhariwal 2021b San- one can assess the quality of the denoised signal via the value of its syndrome, i.e., the number of parity check errors, while a zero syndrome means a valid codeword.
et al. 202I). In our configuration,
Therefore, we propose to find the optimal step size À by solving the following optimization problem
= arg min ||s [1s
8 ||1,
(14)
XER+
3. 3,
where s(-) denotes the syndrome computed over GF(() as in Eq. 2
While many line-search (LS) methods exist in numerical optimization (Nocedal & Wright 2006), since the objective is highly non-differentiable, we suggest adopting grid search procedure such that the search space becomes restricted to À I where is predefined discrete segment. This parallelizable procedure reduces the number of iterations by a sizable factor, as shown Section Details regarding the grid-search procedure are discussed in Appendix C
Architecture and Training The state-of-the-art ECCT architecture of Choukroun & Wolf (2022) used as eg. In this architecture, the capacity of the model is defined according to the chosen embedding dimension d and the number of self-attention layers N. In order to condition the network by the number of parity eπгогs e {O..... multiplied via Hadamard product with the initial elements' embedding of the ECCT. Denoting the ECCT's embedding of the i element as 6,, the new embedding is defined as Φ: Φi @ (b(e)), Vi, where & denotes the n & one hot embedding. As a transformation of the syndrome, e, remains also invariant to the codeword. Additional details on the DDECCT architecture are given in Appendix F
k). we employ a dimensional one hot encoding
The discrete grid search of is uniformly sampled over = [1, 20) with 20 samples, order to find the optimal step size. A denser code adaptive sampling may improve the results, according to predefined computation-speed trade-off. We show the distribution of optimal À in Appendix C
The Adam optimizer (Kingma & Ba 2014) is used with 128 samples per mini-batch, for 2000 epochs, with 1000 mini-batches per epoch. The noise scheduling is constant and set to 3r = 0.01, Vt. An extended discussion regarding the 3 scheduler can be found in Appendix G We initialized the learning rate to 10 -4 coupled with cosine decay scheduler down to 10 at the end training. No warmup (iiong al. 2020) was employed.

---

Published as a conference paper at ICLR 2023
Table 1: A comparison of the negative natural logarithm of Bit Error Rate (BER) for three normal- ized SNR values (4,5,6) of our method with literature baselines. Higher is better. The best results are in bold, second best underlined. BP-based results are obtained after L - 5 BP iterations in the first row (i.e. 10-layer neural network) and at convergence results in the second row are obtained after L = 50 BP iterations (i.e., 100-layer neural network). Our performance is presented for six different architectures: for N (2, 6) and = {32, 64, 128}. The presented results are obtained with the LS procedure.
Method
BP
ARBP
BCCT N
BOCT N-6
Ours N=2
Ours N-6
4
4
5
4
6
4
Polar(64,32)
4.26 5.38
4,04 4.48
4.77
5.57
6,30
7.43
8.19
9.82
4.27
4.57
4.87
5.86
5.44
6.2
7.93
7.50
6.95
5,71
6.99
6.48
8.60
9:44
7.63
11.43
12.32
9.94
6.59 8.95
8.19
6.23
5.99
8.16
8.52 11.23
11.91
10.90
6.76
6.90
6.93
9.51
9.14
9.43
12.85
12.31
12.79
Polar(64,48)
4.15 5.31
5.94 7.42
5,25
5,41 7.19 9.30
6.96
4.92 6.46
5. 6.78
8.41
5.82
6.15
7.81
8.20
10.24
10.86
5.55
5.74 7.8
7.67
10.08
10,40
5.98
5,98
8.02
8.26
11.13
10.94
5.36 7.12 9.39
6.36
8.46
11.09
5.77 7.94
10.64
6,00
8.24
10.98
3.38 3,80 4.15
4,022 5.48 7.55
3.51
8.89
5.37 7.75 10.51
12.77
Polar(118.64)
4.10.5.1 6.15
4.84 6.78
9.30
3.83 5.16 7.04
5.12
7.36
10.48
5.97 8.52 11.72
7.24
10.70 14.56
4,04 5.52
12.18
6.50
16.30
3.80 4.19 4.62
4.81 6:57
9.04
5.58 7,34
5,36 7:45
10.22
5.61 7.76 10.42
6.52 9.21
12.64
82886(128,86)
4.49 6.97
5.39 7.37 10.13
4.49
7.75
11.29
5.99
10,20
13.84
4.75 6.25 8.29
6.31 9:01
12.45
6:27 8.64
11.61
7.60 15.17
10.81
3,99 4.41 4.78
4.92 6.73
4.56 5.98 7:93
5.39
7.62
10.45
5:60
7,83 10.56
6,46
9:41 12.52
Polar( (28,96)
4.61 5.79 7.08
5,27 7.44
10.2
4.88 6,58
4.69 6.20 8.30
8.93
5.88
6.31 9.12
8.33
11.49
12.47
6.26 8.94
5.95 8.42 11.38
12.01
7.16
6.83
9.99
10.3
13.36
13.19
LDPC(49.24)
6,23 8.19 11.72
5.30 7.28 9:88
6.05
6.58 9.39 12.39
8.13 11.68
4.51 6.07 8.11
4.58 6.18 8,46
5.91
5.74
8.13
8.42
11.30
11.90
5.31 7.35
5.27 7.38 10.23
10.40
5.84
5.87
8.22 11.56
8.29
11.85
12.10
5.36
11.92
3.88 5.51 8.06
4.98 7.91
12.70
4.48
6.95 10.65
5.25
8:43 13,80
LDPC(121.60)
4.82 10.87
5,22
8.31 13.07
3.89 5.55
12.72
4.56
13.82
3.93 5.66 8.51
5.17 8.31
13.30
4.46 6.92 10.76
5.38
8.73
14.17
LDPC(121,70)
5.88 8.76 13:04
6,45 10.01 14.77
4.63 6.68 9.73
4.64 6.71 9.77
6.11
6,28 10.12
9.62
15.57
15.10
5.41 8.22 12.22
5.52 8.47 12.63
6.49
6.64
10.39 15.43
10.65 16.21
4.67 6.79 9.98
6.40 10,21
16.11
5.55 8.51 12.81
6.79
11.13 16.93
LDPC(12180)
6.66 9.82 13.98
7.22
11.03 15.90
5.27 7.59 10.08
5.29 7.63 10,90
6,92 10.74 15.10
7,17 11.21 16.31
6.26 9.41 13:41
6.12 9.38 13:25
7.39
7.68
12.19 17.83
11.46 17.65
5.30
16.44
6:26 9.41 13.46
12.17 17.55
MucKay(96.48)
6.849.40 12:57
7.43
10.65 14.65
4.95 6.67 8.94
5.04
6,88 9.86 13.40
6.18 8.63 11.53
6.28
7.93 11.65 15.51
7,86
11.61 15.51
5.17 7.07 9.64
7,38
10,72 14,83
6.31 8.83 12.03
8.12 11.88
15.93
CCSDS(128.64)
9.65 13.78
7.25 10.99 16.36
4.35
4.41 6.09 8.49
6.34
6.65
10.40
14.40
15.46
5.79
5.81 8.79 12.29
7.55 12.01 17.62
11 17.02
4.59 6.42 9.02
6.88 10,90
15.90
6.22 9.72 13.71
7.81 12.48 17.66
BCII63,36)
3.72 4.65 5.66
4.33 5.94 8,21
4.05 5.28 7.01
3.79 4.87 6.35
4.42 5.91
4.62
6.24
8:01
8.44
4.84 6.65 9.01
4.71 6.45 8.72
5.01 6.84 9.30
5.07
7.02 9.85
4.03
4.57 6.39
8.92
4.21 7.25
9.10
5.19 7.27 9.82
9.96
4.08 4.96 6.07
4,80 6.43 8.69
4.47 5.88 7,81
5.16 7.02
9.75
5.127.16
9.95
5:49
7.71
10.86
BCH(63,45)
4.36 5.55 7.26
4.97 6.90
9.41
4.66
10.25
5.33
11.05
4.79 6.39 8.49
5.60
7.79
10.93
5.41 7.61
10.46
5.61
7.94
11.36
4.60 6.05
9.65
5.09
10.38
BCHH633551
4.34 5.29 6.35
4,95 6.69 9.18
4.78 6.34 8.49
5.46
7.57
10.51
5.19
10.20
5,39
7.48 10.53
4.5 5.82 7.42
5.17 7.16 9.53
5.01 6.72 9.03
5.47
7.59
10.62
7.29 10.13
5.47
7.66
10.73
Training and experiments were performed on a 12GB Titan GPU. The total training time ranged from 12 to 24 hours depending the code length, and optimization of the self-attention mecha- nism was employed. Per epoch, the training time was in the range of 19-40 and 40-102 seconds for the N 2, 6 architectures, respectively.
5 EXPERIMENTS
To evaluate our method, we train the proposed architecture with three classes of linear block codes: Low-Density Parity Check (LDPC) codes (Gallager 1962), Polar codes (Arikan 2008) and Saase-Chudhuri--i Hoaeduurii-Huquenghhenn (BCH) codes (Bose & Ray- Say-Chaudhuri 1960). All parity check matrices are taken from Helmling et al. (2019).
The proposed architecture is defined solely by the number of encoder layers N and the dimension of the embedding d. We compare our method with the BP algorithm (Pearl 1988), the recent Autore-
7

---

Published as a conference paper at ICLR 2023
Table 2: A comparison between the line search procedure and the regular reverse diffusion. The A column denotes the difference between the logarithm of Bit Error Rate (BER) for three normalized SNR values (i.e., A = log (B)) + log (egRReg)) )). The other columns represent the mean and standard deviation of the number of iterations of the reverse process until convergence, i.e., convergence to zero syndrome.
Methol
5 Na?
A Nud
41: Reg No1
411 Reg Na5
10. No.
5
6
2012 0.11 0.15
601
03
0447
59:40
33
15 25
52-46
15 25
14 RO
1204 05
12 12
B9 =
08t 16 8:30
2033 0:17
58 12-
57
15
04 1886 n6-4
-05
4.16 310--011-0033 11:00
0.356.13-00 0.31
16. 109
75
47
15
53
46:46
40491
1443405= 18
1 1342410= 1607 =005
28:44166=]
M
496 0.0 8.00
0.33-034 0.35
185 100 88
46
46:45
14 1343205
66
27 1342305=07
12: 12#1909=0599
..10 2.16-0.13-0.23
-2.11 0,04 4.16
12.
6.
2.
6.1 5.
31
36
12222112 12
=
2.19 0.13 0.14
11.94:0 63:35
311
0.
249 31
27460
1. 22206-00
122+22004 (L5 =005
0.6 0:05 0:33
2005 0.31 6.16
115
74 4.
63
53 44:45
23+51 18+1367=
1347613211505
0nt 10.06 8.20
A.13 12 4:30
114+-0 74
13
21.449 10-1307--0
1.5. 1569 1.007 =00
3,09=
0:23 -1.00.05.000 (040
-2.33 0.46 0.55
12
33 40
51
72 30=35
27
18+1150==00
32 -4
LDPC112.30)
4.13-0.00-0.3
A.1 4:42 0.5
135+19 4. 40=
11
22 =0=35
27+77 10+11707
3.
006------66- =04
2:33
42
51
30
61 13:1770=00
1.3
4:23-0 10-00.0
-005 0:29 0.00
15
102 5564-45
14
100
5064
21+-1
13426669-5
20-22155 n9 -06
4.20-0-11:00
2117-021 0.00
151 14
5.864
100
1064
24--4 1242569-20
134-2610
05-00 -03
1243409--0
0.19-0.5.-00 -..400.0
2331 0.36 0.5
20.5 11
13.1 63344:4
65
528
4T=1B41424110-
17 1.1 B. 10=
CCSD61128664
4:21 1.3--.33--00 00.50
0.3 0:22 0.31
366 11.
66284
64
11
5484-40
44 12811+3310000
16
1.1
4.27
30.
11.0
6224
63 128 54
42 121333333
16
.091 0:02 -0:04
ca: 6:0 0.00
12 78-67413
43-51
119
76-61
53
434-5820
36.10 -88
BCHISS
-601
-.11 408 000
1241-7
43-45-55
T
75
51464 11:110741 11
2.17 -08 754-6611
0.6 0.35 0.94
0.99 0.2 1.16
45:41
36 12
47:440
26-33
15 13:3353
16422607=
13333
BCHO6L51)
0.6 0.3 1.13
0/6 0.38 1
41:41 36-34 12-24
47-40
26-34 11424
16+27 01 =1-1203-05
13421062
1003-00
Hh Clued
Belket Cluzed
Toykp Chene!
10"
15-2
1012
10.2
POLAROFLED
POLARIOUSO 26000T
00 DOCOCT
LON016550 DOEC0
EaNouBi
(b)
Figure 4: BER comparison between the ECCT N = 6, = 32 and the proposed DDECCT, for the Rayleigh fadding channel for (a) Polar(64,32), (b) BCH(63,36), and (c) LDPC(49,24) codes.
12000 K.K 2.4
NU00UUM TEBOCT
LOCCTIO DODKCT
1944
10
10
10
10-4
23
4.0 45
8.0
25
12
(a)
(b)
Figure 5: Performance comparison between ECCT and
Figure BER vs the number of iterations (up to n - k) for regular and line search reverse diffusion.
DDECCT N = 6 = 32 for various values of normalized SNR for (a) P0lar(512,3844,, (b) LDPC (529,440) codes.
gressive hyper-network BP of Nachmani & Wolf 1 (AR BP) and the SOTA ECCT (Choukroun) & Wolf, 2022). Since our decoder is based on the ECCT, the contribution of the diffusion model scheme is pertinent in comparing our results with ECCT since they have similar architectures and capacities. Our method's 's overhead over ECCT is by a factor of the number of diffusion steps L, i.c., complexity of ( (dd (2n
k) + hd)), where h is the complexity of the self-attention module.
8

---

Published as a conference paper at ICLR 2023
We refer the reader to Choukroun & Wolf (2022) for detailed complexity analysis of the ECCT. Details about the computational overhead of the DDECCT are given in Appendix [F) Note that LDPC codes designed specifically for BP-based decoding (Richardson et al. 2001).
The results are reported as bit error rates (BER) for different normalized SNR values (Eb/No) We follow the testing benchmark of (Nachmani & Wolf 2019 Choukroun & Wolf 2022). During testing, our decoder decodes at least 10" random codewords, to obtain at least 500 frames with errors each SNR value. All baseline results were obtained from the corresponding papers.
The results are reported in Tab. 1 where we present the negative natural logarithm of the BER. For each code, we present the results of the BP-based competing methods for 5 and 50 iterations (first and second rows), corresponding to a neural network with 10 and 100 layers, respectively. As in (Choukroun & Wolf 2022), our framework's performance with Line Search (LS) as described in Section 4.4 is evaluated for six different architectures, with N = {2, 6} and d {32, 64, 128), respectively (first to third rows). BER plots with respect to the SNR are given in Appendix
As can be seen, our approach outperforms the current SOTA results of ECCT by extremely large margins on several codes, at a fraction of the capacity. Especially for shallow models, the difference can be an order of magnitude. Performance is closer with short high-rate codes, for which ECCT performance already very high. We present in Figure performance the proposed DDECCT on larger codes. As can be seen, DDECCT can learn to efficiently decode larger codes and outper- forms ECCT. A separate comparison to the non-neural SCL Polar decoder of Tal & Vardy (2015) is given in Appendix H demonstrating the need to train bigger architectures in order surpass this specialized decoder.
We present in Table[]jhhe difference in accuracy A between the line search procedure and the regular reverse diffusion. We also present convergence statistics (mean and standard deviation of the number of iterations) for the regular reverse diffusion and the line search procedure. The full table with the statistics for all of the codes is given in Appendix EE, Evidently, the line search procedure enables extremely fast convergence, requiring as little one iteration for high SNR. Note that we measure the number of iterations required to reach a syndrome of zero failed checks. We do not apply early stopping to the decoding, which could reduce the average number of iterations even further if the decoder stagnates and does not converge to zero syndrome.
Non-Gaussian Channel We test our framework on non- non-Gaussian Rayleigh fading channel, which is often used for simulating the propagation environment of a signal, e.g., for wireless devices. In this fading model, the transmission of the codeword {0, 1}"" is defined as y = hr, + where h is an ne-dimesiioal i.dd. Rayleigh-distribtted vector with a scale parameter a, and z ~ O(,0021,, 1,)).
o²
In our simulations, we assume high scale 1 in order to easily compare and reproduce the results, while the level of Gaussian noise and the testing procedure remain the same as described in the paper. The overall variance of the transmitted codeword y in the Rayleigh channel is roughly twice the AWGN's on the tested SNR range. The results are presented in Figure 4 As can be observed, our method is still able to learn to decode,
under these very noisy fading channels.
BER evolution through iteration/time We illustrate in Figure the denoising process for sev- eral codes. We show how the BER decreases with time for the regular proposed method and the augmented line search procedure. We can observe the very fast convergence of the line search ap- proach. We further provide in Appendix (e the performance of the proposed framework for one, two and three iteration steps. We can see that LS enables outperforming the original ECCT, even with one step only.
6 CONCLUSIONS
We present a novel denoising diffusion method for the decoding of algebraic block codes. It is based on an adapted diffusion process that simulates the channel corruption we wish to reverse. The method makes use of the syndrome as a conditioning signal and employs a line-search procedure to control the step size. Since it inherits the iterative nature of the underlying process, both training and deployment are extremely efficient. Even with very low-capacity networks, the proposed approach outperforms existing neural decoders by sizable margins for broad range of code families.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This project has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research, innovation program (grant ERC CoG 725974). This work was further supported by a grant from the Tel Aviv University Center for Al and Data Science (TAD). The contribution of the first author is part of a Ph.D. thesis research conducted at Tel Aviv University.
REFERENCES
Erdal Arikan. Channel polarization: A method for constructing capacity-achieving codes. In 2008 IEEE International Symposium on Information Theory. pp. 1173-1177. IEEE, 2008.
Amir Bennatan, Yoni Choukroun, and Pavel Kisilev. Deep learning for decoding of linear codes-a syndrome-based approach. In 2018 IEEE International Symposium on Information Theory (ISIT), pp. 1595-1599. IEEE, 2018.
Raj Chandra Bose and Dwijendra K Ray-Chaudhuri. On class of error correcting binary group codes. Information and control, 3(1):68-79, 1960.
Sebastian Cammerer, Tobias Gruber, Jakob Hoydis, and Stephan ten Brink. Scaling deep learning- based decoding of polar codes via partitioning. In GLOBECOM 2017-2017 IEEE Global Com- munications Conference, pp. 1-6. IEEE, 2017.
A. Cassagne, O. Hartmann, M. Léonardon, K. He, C. Leroux, R. Tajan, O. Aumage, D. Barthou, T. Tonnellier, V. Pignoly, B. Le Gal, and C. Jégo. Aff3ct: A fast forward error correction toolbox! Elsevier SoftwareX, 10:100345, October 2019. ISSN 2352-7110. doi: https://doi.
org/10 100 100345. URL httt::/www.scieneeee Aaricile/pl1/22252111113333
Nanxin Chen, Yu Zhang, Heiga Zen, Ron Weiss, Mohammad Norouzi, and William Chan. Wave- grad: Estimating gradients for waveform generation. arXiv preprint arXiv:2009.00713, 2020a.
Nanxin Chen, Yu Zhang, Heiga Zen, Ron J. Weiss, Mohammad Norouzi, and William Chan. Wave-
grad: Estimating gradients for waveform generation. arXiv:2009.00713 2020b.
Yoni Choukroun and Lior Wolf. Error correction code transformer. Advances in Neural Information Processing Systems (NeurIPS), 2022.
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in Neural Information Processing Systems, 34, 2021.
Robert Gallager. Low-density parity-check codes. IRE Transactions on information theory, 8(1): 21-28, 1962.
Tobias Gruber, Sebastian Cammerer, Jakob Hoydis, and Stephan ten Brink. On deep learning-based channel decoding. 2017 51st Annual Conference on Information Sciences and Systems (CISS), pp. 1-6. IEEE, 2017.
Michael Helmling, Stefan Scholl, Florian Gensheimer, Tobias Dietz, Kira Kraft, Stefan Ruzika, and Norbert Wehn. Database of Channel Codes and ML Simulation Results. www.unt wwwuunll.... de/
channel codes 2019.
Jonathan Ho, Ajay Jain, and Picter Abbeel.
Denoising diffusion probabilistic models.
arXiv::006. 11239 2020a.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. arXiv preprint arXiv:2006. 1239, 2020b.
Aapo Hyvärinen and Peter Dayan. Estimation of non-normalized statistical models by score match- ing. Journal of Machine Learning Research, 6(4), 2005.
Mohamed Ibnkahla. Applications of neural networks to digital communications-2 a survey. Signal processing, 9017):115-12215 2000.
10

---

Published as a conference paper at ICLR 2023
Hyeji Kim, Yihan Jiang, Ranvir Rana, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath. Communication algorithms via deep learning. In Sixth International Conference on Learning Representations (ICLR), 2018.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980) 2014.
Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. Diffwave: A versatile diffusion model for audio synthesis, (aXiv:2009.0976] 2020.
Eliya Nachmani and Lior Wolf. Hyper-graph-netwoor decoders for block codes. In Advances in Neural Information Processing Systems, pp. 2326-2336, 2019.
Eliya Nachmani and Lior Wolf. Autoregressive belief propagation for decoding block codes. arXiv preprint arXiv:2103.11788 2021.
Alex Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. arXiv:2102.09672 2021a.
Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In International Conference on Machine Learning, pp.
PMLR, 2021b.
Jorge Nocedal and Stephen J. Wright. Line Search Methods, pp. 30-65. Springer New York, New York, NY, 2006. ISBN 978-0-387-40065--5
doi: 0011007/97--03387-40000 //doi. www.oor///....... 000 978 --7---8----77-------
3. URL
https:
Timothy J O' Shea and Jakob Hoydis. An introduction to machine learning communications systems.
arXiv preprint arXiv: arXiv: 1702.0083,, 2017.
Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan kaufmann, 1988.
Nir Raviv, Avi Caciularu, Tomer Raviv, Jacob Goldberger, and Yair Be' ery. perm2vec: Graph permutation selection for decoding of error correction codes using self-attention. arXiv preprint arXiv:2002.02315. 2020.
Thomas J Richardson and Rüdiger L Urbanke. The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions information theory, 47(2):599-618, 2001.
Thomas J Richardson, Mohammad Amin Shokrollahi, and Rüdiger Urbanke. Design of capacity- approaching irregular low-density parity-check codes. IEEE transactions on information theory, 47(2):619-63) 637, 2001.
Chitwan Saharia, Jonathan Ho, William Chan, Tim Salimans, David Fleet, and Mohammad Norouzi. Image super-resolution via iterative refinement. arXiv:arxin:2104.077.5 2021.
Robin San-Roman, Eliya Nachmani, and Lior Wolf. Noise estimation for generative diffusion mod- els. arXiv preprint arXiv: 104.221440000 02600, 2021.
Jascha Sohl- Sih--Dickttein Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibriun thermodynamics. In International Conference on Machine Learn- ing, pp. 2256-2265. PMLR, 2015.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. arXiv:2010.02502 2020a.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. arXiv preprint 1907v:190 2019.
Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv:2011.13450 2020b.
Ido Tal and Alexander Vardy. List decoding of polar codes. IEEE Transactions on Information Theory, 61652222332 2015.
11

---

Published as a conference paper at ICLR 2023
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-I1), pp. 681-688. Citeseer, 2011.
Ruibin Xiong, Yunchang Yang, Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tie- Yan Liu. On layer normalization in the transformer architec- ture. arXiv preprint 200:0400024 2020.
12

---

Published as a conference paper at ICLR 2023
A
UNSCALED DIFFUSION DERIVATION
According to Bayes' rule,
g(04-1 (10)
q 2o) = q
-1 20)
9 200)
1
(It
x(-1)
(81- - rn)²
(It - x00
exp
(15)
2
1 1r
1 2 31
2
exp
3t 1
-
B1
It
3r
To 20) + Clz,, Fi))
where C(z,, 2o) represents the constant term of the second-order equation. Following the standard Gaussian density function, the mean and variance can be parameterized as follows
1
B.
+
B1
3.
i4 (x no)
24
///
31
31
3
Tt +
T0
(16)
Be +
Bt
B1 +
B1
Be
3
1tt +
(It - V B,5)
B. + B1
Br + Bz
v BBBL
v₁ Bg + Be.
8.
B FORWARD DIFFUSION PROCESS VISUALIZATION
We provide a visualization of the forward diffusion process as described in Section three dimensional repetition code as discussed in Section
4. using the
Figure 7 presents random diffusion processes from one of the two valid codewords through time. As can be seen, there is a migration from the valid codewords (depicted by either a blue or red cross) to the vicinity of invalid words (black crosses).
1
Figure 7: Visualization of the forward diffusion process. The two valid codewords are represented as blue cross and a red cross. The other six words are denoted by black crosses.
13

---

Published as a conference paper at ICLR 2023
C
LINE SEARCH HISTOGRAMS AND COMPLEXITY
C.1 HISTOGRAMS
Figure presents the distribution of the optimal step size À for several codes. Each code presents different distribution of the optimal step sizes, as can be seen from the high variance of the x-axis.
P2ND-1
FANE-5
P3N2-4
100000
14
100000
353030
10
3300300
00000
04
7E0085
R3NEw3
B3N2wa
250000
34100
20
130000
1.2
333330
333330
139330
Figure 8: Histograms of optimal À values on the test set for the POLAR(128,96 96) code (first row) and the LDP(49,24) code (second row), for Eb/Ng = [4,5, 6} corresponding to the left to right histograms, respectively. The grid search sampled uniformly, taking 300 samples from the presented range.
C.2 COMPLEXITY OVERIEAD OF THE LINE SEARCI PROCEDURE
The computation the syndrome consists of a series of efficient binary operations (xor) inducing a computational complexity that proportional the density of the code.
The line search consists of the parallel computation of the syndrome, over the multiple words ob- tained for different À values sampled over predefined grid. Thus, the time complexity of the line-search procedure can be reduced to the very efficient computation of the syndrome which can be assumed constant. Without parallelization, the complexity is linear with the grid size, but the overall process remains extremely efficient.
14

---

Published as a conference paper at ICLR 2023
D DDECCT PERFORMANCE WITH FEW ITERATIONS
Table 3 presents the performance of the proposed framework for one, two, and three iteration steps with the regular reverse diffusion method and with the proposed line-search approach. As can be seen, the line-search approach improves over the regular reverse diffusion by orders of magnitude.
Table 3: Negative natural logarithm of BER by number of iterations for N=2 models for the reg- ular and the LS diffusion methods. Higher better. The (column) average over the codes and the dimensions d for the ECCT is (4.58, 6.20, 8.43) on the (4,5,6) Es/ No respectively, and (4.64, 6.37, 3.78 for LS with one iteration.
Method
ECCT
Reg
1:. Reg
It. Reg
1t.
LS
LS
||
6
6
5
4
5
6
4.27 5.44 6.95
2.9 3.39
3.92
3.04 3,51 4.09
3.13 3.3336444 4.26
4.59 6.13
8.23
5.487.43
7.43 9.89
5.71 1.75
10.
Polar(64,32)
296
3.14
6.51
5.84 7.96
4.87 6.2 7,93
2.96
3.39
3.92
3.04 3.51 4.09
3.14 4:26
5.06 6.79 8.99
6.08 8:27
10.58
8.30
10.92
6.42 8.41
3.78 4.41 5.18
3.92-4.33 5.46
4.07 4.85 5.75
5.03
6.80 9.13
5:42
9.92
5.52 10:15
Polar(64,48)
5.14
4244255..
4.85 5.75
5.18 7.03 9.47
5.59
10.19
5.36 7.12 9.39
3.78 4.42 5.18
3.93 4.63 5.46
4.09 5.75
4.86
5.24 9.59
7.15
5.68 7.74 10:22
5.74 7.89 10:43
3.51 4.52 5.93
3.35 3.88
2.97 3.43 4.00
3.02
1.12
3.72 6.64
1.45
6.30 8.54
4.78 6.77 9:01
(28,64)
4.90
3:04
4.12
4.85
9.06
4.04 5.52. 7.62
2.93 3.36 3.88
2.98 3.44 4.00
3.04
4.13
4.05 5.39 7.10
5.11 7.14
9:23
5.58 7.67 9:66
4.30 5.58. 7.34
3.49 4.05 4.74
3.57 4,18 4.93
3.66
4.53 5.97 7.92
5:21 7.18 9:64
5.42 7.46 9.98
(28,)))28886)
4.19
4.33
5.58
10.17
4.75 6.25 8.29
3.50 4.06 4.75
3.59 4,19 94
3.69 4.33 5.14
5.04 6.73 9.00
5.87 8:03
10.71
6.06 8.29 11.04
4.56 5.98 7.93
3.74 4.37 5.13
3.85 4.54 5,36
3.96 5:60
4.75 6.40 8.73
5:29 7.36 9.97
5.45 7.59 10.19
Polar(12896)
5.36
4.94 6.78 9.34
5.59
10:71
4.88 6.58 8.93
3.75 4.38 5.14
3.87 4.55 5.37
3.99 5.61
5.22 7.27
10.06
5.95 8.45 11.48
6.13 8.71 11.73
4.51 6:07 8.11
2.92 3.36 3.88
3.01 3,48 4.05
3,10 4.
4.51 6.12 8.39
5,02 6.95 9:62
5.13 7.13 9:87
(DPC((9924)
4.05
4.23
4.54 6.13
5.07
9.74
4.71 6.38 8.73
2.92 3.36 3,88
3.01 3.48 4.05
3.10
4.23
4.58 6.19
8:57
5.10 6.96
9.77
5.21 7.12 10.00
3.88 5,51 8.06
2.91 3.34 3.86
2.96 3,42 3,98
3.01 3.50 4.11
3.79 5.52
7.62
4.35 6.62 10.16
4.50 6.91 10,50
LDPC(121,00)
2.91
3,98
3.50 4.11
3.79 5:33
7.64
4.36 10.16
3,93 5,66 8.51
2.91 3.34 3,86
2.96 3.42 3.98
3:01 3.50 4.11
3,80 5.34
7.66
4.38 6.65 10.29
4.53 6.93 10.64
1.63.6.68 9.73
3.19 3.68 4,29
3.26 3.80 4.41
3.34 4.62
4.57 6.58
9.50
5.32 8.06 11.80
5.45 8.24 12.08
LDPCC121,70)
4.62
4.60
9.64
5.37
4.67 6.79 9.98
3.19 3. 4.29
3.23 3.80 4.45
3.34
4.62
4.61 6.65
9:70
5.38 8 24
5.52 8.43 12.66
5.27 7.59 10.08
3.47 4.03 4.72
3.57 4,18 4,93
3.68 4.34 5.16
5,28 7.67 10.92
6.04 9.03 12.73
6.17 9.25 12,99
LDPC(12180)
4.18 4.93
4.34 5.16
5.29 7.65 11.00
6.06 12.55
5.30 7.65 11.03
3.47 4.05 4.72
3.57 18 4.93
3.68 3.68 3.68
5.29 7.66 11:00
6.06 9. 12.91
6.19 9:25 13:20
4,95 6.67 8.94
2.95 3.39 3.92
3.04 3.51 4.09
3.12
4.26
5.00 6.86 9.37
5.96 8.30 11.10
6.11 8.49 11.29
K4y)664))))
6.80
2.95
3.92
4.09
3.13
4:26
5.05 6.95 9.52
6.02
11.59
5.17 7.07 9.64
2.95 3.39 3.92
3.04 3.51 4.09
3.13 3.63 4.26
5.04 6.94
9:53
6.01 8:45 11.47
6.18 11.70
6.05 8.30
2.93 3.37 3.90
3.00 3.47 4.04
3.06 3.57 4.18
4.33 6.00 8.44
5.40 7:95 11 11.52
5.68 8.34 11.95
CCSDS(128.64)
6.19
2.95
3,90
3.47
3:06
4.18
4.34 6.04
8.49
5,43
1555
5.71
4.59 6.42 9.02
2.93 3.37 3.90
3,00 3.47 4.04
3.57 4.18 3:07
4.35 6.08
8.51
5.44 8.09
11.65
5.72 8.48 12.13
3.79 4.87 6.35
3.17 3.67 4,26
3.25 3.79 4,43
3.33
1.61
4.11 5:48 7.34
4.43 8.05
4.53.6.15 8.27
3CH(63,36)
3.25 4.44
4.21 5.63 7.52
4.52
8.22
4.21 5.50 7.25
3.18 3.67 4.27
3.26 3,80 4.44
4.62 3.35
5.91 4.37
7.95
4.76 6.55 8.90
4.91 6.78 9.23
4.17 5.85 7.81
3.65 4.26 4.98
3.76 4,43 5,23
3.88
5:48
4.62
8.57
4,96
6.85 9.50
5.06 7.04 9.76
BCH(63,45)
4.98
5.23
5.48
4.73
5.10
9.81
4,79 6.39 8.49
3.65 4,26 98
3.77 4.44 5.23
3,90
4.66 5.48
4.79 6.52 8.95
5.17 7.18
9:93
5.90 7.39 10.21
4.60 6.05 8.05
3.96 4.63 5.46
4,09 4.84 5.74
4.22 6:03
4.78 6.47 8.88
4.99 6.83 9.40
5.05 6.98 9.59
BCH(63,51)
5.46
5.74
4.23 6.03
4.85 9.08
5.08
9.74
9.96
5.01 6.72 9.03
3. 16 4.63 5.46
4,10 4,85 5.74
4.24 6.03
4.88 6.66 9.16
5.11 7.04 9.79
5.18 7.19 9.97
15

---

Published as a conference paper at ICLR 2023
E NUMBER OF DIFFUSION STEPS
Table Sableprreentts the convergence statistics (mean and standard deviation of the number of iterations) for the regular reverse diffusion and the line search procedure. Evidently, the line-search approach substantially reduces the number of steps, especially for low SNRs where the improvement can reach one order of magnitude.
Table 4: A comparison between the line search procedure and the regular reverse diffusion. The A column denotes the difference between the logarithm of Bit Error Rate (BER) for three normalized SNR values (i.e., A = log LER + log( (BERReg)),
The other columns represent the mean and standard deviation of the number of iterations of the reverse process until convergence, i.e., convergence to zero syndrome.
Matthe
Nut
Nin
NoA
Nun
1SN
4106 -010-013-- 40.0
IL54
0.0c 64L
13 75
19263 113-175
54
68261
16:331 105
182301782111
.1.4 0:1
11108
4102 9:1 0.16
1.50 016 0/67
59:.4
13235 38
15221
57
32133
154:27
14 ID 1001449
124 07 INPA WF Un
No1 0.1
0.12 0.41
38.
ST
13 ND
ca
32
15
0604
.019-0026-00
.011- 0069
154 161-4114414
15 1810--0
-0.3:40.0 100
11
1412110 197
1711211
D 6.
41:30-2:11
44.2040:12
1A5 105
134.75
45-144
40
14
201444 18= 1
0,3
.0.09 0..00000000 00.10
.0.32 0:31-011000 0.40
147
16:044
46
83
46
27
13+1308
12+ 19 03
10 00.15
-1.35
0.14
118
11
10.12
A1
s0 111- 1-6
1.3 09 D585
ALJ66-0.12-40 40.33
40.15 0100 0013
23
52
31
6.1249
31
20:44 1021306
LI 15 09 =9
4:31 0.16
11
45
45
11=51
36 13= 05
LDROW9220
0.55
0.00 0.20
.0.13 0.1.0.12000 0.30
114+70
14 14
44
43
75
5.4 44+-45
21
10+ 10+1907+06
1,5 09 1.107-65
WLT -0.10
.1.2 41114-553000 3441
114.27
73 105
44144
21 1011990 1.06
141 0M
1.11
41:1--0-0-400
00.7
-0.33
0.01
TT 16.
151
119
144144
101 11121122111 171101111111
15325 1111
AL08-9.17-40 40.30
-0.11 4.09 8444
266 165
15.1
21.7
11.2
64
03
2112 1711013
=4= 18113 = L.
A.18-0,30.00
0.3
265 16.
93
28 20:6010-: 10
42 12
0.15-0..59.00 0.44
.0.15 0.20 1.00
175 11.
60
42
55 61
12 13+1509
20
10= 11 18152 WSIL C4
L0POU21.00
AL18-0224
-1.35 2017
176
43 125 11111219910
4.13 035-333--00 0044
4U31
4.46 1005
115229 13:30
40
22247
49418
21213
102140722
1.3 09 04 2:44
L0PO12190)
113-0-10440
40
1145
404 18
23
144
4110-5.17-0
-1.76
1711708 146
0507
0.33.0:16.00 0.50
..35
0:29 0.00
153+79
103
64
100 14
64444
1 13+2609207
22 -155-01111
4L39 1119-011-400
4139 -0.5--33000 2011
112
100 36
24 121:2A09 2.0
1.14
218 11A
43
13
CCS09112664
-0.3
42
IK1
141
19
1311111
41:3 101---22-00 00-40
-0.66 003--111 0.77
716 11.0
151
6.7
IK1 1A5
12.6
54
11
42- 13
14111411-00 1.6
16-
BL3081200
4150 010
4015 DU3
12 322
02
43
115
25 25..
43.
33
25:130 1.1 2.413 1.044
0.54 0.16 0.23
...1 4.00 0/14
12.1
16:265
45:50
11.7 15
454550
25 +122227 205
25
1.1 11230.
0m0
-0.00-
72
41:145
30 32
48:-4
19113
05 1A0--1144--00
1.44 18 11364--05
800 0:15 0.10
-0.14 018 6-11
714-6
10:44
34
68-
19:413
20
19-
D1 114444006
144-260--094 -0904 1-64
0:0 0.18
.131 4111116000 0.71
30
191-13
201
1K B 1.M 1966
13175077 1664
M604 0.28 019
IL59 0.42 1.16
41 26:34
12524
26
121
18: 10 111003333000
18:1-2 0T 12213 1.0A
0.66 0:31 1:13
0.06
0:38
1.19
48
34-34
47
26434
12414
16-22 01--0-1-11100 1120300000
13
06 1803 4-0.5
13433
F DENOISING DIFFUSION ERROR CORRECTION CODE TRANSFORMER
F.1 PARITY-CHECK CONDITIONING ARCHITECTURE
The DDECCT architecture is depicted in Figure 9 In order to condition the network on the number of parity errors ét E {O...., n - k). we employ a d dimensional one hot encoding multiplied via Hadamard product with the initial elements" embedding of the ECCT. Denoting the ECCT's embedding of the i element o; the new embedding is defined as &i di @ (ex), Vi, where vi denotes the n - one hot embedding.
F.2 DDECCT COMPUTATIONAL COMPLEXITY
The computational overhead consists of the conditioning, which is a negligible Hadamard product of the initial ECCT embedding with the one-hot encoding of the number of parity-check errors, the parallel line-search procedure (which scales linearly with the density of the code, and most codes sparse), and the number of reverse diffusion iterations, which is reduced to extremely few iterations by the line-search framework.
16

---

Published as a conference paper at ICLR 2023
bin bin(sigm(())
Initial Embedding
Decoding
Output
+
Ohre-hal
Nx
Feed
Embed. V
Norm
2n
MH-SA
8()
bin(sign() ())
t
2n-k Bits
Norm
Embodding
H
Figure 9: Illustration of the proposed DDECCT architecture. The main difference from HCCT is the green component in the Initial Embedding module.
Therefore, the large improvement of DDECCT over ECCT obtained while employing modest increase in computational complexity. Most importantly, the space complexity, determining the capacity of the network, is extremely reduced with the DDECC framework, since even shallow DDECCT architectures outperform deep ECCT models.
should also mentioned that as described the introduction, the iterative DDECC framework supports differential treatment of the samples based on their level of corruption, what is not possi- ble with ECCT.
G BETA SCHEDULING
The choice of the scheduling range, i.e. 1 (0,1,...,7) explained follows. In contrast classical denoising diffusion models used as generative models, the conditioning in our model is performed over the number of parity-check errors order obtain an estimate the proximity to the solution. Thus, T is now defined as the maximum possible number of parity-check errors, i.e.
The values of the beta schedule have been set empirically such that the cumulative sum of the diffusion noise roughly corresponds to the average training noise statistics, i.e., v B such that = x + 02, 2 ~ (0, I), as described in Eq.
In addition the empirical support, constant scheduling has been chosen to induce uniform treat- ment of the noise space. Finally, the full method uses the line-search procedure, reducing the need precisely define tune the scheduler.
H COMPARISON WITH SUCCESSIVE CANCELLATION LIST (SCL) POLAR DECODER
Table compares the performance of ECCT and DDECCT to the SOTA SCL Polar decoder Tal & Vardy (2015) for several Polar Codes. The SCL decoder has time and space complexity of O(L log N) and OLLN). respectively.
We tested the SCL algorithm for L {1, 4} using the AFF3CT software (Cassagne et al. 2019 Note that with this software package, we cannot ensure an exact comparison to our settings and even with regard to the polar code used.
Increasing the capacity of the network, especially with more layers, expected to lead to better results demonstrated for LDPC codes. Similarly, SCL with bigger lists would obtain improved accuracy. We present in Figure I0 the performance of different architecture size. We can observe larger architecture is able to close the gap with the SOTA Polar codes.
17

---

Published as a conference paper at ICLR 2023
Table 5: A comparison of the negative natural logarithm of Bit Error Rate (BER) for three normal-
ized SNR values (4,5,6) between the proposed method with N = 6, d = 128, the ECCT and the SOTA SC-L algorithm. Higher is better.
Method
SC-L =1 1
SC-L = 4
ECCT
DDECCT
4
6
4
5
6
4
6
4
6
Polar(64.32)
7.30
9.67
13.18
8.11
10.70
14.04
6.62
8.89
12.02
6.93
9.51
12.79
Polar(64.48)
6.17
8.41
10.97
6.63
8.63
11.24
6.19
8.28
11.05
6.00
8.24
10.98
Polar(128,66)
8.37
11.69
13.70
9.60
13.16
17.42
5.92
8.64
12.18
9.11
12.90
16.30
Polar( 128,86)
7.54
10.74
15.14
9.26
13.04
17.13
6.31
9.01
12:45
7.60
10.81
15.17
Polar( I 128.66
6.74
9.53
13.53
8.02
11.60
18.16
6.31
9.12
12.47
7.16
10.3
13.19
We believe the high number of degrees of freedom in our model coupled with careful training and hyper-parameter tuning should fill the remaining gap. Most importantly, we believe that permuta- tions of the parity check matrix may have large impact the performance described in many previous neural decoding works (e.g. (Bennatan et al. 2018 Raviv et al. 2020
POLATSSU22
POLARTOUUE
10
10-2
10
10-5
30
10a4
4.50
4.25
4.50
4.35
5.00
5.35
5.50
5.5
6:20
30:2
4.50
4.35
4.50
4.75
5.00
5.25
5.50
535
6.50
Figure 10: BER plots comparing ECCT, DDECCT and the SCL algorithm for various Eb/No and N values.
I RESULTS OVER MULTIPLE SNR VALUES
Figure depicts BER plots comparing the performance of BCCT and DDECCT for several codes.
10a2
10
10'3
10"1
10
15:4
10
10a4
15-
10'
DODOCTOO- 6-32
10a
10
12"3
10
15
Figure 11: BER plots comparing ECCT and the proposed DDECCT for various Eb/No values.
18


Reviews:
[{"review_id": "qzkdrUtm5d", "reviewer": "Reviewer_U25g", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes to employ denoising diffusion models to decode error correcting codes (ECCs). In particular, the authors introduce a diffusion process that models well the decoding of an ECC, and the denoising is performed by conditioning on the number of errors in the parity check matrix. In order to choose the step size of the reverse diffusion, a line search is adopted. The authors compare their results to the transformer-based decoder recently proposed by Choukron & Wolf, (2022). Some comparisons with 'classical' decoders (BP) are also provided.", "summary_of_the_review": "Overall, the paper provides a new framework based on denoising diffusion models, which results in improvements over the existing work by Choukron & Wolf, (2022). My borderline initial opinion is due to the weaknesses pointed out above concerning the experimental results. If such points are properly addressed during the rebuttal, I can raise my score.\n\n--- \n\nMy concerns have been addressed and I have increased my score.", "strength_and_weaknesses": "Strengths:\n\n(1) The idea of using diffusion processes in the context of error correction is, at the best of my knowledge, new. Compared to existing neural decoders which often do not scale well to larger block lengths, this novel framework has the potential to scale to codes with block lengths of a few hundreds of bits.\n\n(2) Clear gains in a number of different settings with respect to ECCT, i.e., the transformer-based approach of Choukron & Wolf, (2022).\n\n\nWeaknesses:\n\n(1) My main concern is that the comparison with 'classical' (i.e., non neural-network-based) decoding algorithms is not sufficiently thorough. It could be that DDECCT does better than ECCT, but ECCT is not quite SOTA, in the sense that there is a 'classical' algorithm that performs much better with roughly the same complexity. More specifically, the standard decoder of polar codes is *not* the BP decoder taken into account here, but rather the successive cancellation list (SCL) decoder. Is DDECCT able to match SCL performance? Let me highlight that, at the lengths considered here (64 in Figure 4, but also 512 in Figure 5), SCL reaches the optimal ML performance with a relatively small list size. \n\n(2) In page 8, the authors give an expression of the overhead of the proposed method over ECCT. However, it is not clear what the overhead is in terms of running time. Suppose that one wishes to compare ECCT with the method proposed here, keeping the complexity fixed. This means that ECCT could use a larger N or d than DDECCT (provided that the complexity of the two procedures is the same). Would DDECCT still compare favourably?\n\n(3) Comparing the performance of different decoding algorithms in the tabular form of Table 1 is not really standard in wireless communications. In particular, what really matters in practice is the SNR needed to reach a certain target BER. Target BERs typical in wireless communications are e.g. in the range $10^{-3}-10^{-5}$. This difference in reporting the results can be quite substantial: if the error curves are very steep, the improvement in the error probability at a fixed SNR could seem very large, while the improvement in the SNR needed to reach the target BER may be limited. I strongly suggest that the authors provide a plot of the error probability as a function of the SNR in addition to Table 1, so that the improvement with respect to the baselines is more clear. As a final (minor) note, I would suggest that the authors put in bold the number corresponding to the best performance in Table 1 to improve readability.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "eQgI7k8QHXn", "reviewer": "Reviewer_YkMp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes a new decoding framework in algebraic block codes by employing a denoising diffusion model. \nThe idea is to learn the process of the codeword corruption using the diffusion model and to detect the noise contribution in an output y by computing the reverse process of the corruption using the learned model. To implement this idea, the authors make some approximations in the reverse process and propose some additional ideas, such as learning the binarized multiplicative noise instead of the additive one and learning the noise process conditioned by the number of parity check errors. The experimental results of the proposed method significantly outperform the other comparative methods, such as the transformer-based framework and the standard decoding scheme based on Belief propagation in terms of the bit error rate (BER), demonstrating the superiority of the proposed method.\n", "summary_of_the_review": "The core idea of the paper is novel and interesting, and the experimental result of the proposed method is good. Hence, I basically vote for accepting the paper, though the presentation should be improved.\n", "strength_and_weaknesses": "Strengths:\n- A novel idea about how to use the diffusion model in decoding.\n\n- The high decoding performance of the proposed method compared to other methods.\n\nWeaknesses:\n- The ideas for implementation, such as learning the binarized multiplicative noise instead of the additive one and learning the noise process conditioned by the number of parity check errors, have no theoretical reasoning.\n\n- There seems to be no guideline on how to choose the variance schedule {\\beta_t}_{t=0}^{T}.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DqNe4PQiMO", "reviewer": "Reviewer_8AQR", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a novel decoding principle for error correcting codes (ECC) based on diffusion models.  The denoising diffusion probability model (DDPM) by Ho et al. can be seen as a basis of the proposed algorithm. A reverse diffusion process in DDPM is used as a decoding process of an ECC. The noise estimator neural network is conditioned on the number of parity errors that  indicates the level of corruption of the original codeword. A line search procedure is introduced for determining a proper diffusion step size. Their experimental results indicates that the proposed algorithm surpasses known state-of-the-art decoding algorithms such as belief propagation(BP). Especially, proposed algorithm has strong advantage for short length codes. ", "summary_of_the_review": "In summary, the decoding principle presented in the paper may indicate a new direction of decoding algorithms. Although I am not so sure whether the proposed algorithm is really competitive against known algorithms such as BP in a practical situation, I am inclining to be positive about this paper because it definitely contains something new from the view point of coding theory. ", "strength_and_weaknesses": "[Strength]\nI am working in the field of error correcting codes, especially for LDPC codes. As far as I know, the idea to use the DDPM as a decoding algorithm is definitely novel one.  The idea of the proposed method is natural and reasonable. The method proposed in the paper heavily depends on the idea and the DDPM architecture presented in Ho et al. but  the paper contains non-trivial contributions such as conditioning based on the Hamming weight of the syndrome and line search procedure. Furthermore, the decoding principle presented in the paper has not been discussed in the coding community. The decoding principle presented in the paper  can be a new direction for the further research in coding theory. The experimental results are promising and supports this optimistic view.\n\n[Weekness]\n(1) I felt that some details of the algorithm is not well documented in the paper (I will describe it in the next section).\n(2) Computational complexity and scalability for longer codes: I got rough understanding on a computational procedure of the decoding process. In order for the proposed method to be a real competitor of the known decoding algorithm such as BP, fair comparisons of the computational complexity will be needed.  For example, BP can be practically applied to LDPC codes of length up to 10^3-10^4. It is better to include some discussions regarding scalability. If this paper concentrates on the ``proof of the concept'', the computational complexity issue is not a large problem so far but some more discussions help the readers. \n(3) I would like to see the results of the numerical experiments on AWGN channel in graphs like Figure 4 (SNR versus BER).  It is common to   display decoding performances in such a way in coding community. It makes easier to grasp the difference in decoding performances.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%