29.1.2.Схемы из функциональных элементов

Мы рассматриваем схемы из функциональных элементов (combinational circuits), соединённых проводами (wires). При этом не должно образовываться циклов (см. ниже). Провод соединяет выход одного элемента со входом другого; выходное значения первого элемента используется вторым как входное. Провод должен быть подключен не более чем к к одному выходу, но может соединять его сразу с несколькими входами. Число входов элементов, подсоединенных к данному проводу, называется его выходной степенью (fan-out). Если провод не подсоединен к выходам элементов, то он является входом схемы, получая значение извне. Если провод не подключен к входам элементов, то он является выходом схемы и выдаёт наружу результат работы схемы (внутренний провод также может, разветвляясь, служить выходом схемы). Схемы не содержат циклов (цикл появляется, если выход элемента является входом второго, выход второго - входом третьего, ..., наконец, выход га-го - входом первого). Они также не содержат элементов задержки (если это не оговорено специально - см. раздел 29.4).

29.1.3.Сумматор

На рис. 29.2 изображен сумматор (full adder), на входы х, у и z которого поступают три бита. Значения на выходах ens даются таблицей

Другими словами, s есть функция чётности (parity) входных аргументов:

s = parity (ж, у, z) = х ф у ф z(29.1)

а с - функция большинства (majority):

с = majority, у, z) = (ж Л у) V (у Л z) V (ж Л z)(29.2)

Функции чётности и большинства имеют смысл для любого числа аргументов: функция «чётность» равна 1, когда среди её аргументов нечётное число единиц, а функция «большинство» - когда более половины её аргументов равны 1.

Заметьте, что в совокупности биты с и s дают двоичную запись суммы xA-yA-z. Например, если х = 1, у = 0 и z = 1, то (с, s) = (10), аж + у + ,г = 2= Юг-Рис. 29.2 Сумматор, (а) В момент 0 биты поступают на вход. (Ь) Через единицу времени появляются значения на выходах элементов A-D глубины 1. (с) Ещё через единицу времни появляются значения на выходах элементов Е и F глубины 2. (d) Ещё через единицу времени (момент времени 3) на выходе элемента G появляется результат работы всей схемы.

Элементы А и Е можно заменить на один элемент XOR с тремя входами а элементы F и G - на один элемент OR с тремя входами. Число входов элемента называют его входной степенью (fan-in).

Будем считать, что каждый элемент имеет единичную задержку, а входные значения поступают в момент 0 (рис. 29.2, а). С этого момента входы элементов A-D (и только их) стабильны в этот момент, поэтому с момента 1 их выходные значения стабильны (рис. 29.2, Ь). Тем самым элементы A-D работают параллельно. С момента 1 входные значения у Е и F (но не у С!) стабильны, поэтому с момента 2 стабильны их выходные знаения (рис. 29.2, с), в том числе выходной бит s. Однако бит с ещё не получен - элемент G имеет стабильные входы с момента 2 и выдаёт с в момент 3 (рис. 29.2, d).

29.1.4. Глубина схемы

Как и в случае сортирующих сетей в главе 28, задержка схемы определяется наибольшим количеством элементов на путях от входов схемы к выходам. Эта характеристика схемы называется её глубиной (depth) и определяет время её работы. По определению входы схемы имеют глубину 0, а выходные провода элемента со входами глубины d\,... ,dn имеют глубину max{di,... , dn} + 1. Поскольку в схеме нет циклов, это индуктивное определение корректно. Глубиной элемента называется глубина его выходов, а глубиной схемы - наибольшая глубина составляющих её элементов.

Если все функциональные элементы производят действие за одно и то же время t, то время работы схемы глубины d не превосходит dt. На рис. 29.2 указана глубина всех элементов сумматора. Поскольку наибольшую глубину (3) имеет элемент G, глубина схемы также равна 3.

Иногда схема может работать несколько быстрее. Например, если на один из входов элемента AND подан 0, то на выходе появится 0, даже если второе входное значение будет всё ещё меняться. Однако на практике время работы схемы чаще всего пропорционально глубине.

29.1.5.Размер схемы

При разработке схемы, реализующей данную функцию, стараются уменьшить не только её глубину, но и размер (size) - число функциональных элементов. Например, описанный выше сумматор имеет размер 7.

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

Однако если нас интересует не одна схема, а семейтво однотипных схем (например, мы строим сумматор га-разрядных чисел для любого га), увеличение набора разрешённых элементов (если он остаётся конечным) уменьшает размер схемы всего лишь в константу раз по сравнению с базовым набором (AND, OR, NOT), поскольку все разрешённые элементы можно составить из базовых.

29.1.6.Упражнения

29.1-1. Как изменятся значения на рис. 29.2 (a)-(d), если х = 1, у=1,г=1?

29.1-2. Постройте из га - 1 элемента XOR схему для функции «чётность» с га входами, глубина которой не превосходит [lgra].

29.1-3. Докажите, что для любой таблицы значений соответствующий логический элемент можно реализовать схемой из элементов AND, OR и NOT.

29.1-4. Докажите, что в предыдущей задаче можно обойтись только элементами типа NAND.

29.1-5. Постройте схему для функции XOR из четырёх элементов NAND.

29.1-6. Пусть схема С имеет га входов, га выходов и глубину d. Соединим два экземпляра С, присоединив выходы первого ко входам второго. Какова может быть глубина такой схемы? (Укажите наибольшее и наименьшее возможные значения.)

29.2. Схемы для сложения

В этом разделе приведены три схемы для сложения га-битовых двоичных чисел. Каскадное сложение (ripple-carry addition) позволяет сложить два га-значных числа за время О (га) с помощью схемы размера О (га). Время можно уменьшить до О (lgra), используя