Soft-input, soft-output joint detection and GRAND

The upcoming sixth generation (6G) of wireless communications promises to support a plethora of data-demanding and delay-sensitive applications [1], requiring both ultra-broadband high-frequency connectivity [2] and ultra-reliable low-latency communication (URLLC) [3]. Such variety in requirements compels a paradigm shift from structured, code-specific channel-code decoding to universal and practical decoding that is efficient for different code rates and lengths. Early universal near-maximum-likelihood (ML) decoders for linear codes adopted a list-decoding principle [4, 5]. Recently, guessing random additive noise decoding (GRAND) [6, 7] is celebrated as a novel and practical universal decoder suited for block-code constructions of moderate redundancy.

GRAND is a capacity-achieving channel-code decoder that has demonstrated ML decoding performance on arbitrary (even unstructured) code-books. Instead of directly identifying the transmitted code-word, GRAND aims at identifying the noise effect that corrupts the code-word; it successively reverses the noise effects from the received signal to recover candidate transmitted words. By leveraging information on channel and noise models, the candidate noise sequences are ordered and queried in decreasing likelihood, guaranteeing the first recovered code-word to be the ML decoding solution, even for channels with memory in the absence of interleaving. The guesswork literature [8, 9, 10] establishes the computational feasibility of GRAND for all moderate redundancy codes, where the Shannon entropy rate of noise is typically less than that of information symbols [7]. Furthermore, GRAND’s computational efficiency and modularity have resulted in highly efficient circuit design, as demonstrated in a recent 65 nm [11] synthesis and a 40 nm [12] CMOS implementation.

Incorporating soft-detection symbol reliability information into decoding decisions enhances decoding accuracy [13, 14]. At one end, GRAND can leverage as soft information a one-bit mask designating whether a channel use is reliable or not [15]; specifying reliable bits via a channel-fading-induced mask is also proposed in [16]. At the other end, the complete information in continuous channel outputs serves as soft symbol-reliability information in the soft-GRAND (SGRAND) scheme [17]. A compromise between one-bit soft-GRAND and SGRAND is ordered reliability bits GRAND (ORBGRAND) [18], which matches the decoding accuracy of SGRAND through code-book-independent quantization of soft information in a hardware-friendly algorithm.

With fading channels, generating high-resolution soft information (as opposed to masks [16]) through exhaustive ML detection is computationally demanding, and low-complexity soft-output detectors only generate sub-optimal LLRs. In the absence of soft information (or with low-quality information), iterative decoding schemes can intrinsically generate soft-decoding reliability information to be fed as soft-input decoding information in subsequent iterations [19]. Such information can be updated over both the detection and decoding iterations [20], introducing more degrees of freedom in versatile, adaptive communication systems. However, how to generate soft-reliability outputs through GRAND remains unclear. Consequently, iterative soft-input, soft-output (SISO) GRAND (turbo-GRAND) has not yet been investigated.

In this work, we propose a variation of GRAND that does not avail of input soft-detection bit reliability information but leverages complex received symbols (soft-information in a crude, unprocessed form), channel state information (CSI), and demapped bits (linear detector outputs) to generate soft-decoding bit-reliability information in log-likelihood ratios (LLRs). We compute the LLRs by populating Euclidean distance metrics corresponding to a list of candidate words–not necessarily code-words–resulting from noise guesswork. Because the number of guesses before hitting a code-word is limited, we cannot compute LLRs for all bits; we propose LLR thresholding. We propose a turbo-GRAND scheme in which the generated extrinsic LLRs are fed as a priori LLRs in subsequent SISO decoding iterations. With access to complex received vectors and continuous CSI, the Euclidean distance computations are common to both detection and decoding; turbo-GRAND thus realizes joint detection and decoding.

The paper is organized as follows. The problem formulation is first presented in Sec. II. Then, the proposed turbo-GRAND scheme is detailed in Sec. III. Performance and complexity results are reported in Sec. IV; conclusions are drawn in Sec. V. Regarding notation, bold upper case, bold lower case, and lower case letters correspond to matrices, vectors, and scalars, respectively. Scalar and vector $\text{L}_{2}$ norms are denoted by $\left|{\cdot}\right|$ and $\left\|{\cdot}\right\|$, respectively. $\mathsf{E}[\cdot]$, $(\cdot)^{T}$, and $(\cdot)^{*}$, stand for the expected value, transpose, and conjugate transpose, respectively. $\mathbf{I}_{M}$ is an identity matrix of size $M$, $\mathbf{0}_{N}$ is a vector of zeros of size $N$, $\mbox{\bb F}_{u}$ denotes a Galois field with $u$ elements, $\mathrm{Pr}(\cdot)$ is the probability function, and $\odot$ is the Hadamard product.

We propose a SISO variation of GRAND that leverages, in addition to the resources of Algorithm 1, the received symbols, CSI, and optional noise statistics, to generate extrinsic bit-reliability LLRs through joint detection and decoding. The LLRs are fed as input soft-decoding information to a subsequent SISO GRAND iteration (up to $T$ iterations), resulting in turbo-GRAND (Fig. 1). Turbo-GRAND aims to approach the performance of a soft GRAND with soft-input information from an exhaustive soft-output ML detector. Therefore, turbo-GRAND is helpful in the absence of soft-input information or the presence of sub-optimal soft information.

The LLR of bit $j$ of symbol $i$ is defined as

Near-optimal ML-detection log-max LLRs [22] are computed by exhaustively searching the lattice $\bar{\mathcal{X}}$, computing $\left|{\mathcal{X}_{1}}\right|\times\left|{\mathcal{X}_{i}}\right|\times\cdots\times\left|{\mathcal{X}_{M}}\right|$ Euclidean distance metrics to solve for [23]

where $\bar{\mathcal{X}}^{i,j,1}\!\triangleq\!\{\mathbf{x}\!\in\!\bar{\mathcal{X}}:c_{i,j}\!=\!1\}$ and $\bar{\mathcal{X}}^{i,j,0}\!\triangleq\!\{\mathbf{x}\!\in\!\bar{\mathcal{X}}:c_{i,j}\!=\!0\}$ are subsets of symbol vectors in $\bar{\mathcal{X}}$, having in the corresponding ${j}{\text{th}}$ bit of the ${i}{\text{th}}$ symbol a value of $1$ and $0$, respectively. We have further assumed the case of white noise, $\sigma_{i,j}\!=\!\sigma,\forall i,j$. For colored noise, $\left\|{\mathbf{y}-\mathbf{H}\mathbf{x}}\right\|^{2}$ is replaced by $\left(\mathbf{y}-\mathbf{H}\mathbf{x}\right)^{*}\Gamma^{-1}\left(\mathbf{y}-\mathbf{H}\mathbf{x}\right)$, where $\Gamma\!=\!\text{diag}\left(\mathbf{v}\right)$. The hard ML detection output is $\hat{\mathbf{x}}^{\mathrm{ML}}\!=\!\operatorname*{arg\,min}_{\mathbf{x}\in\bar{\mathcal{X}}}\left\|{\mathbf{y}-\mathbf{H}\mathbf{x}}\right\|^{2}$. Furthermore, soft information can be extracted per symbol in linear detectors [24], which are near-optimal in point-to-point systems at a high signal-to-noise ratio (SNR) but sub-optimal under symbol interference/correlation. In particular, a zero-forcing (ZF) detector equalizes the channel by multiplying by its pseudo-inverse, $\mathbf{\hat{y}}^{\mathrm{ZF}}\!=\!\left(\mathbf{H}^{*}\mathbf{H}\right)^{-1}\mathbf{H}^{*}\mathbf{y}$. The per-symbol ZF LLRs in $\mathbf{\Lambda}^{\mathrm{ZF}}$ are

