1. i

Report
Architektura systemów komputerowych
(zima 2014)
Wykład 1 (cz. 2)
Reprezentacja danych w komputerze
dr inż. Wojciech Bieniecki
Instytut Nauk Ekonomicznych
i Informatyki
http://wbieniec.kis.p.lodz.pl/pwsz
Kodowanie
Kodowanie informacji jest to przedstawienie informacji w postaci
komunikatu zrozumiałego przez odbiorcę .
Do kodowania używamy określonego zbioru, np. cyfr, znaków,
impulsów.
Kodowanie binarne każdemu elementowi alfabetu
przyporządkowuje ciąg binarny
(np. a -> 0001, b -> 0010, itd. )
Inaczej K(a)=0001, K(b)=0010, gdzie K to kod.
Słowo kodowe
Jeś li K(a)=0001, to 0001 jest słowem kodowym a.
2
Idea działania układów cyfrowych
W układach cyfrowych wszelka informacja i wszelkie wielkości przetwarzane przez
te układy reprezentowane są przez dwa stany.
stan niski (L), nazywany też poziomem logicznym niskim lub zerem (0)
stan wysoki (H), nazywany też poziomem logicznym wysokim lub jedynką (1)
W praktycznej realizacji układów cyfrowych należy określić jakie wartości lub
zakresy wartości oznaczają poziom logiczny niski lub wysoki
bit – podstawowa, najmniejsza i niepodzielna jednostka informacji cyfrowej, jaka
może być przetwarzana przez komputer
bit może przechowywać informację o jednym z dwóch możliwych stanów –
przyjmuje wartości oznaczane jako 0 albo 1
bit to skrót terminu binary digit. bit to po angielsku kawałek – skrót: b
3
Działanie układu cyfrowego
Klucz może być realizowany przez tranzystor
4
Algebra Boola
5
Podstawowe bramki logiczne
6
Proste kombinacje bramek
Realizujemy jako
lub
Realizujemy jako
Bardziej złożone bramki to półsumator, sumator, multiplekser
– przy okazji dodawania
7
Własności algebry Boola
8
Upraszczanie układu
kombinacyjnego
x = ¬ (¬(a¬b)  ¬b)
Prawo de Morgana
x =¬ ¬ ((a¬b) ¬¬b)
Podwójna negacja
x = (a¬b)  b
Rozdzielność
x = (a  b)^(¬b  b)
x = (a  b) ^ 1
x=a b
9
Dlaczego komputery przetwarzają
bity?
Bity są odporne na zakłócenia - w czasie przekazu należy wykryć
tylko dwa poziomy, wysoki H - 1 i niski L - 0.
Brak wartości pośrednich.
W przypadku innych jednostek sygnał musi mieć więcej poziomów,
a więc jest bardziej podatny na przekłamania w trakcie transmisji.
Binarny system pozycyjny da się bezpośrednio zakodować w postaci
bito w - każdej cyfrze binarnej odpowiada jeden bit (na bitach
można wykonywać dowolne operacje arytmetyczne, a więc liczyć )
10
Nazewnictwo
1 bit: 0, 1, rozróżnia 2 znaki
2 bity: 00, 01, 10, 11, rozróżniają 4 znaki.
3 bity: 000, 001, 010, 011, 100, 101, 110, 111, rozróżniają 8 znaków.
4 bity: 0000 ... 1111, rozróżniają 16 znaków (tetrada)
8 bitów pozwala odróżnić 28 = 16 x 16 = 256 znaków
Cztery bity to tetrada (kęs) ang. nibble
Osiem bitów tworzy tzw. oktet zwany również bajtem (B)
Dwa bajty to półsłowo.
Cztery bajty (32 bity) to słowo.
64 bity to podwójne słowo.
Słowo komputerowe to ilość informacji przetwarzanej przez procesor jako
całość.
11
Jednostki informacji
W informatyce nazwy przedrostków nie odpowiadają tym w układzie SI
kilo = 1000= 103
mega = 1000000= 106= kilo x 1000
giga = 1000000000= 109= mega x 1000
tera = 1000000000000 = 1012 = giga x 1000
210=1024=1K
kilobajt, typowa strona tekstu to kilka KB;
220=1024K=1M
megabajt, książka bez grafiki lub minuta muzyki;
230=1024M=1G gigabajt, film cyfrowy, sporo grafiki, ludzki genom;
240=1024G=1T
terabajt, duża biblioteka, szerokoekranowy film w kinie;
250=1024T=1P
petabajt, ludzka pamięć;
12
System liczbowy
Jest to zbiór reguł do jednolitego zapisywania i nazywania cyfr.
Rozróżniamy systemy addytywne i pozycyjne
Systemy addytywne Posiadają osobne symbole dla pierwszych kilku małych liczb,
a następnie posiadają kolejne symbole dla ich wielokrotności. W systemach tych
liczby tworzy się przez "dodawanie” kolejnych symboli i stąd ich nazwa
Przykład cyfry rzymskie
Jeśli "X"=10,"V"=5,"I"=1 to XVI = 10+5+1 = 16
System pozycyjny to taki, w którym znaczenie znaków zależy od ich pozycji.
System wagowy to taki, w którym dla każdej pozycji cyfry przypisana jest inna
waga.
W systemie pozycyjno-wagowym liczbę przedstawia się jako ciąg cyfr, przy czym
wartość tej liczby zależy zarówno od cyfr jak i miejsca, na którym znajdują się one
w tym ciągu
Przykład Liczba 5004 w dziesiętnym systemie liczbowym, w którym podstawą
pozycji jest 10 wyliczamy 5 x 103 + 0 x 102 + 0 x 101 + 4 x 100
13
System liczbowy pozycyjno-wagowy
Liczbę całkowitą L w systemie pozycyjnym o podstawie (bazie) r zapisujemy w
postaci:
 a n 1 a n  2  a1 a 0 
