Pith. sign in

REVIEW 2 major objections 4 minor 40 references

Density Evolution of Soft-Decision Collapsed Projection-Aggregation Decoding for Reed-Muller Codes over the BIAWGN Channel

T0 review · 2 major / 4 minor · reviewed 2026-07-13 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Soft-decision collapsed projection-aggregation decoding of Reed-Muller codes has a density-evolution model that shows vanishing error at vanishing rate.

desk verdict First soft DE treatment of CPA for RM codes; clean exact-marginal/symmetry proofs, but the vanishing-rate asymptotic rests on an independence assumption the authors already flag as imperfect at finite length. read the letter →

arxiv 2607.09602 v1 pith:MTNVQIJH submitted 2026-07-10 cs.IT math.IT

Jiajie Li , Marvin Rübenacke , Warren J. Gross This is my paper · ORCID
classification cs.ITmath.IT MSC 94B3594B70
keywords Reed-Mullercodescollapsedprojection-aggregationdensityevolutionsoft-decisiondecodingBIAWGNchannelasymptoticanalysisexactmarginals
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Reed-Muller codes are known to achieve capacity on several channels, and collapsed projection-aggregation (CPA) decoding has already been observed to come close to maximum-likelihood performance in practice. This paper supplies the first soft-decision density-evolution analysis of CPA over the binary-input AWGN channel. The authors first prove that each iteration of CPA recovers an exact marginal probability and that the decoder is symmetric, so the usual all-zero-codeword assumption is valid. They then build an approximate density-evolution recursion by replacing soft projection and fast-Hadamard decoding with hard-decision counterparts, track the resulting Gaussian means and variances, and show that both quantities collapse rapidly. The same recursion yields an asymptotic statement: when the code rate itself vanishes, the bit-error probability under CPA also vanishes. The analysis therefore supplies both a qualitative explanation for the decoder’s fast convergence and a first rigorous regime in which soft CPA succeeds.

What carries the argument

Density evolution for CPA: after proving exact-marginal and symmetry properties, the authors replace soft projection/FHT by hard-decision counterparts, obtain a Gaussian density for the aggregated LLR via the central-limit theorem, and iterate the resulting mean-and-variance recursion.

What would settle it

Run the density-evolution recursion and the actual soft CPA decoder on a sequence of RM codes whose rates tend to zero (fixed order, growing length) and check whether both the predicted and the observed bit-error rates tend to zero at the same noise levels.

Watch

Extended reading notes

Core claim

Soft-decision CPA decoding of Reed-Muller codes returns exact marginals, is symmetric, and admits a density-evolution model (under hard-decision approximations of projection and FHT) whose asymptotic analysis proves that the decoder achieves vanishing error probability whenever the code rate vanishes.

Load-bearing premise

The analysis treats the messages returned by the different subspaces as independent so that the central-limit theorem can be applied; the paper itself notes that finite-length dependence inflates the true variance.

Editorial extensions

If this is right

  • The same density-evolution framework can be used to design reduced-complexity soft PA variants by pruning subspaces while still guaranteeing the mean/variance collapse.
  • Because CPA recovers exact marginals, broadcast (rather than extrinsic) updates are information-theoretically justified and can replace more expensive extrinsic schedules.
  • The vanishing-rate success region supplies a concrete asymptotic benchmark against which future soft RM decoders can be compared.
  • The rapid collapse of both mean and variance explains the empirically observed early-stopping behaviour of CPA and can guide threshold design.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If a refined analysis that accounts for subspace dependence can restore a usable finite-length error bound, the same density-evolution engine would immediately yield concrete design rules for practical code lengths.
  • The exact-marginal property suggests that CPA can be viewed as a special case of belief propagation on a highly structured factor graph; tools from the BP literature may therefore transfer directly.
  • Extending the hard-decision approximation of the FHT step to a soft Gaussian approximation would tighten the mean lower bound and possibly enlarge the asymptotic success region beyond vanishing rate.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper analyzes soft-decision collapsed projection-aggregation (CPA) decoding of Reed-Muller codes over the BIAWGN channel. It proves that CPA recovers the exact marginal probability of each bit (Proposition 1 and the derivation leading to Eq. (13)) and is symmetric with respect to the transmitted codeword (Lemma 1 and Proposition 2). From these properties a density-evolution model is constructed; the projection and FHT steps are replaced by hard-decision BSC approximations (Eqs. (31)–(33)), the aggregation messages are bounded by mean μ′ and variance (σ′)² (Eqs. (45)–(46)), and the average over n_B subspaces is treated as Gaussian by the central-limit theorem under an independence assumption (Eqs. (47)–(51)). Numerical histograms for RM(7,3) and RM(8,3) show that the model qualitatively tracks the rapid collapse of mean and variance. An asymptotic argument then claims that, for vanishing-rate RM codes (r finite), one-iteration CPA yields vanishing bit-error probability once n_B→∞ (Proposition 3 and the final paragraph of Section V).

Significance. Exact-marginal and symmetry proofs for soft CPA fill a documented gap left by earlier hard-decision analyses of RPA/CPA. The density-evolution construction is the first attempt to track soft-message densities for this decoder family and correctly identifies the mean/variance collapse that underlies the observed fast convergence. The asymptotic vanishing-error claim for vanishing-rate codes is of genuine interest if it can be made rigorous, because it would place soft CPA on the same theoretical footing as the hard-decision results of [16], [17]. The paper is therefore a useful first step, even though the quantitative DE bounds remain loose and the asymptotic step rests on an unproven independence limit.

major comments (2)
  1. The asymptotic vanishing-error claim (Section V, final paragraph) rests on the CLT representation (Eqs. (47)–(51)) that treats the n_B subspace messages as independent, so that Var[¯l]=Var[u]/n_B. The manuscript itself records (p. 13) that finite-length dependence inflates the true variance and renders the error-probability bound (52) unusable. No argument is supplied that residual dependence vanishes as m→∞ (or that a CLT still holds under the residual dependence). Without such an argument the step “n_B→∞ ⇒ variance→0 ⇒ error→0” is incomplete; the claim therefore needs either a rigorous independence proof or a weaker statement that does not rely on the CLT variance formula.
  2. The hard-decision approximation of FHT (Eqs. (31)–(33)) produces only an upper bound on the true soft-FHT error rate. While this is acknowledged, the subsequent mean lower bound μ′ and variance upper bound (σ′)² (Eqs. (45)–(46)) inherit the same looseness. Because these bounds are fed directly into the asymptotic analysis of Section V, the paper should either quantify the gap between hard-decision and soft FHT for order-1 RM codes or replace the hard-decision step by a soft analysis that still yields a positive mean and bounded variance.
minor comments (4)
  1. Figures 1–4 would be clearer if the empirical histograms and the DE Gaussians were overlaid on the same axes rather than plotted separately.
  2. Notation for the projected LLR (l/B_i versus l/1) is inconsistent between Sections II and III; a single convention would help the reader.
  3. The early-stopping threshold θ is mentioned but never given a numerical value in the simulation captions; adding it would improve reproducibility.
  4. A few typographical slips remain (e.g., “thistanh” on p. 4, missing spaces around operators).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: exact-marginal and symmetry proofs are self-contained first-principles arguments; density evolution and the vanishing-error asymptotic follow from those plus explicit hard-decision approximations, binomial identities, and CLT under an independence assumption that is stated (not smuggled).

full rationale

