# On the Efficiency of Polar-like Decoding for Symmetric Codes

Kirill Ivanov, Rüdiger L. Urbanke K. Ivanov and R. L. Urbanke are with the
School of Computer and Communication Sciences, EPFL, Switzerland e-mail:
<EMAIL_ADDRESS>rudiger.urbanke@epfl.ch).Part of the results of this
paper is published at the ISITA 2020 [1]

###### Abstract

The recently introduced polar codes constitute a breakthrough in coding theory
due to their capacity-achieving property. This goes hand in hand with a
quasilinear construction, encoding, and successive cancellation list decoding
procedures based on the Plotkin construction. The decoding algorithm can be
applied with slight modifications to Reed-Muller or eBCH codes, that both
achieve the capacity of erasure channels, although the list size needed for
good performance grows too fast to make the decoding practical even for
moderate block lengths.

The key ingredient for proving the capacity-achieving property of Reed-Muller
and eBCH codes is their group of symmetries. It can be plugged into the
concept of Plotkin decomposition to design various permutation decoding
algorithms. Although such techniques allow to outperform the straightforward
polar-like decoding, the complexity stays impractical.

In this paper, we show that although invariance under a large automorphism
group is valuable in a theoretical sense, it also ensures that the list size
needed for good performance grows exponentially. We further establish the
bounds that arise if we sacrifice some of the symmetries. Although the
theoretical analysis of the list decoding algorithm remains an open problem,
our result provides an insight into the factors that impact the decoding
complexity.

###### Index Terms:

Reed-Muller codes, Polar codes, List decoding, Permutation decoding.

##  I Introduction

Reed-Muller (RM) codes and extended BCH codes are very well known in classical
coding theory and have been studied for decades[2]. It was recently proved
that these codes achieve the capacity of the binary erasure channel under ML
decoding [3]. The equivalent question for general channels is still open and
so is low-complexity (near) maximum likelihood (ML) decoding.

The remarkable structural property of Reed-Muller codes is that they can be
represented as Plotkin concatenation of two smaller Reed-Muller codes. Dumer
and Shabunov [4] proposed to perform this decomposition recursively and keep
the list of most likely codewords at each stage, which brings ML performance
for any rate, but the list size grows exponentially with the code length.
Another idea that first appeared in [4] and further studied in [5, 6, 7] is to
use the large automorphism group of RM codes and consider multiple codeword
permutations, which improves over the list algorithm. In case of eBCH codes,
the list size for near-ML decoding is significantly larger [8].

Polar codes [9] achieve the capacity of an arbitrary binary memoryless
symmetric (BMS) channel. Contrary to RM codes, successive cancellation list
(SCL) decoding [10] (which works similarly to Dumer-Shabunov decoder) with
small list size is sufficient for near-ML performance, but the hardware
implementation is challenging due to the path sorting operation [11].
Permutation decoding works without the sorting operation and therefore
provides an alternative. However, it requires a certain symmetry in the code,
which is lacking for the standard constructions of polar codes as well as
polar-like codes such as CRC-aided polar codes [10] and polar subcodes [12].
In [13] and [14], the authors construct polar codes, which in some cases
perform better under permutation decoding than polar codes with list decoding.
The construction of polar subcodes taylored for permutation decoding remains
an open problem.

In this paper, we investigate the achievable properties of codes with certain
symmetries. We establish the connection with the required list size for near-
ML decoding and demonstrate that in case of RM and eBCH codes the automorphism
group implies the exponential growth. We also investigate what happens if
fewer symmetries are present and discover that a similar result holds even in
this relaxed setting. A method to construct ‘optimal’ partially symmetric
monomial codes, which might be of some use for short lengths, is also
presented. 111The source code to reproduce the bounds and code constructions
is available at https://github.com/kir1994/PartSymCodes

##  II Background

We use $[n]$ to denote the set $\\{0,\dots,n-1\\}$. $\mathbb{F}_{q}$ denotes
the finite field with $q$ elements, and $\mathbb{F}_{q}^{m}$ is the
$m$-dimensional vector space over $\mathbb{F}_{q}$. Note that we can consider
the vector space $\mathbb{F}_{q}^{m}$ as the finite field $\mathbb{F}_{q^{m}}$
and vice versa. $\mathbb{F}_{q}^{*}=\mathbb{F}_{q}\setminus\\{0\\}$ is the
multiplicative group of $\mathbb{F}_{q}$. Bold letters are used for matrices
and vectors, e.g., $\mathbf{A}$ and $\mathbf{b}$. Given a vector
$\mathbf{v}=(v_{0},\dots,v_{m-1}),v_{i}\in\mathbb{F}_{2}$, we consider it as
an integer $v=\sum_{i=0}^{m-1}v_{i}2^{i}$ where needed. For
$\mathbf{c}=(c_{0},\dots,c_{n-1})$, we define
$\mathbf{c}_{a}^{b}=(c_{a},\dots,c_{b}),0\leq a\leq b<n$. $R(\mathcal{C})$
denotes the rate of a binary linear code $\mathcal{C}$.

###  II-A Boolean functions

Let $\\{x_{0},\ldots,x_{m-1}\\}$ be a collection of $m$ variables taking their
values in $\mathbb{F}_{2}$, let
$\mathbf{v}=(v_{0},\ldots,v_{m-1})\in\mathbb{F}_{2}^{m}$ be any binary
$m$-tuple, and let $\operatorname{wt}(\cdot)$ denote the Hamming weight. Then,

$x^{\mathbf{v}}=\prod_{i=0}^{m-1}x_{i}^{v_{i}}$

denotes a monomial of degree $\operatorname{wt}(\mathbf{v})$.

A function $f(\mathbf{x})=f(x_{0},\dots,x_{m-1}):\
\mathbb{F}_{2}^{m}\to\mathbb{F}_{2}$ is called Boolean. Any such function can
be uniquely represented as an $m$-variate polynomial:

$f(x_{0},\dots,x_{m-1})=\sum_{\mathbf{v}\in\mathbb{F}_{2}^{m}}a_{\mathbf{v}}x^{\mathbf{v}},$

where $a_{\mathbf{v}}\in\\{0,1\\}$, which is also called its algebraic normal
form (ANF) [15]. Its evaluation vector
$\operatorname{ev}(f(\mathbf{x}))\in\mathbb{F}_{2}^{2^{m}}$ is obtained by
evaluating $f$ at all points $\boldsymbol{\alpha}_{i}$ of
$\mathbb{F}_{2}^{m}$. Note that any length-$2^{m}$ binary vector $\mathbf{c}$
can be considered as an evaluation vector of some function $f$. For the rest
of the paper, we assume the standard bit ordering of points, i.e.,
$\boldsymbol{\alpha}_{i}$ being the binary expansion of integer $i$.

###  II-B Monomial and polynomial codes

