資源描述：
《4.1 - Symmetric Functions》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、Section4.1SwitchingAlgebraSymmetricFunctionsAlfredoBensoPolitecnicodiTorino,ItalyAlfredo.benso@polito.itSymmetricFunctions?Afunctioninwhicheachinputvariableplaysthesameroleindeterminingthevalueofthefunction.?Examples:–majorityfunction:itis‘1’onlywhenmor
2、ethanhalfoftheinputsare‘1’.Itisthe“carry”functioninthebinaryadditionandthe“voter”functionusedinfaulttolerantcomputing;–(odd)parityfunction:is‘1’onlyifanoddnumberofinputsare‘1’.Itisthe“sum”functionforbinaryadditionanditisusedindetectingorcorrectingcodeci
3、rcuits.1SymmetricFunctions?Symmetricfunctionscanbesynthesizedwithfewerlogicelements?DetectionofsymmetryisanimportantandHARDprobleminCAD?ThereareseveraltypesofsymmetryTotallySymmetricFunctionsDefinition?Afunctionf(x1,x2,........,xn)istotallysymmetriciffi
4、tisunchangedbyanypermutationofitsvariables.?Examples:–F=xy+xz+yz(majorityfunction)–F=x’y+xy’(parityfunction,exor)Theorem:?f(x1,x2,........,xn)istotallysymmetriciffitcanbespecifiedbystatingalistofintegersA={a1,a2,........,am},0=aj=nsothatf=1iffexactlyajo
5、fthevariablesare1?{a1,a2,........,am}arecalleda-numbers?SAisthesymbolusedtoindicateaSymmetricFunction.2a-numberExample?ConsiderthefunctionS1(x,y,z)?Thenthisfunctionhasasinglea-number=1?Thetruthtableis:xyzf00000011010101101001101011001110Anothera-numberE
6、xample?ConsiderthefunctionS0,2(x,y,z)?Thenthisfunctionhastwoa-numbers,0&2?Thetruthtableis:xyzf000100100100011110001011110111103Problem?WritethetruthtableofS1,2(x,y,z)xyzf00000011010101111001101111011110MixedSymmetricFunctionsDefinition?Afunctionf(x1,x2,
7、........,xn)ismixedsymmetriciffitisnottotallysymmetric,butitcanbechangedintototallysymmetricbyreplacingsomeofitsvariablesbytheircomplements.?AmixedsymmetricfunctionisrepresentedbythesymbolSA(x,y’,z’)whereyandzarethevariablestobecomplemented?Examples:–F=
8、xy’z’isnottotallysymmetric,butxyzistotallysymmetric,thereforeFismixedsymmetric4PartiallySymmetricFunctions?Afunctionf(x1,x2,........,xn)willbecalledsymmetricifitiseithertotallyormixedsymmetric?Therearefunctionsthatareunchangedwhe
