一种针对QKD系统的改进型LDPC译码算法

□ 张薇薇

一、引言

量子密钥与经典密钥体系的根本不同在于，其采用微观粒子的不同量子态作为密钥的载体，由量子力学的基本原理保证了该过程的不可窃听、不可破译性，从而提供了一种更为安全的密钥体系。但在量子密钥分发(Quantum Key Distribution，QKD)过程中，由于系统自身暗噪声和外界干扰的存在，使进行QKD的双方产生的量子密钥存在一定的误码。所以一般在QKD系统中会增加一个纠错过程来消除密钥中存在的误码。QKD系统的纠错过程一般基于经典通信领域中的编译码算法，加以流程上的少量变通。

在QKD系统的纠错过程中，进行QKD的双方之一，暂定为Alice，以一定的算法作用于纠错之前的密钥，从而产生校验信息，并将校验信息通过经典通信方式发送给进行QKD的另外一方，暂定为Bob。Bob可以依据接收到的校验信息来判定Alice方的密钥位是逻辑“1”还是逻辑“0”，或者是一个概率，用来表示Alice方的密钥位是逻辑“1”或逻辑“0”的概率，再通过软判决方式判定Alice方的密钥位是逻辑“1”还是逻辑“0”。

本文将讨论的内容涉及编解纠错码领域，具体涉及一种适用于QKD系统的低密度奇偶校验码(Low Density Parity Check Code，LDPC)纠错算法。

二、LDPC算法介绍

在QKD领域常见的纠错算法有Cascade算法及其变种算法、Winnow算法，还有低密度奇偶校验码(Low Density Parity Check Code，LDPC)的算法。由于LDPC算法在性能上被证明优于Winnow算法，所需交互次数少于标准Cascade算法，所以LDPC算法已经成为当前该领域研究的热点。目前LDPC译码算法主要分为两类，即基于校验和统计迭代的比特翻转(Bit Flip，BF)算法和基于概率的置信传播(Belief Propagation，BP)迭代译码算法。

(一)基于校验和统计迭代的比特翻转算法。B方收到校验序列 P1×(n-k)后与自身持有的密钥 TB1×k按照［TB1×k，P1×(n-k)］的形式组合成码字 S1×n，即 S1×n={s0，s1，s2，…sn-1}=［T1B×k，P1×(n-k)］。然后按照下列公式计算校验伴随序列 B1×(n-k)={b0，b1，b2，…，bn-k-1}。

如果伴随序列 B1×(n-k)为全0序列，则说明码字 S1×n没有错误，否则按照下式可计算出校验统计数值序列F1×n。

找出校验统计数值列F1×n中值最大的元素fj的位置j，然后翻转码字S1×n中对应位置的元素sj，到一次修正后的码字序列S'1×n，将修正后的码字序列 S'1×n代替原码字序列S1×n，按照以上步骤处理，直到伴随序列 B1×(n-k)为全0时截止，则经过多次修正之后的码字序列S'1×n即为译码结果，截取其前k比特即为纠错之后的密钥数据T1B×k，且此时T1B×k=TA1×k。

该算法简单易于硬件实现，但性能较差，所以不常用。

(二)基于概率的置信传播算法。基于概率的置信传播算法可以基于不同的量度而衍生出不同的置信传播算法，例如概率差BP译码、概率比BP译码或对数似然比BP译码。但这些算法操作步骤以及本质原理是等价的，这里仅以对数似然比BP译码算法为例介绍。

B方收到校验序列P1×(n-k)后与自身持有的密钥T1B×k按照［T1B×k，P1×(n-k)］的形式组合成码字 S1×n，即 S1×n={s0，s1，s2，…sn-1}=［T1B×k，P1×(n-k)］。码字 S1×n中的每一个元素都被称作信息节点。

计算校验伴随序列的公式 B1×(n-k)=S1×n·［Hn-k)×n］T由(n-k)个线性方程组成，每个方程对应一个校验节点。

那么对数似然比量度下的BP译码算法迭代步骤如下:

1.初始化信息节点。如果初始密钥错误率为e，那么用fi初始化信息节点，fi的计算公式如下:

2.更新校验节点消息。按照下列计算公式逐个更新所有校验节点的值。

上式中，Rij表示第i个校验节点传递给第j个信息节点的置信消息，l表示迭代次数，Rlij表示在第l次迭代中第i个校验节点传递给第j个信息节点的置信消息。Qik表示第i个信息节点传递给第j个校验节点的置信消息，Qlik表示在第l次迭代中第i个信息节点传递给第j个校验节点的置信消息，Q0ik=fi。N(i)表示与校验节点i相连的所有信息节点所构成的集合，N(i)j表示N(i)中除去信息节点j后剩下的集合。

3.更新信息节点消息。按照下列计算公式逐个更新所有信息节点的值。

