KODOWANIE LICZB

WSTĘP

Współczesne komputery przetwarzają informację w postaci bitów, czyli symboli o dwóch podstawowych postaciach, które oznaczamy zwykle cyframi 0 i 1 (stąd pochodzi nazwa systemów zerojedynkowych). Nazwę bit wymyślił w czasie drugiego śniadania John Turkey w roku 1947. Słowo to pochodzi od liter angielskich wyrażeń binary (dwójkowy) oraz digit (cyfra), oznacza więc cyfrę dwójkową. John rozważał jeszcze dwie inne nazwy - binit oraz bigit, lecz, jak już wiemy, nie przyjęły się one
i mamy obecnie bit.

Bity są bardzo wygodne. Poniżej zebraliśmy kilka najważniejszych powodów ich popularności:

• bit ma tylko dwa stany, 0 i 1, dzięki czemu w prosty sposób można konstruować układy elektroniczne, które przetwarzają bity.

• łącząc bity w grupy można otrzymywać dowolną liczbę symboli złożonych, w których jednak wciąż występują podstawowe elementy o prostej postaci - bity. Ta własność umożliwia kodowanie dowolnie skomplikowanych informacji w postaci ciągu bitów.

• dwójkowy system zapisu liczb może być bezpośrednio przeniesiony na bity, co umożliwia kodowanie dowolnych liczb - dzięki temu komputery mogą wykonywać najbardziej skomplikowane obliczenia.

• operacje arytmetyczne w systemie dwójkowym są bardzo proste, więc również stosunkowo proste są układy liczące zrealizowane na bazie tego systemu

• dla bitów można zastosować bezpośrednio reguły algebry Boole'a, co umożliwia przeprowadzanie dowolnych operacji logicznych.

• w trakcie transmisji bitów, są one bardzo odporne na zakłócenia, więc system ten sprzyja tworzeniu sieci komputerowych.

KODOWANIE LICZB

JEDNOSTKI INFORMACJI

W tym rozdziale:

Bit
Grupa bitów

Bajt
Mnożniki binarne
Zadania

Podstawową jednostką informacji jest bit. To fakt ogólnie znany, jednak trudniej uczniom odpowiedzieć na pytanie, co właściwie oznacza to stwierdzenie. W jaki sposób bity można powiązać z informacją.

Informacja jest tworem czysto abstrakcyjnym. Nie istnieje materialnie. Nie można jej dotknąć, poczuć, zobaczyć. Informację da się natomiast wyrażać za pomocą symboli, znaków, kodu. Człowiek najczęściej używa słów, pisma, gestów do przekazywania informacji. Ta sama informacja (idea) może przybierać formę symboli, które, chociaż różne, oznaczają to samo pojęcie. Np. człowiek, human (ang.), Mensch (niem.), el hombre (hisz.), il uomo (wł.) - w każdym języku symbol (słowo) jest inne, lecz ich wspólną cechę stanowi to samo znaczenie, czyli właśnie informacja. Skoro do wyrażania informacji możemy używać różnych symboli (słów), to dlaczego nie zastosować do tego celu bitów? Należy tylko pokazać sposób, jak to zrobić. I tym właśnie się zajmiemy.

Bit

Taśma dziurkowana. Tak kiedyś zapisywano dane. Każda dziurka odpowiadała bitowi o stanie 1. Brak dziurki oznaczał stan 0.

Bit jest symbolem, który może przyjmować dwie różne postacie. Jeśli chcemy zapisać go na papierze, to stosujemy symbole pomocnicze 0 i 1. Technicznie bit realizowany jest za pomocą dwóch różnych sygnałów. W technice cyfrowej określa się poziomy napięć, które odpowiadają bezpośrednio dwóm postaciom bitu:

0,4 ... 0,8 V - stan 0 (oznaczany również L - Low - Niski)
2,0 ... 2,4 V - stan 1 (oznaczany również H - High - Wysoki)

Układy elektroniczne komputera reagują na te napięcia i w ten sposób przetwarzają bity. Zamiast napięć mogą to być również prądy o różnych natężeniach lub zwrotach, sygnały o dwóch rozróżnialnych częstotliwościach oraz wiele innych ciekawych sposobów, których opisanie zajęłoby nam co najmniej kilka lat ciężkiej pracy. Poprzestańmy więc na stwierdzeniu, iż bit to sygnał dwustanowy - jeden stan oznaczamy jako 0, a drugi jako 1.

Każdy ze stanów bitu może przenosić jedną wiadomość w identyczny sposób, jak np. słówko "stół" przenosi wiadomość na temat rzeczy z płaskim blatem i zwykle czterema nogami. Tyle tylko, iż słowa naszego języka mają ustalone od stuleci znaczenia, bity natomiast możemy przystosowywać do dowolnych wiadomości w miarę potrzeb. Jeden bit pozwoli w ten sposób przekazać jedną z dwóch wiadomości.

Czujnik ruchu. W razie wykrycia ruchu w okolicy przekazuje bit o stanie 1.

Przykład

Pojedyncze bity używane są do komunikacji z prostymi czujnikami, które reagują na określoną sytuację - np. gaz w chronionym pomieszczeniu, wzrost temperatury ponad wartość dopuszczalną, osiągnięcie przez ciecz w naczyniu określonego poziomu, otwarcie drzwi, przerwanie wiązki światła, itp.

Bit informacyjny z czujnika przekazywany jest do centrali na różne sposoby - przewodem elektrycznym, linią światłowodową, torem radiowym, itp. Ważne jest tylko to, iż w każdym z tych kanałów transmisyjnych wolno pojawić się tylko jednemu z dwóch stanów bitu - stanowi 0 (np. niskie napięcie, brak prądu, sygnał radiowy o małej amplitudzie itp.) lub stanowi 1 (np. wysokie napięcie, prąd w przewodzie, sygnał radiowy o dużej amplitudzie itp.).

Jeśli wiemy jak reaguje dany czujnik na określone zdarzenie (co oznaczają stany 0 i 1 przekazywane przez ten czujnik), to w prosty sposób możemy zinterpretować przekazywaną przezeń informację. Np. otrzymujemy sygnał o stanie 0 i wiemy, że oznacza on, iż czujnik nic nie wykrył. Jeśli teraz otrzymamy sygnał o stanie 1, oznaczający wystąpienie sytuacji, na którą reaguje dany czujnik, to od razu możemy to odpowiednio zinterpretować - np. wysłać ekipę strażacką do chronionego czujnikiem pomieszczenia lub włączyć samoczynną instalację przeciwpożarową. Możliwości jest bez liku, a wszystko za sprawą jednego bitu informacji.

ZAPAMIĘTAJ 1 bit może przekazać informację o dwóch różnych zdarzeniach. Bit oznaczamy małą literką b.

Grupa bitów

Aparat cyfrowy Zapamiętuje obraz jako długi ciąg bitów

Świat jest zbyt skomplikowany, aby zawrzeć go w dwóch wiadomościach. Dlatego bardzo prędko dojdziemy do sytuacji, gdzie należy operować kilkoma różnymi wiadomościami i bit stanie się niewystarczający. Na szczęście bity możemy łączyć w grupy i traktować je wspólnie jako symbol złożony. Przy takim podejściu otrzymujemy nieograniczone możliwości tworzenia słów binarnych i przypisywania im znaczeń.

Grupa dwóch bitów oddaje nam do dyspozycji cztery różne symbole, które powstają z kombinacji stanów tworzących je bitów:

00 - symbol pierwszy 01 - symbol drugi 10 - symbol trzeci 11 - symbol czwarty

Każdemu symbolowi możemy przypisać informację o osobnym zdarzeniu. Grupa dwóch bitów może więc przekazać informację o czterech różnych zdarzeniach.

Przykład

Załóżmy, iż chcemy zakodować binarnie obrazek pokazany poniżej: Jest on złożony z różnokolorowych punktów, które nazywamy pikselami (z języka ang. picture element - element obrazu, punkt).

Od razu zauważamy, że punkty są tylko w czterech kolorach. Układamy tablicę kodową kolorów, w której każdemu kolorowi punktu przyporządkujemy jeden symbol dwubitowy:

	- 00
	- 01
	- 10
	- 11

Powiązaliśmy w ten sposób informację z reprezentującymi ją symbolami. Teraz wystarczy już tylko każdy piksel zastąpić symbolem dwubitowym. W tej postaci obrazek może być przechowywany w pamięci komputera, przesyłany przez sieci teleinformatyczne oraz przetwarzany.

00	00	00	00	00	00	00	00	0000000000000000
00	00	11	11	11	11	00	00	0000111111110000
00	11	11	11	11	11	00	00	0011111111110000
00	00	11	11	11	11	11	00	0000111111111100
00	00	00	11	11	00	00	00	0000001111000000
00	00	00	00	10	00	00	00	0000000010000000
00	00	00	00	10	00	00	00	0000000010000000
01	01	01	01	01	01	01	01	0101010101010101

Zwróćmy uwagę na małą czytelność dla ludzi informacji zapisanej w systemie binarnym. Szczególnie, jeśli wszystkie bity zapiszemy w jednym ciągu:

0000000000000000000011111111000000111111111100000000111111111100000000111100000000000000100000000101010101010101

Należy jednak pamiętać o tym, iż system ten jest przeznaczony dla maszyn, które nie nudzą się i nie męczą.

Dwa bity dają nam cztery symbole. Jeśli zwiększymy liczbę bitów w grupie do trzech, to dostępna ilość symboli wzrośnie do ośmiu:

000-symbol pierwszy 001-symbol drugi 010-symbol trzeci 011-symbol czwarty 100-symbol piąty 101-symbol szósty 110-symbol siódmy 111-symbol ósmy

Wynika z tego, iż zwiększenie liczby bitów w grupie zwiększa dwukrotnie liczbę dostępnych symboli binarnych, które mogą przenosić informację o zdarzeniu. W poniższej tabeli dokonaliśmy odpowiednich obliczeń dla grup bitowych o długościach od 1 do 32 bitów.

liczba bitów	liczba symboli	liczba bitów	liczba symboli
1	2	17	131072
2	4	18	262144
3	8	19	524288
4	16	20	1048576
5	32	21	2097152
6	64	22	2097152
7	128	23	8388608
8	256	24	16777216
9	512	25	33554432
10	1024	26	67108864
11	2048	27	134217728
12	4096	28	268435456
13	8192	29	536870912
14	16384	30	1073741824
15	32768	31	2147483648
16	65536	32	4294967296

Liczba symboli wzrasta geometrycznie. Ogólnie dla grupy n bitowej liczba możliwych do wykorzystania symboli binarnych wyraża się liczbą 2ⁿ. Dla każdej skończonej liczby wiadomości zawsze możemy dobrać taką liczbę bitów, aby liczba słówek bitowych była równa lub większa od liczby wiadomości. Dla n wiadomości wystarczy, aby liczba bitów była równa części całkowitej wyrażenia (log₂(n - 1) + 1).

ZAPAMIĘTAJ n bitów daje 2^n symboli n symboli wymaga [log2(n - 1) + 1] bitów

Przykład

Drukarka komputerowa. Dane do druku przekazywane są w postaci ciągu bitów.

Zaprojektować kod binarny przeznaczony do kodowania małych liter alfabetu łacińskiego.

W tym przypadku wiadomościami będą literki. W alfabecie łacińskim jest ich 26: abcdefghijklmnopqrstuvwxyz. Każda literka musi być kodowana innym symbolem binarnym. Musimy określić zatem niezbędną liczbę bitów tworzących te symbole. W tym celu wykorzystujemy drugi z podanych wzorów i otrzymujemy:

[log₂(26 - 1) + 1] = [log₂25 + 1] = [4,64 + 1] = [5,64] = 5 bitów

5 bitów tworzy 32 symbole. Nam potrzebne jest 26, więc 6 symboli nie zostanie wykorzystanych. Od przybytku głowa nie boli. Ważne jest, aby symboli nie było mniej niż liczba wiadomości do zakodowania. Więcej w niczym nam nie przeszkadza - nawet lepiej, gdyż w przyszłości będzie można do takiego systemu dodać 6 nowych znaków (n. spacja, przecinek, kropka itp.).

W następnym kroku układamy tabelkę kodu znakowego, w której każdej literce przydzielamy jeden symbol binarny. Po tej operacji można literki przedstawiać jako symbole binarne oraz z symboli binarnych odczytywać literki. Odwzorowanie jest zatem obustronne.

Binarny kod znakowy
Znak	Kod	Znak	Kod	Znak	Kod	Znak	Kod
a	00000	h	00111	o	01110	v	10101
b	00001	i	01000	p	01111	w	10110
c	00010	j	01001	q	10000	x	10111
d	00011	k	01010	r	10001	y	11000
e	00100	l	01011	s	10010	z	11001
f	00101	m	01100	t	10011
g	00110	n	01101	u	10100

Zamieńmy na bity wg opracowanego schematu słowo "sowa":

s	- 10010
o	- 01110
w	- 10110
a	- 00000

Po połączeniu bitów w jeden ciąg otrzymujemy ostatecznie:

10010011101011000000

Dla człowieka zapis ten staje się zupełnie nieczytelny, lecz komputery radzą sobie z nim znakomicie - bity to ich żywioł. Spróbujmy teraz dokonać operacji odwrotnej, tzn. odczytać słowo zakodowane w bitach, które np. otrzymaliśmy za pomocą sieci teleinformatycznej z drugiego końca świata:

1001101110010101100001110

Najpierw rozdzielamy otrzymane bity na grupy po pięć sztuk:

10011    01110    01010    11000    01110

Dla każdej grupy bitów (symbolu binarnego) odszukujemy w tabelce kodu odpowiednią literkę:

10011	- t
01110	- o
01010	- k
11000	- y
01110	- o

Bajt

Chociaż wolno nam tworzyć kody binarne o dowolnej liczbie bitów na symbol, to jednak z technicznego punktu widzenia wygodnie jest przyjąć pewne ustalone jednostki. Standardowe grupy bitów można w prosty sposób przechowywać w pamięciach komputerów, na nośnikach danych oraz przesyłać za pomocą sieci teleinformatycznych.

Bajt jest taką właśnie standaryzacją. Najczęściej przyjmuje się, iż jest to grupa 8 bitów. Komórki pamięci komputera przechowują informację w postaci bajtów. Również wiele urządzeń przystosowane zostało do danych przekazywanych w takiej formie (porcjami po 8 bitów) - np. drukarki, terminale, modemy, dyski elastyczne i twarde, itp. Dlatego bajt stał się kolejną po bicie jednostką informacji. Bajt utożsamiany jest ze znakiem, literą, ponieważ używa się często 8 bitowego kodu do przekazywania znaków (ASCII - American Standard Code for Information Interchange).

ZAPAMIĘTAJ Bajt jest grupą 8 bitów.Oznaczamy go dużą literką B w odróżnieniu od bitu - b.1 B pozwala przekazywać informację o 256 zdarzeniach.

Mnożniki binarne

W fizyce i technice stosowane są wielokrotności jednostek podstawowych. Oznaczamy je odpowiednimi przyrostkami kilo, mega, giga i tera. Podstawą tych wielokrotności jest liczba 10:

kilo	= 1000	= 10^3
mega	= 1000000	= 10^6	= kilo x 1000
giga	= 1000000000	= 10^9	= mega x 1000
tera	= 1000000000000	= 10^12	= giga x 1000

W systemie binarnym, ze względu na podobieństwo, zastosowano również podobne mnożniki, jednakże podstawą ich jest liczba 2, nie 10, gdyż tak jest dużo wygodniej (pod koniec tego opracowania zrozumiesz dlaczego). Starano się przy tym, aby mnożnik binarny był jak najbliższy odpowiednikowi dziesiętnemu. I tak otrzymano:

Kilo	= 1024	= 2^10
Mega	= 1048576	= 2^20	= Kilo x 1024
Giga	= 1073741824	= 2^30	= Mega x 1024
Tera	= 1099511627776	= 2^40	= Giga x 1024

Dla odróżnienia mnożników binarnych od dziesiętnych zapisujemy je dużą literką. Jednostki binarne dzielimy na bitowe (podstawą jest bit) oraz bajtowe (podstawą jest bajt).

Jednostki binarne
bitowe		bajtowe
1b	bit	1B	bajt
1Kb	kilobit	1KB	kilobajt
1Mb	megabit	1MB	megabajt
1Gb	gigabit	1GB	gigabajt
1Tb	terabit	1TB	terabajt

ZAPAMIĘTAJ Podstawą mnożników binarnych jest liczba 2, a nie 10. Więc zamiast 1000 = 10^3 mamy 1024 = 2^10.

Zadania

1. Skoro informacja jest tworem niematerialnym, to w jaki sposób może być przetwarzana za pomocą maszyn liczących?

2. Ile bitów potrzebne jest do zakodowania każdej cyfry dziesiętnej? Podaj odpowiedni przykład.

3. Jak wzrośnie liczba słówek kodowych, jeśli zwiększymy dwukrotnie liczbę tworzących je bitów?

4. Ile bitów zawiera 1MB?

5. Ile bajtów zawiera 1,5GB?

Zadanie 1

Skoro informacja jest tworem niematerialnym, to w jaki sposób może być przetwarzana za pomocą maszyn liczących?

Komputery nie przetwarzają bezpośrednio samej informacji, lecz symbole, które ją reprezentują - bity. Bit ma formę fizyczną, więc może być przetwarzany. Ponieważ informacja jest powiązana z bitami, to przetwarzając bity komputery pośrednio przetwarzają informację.

Zadanie 2

Ile bitów potrzebne jest do zakodowania każdej cyfry dziesiętnej? Podaj odpowiedni przykład.

Cyfr dziesiętnych mamy 10 - {0,1,2,3,4,5,6,7,8,9}. Potrzebujemy zatem kodu binarnego, który potrafi przenosić 10 wiadomości. Każde słówko kodowe musi w tym celu posiadać:

n = [log₂(10-1) + 1] = [log₂9 + 1] = [3,17 + 1] = [4,17] = 4b

Każdej cyfrze przyporządkujemy jedno słówko kodowe. Przyporządkowanie to może być dowolne, ale najczęściej stosowane jest takie:

cyfra	kod
0	0000
1	0001
2	0010
3	0011
4	0100
5	0101
6	0110
7	0111
8	1000
9	1001

Zadanie 3

Jak wzrośnie liczba słówek kodowych, jeśli zwiększymy dwukrotnie liczbę tworzących je bitów?

Liczba słów binarnych dla n bitów jest równa 2ⁿ. Jeśli zwiększymy n dwukrotnie, to otrzymamy 2²ⁿ słówek kodowych. Ponieważ:

2²ⁿ = (2ⁿ)²

zatem możemy dać prostą odpowiedź: dwukrotny wzrost liczby bitów w słowie binarnym zwiększa do kwadratu liczbę tych słów.

Zadanie 4

Ile bitów zawiera 1MB?

Najpierw obliczamy liczbę bajtów:

1MB = 1024KB = 1024 x 1024B = 1048576B

Ponieważ 1B = 8b, to

1048576B = 1048576 x 8 = 8388608b

Zadanie 5

Ile bajtów zawiera 1,5GB?

Liczymy:

1,5 x 1024 x 1024 x 1024 = 1610612736B

KODOWANIE LICZB

NATURALNY KOD BINARNY

W tym rozdziale

Systemy pozycyjne
Dwójkowy system pozycyjny
Zakres naturalnych liczb dwójkowych
Ósemkowy system pozycyjny
Szesnastkowy system pozycyjny
Dwójkowe liczby stałoprzecinkowe
Zakres dwójkowych liczb stałoprzecinkowych
Zadania

W poprzednim rozdziale pokazaliśmy sposoby tworzenia złożonych symboli binarnych z grup bitów. Liczby moglibyśmy w zasadzie zakodować binarnie podobnie jak znaki - każdej z nich przypisując określoną kombinację stanów bitów. Jednakże w przeciwieństwie do znaków na liczbach chcemy przeprowadzać różne operacje arytmetyczne i otrzymywać wyniki zgodne z zasadami arytmetyki. Dlatego sposób przypisania bitów liczbom nie może być dowolny, lecz musi tworzyć system ułatwiający wykonywanie obliczeń - w przeciwnym razie elektroniczne układy arytmetyczne ogromnie by się skomplikowały, a tego nie chcemy.

Rozwiązanie tego problemu istnieje już od dawna, a nawet posługujemy się nim na co dzień - jest to pozycyjny system liczenia.

Systemy pozycyjne

Abakus. Prosty przyrząd wykorzystujący własności systemu pozycyjnego

Ponad tysiąc lat temu pewien hinduski geniusz wymyślił system zapisu liczb, w którym stosuje się jedynie dziesięć różnych znaków, zwanych cyframi. Za sprawą kupców arabskich system ten został rozpowszechniony w ówczesnym świecie i dzisiaj powszechnie jest znany pod nazwą systemu arabskiego. Cechą charakterystyczną tego systemu jest to, iż wartość cyfr w zapisie liczby zależy od ich pozycji. Np.

333

w liczbie tej występują trzy jednakowe cyfry - 3. Pierwsza jednak oznacza trzy setki, druga trzy dziesiątki, a ostatnia trzy jednostki. System ten jest dla nas tak naturalny, iż utożsamiamy wręcz wartość liczby z jej zapisem.

W systemie dziesiętnym podstawą jest liczba dziesięć. Wagi kolejnych pozycji licząc od prawej strony do lewej mają wartość kolejnych potęg podstawy. Wartość liczby jest sumą iloczynów wartości cyfr przez wagi swoich pozycji. Powyższy zapis możemy więc zapisać następująco:

333 = 3 x 10² + 3 x 10¹ + 3 x 10⁰

Jeśli przez p oznaczymy podstawę systemu (czyli 10), a przez c cyfrę ze zbioru {0,1,...,9}, to wartość dowolnej, n-cyfrowej liczby dziesiętnej wyrazi się wzorem:

c_n-1c_n-2...c₂c₁c₀ = c_n-1 x p^n-1 + c_n-2 x p^n-2 + ... + c₂ x p² + c₁ x p¹ + c₀ x p⁰

Powyższy wzór jest również prawdziwy, jeśli dokonamy zmiany wartości podstawy p. Na przykład dla p = 5 otrzymujemy system piątkowy. W systemie piątkowym mamy cyfry {0,1,2,3,4} - cyfry 5 nie ma z tych samych powodów, dla których w naszym systemie nie występuje cyfra 10. Obliczmy dla przykładu wartość liczby piątkowej 3214₍₅₎.

