Constituent automorphism decoding of Reed-Muller codes
Yicheng Qu Amir Tasbihi Frank R. Kschischang





Constituent Automorphism Decoding of Reed–Muller Codes
    Yicheng Qu, Amir Tasbihi, and Frank R. KschischangThe
authors are with the Edward S. Rogers Sr. Dept. of Electrical and
Computer Engineering, University of Toronto, 10 King's College Road,
Toronto, Ontario M5S 3G4, Canada.  Email: ,
, .  Submitted for
publication on July 19th, 2024.
    September 9, 2024
===============================================================================================================================================================================================================================================================================================



§ ABSTRACT 
Automorphism-ensemble decoding is applied to the Plotkin constituents of
Reed–Muller codes, resulting in a new soft-decision decoding algorithm
with state-of-the-art performance versus complexity trade-offs.



Reed–Muller codes, automorphism ensemble decoding, successive
cancellation list decoding.




§ INTRODUCTION



This paper introduces the constituent
automorphism (CA) decoder, a new soft-decision decoding algorithm for
Reed–Muller (RM) codes.  The new algorithm, a variant of automorphism
ensemble (AE) decoding <cit.>, exploits the recursive Plotkin
structure of RM codes, applying AE decoding to constituent RM codes
located at various levels in the resulting decoding tree.  By carefully
adjusting the number of automorphisms applied to particular constituent
decoders, CA decoding results in better performance versus complexity
trade-offs than other state-of-the-art decoding algorithms such as
successive cancellation list (SCL) decoding <cit.> and AE
decoding itself <cit.> (where automorphisms are applied only at
the root of the decoding tree).

Although Reed–Muller codes are among the earliest families of codes
introduced in coding theory <cit.>, contemporary interest in
them arises from (a) their excellent soft-decision decoding performance
at short block lengths, (b) their close connection to polar codes, (c)
the relatively recent discovery that RM codes can be capacity-achieving
in certain situations, and (d) the fact that RM codes arise in
connection with various problems in theoretical computer science; see
<cit.> for an excellent review.  In <cit.>, Schnabl and
Bossert view RM codes as generalized multiple concatenated (GMC) codes,
introducing the first soft-decision RM decoding algorithm—herein
referred to as the GMC decoder—by exploiting their recursive Plotkin
structure to successively decode their constituent codes.  In the
literature on polar codes <cit.>, the GMC decoder
is also often referred to as a successive cancellation (SC)
decoder.  In <cit.>, Dumer and Shabunov show that better RM
soft-decision decoding performance can be obtained for the binary-input
additive white Gaussian noise (BI-AWGN) channel by combining GMC
decoding with list-decoding.  The resulting successive-cancellation list
(SCL) decoder was extended to polar codes in <cit.>.

The idea of exploiting code automorphisms for decoding dates
back to the 1960s <cit.>.
Recent interest in
automorphism-based decoders for RM codes <cit.> stems from
their ability to approach
maximum-likelihood (ML) decoding performance with a reasonable
complexity.
The general idea is to permute the
received vector by the elements of a set ℰ of code
automorphisms, then to decode the permuted versions in parallel via a
simple sub-optimal elementary decoder. The inverse automorphism
is then applied to each decoded word to arrive at a list of
|ℰ| (not necessarily distinct) decoding candidates, where
|ℰ| denotes the number of elements in ℰ.  The
decoder then selects the most likely codeword from the candidate list.
While the automorphism-based decoder is approximately |ℰ|
times computationally more complex than its elementary decoder, its
inherent parallelism makes it very hardware-friendly <cit.>,
which may be seen as an advantage of AE decoding compared with SCL
decoding.  The key idea of this paper is to apply AE decoding at the
level of the Plotkin constituent codes of a Reed–Muller code.  This
maintains a high degree of parallelism in the decoding algorithm and, as
we demonstrate, it can result in performance-complexity benefits.

The remainder of this paper is organized as follows.  Various
coding-theoretic preliminaries needed to understand the rest of the
paper are reviewed in Sec. <ref>.  The CA decoder is
introduced in Sec. <ref>, and its complexity is analyzed in
Sec. <ref>.   Simulation results showing performance and
complexity tradeoffs are given in Sec. <ref>, along with
comparisons to other state-of-the-art RM decoders.  Some brief
concluding remarks are given in Sec. <ref>.

Throughout this paper, the real numbers are denoted by ℝ, the
integers are denoted by ℤ, and the two-element finite field
{ 0, 1 } is denoted by 𝔽_2.  The extended real numbers
ℝ∪{ -∞, +∞} are denoted as
.  The (modulo-two) addition operation in
𝔽_2, equivalent to an exclusive-OR (XOR) operation, is
denoted as ⊕. The soft XOR of two extended real numbers
a, b ∈, denoted as a ⊞ b, is given as

    a ⊞ b ≜ 2tanh^-1( tanh(
    a/2) tanh( b/2) ),