上式中，M(j)表示与信息节点j相连的所有校验节点所构成的集合，M(j)i表示M(j)中除去校验节点i剩下的集合。

4.判决。对所有的信息节点按照下式计算Qlj。

判决规则为

5.校验。按照下式计算校验伴随序列B1×(n-k)。

B1×(n-k)=S1×n·［H(n-k)×n］T

如果B1×(n-k)为全零序列，则说明译码完全正确，如果不全为0则说明码字S1×n仍有错误，此时如果还没有超过设定的迭代次数上限，则回到第2步进行下一轮迭代，否则认为译码失败。

在译码成功后截取S1×n的前k比特即为纠错之后的密钥数据 TB1×k，且此时 TB1×k=TA1×k。

该算法硬件实现非常不易，但性能非常不错。

图1 一个Tanner图实例

现有技术方案会以Tanner图来描述一个LDPC码，图1是一个具体的Tanner图，后面的介绍也基于此图。Tanner图有节点和边组成，上面圆形节点代表校验节点，下面方形节点代表变量节点。正如图1中所示，某校验节点通过边①、②、③和④与另外4个变量节点相连。

足迹深度表征区域内人类活动对自然资源存量占用程度，足迹深度越大表示区域自然资本存量加速减少，生态承载力下降。

当前QKD系统中LDPC纠错中BP译码算法，依旧采用了经典通信中类似做法，并未利用QKD系统的特点，导致译码迭代次数偏高，译码计算量大。

三、一种改进型LDPC译码算法

(一)算法执行过程。QKD系统出于安全考虑允许在纠错过程中舍弃部分密钥，通常这种舍弃过程发生在隐私放大处理步骤，如果在纠错过程中有密钥被舍弃，则通过修正隐私放大因子即可达到等价效果。本提案正是利用QKD系统的这一特点，在LDPC译码过程中抛弃可疑密钥，以减少译码迭代次数，降低译码计算量。

首先为本方案取一个名称——圈地译码(Enclosure Decoding，以下简称ED)算法，ED算法首先按照经典BP算法迭代处理，然后按照一定规则将一部分数据圈起来，正如圈地一样，然后再抛弃圈内的数据，画圈的规则是让尽可能多的错误比特被圈进来。这样就无需更多的计算步骤去纠正这些错误比特，从而降低译码算法的迭代次数。当然画圈的时候，不可随意扩大画圈范围，因为这样会劣化纠错效率。

该算法的核心思想是确定发生误码的大概范围比精确确定误码的位置所需的计算复杂度低，然后再抛弃这些被认定为可能发生误码的范围内的所有数据，只需保证留下来的数据是绝对正确即可。该算法具体实施步骤如下:

假设译码方原始码字为C，伴随序列S，步骤如下:

当Si=0时:

当Si=1时:

2.变量节点消息处理。对所有的变量节点i和相邻的校验节点j∈R(i)，计算第i个变量节点传向第j个校验节点的消息:

式中:Kij是校正因子。

3．判决译码。对所有变量节点计算硬判决信息，若qli(0)＜qli(1)，则=1，否则则=0。

这里需要额外说明的是抛弃规则和额外的CRC校验过程，如下:

(1)抛弃规则。对每个变量节点，计算其可信度:

设置可信度阈值为ɑ，如果pli＜0，则把该变量节点列入抛弃对象，可信度低的变量节点优先抛弃，每次迭代结束时需要统计被列为抛弃对象的变量节点数，如果这个数低于校验节点数，则停止迭代，抛弃这些变量节点。

图2 迭代次数与误码率关系

(2)额外的步骤。迭代结束时译码方可以将被抛弃的变量节点的位置发送编码方，做同步抛弃。此外由于变量节点抛弃之后不能继续以校验方程是否成立来判断是否译码成功，因此译码方可以将抛弃之后剩余的数据计算一次CRC，将CRC发送给编码方。编码方通过CRC确认验证译码方是否成功。

(二)算法性能。采用本提案的译码算法，对比经典BP译码，我们通过软件模拟得到在不牺牲纠错效率的情况下，ED译码算法可比经典BP译码算法节省约1/3的迭代次数。图2是详细对比曲线图。

四、结语

本文分析了现有LDPC译码算法，提出了一种改进型的LDPC译码算法，该算法利用QKD系统纠错过程可抛弃密钥的特点，使用经典LDPC译码算法，计算出各变量节点可信度，然后对各变量节点可信度做排序，抛弃可信度低的变量节点，以减少迭代次数。通过实际仿真结果可知该算法比经典BP译码算法节省约1/3的迭代次数。

［1］Brassard，Salvail.Secret key reconciliation by public discussion［J］.Lecture Notes in Computer Science，1994，765:410～423

［2］T.Sugimoto，K.Yamazaki.A study on secret key reconciliation protocol“cascade”［J］.IEICE Trans.Fundamentals，2000，10:1987～1991