# Group Properties of Polar Codes for
Automorphism Ensemble Decoding

Valerio Bioglio, Ingmar Land, Charles Pillet Ingmar Land was with the
Mathematical and Algorithmic Sciences Lab, Paris Research Center, Huawei
Technologies Co. Ltd. 92100 Boulogne-Billancourt, France, when he provided his
contribution to the paper. He is now with Infinera Corporation, Ottawa, ON K2K
2X3, Canada (email: ingmar.land@ieee.com). Charles Pillet and Valerio Bioglio
are with the Algorithmic and Mathematical Science Lab, Paris Research Center,
Huawei Technologies France S.A.S.U. (email<EMAIL_ADDRESS>valerio.bioglio@huawei.com).

###### Abstract

In this paper, we propose an analysis of the automorphism group of polar
codes, with the scope of designing codes tailored for _automorphism ensemble_
(AE) decoding. We prove the equivalence between the notion of _decreasing
monomial codes_ and the universal partial order (UPO) framework for the
description of polar codes. Then, we analyze the algebraic properties of the
_affine automorphisms group_ of polar codes, providing a novel description of
its structure and proposing a classification of automorphisms providing the
same results under permutation decoding. Finally, we propose a method to list
all the automorphisms that may lead to different candidates under AE decoding;
by introducing the concept of _redundant_ automorphisms, we find the maximum
number of permutations providing possibly different codeword candidates under
AE-SC, proposing a method to list all of them. A numerical analysis of the
error correction performance of AE algorithm for the decoding of polar codes
concludes the paper.

###### Index Terms:

Polar codes, monomial codes, permutation decoding, AE decoding, automorphisms
groups.

##  I Introduction

Polar codes [1] are a class of linear block codes relying on the phenomenon of
channel polarization. Under successive cancellation (SC) decoding, they can
provably achieve capacity of binary memoryless symmetric channels for infinite
block length. However, in the short length regime, the performance of polar
codes under SC decoding is far from state-of-the-art channel codes. To improve
their error correction capabilities, the use of a list decoder based on SC
scheduling, termed as SC list (SCL) decoding, has been proposed in [2]. The
concatenation of a cyclic redundancy check (CRC) code to the polar code
permits to greatly improve its error correction performance [3], making the
resulting CRC-aided SCL (CA-SCL) decoding algorithm the de-facto standard
decoder for polar codes adopted in 5G standard [4]. In order to avoid the
extra decoding delay due to information exchange among parallel SC decoders in
hardware implementation of CA-SCL decoders, permutation-based decoders have
been proposed in [5] for SC; a similar approach was proposed in [6] for belief
propagation (BP) and in [7] for soft cancellation (SCAN). In a permutation-
based decoder, $M$ instances of the same decoder are run in parallel on
permuted factor graphs of the code, or alternatively on permuted versions of
the received signal. Even if the decoding delay is reduced, the error
correction performance gain of permutation-based decoders is quite poor due to
the alteration of the frozen set caused by the permutation. Research towards
permutations not altering the frozen set were carried out [8]; such
permutations are the _automorphisms_ of the code and form the group of
permutations mapping a codeword into another codeword. This new decoding
approach, i.e. the use of automorphisms in a permutation decoder, is referred
to as _automorphism ensemble_ (AE) decoding.

Given their affinity with polar codes, the analysis of the automorphisms group
of Reed-Muller (RM) codes is providing a guidance for this search. In fact,
the automorphism group of binary Reed-Muller code is known to be the general
affine group [9], and an AE decoder for RM codes has been proposed in [10]
using BP as component decoder. The boolean code nature of RM codes permitted
authors in [11] to propose a _monomial code_ description of polar codes.
Through this definition, in the same papers the authors proved that the group
of lower-triangular affine ($\mathsf{LTA}$) transformations form a subgroup of
the automorphisms group of polar codes. However, it has been proved in [10]
that $\mathsf{LTA}$ transformations commute with SC decoding, in the sense
that $\mathsf{LTA}$ transformations do not alter the result of SC decoding
process; this property leads to no gain under AE decoding when these
automorphisms are used. Fortunately, the $\mathsf{LTA}$ transformation group
is not always the full automorphisms group of polar codes [12]; if carefully
designed, a polar code exhibits a richer automorphisms group. In [13, 14], the
complete affine automorphisms group of a polar code is proved to be the block-
lower-triangular affine ($\mathsf{BLTA}$) group. Authors in [13, 12] showed
that automorphisms in $\mathsf{BLTA}$ group (not belonging to $\mathsf{LTA}$)
can be successfully used in an AE decoder; in practice, these automorphisms
are not absorbed by the SC decoder. Unfortunately, the group of affine
automorphisms of polar codes asymptotically is not much bigger than
$\mathsf{LTA}$ [15]. These discoveries paved the way for the analysis of the
automorphism group of polar codes, and in general on the struggle of
constructing polar codes having ”good” automorphism groups, i.e. a set of
automorphisms to be used in an AE decoder. Author in [16] followed another
approach, focusing on the use of polar subcodes in conjunction with a peculiar
choice of the permutation set to design polar codes for AE decoding. However,
this approach is less systematic than the analysis of the automorphism group
of the polar code, leading to less predictable gains.

In this paper, we propose an analysis of the automorphisms group of polar
codes, with the scope of designing codes exhibiting good error correction
performance under AE decoding. To begin with, in Section II we delve into the
monomial codes description of polar codes proposed in [11], proving the
equivalence between the notion of _decreasing monomial codes_ and the
universal partial order (UPO) framework proposed in [17] for the description
of polar codes. This parallelism will allow us to analyze the algebraic
properties of the _affine automorphisms group_ of polar codes in Section III,
namely a sub-group of the complete automorphisms group of polar codes whose
elements can be described through affine transformations. Thanks to this
analysis, we will provide a novel proof of the structure of the affine
automorphism group of polar codes, that is different from the ones provided in
[13, 14] and is connected to the UPO framework. Next, in Section IV we study
the nature of AE decoders introducing the notion of _decoder equivalence_ ,
namely a classification of automorphism providing the same results under
permutation decoding. Thanks to this new formalism, we prove that
$\mathsf{LTA}$ is not always the complete SC absorption group, namely that a
larger set of automorphisms may be absorbed under SC decoding. This result is
an extension of our preliminary analysis of decoder equivalence published in
[18]. We provide an alternative proof of a very recent result presented in
[19], namely that the complete SC absorption group has a $\mathsf{BLTA}$
structure. Finally, we propose a method to list all the automorphisms that may
lead to different candidates under permutation decoding; by introducing the
concept of _redundant_ automorphisms, we find the maximum number of
permutations providing possibly different codeword candidates under AE-SC. Our
method permits to easily list all these automorphisms, greatly simplifying the
search for automorphisms to be used in AE-SC decoding. All the results
presented in the paper are correlated with examples to guide the reader in the
process of constructing and using automorphisms for AE decoding of polar
codes. Section V, including a numerical analysis of the performance of AE
algorithm for the decoding of polar codes, concludes the paper.

##  II Polar codes and monomial codes

In this section we analyze the parallelism between polar codes and decreasing
monomial codes. Monomial codes have been introduced in [11] as a family of
codes including polar and RM codes. In the same paper, decreasing monomial
codes are introduced to provide a monomial description of polar codes. Through
this description, authors in [11] were able to prove that lower triangular
affine ($\mathsf{LTA}$) transformations form a sub-group of the automorphisms
group of polar codes. In this section, we extend the results in [11] proving
the equivalence between the notion of _decreasing monomial codes_ and the
universal partial order (UPO) framework proposed in [17]. UPO represents a
method to partially sort virtual polarized channels independently of the
actual channel used for the transmission. Due to the structure of the
polarization phenomenon, some of the virtual channels are inherently better
than others, and the UPO framework is able to catch this nuance and creates a
structure of virtual channels. To the best of our knowledge, this is the first
time that this equivalence is proved.

###  II-A Polar Codes

To begin with, we provide a definition of polar code. In the following, the
binary field with elements $\\{0,1\\}$ is denoted by $\mathbb{F}_{2}$, while
the set of non-negative integers smaller than $N$ is written as
$\mathbb{Z}_{N}=\\{0,1,\ldots,N-1\\}$.

######  Definition 1 (Polar codes).

A polar code of length $N=2^{n}$ and dimension $K$ is defined by a
transformation matrix $T_{n}=T_{2}^{\otimes n}$, where
$T_{2}\triangleq[\begin{smallmatrix}1&0\\\ 1&1\end{smallmatrix}]$, and a
frozen set $\mathcal{F}\subset\mathbb{Z}_{2^{n}}$, or inversely by an
information set
$\mathcal{I}=\mathcal{F}^{c}=\mathbb{Z}_{2^{n}}\backslash\mathcal{F}$.
Encoding is performed as $x=u\cdot T_{N}$, where $u_{\mathcal{F}}=0$; the code
is then given by

$\mathcal{C}=\\{x=u\cdot T_{N}:u\in\mathbb{F}_{2}^{N},u_{\mathcal{F}}=0\\}.$
(1)

Elements of the information set $\mathcal{I}$ are usually chosen according to
their reliability; in practice, virtual channels originated by the
transformation matrix are sorted in reliability order, and the indices of the
$K$ most reliable ones form the information set of the code. The reliability
of virtual channels depend on the characteristics of the transmission channel,
forcing the code designer to recalculate the reliability order every time the
channel parameters change. However, even if the polarization effect is non-
universal, the structure of transformation matrix $T_{N}$ permits to define an
_universal partial order_ (UPO) among virtual channels. In practice, we say
that $i\preceq j$ if virtual channel represented by index $i$ is always weaker
(i.e. less reliable) than the channel represented by index $j$, independently
of the original channel [17]. A polar code fulfills the UPO if this partial
reliability order is followed.

######  Definition 2 (Universal partial order).

A polar code is said to fulfill the universal partial order (UPO) if $\forall
i,j\in\mathbb{Z}_{2^{n}}$ such that $i\preceq j$ then
$i\in\mathcal{I}\Rightarrow j\in\mathcal{I}$.

$00000$$0$$m_{0}$$\bar{V}_{0}\bar{V}_{1}\bar{V}_{2}\bar{V}_{3}\bar{V}_{4}$$10000$$1$$m_{1}$$\bar{V}_{1}\bar{V}_{2}\bar{V}_{3}\bar{V}_{4}$$01000$$2$$m_{2}$$\bar{V}_{0}\bar{V}_{2}\bar{V}_{3}\bar{V}_{4}$$00100$$4$$m_{4}$$\bar{V}_{0}\bar{V}_{1}\bar{V}_{3}\bar{V}_{4}$$11000$$3$$m_{3}$$\bar{V}_{2}\bar{V}_{3}\bar{V}_{4}$$00010$$8$$m_{8}$$\bar{V}_{0}\bar{V}_{1}\bar{V}_{2}\bar{V}_{4}$$10100$$5$$m_{5}$$\bar{V}_{1}\bar{V}_{3}\bar{V}_{4}$$00001$$16$$m_{16}$$\bar{V}_{0}\bar{V}_{1}\bar{V}_{2}\bar{V}_{3}$$10010$$9$$m_{9}$$\bar{V}_{1}\bar{V}_{2}\bar{V}_{4}$$01100$$6$$m_{6}$$\bar{V}_{0}\bar{V}_{3}\bar{V}_{4}$$10001$$17$$m_{17}$$\bar{V}_{1}\bar{V}_{2}\bar{V}_{3}$$01010$$10$$m_{10}$$\bar{V}_{0}\bar{V}_{2}\bar{V}_{4}$$11100$$7$$m_{7}$$\bar{V}_{3}\bar{V}_{4}$$01001$$18$$m_{18}$$\bar{V}_{0}\bar{V}_{2}\bar{V}_{3}$$00110$$12$$m_{12}$$\bar{V}_{0}\bar{V}_{1}\bar{V}_{4}$$11010$$11$$m_{11}$$\bar{V}_{2}\bar{V}_{4}$$00101$$20$$m_{20}$$\bar{V}_{0}\bar{V}_{1}\bar{V}_{3}$$11001$$19$$m_{19}$$\bar{V}_{2}\bar{V}_{3}$$10110$$13$$m_{13}$$\bar{V}_{1}\bar{V}_{4}$$00011$$24$$m_{24}$$\bar{V}_{0}\bar{V}_{1}\bar{V}_{2}$$10101$$21$$m_{21}$$\bar{V}_{1}\bar{V}_{3}$$01110$$14$$m_{14}$$\bar{V}_{0}\bar{V}_{4}$$10011$$25$$m_{25}$$\bar{V}_{1}\bar{V}_{2}$$01101$$22$$m_{22}$$\bar{V}_{0}\bar{V}_{3}$$11110$$15$$m_{15}$$\bar{V}_{4}$$01011$$26$$m_{26}$$\bar{V}_{0}\bar{V}_{2}$$11101$$23$$m_{23}$$\bar{V}_{3}$$00111$$28$$m_{28}$$\bar{V}_{0}\bar{V}_{1}$$11011$$27$$m_{27}$$\bar{V}_{2}$$10111$$29$$m_{29}$$\bar{V}_{1}$$01111$$30$$m_{30}$$\bar{V}_{0}$$11111$$31$$m_{31}$$1$

Figure 1: Hasse diagram of UPO for $N=32$; integers and their binary
expansions are depicted in black, corresponding monomials are depicted in
blue.

Figure 1 provides a graphical representation of the relations among the
virtual channels for a polar code of length $N=32$. A node in the diagram
represents a virtual channel, while a directed edge represents the order
relation between two virtual channels. Nodes that are connected by a directed
path can be compared through the UPO, while the order relation between
unconnected nodes depends on the transmission channel and should be verified.
As an example, since nodes $5$ and $9$ are connected, we know that $5\preceq
9$ and virtual channel $5$ is always weaker than virtual channel $9$; on the
other hand, nodes $6$ and $9$ are not connected, and hence the order between
these two virtual channels depends on the original channels. A polar code
fulfilling the UPO can be described through few generators composing the
minimum information set $\mathcal{I}_{min}$ [13] as

$\mathcal{I}=\bigcup_{j\in\mathcal{I}_{min}}\\{i\in[N],j\preceq i\\}.$ (2)

It is worth noticing that a polar code designed to be decoded under SCL may
not fulfill the UPO; the universal reliability sequence standardized for 5G is
an example of this exception [4]. However, in the following we will focus on
polar codes fulfilling the UPO, since we are interested in AE decoders having
SC component decoders.

The UPO is induced by noticing that the binary expansion of the virtual
channel index actually provides the sequence of channel modifications, where a
$0$ represents a channel degradation and a $1$ represents a channel upgrade.

######  Definition 3 (Binary expansion).

The _canonical binary expansion_ connecting $\mathbb{F}_{2}^{n}$ and
$\mathbb{Z}_{2^{n}}$,

${v\in\mathbb{F}_{2}^{n}}$${\widehat{v}\in\mathbb{Z}_{2^{n}}}$$\scriptstyle{\widehat{\cdot}}$$\scriptstyle{\widecheck{\cdot}}$

