Source-linked AI summary
Ordered Reliability Bits Guessing Random Additive Noise Decoding
Ken R. Duffy
TL;DR
Short, high-rate codes are important for ultra-reliable low-latency communications, but accurate decoding is difficult across diverse code-books. The paper introduces ORBGRAND, which uses code-book-independent ranked soft information to order noise guesses in a parallelizable hardware-friendly decoder. It reports similar performance across BCH, CA-Polar, and random linear codes, with better BLER than CA-SCL for the evaluated shorter codes.
Problem
URLLC needs short, high-rate codes, motivating accurate universal decoders because conventional maximum-likelihood decoding of linear codes is computationally hard.
Method
ORBGRAND orders predetermined GRAND noise queries using code-book-independent quantized bit-reliability rankings while retaining parallelizable hardware implementation.
Results
ORBGRAND provides similar BLER across BCH, CA-Polar, and random linear codes, and better BLER than CA-SCL for the evaluated shorter codes.
Takeaways & Limitations
A single universal decoder can support diverse short, high-rate code-books while preserving low-complexity, hardware-oriented operation.
Abstract
from arXiv · showhide
Modern applications are driving demand for ultra-reliable low-latency communications, rekindling interest in the performance of short, high-rate error correcting codes. To that end, here we introduce a soft-detection variant of Guessing Random Additive Noise Decoding (GRAND) called Ordered Reliability Bits GRAND that can decode any short, high-rate block-code. For a code of $n$ bits, it avails of no more than $\lceil\log_2(n)\rceil$ bits of code-book-independent quantized soft detection information per received bit to determine an accurate decoding while retaining the original algorithm's suitability for a highly parallelized implementation in hardware. ORBGRAND is shown to provide similar block error performance for codes of distinct classes (BCH, CA-Polar and RLC) with low complexity, while providing better block error rate performance than CA-SCL, a state of the art soft detection CA-Polar decoder.
I. INTRODUCTION
Short, high-rate codes are attractive for URLLC but universal, accurate decoding remains difficult because maximum-likelihood decoding of linear codes is computationally hard. ORBGRAND is introduced as a soft-detection, code-book-independent decoder designed to retain GRAND’s parallel hardware implementation advantages.
- Motivation: Maximum-likelihood decoding is optimally accurate for uniform sources, but decoding linear codes by this method is NP-complete.This motivates practical approximate-ML decoders that exploit code structure or alternative universal procedures.
- Motivation: URLLC applications require short, high-rate codes, creating an opportunity for accurate universal decoders suited to hardware implementation.Such decoders could support a substantially broader range of code-books with one algorithmic instantiation.
- Existing approaches: GRAND decodes by querying the received sequence and successive noise-corrected sequences for code-book membership until a codeword is identified.Its code-book queries are naturally amenable to parallel circuit implementation.
- Existing approaches: Soft GRAND uses real-valued reliability information to produce soft-detection ML decoding, but its dynamic max-heap implementation is not well suited to hardware.SRGRAND preserves parallelizability while using only one reliability bit per demodulated symbol.
- Contribution: ORBGRAND uses code-book-independent quantized bit-reliability ordering to obtain SGRAND-like accuracy in an entirely parallelizable circuit-compatible algorithm.It provides ML decoding for a broad parametric class of bit-flip probability models and approximate-ML decoding otherwise.
II. ORDERED RELIABILITY BITS GRAND
ORBGRAND maps a fixed sequence of noise guesses onto received bits ordered by reliability, using Logistic Weight to approximate likelihood order. The resulting rank-based procedure supports soft decoding without requiring further channel information.
- Inputs and universality: ORBGRAND requires a code-book membership function, hard-demodulated bits, and a permutation ranking bit reliabilities from least to most reliable.It does not require additional information about the received signal or channel.
- Query construction: ORBGRAND creates predetermined base noise sequences and maps them to received-bit locations through the block’s reliability permutation.The first base position represents the least reliable bit, with reliability increasing by index.
- Query ordering: Logistic Weight orders putative noise sequences by summing the indices of their flipped bits rather than counting only the number of flips.This generalizes hard-detection Hamming-weight ordering using ranked soft information.
- Query ordering: The first 100 ORBGRAND queries enumerate noise patterns whose rows encode no flip as white and a flip as black.The displayed ordering assumes bit positions are arranged by decreasing a posteriori flip likelihood.
- Decoding guarantee: When the reliability model belongs to the supported parametric class, ORBGRAND provides soft maximum-likelihood decoding.The rank ordering need only be accurate enough to make the guessing order approximately maximum-likelihood.
III. PERFORMANCE EVALUATION
ORBGRAND is evaluated across BCH, CA-Polar, and RLC codes at two block lengths, measuring BLER and code-book-query complexity. It provides broadly code-book-independent performance, improves over CA-SCL for shorter codes, and supports decoding all considered block-codes.
- Evaluation setup: ORBGRAND is evaluated on BCH, CA-Polar, and RLC codes at rates near 0.7–0.83 and lengths 64–128 bits.The evaluations compare structured codes with random linear codes using the relevant hard- or soft-detection baselines.
- BLER performance: ORBGRAND provides effectively indistinguishable performance from BCH and CA-Polar for same-rate RLCs.A new random code can be used for each communication, while retaining comparable performance in the reported evaluation.
- Universality: ORBGRAND can decode all 28256 listed codes of length 128 or smaller, compared with 35 BCH and 196 CA-Polar codes in the stated comparison.The broader code coverage follows from its applicability across block-code constructions.
- Complexity: About 10^2 queries per bit or fewer suffice in typical regimes targeting BLER of 10^-3 or lower, with fewer than 5 for shorter codes.Queries serve as a complexity proxy and would be parallelized in hardware; the reported complexity is essentially code-book independent.
- BLER performance: 1 dB gain in BLER performance over CA-SCL is reported for n = 64 codes when ORBGRAND uses the 11-bit CRC for error correction.For these shorter codes, the BLER performance is essentially code-book independent.
- BLER performance: 22% of the evaluated RLCs outperform CA-Polar, while 50% achieve BLER within 10^-4 of CA-Polar at Eb/N0 = 4.5 dB.Figure 6 compares 500 individual RLCs, re-randomized RLCs, CA-Polar, and CA-SCL using BLER and average queries per bit.
IV. SUMMARY
ORBGRAND is a universal, hardware-suitable block decoder using code-book-independent quantized soft information. It improves BLER for short 5G NR CA-Polar codes and shows RLCs can match structured BCH and CA-Polar codes.
- ORBGRAND uses code-book-independent quantized soft information and is suitable for hardware implementation.
- ORBGRAND provides better BLER performance than a state-of-the-art soft-detection decoder for short 5G NR CA-Polar codes.
- RLCs offer essentially the same performance as highly structured BCH and CA-Polar codes.