English top / Japanese version

Post-Processing Algorithms after BP Decoding

This page is a research note on post-processing methods used after belief-propagation (BP) decoding for CSS quantum LDPC codes. The goal is to organize how local repair, greedy flipping, OSD-type post-processing, and linear-equation post-processing can be used to repair residual syndrome mismatches after BP decoding.

Basic Form of CSS Post-Processing

Let \(H_X,H_Z\) be the parity-check matrices of a CSS code, and let \[ \hat{x},\hat{z}\in\mathbb F_2^n \] be the error estimates after BP. If the true syndromes are written as \[ s_X=H_X z_{\mathrm{true}},\qquad s_Z=H_Z x_{\mathrm{true}}, \] then the residual syndromes after BP are \[ r_X=s_Z+H_Z\hat{x},\qquad r_Z=s_X+H_X\hat{z}. \] All sums are over \(\mathbb F_2\), i.e., XORs.

Post-processing searches for additional corrections \(\delta_X,\delta_Z\) satisfying \[ H_Z\delta_X=r_X,\qquad H_X\delta_Z=r_Z. \] Updating \[ \hat{x}'=\hat{x}+\delta_X,\qquad \hat{z}'=\hat{z}+\delta_Z \] then gives syndrome-valid estimates: \(H_Z\hat{x}'=s_Z\) and \(H_X\hat{z}'=s_X\).

List of Post-Processing Algorithms

Literature Context

The implementation names on this page are not always standard names in the literature. Still, several connections should be cited explicitly. The flipping part of greedy_reduction and flip_pp is close in spirit to Gallager-type bit-flipping decoding. osd_lite, k_osd, and k_osd_global should be read as lightweight variants of OSD and BP+OSD post-processing. ets_library belongs to the trapping-set and quantum-trapping-set context. The routines local_exact, component_exact, and global_solve are described here as GF(2) syndrome-repair implementations, not as claims of a new decoding principle.

• R. G. Gallager, Low-Density Parity-Check Codes, MIT Press, 1963. A foundational reference for LDPC codes, iterative decoding, and bit-flipping-style decoding.
• R. Tanner, “A recursive approach to low complexity codes,” IEEE Transactions on Information Theory, 1981. The standard graph representation behind Tanner-graph locality.
• T. J. Richardson, “Error floors of LDPC codes,” Allerton, 2003. A standard starting point for trapping sets and LDPC error-floor analysis.
• N. Raveendran and B. Vasić, “Trapping Sets of Quantum LDPC Codes,” Quantum 5, 562, 2021. A quantum-LDPC formulation of trapping sets.
• M. P. C. Fossorier and S. Lin, “Soft-decision decoding of linear block codes based on ordered statistics,” IEEE Transactions on Information Theory, 1995. The classical OSD reference.
• M. P. C. Fossorier, S. Lin, and J. Snyders, “Reliability-based syndrome decoding of linear block codes,” IEEE Transactions on Information Theory, 1998. A closely related reference for reliability-ordered syndrome decoding.
• P. Panteleev and G. Kalachev, “Degenerate Quantum LDPC Codes With Good Finite Length Performance,” Quantum 5, 585, 2021. A representative BP+OSD reference for quantum LDPC codes.
• J. Roffe, D. R. White, S. Burton, and E. Campbell, “Decoding across the quantum low-density parity-check code landscape,” Physical Review Research 2, 043423, 2020. A broad numerical study of BP+OSD decoders for quantum LDPC codes.

Reproducible Specification

Each algorithm can be implemented as a subroutine for one linear problem \[ H\delta=r. \] The input is a parity-check matrix \(H\in\mathbb F_2^{m\times n}\), a residual syndrome \(r\in\mathbb F_2^m\), BP-derived flip costs \(c_i\), and search parameters. The output is success and a correction vector \(\delta\in\mathbb F_2^n\). If success=true, the implementation must verify \(H\delta=r\).

A smaller flip cost means that flipping the variable is considered more plausible. To make the algorithms reproducible, ties are broken by increasing variable index. Thus the candidate order \(\pi\) satisfies \[ (c_{\pi(1)},\pi(1))\le(c_{\pi(2)},\pi(2))\le\cdots. \]

Common input:
  H: binary parity-check matrix, represented by column supports h_i
  r: residual syndrome vector in F_2^m
  c_i: BP flip cost for variable i
  params:
    radius, max_weight, max_nodes
    K or K_max
    total_syndrome_limit

Common output:
  success: boolean
  delta: binary vector in F_2^n

Required final check:
  success is true only if H * delta == r over F_2.

Common Subroutines

Fixing the following subroutines makes the algorithms easier to reproduce exactly.

ones(r):
  return sorted list of check indices a with r[a] = 1

apply_flip(r, i):
  return r + h_i over F_2

score_flip(r, i):
  return weight(r) - weight(r + h_i)

ordered_variables(c):
  return variables sorted by (c_i, i)

gf2_solve(H, r, V):
  # Solve H[:, V] * u = r.
  # Columns are processed in the given order of V.
  # Maintain a row-pivot basis over F_2.
  # Pivot row convention: use the smallest row index whose bit is 1.
  # Each pivot stores both a syndrome vector and the combination of V-columns
  # that produced it.
  basis = empty map: pivot_row -> (syndrome_vector, combination_vector)
  for position j, variable i in enumerate(V):
    v = column H[:, i]
    comb = unit vector e_j
    while v != 0 and basis has pivot p = min {a : v[a] = 1}:
      v = v + basis[p].syndrome_vector
      comb = comb + basis[p].combination_vector
    if v != 0:
      p = min {a : v[a] = 1}
      basis[p] = (v, comb)

  rhs = r
  sol = zero vector of length |V|
  while rhs != 0 and basis has pivot p = min {a : rhs[a] = 1}:
    rhs = rhs + basis[p].syndrome_vector
    sol = sol + basis[p].combination_vector
  if rhs != 0:
    return (false, zero vector in F_2^n)
  delta = zero vector in F_2^n
  for j with sol[j] = 1:
    delta[V[j]] = 1
  return (true, delta)

Pseudocode for Each Algorithm

ets_library(H, r, library):
  S = ones(r)
  if |S| != 2:
    return (false, 0)
  let S = {c0, c1} with c0 < c1
  for each library entry V registered for key (c0, c1):
    delta = indicator(V)
    if H * delta == r over F_2:
      return (true, delta)
  return (false, 0)

postprocess_dispatch(H, r, c, library, params):
  if weight(r) == 0:
    return (true, 0, "none")
  if weight(r) == 2:
    ok, delta = ets_library(H, r, library)
    if ok:
      return (true, delta, "ets_library")
  for method in [local_exact, component_exact, k_osd, osd_lite, flip_pp, flip_history, global_solve]:
    ok, delta = method(H, r, c, params)
    if ok and H * delta == r:
      return (true, delta, method.name)
  return (false, 0, "failed")

local_exact(H, r, c, params):
  S = ones(r)
  if S is empty:
    return (true, 0)
  if |S| > params.total_syndrome_limit:
    return (false, 0)

  V = variables within Tanner-graph distance params.radius from S
  V = V sorted by (c_i, i)

  # Exact bounded search, preferred for very small V or small max_weight.
  search subsets A of V in increasing size, then lexicographic order
  stop when size(A) > params.max_weight or visited nodes > params.max_nodes
  if XOR_{i in A} h_i == r:
    return (true, indicator(A))

  # Optional deterministic fallback on the same local candidate set.
  return gf2_solve(H, r, V)

component_exact(H, r, c, params):
  S = ones(r)
  if S is empty:
    return (true, 0)

  Build the Tanner subgraph induced by unsatisfied checks S,
  their neighboring variables, and checks touched by those variables.
  Decompose this subgraph into connected components C_1, ..., C_t.

  delta = 0
  for each component C_j:
    r_j = r restricted to checks in C_j
    V_j = variables in C_j, optionally enlarged by params.radius
    Run local_exact on (H[:, V_j], r_j) with the inherited costs.
    If it fails:
      return (false, 0)
    Add the component correction into delta.

  if H * delta == r:
    return (true, delta)
  return (false, 0)

greedy_reduction(H, r, c, params):
  delta = 0
  current = r
  repeat:
    choose i maximizing (score_flip(current, i), -c_i, -i)
    if score_flip(current, i) <= 0:
      break
    current = current + h_i
    delta[i] = delta[i] + 1
    stop if number of flips exceeds params.max_nodes

  if current == 0:
    return (true, delta)
  return (false, delta)  # useful as a partial correction

osd_lite(H, r, c, params):
  ordered = ordered_variables(c)
  V = first params.K variables of ordered
  return gf2_solve(H, r, V)