Consider a binary linear $(n=2^{m},k,d)$ code $\mathcal{C}$ with generator
matrix $\mathbf{G}$. Its generating set is given by

$M_{\mathcal{C}}=\\{f_{i},0\leq
i<k|\operatorname{ev}(f_{i})=\mathbf{G}_{i,*}\\},$

where $\mathbf{G}_{i,*}$ are rows of $G$. The code $\mathcal{C}$ is called
monomial if there exists $M_{\mathcal{C}}$ that contains only monomials (which
can be obtained by applying the Gaussian elimination on the coefficients of
$f_{i}$’s) and polynomial otherwise. The minimum distance of a monomial code
can be calculated [16, Proposition 3] as

$d_{min}(\mathcal{C})=2^{m-\max_{x^{\mathbf{v}}\in
M_{\mathcal{C}}}\operatorname{wt}(\mathbf{v})}.$ (1)

Consider the matrix $\mathbf{A}_{m}=\left(\begin{array}[]{cc}1&1\\\
0&1\end{array}\right)^{\otimes m}$, where $\otimes m$ denotes an $m$-fold
Kronecker product of a matrix with itself. Observe that $\left(1\ 1\right)$
and $\left(0\ 1\right)$ are the evaluations over $\mathbb{F}_{2}$ of the
constant monomial $1$ and the monomial $x_{0}$, respectively, and from the
induction on $m$ it follows that the $v$-th row of $\mathbf{A}_{m}$ is an
evaluation vector over $\mathbb{F}_{2}^{m}$ of the monomial $x^{\mathbf{v}}$.
Hence, the encoding for monomial codes can be performed as
$\mathbf{c}=\mathbf{u}\mathbf{A}_{m}$, where $u_{v}=1$ if $x^{\mathbf{v}}\in
M_{\mathcal{C}}$ and $u_{v}=0$ otherwise.

####  II-B1 Polar codes

A $(n=2^{m},k)$ polar code [9] with the set of frozen symbols $\mathcal{F}$ is
a binary linear block code generated by rows with indices
$i\in[n]\setminus\mathcal{F}$ of the matrix $\mathbf{A}_{m}$. Our definition
of polar codes is slightly different from conventional, which uses the matrix
$\left(\begin{array}[]{cc}1&0\\\ 1&1\end{array}\right)^{\otimes m}$, but as
already noted in [16], both definitions are equivalent and ours simplifies the
polynomial notation. For given binary memoryless symmetric (BMS) channel $W$,
the set $\mathcal{F}$ contains the $n-k$ indices with largest bit error
probability under successive cancellation decoding. Polar codes are monomial
with the generating set
$M_{\mathcal{F}}=\\{x^{\mathbf{i}}|i\notin\mathcal{F}\\}$.

####  II-B2 Reed-Muller codes

A Reed-Muller code [17, 18] RM$(r,m)$ of order $r$ is spanned by the
evaluations of $m$-variate monomials of degree at most $r$. The RM$(r,m)$ code
has length $2^{m}$, dimension $\sum_{i=0}^{r}\binom{m}{i}$ and minimum
distance $2^{m-r}$. RM codes are monomial with the generating set
$M_{r,m}=\\{x^{\mathbf{v}}|\operatorname{wt}(\mathbf{v})\leq r\\}$.

####  II-B3 Extended BCH codes

A $(2^{m}-1,k,d\geq\delta)$ primitive narrow-sense BCH code [2] with design
distance $\delta$ has a parity check matrix $H$ with elements

$H_{j,i}=\alpha_{i}^{j},0\leq i<2^{m},0\leq j<\delta-1,$

where $\alpha_{i}$ are distinct elements of $\mathbb{F}_{2^{m}}^{*}$. An
extended code is formed by adding an overall parity check symbol.

###  II-C Derivatives

The derivative in direction $\mathbf{b}$ of the Boolean function $f$ is
defined as

$(D_{\mathbf{b}}f)(\mathbf{x})=f(\mathbf{x}+\mathbf{b})-f(\mathbf{x}).$

In case of monomials, this expression can be written as

$D_{\mathbf{b}}x^{\mathbf{v}}=(\mathbf{x}+\mathbf{b})^{\mathbf{v}}-x^{\mathbf{v}}=\prod_{i=0}^{m-1}(x_{i}+b_{i})^{v_{i}}-\prod_{i=0}^{m-1}x_{i}^{v_{i}}.$

In case of $\operatorname{wt}(\mathbf{b})=1$, i.e., when
$\mathbf{b}=\mathbf{e}_{i}$, the directional derivative coincides with the
partial derivative $\frac{\partial f}{\partial x_{i}}$.

The derivative in direction $\mathbf{b}$ of the code $\mathcal{C}$ is a binary
linear code with generating set

$M_{\mathcal{C}\to\mathbf{b}}=\left\\{D_{\mathbf{b}}f_{i}|f_{i}\in
M_{\mathcal{C}}\right\\}.$ (2)

By definition, $D_{\mathbf{b}}f_{i}$ has identical values at coordinates
$\mathbf{x}$ and $\mathbf{x}+\mathbf{b}$ for all
$\mathbf{x}\in\mathbb{F}_{2}^{m}$, so we can discard the coordinates
$\mathbf{x}+\mathbf{b}$ and obtain the
$(n^{(\mathbf{b})}=2^{m-1},k^{(\mathbf{b})}=\dim
M_{\mathcal{C}\to\mathbf{b}},d^{(\mathbf{b})})$ code
$\mathcal{C}^{(\mathbf{b})}$.

The partial derivatives of Boolean functions are inherently connected with the
Plotkin construction. Namely, any function $f$ can be decomposed as

$\displaystyle f(x_{0},\dots,x_{m-1})$ $\displaystyle=g(x_{1},\dots,x_{m-1})$
$\displaystyle+x_{0}h(x_{1},\dots,x_{m-1}),$

where $g(x_{1},\dots,x_{m-1})$ takes identical values for $x_{0}=0$ and
$x_{0}=1$, whereas $x_{0}h(x_{1},\dots,x_{m-1})$ is only nonzero when
$x_{0}=1$.

Consider a permutation $\pi$ on $[2^{m}]$ and define its action on the Boolean
function $f$ as another Boolean function $g$ obtained by permuting its
evaluation vector, namely $\pi(f)=g:\
\operatorname{ev}(g)=(f(\pi(\boldsymbol{\alpha}_{0})),\dots,f(\pi(\boldsymbol{\alpha}_{2^{m}-1})))$.
The set of permutations that leave the code $\mathcal{C}$ invariant, i.e., map
its codewords to other codewords, forms the automorphism group of a code
denoted by $\operatorname{Aut}(\mathcal{C})$. Note that if
$\operatorname{Aut}(\mathcal{C})$ contains the permutation
$\mathbf{x}\to\mathbf{x}+\mathbf{b}$, then $D_{\mathbf{b}}\mathcal{C}$ is a
subcode of $\mathcal{C}$ (assuming we don’t discard the coordinates
$\mathbf{x}+\mathbf{b}$).