The paper's derivation chain begins with two proved properties (exact recovery of the marginal via the projection-aggregation steps, eqs. 7-13 and Prop. 1; symmetry via the ML-metric argument of Lemma 1 and Prop. 2) that do not presuppose the later density-evolution conclusions. The density-evolution model of Section IV is then obtained by (i) replacing soft FHT with a hard-decision BSC approximation whose crossover probability is the ordinary Gaussian tail (eqs. 31-33), (ii) writing the aggregation output as a signed product whose mean and variance are bounded by the success probability of that hard decoder (eqs. 45-46), and (iii) invoking the classical CLT under an explicit independence assumption among the n_B subspace messages (eqs. 47-51). The asymptotic claim of Section V simply feeds the same one-iteration model into standard binomial-to-Gaussian limits and the growth of the Gaussian binomial coefficient (Prop. 3); no parameter is fitted to data and then re-used as a 'prediction,' no uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled via self-citation. The independence assumption is acknowledged by the paper itself to be imperfect at finite length, but that is a modelling gap, not a circular reduction of the claimed result to its own inputs. Consequently the analysis is non-circular.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The central asymptotic claim rests on standard coding-theory facts (BMS symmetry, binomial theorem, CLT, known hard-decision RM decoding radius) plus three modeling approximations introduced by the authors (hard-decision projection, hard-decision FHT success probability, subspace independence). No free parameters are fitted; the only invented modeling objects are the mean/variance bounds μ' and (σ')^{2}.

assumptions (4)
  • domain assumption BIAWGN channel is BMS, so all-zero codeword may be assumed once symmetry is proved (Def. 1, Prop. 2).
    Standard for density evolution; invoked throughout Sections III-V.
  • domain assumption Hard-decision decoding of order-1 RM codes corrects up to n/2-1 errors with high probability when r=o(√m) (Saptharishi et al.).
    Used to upper-bound FHT error probability (Eq. 33); the paper notes this is only an upper bound on true soft FHT performance.
  • ad hoc to paper Messages from distinct subspaces are independent, permitting CLT for the average (Eq. 47).
    Explicit modeling choice; authors later observe that dependence inflates empirical variance.
  • standard math Projection of soft LLRs onto an (r-1)-dimensional coset equals the LLR of the parity of the bits in that coset (Prop. 1).
    Follows from the box-plus identity and induction; proved in the paper.
invented entities (1)
  • Mean/variance bounds μ' and (σ')^{2} for the aggregated message u
    purpose: Replace the intractable soft-FHT density by analytically tractable lower/upper bounds that still permit a Gaussian DE recursion.
    Defined in Eqs. (45)-(46); they are not physical objects but analysis artifacts whose tightness is only checked numerically.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Density Evolution of Soft-Decision Collapsed Projection-Aggregation Decoding for Reed-Muller Codes over the BIAWGN Channel." pith.science (2026). https://pith.science/paper/MTNVQIJH

@misc{pith2026260709602,
  author       = {Pith},
  title        = {Pith review of: Density Evolution of Soft-Decision Collapsed Projection-Aggregation Decoding for Reed-Muller Codes over the BIAWGN Channel},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MTNVQIJH}},
  note         = {Machine review of arXiv:2607.09602}
}
read the original abstract

Reed-Muller (RM) codes have been shown to achieve capacity over a range of channels, and recently proposed projection-aggregation (PA) decoding has been experimentally shown to achieve near-maximum-likelihood decoding performance. These recent achievements motivate theoretical research on PA decoding. In this work, we analyze the density function of the soft output from collapsed projection-aggregation (CPA) decoding for RM codes over the binary-input additive white Gaussian noise (BIAWGN) channel. We prove that soft-decision CPA decoding returns an exact marginal probability and is symmetric. Based on the analysis, we build a density evolution model for CPA decoding. To simplify the density evolution, we approximate the projection and the fast Hadamard transform decoding using hard-decision decoding. Simulation results over the BIAWGN channel show that our proposed density evolution model captures the fast reduction in the mean and the variance of the soft information returned from the CPA decoding, which qualitatively explains the decoding mechanism and the fast convergence speed of the CPA decoding. We perform an asymptotic analysis based on the proposed density evolution, and we show that CPA decoding can achieve a vanishing error probability for RM codes with a vanishing code rate.

