On circuits and numbers
Author:
- J.E. VuilleminJVJ.E. Vuillemin
- 1 January 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 43 (8) , 868-879
Abstract
We establish new, yet intimate relationships between the 2-adic integers /sub 2/Z from arithmetics and digital circuits, both finite and infinite, from electronics. 1) Rational numbers with an odd denominator correspond to output only synchronous circuits. 2) Bit-wise 2-adic mappings correspond to combinational circuits. 3) Online functions /spl forall/n/spl isin/N,x/spl isinsub 2/Z:f(x)=f(xmodd2/sup n/)mod2/sup n/), correspond to synchronous circuits. 3) Continuous functions, /sub 2/Z/spl rarrsub 2/Z, correspond to circuits with output enable. The proof is obtained by constructing synchronous decision diagrams SDDs. They generalize to sequential circuits as classical BDD constructs do for combinational circuits. From simple identities over /sub 2/Z, we derive both classical and new bit-serial circuits for computing: {+,-,/spl times/,1/(1-2x), (1+8x)}. The correctness of each circuit directly follows from the 2-adic definition of the corresponding operator. All but the adders (+,-) above are infinite. Yet the use of reset signals reduces all previously infinite operators to finite circuits. The present work lays out the semantic basis of a new language for describing synchronous circuits. Language 2Z incorporates arithmetic synthesis for some of the above bit-serial operators, and for periodic binary constants (logic from chronograms). It also provides for the powerful deeply binding synchronous enable and reset operators, whose meaning is discussed.Keywords
This publication has 10 references indexed in Scilit:
- Programmable active memories: a performance assessment1993
- A hardware implementation of pure ESTERELSādhanā, 1992
- Retiming synchronous circuitryAlgorithmica, 1991
- Analog VLSI Implementation of Neural Systems1989
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986
- A very fast multiplication algorithm for VLSI implementationIntegration, 1983
- An 0(n) Parallel Multiplier with Bit-Sequential Input and OutputIEEE Transactions on Computers, 1979
- Binary Decision DiagramsIEEE Transactions on Computers, 1978
- p-adic Numbers, p-adic Analysis, and Zeta-Functions1977
- Two's Complement Pipeline MultipliersIEEE Transactions on Communications, 1976