Матричен множител

Двоично умножение [редактиране]

math math

Умножението в двоичната бройна система е точно същото като в десетичната - според схемата умножение на колона. Ако мултипликантът е [math] k [/ math] bit, а коефициентът е [math] n [/ math] bit, тогава за да формирате продукта, трябва да изчислите [math] n [/ math] частични продукти и да добавите заедно.

Изчисляване на частични продукти [редактиране]

В двоична система, за да изчислите частичен продукт, можете да използвате логическите елементи [math] \ & [/ math] - конюктори. Всеки частичен продукт [math] (m_i) [/ math] е резултат от [math] k [/ math] логически операции [math] \ & [/ math] (между текущия [math] i [/ math], където [math] i = 1.n [/ math], мултипликационният бит и всички [math] k [/ math] цифри на множителя) и преместват резултата от логическата операция вляво с броя на цифрите, съответстващи на теглото на текущия умножител бит. Матричният множител изчислява частичните произведения, използвайки формулата:

[математика] m_i = 2 ^ (a \ & b_i), (i = 1.n) [/ math]

Сумиране на частични продукти [редактиране]

На този етап добавянето на всички частични продукти [math] m [/ math] .

Схема [редактиране]

частични продукти

Схематична диаграма на умножител, който реализира алгоритъма на двоично умножение в колона за две четирицифрени числа е показана на фигурата. Формирането на частични произведения се извършва посредством логически елементи [math] \ & [/ math]. Пълните едноцифрени суматори осигуряват формирането на резултатни битове. Дълбочината на бита на резултата - [math] l [/ math] се определя от битовата ширина на множителя - [math] n [/ math] и множителя - [math] k [/ math]:


Всички конюктори работят паралелно. Пълните еднобитови суматори осигуряват побитово добавяне на резултатите от конюнкции и пренасяне от предишните битови суматори В горната схема се използват четирибитови серийни предаватели за прехвърляне. Времето за изпълнение на операцията за умножение се определя от времето на разпространение на носи към изходния бит [math] p8 [/ math] .

Матричен множител [редактиране]

Ако се вгледате внимателно в диаграмата матричен множител (англ. двоичен множител), тогава можете да видите, че той образува матрица, образувана от проводници, по които се предават цифрите на числото [math] A [/ math] и числото [math] B [/ math]. Портите [math] \ & [/ math] са разположени в пресечните точки на тези проводници. Поради тази причина множителите, реализирани съгласно тази схема, се наричат ​​матрични множители.

Частичните продукти се изчисляват на [math] n [/ math] стъпки. Пренасянето включва добавяне на [math] n - 1 [/ math] стъпки. Последното добавяне може да се направи в [math] O (\ log n) [/ math] .

В резултат на това общото време на работа:

[math] O (n) + O (n) + O (\ log n) = O (n) [/ math]

Времето за работа на веригата може да бъде намалено, ако суматорите не са подредени последователно един след друг, както се предполага от алгоритъма, показан на първата фигура (обща диаграма), но частичните продукти се сумират по двойки, след което двойките на частичните продукти се сумират и т.н. В този случай времето за изпълнение на операцията за умножение ще бъде значително намалено.

Особено забележима е печалбата в производителността при изграждането на многобитови множители, но нищо не е безплатно. В замяна на скорост ще трябва да платите с увеличаване на битовата ширина на суматорите, което означава сложността на веригата.

Има по-бързи начини за умножаване на две числа, например умножение с дърво Уолас, което работи [math] O (\ log n) [/ math] .