先排序，
再解方程 First rank,
then solve

本页的量子码都是 CSS 码：每条检查要么只含 X，要么只含 Z（《从高考数学到 Toric Code》的环面码就是这样）。这样的码可以把 X 错误和 Z 错误分开处理，第 4 章再说为什么。在那之前只看 X 错误；它们由 Z 检查发现，Z 错误的故事把字母对换即可。记号如下：

Every quantum code on this page is a CSS code: each check contains only X or only Z (the toric code of “From High-School Math to the Toric Code” is one). Such a code lets us treat X errors and Z errors separately; Chapter 4 explains why. Until then we look only at X errors; Z checks detect them, and the story for Z errors is the same with the letters swapped. The notation:

• e：长度 n 的一列 0/1，第 j 位为 1 表示第 j 个比特上有 X 错误。n 是比特数。
• H：检查矩阵，m 行 n 列。第 i 行记录第 i 条 Z 检查碰哪些比特：碰到的位置写 1，其余写 0。
• s：症状syndrome：全部检查的读数，写成一列 0/1。第 i 位为 1 表示第 i 条检查「亮了」（读到 −1），即它碰到的比特里有奇数个出错。，长度 m 的一列 0/1，第 i 位为 1 表示第 i 条检查亮了。

• e: a column of n zeros and ones; entry j is 1 when qubit j carries an X error. n is the number of qubits.
• H: the check matrix, m rows and n columns. Row i records which qubits Z check i touches: 1 where it touches, 0 elsewhere.
• s: the syndromeThe readings of all checks, written as a column of zeros and ones. Entry i is 1 when check i is “lit” (reads −1), i.e. an odd number of the qubits it touches are flipped., a column of m zeros and ones; entry i is 1 when check i is lit.

一条检查亮不亮，只取决于它碰到的比特里出错的个数是奇是偶。把「奇偶」写成模 2 加法（1 + 1 = 0），全部检查一起写就是下面这一行。不熟悉模 2 的矩阵乘法，先打开补课 0.A。

Whether a check lights up depends only on whether the number of flipped qubits it touches is odd or even. Writing “odd or even” as addition mod 2 (1 + 1 = 0), all checks at once give the line below. If the mod-2 matrix product is new to you, open Catch-up 0.A first.

译码器只看得到 s，看不到 e。它交出一个修复 c：把 c 里为 1 的比特都翻一次。修复至少要让症状清零，这就是条件 H c = s。清零之后留在比特上的是残留 e ⊕ c（真实错误与修复叠加，同一比特翻两次等于没翻）。因为 H(e ⊕ c) = H e ⊕ H c = s ⊕ s = 0，残留不点亮任何检查。不点亮任何检查的 X 型算符只有两种：

The decoder sees s, not e. It returns a repair c: flip every qubit where c has a 1. A repair must at least clear the syndrome, which is the condition H c = s. After that, what remains on the qubits is the residual e ⊕ c (the true error plus the repair; flipping a qubit twice leaves it unchanged). Since H(e ⊕ c) = H e ⊕ H c = s ⊕ s = 0, the residual lights no check. An X-type operator that lights no check is one of two kinds:

• 稳定子stabilizer：若干条检查的乘积。它作用在编码态上什么也不改变，所以残留是稳定子就算译码成功。：若干条 X 检查的乘积。编码态是所有检查的 +1 本征态，乘上它不起任何作用，所以残留是稳定子就算成功。修复不必等于真实错误，差一个稳定子就够了。
• 逻辑算符logical operator：不点亮任何检查、却不是检查乘积的算符。它悄悄改写了存储的逻辑信息；残留是逻辑算符就是逻辑错误。：不点亮任何检查、却不是检查乘积的算符。它改写了存储的信息，残留是逻辑算符就是失败。

• A stabilizerA product of checks. It leaves every code state unchanged, so a residual that is a stabilizer means decoding succeeded.: a product of X checks. Code states are +1 eigenstates of every check, so multiplying by it does nothing, and a stabilizer residual means success. The repair need not equal the true error; differing by a stabilizer is enough.
• A logical operatorAn operator that lights no check but is not a product of checks. It silently rewrites the stored logical information; a logical residual is a logical error.: lights no check but is not a product of checks. It rewrites the stored information, and a logical residual means failure.

怎么判断残留属于哪一种？看它与每个 Z 型逻辑算符 Z̄ 重叠的比特数是奇是偶。重叠奇数个，二者反对易，残留翻转了 Z̄ 的读数，是逻辑错误；每个 Z̄ 都重叠偶数个，残留是稳定子。要看的是奇偶，不是「有没有一条绕过去的串」：两条平行的绕圈串合起来与 Z̄ 重叠两次，它们的乘积正好是夹在中间的那些检查之积，无害。图 0.1 在最小的环面码上把这件事画出来。

How do we tell which kind a residual is? Count, for every Z-type logical operator Z̄, how many qubits the residual shares with it. An odd overlap means the two anticommute, the residual flips Z̄’s reading, and decoding failed; an even overlap with every Z̄ means the residual is a stabilizer. What matters is the parity, not whether “a string winds around”: two parallel winding strings together overlap Z̄ twice, and their product is exactly the product of the checks between them, which is harmless. Figure 0.1 draws this on the smallest toric code.

所以译码器面对的是一个选择题：与 s 相符的修复有很多，它们按「相差一个稳定子」分成若干类class（陪集）：彼此相差一个稳定子的修复归为一类。同一类里的修复效果完全相同；k 个逻辑比特时，一个症状下有 2^k 类。，同一类里的修复效果相同，选对类就成功。《译码器 · 高中数学版》1.1 节到 1.3 节在表面码上把这件事讲成「最优译码 = 押概率最大的那一类」；本页第 1 章用经典码重新推一遍，第 4 章回到量子的「类」。

So the decoder faces a multiple-choice question: many repairs agree with s, they fall into classesClass (coset): repairs that differ by a stabilizer form one class. All repairs in a class have the same effect; with k logical qubits a syndrome has 2^k classes. of repairs that differ by a stabilizer, repairs in the same class have the same effect, and choosing the right class means success. Sections 1.1 to 1.3 of “Decoders · High-School Edition” turn this into “optimal decoding = bet on the most probable class” for the surface code; Chapter 1 here rederives it with classical codes, and Chapter 4 returns to quantum classes.

环面码里，H 的每一列恰好有两个 1：一条边上的 X 错误点亮它两侧的两个面。于是可以把每个可能的错误画成连接两个警报的一条边，一批错误的症状就是这些边的端点，译码就是把亮着的警报两两连起来，挑总长度最短的连法。这就是最小重量完美匹配，它建立在「一个错误 = 两个端点」上。

In the toric code every column of H has exactly two ones: an X error on an edge lights the two faces beside it. So every possible error can be drawn as an edge joining two alarms, the syndrome of a batch of errors is the set of endpoints, and decoding is joining the lit alarms in pairs with the shortest total length. That is minimum-weight perfect matching, and it rests on “one error = two endpoints”.

IBM 提出的 gross 码（[[144,12,12]]，《BB 码 · 译码器》1.2 节）不是这样：它的 H_Z 每列有三个 1。本页的脚本按那一页的编号重算了一遍：比特 1 上的 X 错误点亮 Z 检查 4、7、13。一个错误连着三个警报，画出来不是边，而是一条超边hyperedge：同时连接三个或更多顶点的「边」。含超边的图叫超图；完美匹配是为普通的两端点边定义的。。「两两配对」这个说法本身就用不上了。

IBM’s gross code ([[144,12,12]], “BB Codes · Decoders”, §1.2) is different: every column of its H_Z has three ones. This page’s script recomputed it with that page’s numbering: an X error on qubit 1 lights Z checks 4, 7 and 13. One error attached to three alarms is not an edge but a hyperedgeAn “edge” joining three or more vertices at once. A graph with hyperedges is a hypergraph; perfect matching is defined for ordinary two-ended edges., and “join in pairs” no longer applies.

能不能退回最笨的办法，把所有与 s 相符的修复列出来逐个比较？第 1 章会数：gross 有 2⁷⁸ ≈ 3.0 × 10²³ 个，列不完。一般的线性码上，「找与症状相符的最轻错误」是 NP 难问题（Bravyi 等 2308.07915 的补充材料引 Berlekamp、McEliece 与 van Tilborg 1978 年的结果）。实用的译码器只能是近似的，BP-OSD 是其中最常用的通用方案之一。

Could we fall back on the crudest method and list every repair that agrees with s? Chapter 1 counts them: gross has 2⁷⁸ ≈ 3.0 × 10²³, far too many. For a general linear code, “find the lightest error that matches the syndrome” is NP-hard (the supplement of Bravyi et al., 2308.07915, cites Berlekamp, McEliece and van Tilborg, 1978). Practical decoders have to be approximate, and BP-OSD is one of the most widely used general-purpose ones.

BP-OSD 的分工一句话说完：BP 排序，OSD 解方程。BP 给每个比特一个实数，表示它有多可能出错；若按这些数逐位判决得到的修复已经满足 H c = s，就直接交出。若不满足，OSD 接手：按 BP 的排序挑出最可能出错的一组比特，在它们身上解 H c = s，其余比特设为 0，保证症状清零。

The division of labour in one sentence: BP ranks, OSD solves. BP gives every qubit a real number that says how likely it is to be flipped; if the bit-by-bit decisions from these numbers already satisfy H c = s, that repair is returned. If not, OSD takes over: following BP’s ranking it picks the group of qubits most likely to be flipped, solves H c = s on them, sets every other qubit to 0, and is guaranteed to clear the syndrome.

本页的路线：第 1 章把译码写成概率推断，引入对数似然比；第 2 章推出 BP 的两条规则，在没有圈的图上验证它精确；第 3 章看圈怎样让 BP 重复计数，以及 min-sum、阻尼、串行调度这些常见变体；第 4 章回到量子码，讲 CSS 分开译码、去极化先验和退化degeneracy：不同的错误相差一个稳定子时效果相同。它让「每个比特最可能的取值」与「最可能的类」分道扬镳。；第 5 章是 OSD：高斯消元、基集、各阶 OSD 与代价；第 6 章把它们装成标准的 BP-OSD，对照常用的 ldpc 软件包的参数，并在实验台上跑蒙特卡洛；第 7 章把同一套方法搬到测量也会出错的电路级译码。

The route: Chapter 1 writes decoding as probabilistic inference and introduces the log-likelihood ratio; Chapter 2 derives BP’s two rules and checks that it is exact on graphs without cycles; Chapter 3 shows how cycles make BP count evidence twice, and covers common variants such as min-sum, damping and the serial schedule; Chapter 4 returns to quantum codes: separate CSS decoding, depolarizing priors and degeneracyDifferent errors that differ by a stabilizer have the same effect. Degeneracy separates “the most likely value of each qubit” from “the most likely class”.; Chapter 5 is OSD: Gaussian elimination, basis sets, the orders of OSD and their cost; Chapter 6 assembles standard BP-OSD, matches its parameters to the widely used ldpc package and runs Monte Carlo on a bench; Chapter 7 carries the same method over to circuit-level decoding, where measurements can also fail.

第 1 到第 3 章只用经典比特，因为 BP 本来就是经典 LDPC 码的译码器，量子码只是把它借过去用（第 4 章）。方程还是 s = H e：比特排成一列 e，检查写成矩阵 H，症状 s 告诉我们哪些检查看到了奇数个错误。例子仍用补课 0.A 的三比特重复码：两条检查 c₁ = b₁ ⊕ b₂、c₂ = b₂ ⊕ b₃。

Chapters 1 to 3 use classical bits only, because BP is originally a decoder for classical LDPC codes and quantum codes borrow it (Chapter 4). The equation is still s = H e: the bits form a column e, the checks form a matrix H, and the syndrome s says which checks saw an odd number of errors. The example is again the three-bit repetition code of Catch-up 0.A: two checks c₁ = b₁ ⊕ b₂ and c₂ = b₂ ⊕ b₃.

要「猜」，先要知道错误是怎么来的。本页默认最简单的独立翻转模型每个比特独立地以概率 p 翻转，互不影响。量子版本（只看数据比特、测量完美）叫码容量模型，第 6 章的实验台用的就是它。：每个比特独立地以概率 p 翻转。于是一个具体的错误图样 e 出现的概率只取决于它有几个 1（记作重量 |e|）：

To guess, we need to know how errors arise. The page’s default is the simplest independent-flip modelEvery bit flips independently with probability p. The quantum version (data qubits only, perfect measurements) is called the code-capacity model; the bench of Chapter 6 uses it.: every bit flips independently with probability p. The probability of one particular error pattern e then depends only on how many ones it has (its weight |e|):

每多一个 1，概率乘上 p/(1 − p)。p = 0.1 时这个因子是 1/9，所以 p < 1/2 时越轻的图样越可能。读到症状以后，与症状不符的图样概率变成 0，相符的图样按原来的比例重新分配，总和为 1。这一步就是条件概率；补课 1.A 从零讲它。

Each additional 1 multiplies the probability by p/(1 − p). For p = 0.1 that factor is 1/9, so for p < 1/2 lighter patterns are more likely. Once the syndrome is read, patterns that disagree with it drop to probability 0, and the agreeing patterns share the total of 1 in their old proportions. That step is conditional probability; Catch-up 1.A teaches it from zero.

读到症状 s 之后，「最可能的错误」可以有三种问法：

Once the syndrome s is read, “the most likely error” can be asked in three ways:

1. 哪个错误图样最可能？在所有与 s 相符的 e 里挑 P(e | s) 最大的一个。这叫最大后验MAP（maximum a posteriori）：在与观测相符的所有可能里挑后验概率最大的一个。独立翻转、p < 1/2 时，就是与症状相符的最轻图样。（MAP）译码；独立翻转、p < 1/2 时就是「与症状相符的最轻图样」。
2. 每个比特各自最可能是什么？对每个 j 单独算 P(e_j = 1 | s)，这叫比特 j 的边缘概率marginal：把其他比特的所有取值都加起来之后，只剩比特 j 一个的概率 P(e_j = 1 | s)。BP 近似计算的就是它。，超过一半就判它出错。BP 近似算的就是这个量。
3. 哪一类最可能？量子码里，相差一个稳定子的修复效果相同，真正该比的是整类的总概率。经典码里每类只有一个成员，这个问题与第一个相同；第 4 章再回来。

1. Which error pattern is most likely? Among all e that agree with s, pick the one with the largest P(e | s). This is maximum a posterioriMAP: among all possibilities consistent with the observation, pick the one with the largest posterior probability. For independent flips with p < 1/2 it is the lightest pattern that matches the syndrome. (MAP) decoding; for independent flips with p < 1/2 it is “the lightest pattern that matches the syndrome”.
2. What is each bit most likely to be? For each j separately compute P(e_j = 1 | s), the marginalThe probability P(e_j = 1 | s) of bit j alone, after summing over every value of all the other bits. BP approximates it. of bit j, and call it flipped if it exceeds one half. This is the quantity BP approximates.
3. Which class is most likely? In a quantum code, repairs that differ by a stabilizer act identically, and what should be compared is the total probability of a class. In a classical code each class has one member and this question is the first one; Chapter 4 comes back to it.

第一个与第二个问题的答案可以不一样，而且第二个问题的答案拼起来可能根本不满足检查。最小的例子只有一条检查：它碰三个比特 a、b、c，读数亮了，也就是 a ⊕ b ⊕ c = 1。p = 0.1。八种图样全部列出来：

The first and second questions can have different answers, and the answers to the second one, put together, may not satisfy the checks at all. The smallest example has a single check touching three bits a, b, c, and it is lit, i.e. a ⊕ b ⊕ c = 1. p = 0.1. All eight patterns:

与「亮」相符的是 100、010、001、111，总概率 0.081 × 3 + 0.001 = 0.244，除以它就是最后一行。问题 1：三个单比特错误并列最可能（各 0.332），MAP 译码随便挑一个，比如 100，满足检查。问题 2：a 出错的图样是 100 和 111，P(a 出错 | 亮) = (0.081 + 0.001)/0.244 = 0.336 < 1/2；b、c 同理。三个比特各自都「更可能没错」，逐位判决得 000，而 000 不满足 a ⊕ b ⊕ c = 1。

The patterns that agree with “lit” are 100, 010, 001 and 111, with total probability 0.081 × 3 + 0.001 = 0.244; dividing by it gives the last row. Question 1: the three single-bit errors tie as most likely (0.332 each), and MAP decoding picks any one, say 100, which satisfies the check. Question 2: the patterns with a flipped are 100 and 111, so P(a flipped | lit) = (0.081 + 0.001)/0.244 = 0.336 < 1/2; likewise for b and c. Each bit on its own is “more likely clean”, the bit-by-bit decision is 000, and 000 does not satisfy a ⊕ b ⊕ c = 1.