Unikalną reprezentacją liczby o wartości L jest zbiór cyfr takich, że
P - podstawa systemu
a – kolejne cyfry w liczbie
i – indeks kolejnych cyfr
n 1
L

a P
i
i
i0
System dziesiętny
System dwójkowy (binarny)
Podstawę systemu dziesiętnego tworzy liczba 10.
Podstawę systemu binarnego tworzy liczba 2.
Zapis liczby tworzymy za pomocą cyfr o
przypisanych wartościach od 0 do 9.
Zapis liczby tworzymy za pomocą cyfr o
przypisanych wartościach 0 i 1.
Przykład
126(10) = 1x102 + 2x101 + 6x100
Przykład
1010(2) = 1x23 + 0x22 + 1x21+ 0x20 = 8 + 2 = 10(10)
14
Kod binarny prosty
Kodem danego zbioru symboli nazywa się przyporządkowanie każdemu symbolowi tego
zbioru jednego i tylko jednego wektora cyfrowej reprezentacji. Jeżeli jest to
przyporządkowanie wzajemnie jednoznaczne to kod nazywamy szyfrem.
Kod binarny prosty to pozycyjny system liczbowy, w którym podstawą pozycji są kolejne
potęgi liczby 2. Do zapisu liczb potrzebne są tylko dwa znaki: 0 i 1. Powszechnie używany w
informatyce. Jak w każdym pozycyjnym systemie liczbowym, liczby zapisuje się tu jako ciąg
cyfr, z których każda jest mnożnikiem kolejnej potęgi liczby stanowiącej podstawę systemu.
Przyporządkowuje dziesiętnym liczbom całkowitym bez znaku n-bitowe liczby dwójkowe.
n
2n
X (10 )  a n 1 a n  2 ... a 2 a1 a 0
a i  0 ,1
0
1
Gdzie
1
2
przy czym:
2
4
n 1
3
8
n 1
1
0
i
X (10 )  a n 1 2
 ...  a1 2  a 0 2 
ai 2
4
16
5
32
i0
n
6
64
0  X (10 )  2  1
Zakres wartości:
7
128
8
256
9
512
15
10
1024

