MacKay-Neal Codes Achieve Capacity under MAP Decoding
Abstract
Statistical-mechanical analyses predict that MacKay-Neal codes can achieve channel capacity at fixed degrees. We prove this prediction for the uncoupled (ℓ,3,3) MN socket ensemble for every fixed integer ℓ≥4. For each binary-input memoryless symmetric channel of capacity strictly greater than 3/ℓ, the ensemble-average block error probability under maximum a posteriori (MAP) decoding is O(log N/N), where N is the transmitted blocklength. The actual transmitted rate converges to 3/ℓ. The result includes both punctured and transmitted variables and does not condition the sparse square matrix on invertibility. The proof establishes an entropy inequality for six bits subject to even parity by an analytic argument that reduces the domain by symmetry, restricts its interior stationary points, where both partial derivatives vanish, to the diagonal, and controls the resulting scalar functions by explicit polynomial bounds. Exact configuration counts then bound the conditional entropy on the binary symmetric channel. A standard comparison by mutual information extends the entropy bound to general symmetric channels; independent output erasures and a minimum-distance estimate for the transmitted code yield the bit and block error bounds.
Related
- Spatially Coupled MacKay-Neal/Hsu-Anastasopoulos CSS Codes Achieve the Quantum-Erasure Hashing Bound by Seeded BP Decoding
- Spatially Coupled MacKay-Neal Codes Achieve Capacity on BMS Channels at Fixed Degrees
- MacKay-Neal Codes for DNA Channels under Block-MAP Decoding
- Spatially Coupled MacKay-Neal Codes on Symmetric Markov Noise: A Reduction to BMS Channels
- Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
BibTeX
@misc{kasai2026mackayneal,
title = {{MacKay-Neal Codes Achieve Capacity under MAP Decoding}},
author = {Kenta Kasai},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10277},
eprint = {2610.10277},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10277},
}
RIS
TY - UNPB
TI - MacKay-Neal Codes Achieve Capacity under MAP Decoding
AU - Kenta Kasai
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10277
UR - https://arxiv.org/abs/2610.10277
AB - Statistical-mechanical analyses predict that MacKay-Neal codes can achieve channel capacity at fixed degrees. We prove this prediction for the uncoupled (ℓ,3,3) MN socket ensemble for every fixed integer ℓ≥4. For each binary-input memoryless symmetric channel of capacity strictly greater than 3/ℓ, the ensemble-average block error probability under maximum a posteriori (MAP) decoding is O(log N/N), where N is the transmitted blocklength. The actual transmitted rate converges to 3/ℓ. The result includes both punctured and transmitted variables and does not condition the sparse square matrix on invertibility. The proof establishes an entropy inequality for six bits subject to even parity by an analytic argument that reduces the domain by symmetry, restricts its interior stationary points, where both partial derivatives vanish, to the diagonal, and controls the resulting scalar functions by explicit polynomial bounds. Exact configuration counts then bound the conditional entropy on the binary symmetric channel. A standard comparison by mutual information extends the entropy bound to general symmetric channels; independent output erasures and a minimum-distance estimate for the transmitted code yield the bit and block error bounds.
ER -