163746. lajstromszámú szabadalom • Kapcsolási elrendezés osztási művelet meggyorsítására
MAGYAR NÉPKÖZTÁRSASÁG ORSZÁGOS TALÁLMÁNYI HIVATAL SZABADALMI LEÍRÁS SZOLGÁLATI TALÁLMÁNY Bejelentés napja: 1972. II. 5. (MA-2316) Közzététel napja: 1973. V. 28. Megjelent:1975.X.6. 163746 Nemzetközi osztályozás: G 06 f 7/52 Feltaláló: Bánki Ferenc i tud. munkatárs 20%, Karádi Pál tud. munkatárs, 20%, Kerényi László tud. munkatárs 20%, Rényi István tud. munkatárs, 20%, Szőnyi László tud. munkatárs, 20%, Budapest. Tulajdonos: MTA Központi Fizikai Kutató Intézet, Budapest Kapcsolási elrendezés osztási művelet meggyorsítására i Számítógépek műveleti sebességével szemben támasztott növekvő igények bizonyos esetekben szükségessé teszik összetettebb műveletek tisztán hardware úton történő megoldását. Az aritmetikai műveletek közül az osztás tipikus példa ilyen időigényes műveletre. Ennek hardware megoldásai általában ismert algoritmusokat valósítanak meg; előjel nélküli, vagy előjeles abszolútértékes számoknál az összehasonlító vagy a visszaállító módszert szokás használni. Osztás összehasonlító módszerrel n bites osztó, hányados és maradék, dupla szóhosszúságú, azaz 2n bites osztandó esetén: Alkalmazott jelölések: X = L.22n+A.2n*H = osztandó, ahol L = O, a tényleges osztandó A és H, két n bites szám hely értékhelyes összegeként áll elő. H egyes bitjeit hj-vel jelöljük. Bi = az i-dik részosztandó, a<: i-dik részosztás során az osztandó felső n+1 bitje BQ= L.2n +A = A D = osztó Q = hányados, egyes bitjeit qj-val jelöljük R = az osztás maradéka r0 = kezdeti maradék = A Ti = az i-dik részmaradék. 10 15 20 25 30 Az osztás az ismert X és D számokból az ismeretlen Q és R számokat határozza meg: X = Q.D*R A2«+H = Q.D • R (1) A módszer a részosztandókat és az osztót hasonlítja össze. Ha *a részosztandó nagyobb vagy egyenlő az osztónál, akkor az osztót ki kell vonni a részmaradékból és a hányados bit 1 lesz. Ha a részosztandó kisebb, akkor aritmetikai műveletet nem kell végezni, és a hányados bit 0 lesz. Mindkét esetben az így előálló/észmaradékot 1 bittel balra kell léptetni, és az lesz az új részosztandó. Ez a folyamat addig ismétlődik, amíg kívánt n számú hányados bit nem képződik. A kezdeti B0 részosztandó egyenlő A-val. BQ = A A kezdeti r0 részmaradék: r 0 = Bo-qoD = A, mivel q0 = 0 Az első részosztandó: Bi = 2r0 • h, és az első részmaradék: r, = B, - qt D ahol qi az első hányados bit; q, egyenlő 1-gyel, vagy 0-val, attól függően, hogy BJ> D illetve Bi<D qi =lha(2r0 +h,)>D q, =0ha(2ro *ht)<D rj = Bi - D ha qt = 1 r! =Bj haqi =0 A következő részosztandó Bs = 2r, + h2 és ä= B 2 -q 2 D = 2rj • h2 -q 2 D talánosságban az i-dik részmaradék 163746
