Rozšírený D-algoritmus - základné pojmy

Pri riešení sekvenčných obvodov je potrebné previesť riešenie sekvenčného obvodu na riešenie kombinačného obvodu. To sa realizuje rozpojením spätnej väzby v obvode. Pri tomto riešení je potrebné vytvárať interaktívne zapojenie viacerých takýchto modulov za sebou a v tomto zapojení potom existuje viacero porúch súčastne. Keďže klasický 5-hodnotový D-algoritmus nie je navrhnutý na riešenie niekoľkých porúch súčastne, bola navrhnutá jeho modifikácia nazvaná rozšírený D-algoritmus.

Základné pojmy

Základom rozšírenia je deväťhodnotový model šírenia signálu. Tieto hodnoty sú definované tiež ako usporiadaná dvojica správnej a poruchovej hodnoty.

hi

0

1

X

D

B

P

hs,hp

0, 0

1, 1

X, X

1, 0

0, 1

1, X

0, X

X, 1

X, 0

Tab. 6 Definícia 9-hodnotového modelu šírenia signálu v obvode

Ďalšie hodnoty boli zavedené, pretože šírenie signálu D v obvode okrem hodnôt 0, 1 umožňujú aj hodnoty D resp. .

Prenosové kocky

Prostriedkom pre vytvorenie citlivej cesty sú prenosové kocky, na rozdiel od klasického D-algoritmu, kde sú to premosové D-kocky. Získame ich kompozíciou primitívnych kociek s opačným výstupom.

Postup vytvárania prenosových kociek:

  1. Singulárne pokrytie rozdelíme na dve podmnožiny S0 a S1 podľa hodnoty výstupného signálu.
  2. Vyberáme kompozíciu všekých možných dvojíc primitívnych kociek tak, že jedna primitívna kocka je z množiny S0 a druhá z množiny S1.
  3. Postup v bode 2. opakujeme, ale prvú kocku vyberáme z množiny S1 a druhú s množiny S0.

Pre operáciu kompozície platí: Majme primitívnu kocku s1 = (a1, a2, ..., an) a s2 = (b1, b2, ..., bn). Operáciou kompozície pre s1 a s2 získame prenosovú kocku c = [(a1, b1), (a2, b2), ..., (an, bn)] = (c1, c2, ..., cn), kde dvojica (ai, bi) určuje hodnotu ci v rámci deväťhodnotového modelu šírenia signálu a i = 1, 2, ..., n.

Doplnkové kocky

Na rozdiel od D-algoritmu je zavedený pojem doplnková kocka, ktorá sa používa pri operácii konzistencie. Tieto kocky predstavujú rozšírenie singulárneho pokrytia o ďalšie kocky, ktoré dostaneme kompozíciou si a sx a tiež sx a si, kde si je primitívna kocka pokrytia a sx je plne neurčená primitívná kocka (X, X, ..., X). Pri určovaní kociek s výstupom P resp. , t. j. kompozícii sx a si, vychádzame zo singulárneho pokrytia zodpovedajúceho skutočnému stavu príslušného logického člena, t. j. ak je to člen s poruchou, použijeme singulárne pokrytie poruchového člena.

Primitívna kocka poruchy

Aj pri tejto verzii, podobne ako pri klasickom D-algoritme, je potrebné vytvoriť primitívnu kocku poruchy, ktorá sa používa v mieste poruchy. Pri jej definícii vychádzame zo singulárneho pokrytia zadaného logického člena bez poruchy a s uvažovanou poruchou. Primitívnu kocku poruchy získame kompozíciou ľubovoľnej primitívnej kocky singulárneho pokrytia bezporuchového logického člena a logického člena s poruchou s opačným výstupom, pričom na vstupe výslednej primitívnej kocky poruchy nesmie byť signál D resp. .

R-prienik

Obdobou D-prieniku je operácia R-prieniku, ktorá je definovaná takto:

hv = hi hi = (hsi, hpi) (hsj, hpj) = [(hsi hsj), (hpi hpj)] = ({hsi hsj}, {hpi hpj}) = ({hsv}, {hpv}) = (hsv, hpv).

Operácia R-prieniku medzi dvoma kockami robíme R-prienikom medzi zodpovedajúcimi súradnicami obidvoch kociek.