Wydział Inżynierii Materiałowej i Ceramiki AGH

Katedra Chemii Analitycznej

Kodowanie informacji w systemach cyfrowych

Instrukcja do ćwiczenia z przedmiotu Komputery w pracach eksperymentalnych

Opracowanie:

dr Małgorzata Jakubowska

Kraków 2002

Wstęp

W pracach eksperymentalnych analizujemy najczęściej sygnały zmieniające się w sposób ciągły (np. potencjał elektrody, prąd fotoogniwa) ale także dyskretny (np. energia elektronu w atomie). Wielkość tych sygnałów dostarcza nam informacji. Informacją jest każdy czynnik zmniejszający stopień niewiedzy o badanym zjawisku czy obiekcie Przetwarzanie sygnałów odbywa się z zastosowaniem techniki analogowej lub cyfrowej. W systemach cyfrowych wejściowa informacja analogowa musi być przekształcona do takiej postaci, aby system ten mógł z niej skorzystać i poddać dalszemu procesowi przetwarzania. System cyfrowy, w tym m.in. komputer gromadzi i przetwarza informację zapisaną wyłącznie w postaci liczbowej, w systemie dwójkowym. Ponieważ w systemie dwójkowym do dyspozycji mamy tylko dwa znaki - umownie oznaczane przez 0 i 1 - w związku z tym jedynie przy ich użyciu można zapisać każdą informację. Najczęściej zapis taki składa się z wielu pozycji, z których każda nazywana jest bitem i może przyjmować wartości z podanego zbioru {0, 1}.

Podstawą zrozumienia zapisu informacji w systemie cyfrowym jest umiejętność przekodowania jej z systemów zwyczajowo używanych (np. systemu dziesiętnego) na postać binarną. Poniższe rozważania przedstawiają krótko teorię liczbowych systemów pozycyjnych oraz praktyczne zagadnienia konwersji i obliczeń w systemach o podstawie 2, 8 oraz 16.

Liczbowe systemy pozycyjne

Niech p oznacza podstawę systemu liczbowego. Dowolną liczbę l_p w systemie o podstawie p można ogólnie przedstawić w postaci:

,

gdzie a_i oznacza cyfry od 0 do p-1, zaś ...p^-2, p^-1, p⁰, p¹, p²... - wagi, przyporządkowane każdej pozycji. W powyższym zapisie zmienna n wskazuje na liczbę cyfr przed przecinkiem, natomiast m - liczbę cyfr po przecinku. Pozycje odpowiadające potęgom nieujemnym oddzielone są przecinkiem (lub kropką) od pozycji odpowiadających ujemnym potęgom podstawy.

Liczbę l_p w systemie pozycyjnym o podstawie p można w skrócie zapisać jako:

.

Przykładowo w systemie dziesiątkowym:

p = 10 a_i ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, np. 99,123;

w systemie ósemkowym:

p = 8 a_i ∈ {0, 1, 2, 3, 4, 5, 6, 7}, np. 77,45 O;

w systemie dwójkowym:

p = 2 a_i ∈ {0, 1}, np. 101,01 B;

w systemie heksadecymalnym:

p = 16 a_i ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}, np. 7A,C3C H.

W systemie szesnastkowym brakujące cyfry uzupełniono pierwszymi literami alfabetu, i tak A oznacza cyfrę 10, B - 11, C - 12, D - 13, E - 14, F - 15. Listę cyfr oraz odpowiadających im liczb w systemie dziesiętnym i binarnym prezentuje tabela 1.

Heksadecymalny system pozycyjny	Dziesiętny system pozycyjny	Binarny system pozycyjny
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

Tabela 1. Cyfry w systemie heksadecymalnym i odpowiadające im liczby w systemie dziesiętnym i binarnym.

W systemie heksadecymalnym stosowana jest konwencja wymagająca rozpoczynania zapisu liczby od cyfry dziesiątkowej. W przypadku gdy zapis szestastkowy zaczyna się od litery - dodaje się na początku zero, które nie zmienia wartości liczby.

Aby uniknąć nieporozumień w zapisie liczb dopisuje się na końcu literę B dla określenia systemu binarnego, O - oktalnego, zaś H - dla heksadecymalnego.

Konwersja

Podstawowym problemem przy stosowaniu różnych systemów liczbowych jest przejście z jednego systemu na drugi.

Konwersję binarno - dziesiętną prowadzimy korzystając bezpośrednio z definicji, np.:

10011 B = 1∗2⁰ + 1∗2¹ + 0∗2² + 0∗2³ + 1∗2⁴ = 1 + 2 + 16 = 19

Operacja sprowadza się do zsumowania wag pozycji, na których występuje cyfra 1. W przypadku systemu ósemkowego lub szesnastkowego wagi poszczególnych pozycji należy pomnożyć przez cyfrę występującą na tej pozycji, np.:

2AC H = 12∗16⁰ + 10∗16¹ + 2∗16² = 12 + 160 + 512 = 684

Przejście z systemu dziesiątkowego na inny tą metodą nie jest praktyczne, ponieważ wymaga stosowania wag wyrażonych w nowym systemie, a zatem wykonywania działań w nowym systemie. Istnieje jednak prostszy sposób. Napiszmy jeszcze raz definicję:

.

Następnie cześć odpowiadającą ujemnym potęgom podstawy pomnóżmy przez p, natomiast pozostałą część podzielmy przez p. Otrzymamy wówczas:

.

W powyższym zapisie
jest pierwszą cyfrą po przecinku w szukanej liczbie, natomiast
jest resztą z dzielenia i odpowiada pierwszej cyfrze przed przecinkiem. Postępując tak dalej otrzymujemy cyfry przed i po przecinku. Np. poszukujemy binarnego zapisu liczby dziesiętnej 43,75:

43 : 2 = 21 reszta 1 0,75 ∗ 2 = 1,5 część całkowita 1

21 : 2 = 10 reszta 1 0,5 ∗ 2 = 1 część całkowita 1

10 : 2 = 5 reszta 0

5 : 2 = 2 reszta 1

2 : 2 = 1 reszta 0

1 : 2 = 0 reszta 1

A zatem poszukiwana liczba to 101011,11 B.

Znacznie łatwiejsza jest zamiana pomiędzy systemami, których podstawy są swoimi całkowitymi potęgami. Wtedy konwersja polega na łączeniu cyfr w grupy o stałej długości i zamianie wewnątrz każdej grupy. Przykładowo prowadząc konwersję binarno - heksadecymalną rozbijamy liczby na czteroznakowe fragmenty:

101110001001101 B = (0101) (1100) (0100) (1101) B

a następnie posługując się tabelą 1 przypisujemy każdej czwórce odpowiadającą jej cyfrę heksadecymalną:

(0101) (1100) (0100) (1101) B = 5C4D H

W powyższym przykładzie dodano na początku zero, by dopełnić ostatni fragment do pełnej czwórki (co nie zmienia wartości samej liczby). Podobnie postępujemy chcąc zamienić liczbę z systemu szesnastkowego na system dwójkowy: każdą cyfrę szesnastkową zamieniamy na ciąg czterech zer lub jedynek. Konwersja z zapisu binarnego na oktalny polega na dzieleniu liczby na grupy zawierające po trzy cyfry. Każdą trójkę cyfr systemu binarnego zastępujemy jedną cyfrą systemu ósemkowego. Np. :

110001011 B = (110) (001) (011) B = 613 O

Dwójkowy (binarny) system pozycyjny

W dwójkowym systemie pozycyjnym podstawa p wynosi 2, zaś cyfry należą do zbioru {0, 1}. Działania arytmetyczne w systemie dwójkowym wykonuje się podobnie jak systemie dziesiątkowym. Tabele 2, 3 oraz 4 przedstawiają reguły arytmetyki binarnej.

	Suma	Przeniesienie
0+0	0	0
0+1	1	0
1+0	1	0
1+1	0	1

Tabela 2. Reguły dodawania dwójkowego.

	Różnica	Pożyczka
0−0	0	0
0−1	1	1
1−0	1	0
1−1	0	0

Tabela 3. Reguły odejmowania dwójkowego.

	Iloczyn
0x0	0
0x1	0
1x0	0
1x1	1

Tabela 4. Reguły mnożenia dwójkowego.

Reprezentacja informacji w systemie cyfrowym

Reprezentacja liczb całkowitych

Liczby całkowite mogą być przechowywane w systemach cyfrowych na wiele róznych sposobów. Najczęściej do tego celu wykorzystywane sa kody: BCD, kod uzupełnieniwy do dwóch lub kod znak - moduł.