这不是计算出了错，0.336 是精确值。问题出在问法：三个并列的答案把概率平分了，每个比特只分到三分之一。「每个比特最可能的取值」拼起来可以不是任何一个合法答案。记住这个例子：第 4 章的退化会把它放大，第 5 章的 OSD 就是为补这个缺口而设的。换成三比特重复码、只有比特 2 出错（s = 11），两种问法就一致：相符的图样 010（0.9）和 101（0.1），问题 1 选 010，问题 2 给 P(b₂ 出错) = 0.9、P(b₁ 出错) = P(b₃ 出错) = 0.1，逐位判决也是 010。

Nothing was miscalculated; 0.336 is exact. The trouble is the question: three tied answers split the probability, and each bit receives only a third. “The most likely value of each bit”, put together, need not be any valid answer. Keep this example in mind: Chapter 4’s degeneracy magnifies it, and Chapter 5’s OSD exists to close this gap. In the three-bit repetition code with only bit 2 flipped (s = 11), the two questions agree: the matching patterns are 010 (0.9) and 101 (0.1); question 1 picks 010, question 2 gives P(b₂ flipped) = 0.9 and P(b₁ flipped) = P(b₃ flipped) = 0.1, and the bit-by-bit decision is also 010.

BP 不直接记概率，而记「没错 : 出错」这个比，叫比特的赔率odds：P(没错) : P(出错)。p = 0.1 的先验赔率是 0.9 : 0.1 = 9 : 1。赔率 x 对应 P(出错) = 1/(1 + x)。。先验赔率是 (1 − p) : p，p = 0.1 时 9 : 1。来了一条证据 E（比如「这条检查亮了」），贝叶斯公式分别写给「没错」和「出错」两种情形再相除，分母 P(E) 约掉，得到：

BP does not keep probabilities directly; it keeps the ratio “clean : flipped”, the bit’s oddsP(clean) : P(flipped). The prior odds for p = 0.1 are 0.9 : 0.1 = 9 : 1. Odds x correspond to P(flipped) = 1/(1 + x).. The prior odds are (1 − p) : p, which is 9 : 1 for p = 0.1. When a piece of evidence E arrives (for example “this check is lit”), write Bayes’ rule for “clean” and for “flipped” and divide; the denominator P(E) cancels and we get:

似然比likelihood ratio：P(E | 没错)/P(E | 出错)。它只说「这条证据在两种情形下出现的可能相差几倍」，不含先验；要得到赔率，必须乘上先验赔率。说的是「如果比特没错，看到 E 的可能是它出错时的几倍」。它本身不是赔率：它不含先验。用 1.2 节的例子算一次。E = 「检查亮了」。若 a 没错，亮 ⇔ b ⊕ c = 1，要恰好 b、c 中一个出错：2 × 0.1 × 0.9 = 0.18。若 a 出错，亮 ⇔ b ⊕ c = 0：0.82。似然比 0.18/0.82 = 0.220，新赔率 = 9 × 0.220 = 1.976，P(a 出错) = 1/(1 + 1.976) = 0.336，与穷举一致。

The likelihood ratioP(E | clean)/P(E | flipped). It says only how many times more likely the evidence is in one case than in the other, without the prior; to get odds it must be multiplied by the prior odds. says “if the bit is clean, seeing E is this many times as likely as if it is flipped”. It is not itself odds: it carries no prior. Compute it for the example of §1.2. E = “the check is lit”. If a is clean, lit ⇔ b ⊕ c = 1, which needs exactly one of b, c flipped: 2 × 0.1 × 0.9 = 0.18. If a is flipped, lit ⇔ b ⊕ c = 0: 0.82. The likelihood ratio is 0.18/0.82 = 0.220, the new odds are 9 × 0.220 = 1.976, and P(a flipped) = 1/(1 + 1.976) = 0.336, matching the enumeration.

两条证据 E₁、E₂，只要在「比特没错」和「比特出错」两种情形下各自互相独立，就依次相乘：新赔率 = 先验赔率 × 似然比₁ × 似然比₂。乘法不好加总，取对数就变成加法（ln(ab) = ln a + ln b，补课 1.B）。于是定义对数似然比log-likelihood ratio, LLR：L = ln[P(没错)/P(出错)]，也就是赔率的对数。正数 = 更相信没错，负数 = 更相信出错，0 = 一半一半。P(出错) = 1/(1 + e^L)。（LLR）：

Two pieces of evidence E₁, E₂ that are independent of each other both when the bit is clean and when it is flipped simply multiply in turn: new odds = prior odds × ratio₁ × ratio₂. Products are awkward to accumulate, and taking logs turns them into sums (ln(ab) = ln a + ln b, Catch-up 1.B). So define the log-likelihood ratioLLR: L = ln[P(clean)/P(flipped)], the log of the odds. Positive = more likely clean, negative = more likely flipped, 0 = fifty-fifty. P(flipped) = 1/(1 + e^L). (LLR):

P(0) 是比特取 0（没错）的概率，P(1) 是取 1（出错）的概率。几个值值得记住：p = 0.1 时 L₀ = ln 9 = 2.20；p = 0.06 时 2.75；p = 0.3 时 0.85；p = 0.5 时 0（完全拿不准）；p = 0.9 时 −2.20。反过来 P(出错) = 1/(1 + e^L)。例子里 L = 2.20 + ln 0.220 = 2.20 − 1.52 = 0.68，1/(1 + e^0.68) = 0.336。最后一步叫硬判决hard decision：把实数 LLR 变成 0/1：L_j < 0 判为出错（c_j = 1），否则判为没错。：LLR 为负就判出错，c_j = 1。本页和《BB 码 · 译码器》2.1 节用同一套记号与数字。

P(0) is the probability that the bit is 0 (clean), P(1) that it is 1 (flipped). A few values are worth remembering: L₀ = ln 9 = 2.20 for p = 0.1; 2.75 for p = 0.06; 0.85 for p = 0.3; 0 for p = 0.5 (no idea at all); −2.20 for p = 0.9. Conversely P(flipped) = 1/(1 + e^L). In the example L = 2.20 + ln 0.220 = 2.20 − 1.52 = 0.68, and 1/(1 + e^0.68) = 0.336. The last step is the hard decisionTurning a real LLR into 0/1: L_j < 0 is decided flipped (c_j = 1), otherwise clean.: a negative LLR is decided flipped, c_j = 1. This page and “BB Codes · Decoders”, §2.1, use the same notation and numbers.

上面的精确答案都是列表列出来的。列表要列多长？方程 H c = s 要么无解，要么恰好有 2^{n − r} 个解，r = rank H 是独立检查的条数。理由：两个解之差 x 满足 H x = 0；r 条独立的方程每一条把候选砍掉一半，所以满足 H x = 0 的 x 有 2ⁿ / 2^r 个，每个都把一个解变成另一个解（这与《从高考数学到 Toric Code》4.4 节「每条独立检查砍半」是同一个数法）。下表由 notes/bp-osd/page_numbers.py 算出，最后一列假设每秒检查 10⁹ 个候选：

The exact answers above came from listing. How long is the list? The equation H c = s has either no solution or exactly 2^{n − r} solutions, where r = rank H is the number of independent checks. Reason: the difference x of two solutions satisfies H x = 0; each of the r independent equations cuts the candidates in half, so 2ⁿ / 2^r vectors satisfy H x = 0, and each one turns a solution into another solution (the same count as “each independent check halves” in “From High-School Math to the Toric Code”, §4.4). The table comes from notes/bp-osd/page_numbers.py; the last column assumes 10⁹ candidates checked per second:

对真正要用的码，精确地回答三个问题中的任何一个都要付出指数级的代价。BP 的想法是只做局部的计算：每个比特只和碰它的检查交换一个数，每轮的工作量与 H 里 1 的个数成正比。代价是它一般只给出问题 2 的近似答案，下一章从它在什么情形下精确讲起。

For the codes we actually care about, answering any of the three questions exactly costs exponential effort. BP’s idea is to compute only locally: each bit exchanges one number with the checks that touch it, and the work per round is proportional to the number of ones in H. The price is that it generally gives only an approximate answer to question 2; the next chapter starts from when it is exact.

Tanner 图把检查矩阵 H 画成图：每个比特一个圆点，每条检查一个方块，H 的第 i 行第 j 列是 1 就在检查 i 与比特 j 之间连一条边。边只连「比特—检查」，不连同类。就是把 H 画出来：每个比特画一个圆，每条检查画一个方块，H 的第 i 行第 j 列是 1，就在检查 i 和比特 j 之间连一条边。边的条数等于 H 里 1 的个数：三比特链 4 条，3 × 3 环面码 36 条，gross 的 H_Z 432 条。BP 的消息沿这些边双向传递：检查发给比特的记作 m_i→j，比特发给检查的记作 L_j→i。

The Tanner graphThe check matrix H drawn as a graph: one circle per bit, one square per check, and an edge between check i and bit j whenever row i, column j of H is 1. Edges only join a bit to a check, never two of the same kind. is H drawn out: one circle per bit, one square per check, and an edge between check i and bit j whenever row i, column j of H is 1. The number of edges equals the number of ones in H: 4 for the three-bit chain, 36 for the 3 × 3 toric code, 432 for gross’s H_Z. BP’s messages travel along these edges in both directions: check to bit is written m_i→j, bit to check L_j→i.

检查 i 要告诉邻居 j：「按其他邻居现在的说法，再加上我亮没亮，关于你没错还是出错，我能提供多大的似然比。」1.3 节已经在 p = 0.1 的例子里算过一次：a 没错时检查亮要求 b ⊕ c 为奇（0.18），a 出错时要求为偶（0.82），似然比 0.18 : 0.82。一般情形只差一件事：其他邻居不止两个，各自的出错概率也不再相同，怎么算它们「之和为奇」的概率？

Check i has to tell neighbour j: “given what my other neighbours currently say, and whether I am lit, this is the likelihood ratio I can offer on whether you are clean or flipped.” §1.3 did it once for p = 0.1: with a clean, a lit check needs b ⊕ c odd (0.18); with a flipped, even (0.82); ratio 0.18 : 0.82. The general case needs one more thing: with more than two other neighbours, each with its own flip probability, what is the probability that their sum is odd?

答案用偏差bias：δ = P(0) − P(1) = 1 − 2P(出错)。p = 0.1 时 δ = 0.8。它等于 tanh(L/2)。几个独立比特之和（mod 2）的偏差 = 各自偏差之积。记账最方便：一个比特的偏差 δ = P(0) − P(1) = 1 − 2 × P(出错)，p = 0.1 时 δ = 0.8。关键事实是：几个独立比特之和（mod 2）的偏差，等于各自偏差的乘积（补课 2.A 给出一行证明）。例：两个 δ = 0.8 的比特，和的偏差 0.64，为奇数的概率 (1 − 0.64)/2 = 0.18，和上面数出来的一样。偏差与 LLR 之间只隔一个函数：δ = tanh(L/2)，反过来 L = 2 artanh δ = ln[(1 + δ)/(1 − δ)]。核对：L = ln 9 时 tanh(L/2) = (9 − 1)/(9 + 1) = 0.8。

The biasδ = P(0) − P(1) = 1 − 2P(flipped). For p = 0.1, δ = 0.8. It equals tanh(L/2). The bias of a mod-2 sum of independent bits is the product of their biases. is the handiest bookkeeping: a bit’s bias is δ = P(0) − P(1) = 1 − 2 × P(flipped), which is 0.8 for p = 0.1. The key fact: the bias of a mod-2 sum of independent bits is the product of their biases (Catch-up 2.A gives a one-line proof). Example: two bits with δ = 0.8 have a sum with bias 0.64, so the sum is odd with probability (1 − 0.64)/2 = 0.18, as counted above. Bias and LLR are one function apart: δ = tanh(L/2), and back again L = 2 artanh δ = ln[(1 + δ)/(1 − δ)]. Check: for L = ln 9, tanh(L/2) = (9 − 1)/(9 + 1) = 0.8.

现在推规则。设 B 是检查 i 除 j 以外的邻居之和的偏差，B = ∏ tanh(L_j′→i/2)，乘积跑遍 j 以外的邻居 j′。检查亮（s_i = 1）时：若 j 没错，其他人之和必须为奇，概率 (1 − B)/2；若 j 出错，必须为偶，概率 (1 + B)/2。这条检查给 j 的似然比就是 (1 − B) : (1 + B)，取对数得 m_i→j = ln[(1 − B)/(1 + B)] = −2 artanh B。检查没亮时两边对调，符号相反。合起来：

Now the rule. Let B be the bias of the sum of check i’s neighbours other than j: B = ∏ tanh(L_j′→i/2), the product running over the neighbours j′ other than j. If the check is lit (s_i = 1): with j clean the others must sum to odd, probability (1 − B)/2; with j flipped, to even, probability (1 + B)/2. The likelihood ratio this check offers j is (1 − B) : (1 + B), and its log is m_i→j = ln[(1 − B)/(1 + B)] = −2 artanh B. If the check is unlit the two sides swap and the sign flips. Together:

三点要读出来。第一，m 是似然比的对数，不是赔率：它不含 j 自己的先验，j 要把它加到自己的 LLR 上（2.3 节）。例子里 2.20 − 1.52 = 0.68，正是 1.3 节的结果。第二，j 自己发来的消息不参与：检查问的是「别人怎么说」。第三，符号与大小可以分开读：artanh 是奇函数，所以 m 的符号 = (−1)^s × 其他邻居 LLR 符号之积；B 是几个绝对值不超过 1 的数之积，所以 |m| 不超过其他邻居里最小的 |L|。直白地说：一条检查的把握不会超过它最没把握的那个邻居。第 3 章的 min-sum 就从这一点来。只有两个邻居的检查，乘积里只剩一个因子，规则化简成 m = ± 另一个邻居的 L（亮取负号）。

Three things to read off. First, m is the log of a likelihood ratio, not odds: it carries no prior of j’s own, and j adds it to its own LLR (§2.3). In the example 2.20 − 1.52 = 0.68, exactly the result of §1.3. Second, j’s own message is left out: the check reports what the others say. Third, sign and size can be read separately: artanh is odd, so the sign of m = (−1)^s × the product of the other neighbours’ LLR signs; B is a product of numbers of absolute value at most 1, so |m| is at most the smallest |L| among the other neighbours. Plainly: a check is never surer than its least sure neighbour. Chapter 3’s min-sum starts from this. For a check with only two neighbours the product has a single factor, and the rule reduces to m = ± the other neighbour’s L (minus if lit).

下面的实验台只算一条检查。默认是 1.2 节的情形：三个邻居，每个发来先验 2.20，检查亮，收消息的是 q1。拖动其他邻居的 L，看 B、似然比和消息怎么变；把 q1 自己的 L 拖到任何值，消息都不变；把检查切成「没亮」，消息变号；把某个邻居的 L 拖成负数，消息也变号（符号规则）；把邻居数加到 6，看 |m| 怎样被最小的那个 |L| 压住。读数最后一行是第 3 章的 min-sum 近似。先留意普通 min-sum（α = 1）的 |m| 从不小于精确值，也就是更「自信」；同一行的归一化值乘了 α，可能反而比精确值小（默认 α = 0.625 时是 −1.37，精确值 −1.52）。

The bench below computes one check. The default is the case of §1.2: three neighbours, each sending the prior 2.20, the check lit, q1 receiving. Drag the other neighbours’ L and watch B, the ratio and the message change; drag q1’s own L anywhere and the message does not move; switch the check to “unlit” and the message flips sign; drag one neighbour’s L below zero and it flips again (the sign rule); raise the neighbour count to 6 and see |m| held down by the smallest |L|. The last line shows Chapter 3’s min-sum approximation. Notice for now that plain min-sum (α = 1) never gives a smaller |m| than the exact value, so it is more “confident”; the normalized value in the same line is multiplied by α and can come out below the exact value (at the default α = 0.625 it is −1.37, against the exact −1.52).

比特 j 从每条邻居检查收到一个似然比的对数。如果这些证据互相独立，1.3 节说它们直接相加：总 LLR = 先验 + 所有邻居检查的消息。比特回话给检查 i 时，用总数减去 i 自己刚发来的那一条，理由和检查的规则一样：不把 i 的话还给 i，否则 i 会把自己的意见当成新证据。

