3.3.4 · Симулятор цифровых схем

Симулятор цифровых схем на расписании задержек

Изменяемые провода, отложенные действия логических элементов, упорядоченное расписание и полусумматор, реагирующий после задержки распространения.

Вопрос для размышления

Как локальные правила логических элементов объединяются в схему, чье поведение разворачивается через явное модельное время?

Хранение одного сигнала и списка действий внутри каждого провода
Запуск действий провода только при реальном изменении сигнала
Планирование обновлений элементов на момент текущего времени плюс фиксированная задержка
Распространение событий плана действий в неубывающем модельном времени
Композиция базовых логических элементов в полусумматор без центральной логики схемы

Провод содержит сигнал и список процедур действий. Установка логического элемента добавляет действие к каждому входному проводу и запускает его один раз для планирования начального вывода. Позже set-signal! вызывает эти действия только тогда, когда сигнал изменяется. Каждый логический элемент считывает свои текущие входы немедленно, но планирует изменение выхода на более позднее время в плане действий.

Полусумматор строится из элементов or, and, inverter и еще одного элемента and. Конечное расписание сначала устанавливает нулевые входы, а затем изменяет a, b и снова a. Зафиксированные моменты времени представляют собой точные события симуляции, полученные из явных задержек в этой модели.

Код SICP2,220 из 1,048,576 байт UTF-8

(begin
  (define current-time 0)
  (define agenda '())
  (define (insert-event event events)
    (cond ((null? events) (list event))
          ((< (car event) (car (car events)))
           (cons event events))
          (else
           (cons (car events)
                 (insert-event event (cdr events))))))
  (define (after-delay delay action)
    (set! agenda
          (insert-event
            (list (+ current-time delay) action)
            agenda)))
  (define (propagate)
    (if (null? agenda)
        'done
        (let ((event (car agenda)))
          (set! agenda (cdr agenda))
          (set! current-time (car event))
          ((cadr event))
          (propagate))))
  (define (make-wire)
    (let ((signal 0) (actions '()))
      (define (call-each procedures)
        (if (null? procedures)
            'done
            (begin
              ((car procedures))
              (call-each (cdr procedures)))))
      (define (set-signal new-value)
        (if (= signal new-value)
            'unchanged
            (begin
              (set! signal new-value)
              (call-each actions)
              'changed)))
      (define (add-action action)
        (set! actions (cons action actions))
        (action)
        'ok)
      (lambda (message)
        (cond ((eq? message 'get) signal)
              ((eq? message 'set) set-signal)
              ((eq? message 'add-action) add-action)
              (else 'unknown-wire-message)))))
  (define (get-signal wire) (wire 'get))
  (define (set-signal! wire value) ((wire 'set) value))
  (define (add-action! wire action) ((wire 'add-action) action))
  (define (logical-not signal) (if (= signal 0) 1 0))
  (define (inverter input output)
    (define (action)
      (let ((new-value (logical-not (get-signal input))))
        (after-delay 2
          (lambda () (set-signal! output new-value)))))
    (add-action! input action)
    'ok)
  (define input (make-wire))
  (define output (make-wire))
  (inverter input output)
  (propagate)
  (define initial-time current-time)
  (define initial-output (get-signal output))
  (set-signal! input 1)
  (propagate)
  (list initial-time
        initial-output
        current-time
        (get-signal output)))

(begin
  (define current-time 0)
  (define agenda '())
  (define (insert-event event events)
    (cond ((null? events) (list event))
          ((< (car event) (car (car events)))
           (cons event events))
          (else
           (cons (car events)
                 (insert-event event (cdr events))))))
  (define (after-delay delay action)
    (set! agenda
          (insert-event
            (list (+ current-time delay) action)
            agenda)))
  (define (propagate)
    (if (null? agenda)
        'done
        (let ((event (car agenda)))
          (set! agenda (cdr agenda))
          (set! current-time (car event))
          ((cadr event))
          (propagate))))
  (define (make-wire)
    (let ((signal 0) (actions '()))
      (define (call-each procedures)
        (if (null? procedures)
            'done
            (begin
              ((car procedures))
              (call-each (cdr procedures)))))
      (define (set-signal new-value)
        (if (= signal new-value)
            'unchanged
            (begin
              (set! signal new-value)
              (call-each actions)
              'changed)))
      (define (add-action action)
        (set! actions (cons action actions))
        (action)
        'ok)
      (lambda (message)
        (cond ((eq? message 'get) signal)
              ((eq? message 'set) set-signal)
              ((eq? message 'add-action) add-action)
              (else 'unknown-wire-message)))))
  (define (get-signal wire) (wire 'get))
  (define (set-signal! wire value) ((wire 'set) value))
  (define (add-action! wire action) ((wire 'add-action) action))
  (define (logical-not signal) (if (= signal 0) 1 0))
  (define (inverter input output)
    (define (action)
      (let ((new-value (logical-not (get-signal input))))
        (after-delay 2
          (lambda () (set-signal! output new-value)))))
    (add-action! input action)
    'ok)
  (define input (make-wire))
  (define output (make-wire))
  (inverter input output)
  (propagate)
  (define initial-time current-time)
  (define initial-output (get-signal output))
  (set-signal! input 1)
  (propagate)
  (list initial-time
        initial-output
        current-time
        (get-signal output)))

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Программа inverter возвращает (2 1 4 0). Программа half-adder возвращает ((initial 5 0 0) (a-one 13 1 0) (both-one 21 0 1) (a-zero 29 1 0)).

На что обратить внимание в трассе

Отделяйте немедленное чтение входов от отложенных изменений выходов. Проследите за упорядоченной вставкой в план действий, каждым обновлением current-time и действиями провода, вызванными изменением сигнала. В полусумматоре определите, какой базовый логический элемент планирует каждый переход в sum и carry.

Попробуйте сами

Измените программу и сравните результат.

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

Показать подсказку

Полный сумматор объединяет два полусумматора и выполняет операцию OR над их выходами carry. Сохраняйте все задержки явными вместо централизованного вычисления таблицы истинности.

Завершить этот урок

В этой главе пройдено 0 из 21 урока0%