алгоритм бута

Ответ от Jokerhaus[новичек]
Приводится результат сравнительного анализа комбинационных аппаратных умножителей. реализованных по алгоритму Бута и по обычной матричной схеме. Даются рекомендации по реализации умножителей в зависимости от разрядности операндов.
В современных устройствах расширенной арифметики микропроцессорных СБИС для выполнения операции умножения используются специализированные блоки, так называемые аппаратные умножители. В большинстве случаев они являются асинхронными устройствами и должны обеспечивать формирование произведения за один период тактового сигнала. Анализ существующих алгоритмов аппаратного умножения показал, что наименьшую площадь и наилучшее быстродействие могли бы иметь умножители, построенные по модифицированный алгоритм Бута (умножение сразу на два разряда) [1]. Однако, на этапе формирования частичных произведений декодером Бута, происходит изменение знака множимого, что требует распространения переноса от младшего разряда к старшему из-за сложения проинвертированного числа с единицей. Распространение переноса, при больших разрядностях операндов, занимает много времени, и поэтому недопустимо в быстродействующих схемах. Следует заметить, что сложение частичных произведений в современных многоразрядных умножителях, как правило, осуществляется при помощи одноразрядных сумматоров, соединённых в матрицу с диагональным переносом [2], а итоговое произведение представляется двухрядным кодом (словом сумм и словом переносов). При таком построении исключается распространение переноса от старших битов слагаемых к младшим. В связи с этим распространение переноса на этапе декодирования Бута вносит значительный вклад в суммарное время умножения, и поэтому, если не исключить его, преимущество в быстродействии над другими алгоритмами достигнуто не будет. Более того, будет иметь место значительный проигрыш.
Разработаны два умножителя 24´24 разряда. В основу одного из них лег модифицированный алгоритм Бута, а второй был реализован по обычной матричной схеме [1]. В обоих умножителях произведение представлено двухрядным кодом. Для исключения распространения переноса на этапе декодирования Бута был использован метод корректирующего слова, являющийся модификацией алгоритма конвертирования битов [3]. Суть метода состоит в том, что, если множимое в результате декодирования изменяет знак, то оно поступает на матрицу сумматоров проинвертированным. Необходимое добавление единицы в младший разряд происходит на этапе коррекции возникшей логической ошибки. По сути, этап коррекции сводится к прибавлению корректирующего слова к слову сумм и к слову переносов, получившихся на выходе матрицы сумматоров. Корректирующее слово имеет вид ….х50х40х30х20х1, где хiÎ(0,1), а i – номер частичного произведения. Если i-е частичное произведение получается из множимого, изменившего знак, то соответствующее ему хi принимает значение, равное единице.
Источник: ссылка