trapping-set · research · also LDPC trapping set

Trapping set

A trapping set is the nonempty set of all variable nodes that fail to become permanently correct for some input to a specified decoder.

Related Observatory article: Read on hesela.com

The operational definition depends on the decoder and its input space, not only the graph. The (a,b) notation counts variables and odd-degree neighboring checks; it does not establish a decoder failure by itself. A wrong codeword can have b=0. [1]

Absorbing sets instead have graph-defined strict-majority conditions. A fully absorbing configuration is stable under the specified majority bit-flipping rule, not necessarily under every soft decoder. [2]

For matrix rows 1100, 1010, 0110 and 1001, transmit 0000 and start hard decisions at 1110. Synchronous strict-majority flipping, with ties unchanged, gives 1110 -> 1111 -> 1111. The eventual failure support is all four bits, not the initial three-bit absorbing set. This exact toy calculation is not a NAND measurement. [3]

For conditionally independent bit-channel observations given the codeword, define L_i = ln(P(y_i|0)/P(y_i|1)). Choose illustrative LLRs (-1,-1,-1,+4), whose signs give the same 1110 hard decisions. Exhaustive enumeration finds only codewords 0000 and 1111. Their scores sum((1-2*x_i)*L_i) are +1 and -1; maximum-likelihood decoding selects 0000. The comparison changes both the decision rule and retained reliability information, so it isolates neither one's individual effect. [3]

Relations

related
LDPC (NAND ECC), Absorbing set, Fully absorbing set

Citations

  1. Tom Richardson. Error Floors of LDPC Codes. Allerton 2003, pages 1426-1435, sections 3.1 and 3.3. (accessed 2026-11-22)
  2. Dolecek et al. Analysis of Absorbing Sets and Fully Absorbing Sets of Array-Based LDPC Codes (2010), section II.B, Definition 1. DOI 10.1109/TIT.2009.2034781. (accessed 2026-11-22)
  3. Hesela: executable synthetic parity-graph and decoder-dependent witness (accessed 2026-11-22)
Sources & caveats
  • The four-bit example compares an exactly specified hard-decision rule with exhaustive maximum-likelihood scoring on a toy code. It does not reproduce Richardson's algorithm, a NAND controller, a BER or FER curve.
  • The fixed point proves this toy trajectory stays wrong; observing a general decoder for finitely many iterations alone would not prove its eventual behavior.

JSON: /data/terms/trapping-set.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Trapping set. Hesela. 2026-11-22. https://hesela.dev/terms/trapping-set/