realizace funkce konkrétními hradly

[Marek Peca]

Ahoj,

> mohl by mi někdo ze znalých poradit stručně jak na to? Mám nějakou funkci,
> např. XOR (y='A x B + A x 'B) a tu chci zrealizovat hradly. Pokud nejsem
> omezen výběrem, tak nemám problém, postačí mi 2xNOT (invertor), 2xAND a
> 1xOR. Ale co když jsem zadáním omezen např. pouze na hradla NAND? Určitě je
> na to nějaký fígl a postup.
> Zkoušel jsem např. XOR zrealizovat tím co umím a pak jednotlivé (zakázané)
> prvky eliminovat nahrazením (třeba invertor nahradím NAND), ale hradla
> nabývají hodně rychle a k požadovanému výsledku se ani neblížím (jak třeba
> nahradím OR NANDem...). Prostě mě nenapadá žádný adekvátní postup - jedině
> matematicky tu funkci pozměnit/přepočítat abych dostal jen součiny a negace?

tohle ve skutecnosti zdaleka neni uplne snadna otazka -- jak to udelat, 
aby "hradel prilis nepribyvalo". Ba naopak, je to jeden z nejdulezitejsich 
a stale zivych problemu soucasnosti (logicka synteza).

Pokud staci, aby to danou fci plnilo a nemelo nutne optimalni nejake 
kriterium (napr. pocet hradel), pak to jde algoritmizovat snadno. Jak uz 
bylo psano v minule odpovedi, pro prevod mezi AND a OR plati de Morganuv 
zakon (je to vlastne konkretni pripad krasneho dualismu mezi pojmy 
"sjednoceni" a "prunik", doporucuji si tuto skutecnost vychutnat).

Dale, kazdou fci zadanou tabulkou lze napr. trivialne algoritmicky prevest 
na veliky OR malych ANDu (ci dualne velky OR malych ANDu). To pak lze opet 
rutinne rozsekat treba na ty NANDy. Ale to nezaruci, ze budete mit 
minimalni pocet prvku. A nebo minimalni zpozdeni, coz byva jindy castym 
kriteriem.

Pokud je zde nekdo, kdo o optimalizaci realizace log. fce vi vic a ma 
nejake pekne studijni materialy, rad se necham poucit. Krome z velike 
dalky videne diskretni optimalizace jsem nikdy nic podobneho nedelal.


ZdraviM.P.