maps an integer $v$ to its binary expansion $\widehat{v}$ with least
significant bit (LSB) on the left, namely with $v_{0}$ representing the LSB of
$v$; zero padding is performed if the number of bits representing $v$ is
smaller than $n$, namely if $v<2^{n-1}$.

So, given two virtual channel indices $i,j\in\mathbb{Z}_{2^{n}}$ with $i<j$,
if $\widehat{i}$ and $\widehat{j}$ represent their binary expansions, we have
that the corresponding nodes in the Hasse diagram are directly connected, and
hence $i\preceq j$, when:

  * •

if $\widehat{i}$ and $\widehat{j}$ only differ for a single entry $t$, where
$\widehat{i}_{t}=0$ and $\widehat{j}_{t}=1$;

  * •

if $\widehat{i}$ and $\widehat{j}$ only differ for two consecutive entries $t$
and $t+1$, where $\widehat{i}_{t}=1,\widehat{i}_{t+i}=0$ and
$\widehat{j}_{t}=0,\widehat{j}_{t+1}=1$.

These rules are iterated to generate the UPO among the virtual channels, and
hence among the integers representing these channels.

###  II-B Monomial Codes

Monomial codes are a family of codes of length $N=2^{n}$ defined by
evaluations of boolean functions of $n$ variables. A boolean function can be
described as a map from a string of $n$ bits to a single bit defined by a
specific truth table; this map can always be rewritten as a polynomial $f$ in
the polynomial ring in $n$ indeterminates over $\mathbb{F}_{2}$, i.e.
$f\in\mathbb{F}_{2}[V_{0},\dots,V_{n-1}]\triangleq\mathbb{F}_{2}^{[n]}$. Since
an element of $\mathbb{F}_{2}^{n}$ can be interpreted as the binary
representation of an integer, boolean functions can be seen as maps
associating a bit to each integer in $\mathbb{Z}_{2^{n}}.$ Every boolean
function can be written as a linear combination of monomials in variables
$V_{i}$, forming a basis for the space of boolean functions. A monomial in
$V_{i}$ is a product of powers of variables $V_{i}$, with $0\leq i<n$, having
non-negative exponents, e.g. $V_{0}^{2}V_{2}$. However, since
$V_{i}^{2}=V_{i}$ in $\mathbb{F}_{2}^{[n]}$, variables either appear or not in
monomials. Similarly, _negative monomials_ , namely monomials in
$\bar{V}_{i}=\neg V_{i}=(1\oplus V_{i})$, form a basis of the same space; in
the following, we will use negative monomials to smoothly map polar codes to
monomial codes, and we call $\mathcal{M}^{[n]}\subset\mathbb{F}_{2}^{[n]}$ the
set of monomials in $n$ indeterminates over $\mathbb{F}_{2}$. Given their
importance in the definition of boolean functions, we introduce here a
notation to connect each monomial in $\mathcal{M}^{[n]}$ to an integer in
$\mathbb{Z}_{2^{n}}$.

######  Definition 4 (Monomials canonical map).

The _canonical map_ connecting $\mathbb{Z}_{2^{n}}$ and $\mathcal{M}^{[n]}$,

$\displaystyle\mathbb{Z}_{2^{n}}$
$\displaystyle\leftrightarrow\mathcal{M}^{[n]}$ $\displaystyle t$
$\displaystyle\leftrightarrow m_{t},$

connects integer $t\in\mathbb{Z}_{2^{n}}$, where for some
$Q\subset\mathbb{Z}_{n}$

$t=\sum_{i\in Q}2^{i},$ (3)

to monomial $m_{t}\in\mathcal{M}^{[n]}$, defined by

$m_{t}=\prod_{i\notin Q}\bar{V}_{i}$ (4)

In practice, the monomials canonical map transforms a monomial into an integer
having zeroes in its binary expansion corresponding to the variable indices,
and ones elsewhere. Equipped with this map, we can now define the monomial
evaluation function.

######  Definition 5 (Evaluation function).

The evaluation function
$\operatorname{eval}:\mathbb{F}_{2}^{[n]}\rightarrow\mathbb{F}_{2}^{N}$ checks
the output of $f$ for all elements of $\mathbb{F}_{2}^{n}$ in increasing
order; in practice,

$x^{(f)}=\operatorname{eval}(f)\triangleq(f(\widehat{0}),f(\widehat{1}),\ldots,f(\widehat{N-1})).$
(5)

As a consequence, every boolean function $f$ can be naturally associated to a
binary vector $x^{(f)}$ of length $N$ through the evaluate function
$\operatorname{eval}(f)$. An example of this construction can be found in
Appendix Boolean functions and permutations. Given that high degree monomials
are defined as products of degree-one monomials, namely single variables,
knowing the evaluations of single variables it is easy to calculate the
evaluation of high-degree monomials as xor of the associated binary strings.
This property permits to generate a family of block codes based on the
evaluation of monomial functions.

######  Definition 6 (Monomial codes).

A _monomial code_ of length $N=2^{n}$ and dimension $K$ is given by the
evaluations of linear combinations of the monomials included in a generating
monomial set $\mathcal{G}\subset\mathcal{M}^{[n]}$, with $|\mathcal{G}|=K$.

Given $n$ variables, it is possible to form $2^{n}$ different monomials, of
which $\binom{n}{r}$ are of degree $r$. A monomial code of length $N=2^{n}$
and dimension $K$ is generated by picking $K$ monomials out of the $N$. Reed-
Muller codes are monomial codes defined by picking all monomials up to a
certain degree: in particular, $\mathcal{R}(r,n)$ code is generated by all
monomials of degree smaller or equal to $r$. The family of monomial codes
being so rich, in order to introduce a parallelism between these codes and the
polar codes, a notion of partial order among monomials is needed. Authors in
[11] propose such a partial order. Given two monomials
$m_{t_{1}},m_{t_{2}}\in\mathcal{G}$ of degrees $s_{1}$ and $s_{2}$
respectively, where
$m_{t_{1}}=\bar{V}_{i_{0}}\cdot\ldots\cdot\bar{V}_{i_{s_{1}-1}}$ and
$m_{t_{2}}=\bar{V}_{j_{0}}\cdot\ldots\cdot\bar{V}_{j_{s_{2}-1}}$, we say that
$m_{t_{1}}\preceq m_{t_{2}}$:

  * •

when $s_{1}=s_{2}=s$, then if and only if $i_{l}\leq j_{l}$ for all
$l=0,\dots,s-1$.

  * •

when $s_{1}<s_{2}$, then if and only if there exists a monomial
$m_{t^{\prime}}$ such that $m_{t^{\prime}}|m_{t_{2}}$,
$deg(m_{t_{1}})=deg(m_{t^{\prime}})$ and $m_{t_{1}}\preceq m_{t^{\prime}}$.

It is worth noticing that we used the same symbol to define the partial order
relations for integers and for monomials; in fact, we will see that these two
orders are equivalent. Equipped with the notion of partial order among
monomials, authors in [11] define the family of _decreasing monomial codes_ as
the monomial codes for which for every monomial in $\mathcal{G}$, all its sub-
monomial factors are also included in $\mathcal{G}$.

######  Definition 7 (Decreasing monomial codes).

A monomial code is _decreasing_ if for every monomial
$m_{t_{1}},m_{t_{2}}\in\mathcal{M}^{[n]}$ such that $m_{t_{1}}\preceq
m_{t_{2}}$ then $m_{t_{2}}\in\mathcal{G}\Rightarrow m_{t_{1}}\in\mathcal{G}$.

###  II-C Monomial and Polar Codes Equivalence

TABLE I: Canonical map between integers and monomials for $n=3$. degree | monomial | evaluation | row of $T_{8}$ | expansion
---|---|---|---|---
$0$ | $m_{7}=1$ | $11111111$ | 7 | 111
$1$ | $m_{6}=\bar{V}_{0}$ | $10101010$ | 6 | 011
$m_{5}=\bar{V}_{1}$ | $11001100$ | 5 | 101
$m_{3}=\bar{V}_{2}$ | $11110000$ | 3 | 110
$2$ | $m_{4}=\bar{V}_{0}\bar{V}_{1}$ | $10001000$ | 4 | 001
$m_{2}=\bar{V}_{0}\bar{V}_{2}$ | $10100000$ | 2 | 010
$m_{1}=\bar{V}_{1}\bar{V}_{2}$ | $11000000$ | 1 | 100
$3$ | $m_{0}=\bar{V}_{0}\bar{V}_{1}\bar{V}_{2}$ | $10000000$ | 0 | 000

Polar codes can be described as monomial codes. In fact, the kernel matrix
$T_{2}$ can be seen as the evaluation of monomials in
$\mathbb{F}_{2}[\bar{V}_{0}]$; $\operatorname{eval}(\bar{V}_{0})=[1,0]$
represents the first row of $T_{2}$, while $\operatorname{eval}(1)=[1,1]$
represents its second row. An example of this parallelism is provided in Table
I for $n=3$. This parallelism can be extended to polar codes of any length
$N=2^{n}$, such that each monomial in $\mathcal{M}^{[n]}$ is represented by an
integer in $\mathbb{Z}_{2^{n}}$ through the monomials canonical map. This map
permits to connect row $t$ of transformation matrix $T=T_{2}^{\otimes n}$ to a
unique monomial $m_{t}$; Then, polar codes can be equivalently defined in
terms of information set $\mathcal{I}$ or generating monomial set
$\mathcal{G}$, since $m_{t}\in\mathcal{G}\Leftrightarrow t\in\mathcal{I}$. To
summarize, polar codes can be seen as monomial codes where the generating
monomials are chosen according to polarization effect.

In the following, we prove the main result of this section, namely that UPO
property for polar codes is equivalent to decreasing property for monomial
codes. As a consequence, every polar code fulfilling the UPO is also a
decreasing monomial code, and vice versa. The fact that UPO is a sufficient
condition for the generation of decreasing monomial codes has been proved in
[11], while, for the best of our knowledge, this is the first time that it is
proven that it is also a necessary condition. Before proving the main theorem
of the section, we need to prove the equivalence between the partial order
defined on integers and the partial order defined on monomials.

######  Lemma 1.

For every $a,b\in\mathbb{Z}_{2^{n}}$, then $b\preceq a\Leftrightarrow
m_{a}\preceq m_{b}$

###### Proof.

Sufficient condition: Given $a,b\in\mathbb{Z}_{2^{n}}$ such that $b\preceq a$,
we want to prove that $m_{a}\preceq m_{b}$ by checking if the two conditions
for the partial ordering of the monomials are satisfied. If we call
$HW(\widehat{t})$ the Hamming weight of the binary expansion of integer $t$,
then $HW(\widehat{t})=n-deg(m_{t})$ by Definition 4, and the degree conditions
of monomial partial orders can be rewritten as conditions on the Hamming
weights of binary expansions of integers.

If $HW(\widehat{a})=HW(\widehat{b})=n-s$, then $deg(m_{a})=deg(m_{b})=s$; if
we call $\bar{S}$ the set of variable indices composing monomial $m_{t}$,
namely $m_{t}=\prod_{i\in\bar{S}}\bar{V}_{i}\in\mathcal{M}^{[n]}$, then
$m_{a}\preceq m_{b}$ if and only if $i^{(a)}_{l}\leq j^{(b)}_{l}$ for all
$l=0,\dots,s-1$, where $i^{(t)}_{l}$ is the $l$-th bit in the binary expansion
of integer $t$. Since $b\preceq a$ and $HW(\widehat{a})=HW(\widehat{b})$, then
it is possible to create a chain of integers $t_{0},\dots,t_{r}$ such that
$b=t_{r}\preceq t_{r-1}\preceq\ldots\preceq t_{1}\preceq t_{0}=a$ such that
they all have the same Hamming weight and each couple of subsequent integers
in the chain only differ for two consecutive entries. By definition, we have
that $m_{t_{i}}\preceq m_{t_{i+1}}$ for the monomials partial order
definition, and then the chain can be rewritten as $m_{a}=m_{t_{0}}\preceq
m_{t_{1}}\preceq\ldots\preceq m_{t_{r-1}}\preceq m_{t_{r}}=m_{b}$.

Alternatively, if $HW(\widehat{b})<HW(\widehat{a})$, than there is at least
one chain of integers such that $b=t_{r}\preceq t_{r-1}\preceq\ldots\preceq
t_{1}\preceq t_{0}=a$, where each couple of subsequent integers only differ
for a single or two consecutive entries. Now, let us focus on three elements
of the chain $t_{i+1}\preceq t_{i}\preceq t_{i-1}$ such that $t_{i+1}$ and
$t_{i}$ differ for a single entry, while $t_{i}$ and $t_{i-1}$ differ for two
consecutive entries; in this case, there exists another integer
$t^{\prime}_{i}$ such that $t_{i+1}\preceq t^{\prime}_{i}\preceq t_{i-1}$ and
$t_{i+1}$ and $t^{\prime}_{i}$ differ for two consecutive entries, while
$t^{\prime}_{i}$ and $t_{i-1}$ differ for a single entry. In practice, it is
always possible to invert the application of two different rules in the chain.
As a consequence, it is always possible to create a chain
$b=t^{\prime}_{r}\preceq t^{\prime}_{r-1}\preceq\ldots\preceq
t^{\prime}_{1}\preceq t^{\prime}_{0}=a$ such that integers from
$b=t^{\prime}_{r}$ to a certain integer $t^{\prime}_{c}$ differ for a single
entry, while from $t^{\prime}_{c}$ to $t^{\prime}_{0}=a$ two consecutive
integers differ for two consecutive entries. Then, from this chain we extract
element $t^{\prime}_{c}$ with $b\preceq t^{\prime}_{c}\preceq a$; by
construction, the set of the indices of the positions of zeroes in the binary
expansion of $t^{\prime}_{c}$ is a subset of the same set of $b$, and hence
$m_{t^{\prime}_{c}}|m_{b}$. Moreover, $HW(t^{\prime}_{c})=HW(\widehat{a})$,
and then $deg(m_{t^{\prime}_{c}})=deg(m_{a})$ and thus $m_{a}\preceq m_{b}$.

Sufficient condition: Given $m_{a},m_{b}\in\mathcal{M}^{[n]}$ such that
$m_{a}\preceq m_{b}$, we want to prove that $b\preceq a$ by checking if the
two conditions for the partial ordering of the integers are satisfied. If
$deg(m_{a})=deg(m_{b})$, we can create a chain of intermediate monomials
$m_{a}=m_{t_{r}}\preceq m_{t_{r-1}}\preceq\ldots\preceq m_{t_{1}}\preceq
m_{t_{0}}=m_{b}$ such that they all have the same degree and each couple of
subsequent monomials in the chain only differ by a variable; in other words,
there exists a variables swap chain passing from $m_{a}$ to $m_{b}$ where each
step of the chain can be sorted according to the partial order. This monomials
chain can be mirrored to the corresponding integers chain $b=t_{0}\preceq
t_{1}\preceq\ldots\preceq t_{r-1}\preceq t_{r}=a$, where consecutive integers
differ for two consecutive entries, and thus $b\preceq a$. Alternatively, If
$deg(m_{a})<deg(m_{b})$, then there exists a monomial $m_{t}$ dividing $m_{b}$
and having the same degree of $m_{a}$ such that $m_{a}\preceq m_{t}\preceq
m_{b}$. Then, $t\preceq a$ for the previous case, and $b\preceq t$. ∎

