资源描述：
《4.1 - Symmetric Functions》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
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