###  II-D List and permutation decoding

Assume that the codeword $\mathbf{c}$ is transmitted through a BMS channel $W$
and the received vector is $\mathbf{y}$. The successive cancellation (SC)
algorithm performs bit-by-bit estimation of the vector $\mathbf{u}$ as

$\tilde{u}_{i}=\begin{cases}\arg\max_{u_{i}\in\\{0,1\\}}W^{(i)}(\mathbf{y}_{0}^{n-1},\mathbf{\tilde{u}}_{0}^{i-1}|u_{i}),&i\notin\mathcal{F},\\\
0&i\in\mathcal{F},\end{cases}$ (3)

where $W^{(i)}=W^{(\\{-,+\\}^{m})}$ and is obtained by recursive application
of channel transformations

$W^{(-)}(y_{0},y_{1}|u_{0})=\frac{1}{2}\sum_{u_{1}\in\\{0,1\\}}W(y_{0}|u_{0}\oplus
u_{1})W(y_{1}|u_{1})$

and

$W^{(+)}(y_{0},y_{1},u_{0}|u_{1})=\frac{1}{2}W(y_{0}|u_{0}\oplus
u_{1})W(y_{1}|u_{1}).$

We can reformulate the recursions in the decoding process as follows:

  1. 1.

Recover $\mathbf{c}^{(-)}=\mathbf{c}_{0}^{n/2-1}\oplus\mathbf{c}_{n/2}^{n-1}$
transmitted through ’XOR’ channel $W^{(-)}$.

  2. 2.

Recover
$\mathbf{c}^{(+)}=\mathbf{c}_{n/2}^{n-1}=\mathbf{c^{(-)}}\oplus\mathbf{c}_{0}^{n/2-1}$
transmitted through ’Combine’ channel $W^{(+)}$, assuming that the recovered
codeword $\mathbf{\hat{c}^{(-)}}$ is correct.

  3. 3.

Return $\mathbf{c}=(\mathbf{c}^{(-)}\oplus\mathbf{c}^{(+)}|\mathbf{c}^{(+)})$

One way to improve the finite-length performance of SC decoding is to keep
track of both possible values $u_{i}$ so that at every step of the recursion
there are at most $L$ possible vectors $\mathbf{c}^{(-)}$ or
$\mathbf{c}^{(+)}$. Another approach is to observe that the code
$\mathcal{C}^{(-)}=\\{\mathbf{c}_{0}^{n/2-1}\oplus\mathbf{c}_{n/2}^{n-1}|\mathbf{c}\in\mathcal{C}\\}$
which appears at step 1 is a partial derivative and the recursions in SC
decoding follow a certain predefined ordering in which the derivatives are
taken. Hence, one can take $P$ distinct orderings, perform SC decoding for
each of them in parallel and return the closest codeword to the received
vector.

###  II-E Decoding efficiency

######  Proposition 1.

Consider a code $\mathcal{C}$ of length $n=2^{m}$ and the transmission through
a BMS channel $W$. If for all $i\in[m]$ holds
$R(\mathcal{C}^{(\mathbf{e}_{i})})>I(W^{(-)})$, SC list algorithm needs the
list size $L=2^{\Omega(n)}$ to achieve ML performance.

###### Proof.

SC decoding can be considered as a two-stage process, when we first recover
$\mathbf{c}^{(-)}\in\mathcal{C}^{(-)}$, assuming the transmission through the
synthetic channel $W^{(-)}$, and then use it to recover
$\mathbf{c}^{(+)}\in\mathcal{C}^{(+)}$, assuming the transmission through the
synthetic channel $W^{(+)}$. List decoding passes $L$ candidate codewords
$\mathbf{c}^{(-)}$ to the next stage and the decoder can only succeed if the
correct codeword is in the list. If $R(\mathcal{C}^{(-)})>I(W^{(-)})$, we are
trying to decode above the capacity and therefore need the list to be at least
$2^{n(R(\mathcal{C}^{(-)})-I(W^{(-)}))}$ to succeed [19, eq. (1.6)]. It
remains to recall that the code $\mathcal{C}^{(-)}$ is a partial derivative
$\mathcal{C}^{(\mathbf{e}_{i})}$, where $i$ depends on the chosen ordering. ∎

Remark. The condition $R(\mathcal{C}^{(\mathbf{e}_{i})})>I(W^{(-)})$ in
proposition 1 assumes that code $\mathcal{C}^{(\mathbf{e}_{i})}$ is capacity-
achieving and can be safely replaced with
$R(\mathcal{C}^{(\mathbf{e}_{i})})>\hat{I}$, where $\hat{I}$ is the largest
capacity of the channel from the same family as $W^{(-)}$ so that the ML
decoding of $\mathcal{C}^{(\mathbf{e}_{i})}$ almost always succeeds.

Therefore, in order to have good performance with small list size, one needs
to guarantee that there is at least one derivative with sufficiently small
rate. Permutation decoding is more demanding in that regard since it uses
different orderings on the derivatives and needs more than one with small
rate. In what follows, we demonstrate the lower bounds on this rate, and that
the automorphism groups of Reed-Muller and eBCH codes ensure the exponential
complexity of their list and permutation decoding.

##  III Fully symmetric codes

######  Definition 1.

A $(2^{m},k)$ code $\mathcal{C}$ is fully symmetric if all its partial
derivatives have equal dimensions.

Let us denote this dimension as $\tilde{k}$. In this section, we demonstrate
that for fully symmetric codes $\tilde{k}$ is bounded from below and in fact
becomes of order $k/2$. We also show that Reed-Muller and eBCH codes are fully
symmetric.

######  Proposition 2.

Consider a $(2^{m},k)$ fully symmetric code $\mathcal{C}$. If its dimension
can be expressed as
$k=\sum_{i=0}^{l-1}\binom{m}{i}+j\frac{\operatorname{lcm}(l,m)}{l}$, where
$0\leq j\frac{\operatorname{lcm}(l,m)}{l}<\binom{m}{l}$, then

$\tilde{k}\geq\sum_{i=0}^{l-2}\binom{m-1}{i}+j\frac{\operatorname{lcm}(l,m)}{m}$
(4)

We get $\operatorname{lcm}$ in the expression due to the full symmetry
constraint, which is further explained below. We call the code optimal if it
satisfies (4) with an equality.

######  Proposition 3.

Consider a sequence of optimal fully symmetric codes $\mathcal{C}$ of fixed
rate and increasing length $2^{m}$. Then for $i\in[m]$

