PaperlayerView exact revision on arXiv

Source-linked AI summary

Spatially Coupled MacKay-Neal Codes on Symmetric Markov Noise: A Reduction to BMS Channels

Kenta Kasai

arXiv:2610.00227v1cs.ITmath.IT

TL;DR

For fixed-degree spatially coupled MacKay–Neal codes on additive symmetric Markov noise, the paper addresses how to transfer BMS fixed-point positivity to a channel with memory. It uses an entropy correction and a posterior-contraction bound, establishing a finite-code capacity criterion for matched finite-window decoding.

  • Problem

    The proof for spatially coupled codes on channels with memory needs a BMS comparison and an additional estimate controlling detector dependence.

    Source: §1 · p. 1

  • Method

    A conditional-entropy correction transfers BMS positivity to Markov noise, while posterior contraction bounds detector interactions for threshold saturation.

    Source: §4 · p. 7, §7 · p. 13

  • Results

    For integer ℓ ≥ 4 with 3/ℓ below channel capacity, code sequences have actual rates tending to 3/ℓ and vanishing average information-bit error under matched finite-window BCJR and sum-product decoding.

    Source: §1.2 · p. 2

  • Takeaways & Limitations

    The argument transfers a positive gap to every nonperfect fixed point, including when the effective BMS channel has capacity below the design rate.

    Source: §3.2 · p. 6, §3.3 · p. 7

    The result is for symmetric Markov noise; extensions to general finite-state channels and quantitative convergence at moderate widths and iteration counts remain open.

    Source: §7 · pp. 13–14

Abstract

from arXiv · show

We prove a capacity criterion for fixed-degree spatially coupled MacKay--Neal codes on additive symmetric Markov noise. The noise bit flips with probability $p$, so the channel has one parameter and capacity $1-h_2(p)$. For every integer $\ell\geq4$ with $3/\ell<1-h_2(p)$, matched finite-window BCJR and sum-product decoding admit code sequences, possibly depending on $p$, with actual rate tending to $3/\ell$ and vanishing average information-bit error. The proof parallels the GEC-to-BEC argument: a conditional-entropy correction transfers BMS fixed-point positivity to the channel with memory. The correction also covers a capacity deficit of the effective BMS channel. A two-state posterior contraction supplies the additional derivative bound needed for threshold saturation. The result uses the cited BMS positivity theorem, with an analytic proof for $\ell\geq33$ and exact interval certificates for $4\leq\ell\leq32$.

1 Introduction

The paper connects fixed-degree spatially coupled MacKay–Neal codes to BMS positivity results to establish a capacity criterion for additive symmetric Markov noise. Its proof combines an entropy correction with a detector-dependence bound.

1.1 Historical background

  • Earlier spatially coupled MN results covered the BEC and GEC, while this work connects the fixed-degree BMS comparison theorem to BCJR detection on a channel with memory [21].Prior work included numerical thresholds near capacity for bounded-degree constructions.Source: §1.1 · pp. 1–2

1.2 Channel and result

  • The channel has additive symmetric Markov noise with transition bit probability p, and its capacity is 1 − h2(p).The noise is not revealed to the receiver; the input, output, and error bits are denoted X_t, Y_t, and E_t.Source: §1.2 · p. 2
  • For integer ℓ ≥ 4 with 3/ℓ below channel capacity, deterministic code realizations attain rates tending to 3/ℓ with vanishing average information-bit error under matched finite-window BCJR and sum-product decoding.The construction may depend on p, while the degrees remain fixed.Source: §1.2 · p. 2

1.3 Proof outline and relation to the GEC argument

  • The proof transfers BMS fixed-point positivity to Markov noise through a conditional-entropy correction, then uses posterior contraction to bound detector interactions for threshold saturation.Finite-window density evolution and a rate argument yield finite codes.Source: §1.3 · p. 3

2 Preliminaries

The preliminaries set up the BMS-law calculus and the extrinsic experiments used to analyze decoding over the Markov channel.

BMS laws

  • A BMS law is represented as a revealed mixture of BSC crossover probabilities, with reliability, conditional entropy, capacity, and Bhattacharyya parameter defined from that mixture.The calculus distinguishes variable convolution, which combines independent observations of one bit, from check convolution, which observes a parity.Source: §2 · p. 3

