CRISP: Curriculum based Sequential neural decoders for Polar code family
Authors: S Ashwin Hebbar
Viraj Vivek Nadkarni
Ashok Vardhan Makkuva
Suma Bhat
Sewoong Oh
Pramod Viswanath
Venue: Submitted to ICLR 2023 (2023)
Keywords: information theory
coding theory
wireless communication
polar codes
PAC codes
machine learning
deep learning

Abstract: Polar codes are widely used state-of-the-art codes for reliable communication that have recently been included in the $5^{\text{th}}$ generation wireless standards ($5$G). However, there still remains room for design of polar decoders that are both efficient and reliable in the short blocklength regime. Motivated by recent successes of data-driven channel decoders, we introduce a novel $\textbf{ C}$ur${\textbf{RI}}$culum based $\textbf{S}$equential neural decoder for $\textbf{P}$olar codes (CRISP). 
We design a principled curriculum, guided by information-theoretic insights, to train CRISP and show that it outperforms the successive-cancellation (SC) decoder and attains near-optimal reliability performance on the $\text{Polar}(16,32)$ and $\text{Polar}(22,64)$ codes. 
The choice of the proposed curriculum is critical in achieving the accuracy gains of CRISP, as we show by comparing against  other curricula. More notably, CRISP can be readily extended to  Polarization-Adjusted-Convolutional (PAC) codes, where existing SC decoders are significantly less reliable. To the best of our knowledge, CRISP constructs the first data-driven decoder for PAC codes and attains near-optimal performance on the $\text{PAC}(16,32)$ code. 