$\lim_{m\to\infty}R(\mathcal{C}^{(\mathbf{e}_{i})})=R(\mathcal{C}).$ (5)

Proposition 2 implies that list or permutation decoding in any channel $W$
s.t. $\frac{\tilde{k}}{2^{m-1}}>I(W^{(-)})$ needs an exponential complexity to
achieve the ML performance, and proposition 3 states that this condition
asymptotically becomes $R(\mathcal{C})>I(W^{(-)})$.

###  III-A Proof of Proposition 2 for monomial codes

Let us start from the rate-1 code $\mathcal{C}_{m}$. All its derivatives are
also rate-1 codes and therefore $\mathcal{C}_{m}$ is fully symmetric. Any
monomial code $\mathcal{C}$ can be constructed by removing $2^{m}-k$ monomials
from $M_{\mathcal{C}_{m}}$ and we would like to do it in a way such that
$\mathcal{C}$ is fully symmetric and $\tilde{k}$ is minimized. Observe that
$\frac{\partial x^{\mathbf{v}}}{\partial x_{i}}$ is nonzero iff $v_{i}=1$ and
hence removing $x^{\mathbf{v}}$ from the generating set decreases the
dimensions of $\operatorname{wt}(\mathbf{v})=\deg(x^{\mathbf{v}})$ partial
derivatives by 1 (or equivalently, the dimensions of all derivatives are
decreased on average by $\operatorname{wt}(\mathbf{v})/m$). This implies that
the optimum strategy is to remove $2^{m}-k$ monomials of the largest degrees.

If $k=\sum_{i=0}^{l}\binom{m}{i},0\leq l\leq m$, we simply remove all
monomials of degree larger than $l$ and consequently each derivative contains
all monomials on $m-1$ variables of degree at most $l-1$, which gives
$\tilde{k}=\sum_{i=0}^{l-1}\binom{m-1}{i}$. Otherwise, we can write
$k=\sum_{i=0}^{l-1}\binom{m}{i}+p,0<p<\binom{m}{l},$ and remove $p$ monomials
of degree $l$ in addition. It follows that the dimensions of all derivatives
are decreased on average by $\frac{pl}{m}$, and since the code is fully
symmetric the actual decrease for any derivative should also be
$\frac{pl}{m}$. Therefore, $\frac{pl}{m}$ must be an integer, which is true
only if $p$ is a multiple of $\frac{\operatorname{lcm}(l,m)}{l}$, which
implies the bound (4).

The bound coincides with the parameters of Reed-Muller codes when $j=0$.
Otherwise, the set of monomials to remove can be found by considering a
bipartite graph $\mathcal{G}=(V_{L},V_{R},E)$ with left vertices $h_{i}\in
V_{L}$ isomorphic to variables $x_{i},1\leq i\leq m$ and right vertices
$h_{v}\in V_{R}$ isomorphic to all degree-$l$ monomials $x^{\mathbf{v}}$. We
draw an edge between $h_{i}$ and $h_{v}$ if the monomial $x^{\mathbf{v}}$
contains $x_{i}$. This graph is $(\binom{m-1}{l-1},l)$-biregular and we want
to remove all but $j\frac{\operatorname{lcm}(l,m)}{l}$ of its right vertices
so that the graph remains biregular, i.e., find its $(\cdot,l)$-biregular
subgraph $\mathcal{G}^{\prime}$.

$x_{4}$$x_{3}$$x_{2}$$x_{1}$$x_{3}x_{4}$$x_{2}x_{4}$$x_{2}x_{3}$$x_{1}x_{4}$$x_{1}x_{3}$$x_{1}x_{2}$

Figure 1: $(3,2)$-regular $\mathcal{G}$ and $(1,2)$-regular
$\mathcal{G}^{\prime}$

Figure 1 demonstrates an example of graph $\mathcal{G}$ for $m=4,l=2$ and one
of its possible $(1,2)$-regular subgraphs $\mathcal{G}^{\prime}$ (in red).
Such $\mathcal{G}^{\prime}$ can be found as a maximum flow solution for the
network with the source connected to all left vertices with
capacity-$\frac{\operatorname{lcm}(l,m)}{l}$ edges, the sink connected to all
right vertices with capacity-$m$ edges and all $e\in E$ having the unit
capacity.

###  III-B Proof of Proposition 2 for polynomial codes

We start from a simple case and consider an $(2^{m},k)$ code
$\mathcal{C}_{r}\subseteq\operatorname{span}\\{x^{\mathbf{v}}|\operatorname{wt}(\mathbf{v})=r\\}$
for some fixed $r$. By definition, $0\leq k\leq\binom{m}{r}$, and consequently
$0\leq\tilde{k}\leq\binom{m-1}{r-1}$. Code $\mathcal{C}_{r}$ by definition is
spanned by $k$ degree-$r$ linearly independent homogeneous polynomials
$f_{s},1\leq s\leq k$. Assume now a certain ordering on monomials
$x^{\mathbf{v}^{(j)}}$, e.g., lexicographic w.r.t. $\mathbf{v}^{(j)}$, and
consider the $k\times\binom{m}{r}$ matrix $\mathbf{M}$ such that $M_{s,j}=1$
if $f_{s}$ includes $\mathbf{v}^{(j)}$. $\mathbf{M}$ is a basis of the linear
space of all polynomials whose evaluations are codewords of $\mathcal{C}_{r}$
and therefore has full row rank, so we can use Gaussian elimination to
transform it into $\mathbf{\tilde{M}}=\left(\mathbf{I}\ *\right)\mathbf{P}$,
where $\mathbf{P}$ is a column permutation matrix. Let us further define a
vector $\boldsymbol{\phi}$ s.t. $\phi_{j}=1$ if $j$-th column of
$\mathbf{\tilde{M}}$ is a column of the identity matrix.

Similarly, the generator of the linear space corresponding to the partial
derivative $\frac{\partial}{\partial x_{i}}$ is a matrix
$\mathbf{\tilde{M}}_{i}$ obtained by removing all columns of
$\mathbf{\tilde{M}}$ but the ones that correspond to monomials that include
$x_{i}=1$. Its dimension is equal to
$\operatorname{rank}\mathbf{\tilde{M}}_{i}$. From the construction it follows
that $\operatorname{rank}\mathbf{\tilde{M}}_{i}\geq|\\{j|\phi_{j}=1\wedge
v^{(j)}_{i}=1\\}|$. In case of monomial codes we have
$\operatorname{rank}\mathbf{\tilde{M}}_{i}=|\\{j|\phi_{j}=1\wedge
v^{(j)}_{i}=1\\}|$, so it only remains to see that the bound (4) minimizes
$\max_{i}|\\{j|\phi_{j}=1\wedge v^{(j)}_{i}=1\\}|$. The extension to the
general case is straightforward.

######  Example 1.

