pith. sign in

arxiv: 2512.00347 · v4 · submitted 2025-11-29 · 💻 cs.IT · math.IT

ORBGRAND Is Exactly Capacity-achieving via Rank Companding

Zhuang Li , Wenyi Zhang This is my paper

Pith reviewed 2026-05-17 03:53 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords ORBGRANDCDF-ORBGRANDrank compandingsymmetric capacitymutual informationbinary-input memoryless channelsBICM capacityguessing-based decoding
0
0 comments X

The pith

By companding ranks in ORBGRAND with the inverse CDF of channel reliability, CDF-ORBGRAND exactly achieves the symmetric capacity for binary-input memoryless channels under symmetric inputs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that a simple transformation of the rank ordering in ORBGRAND produces an algorithm that reaches the exact mutual information of the channel. For any binary-input memoryless channel with symmetric input distribution, mapping the reliability ranks through the inverse cumulative distribution function converts the guessing sequence into one whose success probability matches the information-theoretic limit. The same construction is then applied to bit-interleaved coded modulation, where it is shown to attain the BICM capacity even after accounting for the mismatch introduced by treating the bits as independent parallel channels. A reader cares because the result supplies a concrete, implementable decoder that provably saturates the symmetric capacity rather than merely approaching it.

Core claim

Via suitably companding the ranks in ORBGRAND according to the inverse cumulative distribution function (CDF) of channel reliability, the resulting CDF-ORBGRAND algorithm exactly achieves the mutual information, i.e., the symmetric capacity. This result is then applied to bit-interleaved coded modulation (BICM) systems to handle high-order input constellations, showing that CDF-ORBGRAND achieves the BICM capacity after considering mismatched decoding effects.

What carries the argument

Rank companding by the inverse CDF of channel reliability, which reorders the guessing list in ORBGRAND so that the probability of each guess aligns with the channel's reliability distribution.

If this is right

  • CDF-ORBGRAND reaches the symmetric capacity exactly rather than only approximately for any binary-input memoryless channel under symmetric signaling.
  • In BICM systems the same construction achieves the BICM capacity after mismatch from independent bit decoding is included.
  • Guessing-based decoders can be turned into capacity-achieving schemes by a single monotonic transformation of the reliability ranks.
  • The approach separates the ordering of guesses from the underlying channel statistics in a way that preserves the mutual-information limit.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar inverse-CDF mappings may convert other ordered-reliability decoders into exact capacity achievers for the same channel class.
  • Hardware implementations could exploit the fact that the companding step is a fixed lookup table once the channel is known.
  • The construction invites direct comparison with polar or LDPC constructions on the same channels to test whether the guessing overhead remains competitive at finite length.

Load-bearing premise

The exact capacity achievement requires a general binary-input memoryless channel and a symmetric input distribution; deviation from either condition removes the guarantee.

What would settle it

Compute the mutual information for a concrete binary-input memoryless channel with symmetric inputs, run CDF-ORBGRAND at that rate, and check whether the block error rate tends to zero as block length grows; any persistent gap would falsify the exact-achievement claim.

Figures

Figures reproduced from arXiv: 2512.00347 by Wenyi Zhang, Zhuang Li.

