163746. lajstromszámú szabadalom • Kapcsolási elrendezés osztási művelet meggyorsítására
3 163746 4 rpBj-OjD = 2rtl+li-qiD Ennek a képletnek az ismételt alkalmazásával hányados bitre a következő egyenlet adódik: r„ = 2nr0 +2n-lh, - 2 n " 1 q 1 D • .... •••• + 2h n -l-2q ll . 1 D*h n -q n D azaz r„= 2»r„ 2 2n -»hj I 2 B-iq,D ebből r =2n A*H n •2 2n -i q i D 10 15 2n A+H 2"-i q i D •r_ Az összehasonlító módszerrel végzett bináris osztás algoritmusa tehát: Részmaradék ahol qi = lhaí2ri . 1 *h i )>D qi = 0ha(2ri . 1+ h i )<D Maradék Rn = rn Az I2I óraimpulzusra a B, = 2rM +h; részosztandó beíródott a 6 LINK-be és az 1 akkumulátor regiszterbe. A vh, vk és vs vezérlőjelek megfelelő állapotával vezérelve kialakul a 4 MILL-ben a 2ri . 1 + h j — D érték, amelyet a v4 vezérlőjel a k0 ... kn kimenetekre kapuz, továbbá kialakul q, értéke, amely a kivonáskor keletkező esetleges c, túlcsordulásnak — a kivonás kettes komplemensű összeadással történik - a függvénye. Az I^,*, óraimpulzus hatására ko ... kn vezetékekenlévo érték beíródik a 6 LINK-be és az 1 akkumulátor regiszterbe, a 2 hányados regiszter legkisebb, n-dik bitjébe beíródik q, értéke. Ezután a 4 MILL-ben a q.értékétől függő vh, vk és vs vezérlőjelekkel vezérelve kialakul B^, részosztandó, ami egyenlő r. eggyel balra snittéit értékével, pontosabban 2r,4iK , -val, ahol *i = 2ri _ 1 + h i -D ha ^ = 1 r, = 2rM + h, - D + D azaz 25 30 Hányados Q = 2 2"-^ i-1 35 Fenti algoritmus a hányadost max. n bitesnek mutatja. Ennek feltétele, hogy B0 D, ebből következik, hogy L = O és A D, azaz ^ = 0. Ennek a feltételnek a teljesüléséről az osztás megkezdése előtt meg kell győződni. Ha L = 1, vagy A D, u.n. 40 osztási túlfolyás lép fel, számítógép nem végzi el az osztást. A visszaállító módszer az összehasonlító módszer speciális esete. Ennél a módszernél az összehasonlítás az osztónak a részmaradékból való kivonásával 45 történik. Algoritmusa azonos az összehasonlító módszer algoritmusával. Ismert megvalósítás a visszaállító módszer alkalmazásával a következő (1. sz. ábra). Az osztandó A és H értékét az n bites 1 50 akkumulátor regiszter és az n bites 2 hányados regiszter tartalmazza, L értékét a 6 link egybites carry regiszter a D osztót az n bites 3 osztó regiszter tartalmazza; a szükséges aritmetikai és léptető műveleteket az n bites 4 mill párhuzamos műveletvégrehajtó áramkör, végzi: a vh, vk és vs vezérlőjelek hatására és azoktól függően az aO ... an és bl... bn Í árhuzamos bemeneteken lévő értékek összegét, ülönbaégét vagy az összegnek, Ül. különbségnek egy helyértékkel balra léptetett f értékét - figyelembe véve h bemenetet - képezi a kimenetén, és v4 vezérlőjel hatására a kO ... kn vonalakra kapuzza. Az 5 vezérlő áramkör adja a vezérlőjeleket és I óraimpulzusokat. Az 1. sz. ábra szerinti elrendezés egy részosztást 65 két óraimpulzus alatt végez el. Az i-dik részosztás a következőképp történik. 20 55 r, = 2rM + h, ha q, = 0 A v4 vezérlőjel a B^, részosztandót a k ... kn kimenetekre kapuzza, amelyeken keresztül I2l+3 óraimpulzus hatására beíródik 6 LINK-be, és az 1 akkumulátor regiszterbe, 1,^ hatására a 2 hányados regiszter - amelynek felsobitjei még az osztandó kis helyértékeit, alsó bitjei már a hányados nagy helyértékeit tartalmazza - tartalma egy helyértékkel balra léptetődik úgy, hogy a legkisebb helyértékre zéró íródik be. Ezzel az i-dik részosztás befejeződött. Fenti leírás i = 1 ... n-1 esetben igaz. Az n-edik részosztás abban különbözik a többitől, hogy léptetés nem történik, az 1 dckumulátor regiszterbe az rn = R maradék, a 2 hányados regiszterbe aQ = 2 2ni q, hányados 1-1 végeredmények íródnak be az utolsó óraimpulzusra. Az összehasonlító módszer ismert megvalósítása a fenti megvalósítás elemein kívül még egy 7 összehasonlító áramkört tartalmaz (2. sz. ábra). A 7 összehasonlító áramkör a 6 LINK és az 1 akkumulátor regiszter tartalmát (B;), illetve a 3 osztó regiszter (D) tartalmát hasonlítja össze egymással, azaz a q,-nek megfelelő vö jelet képezi, az osztás algoritmusa szerint. Ez a megvalósítás egy részosztást egy óraimpulzus alatt végez el. Az i-dik részosztás a következőképp történik: az I, óraimpulzusra a B,= 2rM + h, részosztandó beíródott a 6 LINK-be és az akkumulátor regiszterbe. A 7 összehasonlító áramkör a fentiek szerint a B, = 2r,_, + h, és D viszonyát vizsgálja its a vi; i vö eredményétől függően, az 5 vezérlő áramkör képezi q, értékét. Az ugyancsak a vő jeltől függő vk és vs vezérlőjelek hatására a 4 MILL áramkör képezi a 2/2rM + h,/ + h^, vagy a 2(2r, , + h, - D) • hlt1 , azaz a 2r, + hH 1 = BK , új részosztandót, amelyet v4 vezérlőjel 60 hatására a k0 ... kn kimenetekre kapuz. Az I óraimpulzus hatására k0 ... kn beíródik a 6 LINK-be és az 1 akkumulátor regiszterbe, es ugyanerre az impulzusra a 2 hányados regiszter tartalma egy helyértékkel balra shiftelődik úgy, hogy n-dik bitjébe zéró, n-l-dik bitjébe q, íródik be. Ezzel az i-dik részosztás befejeződött. Fenti leírás i = 1 ... n-1 esetén igaz. 2
