随机排序的优化算法

第11A期电子学报Vol.28 No.11A2000年11月ACTA ELECTRONICA SINICANov.2000随机排序的优化算法.吴湛击吴伟陵(北京邮电大学信息工程系181 信箱北京100876 )摘要:随机排序经常出现在数字信号处理的分析和仿真中尤其用于交织器的比较分析和优化设计中,它的算法优劣直接影响到计算仿真的效率.针对原有算法本文提出了优化算法大大改善它的时间和空间复杂度.定量的理论分析和实际的仿真测试都表明优化算法能够有效提高计算效率和节省存储空间.关键词:随机排序;优化算法;时间复杂度;交织器中图分类号: 0224文献标识码: A文章编号: 0372-2112( 2000 ) 11A-0076-04Optimal Algorithm of Random SortWU Zhan-ji ,WU Wei-ling( P.0. Box 181 ,Department of Information Engineering ,BUPT ,Beijing 100876 ,China )Abstract : Random sort is often applied in analysis and simulation of digital signal processing ,and its algorithm afects the com-putation fficiency . In this paper optimal algorithms are put forward ,and can greatly reduce space and time complexity degree of previ-ous algorithms . Both theoretic analysis and experimental simulation prove that optimal algorithms can efficiently promote the computa-tion eficiency and save memory.Key words : randon-sort optimal-algorithm ,ime-complexity-degree Ainterleaver1引言引理1的说明这-引理是由欧拉首先发现的(证明从略),所谓随机排序是指取值范围在1和n之间的两两互不相它表明在n足够大的情况下用l( n)估计2T是精确的.同的随机整数序列.随机排序作为随机交织器的程序算法在交织器的设计中有着重要的作用.在作为IMT2000纠错编码2纯随机排序算法候选方案之-的Turbo码中交织器的设计--直是研究的重点.按照普遍的观点[13-6]随机交织是香农信道编码定理中首先假定仿真已经具备功能即能产生从1到任意指定随机编码的体现,因而被视为较好的一种大量的计算仿真都整数的均匀分布的随机整数.现在要在此基础上产生一个长基于固定交织和随机交织的对比测试,而且交织器的优化设度为n的纯随机排序序列{a;}i a,∈[1 n],v i≠j ,a;≠a;计也往往要在大量随机产生的交织器集合中选择误码率较.1 原有算法(文献2B4页)小的那种.同样随机交织对于. -般意义下的信道交织的对比stepl初始化数组 A ,i∈[1 n]A[ i]=0 ,m=1测试和优化设计也有很大价值.随机排序算法的优劣直接影step2产生随机数 p∈[1 n]响到计算仿真的效率尤其是对于数据量大、耗时长的工程仿step3如果A[p]=0则置A[p]=1并在数组B存储真更是如此.另外对于随机排序算法的时间复杂度的理论分p风m]=p ,且将m加1析也不够完善.本文着重于改进原有随机排序算法提高仿真step4如果 m1转step2;收稿日期209014修回日期200-07-11基金项目国家自然科学基金重大项目( No. 69896243资助课题2电子学报2000年否则停机打印A即纯随机排序序列.布可知{n;独立分布则π(η:)也独立分布,那么时间复杂说明:●优化算法的基本思想是:首先初始化-一个简单递增排度TCD= 2X K(η:))序的数组A={1 2.. ,几}然后产生一个[ 1 ,n 止均匀分布的由引理2,TCD=>;1-;=n;随机整数设为p1)将A[n]与A[p1交换然后,A[ n固定.不变再产生一个[1,n-1]上均匀分布的随机整数(设为由引理1 ,TCD= nlr( n)p2)并将A[ n-1]与A[ P2交换如此反复直到进行完n-1.:原算法时间复杂度是( nl( n))次交换得到一个纯随机排序数组A.2.5小结●从中可以看出纯随机的优化算法基于交换的实现机对于纯随机排序,优化算法比原算法节省50%存储空制休在step3)实现了动态排序.在每一次交换时,它将A数间且计算效率是原算法的lI( n )倍.组分为两部分:[ m+1侄A[ n是固定部分,已实现随机排.3符合特定条件的随机排序算法序不再变动;A[1]至A[m是可变部分需产生均匀分布的随机数p∈[1 m]并将A[ m]与A[p交换.之后,可认为A在研究中有时需要产生满足-定条件的随机排序例如[ m已实现随机排序置于固定部分故将m减一,如此重S随机序列其产生的基本步骤是:首先产生随机数j J≤j≤.复直到m为1.n并与前S个已产生的随机数比较如果与其距离都小于●所以,可得出结论:优化算法的实现基于数组不同位置s则丢弃j重新产生,否则记录j然后寻找下一个位置,直的随机交换这-点保证了它排序的随机性;同时每次产生到所有n个数都找完.我们把这种特定条件抽象成布尔代数的随机数其概率分布不同这一点保证 了它排序的动态性每Fj)∈{0 1}当然也可能不存在使F(j)= 1成立的j那么产生-个随机数就能决定一个排序位置这与原算法不同,从可强行插入一个数并进行后继搜索.而大大提高了运算效率.3.1原有算法( 文献2B5页)2.3 优化算法的成立性证明step1初始化数组A A[ i]=0，i∈[1 n]m=1我们知道每个长度为n的纯随机排序序列的发生概率step2初始化数组 C ,C[ i]=0ji∈[1 m],t=0为1/n!如果优化算法产生的每个数组都满足此条件则说step3产生随机数 p∈[ 1 ,mn]明该算法成立.由算法可知,step4如果A[p]=1转step3RA)= P{ξ1=an &2=an-1.. 5-1=a2}step5如果F[ p]=1转step8. {ξ;独立分布如果Cp]=0则1=1+1 ,C[p]= 1..R(A)=Rξ=an)R 52=an-)..P( ξ-1=a2)step7如果 l 1转step2对照原算法步骤假设m=i时产生随机数p;并令η随机数)否则打印数组A即满足F的随机序列(可能强行插入=A[ p;]则易知，n-i+1 i- 1因{p; }独立分智缝n.)=●符合特定条件的随机算法应用了交换机制(体现在第11A期吴湛击随机排序的优化算法3step6 ).每次交换时也是将随机数组分为两部分:4[ m+1至.由p独立可知n独立则T(ηi他独立分布那么时间复杂A[ n伪固定部分,可认为已经排序;A[ 1 ]至A[ m ]为可变部分动态产生均匀分布的随机数p∈[1,m]这样就能在未排度TCD= 22E 7( r))序部分进行选择而原算法需同时在已排序部分和未排序部.由引理2;rCD=之2;n之艺+分选择随机数所以优化算法提高了计算效率.二i=0台台h●同时优化算法也采用了自环机制(体现在step4 ).在由引理1 ,TCD≈n2l(n+1-i)=n2r(i)A[1至A[ m的可变部分产生的随机数p与固定部分比较,未必满足F(p)=1.如满足则将A[p]与A[m交换并令m由引理3 ,TCD≈n2lu( n)=m-1再重复以上过程.如不满足则令p=p mod m+ 1，.原算法的时间复杂度是0( n2lr( n))看是否满足F( p)=1如此反复.这样就构成了一个试探的自3.3.2平均情况所谓平均情况是指满足 F( j)= 1的随机环p-(p+1)~( p+2)-→..→m→1→2...→(p-1)算法将.数i在待寻数组中均匀分布.虽然要精确地估计两种算法的会寻找满足F的第一个数(设为x).由于自环的起点p是随.时间复杂度是相当困难的,但是可大致估计出两种算法的相机的则X是随机的.若自环均不满足F ,即不存在x则强对程度.行将A[p]与A[ m交换.以上所述的自环机制保证了排序的.假设满足F( j)= 1的相邻的两个随机数都相距d ,由引随机性,同时简单易行运算方便(仅做加一运算) ,而原算法理2易知对于原算法搜索出它的平均时间E( T)= d ,而对需按一定复杂度的计算规则寻找另外的随机数所以优化算于优化算法搜索出它的平均时间K r)=+ >i=d+1亦法在这一环节 也能提高计算效率.●可见这两种技巧尽管简单却能有效地节省内存并提即优化算法的效率约提高了-倍.此外还要考虑到优化算法高效率收到了简单有效的功效.能够直接在未选数组中搜索,由纯随机分析可知又可提高3.3 新旧算法的比较分析Ir( n)倍.综上在平均情况下优化算法的效率大约是原算法首先优化算法只需要-个数组而原算法需要三个所的21( n)倍.3.4小结以新算法节省了67%的存储空间.如果想对某个特定的F精确地估计时间复杂度是相当对于符合特定条件的随机序列,优化算法计算效率是原困难的除非F很简单.但是我们可对平均情况和最差情况算法的2ln( n倍并且节省67%的存储空间.作出大致比较.4仿真计算结果3.3.1最差情况所谓最差情况是指每次搜索都找不到满足F(j)=1的j只能被迫强行插入一个数.对于优化算法,我们用C语言编程实际测试了两种算法的执行时间,结果如图1所示.易知TCD= Zi= (n+1)所以其时间复杂度是Q( n2/2)新旧算法的效率比较图1++理论纯随机21( i).. 理论二随机引理3 limmhn)=1=实验纯随机证明:14**实验s随机:之(i=2[h(x)dx= ["l(x)ix! 12台=r(lr( n)- 1)+ 1糠1fn+1之(i)≤2「l(x)kx≤.I( x )dxi=(n+1XI( n+1)-1)+1.1 = limn(山( n)-1)+ 12n( i)500 1000 1500 2000 2500 3000 3500 4000nl(n)≤ linnl(n)≤lim( n+ XI( n+1)-1)+1. 1图1随机排序 算法效率比较图nlr( n)图中国煤化工2In(i)“limnlr( n)=1MHCNMH度纵坐标效率比表示相同条件卜你异么抗仃则问与几亿算法执行时间的比值.原算法的时间复杂度对照原算法步骤当m=i t=j时产生随机数p)令nηi●对于纯随机排序的S-随机排序在不同的帧长下分别按2.5和3.4所给结论计算了理论效率比并且在sUN工作=dp]+芳片数据易知()=| n+1-i-i iti-1|站_上以10万帧的数据量实际测试了新旧算法的执行时间再求其实验效率比，4电子学报2000年[ 5 ] S.A. Barbulescu and s. s. Pietrobon. Inteleaver design for turbo cod-5结论ing[ J ] Electronic Letters .1994 30( 11 ) 2107 - 2108.无论对于纯随机排序还是满足特定条件的随机排序本[ 6 ] J. Hokfelt ,T. Maseng and 0. Eford. Asessisg interleaver suitability of文提出的优化算法都大大改善了原有算法的时间和空间复Turbo codes. Nordie RadioSymposiun[ C] 1998 ,10 323 - 327.杂度.定量的理论分析和实际的仿真测试表明优化算法能够有效提高计算效率和节省存储空间.作者简介:参考文献:吴湛击1999 年毕业于南京邮电学院获学土学位现为北京邮电大学信息工程系硕士研究[ 1 ]吴伟陵.通向信道编码的Tubro码及其性能分析[J]电子学生研究范围包括宽带通信、编码理论、移动通信报1998 287)35- 40.等.[ 2 ]孙毅.Turbo Code在移动通信中的应用[ D]博士学位论文北京北京邮电大学,1999年.中国煤化工[ 3 ] C. Berrou A. Glavieux ,and P. Thitimajshima. Near Shamnon limit er-YHCNMHGror-orrecting coding and decoding :Tubo codes[ J].in Proe. ICC 93，Geneva Switzerland ,1993 5 :1064 - 1070.吴伟陵( 见本期第14页)[ 4 ] J. dAndersen and V. V. Zyablow . Interleaver design for turbo coding[J] in Proc. int. wymp. on Turbo Codes and Related Topics ( Brest ,Franc54 - 156.