On Circuits and Numbers
28
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
28
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Publié par
Langue
English
On Circuits and Numbers Jean E. Vuillemin Digital Equipment Corp., Paris Research Laboratory (PRL), 85 Av. Victor Hugo. 92563 Rueil-Malmaison, Cedex France. October 13, 1993 Abstract We establish new, yet intimate relationships between the 2adic integers 2 Z from arithmetics and digital circuits, finite and infinite, from electronics. (a) Rational numbers with an odd denominator correspond to output only synchronous circuits. (b) Bit-wise 2ading mappings correspond to combinational circuits. (c) On-line functions, 8n 2 N; x 2 2 Z : f(x) = f(x mod 2n) (mod 2n); correspond to synchronous circuits. (d) Continuous functions 2 Z 7! 2 Z, correspond to circuits with output enable. The proof is obtained by constructing synchronous decision diagrams SDD. They generalize to sequential circuits what classical BDD constructs achieve for combinational circuits. From simple identities over 2 Z, we derive both classical and new bit-serial circuits for computing: f+;;; 1=(1 + 2x);p1 + 8xg. The correctness of each circuit directly follows from the 2adic definition of the corresponding operator. All but the adders (+;) above are infinite.
Voir
- synchronous circuit
- bit
- adic integers
- digital circuit
- upon infinite
- output only
- global clock period
Publié par
Langue
English
On Circuits and Numbers
Jean E. Vuillemin
Digital Equipment Corp.,
Paris Research Laboratory (PRL),
85 Av. Victor Hugo.
92563 Rueil-Malmaison, Cedex France.
October 13, 1993
Abstract
We establish new, yet intimate relationships between the
2adic integers
Z
from arithmetics and
digital circuits
, finite and infinite, from electronics.
(a)
Rational numbers with an odd denominator correspond to output only
synchronous circuits.
(b)
Bit-wise 2ading mappings correspond to combinational circuits.
(c)
On-line functions,
N
Z
:
(
)
(
)
(mod
)
correspond to synchronous circuits.
(d)
Continuous functions
Z
Z
, correspond to circuits with output
enable.
The proof is obtained by constructing
synchronous decision diagrams
SDD.
They generalize to sequential circuits what classical BDD constructs achieve
for combinational circuits.
From simple identities over
Z
, we derive both classical and
new
bit-serial
circuits for computing:
+
(
+
)
+
. The
correctness
of
each circuit directly follows from the 2adic 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.
We indicate which features from this abstract 2adic semantics help syn-
thesize some of the largest synchronous hardware designs ever implemented,
through the 2Z language.
Keywords:
Synchronous, sequential, combinational circuit semantics and synthe-
sis. Bit-serial 2adic arithmetics, arbitrary precision. Periodic numbers. Bit-wise,
on-line, continuous functions. Enable, reset. Programmable Active Memories.
1
1
Introduction
Modern electronic circuits fall in two categories,
analog
and
digital
.
The dynamic analysis of analog circuits involves physical parameters, such as
currents and voltages, whose value
R
vary continuously with
real time
R
.
Carver Mead’s book [M89] provides an excellent introduction to analog circuits.
Digital circuits are characterized by a finite number of physical variables,
whose value
B
is identified with either zero or one through discretization:
say 0 when voltage
and 1 when voltage
.
Digital circuits may further be classified as
asynchronous
or
synchronous
. In
asynchronous circuits, communication of values between the constituting units
may occur at any real instant
R
.
Within synchronous circuits, all variables are sampled at integer multiples
(
∆
for
N
) of the same global clock period
∆
. Setting
∆
through a
suitable choice of the physical units thus allows to identify
digital time
N
with
the set of natural numbers.
The present work is exclusively concerned with synchronous circuits, which
we characterize mathematically as follows:
Definition 1 (Digital Synchronous Circuit)
In a synchronous circuit
, the value
of any variable
(
)
is a
bit
B
which may only change at
integer time
N
:
(
)
R
N
:
B
Here,
denotes the largest integer which is less than or equal to
.
A direct
consequence of definition 1 is that all delays in a digital circuit are
exact integers
. In
particular,
combinational
circuits have
zero delay
: the output response to changes
in the inputs is instantaneous; time plays no part in their mathematical analysis.
With
synchronous
(a. k. a. sequential) circuits, changes in the digital values of
variables are equally instantaneous; they precisely occur at digital times
N
.
Every physical implementation of such mathematical circuits has (hopefully very)
small delays, but (certainly) not zero delays.
As a consequence, the physical
behavior matches its mathematical idealization only when operated on with a
clock whose period
∆
exceeds the maximum physical delay
(
critical path
).
Synchronous circuits naturally operate upon
infinite
binary sequences: within
any computation performed by circuit
, each variable
(
) takes on
consecutive binary values
B
as digital time progresses through
the natural numbers
N
. Synchronous circuits map infinite binary sequences,
representing the successive input values at each clock tick
N
, into infinite
binary sequences, representing the corresponding output values.
2
