PaperlayerView exact revision on arXiv

Source-linked AI summary

MacKay-Neal Codes Achieve Capacity under MAP Decoding

Kenta Kasai

arXiv:2610.10277v1cs.ITmath.IT

TL;DR

It remained to establish whether the predicted capacity achievement holds for the independently matched, uncoupled (ℓ,3,3) ensemble with degrees fixed before blocklength grows. The proof combines exact candidate counts with a six-bit even-parity entropy inequality, then uses channel comparison, independent output erasures, and a minimum-distance estimate to bound decoding errors. For fixed ℓ≥4 and C(W)>3/ℓ, ensemble-average transmitted-bit MAP and extended-word block-MAP errors are both O(log N/N), and the actual transmitted rate converges to 3/ℓ.

  • Problem

    It remained to establish whether the predicted capacity achievement holds for the independently matched, uncoupled (ℓ,3,3) ensemble with degrees fixed before blocklength grows.

    Source: §1 · p. 1

  • Method

    The proof combines exact candidate counts with a six-bit even-parity entropy inequality, then uses channel comparison, independent output erasures, and a minimum-distance estimate to bound decoding errors.

    Source: §1.2 · pp. 3–4, §1.3 · p. 4

  • Results

    For fixed ℓ≥4 and C(W)>3/ℓ, ensemble-average transmitted-bit MAP and extended-word block-MAP errors are both O(log N/N), and the actual transmitted rate converges to 3/ℓ.

    Source: §1.1 · pp. 1–2

  • Takeaways & Limitations

    The capacity prediction is rigorous for the specified uncoupled degree family, including block-MAP decoding of the full extended word.

    Source: §1.2 · p. 3

    The theorem applies to each fixed channel under MAP decoding for the specified ensemble, but does not cover the equality case C(W) = R.

    Source: §1.1 · p. 2

Abstract

from arXiv · show

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.

1 Introduction

The paper makes a fixed-degree capacity prediction rigorous for the specified uncoupled MacKay–Neal ensemble, including block decoding of the full extended word. Its proof combines exact candidate counts with a local entropy inequality and then converts conditional-entropy bounds into bit- and block-error bounds.

1 Introduction

  • Puncturing one variable class lets MN codes pair dense effective constraints with a bounded number of edges per transmitted bit, motivating the fixed-degree capacity question.Earlier rigorous MN capacity results increased degrees as the operating point approached capacity, while later fixed-degree predictions relied on statistical-mechanical analyses.Source: §1 · p. 1

1.1 Main result

  • For fixed ℓ≥4 and C(W)>3/ℓ, ensemble-average transmitted-bit MAP and full extended-word block-MAP errors are both O(log N/N).The actual transmitted rate converges to 3/ℓ; below that capacity, the limiting inferior bit-error bound is strictly positive.Source: §1.1 · pp. 1–2
  • The result concerns the specified uncoupled ensemble and MAP decoding; the equality case C(W)=3/ℓ is not covered.The uniform extended-code prior includes configurations without conditioning the sparse square matrix on invertibility.Source: §1.1 · p. 2, §1.2 · p. 3

1.2 Relation to previous results

  • Exact candidate counts depend on the mean fractions of ones among both punctured and transmitted variables, leaving an inequality to prove for every admissible pair.The relevant local constraint is even parity on six bits, with three sockets from each variable class.Source: §1.2 · p. 3
  • The local inequality and exact configuration counts bound conditional entropy on the BSC; a mutual-information comparison extends the bound to general BMS channels.The same local inequality applies for every fixed ℓ≥4 because the check structure remains unchanged.Source: §1.2 · pp. 3–4, §1.3 · pp. 4–5
  • The proof establishes the six-bit entropy inequality by symmetry reduction, restricting interior stationary points to the diagonal, and explicit polynomial bounds.This handles unequal mean fractions, which symmetry under exchanging them alone does not resolve.Source: §1.2 · p. 4

1.3 Proof outline

  • For the BSC, a noise-syndrome identity expresses full-word uncertainty through counts of noise and auxiliary-vector pairs sharing a syndrome.The proof does not require the sparse matrices to be invertible.Source: §1.3 · p. 4
  • Independent output erasures turn the entropy bound into a transmitted-bit error bound, while a transmitted-code minimum-distance estimate yields full-word block error.Outside a set of graphs of probability O(1/N), the transmitted code has distance at least δ_vN and the punctured word is uniquely determined.Source: §1.3 · p. 5

