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

=

+

+