where $\mathcal{X}_{i}^{j,1}\!\triangleq\!\{x_{i}\!\in\!\mathcal{X}_{i}:c_{i,j}\!=\!1\}$ and $\mathcal{X}_{i}^{j,0}\!\triangleq\!\{x_{i}\!\in\!\mathcal{X}_{i}:c_{i,j}\!=\!0\}$ are subsets of symbols in the one-dimensional constellation $\mathcal{X}_{i}$, having a ${j}{\text{th}}$ bit of $1$ and $0$, respectively, and ${\sigma_{i}^{\mathrm{ZF}}}^{2}\!=\!\sigma_{i}^{2}\!\left(h_{i}^{*}h_{i}\right)^{-1}$ is a scaled noise variance. The ZF hard-outputs are computed per symbol as $\hat{x_{i}}^{\mathrm{ZF}}\!=\!\left\lfloor\hat{y}^{\mathrm{ZF}}_{i}-x_{i}\right\rceil_{\mathcal{X}_{i}}$, where $\lfloor\eta\rceil_{\mathcal{X}_{i}}\triangleq\operatorname*{arg\,min}_{x\in\mathcal{X}_{i}}\left|{\eta-x}\right|$ is the slicing operator over $\mathcal{X}_{i}$. The demapped version of $\hat{\mathbf{x}}^{\mathrm{ZF}}$, $\hat{\mathbf{c}}^{\mathrm{ZF}}$, is the initial vector over which noise effects are guessed in turbo-GRAND.

Contrary to conventional ML and list decoders that query all or multiple code-words, the basic implementation of GRAND achieves ML decoding performance by querying noise sequences and recovering a single code-word. This scarcity in code-word hits across turbo-GRAND iterations is mitigated in joint detection and decoding. We propose generating soft-output LLRs by populating a number of Euclidean distance computations equal to the number of noise guesses, as opposed to the exponential number of distance computations in (3). In particular, through guesswork, we aim at extracting an updated hard-detected vector, $\hat{\mathbf{c}}^{\mathrm{GRAND}}$, and a reliability metric for each bit in $\hat{\mathbf{c}}^{\mathrm{GRAND}}$, accumulated in the soft-decoding LLR vector, $\bar{\mathbf{\Lambda}}^{\mathrm{GRAND}}$, all while recovering the decoded output, $\bar{\mathbf{c}}^{\mathrm{GRAND}}$.

Algorithm 2 illustrates turbo-GRAND in more detail. For detection, we keep track of an ML-detection distance metric, $d^{\mathrm{ML}}$; for decoding, we keep track of an ML-decoding distance metric, $\bar{d}^{\mathrm{ML}}$. After each turbo-GRAND iteration, the candidate vector corresponding to $d^{\mathrm{ML}}$ is the updated detected vector, $\hat{\mathbf{c}}^{\mathrm{GRAND}}$, and the candidate vector corresponding to $\bar{d}^{\mathrm{ML}}$ is the updated decoded vector, $\bar{\mathbf{c}}^{\mathrm{GRAND}}$. Furthermore, for LLR computations, we accumulate a vector of counter-ML-detection distance metrics, $\mathbf{d}^{\mathrm{cML}}\!=\![d^{\mathrm{cML}}_{1,1}\cdots d^{\mathrm{cML}}_{i,j}\cdots d^{\mathrm{cML}}_{M,q}]^{T}\!\in\!\mbox{\bb R}^{N}$, which tracks vectors closest to $\hat{\mathbf{c}}^{\mathrm{GRAND}}$, but with bit-flips at corresponding indices. Searching the entire lattice $\bar{\mathcal{X}}$ results in $d^{\mathrm{ML}}\!=\!\min_{\mathbf{x}\in\bar{\mathcal{X}}}\left\|{\mathbf{y}-\mathbf{H}\mathbf{x}}\right\|^{2}$; we can re-express (3) as

