Chao ic maps and pa e n ecogni ion – he XOR p oblem
Alan Roge s
a,*
, John G. Kea ing
b
, Robe Sho en
a
, Daniel M. Heffe nan
c,d
a
Depa men o Elec onic Enginee ing, Na ional Uni e si y o I eland, Maynoo h, Co. Kilda e, I eland
b
Depa men o Compu e Science, Na ional Uni e si y o I eland, Maynoo h, Co. Kilda e, I eland
c
Depa men o Ma hema ical Physics, Na ional Uni e si y o I eland, Maynoo h, Co. Kilda e, I eland
d
School o Theo e ical Physics, Dublin Ins i u e o Ad anced S udies, Dublin 4, I eland
Accep ed 31 July 2001
Abs ac
In his epo , we desc ibe a no el applica ion o he Bake ’s map. We demons a e ha he chao ic p ope ies o his
map can be used o implemen basic ope a ions in Boolean logic. This obse a ion leads na u ally o he possibili y o
new compu a ional models and implemen a ions o con en ional compu a ional sys ems. He e we show ha by
conside ing he a ia ion o he ac al dimension o i s a ac o , and using a ying pa ame e alues as inpu s, he
gene alised Bake ’s map can be used as a na u al exclusi e OR (XOR) ga e. Fu he , his map can also be used o c ea e
o he logical unc ions such as he AND ga e. The efficacy o ou esul s a e demons a ed by means o a conc e e
applica ion; namely by designing, o he bes o ou knowledge, o he fi s ime, a hal -adde ha is cons uc ed
en i ely by u ilising chao ic dynamics. Ó2002 Else ie Science L d. All igh s ese ed.
1. In oduc ion
Nonlinea dynamics, as a subjec , has eached a conside able deg ee o ma u i y in ecen yea s. Howe e , despi e
apid heo e ical ad ances in he subjec , he gene al a ea o nonlinea dynamics has also been cha ac e ised by a lack o
enginee ing applica ions (wi h he excep ion o nonlinea con ol [1]) ha exploi he undamen al heo y and p ope ies
o nonlinea sys ems. This obse a ion is somewha su p ising since many enginee ing sys ems a e designed o exhibi
beha iou commonly ound in nonlinea sys ems. Examples o his abound in he ae ospace indus y. Figh e ai c a ,
o ins ance, a e designed o ha e uns able dynamics o aid manoeu abili y unde ex eme fligh condi ions. Such
ai c a s a e a ificially s abilised unde no mal fligh condi ions. The p ope ies o local ins abili y o ajec o ies ( apid
manoeu abili y) and global s abili y o o bi s (sa e y) a e o en ound in nonlinea and chao ic sys ems. One p ope y
in pa icula is ex emely a ac i e om an enginee ing pe spec i e: exponen ial sensi i i y o ini ial condi ions, which
allows chao ic sys ems o be hype sensi i e o changes in sys em pa ame e s; and ye unde lying his sensi i i y, chao ic
sys ems ha e global p ope ies, such as ac al dimension o s a e-space a ac o , which can be ex ac ed and used as
ou pu a iables. This obse a ion sugges s ha chao ic dynamics can be used as he design basis o apid sys em
iden ifica ion, and in he design o high pe o mance con ol sys ems. He e, we begin he p ocess o examining he
sui abili y o chao ic maps o such enginee ing applica ions.
In his pape , we will show how he gene alised Bake ’s map can be used o sol e he exclusi e OR (XOR) p oblem.
This is a undamen al p oblem o pa e n ecogni ion, and in ol es elling a a single glance whe he a poin belongs o
one o he wo classes: class A o NOT class A (class B), whe e class A consis s o wo diagonally opposi e co ne s o a
uni squa e, and class B consis s o he o he wo co ne s. The inabili y o a single-laye pe cep ion o sol e his p oblem
Chaos, Soli ons and F ac als 14 (2002) 57–70
www.else ie .com/loca e/chaos
*
Co esponding au ho . Tel.: 353-1-7086067; ax: 353-1-7083967.
E-mail add ess: [email p o ec ed] (A. Roge s).
0960-0779/02/$ - see on ma e Ó2002 Else ie Science L d. All igh s ese ed.
PII: S0960-0779(01)00181-3
is conside ed o be a se e e d awback o ANNs as a mechanism o nonlinea p oblem-sol ing. We will conside he
XOR p oblem in mo e dep h la e .
The gene alised Bake ’s map is a wo-dimensional, h ee-pa ame e , nonlinea mapping, which is chao ic o i -
ually all pa ame e alues. We use i he e because i is one o he bes -unde s ood chao ic maps, and is pa icula ly
sui ed o igo ous analysis (see [2]). I also has he use ul p ope y ha i s Lyapuno dimension is mono onically in-
c easing o a wide ange o pa ame e alues, and we shall u ilise his when we de elop he XOR ga e. To he bes o
ou knowledge, nei he Bake ’s map, no any o he chao ic map, has been p e iously used o sol e he XOR p oblem in
his way.
The es o he pape is o ganised as ollows. In Sec ion 2 we will desc ibe he XOR p oblem, and he way in which
a ificial neu al ne wo ks (ANNs) can, and mo e impo an ly, canno , sol e his p oblem. We shall desc ibe he Bake ’s
map in Sec ion 3. In Sec ion 4 we show how he Bake ’s map can ac as a na u al XOR sys em, and we p esen some o
he p ope ies, ad an ages, and d awbacks, o he new sys em. In Sec ion 5 we show how a hal -adde can be buil using
wo Bake ’s maps. In Appendix A, we b iefly desc ibe ANNs and hei use as pa e n classifie s.
2. Pa e n ecogni ion and he XOR p oblem
The pa e n ecogni ion p oblem consis s o designing algo i hms ha au oma ically classi y ea u e ec o s asso-
cia ed wi h specific pa e ns as belonging o one o a fini e numbe o classes. A benchma k p oblem in he design o
pa e n ecogni ion sys ems is he Boolean exclusi e OR (XOR) p oblem. The s anda d XOR p oblem is depic ed in
Fig. 1. He e he diagonally opposi e co ne -pai s o he uni squa e o m wo classes, A and B (o NOT A). F om he
figu e, i is clea ha i is no possible o d aw a single s aigh line which will sepa a e he wo classes. This obse a ion
is c ucial in explaining he inabili y o a single-laye pe cep on o sol e his p oblem (an o e iew o he pe cep on is
gi en in Appendix A).
This p oblem can be sol ed using mul i-laye pe cep ons (MLPs), o by using mo e elabo a e single-laye ANNs
such as he adial basis unc ion neu al ne wo k [3]. Howe e , he inabili y o simple ANNs, such as he Adeline [4], o
sol e his p oblem, effec i ely ended esea ch in e es in he a ea o ANNs o o e 20 yea s, which highligh s he
impo ance o he XOR p oblem in he design o pa e n ecogni ion sys ems. In his pape , we show ha he gen-
e alised Bake ’s map can be ained o sol e his p oblem in a s aigh o wa d manne .
3. Chaos and he Bake ’s map
3.1. The gene alised Bake ’s map
In hei classic s udy o ac al dimensions, Fa me e al. [4] in oduced he gene alised Bake ’s map in o de o
ob ain igo ous esul s on he dimension o s ange a ac o s. I is a ans o ma ion o he uni squa e ½0;1½0;1, and
has h ee pa ame e s, R1,R2and S:
xnþ1¼R1xni yn<S;
1=2þR2xni ynPS;