k_osd(H, r, c, params):
  ordered = ordered_variables(c)
  lo = 0
  hi = params.K_max
  if gf2_solve(H, r, first hi variables) fails:
    return (false, 0)

  while lo + 1 < hi:
    mid = floor((lo + hi) / 2)
    if gf2_solve(H, r, first mid variables) succeeds:
      hi = mid
    else:
      lo = mid

  return gf2_solve(H, r, first hi variables)

flip_pp(H, r, c, params):
  (greedy_ok, delta_g) = greedy_reduction(H, r, c, params)
  r2 = r + H * delta_g
  if r2 == 0:
    return (true, delta_g)

  Update costs if the implementation supports it; otherwise reuse c.
  (osd_ok, delta_o) = k_osd(H, r2, c, params)
  if not osd_ok:
    (osd_ok, delta_o) = osd_lite(H, r2, c, params)
  if not osd_ok:
    return (false, delta_g)

  delta = delta_g + delta_o
  if H * delta == r:
    return (true, delta)
  return (false, 0)

flip_history(H, r, c, hard_history, params):
  # hard_history[i] records BP-side evidence for variable i.
  # A typical score adds:
  #   +1 for each BP iteration where variable i is decided as 1,
  #   +2 for each hard-decision change between consecutive iterations.
  V = {i : hard_history[i] > 0}
  V = V sorted by (-hard_history[i], -touches(i, ones(r)), c_i, i)
  if |V| > params.K_max:
    V = first params.K_max variables of V
  return gf2_solve(H, r, V)

global_solve(H, r, c, params):
  ordered = ordered_variables(c)
  V = all variables in ordered order
  return gf2_solve(H, r, V)

k_osd_global(H, r, c, params):
  (ok, delta) = k_osd(H, r, c, params)
  if ok:
    return (true, delta)
  return global_solve(H, r, c, params)

For CSS decoding, use \(H_Z\delta_X=r_X\) for the X-error post-processing side, and \(H_X\delta_Z=r_Z\) for the Z-error post-processing side. A clean implementation updates \(\hat{x}'=\hat{x}+\delta_X\) and \(\hat{z}'=\hat{z}+\delta_Z\) only when both sides succeed.

Details of Each Algorithm

In this section, one side of the post-processing problem is written as \[ H\delta=r. \] Here \(H\) is the relevant parity-check matrix, \(r\) is the residual syndrome after BP, and \(\delta\) is the additional binary correction. For a CSS code, the same idea is applied separately to the X and Z sides.

ets_library

ets_library is the first post-processing branch to try when the residual syndrome has weight two. The two unsatisfied checks \(\{c_0,c_1\}\) are used as a key into a library of elementary trapping sets (ETSs) whose odd-check set is exactly those two checks.

A registered candidate \(V\) is not applied blindly. The decoder first checks \[ H\mathbf{1}_V=r. \] Only a verified candidate is returned as \(\delta=\mathbf{1}_V\). If no candidate is registered or the verification fails, the decoder falls back to local_exact, k_osd, global_solve, or another generic repair method.

This branch is placed first because weight-two residual syndromes are often caused by a local ETS. Using the known structure is cheaper and easier to interpret than immediately invoking OSD or an all-variable linear solve. For background, see the classical trapping-set formulation of Richardson and the quantum-LDPC extension of Raveendran--Vasić.

local_exact

local_exact searches for an exact correction in a small neighborhood of the unsatisfied checks. Let \[ S=\{a:r_a=1\} \] be the set of unsatisfied check nodes. The algorithm takes variable nodes that are close to \(S\) in the Tanner graph and forms a local candidate set \(V_{\mathrm{loc}}\). It then tries to solve \[ H_{[:,V_{\mathrm{loc}}]}\delta_{\mathrm{loc}}=r \] by a depth-limited search or by small GF(2) elimination.

The intended regime is that BP has almost succeeded and only a small local inconsistency remains. Because the candidate region is small, the method is cheap. It fails when the residual syndrome is spread over a large region, or when the variables needed for the repair lie outside the chosen local neighborhood. This is best viewed as an implementation pattern based on Tanner-graph locality Tanner and trapping-set neighborhoods Richardson, rather than as a separately standardized decoder name.

component_exact

component_exact decomposes the residual syndrome into connected components in the Tanner graph and solves each component as a smaller exact-repair problem. Starting from the unsatisfied check set \(S\), it builds the induced subgraph containing the relevant variable and check nodes, and decomposes it into connected components \[ C_1,C_2,\ldots,C_t. \] For each component \(C_j\), it forms a local variable set \(V_j\) and solves \[ H_{[:,V_j]}\delta_j=r_j. \] The final correction is the sum of the component corrections, \(\delta=\sum_j\delta_j\).

