# Guessing Random Additive Noise Decoding
of Network Coded Data Transmitted over
Burst Error Channels

Ioannis Chatzigeorgiou, and Dmitry Savostyanov This paper was presented in
part at the 2022 IEEE International Symposium on Information Theory (ISIT),
Espoo, Finland [1].Ioannis Chatzigeorgiou is with the School of Computing and
Communications, Lancaster University, LA1 4WA, United Kingdom (email:
i.chatzigeorgiou@lancaster.ac.uk).Dmitry Savostyanov is with the Department of
Mathematical Sciences, University of Essex, CO4 3SQ, United Kingdom (email:
d.savostyanov@essex.ac.uk).

###### Abstract

We consider a transmitter that encodes data packets using network coding and
broadcasts coded packets. A receiver employing network decoding recovers the
data packets if a sufficient number of error-free coded packets are gathered.
The receiver does not abandon its efforts to recover the data packets if
network decoding is unsuccessful; instead, it employs syndrome decoding (SD)
in an effort to repair erroneously received coded packets, and then reattempts
network decoding. Most decoding techniques, including SD, assume that errors
are independently and identically distributed within received coded packets.
Motivated by the guessing random additive noise decoding (GRAND) framework, we
propose transversal GRAND (T-GRAND): an algorithm that exploits statistical
dependence in the occurrence of errors, complements network decoding and
recovers all data packets with a higher probability than SD. T-GRAND examines
error vectors in order of their likelihood of occurring and altering the
transmitted packets. Calculation and sorting of the likelihood values of all
error vectors is a simple but computationally expensive process. To reduce the
complexity of T-GRAND, we take advantage of the properties of the likelihood
function and develop an efficient method, which identifies the most likely
error vectors without computing and ordering their likelihoods.

###### Index Terms:

Network coding, random linear coding, burst noise, network decoding, syndrome
decoding, guessing random additive noise decoding (GRAND).

##  I Introduction

Random linear codes (RLCs) [2] at layers higher than the physical layer
encompass random linear fountain codes and random linear network codes. They
have the potential to increase throughput and improve resilience to network
attacks. An RLC encoder organizes input symbols into $K$ data packets and
generates $N>K$ coded packets, which are random linear combinations of the $K$
data packets. In essence, a symbol in a particular position of a coded packet
is the randomly-weighted sum of the symbols that occupy the same position in
the $K$ data packets. Thus, symbols in the same position of the $N$ coded
packets compose a codeword of length $N$. Equivalently, if all coded packets
are stacked together to form the rows of a matrix, each column of this matrix
will contain a codeword. An RLC decoder discards received coded packets that
have been corrupted by errors and attempts to reconstruct the $K$ data packets
from correctly received coded packets only.

When RLC decoding is unsuccessful, correctly received coded packets can be
used in conjunction with erroneously received coded packets. Packetized
rateless algebraic consistency (PRAC) [3] is an error correction method that
exploits the algebraic properties of RLCs to identify codewords that contain
errors and iteratively search for valid codewords to replace erroneous
codewords. According to the aforementioned correspondence between
codewords/coded packets and columns/rows of a matrix, correcting errors in
codewords is equivalent to repairing segments in coded packets. Syndrome
decoding [4] looks at the same problem from a different perspective; if errors
are detected in a codeword, syndrome decoding searches for the most likely
error vector that corrupted a codeword instead of looking for the most likely
valid codeword. Although PRAC and syndrome decoding can improve the chances of
an RLC decoder recovering all data packets, they do not account for
correlations between errors, i.e., they are more suitable for memoryless
channels, like the binary symmetric channel (BSC). To address this operational
limitation, we look into the recently proposed guessing random additive noise
decoding (GRAND) scheme.

GRAND is a maximum-likelihood decoding scheme that endeavors to identify and
nullify the effect of noise on transmitted signals [5, 6]. In low-noise
entropy conditions, guessing the noise is notably faster than performing an
exhaustive search through all possible codewords. GRAND has enabled universal
decoding, as it can decode any linear block code. Since its inception, GRAND
has been extended to non-linear codes [7], hard-input iterative decoding [8],
soft detection decoding [9] and soft-input soft-output decoding [10]. It has
also been combined with high-order modulation techniques [11, 12], modified
for fading channels [12, 13, 14] and implemented in hardware [15].

Performing syndrome decoding on coded packets is analogous to performing GRAND
on codewords, since both approaches opt for the less computationally intensive
task of guessing errors in codewords as opposed to guessing the codewords
themselves. The extension of GRAND to channels with memory was envisioned in
[6]. Soon after, GRAND Markov order (GRAND-MO) [11] was developed for guessing
errors that are correlated over time. GRAND-MO focuses on physical-layer
coding, according to which binary codewords are transmitted over a burst error
channel and, consequently, correlated errors are distributed over the bits of
each codeword. By contrast, if binary RLC encoding is used to generate and
transmit coded packets over a burst error channel, correlated errors will be
distributed over the bits of each coded packet. Knowing that, if coded packets
form the rows of a matrix, codewords occupy the columns of the same matrix, we
conclude that errors across adjacent codewords will be correlated but errors
in each codeword will be uncorrelated. Therefore, GRAND-MO cannot complement
syndrome decoding and, in general, RLC decoding. The objective of this paper
is to build on the concept of GRAND and propose transversal GRAND – an
algorithm that exploits correlations between errors in coded packets or,
equivalently, errors across codewords, in contrast to GRAND-MO, which
leverages correlations between errors in codewords.

The algorithmic details of transversal GRAND are discussed extensively in this
paper and examples illustrate how knowledge of the statistical description of
the burst error process can improve the chances of erroneously received coded
packets being repaired. The complexity of a core procedure of transversal
GRAND is studied thoroughly and a more computationally efficient approach is
developed. Simulation results establish the potential of the proposed
algorithm, which does not replace but works alongside RLC decoding, to enhance
the overall decoding performance of the receiver, that is, the probability of
decoding the transmitted coded packets and recovering the original data
packets.

The remainder of this paper has been organized as follows: Section II briefly
describes RLC decoding, which discards packets received in error. Section III
explains how syndrome decoding can repair packets in error and assist RLC
decoding. Transversal GRAND is introduced in Section IV as a means to exploit
the statistical structure of errors and improve the chances of repairing
packets. The implementation of a core procedure of transversal GRAND, which is
responsible for sorting error vectors in order of likelihood, is discussed in
Section V and revised in Section VI to reduce its computational complexity.
Performance comparisons between syndrome decoding and transversal GRAND are
presented in Section VII and key findings are summarized in Section VIII.

##  II Packet-Level Random Linear Coding and Decoding

We consider a source node, which is about to broadcast messages to one or more
destination nodes. Before transmission, each message is segmented into $K$
source packets. Each source packet has been modeled as a sequence of $B$ bits.
The $K$ source packets of $B$ bits can be expressed as a matrix
$\mathbf{U}\in\mathbb{F}^{K\times B}_{2}$, where $\mathbb{F}^{K\times B}_{2}$
denotes the set of all $K\times B$ matrices over $\mathbb{F}_{2}=\\{0,1\\}$.
Random linear network coding [2] is used to encode the $K$ source packets into
$N\geq K$ coded packets. The $N$ coded packets can also be expressed in matrix
form as $\mathbf{X}\in\mathbb{F}^{N\times B}_{2}$. The relationship between
matrices $\mathbf{X}$ and $\mathbf{U}$ is:

$\mathbf{X}=\mathbf{G}\,\mathbf{U},$ (1)

where $\mathbf{G}$ is known as the $N\times K$ generator matrix of the RLC.
Each element of $\mathbf{G}$ is selected uniformly and at random from
$\mathbb{F}_{2}$ but the seed of the pseudo-random generator at the source
node is chosen to ensure that the top $K$ rows of $\mathbf{G}$ are linearly
independent. In other words, if we express $\mathbf{G}$ as:

$\mathbf{G}=\left[\\!\begin{array}[]{c}\mathbf{G}_{K}\\\
\mathbf{M}\end{array}\\!\right],$ (2)

where $\mathbf{G}_{K}\in\mathbb{F}^{K\times K}_{2}$ and
$\mathbf{M}\in\mathbb{F}^{(N-K)\times K}_{2}$, then
$\mathrm{rank}(\mathbf{G}_{K})=K$ and, therefore,
$\mathrm{rank}(\mathbf{G})=K$. Construction of $\mathbf{G}$ in this manner
increases the probability that a destination node will receive $K$ linearly
independent coded packets and recover the $K$ source packets. Alternatively, a
systematic code could be employed. In that case, the sequence of $N$ packets,
generated by the RLC encoder, would consist of the $K$ original source packets
followed by $N-K$ coded packets, hence $\mathbf{G}_{K}=\mathbf{I}_{K}$ in (2),
where $\mathbf{I}_{K}$ is the $K\times K$ identity matrix. The value of the
seed that initializes the pseudo-random number generator and contributes to
the construction of $\mathbf{G}$ at the source node can be conveyed in the
headers of the coded packets, as explained in [16]. For this reason, we assume
that destination nodes have knowledge of $\mathbf{G}$.

Let $\mathbf{Y}$ be an erroneous copy of $\mathbf{X}$ that has been received
by a destination node. The destination node classifies the received coded
packets into error-free and erroneous coded packets, e.g., using cyclic
redundancy checks (CRCs). We denote by $\mathcal{R}$ the set of the row
indices of $\mathbf{Y}$ that correspond to correctly received coded packets,
and by $N_{\mathrm{R}}$ the number of coded packets that contain no errors,
i.e., $|\mathcal{R}|=N_{\mathrm{R}}\leq N$. The remaining $N-N_{\mathrm{R}}$
received coded packets, which have been corrupted by errors, have indices in
the set $\mkern 1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu=\\{1,\ldots,N\\}\backslash\mathcal{R}$. The destination node constructs
matrices $\mathbf{Y}_{\mathcal{R}}$ and $\mathbf{G}_{\mathcal{R}}$ from those
$N_{\mathrm{R}}$ rows of $\mathbf{Y}$ and $\mathbf{G}$, respectively, with
indices in $\mathcal{R}$. On the other hand, the indices in $\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu$ identify the
$N-N_{\mathrm{R}}$ rows of $\mathbf{Y}$ that will be used in the construction
of matrix $\mathbf{Y}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$. Matrices
$\mathbf{Y}$, $\mathbf{Y}_{\mathcal{R}}$ and $\mathbf{Y}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ can be
expressed as follows:

$\displaystyle\mathbf{Y}=\mathbf{X}\oplus\mathbf{E}\Leftrightarrow$
$\displaystyle\mathbf{Y}_{\mathcal{R}}=\mathbf{X}_{\mathcal{R}}=\mathbf{G}_{\mathcal{R}}\mathbf{U},$
(3a) $\displaystyle\mathbf{Y}=\mathbf{X}\oplus\mathbf{E}\Leftrightarrow$
$\displaystyle\mathbf{Y}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}=\mathbf{X}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}\oplus\mathbf{E}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu},$ (3b)

where $\oplus$ represents modulo-$2$ addition. The error matrix $\mathbf{E}$
contains ones in positions where errors have occurred and zeros in the
remaining positions. The indices in sets $\mathcal{R}$ and $\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu$ can be used
to decompose $\mathbf{E}$ into $\mathbf{E}_{\mathcal{R}}$ and
$\mathbf{E}_{\mkern 1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}$, where $\mathbf{E}_{\mathcal{R}}$ is equal to the
$N_{\mathrm{R}}\times B$ zero matrix.

