基于低密度奇偶校验码的数据协调技术

摘要：低密度奇偶校验码（LDPC）是一种（n，k）线性分组码当分组码码长较短时，利用常规的编码方法可以完成编码工作但随着分组码码长的增加，利用常规LDPC的编码方式编码，计算机的内存难以承担为了解决以上问题，提出两种有效的编译码方案首先，该数据协调方案不同于传统校验位译码，利用边信息和原始数据产生的校验子进行联合译码；其次，将校验矩阵以稀疏矩阵的形式存储，利用双向十字循环链表只记录1的位置的方式存储校验矩阵，这样可极大地节省内存空间；最后，通过C语言实现可提高编译码的有效性实验中选取码长105的分组长度，译码器误码率（BER）收敛于1.0dB，每一分组译码时间仅需4s，译码收敛后速率达到24.85kb/s，时效性较强

关键词：低密度奇偶校验码； 边信息； 校验子； 稀疏矩阵； 数据协调

中图分类号： TP309 文献标志码：A

0引言

量子密钥通信是量子通信领域中最接近实用的研究方向协调技术是量子密钥通信中必不可少的一个环节，它可判断窃听的存在，纠正量子通信中大量的误码，并通过密性放大实现密钥蒸馏在经典加密体系中，密钥分配一般分为两种方式：对称密钥体系（私钥密码系统）和非对称密钥体系（公钥密码体系）[1]其中数据协调是对量子信息传输过程造成的不一致进行纠正的一种协议，而密性放大（或密钥蒸馏）是通过去除在量子传输和协调过程中窃听者得到的信息，从而使Alice和Bob拥有相同的密钥的协议[2-3]

截止目前，量子密钥分发（Quantum Key Distribution，QKD）[4]已在实际应用方面获得大量进展，成果突出欧美、日本等地区都投入了大量人力、物力进行相关研究，国内中国科学院、山西大学量子光学与光量子器件重点实验室、中国科学技术大学等单位也致力于这方面的研究，并取得了一定的研究成果Namekata等[5]利用超低噪声正弦门控的雪崩光电二极管，采用单光子探测器，实现了100km的传输距离；当改用差分移相的探测方法后，传输距离可达160km连续变量量子密钥分发系统方面， Lodewyck等[6]实现了一个25km的全光纤连续变量QKD系统Leverrier等[7]提出了一种非高斯调制QKD协议，提高了在密钥协商阶段的效率，该协议还在密钥传输过程中加入了诱骗态，可以抵御任意的集体攻击，证明了它在线性量子信道中是绝对安全的Zhou等[8]、宋汉冲等[9]提出了连续变量量子确定性密钥分配协议，该协议的主要目的是经由公共信道移交一预先确定的密钥给接收者，其中密钥对发送者而言是确定的，在利用零差探测法的情况下协议的传输效率达到了100%Wang等[10]在2013年已完成一个30km全光纤分离调制连续变量QKD系统

QKD在实际应用方面成果突出，但系统中很少涉及具体的数据协调方案与协调速率，本文将从低密度奇偶校验码（Low Density Parity Check Code， LDPC）校验矩阵的合理构造和协调方案的改进两方面阐述协调速率提高的原因其中数据协调步骤为：利用Alice传递过来的边信息[11]根据校验矩阵计算出校验子（syndrome）并通过经典信道传给Bob端，Bob端译出Alice端的密钥信息该方法即为数据协调中的正向协调

1.1LDPC应用概述

低密度奇偶校验码（LDPC） 最早是由Gallager在其1962年发表的博士论文中提出1996年，MacKay等[12]发现LDPC的性能具有超越Turbo码的趋势，从此，LDPC的研究进入新的阶段，引起了人们的广泛关注与研究LDPC利用稀疏的校验矩阵进行编译码，校验矩阵构造合适时，可以实现低信噪比下的完美译码其码率灵活可变，译码算法简单，且可并行计算，这些特点非常适用于数据协调要求

1.2LDPC的构造方法

不同方法构造的校验矩阵性能各异，编译码复杂度也互不相同因此，如何构造一个兼顾低复杂度和优秀性能的LDPC成为研究者们一直追求的目标[13]本方案中构造LDPC的主要工作是：首先寻找一个稀疏矩阵H，使以H为校验矩阵的线性分组码有较好的纠错能力，并且解码的复杂度和码长n呈线性关系信息论的研究成果表明，稀疏校验矩阵H越大，1的分布越随机，LDPC的解码性能越好，越接近于香农限本方案采用C语言实现，其核心技术是H矩阵的内存占用问题，随着分组码长增加到百万级别，计算机的内存难以承担负荷解决方法是利用H矩阵的稀疏性，即只记录1的位置的方式存储H矩阵，这样可极大地降低空间复杂度本文采用双向循环链表的方式，研究如何提高矩阵元素的定位速度，实现整体系统仿真优化

2基于边信息的二进制信源压缩

2.1QKD正向协调模型

在实际量子密钥传输系统中，Bob端收到的信息含有各种噪声、损失和窃听等干扰，为了在原始密钥序列中提取出绝对安全的密钥序列，BB84和B92协议规定，需要在QKD系统中引入数据协调（reconciliation）的步骤，即Bob对量子态进行测量重新得到经典数据后，利用公开经典信道对筛选后数据进行纠错数据协调的作用是，通过纠错编码的方法和信道纠错编码技术把Alice和Bob共同拥有的存在少量不一致的序列变为一致序列

正向协调是Alice根据校验矩阵计算出校验子（syndrome）并通过经典信道传给Bob端，Bob端译出Alice端的密钥信息从信息论的角度来看，量子密钥通信+正向协调系统可抽象成图2所示模型

2.2二进制信源编码和压缩

4数值仿真结果及分析

5结语

本文为了提高数据协调的可靠性和有效性，提出两种解决方案，首先，协调方案采用数据协调中的正向协调方案，这种方案得益于避开由校验矩阵产生生成矩阵，从策略上加速译码；其次，将LDPC校验矩阵以稀疏矩阵的形式存储，以降低空间复杂度来提高译码速度，从根本上加速译码实验结果表明当码长为105时，收敛于1.0dB，译码收敛后速率达到24.85kb/s，时效性较强

进一步的研究工作是能够在更低信噪比下加速收敛，从优化校验矩阵度分布这一角度进一步降低信噪比要求，最终将在现场可编程门阵列（Field Programmable Gate Array，FPGA）上实现整个协调过程

参考文献：

[1]陈晓峰，王育民. 公钥密码体制研究与进展[J]. 通信学报， 2004， 25 （8）： 109-118.

[2]van ASSCHE G， CARDINAL J， CERF N J. Reconciliation of a quantumdistributed gaussian key [J]. IEEE Transactions on Information Theory， 2004， 50（2）： 394-400.

[3]LEVERRIER A， GRANGIER P. Continuousvariable quantum key distribution protocols with a discrete modulation [J/OL]. ArXiv Preprint， 2010： 1002.4083 （2011-01-24） [2013-02-12]. http：//arxiv.org/abs/1002.4083.

[4]MINK A， NAKASSIS A. LDPC for QKD reconciliation [J/OL]. ArXiv Preprint， 2012： 1205.4977 （2012-05-22） [2013-02-16]. http：//arxiv.org/abs/1205.4977.

[5]NAMEKATA N， TAKESUE H， HONJO T， et al. Highrate quantum key distribution over 100 km using ultralownoise， 2GHz sinusoidally gated InGaAs/InP avalanche photodiodes [J]. Optics Express， 2011， 19（11）： 10632-10639.

[6]LODEWYCK J， BLOCH M， GARCAPARTN R， et al. Quantum key distribution over 25km with an allfiber continuousvariable system [J]. Physical Review A， 2007， 76（4）： 042305.

[7]LEVERRIER A， GRANGIER P. Continuousvariable quantum key distribution protocols with a nonGaussian modulation[J]. Physical Review A， 2011， 83（4）：042312.

[8]ZHOU N R， WANG L J， GONG L H， et al. Quantum deterministic key distribution protocols based on teleportation and entanglement swapping [J]. Optics Communications， 2011， 284（19）：4836-4842.

[9]宋汉冲， 龚黎华， 周南润. 基于量子远程通信的连续变量量子确定性密钥分配协议[J]. 物理学报， 2012， 61（15）： 154206.

[10]WANG X Y， BAI Z L， WANG S F， et al. Fourstate modulation continuous variable quantum key distribution over a 30km fiber and analysis of excess noise [J]. Chinese Physics Letters， 2013， 30 （1）： 010305.

[11]LIVERIS A D， XIONG Z X， GEORGHIADESC N. Compression of binary sources with side information at the decoder using LDPC codes [J]. IEEE Communications Letters， 2002， 6（10）： 440-442.

[12]MacKAY D J C， NEAL R M. Near Shannon limit performance of low density parity check codes [J]. Electron Letters， 1996， 33（6）： 457-458.

[13]袁东风， 张海刚. LDPC码理论与应用[M]. 北京：人民邮电出版社， 2008：63-68.