Spatially Coupled MacKay-Neal/Hsu-Anastasopoulos CSS Codes Achieve the Quantum-Erasure Hashing Bound by Seeded BP Decoding

健太 笠井, Kenta Kasai, 隆之 野崎 +3 more

Kenta Kasai

We study hard-erasure belief-propagation (BP), understood as the sum-product algorithm on erasure messages, for a punctured MacKay-Neal/Hsu-Anastasopoulos (MN/HA) representation of Calderbank-Shor-Steane (CSS) codes. For every integer degree triple $2\leq j_Z<j_X<k\leq60$, we prove that the constituent potential thresholds are $j_Z/k$ and $1-j_X/k$. The proof combines classical HA-MN duality with a completed exact rational certificate for all 1711 MN degree pairs in this range. The certificate establishes strict positivity on every physical nontrivial fixed-point branch, at every erasure probability in $[0,1]$, and has an independent integer-arithmetic verifier. A reduction of the Z-side recursion and a fixed-channel vector-potential argument then prove seeded density-evolution convergence below the smaller constituent threshold for sufficiently large coupling width and an ideal seed interval at least that wide. Under $j_Z+j_X=k$, this threshold equals the quantum-erasure hashing-bound parameter determined by the CSS design rate. In particular, the degree triple $(4,8,12)$ has potential threshold $1/3$ without a positivity hypothesis. The numerical example at erasure probability $0.3325$ reproduces the resulting decoding waves. The theorem uses an ideal auxiliary-message seed; its finite-code realization and logical block-error convergence are separate questions.

Elena Berardini, A. Caminata, Alberto Ravagnani

I. Zinnatullin, Kamil Ravilevich Khadiev

健太 笠井, Kenta Kasai, 好一 坂庭 +1 more

Kudekar et al. recently proved that for transmission over the binary erasure channel (BEC), spatial coupling of LDPC codes increases the BP threshold of the coupled ensemble to the MAP threshold of the underlying LDPC codes. One major drawback of the capacity-achieving spatially-coupled LDPC codes is that one needs to increase the column and row weight of parity-check matrices of the underlying LDPC codes. It is proved, that Hsu-Anastasopoulos (HA) codes and MacKay-Neal (MN) codes achieve the capacity of memoryless binary-input symmetric-output channels under MAP decoding with bounded column and row weight of the parity-check matrices. The HA codes and the MN codes are dual codes each other. The aim of this paper is to present an empirical evidence that spatially-coupled MN (resp. HA) codes with bounded column and row weight achieve the capacity of the BEC. To this end, we introduce a spatial coupling scheme of MN (resp. HA) codes. By density evolution analysis, we will show that the resulting spatially-coupled MN (resp. HA) codes have the BP threshold close to the Shannon limit.

Chen Lin, Guowu Yang, Qing-bin Luo +1 more