ynþ1¼
yn=Si yn<S;
ynS
1Si ynPS:
8
<
:
ð1Þ
Fig. 1. The exclusi e OR (XOR) p oblem: poin s (0,0) and (1,1) a e membe s o class A; poin s (0,1) and (1,0) a e membe s o class B.
58 A. Roge s e al. / Chaos, Soli ons and F ac als 14 (2002) 57–70
We illus a e he Bake ’s map ans o ma ion in Fig. 2. As can be seen om Eq. (1), he mapping depends on whe he
he poin in ques ion is abo e o below a ho izon al line y¼S.
Since he Bake ’s Map is a mapping o he uni squa e, we es ic S o he ange (0,1) and R1and R2 o he ange (0,
0.5]. In Fig. 2, we show he ac ion o he map on he en i e uni squa e. I e a ing he map gi es wo e ical s ips, whose
wid hs depend on R1and R2. I e a ing he map again gi es ou s ips, hen eigh s ips, and so on. The a ac o is he
union o a line segmen ( e ical di ec ion) and a Can o se (ho izon al di ec ion).
3.2. Lyapuno numbe s and Lyapuno dimension o he Bake ’s map
I can be seen in Fig. 2 ha he ac ion o he map leads o ‘s e ching’ in he y-di ec ion and ‘comp essing’ in he x-
di ec ion. I is possible o pu hese ac ions in o a mo e ma hema ical amewo k by using he no ion o Lyapuno
numbe s. These numbe s cha ac e ise he s abili y o he map, and a e defined as ollows:
Le Jn¼½JðxnÞJðxn1Þ... Jðx1Þ, whe e JðxÞis he Jacobian o he map, JðxÞ¼ðoF=oxÞ, o some map F.
Le j1ðnÞPj2ðnÞP PjpðnÞbe he magni udes o he peigen alues o Jn.
Then he Lyapuno numbe s a e gi en by
ki¼lim
n!1½jiðnÞ1=n;i¼1;2;...;p:ð2Þ
Since he Bake ’s map is wo-dimensional, i will ha e wo Lyapuno numbe s, cha ac e ising he a e age s e ching/
comp ession ac o s in he x- and y-di ec ions (see Fig. 3). No e ha he Lyapuno exponen s a e simply he loga i hms
o he Lyapuno numbe s. I is cus oma y o o de he Lyapuno numbe s, so ha k1>k2>>kn.
The Lyapuno dimension was in oduced by Kaplan and Yo ke [5] in he so-called Kaplan–Yo ke conjec u e: ha
he Lyapuno dimension DLis he same as he in o ma ion dimension o ‘‘ ypical’’ a ac o s. Fo he Bake ’s map,
DL¼1þlog k1
log 1=k2
:ð3Þ
Fig. 2. Ac ion o he Bake ’s map on uni squa e: ans o ms squa e in o wo s ips, hen ou s ips, eigh s ips, and so on.
Fig. 3. Lyapuno Numbe s cha ac e ise he a e age s e ching ac o s o some small ci cle o adius d. In his case, k1>1 and k2<1.
A. Roge s e al. / Chaos, Soli ons and F ac als 14 (2002) 57–70 59
The Jacobian o Eq. (1) can be w i en in he ollowing o m:
J¼L2ðyÞ0
0L1ðyÞ