Bit j receives the log of a likelihood ratio from each neighbouring check. If these pieces of evidence are independent, §1.3 says they simply add: total LLR = prior + every neighbouring check’s message. When the bit replies to check i it uses the total minus the message i itself just sent, for the same reason as in the check rule: do not hand i’s words back to i, or i would count its own opinion as new evidence.

两条规则交替执行就是 BP。最常见的顺序叫泛洪调度flooding schedule：每一轮先让所有检查同时发言，再让所有比特同时汇总。另一种是串行（分层）调度，逐条检查更新，见 3.4 节。：一开始每个比特向每条邻居检查发先验 L₀；然后每一轮分两个半步，先所有检查同时按 2.2 节的规则发言，再所有比特同时汇总、回话。每轮结束做一次硬判决，得到候选修复 c；若 H c = s，就说 BP 收敛converged：硬判决 c 满足 H c = s，症状清零。本页（和 ldpc 软件包）用它作停止条件；它不保证 c 是对的，只保证症状相符。了，停下交出 c；否则继续，直到轮数达到上限 max_iter。写成程序：

Alternating the two rules is BP. The most common order is the flooding scheduleEach iteration first lets all checks speak at once, then all bits sum up at once. The alternative is the serial (layered) schedule, which updates check by check; see §3.4.: at the start every bit sends the prior L₀ to each neighbouring check; then each iteration has two half-steps, first all checks speak at once by the rule of §2.2, then all bits sum up and reply at once. After each iteration a hard decision gives a candidate repair c; if H c = s, BP is said to have convergedThe hard decision c satisfies H c = s and the syndrome is cleared. This page (and the ldpc package) uses it as the stopping rule; it does not guarantee that c is right, only that it matches the syndrome., and it stops and returns c; otherwise it continues until the iteration count reaches max_iter. As a program:

每轮的工作量正比于边数，而且每条边上的计算只用到相邻节点的数，所以 BP 天然适合并行硬件。这也是它在量子纠错里受重视的原因之一（第 7 章说延迟）。

The work per iteration is proportional to the number of edges, and the computation on each edge uses only numbers from adjacent nodes, so BP suits parallel hardware naturally. That is one reason it matters in quantum error correction (Chapter 7 discusses latency).

在图 2.1(b) 上手跑一遍（比特 2 出错，两条检查都亮，p = 0.1）。每条检查只有两个邻居，规则化简成「消息 = ± 另一个邻居发来的 L」，亮取负号。

Run it by hand on Fig. 2.1(b) (bit 2 flipped, both checks lit, p = 0.1). Each check has only two neighbours, so the rule reduces to “message = ± the L sent by the other neighbour”, minus because both are lit.

• 第 1 轮，检查发言。每个比特发出的都还是先验 2.20，所以四条消息都是 −2.20。
• 第 1 轮，比特汇总。b₁ = 2.20 − 2.20 = 0，b₂ = 2.20 − 2.20 − 2.20 = −2.20，b₃ = 0。回话：b₂ 对 c₁ 说 −2.20 − (−2.20) = 0（只剩先验和 c₂ 的意见，两者抵消）；b₁ 对 c₁ 说 0 − (−2.20) = 2.20。硬判决 (0, 1, 0) 已经满足两条检查，带停止规则的 BP 在这里就停了。
• 第 2 轮（不停下时）。c₁ 对 b₁ 说 −0 = 0，对 b₂ 说 −2.20；c₂ 同理。汇总：b₁ = 2.20，b₂ = −2.20，b₃ = 2.20。之后每一轮都不再变。

• Iteration 1, checks speak. Every bit still sends the prior 2.20, so all four messages are −2.20.
• Iteration 1, bits sum up. b₁ = 2.20 − 2.20 = 0, b₂ = 2.20 − 2.20 − 2.20 = −2.20, b₃ = 0. Replies: b₂ tells c₁ −2.20 − (−2.20) = 0 (only the prior and c₂’s opinion remain, and they cancel); b₁ tells c₁ 0 − (−2.20) = 2.20. The hard decision (0, 1, 0) already satisfies both checks, and BP with the stopping rule stops here.
• Iteration 2 (if we do not stop). c₁ tells b₁ −0 = 0 and b₂ −2.20; likewise c₂. Summing: b₁ = 2.20, b₂ = −2.20, b₃ = 2.20. Nothing changes after that.

穷举核对：与症状相符的只有 010（0.081）和 101（0.009），b₂ 出错的概率 0.9，LLR = ln(0.1/0.9) = −2.20；b₁ 出错的概率 0.1，LLR = +2.20。第 2 轮之后，BP 与精确答案逐位相同。注意第 1 轮的 LLR（0、−2.20、0）还不精确，只是硬判决碰巧已经对了：停止规则看的是判决，不是 LLR。

Check by enumeration: only 010 (0.081) and 101 (0.009) match the syndrome; b₂ is flipped with probability 0.9, LLR = ln(0.1/0.9) = −2.20; b₁ with probability 0.1, LLR = +2.20. After iteration 2, BP agrees with the exact answer bit for bit. Note that the LLRs after iteration 1 (0, −2.20, 0) are not yet exact; the hard decision just happens to be right already: the stopping rule looks at decisions, not at LLRs.

为什么在树上精确？把比特 j 的一条邻居检查 i 连同它后面的一切切下来，得到一棵子树；j 的不同邻居检查切下的子树互不相交，里面的比特各自独立出错，所以在「j 没错」和「j 出错」两种情形下，这些子树提供的证据确实互相独立，1.3 节的「似然比相乘」严格成立。同样的理由在每棵子树里一层层往下也成立。消息每轮往前走一步，所以只要轮数达到图上最远两个比特之间的检查数，每个比特就听到了全图，此后的数就是精确的边缘 LLR。三比特链是 2 轮；实验台里的五比特链（比特 3 出错）是 4 轮，精确值 ±6.59 在第 4 轮出现。

Why exact on a tree? Cut off one neighbouring check i of bit j together with everything behind it: a subtree. The subtrees cut off at j’s different checks do not overlap, and their bits flip independently, so in both cases “j clean” and “j flipped” the evidence they supply really is independent, and §1.3’s “ratios multiply” holds exactly. The same argument works inside each subtree, level by level. Messages advance one step per iteration, so once the iteration count reaches the number of checks between the two farthest bits, every bit has heard the whole graph and the numbers from then on are the exact marginal LLRs. For the three-bit chain that is 2 iterations; for the five-bit chain on the bench (bit 3 flipped) it is 4, and the exact values ±6.59 appear at iteration 4.

下面的步进器把每半步都放出来。一次「下一半步」要么是所有检查发言（边上显示 m，检查→比特），要么是所有比特汇总（边上显示 L，比特→检查）。点一个比特或检查，读数给出它这半步的算式；读数表格里「精确 L」是穷举的答案；下方的小图画出所选比特的 LLR 随轮数的变化。先在三比特链上按四次「下一半步」对照上面的手算，再切到五比特链看第 4 轮；第 3 章会用同一个实验台看圈。3 × 3 环面码的比特编号：横边 h(x, y) 编号 3y + x（0–8），竖边 v(x, y) 编号 9 + 3y + x（9–17），面 f(x, y) 编号 3y + x；虚线圆是环面另一侧同一个比特的副本。

The stepper below shows every half-step. One “next half-step” is either all checks speaking (edges show m, check→qubit) or all bits summing up (edges show L, qubit→check). Click a qubit or check and the readout gives its arithmetic for that half-step; “exact L” in the readout table is the enumeration answer; the small plot below draws the chosen qubit’s LLR per iteration. First press “next half-step” four times on the three-bit chain and compare with the hand calculation above, then switch to the five-bit chain and watch iteration 4; Chapter 3 uses the same bench to look at cycles. Numbering in the 3 × 3 toric code: horizontal edge h(x, y) is 3y + x (0–8), vertical edge v(x, y) is 9 + 3y + x (9–17), face f(x, y) is 3y + x; a dashed circle is a copy of the same qubit on the other side of the torus.

Tanner 图里的圈cycle：从一个节点出发，沿不同的边走，不走回头路，最后回到出发点的路径。Tanner 图里比特与检查交替出现，所以圈长（边数）总是偶数，至少是 4。是一条从某个节点出发、不走回头路、又回到出发点的路径；比特和检查交替出现，所以圈长（边数）是偶数，最短是 4。图里最短的圈长叫围长girth：Tanner 图里最短的圈的长度（边数）。树没有圈，围长记为 ∞。围长越短，消息越快绕回自己。（girth）。有圈时，比特 j 发出的消息沿圈走一圈会回到 j 手里，j 把它当作另一条检查的新证据再加一遍。消息每轮走两条边（检查→比特、比特→检查），所以长 g 的圈要 g/2 轮才绕回来：圈越短，回来得越快。

A cycleA path that starts at a node, follows distinct edges without backtracking, and returns to its start. Bits and checks alternate in a Tanner graph, so a cycle’s length (in edges) is even and at least 4. in a Tanner graph is a path that leaves a node, never backtracks, and returns to its start; bits and checks alternate, so its length in edges is even and at least 4. The length of the shortest cycle is the girthThe length (in edges) of the shortest cycle in a Tanner graph. A tree has no cycle and its girth is written ∞. The shorter the girth, the sooner messages come back to their sender.. With cycles, a message sent by bit j can travel around a cycle and return to j, which then adds it again as fresh evidence from another check. Messages cross two edges per iteration (check→bit, bit→check), so a cycle of length g brings a message back after g/2 iterations: the shorter the cycle, the sooner it returns.

四比特环，一个错误。四个比特排成环，检查 c₁ = b₁ ⊕ b₂、c₂ = b₂ ⊕ b₃、c₃ = b₃ ⊕ b₄、c₄ = b₄ ⊕ b₁，Tanner 图本身就是一个长 8 的圈（《BB 码 · 译码器》2.2 节的同一个例子）。b₄ 出错，c₃、c₄ 亮。穷举：b₄ 的精确 LLR 是 −4.39（出错概率约 0.99），其他三个 +4.39。BP 第 1 轮就判对了（b₄ = −2.20），但之后 b₄ 依次是 −6.59、−10.99、−6.59、−10.99、−15.38……，第 11 轮到 −28.56，每 4 轮净增 −8.79。它的意见沿环走一圈（8 条边 = 4 轮）回到自己，被当作新证据再加一次。这里多出来的只是把握，判决没错。

The four-bit ring, one error. Four bits in a ring with checks c₁ = b₁ ⊕ b₂, c₂ = b₂ ⊕ b₃, c₃ = b₃ ⊕ b₄, c₄ = b₄ ⊕ b₁; the Tanner graph is itself one cycle of length 8 (the same example as “BB Codes · Decoders”, §2.2). b₄ is flipped, c₃ and c₄ are lit. By enumeration the exact LLR of b₄ is −4.39 (flipped with probability about 0.99) and the other three are +4.39. BP decides correctly in iteration 1 (b₄ = −2.20), but then b₄ goes −6.59, −10.99, −6.59, −10.99, −15.38, …, reaching −28.56 at iteration 11, a net −8.79 every 4 iterations. Its own opinion travels once around the ring (8 edges = 4 iterations), comes back, and is added again as new evidence. What grows here is only confidence; the decision is right.

[7,4] Hamming 码，一个错误。这是经典编码里的老朋友：7 个比特，3 条检查，第 j 列是 j 的二进制写法（行 1 是最低位）。于是 c₁ 碰比特 1、3、5、7，c₂ 碰 2、3、6、7，c₃ 碰 4、5、6、7。任意两条检查共享两个比特，比如 c₁、c₂ 都碰 3 和 7，于是有长 4 的圈 比特 3 → c₁ → 比特 7 → c₂ → 比特 3（图 3.1）。比特 7 出错，三条检查都亮。穷举给出：比特 7 的 LLR −0.97，其他六个 +2.20；最可能的单个图样就是「只有比特 7」（后验 0.72）。

The [7,4] Hamming code, one error. An old friend of classical coding: 7 bits, 3 checks, column j is the binary expansion of j (row 1 is the lowest bit). So c₁ touches bits 1, 3, 5, 7, c₂ touches 2, 3, 6, 7, c₃ touches 4, 5, 6, 7. Any two checks share two bits; c₁ and c₂ both touch 3 and 7, giving the length-4 cycle bit 3 → c₁ → bit 7 → c₂ → bit 3 (Fig. 3.1). Bit 7 is flipped and all three checks are lit. Enumeration gives: LLR −0.97 for bit 7, +2.20 for the other six; the most likely single pattern is “bit 7 alone” (posterior 0.72).

BP 第 1 轮：每条检查亮着、有 4 个邻居，它对每个邻居说 −2 artanh(0.8³) = −1.13。比特 3 在 c₁、c₂ 里，收到两条 −1.13：2.20 − 2.26 = −0.06，判为出错；比特 5、6 同理；比特 7 收到三条：2.20 − 3.39 = −1.20。硬判决是 {3, 5, 6, 7}，它满足全部三条检查，带停止规则的 BP 在第 1 轮就「收敛」了。可残留 {3, 5, 6} 是 Hamming 码的一个码字（第 3、5、6 列相加为 0），这是一次译码失败，而精确的边缘 LLR 明确说比特 3 没错（+2.20）。错在哪里：c₁ 和 c₂ 都在「怪」比特 3，但两者的理由是同一件事，就是比特 7 大概没错时它们都需要别人来解释；把这两条消息相加，同一条理由算了两次。不停下的话，BP 在两种状态之间来回摆，在步进器的 Hamming 预设上可以看到。

BP iteration 1: each check is lit with 4 neighbours and tells each of them −2 artanh(0.8³) = −1.13. Bit 3 sits in c₁ and c₂ and receives two −1.13: 2.20 − 2.26 = −0.06, decided flipped; likewise bits 5 and 6; bit 7 receives three: 2.20 − 3.39 = −1.20. The hard decision {3, 5, 6, 7} satisfies all three checks, and BP with the stopping rule has “converged” after one iteration. But the residual {3, 5, 6} is a codeword of the Hamming code (columns 3, 5, 6 add to zero), so this is a decoding failure, while the exact marginal says plainly that bit 3 is clean (+2.20). What went wrong: c₁ and c₂ both “blame” bit 3, but for the same reason, namely that if bit 7 is probably clean then each of them needs someone else to explain it; adding their two messages counts that one reason twice. Without stopping, BP swings between two states, as the Hamming preset of the stepper shows.

本页的脚本算了各张 Tanner 图的围长：

The page’s script computed the girth of each Tanner graph:

最后一行解释了文献里一句常见的话。Poulin 与 Chung（arXiv:0801.1241）写道，对易条件「implies that the graph representing a QEC code must have weight-4 loops」，并在正文里论证：稳定子码若把全部检查画在一张图上，4 圈无法避免。那张图同时含 X 检查和 Z 检查。CSS 码把 X 错误和 Z 错误分开译码时（第 4 章），BP 跑在只含 H_Z（或只含 H_X）的图上，围长可以大于 4，比如表里的 6 和 8。短圈的问题并没有消失：gross 的 6 圈意味着消息 3 轮就回到自己。

The last row explains a sentence often met in the literature. Poulin and Chung (arXiv:0801.1241) write that the commutation condition “implies that the graph representing a QEC code must have weight-4 loops”, and argue in the body of the paper that a stabilizer code drawn with all its checks in one graph cannot avoid 4-cycles. That graph contains X checks and Z checks together. When a CSS code decodes X and Z errors separately (Chapter 4), BP runs on the graph of H_Z alone (or H_X alone), whose girth can exceed 4, like the 6 and 8 in the table. Short cycles do not go away: gross’s 6-cycles bring a message back to its sender in 3 iterations.

2.2 节读出过：检查消息的大小不超过其他邻居里最小的 |L|。min-sum检查规则的近似：m = (−1)^s · (其他邻居符号之积) · min |L|。只用比较和加法，没有 tanh；代价是系统地高估把握。乘一个系数 α < 1 叫归一化 min-sum。干脆把「不超过」当成「等于」：

§2.2 read off that a check message is no larger than the smallest |L| among the other neighbours. Min-sumAn approximation of the check rule: m = (−1)^s · (product of the other signs) · min |L|. Only comparisons and additions, no tanh; the price is a systematic overestimate of confidence. Multiplying by a factor α < 1 gives normalized min-sum. simply treats “at most” as “equal”:

好处是只剩比较大小和改符号，没有 tanh 与 artanh。坏处是系统地高估把握：三比特检查的例子里，精确消息 −1.52，普通 min-sum 给 −2.20，比特 a 的 LLR 从 0.68 掉到 0.00。所以通常乘一个小于 1 的系数 α：α = 0.8 给 −1.76，α = 0.625 给 −1.37。只有两个邻居的检查，普通 min-sum（α = 1）与精确规则完全相同（只有一个「其他邻居」），所以链和环上普通 min-sum 看不出差别（归一化 min-sum 仍会把每条消息乘上 α）；在 Hamming 预设上切换规则就能看到：普通 min-sum 第 1 轮给比特 3、5、6 的是 −2.20，比特 1、2、4 的是 0.00，比特 7 的是 −4.39（精确规则是 −0.06 与 −1.20），之后在两个状态之间来回摆。

The gain is that only comparisons and sign changes remain, no tanh or artanh. The cost is a systematic overestimate of confidence: in the three-bit check example the exact message is −1.52, plain min-sum gives −2.20, and bit a’s LLR drops from 0.68 to 0.00. Hence the usual factor α below 1: α = 0.8 gives −1.76, α = 0.625 gives −1.37. For a check with two neighbours plain min-sum (α = 1) equals the exact rule (there is only one “other neighbour”), so on chains and rings plain min-sum shows no difference (normalized min-sum still multiplies every message by α); switch rules on the Hamming preset to see it: plain min-sum gives bits 3, 5, 6 −2.20, bits 1, 2, 4 0.00 and bit 7 −4.39 in iteration 1 (the exact rule gives −0.06 and −1.20), then swings between two states.

实际用哪个 α，各文献不同，本页不评判好坏，只列出处。Panteleev 与 Kalachev（1904.02703）的全部模拟用「normalized min-sum (NMS) decoder with the normalization factor 0.625」，最多 32 轮。Roffe 等（2005.07016）附录用 min-sum，α 随轮数 t 变：α = 1 − 2^−t（引 Emran 与 Elsabrouty 2014）。ldpc 软件包的 ms_scaling_factor 默认 1.0，设成 0 时就用这条 1 − 2^−t（本页核对了 ldpc 2.4.1 的源码 bp.hpp）。《BB 码 · 译码器》的实验台用 0.8。

Which α to use differs between sources; the page does not judge, it lists them. Panteleev and Kalachev (1904.02703) run every simulation with the “normalized min-sum (NMS) decoder with the normalization factor 0.625”, at most 32 iterations. Roffe et al. (2005.07016) use min-sum in their appendix with α depending on the iteration t: α = 1 − 2^−t (citing Emran and Elsabrouty 2014). The ldpc package’s ms_scaling_factor defaults to 1.0, and setting it to 0 selects exactly this 1 − 2^−t (checked in ldpc 2.4.1’s source, bp.hpp). The bench of “BB Codes · Decoders” uses 0.8.

四比特环换成两个错误，放在 b₁、b₂ 上：c₂、c₄ 亮。BP 的四个 LLR 一起走 2.20、2.20、−2.20、−2.20、2.20、2.20……，每两轮换一次符号，永远停不下来（第 4 章会说它为什么在这里停不下来）。阻尼damping：每轮只把消息往新值挪一部分。本页的形式：新消息 = (1 − γ) × 本轮算出的值 + γ × 上一轮的值，从第 2 轮起使用（第 1 轮不加阻尼）。γ = 0 不加阻尼。让消息每轮只往新值挪一部分：

Give the four-bit ring two errors, on b₁ and b₂: c₂ and c₄ are lit. BP’s four LLRs move together through 2.20, 2.20, −2.20, −2.20, 2.20, 2.20, …, changing sign every two iterations and never settling (Chapter 4 explains why it cannot settle here). DampingMoving each message only part of the way to its new value every iteration. The form used here: new message = (1 − γ) × this iteration’s value + γ × last iteration’s value, applied from iteration 2 on (iteration 1 is undamped). γ = 0 means no damping. moves each message only part of the way to its new value:

γ = 0.5 时，b₁ 的 LLR 变成 2.20、2.20、0、−1.10、−1.10、−0.55、0、0.27、0.27、0.14、0、−0.07……，摆幅每 4 轮缩成四分之一，趋向 0。注意第 1 轮不加阻尼：此前没有「上一轮的消息」可混，本页的步进器和脚本都从第 2 轮起才按上式混合（若把第 0 轮的消息当成 0 来混，数列会变成 2.20、2.20、1.10、0、−0.55……，与上面不同）。0 恰好是精确答案（第 4 章），可 0 表示「一半一半」，硬判决 c = 0，症状仍亮。摇摆治好了，交不出修复的毛病还在。Müller 等（2506.01779，Relay-BP）的图 1 说明写的正是这件事：「A memory term can dampen oscillations, but symmetric trapping sets may lead to convergence to uncertain beliefs」。他们的「记忆」加在比特的先验上（每轮把先验换成 (1 − γ) × 原先验 + γ × 上一轮的总 LLR），与本页对消息的阻尼形式不同，作用相似：放慢更新。图注里的 trapping set陷阱集：少数几个比特和它们的检查组成的一小块结构，BP 的消息在里面来回强化或来回摇摆，走不出正确答案。对称的陷阱集里几个选择一样好，BP 没有理由选边。（陷阱集）指一小组比特和检查，BP 的消息在里面打转、走不出去；上面四比特环的两个错误就是一个对称的小例子：两种修复一样好，BP 没有理由选其中一边。在步进器上选「四比特环：两个错误」，把阻尼拖到 0.5，按「再走 10 轮」即可复现上面的数。

With γ = 0.5, b₁’s LLR becomes 2.20, 2.20, 0, −1.10, −1.10, −0.55, 0, 0.27, 0.27, 0.14, 0, −0.07, …; the swing shrinks fourfold every 4 iterations and tends to 0. Note that iteration 1 is not damped: there is no previous message to mix with yet, so the stepper and the scripts on this page apply the formula from iteration 2 on (mixing with a zero message in iteration 1 would give 2.20, 2.20, 1.10, 0, −0.55, …, a different sequence). Zero is exactly the right answer (Chapter 4), but zero means “fifty-fifty”, the hard decision is c = 0, and the syndrome stays lit. The oscillation is cured; the failure to return a repair remains. The Fig. 1 caption of Müller et al. (2506.01779, Relay-BP) says exactly this: “A memory term can dampen oscillations, but symmetric trapping sets may lead to convergence to uncertain beliefs”. Their “memory” acts on each bit’s prior (every iteration the prior becomes (1 − γ) × the original prior + γ × the previous total LLR), a different form from the message damping used here but with a similar effect: slower updates. The caption’s trapping setA small cluster of bits and their checks in which BP’s messages keep reinforcing each other or swinging back and forth, so BP never reaches the right answer. In a symmetric trapping set several choices are equally good and BP has no reason to pick one. means a small cluster of bits and checks in which BP’s messages go round without getting out; the ring with two errors above is a small symmetric example: two repairs are equally good, and BP has no reason to pick either. On the stepper, choose “4-qubit ring: two errors”, drag damping to 0.5 and press “10 more iterations” to reproduce the numbers above.

泛洪调度里，同一轮的所有检查用的是上一轮的比特消息。串行调度serial（分层，layered）schedule：检查按某个顺序一条一条发言，每发完一条，它碰到的比特立刻更新总 LLR 和回话，后面的检查马上用上新值。ldpc 软件包里是 schedule='serial'；泛洪对应 'parallel'。（也叫分层调度）让检查按顺序一条一条发言，每发完一条，它碰到的比特立刻更新，后面的检查在同一轮里就用上新值。五比特链（比特 3 出错）上按 c₁、c₂、c₃、c₄ 的顺序走一遍，结果是 (4.39, 2.20, −4.39, 6.59, 6.59)：信息沿扫描方向一口气传到了右端，右边两个比特已经是精确值 6.59。数一数每遍之后有几个比特已经精确：串行第 1、2、3 遍后是 2、3、4 个，泛洪第 1、2、3 轮后只有 0、1、3 个。扫描方向下游的比特先到位；逆着扫描方向，信息每遍只能往回走一条检查，比特 1 在扫描的起点，离链的另一端隔着 4 条检查：比特 5 那一头的证据逆着扫描方向每遍只退回一条检查（第 1 遍到 c₄，第 4 遍才到 c₁），所以五个比特全部精确仍然要第 4 遍，和泛洪的 4 轮一样。每条检查只有两个邻居，这些数可以用「消息 = ± 另一个邻居的 L」手算核对。

In the flooding schedule, all checks in an iteration use the bit messages of the previous iteration. The serial scheduleSerial (layered) schedule: checks speak one at a time in some order, and after each one the bits it touches update their totals and replies at once, so later checks use the new values immediately. In the ldpc package this is schedule='serial'; flooding corresponds to 'parallel'. (also called layered) lets checks speak one at a time in order; after each one, the bits it touches update at once, and later checks use the new values within the same iteration. On the five-bit chain (bit 3 flipped), one sweep in the order c₁, c₂, c₃, c₄ gives (4.39, 2.20, −4.39, 6.59, 6.59): information runs along the sweep direction to the right end in one go, and the two rightmost bits already hold the exact 6.59. Count the exact bits after each pass: 2, 3, 4 after serial sweeps 1, 2, 3, against 0, 1, 3 after flooding iterations 1, 2, 3. Bits downstream of the sweep get there first; against the sweep direction information moves back by only one check per sweep, and bit 1 sits where the sweep starts, four checks away from the far end of the chain: the evidence from bit 5’s end moves back one check per sweep (it reaches c₄ in sweep 1 and c₁ only in sweep 4), so all five bits are exact only after sweep 4, the same count as flooding’s 4 iterations. Each check has two neighbours, so these numbers can be checked by hand with “message = ± the other neighbour’s L”.

量子码上的结论只能按出处说。Panteleev 与 Kalachev 用 layered scheduling，「in order to increase the convergence speed of the decoder by approximately two times」（他们的码与去极化噪声）。Kuo 与 Lai（2002.06502）的摘要说，按串行调度运行并配合消息强度归一化，「may significantly improve the decoding performance and error floor in computer simulation」。错误平台error floor：把物理错误率 p 往下调时，译码失败率本应一路陡降，却在某处变平、降得很慢。原因通常是少数几种特定的小错误模式，译码器总是处理不好（例如落进陷阱集）。（error floor）指 p 调低后失败率本该陡降、却变平降不下去的那一段，通常由少数几种译码器总处理不好的小错误模式造成。du Crest 等（2308.13377）提出适合量子码的分层译码，摘要称它「outperforms flooded scheduling」，并发现随机顺序的调度能缓解消息传递译码器在量子码上常见的高错误平台。本页的实验台只实现泛洪调度。

Claims about quantum codes can only be stated per source. Panteleev and Kalachev use layered scheduling “in order to increase the convergence speed of the decoder by approximately two times” (for their codes, under depolarizing noise). Kuo and Lai’s abstract (2002.06502) says that running BP with message-strength normalization on a serial schedule “may significantly improve the decoding performance and error floor in computer simulation”. The error floorAs the physical error rate p is lowered, the decoding failure rate should keep falling steeply, but at some point it flattens and falls slowly. The usual cause is a few specific small error patterns that the decoder always gets wrong (for example, by falling into a trapping set). is the stretch where, as p is lowered, the failure rate flattens instead of dropping steeply, usually because of a few small error patterns the decoder always gets wrong. du Crest et al. (2308.13377) propose a layered decoding suited to quantum codes; their abstract says it “outperforms flooded scheduling”, and they find that a random-order schedule relieves the high error floor typical of message-passing decoders on quantum codes. The benches on this page implement only the flooding schedule.

一个 Pauli 错误可以拆成「X 部分」和「Z 部分」：Y = X 与 Z 同时出现（差一个相位，对纠错无关），所以一个错误写成两列 0/1，x 记哪些比特有 X 部分，z 记哪些有 Z 部分。CSS 码的 Z 检查只含 Z，只对 X 部分敏感；X 检查只对 Z 部分敏感。于是量子症状分成两半：s_Z = H_Z x 与 s_X = H_X z，各是一个第 1 章那样的经典译码问题。Roffe 等（2005.07016）的说法是：假设 X 与 Z 错误不相关，「the CSS code can be decoded independently as two classical codes」。第 0 到第 3 章做的就是其中一半。

A Pauli error splits into an “X part” and a “Z part”: Y is X and Z together (up to a phase, which does not matter for correction), so an error becomes two 0/1 columns, x marking the qubits with an X part and z those with a Z part. A CSS code’s Z checks contain only Z and respond only to the X part; its X checks respond only to the Z part. The quantum syndrome therefore splits in two: s_Z = H_Z x and s_X = H_X z, each a classical decoding problem like Chapter 1. Roffe et al. (2005.07016) put it this way: assuming uncorrelated X and Z errors, “the CSS code can be decoded independently as two classical codes”. Chapters 0 to 3 did one of the two halves.

去极化噪声depolarizing noise：每个比特以概率 p 出错，出错时 X、Y、Z 各占三分之一，即各 p/3。是量子纠错里最常用的模型：每个比特以概率 p 出错，出错时 X、Y、Z 各占一份，各 p/3。X 部分出错的情形是 X 或 Y，概率 2p/3；Z 部分同理。所以分开译码时，每一半的先验是 p_X = p_Z = 2p/3，L₀ = ln((1 − 2p/3)/(2p/3))。

Depolarizing noiseEach qubit is hit with probability p, and a hit is X, Y or Z with a third each, i.e. p/3 each. is the most common model in quantum error correction: each qubit is hit with probability p, and a hit is X, Y or Z, p/3 each. The X part is flipped when the error is X or Y, probability 2p/3; the same for the Z part. So with separate decoding each half has prior p_X = p_Z = 2p/3, L₀ = ln((1 − 2p/3)/(2p/3)).

丢掉的是两部分之间的关联。p = 0.1 时：两部分同时出错就是 Y，概率 p/3 = 0.033；若两部分独立，只会是 (2p/3)² = 0.0044，相差 7.5 倍。换个说法：已知某比特的 X 部分出错，它的 Z 部分出错的概率是 P(Y)/(P(X) + P(Y)) = 1/2，远高于不知情时的 2p/3 = 0.067。分开译码的两个 BP 互不通气，用不上这条信息。能用上它的做法是把每个比特当成四值（I、X、Y、Z）来传消息：Panteleev 与 Kalachev 写道，对去极化信道，「it is better to use the non-binary version of the syndrome BP decoder ... which also takes into account the correlations between X and Z errors in qubits」，Poulin 与 Chung 用的也是这种四值 BP。本页只讲分开译码的二值 BP；第 6 章的实验台只放 X 错误，那是码容量模型，不存在这个问题。

What is thrown away is the correlation between the two parts. For p = 0.1: both parts flipped means Y, probability p/3 = 0.033; if the parts were independent it would be (2p/3)² = 0.0044, 7.5 times less. Put differently: given that a qubit’s X part is flipped, its Z part is flipped with probability P(Y)/(P(X) + P(Y)) = 1/2, far above the uninformed 2p/3 = 0.067. The two BPs of separate decoding do not talk to each other and cannot use this. The way to use it is to pass messages about each qubit as a four-valued variable (I, X, Y, Z): Panteleev and Kalachev write that for the depolarizing channel “it is better to use the non-binary version of the syndrome BP decoder ... which also takes into account the correlations between X and Z errors in qubits”, and Poulin and Chung use such a four-valued BP as well. This page covers only binary BP with separate decoding; the bench of Chapter 6 has X errors only, the code-capacity model, where the issue does not arise.

第 0 章说过，修复只要与真实错误差一个稳定子就算成功。这叫退化degeneracy：不同的错误（修复）相差一个稳定子时效果完全相同。经典码没有这回事；qLDPC 码的稳定子很轻，退化极多。。经典码里没有这回事：经典码只有一个「稳定子」，就是零。qLDPC 码的检查很轻，稳定子也很轻，于是会出现许多同样轻、同样正确的修复。Poulin 与 Chung（0801.1241）的概括是：相差一个稳定子的错误「cannot and need not be distinguished by the error syndrome」，不能分辨，也不必分辨。

Chapter 0 said a repair succeeds as long as it differs from the true error by a stabilizer. This is degeneracyDifferent errors (repairs) that differ by a stabilizer act identically. Classical codes have nothing like it; in qLDPC codes the stabilizers are light and degeneracy is abundant.. Classical codes have nothing like it: their only “stabilizer” is zero. In a qLDPC code the checks are light, so are the stabilizers, and many repairs appear that are equally light and equally correct. Poulin and Chung (0801.1241) sum it up: errors that differ by a stabilizer “cannot and need not be distinguished by the error syndrome”.