3214₍₅₎ = 3 x 5³ + 2 x 5² + 1 x 5¹ + 4 x 5⁰
3214₍₅₎ = 3 x 125 + 2 x 25 + 1 x 5 + 4 x 1
3214₍₅₎ = 375 + 50 + 5 + 4
3214₍₅₎ = 434

A teraz liczba trójkowa (p = 3, c - {0,1,2} ) 2012₍₃₎ :

2012₍₃₎ = 2 x 3³ + 0 x 3² + 1 x 3¹ + 2 x 3⁰
2012₍₃₎ = 2 x 27 + 0 x 9 + 1 x 3 + 2 x 1
2012₍₃₎ = 54 + 0 + 3 + 2
2012₍₃₎ = 59

Z przedstawionych przykładów można wysnuć wniosek, iż każdy system pozycyjny jest równie dobry do zapisu liczb. System dziesiętny jest tutaj o tyle wyjątkowy, iż stosujemy go do zapisu liczb i wydaje się on nam naturalnym systemem liczbowym. Jeśli jednak będziemy zmniejszać wartość podstawy, to w końcu dojdziemy do liczby 2. System liczenia oparty na liczbie 2 jest najprostszym systemem pozycyjnym i z tego powodu doskonale nadaje się do zastosowania w maszynowych rachunkach.

ZAPAMIĘTAJ W dowolnym systemie pozycyjnym o podstawie p mamy p cyfr c - {0,1,...,p-1}. Wagi kolejnych pozycji od strony prawej do lewej są kolejnymi od zera potęgami podstawy. Wartość liczby obliczamy jako sumę iloczynów cyfr przez wagi swoich pozycji. cn-1cn-2...c1c0 = cn-1p^n-1 + cn-2p^n-2 + ... + c1p^1 + c0p^0

Dwójkowy system pozycyjny

W systemie dwójkowym podstawa wynosi 2. Cyfr jest tylko dwie: 0 i 1. Dzięki temu cyfry dwójkowe mogą być bezpośrednio przedstawiane przy pomocy bitów, które również przyjmują dwa stany. Wartość liczby oblicza się szczególnie prosto - w sumie bierzemy tylko te wagi pozycji, na których występują cyfry 1. Oto przykład:

110111₍₂₎ = 1 x 2⁵ + 1 x 2⁴ + 0 x 2³ + 1 x 2² + 1 x 2¹ + 1 x 2⁰
110111₍₂₎ = 1 x 32 + 1 x 16 + 0 x 8 + 1 x 4 + 1 x 2 + 1 x 1
110111₍₂₎ = 32 + 16 + 4 + 2 + 1
110111₍₂₎ = 55

Liczby binarne zapisujemy najczęściej z określoną liczbą bitów (np. 4, 8, 16, 32...). Podyktowane to jest względami technicznymi. Na przykład pamięć komputera zapamiętuje w jednej komórce 8 bitów, więc rozsądnie jest przyjąć format zapisu liczby, który jest wielokrotnością 8 bitów. Bardzo pomocna jest znajomość pierwszych 16 liczb zapisanych w systemie binarnym. Proponujemy wyuczenie się na pamięć poniższej tabelki, co bardzo przyda się przy konwersjach pomiędzy systemami ósemkowym i szesnastkowym. Zwróćcie uwagę, iż dla początkowych liczb starsze wagi pozycji zawierają cyfry 0.

Pierwsze 16 liczb binarnych
0	0000	= 0 x 2^3 + 0 x 2^2 + 0 x 2^1 + 0 x 2^0
1	0001	= 0 x 2^3 + 0 x 2^2 + 0 x 2^1 + 1 x 2^0
2	0010	= 0 x 2^3 + 0 x 2^2 + 1 x 2^1 + 0 x 2^0
3	0011	= 0 x 2^3 + 0 x 2^2 + 1 x 2^1 + 1 x 2^0
4	0100	= 0 x 2^3 + 1 x 2^2 + 0 x 2^1 + 0 x 2^0
5	0101	= 0 x 2^3 + 1 x 2^2 + 0 x 2^1 + 1 x 2^0
6	0110	= 0 x 2^3 + 1 x 2^2 + 1 x 2^1 + 0 x 2^0
7	0111	= 0 x 2^3 + 1 x 2^2 + 1 x 2^1 + 1 x 2^0
8	1000	= 1 x 2^3 + 0 x 2^2 + 0 x 2^1 + 0 x 2^0
9	1001	= 1 x 2^3 + 0 x 2^2 + 0 x 2^1 + 1 x 2^0
10	1010	= 1 x 2^3 + 0 x 2^2 + 1 x 2^1 + 0 x 2^0
11	1011	= 1 x 2^3 + 0 x 2^2 + 1 x 2^1 + 1 x 2^0
12	1100	= 1 x 2^3 + 1 x 2^2 + 0 x 2^1 + 0 x 2^0
13	1101	= 1 x 2^3 + 1 x 2^2 + 0 x 2^1 + 1 x 2^0
14	1110	= 1 x 2^3 + 1 x 2^2 + 1 x 2^1 + 0 x 2^0
15	1111	= 1 x 2^3 + 1 x 2^2 + 1 x 2^1 + 1 x 2^0

ZAPAMIĘTAJ W systemie dwójkowym waga pozycji ma wartość 2. Występują tylko dwie cyfry 0 i 1. Wartość liczby obliczamy zgodnie ze wzorem: cn-1cn-2...c1c0 = cn-12^n-1 + cn-22^n-2 + ... + c12^1 + c02^0

Zakres naturalnych liczb dwójkowych

Oparliśmy system zapisu liczb binarnych na pozycyjnym systemie dwójkowym, ponieważ pozwalał on bezpośrednio kodować cyfry przy pomocy bitów. W następnym kroku określimy zakres liczb, które można przedstawić przy pomocy n bitów. Na początek dolna granica. Najmniejszą liczbę otrzymamy, gdy wszystkie cyfry przyjmą wartość 0. Wartość takiej liczby jest równa zero. Dolną granicą jest zatem liczba zero.

Górną granicę dla n bitów otrzymamy ustawiając wszystkie cyfry na 1. Będzie to największa liczba możliwa do zapisania przy pomocy n bitów. Jaką wartość ma taka liczba. Szybko przekonamy się wypisując kilka początkowych wartości:

dla n = 1 mamy	1(2)	= 1	= 2^1 - 1
dla n = 2 mamy	11(2)	= 3	= 2^2 - 1
dla n = 3 mamy	111(2)	= 7	= 2^3 - 1
dla n = 4 mamy	1111(2)	= 15	= 2^4 - 1

W każdym przypadku otrzymujemy za górną granicę liczbę równą 2ⁿ - 1. Podsumujmy:

ZAPAMIĘTAJ Dla n bitów możemy utworzyć w naturalnym kodzie binarnym liczby z zakresu: <0, 2^n - 1>

Sytuację odwrotną mamy, gdy dana jest określona liczba naturalna W, a chcemy poznać ilość bitów potrzebnych do jej zapisu w naturalnym systemie binarnym. W tym celu wystarczy, aby była spełniona prosta nierówność:

W  2ⁿ - 1,
gdzie n jest poszukiwaną liczbą bitów

Liczbę n obliczamy następująco:

n = [log₂W + 1]

ZAPAMIĘTAJ Do zapisu liczby naturalnej n potrzebne jest co najmniej [log2n + 1] bitów.

Ósemkowy system pozycyjny

Liczby binarne są niewygodne dla ludzi. Cyfry 0 i 1 dają zbyt małą różnorodność i nasze mózgi szybko się nużą przy analizowaniu długich ciągów bitów. Dlatego programiści często zastępują zapis binarny zapisem ósemkowym. Chociaż na początku może się to wydawać dziwne, to jednak ma sens. Otóż system ósemkowy i dwójkowy posiadają wspólną cechę - podstawą ich jest potęga liczby 2. Dzięki temu szczególnie prosto można przeliczać liczby pomiędzy tymi systemami.

Do zamiany liczb binarnych i ósemkowych potrzebna nam będzie prosta tabelka, w której każdą cyfrę ósemkową przedstawiamy w postaci trzech bitów.

cyfra ósemkowa	wartość dwójkowa
0	000
1	001
2	010
3	011
4	100
5	101
6	110
7	111

ZAPAMIĘTAJ W systemie ósemkowym waga pozycji ma wartość 8. Występuje osiem cyfr {0,1,2,3,4,5,6,7}. Wartość liczby obliczamy zgodnie ze wzorem: cn-1cn-2...c1c0 = cn-18^n-1 + cn-28^n-2 + ... + c18^1 + c08^0

Zamiana liczby dwójkowej na ósemkową

Mamy liczbę dwójkową 10111011010101₍₂₎. Zamienimy ją na liczbę w systemie ósemkowym o tej samej wartości. W tym celu bity dzielimy na grupy trzybitowe poczynając od końca. Jeśli w ostatniej grupie nie będzie trzech bitów, to dopisujemy na początku odpowiednią liczbę zer:

10111011010101
010 111 011 010 101

Każdą z grup trzybitowych zastępujemy cyfrą ósemkową z tabelki:

010 2

111 7

011 3

010 2

101 5

W wyniku otrzymujemy liczbę ósemkową o tej samej wartości:

10111011010101₍₂₎. = 27325₍₈₎

Sprawdźmy to:

10111011010101₍₂₎. = 8192 + 2048 + 1024 + 512 + 128 + 64 + 16 + 4 + 1 = 11989
27325₍₈₎ = 2 x 4096 + 7 x 512 + 3 x 64 + 2 x 8 + 5 x 1 = 8192 + 3584 + 192 + 16 + 5 = 11989

Otrzymaliśmy w obu wypadkach ten sam wynik, wobec tego zapis 10111011010101₍₂₎ oraz 27325₍₈₎ odnosi się do tej samej liczby o wartości dziesiętnej 11989.

ZAPAMIĘTAJ Przeliczeń pomiędzy systemem ósemkowym a binarnym dokonujemy zastępując cyfry ósemkowe ich trzybitową wartością w systemie dwójkowym. W odwrotną stronę zastępujemy grupy trzybitowe cyfrą ósemkową, która odpowiada im wartością.

Zamiana liczby ósemkowej na dwójkową

Operacja odwrotna jest równie prosta. W tym przypadku każdą cyfrę ósemkową zastępujemy trzybitową wartością z tabelki. W Wyniku otrzymamy liczbę dwójkową o tej samej wartości. Zamieńmy liczbę ósemkową 336724076102₍₈₎ na odpowiadającą jej liczbę binarną:

3 011

3 011

6 110

7 111

2 010

4 100

0 000

7 111

6 110

1 001

0 000

2 010

Zatem 336724076102₍₈₎ = 011011110111010100000111110001000010₍₂₎

Zwróćcie uwagę, iż zapis ósemkowy jest krótszy i bardziej czytelny dla ludzi od zapisu dwójkowego. Z tego właśnie powodu programiści wolą stosować liczby ósemkowe zamiast binarnych - zawsze przecież można je szybko przeliczyć w jedną i drugą stronę.

Szesnastkowy system pozycyjny

Drugim popularnym systemem służącym do zastępowania liczb binarnych jest system szesnastkowy. Podstawa w tym systemie ma wartość 16. Potrzebujemy zatem 16 cyfr, jednakże dorobiliśmy się ich tylko 10 - {0,1,2,3,4,5,6,7,8,9}. Brakujące 6 cyfr zastępujemy kolejnymi literkami alfabetu A,B,C,D,E i F. Cyfry te mają kolejne wartości: A = 10, B = 11, C = 12, D = 13, E = 14 i F = 15. Po tych ustaleniach możemy już zapisywać liczby w systemie szesnastkowym oraz obliczać ich wartość. Np. obliczmy wartość liczby 25FE₍₁₆₎. Korzystamy ze znanego wzoru:

25FE₍₁₆₎ = 2 x 4096 + 5 x 256 + 15 x 16 + 14 x 1 = 9726