;whe e
L1ðyÞ¼ 1=Swhen y<S;
1=ð1SÞwhen y>S;

L2ðyÞ¼ R1when y<S;
R2when y>S:

So om Eq. (2) we ge
k1¼lim
n!1 L1ðynÞ...L1ðy1Þ½
1=n;
k2¼lim
n!1 L2ðynÞ...L2ðy1Þ½
1=n:
By aking logs, and wi h some manipula ion, no icing ha he o bi s a e e godic in he y-di ec ion, we find ha he
Lyapuno exponen s a e:
log ky¼Slog 1
Sþð1SÞlog 1
1S;ð4aÞ
log kx¼Slog R1þð1SÞlog R2:ð4bÞ
In ou implemen a ion o he XOR ga e, we only equi e wo inpu pa ame e s, so we shall le R2¼R1, in which case we
find ha
log kx¼log R1:ð5Þ
4. Using he Bake ’s Map o sol e he XOR p oblem
4.1. Backg ound
I we plo he ac al dimension o Bake ’s map o a ying alues o Rand S, i becomes ob ious how we can use
he map o sol e he XOR p oblem. Fi s ly, we show how he Lyapuno exponen s (Eqs. (4a) and (5)) a y wi h Rand
S(see Fig. 4). Clea ly, since he map is con ac i e in x-di ec ion, he Lyapuno exponen in ha di ec ion is always
nega i e. Con e sely, he map is expansi e in he y-di ec ion, and he e o e ha Lyapuno exponen is always posi i e.
F om Eq. (3), he Lyapuno dimension is gi en by
DL¼1log ky
log kx
:ð6Þ
In Fig. 5, we plo DLagains R, wi h Sas a pa ame e . No ice ha he ac al dimension a ies be ween 1 and 2, as we
would expec . Due o he symme y o Fig. 4(b), he ac al dimension is symme ical abou S¼0:5. We ha e chosen
sligh ly asymme ical alues o S o illus a e his.
We can choose alues o Rand S, so ha a pai (low R, high S) and ano he pai (high R, low S) gi e he same ac al
dimension, say DA. This co esponds o a diagonally opposi e co ne pai in he XOR p oblem. We can say, he e o e,
ha i he ac al dimension DL¼DA, hen he inpu s a e in class A, and i DL6¼ DA, hen he inpu s belong o class B.
No e ha we always limi S o he ange [0, 0.5], o ensu e a unique ac al dimension o any gi en (R;S) pai .
Fo example, in Fig. 6, we could say ha he ollowing pai s o pa ame e s o m classes.
Ob iously, he poin s in Table 1 do no lie on a pe ec squa e, bu ha is unimpo an . The key idea is ha wo pai s
o diagonally opposing poin s a e mapped o he same class. I is also clea ha we a e qui e es ic ed in he possible
pai s o poin s which we can map o he same ac al dimension. Howe e , i we choose any ou (R;S) pai s o poin s
co esponding oughly o (low, low), (low, high), (high, low) and (high, high), hen by d awing a s aigh line h ough
he (low, high), (high, low) poin s and in e sec ing he y-axis, we can effec i ely sol e he XOR p oblem o much la ge
se o inpu s. We call he in e sec ion o his line wi h he y-axis, DM, he (modified) Lyapuno dimension. This is il-
lus a ed in Fig. 6.
P ocedu e o calcula ion o DM:
(i) Gi en ou poin s in he R–Splane, selec he wo poin s belonging o he same class: ðRa;SbÞ,ðRb;SaÞin Fig. 6.
(ii) Calcula e he Lyapuno dimensions co esponding o he wo poin s, called D1,D2.
(iii) Calcula e he slope, m¼ðD1D2Þ=ðRaRbÞ.
(i ) The dimension DM¼D1þmRa¼D2þmRb.
60 A. Roge s e al. / Chaos, Soli ons and F ac als 14 (2002) 57–70
As DMis cons an ly calcula ed, we can ell whe he he inpu s a e in class A, o no . An algo i hm o his o m is
e e ed o as a aining algo i hm in he ANN and s a is ical pa e n ecogni ion li e a u e [8]. The a ailabili y o such
an algo i hm, and i s complexi y, ul ima ely de e mines he applicabili y o a pa icula pa adigm o a gi en p oblem.
In ou case, gi en a se o class labels, and a se o ec o s, he aining pa s o he pa e n ecogni ion p oblem is
i ial, in ol ing only he simple calcula ion o a slope. Fo an ANN, sol ing his p oblem equi es epea ed calcula ion
o he slope o a leas wo hype planes, and so is mo e compu a ionally in ensi e.
4.2. Compu e simula ion
The sys em is easily implemen ed wi h a ew lines o code. Essen ially, we need o simula e Bake ’s map, gi en i s
inpu pa ame e s, and hen, using i s s a e a iables xand y, compu e he Lyapuno dimension DLo he a ac o (see
Fig. 7).
Fig. 4. Va ia ion o Lyapuno exponen in he (a) x-di ec ion, (b) y-di ec ion.
A. Roge s e al. / Chaos, Soli ons and F ac als 14 (2002) 57–70 61

