Вычислительные схемы
2.5. Вычислительные схемы
К этому классу относятся устройства, предназначенные для организации различных вычислительных операций : сумматоры, вычетатели, умножители, арифметико-логические устройства, компараторы и т.д.
2.5.1.Сумматоры
Сумматоры выполняют арифметическое (в противоположность логическому) сложение и вычитание чисел. Имеют самостоятельное значение и являются также ядром схем арифметико-логических устройств (АЛУ), реализующих ряд разнообразных операций и являющихся непременной частью всех процессоров.
Аппаратная сложность и быстродействие сумматора являются очень важными параметрами и поэтому разработано множество вариантов сумматоров, которые имеют разветвленную классификацию. Выделяя главные варианты, остановимся на следующих типах сумматоров:
полусумматор;
одноразрядный сумматор;
сумматор для последовательных операндов;
сумматор для параллельных операндов с последовательным переносом;
сумматор для параллельных операндов с параллельным переносом;
сумматор групповой структуры.
Рекомендуемые материалы
Наряду с сумматорами могут быть реализованы вычитатели, однако это почти никогда не делается, поскольку вычитание выполняется через сложение с применением обратных (инверсия всех разрядов числа, включая знаковый) либо дополнительных (к младшему разряду обратного кода прибавляется 1) кодов. Это означает, что вычитание можно заменить суммированием, представив вычитаемое, например, в дополнительном коде с учетом необходимой инверсии функции заема. Такое решение особенно важно для построения сумматора, выполняющего сложение чисел с произвольными знаками. В этом случае отрицательные числа хранятся в дополнитнльном коде, а их знаковый разряд отрицательный. Сложение в дополнительном коде осуществляется по правилам двоичной арифметики разряд за разрядом, включая знаковые разряды. Возможный перенос из знакового разряда игнорируется. При этом результат получается также в дополнительном коде. Например:
Многоразрядный сумматор состоит из одноразрядных, реализующих сложение одноразрядных чисел. Одноразрядный сумматор, на вход которого поступают два одноразрядных числа Ai и Bi, а на выходе формируются также одноразрядные числа суммы Si и переноса Рi, называют полусумматором (рис. 5.25,а).
Рис. 5.25
Таблица, истинности для полусумматора (табл. 5.15) позволяет записать функцию вычисления суммы Si и переноса единицы переполнения Рi в старший разряд:
Таблица 5.15
Ai Bi | Si Pi |
0 0 | 0 0 |
0 1 | 1 0 |
1 0 | 1 0 |
1 1 | 0 1 |
(5.10)
Согласно выражениям (5.10) полусумматор можно реализовать в базисе элементов И—НЕ (рис.5.25,б), ИЛИ—НЕ либо на основе логического элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и И (рис. 5.25,в). Возможны другие реализации полусумматора на основании тождественных преобразований (5.10)
Если одноразрядный сумматор реализует сложение трех одноразрядных чисел Ai,Bi и C(перенос из младшего разряда), то такой сумматор называют полным. В многоразрядном сумматоре только самый младший разряд можно выполнить по схеме полусумматора, а остальные разряды выполняют функции полного сумматора.
Таблица истинности одноразрядного сумматора имеет следующий вид (табл. 2.12.).
ai bi ci-1 | Si | Ci |
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 | 0 1 1 0 1 0 0 1 | 0 0 0 1 0 1 1 1 |
Таблица 2.12
Аналитические выражения функций суммы и переноса имеют вид:
Эквивалентные преобразования этих выражений дают различные реализации полного сумматора ( рис. 5.28). На рис 5.28д приведено его условное графическое изображение.
Рис. 5.28
Сложение многоразрядных чисел можно реализовать последовательно либо параллельно. При последовательном суммировании требуется одноразрядный полный сумматор, на вход которого в течение тактового интервала последовательно, начиная с младшего разряда, подаются соответствующие разряды слагаемых
и результат переноса от сложения на предыдущем такте (рис. 5.32,а,б). Результат суммирования поразрядно с выхода сумматора передается в линию связи либо запоминается в буферном сдвигающем регистре суммы.
Рис. 5.32.
Операция суммирования заканчивается через количество тактов суммирования (N+1), где N - количество разрядов слагаемых чисел А и В,. Дополнительный такт необходим для реализации переноса от суммирования старших разрядов. При этом общее время суммирования будет составлять: Tобщ =tзΣ (N+1), где tзΣ –задержка сумматора SM. Последовательный сумматор требует минимальных затрат оборудования, не зависящих от разрядности суммируемых чисел. Однако длительность операции суммирования пропорциональна разрядности операндов, поэтому последовательный сумматор может использоваться в относительно медленнодействующих цифровых устройствах.
Параллельный сумматор с последовательным переносом
В параллельном m-разрядном сумматоре используется т полных сумматоров (рис. 5.32,6), т. е. затраты оборудования пропорциональны разрядности операндов, но операция суммирования выполняется за один такт ΤΣ. Длительность такта ΤΣ и сложность реализации параллельного сумматора зависят от способа реализации переносов. В простейшем случае выходы и входы цепей переноса соединяются последовательно (рис. 5.32,б) и длительность такта пропорциональна количеству разрядов сумматора и времени реализации переноса в одном разряде tзд.р.п. :
(5.15)
где tΣ — длительность суммирования в одноразрядном сумматоре, m — разрядность сумматора.
Рис. 5.32
Как и в других схемах с последовательным распространением сигналов от разряда к разряду, здесь время суммирования практически пропорционально разрядности сумматора.
При большом количестве разрядов и последовательной реализации переноса длительность суммирования (5.15) оказывается недопустимо большой.
Параллельный сумматор с параллельным переносом
Сумматоры для параллельных операндов с параллельным переносом разработаны для получения максимального быстродействия. Увеличение быстродействия параллельного сумматора достигается за счет одновременного формирования сигналов переноса во всех его т разрядах. Сигналы переноса для данного разряда формируются специальными схемами блоками ускоренного переноса, на входы которых поступают все переменные, от которых зависит его наличие или отсутствие. Ясно, что это внешний входной перенос Свх (если он есть) и значения всех разрядов слагаемых, младших относительно данного разряда (рис. 2.28). Обозначение CR от слова carry (перенос).
Формирование переноса в схемах CR выполняется с помощью двух вспомогательных функций: генерации и прозрачности.
Функция генерации принимает единичное значение, если перенос на выходе данного разряда появляется независимо от наличия или отсутствия входного переноса. Очевидно, что эта функция
Функция прозрачности (транзита) принимает единичное значение, если перенос на выходе данного разряда появляется только при наличии входного переноса. Эта функция
Выражение для сигнала переноса можно записать в виде
Таким образом, перенос на выходе младшего разряда т.е. он либо генерируется самим разрядом либо пропускается через него и
Аналогично для переноса C1 на выходе следующего разряда или подставив в это соотношение выражение для Со, получим:
Для произвольного разряда с номером i можно записать:
Длительность суммирования сумматора с параллельным распространением переноса не зависит от его разрядности. Однако с ростом разрядности сумматора увеличивается нагрузка элементов схемы, что увеличивает их задержки. Поэтому рост разрядности замедляет процесс суммирования.
Диапазон разрядностей, в которых проявляются достоинства сумматоров с параллельным переносом, невелик. До n = 3...4 преимущества имеют более простые схемы сумматоров с последовательным переносом, при n>4 преимущества имеют сумматоры с параллельным переносом, а после n = 8 у сумматоров с параллельным переносом появляются перегруженные элементы и элементы с большим числом входов, что замедляет их работу и усложняет реализацию. Поэтому для сложения чисел большей разрядности применяются сумматоры групповой структуры.
Сумматоры групповой структуры
В сумматорах групповой структуры схема с разрядностью n делится нагрупп по m разрядов (n = *т). В группах и между ними возможны различные виды переносов (параллельные и последовательные).
Ниже приведена схема с цепным (последовательным) переносом между группами. В самих группах перенос при этом может быть любым. При группах сумматор имеет .— 1 блок переноса. Блоки переноса включены последовательно и образуют тракт передачи переноса (рис. 2.30). Слагаемые разбиты по m-разрядов, суммируемых в группах. Результат также составляется из m-разрядных частей.
Блоки переноса БПi (i = 1...) анализируют слагаемые в пределах группы, и если из группы должен быть перенос, то он появляется на выходе блока для подачи на вход следующей группы и в цепочку распространения переноса от младших групп к старшим.
Переносы определяются формулами, полученными выше для сумматоров с параллельным переносом, но сумматоры благодаря делению на группы существенно упрощаются — у них все БПi имеют одинаковую сложность (все блоки анализируют m-разрядные операнды ), тогда как в сумматоре с параллельными переносами сложность схем переноса непрерывно возрастает при переходе от предыдущего разряда к последующему (последняя схема переноса требует анализа операндов с разрядностью n-1).
Максимальная длительность суммирования для такого варианта сумматора
Функции прозрачности разрядов, необходимые для блоков переносов, вырабатываются либо в этих блоках, либо уже имеются в группах, если в них организован параллельный перенос, и могут поступать из групп (штриховые линии на рис. 2.30).
Сумматор с параллельными межгрупповыми переносами строится по структуре, аналогичной структуре сумматора с параллельным переносом, в которой роль одноразрядных сумматоров играют группы.
2.5.2. Компараторы
Компараторы (устройства сравнения) определяют отношения между двумя словами.на "больше", "меньше", "равно". Эти отношения используются как логические условия в микропрограммах, в устройствах контроля и диагностики ЭВМ и т. д.
Пример компаратора, которые имеются в сериях цифровых элементов приведен на рис. 2.16. Для краткости записей в индексе выходных функций указывается только слово А.
Устройства сравнения на равенство строятся на основе поразрядных операций над одноименными разрядами обоих слов. Слова равны, если равны все одноименные их разряды, т. е. если в обоих нули или единицы. Признак равенства разрядов
Признак равенства слов
Сравнение на "больше" для одноразрядных слов (табл. 2.7) требует реализации функции
Функцию для многоразрядных слов получаем на основе следующих рассуждений: если старшие разряды a1 и b1 не равны, то результат известен независимо от младших разрядов (при a1 = 1 и b1 = 0 имеем А>В, а при a1 = 0 и b1 = 1 имеем А<В). Если же a1 = b1, результат еще неизвестен, и требуется анализ следующего разряда по тому же алгоритму. Поэтому для двухразрядных слов можно записать
Подобный подход справедлив для слов любой разрядности — к анализу следующего разряда нужно переходить только при равенстве предыдущих. Таким образом, для общего случая n-разрядных слов имеем:
Пример реализации компаратора с тремя выходами для двухразрядных слов приведен на рис. 2.18. Выработка признака А>В в этой схеме производится по соотношению (штрихом отмечены функции с выходов младшей группы)
Компараторы для слов большой разрядности получают наращиванием размерности путем использования нескольких ИС компараторов, принцип наращивания соответствует показанному на рис. 2.18.
2.5.3. Арифметико-логические устройства
Арифметико-логические устройства АЛУ (ALU, Arithmetic-Logic Unit) выполняют над словами ряд действий. Основой АЛУ служит сумматор, схема которого дополнена логикой, расширяющей функциональные возможности АЛУ и обеспечивающей его перестройку с одной операции на другую.
Обычно АЛУ четырехразрядны и для наращивания разрядности объединяются с формированием последовательных или параллельных переносов. АЛУ (рис. 2.35) имеет входы операндов А и В, входы выбора операций S, вход переноса и вход М (Mode), сигнал которого задает тип выполняемых операций: логические (М = 1) или арифметико-логические (М = 0). Результат операции вырабатывается на выходах F, выходы G и Н дают функции генерации и прозрачности, используемые для организаций параллельных переносов при наращивании размерности АЛУ. Сигнал — выходной перенос, а выход А = В есть выход сравнения на равенство с открытым коллектором.
Перечень выполняемых АЛУ операций дан в табл. 2.13. Для краткости двоичные числа S3S2S1S0 представлены их десятичными эквивалентами. Под утолщенными обозначениями 1 и 0 следует понимать наборы 1111 и 0000, входной перенос поступает в младший разряд слова, т. е. равен 000Сi,. Логические операции поразрядные, т. е. операция над словами А * В означает, что аi * bi при отсутствии взаимовлияния разрядов. При арифметических операциях учитываются межразрядные переносы.
Ещё посмотрите лекцию "19 Привлечение к труду осужденных к лишению свободы" по этой теме.
Шестнадцать логических операций позволяют воспроизводить все функции Двух переменных. В логико-арифметических операциях встречаются и логические и арифметические операции одновременно. Запись типаследует понимать так: вначале поразрядно выполняются операции инвертированиялогического сложения и умножения а затем полученные указанным образом два четырехразрядных числа складываются арифметически.
При операциях над словами большой размерности АЛУ соединяются с другом с организацией последовательных (рис. 2.36, a) или параллельных (рис. 2.36, б) переносов. В последнем случае совместно с АЛУ применяются микросхемы — блоки ускоренного переноса (CRU, Carry Unit), получающие от отдельных АЛУ функции генерации и прозрачности, а также входной перенос и вырабатывающие сигналы переноса по формулам, приведенным для сумматора с параллельным переносом.
Рис.2. 36. Схемы наращивания АЛУ при последовательном(а) и параллельном (б) переносах.
Блок CRU вырабатывает также функции генерации и прозрачности для всей группы обслуживаемых им АЛУ, что при необходимости позволяет организовать параллельный перенос на следующем уровне (между несколькими группами из четырех АЛУ).