Kod BCD

Kod dwójkowo - dziesiętny BCD (Binary Coded Decimal) służy do przedstawiania liczb całkowitych bez znaku. W kodzie tym każda cyfra dziesiętna jest zakodowana dwójkowo na 4 bitach, według reguł kodowania binarnego (tabela 5).

Cyfra dziesiętna	Kod BCD
0	0000
1	0001
2	0010
3	0011
4	0100
5	0101
6	0110
7	0111
8	1000
9	1001

Tabela 5. Kody BCD dla poszczególnych cyfr dziesiętnych.

Kod uzupełnieniowy do dwóch

Kod uzupełnieniowy do dwóch służy do kodowania liczb całkowitych ze znakiem. Kodów uzupełnieniowych o różnych podstawach używa się w celu uproszczenia operacji odejmowania.

Cechy kodu:

• do przedstawienia n - bitowej liczby binarnej z uwzględnieniem jej znaku potrzeba n+1 bitów

• liczby dodatnie zapisywane są w naturalnym kodzie binarnym

• najstarszy bit reprezantacji binarnej jest bitem znaku

• znak "+" reprezentowany jest przez 0, znak "-" przez 1

• liczba ujemna jest arytmetycznym uzupełnieniem liczby dodatniej o tej samej wartości bezwzględnej

• identyczna realizacja operacji dodawania dla liczb dodatnich i ujemnych;

• pozycja znaku sumuje się tak jak pozostałe bity

• konwersja ujemno/dodatnia i dodatnio/ujemna są identyczne (zanegować wszystkie bity, dodać 1 do najmniej znaczącej pozycji)

• liczba dodatnia + (-liczba dodatnia) = 0

• jednoznaczna reprezentacja zera

• konwersja binarno-dziesiętna: zamienić liczbę ujemną na dodatnią, przekonwertować na system dziesiętny, dopisać znak "-"

Kod znak - moduł

Kod znak - moduł służy do reprezentowania liczb całkowitych ze znakiem. Liczby dodatnie zapisywane są naturalnym kodzie binarnym, zaś dla liczb ujemnych naturalny kod binarny przyjmowany jest dla wartości bezwzględnej kodowanej liczby, dodatkowo w polu znaku występuje jedynka.

Tabela 6 prezentuje przykład zapisu dodatnich oraz ujemnych liczb całkowitych w kodzie uzupełnieniowym do dwóch oraz w kodzie znak - moduł.

Zapis dziesiętny	Kod uzupełnieniowy do dwóch	Kod znak - moduł
+3	0011	0011
+2	0010	0010
+1	0001	0001
+0	0000	0000
-0	----	1000
-1	1111	1001
-2	1110	1010
-3	1101	1011

Tabela 6. Zapis 4-bitowych liczb dwójkowych ze znakiem w kodzie uzupełnieniowym do dwóch oraz znak - moduł.

Reprezentacja liczb niecałkowitych

Przy opracowaniu sposobu reprezentacji liczb niecałkowitych został wykorzystany fakt, że dowolną liczbę w systemie pozycyjnym o podstawie p można zapisać w postaci:

,

gdzie m oznacza mantysę, zaś c - cechę.

Przykład dla p = 10 (system dziesiętny):

masa słońca = 2∗10³³ g

masa elektronu = 9∗10^-28 g

71,623 = 0,71623 ∗ 10²

0,00098 = 0,98 ∗ 10^-3

-8564,2 = -0,85642 ∗ 10⁴

Przykład dla p = 2 (system binarny):

71,625 = 1000111,101 B = 1000111101 B * 2^{10 B}

Powyższa liczba reprezentowana będzie w systemie binarnym poprzez swoją cechę c = 10 B oraz mantysę m = 1000111101 B.

Arytmetyka zmiennoprzecinkowa

Operacje arytmetyczne na liczbach zmiennoprzecinkowych wykonywane są zgodnie z regułami, z tym że wynik zapisywany jest również w postaci cecha - mantysa. Jeżeli określimy dwie liczby A i B tak, że

natomiast

oraz przyjmiemy, że
to:

Kodowanie znaków alfanumerycznych

Kodami alfanumerycznymi nazywamy takie kody dwójkowe, które określają sposób wzajemnego przyporządkowania znaków alfanumerycznych i słów dwójkowych.