Under review as a conference paper at ICLR 2023
CRISP: CURRICULUM BASED SEQUENTIAL NEURAL DECODERS FOR POLAR CODE FAMILY
Anonymous authors Paper under double-blind review
ABSTRACT
Polar codes are widely used state-of-the-an codes for reliable communication that have recently been included in the 5th generation wireless standards (5G). However, there remains room for the design of polar decoders that are both efficient and reli- able in the short blocklength regime. Motivated by recent successes of data-driven channel decoders, we introduce novel CurRIculum based Sequential neural de- coder for Polar codes (CRISP)'. We design principled curriculum, guided by ceermatiio-thhorete insights, to train CRISP and show that it outperforms the successive-cancellation (SC) decoder and attains near-optimal reliability perfor- mance on the Polar(32, 16) and Polar(64, 22) codes. The choice of the proposed curriculum is critical in achieving the accuracy gains of CRISP, we show by comparing against other curricula. More notably, CRISP can be readily extended to Saaaaafoonndjussdd-oCooooee
(PAC) codes, where existing SC decoders are significantly less reliable. To the best of our knowledge, CRISP constructs the first data-driven decoder for PAC codes and attains near-optimal performance on the PAC(32, 16) code.
INTRODUCTION
Error-correcting codes (codes) are the backbone of modern digital communication. Codes, composed of (encoder, decoder) pairs, ensure reliable data transmission even under noisy conditions. Since the groundbreaking work of Shannon (1948), several landmark codes have been proposed: Convolutional codes, low-density parity-check (LDPC) codes, Turbo codes, Polar codes, and more recently, (PAC) codes (Richardson & Urbanke, 2008). In particular, polar
Polarization-ddine Adjusted-Convollneee codes, introduced by Arikan (2009), are widely used in practice owing to their reliable performance in the short blocklength regime. A family of variants of polar codes known as PAC codes further improves performance, nearly achieving the fundamental lower bound on the performance of any code finite lengths, albeit higher decoding complexity (Arıkan, 2019). In this paper, we focus on the decoding of these two classes of codes, jointly termed the "Polar code family".
The polar family exhibits several crucial information--heoretie properties; practical finite-length performance, however, depends on high complexity decoders. This search for the design of efficient and reliable decoders for the Polar family is the focus of substantial research in the past decade. (a) Polar codes: The classical successive cancellation (SC) decoder achieves informmtionnttheoree capacity asymptotically, but performs poorly finite blocklengths compared to the optimal maximum posteriori (MAP) decoder (Ankan, 2019). To improve upon the reliability of SC, several polar decoders have been proposed the literature (Sec. 6). One such notable result is the celebrated with-Listttt (SCL) decoder (Tal & Vardy, 2015). SCL improves upon the reliability of SC and approaches that of the MAP with increasing list size (and complexity). (b) PAC codes: The sequential "Fano decoder" (Fano, 1963) allows PAC codes to perform information- theoretically near-optimally: however, the decoding time is long and variable (Rowshan et al., 2020a). Although SC is efficient, ((n log n), its performance with PAC codes is significantly worse than that of the Fano decoder. Several works (Yao et al., 2021; Rowshan et al., 2020b; Zhu et al., 2020; Rowshan & Viterbo, 2021b;a: Sun al., 2021) propose ameliorations; constructing efficient and reliable decoders for the Polar family is an active area of research and of
safe to say that
Source code available the following link.

---

Under review as a conference paper at ICLR 2023
Bit Error Rate
Bit Error Rate
Signal-to to-noose ratio (SNR) [dB]
Training iteration
(a)
Figure I: (a) CRISP achieves near-MAP reliability for Polar(64, 22) code on the AWGN channel. (b) Our proposed curriculum is crucial for the gains CRISP attains over the baselines; details in Sec. 4.
utmost practical interest given the advent of Polar codes in 5G wireless cellular standards. The design of efficient and reliable decoders for the Polar family the focus of this paper.
In this paper, we introduce novel CurRIculum based Sequential neural decoder for Polar code family (CRISP). When the proposed curriculum applied to neural network decoder training, thus trained decoders outperform existing baselines and attain wear reliabilty Polar(64, 22). Polar(32, 16) and PAC(32, 16) codes while maintaining low computational complexity (Figs. 1, 5, Table 1). CRISP builds upon inherent nested hierarchy of polar codes; Polar(n, code subsumes all the codewords lower-rate subcodes Polar(n, i). 1 < i S k (Sec. 2.2). We provide principled curriculum of training on examples from a sequence of sub-codes along this hierarchy, and demonstrate that the proposed curriculum is critical in attaining near-optimal performance (Sec. 4),
Curriculum-learning (CL) is training strategy to train machine learning models, starting with easier subtasks and then gradually increasing the difficulty of the tasks (Wang et al., 2021). 1). (Elman, 1993), seminal work, was one of the first employ CL for supervised tasks, highlighting the importance of "starting small". Later, Bengio et al. (2009) formalized the notion of CL and studied when and why CL. helps the context of visual and language learning (Wu et al., 2020; Wang et al., 2021). In recent years, many empirical studies have shown that CL improves generalization and convergence rate of various models domains such as computer vision (Pentina et al., 2015; Jesson et al., 2017; Morerio et al., 2017: Guo et al., 2018; Wang et al., 2019), natural language processing (Cirik et al., 2016; Platanios et al., 2019), speech processing (Amodei et al., 2016; Gao et al., 2016; 2018), generative modeling (Karras et al., 2017; Wang et al., 2018), and neural program generation (Zaremba & Sutskever, 2014; Reed & De Freitas, 2015). Viewed from this context, our results add decoding of algebraic codes (of the Polar family) to the domain of successes of supervised CL. In summary, we make the following contributions:
We introduce CRISP, novel curriculum- crasee sequential neural decoder for the Polar code family. Guided by information-theored insights, we propose CL-based techniques train CRISP, that are crucial for its superior performance (Sec. 3).
We demonstrate that CRISP attains near-optimal reliability performance on Polar(64, 22) and Polar(32, 16) codes whilst achieving a good throughput (Sec. 4.1 and Sec. 4.2).
Compared to Fano's 's decoder, the CRISP decoder has significantly higher throughput and attains near-MAP reliability for the PAC(32, 16) code. To the best of our knowledge, this is the first learning- based PAC decoder achieve this performance (Sec. 4.4).
2 PROBLEM FORMULATION
In this section we formally define the channel decoding problem and provide background on the Polar code family. Our notation is the following: denote Fuclidean vectors by small bold face letters
2

---

Under review as a conference paper at ICLR 2023
a. y, etc. [n] - 21.,..... .). For m R", m.i _ (m1...., m,-1). (N, In) denotes a standard Gaussian distribution in I". u @ v denotes the bitwise XOR of two binary vectors u, v E {0,1)²
2.1
CHANNEL DECODING
Learn
E (0,1}"
E R
[0.1]
Encoder
Modulation
Channel
Decoder
Noise
MSE loss
Figure 2: Channel decoding problem.
The primary goal of channel decoding is to design efficient decoders that can correctly recover the message bits upon receiving codewords corrupted by noise (Fig. 2). More precisely, let u (uI,..., u4.) E {0. 11 denote a block of informaation/messaee bits that we wish to transmit. An encoder {0, 1} + 13" maps these message bits into a binary codeword æ of length n, ic. modulated via Binary Phase Shift Keying (BPSK), i.c. + 1 2x E I", and are transmitted across the channel. We denote both the modulated and unmodulated codewords as The channel, denoted as Prjx(-1-). corrupts the codeword æ to its noisy version y R". Upon receiving the corrupted codeword, the decoder fo estimates the message bits as ú fa(y). The performance of the decoder is measured using standard error metrics such as Bit-Error-Bee Rate (BER) or Block-Erro Error-Rate (BLER): (E) & (1/k) Σ, Plù; & u.J. whereas BLER & Plu & u].
g(u). The encoded bits
Given encoder with code parameters (n, k) and channel PyJx, the channel decoding problem can be mathematically formulated as:
A E arg min BER(fa).
which joint classification of binary classes. To train the parameters we use the mean- square-error (MSE) loss as differentiable surrogate to the objective in Eq. 1. It is well known in neural networks does not work well
the literature that naively parametrizing fo by and they perform poorly even for small blocklengths like n 16 (Gruber et al., 2017). Hence it essential to use efficient decoding architectures that capitalize on the structure the encoder (Kim et al., 2018b Chen & Ye, 3021). To this end, we focus code family, that comprises two state-of-the-ar codes: Polar codes (Arikan, 2009) and Polarization- Adjusted- Adjusted-Coonvolttinne Convolutional (PAC) codes (Arıaan, 2019). Both these codes closely related and hence we first focus on polar codes in Sec. 2.2. In Sec. 3, we present CRISP, our novel curriculum -ecauuuummmaaiingg based neural decoder to decode polar codes. In Sec. 4.4 we detail PAC codes.
popular class of codes, the Polar
2.2 POLAR CODES
Encoding, Polar codes, introduced in Arikan (2009), were the first codes to be theoretically proven achieve capacity for any binary-input discrete memoryless channel. Their encoding is defined as follows: let (n,, k) be the code parameters with n = 2P, < S n. In order to encode a block of message bits u (ui...., 2x) E {0, 1 we first embed them into a source message vector (0, ........ U1 0, 122 O..... dg O,...)
10"" where m., m2 = O for some I C [n]. Since the message block m contains the information bits u only at the
m A (m..... m.)
and
indices pertaining to /x. the set La called the information set, and its complement 1 the frozen set. For the set /x. we first compute the capacities of the n individual polar bit channels and rank them in their increasing order (Tal & Vardy, 2013). Then In picks the top k out of them. For example, Polar(4, 2) has the ordering mj m2 my m4 and Ig {2, 4), and thus
(0. m2, 0, ma).
Similarly, Polar(8, (8, 4) has my < m2 < my < my < m4 < mg < my mg. I = {4, 6, 7, 8) and
m = (0, 0, 0, m4, 0, me, m7, ma).
3

---

Under review as a conference paper at ICLR 2023
X (m2 + my m Ma. Ma. m2)
Plotkin
4
(M2. m2)
V (m4. m2)
Plotkin
Plotkin
L
4.
0
0/1
0/1
m
1
m
M4
M
M
Mg
(a) Polar encoder
(b) Successive cancellation decoder
Figure 3: Polar(4, 2): (a) Polar encoding via Plotkin tree; (b) Blue arrows indicate the decoding order.
Finally, we obtain the polar codeword æ = Plotkin'Tree(m:) where the mapping ProtkinTroe {0. 13" [0, is given by complete binary tree, known as Plotkin tree (Plotkin, 1960). Fig. 3a details the Plotkin tree for Polar(4,2), Plotkin tree takes the input message block m E 10,1]a 13"h at the leaves and applies the "Plotkin" function at each of its E {0, 1
internal nodes recursively to obtain the codeword Plotkin: {0. 1) x {0, 1) + {0, (0,1) E e N, is defined as
at the root. The function
Plotkin(u, v) (u
For example, in Fig. 3a, starting with the message block m (0, m2, 0, ma) at the leaves, first obtain (lotkin(O, m2) (m2, m2) and Plotkin m4) (m4, m4). Applying the function once more, we obtain the codeword
Plotkin(u, v) (m2 @ m4,17 @ m4, m44, m4).
Decoding. The successive-canccllatioo (SC) algorithm is one the most efficient decoders for polar codes, with a decoding complexity of O(n log n). The basic principle behind the SC algorithm is to sequentially decode one message bit m, at a time according to the conditional log- likeeloldoodd ratio (LLR), L, & (og(Pmm, = y. m ] /IP m = 1ly, mcl)), given the corrupted codeword y and previous decoded bits ni for 4. Fig. 3b illustrates this for the Polar(4, 2) code: for both the message bits my and m4, we compute these conditional LLRs and decode them via ny = 1 [ < 0} and m. 1[ 0}. Given the Plotkin tree structure. these LLRs can be efficiently computed sequentially using depth-first-seacch based algorithm (App. A).
As discussed in Sec. SC achieves the theoretically optimal performance only asymptotically, and its reliability is sub-optimal at finite blocklengths. SC-list (SCL) decoding improves upon its error-correction performance by maintaining list of L candidate paths at any time step and choosing the best among them in the end. In fact, for a reasonably large list size L. SCL achieves MAP performance the cost of increased complexity OLn log n), as highlighted in Table
CRISP: CURRICULUM BASED SEQUENTIAL NEURAL DECODER FOR POLAR FAMILY
We design CRISP, a curriculum-leamingg blaenng---drrd sequential neural decoder for polar codes that strictly outperforms the SC algorithm and existing baselines. CRISP uses a sequential RNN decoder, powered by gated recurrent units (GRU) (Chung al., 2014), decode one bit at time. Instead of standard training techniques, we design a novel curriculum, guided by information the RNN to learn good decoders. Fig. illustrates approach.
iioommation-hheortiic theoretic insights, to train
4

---

Under review as a conference paper at ICLR 2023
ICNN
ICNN
Pakr
Charne
CRISP
h4
MSE
RG
GRU
GRU
GRU
GRU
Polar
Chazel
MSE loss
Hy =
(a) CRISP decoder
(b) Curriculum to train CRISP
Figure 4: CRISP decoder and its training by curriculum-learnnng for Polar(2, 4).
CRISP decoder. We use the Polar(4, 2) code as a guiding example to illustrate our CRISP decoder (Fig. 4a). This code has two message bits (m2, m4) and the message block is m (0. m2, 0. m.). Upon encoding to the polar codeword a E {+1}} 4 and receiving its noisy version y IR,, the decoder estimates the message as vn. = (0, m2g O, m,). Similar to SC, CRISP uses the sequential paradigm of decoding one bit m, at a time by capitalizing on the previous decoded bits myy and y. To that end, parametrize the bit estimate m. conditioned
the past as fully connected neural network (FCNN) that takes the hidden state l; as its input. Here h; denotes the hidden state of the GRU that implicitly encodes this past information (meis y) via GRU's recurrence equation, i.e.
h (RUU,(:-1,, m,,1, y), E (1,2,3,4),
(2)
m,yy. l. m. = (h:), E {4,2),
where 8 denotes the FCNN and GRU parameters jointly. Henceforth we refer to our decoder as either CRISP CRISP,- Note that while the RNN is unrolled for = 4 time steps (Eq. 2).
only estimate bits at k = 2 information indices, i.e. mh and m. (Eq. 3). A key drawback of SC is that a bit error a position
contribute to the future bit errors (> i), and it does not have feedback mechanism to correct these error events. On the other hand, owing to the RNN's recurrence
relation (Eq. 2), CRISP can learn correct these mistakes through the gradient it receives (via backpropagation through time) during training.
Curriculum-trainine of CRISP. Given the decoding architecture of CRISP in Fig. 4a, natural approach to train its parameters via supervised learning is to use a joint MSE loss function for both the bits (mz. m.): MSE(mg, m4)) (fi2((0) m2)² (0) - m2)² However, as we highlight in Sec. 4.1 such an approach learns to fail better decoders than SC and gets stuck at local minima. To
address this issue, we propose a curriculum-lens -earnning based approach to train the RNN parameters.
The key idea behind our curriculum training of CRISP is to decompose the problem of joint estimation of bits (mz, m4 into a sequence of sub-problemn with increasing difficulty: start with learning to estimate only the first bit (mz) and progressively add one new message bit at each curriculum step (vi)) until we estimate the full message block m = (mz m4). We freeze all the non-trainable message bits zero during any curriculum step. In other words, in the first step, freeze the bit m4 and train the decoder only to estimate the bit my (i.e. the subcode corresponding to le = 1):
(m2, m4 = 0) + m (0, m2, 0, Polar,
x
Channel
CRISP
m22-
(4)
We use this trained 0 as an initialization for the next task of estimating both the bits (me ma):
(m2, ma) + (0, m2, 0, m4) Polar
Channel
y
CRISPo (mz my).
(5)
Fig. 4b illustrates this murrculummleemiing approach. We note that the knowledge of decoding my when m4 = 0 (Eq. 4) serves as a good initialization when we learn to decode my for a general m4 (0. 1) (Eq. 5). With such curriculum aided training, we show in Sec. 4.1 (Figs. 1, 5) that the
5

---

Under review as a conference paper at ICLR 2023
CRISP decoder outperforms the existing baselines and attains near-optimal performance for variety of blocklengths and codes. We interpret this in Sec. 4.3. We defer the training details to App. E.
Left-to-Rige (L2R) curriculum for Polar A). For a general Polar(n, k) code, similar curriculum to train CRISP Denoting the index set by 15 = {d1, ................................ ig} S [x]] in the increasing order of indices i1 < ... ix. curriculum is given by: Train @ on m4, - Train 0 on (m,, m + + Train 9 on (m,,..... m,, ). We term this curriculum Left-to-Riig (L2R). The anti-curriculum R2L refers progressively training in the decreasing order of the indices in 1g-
follow
4
MAIN RESULTS
In this section, we present numerical results for the CRISP decoder on the Polar code family.
4.1 AWGN CHANNEL
Bin Ervor Rate
Bin Ervor Rate
Signal-ta to noise ratio (SNR) [dB]
Signal to noise ratio (SNR) [cIB]
Training step
(a) (31ar(32, 16)
(b) PAC 16)
(c) PAC(3211)) Progressive train
Figure 5: CRISP outperforms baselines and attains wear-MAP performance for Polar(32, 16) and PAC(32, 16) codes on the AWGN channel.
Data generation. The input message {0, 13* is randomly drawn uniformly from the boolean hypercube and encoded as a polar codeword æ E {+1}". The classical additive white Gaussian noise (AWGN) channel. y = +-+- 2,
(0, o² In generates the training/test data (3/ u) for the decoder. The signal-to-noise ratio, i.e. SNR = - log a² characterizes the noise level in the channel. Here we fix the channel be AWGN in all our experiments, as per the standard convention (Kim et al., 2018b), and refer to App. D) for additional results on fading and t-distributed channels. App. E details the training procedure. Once trained, we use the CRISP models for comparison against the baselines.
Baselines. The optimal channel decoder is the MAP estimator: ú arg max (0. 1]a P(uly), whose complexity grows exponentially in and is computationally infeasible. Given this, we compare CRISP decoder with the SCL (Tal & Vardy, 2015), which has near-MAP performance for large L, along with the classical SC. Among learning- buaning-based decoders, we choose the state-of-the-an art Ceural-Suucesssiv-Cann Cannelllaionnn (NSC) as baseline (Doan et al., 2018). While the original NSC uses a sub-optimal training procedure with SC probabilities as the target, we consider an improved version with end-to-end training (Fig. for fair comparison. We also include the performance of CRISP trained directly without the curriculum. We also compare with the curriculum training procedure of Lee et al. (2020) via the C2N scheme (Sec. 5, Fig. 11). All these baselines have the same number of parameters as CRISP.
Fig. Ia highlights that the CRISP decoder outperforms the existing baselines and attains near-MAP MAP performance over a wide range of SNRs for the Polar(644 (a,,r66,,22) 22) code. Fig. lb illustrates the mechanism behind these gains at OdB: the curriculum- -uided CRISP slowly improves upon the overall BER (over the 22 bits) during the training and eventually achieves much better performance than SC and other baselines. In contrast, the decoder trained from scratch makes a big initial gain but gets stuck at local minima and only achieves marginal improvement over SC. We observe similar trend for Polar(32, 16) code in Fig. 5a, where CRISP achieves near-MAP performance. We posit that aided by good curriculum, CRISP avoids getting stuck at bad local minima and converges to better minima in the optimization landscape. App. D highlights similar reliability gains for non-AW Aon- channels, other blocklengths, and rates. App. illustrates the ablation analysis

---

CRISP_CNT (Ours) Under review as a conference paper at ICLR 2023
4.2
RELIABILIT--OMPLEXITY COMPARISON
Table I: Throughput and reliability comparison of various decoders Polar(n, kt.
Throughput (in Mbps)
Gap to SCL, I.=22 (in dB)
Decoder
(32,
16)
(64, 22)
(32, 16)
(64, 22)
GPU
CPU
GPU
CPU
SC
0.17
27
0.08
15
0.80
0.40
FastSC
N/A
47
N/A
40
0.80
0.40
SCL, L=4
0.01
8.5
0.02
6.27
0.05
0.10
FastSCL, L=4
N/A
30
N/A
24
0.05
0.10
SCL, L=32 (MAP)
5e-3
0.81
2c-3
0.60
0.00
0.00
FastSCI., I=32
N/A
7.7
N/A
5.5
0.00
0.00
NSC
N/A
N/A
32.6
0.02
N/A
0.35
@RISP_GRU (Ours)
80
0.04
38.7
0.02
0.15
0.20
250
0.02
133
0.13
0.15
0.20
CRISP_GRU No curriculum
80
0.04
38.7
0.02
0.60
0.35
In the previous section, we demonstrated that CRISP achieves better reliability than the baselines. Here analyze these gains through the lens of decoding complexity. To quantitatively compare the complexities of these decoders, we evaluate their throughput on single GTX 1080 Ti GPU as well CPU (Intel 17-6850K, 12 threads). For the GPU version, we use our implementation of SC/SCL owing to the lack of publicly available implementations. On the other hand, for the CPU column we use an optimized multithreaded implementation of SC/FastSC, SCL/FastSCL (Léonardon et al. (2019)) in C++ by Cassagne et al. (2019). As Table highlights. CRISP exploits the GPUs' inherent optimization towards NNs to achieve excellent throughput, whilst achieving near-SCI. BER performance. We also design CRISP_CNN (App. C.2), that attains better throughput than CRISP _R_,, while maintaining gains in BER. We posit that further improvement in throughput can be realized using techniques like pruning and knowledge distillation. This beyond the scope of this paper and an important and separate direction of future research. We refer App. F for further discussion. Note that use BER= 10-3 to compute the gap to SCL (Figs. la, 5a)
ID-CNN decoder trained similar to CRISP_GRR
4.3 INTERPRETATION
L2R curriulum
R2L curriculum
No curriculum
Learning Difficulty
Curriculum Step
(a) L2R vs. R2L for decoding
(b) Evolution of learning difficulty
Figure 6: L2R vs. R2L: (a) Bit estimates evolve more smoothly under L2R than R2L for Polar(4, 4). (b) Learning difficulty increases more gracefully for L2R than R2L for Polar(64, 22).
7

---

Under review as a conference paper at ICLR 2023
This section describes why L2R is a better curriculum than others. To this end, we first claim that learning to decode uncorrupted codewords (y = z) is critical to learning a reliable decoder. This claim follows from the following key observation: while training our model (sequential or block) at specific SNR, we observe that whenever our model reaches SC or better performance, its BER on uncorrupted codewords, aka the noiseless BER, drops to zero very early in the training (App. B, Fig. 7a). On the other hand, when the model gets stuck at bad minima even after a lot of training, its noiseless BER is high (Fig. 7b). Hence, without loss of generality, we focus on the setting y = æ. Under this noiseless scenario, we analyze how the optimal bit decoding rules evolve for different curricula. In particular, we focus on the least reliable bits as they contribute the largest to noiseless BER (Fig. 8a and Fig. 8b).
For the Polar [, 4) code. Fig. 6a illustrates how the optimal rule evolves for its least reliable bit my. In this case, the MAP decoding rule for my is: mh = x1 212244444 Under the 1.2R curriculum, we arrive at this expression via 21 - 21 - 21222 - 214227374 whereas R2L. follows 1 1 1 + 23 This highlights that L,2R reaches the optimal rule more gracefully by learning to include one coordinate z; at a time while this change for R2L (and no-curriculum) is abrupt, making it harder to learn. Fig. 9 illustrates a similar evolution for the remaining bits (mz, My, m4).
More concretely, we define the notion of learning difficulty for bit: the number of bits multiplied in its optimal decoding rule. This metric roughly captures the number of operations a model has to learn at any curriculum step. Fig. 6b illustrates how it evolves over the L2R and R2L curricula for the least reliable bit in Polar(64, 22). If we take the maximum learning difficulty over all bits, we obtain similar plot (Fig. 10). Note that in both the plots, the jumps in learning difficulty are larger for R2L, thus indicating a harder transfer than L2R, where it increases smoothly (at most one bit per step).
4.4 PAC CODES
A recent breakthrough work Arıkan (2019) introduces a new class of codes called Polarization- ddjusted-Convolutiin (PAC) codes that match the fundamental lower bound on the performance of any code under the MAP decoding at finite-lengths (Moradi et al., 2020). The motivating idea behind PAC codes is overcome two key limitations of polar codes at finite blocklengths: the poor minimum distance properties of the code and the sub-optimality of SC compared to the MAP (Mondelli et al., 2014). This is addressed by adding a convolutional outer code, with an appropriate indexing JR. before polar encoding to improve the distance properties of the resulting code. More formally, the message block u E {0, 1} is embedded into the source vector m E {0. 1)" according to the Reed-Muller (RM) indices ((RM) compute the Hamming weights of integers 0, n 1 and choose the top ht Now we encode the message m via a rate-1 convolutional code, i... v c E {0, 1)"h + U, = -, cym,-j, for some 1D convolutional kernel E {0, 1).. Finally we obtain the PAC codeword by polar encoding v: Plotkin Tree(v).
PAC codes can be decoded using the classical Fano algorithm (Fano, 1963), a sequential decoding algorithm that uses backtracking. Coupled with the Fano decoder, PAC codes achieve impressive results outperforming polar codes (with SCL decoder) and matching the finite-length capacity bound (Polyanskiy al., 2010). However, the Fano decoder has significant drawbacks like variable running time, large time complexity at low-SNRs (Rowshan et al., 2020b), and sensitivity to the choice of hyperparameters (Moradi, 2020). To overcome these issues, several non-learning techniques, such as stack/list decoding, adaptive path metrics, etc., have been proposed in the literature (Yao et al., 2021; Zhu et al., 2020; Rowshan & Viterbo, 2021b;a; Sun et al., 2021). In contrast, we design a sincculum-learning based CRISP decoder for PAC codes trained directly from the data. We use the same 1.2R curriculum to decode PAC codes.
Fig. 5b highlights that the CRISP decoder achieves MAP performance for the PAC(32, 16) code. While Fano decoding achieves similar reliability, it is inherently non- non-parallelizable In contrast, CRISP allows for batching, and achieves higher throughput, as highlighted in Table 2. Here we measure the throughput of Fano (Rowshan et al., 2020a) at SNR = 1 dB. We note that the existing implementation of Fano is not supported on GPUs These preliminary results suggest that curriculum- based training holds a great promise for designing efficient PAC decoders, especially for longer blocklengths, which is interesting topic of future research (App. D.2).
8

---

Under review as a conference paper at ICLR 2023
Table 2: Throughput and reliability comparison of various decoders on PAC
Throughput (in Mbps)
Decoder
Gap to SCL, L=128 (in dB)
GPU
CPU
SC
N/A
27
1.0
SCL, L=128
N/A
0.02
0.0
Fano
N/A
4e-3
0.1
CRISP_ _RUU (Ours)
80
0.03
0.4
CRISP CNN (Ours)
250
0.15
0.4
CRISP GRU No curriculum
80
0.03
0.8
INFORMATION THEORY GUIDED CURRICULA
In Sec. 4, we demonstrated the superiority of 1.2R curriculum over other schemes. Here we introduce an alternate curriculum, Noisy-to-Clean (N2C), that slightly bests the I.2R, inspired by the polarization property of polar codes. The key idea behind N2C curriculum is to capitalize the polar index set 4.. Recall that the set 1g is obtained by ranking the n polar bit channels (under SC decoding) in the increasing order of their reliabilities (from noisy to clean) and choosing the top k indices. Formally, given 4 = {ir1. 4.2..... } S [n]] in the increasing order of reliabilities, our N2C curriculum given by: Train 9 on m Train 9 on (fi.. m4.2) ... - Train on ( m...). For both the sequential and block decoders, we observe that N2C is the best curriculum and we have N2C x 1.2R > C2N ss R2L (Fig. 11). This ordering is consistent with our interpretation in Sec. 4.3 of how the learning difficulty evolves over a curriculum (Fig. 12). For both N2C and L2R, the learning difficulty evolves smoothly but is abrupt for C2N and R2L, thus making transfer harder in these curricula. Note that the C2N curriculum refers to progressively training on subcodes of Polar(n, k): Polar(n, 1) .... > Polar(n, k) (Lee et al., 2020).
RELATED WORK
To address the sub-optimality of SC finite lengths, a popular technique is to use list decoding (Tal & Vardy, 2015; Saaassoukas-Simmminn et al., 2015), aided by cyclic redundancy checks (CRC) (Li et al., 2012: Niu & Chen, 201 2a; Miloslavskaya & Trifonov, 2014). Several alternate decoding methods have also been proposed such as stack decoding (Niu & Chen, 2012b; Trifonov, 2018), belief propagation decoding (Yuan Parhi, 2014; Elkelesh al., 2018). Deep learning for communication (Qin et al., 2019; Kim et al., 2020) has been an active field in the recent years and has seen success in many problems including the design of neural decoders for existing linear codes (Nachmani et al., 2016; O'shea & Hoydis, 2017; Lugosch & Gross, 2017; Vasić et al., 2018: Liang et al., 2018; Bennatan et al., 2018; Jiang et al., 2019a; Nachmani Wolf, 2019; Buchberger et al., 2020; He et al., 2020), and jointly learning channel encoder-decoder pairs (O'Shea et al., 2016; Kim et al., 2018a; Jiang et al., 2019b; Makkuva et al., 2021; Jamali al., 2021; Chahine et al., 2021a;b).
Earlier works designing neural polar decoders (Gross et al., 2020) used off-the-shelf neural architectures. These were only able to decode codes small blocklength (S 16) (Lyu et al., 2018; Cao et al., 2020). Later works augmented belief propagation decoding (Xu et al., 2018; Doan et al., 2019), with neural components and improved performance. In Cammerer et al. (2017a) 7a) and Doan al. (2018), the authors replace sub-components of the existing SC decoder with NNs scale decoding to longer lengths. However, these methods fail to give reasonable reliability gains compared SC. In contrast, we use curriculum learning train neural decoders, and show non-trivial gains over SC performance. Our approach is closest to that of Lee et al. (2020), who consider curriculum training of polar decoder via the C2N scheme, upon which we strictly improve.
CONCLUSION
We introduce novel curriculum based neural decoder, CRISP, that attains near-optimal reliability the Polar code family in the short blocklength regime. Extending our results to medium blocklengths 1000-1000) and codes outside the Polar family are interesting future directions.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Dario Amodei, Sundaram Ananthanarayanan. Rishita Anubhai, Jingliang Bai, Eric Battenberg, Carl Case, Jared Casper, Bryan Catanzaro, Qiang Cheng, Guoliang Chen, al. Deep speech 2: End-to- end speech recognition in english and mandarin. In International conference on machine learning. pp. 173-182, PMLR, 2016.
Sajid Anwar, Kyuyeon Hwang, and Wonyong Sung. Structured pruning of deep convolutional neural networks, 2015. URL https:::p//.......t. htappp:://riiiii /arxivaivvv/v./////v//aaeaaaaiia org/ /ww.aa/.... 1112. 08571.
Erdal Arikan. Channel polarization: method for constructing
codes for
symmetric binary-input memoryless channels. IEEE Transactions on Information Theory, 55
(7):355--3073, Jul 2009. ISSN 0018-9448. doi: 00.1109/ii.22092222213333 URL http:
//dx.dol org/ 10. 1119/19III1.
Erdal Arıkan. From sequential decoding to channel polarization and back again. arXiv preprint arXiv:1908.09544 2019.
Alexios Maatsoukka-Stiimming Mani Bastani Parizi, and Andreas Burg. Llr-based successive cancellation list decoding of polar codes. IEEE transactions on signal processing, 63(19):5165- 5179, 2015.
Yoshua Bengio. Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pp. 41-48, 2009,
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. IERE, 2018.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, llya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020. URL https: //arxiv. orgg abs/
wass/2055 2005.0000000 14165.
Andreas Buchberger, Christian Häger. Henry D Pfister, Laurent Schmalen, and Alexandre Graell Amat. Pruning neural belief propagation decoders. 2020 IEEE International Symposiun on Information Theory (ISIT), pp. 338-342 IEEE, 2020.
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 communi- cations conference, pp. 1-6. IEEE, 2017a
Sebastian Cammerer, Benedikt Leible, Matthias Stahl, Jakob Hoydis, and Stephan ten Brink. Combin- ing belief propagation and successive cancellation list decoding of polar codes on a gpu platform. In 2017 IEEE international conference on acoustics, speech and signal processing (ICASSP), pp. 3664-3668. IEEE, 2017b.
Zhiwei Cao, Hongfei Zhu, Yuping Zhao, and Dou Li. Learning denoise and decode: A novel residual neural network decoder for polar codes. In 2020 IEEE 92nd Vehicular Technology Conference (VTC2020-Fall pp- 1-6. IEEE, 2020.
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. Aff3et: A fast forward error correction toolbox! Elsevier SoftwareX, 10:100345, October 2019.
Karl Chahine, Yihan Jiang, Pooja Nuti, Hyeji Kim, and Joonyoung Cho. Turbo autoencoder with trainable interleaver. arXiv preprint arXiv:2 1010 2021a.
Karl Chahine, Nanyang Ye, and Hyeji Kim. Deepic: Coding for interference channels via deep learning. arXiv preprint arXiv:2 088000088 2021b.
10

---

Under review as a conference paper at ICLR 2023
Xiangyu Chen and Min Ye. Cyclically equivariant neural decoders for cyclic codes. arXiv preprint arXiv:210S.05540, 2021.
Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks sequence modeling. arXiv preprint arXiv: 2014.
Volkan Cirik, Eduard Hovy, and Louis-Philippe Moreney. Visualizing and understanding curriculum learning for long short-term memory networks. arXiv preprint arXiv:1611.0222 2016.
Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding, 2018. URL https: httpss//aaxxiv.oog
abs/18100 04805.
Nghia Doan, Seyyed Ali Hashemi, and Warren J Gross. Neural successive cancellation decoding of polar codes. In 2018 IEEE 19th international workshop signal processing advances in wireless communications (SPAWC), pp. 1-5, IEEE, 2018.
Nghia Doan, Seyyed Ali Hashemi, Elie Ngomseu Mambou, Thibaud Tonnellier, and Warren J Gross. Neural belief propagation decoding of cre-polar concatenated codes. In ICC 2019-2019 IEEE International Conference on Communications (ICC), pp. 1-6. IEEE, 2019.
Ahmed Elkelesh, Moustafa Ebada, Sebastian Cammerer, and Stephan Ten Brink. Belief propagation list decoding of polar codes. IEEE Communications Letters, 1236:115361 2018.
Jeffrey L Elman. Learning and development in neural networks: The importance of starting small.
Cognition, 48(1):71-99, 1993.
Robert Fano. A heuristic discussion of probabilistic decoding. IEEE Transactions on Information Theory, 92))644 74, 1963.
Tian Gao, Jun Du Li-Rong Dai, and Chin-Hui Lec. Snr-based progressive learning of deep neural network for speech enhancement. In INTERSPEECH, pp. 3713-3717, 2016.
Tian Gao, Jun Du, Li-Rong Dai, and Chin-Hui Lee. Densely connected progressive learning for Istm-based speech enhancement. In 2018 IEEE International Conference Acousties, Speech and Signal Processing (ICASSP), pp. 5054-5058, IEEE, 2018.
Warren Gross, Nghia Doan, Elie Ngomseu Mambou, and Seyyed Ali Hashemi. Deep learning techniques for decoding polar codes. Machine learning for future wireless communications, pp. 287-301, 2020.
Tobias Gruber, Sebastian Cammerer, Jakob Hoydis, and Stephan ten Brink. On deep learning-based channel decoding. In 2017 51 Annual Conference Information Sciences and Systems (CISS), pp. 1-6. IEEE, 2017.
Sheng Guo, Weilin Huang, Haozhi Zhang, Chenfan Zhuang. Dengke Dong, Matthew Scott, and Dinglong Huang. Curriculumnet: Weakly supervised learning from large-scale web images. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 135-150, 2018.
Xu Han, Rongke Liu, Zhanxian Liu, and Ling Zhao. Successive-cancelllttee list decoder of polar codes based on gpu. In 2017 3rd IEEE International Conference on Computer and Communications (ICCC), pp. 2065-2070. IEEE, 2017.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, 2015. URL https::t///. http///axvvvv/. otg/abs aataab//1122 /11.//51...0 03385.
Yunfeng He, Jing Zhang, Shi Jin, Chao-Kai Wen, and Geoffrey Ye Li. Model-driven dnn decoder for turbo codes: Design, simulation, and experimental results. JEEE Transactions on Communications, 68(10):6127-6140 2020.
Dan Hendryeks and Kevin Gimpel. Gaussian error linear units (gelus), 2016. URL https: //arxiv.org abs/1608 /06.66666..1 08415.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network, 2015. URL https: //t/xivvvvv////////v/////////vv .rgg abs /1003. 02531.
11

---

Under review as a conference paper at ICLR 2023
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9(8): 1735-1780, 1997. doi: 10.11622neco.19977 199.
Mohammad Vahid Jamali, Hamid Saber, Homayoon Hatami, and Jung Hyun Bac. Productae: Towards training larger channel codes based neural product codes. arXiv preprint 1rXiv:2110004466 2021.
Andrew Jesson, Nicolas Guizard, Sina Hamidi Ghalchjegh, Damien Goblot, Florian Soudan, and Nicolas Chapados. Cased: currieulum adaptive sampling for extreme data imbalance. In Interna- tional Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 639-646. Springer, 2017.
Yihan Jiang, Sreeram Kannan, Hyeji Kim, Sewoong Oh, Himanshu Asnani, and Pramod Viswanath. Deepturbo: Deep turbo decoder. In 2019 IEEK 20th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), pp- 1-5. IEEE, 2019a.
Yihan Jiang, Hyeji Kim, Himanshu Asnani, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath. Turbo autoencoder: Deep learning based channel codes for point-to-point communication channels. In Advances in Neural Information Processing Systems, pp. 7768-276,, 2019b.
Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu. Tinybert: Distilling bert for natural language understanding, 2019. URL httpps://arxtt org/abs/////oooooo......o 909. 10351.
Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen. Progressive growing of gans for improved quality, stability, and variation. arXiv preprint arXiv:1710. 2017.
Hyeji Kim, Yihan Jiang, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath. Deepcode: Feedback codes via deep learning. Advances in neural information processing systems, 31, 2018a.
Hyeji Kim, Yihan Jiang, Ranvir Rana, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath. Communication algorithms via deep learning. arXiv preprini arXiv: /805.0977 2018b.
Hyeji Kim, Sewoong Oh, and Pramod Viswanath. Physical layer communication via deep learning.
IEEE Journal on Selected Areas in Information Theory, 2020.
Alex Lamb, Anirudh Goyal, Ying Zhang. Saizheng Zhang, Aaron Courville, and Yoshua Bengio. Professor forcing: A new algorithm for training recurrent networks, 2016. URL https:// arxiv. org/ abs /10...61.... 09038.
Hyunjae Lee, Fun Young Seo, Hyosang Ju, and Sang-Hyo Kim. On training neural network decoders of rate compatible polar codes via transfer learning. Entropy, 22(5):496, 2020.
Mathieu Léonardon, Adrien Cassagne, Camille Leroux, Christophe Jégo, Louis-Philippe Hamelin, and Yvon Savaria. Fast and flexible software polar list decoders. Journal of Signal Processing Systems, 91(8):937-952, 2019.
Bin Li, Hui Shen, and David Tse. An adaptive successive cancellation list decoder for polar codes with cyclic redundancy check. IEEE communications letters, 16(12):004420447, 2012.
Fei Liang, Cong Shen, and Feng Wu. An iterative bp-enn architecture for channel decoding. IEEE Journal of Selected Topics in Signal Processing, 12(1):144-159, 2018.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts, 2016. URL https://arxile org/ aas//////// / 608.... 03983.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint
1rXiv:1711.05101, 2017.
Loren Lugosch and Warren Gross. Neural offset min-sum decoding. In 2017 IEEE International Symposium Information Theeory (ISIT), pp. 1361-1365. IEFE, 2017.
Wei Lyu, Zhaoyang Zhang, Chunxu Jiao, Kangjian Qin, and Huazi Zhang. Performance evaluation of channel decoding with deep neural networks. In 2018 IEEE International Conference on Communications (ICC), pp. 1-6. IEBE, 2018
12

