„Digitális technika 2 - Komplemens szorzás” változatai közötti eltérés
Új oldal, tartalma: „{{GlobalTemplate|Villanyalap|KomplemensSzorzas}} ==Komplemens szorzó algoritmus== Úgy tűnik, sikerült megértenem, hogy ez MIÉRT így működik, úgyhogy most le…” |
→Komplemens szorzó algoritmus: formázást rendberaktam |
||
| 1. sor: | 1. sor: | ||
{{GlobalTemplate|Villanyalap|KomplemensSzorzas}} | {{GlobalTemplate|Villanyalap|KomplemensSzorzas}} | ||
Ú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... | Ú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... | ||
===Hosszú szöveges=== | ===Hosszú szöveges=== | ||
| 11. sor: | 7. sor: | ||
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: | 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 | |||
+ 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. | 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. | ||
| 25. sor: | 19. sor: | ||
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: | ||
1011 * 1111 | |||
----------- | |||
!->11011 | |||
!->11011 | + 10110 | ||
+ 10110 | -------- | ||
-------- | 10001 | ||
Stb... | Stb... | ||
| 56. sor: | 48. sor: | ||
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: | 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 | | ||
| 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. | 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. | ||
| 80. sor: | 70. sor: | ||
===Formális matematikai indoklás=== | ===Formális matematikai indoklás=== | ||
Legyen a tetszőleges (itt nem is fontos, hogy bináris) szám. Ezt szeretnénk megszorozni <math>b=-b_3 2^3 + b^2 2^2 + b^1 2^1 + b^0 2^0</math> számmal (az egyszerűség kedvéért legyen 4 bites). A szorzót kicsit átalakítjuk. Felhasználva, hogy <math>b_i 2^i = b_i 2^{i+1}</math>: <math>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</math>, és ezeket csoportosítva <math>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</math>, ez pedig felírható mint <math>b=c_3 2^3 + c_2 b^2 + c_1 b^1 + c_0 b^0</math>, 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. | Legyen a tetszőleges (itt nem is fontos, hogy bináris) szám. Ezt szeretnénk megszorozni | ||
<math>b=-b_3 2^3 + b^2 2^2 + b^1 2^1 + b^0 2^0</math> | |||
számmal (az egyszerűség kedvéért legyen 4 bites). A szorzót kicsit átalakítjuk. Felhasználva, hogy | |||
<math>b_i 2^i = b_i 2^{i+1}</math>: | |||
<math>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</math>, és ezeket csoportosítva | |||
<math>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</math>, | |||
ez pedig felírható mint | |||
<math>b=c_3 2^3 + c_2 b^2 + c_1 b^1 + c_0 b^0</math>, | |||
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! :) | Remélem érthető volt :) Ha bármi hibát találsz benne, vagy szólj, vagy még jobb, ha kijavítod! :) | ||