The test generation of digital sequential circuits with the multiple observation time strategy
The test generation method is designed for digital circuits with memory on the basis of distinguishing state pairs of good and fault devices. The multiple observation time test strategy, 16-valued alphabet and genetic algorithms are used. The proposed method permits to cover the faults that are not...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2012
|
| Назва видання: | Труды Института прикладной математики и механики |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/124131 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | The test generation of digital sequential circuits with the multiple observation time strategy / V.Y. Skobtsov, Al Tal Abdel Rakhman // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2012. — Т. 25. — С. 210-216. — Бібліогр.: 3 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-124131 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1241312017-09-21T03:03:11Z The test generation of digital sequential circuits with the multiple observation time strategy Skobtsov, V.Y. Rakhman, Al Tal Abdel The test generation method is designed for digital circuits with memory on the basis of distinguishing state pairs of good and fault devices. The multiple observation time test strategy, 16-valued alphabet and genetic algorithms are used. The proposed method permits to cover the faults that are not detected with traditional methods. It increases the fault coverage. Для цифровых схем с памятью разработан метод построения тестов на основе различения пар состояний исправного и неисправного устройств. Применяется стратегия кратного наблюдения, 16-значный алфавит и генетические алгоритмы. Предложенный метод позволяет покрыть неисправности, являющиеся нетестируемыми традиционными методами. Это существенно повышает покрытие неисправностей. Для цифрових схем з пам’яттю розроблено метод побудови тестiв на базi розрiзнення пар станiв непошкодженого та пошкодженого пристроїв. Застосовано стратегiю кратного спостереження, 16-значний алфавiт та генетичнi алгоритми. Запропонований метод дозволяє покрити пошкодження, якi є нетестовними традицiйними методами. Це суттєво пiдвищує покриття пошкоджень. 2012 Article The test generation of digital sequential circuits with the multiple observation time strategy / V.Y. Skobtsov, Al Tal Abdel Rakhman // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2012. — Т. 25. — С. 210-216. — Бібліогр.: 3 назв. — англ. 1683-4720 http://dspace.nbuv.gov.ua/handle/123456789/124131 681.518:681.326.7 en Труды Института прикладной математики и механики Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
The test generation method is designed for digital circuits with memory on the basis of distinguishing state pairs of good and fault devices. The multiple observation time test strategy, 16-valued alphabet and genetic algorithms are used. The proposed method permits to cover the faults that are not detected with traditional methods. It increases the fault coverage. |
| format |
Article |
| author |
Skobtsov, V.Y. Rakhman, Al Tal Abdel |
| spellingShingle |
Skobtsov, V.Y. Rakhman, Al Tal Abdel The test generation of digital sequential circuits with the multiple observation time strategy Труды Института прикладной математики и механики |
| author_facet |
Skobtsov, V.Y. Rakhman, Al Tal Abdel |
| author_sort |
Skobtsov, V.Y. |
| title |
The test generation of digital sequential circuits with the multiple observation time strategy |
| title_short |
The test generation of digital sequential circuits with the multiple observation time strategy |
| title_full |
The test generation of digital sequential circuits with the multiple observation time strategy |
| title_fullStr |
The test generation of digital sequential circuits with the multiple observation time strategy |
| title_full_unstemmed |
The test generation of digital sequential circuits with the multiple observation time strategy |
| title_sort |
test generation of digital sequential circuits with the multiple observation time strategy |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2012 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/124131 |
| citation_txt |
The test generation of digital sequential circuits with the multiple observation time strategy / V.Y. Skobtsov, Al Tal Abdel Rakhman // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2012. — Т. 25. — С. 210-216. — Бібліогр.: 3 назв. — англ. |
| series |
Труды Института прикладной математики и механики |
| work_keys_str_mv |
AT skobtsovvy thetestgenerationofdigitalsequentialcircuitswiththemultipleobservationtimestrategy AT rakhmanaltalabdel thetestgenerationofdigitalsequentialcircuitswiththemultipleobservationtimestrategy AT skobtsovvy testgenerationofdigitalsequentialcircuitswiththemultipleobservationtimestrategy AT rakhmanaltalabdel testgenerationofdigitalsequentialcircuitswiththemultipleobservationtimestrategy |
| first_indexed |
2025-07-09T00:53:29Z |
| last_indexed |
2025-07-09T00:53:29Z |
| _version_ |
1837128651153342464 |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2012. Том 25
UDK 681.518:681.326.7
c©2012. V.Y. Skobtsov, Al Tal Abdel Rakhman
THE TEST GENERATION OF DIGITAL SEQUENTIAL CIRCUITS
WITH THE MULTIPLE OBSERVATION TIME STRATEGY
The test generation method is designed for digital circuits with memory on the basis of distinguishing
state pairs of good and fault devices. The multiple observation time test strategy, 16-valued alphabet
and genetic algorithms are used. The proposed method permits to cover the faults that are not detected
with traditional methods. It increases the fault coverage.
Keywords: test generation, genetic algorithms, the multiple observation time strategy.
1. Introduction. The problem of test generation for digital sequential circuits is
widely treated, and many algorithms have been suggested lately [1]. But this problem
remains intractable with using three-valued alphabet and single observation time (SOT)
strategy. The task complexity depends on that, there is no information about initial
state of the circuit. When reset or synchronizing sequence is not available the sequential
circuit cannot be tested with algorithms using the three-valued logic. In this case it
is necessary to use other methods. The using of more adequate multiple observation
time test strategy permits to improve the simulation accuracy and to distinguish state
pairs of good and fault circuits at different times. Note that the exact statement of test
generation problem essentially depends on the definition of the fault detectability. In fact
the various researchers use the different definitions of the fault detectability and it causes
the additional difficulties.
2. Definitions. Let a circuit has primary inputs X = (x1, ..., xn), outputs Z =
(z1, ..., zm) and state variables Y = (y1, ..., yk). The most widespread approach to processing
undefined initial states of sequential circuits is based on logical 3-valued simulation
in alphabet E3 = {0, 1, u} [1], where undefined values u are assigned to all variables
yi = u of circuit state in initial time moment. The vector of initial state is defined as
S = (y1 = u, ..., yk = u) accordingly. Then initial indeterminacy is removed bit by bit
under availability of synchronizing sequence, and state variables take on defined values
0, 1. The problem is in that fact that synchronizing sequence exists not for all circuits
with memory.
Let good sequential circuit realizes finite state machine (FSM) A = (Y, X, Z, δ, λ),
where Y, X, Z – finite sets of states, input and output signals accordingly,λ : Y ×X → Y
– a transition function, defining next FSM state, δ : Y × X → Z – a output function,
defining output signal. The functions δ and λ are realized by combinational circuits,
where:
Y = (y1, ..., yk) : yi ∈ {0, 1}, for i = 1, k; (1)
X = (x1, ..., xn) : xl ∈ {0, 1}, for l = 1, n; (2)
Z = (z1, ..., zm) : zj ∈ {0, 1}, for j = 1,m. (3)
210
The test generation of digital sequential circuits with the multiple observation time strategy
Let X(1), X(2), ..., X(p) – input sequence of length p. Then Y (y0, 0), Y (y0, 1), ..., Y (y0, p)
– the sequence of states which it passes from initial state y0 ∈ Y under effect of input
sequence X(1), X(2), ..., X(p). Let Z(y0, 0), Z(y0, 1), ..., Z(y0, p) – corresponding output
sequence of FSM. Let denote the value of j-th output at t-th simulation iteration as
zj(y0, t) for j = 1,m. Using these denotations the nest FSM state is defined as follows
Y (y0, t) =
{
y0, for t = 0,
δ(X(t), Y (y0, t− 1)), for t 6= 0.
(4)
Similarly output Z(y0, t) is defined by λ function. The fault f transforms FSM A to
FSM Af = (Y, X,Z, δf , λf ). Then we shall use as example little sequential circuit (fig. 1)
with single s− a− 0 fault x2 ≡ 1 and its 2-times iterative combinational circuit (fig. 2).
Fig. 1. Sequential circuit example
Fig. 2. 2-times iterative combinational circuit
The table 1 and table 2 represent automatons that are implemented good and faulty
circuits correspondingly.
Table 1. Fault free FSM Table 2. Faulty FSM x2 ≡ 1
State Inputs X1X2 State Inputs X1X2
y 00 01 10 11 y 00 01 10 11
A(0) 0 1 1 0 a(0) 0 1 1 0
B(1) 0 1 1 0 b(1) 1 1 0 0
211
V.Y. Skobtsov, Al Tal Abdel Rakhman
3. The basic observation strategies of fault detection in sequential circuits.
Further we shall consider different strategies of fault detection in sequential circuits.
Basically we’ll process single stuck-at faults since using more complicated fault models
only increase problem complexity.
In case of 3-valued simulation following definition of fault detection is applied (at
structural level).
Definition 1. Single stuck-at fault f is called detectable in sequential circuit by input
sequence X(1), X(2), ..., X(p) if
∃t ≤ p,∃j ≤ m,∃b ∈ {0, 1} : (zj(t) = b) ∧ (zf
j (t) = b). (5)
According to this definition a fault is detectable if at least at one primary output
in some time moment signals have different values for good and faulty circuits It is
known that results of 3-valued simulation allow to obtain low boundary of fault coverage.
Therefore another more precise criterions of fault detection for sequential circuits are used
(at functional level).
Definition 2. Single stuck-at fault f is called detectable in sequential circuit by input
sequence X(1), X(2), ..., X(p) relatively to single observation time strategy (SOTS) if
∃t ≤ p,∃j ≤ m,∃b ∈ {0, 1}, such that ∀(r, q) : (zj(r, t) = b) ∧ (zf
j (q, t) = b), (6)
where r and q – initial states of good and faulty circuits accordingly.
This definition means that under this observation strategy fault is detectable if at
least one clock t exists such that for any initial state pair (r, q) of good and faulty circuits
some j-th output zj has different values in good and faulty devices. The key moment is
that any state pair of good and faulty circuits must has different output reactions at one
clock. Note that only outputs of last iteration of iterative combinational circuit are used.
As example let consider the simulation of single stuck-at fault x2 ≡ 1 in sequential
circuit (fig.1) on input sequence X = (x1
1 = 1, x1
2 = 0;x1
2 = 1, x2
2 = 0), where high index
is clock number. The table 3 represents the output responses for good and fault circuits
for each possible initial states. These data show that fault x2 ≡ 1 is not detectable in
accordance to single observation time strategy since there does not exist clock for which
all state pairs of good and faulty circuits give different output signals. However, as show
below, this fault is detectable in accordance to multiple observation time strategy.
Table 3. Output reactions for fault free and faulty FSM
Initial state Inputs X1X2
10 10
A(0) 0 0
B(1) 1 1
a(0) 1 0
b(1) 0 1
212
The test generation of digital sequential circuits with the multiple observation time strategy
Therefore sometimes multiple observation time strategy is used for sequential circuits.
In this case different state pairs can be differed at different clocks.
Definition 3.Single stuck-at fault f is called detectable in sequential circuit by input
sequence X(1), X(2), ..., X(p) relatively to the multiple observation time strategy (MOTS)
[2, 3] if
∀(r, q) ∃t ≤ p, ∃j ≤ m, ∃b ∈ {0, 1} : (zj(r, t) = b) ∧ (zf
j (q, t) = b). (7)
Note that principle difference between these strategies is in follows. According to first
strategy all state pairs of good and faulty circuits must be differed at one clock. According
to second strategy any state pairs of good and faulty circuits can be differed at different
clocks. Hence different outputs of different clocks in can be used in combinational iterative
circuit for comparison of good and faulty signal values. For given above example fault
x2 ≡ 1 is detectable of input sequence X = (x1
1 = 1, x1
2 = 0; x1
2 = 1, x2
2 = 0) relatively
to multiple observation time strategy since for any state pair of good and fault circuits
there exists the time clock when they are differed.
The application of MOTS allows increasing fault coverage of tests but requires essential
computing and memory resources. In this case it is necessary save standard reactions of
good circuit for all initial states. For faulty circuit also it is necessary to them with
standard reactions of good circuit.
Therefore last time it is applied so called restricted multiple observation time strategy
(rMOTS), which can be used for circuits that have synchronizing sequence transferred
good circuit to some defined state r from any initial state.
Definition 4. Single stuck-at fault f is called detectable in sequential circuit by
input sequence X(1), X(2), ..., X(p) relatively to the restrictive multiple observation time
strategy (rMOTS) [3] if
∀q ∃t ≤ p, ∃j ≤ m, ∃b ∈ {0, 1}such that ∀r : (zj(r, t) = b) ∧ (zf
j (q, t) = b). (8)
4. Multivalued alphabet. The multivalued alphabets play an important role in
solving considered problem. In proposed method we use the universal 16-valued alphabet
and set of multivalued functions as basic mathematical model [1]. The universal 16-
valued alphabet B16 = {∅, 1, D, G1, D′, F1, D∗, D1, 0, C, F0,H,G0, E, D0, u} is the set
of all subsets of basic alphabet B4 = {0, D′, D, 1}. The elements of B4 have the following
physical interpretation. The elements 0(00) and 1(11) represent equality of signal values
in good and fault DD accordingly. Similarly D′(01) and D(10) represent inequality.
That is the elements of alphabet B4 represents all possible pairs of signal values of
faultfree and faulty devices. Encoding multivalued alphabets is very important. In 16-
valued alphabet B16 it is used the symbol encoding with the help of four Boolean
variables X0, XD′ , XD, X1 that is represented below:∅ = {∅}(X0 = 0, XD′ = 0, XD =
0, X1 = 0), 1 = {1}(0001), D = {D}(0010), G1 = {D ∪ 1}(0011), D′ = {D′}(0100),
F1 = {D′ ∪ 1}(0101), D∗ = {D′ ∪D}(0110), D1 = {D′ ∪D ∪ 1}(0111), 0 = {0}(1000),
C = {0 ∪ 1}(1001), F0 = {0 ∪D}(1010), H = {0 ∪D ∪ 1}(1011), G0 = {0 ∪D′}(1100),
E = {0∪D′ ∪ 1}(1101), D0 = {0∪D′ ∪D}(1110), u = {0∪D′ ∪D∪ 1}(1111). The code
213
V.Y. Skobtsov, Al Tal Abdel Rakhman
X = (X0, XD′ , XD, X1) is characteristic vector. The components of characteristic vector
X = (X0, XD′ , XD, X1) are characteristic variables (X0, XD′ , XD, X1 ∈ B2 = {0, 1}).
The application of alphabet B16 allows to carry out the test generation process for the
fault free and faulty circuits simultaneously at the one model of given DD. Since the
alphabet B16 is the set of all subsets of alphabet B4 then the elements of B16 represent
all possible combinations of pairs of fault free and faulty signal values. It allows to reduce
the search space. Therefore we use this alphabet.
5. Test generation on base of states pare distinguishing. So for test generation
it is necessary to distinguish each states pare of good and fault circuits. We shall use
the common approach [2] that is based on individual distinguishing of each states pare.
In the beginning of test generation process we have the set of initial states pares SI for
that it is necessary to construct the distinguishing sequence T . It is obviously that in
the beginning the set SI is equivalent to set of all possible states pares of good and fault
circuits. For example for circuit fig.1 we have the set SI = {(A, a), (A, b), (A, c), (A, d),
(B, a), (B, b), (B, c), (B, d), (C, a), (C, b), (C, c), (C, d), (D, a), (D, b), (D, c), (D, d)}.
The kernel of test generation method is in following. From the set SI we select the
undistinguishing states pares (S1, S1
f ) of good and fault circuits. For this state pare we
generate input distinguishing sequence T1 with using the genetic algorithm and 16-valued
alphabet and suppose T = T1. Further we simulate in 16-valued alphabet the fault circuit
at the generated input sequence T1. If simulation results show that the fault detectability
criterion (def. 3) is fulfilled then T1 is test sequence and the test generation is over. Else
the test generation process is continued. Then we determine the states pare set SD that
are distinguished with input sequence T1. Further we assume the new states pares set
SI = SI \ SD and select the following initial state pare (S2, S2
f ). For this pare we again
generate the distinguishing input sequence T2 with help of the genetic algorithm. Then
we concatenate sequences T1 and T2: T = T1∪T2. Further we again simulate in 16-valued
alphabet the fault circuit at the generated input sequence T and verify fault detectability
(def. 3) criterion. If criterion is fulfilled then the test generation is over else continued
and so on.
At that approach we process each states pare of good and fault circuits that requires
excessive computing resource. It is possible to process states pares groups with help
of uncertainty insertion to some state variables. Note that the distinguishing states
pares may be only partially definite. Let us suppose that the next states pare (S, Q)
is determined with the following state variables δ1, δ2, ..., δk, where each δi, may have
values {0, 1, D, D′} from 16-valued alphabet B16.
Further during selection next state pare we shall try to insert the uncertainty to
state variables values δ1, δ2, ..., δk as much as possible with keeping fault detectability.
In such a way we extend the distingwishing states pares set. At that we process the
state variables (y1, y2, ..., yk) in series by means of replacement of determined values with
uncertain values in the following way:
1) yi = 0 (0 at good and 0 at faulty circuits) → yi = G0 or yi = F0;
2) yi = 1 (1 at good and 1 at faulty circuits) → yi = G1 or yi = F1;
3) yi = D (1 at good and 0 at faulty circuits) → yi = F0 or yi = G1;
214
The test generation of digital sequential circuits with the multiple observation time strategy
4) yi = D′ (0 at good and 1 at faulty circuits) → yi = F1 or yi = G0.
Note that each state pare must keep the time moment t where output reactions
are different for different state pares. Taking into account aforesaid the test generation
algorithm may be represented as follows.
Test generation (circuit, fault)
{
T = ∅, SI = ∅;
While(exist undistinguishable states pares)
{
Selection indistinguishable state pare (S,Q): S = (α1, α1, ..., αk), S = (β1, β1, ..., βk);
If(indistinguishable states pare does not exist)
then test sequence is generated: return;
Assignment values δ1, δ2, ..., δk in alphabet B16;
Logic simulation in alphabet B16 at input sequence Т with initial states;
if (values D or D’ reach circuit output)
then states pare (S,Q) is distinguished with current sequence Т;
Else
{
Generation distinguishing sequence Ti for (S,Q);
if(distinguishing sequence Ti for (S,Q) is not generated)
then current fault is not detected and removed out fault list;
go to end;
}
For state pare (S,Q): S = (α1, α1, ..., αk), S = (β1, β1, ..., βk)
For j=1 to k do δj = Fβj ;
Logic simulation in B16;
if(T does not distinguish (S,Q)) then restoring value δj ;
δj = Gαj ;
Logic simulation in B16;
if(T does not distinguish (S,Q)) then restoring value δj ;
end;
Determination of new distinguishing states pares (S, Q);
Determination of all distinguishing states pares SI = SI ∪ {S, Q};
}
}
The represented algorithm guarantees test sequence generation for unredundant fault
in that case if it is guaranteed the distinguishing sequence Ti generation for current state
pare (S, Q).
We must to note that for sequential circuits the number of undetectable faults
relatively to SOTS can be enough large. For example, for circuits from benchmark
ISCAS89 even for single stuck-at faults the number of such faults is about 38% [2].
215
V.Y. Skobtsov, Al Tal Abdel Rakhman
Therefore in order to obtain high fault coverage in sequential circuits we must not restrict
oneself to using SOTS and 3-valued simulation. SOTS can be applied at first phase of
simulation or test generation. As result we can pick out set of undetectable faults refer
to SOTS. Then to these faults we should apply simulation or test generation methods
based on more accurate observation time strategies of output signals.
1. Скобцов Ю.А., Скобцов В.Ю. Логическое моделирование и тестирование цифровых устройств,
Донецк: ИПММ НАНУ, ДонНТУ. – 2005. – 450 с.
2. Pomeranz I. and Reddy S.M. The multiple observation time strategy // IEEE Transactions on
Computers. – 1992. – Vol. 41, No. 5. – P. 627-637.
3. Скобцов Ю.А., Сперанский Д.В. Аналитический метод построения различающих последова-
тельностей для дискретных устройств // Автоматика и телемеханика. – No. 1. – 1980. – C. 122-
130.
В.Ю. Скобцов, Аль Таль Абдель Рахман
Построение тестов цифровых последовательностных схем на основе кратной страте-
гии наблюдения.
Для цифровых схем с памятью разработан метод построения тестов на основе различения пар
состояний исправного и неисправного устройств. Применяется стратегия кратного наблюдения,
16-значный алфавит и генетические алгоритмы. Предложенный метод позволяет покрыть неис-
правности, являющиеся нетестируемыми традиционными методами. Это существенно повышает
покрытие неисправностей.
Ключевые слова: построение тестов, генетические алгоритмы, кратная стратегия наблюде-
ния.
В.Ю. Скобцов, Аль Таль Абдель Рахман
Побудова тестiв цифрових послiдовносних схем на основi кратної стратегiї спостере-
ження.
Для цифрових схем з пам’яттю розроблено метод побудови тестiв на базi розрiзнення пар станiв
непошкодженого та пошкодженого пристроїв. Застосовано стратегiю кратного спостереження, 16-
значний алфавiт та генетичнi алгоритми. Запропонований метод дозволяє покрити пошкодження,
якi є нетестовними традицiйними методами. Це суттєво пiдвищує покриття пошкоджень.
Ключовi слова: побудова тестiв, генетичнi алгоритми, кратна стратегiя спостереження.
Ин-т прикл. математики и механики НАН Украины, Донецк
Донецкий национальный технический ун-т
skobtsov@iamm.ac.donetsk.ua
abed_altl@yahoo.com
Received 03.12.12
216
|