Decoding of an RLC utilizes the $N_{\mathrm{R}}$ correctly received coded
packets, represented by $\mathbf{Y}_{\mathcal{R}}$, and discards the
$N-N_{\mathrm{R}}$ erroneously received coded packets contained in
$\mathbf{Y}_{\mkern 1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}$. The source message, represented by $\mathbf{U}$, can be obtained from
$\mathbf{X}_{\mathcal{R}}=\mathbf{G}_{\mathcal{R}}\,\mathbf{U}$ in (3a) if the
rank of $\mathbf{G}_{\mathcal{R}}$ is $K$. In that case, the relationship
$\mathbf{X}_{\mathcal{R}}=\mathbf{G}_{\mathcal{R}}\,\mathbf{U}$ can be seen as
a system of $N_{\mathrm{R}}\geq K$ linear equations, which can be reduced to a
system of $K$ linearly independent equations with $K$ unknowns, i.e., source
packets. This $K\times K$ system will return a unique solution for
$\mathbf{U}$. Otherwise, if $\mathrm{rank}(\mathbf{G}_{\mathcal{R}})<K$, the
linear system is underdetermined, i.e., it has fewer linearly independent
equations than unknowns, therefore a unique solution cannot be obtained.

If the RLC decoder does not discard the erroneous coded packets but attempts
to repair them, the probability of recovering the source message could
potentially be increased. The following section describes syndrome decoding
[4], which aims to repair erroneous coded packets without taking into
consideration the statistical properties of the channel.

##  III Guessing Uncorrelated Errors: Syndrome Decoding

We established in (3b) that the $N-N_{\mathrm{R}}$ erroneous coded packets,
which compose $\mathbf{Y}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$, can be
expressed as the modulo-$2$ sum of the corresponding transmitted coded
packets, which form the rows of $\mathbf{X}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$, and matrix
$\mathbf{E}_{\mkern 1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}$. If an estimate of $\mathbf{E}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$, denoted by
$\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$, is
computed, an estimate of the transmitted coded packets can be derived as
follows:

$\hat{\mathbf{X}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}=\mathbf{Y}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}\oplus\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}.$ (4)

CRC verification will determine which of the estimated rows of
$\hat{\mathbf{X}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ correspond
to successfully repaired coded packets. Let $\nu$ denote the number of rows in
$\hat{\mathbf{X}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ that passed
CRC verification. The indices of the $\nu$ successfully repaired coded packets
will be removed from set $\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu$ and will be
added to set $\mathcal{R}$, while the corresponding rows of
$\hat{\mathbf{X}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ will be
moved to $\mathbf{Y}_{\mathcal{R}}$ in (3a). The cardinalities of sets $\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu$ and
$\mathcal{R}$ will change to $N-N_{\mathrm{R}}-\nu$ and $N_{\mathrm{R}}+\nu$,
respectively, while the dimensions of $\hat{\mathbf{X}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ and
$\mathbf{Y}_{\mathcal{R}}$ will change to $(N-N_{\mathrm{R}}-\nu)\times B$ and
$(N_{\mathrm{R}}+\nu)\times B$, respectively. The indices of the $\nu$
repaired packets will also be used to identify the rows of the generator
matrix $\mathbf{G}$ that should be appended to $\mathbf{G}_{\mathcal{R}}$ in
(3a). If the $\nu$ repaired packets increase the rank of the enlarged
$(N_{\mathrm{R}}+\nu)\times K$ matrix $\mathbf{G}_{\mathcal{R}}$ to $K$, the
process of estimating, or ‘guessing’, matrix $\mathbf{E}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ will have
been successful in assisting the RLC decoder to recover the source message.

Syndrome decoding is a method proposed in [4] for the calculation of
$\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$. This method
takes into account that the $N\times K$ generator matrix $\mathbf{G}$ is known
to all destination nodes and applies column-wise Gaussian elimination on
$\mathbf{G}$ to transform it into standard form:

$\mathbf{G}=\left[\\!\begin{array}[]{c}\mathbf{G}_{K}\\\
\mathbf{M}\end{array}\\!\right]\xrightarrow[\text{column
operations}]{\text{elementary}}\mathbf{G}_{\mathrm{std}}=\left[\\!\begin{array}[]{c}\mathbf{I}_{K}\\\
\mathbf{P}\end{array}\\!\right].$ (5)

The $N\times(N-K)$ parity-check matrix $\mathbf{H}$ is then derived as
follows:

$\mathbf{H}=\left[\\!\begin{array}[]{c}-\mathbf{P}\;|\;\mathbf{I}_{N-K}\end{array}\\!\right]^{\top},$
(6)

so that:

$\mathbf{H}^{\top}\,\mathbf{G}=\mathbf{0}.$ (7)

When operations are performed in $\mathbb{F}_{2}$, negation has no effect on a
matrix, that is, $-\mathbf{P}=\mathbf{P}$. Multiplication of
$\mathbf{H}^{\top}$ by the received matrix $\mathbf{Y}$ produces the
$(N-K)\times B$ syndrome matrix $\mathbf{S}$, i.e.,
$\mathbf{S}=\mathbf{H}^{\top}\mathbf{Y}$. Using (1), (3b) and (7), we find
that the relationship between the syndrome matrix $\mathbf{S}$ and the error
matrix $\mathbf{E}$ is:

$\mathbf{S}=\mathbf{H}^{\top}\mathbf{Y}=\mathbf{H}^{\top}(\mathbf{X}\oplus\mathbf{E})=\mathbf{H}^{\top}(\mathbf{G}\mathbf{U}\oplus\mathbf{E})=\mathbf{H}^{\top}\mathbf{E}.$
(8)

As our focus is on the $N-N_{\mathrm{R}}$ erroneous coded packets only, we use
the set $\mkern 1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu$ to isolate the $N-N_{\mathrm{R}}$ of the $N$ rows of $\mathbf{H}$ and
$\mathbf{E}$, and reduce the two matrices to $\mathbf{H}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ and
$\mathbf{E}_{\mkern 1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}$, respectively. Consequently, expression (8) changes to:

$\mathbf{S}=\left(\mathbf{H}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}\right)^{\\!\top}\mathbf{E}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}.$ (9)

If column $b$ of $\mathbf{S}$ and $\mathbf{E}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ is denoted
by $[\mathbf{S}]_{*,b}$ and $[\mathbf{E}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}]_{*,b}$,
respectively, expression (9) can be re-written as $B$ independent systems of
$N-K$ linear equations with $N-N_{\mathrm{R}}$ unknowns per equation:

$\left[\mathbf{S}\right]_{*,b}=\left(\mathbf{H}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}\right)^{\\!\top}\left[\mathbf{E}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}\right]_{*,b}\quad\text{for}\quad b=1,\ldots,B.$ (10)

Mohammadi et al. [4] observed that erroneously received coded packets usually
contain large error-free segments, thus $\mathbf{E}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ is a sparse
matrix, that is, most of the elements in $\mathbf{E}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ are zero-
valued. Based on this observation, the solution to (10) can be formulated as:

$\displaystyle\bigl{[}\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}\bigr{]}_{*,b}=\;$
$\displaystyle\arg\min_{\mathbf{w}^{\top}}\;\lVert\mathbf{w}\rVert_{0}$ (11a)
$\displaystyle\text{subject to}\;\left(\mathbf{H}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}\right)^{\\!\top}\mathbf{w}^{\top}=\left[\mathbf{S}\right]_{*,b}$ (11b)

where $\mathbf{w}\in\mathbb{F}^{N-N_{\mathrm{R}}}_{2}$ is a row vector that
satisfies constraint (11b) and has the minimum possible number of non-zero
elements. The norm $\lVert\mathbf{w}\rVert_{0}$, which counts the non-zero
elements in $\mathbf{w}$, is defined as $\lVert\mathbf{w}\rVert_{0}=\lvert
w_{1}\rvert^{0}+\ldots+\lvert w_{N-N_{\mathrm{R}}}\rvert^{0}$ assuming that
$0^{0}=0$ [17]. Syndrome decoding considers (11a) and initiates an exhaustive
search for a solution; the sparsity of the row vector $\mathbf{w}$ is
gradually reduced, i.e., the number of ones in $\mathbf{w}$ increases, and the
search concludes when the sparsest vector $\mathbf{w}$ that satisfies (11b)
has been identified.

Although syndrome decoding has the potential to assist RLC decoding and
increase the probability of recovering the source packets [4], it does not
consider the statistical properties of the channel. It selects columns for
$\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ that are as
sparse as possible or, equivalently, have the lowest possible Hamming weight,
but it does not account for the possibility that the columns of
$\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ are
correlated. Thus, syndrome decoding is suitable for memoryless channels only,
such as the BSC. The following section describes a simplified version of the
Gilbert-Elliott channel model, which is commonly used for the characterization
of burst errors in channels with memory, and introduces transversal GRAND,
which exploits the statistical properties of burst error channels.

##  IV Guessing Burst Errors: Transversal GRAND

Coded packets at the input of the RLC decoder often contain bit errors, the
distribution of which is governed by the channel type, multi-user
interference, the modulation method and the forward error correction scheme at
the physical layer. The wireless transmission medium and the physical layer at
the source and destination nodes form a composite channel, which introduces
time-dependent correlated error bursts. Gilbert [18] modeled burst error
channels, and Elliott [19] extended his work establishing the Gilbert-Elliott
channel model.

###  IV-A The Simplified Gilbert-Elliott Channel Model

The Gilbert-Elliott channel model is a two-state Markov chain. The channel
state can be in a ‘bad’ state or a ‘good’ state, and can either transition
from one state to the other or remain in the same state. In the bad state, a
bit error is generated with a certain high probability, while in the good
state a bit error is generated with a low probability. A simplification of the
model, which is often considered in the literature, e.g., [20, 21, 11],
assumes that the bad state always induces a bit error, while the good state
never flips the value of a bit. Therefore, the simplified channel model can be
reduced to the Markov chain shown in Fig. 1, where the bad state is denoted by
$1$ and the good state is denoted by $0$. A transition from state $0$ to state
$1$ occurs with probability $p_{01}$ and causes a transmitted bit to be
received in error. A transition from state $1$ to state $0$, which occurs with
probability $p_{10}$, implies that a transmitted bit has been received
correctly. The channel may remain in state $0$ or state $1$ with probability
$1-p_{01}$ or $1-p_{10}$, respectively.

The steady-state probability of being in state $1$ represents the bit error
probability, which is given by $\varepsilon=p_{01}/(p_{01}+p_{10})$ [22, 23].
The expected number of consecutive errors provides the average length of an
error burst, and is equal to $\Lambda=1/p_{10}$ [23]. The memory of a burst
error channel is defined as $\mu=1-p_{10}-p_{01}$ [24] and provides a measure
of the persistence of the channel in remaining in a state. If $-1\leq\mu<0$,
the channel has oscillatory memory. Otherwise, if $0<\mu<1$, the channel has
persistent memory. For $\mu=0$, the channel is memoryless and the model is
reduced to the BSC model.

Estimation of the bit error probability $\varepsilon$ and the average burst
length $\Lambda$ at the destination facilitates computation of the transition
probabilities $p_{01}$ and $p_{10}$, as the latter can be expressed in terms
of the former, that is,
$p_{01}=\varepsilon/\left[\Lambda\left(1-\varepsilon\right)\right]$ and
$p_{10}=1/\Lambda$. The values of $p_{01}$ and $p_{10}$ can then be used as
inputs to our proposed algorithm and guide the derivation of matrix
$\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$.