Equipped with Lemma 1, we can now prove the main result of this section,
namely the equivalence between UPO polar codes and decreasing monomial codes.

######  Theorem 1.

A polar code design is compliant with the UPO framework if and only if it is a
decreasing monomial code.

###### Proof.

First, we assume that the information set of the polar code is compliant with
the UPO framework. We need to prove that, if $m_{t}\in\mathcal{G}$, then also
$m_{t^{\prime}}\in\mathcal{G}$ for every $m_{t^{\prime}}\preceq m_{t}$.
According to Lemma 1, $t\preceq t^{\prime}$, and since $t\in\mathcal{I}$ we
have that also $t^{\prime}\in\mathcal{I}$ for the UPO hypothesis, and hence
$m_{t^{\prime}}\in\mathcal{G}$. Second, we assume the code to be decreasing
monomial; now we need to prove that for every $t\in\mathcal{I}$, then also
$m_{t^{\prime}}\in\mathcal{G}$ for every $t\preceq t^{\prime}$. Again, Lemma 1
says that $m_{t^{\prime}}\preceq m_{t}$, and since $m_{t}\in\mathcal{G}$ then
also $m_{t^{\prime}}\in\mathcal{G}$ for the decreasing monomial hypothesis,
and hence $t^{\prime}\in\mathcal{I}$. ∎

##  III Polar code automorphisms

Automorphisms are permutations of code bit positions that are invariant to the
code, namely that map codewords into codewords. The analysis of the
automorphism group of a code permits to discover hidden symmetries of the
codewords, and can be used to find new properties of the code. In this paper,
our study of the automorphism group of polar codes is driven by the will of
improving AE decoding algorithms for this family of codes. In this section, we
first revise permutations defined by general affine transforms and then
discuss properties of such permutations that are automorphisms of polar codes.
Moreover, we provide all the tools to help the reader to map an affine
transformation to the related code bit permutation, by explicitly showing how
to pass from one to the other. Equipped with this map, it will be easier for
the reader to understand the main results of following sections and to
reproduce the results presented in Section V.

###  III-A Permutations as affine transformations

######  Definition 8 (Permutation).

A permutation $\pi$ over the set $\mathbb{Z}_{2^{n}}$,

$\displaystyle\pi:\mathbb{Z}_{2^{n}}$
$\displaystyle\rightarrow\mathbb{Z}_{2^{n}}$ $\displaystyle i$
$\displaystyle\mapsto\pi(i),$

is a bijection of $\mathbb{Z}_{2^{n}}$ onto itself.

The _trivial (identity) permutation_ is written as $\mathbbm{1}$ and maps
every integer to itself. Permutations can be applied to vectors in different
ways; in the following, for permutations of vectors we will use the
_functional passive notation_ , where the element in position $i$ is replaced
by element in position $\pi(i)$ after the permutation and permutations are
concatenated giving priority to the right [20].

######  Definition 9 (Vector permutation).

Given a permutation $\pi$, the vector $y=(y_{0},y_{1},\ldots,y_{2^{n}-1})$ is
called the permuted vector of vector $x=(x_{0},x_{1},\ldots,x_{2^{n}-1})$, if
and only if

$y_{i}=x_{\pi(i)}$

for all $i\in\mathbb{Z}_{2^{n}}$. For convenience we may write111The meaning
of $\pi$ becomes clear from the context. $y=\pi(x)$ and call $y$ the
permutation of $x$.

According to the introduced notation, the concatenation of two permutations
$\pi_{1}$ and $\pi_{2}$ is written as $\pi_{2}\circ\pi_{1}=\pi_{2}\pi_{1}$, to
be applied from right to left, i.e., $\pi_{1}$ first and $\pi_{2}$ second. To
apply this to vectors, assume three vectors $x$, $y=\pi_{1}(x)$, and
$z=\pi_{2}(y)=\pi_{2}(\pi_{1}(x))$; then $y_{i}=x_{\pi_{1}(i)}$ and
$z_{j}=y_{\pi_{2}(j)}$ from Definition 9, and $z_{j}=x_{\pi_{1}(\pi_{2}(j))}$
by substituting $i=\pi_{1}(j)$. Next, we define the group of affine
transformations over binary vector, and we show how these transformations are
related to permutations.

######  Definition 10 (Affine transformations).

The General Affine (GA) group $\mathsf{GA}(n)$ is the group of affine
transformations of binary vectors $v\in\mathbb{F}_{2}^{n}$,

$\displaystyle T_{(A,b)}:\mathbb{F}_{2}^{n}$
$\displaystyle\rightarrow\mathbb{F}_{2}^{n}$ $\displaystyle v$
$\displaystyle\mapsto Av+b,$

with invertible matrices $A\in\mathbb{F}_{2}^{n\times n}$ and arbitrary
vectors $b\in\mathbb{F}_{2}^{n}$. Each element $T_{(A,b)}$ of this group is
uniquely identified by a matrix-vector pair $(A,b)$.

Every affine transformation gives rise to a permutation, and it does this in
natural way for codewords of monomial codes through Definition 3 as shown as
follows.

######  Definition 11 ($\mathsf{GA}$ permutations).

The $\mathsf{GA}$ permutations group is the group of permutations over
$\mathbb{Z}_{2^{n}}$ defined by affine transformations as
$\pi_{(A,b)}(v)=\widecheck{T_{(A,b)}\widehat{v}}$; the mapping between
$\mathbb{Z}_{2^{n}}$ and $\mathbb{F}_{2}^{n}$ is given as

${\mathbb{Z}_{2^{n}}}$${\mathbb{F}_{2}^{n}}$${\mathbb{Z}_{2^{n}}}$${\mathbb{F}_{2}^{n}}$$\scriptstyle{\pi_{(A,b)}}$$\scriptstyle{\widehat{\cdot}}$$\scriptstyle{T_{(A,b)}}$$\scriptstyle{\widecheck{\cdot}}$${v}$${\widehat{v}}$${\pi_{(A,b)}(v)}$${A\widehat{v}+b}$$\scriptstyle{\pi_{(A,b)}}$$\scriptstyle{\widehat{\cdot}}$$\scriptstyle{T_{(A,b)}}$$\scriptstyle{\widecheck{\cdot}}$

It is worth noticing that the vice versa is not true, namely that not every
permutation can be expressed as an affine transformation. Assuming a boolean
function $f\in\mathbb{F}_{2}^{[n]}$, an affine transformation $T_{(A,b)}$ can
be applied to $f$, obtaining boolean function $g=T_{(A,b)}(f)$ defined by

$g(V)=f(A\cdot V+b).$

It is possible to concatenate affine transformations; given
$g=T_{(A_{1},b_{1})}(f)$ and $h=T_{(A_{2},b_{2})}(g)$, we have that
$h=T_{(A,b)}(f)=T_{(A_{2},b_{2})}\circ T_{(A_{1},b_{1})}(f)$. By definition,
we have that

$\displaystyle h(V)$ $\displaystyle=g(A_{2}\cdot V+b_{2})=f(A_{1}(A_{2}\cdot
V+b_{2})+b_{1})=$ (6) $\displaystyle=f(A_{1}A_{2}\cdot V+A_{1}b_{2}+b_{1}).$
(7)

As a consequence, $T_{(A,b)}$ is defined by matrix $A=A_{1}A_{2}$ and vector
$b=A_{1}b_{2}+b_{1}$. Note that the order is of the matrices is reversed, as
compared to the order of the permutations.

Let us consider now $g=T_{(A,b)}(f)$ and its evaluation
$x^{(g)}=\operatorname{eval}(g)=(x^{(g)}_{0},\ldots,x^{(g)}_{2^{n}-1})$; this
represents a binary vector that is connected to $x^{(f)}$ by a permutation as
follows.

######  Lemma 2.

Assume a $\mathsf{GA}$ transform $T_{(A,b)}$ over $\mathbb{F}_{2}^{n}$ and a
boolean functions $f\in\mathbb{F}_{2}^{[n]}$, then

$x^{\left(T_{(A,b)}(f)\right)}=\pi_{(A,b)}\left(x^{(f)}\right),$

where $\pi_{(A,b)}$ follows Definition 11.

###### Proof.

Let us consider boolean function $g=T_{(A,b)}(f)$; by Definitions 5 and 9, we
have that

$\displaystyle x^{\left(T_{(A,b)}(f)\right)}_{i}$
$\displaystyle=x^{(g)}_{i}=g(\widehat{i})=f\left(A\widehat{i}+b\right)=$ (8)
$\displaystyle=f\left(\widehat{\pi_{(A,b)}(i)}\right)=x^{(f)}_{\pi_{(A,b)}(i)}.$
(9)

∎

As a consequence, binary vector $x^{(g)}$ is a permutation of $x^{(f)}$; this
permutation is the one induced by affine transformation $T_{(A,b)}$, as
expressed in this scheme:

${f}$${x^{(f)}}$${g}$${x^{(g)}}$$\scriptstyle{T_{(A,b)}}$$\scriptstyle{eval}$$\scriptstyle{\pi_{(A,b)}}$$\scriptstyle{eval}$

For convenient (though imprecise) notation we may simply write
$\pi_{A,b}(i)=Ai+b$, presuming the equivalence between an integer $i$ and its
binary expansions $\widehat{i}$; in practice, we will apply affine
transformations or the equivalent permutation on both vectors and boolean
functions, the meaning becoming clear from the context. An example of this
construction can be found in Appendix Boolean functions and permutations.

Operating over binary vectors, Lemma 2 associates a codeword permutation to
each $\mathsf{GA}$ transform, and we will refer to these as _$\mathsf{GA}$
permutations_; note, however, that not all permutations can be represented by
$\mathsf{GA}$ transforms. The $\mathsf{GA}$ permutations group is obviously
isomorphic to the group of affine transformations $\mathsf{GA}(n)$. For
convenience we refer to $\mathsf{GA}(n)$ and the group of permutations simply
as the group $\mathsf{GA}$.

The relation between $\mathsf{GA}$ transforms and permutations as given in
Lemma 2 gives rise to the question how this translates to concatenation. This
is answered in the following lemma.

######  Lemma 3 (Concatenation of $\mathsf{GA}$ permutations).

Given two $\mathsf{GA}$ permutations $\pi_{(A_{1},b_{1})}$ and
$\pi_{(A_{2},b_{2})}$, their concatenation

$\pi_{(A,b)}=\pi_{(A_{2},b_{2})}\circ\pi_{(A_{1},b_{1})},$

namely when $\pi_{A_{1},b_{1}}$ is applied first and $\pi_{A_{2},b_{2}}$
second, is the $\mathsf{GA}$ permutation $T_{(A,b)}$ defined by

$A=A_{1}A_{2}\;,\qquad b=A_{1}b_{2}+b_{1}.$

###### Proof.

As $\mathsf{GA}$ permutations form a group, their composition is obviously
also a $\mathsf{GA}$ transform. The scheme of the concatenation is:

${f}$${g}$${h}$${x^{(f)}}$${x^{(g)}}$${x^{(h)}}$$\scriptstyle{T_{(A,b)}}$$\scriptstyle{eval}$$\scriptstyle{T_{(A_{1},b_{1})}}$$\scriptstyle{eval}$$\scriptstyle{T_{(A_{2},b_{2})}}$$\scriptstyle{eval}$$\scriptstyle{\pi_{(A,b)}}$$\scriptstyle{\pi_{(A_{1},b_{1})}}$$\scriptstyle{\pi_{(A_{2},b_{2})}}$

If we call $\pi_{j}=\pi_{(A_{j},b_{j})}$ and $T_{j}=T_{(A_{j},b_{j})}$ for
$j=1,2$, by Lemma 2 we have that

$\displaystyle\pi_{2}\circ\pi_{1}(x^{(f)}_{i})$
$\displaystyle=x^{(f)}_{\pi_{1}(\pi_{2}(i))}=x^{(T_{1}(f))}_{\pi_{2}(i)}=x^{(g)}_{\pi_{2}(i)}=$
(10) $\displaystyle=x_{i}^{(T_{2}(g))}=x_{i}^{(T_{2}\circ T_{1}(f))}.$ (11)

∎

Given the equivalence between affine transformations and affine permutations,
in the following we may use $\pi$ to define an affine transformation.

In addition to the group $\mathsf{GA}$ itself, we introduce several sub-groups
of $\mathsf{GA}$ and the corresponding permutations. These sub-groups will be
used in the following sections to prove various results concerning the
automorphisms group of polar codes. The following sub-groups are defined by
transformations $T_{(A,b)}$, where $A$ and $B$ assume a peculiar format:

  * •

the _General Linear group_ $\mathsf{GL}$, for which $b=0$;

  * •

the _Lower-Triangular Affine group_ $\mathsf{LTA}$, for which $A$ is lower-
triangular;

  * •

the _Block-Lower-Triangular Affine group_ $\mathsf{BLTA}(S)$, for which $A$ is
block-lower-triangular with profile $S=(s_{1},s_{2},...,s_{l})$ with
$s_{1}+s_{2}+...+s_{l}=n$, i.e. a block diagonal matrix having non-zero
elements below the diagonal;

  * •

the _Upper-Triangular Linear group_ $\mathsf{UTL}$, for which $A$ is upper-
triangular;

  * •

the _Permutation Linear group_ $\mathsf{PL}$, for which $A$ is a permutation
matrix;

  * •

the _Translation group_ $\mathsf{T}$, for which $A$ is the identity matrix.

Similarly to $\mathsf{GA}$ we may use $\mathsf{GL}$, $\mathsf{LTA}$,
$\mathsf{BLTA}$, $\mathsf{UTL}$, and $\mathsf{PL}$ to refer to the
corresponding groups of permutations.

###  III-B The affine automorphisms group of polar codes

######  Definition 12 (Automorphism).

A permutation $\pi$ is called an automorphism of code $\mathcal{C}$ if
$\pi(\mathcal{C})=\mathcal{C}$, i.e., if $\pi(x)\in\mathcal{C}$ for all
$x\in\mathcal{C}$. The set of automorphisms of a code $\mathcal{C}$ is denoted
by $\mathsf{Aut}(\mathcal{C})$ and forms a group.

For monomial codes, the permutations from $\mathsf{GA}$ are of particular
interest, since they represent linear operations on the variables. If a
$\mathsf{GA}$ permutation is an automorphism, we call it a $\mathsf{GA}$ (or
affine) automorphism. We further denote the _group of affine automorphisms_ of
a code $\mathcal{C}$ by

$\mathcal{A}\triangleq\mathsf{GA}\cap\mathsf{Aut}(\mathcal{C}).$ (12)

