Graph Permutation Selection for Decoding of Error Correction Codes using Self-Attention
Authors: Nir Raviv
Avi Caciularu
Tomer Raviv
Jacob Goldberger
Yair Be'ery
Venue:  (2021)
Keywords: decoding
error correcting codes
belief propagation
deep learning

Abstract: Error correction codes are an integral part of communication applications and boost the reliability of transmission. The optimal decoding of transmitted codewords is the maximum likelihood rule, which is NP-hard. For practical realizations, suboptimal decoding algorithms are employed; however, the lack of theoretical insights currently impedes the exploitation of the full potential of these algorithms. One key insight is the choice of permutation in permutation decoding. We present a data-driven framework for permutation selection combining domain knowledge with machine learning concepts such as node embedding and self-attention. Significant and consistent improvements in the bit error rate are shown for the simulated Bose Chaudhuri Hocquenghem (BCH) code as compared to the baseline decoders. To the best of our knowledge, this work is the first to leverage the benefits of self-attention networks in physical layer communication systems.


Under review as a conference paper at ICLR 2021
GRAPH PERMUTATION SELECTION FOR DECODING OF ERROR CORRECTION CODES USING SELF-ATTENTION
Anonymous authors Paper under double-blind review
ABSTRACT
Error correction codes are integral part of communication applications and boost the reliability of transmission. The optimal decoding of transmitted code- words is the maximum likelihood rule, which is NP-hard. For practical realiza- tions, suboptimal decoding algorithms are employed; however, the lack of the- oretical insights currently impedes the exploitation of the full potential of these algorithms. One key insight is the choice of permutation in permutation decod- ing. We present a data-driven framework for permutation selection combining domain knowledge with machine learning concepts such as node embedding and self-attention. Significant and consistent improvements shown for the simulated Bose Chaudhuri Hocquenghem (BCH) code as compared to the baseline decoders. To the best of our knowledge, this work is the first to leverage the benefits of self-attention networks in physical layer communication systems.
the bit error rate are
INTRODUCTION
Shannon's 's well known channel coding theorem (Shannon 1948) states that for every channel a code exists, such that encoded messages can be transmitted and decoded with an eтrоr as low as needed while the transmission rate below the channel's capacity. For practical applications, latency and computational complexity constrain code size. Thus, structured codes with low complexity encod- ing and decoding schemes, were devised.
Some structured codes possess main feature known the permutation group (PG). The permu- tations in PG map each codeword to some distinct codeword. This is crucial to different decoders, such as the parallelizable soft-decision Belief Propagation (BP) (Pearl) 2014) decoder. It empir- ically stems from evidence that whereas decoding various corrupted words may fail, decoding a permuted version of the same corrupted words may succeed (Macwilliams) 1964). For instance, this exploited in the mRRD (Dimnik & Be ery] (2099) and the BPL (Elkelesh et al. 2018) algorithms, which perform multiple runs over different permuted versions of the same corrupted codewords by trading off complexity for higher decoding gains.
Nonetheless, there is room for improvement since not all permutations required for successful decoding of a given word: simply a fitting one is needed. Our work deals with obtaining the best fit permutation per word, by removing redundant runs which thus preserve computational resources. Nevertheless, it remains unclear how to obtain this type of permutation as indicated by the authors in (Elkelesh et al./ 2018) who stated in their Section III.A, "there exists no clear evidence on which graph permutation performs best for given input" " Explicitly, the goal is to approximate function mapping from single word the most probable-te to-dole permutation. While analytical deriva- tion of this function is hard, advances in the machine learning field may be of use in the computation of this type of function.
The recent emergence of Deep Learning (DL) has demonstrated the advantages of Neural Networks (NN) in a myriad of communication and information theory applications where no analytical solu- tions exists (Simeone) 2018 Zappone et al.) 2019). For instance in (Belghazi et al. 2008)) tight lower bound on the mutual information between two high- nigh-dimensional continuous variables was estimated with NN. Another recurring motive for the use of NN in communications has to do with the amount of data at hand. Several data-driver solutions were described (Caciularu & Burshtein Lin al. 2019) for scenarios with small amounts of data, since obtaining data samples in
2018

---

