日本語トップへ / English top / English version

BP後処理アルゴリズムの整理

このページは、CSS量子LDPC符号に対して belief propagation (BP) 復号を行った後、 残ったシンドローム不一致を修復する後処理を整理するための研究メモです。 とくに、BP後の residual syndrome に対して、局所探索、貪欲反転、 OSD型後処理、線形方程式型後処理をどのように使い分けるかをまとめます。

後処理でシンドローム条件を満たせても、論理的に正しい復号が保証されるとは限りません。 論理失敗率を評価するには、最後に \(\hat{x}+x_{\mathrm{true}}\in\mathrm{Row}(H_X)\) および \(\hat{z}+z_{\mathrm{true}}\in\mathrm{Row}(H_Z)\) を確認する必要があります。

CSS復号後処理の基本形

CSS符号の検査行列を \(H_X,H_Z\) とし、BP後の推定誤りを \[ \hat{x},\hat{z}\in\mathbb F_2^n \] とします。真のシンドロームを \[ s_X=H_X z_{\mathrm{true}},\qquad s_Z=H_Z x_{\mathrm{true}} \] と書くと、BP後の残留シンドロームは \[ r_X=s_Z+H_Z\hat{x},\qquad r_Z=s_X+H_X\hat{z} \] です。すべての和は \(\mathbb F_2\) 上の和、つまりXORです。

後処理は、追加補正 \(\delta_X,\delta_Z\) を求めて \[ H_Z\delta_X=r_X,\qquad H_X\delta_Z=r_Z \] を満たすようにし、 \[ \hat{x}'=\hat{x}+\delta_X,\qquad \hat{z}'=\hat{z}+\delta_Z \] と更新します。これにより、少なくともシンドローム条件は \(H_Z\hat{x}'=s_Z\), \(H_X\hat{z}'=s_X\) になります。

後処理アルゴリズム一覧

名前 方針 長所 注意点
ets_library 残留シンドローム重みが2のとき、2個のodd checkをキーにETSライブラリを引く。 典型的な2-check trapping setを決定的かつ軽く修復できる。 登録済みETSがない場合、または生成シンドローム検証に失敗した場合はfallbackする。
local_exact 残留シンドローム重みが小さいとき、近傍の変数だけで深さ制限付き探索を行う。 軽い。局所的な小さい失敗に効く。 大きい残留シンドロームには届かない。
component_exact 残留シンドロームを連結成分に分け、各成分に局所exact repairをかける。 分離した小成分に強い。 巨大成分や密な残留には弱い。
greedy_reduction 反転によって残留シンドローム重みを最も減らす変数を貪欲に選ぶ。 実装が単純で速い。 局所最適に止まりやすい。
osd_lite BPの反転コストが小さい候補集合を作り、その候補列で \(H\delta=r\) をGF(2)消去する。 BP+OSD型の標準的な後処理に近い。 候補集合に必要な列が入らないと失敗する。
k_osd 候補列をBP信頼度順に並べ、解ける最小の候補prefix長 \(K\) を二分探索する。 OSD-liteより候補数を制御しやすい。 候補prefixに必要な列がなければ失敗する。
flip_pp まずシンドローム重みを貪欲に落とし、残りをK-OSDまたはOSD-liteで詰める。 大きい残留を小さくしてから線形ソルバに渡せる。 貪欲選択が後の解を悪くすることがある。
flip_history BP反復中に不安定だった変数、または繰り返し反転候補になった変数だけを候補集合にして \(H\delta=r\) を解く。 BPが迷った局所領域に候補を絞れる。 必要な列が履歴候補に入らないと、シンドロームを消せない。
global_solve 全 \(n\) 変数を候補にして \(H\delta=r\) をGF(2)消去で直接解く。 シンドロームを満たす解がある限り、syndrome failureを消せる。 返るのは特解であり、最小重み解や最尤解ではない。
k_osd_global まずK-OSDを試し、失敗したらglobal_solveへフォールバックする。 通常はK-OSDを使い、必要なときだけ全変数ソルバに落とせる。 global_solveに落ちた場合は論理失敗の確認が重要。
推奨される分岐順序は、まず residual syndrome weight が2なら ets_library を試し、 登録済み候補が実際に \(H\delta=r\) を満たすことを検証してから適用する、というものです。 ETSで解けない場合だけ、局所探索、OSD型後処理、最後のfallbackとして global_solve に進みます。

文献の位置づけ

このページの名前付き実装は、標準文献にそのまま同じ名前で現れるとは限りません。 ただし、明らかに参照すべき背景があります。greedy_reduction と flip_pp の反転部分は Gallager 型の bit-flipping 復号に近く、 osd_lite, k_osd, k_osd_global は OSDおよびBP+OSD型後処理の簡略版または変形として読むのが自然です。 ets_library は trapping set / quantum trapping set の文脈にあります。 local_exact, component_exact, global_solve は、 ここでは実装上のGF(2) syndrome repairとして記述しており、固有の新しい復号原理として主張しません。

再現用の共通仕様

各アルゴリズムは、片側の線形問題 \[ H\delta=r \] を解くサブルーチンとして実装できます。入力は、検査行列 \(H\in\mathbb F_2^{m\times n}\)、 残留シンドローム \(r\in\mathbb F_2^m\)、BPから得られる変数ごとの反転コスト \(c_i\)、および探索パラメータです。出力は success と補正ベクトル \(\delta\in\mathbb F_2^n\) です。 success=true のときは必ず \(H\delta=r\) を満たすことを確認します。

反転コストは、小さいほど「反転してもよさそう」と解釈します。 実装を再現可能にするため、同じコストの変数はインデックス昇順で並べます。 つまり候補順序 \(\pi\) は \[ (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.

共通サブルーチン

以下のサブルーチンを固定しておくと、各アルゴリズムを一意に再現しやすくなります。 

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)

各アルゴリズムの擬似コード

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 in which 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)

CSS復号では、X誤りの後処理に \(H_Z\delta_X=r_X\) を使い、 Z誤りの後処理に \(H_X\delta_Z=r_Z\) を使います。両方が成功した場合だけ \(\hat{x}'=\hat{x}+\delta_X\), \(\hat{z}'=\hat{z}+\delta_Z\) に更新する、 という扱いにすると実装が明確になります。

各アルゴリズムの詳細

以下では、片側の後処理を \[ H\delta=r \] と書いて説明します。ここで \(H\) は該当する検査行列、\(r\) はBP後に残った residual syndrome、\(\delta\) は追加で反転する変数ベクトルです。 CSS符号では、X側とZ側に同じ考え方をそれぞれ適用します。

ets_library

ets_library は、residual syndrome weight が2である場合に最初に試すべき 専用後処理です。2個のunsatisfied check \(\{c_0,c_1\}\) をキーとして、 その2 checkをodd-check集合にもつ elementary trapping set (ETS) の変数集合 \(V\) を ライブラリから検索します。

登録された候補 \(V\) は、そのまま信用して反転するのではなく、必ず \[ H\mathbf{1}_V=r \] を満たすことを確認してから適用します。検証に成功した場合だけ \(\delta=\mathbf{1}_V\) を返し、候補がない場合や検証に失敗した場合は local_exact, k_osd, global_solve などへfallbackします。

この分岐を先に置く理由は、weight-2 residual syndrome が局所的なETSに由来することが多く、 OSDや全変数線形ソルバよりも、既知の構造を使う方が軽く、解釈もしやすいからです。 背景としては trapping set の古典的定式化 Richardson と、量子LDPC符号での拡張 Raveendran--Vasić を参照してください。

local_exact

local_exact は、残留シンドロームが小さい場合に、その近傍だけで \(H\delta=r\) を正確に満たす小さい補正を探す方法です。まず \[ S=\{a:r_a=1\} \] を満たされていない検査ノードの集合とし、Tanner graph上で \(S\) から距離が近い 変数ノードだけを候補集合 \(V_{\mathrm{loc}}\) とします。その上で \[ H_{[:,V_{\mathrm{loc}}]}\delta_{\mathrm{loc}}=r \] を満たす低重みの \(\delta_{\mathrm{loc}}\) を、深さ制限付き探索または小さいGF(2)消去で探します。

この方法の狙いは、「BPはほとんど合っていて、最後に局所的な矛盾だけが残った」 状況を安く修復することです。候補領域を狭くするので高速ですが、残留シンドロームが 広く分布している場合や、必要な補正が候補領域の外にある場合は失敗します。 固有の標準名を持つアルゴリズムというより、Tanner graph 上の局所性 Tanner と trapping set 近傍探索 Richardson に基づく実装パターンです。

component_exact

component_exact は、残留シンドロームの支持をTanner graph上で連結成分に分け、 各成分を独立した小問題として解く方法です。満たされていない検査集合 \(S\) から、 関係する変数ノードと検査ノードを含む誘導部分グラフを作り、その連結成分を \[ C_1,C_2,\ldots,C_t \] と分解します。各成分 \(C_j\) について局所候補変数 \(V_j\) を作り、 \[ H_{[:,V_j]}\delta_j=r_j \] を解いて、最後に \(\delta=\sum_j\delta_j\) と合成します。