Consider $m=4,r=2,k=4$ and assume $\boldsymbol{\phi}=(0,1,1,1,1,0)$, where the
ordering on degree-2 monomials is
$(x_{1}x_{2},x_{1}x_{3},x_{1}x_{4},x_{2}x_{3},x_{2}x_{4},x_{3}x_{4})$. This
vector corresponds to the matrix

$\mathbf{\tilde{M}}=\begin{pmatrix}*&1&0&0&0&*\\\ *&0&1&0&0&*\\\
*&0&0&1&0&*\\\ *&0&0&0&1&*\\\ \end{pmatrix},$

where $*$ can be any binary value. The partial derivatives correspond to the
matrices

$\mathbf{\tilde{M}}_{1}=\begin{pmatrix}*&1&0\\\ *&0&1\\\ *&0&0\\\ *&0&0\\\
\end{pmatrix}\mathbf{\tilde{M}}_{2}=\begin{pmatrix}*&0&0\\\ *&0&0\\\ *&1&0\\\
*&0&1\\\ \end{pmatrix}\\\ ,$ $\mathbf{\tilde{M}}_{3}=\begin{pmatrix}1&0&*\\\
0&0&*\\\ 0&1&*\\\ 0&0&*\\\
\end{pmatrix}\mathbf{\tilde{M}}_{4}=\begin{pmatrix}0&0&*\\\ 1&0&*\\\ 0&0&*\\\
0&1&*\\\ \end{pmatrix}.$

We have $\max_{i}\operatorname{rank}\mathbf{\tilde{M}}_{i}\geq 2$ and we know
that the code spanned by $\\{x_{1}x_{3},x_{1}x_{4},x_{2}x_{3},x_{2}x_{4}\\}$
has $\max_{i}\operatorname{rank}\mathbf{\tilde{M}}_{i}=2$.

###  III-C Proof of Proposition 3

Let $m$ be an odd number and consider an optimal fully symmetric code of rate
$1/2$. Its dimension can be expressed as $k=2^{m-1}=\sum_{i=0}^{\lfloor
m/2\rfloor}\binom{m}{i}$ and its derivatives have dimension

$\tilde{k}=\sum_{i=0}^{\lfloor m/2\rfloor-1}\binom{m-1}{i}.$

Now consider
$\left|\frac{\tilde{k}}{2^{m-1}}-\frac{1}{2}\right|=\left|\frac{\binom{m-1}{\lfloor
m/2\rfloor}}{2^{m}}\right|$, which goes to 0 with $m\to\infty$, and to finish
the proof it remains to notice that the bound (4) is convex, which gives the
same convergence for all values of $k$. Assume now that $\frac{\partial
C}{\partial x_{i}}$ is a subcode of $\mathcal{C}$, i.e.,
$\operatorname{Aut}(\mathcal{C})$ contains the permutation
$\mathbf{x}\to\mathbf{x}+\mathbf{e}_{i}$. Since any permutation
$\mathbf{x}\to\mathbf{x}+\mathbf{b}$ can be decomposed into a product of
transpositions, we have $\dim\frac{\partial C}{\partial x_{i}}\leq k/2$ due to
Legeay [20, Corollary 1] and therefore the lower bound on the derivative code
rate converges to the worst-case value.

###  III-D Symmetry of RM and eBCH codes

######  Proposition 4.

Reed-Muller codes are fully symmetric.

###### Proof.

Indeed, by construction $M_{r,m}$ includes all $m$-variate monomials up to
degree $r$ and the generating set of any partial derivative consists of all
$(m-1)$-variate monomials up to degree $r-1$. ∎

######  Lemma 1.

If $\operatorname{Aut}(\mathcal{C})$ contains permutation $\pi$ s.t.
$\pi(\mathbf{x}+\mathbf{\tilde{b}})=\pi(\mathbf{x})+\mathbf{b}$ for some
nonzero $\mathbf{b},\mathbf{\tilde{b}}\in\mathbb{F}_{2}^{m}$, then the codes
induced by the direction derivatives $D_{\mathbf{b}}$ and
$D_{\mathbf{\tilde{b}}}$ are permutation equivalent.

###### Proof.

Consider some function $f(\mathbf{x})$ which is a codeword of $\mathcal{C}$
and its permutation $g(\mathbf{x})=f(\pi(\mathbf{x}))$. Take the derivatives
in directions $\mathbf{b}$ and $\mathbf{\tilde{b}}$:

$\displaystyle(D_{\mathbf{b}}f)(\mathbf{x})$
$\displaystyle=f(\mathbf{x})+f(\mathbf{x}+\mathbf{b})$
$\displaystyle(D_{\mathbf{\tilde{b}}}g)(\mathbf{x})$
$\displaystyle=g(\mathbf{x})+g(\mathbf{x}+\mathbf{\tilde{b}})$
$\displaystyle=f(\pi(\mathbf{x}))+f(\pi(\mathbf{x}+\mathbf{\tilde{b}}))$
$\displaystyle=f(\pi(\mathbf{x}))+f(\pi(\mathbf{x})+\mathbf{b})$

It follows that $D_{\mathbf{\tilde{b}}}g$ can be obtained from
$D_{\mathbf{b}}f$ by map $\mathbf{x}\to\pi(\mathbf{x})$. Since both $f$ and
$g$ are codewords of $\mathcal{C}$, we can conclude that any codeword of
$D_{\mathbf{\tilde{b}}}\mathcal{C}$ can be obtained from a codeword of
$D_{\mathbf{b}}\mathcal{C}$ by permutation and vice versa and consequently the
derivatives of $\mathcal{C}$ in directions $\mathbf{b}$ and
$\mathbf{\tilde{b}}$ lead to permutation equivalent codes. ∎

######  Proposition 5.

Affine-invariant codes are fully symmetric.

###### Proof.

A code is affine-invariant if $\operatorname{Aut}(\mathcal{C})$ contains
permutations $x\to ax+b$ for
$a\in\mathbb{F}_{2^{m}}^{*},b\in\mathbb{F}_{2^{m}}$, where the multiplication
$ax$ is performed in the finite field $\mathbb{F}_{2^{m}}$. A permutation
$x\to ax$ satisfies the conditions of Lemma 1 for all pairs $(b,\tilde{b})$
s.t. $b\tilde{b}^{-1}=a$ and it follows that all derivative codes are
permutation equivalent. ∎

######  Corollary 1.

eBCH codes are fully symmetric.

###### Proof.

Indeed, eBCH codes are affine-invariant [2, Theorem 16] and therefore fully
symmetric. ∎

Figure 2: Bounds on the derivative code rates for fully symmetric codes,
$n=512$

