CS 22
Clab 24: Event-driven Circuit Simulation
Last clab, we looked at the details of the agenda and wire construction
used in sicp's event-driven simulation code. We ended by creating and exercising
an inverter. You were were supposed to finish the and-gate and test it, construct
an or-gate two different ways and test them.
Here is a logical-and function to complete the and-gate and a primitive or-gate
as asked for in ex 3.28.
<![CDATA[
(define (logical-and s t)
(cond
((and (= s 1) (= t 1)) 1)
((and (or (= s 0) (= s 1)) (or (= t 0) (= t 1))) 0)
(else (error "invalid signal to logand " s t))))
;;; possible solution to ex 3.28
(define (logical-or s t)
(cond
((and (= s 0) (= t 0)) 0)
((and (or (= s 0) (= s 1)) (or (= t 0) (= t 1))) 1)
(else (error "invalid signal to logor " s t))))
(define (or-gate in1 in2 output)
(define (or-action)
(let ((newval (logical-or (get-signal in1) (get-signal in2))))
(after-delay or-gate-delay
(lambda ()
(set-signal! output newval)))))
(add-action! in1 or-action)
(add-action! in2 or-action)
'ok)
(define or-gate-delay 5)
]]>
I checked this out using probes and it works for all four legal inputs.
We will need a working or-gate in what follows. Use this if you are not
sure yours is correct.
Before we go on let's do ex 3.29 which asks us to construct an or by
designing a circuit from and-gates and inverters. We will do this
using a version of DeMorgan's law. One version of DeMorgan's law
says: not(a or b) = (not a) and (not b). Taking the not of both sides
we get (a or b) = not( (not a) and (not b) ). So we will realize this as
a circuit.
<![CDATA[
;;; some testing code
(define the-agenda (make-agenda))
(define ain (make-wire))
(define bin (make-wire))
(define cout (make-wire))
(probe 'ain ain)
(probe 'bin bin)
(probe 'cout cout)
;;; one solution to ex 3.29
(define (or-ckt in1 in2 output)
(let
((intw1 (make-wire))
(intw2 (make-wire))
(intw3 (make-wire)))
(probe 'intw1 intw1) ;;; probes to watch action
(probe 'intw2 intw2)
(probe 'intw3 intw3)
(inverter in1 intw1)
(inverter in2 intw2)
(and-gate intw1 intw2 intw3)
(inverter intw3 output)))
]]>
We'll talk about the output you get from a couple of tests like:
<![CDATA[
(or-ckt ain bin cout)
(get-signal ain)
(get-signal bin)
(get-signal cout) ;; seems ok for default inputs of 0 0
(set-signal! ain 1) ;; give input 1 0
(propagate)
(get-signal cout) ;; checks input 1 0
(set-signal! bin 1) ;; give input 1 1
(propagate)
(get-signal cout) ;; checks input 1 1
the-agenda
(set-signal! ain 0) ;; give input 0 1
(propagate)
(get-signal cout) ;; checks input 0 1
the-agenda
]]>
Notice that you should not count on an output being accurate until the
end of the time block at which it is expected. Transitory values
may occur before the end of that time block.
Now define the halfadder and fulladder as on pp. 275-276.
<![CDATA[
(define (half-adder a b s c)
(let ((d (make-wire)) (e (make-wire)))
(or-gate a b d)
(and-gate a b c)
(inverter c e)
(and-gate d e s)
'ok))
(define (full-adder a b c-in sum c-out)
(let ((s (make-wire))
(c1 (make-wire))
(c2 (make-wire)))
(half-adder b c-in s c1)
(half-adder a s sum c2)
(or-gate c1 c2 c-out)
'ok))
(define sumout (make-wire))
(probe 'sumout sumout)
]]>
We can test the half-adder as follows:
<![CDATA[
> (half-adder ain bin sumout cout)
ok
> (set-signal! ain 1)
ain 0 New-value = 1
done
> (propagate)
sumout 8 New-value = 1
done
> (set-signal! bin 1)
bin 8 New-value = 1
done
> (propagate)
cout 11 New-value = 1
sumout 16 New-value = 0
done
]]>
It is a bit tedious to test these circuits. There are four
different input combinations to be tested for the half-adder
and 8 combinations for the full-adder and these are just for
one bit position.
So I wrote a tester:
<![CDATA[
(define (fulladdtes bit1 bit2 carin)
(let (
(a (make-wire))
(b (make-wire))
(cin (make-wire))
(sum (make-wire))
(cout (make-wire)))
(full-adder a b cin sum cout)
(set-signal! a bit1)
(set-signal! b bit2)
(set-signal! cin carin)
(newline)
(displayb "start time = ") (displayb (current-time the-agenda))
(propagate)
(newline)
(displayb "end time = ") (displayb (current-time the-agenda))
(newline)
(displayb "sum = ") (displayb (get-signal sum))
(newline)
(displayb "carry = ") (display (get-signal cout))
))
]]>
Here are a couple of sample runs of the tester. Try it on your
fulladder.
<![CDATA[
> (fulladdtes 0 0 0)
start time = 0
end time = 5
sum = 0
carry = 0
>(fulladdtes 0 1 1)
start time = 21
end time = 37
sum = 0
carry = 1
]]>
Of course, you really need to try 8 tests to be sure the adder works,
but you get the idea.
I also wrote a 3 bit adder (part of your homework) and a 3 bit adder tester.
The tester is much longer than the adder it tests. Here is the tester
<![CDATA[
(define (threebitaddtes ainlis binlis)
(let* ((awi1 (make-wire)) (bwi1 (make-wire)) (swi1 (make-wire))
(awi2 (make-wire)) (bwi2 (make-wire)) (swi2 (make-wire))
(awi3 (make-wire)) (bwi3 (make-wire)) (swi3 (make-wire))
(cout (make-wire))
(awilis (list awi1 awi2 awi3))
(bwilis (list bwi1 bwi2 bwi3))
(swilis (list swi1 swi2 swi3))
)
(set-signal! awi1 (car ainlis)) (set-signal! awi2 (cadr ainlis))
(set-signal! awi3 (caddr ainlis)) (set-signal! bwi1 (car binlis))
(set-signal! bwi2 (cadr binlis)) (set-signal! bwi3 (caddr binlis))
(newline)
(displayb "start time = ") (displayb (current-time the-agenda))
(threebitadder awilis bwilis swilis cout)
(propagate)
(newline)
(displayb "end time = ") (displayb (current-time the-agenda))
(newline)
(displayb "sum = ")
(displayb (list (get-signal swi1) (get-signal swi2) (get-signal swi3)))
(newline)
(displayb "carry = ") (display (get-signal cout))
))
]]>
and some trial runs:
<![CDATA[
> (threebitaddtes '(0 1 0) '(0 1 1))
start time = 0
end time = 32
sum = (1 0 1)
carry = 0
> (threebitaddtes '(1 1 0) '(0 1 0))
start time = 32
end time = 64
sum = (0 0 0)
carry = 1
]]>
Of course, to thoroughly test the 3 bit adder, we should do 64 tests.
<![CDATA[
]]>
You may spend the rest of this clab starting on the homework for Monday.
Ask any questions you may have.
<![CDATA[
]]>