where $d^{\mathrm{cML}}_{i,j}=\min_{\mathbf{x}\in\bar{\mathcal{X}}^{i,j,0}}{\left\|{\mathbf{y}-\mathbf{H}\mathbf{x}}\right\|^{2}}$ if $\hat{c}^{\mathrm{ML}}_{i,j}=1$ and $d^{\mathrm{cML}}_{i,j}=\min_{\mathbf{x}\in\bar{\mathcal{X}}^{i,j,1}}{\left\|{\mathbf{y}-\mathbf{H}\mathbf{x}}\right\|^{2}}$ if $\hat{c}^{\mathrm{ML}}_{i,j}=0$ (note that colored noise scaling is embedded into $\mathbf{d}^{\mathrm{ML}}$ and $\mathbf{d}^{\mathrm{cML}}$ in Alg. 2). However, turbo-GRAND only searches a limited number of $\bar{\mathbf{x}}$ vectors that are extracted from the recovered $\bar{\mathbf{c}}\!=\!\hat{\mathbf{c}}\ominus\mathbf{w}$ words via guesswork, and that can be accumulated in a set $\mathcal{S}$ $\left(\left|{\mathcal{S}}\right|<T\!\times\!B\!\ll\!\left|{\bar{\mathcal{X}}}\right|\right)$.

We first initialize $d^{\mathrm{ML}}$ to $\infty$ and $\mathbf{d}^{\mathrm{cML}}$ to saturation noise-scaled thresholds. Then, $d^{\mathrm{ML}}$ and $\mathbf{d}^{\mathrm{cML}}$ are updated iteratively, upon every new noise guess (up to $B$ guesses per iteration $t$ in GRAND with abandonment). For every guessed word, $\bar{\mathbf{c}}$, we re-generate a modulated vector, $\bar{\mathbf{x}}\!=\!\text{mod}\left(\bar{\mathbf{c}}\right)$, and add it to $\mathcal{S}$. Hence, for turbo-GRAND, $d^{\mathrm{ML}}\!=\!\min_{\bar{\mathbf{x}}\in\mathcal{S}}\left\|{\mathbf{y}-\mathbf{H}\bar{\mathbf{x}}}\right\|^{2}$, and

where $d^{\mathrm{cML}}_{i,j}\!=\!\min_{\bar{\mathbf{x}}\in\mathcal{S}^{i,j,0}}{\left\|{\mathbf{y}-\mathbf{H}\bar{\mathbf{x}}}\right\|^{2}}$ if $\hat{c}^{\mathrm{GRAND}}_{i,j}\!=\!1$ and $d^{\mathrm{cML}}_{i,j}\!=\!\min_{\bar{\mathbf{x}}\in\mathcal{S}^{i,j,1}}{\left\|{\mathbf{y}-\mathbf{H}\bar{\mathbf{x}}}\right\|^{2}}$ if $\hat{c}^{\mathrm{GRAND}}_{i,j}\!=\!0$. For the ${i,j}$ indices where $d^{\mathrm{cML}}_{i,j}$ cannot be computed over $\mathcal{S}$, owing to the absence of a corresponding $\bar{\mathbf{x}}$, the initial saturated value of $N/\sigma_{i}^{2}$ is retained. Note that we use a separate $\bar{d}^{\mathrm{ML}}$ for the decoded $\bar{\mathbf{c}}^{\mathrm{GRAND}}$ because not every $\bar{\mathbf{x}}$ in $\mathcal{S}$ corresponds to a code-word. Each turbo-GRAND iteration $t$ ends with a single code-word hit $\bar{\mathbf{c}}^{\mathrm{GRAND}}(t)$; the final decoded vector after $T$ iterations is

Note that Algorithm 2 does not explicitly construct $\mathcal{S}$ and store it in memory for post-processing but instead updates the ML and counter-ML distance metrics on the fly.