BMS results used

  • The cited BMS results give a positive potential gap for nonperfect fixed points above the design rate and convergence on finite chains at sufficiently large width [21].They also bound the Bhattacharyya parameter of every nonperfect fixed point and establish potential descent for an ordered update.Source: §2 · p. 3

Helpers and extrinsic laws

  • Independent BMS helper observations define block uncertainty and coordinate-averaged extrinsic laws, with the root helper omitted to prevent reuse of its incoming observation.Additive symmetry makes the extrinsic experiments BMS and permits all-zero-codeword analysis without transmitted dither.Source: §2 · pp. 3–4

Finite-window detector

  • The matched two-state BCJR detector combines prior likelihoods with the noise transition matrix, and its limiting conditional entropy and extrinsic law exist uniformly and continuously.At the uninformative input, the limiting extrinsic law remains uninformative.Source: §2 · p. 4

3 The BMS reduction

The section replaces the GEC area correction with a conditional-entropy correction for Markov noise, then uses it to transfer a positive potential gap from BMS fixed points. The resulting gap applies to every nonperfect fixed point when the physical channel capacity exceeds the design rate.

3.1 The counterpart of the GEC area correction

  • The entropy correction lower-bounds the normalized correction by the effective BMS channel’s capacity deficit, allowing it to compensate when that channel’s capacity is below the comparison threshold.The paper identifies this as the information-theoretic replacement for the GEC area correction for nonerasure messages.Source: §3.1 · p. 5
  • Varying helpers along a revealed mixture gives an entropy derivative expressed through the extrinsic BMS law, connecting the correction to the GEC area argument.The GEC version uses the extrinsic erasure probability; the entropy-correction bound supplies its replacement for nonerasure messages.Source: §3.1 · p. 5

3.2 Fixed points and potential

  • The fixed-point analysis separates the perfect point, the trivial point (∆0, ∆0), and nontrivial fixed points; the trivial point has potential C − R.The potential decomposes into a BMS potential and an entropy correction; at the uninformative point, the BMS channel has capacity zero while the correction equals C.Source: §3.2 · pp. 5–6

3.3 Transferring the positive gap

  • For each nontrivial fixed point, freezing its extrinsic law makes it a BMS fixed point, so the BMS potential comparison and entropy correction can be applied.The comparison law may differ between fixed points; the trivial point is treated separately.Source: §3.3 · p. 6, §3.2 · p. 6
  • With τ = (C + R)/2, the BMS gap handles effective channels of capacity at least τ, while the entropy correction handles lower-capacity cases, yielding a uniform positive gap ∆ = min{C − τ, Γℓ(τ)}.Because R < τ < C, both terms in the minimum are positive.Source: §3.3 · pp. 6–7

4 The one estimate needed for memory

A posterior contraction bound controls how local helpers affect distant bits, and detector limits and interaction estimates provide the regularity needed by the spatial-shift argument.

4 The one estimate needed for memory

  • After conditioning on the output and arbitrary local helpers, the channel from one bit to a bit k positions away has Dobrushin coefficient at most ρ^k, in either direction and even with perfect helpers.The one-step bound follows from the binary-chain posterior and composes across transitions.Source: §4 · p. 7
  • The entropy and detector limits are uniform and weakly continuous, and the extrinsic map preserves degradation order.For a fixed window, posterior reliabilities and bounded continuous test integrals vary continuously with helper laws; garbling helpers preserves degradation.Source: §4 · pp. 7–8
  • A window detector approximates the full detector through boundary effects: changing both boundaries changes the root reliability by at most 4ρ^W, with at most 2W/n exceptional roots in a finite block.Bounded martingale convergence defines the full posterior.Source: §4 · p. 8
  • The mixed derivative is bounded by a summed helper-interaction term, with each pair’s influence decaying as ρ^|i−j| and the total controlled by Jp.The proof contracts information through the posterior channel between helper locations, then sums the pairwise bounds.Source: §4 · p. 8

5 Threshold saturation

The threshold-saturation proof combines a positive fixed-point potential gap with a bound on how much a spatial shift can decrease the potential. Under the stated capacity and width conditions, the coupled density evolution converges to perfect information on every finite chain.

