Kod uzupełnień do dwóch

Kod uzupełnień do dwóch (w skrócie U2 lub ZU2) – system reprezentacji liczb całkowitych w dwójkowym systemie pozycyjnym. Jest obecnie najpopularniejszym sposobem zapisu liczb całkowitych w systemach cyfrowych. Jego popularność wynika z faktu, że operacje dodawania i odejmowania są w nim wykonywane tak samo jak dla liczb binarnych bez znaku. Z tego też powodu oszczędza się na kodach rozkazów procesora.

Nazwa kodu wzięła się ze sposobu obliczania liczb przeciwnych. Dla jednobitowej liczby wartość przeciwną obliczamy odejmując daną liczbę od 2 (uzupełniamy jej wartość do dwóch). Analogicznie, dla liczb ${\displaystyle n}$-bitowych wartości przeciwne uzyskujemy odejmując liczbę od dwukrotnej wagi najstarszego bitu ${\displaystyle (2\cdot 2^{n-1}=2^{n}).}$ W analogiczny sposób można stworzyć np. kod uzupełnień do jedności.

Zaletą tego kodu jest również istnienie tylko jednego zera. Przedział kodowanych liczb nie jest przez to symetryczny. W U2 na ${\displaystyle n}$ bitach da się zapisać liczby z zakresu:

${\displaystyle [-2^{n-1}\quad ,\quad 2^{n-1}-1].}$

Dla reprezentacji 8-bitowej (jednobajtowej) są to liczby od −128 do 127. Liczba ${\displaystyle -2^{n-1}}$ nie ma liczby przeciwnej w ${\displaystyle n}$-bitowej reprezentacji kodu U2.

Zapis liczb

W dwójkowym systemie liczbowym najstarszy bit liczby ${\displaystyle n}$-cyfrowej ma wagę ${\displaystyle 2^{n-1}.}$ Jedyną różnicą, jaką wprowadza tu kod U2, jest zmiana wagi tego bitu na przeciwną ${\displaystyle (-2^{n-1}).}$ Wartość dziesiętną liczby U2 wyraża wzór:

${\displaystyle -a_{n-1}\times 2^{n-1}+\sum _{i=0}^{n-2}a_{i}\times 2^{i}.}$

Najstarszy bit koduje wartość liczby, ale jest też nazywany bitem znaku, ponieważ świadczy o znaku liczby:

• jeśli jest ustawiony (=1), to liczba jest ujemna,
• jeśli jest skasowany (=0), to liczba jest dodatnia lub równa 0.

Zwiększając obszar zajmowany przez liczbę w kodzie U2 (np. z jednego bajta na dwa), dodawany obszar wypełnia się bitem znaku.

Kod U2 może być również użyty do przechowywania liczb ułamkowych o stałej pozycji przecinka. Zapisywany jest wówczas licznik ułamka o mianowniku będącym potęgą liczby dwa (${\displaystyle 2^{n},}$ np. 2, 4, 8,...), mianownik nie jest zapisywany. Przy mnożeniu i dzieleniu takich liczb wymagane są korekty, jeśli wynik ma mieć przecinek w tym samym miejscu.

Przykład

11101101_U2 = 1 · −2⁷ + 1 · 2⁶ + 1 · 2⁵ + 0 · 2⁴ + 1 · 2³ + 1 · 2² + 0 · 2¹ + 1 · 2⁰ = −128 + 109 = −19

Liczba przeciwna

Aby zamienić liczbę w U2 na przeciwną, należy wykonać dwa kroki:

• dokonać inwersji bitów, czyli zamienić 0 na 1 i odwrotnie;
• zwiększyć wynik o 1.

Przykład

Dana jest liczba:

74₁₀ = 0 · (− (2⁷)) + 1 · 2⁶ + 0 · 2⁵ + 0 · 2⁴ + 1 · 2³ + 0 · 2² + 1 · 2¹ + 0 · 2⁰ = 01001010_U2

dokonujemy inwersji:

10110101

i zwiększamy o 1:

10110110_U2 = 1 · (-(2⁷))+ 0 · 2⁶ + 1 · 2⁵ + 1 · 2⁴ + 0 · 2³ + 1 · 2² + 1 · 2¹ + 0 · 2⁰ = −74₁₀

