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