If the residual really separates into small components, the search complexity is controlled by the component sizes rather than by the full blocklength. If the residual forms one giant component, however, the benefit of this decomposition largely disappears. The decomposition is an implementation device on the Tanner graph Tanner; it should be interpreted as exact repair on small connected components, not as a separate new decoding principle.

greedy_reduction

greedy_reduction repeatedly flips the variable that most decreases the residual syndrome weight. If variable \(i\) is flipped, the residual syndrome is updated as \[ r\leftarrow r+h_i, \] where \(h_i\) is the \(i\)-th column of \(H\). At each step, the score \[ \Delta_i=|r|-|r+h_i| \] is computed, and a variable with the largest positive \(\Delta_i\) is flipped.

This is very fast and is useful as a first stage that reduces the residual before a more expensive solver is invoked. The limitation is that a locally best flip is not necessarily on a path to a good final correction. The algorithm may stop when all single flips are non-improving, even though a multi-bit correction exists. Natural references are Gallager's LDPC decoding Gallager and trapping-set analysis for flipping decoders Richardson.

osd_lite

osd_lite is a lightweight OSD-type method. It uses BP reliability information to select a candidate set and then solves the syndrome equation restricted to that set. Each variable is assigned a flip cost \(c_i\), and the variables with the smallest costs form \[ V_K=\{\pi(1),\ldots,\pi(K)\}. \] The restricted equation \[ H_{[:,V_K]}\delta_K=r \] is solved by GF(2) elimination. If it is solvable, variables outside \(V_K\) are kept at zero and variables inside \(V_K\) are flipped according to \(\delta_K\).

The key point is that OSD-lite does not search all variables. It trusts BP enough to restrict the search to variables that look unreliable. This can be powerful and cheap when the candidate set is adequate, but it fails if the required columns are not included. The underlying OSD reference is Fossorier--Lin; for reliability-ordered syndrome decoding see Fossorier--Lin--Snyders; for BP+OSD in quantum LDPC decoding see Panteleev--Kalachev and Roffe et al..

k_osd

k_osd removes the need to fix the OSD-lite candidate size in advance. It sorts the columns by BP cost, \[ \pi(1),\pi(2),\ldots,\pi(n), \] and considers prefixes \[ V_K=\{\pi(1),\ldots,\pi(K)\}. \] For each prefix, it checks whether \(H_{[:,V_K]}\delta_K=r\) is solvable. As \(K\) increases, the column span can only grow, so solvability is monotone and the smallest usable \(K\) can be found by binary search.

If a small prefix is sufficient, the resulting correction is compact and aligned with the BP reliability ordering. If \(K\) becomes too large, however, the system has many more degrees of freedom, and a syndrome-valid but logically poor correction may become easier to select. The maximum prefix length, ordering rule, and tie-breaking rule therefore matter. Its literature context is the same as osd_lite: OSD Fossorier--Lin and BP+OSD for quantum LDPC codes Panteleev--Kalachev, Roffe et al., with the candidate selection changed into a prefix-length search.

flip_pp

flip_pp is a two-stage method. First it applies a greedy flipping stage to reduce the residual syndrome and records the partial correction \(\delta_{\mathrm{flip}}\). The remaining residual is \[ r'=r+H\delta_{\mathrm{flip}}. \] Then k_osd or osd_lite is applied to \(r'\), producing \(\delta_{\mathrm{osd}}\). The final correction is \[ \delta=\delta_{\mathrm{flip}}+\delta_{\mathrm{osd}}. \]

The advantage is that the greedy stage can shrink a large residual before the linear solver is called. This can make OSD-type post-processing easier. The drawback is that the greedy choices can also change the later candidate ordering or residual structure in an unfavorable way. The relevant references are bit-flipping decoding for the first stage Gallager and BP+OSD post-processing for the second stage Panteleev--Kalachev, Roffe et al..

flip_history

