„Digitális technika 2 - Komplemens szorzás” változatai közötti eltérés
aNincs szerkesztési összefoglaló |
aNincs szerkesztési összefoglaló |
||
| 1. sor: | 1. sor: | ||
{{vissza|Digitális technika 2}} | |||
== | ==1. Példa:== | ||
Szeretnénk összeszorozni 2 számot | 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 * 1111 | ||
| 13. sor: | 15. sor: | ||
------------------ | ------------------ | ||
1. | '''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: | Elvileg tehát már el tudnánk végezni a szorzást: | ||
| 26. sor: | 28. sor: | ||
Stb... | Stb... | ||
Az összeadás eredménye pedig tényleg -15. | Az összeadás eredménye pedig tényleg -15. | ||
2. | 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. | 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. | ==2. Példa:== | ||
Szeretnénk összeszorozni 2 számot: 1011 * 000111000 = ? | |||
Innentől már célszerűbb visszafelé gondolkodni | 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ó). | 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 | 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. | 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. | ||
| 58. sor: | 66. sor: | ||
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. | 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ő: | '''Az algoritmus tehát a következő:''' | ||
# 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.) | |||
# 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). | 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 | Legyen a tetszőleges (itt nem is fontos, hogy bináris) szám. Ezt szeretnénk megszorozni | ||