Digitális technika 2 - Komplemens szorzás - Laptörténet

Szikszayl, 2014. március 13., 13:57-n

2014-03-13T13:57:36Z

← Régebbi változat		A lap 2014. március 13., 15:57-kori változata
95. sor:		95. sor:
	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! :)

	[[~~Category~~:~~Villanyalap~~]]		[[Kategória:Villamosmérnök]]

David14, 2014. január 19., 02:04-n

2014-01-19T02:04:26Z

← Régebbi változat		A lap 2014. január 19., 04:04-kori változata
1. sor:		1. sor:
	{{vissza\|Digitális technika 2}}		{{vissza\|Digitális technika 2}}
			{{noautonum}}

	==1. Példa:==		==1. Példa:==

David14: /* Formális matematikai indoklás */

2014-01-19T02:03:56Z

Formális matematikai indoklás

← Régebbi változat		A lap 2014. január 19., 04:03-kori változata
76. sor:		76. sor:
	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

	<math>b=-b_3 2^3 + ~~b^2~~ 2^2 + ~~b^1~~ 2^1 + ~~b^0~~ 2^0</math>		<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		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_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_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>,		<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>,

David14, 2014. január 19., 01:57-n

2014-01-19T01:57:02Z

← Régebbi változat		A lap 2014. január 19., 03:57-kori változata
1. sor:		1. sor:
	~~Ú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...~~		{{vissza\|Digitális technika 2}}

	==~~=Hosszú szöveges=~~==		==1. Példa:==

	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: 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. ~~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 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. ~~(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!)~~		Az összeadás eredménye pedig tényleg -15.

	2. ~~probléma~~: 1111 ugye -1. Szóval ahhoz, hogy -5-öt -1-gyel összeszorozzunk, kb. 4 összeadást kellene elvégezni???		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. ~~példa~~: 1011 * 000111000 = ?		==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)		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 ~~végereményhez~~ hozzáadni:		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).

	~~1011 * 0111000~~ = ~~0101000 (előző végeremé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.)
	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.)		# 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.

	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).		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===		==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

David14, 2014. január 19., 01:28-n

2014-01-19T01:28:27Z

← Régebbi változat		A lap 2014. január 19., 03:28-kori változata
88. sor:		88. sor:
	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! :)

	~~[[Category:Digitális technika 2]]~~
	[[Category:Villanyalap]]		[[Category:Villanyalap]]

David14, 2013. február 24., 00:50-n

2013-02-24T00:50:36Z

← Régebbi változat		A lap 2013. február 24., 02:50-kori változata
1. sor:		1. sor:
	~~{{GlobalTemplate\|Villanyalap\|KomplemensSzorzas}}~~
	~~[[Category:Digitális technika 2]]~~

	Ú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...

91. sor:		88. sor:
	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! :)

	-- [[~~SafarSimon\|Simon~~]] ~~- 2005.06.17.~~		[[Category:Digitális technika 2]]


	[[Category:Villanyalap]]		[[Category:Villanyalap]]

David14: David14 átnevezte a(z) KomplemensSzorzas lapot a következő névre: Digitális technika 2 - Komplemens szorzás

2013-02-24T00:49:37Z

David14 átnevezte a(z) KomplemensSzorzas lapot a következő névre: Digitális technika 2 - Komplemens szorzás

← Régebbi változat	A lap 2013. február 24., 02:49-kori változata
(Nincs különbség)

Palotasb, 2012. december 10., 12:58-n

2012-12-10T12:58:17Z

← Régebbi változat		A lap 2012. december 10., 14:58-kori változata
1. sor:		1. sor:
	{{GlobalTemplate\|Villanyalap\|KomplemensSzorzas}}		{{GlobalTemplate\|Villanyalap\|KomplemensSzorzas}}
			[[Category:Digitális technika 2]]

	Ú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...

Palotasb: /* Komplemens szorzó algoritmus */ formázást rendberaktam

2012-12-08T15:49:57Z

Komplemens szorzó algoritmus: formázást rendberaktam

← Régebbi változat		A lap 2012. december 8., 17:49-kori változata
1. sor:		1. sor:
	{{GlobalTemplate\|Villanyalap\|KomplemensSzorzas}}		{{GlobalTemplate\|Villanyalap\|KomplemensSzorzas}}

	~~==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...		Ú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===		===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:

	~~<pre>~~		1011 * 1111
	1011 * 1111		-----------
	-----------		1011
	1011		1011
	1011		1011
	1011		+ 1011
	+ 1011		------------------
	------------------
	~~</pre>~~

	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:

	~~<pre>~~		1011 * 1111
	1011 * 1111		-----------
	-----------		!->11011
	!->11011		+ 10110
	+ 10110		--------
	--------		10001
	10001
	~~</pre>~~

	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:

	~~<pre>~~		+-- ez lesz az eredmény utolsó számjegye
			\|
	\|- ez lesz az eredmény utolsó számjegye		V
	V		\|---\|---\|---\|---\|\|---\|---\|---\|---\|\|---\|
	\|---\|---\|---\|---\|\|---\|---\|---\|---\|\|---\|		\| 0 \| 0 \| 0 \| 0 \|\| 1 \| 0 \| 1 \| 1 \|\| 0 \|
	\| 0 \| 0 \| 0 \| 0 \|\| 1 \| 0 \| 1 \| 1 \|\| 0 \|		\|---\|---\|---\|---\|\|---\|---\|---\|---\|\|---\|
	\|---\|---\|---\|---\|\|---\|---\|---\|---\|\|---\|		\| \|
	\| \|		+-----------+
	------------		szorzó
	szorzó
	~~</pre>~~

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

Unknown user: Ú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…”

2012-10-22T11:54:14Z

Ú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…”

Új lap

{{GlobalTemplate|Villanyalap|KomplemensSzorzas}}

==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:

<pre>
1011 * 1111
-----------
1011
1011
1011
+ 1011
------------------
</pre>

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:

<pre>
1011 * 1111
-----------
!->11011
+ 10110
--------
10001
</pre>

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:

<pre>

|- ez lesz az eredmény utolsó számjegye
V
|---|---|---|---||---|---|---|---||---|
| 0 | 0 | 0 | 0 || 1 | 0 | 1 | 1 || 0 |
|---|---|---|---||---|---|---|---||---|
| |
------------
szorzó
</pre>

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

-- [[SafarSimon|Simon]] - 2005.06.17.

[[Category:Villanyalap]]