---

Under review as a conference paper at ICLR 2023
Ashok V Makkuva, Xiyang Liu, Mohammad Vahid Jamali, Hessam Mahdavifar, Sewoong Oh, and Pramod Viswanath. Ko codes: inventing nonlinear encoding and decoding for reliable wireless communication via deep-learning In International Conference on Machine Learning, pp. 7368- 7378. PMLR, 2021.
Vera Miloslavskaya and Peter Trifonov. Sequential decoding of polar codes. IEEE Communications Letters, 18(7) 2014.
Marco Mondelli, Hamed Hassani, and Rüdiger Urbanke. From polar reed-muller codes: technique to improve the finite-length performance. IEEE Transactions on Communications, 62 (9):3084-309,, 2014.
Mohsen Moradi. On the metric and computation of pac codes. arXiv preprint arX1v:2012.05511 2020.
Mohsen Moradi, Amir Mozammel, Kangjian Qin, and Erdal Arikan. Performance and complexity of sequential decoding pac codes. arXiv preprint arXiv:2012.04994 2020.
Pietro Morerio, Jacopo Cavazza, Riccardo Volpi, René Vidal, and Vittorio Murino. Curriculum dropout. In Proceedings of the IEEE International Conference on Compuler Vision, pp. 3544-3552, 2017.
Eliya Nachmani and Lior Wolf. Hyper-graphhnetworkk decoders for block codes. Advances in Neural Information Processing Systems, 32:2329-2339, 2019.
Eliya Nachmani, Yair Be' Be'ery, and David Burshtein. Learning to decode linear codes using deep learning. 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 341-346. IEEE, 2016.
Kai Niu and Kai Chen. Cre-aided decoding of polar codes. IEEE communications letters, 16(10): 1668-161 1661-671111 1, 2012a.
Kai Niu and Kai Chen. Stack decoding of polar codes. Electronics letters, 48(12):695-6677,000
Timothy J O'eaa Kiran Karra, and Charles Clancy. Learning to communicate: Channel auto-
encoders, domain specific regularizers, and attention. In 2016 IEEE International Symposium Signal Processing and Information Technology (ISSPIT), pp. 223-228. IEEE, 2016.
Timothy O'shea and Jakob Hoydis. An introduction to deep learning for the physical layer. IEEE Transactions on Cognitive Communications and Networking, 3(4):563-575, 2017.
Anastasia Pentina, Viktoriia Sharmanska, and Christoph Lampert. Curriculum learning of multiple tasks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5492-5500, 2015.
Emmanouil Antonios Platanios, Otilia Stretcu, Graham Neubig, Barnabas Poczos, and Tom M Mitchell. Competence-based curriculum learning for neural machine translation. arXiv preprint arXiv:1903.090: 09848, 2019.
M. Plotkin. Binary codes with specified minimum distance. IRE Transactions on Information Theory, 6(4):445-450, 1960.
Yury Polyanskiy, H Vincent Poor, and Sergio Verdú. Channel coding rate in the finite blocklength regime. IEEE Transactions on Information Theory, 56(5):2307-239,, 2010.
Zhijin Qin, Hao Ye, Geoffrey Ye Li, and Biing-Wwang Fred Juang. Deep learning in physical layer communications. IEEE Wireless Communications, 26(2):93 2019.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9 2019.
Scott Reed and Nando De Freitas. Neural programmerr-nteepreeer.. arXiv preprint drXiv:1511.06279, 2015.
Tom Richardson and Ruediger Urbanke. Modern coding theory. Cambridge University Press, 2008
13