The core of turbo-GRAND is a soft-input decoding mechanism which rank-orders candidate noise sequences according to $\bar{\mathbf{\Lambda}}^{\mathrm{GRAND}}$. Let $\mathbf{W}\!\in\!\mbox{\bb F}_{2}^{2^{N}\times N}$ be a matrix containing in its rows all possible noise sequences, and let $\acute{\Pi}\!:\!\mbox{\bb R}^{2^{N}}\rightarrow\{1,\cdots,2^{N}\}^{2^{N}}$ be a sorting function (increasing order). Then, $\mathbf{s}=\acute{\Pi}\left(\mathbf{W}\times\left|{\mathbf{\Lambda}}\right|\right)$ is a vector of sorted noise-sequence indices, and $\mathbf{w}=\Pi(\mathbf{s}(k))$ retrieves the ${k}{\text{th}}$ likely noise sequence. However, populating noise sequences in a single matrix is not hardware-friendly nor computationally efficient. Alternatively, SGRAND [17] recursively constructs a max-heap for each combination of reliabilities in $\mathbf{\Lambda}$ to dynamically generate $\mathbf{w}$ vectors with increasing likelihoods. Also, ORBGRAND [18] builds a bit permutation map based on the decreasing rank order of bit reliability to generate a pre-determined series of putative noise queries. Most probably, we have $\mathbf{s}(i)\!\leq\!\mathbf{s}(j)$ when $\mathrm{Pr}(\mathbf{w}\!=\!\mathbf{w}_{i})\!\geq\!\mathrm{Pr}(\mathbf{w}\!=\!\mathbf{w}_{j})$. In SGRAND [17], the latter is an “if and only if” condition. Thus, with either SGRAND or ORBGRAND, turbo-GRAND always queries the all-zeros noise sequence first and is biased to give higher priority to noise sequences of smaller Hamming weight, but not necessarily so, depending on the reliability information in $\bar{\mathbf{\Lambda}}^{\mathrm{GRAND}}$. In the absence of soft information or further channel knowledge, noise query follows increasing Hamming weights for a probability of bit flip less than $1/2$. The latter is captured by an SGRAND core of turbo-GRAND, which reduces to hard-GRAND in the absence of soft information. Hence, SGRAND can be used in the first turbo-GRAND iteration when $\mathbf{\Lambda}\!=\!\mathbf{0}_{N}$. ORBGRAND requires some soft input information to match the performance of SGRAND, so it can be adopted when $\mathbf{\Lambda}\!=\!\mathbf{\Lambda}^{\mathrm{ZF}}$ in the first iteration. However, ORBGRAND entails more noise guesses on average, so it has the potential to generate richer LLRs.

Turbo-GRAND can be modified to support iterative disjoint detection and decoding, where $\bar{\mathbf{\Lambda}}^{\mathrm{GRAND}}$ is fed all the way back to a separate detector. Towards this end, the detector should itself be SISO. For instance, the modified distance metric of a turbo MAP detector can be [25]

where $\mathbf{c_{x}}$ is the bit representation of $\mathbf{x}$. The a posteriori LLRs can be calculated as

Disjoint detection and GRAND offers good modularity, where on every detection iteration, the noise can be filtered towards new signal subspaces [26], yielding more efficient GRAND.

Following the system model of Sec. II, the block-error rate (BLER) performance of turbo-GRAND in decoding Bose–Chaudhuri–Hocquenghem (BCH) [ ​127,113] ​ codes is compared to reference GRAND/ORBGRAND schemes (ORBGRAND exhibited superior performance and complexity tradeoffs compared to other code-specific decoders [18]). Assuming AWGN and normalized transmit power (SNR of $1/\sigma^{2}$), with the absence of input soft information, Fig. 2a illustrates that SGRAND-based turbo-GRAND generates soft information that matches ML-detection soft information. Turbo-GRAND can outperform ML-detection-based ORBGRAND because: 1) turbo iterations can introduce a list-decoding gain and 2) distance computations are over an entire code-word of many channel uses; feasible ML detection search routines only span a few channel uses. A similar relative performance is noted under Rayleigh fading in Fig. 2b and Fig. 2c, using binary phase-shift keying (BPSK) and 16-quadrature amplitude modulation (16-QAM) (Gray mapping), respectively. The gains in soft-GRAND schemes are larger under fading (more than $6\,\mathrm{dB}$ SNR gains at a BLER of $10^{-2}$), highlighting the importance of turbo-GRAND in the absence of soft information. We further note that the turbo-GRAND gains are captured in two iterations, beyond which diminishing returns are expected, as both SGRAND and ORBGRAND converge faster on every new iteration, $t$, guessing over an enhanced initial vector, $\hat{\mathbf{c}}^{\mathrm{GRAND}}(t)$. The achievable gains of turbo-GRAND can be improved by tuning a fixed guess budget, $B$. Alternatively, some sort of reactive taboo search [27] can be adopted, in which every iteration starts with a pseudo-random initial vector upon which noise is guessed.