We consider binary $(N,K)$ polar codes $\mathcal{C}$ of length $N=2^{n}$ and
dimension $K$, having information set $\mathcal{I}$ and monomial set
$\mathcal{G}$ and following UPO framework. In this section, we will prove that
the affine automorphisms group of such a polar code is a $\mathsf{BLTA}$
group. This property has been proved in [13, 14]; in this paper, we provide an
alternative proof based on the introduction of elementary permutations and on
the algebraic structure of the $\mathsf{BLTA}$ group.

To begin with, we notice that $\mathsf{GA}$ permutations map monomials of
$\mathcal{G}$ to linear combinations of monomials in $\mathcal{M}^{[n]}$. A
property of $\mathsf{GA}$ automorphisms is their capacity to map the
generating monomial set into itself.

######  Lemma 4.

$\pi\in\mathcal{A}$ if and only if for every $m_{t}\in\mathcal{G}$, then for
every $m_{t_{1}},\ldots,m_{t_{s}}$ such that

$\pi(m_{t})=m_{t_{1}}+\ldots+m_{t_{s}},$ (13)

we have that $m_{t_{i}}\in\mathcal{G}$.

###### Proof.

This condition is obviously necessary: if all $m_{t_{i}}\in\mathcal{G}$, then
also $\pi(m_{t})\in\mathcal{G}$ for every $m_{t}\in\mathcal{G}$. Conversely,
if $\pi\in\mathcal{A}$, then also $\pi(m_{t})\in\mathcal{G}$. However, in
order for the polynomial $m_{t_{1}}+\ldots+m_{t_{s}}$ to be included into
$\langle\mathcal{G}\rangle$, all its addends must belong to $\mathcal{G}$
because monomials form a base for the code space. ∎

Equipped with these definitions, we now focus on the characterization of
$\mathcal{A}$. To begin with, we prove that $\mathsf{LTA}\subseteq\mathcal{A}$
for any polar code, namely that all the $\mathsf{LTA}$ transformations are
automorphisms; it is worth noticing that this property holds only for polar
codes fulfilling the UPO framework. In order to prove it, we denote the row-
addition elementary matrix by $E_{(i,j)}$, namely the $n\times n$ square
matrix with ones on the diagonal and an additional one at row $i$ and column
$j$. This matrix is associated to the elementary linear transformation

$E_{(i,j)}:\bar{V}_{i}\rightarrow\bar{V}_{i}+\bar{V}_{j}+1,$ (14)

defined by permutation $\epsilon_{(i,j)}=\pi_{(E_{(i,j)},0)}$. This elementary
matrix is of particular interest since every $\mathsf{LTA}$ transformation can
be decomposed as the product of elementary linear transformations having their
one below the diagonal, plus a translation.

######  Lemma 5.

Every $\pi_{(A,b)}\in\mathsf{LTA}$ can be decomposed as

$\pi_{(A,b)}=\epsilon_{(i_{q},j_{q})}\circ\ldots\circ\epsilon_{(i_{1},j_{1})}\circ\tau,$
(15)

where $\epsilon_{(i,j)}$ is an elementary linear transformation,
$\tau\in\mathsf{T}$ and $q$ is the number of nonzero entries of $A$ below the
diagonal.

###### Proof.

To begin with, we prove that every lower triangular matrix $A$ can be written
as a product of $q$ row-addition elementary matrices. To do it, we sort the
nonzero entries of $A$ below the diagonal from top to bottom and then from
left to right: in practice, if $a_{i_{l},j_{l}}$ and $a_{i_{l+1},j_{l+1}}$ are
nonzero entries of $A$, then $i_{l}\leq i_{l+1}$ and, if $i_{l}=i_{l+1}$, then
$j_{l}<j_{l+1}$; in this way, we have that

$A=\prod_{l=1}^{q}E_{(i_{l},j_{l})}.$ (16)

In fact, given a matrix $B$, we have that $B\cdot E_{(i,j)}$ is the matrix
produced from $B$ by adding column $i$ to column $j$; we have that
$i_{l}>j_{l}$ since $A$ is lower triangular, hence realizing the product from
left to right results in adding at every step a nonzero entry in position
$(i_{l},j_{l})$, resulting in matrix $A$. Next, if we define $\tau=\pi_{I,b}$,
the lemma is proved. ∎

When applied to monomials, however, these elementary transformations may lead
to polynomials, making it difficult to connect monomial sets. In fact, given
$m_{t}\in\mathcal{M}^{[n]}$, then

$\epsilon_{(i,j)}(m_{t})=\left\\{\begin{array}[]{lc}m_{t}&\text{if }i\notin
Q\text{ or }i,j\in Q\\\ m_{t}+m_{t^{\prime}}+m_{t^{\prime\prime}}&\text{if
}i\in Q\text{ and }j\in Q\end{array}\right.$ (17)

where $t^{\prime}$ is obtained from $t$ by swapping entries $i$ and $j$ of its
binary expansion and $t^{\prime\prime}$ by adding a one in position $i$ of the
binary expansion of $t$. Lemma 4 shows that $\epsilon_{(i,j)}\in\mathcal{A}$
if and only if for every $m_{t}\in\mathcal{G}$, then $m_{t^{\prime}}$ and
$m_{t^{\prime\prime}}$ obtained from (17) belong to $\mathcal{G}$. In order to
prove the first main result of this section, we need to prove that we can
focus our analysis only on elementary linear transformations, neglecting the
effect of translations. The following lemma gives us this possibility.

######  Lemma 6.

If $\mathcal{C}$ follows UPO framework, then $\mathsf{T}\subset\mathcal{A}$.

###### Proof.

Translation $\tau_{i}\in\mathsf{T}$ maps $\bar{V}_{i}$ to $\bar{V}_{i}+1$.
Then, it maps each monomial in $\mathcal{G}$ including $\bar{V}_{i}$ into the
sum of the monomial itself and the same monomial without $\bar{V}_{i}$; since
the last monomial is included in $\mathcal{G}$ due to the UPO hypothesis, then
$\mathsf{T}\subset\mathcal{A}$. ∎

Since translations are always automorphisms, we can focus on automorphisms in
$\mathsf{GL}$, and more in details we can use elementary linear
transformations to prove the following lemma, that is the first main result of
this section.

######  Theorem 2.

$\mathsf{LTA}\subseteq\mathcal{A}$ if and only if $\mathcal{C}$ follows UPO
framework.

###### Proof.

To begin with, we show that this is a necessary condition. The matrix $A$ of a
given $\mathsf{LTA}$ transformation can be decomposed as a product of
elementary matrices having their extra one below the diagonal. for any of
these elementary transformations $\epsilon_{(i,j)}$, any $m_{t}\in\mathcal{G}$
is transformed into a polynomial $m_{t}+m_{t^{\prime}}+m_{t^{\prime\prime}}$
(or remains the same). By definition, $m_{t^{\prime\prime}}\preceq m_{t}$, and
then, by UPO hypothesis, also $m_{t^{\prime\prime}}\in\mathcal{G}$; moreover,
since by construction $i<j$, also $m_{t^{\prime}}\preceq m_{t}$, and again
$m_{t^{\prime}}\in\mathcal{G}$ by UPO hypothesis. Since all the monomials
forming it belong to $\mathcal{G}$, then also
$\epsilon_{(i,j)}(m_{t})\in\mathcal{G}$ and
$\epsilon_{(i,j)}\in\mathsf{Aut}(\mathcal{C})$ when $i<j$; since the product
of automorphisms is still an automorphism, we have that
$\mathsf{LTA}\subseteq\mathcal{A})$.

To show that it is a sufficient condition, let us proceed by absurd. We
suppose $\mathcal{C}$ not following the UPO framework, namely there exists
some $a\in\mathcal{I}$ for which at least one integer $b$, $a\preceq b$, such
that $b\notin\mathcal{I}$. It is then possible to create a chain of integers
$a=t_{0}\preceq t_{1}\preceq\ldots\preceq t_{r-1}\preceq t_{r}=b$ such that
the passage from an integer to the next one is performed by one of the UPO
basic rules. By absurd hypothesis, there exists an index $s$ such that
$t_{s}\in\mathcal{I}$ and $t_{s+1}\notin\mathcal{I}$. Then, it is possible to
find two integers $i,j$, with $i>j$, such that
$\epsilon_{(i,j)}(m_{t_{s}})=m_{t_{s+1}}+m_{t^{\prime}}$, either by taking the
indices of the swapped entries if $HW(t_{s})=HW(t_{s+1})$ or setting $i$ as
the index of the added one otherwise. By construction,
$\epsilon_{(i,j)}\notin\mathcal{A}$ and then
$\mathsf{LTA}\not\subseteq\mathcal{A}$. ∎

Theorem 2 proves that, if the polar code follows the UPO framework, then
$\mathsf{LTA}\subseteq\mathcal{A}$. Now we expand this result by proving that
the affine automorphisms group of a polar code fulfilling UPO has a
$\mathsf{BLTA}$ structure. To begin with, we prove a lemma regarding
elementary linear transformations.

######  Lemma 7.

If $\mathcal{C}$ follows UPO framework, then $\epsilon_{(i,j)}\in\mathcal{A}$
implies that also $\epsilon_{(i+1,j)},\epsilon_{(i,j-1)}\in\mathcal{A}$.

###### Proof.

According to the hypothesis, for every $m_{t}\in\mathcal{G}$ and
$\epsilon_{(i,j)}\in\mathcal{A}$ such that
$\epsilon_{(i,j)}(m_{t})=m_{t}+m_{t^{\prime}}+m_{t^{\prime\prime}}$, then
$m_{t^{\prime}},m_{t^{\prime\prime}}\in\mathcal{G}$. Then if
$\epsilon_{(i+1,j)}(m_{t})=m_{t}+m_{t_{1}}+m_{t_{2}}$, by construction we have
that $m_{t_{1}}\preceq m_{t^{\prime}}$ and $m_{t_{2}}\preceq
m_{t^{\prime\prime}}$, and hence by UPO hypothesis
$m_{t_{1}},m_{t_{2}}\in\mathcal{G}$ and $\epsilon_{(i+1,j)}\in\mathcal{A}$ by
Lemma 4. Similarly, if
$\epsilon_{(i,j-1)}(m_{t})=m_{t}+m_{t_{3}}+m_{t^{\prime\prime}}$, by
construction we have that $m_{t_{3}}\preceq m_{t^{\prime}}$ and hence by UPO
hypothesis $m_{t_{3}}\in\mathcal{G}$ and $\epsilon_{(i,j-1)}\in\mathcal{A}$ by
Lemma 4. ∎

Lemma 7 will be used to prove the second main result of this section.

######  Theorem 3.

A polar code $\mathcal{C}$ is compliant with the UPO framework if and only if
for some profile $s$ we have that $\mathcal{A}=\mathsf{BLTA}(S)$.

###### Proof.

The condition is necessary since $\mathsf{LTA}\subseteq\mathsf{BLTA}(S)$ for
any profile $S$, and for Theorem 2 $\mathsf{LTA}\subseteq\mathcal{A}$ implies
that $\mathcal{C}$ is compliant with the UPO framework.

To prove that the condition is sufficient, we begin from the observation that
Lemma 7 implies that the affine automorphism group of a code $\mathcal{C}$
following UPO framework has an overlapping block triangular ($\mathsf{OBLT}$)
structure. In practice, this structure is defined by blocks over the diagonal
that can overlap. In the following, we show that such a structure cannot be a
group, and hence a $\mathsf{BLTA}$ is the only ”blocky” matrix structure
compliant with Lemma 7.

$n$$s_{1}$$m$$s_{2}$$i$$j$indices $n-s_{2}-1,\ldots,s_{1}-1$

Figure 2: Structure of OBLT matrix.

In the following, we restrict our analysis to the case depicted in Figure 2,
namely an $\mathsf{OBLT}(s_{1},s_{2})$ structure with $s_{1}+s_{2}>n$ and
$s_{1}>s_{2}$; the results of this case study can be easily extended to more
general $\mathsf{OBLT}$ structures. In the following, we will show that it is
possible to generate a matrix having a non-zero entry in row $i$ and column
$j$, for every $0\leq i<n-s_{2}$ and $n-s_{1}\leq j<n$, as the result of the
multiplication of two matrices belonging to $\mathsf{OBLT}(s_{1},s_{2})$. This
would prove that $\mathsf{OBLT}(s_{1},s_{2})$ is not a group, and the closure
of this set represents the group structure of the automorphisms. Given $i,j$
defined above, elementary matrices $E_{(i,s_{1}-1)}$ and $E_{(s_{1}-1,j)}$
belong to $\mathsf{OBLT}(s_{1},s_{2})$ by construction: the first is included
in the upper block, while the other is included in the lower block. Matrix
$A=E_{(i,s_{1}-1)}\cdot E_{(s_{1}-1,j)}$ is given by $E_{(s_{1}-1,j)}$ but
adding row $s_{1}-1$ to row $i$. As a result, $a_{i,j}=1$, and
$\mathsf{OBLT}(s_{1},s_{2})$ is not a group. ∎

##  IV Classification of affine automorphisms

In this section, we describe a new framework for the analysis of automorphisms
for permutation decoding of polar codes. We introduce the concept of
_permutation decoding equivalence_ for automorphisms; this notion permits to
cluster code automorphisms into classes of automorphisms always providing the
same codeword candidate under permutation decoding, no matter the received
signal. As a consequence, the selection of automorphisms for AE decoding
should avoid automorphisms belonging to the same class. These classes are
generated as cosets of the absorption group of the polar code, which plays a
capital role in the definition of the classes. This result is an extension of
our preliminary analysis of decoder equivalence published in [18].

Next, we focus on the analysis of the absorption group under SC decoding,
providing an alternative proof of a very recent result presented in [19],
namely that the complete SC absorption group has a $\mathsf{BLTA}$ structure.
Thanks to the knowledge of the structure of the SC absorption group, we
calculate the number of the equivalence classes, representing the maximum
number of permutations providing possibly different codeword candidates under
AE-SC decoding. Finally, we propose a practical method to find one
automorphism for each equivalence class, in order to avoid redundant
automorphisms.

###  IV-A Permutation decoding equivalence

We begin by formally defining what is a decoding function of polar codes. We
consider transmission over a binary symmetric memoryless channel with output
$y$ such that

$p(y_{i}|x_{i}=0)=p(-y_{i}|x_{i}=1)$ (18)

for $i=0,1,\ldots,N-1$. An example of such a channel is the BI-AWGN channel,

$y=\tilde{x}+w,$

where $\tilde{x}=\operatorname{bpsk}(x)$ with BPSK mapping
$\operatorname{bpsk}(0)=+1$, $\operatorname{bpsk}(1)=-1$, and $w$ is i.i.d.
Gaussian noise with distribution $\mathcal{N}(0,\sigma^{2})$. We assume a
decoding algorithm for the AWGN channel, operating on the channel outputs222If
the decoder operates on LLRs, we may include the LLR computation into the
channel model. $y$.

######  Definition 13 (Decoding function).

The function

$\displaystyle\operatorname{dec}:\mathbb{R}^{N}$
$\displaystyle\rightarrow\mathcal{C}$ $\displaystyle y$ $\displaystyle\mapsto
x=\operatorname{dec}(y)$ (19)