Dodawanie i odejmowanie liczb

Dodawanie i odejmowanie w U2 odbywa się standardową metodą – traktujemy liczby jako zwykłe liczby binarne (dodatnie), dodajemy je i odejmujemy, a wynik otrzymamy w kodzie U2. Dodawanie i odejmowanie odbywa się łącznie z bitem znaku. Jeśli przeniesienie (lub pożyczka dla odejmowania) wystąpi tylko na bit znaku albo poza niego (niejednocześnie lub wcale), wówczas mamy do czynienia z nadmiarem. Oznacza to, że wynik nie mieści się w kodowanym zakresie.

Przykład

W precyzji do części czwartych, w ośmiobitowej reprezentacji, liczby są kodowane:

${\displaystyle -11{\frac {3}{4}}={\frac {-47}{4}}\leftrightarrow -(00101111_{\mathrm {U2} })=11010001_{\mathrm {U2} }}$

${\displaystyle -7{\frac {2}{4}}={\frac {-30}{4}}\leftrightarrow -(00011110_{\mathrm {U2} })=11100010_{\mathrm {U2} }}$

Dodawanie

${\displaystyle -11{\frac {3}{4}}+-7{\frac {2}{4}}=-19{\frac {1}{4}}={\frac {-77}{4}}\leftrightarrow 10110011_{\mathrm {U2} }}$

 11010001
+11100010
---------
110110011

Dziewiąty bit wyniku jest odrzucany przy określaniu liczby (jest on używany tylko do określenia czy nastąpił nadmiar). Tu wystąpiło przeniesienie na bit znaku i z niego, dlatego nadmiar nie wystąpił – wynik nie przekroczył zakresu i jest poprawny.

Odejmowanie

Odejmowanie jest realizowane, jak odejmowanie w naturalnym kodzie dwójkowym. Przykład z reprezentacją do części czwartych:

${\displaystyle -11{\frac {3}{4}}-\left(-7{\frac {2}{4}}\right)={\frac {-47}{4}}-{\frac {-30}{4}}\leftrightarrow 11010001_{\mathrm {U2} }-11100010_{\mathrm {U2} }=11101111_{\mathrm {U2} }={\frac {-17}{4}}}$

 11010001
−11100010
---------
111101111

Odejmowanie może być zamienione na dodanie liczby przeciwnej, dlatego w niektórych procesorach zrealizowano tylko operację tworzenia liczby przeciwnej i dodawanie, a odejmowanie stałej wartości może nie występować.

Powyższe działanie realizowane jako wzięcie liczby przeciwnej i dodawanie

${\displaystyle -11{\frac {3}{4}}-(-7{\frac {2}{4}})={\frac {-47}{4}}-{\frac {-30}{4}}\leftrightarrow }$

${\displaystyle \leftrightarrow 11010001_{\mathrm {U2} }-11100010_{\mathrm {U2} }=11010001_{\mathrm {U2} }+00011110_{\mathrm {U2} }=11101111_{\mathrm {U2} }}$

przeciwna do 11100010 = 00011110
 11010001
+00011110
 --------
 11101111

Mnożenie liczb

I wariant metody Bootha

Algorytm słowny:

1. Badamy kolejne pary bitów mnożnika.
2. Jeżeli badana para jest kombinacją 10 to od iloczynu częściowego odejmujemy mnożną, wynik przesuwamy o jedno miejsce w prawo.
3. Jeżeli jest to para 01 to dodajemy mnożną do iloczynu częściowego, przesuwamy wynik o jedno miejsce w prawo
4. Jeżeli są to pary 00 lub 11 to nie wykonujemy żadnego działania, tylko przesuwamy o jedno miejsce w prawo.
5. Gdy w skład pary wchodzi bit znaku to nie wykonujemy przesunięcia.

Przykład

Uwaga: część całkowita w zapisie binarnym została pominięta – zapis jest postaci bit_znaku.bity_ułamka

${\displaystyle A=-{\frac {5}{16}}=1.1011_{\mathrm {U2} }}$

${\displaystyle B=-{\frac {7}{8}}=-{\frac {14}{16}}=1.0010_{\mathrm {U2} }}$