2 Ensemble and notation

The ensemble uses independent socket matchings for punctured and transmitted variables, with a uniform prior on the extended code. Its transmitted code and actual rate remain defined even when the sparse matrices are singular.

2 Ensemble and notation

  • Each check has three sockets of each edge type; punctured variables have degree ℓ, transmitted variables degree 3, and the ensemble has N transmitted variables and K = 3N/ℓ punctured variables.The two edge types are matched independently and uniformly; socket degrees are specified before parallel edges are reduced modulo two.Source: §2 · p. 5
  • The extended code contains pairs (u, v) satisfying Au + Bv = 0, and the transmitted code is its projection onto v.The pair (U, V) is uniform on the extended code, while V is sent through the channel and the decoder knows the graph.Source: §2 · pp. 5–6
  • The construction and uniform extended-code prior are defined even when A or B is singular, without requiring either matrix to be invertible.When B is invertible, the relation reduces to the usual MN encoding relation; the definition also covers singular B.Source: §2 · p. 6
  • The actual transmitted rate is dim C(G)/N, which can differ from the design ratio K/N because matrix dependencies affect the transmitted code dimension.Bit- and block-MAP errors use the specified uniform prior and matched channel law; block-MAP success entails correct recovery of the transmitted word.Source: §2 · p. 6

3 An entropy bound for an even-parity check

The section bounds the entropy of an even-parity six-bit check at two potentially unequal marginal means. An analytic reduction establishes the inequality needed for the configuration count.

3 An entropy bound for an even-parity check

  • The local check polynomial F(x, y) encodes even-parity six-bit vectors by the numbers of active sockets in each of the two triples.Its coefficients count the vectors with each pair of socket counts, and F^N counts admissible socket profiles across N checks.Source: §3 · p. 6
  • For feasible means a and b, Φ(a, b) is the maximum natural-log entropy of an even-parity six-bit vector with marginal means a and b on the two triples.The variational expression uses the infimum over positive x and y; infeasible pairs have Φ(a, b) = −∞ when |a − b| > 2/3.Source: §3 · p. 6
  • The proof handles unequal means by reducing the domain through symmetry and boundary estimates, then showing every interior stationary point in the reduced domain lies on the diagonal.Bounds on the diagonal use explicit polynomial and power-series estimates.Source: §3 · p. 7
  • The resulting entropy inequality makes the exponent in the configuration-count bound nonpositive under the stated rate condition.For fixed a and b, the left side of the inequality is piecewise affine in R; its maximum on [0, 1] occurs at R = 1 − h2(b), where Lemma 1 applies.Source: §3 · p. 7

4 Conditional entropy and decoding on BMS channels

The section bounds full-word conditional entropy first on the BSC, then extends the bound to BMS channels and converts it to decoding guarantees. Independent output erasures support the bit-error bound, while separate arguments establish actual-rate convergence and the converse.

4.1 A noise-syndrome identity without rank assumptions

  • The noise-syndrome identity equates uncertainty about the full extended word with uncertainty about an independent auxiliary vector and BSC noise given their syndrome, without rank assumptions.The identity is H(U, V | Y, G) = H(U0, E | T, G), with T = AU0 + BE.Source: §4.1 · p. 7

4.2 Finite noise types on the BSC

  • The finite-noise-type count yields ensemble-average full-word conditional entropy O_p,ℓ(log N) on the BSC below the threshold p*.The proof conditions on noise weight and syndrome so the admissible pairs are equiprobable, then bounds their number by exact socket counts.Source: §4.2 · pp. 8, 10

4.3 The comparison with an equal-capacity BSC

  • For any input-vector distribution and auxiliary variable, a more-capable channel has no greater joint conditional entropy than the compared channel.The coordinate-output replacement argument applies even when code coordinates are correlated, because the single-letter inequality holds for each conditional input probability.Source: §4.3 · pp. 10–11

4.4 Independent output erasures and bit-MAP error

  • Independent output erasures relate bit-MAP error on W to the reduction in conditional entropy between Wε and W.The bound is 2εCN P_MAP bit(W) ≤ H(V | Y(Wε)) − H(V | Y(W)) ≤ H(V | Y(Wε)); erasing spends part of the capacity gap while leaving Wε above rate R.Source: §4.4 · pp. 11–12

