Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.sm.bmstu.ru/sm5/n4/oba/proz2.html
Дата изменения: Thu Feb 15 17:43:25 2007 Дата индексирования: Mon Oct 1 18:58:14 2012 Кодировка: Windows-1251 Поисковые слова: п п п п п п п п п п п п п п п п п п п п п п п п п п |
![]() |
![]() |
![]() |
Принципы построения вычислительных устройств на базе устройств программируемой логики |
Как правило, любое устройство управления или обработки данных разделено на модули, имеющие различные скорости обработки входных данных. Модули соединены между собой линиями связи, которые, в свою очередь, имеют ограниченную пропускную способность. Для согласования различных скоростей обработки модулей применяются дополнительные устройства, которые производят предварительную обработку данных и уменьшают потоки обрабатываемой или передаваемой информации. При построении микропроцессорных устройств обработки или управления практически всегда требуется введение дополнительных дискретных элементов или реализация этих устройств на ПЛИС с целью согласования или предварительной обработки входных сигналов. Модули предварительной обработки могут содержать как простые логические элементы, так и логические устройства: мультиплексоры, счетчики, делители, триггеры, АЛУ, массивы памяти и др. Далее нас будут интересовать устройства, построенные с применением ПЛИС, как более перспективные. Реализация логических операций и логических устройств на ПЛИС не представляет труда, так как ПЛИС по своей сути являются логическими устройствами. Поэтому уделим наше внимание организации арифметических функций:
Перед рассмотрением алгоритмов необходимо выяснить, в каком коде представляются операнды. В ЭВМ в целях упрощения арифметических операций применяют специальные коды для представления чисел. При помощи этих кодов упрощается определение знака результата операции. Операция вычитания или алгебраического сложения сводится к арифметическому сложению кодов, облегчается выработка признаков переполнения разрядной сетки. Для представления чисел со знаком в ЭВМ применяют прямой, обратный и дополнительные коды. Общая идея построения кодов такова. Код трактуется как число без знака, а диапазон представляемых кодами чисел без знака разбивается на два поддиапазона. Один из них представляет положительные числа, а другой - отрицательные. Разбиение производится таким образом, чтобы принадлежность к поддиапазону определялась максимально просто. Использование такого кодирования позволяет говорить о старшем разряде как о знаковом, хотя в общем код трактуется как число без знака. Прямой код двоичного числа G, представленного в n - разрядной сетке, определяется какгде А - величина, равная весу старшего разряда сетки (для дробей А = 1, а для целых А = ![]() ![]() ![]() ![]() Признаком представления положительных или отрицательных чисел является наличие нуля или единицы соответственно в старшем разряде, называемом знаковым. Цифровые разряды прямого кода содержат модуль представляемого числа, что обеспечивает наглядность представления чисел в прямом коде. Обратный код двоичного числа G, представленного в n - разрядной сетке, определяется какгде В - величина наибольшего числа без знака, размещающегося в n- разрядной сетке (для дробей![]() ![]() ![]() ![]() ![]() Дополнительный код двоичного числа G, представленного в n - разрядной сетке, определяется какгде С - величина, равная весу разряда, следующего за старшим разрядом используемой разрядной сетки(для дробей ![]() ![]() ![]() Дополнительный код отрицательного числа может быть получен из обратного путем прибавления 1 к младшему разряду обратного кода. Как правило, АЛУ работает с двоичным дополнительным кодом, так как при его использовании операция алгебраического сложения сводится к сложению арифметическому. Сумматором называется узел ЭВМ, выполняющий арифметическое суммирование кодов чисел. Обычно сумматор представляет собой комбинацию одноразрядных суммирующих схем. При сложении двух чисел в каждом разряде производится сложение трех цифр:
В таблице1 представлены варианты, возникающие при сложении двух двоичных чисел. Таблица 1 |
Перенос из младшего разряда ![]() |
Первое слагаемое |
Второе слагаемое |
Сумма |
Перенос в старший разряд ![]() |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
По таблице1 можно составить булевы функции для описания одноразрядного сумматора:
![]()
Многоразрядный сумматор может быть составлен из одноразрядных сумматоров, число которых равно числу разрядов слагаемых. По характеру распространения переноса различают следующие виды сумматоров:
Сумматоры с поразрядным последовательным переносом. В сумматорах этого типа перенос распространяется последовательно от разряда к разряду по мере образования цифр суммы в каждом разряде. Поэтому в худшем случае время распространения переноса составит где ![]() Сумматоры с параллельным переносом. Можно построить сумматор, в котором сложение выполняется как поразрядная операция, и на распространение переноса не требуется дополнительного времени.Затраты оборудования на построение сумматора такого типа, особенно при большом числе разрядов, настолько велики, что в чистом виде он практически не находит применения. Для формирования переноса в таких сумматорах используются две дополнительные функции: функция генерации переноса и функция распространения переноса. Сигнал Сигнал ![]() ![]() Следовательно, функции сумматора можно представить в виде:
где ![]() ![]() ![]()
Функции, выполняемые Устройством быстрого переноса (CRU- Carry Unit - устройство переноса), можно описать следующими логическими выражениями: Для других линий перенос формируется аналогично. Сумматоры с групповым переносом. Сумматор разбивается на несколько групп примерно равной длины. Сигнал переноса, поступающий на вход младшего разряда группы, при наличии условий распространения переноса во всех разрядах данной группы передается на вход младшего разряда соседней, более старшей группы в обход данной группы. В таком сумматоре максимальная задержка распространения переноса определяется задержкой в его младшей и старшей группах, а также цепях обхода остальных групп. 2. Формирование признаков результата При выполнении арифметических операций необходимо проверять признаки результата, отвечающие за истинность полученного результата:
Признак положительного или отрицательного результата формируется по знаковому (старшему) разряду результата. Если он равен 1, то результат отрицательный, если 0 - положительный. Признак нулевого результата формируется с помощью логической функции Признак переполнения формируется из анализа переноса из знакового и старшего разрядов числа в соответствии с выражением
3. Построение умножителей В этом разделе рассмотрим только целочисленное умножение, то есть умножение чисел с фиксированной точкой. В ЭВМ операция умножения чисел с фиксированной точкой с помощью соответствующих алгоритмов сводится к операциям последовательного сложения и сдвига. Произведение двух n-разрядных чисел может иметь 2n значащих разрядов, поэтому при операции умножения целых чисел необходимо предусмотреть возможность формирования в умножителе произведения, имеющего двойную по сравнению с множителями длину.Для выполнения умножения устройство должно содержать регистры множимого, множителя и схемы формирования суммы частичных произведений - так называемый сумматор частичных произведений. Операция умножения n-разрядных чисел состоит из n циклов. В каждом цикле анализируется очередная цифра множителя, и если эта цифра - 1 , то к сумме частичных произведений прибавляется множимое, в противном случае прибавления не происходит. Цикл завершается сдвигом множимого относительно суммы частичных произведений либо суммы частичных произведений относительно неподвижного множимого.В зависимости от способов формирования суммы частичных произведений различают 4 основных метода выполнения умножения. 1. Умножение, начиная с младших разрядов множителя, со сдвигом суммы частичных произведений вправо при неподвижном множимом. Регистр множителя и сумматор частичных произведений при этом должны иметь цепи сдвига вправо. Регистр множимого цепей сдвига может не иметь. Последовательность действий в каждом цикле умножения определяется младшим разрядом регистра множителя, куда последовательно, одна за другой, поступают цифры множителя. Поскольку по мере сдвига множителя вправо старшие разряды регистра множителя освобождаются, он может быть использован для хранения младших разрядов произведения, поступающих из младшего разряда сумматора частичных произведений.
Последовательность действий, как и в предыдущем случае, определяется младшим разрядом регистра множителя. Особенностью метода является то, что регистр множимого и сумматор частичных произведений должны иметь двойную длину. 3. Умножение, начиная со старших разрядов множителя, при сдвиге суммы частичных произведений влево и неподвижном множимом. Регистр множителя и сумматор частичных произведений должны иметь цепи сдвига влево, регистр множимого цепей сдвига не имеет. Последовательность действий определяется старшим разрядом множителя. Особенностью данного метода является возможность применения описанной структуры и для построения делителя. 4. Умножение, начиная со старших разрядов множителя, при сдвиге вправо множимого и неподвижной сумме частичных произведений. Регистр множителя должен иметь цепи сдвиге влево, регистр множимого - цепи сдвига вправо. Последовательность действий на каждом шаге умножения определяется старшим разрядом множителя. Описываемый метод, как и третий, не требует дополнительных цепей сдвига для выполнения деления. Алгоритм умножения чисел, представленных в прямом коде, начиная с младших разрядов со сдвигом суммы частичных произведений вправо:
Методы ускорения умножения. Методы ускорения умножения делятся на аппаратные и логические. Те и другие требуют дополнительных затрат оборудования. К аппаратным методам ускорения умножения относится ускорение выполнения операций сложения и сдвига, введение дополнительных цепей сдвига, позволяющих за 1 такт производить сдвиг информации сразу на несколько разрядов, совмещение во времени операций сложения и сдвига, построение комбинационных схем умножительных устройств, реализующих "табличное" умножение. Среди логических методов наиболее распространены методы, позволяющие за один шаг умножения обрабатывать несколько разрядов множителя. На практике применяются комплексные методы ускорения. Рассмотрим один из способов умножения на два разряда множителя, начиная с младших разрядов. В зависимости от результата анализа пары разрядов множителя предусматриваются следующие действия:
Поскольку при комбинации "11" вычитается одинарное множимое вместо прибавления утроенного множимого, необходимо скорректировать результат. Для корректировки результата к сумме частичных произведений перед выполнением сдвига необходимо было бы прибавить учетверенное множимое. Но после сдвига вправо сумма частичных произведений уменьшается в 4 раза, так что для корректировки на следующем шаге должно быть прибавлено одинарное множимое. Описанный алгоритм представлен в таблице 2. Таблица 2 |
Пара разрядов множителя |
Признак коррекции предыдущей пары |
Признак коррекции для следующей пары |
Знак действия |
Кратность множимому |
00 |
0 |
0 |
- |
0 |
01 |
0 |
0 |
+ |
1 |
10 |
0 |
0 |
+ |
2 |
11 |
0 |
1 |
- |
1 |
00 |
1 |
0 |
+ |
1 |
01 |
1 |
0 |
+ |
2 |
10 |
1 |
1 |
- |
1 |
11 |
1 |
1 |
- |
0 |
Аналогичным образом можно организовать умножение с обработкой за шаг большего числа разрядов множителя. Спроектировать с применением ПЛИС устройство, выполняющее функцию умножения с накоплением. Функциональная схема устройства представлена на рисунке. Разрядность входных данных и регистра накопителя уточняются согласно номеру варианта задания. Отчет должен содержать:
Выполнение деления необходимо при нормировании сигнала, при построении фильтров и т.д. Деление в ЭВМ обычно сводится к выполнению последовательности вычитаний делителя сначала из делимого, а затем образующихся в процессе деления частичных остатков и сдвига частичных остатков. Алгоритмы деления аналогичны алгоритму деления при ручном счете. Рассмотрим особенности деления на примере деления целых чисел. Пусть Z=X/Y, где X - делимое, представляемое обычно двойным словом (2n-1 цифровых разрядов), Y - делитель и Z - частное, представляемые словами, содержащими n-1 цифровых разрядов.Будем для простоты считать, что делению подвергаются целые числа, представляемые в прямом коде. Так как Z - слово, то должно выполнятся неравенство ![]() ![]() ![]() ![]() ![]() ![]() Если результат пробного вычитания больше 0, то ![]() Рассмотрим пример деления. Пусть X = 10101001 и Y= 0111, тогда |X| = 0101001 и |Y|= 0111. Частное Z должно быть представлено прямым кодом с четырьмя двоичными разрядами, старший из которых знаковый.Выполним деление тогда | X| и |Y| обычным способом:В соответствии с правилами деления очередной цифрой частного является 1, если после вычитания получается положительный результат, и 0, если отрицательный. В последнем случае восстанавливается остаток, который был до вычитания. Затем делитель смещается на разряд, и процедура повторяется. Так как знаки делимого и делителя в примере различны, частное от деления Z имеет знак минус. Реализовать деление можно двумя основными способами. 1. Деление с неподвижным делимым и сдвигаемым вправо делителем. ![]() Этот способ деления основан на прямом копировании действий при ручном делении. Структура АЛУ для деления имеет вид, представленный на рисунке. Сначала делимое X заносится в регистр RX, а делитель в старшие разряды RY. Делитель сдвигается вправо путем косой передачи из RY2 в RY1. Вычитание производится суммированием частичных остатков с дополнительным кодом отрицательного делителя. Цифры частного определяются по знаку частичных остатков и фиксируются в регистре RZ1 путем последовательного занесения их в младший разряд RZ1 и сдвига его содержимого с помощью косой передачи из регистра RZ1 в RZ2. Недостатком такого делителя является двойная длина сумматора и его регистров. 2. Деление с неподвижным делителем и сдвигаемым влево делимым. ![]() Этот способ позволяет строить АЛУ с сумматором одинарной длины. Здесь неподвижный делитель Y хранится в RY, а делимое X, сдвигаемое влево относительно Y, находится в двух регистрах: старшие разряды X - в RX1, а младшие - в RX2. Деление начинается со сдвига влево делимого X путем косой передачи его содержимого в регистр сумматора RSm и регистр RX3 и соответствующих прямых передач в RX1 и Rx2. Далее на вход сумматора подается сдвинутое влево делимое, образуется частичный остаток путем сложения с дополнительным кодом отрицательного делителя, и очередная цифра частного заносится в освободившийся при сдвиге X разряд RX2. Делители данного типа широко используются. Алгоритм деления с неподвижным делителем с восстановлением остатка Алгоритм деления с неподвижным делителем без восстановления остатка:
Пункты 6, 7 совпадают с аналогичными пунктами предыдущего алгоритма. Деление без восстановления остатка всегда требует для получения одной цифры частного только сложения или вычитания и сдвига частичного остатка. После завершения всех циклов деления выдается результат, при этом, если остаток отрицателен, он восстанавливается путем подсуммирования Y.Деление чисел, представленных дополнительными кодоми, можно осуществлять, не переходя к модулям, при этом алгоритм деления оказывается подобным рассмотренным. Отличия заключаются в следующем (для деления без восстановления остатка):
|
Знак остатка | Знак делителя | Действие |
+ | + | Вычитание Y |
+ | - | Прибавление Y |
- | + | Прибавление Y |
- | - | Вычитание Y |
Если знак остатка совпадает со знаком делителя, то Zi =1, иначе Zi =0.Деление правильных дробей выполняется так же, как и деление целых чисел. Разница заключается только в том, что делимое имеет, как правило, такую же длину что и делитель. Однако можно предположить, что делимое имеет еще n младших разрядов, равных 0. |
||
![]() |