flip_history is a linear-solver post-processing method whose candidate set is built from the history of BP hard decisions. For each variable \(i\), record how often the hard decision was 1 during BP iterations, and how often it changed between consecutive iterations. This gives a history score such as \[ h_i=\#\{t:\hat{x}_i^{(t)}=1\}+2\#\{t:\hat{x}_i^{(t)}\ne \hat{x}_i^{(t-1)}\}. \] The same construction is used on the other CSS side.

The post-processing candidate set is \(V=\{i:h_i>0\}\). Variables are ordered by decreasing history score, decreasing number of incident unsatisfied checks, increasing BP flip cost, and then increasing index. The method then solves \[ H_{[:,V]}\delta_V=r \] over GF(2). The intent is to repair the syndrome using only variables that BP visited or oscillated on during the iterative process.

This differs from ordinary cost-ordered OSD because it uses temporal information from BP, not only final reliabilities. The linear solve itself is still OSD-like: if the required columns are absent from the history-based candidate set, the method fails. Also, a syndrome-valid particular solution is not necessarily logically correct, so syndrome validity and logical validity should be logged separately. Its literature context is best described as an implementation variant between bit-flipping decoding Gallager and reliability-ordered syndrome decoding Fossorier--Lin--Snyders.

global_solve

global_solve is an all-variable fallback. It does not restrict the candidate set; instead, it directly solves \[ H\delta=r \] using all columns of \(H\). The columns are usually ordered by BP flip cost, and GF(2) elimination returns one particular solution in that order. Since no candidate columns are discarded, the method finds a syndrome-valid correction whenever \(r\) is in the column span of \(H\).

This only guarantees syndrome validity. The returned solution is not necessarily minimum-weight, maximum-likelihood, or logically correct. For performance evaluation, it is therefore important to distinguish syndrome-valid repairs from logically valid repairs. This is not claimed as a standard named BP post-processing algorithm; it is an implementation fallback that returns one particular solution of a GF(2) linear system. Its relation to reliability-ordered syndrome decoding is closest to Fossorier--Lin--Snyders.

k_osd_global

k_osd_global first tries k_osd, and uses global_solve only if K-OSD cannot solve the residual syndrome. The intended behavior is to handle ordinary failures with a BP-reliability-guided prefix, while keeping the all-variable solve as a last-resort fallback when the required columns are outside the K-OSD prefix.

This is a practical way to balance cost and success probability. Results should still record which path was used. A case solved by K-OSD and a case solved only by global solve are both syndrome-valid, but they may have different logical-failure behavior. It is best positioned as a BP+OSD-style decoder Panteleev--Kalachev, Roffe et al. with an all-variable linear fallback.

How Linear-Solver Post-Processing Chooses a Solution

osd_lite, k_osd, flip_history, and global_solve share the same linear-algebraic core: choose a candidate variable set \(V\), and solve \[ H_{[:,V]}\delta_V=r \] by GF(2) elimination. The difference is how \(V\) is chosen. osd_lite uses a fixed-size candidate set, k_osd searches for a solvable prefix length, flip_history uses a candidate set built from BP iteration history, and global_solve uses all variables.

If variables are ordered by increasing BP flip cost \(c_i\), with order \(\pi\), the candidate columns are arranged as \[ H_{\pi,V}=[h_{\pi(1)}\ h_{\pi(2)}\ \cdots]. \] GF(2) elimination returns one particular solution determined by this column order. Thus linear-solver post-processing generally does not choose a minimum-weight vector from the full solution space.

Input: H, residual syndrome r, BP flip costs c_i, candidate rule
1. Sort variables by increasing c_i:
       ordered = [pi(1), pi(2), ..., pi(n)]
2. Choose a candidate set V from ordered variables.
3. Build a GF(2) pivot basis from columns H[:, i] for i in V.
4. Reduce rhs = r by the pivot basis.
5. If solvable, flip variables specified by the returned particular solution.

The Solution Is Not Unique

The linear equation solved by post-processing is generally \[ H\delta=r,\qquad H\in\mathbb F_2^{m\times n}. \] If \(H\) does not have full column rank, the solution is generally not unique. Once one solution \(\delta_0\) is found, \[ \delta_0+\ker(H) \] gives the full affine space of solutions. In particular, if \(n>\mathrm{rank}(H)\), then \[ \dim\ker(H)=n-\mathrm{rank}(H)>0. \]

Thus linear-solver post-processing selects one particular solution determined by the candidate set and column order. This is why a separate logical-failure check is necessary.

Implementation Notes

• Linear-solver post-processing is a way to remove syndrome failure; in general, it is not minimum-weight decoding.
• It is in the same broad family as BP+OSD-type post-processing, and should be treated as an implementation fallback rather than as a new decoding principle.
• For later comparison, it is useful to log the number and locations of flips, as well as the candidate-prefix length, also on successful repairs.