Kodowanie U2

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: W_ZM = -b_{n - 1}·-2^n-1 + b·2_{n - 2} + .. + b₂·2₂ + b₁·2 + b₀. 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:

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:

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).

Podczas procesu negowania możemy uzyskać nieprawidłową wartość. Liczba -8 to w zapisie U2 jest 1111_U2. Chcą obliczyć jej wartość przeciwną należałoby ją zanegować i dodać 1, ale NOT(1111_U2) + 1 = 0000_U2 + 1 = 0001. Uzyskana wartość przeciwna to 1. Jest to konsekwenacja faktu, że usunięcie zera dołączyło dodatkową wartość ujemną 2^{n - 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: [2^{n - 1}, 2^{n - 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..0_U2.

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.

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.

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:

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.