Papers for

information theory system builders

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

MacKay-Neal codes proven to reach channel capacity with exact decoding

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 $(\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.

Wed 7 OctInformation Theory
The gist
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.
Open → 2610.10277v1