D-algoritmus - základné pojmy

D-algoritmus je jedna z metód, ktorou vieme vytvoriť citlivú cestu resp. viacero citlivých ciest naraz. Táto metóda bola nazvaná podľa signálu D použitého v nej, ktorý znamená, že pri poruche je na danom vodiči iná hodnota, ako v bezporuchovom stave. Tento signál sa šíri z miesta poruchy na výstup. Použitie tohto signálu vedie k 5-hodnotovému modelu šírenia signálu v obvode. Každá z hodnôt je definovaná ako usporiadaná dvojica správnej hs a poruchovej hp hodnoty. Hodnoty modelu sú v tabuľke 2.

Tabuľka 2: Definícia 5-hodnotového modelu šírenia signálu v obvode
hi 0 1 X D ¬D
hs,hp
0,0 1,1 X,X 1,0 0,1

Zavedieme si funkciu g(x1, x2, ..., xn, y), ktorá nadobúda hodnotu 1 práve vtedy, ak y = f(x1, x2, ..., xn). Prosté implikanty funkcie g zapísané v tabuľkovej forme tvoria singulárne pokrytie funkcie f. Jednotlivé implikanty singulárneho pokrytia predstavujú primitívne kocky si singulárneho pokrytia funkcie f.

Ako príklad uvediem logický člen NAND.

Mapa singularneho pokrytia log. clena NAND


Tabuľka 3: Singulárne pokrytie log. člena NAND
s\i 1 2 3
s1 1 1 0
s2 0 x 1
s3 x 0 1

Na formuláciu citlivej cesty zo vstupu logického člena na jeho výstup slúži prenosová D-kocka. Získame ju kombináciou dvoch primitívnych kociek s rôznou hodnotou výstupu, t.j. jedna má výstup 0 a druhá 1 a tak isto aspoň jedným vstupom, ktorý v jednej primitívnej kocke nadobúda hodnotu 0 a v druhej 1.Takto dostaneme na výstupe hodnotu D resp. ¬D a tiež aspoň na jenom vstupe.

Tabuľka 4: Prenosové D-kocky log. člena NAND
s\i 1 2 3
p1 D 1 ¬D
p2 1 D ¬D
p3 D D ¬D
p4 ¬D 1 D
p5 1 ¬D D
p6 ¬D ¬D D

Ako je vidieť v tabuľke, ku každej prenosovej kocke existuje jej inverzný variant, kde signály D sú nahradené ¬D a naopak. Prenosové kocky p1, p2, p4 a p5jednoduché prenosové D-kocky, pretože zodpovedajú existencii jednej citlivej cesty, p3 a p6viacnásobné prenosové D-kocky a zodpovedajú existencii viacero citlivých ciest cez daný logický člen. Vznik hodnoty D určuje primitívna D-kocka poruchy, ktorá udáva podmienky logického člena s poruchou, pri ktorých sa porucha prejaví zmenou správnej hodnoty 1 na 0 resp. naopak.

D-prienik

Realizácia D-prieniku sa robí podľa týchto pravidiel:
Tabuľka 5: Definícia D-prieniku
  0 1 x D ¬D
0 0 Ø 0 ND ND
1 Ø 1 1 ND ND
x 0 1 x D ¬D
D ND ND D ROV OP
¬D ND ND ¬D OP ROV

  1. Ak pri realizácii D-prieniku získame pre niektorú premennú výsledok Ø alebo ND, potom výsledný D-prienik obidvoch kociek neexistuje.
  2. Ak pri vytváraní D-prieniku dvoch kociek sa vyskytujú len znaky ROV a nevyskytujú sa znaky OP, potom platia ďalšie pravidlá D D-prienik D = D a ¬D D-prienik ¬D = ¬D.
  3. Ak pri vytváraní D-prieniku dvoch kociek sa vyskytujú len znaky OP a nevyskytujú sa znaky ROV, zmeníme v druhom operande všetky hodnoty ¬D na D a postupujeme podľa pravidla 2.
  4. Ak pri vytváraní D-prieniku dvoch kociek sa vyskytujú znaky OP a ROV súčastne, potom výsledný D-prienik neexistuje.

Ak výsledný prienik podľa pravidiel 1 a 4 potom je potrebné voliť iné prenosové kocky.