Analizujemy bity liczby ${\displaystyle B}$ (od prawej do lewej strony), dodajemy i odejmujemy liczbę ${\displaystyle A.}$

   0.0000        (iloczyn częściowy)
  −1.1011        (jest 10, odejmuje)
   ------
   0.0101
   0.00101    →  (i przesuwa)
  +1.1011        (jest 01, dodaje)
   -------
   1.11011
   1.111011   →  (i przesuwa)
   1.1111011  →  (jest 00, tylko przesuwa)
  −1.1011        (jest 1.0, ale jest bit znaku, to nie przesuwa )
   ---------
   0.0100011

Wynik otrzymujemy w kodzie znak-moduł (ZM).

Sprawdzenie

${\displaystyle 0.0100011_{\mathrm {ZM} }={\frac {35}{128}}=-{\frac {5}{16}}\cdot -{\frac {7}{8}}}$

II wariant metody Bootha

Algorytm słowny:

1. Oznaczamy i inicjujemy: A – mnożna, iloczyn częściowy = 0
2. Przesuwamy mnożną o jedno miejsce w prawo (wykonujemy działanie ${\displaystyle {\frac {A}{2}}}$)
3. Badamy ostatni bit mnożnika:
   1. jeśli jest równy 1 to dodaj mnożną do iloczynu częściowego
   2. jeśli równy 0 to nie wykonuj żadnego działania (dodaj 0)
4. Przesuwamy mnożnik o jedno miejsce w prawo, czyli przechodzimy do badania kolejnego bitu mnożnika.
5. Przesuwamy iloczyn częściowy o jedno miejsce w prawo, powtarzamy 3 ostatnie punkty do momentu aż napotkamy bit znaku
6. Jeśli bit znaku jest równy 1 to odejmujemy mnożną od iloczynu częściowego, jeśli jest równy 0 to nie wykonujemy żadnego działania.
7. Uzyskany iloczyn częściowy przesuwamy o jedno miejsce w lewo (działanie A · 2).

Przykład

Uwaga: część całkowita w zapisie binarnym została pominięta – zapis jest postaci bit_znaku.bity_ułamka

${\displaystyle A={\frac {3}{8}}=0.011_{\mathrm {U2} }}$

${\displaystyle B=-{\frac {5}{16}}=1.1011_{\mathrm {U2} }}$

Analizuję bity liczby B (mnożnika) od prawej do lewej strony, dodaję i odejmuję liczbę A (mnożną).

${\displaystyle A={\frac {A}{2}}=0.0011_{\mathrm {U2} }}$ – przesuwamy mnożną o jedno miejsce w prawo

   0.0000
  +0.0011        (analizuję 1)
   ------
   0.0011
   0.00011    →
  +0.0011        (analizuję 1)
   -------
   0.01001
   0.001001   →
   0.0001001  →  (analizuję 0)
  +0.0011        (analizuję 1)
   ---------
   0.0100001
   0.00100001 →
  −0.0011        (analizuję 1 – bit znaku)
   ----------
   1.11110001
   1.1110001  ←

Wynik otrzymujemy w kodzie uzupełnień do dwóch.

Sprawdzenie

${\displaystyle 1.1110001_{\mathrm {U2} }=1.0001111_{\mathrm {ZM} }=-{\frac {15}{128}}={\frac {3}{8}}\cdot -{\frac {5}{16}}}$

Dzielenie liczb

Metoda porównawcza

Algorytm słowny:

1. Jeżeli przesunięta reszta częściowa jest większa lub równa od dzielnika, to kolejny bit ilorazu q_i = 1, odejmujemy dzielnik od tej reszty.
2. Jeżeli przesunięta reszta częściowa jest mniejsza od dzielnika, to kolejny bit ilorazu q_i = 0.
3. Dokonujemy przesunięcia otrzymanego wyniku o jedno miejsce w lewo i przechodzimy do punktu pierwszego.

Przykład

Uwaga: część całkowita w zapisie binarnym została pominięta – zapis jest postaci bity_ułamka
Uwaga 2: dzielenie odbywa się w kodzie znak-moduł z pominięciem bitu znaku (operujemy na modułach liczb), w przeciwieństwie do pozostałych metod

${\displaystyle A=-{\frac {25}{128}}=1.0011001_{\mathrm {ZM} }}$ (dzielna)

${\displaystyle B={\frac {5}{16}}=0.0101_{\mathrm {ZM} }}$ (dzielnik)

RC = A = 0011001     (RC ≥ B, więc q1 = 1)
         011001   ←
        −0101
         ------
         000101
    RC = 00101    ←  (RC < B, więc q2 = 0)
    RC = 0101     ←  (RC ≥ B, więc q3 = 1)
        −0101
         ----
    RC = 0000        (kolejna reszta częściowa = 0)

Otrzymany wynik, złożony z kolejnych bitów od q₁ do q₃ jest modułem liczby wynikowej, postaci q₁q₂q₃.

Bit znaku (z) tej liczby określamy na podstawie bitów znaku dzielnej (a) i dzielnika (b) przy pomocy operacji logicznej XOR: z = a XOR b. Tak więc przy różnych bitach znaku daje ona wynik 1, przy takich samych daje 0.

Wynik otrzymujemy w kodzie znak-moduł i jest on równy 1.101_ZM.

Sprawdzenie

${\displaystyle 1.101_{\mathrm {ZM} }=-{\frac {5}{8}}={\frac {-{\frac {25}{128}}}{\frac {5}{16}}}}$

Metoda nierestytucyjna

Algorytm słowny:

1. Założenie: moduł dzielnej musi być mniejszy od modułu dzielnika ${\displaystyle (|A|<|B|)}$ w kodzie ZM
2. Metoda polega na badaniu znaku dzielnika i kolejnej reszty częściowej (pierwsza reszta częściowa jest równa dzielnej).
   1. jeżeli znaki te są zgodne to odejmujemy dzielnik od przesuniętej w lewo kolejnej reszty częściowej, kolejny bit ilorazu q_i = 1
   2. jeżeli znaki są różne to dodajemy dzielnik do przesuniętej w lewo kolejnej reszty częściowej, kolejny bit ilorazu q_i = 0
3. Powtarzamy poprzedni punkt aż do momentu, gdy kolejna reszta częściowa będzie równa 0
4. Do otrzymanego wyniku dodajemy poprawkę równą −1 + 2⁻ⁿ, gdzie n jest liczbą bitów pseudoilorazu.

Przykład

Uwaga: część całkowita w zapisie binarnym została pominięta – zapis jest postaci bit_znaku.bity_ułamka

${\displaystyle A=-{\frac {15}{128}}=1.1110001_{\mathrm {U2} }}$ (dzielna)

${\displaystyle B={\frac {3}{8}}=0.011_{\mathrm {U2} }}$ (dzielnik)

   1.1110001     (znaki różne, 1 oraz 0, więc q0 = 0)
   1.110001   ←
  +0.011
   --------
   0.001001      (znaki zgodne, 0 oraz 0, więc q1 = 1)
   0.01001    ←
  −0.011
   -------
   1.11101       (znaki różne, więc q2 = 0)
   1.1101     ←
  +0.011
   ------
   0.0011        (znaki zgodne, więc q3 = 1)
   0.011      ←
  −0.011
   -----
   0.000         (kolejna reszta częściowa = 0)

Otrzymany wynik, złożony z kolejnych bitów od q₀ do q₃ jest pseudoilorazem (PQ), gdzie q₀ jest jego bitem znakowym, a kolejne są kolejnymi bitami liczby postaci q₀q₁q₂q₃. Tak więc PQ = 0.101

Do pseudoilorazu dodajemy poprawkę

${\displaystyle P=-1+2^{-4}=-{\frac {15}{16}}=1.0001_{\mathrm {U2} }}$

   0.101         (pseudoiloraz)
  +1.0001        (poprawka)
   ------
   1.1011

Wynik otrzymujemy w kodzie uzupełnień do dwóch.

Sprawdzenie

${\displaystyle 1.1011_{\mathrm {U2} }=1.0101_{\mathrm {ZM} }=-{\frac {5}{16}}={\frac {-{\frac {15}{128}}}{\frac {3}{8}}}}$

Zobacz też

• kod znak-moduł
• kod uzupełnień do jedności

Linki zewnętrzne

• Symulator algorytmu Booth’a
• Standardowe Techniki Kompresji. dsp.agh.edu.pl. [zarchiwizowane z tego adresu (2013-12-04)]. (materiały dydaktyczne AGH)