英文文献

Design and Realization of an FPGA-Based Generator for Chaotic Frequency Hopping SequencesLing Cong,Associate Member,IEEE,and Wu XiaofuAbstract—Chaos-based pseudonoise(PN)sequences for spread spectrum(SS)communications ranks amongst the most promising applications of chaos to communications.This paper deals with the design and realization of a chaotic frequency hopping(FH) sequence generator that is compatible with current FH/SS tech-nologies.A simplistic generator architecture adopting nonlinear auto-regressive(AR)filter structures is proposed,which is based on the random sequence model and the metric entropy criterion for generation of random sequences.Conventional PN sequences are employed to perturb the generator such that the resulted se-quences fulfill the FH requirements on period and family size.In addition,a chaos-based FH sequence generator prototype is re-alized in field programmable gate arrays(FPGAs)and various tests are performed.The generator produces long period FH se-quences with uniform distribution over the available bandwidth, large linear complexity as well as suboptimal Hamming correla-tion properties.Bit error rate(BER)performance of the chaos-based asynchronous FH/CDMA system is evaluated by means of computer simulation.These results suggest that the cost-effective and well-performing generator has the potential to be incorporated into existing FH systems.Index Terms—Chaos,field programmable gate arrays,fre-quency hop communication,random number generation, sequences.I.I NTRODUCTIONT HE past decade of research on the applications of chaos theory to communications clearly outlines the trend of near-future development.The dominating schemes of chaos-based communications will be digital,because the inherent nonlinearity of chaos and unavoidable parameter deviation in electronic devices render exact regeneration of chaotic signals in analog systems difficult,and only digital schemes are compatible with modern communications systems. Amongst the various digital applications,at least two,i.e., chaotic encryption for security and chaos-based pseudonoise (PN)sequences for spread spectrum(SS)communications,are ready to be incorporated into existing systems,since they do not require change of other function blocks in popular sinu-soidal carrier communication systems1.The start of the new millennium should see realistic chaos-based communication systems in certain environments.Manuscript received June13,2000;revised November13,2000.This work was supported in part by the National Natural Science Foundation of China under Grant69931040,and in part by the National Key Laboratory of Commu-nication of China.This paper was recommended by Associate Editor T.Saito. The authors are with the Nanjing Institute of Communications Engineering, Nanjing210016,China(e-mail:cling@;lingc_iece@). Publisher Item Identifier S1057-7122(01)03851-X.1Obviously,the statements here do not preclude other applications including analog and chaotic carrier schemes in the far future.PN sequences are widely used as spreading codes for direct sequences(DS)SS systems and as hopping patterns in frequency hopping(FH)systems[1].Chaos-based design offers a new class of nonlinear PN sequences with approximate orthogonality that are especially valuable for asynchronous code-division multiple access(CDMA)systems.Chaotic PN sequences for either DS[2]–[4]or FH[5]systems have been actively explored,and research results are encouraging enough to integrate these sequences into current SS systems.The correlation properties of chaotic PN sequences are shown to be similar to,and in some cases even better than,their linear counterparts.Exact design and analysis of chaotic sequences as in conventional algebraic approach is generally impossible,and researchers depend more or less upon a statistical approach. Among many possible design approaches,the one based on the random sequence model has the advantage that it makes the design problem more tractable,albeit it is in general not the best.Furthermore,the validity of random sequence model has been established in many SS literatures for the performance analysis of asynchronous CDMA systems using long-period se-quences.In theory,the statistical design approach is capable of generating purely random sequences if the precision of chaotic systems is infinite.Kohda and Tsuneda[6]derived a sufficient condition for a class of maps to produce purely random binary sequences.Vizvari and Kolumban[7]presented two methods to improve the independence of consecutive numbers from one to another sampled from chaotic phase-locked loops(PLLs). The entropy criterion of[5]is a much more convenient way to judge whether a chaotic system is able to produce purely random sequences.Sequences obtained from the digital chaos generator,necessarily have a finite period and are,of course, not truly random,but the properties of well-designed chaotic PN sequences are very close to those of random sequences. In CDMA systems,these sequences have multiple access performance identical to that derived on the basis of random sequence model.Mazzini et al.’s idea[4]is different from [5]–[7]in that it tries to increase the capacity of chaos-based DS/CDMA systems.The resulted sequences perform slightly better than random sequences.However,the analysis of[8] revealed that the maximal gain of chaos-based spreading codes with respect to purely random sequences is about14% or just0.1dB in capacity.In addition,the rather small gain comes at the expense of degradation in the auto-correlation property,which will affect the spectral characteristics as well as initial acquisition of the sequences.For example,the maximal magnitude of side-lobe of the normalized auto-correlation would be as high as0.25in order to achieve the full0.1dB gain.Similar results were reported independently in[9],[10],1057–7122/01$10.00©2001IEEEFig.1.Block diagram of the chaotic FH sequence generator with a small perturbation.which showed that the gain is at most15%by more accurate analysis.This phenomenon conforms to the well-known Welch and Sidelnikov bounds[1]on spreading sequences that make a twin-win of autocorrelation and crosscorrelation impossible, as has been observed in a lot of constructions for conventional spreading sequences(see,e.g.,[11]).Due to the nonsignificant improvement in multiple access performance attained by chaotic sequences,and negative effects on auto-correlation, the pure random sequence model seems more appealing on the whole.DS and FH are the two principal types of CDMA technolo-gies.In comparison with DS,a major advantage of FH is that it can be implemented over a much wider frequency bandwidth, and the bandwidth can be noncontiguous.Another advantage is that the requirement for power control is much less stringent in a multiuser system.In DS systems,accurate power control is crucial to resist the near-far effect.These two advantages of FH will be decisive in many applications.In FH communica-tion systems,a PN generator is employed by each user to pro-duce a“random”sequence of frequencies.Such systems require sets of FH sequences that,in addition to having good Ham-ming correlation properties,also have long period and large linear complexity[12],[13].The first requirement reduces in-terference due to presence of other users and helps the sys-tems to have self-synchronizing capability,whereas the second and third requirements prevent an intelligent jammer from jam-ming the communication by duplicating the sequence gener-ation mechanism.Most of the FH sequences are constructed through algebraic approaches[1],[12]–[14].This paper is de-voted to chaos-based FH sequences meeting the above demands. The design methodology is based on the above-justified random sequence model.Preliminary results reported in[5]showed that such sequences are asymptotically suboptimal with respect to the lower bound on Hamming correlation.The design and analysis of chaos-based spread spectrum systems have laid the foundation for chaotic PN sequences toward practical application.Nevertheless,as far as the authors are aware of,no hardware realization of chaotic PN sequences generators completely compatible with current SS technologies has appeared in open literature yet.The major impediment of the practical application of chaos is the finite-wordlength implementation of chaotic systems.Most classical chaotic systems involve complicated nonlinearity,e.g.,multiplication or cosine,that is not suited for digital realization,because only adders and low-precision multipliers are available in typical digital hardware,while high-precision is usually required to achieve fully developed chaos.Moreover,the periods of digital chaotic orbits2are dispersed in a wide range and can not be known a priori.The unpredictable occurrence of short-period orbits has prevented chaos from practical FH/SS systems. This paper deals with the design and realization of a field programmable gate array(FPGA)-based generator for chaotic FH sequences.FPGAs offer great flexibility to design high-speed high-density digital hardware.The hardware is easy to be programmed and reconfigured.This paper is organized as follows.The statistical design of a simplistic chaotic FH se-quence generator suited for FPGA realization is proposed in Section II.Section III provides a perturbation-based architec-ture for the chaos generator as well as the periodicity consid-erations.In Section IV,the FPGA realization of the generator using Xilinx XC4028XLA is described.Section V addresses the performance tests of the chaos-based generator.Finally,conclu-sions are drawn and remaining problems are discussed.II.S TATISTICAL D ESIGNThe symbolic dynamics-based design of chaotic FH se-quences[5]is theoretically strict but does not lend itself to simplistic hardware implementation.A systematic design of discrete-time chaotic systemswithCONG AND XIAOFU:DESIGN AND REALIZATION OF AN FPGA-BASED GENERATOR FOR CHAOTIC FREQUENCY HOPPING SEQUENCES 523structures with two’s complement overflow nonlinearity are of particular interest for FPGA realizations owing to their simple structure.We are thus motivated to study the sequence generator based on nonlinear AR filters.The block diagram of the chaos generator is illustrated in Fig.1.The[15].is the chaotic signaland are the statevariables.for are map-pingsonis a small perturba-tion signal to be discussed in the next section,but is not con-sidered in this section,i.e.,zero input is assumed for the time being.Continuous-valued variables are assumed in the analysis process.However,all variables and coefficients are treated as nonnegative integers without loss of generality when hardware implementation is concerned,since FPGAs are more suitable for fixed-point realization.Throughout this paper,the continuouschaotic signal is denotedby,whereas isdefined asmodis represented in the binary formatof is the wordlength of the filter.Forfixed-point realization,all multiplications and additions are per-formed under the condition of overflowing normally.Finally,the-ary FHcode bitsof.The time evolution of thesystem is governedbydistincteigenvalues.:-dimensional uniform distribution provided that the system is not decomposable and thecoefficient.This goalcan be surprisingly attained,although chaotic systems are deter-ministic.The theory of symbolic dynamics proved that discrete-valued sequences obtained through partition of the phase space of certain chaotic systems are indistinguishable from Markov chains in a probabilistic sense.From the viewpoint of information theory,weobtainbits of information per iteration.Theconnection between chaotic dynamics and information theory has been established [17].It is proven that the metricentropy-dimensionaluniform distribution,the Lyapunov exponents are given by the logarithm of module of the eigenvaluesof .Thus the metric entropy is givenbyalso characterizes the entropy of the discrete informationsource is avail-able to an outside observer,from which the phase space recon-struction is possible;b}The transform to the discrete-valuedsetimplicitly introducesa (see [6]for an example of theso-called chaotic bit sequences);andc)is uniformly dis-tributed.On the basis of this simplification,the metric entropy of the nonlinear filter should satisfy thecondition.In this case,the metric entropy of the systemis(5)which can be derived by writing (3)into theform.Then,the nonlinear filter will produce purelyrandomlie outside the unit circle.In Appendix I,we describe a procedure where the Schur-Cohn test [18],which is originally used to test if a linear system is524IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I:FUNDAMENTAL THEORY AND APPLICATIONS,VOL.48,NO.5,MAY 2001TABLE IO RBIT P ERIOD OF THE A UTONONOUS SYSTEMstable,is performed on the reciprocal polynomialofFurther simplification appears when all the coefficients are neg-ative numbers.In this case,since wehavethe condition simplyisanddistinct roots a priori such that themetric entropy given by (4)is,in addition to satisfying Kelber’s criteria.Thecoefficients can be determined in terms of rootsby(6)where the summation is over all the possible combinationofunless otherwise stated.The perturbationsignalin Fig.1is extracted from a con-ventional PN sequence and then is added into the nonlinearfilter.The perturbation signal is very small compared to the chaoticsignal,wherePN generator with period2in (1)is replaced here bymodcan be derived for the nonlinear filter-basedgenerator with a perturbation.Property 1:Theperiodfalls eventually into aperiod-greater than a certain value,then from (7)wehave must be a multiple of25and.InTable I,the period of zero-input orbits obtained by numerical ex-periments is shown against the wordlength.Though the average period increases exponentiallywithCONG AND XIAOFU:DESIGN AND REALIZATION OF AN FPGA-BASED GENERATOR FOR CHAOTIC FREQUENCY HOPPING SEQUENCES 525TABLE IIO RBIT P ERIOD OF THE P ERTURBED S YSTEM (w =8)evident from Table II.For instance,the average period is length-ened to 3456if aperiod-31ifis a one-to-one mappingon the integerset.Proof:Since,wehavem o di s a p e r i o d o f a s w e l l ,w e h a vem odi s a o n e -t o -o n e m a p p i n g f r om to .T h e r e f o r e ,w e h a v e p r o v e n t h at.R e p e a t i n g t h e b a c k w a r d r e c u r s i o n ,w er e a c h t h e c o n c l u s i o n t h ats e c o n d f i l t e r w i t h 3-b i tp e r t u r b a t i o n .T h e g e n e r a t o r p o l y n o m i a l o f t h em s e q u e n c e is .T he(C ,9)(5,C )(9,5)is changed into an odd number 3,it willproduceis that of the perturbation sequence.Proof:Supposethat.Wehavein particular if the m sequence is employedas the perturbation.Previous works (e.g.,[3])stated that chaos generators support an infinite number of users by changing the initial conditions.This statement is intuitively based on the sensitive dependence of chaotic systems on initial conditions.However,this is not true for digital generators.It was observed that the orbits of au-tonomous 1-D systems with different seeds eventually coincide with very high probability.Grebogi et al.[25]even showed that if one puts down randomly l seeds,one expects,on average,to findonlyand lead to the sameorbitmodand are lessthan .But it contradicts with the assumption.Property 5:The orbits are cyclically distinct if the corre-sponding perturbation sequences are cyclically distinct for fixed initial conditions.Proof:Assume that two cyclically distinct perturbationsequencesand lead to two cyclicallyidenticaland ,i.e.,for someintegermod526IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I:FUNDAMENTAL THEORY AND APPLICATIONS,VOL.48,NO.5,MAY2001Fig.2.Two nonlinear filter structures using left rotation:(a)The multiplication by coefficient c is replaced by ROL is inserted after thesummation and overflow.“modand are cycli-cally identical,which is again contradictory with the assump-tion.Care should be taken when we try to generalize the above properties to chaotic FH sequences,because it is possible that the period of the binary sequence extracted from a particular bitofbitsofmodis the integer represented by thelowest ,because thelowestbits ofoperands.The periodoffor the same reasonas,which is defined as left rotation of the contentsof a registerbyis a one-to-one mapping that not only works like acoefficientis available in the standard very-high-speedintegrated circuits hardware description language (VHDL)for FPGA development.In our design,two possible solutions are considered,as shown in Fig.2.In one method,thecoefficient will be replaced byROLinto the filter after thesummation and overflow [see Fig.2(b)],and the constant coef-ficients are kept.This additional rotation preserves the uniform distribution and maintains the above-mentioned five properties,because it is one-to-one.Also,the metric entropy criterion is satisfied.It can be seen from (2)that the metric entropy is in-creasedbyis inserted.Due to the rotation,the period of FH sequences is unknown.To ensure that the period is no less than2such that2,the admissible value of FHsequence period is either oneorin Fig.1is one-to-one and the initialconditionsare not all identical at the bit positionswhere the FH code is extracted,as Property 2also holds for3Thisis the reason why the left circulation performs much better than a con-stant coefficient.In fact,Frey already recognized this reason in [24].But Frey’s filter,when viewed as one with c =2plus a perturbation,has eigenvalues =01.It is decomposable according to Kelber’s analysis,sinceCONG AND XIAOFU:DESIGN AND REALIZATION OF AN FPGA-BASED GENERATOR FOR CHAOTIC FREQUENCY HOPPING SEQUENCES527Fig.3.Block diagram of the chaotic FH sequence generator for 64frequencies using a third-order filter.(1)c is the two’s complement conversion.FH sequences.Thus the perturbed filter is able to generate FH sequences with period ofprimeare 2,3,5,7,13,17,19,31,61,89,107,127,we can ensure the period no less than the specified value.When the initial conditions are fixed and the FH code is ex-tracted from thelowest,the FH codesat of FH sequences be no less than2,and the family size be 64for potential CDMA applications.The design procedure mainly consists of two steps.First,an appropriate nonlinear filter should be chosen such that themetricentropysequence is used to perturb this nonlinear filter tomakein Fig.2(a)and (b),respectively.Thewordlength of both the filtersis=ROL4,444a nd 16u s i n g (6).R O Lf o l l o w e d b y t a k i ng t w o ’s c o m p l e m e n t r e p l a c e11a nd65h a s t h eb i n a r y f o r m “1000001”c a n s i m p l y b e r e a l i z ed b y a s i x -b s h i f t a n d s u b se q u e n t a d d i t i o n.To m i x t h e p h a s e s p a c e ,t h e t i o n R O L=6.An m sequence with generatorpolynomialthatis added modulo twotoofthesequencegenerator is initialized to be all ones.The nonlinear filter will be reinitialized when all ones are detected once again inthe.The chaos-based generator prototype was realized in the Xilinx FPGA chip of XC4028XLA.The software was devel-oped by the VHDL and was then downloaded from the PC to configure the chip.Fig.4shows the printed circuit board of the generator prototype.The generator has a friendly I/O interface.The FH code data were read into a PC through an ISA bus card that is connected to the I/O interface.The generator was ex-tensively tested.Under various conditions,it produced exactly the same data as those obtained by computer simulation.The realization costs approximately 4000equivalent gates including528IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I:FUNDAMENTAL THEORY AND APPLICATIONS,VOL.48,NO.5,MAY2001Fig. 4.Printed circuit board of the generator prototype realized in XC4028XLA.the I/O interface.The generator supports work frequency up to 30MHz.This indicates that the generator is cost-effective and allows to be integrated into an FH transceiver.The generator costs much less resources than the logistic map generator of [20]that was realized in programmable combina-tional circuit.It utilized a 32Kb16bits.When very high-speed operation and small die area is critical,the ASIC is a better choice.The major advantage of the FPGA is its programmability and easiness of reconfiguration.For example,many sequence sets can be produced using the same hardware,as shown by the above realization example.Moreover,upgrading is easy to do.In the future,the module of FH code synchronization may be included in the FPGA.V .P ERFORMANCE T ESTSIn this section,we present the performance test results of the generator described in Section IV.Fig. parison of the chi-squared values for test of 1-D uniform distribution for chaotic FH sequences and the Lempel-Greenberger sequences averaged over 64sequences.A.Chi-Squared TestsThe chi-squared test compares the FH code generator’s output to the desired uniform distribution.Letth frequency within alength-fromthe generator.Fig.5shows the chi-squared values averaged over all the 64chaotic FH sequences indexedby-introduced shift in frequency from a basic m sequence.By observing (9)we find that the chi-squared value of this se-quence is identical to that ofthesequence averaged on dif-ferent segments.Similar trend was also observedforCONG AND XIAOFU:DESIGN AND REALIZATION OF AN FPGA-BASED GENERATOR FOR CHAOTIC FREQUENCY HOPPING SEQUENCES529Fig. parison of chi-squared values for the test of4-D uniformdistribution for the three bits obtained from the generator in Fig.3and onewith cccco c coc c ccB.Hamming Correlation PropertiesThe periodic Hamming cross-correlation betweentwo sequences is defined by[14]as.The Hammingauto-correlation is defined as.When,theHamming correlation of chaotic FH sequences is asymptoticallyGaussian with mean and variancewhere.With respect to the Lempel-Greenberger lower bound on Ham-ming correlation[14],chaotic frequency hopping sequences areasymptotically suboptimal,since is negli-gible compared to when530IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I:FUNDAMENTAL THEORY AND APPLICATIONS,VOL.48,NO.5,MAY2001Fig.9.Relationship between the linear complexity and sequence length for the sequence indexed by v ={000001}(the sequence is viewed as binary).satisfied by a sequence having linear complexityofconsecutive bits of the sequence.With the knowledge of code sequences the jammer can defeat the processing gain of FH systems by his replica transmission.Linear code sequences are therefore unacceptable for anti-jamming FH systems.On the other hand,chaotic code sequences are inherently nonlinear.Since the code sequences are random,the linear complexity is roughly half of the sequence length [29].The jammer then has an nearly impossible task because he has to store almost the entire sequence in order to regenerate the sequence linearly.The near optimum linear complexity is the major advantage of the chaos-based approach in comparison with conventional approaches.As an example,Fig.9shows the relationship between the linear complexity and sequence length for thesequence indexedby{000001}in Fig.3.The sixbitsactive users employs nonco-herent binary frequency shift keying (BFSK)signaling.It is assumed that one datum bit is transmitted during a hop interval.Whenever two or more signals from different transmitters are transmitted simultaneously in the same frequency slot,we say a “hit”occurs.The probability of a particular bit being hitis,where(12)Fig.10.BER of the chaos-based asynchronous FH/CDMA system over AWGN channels (q =64;K =3).Fig.11.BER of the chaos-based asynchronous FH/CDMA system over Rayleigh fading channels (q =64,K =3).whereover memorylessRayleigh fadingchannels.is not large enough.For moreaccurate analysis see [31].The simulated BERs of chaos-based asynchronous FH/CDMA systems are plotted in Figs.10and 11,respectively,for AWGN channels and Rayleigh fading channels.The single user curve is also included in each figure for compar-ison.Insimulations,CONG AND XIAOFU:DESIGN AND REALIZATION OF AN FPGA-BASED GENERATOR FOR CHAOTIC FREQUENCY HOPPING SEQUENCES531VI.C ONCLUSIONSWe have presented an architecture of chaotic FH sequence generator based on nonlinear AR filter structures.The design re-lies on an entropy criterion for the purely random FH sequence model.Some principles for the choice of coefficients are given.A simplistic structure is proposed in which left rotation plays an important role.To circumvent the finite-wordlength effect that has been the major impediment of practical application of dig-ital chaotic systems,we use the perturbation method to ensure that the period of chaotic FH sequences is lower-bounded by the prescribed value.The periodicity aspects are analyzed.The generator prototype was realized in FPGAs and various tests were performed.In summary,chaotic FH sequences are useful for asynchronous CDMA systems under the threat of intelligent jamming,because they possess uniform distribution,suboptimal Hamming correlation and near optimum linear complexity. Typically,code acquisition of long-period sequences does not depend on the sequences themselves.Instead it is often achieved by other means such as a short-period auxiliary sequence or syn-chronization preamble.The generator proposed in this paper is ready to be incorporated into the FH transceiver when this ac-quisition scheme is adopted.However,the code acquisition of chaos-based approach needs further research when the system is required to have self-synchronization capability.Specifically, new rapid acquisition technique is of paramount importance for chaotic code sequences since some conventional techniques based on the LFSR property are not applicable any longer.A disadvantage of the chaos-based approach is that the performance of sequences is evaluated only in a statistical sense.Consequently,exact formula of the Hamming correlation function is not available.For short-period sequences,this is unlikely to affect the system performance since computer search for low Hamming correlation sequences is feasible. However,further optimization is still needed for long-period sequences to avoid relatively high Hamming correlation.For-tunately,if the sequence period is very long,chaotic,frequency hopping sequences are near optimal.To prevent sequence duplication in typical anti-jamming applications,the sequence period is extremely long,usually measured many years when the hopping rate is about100hops/s.What is employed in a communication process of say,10min,is a very small portion of the whole sequence.An FH sequence is no longer optimal over this partial period even though it is optimal with respect to the Lempel-Greenburger bound over the full period.Various tests show that chaotic sequences and optimal sequences have similar Hamming correlation values,over a small portion of the period.In other words,both of them behave like random sequences.Therefore,we conclude that chaotic frequency hop-ping sequences perform as well as optimal sequences in terms of multiple access interference in anti-jamming applications. We regard this as a strong support to the usefulness of the chaos-based approach.Other remaining problems include a thorough investiga-tion of the periodicity aspects of such sequences in digital generators,bit error rate(BER)performance test in a re-alistic FH/CDMA system using the optimized chaos-based generator and so on.Once these problems have been solved,the chaos-based generator will hopefully find its application in tomorrow’s FH/CDMA communication systems.The anti-jamming capability of such systems would be significantly enhanced while the multiple access interference performance is still preserved.A PPENDIX IS CHUR–C OHN T EST[18]The Schur–Cohn test can determine if thepolynomial Then,for,computeandwhereThe Schur-Cohn test statesthat.Our problem is to determineifasWesetand perform the Schur-Cohntest..A PPENDIX IIP ROOF FOR O DD C OEFFICIENTSSupposethat without loss of generality,thenis oddand,i.e.,is one-to-one.A CKNOWLEDGMENTThe authors wish to thank C.Yong for the discussion of Prop-erty2in Section III and his help in the design of the print circuit。