Low-Density Parity-Check Codes (LDPC)

The sparsity of the parity-check matrix means each bit participates in only a few parity checks. At decoding, message-passing on the bipartite graph is linear in the number of edges, not the code length. For dense codes, decoding would require matrix inversion, which is cubic in code length. Sparsity makes decoding quasi-linear and practical for long codes.

An absorbing set is a small subset of the graph that can trap belief propagation decoding, preventing convergence to the correct solution. They are a primary source of error floor (the non-exponential decrease in BER at low SNR). Code designers avoid short absorbing sets through careful graph construction; analysis tools (e.g., stopping set analysis) identify problematic structures.

Both achieve near-Shannon performance. Polar codes have a recursive structure and provable optimality under successive cancellation decoding at infinite code length. LDPC codes are more flexible and have better finite-length performance empirically. 5G NR uses polar codes for control channels (short packets) and LDPC for data channels (long packets), exploiting each code's strengths.

The girth is the length of the shortest cycle in the bipartite graph. Short cycles (girth < 6) cause belief propagation to use correlated information (messages loop back), degrading performance. High-girth codes (girth ≥ 6) break correlations better. Codes are often designed to maximize girth subject to sparsity constraints.