Сравнительный анализ простых матричных умножителей и умножителей, реализованных по алгоритму бута

Научный руководитель – В.Д. БАЙКОВ

В современных устройствах расширенной арифметики микропроцессорных СБИС для выполнения операции умножения используются специализированные блоки, так называемые аппаратные умножители. В большинстве случаев они являются асинхронными устройствами и должны обеспечивать формирование произведения за один период тактового сигнала. Анализ существующих алгоритмов аппаратного умножения показал, что наименьшую площадь и наилучшее быстродействие могли бы иметь умножители, построенные по модифицированный алгоритм Бута (умножение сразу на два разряда) [1]. Однако, на этапе формирования частичных произведений декодером Бута, происходит изменение знака множимого, что требует распространения переноса от младшего разряда к старшему из-за сложения проинвертированного числа с единицей. Распространение переноса, при больших разрядностях операндов, занимает много времени, и поэтому недопустимо в быстродействующих схемах. Следует заметить, что сложение частичных произведений в современных многоразрядных умножителях, как правило, осуществляется при помощи одноразрядных сумматоров, соединённых в матрицу с диагональным переносом [2], а итоговое произведение представляется двухрядным кодом (словом сумм и словом переносов). При таком построении исключается распространение переноса от старших битов слагаемых к младшим. В связи с этим распространение переноса на этапе декодирования Бута вносит значительный вклад в суммарное время умножения, и поэтому, если не исключить его, преимущество в быстродействии над другими алгоритмами достигнуто не будет. Более того, будет иметь место значительный проигрыш.

Разработаны два умножителя 24´24 разряда. В основу одного из них лег модифицированный алгоритм Бута, а второй был реализован по обычной матричной схеме [1]. В обоих умножителях произведение представлено двухрядным кодом. Для исключения распространения переноса на этапе декодирования Бута был использован метод корректирующего слова, являющийся модификацией алгоритма конвертирования битов [3]. Суть метода состоит в том, что, если множимое в результате декодирования изменяет знак, то оно поступает на матрицу сумматоров проинвертированным. Необходимое добавление единицы в младший разряд происходит на этапе коррекции возникшей логической ошибки. По сути, этап коррекции сводится к прибавлению корректирующего слова к слову сумм и к слову переносов, получившихся на выходе матрицы сумматоров. Корректирующее слово имеет вид ….х₅0х₄0х₃0х₂0х₁, где х_iÎ(0,1), а i – номер частичного произведения. Если i-е частичное произведение получается из множимого, изменившего знак, то соответствующее ему х_i принимает значение, равное единице.

Быстродействие обоих умножителей, спроектированных по технологии 0.8 мкм, составило 9 нс. Однако умножитель Бута имеет площадь, примерно в два раза меньшую. На основании полученных данных был произведен сравнительный анализ умножителей Бута и обычных матричных умножителей различных разрядностей. Результатом анализа является следующее. Декодирование Бута вносит значительный вклад в быстродействие умножителя, что особенно заметно в схемах относительно небольшой разрядности. Умножители 16´16 и менее разрядов, реализованные по алгоритму Бута, имеют проигрыш по быстродействию перед обычной матричной реализацией. Напротив, умножителя 32´32 разряда и более имеют преимущество перед обычными матричными умножителями, как по быстродействию, так и по площади (для умножителя 54´54 разряда выигрыш по быстродействию составит 3 нс, выигрыш по площади составит порядка 30%-40%). Следовательно умножители 24´24 разряда и более следует строить по алгоритму Бута, быстродействующие умножители меньшей разрядности лучше реализовать по обычной матричной схеме.

Список литературы

1. 
   Угрюмов Е.П. Цифровая схеиотехника. – СПб:”БХВ-Петербург”,2001. –528 с.:ил.
   
2. 
   Микропроцессорные БИС и микро-ЭВМ. Построение и применение / под редакцией А.А.Васенкова. –Ь.: Советское радио, 1980.
   
3. 
   A Carry-Free 54b´54b Multiplier Using Equivalent Bit Conversion Algorithm / Y.Kim, B.-S Song, J.Grosspietsch, and S.F. Gilling // IEEE Solid-State Circuits, 2001. –V.SSC-36.- №10. –pp. 1538-1546.
   

жүктеу/скачать 29.35 Kb.

Достарыңызбен бөлісу: