MacKay-Neal codes proven to reach channel capacity with exact decoding
MacKay-Neal Codes Achieve Capacity under MAP Decoding
Information Theory
Summary
Communicating data without errors over channels is challenging. The paper shows that a certain type of error-correcting codes, called MacKay-Neal codes, can transmit information as efficiently as theoretically possible when using the best decoding method. The authors mathematically prove that these codes work well on various channels, ensuring the chance of errors decreases quickly as the message gets longer. This confirms earlier predictions using a rigorous proof.
What this means in practice
- •For telecommunications engineers: Design error-correction schemes that meet theoretical limits for reliable data transmission in memoryless symmetric channels.
- •For information theory system builders: Use the proven capacity-achieving properties of MacKay-Neal codes under MAP decoding to ensure optimal communication system performance.
A theory result. No direct application yet.
Authors
Kenta Kasai
Abstract
Statistical-mechanical analyses predict that MacKay-Neal codes can achieve channel capacity at fixed degrees. We prove this prediction for the uncoupled $(\ell,3,3)$ MN socket ensemble for every fixed integer $\ell\ge4$. For each binary-input memoryless symmetric channel of capacity strictly greater than $3/\ell$, 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/\ell$. 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.