Digitális technika 2 - Komplemens szorzás

← Vissza az előző oldalra – Digitális technika 2

1. Példa:

Szeretnénk összeszorozni 2 számot: 1011 * 1111 = ?

Ezt lehetne úgy csinálni, hogy sokszor egymás alá írjuk az 1011-et eltolva:

      1011 * 1111
      -----------
     1011
    1011
   1011
+ 1011
------------------

1. Probléma: A komplemens szorzás csak meghatározott hosszúságú számokra működik. Viszont például 1011 komplemens kódban ugyanannyi, mint 11011 (bizonyítás: -16+8+valamennyi = -8+valamennyi). Tehát ha összeadáskor az egyik összeadandónak már nincs valahol számjegye, akkor oda az adott szám előjelbitjét kell írni.

Elvileg tehát már el tudnánk végezni a szorzást:

   1011 * 1111
   -----------
!->11011
+  10110
--------
   10001

Stb...

Az összeadás eredménye pedig tényleg -15.

Megjegyzés: miután a komplemens összeadás pont attól működik, hogy adott hosszúságú számoknál lehagyjuk az utolsó (maradékként keletkező) bitet, ezért ezt hagyjuk is le!

2. Probléma: 1111 ugye -1. Szóval ahhoz, hogy -5-öt -1-gyel összeszorozzunk, kb. 4 összeadást kellene elvégezni???

Innen jön a kétbitfigyeléses algoritmus alapötlete. Az 1111 4 számjegyen (mint fent láttuk) ugyanannyi, mint az 1 1 számjegyen komplemens kódban (ahol is az első és egyetlen bitnek van -1-es súlya). Szóval ha a szorzó végén sok 1-es van, azokat leszedhetjük róla az eredmény megváltozása nélkül! Ha sok 0 van a végén, azokat szintén.

2. Példa:

Szeretnénk összeszorozni 2 számot: 1011 * 000111000 = ?

Innentől már célszerűbb visszafelé gondolkodni: 1011 * 0 = 0000. Az előző indoklás alapján 1011 * 000 is 0000. De amikor a szorzó elejére egy 1-est írunk, megváltoztatjuk a súlyozást! Az 1-es -8-as súlyozással fog számítani, tehát az egyenlet bal oldalából 8-szor kivontuk az 1011-et. Ahhoz, hogy a végeredmény továbbra is jó legyen, a jobb oldalból is kivonunk ennyit. Azaz hozzáadunk 8-szor 0101-et (ami az 1011 komplemense). Az egyenletünk tehát: 1011 * 1000 = 0101000. A 3 nulla a 8-cal való szorzás miatt jött be. (-5 * -8 = +40)

A szorzóra rápakolunk még 2 egyest (mint tudjuk, ezt megtehetjük, ilyenkor ugyanis kivonunk 2^n-t, és hozzáadunk 2*2^(n-1)-t (az utolsó előttivé vált számjegy előjelváltása miatt jön be a 2-es szorzó).

1011 * 111000 = 0101000. Ha ezután a szorzó elejére 0-t írunk, akkor az utolsó 1-es súlya ellentettjére változik. Ennek az 1-esnek a súlyozása fele akkora, mint ha 1-est írnánk 0-k elejére azonos hosszúságú számoknál, viszont kétszer annyit változik (pozitívra negatívról és nem 0-ról negatívra). Tehát most 1011000000-t fogunk a végeredményhez hozzáadni:

1011 * 0111000 = 0101000 (előző végeredmény) + 1011000000 = 1011101000 (=-280 = 56*-5, 56=000111000).

Digitalizálás

Adott tehát a módszer: végig kell menni a szorzón, figyelni az 1-0 és 0-1 átmeneteket, és a szorzandót megfelelő 2-hatványokkal szorozva hozzáadogatni a leendő eredményhez. Ez így nem tűnik egyszerűen megvalósíthatónak digitális eszközökkel, tehát kicsit átfogalmazzuk.

Tegyük fel, szeretnénk két n bites számot összeszorozni. Az egyiket (a szorzandót) eltároljuk egy n bites regiszterben, a másikat belerakjuk egy 2n+1 bites shiftregiszter végébe:

                   +-- ez lesz az eredmény utolsó számjegye
                   |
                   V
|---|---|---|---||---|---|---|---||---|
| 0 | 0 | 0 | 0 || 1 | 0 | 1 | 1 || 0 |
|---|---|---|---||---|---|---|---||---|
                   |           |
                   +-----------+
                      szorzó

Ez azért jó, mert így egy regiszter léptetésével végig tudunk menni a szorzón, és ellenőrizni 2 bitenként (a műveletsor végére ez "kipotyog" a regiszter végén), ráadásul még az eredményhez is megfelelő eltolással tudjuk a szorzandót hozzáadni vagy kivonni.

Az algoritmus tehát a következő:

1. Megnézzük a 2 utolsó bitet. ha ez 10, akkor kivonjuk a regiszter baloldali n bitjéből a szorzandót, ha 01, akkor hozzáadjuk. Ha 00 vagy 11, akkor nem csinálunk semmit. Az összeadás és kivonás szigorúan n bites, további maradékok érdektelenek. (mivel komplemens.)
2. A regiszter tartalmát jobbra léptetjük úgy, hogy a bal oldalra mindig olyan bit kerül, mint amilyen volt (pl. 10-ból 110). Végülis így csinálunk hosszabb számot a rövidebből komplemens kódban.

Léptetést n-szer végzünk el (látható, hogy ekkor a leendő utolsó számjegy valóban a helyére kerül).

Formális matematikai indoklás

Legyen a tetszőleges (itt nem is fontos, hogy bináris) szám. Ezt szeretnénk megszorozni

$b=-b_{3}2^{3}+b_{2}2^{2}+b_{1}2^{1}+b_{0}2^{0}$

számmal (az egyszerűség kedvéért legyen 4 bites). A szorzót kicsit átalakítjuk. Felhasználva, hogy:

$b_{i}2^{i}=b_{i}2^{i+1}$

$b=-b_{3}2^{3}+b_{2}2^{3}-b_{2}2^{2}+b_{0}2^{2}+b_{0}2^{1}-b_{0}2^{0}$, és ezeket csoportosítva

$b=(b_{2}-b_{3})2^{3}+(b_{1}-b_{2})2^{2}+(b_{0}-b_{1})2^{1}+(b_{-1}-b_{0})2^{0}$,

ez pedig felírható mint

$b=c_{3}2^{3}+c_{2}b^{2}+c_{1}b^{1}+c_{0}b^{0}$,

ahol a c-k a szorzó szomszédos bitjeiből nyerhetők ki. Miután pedig a c-ket a szorzóból kinyertük, az összeadást és a léptetést elvégezve a végeredményt kapjuk.

Remélem érthető volt :) Ha bármi hibát találsz benne, vagy szólj, vagy még jobb, ha kijavítod! :)