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