Figure 1: The simplified Gilbert-Elliott channel model, where $0$ and $1$
represent the ‘good’ state and the ‘bad’ state, respectively.

###  IV-B The Transversal GRAND Algorithm

Let us refer to a prospective column of $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ as an error
vector of length $L=N-N_{\mathrm{R}}$. In syndrome decoding, error vectors
that have the same number of non-zero elements, i.e., the same Hamming weight,
are treated as being equally likely and can thus be queried in any order by
(11a). Furthermore, all error vectors of a given Hamming weight $w$ are
queried before error vectors of weight $w+1$. The proposed method, which we
call transversal GRAND, queries error vectors in descending order of
likelihood, as dictated by the transition probabilities of the channel model
and not by the Hamming weights of the error vectors.

Inputs: $\mathbf{H}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$,
$\mathbf{S}$, $p_{01}$, $p_{10}$

Output: $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$

origin_vector $\longleftarrow\mathbf{0}$

// initialization for $b=1$

1 for  _$b\leftarrow 1$ to $B$_ do // for all columns of
$\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$

Determine $L_{0}$ and $L_{1}$ from origin_vector

// origin_vector depends on $b$

2
$\bigl{\\{}(\ell^{(\ell)}_{0},\ell^{(\ell)}_{1})\bigr{\\}}_{\ell=1}^{(L_{0}+1)(L_{1}+1)}\longleftarrow$
CalcProbAndSort(_$p_{01}$ , $p_{10}$, $L_{0}$, $L_{1}$_)

3 for  _$\ell\leftarrow 1$ to $(L_{0}+1)(L_{1}+1)$_ do // for all probability
values

4 error_sequence$\;\longleftarrow$ GenerateErrorSequence(_$\ell^{(\ell)}_{0}$
, $\ell^{(\ell)}_{1}$, $L_{0}$, $L_{1}$_)

5

6 forall  _error vectors in error_sequence_ do

7 $\mathbf{w}^{\top}\longleftarrow$ error vector from error_sequence

8 if  _$\left(\mathbf{H}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}\right)^{\\!\top}\mathbf{w}^{\top}=\left[\mathbf{S}\right]_{*,b}$_ then

9 $\bigl{[}\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}\bigr{]}_{*,b}\longleftarrow\mathbf{w}^{\top}$

10 origin_vector $\longleftarrow\bigl{[}\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}\bigr{]}_{*,b}$

11 goto 17 // move to the outer loop and increment $b$

12 end if

13

14 end forall

15

16 end for

17

18 end for

19return $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$

Algorithm 1 Implementation of the transversal GRAND algorithm according to
which generation of the sequence of error vectors relies on the calculation
and sorting of the probabilities of occurrence of the vectors in descending
order of magnitude.

As explained in Algorithm 1, transversal GRAND uses the reduced parity-check
matrix $\mathbf{H}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$, the
syndrome matrix $\mathbf{S}$ and the transition probabilities $p_{01}$ and
$p_{10}$ of the channel model to compute $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$. State $0$
is the initial state of the Markov chain, therefore an all-zero ‘origin’
vector of length $L$ is considered in the calculation of the first column of
$\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$, i.e., when
$b=1$ (see line 1 of Algorithm 1). In general, the origin vector is set equal
to column $b-1$ of $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ when column
$b$ is being derived. Calculation of column $b$ of $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$, for
$b=1,\ldots,B$, starts with the identification of the positions in the origin
vector that are occupied by $0$ and $1$. Let $L_{0}$ and $L_{1}$ be the number
of zeros and ones in the vector, respectively (see lines 1 and 1 of Algorithm
1). Essentially, the origin vector contains the current states of $L$
independent Markov chains; $L_{0}$ of them are in state $0$ (the ‘good’ state)
and the remaining $L_{1}$ chains are in state $1$ (the ‘bad’ state).

According to the channel model, the values of $\ell_{i}$ of the $L_{i}$
elements of the origin vector will change from $i$ to $j$ with probability
$p_{ij}$, for $i,j\in\\{0,1\\}$, $i\neq j$ and $\ell_{i}=0,\dots,L_{i}$. The
values of the remaining $L_{i}-\ell_{i}$ elements will stay the same with
probability $1-p_{ij}$. The overall probability of occurrence of the
aforementioned transitions is:

$f(\ell_{0},\ell_{1})=p_{01}^{\ell_{0}}\left(1-p_{01}\right)^{L_{0}-\ell_{0}}p_{10}^{\ell_{1}}\left(1-p_{10}\right)^{L_{1}-\ell_{1}}.$
(12)

The probability of occurrence $f(\ell_{0},\ell_{1})$ is calculated for
$\ell_{0}=0,\ldots,L_{0}$ and $\ell_{1}=0,\ldots,L_{1}$, and the
$(L_{0}+1)(L_{1}+1)$ probability values compose the entries of the
$(L_{0}+1)\times(L_{1}+1)$ matrix
$\mathbf{F}=\begin{bmatrix}f(\ell_{0},\ell_{1})\end{bmatrix}$. The entries of
matrix $\mathbf{F}$ are then sorted in descending order. The coordinates of
the sorted entries constitute the set
$\\{(\ell_{0}^{(\ell)},\ell_{1}^{(\ell)})\\}_{\ell=1}^{(L_{0}+1)(L_{1}+1)}$,
as shown in line 1 of Algorithm 1, where index $\ell$ indicates the position
of the probability value in the sequence of sorted entries:

$f(\ell^{(1)}_{0},\ell^{(1)}_{1})\geq
f(\ell^{(2)}_{0},\ell^{(2)}_{1})\geq\ldots\geq
f(\ell^{((L_{0}+1)(L_{1}+1))}_{0},\ell^{((L_{0}+1)(L_{1}+1))}_{1}).$ (13)

For each coordinate pair $(\ell_{0}^{(\ell)},\ell_{1}^{(\ell)})$, the
algorithm generates a sequence of
$\binom{L_{0}}{\ell^{(\ell)}_{0}}\binom{L_{1}}{\ell^{(\ell)}_{1}}$ equally
likely error vectors (see lines 1–1 of Algorithm 1). The algorithm
sequentially considers each error vector in the sequence, assigns it to
$\mathbf{w}^{\top}$ and checks whether $\mathbf{w}^{\top}$ is a solution to
the linear equation $\left(\mathbf{H}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}\right)^{\\!\top}\mathbf{w}^{\top}=\left[\mathbf{S}\right]_{*,b}$. If
$\mathbf{w}^{\top}$ is indeed a solution, then it is selected to be column $b$
of $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$. Otherwise,
the algorithm continues to generate and query error vectors in descending
order of likelihood, until a solution is found (see lines 1–1 of Algorithm 1).
As expected, the $(L_{0}+1)(L_{1}+1)$ probability values are mapped onto a
total of

$\sum_{\ell_{0}=0}^{L_{0}}\sum_{\ell_{1}=0}^{L_{1}}\binom{L_{0}}{\ell_{0}}\binom{L_{1}}{\ell_{1}}=\left[\sum_{\ell_{0}=0}^{L_{0}}\binom{L_{0}}{\ell_{0}}\right]\left[\sum_{\ell_{1}=0}^{L_{1}}\binom{L_{1}}{\ell_{1}}\right]=2^{L_{0}+L_{1}}=2^{L}$

error vectors. Transversal GRAND terminates when solutions for all $B$ linear
equations have been estimated and $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ has been
obtained (see line 1 of Algorithm 1).

Figure 2: Example of the derivation of column $b$ of $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ using
Algorithm 1 when the previous column of $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ contains
$L_{0}=2$ zeros and $L_{1}=3$ ones. The transition probabilities are set to
$p_{01}=0.1$ and $p_{10}=0.4$.

Fig. 2 depicts an example of how transversal GRAND derives column $b$ of
$\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ from column
$b-1$, when $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ consists of
$L=5$ rows and the transition probabilities of the channel model are
$p_{01}=0.1$ and $p_{10}=0.4$. Notice in Fig. 2 that column $b-1$ of
$\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$, which is
represented by the origin vector in Algorithm 1, contains $L_{0}=2$ zeros and
$L_{1}=3$ ones. Expression (12) is used to calculate the probability of an
error vector occurring after column $b-1$ of $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ has been
observed. Of the $L_{0}=2$ zeros in column $b-1$ of $\hat{\mathbf{E}}$,
$\ell_{0}$ zeros could change to $1$ with probability $p_{01}$, while the
remaining $L_{0}-\ell_{0}$ zeros would not change value with probability
$1-p_{01}$, for $\ell_{0}=0,1,2$. On the other hand, $\ell_{1}$ of the
$L_{1}=3$ ones could change to $0$ with probability $p_{10}$ and the remaining
$L_{1}-\ell_{1}$ ones would stay unchanged with probability $1-p_{10}$, for
$\ell_{1}=0,1,2,3$. A total of $(L_{0}+1)(L_{1}+1)=12$ probability values are
computed, stored in the $3\times 4$ matrix $\mathbf{F}$, arranged in
descending order and assigned an ascending index $\ell$. The values of
$\ell_{0}$ and $\ell_{1}$ that result in the $\ell$-th highest probability
value are denoted as $(\ell_{0}^{(\ell)},\ell_{1}^{(\ell)})$, as shown in Fig.
2. For instance, the ordered sequence of probabilities of occurrence in Fig. 2
conveys that the probability of $\ell_{0}=0$ zeros changing to $1$ and
$\ell_{1}=2$ ones changing to $0$ is $0.0778$, which is the third highest
probability value; hence, $(\ell_{0}^{(3)},\ell_{1}^{(3)})=(0,2)$. This means
that, when $\ell=3$, the algorithm generates and queries
$\binom{2}{0}\binom{3}{2}=3$ error vectors – each of which occurs with
probability $0.0778$ – for column $b$ of $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$. Error
vectors are created in order of likelihood, as dictated by the ordered
sequence of probabilities of occurrence, and each vector is assigned to
$\mathbf{w}^{\top}$. The first error vector that satisfies
$\left(\mathbf{H}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern
1.5mu}\right)^{\\!\top}\mathbf{w}^{\top}=\left[\mathbf{S}\right]_{*,b}$ is
selected to be column $b$ of $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$.

In contrast to syndrome decoding, the error vectors that are generated by
transversal GRAND are not necessarily of increasing Hamming weight.
Furthermore, transversal GRAND does not assign by default the same probability
of occurrence to error vectors that have the same Hamming weight. For example,
notice that the leading weight-$3$ error vector in the sequence of error
vectors shown in Fig. 2 is not followed by error vectors of higher weights and
is not clustered together with other weight-$3$ error vectors.

##  V Implementation and Complexity of the Sorting Procedure

A core element of transversal GRAND is the calculation of the probability of
occurrence of every possible error vector that could form column $b$ of
$\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$, given
column $b-1$ and the transition probabilities $p_{01}$ and $p_{10}$. As
explained in Section IV-B, the probability of occurrence
$f(\ell_{0},\ell_{1})$ is calculated for $\ell_{0}=0,\ldots,L_{0}$ and
$\ell_{1}=0,\ldots,L_{1}$, where the values of $L_{0}$ and $L_{1}$ are
determined by column $b-1$. The procedure of calculating and sorting the
$(L_{0}+1)(L_{1}+1)$ probability values is called CalcProbAndSort, as can be
seen in Line 1 of Algorithm 1. This section investigates the computational
complexity of CalcProbAndSort.

