搜索
编码与信息安全理论邢藏菊xingcj@mail.buct.edu.cn信源信源编码保密编码信道编码调制器信道信宿信源解码保密解码信道解码解调器噪声通信系统模型本课程的主要内容•研究纠错编码理论和基本的编译码算法–差错控制基本概念–线性分组码–循环码–卷积码•密码学–秘密学基本概念–对称密码体制–公钥密码体制•教材–信息论、编码与密码学，RanjanBose著，武传坤译，机械工业出版社，2005年。–纠错编码原理和应用，张宗橙，电子工业出版社，2005年。–现代密码学，杨波，清华大学出版社，2007年。•成绩评定–平时成绩30％＋期终考试70％•考试时间–16周三（12月15日）1差错控制基本概念数据信号在传输过程中不可避免地会发生差错，即出现误码。造成误码的原因主要有两个方面：一是信道不理想造成的符号间干扰(可以通过均衡方法予以改善以至消除)；二是噪声对信号的干扰差错控制消除一、差错分类差错可以分为两类：随机差错——产生的原因：随机噪声突发差错——产生的原因：脉冲噪声随机差错又称独立差错，它是指那些独立地、稀疏地和互不相关地发生的差错。（存在这种差错的信道称为随机信道或无记忆信道）突发差错是指一串串，甚至是成片出现的差错，差错之间有相关性，差错出现是密集的。（存在这种突发错误的信道称为突发信道或有记忆信道）例：数据序列101100011101××××××××这一串为突发差错（中间可能有不错的码）讨论：实际信道是复杂的，所出现的错误也不是单一的，而是随机和突发差错并存的，只不过有的信道以某种错误为主而已，这两类错误形式并存的信道称为组合信道或复合信道。二、差错控制的基本思路在发送端被传送的信息码序列的基础上，按照一定的规则加入若干“监督码元”后进行传输，这些加入的码元与原来的信息码序列之间存在着某种确定的约束关系。在接收数据时，检验信息码元与监督码元之间的既定的约束关系，如该关系遭到破坏，则在接收端可以发现传输中的错误，乃至纠正错误。信息码+监督码=码组称差错控制编码或纠错编码或信道编码（加的监督码越多，差错控制能力越强）三、差错控制方式差错控制方式一般可以分为四种类型：•检错重发（ARQ）•前向纠错（FEC）•混合纠错检错（HEC）•信息反馈（IRQ）1、检错重发或叫自动反馈重发（ARQ）（1）思路这种差错控制方式在发送端对数据序列进行分组编码，加入一定多余码元使之具有一定的检错能力，成为能够发现错误的码组。接收端收到码组后，按一定规则对其进行有无错误的判别，并把判决结果（应答信号）通过反向信道送回发送端。如有错误，发送端把前面发出的信息重新传送一次，直到接收端认为已正确接收到信息为止。（2）重发方式在具体实现检错重发系统时，通常有3种形式：•停发等候重发•返回重发•选择重发停发等候重发返回重发选择重发原理：停发等候重发返回重发选择重发发送方式停止等待发送连续发送连续发送传输效率最低比较高最高控制方法简单比较简单比较复杂缓冲存储器发送端有发送端有发送和接收端都要求有成本低比较低比较高讨论：(a)三种重发方式的比较(b)ARQ还可以有混合发送方式，它是将等候发送与连续发送结合起来的一种形式。发送端若连续发送多个码组以后，还未收到收端的应答信号，就要停下来等候。(其目的是要进行流量控制。)（3）ARQ的优缺点需反向信道，实时性差。编码效率较高。译码设备较简单。2、前向纠错（FEC）（1）思路前向纠错系统中，发送端的信道编码器将输入数据序列变换成能够纠正错误的码，接收端的译码器根据编码规律检验出错误的位置并自动纠正。（2）优缺点不需要反向信道，实时性好。其缺点是所选择的纠错码必须与信道的错码特性密切配合，否则很难达到降低错码率的要求；为了纠正较多的错码，译码设备复杂。要求附加的监督码也较多，传输效率较低。3、混合纠错检错（HEC）（1）思路–混合纠错检错方式是前向纠错方式和检错重发方式的结合。在这种系统中，发送端发出同时具有检错和纠错能力的码，接收端收到码后，检查错误情况，如果错误少于纠错能力，则自行纠正；如果干扰严重，错误很多，超出纠正能力，但能检测出来，则经反向信道要求发端重发。（2）优缺点–混合纠错检错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷。4、信息反馈（又称回程校验（IRQ））（1）思路–接收端把收到的数据序列全部由反向信道送回发端，发端比较发送的数据序列与送回的数据序列，从而发现是否有错误，并把认为错误的数据序列的原数据再次传送，直到发端没有发现错误为止。（2）优缺点–不需要纠错、检错的编译码器，设备简单。–缺点是需要和前向信道相同的反向信道，实时性差。–发送端需要一定容量的存储器以存储发送码组，环路时延越大，数据速率越高，所需存储容量越大。讨论：四种差错控制方式中:不需反向信道的是FEC实时性最好的是FEC实时性最差的是IRQ不需要纠错、检错编译码器的是IRQ（1）传1位码发1误0收端不知道是否有误码0误1无纠检错能力一、差错控制的基本原理例：要发送两个消息（2）传2位码发11误1000误或01可检错一位2检错和纠错（3）传3位码发111000①收、发两端约定：当收到两个以上的“1”（即011、101、110、111），认为发端发的是111；当收到两个以上的“0”（即001、010、100、000），认为发端发的是000。此时可纠错1位②发111（或000）误110等可能是111误成110，也可能是000误成110。此时最多可检错2位讨论：(a)纠错编码之所以具有检错和纠错能力，是因为在信息码之外附加了监督码。监督码不载荷信息，它的作用是用来监督信息码在传输中有无差错，对用户来说是多余的，最终也不传送给用户，但它提高了传输的可靠性。即码的纠检错能力是靠信息的冗余度换取的。信息码+监督码=码组k+r=n•CODNGTHEORYISANINTERESTNGSUBJECT•CODINGTHEORYISANINTERESTINGSUBJECT二、码距与检错和纠错能力1、几个概念•码组的重量——在信道编码中，定义码组中非零码元的数目为码组的重量，简称码重。–例：11010码组的码重为3•码距——把两个码组中对应码位上具有不同二进制码元的位数定义为两码组的距离，简称码距，汉明距离。–例：1101010001码距为3•最小汉明距离——在一种编码中，任意两个许用码组间距离的最小值，即码组集合中任意两元素间的最小距离，称为这一编码的最小汉明距离，以表示。mind例：一码组集合31011131100142000102311010此码组集合的最小汉明距离=22.最小汉明距离与检错和纠错能力的关系:（1）(e为检错个数)用于检错重发ARQ（2）(t为纠错个数）用于FEC（3）（et）用于HEC（又检又纠）1mined12mintd1minted讨论：↑→检错和纠错能力↑例：设=4，检错和纠错能力如何？用于ARQ，最多能检错3位用于FEC，最多能纠错1位用于又检又纠，能检错2位，纠错1位若设=3，检错和纠错能力如何？用于ARQ，最多能检错2位用于FEC，最多能纠错1位不能同时用于又检又纠。设=6，检错和纠错能力如何？用于ARQ，最多能检错5位用于FEC，最多能纠错2位用于又检又纠，能检错3位，纠错2位三、纠错编码的分类从不同的角度出发，纠错编码可有不同的分类方法。（1）按码组的功能分——有检错码和纠错码两类。（2）按码组中监督码元与信息码元之间的关系分——有线性码和非线性码两类。线性码是指监督码元与信息码元之间的关系呈线性关系，即可用一组线性代数方程联系起来；非线性码指的是二者是非线性关系。（3）按照信息码元与监督码元的约束关系——可分为分组码和卷积码两类。•分组码是监督码元仅监督本码组中的码元，或者说监督码元仅与本码组中的信息码元有关。•在卷积码中，每组的监督码元不但与本码组的信息码元有关，而且还与前面若干组信息码元有关，即不是分组监督，而是每个监督码元对它的前面若干组码元都实行监督，前后相连，因此有时也称为连环码。例：卷积码（4）按照信息码元在编码前后是否保持原来的形式不变——可划分为系统码和非系统码。（5）按纠正差错的类型——可分为纠正随机错误的码和纠正突发错误的码。（6）按照每个码元取值来分——可分为二进制码与多进制码。一、奇偶监督码（r=1，k不一定）1、概念偶监督码——信息码与监督码合在一起“1”的个数是偶数奇监督码——信息码与监督码合在一起“1”的个数是奇数信息码监督码3简单的差错控制编码0110naaa1210naaaa1110naaa11210naaaa2、监督方程偶监督方程或奇监督方程或（4-7）（4-8）（4-9）（4-10）例：10110111（偶）监督码0（奇）收端根据监督方程是否满足可判断是否有误码3、检错能力（1）只能检测奇数个错误，而不能检测出偶数个错误。（2）适合检测随机差错。讨论：(a)奇偶监督码“0”的个数是多少？不一定(b)dmin=2例：100111（偶监督）101110信息码监督码(c)奇偶监督码属于线性分组码，它是检错码。二、水平奇偶监督码1、构成思路将经过奇偶监督编码的码元序列按行排成方阵，每行为一组奇偶监督码，但发送时则按列的顺序传输，接收端仍将码元排成发送时方阵形式，然后按行进行奇偶校验。•例：数据序列1101101011101001……（设每4位码元为一组）发送的数据序列为：11111010011010011010……（以偶监督为例）按列发送监督码*11011*10100*11101*100102、检错能力（1）可发现某一行上所有奇数个错误。（2）能检测出所有长度不大于方阵中行数的突发错误。讨论：水平奇偶监督码属于线性分组码，它是检错码。例：某系统采用水平奇监督码，其信息码元如下表，试填上监督码元，并写出发送的数据序列，这样的发送数据序列能检测突发差错的长度最大为多少？信息码元监督码元1000011101000100001011010011011110011000110011101101100发送的数据序列为：1011100111000100110000001100111011110100010011010101100能检测突发差错的长度最大为5三、二维奇偶监督码（又称行列监督码、方阵码或水平垂直奇偶监督码）1、思路二维奇偶监督码是将水平奇偶监督码推广而得。它的方法是在水平监督基础上对方阵中每一列再进行奇偶校验（即将数据序列排成方阵，每一行每一列都加奇或偶监督码），发送按列（或行）的顺序传输。接收端仍将码元排成发送时方阵形式，然后每一行每一列都进行奇偶校验。例：数据序列1100101011101001……（设每4位码元为一组）11000（以偶监督为例）按列发送10100111011001000011监督码监督码发送的数据序列为（按列的顺序传输）：1111010100011000001100101……2、检错能力（1）可发现某行或某列上奇数个错误。（2）能检测出所有长度不大于方阵中行数（或列数）的突发错误。（3）能检测出偶数个错误。但若偶数个错误恰好分布在矩阵的四个顶点上时，这样的偶数个错误是检测不出来的。（4）可以纠正一些错误，当某行某列均不满足监督关系而判定该行该列交叉位置的码元有错，从而纠正这一位上的错误。（可纠正只发生在某一行或某一列的奇数个错误）讨论：二维奇偶监督码属于线性分组码，它可能是检错码，也可能是纠错码。例1：某系统采用水平垂直偶校验码，试填出下列矩阵中5个空白码位。010110101110000（）000（）110010（）111010000（）01（）010110101110000（1）000（0）110010（1）111010000（1）01（0）解：例2：如果水平垂直奇偶校验码中的码元错误情况如下图所示，试问能否检验出来？解：不能检验出来4线性分组码示例－汉明码汉明码是1950年由美国贝尔实验室提出来的，是第一个设计用来纠正错误的线