Several communication system scenarios further highlight the turbo-GRAND gains, especially under symbol interference in spatial/path diversity schemes, where ML soft information is significantly better than ZF soft information. In such scenarios, starting from ZF soft information, ORBGRAND-based turbo-GRAND can bridge the gap to the much more complex ML-detection-based soft-GRAND (this paper only covers uncorrelated point-to-point channels). In another scenario, under imperfect CSI, joint detection and decoding in turbo-GRAND outperforms conventional soft decoding. We assume $10\%$ CSI error in Fig. 2d, where $\mathbf{H}_{\text{err}}\!=\!0.9\mathbf{H}\!+\!0.1\tilde{\mathbf{H}}$, and $\tilde{\mathbf{H}}$ has the same distribution as $\mathbf{H}$ but is independently and randomly generated. Starting from ZF soft information as input LLRs, ORBGRAND-based turbo-GRAND outperforms both ML-soft- and ZF-soft-ORBGRAND. Note, however, that our ML-detection implementation in these simulations only undergoes an exhaustive search over subsets of symbols in $\mathbf{x}$ of size four.

We next analyze the complexity in terms of floating-point operations in complex multiplication ($\mathrm{CMT}$) and complex addition ($\mathrm{CAD}$). We compare the additional processing in turbo-GRAND over soft-GRAND to the complexity of soft-output ZF and ML detection. The search complexities are dominated by Euclidian distance computations and the complex matrix multiplications they entail. The complexity is exponential (in the symbol-vector length, $M$) with ML detection ((3) and (5)), polynomial with turbo-GRAND (6), and linear with ZF (4).

Table I illustrates the approximate worst-case complexity of generating soft information in one channel use. The average complexity of turbo-GRAND is much less because the guess budget, $B$, is not exploited on every iteration; with more iteration and higher SNR, a few or a single guess can recover a code-word. Turbo-GRAND is thus much less complex than conventional iterative list-based detection and decoding. Even with larger guess budgets, the recovered words on different iterations often overlap, and redundant computations can be saved. Furthermore, because noise-sequence guessing typically follows increasing Hamming weights, the vector Euclidean distance computations can reduce to simple symbol-based scalar distance computations/updates, resulting in an average linear turbo-GRAND complexity of $T\times B\left(M\mathrm{CMT}+M\mathrm{CAD}\right)$. Hence, for large modulation orders, a hardware-optimized turbo-GRAND can even prove to be less complex than soft-output ZF detection followed by soft-GRAND; much less complex than ML detection. Further simplifications can be made if the channel remains static over multiple uses.

We proposed a mechanism for using GRAND to extract soft information in a joint detection and decoding framework. By leveraging access to complex received symbols, hard demapped bits, CSI, and possibly noise statistics, we generate LLRs by populating a shortlist of Euclidean distance computations. Such LLRs can be used in subsequent soft-decoding GRAND iterations, giving rise to turbo-GRAND. Compared to hard GRAND, a few iterations of turbo-GRAND introduce an excess of $6\,\mathrm{dB}$ SNR gains at a BLER of $10^{-2}$ (much higher gains at lower BLERs), under practical communication system scenarios of Rayleigh fading channels. Furthermore, turbo-GRAND can match and even outperform exhaustive ML-detection-based soft-GRAND at a much-reduced average linear complexity. This work can extend into a generic joint detection and decoding framework for future investigations.