IEEE Transactions on Communications
Reduced Complexity Layered CPA List Decoders for Reed–Muller Codes
Jiajie Li, Marwan Jalaleddine, Warren J. Gross
Abstract
The recently proposed projection-aggregation (PA) decoder achieves near maximum-likelihood decoding performance for decoding short-length and low-rate Reed-Muller (RM) codes. However, the high computational complexity has a negative impact on the practicality of its implementation. This paper proposes techniques, which are inspired by the layered decoding and the broadcast modification for the belief propagation decoder used by the low-density parity-check codes, for the collapsed PA (CPA) decoder. Proposed techniques have a negligible impact on the decoding performance while having a 47% reduction in the average complexity at$E_{b}/N_{0}=2.5$dB when decoding RM$(8,3)$codes. When extending the layered decoder to the Chase list decoder, reductions in the average complexity (up to 40%) and the number of iterations (at least one iteration) are observed. Additionally, we propose a quantized and normalized fast Hadamard transform (FHT), which reduces the bit-width from a number equal to the number of stages in the FHT to a constant of 2, and a reformulated list decoding metric, which reduces the bit-width by at least$5-r$bits for RM$\left ({ m=7,r=3}\right)$, RM$\left ({ 7,4}\right)$, and RM$\left ({ 8,3}\right)$codes where$m$is the code-length parameter and$r$is the order of RM codes, for the quantized layered CPA and the list decoders with less than 0.1 dB loss in decoding performance.