Design of an analog/digital truly random number generator

Design o an Analog/Digi al T uly Random Numbe Gene a o S. Espejo , J. D. Ma in , A. Rod iguez-Vazquez and J. L. Hue as A’IT Bell Labs, 600 Moun ain AV., Mu ay Hill, USA D o. de Diseno Anal6gico-CNM, Edi icio CICA, C/ Ta ia s/n, 41012-Se illa, SPAIN Abs ac An analog digi al sys em is p esen ed o he gene a ion o uly andom (ape iodic) digi al sequences. This model is based on a e y simple piecewise-linea disc e e map which is sui able o implemen a ion using monoli hic analog sampleada a echniques. Simula ion esul s a e gi en illus a ing he op imum choice o he model pa ame e s. Ci cui implemen a ions a e epo ed o he disc e e map using bo h swi ched-capaci o (SC) and swi ched-cu en (SI) echniques. The layou o a (SI) p o o ype in a 3pm n-well double poly double me al echnology is included. In oduc ion A andom numbe gene a o is a basic building block in communica ion and ins umen a ion applica ion[l]. Also, he e a e many simula ion p oblems a ising bo h in science and enginee ing whe e andom numbe s a e equi ed [2]. These po en ial applica ions a e wide and in e es ing enough as o challenge design enginee s o conduc esea ch owa ds he elec onic implemen a ion o his kind o signal gene a o s. The use o maximum cycle eedback-shi - egis e s (FSR) p o ided a way o he elec onic gene a ion o a signal exhibi ing ce ain pseudo andom p ope ies. This kind o ha dwa e implemen a ion is commonly used o he pu pose o es ing VLSI ci cui s, whe e he una oidable pe iodici y o he sequence may no be an impo an d awback. Typical ope a ing sys ems o main ame compu e s include, on he o he hand, so wa e o he gene a ion o andom sequences exhibi ing ”be e ” cha ac e is ics han he ones p o ided by FSR. Howe e pe iodici y can be always de ec ed o e a mo e o less long ime. Besides, inc easing he quali y o he sequence equi es a adeo wi h he inc ease o CPU ime. All hese d awbacks esul as a consequence o he use o pu ely digi al echniques. Pe iodici y can be a oided by eso ing o he use o analog echniques. In pa icula a e y simple andom numbe gene a o model is p oposed in his pape which exploi s he chao ic beha io o nonlinea disc e e- ime sys ems. This model can be implemen ed in monoli hic o m using s a e o he a sampled-da a analogue ci cui echniques oge he wi h digi al ci cui y, hus making possible on-chip gene a ion o uly- andom signals in combined analog/digi al chips. An a chi ec u e o andom numbe gene a o Fig.1 shows he concep ual block diag am o a monoli hic A/D andom numbe gene a o . Th ee di e en blocks can be obse ed: 1) The disc e e map. 2) The compa a o . 3) The digi al p ocesso delay Re p ocesso Figu e 1:Concep ual block diag am o a andom numbe gene a o based on a disc e e map. The disc e e map is he c ucial building block o a monoli hic andom numbe gene a o . I has o be designed o p o ide a chao ic (ape iodic) analog signal dn). S a ing om his analog signal, a one-bi digi al sequence d(n) can be ob ained by compa ison wi h a e e ence le el. Al hough o (n) being chao ic he esul ing digi al sequence is ully ape iodic, some co ela ion can be usually obse ed among successi e samples o d(n). Besides, di e en p obabili ies measu es a e ypically ob ained o one and ze o e en s o d(n). The digi al p ocesso in Fig. 1 is in ended o equalize hose p obabili ies and o elimina e co ela ions among successi e samples. The disc e e map S a ing om an a bi a y ini ial poin x(0) in I, a disc e e- ime chao ic signal x(n) can be gene a ed by applying he ollowing i e a i e o mula: x(n)= ix(n-l)] n=1,2,3 ... (1) which is called a disc e e map o he in e al I. The implemen a ion o a disc e e map is concep ualized in Fig.1. A delay block and a non-linea ope a o a e equi ed. Many non-linea ope a o s a e quali ied o p oduce chaos [3,4]. Only some o hem a e howe e sui able o monoli hic implemen a ion. In pa icula we will ocus he e on piecewise-linea (PL) unc ions because hey can be e y easily and accu a ely implemen ed in MOS VLSI [5,6]. Le us s a by conside ing he ollowing discon inuous PL map: whe e sgn(n) holds o he s gn unc ion: x20 -1 XLO Pa ame e s A and B de e mine he p ope ies o he signal gene a ed by a disc e e map based in (2a). Fig.2 illus a es he pa ame e dependence o his unc ion. Analysis shows ha a ame e A is only a scale ac o . On he o he hand, di g en quali a i e beha io s can be ob ained by changing pa ame e B, namely: Figu e 2: Pa ame e deDendence o he man in @a). CH2868-8/90/0000-1368$1.00 0 1990 IEEE - Fo B < 1, a s able pe iodic o bi esul s, he sequence x(n) oscilla ing be ween he alues : x;=A/(I +R) (3) x.1 -A/(l +B) This is ob iously an undesi able si ua ion o he applica ion being conside ed. - Fo B>1 The e a e no s able pe iodic o bi s o any pe iod. - Fo B>2 he e a e poin s inside he egion (-A,A) whose o bi s di e ge so leading o uns able global beha io .This si ua ion is illus a ed in Fig.3. Figu e 3: Illus a ing di e gence o he map in (2a). Le us concen a e on he ange o pa ame e alues whe e nei he s able o bi s no di e gen poin s a e ound, (1 <B <2). Th ee subin e als can be dis inguished o his case inside he in e al (-A,A): (04) All he o bi s s a ing in his in e al emain con ined o i . (A,Al(B-l)) All he o bi s s a ing he e map in o he subin e al (-A,A) (A/(B-l),m) All he o bi s s a ing he e a e di e gen . These di e en p ope ies o he subin e als a e illus a ed in Fig.4a. In p ac ical implemen a ion o (2a), design c i e ia should be p o ided o a oid he co esponden ci cui o be locked a pa asi ic s able poin s, caused by he sa u a ion o he ac i e de ices. Owing o p e ious conside a ions we conclude ha his can be achie ed by se ing he le el o he bias sou ces a a alue comp ised in he second subin e al abo e. I is in ac equi alen o ans o m he o iginal map in o he one in Fig.4b. Obse e ha any o bi e en ually going in o one o he sa u a ion egions is o ced o e u n o he egion o in e es (-Al(B-l),A/(B-l)~. Obse e om Fig.4a ha he alue o B has 60 be selec ed small enough o p o ide wide la e al sa e y .ubin e als: (Al(1 -B),-A), (A,Al(B-1)). On hep he hand, he la ge he alue o B (BS2) is he mo e sui able is he signal x(n) o he gene a ion o andom numbe s. As a ma e o ac an ideal Be nouilli shi esul s o B =2 [41. We hence see ha a adeo in he alues o B is equi ed in any p ac ical design. This adeo can be a oided by eso ing o a sligh ly mo e complex map which is shown in Fig.5 and whose equa ion is: I ,: 1.' Figu e 4: a)Illus a ing o bi s om he di e en subin e als; b)A oiding pa asi ic s able poin s by p ope bias se ing (4) whe e dx) is gi en by (2a) wi h B=2 and C is some cons an g ea e han A. The alue o C is p o en no o be c i ical by nume ical es s. C=2A seems o be a good alue. As i can be seen in Fig.5, poin s ha lie in he egion (A, 2A) a e e-mapped in o he egion (0, A). E en i he slope B is g ea e han 2 he map is s ill s able and appa en ly exhibi s he same beha io as o B less han 2. Analog sampled-da a implemen a ions The disc e e map o (4) can be e y easily and accu a ely implemen ed in MOS VLSI . Fig.6 shows a wo phase s ay-insensi i e SC ci cui . Obse e he ou pu o he compa a o di ec ly codi ies he sign o he chao ic analog sequence x(n). Tha means he e is no need o use he ex a compa a o in he block diag am o Fig.1. In o de o ensu e ull compa ibili y wi h digi al echnologies, swi ched-cu en echniques can be used[8]. A ci cui implemen a ion using his echnique is shown in Fig.7. Obse e only MOS ansis o s a e equi ed. As in he SC ci cui , he compa a o equi ed o he map di ec ly p o ides he andom digi al sequence. IXI<A ix)= /@ Sx-Csgn(x) lxl2A 1369 -- / I Figu e 5: Illus a ing he map in (4) & Figu e 6: A SC ci cui o he map in (4) I II I Teo I Figu e 7a: Basic blocks o a SI map Figu e 7b: SI implemen a ion o he map in (4) Simula ion Kesul s and Digi al P ocesso A lo o simula ions ha e been pe o med o con i m sui abili y o he p oposed model. In o de o analyze egula i y p ope ies, a andom p ocess consis ing o a se o a ound 1000 maps was conside ed. Pa ame e s in he di e en maps o he se we e andomly modi ied ( aking in o accoun ypical echnological de ia ions) a ound hei nominal alue. Up o 105 i e a ions we e conside ed o p ope ly analyze s a iona i y p ope ies. Also, in o de o mo e ealis ic emula e he beha io o an ac ual ci cui implemen a ion, a gaussian noise was added o he calcula ed sample o he signal in each i e a ion s ep. The simula ions we e ca ied ou on a 15M lops CONVEX 220 ec o ial compu e . The bi s in he sequences we e g ouped in o digi al wo ds (bo h 4 and 8 bi s) and he p obabili y o each wo d was measu ed. Fo he map o (2a) wi h B=1.85 (limi alue) he de ia ion om he ideal dis ibu ion o wo ds o 4 bi s was 46% in he ypical case, and 59% in he wo s case. On he o he hand, o he map (4) wi h B=2, he ypical de ia ion was 12%being 35% in he wo s case. Fo bo h maps, he obse ed de ia ions can be in e p e ed as being a consequence o he au oco ela ion o he bi s in he o iginal sequence. This in e p e a ion sugges s a echnique o equalize p obabili ies consis ing in dec easing he sampling a e o elimina ing he sel co ela ion.The p ice o be paid o is a dec easing in he ope a ion speed o he ci cui which may be no con enien depending on he applica ion. An al e na i e me hod is based on he use o a e y simple digi al elemen : he T-bis able. Le us emind he inpu -ou pu map o such a digi al block: Inpu ++$ S a e (5) Conside now an a bi a y digi al sequence d i ing a T-bis able. Taking (5) in o accoun i is easy o conclude ha he digi al sequence a he ou pu will exhibi he same p ope ies o "1" and "0" e en s. Also i he p obabili ies o "I " and "0" we e al eady he same, hen all he sequences o 2 bi s will ha e he same p obabili y a '.he ou pu . To see his keep in mind ha he s a es "0" and "1 " a e equally p obable because hey depend on he pa i y o he numbe o "1 "5 ecei ed by he bis able; as long as he inpu sequence is ape iodic he pa i y is comple ely andom. Thus, we ha e ha connec ing wo T-bis ables o he digi al gene a o all he sequences o wo bi s a he ou pu ha e he same p obabili y. 1370 In gene al when n T-bis ables a e connec ed o he digi al ene a o , all he sequences o n bi s ha e he same p obabiyi y . To p o e his conside a sys em consis ing o n T- bis ables. Gi en an inpu sequence i n), he e is one and only one possible s a e o he sys em o each possible ou pu sequence o(n). So, i all he s a es o he sys em a e equally p obable, all he ou pu sequences a e equally p obable oo. Now, all he s a es o he sys em a e equally p obable because he s a e o he i s bis able depends on he pa i y o he numbe o ”1”‘s ecei ed, he s a e o he second bis able depends on he pa i y gene a ed by he i s (no on he s a e o i ), he hi d on he second and so on. Again as long as he inpu sequence is ape iodic, hose pa i ies a e andom and so is he s a e o he sys em. Un o una ely n T-bis ables do no gua an ee equal p obabili y o wo ds o e n bi s, bu we can use a ha dwa e inplemen a ion algo i hms o he kind p oposed by Knu h [7] . I we wan o gene a e wo ds o n bi s no sel -co ela ed, a e he p ocess desc ibed abo e, we ill a RAM o 2n wo ds, hen numbe s a e picked up om RAM add esses gi en b wo ds o he sequence delayed a la ge enough numbe o cycles. The add ess used is hen e illed wi h he incoming wo d and he p ocess con inues. A block scheme o he digi al p ocesso is shown in Fig.8. Reg. 0 Reg.1 Reg.2 Add ess 4 Ou pu Inpu Reg.n 4 Figu e 8: Block scheme o he digi al p ocesso . Discussion o esul s Piecewise-linea maps a e easy o implemen using sampled-da a analogue echniques, ei he SC o S1,and p o ide a na u al way o he gene a ion o uly andom numbe gene e o s in monoli hic o m. Se e al p o o ypes o Fig.6 and Fig.7 ha e been designed bo h in 3pm and 2pm CMOS. In pa icula Fig.9 shows he layou o a SI y o ype o a n-well double poly 3pm CMOS echnology. imula ion esul s o hese p o o ypes a e in acco dance o he expec ed heo e ical pe o mance. . Figu e 9: Layou o a SI p o o ype. Re e ences [l] S. Haykin: “Communica ion Sys ems”. Wiley 1978. [2] W. H. P ess e al.: “Nume ical Recipes”. Camb idge Uni e si y P ess 1986. [3] R. L. De aney: “An in oduc ion o Chao ic Dynamical Sys ems”. Benjamin I Cummings 1986. [4] H.G. Schus e : “De e minis ic Chaos”. Bi khause 1984. [5] R. A. G ego ian and G. C. Temes: “Analog MOS In eg a ed Ci cui s o Signal P ocessing”. Wiley 1986 S. Espejo e al.: “Ap lica ion o Piecewise-Linea Swi ched-Capaci o 8i cui s o Random Numbe Gene a ion”. P oc. Midwes S mD. Ci cui s Sys ems. [6] “* Aug. 1989. D.E. Knu h: ”Seminume ical Algo i hms” (2nd edi ion). Addison Wesle 1981. [7] [81 J. B. Hughes e al.: ”Swi ched Cu en s. A new Technique o Analog Sampled-Da a Signal P ocessing”. P oc. In e na Lonal Symp. on Ci cui s and Sys ems, 1989, pp. 1584-1587. 1371