---

Under review as a conference paper at ICLR 2023
Mohammad Rowshan and Emanuele Viterbo. On convolutional precoding in pac codes. In 2021 IEEE Globecom Workshops (GC Wkshps), pp. 1-6. IEEE, 2021a.
Mohammad Rowshan and Emanuele Viterbo, List viterbi decoding of pac codes. IEEE Transactions Vehicular Technology, 70(3):2428 2435, 2021b.
Mohammad Rowshan, Andreas Burg. and Emanuele Viterbo. Complexity-efficienl fano decoding of -arzzuation-djusseedd convolutional (pac) codes. In 2020 International Symposium on Information T'heory and Its Applications (ISITA), pp. 200-204. IEEE, 2020a.
Mohammad Rowshan, Andreas Burg, and Emanuele Viterbo. Polarization-aajuste convolutional (pac) codes: Fano decoding vs list decoding. arXiv preprint arXiv:2002.06800, 2020b.
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter, 2019. URL httttp:://axxx..zrg//eaa 01108.
Claude E Shannon. A mathematical theory communication. The Bell system technical journal, 27
(3):379 423, 1948.
He Sun, Emanuele Viterbo, and Rongke Liu. Optimized rate-profiling for pac codes. arXiv preprint arXiv:2106.04074, 2021.
Ido Tal and Alexander Vardy. How to construct polar codes. IEEE Trans. Inf. Theory, 59(10): 2013.
Ido Tal and Alexander Vardy, List decoding of polar codes. IEEE Transactions on Information Theory, 61)):222332 2015.
Peter Trifonov. A score function for sequential decoding of polar codes. 2018 IEEE International Symposium Information Theory (ISIT), pp. 1470-1474, 2018. doi: 10.1 S.W.SITT.20118843755555
Bane Vasié, Xin Xiao, and Shu Lin. Learning to decode Idpc codes with finite-alphabet message passing. 2018 Information Theory and Applications Workshop (ITA), pp. 1-9. IEEE, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pp. 5998-6008, 2017.
Xin Wang, Yudong Chen, and Wenwu Zhu. A survey on curriculum learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Yifan Wang, Federico Perazzi, Brian McWilliams, Alexander Sorkine- Olga Sorkine- Hornung, and Christopher Schroers. fully progressive approach to single-image super-resolution. In Proceedings of the IEEE conference computer vision and pattern recognition workshops, pp.
864-873, 2018
Yiru Wang, Weihao Gan, Jie Yang, Wei Wu, and Junjie Yan. Dynamic curriculum learning for imbalanced data classification. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 5017-5026, 2019.
Ziheng Wang. Jeremy Wohlwend, and Tao Lei. Structured pruning large language models. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP). Association for Computational Linguistics, 2020. doi: 10. 10t533311/220emmllpp 496. URL https: / doi. org/ /0. (653822v18822200 emn emmnl-mmin .466.
Xiaoxia Wu, Ethan Dyer, and Behnam Neyshabur. When do curricula work? arXiv preprint arXiv:2012.03107, 2020.
Weihong Xu, Xiaohu You, Chuan Zhang, and Yair Be' Be'ery. Polar decoding on sparse graphs with deep learning. In 2018 52nd Asilomar Conference Signals, Systems, and Computers, pp. 599 IEEE, 2018.
599-60993 6033
Hanwen Yao, Arman Fazeli, and Alexander Vardy. List decoding of arıkan's 's pac codes. Entropy, 23 (7):841, 2021.
14

---

Under review as a conference paper at ICLR 2023
Bo Yuan and Keshab K. Parhi. Early stopping criteria for energy-efficient low-latency belief- propagation polar code decoders. IEEE transactions on signal processing, 62(24):6499-6553 6506, 2014.
Wojeiech Zaremba and Ilya Sutskever. Learning to execute. arXiv preprint arXiv: 1410.4611. 2014.
Hongfei Zhu, Zhiwei Cao, Yuping Zhao, Dou Li, and Yanjun Yang. Fast list decoders for polarization- adjusted convolutional (pac) codes. arXiv preprint 2rX1::20/2.04425, 2020.
15

---

Under review as a conference paper at ICLR 2023
A SUCCESSIVE CANCELLATION DECODER
Here we detail the cancsssiveecancellation (SC) algorithm for decoding polar codes. As motivating example, let's consider the Polar(2, 2) code. Let the two information bits be denoted by u and v, where v E {0,1}, The codeword E {0, 1 is given by = (II, be the corresponding noisy codeword received by the decoder. First we convert the received y into a vector of log- likelihood-ration (LLRs), Ly E R, which contains the soft-information about coded bits 1 and 22 i.e.
(u @ v, v). Let y E R²
Wi 0 = 0] Plyn 1] log
Plyz D2
0]
by = (2) 1 A llog
(Lg
E R..
Plyz
Once we have the soft-information about the codeword æ, the goal is to now obtain the same for the message bits u and v. compute the LLRs for these information bits, SC uses the following principle: first, compute the soft-information for the left bit u to estimate ú. Use the decoded ú to compute the soft-information for the right bit v and decode it. More concretely, we compute the L.R for the bit as:
+ 100+ + e cly
Lu = LSE(L,)) (
log
ER,
3
where LSE(a, b) A log(1 + eath))((e" e²) for a, E R. The expression in Eq. 6 follows from the fact that u = (u G v) @ 21 G æ2 and hence the soft-information T,, can be accordingly derived from that of x1 and æ2, i.e. Ly. Now we estimate the bit as á 1 { LT < 0}. Assuming that we
know the bit u â, we observe that the codeword x (â @ v, v) can be viewed as two-repitition of v. Hence its LLR L, is given by
Lu 100
(1) --1)) + L E..
Finally we decode the bit ē 1iL < <0}. To summarize, given the LLR vector Ly we first compute the LLR for the bit Lu. using Eq. 6 and decode it. Utilizing the decoded version â, we compute the LLR L, according to Eq. 7 and decode
For more generic Polar(n, ke), the underlying principle is the same: to decode polar codeword (u @ v. v), first decode the left child u and utilize this to decode the right child v. This principle is recursively applied at each node of the Plotkin tree until we reach the leaves of the tree where the decoding is trivial. In view of this principle, the SC algorithm for Polar 4), illustrated in Fig. 3b, can be mathematically expressed as (in the sequence of steps):
y E R.
(2) L (1) Ly 1.::0 ( E R., (2) I R2. Lu (LSE(L)) (1) (3)) LSE(L
Ly = (L,
frozen bit
my O,
L = LSE(L,)) (1) (1) ()) + LSE(L (2) _I(") E R.
m = 1[L2 < 0} E 10.1].
à (1i2, m2) E (0,
L. (I,)), (1)) (-1)a + (I (3) (,,,,,,)
- E R.?
frozen bit
mg 0,
L ( + ( ER. (1)
m4 1[L+ < 0} E 10.1).
In Fig. 3b, the above equations are succinetly represented by two set of arrows: the black solid arrows represent the flow of soft-informatic from the parent node to the children whereas the green dotted arrows represent the flow of the decoded bit information from the children to the parent. We note that we use simpler min-sum approximation for the function LSE that is often used in practice, i.c.
LSF((, b) ss min([a), ( (b))sign a, b E R.
16

---

Under review as a conference paper at ICLR 2023
0.25
Bit Error Rate
0.20
Bit Error Rate
0.3
0.15
0.2
0.10
0.05
0.1
0.00
25
500
75
100
125
150
200
400
600
800
1000
1200
Training iterations
Training iterations
(a) Noiseless BER gocs to zero when the model is
(b) Noiseless BER is high when the model is worse than SC
better than SC
Figure 7: Evolution of training BER at 1dB and noiseless BER for CRISP.
B INTERPRETATION
As discussed in Sec. 4.3, observe that whenever decoder reaches SC or better performance tually when training at a specific SNR, its BER (over all the bits) on uncorrupted codewords, noiseless BER, drops early on in the training. Fig. 7a illustrates this for Polar(32, 16). Conversely, if the model gets stuck at BER worse than that of SC, then we observe that its noiseless BER is also stuck at non-zero value. This is highlighted in Fig. 7b for Polar(64. 32). In particular, reliable bits contribute the most to the noiseless BER, while a majority of the cleaner bits have zero individual BER (Fig. 8a). Viewed from this context, focus the noiseless scenario, i.e. y a.
notice that the least
As a motivating example, we first consider the Polar(4, 4) code. Let m = (m1, m2, mg, m,) E {0, 1)at be the block of message bits and {0, be the codeword. Hence under the L2R curriculum, the subcodes evolve as
k 1 my + (m,, 0,0,0)
(m1, 0,0,0).
* k = 2 (m,, m2) + (m,: m2, 0, - (m1 ) m2, m2, 0,0),
k = 3 (mi, m2; m3) + (m,, m2, m3, 0) + x (mi @ m2 @ ma, m2, ma, 0). k 4: (m1, m2, M3. m4) + (m1, m2, my, m4) + x (m1 m2 my + m4. m2 t
m4, my O m4, m4).
Correspondingly, their optimal bit decoding rules under the MAP evolve as k = 1::30
(m,. 0, + m.
k = 2: I (mL ① m2, m2, 0,0) + (mi m2) = (α) + 12, x2).
k = 3:
(m² m2 @ ma, m2, m3, 0) - (m², (22, mss) (I1 @ 2 T2, (mm @ mm ma @ m4, m2 ① m4, mg m,4, ma) (mh m2, ma, mi4) ① v4, 22 34, 33 @ T4, 24).
k = 4:9
(x) ① 22 ( 33
Similarly, we can compute the subcodes and their corresponding decision rules under the R2L curriculum, Fig. illustrates this evolution for both 1.2R and R2I.. For the least reliable bit mi, we observe that the L2R curriculum reaches the optimal rule more gracefully by including one coordinate I; at a time while this change for R2L (and no-curriculum) is abrupt, making it harder to learn. We observe the same trend for other bits m2, my and m,- Note that for Polar(4, 4). the reliability order my < m2 = my < m. and hence the L2R curriculum is same as N2C and R2L is same as C2N.
For general Polar(n, k), can likewise compute the optimal MAP rules using the fact that the mapping PlotkinTree: : {0, 1)" > {0, 1)" is its own inverse, i.c. x Plotkin Tree(m) = m Plotkin Tree(a:).
17

---

Under review as a conference paper at ICLR 2023
To concretely compare different curricula, define the notion of learning difficulty for bit: the number of codeword bits multiplied its optimal decoding rule. This metric roughly captures the number of multiplicatton operations model has to learn at any curriculum step. For example, for Polar(4, 4), the learning difficulty for my evloves as - 2 + 3 + for the 1,2R curriculum and 0
+ 4 for the R2L curriculum. Fig. 10 illustrates the evolution of learning difficulty (taking maximum over all bits) for Polar(32, 16) and Polar (64, 22) codes. We observe here that the jumps the learning difficulty are larger for R2L, thus indicating a harder transfer than L2R, where it increases smoothly (at most one bit per step).
Fig. 12 highlights similar phenomenon for Polar(64, 22) for L2R, R2L, N2C and C2N curricula. We observe that the learning difficulties of the L2R and N2C curricula evolve smoothly while that of R2L. and C2N are abrupt. Correspondingly, their final BER reliability performance follows the order N2C Ru L2R < R2L z C2N (Fig. 11).
0.4
Bit Error Rate
Block Elroo Rate
0.3
0.2
0.1
0.0
50
100
150
200
250
Training iterations
Decoding method
(a) Bitwise BER for clean and noisy bits
(b) Bitwise contribution to the total BLER
Figure 8: Error analysis for Polar (64, 32) (a) Noiseless BER for the two least reliable bits gets stuck 0.5 whereas it converges 0 for the two most reliable bits, (b) Contribution of each bit (conditioned on no previous errors) to the BLERR
36.3
06
09
09
09
0 0
1.2R curriculum
(b) R2L curriculum
Figure 9: Evolution of the MAP decoding rules for L2R and R2L for Polar(4, 4). Dotted lines indicate new coded bits being introduced into the decoding rule at each curriculum step.
C ABLATION STUDIES
Recall that CRISP decoder consists of the sequential RNN (512-dim hidden state) trained with the L2R curriculum. To understand the contribution of each of these components to its gains over SC, did the following ablation experiments for Polar(64, 22) code.
18

---

Under review as a conference paper at ICLR 2023
Learning Difficulty
Learning Difficulty
Training iterations
Training iterations
(a) Polar(32, 16)
(b) Polar(64, 22)
Figure 10: Evolution of the learning difficulty for L2R and R2L.
16-1
10-1
Block Error Rate
Bit Error Rate
20-
10-1
Signal-to-noise ratio (SNR) [dB]
Signal-to-noise ratio (SNR) [dB]
(a) Polar(32, 16)
(b) Polar(64, 22)
Figure 11: Information theory guided curricula N2C and C2N are marginally better than the L2R and R2L schemes respectively.
C.1 EFFECT OF MODEL SIZE
We fix the decoder be GRU and consider different model sizes via the hidden state size h E {256, 512), and different curricula among (L2R, R2L, Without curriculum (w/o C)). Fig. 13a demonstrates that the accuracy gains of the L2R curriculum are more pronounced for smaller models (h = 256). On the other hand, we observe minimal reliabilty gains for 1,2R with large models (h 512). We also tried other sequential architectures such as L.TMSs (Hochreiter & Schmidhuber, 1997) and Transformers (Radford al., 2019), but found GRUs to be the best (App. D).
C.2 SEQUENTIAL VS. BLOCK DECODING
We note that the sequential RNN architecture for CRISP is inspired in part by the sequential SC algorithm. Notwithstanding, we also designed block decoders that estimate all the information bits in one shot given y. We choose 1D Convolutional Neural Networks (CNNs) to parametrize this block decoder. Similar to sequential decoders, curriculum learning; in particular, the 1.2R scheme works the best for block decoding in achieving near-MAP reliability.
Fig. 14b compares RNNs and CNNs in terms of BLER for Polar 64, 22) with L2R and R2L curricula. We observe that RNN-based decoders (CRISP) are more reliable in terms of BLER than CNNs; in contrast, RNNs and CNNs achieve similar BER performance (Fig. 14a). Further, we observe that the patterns corresponding to bitwise contribution to the total BLER for the RNN model resemble that SC-List, as opposed to CNN models (Fig. 8b). We show the evolution of validation BER for CNN training in Fig. 15. We see that the C2N curriculum performs worse than the N2C curriculum.
19

---

Under review as a conference paper at ICLR 2023
Leaming Difficulty
Learning Difficulty
Training iterations
Training iterations
(a) Noisiest bit
(b) Maximum over all bits
Figure 12: Evolution of learning bit difficulty for different curricula for Polar(64, 22).
16-4
Bit Error Rate
Bit Error Rate
10-4
20005
230000
34030
Signal-to hignal-tonoiss toisois ratio (SNR) [dB]
Training iteration
(a)
(b)
Ablation plots: (a) Choosing the right curriculum is critical when model size smaller, (b) The number of iterations train CRISP each subcode using the L2R/N2C currieulum critical to the final performance achieved.
Figure 13:
D ADDITIONAL RESULTS
We present our additional results on the Polar code family with various decoding architectures such as CNNs and transformers, with BLER reliability, and for longer blocklengths (n = 128). Recall that the CRISP decoder the GRU-based RNN (Fig. 4a) trained with the L2R curriculum.
D. ADDITIONAL RESULTS FOR POLAR CODES
D.1.1 ROBUSTNESS NON-AWGN NOISE
In this section evaluate CRISP trained on AWGN on non-AWGN settings. We test CRISP on Rayleigh fading channel, and T--distribuedd noise. As shown in Fig. 16, CRISP retains its gains when tested on a Rayleigh fading channel. Further, as demonstrated in Fig. 17, CRISP very robust to T-distributed noise and marginally outperforms SCL at higher SNRs.
D.1.2 CRISP FOR CRC-POLAR CODES
In practice, polar codes with successive cancellation list decoding is used in conjunction with cyclic redundancy check (CRC) outer code. The message u E {0, 1 is encoded by a systematic cyclic code of rate Am to obtain a vector m E {0, 1}* We obtain the codewords via the normal polar m. CRISP can be used to decode such CRC-Polar codes by considering
A.
encoding procedure the input to the polar code block. As shown in Fig. 18, CRISP achieves near-M near-MAP reliability when CRCs of length 3 and 8 used for Polar (6, 22) code.
20

---

Under review as a conference paper at ICLR 2023
20"
10-
Block Error Rate
Bit Error Rate
10-1
20-4
10-3
10.
-2
Signal-to-noise ratio (SNR) [dB]
Signal-to-noise ratio (SNR) [dB]
(b)
Figure 14: a) CNN decoder achieves near-MAP BER performance with L2R curriculum. b) CRISP achieves near-MAP BLER for Polar(64, 22). CNN is slightly worse
Bit Error Rate
Training itcration
Figure 15: L2R curriculum helps CNN to achieve near-optimal reliability
D.1.3 SCALING TO LARGER CODES
Curriculum training be used train larger codes and obtain gains over naive training methods. However, we observed that our models were only able to achieve reliability marginally better than SC. As shown in Fig. 21, CRISP performs similar SC decoding on the Polar( (128, 22) code. We believe that it is possible to close the gap with MAP with more training tricks.
1.1.4 RESULTS WITH TRANSFORMERS
We also experimented with transformer- based architecures Vaswani et al. (2017) for our decoder. In particular, we tried an autoregressive transformer-decoder network (similar to GPT (Brown et al., 2020) that does sequential decoding) and the transformer-encoder network (similar to BERT (Devlin et al.. 2018) that does block decoding), Preliminary results indicate that these transformer-baa based models are less reliable compared to RNNs and CNNs (Fig. 19). In addition, these models take a greater number of iterations (E) to train on each of the subcodes than RNNs and CNNs during curriculum training. Transformer training is sensitive to architectural and hyperparameter choices and is computationally expensive. We believe that with the right training tricks, transformer based models can be used to decode larger codes. This ongoing work.
D.2 ADDITIONAL RESULTS FOR PAC CODES
CRISP maintains its good performance even in block error rate, as we show in Fig. 20b. Fig. 20a compares RNNs and CNNs in terms of BER for PAC(32, 16) code with I.2R and R2L. curricula.
21

---

Under review as a conference paper at ICLR 2023
Polari22,54
10.
(a) Polar(64, 22)
(b) Polar 16)
Figure 16: CRISP achieves good reliability on Rayleigh fading channels
Polar22.644 T-dstribtton y
Paar 54,201 Tulrr
6c L-32 GRIP
500
16-1
(a) P6lar(64, 22)
(b) Polar(32, 16)
Figure 17: CRISP matches SCL reliability on T-distributed channels
We observe that while both RNNs and CNNs outperform SC, RNNs achieve slightly better BER reliability than CNNs. On the other hand, Fig. 20b highlights that CNNs achieves an SC-like BLER.
E EXPERIMENTAL DETAILS
We provide our code at the following link.
Data generation. Note that for any Polar(n, k)) or PAC(n, k)) code, the input message m is chosen uniformly at random from {0. 1}A.. We simulate this by drawing &s i.i.d. Bernoulli random variables with probability 1/2. We follow a similar procedure
generate a batch of message blocks (in (0. 1) Bx*) with batch size B, both during training and inference. For the AWGN channel, the batch noise (in R BBny accordingly generated by drawing i.i.d. Gaussian samples from (V ??).
Sarame-araaeeees. For training our models (both sequential and block decoders), we use AdamW optimizer (Loshchilov Hutter, 2017) with a learning rate of 10-3, At each curriculum step, corresponding training subcode, we choose the SNR corresponding to which the optimal decoder for that subcode has BER in the range of 10 ~ 10-1 (Kim et al., 2018b). This ensures that a significant portion of training examples lie close the decision boundary. It is well known that using a large batch size is essential to train a reliable decoder (Jiang et al., 2019a); we use batch size of 4096 or 8192.
22

---

Under review as a conference paper at ICLR 2023
1015
10
10
10-1
16-0
(a) Polar(64, 22)
(b) Polar 16)
Figure 18: CRISP performs well on CRC-Polar code
10-1
10
Bit Error Rate
Bit Eiror Rate
1014
30
Signal-to-nen tonnose ratio (SNR) [dB]
Signal-to-noke tooisse ratio (SNR) [dB]
(a) GPT-based architecture (sequential decoding)
(b) BERT-based architecture (block decoding)
Figure 19: Transformer performance on Polar (32, 16).
E. SEQUENTIAL DECODERS
We present the architectures and training details for our sequential decoders. We consider two popular choices for our sequential models: RNNs and GPT. We also note that it is standard practice to use teucher forcing to train sequential models (Lamb et al., 2016): during training, as opposed to feeding the model prediction m, an input for the next time step, the ground truth message bit m, is provided as an input to the model instead (Fig, 4a). Student forcing refers to using the same m, as an input.
E.I.I RNNS
Architecture. We use a 2-layer GRU with hidden state size of 512. The output each timestep is obtained through a fully connected layer (as shown in Fig. 4a). The network has 2.5M and 600K parameters for block lengths 64 and 32. As shown in Figure 22, 2-layer-LSTM and 3-layer-GHt GRU models achieve similar performance. We choose 2-layer GRU for our experiments since it allows for faster training and has fewer parameters.
Training. We use the teacher forcing mechanism to train our models. We found that teacher forcing gives a better final performance in terms of both BER and BLER, whereas student forcing only provides gains in the BER reliability (Fig. 23). We observed that student forced training achieved sub- optimal performance for larger block lengths. Empirically we observed that the number of iterations spent on training each intermediate subeode of the curriculum is not critical to the performance of the final model (Fig. 13b). To train CRISP for Polar(64,22), we use the following curriculum schedule: Train each subcode for 2000 iterations, and finally train the full code until convergence
23

---

Under review as a conference paper at ICLR 2023
1011
Block Error Rate
Bit Error Rate
1019
10"4
10"
10-1
10"
2
Signal-to-noise ratio (SNR) [dB]
Signal-to-noise ratio (SNR) [dB]
(a) BERs PAC 16)
(b) BLERs PAC 16)
Figure 20: With correct choice of curriculum, CNNs match the BER performance of CRISP on
PAC(32,16). However, they are sub-optimal in BLER.
10-1
10-2
Block Error Rate
Bit Error Rate
16-1
Signal-to-noiss ratio (SNR) [dB]
Signal-to-noise ratio (SNR) [dB]
(a) BERs (12ar(128,22) 22)
(b) BLERs Polar (12a, 22)
Figure 21: CRISP matches SC reliabilty Polar(128, 22).
with decaying learning rate. This training schedule required 13-15 hours of training on GTX 1080Ti GPU.
E.1.2 GPT
Architecture.
The model consists of 6 transformer blocks with masked self-attention and GELU activation. The multiheaded attention unit has 8 heads in each block, and embedding/hidden size of 64 is used throughout the network. The output vectors of the final transformer block are passed through linear layer to estimate each bit sequentially. The model has 350K parameters for blocklength 32.
Training. For training the GPT-based transformer, we use a teacher forcing mechanism. Here, we observed that the decoder takes a greater number of iterations (40, 000) to train on each of the subcodes than RNNs and CNNs (2, 000 10, 000) during curriculum training of Polar(32, 16). For a fixed batch size, GPT also takes significantly longer to train (12 hours) compared to CNNs (3 hours) and RNNs (4 hours) on GTX 1080 Ti GPU.
E.2
BLOCK DECODERS
E.2.1 CNNS
Architecture. For block decoding using Convolutional Neural Networks (CNNs), we use a ResNet- like architecture (He et al., 2015), with the primary difference being the use of ID convolutions instead
24

---

Under review as a conference paper at ICLR 2023
Bit Error Rate
Block Error Rate
10-1
10-3
Signal-to-noise ratio (SNR) [dB]
Signal-to-noise ratio (SNR) [dB]
(a)
(b)
Figure 22: Polar(64, 22): LSTMs and GRUs achieve similar reliability.
10
10-1
Block Error Rate
Bit Error Rate
40
10-
Signal-to-nore to-no ratio (SNR) [dB]
Signal-to toiise ratio (SNR) [dB]
Figure 23: Training CRISP using student forcing results in sub-optimal BLER.
of 2D. The model has 10 ID-convolutional layers with residual connections skipping every two consecutive layers. Each convolutional layer has 64 channels, which are flattened at the penultimate layer and fed as an input to fully- fully-connected neural network with one hidden layer. We use the GELU (Hendrycks & Gimpel, 2016) activation function throughout the network. The model has 2.5M parameters for blocklength 64.
Training. We train the CNN model for 5, 000 iterations for each intermediate subcode of the curriculum. In the last step of the curriculum, we train it for 100, 000 iterations with a decaying cosine annealing schedule for the learning rate (Loshchilov & Hutter, 2016).
E.2.2 BERT
The model consists of transformer blocks with unmasked self-attention and GELU activation. In each block, the multiheaded attention unit has 8 heads, and embedding/hidden size of 64 is used throughout the network. The output vectors of the final transformer block are passed through a linear layer to estimate all the bits in one shot. The model has 350K parameters for blocklength 32.
Architecture.
Training. We train this model each intermediate subcode for around 10, 000 - 20, 000 steps. Thus the BERT-based decoder achieves better reliability than its GPT counterpart despite fewer training iterations (Fig. 19).
25

---

Under review as a conference paper at ICLR 2023
F RELIABILITY-COMPEEIII COMPARISON
Two important metrics in evaluating a decoding algorithm are the decoding reliability and complexity. In this paper, we focus on optimizing the BER performance; the main goal of our paper to design a curriculum based decoder for Polar and PAC codes that can achieve near-optimal reliability performance as opposed to the current data-driven approaches that only match the SC. In Sec. 4.2, we demonstrated that CRISP achieves excellent inference throughput on GPUs. We also see that the decoding complexity of CRISP can be improved with a hardware-aware neural architecture.
We believe that neural decoders, coupled with the recent advances in distillation Sanh et al. (2019) and pruning of neural networks Hinton al. (2015); Wang et (2020); Anwar et (2015) far larger than ours (E.g., 11M for BERT vs. 2.5M for CRISP), can achieve even better runtimes. For instance, TinyBERT (Jiao et (2019)) uses knowledge distillation to learn a model 9.4x faster on inference compared to the parent BERT. With these improvements (a separate line of research), can have fair comparison with SCL decoders, which are the outcome of a decade of innovations in efficient implementations (e.g.. FastSCL) the CRISP decoder is only one of the first of its kind in designing a reliable neural decoder for Polar and Polar-like codes. Coupled with efficient GPU implementations, which are optimized for vector-matrix multiplications, and the aforementioned compression techniques, we believe neural decoders offer a great potential for fast and reliable channel decoding.
is important to note that inference throughput is hardware and software dependant. In Table 1, we report throughput numbers of the optimized C++ multithreaded implementation of SC/SCL decoding on CPU using the aff3ct toolbox (Cassagne et al. (2019)). There has been progress in developing GPU implementations of SCL (Cammerer et al. (2017b); Han al. (2017)). Since could not find publicly available implementations of these works, we report throughput numbers of our implementation.
26


Reviews:
[{"review_id": "uyPBrVSZCK", "reviewer": "Reviewer_aVwC", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper introduces a method to train a neural network to decode polar codes and related codes (PAC, polar with CRC). The main trick is that the training is gradual: first train to decode the first information bit, assuming all other information bits are frozen to 0, then start from the previous point and train assuming all but the second information bit is frozen to zero, etc. The resulting decoder is better than SC and worse than SCL in terms of bit error rate, but better than SCL in terms of throughput.", "summary_of_the_review": "The result seems to be a good fit for ICLR", "strength_and_weaknesses": "I am not an expert in neural networks, so my assessment here is far from authoritative.  To me, the main strength is showing a method of decoding which has some intuition behind it. That is, the decoding is done sequentially, like in SC decoding of polar codes. Another strength is that the authors seem to have found a complexity/error rate point that other algorithms cannot match. A weakness of this method is that it does not seem to work to moderate length codes, and only works for short codes. To their credit, the authors state this outright.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "AoQ-NY5Skrx", "reviewer": "Reviewer_JMRY", "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": "This paper proposes a curriculum-based sequential neural decoder for Polar codes. It is shown that CRISP, trained based on information-theoretic insights, outperforms the SC decoder achieving near-optimal error-correcting performance.", "summary_of_the_review": "Please see `Strength` section.", "strength_and_weaknesses": "Strength\n- It's an interesting application of curriculum learning to me. The rationale behind why the authors introduced curriculum learning for their purposes totally makes sense (feedback mechanism to overcome the key drawback of successive cancellation). I liked the key idea behind the curriculum training of CRISP. I feel it aligns well with what is happening when decoding the Polar codes.\n- It is shown from the evaluation results that CRISP achieves better error-correcting performances compared to the baselines.", "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": "23x5bscPa7b", "reviewer": "Reviewer_FDX2", "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": "================================================================= \n\n[Summary] \n\nThis paper presents an inductively biased curriculum-learning based training technique that makes use of a nesting hierarchy of polar codes to improve BER results through experimentation.\n\n================================================================= \n", "summary_of_the_review": "The usage of polar code nesting hierarchy for curriculum-learning based training strategy is a simple yet intriguing notion, however, it does not appear to make a significant impact, similar to the many kinds of data-driven channel decoders.\n", "strength_and_weaknesses": "================================================================= \n\n[Main Strengths] \n\nThe authors' extensive descriptions of the backgrounds, as well as the important implementation codes, are included in the anonymous repo, which is the paper's main strength.\n\n================================================================= \n\n[Main Weaknesses] \n\nThe study's main shortcoming is that, while the performance improvements are intriguing, they do not appear to have a major impact, similar to the many flavors of data-driven channel decoders. I encourage the authors to make additional improvements, notably for the experiments mentioned in Section 4, which demonstrate how the CRISP handles non-Gaussian channels (e.g., memory channels) well with nonlinear GRU designs as compared to standard model-driven decoders.\n\n================================================================= \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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-YBYWGPNorn", "reviewer": "Reviewer_1zGS", "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": "The authors propose a decoding method for polar-like codes. The proposed approach is based on machine learning techniques, and novel training approach introduced by the authors. The authors show that the proposed method provides performance close to that of the successive cancellation list decoder.", "summary_of_the_review": "The paper is well-written, but the paper lacks proper comparison, and does not seem to provide any improvement with respect to state of the art.", "strength_and_weaknesses": "The paper is very well written, and the proposed training method seems to be novel, although I am not an expert in machine learning.\n\nThe main problem with the paper is that it lacks proper complexity comparison with state-of-the-art decoding techniques for polar codes, and throughput results presented in Table 1 are quite disappointing. In particular, this table implies that the authors obtained decoder throughput for (32,16) code 13008 b/s for SCL(L=4) and 533333 b/s for CRISP.  However, it was shown in  [L2019] that SCL decoder with larger list size L=8 for much longer code (128,64) provides single-threaded throughput more that 3.5 Mb/s.  The discussion after Table 1 suggests, that the obtained results correspond to a multi-threaded implementation, so actual throughput gap is even worse.\n\nPlease observe that the SCL decoder is not the best one in terms of throughput.  Much more efficient decoding algorithms are known, e.g. FastSCL, sequential and trellis-based decoding algorithms [A2019,T2018,T2020]. The authors do not provide performance and complexity comparison with these techniques.  Lack of comparison with sequential decoders is particularly disappointing, since the authors themselves introduced a sequential-type decoder.  \n\nThe authors use throughput of a software decoder as a complexity benchmark. This approach is quite unreliable and difficult to interpret, since it depends on software engineering skills and hardware platform features.  The reviewer suggests to use the number of arithmetic operations performed by the decoder as a benchmark. This would enable comparison with other published results.\n\nThe authors use non-standard notation (k,n) to denote the parameters of polar codes. The standard coding theory notation is (n,k), where n is code length and k is code dimension.\n\n[L2019] Léonardon, M., Cassagne, A., Leroux, C. et al. Fast and Flexible Software Polar List Decoders. J Sign Process Syst 91, 937–952 (2019).\n[A2019] M. H. Ardakani, M. Hanif, M. Ardakani and C. Tellambura, \"Fast Successive-Cancellation-Based Decoders of Polar Codes,\" in IEEE Transactions on Communications, vol. 67, no. 7, pp. 4562-4574, July 2019\n[T2018] P. Trifonov, \"A Score Function for Sequential Decoding of Polar Codes,\" 2018 IEEE International Symposium on Information Theory (ISIT), 2018, pp. 1470-1474\n[T2020] P. Trifonov, \"Recursive Trellis Decoding Techniques of Polar Codes,\" 2020 IEEE International Symposium on Information Theory (ISIT), 2020, pp. 407-412", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject