隨機排序的優(yōu)化算法

第11A期電子學(xué)報Vol.28 No.11A2000年11月ACTA ELECTRONICA SINICANov.2000隨機排序的優(yōu)化算法.吳湛擊吳偉陵(北京郵電大學(xué)信息工程系181 信箱北京100876 )摘要:隨機排序經(jīng)常出現在數字信號處理的分析和仿真中尤其用于交織器的比較分析和優(yōu)化設計中,它的算法優(yōu)劣直接影響到計算仿真的效率.針對原有算法本文提出了優(yōu)化算法大大改善它的時(shí)間和空間復雜度.定量的理論分析和實(shí)際的仿真測試都表明優(yōu)化算法能夠有效提高計算效率和節省存儲空間.關(guān)鍵詞:隨機排序;優(yōu)化算法;時(shí)間復雜度;交織器中圖分類(lèi)號: 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的說(shuō)明這-引理是由歐拉首先發(fā)現的(證明從略),所謂隨機排序是指取值范圍在1和n之間的兩兩互不相它表明在n足夠大的情況下用l( n)估計2T是精確的.同的隨機整數序列.隨機排序作為隨機交織器的程序算法在交織器的設計中有著(zhù)重要的作用.在作為IMT2000糾錯編碼2純隨機排序算法候選方案之-的Turbo碼中交織器的設計--直是研究的重點(diǎn).按照普遍的觀(guān)點(diǎn)[13-6]隨機交織是香農信道編碼定理中首先假定仿真已經(jīng)具備功能即能產(chǎn)生從1到任意指定隨機編碼的體現,因而被視為較好的一種大量的計算仿真都整數的均勻分布的隨機整數.現在要在此基礎上產(chǎn)生一個(gè)長(cháng)基于固定交織和隨機交織的對比測試,而且交織器的優(yōu)化設度為n的純隨機排序序列{a;}i a,∈[1 n],v i≠j ,a;≠a;計也往往要在大量隨機產(chǎn)生的交織器集合中選擇誤碼率較.1 原有算法(文獻2B4頁(yè))小的那種.同樣隨機交織對于. -般意義下的信道交織的對比stepl初始化數組 A ,i∈[1 n]A[ i]=0 ,m=1測試和優(yōu)化設計也有很大價(jià)值.隨機排序算法的優(yōu)劣直接影step2產(chǎn)生隨機數 p∈[1 n]響到計算仿真的效率尤其是對于數據量大、耗時(shí)長(cháng)的工程仿step3如果A[p]=0則置A[p]=1并在數組B存儲真更是如此.另外對于隨機排序算法的時(shí)間復雜度的理論分p風(fēng)m]=p ,且將m加1析也不夠完善.本文著(zhù)重于改進(jìn)原有隨機排序算法提高仿真step4如果 m1轉step2;收稿日期209014修回日期200-07-11基金項目國家自然科學(xué)基金重大項目( No. 69896243資助課題2電子學(xué)報2000年否則停機打印A即純隨機排序序列.布可知{n;獨立分布則π(η:)也獨立分布,那么時(shí)間復雜說(shuō)明:●優(yōu)化算法的基本思想是:首先初始化-一個(gè)簡(jiǎn)單遞增排度TCD= 2X K(η:))序的數組A={1 2.. ,幾}然后產(chǎn)生一個(gè)[ 1 ,n 止均勻分布的由引理2,TCD=>;1-;=n;隨機整數設為p1)將A[n]與A[p1交換然后,A[ n固定.不變再產(chǎn)生一個(gè)[1,n-1]上均勻分布的隨機整數(設為由引理1 ,TCD= nlr( n)p2)并將A[ n-1]與A[ P2交換如此反復直到進(jìn)行完n-1.:原算法時(shí)間復雜度是( nl( n))次交換得到一個(gè)純隨機排序數組A.2.5小結●從中可以看出純隨機的優(yōu)化算法基于交換的實(shí)現機對于純隨機排序,優(yōu)化算法比原算法節省50%存儲空制休在step3)實(shí)現了動(dòng)態(tài)排序.在每一次交換時(shí),它將A數間且計算效率是原算法的lI( n )倍.組分為兩部分:[ m+1侄A[ n是固定部分,已實(shí)現隨機排.3符合特定條件的隨機排序算法序不再變動(dòng);A[1]至A[m是可變部分需產(chǎn)生均勻分布的隨機數p∈[1 m]并將A[ m]與A[p交換.之后,可認為A在研究中有時(shí)需要產(chǎn)生滿(mǎn)足-定條件的隨機排序例如[ m已實(shí)現隨機排序置于固定部分故將m減一,如此重S隨機序列其產(chǎn)生的基本步驟是:首先產(chǎn)生隨機數j J≤j≤.復直到m為1.n并與前S個(gè)已產(chǎn)生的隨機數比較如果與其距離都小于●所以,可得出結論:優(yōu)化算法的實(shí)現基于數組不同位置s則丟棄j重新產(chǎn)生,否則記錄j然后尋找下一個(gè)位置,直的隨機交換這-點(diǎn)保證了它排序的隨機性;同時(shí)每次產(chǎn)生到所有n個(gè)數都找完.我們把這種特定條件抽象成布爾代數的隨機數其概率分布不同這一點(diǎn)保證 了它排序的動(dòng)態(tài)性每Fj)∈{0 1}當然也可能不存在使F(j)= 1成立的j那么產(chǎn)生-個(gè)隨機數就能決定一個(gè)排序位置這與原算法不同,從可強行插入一個(gè)數并進(jìn)行后繼搜索.而大大提高了運算效率.3.1原有算法( 文獻2B5頁(yè))2.3 優(yōu)化算法的成立性證明step1初始化數組A A[ i]=0，i∈[1 n]m=1我們知道每個(gè)長(cháng)度為n的純隨機排序序列的發(fā)生概率step2初始化數組 C ,C[ i]=0ji∈[1 m],t=0為1/n!如果優(yōu)化算法產(chǎn)生的每個(gè)數組都滿(mǎn)足此條件則說(shuō)step3產(chǎn)生隨機數 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時(shí)產(chǎn)生隨機數p;并令η隨機數)否則打印數組A即滿(mǎn)足F的隨機序列(可能強行插入=A[ p;]則易知，n-i+1 i- 1因{p; }獨立分智縫n.)=●符合特定條件的隨機算法應用了交換機制(體現在第11A期吳湛擊隨機排序的優(yōu)化算法3step6 ).每次交換時(shí)也是將隨機數組分為兩部分:4[ m+1至.由p獨立可知n獨立則T(ηi他獨立分布那么時(shí)間復雜A[ n偽固定部分,可認為已經(jīng)排序;A[ 1 ]至A[ m ]為可變部分動(dòng)態(tài)產(chǎn)生均勻分布的隨機數p∈[1,m]這樣就能在未排度TCD= 22E 7( r))序部分進(jìn)行選擇而原算法需同時(shí)在已排序部分和未排序部.由引理2;rCD=之2;n之藝+分選擇隨機數所以?xún)?yōu)化算法提高了計算效率.二i=0臺臺h●同時(shí)優(yōu)化算法也采用了自環(huán)機制(體現在step4 ).在由引理1 ,TCD≈n2l(n+1-i)=n2r(i)A[1至A[ m的可變部分產(chǎn)生的隨機數p與固定部分比較,未必滿(mǎn)足F(p)=1.如滿(mǎn)足則將A[p]與A[m交換并令m由引理3 ,TCD≈n2lu( n)=m-1再重復以上過(guò)程.如不滿(mǎn)足則令p=p mod m+ 1，.原算法的時(shí)間復雜度是0( n2lr( n))看是否滿(mǎn)足F( p)=1如此反復.這樣就構成了一個(gè)試探的自3.3.2平均情況所謂平均情況是指滿(mǎn)足 F( j)= 1的隨機環(huán)p-(p+1)~( p+2)-→..→m→1→2...→(p-1)算法將.數i在待尋數組中均勻分布.雖然要精確地估計兩種算法的會(huì )尋找滿(mǎn)足F的第一個(gè)數(設為x).由于自環(huán)的起點(diǎn)p是隨.時(shí)間復雜度是相當困難的,但是可大致估計出兩種算法的相機的則X是隨機的.若自環(huán)均不滿(mǎn)足F ,即不存在x則強對程度.行將A[p]與A[ m交換.以上所述的自環(huán)機制保證了排序的.假設滿(mǎn)足F( j)= 1的相鄰的兩個(gè)隨機數都相距d ,由引隨機性,同時(shí)簡(jiǎn)單易行運算方便(僅做加一運算) ,而原算法理2易知對于原算法搜索出它的平均時(shí)間E( T)= d ,而對需按一定復雜度的計算規則尋找另外的隨機數所以?xún)?yōu)化算于優(yōu)化算法搜索出它的平均時(shí)間K r)=+ >i=d+1亦法在這一環(huán)節 也能提高計算效率.●可見(jiàn)這兩種技巧盡管簡(jiǎn)單卻能有效地節省內存并提即優(yōu)化算法的效率約提高了-倍.此外還要考慮到優(yōu)化算法高效率收到了簡(jiǎn)單有效的功效.能夠直接在未選數組中搜索,由純隨機分析可知又可提高3.3 新舊算法的比較分析Ir( n)倍.綜上在平均情況下優(yōu)化算法的效率大約是原算法首先優(yōu)化算法只需要-個(gè)數組而原算法需要三個(gè)所的21( n)倍.3.4小結以新算法節省了67%的存儲空間.如果想對某個(gè)特定的F精確地估計時(shí)間復雜度是相當對于符合特定條件的隨機序列,優(yōu)化算法計算效率是原困難的除非F很簡(jiǎn)單.但是我們可對平均情況和最差情況算法的2ln( n倍并且節省67%的存儲空間.作出大致比較.4仿真計算結果3.3.1最差情況所謂最差情況是指每次搜索都找不到滿(mǎn)足F(j)=1的j只能被迫強行插入一個(gè)數.對于優(yōu)化算法,我們用C語(yǔ)言編程實(shí)際測試了兩種算法的執行時(shí)間,結果如圖1所示.易知TCD= Zi= (n+1)所以其時(shí)間復雜度是Q( n2/2)新舊算法的效率比較圖1++理論純隨機21( i).. 理論二隨機引理3 limmhn)=1=實(shí)驗純隨機證明:14**實(shí)驗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)“l(fā)imnlr( n)=1MHCNMH度縱坐標效率比表示相同條件卜你異么抗仃則問(wèn)與幾億算法執行時(shí)間的比值.原算法的時(shí)間復雜度對照原算法步驟當m=i t=j時(shí)產(chǎn)生隨機數p)令nηi●對于純隨機排序的S-隨機排序在不同的幀長(cháng)下分別按2.5和3.4所給結論計算了理論效率比并且在sUN工作=dp]+芳片數據易知()=| n+1-i-i iti-1|站_上以10萬(wàn)幀的數據量實(shí)際測試了新舊算法的執行時(shí)間再求其實(shí)驗效率比，4電子學(xué)報2000年[ 5 ] S.A. Barbulescu and s. s. Pietrobon. Inteleaver design for turbo cod-5結論ing[ J ] Electronic Letters .1994 30( 11 ) 2107 - 2108.無(wú)論對于純隨機排序還是滿(mǎn)足特定條件的隨機排序本[ 6 ] J. Hokfelt ,T. Maseng and 0. Eford. Asessisg interleaver suitability of文提出的優(yōu)化算法都大大改善了原有算法的時(shí)間和空間復Turbo codes. Nordie RadioSymposiun[ C] 1998 ,10 323 - 327.雜度.定量的理論分析和實(shí)際的仿真測試表明優(yōu)化算法能夠有效提高計算效率和節省存儲空間.作者簡(jiǎn)介:參考文獻:吳湛擊1999 年畢業(yè)于南京郵電學(xué)院獲學(xué)土學(xué)位現為北京郵電大學(xué)信息工程系碩士研究[ 1 ]吳偉陵.通向信道編碼的Tubro碼及其性能分析[J]電子學(xué)生研究范圍包括寬帶通信、編碼理論、移動(dòng)通信報1998 287)35- 40.等.[ 2 ]孫毅.Turbo Code在移動(dòng)通信中的應用[ D]博士學(xué)位論文北京北京郵電大學(xué),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.吳偉陵( 見(jiàn)本期第14頁(yè))[ 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.