Figures

Figures reproduced from arXiv: 2607.09602 by the authors.

Figure 1
Figure 1. Histogram of LLRs from the channel and every iteration of the PCPA decoding for the RM [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
Figure 2
Figure 2. Density functions (sim.) of the output from the PCPA decoding over [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Histogram of LLRs from the channel and every iteration of the PCPA decoding for the RM [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Density functions (sim.) of the output from the PCPA decoding over [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 2 linked inside Pith

  1. [16]

    An upper bound on the error probability of RPA decoding of Reed-Muller codes over the BSC,

    V . A. Rameshwar and V . Lalitha, “An upper bound on the error probability of RPA decoding of Reed-Muller codes over the BSC,” inIEEE International Symposium on Information Theory (ISIT), 2025, pp. 1–6

    2025

  2. [17]

    On the error probability of RPA decoding of Reed-Muller codes over BMS channels,

    D. Fathollahi, V . A. Rameshwar, and V . Lalitha, “On the error probability of RPA decoding of Reed-Muller codes over BMS channels,”arXiv preprint arXiv:2601.09581, 2026

    arXiv 2026

  3. [1]

    Application of boolean algebra to switching circuit design and to error detection,

    D. E. Muller, “Application of boolean algebra to switching circuit design and to error detection,”Trans. of the I.R.E. Professional Group on Electronic Computers, vol. EC-3, no. 3, pp. 6–12, 1954

    1954

  4. [2]

    Reed–Muller codes achieve capacity on erasure channels,

    S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. S ¸as ¸o ˇglu, and R. L. Urbanke, “Reed–Muller codes achieve capacity on erasure channels,”IEEE Trans. Inform. Theory, vol. 63, no. 7, pp. 4298–4316, 2017

    2017

  5. [3]

    Reed–Muller codes for random erasures and errors,

    E. Abbe, A. Shpilka, and A. Wigderson, “Reed–Muller codes for random erasures and errors,”IEEE Trans. Inform. Theory, vol. 61, no. 10, pp. 5229–5252, 2015

    2015

  6. [4]

    On the performance of Reed-Muller codes with respect to random errors and erasures,

    O. Sberlo and A. Shpilka, “On the performance of Reed-Muller codes with respect to random errors and erasures,” inProc. of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, ser. SODA ’20. USA: Society for Industrial and Applied Mathematics, 2020, p. 1357–1376

    2020

  7. [5]

    Reed–Muller codes on BMS channels achieve vanishing bit-error probability for all rates below capacity,

    G. Reeves and H. D. Pfister, “Reed–Muller codes on BMS channels achieve vanishing bit-error probability for all rates below capacity,”IEEE Trans. Inform. Theory, pp. 1–1, 2023

    2023

  8. [6]

    A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels,

    E. Abbe and C. Sandon, “A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels,” inIEEE 64th Annual Symposium on F oundations of Computer Science (FOCS), 2023, pp. 177–193

    2023

Show all 40 references
  1. [7]

    Polynomial Freiman-Ruzsa, Reed-Muller codes and Shannon capacity,

    E. Abbe, C. Sandon, V . Shashkov, and M. Viazovska, “Polynomial Freiman-Ruzsa, Reed-Muller codes and Shannon capacity,”arXiv preprint arXiv:2411.13493, 2024

    2024

  2. [8]

    Capacity on BMS channels via code symmetry and nesting,

    H. D. Pfister and G. Reeves, “Capacity on BMS channels via code symmetry and nesting,”arXiv preprint arXiv:2504.15394, 2025

    2025 arXiv

  3. [9]

    A survey of Reed-Muller codes from polar coding perspective,

    E. Arıkan, “A survey of Reed-Muller codes from polar coding perspective,” inIEEE Information Theory Workshop on Information Theory (ITW 2010, Cairo), 2010, pp. 1–5

    2010

  4. [10]

    Reed-Muller codes polarize,

    E. Abbe and M. Ye, “Reed-Muller codes polarize,”IEEE Trans. Inform. Theory, vol. 66, no. 12, pp. 7311–7332, 2020

    2020

  5. [11]

    A class of multiple-error-correcting codes and the decoding scheme,

    I. Reed, “A class of multiple-error-correcting codes and the decoding scheme,”Trans. of the IRE Professional Group on Information Theory, vol. 4, no. 4, pp. 38–49, 1954

    1954

  6. [12]

    A serial orthogonal decoder,

    R. R. Green, “A serial orthogonal decoder,”JPL Space Programs Summary, vol. 37, pp. 247–253, 1966

    1966

  7. [13]

    Optimal soft decision block decoders based on fast Hadamard transform,

    Y . Be’ery and J. Snyders, “Optimal soft decision block decoders based on fast Hadamard transform,”IEEE Trans. Inform. Theory, vol. 32, no. 3, pp. 355–364, 1986

    1986

  8. [14]

    Soft-decision decoding of Reed-Muller codes: recursive lists,

    I. Dumer and K. Shabunov, “Soft-decision decoding of Reed-Muller codes: recursive lists,”IEEE Trans. Inform. Theory, vol. 52, no. 3, pp. 1260–1266, 2006

    2006

  9. [15]

    Recursive projection-aggregation decoding of Reed-Muller codes,

    M. Ye and E. Abbe, “Recursive projection-aggregation decoding of Reed-Muller codes,”IEEE Trans. Inform. Theory, vol. 66, no. 8, pp. 4948–4965, 2020

    2020

  10. [18]

    Coset error pattern in projection-aggregation decoding,

    B. Zhang, F. Chen, and Q. Huang, “Coset error pattern in projection-aggregation decoding,”IEEE Trans. Inform. Theory, pp. 1–1, 2025

    2025

  11. [19]

    Decoding Reed–Muller codes using redundant code constraints,

    M. Lian, C. H ¨ager, and H. D. Pfister, “Decoding Reed–Muller codes using redundant code constraints,” inIEEE International Symposium on Information Theory (ISIT), 2020, pp. 42–47

    2020

  12. [20]

    Pruned collapsed projection-aggregation decoding of Reed-Muller codes,

    Q. Huang and B. Zhang, “Pruned collapsed projection-aggregation decoding of Reed-Muller codes,”CoRR, vol. abs/2105.11878, 2021. [Online]. Available: https://arxiv.org/abs/2105.11878

    2021 arXiv

  13. [21]

    Minimum distance decoding for Reed-Muller codes using projection-aggregation,

    B. Zhang and Q. Huang, “Minimum distance decoding for Reed-Muller codes using projection-aggregation,” inIEEE Information Theory Workshop (ITW), 2025, pp. 680–685

    2025

  14. [22]

    A layered CPA decoder for Reed-Muller codes,

    J. Li and W. J. Gross, “A layered CPA decoder for Reed-Muller codes,” in58th Asilomar Conference on Signals, Systems, and Computers, 2024, pp. 985–989

    2024

  15. [23]

    Reed–Muller codes: Theory and algorithms,

    E. Abbe, A. Shpilka, and M. Ye, “Reed–Muller codes: Theory and algorithms,”IEEE Trans. Inform. Theory, vol. 67, no. 6, pp. 3251–3277, 2021

    2021

  16. [24]

    Reduced-complexity projection-aggregation list decoder for Reed-Muller codes,

    J. Li, H. Zhou, M. Jalaleddine, and W. J. Gross, “Reduced-complexity projection-aggregation list decoder for Reed-Muller codes,”IEEE Trans. Commun., vol. 73, no. 3, pp. 1458–1473, 2025

    2025

  17. [25]

    Iterative decoding of binary block and convolutional codes,

    J. Hagenauer, E. Offer, and L. Papke, “Iterative decoding of binary block and convolutional codes,”IEEE Trans. Inform. Theory, vol. 42, no. 2, pp. 429–445, 1996

    1996

  18. [26]

    The capacity of low-density parity-check codes under message-passing decoding,

    T. Richardson and R. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding,”IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 599–618, 2001

    2001

  19. [27]

    Cambridge university press, 2008

    ——,Modern coding theory. Cambridge university press, 2008

    2008

  20. [28]

    Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation,

    S.-Y . Chung, T. Richardson, and R. Urbanke, “Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation,” IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 657–670, 2001. 21

    2001

  21. [29]

    Analysis of low density codes and improved designs using irregular graphs,

    M. Luby, M. Mitzenmacher, A. Shokrollah, and D. Spielman, “Analysis of low density codes and improved designs using irregular graphs,” inProceedings of the thirtieth annual ACM symposium on Theory of computing, 1998, pp. 249–258

    1998

  22. [30]

    Codes on graphs: normal realizations,

    G. Forney, “Codes on graphs: normal realizations,”IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 520–548, 2001

    2001

  23. [31]

    An optimum symbol-by-symbol decoding rule for linear codes,

    C. Hartmann and L. Rudolph, “An optimum symbol-by-symbol decoding rule for linear codes,”IEEE Trans. Inform. Theory, vol. 22, no. 5, pp. 514–517, 1976

    1976

  24. [32]

    Replication decoding,

    G. Battail, M. Decouvelaere, and P. Godlewski, “Replication decoding,”IEEE Trans. Inform. Theory, vol. 25, no. 3, pp. 332–345, 1979

    1979

  25. [33]

    Roy,Series and Products in the Development of Mathematics: V olume 1

    R. Roy,Series and Products in the Development of Mathematics: V olume 1. Cambridge University Press, 2021

    2021

  26. [34]

    Efficiently decoding Reed-Muller codes from random errors,

    R. Saptharishi, A. Shpilka, and B. L. V olk, “Efficiently decoding Reed-Muller codes from random errors,” inProceedings of the forty-eighth annual ACM symposium on Theory of Computing, 2016, pp. 227–235

    2016

  27. [35]

    Efficiently decoding Reed–Muller codes from random errors,

    ——, “Efficiently decoding Reed–Muller codes from random errors,”IEEE Trans. Inform. Theory, vol. 63, no. 4, pp. 1954–1960, 2017

    1954

  28. [36]

    Accessed on Dec

    Upper and lower bounds for the normal distribution function. Accessed on Dec. 28, 2025. [Online]. Available: https://www.johndcook.com/blog/ norm-dist-bounds/

    2025

  29. [37]

    Optimization and simplification of PCPA decoder for Reed-Muller codes,

    J. Li and W. J. Gross, “Optimization and simplification of PCPA decoder for Reed-Muller codes,”IEEE Commun. Lett., vol. 26, no. 6, pp. 1206–1210, 2022

    2022

  30. [38]

    Accessed on Jan

    (2013) Sums of normal random variables need not be normal. Accessed on Jan. 29, 2026. [Online]. Available: https://planetmath.org/ sumsofnormalrandomvariablesneednotbenormal

    2013

  31. [39]

    Decoding of Reed-Muller codes with a large number of errors,

    V . M. Sidel’nikov and A. S. Pershakov, “Decoding of Reed-Muller codes with a large number of errors,”Problemy peredachi informatsii, vol. 28, no. 3, pp. 80–94, 1992

    1992

  32. [40]

    Recursive decoding and its performance for low-rate Reed-Muller codes,

    I. Dumer, “Recursive decoding and its performance for low-rate Reed-Muller codes,”IEEE Trans. Inform. Theory, vol. 50, no. 5, pp. 811–823, 2004

    2004

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.