Technology Mapping o Speed-Independen Ci cui s: Decomposi ion and
Resyn hesis
Alex Kond a ye , The Uni e si y
o
Aizu,
Japan
Jo di Co adella, Uni . Poli ecnica de Ca alunya, Ba celona, Spain*
Michael Kishine sky,
The
Uni e si y
o
Aizu,
Japan
Lucian0 La agno, Poli ecnico
di
To ino,
I aly
Alex Yako le , Uni e si y
o
Newcas le
upon
Tyne, Uni ed Kingdom
!
Abs ac
This pape p esen s heo y and p ac ical implemen a-
ion
o
a me hod o mul i-le el logic syn hesis
o
speed-
independen ci cui s. An ini ial ci cui implemen a ion is
assumed o sa is y he mono onous co e condi ions bu is
echnology independen . The p oposed me hod pedo ms
bo h combina ional {inse ing new ga es) and sequen ial
{inse ing new memo y elemen s) decomposi ion
o
com-
plex ga es in a gi en s anda d cell lib a y, while p e-
se ing o iginal beha iou and speed-independence. The
algo i hm applies known e icien algeb aic ac o iza ion
echniques om combina ional mul i-le el logic syn hesis,
bu achie es also
boolean
simpli ica ion and sequen ial
decomposi ion. The me hod
allows
sha ing
o
decomposed
logic.
1
In oduc ion
Speed-independen
ci cui s, o igina ing om
D.E.
Mulle ’s wo k
[
111, a e
haza d- ee unde he unbounded
ga e delay model.
Wi h ecen p og ess in de eloping
e i-
cien analysis and syn hesis echniques, suppo ed by
CAD
ools, his sub-class has mo ed close o p ac ice, bea -
ing in mind
he
ad an ages o speed-independen designs,
such as hei g ea e empo al obus ness and sel -checking
p ope ies.
Exis ing me hods o logic syn hesis o
speed-
independen ci cui s ei he assume ha he implemen a-
ion lib a y con ains
and
ga es wi h unbounded anin and
“ ee” inpu in e sions ([1,5,9]) o hey use non-s anda d
‘‘haza d abso bing” lip- lops whose e ec i eness
inp ac-
ice
s ill needs o be e alua ed
([
141). O he esul s on he
implemen abili y o semi-modula ci cui s wi hou inpu s
using wo-inpu / wo-ou pu
and
and
o
ga es ([HI) a e
only in e es ing om
a
heo e ical s andpoin , due o hei
ex emely high implemen a ion cos .
In a emp s o map speed-independen ci cui s in o a
mo e ealis ic, s anda d cell-like, lib a y, o he so o e-
‘This wo k has been pa ly suppo ed by he
Minis y
o
Educa ion
o
Spain (CICYT TIC 95-0419), ACD-WG (ESPRIT21949) and in eg a ed
ac ion
UK
-1995-0203.
his wo k has been pa ly suppo ed by MURST esea ch p ojec
“VLSI
a chi ec u es”.
Wo k suppo ed
by
UK
EPSRC GRn24038, ACiD-WG (ESPRIT
21949) and B i ish Council in eg a edac ion Spain (MDR/1996/97/1159)
s ic ions ha e been exe cised.
Fo
example, he app oach
desc ibed in [16] wo ks only unde
he undamen al mode
assump ion,
which is o e ly es ic i e and does no i well
heo e ically wi h he unbounded delay assump ion. The
same au ho s desc ibe in [15] a me hod o pe o m ech-
nology mapping o speed-independen ci cui s ha only
decomposes exis ing ga es (e.g., a 3-inpu AND in o wo
2-inpu ANDs), wi hou any u he sea ch o
he
implemen-
a ion space. They do no explo e complex decomposi ions,
ha could use mul i-cube di iso s, o decompose se e al
ga es simul aneously. The same limi a ions also a ec he
wo k o
[l,
21. The idea o comple e esyn hesis o a
ci cui e e y ime a new signal is inse ed is exploi ed in
[12] o he echnology mapping o imed asynch onous
ci cui s. Howe e he sea ch space o decomposi ion
is
again limi ed by a single signal ne wo k.
In
[13]
a me hod o echnology mapping
o
speed-
independen ci cui s using complex ga es was p esen ed.
This me hod howe e only iden i ies when a se o simple
logic ga es can be implemen ed as a complex ga e, bu
canno pe o m a speed-independen decomposi ion o a
signal unc ion in case i does no i in o a single ga e. In
ac , his me hod can be used as a pos -op imiza ion s ep
a e ou p oposed decomposi ion echnique.
Finally, Bums analyzes [4] he co ec ness condi ions
o a decomposi ion o a sequen ial elemen ha
is
pa o
a speed-independen ci cui in o wo sequen ial elemen s
(o a sequen ial and a combina ional elemen ). No ably,
hese condi ions a e analyzed using he o iginal (unex-
panded) beha iou al model, hus helping he e iciency o
he me hod. This wo k is, in ou opinion, a big s ep in
he igh di ec ion, bu add esses mainly co ec ness issues.
I does no desc ibe how o use he e icien co ec ness
checks in an op imiza ion loop, and does no allow he
sha ing o a decomposed ga e by di e en signal ne wo ks.
The
idea
o
combina ional logic decomposi ion wi h
esyn hesis has been p oposed in [8,7]. The app oach com-
bines oge he e icien algeb aic ac o iza ion echniques
used in mul i-le el combina ional logic syn hesis
( inding
candida es o decomposi ion), and speed-independence
p ese ing signal inse ion ( he la e idea o igina ed in
[
171
and was implemen ed e icien ly in [6]).
The main con ibu ion
o
his pape
is
a gene alisa ion
and ex ension o he abo e basic idea so as o co e bo h
combina ional and sequen ial decomposi ion. We ha e
0-8186-7922-0/97
$10.00
0
1997
IEEE
240
de eloped a body o heo y ha allows us o p une he
sea ch space when looking o solu ions. We con inue
o use classical logic syn hesis echniques a ailable o
combina ional mul i-le el logic in o de o iid good can-
dida e unc ions o he decomposi ion. In he case
o
combina ional decomposi ion he newly inse ed signal is
a lib a y ga e. The inse ion
o
a combina ional ga e is
based p ima ily on one o he wo ansi ions o he ga e's
ou pu (e.g., i s ising ansi ion). The o he ansi ion o
he combina ional ga e is ully de e mined by he inse ion
place o he i s ansi ion.
A sequen ial decomposi ion, based on a new memo y
elemen , can imp o e he p og ess o mapping by ende ing
he opposi e ansi ion a mo e e ec i e ole, since he se
and ese logic a e inse ed independen ly.
In
pa icula ,
wo
boolean unc ions can be decomposed a
he
same ime
wi h one new signal. Thus, in compa ison wi h
[4],
his
me hod:
e
a ge s he sea ch
o
he solu ion owa ds a gi en
e
allows logic sha ing based on mul iple acknowledg-
0
pe o ms global op imiza ion ia esyn hesis ( a he
Th oughou he pape we use he ollowing no a ion:
lib a y;
men s;
han sequen ial decomposi ion).
A
s ands o he o iginal S a e G aph,
A'
--
o a new
S a e G aph ob ained by signal inse ion.
a,
b,
c,
. . . (lowe case La in le e s) a e used o signal
names and, co esponding o hem, li e als
in
Boolean
unc ions.
2
-
always deno es a
new
signal, which is inse ed
in S a e G aph
A
o decompose a non-implemen able
unc ion.
B,
C,
F,
P,
Q,
R,
.
.
.
(uppe
case
La in le e s, excep
A)
s and o he names o Boolean unc ions.
2
Theo e ical backg ound
In his sec ion we in oduce heo e ical concep s equi ed
o ou decomposi ion me hod:
(1)
ci cui speci ica ion
and i s logic implemen abili y;
(2)
condi ions o speed-
independen decomposi ion o complex ga es; and
(3)
ans o ma ions
o
s a e g aphs
o
ensu e hose condi ions.
2.1
S a e G aphs and
Logic
Implemen abili y
A
S a e G aph (SG)
is a labeled di ec ed g aph whose
nodes
a c
called
s a es.
Each a c o an
SG
is labeled wi h
an
e en ,
ha is a ising (a+)
o
alling
(a-)
ansi ion
o a signal a in he speci ied ci cui . We also allow
no a ion
a*
i we
a e
no speci ic abou
he
di ec ion o
he signal ansi ion. Each s a e is labeled wi h
a
ec o
o
signal alues. An SG
is
consis en
i i s s a e labeling
:
S
--
(0,
is such ha : in e e y ansi ion sequence
om he ini ial s a e, ising and alling ansi ions al ema e
o each signal. Figu e 1,b shows he
SG
o he Signal
T ansi ion G aph in Figu e l,a, which
is
consis en ,
We
w i e
s
Z
(s
5
s')
i he e is an a c om s a e
s
( o s a e
s')
labeled wi h
a.
a+
Z-
a,d
-
inpu s
acdz
--l
o001-
Figu e
1:
An example o S a e T ansi ion G aph (a) and
S a e G aph (b) (benchma k
haza d.g)
The se o all signals whose ansi ions label
SG
a cs
a e pa i ioned in o a (possibly emp y) se o inpu s, which
come om he en i onmen , and a se o ou pu s
o
s a e
signals ha mus be implemen ed. In addi ion
o
consis-
ency, he ollowing wo p ope ies o a
SG
a e needed o
hei implemen abili y
in
a speed-independen logic ci cui .
The i s p ope y is
speedindependence.
I consis s o
h ee cons i uen s: de e minism, commu a i i y and ou pu -
pe sis ency.
A
SG
is called
de e minis ic
i o each s a e
s
and each label
a
he e can be a mos one s a e
s'
such
ha
s
---
s'.
A
SG
is called
commu a i e
i whene e
wo ansi ions can be execu ed om some s a e in any
o de , hen hei execu ion always leads o he same s a e,
ega dless o he o de . An e en
U*
is called pe sis en
in
s a e
s
i i is enabled a
s
and emains enabled in any
o he s a e eachable om
s
by i ing ano he e en
b*.
A
SG is called
ou pu -pe sis en
i i s ou pu signal e en s a e
pe sis en in all s a es. Any ans o ma ion (e.g., inse ion
o new signals o decomposi ion), i pe o med a he
SG
le el, may a ec all h ee p ope ies.
The second p ope y,
Comple e S a e Coding
(CSC),
becomes necessa y and su icien o he exis ence o
a
logic ci cui implemen a ion. A consis en
SG
sa is ies he
CSC
p ope y i o e e y pai o s a es
s,s'
such ha
(s)
=
(s'),
he se o ou pu e en s enabled in bo h s a es
is he same. (The
SG
in Figu e
1
,b is
ou pu -pe sis en
and
has
CSC.)
CSC
does no howe e es ic he ype o logic
unc ion implemen ing each signal.
I
equi es ha each
signal is cas in o a
single a omic
ga e. The complexi y
o such a ga e can howe e go beyond ha p o ided in a
conc e e lib a y o echnology.
2.2
Ga e-le el implemen abili y wi hou haza ds
Necessa y and su icien condi ions o
speed-
independen implemen a ion using unbounded anin
and
ga es (wi h unlimi ed inpu in e sions), bounded anin
o
ga es and
C
elemen s we e gi en in
[
1,9].
In
his wo k we
a e conside ing
a
simila basic implemen a ion a chi ec-
u e, called he
s anda d-C
a chi ec u e, which is desc ibed
in
Figu e
2.
The di e ence om p e ious wo k is ha
24
1
ins ead o unbounded anin ga es o he se and ese logic
o C-elemen s, we will allow only
implemen able
ga es,
ha is he ga es which exis in he chosen lib a y.
Figu e
2:
The s anda d-C a chi ec u e ex ended o com-
plex ga es
The concep s o exci a ion and quiescen egions a e
essen ial o ha .
A
se o s a es is called
an
exci a ion
egion
(ER) o e en
a*
(deno ed by
ERj(a*))
i i is a
maximal connec ed
se
o
s a es such ha
Vs
E
E Rj
(a*)
:
s
5.
Since any e en
a*
can ha e se e al sepa a ed
ERs,
an index
j
is
used o he dis inc ion be ween
di e en
connec ed occu ences
o
a*
in he
SG.
The
quiescen egion
(QR)
(deno ed by
QRj(a*))
o a
ansi ion
a*,
wi h exci a ion egion
ERj(a*),
is a
maximal
se o s a es
s
eachable om
ERj(a*)
such ha
a
is s able
in
s
and
s
is no eachable om any o he
ERk(a*)
such
ha
k
#
j
wi hou going h ough
ERj
(a*)
'.
Examples o
ER
and
QR
a e shown in Figu e 1,b.
Le
Cj(a*)
deno e one
o
he i s -le el
AND-OR
ga es in he s anda d-C a chi ec u e.
Cj(a*)
is a
co -
ec mono onous poly- e m co e?
o he exci a ion egion
ERj(a*)
i he ollowing h ee condi ions a e sa is ied:
1.
Co e condi ion:
Cj(a*)
co e s all s a es o
ERj(a*)
(i.e.,
Cj(a*)
e alua es o
1
in all s a es o
ERj(a*)).
2,
One-ho condi ion:
Cj(a*)
does no co e any s a e
ou side
ERj(a*)
U
QRj(u*).
3.
Mono onici y condi ion:
Cj(a*)
changes a mos once
The condi ions abo e a e called
he
Mono onous Co e
condi ions
o
sho ly he
MC-condi ions.
Since unde hese
condi ions
he
ou pu s
o
he i s -le el ga es a e one-ho
along any s a e sequence wi hin
QRj(a*).
'No e ha con a y o
[9,
11
in
his pape we use only he so-called
es ic ed quiescen egions which do no include s a es eachable di ec ly
om wo di e en exci a ion egions o he same signal.
*He e o simplici y we conside he de ini ion
o
Mono onous Co e
wi hou he ex ension by he so-called
backwa d
quiescen
egions
and
wi hou conside ing co e ing
o
mul iple egions by he same co e .
Howe e all he esul s can be easily gene alized o his ex ension as
well.
encoded
any alid Boolean decomposi ion
o
he second-
le el
o
ga es is speed-independen .
The s anda d-C a chi ec u e pe mi s a
combina ional
implemen a ion o a signal. I he se and ese ne wo ks
a e he complemen s o each o he , hen a C-elemen wi h
iden ical inpu s can be simpli ied o a wi e (see Figu e
2,b,c).
In
such case we say ha he signal has a
comple e
co e ,
2.3
P ope y-p ese ing e en inse ion
Ou
decomposi ion me hod is essen ially beha iou al --
he ex ac ion o new signals a he s uc u al (logic) le el
mus be ma ched
by
an inse ion o hei ansi ions a
he
beha iou al
(SG)
le el. E en inse ion is an ope a ion on
a
SG
which selec s a subse
o
s a es, spli s each o hem
in o wo s a es and c ea es, on he basis o hese new s a es,
an exci a ion egion o a new e en . Figu e
3
shows he
chosen inse ion scheme, analogous o ha used by mos
au ho s in he a ea [17].
Figu e
3:
E en inse ion scheme: (a) be o e inse ion, (b)
a e inse ion
S a e signal inse ion mus p ese e he
speed-
independence
o he o iginal speci ica ion. An inse ed
signal is deno ed by
x
in his pape . The co esponding
o
i
e en s a e deno ed
x*,
x+,
x-,
o ,
i no con usion
occu s, simply by
2.
Le
A
be a
SG
and
A'
is a s a e g aph
ob ained by inse ion
o
e en
x.
We say ha an inse ion
s a e se
ER(x),
in a SG
A
is a
speed-independence p e-
se ing se (SIP-se )
i : (1) o each e en
a
in
A,
i
a
is
pe sis en
in
A,
hen i emains pe sis en in
A',
and
(2)
A'
is de e minis ic and commu a i e. The o mal condi ions
o he se o s a es
o be a SIP-se can be gi en in e ms
o in e sec ions o
wi h he so-called s a e diamonds o
SG
[6].
These condi ions a e illus a ed by Figu e
4,
whe e
all possible cases o he illegal in e sec ions o
wi h s a e
diamonds
a e
shown.
I was shown in
[6]
ha
he
inse ion o a signal by
means
o
a SIP-se is a necessa y and su icien condi ion
o p ese e he speed-independence o a co esponding
SG.
This equi emen is he mos gene al one in he syn hesis
o
speed-independen ci cui s and i does no es ic he
solu ion space unless we go beyond he speed-independen
class.
An
e icien me hod o inding SIP-se s, which
is based on egions, has been p oposed in
[6].
The
i s
me hod
o
inding SIP-se s based on educ ion o
sa is iabili y p oblem was p oposed
in
[
171.
Assume ha he se o s a es
S
in a
SG
is
pa i ioned
in o wo subse s which a e o be encoded by means
o
an addi ional signal. This new signal can be added ei he
in o de o sa is y he
CSC
condi ion,
o
o b eak up a
complex ga e in o a se o smalle ga es.
In
he la e case,
a new signal ep esen s he ou pu o he in e media e ga e
added o he ci cui . Le
and
7
=
S
-
deno e he blocks
o such a pa i ion. Fo implemen ing such a pa i ion we
242
Figu e
4:
Possible iola ions o SIP condi ions
need o inse ansi ions o he new signals in he
bo de
s a es
be ween
T
and
V.
In his pape we shall conside he so-called
inpu
bo de
o a pa i ion block
T,
deno ed by
IB(T),
which is
in o mally a subse o s a es o
T
by which
T
is en e ed. We
call
IB( )
well o med
i he e a e no a cs leading om
s a es in
T
-
IB(T)
o s a es in IB(T). I a new signal is
inse ed using an inpu bo de , which is no well- o med,
hen he consis ency p ope y
is
iola ed. The e o e,
i
an inpu bo de is no well- o med, i s well- o med speed-
independen p ese ing closu e is cons uc ed, as desc ibed
by Algo i hm
4.1
in Sec ion
4.
The inse ion o a new signal can be o malized wi h
he no ion o
I-pa i ion
([17]
used a simila de mi ion).
Gi en a
SG,
A,
wi h a se o s a es
S,
an
I-pa i ion is a
pa i ion o S in o ou blocks:
{S+,
S',
S-,
So}.
So(S')
de ines he s a es in which
z
will ha e he s able alue
0
(1).
S+(S-)
de ines
ER(z+)
(ER(%-))
in he new
SG
A'.
The e o e, abusing no a ion we will o en e e
o
S+(S-)
as o
ER(s+)
(ER(z-))
when alking abou
s a es o he
o iginal
SG
A
o , i con usion may a ise,
we w i e
ERA(z+) (ERA(z-)).
I he inse ion o
z
p ese es consis ency and pe sis ency, hen he only an-
si ions c ossing bounda ies o he blocks a e he ollowing:
so
--+
s+
-+
s'
s-
so.
3
Decomposi ion echniques
We assume he e amilia i y wi h mul i-le el logic syn-
hesis (see
[3]
o mo e de ails).
As desc ibed in he p e ious sec ion, any de e minis ic,
commu a i e, ou pu -pe sis en
SG
sa is ying he
CSC
and
he Mono onous Co e condi ions can be implemen ed
using he s anda d-C a chi ec u e. We assume ha C-
elemen s a e p esen in he lib a y
'.
OR-ga es combining
co e unc ions
C(
a*)
can be decomposed by any s anda d
echnique since hei inpu s a e one-ho encoded. Hence he
bo leneck o echnology mapping is he implemen a ion
o co e unc ions
C(a*)
using ga es a ailable in he
lib a y.
As adi ionally done in mul i-le el combina ional syn-
hesis, we ha e chosen algeb aic di ision as he main
ope a ion o logic decomposi ion. Thus, o each co e
unc ion
C(
a*)
we seek algeb aic di iso s, aiming a de-
composi ions o he ollowing
y
C(a*)
=
F
*
G
+
R
whe e
G
is he quo ien
C(a*)F!
AND-decomposi ion
31n ac
ou
echnique
wo ks
and is implemen ed
also
o
RS-
and
Dla ches. Howe e , his gene aliza ion
o
he me hod is omi ed due
o
he lack
o
space.
i
complex ga e!
I
Figu e
5:
Co e unc ion
C(a*)
(a) and i s combina ional
(b)
and sequen ial
(c)
decomposi ions
is done when
R
=
0,
whe eas OR decomposi ion occu s
when G
=
1.
Howe e , con a y o he classical combina ional de-
composi ion
we
use di iso
F
no o immedia e ex ac ion,
bu as a i s app oxima ion o he unc ion o be ex ac ed.
Mo e speci ically, unc ion
F
de ies one (sequen ial de-
composi ion) o wo (combina ional decomposi ion) blocks
o a pa i ion o he s a e space, which is la e
used
o new
signal inse ion (see Sec ions
4
and 5 o mo e de ails).
Two ways o decomposing
C(a*)
a e possible:
0
combina ional decomposi ion: a di iso
F
is imple-
men ed by a combina ional ga e,
z,
as shown in Figu e
5,b and
0
sequen ial decomposi ion: an addi ional la ch (e.g.,
C-elemen ) implemen s signal
z;
di iso
F
is used
as one o he inpu unc ions o he la ch as shown
in Figu e 5,c. Ano he unc ion (deno ed by
P
in
he
igu e)
mus be ex ac ed om some o he co e
unc ion. Func ions
F
and
P
o m he se and ese
unc ions o he new sequen ial signal
z.
In ou decomposi ion echnique ansi ions o
z
a e
acknowledged by
se e al
co e unc ions. This is mo e
gene al and powe ul han
[lS,
41
whe e ansi ions o
s
mus
be
acknowledged locally, only by he co e unc ion
C(a*)
om which
z
is ex ac ed. Mul iple acknowledg-
men o e s
wo
ad an ages:
(1)
he same signal
z
can be
sha ed by se e al co e unc ions ( his co esponds o he
ex ac ion
o
common sub-di ide s in classical mul i-le el
decomposi ion) and
(2)
co ec speed-independen decom-
posi ion can be ound e en
i
i does no exis o solu ions
wi h single acknowledgmen s
(see
he expe imen al e-
sul s). No e ha we do no speci ically sea ch o mul iple
acknowledgmen s. They appea au oma ically due o he
signal inse ion echnique based on SIP-se s. Hence ou
solu ion is co ec by cons uc ion and con a y o
[2]
ne e
equi es i e a ions wi h e i ica ion p ocedu es.
To
ind
good
di iso s
F
o
C(a*)
he
ollowing unc-
ions a e conside ed:
0
Ke nels and co-ke nels o
C(a*).
243
0
I
C(a*)
is a poly- e m co e , any subse o e ms o
he sum-o -p oduc exp ession (OR-decomposi ion).
0
I
C(a*)
is one cube, any subse o li e als o he cube
(AND-decomposi ion).
0
Recu si e decomposi ion o he p e ious candida es,
e.g. sub-kemels and AND/OR-decomposi ion o ke nels.
This gene a ion o di iso s is heu is ically p uned
o
a oid an explosion
o
candida es o unc ions wi h many
e ms
o cubes wi h many li e als. Expe imen al esul s
(Sec ion
6)
ha e shown his ype o decomposi ion o be
e y e ec i e. In pa icula , only hose decomposi ions a e
conside ed ha :
(1)
p ese e speed-independence and
(2)
gua an ee p og ess in mapping he ci cui o he gi en
lib a y.
The i s condi ion is sa is ied by inding an I-pa i ion
o signal
IC.
Many candida es o decomposi ion
a e
il e ed ou a his s ep, since o many di iso s he e a e
no alid I-pa i ions.
To cla i y he second condi ion assume ha unc ion
F
is ex ac ed om a co e unc ion
C(
a*)
o combina ional
decomposi ion (see Figu e 5,b). I he e is a alid I-pa i ion
o a new signal
2,
hen he e is a speed-independen
implemen a ion o he ci cui wi h signal
IC.
Howe e ,
in gene al, he e is no gua an ee ha unc ion
C(a*)
is
simpli ied in he new ci cui . The subs i u ion
o
5
o
F
in
C(a*)
does no always p ese e
s
ed-independence
and hence new an-in signals o
CG)
can appea in
he implemen a ion. Thus, he p og ess condi ion checks
whe he a subs i u ion o
IC
ins ead o
F
in
C(
a*)
is alid.
Since mul iple acknowledgmen o
5
can appea , he
equi emen o “good decomposi ion” is ollowing: he
complexi y o all (o he han
C(a*))
unc ions in
5’s
an-ou has o emain he same
o
o inc ease e y mode -
a ely. In Sec ion
4.3
we p esen a compu a ionally e icien
me hod o he es ima ion o e ec i e decomposi ions.
The o e all algo i hm o logic decomposi ion is
ske ched below. The nex sec ions desc ibe each s ep
in mo e de ail.
Algo i hm
3.1
(Speed-independen decomposi ion)
while ci cui is no mapped o he libmy
do
Calcula e mono onous co e s o all e en s;
Le
a*
be
he e en
wi h
he
mos complex co e ;
Le
D,
be a se o di iso s o
C(a*);
/*
Kemels, co-ke nels,
AND/OR
decomposi ion
*/
Le
&be
a
se o di iso s o he mos complex
co e unc ions o he han
C(a*);
o each
F
E
D,
do
Decomposi ion(F,
F)
;
/*
Check
combina ional
decomposi ion
o
F
*/
o each
P
E
&do
Decomposi ion(F,
P)
/*
Check sequen ial decomposi ion o he pai
{
F,
P}
*/
end o
end o
i
All
decomposi ions
ail
hen
else
e u n;
/*
Co e
C(a*)
canno be decomposed
*/
Choose he bes decomposi ion
({F,
F}
o
{F,
P});
Inse
a
new
signal
/*
by
an
I-pa i ion de ined
by
he bes decomposi ion
*/
end
i
end while
Decomposi ion(F,
P);
Find I-pa i ion o he pai
{
F,
P};
i no exis s hen e u n ailu e;
E alua e p og ess o decomposi ion o
C(a*);
/*(p oposi ion
4.1)
*/
i no p og ess hen e u n ailu e;
Es ima e p og ess o all o he co e s;
/*
(p ope y
4.5)
*/
i implemen abili y is dis u bed hen e u n ailu e
No e ha a e each cycle, when a success ul decom-
posi ion
is
ound, he implemen a ion o
e e y
signal
in
he
ci cui is ecompu ed o he bes candida e. Since a
he ecompu a ion s ep he new don’
ca e
se s
a e
used
o
all
signals, his p ac ically implemen s sequen ial de-
composi ion and
boolean
di ision (i.e., i is a beyond he
capabili ies o algeb aic ac o iza ion).
a
a
z
z
Figu e
6:
Ci cui s o a
haza d.g
example be o e (a) and
a e (b) decomposi ion
Example
haza dg.
This example ( om he se o
asynch onous benchma ks) is used
o
illus a ing ou al-
go i hm.
I s
Signal T ansi ion G aph and
SG
a e shown in
Figu e l,a and b. Signals
a
and
d
a e inpu s, signals
c
and
z
--
ou pu s.
A
speed-independen implemen a ion o he
ou pu signals
c
and z is p esen ed in Figu e 6,a. Ou a ge
is
he
decomposi ion o unc ion
S,
in o wo-inpu ga es,
because i is a s anda d wo s
case
agains which he pe -
o mance o a decomposi ion algo i hm can be measu ed.
Func ion
S,
consis s o a single 3-li e al cube
iidc.
I can
be
decomposed in h ee ways: by ex ac ing unc ions
iid,
Ec
and
dc.
Example
2.
Fo he co e
C(y*)
=
ab+ac+de
he ol-
lowing di iso s a e gene a ed ( i ial 1-li e al di iso s a e
no conside ed): he ke nel
b
+
c,
he OR-decomposi ions
ab,
ac, de , ab
+
ac, ab
+
de
and
ac
+
de
and he
AND-decomposi ions
de,
d
and
e .
4
Combina ional d~co~~osi ion
4.1
S a e
pa i ioning
In
his sec ion we apply he heo y o SIP-inse ion,
e iewed in Sec ion
2.3,
o a di iso
F
o a gi en co e
C(a*).
244

De ini ion 4.1 (T ansi ion se s)
Le
A
=<
V,
E
>
be a
SG
wi h a se
o
s a es
V
and a se
o
e en s
E.
Le
S
C
V
be a subse
o
s a es and e
E
E
be an e en . The ollowing
se s
o
s a es a e de ined o
S
and e (see Figu e
7):
be o e(e,
S)
=
{
s
:
s
#
S
A
3s'(
s
5
s'
A
s'
E
S)}
en y(e,
S)
=
{s
:
s
E
s
A
W(s'
-5
s
A
SI
#
s)}
Zea e(e,
S)
=
{s
:
s
E
S
A
W(s
-5
s'
A
s'
#
s)}
a e (e,
S)
=
{s
:
s
s
A
3s'(s'
s
A
s'
E
s)}
ea e(e,S)
a e (e,S)
Figu e
7:
Illus a ion o ansi ion se s
P ed(S)
and
Succ(S)
gi e he se s o s a es ou side
S
eachable in one s ep in backwa d
o
o wa d di ec ion,
espec i ely. Inpu ,
IB(S),
and exi ,
EB(S),
bo de s o
S
gi e he se s o s a es inside
S
om which he s a es
no included in
S
a e eachable in one s ep in backwa d
o
o wa d di ec ion, espec i ely. Ou echnique ope a es
wi h inpu bo de s. Se
IB(F)
de ined by De ini ion
4.1
can
be
compu ed
as
ollows
(IB(F)
is
compu ed simila ly):
IB(F)
=
U
en y(e,
{s
:
~(s)
=
01)
=
=
{S
:
F(s)
=
0
A
391
:
SI
+
s
A
F(s~)
=
1).
eEE
An e en
b*
is said o
be
a
igge e en
o e en
a*
i
en y(b*,ER(a*))
#
8.
In o mally, by i ing igge
e en s i
is
possible o en e he exci a ion egion o
a*.
We also say ha signal
b
is a
igge signal
o signal
a
and o e en
a*.
All igge signals o signal
a
mus be
included in he suppo o he logic unc ion implemen ing
a
and hence each igge signal will be in he an-in o
a.
T igge s can be easily de i ed by obse ing
ERs
o
a
in
he
SG.
We can also show ano he p ope y o igge signals,
ha will
be
used
o
es ima e he complexi y o he logic
a e decomposi ion.
P ope y 4.1
E en
x*
is a igge o e en
b*
in
SG
A'
i Zea e(b*,
ER(%*))
#
8.
The p oo ollows di ec ly om he ules o e en
inse ion (c . Figu e 3), because i
Zea e(b*,
ER(x*))
#
8
hen he i ing o
b*
will be delayed un il
x*
has i ed.
Any boolean unc ion
F
de ines a bipa i ion
{
S
F,
SF}
o he se o s a es
o
a SG:
SF
=
{s
:
F(s)
=
1)
and
S"
=
{s
:
F(s)
=
0).
As discussed
in
Sec ion
2.3,
o
inse mg a new signal
x
i is necessa y o ind an I-pa i ion,
{S+,S1,S-,So},
based on bipa i ion
{SF,SF}.
The
ou blocks o I-pa i ion a e cons uc ed as ollows:
S-
=
ER(x-)
g
SF
and
S+
=
ER(s+)
g
S",
co esponding o he exci a ion egions o
5
in he new
SG,
a e ob ained by he well- o med closu e o he
inpu bo de se s,
IB(F)
C
SB
and
IB(F)
C
SF,
espec i ely
[6].
-
-
S'
=
SF
-
S+
and
So
=
SF
-
S-.
The ollowing p ope y s a es ha , i he e is a well- o med
SIP closu e o he
IB,
hen he e
is
a minimal closu e ha
has s ic ly less s a es han any o he .
P ope y 4.2
[8]
Le
{b,6}
be a bipa i ion
o
he
SG
s a es. Le
I1
C
b
and le
I2
be a minimal well- o med
SIP
se such ha
I1
C
I2
C
b.
Then
I2
ei he does no exis
o
unique.
In
pa icula ( he p ac ically use ul case), his p ope y
holds o
I1
=
IB(b).
The p oo
(see
[SI)
p o ides
a cons uc i e p ocedu e o selec ing he minimal well-
o med
SIP
closu e o he inpu bo de wi hou back acking
and hus is compu a ionally e icien . This p ocedu e can be
summa ized
as
ollows. (We u he illus a e i by de i ing
ER(x-)
o
F
=
dc
in
S,
o he
haza d.g
example, as
shown in Figu e
8).
8)
Figu e
8:
De i a ion o
ER(x-)
o a decomposi ion
dc
o a
haza d.g
example
Algo i hm 4.1 Gene a ion o
ERs
o a new signal,
by example o
S-
=
ER($-)
1.
Le
ER(z-)
=
IB(F)
245
2.
Find well- o med closu e
by
ecu si e applica ion
o
he ollowing ule:
i s
E
P ed(ER(x-))
n
SF,
hen
le
ER(x-)
=
ER(x-)
U
s.
3.
P ese e
(i
equi ed) he inpu -ou pu in e ace by
checking ha no inpu signals can be delayed by
x.
Fo his do he ollowing:
o any inpu si nal
b:
i
s
E
a e (b*,ER(x-)),
hen le
ER(x-7
=
ERi-)
U
s.
4.
Fo ce
SIP
p ope ies (make any in e sec ion o s a e
diamonds wi h
ER(x-)
legal
by
inse ing in
ER(x-)
he co esponding s a es o he diamond). Go o S ep
9
d
Calcula ion
o
ER(x-)
s ops ei he
i
a some s ep
in e sec s wi h
SF
( hen he e is no legal
)
o a ixed poin is eached. Calcula ion o
is
done simila ly based
on
IB(F).
Example
ha2a d.g
con inued.
In he example
(see Figu e 8,a)
ER(x-)
=
(1011)
(s ep 1). I is
well- o med (s ep
2).
A s ep
3
we will ind ha
s a e
0011
E
a e (a-,ER(x-))
and s a e 1001
E
).
The e o e,
{0011,1001}
a e in-
Figu e 8,b). S a e diamond
illegally in e sec s
ER(x-)
(s ep
4).
To le alize his, he in e sec ion s a e
OOO1
is
included in
ER x-)
as shown in Figu e8,c.
Figu e
9
shows he esul s o
ER(x*)
gene a ion o
he decomposi ion o
S,
=
Ecd
wi h di iso s
Ed,
Ec
and
dc,
espec i ely. The choice
F
=
Ed
is
no alid (see Fig-
u e 9,a), because
F
in e sec s illegally wi h s a e diamond
{
101 1,001 1,1001,0001). This illegal in e sec ion canno
be co ec ed by expanding
IB(F)
wi hou hi ing s a es
whe e
F
=
0.
The di iso s
Ec
and
dc
a e alid and he
co esponding
ERs
o signal
x
a e shown in Figu e 9,b,c.
acdz
Figu e
9:
Th ee a emp s o decompose
S,
=
Zcd
in
huzu dg
example
4.2
P og ess
Analysis
I
ER(x+)
and
ER(x-)
a e de i ed, hen he e is a
speed-independen implemen a ion o he SG wi h a new
signal
x.
Howe e , o ensu e p og ess in he echnology
mapping o he a ge co e unc ion
C(m)
=
P
*
G
+
R,
we would like o ha e he ollowing implemen a ion in he
new ci cui :
C(a*)
=
x
*
G
+
R
( unc ion
F
is subs i u ed
in his exp ession by one li e al
z)~.
This is no always
possible, since o p ese e speed-independence,
C(
a*)
may
equi e mo e an-in signals. We will o mula e p og ess
condi ions which will de iie when he implemen a ion
abo e is alid.
S a e images.
The p og ess condi ions
a e
easily o mu-
la ed in e ms o he new
SG
A'
.
Howe e , cons uc ing
he new
SG
is compu a ionally ha d and hence i is be e
o use he o iginal SG
A
(c . he app oach in [4]). Fo
his we need o compa e he s a es o
A
and hei images
in
A'.
The inse ion scheme (Figu e
3)
de e mines a bina y
ela ion (we call i an image ela ion) be ween he s a es
o
A
and he s a es o
A'.
A s a e
s'
om
SG
A'
is said
o
be an image o a s a e
s
om
A
i alues o all signals,
excep
x,
a e he same in
s
and in
s'.
Then, s a e
s
is called
he in e se image o
s'.
The in e se image o any s a e
om
A'
is unique. The opposi e is no ue. Each s a e
s
E
ER(x*)
om
SG
A
has wo images
s',
s"
in
A'
such
ha
s'
2
s".
All o he s a es in
A
ha e one image. The
image ela ion is expanded o he se s
o
s a es. I
S
is
a se o s a es in
A',
hen i s in e se image is deno ed by
S-'.
To a oid con usion, we will add subsc ip
A
o
A'
o
add ess
he
objec s in SGs
A
and
A'
i necessa y.
In e se images
o
exci a ion and quiescen egions.
The alidi y o subs i u ing a new signal
z
in a co e
unc ion
C(a*)
is
checked by conside ing he in e se
images o
ER(u*)A
and
QR(u*)A~.
By cons uc ion, only
s a es om
ER(u*)A
ha e images in which
a*
is enabled,
hence
ER(u*)A
is he in e se image o
ER(u*)A~.
Fo
quiescen egions he image ela ion is mo e complica ed.
Conside , o example, signal ansi ion
a+.
Fo e e y s a e
s
E
QR(u+)A
he e is an image in which signal
a
is equal
o 1, and he e o e
QR(u+)A
C
QR(a+), .
Howe e ,
QR(a+)p!
can include addi ional s a es because some
o iginal signal ansi ions a e delayed by
x.
Figu e
10:
In e se image o quiescen egions
This case is illus a ed in Figu e 10. In SG
A
s a e
s
E
ER(a-).
Howe e , in one o i s images,
s',
signal
a
is
equal o
1
and
is
s able, and he e o e
s'
E
QR(u+)A~.
Hence, s a e
s
is in he in e se image o
QR(u+)AI.
The
ollowing p ocedu e compu es he in e se image o a
quiescen egion (by example o
QR(ai+)A!).
4Algo i hm
4.1
does no modi y he bo de s
o
SF
o
SB,
so
he
combina ional solu ion
z
=
F
is always alid. Howe e he echnique
desc ibed
in
his sec ion may also ind a
sequen ial decomposi ion
wi h
his combina ional
"seed".
246
Algo i hm
4.2
Compu ing in e se image
o
quiescen egions
QR(
ai+);!
=
QR(
ai
+)A;
o
each
a,
-
ha
succeeds
a;+
do
i s
E
ER(%*)
n
ER(a,-)
A
a e (a,-,
s)
n
ER(%*)
=
0
hen
QR(ai+)A
=
QR(ai+),!
U
s
end o
Be o e o mula ing p og ess condi ions we p esen a
use ul p ope y ha cap u es condi ions o signal
x
o
ha e a cons an alue inside he exci a ion egion o he
o iginal signal
a
in he
new
SG e en i he exci a ion
egion o
x*
in he
o iginal
SG
con ains s a es om he
ER(a*)
(2,
as be o e, deno es he signal which is inse ed
o decomposi ion).
P ope y 4.3
[8]
Le
SG
A'
be ob ained om
SG
A
by
inse ion
o
signal
x.
Le
a*
be an e en . Le
ER(x+)
be
a welll o med
SIP
closu e
o
he inpu bo de o a block
o
a s a e pa i ion o
SG
A,
ob ained wi h Algo i hm
4.1,
such ha
ER(x+)
l
ER(a*)
#
8.
I he ollowing
wo
condi ions a e sa is ied o
SG
A
hen
x
is equal o
1
in any s a e
o
ER(u*)A .
A symme ical p ope y holds o
ER(x-).
The nex
p oposi ion s a es he p og ess condi ion by p esen ing
condi ions o p ese ing mono onous co e condi ions o
subs i u ing unc ion
F
wi h one li e al
x
in he co e
unc ion
C(a*).
P oposi ion4.1
[7]
Le
CA(U*)
=
F
*
G
+
R
be a
mono onous co e
o
ER(a*)
in
SG
A.
Le
ER(x+)
and
ER(x-)
be he S+and S-se s o inse ing a signal
x
ob-
ained by Algo i hm
4.1.
The unc ion
CAI
(U*)
=
x*G+ R
sa is ies he h ee condi ions o he mono onous co e in
he new
SG
A',
i :
..
1.
Co e condi ion:
a e (a*,
(ER(a*)nF*G* i-))n
ER(x+)
=
8
2.
One-ho condi ion:
Vs
:
s
$2
ER(a*)
U
QR(a*),!
+
s
$2
ER(x-)
n
G
3.
Mono onici y condi ions:
(a)
Vs
:
s
E
(QR(a*)
n
F
*
G
*
x)
+
s
$2
ER(x+),
and
(b)
VS
:
s
E
'QR(a*),!
n
ER(x1)
n
G
+
P e;(s) E
G+R
The p oo is gi en in
[8].
The condi ions in he abo e
p oposi ion can be in o mally explained as ollows.
Condi ion
1
ensu es he co e condi ion o
CAI
(U*)
in
he new
SG
A',
by de ailing P ope y 4.3. Se
ER(a*)
n
F
*
G
*
con ains hose s a es o
ER(a*)
in
SG
A
ha a e co e ed by
F
*
G,
bu no by
R.
The e o e, o
sa is y he co e condi ion in
SG
A',
he image o his
se in
A'
mus be co e ed by he unc ion
x
*
G.
I
a e (a*,
(ER(a*)
n
F
*
G
*
x))
n
ER(x+)
#
0,
hen
he e
is
a ansi ion
SI
2
s2
in e nal
o
ER(x+)
such
ha
F(sl)
=
G(sl)
=
1
and
R(sl)
=
0.
Hence, s a e
~
247
SI
has wo images
si
and
sy
in
A'
such ha
si
2
sy,
which implies ha signal
x
has alue
0
in
si
and alue
1
in
sy.
The e o e, s a e
si
E
ERA~(x+)
is no co e ed by
CAI(U*)
=
x
*
G
+
R
since bo h
2
*
G
and
R
ha e alue
0
in
si.
The co e condi ion is iola ed.
Condi ion
2
ensu es he one-ho condi ion o
CA'
(U*)
in he new SG
A'.
Le s be ou side
ER(a*)
U
QR-'(a*).
I
s
E
ER(x-)
n
G
in
SG
A,
hen in he new SG
A',
unc ion
x
*
G
e alua es o
1
in he i s image
s'
o
s
(s'
"J
s").
Hence, o A', unc ion
x
*
G
is e alua es o
1
ou side
ERA,(U*)UQRA~(U*),
which iola es he one-ho
condi ion o he co e unc ion
CA'
(U*)
=
x
*
G
+
R.
Condi ion 3 ensu es he mono onici y condi ion o
CAI
(U*)
in SG
A'.
Condi ion 3(a) gua an ees ha
CAI
(U*)
canno make a non-mono onous ansi ion o he
y
e
"1-
0-1"
along any pa h inside
ERA~(u*)
U
QRA'(a*y
Se
QR(a*)
n
F
*
G
*
con ains he s a es o
QR(a*)
ha
a e co e ed by
F
*
G,
bu no by
R,
in SG
A.
Le some
s a e
s
om his se belong o
ER(x+).
Then he e a e
wo images o s a e
s
in SG,
A':
s'
and
s"
such ha
s'
2
s".
Func ion
x
*
G
e alua es o
0
in
s'
and o
1
in
SI'.
Nei he image is co e ed by
R.
Mo eo e since s a es
o
ER
a*)
a e co e ed by
CA,(,*)
he co e unc ion
CA'
(a*
pe o ms a non-mono onic ansi ion
1-0-1
along
a pa h wi hin
ERAI(u*)
U
QRA,(u*)
( his pa h s a s in
ER(a*)
and con ains s a es
s'
and
s").
Condi ion 3(b) ensu es ha
CA'
(U*)
canno make a non-
mono onous ansi ion o he o he ype
"0-1-0
along any
pa h inside
ERA,
(a*)
U
QRA,(u*).
Assume ha he e is a
leas one s a e,
s,
such ha
s
E
QR(u*)~!
n
ER(x-)
l
G
and le i s p edecesso ,
SI,
be co e ed nei he by
G
no by
R.
Then unc ion
CA,(,*)
has alue
0
in he image,
si,
o
s1
(i
s1
has wo images, hen
CAI
(U*)
has alue
0
in bo h).
S a e
s
has wo images in
A'
(s'
"s
s").
Func ion
x
*
G
e alua es o
1
in he i s one,
s',
and o
0
in he second one,
s".
Hence, unc ion
CAI
(a*)
pe o ms a non-mono onous
0-1-0
ansi ion along he pa h
si
-+
s'
-+
s"
in
A'.
Example
haza d.g
con inued.
All he condi ions o
P oposi ion
4.1
a e sa is ied o
F
=
Ec
and
F
=
de
and
o bo h o hem
S,
can be sa ely decomposed in o wo
AND ga es.
4.3
Cos es ima ion
The p og ess condi ion (i sa is ied) gua an ees ha he
implemen a ion o a a ge co e unc ion
C(a*)
will be
simpli ied as a esul o a decomposi ion. Howe e , o
accep a decomposi ion we need o check ha i will no
inc ease he complexi y
o
logic o
o he
e en s. We use a
conse a i e es ima e o logic complexi y, in which igge
signals play a key ole, in o de o selec candida es o
decomposi ion.
All e en s (besides he a ge e en
a*)
can be di ided
e
E en s
x*
o
signal
x
in
3
g oups:
I can be shown, by analyzing he MC condi ions ha
x
=
F
is a co ec comple e co e o a signal
x.
The p econdi ions o hese e en s a e no modi ied
by he inse ion o
x,
and hence we
can
(in
he
e
E en s o which
x*
is no
a
igge
wo s case) use he same implemen a ion
as
be o e he
decomposi ion. I is possible, hough, ha
x
can
be
used o u he simpli y he implemen a ion o hose
signals as well, since he don' ca e se is inc eased.
e
E en s o which
x*
is a igge ,
deno ed by
TT(x).
Fo es ima ing complexi y o such e en s he ollow-
ing p ocedu e is used.
Algo i hm 4.3 Es ima ing complexi y o signals
o which
x
is a igge
1.
o
each
b*
E
TT(I)
do
2.
i
I*
eplaces
igge
e en
d*
in
ER(b*)
hen
I*
p ope y 4.4
*/
3.
i
I
subs i u es
d
in
a co e unc ion
C(b*)
hen
I*
p oposi ion
4.2
*I
4.
The complexi y
o
C(
b*)
is
no
inc eased
/*
p ope y
4.5
*I
6.
The complexi y
o
C(b*)
is
inc eased
mode a ely
8.
Decomposi ion
ails
5.
else
i
I
can
be
added as one addi ional li e al
o
C(b*)
hen
7.
else
9.
end
i
10.
end
i
1 1.
end
o
Fu he we conside he main s eps o Algo i hm 4.3.
Replacemen o o he igge e en s by
x
(line
2
o Al-
go i hm 4.3).
P ope y 4.
l
helps o ind he se o e en s
T (z)
o which signal
x
becomes a igge . Condi ions
o eplacing a igge e en by a new signal ansi ion
x*
a e s a ed by he ollowing p ope y.
P ope y4.4
[8]
An e en
x*
eplaces
d*
as
a
igge
e en o
b*
in
SG
A'
i
in
SG
A
he ollowing condi ions
a e sa isj?ed:
(1)
en y(d*,ER(b*))
c
ER(x*)
(2)
be o e(d*,ER(b*))n
ER
x*)
=
0
(3)
a e (&, en y(d*,
ER@*
0
))
n
ER(x*)
=
0
Example
ha2a d.g
con inued.
Le us conside a com-
bina ional decomposi ion o
S,
using unc ion
F
=
dc.
ER(x+)
sa is ies all he condi ions o P ope y
4.4
and
hence
x+
becomes a new igge e en
o
+
ins ead o
d+.
On he o he hand, o
ER(x-)
o bo h e en s
a-
and
d-
condi ion 2 o P ope y
4.4
is iola ed. The e o e,
e en s
a-
and
d-
a e concu en wi h
5-
and none o
hem is eplaced by he new igge e en
x-.
A e in-
se ing signal
x
e en
-
will ha e
h ee
igge e en s
x-,
a-,
d-.
Fo he decomposi ion based on unc ion
F
=
Ec,
he new signal
x
eplaces old igge signals o
Valida ing subs i u ion
o
signal
x
in o a co e unc ion
o he han
C(a*)
(line
3
o
Algo i hm 4.3).
I a ig-
ge e en
x*
eplaces ano he igge e en
d*
o some
ER(b*),
hen he nex s ep is o check ha signal
d
can be
eplaced by signal
x
in he logic implemen a ion o C(b*).
Assume ha
CA@*)
=
d
*
M
+
N.
We wan o check
alidi y
o
subs i u ion
CAI
(b*)
=
x
*
M
+
N.
Condi ions
o alidi y o such subs i u ion a e almos iden ical
o
hose o P oposi ion 4.1.
bo h Z+ and
-
.
P oposi ion
4.2
Le
C(
b*)
=
d
*
M
+
N
be a mono onous
co e o
ER(
b*)
in
SG
A.
Le
{
S+
=
ER(
x+)
,
S'
,
S-
=
ER(x-),
So}
be he I-pa i ion o inse ing signal
x.
The
implemen a ion CA,
(b*)
=
x
*
M
+
N
sa is ies he h ee
condi ions o mono onous co e
in
he new
SG
A'
i :
I.
Co e condi ion:
(a e (
a*,
(ER(a*)
nd*
M*N))
n
2.
One-ho condi ion:
Vs
:
s
$
ER(a*)
U
QR(a*)A!
=$
s
#
(ER(z-)
U
S')
n
M
3. Mono onici y condi ions:
(a)
Vs
:
s
E
(QR(a*)
n
d
*
M
*
P ed(s)
E
M
+
N
Le us cla i y he di e ence be ween P oposi ions 4.1
and 4.2.
In
P oposi ion 4.1 signal
x
is he ou pu o
he ga e implemen ing unc ion
F
and is subs i u ed in o
C(a*)
=
F
*
G
+
R
ins ead o
F.
In P oposi ion 4.2
x
subs i u es signal
d,
which is implemen ed by a ga e di e -
en om he ga e implemen ing
x.
The e o e, Condi ions
1-3 ha e a mo e gene al o m in P oposi ion 4.2. Indeed,
o ensu e he co e condi ion (acco ding o P ope y 4.3)
condi ion
ER(a*)
n
F
*
G
*R
n
ER(z-)
=
0
is equi ed.
This condi ion is au oma ically sa is ied
i
z
=
F
and
x
subs i u es
F
in
C(a*),
whe eas i is no
i
x
subs i u es
signal
d.
I signal
z
subs i u es unc ion
F,
z
is equal o
1
in he same s a es as
F
wi h he excep ion o
ER(x*).
Hence,
in
he
one-ho
and he
mono onici y
condi ions, we
should only conside s a es om
ER(x-).
I
x
subs i u es
signal
d,
hen s a es om
S
should be conside ed as well.
No e ha P ope y 4.2 can also be used when signal
z
eplaces se e al igge signals
dl
,
. .
.
,
dk.
In his case
he co e unc ion o
b*
can be ep esen ed as
C(
a*)
=
d
*
. . .
*
dk
*
M
+
N.
A e subs i u ing
x
a new co e
unc ion
is
C(b*),
=
z
*
M
+
N.
When he eplacemen ails (line
5
o Algo i hm 4.3).
In
his case he complexi y o a co e unc ion o
ER(
b*)
can in gene al inc ease (unless he expanded don' ca e se
induced by
x*
implies u he simpli ica ion o
C(b*)).
I
he condi ions o he ollowing p ope y a e sa is ied, hen
no mo e han one li e al
is added o he an-in o
C(b*).
We es ic
ou
me hod wi h such a mode a e inc ease in
complexi y only
o bound he sea ch space.
P ope y 4.5
[7,
81
Le CA(b*) be
a
mono onous co e
o e en
b*
in
SG
A.
I
in he
SG
A'
ob ained om
A
by inse ing
a
new signal
x
he ollowing condi ions a e
sa is ied:
ER(X+)
=
0)
A
(ER(u*)
n
d
*
M
*
F
n
ER(X-)
=
0)
+
s
$
ER(z+),
and
(b)
VS
:
s
E
QR(U*)A!
n
(ER(x-)
U
SI)
n
M
3
1.
e en
x+
is a igge o
b*;
2.
ER(x+)
l
a e @*,
ER@*))
=
0
and
hen he co e unc ion CAI
(b*)
=
CA&)
*
z
o
3.
C(b*)
n
ER(x-)
=
0,
e en
b*
in
A'
sa is ies he mono onous co e condi ions.
This p ope y is used
as
a
heu is ic il e o selec candida e
di iso s ha a e gua an eed no o inc ease excessi ely he
complexi y o he implemen a ion o o he signals.
248