Under review as a conference paper at ICLR 2021
the real world is costly and hard to collect on-the-fly. On the other hand, one should not belittle the benefits of unlimited simulated data, see (Be' (Be'ery et al. 2020: Simeone et al. (0200)
Lately, two main classes of decoders have been put forward in machine learning for decoding. The first is the class of model-free decoders employing neural network architectures as in (Gruber et al.
2018). The second is composed of model-based decoders (Nachmani al.) 2016 2017 Kim et al.
2018 Doan et al. 2018 Lian et al. 2019] Carpi et al.] 2019) implementing parameterized versions of classical BP decoders. Currently, the model-based approach dominates, but it suffers from regularized hypothesis space due to its inductive bias.
Our work leverages permutation groups and DL to enhance the decoding capabilities of constrained model-based decoders. First, a self-attention model (described in Section 3) (Vaswani et al. 2017) employed to embed all the differentiated group permutations of a code in a word-independent
manner, by extracting relevant features. This is done once before the test phase during a preprocess phase. At test time, a trained NN accepts a corrupted word and the embedded permutations and predicts the probability for successful decoding for each permutation. Thereafter, set of either one, five or ten most-probable--o-eeee the permuted channel words rather than decoding arbitrary dataset with all permutations, and empirically choosing the best subset of them. Our method is evaluated on the renowned BCH code.
permutations are chosen, and decoding is carried out on
RELATED WORK
Permutation decoding (PD) has attracted renewed attention (Kamenev al. 2019) Doan et al. 2018 Hashemi et al. 2018) given its proven gains for 5G-standard approved polar codes. (Kamenev et al., 2019) suggested a novel PI) method for these codes. However the main novelty lies in the proposed stopping criteria for the list decoder, whereas the permutations The authors in (Doan et al. 2018) presented an algorithm to form a permutation set, computed by fixing several first layers of the underlying structure of the polar decoder, and only permuting the last layers. The original graph is included in this set as a default, with additional permutations added during the process of limited space search. Finally proposes a successive permutations scheme that finds suitable permutations as decoding progresses. Again, due to the exploding search space, they only considered the eyclic shifts of each layer. This limited-search first appeared in (Korada 2009).
chosen in a random fashion.
refer to (Hashemi et al. (018)) which
Most PD methods, like the ones mentioned above, have made valuable contributions. We, on the other hand, see the choice of permutation as the most integral part of PD, and suggest a pre-decoding module choose the best fitting one. Note however that direct comparisons between the PD model-based works mentioned and ours are infeasible.
Regarding model-free approaches, we refer in particular to (Bennatan al. 2018) since it integrates permutation groups into a model-free approach. In that paper, the decoding network accepts the syndrome of the hard decisions as part of the input. This way, domain knowledge is incorporated into the model-free approach. We introduce domain knowledge by training the permutation embed- ding on the parity-check matrix and accepting the permuted syndrome. Furthermore, each word is chosen fitting permutation such that the sum of LLRs in the positions of the information-bin is maximized. Note that this approach only benefits model-free decoders. Here as well comparisons infeasible.
BACKGROUND
Coding In typical communication system, first, length & binary message m E (0, 1)* is encoded by a generator matrix G into a length n codeword c = G E (0. 1]" Every codeword e satisfies Hc O, where H is the phrity-check matrix (uniquely defined by GH 0). Next, the codeword c is modulated by the Binary Phase Shift Keying (BPSK) mapping (0 + 1, + -1) resulting in a modulated word After transmission through the additive white Gaussian noise (AWGN) channel, the received word is y = x 2, where z ~ N(O, I.!.).
At the receiver, the received word is checked for any detectable errors. For that purpose, an estimated codeword is calculated using a hard decision (HD) rule: é = 1 [1.<0)- If the syndrome s = H is all zeros, one outputs è and concludes. A non-zero syndrome indicates that channel errors occurred.
2

---

Under review as a conference paper at ICLR 2021
Then, decoding function dec y {0, 1)", , is utilized with output è. One standard soft-decision decoding algorithm is Belief Propagation (BP). BP is a graph-based inference algorithm that can be used decode corrupted codewords in an iterative manner, working over factor graph known as the Tanner graph. The Tanner graph is an undirected graphical model, depicting the constraints that define the code. In these graphs, BP messages that are propagated along cycles become correlated after several BP iterations, preventing convergence to the correct posterior distribution and thus reducing overall decoding performance. We refer the interested reader to (Richardson & Urbanke, 2008) for full derivation of the BP for linear codes, and to (Dehghan & Banihashemi] (2018) for more details on the effects of cycles in codes.
Another works (Nachmani et al. 2016 2018) assigned learnable weights f to the BP algorithm. This formulation unfolds the BP algorithm into a NN, referred to as weighted BP (WBP). The intuition offered was that the trained weights compensate for the short cycles (these are most performance devastating) in the Tanner graph.
Permutation Group of code Let be permutation on nI. A permutation of codeword c (Cl, Go) exchanges the positions of the entries c:
(c) (C=(1), CT(i))
A permutation is an automorphism of a given code C E C implies (c)) E C. The group of all automorphism permutations of a code C is denoted Aul(C), also referred to as the PG of the code.
Only several codes have known PGs (Guenda 2010) such as the BCH codes, given in (Mac
& Sloane 1977) [pp.233] as:
Ta.s (1) [[2 i i B] (mod n)
with a E {1, log,,, + })} and 3 E (1.....n).. Thus a total of n logg(n + 1) permutations compose (C).
n).
One possible way to mitigate the detrimental effects of cycles is by using code permutations. We can apply BP on the permuted received word and then apply the inverse permutation on the decoded word. This can be viewed as applying BP on the original received word with different weights on the variable nodes. Since there are cycles in the Tanner graph there is no guarantee that the BP will converge to an optimal solution and each permutation enables a different decoding attempt. This strategy has proved to yield to a better convergence and overall decoding performance gains DDimikk & Be' ery] 2009), as observed in our experiments, in Section 5
Graph Node Embedding The method we propose uses a node embedding technique for embedding the variable nodes of the code's Tanner graph, thus taking the code structure into consideration. Specifically, in Sec. 4.2 we employ the node2vec (Grover & Leskovee 2016) method. We briefly describe this method and the reader can refer to the paper for more technical details. The task of node embedding is to encode nodes in a graph as low-dimensional vectors that summarize their relative graph position and the structure of their local neighborhood. Each learned vector corresponds to node in the graph, and it has been shown that in the learned vector space, geometric relations are captured; e.g., interactions that modeled edges between the nodes in the graph. Specifically, node2vec is trained by maximizing the mean probability of the occurrence of subsequent nodes in fixed length sampled random walks, employs both breadth-first (BFS) and depth-first (DFS) graph searches to produce high quality informative node representations.
Self-Attention An attention mechanism for neural networks that was designed to enable neural models to focus on the most relevant parts of the input. This modern neural architecture allows for the use of weighted averaging to optimize task objective and to deal with variable sized inputs. When feeding an input sequence into an attention model, the resulting output is an embedded repre- sentation of the input. When single sequence is fed, the attentive mechanism is employed to attend to all positions within the same sequence. This is commonly referred to as the self-attention repre- sentation of a sequence. Initially, self-attention modelling was used in conjunction with recurrent neural networks (RNNs) and convolutional neural networks (CNNs) mostly for natural language processing (NLP) tasks. In (Bahdanau et al. 2013), this setup was first employed and was shown to produce superior results on multiple automatic machine translation tasks.
In this work we use self attention for permutation representation. This mechanism enables better and richer permutation modelling compared to non-attentive representation. The rationale behind
3

---

Under review as a conference paper at ICLR 2021
4T
pe perm2vec
[T(2)
ply, m
g
T (e)
HD
Figure 1: A schematic architecture of the Graph Permutation Selection (GPS) classifier.
using self-attention comes from permutation distance metrics preservation; pair of "similar" per- mutations will have a close geometric self-attentive representation in the learned vector space, since the number of index swaps between permutations only affects the positional embedding additions.
4 THE DECODING ALGORITHM
4.1 PROBLEM FORMULATION AND ALGORITHM OVERVIEW
Assume we want to decode a received word y encoded by a code C. Picking a permutation from the PG Aut(C) may result in better decoding capabilities. However, executing the decoding algorithm for each permutation within the PG is computationally prohibitive task especially if the code permutation group is large. An alternative approach involves first choosing the best permutation and only then decoding the corresponding permuted word.
Given received word y. the optimal single permutation " E Aul(C) is the one that minimizes the bit error rate (BER):
7 arg min BER (dec(((())))))
*EAut(C)
where c the submitted codeword and BER the Hamming distance between binary vectors.
The solution to Eq. ( is intractable since the correct codeword is not known in the decoding process. We propose a data-driven approach as an approximate solution. The gist of our approach to estimate the best permutation without applying tedious decoding process for each code permutation and without relying on the correct codeword
We highlight the key points of our approach below, and elaborate on each one in the rest of this section. Our architecture is depicted in Fig. The main components are the permutation embed- ding (Section 4.2) and the permutation classifier (Section 4.3) First, the permutation embedding block perm2ved receives permutation π, and outputs an embedding vector 4 Next, the vectors (3) and 9s are the input to the permutation classifier that computes estimation p(y. T of the probability of word π (y) to be successfully decoded by dec. Next, we select the permutation whose probability of successful decoding is maximal:
arg max ply, X) A
and decoding done on (z). Finally the decoded word = ===((de((f(g))) is outputted.
4.2 PERMUTATION EMBEDDING
Our permutation embedding model consists of two sublayers: self-attentio followed by average pooling layer. To the best our knowledge, our work the first to leverage the benefits of the self-attention network in physical layer communication systems.
4

---

Under review as a conference paper at ICLR 2021
In VVaswani et al.) 2017), positional encodings are vectors that are originally compounded with entries based on sinusoids of varying frequency. They are added as input elements prior to the first self-attention layer, in order to add position-dependen signal to each embedded token and help the model incorporate the order of the input tokens by injecting information about the relative absolute position of the tokens. Inspired by this method and other recent NIP works (Devlin ict al. 2019; Liu et al., 2019; Yang et al.) 2019), we used learned positional embeddings which have been shown to yield better performance than the constant positional encodings, but instead of randomly initializing them, we first pre-train node2vec node embeddings over the corresponding code's Tanner graph. We then take the variable nodes output embeddings serve as the initial positional embeddings. This helps our model to incorporate some graph structure and to use the code information. We denote by the the dimension of the output embedding space (this hyperparameter is set before the node embedding training). It should be noted that any other node embedding model can be trained instead of node2vec which we leave for future work. Self-attention sublayers usually employ multiple attention heads, but we found that using one attention head was sufficient. Furthermore, using more self-attention layers did improve the results either.
Denote the embedding vector of T(i) by u, R and the embedding of the ith variable node by V; E Id Note that both u, and v, are learned, but as stated above, v, is initialized with the output of the pre-trained variable node embedding over the code's Tanner graph. Thereafter, the augmented attention head operates on an input vector sequence, W = (WI...., Wn) of n vectors where W; E Rd W; u +
The attention head computes a same-length vector sequence P = (Pi....: Po), where pa E Rd2, Each encoder's output vector is computed as a weighted sum of linearly transformed input entries, P: = E}=1 0g5( (Ww,) where the attention weight coefficient is computed using the softmax func- tion, dig
Dm=i e Pem of the normalized relative attention between two input vectors w; and wj. bij- (Qw:)' (Kw;)) Note that K, V E pd are learned parameters matrices.
K.
ddp
Finally, the vector representation of the permutation π is computed by applying the average pooling operation across the sequence of output vectors, 9r = > pi. and is passed to the permutation classifier.
4.3 PERMUTATION CLASSIFIER
We next describe a classifier that predicts the probability of a successful decoding given received word y and permutation π represented by a vector q. It is more convenient to consider the log likelihood ratio (LLR) for soft-decoding. The LLR values in the AWGN case are given by l = ./- y, and knowledge of og assumed.
The input is passed to a neural multilayer perceptron (MLP) with the absolute value of the per- muted input LLRs π a(E) and the syndrome s E -- of the permuted word =((). We first use linear mapping to obtain l' = We [()] and s' Ws s respectively, where We E Rd,xn and W. E (n-k) are learned matrices. Then, inspired by Wang et al. 2018). we use the following
similarity function:
g (h) = wIyss (y22 (41 (b))) + bj
(3)
where,
h lq:'ss qo l' s':'' o s l'::-- - s' -s']. Here []] stands for concatenation and o stands for the Hadamard product. We also define
(4)
6i (x) LeakyReLU (W,x+b;
where W1 E gdd,x2d, W₂ E Rdd,xd, W3 E Rd,xd,/2 and W1 E R44/2 are the learned matrices and bj E 2d,, by Rd, b3 E R2/ and b, E are the learned biases respectively.
Finally, the estimated probability for successful decoding of (zy) is computed as follows, p(y, π) = (g(h))
where (h) is the last hidden layer and (-)) is the sigmoid function. The Graph Permutation Selec- tion (GPS) algorithm for choosing the most suitable permutation is depicted in Fig. [
5

---

Under review as a conference paper at ICLR 2021
Table Values of the syper--arammetrs, permutation embedding and classifier.
SYMBOL
DEFINITION
VALUE
SYMBOL
DEFINITION
VALUE
Ir
Learning rate
10
Optimizer
Adam
dy
Input embedding size
80
dp
Output embedding size
80
LeakyReI.U Negative slope
0.1
SNR range [dB]
K
Mini-batch size
5000
Number of mini-batches
10
10-1
10-2
10-2
DER
10-1
BER
10-3
10-1
rand+BP
10
rand+BP
rand+WBP
rand+WBP
GPS+BP
GP
GPS+ WBP
GPS+WBP
Maximum likelihoad
Maximum likelihaod
2.5
Eg/No [dB]
Eg/No [dB]
BCH(31,16)
(b) RCH(63,36)
Figure 2: BER vs. SNR for GPS and random permutation selection. Both BP and WBP are consid- ered.
4.4 TRAINING DETAILS
We jointly train the permutation embedding and the permutation classifier, employing a single de- coder dec. The cross entropy loss computed for single received word is:
C= -= - log(p(y =)) + (1 dg.=) log(1 p(y.
where dy.r if decoding of π (z) was successful under permutation n, otherwise dy 0. The set of decoders dec used for the dataset generation is described in Section
Each mini-batch consists of K received words from the generated training dataset. This dataset contains pairs of permuted word (y. тT) together with corresponding label dy We used an all- zero transmitted codeword. Empirically, using only the all-zero word seems be sufficient for training. Nonetheless, the test dataset is composed of randomly chosen binary codewords e E C, as one would expect, without any degradation performance. Each codeword transmitted over the AWGN channel with σ specified by given signal-to-noise ratio (SNR), with an equal number of positive examples (d=1) and negative examples (d=0) each batch. The overall hyperparameters used for training the perm2vec and the GPS classifier are depicted in Table
To pre-train the node embeddings, we used the default hyperparameters suggested in the original work (Grover & Leskovec 2016) except for the following modifications: number of random walks 2000, walk length 10, neighborhood size and node embedding dimension d 80.
Regarding computational latency, our perm2vec component is executed only at training time, which results with pretrained permutations' embeddings. Then, all the embeddings are stored in memory. At test time, we determine the probability of a permutation to decode p(y, тT) with single forward pass of the permutation classifier. To find the most suitable permutation, one has to compute logg(n 1) such forward passes. These computations not dependant, hence they can be done

---

Under review as a conference paper at ICLR 2021
Table A comparison of the BER negative decimal logarithm for three SNR values [dB]. Higher is better. We bold the best results and underline the second best ones.
BCH (n.k)
rand+BP
rand+WBP
GPS
BP
GPS WBP
SNR (dB)
4
2
6
4
TOP
(31,16)
1.21 1.74 2.44
1.26
1.99 3.14
1.65
2.96 5.37
1.65
2.96 5.31
(63,36)
1.10 1.51 2.08
1.10
1.67 2.66
1.40
2.67 5.23
1.42 2.82 5.44
(63,45)
1.26 1.90
2.81
1.25
2.08 3.67
1.40
2.58 5.01
1,42
2.73 5.35
(127,64)
0.99 1.30
1.74
0.99 1.32 2.11
1.01 1.94 4.04
1.01 1.98 4.14
TOP 5
(31,16)
1.49 2.55 4.17
1.43 2.522.44.. 4.12
1.72
3.12 5.59
1.69 3.09 5.57
(63,36)
1.18 2.04 3.36
1.18 2.12 3.84
1.47
2.96 5.78
1.49 3.11 6.07
(63,45)
1.33 2.41 4.26
1.30
2.48
1.45
2.85 5.65
1.45 2.98 5.92
(127,64)
0.99 1.49 2.66
0.99 1.51 2.88
1.01 2.10 4.62
1.02 2.11 4.70
in parallel. To conclude, the overall computational latency of our scheme is of a single forward pass through the permutation classifier network.
EXPERIMENTAL SETUP AND RESULTS
The proposed GPS algorithm is evaluated on four different BCH codes (31, 16). 36), (63, 45) and (127, 64). As for the decoder dec, we applied GPS on top of the BP (GPS+BP) and on top of a pre-trained WBP (GPS+WBP), trained with the same configuration taken from (Nachmani ett al. (017). All decoders are tested with 5 BP iterations and the syndrome stopping criterion is adopted after each iteration. These decoders are based on the systematic parity-check matrices, H = [PT k]), since these matrices are commonly used. For comparison, we employ a random permutation selection (from the PG) as a baseline for each decoder- - rand+BP and rand+WBP. In addition, depict the maximum likelihood results, which are the theoretical lower bound for each code (for more details, see (Richardson & Urbanke 2008 Scction 1.5)).
Performance Analysis We assess the quality of our GPS using the BER metric, for different SNR values [dB] when at lcast 1000 error words occurred. Note that refer to the SNR the normalized SNR (E))No), which is commonly used in digital communication. Fig. 3 presents the results for BCH(31,16) and BCH(63,36) and Table 2 lists the results for all codes and decoders, with GPS method and random selection. For clarity, in Table we present the BER negative decimal logarithm only for the baselines, considered as the top-1 results. As can be seen, using our preprocess method outperforms the examined baselines. For BCH(31, (Fig. 2ap. perm2vec together with BP gains up to 2.75 dB as compared the random BP and up 1.8 dB over the random WBP. Similarly, for BCH((63,36) 3,36) (Fig. 2b), our method outperforms the random BP by up to 2.75 dB and by up to 2.2 dB with respect to WBP. We also observed a small gap between our method and the maximum likelihood lower bound. The maximal gaps are 0.4 dB and 1.4 dB for BCH(31, 16) and BCH(63,36), respectively.
Top-k Evaluation In order to evaluate our classifier's confidence, we also investigated the perfor- mance of the top-x permutations - this method could be considered as a list-decoder with smart permutation selection. This extends Eq. (2) from top-1 to the desired top-k. The selected code- word ε* is chosen from a list of x decoders by ě* = arg max, 1yy é.c as in (Dimnik & Be eeyery 2009).
increases better per- formance is observed, with the added-ge -aii gradually eroded. Furthermore, we plot the empirical BP lower bound achieved by decoding with a 5-iterations BP over all к n log2 (n + 1) permutations; and selecting the output word by the argmax criterion mentioned above. In Fig. [a] the reported results are for BCH(63,455. We observed an improvement of 0.4 dB between 1 and x = 5 and
The results for & E 5) are depicted in Table 2 and Fig. 3a Generally,
7

---

Under review as a conference paper at ICLR 2021
10
10-1
70
10"2
BER
10
BER
10
10
GPS+BP [top])
10
(63.36) BP [rendom)
(top5)
(62.36) base
GPS+BP (top10)
(63.36)
(127 (random)
BP lower bound
(127 64) bose
Maximum likellhood
(127 (4) small
10-5
2.0
4.5
5.5
2.5
Eu/No [dB]
En/Na [dB]
(a) Top-i evaluation for BCH(6),445.
Embedding size evaluation.
Figure 3: BER vs. SNR performance comparison for various experiments and BCH codes.
only 0.2 dB between x = 5 and x 10. Furthermore, the gap between x and the BP lower bound is small (0.4 dB). Note that using the BP lower bound is impractical since each BP scales by On l) while our method only scales by On)). Moreover, in our simulations, we found that the latency for five BP iterations 10-100 times greater compared to classifier's inference.
Embedding Size Evaluation In Fig. 3b we present the performance of our method using two embedding sizes. We compare our base model, that uses embedding size dg 80 the small model that uses embedding size d, 20 (note that d, = d..). Recall that changing the embedding size also affects the number of parameters in g, as in Eq. (3). Using smaller embedding size causes slight degradation in performance, but still dramatically improves the random BP baseline. For the shorter BCH(63,36), the gap is 0.5 dB and for BCH(127, 27,6)) the gap is 0.2 dB.
Ablation Study We present an analysis over number facets of our permutation embedding and classifier for BCH (63,36), (63,45) and (127,64). We fixed the BER to 10-3 and inspected the SNR degradation of various excluded components with respect to our complete model. We present the ablation analysis for our permutation classifier and permutation embedding separately. Regarding the permutation classifier, we evaluated the complete classifier (described in Section 4.3) against its three partial versions; Omitting the permutation embedding feature vector qa caused a performance degradation
1.5 to 2 dB. Note that the permutation т still affects both e' and s'. Excluding e' or s' caused degradation of 1-1.5 and 2.5-3 dB, respectively. In addition, tried a simpler feature vector h = [q:l' which led to a performance degradation Regarding the permutation embedding, we compared the complete pe perm2 vec (described in Section 4.2 against its two partial versions: omitting the self-attention mechanism decreased performance by 1.25 to 1.75 dB. Initializing the positional embedding randomly instead of using node embedding also caused performance degradation of 1.25 to 1.75 dB. These results illustrate the ad advantages of our complete method, and, observed, the importance of the permutation embedding component. Note that we preserved the total number of parameters after each exclusion for fair comparison.
to 1.5 dB.
CONCLUSION
We presented self-attention mechanism to improve decoding of linear error correction codes. For every received noisy word, the proposed model selects a suitable permutation out of the code's PG without actually trying all the permutation based decodings. Our method pre-computes the permu- tations' representations, thus allowing for fast and accurate permutation selection at the inference phase. Furthermore, method is independent of the code length and therefore is considered seal-
8

---

Under review as a conference paper at ICLR 2021
able. We demonstrate the effectiveness of perm2vec by showing significant BER performance improvement compared to the baseline decoding algorithms for various code lengths. Future re- search should extend method to polar codes, replacing the embedded Tanner graph variable nodes by embedded factor graph variable nodes.
REFERENCES
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. In International Conference on Learning Representations (ICLR), 2015.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. In Proceedings of the Inter- national Conference on Machine Learning (ICML), 2018.
Amir Bennatan, Yoni Choukroun, and Pavel Kisilev. Deep learning for decoding of linear codes-a syndrome-based approach. In International Symposium on Information Theory (ISIT), 2018.
I. Be' eryery, N. Raviv, T. Raviv, and Y. Be'ery. Active deep decoding of linear codes. IEEE Transac- tions on Communications, 68:728-736, 2020.
Avi Caciularu and David Burshtein. Blind channel equalization using variational autoencoders. In International Conference on Communications Workshops (ICC Workshops). 2018.
Fabrizio Carpi, Christian Häger, Marco Martalò, Riccardo Raheli, and Henry D Pfister. Reinforce- ment learning for channel coding: Learned bit-flipping decoding. In Anmual Allerton Conference on Communication, Control, and Computing (Allerton). 2019.
Ali Dehghan and Amir H Banihashemi. On the tanner graph cycle distribution of random LDPC, random protograph- prosegraph-based based LDPC, and random quasi-cyclic LDPC code ensembles. IEEE Trans- actions on Information Theory, 64:4438 4451, 2018.
Jacob Devlin, Ming-Wer Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Conference of the North American Chapter of the Association for Computational Linguistics (NAACL), 2019.
I. Dimnik and Y. Be' Be'ery, Improved random redundant iterative hdpe decoding. IEEE Transactions on Communications, $7:1982-1985, 2009.
Nghia Doan, Seyyed Ali Hashemi, Marco Mondelli, and Warren J Gross. On the decoding of polar codes on permuted factor graphs. In Global Communications Conference (GLOBECOM), 2018.
Ahmed Elkelesh, Moustafa Ebada, Sebastian Cammerer, and Stephan ten Brink. Belief propagation list decoding of polar codes. IEEE Communications' Letters, 57:1536-1539, 2018.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Interna- tional Conference on Knowledge Discovery and Data Mining (KDD), 2016.
Tobias Gruber, Sebastian Cammerer, Jakob Hoydis, and Stephan ten Brink. On deep learning-basee channel decoding. In Anmual Conference on Information Sciences and Systems (CISS), 2017.
Kenza Guenda. The permutation groups and the equivalence of cyclic and quasi-cyclic codes. arXiv 2010.
preprint
Seyyed Ali Hashemi, Nghia Doan, Marco Mondelli, and Warren Gross. Decoding reed-muller and polar codes by successive factor graph permutations. In International Symposium on Turbo Codes & Iterative Information Processing (ISTC), 2018.
M. Kamenev, Y. Kameneva, O. Kurmaev, and A. Macvskiy. A new permutation decoding method for reed-muller codes. In IEEE International Symposium Information Theory (ISIT), 2019.
Hyeji Kim, Yihan Jiang, Ranvir Rana, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath. Com- munication algorithms via deep learning. International Conference on Learning Representations (ICLR, 2018.

---

Under review as a conference paper at ICLR 2021
Satish Babu Korada. Polar codes for channel and source coding. Technical Report 4461, EPFL, 2009.
Mengke Lian, Fabrizio Carpi, Christian Häger, and Henry D Pfister. Learned belief-propagation de- coding with simple scaling and adaptation. In IEEE International Symposium on Information Theory (ISIT), 2019.
Xiao Lin, Indranil Sur, Samuel A Nastase, Ajay Divakaran, Uri Hasson, and Mohamed R Amer. Data-efficient mutual information neural estimator. arXiv preprint arXiv:1955.033 2019.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach, arXiv preprint orxiv: 1692, 2019.
Florence Jessie Williams and Neil James Alexander Sloane. The theory of error-correcting codes, volume 16. Elsevier, 1977.
Jessie Macwilliams. Permutation decoding of systematic codes. The Bell System Technical Journal, 43(1), 1964.
Eliya Nachmani, Yair Be'ery, and David Burshtein. Learning to decode linear codes using deep learning. In Anmual Allerton Conference on Communication, Control, and Computing (Allerton), 2016.
Eliya Nachmani, Elad Marciano, David Burshtein, and Yair Be'ery, RNN decoding of linear block 2017.
codes. arXiv preprint
Eliya Nachmani, Elad Marciano, Loren Lugosch, Warren J Gross, David Burshtein, and Yair Be' Be'ery. Deep learning methods for improved decoding of linear codes. IEEE Journal of Selected Topics in Signal Processing, 12:119-131, 2018.
Judea Pearl. Probabilistic reasoning in intelligent systems: networks plausible inference. Elsevier, 2014.
Tom Richardson and Ruediger Urbanke. Modern coding theory. Cambridge university press, 2008.
Claude Elwood Shannon. A mathematical theory of communication. Bell system technical journal, 27, 1948.
Osvaldo Simeone. A very brief introduction to machine learning with applications to communication systems. IEEE Transactions Cognitive Communications and Networking, 4:648 664, 2018.
Osvaldo Simeone, Sangwoo Park, and Joonhyuk Kang. From learning to meta-learning Reduced training overhead and complexity for communication systems. arXiv preprint arXiv:2001.01227 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, E. ukasz. Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems (NIPS), 2017.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding. In EMNLP Workshop BlackboxNI.P: Analyzing and Interpreting Neural Networks for NLP,, 2018
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Ruslan Salakhutdinov, and Quoe V Le. XLNet: Generalized autoregressive pretraining for language understanding. In Advances in Neu- ral Information P Processing Systems (NeurIPS), 2019.
A. Zappone, M. Di Renzo, and M. Debbah. Wireless networks design in the era of deep learning: Model-based, bi-based, or both? IEEE Transactions on Communications, 67:7331-7376, 2019.
10


Reviews:
[{"review_id": "zLP9vmOT_fk", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##### Summary\nThe use of permutation decoding improves the performance of some types of structured channel codes. Still, the question remains on which permutations (out of the vast set of possible ones that most of these codes allow) select to decode, in a way that we increase the chances of a successful recovery of the transmitted codeword. Obviously, we could just pass all the possible permutations through the decoder, but this is clearly extremely inefficient and hinders the usage of these methods on real-world scenarios. In the current manuscript, the authors propose a method to select the best possible permutation for every received corrupted codeword $\\textbf{y}$. This allows increasing the performance in terms of error rate, and preserve the efficiency of the decoding process, up to the overhead introduced by the permutation selection procedure. The methodology is based on a permutation classification procedure (trained beforehand), where each permutation is encoded into an embedding vector obtained using the concept of self-attention, to account for the geometric similarity between transformations. The pipeline presented allows improving previous permutation decoding methods by several dBs at almost no extra cost. Hence, it renders an interesting alternative to improve further the decoding of powerful and widely used coding schemes such as Polar codes, that also accept permutation decoding.\n\n##### Strong and weak points\nHonestly, the use of self-attention for this specific task sounds quite convoluted. Still, there is no doubt it actually works, and the performance is significantly outperformed. It is unclear how this attention looks between the permutation vectors, but in the end what matters is the embedding obtained, and how it captures the similarity between them, and also, I believe, some relations with the syndrome. Still, the most important advantage is that it actually should not decrease significantly the efficiency, as the forward pass required during test could be run in parallel for all permutations, as the authors suggest. This is extremely important, and it is one of the most positive aspects of the present methodology. Besides, the paper is nicely and clearly written, with all the important details explained and all the required background information, which allows perfectly understanding the methodology.\n\nStill, there are some important aspects, concerning the results, that may require, from my point of view, some further comparison/study (more details in the section ''Questions and additional evidence''):\n* First, I do consider the comparison of GPS + (W)BP vs rand quite unfair. Is there not any other, more advanced, methods for selecting at least a subset of permutations? IN BPL, although it is applied to Polar codes, the authors finally make use of only 5 different permutations, which is not that ineffective, and enable them to report a great performance. \n* The previous concern also takes me to Fig. 3a, where we can observe how there is still a lot of room for improvement, as taking the 5 top permutations still yields some extra considerable improvement. \n* When performing the ablation studies, it is not clear to which of the codes those degradations correspond. I mention this because the performance degradation, for all ablations, looks quite large and pernicious, but it is difficult to assess their impact without a proper comparison. Hence, it would be interesting to see a plot showing the actual SNR values at a BER of $10^{-3}$ for some of the most harming ones, such as the exclusion of $\\mathbf{s}’$. I consider depicting such comparison quite important because, in some cases, it seems that the degradation may take the model to worse performance than rand-WBP.\n\nFrom my point of view, the aforementioned problems hinder the comparison of results, therefore impeding a full assessment of the scheme used, the decisions taken, and its performance compared to other similar approaches. And this is for me the weakest point of the present manuscript. \n\n##### Decision, and key reasons\nAccept, after discussing and further elaborating some of the previous concerns. Despite the previously described issues, I believe the paper presents an interesting method to advance the current state of permutation decoding. Thanks to the possibility of freely generating training samples on these schemes, it is possible to achieve very satisfactory training for permutation embedding and classification. Once that is achieved, this model can be applied at almost no extra overhead, which indeed renders the current pipeline much more useable on real-world scenarios. Additionally, the paper is nicely written and justified, easing the understanding of the methodology and the need for such an approach.\n\n\n##### Questions and additional evidence\nNevertheless, I believe the authors should elaborate more on the following concerns:\n* Would it be possible to propose a more fair comparison? If not, perhaps please comment on the selection of permutations done in approaches like BPL, and how that selection criterion won’t be applicable here. This may help to alleviate the feeling that comparing against rand seems a bit unfair.\n* The results of Fig. 3a are quite revealing, and the room for improvement is still pretty large. Could you discuss a little bit more about the source of this error in the selection of the permutation? \n* Also, and as part of some supplementary material, I would appreciate a more visual comparison of the different SNR values when performing the ablation studies. And also, discard subsets of them at the same time, etc. This will help to understand better the most key components of the pipeline, as currently it just seems everything is extremely essential, and changing any single aspect will degrade significantly the performance.\n* I would like to understand why you take the absolute value of the LLR. I understand that this is the only way to proceed when you train with all $\\mathbf{0}$ codewords, but is it not harming your training?\n* Finally, I am curious about the Block error rate, as I can imagine that sometimes, when a permutation is quite wrongly chosen, it might push $\\mathbf{y}$ to a different $\\mathbf{c}$, hence leading to $\\mathbf{s}=\\mathbf{0}$, but still resulting in a wrong decoding. Could you provide some more insights about this?\n\n##### Extra feedback\nI just want to conclude with a suggestion for a correction and a typo:\n* In Section 2, second paragraph, the sentence ''Codes with good decoding performance are represented by graphs with cycles’’ is a bit confusing, as it could be understood that indeed graphs are helping with the performance. Although you clearly explain this in the following sentence, I would rephrase that sentence.\n* In page 4, when indicating the dimensions for the matrices to learn, I believe the dimensions are wrong, as they should be $\\mathbf{Q}, \\mathbf{K}, \\mathbf{V}\\in\\text{R}^{d_p\\times{d_w}}$.", "extra_scores": {}, "extra_text": {}}, {"review_id": "oB1rwNThMg2", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[Main Strengths] \n\nThis paper's main strength is that the background section is well-drafted, the problem statement is clear, and each algorithm block's motive is adequately referenced.\n\n================================================================= \n\n[Main Weaknesses] \n\nThe paper's main weakness is that it seems the motivations for choosing four different BCH codes (in Section 5) are not justified clearly. It will make the authors claim stronger if they explain why these represent linear codes cases (unless the permutation decoding only applicable to the BCH codes). Additionally, the SNR gains from baselines (rand+BP) are shown large for the BCH codes (e.g., Figure 2). However, the principal question is that one will observe similarly large gains on the other capacity-achieving codes (e.g., LDPC codes), in particular, when the baseline performs better.\n\n================================================================= \n\n[Technical Comments] \n\n1) Can this approach be extendable to other types of channels (e.g., channels with memory)? \n2) Does the algorithm require LLR to represented as simple as the AWGN channel (in Section 3.3.)?\n\n================================================================= \n\n[Typographical comments]\n1) For better readability, Section 4 can be moved to later (e.g., after Section 5).\n2) page 2: \"a self-attention model (introduced in Section 2)\" should be \"a self-attention model (described in Section 2)\".", "extra_scores": {}, "extra_text": {}}, {"review_id": "c41jRnbWeMQ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThis paper suggests a new decoding algorithm of linear error corrections codes based on self-attention. \n\nReasons for score: \nThe main idea of using self-attention for decoding linear error correction codes is interesting.\nMy main concern is about the justification of the usefulness of the proposed scheme.\n\nConcerns: \n- My main concern is that there is an insufficient amount of reasoning to explain why we use the proposed method over the existing decoding schemes. It would be better to compare the error performance of the proposed method over the other state-of-the-art decoding methods. For example, Fig. 3 (a) contains the BP lower bound and ML bound. I like this point, but I think the authors need to show the performance of the other existing schemes (other than the \"baseline decoders\" of the current manuscript) altogether to easily show the usefulness of the proposed method. Also, it would be better to clearly explain the complexity/cost of using the proposed scheme.\n\n- In the abstract, the authors state that \"the lack of theoretical insights currently impedes the exploitation of the full potential of these algorithms\". For me, this sentence seems important as it might be directly followed by the statements that explain the usefulness of the proposed algorithm. However, it is hard to find for me whether the theoretical foundation of this decoding algorithm is more robust than the other decoding schemes. \n\n- For me, it is not clear why the top k (k>1) performance matters to measure the quality of the decoding algorithm of error correction codes for communication. We usually consider the top 1 performance only for this kind of application which generally requires a very low level of error rates. Instead of plotting the top k (>1) performance, it would be better to include the comparison of performance over the best existing decoding schemes (in terms of top 1 performance given a reasonable complexity).\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Qgbm5d0Frdi", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper focuses on improving the computational complexity of permutation decoding. In permutation decoding, one aims to decode a permutation of the received codeword in the hope that it will lead to successful decoding as compared to applying the decoding algorithm on the received codeword. In practice, one performs decoding with multiple permutations to identify the ones which lead to successful decoding. This paper proposes a classifier that given a received codeword and permutation pair predicts whether the permutation will lead to successful decoding. This alleviates the need to perform the entire decoding with permutations to identify the successful permutations. The classifier itself relies on an embedding model for the permutations which utilizes a self-attention mechanism to embed permutations.\n\nOverall, I think that the paper makes good contributions to the growing field of ML for communications. The utilization of self-attention to this area is novel (to the best of my knowledge). My major concern is about the comprehensiveness of the paper (see below) and the quality of the presentation. The latter should be addressable with minor revision. \n \n\nPros: \n\n1.  The paper utilizes the self-attention mechanism to improves the computational complexity of permutation decoding. To the best of my knowledge, this is the first application of self-attention in ML for communications.\n\n2. The paper empirically demonstrates the utility of their proposed method on BCH codes.\n\n3. The paper performs an ablation study to showcase the importance of different components of their solutions.  \n \nCons/Comments: \n\n1. The paper does not present any broader ML techniques that might be useful beyond the immediate scope of the paper. If the authors feel otherwise, please include a discussion on this.\n\n2. Even though the proposed solution can be potentially employed to decode various codes, the treatment in the paper is restricted to the BCH code. The authors should make this point clear in the abstract/introduction.  Otherwise, please include experimental results with other codes or add a discussion on this.\n\n3. There is some room for improvement in the presentation of the paper. E.g., \n\na. Make the scope of the contribution precise (see the comment above)\n\nb. The discussion in Section 3.2 can be made more clear. How is the same node embedding v being used for all $i$ in $w_i = u_i + v$?\n  \nc. $d$ is being used to represent the embedding dimension as well as an indicator variable in the definition of the loss (Section 3.4)?\n\nd. The computational complexity discussion at the end of Section 3.4 can be improved.\n\nQuestion:\n\nDo authors restrict themselves to a single layer of self-attention mechanism? Have the authors explored the utility of multi-layer self-attention mechanisms, as usually practiced in the ML literature? \n\n######## Post rebuttal ##############\n\nThank you for your response. After going through other reviewers' comments and the authors' responses to those, I am comfortable with my original score. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "65_7fLUxaqW", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The focus of the paper is error correction codes. Some structured codes have a permutation group (PG) that maps codewords via permutations. The PG structure is useful for some soft decoding algorithms (e.g., belief propagation, message passing) because of the observation that while the decoding of a codeword may fail, it often happens that the decoding of a permutation of the same codeword succeeds. The paper is concerned with obtaining the best permutation to facilitate such soft decoding, through the means of deep learning. \n\nIn order to select the most promising permutation without running the soft decoding algorithms, two main ingredients are used: (1) node embeddings of the Tanner graph of the code via the node2vec method, (2) a self attention mechanism that preserves the similarity between two permutations through the node2vec transformation, resulting in close geometric representations. The node2vec embedding is pretrained on the Tanner graph of the code. A permutation classifier is trained jointly at the same time, outputting the probability that a given codeword and permutation will decode correctly.\n\nI find the construction proposed in the paper quite interesting. However, except for some intuitive reasons it is not clear that the approach would have practical merit. The experimental evaluation should provide a convincing argument. \n\nI am leaning towards rejecting the paper, because I find the experimental evaluation quite limited. Unfortunately, it seems that the experiments were run on a very limited set of codes. Only BCH codes were used for evaluation. The size of the codes is really small (n = 31, 63, 127). The rate of the codes is very low, for three of them ½, for one ¾. The size of the permutation group given in the paper is n*log2(n+1) (pg. 2). Considering Table 1 we see that 100,000 mini-batches of size 5000 each have been used for training; is the network learning only because the space is relatively small and the number of training examples very large? \n\nIn the conclusion we read “our method is independent of the code length and therefore is considered scalable”. It would be great to see evidence that the method scales to large code lengths (thousands of bits). Would the learning algorithm still produce significant results? Moreover, how does the method perform on codes with high rate? \n\nMinor comments:\n- It seems that WBP is not defined (is it weighted BP?)\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers positively valued the proposed idea of performing permutation selection in permutation decoding via combining node embedding and self-attention, which seems to be of high originality. I found that this paper is mostly clearly written, except Section 3.2 as AnonReviewer5 commented. The main concern among the reviewers is regarding applicability of the proposal beyond the BCH codes. 

Pros:
- The proposal of utilizing self-attention for permutation selection in permutation decoding is novel and interesting.
- Computational complexity in the decoding phase is only slightly increased compared with random permutation selection, and is far smaller than performing decoding for all permutations. The GPS classifier can be parallelizable to further reduce latency.
- The proposal should be applicable beyond the BCH codes to those with decoding based on the Tanner graph, including polar codes.

Cons:
- Only the BCH codes were considered, whereas in the authors responses they will add a short analysis on polar codes.
- It seems that systematic enumeration of the PG is required, which would limit applicability of the proposal.
- There is a room for improvement in presentation:
-- In Section 3.2, the description of "positional encodings" was unclear to me, in that the ordering of the codeword entries is arbitrary, unlike typical sequence transduction problems to which attention mechanism is being applied.
-- Dependence of the input vector sequences of the attention head on the permutation $\pi$ is not clearly explained.
-- Performance of the proposed method might depends on choices of the parity-check matrix, which is however not discussed in this paper at all.

Based on the above concerns, the paper is not yet ready for publication in its current form.

Minor points:
In page 3, line 14, "that" should be deleted.
In references list, "hdpc" should be in capital. "reed-muller" should be "Reed-Muller".
Decision: Reject