Ob iously, he speed o he sys em depends on he compu a ion o he Lyapuno dimension. The adi ional way o
do his is qui e slow [6], and assumes ha no de ailed in o ma ion is a ailable abou he sys em, ha is o say, only a
ime-se ies x0;x1;x2;...;is a ailable om he sys em. Gi en his ime se ies, some alue om he sequence is selec ed,
Fig. 6. A mo e gene al way o sol ing he XOR p oblem: d aw a s aigh line h ough he wo poin s belonging o class A (say), and
find whe e he line in e sec s he y-axis.
Fig. 5. Va ia ion o ac al dimension wi h a ying pa ame e alues.
62 A. Roge s e al. / Chaos, Soli ons and F ac als 14 (2002) 57–70
say xi, and hen one sea ches he sequence o ano he alue xj ha is close o xi. The sequence o diffe ences is assumed
o di e ge exponen ially, on he a e age:
d0¼jxjxij
d1¼jxjþ1xiþ1j
.
.
.
dn¼jxjþnxiþnj
ð7Þ
We assume ha
dn¼d0ekn;
which, a e aking loga i hms, gi es
k¼1
nlog dn
d0
:ð8Þ
Since we would like ou sys em o be as as as possible, his me hod is compu a ionally expensi e, as i in ol es
con inually sea ching h ough some la ge a ay o numbe s, and hen pe o ming addi ional calcula ions gi en in Eqs.
(7) and (8). As we ha e Bake ’s map da a eadily a ailable, and since we ha e i s inpu pa ame e s al eady, we ha e
ound a quicke way o compu e he Lyapuno numbe s. They a e calcula ed as ollows: we i e a e he Bake ’s map
ðx;yÞas no mal (call i B1), bu we also i e a e ano he Bake ’s map ðB2Þin pa allel wi h i . Fo each pai ðxn;ynÞ
gene a ed by B1, we use some nea by pai o numbe s ðxnþd;ynþeÞas ini ial condi ions o B2. We hen i e a e B2
once (we ha e ound ha i e a ing mo e han once does no imp o e accu acy, bu me ely slows hings down). Now, we
compu e he Lyapuno numbe s
kx¼log j ðxn;ynÞ ðxnþd;ynþdÞjXcomp:
d;
ky¼log j ðxn;ynÞ ðxnþe;ynþeÞjYcomp:
e:
ð9Þ
The numbe s he eby compu ed end o be noisy, bu when a e aged, hey gi e he expec ed heo e ical alues. No e
also ha since he map is always con ac ing in he x-di ec ion, choosing a e y small alue o dgi es en i ely inac-
cu a e esul s, hence we end o use d1.
To illus a e he ac ion o he sys em, we choose ou dis inc poin s, mo e o less a bi a ily (see Fig. 8).
We compu e he slope o he line be ween poin s 1 and 2, belonging o class A, o be m¼1:60667, and he
(modified) Lyapuno dimension DM¼1:752 (see Table 2).
In Fig. 9, we plo he ou pu om Bake ’s map sys em. He e, we ha e a e aged e e y 200 poin s, o smoo h he
ou pu . Clea ly, he e is a adeoff be ween speed o pa e n classifica ion, and accu acy. I we a e age mo e poin s, hen
Fig. 7. The chao ic XOR sys em: he ou pu s om he map a e he s a e a iables xand y, and hese a e used o compu e he
Lyapuno dimension.
Table 1
Pa ame e alues and hei co esponding ac al dimension, and class, as in Fig. 5
R alue S alue F ac al dimension Class
0.1 0.5 1.3 A
0.36 0.1 1.3 A
0.1 0.1 1.14 B (NOT A)
0.36 0.5 1.68 B (NOT A)
A. Roge s e al. / Chaos, Soli ons and F ac als 14 (2002) 57–70 63
Fig. 8. The ou poin s selec ed o illus a e he chao ic XOR sys em.
Fig. 9. Ou pu om he chao ic XOR sys em, wi h inpu s as in Table 2. Con iguous se s o 200 poin s a e a e aged. Class A co -
esponds o a modified Lyapuno dimension DM1:75. No e ha we cycle h ough poin s (1), (4), (2), (3) and (1), espec i ely.
Table 2
Pa ame e alues and hei co esponding classes, as shown in Fig. 6
Poin no. R alue S alue Class
1 0.2 0.5 A
2 0.3 0.1 A
3 0.15 0.2 B
4 0.35 0.4 B
64 A. Roge s e al. / Chaos, Soli ons and F ac als 14 (2002) 57–70
we ge a smoo he ou pu , bu his in oduces a delay in o he ecogni ion p ocess (see Figs. 10 and 11). No e also ha
he ela i e smoo hness also depends on how la ge he alue o Sis, wi h S¼0:5 gi ing a pe ec ly smoo h ou pu . This
is because he expansion a es in he y-di ec ion a e he same only when S¼0:5 (see Fig. 2).
I is clea om Fig. 11 ha by me ely obse ing i he ou pu dimension lies in some sui able ange abou 1.75, we
can ell i he inpu is in class A, o class B.
Fig. 10. Ou pu om he sys em wi h a 5-poin a e aging window. Since he ou pu dimension swi ches be ween wo alues only, he
5-poin a e aging leads o six possible alues o he ou pu .
Fig. 11. Ou pu om he sys em wi h 1000-poin a e aging windows.
A. Roge s e al. / Chaos, Soli ons and F ac als 14 (2002) 57–70 65