Figure 1
Figure 1. Figure 1: Comparison between IORB and ICDF-ORB under AWGN, AWLN, and Rayleigh fading channels. Since Rayleigh fading channels are described in complex baseband, the SNR is defined as the effective per-dimension SNR, corresponding to the in-phase component of the received signal. error probability of decoding, which, for the i.i.d. random coding ensemble in our system model, is equivalent to the error probability of … view at source ↗
Figure 2
Figure 2. Figure 2: Parallel channel model of BICM with ideal interleaving. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Gray (left) and SP (right) labelings for 16QAM. Here [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Achievable rates of ORBGRAND, CDF-ORBGRAND, and BICM capacity for QPSK, 8PSK, and 16QAM over Rayleigh fading channel with perfect [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
read the original abstract

Within the family of guessing-based decoding algorithms, ordered reliability bits GRAND (ORBGRAND) has attracted considerable attention due to its efficient use of soft information and suitability for hardware implementation. It has also been shown that ORBGRAND achieves a rate very close to the capacity of an additive white Gaussian noise channel under antipodal signaling. In this work, it is further established that, for general binary-input memoryless channels under symmetric input distribution, via suitably companding the ranks in ORBGRAND according to the inverse cumulative distribution function (CDF) of channel reliability, the resulting CDF-ORBGRAND algorithm exactly achieves the mutual information, i.e., the symmetric capacity. This result is then applied to bit-interleaved coded modulation (BICM) systems to handle high-order input constellations. Via considering the effects of mismatched decoding due to both BICM and ORBGRAND, it is shown that CDF-ORBGRAND is capable of achieving the BICM capacity, which was initially derived in the literature by treating BICM as a set of independent parallel channels.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces CDF-ORBGRAND, a variant of ordered reliability bits GRAND (ORBGRAND) in which integer ranks are companded by the inverse CDF of the per-symbol channel reliability distribution. For general binary-input memoryless channels with symmetric input distribution, the authors claim that this procedure yields a guessing order whose cumulative probability mass exactly equals the symmetric capacity (mutual information). The result is then extended to bit-interleaved coded modulation (BICM), where CDF-ORBGRAND is shown to achieve the BICM capacity despite the mismatch introduced by both the BICM demapper and the GRAND-style decoder.

Significance. If the central claim is correct, the work supplies a rare example of a practical, list-based soft decoder that is provably capacity-achieving rather than merely capacity-approaching. The explicit construction via rank companding also furnishes a concrete link between the order statistics of reliability and the information-theoretic bound, which could guide the design of other guessing decoders. The BICM extension further demonstrates that the same technique recovers the BICM capacity under the standard mismatched-decoding analysis.

major comments (2)
  1. [§3] §3 (or the section containing the main theorem): the argument that marginal inverse-CDF companding of per-bit ranks produces a global ordering whose cumulative mass equals the symmetric capacity appears to rely on the companded ranks being equivalent to sorting by the joint likelihood of the noise vector. The manuscript does not explicitly address whether the joint distribution of the companded ranks coincides with the joint likelihood ordering when the underlying reliability random variables are dependent across positions (as they are under a fixed codeword length). A concrete counter-example or a proof step showing that the marginal transform preserves the required order statistics would strengthen the claim.
  2. [Theorem 1] Theorem 1 (or the statement of exact capacity achievement): the derivation assumes a symmetric input distribution and memoryless channel. It is not immediately clear how the same companding rule extends when the input distribution is asymmetric or when the channel has memory; the manuscript should state whether the exact equality continues to hold or whether only an approximation is obtained.
minor comments (2)
  1. [§2] The notation for the companded rank variable (e.g., R' versus R_cdf) is introduced without a dedicated definition paragraph; adding an explicit equation would improve readability.
  2. [Figure 2] Figure 2 (BICM capacity curves) lacks error bars or confidence intervals on the simulated points; including them would make the closeness to the theoretical BICM capacity easier to assess.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the major points below and will incorporate clarifications into the revised manuscript.

read point-by-point responses

  1. Referee: [§3] the argument that marginal inverse-CDF companding of per-bit ranks produces a global ordering whose cumulative mass equals the symmetric capacity appears to rely on the companded ranks being equivalent to sorting by the joint likelihood of the noise vector. The manuscript does not explicitly address whether the joint distribution of the companded ranks coincides with the joint likelihood ordering when the underlying reliability random variables are dependent across positions (as they are under a fixed codeword length).

    Authors: We appreciate this observation. Because the channel is memoryless, the per-position reliability random variables are conditionally independent given any fixed codeword; the fixed block length does not introduce statistical dependence among the channel outputs. Consequently the joint likelihood factors into the product of marginals, and the marginal inverse-CDF companding applied to each rank preserves equivalence to the joint-likelihood ordering. We will add an explicit paragraph in Section 3 stating this independence and the resulting preservation of order statistics. revision: yes

  2. Referee: [Theorem 1] the derivation assumes a symmetric input distribution and memoryless channel. It is not immediately clear how the same companding rule extends when the input distribution is asymmetric or when the channel has memory; the manuscript should state whether the exact equality continues to hold or whether only an approximation is obtained.

    Authors: Theorem 1 is proved under the stated assumptions of symmetric inputs and memoryless channels, which define the symmetric capacity. For asymmetric input distributions or channels with memory the exact equality to capacity does not hold in general; the CDF-ORBGRAND ordering then yields only an approximation to the optimal guessing sequence. We will revise the statement of Theorem 1 and the surrounding discussion to make this scope explicit and to note that extensions beyond these conditions are not claimed to be exact. revision: yes

Circularity Check

0 steps flagged

Derivation self-contained; no reduction to inputs by construction

full rationale

The paper derives that CDF-ORBGRAND achieves symmetric capacity exactly by companding ORBGRAND ranks with the inverse CDF of marginal channel reliability for binary-input memoryless channels under symmetric inputs, then extends the result to BICM capacity. No quoted equation or step in the abstract or context reduces a claimed prediction to a fitted parameter, self-citation chain, or definitional equivalence. The central claim rests on information-theoretic definitions and channel statistics rather than renaming known results or smuggling ansatzes via prior self-work. The derivation is therefore treated as independent and externally falsifiable against mutual information bounds.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard definitions of mutual information and CDF for memoryless channels plus the assumption of symmetric inputs; no free parameters or new invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Channel is binary-input memoryless with symmetric input distribution
    Explicitly required for the exact capacity result to hold, as stated in the abstract.
  • standard math Mutual information equals symmetric capacity under the given conditions
    Standard information theory identity invoked to equate the achieved rate with capacity.

pith-pipeline@v0.9.0 · 5480 in / 1260 out tokens · 54357 ms · 2026-05-17T03:53:30.601518+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Capacity-achieving guessing random additive noise decoding,

    K. R. Duffy, J. Li, and M. M ´edard, “Capacity-achieving guessing random additive noise decoding,”IEEE Trans. Inf. Theory, vol. 65, no. 7, pp. 4023–4040, 2019

    work page 2019

  2. [2]

    A universal maximum likelihood GRAND decoder in 40nm CMOS,

    A. Riaz, M. Medard, K. R. Duffy, and R. T. Yazicigil, “A universal maximum likelihood GRAND decoder in 40nm CMOS,” inProc. 14th Int. Conf. on Commun. Syst. NETw. (COMSNETS), 2022, pp. 421–423

    work page 2022

  3. [3]

    Guess- ing decoding of short blocklength codes,

    Q. Wang, J. Liang, P. Yuan, K. R. Duffy, M. M´edard, and X. Ma, “Guess- ing decoding of short blocklength codes,”2025, arxiv:2511.12108

    work page arXiv 2025

  4. [4]

    Lin and D

    S. Lin and D. J. Costello,Error Control Coding, 2nd ed.Pearson, 2004

    work page 2004

  5. [5]

    Guessing random additive noise decoding with symbol reliability information (SRGRAND),

    K. R. Duffy, M. M ´edard, and W. An, “Guessing random additive noise decoding with symbol reliability information (SRGRAND),”IEEE Trans. Commun., vol. 70, no. 1, pp. 3–18, 2021

    work page 2021

  6. [6]

    Soft maximum likelihood decoding using GRAND,

    A. Solomon, K. R. Duffy, and M. M ´edard, “Soft maximum likelihood decoding using GRAND,” inProc. IEEE Int. Conf. Commun. (ICC), 2020, pp. 1–6

    work page 2020

  7. [7]

    Ordered reliability bits guessing random additive noise decoding,

    K. R. Duffy, W. An, and M. M ´edard, “Ordered reliability bits guessing random additive noise decoding,”IEEE Trans. Signal Process., vol. 70, pp. 4528–4542, 2022

    work page 2022

  8. [8]

    High-performance low-complexity error pattern generation for ORBGRAND decoding,

    C. Condo, V . Bioglio, and I. Land, “High-performance low-complexity error pattern generation for ORBGRAND decoding,” inProc. IEEE Globecom Workshops, 2021, pp. 1–6

    work page 2021

  9. [9]

    High-throughput and energy-efficient VLSI architecture for ordered reliability bits GRAND,

    S. M. Abbas, T. Tonnellier, F. Ercan, M. Jalaleddine, and W. J. Gross, “High-throughput and energy-efficient VLSI architecture for ordered reliability bits GRAND,”IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 30, no. 6, pp. 681–693, 2022

    work page 2022

  10. [10]

    A fixed latency ORBGRAND decoder architecture with LUT-aided error-pattern scheduling,

    C. Condo, “A fixed latency ORBGRAND decoder architecture with LUT-aided error-pattern scheduling,”IEEE Trans. Circuits Sys. I: Reg. Papers, vol. 69, no. 5, pp. 2203–2211, 2022

    work page 2022

  11. [11]

    ORBGRAND is almost capacity-achieving,

    M. Liu, Y . Wei, Z. Chen, and W. Zhang, “ORBGRAND is almost capacity-achieving,”IEEE Trans. Inf. Theory, vol. 69, no. 5, pp. 2830– 2840, 2022

    work page 2022

  12. [12]

    GRAND for fading chan- nels using pseudo-soft information,

    H. Sarieddeen, M. M ´edard, and K. R. Duffy, “GRAND for fading chan- nels using pseudo-soft information,” inProc. IEEE Global Commun. Conf. (GLOBECOM), 2022, pp. 3502–3507

    work page 2022

  13. [13]

    GRAND for Rayleigh fading channels,

    S. M. Abbas, M. Jalaleddine, and W. J. Gross, “GRAND for Rayleigh fading channels,” inProc. IEEE Globecom Workshops, 2022, pp. 504– 509

    work page 2022

  14. [14]

    Hardware architecture for fading-GRAND,

    S. M. Abbas, M. Jalaleddine, and W. J. Gross, “Hardware architecture for fading-GRAND,” inGuessing Random Additive Noise Decoding: A Hardware Perspective. Springer, 2023, pp. 125–140

    work page 2023

  15. [15]

    Symbol-level GRAND for high- order modulation over block fading channels,

    I. Chatzigeorgiou and F. A. Monteiro, “Symbol-level GRAND for high- order modulation over block fading channels,”IEEE Commun. Lett., vol. 27, no. 2, pp. 447–451, 2022

    work page 2022

  16. [16]

    URLLC with coded massive MIMO via random linear codes and GRAND,

    S. Allahkaram, F. A. Monteiro, and I. Chatzigeorgiou, “URLLC with coded massive MIMO via random linear codes and GRAND,” inProc. IEEE 96th Veh. Technol. Conf. (VTC-Fall), 2022, pp. 1–5

    work page 2022

  17. [17]

    Symbol-level noise-guessing decoding with antenna sorting for URLLC massive MIMO,

    S. Allahkaram, F. A. Monteiro, and I. Chatzigeorgiou, “Symbol-level noise-guessing decoding with antenna sorting for URLLC massive MIMO,”2023, arXiv:2305.13113

    work page arXiv 2023

  18. [18]

    Approaching maximum likelihood decoding performance via reshuffling ORBGRAND,

    L. Wan and W. Zhang, “Approaching maximum likelihood decoding performance via reshuffling ORBGRAND,” inProc. IEEE Int. Symp. Inf. Theory (ISIT), 2024, pp. 31–36

    work page 2024

  19. [19]

    Fine-tuning ORBGRAND with very few channel soft values,

    L. Wan, H. Yin, and W. Zhang, “Fine-tuning ORBGRAND with very few channel soft values,” inProc. IEEE/CIC Int. Conf. Commun. in China (ICCC Workshops), 2025, pp. 1–6

    work page 2025

  20. [20]

    Bit-interleaved coded modula- tion,

    G. Caire, G. Taricco, and E. Biglieri, “Bit-interleaved coded modula- tion,”IEEE Trans. Inf. Theory, vol. 44, no. 3, pp. 927–946, 1998

    work page 1998

  21. [21]

    Bit-interleaved coded modulation,

    A. G. i Fabregas, A. Martinez, and G. Caire, “Bit-interleaved coded modulation,”Found. Trends® Commun. Inf. Theory, vol. 5, no. 1–2, pp. 1–153, 2008

    work page 2008

  22. [22]

    Bit- interleaved coded modulation revisited: A mismatched decoding per- spective,

    A. Martinez, A. G. i Fabregas, G. Caire, and F. M. Willems, “Bit- interleaved coded modulation revisited: A mismatched decoding per- spective,”IEEE Trans. Inf. Theory, vol. 55, no. 6, pp. 2756–2765, 2009

    work page 2009

  23. [23]

    Mismatched decoding revisited: General alphabets, channels with memory, and the wide-band limit,

    A. Ganti, A. Lapidoth, and I. E. Telatar, “Mismatched decoding revisited: General alphabets, channels with memory, and the wide-band limit,” IEEE Trans. Inf. Theory, vol. 46, no. 7, pp. 2315–2328, 2000

    work page 2000

  24. [24]

    Fading channels: how perfect need ’perfect side information’ be?

    A. Lapidoth and S. Shamai, “Fading channels: how perfect need ’perfect side information’ be?”IEEE Trans. Inf. Theory, vol. 48, no. 5, pp. 1118– 1134, 2002

    work page 2002

  25. [25]

    ORBGRAND: Achievable rate for general bit channels and application in BICM,

    Z. Li and W. Zhang, “ORBGRAND: Achievable rate for general bit channels and application in BICM,” inProc. IEEE Int. Symp. Pers., Ind., Mobile Radio Commun., 2024, pp. 1–7

    work page 2024

  26. [26]

    Gaussian codes and weighted nearest neighbor decoding in fading multiple-antenna channels,

    H. Weingarten, Y . Steinberg, and S. Shamai (Shitz), “Gaussian codes and weighted nearest neighbor decoding in fading multiple-antenna channels,”IEEE Trans. Inf. Theory, vol. 50, no. 8, pp. 1665–1686, 2004

    work page 2004

  27. [27]

    8-PSK trellis codes for a Rayleigh channel,

    E. Zehavi, “8-PSK trellis codes for a Rayleigh channel,”IEEE Trans. Commun., vol. 40, no. 5, pp. 873–884, 1992

    work page 1992