Low-density parity-check code
Low-density parity-check (LDPC) codes are a class of linear block error-correcting codes defined by a sparse parity-check matrix H of dimensions m \times n, where n is the codeword length, m = n - k with k information bits, and the matrix has a low density of 1s such that each column has a small fixed weight \rho \geq 3 and each row has weight \gamma \geq 3.[1] This sparsity enables efficient iterative decoding while allowing the codes to approach the theoretical limits of error correction for certain channels.[1] LDPC codes operate on the principle that a received vector y satisfies H y = 0 for valid codewords, with decoding aiming to find the most likely codeword consistent with the received signal.[1] Invented by Robert G. Gallager in his 1960 MIT Sc.D. thesis and detailed in his 1963 monograph, LDPC codes were initially analyzed for their asymptotic performance on binary symmetric channels using probabilistic decoding methods.[1] Gallager analyzed the asymptotic performance of such codes, showing that ensembles exhibit vanishing error probability in the large block length limit for suitable parameters.[1] Despite these theoretical foundations, practical implementation challenges limited their adoption during the 1960s and 1970s. The codes gained prominence in the 1990s through rediscovery by David J.C. MacKay and Radford M. Neal, who demonstrated via simulations the near-Shannon-limit performance of LDPC codes using belief propagation decoding. Subsequent work showed performance within 0.0045 dB of the Shannon limit on the binary-input AWGN channel.[2][3] This work highlighted the efficacy of message-passing algorithms on the Tanner graph representation of LDPC codes, where variable nodes and check nodes exchange probabilistic messages iteratively to resolve uncertainties in the received bits. Subsequent research refined irregular LDPC codes with optimized degree distributions, further improving performance thresholds. The capacity-achieving properties of irregular LDPC ensembles were proven in the early 2000s.[4] Today, LDPC codes are integral to numerous high-speed communication standards due to their capacity-approaching error rates, low decoding latency, and hardware efficiency. They form the basis for forward error correction in DVB-S2 and DVB-S2X satellite broadcasting systems, where quasi-cyclic structures enable parallelizable encoding and decoding.[5] In wireless networks, quasi-cyclic LDPC codes are mandated for data channels in 5G New Radio (NR) standards, supporting rates up to 1 Gbps with block lengths from 40 to 8448 bits. Additional applications include Wi-Fi (IEEE 802.11n/ac/ax), 10GBASE-T Ethernet, and deep-space telemetry via CCSDS protocols, underscoring their versatility across noisy channels.[5]Fundamentals
Definition and Basic Properties
Low-density parity-check (LDPC) codes are a class of linear block codes over the binary field GF(2), where the codewords form a linear subspace of dimension k in the vector space \mathbb{F}_2^n.[1] These codes are defined by a set of linear parity-check equations that the codewords must satisfy, without specifying a generator matrix explicitly.[6] In general, a linear block code of length n and dimension k has a rate R = k/n and can correct up to t = \lfloor (d_{\min} - 1)/2 \rfloor errors, where d_{\min} is the minimum Hamming distance between any two distinct codewords.[7] An LDPC code is specified by an m \times n parity-check matrix H that is sparse, meaning it contains a low density of nonzero entries (typically less than 0.01 for practical codes with large n).[1][6] The rows of H correspond to m = n - k parity-check equations, and the code rate is R = 1 - m/n. A vector c \in \mathbb{F}_2^n is a valid codeword if and only if it satisfies H c = 0 (modulo 2).[1] For a received vector r = c + e (where e is the error vector), the syndrome is computed as s = H r = H e (modulo 2); a zero syndrome indicates no detectable errors, while a nonzero syndrome signals the presence of errors.[6] The minimum distance d_{\min} of an LDPC code, which determines its error-correcting capability, is closely tied to structural properties of the underlying bipartite Tanner graph, such as its girth (the length of the shortest cycle) and expansion (the growth rate of neighborhoods in the graph).[6] Larger girth helps avoid short cycles that degrade performance, providing lower bounds on d_{\min}, while good expansion ensures reliable error correction for a fraction of errors up to the code's design threshold.[6] The Tanner graph representation, with variable nodes for code bits and check nodes for parity equations connected by edges corresponding to nonzero entries in H, illustrates these graph-theoretic features.[6] LDPC codes exhibit capacity-approaching behavior when decoded using iterative message-passing algorithms, achieving rates arbitrarily close to the Shannon limit on the binary symmetric channel and binary erasure channel for sufficiently large block lengths.[1][7] This performance stems from the sparsity of H, which allows efficient probabilistic decoding that converges to near-optimal maximum-likelihood results in many cases.[7]Parity-Check Matrix and Tanner Graph
The parity-check matrix H of a low-density parity-check (LDPC) code is an m \times n binary matrix, where each of the m rows corresponds to a parity-check equation that the codeword must satisfy, and each of the n columns corresponds to one of the n bits in the codeword.[1] The codewords \mathbf{c} are those vectors in \mathbb{F}_2^n satisfying H \mathbf{c}^T = \mathbf{0}, ensuring the code rate is at least $1 - m/n.[8] The "low-density" property refers to the sparsity of H, where the density of 1s is very small, typically on the order of 1% or less, meaning each row and each column contains only a small number of 1s relative to m and n.[1] This sparsity is quantified by the row weight (number of 1s per row, denoted d_c for check node degree) and column weight (number of 1s per column, denoted d_v for variable node degree), which are fixed in regular LDPC codes but can vary in irregular ones.[8] The Tanner graph provides a graphical representation of the parity-check matrix H, introduced as a bipartite graph model for constraint-based codes.[9] It consists of two sets of nodes: n variable nodes (one for each codeword bit) on one side and m check nodes (one for each parity-check equation) on the other, with an edge connecting variable node i to check node j if and only if H_{j,i} = 1.[8] This structure visually encodes the linear constraints imposed by H, facilitating analysis of the code's dependencies. In the Tanner graph, cycles are closed paths of even length (since the graph is bipartite), and the girth is defined as the length of the shortest such cycle, with the minimum possible girth being 4.[9] Short cycles, particularly those of length 4 or 6, can degrade decoding performance by introducing correlations that hinder the propagation of independent information during iterative processing, while larger girth generally improves error-correction capability by enhancing the code's minimum distance.[9] In regular LDPC codes, all variable nodes have the same degree d_v and all check nodes have the same degree d_c, leading to uniform connectivity, whereas irregular codes allow varying degrees to optimize performance metrics like threshold or error floor.[8] For illustration, consider a small irregular LDPC code with parameters n=8, m=4 (rate $1/2), and parity-check matrix H = \begin{pmatrix} 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix}. [10] The corresponding Tanner graph has variable nodes V_1 to V_8 connected to check nodes C_1 to C_4 as follows: C_1 to V_1, V_3, V_4; C_2 to V_2, V_3, V_5; C_3 to V_4, V_5, V_6; C_4 to V_1, V_6, V_7, V_8.[10] This graph exhibits irregularity, with column weights ranging from 1 to 2 (e.g., V_7 degree 1, V_3 degree 2), and contains cycles whose lengths influence the code's structural properties.[10]Historical Development
Early Invention
Low-density parity-check (LDPC) codes were first invented by Robert G. Gallager in his doctoral dissertation at the Massachusetts Institute of Technology, completed in 1960.[11] In this work, Gallager proposed these codes as a class of linear block codes defined by sparse parity-check matrices, where each row and column has a low, fixed number of nonzero entries.[1] The motivation stemmed from the desire to create error-correcting codes that could approach the Shannon limit while enabling simpler decoding through the sparsity, which reduces the complexity of processing interdependencies in the parity checks compared to denser matrices.[1] Gallager expanded on these ideas in his seminal 1962 paper, providing a formal definition and analysis of LDPC codes.[1] A key contribution was the theoretical proof that ensembles of random LDPC codes, under maximum-likelihood decoding, exhibit an error exponent matching that of completely random codes, thereby achieving performance approaching channel capacity as block lengths grow large.[1] Additionally, he introduced simple iterative decoding algorithms based on probabilistic message-passing between variable and check nodes, which approximate the maximum-likelihood solution with significantly lower computational demands.[1] Gallager's LDPC codes represented the earliest known examples of error-correcting codes with decoding thresholds close to the Shannon limit for binary symmetric channels.[1] Initial computer simulations in the early 1960s demonstrated their strong performance, with error probabilities dropping exponentially for code rates below capacity at moderate block lengths, outperforming contemporaneous codes like BCH.[1] However, despite these promising results, the codes were largely overlooked for decades due to the era's computational limitations, which made the iterative decoding impractical for real-time applications on available hardware. This neglect persisted until the 1990s, predating the invention of turbo codes by over three decades.[12]Modern Rediscovery and Advances
Low-density parity-check (LDPC) codes experienced a significant revival in the late 1990s after decades of obscurity following their initial proposal. In 1997, David J.C. MacKay and Radford M. Neal independently rediscovered Gallager's codes and demonstrated through simulations that LDPC codes, when decoded using belief propagation, could achieve bit error rates near the Shannon limit on binary symmetric and additive white Gaussian noise channels for moderate block lengths. This work highlighted the practical potential of iterative decoding, sparking renewed interest in sparse graph-based codes. Concurrently, in 1997, Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, and Daniel Spielman introduced Tornado codes as a class of highly irregular LDPC codes tailored for efficient erasure correction in multicast scenarios, achieving low encoding and decoding complexity while approaching capacity on binary erasure channels. Key theoretical and design advances followed in the early 2000s, enabling LDPC codes to approach channel capacity more reliably. In 2001, Tom Richardson, Amin Shokrollahi, and Ruediger Urbanke proposed irregular LDPC codes, where variable and check node degrees are non-uniformly distributed to optimize performance; these codes improved decoding thresholds by up to 1 dB closer to capacity compared to regular counterparts on binary-input symmetric channels.[7] The same year, Richardson and Urbanke developed density evolution, an analytical tool that tracks the evolution of message distributions during iterative decoding, allowing precise prediction of code thresholds and guiding the optimization of degree distributions for various channels. These innovations established LDPC codes as capacity-achieving under message-passing decoding, with stability conditions ensuring convergence to low error rates.[13] The practical impact of these rediscoveries materialized through widespread adoption in communication standards. LDPC codes were standardized in the DVB-S2 satellite broadcasting system in 2005, providing rates from 1/4 to 9/10 with performance within 0.7 dB of Shannon limits at a bit error rate of 10^{-5}. They became optional in IEEE 802.11n Wi-Fi (2009) for high-throughput modes, enhancing reliability at data rates up to 600 Mbps, and were integrated into IEEE 802.11ac/ax for even higher speeds. In 5G New Radio (NR), released in 2018, LDPC codes replaced turbo codes for data channels, supporting block lengths up to 8448 bits and rates from 1/3 to 8/9 with low latency decoding suitable for enhanced mobile broadband. In the 2020s, LDPC research has extended to non-binary fields and quantum settings, alongside hardware optimizations for emerging standards. Non-binary LDPC codes over finite fields like GF(256) have gained traction for short-to-medium block lengths in ultra-reliable low-latency communications, offering 1-2 dB gains over binary versions due to better minimum distance properties. Quantum LDPC codes, adapted for stabilizer codes, have advanced with constructions achieving constant relative overhead (e.g., O(1) physical qubits per logical qubit) while tolerating error rates above 1%, as shown in lifted product constructions. For 6G proposals, enhanced LDPC variants like partially information-coupled designs target extreme reliability (error rates below 10^{-9}) and massive connectivity. Hardware accelerations, particularly FPGA implementations, have enabled real-time decoding at throughputs exceeding 1 Gbps for 5G NR codes, reducing power consumption by up to 50% through partially parallel architectures.Code Design and Construction
Matrix Construction Methods
Low-density parity-check (LDPC) codes are defined by their sparse parity-check matrix H, and various methods have been developed to construct H such that the resulting code exhibits strong error-correcting performance. The original construction method, proposed by Robert G. Gallager, generates regular LDPC codes by ensuring fixed column and row weights while maintaining sparsity.[1] In Gallager's approach for a (d_v, d_c)-regular code (where d_v is the column weight and d_c is the row weight), the m rows of H (with m = n(1 - R), n the block length, and R the rate) are partitioned into d_v equal-sized subsets, each containing m/d_v rows.[14] For each subset, exactly one 1 is placed in every column, with positions chosen randomly across the rows in that subset; to achieve the target row weight d_c, this submatrix effectively comprises d_c disjoint permutation matrices summed together, ensuring no multiple 1's in the same row-column pair within the subset.[1] The columns are then randomly permuted within each subset to distribute the 1's evenly and reduce the likelihood of short cycles in the corresponding Tanner graph.[14] This method produces codes with good average performance for large block lengths but can introduce short cycles in smaller codes due to the random placement.[1] A more refined general method is the progressive edge-growth (PEG) algorithm, which constructs the Tanner graph representation of H by incrementally adding edges in a greedy manner to locally maximize the girth (the length of the shortest cycle). Introduced by Hu, Eleftheriou, and Arnold, the PEG algorithm begins with isolated variable and check nodes corresponding to the desired degrees, then adds edges one at a time, starting from the highest-degree nodes. For each new edge connecting a variable node v to an available check node, it selects the check node that results in the longest possible shortest cycle involving the local neighborhood of v, computed via breadth-first search up to a depth related to the target girth.[15] This process continues until all edges are placed, yielding a parity-check matrix with improved cycle distribution compared to purely random methods, particularly for short-to-moderate block lengths. Simulation results demonstrate that PEG-constructed codes achieve thresholds close to density-evolution limits with fewer iterations in belief propagation decoding.[15] Structured constructions offer deterministic and hardware-efficient alternatives to random methods. Protograph-based LDPC codes start with a small protograph—a compact base bipartite graph with a few variable and check node types—and expand it by replacing each edge with a bundle of parallel edges, typically implemented as permutation matrices to preserve sparsity. A prominent example is the accumulate-repeat-accumulate (ARA) code family, developed by Divsalar, Dolinar, and Thorpe, where the protograph incorporates accumulator nodes for rate control and repetition for diversity, resulting in linear-time encodable LDPC codes with thresholds near the Shannon limit.[16] Quasi-cyclic (QC) LDPC codes further enhance structure by composing H from circulant permutation matrices (cyclic shifts of identity matrices), which facilitate parallel hardware implementations and memory-efficient storage.[17] These are particularly adopted in standards like 5G New Radio (NR), where QC-LDPC codes for the physical downlink shared channel support high-throughput rates from 1/3 to 8/9, with base matrices optimized for low latency and flexibility across lifting sizes. In 5G NR, the parity-check matrix is built from a quasi-cyclic structure with two submatrices for systematic encoding, ensuring minimal short cycles through careful shift selections.[18] Key optimization criteria in matrix construction focus on graph properties that enhance decoding convergence. Avoiding short cycles (girth at least 6 or higher) prevents premature convergence in message-passing decoders by reducing correlations in iterative updates on the Tanner graph. Good expansion properties ensure that small sets of variable nodes connect to sufficiently many check nodes, promoting reliable information propagation and approaching capacity. Density evolution serves as a primary validation tool, tracking the probability distribution of log-likelihood ratios during decoding iterations in the asymptotic block-length limit to compute the noise threshold beyond which errors vanish; constructions are refined (e.g., via degree distribution optimization or cycle removal) until this threshold meets or exceeds target performance. As an illustrative example, consider step-by-step construction of a small (3,6)-regular LDPC code with block length n=12 (m=6, rate $1/2) using Gallager's method. Divide the 6 rows into d_v=3 subsets, each with 2 rows (subsets A: rows 1-2, B: rows 3-4, C: rows 5-6). For subset A, partition the 12 columns into two groups of 6 (e.g., columns 1-6 to row 1, 7-12 to row 2) and place 1's in those positions, ensuring one 1 per column; this forms a 2×12 submatrix with row weight 6. Randomly permute the columns within subset A to decorrelate positions (e.g., swap columns 3 and 8). Repeat for subset B: assign another partitioning (e.g., columns 1-3 and 7-9 to row 3, 4-6 and 10-12 to row 4), place 1's, and permute (e.g., cycle shift by 2). For subset C, use a different random partitioning and permutation. The full H combines these submatrices vertically, resulting in a sparse matrix where each column has exactly three 1's (one per subset) and each row has six 1's, with the permutations helping to elongate cycles. For instance, after permutations, a partial H might appear as:This toy example has some structure for clarity but illustrates the process; in practice, random permutations yield a more irregular placement to better avoid 4-cycles.[1]H = [ [1,1,1,1,1,1,0,0,0,0,0,0], // row 1 ([subset](/page/Subset) A, permuted) [0,0,0,0,0,0,1,1,1,1,1,1], // row 2 [1,0,1,0,1,0,1,0,1,0,1,0], // row 3 ([subset](/page/Subset) B, example perm) [0,1,0,1,0,1,0,1,0,1,0,1], // row 4 [1,1,0,0,1,1,0,0,1,1,0,0], // row 5 ([subset](/page/Subset) C, example) [0,0,1,1,0,0,1,1,0,0,1,1] // row 6 ]H = [ [1,1,1,1,1,1,0,0,0,0,0,0], // row 1 ([subset](/page/Subset) A, permuted) [0,0,0,0,0,0,1,1,1,1,1,1], // row 2 [1,0,1,0,1,0,1,0,1,0,1,0], // row 3 ([subset](/page/Subset) B, example perm) [0,1,0,1,0,1,0,1,0,1,0,1], // row 4 [1,1,0,0,1,1,0,0,1,1,0,0], // row 5 ([subset](/page/Subset) C, example) [0,0,1,1,0,0,1,1,0,0,1,1] // row 6 ]
Regular and Irregular Codes
Low-density parity-check (LDPC) codes are classified into regular and irregular variants based on the uniformity of degrees in their associated bipartite Tanner graphs. Regular LDPC codes maintain a fixed variable node degree d_v and a fixed check node degree d_c for all nodes, resulting in a parity-check matrix where each column has exactly d_v ones and each row has exactly d_c ones. A canonical example is the (3,6)-regular LDPC code, where variable nodes connect to three checks and checks connect to six variables, promoting balanced message propagation during decoding.[19] This regularity simplifies matrix construction—often via progressive edge growth or cyclic shifts—and reduces decoding complexity, as all nodes follow identical update rules.[19] However, such codes typically yield performance thresholds that lag behind channel capacity by several decibels, limiting their efficiency in capacity-approaching scenarios.[19] Irregular LDPC codes, by contrast, permit varying degrees among variable and check nodes, allowing tailored distributions that enhance overall error-correcting capability. These are defined by the variable degree distribution polynomial \lambda(x) = \sum_{i=2}^{d_v^{\max}} \lambda_i x^{i-1}, where \lambda_i denotes the fraction of edges connected to degree-i variable nodes, and the check degree distribution \rho(x) = \sum_{j=2}^{d_c^{\max}} \rho_j x^{j-1}, defined analogously for checks.[7] Optimization of \lambda(x) and \rho(x) occurs through methods like density evolution-guided linear programming, which minimizes bit error rates by concentrating low-degree variable nodes for reliable initial messages and higher-degree checks for constraint enforcement.[7] This irregularity produces steeper waterfall performance—rapid error rate drops at moderate signal-to-noise ratios—and suppresses error floors by mitigating trapping sets, outperforming regular codes in both aspects.[7] When comparing the two, irregular LDPC codes achieve error rates substantially closer to Shannon capacity limits, often within 0.1 dB for optimized designs, but incur higher decoding complexity from heterogeneous node processing and larger memory requirements for variable schedules.[7] The key metric distinguishing their efficacy is the threshold \epsilon^*, the highest channel noise level (e.g., erasure probability on the binary erasure channel) under which density evolution predicts vanishing error probability for infinite block lengths. For the binary erasure channel, \epsilon^* solves as the supremum of \epsilon ensuring convergence to zero in the density evolution recursion: x_{\ell+1} = \epsilon \, \lambda \bigl( 1 - \rho(1 - x_\ell) \bigr), with initial condition x_0 = 0, where x_\ell tracks the average erasure probability after \ell iterations.[7] Irregular distributions can push \epsilon^* near the capacity threshold of $1 - R (for rate R), while regular ones plateau lower.[7] Irregular LDPC codes address limitations in outdated regular designs by enabling modern high-throughput applications; for instance, quasi-cyclic irregular constructions are standardized in IEEE 802.11ax (Wi-Fi 6) and IEEE 802.11be (Wi-Fi 7) to deliver robust error correction at multi-gigabit rates over wireless channels.[20]Encoding Techniques
General Encoding Algorithms
Low-density parity-check (LDPC) codes are linear block codes defined by a sparse parity-check matrix \mathbf{H} of size m \times n, where n is the code length and m = n - k with k being the dimension, assuming \mathbf{H} has full row rank. Encoding involves generating a codeword \mathbf{c} = [\mathbf{u} \ | \ \mathbf{p}] from an information vector \mathbf{u} of length k, such that \mathbf{H} \mathbf{c}^T = \mathbf{0}, where \mathbf{p} is the parity vector of length m.[21] In the systematic form, the parity-check matrix is partitioned as \mathbf{H} = [\mathbf{H}_1 \ | \ \mathbf{H}_2], with \mathbf{H}_1 of size m \times k corresponding to information bits and \mathbf{H}_2 of size m \times m to parity bits. This leads to the linear system \mathbf{H}_1 \mathbf{u}^T + \mathbf{H}_2 \mathbf{p}^T = \mathbf{0}, which is solved for \mathbf{p}^T = -\mathbf{H}_2^{-1} \mathbf{H}_1 \mathbf{u}^T. The requirement of full row rank in \mathbf{H} ensures the code has the desired dimension k and that \mathbf{H}_2 is invertible.[21] A straightforward approach to encoding uses the systematic generator matrix \mathbf{G} = [\mathbf{I}_k \ | \ \mathbf{P}], where \mathbf{P} = \mathbf{H}_2^{-1} \mathbf{H}_1 (modulo 2 for binary codes), yielding \mathbf{c} = \mathbf{u} \mathbf{G}. However, since \mathbf{H} is sparse but \mathbf{P} is typically dense, this results in quadratic complexity O(kn), which is inefficient for large n. Direct inversion of \mathbf{H}_2 via Gaussian elimination also incurs O(m^3) complexity, making it impractical for long codes.[21] To exploit the sparsity of \mathbf{H}, efficient algorithms avoid explicit construction of the dense generator matrix. One seminal method, developed by Richardson and Urbanke, transforms \mathbf{H} into an approximate lower triangular form through column permutations, partitioning it into submatrices where a core block is lower triangular. Parity bits are then computed sequentially via back-substitution, solving the system row by row while leveraging sparsity to minimize operations. This achieves near-linear complexity O(n + g^2), where g is a small gap parameter measuring the approximation quality, often approaching O(n) for well-designed codes. For general sparse \mathbf{H}, the overall complexity scales as O(n d_v), with d_v denoting the average column weight (variable node degree).[21] For structured LDPC codes, such as quasi-cyclic constructions where \mathbf{H} comprises circulant permutation matrices, encoding can be further optimized to strict linear time O(n). These methods use cyclic shifts and precomputed scalar multiplications over finite fields (or modulo 2 for binary cases), avoiding matrix-vector multiplications altogether and enabling hardware-efficient implementations via shift registers.Practical Encoder Example
To illustrate the encoding process for a low-density parity-check (LDPC) code, consider the (7,4) Hamming code as a simple example, where the parity-check matrix is sparse with a density of approximately 0.57 ones per entry, qualifying it as a trivial LDPC code.[22] The code has length n=7, dimension k=4, and minimum distance d=3, with the parity-check matrix H defined over GF(2) as follows: H = \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix} [23] This matrix can be partitioned as H = [H1 | H2], where H1 is the 3×4 submatrix corresponding to the information bits and H2 is the 3×3 submatrix for the parity bits, assuming a systematic encoding where the codeword c = [u | p] with information vector u ∈ GF(2)4 and parity vector p ∈ GF(2)3. For u = [1, 0, 1, 1]T, the parity bits are computed by solving the linear system H2 p = H1 u (mod 2). First, compute the syndrome-like vector s = H1 u (mod 2): H_1 = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}, \quad s = H_1 u = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} \pmod{2}. Next, solve H2 p = s (mod 2), where H_2 = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}. The solution yields p = [0, 1, 0]T, so the codeword is c = [1, 0, 1, 1, 0, 1, 0].[24] To verify, compute H cT = 0 (mod 2), confirming c lies in the code: H c^T = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \pmod{2}. [25] The following table summarizes the matrices and vectors in this example:| Component | Value |
|---|---|
| H1 | \begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} |
| H2 | \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} |
| u | [1, 0, 1, 1] |
| p | [0, 1, 0] |
| c | [1, 0, 1, 1, 0, 1, 0] |
Decoding Algorithms
Belief Propagation Decoding
Belief propagation (BP) decoding is a soft-decision iterative algorithm for low-density parity-check (LDPC) codes, operating on the Tanner graph representation of the code to exchange probabilistic messages between variable and check nodes. It initializes messages from variable nodes based on the channel outputs, typically represented as log-likelihood ratios (LLRs), where the LLR for a bit v_i is L_{ch}(v_i) = \log \frac{P(y_i | v_i = 0)}{P(y_i | v_i = 1)}, with y_i denoting the received signal. This approach leverages the sparse structure of the parity-check matrix to approximate maximum a posteriori decoding efficiently. The algorithm proceeds in iterations, alternating between variable-to-check (V2C) and check-to-variable (C2V) message updates until convergence is achieved—such as when all parity checks are satisfied—or a maximum number of iterations is reached. In the sum-product variant, the core of BP, V2C messages convey extrinsic information excluding the target check node, while C2V messages enforce parity constraints. Practical implementations often employ the min-sum approximation to the sum-product algorithm, which replaces nonlinear operations with simpler min and sign computations to reduce complexity while maintaining near-optimal performance. Messages are defined in terms of LLRs for numerical stability. The total LLR at a variable node v is computed asL_v = L_{ch}(v) + \sum_{c \in N(v)} L_{c \to v},
where N(v) is the set of neighboring check nodes, and L_{c \to v} are incoming C2V messages; the outgoing V2C message to a specific check c' excludes L_{c' \to v} to provide extrinsic information. For the C2V message from check node c to variable v, the sum-product update uses the hyperbolic tangent rule:
L_{c \to v} = 2 \tanh^{-1} \left( \prod_{v' \in N(c) \setminus v} \tanh \left( \frac{L_{v' \to c}}{2} \right) \right),
where N(c) denotes neighboring variables; the min-sum approximation simplifies this to
L_{c \to v} = \prod_{v' \in N(c) \setminus v} \operatorname{sign}(L_{v' \to c}) \cdot \min_{v' \in N(c) \setminus v} |L_{v' \to c}|.
After each iteration, hard decisions are made from the total LLRs, and the process repeats. The success of BP decoding depends on the channel noise level relative to the code's design threshold, determined via density evolution analysis, which tracks message distributions over iterations assuming a tree-like graph structure. If the noise (e.g., standard deviation \sigma in AWGN channels) is below this threshold, the bit error rate approaches zero as block length increases; otherwise, decoding fails with positive error probability. For well-designed irregular LDPC codes, thresholds can approach the Shannon limit within 0.06 dB.[7]