Podstawowym kodem, który umożliwia zapisywanie w systemach cyfrowych tekstów jest ASCII (American Standard Code for Information Interchange), w którym każdemu znakowi przyporządkowany jest kod dwójkowy 8-bitowy (tabela 7). Za pomocą kodu ASCII można zapisać następujące znaki:

• 26 małych liter alfabetu łacińskiego

• 26 dużych liter alfabetu łacińskiego

• cyfry od 0 do 9

• spację

• znaki specjalne, np.: #$%^&*

• znaki sterujące (kody ASCII od 0 do 31), np. tabulator, LF (Line Feed - przejdź do nowego wiersza), CR (Carrige Return - powrót karetki).

Kody powyżej 127 to tzw. zestaw rozszerzony, który pozwala na zapisywanie np. znaków alfabetów narodowych. Wybór odpowiedniego dla danego kraju zestawu odbywa się poprzez wybór strony kodowej.

Cechy kodu:

• bity grupujemy zwykle w paczkach po 8 (8 bitów = 1 bajt).

• za pomocą ośmiu bitów zapisać możemy liczbę z przedziału od 00000000₂ do 11111111₂, czyli od 0 do 255.

• połowę tego przedziału (pierwszych 7 bitów) zajmuje podstawowy zestaw ASCII.

• literom specyficznym dla języków innych niż angielski (np. ąćęłń...) przypisywane są liczby z przedziału 128-255.

• dla języka polskiego obowiązującym w Internecie standardem jest ISO 8859-2.

Dec Hex Bin Znak	Dec Hex Bin Znak	Dec Hex Bin Znak
0 00 0000000 NUL '\0' 1 01 0000001 SOH 2 02 0000010 STX 3 03 0000011 ETX 4 04 0000100 EOT 5 05 0000101 ENQ 6 06 0000110 ACK 7 07 0000111 BEL '\a' 8 08 0001000 BS '\b' 9 09 0001001 HT '\t' 10 0A 0001010 LF '\n' 11 0B 0001011 VT '\v' 12 0C 0001100 FF '\f' 13 0D 0001101 CR '\r' 14 0E 0001110 SO 15 0F 0001111 SI 16 10 0010000 DLE 17 11 0010001 DC1 18 12 0010010 DC2 19 13 0010011 DC3 20 14 0010100 DC4 21 15 0010101 NAK 22 16 0010110 SYN 23 17 0010111 ETB 24 18 0011000 CAN 25 19 0011001 EM 26 1A 0011010 SUB 27 1B 0011011 ESC 28 1C 0011100 FS 29 1D 0011101 GS 30 1E 0011110 RS 31 1F 0011111 US 32 20 0100000 spacja 33 21 0100001 ! 34 22 0100010 `` 35 23 0100011 # 36 24 0100100 $ 37 25 0100101 % 38 26 0100110 & 39 27 0100111 ' 40 28 0101000 ( 41 29 0101001 ) 42 2A 0101010 *	43 2B 0101011 + 44 2C 0101100 , 45 2D 0101101 - 46 2E 0101110 . 47 2F 0101111 / 48 30 0110000 0 49 31 0110001 1 50 32 0110010 2 51 33 0110011 3 52 34 0110100 4 53 35 0110101 5 54 36 0110110 6 55 37 0110111 7 56 38 0111000 8 57 39 0111001 9 58 3A 0111010 : 59 3B 0111011 ; 60 3C 0111100 < 61 3D 0111101 = 62 3E 0111110 > 63 3F 0111111 ? 64 40 1000000 @ 65 41 1000001 A 66 42 1000010 B 67 43 1000011 C 68 44 1000100 D 69 45 1000101 E 70 46 1000110 F 71 47 1000111 G 72 48 1001000 H 73 49 1001001 I 74 4A 1001010 J 75 4B 1001011 K 76 4C 1001100 L 77 4D 1001101 M 78 4E 1001110 N 79 4F 1001111 O 80 50 1010000 P 81 51 1010001 Q 82 52 1010010 R 83 53 1010011 S 84 54 1010100 T 85 55 1010101 U	86 56 1010110 V 87 57 1010111 W 88 58 1011000 X 89 59 1011001 Y 90 5A 1011010 Z 91 5B 1011011 [ 92 5C 1011100 \ '\\' 93 5D 1011101 ] 94 5E 1011110 ^ 95 5F 1011111 _ 96 60 1100000 ` 97 61 1100001 a 98 62 1100010 b 99 63 1100011 c 100 64 1100100 d 101 65 1100101 e 102 66 1100110 f 103 67 1100111 g 104 68 1101000 h 105 69 1101001 i 106 6A 1101010 j 107 6B 1101011 k 108 6C 1101100 l 109 6D 1101101 m 110 6E 1101110 n 111 6F 1101111 o 112 70 1110000 p 113 71 1110001 q 114 72 1110010 r 115 73 1110011 s 116 74 1110100 t 117 75 1110101 u 118 76 1110110 v 119 77 1110111 w 120 78 1111000 x 121 79 1111001 y 122 7A 1111010 z 123 7B 1111011 { 124 7C 1111100 | 125 7D 1111101 } 126 7E 1111110 ~ 127 7F 1111111 DEL

