PODSTAWY TEORII
UKŁADÓW CYFROWYCH
Opracował: Andrzej
Nowak
PODSTAWY TEORII
UKŁADÓW CYFROWYCH
Opracował: Andrzej
Nowak
Jednostki
informacji
Jednostki informacji
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.
Skoro do wyrażania informacji możemy używać
różnych symboli (słów), to dlaczego nie zastosować
do tego celu bitów?
Jednostki informacji
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)
Jednostki informacji
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
sposobów.
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.
Jednostki informacji
Tyle tylko, że 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.
Taśma dziurkowana.
Tak kiedyś zapisywano dane.
Każda dziurka odpowiadała
bitowi o stanie
1
.
Brak dziurki
oznaczał stan
0
.
Jednostki informacji
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.
Czujnik ruchu.
W razie wykrycia ruchu
w okolicy przekazuje bit
o stanie
1
.
Jednostki informacji
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.
Jednostki informacji
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).
Jednostki informacji
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.
Jednostki informacji
Jednostki informacji
Zwróćmy uwagę na małą czytelność dla ludzi
informacji zapisanej w systemie binarnym.
Szczególnie, jeśli wszystkie bity zapiszemy w jednym
ciągu:
00000000000000000000111111110000001111111111000000001111111111000000001111000000000000001000000001010
10101010101
Systemy
liczbowe
Systemy liczbowe
Systemy liczbowe
to sposoby zapisywania
i nazywania liczb.
Rozróżnia się systemy liczbowe
pozycyjne
i
niepozycyjne
(addytywne).
W systemach liczbowych pozycyjnych liczbę
przedstawia się jako ciąg cyfr. Wartość jej jest
zależna od położenia (pozycji) cyfry w liczbie.
Do systemów pozycyjnych zaliczamy m.in.:
dziesiątkowy, dwójkowy, ósemkowy,
szesnastkowy.
Do addytywnych systemów liczbowych zaliczamy
m.in.: rzymski, hieroglificzny, alfabetyczny,
gdzie wartość liczby jest sumą wartości jej
znaków cyfrowych.
Definicja liczby
Liczba
– pojęcie abstrakcyjne, jedno z najczęściej
używanych w matematyce.
Określenie „liczba” bez żadnego przymiotnika jest
nieścisłe, gdyż matematycy nie definiują „liczb”,
lecz „liczby naturalne”, „liczby całkowite”, itp.
Poszczególne rodzaje liczb są definiowane za
pomocą aksjomatów lub konstruowane z bardziej
podstawowych pojęć, takich jak zbiór, czy typy
liczb prostsze od konstruowanego.
Pierwotnie liczby służyły do porównywania wielkości
zbiorów przedmiotów (liczby naturalne), później
także wielkości ciągłych (miary i wagi), obecnie
w matematyce są rozważane jako twory
abstrakcyjne, w oderwaniu od ewentualnych
fizycznych zastosowań.
System pozycyjny – wzór ogólny
Ogólnie oznaczając przez
c
n
- cyfrę systemu pozycyjnego i
n
– pozycję
cyfry
zaś przez:
p
- podstawę systemu,
wartość reprezentowaną przez symbol liczby
zapisujemy jako sumę iloczynów postaci:
c
n
*
p
n
+ . . . + c
2
*
p
2
+ c
1
*
p
1
+
c
0
*
p
0
System
dziesiątkowy
(
decymalny
)
System dziesiątkowy
System dziesiątkowy
: 0, 1, 2, 3, 4, 5, 6, 7,
8, 9
- to wszystkim znane symbole cyfr arabskiego
dziesiątkowego, pozycyjnego systemu liczenia.
Każdemu z tych symboli przyporządkowana jest
pewna wartość.
Z tych prostych symboli tworzymy symbole
bardziej złożone wpisując cyfry na tzw. pozycje,
w uszeregowaniu od prawej do lewej.
I tak najbardziej skrajna prawa pozycja, to pozycja
zerowa (pozycja jedności), dalej pozycja
pierwsza (pozycja dziesiątek), dalej pozycja
druga (pozycja setek), ... itd.
System dziesiątkowy
Zgodnie z przedstawioną zasadą, każdemu
prostemu czy złożonemu symbolowi układu
można przyporządkować wartość, zwaną liczbą.
Liczba to nie to samo co cyfra.
Cyfry to znaki graficzne służące do opisu liczb.
System dziesiątkowy
Symb
ol
Wartość w systemie Liczba
7
7 *10
0
siedem
56
5 * 10
1
+ 6 * 10
0
pięćdziesiąt
sześć
342
3 * 10
2
+ 4 * 10
1
+2 *
10
0
trzysta
czterdzieści dwa
Konwersja liczb
Konwersja na dziesiątkowy:
(4013)
5
= 4 * 5
3
+ 0 * 5
2
+ 1 * 5
1
+ 3 * 5
0
= 500 + 5
+ 3 = (508)
10
Konwersja z dziesiątkowego
System dwójkowy
(
binarny
)
System dwójkowy (binarny)
System dwójkowy
- zrewolucjonizował cały
świat techniki, dając podstawę rozwoju wiodącej
obecnie dziedzinie wiedzy jaką jest informatyka.
Cyframi tego systemu są: 0 i 1.
Symbolizują one dwa stany tzw.
0 -
stan niski
– (brak działania/brak
sygnału)
1-
stan wysoki
– (działanie
układu/sygnał)
Podstawą systemu jest 2.
Stąd też i nazwa układ dwójkowy.
Konwersja liczb
Ponieważ jest to również system pozycyjny, to
możemy w znany już sposób dokonywać konwersji
liczby z systemu dziesiątkowego na dwójkowy, np.
( 87)
10
= 87 : 2 = 43 1 =
(1010111)
2
43 : 2 = 21 1
21 : 2 = 10 1
10 : 2 = 5 0
5 : 2 = 2 1
2 : 2 = 1 0
1 : 2 = 0 1
Konwersja liczb
Konwersja z systemu dwójkowego na dziesiątkowy:
(11011101)
2
= 1 * 2
7
+ 1 * 2
6
+ 0 * 2
5
+ 1 * 2
4
+ 1 * 2
3
+ 1 * 2
2
+ 0 * 2
1
+ 1 * 2
0
=
= 128 + 64 + 16 + 8 + 4 + 1 =
(221)
10
System
szesnastkowy
(
heksadecymalny
)
System szesnastkowy
Nawet niezbyt duża co do wartości liczba z systemu
dziesiątkowego zamieniona na postać dwójkową
(binarną) jest długim ciągiem jedynek i zer, a
ponowne przeliczenie jej na wartość w systemie
dziesiątkowym procesem żmudnym
i długotrwałym.
Między innymi dla uproszczenia zapisu i szybkiego
przeliczenia wartości wprowadzono system
pozycyjny, którego podstawą jest 2
4
, czyli 16 i
nazwano systemem szesnastkowym
(heksadecymalnym).
Cyframi tego systemu są:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C,
D, E, F
Zależność między liczbami
Cyfry systemu
szesnastkowego
Liczby systemu
dziesiątkowego
Liczby systemu
dwójkowego
0
0
0000
1
1
0001
2
2
0010
3
3
0011
4
4
0100
5
5
0101
6
6
0110
7
7
0111
8
8
1000
9
9
1001
A
10
1010
B
11
1011
C
12
1100
D
13
1101
E
14
1110
F
15
1111
Konwersje liczb na system
binarny
Każdej cyfrze systemu szesnastkowego odpowiada
cztero-pozycyjna liczba systemu dwójkowego.
Zamiana postaci liczby z systemu dwójkowego na
liczbę systemu szesnastkowego polega na
przypisaniu każdemu kolejnemu cztero-
pozycyjnemu pakietowi układów zero-
jedynkowych odpowiedniej cyfry układu
szesnastkowego, np.
(1011|0011|1010)
2
= (B3A)
16
Jeżeli w zapisie liczby dwójkowej ostatni /pakiet/
(z lewej) ma mniej niż cztery pozycje zero-
jedynkowe, to uzupełniamy brakujące pozycje
zerami, np.
(
11
|1011|1110)
2
= (
00
11|1011|1110)
2
=
(3BE)
16
Konwersje liczb na system
decymalny
Przeliczenie liczby z systemu szesnastkowego na
wartość liczby w systemie dziesiątkowym
odbywa się według znanego wzoru , np.
(3BE)
16
= 3 * 16
2
+ 11 * 16
1
+ 14 *
16
0
= 768 + 176 + 14 = (958)
10
Dwójkowe liczby
stałoprzecinkowe
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
2
+ 5 x 10
1
+ 3 x 10
0
+ 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
(5)
Dwójkowe liczby
stałoprzecinkowe
432,321
(5)
= 4 x 5
2
+ 3 x 5
1
+ 2 x 5
0
+ 3 x 5
-1
+ 2 x 5
-2
+ 1 x
5
-3
432,321
(5)
= 4 x 25 + 3 x 5 + 2 x 1 + 3 x
1
/
5
+ 2 x
1
/
25
+ 1 x
1
/
125
432,321
(5)
= 100 + 15 + 2 +
3
/
5
+
2
/
25
+
1
/
125
432,321
(5)
= 117
86
/
125
432,321
(5)
= 117,688
W dowolnym systemie pozycyjnym o podstawie p
wartość liczby stałoprzecinkowej obliczamy wg wzoru:
c
n-1
...c
0
,c
-1
c
-2
...c
-m
= c
n-1
p
n-1
+ ... + c
0
p
0
+ c
-1
p
-1
+ c
-2
p
-2
+ ... +c
-m
p
-m
gdzie n - liczba cyfr przed przecinkiem, m - liczba cyfr
po przecinku
Dwójkowe liczby
stałoprzecinkowe
Obliczymy wartość dwójkowej liczby
stałoprzecinkowej 1101,1011
(2)
1101,1011
(2)
= 1 x 2
3
+ 1 x 2
2
+ 0 x 2
1
+ 1 x 2
0
+ 1 x
2
-1
+ 0 x 2
-2
+ 1 x 2
-3
+ 1 x 2
-4
1101,1011
(2)
= 1 x 8 + 1 x 4 + 0 x 1 + 1 x 1 + 1 x
1
/
2
+ 0 x
1
/
4
+ 1 x
1
/
8
+ 1 x
1
/
16
1101,1011
(2)
= 8 + 4 + 1 +
1
/
2
+
1
/
8
+
1
/
16
1101,1011
(2)
= 13 +
10
/
16
1101,1011
(2)
= 13,625
Liczby stałoprzecinkowe -
zadania
Zadanie 1
Oblicz wartość następujących liczb w systemie
dziesiętnym:
1234
(5)
, 3456
(7)
, 5678
(9)
110011
(2)
, 1110111
(2)
, 11001110011
(2)
1100111,011101
(2)
Operacje
arytmetyczne
Dodawanie
dwójkowe
Dodawanie dwójkowe
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ęć.
Dodawanie dwójkowe
1101 13
+ 0010 +2
1111 15
0101 5
+ 0111 +7
1100 12
1001 9
+ 0011
+
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
).
1010 10
+ 0110
+
6
1
0000
16
Dodawanie dwójkowe
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.
Dodawanie dwójkowe
stałoprzecinkowe
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 3,375
+ 0111,110 + 7,750
1011,001
11,125
Odejmowanie
dwójkowe
Odejmowanie dwójkowe
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.
Odejmowanie dwójkowe
1111 15
- 0111 -7
1000 8
1011
11
- 0101 -5
0110 6
1101 13
+ 0011 +3
1010 10
0011 3
- 0100
-4
...11
11
11
-1
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
).
Odejmowanie dwójkowe
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.
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.
Wiodące jedynki powstają w tym przypadku w
nieskończoność, co zostało zaznaczone trzema
kropeczkami na początku wyniku odejmowania.
Mnożenie
dwójkowe
Mnożenie dwójkowe
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:
Mnożenie dwójkowe
0011
3
x 0101
x 5
0011
0000
...
+ 0011
001111
15
Mnożenie dwójkowe
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:
Mnożenie dwójkowe
1011
11
x 1101 x 13
1011
1011
33
+ 1011
+
11
10001111
143
Uwagi na temat nadmiaru odnoszą się również do
mnożenia liczb binarnych.
Mnożenie dwójkowe
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
2,5
x 11,01
x
3,25
101
125
101
50
+ 101
+ 75
1000001
1000,001
8125
8,125
Dzielenie
dwójkowe
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ć.
Zadanie
Podzielimy liczbę
1110
(2)
przez
11
(2)
(14 : 3).
Dzielenie dwójkowe
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
Dzielenie dwójkowe
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
Dzielenie dwójkowe
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
Dzielenie dwójkowe
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
Dzielenie dwójkowe
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
(2)
i
resztę 10
(2)
.
Jest to wynik poprawny, gdyż 3 mieści się w 14
cztery razy i pozostaje reszta 2.
Zadanie
podzielmy liczbę
110101101
(2)
przez
111
(2)
(429
przez 7)
Dzielenie dwójkowe
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
Dzielenie dwójkowe
Odpowiedź:
110101101
(2)
:
111
(2)
=
111101
(2)
- reszta
10
(2)
(429 : 7 = 61 - reszta 2).
Zadania
Operacje arytmetyczne -
zadania
Zadanie 1
Dodaj dwie liczby ósemkowe 743
(8)
i 212
(8)
.
Zadanie 2
Wykonaj następujące dodawania binarne:
11010011101
+
10101111
11001111010
+
11111100010
111000111
+
110011001
Operacje arytmetyczne -
zadania
Zadanie 3
Wykonaj odejmowania binarne
1110011111
1
-
10101100
1101111101
0
-
1100111
11111011
1
-
11001
Zadanie 4
Wykonaj mnożenie binarne
111100
x 1011
11010
x 1011
11101
x 11001
Operacje arytmetyczne -
zadania
Zadanie 5
Wykonaj dzielenie binarne
11010011101 :
1110
11011111011 : 110
111010111 : 101
Liczby ujemne
kod-znak-moduł
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).
kod-znak-moduł
Wartość liczby obliczamy wg następującego
wzoru:
bit znaku -najstarszy bit zapisu liczby
W
M
-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
.
W
Z-M
= (1 - 2 x bit znaku) x
W
M
kod-znak-moduł
Wzór ten można również zapisać w postaci
potęgowej:
W
Z-M
= (-1)
bit znaku
x W
M
kod-znak-moduł
Załóżmy, że 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
2
+ 0 x 2
1
+ 1
x 2
0
)
(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
kod-znak-moduł
Natomiast liczba
(1 101)
(ZM)
ma wartość dziesiętną:
(1101)
(ZM)
= (1 - 2 x 1) x (1 x 2
2
+ 0 x 2
1
+ 1
x 2
0
)
(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.
Kod
U2
Kod 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).
Kod U2
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
2
, dla liczb z zakresu
od 0..999 od 1000 - 10
3
itd.
Pascalina - sumator
Pascala
Kod U2
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)
=
1
29
Odrzucamy najstarszą jedynkę i mamy wynik
29
.
Zgadza się? /Pascal też był z tego zadowolony./
Kod U2
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
1
x p
1
+ c
0
x p
0
Kod U2
Obliczmy dla przykładu wartość liczb 4 bitowych w
kodzie U2:
0101
(U2)
= 0 x (- 2
3
) + 1 x 2
2
+ 0 x 2
1
+ 1 x
2
0
0101
(U2)
= 0 x (- 8) + 1 x 4 + 0 x 2 + 1 x 1
0101
(U2)
= 0 + 4 + 1
0101
(U2)
=
5
1
101
(U2)
= 1 x (- 2
3
) + 1 x 2
2
+ 0 x 2
1
+ 1 x
2
0
1
101
(U2)
= 1 x (- 8) + 1 x 4 + 0 x 2 + 1 x 1
1
101
(U2)
= (- 8) + 4 + 1
1
101
(U2)
= - 8 + 5
1
101
(U2)
=
- 3
Kod U2
Zapamiętaj
Wartość liczby w kodzie U2 obliczamy bardzo
podobnie do wartości liczby w naturalnym kodzie
dwójkowym. Musimy tylko pamiętać, że waga
najstarszej pozycji (pozycji znakowej) jest ujemna.
Dla n bitowej liczby U2 możemy zapisać wzór:
W
U2
= c
n-1
x (- 2
n-1
) + wartość reszty liczby w
kodzie NBC
Zakres liczb w
kodzie
U2
Kod 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.
Z
U2min
= -2
n-1
Kod U2
zakres n-bitowej liczby w kodzie U2
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
3
- 1 = 8 - 1 = 7
Z
U2min
= -2
4-1
= -2
3
= -8
Dla czterech bitów Z
U2
=
<-8
,
7>
.
Obliczanie wartości
przeciwnej w kodzie
U2
Kod 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
Kod U2
Przykład
Oblicz wartość przeciwną do liczby 0011
(U2)
= 3:
Sprawdzenie
1101
(U2)
= 1 x (-2
3
) + 1 x 2
2
+ 0 x 2
1
+ 1 x 2
0
1101
(U2)
= 1 x (-8) + 1 x 4 + 0 x 2 + 1 x 1
1101
(U2)
= -8 + 4 + 1
1101
(U2)
=
-3
NOT
0011
1100
+ 0001
1101
Znajdowanie
reprezentacji liczby
w kodzie
U2
Kod 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
n
+ W. Wynik kodujemy
binarnie i otrzymujemy liczbę ujemną w kodzie
U2.
Kod 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 c
0
= 0
46 : 2 = 23i reszta c
1
= 0
23 : 2 = 11i reszta c
2
= 1
11 : 2 = 5i reszta c
3
=
1
5 : 2 = 2i reszta c
4
= 1
2 : 2 = 1i reszta c
5
= 0
1 : 2 = 0i reszta c
6
= 1
92 =
01011100
(U2)
Kod U2
Przykład
Znaleźć zapis liczby
-107
w 8 bitowym kodzie U2:
Liczba jest ujemna, więc
najpierw obliczamy jej
dopełnienie do
podstawy:
U = 2
n
+ W = 2
8
- 107 =
256 - 107 = 149
149 : 2 = 74 i reszta c
0
=
1
74 : 2 = 37 i reszta c
1
=
0
37 : 2 = 18 i reszta c
2
=
1
18 : 2 = 9 i reszta c
3
= 0
9 : 2 = 4 i reszta c
4
= 1
4 : 2 = 2 i reszta c
5
= 0
2 : 2 = 1 i reszta c
6
= 0
1 : 2 = 0 i reszta c
7
= 1
Wyrażamy 149
binarnie
-107 = 10010101
(U2)
Arytmetyka liczb w
kodzie
U2
Dodawanie i
odejmowanie
Kod 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.
5 + (-3)
2-(-3)
0101
0010
+ 1101
- 1101
1
0010
1
0101
Wynik
2
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
Kod U2 - 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.
Kod U2 - mnożenie
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)
Kod U2 - mnożenie
(-2) x 3
11111110
x 00000011
11111110
+ 11111110
10
11111010
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.
Dzielenie
Kod U2 - 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).?
Kod U2 - dzielenie
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.
Kod U2 -
reguły znaków przy dzieleniu liczb
całkowitych
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
Kod U2 - nadmiar i niedomiar
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
7
+ 0 001
+ 1
1 000
-8
Kod U2 - nadmiar i niedomiar
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
- 6
+ 1 101 + - 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.
Kod U2 - nadmiar i niedomiar
Zapamiętaj
Wystąpienie nadmiaru lub niedomiaru jest
wskazówką dla programisty, że ź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).
Kod U2
- reguły powstawania
nadmiaru/niedomiaru
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
Kod U2 - zadania
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.
Zadanie 2
Znajdź wartość przeciwną do podanych liczb w
kodzie U2:
01011101 , 11111111 ,
00000000 , 01111110 , 11110000
Kod U2 - zadania
Zadanie 3
Znajdź zapis w 8 bitowym kodzie U2
następujących wartości dziesiętnych:
-100, -48, 126
Zadanie 4
Oblicz wartość liczb stałoprzecinkowych w kodzie
U2:
1101,111
(U2)
1,1
(U2)
100,001
(U2)
Kod
BCD
Kod
BCD
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.
Kod
BCD
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
001
0
3
001
1
7
011
1
9
100
1
W efekcie otrzymujemy kod BCD tej wartości:
2379
(10)
=
0010001101111001
(BCD)
Kod
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.
Kod
BCD
01101000100100110110
(BCD)
= 0110 1000 1001 0011 0110
01101000100100110110
(BCD)
= 6 x 10
4
+ 8 x 10
3
+ 9 x 10
2
+ 3 x 10
1
+ 6 x 10
0
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
.
Kod
BCD
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).
Kod
BCD
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
(16)
= 0001011001110010
(2)
= 0001 0110 0111
0010
(BCD)
=
1672
(10)
Zapamiętaj
W systemie BCD każda cyfra dziesiętna wartości
liczby zajmuje 4 bity. Bity te przedstawiają dwójkową
wartość cyfry.
Arytmetyka w systemie BCD
Ponieważ liczby w kodzie BCD nie są naturalnymi
liczbami dwójkowymi, zatem nie można na nich
wykonywać normalnych działań arytmetycznych.
15 + 35
24 -15
0001 0101
0010 0100
+ 0011 0101
- 0001 0101
0100 1010
0000 1111
Wynik nie
BCD!
Wynik nie
BCD!
gr1
Arytmetyka w systemie 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).
Arytmetyka w systemie BCD
Sprawdźmy ponownie (kolorem czerwonym
zaznaczono korekcję wyniku):
15 + 35
24 -15
0001 0101
0010 0100
+ 0011 0101
- 0001 0101
0100
1010
0000
1111
+ 0000
0110
- 0000
0110
0101 0000
0000 1001
Wynik = 50
Wynik = 9
Arytmetyka w systemie BCD
Korekcja musi również wystąpić, gdy w trakcie
dodawania wystąpiło przeniesienie (przy
odejmowaniu pożyczka) do sąsiedniej grupy bitów.
29 + 19
31 -18
0010 1001
0011 0001
+ 0001 1001
- 0001 1000
010
0
0010
000
1
1001
+ 0000
0110
- 0000
0110
0100 1000
0001 0011
Wynik = 48
Wynik = 13
Arytmetyka w systemie BCD
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
Kod
Gray’a
Kod
Gray’a
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, że 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
Gray’a
Kod
Wychylenie
000
0°
001
10°
010
20°
011
30°
100
40°
101
50°
110
60°
111
70°
Kod
Gray’a
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,
że 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°.
Kod
Gray’a
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
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.
Kod
Gray’a
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, że 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ę.
Kod
Gray’a
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ść, że kolejne wyrazy różnią się
między sobą wartością tylko jednego bitu.
Kod
Gray’a
Kod
Gray’a
Wychylen
ie
000
0°
001
10°
010
20°
011
30°
100
40°
101
50°
110
60°
111
70°
Teraz poprzednio
opisany problem nie
wystąpi, ponieważ
przejście z kodu 011
dla
30°
na 100 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.
Gr
1
Kod
Gray’a
Zapamiętaj
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.
Liczby
zmiennoprzecink
owe
Liczby zmiennoprzecinkowe
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.
Liczby zmiennoprzecinkowe
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.
Liczby zmiennoprzecinkowe
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ć:
rok świetlny ≈ 9,45 x 10
15
[m]
Liczby zmiennoprzecinkowe
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
Liczby zmiennoprzecinkowe
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.
Liczby zmiennoprzecinkowe
Obliczmy dla przykładu wartość liczby
zmiennoprzecinkowej zapisanej w systemie
czwórkowym: (3,21 x 10
12
)
(4)
.
Przy obliczaniu tego typu wartości musimy
pamiętać, że wszystkie trzy elementy są zapisane
w systemie o podstawie p (równej 4).
m = 3,21
(4)
m = 3 x 4
0
+ 2 x 4
-1
+ 1 x 4
-2
m = 3 x 1 + 2 x
1
/
4
+ 1 x
1
/
16
m = 3 +
2
/
4
+
1
/
16
m = 3
9
/
16
Liczby zmiennoprzecinkowe
p = 10
(4)
p = 1 x 4
1
+ 0 x 4
0
p = 1 x 4 + 0 x 1
p = 4
w = 12
(4)
w = 1 x 4
1
+ 2 x 4
0
w = 1 x 4 + 2 x 1
w = 4 + 2
w = 6
(3,21 x 10
12
)
(4)
=
3
9
/
16
x
4
6
= 14592
(10)
Liczby zmiennoprzecinkowe
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:
W
FP
= m x p
w
Uwaga:
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
Liczby zmiennoprzecinkowe
Pierwszą, charakterystyczną cechą liczb
zmiennoprzecinkowych jest niejednoznaczność
zapisu wartości liczby.
9,45 x 10
15
=
94,5 x 10
14
=
0,945 x
10
16
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).
Operacje
logiczne
UKŁADY
KOMBINACYJNE
UKŁADY KOMBINACYJNE
Układami
kombinacyjnymi
nazywamy te elementy techniki
cyfrowej,
dla
których
dana
kombinacja
stanów
wejściowych
(argumentów funkcji) określa w
sposób jednoznaczny kombinację
sygnałów wyjściowych. Należą do
nich:
•
bramki
•
kodery i dekodery
•
multipleksery i demultipleksery
Funktory logiczne (bramki).
Podstawowe bramki spełniają wszystkie podstawowe
funkcje algebry Boole’a oraz dodatkowe, ułatwiające
syntezę układów. Należą do nich:
A
Y
0
1
1
0
A
Y
BRAMKA NOT (NIE)
Tabela prawdy
Funktory logiczne (bramki).
A
B
Y
0
0
0
0
1
0
1
0
0
1
1
1
BRAMKA AND (I)
Tabela prawdy
Y
A
B
W obwodzie tym tylko przy zwarciu obu kluczy A i B
(stan A=1 i B=1 na "wejściu") świeci się żarówka
oznaczająca stan F=1 "na wyjściu"
Funktory logiczne (bramki).
Tablice stanów prawdy nie są ograniczone tylko do
dwóch zmiennych, tych zmiennych może być
więcej. Rozważmy pewien układ cyfrowy o trzech
wejściach A,B,C i wyjściu F. Tablica (stanów) prawdy
dla tego układu ma postać.
Nr
wiersz
a
A B C F
0
0 0
0 0
1
0 0
1 1
2
0 1
0 1
3
0 1
1 1
4
1 0
0 0
5
1 0
1 1
6
1 1
0 1
7
1 1
1 1
Każdej zmiennej wejściowej
A,B,C i wyjściowej F jest
przyporządkowana w tablicy
stanów osobna kolumna,
a każdemu stanowi układu
osobny wiersz.
Liczba wierszy zależy od liczby zmiennych
wejściowych. Zgodnie z kombinatoryką przy n-
dwustanowych zmiennych wejściowych tablica
zawiera
wierszy;
w naszym przypadku wierszy.
Funktory logiczne (bramki).
Tablica stanów (prawdy) służy również do
stwierdzenia czy dane wyrażenie jest tautologią -
prawem logicznym, tzn. czy jest prawdziwe dla
dowolnych
wartości
(0,1)
zmiennych
występujących w tym wyrażeniu.
Funktory logiczne (bramki).
Przykład
-
umieszczonego
w
tabeli
prawa
rozdzielczości iloczynu względem sumy, czyli:
A*(B+C) = A*B+A*C
A B C B+C
A*(B+C)
A*B
A*C
A*B+A*C
0
0 0
0
0
0
0
0
0
0 1
1
0
0
0
0
0
1 0
1
0
0
0
0
0
1 1
1
0
0
0
0
1
0 0
0
0
0
0
0
1
0 1
1
1
0
1
1
1
1 0
1
1
1
0
1
1
1 1
1
1
1
1
1
Funktory logiczne (bramki).
Y
B
A
BRAMKA OR (LUB)
Tabela prawdy
A
B
Y
0
0
0
0
1
1
1
0
1
1
1
1
Funktory logiczne (bramki).
A
B
Y
0
0
1
0
1
1
1
0
1
1
1
0
BRAMKA NAND (NIE-I)
Tabela
prawdy
BRAMKA NOR (NIE-
LUB)
Tabela prawdy
A
B
Y
0
0
1
0
1
0
1
0
0
1
1
0
Y
B
A
Y
B
A
Funktory logiczne (bramki).
A
B
Y
0
0
0
0
1
1
1
0
1
1
1
0
BRAMKA XOR (ALBO)
Tabela prawdy
Y
B
A
Funktory logiczne (bramki).
Za pomocą odpowiednich połączeń bramek można
zrealizować każdą funkcję np.:
D
C
B
A
B
A
Y
Y=A*(#A+#B)+B*C+#D
A
B
C
D
na schematach negację argumentu można oznaczać #
#A
#B
#A+#B
A*(#A+#B)
B
C
B*C
#D
#D+B*C