Recall from Section IV-B that the $(L_{0}+1)(L_{1}+1)$ probability values
compose the entries of matrix $\mathbf{F}$. Let
$f_{0}(\ell_{0})=p_{01}^{\ell_{0}}(1-p_{01})^{L_{0}-\ell_{0}}$ and
$f_{1}(\ell_{1})=p_{10}^{\ell_{1}}(1-p_{10})^{L_{1}-\ell_{1}}$. Matrix
$\mathbf{F}$ is a rank-one matrix, which is generated as a trace of function
$f(\ell_{0},\ell_{1})=f_{0}(\ell_{0})f_{1}(\ell_{1})$ on the two-dimensional
uniform tensor product grid $\\{(\ell_{0},\ell_{1})\\}$:

$\mathbf{F}=\begin{bmatrix}f_{0}(0)\\\ f_{0}(1)\\\ \vdots\\\
f_{0}(L_{0})\end{bmatrix}\begin{bmatrix}f_{1}(0)&f_{1}(1)&\cdots&f_{1}(L_{1})\end{bmatrix}.$
(14)

When the transition probabilities take the values $p_{01}=0$, $p_{01}=1$,
$p_{10}=0$ or $p_{10}=1$, the singular case of $\mathbf{F}=\mathbf{0}$ is
observed. If $p_{01}=0$ or $p_{10}=0$, the channel model has one state only.
If $p_{01}=1$ or $p_{10}=1$, the channel has oscillatory memory, that is, the
probability of remaining in a state is lower than the steady-state probability
of being in that state [24]. These extreme cases are not of interest in the
context of this paper and are ignored. We assume that $0<p_{01}<1$ and
$0<p_{10}<1$ to ensure that all entries of $\mathbf{F}$ are positive, i.e.,
$f(\ell_{0},\ell_{1})>0$.

Since $f(\ell_{0},\ell_{1})$ is a product of probabilities, it could take very
small values that would lead to an arithmetic underflow. A well-known approach
to this problem is to operate in the log-domain and convert the products of
probabilities into sums of log-probabilities111Although any base can be used
for the $\log$ function, numerical examples in this paper use the the
logarithm to the base $2$.. Noting that

$\displaystyle-\log f(\ell_{0},\ell_{1})$
$\displaystyle=-\ell_{0}\log(p_{01})-(L_{0}-\ell_{0})\log(1-p_{01})-\ell_{1}\log(p_{10})-(L_{1}-\ell_{1})\log(1-p_{10})$
$\displaystyle=\underbrace{\ell_{0}\log\Bigl{(}\frac{1-p_{01}}{p_{01}}\Bigr{)}}_{\varphi_{0}(\ell_{0})}+\underbrace{\ell_{1}\log\Bigl{(}\frac{1-p_{10}}{p_{10}}\Bigr{)}}_{\varphi_{1}(\ell_{1})}-\underbrace{\Bigl{(}L_{0}\log(1-p_{01})+L_{1}\log(1-p_{10})\Bigr{)}}_{\mathrm{\xi}}$
$\displaystyle=\underbrace{\varphi_{0}(\ell_{0})+\varphi_{1}(\ell_{1})}_{\varphi(\ell_{0},\ell_{1})}\;-\;\mathrm{\xi},$
(15)

we consider the matrix
$\mathbf{\Phi}=\begin{bmatrix}\varphi(\ell_{0},\ell_{1})\end{bmatrix}$ with
elements
$\varphi(\ell_{0},\ell_{1})=\varphi_{0}(\ell_{0})+\varphi_{1}(\ell_{1})$ and
of the same size as $\mathbf{F}$. The constant term $\xi$ in (V) contributes
equally to all log-probability values and can be ignored. The negative
logarithm is a monotonically decreasing function, hence the largest element of
$\mathbf{F}$ corresponds to the smallest element of $\mathbf{\Phi}.$
Consequently, instead of arranging the elements of $\mathbf{F}$ in decreasing
order, we can now sort the elements of $\mathbf{\Phi}$ in increasing order.

The values of

$\alpha_{0}=\log\Bigl{(}\frac{1-p_{01}}{p_{01}}\Bigr{)}\qquad\text{and}\qquad\alpha_{1}=\log\Bigr{(}\frac{1-p_{10}}{p_{10}}\Bigl{)}$
(16)

can be computed and stored prior to the execution of the transversal GRAND
algorithm. Calculation of $\varphi_{0}(\ell_{0})=\alpha_{0}\ell_{0}$ requires
one multiplication. Alternatively, we can note that $\varphi_{0}(\ell_{0})$
can be written in recursive form as
$\varphi_{0}(\ell_{0})=\varphi_{0}(\ell_{0}-1)+\alpha_{0}$ and hence,
calculation of $\varphi_{0}(\ell_{0})$ for $\ell_{0}=0,\ldots,L_{0}$ involves
$L_{0}$ additions. Using the same reasoning, we deduce that $L_{1}$ additions
are required for the calculation of $\varphi_{1}(\ell_{1})$ for
$\ell_{1}=0,\ldots,L_{1}$. Having obtained the $(L_{0}+1)$ values of
$\varphi_{0}(\ell_{0})$ and the $(L_{1}+1)$ values of $\varphi_{1}(\ell_{1})$,
the procedure continues with the evaluation of the $(L_{0}+1)(L_{1}+1)$
entries of matrix $\mathbf{\Phi}$. One sum is evaluated for every entry of
matrix $\mathbf{\Phi}$, according to (V). Therefore,
$(L_{0}+1)(L_{1}+1)+L_{0}+L_{1}$ additions are needed for the computation of
matrix $\mathbf{\Phi}.$

After CalcProbAndSort computes the entries $\varphi(\ell_{0},\ell_{1})$ and
inserts them in matrix $\mathbf{\Phi}$, it is tasked with arranging them in
increasing order. Available sorting algorithms achieve different tradeoffs
between runtime, stability and memory usage. Low overall computational
complexity requires a short runtime, which translates into a small number of
executed comparisons. If $n$ is the number of elements to be sorted, the
worst-case number of comparisons is $O(n\log n),$ e.g., using the Heapsort
[25] algorithm. The fact that Heapsort is not a stable algorithm does not
affect the sorting process, as the relative order of equal entries in matrix
$\mathbf{\Phi}$ does not have to be preserved. For this reason, Heapsort is
adopted by CalcProbAndSort to sort the $n=(L_{0}+1)(L_{1}+1)$ elements of
matrix $\mathbf{\Phi}$.

Recall that the output of CalcProbAndSort is not a sequence of sorted
probability values but a sequence of coordinates
$\\{(\ell^{(\ell)}_{0},\ell^{(\ell)}_{1})\\}$, which point to the locations of
the sorted probability values in matrix $\mathbf{\Phi}$. The following section
examines the relationship between $\varphi(\ell_{0},\ell_{1})$ and the
structure of matrix $\mathbf{\Phi}$ in order to develop a procedure that
generates the coordinates of the ordered probability values without the need
to first calculate all of the probability values.

##  VI Implementation and Complexity of a Tracing Procedure

This section introduces TraceSortedProb, a procedure that traces negative log-
probability values, from the smallest to the largest, without first
calculating them and then sorting them, and outputs their coordinates.
TraceSortedProb is proposed as an efficient alternative to CalcProbAndSort.
The structural properties of matrix $\mathbf{\Phi}$ that TraceSortedProb takes
advantage of are described in detail and the complexity of the proposed
procedure is contrasted with that of CalcProbAndSort.

###  VI-A Fundamentals of the Tracing Procedure

Our goal is to trace the smallest elements of matrix
$\mathbf{\Phi}=\begin{bmatrix}\varphi(\ell_{0},\ell_{1})\end{bmatrix}$, taking
in account that
$\varphi(\ell_{0},\ell_{1})=\varphi_{0}(\ell_{0})+\varphi_{1}(\ell_{1}),$
where $\varphi_{0}(\ell_{0})=\alpha_{0}\ell_{0}$ and
$\varphi_{1}(\ell_{1})=\alpha_{1}\ell_{1}.$ The value of
$\varphi(\ell_{0},\ell_{1})$ occupies the entry in row $\ell_{0}+1$ and column
$\ell_{1}+1$ of matrix $\mathbf{\Phi}$. We first consider
$\varphi_{0}(\ell_{0})$ and observe that, according to (16), $\alpha_{0}>0$
for $p_{01}<\tfrac{1}{2}$, $\alpha_{0}<0$ for $p_{01}>\tfrac{1}{2}$, and
$\alpha_{0}=0$ for $p_{01}=\tfrac{1}{2}$. The sequence
$\\{\varphi_{0}(\ell_{0})\\}$ for $\ell_{0}=0,\ldots,L_{0}$ is monotonically
increasing for $\alpha_{0}>0$, monotonically decreasing for $\alpha_{0}<0$,
and constant for $\alpha_{0}=0$. The same conclusions can be drawn for the
sequence $\\{\varphi_{1}(\ell_{1})\\}$ for $\ell_{1}=0,\ldots,L_{1}$.

####  VI-A1 Identifying the smallest entry of matrix $\mathbf{\Phi}$

We established that the smallest element in sequence
$\\{\varphi_{i}(\ell_{i})\\}$, where $i\in\\{0,1\\}$, is $\varphi_{i}(0)$ for
$\alpha_{i}\geq 0$, and $\varphi_{i}(L_{i})$ for $\alpha_{i}\leq 0$. Depending
on the values of $\alpha_{0}$ and $\alpha_{1}$, one of the corner entries of
matrix $\mathbf{\Phi}$, which hold $\varphi(0,0)$, $\varphi(L_{0},0)$,
$\varphi(0,L_{1})$ and $\varphi(L_{0},L_{1})$, will be the smallest entry of
the matrix. Henceforth, we assume that $\alpha_{0}>0$ and $\alpha_{1}>0$. As a
result, the sequences $\\{\varphi_{0}(\ell_{0})\\}$ and
$\\{\varphi_{1}(\ell_{1})\\}$ are both monotonically increasing and,
therefore, the smallest entry of matrix $\mathbf{\Phi}$ is in row $1$ and
column $1$, where $\varphi(0,0)$ resides. Consequently,
$(\ell^{(1)}_{0},\ell^{(1)}_{1})=(0,0)$.

The cases where $\alpha_{0}\leq 0$ or $\alpha_{1}\leq 0$ differ only in the
direction in which sequences $\\{\varphi_{0}(\ell_{0})\\}$ and
$\\{\varphi_{1}(\ell_{1})\\}$ increase. For example, let us assume that
$p_{01}<\tfrac{1}{2}$ and $p_{10}>\tfrac{1}{2}$, hence, $\alpha_{0}>0$ and
$\alpha_{1}<0$. This means that $\\{\varphi_{0}(\ell_{0})\\}$ is a
monotonically increasing sequence, but $\\{\varphi_{1}(\ell_{1})\\}$ is a
monotonically decreasing sequence. If we set
$\tilde{p}_{10}=1-p_{10}<\tfrac{1}{2}$ or, equivalently,
$\tilde{\alpha}_{1}=-\alpha_{1}>0$, we obtain the monotonically increasing
sequence $\\{\tilde{\varphi}_{1}(\ell_{1})\\}$, which satisfies
$\tilde{\varphi}_{1}(\ell_{1})=\varphi_{1}(L_{1}-\ell_{1})$. The negative log-
probability function
$\tilde{\varphi}(\ell_{0},\ell_{1})=\varphi_{0}(\ell_{0})+\tilde{\varphi}_{1}(\ell_{1})$
is used to generate the entries of matrix $\tilde{\mathbf{\Phi}}$. If the
coordinate pair of the $\ell$-th smallest entry of matrix
$\tilde{\mathbf{\Phi}}$ is $(\ell^{(\ell)}_{0},\tilde{\ell}^{(\ell)}_{1})$,
then the $\ell$-th smallest entry of the original matrix $\mathbf{\Phi}$ will
simply be
$(\ell^{(\ell)}_{0},\ell^{(\ell)}_{1})=(\ell^{(\ell)}_{0},L_{1}-\tilde{\ell}^{(\ell)}_{1})$.
On the other hand, the case of $p_{10}=\tfrac{1}{2}$ and, thus, $\alpha_{1}=0$
leads to a constant sequence $\\{\varphi_{1}(\ell_{1})\\}$. Ordering the
entries of $\mathbf{\Phi}$ becomes a trivial problem, as it depends solely on
the monotonicity of sequence $\\{\varphi_{0}(\ell_{0})\\}$, which is
determined by the sign of $\alpha_{0}$. The arguments that were made for
$\alpha_{1}<0$ and $\alpha_{1}=0$ can also be made for $\alpha_{0}<0$ and
$\alpha_{0}=0$.

####  VI-A2 Identifying the second smallest entry of matrix $\mathbf{\Phi}$

Given that
$\varphi(\ell_{0},\ell_{1})=\varphi_{0}(\ell_{0})+\varphi_{1}(\ell_{1})$ and
that $\varphi(0,0)$ holds the smallest entry of matrix $\mathbf{\Phi}$ for
$\alpha_{0}>0$ and $\alpha_{1}>0$, the second smallest entry will be either
$\varphi(1,0)$ or $\varphi(0,1)$. To compare these two candidates for the
second smallest entry, we evaluate the following differences:

$\begin{split}\varphi(1,0)-\varphi(0,0)&=\varphi_{0}(1)-\varphi_{0}(0)=\alpha_{0}(1-0)=\alpha_{0},\\\
\varphi(0,1)-\varphi(0,0)&=\varphi_{1}(1)-\varphi_{1}(0)=\alpha_{1}(1-0)=\alpha_{1}.\end{split}$
(17)

Therefore, the problem boils down to comparing $\alpha_{0}$ with $\alpha_{1}$.
If $\alpha_{0}<\alpha_{1}$, then $\varphi(1,0)$ is the second smallest entry
of matrix $\mathbf{\Phi}$, hence $(\ell^{(2)}_{0},\ell^{(2)}_{1})=(1,0)$;
otherwise, $(\ell^{(2)}_{0},\ell^{(2)}_{1})=(0,1)$. The process of pinpointing
the second smallest entry of matrix $\mathbf{\Phi}$ is illustrated in Fig.
3(a). Note that the coordinates of the smallest and second smallest entries of
$\mathbf{\Phi}$, namely $(\ell^{(1)}_{0},\ell^{(1)}_{1})$ and
$(\ell^{(2)}_{0},\ell^{(2)}_{1})$, have been determined by the values of
$\alpha_{0}$ and $\alpha_{1}$ only.

####  VI-A3 Generalization for the remaining entries of matrix $\mathbf{\Phi}$

$\ell_{0}=0$$\ell_{0}=1$$\ell_{0}=2$$\ell_{1}=0$$\ell_{1}=1$$\ell_{1}=2$$\varphi_{1}(\ell_{1})$$\varphi_{0}(\ell_{0})$$\mathbf{\Phi}$$\alpha_{0}$$\alpha_{1}$

$\ell_{0}$$\ell_{1}$$0$$1$$2$$3$$4$$0$$1$$2$$3$$4$$4\alpha_{1}$$\alpha_{0}+2\alpha_{1}$$2\alpha_{0}+\alpha_{1}$$3\alpha_{0}$$\mathcal{L}$$\bar{\mathcal{L}}$

Figure 3: Pictorial representation of how TraceSortedProb pinpoints the
entries of matrix $\mathbf{\Phi}$, from the smallest to the largest. Here,
$p_{01}<\tfrac{1}{2},$ $p_{10}<\tfrac{1}{2},$ and $p_{01}>p_{10}$ or,
equivalently, $\alpha_{0}>0$, $\alpha_{1}>0$ and $\alpha_{0}<\alpha_{1}$. (a)
A fragment of the matrix $\mathbf{\Phi}$ with the plane above visualizing the
value of its elements. The smallest entry of $\mathbf{\Phi}$, which
corresponds to the largest probability value, is at
$(\ell_{0}^{(1)},\ell_{1}^{(1)})=(0,0)$ and is depicted by a large blue ball.
Two candidates for the second smallest value are shown as small red balls at
$(\ell_{0},\ell_{1})=(1,0)$ and $(\ell_{0},\ell_{1})=(0,1)$, where
$\varphi(\ell_{0},\ell_{1})$ takes the values $\alpha_{0}$ and $\alpha_{1}$,
respectively. Since $\alpha_{0}<\alpha_{1}$, the second smallest entry of
$\mathbf{\Phi}$ is at $(\ell_{0}^{(2)},\ell_{1}^{(2)})=(1,0)$. (b) A larger
fragment of matrix $\mathbf{\Phi}$. The shaded blue region represents the set
$\mathcal{L}$ of the $\ell$ smallest entries of $\mathbf{\Phi}$. The largest
element in $\mathcal{L}$ is depicted by a large blue ball. The candidates for
the $(\ell+1)$-th smallest entry are the corners of $\bar{\mathcal{L}}$, shown
as small red balls. Labels on candidate elements represent the values
$\varphi(\ell_{0},\ell_{1})=\alpha_{0}\ell_{0}+\alpha_{1}\ell_{1}$.

To explain how TraceSortedProb proceeds after the two smallest entries of
matrix $\mathbf{\Phi}$ have been identified, we start by making some simple
observations that follow from the sum structure of
$\varphi(\ell_{0},\ell_{1})$ and the linearity of the univariate functions
$\varphi_{0}(\ell_{0})$ and $\varphi_{1}(\ell_{1})$. Notice that the entries
of matrix $\mathbf{\Phi}$ obey the following column-wise and row-wise
properties:

$\begin{split}\ell_{1}^{\prime}\leq\ell_{1}^{\prime\prime}\quad\Leftrightarrow\quad\varphi(\ell_{0},\ell_{1}^{\prime})\leq\varphi(\ell_{0},\ell_{1}^{\prime\prime})&\qquad\text{for
all $\ell_{0}=0,\ldots,L_{0},$}\\\
\ell_{0}^{\prime}\leq\ell_{0}^{\prime\prime}\quad\Leftrightarrow\quad\varphi(\ell_{0}^{\prime},\ell_{1})\leq\varphi(\ell_{0}^{\prime\prime},\ell_{1})&\qquad\text{for
all $\ell_{1}=0,\ldots,L_{1}.$}\end{split}$ (18)

To extend this observation, we introduce a weak partial order relation and a
strong partial order relation for the coordinate pairs, denoted by
$\preccurlyeq$ and $\prec$, respectively:

$\begin{split}(\ell_{0}^{\prime},\ell_{1}^{\prime})\preccurlyeq(\ell_{0}^{\prime\prime},\ell_{1}^{\prime\prime})&\quad\Leftrightarrow\quad\ell_{0}^{\prime}\leq\ell_{0}^{\prime\prime}\quad\text{and}\quad\ell_{1}^{\prime}\leq\ell_{1}^{\prime\prime},\\\
(\ell_{0}^{\prime},\ell_{1}^{\prime})\prec(\ell_{0}^{\prime\prime},\ell_{1}^{\prime\prime})&\quad\Leftrightarrow\quad(\ell_{0}^{\prime},\ell_{1}^{\prime})\preccurlyeq(\ell_{0}^{\prime\prime},\ell_{1}^{\prime\prime})\quad\text{and}\quad(\ell_{0}^{\prime},\ell_{1}^{\prime})\neq(\ell_{0}^{\prime\prime},\ell_{1}^{\prime\prime}).\end{split}$

Then, it follows from (18) that

$(\ell_{0}^{\prime},\ell_{1}^{\prime})\preccurlyeq(\ell_{0}^{\prime\prime},\ell_{1}^{\prime\prime})\quad\Rightarrow\quad\varphi(\ell_{0}^{\prime},\ell_{1}^{\prime})\leq\varphi(\ell_{0}^{\prime\prime},\ell_{1}^{\prime\prime}).$
(19)

Suppose that the order of the $\ell$ smallest entries of matrix
$\mathbf{\Phi}$ has been determined, that is:

$\varphi(\ell_{0}^{(1)},\ell_{1}^{(1)})\leq\varphi(\ell_{0}^{(2)},\ell_{1}^{(2)})\leq\cdots\leq\varphi(\ell_{0}^{(\ell)},\ell_{1}^{(\ell)}),$
(20)

and the $\ell$ coordinate pairs form the set
$\mathcal{L}=\\{(\ell_{0}^{(\ell^{\prime})},\ell_{1}^{(\ell^{\prime})})\\}_{\ell^{\prime}=1}^{\ell}$,
which has a particular geometric structure, as shown in Fig. 3(b). If
$(\ell_{0},\ell_{1})\in\mathcal{L}$ and
$(\ell_{0}^{\prime},\ell_{1}^{\prime})\preccurlyeq(\ell_{0},\ell_{1}),$ then
from (19) we have
$\varphi(\ell_{0}^{\prime},\ell_{1}^{\prime})\leq\varphi(\ell_{0},\ell_{1}),$
thus $(\ell_{0}^{\prime},\ell_{1}^{\prime})\in\mathcal{L}.$ This means that
every element $(\ell_{0},\ell_{1})\in\mathcal{L}$ defines a set of indices
$\mathcal{S}(\ell_{0},\ell_{1})=\\{(\ell_{0}^{\prime},\ell_{1}^{\prime}):(\ell_{0}^{\prime},\ell_{1}^{\prime})\preccurlyeq(\ell_{0},\ell_{1})\\}$
that make up a rectangle with coordinates $(0,0)$, $(0,\ell_{1})$,
$(\ell_{0},\ell_{1})$ and $(\ell_{0},0)$ in the grid specified by matrix
$\mathbf{\Phi}$. The elements of $\mathcal{S}(\ell_{0},\ell_{1})$ are also
members of $\mathcal{L}$, i.e.,

$(\ell_{0},\ell_{1})\in\mathcal{L}\quad\Rightarrow\quad\mathcal{S}(\ell_{0},\ell_{1})\subseteq\mathcal{L}.$
(21)

Hence,
$\mathcal{L}=\bigcup_{\ell^{\prime}=1,\ldots,\ell}\mathcal{S}(\ell_{0}^{(\ell^{\prime})},\ell_{1}^{(\ell^{\prime})}).$
Many of these rectangles are fully contained in others, and can be omitted
from the union of sets that compose $\mathcal{L}$ without changing the result.
Rectangles that cannot be omitted are those that enclose elements, denoted as
$(c_{0},c_{1})\in\mathcal{L}$, that are not contained in any other rectangular
set:

$(c_{0},c_{1}):\quad\nexists(\ell_{0},\ell_{1})\in\mathcal{L}:\>(c_{0},c_{1})\prec(\ell_{0},\ell_{1}).$
(22)

We call such elements the corners of $\mathcal{L}$, and denote the set of all
corners of $\mathcal{L}$ as $\mathcal{C}_{\mathcal{L}}$. For example, if
$\mathcal{L}$ is defined as in Fig. 3(b), the set of all corners of
$\mathcal{L}$ is given by $\mathcal{C}_{\mathcal{L}}=\\{(0,3),(1,1),(2,0)\\}$.
By tracking $\mathcal{C}_{\mathcal{L}}$, we maintain the minimal
representation of the coordinate set $\mathcal{L}$ at each step of the
procedure, as
$\mathcal{L}=\bigcup_{(c_{0},c_{1})\in\mathcal{C}_{\mathcal{L}}}\mathcal{S}(c_{0},c_{1}).$
Furthermore, the element that was added last to $\mathcal{L}$, that is,
$(\ell_{0}^{(\ell)},\ell_{1}^{(\ell)})$, is always a corner of $\mathcal{L}.$
Indeed, if
$(\ell_{0}^{(\ell)},\ell_{1}^{(\ell)})\notin\mathcal{C}_{\mathcal{L}}$, then
$\exists\ell^{\prime}<\ell$ such that
$(\ell_{0}^{(\ell)},\ell_{1}^{(\ell)})\prec(\ell_{0}^{(\ell^{\prime})},\ell_{1}^{(\ell^{\prime})})$,
which leads to
$\varphi(\ell_{0}^{(\ell)},\ell_{1}^{(\ell)})<\varphi(\ell_{0}^{(\ell^{\prime})},\ell_{1}^{(\ell^{\prime})})$
according to (19). The latter inequality contradicts (20) for
$\ell^{\prime}<\ell$, therefore the original assumption
$(\ell_{0}^{(\ell)},\ell_{1}^{(\ell)})\notin\mathcal{C}_{\mathcal{L}}$ must be
false, hence
$(\ell_{0}^{(\ell)},\ell_{1}^{(\ell)})\in\mathcal{C}_{\mathcal{L}}$ must be
true.

Observe in Fig. 3(b) that, as $\ell$ increases, more entries of
$\mathbf{\Phi}$ are traced, their coordinate pairs are added to $\mathcal{L}$,
and $\mathcal{L}$ grows in size. The $(L_{0}+1)(L_{1}+1)-\ell$ coordinate
pairs of the entries of $\mathbf{\Phi}$ that have not been considered yet in
the tracing process compose the complementary set
$\bar{\mathcal{L}}=\\{(\ell_{0},\ell_{1})\notin\mathcal{L}\\}$, which has
structural properties that mirror those of $\mathcal{L}$. Whereas
$\mathcal{L}$ holds the coordinates of the $\ell$ smallest entries of
$\mathbf{\Phi}$, $\bar{\mathcal{L}}$ consists of the coordinates of the
$(L_{0}+1)(L_{1}+1)-\ell$ largest entries of $\mathbf{\Phi}$. Whereas the
coordinate pair that corresponds to the largest of the $\ell$ smallest entries
of $\mathbf{\Phi}$ is one of the corners of $\mathcal{L}$, the coordinate pair
that corresponds to the smallest of the $(L_{0}+1)(L_{1}+1)-\ell$ largest
entries of $\mathbf{\Phi}$ is one of the corners of $\bar{\mathcal{L}}$. Let
the corners of $\mathcal{L}$ be arranged in
$\mathcal{C}_{\mathcal{L}}=\\{(c_{0}^{(1)},c_{1}^{(1)}),\ldots,(c_{0}^{(C)},c_{1}^{(C)})\\}$
such that $c_{0}^{(1)}<\ldots<c_{0}^{(C)}$ and
$c_{1}^{(1)}>\ldots>c_{1}^{(C)}$, where $C=|\mathcal{C}_{\mathcal{L}}|$. The
corners of $\bar{\mathcal{L}}$ can then be calculated from the corners of
$\mathcal{L}$ as follows:

$\mathcal{C}_{\bar{\mathcal{L}}}=\\{\underbrace{(0,c_{1}^{(1)}+1)}_{\text{omit
if $c_{1}^{(1)}\geq
L_{1}$}},(c_{0}^{(1)}+1,c_{1}^{(2)}+1),\ldots,(c_{0}^{(C-1)}+1,c_{1}^{(C)}+1),\underbrace{(c_{0}^{(C)}+1,0)}_{\text{omit
if $c_{0}^{(C)}\geq L_{0}$}}\\}.$ (23)

Going back to the example in Fig. 3(b), we mentioned that
$\mathcal{C}_{\mathcal{L}}=\\{(0,3),(1,1),(2,0)\\}$, therefore
$\mathcal{C}_{\bar{\mathcal{L}}}=\\{(0,4),(1,2),(2,1),(3,0)\\}$ based on (23).

To determine the $(\ell+1)$-th smallest entry of $\mathbf{\Phi}$ and obtain
the pair $(\ell_{0}^{(\ell+1)},\ell_{1}^{(\ell+1)})$, we need to find the
smallest entry among the candidates
$(\ell_{0},\ell_{1})\in\mathcal{C}_{\bar{\mathcal{L}}},$ i.e.,

$(\ell_{0}^{(\ell+1)},\ell_{1}^{(\ell+1)})=\underset{(\ell_{0},\ell_{1})\in\mathcal{C}_{\bar{\mathcal{L}}}}{\arg\,\min}\,\varphi(\ell_{0},\ell_{1})=\underset{(\ell_{0},\ell_{1})\in\mathcal{C}_{\bar{\mathcal{L}}}}{\arg\,\min}\left(\alpha_{0}\ell_{0}+\alpha_{1}\ell_{1}\right).$
(24)

Essentially, the bivariate function
$\varphi(\ell_{0},\ell_{1})=\alpha_{0}\ell_{0}+\alpha_{1}\ell_{1}$ can be seen
as a ‘penalty’ that is minimized by TraceSortedProb. Fig. 3(b) provides a
visualization of the penalty for each of the four elements of
$\mathcal{C}_{\bar{\mathcal{L}}}$.

$\ell_{0}$$\ell_{1}$$0$$1$$2$$3$$0$$1$$2$$3$$0$$1.22$$2.44$$3.67$$0.58$$1.81$$3.03$$4.25$$1.17$$2.39$$3.61$$4.84$$1.75$$2.98$$4.2$$5.42$

$\ell_{0}$$\ell_{1}$$0$$1$$2$$3$$0$$1$$2$$3$$1.22$$0.59$$\bar{\mathcal{L}}$

$\ell_{0}$$\ell_{1}$$0$$1$$2$$3$$0$$1$$2$$3$$1.22$$1.17$$\mathcal{L}$$\bar{\mathcal{L}}$

$\ell_{0}$$\ell_{1}$$0$$1$$2$$3$$0$$1$$2$$3$$1.22$$1.76$$\mathcal{L}$$\bar{\mathcal{L}}$

$\ell_{0}$$\ell_{1}$$0$$1$$2$$3$$0$$1$$2$$3$$1.76$$2.44$$1.81$$\mathcal{L}$$\bar{\mathcal{L}}$

$\ell_{0}$$\ell_{1}$$0$$1$$2$$3$$0$$1$$2$$3$$2.44$$1.81$$\mathcal{L}$$\bar{\mathcal{L}}$

Figure 4: Example demonstrating the operation of TraceSortedProb for
$p_{01}=0.4$, $p_{10}=0.3$, $L_{0}=3$ and $L_{1}=3$. Based on these values,
$\alpha_{0}=0.59$ and $\alpha_{1}=1.22$ (displayed values have been rounded up
to two decimal places). The entries of $\mathbf{\Phi}$ as well as a path that
begins at the smallest entry and ends at the fifth smallest entry of
$\mathbf{\Phi}$ are presented in (a) for reference. The process of
TraceSortedProb for identifying the five smallest entries of $\mathbf{\Phi}$,
without first calculating all entries and then ordering them, is described in
(b)-(f). Blue balls of any size identify corners of $\mathcal{L}$, while red
balls of any size represent corners of $\bar{\mathcal{L}}$. A large blue ball
marks the coordinate pair that has been added last to $\mathcal{L}$, as it
points to the $\ell$-th smallest value of $\mathbf{\Phi}$, for $\ell=1$ in (b)
to $\ell=5$ in (f). Labels on red balls represent the values of
$\varphi(\ell_{0},\ell_{1})$ at these points. A large red ball pinpoints the
corner of $\bar{\mathcal{L}}$ that is chosen for a value of $\ell$ and changes
to a large blue ball after it is added to $\mathcal{L}$ for the next value of
$\ell$. Observe that the large blue balls in (b)-(f) occupy the same
coordinates and in the same order as the coordinates of the five smallest
entries in (a).

An example of the step-by-step process of TraceSortedProb to identify the five
smallest entries of matrix $\mathbf{\Phi}$ for $\alpha_{0}=0.59$,
$\alpha_{1}=1.22$, $L_{0}=3$ and $L_{1}=3$ is illustrated in Fig. 4. As
explained in Section VI-A1 and shown in Fig. 4(b), the smallest entry is at
$(0,0)$ given that $a_{0}>0$ and $a_{1}>0$. Hence,
$\mathcal{C}_{\mathcal{L}}=\\{(0,0)\\}$ for $\ell=1$, and
$\mathcal{C}_{\bar{\mathcal{L}}}=\\{(0,1),(1,0)\\}$ based on (23). Using
$\eqref{eq:min_penalty}$, we find that transitioning from $(0,0)$ to $(1,0)$
carries a lower penalty than transitioning to $(0,1)$. Therefore, the second
smallest entry, i.e., for $\ell=2$, is at $(1,0)$. The pair $(1,0)$ is added
to $\mathcal{L}$ and $\mathcal{C}_{\mathcal{L}}$, previous members of
$\mathcal{C}_{\mathcal{L}}$ that do not comply with (22) are removed from
$\mathcal{C}_{\mathcal{L}}$, the complementary set
$\mathcal{C}_{\bar{\mathcal{L}}}$ is obtained from $\mathcal{C}_{\mathcal{L}}$
using (23), and the coordinate pair in $\mathcal{C}_{\bar{\mathcal{L}}}$ that
minimizes $\eqref{eq:min_penalty}$ points to the location of the third
smallest entry of $\mathbf{\Phi}$. This iterative process could continue until
all entries of $\mathbf{\Phi}$ have been considered, but it could also
terminate when the coordinates of a desired proportion of the smallest – and,
hence, most significant – entries of $\mathbf{\Phi}$ have been determined.

###  VI-B Complexity Analysis

Similarly to CalcProbAndSolve, the terms
$\alpha_{0}=\log(\tfrac{1-p_{01}}{p_{01}})$ and
$\alpha_{1}=\log(\tfrac{1-p_{10}}{p_{10}})$ are computed prior to the
execution of the algorithm. Part of the running time of TraceSortedProb is
dedicated to the evaluation of the products $\alpha_{0}\ell_{0}$ and
$\alpha_{1}\ell_{1}$ in (24) for all values of $\ell_{0}$ and $\ell_{1}$.
Notice that as $\ell_{0}$ increases in steps of $1$, the value of
$\alpha_{0}\ell_{0}$ increases in steps of $\alpha_{0}$ (i.e., one addition
per step). Calculation of the products $\alpha_{0}\ell_{0}$ and
$\alpha_{1}\ell_{1}$, for $\ell_{0}=0,\ldots,L_{0}$ and
$\ell_{1}=0,\ldots,L_{1}$, involves $L_{0}$ increments of $\ell_{0}$ and
$L_{1}$ increments of $\ell_{1}$, which result in $L_{0}+L_{1}$ sequential
additions. An extra addition is required to evaluate the penalty
$\alpha_{0}\ell_{0}+\alpha_{1}\ell_{1}$ whenever a new coordinate pair
$(\ell_{0},\ell_{1})$ is inserted in $\mathcal{C}_{\bar{\mathcal{L}}}$.

As explained in Section VI-A3, TraceSortedProb maintains and updates
$\mathcal{C}_{\mathcal{L}}$ and $\mathcal{C}_{\bar{\mathcal{L}}}$, which
contain the corners of $\mathcal{L}$ and $\bar{\mathcal{L}}$, respectively. As
the procedure traverses through the entries of matrix $\mathbf{\Phi}$ and the
size of $\mathcal{L}$ increases in each step, maintaining and updating
$\mathcal{C}_{\mathcal{L}}$ and $\mathcal{C}_{\bar{\mathcal{L}}}$ requires no
more than $|\mathcal{C}_{\mathcal{L}}|$ operations per step. These operations
between integer-valued indices can be omitted from the analysis, given that
computational complexity is primarily driven by floating-point operations. At
each step, the complexity of TraceSortedProb is dominated by the process of
finding the lowest penalty among $|\mathcal{C}_{\bar{\mathcal{L}}}|$ penalties
associated with the $|\mathcal{C}_{\bar{\mathcal{L}}}|$ corners of
$\mathcal{C}_{\bar{\mathcal{L}}}$, as described by (24) and depicted in Fig.
4. Let the $|\mathcal{C}_{\bar{\mathcal{L}}}|$ penalties be stored in the form
of a linked list data structure, the elements of which are organized in
ascending order. Therefore, the first element of the list always corresponds
to the lowest penalty. With the aid of Fig. 4, one can observe that, at east
step, a new coordinate pair – on average – is inserted in
$\mathcal{C}_{\bar{\mathcal{L}}}$ and the corresponding penalty is computed
and inserted in the list. Identification of the position in the sorted linked
list where the new penalty value should be inserted requires
$O(\log|\mathcal{C}_{\bar{\mathcal{L}}}|)$ comparisons. The lowest penalty
value is subsequently removed from the linked list and the corresponding
corner in $\mathcal{C}_{\bar{\mathcal{L}}}$ is moved to
$\mathcal{C}_{\mathcal{L}}$. After $(L_{0}+1)(L_{1}+1)$ steps, when all
entries of matrix $\mathbf{\Phi}$ have been considered, TraceSortedProb has
computed and inserted $(L_{0}+1)(L_{1}+1)$ penalty values in the linked list,
raising the total number of additions to $(L_{0}+1)(L_{1}+1)+L_{0}+L_{1}$ and
the total number of comparisons to
$O((L_{0}+1)(L_{1}+1)\log|\mathcal{C}_{\bar{\mathcal{L}}}|)$. As can be
inferred from (23), the structure of $\mathcal{L}$ ensures that the
cardinality of $\mathcal{C}_{\bar{\mathcal{L}}}$ cannot be greater than
$\min(L_{0}+1,L_{1}+1)$, that is,
$|\mathcal{C}_{\bar{\mathcal{L}}}|\leq\min(L_{0}+1,L_{1}+1)$. The number of
comparisons performed by TraceSortedProb is thus
$O((L_{0}+1)(L_{1}+1)\log\min(L_{0}+1,L_{1}+1))$.

In short, we established that both CalcProbAndSolve and TraceSortedProb carry
out $(L_{0}+1)(L_{1}+1)+L_{0}+L_{1}$ additions. If we set
$n=(L_{0}+1)(L_{1}+1)$ and $L_{0}=L_{1}$ to simplify expressions,
CalcProbAndSolve and TraceSortedProb perform $O(n\log n)$ and
$O(n\log(\sqrt{n}-1))$ comparisons, respectively. If we take into account that
$n\log(\sqrt{n}-1)<\tfrac{n}{2}\log n$, we conclude that the worst-case number
of comparisons in both procedures is $O(n\log n)$.

Although both procedures have computational complexities of the same order,
the quick convergence of GRAND-based methods to optimal solutions [6] gives
TraceSortedProb an edge on CalcProbAndSolve. The error vector that is selected
to be a column of matrix $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ is found
among error vectors that have been born out of the first few elements of the
output sequence of coordinate pairs. Assume that transversal GRAND introduces
a threshold $\ell_{\mathrm{th}}$, which limits the number of coordinate pairs
that are considered. CalcProbAndSolve still has to sort the
$(L_{0}+1)(L_{1}+1)$ entries of matrix $\mathbf{\Phi}$ and then output the
coordinates of only the $\ell_{\mathrm{th}}$ smallest entries. Therefore, the
complexity of CalcProbAndSolve remains constant and independent of
$\ell_{\mathrm{th}}$. In contrast, TraceSortedProb will generate the sequence
of $\ell_{\mathrm{th}}$ coordinate pairs after the first $\ell_{\mathrm{th}}$
steps and will then terminate execution, thus ignoring the remaining
$(L_{0}+1)(L_{1}+1)-\ell_{\mathrm{th}}$ entries of matrix $\mathbf{\Phi}$.
This means that the product $(L_{0}+1)(L_{1}+1)$ can be replaced by
$\ell_{\mathrm{th}}$ in the complexity expressions derived in this section. A
summary of the total number of operations performed by CalcProbAndSolve and
TraceSortedProb for the evaluation of a single column of
$\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ is provided
in Table I. Note that for $n=(L_{0}+1)(L_{1}+1)$ and $L_{0}=L_{1}$, the number
of additions carried out by TraceSortedProb reduces from $O(n)$ to
$O(\sqrt{n})$, while the worst-case number of comparisons drops from $O(n\log
n)$ to $O(\log n)$, provided that $\ell_{\mathrm{th}}$ is independent of $n$.

TABLE I: Number of operations involved in two competing procedures for the
evaluation
of a single column of the $L\times B$ matrix $\hat{\mathbf{E}}_{\mkern 1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$, where $L=L_{0}+L_{1}$. Operations | CalcProbAndSort | TraceSortedProb
---|---|---
Additions | $(L_{0}+1)(L_{1}+1)+L_{0}+L_{1}$ |  $\ell_{\mathrm{th}}+L_{0}+L_{1}$ for $1\leq\ell_{\mathrm{th}}\leq(L_{0}+1)(L_{1}+1)$
Worst-case number of comparisons |  $O(n\log n)$ for $n=(L_{0}+1)(L_{1}+1)$ |  $O(\ell_{\mathrm{th}}\log\min(L_{0}+1,L_{1}+1))$ for $1\leq\ell_{\mathrm{th}}\leq(L_{0}+1)(L_{1}+1)$

##  VII Results and Discussion

In this section, the bit error probability, $\varepsilon$, and the average
length of an error burst, $\Lambda$, are used as the channel parameters. For
this reason, the transition probabilities, $p_{10}$ and $p_{01}$, have been
expressed in terms of $\varepsilon$ and $\Lambda$ based on the definitions in
Section IV-A, i.e., $p_{10}=1/\Lambda$ and
$p_{01}=\varepsilon/\left[\Lambda\left(1-\varepsilon\right)\right]$. Recall
that if a destination node receives $L=N-N_{\mathrm{R}}$ erroneous coded
packets of $B$ bits, transversal GRAND attempts to repair them by estimating
the $L\times B$ matrix $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ column by
column. Estimation of a column of $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ relies on
the entries of the previous column. If the previous column contains $L_{0}$
zeros and $L_{1}$ ones, where $L_{0}+L_{1}=L$, transversal GRAND classifies
all $2^{L}$ possible vectors that are candidates for the next column of
$\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ into
$(L_{0}+1)(L_{1}+1)$ groups according to their probability of occurrence, as
explained in Section IV-B. The TraceSortedProb procedure, introduced in
Section VI, provides transversal GRAND with the option to identify only the
$\ell_{\mathrm{th}}$ groups that are most likely to occur, instead of all
$(L_{0}+1)(L_{1}+1)$ groups, thus reducing computational complexity without
necessarily degrading the estimation accuracy of the algorithm.

The objective of this section is to compare the performance of stand-alone RLC
decoding, RLC decoding combined with syndrome decoding (RLC with SD) and RLC
decoding combined with transversal GRAND (RLC with T-GRAND) in terms of their
decoding probability, that is, the probability of a destination node
recovering the $K$ source packets when $N$ coded packets have been
transmitted. Measurements of the decoding probability, obtained through
simulations for $K=10$ and $N$ varying from $10$ to $20$, are presented in
Fig. 5, Fig. 6 and Fig. 7. As can be observed in all three figures, setting
$\ell_{\mathrm{th}}=8$ in order to constrain the number of vectors that
T-GRAND queries, has a negligible impact on the decoding probability of RLC
with T-GRAND.

Figure 5: Comparison of the decoding probabilities of RLC decoding (RLC), RLC
decoding combined with syndrome decoding (RLC with SD) and RLC decoding
combined with transversal GRAND (RLC with T-GRAND) for $K=10$ source packets,
$N$ transmitted coded packets, where $N=10,\ldots,20$, bit error probability
$\varepsilon\in\\{0.01,0.03,0.05\\}$, average length of error bursts
$\Lambda=4$ and packet length $B=64$. Figure 6: Comparison of the decoding
probabilities of RLC decoding (RLC), RLC decoding combined with syndrome
decoding (RLC with SD) and RLC decoding combined with transversal GRAND (RLC
with T-GRAND) for $K=10$ source packets, $N$ transmitted coded packets, where
$N=10,\ldots,20$, bit error probability $\varepsilon=0.03$, average length of
error bursts $\Lambda\in\\{3,5,7\\}$ and packet length $B=64$.

Fig. 5 shows measurements for an increasing probability of the channel
flipping bits in transmitted packets, when each packet contains $B=64$ bits
and errors occur in bursts of length $\Lambda=4$ on average. For
$\varepsilon=0.01$ and a growing number of transmitted packets, the
destination node is likely to receive $K$ error-free linearly independent
packets among the received packets and recover the $K$ source packets using
RLC decoding; SD and T-GRAND offer only a marginal improvement in decoding
probability. If the value of $\varepsilon$ is raised to $0.05$, the proportion
of erroneously received packets increases, the RLC decoder experiences a
notable drop in decoding performance, and SD and T-GRAND become instrumental
in improving the chances of recovering the source packets. For example, when
$\varepsilon=0.05$ and $N=20$, SD increases the decoding probability of RLC
from $0.18$ to $0.56$ whereas T-GRAND, which considers correlations in errors
when repairing coded packets, boosts the decoding probability to $0.82$.

Fig. 6 depicts the impact of the average length of error bursts on the
decoding probability, when $\varepsilon=0.03$. When the value of $\varepsilon$
is constant, the same number of errors – on average – impair the transmitted
packets, but errors aggregate in fewer packets as the average length of error
bursts increases. Consequently, destination nodes receive an increasingly
larger proportion of error-free packets as $\Lambda$ grows, and RLC decoding
stands a greater chance of success. Although fewer packets are received in
error for higher values of $\Lambda$, erroneous packets are more severely
damaged by longer error bursts. Nevertheless, SD and especially T-GRAND can
still improve the decoding probability of RLC. For example, the decoding
probability of RLC, RLC with SD and RLC with T-GRAND is $0.72$, $0.79$ and
$0.85$, respectively, for $\Lambda=7$ and $N=16$. On the other hand, low
values of $\Lambda$ have a negative impact on RLC decoding; for a decreasing
length of error bursts and a fixed average number of errors, the proportion of
correctly received packets reduces. Packets corrupted by errors may dominate
but errors are more sparsely distributed, and both SD and T-GRAND are more
effective in repairing corrupted packets. Notice in Fig. 6 that the decoding
probability of RLC, RLC with SD and RLC with T-GRAND is $0.41$, $0.81$ and
$0.91$, respectively, for $\Lambda=3$ and $N=20$.

The effect of the packet length $B$ on the decoding probability is shown in
Fig. 7. For fixed values of $\varepsilon$ and $\Lambda$, the likelihood that a
packet will be corrupted by errors increases with the packet length and, thus,
the performance of RLC decoding deteriorates. When it comes to SD and T-GRAND,
the value of $B$ also signifies the number of times that the algorithms have
run in order to estimate the errors in the $B$ positions of the corrupted
packets. The advantage of T-GRAND over SD becomes apparent as the packet
length increases. For $B=96$ and $N=20$, SD lifts the decoding probability of
RLC from $0.08$ to $0.62$; T-GRAND further increases the decoding probability
to $0.82$ as is more successful than SD in making consecutive accurate guesses
of error occurrences in the course of the $B=96$ runs.

The results presented in this section considered transmission over burst error
channels and demonstrated the increase in the probability of an RLC decoder
recovering the original source packets, when it is assisted by SD or T-GRAND.
If $L$ coded packets are received in error, both SD and T-GRAND attempt to
repair them by estimating the $L\times B$ matrix $\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$. SD does not
leverage correlations in errors, thus estimation of a column of
$\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ does not
depend on previous columns. This fact makes SD highly parallelizable but
suboptimal in terms of decoding probability. On the other hand, T-GRAND
exploits correlations in errors, hence estimation of each column of
$\hat{\mathbf{E}}_{\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{R}\mkern-1.5mu}\mkern 1.5mu}$ relies on
knowledge of the previous column. Therefore, T-GRAND is a sequential algorithm
that improves on the decoding probability achieved by RLC decoding combined
with SD. We note that RLC, RLC with SD and RLC with T-GRAND should not
necessarily be seen as competing decoding methods, as they could coexist and
offer different delay-reliability trade-offs, depending on the requirements of
an application. For instance, RLC or RLC with SD could be used when streaming
a movie in real-time, and RLC with T-GRAND could be used to further improve
the quality of a downloaded movie for offline viewing.