5 Threshold saturation

  • For C>R, a sufficient coupling width forces coupled density evolution from uninformative initialization to perfect information on every finite chain.The proof rules out a nonperfect limiting profile because the gap-based decrease is at least Δ, while the derivative-based bound is at most Kp/(2w).Source: §5 · pp. 9, 11
  • The proof adapts the BMS shift argument using finite-block potentials, then passes to limiting functionals and uses signed-entropy ordering to show potential descent.An ordered nonperfect limit would remain above the starting profile and contradict the fixed-point potential gap.Source: §5 · p. 9
  • A nonperfect fixed point would have potential at least Δ, while the shift argument bounds its decrease by Kp/(2w), yielding a contradiction at sufficient width.The bound combines the direct variable/check contribution with an additional detector mixed-derivative term.Source: §5 · pp. 10–11
  • The shift estimate uses entropy increments and a detector mixed-derivative bound to control the change along an interpolated profile.For a fixed finite profile, the finite-block residual is uniformly bounded by εn→0, but no convergence rate is inferred.Source: §5 · p. 10

6 Finite codes and actual rate

The paper constructs finite spatially coupled MN codes and relates their finite-window decoding errors to density evolution despite the channel’s temporal dependence. By choosing the construction parameters successively, it obtains actual rates tending to the design rate and vanishing average information-bit error.

6 Finite codes and actual rate

  • The construction uses balanced sectioned MN ensembles, finite-radius BCJR windows, SPA messages, and detector helpers, with shortened boundaries and selected offsets.The transmitted variables are sent through one continuous noise trajectory; the window decoder ignores outputs outside its window.Source: §6 · p. 11
  • As section size grows, ensemble-average errors converge to finite-window density evolution for either variable type at fixed chain length, width, window radius, and iteration count.The result unfolds each decision through a bounded dependency neighborhood while retaining dependence among observations within each detector window.Source: §6 · p. 12
  • A Markov coupling estimate controls dependence between separated windows, establishing ensemble-average error convergence without an exponential concentration claim.The construction takes the section-size limit before the window-radius limit.Source: §6 · p. 12
  • Successive choices of channel capacities, widths, chain lengths, iterations, window radii, and section sizes produce deterministic realizations whose actual rates tend to R and whose information-bit errors vanish.A deterministic encoder is obtained by selecting an information set in the transmitted projection and a linear section into the extended code.Source: §6 · pp. 12–13
  • The theorem gives no useful finite-length or iteration bound, despite the stated O(tn(W + ℓ)) cost for direct implementation.Finite parameters are selected for each target accuracy before increasing section size.Source: §6 · p. 13

7 Conclusion and extensions

The conclusion transfers BMS fixed-point positivity to symmetric Markov noise and identifies the posterior contraction needed for threshold saturation. Extensions to broader noise models require additional bounds and approximation arguments.

7 Conclusion and extensions

  • The potential decomposition transfers BMS positivity to Markov noise, while posterior contraction supplies the detector bound for threshold saturation.The extension argument also requires entropy and detector limits, a uniform summable interaction bound, and a computation-tree approximation.Source: §7 · p. 13
  • For finite binary additive-noise blocks, independent BMS helpers yield BMS extrinsic experiments and A_n ≥ max{0, C_n − C(e_n(d))}.This lower bound follows from the conditional-entropy correction.Source: §7 · p. 13
  • For strictly positive binary Markov transition matrices, the posterior-transition calculation gives a contraction factor η(Q) < 1, but the stated theorem concerns symmetric noise.Unequal switching probabilities generally change both capacity and the trivial point; the replacements and limit and realization arguments remain unchecked.Source: §7 · p. 13
  • For hidden Markov additive noise, including Gilbert–Elliott models, the error bit need not be Markov, and ordinary state mixing does not provide the required posterior control.An extension needs a helper-uniform bound, including perfect helpers, plus a mixed-entropy estimate and finite-window approximation.Source: §7 · p. 14
  • General finite-state channels may lack additive symmetry or have input-dependent transitions; insertions and deletions additionally require alignment and rate-normalization arguments.Quantitative convergence at moderate widths and finite iteration counts remains open, and other degree families need corresponding BMS positivity results.Source: §7 · p. 14
Loading 2610.00227v1…