Podręcznik

Dokładniej, omówimy zapis uzupełnień do W (kod numeryczny uzupełnień do W) dla liczb całkowitych n ∈ Z (a więc również ujemnych). Wykorzystamy następujący fakt.

Fakt: Wybierzmy dowolne m ∈ Z, m ≠ 0 i ustalmy wagę W (W ∈ N, W ≥ 2). Wówczas istnieje dokładnie jeden ciąg: a_na_n-1...a₀, gdzie n > 0, taki że dla każdego i = 1,2,...n−1 a_i ∈ {0,1,...W−1}, a_n ∈ {0,1,...W−1}, oraz a_n = 0 i a_n-1 ≠ 0 i lub a_n = 1 taki, że:

$n = -(\text{sgn } a_n)W^n + \displaystyle\sum_{i=0}^{n-1}a_iW^i\qquad$(*)

Dowód: Prosty dowód pozostawiamy Czytelnikowi jako ćwiczenie.

Dla przypomnienia: funkcja sgn: R → {−1,0,1} (tzw. funkcja signum, czyli znak),

zdefiniowana jest dla wzorem: sgn(x) = $\left\{ \begin{array}{ll} { \text{1 gdy x > 0} \\ \text{0 gdy x = 0}\\\text{-1 gdy x < 0}} \end{array} \right.$

Jak widać dla m ∈ N, m ≠ 0 dzięki powyższemu faktowi możemy zdefiniować odwzorowanie $f$: Z \ {0} → <0,W−1>^* wzorem $f$ (m) = a_na_k...a₀ ∈ <0,W−1>^*. Jeśli przyjmiemy dodatkowo, że $f$ (0) = 0 ∈ <0,W−1>^*, to określimy odwzorowanie

$f$ : Z → <0,W−1>^*

nazywane kodem uzupełnień do W.

1. Jeśli a_n = 0 (tzn. słowa kodowe są postaci 0a_n-1a_n-2...a₀) to liczba jest nieujemna

2. Jeśli a_n = W−1 (tzn. słowa kodowe są postaci (W−1)a_n-1a_n-2...a₀) to liczba jest nieujemna

Algorytm obliczania liczby przeciwnej do danej jest w zapisach uzupełnień do W jest następujący. Jeśli m ∈ Z i słowo a_na_n-1...a₀ reprezentuje tę liczbę to słowo reprezentujące −m uzyskujemy jako uzupełnienie do W słowa a_na_n-1...a₀.

Powyżej zdefiniowany kod uzupełnień do W jest kodem o zmiennej długości słowa kodowego. Zdefiniujemy teraz kod uzupełnień do W o stałej długości słowa kodowego.

Wykorzystamy następujący fakt:

Fakt: Wybierzmy dowolne m ∈ <−Wⁿ,Wⁿ−1>, gdzie n > 0 i ustalmy wagę W (W ∈ N, W ≥ 2). Wówczas istnieje dokładnie jeden ciąg: a_na_n-1...a₀, taki że dla każdego i = 1,2...,n, a_i ∈ {0,1,...,<i>W</i>−1} taki, że:

n = −(sgn a_n)Wⁿ + $\displaystyle\sum^{n-1}_{i=0}a_iW^i\qquad$(*)

Dowód: Prosty dowód pozostawiamy Czytelnikowi jako ćwiczenie.

Odwzorowanie $f$ :<−Wⁿ,Wⁿ−1>→<0,W−1>ⁿ zdefiniowane w powyższym twierdzeniu nosi nazwę zapisu uzupełnień do W (o stałej długości słowa kodowego).

Zakres tak zdefiniowanego kodu jest równy oczywiście <−Wⁿ,Wⁿ−1>.

Algorytm obliczania liczby przeciwnej do danej jest w zapisach uzupełnień do W (o stałej długości) jest następujący. Jeśli m ∈ <−Wⁿ,Wⁿ−1> i słowo a_na_n-1...a₀ reprezentuje tę liczbę to słowo reprezentujące  −m uzyskujemy jako uzupełnienie do W słowa a_na_n-1...a₀.

W systemach cyfrowych stosujemy głównie zapis uzupełnień do 2 (ang. two`s complement notation), który nazywany jest również zapisem U2. Jest to obok zapisu NKB najczęściej stosowany w technice mikroprocesorowej kod numeryczny. Popularność zapisu U2 wynika m.in. z faktu, że algorytmy dodawania i odejmowania w U2 dają się zrealizować a sposób naturalny w zwykłym, prostym sumatorze sumującym liczby w kodzie NKB.

W kodzie U2 (o stałej długości słowa n+1) słowo binarne a_na_n-1...a₀ związane jest z reprezentowaną tym słowem liczbą za pomocą wzoru

n = −(sgn a_n)2ⁿ + $\displaystyle\sum^{n-1}_{i=0}a_i2^i$ = −a_n2ⁿ + $\displaystyle\sum^{n-1}_{i=0}a_i2^i$

a zakres reprezentowanych liczb jest równy <−2ⁿ,2ⁿ−1>

Bit a_n nazywamy bitem najbardziej znaczącym lub bitem MSB od ang. Most Significant Bit) a bit a₀ bitem najmniej znaczącym lub bitem LSB od ang. Least Significant Bit.

W zapisie U2, żeby obliczyć –m mając kod U2 liczby m (czyli rozwinięcie, jak czasem mówimy) negujemy wszystkie bity i na najmniej znaczącej pozycji dodajemy arytmetycznie 1 (tzn. z uwzględnieniem przeniesień). Uzyskany wynik, tzn. słowo binarne reprezentuje tzn. jest kodem U2 liczby –m. Jest to bardzo wygodny algorytm ale uwaga –m musi należeć do zakresu zapisu.