Figure 7: Comparison of the decoding probabilities of RLC decoding (RLC), RLC
decoding combined with syndrome decoding (RLC with SD) and RLC decoding
combined with transversal GRAND (RLC with T-GRAND) for $K=10$ source packets,
$N$ transmitted coded packets, where $N=10,\ldots,20$, bit error probability
$\varepsilon=0.03$, average length of error bursts $\Lambda=3$ and packet
length $B\in\\{16,32,96\\}$.

##  VIII Conclusions and Future Work

In this paper, we built on the ‘guessing random additive noise decoding’
(GRAND) concept and developed transversal GRAND, a hard detection decoder that
leverages correlations between channel errors and works in tandem with the
decoder of a random linear code (RLC) at layers higher than the physical
layer. Transversal GRAND generates and queries error vectors in order of
likelihood, and attempts to correct bits that occupy the same position in
erroneously received packets. After all bit positions have been considered,
RLC decoding utilizes both repaired and correctly received packets to recover
the original information packets. Calculation and sorting of the likelihood
values of all error vectors for each bit position is a simple but
computationally expensive procedure. For this reason, we also presented a
computationally efficient method, which identifies the most likely error
vectors without computing their likelihoods and then ordering them. Simulation
results demonstrated that transversal GRAND has the potential to markedly
improve the performance of RLC decoding when the communication channel
introduces error bursts in transmitted packets.

Future plans include the extension of transversal GRAND for binary RLCs to
non-binary RLCs or, equivalently, RLCs over
$\mathbb{F}_{2^{q}}=\\{0,1,\ldots,2^{q}-1\\}$ for $q\geq 1$. This would
involve the replacement of the binary Gilbert-Elliott channel model by a non-
binary model, e.g., [26], and the derivation of a multidimensional function
that describes the probability of occurrence of each error vector, instead of
the two-dimensional function given in (12). The procedure for identifying the
most likely error vectors would then have to be configured to trace a path of
ordered negative log-probability values, not in a two-dimensional matrix as in
Fig. 4, but in a multidimensional matrix. The generalization of transversal
GRAND for RLCs over $\mathbb{F}_{2^{q}}$ will allow comparison of its
performance with that of other non-binary schemes, e.g., PRAC [3]. Note that
decoding schemes for non-binary RLCs are often designed for large fields,
i.e., large values of $q$, as they rely on the assumption that any $K$ of the
received coded packets are linearly independent, if $K$ source packets have
been encoded. This assumption simplifies decoding but does not hold when small
fields are considered, e.g., $\mathbb{F}_{2}$ as in this paper.

## Acknowledgments

Dmitry Savostyanov acknowledges the support of the Leverhulme Trust Fellowship
programme (RF-2021-258).

## References

  * [1] I. Chatzigeorgiou, “Transversal GRAND for network coded data,” in _Proc. IEEE Int. Symp. on Inf. Theory (ISIT)_ , Espoo, Finland, Jun. 2022\.
  * [2] T. Ho, M. Médard, R. Koetter, D. R. Karger, M. Effros, J. Shi, and B. Leong, “A random linear network coding approach to multicast,” _IEEE Trans. Inf. Theory_ , vol. 52, no. 10, pp. 4413–4430, Oct. 2006.
  * [3] G. Angelopoulos, A. P. Chandrakasan, and M. Médard, “PRAC: Exploiting partial packets without cross-layer or feedback information,” in _Proc. IEEE Int. Conf. on Commun. (ICC)_ , Sydney, Australia, Jun. 2014.
  * [4] M. S. Mohammadi, Q. Zhang, and E. Dutkiewicz, “Reading damaged scripts: Partial packet recovery based on compressive sensing for efficient random linear coded transmission,” _IEEE Trans. Commun._ , vol. 64, no. 8, pp. 3296–3310, Aug. 2016.
  * [5] K. R. Duffy, J. Li, and M. Médard, “Guessing noise, not code-words,” in _Proc. IEEE Int. Symp. on Inf. Theory (ISIT)_ , Vail, CO, USA, Jun. 2018.
  * [6] ——, “Capacity-achieving guessing random additive noise decoding,” _IEEE Trans. Inf. Theory_ , vol. 65, no. 7, pp. 4023–4040, Jul. 2019.
  * [7] A. Cohen, R. G. L. D’Oliveira, K. R. Duffy, J. Woo, and M. Médard, “AES as error correction: Cryptosystems for reliable communication,” Sep. 2022. [Online]. Available: https://arxiv.org/pdf/2203.12047
  * [8] K. Galligan, A. Solomon, A. Riaz, M. Médard, R. T. Yazicigil, and K. R. Duffy, “IGRAND: Decode any product code,” in _Proc. IEEE Global Commun. Conf. (GLOBECOM)_ , Madrid, Spain, Dec. 2021.
  * [9] K. R. Duffy, “Ordered reliability bits guessing random additive noise decoding,” in _Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP)_ , Toronto, Canada, Jun. 2021.
  * [10] C. Condo, “Iterative soft-input soft-output decoding with ordered reliability bits GRAND,” Jul. 2022. [Online]. Available: https://arxiv.org/abs/2207.06691
  * [11] W. An, M. Médard, and K. R. Duffy, “Keep the bursts and ditch the interleavers,” _IEEE Trans. Commun._ , vol. 70, no. 6, pp. 3655–3667, Jun. 2022.
  * [12] I. Chatzigeorgiou and F. A. Monteiro, “Symbol-level GRAND for high-order modulation over flat fading channels,” Jul. 2022. [Online]. Available: https://arxiv.org/abs/2207.07748
  * [13] S. M. Abbas, M. Jalaleddine, and W. J. Gross, “GRAND for Rayleigh fading channels,” Apr. 2022. [Online]. Available: https://arxiv.org/abs/2205.00030
  * [14] H. Sarieddeen, M. Médard, and K. R. Duffy, “GRAND for fading channels using pseudo-soft information,” in _Proc. IEEE Global Commun. Conf. (GLOBECOM)_ , Rio de Janeiro, Brazil, Dec. 2022.
  * [15] S. M. Abbas, T. Tonnellier, F. Ercan, M. Jalaleddine, and W. J. Gross, “High-throughput and energy-efficient VLSI architecture for ordered reliability bits GRAND,” _IEEE Trans. VLSI Syst._ , vol. 30, no. 6, pp. 681–693, Jun. 2022.
  * [16] J. Jin, B. Li, and T. Kong, “Is random network coding helpful in WiMAX?” in _Proc. IEEE 27th Conf. on Comp. Commun. (INFOCOM)_ , Phoenix, AZ, USA, Apr. 2008.
  * [17] D. L. Donoho, “Sparse components of images and optimal atomic decompositions,” _Constr. Approx._ , vol. 17, no. 1, pp. 353–382, Jan. 2001\.
  * [18] E. N. Gilbert, “Capacity of a burst-noise channel,” _Bell Syst. Tech. J._ , vol. 39, no. 5, pp. 1253–1266, Sep. 1960.
  * [19] E. O. Elliott, “Estimates of error rates for codes on burst-noise channels,” _Bell Syst. Tech. J._ , vol. 42, no. 5, pp. 1977–1997, Sep. 1963.
  * [20] N. Aboutorab, P. Sadeghi, and S. Sorour, “Enabling a tradeoff between completion time and decoding delay in instantly decodable network coded systems,” _IEEE Trans. Commun._ , vol. 62, no. 4, pp. 1296–1309, Apr. 2014\.
  * [21] R. D. Cideciyan, S. Furrer, and M. A. Lantz, “Performance of interleaved block codes with burst errors,” _IEEE Trans. Magn._ , vol. 55, no. 3, pp. 1–5, Mar. 2019.
  * [22] T. Rancurel, D. Roviras, and F. Castanié, “Expression of the capacity for the Gilbert channel in presence of interleaving,” in _Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP)_ , Salt Lake City, USA, May 2001.
  * [23] J. Cloud and M. Médard, “Network coding over SATCOM: Lessons learned,” in _Proc. Int. Conf. on Wireless and Satellite Systems (WiSATS)_ , Bradford, UK, Jul. 2015.
  * [24] M. Mushkin and I. Bar-David, “Capacity and coding for the gilbert-elliott channels,” _IEEE Trans. Inf. Theory_ , vol. 35, no. 6, pp. 1277–1290, Nov. 1989.
  * [25] J. W. J. Williams, “Algorithm 232 – Heapsort,” _Communications of the ACM_ , vol. 7, no. 6, pp. 347–348, Jun. 1964.
  * [26] W. Griffiths, H.-J. Zepernick, and M. Caldera, “APP decoding of non-binary block codes on Gilbert-Elliott channels using generalized weight polynomials,” in _Proc. IEEE Int. Symp. on Inf. Theory and its App. (ISITA)_ , Auckland, New Zealand, Dec. 2008.