Figure 2 shows the actual derivative code rates for eBCH codes of length $512$
along with the lower bound (4) on the derivative rates for fully symmetric
codes (recall that RM codes achieve this bound) compared to the smallest
derivative rate for polar codes constructed using the Gaussian approximation
[21] for $E_{b}/N_{0}=2$dB. The capacity transformation for BEC is given as a
reference (if $I(W)=(1-\varepsilon)$, $I(W^{(-)})=(1-\varepsilon)^{2}$).
Observe that the bound is rather loose for eBCH codes, which are close to an
upper bound $k/2$. Potentially a better bound might be derived by taking more
structural properties into consideration rather than only full symmetry, which
we leave as a direction for the future research. However, this plot provides a
good demonstration why the list size for near-ML decoding of eBCH codes grows
even faster than for RM codes (and why for both codes it quickly becomes
impractical). An interesting observation is that the smallest derivative rate
for polar codes is close to the capacity of the ’XOR’ erasure channel despite
being constructed for the Gaussian channel.

##  IV Partially symmetric codes

We demonstrated that the full symmetry puts a rather restrictive lower bound
on the dimensions of the derivatives. In this section, we show what happens if
we demand fewer symmetries and derive the equivalent bounds.

######  Definition 2.

A $(2^{m},k)$ code $\mathcal{C}$ is $t$-symmetric if $t$ of its partial
derivatives have equal dimensions, which we denote as $\tilde{k}_{t}$, and
$m-t$ have dimensions strictly greater.

In other words, there exists a set of target derivatives
$\mathcal{H}_{t},|\mathcal{H}_{t}|=t$, such that
$\forall\mathbf{e}_{i}\in\mathcal{H}_{t}\
\dim\mathcal{C}^{(\mathbf{e}_{i})}=\tilde{k}_{t}$ and
$\forall\mathbf{e}_{i}\notin\mathcal{H}_{t}\
\dim\mathcal{C}^{(\mathbf{e}_{i})}>\tilde{k}_{t}$. A code is fully symmetric
if $t=m$, non-symmetric if $t=1$ and partially symmetric otherwise. Reed-
Muller codes are fully symmetric and polar codes are in general non-symmetric.
Without loss of generality, we assume
$\mathcal{H}_{t}=\\{\mathbf{e}_{i}|i\in[t]\\}$.

######  Proposition 6.

If a $t$-symmetric code $\mathcal{C}$ has dimension
$k=\sum_{i=0}^{l-1}\binom{t}{i}2^{m-t}+j\frac{\operatorname{lcm}(l,t)}{l}$,
then

$\tilde{k}_{t}\geq\sum_{i=0}^{l-2}\binom{t-1}{i}2^{m-t}+j\frac{\operatorname{lcm}(l,t)}{t}.$
(6)

We get $\operatorname{lcm}$ in the expression due to the $t$-symmetry
constraint, which is further explained below. Again we call a partially
symmetric code optimal if it satisfies (6) with an equality.

######  Proposition 7.

Consider a sequence of optimal $t$-symmetric codes $\mathcal{C}$ of fixed rate
and increasing length $2^{m}$, where $t$ is an increasing function of $m$.
Then for $i\in[t]$

$\lim_{m\to\infty}R(\mathcal{C}^{(\mathbf{e}_{i})})=R(\mathcal{C}).$ (7)

Therefore, even in more relaxed setting we get the lower bound similar to the
one for fully symmetric code and identical asymptotic result.

###  IV-A Proof of Proposition 6

Define $\tau_{\mathbf{v}}=|\\{i\in[t]|v_{i}=1\\}|$, i.e. the number of
variables $\\{x_{0},\dots,x_{t-1}\\}$ in the monomial $x^{\mathbf{v}}$. We
start from rate-1 code $\mathcal{C}_{m}$ and using the same argument as in
section III-A we conclude that removing $2^{m}-k$ monomials of the largest
$\tau_{\mathbf{v}}$ gives the optimal $t$-symmetric code. The number of
monomials $x^{\mathbf{v}}$ s.t. $\tau_{\mathbf{v}}=l$ is $\binom{t}{l}2^{m-t}$
since $l$ of the variables $\\{x_{0},\dots,x_{t-1}\\}$ can be selected in
$\binom{t}{l}$ ways with any combination of the remaining $m-t$.

Figure 3 demonstrates the lower bound 6 on the derivative rates of partially
symmetric codes for $t>2$ and $n=512$. In case of 3-symmetric codes, the bound
is close to the BEC curve, which is similar to the best derivative for polar
codes, so we can expect rather good list decoding performance. However, it
quickly grows with $t$, so we expect the large list size for near-ML decoding
except for the low- and high-rate regions.

Figure 3: Lower bounds on the derivative code rates for partially symmetric
codes, $n=512$

Similarly to the section III-B, the bound for monomial codes also holds for
polynomial codes.

###  IV-B Proof of Proposition 7

Let $t$ be an odd number and consider an optimal $t$-symmetric code of rate
$1/2$. Its dimension can be expressed as $k=2^{m-1}=2^{m-t}\sum_{i=0}^{\lfloor
t/2\rfloor}\binom{t}{i}$ and its target derivatives have dimension

$\tilde{k}_{t}=2^{m-t}\sum_{i=0}^{\lfloor t/2\rfloor-1}\binom{t-1}{i}.$

If $t$ is an increasing function of $m$, similarly to section III-C the
expression $\tilde{k}_{t}/2^{m-1}$ converges to $\frac{1}{2}$ and due to
convexity of bound (6), the same holds for all values of $k$. Therefore, any
sequence of $(2^{m},k)$ binary linear codes with the partial symmetry growing
with $m$ is asymptotically bad for polar-like decoding.

###  IV-C Code construction

The construction of the optimal $t$-symmetric monomial codes, i.e., achieving
(6) with equality, is summarized in Algorithm 1.

Algorithm 1 Construction of optimal partially symmetric code

Take $M_{\mathcal{C}}=M_{\mathcal{C}_{m}}$,
$k^{\prime}=|M_{\mathcal{C}_{m}}|=2^{m}$

$\hat{l}\leftarrow t$

while $k^{\prime}-2^{m-t}\binom{t}{\hat{l}}\geq k$ do

Remove from $M_{\mathcal{C}}$ all monomials with $\tau_{\mathbf{v}}=\hat{l}$

$\hat{l}\leftarrow\hat{l}-1$, $k^{\prime}\leftarrow
k^{\prime}-2^{m-t}\binom{t}{\hat{l}}$

$\hat{d}\leftarrow m-t+\hat{l}$

while $k^{\prime}-\binom{t}{\hat{l}}\binom{m-t}{\hat{d}-\hat{l}}\geq k$ do

Remove from $M_{\mathcal{C}}$ all degree-$\hat{d}$ monomials with
$\tau_{\mathbf{v}}=\hat{l}$

$\hat{d}\leftarrow\hat{d}-1$, $k^{\prime}\leftarrow
k^{\prime}-\binom{t}{\hat{l}}\binom{m-t}{\hat{d}-\hat{l}}$

