A-B-

SUM

-Cout

Рис. 3.26: Сумматор.

Преимущество этого определения в том, что теперь мы можем использовать half-adder как строительный блок при создании более сложных схем. Например, на рисунке 3.26 изображен сумматор (full-adder), состоящий из двух полусумматоров и ИЛИ-элемента.26 Сумматор можно сконструировать так:

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

Определив full-adder как процедуру, мы можем ее использовать как строительный блок для еще более сложных схем. (См., например, упражнение 3.30.)

В сущности, наша имитация дает инструмент, с помощью которого строится язык описания схем. Принимая общую точку зрения на языки, с которой мы приступили к изучению Лиспа в разделе 1.1, можно сказать, что элементарные функциональные элементы являются примитивами языка, связывание их проводами представляет собой средство комбинирования, а определение шаблонных схем в виде процедур служит средством абстракции.

Элементарные функциональные элементы.

Элементарные функциональные элементы изображают «силы», через посредство которых изменение сигнала в одном проводе влечет изменение сигнала в других проводах. Для построения функциональных элементов мы будем пользоваться следующими операциями над проводами:

•(get-signal (провод)) возвращает текущее значение сигнала в проводе.

•(set-signal! (провод) (новое-значение)) заменяет значение сигнала в проводе на указанное.

•(add-action! (провод) (процедура без аргументов)) указывает, чтобы процедура-аргумент вызывалась каждый раз, когда сигнальный провод изменяет значение. Такие процедуры служат передаточным механизмом,

26Сумматор - основной элемент схем, используемых для сложения двоичных чисел. Здесь A и B - биты на соответствующих позициях двух складываемых чисел, а Сш - бит переноса из позиции на одну правее. Схема генерирует SUM, бит суммы для соответствующей позиции, и Cout, бит переноса для распространения налево.

с помощью которого изменение значения сигнала в одном проводе передается другим проводам. В дополнение, мы будем пользоваться процедурой after-delay, которая принимает значение задержки и процедуру. Она выполняет процедуру после истечения задержки.

При помощи этих процедур можно определить элементарные функции цифровой логики. Чтобы соединить вход с выходом через инвертор, мы используем add-action! и ассоциируем со входным проводом процедуру, которая будет вызываться всякий раз, когда сигнал на входе элемента изменит значение. Процедура вычисляет logical-not (логическое отрицание) входного сигнала, а затем, переждав inverter-delay, устанавливает выходной сигнал в новое значение:

(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 "Неправильный сигнал" s))))

И-элемент устроен немного сложнее. Процедура-действие должна вызываться, когда меняется любое из значений на входе. Она при этом через процедуру, подобную logical-not, вычисляет logical-and (логическое И) значений сигналов на входных проводах, и затем требует, чтобы изменение значения выходного провода произошло спустя задержку длиной в and-gate-delay.

(define (and-gate al 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)

Упражнение 3.28.

Определите ИЛИ-элемент как элементарный функциональный блок. Ваш конструктор or-gate должен быть подобен and-gate.

Упражнение 3.29.

Еще один способ создать ИЛИ-элемент - это собрать его как составной блок из И-элементов и инверторов. Определите процедуру or-gate, которая это осуществляет. Как время задержки ИЛИ-элемента выражается через and-gate-delay и inverter-delay?

A1 Bl

FA

S1

A2B2C2 A3B3

C

FA

S2

FA

C2

C3

C

*n n

FA

n-1

Cn=0

Рис. 3.27: Каскадный сумматор для n-битных чисел.

Упражнение 3.30.

На рисунке 3.27 изображен каскадный сумматор (ripple-carry adder), полученный выстраиванием в ряд n сумматоров. Это простейшая форма параллельного сумматора для сложения двух n-битных двоичных чисел. На входе мы имеемA3,... An и Bi,

B2, B3, ... Bn - два двоичных числа, подлежащих сложению (каждый из и имеет значение либо 0, либо 1). Схема порождает Si, S3, ... Sn - первые n бит суммы, и C - бит переноса после суммы. Напишите процедуру riple-carry-adder, которая бы моделировала эту схему. Процедура должна в качестве аргументов принимать три списка по n проводов в каждом (A, и S), а также дополнительный провод C. Главный недостаток каскадных сумматоров в том, что приходится ждать, пока сигнал распространится. Какова задержка, требуемая для получения полного вывода n-битного каскадного сумматора, выраженная в зависимости от задержек И-, ИЛИ-элементов и инверторов?

S

S

n

Представление проводов

Провод в нашей имитации будет вычислительным объектом с двумя внутренними переменными состояния: значение сигнала signal-value (вначале равное 0) и набор процедур-действий action-procedures, подлежащих исполнению, когда сигнал изменяется. Мы реализуем провод в стиле с передачей сообщений, как набор локальных процедур плюс процедура диспетчеризации, которая выбирает требуемую внутреннюю операцию. Точно так же мы строили объект-банковский счет в разделе 3.l.l.

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