ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 6843
Скачиваний: 22
265
Тут вжито наступні позначення: X, Y, Z - множене, множник і добуток відповідно, Zi - сума часткових добутків на і-му етапі, Y(n-i-1) - (n-і-1)-й розряд множника, п - кількість розрядів операндів без врахування знакового розряду.
Алгоритм можна представити блок-схемою, показаною на рис. 7.27.
Приклад:
Необхідно помножити два числа (без знакового розряду):
Х=01010101; Y=01101011.
Хід операцій проілюстровано в табл. 7.5.
Таблиця 7.5
|
і |
Zi |
Y(Y(n-i-l)) |
Хі+1 |
Zi+l=Zi+Xi+l*Y(n-i-l) |
|
0 |
0000 0000 0000 0000 |
0110 1011 |
0010 1010 1000 0000 |
0000 0000 0000 0000 |
|
1 |
0000 0000 0000 0000 |
0110 1011 |
000101010100 0000 |
000101010100 0000 |
|
2 |
0001 01010100 0000 |
0110 1011 |
0000 1010 1010 0000 |
0001 1111 1110 0000 |
|
3 |
0001 1111 1110 0000 |
0110 1011 |
0000 0101 0101 0000 |
0001 1111 1110 0000 |
|
4 |
0001 1111 1110 0000 |
0110 1011 |
0000 0010 1010 1000 |
0010 0010 1000 1000 |
|
5 |
0010 0010 1000 1000 |
0110 1011 |
0000 000101010100 |
0010 0010 1000 1000 |
|
6 |
0010 0010 1000 1000 |
0110 1011 |
0000 0000 1010 1010 |
0010 001100110010 |
|
7 |
0010 0011 0011 0010 |
0110 1011 |
0000 0000 0101 0101 |
0010 0011 1000 0111 |
Таким чином 0101 0101 .01101011=0010 0011 1000 0111.
Базова структура багатотактового АОП множення двійкових чисел за описаним методом наведена на рис. 7.28.
266
Тут СМЧД - суматор часткових добутків. Множник зберігається в регістрі множника, а множене - в регістрі множеного. Обидва ці регістри є n-розрядними. Суматор часткових добутків є накопичувальним суматором, тобто на його виході є регістр з оберненим зв'язком як це показано на рис. 7.22, який є 2п-розрядним. В кожному такті вміст регістрів множника та множеного зсувається на один розряд вліво в сторону старших розрядів. Розряд в крайньому лівому тригері регістра множника випадає, а на його місце поміщається наступний розряд множника, який керує операцією СМЧД, тобто вказує чи є в даному такті додавання, чи його немає. В порівнянні з базовою структурою АОП множення першим методом тут СМЧД обов'язково має бути 2п-розрядним.
7.13.2.4. Багатотактовий пристрій множення двійкових чисел з старших розрядів при нерухомому множеному з зсувом суми часткових добутків вліво
Алгоритм множення двійкових чисел, який реалізує цей метод, описується наступним ітераційним виразом:
Тут вжито наступні позначення: X, Y, Z - множене, множник і добуток відповідно, Zi- сума часткових добутків на і-му етапі, Y(n-i-1) - (n-і-1)-й розряд множника, n - кількість розрядів операндів без врахування знакового розряду.
Алгоритм можна представити блок-схемою, показаною на рис. 7.29.
Приклад:
Множимо два числа (без знакового розряду):
Х=0101 0101; Y=01101011.
Хід операцій проілюстровано в табл. 7.6.
267
Таблиця 7.6
|
і |
Zi |
Y (Y(ri-i-l)) |
2*Zi |
Zi+l=2*Zi+ Xi+l*Y(n-i-l) |
|
0 |
0000 0000 0000 0000 |
0110 1011 |
0000 0000 0000 0000 |
0000 0000 0000 0000 |
|
1 |
0000 0000 0000 0000 |
0110 1011 |
0000 0000 0000 0000 |
0000 0000 01010101 |
|
2 |
0000 0000 01010101 |
0110 1011 |
0000 0000 1010 1010 |
0000 0000 1111 1111 |
|
3 |
0000 0000 1111 1111 |
0110 1011 |
0000 0001 1111 1110 |
0000 0001 1111 1110 |
|
4 |
0000 0001 1111 1110 |
0110 1011 |
0000 0011 1111 1100 |
0000 0100 0101 0001 |
|
5 |
0000 0100 0101 0001 |
01101011 |
0000 1000 1010 0010 |
0000 1000 1010 0010 |
|
6 |
0000 1000 1010 0010 |
0110 1011 |
0001 0001 0100 0100 |
0001 0001 1001 1001 |
|
7 |
0001 0001 1001 1001 |
0110 1011 |
0010 0011 0011 0010 |
00100011 10000111 |
Таким чином 0101 0101 .01101011=0010 0011 1000 0111.
Базова структура багатотактового АОП множення двійкових чисел за описаним методом наведена на рис. 7.30.
Тут СМЧД - суматор часткових добутків. Множник зберігається в регістрі множника, а множене - в регістрі множеного. Перший з цих регістрів є n-розрядним, а другий - 2п-розрядним. Суматор часткових добутків є накопичувальним суматором, тобто на його виході є регістр з оберненим зв'язком як це показано на рис. 7.22, який також є 2п-розрядним. Перед початком виконання операції множене знаходиться в лівій частині регістра множеного. В кожному такті вміст регістра множеного та вміст СМЧД зсуваються на один розряд вправо в сторону молодших розрядів. Розряд в крайньому лівому тригері регістра множника випадає, а на його місце поміщається наступний розряд множника, який керує операцією СМЧД, тобто вказує чи є в даному такті додавання, чи його немає. В порівнянні з базовою структурою АОП множення першим методом тут, як в базовій структурі АОП множення другим методом, регістр множеного та СМЧД обов'язково мають бути 2п-розрядними.
В усіх чотирьох розглянутих структурах АОП множення двійкових чисел час виконання операції tмн = ntcM де tcM- затримка СМЧД.
7.13.2.5. Багатотактовіш пристрій прискореного множення
Одним із методів прискореного множення є одночасний аналіз декількох розрядів множника. Це може бути одночасний аналіз двох, трьох і більшої кількості розрядів. Для пояснення суті методу на рис. 7.31 показана схема багатотактового пристрою множення
268
з одночасним аналізом двох розрядів множника. Тут схема аналізу СА проводить аналіз двох розрядів множника і вказує СМЧД тип виконуваної операції: додавання відсутнє, додається значення множеного, додається подвоєне значення множеного, додається потроєне значення множеного. Зсув в регістрах відбувається одночасно на два розряди.
Подібним чином може бути реалізований пристрій множення з одночасним аналізом двох розрядів множника з застосуванням всіх чотирьох вище розглянутих методів множення. При множенні чисел, представлених в доповняльному коді, доцільно використовувати пристрій, який реалізує алгоритм Бута, розглянутий в розділі 4.
Часто застосовуються асинхронні пристрої множення з одночасним аналізом всіх розрядів множника. В таких пристроях кількість тактів визначається кількістю одиниць в множнику.
Приклад:
Х= 101001110001
Y= 110000111110.
На позиціях нулів у множнику Y додавання не виконується, лише зсув на відповідну кількість розрядів.
Множник Y можна представити в вигляді Y = 1100010000(-1)0. Тоді взамін 7 додавань необхідно виконати 3 додавання і одне віднімання. Особливо ефективний цей метод при виконанні множення на константи.
7.13.2.6. Однотактові пристрої множення двійкових чисел з фіксованою комою
Як вже було показано, побудова однотактових операційних пристроїв передбачає апаратне відображення просторового графа алгоритму виконання операції комбінаційними схемами, які виконують функціональні оператори алгоритму і з'єднані між собок відповідно до графа алгоритму. Тому структура однотактового пристрою множення двійкових чисел з фіксованою комою повторить відповідну структуру графа алгоритму наведеного на рис. 4.7, як це показано на рис. 7.32.
269
Тут вхідні дані X та Y поступають в регістри РгХ та PrY, а з них на пристрої логічного множення AND, на яких формуються логічні добутки множеного X на розряди множника Y. Ці логічні добутки з зсувом на відповідну кількіть розрядів поступають на входи комбінаційної схеми багатомісного додавання часткових добутків БДЧД, результат множення з якої поступає в регістр PrZ, а з нього на вихід пристрою.
Комбінаційна схема багатомісного додавання часткових добутків БДЧД реалізує алгоритми, детально розглянуті в п. 4.4.4.2, де кожному оператору двомісного однорозряд-ного двійкового додавання має бути поставлений у відповідність однорозрядний суматор двійкових чисел, який реалізує логічні вирази відповідно до табл. 4.5.
7.13.2.7. Конвеєрні пристрої множення двійкових чисел з фіксованою комою
При побудові конвеєрного операційного пристрою множення двійкових чисел з фіксованою комою кожному функціональному оператору алгоритму ставиться у відповідність комбінаційна схема, яка його виконує, і, крім того, комбінаційні схеми, які реалізують функціональні оператори ярусів потокового графа алгоритму, розділяються конвеєрними регістрами. Алгоритм множення виконується над вхідними даними при їх однократному проходженні через конвеєрний операційний пристрій.
Якщо вибрати для реалізації граф алгоритму послідовного попарного додавання часткових добутків, отриманих починаючи з аналізу молодших розрядів множника, який представлений на рис. 4.8, то структура і-го яруса конвеєрного операційного пристрою множення двійкових чисел з фіксованою комою буде мати вигляд, показаний рис. 7.33.