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

Jul 16, 2026

Reed–Muller (RM) codes achieve capacity across many channels, and projection-aggregation (PA) decoding has been shown experimentally to approach maximum-likelihood performance. This work analyzes the density function of soft outputs from collapsed projection-aggregation (CPA) decoding for RM codes over the binary-input additive white Gaussian noise (BIAWGN) channel. It proves soft-decision CPA yields an exact marginal probability and is symmetric, then builds a density-evolution model approximating projection and fast Hadamard decoding to explain convergence and enable an asymptotic vanishing error result at vanishing rate.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages21

Reading Time53 min

Abstract

Introduction

Capacity-achieving Reed–Muller codes

Decoding algorithms for Reed–Muller codes

Projection-aggregation and collapsed projection-aggregation

Gap: soft-decision density analysis

Contributions

1 arXiv :2607 .09602v 1 [ cs .IT] 10 Jul 2026 Density Evolution of Soft-Decision Collapsed Projection-Aggregation Decoding for Reed–Muller Codes over the BIAWGN Channel Jiajie Li, Marvin R¨ubenacke, and Warren J. Gross Abstract Reed–Muller (RM) codes have been shown to achieve capacity over a range of channels, and recently proposed projectionaggregation (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. Index Terms asymptotic analysis, collapsed projection-aggregation decoding, density evolution, Reed-Muller codes, soft-decision decoding. I. INTRODUCTION Recent research demonstrates that Reed–Muller (RM) codes [1] achieve channel capacity under a wide range of channels, such as the binary erasure channel [2], the binary symmetric channel (BSC) [3], [4], and the binary-input memoryless symmetric (BMS) channel [5]–[8] . In addition to the capacity-achieving capability, the RM codes are structurally similar to polar codes [9] and also exhibit a polarization effect [10] . Decoding with affordable complexity for RM codes is the key to utilizing the desired characteristic mentioned. The first decoding algorithm for RM codes is majority-vote decoding [11] that can correct error patterns with a weight of fewer than half of the minimum distance of RM codes. For order r = 1 RM codes, maximum-likelihood (ML) decoding performance can be achieved under a complexity O (n log2 (n)) using the fast Hadamard transform (FHT) decoding [12], [13], where n is the code length. Many decoding algorithms are proposed for RM codes with r ≥ 2. For example, Dumer’s recursive list decoding can achieve ML decoding performance given a sufficiently large list size [14] . The recently proposed recursive projection-aggregation (RPA) decoding and its list decoding are observed to achieve near-ML decoding performance for a range of code lengths and code rates [15] . Given its near-ML decoding performance, theoretical analysis on RPA decoding is conducted in the literature [16]–[18] . It is proven in [16] that the RPA decoding can asymptotically achieve vanishing probability over the BSC for RM codes with r ≤ log (cm), where m is the code length parameter and c is a constant that is proportional to the cross-over probability of the BSC. Later, the result is extended to the BMS channel [17] . A variant of RPA decoding, namely collapsed projection-aggregation (CPA) decoding, is proposed to reduce the computational complexity of RPA decoding by removing repeated subspaces [19] . CPA decoding targets the soft-decision variant of RPA decoding and, as pointed out in [19], it is closely related to belief propagation (BP) decoding. The similarity of the decoding results under different subspaces in CPA decoding is first analyzed in [20] . The error patterns encountered during RPA and CPA decoding are analyzed in [18], where it is further show

FAQs

What does the paper analyze about collapsed projection-aggregation (CPA) decoding?

It analyzes the density function of the soft output produced by CPA decoding for Reed–Muller codes over the BIAWGN channel, and tracks how the soft information evolves across iterations.

What theoretical properties are proven for soft-decision CPA decoding?

The paper proves that soft-decision CPA returns the exact marginal probability and that the decoding output is symmetric with respect to the transmitted codeword.

How does the proposed density evolution model help explain CPA decoding behavior?

By approximating projection and fast Hadamard-transform decoding with hard-decision counterparts, the model captures the rapid reduction in the mean and variance of soft information returned from CPA decoding, which qualitatively explains the fast convergence.

Jul 16, 2026

Upload by Valentina