随机化算法论文

2024-10-04

随机化算法论文（共8篇）

随机化算法论文篇1

四叉树每个结点有4个分支，一般应用在多维数据库中，如电子地图、计算机图形和图像处理、空间地理信息系统等领域。如图1所示。

压缩四叉树通过合并一系列只有一个子结点的内部结点，达到节省存储空间的目的。如图2所示。

在如何通过输入数据集合构造四叉树结构方面，国内外有许多研究成果。Clarkson提出了第一个压缩四叉树的随机化构造算法[1]。Eppstein建议使用类似跳跃表风格的层次随机采样方法构造压缩四叉树[2]。如果能在常数时间内完成2个整数位交织操作，则可以使用相对简单的算法构造压缩四叉树，否则这项工作将更加困难。

将描述一种简便的新算法构造压缩四叉树，可以看作是Eppstein的跳跃四叉树的变体。

1 预备知识

定义1：对正实数z和实数平面2内的点p=(x,y)，定

义Gz(p)为栅格点。Gz将平面分为许多正方形区域，称为栅格单元。正式地，对任意，半平面x≥zi,x

定义2：一个正方形是正规正方形，假如它被包含在单位正方形内，单位正方形是栅格Gr内的一个单元，r是2的幂。

给定单位正方形内n个点的集合P，按如下方法构建四叉树T：四叉树的根节点对应单位正方形。T中的每个结点v对应正方形单元，并且有4个子结点。这4个子结点对应将分成4个相等的正方形。从根结点开始递归构建这颗四叉树。只要当前结点包含P中的2个以上的点，就继续分割这个结点。直到每个结点只包含P中的一个点为止。

对上述这颗四叉树中只有一个子结点的结点进行压缩可以得到压缩四叉树。P的压缩四叉树表示为ZT(P)。

四叉树中的一个叶结点对应一个正规正方形，一条被压缩的边(更准确地说是这条边最顶端的顶点)对应2个正规正方形的集合差所形成的环形区，这个环形区被称为平铺区。如图3所示。

一棵压缩四叉树将单位正方形分隔为一些平铺区。

2 算法描述

选择P中各点的一个随机排列〈P〉=〈p1,…,pn〉。Ti为Pi={p1,…,pi}的压缩四叉树。在Ti中对应ZT(Pi)中的一个平铺区f的每个结点存储一个列表cl(f)，该列表包含f中的所有点。这样P中的每个点都存储在Ti中。cl(f)称为f的冲突列表。对于P中每个点都有一个指针指向包含它的Ti中的结点。

在第i次迭代中，找到Ti-1=ZT(Pi-1)中存储pi的结点vi，将pi插入vi。这种插入最多导致创建3个新结点。因为只有压缩四叉树的叶结点才能包含插入点。这样会加入一个新结点存储新点Pi。将这个新叶结点悬挂在四叉树上要求一条已有的压缩边Ti-1，加入一个新的顶点。插入pi的叶结点已经存储了一个插入点，不仅为了pi，也是为了这个叶结点上以前存储的点而引入一个新叶结点。如果这2个点之间的距离相对f的直径靠近的话将引入新的压缩边。这样得到的结果树Ti就是Pi的压缩四叉树。将vi中存储的所有点移到Ti中正确的位置。对vi中存储的所有点，检查是否要存储到新结点中，如果是将它移动至新结点。如果vi的冲突列表中有k个点，则本次循环花费O(1+k)时间。由此得到压缩四叉树Tn。

3 算法分析

定义3：设Y为P的任意子集，平铺区f∈ZT(Y)。如果集合,f∈ZT(X)，并且X是具有这种属性的最小子集，即：不存在X的真子集具有平铺区f，则称X是f的定义集。引理1：如果X是平铺区f∈ZT(P)的定义集，则│X│≤4。

与传统随机化增量构建方法不同，这种情况下的定义集不唯一。

引理2：对平铺区f∈ZT(Pi)，第i次迭代创建f的概率≤4/i，即：

证明：设D1,…,DmPi为f的所有不同的定义集。Z=D1∩D2∩…∩Dm。仅当pi∈Z时f在第i次迭代时创建。如果，则存在f的定义集Dt，。同时，由于，f也是ZT(Pi-1)的一个平铺区，这个平铺区在第i次迭代时被创建的概率为零。

根据引理1，所有定义集的基数最大为4，│Z│≤4。要求的概率受到pi在Z中的概率的限制。考虑Pi上所有可能的排列。Z中的4个点之一在这i个点排列中排在最后的最大概率是4/i。根据引理2，创建一个平铺区f的概率与它的冲突列表的大小无关。

引理3：第i次迭代的期望工作量是O(1+n/i)。

证明：对于f∈ZT(Pi)，在第i次迭代时创建中花费的工作量与它的冲突列表cl(f)的长度成正比。设Xi是表示本算法第i次迭代的工作量的随机变量。因为Ti的冲突列表长度为n，根据引理2，第i次迭代的期望工作上限为：

这里的期望是对Pi所有可能的排列。因此，E[Xi]=E[E[Xi│Pi]]=O(1+n/i)。

定理1：对于位于单位正方形内的平面上的n点集合P，可以在时间O(nlogn)内构造一颗压缩四叉树。

证明：根据引理3，上述算法的总计花费时间为

4 结语

这种构造四叉树的方法对于多维空间内的点依然适用。Eppstein的算法是一种懒惰随机化增量四叉树构造算法。Eppstein的算法略为复杂，但支持插入和删除操作，而本算法只支持构建压缩四叉树。

摘要：介绍了一种压缩四叉树形数据结构的随机化增量构造算法。首先给出了压缩四叉树的定义,然后描述了算法实现步骤,通过将单位正方形不断分割为更小的正则正方形达到压缩的目的,使用平铺区域和冲突列表,采用随机化递增的算法构建出压缩四叉树,最后分析了算法正确性和运行时间。

关键词：数据结构,压缩四叉树,平铺区域,正则正方形

参考文献

[1]K.L.Clarkson,K.Mehlhorn,and R.Seidel.Four results onrandomized incremental constructions[J].ComputationalGeometry:Theory and Applications,1993,3(4):185-212.

[2]D.Eppstein,M.T.Goodrich,and J.Z.Sun.The skip quadtree:a simple dynamic data structure for multidimensional data:Proceedings of the 21st annual symposium on Computationalgeometry,2005[C].New York:ACM,2005:296-305.

[3]罗景馨,唐琎.基于改进四叉树分割和结点存储的LOD算法[J].计算机工程,2009,35(20):202-204.

[4]芮小平.一种基于不完全四叉树的LOD生成算法[J].中国图象图形学报,2005,10(9):1152-1160.

“随机化”评语：教育的一种需要篇2

鉴于此，随机评价就显得很有必要，即要求教师能及时捕捉教育的契机，有感而发，及时评定，及时反馈，及时强化与修正，使学生的思想行为沿着健康的轨道发展。“随机化”评语可从如下几个方面来操作：

（一）贺卡评语

在六一儿童节、元旦等节日或学生生日等具有特殊意义的日子，我们可以借赠送贺卡表达祝贺之机，写上几句话，沟通师生双方的心灵。它能使学生倍感亲切，同时会产生一种奋发向上的动力，不失为教育学生的好机会。比如，有一位老师给一个爱好体育但学习成绩却很一般的学生这样写道：“×××同学，你知道吗？校体运会上，你100米短跑比赛获得了第一名，我和同学们都鼓红了手掌！你取得的成绩使老师由衷地高兴。从现在起你能不能向‘三好生冲刺？老师相信你能，一定能！”

当然，要写好评语，教师首先得做教育的有心人，要乐于和学生打成一片，与学生在纷繁广阔的情感领域里进行多方位、多层次的交流，留心学生的一言一行，一举一动，并能做到见微知著，于平淡处品“绚丽”，于无声处听到“惊雷”，然后再发挥评语这种书面语言的独特魅力。此外，还要注意使用情境化、诗化、美化的语言，使学生蕴含品味，妙然心悟，神游于教师用美的语言编织的催人奋进的意境之中。

（二）作业评语

学生学习进步了，要予以赞扬;学习落后了，要予以正面鼓励;学习成绩下降了，要寻其根源，并善于借助作业评语启迪学生心智，激发学生的思维。有一次，我给一个解题方法独特的学生写下这样的评语：“×××同学，你这独特而新颖的解题方法，就连老师也没有想到，如果把你的这种解法介绍给同学们，一定会令大家惊叹不已。继续努力吧！数学的自由王国里一定会有你这‘数学小王子的一席之地！”这种充满希望和鼓励的评语，就好比是冲击波、兴奋剂，学生看后怎能不奋发前行呢？再如，有一位学生因为数学基础薄弱，作业常常出错，一时失去了学习的信心。于是，我在他的作业本上写了这样一段话：“×××同学，作业经常会出错，可能是你在学习的某个方面出了问题，并不表示你没有学习的潜能，老师愿做你的朋友，帮助你进步。相信，你会变得优秀！”这样的话语让学生感受到的是绵绵不断的生命暖意。从那以后，这个学生遇到自己不懂的题目，经常会主动和我讨论，学习上表现出了很强的积极性。

其实，当学生感受到自己被信任、被尊重、被寄予良好的愿望时，当学生感觉到你内心深处的善意时，教育就有了成功的前提。

（三）课堂评语

有道是“水本无华，相荡乃成涟漪”“水不激不兴，人不激不奋”，课堂教学是需要适时地对孩子进行激励的，尤其是需要那种带有诗性的激励。带有诗性的激励的课堂是迷人的，也是令孩子们向往的，因为那是具有韵味的课堂，是洋溢着情意化的课堂，也是激发孩子们运思的课堂。比如，有一堂课上，我在讲圆柱体积公式的推导过程时，将圆分成好多等份，拼成一个近似的长方体，由长方体的体积推出圆柱体积计算公式是“底面积×高”。在这过程中，却有一个学生提出，如果将那近似的的长方体换一种摆放，即一个侧面作底，这时长方体的高就是原来圆柱体的半径，他认为圆柱体的体积还可以用“侧面积的一半×半径”来计算。这种超常的发现和思维，是我在课前没有预料到的，当时我对他大加赞赏：“你的这一发现真的令老师和同学惊讶不已，老师给你的智商打100+20分！”那一刻，这位学生脸上洋溢着成功的喜悦。这一评价满足了学生的内心需要——被老师佩服，那是何等的自豪！

当然，课堂评价不能仅仅局限于关注学生对知识的掌握，还要着眼于学生身心的健康成长、意志品质的锤炼和精神境界的提升。有时候，教学中需要进行分组实验，结果有的组成功了，而有的组失败了，这时，我总会作出诸如此类的评价：“不管是成功还是失败，我们都能从中受到一些启发。发明家爱迪生经常要经过上千次实验才能成功做出一项发明，失败了，下次再来。”言外之意，只要认真参与做了，哪怕失败了，也能获得一些经验，老师仍然欣赏你。

总之，教育的契机随处可寻，只要我们教师具备一双慧眼，善于寻找，用心捕捉，勤于用各种形式去表现，相信会收到良好的教育效果。在这过程中，我们要学会用真爱和宽容、热切与渴望、鼓励和信赖，去影响学生的生命轨迹，要善于用我们的才情去影响学生，濡染学生，唯有这样的影响才是深远的，才贴近教育本质。其实，教育中我们给予学生的，不仅仅是知识，还有生命的烙印。这些烙印，悄悄地藏匿在教师的一句话里、一个动作中，在将来的某个时刻，它们或许会突现出来，成为学生人生航程上的风帆与灯塔。

（作者单位：江苏扬州市八里中心小学）

随机生产模拟算法比较篇3

随机生产模拟于20世纪60年代末出现, 是电力系统规划工作中的重要工具, 用于模拟发电调度, 预测各发电机组在一段时期内的发电量期望值及燃料消耗量, 同时还可计算出该系统的可靠性指标。

随机生产模拟考虑了发电机组停运、负荷波动等不确定性因素, 很好地描述了电力生产中的随机性。在实际计算中, 有多种算法, 各算法有各自的优点与缺点, 本文将就两类常见的方法介绍对比。

2、随机生产模拟的基本原理

2.1 持续负荷曲线

随机生产模拟是以等效持续负荷曲线为核心的, 各类随机生产模拟的方法都以此为基础发展起来的, 该曲线综合考虑了发电机组的随机停运和负荷随机波动, 将两者结合起来从而形成等效持续负荷曲线。

在引入等效持续负荷曲线之前, 先对持续负荷曲线进行介绍。在得到负荷曲线时, 首先形成持续负荷曲线, 如图1所示的持续负荷曲线, 图中横坐标为系统负荷, 纵坐标为负荷的持续时间, T为模拟周期, 模拟周期根据具体的需要而定, 曲线上任意一点 (x, t) 表示系统负荷大于或等于负荷x的持续时间t, 即t=F (x) 。

用周期T除以上式, 得到

式中P可以看作系统负荷大于或等于x的概率。从而系统总负荷为

相类似的, 式 (2) 除以T, 可以得到负荷的平均值 (又称为期望值)

设系统在模拟周期T内投入运行的发电机总容量为Cs, 由图1得, 系统负荷大于发电机总容量的持续时间为

从而得到电力不足概率LOLP为

而相应的, 系统负荷大于发电机总容量时, 图1中的阴影部分的负荷需求, 从而得到电量不足期望值

2.2 递归卷积法

在实际运行中, 发电机组不完全可靠, 存在着随机停运, 因此, 需要考虑发电机组的随机停运状态, 并对原始持续负荷曲线进行修正, 得到考虑随机停运的等效持续负荷曲线。在修正等效持续负荷曲线时, 引入卷积的概念。式 (1) 为原始的持续负荷曲线f (0) , 设第一台发电机首先带负荷, 其容量为C1, 可用率为p1, 强迫停运率为q1=1-p1。

当该机组处于正常运行状态时, 它和其他发电机组所带的负荷由f (0) (x) 来表示。当机组1故障停运时, 系统负荷将由除去机组1剩下的发电机承担, 相当于机组1和其它发电机组共同承担了的xmax+C1负荷, 即曲线f (0) (x) 向右平移了C1, 即图2[1]中f (0) (x-C1) 曲线。

由于机组1可用率为p1, 强迫停运率为q1, 因此考虑其停运时, 等效持续负荷曲线变为:

同理, 可得到第i台发电机的卷积公式:

式中, Ci为第i台机组的额定容量, pi为第i机组的可用率, qi=1-pi, 为故障停运率。假设系统中有n台发电机, 当所有发电机组全部卷积后, 即可得到最终的等效持续负荷曲线f (n) (x) , 此时最大等效负荷为xmax+Cs, 而如图3[1]所示, 相对应的电量不足期望值和电力不足概率分别为:

3、等效电量函数法

上文阐述了随机生产模拟的基本原理。通过运用卷积法得到等效持续负荷曲线, 但为了保证计算精度, 计算过程需要大量的离散点描述持续负荷曲线, 计算量较大。而下文介绍的等效电量函数法在保证精度的基础上, 能够很好地解决计算量的问题。

3.1 等效电量函数法的基本原理

取机组容量的最大公因子Δx, 将横坐标x轴按Δx分段, 故根据2.2所述电量计算的公式, 可得离散化的电量函数:

式中J=+1, 表示不大于x/Δx的整数。E (J) 即为该段负荷对应的电量。若系统最大负荷为xmax, 则对应的离散变量值为:

电力系统负荷的总电量为:

等效电量函数同样是把发电机组停运影响考虑在内的函数, 因此同样需要根据每个机组的可用率来安排其运行。

由2.1已知, 原始持续负荷曲线的概率分布为f (0) (x) , 其对应的电量函数则为E (0) (J) ;故安排完第i-1台发电机组带负荷后得到的等效持续负荷曲线f (i-1) (x) , 所对应的电量函数为E (i-1) (J) 。因此根据 (8) 及 (27) 式, 可得

式中Ki=Ci/Δx。

式 (30) 即为等效电量函数法的卷积计算公式。

同理, 根据 (10) 及 (27) 可得第i台发电机组的发电量为:

式中Ji-1=xi-1/Δx, Ji= (xi-1+Ci) /Δx。

在安排了第i台机组以后, 前i台机组带了区间 (1, Ji) 的负荷, 此时系统尚未满足的负荷电量应为:

式中EDi为前i台机组带负荷后, 系统中尚缺的电量。将式 (30) 代入上式得到:

由 (32) , 可得安排前i-1台机组后尚未满足的系统负荷为

因此 (33) 式中第二项为第i台机组的发电量, 与之前的式 (31) 一致。从而

而系统的电量不足期望值为:

系统的电力不足概率LOLP的计算需要用于2.2中提到的等效持续负荷曲线f (n) (x) 来说明。因为该曲线为单调减小的曲线, 所以LOLP大于其右侧Δx领域内任一点的函数值, 从而也大于该区间内函数f (n) (x) 的平均值, 平均值为:

根据等效电量函数的定义, 上式可以改写为

同理, LOLP小于其左侧Δx领域内任一点的函数值, 从而也小于该区间内, 函数f (n) (x) 的平均值, 故平均值为:

由式 (21) 及 (22) 得到LOLP的上下限:

在很小的区间内, 等效持续负荷曲线可以近似看成线性, 故在用等效电量函数法进行随机生产模拟时, LOLP计算可由下式得到:

4、算例

最后采用IEEEReliabilityTestSystem算例中的数据进行模拟, 机组数为7, 模拟周期为一天 (如表1, 2) 。

等效电量函数法的根据递归卷积法推出的, 将其结果与递归卷积法的对比, 可知, 采用等效电量函数法计算精度上相差不大, 计算得到的各机组发电量都一样, 程序运行时间也较小。因此在进行随机生产模拟时, 采用等效电量函数法比较合适。

5、结语

本文介绍了随机生产模拟的基本原理, 并介绍了两类计算方法, 通过算例比较了它们的优劣。等效电量函数法在计算量和计算精度上都有明显的优势, 因此进行随机生产模拟时, 采用该算法比较合适。

参考文献

[1]王锡凡.电力系统优化规划[M].北京:水利水电出版社, 1990:125-182.

非重复随机数抽取算法研究篇4

在各种计算机软件系统中, 经常要用到随机数抽取的问题。如:从题库中抽题, 机动车摇号上牌等, 这些问题都要用到非重复随机数抽取算法。传统的抽取算法结构简单易懂, 但算法耗时长, 甚至当数据量大时, 存在着无法生成的可能。文中结出的几种算法, 可以有效的解决传统算法的不足问题。

1. 传统的算法

传统的算法原理:每次所抽取的数与前面已抽取的数进行比较, 相同保留, 不同则丢弃, 如此反复进行, 直到满足需求。此算法的时间复杂度为O (n2) , 若抽取个数接近样本空间, 到了抽取末期, 存在着因抽取数据与已抽数据频繁重复而无法完成任务的可能。

2. 下标移动算法

传统的算法的最大的问题就是数据重复性的问题, 若将样本空间的所有数据全部存储到一维数组中, 每抽取一个数, 就从样本空间移除这个数, 即从数组中移出这个数, 即可消除重复性问题。滑动窗口的随机数算法就是应用这种策略, 解决了抽取重复的问题。

滑动窗口的随机数算法可以解决抽取重复的问题, 该算法采用窗口从后向前滑动, 所需要的空间复杂度为O (n+m) , 若生成的随机数较大时, 所占的存储空间也比较大。采用下标移动算法, 所需要的空间复杂度为O (n) , 可以有效的节约存储空间。

2.1 算法原理

下面给出原理:

给定一组正整数, 区间为[1, n], 从中随机抽取m个非重复的数, 且m<=n。

初始化数组a存储这组正整数, k记录产生的随机数个数, 同时也是移动的下标

步骤1 k=1

步骤2在区间[k, n]产生一个随机数t, 将a (k与a (t) 对调。

步骤3 k=k+1, 若k>m算法结束, 否则返回步骤2

2.2 算法分析

移动下标k将区间[1, n]划分为[1, k-1]与[k, n两个空间, 通过k的移动, [1, k-1]空间变大, 满足了生成随机数的存储, [k, n]空间变小, 满足了样本的非重复性。其时间复杂度为O (m) , 符合非重复随机数抽取的需要。下面给出具体的C#代码。

3. 动态求解算法

下标移动算法实现非重复随机数抽取必须将样本空间全部存储蓄到数组中, 当样本空间数据个数n远大于抽取个数m时, 尚有n-m个数据不需要抽取, 但这些数据又占用着存储空间。

经过研究发现, 区间[1, n]的有序序列, 被抽取第k-1个数据后, 剩余的数据仍为有序序列, 用c来表示该序列, c序列不需要用一维数组来保存, 当抽取第k个数据时, 通过分析已抽取的数据与c序列之间的关系, 就可以动态求解出第k个数具体的值。使用该算法可以将空间复杂度降为O (m) 。

3.1 算法原理

下面给出原理:

给定一组正整数, 区间为[1, n], 从中随机抽取m个非重复的数, 且m<=n。

初始化数组a存储已产生的随机数, 数组b存储数组a的升序序列, k记录产生的随机数个数

步骤1 k=1

步骤2在区间[1, n-k+1]产生一个随机数t

步骤3在数组b中找出b (j) –j>=t的元素, 若找到直接进入步骤4, 否则一直找下去, 没有找到也进入步骤4

步骤4 a (k) =t+j-1

步骤5将a (k) 插入数组b中, 并保持数组b为升序

步骤6 k=k+1, 若k>m算法结束, 否则返回步骤2

3.2 算法分析

通过分析有序数组b与c序列的关系, c序列中第t位的元素, 其前面已抽取了j-1个数, 所以第t位的元素的值应为t+j-1;随着k值的变大, 样本区间[1, n-k+1]在变小, 符合非重复随机数抽取的需要, 步骤3由循环来完成, 该算法的时间复杂度为O (m2) 。下面给出具体的C#代码。

4. 结束语

传统的随机数抽取算法, 可靠性差, 只适合从大样本空间中抽取极少量的数据;下标移动算法时间复杂度低, 但空间复杂度较高, 可靠性强, 特别适合从大样本空间中抽取大量的数据;动态求解算法时间复杂度较高, 但空间复杂度低, 可靠性强, 算法较复杂, 特别适合从大样本空间中抽取一部分数据。下标移动算法与动态求解算法都可以完成非重复随机数抽取, 在具体的应用中, 开发者可以根据自己的需要, 选择合适的算法, 高效灵活的解决实际问题。

摘要：介绍了传统随机数抽取算法的原理, 给出了下标移动算法与动态求解算法的原理, 对他们进行了分析, 并给出了C#代码, 分析了他们的优劣与适用范围。

关键词：随机数,非重复,抽取,下标移动,动态求解

参考文献

[1]彭绪富.基于窗口的随机数抽取算法研究.计算机工程与设计, 2007, 28 (3) :526-527

一个基于多种运算的随机密码算法篇5

本文采纳各类密码算法的长处,摒弃它们各自的缺点,设计了一个基于多种简单运算、安全性高、加解密处理效率高的随机密码算法,相对有效地解决了当前各种密码算法存在的问题。

1 密码理念和设计方案

1.1 密码理念

密码技术可以保证信息的机密性、完整性和责任性。所有密码算法的加密目标都在于,“即使未经授权的人获得加密的信息并知道用来加密它的算法,要想获得对信息的访问也会非常困难。”[5]。

密码体制的实用性应该从以下两点考虑:

1)加解密算法的通用性和处理效率。

2)“体制的安全性只依赖于密钥的保密”[6],而不在于算法的保密。

1.2 设计方案

基于以上的密码理念,本文着重从加解密算法的安全性、通用性、经济指标及其处理效率出发,结合目前各种强有力的密码分析技术如差分密码分析、(非)线性密码分析和基于统计特性的密码分析等,同时吸取多种经典密码算法的优点,设计出一种不同于其他随机密码技术的基于一次一密的密码算法。

1)为了保证算法的安全性,即能够抵抗各种密码分析,应该使密文尽可能地复杂化,这里乘积密码技术(即以某种方式连续执行两个或多个密码,以使得所得到的最后结果或乘积从密码编码的角度比其任意一个组成密码都更强)是一个很好的典型。

2)密码算法的经济指标和处理效率需要从算法的计算量、加解密的速度、软硬件实现条件等方面去考虑。

3)算法的通用性侧重于算法的表达能力。

2 密码算法的描述

2.1 基本概念和符号约定

1)余数用S表示;除数用D表示;乘数用M表示。

2)密钥K由四个子密钥组成,即k1k2k3k4,而且顺序不能改变。其中,k4是余数S;k3表示除数D或乘数M;k2是表示换位方式的函数T(l1,l2)或R(l1,l2,---,lm),这里T(l1,l2)表示把某字符串中的l1和l2位置所指向的字符进行交换,R(l1,l2,---,lm)表示把某字符串中的l1,l2,---,lm各个位置所指向的字符进行循环交换,即l1=l2,l2=l3,---,lm=l1,其中l1,l2,---,lm大小可以随机排列,以增大破译的难度。k1是用来表示与余数S进行异或运算的各子串的起始位置的定位函数I(li,lj,---,lx)。

2.2 加密过程

1)假设明文P=p1p2---pn,把它表示为ASCII码值。先随机选择一个数作为余数S,即k4。为了使密文具有较高的保密性,S位数一般在4位以上且各位数尽量相异。然后根据n的大小来选择第一次加密采用除法还是乘法运算,除数D和乘数M的位数根据明文的长度来合理选择。具体实现过程如下:

#define N 30//N值可以根据具体情况来设定

这样产生了第一次密文C。

2)从C中随机选择需要换位的位置以及换位方式,通过换位产生第二次密文C’。可用C语言表示如下:

l1,l2,---,lm散布范围尽量大些且相邻位置所指向的数字要相异,这样才能有效地保证密文的安全性。

3)在C’中随机选择一些子串的起始位置,产生k1=I(li,lj,---,lx),li,lj,---,lx散布范围也应该尽量大些,并按从左到右的顺序依次与余数S进行异或运算,则C’转化为C’’,C’’为待发送的密文。C’’要用十六进制表示,这是因为异或运算的结果若仍用ASCII码表示就可能出现溢位,这样会使接收方无法正确解密。

同时产生密钥K=k1k2k3k4,为了减少密钥长度,可以简化K的格式,即省略k1,k2,k4的首字母和双括号,但为了接收方能够正确判断第一次密文C进行的是何种运算,k3的首字母不可省略,不过可以省略其双括号。同时在子密钥间用分号隔开。即:K=li,lj,---,lx;l1,l2(,---,lm);D(M);S。

最后把密钥K通过安全信道发送给接收方,并将密文C’’通过普通信道发送到接收方。

2.3 解密过程

接收方收到发送方传送过来的密钥K和密文C’’后,使用K按照与加密完全相反的运算顺序对密文进行解密。

1)首先利用k1=I(li,lj,---,lx)按从右到左的顺序与k4进行异或运算,产生C’。值得注意的是,由于各子串间可能部分重叠(其实这种情况会增大了破译密码的难度),因此必须按与加密时相反的运算次序进行异或运算,以保证C’’准确无误地转化成C’。

2)然后根据k2=T(l1,l2)或R(l1,l2,---,lm)将C’中各位还原到原来的位置,得到C。

3)最后依据k3的首字母,判断原文P进行何种运算,如果采用乘法,则有:

P=(C-S)/M

如果采用除法,则有:

P=(C-S)*D

这样接收方就可以得到明文P,即发送方要表达的信息。

3性能分析

1)与其他的密码算法不同,该算法不是在加密前就事先选定某密码,而是在加密过程中根据合理的方案逐步产生子密钥,从而具有一定的随机性和高安全性。

2)由于该算法只采用了三个非常简单的运算,便于软硬件的实现,因此加解密的处理速度比许多经典的密码算法要快得多。

3)此算法采用了综合三个不同运算的技巧,不但掩盖了语言的统计特性,如在英语中最常用的是字母e,其次是t,a,o,n等,避免了基于语言统计特性的密文分析;而且满足严格的雪崩效应;更重要的是,它给出了对于穷举攻击的高复杂度。例如,在一个待发送密文长度为100位(十六进制)、余数为8位数,除数为6位数、换位位数为5、进行异或运算的子串数为6的信息中,即使密码破译者知道了它们各自的位数和子串数,其穷举攻击的复杂度是非常高的,即约为9*107*9*105*P(100,5)*P(100,6),约为1037。

4 示例验证

假定要加密的信息为:P={PLEASE GO TO THE BANK}。为了方便起见,这里假设的明文长度较短。该明文的ASCII值为:{8076 69 65 83 69 71 79 84 79 84 72 69 66 65 78 75}。

1)令S=5136,因为P长度较短,所以宜采用乘法运算,令M=20。根据C=P*M+S得到C={16 15 33 93 16 73 94 35 96 9596 94 53 93 33 16 26 36}。

2)由于S位数较少,为了加强保密性,宜采用循环交换R(l1,l2,---,lm),令R(6,16,27),即把第6位的3换作5,把第16位的5换作9,把第27位的9换作3,这样得到C’={16 15 35 9316 73 94 39 96 95 96 94 53 33 33 16 26 36}。

3)令I(1,3,23,31),即将100F(1615的十六进制)与3324(5136的十六进制)进行异或运算得到的结果是232B,再将2B23与3324异或得到1807,接着把5E35(9453的十六进制)与3324异或得到6D11,最后把101A(1626的十六进制)与3324异或得到233E。则产生待发送的密文C’’={23 18 07 5D 10 49 5E27 60 5F 60 6D 11 21 21 23 3E 24}。

4)同时生成密钥K=1,3,23,31;6,16,27;M20;5136。发送方把密钥K通过安全信道发送给接收方,并将密文C’’通过普通信道发送到接收方。

