算术电路部分综合的代数方法.pdf

1、An Algebraic Approach to Partial Synthesis of Arithmetic CircuitsBhavani Sampathkumar,Ritaja Das,Bailey Martin,Florian Enescu,Priyank Kalla Presenter:Priyank Kalla ProfessorElectrical&Computer Engineeringhttp:/www.ece.utah.edu/kallaIntroductionIntroduction to the Problem of Partial Logic SynthesisOu

2、r focus:Integer Arithmetic CircuitsOur approach uses a computer algebra modelPolynomial modeling of arithmetic circuitsIdeals,varieties and Grbner bases(Buchbergers algorithm)Verification and synthesis techniquesExperimental resultsConclusions and Future WorkThe Foundation of our WorkArithmetic Circ

3、uits:Functions over-bit vectors:-bit vectors functions not efficient for arithmetic circuitsModel the circuit as polynomials over the quotient ring Algebraic Geometry results are valid over fieldsIntegers Impose Boolean idempotency at a polynomial levelRepresent circuits using polynomial ideals,whos

4、e(zeros)varieties are the functions implemented by the circuitsAlgorithms make use of ideal membership using Grbner basesGo from polynomial ideals to Boolean functions,and employ conventional logic synthesis tools for optimizing circuitskkf:k kR=x1,xnx21 x1,x2n xn rationalsx2i xi:Partial Logic Synth

5、esisGiven a Spec polynomial,along with a partially completed circuit.Does there exist a function at some internal net of the circuit,s.t.matches the Spec?f(x1,xn)R=x1,nx21 x1,x2n xnCUCfAn Algebraic Approach to Partial Synthesis of ArithmeticCircuitsABSTRACTWe present an approach to partial logic syn

6、thesis of arithmetic cir-cuits.Its targeted applications are rectifcation of buggy circuits,and computing care and dont care sets at internal nets of the cir-cuit.The approach models the circuit by way of polynomial idealsin rings with coefcients in the feld of rationals(Q).Techniquesfrom commutativ