校验算法（共7篇）
校验算法 篇1
摘要：IP协议为提高数据传输效率,简化了协议,舍弃了许多为提供可靠性所需要的工作(如建立连接、维护连接、拆除连接、确认应答、时间片处理等)。其唯一的正确性检验即依靠头部校验和,以保证头部数据的完整性。为了研究IP首部校验算法,查看了相关的RFC文档并利用wireshark工具进行了抓包,并对抓包取得的数据进行了计算验证。研究发现了一些算法存在一定的问题并对它的改进算法进行了研究。
关键词：IP,头部校验和,算法,验证
1 IP首部
如图1所示,IP数据报首部的固定部分中的各字段:1)版本占4位,指IP协议的版本。
2)首部长度占4位,可表示最大十进制数值是15。
3)区分服务占8位,用来获得更好地服务。总长度总长度是指首部和数据之和的长度。
4)标识占16位,IP软件在存储器中维持一个计数器,每产生一个数据报,计数器就加1,并将该值赋给标识字段。
5)标志占3位,但目前只有两位有意义。MF=1还有分片DF=1不能分片
6)片偏移占13位。片偏移指出较长的分组在分片后,某片在分组中的相对位置。
7)生存时间占8位,表明数据报在网络中的寿命
8)协议占8位,指出此数据报携带的数据时使用何种协议
9)首部检验和占16位。这个字段只检验数据报的首部但不包括数据部分
10)源地址32位
11)目的地址32位
2 IP校验和算法
2.1 发送方
1)将校验和字段置为0,然后将IP包头按16比特分成多个单元,如包头长度不是16比特的倍数,则用0比特填充到16比特的倍数;
2)对各个单元采用反码加法运算(即高位溢出位会加到低位,通常的补码运算是直接丢掉溢出的高位),将得到的和的反码填入校验和字段;
3)发送数据包。
2.2 接收方
1)将IP包头按16比特分成多个单元,如包头长度不是16比特的倍数,则用0比特填充到16比特的倍数;
2)对各个单元采用反码加法运算,检查得到的和是否符合是全1(有的实现可能对得到的和会取反码,然后判断最终值是不是全0);
3)如果是全1则进行下步处理,否则意味着包已变化从而丢弃之.需要强调的是反码和是采用高位溢出加到低位的,如3比特的反码和运算:100b+101b=010b(因为100b+101b=1001b,高位溢出1,其应该加到低位,即001b+1b(高位溢出位)=010b)
2.3 校验和源码
第1个while循环是做普通加法,因为IP包头和TCP整个报文段比较短(没达到2^17数量级),所以不可能导致4字节的sum溢出.紧接着的一个判断语句是为了能处理输入数据是奇数个字节的这种情况.再接着的数据循环是实现反码算法,由反码和的高位溢出加到低位的性质,可得到"32位的数据的高位比特移位16比特,再加上原来的低16比特,不影响最终结果"这个等价运算,因为sum的最初值(刚开始循环时)可能很大,所以这个等价运算需循环进行,直到sum的高比特(16比特以上)全为0.对于32位的sum,事实上这个运算循环至多只有两轮,所以也有程序直接用两条"sum=(sum&0xffff)+(sum>>16);"代替了整个循环.最后,对和取反返回。
2.4 校验和算法特性
1)奇、偶字节可任意排列组合;2)字节顺序独立;
3)并行计算。
2.5 采取反码而不用补码的原因
1)反码和的溢出有后效性(蔓延性)
反码和将高位溢出加到低位,导致这个溢出会对后面操作有永久影响,有后效性;而补码和直接将高位和溢出,导致这个溢出对后面的操作再无影响,因此无后效性
2)反码校验无需考虑字节序
正因为反码和的溢出有后效性,导致大端字节序(big-endian)和小端字节序(little-endian)对同一数据序列(如两个16比特的序列)产生的校验和也只是字节序相反,而补码和因为将溢出丢掉了,不同字节序之间的校验和大不相同且没什么联系。
2.6 wireshark抓包验证算法
如图2所示。
3 增量式修改校验和的加速算法
在实际的应用中,存在对收到的数据包进行修改若干个地方,并回送至发送方或者转发的情况。此时需要重新计算数据包的检验和。最常见的可能就是将收到的数据包的TTL字段减1,并转发的情况。如果仍旧按照传统的计算检验和的方式进行计算,特别是当数据包长度很大时,为了重新计算校验和而将整个数据包的数据遍历一边,反码求和,效率肯定比较低。为提高转发效率,要求重校验算法尽可能快,故出现了如下所示的重校验算法:
算法的实现依据是这样的.假设包头原校验和为~C,改变的字段的原始值是m,更改后的值是m',设~C'为重校验和,RFC1017中给出~C'=~(C+(-m)+m')=~C+(m-m'),但由于该式不是更新的校验和的反码,而且反码减法运算在机器内较难实现,于是RFC1141给出适合在机器内运算的式子~C+m+~m',该等价关系的成立基于反码的运算性质:取反运算满足结合律,按位取反运算与符号取反(及相反数)是等价的(即~C=-C)。
4 可能存在的问题及其解决
4.1 存在的问题
RFC1071和1141所提出的增量式修改校验和有一个BUG,就是按照公式计算新的检验和时,有可能出现计算结果为0XFFFF的情况,则意味着数据包中所有部分相加的结果为0x0000。这是不可能的。
例如:
一个IP包头16位域m=0x5555变为m’=0x3285.包头其它部分反码和为0x CD7A.
HC旧的检验和HC'新的检验和
m某个域(16-bit字)修改前的值
m'某个域修改后的值
包头校验和是:
如用RFC1141给出的公式~C'=~C+m+~m'
与不用加速算法计算出的结果不一样
4.2 问题解决
1)RFC1141里规定:对于更新了的头校验值为+0时,它会改为-0,因为它假定反码有一个分布式的属性,当结果为0时它不会一直保持不变
2)RFC1624里假定上面的属性成立从而避免了这个可能出现的问题,正确的等式如下HC’=~(C+(-m)+m’)HC'=~(C+(-m)+m')=~(0x22D0+~0x5555+0x3285)=~0x FFFF=0x0000
参考文献
[1]Borman D,Research C,Partridge C.Computing the Internet checksum[S].RFC1071,1988.
[2]Mallory T,Kullberg A.Incremental updating of the Internet checksum[S].RFC1141,1990.
[3]Rijsinghani A.Computation of the Internet checksum via incremental update[S].RFC1624,1994.
[4]谢希仁.计算机网络[M].5版.北京:电子工业出版社,2008.
音频分析仪的校验方法 篇2
【摘要】音频是多媒体中的一种重要媒体，我们能够听见的音频信号的频率范围大约是20Hz～20KHz，其中语音大约分布在300 Hz～4KHz之内，而音乐和其他自然声响是全范围分布的。声音经过模拟设备记录或再生，成为模拟音频，再经数字化成为数字音频信号。所谓音频分析就是以数字音频信号为分析对象，以数字信号处理为分析手段，提取信号在时域、频域内一系列特性的过程。
【关键词】音频；分析仪；方法
音频分析仪是常用的音频分析设备，音频分析仪用于分析低频信号的波形特性、不平度、衰减、波形失真等性能，集中了低失真音频源的功能、高性能失真分析仪的功能、频率计数器的功能、交流电压表的功能、直流电压表和SINAD表的功能，可用于检测低频信号发生器、音频扫频仪、各种音频类滤波器及低频函数信号发生器等产品，音频分析仪的性能指标影响着产品品质和实验数据分析的准确度，因此，需要对音频分析仪的性能指标进行校验，判断其是否符合检测要求。而现有的音频分析仪的校验方法，一般具有操作较复杂，检测效率低的缺点。
下面论述的音频分析仪的校验方法，简便实用有效，它包括以下步骤：
第一步，将音频分析仪置于标准环境条件下进行校验；
第二步，对音频分析仪进行外观检查；
第三步，对音频分析仪进行基本误差校验，基本误差校验包括音频分析功能校验和音频信号发生器功能校验；
第四步，根据各误差结果，作出对音频分析仪的校验结论。
一、音频分析功能校验
音频分析功能校验包括：
1、输入电压误差校验：使用多功能校验仪校验音频分析仪的输入电压误差，按照检测调节多功能校验仪的输出，调节音频分析仪使其处于测量电平状态，使音频分析仪的电压量程在手动状态，直接从其电压显示窗中读取各个量程测量点的值，按校验点校验各量程，计算音频分析仪的输入电压误差；
2、输入频率误差校验：使用多功能校验仪校验音频分析仪的输入频率误差，调节多功能校验仪的输出频率，直接从音频分析仪的频率显示窗中读取频率，按校验点校验各量程，计算音频分析仪的输入频率误差；
3、频响特性校验：使用多功能校验仪校验音频分析仪的频响特性，调节多功能校验仪，其固定电压不变，改变其输出频率，直接从音频分析仪的电压显示窗中读取电压，按校验点校验各量程，计算音频分析仪的频响特性；
4、输入失真误差校验：使用失真度仪检定装置校验音频分析仪的输入失真误差，调节失真度仪检定装置的输出失真度，调节音频分析仪使其处于测量失真状态，直接从音频分析仪的失真显示窗中读取失真值，按校验点校验各量程，计算音频分析仪的输入失真误差；
5、滤波器特性校验，包括加权滤波器特性校验：使用多功能校验。1）仪校验音频分析仪的加权滤波器特性，调节多功能校验仪输出至加权滤波器的参考频率点，设置音频分析仪显示零分贝值，按校验点频率调节多功能校验仪频率输出，直接从音频分析仪的电平显示窗中读取加权值，按校验点校验各量程，计算音频分析仪的加权滤波器特性误差；
2）滤波器特性校验，包括带通滤波器特性校验：使用多功能校验仪校验音频分析仪的带通滤波器特性，调节多功能校验仪输出音频分析仪固有的滤波频率，设置音频分析仪显示零分贝值，调节多功能校验仪频率输出直至从音频分析仪的电平显示窗中读取-3db值，此時多功能校验仪输出的频率即为滤波频率，按校验点校验各量程，计算音频分析仪的带通滤波器特性误差。
二、音频信号发生器功能校验
音频信号发生器功能校验包括：
1、输出电压误差校验：使用标准电压表校验音频分析仪的输出电压误差，调节音频分析仪的输出，使被校仪器指在已选定的电压校验点上，并直接从标准电压表中读取这些点的实际值，计算音频分析仪的输出电压误差；
2、输出频率误差校验：使用通用计数器校验音频分析仪的输出频率误差，调节被校音频分析仪的输出，使被校仪器指在已选定的频率校验点上，并直接从通用计数器中读取这些点的实际值，计算音频分析仪的输出频率误差；
3、输出失真误差校验：使用失真仪校验音频分析仪的输出失真误差，调节音频分析仪使其处于正弦波输出状态，改变不同的频率点，直接从失真仪中读取信号的失真值，计算音频分析仪的输出失真误差。
参考文献
[1]周立青，胡爽，瞿修远，陈小桥，王琦.心音采集电子综合实验项目设计与实现[J].实验室研究与探索，2015（02）.
[2]陆毅，刘晓杰，张贵祥，朱幼莲，罗印升.基于MSP430的信号波形合成实验设计[J].实验室研究与探索，2013（06）.
[3]王香婷，李明.国家级电工电子实验教学示范中心的建设与实践[J].实验技术与管理，2012（10）.
校验算法 篇3
在数据通信和计算机通信过程中,由于信道上各种噪声和干扰等复杂因素的影响,使接收端收到的信息与发送端发送的信息不一致,即接收端收到的信息产生了误码。用误码率(PC)来度量信道传输信息的准确度,即
PC=错误接收码元数/接收码元数。
为了尽可能地降低通信的误码率,提高数字通信的可靠性,往往要采用差错控制编码(又叫信道编码)。用差错控制编码可以发现可能产生的误码(检错码),或发现并纠正错码(纠错码)。
差错控制的目的是提高通信的可靠性。差错控制最常用的方法有三种:自动请求重发方式(ARQ)、向前纠错方式(F E C)和混合纠错方式(H E C)。其中FEC和HEC是基于纠错编码,而A R Q是基于检错编码。
FEC依赖于在发送码字中有控制地加入冗余信息。信号在噪声信道中进行传输时会产生误码现象,从而需要进行误码检测和纠正。不管接收码字的译码是否成功,接收机都不进行任何进一步处理。因此,使用于FEC的信道编码技术只要求发射机和接收机之间是单向的链接。
A R Q的基本思想完全不同于F E C。ARQ采用冗余的目的仅仅是为了进行误码检测。当在传输的码字中检测到错误时,接收机就要求重传错误的码字,这就需要使用一条返回路径(反馈信道)。因此,ARQ只能用于半双工或全双工的链路。实现检错功能的差错控制方法有很多,常用的有:奇偶校验、校验和检测、重复码检验、横比码校验、行列冗余码校验等。
HE C是F E C和AR Q的结合。
为了不破坏数据的完整性,差错控制借助于前向纠错FEC的方法来实现。图1给出了采用这种方法的数字通信系统模型。离散信源产生二进制的信息,发射几种的信道编码器收到比特信息后,按照指定的规则加上冗余发送到接收端。接收机中的译码器对收到的数据进行误码检测和纠错。
循环冗余校验CRC是由分组线性码的分支而来,其主要应用是二元码组。由于检错能力强,误判概率很低等优点,被广泛应用于工业测控和数据通信领域。下面重点介绍CRC校验的原理、算法分析,及其C++源程序设计。
2 CRC算法原理
C R C码是一种线性、分组的系统码。在K位信息码之后再拼接R位的校验码,整个编码长度为N位,因此,这种编码又叫(N,K)码。CRC校验采用多项式编码方法,被处理的n比特的数据块可以看作是一个n-1阶的二进制多项式。例如一个8比特的二进制数10111001可以表示为:x7+x5+x4+x3+1。多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模,加减时不进、借位,和逻辑异或运算一致。
模2除步骤如下:
1)用除数对被除数最高几位做模2减,没有借位。
2)除数右移一位,若余数最高位为1,商为1,并对余数做模2减。若余数最高位为0,商为0,除数继续右移一位。
3)一直做到余数的位数小于除数时,该余数就是最终余数。
对于一个给定的(N,K)码,可以证明存在一个最高次幂为N-K=R的多项式G(X)。根据G(X)可以生成K为信息的校验码,而G(X)叫做这个CRC码的生成多项式。
假设待发送的K位信息多项式用C(X)表示,将C(X)左移R位,则可表示为C(X)*2R,这样C(X)的右边就会空出R位,这就是校验码的位置。通过C(X)*2R除以生成多项式G(X)得到的余数就是校验码。Q(X)为商,R(X)为余数。即
在发送端发送信息时,将校验码R(X)加到信息码C(X)之后一同发出。并将这时发出的信息称为T(X)码,其码元形式如下。T(X)正好能被G(X)整除。
接收方收到信息码为T’(X)。如果传输中未发生错误,则接收码T’(X)与发送码T(X)相同,故能被G(X)整除;如果传输中发生错误,则接收码T’(X)与发送码T(X)不相同,且不能被G(X)整除。因此,我们就以T’(X)除以G(X)的余数是否为0来判断接收码元中是否有错误。也有可能收到的错误码元除以G(X)余数为0,这种问题是CRC所不能解决的,只能通过选择G(X)和增加冗余位来降低这种错误的概率。
3 CRC算法分析
C RC码是用待发送的二进制数据C(X)左移R位,然后除以生成多项式G(X),得到的余数就是CRC码。CRC码的具体生成步骤如下:
1)将x的最高幂次为R的生成多项式G(X)转换成对应的R+1位二进制数。
2)将待发送的二进制数据C(X)左移R位,相当于对应的信息多项式C(X)*2R。
3)用生成多项式(二进制数)对信息码做模2除,得到R位的余数R(X)。
4)将余数拼接到信息码左移后空出的位置,得到完整的C R C码。
例如,假设使用的生成多项式是G(X)=x3+x+1,4位的原始报文为1 0 1 0,求编码后的报文。
解的过程如下:
1)将生成多项式G(X)=x3+x+1转换成对应的二进制数1011.
2)生成多项式有4位,要把原始报文C(X)左移3位变为1010000.
3)用生成多项式对应的二进制数对左移3位后的原始报文进行模2除。
4)得到余数0 1 1,即校验码。
5)编码后的报文(C R C码)为1010011
通过CRC编码规则可以看出,CRC编码实际上是将待发送的K位二进制数据C(X)转换成了可以被生成多项式G(X)除尽的K+R位的二进制多项式C(X)*2R,所以,解码时,可以用接收到的数据除以G(X),如果余数为0,则表示传输过程没错误,如果余数不为0,则表示传输过程肯定存在错误。解码时,将接收到的二进制数据去掉尾部的R位数据,得到的就是原始的二进制数据信息。
4 CRC算法性能分析
生成多项式的选取会影响检错纠错的性能。生成多项式应该满足下列要求:任何一位发生错误都应使余数不为0;不同位发生错误应当使余数不同;应满足余数循环规律。
生成多项式的幂次越高,其检错能力越强。若生成多项式G(X)的最高幂次为R,则该C R C校验码的检错性能如下:
1)可检测出所有奇数个错误。
2)可检测出所有单个突发错误。
3)可检测出所有两个错误。
4)可检测出所有长度小于等于R个比特的突发错误。
5)对于长度等于R+1个比特的突发错误,其漏检率仅为1/2 r-1。
6)对于长度大于等于R+1个比特的突发错误,其漏检率仅为1/2r。
CRC码具有良好的检错能力,因而在工业测控和数据通信领域得到了广泛的应用。下面是已经成为国际标准的CRC码生成多项式:
CRC—16为美国采用,而CRC—CCITT为欧洲国家所采用,CRC—32大都被采用在一种
称为Point-to-Point的同步传输中。在实际应用,可根据需要来选用相应的生成多项式。
5 结束语
CRC校验由于实现简单,纠错能力强,被广泛应用于各种数据校验场合及工业测控领域。本文阐述了CRC的校验原理及算法性能分析,并给出了用C++实现的CRC-14源程序,已在PC机上验证通过。并且中科院国家授时中心“BPL长波授时系统现代化改造项目”中,用到了CRC编码技术。用软件实现的CRC不仅可以降低成本,还可广泛应用于微机及各种数据通信领域,为系统长期稳定运行提供了可靠保障。
摘要：在数据通信与网络中,为了尽可能地降低通信的误码率,提高数字通信的可靠性,可以采用一种循环冗余校验码CRC(Cyclic Redundancy Check),简称循环码或CRC码。由于它是一种编码简单,且高效、可靠的差错控制方法,检错能力强,误码概率低,因而被广泛应用于工业测控及数据通信领域。本文阐述用循环冗余校验CRC进行差错控制的原理,CRC算法分析及CRC算法的C++程序设计方法。
关键词：循环冗余校验,CRC算法,差错控制
参考文献
[1]李永忠,苏惠娟.CRC在数据通信中的应用及软件实现.西北民族学院学报.1998.19(1)
[2]李寿强.循环冗余校验CRC的算法分析及其实现方法.成都电子机械高等专科学校学报.2003年第4期
[3]瞿中告,袁威,徐问之.CRC算法在计算机网络通信中的应用.微机发展.2002年第2期
基于多次查表的循环冗余校验算法 篇4
循环冗余校验CRC(Cyclic Redundancy Check)编码简单且误判概率很低,在通信系统中得到了广泛的应用。
其根本原理是通过校验算法增加数据的冗余量,将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验,再将得到的校验码和接收到的校验码比较,如果二者一致则认为传输正确。
1 传统CRC校验算法
CRC校验算法使用的是多项式除法。使用异或运算,不进位,不借位。
计算机使用软件方法实现CRC校验,传统算法是按位计算CRC。下面以CRC-4为例,介绍算法流程。CRC-4的生成多项式为g(x)=x4+x+1,即10011。待发送的数据t(x)是一个8位二进制数据10111010。首先在t(x)的末尾添加4个0,t(x)就成了101110100000。然后用g(x)去除t(x),不用管商是多少,只需要求得余数即可。
算法流程见图1。
1100就是余数,也就是10111010的CRC校验码。
传统CRC校验算法简单,容易实现,对任意长度生成多项式的g(x)都适用。在发送的数据不长的情况下可以使用。但是如果发送的数据块很长的话,这种方法就不太适合了。因为它一次只能处理一位数据,效率太低。
2 基于查表的CRC校验算法
为了提高处理效率,可以预先计算好n位被除数所对应的余数,校验时只需要查表即可。这样就可以一次处理n位数据了。
下面以查4位表为例,如图2,介绍查表法。
生成多项式仍然为10011。待发送数据仍然是10111010。数据前4位1011查表得到余数1110,将余数1110与数据后4位1010异或得0100,再查表0100的余数是1100。因此10111010的余数就是1100。
经过验证,查表法与传统CRC算法得到的校验码相同。
3 基于多次查表CRC校验算法
一个8位的CRC-16余数表(存储着256个余数)占用512个字节的空间,一个16位的CRC-16余数表将占用128KB的空间,而一个32位的余数表将占用8GB。这些空间对于低成本的设备而言是非常巨大的开销,所以一般来说我们最多查8位的余数表。
多项式除法有个非常简单的性质:
(P(X)XOR Q(X))的余数==P(X)的余数XOR Q(X)的余数
举个例子:
P(X)=10110000 Q(X)=1010
P(X)的余数是0001 Q(X)的余数是1101
P(X)XOR Q(X)=10111010的余数就是0001 XOR 1101=1100。
也就是说,可以针对8位数据的高4位和低4位各自建立一个4位的余数表,即可算出8位数据的余数。
根据上述性质,我们就可以把一个32位的表,变成4个8位的余数表。分别查4张表,以代替查一张32位的大表,节省了大量的空间。
查4张8位的余数表与查一张8位余数表的方法相比,查表的次数是相同的,但是可以有效解决异或运算时数据对齐的问题,而且可以减少异或运算和访问存储器的次数。
4 三种算法的测试比较
相对于后两种查表算法,传统CRC算法的实现对编程要求最高。为数据对齐而采取的移位操作和异或运算的时机以及对内存的读写,都将决定算法的效率。
测试条件:
1)测试平台是PC机,CPU酷睿2 T6600,WindowsXP。
2)对30个字节的待发送数据采用CRC-16进行校验。
3)查表法使用8位的余数表,也就是占用了512 BYTE的空间。
4)二次查表法使用了2个8位的余数表,占用1024 BYTE的空间。
测试结果:
1)查表法的效率是传统CRC算法的7～8倍。
2)二次查表法的效率是传统CRC算法的10～12倍。
结果分析:
1)使用查表的方式进行CRC校验,确实可以提高效率。
2)多次查表与普通查表相比,是空间换时间的方法,速度有所提高。
3)测试的算法是本人使用C++高级语言编写的,虽然做过认真优化,但是性能肯定不能与汇编语言相比。如果用汇编语言改写,那么三种算法在PC机上的性能可能都有提高。
参考文献
电子式互感器校验仪的算法研究 篇5
随着电力系统的容量和传输电压等级的增大, 传统的电磁式互感器呈现出一些缺陷, 如绝缘问题、电磁干扰问题、体积大造价高问题, 电磁式互感器已经不能满足当代电力工业的发展要求。电子式互感器能很好地解决电磁式互感器的缺点, 电子式互感器替代电磁式互感器是电力系统的发展方向。由于电子式互感器结构的特殊性, 难以应用电磁式互感器校验装置进行校验, 因此电子式互感器校验方法及其装置的研究一直是国内外的研究热点。
目前常用的电子式互感器校验方法是数字校验法, 该方法借助数据采集装置将标准电磁式互感器和待测电子式互感器输出信号读入计算机, 通过软件分析得出电子式互感器的精度等级[1]。这种方法是采用傅里叶变换求取各路采集信号的基波分量, 但由于电网信号的频率具有波动性, 用傅里叶变换求基波分量产生了较大的误差, 这不利于校验过程的实时实现。
据此, 本文提出一种新型校验方法, 基于DFT算法和准同步算法相结合进行信号基波分量的提取, 两者的结合有效解决了因电网频率波动而导致的非同步采样对校验结果的影响的问题, 论文最后的实验结果验证了该方法的有效性和高效率。
1 电子式互感器校验系统的构造与设计
为克服电源频率不稳带来的误差, 电子式互感器校验一般采用比较法原理, 如图1:被测电子式互感器和参考电磁式互感器串联在同一条回路上, 通过调节输入电流大小进行测试。信号经A/D采样装置, 采集到DSP中进行处理。本装置用的DSP芯片是TMS320F206, 采样芯片用MAX125。通过A/D采集的标准信号和待测信号利用校准算法可计算出信号的基波分量, 进而得到待测电子式互感器的精度指标。
2 检验算法的研究
国家标准规定电网频率可在49.5~50.5 Hz之间波动, 若不进行信号频率的实时测量, 并且仍然按照固定采样率采样的数据进行傅里叶变换以求取基波分量, 则校验精度将受到很大影响。因此, 本文提出DFT算法和准同步算法相结合进行基波分量的提取, 以解决电网频率波动而带来的问题。
2.1 DFT算法设计
研制的电子式互感器校验仪为了配合所研制的电子式互感器的时序, 采用的是一个周期内固定采集26个点的采样方式。对于每周期26点的DFT算法, 我们可以把它分解成2×13个点, 进行DFT计算。DFT算法化简是根据系数WNnK的周期性和对称性, 化简后可以提高算法的效率。
2.2 准同步算法的基本原理
对于一个周期为T的周期函数f (t) , 它的平均值为, 其中t是积分起点。若在一周期内等分成N段, 由梯形求积公式可知:
如果增加N的值, 可以使f (t) 的平均值达到很高的精度, 这就是准同步采样的基本原理[2]。如果区间长度不是T而是T±Δ, Δ为波动误差, 则由式 (1) 计算的f (t) 的平均值与f (t) 真正的平均值之间存在一定的误差。如果通过提高每周期的采样次数, 再用DFT算法分析, 这样增加了计算量, 并且误差随波动误差Δ的增加而增加, 所以增加采样次数很难达到目的。而准同步采样在允许不大的误差Δ存在的情况下, 通过适当增加采样区间来消除非同步误差带来的影响。
假设被测信号f (t) 处于稳定状态, 将宽度为n× (T+Δ) 的积分区间[t0 t0+n× (T+Δ) ]等分为n×N段, 由此得到n×N+1个采样数据f (ti) (i=i0, i0+1, …, i0+n×N) , 有如下定义式:
经过n层递推运算, F1n可以最终表示为如式 (4) 所示的形式, ai为权系数。在式 (2) 和式 (3) 中, ρi (i=i0, i0+1, …, i0+n×N) 为对应的数值求积公式所确定的权系数, 一般通过复化梯形求解, c为递推计算所在的层数, k为序号, k=1, …, (n-c) ×N+1, 从公式中可以看出, 从第1层到第n层的递推计算中各层中的F的个数是逐渐以N为公差递减的, 这样, 可以计算出系数ai。在实际运用中, n=4已经可以达到很高的精度要求, 本算法取n=4, N=26, 所以, 采样26×4+1=105个点。计算出准同步窗函数的表达式为:
再把窗函数归一化, 就可以得到准同步窗, 对存在采样误差的原始数据进行加窗处理, 就实现了对数据的准同步化处理。
2.3 DFT算法和准同步算法相结合
当电网频率波动时, 若采用固定采样率采样, 会导致非整周期采样的情况出现, 如图2。
因此, 若对采样数据按离散傅里叶变换进行处理必然会带来误差, 并且随着误差的增加而增加, 因此, 用准同步算法进行校正是有必要的。我们用DFT算法和准同步算法相结合来对信号实现高精度的分析。由DFT可知道, 系数:
, 令g (t) =f (t) cos (kwt) , 由式 (1) 可以知道, 所以, 因此, 只要精确求出, 就可以精确的求出ak的值。
如果把所采样的105个点进行加准同步窗处理后, 再用DFT计算。所以可以得到DFT与准同步算法结合的谐波分析公式 (5) , (6) :
其中:N, n, η, , W都是常数或已经求出, 所以, ak、bk可以通过采样值fi乘以相应系数再累加的方法得到。这样就可以实现对信号的高准确度分析。
3 实验结果
利用DFT算法和准同步算法相结合后对信号的分析精度比普通的DFT算法对信号分析的精度要高许多。我们的实验如下:
假定信号的表达式为:
, 其中, A=1, a1到a20全部取2, f0取49.5~50.5 Hz, 把这个信号分别用准同步算法与DFT算法相结合和普通DFT算法进行检测分析, 在准同步算法中, n=4, N=26, 国家标准规定, 公用电网谐波次数最多考虑到20次, 因此我们也就考虑在20次以内的谐波影响下的本文所提的算法精度。比较结果如表1所示。
实验测试结果表明, DFT算法和准同步算法相结合后的测量精确度比普通的DFT算法的测量精确度提高了近20倍, 校验的精确度得到了很大的提高。并且加入准同步算法后, 电子式互感器校验系统的实验精确度可以满足0.05级[3]的国家标准精度要求。
在此系统中, 我们分析发现, A/D采样环节的量化误差比较大, 为改善系统的精确度, 改善A/D采样环节的量化误差是提高系统精度的最好方法, 为此, 在做硬件电路时, PCB布局的优化可以大大降低这种量化误差。
4 结论
国家标准规定电网频率可在49.5~50.5 Hz之间波动, 电网的波动会使采样不能严格同步, 在对电子式互感器的高精度测量中为解决这个问题, 本文提出了DFT算法和准同步算法相结合的基本原理来对电子式互感器进行校验。最后, 我们设计了实验, 对该方案进行了验证。实测结果表明基于所提校验方法的校验装置的精度满足0.05级电子式互感器的国家校验精度要求, 为以后的研究提供了很好的理论依据。
参考文献
[1]钱政, 李童杰, 张翔.电子式互感器校验方法的设计与实现[J].北京航天航空大学学报, 2006.QIAN Zheng, LI Tong-jie, ZHANG Xiang.Design and Realization of Calibration Method of Electronic Transformer[J].Journal of Beijing University of Aeronautics and Astronautics, 2006.
[2]张盎然, 陈明华, 杨扬.基于准同步算法的谐波分析方法[J].电测与仪表, 2002.ZHANG Ang-ran, CHEN Ming-hua, YANG Yang.An Approach of Analyzing Harmonics Based on Quasisynchronous Algorithm[J].Electrical Measurement&Instrumentation, 2002.
校验算法 篇6
关键词：LDPC码,残余,置信传播
一引言
低密度奇偶校验 (Low-density Parity-check) 码可以实际应用, 性能接近Shannon极限的纠错编码, 对于现在的无线通信有着至关重要的作用。本文研究的VC-RBP译码算法与RBP译码算法相比, 具有优良的误码率性能, 复杂度较低, 同时具有快速译码的性能, 不同之处在于残留信息的计算。RBP算法的残余信息的计算在校验节点传向变量节点信息更新前后, 而VC-RBP算法的残余信息的计算在变量节点传向校验节点信息更新前后。
二具有准循环特性的LDPC码
尽管LDPC码相对Turbo码有较好的性能和较低的译码复杂度, 但编码却较复杂。Turbo码能在线性时间内编码, 而LDPC码编码器的时间复杂度与码长成二次方。为了降低LDPC码编码复杂度, IEEE802.16e给出一种具有准循环特性的LDPC码 (QC-LDPC) 监督矩阵。IEEE 802.16e标准中规定的LDPC编码规则:H矩阵是由块矩阵组成的。每个块矩阵都用一个数字来表示, 而当这个数字大于等于零时, 这个数字就表示了将单位矩阵循环右移的位数;而当这个数字小于零时, 这个数字就表示了零矩阵。这种QC-LDPC码可以采用移位寄存器的方式进行编码, 大大降低了编码复杂度;避免了矩阵求逆运算, 节约了监督矩阵的储存空间, 使得编码过程简单化。
三LDPC码中的BP译码算法及其改进算法
1. BP译码算法
消息传递 (Message-Passing) 算法的信道输出符号集和译码过程中发送信息的符号集相同, 都是实数集, 即采用连续性的消息时, 适当地选择信息映射函数, 这就把人工智能中的置信传播 (BP, belief-propagation) 算法用到了LDPC码中, 成为LDPC码的现代译码方案。该算法的主要思想在于利用接收到的软信息在变量节点和校验节点之间进行迭代运算, 从而获得最大的编码增益, 因此具有很好的性能。
2. RBP译码算法
RBP译码算法是一种动态调度的译码算法, 在节点开始迭代的最大残余随着迭代次数其值逐渐减小直至为零, 因此残余的值越大说明此消息还未被收敛, 先处理这样的消息会加速译码。对于RBP算法可以概括为三个步骤:根据校验节点传向变量节点的信息更新前后的差异对将要更新的信息进行排序。
RBP算法是一种有效的动态调度方案, 由Vila casado等人将其应用到LDPC码上, 但在误码率性能和复杂度方面不甚理想。RBP算法因其贪婪特性会产生新错误, 这在非动态的译码方案中不会出现。在复杂度方面第5行和第10行, 当一个校验节点到变量节点更新时mc→v不必重新计算信息量, 因为在r (mc→v) 确定的时候已经被计算过了。另外, 在第10行中每个边缘残余被计算时Q都会被重新排序, 增加了译码复杂度。RBP译码算法1:重新从第 (4) 步开始。
3. VC-RBP译码算法
VC-RBP译码算法在贪婪特性方面要优于RBP译码算法, 主要区别在于残余是根据变量节点传向校验节点更新信息前后的差异计算出来。与RBP译码算法相比, VC-RBP译码算法的程序少了一步。第一步, VC-RBP选择相应的边缘最大值重新从第 (3) 步开始。
四仿真结果
本文采用MATLAB工具对提出的LDPC改进译码算法的性能进行了仿真验证, 采用IEEE802.16e标准设计的QC-LDPC码, 在AWGN信道下码长为1024, 码率为1/2, 迭代次数为10的仿真结果为:随着信噪比的增大, RBP译码算法和VC-RBP译码算法与传统的BP译码算法相比性能要优越, 迭代次数为10的VC-RBP在BER为10-4时与RBP相比有0.28dB的增益。
五结束语
基于变量节点到校验节点传递的信息残余的BP译码算法 (VC-RBP) 与基于校验节点到变量节点传递的信息残余的BP译码算法 (RBP) 和一般的BP译码算法相比具有优越的性能。在同一信噪比的情况下, VC-RBP译码算法比起RBP译码算法和BP译码算法误码性能有一定提高。VC-RBP这种译码算法使得LDPC译码算法收敛得更快, 比起RBP算法, 它仅用较少的迭代次数就能显示出更好的性能。算法2与算法1相比, 由于其不用计算生成的包含残余信息的序列和对每次更新时残余信息的序列进行重新排序, 其算法复杂度也要小一些。
参考文献
校验算法 篇7
1.1 我国境内政府网站被篡改情况
近年来,各级政府更加重视信息化建设,许多政府机构都建立了自己的网站。然而目前政府网站还缺乏足够的防护措施, 已成为我国网络安全中最薄弱的一环。同时,由于政府网站有着不可替代的权威性,所以,政府门户网站一直是黑客及敌对势力的重要入侵目标,对它的攻击严重影响着我国的网络信息安全。
据国家互联网应急中心(CNCERT)每月发布的互联网安全报告数据统计,2013年,我国境内政府网站被篡改数量为2430个,较2012年的1802个大幅度增长34.9%,占CNCERT/CC监测的政府网站列表总数的4.0%,即平均每1000个政府网站中就有40个网站遭到了篡改。2013年我国境内政府网站被篡改数量和其占被篡改网站总数比例按月度统计如图1所示。
图 1 2013 年我国境内政府网站被篡改数量和其占被篡改网站 总数比例按月度统计
仅2015年2月,我国境内被篡改网站数量为9,708个,其中被篡改政府网站数量为276个;境内被植入后门的网站数量为2,607个,其中政府网站127个,这些网站的安全事故给我们敲响了警钟。
1.2 中心门户网站
中心门户网站是中心对外宣传与服务的窗口,网站上的所有内容均为开放信息,可公开浏览。近两年来,中心门户网站先后出现过服务器空间被占用、域名指向错误等现象。对此现象的发生应高度重视。
存在问题:
(1)发现此情况后,网站管理员只能手动查找并删除不合法的文件,耗时耗力。
(2)没有足够人力定期浏览、校验所有网页内容,查找有无篡改痕迹。
(3)若有网站空间被占用、网站挂马等现象,只是简单的网页浏览无法发现问题。
(4)若网站内容被篡改,网站管理员只能被动处理,无法做到提前预测防范。
因此,就目前网站所处的现状,需及时对中心门户网站采取各种有效措施,消除安全隐患,为电子政务的良好运行提供必要的安全保障。
2 信息安全要素
通常说的信息安全包含三个要素,机密性、完整性和可用性。保障任何一个信息系统的安全都要致力于这三个要素,并在此三个要素中找到合适的平衡点。
2.1 机密性
机密性是确保计算机的相关资源仅被合法用户访问。也就是说,只有那些有权访问资源的用户才能得到实际的资源访问。
2.2 完整性
完整性是指所有资源只能由授权方或以授权的方式进行修改。“修改”包括写、替换、状态转换、删除和创建等操作。
2.3 可用性
可用性是指所有资源在适当的时候可以由被授权方访问。可用性的对立面是拒绝服务。
根据保障信息安全的三要素分析,保密性与可用性,不适用于网站的信息安全维护,网站内容被篡改属于破坏信息完整性, 因此,本文从校验网站内容完整性上研究如何保障网站信息安全。
3 信息完整性校验
常用的信息完整性校验方法有数据加密、MD5算法等。
3.1 数据加密
数据加密是指通过加密算法和加密秘钥将明文(原始文件) 转变问密文(加密文件),再通过解密算法和解密秘钥将密文恢复为明文,它的核心技术是密码学。
显然,此种方法,不便于应用于网站内容的完整性校验, 数据加密更适用于数据在传输环节上的保护。
3.2 MD5 算法
信息- 摘要算法(Message-Digest Algorithm 5, MD5),在上世纪90年代初由MIT Laboratory for Computer Science和RSAData Security Inc的Ronald L.Rivest开发出来,经MD2、MD3和MD4发展而来。
MD5算法的典型应用,即是验证数据完整性,防止信息被篡改。
比如,将一段200字的总结写在一个叫zongjie.txt的文件中, MD5将整个文件当作一个大文本信息,通过其不可逆的字符串变换算法,产生一个唯一的MD5信息摘要,这个MD5信息摘要就如同每个人的指纹一样,都各不相同。大致结构如下:
MD5(zongjie.txt)=0ca175b9c0f726a831d895e269332461, 这就是zongjie.txt文件的数字签名。如果在以后传播这个文件的过程中,无论对这个文件内容进行何种修改,包括添加、删除、备注、格式转换等等,或者是下载过程中由于线路不稳定引起的传输错误等,这个文件的MD5值就会发生变化,只要对这个文件重新计算MD5,就会发现信息摘要不相同,由此可以确定得到的是一个不正确的文件。
由以上分析得到,可采用MD5算法数据完整性校验的特点,对中心网站内容的完整性做验证。
4 中心网站操作实例
对存储在服务器上的网站内容进行MD5运算,得出唯一的MD5值,在每次对网站信息更新后,对网站内容作MD5运算,存储得到的MD5值,定期重复对网站内容进行MD5校验, 对比MD5值是否一致,校验网站是否被修改。
因MD5算法源码开发,网络中有很多MD5算法软件,本文选用一款名为WINMD5的工具做校验。
对网站内容任意删除一张图片,再进行MD5运算,得到文件www2.md5,再对两次得到的MD5文件进行对比,得到MD5值不相同,说明网站内容被修改。
5 小结
保障信息安全的计算机技术多种多样,各种加密算法、数字签名技术等,从中找到一种适合于维护网站安全的技术,并最大程度的发挥作用是难点。MD5算法应用于校验网站内容完整性,其巧妙之处在于,不仅简单、易用,而且有效的解决了工作中的难点,减少了网站管理员手工查找网站篡改痕迹的工作任务,增强了网站的整体防御能力。
摘要：近几年,随着我国东海、南海等涉海问题的日益敏感,境外势力对我国的网络攻击频繁,其中,对涉海单位的攻击尤为疯狂。涉海单位的门户网站作为提供公众服务与对外宣传的窗口,长期暴露在互联网中,极易遭到攻击和篡改。本文从中心门户网站的现状分析出发,根据保障网站信息安全的几个要素,结合工作实际,对比现有的各种成熟计算机技术,找到适用于维护网站安全的措施,即通过MD5算法校验网站内容的完整性。通过定期对网站内容的校验测试,增强了网站的整体防御能力,为网站信息安全把关。
关键词：信息安全,MD5算法,完整性校验
参考文献
[1]国家互联网应急中心(CNCERT)2013年网络安全报告.2014.
[2]国家互联网应急中心(CNCERT)2015年2月网络安全报告.2015.
[3]Charles P.Pfleeger、Shari Lawrence Pfleeger.信息安全原理与应用[M].电子工业出版社.2007.
[4]谢平华.MD5算法在重复邮件识别方面的研究和实现[J].科技传播.2011.