Konwersja z systemu dziesiętnego
na system dwójkowy
Realizacja
algorytmiczna
w - wartość liczby w systemie
dziesiętnym
p - podstawa nowego systemu
pozycyjnego
ci - cyfra na i-tej pozycji w systemie
pozycyjnym o podstawie p
1. i := 0
2. ci = w mod p
3. w := w div p
4. jeśli w == 0 to koniec
Zapis liczby 172(10) w systemie dwójkowym:
(dzielimy na dwa i zapisujemy resztę)
172
86
43
21
10
5
2
1
0
0
1
1
0
1
0
1
Najmniej znaczący bit 20
Najbardziej znaczący bit 2n
5. inc(i)
6. goto 2
7. koniec
16
Dodawanie liczb binarnych
Do wykonywania dodawania
niezbędna jest znajomość tabliczki
dodawania, czyli wyników
sumowania każdej cyfry z każdą inną:
0101 = 5(10)
1100 =12(10)
+ 0110 = 6(10)
+ 0011 = 3(10)
1011 =11(10)
1111 =15(10)
0
0
1
1
+
+
+
+
0
1
0
1
=
=
=
=
0
1
1
10
1010 = 10(10)
+
1010 = 10(10)
10100 = 20(10)
1111 =15(10)
+
0001 = 1(10)
10000 =16(10)
Problem
W pamięci komputera liczby binarne przechowywane są w postaci ustalonej ilości bitów
(np. 8, 16, 32 bity).
Jeśli wynik sumowania np. liczb 8 bitowych jest większy niż 8 bitów, to najstarszy bit
(dziewiąty) zostanie utracony.
Sytuacja taka nazywa się nadmiarem (ang. overflow)
17
Sprzętowa realizacja dodawania
Półsumator (Half-Adder)
Sumator (full-adder)
Tablica prawdy
18
Odejmowanie liczb binarnych
Przy odejmowaniu
korzystamy z tabliczki
odejmowania:
0
0
1
1
-
0
1
0
1
=
=
=
=
0
1 i pożyczka z następnej pozycji
1
0
Pożyczka oznacza konieczność odjęcia 1 od wyniku odejmowania cyfr w następnej
kolumnie.
problem
11111
Jeśli od liczby mniejszej odejmiemy
1101110 = 110(10)
-0001111 = 15(10)
1011111 = 95(10)
większą , to wynik będzie ujemny.
11111111
00000000
- 00000001
11111111
Otrzymujemy same
jedynki, a pożyczka
nigdy nie zanika.
Sytuacja taka nazywa
się niedomiarem
(ang. underflow)
19
Inne kody liczbowe
Ósemkowy system liczbowy inaczej oktalny to pozycyjny system liczbowy o
podstawie 8. Do zapisu liczb używa się w nim ośmiu cyfr, od 0 do 7.
Przykład:
1x82 + 4x81 + 4x80 = 64 + 32 + 4 = 100.
Zatem 144(8) = 100(10).
Szesnastkowy system liczbowy, hexadecymalny. Poza cyframi dziesiętnymi od 0 do 9
używa się pierwszych sześciu liter alfabetu łacińskiego: A, B, C, D, E, F.
Przykład
liczba zapisana w dziesiętnym systemie liczbowym jako 1000, w kodzie szesnastkowym
przybiera postać 3E8, gdyż:
3x162 + 14x161 + 8x160 = 768 + 224 + 8 = 1000.
Hex jest powszechnie używany w informatyce, ponieważ wartość pojedynczego bajtu
można opisać używając tylko dwóch cyfr szesnastkowych.
W ten sposób można kolejne bajty łatwo przedstawić w postaci ciągu liczb hex.
Jednocześnie zapis 4 bitów można łatwo przełożyć na jedną cyfrę hex.
20
Inne kody liczbowe
Kod dwójkowo-dziesiętny (BCD – ang. Binary-Coded Decimal) –
przyporządkowuje cyfrom od 0 do 9 czterobitowe ciągi
Zastosowanie: tam, gdzie ważna jest
prostota, np. kalkulator.
Zalety: łatwość konwersji
(przekształcanie z postaci znakowej w
postać obliczeniową i odwrotnie).
Wady kodu: mało efektywne
wykorzystanie pamięci, złożoność
realizacji operacji arytmetycznych
(wymagana korekcja wyniku).
Kod BCD spakowany – można przedstawić liczby z zakresu (0..99).
2-cyfrowa liczba dziesiętna bez znaku ma postać 8-bitowego ciągu.
21
Operacje w BCD
Dodawanie w BCD
Dodawanie w BCD realizujemy poprzez wykonanie binarnego dodawania a
następnie poprzez konwersję wyniku z powrotem do BCD. Konwersja polega na
dodaniu do wyniku 6 wówczas, gdy jest on większy niż 9. Przykład:
1001 + 1000 = 10001 = 0001 0001
9 +
8 =
17 =
1
1
W BCD nie istnieje wartość większa niż 9 (1001) dla jednego kęsu.
Korekta polega na dodaniu 6 (0110) do obliczonej sumy:
0001 0001 + 0000 0110 = 0001 0111
1
1 +
0
6 =
1
7
Otrzymujemy dwa kęsy 0001 oraz 0111,odpowiadające cyfrom "1" i "7".
22
Kodowanie dwójkowe liczb
całkowitych ze znakiem
ZNAK-MODUŁ – polega na przeznaczeniu najstarszego bitu (MSB) na znak, reszta
reprezentuje moduł liczby.
Obliczenia są niewygodne, odejmowanie różni się od dodawania (dodawanie nie działa
na liczbach ze znakiem).
Dodatkowo występuje podwójna reprezentacja zera.
ZAPIS BINARNY PRZESUNIĘTY. Aby otrzymać reprezentowaną wartość, odejmuje się od
niej połowę największej liczby.
Zaleta – kody liczb od najmniejszej ujemnej do największej dodatniej tworzą zwykły
binarny ciąg arytmetyczny, opowiadający trybowi pracy liczników dwójkowych.
ZAPIS Z UZUPEŁNIENIEM DO DWÓCH – liczby dodatnie są reprezentowane przez zwykłe
liczy binarne bez znaku.
Liczbę ujemną reprezentuje liczba binarna którą trzeba dodać do liczby dodatniej (0
zastępujemy przez 1, 1 zastępujmy przez 0), co jest nazywane uzupełnieniem do jedynki, a
następnie należy postąpić zgodnie z uzupełnieniem do 2, czyli do liczby w kodzie U1
dodajemy +1.
Najstarszy bit liczby ujemnej w kodzie U2 jest 1.
23
Kod U1
Uzupełnienie do -1
Jest to uzupełnienie n-cyfrowej liczby N o podstawie  do -1. Jest zdefiniowane
jako
(n – 1) - N
Przykład:
Uzupełnieniem liczby (53412)10 jest
(n – 1) – N = (105 – 1) – 53412 = 45687
Uzupełnieniem liczby (1010101)2 jest
(n – 1) – N = (27)10 – 1 – (1010101)2 = (128-1-85)10 = (42)10 = (0101010)U1 = (0101010)U1
Uzupełnienie liczby binarnej do 1 otrzymujemy poprzez odjęcie każdej jej cyfry od
1 lub inaczej mówiąc – zanegowanie danej cyfry.
Np. uzupełnieniem do 1 liczby (11001110101)2 jest liczba
(00110001010)U1 = (00110001010)U1
24
Kod U2
Uzupełnienie do n-cyfrowej liczby N. , jest zdefiniowane jako
n - N
(n – 1) – N = ((n – 1) – N) + 1
Przykład:
Dla = 2 uzupełnienie do dwu jest równe (n-bitowa liczba) U1 +1
(100011010101)2 uzupełnienie do 1: (n – 1) – N =
(011100101010)U1 uzupełnienie do 2 (n – N)
= ((n – 1) – N) + 1 = U1+1 = (011100101010)U1 +1 = (011100101011)U2
25
Przykłady liczb całkowitych ze znakiem
Liczba całkowita
Znak – moduł
+7
+6
+5
+4
+3
+2
+1
0
-1
-2
-3
-4
-5
-6
-7
-8
-(0)
0111
0110
0101
0100
0011
0010
0001
0000
1001
1010
1011
1100
1101
1110
1111
1000
Binarny
przesunięty
1111
1110
1101
1100
1011
1010
1001
1000
0111
1001
0101
0100
0011
0010
0001
0000
-
U2
0111
0110
0101
0100
0011
0010
0001
0000
1111
1110
1101
1100
1011
1010
1001
1000
-
26
Operacje arytmetyczne w U2
Aby dodać dwie liczby: M=+5, N=-2, dodajemy je bit po bicie z przeniesieniem w sposób następujący
0000 0101 = +5 (0000 0010)2 = 2 (1111 1101)U1 = (1111 1110)U2= -2
+1111 1110
---------0000 0011 = +3, C = 1
Aby wykonać odejmowanie 2-5, należy wziąć U2 liczby 5 i dodać do 2:
0000 0010 = +2 (0000 0101)2 = 5 (1111 1010)U1 = (1111 1011)U2= -5
+1111 1011
---------1111 1101 = -3, C = 0
27
Przesunięcie i rotacja
SHL (shift left)
ROL (rotate left)
SHR (shift right)
ASR (arithmentic shift right)
28
Mnożenie i dzielenie przez 2
Mnożenie i dzielenie dobrze działa w zapisie U2. W tym formacie operacje wykonuje się w
sposób naturalny.
Mnożenie przez 2 jest równoważne arytmetycznemu przesunięciu w lewo o jeden bit. Na
najmniej znaczącej pozycji wstawiamy 0. W razie przekroczenia zakresu może pojawić się
nadmiar.
(2)10
= (0010)U2 * 2 = (0100)U2 = (4)10
(-2)10 = (1110)U2 * 2 = (1100)U2 = (-4)10
Jeżeli w wyniku przesunięcia znak liczby (najbardziej znaczący bit) nie ulegnie zmianie, to
przesunięcie w lewo poprawnie realizuje mnożenie przez 2.
(-6)10 = (1010)U2 * 2 = (0100)U2 = (4)10 ??
Wystąpił nadmiar i wynik jest błędny. Wynika to z faktu, że zwiększyliśmy wartość liczby tak
bardzo, że przekroczyła ona zakres liczb możliwych do wyrażenia w danym słowie. Weźmy
dłuższe słowo:
(-6)10 = (11010)U2 * 2 = (10100)U2 = (-12)10 OK.!
29
Dzielenie przez 2
Dzielenie przez 2 wykonujemy przy użyciu arytmetycznego przesunięcia w
prawo.
Polega ono na powieleniu najstarszego bitu. Operacja ta jest zawsze możliwa do
wykonania – nie powoduje błędów.
(6)10 = (0110)U2 : 2 = (0011)U2 = (3)10
Dzieląc liczbę ujemną musimy na najstarszym bicie dopisać jedynkę a nie zero –
stąd nie korzystamy z SHR
(-6)10 = (1010)U2 : 2 = (1101)U2 = (-3)10
Uwaga – przy przesuwaniu w prawo może nastąpić utrata dokładności.
(7)10 = (0111)U2 : 2 = (0011)U2 = (3)10
30
Formaty liczb całkowitych w
procesorze
Liczby całkowite ze znakiem są zawsze zapisywane w kodzie U2.
Używa się do tego celu 8, 16, 32 lub 64 bitów.
Zawsze najbardziej znaczący bit jest używany do określenia znaku.
Liczba Zakres
bajtów dolny
Zakres
górny
Nazwa typu
Zakres bez
znaku
Nazwa typu
1
-128
127
char
0 - 255
byte, unsigned char
2
-32768
32767
short
0 - 65535
word,unsigned short
4
-231
231 - 1
Int, integer
0 -232 - 1
dword, unsigned int
8
-263
263 - 1
long int
0 - 264 - 1
qword, unsigned long
31

similar documents