Source-linked AI summary
Capacity-achieving Guessing Random Additive Noise Decoding (GRAND)
Ken R. Duffy, Jiange Li, Muriel Médard
TL;DR
The paper addresses the complexity of ML decoding for discrete channels, including channels with memory. It introduces GRAND, which guesses noise sequences in likelihood order, and GRANDAB, which stops after a fixed query threshold; both are capacity-achieving with uniform-at-random codebooks under the stated conditions.
Problem
ML decoding for random codebooks can require exponentially many computations, motivating a lower-complexity approach for discrete channels with or without memory.
Method
GRAND subtracts noise sequences from most likely to least likely until a codeword appears, while GRANDAB abandons after a fixed number of unsuccessful queries.
Results
GRAND and GRANDAB are capacity-achieving with uniform-at-random codebooks, with GRAND error and success exponents and GRANDAB complexity, error, and success exponents characterized.
Takeaways & Limitations
Noise-centric guessing applies directly to non-memoryless noise processes without interleaving, with analytic examples for bursty Markovian noise.
Abstract
from arXiv · showhide
We introduce a new algorithm for realizing Maximum Likelihood (ML) decoding in discrete channels with or without memory. In it, the receiver rank orders noise sequences from most likely to least likely. Subtracting noise from the received signal in that order, the first instance that results in a member of the code-book is the ML decoding. We name this algorithm GRAND for Guessing Random Additive Noise Decoding. We establish that GRAND is capacity-achieving when used with random code-books. For rates below capacity we identify error exponents, and for rates beyond capacity we identify success exponents. We determine the scheme's complexity in terms of the number of computations the receiver performs. For rates beyond capacity, this reveals thresholds for the number of guesses by which if a member of the code-book is identified it is likely to be the transmitted code-word. We introduce an approximate ML decoding scheme where the receiver abandons the search after a fixed number of queries, an approach we dub GRANDAB, for GRAND with ABandonment. While not an ML decoder, we establish that the algorithm GRANDAB is also capacity-achieving for an appropriate choice of abandonment threshold, and characterize its complexity, error and success exponents. Worked examples are presented for Markovian noise that indicate these decoding schemes substantially out-perform the brute force decoding approach.
I. INTRODUCTION
The paper introduces GRAND, which performs ML decoding by querying noise sequences from most to least likely until a codeword is found. It establishes capacity, exponent, and complexity results for GRAND and its bounded-search variant GRANDAB.
- Motivation: Conventional ML decoding appears costly because codebooks contain approximately |A|^nR codewords and require extensive likelihood computations or lookup-table construction.The paper frames GRAND as an alternative to these exponentially scaling approaches.
- GRAND: GRAND ranks noise sequences by likelihood, subtracts them sequentially from the received signal, and returns the first resulting codeword.For the stated invertible additive-noise channel model, this first codeword is the ML decoding.
- Results: Under mild ergodicity conditions and uniform-at-random codebooks, GRAND is capacity-achieving and its asymptotic complexity is characterized by receiver operations per block.The analysis also addresses error exponents below capacity and success exponents above capacity.
- GRANDAB: GRANDAB abandons decoding after a fixed number of unsuccessful noise queries, providing a complexity upper bound while remaining capacity-achieving for an appropriate threshold.The threshold can be set after querying the Shannon Typical Set of the noise, and the abandonment likelihood is characterized.
- Analysis: GRAND’s decoding is a race between guessing the true noise and encountering another codeword, yielding correct decoding when the true noise is guessed first.This argument recovers capacity for rates R < 1 − H and supplies error and success exponents around capacity.
II. RELATED WORK
The related-work discussion situates GRAND within guesswork, sequential decoding, approximate ML decoding, and random-code analyses. The paper emphasizes that its analysis applies to broader noise processes than memoryless channels and uses a distinct guesswork-based approach.
- Analytical foundations: Prior error-exponent analyses commonly use Sanov’s theorem and the method of types for IID or Markovian sources.The paper instead begins from a large-deviation principle for guesswork.
- Sequential decoding: Sequential decoding historically controls complexity through a computational cutoff rate, whereas GRAND analyzes noise-guessing complexity for random block codes.The comparison concerns different decoding settings and complexity strategies.
- Complexity comparisons: For linear block codes, a cited ML method has complexity bounded by 2^n(1−R), while GRANDAB has complexity 2^n(H+δ) for arbitrary δ > 0.The paper states GRANDAB is lower-complexity than that method for rates below capacity, except at low code rates where brute force can be preferable.
- Scope and results: The paper analyzes more general noise processes than DMCs, and for DMCs its derived error exponent matches Gallager’s result.It also derives success exponents for coding above capacity.
- Decoder distinctions: GRAND uses ordered noise statistics independently of decoder-output statistics, unlike Ordered Statistics Decoding and Turbo-style systems.The codebook is consulted only to test whether a noise-subtracted sequence is a codeword.
- Approximate decoding: GRANDAB resembles limited-search methods in convolutional-code decoding that stop exploration after restricting the search space.The paper distinguishes its analysis from those approaches by using guesswork results.
A. ML decoding by guesswork
The paper analyzes GRAND’s guesswork-based ML decoding through large-deviation behavior of the true noise and non-transmitted code-words. It establishes capacity behavior, error and success exponents, complexity laws, and early-termination correctness thresholds.
- Guesswork and code-word encounters: The noise guesswork process satisfies a large deviation principle with rate function I_N, whose unique zero is the Shannon entropy rate H.I_N(0) equals the min-entropy rate H_min, and the function is linear before becoming strictly convex under the stated conditions.
- Guesswork and code-word encounters: For uniformly random code-books, the first non-transmitted code-word is encountered after approximately |A|^n(1−R) guesses.The normalized guess count has an exponential approximation with rate |A|^−n(1−R), yielding mean |A|^n(1−R).
- Capacity and exponents: GRAND achieves capacity: below R < 1−H, decoding errors decay exponentially, while above capacity the error probability does not decay exponentially and correct decoding has a success exponent.The below-capacity error exponent is exact, and the above-capacity success exponent describes exponentially rare correct decodings.
- Capacity and exponents: The resulting error and success exponents are exact asymptotically and extend the linear-then-strictly-convex rate-function phenomenon beyond memoryless noise processes.For memoryless channels, the error exponent coincides with Gallager’s exponent.
- Complexity and beyond-capacity behavior: GRAND’s complexity obeys a large deviation principle, with the smaller of the true-noise and non-transmitted-code-word rate functions determining which decoding is encountered.Below capacity, the code-book curtails guesses of unlikely inputs; above capacity, the rate function can be non-convex.
- Complexity and beyond-capacity behavior: When 1−H < R < 1−H_min, sufficiently early termination can identify the transmitted code-word with probability converging to one despite the rate exceeding capacity.Theorem 3 gives the condition I_N(y) < I_U(y) and a threshold below |A|^n y queries for this behavior.
B. Approximate ML decoding with GRANDAB
GRANDAB approximates ML decoding by stopping noise queries after a fixed threshold, trading a controlled abandonment error floor for constrained complexity. It remains capacity-achieving below capacity when the threshold extends beyond the noise typical set, while above capacity it retains ML success behavior.
- B. Approximate ML decoding with GRANDAB: GRANDAB abandons decoding if no code-word is found after a predefined number of noise-removal queries.Unlike GRAND, it can terminate without returning a code-word.
- B. Approximate ML decoding with GRANDAB: For R > 1−H, GRANDAB has the same success probability as ML decoding.The above-capacity success exponent is therefore inherited from the ML analysis.
- B. Approximate ML decoding with GRANDAB: For R < 1−H, GRANDAB is capacity-achieving when abandonment occurs only after querying the typical noise set.Its error combines ML decoding errors with errors caused by premature abandonment.
- B. Approximate ML decoding with GRANDAB: GRANDAB errors arise from either an erroneous ML decoding or abandonment before a code-book element is identified.The more likely of these events determines the error rate.
- B. Approximate ML decoding with GRANDAB: Above capacity, querying to approximately |A|^ny* guesses is likely to preserve correct decoding before the threshold and likely to encounter an incorrect result afterward.The threshold is based on the maximum y satisfying Theorem 3's conditions.
IV. EXAMPLES
The examples evaluate GRAND and GRANDAB on Markovian binary noise, including memory and burstiness, using guess-based complexity and probability approximations. GRANDAB's abandonment threshold is selected numerically to constrain its error contribution relative to uncoded errors.
- IV. EXAMPLES: The examples use binary noise generated by a Markov chain, with the BSC recovered as a special parameterization.The second eigenvalue characterizes the source's burstiness, memory, or mixing.
- IV. EXAMPLES: Markovian noise has a Shannon entropy rate H computed from the stationary transition probabilities, while its rate function I_N is evaluated numerically.The required optimization is one-dimensional and concave.
- IV. EXAMPLES: Complexity is measured as the average number of noise guesses per received bit and compared with conditional-probability computations for direct ML decoding.The comparison treats one noise guess as one conditional-probability computation.
- IV. EXAMPLES: The GRANDAB parameter δ(n) is chosen so abandonment probability is no more than p_abandon times the expected uncoded block error probability.This sets an abandonment-induced block-error floor at a fraction of the uncoded block-error probability.
- IV. EXAMPLES: The examples treat 10^3–10^4 guesses per bit as a feasible complexity range, noting that noise guessing is readily parallelizable.The feasibility criterion is motivated by computation rates being several orders of magnitude greater than received bit rates.
A. Binary Symmetric Channel (BSC)
BSC experiments compare GRAND and GRANDAB with brute-force decoding across rates and block lengths. They show complexity reductions and near-capacity operation under specified block-error thresholds, while GRANDAB introduces an abandonment-related error floor.
- A. Binary Symmetric Channel (BSC): Brute-force ML complexity grows rapidly with code-book rate, whereas GRAND's complexity is evaluated through average noise guesses per received bit.The comparison uses BSC noise with p = 10^-4 in the reported experiment.
- A. Binary Symmetric Channel (BSC): GRANDAB's error curves are limited at lower rates by an abandonment-induced floor, while its higher-rate ML curves coincide with the ML behavior.The floor results from terminating the noise search before further guesses are made.
- A. Binary Symmetric Channel (BSC): 96.5% of capacity is achievable at n = 700 with block error probability below 10^-3 under a 10^3–10^4-guesses-per-bit complexity guideline.This selected block length is substantially smaller than 1/p = 10,000.
- A. Binary Symmetric Channel (BSC): Complexity changes slope at the cut-off rate and decreases beyond it for noise-guessing decoding, unlike the steep increase reported for sequential decoding of tree codes.The comparison concerns the rate dependence of decoding complexity.
- A. Binary Symmetric Channel (BSC): For p = 10^-2, selecting n = 75 allows rates up to 72.4% of capacity with block error probability no more than 10^-2 under the stated complexity range.Higher noise probability makes GRANDAB truncation relevant at smaller block lengths.
B. Bursty Markovian noise
The paper extends its examples to highly bursty Markovian noise without interleaving. GRANDAB reduces complexity for large blocks, while selected block lengths still achieve substantial fractions of capacity under block-error constraints.
- B. Bursty Markovian noise: GRAND and GRANDAB apply to correlated noise without interleaving or other memory-alleviation methods.This is presented as a core feature of the schemes.
- B. Bursty Markovian noise: The p = 10^-4 Markovian example uses a highly bursty source whose conditional flip likelihood after a flip is 3 orders of magnitude higher.Its long-run average bit-error probability matches the BSC comparison.
- B. Bursty Markovian noise: For the p = 10^-2 noisy Markovian channel, selecting n = 75 provides 71.2% of capacity at a block-error threshold of 10^-2.GRANDAB reduces algorithmic complexity while introducing an error floor.
- B. Bursty Markovian noise: Across the presented examples, the best block lengths are no larger than the reciprocal bit-error rate, 1/p.The paper describes this repeatedly observed behavior as desirable for the scheme.
C. Finer approximations for the BSC
For the BSC, the paper derives a finer approximation to block-error probability using the distribution of guesses until a non-transmitted code-word is identified. This approximation is evaluated against GRAND and GRANDAB examples and agrees well with the asymptotic analysis.
- The approximation uses a refined distribution for the number of guesses until a non-transmitted code-word is identified.
- Fig. 6 examines BSC GRAND and GRANDAB at bit flip probability p = 10−2 with a block-error probability floor of 10−2.
- For a BSC, the finer block-error approximation reduces computation to a sum of n+1 terms.
- Fig. 9 reports a true block-error probability of 3×10−3 when the asymptotic target was 10−2.
- Across examined cases, the asymptotic results compare well with more precise computations that may permit higher rates while meeting block-error targets.
V. DISCUSSION AND CONCLUSIONS
The discussion concludes that GRAND and GRANDAB provide capacity-achieving noise-guessing decoders for broad noise processes, with GRANDAB offering bounded computation through abandonment. The paper also identifies implementation constraints for random code-books and scope boundaries for the current hard-detection setting.
- GRAND performs ML decoding by testing code-book membership after subtracting noise sequences in decreasing likelihood order.
- GRANDAB remains capacity-achieving with uniform-at-random code-books while limiting queries through an entropy-based abandonment threshold.
- The schemes apply directly to correlated noise without interleaving, and their execution depends on noise structure rather than code-book construction.
- For both algorithms, the paper provides asymptotic query complexity results, with complexity decreasing as code-book rate increases.
- Random code-books require substantial memory for large block lengths, although encoding and information-word conversion can have linear complexity.
- The current work treats only hard detection with discrete decoder inputs; extensions to other settings remain future work.