1 Introduction↩︎

Shannon’s pioneering work demonstrated that increasing the code length allows for constructions with progressively stronger error-correction capability [1]. However, since maximum likelihood decoding (MLD) of linear block codes is NP-hard, the associated computational burden typically grows rapidly with block length [2]. As wireless communications, optical communications, and high-speed serializer/deserializer (SerDes) links continue to evolve toward higher reliability, lower latency, and higher throughput [3]–[5], efficient short-blocklength channel decoding has become a common key problem across modern communication and information-processing systems [6], [7]. A central challenge is to design decoding strategies that approach MLD performance while maintaining manageable decoding complexity.

Guessing Random Additive Noise Decoding (GRAND) has recently emerged as a universal decoding framework [8]. Instead of searching over the codeword space, GRAND performs decoding in the noise domain by sequentially generating candidate error patterns (EPs) and subtracting them from the received sequence until a valid codeword is identified. With an appropriate ordering of EPs, GRAND can achieve MLD for both hard-output channels such as the binary symmetric channel (BSC) and binary erasure channel (BEC) [8], [9] and soft-output channels such as the additive white Gaussian noise (AWGN) channel [10]. Since the decoding procedure depends only on channel noise statistics, GRAND can operate with arbitrary linear block codes without code-specific decoder design.

To adapt the GRAND framework to different channels and system requirements, a number of variants have been proposed [10]–[15], along with several methods aimed at improving decoding performance and reducing complexity [16], [17]. For soft-output channels, Soft GRAND (SGRAND) generates EPs according to their likelihood using the exact magnitudes of log-likelihood ratios (LLRs), and is equivalent to MLD when the search over EPs is exhaustive [10], [18]. However, generating EPs according to precise LLR magnitudes requires dynamic scheduling of candidate EPs, leading to substantial computational overhead and complicating hardware implementations [19]. In contrast, Ordered Reliability Bits GRAND (ORBGRAND) schedules EPs using only the ranking of LLR magnitudes [20]. Once the reliability ranking is obtained, EPs can be generated according to a fixed structure independent of the exact LLR magnitudes [21]–[25].

ORBGRAND provides an attractive trade-off between decoding performance and implementation complexity by generating EPs based solely on the reliability ranking of LLR magnitudes rather than their exact values. This ranking-based structure enables efficient parallel implementations while maintaining competitive decoding performance. Motivated by this property, several works have proposed improved EP ordering strategies that preserve the reliance on reliability ranking, including heuristic ordering rules [16], [20], [26], empirical rearrangement approaches [27], and search-based optimization methods [28]. We collectively refer to this class of decoding strategies as ORB-type GRAND, whose formal definition will be given later.

From an information-theoretic perspective, ORBGRAND and certain variants have been shown to be capacity-achieving or nearly capacity-achieving [29]–[31], and finite-blocklength analysis [32] further provides achievable-rate expansions and dispersion-based normal approximations. These results characterize reliable transmission through rate-oriented asymptotic analyses, but they do not directly quantify operational list-size-one block error rate (BLER) under a fixed EP test budget. At such finite block lengths, ORB-type GRAND nonetheless exhibits a noticeable BLER gap from MLD, particularly at high signal-to-noise ratios (SNRs).

These observations motivate a closer examination of EP ordering in ORB-type GRAND under finite test budgets. The ordered EP sequence determines which EPs are tested before the decoder terminates, so the resulting BLER is governed jointly by the testing order and the codebook. Existing ordering rules are mostly heuristic, empirical, or based on idealized search criteria, while a systematic BLER analysis from the perspective of EP ordering is still lacking.

Existing analytical results mainly focus on list-GRAND decoding and its extensions to soft-output decoding [33]–[35]. These approaches often approximate the occurrences of competing codewords along the guessing order by geometric distributions, yielding tractable performance predictions that are empirically accurate for random code ensembles. However, for structured linear block codes in the practically relevant list-size-one case—i.e., standard GRAND that terminates upon identifying the first valid codeword—competing-codeword events are strongly code-dependent and are no longer well captured by such geometric approximations; consequently, these predictions become unreliable [36]. This limitation is particularly relevant to ORB-type GRAND, whose performance is governed by a fixed EP ordering.

For the EP-ordering aspect specifically, ReShuffled-ORBGRAND (RS-ORBGRAND) was proposed in [28]. That work studied an idealized search problem in which decoding succeeds once the target EP is queried, thereby isolating the effect of EP ordering on locating the target while excluding target preemption. Thus, although it provides useful insight into ordering candidate EPs, it does not explain how code structure affects target preemption. A systematic BLER analysis of ORB-type GRAND under finite test budgets is therefore still needed.

This paper develops an average guessing posterior (AGP)-based theoretical framework for analyzing ORB-type GRAND and establishing EP-ordering principles. The main contributions are summarized as follows.

• We formalize ORB-type GRAND as the class of GRAND algorithms whose testing order depends only on reliability ranking. We then introduce the AGP, which quantifies EP effectiveness, is independent of any particular LLR realization, and characterizes ORB-type decoding behavior.

• For random code ensembles, we derive exact expressions for the BLER, decoding success probability, stopping-time distribution, and average number of tests under a fixed test budget. The analysis separates target-miss and target-preemption errors, and proves that ordering EPs by non-increasing AGP simultaneously minimizes the average BLER and the average number of tests over the EP set under consideration.

• We extend the BLER analysis to fixed linear block codes. The resulting exact expression isolates the code-dependent target-preemption term, which is characterized through higher-order weight relationships of codeword tuples. It also supports efficient finite-order low-BLER evaluation and yields a simple first-order upper bound.

• Guided by these insights, we formulate RS-ORBGRAND as an AGP-driven offline scheme that preserves the ranking-based ORB-type structure. Compared with the idealized search setting in [28], the present design is supported by a BLER analysis that accounts for competing codewords; simulations for Bose–Chaudhuri–Hocquenghem (BCH)\((127,113)\) show consistent gains and performance within \(0.1\) dB of the MLD lower-bound benchmark down to BLERs of \(10^{-6}\).

The remaining part of this paper is organized as follows. Section 2 introduces the channel model and formally defines ORB-type GRAND. Section 3 analyzes ORB-type GRAND under random code ensembles and derives the decoding success probability, the average number of tests, and the AGP-based optimal ordering rule. Section 4 extends the analysis to fixed linear block codes, establishes the BLER expression, and studies AGP-ordered EP sequences in this fixed-code setting. Section 5 validates the analytical results and evaluates the proposed RS-ORBGRAND. Finally, Section 6 concludes the paper.

2 ORB-Type GRAND Algorithms↩︎

In this section, we establish the analytical framework for the rest of the paper. We begin with the channel model and the posterior quantities associated with EPs, then introduce the GRAND decoding principle and the formal definition of ORB-type GRAND, and finally present RS-ORBGRAND as a practical scheme motivated by this framework. These preliminaries will serve as the foundation for our analysis developed in subsequent sections.

2.1 Channel Model↩︎

We use uppercase letters (e.g., \(W\)) to represent random variables and their corresponding lowercase letters (e.g., \(w\)) to represent their realizations. We append an underscore to a letter to represent a vector (e.g., \(\underline{w}\)), whose length is equal to the code length unless otherwise noted. For a sequence of vectors, we use parenthesis, such as \(\underline{w}(i)\), to represent the ordinal, and for a vector \(\underline{w}\), we use \(w_i\) to represent its \(i\)-th component. For a continuous random variable, we use lowercase \(p\) to represent its probability density function (e.g., \(p_{Y}(y)\)); for a discrete random variable, we use \(P\) to represent its probability mass function, which characterizes the probability distribution that the random variable satisfies (e.g., \(P_{W|Y}(w \mid y)\)); for a random event, we use \(\Pr(\cdot)\) to represent its probability of occurrence. Depending on the context, we may also use certain specific symbols for some frequently used events or probabilities.

We consider a general block code of rate \(R = K/N\), which consists of \(M = 2^K\) different binary codewords \(\{\underline{w}(m)\}_{m = 1, 2, \ldots, M}\), each of a length \(N\), thus forming a codebook \(\mathcal{C} = \{\underline{w}(1),\ldots,\underline{w}(M)\}\). We let \(\underline{W}\) represent a codeword drawn uniformly at random from the codebook. At the receiving end, the channel output vector is \(\underline{Y}\), which is assumed to possess a probability density function over \(\mathbb{R}^N\) for concreteness. We adopt a memoryless channel model, and let the output probability density distribution be \(q_0(y)\) under input \(w = 0\) and \(q_1(y)\) under input \(w = 1\), respectively. We call a channel output-symmetric if \[\begin{align} \label{eqn:output-symmetric-channel} q_0(y) = q_1(-y) \end{align}\tag{1}\] holds for any \(y \in \mathbb{R}\); for example, the commonly considered AWGN channel is output-symmetric.

