1
Alfabet D-algebry umożliwia sformułowanie takiego opisu
układu, w który są widoczne wszystkie sygnały błędne
wszystkie sygnały poprawne.
D - algebra
D - algebra jest to dwójka uporządkowana
<
Φ >
,
,
V
gdzie:
{0,1, , , }
V
D D x
=
alfabet służąc do opisu zmian
powodowanych uszkodzeniem
układu;
Φ
- zbiór operacji nad tym alfabetem.
2
Znaczenie poszczególnych symboli alfabetu V:
• 0(1) - błąd nie zmienia wartości sygnału, jest ona poprawna i
równa 0(1);
• D - błąd zmienia wartość sygnału cyfrowego z 1 na 0; oznacza to,
że w układzie zdatnym sygnał jest równy 1, natomiast w
układzie błędnym sygnał jest równy 0;
•
- błąd zmienia wartość sygnału cyfrowego z 0 na 1; oznacza to,
że w układzie zdatnym sygnał jest równy 0, natomiast w układzie
błędnym sygnał jest równy 1;
D
• x - wartość sygnału jest nieokreślona i może być równa 0,1,
lub D.
D
D - algebra
3
x
1
x
2
x
3
x
4
x
5
x
6
0
1
1
0
0
0
1
1
y
1
y
2
0
1
2
3
4
5
7
6
8
0
0
0
Przykład opisu układu z uszkodzeniem s-a-0 przy pomocy D-algebry
D
D
s-a-0
D
D
Począwszy od swego źródła, uszkodzenie (utożsamiane symbolem lub D)
rozprzestrzenia się w układzie.
D
Jeśli propagowane uszkodzenie osiągnie jedno z obserwowalnych wyjść układu, to stan
wejścia układu odpowiadający określonym warunkom propagacji (jeżeli nie okażą się
one sprzeczne) jest testem rozpatrywanego błędu.
Ścieżka
propagacji błędu
D-algorytm
D-algorytm składa się z następujących
procedur:
• pobudzenie źródła błędu;
• propagacji błędu;
• badania zgodności warunków pobudzenia i
propagacji.
D-algorytm
Początek
Badanie zgodność warunków
ustalonych przez procedurę
pobudzenia i propagacji
Określenie błędu, dla którego poszukiwany będzie test
Przyporządkowanie stanom
wszystkich linii układu wartość x
Punkt decyzyjny:= źródło błędu
Wykonanie procedury propagacji błędu (od wskazanego punktu decyzyjnego)
Warunki
zgodne
Wypisanie test
Koniec
Tak
Odrzucenie błędnego testu. Cofnięcie
się do najbliższego punktu decyzyjnego
Nie
Wykonanie procedury pobudzenie błędu
6
D-algorytm
Procedura pobudzania źródła błędu
Wymuszenie stanu D lub w miejscu występowania błędu. Stan D jest wymuszany w
przypadku błędu s-a-0, natomiast w przypadku błędu s-a-1.
D
D
Niech y będzie wyjściem modułu. Jeżeli na linii y wystąpił błąd s-a-0 (s-a-1), to
wymuszenie na niej wartości polega na ustawieniu wejścia modułu w takim stanie,
któremu poprawnie odpowiada wartość 1(0) wyjścia.
( )
D D
Przy realizacji procedury pobudzenia źródła błędu wykorzystuje się tzw. pierwotne
D-sześciany. Określają one stany wejść bramek potrzebne do wymuszenia D lub na
ich wyjściach. Dla bramek podano je w tabeli 3.
D
7
D-algorytm
Procedura pobudzania źródła błędu – tabela D-sześcianów pierwotnych
Bramka
f
AND
0
x
x
0
1
1
D
OR
1
x
D
x
1
D
0
0
NAND
0
x
D
x
0
D
1
1
NOR
1
x
x
1
0
0
D
XOR
0
0
1
1
0
1
D
1
0
D
D
D
D
D
D
D
D
D
8
D-algorytm
Procedura
propagacji błędu
Procedura propagacji błędu tworzy tzw. ścieżkę pobudzenia, pomiędzy źródłem błędu
a jedynym z obserwowalnych wyjść układu.
Ścieżkę nazywamy pobudzoną, jeżeli zmiana stanu linii początkującej ścieżkę powoduje
zmianę stanu na jej końcu.
Ścieżki pobudzone tworzy się na podstawie tzw. przesyłowych D-sześcianów.
Przesyłowe D-sześciany modułu logicznego wyznacza się
wprost z definicji jego funkcji w D-algebrze.
9
D-algorytm
Procedura propagacji błędu – tabela D-sześcianów przesyłowych
Bramka
f
AND
D
1
D
1
D
D
1
1
OR
D
0
D
0
D
D
0
0
NAND
D
1
1
D
1
D
1
D
D
D
D
D
D
D
D
D
D
D
D
D
1
x
2
x
10
D-algorytm
Procedura propagacji błędu – tabela D-sześcianów przesyłowych
Bramka
f
NOR
D
0
0
D
0
D
0
D
XOR
0
D
D
D
0
D
0
0
1
D
D
1
1
D
1
D
1
x
2
x
D
D
D
D
D
D
D
D
D
D
D
D
11
Tabela propagacji błędu
X
1
X
2
f
AND
f
OR
f
NAND
f
NOR
f
XOR
0
0
0
0
1
1
0
0
1
0
1
1
0
1
0
D
0
D
1
Ð
D
0
Ð
0
Ð
1
D
Ð
1
0
0
1
1
0
1
1
1
1
1
0
0
0
1
D
D
1
Ð
0
Ð
1
Ð
Ð
1
D
0
D
D
0
0
D
1
Ð
D
D
1
D
1
Ð
0
Ð
D
D
D
D
Ð
Ð
0
D
Ð
0
1
1
0
1
Ð
0
0
Ð
1
D
Ð
Ð
1
Ð
1
D
0
D
Ð
D
0
1
1
0
1
Ð
Ð
Ð
Ð
D
D
0
12
D-algorytm
Procedura badania zgodności stanów
Uzupełnienie i badanie zgodności stanów jest treścią ostatniej procedury.
Wykorzystuje się w niej tzw. pierwotne sześciany wyjść modułów przedstawione
w tabeli 5.
1
x
2
x
Bramka
f
AND
0
x
0
x
0
0
1
1
1
OR
1
x
1
x
1
1
0
0
0
NAND
0
x
1
x
0
1
1
1
0
13
D-algorytm
Procedura badania zgodności stanów
Uzupełnienie i badanie zgodności stanów jest treścią ostatniej procedury.
Wykorzystuje się w niej tzw. pierwotne sześciany wyjść modułów przedstawione
w tabeli 5.
Bramka
f
NOR
1
x
0
x
1
0
0
0
1
XOR
0
0
0
1
1
0
1
0
1
0
1
1
1
x
2
x
14
Przykład
x
6
G
7
G
3
x
1
x
2
x
3
x
4
x
5
G
2
G
8
G
6
G
1
G
9
G
5
G
4
y
x
x
x
x
x
x
Krok
Stany linii układu
Komentarz
x
1
x
2
x
3
x
4
x
5
x
6
G
1
G
2
G
3
G
4
G
5
G
6
G
7
1
x
x
x
x
x
x
x
x
x
x
x
x
x
Stan początkowy
2
1
Pobudzenie źródła błędu
s-a-1
1
D
D
3
Wybór ścieżki propagacji
1
2
3
( ,
,
)
G G G
4
0
D
Propagacja przez bramkę NOR
3
(
)
G
D
0
D
D
5
1
D
D
Propagacja przez bramkę AND
5
(
)
G
1
D
1
D
6
0
D
0
D
Propagacja przez bramkę OR
7
(
)
G
0
0
D
7
x
x
1
1
x
x
0
D
0
D
0
D
Stan końcowy
D
15
Przykład
x
6
G
7
G
3
x
1
x
2
x
3
x
4
x
5
G
2
G
8
G
6
G
1
G
9
G
5
G
4
y
x
x
x
x
x
x
Krok
Stany linii układu
Komentarz
x
1
x
2
x
3
x
4
x
5
x
6
G
1
G
2
G
3
G
4
G
5
G
6
G
7
7
x
0
0
Zgodność na bramce
8
1
0
Zgodność na bramce
s-a-1
1
D
9
0
0
Zgodność na bramce
x
1
1
1
0
x
0
D
0
D
0
D
Test
0
D
D
1
D
1
D
0
0
D
D
4
(
)
G
1
( )
G
1
6
(
)
G
D
0
16
Złożoność D-algorytmu
Jeżeli od źródła błędu do obserwowalnego wyjścia układu prowadzi
n ścieżek, to wykonanie
D-algorytmu może, w najgorszym przypadku wymagać
podjęcia
2
n
-1 prób znalezienia poprawnych propagacji.
Liczba 2
n
-1 może być duża, szczególnie w układach zawierających wiele
rozgałęzień.
17
Przykład złożoności D-algorytmu
1
2
3
X
X
7
6/0
x
5
8
12
10
11
6
9
4
X
X
Y
0
0
D
Określenie typu błędu
Ustawienie stanu początkowego
Pobudzenie źródła błędu
Wybór ścieżki propagacji
Propagacja przez bramkę 9
D
0
D
Propagacja przez bramkę 12
0
0
0
D
D
0
Sprawdzenie zgodności dla bramki 10
1
D
0
1
Sprawdzenie zgodności dla bramki 11
0
1
0
0 G 1
sprzeczność dla ścieżki 6-9-12
18
Przykład złożoności D-algorytmu
1
2
3
X
X
7
6/0
x
5
8
12
10
11
6
9
4
X
X
Y
Propagacja błędu dwoma ścieżkami jednocześnie
0
0
D
Propagacja przez bramki 9 i 10
0
D
0
D
0
0
D
D
Propagacja przez bramkę 12
D
0
0
D
D
Sprawdzenie zgodności dla bramek 8 i 11
1
0
0
0
1
0
Sprawdzenie zgodności dla bramek 5 i 7
0
0
1
0
0
1
Błąd 6/0 ma tylko jeden test równy (0, 0, 0, 0)
19
Algorytm PODEM
(Path Oriented Decision Making)
1. Zarówno po pobudzeniu źródła błędu, jak też po każdym kroku propagacji
błędu wykonuje się badanie zgodności tego kroku z poprzednimi;
stosowana procedura “cofania się” wzdłuż ścieżki realizowana jest aż
do pierwotnych wejść układu.
2. Jeżeli badanie potwierdziło zgodność, to symuluje się działanie układu dla
wyznaczonego stanu jego wejścia, po to aby sprawdzić, czy błąd propaguje
się na obserwowalne wyjście układu, co oznacza, że utworzono poprawną
ścieżkę pobudzoną, a zatem znaleziono test rozpatrywanego błędu.
W algorytmie PODEM w porównaniu z D-algorytmem eliminuje się czysto
heurystyczny wybór ścieżek przez:
3. Badanie zgodności decyzji o wyborze pobudzonej ścieżki uzależnia się od
wielkości tzw. sterowalności poszczególnych linii układu.
20
Algorytm PODEM
Początek
Określ wykrywany błąd
Cofnij się wzdłuż wybranej ścieżki (przy jej wyborze posłuż się wartościami:
„najtrudniejszą” lub „najłatwiejszą”. Wykonaj procedurę badania zgodności
ustalonych warunków. Określ odpowiadające im pobudzenie wejść.
Symuluj pełny efekt pobudzenia określonego
przez procedurę badania zgodności
Zmień stan wejść
pierwotnych
Brak testu
1
2
Przyporządkuj stanom wszystkich linii układu wartość x
Punkt decyzyjny:= źródło błędu. Przypisz mu wartość D lub
D
21
Algorytm PODEM
Koniec
Pobudzono
źródło błędu
Tak
Nie
Utworzono ścieżkę
pobudzoną od
źródła błędu do
obserwowanego
wyjścia układu
Cofnij się do najbliższego
punktu decyzyjnego z
pobudzonym D lub
Wyznaczono
test
Tak
Nie
Określ najkrótszą ścieżkę do
obserwowanego wyjścia układu.
Wykonaj D propagację przez
pierwszą bramkę tej ścieżki
1
2
D
22
Przykład
x
6
G
7
G
3
x
1
x
2
x
3
x
4
x
5
G
2
G
8
G
6
G
1
G
9
G
5
G
4
y
Ocena sterowalności linii
Numer węzła
WO
j
X
1
0
X
2
0
X
3
0
X
4
0
X
5
0
G
1
2
G
2
2
G
3
0
G
4
0
Numer węzła
WO
j
G
5
0
G
6
0
G
7
0
G
8
0
G
9
0
WK
j
0
0
0
0
0
2
2
4
2
WK
j
4
2
8
4
4
23
Przykład
x
6
G
7
G
3
x
1
x
2
x
3
x
4
x
5
G
2
G
8
G
6
G
1
G
9
G
5
G
4
y
s-a-1
Krok
Stany linii układu
Komentarz
x
1
x
2
x
3
x
4
x
5
x
6
G
1
G
2
G
3
G
4
G
5
G
6
G
7
1
x
x
x
x
x
x
x
x
x
x
x
x
x
Stan początkowy
2
Źródło błędu G
2
/1
x
x
x
x
x
x
1
D
D
3
1
Cofanie się do X
4
(brak warunków
„najtrudniejszy” „najłatwiejszy”)
4
x
x
x
1
x
x
x
x
x
x
x
x
Symulacja pobudzenia źródła błędu
D
5
1
Określenie najkrótszej ścieżki do wyjścia.
Propagacja przez pierwszą bramkę tej ścieżki.
Sprawdzenie – wejście pierwotne.
D
D
D
1
1
6
x
x
x
1
1
x
x
x
x
x
x
Symulacja efektu pobudzenia
D
D
D
24
Przykład
x
6
G
7
G
3
x
1
x
2
x
3
x
4
x
5
G
2
G
8
G
6
G
1
G
9
G
5
G
4
y
s-a-1
Krok
Stany linii układu
Komentarz
x
1
x
2
x
3
x
4
x
5
x
6
G
1
G
2
G
3
G
4
G
5
G
6
G
7
7
Określenie najkrótszej ścieżki do wyjścia.
Propagacja przez pierwszą bramkę tej ścieżki.
x
x
x
x
x
x
1
D
8
Sprawdz. dla G
4
najłatwiejsze 0, W(X
1
)=0.
Wejście pierwotne.
D
1
1
11
0
x
0
1
1
x
Test
D
D
D
0
0
0
0
0
0
0
9
Sprawdz. dla G
5
najłatwiejsze 0, W(X
3
)=0.
Wejście pierwotne.
0
0
0
D
D
D
10
0
x
0
1
1
x
x
x
0
0
Symulacja efektu pobudzenia
25
Funkcje kosztu
Miary sterowalności
- które wskazują relatywną trudność (koszt) ustalenia pewnej
wartości (0 lub 1) na linii.
•
do wyboru zarówno najtrudniejszego ustawienia linii (powiedzmy,
ustalenia wartości
v
na wyjściu bramki G);
Zastosowanie:
•
do wyboru linii wejściowej bramki o stanie
x
spośród wielu linii,
która najłatwiej wysteruje wyjście bramki G do wartości
v
.
Miary obserwowalności
- które wskazują trudności (koszt) w propagacji błędu od danej
linii do linii wyjściowej układu.
do wybierania bramki spośród bramek należących do D-granicy,
której błąd na wejściu jest najłatwiej obserwowalny.
Zastosowanie:
26
Rekursywne funkcje kosztu
Dowolne funkcje kosztu określające sterowalność i obserwowalność powinny być
miarami relatywnymi tzn. umożliwiać ranking w ramach danego układu.
Inne zastosowanie miar sterowalności i obserwowalności to obliczenie miary
testowalności układu (systemu).
Miary sterowalności
Dla każdej linii L chcemy obliczyć dwie funkcje kosztu:
wskazujące relatywnie trudność ustawienia linii L w stanie 0 lub 1
odpowiednio.
0
( )
c L
i
1
( )
c L
27
Miary sterowalności
– przykład (bez rozgałęzień)
x
A
B
C
Załóżmy, że znamy wartości kosztu C
0
i C
1
dla każdej linii wejściowej.
Aby ustawić X = 0, wystarczy podać 0 na dowolną z linii wejściowych
bramki, zatem:
0
0
0
0
( )
{ ( ),
( ),
( )}
c x
min c A c B c C
=
Aby ustawić X = 1, wystarczy podać 1 na dowolną z linii wejściowych
bramki, zatem:
1
1
1
1
( )
( )
( )
( )
c x
c A
c B
c C
=
+
+
28
Miary sterowalności
– przykład (z rozgałęzieniami)
Funkcja kosztów, dla ustawienia X = 0 będzie równa:
0
0
0
( )
{ ( ),
( )}
c x
min c A c B
=
Funkcja kosztów, dla ustawienia X = 1 będzie równa :
1
1
1
( )
( )
( )
c x
c A
c B
=
+
29
Algorytm wyznaczania sterowalności układu
• Następnie funkcji kosztów C
1
i C
0
dla każdej bramki poziomu 1, potem
poziomu 2 itd.
• Algorytm kończy działanie, gdy zostanie określona funkcja kosztów dla
wszystkich linii układu.
• Nadanie wartości funkcjom kosztów C
1
i C
0
linii wejściowych układu.
30
Miary obserwowalności
O(L)
-
oznacza relatywną trudność propagacji błędu od linii L do wyjścia układu
(OW – obserwowalne wyjście).
Przykład (bez rozgałęzień)
x
A
B
C
Załóżmy, że znamy O(x).
Aby przepropagować błąd z linii A do x należy ustawić B i C na 1, co
pozwoli na przepropagowanie błędu z x do OW. Jeżeli te problemy (zadania) są
niezależne, otrzymujemy:
1
1
( )
( )
( )
( )
O A
c B
c C
O x
=
+
+