shenk’s算法（共3篇）
shenk’s算法 篇1
0 引言
速度控制是机床和机器人控制器最重要的组成部分, 也是系统开发的难点。加减速控制一般分为后加减速控制和前加减速控制。后加减速控制是在插补后再进行加减速处理, 因此会引起轮廓误差。前加减速控制是在插补之前进行加减速处理, 对合成速度进行控制, 不会产生轮廓误差。因此在现代高档数控系统多使用前加减速控制。
目前对前加减速控制的研究比较多。文献[1,2,3,4]对加速进行离散采样时, 会出现“尾巴”, 为了消除“尾巴”需要预测减速点, 重新计算加速度。“尾巴”产生的原因是实际的轨迹由离散的直线段而不是连续曲线组成, 插补路径很难保证刚好是直线段的整数倍。因此, 位移、速度和加速度很难在插补终点同时到达零点。如果速度比位移更早到达零点, 则插补过程需多插补一个额外的低速段以完成剩余的位移量, 这一低速段称为“尾巴”。“尾巴”现象会极大降低系统插补效率。这是因为减速区的插补时间被延长。在某些情况下, 由于大部分伺服驱动器在低速情况下存在“死区”而最终无法达到目标插补终点, 因而将直接导致插补精度的下降。文献[1,2,3]通过重新计算减速区新的加速度和加加速度消除“尾巴”, 该方法对直线加减速而言带来的问题是加速区和减速区的加速度不同。对S形加减速而言, 减速时为了能够保证速度和位移同时到达指定的值, 会让当前速度突变到新速度, 导致加速度和加加速度突变, 会带来很大的冲击, 因此需要预测减速点, 让计算时间延长。
本文在插补开始时根据加速度重新计算运行速度, 以保证该速度加工能够保证插补路径刚好是直线段的整数倍。以此速度重新计算加速度和加加速度, 加工时以重新计算的速度、加速度、加加速度进行运动, 可以避免处理“尾巴”。同时根据采样次数决定加减速, 避免了预测减速点。
1 直线加减速离散算法
1.1 直线加减速
直线加减速是指在加减速过程中加速度为常数的加减速过程。假设Ts为采样周期, na为加减速所需的采样周期数, 则加减速时间T1=naTs;nb为匀速所需的采样周期数, 则匀速运行时间T2=nbTs;S为加工轨迹长度, vmax为程编加工速度 (不失一般性, 假定起点和终点速度为0, 加减速时间相同, 移动的距离大于加减速的移动距离) 。直线加减速过程如图1所示, 则直线加减速的加速度a (t) 、速度v1 (t) 、加工轨迹长度S (t) 分别为
(1)
(2)
式中, τk为相对时间, τk=tk-tk-1;tk为各个阶段的过渡时刻, k=1, 2, 3。
理论上讲, 开始时速度以加速度a加速, 速度达到加工速度后, 进入匀速运行状态, 当运动到减速点时以加速度a减速, 速度减到零时到达目标点, 但实际情况并非如此, 实际的减速过程和理论的减速过程不完全一致, 因此出现“尾巴”[2]。解决该问题的思路是:插补前, 重新计算最大运行速度和加速度, 并以此加速度和最大运行速度运行, 使得速度减为零时恰好达到目标点。
1.2 实际加工速度
由式 (3) 可得加工轨迹的长度S:
S=vmax (T1+T2) =vmax (na+nb) Ts (4)
则匀速段的采样个数nb为
nb=ent (S/ (vmaxTs) ) -na (5)
式中, ent (·) 为取整函数。
而实际的加工速度
v′max=S/[ (na+nb) Ts] (6)
则实际加速度
a′=v′max/ (naTs) (7)
系统以加速度a′进行加速, 加速na个采样周期后到达到速度v′max。以v′max速度匀速运行nb个采样周期后开始减速, 减速时以加速度a′减速na个周期后减速到零。插补的加减段和匀速段通过na和nb判断是否结束, 不需要在每次插补时计算减速区长度, 因此减小了计算量, 提高了效率。
1.3 离散后的加工速度加速段每个插补周期的速度为
v2 (t) = (Sn+1-Sn) /Ts=a′Ts[ (n+1) 2-n2]/2
0≤n<na, 且n为整数, 下同。
则
v2 (t) =a′ (2n+1) Ts/2 (8)
同理, 可得匀速段和减速段的速度。则离散后的加工速度
当t=2Ta+Tb时
S′=v′max (na+nb) Ts (10)
由式 (6) 和式 (10) 可得S′=S。S形加减速处理与直线加减速处理相同。
直线加减速的优点是计算简单, 因为它采用恒加速度, 加速度的导数为0。在加速段和减速段的起点和终点存在加速度突变, 机床运动存在冲击, 且速度的过渡不够平滑、运动精度低。
2 S形加减速离散算法
2.1 S形加减速
S形加减速的最重要特征是该算法的加速度/减速度曲线的形状如字母S。S形加减速的速度曲线平滑, 从而能够减少对机床的冲击并使插补过程具有柔性。S形加减速分为7段:加加速、匀加速、减加速、匀速、加减速、匀减速、减减速。图2所示的S形加减速, 起始和终止速度为零, 加工速度为vmax。不失一般性, 这里假定加加速、减加速、加减速、减减速时间均为T1, 即所需的采样个数na相同, 则T1=naTs;匀加速、匀减速时间均为T2, 所需的采样个数为ne a, 则T2=ne aTs;匀速运行时间为T4, 所需的采样个数为nb, 则T4=nbTs。不失一般性, 所走的距离S大于加减速距离。
S形加减速的加加速度公式为
(11)
式中, J为加加速度。
加速度公式为
(12)
式中, τp为相对时间, τp=tp-tp-1, p=1, 2, …, 7。
速度公式为
(13)
位移公式为
(14)
式中, Si为ti时刻的距离, i=1, 2, …, 6。
2.2 实际的加工速度由式 (12) 可得
J=vmax/[T2s (n2a+nane a) ] (15)
由式 (14) 可得加工长度
S=JnaT3s (2n2aTs+3nane a+n2e a) +nbTsvmax (16)
则采样周期数
nb=ent
由式 (16) 可得匀速段的加工速度
v′max=[S-JnaT3s (2n2aTs+3nane a+n2e a) ]/ (nbTs) (18)
由式 (15) ～式 (18) 可得实际运行过程的加加速度
J′=v′max/[T2s (n2a+nane a) ] (19)
2.3 离散后的加工速度加速段每个插补周期的速度为
v2 (t) = (Sn+1-Sn) /Ts=J′Ts[ (n+1) 3-n3]/6
0≤n<na
则
v2 (t) =J′T2s (3n2+3n+1) /6 (20)
同理可得匀加速段等其他段的加速度。离散后的加工速度为
插补时以该速度进行运算, 直到插补结束。
3 速度变化率
本文采用改变加工速度的方式消除“尾巴”, 由于加工速度和加工效率密切相关, 因此需要判断该方法对加工速度的影响。给出速度变化率的表达式如下:
η=| (vmax-v′max) /vmax|
对于直线, 有
v′max=S/[ (na+nb) Ts]
η<|vmaxTs/ (S-vmaxTs) |<1/ (na+nb-2) (21)
由式 (21) 可知, 长线段时η很小, 即加工速度变化很小, 不影响加工质量。短线段时, 实际速度达不到加工速度, 所以加工速度的变化对运行效果的影响不大。同理可知S形加减速的加工速度变化很小。
4 仿真与试验结果
现在根据上面的分析编程实现直线和S形曲线加减速过程。对于直线加减速。给定速度vmax=300mm/min, 采样周期为1ms, 加减速时间为400ms, 从 (0, 60mm) 运行到 (190mm, 110mm) 。则经过计算后, vmax=300.146mm/min, 加速度为0.75m/s2, 匀速运行的时间为880ms, 运行时间总计1680ms, 如图3所示。利用文献[3]的方法, 计算出vmax=300mm/min, 加速段加速度为0.75m/s2, 减加速段加速度为7.79m/s2, 运行时间总计为1620ms。从运行结果看虽然运行时间减少, 但减速段加速度变化过大, 给机床带来很大的振动。
对于S形加减速。给定速度vmax=300mm/min, 采样周期为1ms, 加减速时间为400ms, 从 (0, 60mm) 运行到 (190mm, 110mm) , 加加速段时间T1=100ms, 匀加速段时间T2=100ms。则经过计算后可知, vmax=300.19mm/min, 匀速运行段的时间T4=980ms, 如图4所示。
直线速度变化率η=0.049%, S形加减速度变化率η=0.063%。速度变化很小。基于上述算法, 在研制的车床系统DTM-7T上实现了此算法, 并在进行了验证, 效果良好。
参考文献
[1]曹宇男, 王田苗, 陈友东, 等.插补前S形加减速在CNC前瞻中的应用[J].北京航空航天大学学报, 2005, 33 (5) :594-599.
[2]Cao Yunan, Chen Youdong, Wei Hongxing, et al.The Algorithm of Former S-shape Acceleration/Deceleration in CNC System[C]//8th International Conference on Progress of Machining Technology.Tokyo, Japan, 2006:165-168.
[3]陈友东, 王田苗, 魏洪兴, 等.数控系统的直线和S形加减速研究[J].中国机械工程, 2006, 17 (15) :1600-1604.
[4]Guo Xingui, Wang Decai, Li Congxin, et al.A Rapid and Accurate Positioning Method with Linear Decel-erationin Servo System[J].International Journal of Machine Tools and Manufacture, 2002, 42 (7) :851-861.
shenk’s算法 篇2
软件测试是一项耗时费力的活动,然而它又在软件工程中占有很重要的地位。NIST在一项报告中称美国每年由于软件故障而导致的经济损失多达599亿美元[1]。报告还称如果在早期采用更有效的故障检测方法则可以挽回大约220亿美元的损失[1]。由此可见,软件测试的作用非同一般。这就需要一种先进的测试技术来提供尽可能高的测试性价比。
软件系统是由组件构成的,因此系统的故障常常是由一些难以预料的系统组件之间的异常交互引起的。若对一个10因素(组件或参数个数)4水平(每个参数的可选值个数)的系统采用穷尽测试的方法就需要生成410=1,048,576个测试用例,但由于受到时间、费用等资源的限制,采取这种穷尽组合的方式来对各组件之间的交互进行测试显然是不切实际的。经验数据表明,配对测试技术适用于多种不同类型的软件系统,它不仅是可行的,并且是一种高效的测试方法。对于上面所述的10因素4水平系统,配对测试只需25个测试用例就可以使不同参数的各值之间的两两配对至少被测试一次[4]。
产生最小配对测试集是一个NP问题,也就是说不可能存在某一算法可以产生最小测试集。因此,现在已经有不同的测试集产生算法,它们的目的都是为了产生接近最优的测试集。文章重点介绍了文献[5]中所给出的一种较新的、较有效的n因素s水平配对测试集生成算法,并给出了具体的应用。
1 配对测试的介绍
1.1 配对测试的定义[6]
定义1 有N个相互独立的测试因素:f1,f2,…,fN,每一个因素fi有Li个可选水平(值):fi={li,1,…,li,Li},一个测试集R被产生。R中的每一个测试用例中都含有N个水平,即包含每一个因素fi的一个水平,并且R中的所有测试用例覆盖了任意两个因素的任意水平所形成的配对。例如,对于一个配对li,p和lj,q,1≤p≤Li,1≤q≤Lj,并且i≠j,那么R中至少有一个测试用例包含配对li,p和lj,q 。
1.2 配对测试的有效性
配对测试相对于穷尽测试来讲可以节省较多的开销,而从检查故障的能力这方面来看,配对测试也是一种比较好的测试方法。研究发现,有20%-40%左右的软件故障是由某个系统参数引发的,20%-40%左右的故障由某两个参数的相互作用引发的,而大约70%的软件故障是由一个或两个参数的相互作用引起的。Dalal等通过经验数据证明了在一个软件系统中应用配对交互测试可以检测出很多已存在的错误;Burr等通过更多的经验数据证明了配对测试是有效的[4]。美国FDA组织对109个软件控制的医疗设备进行了检测,用配对测试检测出了97%的故障。
1.3 已有的算法研究
配对测试是一种有效的测试方法,但是生成最小配对测试集却是一个NP问题。配对测试主要是研究应用组合设计方法对软件进行组合测试。主要有以下六种方法:正交拉丁方算法、AETG算法、IPO算法、Williams算法、PSST算法和Kobayashi算法。
正交拉丁方算法利用组合数学中拉丁方的特殊性质来构造满足两两组合覆盖要求的测试集。它的优点在于构造简单,存在现实中的数学模型,并且在已知参数个数及可取值情况下就可准确计算出满足两两组合覆盖要求的测试集大小。不足之处是在实际系统中,往往为了满足拉丁方数学上的特性,因此在构造算法中常常需要添加“无关值”,从而导致增加额外的测试用例。
AETG算法先产生一组待测的测试用例,然后利用贪心算法选择其中一个能覆盖最多未被覆盖到的两两组合。循环迭代直至所有的两两组合都被覆盖。相对于其它算法,它获得的结果是较优的。但是AETG算法在时间复杂性上不如IPO算法。
IPO算法采用贪心算法,是基于参数顺序的渐进扩展的两两组合覆盖测试用例生成方法。与其它算法一次生成所有测试用例的方式不同,IPO算法是以参数为中心的,这样就有利于系统的扩展,且该方法在时间复杂度上略优于AETG算法,但是结果不是较优的。
Williams算法以正交拉丁方算法为基础,在正交矩阵的基础上加入了分区等因素。它改进的算法在时间复杂度上比较稳定,受参数规模等因素影响较小,且生成测试用例集合的规模同IPO算法基本相当;不足之处是该算法只适合参数规模较小的系统。
PSST算法将解空间映射成一个树,它的基本思想是找出相互间重叠数不超过1的所有解,然后对其进行扩展。PSST算法将启发式方法和代数方法的优点结合起来,并尽量克服两者的不足。该算法也可以允许测试人员预先指定一组测试用例,然后在此基础上进行扩展以生成两两组合覆盖表。该算法具有较强的针对性和灵活性。但由于该算法终究还是属于启发式算法,所以不能保证每次测试用例生成的结果是最优的。
Kobayashi算法是通过一些基本正交表和特征块作为基本成分,来构造满足要求的复杂两两组合覆盖表。Kobayashi算法的基本成分是正交表O表,并通过O表的交叉重叠来构造新的两两组合覆盖表。虽然Kobayashi算法在某些情况下能获得最优解,但是其还是不能避免由于拉丁方特性所带来的缺陷。
Brownlie等开发了OATS系统,该系统是用正交表来生成测试集的,此外还有一些学者将代数方法和一些仿生学方法用于产生配对测试集。下一节中所提出的方法是针对产生n因素s水平配对测试集的方法,算法所产生的测试用例数较少,在某些情况下比AETG算法和IPO算法产生的还要少。
2 N因素S水平配对测试集生成算法
有关N因素S水平的配对测试集生成算法,可细分为s=2和s>2两种情况。
2.1 N因素2水平配对测试集生成算法
假设有一些由若干个1和若干个0组成的数串,这些数串有相同的长度,记为2K-1。将每个数串的权值定义为它所包含的1的个数。用S2k-1表示长度为2K-1并且权值为K的这些2进制数串的集合,其表达式为|S2k-1|=C
从这十个二进制数串中任意选取两个数串,可以看出(0 1),(1 0),(1 1)这三个组合在被选定的两个数串中至少出现一次。因此,如果在S2k-1中的每一个数串后添加一个0,那么(0 0),(0 1),(1 0),(1 1)这四个组合在任意一对数串中至少会出现一次。
下面给出N因素2水平配对测试集生成算法描述:
输入:N
输出:一个测试集
计算满足的最小k值。
从S2k-1中任选N个数串。
在被选的N个数串后分别添加一个0,然后求出它们的转置。
这样就得到N因素2水平的配对测试集,测试集的大小为2k。
例如要产生9因素2水平的配对测试集,则N=9,通过公式计算得k=3,如果选取图1中的前9个数串,则所得到的配对测试集如图2所示。
2.2 N因素S(S>2)水平配对测试集生成算法
算法主要是通过正交阵列和有序设计来构造测试集的,而正交阵列和有序设计的构造又和互相正交的拉丁方(MOLS)有关。在介绍算法之前,先给出几个相关定义和定理,然后介绍一下正交阵列和有序设计的构造过程。
2.2.1 相关定义和定理
定义2[7] 如果n阶方阵A的每行、每列都是{1,2,… , n}的全排列,则称A为n阶拉丁方。
定义3[7] 设A=(aij),B=(bij)是两个n阶拉丁方。如果{1,2, … ,n}2={(aij,bij)|1≤i, j≤n},则称A与B是一对正交的n阶拉丁方。
定义4 一个拉丁方集合(每一个拉丁方有相同的阶),如果任意两个拉丁方是正交的,则称之为相互正交的拉丁方集合。
定义5[5] 一个正交阵列OA(k,s)是一个s2×k的阵列,且在任意两列中每一个有序对只出现一次。
定义6[5] 一个有序设计OD(k, s)是一个s(s-1)×k的阵列,且在任意两列中每一个有序并且值不相同的对只出现一次。
定义7 如果一个OA(k, s)只含有每一个连续的(x,x,…,x)行一次则它是幂等的。
定理1 若s为素数或素数的幂,则存在s-1个互相正交的s阶拉丁方(MOLS)。
定理2 如果s是一个素数或素数的幂,则可以构造OA(s+1,s)。
定理3 如果s是素数或素数的幂,则可构造OD(s,s)。
2.2.2 正交阵列和有序设计的构造方法
对于测试参数而言,如果要构造s+1因素s水平测试集,则需要s-1个阶为s的MOLS。用行号和列号分别表示前两个因素的水平,其余s-1个因素的水平依次用组合后的s-1维阵列中的值表示。例如,要表示4因素3水平,则需要2个3阶MOLS。
如:0 1 2 0 1 2 将它们组合得 (0,0) (1,1) (2,2)
1 2 0 2 0 1 (1,2) (2,0) (0,1)
2 0 1 1 2 0 (2,1) (0,2) (1,0)
阵列中的(1,1)在测试配置中表示为(0,1,1,1),第0行,第1列,值为(1,1)。依次类推可得到4个3值参数的测试用例集为:
任意选取4列中的2列,如选取第1列和第3列,可得到的配对为0 0, 0 1, 0 2, 1 0,1 1, 1 2, 2 0, 2 1, 2 2,这些配对在这两例中出现的次数是相同的,所以这是一个正交阵列。由于只有0,1,2三个值出现所以它又可以成为3水平阵列。我们称之为OA(4,3),其中4表示列数,3表示阶数。
由OA(4, 3)删除第一列就得到幂等OA(3, 3),然后在OA(3, 3)中删除所有形如(x,x,…,x)的行就得到OD(3, 3)。具体过程如图3所示。
2.2.3 算法
现在来介绍如何构造n因素s水平的配对测试集。我们发现正整数u、v满足(1) n-1=(s+1)u+1sv+1,或(2) (s+1)u+1sv是最小的大于或等于n的整数。测试集是通过扩展OA(s+1,s)或OD(s,s) 来构造的。扩展方法则依赖于u和v的值。当s是素数或素数的幂时,n因素s水平的配对测试集构造算法如下:
输入:n,s>2
输出:一个测试集
构造一个正交阵列OA(s+1,s)和一个有序设计OD(s,s)。用li[s]表示OA(s+1,s)的第i列,li*[s]表示li[s]删除本列第一个元素所得到的s2-1个元素的列向量,di[s]表示OD(s,s)的第i列。
找出满足条件1或条件2的整数u和v。如果整数u和v满足条件1,则转向第3步;如果满足条件2,则转向第4步。
下列s2+u(s2-1)+(v+1)(s2-s)个元素的列向量:
是通过一个含有s2个元素的li[s],(其中1≤i≤s+1),u个各含有s2-1个元素的列向量lj1*[s], …,lju*[s](其中1≤j1…,ju≤s+1)和v+1个各含有s2-s个元素的列向量dk1[s],…, dkv+1[s],(其中1≤k1,…,kv+1≤s)连接而成的。构造一个测试集矩阵S,它的列全部由上述连接列向量组成,S共有(s+1)u+1sv+1个列。最后向S添加一个新列,该列的前s2+u(s2-1)+v(s2-s)个元素全为0,最后s2-s个元素值为1,2,…,s-1且每一个值都在列中连续出现s次。形如:
这样就得到一个配对测试集,共有(s+1)u+1sv+1+1列,每一个配对在矩阵S中至少出现一次。S的每一行就代表一个测试用例。
下列s2+u(s2-1)+v(s2-s)个元素的列向量:
是通过一个含有s2个元素的li[s],(其中1≤i≤s+1),u个各含有s2-1个元素的列向量l*j1[s], …,l*ju[s](其中1≤j1…,ju≤s+1)和v个各含有(s2-s)个元素的列向量dk1[s],…, dkv[s],(其中1≤k1,…,kv≤s)连接而成的,共有(s+1)u+1sv个列。构造一个测试集矩阵S,它的列全部由上述连接列向量组成,所以S共有(s+1)u+1sv个列。如果n≤(s+1)u+1sv那么S中的任意由n列组成的子矩阵,它就是n因素s水平的配对测试集,它的行可被当作n因素s水平的配对测试用例。
举例,如果要为100因素4水平系统构造配对测试集,即n=100,s=4。由定理1和定理3可分别构造出OA(5,4)和OD(4,4),如下:
经计算,当u=1,v=1时满足条件(2)即(s+1)u+1sv=5241=100=n,因此根据第4步构造43×100矩阵S,
矩阵的一行就代表100因素4水平的一个测试用例。
下面给出当s是素数或素数的幂时,该算法可以产生n个s值参数的配对测试集的证明。
证明 第3步或第4步所产生的矩阵S,观察它的任意两列,可以发现每一个有序的配对至少出现了一次。如下原因:一个含有s2个值的列向量li[s],通常出现在每一列的第一个位置上,任选两列然后考虑以下两种情况:(1)第一行是(li[s] lj[s])时,1≤i≠j≤s+1,因此每一个有序配对在这两列中至少出现一次。(2)第一行是(li[s] li[s])时,1≤i≤s+1,则必定有一行是l*i[s] l*j[s],1≤i≠j≤s+1,或di[s]dj[s],1≤i≠j≤s的形式。值相同的配对出现在li[s] li[s]中,除(0,0)配对以外的有序配对出现在l*i[s] l*j[s]中,不同值的有序配对出现在di[s]dj[s]中。因此,值的每一个有序配对都至少出现了一次。
该算法的时间复杂度为O(nlogn)。
证明 在第二步中,当s≥2时寻找u和v最多要O((logn)2)。第三步和第四步分别需要O(nlogn),所以算法的时间复杂度为O(nlogn)。
对于s不是素数或素数的幂的情况,要构造n 因素s水平的配对测试集可以将s增加到s0,使s0=pm,其中p是素数,m≥1。例如,要产生15因素10水平的配对测试集,就使n=15,s=11,然后再用本节中的算法来构造。那些多出来的值就是冗余值。
3 实 验
实验表明这种新的算法和配对测试集生成算法AETG和IPO相比,产生的测试集大小相当,但在有些情况下甚至少于它们,所以该算法在生成N因素S水平的配对测试集上是有一定的优越性的。相关实验结果如图4-图6所示。图2和图3中AETG的结果我们不知道。
4 应 用
我们用2.2.2节中的算法对文献[2]中的那个例子进行配对测试用例的构造。这是一个有关电话呼叫的系统。测试参数及各参数的可选取值如表1所示。可知这是构造4个3值参数的情况,即n=4,s=3,其中“Call type”参数可取{Local, Long Distance, International},“Billing”参数可取{Caller, Collect, 800},“Access”参数可取{Loop, ISDN, PBX},“Status”参数可取{Success, Busy, Blocked}。用(0, 1, 2)分别表示每一个参数的三个可选取值。
根据2.2.3节中的算法,首先生成OA(4,3),OD(3,3)(生成方法如前所述)。然后计算正整数u,v的取值,经计算,当u=0,v=0时,满足条件2即n=4=(3+1)0+1×30,因此应采用算法第四步的方法来构造。根据第四步,列向量是通过一个含有s2个元素的li[s],u个各含有s2-1个元素的列向量l*j1[s], …,l*ju[s]和v个各含有(s2-s)个元素的列向量dk1[s],…, dkv[s],连接而成的,在本例中由于u=0,v=0,所以每一个列向量只由一个含有32的li[3]组成。这样所构造的配对测试集就是一个4×9的矩阵。将各参数值取代其对应的数字代号就可得到其配对测试集,如图7所示。
5 结 语
配对测试是一种实用、有效的测试技术,文章给出了配对测试的概念,介绍了配对测试的有效性,并给出了一种新的N因素S水平的配对测试集生成算法,该算法细分为s=2和s>2两种情况。实验结果表明该算法生成的测试集比较小,与AETG和IPO相比具有一定的优越性。
参考文献
[1]Cheng C,Dumitrescu A,Schroeder P.Generating small combinatorialtest suites to cover input-output relationships.Proceedings of the Third-International Conference on Quality Software[C]//QSIC,2003:7682.
[2]Cohen D M,Dalal S R,Fredman M L,et al.The AETG system:An Ap-proach to Testing Based on Combinatorial Design[J].IEEE Trans.onSoftware Engineering,1997,23(7):437-443.
[3]Lei Y,Tai K C.In-Parameter-Order:A Test Generating Strategy forPairwise Testing[J].IEEE Trans.on Software Engineering,2002,28(1):1-3.
[4]Colbourn C J,Cohen M B,Turban R C.A Deterministic Density algo-rithm for pairwise interaction coverage[C]//Proceedings of the IAST-ED International Conference on Software Engineering,2004:242-252.
[5]Maity S,Nayak A.Improved Test Generation Algorithms for Pair-WiseTesting[C]//16th IEEE International Symposium on Software Relia-bility Engineering(ISSRE’05),2005:235-244.
[6]Czerwonka J.Pairwise attesting in Real World[C]//Proceedings of24nd Pacific Northwest Software Quality Conference,2006.
shenk’s算法 篇3
1Huffman和S-DES混合加密算法与现有及传统加密算法的比较
文本加密技术是保障信息安全最基本、最核心的技术措施,主要通过对数据的加密和数字签名来实现。其中对数据的加密处理主要是为了防止数据不会被窃听。数据的加密方式有两种,一种是传统的对称密钥加密,就是加密方用一把密钥对数据进行加密,而解密方用同样一把密钥对数据进行解密。第二种是非对称密钥加密,如果使用这种算法,可以保证对发送方和接收方身份的确认。而数字签名实际上是由生成摘要和生成数字签名两部分构成。其中摘要可以防止文件被篡改,保证信息的完整性;而数字签名则是为了保障在商务活动中数据的不可否认性,从而使数据具有法律意义。
目前在文档安全管理市场上,加密可分为:文档格式转换加解密、核心层加解密、应用层加解密。常见的加密软件有:1) 记事本加密器Ncrypt TX,它预设了多种加密算法,包括DES、3DES、Rijndael、Polyalphabetic、ROT13、Vigenrre、Playfair等。当然不同的加密算法支持不同的数据编码格式,如Hex、Base64、Text、Word等。在工具栏中也可以相应地设置所需的密码。2) 超级密码本SuperCode有两个特色:第一是多重加密功能;第二是密码自动生成,通过创建密钥文件,摆脱记忆密码的烦恼。Super Code内置了Triple DES、DES、Rijndael、RC2等加密算法。Super Code的特点是允许你以上述加密算法为依据,自由组合,创建自己独有的加密算法序列,例如可以选择两种Triple DES算法,一种DES算法,三种RC2算法,五种Rijndael算法,而且可以灵活排列其先后顺序。
对称密钥密码系统,历史悠久,加/解密速度快是其优点,但因加密密钥与解密密钥为同一把密钥,信息的传送方如何在加密之后,将密钥以安全的方式传送给接收方,如何使双方能共享该密钥,是此密码系统的一大问题,因此,对称密钥密码系统不适合多人使用的应用。
非对称式加密就是加密和解密使用的不是同一个密钥,通常有两个密钥,称为“公钥”和“私钥”,它们必须配对使用,否则不能打开加密文件。“公钥”是指可以对外公布的,“私钥”则只能由持有人知道。它的优越性在于,对称式的加密方法如果是在网络上传输加密文件就很难把密钥告诉对方,不管用什么方法都有可能被别人窃听到,而非对称式加密方法有两个密钥,“公钥”可以公开,收件人解密时只要用自己的私钥即可,这样就很好地避免了密钥的传输安全性问题。
非对称式密码系统也称为“公开密钥密码系统”,它弥补了对称密钥密码系统的缺点,但运算速度较慢是公开密钥密码系统的缺点。
DES算法运算速度较慢,但在此基础上改进的S-DES算法,是一个对称分组加密的简化模型,有利于研究和实现,再结合Huff-man编码对文本信息进行压缩编码,即Huffman编码和S-DES算法相结合的混和加密算法就应运而生了。
2Huffman和S-DES加密算法原理分析
2.1 Huffman编码原理分析
哈夫曼编码是一种变长编码,是哈夫曼树的一个应用。哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。
哈夫曼编码根据字符出现的概率来构造平均长度最短的编码。在编码中,若各码字长度严格按照码字所对应符号出现概率的大小的逆序排序,则编码的平均长度是最小的。其中,码字是明文字符,是通过哈夫曼编码后得到的编码,其长度由明文中字符出现的概率决定,出现概率大的编码长度短,出现概率小的编码长度长。
哈夫曼编码对需要编码的数据进行两遍扫描:第一遍统计原数据中各字符出现的频率,利用得到的频率值创建哈夫曼树,并把树的信息保存起来,以便解压时创建同样的哈夫曼树进行解压;第二遍则根据第一遍扫描得到的哈夫曼树进行编码,并把编码后得到的码字存储起来。
哈夫曼编码的缺点:一、对于过短的文件进行编码的意义不大,因为存储哈夫曼树的信息就需要较大的存储空间;二、存储编码信息时,编码速度慢,效率低下。
2.2 S-DES算法分析
S-DES加密算法是以8位明文和10位密钥作为输出。其解密算法用同一密钥对8位密文分组产生原来的明文分组,如图1所示,它描述了S-DES的算法流程。
加密算法的数学表达式:IP-1*fk2*SW*fk1*IP,也可以写为:密文=IP-1(fk2(SW(fk1(IP(明文)))))。其中K1=P8(移位(P10(密钥K))),K2=P8(移位(移位(P10(密钥K))))。
解密算法的数学表示:明文=IP-1(fk1(SW(fk2(IP(密文)))))
S-DES加密算法涉及五个函数
1) 初始置换IP(initial permutation),,将8bit数按照IP函数进行移位;
2) 复杂函数fk1,它是依赖于子密钥K1,包含置换和替换的运算;
3) 置换函数SW,将8bit数的左4bit和右4bit交换位置;
4) 复杂函数fk2,它是依赖于子密钥K2,包含置换和替换的运算;
5) 初始置换IP的逆置换,将8bit数按照IP-1函数进行移位。
3Huffman和S-DES算法混合加/解密过程
3.1 混合加密过程
用数据流方式读入将要加密的文本文件信息,输入密钥并保存,经过第一次哈夫曼编码加密后转化为0/1字符串,在进行第二次加密之前要将0/1字符串分组,每8位一组,将其作为第二次加密S-DES算法的明文输入,经过S-DES算法得到最终的密文,将其保存到另一个TXT文本文件中。混合算法的加密过程如图2所示。
3.2 混合解密过程
解密过程首先要进行身份认证,输入密钥,身份认证成功后将进行解密,否则将不会解密。首先将最终的密文进行分组,每8位一组,经过S-DES算法进行第一次解密,得到0/1字符串,将其作为Huffman算法的编码进行第二次解密,即可得到最终的明文。其混合算法的解密过程如图3所示。
4 Huffman和S-DES混合算法的实现
4.1 Huffman编码的实现
Huffman算法主要涉及到5个核心函数,分别为获取权值数组GetWeightArray、构建哈夫曼树CreateHuffmanTree、创建哈夫曼编码字典CreateHuffmanDict、哈夫曼编码StringToHuffmanCode以及哈夫曼编码的解码ToHuffmanCode。
1)获取权值数组GetWeightArray(string str)
将文本信息中的每种字符出现的次数进行统计,并将其作为哈夫曼树的权值。
2)构建哈夫曼树Create Huffman Tree(Node[] sources)
按“左走0,右走1”的原则创建哈夫曼树。
3)创建哈夫曼编码字典Create Huffman Dict(Node h Tree)
创建哈夫曼编码字典,在数组中实现“左走0,右走1”。
4)哈夫曼编码String To Huffman Code(out Dictionary<char, string> key, string str)
由创建的哈夫曼树,得到哈夫曼编码。
5)哈夫曼编码的解码To Huffman Code(string source, Dictionary<char, string> hfdict)
将哈夫曼编码还原成哈夫曼树,得到每个字符出现的次数,将其还原成原文本信息。
4.2 S-DES算法的实现
S-DES算法中涉及的核心算法为P10置换;P8置换;IP函数;FK函数;SW函数;IP-1函数。
1)P10置换p10(string miyao)
2)P8置换p8(stringls1, string ls2)
3)IP函数IP(stringmingwen)
mingwen = mingwen + numbers[1] + numbers[5] + numbers[2] + numbers[0] + numbers[3] + numbers[7] + numbers[4] + numbers[6];
4)FK函数fk(stringmingwen, string key)
5)SW函数sw(string mingwen)
mingwen = mingwen + numbers[4] + numbers[5] + numbers[6] + numbers[7] + numbers[0] + numbers[1] + numbers[2] + numbers[3];
6)IP-1函数NIP(string mingwen)
mingwen = mingwen + numbers[3] + numbers[0] + numbers[2] + numbers[4] + numbers[6] + numbers[1] + numbers[7] + numbers[5];
5 结束语
该混和加密算法结合了Huffman算法的平均最短编码和S-DES算法的分组加密,能对文本信息进行有效的加密,由于加密的过程是由两次加密算法混合组成,所以增强了密文的安全性。
但Huffman算法在统计文本信息中字符出现的次数,并将该次数作为权值时,降低了程序的运行效率。且S-DES算法每次运算8bit数,增加了循环次数,也降低了程序的运行效率。
本文主要是对TXT文件中的字符进行混合加密,对于其他各种文件,如二进制文件等,虽然能够进行有效的加密,但是其安全性和运行效率无法估计,这也是后续研究中应该加以改善的。
摘要：在对比现有的加密软件和古典密码学常见的加密算法后,结合文本加密的现状及发展趋势,该文将基于动态Huffman编码和S-DES算法相结合,弥补两者的缺点,达到对文本信息的最佳加密及解密效果。