After receiving \(\underline{Y}\), the LLR vector \(\underline{L}\) is determined as follows: \[\label{eq:def95ell} L_i = {\log\frac{p_{Y|W}(Y_i \mid W_i = 0)}{p_{Y|W}(Y_i \mid W_i = 1)}} = \log\frac{q_0(Y_i)}{q_1(Y_i)},\tag{2}\] for \(i = 1, \ldots, N\), and subsequently we use \(\ell_{i}\) to represent the realization of \(L_i\). Based on \(\underline{L}\), the hard decision vector, \(\theta(\underline{Y})\), is given by \(\theta(Y_i) = (1 - \operatorname{sgn}(L_i))/2\). Equivalently, \(\theta(Y_i)=\mathbf{1}(L_i < 0)\), i.e., \(\theta(Y_i)=0\) if \(L_i\ge 0\) and \(1\) otherwise.

For an output-symmetric channel, we have the following useful properties:

• If \(P_W(W=0) = P_W(W=1) = 1/2\), then \(p_Y(y) = p_Y(-y)\), because \[\label{eqn:prop95symm951} p_Y(y) = \frac{1}{2}(p_{Y|W}(y \mid 0) + p_{Y|W}(y \mid 1)) \overset{\eqref{eqn:output-symmetric-channel}}{=} \frac{1}{2}(p_{Y|W}(-y \mid 1) + p_{Y|W}(-y \mid 0)) = p_Y(-y).\tag{3}\]

• If the LLR of \(y\) calculated by 2 is \(\ell\), then the LLR corresponding to \(-y\) is \(-\ell\), because \[\label{eqn:prop95symm952} \ell = \log\frac{p_{Y|W}(y \mid 0)}{p_{Y|W}(y \mid 1)} \Rightarrow \log\frac{p_{Y|W}(-y \mid 0)}{p_{Y|W}(-y \mid 1)} = \log\frac{p_{Y|W}(y \mid 1)}{p_{Y|W}(y \mid 0)} = -\log\frac{p_{Y|W}(y \mid 0)}{p_{Y|W}(y \mid 1)} = -\ell.\tag{4}\]

2.2 Average Guessing Posterior↩︎

Throughout the paper, we assume that for each \(i = 1, \ldots, N\), \(W_i\) is uniform over \(\mathbb{F}_2\). The codebook ensembles studied in the paper satisfy this assumption.

To study EP ordering in noise-guessing decoding, we introduce a key metric that quantifies the effectiveness of an EP. For a received vector \(\underline{y}\) and a candidate EP \(\underline{e}\) which is a vector in \(\mathbb{F}_2^N\), the vector \(\theta(\underline{y})\oplus \underline{e}\) represents the codeword candidate obtained by flipping the hard decision according to \(\underline{e}\). A natural quantity associated with \(\underline{e}\) is therefore the posterior probability that this codeword candidate is indeed the transmitted codeword, referred to as the guessing posterior. Its expectation over the channel output, termed the average guessing posterior (AGP), will serve as the central quantity for characterizing EP ordering and decoding performance in the sequel.

It is clear that the hard decision vector may not coincide with the sent codeword; that is, \(\theta(Y_i) = W_i\) may not hold for some indices in \(\{1, 2, \ldots, N\}\). Regarding this fact, we have the following lemma.

When studying GRAND, we will frequently consider testing whether the modulo-two sum of the hard decision vector \(\theta(\underline{Y})\) and a binary vector \(\underline{e}\) is a codeword, where \(\underline{e}\) is usually interpreted as an EP. For any given \(\underline{y}\), we call \(P_{\underline{W}|\underline{Y}}(\theta(\underline{y})\oplus \underline{e} \mid \underline{y})\) the guessing posterior, which will be seen to play a pivotal role in decoding.

We first consider an idealized setting in which the components of \(\underline{W}\) are i.i.d. In this case, the guessing posterior admits a simple product form that reveals its basic channel-dependent structure.

For an actual codebook \(\mathcal{C}\), however, the i.i.d. condition in Lemma 2 no longer holds. The following result shows that the guessing posterior still admits a similar factorized form, up to a codebook constraint and a normalization coefficient.

When considering the random channel output vector \(\underline{Y}\) induced by a codebook \(\mathcal{C}\), the guessing posterior \(P_{\underline{W}|\underline{Y}}\left(\theta(\underline{Y}) \oplus \underline{e} \mid \underline{Y}\right)\) is itself a random variable. Its expectation is called the AGP. The following proposition shows that, although the instantaneous guessing posterior depends on the codebook \(\mathcal{C}\), this dependence disappears after averaging over the channel output when the channel is output-symmetric in the sense of 1 .

As will be shown in the sequel, the metric of AGP provides the appropriate lens for characterizing the ordering behavior of ORB-type GRAND and for establishing principled EP-ordering rules.

2.3 GRAND↩︎

A GRAND algorithm mainly consists of two components: an EP generator and a codeword tester. An EP generator takes the LLR vector \(\underline{\ell}\) as input, and sequentially outputs a series of vectors in \(\mathbb{F}_2^N\) called EPs. Denote the \(t\)-th EP as \(\underline{e}(t)\), \(1 \leq t \leq T \leq 2^N\), where \(T\) is the maximum number of tests the GRAND algorithm is permitted to conduct.² A codeword tester sequentially tests whether \(\theta(\underline{y}) \oplus \underline{e}(t) \in \mathcal{C}\) for \(t=1,\ldots,T\). It is clear that there are two possibilities:

• There exists at least one index within \(\{1, 2, \ldots, T\}\) such that the corresponding EP passes the test of codeword tester, and we denote the smallest such index as \(\hat{t}\) and declare the decoded codeword to be \(\hat{\underline{w}} = \theta(\underline{y}) \oplus \underline{e}(\hat{t})\);

• There is no index within \(\{1, 2, \ldots, T\}\) such that the corresponding EP passes the test of codeword tester, and we declare a decoding failure with \(\hat{\underline{w}} = \emptyset\).

For the sent codeword \(\underline{w}\), the EP that can lead to successful decoding is \[\label{eqn:target-error-pattern} \underline{e}^{*} = \theta(\underline{y}) \oplus \underline{w},\tag{13}\] which we call the target EP. Relative to the position of this target EP in the tested sequence, decoding errors can be decomposed into the following two types:

• Type I error (target-miss error): \(\underline{e}^{*} \notin \{\underline{e}(t)\}_{t=1}^{T}\). In this case, the correct codeword cannot be reached within the test budget; the decoder may either stop at a competing codeword or declare a decoding failure.

• Type II error (target-preemption error): \(\underline{e}^{*} \in \{\underline{e}(t)\}_{t=1}^{T}\), but an EP \(\underline{e}(\hat{t})\) satisfying \(\theta(\underline{y})\oplus\underline{e}(\hat{t})\in\mathcal{C}\) is encountered before \(\underline{e}^{*}\), so the decoder stops before reaching the target.

The following proposition revisits a known result (see, e.g., [10], [18], [29]) regarding the optimal GRAND, which is in fact equivalent to MLD if \(T = 2^N\).