denotes the decoding function for polar codes.

This definition can be generalized to the notion of decoding function wrapped
by an automorphism. An _automorphism decoder_ is a decoder run on a received
signal that is scrambled according to a code automorphism; the result is then
scrambled back to retrieve the original codeword estimation.

######  Definition 14 (Automorphism decoding function).

For an automorphism $\pi\in\mathsf{Aut}(\mathcal{C})$, the function

$\displaystyle\operatorname{adec}:\mathbb{R}^{N}\times\mathsf{Aut}(\mathcal{C})$
$\displaystyle\rightarrow\mathcal{C}$ (20) $\displaystyle y$
$\displaystyle\mapsto x=\operatorname{adec}(y;\pi)$ (21)

with

$\operatorname{adec}(y;\pi)\triangleq\pi^{-1}(\operatorname{dec}(\pi(y))).$
(22)

is called the automorphism decoding function of the polar code.

$y$$y^{\prime}_{1}$$y^{\prime}_{2}$$y^{\prime}_{M}$$x^{\prime}_{1}$$x^{\prime}_{2}$$x^{\prime}_{M}$$x_{1}$$x_{2}$$x_{M}$$\hat{x}$$\pi_{1}^{-1}$$\pi_{2}^{-1}$$\pi_{M}^{-1}$$\begin{array}[]{c}\text{\small
SC/SCL/BP/SCAN}\\\ \text{decoder}\end{array}$$\begin{array}[]{c}\text{\small
SC/SCL/BP/SCAN}\\\
\text{decoder}\end{array}$$\dots$$\begin{array}[]{c}\text{\small
SC/SCL/BP/SCAN}\\\
\text{decoder}\end{array}$$\pi_{1}$$\pi_{2}$$\pi_{M}$$x=\underset{i=1,\ldots,M}{\mathrm{argmin}}\,||y-x_{i}||$$adec$

Figure 3: Structure of the automorphism ensemble (AE) decoder.

Note that this function may be seen as a decoding function with parameter
$\pi$. Moreover, we focus our analysis on affine automorphisms in
$\mathcal{A}\subseteq\mathsf{Aut}(\mathcal{C})$. An _automorphism ensemble_
(AE) decoder, originally proposed in [10] for Reed-Muller codes, consists of
$M$ automorphism decoders running in parallel, as depicted in Figure 3, where
the codeword candidate is selected using a least-squares metric. Starting from
these definitions, we analyze the effects of automorphism decoding on polar
codes.

######  Definition 15 (Decoder equivalence).

Two automorphisms $\pi_{1},\pi_{2}\in\mathcal{A}$ are called equivalent with
respect to $\operatorname{dec}$, written as $\pi_{1}\sim\pi_{2}$, if

$\operatorname{adec}(y;\pi_{1})=\operatorname{adec}(y;\pi_{2})\quad\text{for
all $y\in\mathbb{R}^{N}$}.$ (23)

This is an equivalence relation, since it is reflexive, symmetric and
transitive. The equivalence classes are defined as

$[\pi]\triangleq\\{\pi^{\prime}\in\mathcal{A}:\pi\sim\pi^{\prime}\\}.$ (24)

The equivalence class $[\mathbbm{1}]$ of the trivial permutation $\mathbbm{1}$
is also called the set of _decoder-absorbed automorphisms_. In fact, for all
$\pi\in[\mathbbm{1}]$,

$\operatorname{adec}(y;\pi)=\operatorname{dec}(y)\quad\text{for all
$y\in\mathbb{R}^{N}$},$ (25)

i.e., these permutations are absorbed by the decoder, or in other words, the
decoding function is invariant to these permutations. This happens also when
an absorbed permutation is concatenated to other permutations. In fact, given
two automorphisms $\pi,\sigma\in\mathcal{A}$, then

$\operatorname{adec}(y;\pi\circ\sigma)=\sigma^{-1}(\operatorname{adec}(\sigma(y);\pi)),$
(26)

and if $\pi\in[\mathbbm{1}]$, we obtain

$\displaystyle\operatorname{adec}(y;\pi\circ\sigma)$
$\displaystyle=\sigma^{-1}(\operatorname{adec}(\sigma(y);\pi))=$ (27)
$\displaystyle=\sigma^{-1}(\operatorname{dec}(\sigma(y)))=\operatorname{adec}(y;\sigma),$
(28)

i.e., the component $\pi$ of the composition $\pi\circ\sigma$ is absorbed. In
the following, we generalize these properties by showing that $[\mathbbm{1}]$
forms a sub-group of $\mathcal{A}$. To begin with, we prove that the inverse
of an absorbed automorphism is also absorbed.

######  Lemma 8.

If $\pi\in[\mathbbm{1}]$, then $\pi^{-1}\in[\mathbbm{1}]$.

###### Proof.

From the definition of the equivalence class, we have that

$\operatorname{dec}(y)=\pi^{-1}(\operatorname{dec}(\pi(y)))\,\,\Leftrightarrow\,\,\pi(\operatorname{dec}(y))=\operatorname{dec}(\pi(y))$
(29)

(with the latter denoting an equivariance); and so

$\displaystyle\operatorname{adec}(y;\pi^{-1})$
$\displaystyle=\pi(\operatorname{dec}(\pi^{-1}(y)))=$ (30)
$\displaystyle=\operatorname{dec}(\pi(\pi^{-1}(y)))=\operatorname{dec}(y).$
(31)

∎

Now we can prove that $[\mathbbm{1}]\leq\mathcal{A}$;

######  Lemma 9.

The equivalence class $[\mathbbm{1}]$ (set of decoder-absorbed automorphisms)
is a subgroup of $\mathcal{A}$, i.e., $[\mathbbm{1}]\leq\mathcal{A}$.

###### Proof.

We prove this lemma using the subgroup test, stating that
$[\mathbbm{1}]\leq\mathcal{A}$ if and only if
$\forall\pi,\sigma\in[\mathbbm{1}]$ then $\pi^{-1}\sigma\in[\mathbbm{1}]$:

$\displaystyle\operatorname{adec}(y;\pi^{-1}\sigma)$
$\displaystyle=(\pi^{-1}\sigma)^{-1}(\operatorname{dec}((\pi^{-1}\sigma)(y)))=$
(32)
$\displaystyle=\sigma^{-1}\left(\pi\left(\operatorname{dec}\left(\pi^{-1}\left(\sigma\left(y\right)\right)\right)\right)\right)=$
(33)
$\displaystyle=\sigma^{-1}\left(\operatorname{dec}\left(\sigma\left(y\right)\right)\right)=$
(34) $\displaystyle=\operatorname{dec}\left(y\right).$ (35)

∎

Now, we use cosets of $[\mathbbm{1}]$ to classify automorphisms into
equivalence classes ($\mathsf{EC}$s) containing permutations providing the
same results under AE decoding.

######  Lemma 10.

Equivalence classes $[\sigma]$ defined by decoder equivalence correspond to
right cosets of $[\mathbbm{1}]$.

###### Proof.

Right cosets of $[\mathbbm{1}]$ are defined as

$[\mathbbm{1}]\sigma\triangleq\\{\pi\circ\sigma:\pi\in[\mathbbm{1}]\\}.$ (36)

Hence, permutations $\sigma_{1},\sigma_{2}\in[\mathbbm{1}]\sigma$ if and only
if there exist two permutations $\pi_{1},\pi_{2}\in[\mathbbm{1}]$ such that
$\sigma_{1}=\pi_{1}\circ\sigma$ and $\sigma_{2}=\pi_{2}\circ\sigma$, where the
second implies $\sigma=\pi_{2}^{-1}\circ\sigma_{2}$. Then the proof is
concluded by

$\displaystyle\operatorname{adec}(y;\sigma_{1})$
$\displaystyle=\operatorname{adec}(y;\pi_{1}\sigma)=$ (37)
$\displaystyle=\operatorname{adec}(y;\pi_{1}\pi_{2}^{-1}\sigma_{2})=\operatorname{adec}(y;\sigma_{2}).$
(38)

∎

According to our notation, two automorphisms in the same $\mathsf{EC}$ always
provide the same candidate under $\operatorname{adec}$ decoding. The number of
non-redundant automorphisms for AE-dec, namely the maximum number of different
candidates listed by an AE-dec decoder, is then given by the number of
equivalence classes of our relation.

######  Lemma 11.

There are $E=\frac{|\mathcal{A}|}{|[\mathbbm{1}]|}$ equivalence classes
$[\pi]$, $\pi\in\mathcal{A}$, all having the same size.

###### Proof.

Follows from Lemma 10 and Lagrange’s Theorem. ∎

The number $E$ of equivalence classes provides an upper bound on the number of
different candidates of an $\operatorname{adec}$ decoder. In fact, all the
permutations included in an equivalence class give the same result under
$\operatorname{adec}$ decoding. Then, when selecting permutations for the
$\operatorname{adec}$ decoder, it is fundamental to select permutations of
different equivalence classes. Moreover, it is useless to select more
permutations than the number of equivalence classes. This observation permits
to control the list size of an $\operatorname{adec}$ decoder. However, the
proposed relation does not assure that, for some value of $y$, two
$\mathsf{EC}$s do not produce the same candidate; in practice, our relation
permits to calculate the maximum number of different results under adec,
providing an upper bound of parameter $M$ of an AE-dec decoder.

Equipped with the definition of equivalence classes under a given decoder, it
is worth analyzing the _redundancy_ of an automorphism set $\mathcal{L}$ used
in an AE decoder. Let us denote by $M=|\mathcal{L}|$ the number of
automorphisms used in the AE decoder; if the elements of $\mathcal{L}$ are
randomly drawn from $\mathcal{A}\setminus[\mathbbm{1}]$, we call $P_{\geq
1}(M)$ the probability of having redundant automorphisms in the set, i.e. that
at least two automorphisms belong to the same equivalence class and hence
provably provide always the same candidates. The probability of having non-
redundant sets is connected to the birthday problem; if we denote by
$E=|\mathsf{EC}|$ the number of equivalence classes under the chosen decoder,
this probability is given by

$P_{\geq 1}(M)=1-P_{0}(M)=1-\prod_{i=0}^{M-1}\frac{E-i}{E},$ (39)

where $P_{m}(M)$ represents the probability of having exactly $m$ redundant
automorphisms. The probability $P_{m}(M)$ is more difficult to compute, since
the $m$ automorphism may belong to the same equivalence classes or from
different equivalence classes. The second possibility being more likely to
happen, we provide a lower bound of $P_{m}(M)$ as the probability of having
$m$ EC with exactly $2$ representatives as

$P_{m}(M)\geq\binom{E}{m}\prod_{k=0}^{m-1}\binom{M-2k}{2}\prod_{k=0}^{M-2m-1}\frac{E-i-m}{E}.$
(40)

The effect of the redundancy of $\mathcal{L}$ will be shown in Section V. In
the next section, we will analyze $\mathsf{EC}$s under SC decoding.

###  IV-B Absorption group of Successive Cancellation decoders

We assume the standard algorithm for SC decoding for the AWGN channel,
operating with the min-approximation of the boxplus operation, with the kernel
decoding equations

$\displaystyle l^{-}$
$\displaystyle=\operatorname{sgn}(l_{0})\cdot\operatorname{sgn}(l_{1})\cdot\min\\{|l_{0}|,|l_{1}|\\},$
$\displaystyle l^{+}$ $\displaystyle=l_{0}+l_{1}.$

This decoder is independent333The decoder with the exact boxplus operation has
similar properties, but depends on the SNR. of the SNR and can directly
operate on the channel outputs $y$ rather than (properly scaled) channel LLRs.
Here we propose again Definitions 13,14 for SC decoding.

######  Definition 16 (SC decoding function).

The function

$\displaystyle\operatorname{\mathsf{SC}}:\mathbb{R}^{N}$
$\displaystyle\rightarrow\mathcal{C}$ $\displaystyle y$ $\displaystyle\mapsto
x=\operatorname{\mathsf{SC}}(y)$ (41)

denotes the decoding function implemented by the SC algorithm (with min-
approximation).

######  Definition 17 (Automorphism SC decoding function).

For an automorphism $\pi\in\mathcal{A}$, the function

$\displaystyle\operatorname{\mathsf{aSC}}:\mathbb{R}^{N}\times\mathcal{A}$
$\displaystyle\rightarrow\mathcal{C}$ (42) $\displaystyle y$
$\displaystyle\mapsto x=\operatorname{\mathsf{aSC}}(y;\pi)$ (43)

with

$\operatorname{\mathsf{aSC}}(y;\pi)\triangleq\pi^{-1}(\operatorname{\mathsf{SC}}(\pi(y))).$
(44)

is called the automorphism SC decoding function.

Again, $\operatorname{\mathsf{aSC}}$ function may be seen as a decoding
function with parameter $\pi$. The notion of SC-absorbed automorphisms group
$[\mathbbm{1}]$ has been introduced in [10] as the set of permutations that
are SC decoding invariant. In the same paper, authors proved that
$\mathsf{LTA}$ automorphisms are absorbed under SC decoding; this result is
reported in the following lemma:

######  Lemma 12 (SC-absorption of $\mathsf{LTA}$).

The group $\mathsf{LTA}$ is SC-absorbed, $\mathsf{LTA}\leq[\mathbbm{1}]$.

###### Proof.

The proof is provided in [10]. ∎

In [10] it was also conjectured that $[\mathbbm{1}]=\mathsf{LTA}$, however
this statement is not true. In fact, the full absorption group of a polar code
may be larger than $\mathsf{LTA}$:

######  Lemma 13.

If $\mathsf{BLTA}(S)$ is the affine permutation group of a polar code with
$s_{1}>1$, then $\mathsf{BLTA}(2,1,\dots,1)<[\mathbbm{1}]$.

###### Proof.

Given $\pi_{(A,b)}\in\mathcal{A}$, to set $a_{0,1}=1$ in matrix $A$
corresponds to map variable $X_{0}$ to variable $a_{0,0}+X_{1}$; in practice
it represents a permutation that identically scrambles 4-uples of the
codeword. To be more precise, the entries $a_{0,0},a_{0,1}$ of $A$ represent a
permutation of the first 4 entries of the codeword, which is repeated
identically for every subsequent block of 4 entries of the vector. Under SC
decoding, this represents a permutation of the entries of the last $4\times 4$
decoding block; in practice, the difference between the
$\operatorname{\mathsf{aSC}}$ decoding of two codewords permuted according two
permutations differing only for entries $a_{0,0},a_{0,1}$ is that entries of
the leftmost $4\times 4$ decoding block are permuted. Since the polar code
follows UPO as stated by Theorem 3, each block of 4 entries of the input
vector can be described as one of the following sequences of frozen (F) and
information (I) bits, listed in increasing rate order with the notation
introduced for fast-SC decoders [21];

  * •

[FFFF]: this represents a rate-zero node, and returns a string of four zeroes
no matter the input LLRs; this is independent of the permutation.

  * •

[FFFI]: this represents a repetition node, and returns a string of four
identical bits given by the sign of the sum of the LLRs; this is independent
of the permutation.

  * •

