Permalink copied!
Designing complex digital systems, such as computers, is an important
engineering activity. Digital systems are constructed by
interconnecting simple elements. Although the behavior of these
individual elements is simple, networks of them can have very complex
behavior. Computer simulation of proposed circuit designs is an
important tool used by digital systems engineers. In this section we
design a system for performing digital logic simulations. This system
typifies a kind of program called an
event-driven simulation, in
which actions (
events) trigger further events that happen at a later time, which in turn trigger more events, and so on.
Our computational model of a circuit will be composed of objects that
correspond to the elementary components from which the circuit is
constructed. There are
wires, which carry
digital signals. A digital signal may at any moment have only one of two
possible values,
0 and 1. There are also various types of digital
function boxes, which connect wires carrying input signals to other output
wires. Such boxes produce output signals computed from their input
signals. The output signal is
delayed by a time that depends on the
type of the function box. For example, an
inverter is a
primitive function box that inverts its input. If the
input signal to an inverter changes to 0, then one inverter-delay
later the inverter will change its output signal to 1. If the input
signal to an inverter changes to 1, then one inverter-delay later
the inverter will change its output signal to 0. We draw an inverter
symbolically as in figure 3.47. An
and-gate,
also shown in figure 3.47, is a primitive
function box with two inputs and one output. It drives its output signal
to a value that is the
logical and of the inputs. That is, if both
of its input signals become 1, then one and-gate-delay time
later the and-gate will force its output signal to be 1; otherwise the
output will be 0. An
or-gate is a similar two-input primitive function
box that drives its output signal to a value that is the
logical or of the inputs. That is, the output will become 1 if at least one
of the input signals is 1; otherwise the output will become 0.
Figure 3.47
Primitive functions in the digital logic simulator.
We can connect primitive functions together to construct more complex
functions. To accomplish this we wire the outputs of some
function boxes to the inputs of other function boxes. For example,
the
half-adder circuit shown in
figure 3.48 consists of an
or-gate, two and-gates, and an inverter. It takes two input signals,
$A$ and $B$, and has
two output signals, $S$ and $C$.
$S$ will become 1
whenever precisely one of $A$ and $B$
is 1, and $C$ will become 1 whenever
$A$ and $B$ are both 1. We can see
from the figure that, because of the
delays involved, the outputs may be generated at different times.
Many of the difficulties in the design of digital circuits arise from
this fact.
Figure 3.48
A half-adder circuit.
We will now build a program for modeling the digital logic circuits we
wish to study. The program will construct computational objects
modeling the wires, which will
holdthe signals. Function boxes will be modeled by functions that enforce the correct relationships among the signals.
One basic element of our simulation will be a
function
make_wire,
which constructs wires. For example, we can construct six wires as follows:
const a = make_wire(); const b = make_wire(); const c = make_wire(); const d = make_wire(); const e = make_wire(); const s = make_wire();
We attach a function box to a set of wires by calling a
function
that constructs that kind of box. The arguments to the constructor
function
are the wires to be attached to the box. For example, given
that we can construct and-gates, or-gates, and inverters, we can wire
together the half-adder shown in figure 3.48:
or_gate(a, b, d);
"ok"
and_gate(a, b, c);
"ok"
inverter(c, e);
"ok"
and_gate(d, e, s);
"ok"
Better yet, we can explicitly name this operation by defining a
function
half_adder
that constructs this circuit, given the four
external wires to be attached to the half-adder:
function half_adder(a, b, s, c) {
const d = make_wire();
const e = make_wire();
or_gate(a, b, d);
and_gate(a, b, c);
inverter(c, e);
and_gate(d, e, s);
return "ok";
}
The advantage of making this definition is that we can use
half_adder
itself as a building block in creating more complex
circuits. Figure 3.49, for example, shows a
full-adder composed of two half-adders and an or-gate.
[1]
We can construct a
full-adder as follows:
function full_adder(a, b, c_in, sum, c_out) {
const s = make_wire();
const c1 = make_wire();
const c2 = make_wire();
half_adder(b, c_in, s, c1);
half_adder(a, s, sum, c2);
or_gate(c1, c2, c_out);
return "ok";
}
Having defined
full_adder
as a
function,
we can now use it as a building block for creating still more complex
circuits. (For example, see exercise 3.30.)
Figure 3.49
A full-adder circuit.
In essence, our simulator provides us with the tools to construct a
language of circuits. If we adopt the general perspective on
languages with which we approached the study of
JavaScript
in section 1.1,
we can say that the primitive function boxes form the primitive
elements of the language, that wiring boxes together provides a means
of combination, and that specifying wiring patterns as
functions
serves as a means of abstraction.
The primitive function boxes
implement the
forcesby which a change in the signal on one wire influences the signals on other wires. To build function boxes, we use the following operations on wires:
-
get_signal($wire$)
returns the current value of the signal on the wire. -
set_signal($wire$, $new$-$value$):
changes the value of the signal on the wire to the new value. -
add_action($wire$, $function$-$of$-$no$-$arguments$):
asserts that the designated function should be run whenever the signal on the wire changes value. Such functions are the vehicles by which changes in the signal value on the wire are communicated to other wires.
Using these
functions,
we can define the primitive digital logic functions. To connect an input
to an output through an inverter, we use
add_action
to associate with the input wire a
function
that will be run whenever the signal on the input wire changes value.
The
function
computes the
logical_not
of the input signal, and then, after one
inverter_delay,
sets the output signal to be this new value:
function inverter(input, output) {
function invert_input() {
const new_value = logical_not(get_signal(input));
after_delay(inverter_delay,
() => set_signal(output, new_value));
}
add_action(input, invert_input);
return "ok";
}
function logical_not(s) {
return s === 0
? 1
: s === 1
? 0
: error(s, "invalid signal");
}
An and-gate is a little more complex. The action
function
must be run if
either of the inputs to the gate changes. It computes the
logical_and
(using a function analogous to
logical_not)
of the values of the signals on the input wires and sets up a change
to the new value to occur on the output wire after one
and_gate_delay.
function and_gate(a1, a2, output) {
function and_action_function() {
const new_value = logical_and(get_signal(a1),
get_signal(a2));
after_delay(and_gate_delay,
() => set_signal(output, new_value));
}
add_action(a1, and_action_function);
add_action(a2, and_action_function);
return "ok";
}
Define an
or-gate as a primitive function box. Your
or_gate
constructor should be similar to
and_gate.
// contributed by GitHub user clean99
function logical_or(s1, s2) {
return s1 === 0 && s2 === 0
? 0
: s1 === 0 || s1 === 1
? s2 === 0 || s2 === 1
? 1
: error(s2, "invalid signal")
: error(s1, "invalid signal");
}
// contributed by GitHub user clean99
function or_gate(a1, a2, output) {
function or_action_function() {
const new_value = logical_or(get_signal(a1),
get_signal(a2));
after_delay(or_gate_delay,
() => set_signal(output, new_value));
}
add_action(a1, or_action_function);
add_action(a2, or_action_function);
return "ok";
}
Another way to construct an
or-gate is as a compound digital logic
device, built from and-gates and inverters. Define a
function
or_gate
that accomplishes this. What is the delay time of the
or-gate in terms of
and_gate_delay
and
inverter_delay?
(contributed by github user taimoon)
Idea: ~(~a & ~b) = nand(~a, ~b) = ~~a | ~~b = a | b
function nand_gate(a1, a2, out){
const tmp = make_wire();
and_gate(a1, a2, tmp);
inverter(tmp, out);
}
function or_gate(a1, a2, out){
const not_a1 = make_wire();
const not_a2 = make_wire();
inverter(a1, not_a1);
inverter(a2, not_a2);
nand_gate(not_a1, not_a2, out);
}
The delay time of the nand-gate is
nand_gate_delay = and_gate_delay + inverter_delay and the delay time of the or-gate above is
or_gate_delay = nand_gate_delay + inverter_delay = and_gate_delay + 2 * inverter_delay.
Figure 3.50 shows a
ripple-carry adder formed by stringing
together $n$ full-adders.
This is the simplest form of parallel adder
for adding two $n$-bit binary numbers.
The inputs $A_{1}$,
$A_{2}$,
$A_{3}$, …,
$A_{n}$ and
$B_{1}$,
$B_{2}$,
$B_{3}$, …,
$B_{n}$
are the two binary numbers to be added (each
$A_{k}$ and
$B_{k}$
is a 0 or a 1). The circuit generates
$S_{1}$,
$S_{2}$,
$S_{3}$,
…,
$S_{n}$,
the $n$ bits of the sum, and
$C$, the carry from
the addition. Write a
function
ripple_carry_adder
that generates this circuit. The
function
should take as arguments three lists of
$n$ wires each—the
$A_{k}$, the
$B_{k}$, and the
$S_{k}$—and
also another wire $C$.
The major drawback of the ripple-carry adder is the need to wait for the
carry signals to propagate. What is the delay needed to obtain the
complete output from an $n$-bit ripple-carry
adder, expressed in terms of the delays for and-gates, or-gates, and
inverters?
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Figure 3.50
A ripple-carry adder for $n$-bit numbers.
A wire
in our simulation will be a computational object with two local
state variables:
a signal_value
(initially taken to be 0) and a collection of
action_functions
to be run when the signal changes value. We implement the wire,
using
message-passing style, as
a collection of local
functions
together with a dispatch
function
that selects the appropriate local operation, just as we did
with the simple bank-account object in section
3.1.1:
function make_wire() {
let signal_value = 0;
let action_functions = null;
function set_my_signal(new_value) {
if (signal_value !== new_value) {
signal_value = new_value;
return call_each(action_functions);
} else {
return "done";
}
}
function accept_action_function(fun) {
action_functions = pair(fun, action_functions);
fun();
}
function dispatch(m) {
return m === "get_signal"
? signal_value
: m === "set_signal"
? set_my_signal
: m === "add_action"
? accept_action_function
: error(m, "unknown operation -- wire");
}
return dispatch;
}
The local
function
set_my_signal
tests whether the new signal value changes the signal on the wire.
If so, it runs each of the action
functions,
using the following
function
call_each,
which calls each of the items in a list of no-argument
functions:
function call_each(functions) {
if (is_null(functions)) {
return "done";
} else {
head(functions)();
return call_each(tail(functions));
}
}
With the local dispatch
function
set up as specified, we can
provide the following
functions
to access the local operations on
wires:
[2]
function get_signal(wire) {
return wire("get_signal");
}
function set_signal(wire, new_value) {
return wire("set_signal")(new_value);
}
function add_action(wire, action_function) {
return wire("add_action")(action_function);
}
Wires, which have time-varying signals and may be incrementally attached to
devices, are typical of mutable objects. We have modeled them as
functions
with local state variables that are modified by assignment. When a new
wire is created, a new set of state variables is allocated (by the
let statements in
make_wire)
and a new dispatch
function
is constructed and returned, capturing
the environment with the new state variables.
The wires are shared among the various devices that have been
connected to them. Thus, a change made by an interaction with one
device will affect all the other devices attached to the wire. The
wire communicates the change to its neighbors by calling the action
functions
provided to it when the connections were established.
The only thing needed to complete the simulator is
after_delay.
The idea here is that we maintain a data structure, called an
agenda, that contains a schedule of things to do.
The following operations are defined for agendas:
-
make_agenda():
returns a new empty agenda. -
is_empty_agenda($agenda$)
is true if the specified agenda is empty. -
first_agenda_item($agenda$)
returns the first item on the agenda. -
remove_first_agenda_item($agenda$)
modifies the agenda by removing the first item. -
add_to_agenda($time$, $action$, $agenda$)
modifies the agenda by adding the given action function to be run at the specified time. -
current_time($agenda$)
returns the current simulation time.
The particular agenda that we use is denoted by
the_agenda.
The
function
after_delay
adds new elements to
the_agenda:
function after_delay(delay, action) {
add_to_agenda(delay + current_time(the_agenda),
action,
the_agenda);
}
The simulation is driven by the function
propagate, which executes each
function on
the_agenda
in sequence.
In general, as the simulation runs, new items
will be added to the agenda, and propagate
will continue the simulation as long as there are items on the agenda:
function propagate() {
if (is_empty_agenda(the_agenda)) {
return "done";
} else {
const first_item = first_agenda_item(the_agenda);
first_item();
remove_first_agenda_item(the_agenda);
return propagate();
}
}
The following
function,
which places a
probeon a wire, shows the simulator in action. The probe tells the wire that, whenever its signal changes value, it should print the new signal value, together with the current time and a name that identifies the wire.
function probe(name, wire) {
add_action(wire,
() => display(name + " " +
stringify(current_time(the_agenda)) +
", new value = " +
stringify(get_signal(wire))));
}
We begin by initializing the agenda and specifying delays for the
primitive function boxes:
const the_agenda = make_agenda(); const inverter_delay = 2; const and_gate_delay = 3; const or_gate_delay = 5;
Now we define four wires, placing probes on two of them:
const input_1 = make_wire();
const input_2 = make_wire();
const sum = make_wire();
const carry = make_wire();
probe("sum", sum);
"sum 0, new value = 0"
probe("carry", carry);
"carry 0, new value = 0"
Next we connect the wires in a half-adder circuit (as in
figure 3.48), set the signal on
input_1
to 1, and run the simulation:
half_adder(input_1, input_2, sum, carry);
"ok"
set_signal(input_1, 1);
"done"
propagate();
"sum 8, new value = 1" "done"
The sum signal changes to 1 at time 8.
We are now eight time units from the beginning of the simulation.
At this point, we can set the signal on
input_2
to 1 and allow the values to propagate:
set_signal(input_2, 1);
"done"
propagate();
"carry 11, new value = 1" "sum 16, new value = 0" "done"
The carry changes to 1 at time 11 and the
sum changes to 0 at time 16.
The internal
function
accept_action_function
defined in
make_wire
specifies that when a new action
function
is added to
a wire, the
function
is immediately run. Explain why this initialization
is necessary. In particular, trace through the half-adder example in
the paragraphs above and say how the system's response would differ
if we had defined
accept_action_function
as
function accept_action_function(fun) {
action_functions = pair(fun, action_functions);
}There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Finally, we give details of the agenda data structure, which holds the
functions
that are scheduled for future execution.
The agenda is made up of
time segments. Each time segment is a
pair consisting of a number (the time) and a
queue (see
exercise 3.32) that holds the
functions
that are scheduled to be run during that time segment.
function make_time_segment(time, queue) {
return pair(time, queue);
}
function segment_time(s) { return head(s); }
function segment_queue(s) { return tail(s); }
The agenda itself is a one-dimensional
table of time segments. It
differs from the tables described in section 3.3.3
in that the segments will be sorted in order of increasing time. In
addition, we store the
current time (i.e., the time of the last action
that was processed) at the head of the agenda. A newly constructed
agenda has no time segments and has a current time of 0:
[3]
function make_agenda() { return list(0); }
function current_time(agenda) { return head(agenda); }
function set_current_time(agenda, time) {
set_head(agenda, time);
}
function segments(agenda) { return tail(agenda); }
function set_segments(agenda, segs) {
set_tail(agenda, segs);
}
function first_segment(agenda) { return head(segments(agenda)); }
function rest_segments(agenda) { return tail(segments(agenda)); }
An agenda is empty if it has no time segments:
function is_empty_agenda(agenda) {
return is_null(segments(agenda));
}
To add an action to an agenda, we first check if the agenda is empty.
If so, we create a time segment for the action and install this in
the agenda. Otherwise, we scan the agenda, examining the time of each
segment. If we find a segment for our appointed time, we add the
action to the associated queue. If we reach a time later than the one
to which we are appointed, we insert a new time segment into the
agenda just before it. If we reach the end of the agenda, we must
create a new time segment at the end.
function add_to_agenda(time, action, agenda) {
function belongs_before(segs) {
return is_null(segs) || time < segment_time(head(segs));
}
function make_new_time_segment(time, action) {
const q = make_queue();
insert_queue(q, action);
return make_time_segment(time, q);
}
function add_to_segments(segs) {
if (segment_time(head(segs)) === time) {
insert_queue(segment_queue(head(segs)), action);
} else {
const rest = tail(segs);
if (belongs_before(rest)) {
set_tail(segs, pair(make_new_time_segment(time, action),
tail(segs)));
} else {
add_to_segments(rest);
}
}
}
const segs = segments(agenda);
if (belongs_before(segs)) {
set_segments(agenda,
pair(make_new_time_segment(time, action), segs));
} else {
add_to_segments(segs);
}
}
The
function
that removes the first item from the agenda deletes the
item at the front of the queue in the first time segment. If this
deletion makes the time segment empty, we remove it from the list of
segments:
[4]
function remove_first_agenda_item(agenda) {
const q = segment_queue(first_segment(agenda));
delete_queue(q);
if (is_empty_queue(q)) {
set_segments(agenda, rest_segments(agenda));
} else {}
}
The first agenda item is found at the head of the queue in the first
time segment. Whenever we extract an item, we also update the current
time:
[5]
function first_agenda_item(agenda) {
if (is_empty_agenda(agenda)) {
error("agenda is empty -- first_agenda_item");
} else {
const first_seg = first_segment(agenda);
set_current_time(agenda, segment_time(first_seg));
return front_queue(segment_queue(first_seg));
}
}
The
functions
to be run during each time segment of the agenda are kept in a queue.
Thus, the
functions
for each segment are called in the order in which they were added to the
agenda (first in, first out). Explain why this order must be used. In
particular, trace the behavior of an and-gate whose inputs change from
0,1 to 1,0 in the same segment and say how the behavior would differ if
we stored a segment's
functions
in an ordinary list, adding and removing
functions
only at the front (last in, first out).
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
[1]
A
full-adder is a basic circuit element used in adding two binary
numbers. Here $A$ and $B$
are the bits at corresponding positions in the
two numbers to be added, and $C_{\mathit{in}}$ is the
carry bit from the addition one place to the right. The circuit generates
$\mathit{SUM}$, which is the sum bit in the corresponding position, and
$C_{\mathit{out}}$, which is the
carry bit to be propagated to the left.
[2]
These
functions
are simply syntactic sugar that allow
us to use ordinary
functional
syntax to access the local
functions
of objects. It is striking that we can interchange the role of
functionsand
datain such a simple way. For example, if we write wire("get_signal") we think of wire as a function that is called with the message "get_signal" as input. Alternatively, writing get_signal(wire) encourages us to think of wire as a data object that is the input to a function get_signal. The truth of the matter is that, in a language in which we can deal with functions as objects, there is no fundamental difference between
functionsand
data,and we can choose our syntactic sugar to allow us to program in whatever style we choose.
[4]
Observe that the
conditional statement in this
function has an
empty block as its alternative statement.
Such a
one-armed conditional statementis used to decide whether to do something, rather than to select between two statements.
[5]
In this way, the current time will always be the time
of the action most recently processed. Storing this time at the head
of the agenda ensures that it will still be available even if the
associated time segment has been deleted.
3.3.4
A Simulator for Digital Circuits