（信号与信息处理专业论文）cfb纠错联合算法和rfid防碰撞算法的研究.pdf

东南大学硕士学位论文摘要 摘要 提高无线网络数据传输的可靠性与安全性，已成为无线网络中日益重要的研究课 题。本文针对无线网络数据传输的安全性、可靠性，主要从以下两个方面展开了研究： ( 1 ) 无线信道纠错和加密编码算法研究。传统的通信系统分别通过加密模块和纠错 模块来保证无线数据通信的安全性和可靠性，这种结构往往使整个系统传输信息的速 率降低，也增加了设备的复杂性。针对上述弊病，本文提出了一种既能实现加密功能 又有一定纠错能力的结构算法c f b 纠错联合算法。该算法建立在分组密码算法的 c f b 工作模式上，利用一组移位寄存器结构同时实现了加密和纠错编码。 本文利用统计分析的方法对c f b 纠错联合算法进行了安全性能分析。依赖性测 试表明：算法的雪崩效应度约为o 9 9 9 3 ；频率测试表明：算法输出服从均匀分布；连 续测试表明：算法输出在0 和1 之间更迭速率适中；频谱测试表明：低于门限的峰值 满足要求。 该算法同时具备较强的纠错能力。测试数据表明，在模拟高斯白噪声信道坏境下， e b n 。= 3 d b 时，算法的误比特率p b = 1 0 一，有效的降低了误码率。 此外，与传统的加密纠错分别实现的算法相比，当输入的数据量较大时，该算法 的运算速率提高了5 。 分析表明，c f b 联合算法可以同时提供纠错性和保密性，适合在无线网络中应用。 ( 2 ) r f i d 系统防碰撞算法研究。防碰撞算法也就是利用多路存取法，使得无线网 络中的接收端和发送端之间数据能够可靠的传输，是保证无线网络可靠性的关键性技 术。本文提出了一种基于码分多址( c d m a ) 的防碰撞算法。该算法利用g o l d 序列 较好的相关特性，为无线网络中的每个用户分配一个唯一的即肼序列来实现多址接 入，有效的减少了r f i d 系统的碰撞。 实验表明，在高斯白噪声信道模型环境中有5 2 0 个用户同时接入时，在门限值 选择恰当的情况下，此方法能够达到较准确的识别效果，有效的实现了防碰撞。最后， 本文讨论了该算法在r f i d 网络中的具体实现方案。 最后本文对c f b 纠错联合密码算法和基于c d m a 方式实现的防碰撞算法进行了 总结。并且针对工作中出现的问题以及将来算法进一步的完善提出了几点建议。 关键词：纠错编码分组加密d e sc f b防碰撞r f i d 东南大学硕士学位论文 a b a s t r a c t a b s t r a c t t oi m p r o v et h er e l i a b i l i t ya n ds e c u r i t yo fd a mt r a n s m i s s i o ni nw i r l e s sn e t w o r k sh a sb e e n d r a w nm o r ea t t e n t i o n si nt h er e s e a r c hf i l e do fw i t l e s sn e t w o r k s t h i st h e s i sd o e si n v e s t i g a t i o ni n t h et w of o l l o w i n ga s p e c t s ： ( 1 ) r e s e a r c h o n e r r o r - c o r r e c t i n gc o d i n g a n d e n c r y p f i o n i nw i r e l e s sn e t w o r k s e r r o r - c o r r e c t i n gc o d i n ga n de n c r y p t i na r et r e a t e d a st w oi n d e p e n d e n ts w e e t si nt r a t i o n a l c o m m u n i c a t i o ns y s t e m s ，w h i c hl e a d st oi n c r e a s ew i t ht h ec o m p l e x i t yo fd e v i c e j o i n tc f b e r r o r - c o r r e c t i n ga l g o r i t h m i s p r o p o s e d i nt h et h e s i sw h i c hh a v i n gf u n c t i o n so fb o t h e r r o r - c o r r e c t i n ga n de n c r y p t i o n n l i sa l g o r i t h mi sb a s e do nt h ec i p h e rf e e d b a c km o d e o fb l o c k c i p h e r s ，a n du s e sas e to f s h i f tr e g i s t e r st oi m p l e m e n te n c r y p t i o na n de r r o r - c o r r e c t i n ga to n et i m e u t i l i z e dt o o l so fs t a t i s t i c a l a n a l y s i s ，t h ep e r f o r m a n c eo ft h ej o i n t c f be r r o r - c o r r e c t i n g a l g o r i t h mo ns e c u r i t ya r ea n a l y z e d t h ed e p e n d e n c et e s tr e s u l t sa c c o r d e dw i mt h ed e m a n d s i t s d e g r e eo fa v a l a n c h ee f f e c ti sa b o u to 9 9 9 3 t h ef r e q u e n c yt e s tr e s u l t si n d i c a t e st h a tt h eo u t p u t g e n e r a t e db yt h ea l g o r i t h mh a su n i f o r m i t y t h er u nt e s tr e s u l t si n d i c a t e st h a to u t p u ta l t e r n a t e s b e t w e e n0a n d1e v e n l y t h es p e c t r a lt e s tr e s u l t sa c c o r d e dw i t hd e m a n d s t h ej o i n tc f be r r o r - c o r r e c t i n ga l g o r i t h mh a ss t r o n ge r r o r - c o r r e c t i n gc a p a b i l i t y t h et e s td a t a i n d i c a t e st h a t ，u n d e rt h ea s s u m p t i o no f j o i n t l yg a u s s i a nd i s t r i b u t i o no fc h a n n e lo u t p u t , w h i l et h e s n re b n o = 3 d b ，t h eb e rp b = 10 。3 ，d e c r e a s e st h eb e re f f e c t i v e l y c o m p a r e dw i t ht h et r a d i t i o n a ls y s t e mi nw h i c he r r o r - c o r r e c t i n gc o d i n ga n de n c r y p t i o na r e t r e a t e ds e p e r a t e d l y , t h ec o m p u t i n gs p e e di n c r e a s e db y5 ( 2 ) r e s e a r c ho na n t i c o l l i s i o na l g o r i t h m si nr f i ds y s t e m s t h ea n t i c o l l i s i o na l g o r i t h m su s e s t h et e c h n o l o g yo fm u l t i p l ea c c e s st ot r a n s i m i t ed a t af r o mt r a n s m i t t e rt or e c e i v e rr e l i a b l y i ti sa k e yt e c h n o l o g yt oe n s u r et h er e l i a b i l i t yo f w i r e l e s sn e t w o r k s t h et h e s i sp r o p o s e sa c d m a _ b a s e d a n t i c o l l i s i o na l g o r i t h m i tu s e st h eg o o dc o r r e l a t i o no fg o l ds e q u e n c e ，a s s i g n e dau n i q u eg o l d s e q u e n c ef o re a c hu s e ri nw i r e l e s sn e t w o r k st oi m p l e m e n tm u l t i p l ea c c e s s ，t or e d u c ec o l l i s i o ni n r f i ds y s t e m s e x p e r i m e n t si n d i c a t e st h a t ，u n d e rt h ea s s u m p t i o no f j o i n t l yg a u s s i a nd i s t r i b u t i o no f c h a n n e l o u t p u t ，w h i l e5 - 2 0 n s e r sa c c e s s e sa tat i m e , t h ea l g o r i t h mg i v e sa c c u r a t er e c o g n i t i o n f i n a l l y ，t h et h e s i sp r e s e n t sai m p l e m e n t a t i o no f t h ea l g o r i t h mi nr f i ds y s t e m e r r o r - c o r r e c t i n g b l o c kc i p h e r sd e s c f ba n t i c o l l i s i o nr f i d 1 】 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了 谢意。 研究生签名：盟日 期：巫珥 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和 纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办 理。 研究生签名： 东南大学硕士学位论文 第一章绪论 第一章绪论 随着无线通信与网络技术的快速发展，无线网络已经渗透到国防军事、教学科研和 医疗卫生等国民经济的各个部门，与人们的日常生活紧密相连。无线网络的应用越来越 广泛，无线网络的安全性和可靠性就越重要。 首先，无线网络要求能够在安全的、可靠的进行数据传输的同时，提高系统的编码 效率，降低系统的复杂性。 其次，当同时存在多个相同的无线设备时，保证各个设备不发生碰撞，实现多址接 入也是保证无线网络中数据传输可靠性的一个关键技术。 针对以上两个方面，本文分别提出了相应解决无线网络中数据传输可靠性问题的 创新性算法。 1 1 无线信道纠错和加密编码算法 传统的无线数据通信系统中，分别用密码算法和纠错码算法来解决数据传输的安全 性和可靠性问题。如图1 1 所示。但是这种把加密和纠错分别考虑的方法有一些缺点， 降低了整个系统传输信息的速率，增加了设备的复杂性，不能满足无线设备降低系统复 杂性的要求。 图1 1 传统通信系统的物理模型 1 9 4 8 年c e s h a n n o n 提出了著名的信道编码定理，指明了纠错码的研究方向，此文 标志着编码理论的开端。1 9 4 9 年，s h a n n o n 从信息论的角度阐述了密码学的基本问题， 从而奠定了现代密码学的基础。 纠错码的任务是通过增加消息多余度的办法排除在噪声信道下传输消息时所带来 的干扰，从而使接收端能够纠正错误，正确译码。与此相反，密码学的任务则是人为的 在要传输的消息中加入“噪声”，使其变成窃听者难于解读的消息，而接收端则可以通 过密钥将消息正确解密。在7 0 年代以前，纠错码理论和密码学几乎互不相关，各自独 立地向前发展。本文提出这样一个问题：能否设计出一个既能实现加密功能又有一定纠 东南大学硕士学位论文 第一章绪论 错能力的结构，这样既可以实现数据的可靠传输，又可以提高系统得编码效率，降低系 统及设备的复杂度。 1 9 7 6 年w d i m e 和m e h e l l m a n 发表了在密码学领域中具有里程碑意义的文章“密 码学的新方向，指明了s h a n n o n 在1 9 4 9 年所提出的将密码系统建立在某个已知数学难 题之上的具体实现途径。1 9 7 8 年e 1 l b e r l e k a m p 1 l j m c e l i e e e 和h c a v a nt f l b o r g 证明 了纠错码中一般线性分组码的译码问题是一个n p c 问题。这两项成果建立起纠错码和 密码学相结合的理论基础。同年，& j m e e l i e c e 根据一般线性分组码的译码问题是一个 n p c 问题，g o p l ) a 码具有快速译码算法的特点，首次构造了基于纠错码的公钥密码体制， 简称为m 公钥密码体制。该体制的公钥是随机产生的一个线性分组码的生成阵，公钥 隐藏了线性分组码的快速译码算法，是一种局部随机密码体制。从此以后，有关纠错码 和密码相结合的研究迅速发展起来。 r a o 于1 9 8 6 年构造了一个用汉明码私钥加密系统，它对生成矩阵保密。r a o 私钥体 制只需要使用简单的纠错码就能提供很好的保密性。因此，相对m c e l i e e e 公钥体制而 言，r a o 私钥体制需要很小的计算量和存储量，为纠错与加密相结合的实用阶段奠定了 基础。r a o 私钥密码体制的安全性和m e e l i e e e 密码体制的安全性相当。但是，若在该 体制中使用短码，那么r a o 体制是不安全的。 王新梅等人在m s 公钥体制的基础上，提出了一个问题：能否把加密和纠错作为一 个整体考虑，提出一种既能加密又能纠错的密码体制呢? 王新梅在文献 1 】中首先讨论 了此问题，并提出了既能加密又能具有一定纠错能力的m s 公钥体制。1 9 8 6 年，王新梅 在m 和m s 公钥体制的缺点，对其进行修正，使其能够适用于传统的分组加密( 非公开 密钥) ，提出了加密与纠错相结合的m c 分组加密纠错体制，在文献【2 】中讨论了该体制 的安全性，并讨论了它在有扰信道中的性能。 纠错密码体制基于代数编码理论之上，若用于实际系统中，必然要求巨大的存储量 和计算量，并不实用。本文从密码体制和纠错码的生成器的结构的相似性出发，提出了 c f b 纠错联合算法。在对分组密码算法的c f b 工作模式的研究中中发现该模式中的移 位寄存器组结构与线性纠错码的移位寄存器组的结构很类似，本文即将密码算法和线性 纠错码算法中移位寄存器的结构统一起来，用一组移位寄存器结构同时实现了加密和纠 错码的设计，并将之命名为c f b 纠错联合算法。本文在第四章和第五章详细分析了c f b 纠错联合算法，给出了详细的安全性分析、纠错能力分析。 1 2 蛐系统防碰撞算法 无线电通信系统中多路存取方法一般具有以下几种形式，空分多路法( s c d m a ) 、时 分多路法( t d m a ) 、频分多路法( f d m a ) 、码分多路法( c d m a ) 。射频识别系统多路存取 技术的实现对射频标签和阅读器提出了特殊的要求，因为必须使人们感觉不到浪费时 间，必须可靠的防止由于射频标签的数据相互冲突而不能读出。 射频识别( r a d i of r e q u e n c yi d e n t i f i c a t i o n ，r f i d ) 技术是从上世纪8 0 年代走向成熟的 一项自动识别技术，近年来发展十分迅速。它是一种非接触式的自动识别技术，其基本 原理是利用射频信号及其空问耦合和传输的特性，实现对静止或移动物体的自动识别。 东南大学硕士学位论文第一章绪论 当许多个标签同时进入识读器识读范围内后，能否实现百分百的多址接入，使得识读器 完全检测到这些标签是r f i d 系统要解决的主要问题。解决这个问题的算法称为防碰撞 算法。本文针对r f i d 系统中的防碰撞算法提出了一种基于码分多址( c d m a ) 的防碰 撞算法。 目前在射频识别系统中，主要是采用时分多路法的原理，使每个电子标签在单独的 某个时隙内占用信道与阅读器进行通信，防止碰撞产生。时分多路防碰撞算法主要有 a l o h a 算法、二叉树搜索算法和c d m a c a 等。 二叉树搜索算法的核心思想是：识读器根据冲突的信号，按照二叉树深度优先搜索 的思想，逐步缩小范围，搜索符合条件的标签，直至找到规定的射频标签。 a l o h a 算法一般用于只读电子标签中。这类电子标签通常只有一些数据( 序列号) 传输给阅读器，并且是在一个周期性的循环中将这些数据发送给阅读器。数据传输时间 只是重复时间的一小部分，以致在传输之问产生相当长的间歇。此外，各个电子标签之 间的重复时间之间的差别是微不足道的。所以存在着一定的概率，两个电子标签可以在 不同的时间段上设置它们的数据，使数据包不互相碰撞。目前，针对r f i d 系统的防碰 撞算法研究是国内外通信领域的一个重要方向，具有非常高的研究价值。 本文对一种伪随机序列_ g d 埘序列的相关特性仿真结果表明g o l d 序列具有明显 的自相关峰值和类白噪声的互相关特性。在此仿真的基础上，本文给出了一种防碰撞方 法：无线网络中的每个用户被分配到一个唯一的g o l d 序列，用户接入时接收端用循环 移位的方式与用户g o l d 序列进行相关操作，将相关值与系统门限值比较，大于门限值 则该用户被检测到，有效的降低了碰撞几率。 1 3 本论文研究内容与组织结构 本文内容分为两个部分，首先在研究分组加密算法和纠错码算法的原理的基础上提出 了一种既可以实现加密功能又可以实现纠错功能的联合算法c f b 纠错联合算法；接着 在对无线信道防碰撞算法的研究中提出了一种新的码分多址，防碰撞算法。 论文内容安排如下： 第一章为绪言，介绍本文的研究目的、国内外应用和研究动态，引出本文工作。 第二章首先详细介绍了目前已有的一些纠错编码技术，重点介绍线性分组码、循环 码以及卷积码的编译码原理，并用m a t l a b 仿真工具对b c h 码和卷积码做了纠错性能分 析。接着介绍了分组密码纠错体制以及算法原理，然后分析了几种算法的原理和性能， 并进行比较，指出这几种算法的优劣。 第三章详细阐述了数据加密标准，包括分组密码算法和序列密码算法两个方面。在 分组密码部分重点介绍了d e s 算法和a e s 算法。序列密码部分主要介绍了密钥流的产 生，一是通过线性反馈移位寄存器产生伪随机数；二是用密码编码学的方法生成密钥流。 在第四章和第六章分别基于这两种方法提出了c f b 纠错联合算法和一种可应用于f r i d 系统中的防碰撞算法。 第四章首先介绍了d e s 算法的c f b 结构，接着对c f b 纠错联合算法的结构进行了 详细描述，给出了理论推导及框图结构。并分别针对分组b c h 码和卷积码给出了c f b 查壹查兰堡主望堡垒查 苎二主竺垒 纠错联合算法的两种结构。 第五章并利用密码学常用的统计测试套件对联合算法进行白化性能测试。最后从理 论上分析算法的抗攻击性能，并与现有的通信系统得分模块的实现方式进行综合性能比 较。 第六章首先介绍了r f i d 系统中的传统防碰撞算法设计，给出了g o l d 序列的生成和 相关性仿真测试结果，并利用g o l d 序列的相关特性提出了一种可应用于r f i d 系统中的 防碰撞算法。给出了高斯白噪声信道环境下，此算法的防碰撞效果。最后，给出了此算 法在r f i d 系统中的一个实现。 第七章对近1 0 个月来的工作进行了总结，指出了工作的不足并下一步的改进和研 究做出了展望。 东南大学硕士学位论文 第二章纠错编码体制 第二章纠错密码体制 2 1 纠错编码的基本概念及其本质 纠错码 2 l 】，又称差错控制编码，是在信息码元序列中加人监督码元，这些监督码 元和信息码元之间有一定的关系，使接收端可以利用这种关系由信道译码器来发现或纠 正可能存在的错码。不同的编码方法，有不同的检错和纠错能力。一般来说，检错、纠 锗的能力就越强，增加的监督码元就越多，系统付出的代价就越大。因此说，纠错编码 实际上是以降低信息传输速率为代价来换取传输可靠性的提高。 1 9 4 8 年，信息论的开创者c 。e s h a n n o n 在他的奠基性论文“am a t h e m a t i c a lo f c o m m u n i c a t i o n ”中提出著名的信道编码定理，即对每一类信道都存在着一定的信道容 量c ，它是信道的极限传输能力，称之为s h a n n o n 限。只要当实际传输速率r c 时， 就可以实现在信道中的无差错传输。信道编码定理为以后纠错码的发展指明了方向。此 后国内外的学者以s h a n n o n 限为目标构造出了各种各样的性能优异的纠错码。下面简单 介绍几种基本的、重要的纠错码。 2 1 1 线性分组码的编码和译码 线性分组码 1 4 】f 2 l 】是分组码中最重要的一类码，它是讨论各类码的基础。 分组码是由一组固定长度的称为码字的矢量构成。码字的长度是矢量元素的个数， 用n 表示。长度为肝的二进制分组码有2 ”种可能的码字。从这2 0 种码字中，可以选取 2 个码字( k ”) 组成一种码。这样，一个k 比特信息的分组可以映射到长度为以的一个 码字，该码字是从由m = 2 个码字构成的码集中选出来的。这样的分组码称为，码， 定义k nz r为码率。除码率尼这个参数外，另一个重要的参数是码字的重量，即该e 码字包含的非零元素的个数。编、解码的功能体现为对码字实行乘、加算术运算，算术 运算的规则服从元素所在字符集代数域的惯例。 设g f ( q ) 的子空间碥 中共有矿个元素，它就是m ，明码的码字，称它们为许用码字， 而其余矿彳个元素( 矢量或玎重) ，称为禁用码字。 定义 g = 蜀 9 2 ： g t g 9 1 2 9 2 t9 2 2 g l lg k 2 g l 9 2 g h 为该印，时玛的生成矩阵。这里g l , 9 2 ，g k 是 n ，明线性分组码k 维线性子空间中一组基 底。显然g l , 9 2 ，积均是码中的码字。设t n = ( m l 。m 2 , m k ) g f ( 碍) 是由信息源输入至 纠错码编码器的信息组，则由编码器输出的码字c = b ，c ：，c 。】= m g 。任何码字都是 g 的矢量 g f 的线性组合。 6 东南大学硕士学位论文 第二章纠错编码体制 仇柚码的任何生成矩阵都可以通过行运算( 以及列置换) 简化成系统形式： g = 口。fp 1 ，这里的厶是k k 维单位矩阵，p 是k ( 撑一k ) 维矩阵，由它决定小七个冗 余比特和一致校验位。在由系统形式的生成矩阵所生成的线性分组码中，每个码字的前 k 位与所要发送的信息比特相同，其余n - k 位是前k 个信息位的线性组合。这样生成的 以d 码叫做系统码。 输入 气 图2 1 生成( 7 ，4 ) 二进制码的线性移存器 如图2 1 所示，一个二进n ( n ，助系统线性分组码的编码器可用k 级移存器和连接到 移存器适当位置的n - k 个模2 加法器组成。检验位由 一k 个加法器生成，它们按顺序暂 存在另一个长度为n k 的移存器中。k 比特信息分组移位输入k 级寄存器，加法器计算 n - k 校验比特，然后先是k 位信息、紧接着是雕位校验比特从两个移存器中移位输出， 送到调制器。 任何一个( h ，舫线性码都有胛k 维对偶码与之关联。对偶码是一种( 聆，h 一动线性码，有 2 脚个码矢量，这些矢量属于( 胛，缈吗的零空间。对偶码的生成矩阵用日表示，是由零空 间中雄，k 个线性无关的码矢量组成的。( ，l ，妨码的任意一个码字g 。均正交于其对偶码的 任意一个码字，因此( ，z ，功码的任意一个码字均正交于矩阵的每一行，即 q h = 0 因为上式对伽，国码的每个码字都成立，则 g h = 0 日矩阵被译码器用来检查接收到的码字是否满足y t p = 0 ，所以把日矩阵成为( 以，妨码的 一致检验矩阵。 纠错编码的性能不仅与编码种类、方式有关，而且与译码方法和具体的工作信道也 有很大关系，在研究二元码编码的性能时通常先采用最简单的二进制对称信道( b s c ) 模型，考察其性能，然后再推导在其他信道中的性能。 设信道误比特率为p ，则传输中( 甩，句线性分组码的一个码组n 位比特中发生f 个差 错的概率以l 丹) 可以用二项分布描述为： p ( i ，聍) = q p l ( 1 一p ) “ 一个码组的行位比特只要有1 位出错，那么该码组就错了，因此接收到的码组( 解调器 之后纠错之前) 发生错误的概率只可以表述为： 东南大学硕士学位论文第二章纠错编码体制 h 只= m ) = q ( 1 - p ) ” a - i1 = 1 设该分组码的纠错能力为，该码组经过纠错后，错误码组中小于等于，比特的错误 码组都被纠正，这时码组的错误概率，矗为： h 匕= e ( i ，n ) = q p ( 1 - p ) “ t f f i i + l i - i + l 在衡量信道编码性能的时候，要从信息传输的角度，用误比特率忍一历0 的关系 作为标准。对线性分组码来说，译码的误比特率也可以近似为： 匕= 吾毫惭) = 丢麦f c ：p m p 广 用d m i n 替代重量分布，得到比上式更简单的形式，即： 耻i 窆。i p ( i , n ) = 丢毫烈l 一矿7 2 1 2b 佣码编解码原理及性能仿真 b c h 码 1 4 1 是1 9 5 9 年由h o c q u e n g h o n ，1 9 6 0 年由b o s e 和r a y - c h a u d h u i 分别独立得 到的可纠多个随机错误的循环码。b c h 码是迄今为止所发现的一类性能优良的线性纠 错码类，它的纠错能力强，在短码长和中等码长下，其性能很接近于理论值，构造方便， 编码简单，并且有快速的译码方法，能纠正多个随机错误。特别是它具有严格的代数结 构，因此它在编码理论与实际中起到重要的作用，也是迄今为止研究最为详尽、分析得 最为透彻、取得成果最为丰富的码类，并且可以用它构造某些密码体制和认证码。 二进制b c h 码的构造可具有下列参数： r = 2 “- 1 疗一k 朋f d m = 2 t + 1 式中，m ( m 3 ) 和t 是任意正整数。这类二进制b c h 码为通信系统设计者们在码长和 码率方面提供了很大的选择余地。 b c h 码的严格定义是：给定任一有限域卯劬及其扩域a ，其中g 是素数或素数 的幂，肼为某一正整数。若码元取自g f 上的一循环码，它的生成多项式占的根集合 r 中含有以下j 1 个连续根：r = k ，口，口”“ 时，则由g 生成的循环码称为g 东南大学硕士学位论文 第二章纠错编码体制 进制b c h 码。 其中，口g f ”) 是域中的行级元素，口”“g f ( q ”) ( o s f s 6 2 ) ，m 0 是任意整数， 但是但最常见的情况是：r n 旷- - 0 或1 。若m o = l ，则称这类b c h 码为狭义b c h 码。 设小，( x ) 和e ，分别是o r m o + t ( f = o ，1 ，艿一2 ) 元素的最小多项式和级，则可知，b c h 码 的生成多项式和码长分别是 g ( 力= l c m ( m o ( x ) ，m o ( 力，m 8 - 2 ( x ) ) 露= l c m ( e o ，q ，一2 ) 如果生成多项式酬的根中，有一个g 只q 中的本原域元素，则甩= q ”- 1 ，称这种 码长万= q “一1 的b c h 码为本原b c h 码；否则，称为非本原b c h 码。 一个码的纠错能力，完全由它的最小汉明距离d 。来决定，而b c h 码的d 。完全由 g o ) 的根决定。研究d 。与go ) 的根的关系一直是一个非常引人注目的研究课题。b c h 码是用根来定义循环码，用控制根来控制纠错能力的。对任何正整数m 和，一定存在一 个二进带j j b c h 码，它以口，a 3 ，t 2 2 “1 为根，其码长刀= 2 ”一1 或2 ”一l 的因子，能纠正t 个随机错误校验位数目至多为o g ( x ) = m t 个。 b c h 码一般情况下是循环码的一个子类。因此可以采用循环码的编码方法，根据生 成多项式组成b c h 码编码器。b c h 码的解码方法分成时域和频域两种方法。频域解码是 把每个码组看成是一个数字信号，把接收的信号进行离散傅立叶变换( d f t ) ，然后利用 数字信号处理在“频域”里解码，最后进行傅立叶反换得到解码后的码组。时域解码是 在时域上直接利用码的代数结构进行解码。 下面介绍用于时域解码的彼得森提出的解码算法。可以分四步： ( 1 ) 用量0 ) 的各因式作为除式，对接收到的码多项式求余，得n t 个余式，称为“部分校 正子”； ( 2 ) 用价“部分校正子”构造一个特定的“解码多项式”，它以错误位置数为根； ( 3 ) 求解码多项式的根，得到错误位置； ( 4 ) 纠正错误。 假定采用硬判决的加性高斯白噪声信道，图2 2 出了码率为1 2 的本原b c h ( 1 2 7 ， “) 码和b c h ( 7 ，4 ) 码的误比特率曲线： 如图2 2 ，随着分组长度的增加，b c h 码的纠错能力迅速增强，但此时译码的复杂性 和延时也迅速增大。 东南大学硕士学位论文第二章纠错编码体制 国2 2 部分b o h 码的误比特率性能( 高斯白噪声信道) 2 1 3 卷积码的编解码原理及性能仿真 卷积码f 1 4 】编码器结构如图2 3 所示。图中的曲线代表滑动窗，每个时刻它总是沿 着输入数据流滑动并且包含一个分组( 七个符号) 。该图说明了当前押个编码输出码符号 不仅依赖当前k 的数据符号，同样也依赖于( m 1 ) 个以前的数据分组。总的输入分组为n ， 也就是卷积码的限制长度。n - 1 通常也称作卷积码的记忆阶数；卷积码的记忆也就是 k ( n - 0 。通常把( 一1 ) 称为约束长度。常把卷积码记作( ，l ，) ，编码效率为：k n 。卷 积编码具有以下的一些特点： ( 1 ) 卷积码中编码后的珂个码元不但与当前段k 个信息有关，而且与前面_ 1 段的信 息有关，编码过程中相互关联的码元为n n 个。 ( 2 ) 卷积码的纠错能力随着的增加而增大，而差错率随着的增加而指数下降。 在编码器复杂性相同的情况下，卷积码的性能优于分组码。 ( 3 ) 分组码有严格的代数结构，但卷积码至今尚未找到严密的数学手段，把纠错性能 与码的构成十分规律的联系起来，目前大都采用计算机来搜索好码。 - 1 0 - 东南大学硕士学位论文第二章纠错编码体制 l 2 ，o b ，o h 12 kl2 k k ，- o h l2 k l23 oo n 图2 3 卷积编码器的一般形式 列 为了进一步理解卷积编码器的结构，图2 4 所示给出了编码效率为1 2 ，约束长度为 3 的卷积编码器结构。 状态 输出序列 图2 4 ( 2 ，1 ，3 ) 卷积编码器 卷积编码器是一种能够产生有限数量状态的器件，根据输入的序列，编码器在不同 的状态组之间进行转移。因此这种编码器也称作有限状态机。可以采用状态图很容易地 表示。方向线表示状态和允许它们之间进行转移。图2 5 就是对图2 4 中编码器的状态 描述。 0 0 1 0 图2 5 卷积编码器状态图 卷积码可以采用序列译码，门限译码，v i t e r b i 译码等译码算法，约束长度较小的卷 积码通常采用维特比译码算法。 维特比译码是一类最大似然算法 1 8 】：把接收序列与所有可能的发送序列比较，选 择一种码距最小的序列作为发送序列。这里的码距可以是汉明距离也可以是欧式距离。 东南大学硕士学位论文 第二章纠错编码体制 算法步骤如下： 接收数据前，先将各状态的幸存路径与路径量度清零。在，z 时刻进入某一状态的状 态转移( t r a n s i t i o n ) 都有两个，这两个状态转移分别由珈l 时刻的两个不同状态发出，且 它们代表的输入比特相同( 1 或、0 ) ，每个状态转移中都对应着输入某比特后卷积编码器 的输出。将这两个输出码与接收到的输入码闻的距离( 可以是汉明距离也可以是欧氏距 离) 计算出来称为分支量度。 将 时刻到达同一状态对应的伊l 时刻的两状态的路径量度分别加上计算出的对应 分支量度，得出两个新的路径量度，取这两个新的路径量度中较小的一个。那么将较小 的路径度量赋予一时刻到达的状态的路径度量，再将幸存路径添上输入的信息比特赋予 即时刻状态的幸存路径。 在珂时刻每个状态操作完后，所有状态的幸存路径与路径量度就被刷新了。对肿1 时刻的每个状态重复上述步骤。以此类推，直至一帧数据解完。最后对应路径量度最小 的幸存路径就是 t e r b i 译码器的输出。 ( n ，k ，所) 卷积编码器共有个2 ”状态，每一个状态对应一个路径寄存器来存储路径 序列，以及一个存储路径度量值的存储器，因此可以看出译码器的复杂度随着编码寄存 器而的个数指数增加。 若发送序列长度为厶到三时刻，篱笆图中的所有状态每一个状态有一条留选路径， 时刻以后，篱笆图上的状态减少，留选路径也减少，直到归到全0 状态，并且仅剩下 一条留选路径，这条路径就是最大似然路径。 译码器一般由以下4 个功能单元组成： f 1 1 分支度量单元( b m u ) 完成译码输入信号与篱笆树上可能的路径信号的分支度量 计算，硬判决和软判决的度量的算法是不同的。硬判决是送入译码器的直接是经过判决 的b i t 流，我们直接将接收到的码元和篱笆图上的标准输计算出汉明距离，作为分支度 量。而对于软判决来说，采用欧式距离来计算欧式距离。进入译码器的是为未经解调和 判决的模拟值，首先将接收到的数据软解调，再送进译码器进行软判决译码。 ( 2 ) 加比选运算单元( a c s u ) 是l i t e r b i 译码器的处理单元，通过加比选来计算每个状 态在某一时刻的度量值。加比选单元把前一状态的路径度量，与当前输入信号的分支度 量相加得到该分支的路径度量，比较不同分支的路径度量的大小，选择最小的度量值， 更新该状态的度量值，同时将加比选的后得到幸存路径送入存储单元。 为了减少延时，采用3 2 个蝶形运算结并行运算，进行加比选运算 ( 3 ) 幸存路径保留单元( s m u ) 完成对幸存路径的完成，直接利用f p g a 的片内资源双 端口r a m 来存储，将r a m 的地址与每个状态相对应，每一个时刻存储6 4 个状态对应 的幸存路径。 ( 4 ) 路径回溯单元( t b u ) 当译码深度达到我们的回溯长度l 以后，每个状态都对应了一 个累计的度量值，以及一个幸存路径的序列，从中选出一个累计度量最小的状态开始回 溯，同时从s m u 单元读出保存的6 以利用移位寄存器回溯前三个状态，读出相应的幸 存路径，从而得到译码b i t 对于卷积码的硬判决译码，维特比算法的量度是指接收序列与网格每节点z ”1 个 东南大学硕士学位论文第二章纠错编码体制 留存序列之间的汉明距离。从确定首次差错事件概率开始。假设发送的是全零路径，并 假定某节点b 上准备与全零路径比较的路径和全零路径相距d 。若d 是奇数，那么当接 收序列的差错数小于( 舟1 ) 2 时，会正确的选择全零路径；反之，选择错误路径。所以， 选择错误路径的概率为： 鳓= t - - ( 妻a + d 2 船矿 鳓= l ：i 矿( 1 一矿 几 若d 为偶数，差错数超过d 2 时将选择错误路径。如果差错数等于d 2 ，两条路径的量 度一样，随便选择两条路径之一，这时有一半差错机会。于是，选择差错路径的总概率 是： 鳓= 黑陟矿毛陟删2 p e 乃昱( d ) 式中，系数 表示与不同距离集合 彳诒葑应的路径数目。这些系数正是转移函数 t ( d ) p s j et ( d ，n ) 展开式中的系数。由此可得首次差错事件概率的较松的上边界如下： p e a a 4 p ( 1 一p ) p r ( d ) id - 、4 一p 0 - p ) d 2 口m 则比特差错概率的上边界为 假定采用硬判决的加性高斯白噪声信道，图2 6 给出了码率为1 2 ，约束长度分别为 k = 3 、5 、7 的卷积码的误比特率曲线。 如图2 6 所示，随着约束长度的增加，卷积码的纠错能力不断增强。 力啄尾 。 d 肘 东南大学硕士学位论文 第二章纠错编码体制 图2 6 部分卷积码的误比特性能( 高斯自噪声倍道) 2 2 纠错密码技术 2 2 。1 m 公钥体制 1 9 7 8 年，m e e l i e c e 发表了一个基于代数编码理论的新的公钥密码体制 【1 】【3 】 1 5 】【17 】。这个系统利用了一种拥有快速译码算法的线性纠错码g o p p a 码 16 】。其 思想是构造一个g o p p a 码并将其伪装成普通的线性码。虽然解g o p p a 码有一种快速算 法，但是要在线性二进制码中找到一种给定大小的代码字则是一个n p 完全问题。虽然 纠错码是线性的，但m 加密方案却不是线性的。下面给出该算法一般描述： 令d h ( x , n 表示x 和y 之间的汉明距离，数厅，k 和t 是系统参数。 私钥由三部分组成：g 是一个能纠t 个错的k ”阶g o p p a 码产生矩阵；p 是胛行阶 置换矩阵；s 是k x k 阶非退化矩阵。公钥是k n 阶矩阵g = s g p 。明文是k 位的串， 以g f ( 2 ) 上的k 维向量表示。 加密消息时，随机选择一a f ( 2 ) 上的疗维向量z ，其汉明距离小于或等于t 。 c = m g + z 解密时，首先计算c 1 = c p 一。然后用g o p p a 码的解码算法寻找m ，使之满足 d 。= ( 所g ，一) 小于或等于t ；最后计算m = m s 。 在m c e l i e e e 最初的论文中，m c e l i e e e 建议取n = 1 0 2 4 ，t = 5 0 ，t = 5 2 4 。这是要达到安 全要求的最小值。 醉时嚣 东南大学硕士学位论文第二章纠错编码体制 文献【1 】中详细分析了m 公钥体制的一般安全性及其在有扰信道中的性能。指出， 若用求解线性方程组得方法破译，计算复杂度 c 0 = o ( k 3 ( _ 二 广) 以一f m 公钥体制是一个仿射型的密码体制，它的安全性取决于随机序列z 及其重量“ 若t - - - o ，由上式知m 公钥可以很快被破译。为了使m 公钥安全，必须选取t 足够大， 一般大于5 0 ，这样就使得g o p p a 码的译码器很复杂，且译码时间很长。另一方面，从 仿射型密码体制的性质可知，若z 是一固定的糟重，则可以由两组已知的明文密文对， 以及该两组明文和密文对很快求得z ，从而破译该体制。因此在m 公钥体制中必须有 一个能产生完全随机，且重量为f 的z 序列产生器，对每一信息组产生不同的z ，因而 使加密器较复杂。 对朋体制的攻击思想主要有以下几种： ( 1 ) 直接获取生成矩阵g 对一个加密矩砗g ，若存在一个k _ j 可逆矩阵& 甩 阶置换矩阵p ，密码分析者 知道其快速译码算法的码c 的生成矩阵g ，且g = s g p 。若这种情况发生，m s 钥密码体 制就可被攻破。但在有限域g f ( 2 ) 中有大约二f 个不同的，次既约多项式，力元集合l 有挖： 不同的次序，对于任一个t 次既约多项式和n 个元素取定次序，都存在一个g o p p a 码的生 成矩阵g 。这说明，当埘，f 都很大时，通过搜索g 来