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.