JustPaste.it

Zapis uzupełnień do 1 - U1

01d26e3e172509b2a3a4812dd1633334.gif

Opisany w poprzednim rozdziale system ZM zapisu liczb ze znakiem był koncepcyjnie prosty, lecz stwarzał poważne problemy przy wykonywaniu operacji arytmetycznych. Z drugiej strony liczba w zapisie ZM nie jest jednorodna. Bit znakowy posiada zupełnie inne znaczenie od pozostałych bitów i nie uczestniczy bezpośrednio w operacjach arytmetycznych.

Drugim podejściem do rozwiązania problemu liczb ze znakiem jest system uzupełnień do 1 zwany systemem U1 (ang. 1C - One's Complement). W systemie tym wszystkie bity zapisu liczby posiadają swoje wagi (w ZM bit znaku nie posiadał wagi). Najstarszy bit jest bitem znaku i ma wagę równą (-2n-1+1), gdzie n oznacza ilość bitów w zapisie liczby. Pozostałe bity posiadają wagi takie jak w naturalnym systemie dwójkowym.

Wartości wag pozycji w zapisie U1
waga -2n-1+1 2n-2 2n-3   22 21 20
cyfra bn-1 bn-2 bn-3 ... b2 b1 b0

Bit znaku przyjmuje wartość 0 dla liczb dodatnich, a dla liczb ujemnych wartość 1 (ponieważ tylko waga tej pozycji jest ujemna, to jest to jedyny sposób na otrzymanie wartości ujemnej).

2fb4f6af18b4a18e3fc16bbfc47d255a.gif    
   
    dcd3535a1b17da16a72cf8e7d19c4c98.gifWartość dziesiętna liczby w zapisie U1

Wartość liczby U1 obliczamy zgodnie z poznanymi zasadami - cyfry mnożymy przez wagi pozycji, na których się znajdują i dodajemy otrzymane iloczyny:

bn-1bn-2bn-3...b2b1b0 (U1) = bn-1(-2n-1+1) + bn-22n-2 + bn-32n-3 + ... + b222 + b121 + b020

gdzie

b - bit, cyfra dwójkowa 0 lub 1
n - liczba bitów w zapisie liczby

 
       

Ponieważ w systemach binarnych cyfry przyjmują tylko dwie wartości 0 lub 1, można rachunek znacznie uprościć sumując jedynie te wagi, dla których cyfra zapisu liczby ma wartość 1.

4 bitowy system U1
Kod U1 Przeliczenie Wartość
0000 0 0
0001 20 1
0010 21 2
0011 21 + 20 3
0100 22 4
0101 22 + 20 5
0110 22 + 21 6
0111 22 + 21 + 20 7
1000 (-23 + 1) (-7)
1001 (-23 + 1) + 20 (-6)
1010 (-23 + 1) + 21 (-5)
1011 (-23 + 1) + 21 + 20 (-4)
1100 (-23 + 1) + 22 (-3)
1101 (-23 + 1) + 22 + 20 (-2)
1110 (-23 + 1) + 22 + 21 (-1)
1111 (-23 + 1) + 22 + 21 + 20 0

W tabelce obok przedstawiliśmy wszystkie możliwe do utworzenia liczby w 4-ro bitowym kodzie U1. Zwróć uwagę, iż wartość 0 posada dwa słowa kodowe: 0000 oraz 1111. Wynika to bezpośrednio ze wzoru obliczania wartości liczby U1. Jeśli wszystkie cyfry mają wartość 0, to żadna waga pozycji nie uczestniczy w wartości liczby i wartość ta jest równa 0.

Z kolei jeśli bit znaku jest równy 1, to jego waga wlicza się do wartości liczby. Waga bitu znakowego jest równa (-2n-1+1). Dla 4 bitowego kodu n=4, zatem waga bitu znakowego wynosi:

waga b3 = (-23+1) = -7

Jeśli pozostałe bity liczby są ustawione na 1, to ich wagi sumują się do wartości 7. Jeśli teraz dodamy wagę bitu znakowego i wagi pozostałych bitów, otrzymamy wartość 0.

Drugą charakterystyczną cechą kodu U1 są liczby przeciwne. Zwróć uwagę, iż liczba przeciwna zawsze powstaje w kodzie U1 przez negację wszystkich bitów:

1(10) = 0001(U1) : (-1)(10) = 1110(U1)
5(10) = 0101(U1) : (-5)(10) = 1010(U1)
7(10) = 0111(U1) : (-7)(10) = 1000(U1)

Zasada ta obowiązuje dla kodów U1 o dowolnej długości.
 

9a02c176d53756c0dda35e575f0b9afe.gif

Jeśli liczba jest dodatnia, to najstarszy bit znakowy posiada wartość 0. Pozostałe bity służą do zapisu liczby w naturalnym kodzie binarnym:

0111(U1) = 7(10), 0001(U1) = 1(10), 01111111(U1) = 127(10)

Jeśli liczba jest ujemna, to najstarszy bit znakowy ma wartość 1. Pozostałe bity są negacjami bitów modułu wartości liczby:

1101(U1) = (-2)(10) : moduł 2(10) = 010(2) : NOT 010 = 101
1100(U1) = (-3)(10) :
moduł 3(10) = 011(2) : NOT 011 = 100
1010(U1) = (-5)(10) :
moduł 5(10) = 101(2) : NOT 101 = 010

Wynika stąd prosta metoda przeliczania liczby dziesiętnej na zapis U1.

2fb4f6af18b4a18e3fc16bbfc47d255a.gif    
   
    dcd3535a1b17da16a72cf8e7d19c4c98.gifWersja 1 - procedura wyznaczania zapisu U1 dla liczby dziesiętnej
  1. Jeśli liczba jest dodatnia, znajdujemy jej reprezentację w naturalnym kodzie binarnym i uzupełniamy bitami o wartości 0 do uzyskania zadanej liczby bitów wymaganej przez przyjęty format zapisu U1.

  2. Jeśli liczba jest ujemna, obliczamy jej moduł. Moduł przedstawiamy w naturalnym systemie dwójkowym uzupełniając go bitami o wartości 0 do długości przyjętego formatu U1. Następnie wszystkie bity zamieniamy na przeciwne i w wyniku otrzymujemy zapis U1.

 
       

f7a81e88aa6959b5e77189b957541f5e.gif

 

Wyznaczyć 8-mio bitowy zapis U1 liczby dziesiętnej 76.

Liczba 76 jest dodatnia, zatem wyznaczamy jej zapis w naturalnym systemie dwójkowym:

76(10) = 1001100(2)

Otrzymaną liczbę dwójkową uzupełniamy bitami o wartości 0 do długości formatu otrzymując:

76(10) = 01001100(U1).

f7a81e88aa6959b5e77189b957541f5e.gif

 

Wyznaczyć 8-mio bitowy zapis U1 liczby dziesiętnej (-113).

Liczba (-113) jest ujemna. Jej moduł wynosi 113. Wyznaczamy zapis dwójkowy modułu:

113(10) = 1110001(2)

Otrzymany zapis uzupełniamy bitami 0 do długości 8 bitów. Następnie negujemy wszystkie bity i otrzymujemy w ten sposób zapis U1 liczby -113:

-113(10) = NOT 01110001 = 10001110(U1).

2fb4f6af18b4a18e3fc16bbfc47d255a.gif    
   
    dcd3535a1b17da16a72cf8e7d19c4c98.gifWersja 2 - procedura wyznaczania zapisu U1 dla liczby dziesiętnej
  1. Jeśli liczba jest dodatnia, znajdujemy jej reprezentację w naturalnym kodzie binarnym i uzupełniamy bitami o wartości 0 do uzyskania zadanej liczby bitów wymaganej przez przyjęty format zapisu U1.

  2. Jeśli liczba jest ujemna, wyznaczamy wartość 2n - 1 + liczba, gdzie n oznacza liczbę bitów w przyjętym formacie U1. Wartość tę kodujemy w naturalnym systemie dwójkowym i otrzymujemy kod U1 liczby wyjściowej.

 
       

f7a81e88aa6959b5e77189b957541f5e.gif

 

Wyznaczyć 8-mio bitowy zapis U1 liczby dziesiętnej (-113).

Obliczamy:

28 - 1 - 113 = 256 - 1 - 113 = 142

Otrzymany wynik kodujemy w systemie dwójkowym i otrzymujemy kod U1 liczby -113:

142(10) = 10001110(2)czyli (-113)(10) = 10001110(U1).

f7a81e88aa6959b5e77189b957541f5e.gif

 

Wyznaczyć 16 bitowy zapis U1 liczby dziesiętnej (-4521).

Obliczamy:

216 - 1 - 4521 = 65536 - 1 - 4521 = 61014

Otrzymany wynik kodujemy w systemie dwójkowym i otrzymujemy kod U1 liczby -45:

61014(10) = 1110111001010110(2)czyli (-4521)(10) = 11101110010101100(U1).

35b4d5d1822139433c7a65c5135d0b43.gif

Liczba U1 przyjmuje wartość największą dla bitu znaku równego 0 i pozostałych bitów równych 1. Ponieważ pozostałe bity przedstawiają w tym przypadku liczbę n-1 bitową w naturalnym kodzie dwójkowym, to dla n bitowego kodu U1 otrzymujemy:

max(U1) = 2n-1 - 1.

Najmniejszą wartość liczba U1 przyjmuje dla bitu znakowego równego 1 (waga ujemna) i pozostałych bitów równych 0. Ponieważ w tym przypadku do wagi bitu znakowego nic nie dodajemy, otrzymujemy:

min(U1) = -2n-1 + 1 i ostatecznie:

2fb4f6af18b4a18e3fc16bbfc47d255a.gif    
   
    dcd3535a1b17da16a72cf8e7d19c4c98.gifZakres n bitowej liczby w kodzie U1 wynosi

Z(U1) = (-2n-1 + 1, 2n-1 - 1)

Zakres ten jest identyczny z zakresem liczb w kodzie ZM.

 
       

f7a81e88aa6959b5e77189b957541f5e.gif

4 bitowe liczby U1 posiadają zakres:

od  -23 + 1  =  -7  = 1000(ZM)
do  23 - 1  =  7  = 0111(ZM1)

8 bitowe liczby U1 posiadają zakres:

od  -27 + 1  =  -127  = 10000000(ZM)
do  27 - 1  =  127  = 01111111(ZM1)

16 bitowe liczby U1 posiadają zakres:

od  -215 + 1  =  -32767  = 1000000000000000(ZM)
do  215 - 1  =  32767  = 0111111111111111(ZM1)

60d581a097f6cb145be3424097a7ca00.gif
DLA
GENIUSZA

9dd23dbe2d9da94e02ef79f1238578e4.gif

Kod U1 może również reprezentować liczby ułamkowe, jeśli dokonamy rozszerzenia cyfr na pozycje ułamkowe. W przypadku liczb dodatnich (gdy pozycja znakowa zawiera cyfrę 0) stosujemy poznane zasady wyznaczania wartości liczby.

f7a81e88aa6959b5e77189b957541f5e.gif

0111,1101(U1) = 22 + 21 + 20 + 2-1 + 2-2 + 2-4
0111,1101(U1) = 4 + 2 + 1 + 1/2 + 1/4 + 1/16
0111,1101(U1) = 713/
16

Jednakże przy liczbach ujemnych musimy wprowadzić drobną modyfikację w stosunku do liczb całkowitych. Kod uzupełnień do 1 ma taką własność, iż wyraz kodowy zbudowany z samych jedynek jest zawsze równy 0:

111...111 , 111...111  = 0

n bitów
całkowitych

 

m bitów
ułamkowych

 

Wynika z tego, iż suma wszystkich wag liczby musi sprowadzać się do 0. Zatem waga bitu znakowego spełnia równanie:

wagaznakowa U1 = -(maxczęści całkowitej + maxczęści ułamkowej)

Załóżmy, iż nasz format U1 zbudowany jest z n bitów całkowitych i m bitów ułamkowych (zobacz tutaj).

maxczęści całkowitej = 2n-1 - 1

maxczęści ułamkowej = (2m - 1) / 2m

Stąd

wagaznakowa U1 = -(2n-1 - 1 + (2m - 1) / 2m)

gdy m = 0, wzór redukuje się do podanego wcześniej wzoru -2n-1 + 1 dla liczb całkowitych.

f7a81e88aa6959b5e77189b957541f5e.gif

1011,1011(U1) : n = 4; m = 4, zatem waga znakowa jest równa -(23 - 1 + (24 - 1) / 24) = -715/16.

1011,1011(U1) = -715/16 + 3 + 11/16
1011,1011(U1) = -44/16

855f5727d4e91a0fcb6f1dcdb2688381.gif

Dodawanie

Liczby U1 dodajemy zgodnie z poznanymi zasadami dodawania dwójkowego. Jednakże jeśli występuje przeniesienie poza bit znaku, to do wyniku należy dodać 1, aby otrzymać poprawny rezultat dodawania.

f7a81e88aa6959b5e77189b957541f5e.gif

3 + 2
    1    
  0 0 1 1
+  0 0 1 0
  0 1 0 1
5
       3 + (-5)
    1    
  0 0 1 1
+  1 0 1 0
  1 1 0 1
(-2)
      (-4) + 3
    1 1  
  1 0 1 1
0 0 1 1
  1 1 1 0
(-1)
 

W podanych powyżej trzech przykładach przeniesienie poza bit znaku nie występuje, zatem wyniki operacji dodawania nie wymagają korekty i są poprawne.

2 + (-1)
1 1 1    
  0 0 1 0
+  1 1 1 0
  0 0 0 0
+ 0 0 0 1
  0 0 0 1
1
       (-1) + (-1)
1 1 1    
  1 1 1 0
+  1 1 1 0
  1 1 0 0
+ 0 0 0 1
  1 1 0 1
(-2)
      (-3) + 7
1 1      
  1 1 0 0
0 1 1 1
  0 0 1 1
+ 0 0 0 1
  0 1 0 0
4

Tutaj natomiast obserwujemy sytuację, gdy pojawia się przeniesienie poza bit znakowy (zapisaliśmy je w kolorze niebieskim). W takim przypadku wynik jest o 1 za mały i wymaga korekty. Ponieważ przeniesienie łatwo wykryć a układy zwiększające liczbę binarną o 1 są nieskomplikowane, dodawanie w kodzie U1 jest dosyć prosto realizowalne sprzętowo.

Liczby U1 mogą być liczbami stałoprzecinkowymi. W przypadku dodawania takich liczb przeniesienie poza bit znaku dodawane jest do najmłodszej cyfry wyniku.

f7a81e88aa6959b5e77189b957541f5e.gif

2 3/16 + (-3/16)
1 1 1              
  0 0 1 0 , 0 0 1 1
+  1 1 1 1 , 1 1 0 0
  0 0 0 1 , 1 1 1 1
+  0 0 0 0 , 0 0 0 1
  0 0 1 0 , 0 0 0 0
2

Odejmowanie

Odejmowanie realizujemy za pomocą dodawania liczby przeciwnej. Liczbę przeciwną tworzymy w kodzie U1 negując wszystkie bity zapisu liczby.

f7a81e88aa6959b5e77189b957541f5e.gif

5 - 6
         
  0 1 0 1
-  0 1 1 0
         
 
operację
5 - 6
zastępujemy operacją
5 + (-6)
5 + (-6)
      1  
  0 1 0 1
+  1 0 0 1
  1 1 1 0
(-1)
2fb4f6af18b4a18e3fc16bbfc47d255a.gif    
   
    3591f600ac8cce8170c469351c3d9e07.gif

Przy dodawaniu dwóch liczb U1 może wystąpić nadmiar (niedomiar), gdy wynik dodawania nie mieści się w ustalonej formatem ilości bitów. Nadmiar (niedomiar) występuje tylko w przypadku dodawania liczb tego samego znaku (czy potrafisz to uzasadnić?) . Zatem najprostszą metodą wykrycia nadmiaru (niedomiaru) jest sprawdzenie znaku wyniku. Jeśli znak wyniku operacji różni się od znaku argumentów, to wystąpił nadmiar (niedomiar).

7 + 2
0 111
+ 0 010
       (-3) + (-5)
1 100
1 010
1 001
(-6)
  10 110
6
 
   

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

 

Źródło: mgr Jerzy Wałaszek