Digitális technika 2 - Komplemens szorzás

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

Komplemens szorzó algoritmus

Úgy tűnik, sikerült megértenem, hogy ez MIÉRT így működik, úgyhogy most leírom, hátha másnak is jól jön...

%TOC{"KomplemensSzorzas"}%

Hosszú szöveges

Szeretnénk összeszorozni 2 számot. 1. példa: 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 pl. 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: 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égereményhez hozzáadni:

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

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! :)

-- Simon - 2005.06.17.