Stochastic pulse coded arithmetic

STOCHASTIC PULSE CODED ARITHMETIC S.L. To al, J.M. Que o, Membe , IEEE and L.G. F anquelo, Senio Membe , IEEE Depa men o Elec onic Enginee ing, Uni e si y o Se ille A da. Camino de los Descub imien os, 41092, Se ille, Spain ABSTRACT Among he di e en pulse codi ica ion echniques, s ochas ic pulse codi ica ion has i s own a i hme ic based on he simila i y be ween boolean algeb a and s a is ic algeb a. Summa ion and mul iplica ion a e he wo basic a i hme ic ope a ions deeply ea ed in li e a u e. In his pape we p esen wo digi al s ochas ic ci cui s ha ex- end adi ional s ochas ic algeb a: a di ision ci cui and a squa e- oo ci cui , and he in e aces be ween he ana- log and s ochas ic domain. As esul , we a e able o p ocess analog inpu signals wi h a simple and comple e p ocessing sys em. These ci - cui s can be implemen ed in low-cos and low-powe digi- al p og ammable de ices. 1. INTRODUCTION S ochas ic sys ems make pseudo analog ope a ions using s ochas ically coded pulse sequences [1], [2]. In o ma ion is ep esen ed by he s a is icalmean alue o a pulse se- quence. In a bina y logic, i is he p obabili y o aking a “high” le el. Figu e 1 shows he gene a ion o a s ochas- ic pulse s eam om a digi al alue. The alue s o ed RANDOM NUMBER COMP Ou pu REGISTER Figu e 1: Digi al o s ochas ic con e sion (DSC). in a egis e is compa ed wi h a andom numbe gene a- o . I he andom numbe gene a o is less o equal han he egis e alue, he ou pu o he compa a o is se o a high le el. O he wise, a low le el is se . Figu e 1 can be conside ed as he scheme o a digi al o s ochas ic con- e e . Equa ion 1 gi e us he p obabili y o an ou pu high le el. P ( O u pu = 00 1 00 )= D ig i al V al ue 2 n (1) The s ochas ic pulses eam a he ou pu o he compa a- o is a Be nouilli’s sequence, wi h p obabili y o a “high” le el ou pu equal o he numbe s o ed in he egis e . Be nouilli’s heo em gua an ees ha he mean o he ad- di ion o he Be nouilli’s andom a iables ends o ha p obabili y. So, he mo e pulses we p ocess, he bes ac- cu acy we ob ain when ep esen ing a digi al alue by means o a s ochas ic pulse s eam. The e a e se e al me hods o gene a e andom num- be s. Digi ally, we can implemen a pseudo andom num- be gene a o , ha is, a sequence o numbe wi h an- domness appea ance,bu exhibi inga epea ablepa e n. Among he whole a ie y o pseudo andom numbe gen- e a o s [3], he mos ex ended one is he linea eedback shi egis e (LFSR) o maximum leng h [4]. S ochas ic pulse coded a i hme ic is e y close o p o- cessing wi h o e sampled signals [5]. The main di e - ence is he ollowing: while pulse densi y a i hme ic only pe o ms basic ope a ions such us addi ion and mul i- plica ion, s ochas ic pulse coded a i hme ic can pe o m supplemen a y ope a ions ha will be p esen ed in his pape . This app oach allow a e y simple elec onic im- plemen a ion o eal applica ions. Pa icula ly, a eac i e powe measu emen me hod and a ha dwa e elec onic implemen a ion o a passi i y based con olle o a se- ies esonan con e e ha e been p oposed in [6] and [7]. In nex sec ion, we will explain basic con e sion schemes be ween analog and s ochas ic domain. Sec ion III desc ibes he ci cui s ha pe o m adi ionals ochas- ic compu a ion, ha is, summa ion and mul iplica ion. Then, di ision and oo -squa e ci cui s will be p esen ed. Finally, conclusions and applica ionso hese pulse coded p ocessing sys em will be poin ed ou . 2. CONVERSION SCHEMES A digi al o analog alue can be eco e ed om a digi al s ochas ic pulse s eam by es ima ing i smean alue in a long enough sequence. A coun e can pe o m he es ima- ion in he digi al domain and a RC ci cui is sui able o he analog one. S a is ically,mean alue es ima o hasa Gaussiandis- ibu ion wi h a mean alue equals o he mean alue o he disc e e Be nouilli sequenceand a s anda dde ia ion ha dec eases wi h oo -squa e o he leng h N o ha se- quence (equa ion 2) mean alue es ima o : AN ( ;  p N ) (2) Figu e 2 illus a es an analog signal ex ac ed om a s ochas ic pulse s eam gene a ed wi h he gene al scheme LFSR plus a compa a o . A comple e s udy o his ci cui can be ound in [8]. Analog o s ochas ic con e - sion is a mo e complica ed ope a ion o pe o m. All he aaa lmn aa a 120 XOR bbb bbb 012 nlm Va Figu e 2: Analog mean alue o a s ochas ic pulse s eam ci cui sp oposeda e basedinanega i e eedbackscheme in which he analog inpu is compa ed wi h he analog signal ob ained om he digi al s ochas ic pulse s eam [9]. The p oblem is ha he RC in eg a ion o he digi al pulse s eam o igu e 3 is no a as in eg a ion, because cu o equency o he RC il e mus be low o eco e he mean alue. So, hebandwid ho he con e e islim- i ed below 1kHz o 8-bi accu acy and a digi al clock e- quency o 10 MHz [9]. In [10] has been p oposed a no el aaa lmn aa a 120 XOR bbb bbb 012 nlm Va Vin 1s 2nd3 d egis o de ap oximaciones sucesi as Figu e 3: Analog o s ochas ic con e sion con e sion ci cui based on sigma-del a modula ion ha imp o e bandwid h and accu acy. The eason is ha , in igu e 4, we in eg a e he e o signal be ween he analog inpu and he s ochas ic pulse s eam, wi hou a p e ious RC il e ing. Once we ha e p esen ed he con e e s be- Analog inpu signal Quan iza ion noise LFSR noise S ochas ic ou pu signal 1 1+2^n* s*s Func. H2 1 s*.s Func. H1 1bi CAD 1 1 bi DAC Figu e 4: Analog o s ochas ic con e sion basedon sigma- del a modula ion ween analog and digi al domain and s ochas ic domain, i is possible o de ine a s ochas ic p ocessing sys em in which, gi en a se o analog o digi al inpu s, hey a e s ochas ically con e ed, hen p ocessed, and inally e- co e ed om he s ochas ic pulse s eam as an analog o digi al alue. Figu e 5 is a block diag am ha illus- a es he whole p ocessing sys em. The main ad an age o he s ochas icp ocessing sys em is he possibili yo do- ing pseudo-analog unc ionswo king wi h hemean alue o he pulse s eam, bu wi h a digi al implemen a ion. (ADSC) (SADC) PROCESSING STOCHASTIC SYSTEMS PROGRAMMABLE DEVICE AN/DIG-ESTOC. STOC.-AN/DIG CONVERTER CONVERTER ANALOG/DIGITAL INPUTS ANALOG/DIGITAL OUTPUTS Figu e 5: S ochas ic p ocessing sys em 3. STOCHASTIC ARITHMETIC 3.1. Basic ope a ions T adi ional ope a ions de ined in he li e a u e a e p od- uc and summa ion [11]. This is because hey a e he yp- ical ope a ions in ol ed en each a i hme ic compu a ion and hey a e also ex ensi ely used in neu al ne wo ks, which is one o he applica ions o s ochas ic logic. Pa icula ly, he p oduc is pe o med by an AND ga e, p o ided ha he inpu s ochas ic pulse s eams a e un- co ela ed. I p 1 and p 2 a e he inpu pulse s eams o he AND ga e, he ou pu pulse s eam will only ha e a high le el when bo h p 1 and p 2 ha e a high le el. Then he ou pu o he AND ga e has a p obabili y equals o he p oduc o he inpu p obabili ies. Summa ionisamo e complica edope a ion o pe o m. The eason is ha , using an OR ga e, he ope a ion ca - ied ou is no ac ually addi ion bu p 1 + p 2  p 1  p 2 .As an adde , he OR ga e has he disad an age o sa u a- ion when a pulse o e lapping occu s. The OR ga e is well sui edwhen we a e wo kingwi hlow pulsedensi ies. In he ci cui s p oposed, i will be used a signed adde scheme, based on he u h able 1. I is a combina ional block, wi h he ollowing logic equa ions (3): add ( p 1 ;p 2 ) = p 1  p 2 + p 1 ( sig ( p 1 )  sig ( p 2 ) sig [ add ( p 1 ;p 2 )] = p 1 sig ( p 1 )+ p 2 sig ( p 2 ) (3) Finally, in eg a ion is pe o med by an up/down COMP k sig( ) k I sig(I ) k k up/down COUNTER LFSR Figu e 6: S ochas ic in eg a ing ci cui AD D E R block p 1 sp 1 p 2 sp 2 ( p 1 + p 2 ) s ( p 1 + p 2 ) 0 0 0 0 0 - 0 0 0 1 0 - 0 0 1 0 1 0 0 0 1 1 1 1 0 1 0 0 0 - 0 1 0 1 0 - 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 - 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 - 1 1 1 1 1 1 Table 1: T u h able o ADDE R block coun e ha s o es in ime he s ochas ic pulse s eam ( k ;sig ( k )) . By compa ing he coun e wi h a LFSR ( ig- u e 6), we ha e an ou pu pulse s eam ep esen ing in- pu signal in eg a ion ( I k ;sig ( I k )) [12]. 3.2. Supplemen a y ope a ions Based on ci cui s o p oduc and summa ion, we will ex- end adi ional basics ochas ic ope a ions by means o a di ision ci cui and a squa e oo ci cui . Di ision ci cui is showed in igu e 7. I is a nega i e eedback scheme in which we a e looking o a s ochas ic pulse s eam p 1 =p 2 ha , mul iplied by p 2 , is compa ed wi h he inpu pulse s eam, inc easing o dec easing he coun e acco ding o he e o pulse s eam e k ; sig ( e k ) .As COMP e sig(e ) k up/down "+" (p /p ) LFSR COUNTER 12 k ADDER p 1 p 2 Figu e 7: S ochas ic di ision ci cui we a e using a nega i e eedback, he e o signal ends o ze o. So, he use o he adde block is jus i ied because we a e wo king wi h low pulse densi ies. As we can only mul iply by a alue in he ange [0,1] ( he alue codi ied is a p obabili y), i mus be e i ied ha p 1  p 2 . Expe imen al esul s has been ob ained using a digi al p og ammable de ice, wi h he con e e s o sec ion II, a coun e size o 10 bi s and a digi al clock equency o 12 MHz. Figu e 8 shows expe imen al esul s as a unc- ion o p 2 o di e en alues o p 1 , and compa ed o he heo e ical esul . Squa e oo ci cui has a simila ( igu e 9) scheme bu using he possibili ies o edundancy in in o ma ion o 0 0.2 0.4 0.6 0.8 1 p2 inpu 0 0.2 0.4 0.6 0.8 1 p1/p2 S ochas ic di ision Theo e ical di ision p1=0.1 p1=0.3 p1=0.5 p1=0.7 Figu e 8: Expe imen al esul s o he s ochas ic di ision ci cui as a unc ion o p 2 o di e en alues o p 1 s ochas ic logic. Two di e en pulse s eam can ep esen he same alue wi h a di e en pa e n o pulses. We a e looking o a s ochas ic pulse s eam ha , mul iplied by i sel using an unco ela ed e sion, ends o he inpu pulse s eam. The coun e is inc eased o dec eased ac- co ding o he e o signal, he same han he p e ious ci cui . The pulse s eams y 1 and y 2 a e edundan and bo h o hem ep esen s hesqua e oo o he inpu pulse s eam p 1 . Expe imen al esul s has been ob ained us- sig(e ) k e "+" COUNTER LFSR 1 COMP COMP LFSR 2 y y k 2 ADDER p 1 p 1 1 Figu e 9: S ochas ic squa e oo ci cui ing he con e e o sec ion II, leading o he igu e 10 (coun e size n=10 and clock equency F clk = 12 MHz ). The dynamical esponse o bo h di ision and squa e oo ci cui depends on h ee pa ame e s:  Digi al clock equency F clk .  Coun e size n.  p 2 o y 2 alue in di ision and oo squa e ci cui , e- spec i ely. Equa ions (4) and (5) a e he ime cons an o di ision 0 0.2 0.4 0.6 0.8 1 p 0.2 0.4 0.6 0.8 1 sq (p) S cohas ic oo −squa e Theo e ical oo −squa e Figu e 10: Expe imen al esul s o he s ochas ic squa e oo ci cui and squa e oo ci cui s [13]:  di = 2 n p 2 F clk (4)  oo = 2 n y 2 F clk (5) In o de o ob ain a easonable speed in bo h ci cui s, he clock equency mus be much highe han he sig- nal dynamic we wan o p ocess. This es ic ion is due o he ac o ep esen ing he in o ma ion as a p obabil- i y in a sequence o bina y pulses. Ne e heless, no ice ha we a e pe o ming pseudo-analog ope a ions wo k- ing wi h he mean alue o he andom pulse s eam. By using he con e sion schemes o sec ion II, we a e able o implemen a e y simple and pu ely digi al solu ions o eal applica ions, like he ones e e enced in [6] and [7]. 4. CONCLUSIONS The use o s ochas ic logic has p o ided a se o e y sim- ple a i hme ic ci cui s cons i u ing a design lib a y sui - able o sol e algeb aic and di e en ial equa ions. Some applica ionshas been ecen ly de eloped usings ochas ic a i hme ic. Pa icula ly. a se o algeb aic equa ions has been sol ed in [6] and a se o di e en ial equa ions has been sol ed in [7]. The e a e o he digi al and analog echniques o sol e di ision and squa e- oo ope a ions [14]. The main ad- an age o s ochas ic app oach is ha can be used mas- si ely in conjunc ion wi h o he s ochas ic ci cui s, ca - ying ou a se ialized in o ma ion and wi h a e y sim- ple analog and digi al in e ace. This app oach allows o he ealiza ion o quasi-analog unc ions bu aking ad- an ages o digi al ci cui s p ope ies. 5. REFERENCES [1] B.R. Gaines, S ochas ic compu ing sys ems, Ad ances In o m. Sys . Sci., ol. 2, pp. 37-172, 1969. [2] C.L. Jane , J.M. Que o, J.G. O ega and L.G. F an- quelo, Fully Pa allel S ochas ic Compu a ion A chi- ec u e, IEEE T ans. Signal P ocessing, ol. 44, no. 8, Au. 1996, pp. 2110- 2117, Aug. 1996. [3] M. Hennecke, RANEXP: expe imen al andom gene - a o package, Compu e Physics Communica ions 79, pages 261-267,1994. [4] S.W. Golomb, Shi Regis e Sequences, Holden-Day, San F ancisco, 1967. [5] J. Tombe g and K. Kaski, “Feasibili y o Synch onous Pulse-Densi y Modula ion A i hme ic in In eg a ed Ci cui Implemen a ions o A i icial Neu al Ne - wo ks”, P oc. o In nl. Symp. on Ci c. and Sys., IS- CAS’92, ol. 5, pp. 2232-2235, San Diego, CA, May 1992. [6] S.L. To al, J.M. Que o and L.G. F anquelo, “Powe Ene gy Me e ing based on Random Signal P ocessing (EC-RPS)”, ISCAS’98, Mon e ey, Cali o nia, May- June 1998. [7] J.M. Que o, S.L.To al, J.M. Ca asco, J.G. O ega and L.G. F anquelo, “Con inuous Time Con olle s using Digi al P og ammable De ices”, IECON’99, San Jose, CA, Dec. 1999 (accep ed o publica ion). [8] J.M. Que o, C.L. Jane , J.G. O ega and L.G. F an- quelo, “D/A Con e e ASIC Uses S ochas ic Logic”, EDN, pp. 86-88, Oc . 1996. [9] J.G. O ega, C.L. Jane , J.M. Que o, L.G. F anquelo, J. Pinilla and J. Se ano, “Analog o Digi al and Dig- i al o Analog Con e sion Based on S ochas ic Logic”, IEEE In l. Con . on Indus ialElec onics,IECON’95, O lando, No . 1995. [10] S.L. To al, J.M. Que o, J.G. O ega and L.G. F an- quelo, “S ochas ic A/D Sigma Del a Con e e on FPGA”, In nl. P oc. o 42nd Midwes Symposium on Ci cui s and Sys ems, MWSCAS’99, Las C uces, Nue o Mexico, Aug. 1999. [11] S. Ribei o, “Random-pulse machines”, IEEE T ans- ac ionsonElec onicCompu e s, ol.EC-16,no.3, pp. 261-276, June 1967. [12] S.L. To al, J.M. Que o and L.G. F anquelo, “Reac- i e Powe and Ene gy Me e based on Random Sig- nal P ocessing”, DCIS’98, Mad id, pp. 346-351, No . 1998. [13] J.M. Que o, S.L. To al, J.G. O ega and L.G. F an- quelo, “Con inuous Time Fil e Design UsingS ochas- ic Logic”, In nl. P oc. o 42nd Midwes Symposium on Ci cui s and Sys ems, MWSCAS’99, Las C uces, Nue o Mexico, Aug. 1999. [14] M.D. E cego ac and T. Lang, “Di ision and Squa e- Roo : Digi -Recu ence Algo i hms and Implemen a- ions”, Bos on, Kluwe Academic, 1994.