Tabela 7. Kody ASCII.

Obecnie do użytku wprowadzany jest nowy sposób kodowania znaków o nazwie UNICODE. Jest to 16-bitowy standard, w którym jest miejsce na wszystkie alfabety narodowe, dotychczas jeszcze niezbyt powszechny. W przyszłości pozwoli on na uniknięcie niedogodności związanych z ograniczoną pojemnością kodu ASCII i instalowaniem stron kodowych.

Uwaga

W systemie cyfrowym ciąg bitów interpretować możemy na nieskończenie wiele sposobów.

Przykład:

01000011010011110011111100111111 ciąg bitów

C O ? ? ASCII - po 1 bajcie (char)

67 79 63 63 liczby całkowite 8-bitowe

20291 16191 liczby całkowite 2-bajtowe (int)

0.747303187847137451 liczba zmiennoprzecinkowa 4-bajtowa (float)

X XX X XXXX XXXXXX XXXXXX czarno-biały obraz 32x1 piksel

X XX

X XXXX

XXXXXX

XXXXXX czarno-biały obraz 8x4 piksele

Wewnętrzne kody cyfrowe przetwornika

W przetwornikach stosuje się różne kody wewnętrzne zanim uzyska się na wyjściu informację w kodzie dwójkowym.

Kod termometrowy

Zasadniczą cechą zaprezentowanego w tabeli 8 kodu termometrowego jest prawidłowość, że przy wzroście liczby w kodzie dwójkowym „słupek” stanów 1 powiększa się. Kod ten może być łatwo „sprzętowo” przekształcony do postaci dwójkowej wewnątrz przetwornika.

Kod dwójkowy	Kod termometrowy
0000	00000000
0001	00000001
0010	00000011
0011	00000111
0100	00001111
0101	00011111
0110	00111111
0111	01111111
1000	11111111

Tabela 8. Zestawienie kodów dwójkowego i termometrowego.

Kod Graya

Specyficzna właściwość kodu Graya (tabela 9) polega na tym, że przy przejściach od jednego stanu do drugiego zmienia się tylko jeden bit. W związku z tym w czasie pomiaru wzrost sygnału wejściowego powoduje zmianę kolejno tylko jednego bitu. Cechy tej nie posiada na między innymi popularny kod uzupełnieniowy do dwóch. W kodzie tym przykładowo przejście od wartości 0 do -1 jest związane ze zmianą stanu wszystkich bitów.

Kod dziesiętny	Kod dwójkowy	Kod Graya
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

Tabela 9. Zestawienie kodów dwójkowego i Graya.

Kod kołowy

Przy wzrastających wartościach kodu dwójkowego wzrasta liczba stanów 1 w kodzie kołowym, aż następuje całkowite wypełnienie samymi jedynkami (kod 1111). Następnie stanów 1 zaczyna ubywać, aż do osiągnięcia wartości 1000 na końcu zakresu. Kolejną wartością w tym kodzie będzie znowu 0000. W tabeli 10 zestawiono wartości kodu kołowego z odpowiadającymi im wartościami kodu dwójkowego.

Kod dwójkowy	Kod kołowy
000	0000
001	0001
010	0011
011	0111
100	1111
101	1110
110	1100
111	1000

Tabela 10. Zestawienie kodów dwójkowego i kołowego.

5

---