[FFII]: this case is not possible if $s_{1}>1$.

  * •

[FIII]: this represents a single parity check node, and returns the bit
representing the sign of each LLR while the smallest LLR may be flipped if the
resulting vector has even Hamming weight; permuting them back gives the same
result for the two decoders.

  * •

[IIII]: this represents a rate-one node, and returns the bit representing the
sign of each LLR; permuting them back gives the same result for the two
decoders.

As a consequence, changing entries $a_{0,0},a_{0,1}$ of the permutation matrix
(while keeping it invertible) does not change the result of the
$\operatorname{\mathsf{aSC}}$ decoder. ∎

Recently, authors in [19] extended this result to other $\mathsf{BLTA}$
structures, proving that, under SC decoding, $[\mathbbm{1}]$ is a
$\mathsf{BLTA}$ space, and providing guidance to find the profile of such a
group. Here we reconsider this result, providing a non-constructive proof
based on algebraic reasoning that does not consider the frozen set of the
code.

######  Theorem 4.

If $\mathcal{A}=\mathsf{BLTA}(S)$, then
$[\mathbbm{1}]=\mathsf{BLTA}(S_{\mathbbm{1}})$, with
$S_{\mathbbm{1}}=(s_{1,1},s_{1,2},\ldots,s_{1,j_{1}},s_{2,1},\ldots,s_{2,j_{2}},\ldots,s_{s_{l},1},\ldots,$
$s_{s_{l},j_{l}})$ where $s_{i,1}+\ldots+s_{i,j_{i}}=s_{i}$ for every $1\leq
i\leq l$.

###### Proof.

The proof follows from Lemma 13 and from the same line of reasoning of the
proof of sufficient condition of Theorem 3. ∎

In practice, to construct the profile $S_{\mathbbm{1}}$, the block of size
$s_{i}$ of $S$ is divided into sub-blocks of size
$s_{i,1},\ldots,s_{i,j_{i}}$. Given that both $\mathcal{A}$ and
$[\mathbbm{1}]$ have a $\mathsf{BLTA}$ structure under SC decoding, in order
to count the number of $\mathsf{EC}$s under this decoder we need to calculate
the size of such a group.

######  Lemma 14.

The size of $\mathsf{BLTA}(S)$, with $S=(s_{1},\dots,s_{t})$ and
$\sum_{i=1}^{t}s_{i}=n$, is:

$\displaystyle|\mathsf{BLTA}(S)|$
$\displaystyle=2^{\frac{n(n+1)}{2}}\cdot\prod_{i=1}^{t}\left(\prod_{j=2}^{s_{i}}\left(2^{j}-1\right)\right).$
(45)

###### Proof.

It is well known that
$|\mathsf{GL}(m)|=\prod_{i=0}^{m-1}\left(2^{m}-2^{i}\right)$. From this, we
have that

$\displaystyle|\mathsf{GL}(m)|$
$\displaystyle=\prod_{i=0}^{m-1}\left(2^{m}-2^{i}\right)=$
$\displaystyle=\prod_{i=0}^{m-1}2^{i}\left(2^{m-i}-1\right)=$
$\displaystyle=\left(\prod_{j=0}^{m-1}2^{j}\right)\cdot\left(\prod_{i=0}^{m-1}\left(2^{m-i}-1\right)\right)=$
$\displaystyle=2^{\sum_{j=0}^{m-1}j}\cdot\prod_{i=1}^{m}\left(2^{i}-1\right)=$
$\displaystyle=2^{\frac{m(m-1)}{2}}\cdot\prod_{i=2}^{m}\left(2^{i}-1\right).$

It is worth noting that we rewrote the size of $\mathsf{GL}(m)$ as the product
of the number of lower-triangular matrices and the product of the first $n$
powers of two, diminished by one. This property can be used to simplify the
calculation of $\mathsf{BLTA}(S)$. In fact, each block of the $\mathsf{BLTA}$
structure forms an independent $\mathsf{GA}(s_{i})$ space, having size
$|\mathsf{GA}(s_{i})|$. All the entries above the block diagonal are set to
zero, so they are not taken into account in the size calculation, while the
entries below the block diagonal are free, and can take any binary value.
Then, the size of $\mathsf{BLTA}(S)$ can be calculated as
$|\mathsf{LTA}(n)|=2^{\frac{n(n+1)}{2}}$ multiplied by the product of the
first $s_{i}$ powers of two, diminished by one, for each size block $s_{i}$,
which concludes the proof. ∎

Now we can prove the last result of this section, namely the number of
$\mathsf{EC}$s under SC decoding.

######  Lemma 15.

A polar code of length $N=2^{n}$ with $\mathcal{A}=\mathsf{BLTA}(S)$,
$S=(s_{1},\dots,s_{t})$ and $[\mathbbm{1}]=\mathsf{BLTA}(S_{\mathbbm{1}})$
defined in Theorem 4 has

$E=\frac{|\mathsf{BLTA}(S)|}{|\mathsf{BLTA}(S_{\mathbbm{1}})|}=\frac{\prod_{i=1}^{t}\left(\prod_{j=2}^{s_{i}}\left(2^{j}-1\right)\right)}{\prod_{i=1}^{t}\prod_{l=1}^{j_{i}}\left(\prod_{r=2}^{s_{i,l}}\left(2^{r}-1\right)\right)}.$
(46)

equivalence classes under SC decoding.

###### Proof.

This follows from the application of Lemma 11 and Lemma 14. ∎

Lemma 15 also provides an upper bound on the number of $\mathsf{EC}$s for a
polar code under SC decoding; in fact, since $\mathsf{LTA}<[\mathbbm{1}]$, we
have that

$E=\frac{|\mathsf{BLTA}(S)|}{|[\mathbbm{1}]|}\leq\frac{|\mathsf{BLTA}(S)|}{|\mathsf{LTA}|}=\prod_{i=1}^{t}\left(\prod_{j=2}^{s_{i}}\left(2^{j}-1\right)\right).$
(47)

In the scenario of Lemma 13, the upper bound provided by Lemma 15 on the
number of $\mathsf{EC}$s for a polar code under SC decoding can be rewritten
as

$E=\frac{|\mathsf{BLTA}(S)|}{|\mathsf{BLTA}(2,1,\ldots,1)|}=\frac{1}{3}\prod_{i=1}^{t}\left(\prod_{j=2}^{s_{i}}\left(2^{j}-1\right)\right).$
(48)

###  IV-C Decomposition of equivalence classes under SC decoding

Lemma 11 provides the number of $\mathsf{EC}$s of the
$\operatorname{\mathsf{aSC}}$ decoding relation, however without providing a
method to calculate them. In this section we show how, thanks to the structure
of the automorphism group of polar codes, $\mathsf{EC}$ representatives can be
decomposed in blocks, which can be calculated separately. This decomposition
greatly simplifies the task of listing all the $\mathsf{EC}$s of the relation
for practical application of our proposal.

To begin with, we define the block diagonal matrix
$B=diag(B_{1},\ldots,B_{l})$ where $B_{i}$ is an invertible square matrix in
$\mathsf{GL}(s_{i})$. By definition, $B$ is the transformation matrix of an
automorphism of the code; in the following, we will prove that every
$\mathsf{EC}$ contains at least an automorphism defined by such a matrix. In
particular, we call the equivalence sub-class
$\mathsf{EC}_{i}=\mathsf{GL}(s_{i})/\mathsf{BLTL}(s_{i,1},\ldots,s_{i,j_{i}})$,
namely the set of the cosets of $\mathsf{BLTL}(s_{i,1},\ldots,s_{i,j_{i}})$ in
$\mathsf{GL}(s_{i})$. By definition, we have that
$\prod_{i=1}^{l}|\mathsf{EC}_{i}|=|\mathsf{EC}|$ under SC decoding; in the
following, we prove that a representative of any $\mathsf{EC}$ can be
expressed as the juxtaposition of representatives of equivalence sub-classes.

######  Lemma 16.

For every $B_{i},D_{i}\in\mathsf{GL}(s_{i})$ such that
$B=diag(B_{1},\ldots,B_{l})$ and $D=diag(D_{1},\ldots,D_{l})$ for all
$i=1,\ldots,l$, then $[\pi_{(B,0)}]=[\pi_{(D,0)}]$ if and only if $B_{i}$ and
$D_{i}$ belong to the same coset of
$\mathsf{GL}(s_{i})/\mathsf{BLTA}(s_{i,1},\ldots,s_{i,j_{i}})$.

###### Proof.

First, assume that $B_{i}$ and $D_{i}$ belong to the same equivalence sub-
class for all $i=1,\ldots,l$; since each block is independent,

$BD^{-1}=diag(B_{1}D_{1}^{-1},\ldots,B_{l}D_{l}^{-1})\in\mathsf{BLTA}(S_{\mathbbm{1}})$
(49)

since for every block
$B_{i}D_{i}^{-1}\in\mathsf{BLTL}(s_{i,1},\ldots,s_{i,j_{i}})$. Conversely,
assume $[\pi_{(B,0)}]=[\pi_{(D,0)}]$. This means that
$BD^{-1}\in\mathsf{BLTA}(S_{\mathbbm{1}})$, and given that each block is
independent, $B_{i}D_{i}^{-1}\in\mathsf{BLTL}(s_{i,1},\ldots,s_{i,j_{i}})$ for
all $i=1,\ldots,l$. ∎

Now we can prove that every $\mathsf{EC}$ can be represented by an affine
automorphism whose matrix can be expressed as a block diagonal matrix.

######  Theorem 5.

Every $\mathsf{EC}$ includes at least an affine automorphism whose matrix is
block diagonal.

###### Proof.

Lemma 16 proves the connection between equivalence sub-classes and
$\mathsf{EC}$s; in particular, we have seen that different compositions of
sub-classes lead to different $\mathsf{EC}$s. The proof can be conluded by
proving that the number of ways to compose block diagonal matrices using
representatives of different sub-classes is equal to the number of
$\mathsf{EC}$s; in fact,

$\displaystyle\prod_{i=1}^{l}|\mathsf{EC}_{i}|$
$\displaystyle=\prod_{i=1}^{l}|\mathsf{GL}(s_{i})/\mathsf{BLTA}(s_{i,1},\ldots,s_{i,j_{i}})|=$
(50)
$\displaystyle=\prod_{i=1}^{l}\frac{|\mathsf{GL}(s_{i})|}{|\mathsf{BLTA}(s_{i,1},\ldots,s_{i,j_{i}})|}=$
(51)
$\displaystyle=\prod_{i=1}^{l}\frac{2^{\frac{s_{i}(s_{i}-1)}{2}}\prod_{j=2}^{s_{i}}(2_{j}-1)}{2^{\frac{s_{i}(s_{i}-1)}{2}}\prod_{i=1}^{t}(\prod_{j=2}^{s_{i,j_{t}}}(2^{j}-1))}=$
(52)
$\displaystyle=\frac{\prod_{i=1}^{t}\left(\prod_{j=2}^{s_{i}}\left(2^{j}-1\right)\right)}{\prod_{i=1}^{t}\prod_{l=1}^{j_{i}}\left(\prod_{r=2}^{s_{i,l}}\left(2^{r}-1\right)\right)}=$
(53) $\displaystyle=|\mathsf{EC}|.$ (54)

∎

It is worth noticing that this property holds when
$\mathsf{LTA}\leq[\mathbbm{1}]$; if the absorption group is smaller, the
property may not be true. This property can be used to efficiently list all
the equivalence classes under SC decoding. In fact, each block of the
$\mathsf{BLTA}$ automorphism group can be searched independently, and the
resulting sub-classes can be merged to find all the equivalence classes.

Focusing on a sub-class $\mathsf{EC}_{i}$, we propose to use PUL matrix
decomposition to further simplify the representatives search.

######  Definition 18 (PUL decomposition).

The matrices $P\in\mathsf{PL}$, $U\in\mathsf{UTL}$ and $L\in\mathsf{LTL}$ form
the PUL decomposition of invertible matrix $A$ if $A=PUL$.

The PUL decomposition exists for all $A\in\mathsf{GL}$ and is not necessarily
unique; this is due to the non-uniqueness of the LU decomposition, of which
the PUL decomposition is merely a variation. We extend the notion of PUL
decomposition to automorphisms $\pi_{(A,b)}\in\mathcal{A}$, corresponding to
the concatenation of the permutations as

$\pi_{(A,b)}=\pi_{(L,b)}\circ\pi_{(U,0)}\circ\pi_{(P,0)},$ (55)

applied from right to left. By Lemma 12, we have that under SC decoding
$\pi_{L,b}\in[\mathbbm{1}]$. In the following, we show that representatives of
$\mathsf{EC}$s can be decomposed as the product of two automorphisms, one
belonging to $\mathsf{UTL}$ and the other belonging to $\mathsf{PL}$. If we
call $\mathcal{A}_{\mathcal{P}}$ and $\mathcal{A}_{\mathcal{U}}$ the subgroups
of $\mathcal{A}$ containing only $\mathsf{PL}$ and $\mathsf{UTL}$
automorphisms respectively, we can always find an $\mathsf{EC}$ representative
composing elements from these two sets.

######  Lemma 17.

Each $\mathsf{EC}$ contains at least an automorphism $P\cdot U$ with
$P\in\mathcal{A}_{\mathcal{P}}$ and $U\in\mathcal{A}_{\mathcal{U}}$.

###### Proof.

By Theorem 5 we know that every $\mathsf{EC}$ includes an affine automorphism
$\pi_{(D,b)}$ such that $D=diag(D_{1},\ldots,D_{l})$. Every sub-matrix $D_{i}$
has PUL decomposition $D_{i}=P_{i}U_{i}L_{i}$, and we define
$P=diag(P_{1},\ldots,P_{l})$, $U=diag(U_{1},\ldots,U_{l})$ and
$L=diag(L_{1},\ldots,L_{l})$, with $P\in\mathcal{A}_{\mathcal{P}}$ and
$U\in\mathcal{A}_{\mathcal{U}}$. then, we have that

$\displaystyle\pi_{(D,b)}$ $\displaystyle=\pi_{(diag(D_{1},\ldots,D_{l}),b)}=$
(56) $\displaystyle=\pi_{(diag(P_{1}U_{1}L_{1},\ldots,P_{l}U_{l}L_{l}),b)}=$
(57) $\displaystyle=\pi_{(PUL,b)}=$ (58)
$\displaystyle=\pi_{(L,b)}\circ\pi_{(U,0)}\circ\pi_{(P,0)},$ (59)

and since $\pi_{(L,b)}\in[\mathbbm{1}]$ we have that
$[\pi_{(D,b)}]=[\pi_{(U,0)}\circ\pi_{(P,0)}]$. ∎

The proof of the previous lemma is constructive, in the sense that it proposes
a method to list all $\mathsf{EC}$s by mixing $\mathsf{UTL}$ and $\mathsf{PL}$
automorphisms that are block diagonal. In fact, in order to generate an
$\mathsf{EC}$ candidate matrix $A$, it is sufficient to randomly draw $l$
$\mathsf{UTL}$ matrices $U_{1},\ldots,U_{l}$ and $l$ $\mathsf{PL}$ matrices
$P_{1},\ldots,P_{l}$, of size $s_{1},\ldots,s_{l}$ respectively, create the
block diagonal matrices $U=diag(U_{1},\ldots,U_{l})$ and
$P=diag(P_{1},\ldots,P_{l})$ and generate $A=P\cdot U$. By listing all the
possible matrices $P$ and $U$, Lemma 16 ensures that all the $\mathsf{EC}$s
will be found.

However, since the PUL decomposition of a matrix is not unique, this method is
redundant, in the sense that it may generate multiple representatives of the
same $\mathsf{EC}$. A further check is required to assure that the
$\mathsf{EC}$ representative does not belong to an already calculated
$\mathsf{EC}$. This check is done by multiplying the calculated $P\cdot U$
matrix and the $P\cdot U$ matrices of the previously calculated $\mathsf{EC}$s
as stated in Lemma 18.

######  Lemma 18.

Given $\pi_{1},\pi_{2}\in\mathcal{A}$ having transformation matrices
$A_{1},A_{2}$, then $\pi_{1}\in[\pi_{2}]$ if and only if $A_{1}\cdot
A_{2}^{-1}\in\mathsf{BLTA}(S_{\mathbbm{1}})$.

###### Proof.

This follows directly from the definitions of $\mathsf{EC}$ and
$[\mathbbm{1}]$. ∎

We can now propose a practical method to create the automorphisms list
$\mathcal{L}$, including an automorphism for every $\mathsf{EC}$. The idea is
to start by dividing the affine transformation matrix in $l$ blocks of size
$s_{1},\ldots,s_{l}$. For each block, all the matrices belonging to
$\mathcal{U}(s_{i})$ and $\mathcal{P}(s_{i})$, namely the group of upper
triangular and permutation matrices of size $s_{i}$, are calculated. Next, all
the block upper diagonal matrices $U\in\mathcal{A}_{\mathcal{U}}$ having
matrices in $\mathcal{U}(s_{i})$ on the diagonal are calculated, along with
all the block permutation matrices $P\in\mathcal{A}_{\mathcal{P}}$ having
matrices in $\mathcal{P}(s_{i})$ on the diagonal; each block diagonal matrix
is considered ad the affine transformation matrix of a representative of an
$\mathsf{EC}$ and included in $\mathcal{L}$, after checking that the new
automorphisms is not includes in any coset already included in the list as
stated in Lemma 17. Next, matrices in the form $P\cdot U$ are included in the
list if they pass the check of Lemma 17. When $|\mathsf{EC}|$ representatives
are found, the searching process stops.

In order to evaluate the complexity of the proposed method, we need to
evaluate the number of matrices that are generated during the process. By
construction, we have that

$|\mathcal{U}(s_{i})|=2^{\frac{s_{i}(s_{i}-1)}{2}}\quad,\quad|\mathcal{P}(s_{i})|=s_{i}!~{}.$
(60)

For a block structure $S=(s_{1},\dots,s_{t})$, the number of $\mathsf{UTL}$
and $\mathsf{PL}$ automorphisms are:

$|\mathcal{A}_{\mathcal{U}}|=\prod_{i=1}^{t}2^{\frac{s_{i}(s_{i}-1)}{2}}\quad,\quad|\mathcal{A}_{\mathcal{P}}|=\prod_{i=1}^{t}s_{i}!~{}.$
(61)

Hence, the number of generated matrix is given by

$|\mathcal{A}_{\mathcal{U}}|+|\mathcal{A}_{\mathcal{P}}|+|\mathcal{A}_{\mathcal{U}}|\cdot|\mathcal{A}_{\mathcal{P}}|.$
(62)

It is worth noticing that if $[\mathbbm{1}]=\mathsf{LTA}$ then every
$\mathsf{EC}$ include only one $\mathsf{UTL}$ or $\mathsf{PL}$ matrix, such
that
$\mathcal{A}_{\mathcal{U}}\cup\mathcal{A}_{\mathcal{P}}\subset\mathcal{L}$. An
example of this construction can be found in Appendix $\mathsf{EC}$
representatives calculation.

##  V Numerical results

In this section, we present a numerical analysis of error correction
performance of AE decoders. Simulation results are obtained under BPSK
modulation over the AWGN channel. We analyze polar codes having meaningful
affine automorphism groups, decoded under AE-$M$-$\operatorname{dec}$ where
$M$ represents the number of parallel $\operatorname{adec}$ decoders. For each
code, we provide the minimum information set $\mathcal{I}_{min}$, the affine
automorphism group $\mathcal{A}$ and the SC absorption group $[\mathbbm{1}]$.
Automorphism set $\mathcal{L}$ are generated according to the method described
in Lemma 18; the results obtained are compared to a random selection of
automorphisms. We compare error-correction performance of proposed polar codes
to 5G polar codes under CRC-aided SCL [4]; ML bounds depicted in the figures
are retrieved with the truncated union bound, computed with the minimum
distance $d_{min}$ and the number of minimum distance codewords of the code
[11].

Figure 4: Error-correction performance of $(128,85)$ polar codes under AE-SC
decoding.

Figure 4 shows the performance of AE-SC decoding for the $(128,85)$ code
defined by $\mathcal{I}_{min}=\\{23,25\\}$ and having
$\mathcal{A}=\mathsf{BLTA}(3,1,3)$. Following the procedure of Lemma 13, it is
possible to prove that this code has sequences of length $8$ of frozen and
information bits that are invariant under SC decoding, thus
$[\mathbbm{1}]=\mathsf{BLTA}(3,1,1,1,1)$ [19]. This code has $E=21$
equivalence classes, so a set $\mathcal{L}$ composed of $21$ $\mathsf{EC}$
representatives provides a bound on the decoding performance of
AE-$\operatorname{\mathsf{SC}}$ decoding. AE with a set of $M=3$ randomly
drawn automorphisms suffers from a significant loss with respect to AE having
a set composed of $M=3$ $\mathsf{EC}$ representatives; this loss is eliminated
by drawing an additional automorphism, setting $M=4$. In this case, a set of
$21$ random automorphisms is essentially matching the AE bound; the impact of
new non-redundant automorphisms seems to be reducing with the list size $M$,
and a small number of equivalence classes $E$ reduces the effect of the AE
decoder. Performance of 5G polar code decoded under CA-SCL with $L=4$ is
plotted as a reference; proposed polar code under AE decoding outperforms CA-
SCL 5G polar code for BLER$\geq 10^{-3}$, while 5G polar code shows better
performance for lower BLER, however at a larger decoding cost.

Figure 5: Error-correction performance of $(256,95)$ polar codes under AE-SC
and AE-SCAN decoding.

Next, in Figure 5 we investigate the error-correction performance of the
$(256,95)$ code defined by $\mathcal{I}_{min}=\\{55,120,228\\}$ and having
$\mathcal{A}=\mathsf{BLTA}(2,1,1,1,3)$. The number of $\mathsf{EC}$s under SC
decoding for this code can be calculated as $E=21$ by knowing that
$[\mathbbm{1}]=\mathsf{BLTA}(2,1,1,1,1,1,1)$. For $M=7$, AE-SC decoding with a
random automorphism set suffers from a loss with respect to AE-SC decoding
performed with automorphisms from $7$ distinct $\mathsf{EC}$s. The bound under
AE-SC decoding is obtained by using $M=21$ non-redundant automorphisms, one
representative from each $\mathsf{EC}$. However, this AE bound is far away
from the ML bound of the code; then, the error-correction performance under
AE-SCAN decoding is analyzed. We observe that error-correction performance of
AE-$2$-SCAN with a set composed of two $\mathsf{LTA}$ automorphisms is not
equivalent to the error-correction performance of SCAN. Thus, the absorption
group of SCAN is smaller than $\mathsf{LTA}$, permitting to use additional
automorphisms without redundancy; the characterization of the absorption set
under SCAN decoding, that we conjecture to be limited to the trivial
permutation, is still an open problem. Decoding performance of AE-$64$-SCAN
designed with a set of $64$ random automorphism from
$\mathsf{BLTA}(2,1,1,1,3)$ matches the ML bound for low BLER.

Figure 6: Error-correction performance of $(128,60)$ polar code with
$\mathcal{A}=\mathsf{BLTA}(3,4)$ under AE-SC.

Figure 6 shows the error-correction of $(128,60)$ code defined by
$\mathcal{I}_{min}=\\{27\\}$. This code has $\mathcal{A}=\mathsf{BLTA}(3,4)$
and SC absorption group
$[\mathbbm{1}]_{\operatorname{\mathsf{SC}}}=\mathsf{BLTA}(2,1,1,1,1,1)$. Under
SC decoding, the code exhibits $E=2205$ $\mathsf{EC}$s permitting to match the
ML bound under AE-SC when $M=2205$ non-redundant automorphisms are used. Given
the large number of ECs, the probability for a random set of automorphisms to
include redundant permutation is quite small; as an example, $P_{\leq
1}(8)=0.0126$. A more accurate analysis shows that for large sets
$\mathcal{L}$, some $\operatorname{\mathsf{aSC}}$ decoding units returns the
correct codeword, whereas AE-SC decoder selects another codeword based on the
least-square metric. To overcome this problem, we introduced a short CRC of
$3$ bits; simulation results show that in this way it is possible to beat the
ML bound of the code with only $M=64$ automorphisms. However, the introduction
of a CRC is not always useful; in fact, its introduction for the previously
analyzed codes did not provide any benefit. How and when to introduce a CRC
under AE-SC decoding is still an open problem. Finally, we note that the code
investigated has a good ML bound allowing the error correction performance of
AE decoding with $M=8$ to outperform 5G polar code decoded under CA-SCL-$8$
decoding.

##  VI Conclusions

In this paper, we introduced the notion of redundant automorphisms of polar
codes under AE decoding. This notion permits to greatly reduce the number of
automorphisms that can be used in AE-SC decoding of polar codes. Moreover, by
analyzing the number of non-redundant automorphisms it is possible to have an
idea of the impact of an AE-SC dedoder: in fact, even if a polar code has a
large affine automorphism group, if it SC absorption group is too large, the
number of distinct codeword candidate under AE-SC decoding may be too small.
Then, we introduced a method to generate a set if non-redundant automorphisms
to be used in AE-SC decoding. All these results were made possible by a
preliminar analysis of the structure of the affine automorphism group of polar
codes. We proposed a novel approach to prove the most recent results in this
field, and we provide a proof of the equivalence between decreasing monomial
codes and polar codes following UPO. Simulation results show the goodness of
our approach, however leaving open various problems: the structure of the
absorption group of decoding algorithms other than SC, e.g. BP or SCAN, is
still unknown, while it is not clear if it is possible to further reduce the
automorphism set size by eliminating automorphisms providing the same result
under a given received signal $y$. With our paper, we hope to provide new
tools to help the researcher to answer to these and to other question related
to AE decoding of polar codes, a really promising decoding algorithm for high
parallel implementations.

## References

  * [1] 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, July 2009.
  * [2] I. Tal and A. Vardy,  “List decoding of polar codes,”  IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2213–2226, May 2015.
  * [3] K. Niu and K. Chen,  “CRC-aided decoding of polar codes,”  IEEE Communications Letters, vol. 16, pp. 1668–1671, Oct. 2012\.
  * [4] V. Bioglio, C. Condo, and I. Land,  “Design of polar codes in 5G New Radio,”  IEEE Communications Surveys & Tutorials, vol. 23, no. 1, Jan. 2021\.
  * [5] N. Doan, S. A. Hashemi, M. Mondelli, and W. J. Gross,  “On the decoding of polar codes on permuted factor graphs,”  in IEEE Global Communications Conference (GLOBECOM), Abu Dhabi, Dec. 2018.
  * [6] A. Elkelesh, M. Ebada, S. Cammerer, and S. ten Brink,  “Belief propagation list decoding of polar codes,”  IEEE Communications Letters, vol. 22, no. 8, pp. 1536–1539, Aug 2018.
  * [7] C. Pillet, C. Condo, and V. Bioglio,  “SCAN list decoding of polar codes,”  in IEEE International Conference on Communications (ICC), Dublin, Ireland, June 2020.
  * [8] M. Kamenev, Y. Kameneva, O. Kurmaev, and A. Maevskiy,  “Permutation decoding of polar codes,”  in International Symposium ”Problems of Redundancy in Information and Control Systems” (REDUNDANCY), Moscow, Russia, Oct. 2019.
  * [9] MacWilliams F.J. and Sloane N.J.A.,  The theory of error correcting codes,  North-Holland Publishing Company, 1977.
  * [10] M. Geiselhart, A. Elkelesh, M. Ebada, S. Cammerer, and S. ten Brink,  “Automorphism ensemble decoding of Reed-Muller codes,”  IEEE Transactions on Communications, vol. 69, no. 10, pp. 6424–6438, 2021.
  * [11] M. Bardet, V. Dragoi, A. Otmani, and J. Tillich,  “Algebraic properties of polar codes from a new polynomial formalism,”  in IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, July 2016.
  * [12] C. Pillet, V. Bioglio, and I. Land,  “Polar codes for automorphism ensemble decoding,”  in IEEE Information Theory Workshop (ITW), 2021, pp. 1–6.
  * [13] M. Geiselhart, A. Elkelesh, M. Ebada, S. Cammerer, and S. ten Brink,  “On the automorphism group of polar codes,”  in IEEE International Symposium on Information Theory (ISIT), Melbourne, Australia, 2021.
  * [14] Y. Li, H. Zhang, R. Li, J. Wang, W. Tong, G. Yan, and Z. Ma,  “The complete affine automorphism group of polar codes,”  in 2021 IEEE Global Communications Conference (GLOBECOM), 2021, pp. 01–06.
  * [15] K. Ivanov and R. Urbanke,  “Polar codes do not have many affine automorphisms,”  in arXiv preprint arXiv:2112.12495., Dec. 2021.
  * [16] M. Kamenev,  “Improved permutation-based successive cancellation decoding of polar codes,”  in IEEE International Conference of Young Professionals in Electron Devices and Materials (EDM), Souzga, Russia, July 2021.
  * [17] C. Schürch,  “A partial order for the synthesized channels of a polar code,”  in IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, July 2016.
  * [18] C. Pillet, V. Bioglio, and I. Land,  “Classification of automorphisms for the decoding of polar codes,”  in IEEE International Conference on Communications (ICC), Seoul, South Kore, May 2022.
  * [19] Z. Ye, Y. Li, H. Zhang, R. Li, J. Wang, G. Yan, and Z. Ma,  “The complete SC-invariant affine automorphisms of polar codes,”  in arXiv preprint arXiv:2201.12714, Feb. 2022.
  * [20] M. Bóna,  Combinatorics of permutations,  CRC Press, 2012.
  * [21] G. Sarkis, P. Giard, A. Vardy, C. Thibeault, and W. J. Gross,  “Fast polar decoders: algorithm and implementation,”  IEEE Journal on Selected Areas in Communications, vol. 32, no. 5, pp. 946–957, May 2014.

## Boolean functions and permutations