成分が本当に分離している場合、探索空間は全体ではなく各成分の大きさで決まるため、 計算量を大きく下げられます。一方、残留シンドロームが一つの巨大成分に連結してしまうと、 local_exact と同様に探索が重くなり、成分分解の利点は小さくなります。 この成分分解は Tanner graph 表現 Tanner 上の実装上の工夫であり、独立した新しい復号原理としてではなく、 小さい連結成分に対する exact repair として扱います。

greedy_reduction

greedy_reduction は、残留シンドローム重みを直接減らす変数を順に反転する方法です。 変数 \(i\) を反転すると、残留シンドロームは \[ r\leftarrow r+h_i \] と更新されます。ここで \(h_i\) は \(H\) の第 \(i\) 列です。各ステップで \[ \Delta_i=|r|-|r+h_i| \] が最大の変数を選び、\(\Delta_i>0\) の間だけ反転を続けます。

この方法は非常に軽く、前処理として残留シンドロームを小さくする用途に向いています。 ただし、局所的に重みを減らす反転が常に正しい補正に近づくとは限りません。 途中で \(\Delta_i\le0\) になって止まっても、複数ビットを同時に反転すれば解ける場合があります。 反転規則の背景としては、Gallager のLDPC復号 Gallager と、反転復号に対する trapping set 解析 Richardson が自然な参照です。

osd_lite

osd_lite は、BPの信頼度情報を使って候補変数を絞り、その候補上で 線形方程式を解く簡易OSD型の後処理です。BP後の各変数について、反転した方がよさそうな度合いを コスト \(c_i\) として計算し、コストの小さい変数から候補集合 \[ V_K=\{\pi(1),\ldots,\pi(K)\} \] を作ります。そして \[ H_{[:,V_K]}\delta_K=r \] をGF(2)消去で解きます。解けた場合は、候補集合の外では0、候補集合の中では \(\delta_K\) に従って反転します。

重要なのは、OSD-liteが「全変数から最適解を探す」のではなく、 BPが怪しいと判断した比較的小さい候補集合に探索を制限する点です。 候補集合が十分なら軽く強力ですが、必要な変数が候補から漏れると、線形方程式自体が解けません。 OSDそのものは Fossorier--Lin、syndrome decoding版の信頼度順序は Fossorier--Lin--Snyders、量子LDPCでのBP+OSD利用は Panteleev--Kalachev と Roffe et al. を参照してください。

k_osd

k_osd は、OSD-liteの候補数 \(K\) を固定せず、 解ける最小の候補prefixを探す方法です。BPコスト順の列順序 \[ \pi(1),\pi(2),\ldots,\pi(n) \] を作り、prefix \[ V_K=\{\pi(1),\ldots,\pi(K)\} \] に対して \(H_{[:,V_K]}\delta_K=r\) が解けるかを調べます。 \(K\) を増やすほど列空間は広がるので、解けるかどうかは単調になり、 二分探索で必要な候補数を絞れます。

この方法では、小さい \(K\) で解ければBPの信頼度に沿ったコンパクトな補正が得られます。 一方で、\(K\) を大きくしすぎると自由度が増え、シンドロームは満たしても論理的に悪い補正を 選びやすくなる場合があります。そのため、候補順序、最大 \(K\)、タイブレークの設計が重要です。 基本的な文献上の位置づけは osd_lite と同じで、OSD Fossorier--Lin および量子LDPCのBP+OSD Panteleev--Kalachev, Roffe et al. の候補選択を prefix 長探索にした実装変形です。

flip_pp

flip_pp は、貪欲な反転とOSD型の線形ソルバを組み合わせる二段階方式です。 まず greedy_reduction と同じ考え方で残留シンドローム重みを下げ、 途中の補正を \(\delta_{\mathrm{flip}}\) とします。その後、更新後の残留 \[ r'=r+H\delta_{\mathrm{flip}} \] に対して k_osd や osd_lite を適用し、 追加補正 \(\delta_{\mathrm{osd}}\) を求めます。最終的な補正は \[ \delta=\delta_{\mathrm{flip}}+\delta_{\mathrm{osd}} \] です。

利点は、線形ソルバに渡す前に問題を小さくできることです。特に、残留シンドロームが大きくて OSD候補だけでは扱いにくいときに有効です。欠点は、最初の貪欲反転が後段の候補順序や 解空間を悪化させる可能性があることです。 参照すべき背景は、前段については bit-flipping 型復号 Gallager、後段についてはBP+OSD型後処理 Panteleev--Kalachev, Roffe et al. です。

flip_history

flip_history は、BP反復の履歴から候補集合を作る線形ソルバ型の後処理です。 各変数 \(i\) について、BP反復中の hard decision が何度 1 になったか、 あるいは連続する反復間で何度変化したかを数え、履歴スコア \(h_i\) を作ります。 例えば \[ h_i=\#\{t:\hat{x}_i^{(t)}=1\}+2\#\{t:\hat{x}_i^{(t)}\ne \hat{x}_i^{(t-1)}\} \] のように定義できます。Z側も同様です。

後処理では \(h_i>0\) の変数だけを候補集合 \(V\) とし、履歴スコアの大きい順、 残留シンドロームとの接触数の大きい順、BP flip cost の小さい順で並べます。 その候補集合に対して \[ H_{[:,V]}\delta_V=r \] をGF(2)消去で解きます。狙いは、BPが反復中に迷っていた変数だけを使って syndrome repairを行うことです。

この方法は、BPの時間方向の情報を候補選択に使う点で、通常のコスト順OSDとは少し違います。 ただし線形ソルバの部分はOSD型後処理と同じで、候補集合に必要な列が含まれない場合は失敗します。 また、シンドロームを満たす特解が得られても論理的に正しいとは限らないため、 syndrome-validとlogical-validを分けて記録する必要があります。 文献上は、bit-flipping復号 Gallager と、信頼度順序付きsyndrome decoding Fossorier--Lin--Snyders の中間的な実装変形として扱うのが自然です。

global_solve

global_solve は、候補集合を絞らず、全変数を使って \[ H\delta=r \] を直接解くフォールバックです。BPコスト順に列を並べた上でGF(2)消去を行い、 その消去が返す一つの特解を補正として採用します。候補を捨てないため、 \(r\) が \(H\) の列空間に入っていれば、シンドロームを満たす補正を見つけられます。

ただし、この方法はシンドロームを満たすことだけを目的とします。返る解は最小重み解でも 最尤解でもなく、論理的に正しい補正である保証もありません。そのため、実験評価では syndrome-validになったこととlogical-validになったことを分けて記録する必要があります。 これは標準文献にある特定のBP後処理名というより、GF(2)線形方程式の特解を使う 実装上のfallbackです。OSD型との関係を見るときは、信頼度順序付きsyndrome decoding Fossorier--Lin--Snyders を背景文献として参照できます。

k_osd_global

k_osd_global は、まず k_osd でBP信頼度に沿った小さい候補補正を試し、 それで解けない場合だけ global_solve に落とす方法です。通常の失敗は K-OSDで処理し、K-OSDの候補prefixに必要な列が含まれない場合だけ全変数ソルバを使います。

この構成は、計算量と成功率のバランスを取りやすい一方、フォールバックに入ったケースの 解釈には注意が必要です。K-OSDで解けたケースとglobal solveで解けたケースは、同じ syndrome-validでも性質が違うため、結果を集計するときはどちらの経路で成功したかを 分けて見るのが安全です。 文献上はBP+OSD後処理 Panteleev--Kalachev, Roffe et al. に全変数の線形fallbackを加えた実装設計として位置づけるのが自然です。

線形ソルバ型後処理の解の選び方

osd_lite, k_osd, flip_history, global_solve は、いずれも候補変数集合 \(V\) を決めて \[ H_{[:,V]}\delta_V=r \] をGF(2)消去で解く、という共通の形を持ちます。違いは候補集合 \(V\) の作り方です。 osd_lite は固定サイズの候補集合、k_osd は解けるprefix長、 flip_history はBP反復履歴で作った候補集合、 global_solve は全変数集合を使います。

BP後の反転コスト \(c_i\) が小さい順に候補を並べ、その順序を \(\pi\) とすると、 候補集合上の列は \[ H_{\pi,V}=[h_{\pi(1)}\ h_{\pi(2)}\ \cdots] \] のように並びます。GF(2)消去は、この列順に依存して一つの特解を返します。 したがって、線形ソルバ型後処理は一般に、解空間全体から最小重み解を選ぶものではありません。 

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.

解は一意ではない

後処理で解く線形方程式は一般に \[ H\delta=r,\qquad H\in\mathbb F_2^{m\times n} \] です。\(H\) がフル列ランクでない場合、解は一般に一意ではありません。 解が一つ \(\delta_0\) 見つかると、 \[ \delta_0+\ker(H) \] がすべて解になります。特に \(n>\mathrm{rank}(H)\) なら \[ \dim\ker(H)=n-\mathrm{rank}(H)>0 \] です。

したがって、線形ソルバ型後処理は「多数ある解のうち、候補集合と列順が決める一つの特解」を選びます。 この性質を理解した上で、論理失敗率を別途評価する必要があります。

実装上の注意