plik


ÿþ Mno\enie Skalowanie w systemach naturalnych Skalowanie  mno\enie przez caBkowit potg podstawy ²k. " skalowania mo\na skBada poniewa\ ²kX= ²& ²²X " mno\enie przez ka\d dodatni potg podstawy daje w wyniku cykliczne przemieszczenie cyfr w lewo, poniewa\ i=k -1 i=k -1 i=k i i+1 i ² ² = ² = ² "xi "xi "xi-1 i=-m i=-m i=-m+1 " mno\enie przez ka\d ujemn potg podstawy daje w wyniku cykliczne przemieszczenie cyfr w prawo, poniewa\ i=k -1 i=k -1 i=k -2 -1 i i-1 i ² ² = ² = ² "xi "xi "xi+1 i=-m i=-m i=-m-1 © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 1 Mno\enie Skalowanie w systemach uzupeBnieniowych i dopeBnieniowych Je[li najwy\sz pozycj liczby nie jest cyfr rozszerzenia xk = Õ(xk -1)(² -1), to w wyniku mno\enia przez ² mo\e wystpi nadmiar. Je[li k najwy\szych pozycji liczby nie jest cyframi rozszerzenia, to w wyniku mno\enia przez ²k mo\e wystpi nadmiar. W systemie uzupeBnieniowym  rozszerzenie: xk = Õ(xk -1)(² -1)  otrzymamy Xe = {Õ(xk -1)(² -1), xk -1, xk -2,..., x-m}Ò!² Xe = {xk -1, xk -2,..., x-m,0}, W systemie dopeBnieniowym nastpi cykliczne przemieszczenie cyfr Xe = {Õ(xk -1)(² -1), xk -1, xk -2,..., x-m}Ò!² Xe = {xk -1, xk -2,..., x-m ,Õ(xk -1)(² -1)} Wynik skalowania odwrotnego (mno\enia przez ²-1) jest zawsze poprawny -1 Xe = {xk -1, xk -2,..., x-m+1, x-m}Ò!² Xe = {Õ(xk -1)(² -1), xk -1, xk -2,..., x-m+1} © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 2 Mno\enie Skalowanie w dwójkowym systemie uzupeBnieniowym i dopeBnieniowym Wynikiem dodawania liczby do niej samej jest na ka\dej pozycji: xi + xi + ci = 2ci+1 + si Ò! ci+1 = xi , si = ci Ò! si+1 = xi W systemie uzupeBnieniowym, u\ywajc rozszerzenia, otrzymamy Xe = {xk -1, xk -1, xk -2,..., x-m+1, x-m}Ò!Xe + Xe = {xk -1, xk -2,..., x-m+1, x-m,0}, " (×2)U = przesunicie logiczne (logical shift) W systemie dopeBnieniowym pojawi si przeniesienie okr\ne o warto[ci xk 1 Xe = {xk -1, xk -1, xk -2,..., x-m+1, x-m}Ò!Xe + Xe = {xk -1, xk -2,..., x-m+1, x-m, xk -1} " (×2)D = przemieszczenie cykliczne, rotacja (rotation) Wynikiem skalowania odwrotnego (mno\enia przez 2-1) jest zawsze Xe = {xk -1, xk -2,..., x-m+1, x-m}Ò!1 Xe = {xk -1, xk -1, xk -2,..., x-m+1} 2 " (×2-1) = przesunicie arytmetyczne (arithmetic shift). © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 3 Mno\enie Skalowanie jako zBo\enie przesuni Poniewa\ ²k=(²a²2 b²4 c& )-1 (a,b,c,& =0,1), wic mno\enie przez ²k mo\na wykona jako zBo\enie przesuni o 2i pozycji " w lewo gdy k>0 " w prawo gdy k<0 L P L P L P L P L P L P L P L P ! ! 1 L P L P L P L P L P L P L P L P ! ! 2 L P L P L P L P L P L P L P L P ! ! 4 Schemat skalowania przez przesunicie w lewo © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 4 Mno\enie Sekwencyjny algorytm mno\enia w systemie naturalnym Mno\na (multiplicand) A =|{as-1,..., a- p+1, a- p}² |, Mno\nik (multiplier) X =|{xk-1,..., x-m+1, x-m}² |, k-1 k-1 öø i i AÅ" X = AÅ"ëø xi² = (xi A) ìø " ÷ø "² íøi=-m øø i=-m Algorytm pisemny  akumulacja skalowanych iloczynów cz[ciowych i=- m, - m+1,...,k-1, S-m = 0 i Si+1 = Si + ² (xi A) , Sk = AÅ" X Algorytm dodaj-przesuD (add-and-shift)  skalowanie sum cz[ciowych -i Pi = ² Si -1 Pi+1 = ² (Pi + xi A) k -1 k i ² Pk = P-m + A{ xi ² } = A Å" X " i=-m © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 5 Mno\enie Mno\enie sekwencyjne w systemach uzupeBnieniowych i dopeBnieniowych Warto[ci znakowanego mno\nika jest k-1 i X = -Õ(xk-1)R + xi ² , " i=-m gdzie R=Q+ulp-´Å"ulp =²k+´Å"² m (´=1 w systemie niepeBnym, 0 w peBnym) 1 Õ(xk -1) = (1+ sgn(2xk -1- (² -1)))  funkcja znaku liczby, 2 Ale xk 1 jest warto[ci w jednopozycyjnym systemie uzupeBnieniowym, wic k -2 k -1 i -m X = (xk -1 - ²Õ(xk -1))² + ² + ´Õ(xk -1)² "x i i=-m Je\eli najwy\sz cyfr jest cyfra rozszerzenia xk -1 = (² -1)Õ(xk -1), to wtedy k -2 öø k -1 i -m AÅ" X = AÅ"ëø-Õ(xk -1)² + xi ² +´Õ(xk -1)² = ìø " ÷ø íø i=-m øø k -2 k -1 i -m = -Õ(xk -1)² A + (xi A) + ´Õ(xk -1)² A "² i=-m © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 6 Mno\enie Interpretacja PrzeksztaBcenie zk -1 = xk -1 - ²Õ(xk -1) mo\na interpretowa jako przeksztaBcenie zbioru cyfr najwy\szej pozycji D={0,1,& ,²-1} 1 1 na nieredundantny zbiór cyfr znakowanych DS = {- ² ,...,-1,0,1,..., ² -1} 2 2 Je[li zatem najwy\sz cyfr reprezentacji uzupeBnieniowej jest  ²-1 , to jej faktyczn warto[ci w dziaBaniach pozycyjnych jest  1. W dwójkowych systemach uzupeBnieniowych równowa\n interpretacj liczby o ujemnej wadze pozycji najwy\szej ( 2k 1), jest jej interpretacja jako liczby z ujemn cyfr ( xk 1 i dodatni wag (2k 1) i=k -2 i=k -2 i=k -2 - xk -12k -1 + 2i = xk -1(-2k -1) + 2i = (-xk -1) 2k -1 + 2i "xi "xi "xi i=-m i=-m i=-m © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 7 Mno\enie Mno\enie pisemne w systemie uzupeBnieniowym  przykBad bez rozszerzenia mno\nika 9 9 9 8 7 6 0 1 2 4 A=-124 A=124 7 7 9 7 7 9 X=-21 X=-21 9 9 9 9 8 8 8 4 0 0 0 0 1 1 1 6 x0=9 x0=9 9 9 9 9 1 3 2 0 0 0 0 8 6 8 x1=7 x1=7 0 0 0 3 7 2 9 9 9 6 2 8 x2=-3 -3A x2=-3 -3A 0 0 0 2 7 4 0 4 9 9 9 7 2 5 9 6 XÅ"A XÅ"A z rozszerzeniem mno\nika 9 9 9 8 7 6 0 1 2 4 A=-124 A=124 9 7 7 9 9 7 7 9 X=-21 X=-21 9 9 9 9 8 8 8 4 0 0 0 0 1 1 1 6 x0=9 x0=9 9 9 9 9 1 3 2 0 0 0 0 8 6 8 x1=7 x1=7 9 9 9 1 3 2 0 0 0 8 6 8 x2=7 x2=7 0 0 1 2 4 9 9 8 7 6 x3=-1 -A x3=-1 -A 0 0 0 2 7 4 0 4 9 9 9 7 2 5 9 6 XÅ"A XÅ"A © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 8 Mno\enie Algorytm mno\enia sekwencyjnego w systemach uzupeBnieniowych Algorytm mno\enia dodaj-przesuD (add-and-shift)  [ xk -1 = (² -1)Õ(xk -1)] 0. if xk -1 `" (² -1)Õ(xk -1) then a) xk = (² -1)Õ(xk -1) ; dopisz pozycj rozszerzenia b) k++ ; zwiksz k 1. P-m = ´Õ(xk -1)A ; (´=1 w s. niepeBnym, 0 w peBnym) 2. i= m 3. Mi = xi A ; oblicz iloczyn cz[ciowy -1 4. Pi+1 = ² (Pi + Mi ) ; przeskaluj (przesuD) sum cz[ciow 5. i++ ; zwiksz i 6. if i<k 1 goto 3 ; powtarzaj do przedostatniego -1 7. Pk = ² (Pk -1 +Õ(xk -1)(-A)) ; dodaj dopeBnienie mno\nej lub 0 k 8. AÅ" X = ² Pk ; iloczyn !! UWAGA: Wszystkie sumy cz[ciowe s przesuwane w prawo wic musz by obliczane z lewostronnym rozszerzeniem © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 9 Mno\enie Mno\enie dodaj-przesuD w systemie uzupeBnieniowym  przykBad 9 8 7 6 0 1 2 4 A = -124 A = 124 7 7 9 7 7 9 X = -21 X = -21 +9A 9 8 8 8 4 +9A 0 1 1 1 6 x0 = 9 x0 = 9 ’! ’! 9 9 8 8 8 4 0 0 1 1 1 6 +7A 9 9 1 3 2 +7A 0 0 8 6 8 x1 = 7 x1 = 7 9 9 0 2 0 4 0 0 9 7 9 6 ’! ’! 9 9 9 0 2 0 4 0 0 0 9 7 9 6 0 0 3 7 2 9 9 6 2 8 x2 = - 3 -3A x2 = - 3 -3A 0 0 2 7 4 0 4 9 9 7 2 5 9 6 ’! 0 0 0 2 7 4 0 4 XÅ"A 9 9 9 7 2 5 9 6 XÅ"A & & & & ’! ’! 9 9 9 0 2 0 4 0 0 0 9 7 9 6 +7A 9 9 1 3 2 +7A 0 0 8 6 8 x2 = 7 x2 = 7 9 9 0 3 4 0 4 0 0 9 6 5 9 6 ’! 9 9 9 0 3 4 0 4 ’! 0 0 0 9 6 5 9 6 0 0 1 2 4 9 9 8 7 6 x3 = - 1 -A x3 = - 1 -A 0 0 0 2 7 4 0 4 9 9 9 7 2 5 9 6 XÅ"A XÅ"A © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 10 Mno\enie Mno\enie pisemne w dwójkowych systemach uzupeBnieniowych U2 i U1 U2 1 0 0 1 0 1 0 1 A = -7 A = +5 1 0 1 1 1 1 0 1 X = -5 X = -3 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 1 x0 = 1 x0 = 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 x1 = 1 x1 = 0 0 0 0 0 0 0 0 0 0 1 0 1 x2 = 0 x2 = 1 0 0 1 1 1 1 1 0 1 1 0 0 0 x3 = 1 (-A) x3 = 1 (-A) 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 XÅ"A = 35 XÅ"A = -15 U1 1 0 0 0 0 1 0 1 A = -7 A = +5 1 0 1 1 1 1 0 1 X = -4 X = -2 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 1 P0 = x3 A P0 = x3 A 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 1 x0 = 1 x0 = 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 x1 = 1 x1 = 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 x2 = 0 x2 = 1 0 0 1 1 1 0 0 0 1 1 0 1 0 1 1 1 x3 = 1 (-A) x3 = 1 (-A) 0 0 0 1 1 0 0 1 1 1 1 1 0 1 0 1 e-a-c = 11 0 0 0 0 0 0 1 1 e-a-c = 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 XÅ"A = 28 XÅ"A = -10 © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 11 Mno\enie Mno\enie maszynowe w dwójkowych systemach uzupeBnieniowych W dwójkowych systemach uzupeBnieniowych xk -1 - 2Õ(xk -1) = -xk -1 k -2 X = -xk -12k -1 + xi2i +´ xk -12-m " i=-m 1. P-m = ´ xk -1A ; (xk 1A) 0 w systemie (nie)peBnym i= m 2. Mi = xi A ; oblicz iloczyn cz[ciowy 3. Si+1 = Pi + Mi ; oblicz sum cz[ciow 4. if ´=1 then Si+1 = Si+1 + c+ ; ´=1’!skoryguj sum przeniesieniem 5. Pi+1 = 2-1Si+1 ; przeskaluj sum (przesuD w prawo) 6. i++ ; zwiksz i 7. if i<k 1 goto 3 ; powtarzaj do przedostatniego 8. Pk = 2-1(Pk -1 + xk -1(-A)) ; dodaj dopeBnienie mno\nej lub 0 9. AÅ" X = 2k Pk ; iloczyn " dziaBania na wszystkich pozycjach sum cz[ciowych © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 12 Mno\enie Mno\enie maszynowe w systemie U2  przykBad 1 0 0 1 0 1 0 1 A=-7 A=+5 1 0 1 1 1 1 0 1 X=-5 X=-3 0 0 0 0 0 0 0 0 0 0 P0=0 P0=0 +A + 1 1 0 0 1 +A 0 0 1 0 1 x0=1 x0=1 1 1 0 0 1 0 0 1 0 1 ShR 1 1 1 0 0 1 ShR 0 0 0 1 0 1 +A + 1 1 0 0 1 0 ShR 0 0 0 0 1 0 1 x1=1 x1=0 1 0 1 0 1 1 +A + 0 0 1 0 1 0 0 x2=1 ShR 1 1 0 1 0 1 1 0 0 1 1 0 0 1 ShR 1 1 1 0 1 0 1 1 ShR 0 0 0 1 1 0 0 1 x2=0 + 0 0 1 1 1 0 0 0 + 1 1 0 1 1 0 0 0 x3=1 -A x3=1 -A 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 XÅ"A=35 XÅ"A=-15 Uwaga: W polach zacienionych wpisano cyfry rozszerzenia znakowego. © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 13 Mno\enie Mno\enie maszynowe w systemie U1  przykBad 1 0 0 0 0 1 0 1 A=-7 A=+5 1 0 1 1 1 1 0 1 X=-4 X=-2 1 1 0 0 0 0 0 1 0 1 P0=x3A P0=x3A +A + 1 1 0 0 0 +A 0 0 1 0 1 x0=1 x0=1 +1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 ShR 0 0 1 0 1 0 ShR 1 1 0 0 0 1 ShR 0 0 0 1 0 1 0 x1=0 +A + 1 1 0 0 0 1 +A + 0 0 1 0 1 0 0 x1=1 x2=1 +1 1 0 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 ShR 0 0 0 1 1 1 1 0 ShR 1 1 0 0 0 1 1 + 1 1 0 1 0 1 1 1 x3=1 -A ShR 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 x2=0 XÅ"A=-10 + 0 0 1 1 1 0 0 0 x3=1 -A +1 0 0 0 1 1 0 1 1 + 1 0 0 0 1 1 1 0 0 XÅ"A=28 © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 14 Mno\enie Uproszczenie mno\enia w dwójkowym systemie uzupeBnieniowym Je[li do liczby danej w dwójkowym systemie uzupeBnieniowym o k pozycjach cz[ci caBkowitej dodamy 2k 1 to otrzymamy liczb dodatni k -2 k -2 - xk -12k -1 + 2i + 2k -1 = (1- xk -1)2k -1 + 2i "xi "xi i=-m i=-m Je[li zatem do ka\dego iloczynu cz[ciowego xiA dodamy i odejmiemy 2k 1 (waga najwy\szej pozycji mno\nej), a nastpnie przeskalujemy, to iloczyn bdzie sum przeskalowanych iloczynów cz[ciowych z dopeBnieniem najwy\szej cyfry pomniejszon o sum kolejnych potg dwójki poczynajc od potgi odpowiadajcej najwy\szej cyfrze mno\nej. UWAGA: Uproszczenie jest istotne w rozwizaniach ukBadowych, ale umo\liwia uproszczenie realizacji programowej. Intuicja (inne systemy) Je[li do liczby w systemie uzupeBnieniowym o k pozycjach cz[ci caBkowitej k -1 1 dodamy ² , to otrzymamy liczb dodatni, ale & algorytm si komplikuje 2 © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 15 Mno\enie Akumulacja iloczynów cz[ciowych w kodzie U2 Czy mo\na pomin rozszerzenia znakowe iloczynów cz[ciowych? s-2 k-2 ëø j AÅ" X = as-12s-1 + 2 xk-12k-1 + xi 2i öø ìø- ÷øìø- "a öøëø " ÷ø j j=0 i=0 øø íø øøíø s-2 k-2 s-2 ëø j i j = -2k-1 as-1xk-12s-1 + xk-12 + ÷ø ìø- ÷ø ìø- "a öø "2 ëø as-1xi 2s-1 + "a xi 2 öø = j j j=0 i=0 j=0 íø øø íø øø s-2 k-2 s-2 ëø (k- (k-1) j i (i (i) j = -2k-1 (1- as-11))2s-1 + ÷ø ìø ÷ø ìø "a 2 - 2s-1 öø + "2 ëø(1- as-) )2s-1 + "a 2 - 2s-1 öø = j 1 j j=0 i=0 j=0 íø øø íø øø s-2 k-2 s-2 ëø (k- (k-1) j i (i (i) j = -2k-1 (1- as-11))2s-1 + ÷ø ìø ÷ø ìø "a 2 öø + "2 ëø(1- as-) )2s-1 + "a 2 öø + 2s-1 j 1 j j=0 i=0 j=0 íø øø íø øø gdzie a(ji) = a xi  j-ty bit mno\nej lub 0 gdy xi=0 j ’! algorytm (je[li A=-2k-1, konieczne rozszerzenie mno\nej) " zastpi dopeBnieniem najwy\szy bit iloczynu cz[ciowego (0’!10& 00!) " dokona korekty dodawania przekodowanych operandów +2s-1 © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 16 Mno\enie Schemat dodawania iloczynów cz[ciowych w kodzie U2 a) A 9 8 7 6 5 4 3 2 1 0 b) A 9 8 7 6 5 4 3 2 1 0 o o o o o o o o o o " " " " " " " " " " " " " " " " " " " " " " " " " " " " " o o o o o o o o o o " " " " " " " " " " " " " " " " " " " " " " " " " o o o o o o o o o o " " " " " " " " " " " " " " " " " " " " " o o o o o o o o o o " " " " " " " " " " " " " " " " " o o o o o o o o o o " " " " " " " " " " " " " o o o o o o o o o o " " " " " " " " " + 1 0 0 0 0 0 1 Matryca iloczynów cz[ciowych: a) z rozszerzeniem (" "  bit najwy\szy lub " " jego kopia), b) przekodowanych ("  dopeBnienie najbardziej znaczcego bitu) 1 1 1 1 1 0 1 1 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 1 0 0 1 1 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 17 Mno\enie Mno\enie skrócone w systemie U2 U2 1 0 0 1 1 0 0 1 A=-7 A=-7 1 0 1 1 1 0 1 1 X=-5 X=-5 1 1 1 1 1 0 0 1 0 1 0 0 1 x0=1 x0=1 1 1 1 1 0 0 1 0 1 0 0 1 x1=1 x1=1 0 0 0 0 0 0 1 0 0 0 0 x2=0 x2=0 0 0 1 1 1 1 0 1 1 1 x3=1 (-A) x3=1 (-A) 0 0 1 0 0 0 1 1 korekta 1 0 0 0 1 XÅ"A=35 0 0 1 0 0 0 1 1 XÅ"A=35 © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 18 Mno\enie Algorytm mno\enia równolegBego mno\na A =|{as-1,...,a- p+1,a- p}² |, mno\nik X =|{xk-1,..., x-m+1, x-m}² | system naturalny s-1 k-1 s+k-2 ëø j r AÅ" X = ² xi² = ìø ÷øìø i öø "a öøëø " ÷ø "² "a xi j j j=- p i=-m øø r=-m- p i+ j=r íø øøíø algorytm ’! obliczenie wszystkich iloczynów elementarnych a xi j ’! akumulacja czynników o tej samej wadze xi "a j i+ j=r problem  szybkie dodawanie wieloargumentowe system uzupeBnieniowy do 2  niektóre iloczyny elementarne maj ujemne wagi s-2 k -2 s+k -2 ëø öøëø j r p ìø- AÅ" X = as-12s-1 + 2 xk -12k -1 + xi 2i öø = ÷ø "a ÷øìø- " "2 "a xi (-1) j j ìø ÷øíø j=- p i=-m øø r =-m- p i+ j=r íø øø p=0 gdy j`"s 1 oraz i`"k 1 lub i+j=s+k 2, w przeciwnym razie p=1 © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 19 Mno\enie Algorytm mno\enia liczb dwójkowych w kodzie NB Krok 0. A ! A, X/P ! X, C||S/P ! 0. Podstaw i=1. Krok 1. C||S/P ! (S/P) + xi(A) Krok 2. C||S/P||X/P ! 2 1(C||S/P||X/P) = ShR(C||S/P||X/P) Krok 3. i=i+1. Je[li i < k+m, wró do kroku 1. Wynik: AÅ"X=(S/P||X/P) ShR A C S/P X/P £ S Schemat blokowy ukBadu mno\cego: S/P  rejestr sum cz[ciowych, X/P  rejestr mno\nika, A  rejestr mno\nej, C  rejestr przeniesienia © Janusz Biernat, Mno\enie, 20 listopada 2003 MUL 20

Wyszukiwarka

Podobne podstrony:
2006  mnozenie
mnozenie do 25 1
ASK LAB5 Mnozenie
mnozenie do 100 1 k
2006 szybkie mnozenie
matematyka tabliczka mnozenia
wzoru skroconego mnozenia
szybkie mnozenie

więcej podobnych podstron