基于LDPC硬判决算法的高效数据协调方法

屠亮亮，徐荣青

(南京邮电大学 科学与工程学院，江苏 南京 210003)



基于LDPC硬判决算法的高效数据协调方法

屠亮亮，徐荣青

(南京邮电大学 科学与工程学院，江苏 南京 210003)

摘要：数据协调是量子密钥分发中必不可少的一个环节，其主要目的是纠正量子通信筛选后信息的错误图案，使合法通信双方获得一致的密钥信息。为了提高协调算法的纠错效率，选择了一种基于硬判决迭代译码算法的LDPC码对QKD中的密钥序列进行数据协调，相较于传统的协调方法如级联码、卷积码、Winnow方案，采用低复杂度的LDPC比特翻转算法的正向协调方案具有较强的时效性，尤其是在0.4～0.6的码率时协调效率达到最高。

关键词：量子密钥分发；数据协调；LDPC

引用格式：屠亮亮，徐荣青. 基于LDPC硬判决算法的高效数据协调方法[J].微型机与应用，2016,35(12)：67-69.

0引言

量子密钥分发(QKD)[1]是近几年来信息安全领域中发展极为迅速的一个课题，有别于采用数学算法保护密钥安全的传统密钥体系，量子密钥分发是通过量子力学的物理性质来达到理论上的密钥绝对安全。

本文采用传统称谓，即定收发双方分别为Alice和Bob。QKD是由合法通信双方通过量子信道传送量子态信号，并通过经典信道实现密钥后处理，最终提取出二进制密钥序列以实现密钥通信的过程。可以将量子密钥分发流程归纳为4个步骤，分别是量子传输过程、信道参数估计、数据协调、密钥放大。数据协调的作用是纠正双方对应位置的不一致信息，使用的是经典公开信道，适用于所有经典信道的信息理论。

本文的重点聚焦在协议的数据协调部分，即假定在Alice和Bob端已经完成了4步流程的前两步，各自建立了等长且具有一定相关性的密钥，密钥序列的数量和顺序大致相同且具有一定的差错率。在QKD中，可以把这个差错率叫做量子误码率(QBER)，理论上只要该值不大于11%，就认为Alice和Bob的通信没有被窃听，即可以实现理论上的安全传输。

常见的量子密钥分发技术可以分为离散变量量子密钥分发(DVQKD)[2]和连续变量量子密钥分发(CVQKD)两种，其中前者在理论上可以实现更远的传输距离，不过，DVQKD也存在着单光子信源难以制备、检测设备装置复杂的缺点。在单光子信源研究领域，超导材料作为光敏感器件的单光子探测技术的发现,使得量子效率、暗计数率和计数率大幅度提高。另外，潘建伟等人首次在类石墨烯材料中发现一种非经典单光子发射器，为光量子器件发展开辟了一个新的重要领域。这些单光子制备工艺的发展，也在推动DVQKD进一步走向实际应用。

1数据协调方案

CVQKD系统一般都是将数据协调和密钥放大结合在一起实现，事实上对于DVQKD系统，单独考虑数据协调更有利于观测不同协调方法的性能。本文抛开密钥放大对纠错过程的影响，侧重于各自协调方案的研究。

由于数据协调过程使用的是经典信道，因此常见的经典信道编码方法[3]都可以应用于数据协调过程。综合以往文献，数据协调的性能主要由协调效率和泄露信息百分比来衡量。目前广泛使用的级联码协调方法难以避免合法通信双方的交互延迟。而Winnow协调方法借助汉明码纠错技术对此有所改进，不过也是以牺牲纠错率和泄露更多密钥信息为代价。本文提出的LDPC[4]协调技术只需要Alice和Bob进行一次信息交互，并且可以通过校验矩阵参数有效地控制泄露信息的数量。另一方面，LDPC作为最接近香农限的信道编码技术，采用硬判决算法可以显著地降低纠错算法的时间复杂度，有效提高系统的时效性。

数据协调方案的选取应该满足3个基本要求[5]：误码率应足够低，尽量不舍弃初始信息，尽量保证时效性。假设Alice和Bob在经过了量子传输和信道参数估计之后分别获得了初始密钥序列X和Y，其中X、Y同为二进制信息序列，序列X为标准密钥，序列Y与序列X的错误图案为E，即Y=X+E；Bob则通过接收到的序列Y和理想的无差错经典信道与X协商纠错，并得到X的估计，如图1所示。双方的信息协商有可能会泄露原始密钥的相关信息，因此在协商之后还应该按适当比例删除序列X与Y的部分信息比特，保证系统的安全性。

图1　公开经典信道下的数据协调

1.1Slepian-Wolf编码定理

LDPC是一种高效的信道编码技术，其本质是给码字信息增加监督位来提高信息传输的抗信道噪声能力。数据协调过程可以看作是一对相关信源的信源压缩编码，即一个双信源的分布式信源编码过程(DSC)，该方法在满足SW(Slepian-Wolf)定理所定义的熵条件下，将信道编码技术运用于信源编码，实现信源的无失真编码。SW定理有两个要求：一是需要将一个信源作为主信源，另一个信源作为边信息，即完全边信息问题；二是两个信源应有一定的相关性。

1.2校验位和校验子检测方法

传统的LDPC编码纠错方法是在发送端借助LDPC生成矩阵G进行编码，并在接收端使用对应的校验矩阵H和迭代译码算法实现相应的译码，最终实现纠错检错，使用这种方法的数据协调方法也叫校验位纠错方法。该方法的弊端是根据LDPC的监督矩阵H获得生成矩阵G的方法比较复杂，并且需要对全码长序列进行信道译码，因此还需要更长的译码时间。

2003年，SARTIPI等人提出了一种结合LDPC码的校验子纠错方法，之后，PRADHAN等人将校验子纠错方法运用到了分布式信源编码，使用这种方法的优点是：(1)有效地压缩信源，减少协商泄露的信息长度；(2)直接使用LDPC的稀疏矩阵H进行纠错，避免了计算LDPC的生成矩阵，极大地提高了系统的协调效率；(3)迭代译码的时间复杂度因为信源的压缩而线性减少。

本文采用基于校验子检测的完全边信息协商方法，简要的信息流程框图如图2所示。

图2　基于校验子检测的完全边信息协调方法

1.3LDPC比特翻转算法

现今LDPC的译码器大多采用概率域的和积译码算法，借助无短环和大码长特性能够达到接近香农限的纠错能力。比特翻转算法是一种硬判决算法，特点是算法时间复杂度很低，仅适用于BSC信道，可以看作是置信传播算法的简化形式。首先将待译码序列进行硬判决，将所得0/1序列代入伴随式的校验方程，找到使校验方程不成立数目最多的变量节点，将该节点所对应的比特位翻转，通过如此不停地迭代，直到满足系统设定的检验方程或达到最大的迭代次数。

由于该算法的时间复杂度很低，非常适用于对协调效率要求较高的系统。该算法只进行了比特翻转等几种常见的逻辑运算，硬件实现非常容易，在对性能要求较低的场合具有重要的应用前景。

2使用比特翻转译码方法的数据协调过程

本文采用一种基于LDPC比特翻转译码方法和校验子验证的正向协调方案，满足SW编码的完全边信息条件。该方案的实现方法主要可以分为4个模块：密钥生成、编码、校验子计算、比较译码。在编码端，需要对主信息序列X进行两步处理，首先是对序列X进行DSC压缩，即利用LDPC校验矩阵对X进行编码，此处压缩率应为n-m/n；第二步是对校验子S进行LDPC信道编码，将该信道码序列M传送给B。在解码端，要先对M进行信道译码，滤除BSC信道噪声的影响，再对译码后的序列结合边信息序列Y进行最后的联合译码。

需要注意的是，对于校验子S的信道编码和译码，考虑到BSC信道的不稳定性，本文并没有使用数据协调所用的硬判决译码算法，而是使用相对成熟的LLR-BP算法。将其独立出来考虑是为了方便采用其他的信道编码技术来适应不同的协调信道。如果所用的经典信道是AWGN信道，其译码步骤仍然是初始化、变量节点信息迭代、校验节点信息迭代、译码判决4个步骤，唯一的不同是需修改LLR-BP算法的初始化过程。此处设BSC信道的转移概率为p，则译码时概率似然比消息初始化为：

3数值仿真结果与分析

本次仿真选择码长为106的初始键值，原始密钥信息完全随机产生，并根据设定的量子误码率得到对应边信息。该迭代过程的最大迭代次数设置为100。纠错所选用的编码方法为基于PEG算法的准循环LDPC码，并用四六环检测程序排除短环的影响，确保该方法产生的LDPC校验矩阵的最短环长为8环且不含低码重码字，具有非常良好的纠错性能。

实验分别使用码长固定、码率为0.4、0.5、0.6的LDPC校验矩阵进行数据协调，结果如图3所示。由图可见，随着码率的增加，系统纠错效果显著增强，且在低QBER的情况下正向译码性能明显优于Winnow和卷积码方法。

图3　各协调方法的纠错性能

理论上的泄露信息比特数可以通过公式d=1-I(e)计算，其中e是量子误码率。本文所采用的LDPC协调方案所产生的泄露信息比特数与通过公开信道发送的校验子S的比特数相等，且在合法通信双发之间仅需一次交互。通过与已有的方法比较可知，LDPC的泄露信息比特数完全可控，可以针对不同的系统选择不同的码率，见图4。

图4　不同协调方法的泄露信息比特数

4结论

本文对基于LDPC码的QKD数据协调技术的应用进行了比较全面的分析与研究，提出了一种采用SW完全边信息编码方法的正向协调方案，避免了计算LDPC的生成矩阵G，采用硬判决算法降低时间复杂度，从根本上提高了译码速度，并着重分析了不同码率和编码方法对协商效果的影响。实验表明，码率在0.4～0.6的LDPC码的纠错效率最强，可以在低QBER环境下取得极佳的性能。

进一步的研究工作是针对不同的筛选后码字优化LDPC码校验矩阵的度分布，排除低码重码问题对于译码性能的影响。

参考文献

[1] 逯志欣，于丽，李康，等.基于逆向协调的连续变量量子密钥分发数据协调[J].中国科学(G辑),2009,39(11):1606-1612.

[2] 郭大波，刘纲，张宁，等.量子高斯密钥分发的逆向数据协调[J].量子光学学报,2013，19(3):219-226.

[3] 刘洋,章国安,何黄燕，等.基于高效纠错码的无线光通信系统性能分析[J].电子技术应用,2014,40(12):103-106.

[4] 宁平.IEEE 802.16e标准中LDPC编码的实现与仿真[J].电子技术应用,2014,40(9):101-104.

[5] 白增量，王旭阳，杜鹏燕，等.连续变量量子密钥分发的数据逆向协调[J].量子光学学报,2012,18(1):23-26.

中图分类号：TN911.22

文献标识码：A

DOI：10.19358/j.issn.1674- 7720.2016.12.021

(收稿日期：2016-01-19)

作者简介：

屠亮亮(1989-)，男，硕士研究生，主要研究方向：信道编码、量子通信数据后处理。

徐荣青(1966-)，男，博士，教授，主要研究方向：光电检测技术与光电信号处理。

Efficient reconciliation using LDPC hard decision for quantum key distribution

Tu Liangliang, Xu Rongqing

(School of Electronic Science and Engineering, Nanjing Univercity of Posts and Telecommunication, Nanjing 210003, China)

Abstract:Reconciliation is a significant procedure in quantum key distribution(QKD) system.It is employed to extract secure secret key from the sifted information by correcting error codes between two legal users.In this paper, we proposed an reconciliation protocol through employing a low density parity-check (LDPC) code based on hard decision decoding algorithm in QKD system.From numerical simulation while it yields low complexity comparable to the existing LDPC-based reconciliation protocols and the performance of our proposed scheme is superior to conventional Winnow and CASCADE protocols, especially at the rate of 0.4～0.6, the reconciliation efficiency reaches the maximum value.

Key words:quantum key distribution; reconciliation; LDPC