Associative Digital Network Theory Nico F. Benschop Associative Digital Network Theory An Associative Algebra Approach to Logic, Arithmetic and State Machines Dr.NicoF.Benschop AmspadeResearch Drossaardstraat71 5663GJGeldrop Netherlands E-mail:[email protected] ISBN 978-1-4020-9828-4 e-ISBN 978-1-4020-9829-1 DOI 10.1007/978-1-4020-9865-9 LibraryofCongressControlNumber:2008944293 ©SpringerScience+BusinessMediaB.V.2009 Nopartofthisworkmaybereproduced,storedinaretrievalsystem,ortransmittedinanyformorby anymeans,electronic,mechanical,photocopying,microfilming,recordingorotherwise,withoutwritten permissionfromthePublisher,withtheexceptionofanymaterialsuppliedspecificallyforthepurpose ofbeingenteredandexecutedonacomputersystem,forexclusiveusebythepurchaserofthework. Coverdesign:eStudioCalamarFigueres|Berlin Printedonacid-freepaper 9 8 7 6 5 4 3 2 1 springer.com ———————————————————————————– Tomyparents,forcaringandpersistingthroughhardtimes. Andtomywife,forherpatienceandunderstanding. ————————————o0O0o———————————— OldDutchsaying: —“Wiehetkleinenieteert,ishetgrotenietweerd.”— (Whodoesnothonorthesmall,doesnotdeservethelarge) Math=TheArtofseparatingNecessityfromCoincidence. Life = Makingthebestof Necessity, usingCoincidence. “Itjusthappenedthatno-oneelsewasfamiliarwithbothfields atthesametime.” (ClaudeShannononinter-disciplinarywork,1948) “ItalwaysworkedoutthatwhenIunderstoodsomething,itturnedouttobe simple.Taketheconnectionbetweenthequantumstuffandelectrodynamicsinmy book.Ittookmethirtyyearstofigureout,andintheenditwasalmosttrivial.It’s sosimplethatanyfreshmancouldreadandunderstandit.Butitwashardformeto getthere,withallthishistoricaljunkintheway.” (CarverMead:interviewAmericanSpectatorv34n7p68Sep.2001) “Mathematiciansopenedthegatetoanextensivedomain, but they did not enter this domain themselves. Bytheirnaturetheyaremoreinterestedintheway thegateisopened,thaninthegardenbehindit.” (MauritsEscherin“RegularDivisionofthePlane”,1958) — IftheWholeismorethanthesumofitsparts, — — thenthecouplingofpartsisthedifference. — H Logic aa = a / \ < + ^ * > Quint Essence C U Arithmetic ab = ba \ / L R Memory a(bc)=(ab)c=abc Preface This book is intended for researchers at industrial laboratories, teachers and stu- dents at technical universities, in electrical engineering, computer science and ap- pliedmathematicsdepartments,interestedinnewdevelopmentsofmodelingandde- signingdigitalnetworks(DN:statemachines,sequentialandcombinationallogic) in general, as a combined math/engineering discipline. As background an under- graduatelevelofmodernappliedalgebra1 willsuffice.Essentialconceptsandtheir engineeringinterpretationareintroducedinapracticalfashionwithexamples.The motivationinessenceis:theimportanceoftheunifyingassociativealgebraoffunc- tion composition (viz. semigroup theory) for the practical characterization of the threemainfunctionsincomputers,namelysequentiallogic(state-machines),arith- meticandcombinational(Boolean)logic. Knownprinciplesofdiscretemathematics,especiallyfinitesemigroups,residue arithmeticandbooleanlogic(lattices)areinterpretedintermsofpracticalDN de- sign issues. The main three levels of state machine synthesis form a natural ‘top down’hierarchyofassociativealgebras: Application Algebratype Syntax Objects Operations sequentiallogic associative (ab)c=a(bc) functions sequencing arithmetic commutative ab=ba numbers (+) (.) combinat’llogic idempotent aa=a sets ∪ ∩ Historically,non-commutativeandidempotentalgebrasdivergedfromarithmeticin the nineteenth century. Our aim is to emphasize again their arithmetic nature, for practicalengineeringpurposessuch as efficientsynthesis of binarylogicandstate machines.The‘static’(combinational,idempotentx2≡x)and‘iterative’(commu- tative,xi+1=xix=xxi)aspectscanbemodeledbyfiniteresiduearithmetic.Apart from the two non-commutative components of memory type (branch- and reset- machines, shown to be each others dual), non-commutative aspects of sequential behaviorcanberepresentedbycouplingfunctionsbetweencomponents. • In the first of three parts, on state machines (Chaps. 1–4), an introductory chapter recalls basic principles in theory and practice. The five basic components ofsequentialbehavior(withindecomposablesemigroup)arederived,withwaysto couple them efficiently—only required in the non-commutative case. They define thefivebasictypesofstatemachinesfornetworkcomposition. • In the second part, on combinational (Boolean) logic (Chaps. 5, 6) the con- ceptofspectrumasacharacteristicsequenceofnumbers,isborrowedfromFourier analysis for order-independent (symmetric) synthesis of Boolean functions (BFs). Ausefularithmeticcompositionalruleholds:thespectrumofaproductoffunctions (ofdisjointinputs)istheproductofthecomponentspectra.InfactBoole(1854)in- troduced his algebra—a calculus of binary properties—as an idempotent form of 1Birkhoff-Bartee1970—ModernAppliedAlgebra Hartmanis-Stearns1970—AlgebraicStructureofSequentialMachines. vii viii Preface arithmetic. This allows convolution-like composition rules (as in linear filters), to bedeveloped. SymmetricBFsareimplementedasacrossing-freeandcompactorthogonalgrid networkofMOStransistorsinthesiliconplane,toobtainaregularlystructuredVLSI implementation.SimplyremovingtransistorsfromsuchgridyieldsplanarBFswith thedesiredcrossing-freeproperty,coveringamajorityofBooleanfunctions.Using thisrepresentation,thecomplexityofBFsgrowspolynomial,andnotexponential, withthenumberofinputs.Itappearsthatbypermutingand/orinvertingtheninputs, eachBF ofatmostfourinputsisplanar. n AfastO(n2)algorithmforsymmetriclogicsynthesisisdeveloped,andapplied tooptimizefault-tolerantlogicusingHamming-orproduct-codesforerrorcorrec- tion,withsynthesizedgatecountascostcriterium. •Thethirdandlastpart,onarithmetic(Chaps.7–11),analysesresiduearithmetic withtwoextremaltypesofprimerelatedmoduli:pk andm =p p ···p typical k 1 2 k for ‘sequential’resp. ‘parallel’ arithmetic.By expandingr mod m residues witha ‘carry’ c as multiple of modulus m: n=cm+r, integer arithmetic obtains a dual focus on closure- and generative properties of residues and carry, as independent resp.dependentnetworkcomponents. This balanced approach to arithmetic provides new insights into old and well known problems in finite additive number theory (Fermat, Goldbach, Waring: Chaps. 8, 9, 10) with practical engineering results. For instance each odd residue mod2k isauniquesignedpowerof3,allowingefficientlog-arithmeticoverbases 2 and 3 [patent US-5923888]. Moreover, a binary log-arithmetic microprocessor (32bits,in0.18μCMOStechnology)isdescribed,designedaspartofaEuropean Esprit project,2 comparing favorably with the known floating point arithmetic de- vices. NicoF.Benschop ♠AmspadeResearch, Geldrop,TheNetherlands, Oct.2008. Acknowledgements TheauthorisgratefultoPhilipsResearch(Eindhoven,NL)forallowingtopublish this material, developed during his 32 years there. Also gratefully acknowledged arethecontributions,toChaps.6and11,ofcolleaguesRichardKleihorst,Renévan der Vleuten (Philips Research), G. Muurling, prof. J. Simonis (TU Delft), and of Esprit project co-workers Chris Softley, dr. Nick Coleman (Univ. Newcastle UK) andRudolfMatousek,prof.JiriKadlec(UTIA,Prague). 2Esprit33544HSLA,1999–2002,maincontractorUniv.Newcastle(dpt.ECE)UK. Contents Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Part1 SecuentialLogic:FiniteAssociative . . . . . . . . . . . . . . . . . 3 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 SequentialandCombinationalLogic . . . . . . . . . . . . . . . . 3 1.2 FiveBasicStateMachines,asNetworkComponents . . . . . . . . 5 1.3 Subset/Partition,Local/Global,Additive/Mult’ve . . . . . . . . . . 8 1.3.1 AssociativeClosure:SemigroupandSub-Semigroup . . . . 9 1.3.2 PreservedPartition:CongruenceandImage. . . . . . . . . 10 1.4 IntegerArithmetic:ResidueswithCarry . . . . . . . . . . . . . . 11 2 SimpleSemigroupsandtheFiveBasicMachines . . . . . . . . . . . 15 2.1 StateMachine:SequentialClosureandRank . . . . . . . . . . . . 15 2.2 BasicMachinesandSimpleSemigroups . . . . . . . . . . . . . . 16 2.2.1 Iterations:Monotone,Periodic,Idempotent . . . . . . . . . 17 2.2.2 OrderedIdempotentsH forCombinationalLogic . . . . . 18 2.2.3 TheFiveMinimalSemigroupsandBasicMachines . . . . 19 2.3 EquivalentIdempotents:MemoryComponentsL,R . . . . . . . . 20 2.4 MaximalSubgroups:PeriodicG . . . . . . . . . . . . . . . . . . 24 2.5 ConstantRankMachines,andSimpleSemigroups . . . . . . . . . 25 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3 CouplingStateMachines. . . . . . . . . . . . . . . . . . . . . . . . . 29 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2 NoCoupling:SemigroupZ(.)modm,Compositem . . . . . . . . 30 3.3 MachineDecomposition:RightCongruenceSuffices . . . . . . . . 34 3.4 CascadeComposition:FullGroupsFG andFG . . . . . . . . . 36 3 4 3.5 DecomposingtheFull-andAlternatingGroupoverFourStates . . 41 3.6 DecomposingSimpleGroupsAG ⊂FG forn>4 . . . . . . . . 44 n n 3.7 LoopCompositionSuperfluous . . . . . . . . . . . . . . . . . . . 48 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 ix x Contents 4 GeneralNetworkDecompositionofStateMachines . . . . . . . . . . 51 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.2 ImplementingM=(Q,A)byItsAlphabetA . . . . . . . . . . . 52 4.2.1 DecompositionbyLocalInputClosures . . . . . . . . . . 52 4.3 Bottom-UpRankDrivenDecompositionofS=A∗/Q . . . . . . 53 4.4 PartialDirectProducts,UnusedCodes,Efficiency . . . . . . . . . 53 4.5 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.5.1 Top-DownDecompositionbyLocalInputClosures . . . . 62 4.5.2 GlobalDecompositionbyMaximalIterativeComponents . 63 4.6 Invariants:OrderedCommutingIdempotents . . . . . . . . . . . . 65 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Part2 CombinationalLogic:CommutingIdempotents . . . . . . . . . . 69 5 SymmetricandPlanarBooleanLogicSynthesis . . . . . . . . . . . . 69 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.2 LogicSynthesisIndependentofInputOrdering . . . . . . . . . . . 70 5.2.1 OrthogridPlotandRankSpectrum . . . . . . . . . . . . . 70 5.2.2 FactoringPathsbyaPlanarNode . . . . . . . . . . . . . . 71 5.3 SymmetricandThresholdBF’s . . . . . . . . . . . . . . . . . . . 72 5.3.1 SymmetricFunctions‘Count’ . . . . . . . . . . . . . . . . 73 5.3.2 T-CellLibrary,ThresholdLogicCells . . . . . . . . . . . 74 5.4 PlanarCutandFactoring . . . . . . . . . . . . . . . . . . . . . . 74 5.5 FastSymmetricSynthesis:Quadraticinnr.Inputs . . . . . . . . . 75 5.6 ExperimentsandConclusion . . . . . . . . . . . . . . . . . . . . 75 5.7 PlanarBooleanLogicSynthesis . . . . . . . . . . . . . . . . . . . 76 5.7.1 AllBF ArePlanarupton=4Inputs . . . . . . . . . . . . 77 n References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 6 FaultTolerantLogicwithErrorCorrectingCodes . . . . . . . . . . 83 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.2 FaultTolerantICDesignEnvironment . . . . . . . . . . . . . . . 84 6.2.1 ImplementationatRegisterTransferLevel . . . . . . . . . 85 6.2.2 ProtectingRegistersandConnections . . . . . . . . . . . . 86 6.3 ThreeErrorCorrectionMethodsforLogicCircuits . . . . . . . . . 86 6.3.1 MajorityVoting . . . . . . . . . . . . . . . . . . . . . . . 87 6.3.2 HammingCodes(BlockCodes) . . . . . . . . . . . . . . . 87 6.3.3 ProductCodes(ArrayCodes) . . . . . . . . . . . . . . . . 87 6.4 DemonstrationofExperimentalCircuit . . . . . . . . . . . . . . . 88 6.5 ResultsforTypicalDesigns . . . . . . . . . . . . . . . . . . . . . 93 6.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Contents xi Part3 FiniteArithmetic:Associative,Commutative . . . . . . . . . . . . 97 7 Fermat’sSmallTheoremExtendedtorp−1modp3 . . . . . . . . . . 97 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 7.1.1 Divisorsr|p±1andResidues(p±1)p modp3 . . . . . . 99 7.2 LatticeStructureofSemigroupZ(.)modq . . . . . . . . . . . . . 99 7.2.1 Distinctep−1modp3 forIdempotentse∈Zp−1 . . . . . . 101 7.3 Distinctrp−1 modp3 forDivisorsr|p±1 . . . . . . . . . . . . . 103 7.3.1 IdempotentsofZp+1(.)andDivisorsofp+1 . . . . . . . 104 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 8 AdditiveStructureofUnitsGroupmodpk,withCarryExtension foraProofofFermat’sLastTheorem . . . . . . . . . . . . . . . . . 107 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 8.2 StructureoftheGroupG ofUnits . . . . . . . . . . . . . . . . . 109 k 8.3 CubicRootSolutioninCore,andCoreSymmetries . . . . . . . . 111 8.3.1 AnotherDerivationoftheCubicRootsof1modpk . . . . 111 8.3.2 Core Increment Symmetry mod p2k+1, Asymmetry modp3k+1 . . . . . . . . . . . . . . . . . . . . . . . . . . 113 8.4 SymmetriesasFunctionsYield‘Triplets’ . . . . . . . . . . . . . . 115 8.4.1 ATripletforEachUnitninG . . . . . . . . . . . . . . . 117 k 8.4.2 TheEDSArgumentExtendedtoNon-CoreTriplets . . . . 118 8.5 RelationtoFermat’sSmallandLastTheorem . . . . . . . . . . . 119 8.5.1 ProofoftheFLT Inequality . . . . . . . . . . . . . . . . . 120 8.6 ConclusionsandRemarks . . . . . . . . . . . . . . . . . . . . . . 121 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 9 AdditiveStructureofZ(.)modm (Squarefree)andGoldbach’s k Conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 9.2 LatticeofGroups . . . . . . . . . . . . . . . . . . . . . . . . . . 124 9.2.1 OrderingofCommutingIdempotents . . . . . . . . . . . . 125 9.2.2 LatticeofIdempotents:AddvsJoin . . . . . . . . . . . . . 125 9.3 Primes,CompositesandNeighbors . . . . . . . . . . . . . . . . . 126 9.3.1 EachIdempotent’sSuccessorisinG orG . . . . . . . . 127 1 2 9.4 EuclideanPrimeSieve . . . . . . . . . . . . . . . . . . . . . . . . 128 9.4.1 PairSumsofCarryExtendedUnits . . . . . . . . . . . . . 129 9.4.2 InductionBase:PairSumsofPrimesinG(3) . . . . . . . . 130 9.4.3 ExcludingCompositesin G(k), Baseprimesand1 as Summands . . . . . . . . . . . . . . . . . . . . . . . . . . 132 9.5 ProvingGCviaGR(k)byInductiononk . . . . . . . . . . . . . . 133 9.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 (cid:2) 10 Powersums xp Represent Residues mod pk, from Fermat toWaring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 xii Contents 10.2 CoreIncrementsasCosetGenerators . . . . . . . . . . . . . . . . 138 10.3 CoreExtensions:A toF ,andPairsumsmodpk . . . . . . . . . 140 k k 10.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 11 Log-Arithmetic,withSingleandDualBase . . . . . . . . . . . . . . 147 11.1 Log-ArithmeticwithDualBase2and3 . . . . . . . . . . . . . . . 147 11.1.1 ProposedNewBinaryNumberCode . . . . . . . . . . . 148 11.1.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . . 149 11.1.3 ApplicationtoMultipliers . . . . . . . . . . . . . . . . 149 11.1.4 SignedMagnitudeBinaryCodeoverBases2and3 . . . 150 11.1.5 AdditioninLogCode:‘Odd’Arithmetic(Base2and3). 151 11.2 EuropeanLogarithmicMicroprocessorELM . . . . . . . . . . . . 152 11.2.1 Introduction:Log-ArithmeticwithSingleBase2 . . . . 153 11.2.2 Log-ArithmeticAlgorithms,anOverview . . . . . . . . 155 11.2.3 DataFormat,RangeandPrecision . . . . . . . . . . . . 156 11.2.4 MeasurementofAccuracy . . . . . . . . . . . . . . . . 157 11.2.5 ConventionalLNSAdditionandSubtraction . . . . . . . 158 11.2.6 NewErrorCorrectionAlgorithm . . . . . . . . . . . . . 160 11.2.7 ErrorCorrectionforSubtraction . . . . . . . . . . . . . 163 11.2.8 Adder/SubtractorDesignandEvaluation . . . . . . . . . 163 11.2.9 ArchitectureandPerformance . . . . . . . . . . . . . . 165 11.2.10 VLSIImplementation . . . . . . . . . . . . . . . . . . . 166 11.2.11 TheELM:SomeMoreArchitecturalDetails . . . . . . . 167 11.2.12 AccuracyComparisonsLNSvs.FLP . . . . . . . . . . . 168 11.2.13 TheTMS-320C6711 . . . . . . . . . . . . . . . . . . . 170 11.2.14 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 171 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . 172 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179