while $k^{\prime}-\binom{t}{\hat{l}}\geq k$ do

Pick a degree-$(\hat{d}-\hat{l})$ monomial $x^{\mathbf{s}}$ s.t.
$\tau_{\mathbf{s}}=0$

Remove from $M_{\mathcal{C}}$ all degree-$\hat{d}$ monomials with
$\tau_{\mathbf{v}}=\hat{l}$ that contain $x^{\mathbf{s}}$

$k^{\prime}\leftarrow k^{\prime}-\binom{t}{\hat{l}}$ return $M_{\mathcal{C}}$

Note that for the small values of $t$ this construction leads to poor minimum
distance. For example, in case of $2$-symmetric codes with dimension $k\geq
2^{m}-2^{m-2}$ only at most $2^{m-2}$ monomials with $\tau_{\mathbf{v}}=2$ are
removed. Consequently, the generating set contains a degree-$(m-1)$ monomial
$\mathbf{x}^{\mathbf{\hat{v}}}$ with $\tau_{\mathbf{\hat{v}}}=1$ and therefore
from (1) the code has minimum distance at most 2.

In practice, one can construct $t$-symmetric codes as subcodes of some Reed-
Muller codes RM$(r,m)$ to guarantee that the minimum distance is at least
$2^{m-r}$. In this case, at step 1 we start from $M_{r,m}$ instead of
$M_{\mathcal{C}_{m}}$, at step 2 the term $2^{m-t}$ is replaced with
$\binom{t}{\hat{l}}\sum_{i=0}^{\min(m-t,r-\hat{l})}\binom{m-t}{i}$ and at step
3 the initial value of $\hat{d}$ becomes $\min(m-t+\hat{l},r)$ (since after
step 1 all monomials with the degree greater than $r$ are already removed and
therefore out of consideration).

######  Example 2.

Consider $m=4,t=3$ and $k=8$. All monomials with nonzero $\tau_{\mathbf{v}}$
are listed in Table I sorted in the removal order.

TABLE I: Monomials to remove. $l$ | Impact on dimension | Monomials
---|---|---
$3$ | Remove 1 monomial | $x_{1}x_{2}x_{3}x_{4}$
|  $\tilde{k}$ decreases by 1 | $x_{1}x_{2}x_{3}$
$2$ | Remove 3 monomials |  $x_{1}x_{2}x_{4}$, $x_{1}x_{3}x_{4}$, $x_{2}x_{3}x_{4}$
|  $\tilde{k}$ decreases by 2 |  $x_{1}x_{2}$, $x_{1}x_{3}$, $x_{2}x_{3}$
1 | Remove 3 monomials |  $x_{1}x_{4}$, $x_{2}x_{4}$, $x_{3}x_{4}$
|  $\tilde{k}$ decreases by 1 |  $x_{1}$, $x_{2}$, $x_{3}$

Start from $M_{4},k^{\prime}=16$ and go to step 2. Set $\hat{l}=3$.
$16-2^{4-3}\binom{3}{3}=14\geq 8$, so we remove all monomials that contain
$x_{1}x_{2}x_{3}$ ($x_{1}x_{2}x_{3}x_{4}$ and $x_{1}x_{2}x_{3}$), now
$k^{\prime}=14$ and $\hat{l}=2$. $14-2^{4-3}\binom{3}{2}=8\geq 8$, so we
remove all monomials that contain $x_{1}x_{2}$, $x_{1}x_{3}$ or $x_{2}x_{3}$
($x_{1}x_{2}x_{4}$, $x_{1}x_{3}x_{4}$, $x_{2}x_{3}x_{4}$ and $x_{1}x_{2}$,
$x_{1}x_{3}$, $x_{2}x_{3}$), now $k^{\prime}=8$ and the construction procedure
is terminated since $k^{\prime}=k$.

The constructed $(16,8,4)$ code has generating set
$M_{\mathcal{C}_{4,3}}=\\{x_{1}x_{4},x_{2}x_{4},x_{3}x_{4},x_{1},x_{2},x_{3},x_{4},1\\}$
and all of its target derivatives have the generating set $\\{x_{4},1\\}$ of
cardinality $2$.

Assume that $k$ satisfies proposition 6 and Algorithm 1 ends with
$k^{\prime}>k$. This means that for some fixed degree-$(\hat{d}-\hat{l})$
monomial $x^{\mathbf{s}},\tau_{\mathbf{s}}=0$ we need to remove $k^{\prime}-k$
degree-$\hat{d}$ monomials with $\tau_{\mathbf{v}}=\hat{l}$ that contain
$x^{\mathbf{s}}$ so that the dimensions of all target derivatives are
decreased by $\frac{(k^{\prime}-k)\hat{l}}{t}$. The set of monomials to remove
can be found using the same bipartite graph formulation as in section III-A.

###  IV-D Performance of partially symmetric monomial codes

We consider the transmission via additive white Gaussian noise (AWGN) channel
with binary phase shift keying (BPSK) modulation. We compare the list and
permutation decoding of optimal $(256,127)$ 3-symmetric and $(256,128)$
5-symmetric monomial codes that are subcodes of RM$(4,8)$, which are
constructed with the proposed algorithm. The set of permutations $\pi_{i}$ is
selected as in [13], namely by sorting all $m!$ factor graph layer
permutations by the SC decoding error probability and picking $P$ smallest
such that the Hamming distance between any pair
$(\pi_{i^{\prime}},\pi_{i^{\prime\prime}})$ is at least 5 so that they are
more likely to correct different error patterns. We observed that this method
performs better than randomly choosing from $t!$ layer permutations. Maximum
likelihood performance is estimated by choosing sufficiently large list size
so that the returned codeword is always not farther from the received vector
than the true one. For each data point, the simulation is stopped after
reaching 1000 decoding error events or 1000000 transmitted frames.

Figure 4: List and permutation decoding performance, $(256,127)$ 3-symmetric
and $(256,128)$ 5-symmetric monomial codes

The results are presented at figure 4. Despite almost identical ML
performance, 3-symmetric codes perform better under SCL decoding. In case of
5-symmetric codes, permutation decoding is as efficient as SCL. A similar
behavior for partially symmetric codes is also observed in [14] and [22],
where a larger group of permutations is used for the decoding.

##  V Discussion

Our results show that even the partial symmetry often implies an exponential
growth of list size. The case of permutation decoding is much trickier to
analyze. However, we know that it needs a rather large automorphism group to
work efficiently, which in turn increases the partial symmetry and therefore
the SC error probability. We conjecture that for larger codes it quickly
becomes much less efficient, although the limitations of permutation decoding
for short and moderate block lengths are yet to be investigated.

Another question is the construction of partially symmetric polynomial codes.
Polar codes with CRC [10] and dynamic frozen symbols [23] demonstrate a
significant performance improvement under list decoding despite being rather
simple to construct, so we would like to have something similar for the
permutation decoding. Experiments show that applying CRC does not give the
same effect for the permutation decoding as it does for the list decoding. The
design of codes with dynamic frozen symbols is also highly nontrivial. One
possible approach might be to start from an optimal monomial code with further
refinement of the corresponding linear subspace. However, we did not succeed
in constructing the codes of practical interest with this method.

##  VI Conclusion

In this paper, we studied how permutation group of the code impacts its list
decoding performance. One result is that highly symmetric codes such as Reed-
Muller or eBCH codes need exponentially growing list size and hence variations
of SC algorithm quickly become inefficient for larger code lengths. We also
show that the similar result holds in the case of much lesser symmetry.

## Acknowledgements

The authors thank the anonymous reviewers for many helpful comments, which
have greatly improved the quality of the paper. The authors thank Henry
Pfister for the useful feedback and pointing out that Lemma 1 can be
formulated for more general class of permutations rather than $x\to ax$.

## References

  * [1] K. Ivanov and R. Urbanke, “On the dependency between the code symmetries and the decoding efficiency,” in _2020 International Symposium on Information Theory and Its Applications (ISITA)_ , 2020, pp. 195–199.
  * [2] F. MacWilliams and N. Sloane, _The Theory of Error-Correcting Codes_ , 3rd ed. North-holland Publishing Company, 1981.
  * [3] S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. Şaşoğlu, and R. Urbanke, “Reed-Muller Codes Achieve Capacity on Erasure Channels,” in _Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing_ , ser. STOC ’16. New York, NY, USA: ACM, 2016, pp. 658–669. [Online]. Available: http://doi.acm.org/10.1145/2897518.2897584
  * [4] I. Dumer and K. Shabunov, “Soft-decision decoding of Reed-Muller codes: recursive lists,” _IEEE Transactions on Information Theory_ , vol. 52, no. 3, pp. 1260–1266, March 2006.
  * [5] M. Kamenev, Y. Kameneva, O. Kurmaev, and A. Maevskiy, “A new permutation decoding method for Reed-Muller codes,” _CoRR_ , vol. abs/1901.04433, 2019. [Online]. Available: http://arxiv.org/abs/1901.04433
  * [6] K. Ivanov and R. Urbanke, “Permutation-based decoding of Reed-Muller codes in binary erasure channel,” in _2019 IEEE International Symposium on Information Theory (ISIT)_ , July 2019, pp. 21–25.
  * [7] M. Geiselhart, A. Elkelesh, M. Ebada, S. Cammerer, and S. ten Brink, “Automorphism Ensemble Decoding of Reed-Muller Codes,” _arXiv:2012.07635 [cs, math]_ , Dec. 2020, arXiv: 2012.07635. [Online]. Available: http://arxiv.org/abs/2012.07635
  * [8] P. Trifonov, “A Score Function for Sequential Decoding of Polar Codes,” in _2018 IEEE International Symposium on Information Theory (ISIT)_ , 2018, pp. 1470–1474.
  * [9] E. Arikan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” _IEEE Transactions on Information Theory_ , vol. 55, no. 7, pp. 3051 –3073, June 2009\.
  * [10] I. Tal and A. Vardy, “List Decoding of Polar Codes,” _IEEE Transactions on Information Theory_ , vol. 61, no. 5, pp. 2213–2226, 2015.
  * [11] P. Giard, G. Sarkis, A. Balatsoukas-Stimming, Y. Fan, C.-y. Tsui, A. Burg, C. Thibeault, and W. J. Gross, “Hardware decoders for polar codes: An overview,” in _2016 IEEE International Symposium on Circuits and Systems (ISCAS)_ , 2016, pp. 149–152.
  * [12] P. Trifonov and V. Miloslavskaya, “Polar subcodes,” _IEEE Journal on Selected Areas in Communications_ , vol. 34, no. 2, pp. 254–266, Feb 2016.
  * [13] M. Kamenev, Y. Kameneva, O. Kurmaev, and A. Maevskiy, “Permutation decoding of polar codes,” _CoRR_ , vol. abs/1901.05459, 2019. [Online]. Available: http://arxiv.org/abs/1901.05459
  * [14] M. Geiselhart, A. Elkelesh, M. Ebada, S. Cammerer, and S. ten Brink, “On the Automorphism Group of Polar Codes,” _arXiv:2101.09679 [cs, math]_ , Jan. 2021, arXiv: 2101.09679. [Online]. Available: http://arxiv.org/abs/2101.09679
  * [15] C. Carlet, _Boolean Functions for Cryptography and Error-Correcting Codes_ , Y. Crama and P. L. Hammer, Eds. Cambridge: Cambridge University Press, 2010. [Online]. Available: https://www.cambridge.org/core/product/identifier/CBO9780511780448A022/type/book_part
  * [16] M. Bardet, V. Dragoi, A. Otmani, and J. Tillich, “Algebraic properties of polar codes from a new polynomial formalism,” in _2016 IEEE International Symposium on Information Theory (ISIT)_ , July 2016, pp. 230–234.
  * [17] I. Reed, “A class of multiple-error-correcting codes and the decoding scheme,” _Transactions of the IRE Professional Group on Information Theory_ , vol. 4, no. 4, pp. 38–49, September 1954.
  * [18] D. E. Muller, “Application of Boolean algebra to switching circuit design and to error detection,” _Transactions of the I.R.E. Professional Group on Electronic Computers_ , vol. EC-3, no. 3, pp. 6–12, Sept 1954.
  * [19] C. E. Shannon, R. G. Gallager, and E. R. Berlekamp, “Lower bounds to error probability for coding on discrete memoryless channels. I,” _Information and Control_ , vol. 10, no. 1, pp. 65–103, 1967. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0019995867900526
  * [20] M. Legeay, “Permutation decoding: Towards an approach using algebraic properties of the $\sigma$-subcode,” in _WCC 2011 - Workshop on coding and cryptography_ , Paris, France, Apr. 2011, pp. 193–202. [Online]. Available: https://hal.inria.fr/inria-00608107
  * [21] P. Trifonov, “Efficient design and decoding of polar codes,” _IEEE Transactions on Communications_ , vol. 60, no. 11, pp. 3221–3227, 2012.
  * [22] C. Pillet, V. Bioglio, and I. Land, “Polar Codes for Automorphism Ensemble Decoding,” _arXiv:2102.08250 [cs, math]_ , 2021. [Online]. Available: http://arxiv.org/abs/2102.08250
  * [23] P. Trifonov and G. Trofimiuk, “A randomized construction of polar subcodes,” in _2017 IEEE International Symposium on Information Theory (ISIT)_ , June 2017, pp. 1863–1867.