4.5 Actual transmitted rate and the converse

  • The actual transmitted rate converges to R in L1 and therefore in probability.The proof controls the kernel dimension on the noiseless channel and excess extended-code dimension on a channel with capacity just above R.Source: §4.5 · p. 12
  • For capacity below R, the coordinatewise binary Fano bound gives a strictly positive asymptotic lower bound on average bit-MAP error.The argument averages over graphs and uses rate convergence.Source: §4.5 · p. 12

N P MAP

The passage identifies the preceding claim as part of Theorem 1.

N P MAP

5 Minimum distance of the transmitted code and block-MAP decoding

A graph event gives the transmitted code linear minimum distance and makes the punctured variables uniquely determined by the transmitted word. This distance property upgrades the transmitted-bit MAP bound to a block-MAP bound for the full extended word.

  • Outside an event of probability tending to zero, A is injective and every nonzero transmitted codeword has weight greater than δ_vN.The supplied result identifies the event G_N but does not state its probability bound here.Source: §5 · p. 13
  • The distance proof covers small total weights by socket containment and larger total weights with small transmitted weight by the entropy inequality.The decomposition also excludes nonzero invisible pairs (u, 0), yielding injectivity of A.Source: §5 · p. 13
  • The full extended-word block-MAP error probability is O(log N/N).The nearest-codeword decoder and a half-minimum-distance argument turn the expected bit-error count into a block-error bound without assuming independent bit errors.Source: §5 · p. 13
  • The block-error comparison itself does not require channel symmetry; symmetry is used in the preceding transmitted-bit MAP bound.Source: §5 · p. 13

6 Conclusion

The paper proves fixed-degree MAP capacity achievement for the independent uncoupled (ℓ, 3, 3) MN socket ensemble. Its proof combines a local entropy inequality with finite-length counting, while sharper bounds and other degrees remain open questions.

  • The independent uncoupled (ℓ, 3, 3) MN socket ensemble attains the MAP capacity threshold for every fixed integer ℓ≥4.The result establishes actual-rate convergence and vanishing block error for each BMS channel whose capacity exceeds the design rate.Source: §6 · p. 14
  • The local entropy inequality is independent of ℓ and the channel, and supplies the negative exponent used to bound transmitted-code minimum distance.The BSC-to-BMS step uses information ordering, while additional arguments are needed to compare MAP error probabilities.Source: §6 · p. 14
  • Analogous inequalities for other MN degrees and sharper finite-length distance and error bounds remain further questions.Source: §6 · p. 14

A Proof of the entropy bound for an even-parity check

The appendix proves the local entropy bound by reducing the domain and showing that any interior stationary point must lie on the diagonal. Explicit one-variable estimates then establish the inequality on that diagonal.

B Proof of the minimum-distance estimate for the transmitted code

The minimum-distance estimate separates low total weights from words with larger total weight but small transmitted weight. Socket containment and the entropy inequality bound these regions and establish a graph event with injectivity and linear transmitted-code distance.

  • The small-weight region is bounded by counting active sockets, which must occupy at most m rows when each occupied row has positive even active degree.The proof unions over sets of m rows and then over support pairs.Source: B Proof of the minimum-distance… · pp. 18–19
  • For small total weight, the cited estimate bounds G{∃(u, v) ≠ 0: Au + Bv = 0, |u| + |v| ≤ δ_eN} by 325ℓ^3.The small-total-weight region is controlled by socket containment. The proof uses the parity of ℓa + 3t and does not require t itself to be even.Source: B Proof of the minimum-distance… · pp. 18–19
  • For larger total weight and transmitted weight at most δ_vN, the entropy inequality gives a bound Q_Ne^(−cℓN) on the probability of any such word.The count sums over at most (K+1)(N+1) weight pairs.Source: B Proof of the minimum-distance… · pp. 19–20
  • The two estimates yield an event G_N on which A is injective and every nonzero transmitted codeword has weight greater than δ_vN.Injectivity follows because the event excludes nonzero words (u, 0).Source: B Proof of the minimum-distance… · p. 20

Declaration of generative AI use

The author reports substantial Codex assistance across research development and manuscript preparation, while retaining full responsibility for the final work.

Loading 2610.10277v1…