Читальный зал -->  База цифровых устройств 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 [ 32 ] 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176

Перемножение в пределах зон дает частичные произведения р = P5iP4iP3iP2iPiiPoi и Р2 = P52P P32P22Pi2P02- Для получения Конечного значения произведения эти частичные произведения нужно сложить с учетом их взаимного положения (сдвига одного относительно другого).

Схема, реализующая указанный принцип, изображена на рис. 2 38, в. В ней использовано условное обозначение МСБ (рис. 2.38, б). Для обишости оба блока размерности 4x2 показаны как МСБ, хотя первый может быть просто множительным блоком, т. к. для него слагаемые С и D имеют нулевое значение.

Схемы ускоренного умножения

Для ускорения умножения разработан ряд алгоритмов, большой вклад в эти разработки внес Э. Бут (Е. Boot). Рассмотрим процесс умножения по так называемому модифицированному алгоритму Бута (умножение сразу на два разряда).

Из изложенного выше видно, что основную задержку в процесс выработки произведения вносит суммирование частичных произведений. Уменьщение их числа сократило бы время суммирования. К этому приводит алгоритм, основанный на следующих рассуждениях.

Пусть требуется вычислить произведение

Р = А x В = А x (b i2 - + b -22 - +...+b 2)). (а)

Непосредственное воспроизведение соотношения (а) связано с выработкой частичных произведений вида Abj2 (i = 0...n - 1). Число таких произведений равно разрядности множителя п.

Выражение (а) можно видоизменить с помощью соотношения

bi2 = bi2i+ - 2Ъ0-, (б)

справедливость которого очевидна.

Это соотношение позволяет разреживать последовательность (спектр) степеней в сумме частичных произведений. Можно, например, исключить четные степени, как показано на рис. 2.39, о Исключение четных (или нечетных) степеней не только изменяет значения оставшихся частичных произведений, но и сокращает их число примерно вдвое, что, в конечном счете, ускоряет выработку произведения. Для того чтобы разнести по соседям член со степенью 2 , расширим разрядную сетку, введя слагаемое b i2 (нулевой разряд с номером -1).

Оставшиеся частичные произведения имеют вид

R, = A(-2bi+,-Hbi-l-bi-.,)2.

Глава г £7

Так как число частичных произведений уменьшилось примерно вдвое, при применении этого алгоритма говорят об умножении сразу на два разряда.

Рис. 2.39. К пояснению принципа быстрого умножения срезу на два разряда (в) и схема быстрого умножения (б)

Для всех возможных сочетаний b,+i, bi, bj-, можно составить таблицу (табл. 2.14) частичных произведений.

Таблица 2.14

			Значение скобки		Операция для получения Ri/2
					Заменить А нулем
					Скопировать А
					Скопировать А
					Сдвинуть А влево
					Сдвинуть А влево и преобразовать в дополнительный код
					Преобразовать А в дополнительный код
					Преобразовать А в дополнительный код
					Заменить А нулем

Пример

Пусть требуется умножить 101 Ог на 01112, т. е. 10 х 7. При разреживании частичных произведений оставим только нечетные, как показано на рис. 2.39, а Расширив разрядную сетку множителя, имеем В = b,b3b2bibob-ib-2 = 0011100.

Первому частичному произведению соответствует тройка bob-ib-2 = 100. Из табл. 2.14 получаем, что этой тройке соответствует частичное произаедение- -2А 2 = -А. для получения которого требуется перевести А в дополнительный код. Сама величина А в пределах разрядной сетки произведения должна быть записана кек 00001010. ее обратный код 11110101 и дополнительный код 11110110.

Второму частичному произведению соответстаует тройка b2bibo =111. следовательно, второе чвстичное произведение равно нулю (табл. 2.14).

Третьему частичному произведению соответствует тройка Ь4ЬзЬ2 = 001, следовательно, оно имеет вид А 2 = 01010000

Для получения результата заданного умножения требуется сложить частичные произведения:

11110110 01010000

01000110 = 2 + 2 + 2 = 64 + 4 + 2 =70.

Схема, реализующая алгоритм быстрого умножения сразу на два разряда, показана на рис. 2.39, б. Множимое А поступает в этой схеме на ряд преобразователей, заготавли- 1 вающих все возможные варианты частичных произведений (-2А, -А, 2Л), кроме самого А и нуля, которые не требуют схемной реализации. Множитель В поступает на логический преобразователь ЛП, который анализирует

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 [ 32 ] 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176

ООО «Мягкий Дом» - это Отечественный производитель мебели. Наша профильная продукция - это диваны еврокнижка. Каждый диван можем изготовить в соответствии с Вашими пожеланияи (размер, ткань и материал). Осуществляем бесплатную доставку и сборку.



Звоните! Ежедневно!
 (926)274-88-54 
Продажа и изготовление мебели.

Копирование контента сайта запрещено.
Авторские права защищаются адвокатской коллегией г. Москвы.