TABLE II: Truth table for boolean function $f$ in (63). $i$ |  | $\widehat{i}$ |  | $\operatorname{eval}(\bar{V}_{0})$ | $\operatorname{eval}(\bar{V}_{1})$ | $\operatorname{eval}(\bar{V}_{2})$
---|---|---|---|---|---|---
0 | 0 | 0 | 0 | 1 | 1 | 1
1 | 1 | 0 | 0 | 0 | 1 | 1
2 | 0 | 1 | 0 | 1 | 0 | 1
3 | 1 | 1 | 0 | 0 | 0 | 1
4 | 0 | 0 | 1 | 1 | 1 | 0
5 | 1 | 0 | 1 | 0 | 1 | 0
6 | 0 | 1 | 1 | 1 | 0 | 0
7 | 1 | 1 | 1 | 0 | 0 | 0

Boolean function $f\in\mathbb{F}_{2}^{[3]}$ defined by

$f=\bar{V}_{2}\oplus\bar{V}_{0}\bar{V}_{1}\oplus\bar{V}_{0}\bar{V}_{2}\oplus\bar{V}_{1}\bar{V}_{2}=m_{3}+m_{4}+m_{2}+m_{1}$
(63)

can be easily evaluated on the basis of single variable evaluations given by

$\displaystyle x^{(m_{6})}=\operatorname{eval}(\bar{V}_{0})=$ $\displaystyle
10101010$ $\displaystyle x^{(m_{5})}=\operatorname{eval}(\bar{V}_{1})=$
$\displaystyle 11001100$ $\displaystyle
x^{(m_{3})}=\operatorname{eval}(\bar{V}_{2})=$ $\displaystyle 11110000$

Each single variable evaluation is described by a column of the Truth Table
II. In fact, the evaluation of function $f$ is given by

$x^{(m_{3})}=\operatorname{eval}(\bar{V}_{2})$ | $11110000$ | $\oplus$
---|---|---
$x^{(m_{4})}=\operatorname{eval}(\bar{V}_{0}\bar{V}_{1})$ | $10001000$ | $\oplus$
$x^{(m_{2})}=\operatorname{eval}(\bar{V}_{0}\bar{V}_{2})$ | $10100000$ | $\oplus$
$x^{(m_{1})}=\operatorname{eval}(\bar{V}_{1}\bar{V}_{2})$ | $11000000$ | $=$
$x^{(f)}=\operatorname{eval}(f)$ | $00011000$ |

Now let us apply left shift permutation $\sigma_{j}$ to this vector, where
$\sigma_{j}(i)=[i+j]_{2^{n}}$, with $[\cdot]_{2^{n}}$ representing modulo
$2^{n}$ operation; according to our notation, element in $i$ is replaced by
element in $[i+j]_{2^{n}}$. Double left shift $\sigma_{2}$ can be expressed as
an affine transformation, while $\sigma_{3}$ cannot; for $n=3$, $\sigma_{2}$
can be expressed as an affine transformation defined by

$\displaystyle A$ $\displaystyle=\left[\begin{smallmatrix}1&0&0\\\ 0&1&0\\\
0&1&1\end{smallmatrix}\right],$ $\displaystyle b$
$\displaystyle=\left[\begin{smallmatrix}0\\\ 1\\\ 0\end{smallmatrix}\right].$

Let us take boolean function $g\in\mathbb{F}_{2}^{[3]}$ defined by
$g=\bar{V}_{0}\bar{V}_{2}\oplus\bar{V}_{1}\bar{V}_{2}=m_{2}+m_{1}$, having
evaluation $x^{(g)}=01100000$. According to Lemma 2, we have that
$\sigma_{2}\left(x^{(f)}\right)=x^{(g)}$ when $g=\sigma_{2}(f)$. In fact,
according to its affine transformation definition, $\sigma_{2}$ maps

$\displaystyle\bar{V}_{0}\mapsto\bar{V}_{0},$
$\displaystyle\bar{V}_{1}\mapsto\bar{V}_{1}\oplus 1,$
$\displaystyle\bar{V}_{2}\mapsto\bar{V}_{1}\oplus\bar{V}_{2}\oplus 1.$

It is worth noticing that the use of negative monomials adds a ”$\oplus 1$”
addend compared to positive monomials when the number of output variables is
even. It is easy to verify that applying this variables substitutions to
boolean function $f$ leads to boolean function $g$.

##  $\mathsf{EC}$ representatives calculation

Here we provide an example of the generation of automorphisms list
$\mathcal{L}$ according to the proposed method. We analyze the $(256,95)$ code
defined by $\mathcal{I}_{min}=\\{55,120,228\\}$ and having
$\mathcal{A}=\mathsf{BLTA}(2,1,1,1,3)$, whose error correction performance are
depicted in Figure 5. According to Lemma 14, this code has

$|\mathcal{A}|=2^{\frac{8(8+1)}{2}}\cdot\prod_{i=1}^{5}\left(\prod_{j=2}^{s_{i}}\left(2^{j}-1\right)\right)=2^{36}\cdot(3)\cdot(3\cdot
7)=63\cdot 2^{36}$ (64)

affine automorphisms. This code has SC absorption group
$[\mathbbm{1}]=\mathsf{BLTA}(2,1,1,1,1,1,1)$, and again for Lemma 14 the
number of SC absorbed affine automorphisms is given by

$|[\mathbbm{1}]|=2^{\frac{8(8+1)}{2}}\cdot\prod_{i=1}^{7}\left(\prod_{j=2}^{s_{i}}\left(2^{j}-1\right)\right)=3\cdot
2^{36}.$ (65)

According to Lemma 11, there are $E=\frac{|\mathcal{A}|}{|[\mathbbm{1}]|}=21$
equivalence classes under SC decoding, as confirmed by Lemma 15. So, there are
only $21$ possible different outcomes under AE-SC decoding, greatly reducing
the maximum size $M$ of the AE decoder.

In the following, we use the result of Lemma 17 to create a list of $21$
affine automorphisms belonging to different equivalence classes under SC
decoding. In this case, there are $|\mathcal{A}_{\mathcal{U}}|=16$
$\mathsf{UTL}$ automorphisms and $|\mathcal{A}_{\mathcal{P}}|=12$
$\mathsf{PL}$ automorphisms; it is worth noticing that
$|\mathcal{A}_{\mathcal{U}}|+|\mathcal{A}_{\mathcal{P}}|>21$ since
$[\mathbbm{1}]\subsetneq\mathsf{LTA}$, so automorphisms in
$\mathcal{A}_{\mathcal{U}}$ and $\mathcal{A}_{\mathcal{P}}$ are not all
included in $[\mathbbm{1}]$. To begin with, we generate all the $16$ UTL
automorphisms composing $\mathcal{A}_{\mathcal{U}}$; each of them has the form
$\pi_{(U,0)}$ where

$U=\begin{bmatrix}U_{1}&&&&0\\\ &1&&&\\\ &&1&&\\\ &&&1&\\\ 0&&&&U_{5}\\\
\end{bmatrix},$ (66)

and $U_{1}$ is a $2\times 2$ $\mathsf{UTL}$ matrix, while $U_{5}$ is a
$3\times 3$ $\mathsf{UTL}$ matrix. There are only $2$ $\mathsf{UTL}$ matrices
of size 2 and $8$ $\mathsf{UTL}$ matrices of size $3$; combining them in $U$
it is possible to list all the $16$ $\mathsf{UTL}$ affine automorphisms of the
code. Similarly, a $\mathsf{PL}$ automorphism of the code is described by
where

$P=\begin{bmatrix}P_{1}&&&&0\\\ &1&&&\\\ &&1&&\\\ &&&1&\\\ 0&&&&P_{5}\\\
\end{bmatrix}$ (67)

and $P_{1}$ is a $2\times 2$ $\mathsf{PL}$ matrix and $P_{5}$ is a $3\times 3$
$\mathsf{PL}$ matrix. Again, there are only $2$ $\mathsf{PL}$ matrices of size
2 and $6$ $\mathsf{PL}$ matrices of size $3$, for a total of $12$
$\mathsf{PL}$ automorphisms. In order to generate
$\mathcal{L}=\\{\pi_{i},\ldots,\pi_{21}\\}$, where $\pi_{i}=\pi_{{A_{i},0}}$,
we begin by setting $A_{1}=I$, such that $[\pi_{1}]=[\mathbbm{1}]$. Next, we
star adding to $\mathcal{L}$ the elements of $\mathcal{A}_{\mathcal{U}}$; only
$7$ of them can be added, an they are listed as $A_{2},\ldots,A_{8}$. This
happens because the first block $U_{1}$ of an $\mathsf{UTL}$ matrix $U$ is
always included in the absorption group, and hence only the matrices having
different last block $U_{5}$ can be included, as stated by Lemma 18. Next,
elements of $\mathcal{A}_{\mathcal{P}}$ are added; only $5$ of them are
independent from the already included ones, and they are listed as
$A_{9},\ldots,A_{13}$. Finally, the remaining elements of $\mathcal{L}$ need
to be calculated as $P\cdot U$, with $U\in\mathcal{A}_{\mathcal{U}}$ and
$P\in\mathcal{A}_{\mathcal{P}}$, as stated in Lemma 17. There are
$|\mathcal{A}_{\mathcal{U}}|\cdot|\mathcal{A}_{\mathcal{P}}|=192$ possible
combinations of $\mathsf{UTL}$ an $\mathsf{PL}$ automorphisms; however, it is
not mandatory to calculate all of them, since when the remaining $8$
independent matrices are calculated, the process can stop. Finally, we can
generate the automorphism list $\mathcal{L}=\\{\pi_{i},\ldots,\pi_{21}\\}$,
where $\pi_{i}=\pi_{{A_{i},0}}$ and

$\displaystyle A_{1}$
$\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\ 0&1&0&0&0&0&0&0\\\
0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\ 0&0&0&0&0&1&0&0\\\
0&0&0&0&0&0&1&0\\\ 0&0&0&0&0&0&0&1\end{smallmatrix}\right],$ $\displaystyle
A_{2}$ $\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0\\\ 0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\
0&0&0&0&0&1&0&0\\\ 0&0&0&0&0&0&1&1\\\
0&0&0&0&0&0&0&1\end{smallmatrix}\right],$ $\displaystyle A_{3}$
$\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\ 0&1&0&0&0&0&0&0\\\
0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\ 0&0&0&0&0&1&0&1\\\
0&0&0&0&0&0&1&0\\\ 0&0&0&0&0&0&0&1\end{smallmatrix}\right],$ $\displaystyle
A_{4}$ $\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0\\\ 0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\
0&0&0&0&0&1&0&1\\\ 0&0&0&0&0&0&1&1\\\
0&0&0&0&0&0&0&1\end{smallmatrix}\right],$ $\displaystyle A_{5}$
$\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\ 0&1&0&0&0&0&0&0\\\
0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\ 0&0&0&0&0&1&1&0\\\
0&0&0&0&0&0&1&0\\\ 0&0&0&0&0&0&0&1\end{smallmatrix}\right],$ $\displaystyle
A_{6}$ $\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0\\\ 0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\
0&0&0&0&0&1&1&0\\\ 0&0&0&0&0&0&1&1\\\
0&0&0&0&0&0&0&1\end{smallmatrix}\right],$ $\displaystyle A_{7}$
$\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\ 0&1&0&0&0&0&0&0\\\
0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\ 0&0&0&0&0&1&1&1\\\
0&0&0&0&0&0&1&0\\\ 0&0&0&0&0&0&0&1\end{smallmatrix}\right],$ $\displaystyle
A_{8}$ $\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0\\\ 0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\
0&0&0&0&0&1&1&1\\\ 0&0&0&0&0&0&1&1\\\
0&0&0&0&0&0&0&1\end{smallmatrix}\right],$ $\displaystyle A_{9}$
$\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\ 0&1&0&0&0&0&0&0\\\
0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\ 0&0&0&0&0&0&0&1\\\
0&0&0&0&0&1&0&0\\\ 0&0&0&0&0&0&1&0\end{smallmatrix}\right],$ $\displaystyle
A_{10}$ $\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0\\\ 0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\
0&0&0&0&0&0&1&0\\\ 0&0&0&0&0&0&0&1\\\
0&0&0&0&0&1&0&0\end{smallmatrix}\right],$ $\displaystyle A_{11}$
$\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\ 0&1&0&0&0&0&0&0\\\
0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\ 0&0&0&0&0&0&1&0\\\
0&0&0&0&0&1&0&0\\\ 0&0&0&0&0&0&0&1\end{smallmatrix}\right],$ $\displaystyle
A_{12}$ $\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0\\\ 0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\
0&0&0&0&0&1&0&0\\\ 0&0&0&0&0&0&0&1\\\
0&0&0&0&0&0&1&0\end{smallmatrix}\right],$ $\displaystyle A_{13}$
$\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\ 0&1&0&0&0&0&0&0\\\
0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\ 0&0&0&0&0&0&0&1\\\
0&0&0&0&0&0&1&0\\\ 0&0&0&0&0&1&0&0\end{smallmatrix}\right],$ $\displaystyle
A_{14}$ $\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0\\\ 0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\
0&0&0&0&0&0&1&1\\\ 0&0&0&0&0&0&0&1\\\
0&0&0&0&0&1&0&0\end{smallmatrix}\right],$ $\displaystyle A_{15}$
$\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\ 0&1&0&0&0&0&0&0\\\
0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\ 0&0&0&0&0&0&1&1\\\
0&0&0&0&0&1&0&0\\\ 0&0&0&0&0&0&0&1\end{smallmatrix}\right],$ $\displaystyle
A_{16}$ $\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0\\\ 0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\
0&0&0&0&0&0&1&0\\\ 0&0&0&0&0&1&0&1\\\
0&0&0&0&0&0&0&1\end{smallmatrix}\right],$ $\displaystyle A_{17}$
$\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\ 0&1&0&0&0&0&0&0\\\
0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\ 0&0&0&0&0&1&0&1\\\
0&0&0&0&0&0&0&1\\\ 0&0&0&0&0&0&1&0\end{smallmatrix}\right],$ $\displaystyle
A_{18}$ $\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0\\\ 0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\
0&0&0&0&0&0&1&1\\\ 0&0&0&0&0&1&0&1\\\
0&0&0&0&0&0&0&1\end{smallmatrix}\right],$ $\displaystyle A_{19}$
$\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\ 0&1&0&0&0&0&0&0\\\
0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\ 0&0&0&0&0&0&0&1\\\
0&0&0&0&0&1&1&0\\\ 0&0&0&0&0&0&1&0\end{smallmatrix}\right],$ $\displaystyle
A_{20}$ $\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0\\\ 0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\
0&0&0&0&0&1&1&0\\\ 0&0&0&0&0&0&0&1\\\
0&0&0&0&0&0&1&0\end{smallmatrix}\right],$ $\displaystyle A_{21}$
$\displaystyle=\left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\\ 0&1&0&0&0&0&0&0\\\
0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\ 0&0&0&0&0&1&1&1\\\
0&0&0&0&0&0&0&1\\\ 0&0&0&0&0&0&1&0\end{smallmatrix}\right].$