The SGRAND algorithm [10] implements the optimal EP generator in Proposition 2. Since its soft weight depends upon the actual values of LLRs, it can only be implemented in an “on-the-fly” fashion, with its parallelization and hardware implementation still remaining at an exploratory stage [19]. More generally, many GRAND algorithms can be viewed as ordering EPs according to a weighted metric. Following [29], we introduce a generalized measure \[\zeta'(\underline{e}) =\sum_{i:e_i=1}\gamma_i(\underline{\ell},\underline{e}),\] where \(\gamma_i\) are nonnegative functions that may depend on both \(\underline{\ell}\) and \(\underline{e}\). We have the following unified description of many GRAND algorithms: \[\begin{align} \label{eq:gamma} \hat{\underline{w}} = \theta(\underline{y})\oplus \arg\min_{\underline{e}:\theta(\underline{y})\oplus \underline{e}\in \mathcal{C}}\sum_{i:e_i=1} \gamma_{i}(\underline{\ell},\underline{e}). \end{align}\tag{17}\] The flexibility of 17 comes from allowing \(\gamma_i\), \(i=1,\ldots,N\), to depend on \(\underline{\ell}\), on the candidate EP \(\underline{e}\), or on both. Table 1 gives a compact overview of representative GRAND variants under this formulation, and also indicates which of them admit a pre-defined, ranking-based EP sequence. This distinction is important for the ORB-type class studied below.

In particular, when the metric depends only on the reliability ranking of the received symbols, the resulting decoder belongs to the class of ORB-type GRAND algorithms, which will be formally defined in the next subsection.

2.4 ORB-Type GRAND↩︎

While the optimal GRAND ordering relies on the exact LLR magnitudes \(|\ell_i|\), implementing such ordering may be computationally demanding. A natural idea is therefore to replace \(|\ell_i|\) with alternative measures \(\gamma_i\) (\(i=1,\ldots,N\)) that are easier to compute, especially measures determined only by the reliability ranking. In particular, ORBGRAND [20] has received attention due to its simplicity and effectiveness. To describe ORBGRAND, let \(\underline{r}\) denote the ranking vector of \(|\underline{\ell}|\), where \(r_i\) represents the position of \(|\ell_i|\) in the ascending order among the elements of \(|\underline{\ell}|\). For example, if \(|\underline{\ell}| = (1.2, 0.7, 0.4, 1.1, 0.3)\), then \(\underline{r} = (5, 3, 2, 4, 1)\). ORBGRAND simply sets \(\gamma_i = r_i\) in 17 . Intuitively, the idea is to approximate the exact value of \(|\ell_i|\) with its ranking \(r_i\) among \(|\underline{\ell}|\).

An alternative description of the ORBGRAND algorithm is as follows:

• For each \(\underline{e} \in \mathbb{F}_2^N\), calculate the ranking weight of \(\underline{e}\) as \(\sum_{i:e_i=1} i\), and arrange the elements of \(\mathbb{F}_2^N\) as an ordered list \(\mathcal{E}\) such that their ranking weights are monotonically non-decreasing (ties broken arbitrarily). If the maximum number of tests \(T\) is imposed, then truncate \(\mathcal{E}\) to include its first \(T\) elements only.

• For the received vector \(\underline{y}\) and thus its corresponding \(|\underline{\ell}|\), obtain the ranking \(\underline{r}\) which induces a permutation \(\pi_{\underline{y}}\) over \(\{1, 2, \ldots, N\}\). We refer to this mapping rule as the rank-based permutation.

• The EP generator outputs \(\underline{e}(t)\) sequentially, and the codeword tester checks whether \(\theta(\underline{y}) \oplus \pi_{\underline{y}}(\underline{e}(t)) \in \mathcal{C}\) for \(t=1,\ldots,T\).

We emphasize that the ordered EP list \(\mathcal{E}\) is an abstract representation of the EP ordering rather than a specific implementation. One possible implementation is to pre-generate and store \(\mathcal{E}\) offline, in which case the EP generator sequentially reads elements from \(\mathcal{E}\) and applies the permutation \(\pi_{\underline{y}}\) to obtain \(\{\pi_{\underline{y}}(\underline{e}(t))\}_{t=1,\ldots,T}\). Alternatively, as discussed in [20], the same ordered EP sequence can be generated on-the-fly using efficient search procedures that exploit the integer structure of the ranking weights (e.g., \(\sum_{i:e_i=1} i\)), without explicitly storing \(\mathcal{E}\). These implementations are algorithmically equivalent in that they produce the same ordered EP sequence.

In this paper, we use \(\mathcal{E}\) as an abstract notation for the ordered EP set, independent of any particular implementation. For convenience, we denote \[\pi_{\underline{y}}(\mathcal{E}) = \{\pi_{\underline{y}}(\underline{e}(1)),\ldots,\pi_{\underline{y}}(\underline{e}(T))\}.\]

To illustrate the difference between the ordering rules of SGRAND and ORBGRAND, we consider the following example.

Motivated by the observation in Example 1, several subsequent works have used more sophisticated, yet still ranking-based, choices of \(\gamma_i\) to better approximate \(|\ell_i|\) [16], [20], [25], [26], [28], [29]. As suggested in these works, algorithms whose ordering rule depends on the reliability ranking vector \(\underline{r}\) rather than the raw LLR vector \(\underline{\ell}\) are referred to as ORB-type GRAND algorithms. In this paper, we formalize this notion by slightly generalizing the description of ORBGRAND, as follows:

In the sequel, whenever probabilities or expectations are taken over the channel output, we usually abbreviate the random permutation \(\pi_{\underline{Y}}\) simply as \(\pi\) whenever no ambiguity arises. For a fixed received vector \(\underline{y}\), \(\pi_{\underline{y}}\) denotes the corresponding realization; in algorithmic descriptions, \(\pi\) denotes this realized permutation. Two representative examples of ORB-type GRAND are given below.

• If the receiver only has hard decision results \(\theta(\underline{y})\), we can set \(\pi\) to be an identical mapping, and generate \(\mathcal{E}\) according to the Hamming weight order. This is the original GRAND for hard decision channels [8].

• For a soft-output channel, the rank-based permutation used above maps the \(r_i\)-th component of an unpermuted EP to channel coordinate \(i\). Together with the ranking-weight ordered list \(\mathcal{E}\) described before Example 1, this specialization gives standard ORBGRAND [20]. The same permutation law can also be combined with other ordered lists \(\mathcal{E}\), which is the main degree of freedom behind general ORB-type designs [16], [29].

In Sections 3 and 4, we will study the performance of ORB-type GRAND algorithms for random code ensembles and fixed linear block codes, respectively.

2.5 Reshuffled ORBGRAND↩︎

A specific ORB-type GRAND algorithm, called ReShuffled-ORBGRAND (RS-ORBGRAND), has been proposed in [28]. The design is motivated by the observation in Proposition 2 that the optimal GRAND algorithm generates a non-increasing sequence of guessing posteriors (see also Remark 2). However, sorting the guessing posterior sequence requires “on-the-fly” generation of EPs and thus does not lead to an ORB-type GRAND algorithm.

To retain the ORB-type structure, RS-ORBGRAND arranges the EPs in \(\mathcal{E}\) such that their AGPs are non-increasing. In an ORB-type GRAND algorithm, the \(t\)-th tested EP is denoted by \(\pi(\underline{e}(t))\), and hence the corresponding AGP is given by \[\label{eq:orb95type95agp95def} p_t := \mathbf{E}_{\underline{Y}} \left[P_{\underline{W}|\underline{Y}}(\theta(\underline{Y})\oplus \pi(\underline{e}(t)) \mid \underline{Y})\right].\tag{18}\] Similar to Proposition 1, Proposition 3 further shows that \(p_t\) can be computed offline, thereby ensuring the practical feasibility of this design.

Practical constructions. The AGP-ordering principle can be implemented offline in different ways; these implementations should be distinguished from the theoretical ordering results proved later. We highlight two possible schemes.

• Scheme 1: AGP computation over a candidate list. Start from a finite ordered EP list \(\mathcal{E}\) generated by an existing ORB-type GRAND algorithm, compute the AGPs of its elements using Proposition 3 or Monte Carlo integration, reshuffle the list in non-increasing AGP order, and then keep the first \(T\) EPs. This scheme is directly tied to the AGP expression, but it requires evaluating \(p_t\) for the candidate EPs and depends on the quality of the initial candidate list.

• Scheme 2: empirical target-EP ordering. We repeatedly draw a transmitted codeword \(\underline{W}\) and generate the corresponding channel output \(\underline{Y}\) according to the channel. For each realization, we record the target EP before applying the rank-based permutation, \[\underline{E}_{\mathrm{tar}} = \pi_{\underline{Y}}^{-1}\!\left(\theta(\underline{Y})\oplus \underline{W}\right).\] Conditioned on \(\underline{Y}\), the event \(\underline{E}_{\mathrm{tar}}=\underline{e}\) is equivalent to \(\underline{W}=\theta(\underline{Y})\oplus\pi(\underline{e})\). Hence, by averaging over \(\underline{Y}\), the empirical frequency of each unpermuted EP estimates its AGP: \[\Pr(\underline{E}_{\mathrm{tar}}=\underline{e}) = \mathbf{E}_{\underline{Y}}\!\left[ P_{\underline{W}|\underline{Y}}\!\left( \theta(\underline{Y})\oplus \pi(\underline{e})\mid \underline{Y} \right)\right].\] This scheme avoids evaluating a closed-form expression for \(p_t\) and may be useful when such an expression is difficult to obtain.

In practice, one may generate an auxiliary list of size \(T_1>T\), compute the AGP of each EP in this list, sort the EPs in non-increasing AGP order, and then keep the first \(T\) EPs. Algorithm 3 records this offline finite-list construction. The sorting permutation \(\widetilde{\pi}\) is used only to construct the reshuffled list \(\widetilde{\mathcal{E}}\); online decoding then follows Algorithm 2 with this fixed list.

The subsequent sections analyze the AGP-based ordering rule used in the construction above. We first show that ordering EPs by non-increasing AGP is optimal for random code ensembles, in the sense that it simultaneously minimizes the ensemble-average decoding error probability and the ensemble-average number of tests over the EP set under consideration. For fixed linear block codes, the corresponding result is more limited but still useful: under an output-symmetric channel and the rank-based permutation, within any fixed \(T\)-element candidate EP set, some optimal ordering has a non-increasing AGP sequence \(\{p_t\}\). The choice of the candidate set itself is part of the practical construction; in RS-ORBGRAND, this is handled by the finite-list procedure in Algorithm 3.

3 Random Code Ensemble↩︎

In this section, we analyze ORB-type GRAND under the random code ensemble. This setting provides a clean baseline in which the effect of EP ordering can be isolated: the target-miss component is determined by the AGPs, while the target-preemption component has an ensemble-averaged form independent of any particular code structure. We first describe the random codebook model under consideration. We then study three key aspects of decoding performance:

1. block error rate (BLER) of ORB-type GRAND algorithms;

2. distribution of the number of decoding tests;

3. AGP-based ordering principles for ORB-type GRAND algorithms.

Based on these results, we further establish the ordering principle based on non-increasing AGP, which motivates RS-ORBGRAND and serves as a reference point for the fixed-code analysis in the next section.

3.1 Random Code Ensemble↩︎

Starting with the channel model in Section 2.1, we further consider the codebook as a subset of size \(M = 2^K\) uniformly drawn from all possible size-\(2^K\) subsets of \(\mathbb{F}_2^N\) at random. Denote the random codebook by \(\mathbfcal{C}\), and its realization by \(\mathcal{C}\).

Operationally, one may generate \(\mathbfcal{C}\) via sampling without replacement. First, draw \(\underline{W}(1)\) from \(\mathbb{F}_2^N\) uniformly at random; then, draw \(\underline{W}(2)\) from \(\mathbb{F}_2^N \backslash \{\underline{W}(1)\}\) uniformly at random; continuing this procedure, draw \(\underline{W}(m)\) from \(\mathbb{F}_2^N \backslash \{\underline{W}(1), \ldots, \underline{W}(m-1)\}\) uniformly at random, until \(m = 2^K\).

Note that the random code ensemble of \(\mathbfcal{C}\) is different from the more commonly considered i.i.d. random code ensemble, which corresponds to sampling \(\mathbb{F}_2^N\) with replacement. For \(\mathbfcal{C}\), all the codewords are distinct, and this property facilitates our analysis. Also note that for \(\underline{W}\) uniformly drawn from \(\mathbfcal{C}\) at random, each of its \(N\) positions is uniform over \(\mathbb{F}_2\).

3.2 Analysis of Block Error Rate↩︎

In this subsection, we analyze the BLER averaged over the random code ensemble. The result is stated in the following theorem.

The rest of this subsection is devoted to proving Theorem 1. Fig. 4 visually shows the logic flow chart of the proof. In a nutshell, we decompose \(P_{\text{err}}\) into the target-miss and target-preemption components, as shown in Proposition 4. These two parts are then quantified in Propositions 5 and 6, respectively.

In the sequel, we proceed to calculate these two error probabilities respectively.

3.2.1 Target-Miss Error↩︎

The following proposition characterizes the target-miss probability.

The following corollary further reveals the role of \(p_t\).

From ?? , together with \(p_t = \mathbf{E}_{\underline{Y}}\!\left[P_{\underline{W}|\underline{Y}}(\theta(\underline{Y})\oplus \pi(\underline{e}(t)) \mid \underline{Y})\right]\), we observe that the probability of target-miss error depends solely on the channel statistics through the quantities \(\{p_t\}\) and is independent of the particular realization of the codebook. This reveals a useful separation between channel effects and codebook effects in the analysis. Intuitively, target-miss error occurs when the target EP appears late in the ordered EP sequence. When the channel causes the hard-decision vector \(\theta(\underline{Y})\) to differ from the transmitted codeword in many positions, the corresponding target EP typically has low priority in the EP ordering, and thus a small testing budget \(T\) leads to a high target-miss probability.

In our prior work [28], only this aspect was considered, where the decoding problem was effectively reduced to a search problem. However, when \(T\) becomes sufficiently large, target-preemption error—arising from competing codewords encountered before the target EP—can become the dominant cause of decoding failure. This effect will be analyzed next.

3.2.2 Target-Preemption Error↩︎

Using the position-wise decomposition in Proposition 4, the target-preemption probability in ?? can be written as \[\begin{align} P_{\text{II}} = & \sum_{t=1}^{T}\Pr(\theta(\underline{Y})\oplus \pi(\underline{e}(t)) = \underline{W}(1))\cdot\Pr(\theta(\underline{Y})\oplus \pi(\underline{e}(t'))\in \mathbfcal{C},\exists\;t'< t \mid \theta(\underline{Y})\oplus \pi(\underline{e}(t))=\underline{W}(1))\\ = & \sum_{t=1}^{T}p_{t}\cdot\Pr(\theta(\underline{Y})\oplus \pi(\underline{e}(t'))\in \mathbfcal{C},\exists\;t'< t \mid \theta(\underline{Y})\oplus \pi(\underline{e}(t))=\underline{W}(1)),\label{eq:Type-II-simplified} \end{align}\tag{29}\] where we have utilized Corollary 1.

For notational convenience, we introduce the pre-target codeword-hit probability: \[f(\mathbfcal{C},\mathcal{E},t) := \Pr(\theta(\underline{Y})\oplus \pi(\underline{e}(t'))\in \mathbfcal{C},\exists\;t'< t \mid \theta(\underline{Y})\oplus \pi(\underline{e}(t))=\underline{W}(1)), \label{def:pre95target95hit}\tag{30}\] which is the conditional probability that although the \(t\)-th test would identify the sent codeword, at least one earlier EP during the first \(t-1\) tests leads to a competing codeword. Clearly we have \(f(\mathcal{C}, \mathcal{E}, 1) = 0\). With the pre-target codeword-hit probability, the target-preemption probability in 29 is further rewritten as \[\sum_{t=1}^{T}p_{t} f(\mathbfcal{C},\mathcal{E},t).\label{eq:Type-II-simplified-f}\tag{31}\]

The following lemma quantifies the pre-target codeword-hit probability, i.e., the probability that one of the first \(t-1\) candidate words coincides with another codeword in the randomly generated codebook.

We are now ready to establish the probability of target-preemption error, as given by the following proposition.

Combining Propositions 4, 5, and 6, we establish Theorem 1.

3.3 Analysis of Number of Tests↩︎

In this subsection, we study the distribution of the number of tests conducted by the codeword tester. As before, \(t\) indexes the ordered EP sequence, and \(f(t)=f(\mathbfcal{C}, \mathcal{E}, t)\) is the pre-target codeword-hit probability from Lemma 4. We let \(P_{\text{stop}}(t)\) denote the probability that the codeword tester stops after exactly \(t\) tests.

Proposition 7 below characterizes the probability distribution of the number of tests before declaring the decoded codeword.

Based on Proposition 7, we have the following theorem characterizing the average number of tests.

Substituting \(f(t) = 1 - \prod_{i=1}^{t-1}\frac{2^N-2^K+1-i}{2^N-i}\) given by Lemma 4 into 39 , we have \[Q = \sum_{t=1}^{T}\left(\prod_{i=1}^{t-1}\frac{2^N-2^K+1-i}{2^N-i}\right) - \sum_{t=1}^{T-1}p_t\left(\sum_{i=t+1}^{T}\prod_{j=1}^{i-1}\frac{2^N-2^K+1-j}{2^N-j}\right).\]

From Proposition 7 we can also quantify the probability of decoding correctly, conditioned on the event that the codeword tester stops after \(t\) tests.

3.4 Optimal AGP Ordering for the Random Code Ensemble↩︎

By the analysis of the average BLER and the average number of tests in the preceding two subsections, we now establish the optimal ordering principle for ORB-type GRAND over the random code ensemble.

Theorem 3 is an ordering result rather than an algorithmic claim. Algorithm 3 implements this principle within the ORB-type structure by estimating the AGPs of a finite candidate EP list and then reshuffling the list in non-increasing AGP order. Thus, for the random code ensemble, RS-ORBGRAND can be viewed as a practical realization of the optimal AGP ordering over the candidate list used for construction.

3.5 Illustrations↩︎

We present some numerical results to illustrate the analysis in this section. In the numerical illustrations we consider the random code ensemble described in Section 3.1 with \(N = 127\) and \(K = 113\). We plot in Fig. 5 the average BLER and its target-miss and target-preemption components, according to Theorem 1 and Propositions 5 and 6. We use the original ORBGRAND algorithm [20], and let the maximum number of tests \(T\) change from \(1\) to \(10^4\). We see that the target-miss probability dominates for small \(T\) and decreases with \(T\), while the target-preemption probability increases with \(T\) and becomes dominant for large \(T\). This behavior is consistent with our intuition.

To gain further intuition on ORB-type GRAND algorithms, Fig. 6 plots the AGP sequence \(\{p_{t}\}_{t=1,\ldots,T}\) from Proposition 3, with \(T = 10^4\), and the stopping probability sequence \(\{P_{\text{stop}}(t)\}_{t=1,\ldots,T}\) from Proposition 7. For ORBGRAND, both sequences show an overall downward trend with \(t\) but have highly patterned variations. For RS-ORBGRAND, in contrast, both sequences decrease monotonically with \(t\).

To illustrate the improvement of RS-ORBGRAND in decoding performance, we compare the BLER of ORBGRAND and RS-ORBGRAND in Fig. 7 for the random code ensemble. We plot BLER curves for different choices of \(T\). Starting from \(T = 100\), RS-ORBGRAND visibly outperforms ORBGRAND, showing its advantage of prioritizing EPs with larger AGPs. We also observe that, for a fixed \(T\), as \(E_b/N_0\) grows sufficiently large, the downward trend of BLER curves gradually stalls. This is because ORB-type GRAND performance is ultimately limited by EPs outside the tested set of size \(T\), unless \(T = 2^N\).

We also examine the performance improvement of RS-ORBGRAND from another perspective, as shown in Fig. 8. The bars show the stopping probability \(P_{\text{stop}}(t)\) over different test intervals, obtained from Proposition 7, while the curves show the corresponding conditional error probability \(1-P_{\text{succ}\mid\text{stop}}(t)\), obtained from Corollary 2. Compared with ORBGRAND, RS-ORBGRAND has a higher chance to stop decoding with \(10\)–\(10^2\) tests, and lower chance with \(10^2\)–\(10^3\) and \(10^3\)–\(10^4\) tests. These results further corroborate the ordering principle based on non-increasing AGP in Theorem 3.

4 Linear Block Codes↩︎

In this section, we extend the ORB-type GRAND analysis from the random code ensemble to fixed linear block codes. The same target-miss/target-preemption decomposition remains useful, but the preemption term is no longer governed only by the number of earlier tests. Instead, it depends on algebraic relations among the tested EP differences and the codewords of the underlying code.

We first formulate the fixed-code model in Section 4.1. Section 4.2 derives the BLER expression by reusing the random-ensemble decomposition where it remains applicable and isolating the code-dependent preemption term. Section 4.3 studies AGP-ordered EP sequences in this setting, and Section 4.4 characterizes the remaining code-dependent term through code-weight relationships.

4.1 Linear Block Code Model↩︎

Consider a binary linear block code with rate \(R=K/N\) and generator matrix \(G\in\mathbb{F}_2^{K\times N}\). The corresponding codebook is \[\mathcal{C}=\{G^T\underline{u}:\underline{u}\in\mathbb{F}_2^K\},\] which contains \(2^K\) distinct codewords.

To facilitate a notation parallel to that used for the random code ensemble in Section 3, we introduce a randomized indexing of the codewords in \(\mathcal{C}\). Specifically, we regard the codewords in \(\mathcal{C}\) as arranged in a random order, chosen uniformly from all \(2^K!\) permutations, and denote the resulting ordered random codebook by \(\mathbfcal{C}=\{\underline{W}(1),\underline{W}(2),\ldots,\underline{W}(2^K)\}\). Here, \(\mathbfcal{C}\) is random only through the ordering of the codewords, whereas the underlying codebook \(\mathcal{C}\) itself remains fixed.

Equivalently, this construction can be viewed as sampling all codewords in \(\mathcal{C}\) without replacement and recording them in the order in which they are drawn. This randomized ordering is introduced only for analytical convenience, so that the transmitted codeword can be represented as \(\underline{W}(1)\) without loss of generality. This randomized indexing does not affect the decoding rule or the performance, but enables a unified probabilistic representation consistent with the random code ensemble. In the analysis below, we keep \(\mathbfcal{C}\) when invoking this randomized indexing argument. Once membership in the underlying code is considered, we write the fixed codebook as \(\mathcal{C}\).

4.2 Analysis of Block Error Rate↩︎

Unlike the random code ensemble, where the decoding performance depends solely on the EP ordering through \(\{p_t\}\), the performance of ORB-type GRAND over linear block codes is also influenced by the structure of the code.

In particular, interactions between different EPs may lead to decoding errors even when the target EP is included in the tested sequence, giving rise to a non-negligible target-preemption component. To capture this effect, we establish a unified analytical expression that explicitly relates the BLER to both the EP ordering and the code structure.

The rest of this subsection is devoted to proving Theorem 4. Fig. 9 summarizes the main conclusions of this section and outlines the logical flow of the derivations for fixed linear block codes.

In the analysis of the BLER, we continue to decompose the overall error event into target-miss and target-preemption components. It is shown that the characterization of the target-miss component remains identical to that under the random code ensemble, whereas the treatment of the target-preemption component requires additional consideration that accounts for the structure of linear block codes.

4.3 Optimal ORB-type GRAND under Linear Block Codes↩︎

This subsection studies the ordering of a fixed candidate EP set for a fixed linear block code. The candidate set itself is assumed to be given; hence the result below should be read as a structural optimality statement for arranging the selected EPs, not as a guarantee that the selected set is globally optimal among all \(2^N\) EPs.

Recall from 30 that \(f(\mathcal{C},\mathcal{E},t)\) denotes the pre-target codeword-hit probability when the target EP is \(\pi(\underline{e}(t))\). Theorem 4 shows that, for an output-symmetric channel and the rank-based permutation \(\pi\), this quantity reduces to \[f(\mathcal{C},\mathcal{E},t) = \Pr\!\big(\pi(\underline{e}(t') \oplus \underline{e}(t)) \in \mathcal{C},\;\exists\, t' < t\big), \label{eq:mif95linear}\tag{51}\] and accordingly, \[P_{\text{err}} = 1 - \sum_{t=1}^{T} p_t \!\left(1 - \Pr\!\big(\pi(\underline{e}(t') \oplus \underline{e}(t)) \in \mathcal{C},\;\exists\, t' < t\big)\right) = 1 - \sum_{t=1}^{T} p_t \big(1 - f(\mathcal{C},\mathcal{E},t)\big), \quad P_{\text{succ}} = \sum_{t=1}^{T} p_t \big(1 - f(\mathcal{C},\mathcal{E},t)\big).\]

The output-symmetric channel assumption and the rank-based permutation are the standing conditions under which the conditional expression in Theorem 4 reduces to the unconditional form above. In what follows, we present the corresponding results for a fixed linear block code. Compared with the case of the random code ensemble in Theorem 3, the optimality structure becomes more involved due to the presence of code-induced dependencies among EPs. We therefore state the result in the following form.

Despite the non-uniqueness of optimal orderings and the lack of a precise characterization at the boundary between the \(T\)-th and \((T+1)\)-th EPs, arranging EPs in a non-increasing order of \(\{p_t\}\) remains a natural and well-motivated design principle. Theorem 5 shows that such an ordering is always attainable without loss of optimality within any fixed candidate set, thereby providing a systematic construction guideline with a clear fixed-code scope.

Building upon the structural characterization of optimal EP ordering in Theorem 5, we next turn to a more explicit characterization of the decoding error probability for linear block codes. In particular, we aim to characterize the remaining code-dependent term in the BLER and reveal how it is governed by the EP ordering and higher-order weight relationships of the code.

4.4 Pre-Target Codeword-Hit Probability for Linear Block Codes↩︎

In this subsection, we further characterize the pre-target codeword-hit probability \(f(\mathcal{C},\mathcal{E},t)\) for linear block codes. This is the only code-dependent term in the BLER expression of Theorem 4. Thus the purpose of this subsection is narrow: we explain how the structure of a fixed code enters this term.

Unlike the random code case, where the pre-target codeword-hit probability depends only on the target position, the linear block code case involves dependencies among multiple EP differences. These dependencies arise because several permuted EP differences may simultaneously fall into the fixed code. The main tool below is therefore a combinatorial representation based on the weight relationships among ordered codeword tuples.

The analysis in this subsection is technically self-contained. It mainly supports the first two parts of the simulation section, where the BLER expression and the impact of code structure are validated. Readers primarily interested in the RS-ORBGRAND performance comparison may skip the derivation on a first reading and return to it when examining those validation results.

The main idea is to separate each joint pre-target hit probability into a code-structure factor and a coordinate-permutation factor. The former counts codeword tuples in \(\mathcal{C}\) with a prescribed weight relationship, while the latter measures how likely the rank-based permutation is to realize a matching tuple.

Under a memoryless output-symmetric channel, the coordinate LLRs, and hence the reliabilities \(|\ell_1|,\ldots,|\ell_N|\), are i.i.d. Therefore, for the rank-based permutation used for ORB-type GRAND above, each reliability ordering occurs with probability \(1/N!\) (assuming ties occur with probability zero, or are broken uniformly). Accordingly, \(\pi\) may be regarded as a uniform random permutation in the expressions below. For \(i<j\), denote the EP difference by \(\underline{e}(i,j)\triangleq\underline{e}(i)\oplus\underline{e}(j)\), and define the event \(A_{ij}\triangleq \{\pi(\underline{e}(i,j))\in\mathcal{C}\}\). Then the pre-target codeword-hit probability can be written as \(f(\mathcal{C},\mathcal{E},t) = \Pr\!\left(\bigcup_{i=1}^{t-1}A_{it}\right)\). Applying the inclusion–exclusion principle, we obtain \[\label{eq:pre95target95hit95IEP} f(\mathcal{C},\mathcal{E},t) = \sum_{j=1}^{t-1}(-1)^{j-1} \sum_{1\le i_1<\cdots<i_j<t} \Pr\!\left(\bigcap_{k=1}^{j}A_{i_k t}\right).\tag{59}\] In particular, retaining only the first-order term in 59 gives the union bound, equivalently the first Bonferroni inequality [37], \[\label{eq:first95order95f95bound} f(\mathcal{C},\mathcal{E},t) \le \sum_{i=1}^{t-1}\Pr(A_{it}).\tag{60}\] Since the BLER expression in Theorem 4 is increasing in \(f(\mathcal{C},\mathcal{E},t)\) for each \(t\), this directly yields the computable upper bound \[\label{eq:first95order95bler95bound} P_{\mathrm{err}} \le 1-\sum_{t=1}^{T}p_t + \sum_{t=1}^{T}p_t\sum_{i=1}^{t-1}\Pr(A_{it}).\tag{61}\] This bound only requires the single-event probabilities \(\Pr(A_{it})\), given explicitly in Corollary 3, and will be used as a simple analytical benchmark in the numerical experiments.

The first-order bound already reflects the code structure through the ordinary weight distribution. The remaining joint probabilities in 59 capture finer dependencies: whether several events \(A_{i_k t}\) occur simultaneously depends on the algebraic relationships among the corresponding EP differences. These relationships can be fully described by the weights of all XOR combinations of the involved vectors. This motivates the weight-relationship notation below.

Specifically, let \(\{0,1\}^t\) denote the set of all binary vectors of length \(t\), ordered in lexicographic order. The next two definitions provide the bookkeeping needed to count the joint events in 59 : \(\mathcal{F}(\cdot)\) records the relevant weight relationships, while \(Z(\cdot)\) counts how often a given relationship appears in the codebook.

The conventional weight distribution is recovered as the special case \(t=1\). More generally, \(\mathcal{F}(\cdot)\) and \(Z(\cdot)\) characterize higher-order structural relationships among multiple codewords. For example, when \(t=3\), the collection \(\bigl(g(\underline{b})\bigr)_{\underline{b}\in\{0,1\}^3,\,\underline{b}\neq \underline{0}}\) consists of the Hamming weights of all nonempty XOR combinations of \(\underline{u}(1),\underline{u}(2),\underline{u}(3)\), and \(Z\bigl((g(\underline{b}))_{\underline{b}\in\{0,1\}^3}\bigr)\) counts the number of ordered triples having that prescribed relationship.

The following theorem formalizes this decomposition exactly for all joint terms in the inclusion–exclusion expansion.

Theorem 6 is an exact fixed-code expression when the full inclusion–exclusion sum is retained and the codeword-tuple counts \(Z(\mathbf{g})\) are evaluated exactly. In practical low-BLER evaluation, two distinct approximations may be introduced: truncating the inclusion–exclusion sum to a finite order, and replacing unavailable higher-order values of \(Z(\mathbf{g})\) by a structural model. These approximations are not part of the theorem itself and will be stated explicitly when used in the numerical section.

Before proving Theorem 6, we separate the argument into two simple counting steps. First, a joint pre-target hit can occur only through codeword tuples whose weight relationship matches that of the EP-difference tuple. Second, once such a tuple is fixed, the number of coordinate permutations that realize the match depends only on this common weight relationship.

Lemma 5 reduces the joint probability to a permutation-counting problem. The following proposition solves this counting problem by grouping coordinates according to the binary column that they form across an ordered tuple.

It remains only to justify that the state multiplicities in Proposition 8 are indeed determined by the weight relationship \(\mathbf{g}\). The following proposition gives this relation explicitly; its recursion and invertibility details are deferred to the appendix.

Now we are ready to complete the proof of Theorem 6.

It remains to combine the above ingredients with the inclusion–exclusion expansion 59 . For any fixed indices \(1\le i_1<\cdots<i_j<t\), Lemma 5 shows that \(\Pr\!\left(\bigcap_{k=1}^{j}A_{i_k t}\right)\) can be evaluated by summing over all ordered codeword tuples in \(\mathcal{C}^j\) having the same weight relationship as \([\underline{e}(i_1,t),\ldots,\underline{e}(i_j,t)]\).

By Proposition 8, for every ordered codeword tuple appearing in this summation, the number of admissible coordinate permutations depends only on the common weight relationship \(\mathbf{g}=\mathcal{F}(\underline{e}(i_1,t),\ldots,\underline{e}(i_j,t))\) and is given by \(\mathcal{H}(\mathbf{g})\) in ?? . Hence, \[\Pr\!\left( \bigcap_{k=1}^{j}\{\pi(\underline{e}(i_k,t))=\underline{u}(k)\} \right) = \frac{1}{N!}\mathcal{H}(\mathbf{g}).\]

Hence, every ordered codeword tuple with weight relationship \(\mathbf{g}\) contributes the same probability, and summing over all such tuples yields \[\Pr\!\left(\bigcap_{k=1}^{j}A_{i_k t}\right) = \frac{1}{N!}Z(\mathbf{g})\mathcal{H}(\mathbf{g}).\]

Substituting this expression into 59 gives ?? , which completes the proof of Theorem 6.

Theorem 6 separates the computation of \(f(\mathcal{C},\mathcal{E},t)\) into two parts. The factor \(\mathcal{H}(\mathbf{g})\) is purely combinatorial and captures the symmetry induced by coordinate permutations. The term \(Z(\mathbf{g})\) is code-dependent and describes how often a given higher-order weight relationship appears in the codebook.

This separation is useful at two levels. The first-order term leads to a simple upper bound that depends only on the ordinary weight distribution. Higher-order terms refine this bound by incorporating joint codeword relationships. We spell out both points below.

Evaluation. From the figure, we obtain \(\mathbf{g}=(15,7,7,8,8,5,7,6)\). Applying Theorem 6, the corresponding joint-event probability is \[\frac{1}{15!}\,Z(\mathbf{g})\,\mathcal{H}(\mathbf{g}).\]

To compute \(\mathcal{H}(\mathbf{g})\), we solve \(\mathbf{J}^{(3)}=\mathbf{B}_3^{-1}\mathbf{g}^{(3)}\). Using \[\mathbf{B}_3= \left[\begin{array}{llll:llll} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\ \hdashline 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{array}\right],\qquad \mathbf{B}_3^{-1} = \frac{1}{4} \left[\begin{array}{rrrrrrrr} 4 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ 0 & 1 & -1 & 1 & -1 & 1 & -1 & 1 \\ 0 & -1 & 1 & 1 & -1 & -1 & 1 & 1 \\ 0 & 1 & 1 & -1 & -1 & 1 & 1 & -1 \\ 0 & -1 & -1 & -1 & 1 & 1 & 1 & 1 \\ 0 & 1 & -1 & 1 & 1 & -1 & 1 & -1 \\ 0 & -1 & 1 & 1 & 1 & 1 & -1 & -1 \\ 0 & 1 & 1 & -1 & 1 & -1 & -1 & 1 \end{array}\right].\] Hence, \[[J(000),J(100),\ldots,J(111)]^T=\mathbf{B}_3^{-1}\mathbf{g}^T=[3,1,2,1,1,3,2,2]^T,\] and therefore \[\mathcal{H}(\mathbf{g})=\prod_{l=0}^{7}J(l)!=(3!)(1!)(2!)(1!)(1!)(3!)(2!)(2!)=288.\]

Thus, \[\Pr(A_{1t}\cap A_{2t}\cap A_{3t}) = \frac{288}{15!}\,Z(\mathbf{g}),\] where \(Z(\mathbf{g})\) is determined by the codebook. This example illustrates that the joint-event probability decomposes into a combinatorial factor \(\mathcal{H}(\cdot)\) and a structural term \(Z(\cdot)\).

5 Numerical Experiments↩︎

In this section, we provide numerical results to validate the proposed analytical framework and evaluate the performance of RS-ORBGRAND. We first examine how many Monte Carlo trials are used and how the resulting estimates behave statistically, then verify the derived BLER expression on representative codes, and finally compare RS-ORBGRAND with existing decoding methods in terms of accuracy and complexity.

5.1 Accuracy of Monte Carlo Estimation↩︎

In this subsection, we quantify the statistical accuracy of the simulation results used later in this section. Both the conventional BLER from decoding simulation and the BLER computed from the analytical expression in Section 4 rely on Monte Carlo estimation, so we derive CLT-based sufficient conditions on the numbers of independent Monte Carlo trials. We let \(\mathcal{L}_{\text{dec}}\) denote the number of independent decoding simulations used to estimate the BLER, and let \(\mathcal{L}_{\text{agp}}\) denote, in each run of the analytical method, the number of channel uses used to obtain Monte Carlo estimates of the AGPs \(\{p_t\}\).

We first consider the BLER under conventional decoding. Based on the Markov chain \(\underline{W}\rightarrow \underline{Y}\rightarrow \hat{\underline{W}}\), we write \(P_{\text{err}} = \Pr(\underline{W} \neq \hat{\underline{W}})\) and estimate it from \(\mathcal{L}_{\text{dec}}\) independent Monte Carlo trials. The natural estimator is \[\label{eq:decoding95bler95estimator} \hat{P}_{\text{err}} = \frac{1}{\mathcal{L}_{\text{dec}}} \sum_{i=1}^{\mathcal{L}_{\text{dec}}} \mathbf{1}(\underline{w} \neq \hat{\underline{w}}),\tag{65}\] which is unbiased, with \(\operatorname{Var}(\hat{P}_{\text{err}}) = P_{\text{err}}(1 - P_{\text{err}})/\mathcal{L}_{\text{dec}}\). By the central limit theorem (CLT), for sufficiently large \(\mathcal{L}_{\text{dec}}\) we use the approximation \(\hat{P}_{\text{err}} \sim \mathcal{N}\!\left(P_{\text{err}}, P_{\text{err}}(1 - P_{\text{err}})/\mathcal{L}_{\text{dec}}\right)\), so that for a target relative deviation \(\Delta\) and confidence level \(\alpha\) a sufficient condition on \(\mathcal{L}_{\text{dec}}\) is \[\label{eq:decoding95clt95condition} 2\Phi\!\left(\sqrt{\frac{\mathcal{L}_{\text{dec}}}{P_{\text{err}}(1 - P_{\text{err}})}} \, \Delta P_{\text{err}} \right) - 1 \geq \alpha.\tag{66}\]

We next consider the BLER when it is obtained from the analysis of Section 4, i.e., from \[\label{eq:linear95bler95decomp} P_{\text{err}} = 1 - \sum_{t=1}^{T} p_t\bigl(1 - f(\mathcal{C}, \mathcal{E}, t)\bigr).\tag{67}\] The same \(1 - \sum_{t=1}^{T} p_t\bigl(1 - f(\mathcal{C}, \mathcal{E}, t)\bigr)\) structure applies in both the random-ensemble and fixed-code settings. For a random code ensemble, \(f(\mathcal{C}, \mathcal{E}, t)\) is available in closed form by ?? . For a fixed linear block code, the exact \(f(\mathcal{C}, \mathcal{E}, t)\) is given by the full inclusion–exclusion expression in Theorem 6; practical computation may instead use a finite-order truncation and, when necessary, an approximation to the code-dependent counts \(Z(\mathbf{g})\). For brevity, write \(f(t)=f(\mathcal{C}, \mathcal{E}, t)\) in the remainder of this subsection.

We first isolate the sampling error caused by estimating the AGPs. To this end, treat the evaluated values \(\{f(t)\}_{t=1}^{T}\) as fixed, so that the only randomness in the analytical BLER estimate comes from replacing \(\{p_t\}\) by Monte Carlo estimates from an \(\mathcal{L}_{\text{agp}}\)-trial run. The reported BLER is then \[\label{eq:agp95bler95estimator} \hat{P}_{\text{err}} = 1 - \sum_{t=1}^{T} \hat{p}_t\bigl(1 - f(t)\bigr).\tag{68}\] By the multivariate CLT, \((\hat{p}_1,\ldots,\hat{p}_T)\) is asymptotically jointly normal as \(\mathcal{L}_{\text{agp}}\to\infty\). The AGP estimators are unbiased for \((p_1,\ldots,p_T)\), and 67 is affine in \((p_1,\ldots,p_T)\), so the corresponding \(\hat{P}_{\text{err}}\) in 67 is unbiased for \(P_{\text{err}}\) for the same \(\{f(t)\}\) and is asymptotically normal. In the expressions below, \(\operatorname{Var}(\hat{P}_{\text{err}})\) denotes the asymptotic variance of \(\sqrt{\mathcal{L}_{\text{agp}}}\bigl(\hat{P}_{\text{err}}-P_{\text{err}}\bigr)\); in practice it is estimated from the sample variance of \(\{\hat{P}_{\text{err}}^{(r)}\}\) over independent repetition indices \(r\), each obtained from a separate \(\mathcal{L}_{\text{agp}}\)-trial run. For large \(\mathcal{L}_{\text{agp}}\), we use \(\hat{P}_{\text{err}} \sim \mathcal{N}\!\left(P_{\text{err}}, \operatorname{Var}(\hat{P}_{\text{err}})/\mathcal{L}_{\text{agp}}\right)\), which yields the following sample-size condition \[\label{eq:agp95clt95condition} 2\Phi\!\left(\sqrt{\frac{\mathcal{L}_{\text{agp}} P_{\text{err}}^2}{\operatorname{Var}(\hat{P}_{\text{err}})}} \, \Delta \right) - 1 \geq \alpha.\tag{69}\]

In the same spirit, to target \(\Delta = 1\%\) and \(\alpha = 99\%\), a convenient sufficient condition for the number of decoding simulations \(\mathcal{L}_{\text{dec}}\) is \[\label{eq:decoding95sample95rule} \mathcal{L}_{\text{dec}} \gtrsim 9 \times 10^4 \cdot \frac{1 - P_{\text{err}}}{P_{\text{err}}}.\tag{70}\] For the analytical evaluation that uses Monte Carlo estimates of \(\{p_t\}\), the quantities \(P_{\text{err}}\) and \(\operatorname{Var}(\hat{P}_{\text{err}})\) in the display below are taken for the same \(\{f(t)\}\) as in 67 , and a corresponding condition for \(\mathcal{L}_{\text{agp}}\) is \[\label{eq:agp95sample95rule} \mathcal{L}_{\text{agp}} \gtrsim 9 \times 10^4 \cdot \frac{\operatorname{Var}(\hat{P}_{\text{err}})}{P_{\text{err}}^2}.\tag{71}\]

5.2 Analytical and Simulated BLER↩︎

We compare decoding simulation with the BLER from the analytical expression for representative linear block codes, in line with Subsection 5.1 and the preceding remark: the deviation from decoding includes Monte Carlo error in the estimates of the AGPs, while a finite expansion order in \(f\) or an approximation to \(Z(\mathbf{g})\) may introduce an additional bias. We begin with the Hamming\((7,4)\) code, with ORBGRAND and at most \(T = 10\) tests.

The evaluation follows directly from the theoretical results in Section 4. Specifically, we compute the AGP \(\{p_t\}\) using Proposition 3, evaluate the pre-target codeword-hit function \(f(\mathcal{C}, \mathcal{E}, t)\) via Theorem 6, and obtain the BLER from Theorem 4. For the short Hamming code, the required codeword-tuple counts are evaluated exactly; the first-order single-event probabilities are illustrated in Example 2. For the longer BCH code considered next, the first-order term uses the exact weight distribution, while the second-order term uses the pairwise approximation described below.

Fig. 12 compares the BLER obtained from decoding simulation and from the analytical expression. To compute \(f(\mathcal{C}, \mathcal{E}, t)\), we apply the inclusion–exclusion principle and truncate the expansion after a finite number of terms. The curves labeled by different orders correspond to retaining the first one, two, and three terms in ?? , respectively; in particular, the first-order curve is the union-bound-based BLER upper bound in 61 .

It is observed that retaining two terms already yields the same result as retaining three terms. This indicates that, under the given EP set \(\mathcal{E}\) and testing budget \(T\), the probability of having three or more pre-target codeword hits is zero. Consequently, the truncated expression of \(f(\mathcal{C}, \mathcal{E}, t)\) is exact in this case.

The small gap is therefore due mainly to sampling error in \(\{\hat{p}_t\}\) (cf.Subsection 5.1), while \(f\) is effectively free of truncation error. The case confirms that the analysis tracks decoding when the \(f\) expansion is exact at the order retained.

We next consider a longer Bose–Chaudhuri–Hocquenghem (BCH) code, namely BCH\((127,113)\), and evaluate both the accuracy and computational complexity of the finite-order analytical approximation with \(T = 10^4\).

Fig. 13 compares the BLER obtained from decoding simulation and from different analytical approximations. The order-\(k\) curves correspond to retaining the first \(k\) terms in the inclusion–exclusion expansion ?? . In particular, order-0 ignores the pre-target codeword-hit effect, order-1 gives the first-order upper bound in 61 , and order-2 further incorporates pairwise interactions using the approximation to \(Z(\mathbf{g}^{(2)})\) described below. This matches the discussion in Subsection 5.1 and the remark: a small \(k\) inflates the approximation error in \(f\), while order-2 together with a sufficiently large \(\mathcal{L}_{\text{agp}}\) brings the analytical points close to the decoding curve (see Fig. 13).

It is observed that the first-order bound is already reasonably close, although still conservative (around \(3\%\) at \(6\) dB), while the second-order approximation achieves high accuracy, with a deviation below \(0.5\%\). Thus, the first-order term provides a simple and useful BLER upper bound, and adding the pairwise term substantially tightens the analytical prediction. For comparison, the method in [36] (referred to as “SO-predicted”) assumes a geometric distribution for competing-codeword hits, which leads to noticeable inaccuracies at high SNR.

To further illustrate this behavior, Fig. 14 shows the empirical distribution of the number of pre-target codeword hits, obtained from decoding simulation. It is observed that the probability decays rapidly as the number of pre-target codeword hits increases, and events involving more than two such hits are extremely rare. This empirical observation supports the effectiveness of the second-order approximation, as higher-order terms contribute negligibly in practice.

We briefly describe how the analytical results are computed in practice. By Corollary 3, the first-order term of \(f(\mathcal{C}, \mathcal{E}, t)\) depends only on the weight distribution of the code, which can be efficiently obtained from the dual code via the MacWilliams identity [38]: \[\label{eq:macwilliams95identity} A(z)=2^{-(N-K)}(1+z)^N B\!\left(\frac{1-z}{1+z}\right).\tag{72}\]

For the second-order term, the exact fixed-code expression requires \(Z(\mathbf{g}^{(2)})\), which involves the joint weight distribution of codeword pairs, where \[\mathbf{g}^{(2)}=(N,g(01),g(10),g(11)).\] Since such pairwise weight enumerators are typically unavailable for structured codes, the BCH evaluation adopts a tractable uniform support model: conditioned on their individual weights, the supports of two codewords are treated as uniformly distributed subsets of \(\{1,\ldots,N\}\). Under this model, the overlap profile—and hence \(Z(\cdot)\)—is determined by simple combinatorial counting, leading to the following approximation: \[\label{eq:second95order95Z95approx} Z(\mathbf{g}^{(2)}) \approx Z(\mathbf{g}_{01}^{(1)}) Z(\mathbf{g}_{10}^{(1)}) \cdot \frac{C_{g(01)}^{(g(01)+g(10)-g(11))/2} C_{N-g(01)}^{(g(10)+g(11)-g(01))/2}}{C_{N}^{g(10)}}.\tag{73}\] Here, \(\mathbf{g}_{01}^{(1)}=(N,g(01))\) and \(\mathbf{g}_{10}^{(1)}=(N,g(10))\).

Table 2 lists the numbers of decoding runs and AGP-trial runs (values of \(\mathcal{L}_{\text{dec}}\) and \(\mathcal{L}_{\text{agp}}\)) obtained from the bounds in Subsection 5.1 for \(\Delta = 1\%\) and \(\alpha = 99\%\), for second-order \(f\) in the same analytical setting as in Fig. 13.

The row for \(\operatorname{Var}(\hat{P}_{\text{err}})\) uses the sample variance in Subsection 5.1 for the path that estimates \(\{p_t\}\) by Monte Carlo, not the Bernoulli variance \(P_{\text{err}}(1-P_{\text{err}})\) from decoding simulation; the difference between the two explains why the sufficient condition on \(\mathcal{L}_{\text{dec}}\) in the last row is vastly larger than that on \(\mathcal{L}_{\text{agp}}\) at low \(P_{\text{err}}\).

As the SNR increases, the lower bound on \(\mathcal{L}_{\text{dec}}\) from the same sufficient conditions grows very quickly, while the corresponding lower bound on \(\mathcal{L}_{\text{agp}}\) changes only mildly across SNR, consistent with the variance scalings in Subsection 5.1.

5.3 Performance and Near-Optimality of RS-ORBGRAND↩︎

In this subsection, we evaluate the performance of the proposed RS-ORBGRAND through numerical simulations. We consider two representative codes: BCH\((127,113)\) and cyclic-redundancy-check (CRC)-aided polar\((128,114)\).

The EP list \(\mathcal{E}_{RS}\) is constructed following Algorithm 3: we first generate an initial candidate list using CDF-ORBGRAND [20], [29] and then reshuffle it by sorting the estimated AGPs \(\{p_t\}\) in descending order. Unless otherwise specified, the maximum number of tests is set to \(T=10^4\).

Fig. 15 compares the BLER of RS-ORBGRAND with several ORB-type decoders, as well as SGRAND and a lower bound on the MLD BLER. Since this lower-bound curve is no higher than the true MLD BLER curve, its SNR gap provides a conservative reference for near-MLD performance. It is observed that RS-ORBGRAND approaches SGRAND and remains within \(0.1\) dB of this lower-bound curve at high SNR. Compared with existing ORB-type decoders, RS-ORBGRAND provides a consistent performance gain. For example, at a BLER of \(10^{-5}\), the SNR gain relative to ORBGRAND is about \(0.5\) dB.

Table 3 further reports the average number of tests. Among ORB-type GRAND decoders, RS-ORBGRAND requires the smallest number of queries. Although SGRAND achieves the lowest average number of tests, it generates its EP queries adaptively from the received LLR vector for each decoding instance, which results in significantly higher computational complexity.

Fig. 16 shows the BLER performance for CRC-aided polar\((128,114)\). We further investigate the impact of the candidate set size \(T_1\) used in Algorithm 3 to form the initial EP candidate list before reshuffling. It is observed that a sufficiently large candidate set is essential for achieving good performance. Increasing \(T_1\) enables more EPs with larger AGPs to be identified and prioritized during reshuffling, thereby improving decoding performance. Notably, \(T_1\) only affects the one-time construction of \(\mathcal{E}_{RS}\), while the per-decoding complexity remains bounded by \(T = 10^4\).

6 Conclusion↩︎

This paper develops an AGP-based framework for analyzing and designing ORB-type GRAND algorithms. For random code ensembles, we derive exact expressions for the BLER, stopping-time distribution, and average number of tests under a fixed test budget. The analysis separates target-miss and target-preemption errors and establishes that ordering EPs by non-increasing AGP simultaneously minimizes the average BLER and the average number of tests over the EP set under consideration.

For fixed linear block codes, we extend the BLER analysis by isolating the code-dependent target-preemption term. This term is characterized through higher-order weight relationships of codeword tuples, with the ordinary weight distribution appearing as the first-order special case. Guided by these results, we formulate RS-ORBGRAND as an AGP-driven offline reshuffling scheme that preserves the ranking-based ORB-type structure. Numerical results show consistent gains over existing ORB-type GRAND decoders and near-MLD performance, while finite-order analytical evaluations based on the derived expressions enable efficient low-error-rate prediction beyond brute-force decoding simulation.

6.1 Proof of Proposition 9↩︎

6.1.0.1 Proof of the recursive structure.

We derive ?? from the entry-wise definition of \(\mathbf{B}_{j+1}\).

6.1.0.2 Proof of invertibility.

We prove that \(\mathbf{B}_j\) is invertible over \(\mathbb{R}\) for all \(j\).

References↩︎

---

1. The authors are with Department of Electronic Engineering and Information Science, University of Science and Technology of China, Hefei, China, 230027.↩︎

2. For implementation, setting such a maximum number \(T\) typically much smaller than \(2^N\) is necessary, and in the literature this is called GRAND with abandonment (GRANDAB) [8].↩︎