ZAPAMIĘTAJ W systemie szesnastkowym, zwanym również heksadecymalnym, podstawa p = 16. Zbiór cyfr tworzą znaki: {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. Dodatkowe cyfry A,...,F mają wartości dziesiętne równe kolejno od 10 do 15. Wartość liczby szesnastkowej obliczamy według wzoru: cn-1cn-2...c1c0 = cn-116^n-1 + cn-216^n-2 + ... + c116^1 + c016^0

Konwersję pomiędzy systemem szesnastkowym a dwójkowym wykonujemy podobnie jak dla systemu ósemkowego - 16 jest również potęgą liczby 2. Potrzebna nam będzie tabelka wartości cyfr szesnastkowych w systemie dwójkowym. Każdej cyfrze szesnastkowej odpowiada grupa czterech bitów:

cyfra szesnastkowa	wartość dwójkowa
0	0000
1	0001
2	0010
3	0011
4	0100
5	0101
6	0110
7	0111
8	1000
9	1001
A	1010
B	1011
C	1100
D	1101
E	1110
F	1111

Zamiana liczby dwójkowej na szesnastkową

Liczbę dwójkową dzielimy na grupy czterobitowe poczynając od prawej strony. Jeśli w ostatniej grupie wypadnie mniej bitów, to dopełniamy je zerami. Następnie każdą grupę zastępujemy odpowiednią cyfrą szesnastkową. Dla przykładu zamieńmy liczbę binarną 111010100011101010101101101001110₍₂₎ na odpowiadającą jej wartość w systemie szesnastkowym:

111010100011101010101101101001110
0001 1	1101 D	0100 4	0111 7	0101 5	0101 5	1011 B	0100 4	1110 E

111010100011101010101101101001110₍₂₎ = 1D4755B4E₍₁₆₎

Zamiana liczby szesnastkowej na dwójkową

Zamiana polega na zastąpieniu każdej cyfry szesnastkowej odpowiadającą jej grupą czterech bitów z tabelki. W wyniku otrzymamy liczbę dwójkową o tej samej wartości. Dla przykładu zamieńmy liczbę FDA73201₍₁₆₎ na postać binarną:

F 1111

D 1101

A 1010

7 0111

3 0011

2 0010

0 0000

1 0001

Zatem FDA73201₍₁₆₎ = 11111101101001110011001000000001₍₂₎.

Dwójkowe liczby stałoprzecinkowe

System stałopozycyjny zapisu liczb jest rozszerzeniem zapisu liczb naturalnych w stronę wartości ułamkowych. W systemie dziesiętnym za cyfrą jednostek umieszcza się przecinek, a kolejne wagi pozycji są teraz ujemnymi potęgami podstawy:

253,763 = 2 x 10² + 5 x 10¹ + 3 x 10⁰ + 7 x 10^-1 + 6 x 10^-2 + 3 x 10^-3

Zasada ta obowiązuje również w innych systemach pozycyjnych. Dla przykładu obliczmy wartość stałopozycyjnej liczby piątkowej: 432,321₍₅₎:

432,321₍₅₎ = 4 x 5² + 3 x 5¹ + 2 x 5⁰ + 3 x 5^-1 + 2 x 5^-2 + 1 x 5^-3
432,331₍₅₎ = 4 x 25 + 3 x 5 + 2 x 1 + 3 x ¹/₅ + 2 x ¹/₂₅ + 1 x ¹/₁₂₅
432,331₍₅₎ = 100 + 15 + 2 + ³/₅ + ²/₂₅ + ¹/₁₂₅
432,331₍₅₎ = 117 ⁸⁶/₁₂₅
432,331₍₅₎ = 117,688

ZAPAMIĘTAJ W dowolnym systemie pozycyjnym o podstawie p wartość liczby stałoprzecinkowej obliczamy wg wzoru: cn-1...c0,c-1c-2...c-m = cn-1p^n-1 + ... + c0p^0 + c-1p^-1 + c-2p^-2 + ... +c-mp^-mgdzie n - liczba cyfr przed przecinkiem, m - liczba cyfr po przecinku

Znając tą zasadę nie napotkamy żadnych trudności w systemie dwójkowym. Obliczymy wartość dwójkowej liczby stałoprzecinkowej 1101,1011₍₂₎:

1101,1011₍₂₎ = 1 x 2³ + 1 x 2² + 0 x 2¹ + 1 x 2⁰ + 1 x 2^-1 + 0 x 2^-2 + 1 x 2^-3 + 1 x 2^-4
1101,1011₍₂₎ = 1 x 8 + 1 x 4 + 0 x 1 + 1 x 1 + 1 x ¹/₂ + 0 x ¹/₄ + 1 x ¹/₈ + 1 x ¹/₁₆
1101,1011₍₂₎ = 8 + 4 + 1 + ¹/₂ + ¹/₈ + ¹/₁₆
1101,1011₍₂₎ = 13 + ¹⁰/₁₆
1101,1011₍₂₎ = 13,625

Zakres dwójkowych liczb stałoprzecinkowych

Określimy zakres liczb stałoprzecinkowych, w których n bitów przechowuje część całkowitą, a m bitów część ułamkową. Wartość takiej liczby można zapisać jako sumę części całkowitej oraz części ułamkowej:

Jeśli liczbę zapiszemy za pomocą cyfr binarnych c, należących do zbioru {0,1}, to

W - wartość liczby = c_n-1c_n-2...c₂c₁c₀,c_-1c_-2...c_-m+1c_-m
W_c - wartość części całkowitej = c_n-1c_n-2...c₂c₁c₀
W_u - wartość części ułamkowej = c_-1c_-2...c_-m+1c_-m

W = W_c + W_u

W_c = c_n-12^n-1 + c_n-22^n-2 + ... + c₂2² + c₁2¹ + c₀2⁰
W_u = c_-12^-1 + c_-22^-2 + ... + c_-m+12^-m+1 + c_-m2^-m

Zakres części całkowitej policzyliśmy już wcześniej i wynosi on <0,2ⁿ - 1>. Policzymy zatem zakres części ułamkowej. Najmniejszą liczbę otrzymamy, gdy wszystkie cyfry będą zerami. Wartość ta wynosi oczywiście zero. Największą liczbę otrzymamy przy wszystkich cyfrach równych 1. Sprawdźmy ile to będzie dla kolejnych wartości m:

m = 1,	0,1	= 1 x 2^-1	= 1 x ^1/2	= ^1/2
m = 2,	0,11	= 1 x 2^-1 + 1 x 2^-2	= 1 x ^1/2 + 1 x ^1/4	= ^3/4
m = 3	0,111	= 1 x 2^-1 + 1 x 2^-2 + 1 x 2^-3	= 1 x ^1/2 + 1 x ^1/4 + 1 x ^1/8	= ^7/8

Jeśli przyjrzycie się otrzymanym wynikom, to na pewno zauważycie, iż mianownik otrzymanego ułamka ma wartość 2^m, natomiast licznik jest o 1 mniejszy, czyli 2^m - 1. Stąd zakres części ułamkowej wynosi:

<0,	2^m - 1	>
			2^m

Jeśli teraz połączymy zakresy części całkowitej i ułamkowej, to otrzymamy zakres liczby stałoprzecinkowej o n cyfrach całkowitych i m cyfrach ułamkowych, który wynosi:

<0, 2^n - 1 +	2^m - 1	>
			2^m

Zadania

1. Oblicz wartość następujących liczb:

1234₍₅₎, 3456₍₇₎, 5678₍₉₎

2. Oblicz wartość następujących liczb binarnych:

110011₍₂₎, 1110111₍₂₎, 11001110011₍₂₎

3. Jak wzrośnie zakres n bitowej liczby binarnej, jeśli zwiększymy jej długość o 3 bity?

4. Załóżmy, iż pewna liczba binarna posiada 3n bitów. Taką liczbę da się przedstawić w systemie ósemkowym za pomocą n cyfr. Jak rozpoznać w zapisie ósemkowym, iż najstarszy bit liczby binarnej ma wartość 1?

5. Jak określić liczbę cyfr ósemkowych liczby binarnej zapisanej w systemie szesnastkowym za pomocą n cyfr?

6. Oblicz wartość następującej liczby binarnej:

1100111,011101₍₂₎

Naturalny kod binarny

Zadanie 1

Oblicz wartość następujących liczb:

1234₍₅₎, 3456₍₇₎, 5678₍₉₎

1234₍₅₎ = 1 x 5³ + 2 x 5² + 3 x 5¹ + 4 x 5⁰
1234₍₅₎ = 1 x 125 + 2 x 25 + 3 x 5 + 4 x 1
1234₍₅₎ = 125 + 50 + 15 + 4
1234₍₅₎ = 194

3456₍₇₎ = 3 x 7³ + 4 x 7² + 5 x 7¹ + 6 x 7⁰
3456₍₇₎ = 3 x 343 + 4 x 49 + 5 x 7 + 6 x 1
3456₍₇₎ = 1029 + 196 + 35 + 6
3456₍₇₎ = 1266

5678₍₉₎ = 4 x 9³ + 6 x 9² + 7 x 9¹ + 8 x 9⁰
5678₍₉₎ = 4 x 729 + 6 x 81 + 7 x 9 + 8 x 1
5678₍₉₎ = 2916 + 486 + 63 + 8
5678₍₉₎ = 3473

Zadanie 2

Oblicz wartość następujących liczb binarnych:

110011₍₂₎, 1110111₍₂₎, 11001110011₍₂₎

110011₍₂₎ = 1x2⁵ + 1x2⁴ + 0x2³ + 0x2² + 1x2¹ + 1x2⁰
110011₍₂₎ = 1x32 + 1x16 + 0x8 + 0x4 + 1x2 + 1x1
110011₍₂₎ = 32 + 16 + 2 + 1
110011₍₂₎ = 51

1110111₍₂₎ = 1x2⁶ + 1x2⁵ + 1x2⁴ + 0x2³ + 1x2² + 1x2¹ + 1x2⁰
1110111₍₂₎ = 1x64 + 1x32 + 1x16 + 0x8 + 1x4 + 1x2 + 1x1
1110111₍₂₎ = 64+32+16+4+2+1
1110111₍₂₎ = 119

11001110011₍₂₎ = 1x2¹⁰+1x2⁹+0x2⁸+0x2⁷+1x2⁶+1x2⁵+1x2⁴+0x2³+0x2²+1x2¹+1x2⁰
11001110011₍₂₎ = 1x1024+1x512+0x256+0x128+1x64+1x32+1x16+0x8+0x4+1x2+1x1
11001110011₍₂₎ = 1024 + 512 + 64 + 32 + 16 + 2 + 1
11001110011₍₂₎ = 1651

Zadanie 3

Jak wzrośnie zakres n bitowej liczby binarnej, jeśli zwiększymy jej długość o 3 bity?

Aby znaleźć odpowiednie zależności, sprawdźmy kilka początkowych zakresów:

n = 1 - zakres <0,1>
n+3 = 4 - zakres <0,15> - wzrost o 14

n = 2 - zakres <0,3>
n+3 = 5 - zakres <0,31> - wzrost o 28

n = 3 - zakres <0,7>
n+3 = 6 - zakres <0,63> - wzrost o 56

Widzimy już prawidłowość. Dla kolejnych n możemy wypisać:

n = 1, wzrost 14 = 16 - 2 = 2⁴ - 2¹ = 2ⁿ⁺³ - 2ⁿ
n = 2, wzrost 28 = 32 - 4 = 2⁵ - 2² = 2ⁿ⁺³ - 2ⁿ
n = 3, wzrost 56 = 64 - 8 = 2⁶ - 2³ = 2ⁿ⁺³ - 2ⁿ
...

Zatem ostatecznie odpowiadamy, iż wzrost długości n bitowej liczby binarnej o 3 bity powoduje zwiększenie jej zakresu o czynnik:

2ⁿ⁺³ - 2ⁿ

Zadanie 4

Załóżmy, iż pewna liczba binarna posiada 3n bitów. Taką liczbę da się przedstawić w systemie ósemkowym za pomocą n cyfr. Jak rozpoznać w zapisie ósemkowym, iż najstarszy bit liczby binarnej ma wartość 1?

W tym celu należy zbadać najstarszą cyfrę ósemkową. Ponieważ cyfra ósemkowa zastępuje trzy cyfry binarne, to dla najstarszego bitu równego 1 otrzymujemy następujące cyfry ósemkowe:

100 - 4
101 - 5
110 - 6
111 - 7

Odpowiedź brzmi: liczba binarna 3n bitowa ma najstarszy bit równy 1, jeśli w jej reprezentacji ósemkowej najstarszą cyfrą ósemkową jest jedną z cyfr 4, 5, 6 lub 7.

Zadanie 5

Jak określić liczbę cyfr ósemkowych liczby binarnej zapisanej w systemie szesnastkowym za pomocą n cyfr?

Każda cyfra szesnastkowa zastępuje 4 cyfry binarne. Dlatego n cyfrowa liczba szesnastkowa odpowiada 4n bitowej liczbie binarnej. Z kolei cyfra ósemkowa zastępuje 3 cyfry binarne, zatem dla 4n cyfr binarnych potrzebujemy ⁴/₃n cyfr ósemkowych. Liczba ta musi być zaokrąglona w górę do najbliższej liczby całkowitej.

Zadanie 6

Oblicz wartość następującej liczby binarnej:

1100111,011101₍₂₎ = 103,453125KODOWANIE LICZB

Kod Gray'a

W tym rozdziale

Konstrukcja wyrazów kodu Gray'a
Przeliczanie kodu Gray'a na kod binarny
Zadania

Konstrukcja wyrazów kodu Gray'a

Istnieje wiele przykładów sytuacji, gdzie wymaga się, aby kolejne wyrazy kodowe różniły się między sobą wartością tylko jednego bitu. Jedną z nich są układy pomiarowe (np. kąta zgięcia ramienia robota). Załóżmy, iż w takim przypadku zastosowano zwykły kod binarny, dla uproszczenia 3 bitowy. Za pomocą tego kodu przedstawiamy kolejne wartości ugięcia ramienia w zakresie od 0 do 70° z dokładnością co 10°:

Kod	Wychylenie
000	0°
001	10°
010	20°
011	30°
100	40°
101	50°
110	60°
111	70°

Teraz załóżmy, iż kod binarny tworzony jest na podstawie odczytu czujników np. krzywkowych, które przy odpowiednim położeniu ramienia zwierają zestyki przekaźników lub zamykają strumień świetlny dla fotodiody. Cechą charakterystyczną takich rozwiązań jest to, iż z uwagi na różne luzy w układzie krzywka - zestyki następuje przełączanie bitów w różnych punktach, przez co nie wszystkie bity zmieniają się równocześnie. Rozważmy przypadek, gdy ramię robota przesuwa się z położenia 30° na 40°. W pierwszym przypadku kod wynosi 011. Teraz na skutek nie jednoczesnych przełączeń bitów mogą właściwie pojawić się wszystkie dostępne słowa kodowe zanim ustali się wartość 100 dla 40°. Np.

011 - 111 - 100

Powyżej pokazaliśmy możliwe przejście ze stanu 011 do 100. Na początku mamy słowo kodowe 011, które informuje o zajęciu przez ramię robota położenia 30°. Komputer sterujący robotem włącza teraz silniki obrotu ramienia i odczytuje stan czujników. Niestety, na skutek luzów pierwszy bit ustalił się na 1, ale pozostałe 2 nie przeszły jeszcze w stan 0. Co może w takim przypadku "pomyśleć" komputer sterujący  ramieniem? Pomyśli, iż ramię jest w położeniu krańcowym, tzn. 70° i zmieni obroty silnika, aby cofnąć je z powrotem na 40°. Kod zmieni się na 011, a więc znów będziemy w położeniu wyjściowym. Komputer zmieni kierunek obrotów,  odczyta kod 111 i zapętli się.

Oczywiście w praktyce konstruktor robota na pewno odpowiednio zabezpieczył by się przed taką możliwością. Jednakże problem istnieje, ponieważ dobraliśmy zły kod. Lepszym rozwiązaniem jest kod Gray'a, który ma taką własność, iż kolejne wyrazy różnią się między sobą wartością tylko jednego bitu. Zobaczmy, jak to zadziała w naszym przykładzie:

Kod	Wychylenie
000	0°
001	10°
011	20°
010	30°
110	40°
111	50°
101	60°
100	70°

Teraz poprzednio opisany problem nie wystąpi, ponieważ przejście z kodu 010 dla 30° na 110 dla 40° zmienia stan tylko pierwszego bitu. Z tego powodu kod Gray'a jest lepszy od naturalnego kodu binarnego w układach pomiarowych, gdzie należy zachować ciągłość odczytów.

ZAPAMIĘTAJ Można zaprojektować wiele różnych kodów Gray'a. Ich wspólną cechą jest to, iż kolejne wyrazy kodowe różnią się między sobą wartością tylko jednego bitu.

Aby otrzymać i-ty wyraz kodu Gray'a wykonujemy następujące operacje:

1. Zapisujemy numer wyrazu kodu Gray'a w naturalnym kodzie dwójkowym na zadanej liczbie bitów.

2. Pod spodem wypisujemy ten sam numer przesunięty w prawo o 1 bit. Najmniej znaczący bit odrzucamy. Na początku dopisujemy bit o wartości 0.

3. Nad odpowiadającymi sobie bitami wykonujemy operację logiczną XOR. Wynik jest wyrazem w kodzie Gray'a.

Dla przykładu znajdźmy tą metodą wszystkie 16 wyrazów 4 bitowego kodu Gray'a:

Wyraz 0	Kod dwójkowy 0000	0000 XOR 0000 0000	Kod Gray'a 0000
Wyraz 1	Kod dwójkowy 0001	0001 XOR 0000 0001	Kod Gray'a 0001
Wyraz 2	Kod dwójkowy 0010	0010 XOR 0001 0011	Kod Gray'a 0011
Wyraz 3	Kod dwójkowy 0011	0011 XOR 0001 0010	Kod Gray'a 0010
Wyraz 4	Kod dwójkowy 0100	0100 XOR 0010 0110	Kod Gray'a 0110
Wyraz 5	Kod dwójkowy 0101	0101 XOR 0010 0111	Kod Gray'a 0111
Wyraz 6	Kod dwójkowy 0110	0110 XOR 0011 0101	Kod Gray'a 0101
Wyraz 7	Kod dwójkowy 0111	0111 XOR 0011 0100	Kod Gray'a 0100
Wyraz 8	Kod dwójkowy 1000	1000 XOR 0100 1100	Kod Gray'a 1100
Wyraz 9	Kod dwójkowy 1001	1001 XOR 0100 1101	Kod Gray'a 1101
Wyraz 10	Kod dwójkowy 1010	1010 XOR 0101 1111	Kod Gray'a 1111
Wyraz 11	Kod dwójkowy 1011	1011 XOR 0101 1110	Kod Gray'a 1110
Wyraz 12	Kod dwójkowy 1100	1100 XOR 0110 1010	Kod Gray'a 1010
Wyraz 13	Kod dwójkowy 1101	1101 XOR 0110 1011	Kod Gray'a 1011
Wyraz 14	Kod dwójkowy 1110	1110 XOR 0111 1001	Kod Gray'a 1001
Wyraz 15	Kod dwójkowy 1111	1111 XOR 0111 1000	Kod Gray'a 1000

Zbierzmy otrzymane wyniki w tabeli. Kolorem czerwonym zaznaczyliśmy bity, które ulegają zmianie w stosunku do poprzedniego wyrazu.

Lp.	Kod binarny	Kod Gray'a
0	0000	0000
1	0001	0001
2	0010	0011
3	0011	0010
4	0100	0110
5	0101	0111
6	0110	0101
7	0111	0100
8	1000	1100
9	1001	1101
10	1010	1111
11	1011	1110
12	1100	1010
13	1101	1011
14	1110	1001
15	1111	1000

Zwróćcie uwagę, iż wyrazy kodu Gray'a tworzą zamknięty pierścień. Ostatni wyraz różni się od pierwszego również tylko jednym bitem. Tego typu kod nazywamy kodem Gray'a odzwierciedlonym binarnie (ang. binary reflected Gray code), ponieważ powstał przez proste przekształcenie kodu dwójkowego.

Przeliczanie kodu Gray'a na kod binarny

Przekształcenie kodu dwójkowego w kod Gray'a, jak obserwowaliśmy w poprzednim paragrafie, jest dosyć proste. Równie mało skomplikowana jest operacja odwrotna.  Przeliczenia dokonujemy kopiując najstarszy bit kodu Gray'a do najstarszego bitu kodu binarnego. Pozostałe bity otrzymamy wykonując operację XOR na i-tym bicie kodu Gray'a i (i+1) bicie wyrazu binarnego. Dla przykładu przeliczmy słowo w kodzie Gray'a 1110 na odpowiadające mu słowo dwójkowe:

Operacja	Opis
1110      1???	Przepisujemy najstarszy bit z kodu Gray'a do najstarszego bitu słowa dwójkowego. Bity te w obu kodach mają tą samą wartość.
1110 XOR  1   10??	Otrzymany bit umieszczamy na pozycji przesuniętej w prawo o jedno miejsce i wykonujemy operację XOR z bitem kodu Gray'a. W ten sposób otrzymujemy kolejne bity kodu dwójkowego. W tym przypadku dostajemy bit o wartości 0.
1110 XOR   0  101?	Identyczną operację wykonujemy z poprzednio otrzymanym bitem o wartości 0 otrzymując bit kodu dwójkowego o wartości 1.
1110 XOR    1 1011	Ostatnia operacja daje w wyniku słowo binarne 1011, które posłużyło do utworzenia słowa kodu Gray'a o wartości 1110, co można sprawdzić w poprzedniej tabelce.

Zadania

1. Wyszukaj w Internecie trzy sensowne zastosowania kodu Gray'a. Opisz je wraz z przykładami.

2. Przelicz następujące słowa dwójkowe na odpowiadające im kody Gray'a:

11001101,   00111100,  10001111

3. Przelicz następujące słowa kodu Gray'a na odpowiadające im kody dwójkowe:

11001101,   00111100,  10001111

4. Skonstruuj trzy alternatywne, 3 bitowe kody Gray'a.

5. Czy kod Gray'a jest kodem pozycyjnym?

Kod Gray'a

Zadanie 1

Wyszukaj w Internecie trzy sensowne zastosowania kodu Gray'a. Opisz je wraz z przykładami.

Praca indywidualna studenta.

Zadanie 2

Przelicz następujące słowa dwójkowe na odpowiadające im kody Gray'a:

Kod dwójkowy 11001101	11001101 XOR 01100110 10101011	Kod Gray'a 10101011
Kod dwójkowy 00111100	00111100 XOR 00011110 00100010	Kod Gray'a 00100010
Kod dwójkowy 10001111	10001111 XOR 01000111 11001000	Kod Gray'a 11001000

Zadanie 3

Przelicz następujące słowa kodu Gray'a na odpowiadające im kody dwójkowe:

11001101          1???????	00111100          0???????	10001111          1???????
11001101 XOR 1       10??????	00111100 XOR 0       00??????	10001111 XOR 1       11??????
11001101 XOR  0      100?????	00111100 XOR  0      001?????	10001111 XOR  1      111?????
11001101 XOR   0     1000????	00111100 XOR   1     0010????	10001111 XOR   1     1111????
11001101 XOR    0    10001???	00111100 XOR    0    00101???	10001111 XOR    1    11110???
11001101 XOR     1   100010??	00111100 XOR     1   001010??	10001111 XOR     0   111101??
11001101 XOR      0  1000100?	00111100 XOR      0  0010100?	10001111 XOR      1  1111010?
11001101 XOR       0 10001001	00111100 XOR       0 00101000	10001111 XOR       0 11110101

Zadanie 4

Skonstruuj trzy alternatywne, 3 bitowe kody Gray'a.

Najprostszym sposobem utworzenia nowych kodów Gray'a jest permutacja kolumn kodu podstawowego. Oto przykłady:

Kod Gray'a 321	Wersja 312	Wersja 123	Wersja 231
000	000	000	000
001	010	100	001
011	011	110	101
010	001	010	100
110	101	011	110
111	111	111	111
101	110	101	011
100	100	001	010

Zadanie 5

Czy kod Gray'a jest kodem pozycyjnym?

Nie, wartość kodu Gray'a nie można obliczyć na podstawie cyfr i wag pozycji - jest ona wynikiem odpowiedniej kombinacji tworzących go bitów.

Kod BCD

W tym rozdziale

System Dziesiętny Kodowany Binarnie
Wartość liczb w kodzie BCD
Arytmetyka w systemie BCD
Zadania

System Dziesiętny Kodowany Binarnie

System binarny jest wygodny do prowadzenia obliczeń maszynowych. Jednakże istnieje duża liczba zastosowań urządzeń obliczeniowych, gdzie występuje częsta potrzeba konwersji dziesiętno-binarnych - np. kalkulatory, kasy sklepowe, wagi, urządzenia pomiarowe, liczniki itp. Dla takich zadań opracowano kod BCD - Binary Coded Decimal, czyli dziesiętny kodowany binarnie. Stanowi on połączenie zalet dwójkowego kodowania z czytelnością liczb dziesiętnych.

Wartość liczb w kodzie BCD

W systemie BCD każdą cyfrę dziesiętną liczby kodujemy za pomocą 4 bitów tworzących wartość tej cyfry w systemie dwójkowym. Np. liczbę 2379 zakodujemy następująco:

2 0010

3 0011

7 0111

9 1001

W efekcie otrzymujemy kod BCD tej wartości:

2379₍₁₀₎ = 0010001101111001_(BCD)

Mając liczbę w kodzie BCD rozdzielamy jej bity na grupy 4 bitowe. Każdą grupę traktujemy jak cyfrę dziesiętną. Dlatego wartości uzyskanych cyfr przemnażamy przez kolejne potęgi podstawy systemu dziesiętnego, czyli 10. Wyniki iloczynów sumujemy. Np.:

01101000100100110110_(BCD) = 0110 1000 1001 0011 0110
01101000100100110110_(BCD) = 6 x 10⁴ + 8 x 10³ + 9 x 10² + 3 x 10¹ + 6 x 10⁰
01101000100100110110_(BCD) = 6 x 10000 + 8 x 1000 + 9 x 100 + 3 x 10 + 6 x 1
01101000100100110110_(BCD) = 60000 + 8000 + 900 + 30 + 6
01101000100100110110_(BCD) = 68936

Ponieważ cyfry dziesiętne kodowane są na 4 bitach, liczby BCD zawsze posiadają długość będącą wielokrotnością liczby 4. Kod BCD nie jest kodem efektywnym. Np. jedno bajtowa liczba BCD może pomieścić tylko dwie cyfry dziesiętne. Wykorzystane zatem zostaje jedynie 100 słów kodowych (dla liczb od 0 do 99), podczas gdy 1 bajt może przyjąć postać 256 różnych słówek kodowych - 156 nie będzie wykorzystanych. To więcej niż połowa. Przy liczbach 2 bajtowych stosunek ten jest jeszcze gorszy - 10000 liczb z 65536 słów kodowych. Zatem łatwość konwersji na system dziesiętny okupiona została efektywnością kodowania informacji i dlatego system BCD stosowany jest tylko tam, gdzie się to naprawdę opłaca (np. przy obliczeniach, gdzie zależy nam na zminimalizowaniu błędów zaokrągleń przy konwersji dwójkowo-dziesiętnej).

Bardzo miłą cechą kodu BCD jest to, iż w systemie szesnastkowym poszczególne cyfry dziesiętne odpowiadają bezpośrednio cyfrom szesnastkowym 0...9. Dzięki tej własności można w prosty sposób wprowadzać wartości BCD jako liczby szesnastkowe:

1672₍₁₆₎ = 0001011001110010₍₂₎ = 0001 0110 0111 0010_(BCD) = 1672₍₁₀₎

ZAPAMIĘTAJ W systemie BCD każda cyfra dziesiętna wartości liczby zajmuje 4 bity. Bity te przedstawiają dwójkowa wartość cyfry.

Arytmetyka w systemie BCD

Ponieważ liczby w kodzie BCD nie są naturalnymi liczbami dwójkowymi, zatem nie można nad nimi wykonywać normalnych działań arytmetycznych. Sprawdźmy:

15 + 35 0001 0101 +   0011 0101		24 -15 0010 0100 - 0001 0101
0100 1010 Wynik nie BCD!		0000 1111 Wynik nie BCD!

Po wykonaniu standardowej operacji nad liczbami w kodzie BCD należy sprawdzić i w razie potrzeby skorygować wynik. Dla dodawania i odejmowania korekcja będzie potrzebna wtedy, gdy dana grupa bitów reprezentujących cyfrę dziesiętną ma wartość większą od 9 (binarnie 1001). W takiej sytuacji do grupy tej należy dodać (dla odejmowania odjąć) wartość binarną 0110 (dziesiętnie 6). Sprawdźmy ponownie (kolorem czerwonym zaznaczyliśmy korekcję wyniku):

15 + 35 0001 0101 +   0011 0101		24 -15 0010 0100 - 0001 0101
0100 1010 + 0000 0110		0000 1111 - 0000 0110
0101 0000 Wynik = 50		0000 1001 Wynik = 9

Korekcja musi również wystąpić, gdy w trakcie dodawania wystąpiło przeniesienie (przy odejmowaniu pożyczka) do sąsiedniej grupy bitów. Np:

29 + 19 0010 1001 +   0001 1001		31 -18 0011 0001 - 0001 1000
0100 0010 + 0000 0110		0001 1001 - 0000 0110
0100 1000 Wynik = 48		0001 0011 Wynik = 13

ZAPAMIĘTAJ W systemie BCD korekcja przy dodawaniu polega na dodaniu (lub odjęciu przy odejmowaniu) do grupy bitów reprezentujących cyfrę dziesiętną liczby 0110 (6). Korekcję wykonujemy, gdy po operacji arytmetycznej: grupa bitów nie przedstawia cyfry dziesiętnej nastąpiło przeniesienie (pożyczka) do następnej grupy bitów

Zadania

1. Podaj wzór obliczania wartości liczby w kodzie BCD.

2. Oblicz zakres n bitowych liczb w kodzie BCD. Jaki jest zakres 10 bitowych liczb BCD?

3. Zaproponuj sposób przedstawiania liczb ujemnych w kodzie BCD oraz określ reguły ich dodawania i odejmowania.

Kod BCD

Zadanie 1

Podaj wzór obliczania wartości liczby w kodzie BCD.

W celu znalezienia wzoru obliczeniowego rozważmy wagi pozycji 12 bitowej liczby BCD:

Cyfra dziesiętna

d2

d1

d0

Waga pozycji

800 10^22^3

400 10^22^2

200 10^22^1

100 10^22^0

80 10^12^3

40 10^12^2

20 10^12^1

10 10^12^0

8 10^02^3

4 10^02^2

2 10^02^1

1 10^02^0

Cyfra dwójkowa

c11

c10

c9

c8

c7

c6

c5

c4

c3

c2

c1

c0

Waga i-tej pozycji w kodzie BCD ma wartość 10^[i/4] x 2^{i mod 4}. Wobec tego wzór na wartość liczby BCD jest następujący:

W_BCD = c_n-1...c₁c₀ = c_n-1 x 10^[(n-1)/4] x 2^{(n-1) mod 4} + ... + c₁ x 10⁰ x 2¹ + c₀ x 10⁰ x 2⁰

Zadanie 2

Oblicz zakres n bitowych liczb w kodzie BCD.  Jaki jest zakres 10 bitowych liczb BCD?

Najmniejszą wartość liczba BCD osiągnie dla wszystkich bitów równych 0. Czyli:

Z_BCDmin = 0

W celu obliczenia górnej granicy obliczamy liczbę pełnych cyfr dziesiętnych zakodowanych w czwórkach bitów liczby BCD. Liczbę tą znajdziemy jako część całkowitą z dzielenia n przez 4:

n_d = [n : 4]

Każda pozycja dziesiętna może przyjąć maksymalnie wartość 9. I tak:

dla n_d = 1   Z_BCDmax = 9 = 10¹ - 1
dla n_d = 2   Z_BCDmax = 99 = 10² - 1
dla n_d = 3   Z_BCDmax = 999 = 10³ - 1

Widzimy, że górny kres jest równy:

Z_BCDmax = 10^nd - 1 = 10^{[n : 4]} - 1

Może się okazać, iż liczba BCD zawiera więcej bitów niż wielokrotność 4. W takim przypadku najstarsze bity (których może być 0,1,2 lub 3) tworzą maksymalnie cyfrę o wartości:

Z_BCDmaxReszta = (2^{n mod 4} - 1) x 10^{[n : 4]}

Po zsumowaniu otrzymujemy ostatecznie:

Z_{BCDmaxCałość} = Z_BCDmax + Z_BCDReszta

Z_{BCDmaxCałość} = 10^{[n : 4]} - 1 + (2^{n mod 4} - 1) x 10^{[n : 4]}

Dla n = 10 otrzymujemy:

Z_BCDmax = 10^{[10 : 4]} - 1 + (2^{10 mod 4} - 1) x 10^{[10 : 4]}
Z_BCDmax = 10^[2,5] - 1 + (2² - 1) x 10^[2,5]
Z_BCDmax = 10² - 1 + (2² - 1) x 10²
Z_BCDmax = 100 - 1 + (4 - 1) x 100
Z_BCDmax = 99 + 3 x 100
Z_BCDmax = 399

Zadanie 3

Zaproponuj sposób przedstawiania liczb ujemnych w kodzie BCD oraz określ reguły ich dodawania i odejmowania.

Jeśli chcemy reprezentować w kodzie BCD wartości ujemne, to możemy, kosztem zmniejszenia zakresu, wykorzystać do tego celu najstarszy bit liczby. W takim przypadku najstarsza cyfra dziesiętna będzie reprezentowana przez trzy bity i nie może mieć wartości większej od 7. Reszta bitów może zostać potraktowana jako moduł liczby dziesiętnej. Dla tak skonstruowanych liczb BCD mają zastosowanie reguły arytmetyki liczb w kodzie Z-M z uwzględnieniem korekcji dziesiętnej.

KOD UZUPEŁNIEŃ DO 2

W tym rozdziale

Wartość liczby w kodzie U2
Zakres liczb w kodzie U2
Obliczanie wartości przeciwnej w kodzie U2
Znajdowanie reprezentacji liczby w kodzie U2
Arytmetyka liczb w kodzie U2
Nadmiar i niedomiar w kodzie U2
Zadania

Wartość liczby w kodzie U2

System zapisu liczb ze znakiem opisany w poprzednim rozdziale nie jest zbyt wygodny dla obliczeń maszynowych. Już przy tak prostych operacjach jak dodawanie i odejmowanie musimy stosować dodatkową logikę obsługi znaków, aby otrzymywać poprawne wyniki. Dlatego w obliczeniach komputerowych bardziej popularny jest inny system, zwany systemem uzupełnień do dwóch (w skrócie U2) lub uzupełnień do podstawy (w literaturze angielskiej nosi on nazwę Two's Complement Numbering System).

Pascalina - sumator Pascala

Idea systemu U2 nie jest nowa - wymyślił ją już Blaise Pascal, znany francuski fizyk i matematyk, który skonstruował w 1652 roku prostą maszynę arytmetyczną zdolną dodawać liczby dziesiętne. Aby umożliwić również odejmowanie liczb, Pascal wprowadził tzw. uzupełnienie do podstawy 10. Otrzymujemy je odejmując daną liczbę od podstawy podniesionej do potęgi równej największej ilości cyfr dodawanych liczb. Np. dla liczb z zakresu od 0..99 będziemy odejmować od 100 - 10², dla liczb z zakresu od 0..999 od 1000 - 10³ itd. Dla przykładu sprawdźmy jak to działa:

Chcemy wykonać odejmowanie: 56 - 27. W tym celu obliczamy uzupełnienie do podstawy 10 liczby 27:

- 27 = 100 - 27 = 73_(U10)

Teraz wykonujemy dodawanie liczby 56 oraz uzupełnienia 73_(U10):

56 + 73_(U10) = 129

Odrzucamy najstarszą jedynkę i mamy wynik 29. Zgadza się? Pascal też był z tego zadowolony.

Na identycznej zasadzie utworzono system uzupełnień do podstawy U2. W systemie tym waga pozycji najstarszego bitu jest ujemna. Jeśli bit na tej pozycji będzie miał wartość 0, to otrzymamy liczbę dodatnią, której wartość określają pozostałe bity. Gdy bit znaku przyjmie wartość 1, to liczba będzie ujemna. Wartość liczby obliczymy jako sumę wagi pozycji najstarszego bitu (jest ujemna) oraz pozostałej części liczby. Wzór obliczeniowy jest następujący:

W_U2 = c_n-1 x (- p^n-1) + c_n-2 x p^n-2 + ... + c₁ x p¹ + c₀ x p⁰

Obliczmy dla przykładu wartość liczb 4 bitowych w kodzie U2:

0101_(U2) =  0 x (- 2³) + 1 x 2² + 0 x 2¹ + 1 x 2⁰
0101_(U2) =  0 x (- 8) + 1 x 4 + 0 x 2 + 1 x 1
0101_(U2) =  0 + 4 + 1
0101_(U2) =  5

1101_(U2) =  1 x (- 2³) + 1 x 2² + 0 x 2¹ + 1 x 2⁰
1101_(U2) =  1 x (- 8) + 1 x 4 + 0 x 2 + 1 x 1
1101_(U2) =  (- 8) + 4 + 1
1101_(U2) =  - 8 + 5
1101_(U2) =  - 3

ZAPAMIĘTAJ Wartość liczby w kodzie U2 obliczamy bardzo podobnie do wartości liczby w naturalnym kodzie dwójkowym. Musimy tylko pamiętać, iż waga najstarszej pozycji (pozycji znakowej) jest ujemna. Dla n bitowej liczby U2 możemy zapisać wzór: WU2 = cn-1 x (- 2^n-1) + wartość reszty liczby w kodzie NBC

Zakres liczb w kodzie U2

Największą liczbę w kodzie U2 otrzymamy, gdy bit znaku przyjmie wartość 0 (liczba dodatnia), a reszta cyfr będzie składała się z samych jedynek. Reszta cyfr tworzy największą liczbę n-1 bitową w naturalnym kodzie binarnym, wobec tego:

Z_U2max = 2^n-1 - 1

Najmniejszą liczbę w kodzie U2 otrzymamy dla bitu znaku równego 1 (liczba ujemna) oraz pozostałych bitów równych zero. Stąd:

Z_U2min = -2^n-1

I ostatecznie zakres n-bitowej liczby w kodzie U2 jest następujący:

Z_U2 = <-2^n-1, 2^n-1 - 1>

Przykład

Obliczmy zakres 4 bitowych liczb w kodzie U2:

Z_U2max = 2^4-1 - 1 = 2³ - 1 = 8 - 1 = 7

Z_U2min = -2^4-1 = -2³ = -8

Dla czterech bitów Z_U2 = <-8, 7>.

W systemie U2 można również zapisywać liczby stałoprzecinkowe. Zastanówcie się nad wzorem obliczeniowym oraz zakresem liczb stałoprzecinkowych U2 o n cyfrach całkowitych i m cyfrach ułamkowych. Potraktujcie to jako ćwiczenie.

Obliczanie wartości przeciwnej w kodzie U2

Wartość przeciwna ma tą samą wartość bezwzględną, lecz znak przeciwny. W kodzie U2 obliczamy ją następująco:

ZAPAMIĘTAJ Aby znaleźć wartość przeciwną do danej w kodzie U2, wykonaj następujące dwie operacje: zmień wszystkie bity liczby na przeciwne (możesz wykorzystać do tego celu operację logiczną NOT). Do tak uzyskanej liczby dodaj 1

Dla przykładu obliczmy wartość przeciwną do liczby  0011_(U2) = 3:

NOT  0011

1100 +   0001

1101

Sprawdźmy:

1101_(U2) = 1 x (-2³) + 1 x 2² + 0 x 2¹ + 1 x 2⁰
1101_(U2) = 1 x (-8) + 1 x 4 + 0 x 2 + 1 x 1
1101_(U2) = -8 + 4 + 1
1101_(U2) = -3

Znajdowanie reprezentacji liczby w kodzie U2

Mamy wartość dziesiętną W i chcemy zapisać ją w n-bitowym kodzie U2. Najpierw musimy sprawdzić, czy zakres liczb U2 obejmuje wartość W. Jeśli tak, to:

• Dla W nieujemnego obliczamy liczbę dwójkową o tej wartości, a następnie dopełniamy ją zerami do formatu n-bitowego.

• Dla W ujemnego obliczamy uzupełnienie do podstawy 2 o wartości 2ⁿ + W. Wynik kodujemy binarnie i otrzymujemy liczbę ujemną w kodzie U2.

Przykład

Znaleźć zapis liczby 92 w 8 bitowym kodzie U2.

Liczba jest dodatnia, więc znajdujemy jej zapis binarny:

92 : 2 =	46	i reszta c0 = 0
46 : 2 =	23	i reszta c1 = 0
23 : 2 =	11	i reszta c2 = 1
11 : 2 =	5	i reszta c3 = 1
5 : 2 =	2	i reszta c4 = 1
2 : 2 =	1	i reszta c5 = 0
1 : 2 =	0	i reszta c6 = 1	, koniec

92 = 01011100_(U2)

Znaleźć zapis liczby -107 w 8 bitowym kodzie U2:

Liczba jest ujemna, więc najpierw obliczamy jej dopełnienie do podstawy:

Najpierw obliczamy uzupełnienie do podstawy:

U = 2ⁿ + W = 2⁸ - 107 = 256 - 107 = 149

Wyrażamy 149 binarnie

149 : 2 =	74	i reszta c0 = 1
74 : 2 =	37	i reszta c1 = 0
37 : 2 =	18	i reszta c2 = 1
18 : 2 =	9	i reszta c3 = 0
9 : 2 =	4	i reszta c4 = 1
4 : 2 =	2	i reszta c5 = 0
2 : 2 =	1	i reszta c6 = 0
1 : 2 =	0	i reszta c7 = 1	, koniec

-107 = 10010101_(U2)

Arytmetyka liczb w kodzie U2

Dodawanie i odejmowanie

Zasady dodawania i odejmowania liczb w kodzie U2 nie różnią się od zasad wykonywania tych działań arytmetycznych w zwykłym systemie binarnym, co jest niewątpliwą zaletą kodu U2. Sprawdźmy:

5 + (-3) 0101 +   1101		2-(-3) 0010 - 1101
1 0010 Wynik 2		1 0101 Wynik 5

Otrzymaliśmy poprawne wyniki operacji bez sprawdzania znaków przetwarzanych liczb. Jest to bardzo dużą zaletą kodu U2, dzięki której obliczenia są szybkie i sprawne.

ZAPAMIĘTAJ W systemie U2 dodawanie i odejmowanie wykonujemy wg poznanych zasad dla naturalnego kodu dwójkowego. Przeniesienia i pożyczki poza bit znaku ignorujemy.

Mnożenie

Mnożenie liczb w kodzie U2 różni się nieco od standardowego mnożenia liczb binarnych. Przed wykonaniem tej operacji arytmetycznej musimy rozszerzyć znakowo obie mnożone liczby tak, aby ich długość (liczba bitów) wzrosła dwukrotnie (jeśli są różnej długości, to rozszerzamy znakowo względem dłuższej liczby). Rozszerzenie znakowe polega na powielaniu bitu znaku na wszystkie dodane bity. Np.:

0111_(U2) = 0000 0111_(U2) - rozszerzyliśmy znakowo liczbę 4 bitową do 8 bitowej
1011_(U2) = 1111 1011_(U2) - to samo dla liczby ujemnej.

Rozszerzenie znakowe nie zmienia wartości liczby w kodzie U2. Po wykonaniu rozszerzenia znakowego liczby mnożymy wg poznanych już zasad. Dla przykładu pomnóżmy (-2) x 3:

-2 = 1110_(U2) - 1111 1110_(U2)
3 = 0011_(U2) = 0000 0011_(U2)

(-2) x 3 11111110 x   00000011

11111110 +  11111110

1011111010 Wynik = -6

Wynik mnożenia może być liczbą o długości równej sumie długości mnożonych liczb. Dlatego bity wykraczające w naszym przykładzie poza 8 bitów ignorujemy. Pozostałe 8 bitów określa w kodzie U2 liczbę -6. Zatem rachunek zgadza się.

Dzielenie

Najprostszym rozwiązaniem jest zapamiętanie znaków dzielonych liczb, zamiana ich na liczby dodatnie, dokonanie dzielenia dla liczb naturalnych, a następnie zmiana znaku wyniku, jeśli znaki dzielnej i dzielnika różnią się.

Podzielmy 6 przez -3:

6 = 0110_(U2)
-3= 1101_(U2) - zmieniamy na 3 = 0011_(U2)

Dzielimy liczbę 0110 przez 0011

    10
  0110 : 0011
- 011
  0000
  0011

Otrzymaliśmy wynik 0010  (liczba 2). Ponieważ znaki dzielnej i dzielnika są różne, zmieniamy znak wyniku na przeciwny:

NOT  0010

1101 +   0001

1110

I ostatecznie otrzymujemy wynik 1110_(U2) = -2.

Jeśli w trakcie dzielenia otrzymamy resztę, to musi ona mieć ten sam znak, co dzielna. Zbierzmy i podsumujmy  reguły określania znaków wyniku i reszty z dzielenia w poniższej tabelce.

Reguły znaków przy dzieleniu liczb całkowitych
Dzielna	Dzielnik	Wynik	Reszta
plus	plus	plus	plus
plus	minus	minus	plus
minus	plus	minus	minus
minus	minus	plus	minus

Nadmiar i niedomiar w kodzie U2

W trakcie wykonywania działań arytmetycznych wynik operacji może przekroczyć dozwolony zakres liczb zarówno powyżej górnej granicy (nadmiar) jak i poniżej dolnej (niedomiar). Cechą charakterystyczną nadmiaru/niedomiaru jest zmiana znaku wyniku w sytuacji, gdy nie powinna ona nastąpić. Załóżmy, iż operujemy na 4 bitowych liczbach w kodzie U2 i chcemy wykonać proste dodawanie:

0 111 +   0 001		7 + 1
1 000		-8

Otrzymany wynik jest niepoprawny w tym kodzie. Spowodowane to jest tym, iż liczba 8 będąca sumą 7 i 1 wykracza poza górny kres wartości 4 bitowego kodu U2 (równy 7) i nie można jej poprawnie przedstawić - musielibyśmy przeznaczyć na zapis liczby więcej bitów.

Podobną sytuację zastaniemy przy próbie dodania dwóch liczb ujemnych, np. -6 i -3:

1 010 +   1 101		-6 + -3
10 111		7

Liczba -9 jest mniejsza od dolnego krańca 4 bitowych liczb w kodzie U2 (równego -8) i z tego powodu nie może być poprawnie przedstawiona w tym kodzie.

ZAPAMIĘTAJ Wystąpienie nadmiaru lub niedomiaru jest wskazówką dla programisty, iż źle dobrał typ danych dla przetwarzanej informacji - liczby są reprezentowane zbyt małą ilością bitów i nie można poprawnie zapisywać wyniku operacji. Najprostszym rozwiązaniem będzie zwiększenie liczby bitów dla liczb w kodzie U2 (np. z 16 na 32).

W poniższej tabelce zebraliśmy reguły powstawania nadmiaru i niedomiaru przy różnych operacjach arytmetycznych na liczbach w kodzie U2.

Reguły powstawania nadmiaru/niedomiaru
Operacja	Pierwszy argument	Drugi argument	Wynik
DODAWANIE	plus	plus	minus
		minus	minus	plus
	ODEJMOWANIE	plus	minus	minus
		minus	plus	plus
	MNOŻENIE DZIELENIE	plus	plus	minus
		minus	minus	minus
		plus	minus	plus
		minus	plus	plus

Zadania

1. Oblicz wartość liczby binarnej 1101 traktując ją kolejno jako liczbę w naturalnym kodzie dwójkowym, w kodzie Z-M oraz w kodzie uzupełnień do podstawy. Wyciągnij wnioski.

2. Czy kod U2 jest efektywny?

3. Znajdź wartość przeciwną do podanych liczb w kodzie U2:

01011101   11111111   00000000   01111110   11110000

4. Znajdź zapis w 8 bitowym kodzie U2 następujących wartości dziesiętnych:

-100,  -48, 126

5. Oblicz wartość liczb stałoprzecinkowych w kodzie U2:

1101,111_(U2)   1,1_(U2)  100,001_(U2)

Kod uzupełnień do 2

Zadanie 1

Oblicz wartość liczby binarnej 1101 traktując ją kolejno jako liczbę w naturalnym kodzie dwójkowym, w kodzie Z-M oraz w kodzie uzupełnień do podstawy. Wyciągnij wnioski.

1101₍₂₎ = 1 x 2³ + 1 x 2² + 0 x 2¹ + 1 x 2⁰
1101₍₂₎ = 1 x 8 + 1 x 4 + 0 x 2 + 1 x 1
1101₍₂₎ = 8 + 4 + 1
1101₍₂₎ = 13

1101_(Z-M) = (1 - 2 x 1) x (1 x 2² + 0 x 2¹ + 1 x 2⁰)
1101_(Z-M) = (1 - 1) x (1 x 4 + 0 x 2 + 1 x 1)
1101_(Z-M) = (- 1) x (4 + 1)
1101_(Z-M) = (- 1) x 5
1101_(Z-M) = - 5

1101_(U2) = 1 x (- 2³) + 1 x 2² + 0 x 2¹ + 1 x 2⁰
1101_(U2) = 1 x (- 8) + 1 x 4 + 0 x 2 + 1 x 1
1101_(U2) = - 8 + 4 + 1
1101_(U2) = - 3

Otrzymaliśmy za każdym razem inną wartość. Stąd wniosek, iż te same bity mogą być stosowane do kodowania różnych informacji. Dlatego bardzo istotne jest, aby odbiorca danych binarnych dokładnie wiedział, w jakim kontekście zostały one nadane, czyli znał ich format.

Zadanie 2

Czy kod U2 jest efektywny?

Zakres n bitowych liczb U2 obejmuje przedział liczbowy <-2^n-1, 2^n-1 -1>. Przedział ten ma długość:

2^n-1 - 1 - (- 2^n-1) + 1 = 2^n-1 - 1 + 2^n-1 + 1 = 2 x 2^n-1 = 2^n-1+1 = 2ⁿ

Z kolei n bitów tworzy 2ⁿ różnych słów kodowych. Z tych dwóch faktów wnioskujemy, iż w kodzie U2 każde słowo kodowe odpowiada jednej liczbie z zakresu. Dlatego kod ten jest kodem efektywnym, który w pełni wykorzystuje wszystkie dostępne słówka kodowe.

Zadanie 3

Znajdź wartość przeciwną do podanych liczb w kodzie U2:

NOT 01011101		NOT 11111111		NOT 00000000		NOT 01111110		NOT 11110000
10100010 + 00000001		00000000 + 00000001		11111111 + 00000001		10000001 + 00000001		00001111 + 00000001
10100011		00000001		1 00000000		10000010		00010000

Zadanie 4

Znajdź zapis w 8 bitowym kodzie U2 następujących wartości dziesiętnych:

-100  - obliczamy uzupełnienie do podstawy 2:
2⁸ - 100 = 256 - 100 = 156

156 : 2 =	78	i reszta c0 = 0
78 : 2 =	39	i reszta c1 = 0
39 : 2 =	19	i reszta c2 = 1
19 : 2 =	9	i reszta c3 = 1
9 : 2 =	4	i reszta c4 = 1
4 : 2 =	2	i reszta c5 = 0
2 : 2 =	1	i reszta c6 = 0
1 : 2 =	0	i reszta c7=1	, koniec

-100 = 10011100_(U2)

 -48  - obliczamy uzupełnienie do podstawy 2:
2⁸ - 48 = 256 - 48 = 208

208 : 2 =	104	i reszta c0 = 0
104 : 2 =	52	i reszta c1 = 0
52 : 2 =	26	i reszta c2 = 0
26 : 2 =	13	i reszta c3 = 0
13 : 2 =	6	i reszta c4 = 1
6 : 2 =	3	i reszta c5 = 0
3 : 2 =	1	i reszta c6 = 1
1 : 2 =	0	i reszta c7 = 1	, koniec

-48 = 11010000_(U2)

126 - liczba dodatnia, więc przetwarzamy ją bezpośrednio

126 : 2 =	63	i reszta c0 = 0
63 : 2 =	31	i reszta c1 = 1
31 : 2 =	15	i reszta c2 = 1
15 : 2 =	7	i reszta c3 = 1
7 : 2 =	3	i reszta c4 = 1
3 : 2 =	1	i reszta c5 = 1
1 : 2 =	0	i reszta c6 = 1	, koniec

126 = 01111110_(U2)

Zadanie 5

Oblicz wartość liczb stałoprzecinkowych w kodzie U2:

1101,111_(U2) = 1x(- 2³) + 1x2² + 0x2¹ + 1x2⁰ + 1x2^-1 + 1x2^-2 + 1x2^-3
1101,111_(U2) = 1x(- 8) + 1x4 + 0x2 + 1x1 + 1x¹/₂ + 1x¹/₄ + 1x¹/₈
1101,111_(U2) = - 8 + 4 + 1 + ¹/₂ + ¹/₄ + ¹/₈
1101,111_(U2) = - 8 + 5 ⁷/₈
1101,111_(U2) = - 2¹/₈

1,1_(U2) = 1 x (- 2⁰) + 1 x 2^-1
1,1_(U2) = 1 x (- 1) + 1 x ¹/₂
1,1_(U2) = - 1 + ¹/₂
1,1_(U2) = - ¹/₂

100,001_(U2) = 1 x (- 2²) + 0 x 2¹ + 0 x 2⁰ + 0 x 2^-1 + 0 x 2^-2 + 1 x 2^-3
100,001_(U2) = 1 x (- 4) + 0 x 2 + 0 x 1 + 0 x ¹/₂ + 0 x ¹/₄ + 1 x ¹/₈
100,001_(U2) = - 4 + ¹/₈
100,001_(U2) = - 3 ⁷/₈

KOD ZNAK MODUŁ

W tym rozdziale

Wartość liczb w kodzie Z-M
Zakres liczb w kodzie Z-M
Arytmetyka liczb Z-M
Zadania

Wartość liczb w kodzie Z-M.

System zapisu liczb ze znakiem znany pod nazwą znak-moduł (zapis Z-M) pochodzi w prostej linii od naszego własnego sposobu zapisu liczb ujemnych. Znak kodowany jest stanem najstarszego bitu:

• Bit znaku = 0 - liczba dodatnia

• Bit znaku = 1 - liczba ujemna

Reszta bitów przechowuje moduł, czyli wartość bezwzględną liczby zakodowaną w naturalnym kodzie binarnym (stosuje się również system stałoprzecinkowy Z-M). Wartość liczby obliczamy wg następującego wzoru:

W_Z-M = (1 - 2 x bit znaku) x W_M

bit znaku -	najstarszy bit zapisu liczby
WM -	wartość modułu, czyli pozostałych bitów traktowanych jako liczba w naturalnym kodzie binarnym (lub w kodzie stałoprzecinkowym).

Wyrażenie (1 - 2 x bit znaku) przyjmuje wartość 1 dla bitu znaku = 0 oraz -1 dla bitu znaku = 1. Wzór ten można również zapisać w postaci potęgowej:

W_Z-M = (-1)^{bit znaku} x W_M

Przykład

Załóżmy, iż operujemy 4 bitowymi liczbami w kodzie Z-M. Liczba (0 101)_(ZM) ma wartość:

(0 101)_(ZM) = (1 - 2 x 0) x (1 x 2² + 0 x 2¹ + 1 x 2⁰)
(0 101)_(ZM) = 1 x (1 x 4 + 1 x 1)
(0 101)_(ZM) = 1 x (4 + 1)
(0 101)_(ZM) = 1 x 5
(0 101)_(ZM) = 5

Natomiast liczba (1 101)_(ZM) ma wartość dziesiętną:

(1101)_(ZM) = (1 - 2 x 1) x (1 x 2² + 0 x 2¹ + 1 x 2⁰)
(1101)_(ZM) = -1 x (1 x 4 + 1 x 1)
(1101)_(ZM) = -1 x (4 + 1)
(1101)_(ZM) = -1 x 5
(1101)_(ZM) = -5

Czyli jest liczbą przeciwną do poprzedniej.

Zakres liczb w kodzie Z-M

Najmniejszą liczbą w kodzie Z-M jest liczba ujemna, której wszystkie bity mają wartość 1. Zgodnie z poznanym wzorem będzie to:

Z_min = (-1) x (2^n-1 - 1) = - 2^n-1 + 1

W potędze liczby dwa jest wykładnik n -1, ponieważ moduł liczby ma długość pomniejszoną o bit znaku, który interpretujemy inaczej.

Największą liczbą w kodzie Z-M będzie liczba dodatnia, której bit znaku ma wartość 0, a wszystkie bity modułu są ustawione na 1. Otrzymamy zatem:

Z_max = 2^n-1 - 1

I ostatecznie:

Z_Z-M = <Z_min, Z_max> = <- 2^n-1 + 1, 2^n-1 - 1>

Przykład

Obliczyć zakres 8 bitowych liczb w kodzie Z-M.

Przyjmujemy n = 8 i otrzymujemy bezpośrednio:

Z_(Z-M) = <- 2^n-1 + 1, 2^n-1 - 1>
Z_(Z-M) = <- 2^8-1 + 1, 2^8-1 - 1>
Z_(Z-M) = <- 2⁷ + 1, 2⁷ - 1>
Z_(Z-M) = <- 128 + 1, 128 - 1>
Z_(Z-M) = <- 127, 127>

Dla liczb stałoprzecinkowych w kodzie Z-M zbudowanych wg schematu:

bn-1	bn-2bn-3 ... b1b0	b-1b-2 ... b-m+1b-m
znak	n - 1 bitów części całkowitej	m bitów części ułamkowej

zakres wyraża się wzorem:

ZZ-M = <-2^n-1 + 1 -	2^m - 1	, 2^n-1 - 1 +	2^m - 1	>
			2^m			2^m

Przykład

Obliczyć zakres 8 bitowych liczb stałoprzecinkowych w kodzie Z-M o 3 cyfrach po przecinku.

Ustalamy:

m = 3,  n = 5

ZZ-M = <-2^n-1 + 1 -	2^m - 1	, 2^n-1 - 1 +	2^m - 1	>
			2^m			2^m

ZZ-M = <-2^5-1 + 1 -	2^3 - 1	, 2^5-1 - 1 +	2^3 - 1	>
			2^3			2^3

ZZ-M = <-2^4 + 1 -	2^3 - 1	, 2^4 - 1 +	2^3 - 1	>
			2^3			2^3

ZZ-M = <-16 + 1 -	8 - 1	, 16 - 1 +	8 - 1	>
			8			8

ZZ-M = <-15	7	, 15	7	>
			8			8

Arytmetyka liczb w kodzie Z-M

W kodzie Z-M działania arytmetyczne wykonuje się na modułach, czyli liczbach bez znaku. Sprawa się jednak komplikuje, ponieważ musimy uwzględniać znaki liczb, aby otrzymywać poprawne rezultaty. Problem możemy zauważyć już przy prostym dodawaniu liczby 3 i -3 w 4 bitowym kodzie Z-M:

0011 + 1011	=	3 + -3
1110			? -6

Otrzymaliśmy wynik -6 zamiast spodziewanego wyniku 0. Wynika stąd, iż znaki liczb wpływają na rodzaj wykonywanej nad nimi operacji arytmetycznej. W tym przypadku zamiast dodawania, powinniśmy zastosować odejmowanie, a wtedy:

0011 - 1011	=	3 + -3
1000			? -0

otrzymany wynik jest zgodny z oczekiwaniami. W operacjach arytmetycznych uczestniczą tylko moduły liczb. Poniżej prezentujemy reguły wykonywania operacji arytmetycznych w tym systemie z uwzględnieniem znaków przetwarzanych liczb.

Reguły dodawania liczb Z-M wynik = aZ-M + bZ-M
Znak aZ-M	Znak bZ-M	operacja	Znak wyniku
plus	plus	dodawanie modułów	plus
minus	minus	dodawanie modułów	minus
plus	minus	odejmowanie modułu mniejszego od modułu większego	znak większego modułu
minus	plus

3+2 0 011 + 0 010		-3 + -2 1 011 + 1 010		4 + -6 1 110 - 0 100		5 + -3 0 101 - 1 011
0 101 wynik 5				1 101 wynik -5			1 010 wynik -2		0 010 wynik 2

Reguły odejmowania liczb Z-M wynik = aZ-M - bZ-M
Znak aZ-M	Znak bZ-M	operacja	Znak wyniku
plus	plus	odejmowanie modułu mniejszego od modułu większego	Znak aZ-M, jeśli moduł ten jest większy od modułu bZ-M. Inaczej znak przeciwny.
minus	minus
plus	minus	dodawanie modułów	plus
minus	plus	dodawanie modułów	minus

3 - 2 0 011 - 0 010		-3 - -2 1 011 - 1 010		2 - -3 0 010 + 1 011		-5 - 2 1 101 + 0 010
0 001 wynik 1				1 001 wynik -1			0 101 wynik 5		1 111 wynik -7

Reguły mnożenia i dzielenia liczb Z-M wynik = aZ-M x bZ-M wynik = aZ-M : bZ-M
Znak aZ-M	Znak bZ-M	operacja	Znak wyniku
plus	plus	mnożenie lub dzielenie modułów	Jeśli znaki aZ-M i bZ-M są takie same, to plus. Inaczej minus
minus	minus
plus	minus
minus	plus

3 x 2 0 011 x 0 010		-3 x -2 1 011 x 1 010		3 x -2 0 011 + 1 010		-3 x 2 1 011 + 0 010
0 110 wynik 6				0 110 wynik 6			1 110 wynik -6		1 110 wynik -6

Jeśli wynikowy moduł nie może być przedstawiony za pomocą założonej liczby bitów, to mamy do czynienia z nadmiarem. Nadmiar najprościej można wykryć, jeśli nastąpiła pożyczka lub przeniesienie na pozycję bitu znaku.

4 + 5 0 100 x 0 101

1 001

Zadania

1. Oblicz wartość następujących liczb w kodzie Z-M:

(1 0011101)_(ZM), (0 1101100)_(ZM), (1 1110110)_(ZM)

2. Przedstaw w 8 bitowym kodzie Z-M liczby dziesiętne:

-45, 126, -99

3. Czy kod Z-M jest całkiem efektywny?

4. Ile bitów jest potrzebne na zapis w kodzie Z-M liczb z zakresu od <-26, 45> ?

5. Wykonaj następujące operacje arytmetyczne na liczbach w kodzie Z-M:

0110111 + 1101110		10001011 + 10111010		11101110 - 01011100		00001101 - 10011011

Kod znak-moduł

Zadanie 1

Oblicz wartość następujących liczb w kodzie Z-M:

(1 0011101)_(ZM) = (1 - 2 x 1) x (0x2⁶ + 0x2⁵ + 1x2⁴ + 1x2³ + 1x2² + 0x2¹ + 1x2⁰)
(1 0011101)_(ZM) = ( - 1) x (0x64 + 0x32 + 1x16 + 1x8 + 1x4 + 0x2 + 1x1)
(1 0011101)_(ZM) = ( - 1) x (16 + 8 + 4 +1)
(1 0011101)_(ZM) = ( - 1) x 29
(1 0011101)_(ZM) = - 29

(0 1101100)_(ZM) = (1 - 2 x 0) x (1x2⁶ + 1x2⁵ + 0x2⁴ + 1x2³ + 1x2² + 0x2¹ + 0x2⁰)
(0 1101100)_(ZM) = 1 x (1x64 + 1x32 + 0x16 + 1x8 + 1x4 + 0x2 + 0x1)
(0 1101100)_(ZM) = 1 x (64 + 32 + 8 + 4)
(0 1101100)_(ZM) = 1 x (108)
(0 1101100)_(ZM) = 108

(1 1110110)_(ZM) = (1 - 2 x 1) x (1x2⁶ + 1x2⁵ + 1x2⁴ + 0x2³ + 1x2² + 1x2¹ + 0x2⁰)
(1 1110110)_(ZM) = ( - 1) x (1x64 + 1x32 + 1x16 + 0x8 + 1x4 + 1x2 + 0x1)
(1 1110110)_(ZM) = ( - 1) x (64 + 32 + 16 + 4 + 2)
(1 1110110)_(ZM) = ( - 1) x 118
(1 1110110)_(ZM) = - 118

Zadanie 2

Przedstaw w 8 bitowym kodzie Z-M liczby dziesiętne:

-45
bit znaku = 1
moduł 7 bitowy = 45 = 0101101₍₂₎
-45 w kodzie Z-M = (1 0101101)_(Z-M)

126
bit znaku = 0
moduł 7 bitowy = 126 = 1111110₍₂₎
126 w kodzie Z-M = (0 1111110)_(Z-M)

-99
bit znaku = 1
moduł 7 bitowy = 99 = 1100011₍₂₎
-99 w kodzie Z-M = (1 1100011)_(Z-M)

Zadanie 3

Czy kod Z-M jest całkiem efektywny?

Nie. W kodzie Z-M liczba 0 może być wyrażona na dwa sposoby: moduł = 0 oraz bit znaku = 1 lub bit znaku = 0. Z tego powodu n bitów w kodzie Z-M może zakodować 2ⁿ - 1 różnych liczb, podczas gdy istnieje 2ⁿ różnych słówek kodowych. Dwa słówka kodowe kodują tą samą liczbę zero.

Zadanie 4

Ile bitów jest potrzebne na zapis w kodzie Z-M liczb z zakresu od <-26, 45> ?

W tym przypadku musimy dopasować zakres do większej na moduł liczby 45. Dlatego liczba bitów n musi spełniać nierówność:

2^n-1 - 1 ≥ 45

Nierówność ta jest spełniona dla n = 7:

2^7-1 - 1 = 2⁶ - 1 = 64 - 1 = 63 ≥ 45

Odpowiedź brzmi: potrzebne jest co najmniej 7 bitów.

Zadanie 5

Wykonaj następujące operacje arytmetyczne na liczbach w kodzie Z-M:

0 110111 + 1 101110		1 0001011 + 1 0111010		1 1101110 - 0 1011100		0 0001101 - 1 0011011
110111 - 101110				0001011 + 0111010			1101110 - 1011100		0001101 + 0011011
0 001001		1 1000101		1 0010010		0 0101000

LICZBY ZE ZNAKIEM

Poznaliśmy naturalny kod binarny pozwalający zakodować w postaci bitów dowolną liczbę naturalną oraz liczby dodatnie ułamkowe za pomocą notacji stałoprzecinkowej. Jednakże już proste działanie arytmetyczne odejmowania może prowadzić do uzyskania wyniku, który nie da się poprawnie przedstawić opisywanymi metodami. Chodzi o liczby ujemne. W systemie dziesiętnym poradziliśmy sobie w prosty sposób wprowadzając dodatkowy znak minus. W przypadku bitów nie możemy tak zrobić - mamy dostępne tylko cyfry 0 i 1. Nie istnieje żaden inny symbol bitowy. Wynika stąd, iż np. liczby -5 nie można binarnie po prostu zapisać jako -101₍₂₎, ponieważ symbol "-" nie będzie mógł być przedstawiony za pomocą stanów bitów. Jak zatem rozwiązano ten problem? Oczywiście ingerując w znaczenie bitów tworzących zapis liczby.

Liczby całkowite (tzn. naturalne, zero oraz ujemne) zapisywane są w systemie binarnym w ściśle określonym formacie, np. za pomocą 8, 16, 32, 64 bitów. Najstarszy bit pełni specjalną funkcję tzw. bitu znaku. Jeśli ma on wartość 0, to liczba jest dodatnia. Bit znaku o wartości 1 wskazuje liczbę ujemną. Taka jest podstawowa idea. Szczegóły omówimy dokładnie w dwóch kolejnych rozdziałach.

LICZBA ZE ZNAKIEM
bit znaku	bity wartości liczby

 

ZAPAMIĘTAJ Liczby całkowite zwane są w informatyce liczbami ze znakiem. Znak liczby przechowywany jest w najstarszym bicie liczby. Np. dla liczb 8 bitowych będzie to bit b7. Pozostałe bity przechowują wartość liczby.

OPERACJE LOGICZNE

W tym rozdziale

Algebra Boole'a
Zaprzeczenie logiczne, negacja, funkcja NOT
Suma logiczna, alternatywa, funkcja OR
Iloczyn logiczny, koniunkcja, funkcja AND
Suma symetryczna, suma modulo 2, funkcja XOR
Prawa Algebry Boole'a
Dowodzenie praw logicznych
Prawa DeMorgana
Operacje na bitach
Zadania

Algebra Boole'a

Operacje arytmetyczne operują na grupie bitów traktowanej jako całość, liczba. Operacje logiczne operują z kolei na pojedynczych bitach. Wszystkie współczesne komputery są maszynami logicznymi, w których wszelkie działania zrealizowano w formie operacji logicznych (nawet operacje arytmetyczne można sprowadzić do działań logicznych). Dlatego logika jest podstawą przetwarzania informacji.

Logika cyfrowa opiera się na tzw. Algebrze Boole'a, którą opracował i opublikował matematyk George Boole (1835-1882). Podstawą tej algebry są operacje logiczne wykonywane na dwóch wartościach - prawda i fałsz. Wynikiem każdej z operacji logicznych też może być tylko jedna z wartości prawda lub fałsz. Algebra Boole'a idealnie wręcz pasuje do bitów, które przyjmują dwa stany - 0 i 1.

Symbol Algebry Boole'a	Symbol bitowy
PRAWDA	1
FAŁSZ	0

Po takim określeniu znaczenia stanów bitów możemy w Algebrze Boole'a operować bitami w sensie wartości logicznych. Dzięki temu algebra ta da się zrealizować technicznie i wykorzystać w konstrukcji maszyn liczących - co też się szeroko czyni.

Działanie funkcji logicznych opisujemy za pomocą tabelek stanów. Parametry wejściowe oznacza się zwykle literkami A, B, C... Każdy z parametrów może przyjmować dowolną wartość logiczną (0 - fałsz, 1 - prawda) niezależnie od innych. Funkcja logiczna na podstawie stanu swoich argumentów określa stan wyjścia, które oznaczamy zwykle literką Y. Na wyjściu pojawia się wartość 0 lub 1. Stan wyjścia określamy dla każdej kombinacji stanów wejściowych.

Pewna funkcja logiczna
A	B	C	Y
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

W powyższej tabelce przedstawiliśmy pewną funkcję logiczną. W kolumnach A, B i C umieszczone są wszystkie możliwe kombinacje wartości logicznych, które mogą pojawić się jako argumenty wejściowe. W kolumnie Y określony jest stan wyjścia (wartość funkcji) dla każdej kombinacji stanów wejściowych. Np. dla A = 0, B = 1 i C = 1 odczytujemy z tabelki Y = 1, czyli funkcja przyjmie wartość logiczną prawdy.

Zaprzeczenie logiczne, negacja, funkcja NOT

Zaprzeczenie logiczne jest najprostszą funkcją logiczną. Funkcja ta daje na wyjściu stan przeciwny do swojego wejścia. Tabelka stanów jest następująca:

Y = NOT A
A	Y
0	1
1	0

Odpowiednikiem tej funkcji w arytmetyce jest negacja znaku (zmiana znaku liczby na przeciwny). Operacja negacji logicznej zastosowana do grupy bitów zmienia ich stan na przeciwny. Oto przykład:

NOT 0010111101101010

1101000010010101

Suma logiczna, alternatywa, funkcja OR

Suma logiczna jest funkcją dwuargumentową, tzn. jej wynik Y zależy od stanu dwóch argumentów A i B. Wynik przyjmuje stan 1, jeśli dowolny z argumentów ma również stan 1. Stan 0 występuje na wyjściu tylko wtedy, gdy wszystkie argumenty mają również stan 0.

Y = A OR B
A	B	Y
0	0	0
0	1	1
1	0	1
1	1	1

Odpowiednikiem tej funkcji w arytmetyce jest suma. Zastosowanie sumy logicznej do dwóch słów binarnych powoduje odpowiednią zmianę bitów wyniku zgodnie z podaną tabelką. Oto przykład:

0010111101101010 OR 1010101010001111

1010111111101111

Iloczyn logiczny, koniunkcja, funkcja AND

Kolejną funkcją dwuargumentową jest iloczyn logiczny. Wynik Y przyjmuje wartość 1, jeśli wszystkie argumenty również mają wartość 1, a 0 w każdym innym przypadku. Oto tabelka:

Y = A AND B
A	B	Y
0	0	0
0	1	0
1	0	0
1	1	1

Odpowiednikiem arytmetycznym jest mnożenie. Zastosowanie iloczynu logicznego do dwóch słów binarnych powoduje odpowiednią zmianę bitów wyniku zgodnie z podaną tabelką. Oto przykład:

0010111101101010 AND 1010101010001111

0010101000001010

Suma symetryczna, suma modulo dwa, funkcja XOR

Suma symetryczna nie jest funkcją podstawową. Jej wzór logiczny przyjmuje postać:

A XOR B = ((NOT A) AND B) OR (A AND (NOT B))

Dziwny, nieprawdaż. Dużo prościej wygląda tabelka stanów:

Y = A XOR B
A	B	Y
0	0	0
0	1	1
1	0	1
1	1	0

Z tabelki tej wynika prosta zasada - funkcja sumy symetrycznej przyjmuje wartość 0, gdy oba argumenty są sobie równe, a 1 w przeciwnym przypadku. Suma symetryczna ma olbrzymie zastosowanie w technice cyfrowej, dlatego prezentujemy ją w tym opracowaniu.

Dokładnym odpowiednikiem arytmetycznym tej funkcji jest suma modulo 2 (tzn. suma, po wykonaniu której bierze się resztę z dzielenia wyniku przez 2). Zastosowanie sumy symetrycznej do dwóch słów binarnych powoduje odpowiednią zmianę bitów wyniku zgodnie z podaną tabelką. Oto przykład:

0010111101101010 XOR 1010101010001111

1000010111100101

Jeśli jeden z argumentów będzie miał wszystkie bity ustawione na 1, to wykonanie operacji XOR da w wyniku negację bitów drugiego argumentu:

0010111101101010 XOR 1111111111111111

1101000010010101

Prawa Algebry Boole'a

Zanim przedstawimy prawa Algebry Logiki Boole'a, ustalmy praktyczne symbole operacji logicznych, które będziemy stosować w wyrażeniach:

Symbole funkcji logicznych
Funkcja	Symbol	Przykład
Negacja NOT		y = a
Suma OR		y = a  b
Iloczyn AND		y = a  b
Suma symetryczna XOR		y = a  b

Prawa trywialne (oczywiste) Algebry Logiki Boole'a można wyprowadzić bezpośrednio z tabelek stanów dla poszczególnych funkcji logicznych. Oto one:

Prawa trywialne Algebry Logiki Boole'a
Lp.	Prawo	Opis
I	a  0 = 0	Iloczyn logiczny z wartością 0 daje w wyniku zawsze 0
II	a  1 = a	Iloczyn logiczny przez 1 nie zmienia wyniku operacji
III	a  0 = a	Dodanie logiczne zera nie zmienia wyniku operacji
IV	a  1 = 1	Suma logiczna z wartością 1 daje zawsze wynik 1
V	a  a = a	Iloczyn logiczny argumentu przez samego siebie daje w wyniku ten sam argument
VI	a  a = a	Suma logiczna argumentu z samym sobą daje w wyniku ten sam argument
VII	a  a = 0	Iloczyn argumentu z jego zaprzeczeniem daje zawsze wartość logiczną 0.
VIII	a  a = 1	Suma argumentu z jego zaprzeczeniem daje zawsze wartość logiczną 1

Prawa nie trywialne muszą być wyprowadzane z podstawowych własności funkcji logicznych za pomocą odpowiednich przekształceń logicznych. Poniżej podajemy kilka z nich:

Lp.	Prawa Algebry Boole'a
I	a = a
II	a  b = b  a
III	a  b = b  a
IV	a  (b  c) = a  b  a  c
V	a  (b  c) = (a  b)  (a  c)
VI	a  (b  c) = (a  b)  c
VII	a  (b  c) = (a  b)  c
VIII	a  a  b = a
IX	a (a  b) = a
X	a  (a  b) = a  b
XI	a  a  b = a  b
XII	a  a  b = a  b
XIII	a  a  b = a  b

Dla przykładu udowodnimy prawo VIII - a  a  b = a. W tym celu rozważmy dwa przypadki:

a = 0, otrzymujemy 0  0  b = 0  0 = 0, czyli wynik równy wartości a

a = 1, otrzymujemy 1  1  b = 1  b = 1, wynik znów równy wartości a.

Wnioskujemy zatem, iż a  a  b = a.

Dowodzenie praw logicznych

Prawa logiczne w Algebrze Boole'a możemy dowodzić na dwa sposoby:

1. Przy pomocy odpowiednich przekształceń logicznych

2. Za pomocą tabelki stanów logicznych.

Udowodnimy pierwszym sposobem prawo XIII - a  a  b = a  b. Wykażemy, iż z lewej strony wynika prawa strona równania.

Zastosowane prawo logiczne	Przekształcenie wyrażenia logicznego
Wyrażenie wyjściowe	a  a  b
a  0 = a a  a = 0	a  a  b  a  a
a  (b  c) = a  b  a  c	a  a  (b  ~a)
a  (b  c) = (a  b)  (a  c)	(~a  a)  (~a  ~b  ~a)
a  b = b  a a  a = 1	1  (~a  ~b  ~a)
a  b = b  a a  1 = a	~a  ~b  ~a
a  b = b  a a  a = a	~a  ~b

Jak zauważyliście, sposób pierwszy nie jest najprostszy. Wymaga dobrej znajomości praw logicznych. Dlatego częściej stosujemy sposób drugi. w którym tworzymy tabelkę wartości wszystkich podwyrażeń, na podstawie których wyprowadzamy wynik.

Tabelka stanów logicznych
a	b	~a	~b	a  ~b a  d	a  a  b c  e	~a  ~b c  d
a	b	c	d	e	y1	y2
0	0	1	1	0	1	1
0	1	1	0	0	1	1
1	0	0	1	1	1	1
1	1	0	0	0	0	0

W kolumnach y₁ oraz y₂ otrzymaliśmy te same stany. Kolumna y₁ zawiera wynik logiczny wyrażenia po lewej stronie, a y₂ wyrażenia po prawej stronie. Identyczność tych kolumn dowodzi prawdziwości równania logicznego.

Prawa DeMorgana

W wielu przekształceniach wyrażeń logicznych korzysta się często z tzw. praw DeMorgana (wprowadził je do logiki matematyk Augustus DeMorgan, 1806 - 1876). Prawa te odnoszą się do zaprzeczenia iloczynu i sumy logicznej. Brzmią one następująco:

ZAPAMIĘTAJ I Prawo DeMorgana: Zaprzeczenie sumy logicznej jest równe iloczynowi logicznemu zaprzeczeń ~(a  b) = ~a  ~b II Prawo DeMorgana Zaprzeczenie iloczynu logicznego jest równe sumie logicznej zaprzeczeń. ~(a  b) = ~a  ~b

Prawa te udowodnimy za pomocą tabelki stanów logicznych:

I Prawo DeMorgana ~(a  b) = ~a  ~b
a	b	a  b	~(a  b) ~c	~a	~b	~a  ~b d  e
a	b	c	y1	d	e	y2
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0
II Prawo DeMorgana ~(a  b) = ~a  ~b
a	b	a  b	~(a  b) ~c	~a	~b	~a  ~b d  e
a	b	c	y1	d	e	y2
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Operacje na bitach

Przy operacjach na bitach stosuje się specjalne słowo bitowe nazywane maską. Maska posiada odpowiednio ustawione lub wyzerowane bity na odpowiednich miejscach. W zależności od zastosowanej funkcji logicznej będą aktywne bity maski o wartości 1 lub 0.

Zerowanie bitu

Przygotowujemy maskę, w której wszystkie bity mają wartość 1, za wyjątkiem bitu na pozycji, która w słowie przetwarzanym ma zostać wyzerowana. Bit ten musi być w stanie 0. Następnie wykonujemy nad słówkiem binarnym i maską operację iloczynu logicznego. Wynikowe słowo binarne zachowuje stan wszystkich bitów słowa kodowego, z wyjątkiem bitu na pozycji wyzerowanej w masce, który zostanie ustawiony na 0.

Przykład:

Zerujemy bit b₃ w słowie kodowym zbudowanym z 8 bitów b₇b₆b₅b₄b₃b₂b₁b₀ o wartości 11011111.  W tym celu przygotowujemy maskę, w której wszystkie bity mają stan 1 za wyjątkiem bitu na pozycji b₃:

maska = 11110111

Teraz wykonujemy operację AND ze słówkiem kodowym oraz maską:

11011111 AND 11110111

10110111

W efekcie bit na pozycji b₃ zostaje wyzerowany. Pozycję tą oznaczyliśmy kolorem czerwonym. W identyczny sposób można wyzerować dowolną ilość bitów ustawiając ich pozycje w masce na 0.

Ustawianie bitu

Przygotowujemy maskę, w której wszystkie bity mają wartość 0, za wyjątkiem bitu na pozycji, która w słowie przetwarzanym ma zostać ustawiona na 1. Bit ten musi być w stanie 1. Następnie wykonujemy nad słówkiem binarnym i maską operację sumy logicznej. Wynikowe słowo binarne zachowuje stan wszystkich bitów słowa kodowego, z wyjątkiem bitu na pozycji ustawionej na 1 w masce.

Przykład:

Ustawiamy na 1 bit b₃ w słowie kodowym zbudowanym z 8 bitów b₇b₆b₅b₄b₃b₂b₁b₀ o wartości 11000011.  W tym celu przygotowujemy maskę, w której wszystkie bity mają stan 0 za wyjątkiem bitu na pozycji b₃:

maska = 00001000

Teraz wykonujemy operację OR ze słówkiem kodowym oraz maską:

11000011 OR 00001000

11001011

W efekcie bit na pozycji b₃ zostaje ustawiony na 1. Pozycję tą oznaczyliśmy kolorem czerwonym. W identyczny sposób można ustawić dowolną ilość bitów.

Zmiana stanu bitu na przeciwny

Przygotowujemy maskę, w której wszystkie bity mają wartość 0, za wyjątkiem bitu, który w słowie przetwarzanym ma zostać zmieniony na przeciwny. Bit ten musi być w stanie 1. Następnie wykonujemy nad słówkiem binarnym i maską operację sumy symetrycznej. Wynikowe słowo binarne zachowuje stan wszystkich bitów słowa kodowego, z wyjątkiem bitu ustawionego na 1 w masce.

Przykład:

Ustawiamy na 1 bit b₃ w słowie kodowym zbudowanym z 8 bitów b₇b₆b₅b₄b₃b₂b₁b₀ o wartości 11001111.  W tym celu przygotowujemy maskę, w której wszystkie bity mają stan 0 za wyjątkiem bitu na pozycji b₃:

maska = 00001000

Teraz wykonujemy operację XOR ze słówkiem kodowym oraz maską:

11001111 XOR 00001000

11000011

W efekcie bit na pozycji b₃ zmienia swój stan na przeciwny. Pozycję tą oznaczyliśmy kolorem czerwonym. W identyczny sposób można zmienić stan dowolnej liczby bitów.

Zadania

1. Wykonaj następujące operacje logiczne:

NOT 0101110101		1111101101 OR 0011111011		1101011010 AND 1110110011		1001110010 XOR 0111011111

2.. Udowodnij za pomocą tabelki stanów następujące prawa logiczne:

a  (b  c) = (a  b)  (a  c)
a  (b  c) = (a  b)  c

3. Jaką funkcję logiczną przedstawia poniższa tabelka?

Y = ?
A	B	Y
0	0	1
0	1	0
1	0	1
1	1	1

4. Mamy dane dwa słówka bitowe w₁ = 11010011 oraz w₂ = 01110101. Oba zawierają po 8 bitów. Jakie operacje logiczne należy przeprowadzić, aby uzyskać słowo bitowe, którego młodsze 4 bity pochodzą z w₁, a 4 starsze bity pochodzą z w₂?

5. Jak sensownie sprawdzić stan określonego bitu w słowie binarnym, przy założeniu, iż mamy możliwość zbadania, czy wynik operacji jest zerem lub nie?

6. Ile jest konieczne podstawowych funkcji logicznych do wyliczenia wartości logicznej dowolnych wyrażeń?

Zadanie 1

Wykonaj następujące operacje logiczne:

NOT 0101110101		1111101101 OR 0011111011		1101011010 AND 1110110011		1001110010 XOR 0111011111
1010001010		1111111111		1100010010		1110101101

Zadanie 2

Udowodnij za pomocą tabelki stanów następujące prawa logiczne:

a  (b  c) = (a  b)  (a  c)
a	b	c	b  c	a  (b  c) a  d	a  b	a  c	(a  b)  (a  c) e  f
a	b	c	d	y1	e	f	y2
0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	1	1	1	1

 

a  (b  c) = (a  b)  c
a	b	c	b  c	a  (b  c) a  d	a  b	(a  b)  c e  c
a	b	c	d	y1	e	y2
0	0	0	0	0	0	0
0	0	1	1	1	0	1
0	1	0	1	1	1	1
0	1	1	1	1	1	1
1	0	0	0	1	1	1
1	0	1	1	1	1	1
1	1	0	1	1	1	1
1	1	1	1	1	1	1

Zadanie 3

Jaką funkcję logiczną przedstawia poniższa tabelka?

Y = ?
A	B	Y
0	0	1
0	1	0
1	0	1
1	1	1

Funkcja przyjmuje stan 1 dla A = 0 i B = 0 oraz dla A = 1. Wobec tego jej wzór jest następujący:

Y = (~A  ~B)  A

Zadanie 4

Mamy dane dwa słówka bitowe w₁ = 11010011 oraz w₂ = 01110101. Oba zawierają po 8 bitów. Jakie operacje logiczne należy przeprowadzić, aby uzyskać słowo bitowe, którego młodsze 4 bity pochodzą z w₁, a 4 starsze bity pochodzą z w₂?

W w₁ należy wyzerować starsze 4 bity od b₄ do b₇, w w₂ należy wyzerować młodsze 4 bity od b₀ do b₃, a następnie połączyć w₁ z w₂ za pomocą sumy logicznej:

w1 = 11010011 AND 00001111

00000011

w2 = 01110101 AND 11110000

01110000

00000011  OR  01110000

01110011

Zadanie 5

Jak sensownie sprawdzić stan określonego bitu w słowie binarnym, przy założeniu, iż mamy możliwość zbadania, czy wynik operacji jest zerem lub nie?

Tworzymy maskę z ustawionym na 1 bitem na badanej pozycji. Następnie wykonujemy operację iloczynu logicznego badanego słowa z maską. W wyniku zostaną wyzerowane wszystkie bity za wyjątkiem bitu, na którego pozycji w masce jest ustawiony bit na 1. Stan tego bitu pozostaje niezmieniony. Teraz wystarczy sprawdzić, czy całe słowo jest zerem - badany bit ma stan 0, lub jest różne od zera - badany bit ma stan 1. Sprawdźmy tą metodą najstarszy bit 4 bitowych słówek 0101 oraz 1110:

0101 AND 1000

0000

1110 AND 1000

1000

W pierwszym przypadku otrzymaliśmy wynik 0, badany bit miał stan 0. W drugim przypadku otrzymaliśmy wynik 8, czyli różny od zera - badany bit miał stan 1.

Zadanie 6

Ile jest konieczne podstawowych funkcji logicznych do wyliczenia wartości logicznej dowolnych wyrażeń?

Dzięki prawom DeMorgana potrzebna jest tylko jedna z par funkcji logicznych:

• zaprzeczenie - suma logiczna

• zaprzeczenie - iloczyn logiczny

Mając do dyspozycji zaprzeczenie i sumę logiczną można utworzyć iloczyn logiczny następująco:

a  b = ~~(a  b) = ~(~a  ~b)

Iloczyn logiczny uzyskujemy jako zaprzeczenie sumy logicznej zaprzeczeń.

Podobnie mając do dyspozycji jedynie zaprzeczenie i iloczyn logiczny można utworzyć sumę logiczną w sposób następujący:

a  b = ~~(a  b) = ~(~a  ~b)

Sumę logiczną uzyskujemy jako zaprzeczenie iloczynu logicznego zaprzeczeń.OPERACJE ARYTMETYCZNE

W tym rozdziale

Dodawanie dwójkowe
Odejmowanie dwójkowe
Mnożenie dwójkowe
Dzielenie dwójkowe
Zadania

W poprzednich rozdziałach omówiliśmy dokładnie sposoby zapisu liczb binarnych naturalnych oraz stałoprzecinkowych. Jeśli przyswoiliście sobie podane tam informacje, to bez trudu potraficie wyrażać dowolne wartości dziesiętne w systemie dwójkowym i na odwrót. Teraz nadszedł czas na praktyczne zastosowanie tych liczb w rachunkach. Poznanie metod wykonywania działań w systemie binarnym pozwoli nam lepiej zrozumieć różne ograniczenia komputerów oraz zasady ich pracy.

Dodawanie dwójkowe

Na pewno pamiętacie horror uczenia się na pamięć tabliczki dodawania w systemie dziesiętnym. Mamy tutaj dziesięć cyfr, zatem należy nauczyć się 100 sum częściowych każdej cyfry z każdą. W systemie dwójkowym cyfr jest tylko dwie. Tabliczka dodawania jest szczególnie prosta:

Tabliczka dodawania binarnego

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0 i 1 dalej

Ostatni wynik należy rozumieć następująco: 1 + 1 daje 0 w bieżącej kolumnie i przeniesienie (ang. carry) jedynki do następnej kolumny. Przeniesienie dodawane jest do cyfry w następnej kolumnie - zupełnie tak samo postępujemy w systemie dziesiętnym, gdy wynik sumowania cyfr przekracza dziewięć. Wykonajmy kilka prostych dodawań:

1101 + 0010	=	13 + 2
1111			15

0101 + 0111	=	5 + 7
1100			12

1001 + 0011	=	9 + 3
1100			12

Jeśli liczby binarne są zapisywane ze stałym formatem (np. 8 bitów), to może się zdarzyć, iż wynik dodawania nie zmieści się w dozwolonym zakresie liczb. Sytuacja taka nazywa się nadmiarem (ang. overflow).

Przykład

Załóżmy, iż operujemy arytmetyką liczb 4 bitowych. Liczby takie posiadają zakres <0, 15>. Dodajmy dwie proste liczby 4 bitowe:

1010 + 0110	=	10 + 6
10000			16

Wynik dodawania jest liczbą 5 bitową i nie mieści się w 4 bitach. Jeśli ograniczymy go do 4 bitów, to otrzymamy wartość 0. Wystąpił nadmiar. Wynik został obcięty do reszty z dzielenia przez 16.

ZAPAMIĘTAJ Nadmiar jest przekroczeniem górnej granicy zakresu liczb. Dla liczb naturalnych mamy do czynienia z nadmiarem, gdy pojawi się przeniesienie poza najstarszą pozycję liczby.

W identyczny sposób dodajemy liczby stałoprzecinkowe. Należy tylko pamiętać o ustawieniu przecinków w jednej kolumnie i dopisaniu w razie konieczności zer na początku części całkowitych i na końcu części ułamkowych:

0011,011 + 0111,110	=	3,375 + 7,750
1011,001			11,125

Odejmowanie dwójkowe

Tabliczka odejmowania jest równie prosta jak w przypadku dodawania:

Tabliczka odejmowania binarnego

0 - 0 = 0

1 - 0 = 1

1 - 1 = 0

0 - 1 = 1 i pożyczka

Ostatni zapis należy rozumieć jako: 0 - 1 daje w bieżącej kolumnie 1 i pożyczkę (ang. borrow) do następnej kolumny. Pożyczka jest odejmowana od cyfr w następnej kolumnie. Dla przykładu wykonajmy kilka odejmowań:

1111 - 0111	=	15 -  7
1000			8

1011 - 0101	=	11 - 5
0110			6

1101 - 0011	=	13 - 3
1010			10

Przy odejmowaniu wynik może być liczbą ujemną. Ponieważ omówione systemy zapisu liczb binarnych nie uwzględniają jeszcze liczb ujemnych, to w takim przypadku wystąpi sytuacja zwana niedomiarem (ang. underflow).

Przykład

Załóżmy, iż wykonujemy operację odejmowania na liczbach binarnych, których rozmiar jest ograniczony do 4 bitów. Zakres takich liczb jest równy <0, 15>.

0011 - 0100	=	3 -  4
...111111			-1

Liczba -1 leży poza zakresem liczb dla kodu 4 bitowego. Dlatego nie może w tym kodzie być przedstawiona prawidłowo i otrzymujemy wynik równy 15. Zwróćcie uwagę, iż wiodące jedynki powstają w tym przypadku w nieskończoność, co zaznaczyliśmy trzema kropeczkami na początku wyniku odejmowania.

ZAPAMIĘTAJ Niedomiar jest przekroczeniem dolnej granicy zakresu liczb. Dla liczb naturalnych mamy do czynienia z niedomiarem, gdy pojawi się pożyczka poza najstarszą pozycję liczby.

Mnożenie dwójkowe

Bez wątpienia każdy początkujący informatyk musi polubić tabliczkę mnożenia dla liczb dwójkowych. Nauczenie się jej nie potrwa ani minuty. Oto ona:

Tabliczka mnożenia binarnego

0 x 0 = 0

1 x 0 = 0

0 x 1 = 0

1 x 1 = 1

Mnożenie binarne wykonujemy identycznie jak w systemie dziesiętnym - przemnażamy mnożną przez każdą cyfrę mnożnika zapisując wyniki tego mnożenia odpowiednio przesunięte. Następnie wykonujemy dodawanie zgodnie z opisanym wcześniej schematem:

0011 x   0101	=	3 x  5
0011 0000  + 0011			...
001111		15

W systemie dwójkowym wynik mnożenia jest równy 1 tylko wtedy, gdy obie mnożone cyfry mają wartość 1. W każdym innym przypadku otrzymujemy wartość 0. Pozwala to znacznie uprościć schemat mnożenia. Mnożną umieszczamy tylko w tych kolumnach, w których w mnożniku występują cyfry 1. Pozostałe kolumny pomijamy:

1011 x    1101	=	11 x  13
1011 1011   + 1011			33 + 11
10001111		143

Uwagi na temat nadmiaru odnoszą się również do mnożenia liczb binarnych.

Mnożenie liczb stałopozycyjnych wykonujemy w identyczny sposób, lecz musimy pamiętać, aby przy wyniku oddzielić odpowiednią ilość cyfr ułamkowych przecinkiem - ilość ta jest sumą liczby miejsc po przecinku mnożnej i mnożnika - tak samo jak w systemie dziesiętnym.

10,1 x   11,01	=	2,5 x  3,25
101 101   +  101			125 50  +  75
1000001 1000,001		8125 8,125

Dzielenie dwójkowe

Dzielenie binarne jest najbardziej skomplikowaną operacją arytmetyczną z dotychczas opisywanych. Wymyślono wiele algorytmów efektywnego dzielenia, ale dla potrzeb tego opracowania wystarczy znany wam algorytm szkolny, który polega na cyklicznym odejmowaniu odpowiednio przesuniętego dzielnika od dzielnej. W systemie dwójkowym jest to szczególnie proste, ponieważ dzielnika nie musimy mnożyć, Oto odpowiedni przykład:

Podzielimy liczbę 1110₍₂₎ przez 11₍₃₎ (14 : 3).

1. Przesuwamy w lewo dzielnik, aż zrówna się jego najstarszy, niezerowy bit z najstarszym, niezerowym bitem dzielnej. Nad dzielną rysujemy kreseczkę:

1110 - dzielna
11   - przesunięty dzielnik.

2. Jeśli dzielnik da się odjąć od dzielnej bez niedomiaru, to nad kreską w kolumnie najmłodszego bitu dzielnika wpisujemy 1 i wykonujemy odejmowanie:

 1
1110 - dzielna
11  - przesunięty dzielnik
0010 - różnica dzielnej i przesuniętego dzielnika

3. Dzielnik przesuwamy o jeden bit w prawo i próbujemy tego samego z otrzymaną różnicą. Jeśli odejmowanie jest możliwe, to nad kreską w następnej kolumnie dopisujemy 1, odejmujemy dzielnik od różnicy, przesuwamy go o 1 bit w prawo i kontynuujemy. Jeśli odejmowanie nie jest możliwe, to dopisujemy nad kreską 0, przesuwamy dzielnik o 1 bit w prawo i kontynuujemy.

   100 - wynik dzielenia
  1110 - dzielna
- 11   - dzielnik
  0010 - dzielna po odejmowaniu przesuniętego dzielnika
-  11  - dzielnika nie można odjąć
  0010 - dzielna
-   11 - dzielnika nie można odjąć, koniec
  0010 - reszta z dzielenia

4. Operacje te wykonujemy dotąd, aż dzielnik osiągnie swoją pierwotną wartość. Pozostała dzielna jest resztą z dzielenia

W naszym przykładzie otrzymaliśmy wynik 100₍₂₎ i resztę 10₍₂₎ (4 i 2). Jest to wynik poprawny, gdyż 3 mieści się w 14 cztery razy i pozostaje reszta 2.

Dla wprawki podzielmy liczbę 110101101₍₂₎ przez 111₍₂₎ (429 przez 7):

  0111101 - wynik dzielenia
110101101 : 111
111       - nie da się odjąć, nad kreską 0
110101101
 111      - da się odjąć, nad kreską 1
 11001101
  111     - da się odjąć, nad kreską 1
  1011101
   111    - da się odjąć, nad kreską 1
   100101
    111   - da się odjąć, nad kreską 1
     1001
     111  - nie da się odjąć, nad kreską 0
     1001
      111 - da się odjąć, nad kreską 1, koniec
       10 - reszta z dzielenia

110101101₍₂₎ : 111₍₂₎ = 111101₍₂₎ i reszta 10₍₂₎ (429 : 7 = 61 i reszta 2).

Zadania

1. Dodaj dwie liczby ósemkowe 743₍₈₎ i 212₍₈₎.

2. Wykonaj następujące dodawania binarne:

11010011101 +      10101111

11001111010 + 11111100010

111000111 + 110011001

3. Wykonaj odejmowania binarne:

11100111111 -      10101100

11011111010 -       1100111

111110111 -       11001

4. Wykonaj mnożenie binarne:

111100 x    1011

11010 x   1011

11101 x 11001

5. Wykonaj dzielenie binarne:

11010011101 : 1110

11011111011 : 110

111010111 : 101

Operacje arytmetyczne

Zadanie 1

Dodaj dwie liczby ósemkowe 743₍₈₎ i 212₍₈₎.

Liczby ósemkowe zamieniamy na ich odpowiedniki w systemie dwójkowym:

743₍₈₎ = 111100011₍₂₎ ,  212₍₈₎ = 010001010₍₂₎

Wykonujemy dodawanie w systemie dwójkowym:

   111100011
+  010001010
  1001101101

Wynik zamieniamy z powrotem na system ósemkowy:

001001101101₍₂₎ = 1155₍₈₎, i ostatecznie

743₍₈₎ + 212₍₈₎ = 1155₍₅₎

Zadanie 2

Wykonaj następujące dodawania binarne:

11010011101 +      10101111 11101001100

11001111010 + 11111100010 111001011100

111000111 + 110011001 1101100000

Zadanie 3

Wykonaj odejmowania binarne:

11100111111 -      10101100 11010010011

11011111010 -       1100111 11010010011

111110111 -       11001 111011110

Zadanie 4

Wykonaj mnożenie binarne:

111100 x      1011 111100 111100  + 111100    1010010100

11010 x     1011 11010 11010  + 11010    100011110

11101 x     11001 11101 11101    + 11101     1011010101

Zadanie 5

Wykonaj dzielenie binarne:

01111000   11010011101 : 1110 - 1110          11010011101 -  1110          1100011101 -   1110          101011101 -    1110           1111101 -     1110             1101 -      1110            1101 -       1110           1101 -        1110          1101 - reszta

100101001   11011111011 : 110 - 110              11111011 -  110             11111011 -   110            11111011 -    110             111011 -     110            111011 -      110             1011 -       110            1011 -        110           1011 -         110           101 - reszta

1011110   111010111 : 101 - 101          10010111 -  101         10010111 -   101         1000111 -    101          11111 -     101          1011 -      101            1 -       101           1 - reszta

LICZBY ZMIENNOPRZECINKOWE

W tym rozdziale

Zapis zmiennoprzecinkowy
Niejednoznaczność zapisu zmiennoprzecinkowego
Precyzja liczb zmiennoprzecinkowych
Dwójkowy zapis zmiennoprzecinkowy
Zakres dwójkowych liczb zmiennoprzecinkowych
Zadania

Zapis zmiennoprzecinkowy

W obliczeniach inżynierskich, matematycznych czy naukowych operuje się wielkościami zarówno bardzo dużymi, jak i bardzo małymi. Zapis takich liczb w systemie binarnym byłby mało efektywny z uwagi na wymaganą ilość bitów. Dzisiaj zapewne można by się z tym pogodzić, ale większość systemów liczbowych dla maszyn cyfrowych opracowano w czasach, gdy pamięć stanowiła poważny procent kosztu całej maszyny i programiści dbali o jej efektywne wykorzystywanie. Z kolei liczby o dużej ilości bitów wymagają więcej czasu na przetworzenie lub sprzętu o większej mocy obliczeniowej. Wobec tego szukano sposobu przedstawiania liczb o dużym zakresie przy pomocy niewielkiej liczby bitów. Rozwiązaniem okazał się zapis zmiennoprzecinkowy.

Na pewno spotkaliście już dziesiętny zapis zmiennoprzecinkowy. Chętnie stosują go fizycy dla wielkości bardzo dużych (lub bardzo małych). Na przykład moglibyśmy zapisać, że rok świetlny to 9454254955488000 [m]. Liczbę taką źle się czyta. Jeśli nie jest nam potrzebna wielka dokładność, to możemy zapisać, iż:

rok świetlny  9,45 x 10¹⁵ [m]

Dużą liczbę zapisaliśmy przy pomocy trzech mniejszych liczb:

Mantysy - 9,45
Podstawy - 10
Wykładnika 15

Ponieważ podstawa jest dla danego systemu stała i znana, więc nie musimy jej zapamiętywać wraz z liczbą. Wystarczy informacja o mantysie oraz wykładniku. Niektóre kalkulatory naukowe w ten właśnie sposób prezentują duże liczby:

 9,45 15

Sposób ten możemy prosto uogólnić na dowolny, pozycyjny system liczenia. Wzór obliczania wartości liczby zmiennoprzecinkowej jest zawsze ten sam:

W_FP = m x p^w

m - mantysa zapisana w systemie o podstawie p
p - podstawa danego systemu pozycyjnego
w - wykładnik zapisany w systemie o podstawie p.

Obliczmy dla przykładu wartość liczby zmiennoprzecinkowej zapisanej w systemie czwórkowym: (3,21 x 10¹²)₍₄₎. Przy obliczaniu tego typu wartości musimy pamiętać, iż wszystkie trzy elementy są zapisane w systemie o podstawie p (u nas równej 4). Obliczamy:

m = 3,21₍₄₎
m = 3 x 4⁰ + 2 x 4^-1 + 1 x 4^-2
m = 3 x 1 + 2 x ¹/₄ + 1 x ¹/₁₆
m = 3 + ²/₄ + ¹/₁₆
m = 3⁹/₁₆

p = 10₍₄₎
p = 1 x 4¹ + 0 x 4⁰
p = 1 x 4 + 0 x 1
p = 4

w = 12₍₄₎
w = 1 x 4¹ + 2 x 4⁰
w = 1 x 4 + 2 x 1
w = 4 + 2
w = 6

(3,21 x 10¹²)₍₄₎ = 3⁹/₁₆ x 4⁶ = 14592

ZAPAMIĘTAJ Aby obliczyć wartość liczby zmiennoprzecinkowej zapisanej w dowolnym systemie pozycyjnym o podstawie p, oblicz dziesiętną wartość mantysy m oraz wykładnika w i podstaw wyniki do wzoru: WFP = m x p^w

Mantysa jest liczbą stałoprzecinkową ze znakiem, która posiada ustaloną liczbę cyfr całkowitych oraz ułamkowych. Wykładnik jest zawsze liczbą całkowitą.

Niejednoznaczność zapisu zmiennoprzecinkowego

Pierwszą, charakterystyczną cechą liczb zmiennoprzecinkowych jest niejednoznaczność zapisu wartości liczby. Np.

9,45 x 10¹⁵ = 94,5 x 10¹⁴ = 0,945 x 10¹⁶

Wszystkie trzy zapisy przedstawiają tą samą wartość. Wynika stąd, iż w zapisie zmiennoprzecinkowym liczby można przedstawiać w różnych kombinacjach mantys i wykładników. Stąd nazwa - zmiennoprzecinkowe (ang. floating point number).

Z uwagi na tą cechę wprowadza się tzw. postać znormalizowaną liczby zmiennoprzecinkowej, w której mantysa m spełnia nierówność:

1  |m| < p

Z trzech podanych powyżej form zmiennoprzecinkowych znormalizowany jest zapis:

9,45 x 10¹⁶

Normalizacja liczby zmiennoprzecinkowej polega na sprowadzeniu mantysy do podanego zakresu. Operację taką wykonujemy przesuwając cyfry mantysy w lewo lub w prawo, aż otrzymamy część całkowitą w zakresie od 1 do p. Jedno przesunięcie cyfr w lewo wymaga zmniejszenia wykładnika o 1. Przesunięcie w prawo wymaga zwiększenia wykładnika o 1. Np. znormalizujmy liczbę piątkową (143,11 x 10³)₍₅₎:

(143,11 x 10³)₍₅₎ = (14,311 x 10⁴)₍₅₎ = (1,4311 x 10¹⁰)₍₅₎

ZAPAMIĘTAJ W pamięci komputera liczby zmiennoprzecinkowe są przechowywane w postaci znormalizowanej, ponieważ pozwala to najlepiej wykorzystać przeznaczone na zapis liczby bity.

Precyzja liczb zmiennoprzecinkowych

Drugą istotną cechą jest precyzja liczby zmiennoprzecinkowej, która określa, ile znaczących cyfr liczba zawiera. Np. zapis:

9,45 x 10¹⁵

posiada tylko 3 cyfry znaczące : 9 4 i 5. Precyzja ma bardzo istotne znaczenie przy wykonywaniu operacji matematycznych na liczbach zmiennoprzecinkowych. Np. dodajmy do naszej liczby wartość 1:

9,45 x 10¹⁵ + 1 = 9450000000000000 + 1 = 9450000000000001

Zwróćcie uwagę, iż otrzymanej liczby nie da się zapisać w systemie zmiennoprzecinkowym z precyzją 3 cyfr. Jeśli to zrobimy, to znów otrzymamy naszą poprzednią liczbę 9,45 x 10¹⁵, co sugeruje, iż suma nie wpłynęła na wartość liczby. Wynika stąd wniosek:

ZAPAMIĘTAJ Liczby zmiennoprzecinkowe o ustalonej precyzji są liczbami przybliżonymi. Jeśli wynik jakiejkolwiek operacji wymaga większej precyzji, to zostanie on zaokrąglony. Powoduje to tzw. błędy zaokrągleń w obliczeniach wykonywanych przy pomocy maszyn cyfrowych.

Dwójkowy zapis zmiennoprzecinkowy

Wszystkie podane powyżej informacje dotyczą również dwójkowego systemu zapisu liczb zmiennoprzecinkowych. Wartość liczby obliczamy wg poznanego wzoru:

W_FP2 = m x 2^w

m - mantysa, liczba stałoprzecinkowa ze znakiem
w - wykładnik, liczba całkowita

W praktyce wymyślono wiele różnych sposobów zapisu liczb zmiennoprzecinkowych w systemie binarnym, jednakże dla potrzeb tego opracowania są one niepotrzebnie skomplikowane. Zainteresowanych odsyłam do artykułu "Dziedzictwo Konrada Zuse" oraz do dodatku. My wprowadzimy bardzo prosty (szkolny) system zapisu liczb zmiennoprzecinkowych w systemie binarnym, z którym będziemy mogli sobie eksperymentować bez zbytniego obciążenia wiedzą. Pomimo prostoty system ten będzie posiadał wszystkie podstawowe własności zapisu zmiennoprzecinkowego.

Najpierw ustalimy format liczby zmiennoprzecinkowej - będzie się ona składała z 8 bitów, które podzielimy na dwie grupy: 4 bity dla wykładnika w kodzie U2 oraz 4 bity dla mantysy w kodzie Z-M. W poniższej tabelce podajemy dokładną interpretację wartości poszczególnych bitów liczby zmiennoprzecinkowej w naszym systemie zapisu:

Format dwójkowej liczby zmiennoprzecinkowej
wykładnik - kod U2				mantysa - kod Z-M
b7	b6	b5	b4	b3	b2	b1	b0
x(-8)	x4	x2	x1	znak	x 1	x ^1/2	x ^1/4

Obliczmy dla przykładu wartości paru liczb zmiennoprzecinkowych zapisanych w tym systemie (bity wykładnika oznaczyliśmy kolorem zielonym, bit znaku niebieskim, a bity mantysy czerwonym):

00100111(FP2) w = 0010(U2) = 2 m = 0 1,11(ZM) = 1^3/4 WFP2 = m x 2^wWFP2 = 1^3/4 x 2^2WFP2 = ^7/4 x 4 WFP2 = 7

11110111(FP2) w = 1111(U2) = -1 m = 0 1,11(ZM) = 1^3/4 WFP2 = m x 2^wWFP2 = 1^3/4 x 2^-1WFP2 = ^7/4 x ^1/2 WFP2 = ^7/8

00001001(FP2) w = 0000(U2) = 0 m = 1 0,01(ZM) = -^1/4 WFP2 = m x 2^wWFP2 = (-^1/4) x 2^0WFP2 = (-^1/4) x 1 WFP2 = -^1/4

Skoro umiemy obliczyć wartość liczby zmiennoprzecinkowej, to teraz wykonajmy operację odwrotną - znajdźmy reprezentację wartości liczby w opisanym systemie zmiennoprzecinkowym. Skorzystamy tutaj z podanych w poprzednich rozdziałach wiadomości.

Przeliczenie wartości liczby z systemu dziesiętnego na dwójkowy system zmiennoprzecinkowy polega na znalezieniu wartości mantysy oraz wykładnika w systemie dwójkowym, a następnie znormalizowaniu liczby.

Przykład

Chcemy znaleźć zapis liczby dziesiętnej 3,5. W tym celu obliczamy jej reprezentację stałoprzecinkową:

3,5 = (3,5 x 2) / 2
3,5 = 7 / 2
3,5 = 0 11,1_(ZM)

Teraz normalizujemy liczbę obliczając wykładnik docelowy (potęga jest w kodzie U2):

3,5 = (0 11,1)_(ZM) x 10⁰⁰⁰⁰
3,5 = (0 1,11)_(ZM) x 10⁰⁰⁰¹ - postać znormalizowana

3,5 = (0001 0111)_(FP2)

Przykład

Przeliczmy wartość ³/₃₂:

³/₃₂ = (³/₃₂  x 2⁵) / 2^5
3/₃₂ = 3 / 2^5
3/₃₂ = 0 0,00011_(ZM)

³/₃₂ = (0 0,00011)_(ZM) x 10^0000
3/₃₂ = (0 0,0011)_(ZM) x 10^1111
3/₃₂ = (0 0,011)_(ZM) x 10^1110
3/₃₂ = (0 0,110)_(ZM) x 10^1101
3/₃₂ = (0 1,10)_(ZM) x 10¹¹⁰⁰

³/₃₂ = 11000110_(FP2)

Zakres dwójkowych liczb zmiennoprzecinkowych

Dla naszego systemu dwójkowych liczb zmiennoprzecinkowych największą wartość otrzymamy przy mantysie równej (0 1,11)_(ZM) = 1³/₄ i wykładniku 0111_(U2) = 7, czyli

Z_FPmax = 1³/₄ x 2⁷
Z_FPmax = ⁷/₄ x 128
Z_FPmax = 7 x 32
Z_FPmax = 224

Najmniejszą liczbą różną od zera otrzymamy dla mantysy równej (0 0,01)_(ZM) = ¹/₄ i wykładnika 1000_(U2) = -8, czyli

Z_FPmin = ¹/₄ x 2^-8
Z_FPmin = ¹/₄ x ¹/₂₅₆
Z_FPmin = ¹/₁₀₂₄

Ponieważ mantysa jest liczbą ze znakiem, zatem otrzymane wartości maksymalne i minimalne występują zarówno jako dodatnie, jak i ujemne. Zwróćcie uwagę na pewną charakterystyczną cechę liczb zmiennoprzecinkowych. Otóż nie wszystkie liczby leżące pomiędzy Z_FPmin a Z_FPmax dadzą się przedstawić w naszym systemie. Problem rozpoczyna się już z liczbą 9:

9 = (0 1001,000)_(ZM) x 10⁰⁰⁰⁰
9 = (0 100,100)_(ZM) x 10⁰⁰⁰¹
9 = (0 10,010)_(ZM) x 10⁰⁰¹⁰
9 = (0 1,001)_(ZM) x 10⁰⁰¹¹ - ostatni bit będzie utracony

Po normalizacji liczby otrzymaliśmy wykładnik 0011 oraz mantysę 0100. Nietrudno sprawdzić, iż taka liczba przedstawia wartość 8, a nie 9. Nastąpiła utrata dokładności. Związane to jest z precyzją naszego systemu. Dokładnie możemy zapamiętać tylko trzy znaczące bity. Liczba 9 wymaga 4 bitów znaczących (1001). Nie może więc być poprawnie przedstawiona w takim systemie i zostanie zaokrąglona w dół (bity znaczące pozostają po usunięciu od końca i od początku liczby wszystkich bitów o wartości 0, np. liczba 0,0101000 ma trzy bity znaczące równe 101).

ZAPAMIĘTAJ W przypadku liczb zmiennoprzecinkowych oprócz zakresu należy również określać precyzję. Precyzja rośnie wraz ze wzrostem liczby bitów przeznaczonych na mantysę. Zakres rośnie wraz ze wzrostem liczby bitów przeznaczonych na wykładnik.

Zadania

1. W jakim celu wymyślono liczby zmiennoprzecinkowe?

2. Zapisz podane liczby stałopozycyjne jako znormalizowane liczby zmiennoprzecinkowe::

152,403₆, 3222,33₄, 1101,011₂

3. Oblicz wartość następujących dwójkowych liczb zmiennoprzecinkowych zapisanych wg podanego w rozdziale systemu:

00101100,  01010111, 10001101

4. Zapisz w przedstawionym w rozdziale dwójkowym systemie zmiennoprzecinkowym następujące wartości dziesiętne:

-2,5  24  80

5. Oblicz górną granicę dwójkowych liczb zmiennoprzecinkowych dla mantysy i wykładnika 8 bitowego.

Liczby zmiennoprzecinkowe

Zadanie 1

W jakim celu wymyślono liczby zmiennoprzecinkowe?

Aby umożliwić efektywny zapis i przetwarzanie liczb z dużego zakresu wartości. Liczby zmiennoprzecinkowe pozwalają wykonywać operacje na liczbach rzeczywistych, nadają się zatem szczególnie dobrze do zastosowań naukowych i technicznych.

Zadanie 2

Zapisz podane liczby stałopozycyjne jako znormalizowane liczby zmiennoprzecinkowe::

152,403₆ = (152,403 x 10⁰)₍₆₎
152,403₆ = (15,2403 x 10¹)₍₆₎
152,403₆ = (1,52403 x 10²)₍₆₎

3222,33₄ = (3222,33 x 10⁰)₍₄₎
3222,33₄ = (322,233 x 10¹)₍₄₎
3222,33₄ = (32,2233 x 10²)₍₄₎
3222,33₄ = (3,22233 x 10³)₍₄₎

1101,011₂ = (1101,011 x 10⁰)₍₂₎
1101,011₂ = (110,1011 x 10¹)₍₂₎
1101,011₂ = (11,01011 x 10¹⁰)₍₂₎
1101,011₂ = (1,101011 x 10¹¹)₍₂₎

Zadanie 3

Oblicz wartość następujących dwójkowych liczb zmiennoprzecinkowych zapisanych wg podanego w rozdziale systemu:

0010 1100
w = 0010_(U2) = 2
m = 1 1,00_(ZM) = - 1
W = m x 2^w
W = (- 1) x 2²
W = (- 1) x 4
W = - 4

0101 0111
w = 0101_(U2) = 5
m = 0 1,11_(ZM) = 1³/₄
W = m x 2^w
W = 1³/₄ x 2⁵
W = ⁷/₄ x 32
W = 56

1000 1101
w = 1000_(U2) = - 8
m = 1 1,01 = - 1¹/₄
W = m x 2^w
W = (- 1¹/₄) x 2^-8
W = (- ⁵/₄) x ¹/₂₅₆
W = - ⁵/₁₀₂₄

Zadanie 4

Zapisz w przedstawionym w rozdziale dwójkowym systemie zmiennoprzecinkowym następujące wartości dziesiętne:

- 2,5 = (- 2,5 x 2) / 2
- 2,5 = (- 5) / 2
- 2,5 = 1 10,10 x 10⁰⁰⁰⁰
- 2,5 = 1 1,01 x 10⁰⁰⁰¹
- 2,5 = (0001 1101⁾_(FP)

24 = 0 11000,00 x 10⁰⁰⁰⁰
24 = 0 1100,00 x 10⁰⁰⁰¹
24 = 0 110,00 x 10⁰⁰¹⁰
24 = 0 11,00 x 10⁰⁰¹¹
24 = 0 1,10 x 10⁰¹⁰⁰
24 = (0100 0110)_(FP)

80 = 0 1010000,00 x 10⁰⁰⁰⁰
80 = 0 101000,00 x 10⁰⁰⁰¹
80 = 0 10100,00 x 10⁰⁰¹⁰
80 = 0 1010,00 x 10⁰⁰¹¹
80 = 0 101,00 x 10⁰¹⁰⁰
80 = 0 10,10 x 10⁰¹⁰¹
80 = 0 1,01 x 10⁰¹¹⁰
80 = (0110 0101)_(FP)

Zadanie 5

Oblicz górną granicę dwójkowych liczb zmiennoprzecinkowych dla mantysy i wykładnika 8 bitowego.

Mantysa przyjmuje największą wartość, gdy wszystkie bity modułu będą ustawione na 1, czyli 01111111. Odpowiada to liczbie stałoprzecinkowej 0 1,111111_(ZM) równej ¹²⁷/₆₄. Wykładnik największą wartość przyjmie, gdy bit znaku będzie zerem, a pozostałe bity jedynkami, czyli 01111111_(U2) = 127. Zatem

Z_FPmax = ¹²⁷/₆₄ x 2¹²⁷
Z_FPmax = ¹²⁷/₆₄ x 2⁶ x 2¹²¹
Z_FPmax = ¹²⁷/₆₄ x 64 x 2¹²¹
Z_FPmax = 127x 2¹²¹
Z_FPmax  3,38 x 10³⁸

Precyzja takich liczb wynosi siedem bitów, czyli nieco ponad dwie cyfry dziesiętne.

ARYTMETYKA ZMIENNOPRZECINKOWA

W tym rozdziale

Dodawanie i odejmowanie dwójkowych liczb zmiennoprzecinkowych
Mnożenie i dzielenie dwójkowych liczb zmiennoprzecinkowych
Zadania

Dodawanie i odejmowanie dwójkowych liczb zmiennoprzecinkowych

Koprocesor arytmetyczny

Arytmetyka liczb zmiennoprzecinkowych wbrew pozorom nie jest specjalnie trudna. Jeśli dokładnie przyswoiliście sobie zasady wykonywania operacji arytmetycznych na liczbach ze znakiem, to nie powinniście mieć z nią żadnych problemów.

Pionierem w tej dziedzinie był sławny niemiecki konstruktor i wynalazca, Konrad Zuse, którego obecnie uważa się za ojca komputerów. Co ciekawe, wyprzedził on rozwój techniki o kilka dziesięcioleci i już w 1936 roku skonstruował komputer, w którym operacje arytmetyczne wykonywane były na bazie dwójkowego systemu zmiennoprzecinkowego. Dla porównania pierwsze procesory firmy Intel zastosowane w komputerach IBM w 1981 roku (45 lat później) nie miały wcale instrukcji obsługi liczb zmiennoprzecinkowych - obliczenia na takich liczbach wykonywano w sposób programowy (tzn. bardzo wolno). Dopiero później zastosowano dodatkowy procesor zwany zmiennoprzecinkowym koprocesorem arytmetycznym, który współpracując z głównym procesorem komputera wykonywał sprzętowo (tzn. bardzo szybko) operacje na liczbach zmiennoprzecinkowych. Nowsze generacje procesorów (od modelu Intel 80486 do współczesnego Pentium IV) wchłonęły ten dodatkowy układ i stanowi on obecnie integralną część mikroprocesora.

Mamy dane dwie dwójkowe liczby zmiennoprzecinkowe o postaci m₁ x 2^w1  i m₂ x 2^w2. Rozważmy sumę tych liczb:

m1 x 2^w1 + m2 x 2^w2 =	m1 x 2^w1	x 2^w2 + m2 x 2^w2
			2^w2

m1 x 2^w1 + m2 x 2^w2 = m1 x 2^w1-w2 x 2^w2 + m2 x 2^w2

m1 x 2^w1 + m2 x 2^w2 = (m1 x 2^w1-w2 + m2) x 2^w2

Co wynika z tych przekształceń? Otóż przed wykonaniem sumowania musimy odpowiednio przekształcić mantysę i wykładnik jednej z liczb tak, aby jej wykładnik zrównał się z wykładnikiem drugiej liczby. Operację tą nazywamy wyrównaniem wykładników. W systemie binarnym dokonuje się ją w bardzo prosty sposób - przesuwając bity mantysy w lewo ze zmniejszaniem wykładnika lub w prawo ze zwiększaniem wykładnika. O kierunku przesuwania bitów mantysy decyduje znak różnicy w₁ - w₂. Wynik dodatni - przesuwamy w lewo, ujemny - przesuwamy w prawo. Po zrównaniu wykładników mantysy dodajemy w zwykły sposób wg zasad dla liczb w kodzie Z-M. Po wykonaniu dodawania wynik normalizujemy.

Przykład

Dodajmy dla przykładu liczby (0010 0100)_(FP) i (0000 0110)_(FP).

w₁ = 0010_(U2) = 2,  m₁ = (0 1,00)_(ZM) = 1 (liczba ta ma wartość dziesiętną 4)
w₂ = 0000_(U2) = 0,  m₂ = (0 1,10)_(ZM) = 1¹/₂ (liczba ta ma wartość dziesiętną 1¹/₂)

Najpierw obliczamy różnicę wykładników:

w₁ - w₂ = 2 - 0 = 2

Wynik dodatni, zatem mantysę m₁ przesuwamy o dwa bity w lewo zmniejszając jednocześnie wykładnik w₁ o dwa, aby zachować wartość liczby:

m1 = (0 001,00)(ZM)	, w1 = 0010(U2)
m1 = (0 010,00)(ZM)	, w1 = 0001(U2) - pierwsze przesunięcie, wykładnik zmniejszamy o 1
m1 = (0 100,00)(ZM)	, w1 = 0000(U2) - ostatnie przesunięcie, wykładniki są zrównane

Po zrównaniu wykładników mantysy dodajemy wg zasad opisanych dla kodu znak-moduł:

0 100,00(ZM) + 0 001,10(ZM)

0 101,10(ZM)

Otrzymaliśmy nową mantysę m = (0 101,10)_(ZM) przy wykładniku w = 0000_(U2). Wynik normalizujemy:

m = (0 101,10)(ZM)	, w = 0000
m = (0 10,11)(ZM)	, w = 0001
m = (0 1,01)(ZM)	, w = 0010 - mantysa znormalizowana, utraciliśmy ostatni bit.

Wynikiem dodawania jest liczba zmiennoprzecinkowa (0010 0101)_(FP), która ma wartość dziesiętną 5. W trakcie niezbędnej normalizacji nastąpiła utrata dokładności liczby, dlatego wynik dodawania jest przybliżony. Zapamiętajcie tą charakterystyczną cechę arytmetyki liczb zmiennoprzecinkowych.

Możemy teraz uogólnić procedurę dodawania i odejmowania dwójkowych liczb zmiennoprzecinkowych:

ZAPAMIĘTAJ Procedura dodawania i odejmowania liczb zmiennoprzecinkowych m12^w1 i m22^w2 jest następująca: Oblicz różnicę wykładników w1 - w2. Jeśli różnica ta jest różna od zera, to należy zrównać wykładnik w1 z w2. Bity mantysy m1 przesuwamy o tyle miejsc, ile wynosi wartość bezwzględna różnicy wykładników. Kierunek przesunięcia określa znak różnicy - minus: przesunięcie w prawo, plus: przesunięcie w lewo. Po zrównaniu wykładników mantysy dodajemy (lub odejmujemy) wg zasad obowiązujących dla liczb w kodzie znak-moduł. Wynik dodawania (odejmowania) musi być znormalizowany

Mnożenie i dzielenie dwójkowych liczb zmiennoprzecinkowych

Mamy dane dwie liczby zmiennoprzecinkowe m₁2^w1 oraz m₂2^w2. Iloczyn obliczamy zgodnie ze wzorem:

m₁2^w1 x m₂2^w2 = m₁m₂2^w1+w2

Mantysa iloczynu jest równa iloczynowi mantys mnożonych liczb. Wykładnik iloczynu jest równy sumie wykładników mnożonych liczb. Po wykonaniu mnożenia wynik należy znormalizować.

Przykład

Obliczmy iloczyn następujących liczb zmiennoprzecinkowych: (1110 0110)_(FP), (0010 0100)_(FP):

w₁ = 1110_(U2) = -2,  m₁ = (0 1,10)_(ZM) = 1¹/₂ (liczba ma wartość dziesiętną ³/₈)
w₂ = 0010_(U2) = 2,   m₂ = (0 1,00)_(ZM) = 1 (liczba ma wartość dziesiętną 4)

Obliczamy iloczyn mantys:

110 x 100

110

11000

W otrzymanym wyniku odkładamy 4 cyfry po przecinku i otrzymujemy:

m = m₁ x m₂ = (0 1,10)_(ZM)

Teraz obliczamy sumę wykładników:

1110 + 0010

1 0000

w = w₁ + w₂ = 0000_(U2)

Mantysa jest już znormalizowana, zatem wynikiem mnożenia jest liczba zmiennoprzecinkowa (0000 0110)_(FP) o wartości dziesiętnej 1¹/₂. Wynik jest dokładny, gdyż zachowaliśmy wszystkie bity znaczące iloczynu.

ZAPAMIĘTAJ Procedura mnożenia liczb zmiennoprzecinkowych m12^w1 i m22^w2 jest następująca: Oblicz mantysę iloczynu równą m = m1 x m2. Oblicz wykładnik iloczynu równy w = w1 + w2. Znormalizuj mantysę iloczynu

Wzór na dzielenie dwóch liczb zmiennoprzecinkowych jest następujący:

m12^w1	=	m1	x 2^w1-w2
m22^w2				m2

Mantysa ilorazu równa jest ilorazowi mantys. Wykładnik ilorazu równy jest różnicy wykładnika dzielnej i dzielnika. Po wykonaniu dzielenie mantysa wyniku musi zostać znormalizowana.

Dzielenie mantys wykonujemy wg zasad opisanych w rozdziale o operacjach arytmetycznych z tym, iż nie nie kończymy na reszcie, lecz kontynuujemy otrzymując części ułamkowe - zasady są identyczne jak w systemie dziesiętnym. Dzielenie przerywamy w momencie osiągnięcia zadanej liczby bitów znaczących.

Przykład

Podzielmy liczbę (1111 0110)_(FP) przez (1101 0100)_(FP):

w₁ = 1111_(U2) = - 1, m₁ = (0 1,10)_(ZM) = 1¹/₂, (liczba o wartości ³/₄)
w₂ = 1101_(U2) = - 3, m₂ = (0 1,00)_(ZM) = 1, (liczba o wartości ¹/₈)

Dzielimy mantysę m₁ przez m₂:

   1,1
1,10   : 100
1,00
0,100
0,100
  000

Mantysa ilorazu jest już znormalizowana i wynosi:

m = m₁ : m₂ = (0 1,10)_(ZM)

Teraz odejmujemy wykładniki:

  1111
- 1101
  0010

w = w₁ - w₂ = 0010_(U2) = 2

Ostatecznie otrzymujemy liczbę zmiennoprzecinkową (0010 0110)_(FP), której wartość wynosi 6.

ZAPAMIĘTAJ Procedura dzielenia liczb zmiennoprzecinkowych m12^w1 i m22^w2 jest następująca: Oblicz mantysę ilorazu równą m = m1 : m2. Oblicz wykładnik ilorazu równy w = w1 - w2. Znormalizuj mantysę iloczynu

Zadania

1. Dodaj

(1100 0111)_(FP) i (1101 0111)_(FP)

2. Odejmij

(0011 0111)_(FP) i (0001 1100)_(FP)

3. Pomnóż

(0011 0111)_(FP) i (1100 0111)_(FP)

Arytmetyka zmiennoprzecinkowa

Zadanie 1

Dodaj

(1100 0111)_(FP) i (1101 0111)_(FP)

w₁ = 1100_(U2) = -4, m₁ = (0 1,11)_(ZM) = 1³/₄ (wartość dziesiętna ⁷/₆₄)
w₂ = 1101_(U2) = -3, m₂ = (0 1,11)_(ZM) = 1³/₄ (wartość dziesiętna ⁷/₃₂)

Obliczamy różnicę wykładników w₁ i w₂:

w₁ - w₂ = -4 - (-3) = -1

Mantysę m₁ musimy przesunąć o 1 bit w prawo:

m₁ = (0 0,111)_(ZM)

Obliczamy mantysę sumy:

0 0,111(ZM) + 0 1,110(ZM)

0 10,101(ZM)

Normalizujemy mantysę:

m = (0 10,101)(ZM)	, w = 1101(U2)
m = (0 1,0101)(ZM)	, w = 1110(U2) - mantysa znormalizowana
m = (0 1,01)(ZM)	, w = 1110(U2) - obcinamy mantysę do 3 bitów znaczących

i ostatecznie wynikiem jest liczba zmiennoprzecinkowa: (1110 0101)_(FP) o wartości dziesiętnej ⁵/₁₆. Ponieważ w czasie normalizacji utracone zostały mniej znaczące bity mantysy wynikowej, wynik jest przybliżony.

Zadanie 2

Odejmij

(0011 0111)_(FP) i (0001 1100)_(FP)

w₁ = 0011_(U2) = 3, m₁ = (0 1,11)_(ZM) = 1³/₄ (wartość dziesiętna 14)
w₂ = 0001_(U2) = 1, m₂ = (1 1,00)_(ZM) = - 1 (wartość dziesiętna - 2)

Obliczamy różnicę wykładników w₁ i w₂:

w₁ - w₂ = 3 - 1 = 2

Mantysę m₁ musimy przesunąć o 2 bity w lewo:

m₁ = (0 111,00)_(ZM)

Obliczamy mantysę różnicy:

0 111,00(ZM) + 1 001,00(ZM)

0 1000,00(ZM)

Normalizujemy mantysę:

m = (0 1000,00)(ZM)	, w = 0001(U2)
m = (0 100,00)(ZM)	, w = 0010(U2)
m = (0 10,00)(ZM)	, w = 0011(U2)
m = (0 1,00)(ZM)	, w = 0100(U2)

i ostatecznie wynikiem jest liczba zmiennoprzecinkowa: (0100 0100)_(FP) o wartości dziesiętnej 16. Jest to wynik dokładny.

Zadanie 3

Pomnóż

(0011 0111)_(FP) i (1100 0111)_(FP)

w₁ = 0011_(U2) = 3,  m₁ = (0 1,11)_(ZM) = 1³/₄ (wartość dziesiętna 14)
w₂ = 1100_(U2) = -4, m₂ = (0 1,11)_(ZM) = 1³/₄ (wartość dziesiętna ⁷/₆₄)

 Obliczamy iloczyn mantys:

111 x   111

111 111  + 111

110001

m = m₁ x m₂ = (0 11,0001)_(ZM)

Obliczamy sumę wykładników:

0011 + 1100

1111

w = w₁ + w₂ = 1111_(U2)

Normalizujemy mantysę:

m = (0 110001)(ZM)	, w = 1111(U2)
m = (0 1,10001)(ZM)	, w = 0000(U2)

Mantysę ograniczamy do trzech bitów znaczących i otrzymujemy wartość wynikową iloczynu (0000 0110)_(FP) - liczba 1¹/₂. Ponieważ utracone zostały bity mniej znaczące mantysy, wynik jest przybliżony.

KODOWANIE LICZB

Rozwiązanie zadań

W ostatnim rozdziale podaliśmy rozwiązania zadań umieszczonych w rozdziałach naszego opracowania. Służą one do sprawdzenia wykonanych obliczeń oraz wyjaśniają zastosowane przy tym metody, dlatego rozwiązań nie należy czytać przed samodzielnym rozwiązaniem danego problemu.

Rozdziały

Jednostki informacji
Naturalny Kod Binarny
Algorytm Hornera
Operacje Arytmetyczne
Operacje Logiczne
Kod Z-M
Kod U2
Kod BCD
Kod Gray'a
Liczby zmiennoprzecinkowe
Arytmetyka zmiennoprzecinkowa

Algorytm Hornera

Zadanie 1

Oblicz za pomocą algorytmu Hornera wartość następujących liczb pozycyjnych:

6243₍₈₎

w₀ = 0
w₁ = 0 x 8 + 6 = 6
w₂ = 6 x 8 + 2 = 48 + 2 = 50
w₃ = 50 x 8 + 4 = 400 + 4 = 404
w₄ = 404 x 8 + 3 = 3232 + 3 = 3235

132211₍₄₎

w₀ = 0
w₁ = 0 x 4 + 1 = 1
w₂ = 1 x 4 + 3 = 4 + 3 = 7
w₃ = 7 x 4 + 2 = 28 + 2 = 30
w₄ = 30 x 4 + 2 = 120 + 2 = 122
w₅ = 122 x 4 + 1 = 488 + 1 = 489
w₆ = 489 x 4 + 1 = 1956 + 1 = 1957

9FF35₍₁₆₎

w₀ = 0
w₁ = 0 x 16 + 9 = 9
w₂ = 9 x 16 + 15 = 144 + 15 = 159
w₃ = 159 x 16 + 15 = 2544 + 15 = 2559
w₄ = 2559 x 16 + 3 = 40944 + 3 = 40947
w₅ = 40947 x 16 + 5 = 655152 + 5 = 655157

Zadanie 2

Oblicz algorytmem Hornera wartość liczby dwójkowej:

11001110001111000011111₍₂₎

w₀ = 0
w₁ = 0 + 0 + 1 = 1
w₂ = 1 + 1 + 1 = 3
w₃ = 3 + 3 + 0 = 6
w₄ = 6 + 6 + 0 = 12
w₅ = 12 + 12 + 1 = 25
w₆ = 25 + 25 + 1 = 51
w₇ = 51 + 51 + 1 = 103
w₈ = 103 + 103 + 0 = 206
w₉ = 206 + 206 + 0 = 412
w₁₀= 412 + 412 + 0 = 824
w₁₁= 824 + 824 + 1 = 1649
w₁₂= 1649 + 1649 + 1 = 3299
w₁₃= 3299 + 3299 + 1 = 6599
w₁₄= 6599 + 6599 + 1 = 13199
w₁₅= 13199 + 13199 + 0 = 26398
w₁₆= 26398 + 26398 + 0 = 52796
w₁₇= 52796 + 52796 + 0 = 105592
w₁₈= 105592 + 105592 + 0 = 211184
w₁₉= 211184 + 211184 + 1 = 422369
w₂₀= 422369 + 422369 + 1 = 844739
w₂₁= 844739 + 844739 + 1 = 1689479
w₂₂= 1689479 + 1689479 + 1 = 3378959
w₂₃= 3378959 + 3378959 + 1 = 6757919

Zadanie 3

Oblicz algorytmem Hornera wartość następujących, pozycyjnych liczb stałoprzecinkowych:

221,1022₍₃₎

w₀ = 0
w₁ = 0 x 3 + 2 = 2
w₂ = 2 x 3 + 2 = 6 + 2 = 8
w₃ = 8 x 3 + 1 = 24 + 1 = 25 - część całkowita
w₄ = 25 x 3 + 1 = 75 + 1 = 76
w₅ = 76 x 3 + 0 = 228 + 0 = 228
w₆ = 228 x 3 + 2 = 684 + 2 = 686
w₇ = 686 x 3 + 2 = 2058 + 2 = 2060
w = w₇ : 3⁴ = 2060 : 81 = 25 ³⁴/₈₁

412,301₍₅₎

w₀ = 0
w₁ = 0 x 5 + 4 = 4
w₂ = 4 x 5 + 1 = 20 + 1 = 21
w₃ = 21 x 5 + 2 = 105 + 2 = 107 - część całkowita
w₄ = 107 x 5 + 3 = 535 + 3 = 538
w₅ = 538 x 5 + 0 = 2690 + 0 = 2690
w₆ = 2690 x 5 + 1 = 13450 + 1 = 13451
w = w₆ : 5³ = 13451 : 125 = 107 ⁷⁶/₁₂₅

634,1252₍₇₎

w₀ = 0
w₁ = 0 x 7 + 6 = 6
w₂ = 6 x 7 + 3 = 42 + 3 = 45
w₃ = 45 x 7 + 4 = 315 + 4 = 319 - część całkowita
w₄ = 319 x 7 + 1 = 2233 + 1 = 2234
w₅ = 2234 x 7 + 2 = 15638 + 2 = 15640
w₆ = 15640 x 7 + 5 = 109480 + 5 = 109485
w₇ = 109485 x 7 + 2 = 766395 + 2 = 766397
w = w₇ : 7⁴ = 766397 : 2401 = 319 ⁴⁷⁸/₂₄₀₁

Zadanie 4

Przelicz na system szóstkowy następujące liczby dziesiętne:

100

100 : 6 =	16	i reszta c0 = 4
16 : 6 =	2	i reszta c1 = 4
2 : 6 =	0	i reszta c3 = 2	- koniec

100 = 244₍₆₎

500

500 : 6 =	83	i reszta c0 = 2
83 : 6 =	13	i reszta c1 = 5
13 : 6 =	2	i reszta c2 = 1
2 : 6 =	0	i reszta c3 = 2	- koniec

500 = 2152₍₆₎

1000

1000 : 6 =	166	i reszta c0 = 4
166 : 6 =	27	i reszta c1 = 4
27 : 6 =	4	i reszta c2 = 3
4 : 6 =	0	i reszta c3 = 4	- koniec

1000 = 4344₍₆₎

10000

10000 : 6 =	1666	i reszta c0 = 4
1666 : 6 =	277	i reszta c1 = 4
277 : 6 =	46	i reszta c2 = 1
46 : 6 =	7	i reszta c3 = 4
7 : 6 =	1	i reszta c4 = 1
1 : 6 =	0	i reszta c5 = 1	- koniec

10000 = 114144₍₆₎

Zadanie 5

Przelicz na system dwójkowy następujące liczby dziesiętne:

100

100 : 2 =	50	i reszta c0 = 0
50 : 2 =	25	i reszta c1 = 0
25 : 2 =	12	i reszta c2 = 1
12 : 2 =	6	i reszta c3 = 0
6 : 2 =	3	i reszta c4 = 0
3 : 2 =	1	i reszta c5 = 1
1 : 2 =	0	i reszta c6 = 1	- koniec

100 = 1100100₍₂₎

1000

1000 : 2 =	500	i reszta c0 = 0
500 : 2 =	250	i reszta c1 = 0
250 : 2 =	125	o reszta c2 = 0
125 : 2 =	62	i reszta c3 = 1
62 : 2 =	31	i reszta c4 = 0
31 : 2 =	15	i reszta c5 = 1
15 : 2 =	7	i reszta c6 = 1
7 : 2 =	3	i reszta c7 = 1
3 : 2 =	1	i reszta c8 = 1
1 : 2 =	0	i reszta c9 = 1	- koniec

1000 = 1111101000₍₂₎

10000

10000 : 2 =	5000	i reszta c0 = 0
5000 : 2 =	2500	i reszta c1 = 0
2500 : 2 =	1250	i reszta c2 = 0
1250 : 2 =	625	i reszta c3 = 0
625 : 2 =	312	i reszta c4 = 1
312 : 2 =	156	i reszta c5 = 0
156 : 2 =	78	i reszta c6 = 0
78 : 2 =	39	i reszta c7 = 0
39 : 2 =	19	i reszta c8 = 1
19 : 2 =	9	i reszta c9 = 1
9 : 2 =	4	i reszta c10=1
4 : 2 =	2	i reszta c11=0
2 : 2 =	1	i reszta c12=0
1 : 2 =	0	i reszta c13=1	- koniec

10000 = 10011100010000₍₂₎

Zadanie 6

Przelicz na system trójkowy z dokładnością do 4 cyfr po przecinku następujące dwie liczby dziesiętne:

10,5

w = 10,5 x 3⁴ = 10,5 x 81 = 850,5

Liczby tej nie przedstawimy dokładnie w systemie trójkowym z dokładnością do 4 cyfr po przecinku. Zaokrąglamy ją do najbliższej liczby całkowitej

w = 850

850 : 3 =	283	i reszta c0 = 1
283 : 3 =	94	i reszta c1 = 1
94 : 3 =	31	i reszta c2 = 1
31 : 3 =	10	i reszta c3 = 1
10 : 3 =	3	i reszta c4 = 1
3 : 3 =	1	i reszta c5 = 0
1 : 3 =	0	i reszta c6 = 1	- koniec

Odkładamy cztery ostatnie cyfry i otrzymujemy :

10,5  101,1111₍₃₎

15,86

w = 15,86 x 3⁴ = 15,86 x 81 = 1284,66
w = 1285

1285 : 3 =	428	i reszta c0 = 1
428 : 3 =	142	i reszta c1 = 2
142 : 3 =	47	i reszta c2 = 1
47 : 3 =	15	i reszta c3 = 2
15 : 3 =	5	i reszta c4 = 0
5 : 3 =	1	i reszta c5 = 2
1 : 3 =	0	i reszta c6 = 1	i koniec

15,86  120,2121₍₃₎

---