Optimized Synthesis of Self-Testable Finite Sta te Mach ines 
Bernhard Eschermann, Hans.Joachim Wunderlich 
Universitiit Karlsruhe, Institut fur Rechnerentwurf und Fehlertoleranz 
Zirkel 2, 75()() K/lrlsruhe, F.R. Germany 
ABSTRACT 
In this paper a synthesis procedure (or self-tenable finite 
nalt machines is presenled. Tenability is abudy considered 
while transforming the behavioral description of the Muil into 
• struCtural description. To this end a novel state encoding al-
gorithm as well as a modified self'lI::s! architecture are devel -
oped. Expc:rimentalrcsuiu show that this approach leads to a 
significant reduction of hardware overflead. 
Keywords: VLSI design validation, synthesis for testability. 
sequential circuits, built-in self'leSl 
1 INTRODUCTION 
1.1 Molivation 
Scan design methods and designs based on self-lest regis . 
ters , c.g. Bll..BO·s, are used 10 alleviate the problem of testing 
sequential circuits. Both approaches have in common thaI sup-
plemenulI)' hardware only usc:d for tcsting purposes is added 
after the functional design of the circuit is fmishcd. It is tried to 
kccp the hardware ovcrhead low by integrating the additional 
components within me origin.a.l cin:uit as much as possible. 
The overl'lcad can be reduced funher, if testability is consid-
ered during thc functional design of the circuit (~synthesil for 
tcstability~). Thc advantagcs of this approach are twofold: 
Firstly, thc tcst hardware, which has to be implcmented any-
way, can be util ized in systcm modc instcad of being supert1u-
ous aftcr the tCSt is finished, thus reducing thc amount of logic 
needed to implcment the system functionality. Secondly, logic 
dcsign decisions can be tarzcted towards obtaining circuits. 
which are easily testable Hby conSUUCtiOfl~. SevenU approaches 
to synthesis for testability havc already been investizated and 
are reviewed in the: sequel. 
CH 28n-91'i101OOO0I03901501 .00 _1lXKlleee 39' 
1.2 Slate o r t he Art 
A finite state machine (FSM) can be tested function.a.lly by a 
sequcnce of teSI patterns. which validates the existcnce of all 
the StateS and the correctness of all ttle state transitions. Such a 
ch~cking experiment (Henn 64) can be simplified by adding 
eXIJ"I inputs. outputs and/or slate transitions to the FSM (e.g. 
(FuKi 74], IPrad 83J, (HaMc 84J. (SaDa 86J. (WaMM 87». 
Devadas et al. proposed a special state assignment strategy 
(DMNS 88al. thai alloW! 10 raiuce the test length by replacing 
the exhaustive checking with deterministic teSI panems using a 
single stuck-at fault model. Laler on the same authors pub-
lished an approach for dcsigning sequentially irredundant 
FSMs. which can also be tested for all singlc stuck-at faulu 
(DMNS 90). Oleng and Agrawal were able to reduce the num-
ber of flipnops in a partial scan path by using a special state 
assignment algorithm [OlAg 89J. 
On-line cbt:clring of FSMs can be done by verifying the state 
codc sequence with a parallel signature register. Leveugle and 
Saucier (LeSa 89J simplified this process by encoding the 
sta tes in such a way, that the signllurt only depends on the 
stile reached by the FSM and nOI on the exact transition se-
quence, with which the state Wll.ll reached. Chuang and Gupta 
[OlOu 89J suggested 10 use a parallel self-test strategy for se-
quential circuits, in which the: signarures coUccted in a multiple-
input linear feedback. shift register are also used as test patterns. 
The problem thai certain states are not reachable in self-tell 
mode is avoided by assigning the state codes in a clever way. 
This paper focuses on the synthesis of self-testable FSM 's. 
In the following subsections we firsl present our wget archi-
teCture, and illustrate its merits with a small example. The de-
scription of an FSM Stale aSSignment algorithm in section 2, 
which makes optimal use of the self-test hardware. forms the 
core of this paper. Sclf-testing circuits generally employ linear 
feedback shift registers fOf" panem generation. The impact of 
choosing a particular feedback polynomial on the state encod-
ing is discussed. Testing the modified self- test structure is 
similar to testing the modified scan path structure in 
tEsWu 901 and therefore not eIabon.ted in this paper. 
1.3 Target Ar chitecture 
A circui! is made self-teslllble by adding a source of rest pal-
terns and a response analyzer 10 the circuit. One approach is 10 
use a built-in logic block observer (BILBO) [K6MZ 79J. The 
system flipnops are. redesigned. so that they can function as a 
linear feedback shift reg ister (LFSR). which is able to both 
generate tesl patterns and to compact lest responSC$ into a sig-
natW"e. TIle mode of the BILBO is detennined by external con-
trol signals. While LFSR -, generating pseudo-random patterns 
are widely used as paltern generators. many circuits are not 
amenable to random tests due to faults with low detection pr0b-
abilities. By using pattern generators with optimized signal 
probabilities (e.g. GURT's [Wund 87J), higher fault coverages 
can be obtained with reasonable tesllengths. 
Fig. I shows three possible self-test architectures I. In archi-
tecture a) [Benn 84J. (WaMc 87J the system flipnops can be 
configured as autonomous LFSR. which generates teSt panems 
for the combinational logic (PO: pattern generator). 1lIe re-
sponses are compacted in a separate mul tiple-input LFSR 
(MISR). 1£ the signature analyur is implemented as a BILBO. 
it can also be used to gener,lIe test patterns f?J" other circuits on 
the chip. Architecture b) [Benn 84] is applicable, if the logic 
can be partitioned into two pans, such thaI the state signals 
generated by one pan are only used as inputs in the other pan. 
In a [lISI test session BILBO I is employed as pattern genera-
tor, BILBO 2 as signature analyzer, in a second session the 
functions are interchanged. Unfortunately, for FSM-s such a 
panitioning is rarely possible. Architecture c) (BaMc 82) , 
[BeMa 84) saves a separate pattern generator, it uses the o ut-
puts of the signalure analyzer as teS! patterns instead. The 
drawback is that the characteristics of these tes t patterns may be 
undesirable [ChGIl 89J. In the sequel we will restric t ourselves 
10 architecture a) , since it is the only one usable for arbitnuy 
circuits and able to guarantee a high fault coverage. 
combi-
national 
logic 
a) SeplTllte pattern generation and signature registers 
Pattern generation and response analysis for tile primary inputs and 
outputs are not shown, since !hey ~ identical for all the sell'leSt 
.-chi1CC~. 
391 
b) Combinational logic partitioned 
com b i-
national 
logic 
c) Signature register used to generate test panerns 
Fig. I . Architectures of self-testable sequential circuits 
TIle test pattern generation register PO is characterized by its 
ability to cycle through certain slates on its own. This property 
can also be used in system mode, if the encodings of the pre-
sent and the next state are consecutive elements in this cycle. If 
the next state code is produced by the PG register. which has to 
be implemented for lesting purposes anyway, it is not neces-
sary 10 generate it in the next state logic. Replacing the next 
state entries with don-t cares for al l such uansitions, greatly in-
creases the potential for logic optimization of the combinational 
logic. Fig. 2 illustrates a possible real ization of this idea. An 
additional output signal liS detennines, whcther the State ma-
chine nipflops behavc like ordinary D-flipnops or function in 
pallero generation mode. In this mode the state register gener-
ates the next statc on its own, the next state signals assened by 
the combinational logic can be selto arbitrary values. 
combi-
national 
logic 
Fig. 2. ModifiCd self-rest architecture 
M1 
SR 
The main problem is to find a slate assignment reducing the 
combinational logic of this modified self-test structure. 
Conventional state assignment algorithms are cenainly oot opti-
mal, because the pattern generation capability of the state mem-
ory canoot be taken into account until aftcr the state assign-
mc:nt. On the other hand it is not necessarily advan tageous to 
maximize the number of state transitions generated by the PG 
register, since il may be impossible to fllnhcr minimize the 
combinational network for the remaining state transitions. Both 
lUpcclS, minimization by replacing next state entries with don'l 
cares and minimization by conventional logic optimization al-
gorithms have 10 be regarded concwrently during stale assign-
ment. 
1.4 Illustra tive Exam ple 
A variery of state assignmenl algorithms has been proposed 
to minimize the area of the combinarional logic needed to im-
plement an FSM. An extensive survey can be found in 
[Esch 9OJ. Most of the newer algorithms for two-level 
combinational logic follow a slnI.tegy proposed by DeMicheli et 
al. [OcMi 86]: FirS! , logic minimization is applied to a 
symbolic representation of the FSM. The effect of this 
symbolic minimiration1. is 10 group together the states that are 
mapped by some input into the same next state and output. If 
these groups of states are encoded in a minimal subspace of 
Boolean r-space (r : encoding length), the number of product 
tenns of a two-level implementation is reduced. It is the task of 
the subsequent encoding step to satisfy these coding 
consrraims. 
To illustrate th is process. the FSM of F ig. 3a is used. If 
each symbolic stale is replaced by a binary code word, in 
which each Slale is represented by one bit position (Fig. 3b), 
and this binary representation is minimized with a standard 
minimization algorithm. the result in Fig. 3c is obtained. This 
minimired symbolic cover contains the coding constraints that 
have to be satisfied later on. 
Slate in n.state out. , i "' 0 , i n. 0 A 00 A I 100 00 100 I 101 00 100 I 
01 B 0 100 01 010 0 111 1- 010 I 
I· B I 100 1- 010 I 100 01 010 0 
B 00 A 0 01000 100 0 010 00 100 0 
01 C 0 010 01 001 0 010 01 001 0 
I· B I 010 1- 010 I 001 01 100 0 
C 00 A I 001 00 100 I 
01 A 0 001 01 100 0 
I· B I 001 1- 010 1 
Fig. 3. 
a) FSM description b) symbol. deser. c) coding constraints 
The first symbolic implicanJ in Fig. 3c contains the follow-
ing information: If states A and C are given adjacent codes 
(Hamming distance equal to t). the binary implicanlS can be 
merged in Ihe same way as their symbolic counterparts are. 1be 
1. To simplify the presentation. in this paper IICtual ly only "disjoint 
minimization" [OeM; 861 is used. 
392 
constraint in line 2 is trivially satisfied by any encoding. With 
the stale assignment of Fig. 4a, the two-level logic of Fig. 4b is 
obtained. The eltample illuslTates that conventional state as-
signment methods only use those implicaDts of Ihe minimized 
symbolic cover, in which groups of present state symbols ap-
pear. 
state A: 01 
Slate B: 10 
state C: 11 
Fig. 4. a) state assignment 
, i no 0 
·1 00 01 I .. I· 10 I 
01 01 10 0 
10 00 01 0 
10 01 II 0 
II 01 01 0 
b) PLA personalization 
With the self-test architecture of Fig. 2, the next state need 
not necessarily be produced by the combinational logic of the 
FSM. The self-test hardware can be ulilized to take over Ihis 
function if the next state code of the FSM is equal to the next 
panern generated. by the PO register. For the state encoding of 
Fig. 4a and the LFSR feedback polynomial 1+x+x2, the PO 
register built &om this LFSR is able to generate Ihe state transi-
tions A -J B, B -J C , and C -J A. The symbolic implicanls 
in line 3, 5 and 6 of Fig. le, not usable for minimization in 
conventional state assignment algorithms, can now be com-
pletely saved, if the signal US '" 0 (cf. Fig. 2) makes the LFSR 
operate in pattern generation mode, and US = I makes it load 
the next state signals from Ihe combinational logic. The result is 
shown in Fig. 5. 
, i "' 101 00 100 
III I· 010 
100 01 ... 
010 00 100 
010 01 ... 
001 01 .. . 
0 US 
I I 
I I 
0 0 
0 I 
0 0 
0 0 
s ns 0 l/.S 
- I 00 01 
1- 10 I 
1000010 
Fig. 5. a) min. symb. description b) PLA personalil.8.tion 
~ 1 , , 
Fig. 5. c) Resulting circuit structure 
2 SOLUTION OF THE STATE ASSIGNMENT 
PROBLEM 
Our approach to state encoding is based on an analylical 
formulation of me state assignment problem. The main advan-
tage of this approach is that a global optimiution is perl'onned. 
The heuristic algorithms usually employed for utisfying me 
coding constrain[S all use some kind of a greedy ordering. 
which is likely to lead to a good solution in most cases, but 
sometimes also fails in achieving this objective. Additionally. iI 
is very easy 10 accommodate the additional PG register con-
strainu in me analytic fonnulation. Beforehand, some matrices 
have to be introduced. Let s be Ole number of states of the 
FSM, and r the number of bilS used fOf the encoding of these 
states. 
Definition 1: The adjactncy matrix A of a minimiud sym-
bolic cover is an s x s matrix of non-negative integer entries 
aa:. For il'k the value ailt corresponds to me number of lines. in 
which SlIlte i and k boOl occur in a coding constraint; the diago-
nal entries aii are set to O. 
Defininon 2: 1bc disranCt matrix 0 is a 2' x 2' matrix with 
non-negative integer entries dJI. where djl is equal to the 
Hamming distance of codes j and I minus I for j .. I and 
djj = O. 
Similar adjacency and Hamming distance values have al-
ready been used in many state assignment algorithms (see 
(Anns 62) for one of the ('lnt re ferences). To describe the ef-
fect of the PO register. two other matrices become necessary. 
Definition 3: The successor matrix S of a minimized sym-
bolic cover is an s x s matrix o f non-negalive integer entries 
sik. where Silt is the number of symbol ic implicants with an 
isolated present state i and I\Cltt state k. 
Dqinition 4 : The cyclt matrix C of an r-bit pattern generator 
is a 2' x 2' matrilt with entries Cjl" (O,II. where Cjl - 0, if 
code I is the successor of code j in the sequence geneI'llted by 
the pattern generator, and cjl = 1 otherwise. 
Manix A collects the infcmtation about pairs of statts from 
the minimized symbolic cover, roatrilt S deals with the succes-
sor relationships obtainable from the symbolic implicanUl not 
specifying any slate groups. Matrices 0 and C contain the in-
formation about pain of cotks necessary fOf the encoding pr0-
cess) . 
For the example of section 1.4 and the minimized symbolic 
cover in Fig. 3c. the matrices in Fig. 6 are obtained. In matri -
ces A and S the rlnt row/column COITesponds to state" An, the 
second to state WS " and the third 10 Stale "C". The order of en-
tries in matrices 0 and C corresponds to the codes 00. 01 , 10 
and II in tnat sequence. For matrix C, again the LFSR with a 
feedback. polynomial l+x+x1 was used. NOIC thaI A and 0 are 
'~:'=l!T~rs:~nl i ~ 1 
8=[H!l c-ll i ~ n 
Fig. 6. Eumple matrices A. S, 0 and C 
To fannulate the state assignment problem analytically, a 
COSI function is needed that captwt:s all the nec:esiW)' ingredi-
ents of a good assignment. In a good assignment, all the StateS 
appearing together in many symbolic implicants are assigned to 
codes with small Hamming distances. prefenbly to adjacent 
codes. Let X be an assignment matrix with Boolean entries ltlj 
E {0,1 ), Xi) - I if code j is assigned to s tate i and 0 other-
wise. Then a partial cost of 
a (ij,k.1) ;= i ailt djlltij ltltl 
is incurred (cf. Fig. 7) by the assignment of. pair of non-adja-
cent codes j and I (djl :' dlj > 0) to stales appearinj together 
in symbolic implicants (ailr. = aid > 0). The factor 2 wes the 
sy~uy of matrices A and 0 into account. 
states codes 
/ 
, , 
Fig. 7, Non-adjacency cOSt a (ij,k.l) 
1 Two _ mauieeI are necessary. if "eovennl rcbtiOlLll" from • Ir\Ie 
S)'IIIbolie minimiz.alion arc 10 be (:(lI\$idered. 
Ir lnnsitions nOi. minimizable with the help of adjacency 
constraints (SUr; > 0) cannot be realiud with the help of !he PO 
register (cJ - I) by usigning code j 10 stale i (lI.ij - 1) and code 
110 Sllle k (10k!- I), Ihb corresponds 10 a COSI o( 
t (ij,t) : .. IiJI; cp "ij lI.tl 
(d. Fi,. 8). 
ltatel 
x _1 
XjJ-a, / / 
• < 
• ~"'9 / " 
k 
"" _1 
""' .. 
j 
• 
• 
• 
Fi,. 8. Non·PO transition cost t (ij,k,l) 
'. 
The problem of nndinl an appropriale Issignment matrill. X, 
such that SIAIe pain appearing lOielher in symbolic implicants 
are encoded with adjacent codes and thai the remaining state 
nnsitions lit prnferably produced by swiu:lling 10 pattern gen-
eration mode, then can be fonDll.alCd IS a 0-1 inleger program: 
(1) min(X ); L (a(i, j,k,I)+T(i,j,k,1)) 
'." :: L (ta~d, +Bille,) x,x loI 
1.1. •• ' 
(2) w .r. t . LXu s: 1 ~j 
I 
(3) LX .. _I ~i 
J • 
( 4 ) Xu e {O,I} 'If i ,j 
In this formulation the complete COSI of !he assignment was 
obtained by adding the COIl of transitions nOl reducible by logic 
minimization to the COIl 01 transitions no! realiz.able by switch· 
ing 10 pattern aeneration mode and sunvning lhese COSt values 
over III Slates and codes. Adjacency and successor relation-
ships can also be given different weights by minimizing the 
sum of COSI values kl a(ij,k, l) .k2 't (ij.k,I), with arbitrary 
constants k l.klO!:O. The i • j linear conslninlS (2) and (3) en-
sure that each stale is lSIigned exactly one code and thll each 
code b assigned 10 It most one stale. 
Problem (I) - (4) is I well· known combinatorial opIimiu-
lion problem, the quadratjc assiglllMnt probl~m (GaNe 72). 
Although it was proven 10 be NP-complete (Galo 791. because 
of ils relevance for many applications a 101 of effon wu spenl 
to develop feasible solution methods (see (Burk 84) for an 
". 
overview). Ex.acl a11orh,tuns usin& implicit enumeration teCh-
niques can cope with problems up to 1S·20 SliteS. For larger 
problems. we chose 10 usc • heuristic approach similu to 
(BuRe 14). The algorithm does rIO! rely on I beuristic ordering 
of coding conscra.ints or codes 10 be encoded; the COSt function 
to be minimized always provides. g10baI view on the complete 
encoding. 
For the eumple 01 section 3, the minima.! cost obtained with 
the assignment in Fig. 4a 
i. 
L (~air.dj+8"cj) lIUllW - 2 
I, J. t ,L 
with a COSI of 1 for non-adjacencies (Ihe Hamming diSlance 
between the codes (or ~A~ and ~8~ is 2) and a COSI of I (or 
0Iher transitions rIO! realiuble with the PG regillter (B -t A). 
'The proposed stalC encoding method can be used f« multi· 
level combinational circuits with only minor modiflCationS. In 
[DMNS 88b} I nrst Slate aui&nmenl algorithm targeted to-
wards multi · level implementations wu proposed. II is based 
on mlnimiun& I COSt function with the ume mathematical 
struClure u the: non-adjacency pan of the COIl function used 
above. Tbe only difference is that the values ait lit not derived 
by symbolic minimization bUI by eslimlling the number of 
common cubes that can be UU'lCted from the resulting combi-
national nelwork. 
3 CHOICE OF FEEDBACK POLYNOMIAL 
Unti l now the characleris tics o(!he pattern generator were 
only needed 10 determine the cycle matrix C. 'Illere(orc any test 
pattern generalOf describable by such a maDix can be SCCOffi' 
modated. In practice the chotec wiU be made based on the nec-
essary faull eovera&e and the hardware overhead involved In 
the sequel we will consider the imponanl case of LFSR " with 
primitive fcedllM:k polynomials (cC. (Pete 72]). 
An LFSR with feedback polynomial Pi(x) produces a code 
Kquent:e which. when reversed. is equal 10 the sequence pro-
duced by the reciprocal foodback polynomial Pi '(x). Hence. the 
cycle maDix q' obtained (or Pi ' (x) is equal to the transposed 
cycle matrix. C, (or Pi(x). If the jndkes o( the codes are per-
muted in such I way, that Cj - becomes equal to Cj. the com:-
spondin& permutations in the diSllnCe maDix 0 will revene all 
the Iine5 of D. Accordingly. the liite usignmenlS obtained 
with different polynomials vary. 110 do the complexities of the 
resulting combinational logic. To obtain the optimal solution 
requires finding out, which LFSR sttucture is best suited to me 
FSM under consideration. Choosing,the feedback polynomial 
of the LFSR by-minimizing the cost function of section 4 over 
all c; thus provides an additional degree of flttdom 
In order to minimi:r.e LFSR area, minimum weight polyno-
mials are often preferred. An interesting fact is that it does nOt 
matter, whether a standard implementation or a modular im· 
plementation [McCI 86] of the LFSR is chosen, as long as a 
polynomial p(,,) = 1 + "i + "n, 1 !!> i < n, with only one 2-
input XOR-gate in the feedback. structure of the LFSR is used. 
The reason is that in this case both implementations only differ 
in tbe sequence of flipflops (see Fig. 9), which is irrelevant 10 
state assignment and logic minimilation. Matrix D remains un-
changed, because tbe permutation of coding columns does not 
influence the: Hanuning distances of codes. 
standard implementation 
crn:".~ 
modular implementation 
e"·~·· -~ 
Fig. 9. Standard and modular LFSR with p(x) = 1 + xi + xn 
4 RESULTS 
The complete logic synthesis process for self· testable 
FSM 's is summarized in Fig. 10. Sianing from a behavioral 
description, the coding constraints are generated either by sym-
bolic minimization (for 2-Jevel combinational logic) or with the 
approach presented in (DMNS 88bJ (for multi· level logic). 
They are analyzed and trans lated intO the matrices A, D and S. 
The default encoding length is rO - r log2 s l. but any other 
number r > rO can be specified as well. Matrix C is computed 
for a first candidate PO register. With these matrices the algo-
rithm for quadratiC assignment is staned. The resulting cost 
function value can be compared for different PO registers. The 
PO register with the lowest cost is chosen. Afterwards logic 
minimiz.ation (either 2-leve\ or multi·level) can be perfonned 
and a layout for the self-testable FSM can be generated. 
'" 
( behavioral FSM iPGn~.~. } 
description ~ description 
'f I I generation of I I I 
coding constraints 
I 
I 
( matrieea A, D. S ) I l """'C J 
"" 
I / 
quadratic assignment 
algorithm 
'f 
I logic minimization I 
-~ 
( Boolean equations 
to layout 
generation 
Fig. 10. Synthesis process for self-testable FSM's 
We perfonned various experiments by running FSM bench· 
mark examples from the MCNC Workshop on logic Synthesis 
(MCNC 88J through a preliminary implementation of the a1go· 
rithms presented. First, the machines were encoded and opri. 
mized disregarding the: pattern generation capability of the state 
memory. We used the programs NOVA4 (2·level logic, 
(ViSa 89]) and MUSTANGS (multi. level logic, (DMNS 88b]) 
from the Octtools distribution of the University of california, 
Berkeley [ocr 89) for this purpose. Afterwards, we used our 
combined synthesis for testability (SrI) approach. 
The combinational logic was optimized using identical logic 
minimizat ion procedures for the conventional and the SIT ap· 
proach. This is panicularly imponant fOl" comparing multi·level 
logic resulls, since multi·level minimit.ers are generally interac· 
tive and it would be impossible to distinguish between im-
provements due to a modified circuit stn.Jclure I state assign· 
ment on the one hand and a more intensive logic minimization 
on the other hand. Some results are summarized in Table 1. 
The column "i/o/s" gives the number of input variables, output 
variables, and states, respectively. For the two-level implemen-
tations of the combinational logic the number of PLA product 
tenns, for multi-level logic the number of literals is given. CPU 
4 MoreexacLly, 1M encoding option "ihybrid- W3S used. 
S Bot/t,!he fMin·omntcd sJgorllhm and !he fanom-criemed a1gorilhm 
.... ere run . The best resuJt .... as taken. 
times for the state assignment were in the range of minuteS on a 
3 MIPS machine. 
2· level • <) m-Ievel 1# lit 
ti 
NOVA SIT MUST SIT 
146 136 822 773 
91 83 '" 569 149 59 547 496 
I ">" ~ 94 93 594 543 59 " 270 241 I donfil' 29 33 160 74 
48 44 280 253 
80 81 351 236 
76 65 2A8 171 
29 27 149 m 
64 54 176 146 
30 27 121 134 
m"''' 20 17 lOS 94 
~ IS 17 70 48 19 16 77 70 
13 9 35 29 
Table 1. Summary of beochmark n:sults 
For many examples significant savings arc: possible, 
although, because of output incompatibilities, not al l the transi· 
tions realized with the PG register can indeed be saved. An ex· 
cellent illustration of this effect can be found in Table I: the 
only difference between the examples sl and sin is that for sIn 
aIllhe outputs are "O~, so output I11compatibilities do nO! playa 
role, in contrast to sl . The problem is particularly important for 
2·ievei combinational logic; it could be alleviated by separating 
the next State logic and the output logic. Sometimes there is a 
tradeoff between satisfying adjacency constraints and utili:ting 
PO transitions. As it is unlike ly that there exists a cost function 
aceu<1Itely nlOdc:linl: this effect withuut requiring ellponential 
effort (logic minimiultion is NP·complete (GaJo 79]), it may 
happen that utili:ting PG transitions actually increases the 
amount of hardware needed (cr. donfii~ and sl). In this case 
ellptrimenting with different weighting factors k I and k2 in 
cost function (1) can help. 
S CONCLUSIONS 
Self·testable circuits can provide a satisfactory solution to 
the problem of testing digital systems, if they are realizable 
with a reasonable amount of Clltra hardware. In this paper we 
presented an approach to reduce the overhead for sclf· testable 
control units by finding a useful application of Ihe se1f·test 
hardware in system mode. This way the combinational logic 
39. 
for implementing the system functionali ty can be simplified. 
Self· test thus may become more competitive with other design 
for testability methods for area--critical applications. 
ACKNOWLEDGEMENTS 
The help of Prof. Burkard and Dr. Rend! from the Technical 
Univers ity of Graz (Austria), who provided us with some stan· 
dard programs for quadnttic assignment, is gratefully admowl· 
edged. 
Aman 81 
Arms 62 
BuRe 8A 
.,.,." 
CbAg 89 
DeBS8~ 
DeMi 86 
LITERATURE 
R. Amann: Algorithmic Design Methods for Combined 
PLA/ROM ConlJOtie rs (in German): Fonschrillberichle 
VD!, nt. 68,1987. 
D. B. Armstrong: A Programmed AJgoriLhm for A$Signing 
Internal Codes 10 Sequential Mac hines: IRE TJ1U\S. on 
Elec1JOnic Computers. vol. EC· II , lIP. 466-472, 1962. 
P. H. BardeU, W. H. McAnney: $elf.Testing of Multichip 
Logic Modules: Pmc:. IEEE Inl Test Conference, lIP. 20(}.. 
204,1982 
F. P. Beuder, M. J. Manner: HILOO: Tile Highly 
Integmtcd Logic Device Observer: VLSI Design, pp. 88·96, 
June 1984. 
R. G. Bennetts: Design of Testable Logic Circuits ; 
Addison·Wesley, 1984. 
R. E. Burkard, F. Rendl : A Thermodynamically Motivated 
Simulated Procedure for Combinatoria l Optimiuuion 
Problems: EurQpean Journal of Operational Research. vol. 
17, pp. 169·174, 1984. 
R. E. Burkard: Quadtatic Assignment Problems: European 
Jownal of Operational RelotlCch, vol. I ' , pp. 233-289. 
1984. 
K. _T. Cheng. Vishwani D. Agra .... aJ: Design of Sequential 
Machines for Emeic:n! Test Gcnc:rat.ion; Dig. Tech. Papers 
International Conference on Computer·Aided Design. pp. 
3'8·361 . 1989. 
C. C. Chuang. A. K. Gupta: The Analys is ofPar1iUel BIST 
by the Combined Markov Chain (CMC) Model; Proc. IEEE 
Inl Test Confe~ lIP. 337· )43, 1989. 
G. DeMicllcli. R. K. BraylOO. A. Sangiovanni·VincenteUi: 
()ptimIJ State Assignment for Finite Slate Machines.: IEEE 
Tratls. on Computer·Aided Design, vol. CAD-4, no. 3, pp. 
269·285, 1985. 
O. DeMicheli: Symbolic Design of Combinational and 
Scquentiall.ogic Circuits Implemented by Two-Level Logic 
Macros; IEEE Trans. on Computer·Aided Design, vol. 
CAD·S, pp. 591-616, 1986. 
DMNS 8Sa S. Devadas, H.-K. Ma, A. R. NewlOn, A. Sangiovanni_ 
VirM:emdli: SyDthuis and Optimization Procedures for 
Fully and Euily Tcslablc Soquc:mial Madlines; Proc. InL 
Test Conff:fUlCe. PII. 621-630, 1988. 
DMNS S8b S. Devldu, H.·K. Ma. A. R. Newton, A Sangiovanni_ 
VineenleUi; MUSTANG; Slale Assignment of Finite Stale 
M.eh.inu Tuaetin, Multilevel Logic lmpkmenwions; 
IEEE Trans.. on CompuW-Aided [)Wan, '101. CAD-7. PII. 
1290-1300. 1988. 
DMNS 90 S. Devldu. H. T. Ma. A. R. Newton, A. Sangiovanni-
VincenteUi; IrredIllOdanI SeqllC'ntial MaclUnes Via Optimal 
LocJc: Synt/le$is; IEEE Trans. on Computer-Aided Desi,n, 
vol. CAD-9. PII. I-II, 1990. 
EsWu90 
B. E,cherman n: State Assignment Method$ for 
SynchroDOllI Sequential Circuits; Progress in Computet 
Aided Vt..S1 Design, O. lobrLst (ed.), Able~, Norwood. 
''''. 
a. Eschennann. H.-J. Wunderlich; A Synthesis Mr:ihod 10 
Reduce Sean Delign Oveme.d; Fim European Desi,n 
Automation Confetenu, 1990. 
FuKi 74 H. Fujiwan, K. Kinoshita; Design of Diagnosable 
Sequential Machines Utilizilll Exln OuqllllS; lEEE Trans. 
on Computers, \'01. CD. PII. 13S-14S, 1974. 
Ga1079 M. Garey. D. JohllSOn; Computers and Intractability; 
Freeman, Ne .... York 1979. 
GaNc 72 R. G.-f"lIIkcl. G. Nemhalucr. Inlegu Programming; Wiley, 
Ne .... Yorlc. 1972.. 
HaMc 114 S. Hassan. E. McCluskey: PseIiOO-Exllauslive Testil\i 01 
Sequential Machin« Ulin, Sia;nr.~ Analysis; Proc:. InL 
Te$l COIIr_nee, PII. 320-326. 1984. 
Hem 64 F. C. HeMie: FWlt Detc:ctinl EJ.pcrimelIlS for Sequential 
Circuits; Pl"oc . Sih Annua l Symp. Switching Cirtuit 
Theofy IJId Logical Design. PII. 9S-IIO, 1964. 
KOMZ 79 B. KOnemartll, J. Muchl, G. Zwichoff: Built-In Logic Block: 
Obse ...... tlon Toc:hnlq llCl; Proc. lEEE lnL Test Conference, 
pp. 37-41.1979 
LeSa 19 R. Leveugle. G. Saucier. Optimized Synthesis of Dedicated 
Controlle rs with Conc:urrent Chectins Capabilities; Prot. 
InL Test ConrerMCe, pp. )5S·363, 1989. 
McCI S6 E. J. McCluskey: Logic Design Pl"inc:iples with Emphasis 
on Testable ScmicuStom Circuit$; Prenti<:e·HaU, Englewood 
Cliff., 1916.. 
MCNC 18 R. Liunk:e: Logic Synthesis and Optimiulion Benchmarks, 
Version 2.0; Microelcc\l"Oflic$ Ccnter of North Carolina, 
1918. 
OCT" 
",.72 
"" " 
Octtools Distribution 3.3. EIccIJOllic& ReJearth Laboratory, 
University 01 Califomia, 8erteky, 1989. 
W. W. Petcrson, E. J. Weldon; Enor·Correcting Codes; 
MIT Prea, Cambridge, 1972. 
O. K. Pndhan; Sequential Netwodc Desia;n Using Extra 
InpulS fOl' F.ult Delection.; IEEE Trans. OIl Computers, \'01. 
C-12, pp. 119·123, 1983. 
K. K. Sa/u;', R. Dandapani: A Built-In Self-Tespble 
Design Method for Sequential Circu its; Proc. 16th lnL 
Symp. Fa:ult ToIetatIt Computing. pp. 312-317. 1986. 
ViSa 89 T . Villa, A. Sanlio-tanni-VillCcptelli: NOVA.: Slate 
Assipment 0( FiniloC SPloC t.Uc1lincs for Optimal 1"A-"o-
Level Loa;ie Implementations; Proc. 26th DesiS~ 
AIIIOmItion Confuaocc:, PII. 3"27-332, 1\189. 
WtMo::87 L.-T. Wana;, E. J. McCiustey: Buill- in Self-Test for 
Sequential Machines; Proc. InL Test Confumcc, PII. 1l4-
J.t1.19I1. 
WaMMl7 L..T. Wang, E. J. Mc:CIuskey, S. Mound: ShiTl Relista" 
Tutina; of Sequential Machine.; Proc:. 17th Inl. Symp. 
Faull.ToJetant Computing, pp. 66-71. 1987. 
Wund 87 H.·J. WlUltierllcll: Self_Test Uaing Unequiprobable Random 
l'lIuetIU; Proc. 17th lnL Symp. Faull-Tolerani Computinl, 
PII. 2~1-263. 1987.