where tanh( ±∞) = ± 1, and where the symbol `≜'
signifies that the right-hand side is the definition of the left-hand
side.  The negative log-sigmoid of
x ∈ is given as

    (x) ≜ln(1 + exp(-x)),

where (-∞) = ∞ and (∞) = 0.
For any integer k,

    ℤ^≥ k≜{ k, k+1, …} and ℤ^≤ k≜{…, k-1, k }.

For any n ∈ℤ^≥ 0, [n] ≜{ 0, 1, …,
n-1 }, where [0] is the empty set.  The mapping (-1)^(·):
𝔽_2 →ℝ is defined, for b ∈𝔽_2, as

    (-1)^b ≜ 1,    if b=0; 
    
                          -1,    if b=1.

For any predicate p, 1_p denotes the indicator function 

    1_p ≜
    1,    if  p  is true;
    
    0,    otherwise.

The codomain of 1_p may be  or
𝔽_2 as context dictates.  Vectors (over
 or 𝔽_2) are denoted with boldface
lower-case letters.  A vector of length n, i.e., a vector
having n components, is referred to as an n-vector.  The ith
component of an n-vector 𝐯 is denoted 𝐯[i],
where i ∈ [n].  The empty vector ∅≜ () has
zero length and no components.  The concatenation of an
n_1-vector 𝐮 and an n_2-vector 𝐯, in that
order, is the (n_1+n_2)-vector

    ( 𝐮|𝐯 ) ≜
    ( 𝐮[0], …, 𝐮[n_1-1],
      𝐯[0], …, 𝐯[n_2-1] ).

Generally (𝐮|𝐯 ) ≠ (𝐯|𝐮), although ( 𝐮|∅) = (∅|𝐮) = 𝐮.  The all-zero and all-one n-vectors
over 𝔽_2 are denoted as 0_n and 1_n,
respectively, where the subscript may be omitted if the length is clear
from the context.  For any binary vector 𝐛 and any real vector
λ of the same length, (-1)^𝐛λ
denotes a real vector whose ith component is (-1)^𝐛[i]λ[i].  For any n ∈ℤ^≥ 0, ((a_i,
b_i)_i ∈ [n]) denotes the n-tuple of 2-tuples ((a_0,
b_0), (a_1, b_1), …, (a_n-1, b_n-1)), where the a_i's and
b_i's are arbitrary mathematical objects. This notation may be generalized to
n-tuples of m-tuples in the obvious way.  For any m ∈ℤ^≥ 0, the ring of m-variate binary polynomials with
indeterminates x_0, …, x_m-1 is denoted by 𝔽_2[x_0,
…, x_m-1].  When m=0 we have 𝔽_2[ ]
≜𝔽_2.  For any r ∈ℤ,
𝔽_2^≤ r [x_0, …, x_m-1] denotes the set of
polynomials in 𝔽_2[x_0, …, x_m-1] whose total degree
is at most r.  The total degree of the zero polynomial 0 is taken as
-∞; thus for any r < 0, 𝔽_2^≤
r[x_0,…,x_m-1] = { 0 }.




§ PRELIMINARIES


In this section we briefly review various coding-theoretic
concepts needed to understand the remainder of the paper.



 §.§ Channels and Decoders


Throughout this paper, we assume the use of a binary-input memoryless
channel with input alphabet 𝔽_2, output alphabet
𝒴, and channel law given, for x ∈𝔽_2 and y
∈𝒴, as W(y | x), where W is either a conditional
probability mass function or conditional probability density function
according to whether 𝒴 is discrete or continuous.  Without
loss of generality, we assume that 𝒴 is chosen so that W(y
| 0) ≠  0 or W(y | 1) ≠ 0 for all y ∈𝒴.

A standard example of such a channel is the binary symmetric channel
with crossover probability p, where 𝒴 = 𝔽_2
and W(1| 0)=W(0| 1)=p.  Another example is the binary erasure
channel (BEC) with erasure probability ϵ, where 𝒴 =
𝔽_2 ∪{ e } and W(e | 0) = W(e | 1) = ϵ
and W(0 | 1)=W(1 | 0) = 0.  Another standard example, and the
one we use to present simulation results, is the BI-AWGN with noise
variance σ^2, where 𝒴 = ℝ, with W(y | 0)
= 𝒩(1,σ^2) and W(y | 1) = 𝒩(-1,σ^2),
where 𝒩(m,σ^2) denotes a Gaussian density function with
parameters m and σ^2.  The signal-to-noise ratio (SNR)
of such a channel is 1/σ^2.

Associated with each received channel output y ∈𝒴 is the log-likelihood
ratio (LLR) Λ(y) ≜ln(  W(y | 0) / W(y
| 1)) ∈, where Λ(y) =
-∞ if W(y | 0) = 0 and Λ(y) = +∞ if W(y | 1)
= 0.  Infinite LLRs occur, for example, for unerased symbols received
at the output of the BEC.  The hard decision associated with an
LLR value λ = Λ(y), for some channel output y, is given
by the function : →𝔽_2, where
(λ) ≜1_λ < 0.

Suppose that a binary codeword of length n is transmitted.  Based on
the corresponding channel output 𝐲∈𝒴^n, we
assume that the receiver produces the log-likelihood-ratio (LLR) vector
λ∈^n, where λ[i]  =
Λ(𝐲[i]) for i ∈ [n].  The LLR vector serves as the
interface between the channel and the decoder.  We also define the
vector of hard-decisions (λ) ∈𝔽_2^n as a
binary n-vector whose entries are hard decisions associated with
λ entries, i.e., (λ)[i] ≜(λ[i]) for i ∈ [n].

A decoding rule or simply decoder for a binary code C of
length n is a function D: ^n → C ∪{ F }
that maps an LLR vector λ either to a codeword of C or to
the symbol F (which indicates a decoding failure).  Two decoders D_1
and D_2 are the same for a given channel if they almost surely
produce the same decoding decision, i.e., if
(D_1(λ) ≠ D_2(λ)) = 0, where
λ is the LLR vector corresponding to the channel output.
We write D_1 ≠ D_2 when D_1 and D_2 are not the same.

The analog weight w(𝐱, λ) of a channel
input 𝐱 with respect to an LLR vector λ is given
as the sum of the absolute values of those components of λ
whose hard-decisions disagree with the corresponding component of
𝐱, i.e.,

    w(𝐱,λ) ≜∑_i:𝐱[i] ≠(λ[i])
    |λ[i]|.

The analog weight w(𝐱,λ) measures the cost of
disagreements between 𝐱 and (λ).  Among all
possible channel inputs, the hard-decision vector (λ) itself
has minimum possible analog weight, namely 0;  however, (λ)
may not be a codeword.  Given an LLR vector λ,
a maximum-likelihood (ML) decoder
for a code C produces a codeword 𝐯∈ C having least
analog weight with respect to λ.
If codewords are equally likely to be transmitted, an ML
decoder minimizes block error rate (BLER), i.e., the probability
that the decoding decision disagrees with the transmitted codeword.



 §.§ Code Automorphisms


For any positive integer n, a permutation of order n is a
bijection π : [n] → [n].  The set of all permutations of order n
forms a group (the symmetric group S_n) under function
composition.  The group identity is denoted as 𝕀.  The symmetric
group S_n acts on n-vectors by permutation of coordinates,
i.e., for any n-vector 𝐯 and any π∈ S_n,

    π𝐯≜ ( 𝐯[π(0)], … ,
    𝐯[π(n-1)] ).


A permutation π∈ S_n is called an automorphism of a code
C of length n if 𝐜∈ C implies π𝐜∈ C.
In other words, an automorphism of a code is a permutation which maps
codewords to codewords.  The set of all automorphisms of C form a
subgroup of S_n called the automorphism group of C.



 §.§ Reed–Muller Codes


Fix m ∈ℤ^≥ 0.  For any
polynomial p = p(x_0,…,x_m-1) ∈𝔽_2[x_0, …,
x_m-1], and any binary m-vector 𝐯, called a
point, let p(𝐯) = p(𝐯[0], …,
𝐯[m-1]) ∈𝔽_2 denote the evaluation of the
polynomial p at the point 𝐯, i.e., the binary value
obtained when x_i is substituted with 𝐯[i], for each i ∈
[m].  When m=0, we have p(∅) = 0 if p = 0 and
p(∅)=1 if p=1.  Define the evaluation map :
𝔽_2 [x_0, …, x_m-1] →𝔽_2^2^m as the
function which maps the polynomial p ∈𝔽 [x_0, …,
x_m-1] to its evaluation at all points of 𝔽_2^m in
lexicographic order, i.e., 

    (p) ≜(
    p(0,…,0,0), p(0,…,0,1), p(0,…,1,0),
    …, p(1,…,1,1)).

For any r ∈ℤ and any m ∈ℤ^≥ 0, the
binary Reed–Muller code of log-length m and order r,
denoted as (r,m), is the image of 𝔽_2^≤
r[x_0,…,x_m-1] under the evaluation map, i.e.,

    (r,m) ≜{(p): p ∈𝔽_2^≤ r[x_0, …, x_m-1]
    }.

It can be shown (see, e.g., <cit.>), for any
m ∈ℤ^≥ 0 and any integer r satisfying 0 ≤ r
≤ m, that (r,m) is a code of block length n = 2^m, dimension

    k(r,m) ≜∑_i=0^r mi

and minimum Hamming distance d = 2^m-r.  When r < 0, (r,m) =
{0_2^m} contains only the zero codeword.  When r=0, (r,m) is the
binary repetition code of length 2^m.  When
r=m-1, (m-1,m) is the (2^m,2^m-1) single-parity check (SPC) code.
When r ≥ m, (r,m) =
𝔽_2^2^m (the whole space of 2^m-vectors).  These are the
trivial RM codes.  When 0 < r < m-1, we call (r,m)
nontrivial.

RM codes are one of the few algebraic code families with a
well-characterized automorphism group.  We denote the automorphism
group of (r,m) by r,m.  When (r,m) is nontrivial, it
is known <cit.><cit.> that
r,m is isomorphic to the general affine group GA(m,
𝔽_2).  When (r,m) is trivial, r,m is equal to
S_2^m (i.e., every permutation of coordinates is an
automorphism).

Under the lexicographic order by which the evaluation map in
(<ref>) is defined, one may show that RM codes admit a
Plotkin structure <cit.>.  This means that any codeword
𝐜∈(r,m), where m ≥ 1, can be written as 

    𝐜 = (𝐮|𝐮⊕𝐯),

where 𝐮∈(r,m-1) and 𝐯∈(r-1,m-1).  We
refer to (r,m-1) and (r-1,m-1) as the Plotkin
constituents of (r,m).  Of course (r,m-1) and (r-1,m-1)
are themselves RM codes, having their own Plotkin constituents.

The relationships among the various Plotkin constituents of (r,m)
are readily visualized using a binary tree, called a Plotkin
tree, and denoted rm.  Each vertex in the tree is labelled
with a pair of integers (r',m'); in particular, the root is labelled
with (r,m).  A vertex v with label (r',m') where m'>0 has two
children: the left child has label (r',m'-1)
and the right child has label (r'-1,m'-1).
Vertices (r',m') with m'=0 are leaf vertices; they have no children.
Fig. <ref> illustrates 24.



Since it is possible for some vertices in rm to have the same
label, it is useful to assign a unique variable-length binary
address to each vertex.  The construction is standard: the root
is assigned address ∅, and throughout the tree (or any
rooted subtree thereof), the left child of a vertex with the address
𝐚 receives address (𝐚| 0), while the right
child receives address (𝐚| 1).  However, rather than
writing addresses as vectors, we will write them as binary strings.  For
example, Fig. <ref> illustrates the vertex addresses for
a rooted subtree of 36.  If the root of the tree has label
(r,m), then a vertex with address 𝐚 has label
(r-wt(𝐚),m-len(𝐚)), where
wt(𝐚) denotes the Hamming weight of 𝐚 and
len(𝐚) denotes the length of 𝐚.

In principle, soft-decision ML decoding of (r,m) can be
accomplished via the Viterbi algorithm; however the number of edges in
the trellis diagram scales at least exponentially in the block length
<cit.>, making this approach
computationally infeasible for all but very short RM codes.  On the
other hand, ML decoding of the trivial RM codes (which include
repetition codes and SPC codes) is easy.  ML decoding of (m-1,m), the 
SPC code, is straightforward via the Wagner
decoding rule <cit.>, with the main complexity being
determination of the position in the received word having the smallest LLR
magnitude.   Soft-decision decoding of first-order RM codes (1,m)
can be accomplished using the “Green Machine”
decoder <cit.><cit.>, with the main
complexity being the computation of a Hadamard transform of the received
LLR vector.  In the following sections, we discuss some of the non-ML
soft-decision decoding algorithms for general RM codes.



 §.§ GMC Decoding of RM Codes


As already noted, the GMC decoder <cit.> uses a divide-and-conquer
approach that exploits the recursive Plotkin structure of RM codes,
splitting the task of decoding (r,m) into that of decoding its
Plotkin constituents, namely (r-1,m-1) and (r,m-1).  In turn,
these smaller decoding problems can themselves be split into even
smaller decoding problems, until eventually an “easy” decoding problem
is reached, at which point no further task-splitting is required.

To make this precise, let 𝒜, called an atom set, be
any collection of RM codes for which task-splitting is not required due
to the availability of computationally feasible decoders for those
codes.  For example, 𝒜 might contain all trivial RM codes
and the first-order RM codes
(1,m).  We will assume that an atom set always contains trivial
RM codes (r,0) of length 1.  An RM code not contained in
𝒜 is called composite with respect to 𝒜.
The decoding function for an RM code (r,m) ∈𝒜 is
denoted as A_r,m.

Let λ∈^2^m, denote the LLR
vector produced at the output of a binary-input memoryless channel when
a codeword of (r,m) is transmitted.  The GMC decoder with atom set
𝒜 is the function rm^𝒜 :
^2^m→(r,m) recursively defined by

    rm^𝒜(λ) ≜
    A_r,m(λ),    if (r,m) ∈𝒜;
    
    (𝐮|𝐮⊕𝐯),    otherwise,

where, assuming λ is partitioned as
λ=(λ'|λ”) with λ',
λ”∈^2^m-1, the binary
2^m-1-vectors 𝐯 and 𝐮 are given as

    𝐯   = r-1m-1^𝒜 (λ'⊞λ”),
    
    𝐮   = rm-1^𝒜 (λ' + (-1)^𝐯λ”),

respectively.  Since 𝒜 is required to include trivial
length-1 RM codes, the GMC decoder is guaranteed to terminate.

Note that computation of 𝐮 in (<ref>) depends on
the availability of 𝐯 defined in (<ref>), and
both 𝐮 and 𝐯 are required in (<ref>).  In effect, the GMC decoder rm^𝒜
performs a reverse post-order traversal of a rooted subtree of
rm—called the GMC decoding tree with respect to
𝒜 and denoted as rm^𝒜—in which
vertices with labels corresponding to codes that are composite with
respect to 𝒜 are internal, and those with labels
corresponding to elements of 𝒜 are leaves.  We refer to the
decoders for elements of 𝒜 as leaf decoders.

The smallest possible atom set contains only the RM codes of length 1,
in which case the GMC decoding tree for (r,m) is the same as the
Plotkin tree rm.  However, as noted earlier, another choice
for the atom set is the one containing the trivial and the first-order
RM codes, i.e.,

    𝒜^∗ = {(r, m): m ∈ℤ^≥ 0, r ∈ℤ^≤ 1∪ℤ^≥ m-1}.

The circled vertices in Fig. <ref> illustrate
24^𝒜^∗, the GMC decoding tree for (2,4)
with atom set 𝒜^∗, and Fig. <ref> shows
the GMC decoding tree 36^𝒜^∗ (along with the
address of each vertex).




It is important to note that GMC decoding, though computationally
convenient, does not always return an ML codeword, and therefore GMC
decoding does not generally have the smallest possible BLER.  The complexity
of GMC decoding of an RM code of length n is 𝒪(n log
n) <cit.>. Because of its low complexity (and its
suboptimality), the GMC decoder can be used as an elementary decoder in
AE decoding; see Sec. <ref>.



 §.§ SCL Decoding of RM Codes


SCL decoders generalize GMC decoders by allowing the constituent
decoders to return not just a single codeword, but rather a list
of possible codewords.
In SCL decoding, the atom set is usually chosen as
𝒜' ≜{(r,0): r ∈ℤ},
which contain only RM codes of length 1.
To avoid an exponential growth of the decoding
list, an upper bound on the returned list size at each constituent
decoder is maintained, retaining only those candidate codewords of
lowest cost, defined as follows <cit.>.
For any LLR vector λ∈^2^m and any
𝐜∈(r,m), let

    (𝐜,
    λ) ≜∑_i ∈ [2^m]((-1)^𝐜[i]λ[i])

be the cost of decoding the LLR vector λ
to the vector 𝐜, where  was defined
in (<ref>).
If λ =
(λ'|λ”), for some λ' and
λ”∈^2^m-1, and if 𝐜 =
(𝐮|𝐮⊕𝐯), then

    (𝐜, λ) =
    (𝐯, λ'⊞λ”)+
    (𝐮, λ' + (-1)^𝐯λ”).

The terms
(𝐯, λ'⊞λ”) and 
(𝐮, λ' + (-1)^𝐯λ”) may
be regarded as the
Plotkin constituent costs of
𝐜 = (𝐮|𝐮⊕𝐯);
the SCL decoder exploits this additive decomposition of the overall
cost of 𝐜.

SCL decoding proceeds recursively in the same manner as the GMC
decoder, except, rather than being provided with a single LLR vector,
the constituent decoders are provided with a list of one or more ordered pairs,
where each pair comprises an LLR vector and an associated cost.
The output of each constituent decoder is a list of triples,
where each triple comprises
a codeword, the index within the input list
of the LLR vector from which that codeword
was decoded, and the overall cost of that codeword.

More precisely, a constituent SCL decoder for
(r,m) with
maximum output-list-size ∈ℤ^≥ 2
and input-list-size ≤
is a function

    _r,m^, : (^2^m×)^→ ((r,m)  ×
    [] ×)^,
 
where = min(2^k(r,m), ).
We will start by defining this function for the
special case when m=0, i.e., for a leaf decoder.

When m=0, the SCL decoder is a map

    _r,0^, : (×)^→ ((r,0) × [] ×)^,

where = min(2^k(r,0), ).
Thus the input to a leaf decoder is
a list of pairs
((λ_0,ψ_0), …, (λ_ -1,ψ_-1)) ∈
(×)^, where λ_i is an
LLR value and ψ_i is the associated cost.
Two cases must be considered:


  * If r ≥ 0, then (r,0) = {0_1, 1_1 }.
In this case,
for each λ_i, i ∈ [], there are two
possible codewords: 0 with overall cost
ψ_i + (0, λ_i) = ψ_i + (λ_i)
leading to the tentative output triple (0,i,ψ_i + (λ_i)),
and 1 with overall cost ψ_i + (1, λ_i) = ψ_i + (-λ_i)
leading to the tentative output triple (1,i,ψ_i + (-λ_i)).
In total there will be 2 tentative output triples.  If needed,
this list of tentative triples
is truncated to length , with the decoder
returning only those
candidates with the least overall cost.

  * If r < 0, then (r,0) = {0_1 }. In this case 0 is the only
possible candidate codeword for each
λ_i, i∈ [],
leading to output triple (0,i,ψ_i + (λ_i)).
All  of the resulting triples are returned by the decoder.


When m>0, suppose the input to the SCL decoder
is the -tuple 

    τ = (((λ'_i |λ”_i), s_i)_i ∈
    []),
 
with λ'_i and
λ”_i∈^2^m-1  
and s_i ∈. We will then have

    _r,m^, (τ) ≜(((𝐮_i
    |𝐮_i ⊕𝐯_q_i), p_q_i, s'_i)_i ∈ [])

where
𝐯_j's and the
p_j's in (<ref>) are obtained from 

    ((𝐯_j, p_j, s_j”)_j∈ [ℓ']) = 
    _r-1, m-1^, (
    (λ'_i ⊞λ”_i,s_i)_i ∈ []),

where 

    ℓ' = min(2^k(r-1, m-1), ).
  
Moreover, the
𝐮_j's, the q_j's, and the s'_j's in (<ref>) are
obtained from

    ((𝐮_j, q_j, s'_j)_j∈ [ℓ”])
    = 
    _r, m-1^ℓ', (
    (λ'_p_j + (-1)^𝐯_jλ”_p_j, s_j”)_j ∈ [ℓ']),

where 

    ℓ” = min(2^k(r, m-1)ℓ', ) = min(2^k(r,m), ).


The overall SCL decoder for (r,m) is obtained by setting =
1 and by choosing any arbitrary real number as the initial cost of
its input LLR vector.  The overall decoder returns the codeword
having the smallest analog weight with respect to the input LLR vector
from the list of candidates returned by
the decoder at the root of the decoding tree.



 §.§ AE Decoding of RM Codes


As described in Sec. <ref> and as illustrated in
Fig. <ref>, an AE decoder operates by permuting the received
LLR vector λ by the elements of a set ℰ = {π_1, …, π_ℓ}, called an automorphism ensemble, of
code automorphisms.   Each of the ℓ permuted LLR vectors is then
decoded (perhaps in parallel) using a simple sub-optimal elementary
decoder such as a GMC decoder, and the corresponding inverse permutation
is applied to each decoding result.  The most likely codeword is then
selected from the ℓ generated candidates.

For any choice of atom set 𝒜 and
any automorphism π∈r, m, let
rmπ, 𝒜 : ^2^m→(r,m) denote the
π-permuted GMC decoder, defined as

    rmπ, 𝒜≜π^-1∘rm^𝒜∘ π,
 
where ∘ denotes function composition.
Thus rmπ,𝒜(λ) =
π^-1rm^𝒜(πλ).
Of course rm𝕀, 𝒜 = rm^𝒜,
i.e., the 𝕀-permuted GMC decoder is just the GMC decoder itself.


Depending on the choice of π, because
of the suboptimality of a GMC decoder, it may happen
that

    rm^𝒜≠rmπ, 𝒜.

This is useful, because if
rm^𝒜 makes an error, there is a possibility
that
rmπ, 𝒜 can nevertheless decode correctly, and
vice versa.
Automorphism ensemble decoding of RM codes <cit.> exploits (<ref>) to decode a received
LLR vector using an ensemble ℰ of automorphisms with the property,
that

    π_1, π_2 ∈ℰ, π_1 ≠π_2  implies rmπ_1, 𝒜≠rmπ_2, 𝒜.

Indeed, if rmπ_i, 𝒜, π_i ∈ℰ, produces 
decoding decision 𝐜_i, then
the overall AE decoding decision is given, as illustrated
in Fig. <ref>, by

    𝐜 =
    min_𝐜_1,…,𝐜_ℓ w(𝐜_i,λ),

where the analog-weight function w was
defined in (<ref>).


 



§ CONSTITUENT AUTOMORPHISM DECODING
 

Like all successive-cancellation decoding schemes, GMC decoders are prone
to error propagation: once a leaf decoder makes an error, the error
propagates to all succeeding decoders encountered in the decoding
tree traversal.  Because of channel
polarization <cit.>, different constituent
leaf decoders of an RM code observe different synthetic channels
and, as a result, they
have different first-error probability, the probability that they
produce an error while all preceding leaf decoders have decoded
correctly.
For example, Table <ref> gives the binary
addresses of the leaf
constituent codes of 49^𝒜^∗ having the largest
first-error probability at the output
of a BI-AWGN channel with an SNR of 4 dB.  It is clear that most decoding
errors are triggered by the leaf decoder with address 111.

Because of this channel polarization effect,
it is sensible to devote
more decoding resources to those constituent codes having relatively
degraded channels, as these trigger the most decoding errors.
However, a conventional AE decoder treats all constituent
codes evenly.  In particular, via an AE decoder with some automorphism ensemble
ℰ, each constituent code of a composite RM code is decoded
|ℰ| times. To remedy this issue, we introduce
constituent automorphism
decoding.
The key idea is
to apply AE decoding locally to the codes that are composite
with respect to a given atom set 𝒜.



With a random selection of ℰ from r, m chosen to satisfy
(<ref>), we did not see any difference in BLER at the output of a
BI-AWGN between various selected automorphism ensembles for any of the
(r,m) codes that we tested.  Thus we speculate that the performance of an
AE decoder depends only on the ensemble size.  As a result, we will only
specify the AE size, without describing the actual automorphisms used.

By default, all decoders in the decoding tree will use an AE size of one
(conveniently implemented with an automorphism ensemble containing just the
identity permutation 𝕀).  However, certain selected composite (non-leaf)
decoders will use AE decoding locally with a larger AE size.

To specify the local decoders having an AE size greater than unity, we define
an automorphism distribution 𝒮 as a set of (𝐚,s)
pairs, where 𝐚 is the binary address of a decoder in
rm^𝒜 and s is the corresponding AE size.  For example,
𝒮 = { (1,2), (11,3) } denotes a CA decoder that applies AE
decoding with AE size 2 at the decoding tree vertex with address 1, and AE
decoding with AE size 3 at the vertex with address 11.  In this notation, a
conventional AE decoder with AE size s has automorphism distribution
𝒮 = { (∅,s) }. We denote the CA decoder for (r,m)
with automorphism distribution 𝒮 and atom set 𝒜 as

    _r, m^𝒮, 𝒜: ^2^m→(r, m).


In the rest of this paper, all CA decoders use the atom set 𝒜^∗.
The leaf decoders associated with 𝒜^∗ are permutation invariant ML
decoders, so applying AE to them cannot improve performance. Hence the AE size
of leaf nodes in rm^𝒜^∗ is fixed to unity. As we will
show in Sec. <ref>, most of the benefit of CA decoding arises when
the addresses 𝐚 are chosen from the set {∅, 1, 11, 111,
…} which are called rightmost nodes, as these correspond to the
synthetic channels that polarize to relatively “bad” channels.  A slightly
better heuristic for choosing the vertices at which to apply AE decoding is
given in Sec. <ref>.






§ COMPLEXITY ANALYSIS





 §.§ Basic Operations


It is difficult to give a precise analysis of decoding complexity, as it
strongly depends on the available hardware and its architecture.  Nevertheless,
complexity (measured by the area-time product of an integrated circuit
implementation, or in execution time of a software implementation) will scale
approximately linearly with the number of unary and binary operations executed
by the decoding algorithm.  Accordingly, we will measure
complexity by counting such operations (in the worst case) for each of the
decoders that we consider.

In practice, LLR values are often represented using
a fixed point (integer) representation with a fixed word size.
We will assume that
vectors of length n, whether integer- or 𝔽_2-valued,
are stored as sequences of n words.
All decoders that we consider are implemented as sequences of the following
basic unary and binary operations (operating on
one or two words): addition (+), comparison (<, >, ≤, ≥), 
minimum and maximum (min, max),
soft XOR (⊞), negative log-sigmoid (), absolute value (|·|), 
negation (-), binary addition (⊕), and, finally, copying a word or its negation.

We assume the soft XOR and the negative log-sigmoid operations are calculated by
look-up tables or hardware-friendly approximations.
In a pipelined processor architecture, the fetching of operands
and the storing of results take place in parallel with
instruction decoding and execution, so we do not
assign additional complexity for such operations.
Assuming the use of pipelining,
all of these basic operations can be executed in a single clock cycle on 
average.  Accordingly, we weight these operations evenly, taking
their total count  as a measure of decoder complexity.


Let D_r,m denote a decoder for (r,m) and let _D(r,m) denote
its complexity.  Except at leaf decoders, D_r,m is defined recursively in
terms of D_r-1,m-1 and D_r,m-1, the decoders for its Plotkin
constituents.   Depending on the nature of the decoder, these constituent
decoders may be invoked more than once.  It follows that _D(r,m) will
generally decompose (recursively) into three terms: 1) a term
that accounts for one or more applications of D_r-1,m-1, 2) a
term that accounts for one or more applications of D_r,m-1, and
3) a term that accounts for the preparation of LLRs and the final
decision.  Leaf decoders are not defined recursively, and thus each such
decoder will require its own separate complexity analysis.



 §.§ Complexity of CA, GMC, and AE decoders


For all nontrivial RM codes,
assuming use of the atom set 𝒜^∗ defined in (<ref>),
the only required leaf decoders are those for the
(m-1,m) SPC codes and (1,m) first-order
RM codes.



  §.§.§ (m-1,m)

The worst-case complexity of applying the Wagner decoding rule
to the (m-1,m) SPC code can be separated into:


  * converting LLRs to hard-decisions, which
requires 2^m comparisons;

  * determining the overall parity, which
requires 2^m-1 binary field additions;

  * checking whether the overall parity is nonzero,
which requires 1 comparison,

  * flipping the bit
with the least absolute LLR
value (if the parity bit is nonzero), which
requires 2^m absolute value computations,
2^m-1 comparisons, and 1 binary field addition.

Adding these values gives

    (m-1,m) = 2^m+2.





  §.§.§ (1,m)

The worst-case complexity of decoding (1,m), the
length-2^m first-order RM code,
using the Green Machine decoder can be separated into:


  * applying the fast Hadamard transform to
the given LLR vector, which requires m · 2^m additions;

  * finding the index with the largest absolute value, which
requires 2^m absolute value computations, and 2^m-1 comparisons;

  * extracting the sign of the corresponding LLR,
which requires 1 comparison,

  * converting the sign and index to a codeword,
 which requires
2^m + m operations according to Algorithm <ref>.

Adding these values gives

    (1,m) = (m+3)2^m +m  .






Let _(r, m, 𝒮) denote the complexity of _r,
m^𝒮, 𝒜^∗, the CA decoder for a composite (r,m)
under an automorphism distribution 𝒮 and with atom set
𝒜^∗. Let ℓ denote the number of automorphisms applied at
the root of the decoding tree. Note that (∅, ℓ) ∈𝒮
if and only if ℓ > 1.  A CA decoder for (r,m) using 𝒮
invokes CA decoders for the Plotkin constituents of the code,
i.e., (r-1, m-1) and (r, m-1), using, respectively, the
automorphism distributions 𝒮_1 and 𝒮_0, defined as

    𝒮_1    ≜{(𝐚, s_𝐚): ((1 |𝐚), s_𝐚) ∈𝒮} and
    𝒮_0    ≜{(𝐚, s_𝐚): ((0 |𝐚), s_𝐚) ∈𝒮}.


The number of operations contributing to _(r, m, 𝒮) decomposes as follows:


  * preparing LLRs for _r-1,m-1^𝒮_1, 𝒜^∗ in accordance with (<ref>), which
requires ℓ 2^m-1 soft XOR operations;

  * invoking ℓ instances of _r-1, m-1^𝒮_1, 𝒜^∗, which requires 
ℓ_(r-1, m-1, 𝒮_1) operations;

  * preparing LLRs for _r, m-1^𝒮_0, 𝒜^∗ in accordance with (<ref>), which
requires ℓ 2^m-1 comparisons and ℓ 2^m-1 additions;

  * invoking ℓ instances of
_r, m-1^𝒮_0, 𝒜^∗, which requires 
ℓ_(r, m-1, 𝒮_0) operations;

  * combining Plotkin constituents according
to (<ref>), which requires
ℓ 2^m-1 binary field additions; 

  * choosing the codeword with minimum analog weight among ℓ candidates, which if ℓ = 1 
requires no operations and  
if ℓ > 1 requires ℓ 2^m comparisons
and ℓ (2^m - 1) additions for computing analog weight, and 
another ℓ - 1 comparisons for choosing the final codeword.

As a result, 

    _(r, m, 𝒮) =     ℓ_(r-1, m-1, 𝒮_1) + ℓ_(r, m-1, 𝒮_0) + 
       ℓ 2^m+1 + 1_ℓ > 1· (ℓ 2^m+1 - 1),

with boundary conditions _(m-1, m, {}) = (m-1, m) and
_(1,m, {}) = (1,m), defined in (<ref>)
and (<ref>), respectively.

GMC and AE decoders are special cases of a CA decoder and so
their complexity may be expressed in terms of 
_.
Since all nodes in the decoding tree of a GMC decoder use only
the identity automorphism,
the automorphism distribution for such a decoder
is 𝒮 = {}; thus

    GMC(r,m) = _(r, m, {}).

An AE decoder with an automorphism ensemble of size ℓ has automorphism 
distribution 𝒮={(∅, ℓ)}; thus,

    AE(r, m, ℓ) = _(r, m, {(∅, ℓ)}).




 §.§ Complexity of SCL Decoders


We assume that (r,m) has a non-negative order and that the atom set
𝒜' is used.  Similar to CA decoders,
we first discuss the complexity of list decoding of codes in
𝒜'. We then derive the complexity of the SCL
decoder for a composite code (r,m).




  §.§.§ (r,m) ∈𝒜'


For list-truncation purposes, some of the leaf SCL decoders must find the least
 numbers among an unsorted list of n numbers, where n ∈ℤ.
When < n, there are a number of algorithms for this task,
each having its own complexity.
We denote by
sel(,n) the number of basic
operations required for this task
in the worst case.  Clearly sel(,n) = 0
when ≥ n.


In this paper, we use (,n)
selection
networks, which combine a fixed number of comparator and
minimum selector (minselector) elements to achieve a deterministic number of basic
operations for
selection of the smallest  entries from
an input list of size n > <cit.>,
<cit.>. 
A comparator is a two-input two-output computational unit, that
transforms
a pair (x,y) of input scores to (min(x,y),max(x,y)), requiring
two basic operations.
Similarly, a minselector is a two-input one-output unit,
transforming a pair (x,y) to min(x,y), requiring one basic operation.
Since n-
inputs are dropped by an (,n) selection network, the number of
minselectors in such a network will always be n-.
Thus, an (,n) selection network with a total
of T
computational units (comparators
and minselectors) requires 
sel(,n) = 2T - (n-) basic operations.

An (,n) selection network is said to be optimal
if the total number T
of computational units
that it contains is as small as possible;
this
minimum possible number of computational units is denoted as
U_(n).
The exact value of U_(n) is
known only for
small values of  and n; however, it is known
that <cit.>

    U_(n) ≥ (n-) ⌈log_2 (+1) ⌉.

Fig. <ref> shows conjectured-optimal (4,8)
and optimal (6,8) selection networks.



Table <ref> shows the value for sel(,n)
for different
values of  and n encountered in SCL decoding of RM codes
in Sec. <ref>.  The values for
sel(4,8) and sel(6,8) correspond to
the selection networks of
Fig. <ref>.
In the (6,12) case, 
we have assumed that the lower bound in (<ref>)
is achieved with equality;  however, in practice this bound may not
be achievable, and thus sel(6,12) may be larger
than the value given in the table.




Let _(r, m, , ) denote the decoding complexity of
_r,m^,.  We start by considering
_(r, 0, , ), i.e., the decoding complexity
of the leaf decoders _r,0^,. 

For an input-list size ∈ℤ^≥ 1 and a maximum output-list
size ∈ℤ^≥ 2, the complexity of applying
_r, 0^, to decode LLR values λ_0, …,
λ_ - 1 to a codeword (of length one)
in (r,0) can be separated into
the following steps.


  * Computing the overall cost of each tentative candidate codeword
along with the value of that codeword.
For  the zero codeword this requires 
one call to , one addition, and  one bit-copy operation,
for a total cost of 3 basic operations.
When r ≥ 0,
the nonzero codeword requires these operations and
an extra negation for an additional cost of 4 basic operations.
In total,
this results in (3+4 ·1_r ≥ 0) operations.

  * Finding the (at most) 
codewords having least cost from
a list of 2^k(r,0) codewords, which
requires sel(,2^k(r,0)) basic operations.

Adding the number of basic operations for these steps gives

    _(r, 0, , ) =
     (3+4 ·1_r ≥ 0) + sel(,2^k(r,0)).




  §.§.§ (r,m) ∉𝒜'

For an input-list size  and a maximum
output-list size , the complexity of applying _r,m^,
to decode (r,m) ∉𝒜' decomposes as follows:


  * preparing LLRs for _r-1, m-1^, in accordance with (<ref>), which
requires 2^m-1 soft XOR operations; 

  * invoking _r-1, m-1^,, which
requires _(r-1, m-1, , ) operations;

  * preparing LLRs in accordance with (<ref>), which
requires ℓ' 2^m-1 comparisons 
and ℓ' 2^m-1 additions where ℓ' is given in (<ref>);

  * invoking _r, m-1^ℓ',, which  requires _(r, m-1, ℓ', ) operations;

  * combining Plotkin constituents, which
requires ℓ” 2^m-1 binary field additions where ℓ”   
is as (<ref>).

As a result,

    _(r, m, , ) = _(r-1, m-1, , ) + 
    _(r, m-1, ℓ', ) + 2^m-1( + 2ℓ' + ℓ”),

with boundary conditions defined by leaf decoders according to (<ref>).
The complexity of the overall SCL decoder with a maximum output-list size of
 is then _(r, m, 1, ).



§ NUMERICAL RESULTS
 

In this section, using numerical simulations we provide
performance versus
complexity and BLER versus SNR trade-offs for the
schemes described in this paper.
We assume transmission over a BI-AWGN channel.  Performance is measured by
the gap to the constrained Shannon limit at a BLER of 10^-3.  Complexity
is measured as the worst-case number of operations,
computed according to Sec. <ref>, normalized by
the code dimension.



 §.§ Selection of automorphism distribution



There are numerous possible ways to choose an
automorphism distribution.  It is an open problem
to determine the automorphism distribution that leads
to the best performance at a given decoding complexity.
Guided by the following numerical
results, we provide a heuristic method for finding 
“good” CA decoders.



We first compare the performance-complexity tradeoffs of CA decoders
for (4,9) for a large number of different choices of
automorphism distribution.  
According to
Table <ref>, most decoding errors are caused by
rightmost leaf decoders.
We have tested addresses in automorphism distributions
involving the first 5 nodes in the reverse pre-order decoding
tree traversal (namely, nodes with address
∅, 1, 11, 110, and 1100),  with AE size for each address
ranging from 1 to 4.
The results are given in Fig. <ref>.

The lower hull
in Fig. <ref> is the Pareto frontier; it connects
the Pareto-efficient points. A point is Pareto-efficient
with respect to a given set of points
if no other point in the set
can achieve better performance with the same or lower complexity.
The parameters of the Pareto-efficient points in this test are
given in Table <ref>. 


We categorize the tested automorphism distributions  in
Fig. <ref> into four classes: (a) no rightmost nodes, (b) only
root node, (c) only rightmost nodes (excluding only root node), (d) others.
It is clear that CA decoders in class (a) have almost the same decoding
performance as the GMC decoder, which implies that including the rightmost nodes
is a necessary condition to make an improvement. The Pareto frontier has roughly
0.2 dB gain from decoders in (b), which shows the advantage of CA decoding
compared to AE decoding. CA decoders with automorphism distributions satisfying
(c) are called rightmost CA decoders. According to
Fig. <ref> and Table <ref>, the
Pareto-efficient points involve automorphism distributions where only
rightmost or “nearly rightmost” vertices in the decoding
tree receives an AE size greater than one.

These observations suggest the following heuristic method
for choosing an automorphism distribution where only
rightmost composite decoders (i.e., the root or any
non-leaf decoder with an all-ones address) receive an AE size greater
than unity.  Let m(i) denote the AE size for the right-most
composite decoder at depth i in rm^𝒜^*.
The heuristic would then choose:

    
  * m(i) ≤ 7  for all i, i.e.,  the number of
automorphisms applied at any local decoder is restricted; and
    
  * if m(i) ≥ 2 then m(j) ≥ 2 for all j≥ i, i.e.,
AE decoding with size greater than unity should be
applied at a node only
when all of its right descendants also have AE size greater
than unity.


Fig. <ref> shows the performance of all decoders
for (4,9), where AE decoding is applied at the right-most
composite decoders.  Included are those decoders 
whose complexity does not exceed that of AE-4, i.e.,
the CA decoder with 𝒮 = {(∅,4) }.
It can be seen that
almost all Pareto-efficient points are selected by
the given heuristic and all heuristically chosen decoders are close to
the Pareto frontier (within 0.07 dB). The decoder parameters
for Pareto-efficient points in Fig. <ref>
are given in Table <ref>.

In the following comparisons, 
the CA decoders were all selected using the heuristic described above.









 §.§ Comparison of Decoders


Fig. <ref> compares the performance
achieved by different decoders for three different RM
codes of rate 1/2. Table <ref> lists the complexity
for each tested decoder. The AE, CA and SCL decoders that we have tested are
approximately at the same complexity level. It is clear that the CA
decoding algorithm outperforms the other decoders at the same complexity
level.






Comparing the performance of CA and AE decoding, we find that the
improvement changes for different codes. The improvement for
(3,7) is merely 0.1 dB, whereas there is a gain of
0.4 dB for (5,11). 


Fig. <ref> shows a comparison of CA decoders and AE
decoders for different RM codes with the same block length (same m).
The Pareto-efficient CA decoders with decoding
complexity not exceeding that of AE-4 are depicted with solid marks,
while the AE decoders are drawn in
hollow marks. We observe that the gap between the AE decoder and the
CA decoder is larger for higher order r.
In other words, the gain achieved when applying CA
decoding compared to AE decoding is more significant for high order RM
codes. 
This trend is expected, since
higher order RM codes have more rightmost nodes, which means there
are more nodes observing “bad” channel polarization, and therefore
such codes benefit more from an uneven distribution of decoding
resources.






§ CONCLUSIONS


This paper has introduced the constituent automorphism (CA) decoding
algorithm for RM codes, which applies AE decoding at the (mainly rightmost)
constituent decoders according to a specified automorphism distribution.
CA decoders can achieve better performance versus
complexity trade-offs than other state-of-the-art decoding algorithms.
The benefits of CA decoding appear to increase as the order of
the RM code increases.
While the problem of selecting an automorphism distribution
achieving the best performance at a fixed complexity remains open,
we have provided a simple heuristic by which a “good” automorphism
distribution may be selected.
In the future, it would be interesting to study whether CA
decoding can be adapted to a suitable class of polar codes. 
As in <cit.>, 
the chosen polar-code class would need to overcome
the property that polar codes do not generally have a large
automorphism group <cit.>.





7
IEEEtran