最小的例子：四比特环加一条 X 检查。给 3.3 节的环添一条 X 检查 X₁X₂X₃X₄（它与每条 Z 检查共享两个比特，都对易），就得到一个小量子码。错误在 b₁、b₂，亮 c₂、c₄。与症状相符的修复恰好两个，{b₁, b₂} 和 {b₃, b₄}，概率相同；它们相差 X₁X₂X₃X₄，正是那条 X 检查，所以两个都对。精确答案因此是每个比特出错的概率都恰好 1/2，四个 LLR 全为 0。3.3 节的 BP 在 ±2.20 之间摇摆，加阻尼后趋于 0，两种情形都交不出修复：判决要么全 0，要么全 1，都让 H c = 0 ≠ s。不过这里「都对」来得太容易：这个小码 n = 4，rank H_Z = 3，rank H_X = 1，k = 4 − 3 − 1 = 0，一个逻辑比特也不编码，没有逻辑算符可以被翻错，任何满足症状的修复都自动算对（后面 Poulin 与 Chung 的两比特码，检查 XX、ZZ，也是 k = 0）。它只用来看清 BP 面对对称时的困境。k ≥ 1 时退化才真正考验译码器，因为满足症状的修复可能落在不同的类里；下面环面码的拐角错误（k = 2，四个类）就是这种情形。

The smallest example: the four-bit ring plus one X check. Add the X check X₁X₂X₃X₄ to the ring of §3.3 (it shares two qubits with every Z check, so all commute) and we have a small quantum code. The error is on b₁, b₂; c₂ and c₄ are lit. Exactly two repairs match, {b₁, b₂} and {b₃, b₄}, with equal probability; they differ by X₁X₂X₃X₄, the X check itself, so both are right. The exact answer is therefore that every qubit is flipped with probability exactly 1/2: all four LLRs are 0. BP in §3.3 swings between ±2.20, and with damping tends to 0; neither returns a repair, because the decisions are all 0 or all 1, and both give H c = 0 ≠ s. Here “both right” comes too cheaply, though: this small code has n = 4, rank H_Z = 3, rank H_X = 1, so k = 4 − 3 − 1 = 0. It encodes no logical qubit, there is no logical operator to get wrong, and every repair that matches the syndrome is automatically right (Poulin and Chung’s two-qubit code below, with checks XX and ZZ, also has k = 0). The example only shows BP’s trouble with symmetry. Degeneracy really tests a decoder when k ≥ 1, because repairs that match the syndrome can fall into different classes; the toric-code corner error below (k = 2, four classes) is that case.

在环面码上：一个拐角错误。3 × 3 环面码，X 错误在比特 4（横边 h(1,1)）和比特 14（竖边 v(2,1)）上，两条边在顶点 (2, 1) 拐了个弯，亮面 1 和面 5。图 4.1 画出最轻的两个修复：A = {4, 14}（真实错误本身）和 B = {5, 11}（绕顶点另一侧走）。A ⊕ B 恰好是顶点 (2, 1) 上的星形 X 检查，所以 A、B 属于同一类，都对。

On the toric code: a corner error. In the 3 × 3 toric code, X errors sit on qubit 4 (horizontal edge h(1,1)) and qubit 14 (vertical edge v(2,1)); the two edges turn a corner at vertex (2, 1) and light faces 1 and 5. Fig. 4.1 draws the two lightest repairs: A = {4, 14} (the true error itself) and B = {5, 11} (around the other side of the vertex). A ⊕ B is exactly the star X check at vertex (2, 1), so A and B are in the same class and both are right.

A、B 各占 0.352 的后验，比特 4、5、11、14 各自只分到其中一个，精确的边缘概率只有 0.40，LLR +0.40。逐位判决把四个都判成没错，交出的「修复」是空的，症状仍亮。BP 在这里其实算得很准：30 轮后是 +0.38，离精确值只差 0.02。失灵的不是 BP 的近似，而是 1.2 节的第二个问题本身：两个都对的答案把概率平分，每个比特单独看都不够格。这正是 1.2 节那条三比特检查的放大版。真正该比的是类：真实错误所在的类总概率 0.723，是四类里最大的，最优的「押类」译码器会选对；可 BP 只输出逐比特的数，没有「类」的概念。Poulin 与 Chung 的两比特例子（检查 XX、ZZ，错误 IX）是同一个现象的极端形式：「any decoding scheme based on qubit-wise probabilities will fail with this very simple code」。在第 2 章的步进器上选「3 × 3 环面码」，按「跑到收敛」，就能看到 LLR 停在 +0.38、判决满足 H c = s 一栏始终是「否」。

A and B each hold 0.352 of the posterior, and each of qubits 4, 5, 11, 14 belongs to only one of them, so its exact marginal flip probability is just 0.40, LLR +0.40. The bit-by-bit decision calls all four clean, the returned “repair” is empty, and the syndrome stays lit. BP is actually accurate here: after 30 iterations it gives +0.38, 0.02 from the exact value. What fails is not BP’s approximation but question 2 of §1.2 itself: two right answers split the probability, and no qubit qualifies on its own. It is the three-bit check of §1.2 magnified. What should be compared is classes: the class of the true error has total probability 0.723, the largest of the four, and an optimal “bet on the class” decoder would get it right; but BP outputs only per-qubit numbers and has no notion of a class. Poulin and Chung’s two-qubit example (checks XX and ZZ, error IX) is the extreme form of the same phenomenon: “any decoding scheme based on qubit-wise probabilities will fail with this very simple code”. On the stepper of Chapter 2, choose “3 × 3 toric code” and press “run to convergence”: the LLRs settle at +0.38 and “decisions satisfy Hc = s” stays “no”.

Poulin 与 Chung 提出的补救是在 BP 卡住时打破对称：随机「冻结」一个比特的先验、给先验加随机扰动，或配合他们称为 collision 的技巧，并报告了明显的改进。他们也写道，在所研究的全部情形里，失败的译码「100% ... were detected errors」，也就是症状没清零的那种；同一段稍后又说，唯一的例外是 Camara、Ollivier 与 Tillich（quant-ph/0502086，未在 QEC-Bank 登记）的码，他们发现那些码含有许多重量 6 的码字，所以在那里有一部分失败没被察觉。这指向一个结论：BP 之后缺一个能「选边站」的步骤。第 5 章的 OSD 就是它。

Poulin and Chung’s remedy is to break the symmetry when BP stalls: randomly “freeze” one qubit’s prior, add a random perturbation to the priors, or combine these with a trick they call collision; they report a clear improvement. They also write that in all the cases they investigated, “100% of the errors were detected errors”, i.e. failures where the syndrome was not cleared; later in the same paragraph they name the only exceptions, the codes of Camara, Ollivier and Tillich (quant-ph/0502086, not registered in the QEC-Bank), which they found to contain many weight-6 codewords, so there some failures went undetected. That points to one conclusion: after BP a step is missing that can pick a side. Chapter 5’s OSD is that step.

BP 在量子码上的失败要分成三种来听，它们的补救不同：

BP’s failures on quantum codes should be told apart into three kinds, because their remedies differ:

1. 摇摆：判决一轮一轮来回变，停不下来（四比特环的两个错误）。阻尼能压住摇摆，但压不出答案。
2. 判决不满足症状：LLR 稳定了，可判决拼起来 H c ≠ s（拐角错误的 +0.38）。这是 BP 特有的：匹配译码器永远交出一个清零症状的答案。OSD 专治这一种和上一种。
3. 押错类：判决满足 H c = s，但残留是逻辑算符（与某个 Z̄ 重叠奇数次，0.1 节）。症状已清零，OSD 不会被调用；即使调用，它也只保证 H c = s。

1. Oscillation: the decisions keep changing from iteration to iteration and never settle (the ring with two errors). Damping suppresses the swinging but does not produce an answer.
2. Decisions that miss the syndrome: the LLRs settle, but the decisions put together give H c ≠ s (the corner error’s +0.38). This is peculiar to BP: a matching decoder always returns an answer that clears the syndrome. OSD treats this failure and the previous one.
3. Wrong class: the decisions satisfy H c = s, but the residual is a logical operator (odd overlap with some Z̄, §0.1). The syndrome is cleared, so OSD is not called; even if it were, it only guarantees H c = s.

本页的脚本在 3 × 3 环面码上把全部 153 个两比特 X 错误都跑了一遍（精确 tanh 规则，最多 30 轮，p = 0.1），逐个用精确枚举判断最优的「押类」译码器会不会成功：

The page’s script ran all 153 two-qubit X errors on the 3 × 3 toric code (exact tanh rule, at most 30 iterations, p = 0.1), and for each one used exact enumeration to see whether the optimal “bet on the class” decoder would succeed:

这张表的范围要说清：码容量模型（只有 X 错误、测量完美）、最小的环面码、只有两比特错误、精确规则 30 轮。它说明三种失败在最小的量子码上就都出现，不说明更大的码上各占多少。

The scope of this table must be stated: the code-capacity model (X errors only, perfect measurements), the smallest toric code, two-qubit errors only, the exact rule for 30 iterations. It shows that all three failure modes occur already on the smallest quantum code; it says nothing about their shares in larger codes.

第 3、4 章的失败里，BP 的数并非没用。拐角错误上，比特 4、5、11、14 的 LLR 是 +0.38，其余都在 +2 以上：它清楚地指出了「嫌疑最大的四个」，只是没法在两个等价修复之间选边。缺的是一个保证 H c = s 的步骤，而「找一个满足 H c = s 的 c」是纯线性代数，一次高斯消元就够。OSD 的想法是让 BP 决定在哪里解：嫌疑大的比特放进方程组里当未知数，嫌疑小的直接设为 0。

In the failures of Chapters 3 and 4, BP’s numbers were not useless. On the corner error, qubits 4, 5, 11, 14 have LLR +0.38 and all the others are above +2: BP points plainly at “the four main suspects”, it just cannot pick a side between two equivalent repairs. What is missing is a step that guarantees H c = s, and “find a c with H c = s” is pure linear algebra, one Gaussian elimination. OSD’s idea is to let BP decide where to solve: suspicious qubits become unknowns in the system, unsuspicious ones are set to 0.

需要一个词：基集basis set（Roffe 等的叫法）：一组比特，个数等于 rank H，H 在这些列上线性独立。一旦其余比特的取值定下，这些比特的取值由 H c = s 唯一确定。。它是一组比特，个数等于 r = rank H，并且 H 在这些列上线性独立（没有哪几列相加等于另一列）。它的用处是：其余 n − r 个比特随便定个值，这组比特的取值就由 H c = s 唯一解出。OSD 沿 BP 的排序，从最可能出错的比特开始，一列一列地收，能收就收（这一列不能由已收的列相加得到），收满 r 个为止。收下的叫主元，其余叫非主元；主元组成的就是基集。读文献时留意一个叫法的差别：Panteleev 与 Kalachev（1904.02703）和 Fossorier 与 Lin 的经典 OSD 把另一半，也就是其余 n − r 个最可靠的比特（本页的非主元），叫作信息集information set：Panteleev–Kalachev 与经典 OSD 的叫法，指基集以外的 n − r 个最可靠的比特，也就是本页的非主元。本页不用这个词。（information set）。所以 PK 的 OSD-w 把信息集里最不可靠的前 w 个位置取遍所有值，这些位置正是本页排序最靠前的 w 个非主元。

One term is needed: a basis setRoffe et al.’s term. A set of qubits, as many as rank H, on whose columns H is linearly independent. Once the other qubits are fixed, the values of these qubits are determined uniquely by H c = s.. It is a set of qubits, r = rank H of them, on whose columns H is linearly independent (no few of the columns add up to another). Its use: give the other n − r qubits any values, and the values on this set follow uniquely from H c = s. OSD walks along BP’s ranking from the most suspicious qubit, accepting column after column whenever it can (the column is not a sum of columns already accepted), until r are accepted. The accepted ones are the pivots, the rest the non-pivots; the pivots form the basis set. When reading the literature, watch one difference in naming: Panteleev and Kalachev (1904.02703) and the classical OSD of Fossorier and Lin call the other part, the remaining n − r most reliable qubits (this page’s non-pivots), the information setThe term used by Panteleev–Kalachev and classical OSD for the n − r most reliable qubits outside the basis set, i.e. this page’s non-pivots. This page does not use the term.. So when PK’s OSD-w sets the first w least reliable positions of the information set to all possible values, those positions are exactly the first w non-pivots in this page’s ranking.

「逐列找主元」的标准做法是高斯消元。在二元域上只有一种操作：把一行加到另一行上（逐位 ⊕），症状位跟着一起加。两条方程相加仍是一条成立的方程，再加一次又变回来，所以这种操作不改变解。在四比特环的两个错误上做一遍（4.3 节，亮 c₂、c₄）。BP 30 轮后四个 LLR 都是 −2.20，一样大，按编号排：b₁, b₂, b₃, b₄。起点：

The standard way to “find pivots column by column” is Gaussian elimination. Over the binary field there is one operation: add one row to another (entry by entry, ⊕), with the syndrome bit added along. The sum of two valid equations is a valid equation, and adding again undoes it, so the operation does not change the solutions. Do it on the ring with two errors (§4.3, c₂ and c₄ lit). After 30 BP iterations all four LLRs are −2.20, a tie, broken by number: b₁, b₂, b₃, b₄. The start:

列 b₁：行 1 有 1，它当主元行；行 4 也有 1，行 4 ← 行 4 ⊕ 行 1 = (0, 1, 0, 1 | 1)。列 b₂：从行 2 起找，行 2 有 1，当主元行；消掉行 1 与行 4 的 1：行 1 ← (1, 0, 1, 0 | 1)，行 4 ← (0, 0, 1, 1 | 0)。列 b₃：行 3 当主元行；消掉行 1、2、4 的 1，得到右半边的表。列 b₄：剩下的行 4 全是 0，没有主元：b₄ 的列 (0, 0, 1, 1) 恰好是前三列之和。主元是 b₁, b₂, b₃（基集，个数 3 = rank H），非主元是 b₄。行 4 的症状位是 0，与全零的左边一致，方程组有解。一共 6 次行加法，与实验台上的步数相同。

Column b₁: row 1 has a 1 and becomes the pivot row; row 4 also has a 1, so row 4 ← row 4 ⊕ row 1 = (0, 1, 0, 1 | 1). Column b₂: search from row 2; row 2 has a 1 and becomes the pivot row; clear the 1s in rows 1 and 4: row 1 ← (1, 0, 1, 0 | 1), row 4 ← (0, 0, 1, 1 | 0). Column b₃: row 3 becomes the pivot row; clearing rows 1, 2, 4 gives the right half of the table. Column b₄: the remaining row 4 is all zeros, no pivot: b₄’s column (0, 0, 1, 1) is exactly the sum of the first three. The pivots are b₁, b₂, b₃ (the basis set, 3 = rank H of them) and the non-pivot is b₄. Row 4’s syndrome bit is 0, matching its all-zero left side, so the system has a solution. Six row additions in all, the same count as on the bench.

0 阶 OSDOSD-0：非主元全设为 0，只解一次方程，不尝试任何改动。消元后每个主元比特直接等于它那一行的症状位。（OSD-0）把非主元全设为 0。消元后的矩阵里每个主元列只在自己那一行有 1，所以每个主元比特直接等于它那一行的症状位：右表给出 b₁ = 1、b₂ = 1、b₃ = 0，再加 b₄ = 0，修复 {b₁, b₂}，恰好是真实错误。换一个排序，让 b₁ 或 b₂ 排到最后，比如 b₃, b₄, b₁, b₂：主元依次是 b₃、b₄、b₁，b₂ 成为非主元，OSD-0 得到 {b₃, b₄}，同样正确。只把 b₄ 提到最前（b₄, b₁, b₂, b₃）不够：非主元变成 b₃，解仍是 {b₁, b₂}。这就是 OSD 在退化面前的作用：排序里先到的比特进基集，平局就此打破，交出等价修复中的一个。

Order-0 OSDOSD-0: set every non-pivot to 0 and solve once, trying no changes. After elimination each pivot qubit equals the syndrome bit of its row. (OSD-0) sets every non-pivot to 0. In the eliminated matrix each pivot column has a 1 only in its own row, so each pivot qubit simply equals its row’s syndrome bit: the right table gives b₁ = 1, b₂ = 1, b₃ = 0, plus b₄ = 0, repair {b₁, b₂}, which is the true error. An ordering that puts b₁ or b₂ last, say b₃, b₄, b₁, b₂, makes b₃, b₄, b₁ the pivots and b₂ the non-pivot, and OSD-0 returns {b₃, b₄}, equally right. Moving only b₄ to the front (b₄, b₁, b₂, b₃) is not enough: the non-pivot becomes b₃ and the solution is still {b₁, b₂}. That is what OSD does against degeneracy: qubits earlier in the ranking enter the basis set, the tie is broken, and one of the equivalent repairs comes out.

保证只有一条：只要症状确实来自某个错误（方程组有解），OSD 交出的 c 满足 H c = s。它不保证残留是稳定子。拐角错误上，BP 的排序以 4、5、11、14 开头（LLR 相同，按编号），主元依次收下 4、5、11，14 的列被前三列表出，成为非主元；OSD-0 交出 {5, 11}，是图 4.1 的修复 B，与真实错误 {4, 14} 同类，成功。Hamming 码（比特 7 出错）是另一种情形：BP 第 1 轮已经「收敛」到 {3, 5, 6, 7}，标准的 BP-OSD 在收敛时不调用 OSD，所以交出的仍是这个错误答案（3.1 节）。若拿第 1 轮的 LLR 强行跑 OSD-0，排序是 7, 3, 5, 6, 1, 2, 4，主元 7、3、5，解出 {7}，正确。

The guarantee is exactly one: as long as the syndrome really came from some error (the system has a solution), the c returned by OSD satisfies H c = s. It does not guarantee a stabilizer residual. On the corner error BP’s ranking starts with 4, 5, 11, 14 (equal LLRs, by number); the pivots accept 4, 5, 11, and 14’s column is expressed by those three and becomes a non-pivot; OSD-0 returns {5, 11}, repair B of Fig. 4.1, in the same class as the true error {4, 14}: success. The Hamming code (bit 7 flipped) is a different case: BP has already “converged” to {3, 5, 6, 7} in iteration 1, standard BP-OSD does not call OSD after convergence, and the wrong answer stands (§3.1). Running OSD-0 anyway with the iteration-1 LLRs gives the order 7, 3, 5, 6, 1, 2, 4, pivots 7, 3, 5, and the solution {7}, which is right.

下面的步进器把整个过程一步一步放出来：BP 的 LLR 与排序、按排序重排的矩阵、每一次换行和行加法（主元橙框，目标行加底色，★ 标出已收下的主元列）、基集、OSD-0 的解，以及（若选 OSD-E 或 OSD-CS）全部候选。最后一步是 5.6 节的对照。

The stepper below shows the whole process step by step: BP’s LLRs and the ranking, the matrix reordered by the ranking, every row swap and row addition (pivot in an orange box, target row shaded, ★ marking accepted pivot columns), the basis set, the OSD-0 solution, and (for OSD-E or OSD-CS) every candidate. The last step is the comparison of §5.6.

OSD-0 把非主元全押成 0。非主元里排得靠前的，BP 认为也有些嫌疑，值得试着设成 1：每设一种非主元图样 t，主元就重新解一次（主元 = 化简后的症状 ⊕ 被翻的非主元列在化简矩阵里的那几列），得到另一个满足 H c = s 的修复。所有候选里挑最可能的一个。OSD 阶数OSD order：允许在非主元上尝试的改动的规模。OSD-E 试前 w 个非主元的全部 2^w 种取值；OSD-CS 试每个非主元单独翻，外加前 λ 个里的全部两两组合。ldpc 软件包里都叫 osd_order。规定试多少种。常见的两种：

OSD-0 bets every non-pivot on 0. Non-pivots near the front of the ranking are somewhat suspicious in BP’s eyes too, and are worth trying as 1: for each non-pivot pattern t, the pivots are solved again (pivots = the reduced syndrome ⊕ the reduced-matrix columns of the flipped non-pivots), giving another repair with H c = s. The most likely candidate wins. The OSD orderThe size of the set of changes tried on the non-pivots. OSD-E tries all 2^w values of the first w non-pivots; OSD-CS tries each non-pivot flipped alone plus every pair among the first λ. The ldpc package calls both osd_order. says how many. The two common ones:

• OSD-E（穷举，exhaustive）：排序后最靠前的 w 个非主元取遍全部 2^w 种 0/1 组合，共 2^w 个候选（含 OSD-0）。这是 Panteleev 与 Kalachev（1904.02703）的 OSD-w；Roffe 等（2005.07016）把它称为 OSD-E。
• OSD-CS（组合扫描，combination sweep）：每个非主元单独翻一次（k′ = n − r 个），再在前 λ 个非主元里取全部两两组合（C(λ,2) 个），在 OSD-0 之外共 k′ + C(λ, 2) 个候选。这是 Roffe 等的原文定义，他们说全部模拟都取 λ = 60（下一段引用的附录比较例外，用 λ = 86）；ldpc 软件包 2.4.1 的源码（osd.hpp）按同样的规则生成候选，λ 就是参数 osd_order，但有一个例外：osd_order = 0（ldpc 的默认值）时，无论选哪种方法都只做 OSD-0，不做 k′ 个单独翻转。所以本页实验台的 λ 从 1 起。

• OSD-E (exhaustive): the first w non-pivots in the ranking take all 2^w combinations of 0/1, 2^w candidates in all (OSD-0 included). This is the OSD-w of Panteleev and Kalachev (1904.02703); Roffe et al. (2005.07016) call it OSD-E.
• OSD-CS (combination sweep): flip each non-pivot alone (k′ = n − r of them), then every pair among the first λ non-pivots (C(λ,2) of them), k′ + C(λ, 2) candidates besides OSD-0. This is the definition in Roffe et al., who say they use λ = 60 in all their simulations (except the appendix comparison quoted in the next paragraph, which uses λ = 86); the source of the ldpc package 2.4.1 (osd.hpp) generates candidates by the same rule, with λ being the parameter osd_order, with one exception: at osd_order = 0 (ldpc’s default) every method does plain OSD-0, without the k′ single flips. That is why the bench on this page starts λ at 1.

候选数可以核对一个文献里的数。Roffe 等在附录里比较 d = 15 的环面码：OSD-E 取 λ = 12，「a total of 4096 search terms」；OSD-CS 取 λ = 86，「a total of 3881」。本页的脚本算出这个环面码的 H_Z 有 n = 450、rank 224，所以 k′ = 226，226 + C(86, 2) = 226 + 3655 = 3881；2¹² = 4096。两个数都对得上。他们报告在候选数相近时，组合扫描比穷举略好（「a modest improvement」）。Panteleev 与 Kalachev 也提醒，他们的 OSD-w 与 Fossorier 和 Lin（1995）的经典 OSD 不同：经典做法试的是「不超过 w 个比特」的全部翻法，共 Σ_i≤w C(k, i) 种，而他们试的是前 w 个的全部 2^w 种。

The candidate counts can be checked against a number in the literature. In their appendix Roffe et al. compare, on the distance-15 toric code, OSD-E with λ = 12, “a total of 4096 search terms”, and OSD-CS with λ = 86, “a total of 3881”. The page’s script finds n = 450 and rank 224 for that toric code’s H_Z, so k′ = 226 and 226 + C(86, 2) = 226 + 3655 = 3881; 2¹² = 4096. Both numbers match. They report that with a similar number of candidates the combination sweep does slightly better than the exhaustive one (“a modest improvement”). Panteleev and Kalachev also point out that their OSD-w differs from the classical OSD of Fossorier and Lin (1995): the classical version tries every flip of “at most w bits”, Σ_i≤w C(k, i) of them, while theirs tries all 2^w settings of the first w.

打分。独立噪声下，修复 c 的概率正比于 ∏_cj=1 p_j/(1 − p_j)，所以「最可能」等价于「Σ_cj=1 ln((1 − p_j)/p_j) 最小」，本页的实验台用这个分数。所有 p_j 相同时，它就是重量乘一个常数：挑最轻的。ldpc 源码与 Bravyi 等（2308.07915）的补充材料用的是 Σ ln(1/p_j)；p 全相同时排名完全一样，p 不同时（第 7 章的电路级译码）二者在 p 很小时很接近。另一个细节：Roffe 等与 ldpc 的 OSD-0 把非主元设为 0，Panteleev 与 Kalachev 的原文把它们设为 BP 的硬判决。两种做法在「每个 LLR 为负的比特都进了基集」时完全一致，因为排序把负 LLR 放在最前。

Scoring. Under independent noise the probability of a repair c is proportional to ∏_cj=1 p_j/(1 − p_j), so “most likely” means “smallest Σ_cj=1 ln((1 − p_j)/p_j)”, the score used on this page’s benches. When all p_j are equal it is the weight times a constant: pick the lightest. The ldpc source and the supplement of Bravyi et al. (2308.07915) use Σ ln(1/p_j); with equal p the ranking is identical, and with unequal p (circuit-level decoding, Chapter 7) the two are close when p is small. One more detail: Roffe et al. and ldpc set the non-pivots to 0 in OSD-0, while Panteleev and Kalachev set them to BP’s hard decisions. The two agree whenever every qubit with a negative LLR lands in the basis set, since the ranking puts negative LLRs first.

在步进器上选 OSD-E 或 OSD-CS 可以看候选表。Hamming 码的例子里，非主元按排序是 6, 1, 2, 4；OSD-E 取 w = 2 试 {}、{6}、{1}、{6, 1} 四种，得到重量 1、4、3、2 的修复，挑 {7}。

Choose OSD-E or OSD-CS on the stepper to see the candidate table. In the Hamming example the non-pivots in order are 6, 1, 2, 4; OSD-E with w = 2 tries {}, {6}, {1}, {6, 1}, giving repairs of weight 1, 4, 3, 2, and picks {7}.

对 m × n 的矩阵做消元，每个主元要扫一遍所有行、每行最多 n 位，工作量大约 m · n · r 次位运算。qLDPC 码里 m、r 都与 n 成正比，所以是 O(n³)：n 翻倍，时间最多约 8 倍。Panteleev 与 Kalachev 写道，很多情形下 OSD-0 就够了，「the computational cost of the decoding is O(n³)」，一般的 OSD-w 是 O(n³ + n 2^w)。ldpc 的文档说它的 OSD-0 用一种提前终止的消元（fast-solve），「terminates the Gaussian elimination as soon as the syndrome becomes linearly dependent on the columns eliminated up to that point」。

Eliminating an m × n matrix scans every row for each pivot, up to n bits per row, about m · n · r bit operations. In qLDPC codes m and r are proportional to n, so this is O(n³): doubling n multiplies the time by at most about 8. Panteleev and Kalachev write that in many cases OSD-0 is enough and “the computational cost of the decoding is O(n³)”, while general OSD-w costs O(n³ + n 2^w). The ldpc documentation says its OSD-0 uses an early-stopping elimination (fast-solve) that “terminates the Gaussian elimination as soon as the syndrome becomes linearly dependent on the columns eliminated up to that point”.

和 BP 对比就看出问题所在：BP 每轮的工作量与边数成正比，每条边上的计算只用邻居的数，可以大规模并行；高斯消元每一步都要看整张矩阵，行与行之间有先后依赖，耗时还随症状变化。实时纠错要求译码跟上症状产生的速度，所以在 BP-OSD 里拖慢速度的通常是 OSD 这一步。第 7 章的几种新方法主要就是冲着它来的。

The comparison with BP shows the problem: BP’s work per iteration is proportional to the number of edges, and each edge uses only its neighbours’ numbers, so it parallelizes massively; each step of Gaussian elimination looks at the whole matrix, rows depend on earlier steps, and the time varies with the syndrome. Real-time correction needs decoding to keep pace with the syndromes, so in BP-OSD the step that usually sets the pace is OSD. Several newer methods in Chapter 7 target exactly this.

QEC-Bank 的译码器登记表里有一条不看任何概率的基线 css-pivot，原文：「Solves the X- and Z-syndrome linear systems by left-to-right GF(2) elimination with free variables fixed to zero; it scales polynomially but ignores likelihoods and degeneracy, so it is a reproducible baseline rather than a competitive decoder」。换成本章的话：它就是按编号顺序（而不是按 BP 的排序）做的 OSD-0。两者唯一的差别是列的顺序，所以把它们放在一起，就能看出 BP 的排序值多少。

The QEC-Bank decoder registry has a baseline, css-pivot, that ignores all probabilities: “Solves the X- and Z-syndrome linear systems by left-to-right GF(2) elimination with free variables fixed to zero; it scales polynomially but ignores likelihoods and degeneracy, so it is a reproducible baseline rather than a competitive decoder”. In this chapter’s words: it is OSD-0 in index order instead of BP’s ranking. The only difference between the two is the column order, so putting them side by side shows what BP’s ranking is worth.

• Hamming 码，比特 7 出错。按编号，最先独立的三列是 1、2、4（第 3 列 = 第 1 列 + 第 2 列），于是比特 3、5、6、7 都被强制为 0。症状 (1, 1, 1) = 第 1、2、4 列之和，解出 {1, 2, 4}，重量 3；残留 {1, 2, 4, 7} 是一个码字，失败。按 BP 排序的 OSD-0 解出 {7}。
• 环面码的拐角错误。按编号的主元是 0, 1, 2, 3, 4, 5, 9, 10，比特 11 和 14 被强制为 0，解出 {5, 9, 10}，重量 3，残留与 Z̄ 重叠奇数次，失败。按 BP 排序的 OSD-0 交出 {5, 11}，成功。4.4 节的清点里，BP 不收敛的 54 个两比特错误，OSD-0 全部成功，css-pivot 失败 20 个。

• Hamming code, bit 7 flipped. By index the first three independent columns are 1, 2, 4 (column 3 = column 1 + column 2), so bits 3, 5, 6, 7 are forced to 0. The syndrome (1, 1, 1) is the sum of columns 1, 2, 4, giving {1, 2, 4}, weight 3; the residual {1, 2, 4, 7} is a codeword: failure. OSD-0 in BP’s ranking gives {7}.
• The toric code’s corner error. The index-order pivots are 0, 1, 2, 3, 4, 5, 9, 10; qubits 11 and 14 are forced to 0, the solution is {5, 9, 10}, weight 3, and the residual overlaps Z̄ an odd number of times: failure. OSD-0 in BP’s ranking returns {5, 11}: success. In the count of §4.4, OSD-0 succeeded on all 54 two-qubit errors where BP did not converge, and css-pivot failed on 20.

两者的消元一模一样，差别全在「让哪些比特当未知数」：按编号，最可能出错的比特常常被排在非主元里、被强制设成 0，方程只好用一堆别的比特去凑症状，凑出来的修复更重，更容易落进错误的类。在步进器上选好预设后按「跳到结尾」，就能看到两个结果并排。

The elimination is identical; the whole difference is which qubits are made unknowns. In index order the most suspicious qubits often end up as non-pivots forced to 0, the system has to assemble the syndrome from other qubits, and the resulting repair is heavier and more likely to land in the wrong class. Choose a preset on the stepper and press “jump to the end” to see both results side by side.

标准 BP-OSD 一次译码的全部步骤：由每个比特的出错概率 p_j 算出先验 L₀ = ln((1 − p_j)/p_j)；跑 BP，最多 max_iter 轮，每轮后做硬判决，满足 H c = s 就停下交出 c；若跑满仍不满足，用最后一轮的 LLR 排序，做 OSD（0 阶或更高阶），交出它的解。Roffe 等描述他们的实现时写道：「the OSD post-processing step is called when the BP algorithm fails to converge」。

One decoding with standard BP-OSD, complete: from each qubit’s flip probability p_j compute the prior L₀ = ln((1 − p_j)/p_j); run BP for at most max_iter iterations, taking a hard decision after each and stopping with c as soon as H c = s; if the decisions still miss the syndrome at the end, rank by the last LLRs, run OSD (order 0 or higher) and return its solution. Roffe et al. describe their implementation: “the OSD post-processing step is called when the BP algorithm fails to converge”.

ldpc 软件包Joschka Roffe 等维护的开源 Python/C++ 库（pip 包名 ldpc），实现 BP、BP-OSD、BP-LSD 等译码器。本页核对的是 2.4.1 版的文档字符串与 C++ 源码。（pip 包名 ldpc，Roffe 等维护）的 BpOsdDecoder 把上面每个选择都做成参数。下表逐条对照本页的章节；每一条都核对过 2.4.1 版的文档字符串和 GitHub 上的 C++ 源码（bp.hpp、osd.hpp）：

The BpOsdDecoder of the ldpc packageAn open-source Python/C++ library maintained by Joschka Roffe and others (pip name ldpc) implementing BP, BP-OSD, BP-LSD and other decoders. This page checked the docstrings and C++ source of version 2.4.1. (pip name ldpc, maintained by Roffe et al.) turns each of these choices into a parameter. The table matches each one to a section of this page; every entry was checked against the docstrings of version 2.4.1 and the C++ source on GitHub (bp.hpp, osd.hpp):

两处细节与本页不同，写下来免得对不上：ldpc 的硬判决把 L ≤ 0 判为出错（本页是 L < 0，只在 L 恰好为 0 时有差别）；它的 OSD 按 Σ ln(1/p_j) 给候选打分（5.4 节，p 全相同时与本页等价）。本页的脚本 notes/bp-osd/ldpc_check.py 把本页的 BP-OSD 与 ldpc 2.4.1 放在同一批随机症状上比较（归一化 min-sum，α = 0.625，泛洪，max_iter = 30）：BP 是否收敛在全部试验里一致；逻辑失败次数，L = 4 环面码（p = 0.05，2000 次，OSD-CS λ = 6）ldpc 169、本页 171，L = 6 环面码（p = 0.08，1000 次）OSD-0 为 173 与 174、OSD-CS（λ = 10）为 174 与 175，[[72,12,6]]（p = 0.04，1000 次，OSD-CS λ = 10）为 88 与 86。个别修复不同，来自 LLR 相同的比特之间的排序差异。调用方式如下（与 ldpc_check.py 相同）：

Two details differ from this page and are noted so the numbers line up: ldpc’s hard decision calls L ≤ 0 flipped (this page uses L < 0; they differ only when L is exactly 0); its OSD scores candidates by Σ ln(1/p_j) (§5.4, equivalent to this page when all p are equal). The page’s script notes/bp-osd/ldpc_check.py compares this page’s BP-OSD with ldpc 2.4.1 on the same random syndromes (normalized min-sum, α = 0.625, flooding, max_iter = 30): whether BP converged agrees in every trial; logical failures: L = 4 toric code (p = 0.05, 2000 trials, OSD-CS λ = 6) ldpc 169, this page 171; L = 6 toric code (p = 0.08, 1000 trials) OSD-0 173 and 174, OSD-CS (λ = 10) 174 and 175; [[72,12,6]] (p = 0.04, 1000 trials, OSD-CS λ = 10) 88 and 86. The occasional different repair comes from ordering qubits whose LLRs are equal. The call looks like this (as in ldpc_check.py):

下面的实验台在码容量模型code-capacity model：只有数据比特出错（这里只放 X 错误，每个比特独立以概率 p），测量完美。它是最简单的噪声模型，数字比电路级噪声下好看得多，不能与之混用。下比较四个译码器：只有 X 错误、每个比特独立以概率 p 出错、测量完美。每次试验抽一个错误，算出症状，交给 (1) 只用 BP（未收敛算失败），(2) BP + OSD-0，(3) BP + OSD-CS，(4) QEC-Bank 的 css-pivot 基线；残留与某个 Z̄ 重叠奇数次就记一次失败（0.1 节）。失败率旁边是 95% Wilson 区间由 k 次失败 / N 次试验算出的二项分布置信区间，比「k/N ± 1.96√(k/N(1−k/N)/N)」在 k 很小时更可靠。它只反映抽样的随机性。，只反映抽样的随机性；这些数只属于所选的码、这个噪声模型和这些设置。随机数由种子决定，同一种子每次得到同样的错误序列；notes/bp-osd/benchcheck.py 在浏览器里驱动这个实验台，再用 Python 复算同样的设置，计数完全相同。

The bench below compares four decoders under the code-capacity modelOnly data qubits fail (here only X errors, each qubit independently with probability p), and measurements are perfect. The simplest noise model; its numbers look far better than under circuit-level noise and must not be mixed with them.: X errors only, each qubit flipped independently with probability p, perfect measurements. Each trial draws an error, computes the syndrome and hands it to (1) BP alone (non-convergence counts as failure), (2) BP + OSD-0, (3) BP + OSD-CS, (4) the QEC-Bank css-pivot baseline; a residual that overlaps some Z̄ an odd number of times counts as a failure (§0.1). Next to each rate is a 95% Wilson intervalA confidence interval for a binomial rate computed from k failures in N trials; more reliable than “k/N ± 1.96√(k/N(1−k/N)/N)” when k is small. It reflects sampling randomness only., which reflects sampling randomness only; the numbers belong only to the chosen code, this noise model and these settings. The random numbers are set by the seed, and a given seed always produces the same error sequence; notes/bp-osd/benchcheck.py drives this bench in a browser and reruns the same settings in Python, with identical counts.

默认设置（L = 6 环面码，p = 0.05，N = 500，max_iter = 30，λ = 10，种子 1）的结果是：只用 BP 失败 194 次（失败率 0.388，区间 [0.346, 0.431]），BP + OSD-0 失败 18 次（0.036，[0.023, 0.056]），BP + OSD-CS 失败 19 次（0.038，[0.024, 0.059]），css-pivot 失败 202 次（0.404，[0.362, 0.448]）。可以读出三件事。第一，环面码上 BP 单独很差：500 次里只有 308 次收敛，退化让它交不出修复（第 4 章）。第二，OSD 把绝大部分不收敛的情形救了回来，而按编号顺序做同样的消元（css-pivot）几乎没有用：差别全在 BP 的排序。第三，这一批样本里 OSD-CS 比 OSD-0 多失败 1 次：更高阶挑的是更轻的修复，更轻不保证是对的类，而且两个区间大部分重叠，这 1 次差别在抽样误差之内。换成 [[72,12,6]]（同样 p = 0.05、种子 1）是另一种图景：BP 收敛 425 次，但收敛后押错类的有 33 次，OSD 管不到它们；三种 BP 类译码器失败 108、93、90 次，css-pivot 失败 435 次。

The default settings (L = 6 toric code, p = 0.05, N = 500, max_iter = 30, λ = 10, seed 1) give: BP alone fails 194 times (rate 0.388, interval [0.346, 0.431]), BP + OSD-0 18 times (0.036, [0.023, 0.056]), BP + OSD-CS 19 times (0.038, [0.024, 0.059]), css-pivot 202 times (0.404, [0.362, 0.448]). Three things can be read off. First, BP alone is poor on the toric code: only 308 of 500 trials converge, because degeneracy keeps it from returning a repair (Chapter 4). Second, OSD rescues the great majority of the non-converged cases, while the same elimination in index order (css-pivot) barely helps: the whole difference is BP’s ranking. Third, in this sample OSD-CS fails once more than OSD-0: a higher order picks lighter repairs, lighter does not guarantee the right class, and the two intervals overlap almost entirely, so the difference of one is within sampling error. The [[72,12,6]] code (same p = 0.05, seed 1) looks different: BP converges 425 times, but 33 of those converge to the wrong class, which OSD cannot touch; the three BP-based decoders fail 108, 93 and 90 times, css-pivot 435 times.

值得自己试的：把 p 从 0.02 拖到 0.12，看 BP 单独与 BP + OSD 的差距怎样随 p 变化；把 max_iter 从 30 改成 10，看 BP 收敛次数少了多少、OSD 接手后结果又差多少；在 L = 4、5、6 之间切换同一个 p，看码变大时失败率怎样变（这是阈值的雏形，但三个小码、几百次试验远不足以估计阈值）。

Worth trying yourself: drag p from 0.02 to 0.12 and watch how the gap between BP alone and BP + OSD changes; change max_iter from 30 to 10 and see how many fewer trials converge and how much worse the result is once OSD takes over; switch between L = 4, 5, 6 at a fixed p and see how the failure rate changes with code size (the seed of a threshold, although three small codes and a few hundred trials are far from enough to estimate one).

一个译码数字至少要带着：哪个码、哪种噪声模型、哪个译码器的哪种设置、怎么得到的（算出、界出，还是模拟后怎样估计），以及出处。下面三条都按这个格式写，引文都核对过 arXiv 上的 TeX 源文件。

A decoding number needs at least: which code, which noise model, which decoder with which settings, how it was obtained (computed, bounded, or simulated and estimated how), and the source. The three entries below follow that format; the quotations were checked against the TeX sources on arXiv.

• Roffe、White、Burton、Campbell 2020（2005.07016）：环面码，d = 9、11、13、15；码容量模型，只模拟 X 错误（假设 X、Z 不相关，「it suffices to simulate a single error species」）；BP 为 min-sum，α = 1 − 2^−t，最多 n 轮；OSD-CS，λ = 60。他们从不同 d 的曲线交点读出阈值：BP + OSD-CS「in the region 9.9 ± 0.2%」，BP + OSD-0 为 9.2 ± 0.2%；只用 BP 没有阈值（码越大越差）。文中没有说明 ±0.2% 是怎样估出来的。
• Panteleev、Kalachev 2019（1904.02703）：去极化信道；四值 BP 的归一化 min-sum 近似，系数 0.625，最多 32 轮，分层调度；多数情形只用 OSD-0；指标是字错误率（WER，一个码块里至少一个逻辑比特出错或译码失败的比例）。对 [[882,24]] 广义超图积码，BP-OSD 相对 BP 的 WER 改进「up to 5 orders of magnitude」；对列重为 5 的 [[254,28]] 广义 bicycle 码，改进很小。
• Bravyi 等 2023（2308.07915）：BB 码（含 gross 码）的深度 7 症状测量电路，电路级噪声，N_c = d 轮测量；BP-OSD 扩展到电路级的「线性化噪声模型」（第 7 章），用 Roffe 等的软件，「MIN-SUM belief propagation with the limit of 10,000 iterations and combination sweep version of OSD」；除最小的错误率外每个数据点至少累积 100 次逻辑错误，误差棒约 p_L/10。常被引用的 0.8% 不是「几种尺寸的曲线交点」，而是对每个码分别求解 p_L(p) = kp（整块每轮的失败率等于 k 个裸比特的近似失败率）的伪阈值；v1 表 1 给出 0.007 到 0.008 之间，v2 给出 0.0048 到 0.0069。完整的五个限定项见《BB 码 · 译码器》3.3 节，这里不再展开。

• Roffe, White, Burton, Campbell 2020 (2005.07016): toric codes, d = 9, 11, 13, 15; code-capacity model, simulating X errors only (X and Z assumed uncorrelated, “it suffices to simulate a single error species”); BP is min-sum with α = 1 − 2^−t, at most n iterations; OSD-CS with λ = 60. They read thresholds off the crossings of the curves for different d: BP + OSD-CS “in the region 9.9 ± 0.2%”, BP + OSD-0 9.2 ± 0.2%; BP alone shows no threshold (larger codes do worse). The text does not say how the ±0.2% was estimated.
• Panteleev, Kalachev 2019 (1904.02703): depolarizing channel; a normalized min-sum approximation of four-valued BP with factor 0.625, at most 32 iterations, layered schedule; OSD-0 in most cases; the metric is the word error rate (WER, the fraction of code blocks with at least one logical error or a decoding failure). For the [[882,24]] generalized hypergraph-product code the WER improvement of BP-OSD over BP is “up to 5 orders of magnitude”; for the [[254,28]] generalized bicycle code with column weight 5 the improvement is small.
• Bravyi et al. 2023 (2308.07915): depth-7 syndrome-measurement circuits for BB codes (gross included), circuit-level noise, N_c = d measurement rounds; BP-OSD extended to a circuit-level “linearized noise model” (Chapter 7), using Roffe et al.’s software with “MIN-SUM belief propagation with the limit of 10,000 iterations and combination sweep version of OSD”; every data point except the smallest error rates accumulated at least 100 logical errors, error bars about p_L/10. The often-quoted 0.8% is not a crossing of curves for several sizes: it is a pseudo-threshold obtained separately for each code by solving p_L(p) = kp (the whole block’s per-round failure rate equals the approximate failure rate of k bare qubits); Table 1 of v1 gives values between 0.007 and 0.008, v2 gives 0.0048 to 0.0069. The full five qualifiers are in “BB Codes · Decoders”, §3.3 and are not repeated here.

三个数来自三种不同的噪声模型，不能互相比较：码容量的 9.9% 与电路级的 0.7%–0.8% 相差一个数量级以上，差距主要来自噪声模型，而不是译码器。

The three numbers come from three different noise models and cannot be compared with each other: code-capacity 9.9% and circuit-level 0.7–0.8% differ by more than an order of magnitude, mostly because of the noise model, not the decoder.

测量会错时，单看某一轮的读数没有意义：一个读错的检查会在那一轮亮起、下一轮又「恢复」。所以比较的是相邻两轮的读数：探测器detector：若干次测量结果的一个奇偶组合，没有任何故障时它的值确定（通常是 0）。常见的是「同一条检查相邻两轮读数之差」。它为 1 就说它亮了。是若干次测量结果的一个奇偶组合，没有故障时它的值确定为 0，最常见的就是「同一条检查这一轮与上一轮读数之差」（《译码器 · 高中数学版》5.1 节讲过它在表面码上的样子）。然后把每一种可能的单个故障列出来，记下它会让哪些探测器翻转、会不会翻转我们关心的逻辑读数。这张表就是探测器错误模型detector error model, DEM：一张表，每一列是一种独立发生的故障机制，带一个概率，记录它翻转哪些探测器（症状）和哪些逻辑观测量。译码就是根据亮的探测器推断逻辑观测量是否被翻转。（DEM）。常用的纠错电路模拟软件 StimGidney（2021，arXiv:2103.02202）写的开源软件，能快速模拟纠错电路（反复测量检查的量子电路）并抽样出测量记录，还定义了 DEM 的文件格式。（Gidney 2021）的文档这样定义它：「A detector error model is a list of independent error mechanisms. Each error mechanism has a probability, symptoms (the detectors that the error flips), and frame changes (the logical observables that the error flips)」。

When measurements can fail, a single round’s readings mean little: a misread check lights up in that round and “recovers” in the next. So adjacent rounds are compared: a detectorA parity of several measurement outcomes whose value is fixed (usually 0) when nothing fails. The common one is “the change of one check between two consecutive rounds”. It is lit when it equals 1. is a parity of several measurement outcomes whose value is 0 when nothing fails, most often “this round’s reading of a check minus the previous round’s” (“Decoders · High-School Edition”, §5.1, shows it on the surface code). Then list every possible single fault and record which detectors it flips and whether it flips the logical readout we care about. That table is the detector error modelDEM: a table whose columns are independent fault mechanisms, each with a probability, recording which detectors (symptoms) and which logical observables it flips. Decoding means inferring from the lit detectors whether the logical observable was flipped. (DEM). The documentation of StimOpen-source software by Gidney (2021, arXiv:2103.02202) that quickly simulates error-correction circuits (quantum circuits that measure checks over and over) and samples their measurement records; it also defines the DEM file format., a widely used simulator of error-correction circuits (Gidney 2021), defines it: “A detector error model is a list of independent error mechanisms. Each error mechanism has a probability, symptoms (the detectors that the error flips), and frame changes (the logical observables that the error flips)”.

最小的例子：三比特重复码（只防比特翻转），两条检查 A = Z₀Z₁、B = Z₁Z₂，测两轮，最后把三个数据比特直接读出来。探测器六个：A1、B1 是第 1 轮的读数（初始奇偶已知为 0）；A2、B2 是第 2 轮与第 1 轮之差；A3、B3 是由最后读出的数据算出的奇偶与第 2 轮之差。逻辑观测量 L 是比特 0 的最后读数。故障机制：三个时刻（第 1 轮前、两轮之间、读出前）三个比特各可能翻转，共 9 种；两轮各两次测量各可能读错，共 4 种；再手工加一种关联故障 MAB1：第 1 轮的两个读数同时读错（例如两个辅助比特的读出互相串扰）。图 7.1 画出前两类故障各点亮哪些探测器。

The smallest example: the three-bit repetition code (protecting against bit flips only), checks A = Z₀Z₁ and B = Z₁Z₂, measured for two rounds, then the three data qubits are read out directly. Six detectors: A1, B1 are the round-1 readings (the initial parities are known to be 0); A2, B2 are round 2 minus round 1; A3, B3 are the parities computed from the final data readout minus round 2. The logical observable L is the final reading of qubit 0. Fault mechanisms: at three times (before round 1, between the rounds, before readout) each of the three qubits may flip, 9 in all; each of the two readings in each of the two rounds may be wrong, 4 in all; and one correlated fault added by hand, MAB1: both round-1 readings wrong at once (for instance through crosstalk between the two ancilla readouts). Fig. 7.1 shows which detectors the first two kinds light.

