Strona główna » Algorytmy » Artykuły » Kodowanie U2
U2
 

Kodowanie U2

· Znak - Moduł · Kodowanie U1 ·

Wstęp

U2 to system kodowania liczb całkowitych, który rozwiązuje problemy związane z implementacją kodowania U1. Dotyczy to przede wszystkim operacji arytmetycznych, ale też również problemu związanego z podwójną reprezentacją wartości 0. Kod U2 nosi nazwę uzupełnień do podstawy 2.

Opis kodowania

Przypuśćmy, że mamy zapis składajacy się z n bitów. Wtedy do obliczenia wartości tego zapisu skorzystamy ze wzoru: WZM = -bn - 1·-2n-1 + b·2n - 2 + .. + b2·22 + b1·2 + b0. Jak można zauważyć w przeciwieństwie do U1 do najbardziej znaczącej cyfry nie dodajemy wartości 1. Przeliczmy na początek kilka przykładów:

Zapis U2PrzeliczenieZakodowana
liczba
01010·-23 + 22 + 20 = 55
00100·-23 + 21 = 22
11011·-23 + 22 + 20 = -3-3
10111·-23 + 21 + 20 = -5-5

W wyniku zmiany wagi pierwszego bitu wszystkie liczby ujemne są o jeden mniejsze niż w kodowaniu U1. Liczby dodatnie dalej są kodowane w ten sam sposób, ponieważ ich pierwszy bit to nadal 0, więc zmiana wprowadzone we wzorze ich nie dotyczy.

Przeliczanie liczb dodatnich niezmiennie pozostaje takie samo jak w przypadku kodowania ZM oraz U1. Chcąc przeliczyć wartości dodatnie wystarczy wyznaczyć zapis binarny i z przodu dopisać tyle zer, aby zapis miał tyle bitów ile ustaliliśmy z góry. W tym przypadku kodujemy liczby dodatnie na 4 bitach:

Liczba
dziesiętna
ModułKod U1
4bity
Sprawdzenie
1100010·-23 + 20 = 1
711101110·-23 + 22 + 21 + 20 = 7

Najprostszym sposobem na przeliczenie liczby ujemnej na kodowanie U2 polega na wyznaczeniu zapisu modułu przeliczanej liczby. Następnie uzupełniamy z przodu 0 do n bitów, a na koniec negujemy liczbę.

Z kolei proces negowania polega jedynie na zanegowaniu wszystkich bitów zapisanych w kodzie U2, a następnie dodaniu 1 (tak jak się dodaje w systemie binarnym).

Liczba
dziesiętna
ModułUzupełnienieNegacja
(Kod U1 4bity)
Dodaj 1Sprawdzenie
-110001111011111·-23 + 23 + 22 + 21 = -1
-41000100101111001·-23 + 22 = -4
-71110111100010011·-23 + 20 = -7

Podczas procesu negowania możemy uzyskać nieprawidłową wartość. Liczba -8 to w zapisie U2 jest 1111U2. Chcą obliczyć jej wartość przeciwną należałoby ją zanegować i dodać 1, ale NOT(1111U2) + 1 = 0000U2 + 1 = 0001. Uzyskana wartość przeciwna to 1. Jest to konsekwenacja faktu, że usunięcie zera dołączyło dodatkową wartość ujemną 2n - 1, która z kolei nie posiada wartości przeciwnej. Z tego powodu warto uważać podczas negowania.

Jak wspomniałem zakres danych zwiększył się o jedną wartość z powodu usunięcia podwójnej reprezentacji liczby 0: [2n - 1, 2n - 1 - 1]. Jest on niesymetryczny. Można tutaj zauważyć, że 0 ma teraz dokładnie jedną reprezentację i są to same cyfry 0 = 00..0U2.

Arytmetyka

Dodawanie

Dzięki temu, że pierwszy bit posiada konkretną wartość dodawanie dwóch liczb w teorii nie różni się niczym od już znanego dodawania liczb binarnych. Nie ma również problemu związanego z przenoszeniem wartości 1 jeśli przekroczymy zakres jak w kodowaniu U1.

0001
0011
0100
1 + 3 = 4
0011
1001
1100
3 + (-7) = -4
1001
0101
1110
(-7) + 5 = (-2)
0011
0000
0011
3 + 0 = 3

Odejmowanie

W matematyce odejmowanie to inaczej dodawanie liczby przeciwnej, więc najpierw należy zanegować odejmowaną wartość, a następnie dodać ją do pierwszego argumentu. Dla przypomniena w celu zanegowania należy zanegować każdy bit i dodać do całej wartości 1.

 1001
- 1010
 1001
 0110
 1111
(-6) - (-5) =
(-6) + 5 = (-1)
 1000
-1000
 1000
 1000
 0000
(-7) - (-7) =
(-7) + 7 = 0

Liczba przeciwna

W celu otrzymania liczby przeciwnej wystarczy zanegować wszystkie bity i dodać wartość 1. Należy pamiętać, że liczba złożona z samych cyfr 1 nie ma liczby przeciwnej! Rozpatrzmy poniższe przypadki na zapisie 4 bitowym:

Wartość
dziesiętna
Zapis U1Liczba
przeciwna
Komentarz
100011111NOT(0001) + 1 = 1110 + 1 = 1111
300111101NOT(0011) + 1 = 1100 + 1 = 1101
-711100010NOT(1110) + 1 = 0001 + 1 = 0010
-811110001Brak liczby przeciwnej! -8 ≠ 1

Uwagi końcowe

Należy pamiętać, że jak w przypadku innych kodowań nie zawsze jest możliwe dodanie i odjęcie podanych argumentów. Zmienne posiadają pewien zakres, który po przekroczeniu zwykle powoduje uzyskanie złego wyniku. Jednak dla typowych obliczeń kodowanie to sprawdza się idealnie.

0001
0111
1000
1 + 7 = 8 ≠ 0
1110
1001
0111
(-2) + (-7) = (-9) ≠ 7
Implementacja
Część prywatna
Testowanie funkcji
Kod źródłowy ImplementacjaKod źródłowy Implementacja
Zadania
Zadanie 1
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1