5)接收方收到发送方传送来的密钥K和密文C’’后,先利用k1=I(1,3,23,31)和k4,把C’’转化为C’={16 15 35 9316 73 94 39 96 95 96 94 53 33 33 16 26 36}。

6)接着利用k2=R(6,16,27),把C’变换为C={16 15 3393 16 73 94 35 96 95 96 94 53 93 33 16 26 36}。

7)最后利用k3和k4把C还原为明文P={80 76 69 65 8369 71 79 84 79 84 72 69 66 65 78 75},亦即PLEASE GO TO THE BANK。

由于本示例中明文长度很短,因此从密钥长度跟明文长度差不多的角度来看,此算法没能体现出它的优点。然而在现实通信中,信息明文长度一般比较长,此时该算法就体现出其强大的优越性。

5 结束语

本文通过比较分析各类密码技术的优缺点,设计出一个综合性能好的基于三种简单运算的随机密码算法。它有效地防御各种密码分析,具有很高的安全性和较好的实用性。然而该算法也是属于对称密钥密码体制,有它自身的一些缺点,如密钥管理与分配等问题。因此,密钥必须通过安全的信道来传送。

摘要：本文着眼于密码体制的实用性,设计了一个基于四则运算、换位、异或等多种运算的具有一定的随机性的密码算法。它在具有高效率的加解密处理的同时给出了对于穷举攻击的复杂度,保证了算法对各种密码分析的安全性。

关键词：简单运算,随机密码,加解密,密钥,算法

参考文献

[1]袁家政.计算机网络安全与应用技术[M].北京:清华大学出版社,2002.

[2]卢开澄.计算机密码学[M].北京:清华大学出版社,2003.

[3]罗毅.信息安全与密码算法[J].湖北教育学院学报,2006,23,(08):37-39.

[4]戚君贤,周建钦.密码理论算法综述[J].电讯技术,2006,(05):18-22.

[5]Maiwald.E著.马海军,王泽波,等译.网络安全基础教程[M].北京:清华大学出版社,2005.

位数随机的有效数字自动运算算法篇6

关键词：位数随机的有效数字,科学记数法,四舍六入五配偶,数值多项式

0 引言

物理实验数据的计算机自动处理不仅有利于大学生将实验的重点放在实验的操作环节上,还有利于为大学生物理实验数据处理的计算机自动评估提供精确而客观的参考标准[1,2,3]。其中有效数字的计算机自动处理是物理实验数据处理中不可缺少的重要环节。

由于各种物理实验测量仪器最小刻度值的单位不一定相同,这就造成了各种直接测量数据的有效位数也可能不相同,对这些数据进行运算处理时,运算的结果可能需要用科学记数法来表示[4]。

例如,在乘除幂运算的结果中,误差位可能高于个位,这时就必需要用科学记数法来表示该运算结果。如在21.3×456.7=9 727.71中,由于运算数据的有效数字位数最少的是3位(如数据“21.3”),则运算结果就只能取3个有效数字[4],即运算结果的十位就是误差位了,运算的有效结果只能用科学记数法表示为9.73×103。计算机在自动处理这种情况下的运算时,除了自动计算外,还要能够自动将计算结果转换成科学记数法的形式,即将9 727.71转换成9.73E+3[5]的形式,其中,E表示底数10,+3表示10的指数(即数量级表示)。

目前的计算机语言系统本身具有有效数字自动处理的功能,即能够自动将运算结果转换成科学记数法的形式,但它只能对计算机中有效位数固定的数据类型进行处理,如整型、浮点型、双精度型数据等[5]。只有运算结果的数值位数超过了这些数据类型所能存储的范围时,计算机才会将该数据自动转换成科学记数法的有效数字表示形式。然而,这些类型数据的有效位数与物理实验数据的有效位数不一定相同,因为,物理实验数据的有效位数受实验精度的影响,位数具有随机性。因此,必须根据这种数据的随机有效位数来研究其计算机处理算法。

提出一种位数随机的有效数字的自动运算算法,它包括有效数字运算结果的科学记数表示算法、有效位数的取舍算法、数据表示形式的转换算法以及不同位数有效数字的运算算法。实验结果表明,算法运算的结果与人工运算的结果完全相同,算法符合物理实验数据处理的要求。

1 算法描述

在物理实验数据处理中,加减运算结果的末位与运算数据中最先出现的可疑位相同,乘除运算结果的有效数字个数与乘除运算数据中有效数字个数最少的相同,幂运算结果的有效数字与幂底数的有效数字相同[4]。

算法1 有效数字个数的计算

从左至右(即从数据的最高位到最低位)搜索单个数据中的每一个数字,当搜索到第一个不为零的数字时,有效数字的个数计为1(n=1)。此后,每搜索到一个数字,有效数字的个数就加1,即n=n+1。若搜索到的字符为“E”,则终止搜索,否则一直搜索完整个数据。数据搜索结束后的n值即为该数据的有效数字的个数,数据中有效数字的最后(或最低)一位即为可疑位或误差位。

算法2 误差位的定位

在数据的表现形式中,误差位总是出现在个位或更低的位数上。因此,从左至右(即从数据的最高位到最低位)搜索单个数据中的每一个数字,当搜索到小数点时开始计数误差位,此时计m=0,往后每搜索到一个数字,m就减1,即m=m-1。若搜索到的字符为“E”,则终止搜索,否则一直搜索完整个数据。搜索终止时,数据的误差位就为m,若没有搜索到小数点,则m=0,即误差位在个位上。m=-1时,小数点后第1位是误差位,m=-2时,小数点后第2位是误差位,…。

算法3 数据的科学记数法表示

当数据的绝对值小于1时,如0.00056082。第一个不为0的数字(如“5”)的前面“0”的个数(=4)即为该数据科学记数法中负指数的大小,即:

5.6082×10-4

当数据的绝对值大于1时,如56 082 394.107。从与第一个不为0的数字(如“5”)相邻的数字开始直到个位的所有数字的个数(=7)即为该数据科学记数法中正指数的大小,即:

5.6082394107×107

为便于数据中每一位数字的提取和识别,先将该数据转换成字符型的字符串d1,d2,…,dL[5],其中L为字符的长度。从左至右(即从数据的最高位到最低位)搜索提取并识别字符串数据中的每一位数字字符dn[5],若第1位字符d1=“0”,则该数据为绝对值小于1的数据,记指数为index=-1,往后每搜索的1位字符dn若为“0”,则指数减1,即index=index-1,直到搜索到第1个不为“0”的字符dn为止。当搜索到第1个不为“0”的字符时,重建新的数据字符串string,此时令string=dn+“.”,“.”为小数点字符。往后每搜索到1位字符dn,string就增加1位字符dn,即string=string+dn;若第1位字符d1≠“0”,该被搜索的数据即为绝对值大于1的数据,此时记string=d1+“.”,并令index=0。往后每搜索到1位不为“.”的字符dn,则string=string+dn,且在搜索到“.”之前,每搜索到1位字符dn时,则index=index+1,当搜索到“.”时,则停止指数的累加。当数据搜索完后则可得科学记数法的数据字符串为string=string+“E”+Str(index),设Str()为将数值型数据转换成字符型数据的转换函数[5]。算法流程如图1所示。

算法4 四舍六入五配偶的处理

数据运算结果的有效位数由运算数据的有效位数来决定,运算结果的有效位数决定后就有可能要涉及到运算结果有效数字的取舍问题,运算结果有效数字的取舍要遵循有效数字的取舍原则——四舍六入五配偶[4],取舍算法如下:

从左至右(即从数据的最高位到最低位)搜索运算结果数据中的每一位数字,每搜索到一位数字或小数点就按原来的顺序与前面搜索到的数字排列成一个字符串,即string=string+Str(dn),其中,dn是搜索到的当前位数字。当搜索到第1个可疑位(数据运算后的结果可能不止一个可疑位)处的数字dn时,则检查该可疑位后面1位相邻的数字。若该数字大于5,则dn+1,string=string+Str(dn+1),并终止搜索;若该数字小于5,则dn不变,string=string+Str(dn),并终止搜索;若该数字等于5,则再检查该数字后所有位处的数字,直到遇到字符“E”为止(若“E”存在的话),其中只要有一位数字大于0,则dn+1,string=string+Str(dn+1);若全为“0”或无数字,则检查dn的奇偶性。若dn为奇数,则dn+1,string=string+Str(dn+1),若dn为偶数,则dn不变,string=string+Str(dn)。完成四舍六入五配偶的处理后,则提取字符串string。若不存在指数部分“E+index”(index为不等于零的正负指数),则string就为取舍的结果;若“E+index”存在,则提取之,取舍的结果就为string=string+“E”+Str(index)。

算法5 数据表示形式的转换

在有效数字的加减运算中,为确定运算结果的误差位,往往需要将运算数据转换成统一的形式,如:

2.34×103+1.8976-2.68×101

=(2.34+0.0018976-0.0268)×103=2.32×103

上式中,运算数据全部转换成103形式,可知最高误差位在小数点后第二位处(如数据“2.34”)。这样,为保持每个运算数据的误差位不变,以运算数据中幂指数最大的为准(如“103”),将各数据全部转换成该最大指数的形式。这样,运算结果的误差就在小数点后的第二位处(如“2.32×103”)。转换算法如下:

设原数据的指数为n,当改为m(m>n)时,则数据中的小数点向左移m-n位,亦即数据左边增加了m-n个“0”。

$d_{0} \cdot d_{- 1} d_{- 2} \dots d_{L} \times 10^{n} = \underset{m - n 个 “ 0 ”}{0.00 \dots 0} d_{0} \cdot d_{- 1} d_{- 2} \dots d_{L} \times 10^{m}$

算法6 有效数字的运算

考虑到运算结果的误差位可能高于个位的情况,将每一步的运算结果都转换成科学记数法的表示形式,再对该形式的数据进行有效数字的取舍处理。运算算法如下:

从左至右搜索数值运算式字符串中的每一个字符,若字符不为“+”、“-”、“*”、“/”、“^”,则该字符为运算数据中的一个数字或小数点,一般以字符“+”、“-”、“*”、“/”、“^”为断点搜索提取运算式中的每一个数据。当搜索的字符为“+”或“-”时,则检查其前一位相邻的字符,若前一位字符为“E”,说明数据为科学记数法表示,则继续往后搜索;若不为“E”,则“+”或“-”处就为数据提取的断点。先对运算式中的乘除幂运算项进行运算,对乘除运算数据、幂中的底数数据运用算法1来计算各数据的有效数字个数ni,记下其中有效数字最少的个数min{ni},对这些数据进行乘除幂运算后所得结果的有效数字的个数则为min{ni},运用算法3将运算结果用科学记数法表示,运用算法1、4和min{ni}来选取该运算结果的最后一位,提取该有效数字,将其代替并放置在该乘除幂运算项位置处,组成新的只含有加减运算的数值运算式。运用算法5统一各加减数据中的指数表示形式,运用算法2计算该加减运算式中的每一个数据的误差位mi,记下其中位数最高的误差位max{mi}。对这些数据进行加减运算,运算结果的误差位则为max{mi},运用算法2、4和max{mi}来选取该结果的最后一位。算法流程如图2所示。

2 实验及其结果

为验证以上算法,采用VB6.0开发了一个有效数字运算式的输入与运算界面系统,如图3所示。在“有效数字运算式” 文本框中输入有效数字运算式的文本形式,按下“数据运算”按钮,则将运算结果显示在按钮下面的列表框中。根据运算优先级,先对运算式中的幂进行运算,再对乘、除进行运算,最后是加、减运算。每运算一步则显示一步的运算结果,以便人工检查。从图中可以看出,运算结果符合算法的思想,且与人工运算结果相同。

列表框中的第0行为原数值运算表达式,系统首先计算每个加减项中最少的有效数字位数,第1项“5.24^2*6.25/1.25”中的最少有效数字位数为3位,如数据“5.24”、“ 6.25”、“1.25”都是3位有效数字。第2项“8.95^4”只有1个运算数据“8.95”,其有效数字位数是3位,则该项最少的有效数字位数就是3位。第3项“12.5*3.252016”中有效数字位数最少的数据是“12.5”,有效数字位数是3。第4项“2.4736”是1 个数据,有效数字位数是5位。第5项“40.4625/3.25”中有效数字位数最少的数据是“3.25”, 有效数字位数是3。它们都是各项运算结果的有效数字取舍的依据。

列表框中的第1行是原式中幂运算的结果,幂运算是该式子中运算优先级最高的运算。在原式的第1个加减项“5.24^2*6.25/1.25”中,幂的运算结果为“27.4576”,则得出第1 行中的第1个加减项“27.4576*6.25/1.25”的表现形式。而原式中的第2个加减项只有幂1种运算,则“8.95^4”的运算结果必须用有效数字来表示,运算结果只能取3个有效数字。

纯数字运算的结果为“6 416.41050625”,取3个有效数字,则说明误差在十位上,此时必须用科学记数法来表示,根据有效数字的取舍的原则,取为“6.42*10^3”。

列表框中的第2行是除法运算的结果,第1 加减项“27.4576*6.25/1.25”的结果为“27.4576*5”。而第5个加减项“40.4625/3.25”只有除法1种运算,因此,其运算结果要用有效数字表示。其纯数学运算结果为40.4625/3.25=12.45,由于结果只能取3个有效数字,因此,根据四舍六入五配偶的原则,“5”是最后一位数字,且其前位数字是偶数“4”,因此舍去“5”,结果为“1.24*10^1”。

列表框中的第3行是乘法运算的结果,第1个加减项“27.4576*5”的纯数学运算结果为137.288,由于其最终运算结果取3个有效数字,因此,结果为“1.37*10^2”。第3个加减项“12.5*3.252016”的纯数学运算结果为40.6502,由于结果取3个有效数字,则误差位在小数点后第1位“6”处,由其后1位是“5”,且“5”后有不为0的数字“2”,则进位,结果就为“4.07*10^1”。

列表框中的第4行是将各加减项运算数据的形式统一化成10^3数量级的形式,可得有效数字的最高误差位在小数点后第2位处(如括号中的数据“6.42”),则加减运算的最终结果的有效数字的误差位也就在小数点后第2位上,如列表框中第5行的最终运算结果“-6.23*10^3”所示。

用文中设计的软件系统对位数随机的有效数字的多项式运算进行了大量运算实验,运算结果都服从有效数字运算的原则,运算正确率为100%。

3 结语

(1) 实验结果表明本文算法符合有效数字运算的原则,满足位数随机的有效数字的运算要求,且运用该算法的运算结果与人工运算的结果完全相同。在有效数字的多项式运算方面,该算法满足位数随机的物理实验数据处理的要求。

(2) 本文设计的系统是为了说明有效数字的运算情况而分步显示各运算步骤的,以便人为验证每个运算步骤的正确性,这些步骤也是物理实验数据处理中数据运算处理的步骤,是最终运算结果的理由步骤。

(3) 输入的运算数据不一定要用科学记数法来表示,但运算的结果必须要反映出有效数字的个数以及误差位,若误差位高于个位时,运算结果就必须要用科学记数法来表示,如图3中第2个加减项的运算结果“6.42*10^3”就属于这种情况。

参考文献

[1]黄天成,袁斯昊,张琴,等.大学物理实验数据计算机检验、处理系统的研制[J].大学物理实验,2010,23(1):74-76.

[2]牛原,肖霖,成正维.大学物理实验数据处理系统[J].大学物理实验,2008,21(1):91-93.

[3]熊万杰,黄振中.用Origin软件处理物理实验数据[J].大学物理实验,2004,17(2):65-67.

[4]刘传安.英汉大学物理实验[M].天津:天津大学出版社,2005.

随机化算法论文篇7

OFDM (Orthogonal Frequency Division Multiplexing) 是一种并行的多载波传输技术, 它通过相互正交的多个子载波来传输信息, 使受到干扰的信号能够可靠地接收。目前, OFDM技术已经成功地应用于数字音频广播 (Digital Audio Broadcasting, DAB) 、数字视频广播 (Digital Video Broadcasting, DVB) 、无线局域网 (Wireless Local Area Network, WLAN) 等高速率数据传输系统中。

OFDM的不足之处主要表现在对定时和频率偏移敏感和高峰均功率比 (Peak to Average Power Ratio, PAPR) 。较高的PAPR会导致发送端对高频放大器 (HPA) 的线性要求很高而且发送效率极低, 接收端对前端放大器的线性要求也很高而且会增加D/A和A/D转换器的复杂度。

目前已有的降低OFDM信号PAPR值的方法大致可分为三类:最简单的方法就是通过对OFDM信号进行限幅来降低PAPR值, 但限幅引入了非线性失真, 导致系统的误码率性能下降;分组编码类方法降低PAPR的基本思想是将原来的信息码字映射到PAPR较小的序列来进行传输, 从而避开会使OFDM信号出现峰值的码字, 编码技术[1]的计算复杂度非常高, 编解码麻烦且使信息速率大大降低, 只适用于子载波数目较小的情况;信号扰码类方法则着眼于降低OFDM信号峰值出现的概率[2], 可有效降低信号的PAPR值又不对信号产生畸变, 尽管其计算复杂度较大, 但随着数字信号处理技术的发展, 该技术最有希望解决OFDM系统中的峰均比问题。部分传输序列 (Partial Transmit Squence, PTS) 法就属于信号扰码类技术, 本文提出了将随机分割子序列的分块方法与迭代移位搜索加权因子方法相结合的改进PTS算法, 通过仿真证明改进方法降低了系统的PAPR。

1 PAPR基本原理

OFDM系统中的PAPR是指OFDM信号的峰值功率与平均功率的比值, 因此PAPR可定义为:

$Ρ A Ρ R (d B) = 10 \lg \frac{\max {| x (t) |^{2}}}{E {| x (t) |^{2}}}$

式中:x (t) 代表一个OFDM符号的波形, 分子表示x (t) 的最大瞬时功率, 分母表示x (t) 的平均功率[2]。对于包含N个子载波的OFDM系统来说, 当N个子载波都以相同的相位求和时, 所得符号的PAPR (dB) 就是平均功率E{|x (t) |2}的N倍。因此, 基带信号的PAPR可以表示为PAPR=10lg N。可见当N较大时, OFDM系统的PAPR就会很高。

根据中心极限定理, 当子载波数N较大时 (一般取N>64) , OFDM信号的包络服从瑞利分布, 其功率服从均值为零、自由度为2的χ2分布, 其分布函数的数学表达式为F (z) =1-e-z。在实际应用中, 习惯用PAPR超过某一门限值PAPR0的概率即互补累积概率分布函数 (CCDF) 来表征PAPR的分布, 其表达式为:P (PAPR>z) =1- (1-e-z) N。

2 降低PAPR的PTS算法

PTS原理如图1所示。输入数据块X被分割成M个不相交子块, 每一块进行IFFT变换后的时域信号再乘以相位序列叠加合并来降低PAPR。 PTS方法是要通过适当地选择辅助加权系数, 使得峰值信号达到最优化。

文献[3]中所提到的降低OFDM系统峰均功率比的PTS方法是将输入的数据符号分割成几个子块, 并分别给每一子块乘以不同的权值, 然后通过选择适当的权值来减小传输信号的PAPR。现已提出很多方法来减少其运算的复杂度, 如在文献[4]提出次优化方法寻找加权系数, 其加权系数取值范围只限于[+1, -1]。还有文献[5]提出的格形因子搜索的方法, 文献[6]提出的迭代移位线性搜索法及文献[7]提出的循环移位线性搜索法。

3 基于随机分割的PTS改进算法研究

PTS-OFDM系统中有三种分割子块的方法:相邻分割法、随机分割法和交织分割法[8]。相邻分割法是把N/M个连续的子载波按顺序分别分在同一个子块里面;随机分割法中每个子载波被随机地任意分配到M个PTS内;交织分割则将相邻间隔为M的子载波分配到一个子块中。

以上提到PTS的三种不同分割方法中, 如其他条件一致, 随机分割方法在降低OFDM系统PAPR的性能方面最佳, 如图2所示。

本文在随机分割方法的基础上, 对最优加权系数的寻找方法进行了改进。

3.1 原PTS方法的遍历搜索过程

(1) 将N个子载波随机分割为M个子序列, 相位因子bm=±1;

(2) 令bm=1 (m=1, 2, …, M) , 计算此时的峰均功率比PAPR0;令b1=-1, 且计算此时的PAPR1;如果PAPR1>PAPR0, 则b1=1, 否则b1=-1不变;

(3) 按照同样方法依次优化bm (m=1, 2, …, M) , 当优化完bm后, 完成搜索。

3.2 新PTS方法的遍历搜索过程

(1) 将N个子载波随机分割为M个子序列, 相位因子bm=±1 (m=1, 2, …, M) ;

(2) 令b2i-1=1 (i=1, 2, …, M/2) , b2i=-1 (i=1, 2, …, M/2) , 计算此时的峰均功率比PAPR0;令b1=-1, 且计算此时的PAPR1;如果PAPR1>PAPR0, 则b1=1, 否则b1=-1不变;

(3) 按照同样方法依次优化bm (m=1, 2, …, M) , 当优化完bm后, 完成搜索。

上述两种方法利用随机分割子序列的方式将N个子载波分割为M个子序列, 降低了双层搜索法[9]的复杂度, 虽然对系统PAPR的改善有所降低, 但是在实际应用中仍是可行的。

为了描述改进方法对OFDM信号峰均功率比的改善情况, 本文进行了计算机仿真, 仿真的条件是:子载波数为N=128, 子块M=4, 调制方式采用QPSK调制。

由图3的仿真分析可知, 新方法的CCDF性能优于原随机分割法的CCDF性能, 在CCDF=10-4时, PAPR改善了近0.5 dB。

4 结语

本文提出了一种降低OFDM信号峰均比的改进算法, 该算法降低了PTS系统双层搜索法计算复杂度, 改善了原随机分割法的CCDF性能。

摘要：正交频分复用 (OFDM) 系统的一个主要缺点是信号的峰均功率比 (PAPR) 很高。提出了一种将随机分割方法与迭代移位搜索加权因子相结合的改进PTS算法。仿真结果表明, 改进后的算法在改善PAPR性能和计算的复杂度之间取得了较好的折衷。

关键词：正交频分复用,峰均功率比,部分传输序列,随机分割方法

参考文献

[1]DAVIS J A, JEDWAB J.Peak-to-meanpower control anderror correction for OEDM transmission using Golay se-quences and Reed-Muller codes[J].Electronics Letters, 1997:267-268.

[2]邵佳, 董辰辉.Matlab/Simulink通信系统建模与仿真实例精讲[M].北京:电子工业出版社, 2009.

[3]MULLER S H, BAUML R W.OFDM with reduced peak-to-average power ratio by multiple signal representation[J].In Annals of Telecommunications, 1997, 52 (1) :58-67.

[4]CIMINI L J, SOLLENBERGER N R.Peak-to-averagepower ratio reduction of an OFDM signal using partialtransmit sequence[J].IEEE Commun.Lett., 2000, 4 (3) :86-88.

[5]WU Bing-yang, CHENG Shi-xin.Patrial transmitting se-quence method based on trellis factor search[J].Journal ofSoutheast University, 2005, 21 (2) :123-126.

[6]尹东辉, 褚姝韫, 崔伟.降低OFDM系统中峰平比方法研究[J].科技广场, 2006 (11) :14-16.

[7]王裕民.OFDM关键技术与应用[M].北京:机械工业出版社, 2006.

[8]MULLER S H, HUBER J B.OFDM with reduced peak-to-average power ratio by optimum combination of transmit se-quences[J].Electronics Letter, 1997, 33 (5) :368-369.

[9]HOWS, MADHUKUMAR A S, Chin F.Peak-to-averagepower ratio reduction using partial transmit sequences:asuboptimal approach based on dual layered phase sequencing[J].IEEE Trans.on Broadcast., 2003, 49 (2) :225-231.

随机化算法论文篇8

随着计算机科学、微电子技术和密码学的迅猛发展,信息安全理论不断丰富,技术不断完善,地位作用日益凸显。认证技术是信息安全的重要方面,主要用于鉴别用户的身份信息,从保证通信网络安全的角度来说,认证技术比信息加密更加普遍,更加重要。

身份认证时指验证用户或设备(如客户机、服务器、交换机、路由器、防火墙等)身份的过程,包括识别和验证两个方面[2]。在通信网络中,通信设备的身份信息是用一组特定的数据来表示的,系统只能识别设备的数字身份,所有的设备身份认证就是针对设备数字身份的认证,用于保证接入设备的物理身份与数字身份相对应。作为通信网络的安全防护措施,身份认证具有举足轻重的作用。

与静态身份认证相比,动态身份认证在身份认证过程中加入不确定因素,每次认证时传送的信息都不相同,提高认证过程的安全性[3]。动态身份认证技术提供一次一变的身份认证方式,选择不同的不确定因子将构成不同方式的认证系统。

动态身份认证的主要机制是基于某种加密算法,将用户的身份代码和某种不确定因素作为密码算法的输入参数,经过算法变换得到一个变化的结果,即动态口令,将其作为用户的登录口令;认证服务器使用相应的算法进行计算并将计算结果与用户的登录口令进行匹配。不重复的动态口令不断变化,一个口令只能使用一次,不能重复使用。目前主要有三种认证方式[4],包括哈希链方式、同步方式和异步方式。

(1)哈希链方式:动态口令为前后相关的单向序列,系统记录一定数量的口令进行匹配。该方案易于实现,无需专用硬件支持,但其安全性依赖于单向哈希函数,不宜在分布式网络环境使用,而且认证过程需要多次调用哈希函数,运算量较大。

(2)同步方式:将时间戳作为不确定因子,认证服务器与用户端的时钟保持同步,按照约定的算法可以计算出相同的动态口令。该方案操作简单,适用于单向数据传输,但需要严格的时间同步,数据传输超时会造成认证失败。

(3)异步方式:服务器向用户端发送一组随机数作为不确定因子,用户端通过特定的算法计算出口令后返回服务器。该方案用户端设备简单,无需时间同步,但必须具备数据回传条件。

对于接入固定通信网的普通话机来说,由于受到制造成本和通信线路的限制,无法直接应用现有的动态认证方法。因此,我们提出了一种基于随机密钥栅栏算法的身份动态认证机制,成功应用于电话末端综合预警系统[5]中,实现了话机的动态身份认证。

1 随机密钥栅栏算法

传统的栅栏加密算法,就是把要加密的明文分成N个一组,然后把每组的第i个字连起来,形成一段无规律的密文,解密的方式就是进行一次逆运算。

密钥栅栏算法在传统栅栏加密算法的基础上,按照密钥确定栅栏算法的加密规则,将栅栏分割的固定长度和顺序更改为可变长度和顺序。加密强度随着密钥的长度呈阶乘式增长,以较少的计算量增加了更多的不确定性,大大提高了加密强度。

随机密钥栅栏算法在密钥栅栏算法的基础上,随机产生两个字节的数据,然后根据这两个字节数据进行重新计算和排序获取的新密钥才是最终的加密密钥,而且新密钥的长度并不固定,可以为2到16位。原始数据在通过栅栏算法分割成多段后,会根据密钥包含的排列顺序重新打乱再进行发送。

该算法在用户端进行加密的过程中,主要的计算形式为比较和排序,在单片机中能轻松实现,运算速度快,运行时间短,硬件资源消耗少,占用时间短,不会对系统造成太大的负担。

2 双重身份认证机制

该系统采用双重身份认证机制,分为注册阶段和认证阶段。首先,在注册阶段,采用话机内部芯片的UID唯一标识符作为话机的数字身份,在服务器端对入网话机进行授权,作为动态身份认证的基础数据。然后,在认证阶段,在话机接入固定通信网后,采用周期轮询和定制查询相结合的方式对用户端进行二次身份认证。

身份认证中的电路设计集成了CPU、E2PROM、RAM、ROM和COS等软硬件,不仅具备数据读写和存储功能,而且能完成数据处理。动态认证采用异步方式的原理,由服务器发起认证请求,用户端进行响应。服务器实现的功能主要包括用户注册授权,发送认证请求、接收认证信息,验证用户身份,提交认证结果等。用户端实现的功能包括接收认证请求、发送认证信息等。

在系统中,监测设备作为服务器,话机作为客户端,具体认证流程如下:

监测设备和话机之间的动态认证流程如图1 所示,当监测设备首次向话机发送身份认证请求,话机回送经过初始密钥key0加密的身份数据和通信密钥key1,监测设备使用初始密钥key0解密身份数据,并记录通信密钥key1,然后将身份数据上传服务器进行身份认证,本次身份认证完成。

当监测设备再次向话机发送身份认证请求,话机回送经过通信密钥key1 加密的身份数据和通信密钥key2,监测设备使用通信密钥key1 解密身份数据,并记录通信密钥key2,同样由监测设备进行身份认证,并继续循环下去。

话机在每次向监测设备发送的数据中,需要添加下次通信的加密密钥,监测设备接受后进行暂存,作为下次通信的解密密钥,同时有效避免了加密密钥信息重复过多的问题。如果监测设备发现数据解密密钥错误,会立即向话机发送重置密钥的指令,话机会使用预设的初始密钥重新传送数据。

3 安全性分析

从网络管理的角度看,该机制具备以下功能:

(1)身份认证功能,监测设备能实时、不间断地对话机身份进行验证,保证话机设备身份的合法性;

(2)信息机密性,在通信线路上传输的信息都是密文形式,一次一密,保证身份信息的安全传输;

(3)信息完整性,监测设备和话机都能够接受到完整的信息,在出现错误时具备自我恢复功能;

(4)有效抵抗多种攻击手段,如暴力破解、重放攻击、假冒攻击等。

在实际应用中,该机制对用户完全透明,不影响用户使用体验。系统部署采用分布式结构,在身份认证过程中,信息交互次数和传递次数有限可控,带宽资源消耗少,能够保证实时通信。在认证话机数量增加时,能有效解决并发性的问题,对服务器的性能要求不高。

4 应用前景