디지털 회로 시뮬레이터 소스와 문제 풀이

[xeraph]

3.28. 논리합 소자를 or-gate라는 프로시저로 정의하라. and-gate와 비슷하게 만들면 된다.
아래 소스 찾아보면 있음.

3.29. 논리곱 소자와 인버터를 엮어서 논리합 소자를 짜맞추는 방법이 있다. 이 방법대로 or-gate 프로시저를 정의하라.
이때 뒤처지는 시간을 and-gate-delay와 inverter-delay로 표현하면 어떻게 되는가?
드 모르간 법칙을 이용해서 정의하면 된다. 아래 or-gate2 정의를 참고.
inverter, and-gate, inverter 순서대로 통과하므로 지연 시간 역시 (+ (* 2 inverter-
delay) and-gate-delay) 가 됨.

3.30. 자리 올림 덧셈기는 덧셈기 n개를 한데 묶어 만든 것이다. n비트 자리 올림 덧셈기에서 신호가 모두 나오려면 얼마나
기다려야 하는가?
FA 하나 기준으로 계산한 다음, FA 갯수만큼 곱하면 된다. (일일이 따져보긴 귀찮네-_-)

3.31. make-wire의 안쪽 프로시저 accept-action-procedure!는 일 프로시저를 줄과 짝맞출 때, 그
프로시저를 곧바로 돌리고 있다. 왜 이렇게 해야 하는지 설명해 보라. accept-action-procedure!를 아래처럼 정
의했다면, 위 절에 나온 반 덧셈기를 돌리면서 무엇이 어떻게 달라지는지 밝혀라.
코드를 보면 agenda 시간표에 집어넣도록 되어있어서 proc 빼놓으면 액션 실행이 안 됨.

3.32. 시간표에는 조각 시간마다 돌려야 할 프로시저가 큐에 들어있다. 따라서 조각 시간 속에 있는 프로시저는 시간표에 넣은
차례대로 돌아간다. 왜 이런 차례를 따라야 하는지 밝혀 보라.
신호가 바뀌면서 순차적으로 이벤트가 걸리는데 시간 순서를 뒤집으면 결과가 꼬일 수 있음.

(define (make-queue) (cons '() '()))
(define (empty-queue? queue) (null? (front-ptr queue)))
(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item) (set-car! queue item))
(define (set-rear-ptr! queue item) (set-cdr! queue item))
(define (front-queue queue)
(if (empty-queue? queue)
(error "FRONT called with an empty queue" queue)
(car (front-ptr queue))))

(define (insert-queue! queue item)
(let ((new-pair (cons item '())))
(cond ((empty-queue? queue)
(set-front-ptr! queue new-pair)
(set-rear-ptr! queue new-pair)
queue)
(else
(set-cdr! (rear-ptr queue) new-pair)
(set-rear-ptr! queue new-pair)
queue))))

(define (delete-queue! queue)
(cond ((empty-queue? queue)
(error "DELETE! called with an empty queue" queue))
(else
(set-front-ptr! queue (cdr (front-ptr queue)))
queue)))

(define (make-wire)
(let ((signal-value 0) (action-procedures '()))
(define (set-my-signal! new-value)
(if (not (= signal-value new-value))
(begin (set! signal-value new-value)
(call-each action-procedures))
'done))

(define (accept-action-procedure! proc)
(set! action-procedures (cons proc action-procedures))
(proc))

(define (dispatch m)
(cond ((eq? m 'get-signal) signal-value)
((eq? m 'set-signal!) set-my-signal!)
((eq? m 'add-action!) accept-action-procedure!)
(else (error "Unknown operation -- WIRE" m))))

dispatch))

(define (call-each procedures)
(if (null? procedures)
'done
(begin
((car procedures))
(call-each (cdr procedures)))))

(define (get-signal wire)
(wire 'get-signal))

(define (set-signal! wire new-value)
((wire 'set-signal!) new-value))

(define (add-action! wire action-procedure)
((wire 'add-action!) action-procedure))

(define (after-delay delay action)
(add-to-agenda! (+ delay (current-time the-agenda))
action
the-agenda))

(define (propagate)
(if (empty-agenda? the-agenda)
'done
(let ((first-item (first-agenda-item the-agenda)))
(first-item)
(remove-first-agenda-item! the-agenda)
(propagate))))


(define (probe name wire)
(add-action! wire
(lambda ()
(newline)
(display name)
(display " ")
(display (current-time the-agenda))
(display " New-value = ")
(display (get-signal wire)))))

(define (make-agenda) (list 0))

(define (current-time agenda) (car agenda))

(define (set-current-time! agenda time)
(set-car! agenda time))

(define (segments agenda) (cdr agenda))

(define (set-segments! agenda segments)
(set-cdr! agenda segments))

(define (first-segment agenda) (car (segments agenda)))

(define (rest-segments agenda) (cdr (segments agenda)))

(define (empty-agenda? agenda)
(null? (segments agenda)))

(define (add-to-agenda! time action agenda)
(define (belongs-before? segments)
(or (null? segments)
(< time (segment-time (car segments)))))

(define (make-new-time-segment time action)
(let ((q (make-queue)))
(insert-queue! q action)
(make-time-segment time q)))


(define (add-to-segments! segments)
(if (= (segment-time (car segments)) time)
(insert-queue! (segment-queue (car segments))
action)
(let ((rest (cdr segments)))
(if (belongs-before? rest)
(set-cdr!
segments
(cons (make-new-time-segment time action)
(cdr segments)))
(add-to-segments! rest)))))

(let ((segments (segments agenda)))
(if (belongs-before? segments)
(set-segments!
agenda
(cons (make-new-time-segment time action)
segments))
(add-to-segments! segments))))

(define (remove-first-agenda-item! agenda)
(let ((q (segment-queue (first-segment agenda))))
(delete-queue! q)
(if (empty-queue? q)
(set-segments! agenda (rest-segments agenda)))))

(define (first-agenda-item agenda)
(if (empty-agenda? agenda)
(error "Agenda is empty -- FIRST-AGENDA-ITEM")
(let ((first-seg (first-segment agenda)))
(set-current-time! agenda (segment-time first-seg))
(front-queue (segment-queue first-seg)))))

(define (inverter input output)
(define (invert-input)
(let ((new-value (logical-not (get-signal input))))
(after-delay inverter-delay
(lambda ()
(set-signal! output new-value)))))
(add-action! input invert-input)
'ok)

(define (logical-not s)
(cond ((= s 0) 1)
((= s 1) 0)
(else (error "Invalid signal" s))))

(define (and-gate a1 a2 output)
(define (and-action-procedure)
(let ((new-value
(logical-and (get-signal a1) (get-signal a2))))
(after-delay and-gate-delay
(lambda ()
(set-signal! output new-value)))))
(add-action! a1 and-action-procedure)
(add-action! a2 and-action-procedure)
'ok)

(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))

; problem 3.28. define or-gate similar to and-gate
(define (logical-and a1 a2)
(cond ((and (= a1 0) (= a2 0)) 0)
((and (= a1 0) (= a2 1)) 0)
((and (= a1 1) (= a2 0)) 0)
((and (= a1 1) (= a2 1)) 1)
(else (error "Invalid signal"))))

(define (logical-or a1 a2)
(cond ((and (= a1 0) (= a2 0)) 0)
((and (= a1 0) (= a2 1)) 1)
((and (= a1 1) (= a2 0)) 1)
((and (= a1 1) (= a2 1)) 1)
(else (error "Invalid signal"))))

(define (or-gate a1 a2 output)
(define (or-action-procedure)
(let ((new-value
(logical-or (get-signal a1) (get-signal a2))))
(after-delay or-gate-delay
(lambda ()
(set-signal! output new-value)))))
(add-action! a1 or-action-procedure)
(add-action! a2 or-action-procedure)
'ok)

; problem 3.29. define or-gate using and-gate and inverter
; answer. 2 * inverter-delay + and-gate-delay
(define (or-gate2 a1 a2 output)
(let ((o1 (make-wire))
(o2 (make-wire))
(o3 (make-wire)))
(inverter a1 o1)
(inverter a2 o2)
(and-gate o1 o2 o3)
(inverter o3 output)
'ok))

(define (make-time-segment time queue)
(cons time queue))

(define (segment-time s) (car s))
(define (segment-queue s) (cdr s))

; test
(define the-agenda (make-agenda))
(define inverter-delay 2)
(define and-gate-delay 3)
(define or-gate-delay 5)
;(define input-1 (make-wire))
;(define input-2 (make-wire))
;(define sum (make-wire))
;(define carry (make-wire))
;(probe 'sum sum)
;(probe 'carry carry)
;(half-adder input-1 input-2 sum carry)
;(set-signal! input-1 1)
;(propagate)

(define input-1 (make-wire))
(define input-2 (make-wire))
(define output (make-wire))
(probe 'output output)
(or-gate2 input-1 input-2 output)
(set-signal! input-2 1)
(propagate)