把 14 列排成矩阵，就是下面实验台里的表：行 = 6 个探测器，列 = 14 种机制，每列上方是它的概率（数据翻转与读错各 0.05，关联读错 0.02，都是为教学取的数），最下面一行 L 记录每种机制是否翻转逻辑观测量。除 MAB1 外每列至多两个 1：这个小码的普通故障都是「边」。MAB1 有四个 1，是一条超边（0.2 节）。匹配译码要求每列至多两个 1，所以只能把它拆成两条边 MA1 + MB1（Stim 的文件格式允许给一个机制附上「建议的分解」，把它写成几个更简单的机制之和）。拆开后，MAB1 的 0.02 并进这两条边，当作各自独立发生：每条边的概率变成「恰好一个来源发生」的 0.05 × (1 − 0.02) + 0.02 × (1 − 0.05) = 0.068。代价是模型再也表达不了「两个读错一起来」：它给「MA1 与 MB1 同时发生」的概率是 0.068 × 0.068 ≈ 0.0046，而真实模型光 MAB1 一项就有 0.02。BP-OSD 不需要拆：它把这一列原样放进矩阵，先验 L₀ = ln(0.98/0.02)。

Arranging the 14 columns as a matrix gives the table in the bench below: rows = 6 detectors, columns = 14 mechanisms, each column headed by its probability (data flips and misreadings 0.05 each, the correlated misreading 0.02, all chosen for teaching), and the bottom row L recording whether each mechanism flips the logical observable. Apart from MAB1 every column has at most two ones: the ordinary faults of this small code are “edges”. MAB1 has four ones, a hyperedge (§0.2). Matching needs at most two ones per column, so it would have to split MAB1 into the two edges MA1 + MB1 (Stim’s file format lets a mechanism carry a “suggested decomposition” into simpler mechanisms). After the split, MAB1’s 0.02 is merged into those two edges as if it struck each of them independently: each edge’s probability becomes that of “exactly one source fires”, 0.05 × (1 − 0.02) + 0.02 × (1 − 0.05) = 0.068. The price is that the model can no longer say that the two misreads come together: it gives “MA1 and MB1 both happen” probability 0.068 × 0.068 ≈ 0.0046, while the true model has 0.02 from MAB1 alone. BP-OSD needs no split: the column goes into the matrix as it is, with prior L₀ = ln(0.98/0.02).

译码问题的形状与第 0 章完全相同：矩阵 D（探测器 × 机制）代替 H，亮的探测器代替症状，未知数是「哪些机制发生了」，每个未知数的先验来自它那一列的概率。BP 在 D 的 Tanner 图上传消息，卡住时 OSD 沿排序解 D c = s。不同的只有最后一步：译码器要交出的不是一个修复，而是一个比特，「逻辑观测量翻没翻」，预测值是 L 行与解释 c 的点积（模 2）。所以这里的「类」就是 L 的值：两个解释只要预测同一个 L，效果就相同，哪怕它们本身差别很大。Bravyi 等把 BB 码的电路做成这样一张矩阵，称为「linearized noise model」，他们写道它「ignores possible cancellations between errors generated by two or more faulty operations」（两个故障互相抵消的情形被忽略，这类情形的概率是 O(p²)），并按 CSS 结构把 X、Z 分开，得到两张矩阵 D_X、D_Z：对 [[144,12,12]] 码测 12 轮，它们分别有 8857 列和 8785 列，每列至多 6 个 1、每行至多 35 个 1。

The decoding problem has exactly the shape of Chapter 0: the matrix D (detectors × mechanisms) replaces H, the lit detectors replace the syndrome, the unknowns are “which mechanisms happened”, and each unknown’s prior comes from its column’s probability. BP passes messages on D’s Tanner graph, and when it stalls OSD solves D c = s along the ranking. Only the last step differs: the decoder must return not a repair but one bit, “was the logical observable flipped”, predicted as the dot product (mod 2) of row L with the explanation c. So the “class” here is the value of L: two explanations that predict the same L have the same effect, however different they are. Bravyi et al. turn the BB-code circuits into such a matrix, calling it a “linearized noise model”, which “ignores possible cancellations between errors generated by two or more faulty operations” (cases where two faults cancel are ignored; they occur with probability O(p²)); following the CSS structure they split X and Z into two matrices D_X, D_Z: for the [[144,12,12]] code with 12 rounds these have 8857 and 8785 columns, with at most 6 ones per column and at most 35 per row.

实验台默认只发生了 MAB1，亮 A1、B1、A2、B2。穷举这个模型的 2¹⁴ 种组合：最可能的解释就是 MAB1 本身，在与读数相符的组合中占 0.766；逻辑观测量被翻转的后验概率 0.013。按「用 BP-OSD 译码」：BP 第 1 轮就满足了全部探测器，但它的逐位判决是 {X1@1, X1@2, MA1, MB1, MAB1}：三种解释各自点亮同样四个探测器，三个加起来（模 2）仍是那四个，所以满足 D c = s。这个解释很重，不是最可能的那个（与 3.1 节的 Hamming 码是同一种现象），但它预测 L = 0，与事实一致，所以这次译码成功。把模型切成「把 MAB1 拆开并进 MA1、MB1 两条边」：BP 第 5 轮收敛到 {MA1, MB1}，同样预测 L = 0，这也是拆开后的模型里最可能的解释（占 0.598）；可这个模型认为同样的读数下 L 被翻转的概率是 0.040，约为完整模型（0.013）的三倍。拆开超边丢掉的，就是这类概率上的准确性。

By default only MAB1 has happened on the bench, lighting A1, B1, A2, B2. Enumerating all 2¹⁴ fault sets of this model: the most likely explanation is MAB1 itself, with a share of 0.766 among the sets matching the readings; the posterior probability that the observable was flipped is 0.013. Press “Decode with BP-OSD”: BP satisfies every detector in iteration 1, but its bit-by-bit decision is {X1@1, X1@2, MA1, MB1, MAB1}: three explanations each light the same four detectors, and all three together (mod 2) still light those four, so D c = s holds. This explanation is heavy and not the most likely one (the same phenomenon as the Hamming code of §3.1), but it predicts L = 0, which is the truth, so this decoding succeeds. Switch the model to “MAB1 split and merged into the MA1 and MB1 edges”: BP converges at iteration 5 to {MA1, MB1}, also predicting L = 0, and this is also the split model’s most likely explanation (share 0.598); but this model puts the probability that L was flipped, given the same readings, at 0.040, about three times the full model’s 0.013. Accuracy of probabilities like this is what splitting the hyperedge gives up.

一次长时间的存储实验要测成千上万轮，整段历史一起译码既不可能（要等实验结束）也太大。常见的办法是滑动窗口译码sliding-window decoding：每次只译码最近 W 轮组成的一段（窗口），只把最早 F 轮的修正定下来（提交），然后窗口向后滑 F 轮。F < W 时相邻窗口重叠。：每次取最近 W 轮组成一个窗口，只把最早的 F 轮的结论定下来（提交），剩下的留给下一个窗口，然后窗口向后滑 F 轮（图 7.2）。Huang 与 Puri（2311.03307）说明这个做法最早由 Dennis 等为表面码提出，叫 overlapping recovery；他们在超图积码与提升积码上、现象学噪声（数据比特与测量会错，但测量电路本身不出错）下用 BP-OSD 做窗口译码，发现重叠窗口（F < W）的逻辑寿命显著长于不重叠的窗口（F = W）：例如在 [[625,25,8]] 超图积码上、p = 0.7% 时，W = F = 16 的寿命比 W = 3、F = 1 小近一个数量级。他们的摘要还拿滑动窗口与单发译码single-shot decoding：每测一轮，只用这一轮的读数译码一次并立刻修正，相当于 W = F = 1 的窗口。（每测一轮只用这一轮的读数译码一次，即 W = F = 1）比较，说窗口带来的改进「may not cost a larger decoding complexity」。正文的依据是：四份 [[625,25,8]] 码用 W = 4、F = 1 的窗口译码，每份码的每个窗口要处理的症状位数 W(n − k)/2 = 1200，与 [[2500,100]] 码单发译码一样多，逻辑寿命却更长。

A long memory experiment measures thousands of rounds, and decoding the whole history at once is both impossible (it would wait for the end) and too large. The usual method is sliding-window decodingDecode only the most recent W rounds (the window), commit the corrections for the earliest F rounds, then slide the window forward by F rounds. With F < W consecutive windows overlap.: take the most recent W rounds as a window, commit the conclusions for only its earliest F rounds, leave the rest to the next window, and slide forward by F rounds (Fig. 7.2). Huang and Puri (2311.03307) note that the method was first proposed by Dennis et al. for the surface code under the name overlapping recovery; using BP-OSD for window decoding of hypergraph-product and lifted-product codes under phenomenological noise (data qubits and measurements fail, but the measurement circuit itself does not), they find that overlapping windows (F < W) give a markedly longer logical lifetime than non-overlapping ones (F = W): for example, on the [[625,25,8]] hypergraph-product code at p = 0.7%, W = F = 16 gives a lifetime nearly ten times shorter than W = 3, F = 1. Their abstract also compares sliding windows with single-shot decodingDecoding once per measurement round, using only that round’s readings, and correcting at once: a window with W = F = 1. (decoding once per round from that round’s readings alone, i.e. W = F = 1) and says the window’s improvement “may not cost a larger decoding complexity”. The body backs this up: four copies of the [[625,25,8]] code decoded with W = 4, F = 1 process W(n − k)/2 = 1200 syndrome bits per copy and window, as many as single-shot decoding of the [[2500,100]] code, and still live longer.

延迟重要，是因为症状是按固定节奏源源不断产生的。译码一个窗口的时间若比产生它的时间长，没译完的数据就越积越多；需要根据译码结果决定下一步操作（比如逻辑门）时，处理器只能干等。5.5 节说过 BP 天然并行、OSD 的消元是全局的，所以 BP-OSD 的延迟主要花在 OSD 上。作为一个具体的量级，Wolanski 与 Barber 的摘要报告，他们的 ambiguity clustering 实现在 M2 CPU 上译码 gross 码每轮症状提取用 135 µs，并称这「already fast enough to keep up with neutral atom and trapped ion systems」（已经快到能跟上中性原子与离子阱系统）。

Latency matters because syndromes arrive continuously at a fixed pace. If decoding a window takes longer than producing it, undecoded data piles up; and when the next operation (a logical gate, say) depends on the decoding result, the processor can only wait. §5.5 noted that BP is naturally parallel while OSD’s elimination is global, so BP-OSD’s latency is spent mostly in OSD. For a concrete scale, Wolanski and Barber’s abstract reports that their ambiguity-clustering implementation decodes the gross code in 135 µs per round of syndrome extraction on an M2 CPU, which they call “already fast enough to keep up with neutral atom and trapped ion systems”.

下面几种方法都保留 BP，改的是 BP 之后（或 BP 本身）的做法。每条只写摘要里说的事；性能数字都只在摘要所说的码、噪声与比较对象下成立，本页没有复现它们。除 belief matching 外，它们都没有登记在 QEC-Bank 的译码器表里。

The methods below all keep BP and change what happens after it (or inside it). Each entry states only what the abstract says; performance numbers hold only for the codes, noise and comparisons the abstract names, and this page did not reproduce them. Except for belief matching, none is registered in the QEC-Bank decoder table.

• 局部统计译码（localized statistics decoding, LSD），Hillmann 等，arXiv:2406.18655（未登记于 QEC-Bank）：不在整张矩阵上消元，而用一种并行的「on-the-fly elimination」找出、验证并求解译码图上的局部区域；摘要称它与最先进的译码器性能相当，同时降低了低于阈值区间的运行时复杂度。ldpc 软件包里有它的实现（BpLsdDecoder）。
• 模糊聚类（ambiguity clustering, AC），Wolanski 与 Barber，arXiv:2406.14527（未登记于 QEC-Bank）：BP 之后把测量数据分成可以各自独立译码的簇；摘要报告在 BB 码、0.3% 电路级去极化噪声下比 BP-OSD 快至多 27 倍，准确度相当。
• Relay-BP，Müller 等，arXiv:2506.01779（未登记于 QEC-Bank）：不用 OSD，只改进 BP 本身：给每个比特加上「无序的记忆强度」（3.3 节），并把多次这样的 BP 接力运行；摘要称它在 BB 码上明显优于 BP+OSD+CS-10，在表面码上与最小重量匹配相当，并且适合用 FPGA/ASIC两类专用硬件。FPGA（现场可编程门阵列）是可以反复重新接线的芯片；ASIC（专用集成电路）是为一个任务专门制造的芯片。它们都能做到比普通 CPU 低得多、也更稳定的延迟，这正是实时译码需要的。（可重新接线的芯片 / 专门制造的芯片，延迟都比 CPU 低）实现。
• Belief matching，Higgott 等，arXiv:2203.04948（QEC-Bank 登记键 higgott2023beliefmatching）：用 BP 估计关联故障，再给匹配图重新赋权，最后仍用最小重量匹配；适用于每个故障最多点亮两个探测器（或可分解成这样）的码，比如表面码。摘要报告在他们的电路噪声模型下表面码阈值 0.94%，标准匹配是 0.82%。

• Localized statistics decoding (LSD), Hillmann et al., arXiv:2406.18655 (not registered in the QEC-Bank): instead of eliminating over the whole matrix, a parallel “on-the-fly elimination” identifies, validates and solves local regions of the decoding graph; the abstract says it matches the performance of state-of-the-art decoders while reducing the runtime complexity in the sub-threshold regime. The ldpc package implements it (BpLsdDecoder).
• Ambiguity clustering (AC), Wolanski and Barber, arXiv:2406.14527 (not registered in the QEC-Bank): after BP, the measurement data are divided into clusters that can be decoded independently; the abstract reports up to 27 times faster than BP-OSD with matched accuracy on BB codes under 0.3% circuit-level depolarizing noise.
• Relay-BP, Müller et al., arXiv:2506.01779 (not registered in the QEC-Bank): no OSD, only a better BP: each bit gets a “disordered memory strength” (§3.3) and several such BP runs are chained in a relay; the abstract says it significantly outperforms BP+OSD+CS-10 on BB codes, is comparable to minimum-weight matching on surface codes, and suits implementation on FPGA/ASICTwo kinds of dedicated hardware. An FPGA (field-programmable gate array) is a chip whose wiring can be reconfigured; an ASIC (application-specific integrated circuit) is a chip manufactured for one task. Both reach much lower and steadier latency than an ordinary CPU, which is what real-time decoding needs. (a rewirable chip / a purpose-built chip, both with lower latency than a CPU).
• Belief matching, Higgott et al., arXiv:2203.04948 (QEC-Bank key higgott2023beliefmatching): BP estimates correlated faults and reweights a matching graph, and minimum-weight matching still makes the final choice; it suits codes where each fault lights at most two detectors (or can be decomposed that way), such as the surface code. The abstract reports a surface-code threshold of 0.94% under their circuit noise model, against 0.82% for standard matching.

复盘整条推理链：译码 = 在满足 H c = s 的修复里选一个，使残留与每个 Z̄ 重叠偶数次；qLDPC 码的一个错误点亮三条以上检查，配对用不上（第 0 章）→ 「最可能的图样」与「每个比特最可能的取值」是两个问题，LLR 把贝叶斯的乘法变成加法（第 1 章）→ BP 的两条规则：检查用偏差之积，比特把消息相加；树上精确（第 2 章）→ 圈让证据被数两次，从过度自信到收敛到错误答案；min-sum、阻尼、串行调度（第 3 章）→ 量子码：CSS 分开译码，退化让逐比特判决交不出修复（第 4 章）→ OSD 按 BP 的排序做高斯消元，保证 H c = s，在等价修复里选边；按编号做同样的消元就差得多（第 5 章）→ ldpc 的参数、实验台与文献数字（第 6 章）→ 同一套方法用在探测器错误模型上（第 7 章）。

The chain of reasoning in one pass: decoding = choosing, among repairs with H c = s, one whose residual overlaps every Z̄ an even number of times; in qLDPC codes one error lights three or more checks and pairing is unavailable (Ch. 0) → “the most likely pattern” and “the most likely value of each bit” are different questions, and the LLR turns Bayes’ products into sums (Ch. 1) → BP’s two rules: checks multiply biases, bits add messages; exact on trees (Ch. 2) → cycles make evidence count twice, from overconfidence to converging on a wrong answer; min-sum, damping, the serial schedule (Ch. 3) → quantum codes: separate CSS decoding, and degeneracy that keeps bit-by-bit decisions from producing a repair (Ch. 4) → OSD does Gaussian elimination in BP’s order, guarantees H c = s and picks a side among equivalent repairs; the same elimination in index order does much worse (Ch. 5) → ldpc’s parameters, the bench and literature numbers (Ch. 6) → the same method on detector error models (Ch. 7).