Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

DigitalAlgebraandCircuitsJeanVuilleminEcoleNormaleSupe´rieure,45rued’Ulm,75005ParisFrance.Abstract.DigitalnumbersDaretheworld’smostpopulardatarep-resentation:nearlyalltexts,soundsandimagesarecodedsomewhereintimeandspacebybinarysequences.Themathematicalconstructionofthefixed-pointD'Z2andfloating-pointD0'Q2digitalnumbersisadualtotheclassicalconstructionsoftherealnumbersR.ThedomainD0containsthebinaryintegersNandZ,aswellasQ.ThearithmeticoperationsinD0aretheusualoneswhenrestrictedtointegersorrationalnumbers.Similarly,thepolynomialoperationsinD0aretheusualoneswhenappliedtofinitebinarypolynomialsF2[z]ortheirquotientsF2(z).Finally,thesetoperationsinD0aretheusualonesoverfiniteorinfinitesubsetsofN.Theresultingalgebraicstructureisrich,andweidentifyoveradozenrings,fieldsandBooleanalgebrasinD0.Eachstructureiswell-knowninitsownright.TheuniquenatureofD0istocombineallintoasinglealgebraicstructure,whereoperationsofdifferentnaturehappilymix.Thetwo’scomplementformulax=1+¬xisanexample.Digitalalgebraisconcernedwiththerelationsbetweenadozenoperators.Digitalsynchronouscircuitsarebuiltfromasimplesubsetoftheseoperators:threeBooleangatesandtheunit-delayz.DigitalanalysisissimplerandmoreintuitivethananalysisinR.ThecomputabledigitalfunctionsD7→Darecontinuous:eachoutputbitdependsuponfinitelymanyinputbits.Infinitecircuitscomputecausalfunctions:presentoutputdependsuponpastinputs.SequentialfunctionsareequivalentlycomputedbyFSMandbyfinitecircuits.Theν-transformisaninfinitebinarytruth-tableforcausalfunctions.Theν-transformprovidesanaturalone-to-onecorrespondencebetweenalgebraicdigitalnumbersandsequentialfunctions.Questionsaboutse-quentialfunctionsaretransformedbyνintoquestionsaboutalgebraicdigitalnumbers,wherethewholeofdigitalalgebraapplies.AnalgebraicdigitalnumberisfinitelyrepresentedbyauniqueminimalregularbinarytreeRBT.TheinversetransformoftheRBTisthemini-maldeterministicFSMforcomputingthe(reversed)sequentialfunction.Analgebraicdigitalnumberisfinitelyrepresentedbyauniqueminimalup-polynomialMUPofwhichitisroot.TheMUPissmallerthantheRBT.ItisexponentiallysmallerthantheminimaldeterministicFSMforashift-registercircuit.Thenet-listofacircuitistransformedbyνintotheisomorphictruth-list:asystemofequationsoveralgebraicnumbers.Circuitexamplesshowhowthetruth-listiscasttonormalform-eitherRBTorMUP-throughasequenceofsimpleidentitiesfromdigitalalgebra.ThiscontributionisdedicatedtoZoharMannaonhis64-thbirthday.
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin